DiffWire: Lovász 경계를 통한 유도형 그래프 리와이어링

그래프 신경망(GNNs)은 다양한 분야에서 노드 및 그래프 분류, 링크 예측, 노드 및 그래프 클러스터링과 같은 그래프 관련 작업에 경쟁력 있는 성능을 보여주었다. 대부분의 GNN은 메시지 전달 프레임워크를 사용하므로 MPNN(Message Passing Neural Networks)라고 불린다. 이러한 모델은 희망적인 결과를 내놓았지만, 과도한 스무딩(over-smoothing), 과도한 압축(over-squashing), 그리고 정보 도달 부족(under-reaching) 등의 문제에 시달리고 있다. 기존 연구에서는 그래프 리와이어링(graph rewiring)과 그래프 풀링(graph pooling)을 이러한 한계를 해결하기 위한 해결책으로 제안해왔다. 그러나 현재 최고 성능을 기록하는 대부분의 그래프 리와이어링 기법은 그래프의 전반적인 위상 구조를 유지하지 못하며, 미분 가능하지도 않고, 유도적(inductive)이 아니며, 하이퍼파라미터 조정이 필요하다는 단점이 있다. 본 논문에서는 로바슈 경계(Lovász bound)를 활용하여, 원칙적이고 완전히 미분 가능하며 하이퍼파라미터가 필요 없는 새로운 그래프 리와이어링 프레임워크인 DiffWire를 제안한다. 제안된 방법은 MPNN 내에 두 가지 새로운 보완적 레이어를 제안함으로써 그래프 리와이어링에 대한 통합적 이론을 제공한다. 첫째, CT-Layer는 전이 시간(commute time)을 학습하고 이를 엣지 재가중에 대한 관련성 함수(relevance function)로 활용한다. 둘째, GAP-Layer는 네트워크의 특성과 작업의 성격에 따라 스펙트럴 갭(spectral gap)을 최적화하는 레이어이다. 우리는 그래프 분류를 위한 벤치마크 데이터셋을 활용하여 각 레이어의 효과를 실험적으로 검증하였다. 또한 CT-Layer가 동질성(homophilic) 및 이질성(heterophilic) 노드 분류 작업에 어떻게 활용될 수 있는지에 대한 초기 연구를 수행하였다. DiffWire는 전이 시간의 학습 가능성을 곡률(curvature)과 관련된 정의들과 결합함으로써, 더 표현력이 풍부한 MPNN을 설계할 수 있는 길을 열어준다.