Learning Expanding Graphs for Signal Interpolation

Bishwadeep Das, Elvin Isufi

Introduction

In Graph Signal Processing (GSP), the underlying topology is typically treated as a static foundation. However, real-world networks—from social platforms to recommendation engines—are inherently dynamic and expanding. When a new node enters a graph, such as a newly released movie in a database or a new user in a social network, its connectivity to existing nodes is initially unknown. This lack of topological information creates a significant hurdle for downstream tasks like signal interpolation, commonly referred to as the "cold start" problem.

A recent study by Bishwadeep Das and Elvin Isufi addresses this challenge by proposing a framework to learn the connectivity of incoming nodes in a data-driven manner. By modeling node attachment as a stochastic process, the authors demonstrate how to interpolate signals on expanding graphs without requiring pre-defined connectivity or external node features.

The Challenge of Expanding Graphs

Standard GSP techniques, such as graph filtering and denoising, rely on a known graph Laplacian or adjacency matrix. In an expanding graph scenario, an incoming node arrives with an unknown set of edges connecting it to the existing nodes. Without these edges, we cannot define the local operators necessary to estimate the signal value at the new node.

While traditional models like preferential attachment provide statistical rules for graph growth, they are often too rigid for specific signal processing tasks. The goal here is not necessarily to recover the "physical" ground-truth edges, but to identify a connectivity pattern that optimizes the accuracy of signal interpolation.

Methodology: Stochastic Attachment and Optimization

The authors propose a stochastic attachment model where the connectivity of the incoming node is treated as a random vector.

1. The Bernoulli Model

Each potential edge between the new node and the existing graph is modeled as an independent Bernoulli random variable. This model is parameterized by two key variables:

  • Attachment Probabilities ($p$): A vector representing the likelihood of a connection forming between the new node and each existing node.
  • Edge Weights ($w$): A vector representing the strength of those connections, should they exist.

2. Signal Interpolation via Graph Filters

To predict the signal at the new node, the framework employs graph filters—mathematical operators that diffuse signal information across the graph's structure. The authors derive a closed-form expression for the Mean Squared Error (MSE) of this interpolation. This MSE formulation is critical as it explicitly accounts for both the bias of the filter and the variance introduced by the stochastic nature of the edges.

3. Learning Task-Optimal Topology

The parameters $p$ and $w$ are estimated by looking at "historical" incoming nodes—nodes that arrived previously and whose signals and connections are already known. The optimization problem seeks to minimize the reconstruction error over this training set. Because the objective function is non-convex, the authors utilize an alternating projected gradient descent algorithm. This approach iteratively updates the probabilities and weights, ensuring they remain within valid bounds while converging toward a task-optimal configuration.

Experimental Validation

The framework was evaluated using both synthetic benchmarks and real-world recommendation data.

Synthetic Graphs

Using Erdős-Rényi (ER) and Barabási-Albert (BA) models, the authors tested the algorithm's ability to recover growth patterns. The proposed method achieved an MSE between 0.03 and 0.05, significantly outperforming baseline models like uniform attachment or standard preferential attachment, which yielded errors between 0.06 and 0.1.

Real-World Cold Start: MovieLens 100K

The model was applied to the MovieLens 100K dataset to predict user ratings for "new" movies. The results highlighted the model's strength in handling low-interaction users. In these sparse-data scenarios, the proposed method achieved the lowest median error compared to traditional statistical baselines. Furthermore, for high-interaction users, the model demonstrated higher reliability, showing a "thinner tail" in its error distribution—meaning it produced fewer extreme prediction failures.

Key Insights

  • Task-Driven Connectivity: The research shifts the focus from finding the "true" graph to finding the "most useful" graph for a specific task.
  • Weight Importance: Empirical results suggest that optimizing edge weights ($w$) often yields greater performance gains than optimizing attachment probabilities ($p$) alone.
  • Marginal Convexity: The authors identified that with appropriate regularization, the non-convex optimization problem can be "marginally convexified," leading to more stable and reliable convergence during training.

Conclusion

This work provides a robust theoretical and practical foundation for signal processing on growing networks. By treating graph expansion as a learnable stochastic process, it offers a powerful tool for addressing cold-start problems in recommendation systems and beyond. Future research directions include extending the model to handle the simultaneous arrival of multiple nodes and integrating these stochastic models with Graph Neural Networks (GNNs) to leverage complex node features.

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},
}
Figure