# Commute Graph Neural Networks

arXiv: https://arxiv.org/abs/2407.01635 · HTML: https://mlsanity.com/paper/2407.01635/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 50 references that are in the map.
- First posted on arXiv 30 Jun 2024.

## Builds on (most cited first, 28 of 28)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [MagNet: A Neural Network for Directed Graphs](https://mlsanity.com/paper/2102.11391/) (2021)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [DiffWire: Inductive Graph Rewiring via the Lov'asz Bound](https://mlsanity.com/paper/2206.07369/) (2022)
- [Directed Graph Convolutional Network](https://mlsanity.com/paper/2004.13970/) (2020)
- [LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2302.08191/) (2023)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [Efficient Graph Similarity Computation with Alignment Regularization](https://mlsanity.com/paper/2406.14929/) (2024)
- [GAG: Global Attributed Graph Neural Network for Streaming Session-based Recommendation](https://mlsanity.com/paper/2007.02747/) (2020)
- [SigMaNet: One Laplacian to Rule Them All](https://mlsanity.com/paper/2205.13459/) (2022)
- [Transformers over Directed Acyclic Graphs](https://mlsanity.com/paper/2210.13148/) (2022)
- [HoloNets: Spectral Convolutions do extend to Directed Graphs](https://mlsanity.com/paper/2310.02232/) (2023)
- [A Magnetic Framelet-Based Convolutional Neural Network for Directed Graphs](https://mlsanity.com/paper/2210.10993/) (2022)
- [DUPLEX: Dual GAT for Complex Embedding of Directed Graphs](https://mlsanity.com/paper/2406.05391/) (2024)

## Built on by (most cited first, 5 of 5)

- [Scale-aware Message Passing For Graph Node Classification](https://mlsanity.com/paper/2411.19392/) (2024)
- [Personalized Subgraph Federated Learning with Differentiable Auxiliary Projections](https://mlsanity.com/paper/2505.23864/) (2025)
- [Gauge-Equivariant Graph Networks via Self-Interference Cancellation](https://mlsanity.com/paper/2511.16062/) (2025)
- [Persistent Tri-State Message Passing](https://mlsanity.com/paper/2601.01207/) (2026)
- [Learning Graphs through Continuous Information Entropy Fields](https://mlsanity.com/paper/2606.22895/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) have shown remarkable success in learning from graph-structured data. However, their application to directed graphs (digraphs) presents unique challenges, primarily due to the inherent asymmetry in node relationships. Traditional GNNs are adept at capturing unidirectional relations but fall short in encoding the mutual path dependencies between nodes, such as asymmetrical shortest paths typically found in digraphs. Recognizing this gap, we introduce Commute Graph Neural Networks (CGNN), an approach that seamlessly integrates node-wise commute time into the message passing scheme. The cornerstone of CGNN is an efficient method for computing commute time using a newly formulated digraph Laplacian. Commute time is then integrated into the neighborhood aggregation process, with neighbor contributions weighted according to their respective commute time to the central node in each layer. It enables CGNN to directly capture the mutual, asymmetric relationships in digraphs. Extensive experiments on 8 benchmarking datasets confirm the superiority of CGNN against 13 state-of-the-art methods.