【GNN原理解析】什么是图

图（Graph）是图神经网络的基础数据结构。理解图论的基本概念和数学表示，是后续学习 GCN、GAT、GraphSAGE 等模型的前提。本文从图论基础出发，系统梳理图的定义、性质、矩阵表示，以及经典的图数据集和表示格式。

一、图的形式化定义

1.1 基本定义

一个图 G 由两个集合组成：顶点集合 V 和 边集合 E，记为 G = (V, E)。

• 顶点（Vertex/Node）：图中的基本实体，通常用 v_i 表示。顶点数量记作 |V| = N。
• 边（Edge）：连接两个顶点的关系，通常用 e_ij = (v_i, v_j) 表示。边数量记作 |E| = M。

# 图的基本表示
import torch

N = 5                       # 5 个节点
edge_index = torch.tensor([ # 边的索引（COO 格式）
    [0, 1, 1, 2, 2, 3],   # 源节点
    [1, 0, 2, 1, 3, 4],   # 目标节点
])

1.2 图的分类

按方向分类：

• 无向图（Undirected Graph）：边没有方向，(v_i, v_j) = (v_j, v_i)。例如社交网络中的好友关系。
• 有向图（Directed Graph / Digraph）：边有方向，(v_i, v_j) 表示从 v_i 指向 v_j。例如 Twitter 的关注关系、引用网络。

按边的权重分类：

• 无权图（Unweighted Graph）：所有边的权重相同（通常为 1），邻接矩阵元素为 0 或 1。
• 加权图（Weighted Graph）：边有权重 w_ij，表示两个节点之间关系的强度。例如交通网络中两城市之间的距离。

按是否包含属性分类：

• 普通图：节点和边没有附加特征。
• 属性图（Attributed Graph）：每个节点有特征向量 x_i ∈ R^d。这是 GNN 最常见处理的图类型。
• 异构图（Heterogeneous Graph）：节点和边有多种类型。例如知识图谱中有人物、地点、组织等不同类型的节点。

按图的整体性质分类：

• 连通图（Connected Graph）：任意两个节点间存在路径。
• 完全图（Complete Graph）：每对节点之间都存在边，边数 M = N(N-1)/2（无向）或 M = N(N-1)（有向）。
• 二分图（Bipartite Graph）：节点可分成两个集合 U 和 V，边只存在于 U 与 V 之间。
• 树（Tree）：无环连通图，边数 M = N - 1。
• 森林（Forest）：无环图（多个树的并集）。

二、图的度与邻居

2.1 度（Degree）

• 无向图的度：节点 v_i 的度 d_i 等于与其相连的边的数量。
• 有向图的入度（In-degree）：指向节点 v_i 的边的数量，记作 d_i^{in}。
• 有向图的出度（Out-degree）：从节点 v_i 指出的边的数量，记作 d_i^{out}。

# 计算度的 Python 示例
import numpy as np

# 邻接矩阵 A (N x N), A[i][j] = 1 表示边 i→j
A = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 1, 1],
    [0, 1, 1, 0, 0],
    [0, 0, 1, 0, 0],
])

# 无向图中：度 = 每行求和（或每列求和，两者相等）
degrees = A.sum(axis=1)                    # [2, 2, 3, 2, 1]

# 有向图中：出度 = 行求和，入度 = 列求和
out_degrees = A.sum(axis=1)                # [2, 2, 3, 2, 1]
in_degrees = A.sum(axis=0)                 # [2, 2, 2, 2, 1]

# 度矩阵 D: diag(d_1, d_2, ..., d_N)
D = np.diag(degrees)

2.2 邻居（Neighbors）

节点 v_i 的邻居集合 N(i) = {v_j | (v_i, v_j) ∈ E}。

• 一阶邻居（1-hop Neighbors）：与 v_i 直接相连的节点。
• k 阶邻居（k-hop Neighbors）：从 v_i 出发经过恰好 k 条边可达的节点。
• 对于有向图，区分入边邻居和出边邻居。

邻居的概念是 GNN 中消息传递（Message Passing）的基础：GNN 的每一层将每个节点的一阶邻居特征聚合起来更新该节点的表示。

三、图的矩阵表示

3.1 邻接矩阵（Adjacency Matrix）

邻接矩阵 A ∈ R^{N×N} 是最基本的图表示：

A[i][j] = {
    1    if (v_i, v_j) ∈ E
    0    otherwise
}

对于加权图：A[i][j] = w_ij（边的权重）。

性质：

• 无向图的邻接矩阵是对称矩阵（A = A^T）。
• 邻接矩阵是稀疏矩阵：大部分元素为 0，边数 M << N^2。
• A^k 的 (i, j) 元素表示从 v_i 到 v_j 的长度为 k 的路径的数量。

3.2 度矩阵（Degree Matrix）

度矩阵 D ∈ R^{N×N} 是对角矩阵：

D[i][i] = d_i  （节点 v_i 的度）
D[i][j] = 0    （i ≠ j）

对于有向图，有入度矩阵 D^{in} 和出度矩阵 D^{out}。

3.3 关联矩阵（Incidence Matrix）

关联矩阵 M ∈ R^{N×M} 关联节点和边：

无向图：

M[i][j] = {
    1    if v_i 是边 e_j 的一个端点
    0    otherwise
}

有向图：

M[i][j] = {
     1    if 边 e_j 指向 v_i
    -1    if 边 e_j 离开 v_i
     0    otherwise
}

关联矩阵与拉普拉斯矩阵的关系：L = M · M^T（对于无向图）。

3.4 邻接表（Adjacency List）

由于邻接矩阵通常非常稀疏（空间复杂度 O(N^2)），实践中常使用邻接表：为每个节点 v_i 维护一个列表，包含其所有邻居。

# 邻接表表示
adj_list = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2],
    4: [2],
}

四、图拉普拉斯矩阵

图拉普拉斯矩阵（Graph Laplacian）是 GNN 中最重要的数学对象之一。它是谱图理论（Spectral Graph Theory）的核心，也是 GCN 中卷积操作的基础。

4.1 三种拉普拉斯矩阵

1. 组合拉普拉斯（Combinatorial Laplacian）

L = D - A

L 是半正定矩阵（所有特征值 ≥ 0），最小的特征值为 0，其重数等于图的连通分量数。

2. 对称归一化拉普拉斯（Symmetric Normalized Laplacian）

L_sym = I - D^(-1/2) A D^(-1/2)
      = D^(-1/2) L D^(-1/2)

L_sym 的元素：

L_sym[i][j] = {
    1                    if i=j and d_i > 0
    -1 / sqrt(d_i d_j)   if i≠j and (i,j) ∈ E
    0                    otherwise
}

L_sym 的特征值范围在 [0, 2] 之间。

3. 随机游走拉普拉斯（Random Walk Laplacian）

L_rw = I - D^(-1) A
     = D^(-1) L

L_rw 的元素：

L_rw[i][j] = {
    1               if i=j and d_i > 0
    -1 / d_i        if i≠j and (i,j) ∈ E
    0               otherwise
}

L_rw 与随机游走（Random Walk）的关系：L_rw 的转移矩阵 P = I - L_rw = D^(-1)A 就是经典随机游走的转移矩阵。

4.2 拉普拉斯矩阵的性质

关键性质：

1. 对称性：L（组合）和 L_sym 是对称矩阵；L_rw 通常不是对称的。

2. 半正定性：三种拉普拉斯矩阵都是半正定的。对于任意向量 x ∈ R^N：

   x^T L x = 1/2 * Σ_{(i,j)∈E} (x_i - x_j)^2

   这个二次型衡量了向量 x 在边上的平滑程度。在 GNN 中，这个性质导出”相邻节点应有相似的特征”的归纳偏差（inductive bias）。

3. 特征值与连通性：

   • λ_1 = 0 始终是一个特征值，对应的特征向量是全 1 向量（对于 L：v_1 = [1,1,…,1]^T）
   • λ_2 > 0 当且仅当图为连通图（λ_2 称为代数连通度/ Fiedler 值）
   • λ_2 越大，图越紧密连接
   • λ_k = 0 的重数 = 图的连通分量数

4. 拉普拉斯与度数：拉普拉斯矩阵的迹 tr(L) = Σ d_i = 2M。

4.3 拉普拉斯矩阵的 Python 实现

import numpy as np
from scipy.sparse.linalg import eigsh

# 构造图
N = 5
edge_index = [(0,1), (0,2), (1,0), (1,3), (2,0), (2,3), (2,4), (3,1), (3,2), (4,2)]

# 邻接矩阵
A = np.zeros((N, N))
for i, j in edge_index:
    A[i][j] = 1

# 度矩阵
D = np.diag(A.sum(axis=1))

# 度矩阵的 -1/2 次幂（处理孤立节点：d_i=0 时 d_i^(-1/2)=0）
D_inv_sqrt = np.zeros_like(D)
d = A.sum(axis=1)
for i in range(N):
    if d[i] > 0:
        D_inv_sqrt[i][i] = 1.0 / np.sqrt(d[i])

# 组合拉普拉斯
L = D - A

# 对称归一化拉普拉斯
L_sym = np.eye(N) - D_inv_sqrt @ A @ D_inv_sqrt

# 随机游走拉普拉斯
D_inv = np.zeros_like(D)
for i in range(N):
    if d[i] > 0:
        D_inv[i][i] = 1.0 / d[i]
L_rw = np.eye(N) - D_inv @ A

# 验证半正定性（特征值都 ≥ 0）
eigenvalues, _ = np.linalg.eigh(L)
print(f"组合拉普拉斯特征值: {eigenvalues}")
print(f"最小特征值 ≈ 0: {np.isclose(eigenvalues[0], 0)}")

五、谱图理论基础

5.1 图傅里叶变换

图信号 x ∈ R^N 是定义在图节点上的函数，x_i 表示节点 v_i 上的信号值。

经典傅里叶变换将时域信号分解为不同频率的正弦波；图傅里叶变换将图信号分解为拉普拉斯矩阵的不同特征向量分量。

图拉普拉斯的特征分解：

L = U Λ U^T

其中：

• U = [u_1, u_2, …, u_N]：特征向量矩阵（正交矩阵：U^T U = I），每列 u_k 是一个特征向量
• Λ = diag(λ_1, λ_2, …, λ_N)：特征值矩阵，λ_1 ≤ λ_2 ≤ … ≤ λ_N

图傅里叶变换（Graph Fourier Transform）：

x̂ = U^T x      // 将图信号 x 变换到谱域

逆图傅里叶变换（Inverse Graph Fourier Transform）：

x = U x̂         // 将谱域信号变换回空间域

物理直觉： 小的特征值 λ_k 对应的特征向量 u_k 在图上变化缓慢（低频信号），大的特征值对应的特征向量震荡剧烈（高频信号）。图傅里叶变换将一个图信号分解为不同”频率”分量的加权和。

5.2 谱域卷积

在图谱域中，卷积操作定义为：

x * G g = U ((U^T g) ⊙ (U^T x))
        = U g_θ(Λ) U^T x

其中 g_θ(Λ) = diag(θ_1, θ_2, …, θ_N) 是可学习的谱域滤波器参数。

这一定义是 GCN（Graph Convolutional Network）的数学基础。GCN 的不同变体对此进行了各种简化和近似：

• **Bruna et al. (2014)**：直接学习 g_θ(Λ) 的对角元素（参数量 O(N)，不局部化）
• **Defferrard et al. (2016, ChebNet)**：使用切比雪夫多项式近似 g_θ，避免特征分解
• **Kipf & Welling (2017, GCN)**：一阶近似 + 重归一化技巧，把 g_θ 简化为一个可学习参数

这个内容将在《图信号处理与图卷积神经网络》中详细展开。

六、经典图数据集

6.1 引文网络数据集

这三个是 GNN 论文中最常使用的基准数据集：

数据集	节点数	边数	特征维数	类别数	说明
Cora	2,708	5,429	1,433	7	机器学习论文引文网络
CiteSeer	3,327	4,732	3,703	6	计算机科学论文引文网络
PubMed	19,717	44,338	500	3	医学论文引文网络（规模较大）

这些数据集的共同特点：

• 节点代表学术论文
• 边代表引用关系（有向，但通常建模为无向图）
• 每个节点的特征是词袋向量（Bag of Words），表示论文中某些关键词是否出现
• 任务：半监督节点分类（已知少量节点的标签，预测其余节点的标签）

6.2 OGB（Open Graph Benchmark）

OGB 是斯坦福大学发布的标准化图数据集基准，解决了”论文中引文网络数据集过小且测试协议不统一”的问题：

数据集	规模	任务	节点数	边数
ogbn-arxiv	中	节点分类	169,343	1,166,243
ogbn-products	大	节点分类	2,449,029	61,859,140
ogbn-proteins	中	节点分类（多标签）	132,534	39,561,252
ogbl-collab	中	链接预测	235,868	1,285,465
ogbl-ppa	大	链接预测	576,289	30,326,273

使用 OGB 进行实验时，需要遵循其标准的 train/validation/test 划分和评测协议。

6.3 其他常用数据集

• Reddit：Reddit 社区的帖子-帖子图（posts 是节点，相同用户评论连接帖子）。232,965 节点，节点分类任务（41 类）。
• PPI（Protein-Protein Interaction）：24 张人体组织蛋白质互作图，每张图约 2,372 节点，多标签节点分类（121 类）。
• QM9：分子图数据集（130k 分子），每个分子是一个图，边是化学键，节点是原子。图回归任务。
• ZINC：分子溶解度预测，约 250k 分子图，图回归任务。

七、图数据的存储格式

7.1 常见图表示格式

格式	说明	空间复杂度	使用场景
边列表（Edge List）	每行 (source, target [, weight])	O(M)	简单，扩展性好
邻接表（Adjacency List）	每个节点存储其邻居列表	O(N + M)	标准图算法
邻接矩阵	N×N 矩阵，A[i][j] = w_ij	O(N^2)	小图，密集图
COO（Coordinate）	(row, col, val) 三元组列表	O(M)	稀疏矩阵构造
CSR（Compressed Sparse Row）	row_ptr + col_ind + values	O(N + M)	高效稀疏矩阵运算
CSC（Compressed Sparse Column）	col_ptr + row_ind + values	O(N + M)	CSR 的列版本

7.2 PyTorch Geometric 的 Data 对象

import torch
from torch_geometric.data import Data

# PyG 的 Data 对象封装了图的全部信息
edge_index = torch.tensor([
    [0, 1, 1, 2, 2, 3, 3, 4],
    [1, 0, 2, 1, 3, 2, 4, 3]
], dtype=torch.long)

x = torch.tensor([
    [1.0, 0.0],    # 节点 0 的特征（2 维）
    [0.0, 1.0],    # 节点 1
    [1.0, 1.0],    # 节点 2
    [0.0, 0.0],    # 节点 3
    [1.0, 0.0],    # 节点 4
], dtype=torch.float)

y = torch.tensor([0, 1, 0, 1, 0], dtype=torch.long)  # 节点标签

data = Data(x=x, edge_index=edge_index, y=y)

print(f"节点数: {data.num_nodes}")
print(f"边数: {data.num_edges}")
print(f"节点特征维度: {data.num_node_features}")
print(f"是否有孤立节点: {data.has_isolated_nodes()}")
print(f"是否是无向图: {data.is_undirected()}")
print(f"类别数: {data.num_classes}")

7.3 从边列表构造 CSR 格式

def edge_list_to_csr(edge_index, num_nodes):
    """
    将 COO 格式的边列表转为 CSR 格式
    edge_index: (2, M) 的 tensor, edge_index[0]=源节点, edge_index[1]=目标节点
    """
    src, dst = edge_index[0].numpy(), edge_index[1].numpy()
    
    # 按源节点排序
    order = np.argsort(src)
    src = src[order]
    dst = dst[order]
    
    # 构建 row_ptr
    row_ptr = np.zeros(num_nodes + 1, dtype=np.int64)
    unique_src, counts = np.unique(src, return_counts=True)
    for node, count in zip(unique_src, counts):
        row_ptr[node + 1] = row_ptr[node] + count
    for i in range(1, num_nodes + 1):
        if row_ptr[i] == 0:
            row_ptr[i] = row_ptr[i-1]
    
    # col_ind 和 values
    col_ind = dst
    values = np.ones_like(dst)
    
    return row_ptr, col_ind, values

# CSR 格式的优势：高效地访问节点的邻居
# row_ptr[node] 到 row_ptr[node+1] 给出了节点 node 的所有邻居的区间
def get_neighbors(row_ptr, col_ind, node):
    return col_ind[row_ptr[node]:row_ptr[node+1]]

八、图的拓扑性质

8.1 聚类系数（Clustering Coefficient）

聚类系数衡量节点的邻居之间”互为朋友”的程度：

• 局部聚类系数 C_i：节点的邻居之间实际存在的边数 / 邻居之间可能存在的最大边数

  C_i = 2 * e_i / (k_i * (k_i - 1))

  其中 e_i 是节点 i 的邻居之间的边数，k_i 是节点 i 的度。

• 平均聚类系数：所有节点聚类系数的平均值，反映图的整体”抱团”程度。

社交网络通常具有高聚类系数（朋友的朋友也是朋友）。

8.2 平均路径长度（Average Path Length）

图中所有节点对之间最短路径的平均值。小世界网络具有较小的平均路径长度。

8.3 度分布（Degree Distribution）

P(k) = 图中度数为 k 的节点的比例。

• 随机网络（Erdos-Renyi）：度分布近似泊松分布。
• 无标度网络（Scale-Free Network）：度分布遵循幂律 P(k) ~ k^{-γ}。互联网、社交网络大多是无标度的。
• 无标度网络的特征：少数节点（hub）有极高的度数，多数节点度数很小。

8.4 小世界现象（Small-World）

Stanley Milgram 的六度分隔理论。小世界网络同时满足：

• 高聚类系数（像规则网络）
• 短平均路径长度（像随机网络）

这是许多真实世界网络（社交网络、Internet、生物网络）的共性。

十四、图的可视化

14.1 使用 NetworkX 可视化图

import networkx as nx
import matplotlib.pyplot as plt

G = nx.karate_club_graph()  # Zachary's Karate Club：经典社交网络数据集

plt.figure(figsize=(10, 8))
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, node_color=range(G.number_of_nodes()),
        node_size=300, cmap=plt.cm.viridis,
        with_labels=True, font_size=8)
plt.title("Zachary's Karate Club Graph")
plt.show()

14.2 t-SNE 可视化节点嵌入

from sklearn.manifold import TSNE

def visualize_embeddings(embeddings, labels, title="Node Embeddings"):
    tsne = TSNE(n_components=2, random_state=42, perplexity=30)
    embeddings_2d = tsne.fit_transform(embeddings)
    plt.figure(figsize=(10, 8))
    scatter = plt.scatter(embeddings_2d[:, 0], embeddings_2d[:, 1],
                          c=labels, cmap='tab10', s=30, alpha=0.7)
    plt.colorbar(scatter)
    plt.title(title)
    plt.show()

14.3 PyG 内置数据集加载

from torch_geometric.datasets import Planetoid, TUDataset

cora = Planetoid(root='/tmp/Cora', name='Cora')
print(f"Cora: 节点数={cora[0].num_nodes}, 边数={cora[0].num_edges}")

mutag = TUDataset(root='/tmp/MUTAG', name='MUTAG')
print(f"MUTAG: {len(mutag)} 张图, 类别数={mutag.num_classes}")

十五、总结与知识体系导航

本文建立了 GNN 所需的核心图论基础。后续文章将依次展开：表示学习（DeepWalk/Node2Vec）、神经网络基础（MLP/反向传播）、CNN（卷积如何推广到图）、图信号处理与 GCN（完整数学推导与 PyG 实现）。

掌握本文的图论基础后，你将能理解 GCN 公式中每一步操作的数学含义：D^{-1/2} A D^{-1/2} 从何而来、为什么这样做能实现图上卷积，以及图拉普拉斯矩阵的特征分解如何构成图信号处理的理论基石。

图论概念	在 GNN 中的应用
邻接矩阵 A	定义消息传递的路径：谁向谁发送消息
度矩阵 D	归一化聚合操作，平衡高度数节点和低度数节点的贡献
拉普拉斯矩阵 L	谱域卷积的基础，定义图上的卷积操作
归一化拉普拉斯 L_sym	GCN 的传播算子：H^{(l+1)} = σ( D̃^{-1/2} Ã D̃^{-1/2} H^{(l)} W^{(l)} )
邻居集合 N(i)	消息传递的聚合范围
k 阶邻居	决定了 GNN 的感受野（receptive field）：K 层 GNN 覆盖 K-hop 邻居
节点度	影响节点在接受消息时的归一化方式
连通分量	GNN 中不同连通分量之间的节点不会交换信息

---

面试/理解自查问题

Q1：邻接矩阵、度矩阵、拉普拉斯矩阵三者之间的关系？

邻接矩阵 A 记录边是否存在；度矩阵 D 记录每个节点的度数（D = diag(A 的行和)）；组合拉普拉斯 L = D - A。三种归一化拉普拉斯（对称 L_sym、随机游走 L_rw）是 L 的不同归一化形式。GCN 使用的是重归一化后的 Ã = A + I 和 D̃ = D + I 构建的 D̃^{-1/2} Ã D̃^{-1/2}。

Q2：为什么 GCN 需要有自环（self-loop）？

标准邻接矩阵 A 的对角线为 0（节点不与自身相连），而 GCN 中使用的 Ã = A + I 添加了自环。原因：1）让节点在聚合邻居特征时也保留自身的信息；2）数学上使 D̃^{-1/2} Ã D̃^{-1/2} 的特征值范围在 (-1, 1] 之间，保证数值稳定性。

Q3：对称归一化 vs 随机游走归一化在 GNN 中分别用于何处？

• 对称归一化（D^{-1/2} A D^{-1/2}）：GCN 使用，双向对称归一化（同时对发送节点和接收节点归一化），保留矩阵的对称性。
• 随机游走归一化（D^{-1} A）：GraphSAGE 的非对称归一化版本使用，每一步只归一化接收到的消息。物理意义上对应从邻居到中心节点的随机游走转移概率。

十、图的遍历与连通性

10.1 广度优先搜索（BFS）vs 深度优先搜索（DFS）

这两种遍历策略直接影响了 Node2Vec 算法中”BFS vs DFS”的权衡：

from collections import deque

def bfs(graph, start):
    """广度优先搜索"""
    visited = set([start])
    queue = deque([start])
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

def dfs(graph, start):
    """深度优先搜索"""
    visited = set()
    order = []
    
    def dfs_recursive(node):
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs_recursive(neighbor)
    
    dfs_recursive(start)
    return order

BFS 探索节点的近邻，产生局部微观视图（micro-view）；DFS 探索远离起始节点的区域，产生全局宏观视图（macro-view）。Node2Vec 通过有偏随机游走在两者之间插值。

10.2 连通分量检测

def connected_components(graph, num_nodes):
    """并查集算法检测连通分量"""
    parent = list(range(num_nodes))
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
    
    for u in graph:
        for v in graph[u]:
            union(u, v)
    
    components = {}
    for i in range(num_nodes):
        root = find(i)
        components.setdefault(root, []).append(i)
    
    return list(components.values())

在 GNN 中，不同连通分量的节点之间不会进行消息传递。处理大规模图时需要意识到这一点。

10.3 中心性度量（Centrality）

度中心性（Degree Centrality）：C_D(v) = d_v / (N-1)。直观地，度越高的节点越”重要”。

介数中心性（Betweenness Centrality）：节点在所有最短路径中出现频率越高，介数中心性越高。衡量节点在图中作为”桥梁”的重要性。

特征向量中心性（Eigenvector Centrality）：节点的中心性不仅取决于自身的度，还取决于其邻居的中心性。这是 PageRank 的前身。数学上：Ax = λx，特征向量中心性是邻接矩阵的主特征向量。

PageRank：Google 的经典算法。与特征向量中心性的关键区别在于引入了”随机跳跃”（teleport）：

PR(v) = (1-d)/N + d * Σ_{u→v} PR(u)/d_out(u)

其中 d ≈ 0.85 是阻尼系数，PR 的迭代过程对应随机游走的稳态分布。

def pagerank(adj_matrix, d=0.85, max_iter=100, tol=1e-6):
    N = adj_matrix.shape[0]
    out_degree = adj_matrix.sum(axis=1)
    out_degree[out_degree == 0] = 1  # 避免除以 0
    
    # 转移矩阵 M (列随机)
    M = adj_matrix / out_degree[:, np.newaxis]
    
    pr = np.ones(N) / N  # 初始化均匀分布
    
    for _ in range(max_iter):
        new_pr = (1 - d) / N + d * M.T @ pr
        if np.linalg.norm(new_pr - pr, 1) < tol:
            break
        pr = new_pr
    
    return pr

十一、图谱聚类

11.1 谱聚类原理

谱聚类（Spectral Clustering）利用拉普拉斯矩阵的特征向量将图划分为若干簇。其核心思想在 GNN 的池化（pooling）和数据预处理中非常重要。

谱聚类算法步骤：

1. 构造相似图（k-NN 图、ε-近邻图或全连接图）
2. 计算拉普拉斯矩阵 L（通常使用 L_sym）
3. 计算 L_sym 的前 k 个特征向量（对应最小的 k 个特征值）
4. 将这些特征向量按行组成 N×k 矩阵
5. 对矩阵的行执行 K-means 聚类

from sklearn.cluster import KMeans
from scipy.sparse.linalg import eigsh

def spectral_clustering(adj_matrix, n_clusters):
    N = adj_matrix.shape[0]
    D = np.diag(adj_matrix.sum(axis=1))
    D_inv_sqrt = np.diag(1.0 / np.sqrt(np.diag(D) + 1e-10))
    L_sym = np.eye(N) - D_inv_sqrt @ adj_matrix @ D_inv_sqrt
    
    # 计算最小的 n_clusters 个特征向量
    eigenvalues, eigenvectors = eigsh(L_sym, k=n_clusters, which='SM')
    
    # 对特征向量的行做 K-means
    kmeans = KMeans(n_clusters=n_clusters, random_state=42)
    labels = kmeans.fit_predict(eigenvectors)
    
    return labels

11.2 谱聚类与 GNN 的关系

谱聚类的特征向量嵌入与 GCN 的节点嵌入有深刻的联系：

• 谱聚类使用拉普拉斯矩阵的”最小”特征向量（低频信号）来捕捉图的宏观结构
• GCN 使用相似的谱域滤波器，但通过神经网络进行非线性变换和端到端学习
• 谱聚类是无监督的；GCN 可以通过标签进行监督学习，因此 GCN 的表现通常优于纯谱方法

十二、子图与图同构

12.1 图同构问题

图同构（Graph Isomorphism）是判断两个图在重标记节点后是否完全相同。这是一个经典的 NP-intermediate 问题（尚未证明是 P 或 NP-complete）。

在 GNN 中，图同构问题直接关系到模型的表达能力：

• Weisfeiler-Lehman (WL) 测试：一种高效的图同构启发式算法，通过迭代地聚合邻居颜色（标签）来区分非同构图
• GIN（Graph Isomorphism Network）：证明了 GNN 的表达能力上限等于 WL 测试。使用 SUM 聚合器 + MLP 可以达到 WL 测试的表达能力

12.2 WL 测试的简化实现

def wl_test(adj_matrix, node_features, iterations=3):
    """1-WL 测试的简化实现"""
    N = adj_matrix.shape[0]
    # 初始化颜色（哈希映射）
    colors = {i: hash(str(node_features[i].tolist())) for i in range(N)}
    
    for _ in range(iterations):
        new_colors = {}
        for i in range(N):
            # 聚合邻居颜色
            neighbor_colors = sorted([
                colors[j] for j in range(N) if adj_matrix[i][j] == 1
            ])
            # 更新颜色 = hash(自身颜色, 邻居颜色集合)
            signature = str(colors[i]) + str(neighbor_colors)
            new_colors[i] = hash(signature)
        colors = new_colors
    
    return colors

WL 测试的局限性：无法区分某些规则图（如两个大小相同但结构不同的正六边形 vs 两个分离的三角形）。这对应了 GNN 的表达能力上限——基于消息传递的 GNN 无法区分 WL 测试无法区分的图。

十三、图数据增强

在 GNN 训练中，数据增强是提升模型泛化能力的重要技术：

13.1 边扰动（Edge Perturbation）

随机删除或添加一定比例的边，使模型对噪声更具鲁棒性：

def drop_edges(edge_index, drop_rate=0.1):
    """随机丢弃边（DropEdge 策略）"""
    num_edges = edge_index.shape[1]
    mask = torch.rand(num_edges) > drop_rate
    return edge_index[:, mask]

13.2 节点特征掩码（Feature Masking）

类似 BERT 的 MLM 预训练任务，随机遮蔽部分节点的特征，训练 GNN 重构被遮蔽的特征：

def mask_features(x, mask_rate=0.15):
    """随机遮蔽特征"""
    mask = torch.rand(x.shape[0]) > mask_rate
    masked_x = x.clone()
    masked_x[~mask] = 0  # 用 0 填充被遮蔽的特征
    return masked_x, mask

13.3 子图采样（Subgraph Sampling）

对于大规模图，训练时随机采样子图可以降低内存消耗并提供正则化效果：

def sample_subgraph(edge_index, num_nodes_to_sample, num_nodes):
    """从图中随机采样子图"""
    sampled_nodes = torch.randperm(num_nodes)[:num_nodes_to_sample]
    mask = torch.isin(edge_index[0], sampled_nodes) & torch.isin(edge_index[1], sampled_nodes)
    return edge_index[:, mask], sampled_nodes

十四、总结

图神经网络将深度学习从欧几里得空间（图像、文本、语音）拓展到了非欧几里得的图结构空间，极大扩展了深度学习的应用边界。本文从图的基本定义出发，系统覆盖了：

1. 图的数学基础：邻接矩阵、度矩阵、拉普拉斯矩阵及其归一化形式，它们是 GNN 理论的基石。
2. 消息传递范式：GNN 的核心计算模型——每个节点聚合邻居信息后更新自身表示。
3. 经典模型族：GCN（谱域卷积的一阶近似）、GraphSAGE（归纳式邻居采样）、GAT（注意力权重聚合）、GIN（表达能力极限分析）。
4. 训练与部署实践：直推式 vs 归纳式学习、节点/边/图层面的任务设计、PyG 框架加速技巧。
5. 前沿训练策略：对比学习、特征掩码、子图采样等自监督预训练方法。

图神经网络仍然在快速发展中——从更深的 GCN（GCNII、ResGCN）到等变 GNN（SE(3)-Transformers），从异质图到动态图，每个方向都在推动图学习的边界。对于实践者而言，关键是理解图数据的特性（同质性/异质性、规模、归纳需求），选择合适的模型和训练策略，并在真实场景中验证图结构是否真正贡献了信息。

参考

• Kipf & Welling, “Semi-Supervised Classification with Graph Convolutional Networks”, ICLR 2017
• Hamilton et al., “Inductive Representation Learning on Large Graphs”, NeurIPS 2017
• Veličković et al., “Graph Attention Networks”, ICLR 2018
• Xu et al., “How Powerful are Graph Neural Networks?”, ICLR 2019
• PyG (PyTorch Geometric): https://pyg.org
• DGL (Deep Graph Library): https://dgl.ai