🤖 machine learning

A Survey of Graph Transformers: Architectures, Theories and Applications

본 논문은 그래프 트랜스포머(Graph Transformers)에 대한 포괄적인 조사 연구를 제시하며, 구조적 처리 전략을 바탕으로 이들의 아키텍처를 체계적으로 분류하고, 이론적 표현력을 분석하며, 관계형, 기하학적, 동적 및 이종 그래프 형태에 걸친 응용 분야를 정리함으로써 실질적인 지침을 제공하고 향후 연구 방향을 제시한다.

원저자: Chaohao Yuan, Kangfei Zhao, Ercan Engin Kuruoglu, Liang Wang, Tingyang Xu, Wenbing Huang, Deli Zhao, Hong Cheng, Yu Rong

게시일 2026-07-28

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Chaohao Yuan, Kangfei Zhao, Ercan Engin Kuruoglu, Liang Wang, Tingyang Xu, Wenbing Huang, Deli Zhao, Hong Cheng, Yu Rong

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

컴퓨터에게 세상을 픽셀의 격자나 단어의 목록이 아니라, 거대하고 뒤엉킨 연결의 그물망으로 이해하도록 가르치려 한다고 상상해 보십시오. 친구들은 점이고 악수는 선인 소셜 네트워크나, 원자들은 점이고 화학 결합은 선인 분자를 떠올려 보세요. 이것이 바로 "그래프 데이터(graph data)"입니다. 이는 본래 무질서하고 서로 연결된 것들을 표현하는 방식입니다. 오랫동안 이 그물망을 이해하기 위한 가장 좋은 도구는 그래프 신경망(Gational Neural Networks, GNN)이라 불렸습니다. 이것들은 마치 '전화기 게임(game of telephone)'처럼 작동했습니다. 하나의 노드(점)가 즉각적인 이웃들의 이야기를 듣고, 자신의 이야기를 업데이트한 뒤, 그 새로운 이야기를 이웃들에게 전달하는 방식이었죠. 이는 근처의 소문을 듣는 데는 훌륭했지만, 방 저편에서 들려오는 뉴스를 듣는 데는 엉망이었습니다. 만약 웹이 너무 크거나 연결이 너무 복잡하면, 메시지가 이동하는 동안 너무 흐릿해져서 결국 모두가 똑같은 소리를 내게 되었습니다.

현대 AI를 혁신하며 컴퓨터가 책을 읽고 이미지를 생성하는 방식을 바꾼 슈퍼스타, 트랜스포머(Transformer)가 등장했습니다. 트랜스포머는 '슈퍼 리스너(super-listeners)'와 같습니다. 이들은 문장 속의 단어들이 아무리 멀리 떨어져 있더라도 한 번에 모든 단어에 주의를 기울일 수 있습니다. 이들은 장거리 관계를 혼란 없이 이해하는 것으로 유명합니다. 과학자들이 던진 큰 질문은 이것이었습니다. "만약 트랜스포머에게 이 뒤엉킨 그물망을 들을 수 있는 능력까지 준다면 어떻게 될까?" 이것이 바로 그래프 트랜스포머(Graph Transformers)의 이야기입니다. 이들은 기존의 "전화기 게임" 방식이 해결하지 못했던 문제들을 풀기 위해, 트랜스포머의 초능력과 그래프의 구조를 결합하려고 노력하는 새로운 세대의 모델입니다.

이 논문은 폭발적으로 성장하는 그래프 트랜스포머의 세계를 안내하는 거대한 투어 가이드입니다. 저자들(일류 대학과 기술 연구소의 연구진)은 단순히 새로 나온 모델들을 나열하는 데 그치지 않고, 이 혼돈을 명확한 지도로 정리했습니다. 그들은 이 모델들이 어떻게 구축되는지, 왜 작동하는지(혹은 왜 작동하지 않는지), 그리고 실제로 어디에 사용되고 있는지를 살펴보았습니다.

먼저, 그들은 연구자들이 트랜스포머가 그래프를 이해하도록 만드는 데 사용하는 다양한 "아키텍처(architectures)", 즉 설계도를 분석했습니다. 알고 보니 이를 수행하는 방법은 단 한 가지만이 아니었습니다. 어떤 모델은 웹의 모든 점을 개별적인 단어로 취급하고(노드 수준), 다른 모델은 점들을 이웃 단위로 그룹화하거나(서브그래프 수준), 심지어 연결 자체를 단어로 취급하기도 합니다(엣지 수준). 어떤 모델은 트랜스포머에게 점이 웹의 어디에 위치해 있는지 알려주기 위해 특수한 "위치 코드(positional codes)"를 추가하는데, 이는 마치 우체부에게 편지를 배달할 위치를 알 수 있도록 도시의 모든 집에 고유한 주소를 부여하는 것과 같습니다. 또 다른 모델들은 "주의(attention)" 메커즘—무엇에 집중할지 결정하는 뇌의 부분—을 수정하여, 모델이 단순히 무작위적인 점들에 집중하는 것이 아니라 실제 연결 관계에 주목하도록 만듭니다. 저자들은 또한 가장 똑똑한 모델 중 일부가 기존의 "전화기 게임" 스타일과 새로운 "슈퍼 리스너" 스타일을 혼합하여 최상의 결과를 얻어내는 하이브리드 형태라는 점을 발견했습니다.

또한 이 논문은 이론적인 측면을 파고들며 어려운 질문을 던집니다. "이 새로운 모델들이 실제로 더 똑똑한 것인가, 아니면 그저 목소리만 더 큰 것인가?" 그들은 두 그래프가 겉보기에는 동일해 보이지만 실제로는 미세하게 다르다는 것을 구별할 수 있는지 확인하기 위해 수학적 테스트를 사용하여 그래프 트랜스포머를 기존 방식들과 비교했습니다. 그 결과, 그래프 트랜스포머가 이론적으로는 더 강력하지만, "더 강력하다"는 것이 실생활에서 항상 승리를 보장하는 것은 아니라는 것을 발견했습니다. 때때로 데이터에 노이즈가 많거나 컴퓨터의 메모리가 부족한 경우, 기존의 더 단순한 방식들이 여전히 효과적일 수 있습니다.

마지막으로, 저자들은 이 모델들이 실제로 승리하고 있는 분야를 분류했습니다. 응용 분야를 네 가지 주요 진영으로 나누었습니다:

관계 그래프(Relational Graphs): 소셜 네트워크나 화학 분자처럼, 누가 누구를 아는지에 초점을 맞춥니다.
기하학적 그래프(Geometric Graphs): 3D 단백질 구조나 결정체처럼, 공간에서의 정확한 모양과 거리가 중요합니다.
동적 그래프(Dynamic Graphs): 교통 흐름이나 소문 확산처럼, 웹이 시간에 따라 변하는 경우입니다.
이종 그래프(Heterogeneous Graphs): 사용자, 제품, 이미지가 섞여 있는 것처럼, 서로 다른 유형의 것들이 연결된 경우입니다.

논문은 이러한 모델을 구축하려는 사람들을 위한 실질적인 가이드로 마무리됩니다. 최선의 설계는 전적으로 당신이 이해하려는 웹의 종류에 달려 있다고 제안합니다. 만약 3D 형상을 보고 있다면, 기하학을 다루기 위한 특정 도구가 필요합니다. 만약 교통량을 추적하고 있다면, 시간을 다루는 도구가 필요합니다. 저자들은 그래프 트랜스포머가 거대한 도약이지만, 모든 것을 해결해 주는 마법 지팡이는 아니라고 조언합니다. 이들은 강력하지만, 많은 컴퓨팅 자원을 필요로 하며 때로는 매우 크고 무질서한 웹에서 혼란을 겪기도 하는 등의 과제를 안고 있습니다. 논문은 미래를 향해 나아가며, 다음의 큰 돌파구는 이 모델들을 다른 새로운 기술과 결합하거나, 대규모 언어 모델이 텍스트에 하는 것처럼 한 번 학습한 그래프에 대해 다양한 작업을 수행할 수 있는 "파운데이션 모델(foundational models)"을 만드는 데서 올 수 있음을 시사하며 끝을 맺습니다.

기술 요약: 그래프 트랜스포머 서베이: 아키텍처, 이론 및 응용

문제 정의

그래프 신경망(GNN), 특히 메시 전달(message-passing) 패러다임에 기반한 모델들은 비유클리드 데이터 모델링에서 상당한 성공을 거두었습니다. 그러나 이들은 오버 스무딩(over-smoothing)(깊은 층에서 노드 임베딩이 구별 불가능해지는 현상)과 오버 스쿼싱(over-squashing)(정보 압축으로 인해 장거리 의존성을 효과적으로 포착하지 못하는 현상)을 포함한 본질적인 한계에 직면해 있습니다. 트랜스포머 아키텍처는 시퀀셜 데이터(예: NLP, 비전)에서 장거리 의존성을 포착하는 데 탁월한 성과를 보여왔으나, 표준 트랜스포머는 그래프의 고유한 구조적 정보를 무시합니다. 결과적으로, 전통적인 GNN의 한계를 극복하면서 그래프 구조를 처리할 수 있도록 트랜스포머 아키텍처를 적응시킨 **그래프 트랜스포머(GT)**에 대한 체계적인 검토가 필요합니다.

방법론 및 분류 체계

본 서베이는 GT를 아키텍처(Architectures), 이론(Theories), **응용(Applications)**이라는 세 가지 주요 관점을 통해 조직하여 문헌을 종합적으로 검토합니다.

1. 아키텍처 전략

저자들은 구조적 사전 지식(structural priors)을 트랜스포머 프레임워크에 통합하는 방식에 따라 기존 GT 아키텍처를 다음과 같이 분류합니다:

다단계 그래프 토큰화 (Multi-level Graph Tokenization): 그래프 데이터를 시퀀셜 토큰으로 변환합니다.
- 노드 수준(Node-level): 각 노드를 하나의 토큰으로 취급합니다 (가장 세밀한 단위).
- 엣지 수준(Edge-level): 상호작용 역학을 포착하기 위해 엣지를 토큰으로 취급합니다.
- 서브그래프 수준(Subgraph-level): 고차 모티프(higher-order motifs)를 포착하기 위해 유도된 로컬 패치를 토큰으로 취급합니다.
- 홉 수준(Hop-level): 거리 셸(distance shells)과 확장성을 강조하기 위해 앵커 노드 주변의 정렬된 이웃 시퀀스를 구축합니다.
구조적 위치 인코딩 (Structural Positional Encoding, PE): 그래프 구조에 따른 노드 위치를 표현하도록 PE를 적응시킵니다.
- 절대적 PE (Absolute PE): 그래프 구조(예: 라플라시안 고유벡터, 랜덤 워크 확률, 노드 차수)에 기반하여 고유한 임베딩을 할당합니다.
- 상대적 PE (Relative PE): 쌍별 관계(pairwise relationships)를 어텐션 메커니즘에 직접 주입합니다 (예: 최단 경로 거리, 저항 거리).
구조 인식 어텐션 메커니즘 (Structure-aware Attention Mechanisms): 그래프 토폴로지를 반영하도록 어텐션 행렬을 수정합니다.
- 어텐션 바이어스 (Attention Bias): 구조적 지표(예: 최단 경로, 엣지 특징)에서 유도된 바이어스 항을 어텐션 점수에 추가합니다.
- 어텐션 마스크 (Attention Mask): 어텐션 연결을 마스킹하거나 가중치를 두기 위해 구조적 행렬(예: 인접 행렬, 확산 커널)을 사용합니다.
- 엣지 수준 입력 (Edge-level Input): 엣지 토큰을 어텐션 계산에 직접 포함합니다.
모델 앙상블 (Model Ensemble): 로컬 메시 전달과 글로벌 어텐션을 모두 활용하기 위해 다양한 구성(순차적, 인터리브형, 병렬형)으로 GNN과 트랜스포머를 결 der 합니다.

2. 이론적 기초

본 서베이는 주로 와이스펠러-레만(Weisfeiler-Lehman, WL) 테스트 계층을 벤치마크로 사용하여 GT의 **표현력(expressivity)**을 조사합니다.

토큰화와 표현력: 고차 토큰화(서브그래프, 엣지, 홉)는 모델이 $k$ -차 WL 테스트를 모방할 수 있게 하여, 1-WL(표준 GNN)이 구분할 수 없는 그래프 구조를 구분할 수 있게 합니다.
위치 인코딩: 이론적 분석에 따르면 강력한 PE는 대칭성을 깰 수 있지만, 적절한 토큰화와 결합되지 않으면 본질적으로 고차 구조적 정체성을 제공하지는 않습니다. 상대적 PE는 쌍별 관계에 더 효과적인 경우가 많으며, 절대적 PE는 글로벌 좌표를 제공합니다.
한계점: 이론적 표현력(최악의 경우 구별 가능성)이 항상 경험적 성능으로 직결되는 것은 아니며, 이는 최적화, 샘플 효율성 및 데이터 분포의 영향도 받습니다.

3. 응용 분야 조직

저자들은 응용 분야를 도메인별(예: 화학, 사회 네트워크)로 조직하는 대신, **그래프 조직 형태(graph organization forms)**에 따라 분류합니다:

관계형 그래프 (Relational Graphs): 이산적 의미론을 가집니다 (예: 분자, 지식 그래프). 핵심 설계는 관계 인식 바이어스와 최단 경로 인코딩을 포함합니다.
기하학적 및 주기적 그래프 (Geometric & Periodic Graphs): 3D 좌표와 격자 구조를 가진 데이터입니다 (예: 단백질, 결정). 핵심 설계는 유클리드 변환에 대한 불변성/동변성을 보장하기 위한 동변(equivariant) 레이어와 거리 인식 어텐션을 포함합니다.
동적 그래프 (Dynamic Graphs): 시간적으로 진화하는 구조입니다 (예: 교통량, 루머). 핵심 설계는 시간적 위치 인코딩과 시공간 결합 어텐션을 포함합니다.
이종/멀티모달 그래프 (Heterogeneous/Multimodal Graphs): 여러 노드/엣지 타입 또는 모달리티를 가진 그래프입니다. 핵심 설계는 타입별 프로젝션과 교차 어텐션 메커니즘을 포함합니다.

4. 실무 가이드

본 논문은 이러한 발견을 **실무 가이드 테이블 (Table 4)**로 합성하여, 채택 빈도에 따라 아키텍처 구성 요소를 네 가지 그래프 조직 형태에 매핑합니다. 이를 통해 실무자는 단순히 응용 도메인이 아니라 입력 구조에 따라 설계 패밀리(예: 기하학적 그래프를 위해 거리 기반 어텐션 사용 또는 동적 그래프를 위해 시간적 PE 사용)를 선택할 수 있습니다.

주요 기여

통합된 아키텍처 프레임워크: 구조적 정보를 통합하기 위한 네 가지 뚜렷한 전략으로 GT를 체계적으로 분류하여, 단순한 수정을 넘어선 설계 공간을 명확히 했습니다.
이론적 합성: WL 테스트의 관점에서 GT의 표현력을 비판적으로 검토하여, 토큰화 능력과 위치 인코딩의 역할을 구분하고, 이론적 능력과 경험적 견고함 사이의 간극을 강조했습니다.
응용 재구성: 그래프 조직 형태(관계형, 기하학적, 동적, 이종)를 기반으로 한 새로운 GT 응용 분류 체계를 제시하여, 다양한 도메인 전반에 걸친 일관된 설계 패턴을 밝혀냈습니다.
실무 로드맵: 특정 그래프 유형에 적합한 아키텍처 선택을 돕기 위해 빈도 기반의 가이드 테이블을 제공합니다.
미래 방향: 데이터 제약 도메인으로의 GT 확장, GT와 멀티모달 파운데이션 모델의 통합, 셀프 어텐션의 대안 탐색(예: Graph Mamba), 그리고 스펙트럴 이론과 아키텍처 설계 간의 간극 해소 등 열린 과제들을 식별했습니다.

결과 및 주장

본 논문은 새로운 실험 결과를 제시하는 것이 아니라, 기존 문헌을 합성하여 다음과 같은 결론을 도출합니다:

아키텍처-태스크 정렬: GT 설계의 효과는 특정 응용 도메인보다 입력 그래프의 조직 형태에 의해 더 강력하게 예측됩니다. 예를 들어, 기하학적 그래프는 일관되게 동변 업데이트와 거리 기반 어텐션을 요구하는 반면, 관계형 그래프는 최단 경로 바이어스의 이점을 얻습니다.
표현력 vs 성능: 서브그래프 토큰화와 같은 특정 아키텍처 선택이 이론적으로 1-WL 이상의 표현력을 높여주지만, 이것이 반드시 우수한 경험적 성능을 보장하는 것은 아닙니다. 계산 비용, 안정성(예: 라플라시안 PE의 섭동 민감도), 태스크의 성격(로컬 vs 글로벌) 등이 결정적인 역할을 합니다.
확장성 및 동변성: 선형 어텐션, 희소 메커니즘, 홉 수준 토큰화 등을 통해 확장성 문제를 해결하고, SE(3)-동변 레이어를 통해 동변성을 확보하는 데 상당한 진전이 있었으나, 이를 대규모 데이터 희소 도메인으로 확장하는 데에는 여전히 과제가 남아 있습니다.

의의

저자들은 본 서료가 주로 아키텍처의 세부 사항에 집중했던 이전 리뷰들과 달리, 아키텍처적 통찰, 이론적 표현력, 그리고 교차 도메인 응용을 하나의 통합된 프레임워크로 결합했다는 점에서 중요하다고 주장합니다. 이 논문은 GT 설계 선택을 이해하기 위한 체계적인 방법을 제공하며, 연구자와 실무자가 특정 그래프 구조에 적합한 모델을 선택하도록 안내하고, 그래프 파운데이션 모델(Graph Foundational Models) 개발 및 장거리 의존성 포착을 위한 비-어텐션 메커니즘 탐색과 같은 향후 연구 방향을 제시하는 것을 목표로 합니다.