关于GNN相关的前置知识
首先非常建议大家去读一读下面这篇文章 A Gentle Introduction to Graph Neural Networks ,指路 https://distill.pub/2021/gnn-intro/ 。
图 Graph
图的基础表述
从数学上讲,一个图可以简单地表示为 :
- (Vertex/Node): 节点。代表实体,比如社交网络里的一位用户、分子结构里的一个原子。
- (Edge/Link): 边。代表实体间的关系,比如用户间的关注、原子间的化学键。
我们通常用两个矩阵来描述图:
- 邻接矩阵 (Adjacency Matrix, ): 描述谁和谁相连。如果节点 和 相连,则 ,否则为 。
- 特征矩阵 (Feature Matrix, ): 描述节点自身的属性。
图的拓扑特性
子图:给定图 ,若 且 ,且 中的边所关联的顶点都在 中,则 是 的子图。
连通图:在无向图中,如果任意两个节点 之间都存在路径,则图是连通的。对于有向图,若任意两点双向可达,称为强连通。
连通分量:图中最大的连通子图。可以把它想象成社交网络中的小圈子,圈子内部相互认识,但圈子之间没有任何交集。
最短路径:两点之间边数最少的路径(或权值和最小)。
直径 (Diameter):图中任意两点间最短路径的最大值。
度 (Degree):对于无向图 ,节点 的度 定义为连接到该节点的边的数目。在有向图中,边的方向性使得度被拆分为两个独立的概念:入度与出度。入度 (In-degree, ) 为指向节点 的边的数量;出度 (Out-degree, ) 为从节点 出发的边的数量;总度为节点入度与出度的加和。
图中心性
在图论分析中,中心性(Centrality)是用于量化图中顶点重要程度或影响力的一类指标。由于重要性在不同的应用语境下有不同的定义,图论中演化出了多种中心性度量方法。
度中心性 (Degree Centrality) 是最基础、最直观的中心性度量指标。它基于一个朴素的假设:一个节点的连接数越多,其在网络中的地位就越重要。
对于一个拥有 个节点的无向图 ,节点 的度中心性 定义为该节点的度数 :
为了便于在不同规模的图之间进行比较,通常会对该指标进行归一化处理。归一化后的度中心性定义为节点实际度数与图中可能的最大度数(即 )之比:
紧密中心性 (Closeness Centrality) 是从距离的角度出发,衡量一个节点到达图中其他所有节点的效率。如果一个节点到其他节点的平均最短路径距离越小,则该节点在网络中越接近几何中心。
设 为节点 与 之间的最短路径长度。节点 的紧密中心性定义为其到所有其他节点距离之和的倒数:
中介中心性 (Betweenness Centrality) (亦称间距中心性)衡量的是一个节点在网络中担任桥梁角色的程度。它关注的是节点对网络中信息流动的控制能力。
定义 为节点 到节点 之间所有的最短路径总数, 为这些最短路径中经过节点 的数量。节点 的中介中心性定义为:
特征向量中心性 (Eigenvector Centrality) 特征向量中心性是一种递归定义的指标。其核心思想是:一个节点的重要性不仅取决于其邻居的数量,还取决于其邻居的重要性。
设 为节点 的重要性得分,其值正比于其所有邻居的重要性得分之和:
其中 为图的邻接矩阵, 为常数。将其写成矩阵形式,即:
这表明,节点重要性向量 实际上是邻接矩阵 的特征向量。根据 Perron-Frobenius 定理,对于一个连通图,对应于最大特征值 的特征向量的所有分量均为正值。因此,特征向量中心性通常取邻接矩阵最大特征值对应的特征向量。该指标不仅考虑了节点的局部结构,还融合了全网的拓扑结构信息。
PageRank
既然是介绍图,那么肯定绕不开经典的 PageRank ,如果将万维网看作一个巨大的有向图,其中网页是节点,网页之间的超链接是有向边,那么网页的重要性就可以通过图的拓扑结构来推导。
PageRank 由 Google 创始人 Larry Page 和 Sergey Brin 提出。其核心假设基于随机游走模型(Random Surfer Model):一个网页的重要性取决于指向它的其他网页的重要性,以及这些网页包含的外链数量。
假设网络中有一个冲浪者,他在当前页面 时,会等概率地随机点击页面上的任意一个超链接跳转到下一个页面。如果页面 有 个出链(Out-degree),那么他点击其中任何一个链接的概率为 。
基于此,一个页面 的 PageRank 值(记为 )可以通过所有指向它的页面 的 PageRank 值来定义:
其中, 表示所有包含指向页面 的链接的页面集合(即 的入邻居)。可以看出,PageRank 的计算是一个递归过程,通常通过迭代来求解稳定值。
然而,上述基本模型在实际网络中会遇到两个问题,一是某些网页没有出链,导致全网的 PR 值在迭代中逐渐趋零;二是某些网页集合只在内部相互链接,形成封闭循环。
为了解决这两个问题,PageRank 引入了阻尼因子 (Damping Factor, 通常记为 ),意味着游走者在任何一个页面时,有 的概率继续点击链接,有 的概率感到厌倦,并在地址栏随机输入网址跳转到全网的任意一个页面。
加入了阻尼因子后的 PageRank 完整公式为:
其中, 是网络中所有网页的总数。通常经验上取 。
PageRank 的计算等价于求解马尔可夫链的平稳分布。设 为状态转移矩阵, 为所有网页的 PR 值列向量,则迭代过程可表示为:
(其中 为全 1 矩阵)。当 时, 收敛于修正后转移矩阵的最大特征值(即 1)对应的特征向量。
扯远了,这一章我们大概了解了图的一些基本性质,在下一章中,我们将了解到如何表征一个图,即 Graph Embedding 。
图嵌入 Graph Embedding
正如 Distill 的 GNN 综述中所指出的,传统深度学习模型(如 CNN 处理图像、RNN 处理文本)依赖于数据具有固定的、规则的空间结构。而图数据具有高度的灵活性和无序性(其具有置换不变性,改变其空间结构不回对其造成影响)。
那能否直接使用邻接矩阵 作为特征输入呢?显然是不行的,真实世界的网络(如微信社交网)包含数亿节点,其邻接矩阵极大且极其稀疏;同时,在邻接矩阵中,每个节点可看作一个独热编码(One-hot)向量。任何两个不同节点的向量内积都为 0,这完全丢失了图的连通结构;最后,一旦网络中新增节点,整个矩阵的维度都会随之改变,模型必须重新训练。
因此,我们需要使用 图嵌入(Graph Embedding) ,图嵌入的目标是寻找一个映射函数 ,将图中的离散节点映射到一个低维、稠密、连续的向量空间中(通常 ),并在向量空间中,保持图中原有的拓扑结构信息和节点相似性。
随机游走 RandomWalk
在图 中,从节点 开始的随机游走可以定义为一个节点序列 ,其中 是游走的步数。在最朴素的设定下,如果当前停留在节点 ,那么下一个节点 将从 的邻居节点集中等概率地随机选取。
在随机游走序列中,如果两个节点经常出现在彼此的上下文中(即距离很近),那么它们在图中的结构作用或所属类别(如果要分类的话)区也非常相似。
DeepWalk
从图中的每一个节点出发,生成指定数量(如 个)、指定长度(如 步)的均匀随机游走序列。由于是等概率选择邻居,我们称之为无偏游走(Unbiased Random Walk)。
将这些游走序列视作“句子”,投入 Skip-Gram 模型中。在 NLP 中,Skip-Gram 的目标是:给定序列中的一个中心节点 ,最大化其前后窗口大小为 内的上下文节点出现的概率。为什么可以借鉴 NLP 的模型 Skip-Gram(Word2Vec最常见的模型),其实是由于图中的随机游走序列,在统计特性上与人类语言的句子非常相似,比如人类的句子是单词的排列,如[我, 喜欢, 学习, 图, 神经网络],而通过随机有座,图中的节点也可以排列成序列,如[节点1, 节点5, 节点2, 节点8, 节点5]。这两者都遵循幂律分布,图中少数几个枢纽节点会频繁出现在大量随机游走序列中,就像人类语言中的高频词(如“的”、“是”)一样。
想象你手里拿着一条随机游走生成的序列:[A, B, C, D, E]。假设当前窗口大小 ,我们关注中心节点 C。DeepWalk(基于 Word2Vec)的目标是,如果你手里只有节点 C 的向量 ,你能不能通过这个向量,精准地预测出它的邻居 B 和 D 也是这条序列里的人?
如果模型预测对了(概率 很高),说明 很好地捕捉了它的上下文信息,如果模型预测错了,我们就调整 ,直到它能预测对为止。
用数学语言表达就是,设定一个窗口大小 ,对于游走序列中的节点 ,模型尝试利用其向量表示 来预测它前后的邻居 。设 为节点 的连续型向量表示(即我们最终要求的 Embedding),DeepWalk 的优化目标是最大化以下对数似然函数:
其中,代表遍历序列里的每一个节点作为中心点。代表对于选定的中心点,预测它左边 个和右边 个邻居。而那么 描述的是:在已知当前中心节点是 的情况下,它的上下文邻居恰好是 的可能性。
而又如何计算呢?我们知道,在向量空间里,衡量两个向量像不像最简单的方法就是内积(点积)。两个向量越接近,它们的内积就越大。为了把这个内积变成一个 0 到 1 之间的概率,我们使用 Softmax 函数:
其中的分母则是中心节点 和图中所有节点(包括那些不相关的点)的内积总和。
理解了公式,但我们仍然需要理解为什么 DeepWalk 的优化目标是最大化上面的对数似然函数。想象你是一个侦探,你在空手道俱乐部潜伏了几天。你并不认识每个人,但你看到了很多真实的活动轨迹:小明、小红、小刚在一起喝咖啡,小刚、小强、老王在一起打球。这相当于随机游走路径集合。
而现在,你手里有一个包含所有节点向量的模型,向量点积大就代表两个人关系较为接近,那么就意味着他们出现在一个随机游走路径中的概率更高。而最大化总概率(即上面的对数似然函数)就意味着我们要不断调整模型里的那些向量坐标,直到模型预测的结果和我们观察到的事实接近(和随机游走出的集合接近)。
DeepWalk 使用的 Word2Vec (Skip-Gram) 模型是一个只有 3 层的神经网络。其输入层是节点的 One-hot 编码向量(维度是 ,全图节点数)。隐藏层没有激活函数,它的神经元个数就是你想要的 Embedding 维度,比如128。输出层为Softmax 层,维度也是 ,用来预测周围每个节点出现的概率。
训练的过程为:
- 把节点 的 One-hot 向量喂给网络。
- 网络通过当前的权重 计算出预测概率。
- 将预测结果与真实的游走序列对比,计算误差。
- 使用反向传播调整权重 。
当训练结束,权重矩阵 里的每一行就是我们要的 Embedding。也就是说,和一般情况下使用神经网络不同,该任务不训练预测工具,只是通过预测任务,让神经网络生成一组特征向量,这组特征向量可以做各种任务,比如分类。
DeepWalk简单实战
为了能够更好的理解deepwalk的应用,我们做一个简单的例子。我们通过:
1 | G = nx.karate_club_graph() |
可以加载著名的 Toy Dataset 空手道俱乐部网络。其图结构可以被可视化为图2(a)。在下面的代码实践中,我们需要设计一个DeepWalk类,包含多次随机游走生成序列,并利用 gensim 库的 Word2Vec 类实现训练 Skip-gram 模型
1 | import networkx as nx |
我们来执行一下:
1 | G = nx.karate_club_graph() |
生成了 34 个节点的 64 维向量,可以用于下游任务了,这里以分类任务为例,使用经典的逻辑回归分类器进行分类。为了展示 embedding 的效果,我们仅用20%的数据,就是区区几个点,进行训练。
1 | from sklearn.linear_model import LogisticRegression |
对predict结果做一下评估,显示仅使用 20% 标注样本下的准确率: 0.8571,还是非常不错的。下图(b)展示了分类结果和分类错误的点。
Node2vec
在上文中,我们简单介绍了RandomWalk的实现DeepWalk,然而,DeepWalk 的完全随机游走真的是最优解吗?在真实世界的网络中,当我们说两个节点很相似时,通常包含两种截然不同的物理含义:
- 一是距离相近、互为邻居、同属一个社区的节点应该具有相似的 Embedding。
- 二是在网络拓扑中扮演类似角色的节点应该具有相似的 Embedding,哪怕它们在空间上相隔十万八千里。
用文章中专业的语言来说,在复杂网络理论中,节点的相似性通常被归结为两种物理范式:同质性(Homophily)与结构等价性(Structural Equivalence)。
同质性强调物以类聚,即距离相近、同属一个密集社区的节点应当具有高度相似的表征;要捕获这种特征,游走策略需要倾向于深度优先搜索(DFS),以探索社区的宏观边界。相反,结构等价性关注节点在网络拓扑中所扮演的角色(如中心枢纽或边缘节点),即使两个节点在物理空间上相距甚远,只要它们的局部网络结构相似,其表征亦应趋同;捕获这一特征则要求游走策略偏向广度优先搜索(BFS),以充分描绘节点的微观邻域轮廓。
Node2vec 的核心贡献,就是设计了一种有偏的二阶随机游走机制。
假设游走者刚刚通过边 从节点 来到了当前节点 。现在他站在 上,思考着下一步走向 的概率,这个转移概率定义为:
其中, 是边 的固有权重(如果是无权图,则 )。真正的核心在于搜索偏好系数 。
Node2vec 引入了两个极其关键的超参数(Hyperparameters)来定义 :
- 返回参数 (Return parameter, ):控制游走者折返回上一个节点 的概率。
- 进出参数 (In-out parameter, ):控制游走者向更远方探索的概率。
根据候选节点 与上一步节点 之间的最短路径距离 ,系数 被定义为一个分段函数:
这里我们就不深入展开了,作为DeepWalk的一个升级,我们暂时先大概了解一下其核心方法。
LINE
随机游走方法首先构造了游走序列,再基于序列进行学习,从而得到特征,这样的方法面临着两个问题:
无法处理带权图: 随机游走很难较好的融合边的权重。
缺乏明确的客观函数:Skip-gram 优化的是路径上的共现概率,而不是图拓扑结构本身的概率。
为了解决这些问题,LINE 抛弃了游走,通过定义相似度并优化概率分布的KL散度,来对齐模型的预测结果和真实数据,这两种相似度分别为一阶相似度和二阶相似度。
一阶相似度
一阶相似度描述的是图中有直接边连接的两个节点之间的局部相似性。如果节点 和 之间边的权重 很大,那么它们在向量空间中的距离就应该很近。
对于每一条无向边 ,LINE 使用 Sigmoid 函数来定义它们在低维向量空间中相连的联合概率:
其中, 为节点 的 Embedding 向量。
而在真实网络中,这对节点相连的经验联合概率为该边权重在全图权重中的占比:
其中,全图总权重 。
为了使两个分布对齐,LINE 最小化它们之间的 KL 散度 (Kullback-Leibler Divergence)。省略掉 KL 散度中与参数无关的常数项后,一阶相似度的目标函数被简化为:
二阶相似度
二阶相似度考察的是节点与邻居的关系。借鉴 NLP 领域的思想,LINE 为每个节点引入了两个角色的向量表示:作为中心节点时的向量 ,以及作为上下文(邻居)时的向量 。
给定中心节点 ,产生上下文节点 的预测条件概率通过 Softmax 函数定义:
对应地,真实网络中的经验条件概率为:
其中 ,即节点 的出度。
同样使用 KL 散度进行对齐,并且考虑到不同节点的重要性不同(度数越大的节点在网络中越重要),LINE 引入节点的度数 作为惩罚权重 ,推导出二阶目标函数:
模型训练
在分别定义了基于 KL 散度的一阶与二阶目标函数后,LINE 面临的核心问题是如何在低维向量空间中同时兼顾这两种尺度迥异的拓扑信息。理论上,可以通过引入权重超参数将两个目标函数进行线性组合,从而进行联合优化,但实现上在大规模网络中优化这两个函数不太可行。
因此,LINE选择分别训练两次以优化这两个函数。首先是一阶目标函数。在这一阶段,只看图里的直接连边,纯粹使用一阶目标函数 训练模型。经过几轮迭代,全图每个节点都获得了一个 维的向量,称之为一阶 Embedding 。
随后是二阶目标函数,这次纯粹使用二阶目标函数 训练模型。同样,每个节点又获得了一个 维的向量。称之为二阶 Embedding 。并最终将两个向量结果首尾拼接:
使用 即可完成接下来的下游任务。
小结
本文简单介绍了图的基本结构,一些指数,以及graph embedding的几个经典方法,虽然不够全面,但获取可以通过这些方法大致了解处理图的一些思想。在下一章中,我们将开始介绍图神经网络。再见。