26년 3월 2주차 그래프 오마카세

Position: Message-passing and spectral GNNs are two sides of the same coin

paper link : https://arxiv.org/abs/2602.10031

• 새로운 GNN 프로젝트를 위한 적절한 아키텍처들을 구축하고자 할 때 자연스럽게 두 가지 표준적인 접근 방식 사이에서 고민하게 됩니다. 바로 MPNN 계열의 메시지 전달 방식과 Spectral 기반 방식입니다.
• 우리는 흔히 이 두 접근을 서로 다른 철학으로 이해해왔습니다. 하나는 그래프의 이산적 국소 구조와 표현력에 초점을 맞추고, 다른 하나는 신호 처리 관점에서의 연속성과 안정성을 강조하는 방식으로 말입니다.
• 이번 주 오마카세에서 소개해드릴 논문은 이런 질문을 독자들에게 던지고 있습니다. "이 두 갈래의 구분이 정말로 우리의 선택지를 넓혀주고 있는 걸까, 혹은 오히려 불필요한 혼란과 고민을 만들어내고 있는 것은 아닐까?"
• 그리고 바로 이 지점에서 꽤 직설적인 답을 제시합니다. MPNN과 Spectral 방식은 서로 다른 패러다임이 아니라, 동일한 연산자를 서로 다른 형태로 표현한 것에 불과하다는 것입니다. 즉, 두 접근법이 경쟁하는 대안이 아니라 사실상 같은 동전의 양면이라는 점을 제목에서부터 분명하게 선언합니다.
• 학계의 오래된 이분법을 깨고 GNN의 진정한 본질을 꿰뚫어 보기 위한 하나로의 통일된 관점을 제안하는 흥미로운 인사이트를 이번 글에서 제공해드리고자 합니다.

• 해당 논문의 저자들은 GNN 연구를 오랫동안 양분해 온 두 패러다임이 실제로는 동일한 수학적 대상, 즉 그래프 신호에 작용하는 Permutation Equivariant 연산자의 서로 다른 방식으로 파라메터화한 것에 불과하다고 주장합니다.
• 이를 설명하기 위한 5가지 핵심 논점들(Positions)을 제시합니다.

(P1) Spectral GNN과 MPNN은 종종 동등하지만, 항상 같지는 않다

• MPNN에서 이웃 노드의 정보를 집계하는 aggregation 과정은 행렬 연산으로 표현될 수 있으며, 이를 GSO(Graph Shift Operator)로 정의할 수 있습니다.
  • GSO는 Spatial 영역의 연산을 Spectral 영역의 필터링으로 연결하는 핵심 매개체로, 많은 Spectral GNN 아키텍처에서 기본적인 연산자로 사용됩니다.
• 정보 집계 (Aggregation) 기반 GSO와 연속적인 주파수 응답을 사용하는 Spectral GNN, 그리고 표준 MPNN은 모두 1-WL과 동등한 separation power를 갖습니다. 특히 Polynomial filter(ChebNet, GCN)를 사용하는 경우 Spectral GNN은 MPNN의 특수한 형태로 해석될 수 있으며, 반대로 MPNN 역시 Polynomial Spectral GNN으로 uniform approximation가 가능합니다.

$$\mathbf{H}^{(l+1)} = \sigma\left( \tilde{\mathbf{D}}^{-\frac{1}{2}} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-\frac{1}{2}} \mathbf{H}^{(l)} \mathbf{W}^{(l)} \right)$$

• MPNN 관점에서 보면, 이 수식에서 $\tilde{\mathbf{A}}$는 이웃 노드 간 정보 전달을 정의하는 연결 구조입니다. 각 노드는 인접 행렬 $\tilde{\mathbf{A}}$를 통해 이웃 노드를 확인하고, 그들의 특징 벡터 $\mathbf{H}$를 수집한 뒤 정규화를 거친 가중 평균 형태의 aggregation을 수행합니다.
• 반면 Spectral 관점에서 $\tilde{\mathbf{A}}$는 그래프 라플라시안($\mathbf{L}$)과 밀접하게 연결된 연산자로 볼 수 있습니다. 이 경우 동일한 연산은 그래프 신호에서 급격한 변화를 억제하고 완만한 변화를 강조하는 low-pass filtering 과정으로 해석됩니다.
• 결국 GCN을 학습한다는 것은 두 가지 관점에서 동일한 의미를 갖습니다. 하나는 이웃으로부터 어느 정도까지 정보를 받아들일지를 결정하는 것이고, 다른 하나는 그래프 신호에서 어떤 주파수 대역을 강조할지를 선택하는 것입니다. 이 논문은 바로 이 지점에서 우리가 사실상 같은 연산을 서로 다른 언어로 설명하고 있었을 뿐이라는 통찰을 제시합니다.
• 다만 이러한 동등성은 항상 성립하는 것은 아닙니다. 만약 GSO의 스펙트럼이 무한히 발산하는 경우 (n개 노드를 갖는 완전연결 그래프의 최대 고유값이 n), Polynomial GNN은 $\sin(\lambda)$와 같은 연속 필터를 근사할 수 없습니다. 이는 논문의 Proposition 18에서 반례로 제시됩니다.
  • 이 결과는 두 접근 방식 사이의 표현력 차이가 단순한 구조적 차이가 아니라 스펙트럼의 유계성(bounded spectrum : 그래프 연산 결과값이 무한히 커지거나 작아지지 않도록 특정 범위안에 가두는 성질. e.g. 정규화 라플라시안 행렬 > [0~2])에 달려 있음을 보여줍니다. 반대로, GSO의 스펙트럼이 공통된 유계 구간에 포함된다면 두 접근법은 서로를 근사할 수 있으며 표현력 측면에서 사실상 동등해집니다(Proposition 19).

(P2) MPNN은 이산 구조 분석과 대규모 배포에 고유한 이점을 가진다.

• 두번째 논점으로부터 MPNN이 업계의 표준으로 자리 잡은 이유가 명확해집니다.
• 이론적으로 MPNN은 WL 테스트와 같은 그래프 동형 판별과 알고리즘 추론에 깊이 뿌리 내리고 있어 모델의 표현력을 수학적으로 보장합니다.
• MPNN의 로컬 업데이트 구조는 그래프 알고리즘 연구와도 밀접하게 연결되어 있습니다. 특히 Neural Algorithmic Reasoning(NAR) 연구에서는 MPNN이 데이터로부터 알고리즘을 학습하고 실행하는 구조를 표현할 수 있음을 보여주었습니다. 이러한 특성 덕분에 전통 알고리즘 영역에 속하던 문제들에도 적용 가능성이 확인되고 있습니다.
• 시스템 관점에서도 MPNN의 구조는 매우 실용적이기 때문에 많은 실제 산업 시스템에서 사용하는 GNN 아키텍처 역시 MPNN 구조를 기반으로 합니다. 대표적으로 LinkedIn의 추천 시스템과 같은 대규모 그래프 학습 환경에서도 이러한 접근이 널리 활용되고 있습니다.

(P3) Spectral GNN은 스무딩·병목·커뮤니티 분석에 고유한 이점을 가진다

• MPNN 대비 Spectral GNN의 장점을 크게 세 가지 관점(오버스무딩, 오버스쿼싱, 커뮤니티 분석)에서 설명합니다
• 깊은 MPNN에서 자주 등장하는 문제 중 하나가 오버스무딩입니다. 레이어가 깊어질수록 노드 표현이 서로 비슷해지는 현상인데, 논문에서는 이를 스펙트럼 수축(spectral contraction) 관점에서 설명합니다.
  • MPNN의 기본 연산은 사실상 low-pass filter로 작동하기 때문에, 반복적인 필터링 과정에서 그래프 신호는 점차 최대 고유값 $\lambda_{max}$에 해당하는 주성분 방향으로 수축하게 됩니다. 그 결과 노드 표현이 점점 균질해지면서 구별력이 사라지게 됩니다.
  • Spectral GNN에서는 이러한 문제를 보다 유연하게 다룰 수 있습니다. 주파수 도메인에서 필터 함수 $g_\theta(\Lambda)$를 직접 설계할 수 있기 때문에, 고주파 성분을 보존하거나 특정 대역만 통과시키는 band-pass 또는 high-pass 필터를 구성할 수 있습니다. 이를 통해 신호의 변별력을 유지하면서 더 깊은 모델을 구성할 수 있습니다.
• MPNN에서 또 다른 중요한 문제로 지적되는 것이 오버스쿼싱입니다. 이는 그래프 상에서 멀리 떨어진 많은 정보가 좁은 경로를 통해 전달되면서 발생하는 정보 병목 현상을 의미합니다.
  • Spectral GNN에서는 그래프 라플라스안의 고유벡터를 전역적인 기저로 사용하여 연산을 수행합니다. 따라서 정보 전달이 단순한 로컬 경로에 의존하지 않고 그래프 전체 구조를 기반으로 이루어지기 때문에, 이러한 병목 구조의 영향을 상대적으로 덜 받게 됩니다.
• Spectral 접근법은 그래프의 커뮤니티 구조를 포착하는 데에도 유리한 특성을 갖습니다. 이는 Spectral Clustering에서 잘 알려진 사실과도 연결됩니다. 그래프 라플라스안의 low-frequency 성분은 그래프의 거시적인 연결 구조와 커뮤니티 패턴을 반영하기 때문입니다.
  • Spectral GNN은 이러한 저주파 성분을 활용함으로써 그래프의 전역적인 구조와 커뮤니티 패턴을 보다 직접적으로 반영하는 표현을 학습할 수 있습니다.

(P4) 안정성·전이성·일반화에서 두 관점은 실질적으로 동등하다

• 안정성 측면을 살펴보면, Spectral GNN은 필터 차수에 따라 안정성이 비교적 선형적으로 예측 가능한 구조를 가집니다. 반면 MPNN은 각 레이어에서 반복되는 비선형 연산 때문에 안정성 경계가 지수적으로 변화하는 것처럼 보이기도 합니다.
• 하지만 논문에서 MPNN에서 비선형 연산의 적용 빈도를 Spectral 방식과 유사하게 조정하면 두 모델의 안정성 지표가 동일한 형태로 수렴한다는 사실을 보이고, 차이는 이론적 본질이 아니라 설계 방식의 차이에 가깝다는 것을 주장합니다.
• 전통적으로 Spectral GNN 이론은 Dense 그래프 분석에 강점이 있고, MPNN 이론은 현실 세계에서 흔히 등장하는 Sparse 그래프 환경에 더 적합하다고 여겨져 왔습니다. 두 그래프 구조의 차이에 대한 이론적 강점에서도 해당 논문에서는 일대일 대응 관계로 연결될 수 있음을 보입니다.
• 마지막으로 일반화 분석에서도 보통 Lipschitz 연속성과 같은 안정 조건이 만족될 경우, Spectral GNN과 MPNN은 유사한 모델 복잡도 경계를 가지며 일반화 성능 측면에서도 큰 차이가 나타나지 않습니다.
• 결국 안정성, 전이성, 일반화라는 세 가지 관점에서 보더라도 두 접근법은 본질적인 구조 차이라기보다 표현 방식의 차이에 가깝다는 것이 주장의 핵심입니다.

(P5) Spectral Positional Encoding은 독립적 설계 축이다

• Spectral Positional Encoding(SPE)는 Spectral GNN의 구성 요소라기보다 그래프에 주어지는 입력 표현 방식의 한 종류로 볼 수 있습니다. 따라서 SPE는 특정 아키텍처에 종속되지 않으며, MPNN과 Spectral GNN 모두에서 동일하게 활용될 수 있습니다.
• 다만 표준적인 고유벡터 기반 Positional Encoding에는 sign ambiguity 또는 eigenspace rotation 문제 등에 취약한 한계점들이 존재하기 때문에 학습 안정성이 영향을 받을 수 있습니다. 최근 연구에서는 이러한 문제를 해결하기 위한 보다 안정적인 SPE 방법들이 제안되고 있습니다. (e.g. Spectral Positional Encoding을 제안하여 고유벡터 기반 표현의 안정성을 개선)
• 최근 이론 연구에서는 메시지 전달 과정 자체가 그래프 구조에 대한 스펙트럼 정보를 점진적으로 구축하는 과정으로 해석될 수 있음을 수학적으로 밝혀가면서 MPNN 모델들 역시 이미 암묵적인 형태의 SPE를 구성하고 있다는 흥미로운 사실을 언급합니다.

• 저자들은 이러한 이론적 통합이 실제 연구로 이어지기 위해, 앞으로 학계가 집중해야 할 몇 가지 구체적인 과제를 제안합니다.
  • 먼저 공통 용어 체계의 구축입니다. 현재 MPNN과 Spectral GNN 커뮤니티는 동일한 개념을 서로 다른 언어로 설명하는 경우가 많습니다. 저자들은 GSO, 기저, Positional Encoding과 같은 핵심 요소를 중심으로, 두 접근법이 사용하는 가정과 연산을 직접 비교할 수 있는 연산자 중심의 공통 용어 체계가 필요하다고 강조합니다.
  • 두 번째는 제어된 GSO 기반 벤치마크의 구축입니다. 현재 많은 벤치마크는 단순한 성능 비교에 집중되어 있지만, 저자들은 oversmoothing, oversquashing, 커뮤니티 탐지, 방향성 그래프 처리, 링크 예측과 같은 특정 현상을 독립적으로 분석할 수 있는 테스트 환경이 필요하다고 주장합니다. 이러한 벤치마크를 통해 두 접근법이 실제로 어떤 조건에서 강점을 보이는지 보다 명확하게 확인할 수 있을 것입니다.
  • 세 번째는 하이브리드 아키텍처에 대한 체계적인 탐색입니다. 예를 들어 스펙트럼 필터와 MPNN 업데이트를 결합하거나, 학습 가능한 GSO를 도입하거나, MPNN 내부에 스펙트럼 기반 Positional Encoding을 통합하는 방식 등이 가능합니다. 저자들은 이러한 혼합 설계가 두 패러다임의 장점을 동시에 활용하는 중요한 연구 방향이 될 것이라고 전망합니다.
  • 마지막으로 진정한 스펙트럼 이론의 발전입니다. 지금까지 많은 연구에서는 Spectral 모델을 Polynomial 필터나 MPNN의 특수한 형태로 환원해 설명하는 경향이 있었습니다. 그러나 저자들은 이를 넘어 Functional Analysis에 기반한 보다 독자적인 스펙트럼 분석 이론을 발전시켜야 한다고 주장합니다. 이러한 이론은 기존 MPNN 관점과 충돌하기보다는, 공통된 언어 안에서 서로 보완적인 역할을 할 수 있는 새로운 이론적 기반이 될 수 있습니다.
• 결론적으로 이 논문의 저자들이 저와 여러분들에게 던지는 핵심 메시지는 한 문장으로 정리 가능합니다.

• 그렇다면 저희들이 던져볼 질문들은 (자연스레) 기존의 "어떤 아키텍처의 방향성으로 선택할 것인가?" 가 아닌, "그래프 위에서 어떤 연산자(GSO)를 정의하고, 그 위에서 어떤 함수를 학습시킬 것인가?" 으로 귀결됨을 보여줍니다.
• 이러한 관점에서 보면 다양한 그래프 모델들도 하나의 연산 공간 위에서 다시 해석할 수 있습니다.
  예를 들어 Graph Diffusion이나 Wavelet 기반 모델들은 GSO의 지수 함수 형태로 표현되는 연산으로 이해할 수 있으며, Graph Transformer 역시 모든 노드가 서로 연결된 완전 그래프 형태의 GSO 위에서 작동하는 특수한 메시지 전달 모델로 볼 수 있습니다. 또한 최근 연구되고 있는 Sheaf Neural Networks 역시 행렬 형태의 GSO를 통해 노드 간 더 복잡한 관계를 표현하는 확장된 연산 구조로 해석할 수 있습니다.
• 이처럼 다양한 모델을 동일한 연산자 관점에서 바라볼 수 있게 되면, 앞으로 등장할 새로운 GNN 아키텍처 역시 어떤 GSO를 정의하고 그 위에서 어떤 함수를 학습시키는가라는 방향에서 이해할 수 있을 것입니다. 이러한 관점이 앞으로의 GNN 연구 흐름과 새로운 트렌드를 바라보는 하나의 흥미로운 출발점이 되기를 기대해봅니다.

[Contact Info]

Gmail: jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn