그래프 레이블 선택 (Graph Label Selection) 문제에서는 $n$개의 정점을 가진 그래프와 예산 $k$가 주어졌을 때, 나머지 정점들의 레이블을 정확하게 예측할 수 있도록 하는 $k$개의 정점을 선택하는 것을 목표로 합니다. 이 문제는 전체 그래프로부터 작고 대표성 있는 집합을 추출 (distilling)하는 과정을 공식화한 것입니다. 본 논문에서는 표준 예산 제약 조건 (budget constraint) 하에서 그래프 레이블 선택을 위한 최초의 $\tilde{O}(\log^{1.5} n)$-근사 알고리즘 (approximation algorithm)을 제시합니다. 기존 연구들은 $k$보다 훨씬 더 많은 레이블된 정점을 허용하는 자원 증강 (resource augmentation)에 의존하거나, 증명 가능한 보장 (provable guarantees)이 없는 휴리스틱 (heuristics)으로만 구성되어 있었습니다. 마지막으로, 본 논문은 우리 알고리즘의 실용적인 휴리스틱 변형들이 품질을 본질적으로 유지하면서도 이전 방법들보다 훨씬 더 큰 그래프로 확장 (scale) 가능하다는 것을 입증합니다.