# Learning Expanding Graphs for Signal Interpolation

arXiv: https://arxiv.org/abs/2203.07966 · HTML: https://mlsanity.com/paper/2203.07966/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 15 Mar 2022.

## Builds on (most cited first, 10 of 10)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Advances in Distributed Graph Filtering](https://mlsanity.com/paper/1808.03004/) (2018)
- [State-Space Network Topology Identification from Partial Observations](https://mlsanity.com/paper/1906.10471/) (2019)
- [Online Graph-Adaptive Learning with Scalability and Privacy](https://mlsanity.com/paper/1812.00974/) (2018)
- [Recursive Prediction of Graph Signals with Incoming Nodes](https://mlsanity.com/paper/1911.11542/) (2019)
- [Online Time-Varying Topology Identification via Prediction-Correction Algorithms](https://mlsanity.com/paper/2010.11634/) (2020)

## Built on by (most cited first, 4 of 4)

- [Topology-aware Embedding Memory for Continual Learning on Expanding Networks](https://mlsanity.com/paper/2401.13200/) (2024)
- [Online Filtering over Expanding Graphs](https://mlsanity.com/paper/2301.06898/) (2023)
- [Online Graph Filtering Over Expanding Graphs](https://mlsanity.com/paper/2409.07204/) (2024)
- [Stochastic Sequential Decision Making over Expanding Networks with Graph Filtering](https://mlsanity.com/paper/2603.19501/) (2026)

## Abstract (arXiv)

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.