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

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.