Coloring Graph Neural Networks for Node Disambiguation
Abstract
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.
Cite
Text
Dasoulas et al. "Coloring Graph Neural Networks for Node Disambiguation." International Joint Conference on Artificial Intelligence, 2020. doi:10.24963/IJCAI.2020/294Markdown
[Dasoulas et al. "Coloring Graph Neural Networks for Node Disambiguation." International Joint Conference on Artificial Intelligence, 2020.](https://mlanthology.org/ijcai/2020/dasoulas2020ijcai-coloring/) doi:10.24963/IJCAI.2020/294BibTeX
@inproceedings{dasoulas2020ijcai-coloring,
title = {{Coloring Graph Neural Networks for Node Disambiguation}},
author = {Dasoulas, George and Dos Santos, Ludovic and Scaman, Kevin and Virmaux, Aladin},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2020},
pages = {2126-2132},
doi = {10.24963/IJCAI.2020/294},
url = {https://mlanthology.org/ijcai/2020/dasoulas2020ijcai-coloring/}
}