Weisfeiler와 Leman이 희소해지다: 확장 가능한 고차 그래프 임베딩에 대한 연구

1차원 Weisfeiler-Leman 알고리즘과 해당 신경망 구조를 기반으로 하는 그래프 커널이 최근 (감독된) 그래프 학습에서 강력한 도구로 부상하고 있습니다. 그러나 이 알고리즘의 순전히 국소적인 특성 때문에 주어진 데이터에서 중요한 패턴을 놓칠 수 있으며, 이진 관계만 처리할 수 있다는 한계가 있습니다. $k$-차원 Weisfeiler-Leman 알고리즘은 이를 해결하기 위해 정점 집합 위에서 정의된 $k$-튜플을 고려하고, 이러한 정점 튜플 간의 적절한 인접성을 정의합니다. 따라서, 이 알고리즘은 정점 간의 고차 상호작용을 고려합니다. 그러나 이 알고리즘은 확장성이 떨어지고, 머신러닝 환경에서 사용될 때 과적합 문제를 겪을 수 있습니다. 따라서, 표현력이 뛰어나면서도 확장성이 좋고 과적합에 덜 취약한 WL 기반 그래프 학습 방법을 설계하는 것이 여전히 중요한 미해결 문제입니다.본 연구에서는 원래의 이웃 집합의 부분집합을 고려하여 더 확장적이며 과적합에 덜 취약하도록 설계된 국소 변형 알고리즘과 해당 신경망 구조를 제안합니다. (우리 알고리즘 중 하나의) 표현력은 비동형인 그래프를 구분하는 능력 측면에서 원래 알고리즘보다 엄격하게 높습니다. 실험 연구 결과, 국소 알고리즘이 커널 및 신경망 구조 모두에서 계산 시간을 크게 줄이고 과적합을 방지한다는 것을 확인하였습니다. 커널 버전은 다양한 벤치마크 데이터셋에서 그래프 분류에 있어 새로운 최고 성능(SOTA)을 달성하였으며, 신경망 버전은 대규모 분자 회귀 작업에서 유망한 성능을 보여주었습니다.