感知共同邻居的随机游走采样

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

有向

无向

异构节点

异构关系

加权关系

词汇表

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

介绍

图采样算法可用于在保留结构属性的同时减小大型复杂图的大小。这有助于减少偏差，确保隐私，并使图分析更具可扩展性。采样算法广泛用于机器学习、社交网络分析以及许多其他应用中。

常见邻居感知随机游走 (CNARW) 是一种图采样技术，它涉及优化下一跳节点的选择。它考虑了当前节点和下一跳候选节点之间共同邻居的数量。

根据这篇论文，简单随机游走收敛速度慢的主要原因是，一些类型的图（例如，在线社交网络 (OSN)）通常具有很高的聚类特性。当随机地移动到邻居时，很容易陷入局部循环并重新访问先前访问过的节点，这会减慢收敛速度。

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

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

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

常见邻居很重要：具有常见邻居感知的快速随机游走采样

关系权重

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

节点标签分层

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

语法

以下是运行该算法的 API 说明

CALL gds.graph.sample.cnarw(
  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	布尔值	`真`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`空`	是	用作权重的关系属性的名称。如果未指定，则算法将以无权重方式运行。
samplingRatio	浮点数	`0.15`	是	要从原始图中采样的节点的比例。
restartProbability	浮点数	`0.1`	是	采样随机游走从其中一个起点重新开始的概率。
startNodes	整数或节点列表	`均匀随机选择的节点`	是	原始图中初始节点集的 ID，从该节点集开始采样随机游走。
nodeLabelStratification	布尔值	`假`	是	如果为真，则保留原始图的节点标签分布。
randomSeed	整数	`n/a`	是	用于控制算法随机性的种子值。请注意，在设置此参数时，`concurrency` 必须设置为 1。

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

此图有两个紧密相连的“用户”集群。在这些集群之间存在双向关系。

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

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

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)
  }
)

采样

现在，我们可以继续使用 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 字节"