使用cypher和gremlin进行图随机游走

2019-12-26 10:39:04

随机游走简介

随机游走，又称随机漫步，英文为‘random walk’。在wiki上的解释是这样的：

A random walk is a mathematical object, known as a stochastic or random process, that describes a path that consists of a succession of random steps on some mathematical space such as the integers.

比较抽象，在此就不解释了。举些例子比较直观，其实自然界和人类社会中，随机游走的例子非常多：

分子在液体或气体中的运动轨迹（我们每个人都学过的‘布朗运动’）；

觅食动物搜寻食物的轨迹；

股市中的股票价格波动轨迹（惊不惊喜，意不意外！）；

职业赌徒的财务状况等；

正因为如此，随机游走在工程和许多科学领域都有应用，包括生态学、心理学、计算机科学、物理学、化学、生物学以及经济学等等。随机游动解释了这些领域中许多被观察到的过程行为，从而成为这些被记录的随机活动的基本模型。

更多随机游走例子和应用请参考wiki，在此不深入描述。

随机游走在机器学习等算法中的使用

本文主要关注属性图中的随机游走，所谓属性图就是有节点/顶点、边及其他们属性构成的图。那么随机游走就是从图中的一个顶点出发，沿着符合条件的边向外不断扩展n次得到的路径。

在图数据库中，随机游走常常作为其他图算法的一部分，如作为机器学习模型训练过程的一部分，这是因为典型的机器学习输入是固定大小的表格数据。而图是由任意个顶点和边组成的灵活的结构，因此很难将图作为机器学习的输入。

而随机游走是一种强大的获取图的连接特性并将其保存在简单的数据结构中的方法。每次随机游走都会输出一个固定大小的路径，如果在一个图上获取足够多数量的随机游走，那么就能够充分表达整个图的连接特性。换种方式说，一个随机游走就是对图的一次采样，只要采样次数够多，那么就能将数据源足够得表达出来。该种方式已经在语言建模、社交网络和蛋白质结构领域得到了非常成功的应用。

了解通过随机游走来提高TensorFlow学习精度的例子。

除了机器学习之外，随机游走还广泛应用在其他图算法中，包括：

作为node2vec和graph2vec的一部分；

作为某些社区发现（community detection）算法的一部分，如果随机游走重复返回一小组节点，则表明这些节点可能具有一个社区结构；

作为Google pagerank算法的一部分；

使用cypher获取随机游走

cypher是Neo4j图数据库的操作语言，其他一些图数据库也通过将cypher转换为自己的图查询语言来兼容cypher。Neo4j是当前为流行的图数据库，掌握使用cypher进行随机游走是一项基本要求。

Neo4j为用户提供了丰富的图算法实现API，这些API本来位于Neo4j存储过程包neo4j-apoc-procedures中，在新版本中已经独立为一个新算法包neo4j-graph-algorithms。支持的图算法包括：Centralities,Community detection,Path finding,Similarity,Link Prediction和Preprocessing等；在此不一一展开，更详细的介绍请戳这里。

这些算法中许多都是迭代方法，需使用随机游走、广度优先或深度优先搜索或模式匹配来遍历图形进行计算。因此，可以说随机游走是一种基础算法。

cypher的随机游走语法

随机游走语法如下所示：algo表示其位于算法包中，randomWalk即为算法的名称，stream后的括号中为本次游走的参数。

CALL algo.randomWalk.stream(start:Object, steps: 100, walks: 10000,
    {graph:'heavy', nodeQuery:'label or query', relationshipQuery:' type or query', direction:"IN/OUT/BOTH",
     mode:"node2vec"/"random", inOut: 1.0, return: 1.0, path:false, concurrency:4})
YIELD nodes, path

具体参数的说明如下图所示：

其中，start为随机游走的起点，如果为null，表示从整个图中随机选择一个节点作为起点；steps表示随机游走路径包含多少步；walks表示需要返回多少条游走路径；graph,nodeQuery,relationshipQuery为3个关联参数，graph可以为heavy或cypher，如果为cypher，则nodeQuery和relationshipQuery为用于查找符合条件的节点和边的cypher语句，如果为heavy，则2个参数分别为节点标签和边的类型；direction表示游走路径上边的方向；mode,inOut,return也是一组关联参数，inOut和return仅在mode为node2vec是有效；path表示是否需要返回完整的游走路径；concurrency表示并发任务个数；YIELD后指定本次游走需要返回的对象。

下面举在公司内部某业务上使用到的cypher语句作为例子进行说明：

CALL algo.randomWalk.stream(null, 20, 10,{graph:'heavy' 
 , nodeQuery:"user" 
 , relationshipQuery:"usertouser" 
 , direction:'BOTH' 
 , mode:'node2vec' 
, inOut: 0.8, return: 0.2 
 , path:true, concurrency:20}) YIELD startNodeId,nodeIds as id 
 return startNodeId,id;

该例子未指定游走起始节点，需要进行10次游走，每次由20步组成；采用heavy模式产生游走所需的虚拟子图，所以nodeQuery为节点标签user，relationshipQuery为边的类型usertouser；这里指定的并发数为20，需要说明的是Neo4j的社区版大并发数只能为4；游走模式为node2vec，因此inOut和return有效，分别为0.8和0.2；

CALL algo.randomWalk.stream([21243,21228], 20, 10,{graph:'heavy' 
 , nodeQuery:"user" 
 , relationshipQuery:"usertouser" 
 , direction:'BOTH' 
 , mode:'node2vec' 
, inOut: 0.8, return: 0.2 
 , path:false, concurrency:20}) YIELD startNodeId,nodeIds as id
 return startNodeId,id;

本例子与上例不同的是，起点为2个节点组成的数组；

match (n:user{vid:'6226683'}) with id(n) as ids 
 CALL algo.randomWalk.stream(ids, 20, 10,{graph:'heavy' 
 , nodeQuery:"user" 
 , relationshipQuery:"usertouser" 
 , direction:'BOTH' 
 , mode:'node2vec' 
, inOut: 0.8, return: 0.2 
 , path:false, concurrency:20}) YIELD startNodeId,nodeIds as id 
 return startNodeId,id;

第三个例子，通过一个cypher语句来指定起始节点，该节点的id为6226683；

match (n:user{randomWalk:1}) with n limit 5 with collect(id(n)) as ids 
 CALL algo.randomWalk.stream(ids, 20, 10,{graph:'heavy' 
 , nodeQuery:"user" 
 , relationshipQuery:"usertouser" 
 , direction:'BOTH' 
 , mode:'node2vec' 
, inOut: 0.8, return: 0.2 
 , path:false, concurrency:20}) YIELD startNodeId,nodeIds as id
 return startNodeId,id;

第四个例子，通过另一个cypher语句来指定起始节点集合，作为起点的节点标签为user且均有类型为randomWalk的边，选择符合要求的前5个节点作为起始节点。这里值得注意的有2点：

需要使用collect()来将查询结果转成集合传入randomWalk算法API中（例中为ids），否则，cypher语句返回的每个id都会调用一次randomWalk API，从而得到错误的结果；
walks指定的参数10为本次调用一共返回10条游走，而不是每个起点返回10条。

CALL algo.randomWalk.stream(null, 20, 10,{graph:'cypher' 
 , nodeQuery:"match (n:user) where n.lastModifyDate>='2019-04-01' with n SKIP $skip LIMIT $limit return id(n) as id" 
 , relationshipQuery:"match (n:user)-[r:usertouser]-(m:user) where n.vid<m.vid with id(n) as source,id(m) as target,r.weight as weight SKIP $skip LIMIT $limit return source,target,weight" 
 , direction:'BOTH' 
 , mode:'node2vec' 
, inOut: 0.8, return: 0.2 
 , path:false, concurrency:20,batchSize:500000}) YIELD startNodeId,nodeIds as id
 return startNodeId,id;

后一个例子的图产生模式为cypher，即用cypher语句来加载符合条件的节点和边，节点和边的条件分别为：

match (n:user) where n.lastModifyDate>='2019-04-01' with n SKIP $skip LIMIT $limit return id(n) as id

和

match (n:user)-[r:usertouser]-(m:user) where n.vid<m.vid with id(n) as source,id(m)

表示选择标签为user且lastModifyDate属性大于等于2019-04-01年的节点，源节点id小于目标节点id的类型为usertouser的边。在本例中，还有SKIP $skip LIMIT $limit关键词，用于并行加载随机游走所需子图，这两个参数可与batchSize配合使用，batchSzie表示加载子图时batch大小，如指定500000，则个任务为SKIP 0 LIMIT 500000，第二个任务为SKIP 500000 LIMIT 500000；任务并发数由concurrency指定。

使用gremlin获取随机游走

与cypher相似，gremlin也是一种主流的图操作语言，属于Apache图生态TinkerPop的一部分，使用gremlin作为操作语言的图数据库是JanusGraph/Titian，国内的图数据库厂商，如Alibaba Graph Database、Huawei Graph Engine Service和Baidu HugeGraph等均使用gremlin作为操作语言。相比cypher，gremlin中的随机游走并不是独立的语法，而是由多个独立操作组成的。当然，由于gremlin的开源属性，不排除第三方数据库厂商将其进行封装，提供独立的随机游走API调用。本文仅介绍gremlin原生的随机游走操作方法。所述例子来源于开源书籍PRACTICAL GREMLIN:An Apache TinkerPop Tutorial。以全美各大城市机场航线网络构建一个属性图。节点的属性code表示机场代号；route表示2个机场间的一条航线（即边）；dist为route的一个属性，表示机场间距离。

指定起点随机游走

// Random walk with five hops
g.V().has('code','AUS').
      repeat(bothE('route').
         sample(1).by('dist').otherV()).
      times(5).
      path().by('code').by('dist')

个例子是获取5条从起始点城市AUS（Austin）出发通过5次飞行能够到达的城市组成的航程。其中times()对应cypher randomWalk API中的参数steps，即一次随机游走的步数；repeat()的功能类似于参数组graph, nodeQuery和relationshipQuery，用于指定游走的规则；sample()用于随机选择满足条件的边/节点。

该查询执行一次返回一条随机游走。下面展示执行一次和五次的输出。

// the results of running the query one time
[AUS,992,SFB,828,MDT,592,ORD,234,DTW,500,LGA]
// the results of running the query five times
[AUS,992,SFB,828,MDT,592,ORD,234,DTW,500,LGA]

[AUS,957,CVG,374,ATL,1890,SAN,2276,DCA,204,PIT]

[AUS,1209,PIT,1399,CUN,941,BJX,729,IAH,1384,BZN]

[AUS,748,MEX,1252,PHX,5255,LHR,2487,LXR,492,JED]

[AUS,722,STL,717,DCA,893,RSW,1103,HPN,563,CLT]

任意起点随机游走

// Random walk with five hops
g.V().hasLabel('airport').sample(1).
      repeat(bothE('route').
        sample(1).by('dist').otherV()).
      times(5).
      path().by('code').by('dist')

与上例通过has('code','AUS')指定code属性值AUS的节点为起点不同，本例通过hasLabel('airport')来选择标签为airport为节点，并通过sample()来随机选择符合条件的一个airport节点作为起点。执行五次的结果如下

// the results of running the query five times
[OMA,1144,LGA,584,CVG,750,BOS,6682,NRT,5951,VCE]

[CLE,244,ROC,263,JFK,8054,HKG,7952,BOS,7288,PVG]

[EMA,1126,AGP,969,PMO,708,VIE,5684,NRT,5152,DOH]

[SNN,387,LGW,1349,KBP,264,KHE,434,IST,2831,DEL]

[ARN,1814,LEI,1232,PRG,433,BRU,1384,SVO,3598,PEK]

同时返回多条随机游走

// Five random walks each of five hops
g.V().hasLabel('airport').
      repeat(local(bothE('route').
        sample(1).by('dist').otherV())).
      times(5).
      path().by('code').by('dist').limit(5)

这可能是接近实际使用的例子。规定了起点的标签，循环选择其中一个起点进行游走。使用limit()来限制终返回的游走次数。该操作执行一次的结果如下：

// the results of running the query one time
[ATL,1301,ASE,845,SFO,2580,MIA,596,ATL,546,PBI]
[ANC,2547,PHX,1999,BWI,368,BOS,3576,CGN,4745,MIA]
[AUS,922,CUN,931,SAT,248,DAL,1378,LGA,736,MKE]
[BNA,630,DFW,1430,SJC,2110,ATL,2180,SEA,4868,AMS]
[BOS,3838,MUC,4024,JFK,8054,HKG,858,YNZ,901,HRB]

小结

本文简单介绍了什么是随机游走，举例说明了自然界和人类社会中随机游走例子，分析了随机游走在基于图的机器学习上的使用。后分别用实例说明了如何用主流的图操作语言来实现随机游走。

分享好友

分享这个小栈给你的朋友们，一起进步吧。