Online Graph Filtering Over Expanding Graphs

Bishwadeep Das, Elvin Isufi

Introduction

Graph filters are fundamental tools in Graph Signal Processing (GSP), utilized for tasks such as denoising, interpolation, and classification. Traditionally, these filters are designed for static graphs with a fixed number of nodes. However, real-world networks—such as social media platforms, epidemic spreads, and recommendation systems—are inherently dynamic and "expanding." In these scenarios, new nodes and edges arrive sequentially, fundamentally altering the graph's spectral properties. Conventional static filters are ill-equipped to handle this evolution, often leading to significant performance degradation as the network grows.

This paper introduces a novel framework for online graph filtering specifically designed for expanding graphs. By integrating online learning principles with GSP, the proposed approach allows filters to adapt in real-time to both incoming data and changing topologies, even when the exact connection patterns are initially unknown.

The Challenge of Expanding Graphs

Processing signals on growing networks presents three primary difficulties that batch processing cannot easily solve:

  1. Streaming Data: Information arrives in a continuous stream, necessitating real-time processing rather than offline computation.
  2. Evolving Topology: The underlying structure changes with every new node, rendering fixed filter coefficients obsolete as the graph's Laplacian or adjacency matrix evolves.
  3. Topological Uncertainty: In many scenarios, such as "cold-start" problems in recommender systems, the exact connection pattern of a new node is unknown at the moment a prediction is required. We must act before the environment reveals how the new node attaches to the existing structure.

Proposed Online Filtering Framework

To address these challenges, the authors treat filter design as a time-varying optimization problem. They propose a suite of algorithms tailored to different levels of topological knowledge:

Deterministic and Stochastic Approaches

  • Deterministic Online Graph Filtering (D-OGF): This is used when the connection pattern (attachment vector) of a new node is known upon arrival. It utilizes projected online gradient descent to update filter coefficients at each time step, ensuring the filter stays optimal relative to the current graph state.
  • Stochastic Online Graph Filtering (S-OGF): Designed for "cold-start" scenarios where connections are initially unknown. It employs heuristic stochastic models (e.g., random attachment) to estimate losses and update the filter parameters.
  • Prediction-Correction (PC-OGF): A two-step mechanism that first predicts the signal using a stochastic model and subsequently "corrects" the filter parameters once the true attachment is revealed by the environment. This feedback loop is critical for long-term accuracy.

Adaptive Learning for Unknown Topologies

Recognizing that a single growth model rarely captures real-world complexity, the authors introduce Ada-OGF (Adaptive Stochastic Online Graph Filtering). This algorithm maintains an ensemble of different attachment rules—such as PageRank, degree centrality, or betweenness—and adaptively weights them. This allows the learner to dynamically identify the most likely connection pattern for new nodes based on the historical performance of each rule.

Theoretical Foundation: Regret Analysis

A core contribution of this work is the regret analysis. The authors provide theoretical guarantees that the proposed online filters achieve sublinear regret. This mathematical proof ensures that as the graph grows, the performance of the online filter converges toward that of an "optimal" fixed filter that had full knowledge of all data and the entire graph evolution in advance. This confirms that the algorithm is effectively "learning" the optimal filtering strategy over time.

Experimental Evaluation

The framework was validated using synthetic data and two real-world datasets: MovieLens 100K and COVID-19 infection tracking.

Performance Highlights

  • MovieLens 100K: In simulating new users joining a movie-rating network, D-OGF achieved a Root Normalized Mean Square Error (NRMSE) of 0.26. In contrast, a pre-trained static filter yielded an NRMSE of 0.84, and a batch-trained solution failed significantly (NRMSE of 6.7) due to its inability to adapt to the non-stationary nature of the expanding user base.
  • COVID-19 Case Prediction: Tracking daily infections across 269 cities, Ada-OGF demonstrated remarkable robustness. Even without prior knowledge of exact city-to-city connections, it achieved an NRMSE of 0.26, matching the performance of deterministic methods that possessed full topological knowledge.
  • Comparison with State-of-the-Art: The proposed filters generally outperformed kernel-based methods like Online Kernel Learning (OKL) and Online Multi-Kernel Learning (OMHKL), particularly in scenarios where the data followed graph-signal properties like smoothness.

Key Insights and Future Directions

The research highlights that online filters are often superior to batch methods in dynamic environments. Batch methods tend to over-depend on the initial training distribution, whereas online filters continuously adapt to the "non-stationary" evolution of the graph. The Prediction-Correction approach emerged as a standout, proving that leveraging ground-truth feedback to fix internal parameters leads to much lower error in subsequent steps.

While the current framework is highly effective, future research may address the computational complexity of graph diffusions in massive-scale graphs through distributed local updates. Additionally, integrating true spatio-temporal dynamics—where signals vary both by node arrival and over time for existing nodes—remains a promising avenue for further exploration in the field of graph signal processing.

Summary updated

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.
BibTeX
@article{das2024online,
  author = {Bishwadeep Das and Elvin Isufi},
  title = {{Online Graph Filtering Over Expanding Graphs}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
  url = {https://openreview.net/forum?id=GsWTRDHxGm},
}
Figure