前言
六边形结构和两个三角形拼接的结构，人眼看起来完全不一样。但有些图神经网络，就是分辨不出这两张图。原因和模型大小、数据多少都没关系。
一、节点没有固定顺序
一张图，换一种节点编号，结构没变，但邻接矩阵完全不同。直接扔给普通神经网络，模型会认为这是两张完全不同的图。
图神经网络要解决这个问题，需要满足置换不变性——节点编号怎么换，输出结果都不变。消息传递是最直接的做法：不依赖节点全局顺序，只通过邻居之间的局部信息交换来学习。
二、消息传递：每个节点都是被蒙住眼睛的传话人
想象你是一个节点，被蒙住眼睛，只能和直接相连的邻居说话，看不到整张图。每轮游戏你做三件事：听邻居说什么，把信息合并成一条，然后更新自己的状态再告诉别人。
每一层网络，就是一轮传话。节点的特征向量，就是它的身份标签。GCN、GAT、GIN 都跳不出这个框架，只能靠邻居传过来的信息定位自己，没有俯视全局的上帝视角。
三、1-WL 算法：给图做同构测试
在说 1-WL 之前，先说清楚图同构：两张图本质上一模一样，只是节点编号不同。
1-WL（Weisfeiler-Leman 算法，1968 年）是一种判断图同构的方法，思路是给节点染色：
- 初始染色：每个节点根据自身特征（通常是度数）获得一个初始颜色
- 迭代更新：每轮每个节点的新颜色，由自身颜色加上所有邻居颜色的多重集决定（不排序，只记录每种颜色出现几次）
- 终止：颜色分布稳定后停止
- 结论：两张图颜色分布不同，一定不同构；相同，仅可能同构（1-WL 无法保证 100% 正确）
1-WL 有个经典的盲区：
- 图 A：6 个节点连成的正六边形
- 图 B：两个独立的三角形拼在一起
人眼能看出差异，但 1-WL 每轮算出来的颜色分布都一样，区分不了。两种结构里，每个节点的度数都是 2，邻居颜色分布完全一致。
四、1-WL 为什么能限制消息传递 GNN
消息传递 GNN 的每一层，和 1-WL 的每一轮，做的事是一样的。
1-WL 用「自身颜色 + 邻居颜色多重集」给节点打标签，消息传递 GNN 用「自身特征 + 邻居特征聚合」生成节点向量。区别只在于实现方式：前者离散，后者可微。
所以：1-WL 区分不了的图，纯消息传递 GNN 大概率也区分不了。
五、GIN 为什么能摸到上限
GIN（Graph Isomorphism Network，ICLR 2019）是第一个在理论上达到 1-WL 上限的消息传递 GNN，设计思路是「求和 + MLP」。
GIN 能做到这样，靠的是单射——两个不同的邻居集合，聚合后结果必须不同。
GCN 和 GAT 做不到单射。GCN 的归一化均值会抹掉邻居的数量信息：{1,3} 和 {2,2} 均值都是 2，但结构不一样。最大池化也有类似问题：{1,5} 和 {3,5} 最大值都是 5，区分不开。
GIN 用求和配合 MLP 解决了这个问题。求和不主动丢弃信息，MLP（足够宽时）可以把相近的结果映射到完全不同的向量空间，两者配合实现了单射，复刻了 1-WL 的能力。
六、还能突破上限吗
如果不借助外部特征，纯靠局部消息传递，突破的空间比较有限。这是消息传递范式的数学局限，不是调参能解决的事。
想绕过去，需要打破纯局部的假设，比如给节点加上整图位置信息，或者用子图 GNN、高阶 WL 测试对应的设计。不过这些做法已经不属于纯消息传递 GNN 了。
参考文献
JigmeDorje. (2026-04-16). 所有消息传递GNN都被1968年的1-WL算法锁死了. 微信公众号 VOKE FLOW 涌现. https://mp.weixin.qq.com/s/fdijAVjtf5kddeyYUBxM9A
Weisfeiler, B., & Leman, A. A. (1968). A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Technicheskaya Informatsiya, 2(9), 12–16.
Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., & Borgwardt, K. M. (2011). Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12, 2533–2561.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. Proceedings of the 34th International Conference on Machine Learning (ICML).
Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How powerful are graph neural networks? International Conference on Learning Representations (ICLR).