mlsanityData to 14 Oct 2026

Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability

arXiv 2309.00738 ↗First posted 1 Sep 2023cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

The expressivity of Graph Neural Networks (GNNs) has been studied broadly in recent years to reveal the design principles for more powerful GNNs. Graph canonization is known as a typical approach to distinguish non-isomorphic graphs, yet rarely adopted when developing expressive GNNs. This paper proposes to maximize the expressivity of GNNs by graph canonization, then the power of such GNNs is studies from the perspective of model stability. A stable GNN will map similar graphs to close graph representations in the vectorial space, and the stability of GNNs is critical to generalize their performance to unseen graphs. We theoretically reveal the trade-off of expressivity and stability in graph-canonization-enhanced GNNs. Then we introduce a notion of universal graph canonization as the general solution to address the trade-off and characterize a widely applicable sufficient condition to solve the universal graph canonization. A comprehensive set of experiments demonstrates the effectiveness of the proposed method. In many popular graph benchmark datasets, graph canonization successfully enhances GNNs and provides highly competitive performance, indicating the capability and great potential of proposed method in general graph representation learning. In graph datasets where the sufficient condition holds, GNNs enhanced by universal graph canonization consistently outperform GNN baselines and successfully improve the SOTA performance up to 31%, providing the optimal solution to numerous challenging real-world graph analytical tasks like gene network representation learning in bioinformatics.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 37 of its 67 references that are in the map. First posted on arXiv 1 Sep 2023.

Builds on

37 of 67 references.

References · 37

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  7. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  8. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  10. 2018Efficient Neural Architecture Search via Parameter Sharingcited by 837
  11. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  12. 2015Generating Sentences from a Continuous Spacecited by 612
25 more
  1. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  2. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  3. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 413
  4. 2019Provably Powerful Graph Networkscited by 389
  5. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
  6. 2016Learning Convolutional Neural Networks for Graphscited by 314
  7. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
  8. 2018Learning Deep Generative Models of Graphscited by 229
  9. 2021ChemRL-GEM: Geometry Enhanced Molecular Representation Learning for Property Predictioncited by 204
  10. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  11. 2021Identity-aware Graph Neural Networkscited by 198
  12. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  13. 2019Relational Pooling for Graph Representationscited by 150
  14. 2021Nested Graph Neural Networkscited by 137
  15. 2019D-VAE: A Variational Autoencoder for Directed Acyclic Graphscited by 98
  16. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  17. 2017Geometric Matrix Completion with Recurrent Multi-Graph Neural Networkscited by 88
  18. 2021The Logic of Graph Neural Networkscited by 85
  19. 2021Directed Acyclic Graph Neural Networkscited by 70
  20. 2023CktGNN: Circuit Graph Neural Network for Electronic Design Automationcited by 58
  21. 2020Graph convolutions that can finally model local structurecited by 31
  22. 2022PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphscited by 20
  23. 2022Domain Knowledge-Infused Deep Learning for Automated Analog/Radio-Frequency Circuit Parameter Optimizationcited by 10
  24. 2022Domain Knowledge-Based Automated Analog Circuit Design with Deep Reinforcement Learningcited by 7
  25. 2022Interpreting the Mechanism of Synergism for Drug Combinations Using Attention-Based Hierarchical Graph Poolingcited by 5

Built on by

Not cited yet.