Research map / Graph learning / GNN architectures
Commute 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 Commute Graph Neural Networks (CGNN), which computes node-pair commute times on digraphs via a new digraph Laplacian (DiLap) and uses them as neighbor weights in directed message passing.
Problem
Standard message passing and digraph GNNs capture unidirectional relations but miss the mutual, asymmetric path dependencies between nodes in directed graphs, and exact commute-time computation is dense and O(N^3).
Approach
Define a digraph Laplacian (DiLap) as the divergence of the gradient on digraphs weighted by transition probabilities and the Perron vector, compute commute times via its sparse pseudoinverse with randomized truncated SVD after similarity-based rewiring for irreducibility, and weight neighbor messages by exp(-commute time) inside a DirGNN-style layer.
Key results
- CGNN achieves best accuracy on 6 of 8 datasets, e.g., 77.83 on Squirrel vs 75.19 for DirGNN and 71.59 on Citeseer vs 67.42 for DiGCL.
- Replacing rewiring with PageRank-style dense teleportation (CGNN_ppr) lowers Squirrel accuracy from 77.83 to 68.37 and increases running time from 99.25s to 257.84s.
- Using symmetrized adjacency (CGNN_sym) drops Squirrel accuracy from 77.83 to 72.37, indicating edge direction matters.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add commute-time-based neighbor weights | DirGNN · Squirrel | accuracy: 75.19 ± 1.26 -> 77.83 ± 1.52 | Helped |
| Add commute-time-based neighbor weights | DirGNN · Citeseer | accuracy: 66.57 ± 0.74 -> 71.59 ± 0.16 | Helped |
| Add commute-time-based neighbor weights | DirGNN · CoraML | accuracy: 75.33 ± 0.32 -> 77.08 ± 0.54 | Mixed |
| Replace feature-similarity rewiring with a PPR graph (ablation) | Commute GNN · Squirrel | accuracy: 77.83 -> 68.37 | Hurt |
| Replace feature-similarity rewiring with a PPR graph (ablation) | Commute GNN · Chameleon | accuracy: 79.62 -> 71.69 | Hurt |
| Replace feature-similarity rewiring with a PPR graph (ablation) | Commute GNN · Citeseer | accuracy: 71.59 -> 68.59 | Hurt |
| Replace feature-similarity rewiring with a PPR graph (ablation) | Commute GNN · CoraML | accuracy: 77.08 -> 76.23 | Hurt |
| Replace feature-similarity rewiring with a PPR graph (ablation) | Commute GNN · AM-Photo | accuracy: 90.42 -> 88.52 | Hurt |
| Symmetrize edges before computing commute time (ablation) | Commute GNN · Squirrel | accuracy: 77.83 -> 72.37 | Hurt |
| Symmetrize edges before computing commute time (ablation) | Commute GNN · CoraML | accuracy: 77.08 -> 71.29 | Hurt |
| Symmetrize edges before computing commute time (ablation) | Commute GNN · AM-Photo | accuracy: 90.42 -> 88.53 | Hurt |
| Vary the randomized truncated SVD rank q (ablation) | Commute GNN · AM-Photo, Snap-Patents, Arxiv-Year | accuracy: AM-Photo: 88.36, 90.42, 90.19, 90.37; Snap-Patents: 71.53, 72.89, 73.01, 72.97; Arxiv-Year: 64.20, 66.16, 66.21, 66.45 | Mixed |
Surprising findings
- Commute-time weighting does not help on CoraML and Snap-Patents, which the authors attribute to the absence of mutual path dependencies in citation networks.
- With careful tuning, general GNNs such as GCN can match or beat several digraph-specific GNNs on Squirrel, Chameleon, and AM-Photo.
Limitations
- The commute time matrix is dense, giving quadratic memory complexity in the number of nodes.
- Commute time weighting can slightly hurt performance on citation graphs without mutual paths.
- Results are reported on semi-supervised node classification only.
Experimental setup
Datasets: Squirrel Chameleon Citeseer CoraML AM-Photo Snap-Patents Roman-Empire Arxiv-Year
Benchmarks: Squirrel Chameleon Citeseer CoraML AM-Photo Snap-Patents Roman-Empire Arxiv-Year
Metrics: node classification accuracy
Baselines: GCN GAT GraphSAGE APPNP MixHop GPRGNN GCNII DGCN DiGCN MagNet DiGCL DUPLEX
Builds on: DirGNN GraphSAGE PageRank Perron-Frobenius theorem
Closest papers by meaning
- Improving Graph Neural Networks by Learning Continuous Edge Directions (ICLR 2025 · similarity 0.88)
- Graph neural networks and non-commuting operators (NeurIPS 2024 · similarity 0.87)
- Deep Homomorphism Networks (NeurIPS 2024 · similarity 0.87)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.87)
- DiGRAF: Diffeomorphic Graph-Adaptive Activation Function (NeurIPS 2024 · similarity 0.87)
- TopoTune: A Framework for Generalized Combinatorial Complex Neural Networks (ICML 2025 · similarity 0.87)
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.