Faster Inference of Cell Complexes from Flows via Matrix Factorization

Abstract

We consider the following inference problem: Given a set of edge-flow signals observed on a graph, lift the graph to a cell complex, such that the observed edge-flow signals can be represented as a sparse combination of gradient and curl flows on the cell complex. Specifically, we aim to augment the observed graph by a set of 2-cells (polygons encircled by closed, non-intersecting paths), such that the eigenvectors of the Hodge Laplacian of the associated cell complex provide a sparse, interpretable representation of the observed edge flows on the graph. As it has been shown that the general problem is NP-hard in prior work, we here develop a novel matrix-factorization-based heuristic to solve the problem. Using computational experiments, we demonstrate that our new approach is significantly less computationally expensive than prior heuristics, while achieving only marginally worse performance in most settings. In fact, we find that for specifically noisy settings, our new approach outperforms the previous state of the art in both solution quality and computational speed.

arXiv comment5 pages, 5 figures, accepted at EUSIPCO 2025 in Palermo, evaluation code available at https://github.com/til-spreuer/mfci-workflow

References in corpus (8)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Topological Signal Processing over Simplicial Complexes
• Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• The Spacey Random Walk: a Stochastic Process for Higher-order Data
• Flow Smoothing and Denoising: Graph Signal Processing in the Edge-Space
• Network Geometry and Complexity
• Signal Processing on Cell Complexes