Online Graph Filtering Over Expanding Graphs

• URL: http://arxiv.org/abs/2409.07204v1
• Date: Wed, 11 Sep 2024 11:50:16 GMT
• Title: Online Graph Filtering Over Expanding Graphs
• Authors: Bishwadeep Das, Elvin Isufi,
• Abstract summary: 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.
• Score: 14.594691605523005
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Graph filters are a staple tool for processing signals over graphs in a multitude of downstream tasks. However, they are commonly designed for graphs with a fixed number of nodes, despite real-world networks typically grow over time. This topological evolution is often known up to a stochastic model, thus, making conventional graph filters ill-equipped to withstand such topological changes, their uncertainty, as well as the dynamic nature of the incoming data. To tackle these issues, 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. Numerical experiments with synthetic and real data corroborate the proposed approach for graph signal inference tasks and show a competitive performance w.r.t. baselines and state-of-the-art alternatives.

Related papers

• Fairness-aware Optimal Graph Filter Design [25.145533328758614]
  Graphs are mathematical tools that can be used to represent complex real-world interconnected systems. Machine learning (ML) over graphs has attracted significant attention recently. We take a fresh look at the problem of bias mitigation in graph-based learning by borrowing insights from graph signal processing.
  arXiv  Detail & Related papers  (2023-10-22T22:40:40Z)
• Fairness-Aware Graph Filter Design [19.886840347109285]
  Graphs are mathematical tools that can be used to represent complex real-world systems. Machine learning (ML) over graphs amplifies the already existing bias towards certain under-represented groups. We propose a fair graph filter that can be employed in a versatile manner for graph-based learning tasks.
  arXiv  Detail & Related papers  (2023-03-20T21:31:51Z)
• Online Filtering over Expanding Graphs [14.84852576248587]
  We propose an online update of the filter, based on the principles of online machine learning. We show the performance of our method for signal at the incoming nodes. These findings lay the foundation for efficient filtering over expanding graphs.
  arXiv  Detail & Related papers  (2023-01-17T14:07:52Z)
• State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
  Graph-level learning has been applied to many tasks including comparison, regression, classification, and more. Traditional approaches to learning a set of graphs rely on hand-crafted features, such as substructures. Deep learning has helped graph-level learning adapt to the growing scale of graphs by extracting features automatically and encoding graphs into low-dimensional representations.
  arXiv  Detail & Related papers  (2023-01-14T09:15:49Z)
• Graph Filters for Signal Processing and Machine Learning on Graphs [83.29608206147515]
  We provide a comprehensive overview of graph filters, including the different filtering categories, design strategies for each type, and trade-offs between different types of graph filters. We discuss how to extend graph filters into filter banks and graph neural networks to enhance the representational power. Our aim is that this article provides a unifying framework for both beginner and experienced researchers, as well as a common understanding.
  arXiv  Detail & Related papers  (2022-11-16T11:56:45Z)
• Similarity-aware Positive Instance Sampling for Graph Contrastive Pre-training [82.68805025636165]
  We propose to select positive graph instances directly from existing graphs in the training set. Our selection is based on certain domain-specific pair-wise similarity measurements. Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
  arXiv  Detail & Related papers  (2022-06-23T20:12:51Z)
• 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)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• A User Guide to Low-Pass Graph Signal Processing and its Applications [31.90359683602266]
  We show how to leverage properties of low-pass graph filters to learn the graph topology or identify its community structure. We illustrate how to represent graph data through sampling, recover missing measurements, and de-noise graph data.
  arXiv  Detail & Related papers  (2020-08-04T03:27:17Z)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  We leverage graph signal processing to characterize the representation space of graph neural networks (GNNs) We discuss the role of graph convolutional filters in GNNs and show that any architecture built with such filters has the fundamental properties of permutation equivariance and stability to changes in the topology. We also study the use of GNNs in recommender systems and learning decentralized controllers for robot swarms.
  arXiv  Detail & Related papers  (2020-03-08T13:02:15Z)

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.