Research map / Graph learning / Graph algorithms and clustering
A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes graphon signal sampling theory (Poincaré inequality, uniqueness sets for Paley-Wiener spaces, consistency via Gaussian elimination and spectral clustering) and a graphon-based subsampling algorithm for large graphs, evaluated on transferability and positional encodings.
Problem
Sampling signals on large graphs requires expensive spectral computations that must be repeated whenever the graph changes; a sampling theory that generalizes across graphs drawn from a limit object is needed.
Approach
Formulate graph signal sampling on a graphon (graph limit), prove a graphon Poincaré inequality so complements of certain node sets are uniqueness sets for Paley-Wiener graphon signal spaces, and connect Gaussian elimination on graph Laplacian eigenvectors to kernel spectral clustering to show consistency; the resulting sampled intervals are computed once and reused for any graph sampled from the
Key results
- On Cora, graphon-sampled subgraph training reaches 0.49 ± 0.09 accuracy versus 0.86 for the full graph and 0.46 for random sampling in the base setting, with graphon sampling better than random in the base case.
- On MalNet-Tiny, positional encodings from graphon-sampled subgraphs without isolated nodes reach 0.33 ± 0.06 accuracy versus 0.26 with no PEs and 0.43 with full-graph PEs.
- PE computation on sampled subgraphs takes about 0.075 s versus 12.40 s on the full graph.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use graphon sampling instead of random node sampling | GNN training on subsampled citation graphs · Cora node classification, base | accuracy: 0.46 $\pm$ 0.09 -> 0.49 $\pm$ 0.09 | Helped |
| use graphon sampling instead of random node sampling | GNN training on subsampled citation graphs · CiteSeer node classification, base | accuracy: 0.51 $\pm$ 0.08 -> 0.56 $\pm$ 0.06 | Helped |
| use graphon sampling instead of random node sampling | GNN training on subsampled citation graphs · PubMed node classification, base | accuracy: 0.69 $\pm$ 0.07 -> 0.71 $\pm$ 0.07 | Helped |
| double the number of communities (ablation) | Graphon sampling for node classification · Cora and CiteSeer | accuracy: Cora: 0.49 $\pm$ 0.09 -> 0.56 $\pm$ 0.09; CiteSeer: 0.56 $\pm$ 0.06 -> 0.56 $\pm$ 0.05 | Helped |
| double the number of communities (ablation) | Graphon sampling for node classification · PubMed | accuracy: 0.71 $\pm$ 0.07 -> 0.67 $\pm$ 0.06 | Hurt |
| double the nodes sampled per interval (ablation) | Graphon sampling for node classification · Cora | accuracy: 0.49 $\pm$ 0.09 -> 0.73 $\pm$ 0.05 | Helped |
| double the nodes sampled per interval (ablation) | Graphon sampling for node classification · CiteSeer | accuracy: 0.56 $\pm$ 0.06 -> 0.67 $\pm$ 0.03 | Helped |
| double the nodes sampled per interval (ablation) | Graphon sampling for node classification · PubMed | accuracy: 0.71 $\pm$ 0.07 -> 0.75 $\pm$ 0.05 | Helped |
| double the eigenvalue index (ablation) | Graphon sampling for node classification · Cora, CiteSeer, and PubMed | accuracy: Cora: 0.49 $\pm$ 0.09 -> 0.51 $\pm$ 0.09; CiteSeer: 0.56 $\pm$ 0.06 -> 0.51 $\pm$ 0.10; PubMed: 0.71 $\pm$ 0.07 -> 0.69 | Hurt |
| use graphon-sampled positional encodings rather than no positional encodings | GNN on MalNet-Tiny · MalNet-Tiny graph classification | mean accuracy: 0.26$\pm$0.03 -> 0.29$\pm$0.06 | Helped |
| use graphon-sampled rather than randomly sampled positional encodings | GNN on MalNet-Tiny · MalNet-Tiny graph classification, with isolated nodes | mean accuracy: 0.28$\pm$0.07 -> 0.29$\pm$0.06 | No clear effect |
| remove isolated nodes from the graphon-sampled subgraph (ablation) | Graphon-sampled positional encodings · MalNet-Tiny graph classification | mean accuracy: 0.29$\pm$0.06 -> 0.33$\pm$0.06 | Helped |
Surprising findings
- When the sampled set is enlarged in the eigenvalue index (higher bandwidth), graphon sampling underperforms random sampling, which the authors attribute to too small a sample size.
- On PubMed, doubling the number of communities favors random sampling over graphon sampling.
Limitations
- Consistency and Poincaré results are asymptotic; non-asymptotic analysis is left to future work.
- Graphon-subsampled training accuracy on Cora (0.49) is far below full-graph training (0.86) and the gap over random sampling is within standard deviation in several settings.
- Positional encodings from sampled subgraphs were not as effective as full-graph PEs.
Experimental setup
Datasets: Cora CiteSeer PubMed MalNet-Tiny
Benchmarks: Cora CiteSeer PubMed MalNet-Tiny
Metrics: accuracy runtime (s)
Baselines: random sampling full graph training no positional encodings full-graph Laplacian positional encodings
Builds on: graph signal sampling via Gaussian elimination graphon theory kernel spectral clustering consistency E-optimal sampling
Closest papers by meaning
- Higher-Order Graphon Neural Networks: Approximation and Cut Distance (ICLR 2025 · similarity 0.86)
- Efficient Streaming Algorithms for Graphlet Sampling (NeurIPS 2024 · similarity 0.86)
- Low-Rank Graphon Learning for Networks (NeurIPS 2025 · similarity 0.86)
- WaveNet: Tackling Non-stationary Graph Signals via Graph Spectral Wavelets (AAAI 2024 · similarity 0.86)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.85)
- HoloNets: Spectral Convolutions do extend to Directed Graphs (ICLR 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.