Tackling Provably Hard Representative Selection via Graph Neural Networks
Not on the map. Why?
Abstract (arXiv)
Representative Selection (RS) is the problem of finding a small subset of exemplars from a dataset that is representative of the dataset. In this paper, we study RS for attributed graphs, and focus on finding representative nodes that optimize the accuracy of a model trained on the selected representatives. Theoretically, we establish a new hardness result forRS (in the absence of a graph structure) by proving that a particular, highly practical variant of it (RS for Learning) is hard to approximate in polynomial time within any reasonable factor, which implies a significant potential gap between the optimum solution of widely-used surrogate functions and the actual accuracy of the model. We then study the setting where a (homophilous) graph structure is available, or can be constructed, between the data points.We show that with an appropriate modeling approach, the presence of such a structure can turn a hard RS (for learning) problem into one that can be effectively solved. To this end, we develop RS-GNN, a representation learning-based RS model based on Graph Neural Networks. Empirically, we demonstrate the effectiveness of RS-GNN on problems with predefined graph structures as well as problems with graphs induced from node feature similarities, by showing that RS-GNN achieves significant improvements over established baselines on a suite of eight benchmarks.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 62 of its 139 references that are in the map. First posted on arXiv 20 May 2022.
Builds on
62 of 139 references.
References · 62
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2017Neural Discrete Representation Learningcited by 4,650
- 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
- 2018UMAP: Uniform Manifold Approximation and Projection for Dimension Reductioncited by 2,841
- 2018Dynamic Graph CNN for Learning on Point Cloudscited by 2,220
- 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
- 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
- 2019Simplifying Graph Convolutional Networkscited by 1,470
- 2018Deep Graph Infomaxcited by 1,101
- 2018Pitfalls of Graph Neural Network Evaluationcited by 994
- 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
38 more
- 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
- 2017Self-Normalizing Neural Networkscited by 591
- 2021Deep Learning on a Data Diet: Finding Important Examples Early in Trainingcited by 529
- 2019Graph U-Netscited by 489
- 2019Self-Attention Graph Poolingcited by 421
- 2019Selection via Proxy: Efficient Data Selection for Deep Learningcited by 337
- 2020SIGN: Scalable Inception Graph Neural Networkscited by 283
- 2021GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Trainingcited by 269
- 2020GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learningcited by 224
- 2018Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimizationcited by 220
- 2020Graph Clustering with Graph Neural Networkscited by 163
- 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
- 2019Attributed Graph Clustering: A Deep Attentional Embedding Approachcited by 149
- 2020Structural Deep Clustering Networkcited by 145
- 2018Contextual Stochastic Block Modelscited by 134
- 2021Batch Active Learning at Scalecited by 127
- 2013Learning by Transductioncited by 120
- 2021SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networkscited by 108
- 2020FairBatch: Batch Selection for Model Fairnesscited by 99
- 2019Attributed Graph Clustering via Adaptive Graph Convolutioncited by 96
- 2021RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learningcited by 72
- 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
- 2019Learning From Less Data: A Unified Data Subset Selection and Active Learning Framework for Computer Visioncited by 64
- 2020Memory-Based Graph Networkscited by 56
- 2022GraphWorld: Fake Graphs Bring Real Insights for GNNscited by 56
- 2016Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithmscited by 54
- 2017Active Learning for Graph Embeddingcited by 53
- 2022Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunitiescited by 52
- 2019Overlapping Community Detection with Graph Neural Networkscited by 45
- 2018Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithmscited by 44
- 2021Attention-driven Graph Clustering Networkcited by 40
- 2021VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantizationcited by 39
- 2019Active Learning for Graph Neural Networks via Node Feature Propagationcited by 37
- 2013Efficient Monte Carlo and greedy heuristic for the inference of stochastic block modelscited by 29
- 2021Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximizationcited by 28
- 2015The Hardness of Approximation of Euclidean k-meanscited by 25
- 2021Adaptive Sampling for Minimax Fair Classificationcited by 24
- 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
50 most cited of 62 All 62 (JSON)
Built on by
Citing papers per year: 2023: 1; 2024: 0; 2025: 0; 2026: 1.
2 papers.