본 논문은 기존 그래프 증류 기법의 한계점(전체 데이터셋으로의 훈련 필요성, 매개변수 또는 GNN 아키텍처 변경 시 재증류 필요성, 충분한 크기 감소 실패)을 지적하고, 이를 해결하기 위한 새로운 그래프 증류 방법인 Bonsai를 제시합니다. Bonsai는 메시지 전달 GNN의 기본 처리 단위인 계산 트리를 활용하여, 훈련 세트의 모든 계산 트리를 최대한 대표하는 예시 트리를 신중하게 선택하여 데이터셋을 증류합니다. 선형 시간 복잡도를 가지는 모델 독립적인 알고리즘으로, 6개의 실제 데이터셋에서 기존 기법보다 정확도가 높고 평균 22배 빠른 성능을 보입니다. 채택된 근사 전략에 대한 엄격한 수학적 보장을 기반으로 GNN 아키텍처, 데이터셋 및 매개변수에 대한 강건성을 갖습니다.
