Coloring graph neural networks for node disambiguation
This addresses a fundamental limitation in graph neural networks for researchers and practitioners, representing a novel method rather than an incremental improvement.
The paper tackles the problem of identical node attributes limiting the expressive power of Message Passing Neural Networks by introducing a coloring scheme called CLIP, which theoretically achieves universal approximation and experimentally matches state-of-the-art performance on graph classification benchmarks.
In this paper, we show that a simple coloring scheme can improve, both theoretically and empirically, the expressive power of Message Passing Neural Networks(MPNNs). More specifically, we introduce a graph neural network called Colored Local Iterative Procedure (CLIP) that uses colors to disambiguate identical node attributes, and show that this representation is a universal approximator of continuous functions on graphs with node attributes. Our method relies on separability , a key topological characteristic that allows to extend well-chosen neural networks into universal representations. Finally, we show experimentally that CLIP is capable of capturing structural characteristics that traditional MPNNs fail to distinguish,while being state-of-the-art on benchmark graph classification datasets.