面向机器学习的图论:关系的数据结构

面向机器学习的图论:关系的数据结构

本节摘要:图是关系的数据结构——如果你的数据有连接,就需要图论。社交网络、分子、知识库、引文网络、路网都是图。传统 ML 把数据当扁平表(每行独立、每特征一列),但当连接的结构要紧时,表格失败:预测用户会买什么,不仅看他的购买史,更看他朋友的购买史;预测分子是否结合蛋白,原子怎么键合比原子本身更重要——结构就是数据。图神经网络(GNN)是深度学习增长最快的领域,驱动药物发现、社交推荐、欺诈检测、知识图谱推理,而每个 GNN 都建立在同一基础上:基本图论。本节讲透四件事:① 把图表示成矩阵(邻接矩阵,使其可乘);② 遍历算法探索图结构(BFS 找最短路、DFS 找连通分量与环);③ 图拉普拉斯 L = D − A——谱图理论最重要的矩阵,其零特征值个数 = 连通分量数,最小非零特征值(Fiedler 值)量连通性,对应特征向量(Fiedler 向量)揭示最佳二分(谱聚类);④ 消息传递——每个节点收集邻居消息、聚合、更新自身,这恰是一次归一化邻接矩阵乘法,是 GCN/GAT/GraphSAGE 的核心运算。

对应原课程:Phase 01 · Lesson 21 · graph-theory(原英文 phases/01-math-foundations/21-graph-theory/docs/en.md)。前置:第 1~3 节(线性代数、矩阵)。

学习目标

阅读完本节,你应当能够:

1. 搭一个图类,支持邻接矩阵/邻接表两种表示,实现 BFS 与 DFS 遍历。
2. 算图拉普拉斯,用其特征值检测连通分量与聚类节点。
3. 实现一轮 GNN 式消息传递(归一化邻接矩阵乘法)。
4. 用 Fiedler 向量做谱聚类划分图。

一、问题与直觉

社交网络、分子、知识库、引文网络、路网都是图。传统 ML 把数据当扁平表——每行独立、每特征一列,但当连接的结构要紧时表格失败。考虑社交网络:预测用户买什么,购买史要紧,但朋友的购买史更要紧,连接承载信号。或考虑分子:预测是否结合蛋白,原子要紧,但真正要紧的是原子如何彼此键合,结构就是数据。图神经网络是深度学习增长最快的领域,驱动药物发现、社交推荐、欺诈检测、知识图谱推理,每个 GNN 都建立在同一基础上:基本图论。你需要四样东西:① 把图表示成矩阵(使其可乘);② 探索图结构的遍历算法;③ 拉普拉斯——谱图理论最重要的矩阵;④ 消息传递——让 GNN 工作的运算。

1.1 图:节点与边

图 G = (V, E) 由顶点(节点)V 与边 E 组成,每条边连两节点。

• 有向 vs 无向:无向图中边 (u,v) 表示 u 连 v 且 v 连 u;有向图中 (u,v) 表示 u 指向 v,反向不一定。
• 加权 vs 无权:无权图边只有有无;有权图每条边有数值权重(距离、代价、强度)。

1.2 邻接矩阵

邻接矩阵 A 是核心表示。对 n 节点的图:A[i][j] = 1(若有从 i 到 j 的边),否则 0。无向图 A 对称 A[i][j] = A[j][i];加权图 A[i][j] = 边(i,j) 的权重。

三角形:节点 0,1,2;边 (0,1),(1,2),(0,2)
A = [[0,1,1],
     [1,0,1],
     [1,1,0]]
​

邻接矩阵是每个 GNN 的输入,对 A 的矩阵运算对应图上的运算。

1.3 度

节点的度是连接它的边数;有向图分入度(进来的边)与出度(出去的边)。度矩阵 D 是对角阵:D[i][i] = 节点 i 的度,非对角元 0。三角形 D = diag(2,2,2)(每节点连两其他)。度告诉你节点重要性:高度=枢纽节点。网络的度分布揭示结构:社交网络服从幂律(少枢纽、多叶节点),随机图度服从 Poisson 分布。

1.4 BFS 与 DFS

两种基本图遍历算法,都需要。

广度优先搜索(BFS):先探索所有邻居,再邻居的邻居,用队列(FIFO)。BFS 在无权图找最短路——起点到任一节点的距离等于该节点首次被发现的 BFS 层级。这就是为何 BFS 用于社交网络的跳数距离。

深度优先搜索(DFS):尽量深再回溯,用栈(LIFO)或递归。DFS 用于:找连通分量(从未访问节点跑 DFS);环检测(DFS 树里的回边);拓扑排序(逆 DFS 完成序)。

1.5 图拉普拉斯

L = D − A——谱图理论最重要的矩阵。对三角形:

D = [[2,0,0],   A = [[0,1,1],   L = [[2,-1,-1],
     [0,2,0],        [1,0,1],        [-1,2,-1],
     [0,0,2]]        [1,1,0]]        [-1,-1, 2]]
​

拉普拉斯有非凡性质:

1. L 半正定,所有特征值 ≥ 0。
2. 零特征值的个数等于连通分量数——连通图恰一个零特征值,3 个不连通分量则三个零特征值。
3. 最小非零特征值(Fiedler 值)量连通性:大 Fiedler 值=图连通好,小 Fiedler 值=图有薄弱点(瓶颈)。
4. Fiedler 值的特征向量(Fiedler 向量)揭示最佳二分:正值节点一组、负值节点另一组,这就是谱聚类。

1.6 谱性质

邻接矩阵与拉普拉斯的特征值无需任何遍历就揭示结构性质。谱聚类这样工作:① 算拉普拉斯 L;② 找 L 的 k 个最小特征向量(跳过第一个,连通图时它是全 1);③ 用这些特征向量作每个节点的新坐标;④ 在这些坐标上跑 k-means。

为何有效:L 的特征向量编码图上「最平滑」的函数——连通好的节点特征向量值相似,被瓶颈分开的节点值不同,特征向量自然分离簇。随机游走联系:归一化拉普拉斯与图上随机游走有关,随机游走的平稳分布正比于节点度,混合时间(收敛多快)取决于谱间隙。

1.7 消息传递

图神经网络的核心运算。每个节点从邻居收集消息、聚合、更新自身状态:h_v^(k+1) = UPDATE(h_v^(k), AGGREGATE({h_u^(k) : u ∈ neighbors(v)}))。最简形式 AGGREGATE=mean,UPDATE=线性变换+激活:h_v^(k+1) = σ(W · mean({h_u^(k) : u ∈ 邻居(v)}))。

这其实是矩阵乘法的伪装。若 H 是所有节点特征的矩阵、A 是邻接矩阵:H^(k+1) = σ(A_norm · H^(k) · W),其中 A_norm 是归一化邻接矩阵(每行和为 1)。一轮消息传递让每节点「看到」直接邻居,两轮看到邻居的邻居,K 轮给每节点其 K 跳邻域的信息。

1.8 概念与 ML 应用

二、从零实现

完整源码见 phases/01-math-foundations/21-graph-theory/code/。

2.1 图类

class Graph:
    def __init__(self, n_nodes, directed=False):
        self.n = n_nodes; self.directed = directed
        self.adj = {i: {} for i in range(n_nodes)}
    def add_edge(self, u, v, weight=1.0):
        self.adj[u][v] = weight
        if not self.directed: self.adj[v][u] = weight
    def neighbors(self, node): return list(self.adj[node].keys())
    def degree(self, node):    return len(self.adj[node])
    def adjacency_matrix(self):
        A = np.zeros((self.n, self.n))
        for u in range(self.n):
            for v, w in self.adj[u].items(): A[u][v] = w
        return A
    def degree_matrix(self):
        D = np.zeros((self.n, self.n))
        for i in range(self.n): D[i][i] = self.degree(i)
        return D
    def laplacian(self):
        return self.degree_matrix() - self.adjacency_matrix()
​

邻接表 self.adj 高效存邻居;邻接矩阵转换用 numpy,因所有谱操作都需要它。

2.2 BFS 与 DFS

from collections import deque
def bfs(graph, start):
    visited = set(); order = []; distances = {}
    queue = deque([(start, 0)]); visited.add(start)
    while queue:
        node, dist = queue.popleft()
        order.append(node); distances[node] = dist
        for nb in graph.neighbors(node):
            if nb not in visited:
                visited.add(nb); queue.append((nb, dist + 1))
    return order, distances

def dfs(graph, start):
    visited = set(); order = []; stack = [start]
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node); order.append(node)
        for nb in reversed(graph.neighbors(node)):
            if nb not in visited: stack.append(nb)
    return order
​

BFS 用 deque 做 O(1) popleft,DFS 用 list 作栈,两者都恰好访问每节点一次——O(V+E)。

2.3 连通分量与拉普拉斯特征值

def connected_components(graph):
    visited = set(); components = []
    for node in range(graph.n):
        if node not in visited:
            order, _ = bfs(graph, node)
            visited.update(order); components.append(order)
    return components

def laplacian_eigenvalues(graph):
    L = graph.laplacian()
    return np.linalg.eigvalsh(L)          # 对称矩阵专用,升序返回
​

eigvalsh 用于对称矩阵(无向图拉普拉斯恒对称),升序返回特征值,数零即连通分量数。

2.4 谱聚类

def spectral_clustering(graph, k=2):
    L = graph.laplacian()
    eigenvalues, eigenvectors = np.linalg.eigh(L)
    features = eigenvectors[:, 1:k+1]      # 跳过全 1 的平凡特征向量
    labels = np.zeros(graph.n, dtype=int)
    for i in range(graph.n):
        labels[i] = 0 if features[i, 0] >= 0 else 1   # k=2 用 Fiedler 向量符号
    return labels
​

k=2 时 Fiedler 向量的符号把图分两簇;k>2 时在前 k 个特征向量(除平凡全 1)上跑 k-means。

2.5 消息传递

def message_passing(graph, features, weight_matrix):
    A = graph.adjacency_matrix()
    row_sums = A.sum(axis=1, keepdims=True)
    row_sums[row_sums == 0] = 1
    A_norm = A / row_sums                   # 归一化邻接矩阵(行和为 1)
    aggregated = A_norm @ features          # 每节点 = 邻居特征均值
    return aggregated @ weight_matrix       # 线性变换
​

这是一轮 GNN 消息传递:每节点新特征 = 其邻居特征加权均值,再经权重矩阵变换。堆多轮把信息传播更远。

三、框架对比

用 networkx 与 numpy,同样操作是一行:

import networkx as nx
G = nx.karate_club_graph()
A = nx.adjacency_matrix(G).toarray()
L = nx.laplacian_matrix(G).toarray()
eigenvalues = np.linalg.eigvalsh(L.astype(float))
print(f"最小特征值: {eigenvalues[:5]}")
print(f"连通分量: {nx.number_connected_components(G)}")
communities = nx.community.greedy_modularity_communities(G)
pr = nx.pagerank(G)
​

networkx 用优化 C 后端处理任意大小图,生产用它;用从零实现理解它在做什么。

numpy 谱分析:

A = np.array([[0,1,1,0,0],[1,0,1,0,0],[1,1,0,1,0],[0,0,1,0,1],[0,0,0,1,0]])
D = np.diag(A.sum(axis=1)); L = D - A
eigenvalues, eigenvectors = np.linalg.eigh(L)
fiedler = eigenvectors[:, 1]                # Fiedler 向量
group_a = np.where(fiedler >= 0)[0]
group_b = np.where(fiedler < 0)[0]
​

Fiedler 向量做重活——正项一簇、负项一簇,无需迭代优化,一次特征分解即可。GCN(Kipf & Welling 2017)的图卷积用带自环的邻接矩阵  = A + I:H^(l+1) = σ(D̂^(-1/2)·Â·D̂^(-1/2)·H^(l)·W^(l)),自环让每节点聚合时包含自身特征,这正是带对称归一化的消息传递,与对称拉普拉斯 L_sym = I − D^(-1/2)·A·D^(-1/2) 紧密相关——理解拉普拉斯就是理解 GCN 为何有效。

四、可复用产物

• outputs/skill-graph-analysis.md:一份分析图结构数据的技能参考,含何时用谱聚类、何时用消息传递、如何读拉普拉斯特征值。

源码见 phases/01-math-foundations/21-graph-theory/code/。

五、练习

1. (Easy) 从零实现 PageRank:从均匀分数开始,每步 score(v) = (1-d)/n + d·Σ(score(u)/out_degree(u))(对所有指向 v 的 u),用 d=0.85,跑到收敛(变化<1e-6),在小网页图上测试。
2. (Medium) 谱聚类找社区:造两个明显分离的簇图(如两个团被单边相连),跑谱聚类验证找到正确划分;增加跨簇边时会发生什么?
3. (Medium) 实现 Dijkstra 算法求加权图最短路,在同一图(均匀权重)上与 BFS 比较结果。
4. (Hard) 搭 2 层消息传递网络:用不同权重矩阵应用消息传递两次,证明 2 轮后每节点有其 2 跳邻域信息。
5. (Hard) 分析真实图:用空手道俱乐部图(34 节点、78 边),算度分布、拉普拉斯特征值、谱聚类,把谱聚类结果与已知真值划分比较。

本节要点回顾

1. 图 G=(V,E) 编码成对关系——社交、分子、知识库、路网;有向/无向、加权/无权。
2. 邻接矩阵 A 是 GNN 输入:无向图 A 对称,加权图 A[i][j]=权重;度矩阵 D 对角。
3. BFS 用队列找无权图最短路(社交跳数),DFS 用栈找连通分量、环、拓扑排序。
4. 图拉普拉斯 L = D − A 是谱图理论核心:零特征值数=连通分量数,Fiedler 值量连通性。
5. Fiedler 向量做谱聚类:正值一簇、负值一簇,无需迭代优化,一次特征分解。
6. 消息传递是 GNN 核心运算:H^(k+1) = σ(A_norm·H^(k)·W),一轮让节点看到邻居,K 轮看到 K 跳邻域。
7. 消息传递是矩阵乘法伪装:归一化邻接矩阵乘特征矩阵,GCN/GAT/GraphSAGE 都基于此。
8. GCN 用带自环的对称归一化 D̂^(-1/2)·Â·D̂^(-1/2),与对称拉普拉斯紧密相关——懂拉普拉斯就懂 GCN。
9. 度分布揭示网络结构:社交网络幂律(少枢纽多叶)、随机图 Poisson。
10. 生产用 networkx,从零实现用于理解底层——谱分析、PageRank、社区检测都是 numpy 一行。

最后一节,我们把随机性加上时间维度——随机过程:随机游走、马尔可夫链、布朗运动、Langevin 动力学、MCMC,以及扩散模型如何用逆马尔可夫链生成数据。