핵심 12편
- On the Bottleneck of Graph Neural Networks and its Practical Implications (ICLR 2021)
- Understanding Over-squashing and Bottlenecks on Graphs via Curvature (ICLR 2022)
- Revisiting Heterophily for Graph Neural Networks (NeurIPS 2022)
- Understanding Heterophily for Graph Neural Networks (NeurIPS 2022)
- Graphormer: Do Transformers Really Perform Badly for Graph Representation? (NeurIPS 2021)
- Recipe for a General, Powerful, Scalable Graph Transformer (GraphGPS) (NeurIPS 2022)
- Exphormer: Sparse Transformers for Graphs (ICML 2023)
- Ordering Message Passing to Deal with Heterophily and Over-smoothing Simultaneously (ICLR 2023)
- A Survey of Large Language Models for Graphs (KDD 2024 tutorial/survey)
- Graph Machine Learning in the Era of Large Language Models (LLMs) (2024 survey)
- Towards Graph Foundation Models: A Transferability Perspective (2025)
- Graph Foundation Models: A Comprehensive Survey (2025)
1단계: 2021~2022의 출발점 — “왜 기존 GNN이 잘 안 되나?”
1. On the Bottleneck of Graph Neural Networks and its Practical Implications
이 논문은 최근 5년 GNN 흐름의 출발점에 가깝다. 핵심은 oversquashing이다. 즉, 멀리 떨어진 많은 정보가 좁은 message-passing 경로를 통해 압축되면서 장거리 의존성을 학습하기 어려워진다는 것이다. 이후 long-range, rewiring, graph transformer 논문들이 사실상 이 문제의식 위에서 전개됐다.
2. Understanding Over-squashing and Bottlenecks on Graphs via Curvature
이 논문은 oversquashing을 좀 더 이론적으로 정리한 대표작이다. 병목과 그래프 기하/곡률 관점으로 문제를 해석하면서, “왜 멀리 있는 정보 전달이 구조적으로 막히는가”를 더 정교하게 설명했다. 2022 이후 oversquashing 관련 논문들이 이 계열 이론을 많이 참조한다.
이 시기에 같이 기억할 포인트는, GNN 연구의 초점이 단순히 “새 convolution layer 만들기”가 아니라 message passing 자체의 구조적 한계 진단으로 옮겨갔다는 점이다.
2단계: 2022의 핵심 전환 — “homophily 가정이 깨지면 어떻게 되나?”
3. Revisiting Heterophily for Graph Neural Networks
이 논문은 heterophily를 다룰 때 기존 homophily metric이 충분하지 않다고 지적하고, post-aggregation similarity 관점에서 다시 보자고 제안한다. 최근 heterophily 연구를 읽으려면 거의 필수 배경이다.
4. Understanding Heterophily for Graph Neural Networks
이 논문은 heterophily를 이론적으로 파고든 대표작이다. “이웃이 다르다”는 사실만으로 끝나는 게 아니라, 어떤 형태의 heterophily가 특히 GNN에 어려운가를 구분해 설명하려 한다. 그래서 “heterophily = 무조건 나쁨” 같은 단순화된 이해를 피하는 데 도움이 된다.
5. Is Homophily a Necessity for Graph Neural Networks?
이 논문도 같이 보면 좋다. 제목 그대로, homophily가 정말 GNN의 필요조건인가를 묻는다. heterophily 논문들을 읽을 때 균형을 잡아주는 역할을 한다.
이 시기의 의미는 명확하다.
예전엔 citation/social benchmark에서 GNN이 잘 되니까 “그래프 이웃은 대체로 비슷하다”는 가정이 거의 기본이었는데, 2022 전후부터는 그 가정이 흔들리기 시작했다. 이후 top-tier의 많은 논문이 사실상 heterophily 대응을 전면에 내세우게 된다.
3단계: 2021~2023 — Graph Transformer의 부상
6. Graphormer: Do Transformers Really Perform Badly for Graph Representation?
Graphormer는 “Transformer가 그래프에서 별로다”라는 통념에 정면으로 반박한 대표작이다. 구조적 인코딩을 적절히 넣으면 Transformer도 그래프 표현학습에서 강력할 수 있음을 보여줬다. 최근 Graph Transformer 계열의 출발점으로 보는 경우가 많다.
7. Recipe for a General, Powerful, Scalable Graph Transformer (GraphGPS)
GraphGPS는 최근 그래프 트랜스포머 흐름에서 아주 중요하다. 이 논문은 Graph Transformer를 잘 만들기 위한 recipe를 local message passing + global attention + positional/structural encoding 조합으로 정리한다. 지금도 많은 후속연구가 사실상 이 프레임 위에서 움직인다.
8. Exphormer: Sparse Transformers for Graphs
Graph Transformer의 약점인 계산량/스케일링 문제를 겨냥한 대표 논문이다. sparse attention 구조를 통해 대규모 그래프에도 적용 가능성을 넓혔다. Graph Transformer가 “좋긴 한데 너무 무겁다”는 비판에 대한 중요한 응답이다.
9. Graph Transformers: A Survey
2024년 survey지만, 여기까지 읽고 나서 전체 판을 정리할 때 아주 좋다. Graph Transformer 연구를 encoding, depth, scalability, pretraining 등의 축으로 정리해준다.
이 시기 흐름의 핵심은, GNN이 단순 message passing에 머무르지 않고 global dependency modeling을 위해 Transformer 쪽으로 확장되었다는 점이다. 다만 최근 커뮤니티는 “Transformer가 GNN을 완전히 대체했다”기보다, 둘의 hybrid 설계가 실용적이라고 보는 분위기가 강하다.
4단계: 2023 — 문제를 통합적으로 다루는 방향
10. Ordering Message Passing to Deal with Heterophily and Over-smoothing Simultaneously
이 논문은 heterophily와 oversmoothing을 따로따로가 아니라 동시에 다룬다는 점에서 의미가 있다. 2023년 이후엔 이런 식으로 그래프 학습의 난점들을 분리된 문제로 보기보다, 서로 연결된 현상으로 보는 흐름이 강해졌다.
11. Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey
이건 survey지만 꼭 읽을 가치가 있다. 최근 몇 년간 왜 rewiring이 중요한 아이디어로 떠올랐는지 한 번에 정리해준다. oversquashing/oversmoothing 완화를 위해 아예 그래프 구조를 바꾸는 접근이 얼마나 중요해졌는지를 보여준다.
이 시기의 핵심은, 그래프 학습의 실패 원인을 하나만 탓하지 않는다는 점이다. 최근 top-tier에선 oversmoothing, oversquashing, heterophily, long-range가 서로 얽혀 있다는 인식이 강하다.
5단계: 2024 — “GNN alone”에서 “Graph + LLM”으로
12. A Survey of Large Language Models for Graphs
KDD 2024 축에서 나온 대표 survey다. LLM을 그래프 문제에 쓰는 방식들을 체계적으로 정리한다. 이 시점부터 그래프 학습은 더 이상 순수 GNN만의 문제가 아니라, LLM과 결합된 broader graph learning으로 해석해야 한다.
13. Graph Machine Learning in the Era of Large Language Models (LLMs)
이 survey는 반대 방향도 같이 본다. 즉 LLM이 graph ML을 어떻게 돕는지, 그리고 graph가 LLM을 어떻게 돕는지를 함께 다룬다. few-shot, generalization, reasoning 측면에서 왜 이 결합이 주목받는지 이해하기 좋다.
14. Graph Learning in the Era of LLMs: A Survey from the Perspective of Data, Models, and Tasks
이건 2024 말 기준으로 나온 survey인데, TAG(text-attributed graph), 모델 설계, 태스크 관점에서 더 넓게 정리한다. 최근의 “텍스트가 붙은 그래프”와 산업 응용 흐름을 이해하는 데 유용하다.
이 시점의 변화는 중요하다.
예전엔 “그래프 모델을 어떻게 더 잘 만들까?”가 중심이었다면, 2024 이후부터는 그래프를 텍스트/지식/추론과 어떻게 연결할까가 핵심 질문으로 부상했다. 특히 추천, 과학, QA, reasoning 쪽에서는 이 흐름이 강하다.
6단계: 2025~2026 — Graph Foundation Model과 재평가 국면
15. Towards Graph Foundation Models: A Transferability Perspective
이 논문은 GFM을 transferability 관점에서 정리한다. 최근 GFM 논의의 핵심이 단순히 “큰 모델”이 아니라, 서로 다른 그래프/도메인/태스크로 얼마나 잘 옮겨가느냐라는 점을 잘 보여준다.
16. Graph Foundation Models: A Comprehensive Survey
2025년의 대표 survey다. backbone, pretraining, adaptation을 축으로 GFM을 정리하고, universal / domain-specific / task-specific 구분도 제시한다. 최근 그래프 학습의 무게중심이 foundation-model-style pretraining과 transfer로 이동하고 있음을 보여준다.
17. Re-evaluating the Advancements of Heterophilic Graph Learning
중요한 건, 최근 흐름이 “새로운 SOTA 발표”만이 아니라는 점이다. 이 논문은 heterophily용 모델들이 정말 일반적으로 우수한지 다시 평가한다. 즉, 최근 그래프 학습은 평가 재검증이 매우 중요한 국면에 들어갔다.
18. Unpacking Evaluation Pitfalls on Standard GNN Benchmarks
이 논문은 표준 벤치마크에 class imbalance 같은 문제가 있어, 모델 비교 해석이 흔들릴 수 있다고 지적한다. 최근 탑티어 커뮤니티가 “benchmarks 자체를 믿어도 되나?”를 많이 따지고 있다는 증거다.
19. Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning
이 논문은 그래프 학습 커뮤니티에 퍼져 있는 여러 통념을 비판적으로 다시 본다. 최근 분위기를 가장 잘 보여주는 텍스트 중 하나다. 즉, 이제는 “문제를 하나의 단어로 쉽게 설명하는 시대”를 넘어, 무엇이 정확히 문제인지 구분해서 말해야 하는 시대가 됐다.
20. Can You Hear Me Now? A Benchmark for Long-Range Graph Learning (ECHO)
long-range 문제를 진짜로 요구하는 benchmark가 필요하다는 문제의식에서 나온 최근 작업이다. 핵심은, 기존 벤치마크가 장거리 전파를 충분히 강제하지 않을 수 있다는 점이다. 그래서 “long-range 문제 해결”도 사실 아직 끝난 게 아니라는 걸 보여준다.
네가 읽는 순서 추천
네가 연구 흐름을 빨리 잡고 싶다면 이 순서가 좋다.
A. 근본 문제부터
- On the Bottleneck of GNNs
- Understanding Over-squashing via Curvature
- Revisiting Heterophily
- Understanding Heterophily
B. 아키텍처 확장
- Graphormer
- GraphGPS
- Exphormer
- Graph Transformers: A Survey
C. 최신 판 읽기
- A Survey of LLMs for Graphs
- Graph ML in the Era of LLMs
- Towards Graph Foundation Models
- Graph Foundation Models: A Comprehensive Survey
D. 비판적으로 마무리
- Re-evaluating the Advancements of Heterophilic Graph Learning
- Unpacking Evaluation Pitfalls on Standard GNN Benchmarks
- Demystifying Common Beliefs in Graph ML
- ECHO benchmark
지금 그래프 쪽에서 특히 살아 있는 축은 대략 네 가지다.
1. long-range / heterophily / robustness 같은 근본 한계 문제
아직 미해결이고, 이론과 실험이 둘 다 중요하다.
2. Graph Transformer 및 hybrid architecture
순수 MPNN보다 더 넓은 표현력을 노리되, scalability를 어떻게 확보할지가 핵심이다.
3. LLM + Graph
추천, scientific discovery, graph reasoning에서 특히 강한 최신 흐름이다.
4. Graph Foundation Model / transferability / evaluation reform
앞으로의 “판”은 여기가 될 가능성이 크다. 다만 아직 NLP 비전처럼 완전히 정착한 단계는 아니고, transfer와 benchmark 신뢰성이 큰 과제다.