Representing Edge Flows on Graphs via Sparse Cell Complexes
- URL: http://arxiv.org/abs/2309.01632v3
- Date: Thu, 2 Nov 2023 08:26:48 GMT
- Title: Representing Edge Flows on Graphs via Sparse Cell Complexes
- Authors: Josef Hoppe and Michael T. Schaub
- Abstract summary: We introduce the flow representation learning problem, i.e., the problem of augmenting the observed graph by a set of cells.
We show that this problem is NP-hard and introduce an efficient approximation algorithm for its solution.
- Score: 6.74438532801556
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals [18.45931641798935]
This paper introduces Polynomial Graphical Lasso (PGL), a new approach to learning graph structures from nodal signals.
Our key contribution lies in the signals as Gaussian and stationary on the graph, enabling the development of a graph-learning lasso.
arXiv Detail & Related papers (2024-04-03T10:19:53Z) - Learning graphs and simplicial complexes from data [26.926502862698168]
We present a novel method to infer the underlying graph topology from available data.
We also identify three-node interactions, referred to in the literature as second-order simplicial complexes (SCs)
Experimental results on synthetic and real-world data showcase a superior performance for our approach compared to existing methods.
arXiv Detail & Related papers (2023-12-16T22:02:20Z) - Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure.
We introduce a new class of manifold, named soft manifold, that can solve this situation.
Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
arXiv Detail & Related papers (2023-11-29T12:48:33Z) - Pure Spectral Graph Embeddings: Reinterpreting Graph Convolution for
Top-N Recommendation [1.8047694351309205]
We investigate the effect of using graph convolution throughout the user and item representation learning processes.
We present an approach that directly leverages the eigenvectors to emulate the solution obtained through graph convolution.
arXiv Detail & Related papers (2023-05-28T05:34:50Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals.
We propose a general graph estimator based on a novel structured fusion regularization.
We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
arXiv Detail & Related papers (2021-03-05T04:42:32Z) - Multilayer Clustered Graph Learning [66.94201299553336]
We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph.
Experiments show that our method leads to a clustered clusters w.r.t.
We learn a clustering algorithm for solving clustering problems.
arXiv Detail & Related papers (2020-10-29T09:58:02Z) - Joint Inference of Multiple Graphs from Matrix Polynomials [34.98220454543502]
Inferring graph structure from observations on the nodes is an important and popular network science task.
We study the problem of jointly inferring multiple graphs from the observation of signals at their nodes.
We propose a convex optimization method along with sufficient conditions that guarantee the recovery of the true graphs.
arXiv Detail & Related papers (2020-10-16T02:45:15Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology.
Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
arXiv Detail & Related papers (2020-06-19T13:09:44Z) - Semiparametric Nonlinear Bipartite Graph Representation Learning with
Provable Guarantees [106.91654068632882]
We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution.
We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate.
Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
arXiv Detail & Related papers (2020-03-02T16:40:36Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs.
We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions.
Our methods are scalable to sparse graphs consisting of millions of nodes.
arXiv Detail & Related papers (2020-02-14T11:42:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.