关于图算法 & 图分析的基础知识概览

2019 年 5 月 16 日 机器之心
关于图算法 & 图分析的基础知识概览

机器之心转载

来源:数据科学一线DSFrontier

本篇博文的主要内容来源于 O’Reilly 系列的《GraphAlgorithms》,对图算法进行了综述介绍,作者为 Amy E. Hodler & Mark Needham。


网址:https://learning.oreilly.com/library/view/graph-algorithms-/9781492060116/


你肯定没有读过这本书,因为这本书的发布日期是2019年5月。本文会覆盖该书的大部分内容,读完这篇,你能够了解图算法的基本概念。关于此书,作为市面上为数不多的面向数据科学应用的图算法书籍,写的比较全面系统和易懂。当然,书在细节上的提高空间还有很多。今天内容很多,坐稳~


目录

图算法 & 图分析

图基础知识

       连通图与非连通图

       未加权图与加权图

       有向图与无向图

       非循环图和循环图

图算法

       路径搜索算法

              DFS & BFS

              最短路径

              最小生成树

              随机游走

       中心性算法

              DegreeCentrality

              ClosenessCentrality

              BetweennessCentrality

              PageRank

       社群发现算法

              MeasuringAlgorithm

              ComponentsAlgorithm

              LabelPropagation Algorithm

              LouvainModularity Algorithm

结论


图算法 & 图分析


图分析使用基于图的方法来分析连接的数据。我们可以:查询图数据,使用基本统计信息,可视化地探索图、展示图,或者将图信息预处理后合并到机器学习任务中。图的查询通常用于局部数据分析,而图计算通常涉及整张图和迭代分析。


图算法是图分析的工具之一。图算法提供了一种最有效的分析连接数据的方法,它们描述了如何处理图以发现一些定性或者定量的结论。图算法基于图论,利用节点之间的关系来推断复杂系统的结构和变化。我们可以使用这些算法来发现隐藏的信息,验证业务假设,并对行为进行预测。


图分析和图算法具有广泛的应用潜力:从防止欺诈,优化呼叫路由,到预测流感的传播。下图是 Martin Grandjean 创建的航线网络图,这幅图清楚地展示了航空运输集群高度连接的结构,帮助我们了解航空运力如何流动。航线网络采用典型的辐射式结构(hub-and-spoke structure),这样的结构在有限运力的前提下,增大了航线的网络的始发-到达对(OD Pair),然而却也带来了系统级联延迟的可能。


图基础知识


我们已经在前一篇博文中介绍了属性图的概念。我们已经知道了节点、关系、属性(Property)、标签等概念。



子图(Subgraph)是一张图的一部分。当我们需要对图中的特定节点,特定关系,或者特定标签或者属性进行特定分析时,子图就会很有用。


路径(Path)是一组节点及他们的关系的集合。以上图为例,“Dan” 开过型号为 “Volvo V70” 的车,这辆车是属于 “Ann” 的。那么节点 “Dan” “Ann” “Car”和关系 “Drives” “Owns” 组成了一个简单的路径。


我们在介绍图算法前,先梳理一下图的不同属性(Attribute)。


连通图与非连通图


连通图(Connected Graphs)指图内任意两个节点间,总能找到一条路径连接它们,否则,为非连通图(Disconnected Graphs)。也就是说,如果图中包含岛(Island),则是非连通图。如果岛内的节点都是连通的,这些岛就被成为一个部件(Component,有时也叫 Cluster)。



有些图算法在非连通图上可能产生无法预见的错误。如果我们发现了未预见的结果,可以首先检查图的结构是否连通。


未加权图与加权图


未加权图(Unweighted Graphs)的节点和边上均没有权重。对于加权图(Weighted Graphs),所加权重可以代表:成本、时间、距离、容量、甚至是指定域的优先级。下图给出了示意图。



基本的图算法可以通过处理权重来代表关系的强度。许多算法通过计算指标,用作后续算法的权重。也有些算法通过更新权重值,来查找累计总数、最小值或最优化结果。


关于加权图的一个典型用途是路径寻找算法。这些算法支持我们手机上的地图应用程序,并计算位置之间最短/最便宜/最快的运输路线。例如,下图使用了两种不同的方法来计算最短路线。



如果没有权重,计算最短路径时,实则在计算关系(Relation,也称 Hop)的数量。那么在上图左边,我们找到 A 和 E 之间的最短距离为 2,经过 D 点。如果像上图右边所示,边被赋予了权重,用以代表节点之间的物理距离(单位:KM)。那么我们可以找到 A 和 E 之间的最短距离是 50 KM,需要经过 C 和 D 两个点。而此时,在未加权图中计算的最短路径 A-D-E 距离为 70 KM,比我们找到的路径 A-C-D-E 距离远。


有向图与无向图


在无向图(Undirected Graphs)中,节点的关系被认为是双向的(bi-directional),例如朋友关系。而在有向图(Directed Graphs)中,节点的关系可以指定方向。边如果指向了一个节点,我们称为 in-link,边如果从一个节点出发,我们称为 out-link。


边的方向加入了更多维度的信息,同样关系的边,却包含不同的方向,则代表了不同的语义信息。如下图所示,有向图绘制了一个简单的同学网络,边的方向代表着 “喜欢”。那么从图中,我们可以知道,同学中 “最受欢迎的” 的人是 “A” 和 “C”。




我们还可以用道路网络帮我们理解为什么需要有向图和无向图。例如,高速公路一般都是双向的,我们使用无向图即可。但是,在城市内部,经常会有单向车道,我们必须使用有向图。


非循环图和循环图


图论中,循环指一些特殊的路径,它们的起点和终点是同一个节点。在非循环图(Acyclic Graph)中,不存在循环路径,相反则为循环图(Cyclic Graphs)。如下图所示,有向图和无向图都可能包含循环,所不同的是,有向图的路径必须遵循边的方向。图中的 Graph 1 是一个典型的 DAG(Directed Acyclic Graph,有向无循环图),并且 DAG 通常有叶子节点(leaf node,也称 dead node)。



Graph 1 和 Graph 2 是无循环的,因为我们在不重复任何一条边的情况下,无法从任何一个点出发,再回到它。Graph 3 中有一个简单的循环 A-D-C-A。而 Graph 4 中,我们可以发现多个循环:B-F-C-D-A-C-B,C-B-F-C 等等。


循环在图中非常常见。有时,我们为了提高处理效率,会将循环图转化为非循环图(通过剪除一些关系)。DAG 在调度、版本控制等问题中十分常见。实际上,我们在数学或者计算机科学中经常遇见的树(Tree)就是一个典型的 DAG,只是对于树来说,只能拥有一个 Parent,而 DAG 没有这个限制。


图算法


我们关注三类核心的图算法:路径搜索(Pathfinding and Search)、中心性计算(Centrality Computation)和社群发现(Community Detection)。


路径搜索算法


图搜索算法(Pathfinding and Search Algorithms)探索一个图,用于一般发现或显式搜索。这些算法通过从图中找到很多路径,但并不期望这些路径是计算最优的(例如最短的,或者拥有最小的权重和)。图搜索算法包括广度优先搜索和深度优先搜索,它们是遍历图的基础,并且通常是许多其他类型分析的第一步。


路径搜索(Pathfinding)算法建立在图搜索算法的基础上,并探索节点之间的路径。这些路径从一个节点开始,遍历关系,直到到达目的地。路径搜索算法识别最优路径,用于物流规划,最低成本呼叫或者叫IP路由问题,以及游戏模拟等。


下图是路径搜索类算法的分类:



DFS & BFS


图算法中最基础的两个遍历算法:广度优先搜索(Breadth First Search,简称 BFS)和深度优先搜索(Depth First Search,简称 DFS)。BFS 从选定的节点出发,优先访问所有一度关系的节点之后再继续访问二度关系节点,以此类推。DFS 从选定的节点出发,选择任一邻居之后,尽可能的沿着边遍历下去,知道不能前进之后再回溯。


下面是两张同样的图,分别采用 BFS 和 DFS 进行图的遍历,图上节点的数字标识这遍历顺序。


BFS



DFS


对于我们数据科学的角色来说,我们很少真正需要使用 BFS 和 DFS。这两个图搜索算法更多地作为底层算法支持其他图算法。例如,最短路径问题和 Closeness Centrality (在后文会有介绍)都使用了 BFS 算法;而 DFS 可以用于模拟场景中的可能路径,因为按照 DFS 访问节点的顺序,我们总能在两个节点之间找到相应的路径。感兴趣的话,可以猜一猜,后文介绍的算法是否使用了图搜索算法,并且分别使用了 DFS 还是 BFS。


最短路径


最短路径(Shortest Paths)算法计算给定的两个节点之间最短(最小权重和)的路径。算法能够实时地交互和给出结果,可以给出关系传播的度数(degree),可以快速给出两点之间的最短距离,可以计算两点之间成本最低的路线等等。例如:


  • 导航:谷歌、百度、高德地图均提供了导航功能,它们就使用了最短路径算法(或者非常接近的变种);

  • 社交网络关系:当我们在 LinkedIn、人人(暴露年龄了)等社交平台上查看某人的简介时,平台会展示你们之间有多少共同好友,并列出你们之间的关系。


最常见的最短路径算法来自于 1956 年的 Edsger Dijkstra。Dijkstra 的算法首先选择与起点相连的最小权重的节点,也就是 “最临近的” 节点,然后比较 起点到第二临近的节点的权重 与 最临近节点的下一个最临近节点的累计权重和 从而决定下一步该如何行走。可以想象,算法记录的累计权重和 如同地理的 “等高线” 一样,在图上以 “波” 的形式传播,直到到达目的地节点。


最短路径算法有两个常用的变种:A (可以念作 A Star)algorithm和 Yen’s K-Shortest Paths。A algorithm 通过提供的额外信息,优化算法下一步探索的方向。Yen’s K-Shortest Paths 不但给出最短路径结果,同时给出了最好的 K 条路径。


所有节点对最短路径(All Pairs Shortest Path)也是一个常用的最短路径算法,计算所有节点对的最短路径。相比较一个一个调用单个的最短路径算法,All Pairs Shortest Path 算法会更快。算法并行计算多个节点的信息,并且这些信息在计算中可以被重用。


本文不打算再深入了,下图是从A节点开始的计算过程,看懂这张图,你就明白了。



All Pairs Shortest Path 算法通常用于,当最短路径受限或者变成了非最优时,如何寻找替代线路。其实算法非常常用:


  • 优化城市设施的位置和货物的分配:例如确定运输网格中不同路段上预期的交通负荷,例如快递线路设计,从而保证运输对突发事件的应对;

  • 作为数据中心设计算法的一部分:查找具有最大带宽和最小延迟的网络。


最小生成树


最小生成树(Minimum Spanning Tree)算法从一个给定的节点开始,查找其所有可到达的节点,以及将节点与最小可能权重连接在一起,行成的一组关系。它以最小的权重从访问过的节点遍历到下一个未访问的节点,避免了循环。


最常用的最小生成树算法来自于 1957 年的 Prim 算法。Prim 算法与Dijkstra 的最短路径类似,所不同的是, Prim 算法每次寻找最小权重访问到下一个节点,而不是累计权重和。并且,Prim 算法允许边的权重为负。



上图是最小生成树算法的步骤分解,算法最终用最小的权重将图进行了遍历,并且在遍历的过程中,不产生环。


算法可以用于优化连接系统(如水管和电路设计)的路径。它还用于近似一些计算时间未知的问题,如旅行商问题。虽然该算法不一定总能找到绝对最优解,但它使得复杂度极高和计算密集度极大的分析变得更加可能。例如:


  • 旅行计划:尽可能降低探索一个国家的旅行成本;

  • 追踪流感传播的历史:有人使用最小生成树模型对丙型肝炎病毒感染的医院暴发进行分子流行病学调查


随机游走


随机游走(Random Walk)算法从图上获得一条随机的路径。随机游走算法从一个节点开始,随机沿着一条边正向或者反向寻找到它的邻居,以此类推,直到达到设置的路径长度。这个过程有点像是一个醉汉在城市闲逛,他可能知道自己大致要去哪儿,但是路径可能极其“迂回”,毕竟,他也无法控制自己~


随机游走算法一般用于随机生成一组相关的节点数据,作为后续数据处理或者其他算法使用。例如:


  • 作为 node2vec 和 graph2vec 算法的一部分,这些算法可以用于节点向量的生成,从而作为后续深度学习模型的输入;这一点对于了解 NLP (自然语言处理)的朋友来说并不难理解,词是句子的一部分,我们可以通过词的组合(语料)来训练词向量。那么,我们同样可以通过节点的组合(Random Walk)来训练节点向量。这些向量可以表征词或者节点的含义,并且能够做数值计算。这一块的应用很有意思,我们会找机会来详细介绍;

  • 作为 Walktrap 和 Infomap 算法的一部分,用于社群发现。如果随机游走总是返回同一组节点,表明这些节点可能在同一个社群;

  • 其他机器学习模型的一部分,用于随机产生相关联的节点数据。


中心性算法


中心性算法(Centrality Algorithms)用于识别图中特定节点的角色及其对网络的影响。中心性算法能够帮助我们识别最重要的节点,帮助我们了解组动态,例如可信度、可访问性、事物传播的速度以及组与组之间的连接。尽管这些算法中有许多是为社会网络分析而发明的,但它们已经在许多行业和领域中得到了应用。


下图罗列了我们所有需要了解的中心性算法指标。



Degree Centrality


Degree Centrality (度中心性,以度作为标准的中心性指标)可能是整篇博文最简单的 “算法” 了。Degree 统计了一个节点直接相连的边的数量,包括出度和入度。Degree 可以简单理解为一个节点的访问机会的大小。例如,在一个社交网络中,一个拥有更多 degree 的人(节点)更容易与人发生直接接触,也更容易获得流感。


一个网络的平均度(average degree),是边的数量除以节点的数量。当然,平均度很容易被一些具有极大度的节点 “带跑偏” (skewed)。所以,度的分布(degree distribution)可能是表征网络特征的更好指标。


如果你希望通过出度入度来评价节点的中心性,就可以使用 degree centrality。度中心性在关注直接连通时具有很好的效果。应用场景例如,区分在线拍卖的合法用户和欺诈者,欺诈者由于尝尝人为太高拍卖价格,拥有更高的加权中心性(weighted centrality)。


Closeness Centrality


Closeness Centrality(紧密性中心性)是一种检测能够通过子图有效传播信息的节点的方法。紧密性中心性计量一个节点到所有其他节点的紧密性(距离的倒数),一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离最小值。


对于一个节点来说,紧密性中心性是节点到所有其他节点的最小距离和的倒数:



其中 u 是我们要计算紧密性中心性的节点,n 是网络中总的节点数,d(u,v) 代表节点 u 与节点 v 的最短路径距离。更常用的公式是归一化之后的中心性,即计算节点到其他节点的平均距离的倒数,你知道如何修改上面的公式吗?对了,将分子的 1 变成 n-1 即可。


理解公式我们就会发现,如果图是一个非连通图,那么我们将无法计算紧密性中心性。那么针对非连通图,调和中心性(Harmonic Centrality)被提了出来(当然它也有归一化的版本,你猜这次n-1应该加在哪里?):



Wasserman and Faust 提出过另一种计算紧密性中心性的公式,专门用于包含多个子图并且子图间不相连接的非连通图:



其中,N 是图中总的节点数量,n 是一个部件(component)中的节点数量。


当我们希望关注网络中传播信息最快的节点,我们就可以使用紧密性中心性。


Betweenness Centrality


中介中心性(Betweenness Centrality)是一种检测节点对图中信息或资源流的影响程度的方法。它通常用于寻找连接图的两个部分的桥梁节点。因为很多时候,一个系统最重要的 “齿轮” 不是那些状态最好的,而是一些看似不起眼的 “媒介”,它们掌握着资源或者信息的流动性。


中间中心性算法首先计算连接图中每对节点之间的最短(最小权重和)路径。每个节点都会根据这些通过节点的最短路径的数量得到一个分数。节点所在的路径越短,其得分越高。计算公式:



其中,p 是节点 s 与 t 之间最短路径的数量,p(u) 是其中经过节点 u 的数量。下图给出了对于节点 D 的计算过程:



当然,在一张大图上计算中介中心性是十分昂贵的。所以我们需要更快的,成本更小的,并且精度大致相同的算法来计算,例如 Randomized-Approximate Brandes。我们不会对这个算法继续深入,感兴趣的话,可以去了解一下,算法如何通过随机(Random)和度的筛选(Degree)达到近似的效果。


中介中心性在现实的网络中有广泛的应用,我们使用它来发现瓶颈、控制点和漏洞。例如,识别不同组织的影响者,他们往往是各个组织的媒介,例如寻找电网的关键点,提高整体鲁棒性。


PageRank


在所有的中心性算法中,PageRank 是最著名的一个。它测量节点传递影响的能力。PageRank 不但节点的直接影响,也考虑 “邻居” 的影响力。例如,一个节点拥有一个有影响力的 “邻居”,可能比拥有很多不太有影响力的 “邻居” 更有影响力。PageRank 统计到节点的传入关系的数量和质量,从而决定该节点的重要性。


PageRank 算法以谷歌联合创始人拉里·佩奇的名字命名,他创建了这个算法来对谷歌搜索结果中的网站进行排名。不同的网页之间相互引用,网页作为节点,引用关系作为边,就可以组成一个网络。被更多网页引用的网页,应该拥有更高的权重;被更高权重引用的网页,也应该拥有更高权重。原始公式:



其中,u 是我们想要计算 PageRank 的网页,T1 到 Tn 是引用的网页。d 被称为阻尼系数(damping factor),代表一个用户继续点击网页的概率,一般被设置为 0.85,范围 0~1。C(T) 是节点 T 的出度。


从理解上来说,PageRank 算法假设一个用户在访问网页时,用户可能随机输入一个网址,也可能通过一些网页的链接访问到别的网页。那么阻尼系数代表用户对当前网页感到无聊,随机选择一个链接访问到新的网页的概率。那么 PageRank 的数值代表这个网页通过其他网页链接过来(入度,in-degree)的可能性。那你能如何解释 PageRank 方程中的 1-d 呢?实际,1-d 代表不通过链接访问,而是随机输入网址访问到网页的概率。


PageRank 算法采用迭代方式计算,直到结果收敛或者达到迭代上限。每次迭代都会分两步更新节点权重和边的权重,详细如下图:



当然,上图的计算并没有考虑阻尼系数,那为什么一定要阻尼系数呢?除了我们定义的链接访问概率,有没有别的意义呢?从上图的过程中,我们可能会发现一个问题,如果一个节点(或者一组节点),只有边进入,却没有边出去,会怎么样呢?按照上图的迭代,节点会不断抢占 PageRank 分数。这个现象被称为 Rank Sink,如下图:



解决 Rank Sink 的方法有两个。第一个,假设这些节点有隐形的边连向了所有的节点,遍历这些隐形的边的过程称为 teleportation。第二个,使用阻尼系数,如果我们设置 d 等于 0.85,我们仍然有 0.15 的概率从这些节点再跳跃出去。


尽管阻尼系数的建议值为 0.85,我们仍然可以根据实际需要进行修改。调低阻尼系数,意味着访问网页时,更不可能不断点击链接访问下去,而是更多地随机访问别的网页。那么一个网页的 PageRank 分数会更多地分给他的直接下游网页,而不是下游的下游网页。


PageRank 算法已经不仅限于网页排名。例如:


  • 寻找最重要的基因:我们要寻找的基因可能不是与生物功能联系最多的基因,而是与最重要功能有紧密联系的基因;

  • who to follow service at twitter:Twitter使用个性化的 PageRank 算法(Personalized PageRank,简称 PPR)向用户推荐他们可能希望关注的其他帐户。该算法通过兴趣和其他的关系连接,为用户展示感兴趣的其他用户;

  • 交通流量预测:使用 PageRank 算法计算人们在每条街道上停车或结束行程的可能性;

  • 反欺诈:医疗或者保险行业存在异常或者欺诈行为,PageRank 可以作为后续机器学习算法的输入。


社群发现算法


社群的形成在各种类型的网络中都很常见。识别社群对于评估群体行为或突发事件至关重要。对于一个社群来说,内部节点与内部节点的关系(边)比社群外部节点的关系更多。识别这些社群可以揭示节点的分群,找到孤立的社群,发现整体网络结构关系。社群发现算法(Community Detection Algorithms)有助于发现社群中群体行为或者偏好,寻找嵌套关系,或者成为其他分析的前序步骤。社群发现算法也常用于网络可视化。


下图是社群发现算法的分类。



Measuring Algorithm


三角计数(Triangle Count)和聚类系数(Clustering Coefficient)经常被一起使用。三角计数计算图中由节点组成的三角形的数量,要求任意两个节点间有边(关系)连接。聚类系数算法的目标是测量一个组的聚类紧密程度。该算法计算网络中三角形的数量,与可能的关系的比率。聚类系数为 1 表示这个组内任意两个节点之间有边相连。


有两种聚类系数:局部聚类系数(Local Clustering Coefficient)和全局聚类系数(Global Clustering Coefficient)。


局部聚类系数计算一个节点的邻居之间的紧密程度,计算时需要三角计数。计算公式:



其中,u 代表我们需要计算聚类系数的节点,R(u) 代表经过节点 u 和它的邻居的三角形个数,k(u) 代表节点 u的度。下图是三三角计数聚类系数计算示意图:



全局聚类系数是局部聚类系数的归一化求和。


当需要计算一个组的稳定性或者聚类系数时,我们可以使用三角计数。三角计数在社交网络分析中有广泛的应用,通航被用来检测社区。聚类系数可以快速评估特定组或整个网络的内聚性。这些算法可以共同用于特定网络结构的寻找。例如,探索网页的主题结构,基于网页之间的相互联系,检测拥有共同主题的 “网页社群”。


Components Algorithm


强关联部件(Strongly Connected Components,简称 SCC)算法寻找有向图内的一组一组节点,每组节点可以通过关系 互相 访问。在 “Community Detection Algorithms” 的图中,我们可以发现,每组节点内部不需要直接相连,只要通过路径访问即可。


关联部件(Connected Components)算法,不同于 SCC,组内的节点对只需通过一个方向访问即可。


关联类算法作为图分析的早期算法,用以了解图的结构,或确定可能需要独立调查的紧密集群十分有效。对于推荐引擎等应用程序,也可以用来描述组中的类似行为等等。许多时候,算法被用于查找集群并将其折叠成单个节点,以便进一步进行集群间分析。对于我们来说,先运行以下关联类算法查看图是否连通,是一个很好的习惯。


Label Propagation Algorithm


标签传播算法(Label Propagation Algorithm,简称 LPA)是一个在图中快速发现社群的算法。在 LPA 算法中,节点的标签完全由它的直接邻居决定。算法非常适合于半监督学习,你可以使用已有标签的节点来种子化传播进程。


LPA 是一个较新的算法,由 Raghavan 等人于 2007 年提出。我们可以很形象地理解算法的传播过程,当标签在紧密联系的区域,传播非常快,但到了稀疏连接的区域,传播速度就会下降。当出现一个节点属于多个社群时,算法会使用该节点邻居的标签与权重,决定最终的标签。传播结束后,拥有同样标签的节点被视为在同一群组中。


下图展示了算法的两个变种:Push 和 Pull。其中 Pull 算法更为典型,并且可以很好地并行计算:



我们不再继续深入,看完上图,你应该已经理解了算法的大概过程。其实,做过图像处理的人很容易明白,所谓的标签传播算法,不过是图像分割算法的变种,Push 算法是区域生长法(Region Growing)的简化版,而 Pull 更像是分割和合并(divide-and-merge,也有人称 split-merge)算法。确实,图像(image)的像素和图(graph)的节点是十分类似的。


Louvain Modularity Algorithm


Louvain Modularity 算法在给节点分配社群是,会比较社群的密度,而不仅仅是比较节点与社群的紧密程度。算法通过查看节点与社群内关系的密度与平均关系密度的比较,来量化地决定一个节点是否属于社群。算法不但可以发现社群,更可以给出不同尺度不同规模的社群层次,对于理解不同粒度界别的网络结构有极大的帮助。


算法在 2008 年被提出以后,迅速成为了最快的模块化算法之一。算法的细节很多,我们无法一一覆盖,下图给出了一个粗略的步骤,帮助我们理解算法如何能够多尺度地构建社群:



Louvain Modularity 算法非常适合庞大网络的社群发现,算法采用启发式方式从而能够克服传统 Modularity 类算法的局限。算法应用:


  • 检测网络攻击:该算可以应用于大规模网络安全领域中的快速社群发现。一旦这些社群被发现,就可以用来预防网络攻击;

  • 主题建模:从 Twitter 和 YouTube 等在线社交平台中提取主题,基于文档中共同出现的术语,作为主题建模过程的一部分。


结论


本文更像是一篇综述,算法很干,我们会在后续继续分享图分析相关内容,敬请期待。


公众号简介:数据科学一线(微信号:DSFrontier)。分享数据科学家的日常,关注能落地的技术,介绍数据科学在各个行业的应用。


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

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

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

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

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

登录查看更多
4

相关内容

在图论中,连通图基于连通的概念。在一个无向图 G 中,若从顶点i到顶点j有路径相连(当然从j到i也一定有路径),则称i和j是连通的。如果 G 是有向图,那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的,那么图被称作连通图。如果此图是有向图,则称为强连通图(注意:需要双向都有路径)。图的连通性是图的基本性质。

【导读】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
小贴士
相关资讯
一文了解成分句法分析
人工智能头条
15+阅读 · 2019年4月24日
关于机器学习你要了解的 5 件事
机器学习算法与Python学习
5+阅读 · 2018年9月7日
干货 | 受限玻尔兹曼机基础教程
机器学习算法与Python学习
5+阅读 · 2018年3月27日
15款免费预测分析软件!收藏好,别丢了!
七月在线实验室
9+阅读 · 2018年2月27日
推荐系统机器学习算法概览
论智
6+阅读 · 2017年12月14日
入门 | 一文概览深度学习中的激活函数
机器之心
5+阅读 · 2017年11月2日
深度学习知识总结(一)
深度学习探索
7+阅读 · 2017年7月18日
相关VIP内容
相关论文
Suyu Ge,Chuhan Wu,Fangzhao Wu,Tao Qi,Yongfeng Huang
20+阅读 · 2020年3月31日
Heterogeneous Graph Transformer
Ziniu Hu,Yuxiao Dong,Kuansan Wang,Yizhou Sun
21+阅读 · 2020年3月3日
Qingyu Guo,Fuzhen Zhuang,Chuan Qin,Hengshu Zhu,Xing Xie,Hui Xiong,Qing He
83+阅读 · 2020年2月28日
Wenwu Zhu,Xin Wang,Peng Cui
20+阅读 · 2020年1月2日
Saurabh Verma,Zhi-Li Zhang
4+阅读 · 2019年9月25日
Aravind Sankar,Yanhong Wu,Liang Gou,Wei Zhang,Hao Yang
44+阅读 · 2019年6月15日
Accelerated Methods for Deep Reinforcement Learning
Adam Stooke,Pieter Abbeel
5+阅读 · 2019年1月10日
Felix Laumann,Kumar Shridhar,Adrian Llopart Maurin
18+阅读 · 2018年6月27日
KiJung Yoon,Renjie Liao,Yuwen Xiong,Lisa Zhang,Ethan Fetaya,Raquel Urtasun,Richard Zemel,Xaq Pitkow
3+阅读 · 2018年5月25日
Yeonwoo Jeong,Hyun Oh Song
6+阅读 · 2018年5月15日
Top
微信扫码咨询专知VIP会员