Research map / Graph learning / GNN architectures
Rethinking the Power of Graph Canonization in Graph Representation Learning with Stability
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes graph-canonization-enhanced GNNs (GC-GNN) that use canonical node orderings as positional encodings, identifies an expressivity-stability trade-off, and introduces universal graph canonization (UGC-GNN) with a sufficient condition based on dataset-wide node labeling.
Problem
GNNs are limited by 1-WL expressivity; graph canonization can distinguish non-isomorphic graphs, but canonical node labelings are unstable under small graph perturbations, hurting generalization to unseen graphs.
Approach
Use graph canonization outputs as one-hot node positional encodings to maximize expressivity, then resolve the resulting stability loss with a dataset-level "universal" canonization defined via a globally injective node labeling l(v|G) that is consistent across graphs, also applied in the readout layer via per-label weight matrices.
Key results
- GC-GNN (GIN) reaches 1.00 train and 0.9667 test accuracy on CSL versus 0.1400/0.1157 for GIN; on TU datasets GC-GNN improves backbones by up to 29.6% on D&D, and GC-GNN (GraphSAGE) reaches 89.4% on MUTAG.
- UGC-GNN (GIN) achieves 0.624 accuracy on Mayo, 0.701 on RosMap and 0.714 on Cancer Subtype, outperforming listed gene-network DL baselines such as MLA-GNN (0.589, 0.595, 0.631).
- On NA and BN DAG regression, UGC-GNN (GIN) obtains RMSE 0.253 and 0.120, improving over SAN (0.311 and 0.158).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add graph canonization positional encodings to GIN/GCN | GIN, GCN · EXP and CSL isomorphism tests | test accuracy: EXP GCN 0.5000 -> 0.9267; GIN 0.5000 -> 0.9975 | Helped |
| add graph canonization (GC-GNN) to backbone GNNs | TU datasets (GCN, GraphSAGE, GIN, GAT) · D&D, MUTAG, PROTEINS, PTC-MR, ENZYMES | accuracy: average improvement over backbone 6.0% to 28.2% across datasets; max 29.6% on D&D | Helped |
| add graph canonization to GNN backbones | TU datasets · ENZYMES and PTC-MR (some GC-GNN variants) | accuracy: GC-GNN (GIN) 30.7 on ENZYMES and 57.2 on PTC-MR, below several baselines such as GIN-AK+ and SignNet | Mixed |
| add general graph canonization (GC) to GIN on gene networks | GIN on Mayo, RosMap, Cancer · gene network datasets | accuracy: Mayo GIN 0.496 -> GC-GNN 0.483; RosMap GIN 0.471 -> GC-GNN 0.486 (Mayo worse) | Hurt |
| replace general graph canonization with universal graph canonization (UGC) on GIN (ablation) | GIN on gene networks and brain graphs · Mayo, RosMap, Cancer, fMRI-ABIDE | accuracy: Mayo 0.483 (GC) -> 0.624 (UGC); RosMap 0.486 -> 0.701; Cancer 0.539 -> 0.714; fMRI-ABIDE 0.610 -> 0.648 | Helped |
| add universal graph canonization (UGC) to GIN | GIN on DAG datasets · NA and BN | RMSE (lower better): NA 0.264 (DAGNN best baseline) -> 0.253; BN 0.122 -> 0.120 | Helped |
| add universal graph canonization to GIN | GIN on gene networks · Mayo, RosMap, Cancer | accuracy: Mayo 0.496 -> 0.624 (GIN backbone to UGC-GNN); RosMap 0.471 -> 0.701 | Helped |
| add general graph canonization (GC) to GCN on gene networks (ablation) | GCN · Mayo, RosMap, Cancer Subtype | accuracy: Mayo GCN 0.561 -> 0.522; RosMap 0.520 -> 0.508; Cancer 0.593 -> 0.544 | Mixed |
| add universal graph canonization (UGC) to GCN (ablation) | GCN · Mayo, RosMap, Cancer Subtype | accuracy: Mayo 0.561 -> 0.572 (UGC); RosMap 0.520 -> 0.658; Cancer 0.593 -> 0.619 | Mixed |
| add graph canonization to GIN on molecular datasets (ablation) | GIN · ogbg-molhiv and ogbg-molpcba | AUC / AP: molhiv GIN 0.7744 -> GN-GIN 0.7705 (drop); molpcba 0.2703 -> 0.2781 (gain) | Mixed |
Surprising findings
- General graph canonization (GC-GNN) often performs worse than the GIN backbone on large gene networks (Mayo, RosMap, Cancer), supporting the claimed stability trade-off.
- GC-GNN (GIN) gets lower than GIN on ogbg-molhiv-type settings and does not reach SOTA on OGB molecular datasets.
Limitations
- Universal graph canonization requires a dataset-level injective node labeling, which is only available in specific domains (gene networks, brain graphs, grids, DAGs).
- Graph canonization ignores edge heterogeneity and is not suited to all tasks; gains on OGB molecular datasets are modest and not SOTA.
- Stability/generalization results are theoretical with loose constants and empirical comparison is limited to a subset of baselines.
Experimental setup
Datasets: EXP CSL TU datasets (PROTEINS, PTC-MR, MUTAG, ENZYMES, D&D) Mayo RosMap Cancer Subtype fMRI ABIDE NA (ENAS neural architectures) BN (bnlearn Bayesian networks) ogbg-molhiv ogbg-molpcba
Benchmarks: EXP CSL TU datasets Mayo RosMap Cancer Subtype fMRI ABIDE NA BN ogbg-molhiv ogbg-molpcba
Metrics: accuracy F1 score RMSE Pearson's r ROC-AUC AP
Baselines: GCN GIN GAT GraphSAGE Nested GNN GraphSNN GIN-AK+ SignNet ESAN DropGNN GNN-RNI PPGN
Builds on: Weisfeiler-Lehman test Nauty Graph Isomorphism Network Nested GNN positional encoding for graph transformers
Closest papers by meaning
- Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.90)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.89)
- Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs (ICLR 2025 · similarity 0.88)
- On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.88)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.