Research map / Graph learning / GNN architectures
On topological descriptors for graph products
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the expressive power of Euler characteristic (EC) diagrams on colored graphs, gives efficient algorithms for persistent homology (PH) under product filtrations on box products of graphs, and shows PH of (virtual) graph products is strictly more expressive than PH of components while EC is not.
Problem
Topological descriptors (persistent homology and Euler characteristic) on graphs are expensive to compute and filtrations are usually fixed or learned without structural considerations; it is unclear what information EC and PH capture, especially on box products of graphs.
Approach
Gives a combinatorial characterization of EC diagram expressivity on colored graphs, shows max EC (edge filtrations induced by vertex colors) matches EC in expressivity, and analyzes PH/EC on box products with product filtrations, yielding efficient product-filtration PH algorithms.
Key results
- On BREC Basic, GProd with closeness filtration reaches 100.0% vs 93.33% for standard PH edge-level.
- GIN + GProd improves DHFR accuracy from 80.53 to 82.89 and ZINC MAE from 0.57 to 0.54.
- Proposed product-filtration algorithms run faster than naive union-find and gudhi PH on the full graph product as graph size grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use graph-product edge-level PH instead of standard edge-level PH | BREC Basic (60), Closeness · BREC Basic (60) | accuracy: 93.33 -> 100.0 | Helped |
| Use graph-product edge-level PH instead of standard edge-level PH | BREC Reg. (50), Closeness · BREC Reg. (50) | accuracy: 86.00 -> 100.0 | Helped |
| Use graph-product edge-level PH instead of standard edge-level PH | BREC Ext. (100), Closeness · BREC Ext. (100) | accuracy: 71.00 -> 94.00 | Helped |
| Use graph-product edge-level PH instead of standard edge-level PH | BREC Basic (60), Jaccard Index · BREC Basic (60) | accuracy: 98.33 -> 98.33 | No clear effect |
| Use graph-product edge-level PH instead of standard edge-level PH | BREC Reg. (50), Jaccard Index · BREC Reg. (50) | accuracy: 94.00 -> 94.00 | No clear effect |
| Use graph-product edge-level PH instead of standard edge-level PH | BREC Ext. (100), Jaccard Index · BREC Ext. (100) | accuracy: 56.00 -> 61.00 | Helped |
| Use graph-product vertex-level PH instead of standard vertex-level PH | BREC Basic (60), Clustering · BREC Basic (60) | accuracy: 100.0 -> 100.0 | No clear effect |
| Use graph-product vertex-level PH instead of standard vertex-level PH | BREC Reg. (50), Clustering · BREC Reg. (50) | accuracy: 98.00 -> 98.00 | No clear effect |
| Use graph-product vertex-level PH instead of standard vertex-level PH | BREC Ext. (100), Clustering · BREC Ext. (100) | accuracy: 84.00 -> 84.00 | No clear effect |
| Add graph-product PH descriptors | GIN · DHFR | accuracy: 80.53 ± 4.10 -> 82.89 ± 4.16 | Helped |
| Add graph-product PH descriptors | GIN · COX2 | accuracy: 76.60 ± 2.61 -> 78.30 ± 5.90 | Helped |
| Add graph-product PH descriptors | GIN · ZINC (12K) | MAE: 0.57 ± 0.02 -> 0.54 ± 0.02 | Helped |
Surprising findings
- EC of box products adds no expressivity beyond EC of individual components, unlike PH.
- Max EC has the same expressive power as full EC on colored graphs.
Limitations
- Algorithms cover only a subcollection of color-based filtrations (product filtrations); general filtrations on the product may be costlier.
- Expressivity gains reported for PH on products rely on a technical virtual-node modification.
- Graph classification gains are modest and often within standard deviations.
Experimental setup
Datasets: BREC minimal Cayley graphs COX2 DHFR NCI1 NCI109 ZINC PROTEINS
Benchmarks: BREC minimal Cayley graphs COX2 DHFR NCI1 NCI109 ZINC PROTEINS
Metrics: accuracy MAE runtime (seconds)
Baselines: standard PH GIN GCN GraphSAGE ProdFilt
Builds on: persistent homology BREC benchmark GIN GCN GraphSAGE
Closest papers by meaning
- Graph Persistence goes Spectral (NeurIPS 2025 · similarity 0.90)
- Graphcode: Learning from multiparameter persistent homology using graph neural networks (NeurIPS 2024 · similarity 0.87)
- Differentiability and Optimization of Multiparameter Persistent Homology (ICML 2024 · similarity 0.87)
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.86)
- TopER: Topological Embeddings in Graph Representation Learning (NeurIPS 2025 · similarity 0.85)
- Diss-l-ECT: Dissecting Graph Data with Local Euler Characteristic Transforms (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.