带重启随机游走采样

此功能处于 Alpha 阶段。有关功能阶段的更多信息，请参阅 API 阶段。

有向

无向

异构节点

异构关系

加权关系

词汇表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不能在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点进行类似的处理，而不管其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系进行类似的处理，而不管其类型如何。
加权关系: 加权特性。该算法支持使用关系属性作为权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，丢弃任何关系权重的值。

带重启随机游走采样在端到端示例 Jupyter 笔记本中有所体现

简介

有时，拥有给定图的结构上具有代表性但规模较小的样本可能很有用。例如，此类样本可用于训练归纳嵌入算法（例如图神经网络，如 GraphSAGE）。然后，训练将比在整个图上训练更快，并且训练后的模型仍可用于预测整个图上的嵌入。

带重启随机游走 (RWR) 通过从一组起始节点进行随机游走来对图进行采样（参见下面的 startNodes 参数）。在随机游走的每个步骤中，都有一定的概率（参见下面的 restartProbability 参数）使游走停止，并从起始节点之一开始新的游走（即游走重启）。这些游走中访问的每个节点都将成为采样子图的一部分。当访问到所需数量的节点时，算法停止游走（参见下面的 samplingRatio 参数）。采样子图的关系是由采样节点诱导的（即连接已采样节点的原始图的关系）。

如果在某个时刻，从当前起始节点集进行随机游走不太可能访问到新的节点（可能是由于原始图不连通），则算法将通过从原始图中随机均匀地选择节点，一次一个地延迟扩展起始节点池。

Leskovec 等人在论文“从大型图中采样”中证明，RWR 是一种非常好的采样算法，可以保留所采样原始图的结构特征。此外，RWR 在文献中已被成功用于对图神经网络 (GNN) 训练的批次进行采样。

带重启随机游走有时也称为根或个性化随机游走。

关系权重

如果图是有权重的，并且指定了 relationshipWeightProperty，则随机游走是有权重的。这意味着沿着关系游走的概率是该关系的权重除以当前节点发出关系的权重总和。

节点标签分层

在某些情况下，可能希望采样图保留原始图的节点标签分布。为了启用这种分层，可以在算法配置中将 nodeLabelStratification 设置为 true。分层采样通过仅在需要更多具有该节点特定标签集的节点来维持原始图的节点标签分布时，才将节点添加到采样图中来执行。

默认情况下，算法以相同的方式处理所有节点，无论它们如何标记，并且不会特别努力保留原始图的节点标签分布。请注意，分层采样可能会稍微慢一些，因为它在爬取图时对可以添加到采样图中的节点类型有限制。

目前不支持关系类型分层。

语法

以下是运行算法的 API 说明

CALL gds.graph.sample.rwr(
  graphName: String,
  fromGraphName: String,
  configuration: Map
)
YIELD
  graphName,
  fromGraphName,
  nodeCount,
  relationshipCount,
  startNodeCount,
  projectMillis

表 1. 参数
名称	类型	描述
graphName	字符串	存储在图目录中的新图的名称。
fromGraphName	字符串	图目录中原始图的名称。
configuration	映射	配置子图采样的其他参数。

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供的 ID，以便更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性的名称。如果未指定，则算法将运行无权重。
samplingRatio	浮点数	`0.15`	是	要采样的原始图中节点的比例。
restartProbability	浮点数	`0.1`	是	采样随机游走从起始节点之一重启的概率。
startNodes	整数列表	`随机均匀选择的节点`	是	原始图中初始节点集的 ID，从中开始采样随机游走。
nodeLabelStratification	布尔值	`false`	是	如果为 true，则保留原始图的节点标签分布。
randomSeed	整数	`n/a`	是	用于计算中所有随机性的随机种子。需要 `concurrency = 1`。

表 3. 结果
名称	类型	描述
graphName	字符串	存储在图目录中的新图的名称。
fromGraphName	字符串	图目录中原始图的名称。
nodeCount	整数	子图中的节点数。
relationshipCount	整数	子图中的关系数。
startNodeCount	整数	算法实际使用的起始节点数。
projectMillis	整数	投影子图所用的毫秒数。

示例

以下所有示例都应在空数据库中运行。

这些示例使用 Cypher 投影作为规范。原生投影将在将来的版本中弃用。

在本节中，我们将演示在小型玩具图上使用 RWR 采样算法。

设置

在本节中，我们将展示在具体图上运行带重启随机游走采样算法的示例。目的是说明结果是什么样的，并提供有关如何在实际环境中使用该算法的指南。我们将在少量节点以特定模式连接的小型社交网络图上执行此操作。示例图如下所示

以下 Cypher 语句将在 Neo4j 数据库中创建示例图

CREATE
  (nAlice:User {name: 'Alice'}),
  (nBridget:User {name: 'Bridget'}),
  (nCharles:User {name: 'Charles'}),
  (nDoug:User {name: 'Doug'}),
  (nMark:User {name: 'Mark'}),
  (nMichael:User {name: 'Michael'}),

  (nAlice)-[:LINK]->(nBridget),
  (nAlice)-[:LINK]->(nCharles),
  (nCharles)-[:LINK]->(nBridget),

  (nAlice)-[:LINK]->(nDoug),

  (nMark)-[:LINK]->(nDoug),
  (nMark)-[:LINK]->(nMichael),
  (nMichael)-[:LINK]->(nMark);

此图有两个紧密连接的用户集群。这两个集群之间只有一个关系。

现在，我们可以投影图并将其存储在图目录中。

以下语句将投影图并将其存储在图目录中。

MATCH (n:User)-[r:LINK]->(m:User)
RETURN gds.graph.project('myGraph', n, m)

采样

现在，我们可以继续使用 RWR 从“myGraph”中采样子图。使用“Alice”User节点作为我们的起始节点集，我们将尝试访问图中的四个节点作为我们的样本。由于我们的图中总共有六个节点，并且 4/6 ≈ 0.66，因此我们将将其用作我们的采样比率。

以下将运行带重启随机游走采样算法

MATCH (start:User {name: 'Alice'})
CALL gds.graph.sample.rwr('mySample', 'myGraph', { samplingRatio: 0.66, startNodes: [start] })
YIELD nodeCount, relationshipCount
RETURN nodeCount, relationshipCount

表 4. 结果
nodeCount	relationshipCount
4	4

如我们所见，我们确实访问了四个节点。查看原始图“myGraph”的拓扑结构，我们可以得出结论，这些节点必须是对应于名称属性为“Alice”、“Bridget”、“Charles”和“Doug”的User节点的节点。并且采样的关系是连接这些节点的关系。