Joint Inference of Multiple Graphs from Matrix Polynomials
- URL: http://arxiv.org/abs/2010.08120v1
- Date: Fri, 16 Oct 2020 02:45:15 GMT
- Title: Joint Inference of Multiple Graphs from Matrix Polynomials
- Authors: Madeline Navarro, Yuhao Wang, Antonio G. Marques, Caroline Uhler,
Santiago Segarra
- Abstract summary: 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.
- Score: 34.98220454543502
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inferring graph structure from observations on the nodes is an important and
popular network science task. Departing from the more common inference of a
single graph and motivated by social and biological networks, we study the
problem of jointly inferring multiple graphs from the observation of signals at
their nodes (graph signals), which are assumed to be stationary in the sought
graphs. From a mathematical point of view, graph stationarity implies that the
mapping between the covariance of the signals and the sparse matrix
representing the underlying graph is given by a matrix polynomial. A prominent
example is that of Markov random fields, where the inverse of the covariance
yields the sparse matrix of interest. From a modeling perspective, stationary
graph signals can be used to model linear network processes evolving on a set
of (not necessarily known) networks. Leveraging that matrix polynomials
commute, a convex optimization method along with sufficient conditions that
guarantee the recovery of the true graphs are provided when perfect covariance
information is available. Particularly important from an empirical viewpoint,
we provide high-probability bounds on the recovery error as a function of the
number of signals observed and other key problem parameters. Numerical
experiments using synthetic and real-world data demonstrate the effectiveness
of the proposed method with perfect covariance information as well as its
robustness in the noisy regime.
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) - 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) - Joint graph learning from Gaussian observations in the presence of
hidden nodes [26.133725549667734]
We propose a joint graph learning method that takes into account the presence of hidden (latent) variables.
We exploit the structure resulting from the previous considerations to propose a convex optimization problem.
We compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
arXiv Detail & Related papers (2022-12-04T13:03:41Z) - Joint Network Topology Inference via a Shared Graphon Model [24.077455621015552]
We consider the problem of estimating the topology of multiple networks from nodal observations.
We adopt a graphon as our random graph model, which is a nonparametric model from which graphs of potentially different sizes can be drawn.
arXiv Detail & Related papers (2022-09-17T02:38:58Z) - Joint inference of multiple graphs with hidden variables from stationary
graph signals [19.586429684209843]
We introduce a joint graph topology inference method that models the influence of the hidden variables.
Under the assumptions that the observed signals are stationary on the sought graphs, the joint estimation of multiple networks allows us to exploit such relationships.
arXiv Detail & Related papers (2021-10-05T21:31:36Z) - 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) - 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) - Offline detection of change-points in the mean for stationary graph
signals [55.98760097296213]
We propose an offline method that relies on the concept of graph signal stationarity.
Our detector comes with a proof of a non-asymptotic inequality oracle.
arXiv Detail & Related papers (2020-06-18T15:51:38Z) - 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.