带重启的随机游走采样

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

有向

无向

异构节点

异构关系

加权关系

术语表

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

带重启的随机游走采样在端到端示例 Jupyter notebook 中有介绍

简介

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

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

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

Leskovec 等人在论文《大型图的采样》("Sampling from Large Graphs") 中表明，RWR 是一种非常好的采样算法，可以保留被采样的原始图的结构特征。此外，RWR 在文献中已被成功用于采样图神经网络 (GNN) 训练的批次。

带重启的随机游走有时也称为根植 (rooted) 或个性化 (personalized) 随机游走。

关系权重

如果图是加权的，并且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 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	一个可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将运行非加权。
samplingRatio	浮点数	`0.15`	是	原始图中要采样的节点分数。
restartProbability	浮点数	`0.1`	是	采样随机游走从起始节点之一重启的概率。
startNodes	整数列表	`均匀随机选择一个节点`	是	原始图的初始节点集的ID，采样随机游走将从这些节点开始。
nodeLabelStratification	布尔值	`false`	是	如果为 true，则保留原始图的节点标签分布。
randomSeed	整数	`不适用`	是	一个随机种子，用于计算中所有随机性。需要`concurrency = 1`。
1. 在GDS Session中，默认值为可用处理器数量

表 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);

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

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

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

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节点。采样到的关系是连接这些节点的关系。