acceptodds
Under review as a conference paper at ICLR 2027

How Far Apart Is Distinguishable? Measuring the Expressivity of Topological Neural Networks through Weisfeiler–Leman and Co-Optimal Transport

Abstract

The Weisfeiler-Leman (WL) isomorphism test is a classical tool for analyzing the expressive power of message-passing graph neural networks (GNNs). Message-passing topological neural networks (TNNs) generalize message passing from graphs to higher-order combinatorial domains, such as simplicial and cell complexes. Recent work extends the WL test to attributed combinatorial complexes through the Combinatorial Complex Weisfeiler-Leman (CCWL) test, showing that CCWL upper-bounds the expressivity of a broad class of TNNs. Like the classical WL test, however, CCWL is binary, i.e., it decides whether two complexes can be distinguished, but not how different they are. For this reason, we turn CCWL into a quantitative distance by replacing its color refinement with a recursive distributional representation: for each cell, the messages passed through its boundary, coboundary, lower-adjacency, and upper-adjacency channels are represented as a distribution, and these channel-wise representations are recursively compared across refinement depths. We prove that the resulting distance is a pseudometric and that it vanishes exactly for pairs of attributed combinatorial complexes that CCWL cannot distinguish. We then connect it to co-optimal transport (Co-OT) between attributed combinatorial complexes through a convex relaxation of Co-OT. We show that this convex Co-OT discrepancy and the CCWL distance characterize the same zero set and correlate strongly. To the best of our knowledge, this is the first work to jointly connect TNNs, optimal transport, and CCWL expressivity, opening several future research directions.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Topological Neural Networks, Weisfeiler–Leman, Optimal Transport, Combinatorial Complexes, Expressivity, Higher-Order Learning

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_rzKAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the expressivity of message-passing neural networks on attributed combinatorial complexes (ACCs), that is, combinatorial complexes carrying an attribute at each cell, using Weisfeiler–Leman (WL) refinement and optimal transport. Building on the existing Combinatorial Complex Weisfeiler–Leman (CCWL) test, the authors define a base probability distribution on the cells of an ACC based on their ranks and freely chosen positive weights. They then recursively construct probability distributions by pushing forward this base distribution through representations obtained from CCWL-type refinement. This leads to a distance DCCWLD_{\mathrm{CCWL}} between ACCs, defined as the supremum over refinement depths of the Wasserstein distances between the corresponding probability distributions. Under suitable assumptions, the authors show that DCCWLD_{\mathrm{CCWL}} is a pseudometric and that it vanishes if and only if CCWL cannot distinguish the two complexes.

The authors further introduce a co-optimal transport distance between ACCs and show that a convex relaxation of this distance is a pseudometric with the same zero set as DCCWLD_{\mathrm{CCWL}}. They also provide experiments comparing the distances and investigating their practical usefulness.

Critical strengths
  • The paper provides an interesting mathematical approach, by extending the wasserstein based WL-distances on ACCs. The mathematics are involved and seem carefully developped.

  • Also the connection to co-optimal transport is interesting and obtaining the tractable convex relaxation with the same zero-set is a nice result.

Critical weaknesses

My main concern is the motivation and theoretical significance of the proposed distances.

  • The construction of DCCWLD_{\mathrm{CCWL}} involves several freely chosen parameters, such as the weights assigned to different ranks and neighborhood channels, as well as the underlying metric. While the authors show that the zero set is independent of these choices, the actual distances depend on them. It is unclear how these parameters should be chosen and to what extent the resulting distances are meaningful.

  • More generally, I am not convinced what the proposed distances actually tell us about the expressivity of topological neural networks. The main theoretical results establish equivalence of zero sets with CCWL indistinguishability, but it is unclear what additional insights are obtained from the positive values of the distances. The convex relaxation of Co-OT provides an efficiently computable characterization of CCWL indistinguishability, but the theoretical significance of its numerical values remains unclear.

Questions for authors
  • Is there a natural choice of the weights and the underlying metric? How sensitive are the distances and the experimental results to these choices?

  • Can the authors explain more concretely what the numerical values of the proposed distances tell us about the expressivity of TNNs? For example, is there a quantitative relation between these distances and differences in network outputs?

1 comment

We appreciate the careful summary and the two questions.

Q11: Is there a natural choice of the weights and the underlying metric? How sensitive are the distances and the experimental results to these choices?

There is no unique one, and for the theory none is needed, as the results hold for all valid weights. However, there may be natural choices depending on the settings. For examples (i) when symmetry or equivariance is desired, uniform α\alpha and uniform ww are the only choices invariant under relabeling the channels and the ranks (ii) when we would like to match a model class. Theorem C.9 makes the choice concrete for TNNs. The rank weights in the bound are those of the network's readout (the readout in Theorem C.9), so ww should equal the readout weights of the architecture whose outputs the distance is meant to control.

To quantify the sensitivity, we recomputed DCCWLD _ {CCWL} on MUTAG, changing one parameter at a time from the default: αid∈{0.1,0.4}\alpha _ {id}\in\lbrace 0.1,0.4\rbrace; boundary/coboundary-heavy α=(0.2,0.3,0.3,0.1,0.1)\alpha=(0.2,0.3,0.3,0.1,0.1) and adjacency-heavy α=(0.2,0.1,0.1,0.3,0.3)\alpha=(0.2,0.1,0.1,0.3,0.3) over (id,B,C,↓,↑)(id,B,C,\downarrow,\uparrow); rank weights w=(2,1,1)w=(2,1,1) and (1,1,2)(1,1,2).

settingSpearman correlations1-NN acc using D(4)D^{(4)}1-NN acc using D^4\widehat D _ 4
default (uniform α\alpha, ww; difference-graded d0d _ 0)1 / 182.55 ± 5.2883.57 ± 3.61
αid=0.1\alpha _ {id}=0.10.997 / 1.00082.55 ± 5.2884.00 ± 3.38
αid=0.4\alpha _ {id}=0.40.983 / 1.00082.55 ± 5.2883.57 ± 3.61
boundary/coboundary-heavy α\alpha1.000 / 1.00082.98 ± 5.2184.00 ± 3.38
adjacency-heavy α\alpha1.000 / 1.00082.55 ± 5.2883.57 ± 3.61
w=(2,1,1)w=(2,1,1)0.999 / 0.99482.98 ± 5.2183.15 ± 2.50
w=(1,1,2)w=(1,1,2)0.992 / 0.98482.55 ± 5.2883.15 ± 3.15

In every setting the zero set is exactly the same pairs, as the theory predicts. The weights matter very little: under every change of α\alpha and ww the distances keep a rank correlation of at least 0.98 with the default over all pairs, and 1-NN accuracy moves by at most 0.5 points, well within one standard deviation across splits.

Q12: What do the numerical values of the distances tell us about TNN expressivity? Is there a quantitative relation with differences in network outputs?

Yes. The revision adds a Lipschitz theorem (Theorem C.9, App. C.5.1), stated in full in our response to Reviewer FZE6. For any TT-layer message-passing TNN with mean-aggregated messages over the four CCWL channels and a rank-weighted mean readout, with a bounded, Lipschitz input encoder and Lipschitz layers,

∥F(X)−F(Y)∥≤LoutΛT∗DCCWL(T)(X,Y)≤LoutΛT∗DCCWL(X,Y),\Vert F( X)-F(Y)\Vert \le L _ {out} \Lambda^\ast _ T D^{(T)} _ {CCWL}( X,Y) \le L _ {out} \Lambda^\ast _ T D _ {CCWL}(X,Y),

where ΛT∗\Lambda^\ast _ T is explicit in the layers' Lipschitz constants and the channel weights. The proof proceeds by induction on the layers, following Chen et al. (2023) for MPNNs.

This is what a positive value tells us: two complexes that such a network separates by a margin ε\varepsilon must be at distance at least ε/(LoutΛT∗)\varepsilon/(L _ {out}\Lambda^\ast _ T). The bound is depth-matched, so DCCWL(T)D^{(T)} _ {CCWL} describes what a network of depth TT can do. The bounds can be computed explicitly.

Reviewer_Un1pOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors extend the WL distance of Chen et al. (2022) to combinatorial complexes, using a similar construction but based on the recent definition of the 1-WL test for combinatorial complexes (CCWL). They also present co-optimal transport (Co-OT) as an alternative to the CCWL distance, and show the two are highly correlated. The appendices also include 1-NN classification and a distance-based regularizer for TNNs.

Critical strengths
  • The extension of the WL distance to accommodate the diverse neighborhood structures in combinatorial complexes is a natural and timely step. The authors prove that the distance is a pseudometric and that it vanishes exactly on CCWL-equivalent complexes.

  • The authors also propose a relaxed Co-OT formulation with the same zero set as their CCWL distance (which is convex and can be solved as an LP), and show in the appendix that the unrelaxed version is strictly more discriminative.

Critical weaknesses
  • It is not clear what is gained by the relaxed Co-OT formulation. Since it is convex, I would expect the advantage to be computational, but there is no complexity analysis or wall-clock comparison against the CCWL distance.

  • The experimental results are relatively weak. The CCWL distances underperform the WL distance of Chen et al. on NCI1 and NCI109. Meanwhile, it is not clear why both Co-OT formulations outperform the CCWL distance on all datasets. Furthermore, the regularizer gains in Table 2 are mostly within one standard deviation.

  • Combining the measures stemming from different neighborhood aggregations relies on multiple weights (α\alpha's and ww's). However the authors do not elaborate on how important these choices, i.e. their specific values, are to the overall theory and empirical performance.

Questions for authors
  • What is the computational cost of the CCWL distance and of convex Co-OT as a function of the number of cells and ranks?

  • Can the authors provide a wall-clock time comparison between CCWL and both the relaxed and unrelaxed Co-OT formulations?

  • Can the authors elaborate further on the results in the appendix? (see the second bullet in 'Critical Weaknesses').

  • Please elaborate on the importance of α\alpha's and ww's, as well as how they are set in the experiments.

4 comments

We thank the reviewer for the clear summary and the insightful questions.

Q6: What is gained by the relaxed Co-OT formulation?

We would like to clarify that Convexity results in a gain in exactness rather than in computational speed. The unrelaxed objective is bilinear in adjacent couplings and is minimized by block-coordinate descent, which returns a local optimum whose value depends on the initialization. The relaxed problem is a linear program solved to a global optimum, certified by its dual. The relaxation also gives the right zero set: the unrelaxed Co-OT is strictly finer than CCWL (Prop. D.8), so it separates pairs that no CCWL-bounded TNN can separate, whereas the convex relaxation has exactly the CCWL zero set (Prop. 4.2), which makes it an optimal transport formulation of CCWL expressivity. In speed, convex Co-OT is faster than DCCWLD _ {CCWL} on small complexes and on complexes spread over many ranks, and slower on large ones (see Q7–Q8).

Q7: Computational cost as a function of the number of cells and ranks.

We thank the reviewer for pointing out the need for the computaion analysis. We added App. E.1. For complexes with NN and MM cells, ranks 0,…,R0,\dots,R and rank sizes nr,mrn _ r, m _ r:

  • DCCWLD _ {CCWL} to depth TT solves exactly 4NMT4NMT local transport problems, between neighborhood contexts of at most Δ\Delta atoms, plus T+1T+1 global problems of size N×MN\times M. That is O(TNMΔ3log⁡Δ+TNM(N+M)log⁡(N+M))O\bigl(TNM \Delta^3\log\Delta + TNM(N+M)\log(N+M)\bigr) time and O(NM)O(NM) memory, with the network simplex for each problem. The count is exact, it is linear in depth, and one pass returns every D(t)D^{(t)}, t≤Tt\le T. The number of ranks does not enter the count; it enters only through the context sizes Δ\Delta.
  • Convex Co-OT is one linear program with ∑rnrmr+∑r≥1(nr−1mr+nrmr−1)\sum _ r n _ r m _ r+\sum _ {r\ge1}(n _ {r-1}m _ r+n _ r m _ {r-1}) variables. For balanced ranks this is NM(3R+1)/(R+1)2NM(3R+1)/(R+1)^2, which equals NMNM for R≤1R\le1 and decreases as Θ(NM/R)\Theta(NM/R): the couplings are block diagonal by rank, so more ranks make the program smaller. Its time is that of a general LP in this many variables, superlinear in the number of variables.
  • Unrelaxed Co-OT costs SS restarts ×\times at most II sweeps, each sweep solving R+1R+1 rank-wise transport problems of size nr×mrn _ r\times m _ r.

Q8: Wall-clock comparison of DCCWLD _ {CCWL} with relaxed and unrelaxed Co-OT.

We added App. E.2 of wall clock times all of them on the same CPU core on random rank-2 complexes:

  • Number of cells (24 to 198, Figure 8). DCCWLD _ {CCWL} grows with log-log slope 1.99 and takes 11 s per pair at 198 cells to depth 10. Convex Co-OT grows with slope 4.18: it is the fastest exact method below 60–90 cells and 10×10\times slower than DCCWLD _ {CCWL} at 198 cells. A single unrelaxed Co-OT descent takes milliseconds. With the 1000 restarts we use, it costs between half of and slightly more than DCCWL(10)D^{(10)} _ {CCWL}, and still without an optimality guarantee.
  • Depth (Figure 9). The time of DCCWLD _ {CCWL} is linear in TT (R2≥0.9999R^2\ge0.9999) at every size, as the exact count predicts.
  • Ranks (Figure 10). For 60 cells spread over ranks 0,…,R0,\dots,R, convex Co-OT becomes 4.6×4.6\times faster from R=1R=1 to R=4R=4, as its program shrinks. DCCWLD _ {CCWL} becomes 2.5×2.5\times slower, because contexts grow.

All-pairs computation on large datasets or large complexes nevertheless remains costly, and we leave more efficient distances as future work.

Q9: The results in the appendix.

We agree that DCCWLD _ {CCWL} is below on these on NCI1 and NCI109, and we refer the reviewer to our response in On Table 1 (NCI1, NCI109)., the last point in our response to Reviewer 5xzs.

Why both Co-OT formulations score higher than DCCWLD _ {CCWL}. The distances share a zero set (exactly, for convex Co-OT), but on distinguishable pairs their values are different functions, so nearest neighbors can differ. The CCWL distances in Table 1 are truncated at depth t≤4t\le4, Co-OT instead solves one coupling per rank for the whole complex, jointly constrained by incidence, so it aligns the entire complex at once. On small molecules this global alignment appears to match the labels better.

Regularizer gains in Table 2 mostly within one standard deviation. We agree. To test the distance where it can matter statistically significantly, we added App. B.3. A trained backbone (CCIN, CWN or CIN++) is combined at inference with a kk-NN vote under DCCWLD _ {CCWL}, with the mixing weight selected on a validation split. With all labels the gain is small (+0.2+0.2 to +0.4+0.4 points), consistent with Table 2. With 25% or 10% of the labels, adding DCCWLD _ {CCWL} improves accuracy in 31 of 36 configurations (3 backbones ×\times 6 datasets ×\times 2 label fractions), by +1.52+1.52 points on average (p<10−4p \lt 10^{-4}). This includes NCI1 and NCI109, where all low-label configurations improve. This helps identify a regime where the distance can be more helpful.

Q10: Importance of the α\alpha's and ω\omega's, and how they are set in the experiments.

Role of the parameters. The channel weights αa\alpha _ a, a∈{id,B,C,↓,↑}a\in\lbrace id,B,C,\downarrow,\uparrow\rbrace, are the masses that the five channels receive in a cell's refined label. The rank weights wrw _ r define the base measure μX\mu _ { X}: rank rr receives mass wr/sXw _ r/s _ { X}, spread uniformly over its cells. They decide how much each rank contributes to the global transport problem.

Setting in the experiments. All experiments use uniform weights: αa=1/5\alpha _ a=1/5 for all five channels and wr=1w _ r=1 for every rank, so that each rank present carries mass 1/∣RX∣1/\vert R _ {X}\vert. None of these values was tuned on any dataset. We will state them explicitly in the experimental section of the next revision.

Is there a natural choice? There is no unique one, and for the theory none is needed, as the results hold for all valid weights. However, there may be natural choices depending on the settings. For examples (i) when symmetry or equivariance is desired, uniform α\alpha and uniform ww are the only choices invariant under relabeling the channels and the ranks (ii) when we would like to match a model class. Theorem C.9 makes the choice concrete for TNNs. The rank weights in the bound are those of the network's readout (the readout in Theorem C.9), so ww should equal the readout weights of the architecture whose outputs the distance is meant to control.

To quantify the sensitivity, we recomputed DCCWLD _ {CCWL} on MUTAG, changing one parameter at a time from the default: αid∈{0.1,0.4}\alpha _ {id}\in\lbrace 0.1,0.4\rbrace; boundary/coboundary-heavy α=(0.2,0.3,0.3,0.1,0.1)\alpha=(0.2,0.3,0.3,0.1,0.1) and adjacency-heavy α=(0.2,0.1,0.1,0.3,0.3)\alpha=(0.2,0.1,0.1,0.3,0.3) over (id,B,C,↓,↑)(id,B,C,\downarrow,\uparrow); rank weights w=(2,1,1)w=(2,1,1) and (1,1,2)(1,1,2).

settingSpearman correlations1-NN acc using D(4)D^{(4)}1-NN acc using D^4\widehat D _ 4
default (uniform α\alpha, ww; difference-graded d0d _ 0)1 / 182.55 ± 5.2883.57 ± 3.61
αid=0.1\alpha _ {id}=0.10.997 / 1.00082.55 ± 5.2884.00 ± 3.38
αid=0.4\alpha _ {id}=0.40.983 / 1.00082.55 ± 5.2883.57 ± 3.61
boundary/coboundary-heavy α\alpha1.000 / 1.00082.98 ± 5.2184.00 ± 3.38
adjacency-heavy α\alpha1.000 / 1.00082.55 ± 5.2883.57 ± 3.61
w=(2,1,1)w=(2,1,1)0.999 / 0.99482.98 ± 5.2183.15 ± 2.50
w=(1,1,2)w=(1,1,2)0.992 / 0.98482.55 ± 5.2883.15 ± 3.15

In every setting the zero set is exactly the same pairs, as the theory predicts. The weights matter very little: under every change of α\alpha and ww the distances keep a rank correlation of at least 0.98 with the default over all pairs, and 1-NN accuracy moves by at most 0.5 points, well within one standard deviation across splits.

Thank you for the detailed response and revision. While the experimental results are not especially strong, the contribution is primarily theoretical, and the complexity analysis, the analysis of the weights and the new Lipschitz theorem help position the work well; I now consider it a valuable contribution to the literature. I am raising my score accordingly, and I encourage the authors to move the weight analysis and settings from the rebuttal into the paper.

We thank the reviewer again for their valuable insights and expertise, which helped us sharpen this paper. We are truly glad that the reviewer sees the value of our work as we intended: this is primarily a theoretical paper that aims to connect TNN expressivity, CCWL with optimal transport, in the hope of offering a new perspective for understanding message-passing TNNs. As suggested, we will restructure the main paper to include the Lipschitz theorem, and integrate weight analysis and the experimental settings from the rebuttal.

Reviewer_5xzsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper turns the Combinatorial Complex WL test (CCWL) into a quantitative distance. Following the WL distance of Chen et al. (2022) for graphs, each cell is represented by the distributions of messages over its boundary, coboundary, lower adjacency and upper adjacency channels, and these are compared recursively by Wasserstein distances (Def 3.1). The authors prove that the resulting CCWL distance is a pseudometric (Prop 3.2) that vanishes exactly on pairs CCWL cannot distinguish (Prop 3.3), so any TNN bounded by CCWL gives equal outputs when the distance is zero (Cor 3.4). They then define co-optimal transport between attributed combinatorial complexes, together with a convex relaxation that penalizes incidence mismatch residuals, and show that the relaxation has the same zero set as the CCWL distance (Prop 4.2).

Empirically, the two distances correlate strongly on 240 synthetic pairs of rank-2 complexes (Fig 2). The appendix adds 1-NN classification on five TU datasets and the use of the distance as a regularizer for three cellular networks.

Critical strengths
  1. The theory is correct and carefully done. The pseudometric property and both directions of the zero-set equivalence seems correct, and forcing every coupling to preserve channels through an infinite cross-channel cost is a clean device (Prop C.1). The example in D.5, where unrelaxed Co-OT separates a pair that CCWL cannot, nicely shows why the relaxation is needed.

  2. Connecting CCWL, a recursive OT distance and a convex Co-OT relaxation is a natural step for topological deep learning. The convex Co-OT distance is also the best of the tested distances for 1-NN classification on all five datasets (Table 1).

Critical weaknesses
  1. The contribution is incremental. Def 3.1 and Prop 3.3 follow the WL distance of Chen et al. (2022) channel by channel, and the main result, Prop 4.2, reduces to a classical theorem. Its proof shows that zero convex Co-OT gives a doubly stochastic S with AXS=SAYA_{\mathcal X} S = S A_{\mathcal Y} on the rank-graded incidence graph (lines 1589-1593), i.e. a fractional isomorphism, and then derives every CCWL count from this identity. Together with Tinhofer's theorem, this means that CCWL equivalence coincides with 1-WL equivalence on the attributed incidence graph, so the lower and upper adjacency channels add no distinguishing power here. Tinhofer and fractional isomorphism are not cited, and neither is Böker et al. (NeurIPS 2023), who study fine-grained expressivity of GNNs and state this background. The paper also does not answer the open questions listed by Chen et al. or Böker et al.

  2. There is no quantitative link between the distance and TNNs, which is what is needed to measure expressivity. Cor 3.4 only says that a zero distance gives equal outputs (lines 375-378). There is no Lipschitz or Hölder bound of TNN outputs in DCCWLD_{\mathrm{CCWL}} and no converse, and the conclusion leaves this as future work (lines 484-485). Rauchwerger et al. and Böker et al. prove such results for MPNNs. There is also no inequality between DCCWLD_{\mathrm{CCWL}} and convex Co-OT beyond equal zero sets. The evidence that they agree away from zero is one run on 240 synthetic pairs (Fig 2, lines 462-465) with no seeds, size range or null baseline. In Table 1, DCCWLD_{\mathrm{CCWL}} is 3 to 6 points below the WL distance of Chen et al. on NCI1 and NCI109. So the question in the title is not yet answered.

Questions for authors

Clarifications that could change my assessment:

  1. Is CCWL equivalent to 1-WL on the attributed rank-graded incidence graph? The proof of Prop 4.2 together with Tinhofer's theorem seems to imply it. If so, what do the lower and upper adjacency channels add, and how does DCCWLD_{\mathrm{CCWL}} compare with the WL distance of Chen et al. computed on that graph?

  2. Can you prove a Lipschitz or Hölder bound of message-passing TNN outputs in DCCWLD_{\mathrm{CCWL}}, or an inequality between DCCWLD_{\mathrm{CCWL}} and convex Co-OT? Without one, what does a small nonzero distance say about expressivity?

  3. For Fig 2, please give the generator, the size range, the seeds, which correlation coefficient is reported, and the weights αa\alpha_a, wrw_r and ground metric d0d_0 used.

  4. What is the runtime of DCCWLD_{\mathrm{CCWL}} and of convex Co-OT as the complexes grow?

4 comments

We thank the reviewer for the careful reading and for pointing out the connection to Tinhofer's theorem. Below we list our responses.

Q2: Is CCWL equivalent to 1-WL on the attributed rank-graded incidence graph? What do the lower and upper adjacency channels add, and how does DCCWLD _ {CCWL} compare with the WL distance of Chen et al. on that graph?

Yes, in the limit, and we thank the reviewer for this observation. We now state it as a corollary (App. C.6, Corollary C.14): CCWL equivalence, 1-WL equivalence on the rank-colored incidence graph HH, fractional isomorphism of HH (Tinhofer's theorem, Theorem C.13), DCCWL=0D _ {CCWL}=0 and DCo-OTcvx=0D^{\mathrm{cvx}} _ {\text{Co-OT}}=0 all coincide. We approached to the problem from the optimal transport (Gromov–Wasserstein / Co-OT) side [1] and had not made this connection explicit. The revision now cites Tinhofer (1986, 1991), Ramana et al. (1994), Arvind et al. for the vertex-colored form, and Böker et al. (2023). This redundancy in the limit is shared by other higher-order tests: Bodnar et al. (2021) show that some channels can be dropped from simplicial and cellular WL without loss of distinguishing power.

The adjacency channels matter at finite depth, and a TNN always has finite depth. Corollary C.14(i) shows that CCWL at depth tt is matched by 1-WL on HH only at depth up to 2t2t, and the factor two is attained (Remark C.15). The reason is that a lower or upper adjacency pair is a boundary or coboundary multiset at a neighbor, which 1-WL on HH must first record at the neighbor and then transport, two rounds where CCWL takes one.

This is also how DCCWLD _ {CCWL} differs from the WL distance of Chen et al. computed on HH. The two have the same zero set in the limit, but at depth TT Chen et al.'s distance on HH vanishes on the pairs above.

As empirical verifications, we show the gap on real data. We measured on MUTAG, COX2, NCI1 and NCI109. The following table counts pairs that 1-WL color refinement on the incidence graph does not distinguish at depth tt but CCWL does. In parentheses is the depth on WL needed to match CCWL at depth tt.

datasetpairst=1t=1t=2t=2t=3t=3t=4t=4
MUTAG17,57899 (2)42 (4)1 (4)1 (7)
COX2108,81191 (2)35 (4)5 (4)0
NCI18,078,19097 (2)64 (4)10 (4)0
NCI1098,090,25392 (2)51 (4)8 (4)0

The reverse count (separated on WL but not by CCWL) is 00 everywhere, as the corollary predicts.

We also show that TNNs captures the gap. For random TT-layer TNNs (10 networks per depth), we checked whether the gap pairs receive different outputs. At T=1T=1, between 90% and 100% of the gap pairs are separated by every network (MUTAG 92/99, COX2 91/91, NCI1 89/97, NCI109 83/92). At T=2T=2 the figures are MUTAG 40/42, COX2 5/35, NCI1 42/64 and NCI109 32/51. On each of these pairs, a depth-TT distance on WL is zero while the TNN outputs differ. On such pairs no bound of TNN outputs by that distance can hold. Our new Lipschitz theorem bounds a TT-layer TNN by DCCWL(T)D^{(T)} _ {CCWL} at matching depth.

[1] Chung, J., Song, E., Kim, W.H. & Park, G.. (2026). Convex Distance Operator Transport: A Convex and Geometry-Preserving Formulation. ICML 2026.

On "Def. 3.1 and Prop. 3.3 follow Chen et al. channel by channel": the construction is inspired by Chen et al., as we state in Section 3, but it differs in three ways. The adjacency channels are joint distributions over neighbor–mediator pairs. The base measure is rank-balanced, matching the TNN readout, rather than degree-proportional. And it is these choices that make the depth-matched Lipschitz bound possible, with constants built from the channel and rank weights.

Q3: Can you prove a Lipschitz or Hölder bound o...?

Yes; we kindly refer the reviewer to our response to Q1 to Reviewer FZE6 for the full statement. In short, the revision adds Theorem C.9 (App. C.5.1). For any TT-layer message-passing TNN with mean-aggregated messages over the four CCWL channels and a rank-weighted mean readout, with a bounded Lipschitz input encoder and Lipschitz layers,

∥F(X)−F(Y)∥≤LoutΛT∗DCCWL(T)(X,Y)≤LoutΛT∗DCCWL(X,Y),\Vert F(X)-F(Y)\Vert \le L _ {out}\Lambda^\ast _ T D^{(T)} _ {CCWL}(X,Y)\le L _ {out}\Lambda^\ast _ T D _ {CCWL}( X,Y),

with an explicit constant ΛT∗\Lambda^\ast _ T built from the layers' Lipschitz constants and the channel weights. The proof proceeds by induction on the layers, following Chen et al. (2023) for MPNNs. We verify it on all pairs of MUTAG and COX2 (App. C.5.2): outputs agree to rounding error (≤1.9×10−16\le 1.9\times10^{-16}) on the zero set, the output-to-distance ratio is finite, and the Spearman correlation between output differences and DCCWL(T)D^{(T)} _ {CCWL} rises with depth from 0.62 to 0.85 (MUTAG) and from 0.48 to 0.64 (COX2). A small nonzero distance therefore says that no TT-layer TNN of this class with given Lipschitz constants can place the two complexes far apart.

Due to the time limit, we leave such bounds for convex Co-OT to future work.

Q4: Figure 2 with only one run.

The 240 pairs are built from three base rank-2 complexes with rank sizes (n0,n1,n2)=(6,9,4)(n _ 0,n _ 1,n _ 2)=(6,9,4), (8,14,6)(8,14,6) and (10,20,8)(10,20,8), with categorical attributes, so each complex has 15–41 cells. DCCWLD _ {CCWL} uses uniform channel weights αa=1/5\alpha _ a=1/5, rank weights wr=1w _ r=1 and the for q0(x)=(c(x),rk(x),m(x),n(X))q _ 0(x)=(c(x),\mathrm{rk}(x), m(x), n( X)),

d0(q0(x),q0(y))=M4[1{c(x)≠c(y)}+1{rk(x)≠rk(y)}+14∑j=14δ(mj(x),mj(y))+1R+1∑r=0Rδ(nr(X),nr(Y))],δ(p,q)=∣p−q∣1+∣p−q∣,d _ 0\bigl(q _ 0(x),q _ 0(y)\bigr)=\tfrac{M}{4}\Bigl[\mathbf 1\lbrace c(x)\neq c(y)\rbrace +\mathbf 1\lbrace \mathrm{rk}(x)\neq \mathrm{rk}(y)\rbrace +\tfrac14\sum _ {j=1}^{4}\delta\bigl(m _ j(x),m _ j(y)\bigr)+\tfrac{1}{R+1}\sum _ {r=0}^{R}\delta\bigl(n _ r(X),n _ r(Y)\bigr)\Bigr],\qquad \delta(p,q)=\frac{\vert p-q\vert }{1+\vert p-q\vert },

with M=1M=1, where m(x)m(x) are the sizes of the four neighborhood contexts of xx (boundary, coboundary, lower and upper adjacency) and n(X)n( X) the numbers of cells per rank (zero-padded to the common maximal rank RR).

To address the single seed, we ran the experiment five times with the same design but fresh randomness. The following table gives Spearman's ρ\rho with DCCWLD _ {CCWL}, mean ±\pm sd over the five seeds; about 80 pairs per seed have equal sizes.

all pairsequal sizedifferent size
convex Co-OT, full (βr=τr\beta _ r=\tau _ r)0.959±0.0080.959\pm0.0080.883±0.0430.883\pm0.0430.984±0.0030.984\pm0.003
Co-OT, full0.959±0.0080.959\pm0.0080.882±0.0430.882\pm0.0430.985±0.0020.985\pm0.002
convex Co-OT, structure only (βr=0\beta _ r=0)0.758±0.0220.758\pm0.0220.764±0.0800.764\pm0.0800.855±0.0110.855\pm0.011
Co-OT, structure only0.833±0.0190.833\pm0.0190.826±0.0440.826\pm0.0440.921±0.0080.921\pm0.008
attribute term only0.795±0.0110.795\pm0.0110.188±0.0770.188\pm0.0770.858±0.0100.858\pm0.010
baseline: size-only distance0.913±0.0100.913\pm0.010–0.914±0.0090.914\pm0.009

Q5: Runtime as the complexes grow.

We added App. E to address the computation complexity, supported with wall-clock analysis. We would like to be upfront that neither distance is efficient in its current implementation. One pass of DCCWLD _ {CCWL} to depth TT solves exactly 4NMT4NMT small transport problems for complexes with NN and MM cells, so its time is quadratic in the number of cells and linear in depth. Convex Co-OT is one linear program whose number of variables depends on the distribution of cells over ranks. Spreading a fixed number of cells over more ranks shrinks the program (Figure 10). Both computations parallelize trivially over pairs, which is how we computed all-pairs distances on the benchmarks, but all-pairs computation on large datasets or large complexes remains costly. We therefore leave more efficient distances, for example entropic or sliced approximations of the inner transport problems, as future work.

On Table 1 (NCI1, NCI109). We agree that DCCWLD _ {CCWL} is below the WL distance of Chen et al. in 1-NN accuracy on these two datasets. 1-NN accuracy is a more complicated signal than it may appear, because it involves the labels as well as the distance. It is high when complexes with the same label are close, which depends on whether the labels are driven by the structural differences the distance emphasizes. Which of these distances aligns better with a given labeling, as in NCI1 and NCI109, varies from dataset to dataset. To test more directly whether the geometry of DCCWLD _ {CCWL} is useful to TNNs, we added App. B.3. Combining a trained backbone (CCIN, CWN or CIN++) with a nearest-neighbor correction under DCCWLD _ {CCWL} at inference improves accuracy in 31 of 36 low-label configurations (+1.52+1.52 points on average, with p<10−4p \lt 10^{-4}), including NCI1 and NCI109, where the gains are smaller but positive.

Thank you for the detailed replies. The incidence-graph equivalence, finite-depth comparison, and runtime analysis clarify several of my concerns. The new Lipschitz theorem provides the missing quantitative connection to TNN outputs, but its stated assumptions need to match the proof. The proof uses a uniform separation between different ranks; please explicitly assume the metric of Remark C.8, or an appropriate rank-separation condition with an adjusted constant. The repeated correlation experiments and equal-size controls are useful, but the exact seeds and full generation procedure are still missing. I will maintain my score of 2.

AuthorsOpenReview ↗

We thank the reviewer for the prompt reply and the careful reading of our response.

Follow-up on Q3 (Lipschitz theorem)

We thank the reviewer for catching this. The proof indeed uses the uniform separation between ranks given by the metric of Remark C.8, and the theorem now assumes it explicitly. Theorem C.9 is stated with d0d_0 the metric of Remark C.8. Its rank term gives d0(q0(x),q0(y))≥M/4d_0(q_0(x),q_0(y))\ge M/4 whenever rk(x)≠rk(y)\mathrm{rk}(x)\neq\mathrm{rk}(y). More generally, any d0d_0 with a rank-separation constant κ>0\kappa>0 (d0≥κd_0\ge\kappa across ranks) gives the same result with 8B/(αidTM)8B/(\alpha_{id}^TM) replaced by 2B/(αidTκ)2B/(\alpha_{id}^T\kappa).

Follow-up on Q4 (Figure 2): seeds, code and complete procedure

We thank the reviewer for pressing on this point. The submitted Figure 2 was a single draw without a fixed seed. To make the experiment fully reproducible, we now provide one self-contained script, fig2_synthetic.py (NumPy, SciPy and POT only) in the suplement material. It generates the pairs, computes both distances and the two ablations with exact solvers, runs zero-set self-tests, and reports the statistics. All randomness comes from a single numpy.random.default_rng(seed), consumed in the fixed order of the design below. The distances use exact solvers and contain no randomness. We report seeds 0, 1, 2, 3, 4.

Generator. A base complex Base(n0,n1,n2)\mathrm{Base}(n_0,n_1,n_2) is drawn as follows. The vertices are {0,…,n0−1}\lbrace 0,\dots,n_0-1\rbrace. The edges are n1n_1 distinct vertex pairs drawn uniformly without replacement (a uniform G(n0,n1)G(n_0,n_1) graph). The draw is repeated if a vertex is isolated or there are fewer than n2n_2 triangles. The rank-2 cells are n2n_2 triangles drawn uniformly without replacement, and incidence is containment. Every cell of every rank receives an attribute drawn uniformly from three values. The base configurations are (n0,n1,n2)∈{(6,9,4),(8,14,6),(10,20,8)}(n_0,n_1,n_2)\in\lbrace (6,9,4),(8,14,6),(10,20,8)\rbrace, 80 pairs each. Each pair draws a fresh base complex X\mathcal X, and its partner Y\mathcal Y comes from one of three families.

  • Perturbation, 72 pairs: configuration ×\times kflip∈{1,3,6}k_{\mathrm{flip}}\in\lbrace 1,3,6\rbrace ×\times kattr∈{0,2}k_{\mathrm{attr}}\in\lbrace 0,2\rbrace ×\times 4 replicates. Y\mathcal Y is X\mathcal X with kflipk_{\mathrm{flip}} distinct incidence entries flipped, chosen uniformly among all n0n1+n1n2n_0n_1+n_1n_2 entries, and kattrk_{\mathrm{attr}} distinct cells given fresh uniform attributes. Flipping entries directly makes Y\mathcal Y a general combinatorial complex rather than a simplicial one.
  • Resize, 96 pairs: configuration ×\times ksize∈{1,2}k_{\mathrm{size}}\in\lbrace 1,2\rbrace ×\times kflip∈{0,2}k_{\mathrm{flip}}\in\lbrace 0,2\rbrace ×\times kattr∈{0,2}k_{\mathrm{attr}}\in\lbrace 0,2\rbrace ×\times 4 replicates. After kflipk_{\mathrm{flip}} flips, each of ksizek_{\mathrm{size}} operations is drawn uniformly from (add, delete) ×\times (rank 0, 1, 2). An added cell gets a uniform attribute and Bernoulli incidence entries at the current density of each adjacent incidence matrix. A deleted cell is drawn uniformly among the original cells of that rank and removed with its incidence row or column. Finally, kattrk_{\mathrm{attr}} attributes are resampled.
  • Independent, 72 pairs: 24 per configuration. With probability 12\tfrac12, Y\mathcal Y is a base complex of a uniformly chosen base configuration. Otherwise Y=Base(n0,n1,n2)\mathcal Y=\mathrm{Base}(n_0,n_1,n_2) with n0∼U{5,…,12}n_0\sim U\lbrace 5,\dots,12\rbrace, n1∼U{n0+1,…,min⁡((n02),3n0−2)}n_1\sim U\lbrace n_0+1,\dots,\min(\binom{n_0}{2},3n_0-2)\rbrace and n2∼U{3,…,10}n_2\sim U\lbrace 3,\dots,10\rbrace, redrawn if infeasible.

Complexes have 16–55 cells. Per seed, 86–99 of the 240 pairs have equal rank sizes.

Results (Spearman ρ\rho with D^4\widehat D_4, mean ±\pm sd over seeds 0–4):

all pairsequal sizedifferent sizesubmitted Figure 2 (all / equal / different)
attribute + structure0.986±0.0030.986\pm0.0030.960±0.0120.960\pm0.0120.985±0.0010.985\pm0.0010.9880.988 / 0.9860.986 / 0.9870.987
attribute only (τr=0\tau_r=0)0.820±0.0240.820\pm0.0240.579±0.0650.579\pm0.0650.878±0.0270.878\pm0.0270.8720.872 / 0.6530.653 / 0.9210.921
structure only (βr=0\beta_r=0)0.858±0.0160.858\pm0.0160.831±0.0500.831\pm0.0500.857±0.0110.857\pm0.0110.8470.847 / 0.7590.759 / 0.8680.868

Seed 0 gives ρ=0.987\rho=0.987 (p=1.0×10−192p=1.0\times10^{-192}), 0.8250.825 (p=8.2×10−61p=8.2\times10^{-61}) and 0.8610.861 (p=8.1×10−72p=8.1\times10^{-72}). The conclusions of the submitted figure hold in every seed.

Relation to the five-seed table in our previous reply: That table came from an independent re-implementation of the same 72/96/72 design with 2-cells drawn among cycles of length 3–6, depth 15, and unrelaxed Co-OT added. The two implementations tell the same story.

We hope this addresses your concerns, and we are happy to provide any further details or clarification.

Reviewer_FZE6OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses the issue of distinguishability in topological deep learning. The authors propose a new distance metric and prove that it is a pseudometric whose zero set equals CCWL equivalence. They carry out experiments to show a correlation between this distance and convex Co-OT distances.

Critical strengths

The mathematical work in the paper is appreciated. However, there is no link between the proposed distance and TNN behavior, which is the main motivation for this paper.

Critical weaknesses

The paper's title focuses on "Measuring the Expressivity". However, the results do not show it. There is no quantitative statement showing that a small distance implies similar outputs, and there is no universality or generalization result.

Questions for authors

Can you prove any bound relating D_CCWL or D^cvx_Co-OT to differences in outputs of a message-passing TNN (Lipschitz or continuity), as done for GNNs in prior work? If not, why is it a measure of expressivity?

1 comment

We thank the reviewer for the constructive comments. We have uploaded a revision with a Lipschitz theorem for message-passing TNNs (Theorem C.9, App. C.5.1) and its empirical verification(App. C.5.2). We summarize both here so that the response is self-contained.

Q1: Can you prove a bound relating DCCWLD _ {CCWL} to differences in TNN outputs?

Yes, (Theorem C.9). Consider any TT-layer message-passing TNN that updates each cell from its own state and from mean-aggregated messages over the four CCWL channels, followed by a rank-weighted mean readout F(X)=fout(∑rwrsX∣Xr∣∑x∈Xrh(T)(x))F(X)=f _ {out}\bigl(\sum _ r \tfrac{w _ r}{s _ {X}\vert X _ r\vert }\sum _ {x\in X _ r}h^{(T)}(x)\bigr). This class includes CWN/CIN, CIN++ and CCIN-style layers with mean aggregation. We assume only that (A1) the input encoder is bounded and Λ0\Lambda _ 0-Lipschitz with respect to the ground metric d0d _ 0 on initial attributes (e.g. an embedding table for atom types, or an MLP on bounded features), and (A2) the update, message and readout maps are Lipschitz, with constants LϕL _ \phi, (La∘,La)(L^\circ _ a, L _ a) and LoutL _ {out}. Then for all complexes X,YX,Y,

∥F(X)−F(Y)∥≤LoutΛT∗DCCWL(T)(X,Y)≤LoutΛT∗DCCWL(X,Y),\Vert F( X)-F(Y)\Vert \le L _ {out} \Lambda^\ast _ T D^{(T)} _ {CCWL}( X,Y) \le L _ {out} \Lambda^\ast _ T D _ {CCWL}(X, Y),

where ΛT∗=max⁡{ΛT, 8B/(αidTM)}\Lambda^\ast _ T=\max\lbrace \Lambda _ T,\ 8B/(\alpha _ {id}^T M)\rbrace, where Λt+1=Lϕmax⁡aℓa(t)/αa\Lambda _ {t+1}=L _ \phi\max _ a \ell _ a(t)/\alpha _ a with ℓid(t)=(1+∑a≠idLa∘)Λt\ell _ {id}(t)=(1+\sum _ {a\neq id}L^\circ _ a)\Lambda _ t and ℓa(t)=max⁡{caLaΛt, Ka/M}\ell _ a(t)=\max\lbrace c _ aL _ a\Lambda _ t,\ K _ a/M\rbrace. Here αa\alpha _ a are the channel weights of the distance, MM is the bound of d0d _ 0, BB bounds the cell embeddings, KaK _ a bounds the gap between a message and the fixed vector used for an empty channel, and ca=1c _ a=1 for boundary and coboundary, 22 for the pair-valued adjacency channels. The bound is depth-matched: a TT-layer network is controlled by the depth-TT distance DCCWL(T)D^{(T)} _ {CCWL}, and hence also by the full distance.

Proof sketch. We kindly refer the reviewer to the full proof in App. C.5.1. It follows the strategy of Chen et al. (2023) for MPNNs and proceeds by induction on the layers. Mean aggregation is an integral of the message function against the distribution of the neighbors' representations. Via the channel decomposition dt+1=αiddt+∑aαaWad _ {t+1}=\alpha _ {id}d _ t+\sum _ a\alpha _ aW _ a (Prop. C.1), each message gap is therefore bounded by the corresponding Wasserstein term of the distance, and the rank-weighted readout passes the cell-level bound to complexes.

Empirical verification (App. C.5.2). We implemented networks of exactly this form and compared their output differences with DCCWL(T)D^{(T)} _ {CCWL} on all pairs of MUTAG and COX2. 1) On every pair with DCCWL(T)=0D^{(T)} _ {CCWL}=0, the outputs agree to double-precision rounding (largest difference 1.9×10−161.9\times10^{-16}; Table 4). 2) On all other pairs the ratio ∥F(X)−F(Y)∥/DCCWL(T)\Vert F( X)-F( Y)\Vert /D^{(T)} _ {CCWL} is finite and of order one (Figure 5). 3) The distance also tracks the output differences: the Spearman correlation between ∥F(X)−F(Y)∥\Vert F( X)-F(Y)\Vert and DCCWL(T)D^{(T)} _ {CCWL} rises with depth from 0.62 to 0.85 on MUTAG and from 0.48 to 0.64 on COX2, with a 95% interval of at most ±0.018\pm0.018 across initializations (Figure 6).

On the title. With Theorem C.9, "measuring expressivity" has two precise meanings in the paper. Qualitatively, DCCWLD _ {CCWL} vanishes exactly on the pairs that no CCWL-bounded TNN can separate (Prop. 3.3, Cor. 3.4). Quantitatively, its depth-TT value bounds how far apart any TT-layer TNN of the class can place two complexes (Theorem C.9). We have also added evidence that this geometry is useful to trained TNNs. Combining a trained backbone with nearest neighbors correction under DCCWLD _ {CCWL} at inference improves accuracy in 31 of 36 low-label configurations across three backbones and six datasets (+1.52+1.52 points on average, with p<10−4p \lt 10^{-4}; App. B.3).

Comments on the paper

1 comment
AuthorsOpenReview ↗

General responses

We thank the reviewers for their careful reading and constructive comments. These comments have substantially strengthened our work. We have uploaded a revision. Below we summarize the changes and common concerns shared by several reviewers. (Individual responses give the details.)

Summary of the revision

  • App. C.5: Lipschitz theorem for TNNs (new). Theorem C.9 states that any TT-layer message-passing TNN over the four CCWL channels and a rank-weighted mean readout. For such networks, ∥F(X)−F(Y)∥≤LoutΛT∗ DCCWL(T)(X,Y)\lVert F(\mathcal X)-F(\mathcal Y)\rVert\le L_{\mathrm{out}}\Lambda_T^{\ast}\ D_{\mathrm{CCWL}}^{(T)}(\mathcal X,\mathcal Y), with an explicit constant built from the layers' Lipschitz constants and the channel weights. The proof is by induction on the layers, following Chen et al. (2023) for MPNNs. App. C.5.2 verifies the bound on all pairs of MUTAG and COX2.
  • App. C.6: CCWL and 1-WL on the incidence graph (new). Corollary C.14 shows that, in the limit, the following coincide: CCWL equivalence, 1-WL equivalence on the rank-colored incidence graph, fractional isomorphism (Tinhofer's theorem), DCCWL=0D_{\mathrm{CCWL}}=0 and DCo-OTcvx=0D_{\mathrm{Co\text{-}OT}}^{\mathrm{cvx}}=0. At depth tt, 1-WL on the incidence graph needs up to 2t2t rounds, and the factor two is attained. App. C.6.1 quantifies this depth gap on four benchmarks.
  • App. B.3: DCCWLD_{\mathrm{CCWL}} at inference in the low-label regime (new). A trained backbone (CCIN, CWN or CIN++) is combined with a nearest-neighbor vote correction under DCCWLD_{\mathrm{CCWL}}.
  • App. E: complexity and wall-clock analysis (new). It gives exact operation counts for DCCWLD_{\mathrm{CCWL}}, convex Co-OT and unrelaxed Co-OT, and timings against the number of cells, the depth and the number of ranks.

Common concerns

1. What do the values of the distance say about TNNs? Raised in different forms by several reviewers. Theorem C.9 answers this. A small DCCWL(T)D_{\mathrm{CCWL}}^{(T)} verifies that no TT-layer TNN of the class, with given Lipschitz constants, can map two complexes far apart. Conversely, two complexes that such a network separates by a margin ε\varepsilon are at distance at least ε/(LoutΛT∗)\varepsilon/(L_{\mathrm{out}}\Lambda_T^{\ast}). The bound is depth-matched, i.e. a TT-layer network is controlled by the depth-TT distance. Empirically, outputs agree to rounding error (≤1.9×10−16\le1.9\times10^{-16}) on the zero set, the finite ratio of output difference to distance, and the rank correlation between the two increases with depth. Following reviewer 5xzs's follow-up, the theorem now states explicitly the rank separation that its proof uses. The ground metric of Remark C.8 and the implemented metric of our experiments both satisfy it.

3. Computational cost. We are upfront that neither distance is efficient in its current implementation. DCCWLD_{\mathrm{CCWL}} to depth TT solves exactly 4NMT4NMT small transport problems. Its time is quadratic in the number of cells and linear in depth. Convex Co-OT is one linear program. The gain from convexity is exactness, i.e. an exact global optimum with the right zero set, instead of speed. More efficient approximations are left to future work.

4. Choice of weights and ground metric. All experiments use uniform channel weights αa=1/5\alpha_a=1/5, rank weights wr=1w_r=1. The zero set, and every distinguishability result, hold for every choice. Theorem C.9 may gives a natural choice: ww should match the network's readout weights, and α\alpha should follow the network's sensitivity to each channel. In a sensitivity study on all 13,499 MUTAG pairs, every change of α\alpha or ww keeps a rank correlation of at least 0.98 with the default and moves 1-NN accuracy by at most 0.5 points.

5. Empirical usefulness. 1-NN accuracy depends on how the labels align with the structural differences a distance emphasizes. This alignment varies across datasets, which explains why DCCWLD_{\mathrm{CCWL}} leads on MUTAG and PROTEINS but not much so on NCI1 and NCI109. To test the geometry where it can matter for TNNs, App. B.3 adds DCCWLD_{\mathrm{CCWL}} at inference to trained backbones. With 25% or 10% of the labels, accuracy improves statistically significantly. This includes every low-label configuration on NCI1 and NCI109.

We sincerely hope these additions address the reviewers' concerns and would be glad to clarify anything further.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.