Learning Expanding Graphs for Signal Interpolation

Bishwadeep Das, Elvin Isufi

In the world of Graph Signal Processing (GSP), we usually assume the "ground" we are walking on—the graph topology—is fixed. But in reality, graphs are alive; they grow. Think of a movie recommendation system: every day, new movies are added. How do we predict a user's rating for a movie that has no previous connections to the existing database? This is the "cold start" problem, and a new paper by Bishwadeep Das and Elvin Isufi offers a clever GSP-based solution.

TL;DR

This paper introduces a data-driven framework to interpolate signal values on new nodes entering a graph without knowing their exact connectivity. By modeling node attachment as a stochastic process and learning its parameters from historical data, the authors outperform traditional statistical models in tasks like cold-start movie recommendations.

What Problem Does This Paper Address?

Most GSP techniques require a known, fixed graph structure to perform tasks like denoising or interpolation. However, many real-world networks are expanding graphs, where new nodes arrive over time.

The challenge is that when a new node (an "incoming node") arrives, we don't know its neighbors. Without knowing how it connects to the rest of the graph, we can't use standard graph filters to estimate its signal value (e.g., a rating, a sensor reading, or a class label). Existing solutions often rely on node features (which might not exist) or rigid statistical models (like preferential attachment) that don't always fit the specific task at hand.

Methods

The authors propose a stochastic attachment model. Instead of assuming a fixed set of neighbors, they treat the connectivity of a new node as a random vector.

  1. The Model: Each potential edge between the new node and the existing graph is modeled as a Bernoulli random variable. This is governed by two learnable parameters:
  2. $p$ (Attachment Probabilities): How likely is the new node to connect to node $i$?
  3. $w$ (Edge Weights): If a connection exists, how strong is it?
  4. Signal Interpolation via Graph Filters: They use graph filters—local operators that diffuse information across the network—to predict the signal at the new node. They derive a closed-form expression for the Mean Squared Error (MSE) of this interpolation, which accounts for both the model's bias and the variance caused by the stochastic nature of the connections.
  5. Learning from the Past: To find the best $p$ and $w$, they look at "earlier" incoming nodes whose connectivity and signals are already known. They set up an optimization problem to minimize the reconstruction error on this training set.
  6. Optimization: Since the resulting problem is non-convex, they develop an alternating projected gradient descent algorithm. This approach iteratively updates the probabilities and weights to find a task-optimal connectivity pattern.

Datasets

The authors validated their approach using two types of data:

  • Synthetic Graphs: They generated random graphs using the Erdős-Rényi (ER) and Barabási-Albert (BA) models to test the algorithm's ability to recover known growth patterns.
  • Real-World Data: They used the MovieLens 100K dataset, a classic benchmark for recommender systems. They simulated a cold-start scenario by treating a subset of movies as new arrivals and attempting to predict user ratings.

Key Insights and Ideas

  • Task-Driven Topology: Instead of trying to find the "true" physical connections, the model learns a "task-specific" connectivity. It asks: What connections would make my signal prediction most accurate?
  • The Bias-Variance Trade-off: The paper mathematically demonstrates that minimizing interpolation error isn't just about matching the signal (bias); it's also about minimizing the uncertainty in the connection pattern (variance).
  • Marginal Convexity: While the overall problem is non-convex, the authors identify specific conditions (regularization weights) under which the problem becomes "marginally convex," allowing for more stable convergence.
  • Weights vs. Probabilities: Interestingly, the results suggest that learning the edge weights ($w$) is often more impactful for performance than learning the attachment probabilities ($p$).

Key Results

  • Synthetic Superiority: On ER and BA graphs, the proposed method achieved an MSE of 0.03–0.05, significantly lower than standard uniform or preferential attachment baselines (which ranged from 0.06 to 0.1).
  • Cold-Start Success: In the MovieLens experiment, the model excelled in the most difficult scenario: low-interaction users. For users with few ratings, the proposed method achieved the lowest median error, proving it can effectively "personalize" recommendations even with sparse data.
  • Robustness: For high-interaction users, while simple mean-prediction is competitive, the proposed model showed a much "thinner tail" in its error distribution, meaning it is less likely to make massive prediction failures compared to baseline attachment models.

Limitations and Future Work

The current framework focuses on the arrival of a single node at a time. While the authors mention that the math can be extended to multiple nodes, the experimental results only cover the single-node case.

Future work could explore:

  • Sequential Arrivals: How does the model perform when a long sequence of nodes arrives, and the graph grows significantly?
  • Dynamic Signals: Integrating time-varying signals on these expanding graphs.
  • Deep Learning Integration: Combining this stochastic GSP approach with Graph Neural Networks (GNNs) for more complex feature-based interpolation.

Summary updated

Abstract

Performing signal processing over graphs requires knowledge of the underlying fixed topology. However, graphs often grow in size with new nodes appearing over time, whose connectivity is typically unknown; hence, making more challenging the downstream tasks in applications like cold start recommendation. We address such a challenge for signal interpolation at the incoming nodes blind to the topological connectivity of the specific node. Specifically, we propose a stochastic attachment model for incoming nodes parameterized by the attachment probabilities and edge weights. We estimate these parameters in a data-driven fashion by relying only on the attachment behaviour of earlier incoming nodes with the goal of interpolating the signal value. We study the non-convexity of the problem at hand, derive conditions when it can be marginally convexified, and propose an alternating projected descent approach between estimating the attachment probabilities and the edge weights. Numerical experiments with synthetic and real data dealing in cold start collaborative filtering corroborate our findings.
BibTeX
@inproceedings{das2022learning,
  author = {Bishwadeep Das and Elvin Isufi},
  title = {{Learning Expanding Graphs for Signal Interpolation}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=905z7KdUIE},
}

Loading related content...

Figure