基于公共邻居感知的随机游走采样

此功能处于 Beta 测试阶段。有关功能分级的更多信息，请参阅 API 分级。

术语表

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

简介

图采样算法可用于在保持结构属性的同时减小大型复杂图的规模。这有助于减少偏差、确保隐私并提高图分析的可扩展性。采样算法被广泛应用于机器学习、社交网络分析及许多其他领域。

公共邻居感知随机游走 (CNARW) 是一种图采样技术，它通过优化下一跳节点的选择来实现。它考虑了当前节点与下一跳候选节点之间的公共邻居数量。

据论文所述，简单随机游走收敛缓慢的主要原因之一是某些类型图（例如在线社交网络 OSN）典型的高聚类特征。当随机均匀地移动到邻居时，很容易陷入局部循环并重新访问之前访问过的节点，从而减慢收敛速度。

为了解决这个问题，一种解决方案是优先选择在每一步中更有可能探索未访问节点的节点。度数较高的节点可能提供这种机会，但它们也可能与之前访问过的节点有更多的公共邻居，从而增加了重新访问的可能性。

因此，选择度数较高且与之前访问过的节点（或当前节点）公共邻居较少的节点，不仅增加了发现未访问节点的机会，还降低了在未来步骤中重新访问已访问节点的概率。

该算法的实现基于以下论文

公共邻居很重要：具有公共邻居感知能力的快速随机游走采样

关系权重

与 RandomWalksWithRestarts 算法中的 relationshipWeightProperty 参数相同。

节点标签分层

与 RandomWalksWithRestarts 算法中的 nodeLabelStratification 参数相同。

语法

以下描述了用于运行该算法的 API

CALL gds.graph.sample.cnarw(
  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 投影。原生投影将在未来版本中弃用。

在本节中，我们将演示如何在小型演示图上使用 CNARW 采样算法。

设置

在本节中，我们将展示在具体图上运行公共邻居感知随机游走图采样算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指南。我们将使用一个连接方式特定的、包含少量节点的小型社交网络图。示例图如下所示

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

CREATE
    (J:Female {name:'Juliette'}),
    (R:Male {name:'Romeo'}),
    (r1:Male {name:'Ryan'}),
    (r2:Male {name:'Robert'}),
    (r3:Male {name:'Riley'}),
    (r4:Female {name:'Ruby'}),
    (j1:Female {name:'Josie'}),
    (j2:Male {name:'Joseph'}),
    (j3:Female {name:'Jasmine'}),
    (j4:Female {name:'June'}),
    (J)-[:LINK]->(R),
    (R)-[:LINK]->(J),
    (r1)-[:LINK]->(R),   (R)-[:LINK]->(r1),
    (r2)-[:LINK]->(R),   (R)-[:LINK]->(r2),
    (r3)-[:LINK]->(R),   (R)-[:LINK]->(r3),
    (r4)-[:LINK]->(R),   (R)-[:LINK]->(r4),
    (r1)-[:LINK]->(r2),  (r2)-[:LINK]->(r1),
    (r1)-[:LINK]->(r3),  (r3)-[:LINK]->(r1),
    (r1)-[:LINK]->(r4),  (r4)-[:LINK]->(r1),
    (r2)-[:LINK]->(r3),  (r3)-[:LINK]->(r2),
    (r2)-[:LINK]->(r4),  (r4)-[:LINK]->(r2),
    (r3)-[:LINK]->(r4),  (r4)-[:LINK]->(r3),
    (j1)-[:LINK]->(J),   (J)-[:LINK]->(j1),
    (j2)-[:LINK]->(J),   (J)-[:LINK]->(j2),
    (j3)-[:LINK]->(J),   (J)-[:LINK]->(j3),
    (j4)-[:LINK]->(J),   (J)-[:LINK]->(j4),
    (j1)-[:LINK]->(j2),  (j2)-[:LINK]->(j1),
    (j1)-[:LINK]->(j3),  (j3)-[:LINK]->(j1),
    (j1)-[:LINK]->(j4),  (j4)-[:LINK]->(j1),
    (j2)-[:LINK]->(j3),  (j3)-[:LINK]->(j2),
    (j2)-[:LINK]->(j4),  (j4)-[:LINK]->(j2),
    (j3)-[:LINK]->(j4),  (j4)-[:LINK]->(j3) ;

该图有两个联系紧密的 Users 集群。这些集群之间存在双向关系。

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

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

MATCH (n:Male|Female)-[r:LINK]->(m:Male|Female)
RETURN gds.graph.project('graph', n, m,
  {
    sourceNodeLabels: labels(n),
    targetNodeLabels: labels(m),
    relationshipType: type(r)
  }
)

采样 (Sampling)

现在我们可以继续使用 CNARW 从 "myGraph" 中采样一个子图。使用 "Juliette" 节点作为我们的起始节点集，我们将尝试访问图中的五个节点作为样本。由于我们的图中总共有六个节点，且 5/10 = 0.5，我们将此值用作我们的采样率。

以下代码将运行公共邻居感知随机游走采样算法

MATCH (start:Female {name: 'Juliette'})
CALL gds.graph.sample.cnarw('sampledGraph', 'graph',
{
    samplingRatio: 0.5,
    startNodes: [start]
})
YIELD nodeCount
RETURN nodeCount;

表 4. 结果
nodeCount
5

由于采样的随机性，该算法在不同运行中可能会返回不同的计数。

公共邻居感知随机游走与带重启随机游走图采样算法的主要区别在于，前者有更多机会进入另一个集群（在上面的示例中以蓝色标出）。采样的关系是连接这些节点的边。

内存估算

首先，我们将使用 estimate 过程来估算运行该算法的开销。这可以在任何执行模式下完成。对采样过程进行估算有助于了解在图上运行该过程对内存的影响。如果估算显示执行超出其内存限制的概率极高，则会禁止执行。要了解更多相关信息，请参阅自动估算与执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估算。

以下代码将估算运行该采样算法所需的内存

CALL gds.graph.sample.cnarw.estimate('graph',
{
    samplingRatio: 0.5
})
YIELD requiredMemory
RETURN requiredMemory;

表 5. 结果
requiredMemory
"1272 字节"