随机游走

此功能在 Aura 图分析无服务器中不可用。

有向

无向

异构节点

异构关系

加权关系

术语表

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

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

随机游走模拟了图的遍历，其中遍历的关系是随机选择的。在经典的随机游走中，每个关系被选中的概率相同，可能加权。这个概率不受之前访问过的节点的影响。Neo4j 图数据科学库的随机游走实现支持二阶随机游走的概念。该方法试图根据当前访问的节点 v、当前节点之前访问过的节点 t 以及候选关系的`目标节点 x 来建模转移概率。因此，随机游走受到两个参数的影响：`returnFactor` 和 `inOutFactor`

当 `t` 等于 `x` 时，即随机游走返回到先前访问的节点时，使用 `returnFactor`。
当 `t` 到 `x` 的距离等于 2 时，即游走路径进一步远离节点 `t` 时，使用 `inOutFactor`。

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

为了获得一个转移概率独立于先前访问节点的随机游走，`returnFactor` 和 `inOutFactor` 都可以设置为 1.0。

运行此算法需要足够的内存。在运行此算法之前，我们建议您阅读内存估算。

语法

每种模式的 RandomWalk 语法

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

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

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

表 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	整数	`随机`	是	用于生成随机游走的随机数生成器的种子值。
walkBufferSize	整数	`1000`	是	在开始训练之前要完成的随机游走次数。
1. 在 GDS 会话中，默认值为可用处理器数量

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

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

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

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

表 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	整数	`随机`	是	用于生成随机游走的随机数生成器的种子值。
walkBufferSize	整数	`1000`	是	在开始训练之前要完成的随机游走次数。
2. 在 GDS 会话中，默认值为可用处理器数量

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

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

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

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

表 8. 配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`不适用`	否	GDS 图中写入随机游走访问计数的节点属性。
sourceNodes	整数列表	`所有节点列表`	是	进行随机游走的起始节点列表。
walkLength	整数	`80`	是	单次随机游走的步数。
walksPerNode	整数	`10`	是	为每个节点生成的随机游走次数。
inOutFactor	浮点数	`1.0`	是	随机游走倾向于停留在起始节点附近或在图中扩散。值越高表示倾向于停留在本地。
returnFactor	浮点数	`1.0`	是	随机游走返回到最后访问节点的倾向。值低于 1.0 表示更高的倾向。
relationshipWeightProperty	字符串	`null`	是	用作权重以影响随机游走概率的关系属性名称。权重必须 >= 0。如果未指定，算法将运行非加权。
randomSeed	整数	`随机`	是	用于生成随机游走的随机数生成器的种子值。
walkBufferSize	整数	`1000`	是	在开始训练之前要完成的随机游走次数。

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

示例

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

这些示例通常使用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	页面
[0, 6, 0]	["主页", "站点 C", "主页"]
[3, 5, 3]	["链接", "站点 B", "链接"]
[2, 0, 1]	["产品", "主页", "关于"]
[1, 0, 4]	["关于", "主页", "站点 A"]
[7, 3, 0]	["站点 D", "链接", "主页"]
[6, 0, 2]	["站点 C", "主页", "产品"]
[5, 0, 7]	["站点 B", "主页", "站点 D"]
[4, 0, 2]	["站点 A", "主页", "产品"]

指定源节点

在 `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	页面
[0, 6, 0]	["主页", "站点 C", "主页"]
[1, 0, 4]	["关于", "主页", "站点 A"]

统计

在 `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}

变异

在 `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"

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

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. 结果
页面	randomWalksCount
"关于"	1
"主页"	6
"链接"	6
"产品"	1
"站点 A"	3
"站点 B"	1
"站点 C"	4
"站点 D"	2