传统图机器学习 - 咕咕鸽爱学习

传统图机器学习和特征工程

节点层面的特征工程

目的：描述网络中节点的结构和位置

eg:输入某个节点的D维向量，输出该节点是某类的概率。

节点度 (Node Degree)

定义：节点度是指一个节点直接连接到其他节点的边数。

无向图中：节点的度即为与其相邻的节点数。
有向图中：通常区分为入度（有多少条边指向该节点）和出度（从该节点发出的边的数量）。

意义：节点度直观反映了节点在网络中的直接连接能力。度高的节点通常在信息传播或资源分配中具有较大作用。

例如，在社交网络中，一个拥有大量好友的用户（高节点度）可能被视为“热门”或者“活跃”的社交人物。

节点中心性 (Node Centrality)

定义：节点中心性是一类衡量节点在整个网络中“重要性”或“影响力”的指标。其核心思想是，不仅要看节点的直接连接数，还要看它在网络中的位置和在信息流动中的角色。

常见的指标：

介数中心性 (Betweenness Centrality)：衡量节点位于其他节点间最短路径上的频率，反映其作为“桥梁”的作用。
接近中心性 (Closeness Centrality)：衡量节点到网络中其他节点平均距离的倒数，距离越近中心性越高。
特征向量中心性 (Eigenvector Centrality)：除了考虑连接数量外，还考虑邻居节点的“重要性”，连接到重要节点会提升自身的中心性。

举例：

假设有 3 个节点，记为 $1, 2, 3$，它们构成了一条链：

$$ 1 \; \leftrightarrow \; 2 \; \leftrightarrow \; 3 $$ 即只有边 $(1,2)$ 和 $(2,3)$，没有直接连接 $(1,3)$。

令邻接矩阵 $A$ 为：

$$ A \;=\; \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix}. $$

介数中心性（必经之地）：

$$ \displaystyle c_v \;=\; \sum_{s \neq t}\; \frac{\sigma_{st}(v)}{\sigma_{st}}, $$ 其中

$\sigma_{st}$ 表示从节点 $s$ 到节点 $t$ 的所有最短路径数；
$\sigma_{st}(v)$ 表示这些最短路径当中经过节点 $v$ 的条数；
求和一般只考虑 $s \neq t$ 且 $s \neq v \neq t$ 的情形，避免把端点本身算作中间节点。

换言之，节点 $v$ 的介数中心性就是它作为“中间节点”出现在多少对 $(s,t)$ 的最短路径上。

对 3 个节点 ${1,2,3}$，不同的 $(s,t)$ 有：

$(s,t)=(1,2)$：最短路径为 $(1,2)$。
- 路径上节点：1 → 2
- 中间节点：无 (1、2 是端点)
$(s,t)=(1,3)$：最短路径为 $(1,2,3)$。
- 路径上节点：1 → 2 → 3
- 中间节点：2
$(s,t)=(2,3)$：最短路径为 $(2,3)$。
- 路径上节点：2 → 3
- 中间节点：无 (2、3 是端点)
节点 1
- 只会出现在路径 (1,2) 或 (1,3) 的端点位置；(2,3) 的最短路径不包含 1。
- 端点不计作中间节点，所以 $\sigma_{st}(1) = 0$ 对所有 $s\neq t\neq 1$。
- 因此 $$ c_1 = 0. $$
节点 2
- 在 (1,3) 的最短路径 (1,2,3) 中，2 是中间节点。此时 $\sigma_{1,3}(2) = 1$；
- (1,2) 路径 (1,2) 中 2 是端点，(2,3) 路径 (2,3) 中 2 也是端点，因此不计入中间节点。
- 所以 $$ c_2 = \underbrace{\frac{\sigma_{1,3}(2)}{\sigma_{1,3}}}_{=1/1=1} ;=; 1. $$

接近中心性（去哪儿都近）：

$$ c_v \;=\; \frac{1}{\sum_{u \neq v} d(u,v)}, $$ 其中 $d(u,v)$ 表示节点 $u$ 与节点 $v$ 的最短路径距离。

节点1：

与节点 2 的距离：$d(1,2)=1$。
与节点 3 的距离：$d(1,3)=2$（路径 1→2→3）。
距离和：$;1 + 2 = 3.$
接近中心性：$; c_1 = \tfrac{1}{3} \approx 0.333.$

其他两节点同理。

特征向量中心性

特征向量中心性要求我们求解

$$ A\,\mathbf{x} = \lambda\,\mathbf{x}, $$ 并选取对应**最大特征值** $\lambda$ 的特征向量 $\mathbf{x}$ 来代表每个节点的中心性。

记 $\mathbf{x} = (x_1,,x_2,,x_3)^T$
这里 $x_1$ 是节点 1 的中心性值，$x_2$ 是节点 2 的中心性值，$x_3$ 是节点 3 的中心性值

方程 $A,\mathbf{x} = \lambda,\mathbf{x}$ 具体展开
$$ \begin{pmatrix} 0 & 1 & 0\ 1 & 0 & 1\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} x_1\ x_2\ x_3 \end{pmatrix} ;=; \lambda \begin{pmatrix} x_1\ x_2\ x_3 \end{pmatrix}. $$ 这意味着： $$ \begin{cases} 1.; x_2 = \lambda, x_1, \ 2.; x_1 + x_3 = \lambda, x_2, \ 3.; x_2 = \lambda, x_3. \end{cases} $$
求解最大特征值 $\lambda$ 及对应的 $\mathbf{x}$
- 通过特征多项式可知本矩阵的最大特征值为 $\sqrt{2}$。
- 最终（若需单位化）可以将向量归一化为 $$ \mathbf{x} = \frac{1}{2},\begin{pmatrix} 1 \ \sqrt{2} \ 1 \end{pmatrix}. $$
解释
- 节点 2 的得分最高（$\tfrac{\sqrt{2}}{2}\approx 0.707$），因为它连接了节点 1 和 3，两边的贡献都能“传递”到它。
- 节点 1 和 3 的得分相同且略低（$\tfrac{1}{2}=0.5$），因为它们都只与节点 2 相连。

聚类系数 (Clustering Coefficient)

定义：
聚类系数描述一个节点的邻居之间彼此相连的紧密程度。

对于某个节点，其局部聚类系数计算为：
$$ C = \frac{2 \times \text{实际邻居间的边数}}{k \times (k-1)} $$ 其中 $k$ 为该节点的度数。

意义：

高聚类系数： 表示节点的邻居往往彼此熟识，形成紧密的小团体。
低聚类系数： 则说明邻居之间联系较少，节点更多处于桥梁位置，可能连接不同的社群。

在很多网络中，聚类系数能揭示局部社区结构和节点的协同效应。

Graphlets

定义：
Graphlets 是指网络中规模较小（通常由3至5个节点构成）的非同构子图。

通过统计一个节点参与的各种 graphlet 模式的数量，我们可以构造出该节点的 Graphlet Degree Vector (GDV)。

意义：

Graphlets 能捕捉节点在局部网络结构中的精细模式，比单纯的度数或聚类系数提供更丰富的信息。
在很多应用中（如生物网络分析或社交网络挖掘），通过分析节点参与的 graphlet 模式，可以更好地理解节点的功能和在整个网络中的角色。

Graphlets 被视为网络的“结构指纹”，有助于区分功能不同的节点。

连接层面的特征工程

目的：通过已知连接补全未知连接

eg: AB之间有连接，BC之间有连接，那么AC之间是否可能有连接呢？

法一：直接提取连接的特征，把连接变成D维向量(推荐)。

法二：把连接两端节点的D维向量拼接，即上一讲的节点特征拼接（不推荐，损失了连接本身的结构信息。）

Distance-based Feature

核心思路： 用两个节点之间的最短路径长度（或加权距离等）作为边的特征，衡量节点对的“接近”程度。

Local Neighborhood Overlap

核心思路： 度量两个节点在其“一阶邻居”层面共享多少共同邻居，或者它们的邻居集合相似度如何。

Common Neighbors
$$ \text{CN}(u,v) ;=; \bigl|,N(u),\cap,N(v)\bigr|, $$ 其中 $N(u)$ 是节点 $u$ 的邻居集合，$\cap$ 表示交集。数值越大，表示两节点在局部网络中有更多共同邻居。
Jaccard Coefficient
$$ \text{Jaccard}(u,v) ;=; \frac{\bigl|,N(u),\cap,N(v)\bigr|}{\bigl|,N(u),\cup,N(v)\bigr|}. $$ 反映了两个节点邻居集合的交并比，越大则两者邻居越相似。
Adamic-Adar
$$ \text{AA}(u,v) ;=; \sum_{w ,\in, N(u),\cap,N(v)} \frac{1}{\log,\bigl|N(w)\bigr|}. $$ 共同邻居数目较多、且这些邻居本身度数越小，贡献越大。常用于社交网络链接预测。（直观理解：如果AB都认识C，且C是个社牛，那么AB之间的友谊就不一定好）

Global Neighborhood Overlap

核心思路： 不只看“一阶邻居”，还考虑更大范围（如 2 步、3 步乃至更多跳数）上的共同可达节点，或更广泛的结构相似度。

Katz 指标：累加节点间所有长度的路径并衰减；

Random Walk：基于随机游走来度量节点对的全局可达性；

Graph Embedding：DeepWalk、node2vec等，都可将多跳结构信息编码到向量表示里，再用向量相似度当作边特征。

真实情况如何编码边的特征？

在一个 边的特征工程 任务中，可以将 Distance-based Feature、Local Neighborhood Overlap 和 Global Neighborhood Overlap 等特征组合起来，形成一个完整的特征向量。

例如：对于每条边 $ (u,v) $，我们提取以下 6 种特征：

最短路径长度 $ d(u,v) $ (Distance-based Feature)
共同邻居数 $ CN(u,v) $ (Local Neighborhood Overlap)
Jaccard 系数 $ Jaccard(u,v) $ (Local Neighborhood Overlap)
Adamic-Adar 指标 $ AA(u,v) $ (Local Neighborhood Overlap)
Katz 指数 $ Katz(u,v) $ (Global Neighborhood Overlap)
Random Walk 访问概率 $ RW(u,v) $ (Global Neighborhood Overlap)

对于图中某条边 $ (A, B) $，它的特征向量可能是：

$$ \mathbf{f}(A, B) = \big[ 2, 5, 0.42, 0.83, 0.31, 0.45 \big] $$

图层面的特征工程

目的：网络相似度、图分类（已知分子结构判断是否有xx特性）

当我们要对整张图进行分类或比较（如图分类、图相似度计算等），需要将图转化为可比较的向量或特征。最朴素的想法是：

Bag-of-Node-Degrees：统计每个节点的度，然后构建一个“度分布”或“度直方图”。

例如，对图 $G$，我们计算 $\phi(G) = [,\text{count of deg}=1,\ \text{count of deg}=2,\ \dots,]$。
缺点：只关注了节点度，无法区分很多结构不同、但度分布相同的图。

为解决这个不足，人们提出了更精细的“Bag-of-*”方法，把节点周围的更丰富结构（子图、子树、图形）纳入统计，从而形成更有判别力的特征。

Graphlet Kernel

Graphlets：指小规模（如 3 节点、4 节点、5 节点）的非同构子图。
做法：枚举或随机采样网络中的所有小型子图（graphlets），并根据其类型计数出现频率。
- 比如在 4 节点层面，有 6 种不同的非同构结构，就统计每种结构出现多少次。
得到的特征：一个“graphlet type”直方图，即 $\phi(G) = \big[\text{count}(\text{graphlet}_1), \dots, \text{count}(\text{graphlet}_k)\big]$。
优点：比单纯节点度更能捕捉网络的局部模式。
缺点：当图很大时，遍历或采样 graphlet 代价较高；仅依赖小子图也可能忽略更大范围结构。

Weisfeiler–Lehman Kernel

Weisfeiler–Lehman (WL) 核是一种基于迭代标签传播的方法，用于图同构测试和图相似度计算。
核心思路：
1. 初始标签：给每个节点一个初始标签（可能是节点的类型或颜色）。
2. 迭代更新：在每一步迭代中，将节点自身标签与其邻居标签拼接后做哈希，得到新的标签。
3. 记录“标签多重集”：每次迭代会产生新的节点标签集合，可视为“节点子树结构”的某种编码。
Bag-of-Labels / Bag-of-Subtrees：
- 在每一轮迭代后，统计各类标签出现次数，累加到特征向量中。
- 相当于对节点子树或“局部邻域结构”做词袋统计。
优点：在保留更多结构信息的同时，计算复杂度相对可控。
缺点：仍然可能有一定的“同构测试”盲区；对于非常复杂的图，标签碰撞可能出现。

例子：

假设我们有一个简单的无向图，包含 4 个节点和 4 条边，结构如下：

1 — 2 — 3
    |
    4

1. 初始化标签

首先，给每个节点一个初始标签。假设我们直接用节点的度数作为初始标签：

初始标签如下：

节点 1: 1
节点 2: 3
节点 3: 1
节点 4: 1

2. 第一次迭代

在第一次迭代中，每个节点的标签会更新为其自身标签和邻居标签的拼接，然后通过哈希函数生成新的标签。

节点 1：
- 邻居是节点 2，标签为 3。
- 拼接后的标签为 (1, 3)。
- 假设哈希结果为 A。
节点 2：
- 邻居是节点 1、3、4，标签分别为 1、1、1。
- 拼接后的标签为 (3, 1, 1, 1)。
- 假设哈希结果为 B。
节点 3：
- 邻居是节点 2，标签为 3。
- 拼接后的标签为 (1, 3)。
- 假设哈希结果为 A。
节点 4：
- 邻居是节点 2，标签为 3。
- 拼接后的标签为 (1, 3)。
- 假设哈希结果为 A。

第一次迭代后的标签如下：

节点 1: A
节点 2: B
节点 3: A
节点 4: A

3. 第二次迭代

节点 1：
- 邻居是节点 2，标签为 B。
- 拼接后的标签为 (A, B)。
- 假设哈希结果为 C。
节点 2：
- 邻居是节点 1、3、4，标签分别为 A、A、A。
- 拼接后的标签为 (B, A, A, A)。
- 假设哈希结果为 D。
节点 3：
- 邻居是节点 2，标签为 B。
- 拼接后的标签为 (A, B)。
- 假设哈希结果为 C。
节点 4：
- 邻居是节点 2，标签为 B。
- 拼接后的标签为 (A, B)。
- 假设哈希结果为 C。

第二次迭代后的标签如下：

节点 1: C
节点 2: D
节点 3: C
节点 4: C

4. 停止条件

通常，WL Kernel 会进行多次迭代，直到节点的标签不再变化（即收敛）。在这个例子中，假设我们只进行两次迭代。

5.统计标签的多重集

在每次迭代后，统计图中所有节点的标签分布（即“标签多重集”），并将其作为图的特征。

初始标签多重集：
- 标签 1 出现 3 次（节点 1、3、4）。
- 标签 3 出现 1 次（节点 2）。
第一次迭代后的标签多重集：
- 标签 A 出现 3 次（节点 1、3、4）。
- 标签 B 出现 1 次（节点 2）。
第二次迭代后的标签多重集：
- 标签 C 出现 3 次（节点 1、3、4）。
- 标签 D 出现 1 次（节点 2）。

$$ \phi(G) = [\text{count}(1), \text{count}(3), \text{count}(A), \text{count}(B), \text{count}(C), \text{count}(D)]. \\ \phi(G) = [3, 1, 3, 1, 3, 1]. $$

直观理解

初始标签：只关注节点的度数。
第一次迭代：关注节点的度数及其邻居的度数。
第二次迭代：关注节点的度数、邻居的度数，以及邻居的邻居的度数。
随着迭代的进行，WL Kernel 能够捕捉到越来越复杂的局部结构信息。