Research map / Graph learning / GNN architectures

Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing

ICLR 2025 · Graph learning › GNN architectures · approach: Expressive equivariant message passing · 0 citations (OpenAlex)

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.

Recasts simplicial/cellular complexes and their message passing as relational structures, derives oversquashing bounds (sensitivity, curvature, depth, width) via influence graphs, and proposes a relational rewiring heuristic evaluated on TUDatasets and RingTransfer.

Problem

Oversquashing in topological (simplicial/cellular) message passing is understudied and lacks theoretical analysis, and graph oversquashing results do not directly apply to higher-order structures.

Approach

Model simplicial complexes as relational structures with shift operators, so that simplicial message passing becomes an instance of relational message passing; analyze sensitivity via an aggregated influence matrix and influence graph, extending graph oversquashing results (curvature, depth, width) to this setting, and adapt graph rewiring (SDRF, FoSR, AFRC) by adding a new relation built from a c

Key results

• Relational rewiring with the best algorithm improves test accuracy for most base graphs; e.g., GCN on MUTAG rises from 71.0 to 83.0 and RGCN on IMDB-B with FoSR from 47.6 to 68.0.
• Results show relational and topological models respond to rewiring similarly to graph models, with some decreases (e.g., SIN on MUTAG drops from 88.5 to 85.5).
• RingTransfer experiments are reported to be consistent with the theory: larger rings degrade performance, while rewiring and moderate hidden dimensions help.

Measured effects reported in the paper

Surprising findings

• Rewiring with fixed, dataset- and model-agnostic hyperparameters sometimes decreases accuracy (e.g., GIN on IMDB-B drops from 71.7 to 67.1 with FoSR).

Limitations

• Rewiring algorithms were not designed for weighted directed influence graphs, so they may be suboptimal.
• Curvature comparisons between graphs and clique complexes are proxies and not theoretically rigorous.
• Results on oversquashing are based on bounds with assumptions (bounded Jacobians, row-normalized shift operators) and balanced Forman curvature extension is left for future work.

Experimental setup

Datasets: ENZYMES IMDB-B MUTAG NCI1 PROTEINS RingTransfer

Benchmarks: ENZYMES IMDB-B MUTAG NCI1 PROTEINS RingTransfer

Metrics: test accuracy

Baselines: SGC GCN GIN RGCN RGIN SIN CIN CIN++

Builds on: First-Order Spectral Rewiring (FoSR) relational graph convolutional network (R-GCN) simplicial Weisfeiler-Lehman / simplicial neural networks CW networks

Closest papers by meaning

• Topological Blindspots: Understanding and Extending Topological Deep Learning Through the Lens of Expressivity (ICLR 2025 · similarity 0.89)
• Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes (AAAI 2024 · similarity 0.87)
• Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching (ICML 2025 · similarity 0.86)
• Deeper with Riemannian Geometry: Overcoming Oversmoothing and Oversquashing for Graph Foundation Models (NeurIPS 2025 · similarity 0.86)
• HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representations (NeurIPS 2026 · similarity 0.85)
• TopoTune: A Framework for Generalized Combinatorial Complex Neural Networks (ICML 2025 · similarity 0.85)