Faster Inference of Cell Complexes from Flows via Matrix Factorization
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Families of Optimal Transport Kernels for Cell Complexes
Recent advances have discussed cell complexes as ideal learning representations. However, there is a lack of available machine learning methods suitable for learning on CW complexes. In this paper, we derive an explicit …
Topological Signal Processing over Generalized Cell Complexes
Topological Signal Processing (TSP) over simplicial complexes is a framework that has been recently proposed, as a generalization of graph signal processing (GSP), to extend GSP to analyzing signals defined over sets of …
Image SegmentationSemantic SegmentationRepresenting Edge Flows on Graphs via Sparse Cell Complexes
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…
Inference OptimizationRepresentation LearningCell Complex Neural Networks
Cell complexes are topological spaces constructed from simple blocks called cells. They generalize graphs, simplicial complexes, and polyhedral complexes that form important domains for practical applications. They also …
DecoderSignal Processing on Cell Complexes
The processing of signals supported on non-Euclidean domains has attracted large interest recently. Thus far, such non-Euclidean domains have been abstracted primarily as graphs with signals supported on the nodes, thoug…