← 研踪 PaperTrailarXiv:2410.01308 · v7
How Hard Is It for Message-Passing GNNs to Simulate One Step of the Weisfeiler-Lehman Test?
首次提交 2024-10-02 16:01
版本更新 2026-11-09 16:32
雷达观测 2026-11-10 15:22
摘要
Message-passing graph neural networks (MPGNNs) are commonly compared with the Weisfeiler-Lehman (WL) test, but this comparison does not quantify the resource parameters a network needs to implement a step of the WL test with bounded-size messages and finite numerical precision. We study the cost of simulating a single step of the WL test on unattributed graphs. We distinguish input-independent, or oblivious, simulation from instance-dependent simulation. In the former, the parameters, or their distributions in randomized models, are fixed before the input instance is known. Our results show that the local update rule of the WL test hides a global relabeling problem. In the oblivious setting, deterministic and zero-error randomized MPGNNs cannot solve this problem in the worst case using only shallow networks with small messages. We complement this lower bound with a nearly matching construction in a stronger rooted, port-aware model. By contrast, when the color set is large, bounded-error randomness can greatly reduce the cost, and a one-layer MPGNN with messages of logarithmic size and a logarithmic number of random bits suffices. We show that this logarithmic number of random bits is essentially necessary for shallow, small-message simulations. When the color set is small, we still obtain a rooted, port-aware simulation, but this construction requires more layers or larger messages. We also prove that this extra cost is partly unavoidable, as small color sets force a nontrivial trade-off between the number of layers and the message size. Finally, instance-dependent simulation can be much shallower, but the required instance-specific parameters are not necessarily easy to find. Together, these results reveal quantitative structure hidden behind the statement that MPGNNs match the WL test.
作者备注：Accepted by NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v7 · 2026-11-09 16:32 · 最新观测版本
How Hard Is It for Message-Passing GNNs to Simulate One Step of the Weisfeiler-Lehman Test?
Message-passing graph neural networks (MPGNNs) are commonly compared with the Weisfeiler-Lehman (WL) test, but this comparison does not quantify the resource parameters a network needs to implement a step of the WL test with bounded-size messages and finite numerical precision. We study the cost of simulating a single step of the WL test on unattributed graphs. We distinguish input-independent, or oblivious, simulation from instance-dependent simulation. In the former, the parameters, or their distributions in randomized models, are fixed before the input instance is known. Our results show that the local update rule of the WL test hides a global relabeling problem. In the oblivious setting, deterministic and zero-error randomized MPGNNs cannot solve this problem in the worst case using only shallow networks with small messages. We complement this lower bound with a nearly matching construction in a stronger rooted, port-aware model. By contrast, when the color set is large, bounded-error randomness can greatly reduce the cost, and a one-layer MPGNN with messages of logarithmic size and a logarithmic number of random bits suffices. We show that this logarithmic number of random bits is essentially necessary for shallow, small-message simulations. When the color set is small, we still obtain a rooted, port-aware simulation, but this construction requires more layers or larger messages. We also prove that this extra cost is partly unavoidable, as small color sets force a nontrivial trade-off between the number of layers and the message size. Finally, instance-dependent simulation can be much shallower, but the required instance-specific parameters are not necessarily easy to find. Together, these results reveal quantitative structure hidden behind the statement that MPGNNs match the WL test.
查看此版本解读 →查看此版本原文 ↗