子图表示：从局部结构理解全图

可视化演示

子图基础概念

观察员的第一课，是学会“切豆腐”。城市有十万居民，你不可能一口吞下，但可以把目光锁定在市民小周身上：圈出他常出没的三家店、常聚的五个朋友。这一小块“熟人豆腐”，就是社交网络里的一张子图。

图论中，一张完整的图 G 由节点集合 V 和边集合 E 构成。子图 S 是从中选取一部分节点 V_s，再配上这些节点之间原有的边 E_s，组成的一个更小的图。它有一个硬性约束：E_s 里每条边的两个端点都必须属于 V_s，否则边就会“悬空”，不再是一张合法的图。

为什么研究子图？因为一张图的“性格”藏在局部拓扑里：一个人是社交达人（度很高）、挤在铁三角小团体里（聚类系数高），还是连接两大社区的桥梁（中介性高），这些身份信号只需要看他周围一小块区域就能读出。子图表示的目标，正是把这种局部拓扑模式变成机器可用的特征。

所以子图不是随手乱切的豆腐块，而是精心挑选的“社区观察窗口”。窗口切得好，一个人的社会角色乃至一座城市的性格，都能从这块小豆腐里看出门道。

子图采样策略

广场舞队有六十人，逐一面谈要花三小时；棋牌室只有二十人，二十分钟就足够。聪明的观察员绝不会对每个圈子都做全面普查，而是先抽样摸底。子图采样，就是在大图中挑出有代表性的节点和边来构成子图的过程。

最简单的是随机采样：每个节点以同等概率被选入子图。实现只需一行随机数，但缺陷明显——社交网络分布极不均匀，随机抽样的节点常常扎堆在几个“网红”聚集区，而连接两个社区的关键桥梁节点却可能被漏掉。

因此工程实践更常用邻居采样：从目标节点出发，沿着边向外扩展，有选择地保留前若干跳邻居；同时配合规模控制，例如每跳最多保留 10 个邻居，避免大 V 节点把子图撑爆。

抽样是一门手艺活：既要省钱（控制规模），又要看得准（保留关键结构）。好采样就像聪明的观察员——不贪多，但每一个样本都打在要害上。

Ego网络

盯住小周之后，观察员把他的朋友、朋友的朋友全都列了出来。这张以“我”为中心、不断向外蔓延的熟人网络，社会学里叫自我网络，图论中称为 Ego 网络。

Ego 网络的定义极其自然：给定中心节点 v 和跳数 k，它包含 v 以及所有到 v 最短距离不超过 k 的节点。k=1 时是直接好友圈，k=2 时扩展到好友的好友，层级概念与“朋友圈”完全对应。

多跳扩展会带来一个经典问题——规模爆炸。假如平均每人有 200 个好友，两跳子图就接近 4 万个节点。所以实践中 k 通常取 2 或 3，并配合上一节的采样策略控制规模。既要看得远，又不能看得太贵。

Ego 网络把抽象的“朋友圈”变成了可计算、可比较的数学对象。从此观察员的视野有了刻度：几跳，就是看得多远。

子图编码方法

圈子找好了，怎么用一句话概括“小周的圈子”？观察员提炼三个指标：圈子有多少人、平均每人认识几个、有多少铁三角。子图编码做的正是类似的事——把子图结构变成一组数字向量。

具体分两步：先提取结构特征——每个节点的度数、聚类系数、是否为中心节点；再把这些结构特征与节点自带的属性特征拼接，最后通过子图池化（READOUT）把子图内所有节点向量汇总成一个固定长度的向量。

最常见的 READOUT 是平均池化：所有节点向量逐维求平均。此外还有最大池化（保留最强信号）和求和池化（保留规模信息）。选哪种取决于任务：平均池化稳定，最大池化对极端特征敏感，求和池化则能区分圈子的大小。

编码就是给圈子画像。画像画得好不好，直接决定下游分类与预测的天花板——机器看不到圈子，只能看到向量。

全图融合机制

观察员攒了几百张圈子画像，但还要回答一个更大的问题：这座城市整体是什么气质？答案是把画像拼接起来，同时留意圈子之间的连接方式——这就是从局部到全局的融合。

常见做法是层次建模：先为每个节点提取子图表示，再通过池化把这些子图表示汇总成图级表示；或者把子图表示当作新的节点特征，送进下一层网络继续传播。无论哪种，都绕不开一个难题：不同子图的贡献不同——核心商圈的小圈子和城市边缘的孤岛，分量当然不一样。

注意力加权机制因此登场：为每个子图学习一个权重 α，重要的圈子权重高，冗余的圈子权重低；权重经 softmax 归一化后总和为 1，还自带可解释性——模型可以告诉你它最看重哪个圈子。

融合就像把散落的拼图按重要程度摆回正确位置——既保留每个朋友圈的细节，又不丢城市的大格局。

节点分类应用

画像齐了，开始猜人！观察员看小周的圈子：程序员浓度高、深夜活跃、聊天记录满是算法关键词——他是程序员的概率极高。节点分类任务就是如此：根据节点及其周边子图的特征预测标签。

只靠节点自身特征的模型（如多层感知机）只能利用孤立属性，信息稀疏得可怜；引入子图表示之后，模型同时读到“节点是谁”（自身特征）与“节点混什么圈子”（局部拓扑），分类性能显著提升。

数学上，把子图增强后的节点特征 \(h_v^{\text{local}}\) 送入一个线性分类层，再接 softmax，就得到各个类别的概率。

分类的胜负手往往不在模型多深，而在特征看得多远。子图让模型的眼光从“一个人”延伸到“一个人周围的一整张网”。

链路预测应用

小周和小李都爱去同一家深夜面馆，又都在同一个技术群潜水，却互不相识。观察员判断：两人的圈子高度重叠，他们很可能早就该认识了。这就是链路预测——预测两个节点之间是否存在或即将出现一条边。

传统方法手工计算共同好友数、Jaccard 系数等指标，依赖人工设计且覆盖不全。子图表示的做法更优雅：分别提取两个节点的 Ego 网络，编码成向量，再计算相似度作为连边得分。圈子越像，越可能连边。

相似度函数常用余弦相似度：把两个子图向量夹角的余弦值作为得分，取值区间为 [-1, 1]，实现简单且几何意义直观。配合负采样构造负样本对，就能把链路预测变成标准的二分类问题。

从两个人的朋友圈结构，推演出“尚未发生的相识”——这正是子图表示在好友推荐中大显身手的底层逻辑。

实践挑战

理想很丰满：给城市一百万人每人画一张三跳朋友圈。现实很骨感：三跳子图的平均规模以百万计，内存和算力双双告急。观察员必须做出取舍，这个取舍贯穿子图表示的全部工程实践。

第一道坎是计算效率。为每个节点提取子图都要做一次广度优先遍历，邻居数量高速膨胀。工业界常用固定规模采样：每跳只保留固定数量的邻居（比如 5 个），把子图规模钉死在常数范围。第二道坎是超参数选择：跳数 k 与采样数如何配比，需要在验证集上反复实验。

复杂度直观地看，跳数为 k、平均度为 d 时，Ego 网络规模约为 d 的 k 次方。这个指数爆炸公式是所有采样优化策略的出发点——控制了它，就控制了成本。

观察员的智慧不在于追求全知，而在于够用就好。子图表示的真谛，正是用有限的计算，换取对局部结构足够深刻的理解。

AI 应用场景

Python 演示

import networkx as nx  def extract_ego_subgraph(G, center, k):    """Extract k-hop ego subgraph around center node."""    nodes = {center}    frontier = [center]    for _ in range(k):        nxt = []        for u in frontier:            for v in G.neighbors(u):                if v not in nodes:                    nodes.add(v)                    nxt.append(v)        frontier = nxt    return G.subgraph(nodes).copy()  def encode_subgraph(subG, center):    """Encode subgraph into a vector by average pooling."""    feats = []    for node in subG.nodes():        feats.append([            subG.degree(node),            1 if node == center else 0,            nx.clustering(subG, node),            len(list(nx.common_neighbors(subG, node, center))) if node != center else 0        ])    return [sum(col) / len(feats) for col in zip(*feats)]  def predict_link_score(G, u, v, k=2):    """Predict link probability by cosine similarity of ego encodings."""    su = encode_subgraph(extract_ego_subgraph(G, u, k), u)    sv = encode_subgraph(extract_ego_subgraph(G, v, k), v)    dot = sum(a * b for a, b in zip(su, sv))    nu = sum(a * a for a in su) ** 0.5    nv = sum(b * b for b in sv) ** 0.5    return dot / (nu * nv) if nu and nv else 0.0  def main():    G = nx.karate_club_graph()    print("graph:", G.number_of_nodes(), "nodes,", G.number_of_edges(), "edges")    for center in [0, 33]:        sub = extract_ego_subgraph(G, center, 2)        vec = encode_subgraph(sub, center)        print("center", center, "| subgraph nodes:", sub.number_of_nodes(),              "| edges:", sub.number_of_edges(),              "| vector:", [round(x, 2) for x in vec])    print("link score(node0, node33):", round(predict_link_score(G, 0, 33), 4))  if __name__ == "__main__":    main()

1. def extract_ego_subgraph(G, center, k):逐层扩展邻居，提取以 center 为中心、k 跳以内的“朋友圈”子图
2. return G.subgraph(nodes).copy()调用 networkx 提取子图并复制，避免修改原图
3. nx.clustering(subG, node)计算聚类系数，度量该节点周边“铁三角”的密集程度
4. [sum(col) / len(feats) for col in zip(*feats)]平均池化：对特征矩阵逐列求均值，得到子图向量
5. dot / (nu * nv) if nu and nv else 0.0余弦相似度打分：向量夹角越小得分越高，越可能连边

常见误区

面试题