NEO4J与图算法共舞：NEO4J内置图算法功能、计算思想与实例实操概览
Neo4j作为当前最为流行的图数据库之一，已经为众人所熟知。而基于Neo4j图数据库进行图算法相关的分析应用也逐步受到关注。
一般而言，我们可以使用Neo4j+图算法分析工具（networkx等开源工具）的方式进行配合来完成相关工作。
幸运的是，Neo4j图形数据科学（GDS）库中提供了许多图形算法，包括Path finding路径查找算法、Similarity节点相似度算法、Community detection社区发现算法、Centrality中心度计算算法、Node embeddings节点嵌入算法以及Topological link prediction拓扑链接预测算法等。
这也成为了第二种方式，值得我们探索一番。
本文围绕NEO4J中使用内置图谱算法的介绍与分析这一主题，对上述六个算法模块进行介绍和使用实践，供大家参考。
一、Path finding路径查找算法
路径查找算法在两个或多个节点之间找到路径，或评估路径的可用性和质量。
Neo4j中提供了包括Delta-Stepping Single-Source Shortest Path、Dijkstra Source-Target Shortest Path、Dijkstra Single-Source Shortest Path、A* Shortest Path、Yen’s Shortest Path、Breadth First Search、Depth First Search、Random Walk、Minimum Weight Spanning Tree和All Pairs Shortest Path等路径算法。
下面以A* Shortest Path为例进行介绍：
1、创建图谱
CREATE (a:Station {name: 'Kings Cross', latitude: 51.5308, longitude: -0.1238}),
(b:Station {name: 'Euston', latitude: 51.5282, longitude: -0.1337}),
(c:Station {name: 'Camden Town', latitude: 51.5392, longitude: -0.1426}),
(d:Station {name: 'Mornington Crescent', latitude: 51.5342, longitude: -0.1387}),
(e:Station {name: 'Kentish Town', latitude: 51.5507, longitude: -0.1402}),
(a)-[:CONNECTION {distance: 0.7}]->(b),
(b)-[:CONNECTION {distance: 1.3}]->(c),
(b)-[:CONNECTION {distance: 0.7}]->(d),
(d)-[:CONNECTION {distance: 0.6}]->(c),
(c)-[:CONNECTION {distance: 1.3}]->(e)
2、读取数据到模型
CALL gds.graph.project(
'myGraph',
'Station',
'CONNECTION',
{
nodeProperties: ['latitude', 'longitude'],
relationshipProperties: 'distance'
}
)
3、执行路径查询
MATCH (source:Station {name: 'Kings Cross'}), (target:Station {name: 'Kentish Town'})
CALL gds.shortestPath.astar.stream('myGraph', {
sourceNode: source,
targetNode: target,
latitudeProperty: 'latitude',
longitudeProperty: 'longitude',
relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
index,
gds.util.asNode(sourceNode).name AS sourceNodeName,
gds.util.asNode(targetNode).name AS targetNodeName,
totalCost,
[nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
costs,
nodes(path) as path
ORDER BY index
4、数据结果
二、Similarity节点相似度算法
相似性算法根据节点的邻域或其属性计算节点对的相似性，几个相似度指标可用于计算相似性分数。Neo4j GDS库包括Node Similarity、K-Nearest Neighbors等相似性算法。
1）Node Similarity
节点相似性算法根据它们连接的节点比较一组节点。如果两个节点共享许多相同的邻居，则被视为相似。节点相似性根据Jaccard度量（也称为Jaccard相似性分数）或重叠系数（也称为Szymkiewicz-Simpson系数）计算成对相似性。
给定两组A和B，使用以下公式计算Jaccard相似性：
重叠系数使用以下公式计算：
节点相似性算法比较了每个与此类节点有传出关系的节点。对于每个节点n，我们收集该节点的传出邻域N(n)，即所有节点m，使得从n到m有一个关系。对于每对n，m，该算法计算该对的相似性，该相似性等于N(n)和N(m)所选相似性度量的结果。
节点相似性具有时间复杂度O（n3）和空间复杂度O（n2）。我们在时间和空间O(n2)中计算和存储邻居集，然后在时间O(n3)中计算成对相似性分数。
2）K-Nearest Neighbors
而K-Nearest Neighbors算法计算图中所有节点对的距离值，并在每个节点与其k个最近邻居之间创建新的关系。距离是根据节点属性计算的，K-Nearest Neighbors算法比较每个节点的给定属性。这些属性最相似的k个节点是k个最近的邻居。
KNN算法中使用的相似性度量取决于配置节点属性的类型。KNN支持标量数字值和数字列表。当属性是标量数时，相似性计算公式为一除以1加上绝对差额：
其中：
Cosine相似性表示向量的点积除以其长度的乘积：
当指定多个属性时，两个邻居的相似性是单个属性相似性的平均值，即数字的简单平均值，每个属性都在[0, 1]范围内，给出的总分数也在[0, 1]范围内。
下面以node simlarity算法为例进行实验：
1、创建图谱
CREATE
(alice:Person {name: 'Alice'}),
(bob:Person {name: 'Bob'}),
(carol:Person {name: 'Carol'}),
(dave:Person {name: 'Dave'}),
(eve:Person {name: 'Eve'}),
(guitar:Instrument {name: 'Guitar'}),
(synth:Instrument {name: 'Synthesizer'}),
(bongos:Instrument {name: 'Bongos'}),
(trumpet:Instrument {name: 'Trumpet'}),
(alice)-[:LIKES]->(guitar),
(alice)-[:LIKES]->(synth),
(alice)-[:LIKES {strength: 0.5}]->(bongos),
(bob)-[:LIKES]->(guitar),
(bob)-[:LIKES]->(synth),
(carol)-[:LIKES]->(bongos),
(dave)-[:LIKES]->(guitar),
(dave)-[:LIKES]->(synth),
(dave)-[:LIKES]->(bongos);
2、读取数据到模型
CALL gds.graph.project(
'myGraph',
['Person', 'Instrument'],
{
LIKES: {
type: 'LIKES',
properties: {
strength: {
property: 'strength',
defaultValue: 1.0
}
}
}
}
);
3、计算节点相似度
节点相似性算法只会计算至少为1度的节点的相似性。
CALL gds.nodeSimilarity.stream('myGraph')
YIELD node1, node2, similarity
RETURN gds.util.asNode(node1).name AS Person1, gds.util.asNode(node2).name AS Person2, similarity
ORDER BY similarity DESCENDING, Person1, Person2
4、输出结果
Person1 Person2 similarity
"Alice" "Dave" 1.0
"Dave" "Alice" 1.0
"Alice" "Bob" 0.6666666666666666
"Bob" "Alice" 0.6666666666666666
"Bob" "Dave" 0.6666666666666666
"Dave" "Bob" 0.6666666666666666
"Alice" "Carol" 0.3333333333333333
"Carol" "Alice" 0.3333333333333333
"Carol" "Dave" 0.3333333333333333
"Dave" "Carol" 0.3333333333333333
三、Community detection社区发现算法
Neo4j中封装了包括Production-quality、Louvain、Label Propagation、Weakly Connected Components、Triangle Count、Local Clustering Coefficient、K-1 Coloring、Modularity Optimization、Strongly Connected Components、Speaker-Listener Label Propagation、Approximate Maximum k-cut、Conductance metric、K-Means Clustering以及Leiden等几种经典社区发现方法。
下面以Louvain算法为例进行介绍：
1、创建图谱
CREATE
(nAlice:User {name: 'Alice', seed: 42}),
(nBridget:User {name: 'Bridget', seed: 42}),
(nCharles:User {name: 'Charles', seed: 42}),
(nDoug:User {name: 'Doug'}),
(nMark:User {name: 'Mark'}),
(nMichael:User {name: 'Michael'}),
(nAlice)-[:LINK {weight: 1}]->(nBridget),
(nAlice)-[:LINK {weight: 1}]->(nCharles),
(nCharles)-[:LINK {weight: 1}]->(nBridget),
(nAlice)-[:LINK {weight: 5}]->(nDoug),
(nMark)-[:LINK {weight: 1}]->(nDoug),
(nMark)-[:LINK {weight: 1}]->(nMichael),
(nMichael)-[:LINK {weight: 1}]->(nMark);
2、读取数据到模型
CALL gds.graph.project(
'myGraph',
'User',
{
LINK: {
orientation: 'UNDIRECTED'
}
},
{
nodeProperties: 'seed',
relationshipProperties: 'weight'
}
)
3、发现社区
CALL gds.louvain.stream('myGraph')
YIELD nodeId, communityId, intermediateCommunityIds
RETURN gds.util.asNode(nodeId).name AS name, communityId, intermediateCommunityIds
ORDER BY name ASC
4、输出社区结果
name communityId intermediateCommunityIds
"Alice" 2 null
"Bridget" 2 null
"Charles" 2 null
"Doug" 5 null
"Mark" 5 null
"Michael" 5 null
四、Centrality中心度计算算法
Neo4j中封装了包括Page Rank、Article Rank、Eigenvector Centrality、Betweenness Centrality以及Degree Centrality等几种中心度计算的方法。
其中：
1）PageRank算法
该算法根据数字传入关系和相应源节点的重要性来衡量图中每个节点的重要性。
2）ArticleRank
该算法是Page Rank算法的变体，用于测量节点的传递影响。页面排名遵循以下假设：来自低度节点的关系比来自高度节点的关系具有更大的影响力。文章排名通过降低每次迭代中发送给邻居的分数来降低低度节点的影响。
3）Eigenvector Centrality
该算法是一种测量节点传递影响的算法。来自高分节点的关系对节点得分的贡献大于来自低分节点的连接。高特征向量分数意味着一个节点连接到许多本身得分很高的节点。
4）Betweenness Centrality算法
该算法计算图表中所有节点对之间的未加权最短路径。每个节点根据通过节点的最短路径数量获得一个分数。更频繁地位于其他节点之间最短路径上的节点将具有更高的中心性分数。
5）Degree Centrality算法
该算法测量来自节点的传入或传出（或两者兼而有之）关系的数量，具体取决于关系投影的方向，可以应用于加权或无加权图。在加权情况下，该算法计算节点相邻关系的所有正权重的总和，适用于图中的每个节点。
下面以pagerank算法为例进行介绍：
1、创建图谱
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 {weight: 0.2}]->(about),
(home)-[:LINKS {weight: 0.2}]->(links),
(home)-[:LINKS {weight: 0.6}]->(product),
(about)-[:LINKS {weight: 1.0}]->(home),
(product)-[:LINKS {weight: 1.0}]->(home),
(a)-[:LINKS {weight: 1.0}]->(home),
(b)-[:LINKS {weight: 1.0}]->(home),
(c)-[:LINKS {weight: 1.0}]->(home),
(d)-[:LINKS {weight: 1.0}]->(home),
(links)-[:LINKS {weight: 0.8}]->(home),
(links)-[:LINKS {weight: 0.05}]->(a),
(links)-[:LINKS {weight: 0.05}]->(b),
(links)-[:LINKS {weight: 0.05}]->(c),
(links)-[:LINKS {weight: 0.05}]->(d);
2、读取数据到模型
CALL gds.graph.project(
'myGraph',
'Page',
'LINKS',
{
relationshipProperties: 'weight'
}
)
3、计算节点重要性
CALL gds.pageRank.stream('myGraph')
YIELD nodeId, score
RETURN gds.util.asNode(nodeId).name AS name, score
ORDER BY score DESC, name ASC
4、节点中心度结果
name score
"Home" 3.215681999884452
"About" 1.0542700552146722
"Links" 1.0542700552146722
"Product" 1.0542700552146722
"Site A" 0.3278578964488539
"Site B" 0.3278578964488539
"Site C" 0.3278578964488539
"Site D" 0.3278578964488539
五、Node embeddings节点嵌入算法
Neo4j中封装了包括Fast Random Projection、GraphSAGE和Node2Vec三种经典图嵌入的方法。
其中：
1）Fast Random Projection算法
该算法为快速随机投影，简称FastRP，是随机投影算法家族中的节点嵌入算法，最初使用一种称为非常稀疏的随机投影的技术为所有节点分配随机向量。
2）GraphSAGE算法
该算法是一种用于计算节点嵌入的归纳算法。GraphSAGE正在使用节点特征信息在看不见的节点或图形上生成节点嵌入。该算法不是为每个节点训练单个嵌入，而是学习一个函数，该函数通过从节点的本地邻居中采样和聚合功能来生成嵌入。
3）Node2Vec算法
该算法是一种节点嵌入算法，它根据图中的随机行走计算节点的矢量表示。该社区通过随机散步进行采样。该算法使用一些随机邻域样本来训练单个隐藏层神经网络。神经网络经过训练，可以根据另一个节点的出现来预测一个节点在步行中发生的可能性。
1、创建图谱
CREATE (alice:Person {name: 'Alice'})
CREATE (bob:Person {name: 'Bob'})
CREATE (carol:Person {name: 'Carol'})
CREATE (dave:Person {name: 'Dave'})
CREATE (eve:Person {name: 'Eve'})
CREATE (guitar:Instrument {name: 'Guitar'})
CREATE (synth:Instrument {name: 'Synthesizer'})
CREATE (bongos:Instrument {name: 'Bongos'})
CREATE (trumpet:Instrument {name: 'Trumpet'})
CREATE (alice)-[:LIKES]->(guitar)
CREATE (alice)-[:LIKES]->(synth)
CREATE (alice)-[:LIKES]->(bongos)
CREATE (bob)-[:LIKES]->(guitar)
CREATE (bob)-[:LIKES]->(synth)
CREATE (carol)-[:LIKES]->(bongos)
CREATE (dave)-[:LIKES]->(guitar)
CREATE (dave)-[:LIKES]->(synth)
CREATE (dave)-[:LIKES]->(bongos);
2、读取数据到模型
CALL gds.graph.project('myGraph', ['Person', 'Instrument'], 'LIKES');
3、运行node2vec算法
CALL gds.beta.node2vec.stream('myGraph', {embeddingDimension: 2})
YIELD nodeId, embedding
RETURN nodeId, embedding
3、获取节点embedding
nodeId embedding
0 [-0.14295829832553864, 0.08884537220001221]
1 [0.016700705513358116, 0.2253911793231964]
2 [-0.06589698046445847, 0.042405471205711365]
3 [0.05862073227763176, 0.1193704605102539]
4 [0.10888434946537018, -0.18204474449157715]
5 [0.16728264093399048, 0.14098615944385529]
6 [-0.007779224775731564, 0.02114257402718067]
7 [-0.213893860578537, 0.06195802614092827]
8 [0.2479933649301529, -0.137322798371315]
六、Topological link prediction拓扑链接预测算法
Topological link prediction拓扑链接预测算法仅使用图的拓扑来预测节点之间的关系，包括Adamic Adar、Common Neighbors、Preferential Attachment、Resource Allocation、Same Community以及Total Neighbors等算法。
其中：
1）Adamic Adar算法
Lada Adamic和Eytan Adar于2003年引入了Adamic Adar算法，用于预测社交网络中的链接。它使用以下公式计算：
其中N(u)是毗邻u的节点集合。
0的值表示两个节点没有关闭，而较高的值表示节点更接近。
2）Common Neighbors算法
该算法认为，两个有共同朋友的陌生人比那些没有共同朋友的陌生人更有可能被介绍。它使用以下公式计算：
其中N(x)是与节点x相邻的节点集，N(y)是与节点y相邻的节点集。
0的值表示两个节点没有关闭，而较高的值表示节点更接近。
3）Preferential Attachment算法
该算法是一种测量方法，用于根据节点的共享邻居来计算节点的接近度。优先附件意味着节点连接越多，接收新链接的可能性就越大。Albert-László Barabási和Réka Albert通过他们在无尺度网络方面的工作推广了该算法。它使用以下公式计算：
4）Resource Allocation算法
该算法是一种用于根据共享邻居计算节点接近度的度量。由Tao Zhou、Linyuan Lü和Yi-Cheng Zhang于2009年引入，作为预测各种网络链接研究的一部分。它使用以下公式计算：
其中N(u)是毗邻u的节点集合。0的值表示两个节点没有关闭，而较高的值表示节点更接近。
5）Same Community算法
该算法是确定两个节点是否属于同一社区的一种方式。这些社区可以通过使用社区检测之一进行计算。如果两个节点属于同一个社区，那么如果还没有的话，它们之间将来更有可能存在关系。值为0表示两个节点不在同一社区中。值为1表示两个节点位于同一个社区中。
6）Total Neighbors算法
该算法根据节点的唯一邻居数量计算节点的接近度。它基于这样一种想法，即节点连接越多，接收新链接的可能性就越大。
该算法使用以下公式计算：
其中N(x)是与x相邻的节点集，N(y)是与y相邻的节点集。
0的值表示两个节点没有关闭，而较高的值表示节点更接近。
下面以Adamic Adar算法为例进行介绍。
1、创建图谱
CREATE
(zhen:Person {name: 'Zhen'}),
(praveena:Person {name: 'Praveena'}),
(michael:Person {name: 'Michael'}),
(arya:Person {name: 'Arya'}),
(karin:Person {name: 'Karin'}),
(zhen)-[:FRIENDS]->(arya),
(zhen)-[:FRIENDS]->(praveena),
(praveena)-[:WORKS_WITH]->(karin),
(praveena)-[:FRIENDS]->(michael),
(michael)-[:WORKS_WITH]->(karin),
(arya)-[:FRIENDS]->(karin)
2、执行算法与输出结果
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN gds.alpha.linkprediction.adamicAdar(p1, p2) AS score
结果：score 0.9102392266268373
MATCH (p1:Person {name: 'Michael'})
MATCH (p2:Person {name: 'Karin'})
RETURN gds.alpha.linkprediction.adamicAdar(p1, p2, {relationshipQuery: 'FRIENDS'}) AS score
结果：score 0.0
总结
本文围绕NEO4J中使用内置图谱算法的介绍与分析这一主题进行了介绍，
其中Similarity节点相似度算法、Node embeddings节点嵌入算法以及Topological link prediction拓扑链接预测算法这三种算法十分有趣，算法细节值得进一步看看。
更细节的，可进一步阅读参考文献。
参考文献
1、https://neo4j.com/docs/graph-data-science/current/algorithms/
关于我们
老刘，刘焕勇，NLP开源爱好者与践行者，主页：https://liuhuanyong.github.io。
就职于360人工智能研究院、曾就职于中国科学院软件研究所。
老刘说NLP，将定期发布语言资源、工程实践、技术总结等内容，欢迎关注。
对于想加入更优质的知识图谱、事件图谱实践、相关分享的，可关注公众号，在后台菜单栏中点击会员社区->会员入群加入。