# Tackling Provably Hard Representative Selection via Graph Neural Networks

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 139 references that are in the map.
- First posted on arXiv 20 May 2022.

## Builds on (most cited first, 30 of 62)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Self-Normalizing Neural Networks](https://mlsanity.com/paper/1706.02515/) (2017)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training](https://mlsanity.com/paper/2103.00123/) (2021)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning](https://mlsanity.com/paper/2012.10630/) (2020)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Batch Active Learning at Scale](https://mlsanity.com/paper/2107.14263/) (2021)
- [Learning by Transduction](https://mlsanity.com/paper/1301.7375/) (2013)
- [SLAPS: Self-Supervision Improves Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2102.05034/) (2021)

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

- [Gradient-Free Structured Pruning with Unlabeled Data](https://mlsanity.com/paper/2303.04185/) (2023)
- [Effective Graph and Rank-based Contextual Embeddings for Textual and Multimedia Data](https://mlsanity.com/paper/2608.29001/) (2026)

## 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.