노드 감소 풀링을 통한 그래프 신경망에서의 계층적 표현 학습

그래프 신경망(GNN)에서 풀링 연산자는 입력 그래프의 국소적 요약을 계산하여 전반적인 그래프 특성을 포착하며, 계층적인 표현을 학습하는 깊은 GNN을 구축하는 데 있어 핵심적인 역할을 한다. 본 연구에서는 전체 그래프의 구조를 유지하면서 더 해상도가 낮은 그래프를 생성하는 GNN용 풀링 연산자인 노드 감소 풀링(Node Decimation Pooling, NDP)을 제안한다. 학습 과정에서 GNN은 새로운 노드 표현을 학습하고, 사전 처리 단계에서 오프라인으로 계산된 다단계의 해상도 낮은 그래프 계층에 이를 적합시킨다. NDP는 세 단계로 구성된다. 먼저, 스펙트럴 알고리즘이 \maxcut{} 해를 근사하는 방식으로 분할된 그래프의 한 쪽에 속하는 노드들을 선택하는 노드 감소 절차를 수행한다. 이후 선택된 노드들 사이에 크론(Kron) 축소를 적용하여 해상도가 낮은 그래프를 구성한다. 마지막으로, 생성된 그래프는 매우 밀도가 높기 때문에, GNN 내에서 계산 비용을 줄이기 위해 해상화된 그래프의 인접 행렬을 정리하는 희소화 절차를 적용한다. 특히, 그래프 구조에 큰 영향을 주지 않으면서도 많은 간선을 제거할 수 있음을 보여준다. 실험 결과, NDP는 최신 기술 수준의 그래프 풀링 연산자들과 비교하여 더 높은 효율성을 보이며, 다양한 그래프 분류 과제에서 경쟁력 있는 성능을 달성함을 확인하였다.