  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.
