혼합 그래프 알고리즘 전개를 통한 경량 및 해석 가능한 Transformer 기반 교통 예측

기본 정보

• 논문 ID: 2505.13102
• 제목: Lightweight and Interpretable Transformer via Mixed Graph Algorithm Unrolling for Traffic Forecast
• 저자: Ji Qi, Mingxiao Liu, Tam Thuc Do, Yuzhe Li, Zhuoshi Pan, Gene Cheung, H. Vicky Zhao
• 분류: cs.LG cs.AI eess.SP
• 발표 시간: 2025년 10월 12일 (arXiv v2)
• 논문 링크: https://arxiv.org/abs/2505.13102

초록

본 논문은 혼합 그래프 알고리즘 전개에 기반한 경량 해석 가능 Transformer 모델을 교통 예측에 제안한다. 기존의 "블랙박스" Transformer와 달리, 본 방법은 혼합 그래프 최적화 알고리즘을 전개하여 해석 가능한 Transformer 유사 신경망을 구축한다. 모델은 두 개의 그래프를 구성한다: 무향 그래프 $\mathcal{G}^u$는 지리공간 상관성을 포착하고, 유향 그래프 $\mathcal{G}^d$는 시간 관계를 포착한다. 새로운 $\ell_2$ 및 $\ell_1$ 노름 변분 항을 설계하여 유향 그래프 상의 신호 평활성을 정량화하고 촉진하며, 교대 방향 승수법(ADMM)에 기반하여 반복 알고리즘을 설계하고 이를 데이터 기반 매개변수 학습을 위한 피드포워드 네트워크로 전개한다. 실험 결과는 본 모델이 경쟁력 있는 교통 예측 성능을 유지하면서 매개변수 수를 대폭 감소시킴을 보여준다.

연구 배경 및 동기

문제 정의

교통 예측은 다음을 동시에 포착해야 하는 중요한 시공간 데이터 모델링 문제이다:

1. 공간 상관성: 지리적으로 인접한 모니터링 지점 간의 상관성
2. 시간 의존성: 과거 관측이 미래에 미치는 영향 관계

기존 방법의 한계

1. 기존 Transformer: 매개변수 수가 방대하고 해석 가능성이 부족하며, 실제 배포에서 계산 및 메모리 제약에 직면
2. 모델 기반 방법: 공간과 시간 차원을 독립적으로 처리하는 경향이 있어 시공간 관계를 충분히 활용하지 못함
3. 기존 심층 학습 방법: 우수한 성능에도 불구하고 여전히 "블랙박스" 모델이며 매개변수 수가 많음

연구 동기

1. 산업 응용에서 경량 모델에 대한 절실한 필요성
2. 알고리즘 전개(Algorithm Unrolling)가 모델 기반과 데이터 기반을 결합한 새로운 패러다임 제공
3. 기존 작업은 양의 무향 그래프만 사용하여 복잡한 시공간 관계를 효과적으로 모델링하지 못함

핵심 기여

1. 혼합 그래프 알고리즘 전개 최초 제안: 무향 그래프(공간)와 유향 그래프(시간)를 결합하여 복잡한 시공간 관계 모델링
2. 혁신적인 유향 그래프 정규화 항: 유향 그래프 라플라시안 정규화기(DGLR)와 유향 그래프 전변분(DGTV) 설계
3. 경량 해석 가능 Transformer: ADMM 알고리즘 전개를 통해 매개변수를 대폭 감소(PDFormer의 6.4%만 사용)
4. 이론적 기여: 무가중 유향 선 그래프의 경우 유향 그래프 주파수 정의가 고전 푸리에 주파수로 축퇴됨을 증명

방법 상세 설명

작업 정의

N개의 모니터링 지점에서 과거 T+1개 시점의 관측값이 주어졌을 때, 미래 S개 시점의 교통 상태를 예측한다. 입력은 부분 관측된 시공간 신호 $y \in \mathbb{R}^M$이고, 출력은 완전한 시공간 신호 $x \in \mathbb{R}^{N(T+S+1)}$이다.

혼합 그래프 구성

무향 그래프 $\mathcal{G}^u$

• 동일 시점의 지리적으로 인접한 노드를 연결
• 공간 상관성 포착
• 대칭 인접 행렬 $W^u$ 사용

유향 그래프 $\mathcal{G}^d$

• 시점 $\tau$의 노드에서 $\tau+1, ..., \tau+W$ 시점의 동일 노드로 연결
• 시간 인과 관계 포착
• 비대칭 인접 행렬 $W^d$ 사용

유향 그래프 변분 항 설계

$\ell_2$ 노름 항: 유향 그래프 라플라시안 정규화기(DGLR)

$x^T\mathcal{L}_r^d x = x^T(L_r^d)^T L_r^d x = \|x - W_r^d x\|_2^2$

여기서 $L_r^d = I - W_r^d$는 행 확률 라플라시안 행렬이고, $W_r^d = (D^d)^{-1}W^d$는 행 확률 인접 행렬이다.

$\ell_1$ 노름 항: 유향 그래프 전변분(DGTV)

$\|L_r^d x\|_1 = \sum_{j \in \bar{S}} |x_j - \sum_i w_{j,i} x_i|$

최적화 목적 함수

$\min_x \|y - Hx\|_2^2 + \mu_u x^T L^u x + \mu_{d,2} x^T \mathcal{L}_r^d x + \mu_{d,1} \|L_r^d x\|_1$

여기서 $H$는 샘플링 행렬이고, $\mu_u, \mu_{d,2}, \mu_{d,1}$은 가중치 매개변수이다.

ADMM 알고리즘 설계

보조 변수 $\phi$를 도입하여 최적화 문제를 다음과 같이 변환한다: $\min_{x,\phi} \|y - Hx\|_2^2 + \mu_u x^T L^u x + \mu_{d,2} x^T \mathcal{L}_r^d x + \mu_{d,1} \|\phi\|_1$$\text{s.t. } \phi = L_r^d x$

부분 문제 해결

1. $x$ 부분 문제: 켤레 기울기법을 통한 선형 시스템 해결
2. $\phi$ 부분 문제: 소프트 임계값 연산 $\phi_i^{\tau+1} = \text{sign}(\delta) \cdot \max(|\delta| - \rho^{-1}\mu_{d,1}, 0)$ 여기서 $\delta = (L_r^d)_i x^{\tau+1} - \rho^{-1}\gamma_i^\tau$

그래프 학습 모듈

무향 그래프 학습(UGL)

마할라노비스 거리를 사용하여 노드 유사성 계산: $d^u(i,j) = (f_i^u - f_j^u)^T M (f_i^u - f_j^u)$

간선 가중치는 정규화된 지수 함수를 통해 계산: $w_{i,j}^u = \frac{\exp(-d^u(i,j))}{\sqrt{\sum_{l \in \mathcal{N}_i} \exp(-d^u(i,l))} \sqrt{\sum_{k \in \mathcal{N}_j} \exp(-d^u(k,j))}}$

유향 그래프 학습(DGL)

유사하게 메트릭 행렬 $P$를 사용하여 유향 간선 가중치 계산.

네트워크 아키텍처

ADMM의 각 반복을 신경층으로 구현:

• 5개 ADMM 블록, 각 블록 25층
• 각 블록 앞에 그래프 학습 모듈 삽입
• 다중 헤드 주의 메커니즘 사용(4개 병렬 그래프 학습 모듈)

실험 설정

데이터셋

• METR-LA: 로스앤젤레스 교통 속도 데이터, 207개 노드, 1315개 간선
• PEMS03: 교통 흐름 데이터, 358개 노드, 547개 간선
• 샘플링 간격: 5분
• 데이터 분할: 6:2:2(훈련:검증:테스트)

평가 지표

• RMSE: 평균 제곱근 오차
• MAE: 평균 절대 오차
• MAPE: 평균 절대 백분율 오차

비교 방법

6가지 기준선 방법 포함:

• 모델 기반: VAR
• GNN 방법: STGCN, STSGCN
• GAT 방법: GMAN, ST-Wave
• Transformer 방법: PDFormer, STAEformer
• 적응형 그래프 방법: Graph WaveNet, AGCRN
• 단순 선형 모델: STID, SimpleTM

구현 세부사항

• 예측 기간: 30/60/120분(6/12/24 단계)
• 과거 윈도우: 60분(12 단계)
• 최적화기: Adam, 학습률 5×10⁻⁴
• 손실 함수: Huber 손실(δ=1)
• 하드웨어: NVIDIA GeForce RTX 3090

실험 결과

주요 결과

주요 발견

1. 매개변수 효율성: PDFormer의 6.4%만의 매개변수로 경쟁력 있는 성능 달성
2. 장기 예측 우위: 예측 기간이 길수록 최고 방법과의 성능 차이 감소
3. 데이터 효율성: 데이터 부족 상황에서 더 안정적인 성능

절제 실험

결과는 다음을 보여준다:

• DGLR 항이 성능 향상에 가장 중요
• DGTV 항도 명확한 기여
• 유향 그래프 모델링이 무향 그래프 모델링보다 우수

이론적 검증

정리 3.1은 다음을 증명한다: 무가중 유향 선 그래프의 경우, 대칭화된 유향 그래프 라플라시안 $\mathcal{L}_r^d = (L_r^d)^T L_r^d$은 무향 선 그래프의 라플라시안 행렬과 동등하며, 주파수 정의의 타당성을 검증한다.

관련 연구

경량 모델

• 대규모 언어 모델: LoRA 저순위 적응, 매개변수 양자화
• 음성 강화: 국소 인과 자기 주의
• 이미지 처리: YUV 채널 분리 처리

교통 예측 방법

1. GNN 방법: STGCN, Graph WaveNet 등, 공간 모델링에 집중
2. Transformer 방법: 이중 Transformer가 시공간 차원을 각각 처리
3. 단순 선형 모델: 복잡한 모델의 효과성에 도전

알고리즘 전개

• 최적화 알고리즘 반복을 신경층으로 전개
• 수학적 해석 가능성과 데이터 기반 능력을 모두 갖춤
• 이미지 처리에서 성공적인 응용

결론 및 논의

주요 결론

1. 혼합 그래프 알고리즘 전개가 경량 해석 가능한 교통 예측 모델을 성공적으로 구현
2. 유향 그래프 변분 항이 시간 인과 관계를 효과적으로 포착
3. 매개변수 수를 대폭 감소시키면서 경쟁력 있는 성능 유지

한계

1. 거리 제약: 학습된 마할라노비스 거리는 음이 아닌 반면, 기존 자기 주의는 음수일 수 있음
2. 그래프 희소성: 실제 도로 연결에 기반한 제약이 그래프 연결성 제한
3. 고정 시간 윈도우: 미리 정의된 시간 윈도우가 충분히 유연하지 않을 수 있음

향후 방향

1. 부호 있는 거리 및 더 복잡한 그래프 모델링으로 확장
2. 적응형 시간 윈도우 학습
3. 다른 시공간 예측 작업으로의 응용

심층 평가

장점

1. 이론적 혁신: 유향 그래프에 대한 주파수 개념을 최초로 정의하고 해당 정규화 항 설계
2. 방법 참신성: 혼합 그래프 알고리즘 전개가 Transformer 설계에 새로운 관점 제공
3. 실용적 가치: 현저한 매개변수 감소가 실제 배포에 중요한 의미
4. 해석 가능성: 각 층이 최적화 알고리즘 반복에 대응하여 명확한 수학적 의미 보유

부족한 점

1. 성능 트레이드오프: 일부 지표에서 여전히 최고 기준선 방법에 미치지 못함
2. 적용 범위: 주로 교통 예측에서 검증되었으며 다른 시공간 작업으로의 일반화 가능성 미지수
3. 이론적 분석: 수렴성 및 복잡도에 대한 이론적 분석 부족

영향력

1. 학술 기여: 그래프 신호 처리 및 Transformer 설계에 새로운 관점 제공
2. 실용적 가치: 경량 특성이 모바일 기기 및 리소스 제약 환경에 적합
3. 재현성: 오픈소스 코드 제공, 실험 설정 상세 기술

적용 시나리오

1. 리소스 제약 환경: 모바일 기기, 엣지 컴퓨팅
2. 실시간 예측 시스템: 빠른 응답이 필요한 교통 관리 시스템
3. 해석 가능 AI 응용: 모델 투명성이 필요한 안전 관련 시스템

참고문헌

논문은 다음을 포함한 여러 중요 작업을 인용한다:

• Transformer 원본 논문 (Vaswani et al., 2017)
• 알고리즘 전개 종설 (Monga et al., 2021)
• 그래프 신호 처리 기초 (Ortega et al., 2018)
• 교통 예측 관련 작업 (Li et al., 2017; Yu et al., 2018)

종합 평가: 이는 교통 예측 분야에서 혁신적인 작업으로, 알고리즘 전개 개념을 혼합 그래프 설정으로 성공적으로 확장하여 성능을 유지하면서 매개변수 수를 대폭 감소시켰다. 일부 지표에서 개선의 여지가 있지만, 경량성과 해석 가능성의 특징이 중요한 실용적 가치와 학술적 의의를 부여한다.