Representing Edge Flows on Graphs via Sparse Cell Complexes
This work addresses the need for interpretable flow representations in machine learning and signal processing, offering a novel algorithmic approach with practical improvements.
The paper tackles the problem of obtaining sparse, interpretable representations of edge flows on graphs by generalizing the Hodge decomposition to cellular complexes and introducing the flow representation learning problem, which is shown to be NP-hard; it proposes an efficient approximation algorithm that outperforms state-of-the-art methods in approximation error on real-world and synthetic data.
Obtaining sparse, interpretable representations of observable data is crucial in many machine learning and signal processing tasks. For data representing flows along the edges of a graph, an intuitively interpretable way to obtain such representations is to lift the graph structure to a simplicial complex: The eigenvectors of the associated Hodge-Laplacian, respectively the incidence matrices of the corresponding simplicial complex then induce a Hodge decomposition, which can be used to represent the observed data in terms of gradient, curl, and harmonic flows. In this paper, we generalize this approach to cellular complexes and introduce the flow representation learning problem, i.e., the problem of augmenting the observed graph by a set of cells, such that the eigenvectors of the associated Hodge Laplacian provide a sparse, interpretable representation of the observed edge flows on the graph. We show that this problem is NP-hard and introduce an efficient approximation algorithm for its solution. Experiments on real-world and synthetic data demonstrate that our algorithm outperforms state-of-the-art methods with respect to approximation error, while being computationally efficient.