그래프 트랜스포머를 위한 k-최대 내적 어텐션 및 그래프GPS의 표현력: 그래프GPS의 표현력

k-Maximum Inner Product Attention for Graph Transformers and the Expressive Power of GraphGPS The Expressive Power of GraphGPS

그래프 트랜스포머는 전통적인 그래프 신경망의 한계, 예를 들어 과도한 정보 압축 및 장거리 의존성 모델링의 어려움을 극복할 수 있는 잠재력을 보여주었습니다. 그러나 모든 노드 간의 상호 작용을 고려하는 완전 연결 어텐션 메커니즘의 이중 섭동 메모리 및 계산 복잡성은 대규모 그래프에 대한 적용을 방해합니다. 선형화된 어텐션 및 제한된 어텐션 패턴과 같은 대안이 제안되었지만, 이러한 방법은 종종 성능 저하를 초래하거나 표현력을 제한합니다. 효율성과 효과의 균형을 개선하기 위해, 우리는 그래프 트랜스포머를 위한 k-최대 내적(k-MIP) 어텐션을 소개합니다. k-MIP 어텐션은 각 쿼리에 대해 가장 관련성이 높은 키 노드를 상위 k개 항목 선택 연산을 통해 선택하여, 희소하지만 유연한 어텐션 패턴을 생성합니다. 기호 행렬 기반의 어텐션 점수 계산과 결합하여, k-MIP 어텐션은 선형 메모리 복잡성을 제공하며, 완전 연결 어텐션에 비해 최대 10배의 속도 향상을 제공하여, 단일 A100 GPU에서 500k 개 이상의 노드를 가진 그래프를 처리할 수 있습니다. 우리는 k-MIP 어텐션의 표현력에 대한 이론적 분석을 제공하며, k-MIP 어텐션이 그래프 트랜스포머의 표현력을 저해하지 않음을 보여줍니다. 특히, k-MIP 트랜스포머는 모든 완전 연결 어텐션 트랜스포머를 임의의 정밀도로 근사할 수 있음을 증명합니다. 또한, 우리의 어텐션 메커니즘을 통합한 GraphGPS 프레임워크의 표현력을 분석하고, S-SEG-WL 테스트를 기준으로 그래프 구별 능력에 대한 상한을 설정합니다. 마지막으로, 우리는 Long Range Graph Benchmark, City-Networks 벤치마크 및 두 개의 사용자 정의 대규모 유도 포인트 클라우드 데이터 세트에서 우리의 접근 방식을 검증했으며, 일관되게 최고 성능을 보이는 확장 가능한 그래프 트랜스포머 중 하나로 평가되었습니다.

Graph transformers have shown promise in overcoming limitations of traditional graph neural networks, such as oversquashing and difficulties in modelling long-range dependencies. However, their application to large-scale graphs is hindered by the quadratic memory and computational complexity of the all-to-all attention mechanism. Although alternatives such as linearized attention and restricted attention patterns have been proposed, these often degrade performance or limit expressive power. To better balance efficiency and effectiveness, we introduce k-Maximum Inner Product (k-MIP) attention for graph transformers. k-MIP attention selects the most relevant key nodes per query via a top-k operation, yielding a sparse yet flexible attention pattern. Combined with an attention score computation based on symbolic matrices, this results in linear memory complexity and practical speedups of up to an order of magnitude compared to all-to-all attention, enabling the processing of graphs with over 500k nodes on a single A100 GPU. We provide a theoretical analysis of expressive power, showing that k-MIP attention does not compromise the expressiveness of graph transformers: specifically, we prove that k-MIP transformers can approximate any full-attention transformer to arbitrary precision. In addition, we analyze the expressive power of the GraphGPS framework, in which we integrate our attention mechanism, and establish an upper bound on its graph distinguishing capability in terms of the S-SEG-WL test. Finally, we validate our approach on the Long Range Graph Benchmark, the City-Networks benchmark, and two custom large-scale inductive point cloud datasets, consistently ranking among the top-performing scalable graph transformers.