Tackling Provably Hard Representative Selection via Graph Neural Networks
Representative selection (RS) is the problem of finding a small subset of
exemplars from an unlabeled dataset, and has numerous applications in
summarization, active learning, data compression and many other domains. In
this paper, we focus on finding representatives that optimize the accuracy of a
model trained on the selected representatives. We study RS for data represented
as attributed graphs. 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 that
optimize surrogate functions. Theoretically, we establish a new hardness result
for RS by proving that RS is hard to approximate in polynomial time within any
reasonable factor, which implies a significant gap between the optimum solution
of widely-used surrogate functions and the actual accuracy of the model, and
provides justification for the superiority of representation learning-based
approaches such as RS-GNN over surrogate functions.