图表示学习与消息传递机制

一句话概述

图表示学习（Graph Representation Learning）是深度学习在图结构数据上的扩展。与传统深度学习处理网格结构数据（图像）或序列数据（文本）不同，图数据具有不规则的结构——节点数量可变、连接关系复杂、没有固定的顺序。图神经网络（GNN）的核心思想是"消息传递"（Message Passing）：每个节点通过聚合邻居节点的信息来更新自己的表示，经过多轮消息传递后，每个节点的表示不仅包含自身特征，还融合了局部邻域乃至全局图结构的信息。消息传递包含三个核心步骤：①消息计算（邻居节点生成消息），②消息聚合（收集邻居消息），③节点更新（结合自身和聚合消息更新表示）。这一机制统一了GCN、GAT、GraphSAGE等主流GNN架构，是图深度学习的理论基础。

💡 核心要点：①图数据不规则，需要专门的消息传递机制来学习节点表示 ②消息传递三步骤：消息计算→消息聚合→节点更新 ③多层消息传递使节点能感知多跳邻居（感受野扩大）④图表示学习输出节点嵌入、边嵌入或图级嵌入，用于下游任务

教学与演示

一、图数据与图表示学习的挑战

是什么（定义）：图（Graph）由节点（Node/Vertex）和边（Edge）组成，表示为G=(V, E)，其中V是节点集合，E是边集合。图可以是有向或无向的，边可以有权重。图表示学习的目标是学习一个映射函数f: V→R^d，将每个节点映射到一个低维向量（节点嵌入），使得图中结构相似的节点在嵌入空间中距离相近。图数据的核心挑战包括：不规则结构（不像图像有固定网格）、节点顺序无关性（置换不变性）、异质性（节点和边有多种类型）。

大白话 图就像"社交网络"。每个人是一个节点，朋友关系是边。图表示学习的目标是给每个人一个"数字画像"（向量），使得画像相似的人要么是朋友（结构相似），要么有相似的兴趣（特征相似）。挑战在于：社交网络不像照片（像素排列整齐），它的结构千奇百怪——有的人有1000个朋友，有的人只有2个；有的人在紧密的小圈子里，有的人连接着不同圈子。传统的CNN（处理整齐网格）和RNN（处理有序序列）都无法直接处理这种不规则结构。

为什么（原理）：传统深度学习无法直接处理图数据的原因有三：①CNN假设输入是规则的网格结构（如图像），图的邻域大小不固定，无法使用固定大小的卷积核；②RNN假设输入是有序的序列，图的节点没有天然顺序；③图数据需要满足置换不变性（permutation invariance）——无论节点如何编号，图的表示应该相同。GNN通过消息传递机制解决了这些问题：邻居聚合不依赖节点顺序，聚合函数可以处理任意数量的邻居。

import numpy as np

# 图数据的基本表示与挑战
# 演示图的邻接矩阵、度矩阵和特征矩阵

class GraphData:
    def __init__(self):
        pass

    def create_sample_graph(self):
        """创建一个简单的示例图"""
        # 5个节点的图
        #  0 -- 1 -- 2
        #  |    |
        #  3 -- 4
        # 邻接矩阵：A[i][j]=1 表示节点i和j之间有边
        A = np.array([
            [0, 1, 0, 1, 0],  # 节点0连接1和3
            [1, 0, 1, 0, 1],  # 节点1连接0,2,4
            [0, 1, 0, 0, 0],  # 节点2连接1
            [1, 0, 0, 0, 1],  # 节点3连接0和4
            [0, 1, 0, 1, 0],  # 节点4连接1和3
        ])

        # 节点特征矩阵：每个节点有一个d维特征向量
        # 这里每个节点有4个特征
        X = np.array([
            [0.5, 0.2, 0.1, 0.8],  # 节点0的特征
            [0.1, 0.9, 0.3, 0.2],  # 节点1的特征
            [0.3, 0.1, 0.7, 0.1],  # 节点2的特征
            [0.8, 0.1, 0.2, 0.5],  # 节点3的特征
            [0.2, 0.6, 0.1, 0.3],  # 节点4的特征
        ])

        return A, X

    def compute_degree(self, A):
        """计算每个节点的度（邻居数量）"""
        degrees = np.sum(A, axis=1)  # 对每行求和
        return degrees

    def get_neighbors(self, A, node_idx):
        """获取指定节点的邻居列表"""
        neighbors = np.where(A[node_idx] == 1)[0]
        return neighbors


graph = GraphData()
A, X = graph.create_sample_graph()

print("=== 图数据的基本表示 ===\n")

print("邻接矩阵 A（5×5）：")
print(A)

print(f"\n每个节点的度（邻居数）：{graph.compute_degree(A)}")

print("\n节点特征矩阵 X（5×4）：")
for i in range(5):
    print(f"  节点{i}: {X[i]}")

print("\n每个节点的邻居：")
for i in range(5):
    neighbors = graph.get_neighbors(A, i)
    print(f"  节点{i}的邻居: {neighbors.tolist()}")

print("\n关键观察：")
print("- 节点0有2个邻居（1和3），节点2只有1个邻居（1）")
print("- 邻居数量不固定——这是图数据区别于图像的核心挑战")
print("- CNN的固定大小卷积核无法直接应用于这种不规则结构")
print("- GNN通过消息传递机制（聚合邻居）来解决这个问题")

大白话 图就是"点+线"。点（节点）代表实体——人、商品、原子、论文；线（边）代表关系——朋友、购买、化学键、引用。邻接矩阵A是一个"关系表"——A[i][j]=1表示i和j有关系，0表示没关。特征矩阵X是"属性表"——每行记录一个节点的属性。图神经网络的输入就是这两个矩阵，输出是每个节点的"新属性"（融合了邻居信息的表示）。

什么用（应用）：图表示学习在众多领域有重要应用。社交网络：节点是用户，边是好友关系，任务包括好友推荐、社区发现、影响力预测。推荐系统：节点是用户和商品，边是交互关系（购买、点击），GNN用于学习用户和商品的嵌入。药物发现：节点是原子，边是化学键，GNN预测分子性质（如毒性、药效）。知识图谱：节点是实体，边是关系，GNN用于知识推理和问答。交通预测：节点是路段，边是连接关系，GNN预测交通流量。

哪些坑（缺点）：图表示学习的主要挑战包括：①大规模图——真实图可能有数十亿节点和边，消息传递的计算和内存开销巨大；②异质图——节点和边有多种类型，需要不同的处理方式；③动态图——图结构随时间变化，需要时序GNN；④过平滑（over-smoothing）——多层GNN会使所有节点的表示趋于相同，失去区分度。

二、消息传递机制：GNN的通用框架

是什么（定义）：消息传递（Message Passing）是图神经网络的核心计算范式。每一层消息传递包含三个步骤：①消息计算（Message）：邻居节点j根据自身特征h_j和边特征e_{ij}生成消息m_{ij} = Message(h_j, e_{ij})；②消息聚合（Aggregate）：节点i收集所有邻居的消息，通过聚合函数（如求和、平均、最大值）得到一个聚合向量a_i = Aggregate({m_{ij}: j∈N(i)})；③节点更新（Update）：节点i结合自身特征h_i和聚合消息a_i，更新自己的表示h_i' = Update(h_i, a_i)。

大白话 消息传递就像"传纸条开会"。每个节点是一个"参会者"。第一步：每个参会者写一张纸条（消息），告诉邻居"我现在的想法是XXX"。第二步：收集——每个参会者收集所有邻居递来的纸条。第三步：更新——每个参会者看自己的纸条和收集到的所有纸条，综合思考后更新自己的"想法"。这个"开会"过程重复多次（多层GNN），每开一次会，每个参会者的想法就吸收更多人的意见，最终每个人的想法都融合了整张图的信息。

为什么（原理）：消息传递框架之所以有效，是因为它抓住了图数据的关键特性——节点的信息蕴含在它和邻居的关系中。通过多层消息传递，节点可以感知到越来越远的邻居：第1层后，每个节点包含1-hop邻居的信息；第2层后，包含2-hop邻居的信息；第k层后，包含k-hop邻居的信息。这类似于CNN中感受野的扩大，但适用于不规则的图结构。

import numpy as np

# 消息传递机制：GNN的核心计算框架
# 演示消息计算、聚合、更新三个步骤

class MessagePassingLayer:
    def __init__(self, d_in=4, d_out=3):
        np.random.seed(42)
        # 消息计算权重：将邻居特征映射为消息
        self.W_msg = np.random.randn(d_in, d_out) * 0.3
        # 自环权重：处理节点自身特征
        self.W_self = np.random.randn(d_in, d_out) * 0.3
        # 偏置
        self.bias = np.zeros(d_out)

    def compute_messages(self, X, neighbors):
        """步骤1：消息计算——邻居节点生成消息"""
        messages = []
        for nbr in neighbors:
            # 消息 = 邻居特征 × 消息权重矩阵
            msg = X[nbr] @ self.W_msg
            messages.append(msg)
        return np.array(messages)

    def aggregate(self, messages, mode='mean'):
        """步骤2：消息聚合——收集并汇总邻居消息"""
        if len(messages) == 0:
            return np.zeros(self.W_msg.shape[1])
        if mode == 'sum':
            return np.sum(messages, axis=0)  # 求和聚合
        elif mode == 'mean':
            return np.mean(messages, axis=0)  # 平均聚合
        elif mode == 'max':
            return np.max(messages, axis=0)  # 最大值聚合

    def update(self, self_feat, aggregated_msg):
        """步骤3：节点更新——结合自身和聚合消息"""
        # 自身特征变换
        self_transformed = self_feat @ self.W_self
        # 结合自身和聚合消息
        new_feat = self_transformed + aggregated_msg + self.bias
        # 激活函数（ReLU）
        new_feat = np.maximum(0, new_feat)
        return new_feat

    def forward_one_node(self, X, A, node_idx):
        """对单个节点执行消息传递"""
        # 找到邻居节点
        neighbors = np.where(A[node_idx] == 1)[0]

        # 步骤1：计算消息
        messages = self.compute_messages(X, neighbors)

        # 步骤2：聚合消息
        aggregated = self.aggregate(messages, mode='mean')

        # 步骤3：更新节点
        new_feat = self.update(X[node_idx], aggregated)

        return new_feat, neighbors, messages, aggregated

    def forward_all(self, X, A):
        """对所有节点执行消息传递"""
        n = X.shape[0]
        new_X = np.zeros((n, self.W_msg.shape[1]))
        for i in range(n):
            new_X[i], _, _, _ = self.forward_one_node(X, A, i)
        return new_X


# 创建示例图
A = np.array([
    [0, 1, 0, 1, 0],
    [1, 0, 1, 0, 1],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 1, 0],
])
X = np.array([
    [0.5, 0.2, 0.1, 0.8],
    [0.1, 0.9, 0.3, 0.2],
    [0.3, 0.1, 0.7, 0.1],
    [0.8, 0.1, 0.2, 0.5],
    [0.2, 0.6, 0.1, 0.3],
])

mp = MessagePassingLayer(d_in=4, d_out=3)

# 展示节点0的消息传递过程
print("=== 消息传递机制演示 ===\n")
print("以节点0为例，展示消息传递三步：\n")

new_feat, neighbors, messages, aggregated = mp.forward_one_node(X, A, 0)

print(f"节点0的邻居: {neighbors.tolist()}")
print(f"节点0原始特征: {X[0]}")

print(f"\n步骤1 - 消息计算：")
for i, nbr in enumerate(neighbors):
    print(f"  邻居{nbr}的消息: {messages[i]}")

print(f"\n步骤2 - 消息聚合（平均）：")
print(f"  聚合后向量: {aggregated}")

print(f"\n步骤3 - 节点更新：")
print(f"  自身变换: {X[0] @ mp.W_self}")
print(f"  聚合消息: {aggregated}")
print(f"  新特征: {new_feat}")

print(f"\n更新前: {X[0]}")
print(f"更新后: {new_feat}")
print("→ 节点0的新表示融合了邻居1和3的信息！")

# 执行全图消息传递
print(f"\n\n=== 全图消息传递 ===")
new_X = mp.forward_all(X, A)
print(f"输入形状: {X.shape}")
print(f"输出形状: {new_X.shape}")
print("\n所有节点更新后的特征：")
for i in range(5):
    print(f"  节点{i}: {new_X[i]}")

大白话 消息传递就是"三步循环"。第一步：每个邻居根据自己"知道的事"写一条消息（Message）。第二步：你把所有邻居的消息收上来，汇总成一个"摘要"（Aggregate）——可以是求平均（"大家大概这么想"）、求和（"大家说的重要程度总和"）、或取最大值（"最突出的意见"）。第三步：你结合自己的"原有想法"和"邻居摘要"，形成"新想法"（Update）。重复K次，你的想法就融合了K度人脉圈的所有信息。

什么用（应用）：消息传递框架是几乎所有GNN变体的基础。GCN（图卷积网络）使用带归一化的求和聚合；GAT（图注意力网络）在聚合时对邻居加权（注意力）；GraphSAGE使用采样+聚合处理大规模图；GIN（图同构网络）使用求和聚合+MLP更新，理论上最强大。理解消息传递框架，就理解了整个GNN领域的核心思想。在PyTorch Geometric等GNN框架中，用户只需定义Message和Update函数，框架自动处理消息传递。

哪些坑（缺点）：消息传递的主要局限包括：①邻居爆炸——k层GNN需要聚合k-hop邻居，在大图中邻居数量指数增长（"邻居爆炸"问题）；②过平滑——多层后所有节点表示趋于相同（信息过度混合）；③计算效率——对每个节点聚合邻居，在大图中计算开销大。这些问题推动了GraphSAGE（采样）、简化GCN（去除非线性）等改进方向。

三、图的置换不变性与等变性

是什么（定义）：图神经网络必须满足两个重要的对称性。①置换不变性（Permutation Invariance）：图级输出（如整个图的分类标签）不随节点编号顺序改变而改变——f(P·A·P^T, P·X) = f(A, X)，其中P是置换矩阵。②置换等变性（Permutation Equivariance）：节点级输出随节点编号顺序同步变化——f(P·A·P^T, P·X) = P·f(A, X)。消息传递机制天然满足这些性质，因为聚合函数（求和、平均、最大）不关心邻居的输入顺序。

大白话 置换不变性就是"改名不影响结果"。你把社交网络中的用户重新编号（张三从1号变成5号，李四从5号变成1号），整个网络的"性质"（如社区数量、平均度数）不应该改变。GNN的输出也应该是这样——无论怎么编号，图分类结果应该一样。置换等变性就是"改名后，每个人的输出也跟着改名"——如果张三从1号变成5号，那么张三的输出也从第1行换到第5行。GNN的聚合操作（求和、平均）天然满足这些性质。

为什么（原理）：聚合函数（求和、均值、最大值）的不变性源于它们对输入顺序不敏感。Sum({a, b, c}) = Sum({c, a, b})，无论输入顺序如何，结果相同。这使得GNN在处理图数据时不需要像序列模型那样"排序"节点。这也是GNN与RNN/CNN的本质区别之一——RNN对序列顺序敏感，CNN对空间位置敏感，而GNN天然适合无序的图结构。

import numpy as np

# 图的置换不变性演示
# 证明GNN的消息传递机制对节点编号不敏感

class PermutationInvarianceDemo:
    def __init__(self):
        pass

    def simple_gnn_layer(self, X, A):
        """简化的GNN层：h_i' = ReLU(Σ_{j∈N(i)} h_j / |N(i)|)"""
        n = X.shape[0]
        new_X = np.zeros_like(X)
        for i in range(n):
            neighbors = np.where(A[i] == 1)[0]
            if len(neighbors) > 0:
                # 聚合邻居特征（平均）——不依赖邻居顺序
                new_X[i] = np.maximum(0, np.mean(X[neighbors], axis=0))
            else:
                new_X[i] = np.maximum(0, X[i])
        return new_X

    def graph_readout(self, X):
        """图级读出：对所有节点特征求平均"""
        return np.mean(X, axis=0)  # 不依赖节点顺序

    def permute_graph(self, X, A, perm):
        """对图进行节点编号置换"""
        # 置换特征矩阵的行
        X_perm = X[perm]
        # 置换邻接矩阵的行和列
        A_perm = A[perm][:, perm]
        return X_perm, A_perm


demo = PermutationInvarianceDemo()

# 原始图
A = np.array([
    [0, 1, 0, 1, 0],
    [1, 0, 1, 0, 1],
    [0, 1, 0, 0, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 1, 0],
])
X = np.array([
    [0.5, 0.2, 0.1, 0.8],
    [0.1, 0.9, 0.3, 0.2],
    [0.3, 0.1, 0.7, 0.1],
    [0.8, 0.1, 0.2, 0.5],
    [0.2, 0.6, 0.1, 0.3],
])

# 节点编号置换：0→2, 1→0, 2→4, 3→1, 4→3
perm = np.array([2, 0, 4, 1, 3])

print("=== 图的置换不变性演示 ===\n")

# 原始图的计算
new_X = demo.simple_gnn_layer(X, A)
graph_repr = demo.graph_readout(new_X)
print(f"原始图（节点编号 0,1,2,3,4）：")
print(f"  图级表示: {graph_repr}")

# 置换后的图
X_perm, A_perm = demo.permute_graph(X, A, perm)
print(f"\n置换后（节点编号 2,0,4,1,3）：")
print(f"  新邻接矩阵：")
print(A_perm)

new_X_perm = demo.simple_gnn_layer(X_perm, A_perm)
graph_repr_perm = demo.graph_readout(new_X_perm)
print(f"  图级表示: {graph_repr_perm}")

# 验证置换不变性
print(f"\n图级表示是否相同？{np.allclose(graph_repr, graph_repr_perm)}")
print("→ 图级输出不变！这就是置换不变性")

# 验证置换等变性（节点级输出）
print(f"\n原始节点级输出（节点0-4）：")
for i in range(5):
    print(f"  节点{i}: {new_X[i]}")
print(f"\n置换后节点级输出（重新编号后）：")
for i in range(5):
    print(f"  新节点{i}: {new_X_perm[i]}")
print(f"\n节点级输出同步变化：新节点{i}的输出 = 原节点{perm[i]}的输出")
print("→ 这就是置换等变性！")

大白话 置换不变性就是"编号不重要"。一个班级的同学，你按学号排、按身高排、按名字排——不管怎么排，这个班级的"平均成绩"（图级表示）是一样的。置换等变性就是"编号变了，输出跟着编号走"——你按学号排，张三的输出在第3行；你按身高排，张三的输出跑到第5行——输出内容没变，只是位置跟着编号变了。GNN天然满足这些性质，这也是它能处理图的根本原因。

什么用（应用）：置换不变性/等变性是GNN应用于图数据的理论基础。在分子性质预测中，无论原子如何编号，分子的毒性预测结果应该相同（不变性）。在节点分类中，节点编号改变，分类结果应该跟着改变（等变性）。这些性质确保了GNN的预测不会因为数据预处理中的编号方式不同而产生不一致的结果。

哪些坑（缺点）：虽然置换不变性是GNN的优势，但它也限制了GNN的表达能力。例如，GNN无法区分某些非同构图（如两个不同构的图，但具有相同的计算树），这被称为GNN的表达能力上限（不超过1-WL测试）。GIN（图同构网络）通过使用求和聚合+MLP达到了1-WL测试的上限。此外，在需要利用节点顺序信息的任务中（如代码解析），置换不变性反而成为限制。

概念关系图谱

重点答疑

Q1: 为什么CNN不能直接用于图数据？

CNN的三个核心假设在图数据上不成立：①规则网格——图像像素排列在固定网格上，但图的邻居数量不固定（节点0有2个邻居，节点1有4个邻居）；②平移不变性——CNN的卷积核在所有位置共享，因为图像特征（如边缘）在任意位置含义相同，但图中不同节点的邻居结构可能完全不同；③局部性——CNN的卷积核有固定大小（如3×3），但图的邻居集合大小不固定。GNN通过消息传递（聚合邻居）解决了这些问题。

Q2: 消息传递的聚合函数（求和、平均、最大）各有什么优劣？

求和：保留邻居数量信息（度信息），表达能力最强，但可能导致数值不稳定（度大的节点数值过大）。平均：归一化邻居信息，数值稳定，但丢失度信息。最大：只保留最显著特征，计算简单，但丢失大部分信息。GIN论文证明：求和聚合+MLP更新可以达到1-WL测试的表达能力上限，而平均和最大聚合的表达能力较弱。

Q3: 为什么多层GNN会导致过平滑（over-smoothing）？

每层消息传递相当于对节点特征做了一次"平滑"（邻居特征的平均）。多层后，每个节点的特征被反复平均，最终所有节点的特征趋于相同——就像在一张纸上反复涂抹，最终所有颜色都变成灰色。数学上，多层GNN等价于图拉普拉斯矩阵的幂迭代，最终收敛到图的主特征向量。缓解方法包括：残差连接（保留原始特征）、层数限制（通常2-3层）、跳跃连接（结合不同层的输出）。

章节单词汇总