图与图学习

一、图

1.1、图的定义

图表示物 件与物件之间的关系的数学对象,是图论的基本研究对象。

节点(node)用红色标出,通过黑色的边(edge)连接。

在图上执行怎样的分析:

  • 研究拓扑结构和连接性
  • 群体检测
  • 识别中心节点
  • 预测缺失的节点
  • 预测缺失的边

空手道俱乐部图

这个「空手道」图表示什么?Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员,成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间,管理员 JohnA 与教练 Mr.Hi(化名)之间出现了冲突,导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部,另一半则找了一个新教练或放弃了空手道。基于收集到的数据,除了其中一个成员,Zachary 正确分配了所有成员在分裂之后所进入的分组。

1.2、图的基本表示方法

  • G=(V, E) 由下列要素构成:

  • 一组节点(也称为 verticle)V=1,…,n

  • 一组 E⊆V×V

  • (i,j) ∈ E 连接了节点 i 和 j

  • ij 被称为相邻节点(neighbor)

  • 节点的(degree)是指相邻节点的数量

    • 如果一个图的所有节点都有 n-1 个相邻节点,则该图是完备的(complete)。也就是说所有节点都具备所有可能的连接方式。
    • 从 i 到 j 的路径(path)是指从 i 到达 j 的边的序列。该路径的长度(length)等于所经过的边的数量。
    • 图的直径(diameter)是指连接任意两个节点的所有最短路径中最长路径的长度。
    • 测地路径(geodesic path)是指两个节点之间的最短路径。
    • 如果所有节点都可通过某个路径连接到彼此,则它们构成一个连通分支(connected component)。如果一个图仅有一个连通分支,则该图是连通的(connected)
有向图
  • 如果一个图的边是有顺序的配对,则该图是有向的(directed)。i 的入度(in-degree)是指向 i 的边的数量,出度(out-degree)是远离 i 的边的数量。

  • 如果可以回到一个给定节点,则该图是有环的(cyclic)。相对地,如果至少有一个节点无法回到,则该图就是无环的(acyclic)。
  • 图可以被加权(weighted),即在节点或关系上施加权重。
  • 如果一个图的边数量相比于节点数量较小,则该图是稀疏的(sparse)。相对地,如果节点之间的边非常多,则该图是密集的(dense)
图的种类

分别是有向图无向图有环图无环图加权图无加权图稀疏图密集图

1.3、同构图与异构图

两个图 G 和 H 是同构图(isomorphic graphs),能够通过重新标记图 G 的顶点而产生图 H。

如果 G 和 H 同构,那么它们的阶是相同的,它们大小是相同的,它们个顶点的度数也对应相同。

异构图是一个与同构图相对应的新概念。

传统同构图(Homogeneous Graph)数据中只存在一种节点和边,因此在构建图神经网络时所有节点共享同样的模型参数并且拥有同样维度的特征空间。

异构图(Heterogeneous Graph)中可以存在不只一种节点和边,因此允许不同类型的节点拥有不同维度的特征或属性。

异构图和同构图的区别

同构图中,node 的种类只有一种,一个 node 和另一个 node 的连接关系只有一种

  1. 例如在社交网络中,可以想象 node 只有‘人’这一个种类,edge 只有‘认识’这一种连接。而人和人要么认识,要么不认识。
  2. 但是也可能细分有人,点赞,推文。则人和人可能通过认识连接,人和推文可能通过点赞连接,人和人也可能通过点赞同一篇推文连接(meta path)。这里节点、节点之间关系的多样性表达就需要引入异构图了。

异构图中,有很多种 node。node 之间也有很多种连接关系(edge),这些连接关系的组合则种类更多(meta-path), 而这些 node 之间的关系有轻重之分,不同连接关系也有轻重之分。比如在 IMDB 中,可以有三类 node 分别是 Movie,Director 和 Actor

1.4、主要的图算法

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

  • Pathfinding(寻路):根据可用性和质量等条件确定最优路径。我们也将搜索算法包含在这一类别中。这可用于确定最快路由或流量路由。
  • Centrality(中心性):确定网络中节点的重要性。这可用于识别社交网络中有影响力的人或识别网络中潜在的攻击目标。
  • Community detection(社群检测):评估群体聚类的方式。这可用于划分客户或检测欺诈等。
寻路和图搜索算法
  • 寻路算法是通过最小化跳(hop)的数量来寻找两个节点之间的最短路径。
  • 搜索算法不是给出最短路径,而是根据图的相邻情况或深度来探索图。这可用于信息检索

1). 搜索算法

图搜索算法主要有两种:

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

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

    2). 寻路算法

    a. 最短路径

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

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

b. 单源最短路径

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

c. 所有配对最短路径

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

d. 最小权重生成树

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

社群检测

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

这通常可用于识别社交社群客户行为网页主题。 社区是指一组相连节点的集合。但是,目前关于社群还没有广泛公认的定义,只是社群内的节点应该要密集地相连。

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

该算法的步骤如下:

  1. 计算网络中所有已有边的居间性。
  2. 移除居间性最高的边。
  3. 移除该边后,重新计算所有边的居间性。
  4. 重复步骤 2 和 3,直到不再剩余边。
分层聚类

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

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

相似度距离

衡量聚类是否相近。令 d(i,j)ij 之间的最短路径的长度。

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

二、图学习

图学习中包含三种主要的任务:

  • 链接预测(Link prediction)
  • 节点标记预测(Node labeling)
  • 图嵌入(Graph Embedding)

在链接预测中,给定图 G,我们的目标是预测新边。例如,当图未被完全观察时,或者当新客户加入平台(例如,新的 LinkedIn 用户)时,预测未来关系或缺失边是很有用的。

在不同的 task 中,Link Prediction 被用于:

  1. 在社交网络中,进行用户/商品推荐

  2. 在生物学领域,进行相互作用发现

  3. 在知识图谱中,进行实体关系学习

  4. 在基础研究中,进行图结构捕捉

在不同的 work 中,Link Prediction 还会被称为(可以使用这些关键词检索哦):

  1. Edge Embedding/Classification

  2. Relational Inference/Reasoning

  3. Graph Generation(一种是从节点生成边,另一种是从噪声生成图,前者是 Link Prediction)