A Poincar\'e Inequality and Consistency Results for Signal Sampling on Large Graphs

arXiv:2311.10610v2 Announce Type: replace
Abstract: Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean. Existing graph sampling techniques require not only computing the spectra of large matrices but also repeating these computations when the graph changes, e.g., grows. In this paper, we introduce a signal sampling theory for a type of graph limit -- the …

abstract arxiv complexity computing cs.lg graph graphs inequality machine machine learning non-euclidean results sampling scale signal stat.ml the graph type