图正成为机器学习的核心，可以通过了解社交网络的结构来预测潜在联系，检测欺诈，了解客户的汽车租赁服务行为或进行实时推荐。
在本文中，我们将介绍：
- 图学习算法
- 使用python来实现图
接下来，打开一个Jupyter Notebook并导入以下包：
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt
以下文章将使用networkx最新版本2.x。 networkx是一个Python包，用于创建，操作和研究复杂网络的结构，动态和功能。
我将尝试使用一种实用的方法并对大多数概念进行说明。我们将在本文中介绍图学习中的三个主要任务：
- 链接预测
- 节点标签预测
- 图嵌入
一.链接预测(Link predicton)
在链接预测中，给定图G，我们的目标是预测新边。例如，当图未被完全观察时，或者当新客户加入平台（例如，新的LinkedIn用户）时，预测未来关系或缺失边是很有用的。
新LinkedIn用户的链接预测只是给出它可能认识的人的建议。
在链路预测中，我们只是尝试在节点对之间建立相似性度量，并链接最相似的节点。现在的问题是识别和计算正确的相似性分数！
为了说明不同的相似性得分，让我们考虑以下图：
初始图
设N(i)是节点i的一组邻居。在上图中，节点i和j的邻居可以表示为：
节点j的邻居
节点i的邻居
节点i的邻居
1. 相似度分数
我们可以根据它们的邻居为这两个节点建立几个相似度分数。
-
公共邻居：S(i,j)=∣N(i)∩N(j)∣，即公共邻居的数量。在此示例中，分数将为2，因为它们仅共享2个公共邻居。
公共邻居
-
Jaccard系数：标准化的共同邻居版本。
Jaccard系数
交集是共同的邻居，并集是：
邻居的并集
因此，Jaccard系数由粉红色与黄色的比率计算出：
Jaccard系数
值是2/7。
-
Adamic-Adar指数：对于节点i和j的每个公共邻居，我们将1除以该节点的邻居总数。这个概念是，当预测两个节点之间的连接时，与少量节点之间共享的元素相比，具有非常大的邻域的公共元素不太重要。
Adamic-Adar指数
-
优先依附(Preferential attachment)： S(i,j)=∣N(i,j)∣∗∣N(j)∣
-
当社区信息可用时，我们也可以在社区信息中使用它们。
2. 性能指标(Performance metrics)
我们如何进行链接预测的评估？我们必须隐藏节点对的子集，并根据上面定义的规则预测它们的链接。这相当于监督学习中的train/test的划分。
然后，我们评估密集图的正确预测的比例，或者使用稀疏图的标准曲线下的面积(AUC)。
3. 实现
我们使用在前两篇文中提及到的Karate图，并使用python来进行实现。首先，打印有关图的信息：
# Load the graph
G_karate = nx.karate_club_graph()
# Find key-values for the graph
pos = nx.spring_layout(G_karate)
# plot the graph
nx.draw(G_karate, cmap=plt.get_cmap('rainbow'), with_labels=True, pos=pos)
m = G_karate.number_of_edges()
print("Number of nodes :", str(n))
print("Number of edges :", str(m))
print("Number of connected components :" str(nx.number_connected_components(G_karate)))
image.png
然后，绘制图:
nx.draw(G_karate)
image.png
现在，让我们删除一些连接，例如25％的节点：
edge_subset = random.sample(G_karate.edges(), int(0.25 * G_karate.number_of_edges()))
# Remove some edges
G_karate_train = G_karate.copy()
G_karate_train.remove_edges_from(edge_subset)
绘制部分观察到的图：
plt.figure(figsize=(12,8))
nx.draw(G_karate_train)
部分观察到的图
你可以打印我们删除的边数和剩余边数：
edge_subset_size = len(list(edge_subset))
print("Deleted : ", str(edge_subset_size))
print("Remaining : ", str((m - edge_subset_size)))
image.png
Jaccard Coefficient
我们可以先使用Jaccard系数进行预测：
prediction_jaccard = list(nx.jaccard_coefficient(G_karate_train))
score, label = zip(*[(s, (u, v) in edge_subset) for (u,v,s) in prediction_jaccard])
print(prediction_jaccard)
预测结果就像这样，第一个是节点，第二个是另一个节点，最后一个是Jaccard分数（或直接标签）：
image.png
我们可以使用ROC-AUC标准来比较不同模型的性能，因为我们既有标签又有概率。
Adamic-Adar
我们现在可以用Adamic-Adar指数重复这个：
prediction_adamic = list(nx.adamic_adar_index(G_karate_train))
score, label = zip(*[(s, (u, v) in edge_subset) for (u,v,s) in prediction_adamic])
print(prediction_adamic)
image.png
Preferential Attachment
对于preferential attachment得分:
prediction_pref = list(nx.preferential_attachment(G_karate_train))
score, label = zip(*[(s, (u,v) in edge_subset) for (u,v,s) in prediction_pref])
print(prediction_pref)
image.png
然后，我们选择最大化曲线下面积的模型，或者你选择的任何其他标准。到目前为止，我们已经涵盖了链接预测中最常用的相似度分数计算方法。
我们现在将详细介绍节点标记(node labeling)算法。
三. Node Labeling
给定一个未标记某些节点的图，我们希望对这些节点的标签进行预测。这在某种意义上是一种半监督的学习问题。
处理这些问题的一种常见方法是假设图上有一定的平滑度。平滑度假设指出通过数据上的高密度区域的路径连接的点可能具有相似的标签。这是标签传播算法背后的主要假设。
标签传播算法（Label Propagation Algorithm,LPA）是一种快速算法，仅使用网络结构作为指导来发现图中的社区，而无需任何预定义的目标函数或关于社区的先验信息。
Neo4J中展示的LPA
单个标签在密集连接的节点组中迅速占据主导地位，但是在穿过稀疏连接区域时会遇到问题。
半监督标签传播算法是如何工作？
首先，我们有一些数据：x1, …, xl, xl+1, …, xn ∈ Rp,，以及前l个点的标签：y1,…,yl ∈ 1…C.
我们定义初始标签矩阵Y ∈ R(n×C)，如果xi具有标签yi=j则Yij=1，否则为0。
该算法将生成预测矩阵F∈R(n×C)，我们将在下面详述。然后，我们通过查找最可能的标签来预测节点的标签：
image.png
预测矩阵F是什么？
预测矩阵是矩阵F*，其最小化平滑度和准确度。因此，我们的结果在平滑性和准确性之间进行权衡。
问题的描述非常复杂，所以我将不会详细介绍。但是，解决方案是：
image.png
如果您想进一步了解这个主题，请关注图函数的平滑度和流形正则化的概念。我不会介绍这部分的实现，但如果你有兴趣，斯坦福有一套很好的标签图可以下载：https://snap.stanford.edu/data/，Networkx直接实现标签传播：https://networkx.github.io/documentation/latest/reference/algorithms/generated/networkx.algorithms.community.label_propagation.label_propagation_communities.html
三. 图嵌入（Graph Embedding）
在处理NLP或计算机视觉问题时，我们习惯在深度神经网络中对图像或文本进行嵌入(embedding)。到目前为止，我们所看到的图的一个局限性是没有向量特征。但是，我们可以学习图的嵌入！图有不同几个级别的嵌入：
1. 节点嵌入(Node Embedding)
我们首先关注的是图组件的嵌入。有几种方法可以对节点或边进行嵌入。例如，DeepWalk使用短随机游走来学习图中边的表示。我们将讨论Node2Vec，这篇论文由2016年斯坦福大学的Aditya Grover和Jure Leskovec发表。
作者说：“node2vec是一个用于图表示学习的算法框架。给定任何图，它可以学习节点的连续特征表示，然后可以用于各种下游机器学习任务。“
该模型通过使用随机游走，优化邻域保持目标来学习节点的低维表示。
Node2Vec的代码可以在GitHub上找到：
https://github.com/eliorc/node2vec
要安装软件包，只需运行：
pip install node2vec
然后，在你的笔记本中，我们将对Karate图进行嵌入：
!pip install node2vec
from node2vec import Node2Vec
然后，预先计算概率并生成walks：
node2vec = Node2Vec(G_karate, dimensions=64, walk_length=30, num_walks=200, workers=4)
然后我们可以对节点进行嵌入：
model = node2vec.fit(window=10, min_count=1, batch_words=4)
要获取节点的向量，比如节点’2’，使用get_vector：
model.wv.get_vector('2')
image.png
它的长度为64，因为我们在上面将维度定义为64。使用嵌入我们能做些什么？首先想到的就是识别最相似的节点！
model.wv.most_similar('2')
image.png
它返回最相似节点的列表和相应的概率。
如果节点有标签，我们可以训练基于嵌入的算法并附加标签（节点标签，最相似的节点…）
2. 边嵌入(Edge Embedding)
边也可以进行嵌入，嵌入可以进一步用于分类。
from node2vec.edges import HadamardEmbedder
edges_embs = HadamardEmbedder(keyed_vectors=model.wv)
然后，通过指定2个链接节点的名称来检索向量：
edges_embs[('1','2')]
image.png
同样，我们可以检索最相似的边，可用于缺失边预测，例如：
edges_kv = edges_embs.as_keyed_vectors()
edges_kv.most_similar(str(('1','2')))
image.png
3.图嵌入(Graph Embedding)
还有一些方法可以直接对图或子图进行嵌入。这种方法已经在Graph2Vec论文中被提出，并且可用于将图或子图表示为向量，从而可以对图进行分类或相似性度量。我不会深入研究这种技术，但请随时查看这个项目的Github：
https://github.com/benedekrozemberczki/graph2vec
运行嵌入的命令如下：
python src/graph2vec.py --input-path data_folder/ --output-path output.csv
四. 进一步探索
我们现在已经覆盖了图的介绍，图的主要类型，不同的图算法，在Python中使用Networkx来实现它们，以及用于节点标记，链接预测和图嵌入的图学习技术。
毋庸置疑，这只是冰山一角。图论不断扩展，我认为列出一些资源以进一步学习是有用的：
- 图卷积网络(Graph Convolution Networks): https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780
- 图和流形上的几何深度学习(Geometric Deep Learning on Graphs and Manifolds):http://www.geometricdeeplearning.com/
- 一个可以提供帮助的MOOC:https://www.edx.org/course/advanced-algorithmics-and-graph-theory-with-python
如果你有任何其他资源，你认为有用，请不要犹豫，发表评论，我会将其添加到列表中！
我希望这一系列文章很有意思！如果你有任何问题或评论，请随时发表评论。
注意：这篇文章最初发表在我的个人博客上：https://maelfabien.github.io/
参考文献：
-
A Comprehensive Guide to Graph Algorithms in Neo4j, Mark Needham & Amy E. Hodler
-
Networkx documentation, https://networkx.github.io/documentation/stable/
-
Graph Theory courses at Telecom Paris
网友评论