Online Proximal ADMM for Graph Learning from Streaming Smooth Signals

• URL: http://arxiv.org/abs/2409.12916v1
• Date: Thu, 19 Sep 2024 17:12:03 GMT
• Title: Online Proximal ADMM for Graph Learning from Streaming Smooth Signals
• Authors: Hector Chahuara, Gonzalo Mateos,
• Abstract summary: 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.
• Score: 9.34612743192798
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph signal processing deals with algorithms and signal representations that leverage graph structures for multivariate data analysis. Often said graph topology is not readily available and may be time-varying, hence (dynamic) graph structure learning from nodal (e.g., sensor) observations becomes a critical first step. In this paper, we develop a novel algorithm for online graph learning using observation streams, assumed to be smooth on the latent graph. Unlike batch algorithms for topology identification from smooth signals, our modus operandi is to process graph signals sequentially and thus keep memory and computational costs in check. To solve the resulting smoothness-regularized, time-varying inverse problem, we develop online and lightweight iterations built upon the proximal variant of the alternating direction method of multipliers (ADMM), well known for its fast convergence in batch settings. The proximal term in the topology updates seamlessly implements a temporal-variation regularization, and we argue the online procedure exhibits sublinear static regret under some simplifying assumptions. Reproducible experiments with synthetic and real graphs demonstrate the effectiveness of our method in adapting to streaming signals and tracking slowly-varying network connectivity. The proposed approach also exhibits better tracking performance (in terms of suboptimality), when compared to state-of-the-art online graph learning baselines.

Related papers

• Online Graph Learning via Time-Vertex Adaptive Filters: From Theory to Cardiac Fibrillation [37.69303106863453]
  We introduce AdaCGP, an online algorithm for adaptive estimation of the Graph Shift Operator (GSO) Through simulations, we show that AdaCGP performs consistently well across various graph topologies, and achieves improvements in excess of 82% for GSO estimation. AdaCGP's ability to track changes in graph structure is demonstrated on recordings of ventricular fibrillation dynamics in response to an anti-arrhythmic drug.
  arXiv  Detail & Related papers  (2024-11-03T13:43:51Z)
• 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 Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• 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)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  Spectral graph convolutional networks (SGCNs) have been attracting increasing attention in graph representation learning. We propose a novel class of spectral graph convolutional networks that implement graph convolutions with adaptive graph wavelets.
  arXiv  Detail & Related papers  (2021-08-03T17:57:53Z)
• Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
  Graph signal processing is a ubiquitous task in many applications such as sensor, social transportation brain networks, point cloud processing, and graph networks. We propose two restoration methods based on convexindependent deep ADMM (ADMM) parameters in the proposed restoration methods are trainable in an end-to-end manner.
  arXiv  Detail & Related papers  (2021-06-30T08:57:01Z)
• 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)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design. We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
  arXiv  Detail & Related papers  (2020-10-21T20:04:22Z)
• Active Learning on Attributed Graphs via Graph Cognizant Logistic Regression and Preemptive Query Generation [37.742218733235084]
  We propose a novel graph-based active learning algorithm for the task of node classification in attributed graphs. Our algorithm uses graph cognizant logistic regression, equivalent to a linearized graph convolutional neural network (GCN) for the prediction phase and maximizes the expected error reduction in the query phase. We conduct experiments on five public benchmark datasets, demonstrating a significant improvement over state-of-the-art approaches.
  arXiv  Detail & Related papers  (2020-07-09T18:00:53Z)
• Time-varying Graph Representation Learning via Higher-Order Skip-Gram with Negative Sampling [0.456877715768796]
  We build upon the fact that the skip-gram embedding approach implicitly performs a matrix factorization. We show that higher-order skip-gram with negative sampling is able to disentangle the role of nodes and time. We empirically evaluate our approach using time-resolved face-to-face proximity data, showing that the learned time-varying graph representations outperform state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-06-25T12:04:48Z)

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.