Online Filtering over Expanding Graphs
- URL: http://arxiv.org/abs/2301.06898v1
- Date: Tue, 17 Jan 2023 14:07:52 GMT
- Title: Online Filtering over Expanding Graphs
- Authors: Bishwadeep Das and Elvin Isufi
- Abstract summary: 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.
- Score: 14.84852576248587
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Data processing tasks over graphs couple the data residing over the nodes
with the topology through graph signal processing tools. Graph filters are one
such prominent tool, having been used in applications such as denoising,
interpolation, and classification. However, they are mainly used on fixed
graphs although many networks grow in practice, with nodes continually
attaching to the topology. Re-training the filter every time a new node
attaches is computationally demanding; hence an online learning solution that
adapts to the evolving graph is needed. We propose an online update of the
filter, based on the principles of online machine learning. To update the
filter, we perform online gradient descent, which has a provable regret bound
with respect to the filter computed offline. We show the performance of our
method for signal interpolation at the incoming nodes. Numerical results on
synthetic and graph-based recommender systems show that the proposed approach
compares well to the offline baseline filter while outperforming competitive
approaches. These findings lay the foundation for efficient filtering over
expanding graphs.
Related papers
- 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) - Careful Selection and Thoughtful Discarding: Graph Explicit Pooling
Utilizing Discarded Nodes [53.08068729187698]
We introduce a novel Graph Explicit Pooling (GrePool) method, which selects nodes by explicitly leveraging the relationships between the nodes and final representation vectors crucial for classification.
We conduct comprehensive experiments across 12 widely used datasets to validate our proposed method's effectiveness.
arXiv Detail & Related papers (2023-11-21T14:44:51Z) - 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) - Learning Optimal Graph Filters for Clustering of Attributed Graphs [20.810096547938166]
Many real-world systems can be represented as graphs where the different entities in the system are presented by nodes and their interactions by edges.
An important task in studying large datasets with graphical structure is graph clustering.
We introduce a graph signal processing based approach, where we learn the parameters of Finite Impulse Response (FIR) and Autoregressive Moving Average (ARMA) graph filters optimized for clustering.
arXiv Detail & Related papers (2022-11-09T01:49:23Z) - Graph filtering over expanding graphs [14.84852576248587]
We propose a filter learning scheme for data over expanding graphs.
We show near-optimal performance compared with baselines relying on the exact topology.
These findings lay the foundation for learning representations over expanding graphs by relying only on the connectivity model.
arXiv Detail & Related papers (2022-03-15T16:50:54Z) - Beyond Low-pass Filtering: Graph Convolutional Networks with Automatic
Filtering [61.315598419655224]
We propose Automatic Graph Convolutional Networks (AutoGCN) to capture the full spectrum of graph signals.
While it is based on graph spectral theory, our AutoGCN is also localized in space and has a spatial form.
arXiv Detail & Related papers (2021-07-10T04:11:25Z) - Message Passing in Graph Convolution Networks via Adaptive Filter Banks [81.12823274576274]
We present a novel graph convolution operator, termed BankGCN.
It decomposes multi-channel signals on graphs into subspaces and handles particular information in each subspace with an adapted filter.
It achieves excellent performance in graph classification on a collection of benchmark graph datasets.
arXiv Detail & Related papers (2021-06-18T04:23:34Z) - Graph Neural Networks with Adaptive Frequency Response Filter [55.626174910206046]
We develop a graph neural network framework AdaGNN with a well-smooth adaptive frequency response filter.
We empirically validate the effectiveness of the proposed framework on various benchmark datasets.
arXiv Detail & Related papers (2021-04-26T19:31:21Z) - 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) - 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)
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.