Online Time-Varying Topology Identification via Prediction-Correction Algorithms

• URL: http://arxiv.org/abs/2010.11634v2
• Date: Wed, 10 Feb 2021 15:45:53 GMT
• Title: Online Time-Varying Topology Identification via Prediction-Correction Algorithms
• Authors: Alberto Natali, Mario Coutino, Elvin Isufi and Geert Leus
• Abstract summary: We propose a general-purpose online algorithm operating in non-stationary environments. Because of its iteration-constrained nature, the proposed approach exhibits an intrinsic temporal-regularization of the graph topology without explicitly enforcing it.
• Score: 36.620113114806294
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Signal processing and machine learning algorithms for data supported over graphs, require the knowledge of the graph topology. Unless this information is given by the physics of the problem (e.g., water supply networks, power grids), the topology has to be learned from data. Topology identification is a challenging task, as the problem is often ill-posed, and becomes even harder when the graph structure is time-varying. In this paper, we address the problem of dynamic topology identification by building on recent results from time-varying optimization, devising a general-purpose online algorithm operating in non-stationary environments. Because of its iteration-constrained nature, the proposed approach exhibits an intrinsic temporal-regularization of the graph topology without explicitly enforcing it. As a case-study, we specialize our method to the Gaussian graphical model (GGM) problem and corroborate its performance.

Related papers

• Online Proximal ADMM for Graph Learning from Streaming Smooth Signals [9.34612743192798]
  We develop a novel algorithm for online graph learning using observation streams, assumed to be smooth on the latent graph. Our modus operandi is to process graph signals sequentially and thus keep memory and computational costs in check. The proposed approach also exhibits better tracking performance (in terms of suboptimality) when compared to state-of-the-art online graph learning baselines.
  arXiv  Detail & Related papers  (2024-09-19T17:12:03Z)
• Online Learning Of Expanding Graphs [14.952056744888916]
  This paper addresses the problem of online network inference for expanding graphs from a stream of signals. We introduce a strategy that enables different types of updates for nodes that just joined the network and for previously existing nodes.
  arXiv  Detail & Related papers  (2024-09-13T09:20:42Z)
• Online Graph Filtering Over Expanding Graphs [14.594691605523005]
  We propose an online graph filtering framework by relying on online learning principles. We design filters for scenarios where the topology is both known and unknown, including a learner adaptive to such evolution. We conduct a regret analysis to highlight the role played by the different components such as the online algorithm, the filter order, and the growing graph model.
  arXiv  Detail & Related papers  (2024-09-11T11:50:16Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Online Graph Learning under Smoothness Priors [8.826181951806928]
  We develop novel algorithms for online network topology inference given streaming observations assumed to be smooth on the sought graph. Our goal is to track the (possibly) time-varying network topology while maintaining the memory and computational costs in check by processing graph signals sequentially-in-time. Computer simulations using both synthetic and real financial market data illustrate the effectiveness of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-03-05T15:42:53Z)
• Efficient Variational Bayesian Structure Learning of Dynamic Graphical Models [19.591265962713837]
  Estimating time-varying graphical models is of paramount importance in various social, financial, biological, and engineering systems. Existing methods require extensive tuning of parameters that control the graph sparsity and temporal smoothness. We propose a low-complexity tuning-free Bayesian approach, named BADGE.
  arXiv  Detail & Related papers  (2020-09-16T14:19:23Z)

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.