随机游走 (Random Walk)

在 Aura Graph Analytics 中，此功能仅通过 Python 客户端提供。它目前无法作为 Cypher 过程或函数使用。

术语表

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

随机游走是一种在图中提供随机路径的算法。

随机游走模拟了图的一种遍历方式，其中被遍历的关系是随机选择的。在经典的随机游走中，每个关系被选中的概率相同（或按权重分配）。此概率不受之前访问过的节点影响。Neo4j 图数据科学 (GDS) 库的随机游走实现支持二阶随机游走的概念。该方法尝试基于当前访问的节点 v、当前节点之前的节点 t 以及候选关系的目标节点 x 来建模转移概率。因此，随机游走受两个参数影响：returnFactor（返回因子）和 inOutFactor（进出因子）。

如果 t 等于 x，即随机游走返回到之前访问的节点时，使用 returnFactor。
如果从 t 到 x 的距离等于 2，即游走进一步远离节点 t 时，使用 inOutFactor。

在随机游走期间遍历关系的概率可以通过指定 relationshipWeightProperty 进一步受到影响。大于 1 的关系属性值将增加遍历该关系的概率，介于 0 和 1 之间的属性值将降低该概率。

若要获得转移概率与之前访问过的节点无关的随机游走，可以将 returnFactor 和 inOutFactor 均设置为 1.0。

运行此算法需要足够的可用内存。在运行之前，建议您阅读内存估计 (Memory Estimation)。

语法

按模式划分的 RandomWalk 语法

在命名图上以流 (stream) 模式运行 RandomWalk。

CALL gds.randomWalk.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeIds: List of Integer,
  path: Path

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNodes	整数列表	`所有节点列表`	是	用于执行随机游走的节点列表。
walkLength	整数	`80`	是	单次随机游走的步数。
walksPerNode	整数	`10`	是	为每个节点生成的随机游走次数。
inOutFactor	浮点数	`1.0`	是	随机游走倾向于停留在起始节点附近还是在图中向外扩散。值越大，越倾向于局部停留。
returnFactor	浮点数	`1.0`	是	随机游走倾向于返回上次访问的节点的程度。低于 1.0 的值表示倾向性更高。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称，用于影响随机游走的概率。权重需要 >= 0。如果未指定，算法将以无权重方式运行。
randomSeed	整数	`random`	是	用于生成随机游走的随机数生成器的种子值。
walkBufferSize	整数	`1000`	是	开始训练前要完成的随机游走次数。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
`nodeIds`	整数列表	随机游走的节点。
`path`	路径	随机游走的 `Path` 对象。

在命名图上以统计 (stats) 模式运行 RandomWalk。

CALL gds.randomWalk.stats(
  graphName: String,
  configuration: Map
)
YIELD
  preProcessingMillis: Integer,
  computeMillis: Integer,
  configuration: Map

表 4. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNodes	整数列表	`所有节点列表`	是	用于执行随机游走的节点列表。
walkLength	整数	`80`	是	单次随机游走的步数。
walksPerNode	整数	`10`	是	为每个节点生成的随机游走次数。
inOutFactor	浮点数	`1.0`	是	随机游走倾向于停留在起始节点附近还是在图中向外扩散。值越大，越倾向于局部停留。
returnFactor	浮点数	`1.0`	是	随机游走倾向于返回上次访问的节点的程度。低于 1.0 的值表示倾向性更高。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称，用于影响随机游走的概率。权重需要 >= 0。如果未指定，算法将以无权重方式运行。
randomSeed	整数	`random`	是	用于生成随机游走的随机数生成器的种子值。
walkBufferSize	整数	`1000`	是	开始训练前要完成的随机游走次数。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
`preProcessingMillis`	整数	预处理数据的毫秒数。
`computeMillis`	整数	运行算法的毫秒数。
`配置`	Map	用于运行算法的配置。

在命名图上以变异 (mutate) 模式运行 RandomWalk。

CALL gds.randomWalk.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  nodePropertiesWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  postProcessingMillis: Integer,
  configuration: Map

表 7. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 8. 配置
名称	类型	默认	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中用于写入随机游走访问次数的节点属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNodes	整数列表	`所有节点列表`	是	用于执行随机游走的节点列表。
walkLength	整数	`80`	是	单次随机游走的步数。
walksPerNode	整数	`10`	是	为每个节点生成的随机游走次数。
inOutFactor	浮点数	`1.0`	是	随机游走倾向于停留在起始节点附近还是在图中向外扩散。值越大，越倾向于局部停留。
returnFactor	浮点数	`1.0`	是	随机游走倾向于返回上次访问的节点的程度。低于 1.0 的值表示倾向性更高。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称，用于影响随机游走的概率。权重需要 >= 0。如果未指定，算法将以无权重方式运行。
randomSeed	整数	`random`	是	用于生成随机游走的随机数生成器的种子值。
walkBufferSize	整数	`1000`	是	开始训练前要完成的随机游走次数。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 9. 结果
名称	类型	描述
`nodePropertiesWritten`	整数	添加到投影图中的属性数量。
`preProcessingMillis`	整数	预处理数据的毫秒数。
`computeMillis`	整数	运行算法的毫秒数。
`mutateMillis`	整数	向投影图添加属性的毫秒数。
`postProcessingMillis`	整数	未使用。
`配置`	Map	用于运行算法的配置。

示例

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

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

考虑由以下 Cypher 语句创建的图

CREATE (home:Page {name: 'Home'}),
       (about:Page {name: 'About'}),
       (product:Page {name: 'Product'}),
       (links:Page {name: 'Links'}),
       (a:Page {name: 'Site A'}),
       (b:Page {name: 'Site B'}),
       (c:Page {name: 'Site C'}),
       (d:Page {name: 'Site D'}),

       (home)-[:LINKS]->(about),
       (about)-[:LINKS]->(home),
       (product)-[:LINKS]->(home),
       (home)-[:LINKS]->(product),
       (links)-[:LINKS]->(home),
       (home)-[:LINKS]->(links),
       (links)-[:LINKS]->(a),
       (a)-[:LINKS]->(home),
       (links)-[:LINKS]->(b),
       (b)-[:LINKS]->(home),
       (links)-[:LINKS]->(c),
       (c)-[:LINKS]->(home),
       (links)-[:LINKS]->(d),
       (d)-[:LINKS]->(home)

MATCH (source:Page)-[r:LINKS]->(target:Page)
RETURN gds.graph.project(
  'myGraph',
  source,
  target,
  {},
  { undirectedRelationshipTypes: ['*'] }
)

不指定源节点

在 myGraph 上运行 RandomWalk 算法

CALL gds.randomWalk.stream(
  'myGraph',
  {
    walkLength: 3,
    walksPerNode: 1,
    randomSeed: 42,
    concurrency: 1
  }
)
YIELD nodeIds, path
RETURN nodeIds, [node IN nodes(path) | node.name ] AS pages

表 10. 结果
nodeIds	pages
[0, 6, 0]	["Home", "Site C", "Home"]
[3, 5, 3]	["Links", "Site B", "Links"]
[2, 0, 1]	["Product", "Home", "About"]
[1, 0, 4]	["About", "Home", "Site A"]
[7, 3, 0]	["Site D", "Links", "Home"]
[6, 0, 2]	["Site C", "Home", "Product"]
[5, 0, 7]	["Site B", "Home", "Site D"]
[4, 0, 2]	["Site A", "Home", "Product"]

指定源节点

在 myGraph 上运行指定 sourceNodes 的 RandomWalk 算法

MATCH (page:Page)
WHERE page.name IN ['Home', 'About']
WITH COLLECT(page) as sourceNodes
CALL gds.randomWalk.stream(
  'myGraph',
  {
    sourceNodes: sourceNodes,
    walkLength: 3,
    walksPerNode: 1,
    randomSeed: 42,
    concurrency: 1
  }
)
YIELD nodeIds, path
RETURN nodeIds, [node IN nodes(path) | node.name ] AS pages

表 11. 结果
nodeIds	pages
[0, 6, 0]	["Home", "Site C", "Home"]
[1, 0, 4]	["About", "Home", "Site A"]

统计信息 (Stats)

在 myGraph 上运行 RandomWalk 统计模式

CALL gds.randomWalk.stats(
  'myGraph',
  {
    walkLength: 3,
    walksPerNode: 1,
    randomSeed: 42,
    concurrency: 1
  }
)

表 12. 结果
preProcessingMillis	computeMillis	配置
0	1	{randomSeed=42, walkLength=3, jobId=b77f3147-6683-4249-8633-4db7da03f24d, sourceNodes=[], walksPerNode=1, inOutFactor=1.0, nodeLabels=[], sudo=false, relationshipTypes=[], walkBufferSize=1000, returnFactor=1.0, concurrency=1}

Mutate

在 myGraph 上运行 RandomWalk 变异模式

CALL gds.randomWalk.mutate(
  'myGraph',
  {
    walkLength: 3,
    walksPerNode: 1,
    randomSeed: 19,
    concurrency: 1,
    mutateProperty: 'randomWalksCount'
  }
)
YIELD nodePropertiesWritten, configuration
RETURN nodePropertiesWritten, configuration.mutateProperty AS mutateProperty

表 13. 结果
nodePropertiesWritten	mutateProperty
8	"randomWalksCount"

然后，我们可以流式传输变异后的节点属性，以查看它在多少次 RandomWalk 中出现过

CALL gds.graph.nodeProperty.stream('myGraph', 'randomWalksCount')
YIELD nodeId, propertyValue
RETURN gds.util.asNode(nodeId).name AS page, propertyValue AS randomWalksCount
ORDER BY page ASC

表 14. 结果
page	randomWalksCount
"About"	1
"Home"	6
"Links"	6
"Product"	1
"Site A"	3
"Site B"	1
"Site C"	4
"Site D"	2