Reproduce “The Surprising Power of Graph Neural Networks with Random Node Initialization” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ralph Abboud, İsmail İlkan Ceylan, Martin Grohe, Thomas Lukasiewicz
Graph Neural Networks (GNNs) enhanced with Random Node Initialization (RNI) are proven to be universal approximators for invariant functions on graphs, achieving high expressiveness comparable to powerful but computationally intensive higher-order GNNs while maintaining memory efficiency. Empirical evaluations on custom datasets demonstrate that RNI allows Message Passing Neural Networks (MPNNs) to overcome the 1-Weisfeiler-Leman (1-WL) test's expressiveness limitations, reaching over 95% accuracy on tasks where standard GNNs perform at chance.
Key insights
- RNI overcomes the 1-WL expressiveness barrier by individualizing nodes through distinct random initial features, which allows MPNNs to differentiate non-isomorphic graphs that are otherwise indistinguishable.
- MPNNs with RNI are universal approximators for invariant real-valued functions on graphs, providing the first universality result for a memory-efficient GNN architecture.
- Despite introducing randomness, RNI-enhanced MPNNs preserve permutation invariance in expectation, maintaining a desirable inductive bias for graph learning tasks.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.