mlsanityData to 14 Oct 2026

Coloring graph neural networks for node disambiguation

arXiv 1912.06058 ↗First posted 12 Dec 2019cs.LG stat.MLcited by 52

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 52 papers in the map (data through 14 Oct 2026). First posted on arXiv 12 Dec 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 16; 2022: 12; 2023: 10; 2024: 8; 2025: 2; 2026: 4.

52 papers.

Sort:

  1. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  2. 2021Equivariant Subgraph Aggregation Networkscited by 154
  3. 2021Nested Graph Neural Networkscited by 137
  4. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  5. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  6. 2022A Survey on Graph Representation Learning Methodscited by 66
  7. 2021Reconstruction for Powerful Graph Representationscited by 65
  8. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  9. 2022Ordered Subgraph Aggregation Networkscited by 57
  10. 2024KAGNNs: Kolmogorov-Arnold Networks meet Graph Learningcited by 49
  11. 2021Simple GNN Regularisation for 3D Molecular Property Prediction & Beyondcited by 44
  12. 2021Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networkscited by 39
38 more
  1. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  2. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  3. 2023WL meet VCcited by 31
  4. 2023Graph Positional Encoding via Random Feature Propagationcited by 31
  5. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 30
  6. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  7. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  8. 2023Learning Probabilistic Symmetrization for Architecture Agnostic Equivariancecited by 26
  9. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  10. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 20
  11. 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
  12. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  13. 2021Learning Parametrised Graph Shift Operatorscited by 16
  14. 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
  15. 2022Rethinking Graph Neural Networks for the Graph Coloring Problemcited by 13
  16. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  17. 2022Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphscited by 12
  18. 2023PlanE: Representation Learning over Planar Graphscited by 11
  19. 2024Improving the Expressiveness of K-hop Message-Passing GNNs by Injecting Contextualized Substructure Informationcited by 9
  20. 2022Weisfeiler and Leman go Hyperbolic: Learning Distance Preserving Node Representationscited by 7
  21. 2024GRANOLA: Adaptive Normalization for Graph Neural Networkscited by 7
  22. 2023State of the Art and Potentialities of Graph-level Learningcited by 6
  23. 2021Node Feature Kernels Increase Graph Convolutional Network Robustnesscited by 5
  24. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  25. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  26. 2023What Do GNNs Actually Learn? Towards Understanding their Representationscited by 4
  27. 2024Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodingscited by 4
  28. 2022Graph Representation Learning with Individualization and Refinementcited by 3
  29. 2024Iterative Graph Neural Network Enhancement via Frequent Subgraph Mining of Explanationscited by 3
  30. 2026Universality and Approximation Rates of Graph Neural Networks with Random Featurescited by 3
  31. 2021Equivariant Quantum Graph Circuitscited by 2
  32. 2022Universally Expressive Communication in Multi-Agent Reinforcement Learningcited by 2
  33. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  34. 2025Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networkscited by 1
  35. 2026How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?cited by 1
  36. 2021Ego-based Entropy Measures for Structural Representations on Graphscited by 0
  37. 2021Distance and Hop-wise Structures Encoding Enhanced Graph Attention Networkscited by 0
  38. 2021A systematic approach to random data augmentation on graph neural networkscited by 0

50 most cited of 52 All 52 (JSON)