Research map / Graph learning / GNN architectures
Multi-Track Message Passing: Tackling Oversmoothing and Oversquashing in Graph Learning via Preventing Heterophily Mixing
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 MTGCN, a multi-track GCN whose message passing propagates node features separately in category-specific tracks to prevent heterophily mixing, tackling oversmoothing and oversquashing.
Problem
Deep GNNs suffer from oversmoothing and oversquashing, which the authors attribute to information loss from mixing messages of different category semantics (heterophily mixing) during aggregation.
Approach
Separate messages into multiple isomorphic graph tracks, one per category semantic, with soft node-track affiliations computed by dot-product attention against track prototypes; messages propagate independently within each track, with initial residuals and no per-layer weights or activations, and a multi-stage self-training pipeline refines affiliations and pseudo-labels.
Key results
- MTGCN-s3 reaches 86.40% accuracy on Cora in the semi-supervised setting, the highest reported in the paper's comparison.
- At 64 layers on Cora, MTGCN keeps 86.4% accuracy while GCN drops to 28.7%.
- MTGCN achieves nearly perfect training accuracy on Tree-NeighborsMatch, while other models decline beyond tree depth 5.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use multi-track message passing with stage 3 | MTGCN · Cora (semi-supervised) | accuracy: 85.30 -> 86.40 | Helped |
| Use multi-track message passing with stage 3 | MTGCN · Citeseer (semi-supervised) | accuracy: 75.60 -> 74.60 | Hurt |
| Use multi-track message passing with stage 2 | MTGCN · Pubmed (semi-supervised) | accuracy: 80.60 -> 81.10 | Helped |
| Use multi-track message passing with stage 4 | MTGCN · Coauthor CS (semi-supervised) | accuracy: 90.01 -> 92.54 | Helped |
| Use multi-track message passing with stage 4 | MTGCN · Coauthor Physics (semi-supervised) | accuracy: 94.55 -> 94.72 | Helped |
| Use multi-track message passing with stage 1 | MTGCN · Cora (fully supervised) | accuracy: 88.49 -> 90.61 | Helped |
| Use multi-track message passing with stage 3 | MTGCN · Citeseer (fully supervised) | accuracy: 77.99 -> 77.36 | Hurt |
| Use multi-track message passing with stage 1 | MTGCN · Pubmed (fully supervised) | accuracy: 90.30 -> 88.43 | Hurt |
| Use multi-track message passing with stage 4 | MTGCN · Cornell (fully supervised) | accuracy: 85.68 -> 89.47 | Helped |
| Use multi-track message passing with stage 2 | MTGCN · Texas (fully supervised) | accuracy: 88.38 -> 92.10 | Helped |
| Use multi-track message passing with stage 1 | MTGCN · Wisconsin (fully supervised) | accuracy: 89.41 -> 90.20 | Helped |
| Increase message-passing depth from 2 to 64 layers (ablation) | MTGCN · Cora (semi-supervised) | accuracy: 80.5 -> 86.4 | Helped |
Surprising findings
- Node-track affiliation accuracy on Cora is only 73.85%, yet classification accuracy exceeds it thanks to initial residual connections.
- Space complexity O(d|T||V|eta) grows with the number of tracks, causing a slight accuracy decline beyond 6-7 layers on Tree-NeighborsMatch.
Experimental setup
Datasets: Cora Citeseer Pubmed Coauthor CS Coauthor Physics Cornell Texas Wisconsin Tree-NeighborsMatch
Benchmarks: Cora Citeseer Pubmed Coauthor CS Coauthor Physics Cornell Texas Wisconsin Tree-NeighborsMatch
Metrics: classification accuracy group distance ratio Rg training accuracy node-track affiliation accuracy
Baselines: GCN GAT Self-Train DisenGCN GCNII EGNN GRAND++ PDE-GCN GraphCON ACMP GREAD H2GCN
Builds on: GCN GCNII SGC DisenGCN
Closest papers by meaning
- A Signed Graph Approach to Understanding and Mitigating Oversmoothing (NeurIPS 2025 · similarity 0.87)
- HeterSEED: Semantics–Structure Decoupling for Heterogeneous Graph Learning under Heterophily (NeurIPS 2026 · similarity 0.87)
- Graph Neural Networks Do Not Always Oversmooth (NeurIPS 2024 · similarity 0.86)
- Relieving the Over-Aggregating Effect in Graph Transformers (NeurIPS 2025 · similarity 0.86)
- Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching (ICML 2025 · similarity 0.86)
- Mitigating Oversmoothing Through Reverse Process of GNNs for Heterophilic Graphs (ICML 2024 · similarity 0.86)
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.