CS224W之二:传统的图机器学习

本文最后更新于:几秒前

这是CS224W课程的第二篇,主要内容是传统的图机器学习方法

前言

回顾图机器学习的主要任务包括以下几个部分:节点层级的预测、连接层级的预测、图层级的预测。在传统的流程中,主要是从上述层级中设计特征后再从训练数据中获得特征,这也是遵循了传统机器学习的路子:训练模型-应用模型。从中可以看出,需要构建出有效的特征来达到较好的模型性能,而传统的机器学习使用的是手工设计的特征来实现节点、连接、图层级的预测,为了尽可能说明问题,这里主要集中在无向图中。 图机器学习的目标是依据一组对象的集合进行预测。为此,可以做出以下假设,对于特征,可以定义为一个\(d\)维的向量;对于节点、边、节点集合、边集合都可以定义为对象;那有了这样的定义后,那对于节点层级的预测问题可以形式化表示为:对于给定的\(G=(V,E)\),需要学习一个函数\(f:V\rightarrow \mathbb{R}\)可以根据给定的节点结合\(V\)找到关联关系,那如何学习这个关系呢?下面分别从不同的层级来进行介绍。

节点层级

目标是实现表征网络中节点结构和位置,例如:节点度数、节点中心性、聚类系数、非同构子图单元(Graphlet)等。 其中节点\(v\)的度数\(k_v\)是指这个节点所包含的边数,这个时候并未考虑节点的重要性,而节点\(v\)的中心性\(c_v\)则进一步考虑了这点。

特征向量中心性

这个中心性定义认为一个重要的节点\(v\)周边应当环绕着一些重要的节点\(u\in N(v)\),那节点的中心性则可以用周边节点的中心性平均值来度量,即 \[c_v=\frac{1}{\lambda}\sum_{u\in N(v)}c_u,\]其中\(\lambda\)是归一化常数,一般是邻接矩阵的最大的特征值。注意到这个问题实际上是一个递归问题,即计算当前节点之前要计算周边节点,这样的形式实际上是无解的。但换个写法表示的话即可变为\[\lambda c=Ac,\]其中\(A\)是邻接矩阵(\(A_{uv}=1\),如果\(u\in N(v)\)),\(c\)是所有节点的中心性向量,\(\lambda\)是特征值,依据Perron-Frobenius定理,\(\lambda_{max}\)总是正值且唯一,那就可以相应的计算出对应的\(c_{max}\)1

介数中心性

这个中心性认为一个节点如果在其他节点最短路径之间出现次数越多越重要。可以表示为\[c_v=\sum_{s\neq v\neq t}\frac{s和t最短路径中包含v的数量}{s和t最短路径数}\]例如: 介数中心性

接近中心性

这个中心性认为一个节点如果到其他节点的路径越短越重要,形式化表示为\[c_v=\frac{1}{\sum_{u\neq v}u和v之间的最短距离}\]例如: 接近中心性

聚类系数

这个主要是来度量\(v\)的节点相邻情况,即这个点的相邻点之间有多少是两两互通的比值2,可以用如下公式表示:\[e_v=\frac{相邻节点之间的边数}{相邻节点组合数}=\frac{相邻节点边数}{C_{k_v}^2}\] 例如: 相邻节点

Graphlet

从聚类系数开始往后,仔细观察可以发现,实际上相邻节点边数就是包含目标节点的三角形的数量,例如上图的中间部分,这样的三元组被称之为Graphlet(当然还有其他形式)。 Graphlet

这个词,我没找到合适的翻译来对应,有的人翻译为图基元,有的翻译为图元。更多是直接用Graphlet,意思就是图的核心组成部件。

这个定义的目的在于描述节点\(u\)周边的图网络结构情况。在此基础上,学者定义了2-5个节点的所有异构子图,共有73个模板,例如右上角的图就有0,1,2,3,5,10,11,...等情况。 示意图

Graphlet Degree Vector (GDV)

是在Graphlet的基础上定义的子图出现的次数,注意此处是指非同构子图必须包含关注的节点,且必须完全符合,子图包含的不可有多余的边,例如下图中虽然有c这种情况存在,但是在删除了多余边后和b是重复的,所以是没有c这种情况的。3 GDV

连接层级

在连接层级的主要目标是基于已有的连接来预测新的连接,验证时节点对将会进行排序,并取前K个节点对作为预测结果,这里的关键在于设计好键值对的特征。

链路的预测有两种形式:(1)随机擦除边,并训练模型预测出这个边;(2)给定一个图\(G[t_0,t'_0]\),随着时间的流转会有不同变化,逐渐变为\(G[t_1,t'_1]\),具体实施时,可以通过计算两个节点之间的分数\(c(x,y)\)并排序,选择前\(n\)个键值对作为新的连接从而预测\(t_1\)时刻的节点。

连接层级的特征可以从基于距离的特征、局部邻域重合和全局邻域重合来概述。

基于距离的特征

就是两点之间距离最短的长度。 距离特征

局部邻域重合

获取某两个节点的共同邻居数,可以从常规邻居数、杰卡德系数、AA指标(Adamic-Adar index)来分别度量。 局部邻域重合

全局邻域重合

局部邻域重合存在局限,即,当两个节点没有任何共同邻居时值总为0。但是这两个点还是有可能在将来产生连接的,为此从全图的角度提出了全局邻域重合。

这里引入Katz index指标,主要通过计算给定节点之间所有路径的长度。具体实施时,使用邻接矩阵的k次幂来实现,例如下图\(A_{uv}^1=P_{12}^{(1)}\)的即是一个全局邻域重合之一 使用邻接矩阵的幂来计算 以此类推,可以得到长度为2的即是2次幂,相应的,可以继续获得更高的幂值。 二次幂 那l次幂的结果\(A_{uv}^l\)即是节点\(u,v\)经过了\(l\)步可以到达的。 因此Katz index计算公式为:\[S_{v_1 v_2}=\sum_{l=1}^{\infty}\beta^l \mathbf{A}_{v_1 v_2}^l,\]用以计算 \(v_1,v_2\)之间的距离,其中\(\beta\)会给距离较长的节点路径以更小的权重。可以通过以下解析解来求得: \[S=\sum_{i=1}^{\infty}\beta^i\mathbf{A}^i=(\mathbf{I}-\beta\mathbf{A})^{-1}-\mathbf{I},\]其中\(\mathbf{I}\)是单位阵。 推导过程如下:

实际上 \(S=\beta\mathbf{A}+\beta^2\mathbf{A}^2+\beta^3\mathbf{A}^3+...\) 那么对于 \((\mathbf{I}-\beta\mathbf{A})(\mathbf{I}+S)\) \(=(\mathbf{I}-\beta\mathbf{A})(\mathbf{I}+\beta\mathbf{A}+\beta^2\mathbf{A}^2+\beta^3\mathbf{A}^3+...)\) \(=(\mathbf{I}+\beta\mathbf{A}+\beta^2\mathbf{A}^2+\beta^3\mathbf{A}^3+...)-(\beta\mathbf{A}+\beta^2\mathbf{A}^2+\beta^3\mathbf{A}^3+...)\) \(=\mathbf{I}\) 则:\(\mathbf{I}+S=(\mathbf{I}-\beta\mathbf{A})^{-1}\) 故:\(S=(\mathbf{I}-\beta\mathbf{A})^{-1}-\mathbf{I}\)

图层级特征和图核

图层级的特征是为了获得全图的结构特征。

核方法是一类广泛用于图层级预测的传统机器学习方法。核心思想是设计核而不是特征向量。假定使用核\(K(G,G')\in \mathbb{R}\)来度量两个数据的相似性,核矩阵\(\mathbf{K}=(K(G,G'))_{G,G'}\)需为半正定矩阵,存在特征表示\(\phi(\cdot)\)使得\(K(G,G')=\phi(G)^T\phi(G')\),这里其实可以类比卷积核。

半正定矩阵 4

图核

图核的目标是计算两个图的相似性,常见的有Graphlet核和WL核(Weisfeiler-Lehman kernel)。其目标就是设计出一个图特征向量\(\phi(G)\),核心思想是图词袋,即将图视作一个句子,节点视作单词,图核就是从这个“句子”中提取特征,但这个要比节点度数复杂精密的多。

Graphlet 特征

顾名思义就是通过Graphlet来度量特征,主要是计算图中不同Graphlet的数量。但这里的Graphlet和节点层级的定义有所不同:(1)Graphlet的节点可以不用完全连接,可以存在离散点;(2)这里的Graphlet没有根 图层级的Graphlet 假设对于节点数为\(k\)的图有对应的Graphlet列表为\(\mathcal{G}_k=(g_1,g_2,...,g_{n_k})\),可以进一步定义GCV(Graphlet count vector), \(f_G\in\mathbb{R^{n_k}}\)为:\[(f_G)_i=\#(g_i\subseteq G),i=1,2,...,n_k\] 则对于下述示例中\(k=3\)时,GCV为\(f_G=(1,3,6,0)^T\)k=3时的Graphlet特征

Graphlet 核

它是指,在给定两个图\(G\)\(G'\)时,Graphlet核可以使用如下公式计算:\(K(G,G')=f_G^Tf_{G'}\),问题在于如果\(G\)\(G'\)的尺度不一致,那么会导致预测值区别很大,这里需要进行归一化。 需要注意的是,使用Graphlet核进行计算是耗费较大,对大小为\(n\)的图进行尺寸为\(k\)的Graphlet进行枚举时,最多需要要计算\(n^k\)5,而这个问题因为原始子图的获取是一个NP难的问题,使得该问题无法避免,如果图的节点度数是\(d\),那么计算所有\(k\)大小的Graphlet算法的复杂度为\(O(n d^{k-1})\),有没有更有效的办法呢?

WL核(Weisfeiler-Lehman Kernel)

这里引入了WL核(Weisfeiler-Lehman Kernel),这个核的目标是设计一个有效的核特征表示\(\phi(G)\),核心思想是利用相邻节点的结构来以迭代的方式丰富节点信息(词典)。一般的节点度数就是用单跳的节点度数来衡量的,而这个算法就采取了一个叫Color Refinement的算法来实现。

给定一个图\(G\)包含\(V\)个节点 1. 给每个节点\(v\)分配一个初始颜色\(c^{(0)}(v)\). 2. 递归式使用下式的改进节点颜色:\[c^{(k+1)}(v)=HASH(\{c^{(k)}(v),{c^{(k)}(u)}_{u\in N(v)}\}),\]其中HASH是把不同的输入映射到不同的颜色的函数。 3. 在\(k\)轮后,\(c^{(k)}(v)\)就是表示了\(K-hop\)的近邻结构。

分配颜色并收集周边颜色 计算哈希值 再次收集周边颜色并计算哈希值 最终会稳定得到的结果两个图的WL核特征为6最终状态

最终计算得到的结果为 结果

这个效率仅仅和边有关,因此计算的复杂度只和节点上色有关,这个也与GNN高度相关: WL核的优势


  1. 这里提到的变换,我没看懂,证明的过程还没找到依据,这个定理我也不清楚。↩︎

  2. 参考维基百科 https://zh.m.wikipedia.org/zh-cn/%E9%9B%86%E8%81%9A%E7%B3%BB%E6%95%B0↩︎

  3. 这里有个没懂的是a,b,c,d顺序是怎么定义的↩︎

  4. 半正定矩阵 https://baike.baidu.com/item/%E5%8D%8A%E6%AD%A3%E5%AE%9A%E7%9F%A9%E9%98%B5/2152711↩︎

  5. 这里没有详细的解释,不是很理解↩︎

  6. 讲实话,我没看懂这块是什么意思,怎么稳定的↩︎


CS224W之二:传统的图机器学习
https://blog.waynehfut.com/2022/07/19/CS224W-2/
作者
Hao Wang
发布于
2022年7月19日
更新于
2022年11月9日
许可协议