图论与图学习(二):图算法

2019 年 8 月 3 日 机器之心
图论与图学习(二):图算法

选自towardsdatascience

作者:Maël Fabien
机器之心编译
参与:熊猫

图(graph)近来正逐渐变成机器学习的一大核心领域,比如你可以通过预测潜在的连接来理解社交网络的结构、检测欺诈、理解汽车租赁服务的消费者行为或进行实时推荐。近日,数据科学家 Maël Fabien 在其博客上发布了涉及图论、图算法和图学习的系列文章《图论与图学习》。

本文是其中第二篇,介绍了图算法。更多文章和对应代码可访问: https://github.com/maelfabien/Machine_Learning_Tutorials


本文涵盖以下主题:


  • 主要的图算法

  • 示意图和用例

  • Python 示例


首先进行一些准备工作,打开 Jupyter Notebook,导入以下软件包:

import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt


后文会使用 networkx 最新的 2.0 版本。networkx 是一个用于复杂网络的结构、动态和功能的创建、操作和研究的 Python 软件包。


我会尽量以实用为目标,努力阐释每个概念。


前一篇文章介绍了图的主要种类以及描述一个图的基本特性。现在我们更加详细地介绍图分析/算法以及分析图的不同方式。


为了理解上下文,这里给出一些图算法的用例:


  • 实时欺诈检测

  • 实时推荐

  • 精简法规遵从性

  • 复杂网络的管理和监控

  • 身份和访问管理

  • 社交应用/功能


目前大多数框架(比如 Python 的 networkx 或 Neo4J)支持的图算法类别主要有三个:


  • Pathfinding(寻路):根据可用性和质量等条件确定最优路径。我们也将搜索算法包含在这一类别中。这可用于确定最快路由或流量路由。

  • Centrality(中心性):确定网络中节点的重要性。这可用于识别社交网络中有影响力的人或识别网络中潜在的攻击目标。

  • Community detection(社群检测):评估群体聚类的方式。这可用于划分客户或检测欺诈等。


我们将在第三篇文章中介绍图中的机器学习和图学习。

networkx 中的所有算法都可在这里找到: https://networkx.github.io/documentation/stable/reference/algorithms/index.html


我们只会介绍 networkx 中实现的最常见的基本算法。


一 寻路和图搜索算法


  • 寻路算法是通过最小化跳(hop)的数量来寻找两个节点之间的最短路径。

  • 搜索算法不是给出最短路径,而是根据图的相邻情况或深度来探索图。这可用于信息检索。


1. 搜索算法


图搜索算法主要有两种:


  • 宽度优先搜索(BFS):首先探索每个节点的相邻节点,然后探索相邻节点的相邻节点……

  • 深度优先搜索(DFS):会尝试尽可能地深入一条路径,如有可能便访问新的相邻节点。


搜索算法


2. 寻路算法


a. 最短路径


最短路径计算的是一对节点之间的最短的加权(如果图有加权的话)路径。


这可用于确定最优的驾驶方向或社交网络上两个人之间的分离程度。


计算图中的最短路径的方法有很多,包括 Dijkstra 算法,这是 networkx 中的默认算法。


根据维基百科,该算法的伪代码如下:


  • 将图中所有节点标记为未访问。创建一个所有未访问节点的集合,称为未访问集。

  • 为每个节点分配一个暂定的距离值:将我们的初始节点的该值设置为零,将其它所有节点的该值设置为无穷。将初始起始节点设置为当前节点。

  • 对于当前节点,考察其所有未被访问过的相邻节点并计算通过当前节点的暂定距离。比较新计算出的暂定距离与当前分配的值,配之以其中更小的值。举个例子,如果当前节点 A 标记的距离为 6,将其与相邻节点 B 连接的边的长度为 2,则通过 A 到达 B 的距离为 6+2=8。如果 B 之前被标记的距离大于 8,则将其改为 8。否则,保持其当前的值。

  • 当我们考察完当前节点的所有未访问节点时,将当前节点标记为已访问,并将其移出未访问集。已访问节点不会再次进行检查。

  • 如果目标节点已被标记为已访问(当规划两个特定节点之间的路由时)或未访问集中节点之间的最小暂定距离为无穷时(当规划一次完整的遍历时;当初始节点与剩余的未访问节点之间没有连接时才会出现这种情况),那么就停止操作。算法结束。

  • 否则,选择标记有最小暂定距离的未访问节点,将其设置为新的「当前节点」,然后回到步骤 3。


更多有关最短路径问题的介绍请参阅:https://en.wikipedia.org/wiki/Shortest_path_problem

维基百科上 Dijkstra 算法示意图


该算法的 Python 实现简单直接:

# Returns shortest path between each node
nx.shortest_path(G_karate)

这会返回图中每个节点之间的最小路径的列表:

{0: {0: [0],
    1: [0, 1],
    2: [0, 2],
    ...


b. 单源最短路径


单源最短路径(Single Source Shortest Path/SSSP)是找到给定节点与图中其它所有节点之间的最短路径。


这常用于 IP 网络的路由协议。


c. 所有配对最短路径


所有配对最短路径(All Pairs Shortest Path / APSP)算法是找到所有节点对之间的最短路径。


尽管能够提供相近的结果,但这比为每个节点对调用单源最短路径算法更快。该算法通常可用于确定交通网格的不同分区的流量负载。

# Returns shortest path length between each node
list(nx.all_pairs_shortest_path_length(G_karate))


这会返回:

[(0,
    {00,
    11,
    21,
    31,
    41,
    ...

d. 最小权重生成树


最小权重生成树(minimum spanning tree)是图(一个树)的一个子图,其用权重和最小的边连接了图中的所有节点。


最小生成树应该用于无向图。

from networkx.algorithms import tree
mst = tree.minimum_spanning_edges(G_karate, algorithm='prim', data=False)
edgelist = list(mst)
sorted(edgelist)


这会返回:

[(01),
(02),
(03),
(04),
(05),
(06),
...


二 社群检测
社群检测是根据给定的质量指标将节点划分为多个分组。


这通常可用于识别社交社群、客户行为或网页主题。


社区是指一组相连节点的集合。但是,目前关于社群还没有广泛公认的定义,只是社群内的节点应该要密集地相连。


社群


Girvan Newman 算法是一个用于发现社群的常用算法。其通过逐步移除网络内的边来定义社区。我们将居间性称为「边居间性(edge betweenness)」。这是一个正比于穿过该边的节点对之间最短路径的数量的值。


该算法的步骤如下:


  • 计算网络中所有已有边的居间性。

  • 移除居间性最高的边。

  • 移除该边后,重新计算所有边的居间性。

  • 重复步骤 2 和 3,直到不再剩余边。


你可以通过 Python 使用以下代码实现它:

from networkx.algorithms import communityk = 1
comp = community.girvan_newman(G_karate)for communities in itertools.islice(comp, k):
    print(tuple(sorted(c) for c in communities))

这会得到一个属于每个社群的节点的列表(k=1 的意思是我们期望得到 2 个社群):

([0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21][2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])


如上给出的那样,这个方法实在没法扩展。由于这个原因,Louvain 等方法已被开发出来。但是,如果要运行大规模的图,这些方法需要很长的时间。


3. Louvain 模块性


在定义 Louvain 方法之前,需要介绍一下模块性(modularity)的概念。模块性是一个度量,衡量的是分组被划分为聚类的程度:


模块性


Louvain 方法的伪代码如下:


  • 首先为每个节点分配一个社群

  • 交替执行接下来的两个步骤,直到收敛

  • 创建一个带有相邻节点的新社群,以最大化模块性

  • 创建一个新的加权的图。之前步骤的社群变成图的节点。


这个现在可能看起来有些让人迷惑。事实上,我们现在唯一做的事情是将最近的节点划分为分组,以便我们优化模块性指标。


Louvain 方法


注意,Louvain 方法没有理论上的保证,但实践效果很好。Louvain 方法是 networkx 的一个子项目,参阅:https://python-louvain.readthedocs.io/en/latest/


首先,安装软件包:

pip install python-louvain


然后,计算最佳的划分方式(基于 Louvain 方法):

import community
partition = community.best_partition(G_karate)pos = nx.spring_layout(G_karate)
plt.figure(figsize=(88))
plt.axis('off')
nx.draw_networkx_nodes(G_karate, pos, node_size=600, cmap=plt.cm.RdYlBu, node_color=list(partition.values()))
nx.draw_networkx_edges(G_karate, pos, alpha=0.3)
plt.show(G_karate)


使用 Louvain 对空手道图执行的最佳划分


4. 强互连的组分


强互连的组分(Strongly Connected Components /SCC)算法能找到有向图中的互连节点的分组。注意,在同一个分组中,每个节点都必须从任意其它节点从两个方向都到达。


这通常用在图分析过程的早期阶段,能让我们了解图构建的方式。举个例子,这能让我们探索财务报表数据,了解谁拥有什么公司的股份。


5. 弱互连的组分(并查集)


弱互连的组分(Weakly Connected Components),也称为并查集(Union Find)算法,能找到有向图中的互连节点的集合,在同一个集合中,每个节点都可从任意其它节点到达。


这只需要节点对之间在一个方向上存在一条路径即可,而 SCC 则需要两个方向都存在路径。和 SCC 一样,并查集通常用在分析的早期阶段,以理解图的结构。


并查集是一个预处理步骤,为了理解图的结构,在任何算法之前都是必需的。


我们可以使用下面的方法测试相连的有向图:

nx.is_weakly_connected(G)
nx.is_strongly_connected(G)


或使用下面的方法测试无向图:

nx.is_connected(G_karate)

这会返回一个布尔值。


一定要看看 networkx 文档中有关连接性实现的问题:https://networkx.github.io/documentation/stable/reference/algorithms/component.html


6. 分层聚类


在分层聚类(hierarchical clustering)中,我们构建聚类的层次结构。我们用树状图的形式表示聚类。


树状图


其思想是以不同的规模分析社群结构。我们通常自下而上构建树状图。我们从每个节点一个聚类开始,然后合并两个「最近」的节点。


但我们如何衡量聚类是否相近呢?我们使用相似度距离。令 d(i,j) 为 i 和 j 之间的最短路径的长度。


相似度距离


要得到最大连接,在每个步骤,被最短距离分开的两个聚类被组合到一起。相似度距离可用以下示意图阐释:


连接方式


回到我们的空手道示例。在应用分层聚类之前,我们需要定义每个节点之间的距离矩阵。

pcc_longueurs=list(nx.all_pairs_shortest_path_length(G_karate))
distances=np.zeros((n,n))# distances[i, j] is the length of the shortest path between i and j
for i in range(n):
    for j in range(n):
        distances[i, j] = pcc_longueurs[i][1][j]

现在,我们将使用 sklearn 的 AgglomerativeClustering 函数来确定分层聚类。

from sklearn.cluster import AgglomerativeClusteringclustering = AgglomerativeClustering(n_clusters=2,linkage='average',affinity='precomputed').fit_predict(distances)


最后,根据聚类结果,用不同颜色绘出所得到的图:

nx.draw(G_karate,  node_color = clustering)

分层聚类


7. 聚类系数


聚类系数衡量的是两个节点倾向于聚类到一起的程度。


局部聚类系数是以节点 i 为中心的三角形的数量与以节点 i 为中心的三节点的数量的比。某种程度而言,这衡量的是节点 i 与其相邻节点接近完备图(complete graph)的程度。


聚类系数


我通过以下图演示了聚类系数的计算:

聚类系数


全局聚类系数衡量的是图中三角形(局部聚类)的密度:


全局聚类系数


上面的图的全局聚类系数为:


对于 Erdos-Rényi 随机图,E[Clustering Coefficient]=E[Ci]=p,其中 p 是前一篇文章中定义的概率。


对于 Baràbasi-Albert 随机图,全局聚类系数根据节点的数量遵循幂律。度为 k 的节点的平均聚类系数正比于 k 的倒数:


度较低的节点连接的是它们社群中的其它节点。度较高的节点连接的是其它社群的节点。


对于一个给定的图,在 networkx 中,聚类系数很容易算出。首先,我们来计算局部聚类系数:

List of local clustering coefficients
list(nx.clustering(G_barabasi).values())

这会得到类似下面的结果:

0.13636363636363635,
0.2,
0.07602339181286549,
0.04843304843304843,
0.09,
0.055384615384615386,
0.07017543859649122,
...

然后平均这些结果,得到该图的全局聚类稀疏:

Global clustering coefficient
np.mean(list(nx.clustering(G_barabasi).values()))

这会得到:

0.0965577637155059


三 中心度算法


中心度(Centrality)衡量的是节点的重要程度。这并非一个明晰的定义,但如果我们想要确定重要的网页、交通网络中的瓶颈……,那这就会很有用。



游走(walk)是可以多次经过同一个节点的路径。根据所考虑的游走类型和统计它们的方式,中心度度量也会各有不同。


1. PageRank 算法


PageRank 是根据所连接的相邻节点,然后再根据它们各自的相邻节点估计当前节点的重要性。


尽管是谷歌让这种算法流行起来的,但这种方法能够用于检测任何网络中的高影响力节点。比如可用在社交网络上进行推荐。


PageRank 要么是通过在相邻节点上迭代地分配节点的秩(原本是基于度)来计算,要么是通过随机遍历图并统计每次游走期间到达每个节点的频率来计算。


Neo4J 对 PageRank 算法的总结


PageRank 通常是在有向图上计算,但也可通过将有向图中的每条边转换成两条边而在无向图上执行。


举个例子,空手道图的 PageRank 可以这样获得:

nx.pagerank(G_karate, alpha=0.9)

其中 alpha 是阻尼参数(默认为 0.85)。这应该能返回一个排名列表:

{0: 0.09923208031303203,
 1: 0.0543403155825792,
 2: 0.05919704684187155,
 3: 0.036612460562853694,
...

2. 度中心度


度中心度(Degree Centrality)统计的是终止于节点 i 的长度为 1 的游走的数量。


这能够衡量传入和传出关系。这能通过 C(Xi)=di 给出。度中心度可用于识别社交网络中最有影响力的人。

c_degree = nx.degree_centrality(G_karate)
c_degree = list(c_degree.values())


3. 特征向量中心度


特征向量中心度(Eigenvector Centrality)是终止于节点 i 的长度为无穷的游走的数量。


这能让有很好连接相邻节点的节点有更高的重要度。

特征向量中心度

c_eigenvector = nx.eigenvector_centrality(G_karate)
c_eigenvector = list(c_eigenvector.values())

4. 接近度中心度


接近度中心度(Closeness Centrality)检测的是可以在图中有效传播信息的节点。


这可用于识别假新闻账户或恐怖分子,以便隔离能向图中其它部分传播信息的个体。


接近度中心度反比于到其它节点的最短路径长度的总和。

c_closeness = nx.closeness_centrality(G_karate)
c_closeness = list(c_closeness.values())


5. 居间性中心度


居间性中心度(Betweenness Centrality)检测的是节点在图中的信息流上所具有的影响量。


这通常可用于发现用作从图的一部分到另一部分的桥的节点,比如用在电信网络的数据包传递处理器或假新闻传播分析中。


其中:

  • σ_jk 是 j 和 k 之间的最短路径的数量

  • σ_jk(i) 是 j 和 k 之间的经过 i 的最短路径的数量


居间性中心度衡量的是一个节点用作两个节点之间的桥的次数,比如:

中心度度量

c_betweenness = nx.betweenness_centrality(G_karate)
c_betweenness = list(c_betweenness.values())


Python 中实现依赖于 networkx 的内置函数:

# Plot the centrality of the nodes
plt.figure(figsize=(1812))# Degree Centrality
f, axarr = plt.subplots(22, num=1)
plt.sca(axarr[0,0])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_degree, node_size=300pos=pos, with_labels=True)
axarr[0,0].set_title('Degree Centrality', size=16)# Eigenvalue Centrality
plt.sca(axarr[0,1])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_eigenvector, node_size=300pos=pos, with_labels=True)
axarr[0,1].set_title('Eigenvalue Centrality', size=16)# Proximity Centrality
plt.sca(axarr[1,0])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_closeness, node_size=300pos=pos, with_labels=True)
axarr[1,0].set_title('Proximity Centrality', size=16)# Betweenness Centrality
plt.sca(axarr[1,1])
nx.draw(G_karate, cmap = plt.get_cmap('inferno'), node_color = c_betweenness, node_size=300pos=pos, with_labels=True)
axarr[1,1].set_title('Betweenness Centrality', size=16)

不同的中心度度量


可以观察到,不同的中心度度量关注的节点也不同。比如,居间性中心度得到的结果与其它方法的结果非常不同,因为它们衡量的不是同一个指标。


四 总结


现在我们已经介绍了图的基础知识、图的主要类型、不同的图算法和它们使用 networkx 的 Python 实现。


下一篇文章我们将介绍图学习,这能提供预测图中节点和边的方法,从而处理缺失值或预测新的关系。


扩展阅读:


  • Neo4j 的图算法全面指南,Mark Needham & Amy E. Hodler:https://go.neo4j.com/rs/710-RRC-335/images/Comprehensive-Guide-to-Graph-Algorithms-in-Neo4j-ebook-EN-US.pdf

  • Networkx 文档:https://networkx.github.io/documentation/stable/


原文链接:https://towardsdatascience.com/graph-algorithms-part-2-dce0b2734a1d



文为机器之心编译,转载请联系本公众号获得授权

✄------------------------------------------------

加入机器之心(全职记者 / 实习生):hr@jiqizhixin.com

投稿或寻求报道:content@jiqizhixin.com

广告 & 商务合作:bd@jiqizhixin.com

登录查看更多
4

相关内容

【导读】Graph Neural Network(GNN)由于具有分析图结构数据的能力而受到了广泛的关注。本文对Graph Neural Network进行了简要介绍。它涵盖了一些图论,以便于理解图和分析图时遇到的问题。然后介绍了不同形式的Graph神经网络及其原理。它还涵盖了GNN可以做什么以及GNN的一些应用。

图论

首先,我们需要知道什么是图。图是一种由两个部分组成的数据结构:顶点和edge。它用作分析目标和实体之间成对关系的数学结构。通常,将图定义为G =(V,E),其中V是一组节点,E是它们之间的边。

图通常由邻接矩阵A表示。如果图具有N个节点,则A的维数为(N x N)。人们有时会提供另一个特征矩阵来描述图中的节点。如果每个节点都有F个特征,则特征矩阵X的维数为(N x F)。

为什么图难以分析?

首先,在欧几里得空间中不存在图,这意味着它无法用我们熟悉的任何坐标系表示。与其他类型的数据(例如波,图像或时间序列信号)相比,这使得图数据的解释更加困难(“文本”也可以视为时间序列),可以轻松地将其映射为2-D或3-D欧几里德空间。

其次,图没有固定的形式。为什么?看下面的例子。图(A)和图(B)具有完全不同的结构和外观。但是,当我们将其转换为邻接矩阵表示形式时,两个图具有相同的邻接矩阵(如果不考虑边的权重)。那么我们应该考虑这两个图是相同还是不同?

最后,一般来说,图很难直观地显示出来以供人类解释。我不是在谈论像上面的例子这样的小图。我说的是涉及数百或数千个节点的巨型图。它的维数很高,节点密集地分组在一起,甚至使人难以理解图。因此,为该任务训练机器是具有挑战性的。以下示例显示了对集成电路中逻辑门进行建模的图。

Example of a giant graph: circuit netlist. Figure from J. Baehr et. al. “Machine Learning and Structural Characteristics of Reverse Engineering”

为什么要使用图?

人们选择使用图的原因可以归纳为以下几点:

  1. 图提供了一种更好的方式来处理诸如关系和交互之类的抽象概念。它们还提供了直观的视觉方式来思考这些概念。图也构成了在社会环境中分析关系的自然基础。
  2. 图可以通过将问题简化为更简单的表示形式来解决更复杂的问题,或者从不同的角度将问题转换为表示形式。
  3. 图论和概念用于研究和建模社交网络,欺诈模式,功耗模式,病毒性以及在社交媒体中的影响力。社交网络分析(SNA)可能是图论在数据科学中最著名的应用。

传统图分析方法

传统方法主要基于算法,例如:

  1. 搜索算法,例如BFS,DFS
  2. 最短路径算法,例如Dijkstra算法,最近邻居
  3. 生成树算法,例如Prim算法
  4. 聚类方法,例如高度连接的组件,k均值 这种算法的局限性在于,在应用该算法之前,我们需要以一定的置信度获得图的先验知识。换句话说,它对我们研究图本身没有任何意义。最重要的是,没有办法执行图级别分类。

图神经网络

所谓的图神经网络是一种可以直接应用于图的神经网络。它为节点级别,边缘级别和图级别的预测任务提供了一种方便的方法。

文献中主要有三种类型的图神经网络:

  1. 递归图神经网络
  2. 空间卷积网络
  3. 谱卷积网络

GNN的直觉是,节点自然是由其邻居和连接定义的。为了理解这一点,我们可以简单地想象一下,如果删除节点周围的邻居和连接,则该节点将丢失其所有信息。因此,节点的邻居和与邻居的连接定义了节点的概念。

考虑到这一点,我们然后给每个节点一个状态(x)来表示其概念。我们可以使用节点状态(x)产生输出(o),即有关概念的决策。节点的最终状态(x_n)通常称为“节点嵌入”。所有GNN的任务是通过查看其相邻节点上的信息来确定每个节点的“节点嵌入”。 我们将从图神经网络,循环图神经网络或RecGNN的经典版本开始。

递归图神经网络

正如原始GNN论文中介绍的那样,RecGNN是基于Banach不动点定理的假设而构建的。Banach不动点定理指出:(X,d)是一个完整的度量空间,而(T:X→X)是一个压缩映射。然后,T具有唯一的不动点(x ∗),对于任何x∈X,n→∞的序列T_n(x)收敛到(x ∗)。这意味着,如果我申请的映射T上X为ķ倍,X ^ K在几乎等于x ^(K-1),即:

RecGNN定义了一个参数化函数f_w:

其中L_N,l_co,x_ne,l_ne 表示当前节点的特征[n],节点的边缘[n],相邻节点的状态,与相邻节点的功能。(在原始论文中,作者将节点特征称为节点标签。这可能会造成一些混乱。)

An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model” 最终,在经过k次迭代之后,最终的节点状态将用于生成输出,以决定每个节点。输出函数定义为:

空间卷积网络

空间卷积网络的直觉类似于著名的CNN,后者主导着图像分类和分割任务的文献。要了解图像上的CNN,您可以查看这篇文章,其中详细说明了CNN。

简而言之,在图像上进行卷积的想法是对中心像素周围的相邻像素求和,该像素由参数化大小和可学习权重的滤波器指定。空间卷积网络通过将相邻节点的特征聚合到中心节点中采用了相同的思想。

Left: Convolution on a regular graph such as an image. Right: Convolution on the arbitrary graph structure. Figure from “A Comprehensive Survey on Graph Neural Networks”

谱卷积网络

与其他类型的GNN相比,这种类型的图卷积网络具有非常强大的数学基础。谱卷积网络建立在图信号处理理论的基础上。并通过简化和逼近图卷积。 通过Chebyshev多项式逼近 (Hammond et al。2011),图卷积可以简化为以下形式:

进一步简化后,GCN论文提出了一种2层神经网络结构,可以用以下等式描述:

其中A_head是原始图邻接矩阵A的预处理拉普拉斯算子。(有关数学的详细信息,请参见GCN论文。将需要大量的精力来进行充分说明。)

如果您有一些机器学习经验,则此公式看起来非常熟悉。这不过是常用的两个完全连接的层结构。但是在这种情况下,它确实可以用作图卷积。我将在下面说明为什么它可以执行图卷积。

Example of a graph with a feature assigned to each node. Figured by author

让我们考虑一下,我们有一个包含4个节点的简单图。如上图所示,为这些节点中的每个节点分配了一个特征矩阵。图邻接矩阵和特征矩阵很容易得出,如下所示:

Example of the adjacency matrix and feature matrix. Figure by author

注意,邻接矩阵的对角线故意更改为“ 1”,以为每个节点添加一个自环。当我们执行特征聚合时,这将包括每个节点本身的特征。 然后,我们执行A x X(为简单起见,我们先忽略A的拉普拉斯算子和权重矩阵W。)

Example of graph convolution by matrix multiplication. Figure by author

矩阵乘法的结果显示在最右边的矩阵中。让我们以第一个节点的结果功能为例。不难发现结果是[节点1]的所有特征之和,包括[节点1]本身的特征,并且[节点4]中的特征不包括在内,因为它不是[节点1]的邻居。。在数学上,仅当存在边时,图的邻接矩阵才具有值“ 1”,否则具有“ 0”。这使得矩阵乘法成为连接到参考节点的节点的特征之和。 因此,频谱卷积网络和空间卷积网络尽管是在不同的基础上开始的,但是它们共享相同的传播规则。 当前可用的所有卷积图神经网络共享相同的格式。他们都尝试学习通过该消息传递过程传递节点信息并更新节点状态的功能。 任何图神经网络可被表达为与消息传递神经网络(J. Gilmer et al. , 2017)的消息传递功能,节点更新功能和读出功能。

GNN可以做什么?

GNN解决的问题可以大致分为三类:

  1. 节点分类
  2. 链接预测
  3. 图分类 在节点分类中,任务是预测图中每个节点的节点嵌入。通常以半监督的方式训练此类问题,其中仅对部分图进行标记。节点分类的典型应用包括引文网络,Reddit帖子,Youtube视频和Facebook朋友关系。 在链接预测中,任务是了解图中实体之间的关系,并预测两个实体之间是否存在连接。例如,推荐系统可被视为链接预测问题,其中模型被赋予一组用户对不同产品的评论,任务是预测用户的偏好并调整推荐系统以根据用户推送更多相关感兴趣的产品。 在图分类中,任务是将整个图分类为不同的类别。它类似于图像分类,但是目标变为图域。有许多工业问题可以应用图分类,例如在化学,生物医学,物理学中,模型被赋予分子结构并被要求将目标分类为有意义的类别。它加快了对原子,分子或任何其他结构化数据类型的分析。

一些实际的应用

在了解了GNN可以执行哪种类型的分析之后,您一定想知道我可以对图进行哪些实际应用。好了,本节将为您提供有关GNN实际应用的更多见解。

自然语言处理中的GNN

GNN被广泛使用在自然语言处理(NLP)中。实际上,这也是GNN最初开始的地方。如果您中的某些人具有NLP经验,则必须考虑到文本应该是一种序列或时间数据,则可以由RNN或LTSM最好地描述。然而,GNN则从完全不同的角度解决了这个问题。GNN利用单词或文档的内部关系来预测类别。例如,引文网络尝试根据论文引文关系和其他论文中引用的词来预测网络中每篇论文的标签。它也可以通过查看句子的不同部分而不是像RNN或LTSM中那样的纯粹序列来构建语法模型。

计算机视觉中的GNN

许多基于CNN的方法已经在图像中的目标检测中达到了最新的性能,但是我们还不知道目标之间的关系。GNN在CV中的一种成功应用是使用图来建模基于CNN的检测器检测到的物体之间的关系。从图像中检测到目标后,将它们输入到GNN推理中以进行关系预测。GNN推断的结果是生成的图,该图对不同目标之间的关系进行建模。

Scene Graph Generation. Figure from D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017

CV中另一个有趣的应用是根据图描述生成图像。这可以解释为几乎与上述应用相反。图像生成的传统方式是使用GAN或自动编码器生成文本到图像。从图到图像的生成不是使用文本来描述图像,而是提供了有关图像语义结构的更多信息。

Image generated from scene graphs. Figure from J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018 我想分享的最有趣的应用是零样本学习(ZSL)。您可以找到这篇文章,以全面了解ZSL。总之,ZSL是想学给定的一类分类NO(目标类别的)训练样本。这是非常具有挑战性的,因为如果没有给出训练样本,我们需要让模型在逻辑上“思考”以识别目标。例如,如果给了我们三张图像(如下图所示),并告诉我们在其中找到“ okapi”。我们以前可能没有看过“okapi”。但是,如果我们还得到信息,“okapi”是一种有四只腿,斑马纹皮肤的鹿面动物,那么我们就不难确定哪个是“okapii”。典型的方法是通过将检测到的特征转换为文本来模拟这种“思考过程”。但是,文本编码彼此独立。很难对文本描述之间的关系进行建模。换句话说,图表示很好地模拟了这些关系。

Figure from X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018

其他领域的GNN

GNN的更多实际应用包括人类行为检测,交通控制,分子结构研究,推荐系统,程序验证,逻辑推理,社会影响预测以及对抗攻击。下面显示了对社交网络中人际关系建模的图表。GNN可用于将人们分为不同的社区群体。

结论

我们在本文中介绍了一些图论,并强调了分析图的重要性。人们总是将机器学习算法视为“ 黑匣子 ”。大多数机器学习算法仅从训练数据的特征中学习,但没有实际的逻辑可以执行。使用形,我们也许能够将一些“逻辑”传递给机器,并使其更自然地“思考”。

GNN仍然是一个相对较新的领域,值得更多的研究关注。它是分析图数据的强大工具。但是,它不仅限于图中的问题。它可以很容易地推广到任何可以通过图建模的研究中。图建模是分析问题的自然方法。

参考链接:

https://medium.com/datadriveninvestor/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

成为VIP会员查看完整内容
0
94
小贴士
相关资讯
从数据结构到算法:图网络方法初探
机器之心
6+阅读 · 2019年8月12日
图论、图算法与图学习
专知
19+阅读 · 2019年6月24日
GitHub超2.7万星,最全Python入门算法来了
新智元
5+阅读 · 2019年4月28日
掌握图神经网络GNN基本,看这篇文章就够了
新智元
156+阅读 · 2019年2月14日
网络表示学习介绍
人工智能前沿讲习班
16+阅读 · 2018年11月26日
目标跟踪算法分类
算法与数据结构
18+阅读 · 2018年9月28日
相关VIP内容
专知会员服务
142+阅读 · 2020年4月12日
一份简短《图神经网络GNN》笔记,入门小册
专知会员服务
191+阅读 · 2020年4月11日
专知会员服务
117+阅读 · 2020年3月27日
【图神经网络(GNN)结构化数据分析】
专知会员服务
94+阅读 · 2020年3月22日
【2020新书】图机器学习,Graph-Powered Machine Learning
专知会员服务
310+阅读 · 2020年1月27日
相关论文
A Collective Learning Framework to Boost GNN Expressiveness
Mengyue Hang,Jennifer Neville,Bruno Ribeiro
19+阅读 · 2020年3月26日
Q-value Path Decomposition for Deep Multiagent Reinforcement Learning
Yaodong Yang,Jianye Hao,Guangyong Chen,Hongyao Tang,Yingfeng Chen,Yujing Hu,Changjie Fan,Zhongyu Wei
19+阅读 · 2020年2月10日
Hyper-SAGNN: a self-attention based graph neural network for hypergraphs
Ruochi Zhang,Yuesong Zou,Jian Ma
12+阅读 · 2019年11月6日
HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
Naganand Yadati,Madhav Nimishakavi,Prateek Yadav,Vikram Nitin,Anand Louis,Partha Talukdar
9+阅读 · 2019年5月22日
Joint Embedding of Meta-Path and Meta-Graph for Heterogeneous Information Networks
Lichao Sun,Lifang He,Zhipeng Huang,Bokai Cao,Congying Xia,Xiaokai Wei,Philip S. Yu
4+阅读 · 2018年9月11日
Kevin Scaman,Francis Bach,Sébastien Bubeck,Yin Tat Lee,Laurent Massoulié
7+阅读 · 2018年6月1日
Xuanyi Dong,Liang Zheng,Fan Ma,Yi Yang,Deyu Meng
7+阅读 · 2018年2月14日
Nils Bore,Patric Jensfelt,John Folkesson
6+阅读 · 2018年1月28日
Joel A. Tropp,Alp Yurtsever,Madeleine Udell,Volkan Cevher
4+阅读 · 2018年1月2日
Haitham Afifi,Sebastien Auroux,Holger Karl
7+阅读 · 2017年12月18日
Top
微信扫码咨询专知VIP会员