CS224W | Machine Learning with Graphs

传统基于特征的方法｜Traditional Feature-base Methods

节点中心性｜Node Centrality

特征向量中心度｜Eigenvector centrality

衡量节点重要性的一种中心性指标，不仅考虑节点的直接连接数量，还考虑其相邻节点的重要性。特征向量中心性通过计算图的邻接矩阵的主导特征向量（最大特征值对应的特征向量）来确定，每个节点的中心性得分与其邻居的得分成正比。这种方法可用于识别网络中影响力较大的节点，如社交网络中的关键人物或传播网络中的核心节点。

思想：对于节点v，如果v被重要的邻居节点$u\in N(v)$包围，那么这个节点就相对重要

$$c_v = \frac{1}{\lambda} \sum_{u \in N(v)}c_u \longleftrightarrow \lambda \mathbf{c} = \mathbf{Ac}$$

其中：

• $\lambda$是某个正常量
• A是邻接矩阵，且若$u\in N(v), A_{uv} = 1$
• c为中心性向量(Centrality vector)

最大的特征值$\lambda_{max}$总是正数且唯一

主导特征向量 $C_max$用于衡量图的中心性。

中介中心性｜Betweenness Centrality

衡量一个节点在图中充当其他节点之间“桥梁”作用的程度。具体而言，它表示该节点出现在所有最短路径中的频率，数值越高，说明该节点在信息传递或网络流动中的重要性越大。

思想：如果许多的最短路径都经过这个节点，那么这个节点就相对重要

公式具体如下：

$$c_v = \sum_{s\neq v \neq t}\frac{在s和t之间包含节点v的最短路径数}{在s和t中的最短路径数}$$

接近中心性｜Closeness Centrality

衡量一个节点与图中所有其他节点的平均最短路径距离的倒数。数值越高，表示该节点更容易接触到图中的其他节点，信息传播效率更高，通常用于评估节点在网络中的传播能力。

思想：如果一个节点到所有的节点的距离最小，那么这个节点相对重要

公式如下：

$$c_v = \frac{1}{\sum_{u\neq v}u和v之间最短路径的长度}$$

聚类系数｜Clustering Coefficient

针对单个节点，定义为该节点的邻居之间实际存在的边数与可能存在的最大边数之比

公式：

$$e_v = \frac{v节点的邻居节点之间的边数}{C_{k_v}^{2}}$$

其中，分母表示节点v的邻居节点两两相连得到的边数。

图元频率向量｜Graphlet Degree Vector

图元

图元（Graphlets）：指小规模的、无方向或有方向的连通子图，通常用于分析复杂网络的局部结构。图元可以帮助识别网络的模式、节点的结构角色，并用于特征提取、网络比较和生物网络分析。

• 度数计算的是节点接触多少条边
• 聚类系数计算的是节点接触多少个三角形
• GDV计算的是节点接触多少个图元

图元度向量的作用

考虑由2到5个节点组成的图元时：

• 通过分析2到5个节点的所有可能连通子图，构建一个包含73维度的向量，该向量被视为节点的特征签名，用于描述其局部拓扑结构。
• 该向量不仅考虑节点的直接邻居，还能捕捉其在最多4跳范围内的互连关系
• 图元度向量提供了比单纯的节点度（Degree）或聚类系数（Clustering Coefficient）更丰富的结构信息

链接级预测任务｜Link-Level Prediction Task

在此任务中，是基于现有的链接预测新的链接。在测试阶段，对所有的未连接节点对进行排序，并且预测最高的K个节点对。关键是设计一对节点的特征。

两种链接预测的形式：

• 随机链接缺失边：随机移除一些链接，并且尝试去预测它们
• 随时间进行链接：
  • 对于给定的图$G[t_0,t_0’]$，图的边在时间$t_0’$之前，需要产生一个对在原图中不存在的链接的排序的表，其中这些链接是被预测在$G[t_1,t_1’]$中出现
  • 评估：
    • $n=|E_{new}|$：在测试阶段$[t_1,t_1’]$新出现的边
    • 取出L中前n个元素并且计算正确的边数

通过相似性的链接预测

方法：

1. 对于每一对节点$(x,y)$，计算相似性分数$c(x,y)$
   • 例如，可以计算相同的邻居数目
2. 按照相似性分数降序排列节点对
3. 预测分数最高的n对作为新的链接
4. 查看这些链接中哪些真实存在于图$G[t_1,t_1’]$中

基于距离的特征｜Distance-Based Features

使用两个节点之间最短路径的长度

缺陷：不能捕获领域重叠的信息

局部邻域重叠｜Local Neighborhood Overlap

捕获两个节点$v_1,v_2$之间共享的邻居节点

• Common neighbors: $|N(v_1)\cap N(v_2)|$
• Jaccard’s coefficient: $\frac{|N(v_1)\cap N(v_2)|}{|N(v_1)\cup N(v_2)|}$
• Adamic-Adar index: $\sum_{u\in N(v_1)\cap N(v_2)}\frac{1}{log(k_u)}, k_u: degrees\quad of\quad node\quad u$

缺陷：当两个节点没有任何公共邻居时总为0，但是这两个节点在未来仍有可能被链接

全局邻域重叠｜Global Neighborhood Overlap

Katz index：计算一个给定的节点对中所有长度的路径的数目

方法：使用邻接矩阵的幂可以计算各种长度的路径数

• $A_{uv}$表示节点u和v之间长度为1的路径
• $A_{uv}^{l}$表示节点u和v之间长度为l的路径

对于$v_1,v_2$的Katz index计算如下：

$$S_{v_1v_2} = \sum_{l=1}^{\infty}\beta^{l}A_{v_1v_2}^{l}, 0<\beta<1:discount\quad factor$$

Katz index矩阵闭式计算：

$$\mathbf{S} = \sum_{i=1}^{\infty}\beta^i\mathbf{A}^i = (\mathbf{I} - \beta\mathbf{A})^{-1}-\mathbf{I}$$

图级别的特征｜Graph-Level Features

背景：核方法｜Kernel Methods

核方法被广泛应用于传统机器学习中的图级别预测任务。

核心思想: 设计核函数而非特征向量

• 核函数$K(G, G’)\in R$衡量数据之间的相似性
• 核矩阵$K=(K(G, G’))_{G,G’}$必须始终保持半正定(即具有非负特征值)
• 存在特征表示$\Phi(·)$使得$K(G,G’)=\Phi(G)^T\Phi(G’)$
• 一旦定义好核函数，就可以直接使用现成的机器学习模型(如核支持向量机)进行预测

图核｜Graph Kernels

核心思想是设计核函数来衡量图之间的相似性，而不是直接使用特征向量。图核方法允许在不显式构造高维特征向量的情况下，利用核函数将图映射到一个高维特征空间，并应用标准的机器学习模型（如支持向量机 SVM）进行预测。

• Graphlet Kernel
• Weisfeiler-Lehman Kernel
• Random-walk kernel
• Shortest-path graph kernel

词袋｜Bag-of-Words

为图设计特征向量$\phi (G)$，一种方法就是设计词袋（Bag-of-Words，BoW）。

词袋（BoW）：对于文本，直接对出现的单词进行计数并作为其特征，其中并没有考虑顺序的因素。

对于拓展到图上的朴素的思想就是将节点视作单词。

e.g.对于向量[1, 4, 0]，可以表示为度为1，2，3的节点分别有1，4，0个。

图元核｜Graphlet Kernel

核心思想：计算在图中的不同图元的数目，将得到的特征向量记为$\mathbf{f}_G$

对给定的图$G$，以及一个图元表

$$G_{k}=(g_{1}, g_{2},...,g_{n_k})$$

我们将图元计数得到的向量$\mathbf{f}_{G}\in R^{n_k}$定义为

$$(\mathbf{f}_G)_i = (g_i \subseteq G),i = 1,2,...,n_k$$

对于给定的两个图G,G’，图元核可以通过以下的方式进行计算：

$$K(G,G') = \mathbf{f}_{G}^{T}\mathbf{f}_{G'}$$

问题：如果G和G’拥有不同的大小，那么值将会有偏移

解决方法：将每个特征向量进行归一化

$$\mathbf{h}_{G} = \frac{\mathbf{f}_{G}}{Sum(\mathbf{f}_{G})}$$ $$K(G, G') = \mathbf{h}_{G}^{T}\mathbf{h}_{G'}$$

缺陷：计算图元开销很大。对于计算一个大小为n的图中大小为k的图元，使用枚举法需要$n^k$次。计算某图是否是另一个图的子图是NP难问题。但对于节点度数上限为$d$的图，计算大小为k的图元数目，现在存在一个$O(nd^{k-1})$的算法。

Weisfeiler-Lehman Kernel

思想：使用领域的结构来丰富节点的表示。

从Bag of node degrees提取出的信息是1-邻域的信息，使用算法Color refinement可以提取多领域信息。

颜色细化｜Color Refinement

输入：图G和节点集合V

• 对于每个节点v，给定一个初试颜色$c^{(0)}(v)$
• 通过以下公式迭代更新节点颜色，其中HASH将不同的输入映射到不同颜色：

$$c^{(k+1)}(v) = HASH(\{c^{(k)}(v),\{c^{(k)}(u)\}_{u\in N(v)}\})$$

• 通过K步颜色更新，$c^{K}(v)$将提取出K邻域的结构信息

WL Kernel的优势

WL kernel计算效率很高，因为每次更新的时间复杂度都是线性的。而计算核值的时候，只有同时出现在两个图中的颜色才会被追踪。因此，颜色数目最多不会超过节点数目。计算颜色的数目的时间复杂度为线性的。因此，总的时间复杂度为线性的。

节点嵌入｜Node Embedding

假设目前拥有一个图$G$，其中

• $V$是节点集
• $A$是邻接矩阵（假设为0-1邻接矩阵）
• 为了简便起见，假设没有节点信息和额外信息
• 假设是无向图

目标：在原始网络中的相似性$similarity(u, v)\approx\mathbf{z_{v}^{T}z_{u}}$

节点嵌入学习：

1. 编码器将节点映射为嵌入
2. 定义节点相似性函数（例如用于衡量原始网络中的相似性）
3. 解码器DEC将嵌入映射为相似性分数
4. 优化编码器的参数使得$similarity(u, v)\approx\mathbf{z_{v}^{T}z_{u}}$

编码器｜Encoder

将每个节点映射到一个低维向量

$$ENC(v) = \mathbf{z}_v$$

最简单的编码

最简单的编码方法：编码仅为一个嵌入的查找

$$ENC(v) = \mathbf{z}_{v} = \mathbf{Z}\cdot v$$ $$\mathbf{Z}\in R^{d\times |V|}：矩阵，每一列是一个节点嵌入（我们需要学习/优化的目标）$$ $$v\in \mathrm{II}^{|V|}：指示向量，在一列中只有0和1，用于指示节点v$$

缺陷：参数过多，矩阵大小与节点数成正比。节点数较多的情况下运算很慢。

相似性函数｜Similarity function

指定在向量空间中的关系如何映射到原始网络中的关系

$$similarity(u,v)\approx\mathbf{z}_{v}^{T}\mathbf{z}_{u}$$

随机游走嵌入｜Random-Walk Embedding

1. 估计使用随机游走策略的决策$R$，从节点$u$出发访问节点$v$的概率
2. 优化嵌入方式来编码这些随机游走的概率

优化的特征学习：

• 给定图$G=(V,E)$
• 目标是学习一个映射$f:u\rightarrow R^{d}: f(u) = z_{u}$
• 对数相似性目标： $$max_{f}\sum_{u\in V}logP(N_{R}(u)|\mathbf{z}_{u}),N_{R}(u)是使用策略R的节点u的一个邻居$$

对于给定的节点u，我们想要学习在随机游走的邻域$N_{R}(u)$中可预测的节点的特征表示。

随机游走优化算法

1. 从每个节点u开始在图中使用随机游走策略R走固定长度的短路径
2. 对于每个节点u得到可重集合$N_{R}(u)$（记录使用从u开始的随机游走策略访问的节点）
3. 根据给定节点$u$预测邻域$N_{R}(u)$来优化嵌入

等价的，优化目标变为

$$L = \sum_{u\in V}\sum_{v\in N_{R}(u)}-log(P(v|\mathbf{z}_u))$$

目标：优化嵌入$z_u$以最大化随机游走的可能性

使用softmax参数化$P(v|\mathbf{z}_u)$:

$$P(v|\mathbf{z}_u) = \frac{exp(\mathbf{z}_{u}^{T}\mathbf{z}_{v})}{\sum_{n\in V}exp(\mathbf{z}_{u}^{T}\mathbf{z}_{n})}$$

因此，最终的优化的目标为（时间复杂度为$O(|V|^{2})）$：

$$L = \sum_{u\in V}\sum_{v\in N_{R}(u)}-log(\frac{exp(\mathbf{z}_{u}^{T}\mathbf{z}_{v})}{\sum_{n\in V}exp(\mathbf{z}_{u}^{T}\mathbf{z}_{n})})$$

负采样｜Negative Sampling

由于原来需要优化的目标时间复杂度过高，需要对目标进近似，此处采用负采样的方法：

$$log(\frac{exp(\mathbf{z}_{u}^{T}\mathbf{z}_{v})}{\sum_{n\in V}exp(\mathbf{z}_{u}^{T}\mathbf{z}_{n})}) \ \approx log(\sigma(\mathbf{z}_{u}^{T}\mathbf{z}_{v})) - \sum_{i=1}^{k}log(\sigma(\mathbf{z}_{u}^{T}\mathbf{z_{n_{i}}})),n_{i}\sim P_{V}$$

在此过程中，对于每个探测随机采样k个负节点

其中更大的k给出的估计越具有鲁棒性，同时也会在负样例中给出更高的偏移。

实际中k取5到20。

优化方法使用随机梯度下降法。

---

参考文献｜References

1. CS224W-Video:CN,EN