Research map / Graph learning / GNN architectures
Exploring Consistency in Graph Representations: from Graph Kernels to Graph Neural Networks
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 a model-agnostic consistency loss that enforces layer-wise consistency of graph-similarity rankings in GNNs, motivated by a theoretical analysis of WL-subtree vs. WLOA graph kernels.
Problem
GNNs often fail to preserve consistent relative similarities among graphs across layers, and WL-based graph kernels rely on predefined kernels and lack non-linearity, so the gap between kernel methods and GNNs for graph classification remains.
Approach
Define iterative graph kernels and a consistency property (monotonic decrease and order consistency), show WLOA satisfies it asymptotically while WL-subtree does not, and add a probabilistic pairwise-ranking cross-entropy loss that aligns the cosine-distance ordering of graph embeddings between consecutive GNN layers.
Key results
- Adding the consistency loss improves GIN on D&D by up to 4.51%, COLLAB by 4.32%, and IMDB-B by 3.70% (10-fold accuracy).
- Consistency loss raises layer-to-layer Spearman correlation of graph distances, e.g., GIN on PROTEINS from 0.741 to 0.904.
- On REDDIT-MULTI-5K subsets, GCN+consistency gains grow with class count (e.g., 50.30 to 57.15 on 4-class subset).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add consistency loss to GIN | GIN · NCI1 | accuracy: 78.13 -> 79.45 | Helped |
| Add consistency loss to GIN | GIN · NCI109 | accuracy: 76.75 -> 77.46 | Helped |
| Add consistency loss to GIN | GIN · PROTEINS | accuracy: 72.97 -> 74.98 | Helped |
| Add consistency loss to GIN | GIN · D&D | accuracy: 71.10 -> 75.51 | Helped |
| Add consistency loss to GMT | GMT · IMDB-B | accuracy: 79.80 -> 79.60 | Hurt |
| Add consistency loss to GCN | GCN · NCI109 | accuracy: 74.04 -> 73.25 | Hurt |
| Add consistency loss to GIN | GIN · COLLAB | accuracy: 79.84 -> 84.16 | Helped |
| Add consistency loss to GIN | GIN · COIL-RAG | accuracy: 93.33 -> 94.03 | Helped |
| Add consistency loss to GraphSAGE | GraphSAGE · OGB-HIV | ROC-AUC: 77.03 -> 78.60 | Helped |
| Add consistency loss to GIN | GIN · REDDIT-T | accuracy: 77.50 -> 77.64 | Helped |
| Add consistency loss to GCN | GCN · REDDIT-MULTI 5K Subset3 (4 classes) | accuracy: 50.30 -> 57.15 | Helped |
| Add consistency loss to GCN | GCN · IMDB-B (small density) | accuracy: 77.58 -> 84.24 | Helped |
Surprising findings
- Gains are largest for GIN, which the authors attribute to its weak cross-layer consistency; GCN on NCI109 and GMT on IMDB-B already had high correlation and showed little benefit.
- The consistency loss underperforms the base model on some settings (e.g., GCN on NCI109: 73.25 vs 74.04).
Limitations
- Theoretical guarantees for WLOA hold asymptotically and rely on strong assumptions (convergence and continuity of kernels, weights omega(i)=1).
- Kernel methods are computationally costly, and the method's scalability is only partially assessed.
- Gains are not uniform; some base-model/dataset combinations show no improvement or slight decreases.
Experimental setup
Datasets: NCI1 NCI109 PROTEINS D&D IMDB-BINARY IMDB-MULTI COLLAB COIL-RAG ogbg-molhiv Reddit-T REDDIT-MULTI-5K
Benchmarks: NCI1 NCI109 PROTEINS D&D IMDB-BINARY IMDB-MULTI COLLAB COIL-RAG ogbg-molhiv Reddit-T
Metrics: accuracy ROC-AUC Spearman rank correlation
Baselines: GCN GIN GraphSAGE GTransformer GMT WL-subtree kernel WLOA kernel
Builds on: Weisfeiler-Lehman subtree kernel Weisfeiler-Lehman optimal assignment kernel message passing neural networks GIN
Closest papers by meaning
- A Fair Comparison of Graph Neural Networks for Graph Classification (ICLR 2020 · similarity 0.91)
- Rethinking Kernel Methods for Node Representation Learning on Graphs (NeurIPS 2019 · similarity 0.91)
- Graph Classification via Reference Distribution Learning: Theory and Practice (NeurIPS 2024 · similarity 0.90)
- OpenGSL: A Comprehensive Benchmark for Graph Structure Learning (NeurIPS 2023 · similarity 0.90)
- KerGNNs: Interpretable Graph Neural Networks with Graph Kernels (AAAI 2022 · similarity 0.90)
- How Graph Neural Networks Learn: Lessons from Training Dynamics (ICML 2024 · similarity 0.89)
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.