- 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 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 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 . 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 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?
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 α and uniform w 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 w should equal the readout weights of the architecture whose outputs the distance is meant to control.
To quantify the sensitivity, we recomputed DCCWL on MUTAG, changing one parameter at a time from the default: αid∈{0.1,0.4}; boundary/coboundary-heavy α=(0.2,0.3,0.3,0.1,0.1) and adjacency-heavy α=(0.2,0.1,0.1,0.3,0.3) over (id,B,C,↓,↑); rank weights w=(2,1,1) and (1,1,2).
In every setting the zero set is exactly the same pairs, as the theory predicts. The weights matter very little: under every change of α and w 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 T-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),
where Λ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 ε must be at distance at least ε/(LoutΛT∗). The bound is depth-matched, so DCCWL(T) describes what a network of depth T can do. The bounds can be computed explicitly.