Pith. sign in

REVIEW 2 major objections 5 minor 17 references

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

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper establishes that simplicial and relational message passing obey the same walk-based sensitivity bound that drives oversquashing in GNNs, so curvature and rewiring tools transfer to higher-order networks.

desk verdict Relational-structure reduction and Lemma 3.2 are solid, but the depth theorem (Thm 3.5) has a false binomial bound and assumes row-normalization that the paper's own models violate. read the letter →

arxiv 2506.06582 v1 pith:6Q7TLQ36 submitted 2025-06-06 cs.LG stat.ML

Diaaeldin Taha , James Chapman , Marzieh Eidi , Karel Devriendt , Guido Montúfar This is my paper
classification cs.LGstat.ML MSC 68T0755U1005C50
keywords topologicaldeeplearningsimplicialcomplexesrelationalstructuresoversquashingmessagepassinggraphrewiringinfluencegraphsFormancurvature
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that simplicial complexes and the message-passing networks built on them can be rewritten as relational structures—finite sets of entities connected by boundary, co-boundary, lower, and upper adjacency relations—and that this rewrite is enough to import the oversquashing theory of graph neural networks. If this is right, the same quantities that predict information loss in GNNs, namely walk counts and bottlenecks in an adjacency matrix, also predict information loss in simplicial, cellular, and other higher-order networks, and graph rewiring algorithms can be adapted to fix it. The authors prove a sensitivity bound, a curvature bound, a depth-decay theorem, and a hidden-dimension bound for relational message passing, and they test the resulting rewiring heuristic on graph classification, node classification, and synthetic transfer tasks.

What carries the argument

The load-bearing object is the relational structure $R=(S,R_1,\ldots,R_k)$ equipped with shift operators $A^{R_i}$ that weight each relation, from which the paper forms the aggregated influence matrix $\tilde A = \sum_i \tilde A^{R_i}$, the augmented influence matrix $B=\gamma I + \tilde A$ with $\gamma$ the maximum row sum of $\tilde A$, and the influence graph $G(S,B)$. The entry $(B^t)_{\sigma,\tau}$ counts weighted walks from $\tau$ to $\sigma$ in $G(S,B)$, which is exactly what makes the sensitivity bound combinatorial rather than merely analytic. For rewiring, the paper collapses the relational structure to a graph via the collapsed adjacency matrix $A^{\mathrm{col}}$, runs a graph rewiring algorithm on that graph, and adds the newly created edges as an extra relation.

What would settle it

Compute the row sums of the shift operators used by the SIN and CIN layers in Appendix F.5: with sum aggregation, a simplex's row sum equals its neighborhood size, so Assumption 2 fails and the exponential decay in distance $r$ from Theorem 3.5 has no force for those standard schemes. A direct check would be to build a small simplicial complex satisfying the normalization assumption, set edge weights so that $2\alpha_{\max}\beta_{\max}M<1$, and compare finite-difference Jacobians across distance $r$ with the predicted $(2\alpha_{\max}\beta_{\max}M)^r$ scaling; if the scaling does not hold, the depth theorem's premise rather than its conclusion is the broken link.

Watch

Extended reading notes

Core claim

The central claim is Lemma 3.2: for relational message passing with bounded Jacobians, the sensitivity of entity $\sigma$'s features at layer $t$ to entity $\tau$'s input features satisfies $\|\partial h^{(t)}_\sigma / \partial h^{(0)}_\tau\|_1 \leq \bigl(\prod_{\ell=0}^{t-1} \alpha^{(\ell)}\beta^{(\ell)}\bigr)(B^{t})_{\sigma,\tau}$, where $B = \gamma I + \tilde A$ is the augmented influence matrix built from the shift operators of the relational structure. The same construction yields an extended Forman curvature bound on two-step sensitivity (Proposition 3.4), an exponential depth-decay bound when the largest influence weight $M$ satisfies $2\alpha_{\max}\beta_{\max}M < 1$ (Theorem 3.5), and a hidden-width bound that makes shallow and narrow networks more prone to oversquashing (Section 3.4). The paper also claims that these bounds transfer the standard GNN toolkit—curvature, rewiring, spectral arguments—to simplicial complexes, and it validates the transfer empirically on real-world benchmarks and a ring-transfer task.

Load-bearing premise

The load-bearing premise is Assumption 2: every shift operator is row-normalized, with each row summing to either 1 or 0; standard simplicial message passing aggregates with unnormalized sums over boundary, co-boundary, lower, and upper neighborhoods, so without a normalization step the exponential depth-decay guarantee does not apply to the very schemes the paper analyzes and tests.

Editorial extensions

If this is right

  • If the sensitivity bound is correct, oversquashing in simplicial and cellular message passing is diagnosed by the same quantities used for GNNs: weighted walk counts $(B^t)_{\sigma,\tau}$ and bottleneck structure of the influence graph $G(S,B)$.
  • If Theorem 3.5 is correct, deeper topological networks lose long-range sensitivity exponentially in distance whenever the largest influence weight satisfies $2\alpha_{\max}\beta_{\max}M < 1$, and the loss is governed by how fast walks between distant entities grow.
  • The relational rewiring heuristic gives a direct way to port spectral and curvature-based rewiring methods (FoSR, SDRF, AFRC) to topological architectures by rewiring the collapsed graph and adding the new edges as a fresh relation.
  • The framework covers relational GNNs, higher-order GNNs, and CW networks as well as simplicial complexes, so the same sensitivity, curvature, depth, and rewiring results apply across those model families.
  • Hidden width enters the bound multiplicatively: increasing message and update dimensions relaxes the sensitivity upper bound and can improve propagation, up to the point where overfitting and oversmoothing take over.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the relational rewiring heuristic first collapses the structure to an unweighted graph, discarding the weights and directions that the influence-graph analysis identifies as controlling information flow; rewiring $G(S,B)$ directly, with weighted directed edges, is a natural strengthening the paper leaves implicit.
  • Editorial inference: the walk-count bound yields a cheap pre-training check for whether a clique or ring lift actually relieves oversquashing—compare $(B^t)$ walk growth between the original graph and its lift before committing to training.
  • Editorial inference: because standard sum-aggregation simplicial layers violate the row-normalization assumption behind the depth theorem, normalizing shift operators by neighborhood size would make the exponential decay bound applicable and might itself mitigate oversquashing; the paper does not vary this choice in experiments.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes an axiomatic framework that views simplicial complexes and their message-passing schemes as relational structures, and introduces influence graphs G(S,Q) together with aggregated influence matrices A and B. The main theoretical results are a sensitivity bound for relational message passing (Lemma 3.2), a curvature-based two-layer bound (Proposition 3.4), an exponential-in-depth decay bound (Theorem 3.5), and a hidden-dimension scaling analysis (Section 3.4). The paper also proposes a relational rewiring heuristic based on a collapsed adjacency matrix, and evaluates it on TUDataset benchmarks and the RingTransfer synthetic task using SIN, CIN, and CIN++ models.

Significance. The relational-structure viewpoint is a clean and potentially useful unifying perspective, and Lemma 3.2 is a valid, clearly proved generalization of GNN sensitivity bounds. The influence graph gives a concrete combinatorial object on which graph-theoretic tools such as curvature and rewiring can be ported. The code is publicly released and the experimental suite is broad. However, the paper's central depth result (Theorem 3.5) rests on a false proof step and is not applicable to the unnormalized simplicial message-passing layers used in the experiments, so the claimed exponential-decay guarantee for simplicial message passing is not established as written.

major comments (2)
  1. [Appendix C.3, Eq. (12)] The proof of Theorem 3.5 contains a false binomial inequality. The chain bounds the coefficient (r+m choose r+q) by ((1+m)/(m+1))^{r-m}(1+m)^m, but for m=1 and any r>=3, the left-hand product equals r+1 while the claimed bound equals 2. Consequently, the product over j=1..r of (1+m/j) is not bounded by ((1+m)/(m+1))^{r-m}(1+m)^m; its true value is binomial(r+m,m), which is a polynomial of degree m in r. This means the constant C in Eq. (12) cannot be independent of r as stated, and the exponential-decay constant (2 alpha_max beta_max M)^r is not established by the proof. The statement of Theorem 3.5 and the proof need correction, for instance by allowing C to grow polynomially in r.
  2. [Assumption 2 (Eq. 11) / Appendix F.5 / Section 5.2] Assumption 2 requires every shift operator A^{R_i} to have row sums equal to 1 or 0. The SIN, CIN, and CIN++ layers specified in Appendix F.5 perform unnormalized sum aggregations over boundary, co-boundary, lower, and upper neighborhoods, so their shift operators are adjacency indicators whose row sums equal the corresponding neighborhood sizes, which generally exceed 1. Therefore Theorem 3.5 does not apply to the models used in the RingTransfer experiments (Section 5.2) or in Table 1. The claim in Section 5.2 that the RingTransfer results 'confirm' the theoretical results of Section 3 is thus too strong: the depth component of the theory is not tested by those experiments. Either the experiments should use row-normalized aggregation, or a separate analysis covering unnormalized shifts is needed.
minor comments (5)
  1. [Sections 2.2 and 3] The phrase 'Appendx H' appears instead of 'Appendix H'; this typo should be fixed.
  2. [Eq. (7)] The definition of gamma as 'max_sigma sum_{xi in S^{n_i-1}} tilde{A}_{sigma,xi}' mixes the index sets of the shift operators with the aggregated matrix tilde{A}; gamma should be defined as the maximum row sum of tilde{A}.
  3. [Section 3.3, preamble] Assumption 2 is described as 'non-restrictive', but it is a substantive restriction that excludes the standard simplicial message-passing schemes studied later in the paper; the label should be removed or justified.
  4. [Appendix C.3] The intermediate expression ((1+m)^2/(2m+1)) appearing in the proof of Theorem 3.5 does not match the preceding algebraic line and appears to be a typographical or algebraic error that should be corrected.
  5. [Section 5.2] The statement that the RingTransfer experiments 'confirm' the theoretical results should be softened, given that the architectures used do not satisfy Assumption 2 and hence Theorem 3.5 is not directly validated by these experiments.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sensitivity and depth bounds are derived from the shift operators by direct induction, and no fitted parameter is renamed as a prediction.

full rationale

The paper's derivation chain is self-contained rather than circular. The relational message-passing model (Definition 2.5) is stated first, and the aggregated influence matrix is defined from the shift operators (Eq. 5-6), with B = gamma*I + tilde-A (Eq. 7) also defined from those inputs. Lemma 3.2 is then proved by a layer-by-layer induction using only Assumption 1, the triangle inequality for the 1-norm, and the definition of matrix multiplication; the claimed bound (prod alpha*beta)(B^t)_{sigma,tau} is exactly what the proof produces, not a restatement of the conclusion. Theorem 3.5 is a binomial expansion of (gamma*I + tilde-A)^(r+m) under the explicitly stated Assumptions 2 and 3; it is a mathematical derivation from the model, not a quantity fitted to data and then re-predicted. The RingTransfer experiments report task accuracies for different depths, widths, and rewiring iterations; they do not fit a parameter and then 'predict' that same parameter. Self-citations (e.g., FoSR from Karhadkar et al., which shares an author) are used as external rewiring baselines and are not load-bearing for the theoretical claims. Some correctness concerns do exist, but they are not circularity: the binomial coefficient bound in Appendix C.3 appears false for m=1, r>=3, so the constant C may not be r-independent as stated, and Assumption 2 (row-normalized shifts) is not satisfied by the unnormalized SIN/CIN/CIN++ layers used in the experiments, limiting the scope of Theorem 3.5. These are validity issues in the proof and assumptions, not instances of a conclusion being equivalent to its input by construction. Therefore the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 3 invented entities

The central claim requires no fitted parameters. The main analytical constructs (influence graph, aggregated and augmented influence matrices, collapsed adjacency) are defined from the shift operators and are not independent entities. The key burden is Assumption 2, which is a paper-specific restriction needed for the exponential depth decay result.

assumptions (5)
  • domain assumption Message and update functions are differentiable with bounded Jacobians (Assumption 1)
    Used in Lemma 3.2 and all derived bounds; standard in GNN oversquashing analyses (Topping et al. 2022; Di Giovanni et al. 2023).
  • ad hoc to paper Each shift operator is row-normalized (Assumption 2)
    Required for Theorem 3.5's exponential decay with distance; not satisfied by the standard sum-based simplicial message passing used in the paper's own experiments, so it is an ad hoc restriction for the depth result.
  • domain assumption Lipschitz constants bounded uniformly across layers (Assumption 3)
    Used in Theorem 3.5 to absorb constants into C; standard for depth analysis.
  • standard math Simplicial complexes are closed under non-empty subsets and represented as a finite relational structure (Definition 2.1)
    Standard definition from Nanda (2021), used as background.
  • standard math Matrix induced 1-norm submultiplicative and additive properties
    Used throughout the sensitivity proof in Appendix C.1.
invented entities (3)
  • Influence graph G(S,Q)
    purpose: Represent aggregated relational message passing dynamics as a weighted directed graph for analysis.
    Defined in Definition 3.1 from the aggregated influence matrix; it is an analysis construct with no external falsifiable handle.
  • Aggregated influence matrix A_tilde and augmented influence matrix B
    purpose: Collapse all relations and argument positions into a single nonnegative matrix used in sensitivity bounds.
    Defined in Equations 5-7; they are aggregations of the shift operators, not independently measurable quantities.
  • Collapsed adjacency matrix A_col
    purpose: Enable applying graph rewiring algorithms to relational structures by ignoring relation types.
    Defined in Definition 4.1 to construct the rewiring heuristic; not an independently observable entity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing." pith.science (2026). https://pith.science/paper/6Q7TLQ36

@misc{pith2026250606582,
  author       = {Pith},
  title        = {Pith review of: Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6Q7TLQ36}},
  note         = {Machine review of arXiv:2506.06582}
}
read the original abstract

Topological deep learning (TDL) has emerged as a powerful tool for modeling higher-order interactions in relational data. However, phenomena such as oversquashing in topological message-passing remain understudied and lack theoretical analysis. We propose a unifying axiomatic framework that bridges graph and topological message-passing by viewing simplicial and cellular complexes and their message-passing schemes through the lens of relational structures. This approach extends graph-theoretic results and algorithms to higher-order structures, facilitating the analysis and mitigation of oversquashing in topological message-passing networks. Through theoretical analysis and empirical studies on simplicial networks, we demonstrate the potential of this framework to advance TDL.

Figures

Figures reproduced from arXiv: 2506.06582 by the authors.

Figure 1
Figure 1. The left panel shows a simplicial complex [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Performance on RINGTRANSFER obtained by varying model hidden dimensions (left), ring size (middle), and number of rewiring iterations (right). Appendix D.4, (2) graph regression for ZINC in Appendix D.5, (3) node classification for COR￾NELL, WISCONSIN, TEXAS, CORA, and CITESEER in Appendix D.6, (4) simplex pruning on the MUTAG dataset in Appendix D.8, and (5) full TUDataset results in Appendix E.1. 6 DISCUSSION AND … view at source ↗
Figure 6
Figure 6. Each of the green nodes is assigned a distinct random label which is represented by a [PITH_FULL_IMAGE:figures/full_fig_p028_6.png] view at source ↗
Figures from the paper (10 more)
Figure 3
Figure 3. Figure 3: Long dumbbell graph before and after lifting to its clique complex. Edges are colored [PITH_FULL_IMAGE:figures/full_fig_p029_3.png]
Figure 4
Figure 4. Figure 4: Weighted curvature scatter plots for MUTAG: Ollivier Ricci curvature (top), balanced For [PITH_FULL_IMAGE:figures/full_fig_p030_4.png]
Figure 5
Figure 5. Figure 5: Edge curvature distribution across all graphs in the MUTAG dataset: Ollivier-Ricci curva [PITH_FULL_IMAGE:figures/full_fig_p030_5.png]
Figure 6
Figure 6. Figure 6: NeighborsMatch Graph with 3 cliques of 5 nodes. [PITH_FULL_IMAGE:figures/full_fig_p031_6.png]
Figure 7
Figure 7. Figure 7: Neighbors Match Rewiring experiment. We also benchmark trees and trees with cycles attached to the leaves on the NeighborsMatch bench￾mark (see [PITH_FULL_IMAGE:figures/full_fig_p031_7.png]
Figure 8
Figure 8. Figure 8: Tree without and with attached cycles have very distinct topologies. [PITH_FULL_IMAGE:figures/full_fig_p032_8.png]
Figure 9
Figure 9. Figure 9: Neighbors Match Rewiring experiment on trees and trees with cycles, with increasing [PITH_FULL_IMAGE:figures/full_fig_p032_9.png]
Figure 10
Figure 10. Figure 10: Comparison of model performance between graph representations (Lift=None) and corre [PITH_FULL_IMAGE:figures/full_fig_p035_10.png]
Figure 11
Figure 11. Figure 11: Graph for the RingTransfer experiment. 37 [PITH_FULL_IMAGE:figures/full_fig_p037_11.png]
Figure 12
Figure 12. Figure 12: (a) The simplicial complex K consisting of nodes i, j, k, and edges {i, j}, {j, k}. (b) The adjacency relations on K, showing boundary, co-boundary, lower, and upper relations. (c) The influence graph G(S, B) representing the information flow between the entities. Shi…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

17 extracted references · 13 canonical work pages

  1. [2]

    2m boundary relations

    work page

  2. [3]

    2m co-boundary relations

    work page

  3. [4]

    P v∈V 2 deg(v) 2 ≤ 2md lower relations

    work page

  4. [5]

    None”, “Clique

    URL https://gudhi.inria.fr/doc/3.1.1/. Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- tional Conference on Learning Representations , 2022. URL https://openreview.net/ forum?id=7UmjRGzp-A. Floriano Tori, Vincent Holst,...

    arXiv 2021

  5. [9]

    Clique lifting of dimension 2 If G has |F | = k faces, then the clique K contains

    2m upper relations Note that we need to count the upper and lower relations for each direction of the edge so we get a factor of 2. Clique lifting of dimension 2 If G has |F | = k faces, then the clique K contains

    work page

  6. [10]

    2m + 3k boundary relations

    work page

  7. [11]

    2m + 3k co-boundary relations 48 Published as a conference paper at ICLR 2025

    work page 2025

  8. [12]

    P v∈V 2 deg(v) 2 + P σ∈F P τ ∈F χ(σ ∩ τ ) lower relations

    work page

Show all 17 references
  1. [13]

    Depending on the dataset under consideration, one may opt for a model like CIN where lower relations are ignored

    2m + 6k upper relations In dense graphs, the number of lower relations can be very large. Depending on the dataset under consideration, one may opt for a model like CIN where lower relations are ignored. Complete Graph We can provide precise estimates when we have a complete g...

  2. [14]

    nd(n − d − 1) boundary relations (if d >0)

  3. [15]

    nd(d + 1) co-boundary relations

  4. [16]

    nd(d + 1)(n − d − 1) lower relations (if d >0)

  5. [17]

    Computing the total number of cells gives 2n − 1

    nd(d + 1)(n − d − 1) upper relations , where the d > 0 condition comes from the fact that there isn’t a cell {} in the complex so there aren’t lower or co-boundary relations for zero dimensional cells. Computing the total number of cells gives 2n − 1. The total number of edges...

    2025

  6. [2019]

    George Dasoulas, Johannes F

    URL https://proceedings.neurips.cc/paper_files/paper/2019/ file/71ee911dd06428a96c143a0b135041a4-Paper.pdf. George Dasoulas, Johannes F. Lutzeyer, and Michalis Vazirgiannis. Learning parametrised graph shift operators. In International Conference on Learning Representations, 2...

    2019 arXiv

  7. [2020]

    Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzm ´an-S´aenz, and Karthikeyan Natesan Ramamurthy

    URL https://openreview.net/forum?id=6Tq18ySFpGU. Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzm ´an-S´aenz, and Karthikeyan Natesan Ramamurthy. Higher-order attention networks. arXiv preprint arXiv:2206.00606, 2(3):4, 2022. Mustafa Hajij, Ghada Zamzm...

    2022 arXiv

  8. [2021]

    Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna

    URL https://proceedings.neurips.cc/paper_files/paper/2021/ file/0cbed40c0d920b94126eaf5e707be1f5-Paper.pdf. Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence be- tween graph isomorphism testing and function approximation with GNNs. In Ad- vances in Ne...

    2021

  9. [2022]

    Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky

    URL https://openreview.net/forum?id=LIDvgVjpkZr. Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems , volume 30. Cur- ran Associates, Inc., 2017. URL https://pro...

    2017 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.