CTQWformer: A CTQW-based Transformer for Graph Classification

본 논문은 기존 GNN 및 그래프 커널 방법보다 그래프 분류 작업에서 우수한 성능을 달성하기 위해 전역 구조적 의존성과 동적 정보 전파를 모두 포착할 수 있도록 연속 시간 양자 보행과 트랜스포머 아키텍처를 통합한 새로운 하이브리드 프레임워크인 CTQWformer를 제안합니다.

핵심

복잡한 도시를 이해하려고 한다고 상상해 보세요. 당신은 거리들이 어떻게 연결되어 있는지 보여주는 지도(그래프 구조)와 모든 건물에 대한 설명 목록(노드 특징)을 가지고 있습니다.

전통적인 컴퓨터 프로그램(GNN이라고 함)은 한 건물에서 바로 옆 이웃으로 메신저를 보내 "무엇이 보이나요?"라고 물어보며 이 도시를 이해하려고 시도합니다. 그들은 이 메시지를 계속 전달합니다. 그러나 이 방법에는 두 가지 큰 문제가 있습니다:

1. 너무 국소적입니다: 메신저는 몇 블록만 지나면 지쳐서 도시 반대편에서 무슨 일이 일어나고 있는지 잊어버립니다(장거리 연결 누락).
2. 너무 정적입니다: 도시가 시간 흐름에 따라 어떻게 변하거나 흐를 수 있는지 무시한 채 도시를 고정된 스냅샷으로 취급합니다.

CTQWformer 등장: 양자 물리학, AI 채팅봇 뒤의 기술인 트랜스포머, 그리고 시간 여행이라는 세 가지 세계의 장점을 결합한 이러한 "도시"(그래프) 를 분석하는 새롭고 초지능적인 방법입니다.

다음은 이를 간단한 부분으로 나누어 설명한 작동 원리입니다:

1. "양자 워커"(물리학 부분)

한 번에 한 블록씩 걷는 지친 메신저 대신, 양자 워커를 상상해 보세요.

• 마법: 양자 세계에서는 입자가 한 거리만 걷는 것이 아니라, 중첩을 통해 한 번에 여러 곳에 있을 수 있고, 연못의 물결처럼 자기 자신과 간섭할 수 있습니다.
• 혁신: 일반적으로 이 "양자 워커"는 고정되고 경직된 규칙입니다. 하지만 CTQWformer는 거리 배치 와 지나가는 건물의 유형 모두에 기반하여 워커의 경로를 조정하도록 학습하는 맞춤형 학습 가능 가이드(해밀토니안이라고 함) 를 구축합니다.
• 결과: 이 워커는 도시 전체를 즉시 탐험하여 일반 워커가 놓칠 복잡한 패턴과 연결을 포착합니다. 이는 워커가 시간에 따라 도시를 이동하는 방식을 보여주는 "영화"를 생성합니다.

2. 두 개의 전문 팀

양자 워커가 영화를 마친 후, CTQWformer는 데이터를 분석하기 위해 두 팀으로 나눕니다:

• 팀 A: "스냅샷" 분석가 (트랜스포머)

  • 하는 일: 양자 워커 영화의 마지막 프레임을 봅니다.
  • 비유: 10 초 후 워커가 도착한 장면을 찍은 사진을 찍는다고 상상해 보세요. 이 사진은 도시 구조의 "큰 그림"을 보여줍니다.
  • 도움 방법: 이 사진을 AI 두뇌인 트랜스포머에 입력합니다. AI 에게 "이 특정 건물들에 특히 주의를 기울이세요. 양자 물리학이 강력하게 연결되어 있다고 말하고 있습니다"라고 알려줍니다. 이를 통해 AI 가 그래프의 전체적인 모양을 이해하는 데 도움이 됩니다.

• 팀 B: "영화" 분석가 (순환 신경망)

  • 하는 일: 워커가 1 초에서 10 초까지 움직이는 전체 영화를 봅니다.
  • 비유: 팀 A 가 마지막 사진을 보는 동안, 팀 B 는 그 춤을 봅니다. 워커가 어떻게 진동하고, 왕복하며, 흐르는지 봅니다.
  • 도움 방법: 시퀀스에 좋은 AI 인 순환 신경망을 사용하여 도시의 리듬과 템포를 학습합니다. 이는 정적 사진으로는 보여줄 수 없는 정보의 흐름과 시간에 따른 변화를 포착합니다.

3. 그랜드 파이널 (융합)

마지막으로, 모델은 "스냅샷 분석가"(구조) 와 "영화 분석가"(시간 기반 흐름) 의 통찰력을 가져와 융합시킵니다.

• 이해의 탑을 쌓는 것처럼 이러한 레이어들을 서로 위에 쌓아 올립니다.
• 맨 꼭대기에서는 모든 학습된 정보의 "평균"을 취하여 전체 그래프에 단일 레이블을 부여합니다(예: "이 그래프는 단백질이다" 또는 "이 그래프는 소셜 네트워크이다").

이것이 왜 중요한가요?

이 논문은 양자 물리학(복잡하고 전역적인 연결을 처리하는 데 본질적으로 뛰어남) 과 딥러닝(데이터에서 학습하는 데 뛰어남) 을 혼합함으로써 CTQWformer 가 기존 방법들을 능가한다고 주장합니다.

• 기존 방법은 확대경을 들고 지도를 보거나(너무 국소적), 정적 사진을 보는 것과 같습니다(시간 없음).
• CTQWformer는 한 번에 모든 곳을 날아다닐 수 있는 드론(전역적) 을 가지고, 3D 로 도시를 보고(구조), 교통 흐름의 고화질 고속 비디오를 기록하며(동역학), 특정 작업에 가장 중요한 경로를 정확히 학습하는 것과 같습니다.

핵심 요약:
저자들은 화학 분자 및 소셜 네트워크와 같은 표준 데이터셋에서 이를 테스트한 결과, 그들의 "양자 - 트랜스포머" 하이브리드가 이전 방법들보다 이러한 그래프를 분류하는 데 더 뛰어났음을 발견했습니다. 이는 AI 에 약간의 "양자 동역학"을 추가하면 동시에 숲과 나무를 모두 볼 수 있게 해준다는 것을 증명합니다.

기술 요약

기술 요약: CTQWformer

문제 제기

그래프 신경망 (GNN) 과 Transformer 기반 아키텍처는 그래프 학습을 발전시켰지만 특정 한계에 직면해 있습니다. 전통적인 GNN 은 종종 국소 수용 영역의 어려움, 깊은 네트워크에서의 과평활화 (over-smoothing), 그리고 장기 의존성 포착의 부재로 고생합니다. 반면, Transformer 는 장기 의존성 모델링에 뛰어나지만 국소 및 전역 구조적 의존성을 동시에 효과적으로 포착하는 데는 종종 실패합니다. 더 나아가 기존 방법들은 그래프 구조에 내재된 동적 정보 전파를 모델링할 물리적으로 근거 있는 메커니즘이 부족할 수 있습니다. 본 논문은 전역 어텐션을 활용하면서도 국소 구조 정보를 보존하고 동적 진화 패턴을 모델링할 수 있는 프레임워크의 필요성을 지적합니다.

방법론

저자들은 연속 시간 양자 보행 (Continuous-Time Quantum Walks, CTQW) 과 GNN 을 통합한 하이브리드 그래프 학습 프레임워크인 CTQWformer를 제안합니다. 이 모델은 그래프 수준 표현 학습을 위해 CTQW 의 정적 물리 구조 편향과 동적 시간적 진화 패턴을 모두 포착하도록 설계되었습니다. 아키텍처는 세 가지 핵심 구성 요소로 이루어져 있습니다:

1. 양자 보행 인코더 (QWE)

고정된 라플라시안 또는 인접 행렬에 의존하는 고전적 CTQW 모델과 달리, CTQWformer 는 학습 가능한 해밀토니안($H_\theta$) 을 사용합니다.

• 구성: 해밀토니안은 그래프 토폴로지와 노드 특징을 융합합니다. 엣지 가중치는 인접 노드 특징을 연결 (concatenating) 하고 ReLU 및 Sigmoid 활성화 함수를 가진 다층 퍼셉트론 (MLP) 을 통과시켜 가중치가 유계 (bounded) 되도록 보장함으로써 학습됩니다.
• 동역학: 시스템은 슈뢰딩거 방정식 ($i \frac{d}{dt}|\psi(t)\rangle = H|\psi(t)\rangle$) 에 따라 진화합니다. 이 모델은 단일 노드 초기 상태인 직교 기저 상태에서 시작하여 이산 시간 단계 $T$에 걸쳐 CTQW 의 진화를 시뮬레이션합니다.
• 출력: 이 과정은 각 시간 단계에서 그래프 전체에 걸친 보행자의 확률 분포를 인코딩하는 시간적 진화 텐서 $P \in \mathbb{R}^{T \times n \times n}$를 생성합니다.

2. 양자 보행 - 그래프 Transformer (QWGT) 모듈

이 모듈은 전역 구조 인식의 필요성을 해결합니다.

• 메커니즘: CTQW 시뮬레이션으로부터의 최종 시간 전파 확률($P^T$) 을 정적 구조 편향으로 포함시켜 그래프 Transformer 의 자기 어텐션 메커니즘에 통합합니다.
• 통합: 편향 행렬 $B$는 $P^T$를 정규화하고 로그 변환 ($B = \log(1 + P^T)$) 을 적용하여 유도되며, 이는 어텐션 점수 행렬 ($QK^T/\sqrt{d} + B$) 에 추가됩니다. 이는 어텐션 메커니즘이 단순한 특징 유사성을 넘어 근본적인 그래프 토폴로지와 물리 구조적 속성을 존중하도록 안내합니다.

3. 양자 보행 - 그래프 순환 (QWGR) 모듈

이 모듈은 양자 보행의 동적 시간적 진화를 포착합니다.

• 메커니즘: CTQW 진화 텐서의 전체 시간 시퀀스를 처리합니다. 구체적으로, 시간 단계에 걸친 확률 행렬에서 대각선 요소 (노드별 자기 전파 확률) 를 추출합니다.
• 아키텍처: 이러한 시퀀스는 순방향 및 역방향 모두에서 시간적 변동과 의존성을 모델링하기 위해 **양방향 게이트 순환 유닛 (BiGRU)**에 입력됩니다.
• 출력: 생성된 노드 표현은 평균 풀링과 순방향 네트워크를 통해 집계되어 그래프 수준의 임베딩을 생성합니다.

융합 및 예측

QWGT 와 QWGR 모듈은 통합된 레이어에 통합됩니다. 이들의 출력은 연결된 후 순방향 융합 네트워크를 통과합니다. 이 모델은 다중 레이어 스택을 지원하며, 여기서 그래프 수준 임베딩은 노드 수준 표현으로 브로드캐스트되어 후속 레이어를 안내합니다. 마지막으로, 전역 평균 풀링은 최종 노드 임베딩을 집계하여 그래프 수준 분류를 수행합니다.

주요 기여

1. 학습 가능한 해밀토니안: 그래프 구조와 노드 특징을 모두 통합하는 매개변수화 된 해밀토니안 설계. 이를 통해 CTQW 동역학이 노드 특징에 기반하여 연결을 적응적으로 포착할 수 있게 되어, 속성 그래프 분류 작업에 적합한 모델이 됩니다.
2. 하이브리드 프레임워크 (CTQWformer): 최초의 하이브리드 CTQW 기반 Transformer 제안. 이는 다음과 같이 독특하게 결합합니다:
   • 정적 편향: Transformer 의 어텐션 메커니즘을 안내하기 위해 최종 시간 CTQW 확률 사용.
   • 동적 모델링: CTQW 의 시간적 진화를 처리하기 위해 양방향 순환 네트워크 사용.
     이 통합을 통해 모델은 정적 물리 구조 편향과 동적 시간적 진화 패턴을 모두 포착할 수 있습니다.
3. 성능: 광범위한 실험을 통해 이 프레임워크가 여러 벤치마크 데이터셋에서 전통적인 그래프 커널 및 다양한 GNN 기반 방법 (Graphormer 및 GraphGPS 포함) 보다 우수한 성능을 보임을 입증했습니다.

실험 결과

이 모델은 생정보학 및 소셜 네트워크를 아우르는 TU 컬렉션의 6 개 벤치마크 데이터셋 (MUTAG, PTC(MR), PROTEINS, DD, IMDB-B, IMDB-M) 에서 평가되었습니다.

• 그래프 커널과의 비교: CTQWformer 는 고전적 R-컨볼루션 커널과 CTQW 기반 정보 이론 커널 (예: JTQK, QJSK) 을 포함한 7 개 그래프 커널 방법과 일관되게 비교하여 6 개 데이터셋 중 5 개에서 최상의 성능을 달성했습니다.
• GNN 과의 비교: 이 모델은 8 개의 대표적인 GNN (예: GIN, GCN, GraphSAGE) 과 3 개의 최첨단 그래프 Transformer(Graphormer, GraphGPS, GRIT) 에 대해 경쟁력 있거나 우수한 결과를 달성했습니다.
• 애블레이션 연구: QWGR 모듈 (시간적 모델링) 을 제거하면 성능이 크게 저하되었습니다 (예: MUTAG 정확도가 92.54% 에서 74.97% 로 하락). 이는 동적 진화 모델링의 결정적 중요성을 강조합니다. QWGT 모듈 (구조 편향) 을 제거하면 작지만 눈에 띄는 감소가 발생하여 두 구성 요소 모두 가치가 있음을 나타냈습니다.
• 하이퍼파라미터 민감도: 연구에 따르면 적절한 시간 단계 (예: MUTAG 의 경우 $T=4$) 와 네트워크 깊이 (예: $L=2$) 가 최적의 성능을 제공했으며, 과도한 진화 시간이나 네트워크 깊이는 정보 희석이나 과평활화로 이어질 수 있음을 시사했습니다.

중요성 및 주장

본 논문은 CTQWformer 가 양자 동역학을 학습 가능한 딥러닝 프레임워크에 성공적으로 통합함으로써 중요한 발전을 이루었다고 주장합니다.

• 물리적 근거: 슈뢰딩거 방정식을 통한 그래프 구조의 물리적으로 근거 있는 모델링을 제공하며, 양자 보행에 내재된 구성적 및 파괴적 간섭 효과를 통해 정교한 구조 정보를 포착합니다.
• 상호 보완적 모델링: 정적 구조 편향과 동적 시간적 진화를 융합함으로써 국소 집계나 정적 어텐션에만 의존하는 모델의 한계를 극복합니다.
• 유일무이한 첫 사례: 저자들은 알고 있는 한, CTQW 에서 유도된 구조 편향과 시간적 진화 모델링을 통합하여 그래프 학습을 발전시키는 최초의 하이브리드 CTQW 기반 Transformer 라고 명시합니다.

저자들은 이 작업이 그래프 표현 학습을 위한 양자 보행 동역학의 잠재력을 입증했으며, 향후 연구는 계산 효율성 향상과 프레임워크를 더 넓은 그래프 학습 작업으로 확장하는 데 초점을 맞출 것이라고 결론지었습니다.