带重启的随机游走采样

术语表

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

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

简介

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

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

如果在某个时刻，通过从当前起始节点集进行随机游走来访问新节点的可能性非常低（可能是由于原始图是不连通的），算法将通过从原始图中均匀随机选择节点，逐个懒加载地扩展起始节点池。

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

带重启的随机游走有时也被称为根节点随机游走 (rooted random walk) 或个性化随机游走 (personalized random walk)。

关系权重

如果图是加权的，并且指定了 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	字符串	图目录中原始图的名称。
配置	Map	用于配置子图采样的附加参数。

表 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 会话中，默认值为可用处理器的数量。

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

该图有两个紧密相连的用户 (Users) 集群。在这两个集群之间有一条单独的关系。

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

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

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

采样 (Sampling)

现在我们可以继续使用 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 节点。而采样的关系是连接这些节点的关系。