Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Interpreting the Mechanism of Synergism for Drug Combinations Using Attention-Based Hierarchical Graph PoolingCancers, 2023
- Multi-level attention graph neural network based on co-expression gene modules for disease diagnosis and prognosisBioinformatics, 2022
- BrainGNN: Interpretable Brain Graph Neural Network for fMRI AnalysisMedical Image Analysis, 2021
- TranSynergy: Mechanism-driven interpretable deep neural network for the synergistic prediction and pathway deconvolution of drug combinationsPLOS Computational Biology, 2021
- Inferring Disease-Associated MicroRNAs Using Semi-supervised Multi-Label Graph Convolutional NetworksiScience, 2019
- Modeling polypharmacy side effects with graph convolutional networksBioinformatics, 2018
- Human whole genome genotype and transcriptome data for Alzheimer’s and other neurodegenerative diseasesScientific Data, 2016
- Histone deacetylase inhibitors: Mechanisms of cell death and promise in combination cancer therapyCancer Letters, 2008
- Cancer classification using gene expression dataInformation Systems, 2003
- KEGG: Kyoto Encyclopedia of Genes and GenomesNucleic Acids Research, 2000