On topological descriptors for graph products

AI summary

Overview

Research area: Topological deep learning / graph representation learning — specifically topological descriptors (persistent homology and Euler characteristic) applied to graph products.

Technical level: Advanced. The paper assumes familiarity with persistent homology, filtrations, simplicial complexes, graph products, and the Weisfeiler–Leman expressivity literature.

Scope: The paper characterizes the expressive power of Euler characteristic diagrams versus persistent homology diagrams on graphs and their (box) products, and provides efficient algorithms for computing persistence diagrams of product filtrations.

What This Paper Is About

Graph neural networks based on message passing cannot compute basic structural properties such as cycles or connected components, so researchers augment them with topological descriptors like persistent homology (PH) and the Euler characteristic (EC). This paper asks what happens to these descriptors when graphs are combined via the box (Cartesian) product: whether the product exposes structure that the individual components do not, and how cheaply the resulting diagrams can be computed. The authors aim to build a "calculus" for topological descriptors under graph products as a step toward principled design of richer filtration functions.

Key Contributions

1. Complete combinatorial characterization of EC expressivity. The authors prove that EC diagrams of two graphs agree for every choice of coloring functions if and only if the two graphs have the same number of vertices of each color and the same number of edges between each pair of colors (Theorem 2). A matching characterization is given for the weaker variant they call max EC (Theorem 1), and the equivalence extends to colored simplicial complexes (Theorem 3).

2. A separation between PH and EC under graph products. PH of a (virtual) graph product contains strictly more information than PH of the individual components (Proposition 4, Corollary 1), whereas EC of the product adds no expressivity beyond EC of the components (Proposition 5).

3. Characterization of product filtrations. The product of vertex filtrations on the components is equivalent to a single vertex coloring on the product assigning each vertex the maximum of the two component values (Proposition 6); the product of edge filtrations is equivalent to a specific edge coloring on the product (Proposition 7).

4. Algorithms for computing PH diagrams of product filtrations. Efficient procedures are given for 0-dimensional persistence pairs under vertex product filtrations (Theorem 4) and edge product filtrations (Theorem 5), plus a general procedure for 1-dimensional persistence pairs of any product filtration (Proposition 8).

Main Findings

• Max EC costs less but sees the same. The max EC diagram, which restricts EC to max-induced edge filtrations, has exactly the same expressive power as the full EC diagram, and is described as even more cost-effective (Theorem 1).

• Max PH matches vertex death times and cycle birth times. For the max filtration, the vertex death times as a multiset of PH(G,f)^E and PH(G,f)^V are the same, and the cycle birth times are also the same (Proposition 1).

• EC diagrams reduce to counting combinatorics. Two graphs share the same EC diagram for all colorings precisely when they have equal counts of vertices per color and equal counts of edges between each ordered pair of colors (Theorem 2), valid for both EC and max EC.

• The equivalence generalizes beyond graphs. There is a natural extension of EC and max EC to colored simplicial complexes under which they retain identical expressive power for color-based filtrations (Theorem 3).

• Products help PH but not EC. There exist graphs G and H that vertex-level and edge-level PH cannot distinguish, yet edge-level PH on G□G and H□H can distinguish them (Proposition 4); the explicit example in Figure 1 involves a non-trivial cycle created by edges between vertices of color (blue, blue) and (red, blue) in one product and no cycles in the other. By contrast, if EC cannot differentiate G and H (with equal vertex counts), the EC diagrams of G□G, G□H, and H□H are all identical (Proposition 5).

• Adjoining a virtual node guarantees strictly more information. For graphs G_+ and H_+ obtained by adding a disjoint basepoint colored "virtual" and born at time −∞, the PH of G_+□G_+, G_+□H_+, and H_+□H_+ contains strictly more information than the PH of G and H (Corollary 1). The EC of virtual graph products still adds no information.

• Product filtrations have clean algebraic forms. The product of injective vertex color functions f_G and f_H equals the vertex coloring F((g,h)) = max(f_G(c(g)), f_H(c(h))) (Proposition 6); the product of edge color functions assigns edges within a fiber the corresponding component's edge value (Proposition 7).

• Runtime improvements over the naive approach. For vertex product filtrations, the 0-dimensional PH diagram is computed in O(n_G n_H + m_G log m_G + m_H log m_H + n_G + n_H) assuming constant coloring-set size (Theorem 4), compared to the naive O(n_G n_H + (n_G m_H + n_H m_G) log(n_G m_H + n_H m_G)). For edge product filtrations (Theorem 5), the runtime is O(max(n_G log n_G + n_H log n_H, m_G log m_G + n_G, m_H log m_H + n_H)), again better than the same naive bound.

• One-dimensional features have a closed form. The 1-dimensional PH of the product filtration G_t□H_t consists of β₁(G_{a₁}□H_{a₁}) copies of (a₁, ∞) and β₁(G_{a_i}□H_{a_i}) − β₁(G_{a_{i−1}}□H_{a_{i−1}}) copies of (a_i, ∞) for i > 1, with runtime O(m_G log m_G + n_G + m_H log m_H + n_H), using β₁(A□B) = #E(A)#E(B) + β₀(A)β₀(B) − χ(A)χ(B) (Proposition 8).

• Empirical study is described but numeric results are not in the provided content. The paper reports three experiment sets: (1) expressivity on BREC datasets and minimal Cayley graphs with varying numbers of nodes, (2) runtime performance of the algorithms from Theorems 4 and 5 using BREC datasets, and (3) integration of the descriptors with GNNs for graph classification. The provided text is truncated before the results of these experiments, so specific datasets sizes, accuracy figures, and timings are not reported here.

Methodology in Plain English

The authors work with graphs carrying vertex colors, and two families of filtration: vertex-level filtrations (where an edge takes the higher value of its two endpoints) and edge-level filtrations (where an edge takes a value determined by its endpoint colors). They define an isomorphism-invariant "diagram" for both PH and EC, then ask when two graphs produce the same diagram for every possible choice of coloring function. By translating the diagrams into combinatorial counts — how many vertices carry each color, how many edges connect each pair of colors, and the Euler characteristic of the subgraph induced by each color class — they obtain exact conditions for when the descriptors can and cannot tell graphs apart. They then transfer this analysis to the box product of graphs, where vertices are pairs (g, h) and the natural product coloring is the pair of component colors. To force the product to carry strictly more information than its factors, they adjoin a "virtual" basepoint born at time −∞. For the algorithmic side, they exploit the structure of product filtrations to decompose the persistence computation into changes in the two component graphs, giving dynamic programs that track births, deaths, and Betti numbers rather than running PH on the full product.

Why This Matters

The work gives a precise, provable picture of when combining graphs via a product enriches a topological descriptor and when it does not. That matters because practitioners often assume richer input structures automatically yield richer invariants; here, EC provably does not benefit from the product while PH does. It also lowers the cost of PH-based features by replacing a computation on the whole product graph with one that scales with the components.

Real-world applications named in the paper:

• Relational databases: comparing tables of records (the paper's Motivation 1 uses wage-income tables for New York and London residents) by modeling each table as a graph and taking the Cartesian product to analyze cross-table relationships.
• Hamming graphs: explicitly named as graph data with natural product structure.
• Subgraph GNNs: graph products arise naturally in the context of subgraph-based graph neural networks.
• Multi-way data and relational modeling: graph products are described as a natural tool for modeling and analyzing multi-way data, and have been incorporated into various GNN architectures.

Industry relevance: The main practical lever is cost. The paper positions max EC as an economical substitute for PH-based descriptors (explicitly noting that this opens avenues for integrating max EC into Topological Neural Networks), while reserving product-based PH for cases where additional discriminative power is genuinely needed. The released code (https://github.com/Aalto-QuML/tda_graph_product) supports reproducibility for teams wanting to add these descriptors to existing pipelines.

Future Directions

• Handling filtrations outside product filtrations. The paper states as an explicit limitation that its algorithms cover only a subcollection of possible color-based filtrations on G□H; for general filtrations the PH may not decompose neatly and may be more computationally expensive. Extending the decomposition is an open problem.

• Integrating max EC into Topological Neural Networks. The authors flag this as an immediate avenue, since max EC retains EC's expressivity at lower cost and higher-order message-passing models have recently been shown to benefit from topological descriptors.

• Principled design of filtration functions. The paper argues that filtration functions are almost invariably fixed a priori or learned without structural considerations such as symmetries, and positions its graph-product analysis as a rigorous starting point for designing richer, structure-aware filtrations.

• Scope of the 1-dimensional algorithm and higher dimensions. The 1-dimensional algorithm in Proposition 8 works for any product filtration, while the 0-dimensional algorithms cover only vertex and edge product filtrations; generalizing the 0-dimensional decomposition and pushing beyond dimension 1 remain natural next steps.

Target Audience

Researchers and graduate students in topological data analysis, geometric deep learning, and graph representation learning who want provable statements about the expressive power of topological descriptors. It is also relevant to practitioners building GNN augmentation pipelines who need to know when the extra cost of PH is justified — and who may prefer max EC as a cheaper alternative — and to theorists working on expressivity hierarchies for graph learning models.

Authors’ abstract

Topological descriptors have been increasingly utilized for capturing multiscale structural information in relational data. In this work, we consider various filtrations on the (box) product of graphs and the effect on their outputs on the topological descriptors - the Euler characteristic (EC) and persistent homology (PH). In particular, we establish a complete characterization of the expressive power of EC on general color-based filtrations. We also show that the PH descriptors of (virtual) graph products contain strictly more information than the computation on individual graphs, whereas EC does not. Additionally, we provide algorithms to compute the PH diagrams of the product of vertex- and edge-level filtrations on the graph product. We also substantiate our theoretical analysis with empirical investigations on runtime analysis, expressivity, and graph classification performance. Overall, this work paves way for powerful graph persistent descriptors via product filtrations. Code is available at https://github.com/Aalto-QuML/tda_graph_product.