# Towards joint graph learning and sampling set selection from data

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 17 references that are in the map.
- First posted on arXiv 12 Dec 2024.

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

- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Discrete Signal Processing on Graphs: Sampling Theory](https://mlsanity.com/paper/1503.05432/) (2015)
- [Eigendecomposition-Free Sampling Set Selection for Graph Signals](https://mlsanity.com/paper/1809.01827/) (2018)
- [Irregularity-Aware Graph Fourier Transforms](https://mlsanity.com/paper/1802.10220/) (2018)
- [Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment](https://mlsanity.com/paper/1907.06179/) (2019)
- [Practical graph signal sampling with log-linear size scaling](https://mlsanity.com/paper/2102.10506/) (2021)
- [A Probabilistic Interpretation of Sampling Theory of Graph Signals](https://mlsanity.com/paper/1503.06629/) (2015)
- [An efficient algorithm for graph Laplacian optimization based on effective resistances](https://mlsanity.com/paper/2004.08451/) (2020)
- [Joint Graph and Vertex Importance Learning](https://mlsanity.com/paper/2303.08552/) (2023)
- [Graph-based Scalable Sampling of 3D Point Cloud Attributes](https://mlsanity.com/paper/2410.01027/) (2024)

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

- [On the Impact of Downstream Tasks on Sampling and Reconstructing Noisy Graph Signals](https://mlsanity.com/paper/2509.10874/) (2025)
- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)

## Abstract (arXiv)

We explore the problem of sampling graph signals in scenarios where the graph structure is not predefined and must be inferred from data. In this scenario, existing approaches rely on a two-step process, where a graph is learned first, followed by sampling. More generally, graph learning and graph signal sampling have been studied as two independent problems in the literature. This work provides a foundational step towards jointly optimizing the graph structure and sampling set. Our main contribution, Vertex Importance Sampling (VIS), is to show that the sampling set can be effectively determined from the vertex importance (node weights) obtained from graph learning. We further propose Vertex Importance Sampling with Repulsion (VISR), a greedy algorithm where spatially -separated "important" nodes are selected to ensure better reconstruction. Empirical results on simulated data show that sampling using VIS and VISR leads to competitive reconstruction performance and lower complexity than the conventional two-step approach of graph learning followed by graph sampling.