Graph Distribution-valued Signals: A Wasserstein Space Perspective

논문 요약: 그래프 분포 값 신호 (GDS) 와 Wasserstein 공간의 관점

1. 문제 정의 (Problem)

기존의 그래프 신호 처리 (Graph Signal Processing, GSP) 는 그래프 신호를 노드 값의 벡터로 모델링합니다. 그러나 이 벡터 기반 접근법은 다음과 같은 두 가지 주요 한계를 가집니다.

• 완전한 관측 가정 (Complete Observation Assumption): 모든 노드의 신호가 동시에 관측되어야 한다는 전제가 필요합니다. 실제 응용 (예: 센서 네트워크, 사회 네트워크) 에서는 데이터 수집이 비동기적이거나 일부 노드에서 누락되는 경우가 많아 이 가정이 비현실적입니다.
• 엄격한 대응 관계 요구 (Strict Correspondence Requirement): 기존 통계적 GSP 방법들도 확률 변수를 도입하지만, 그래프 필터는 여전히 벡터에서 벡터로의 매핑으로 정의됩니다. 이는 예측 작업에서 입력 신호와 출력 신호가 1:1 로 엄격하게 정렬 (alignment) 되어야 함을 의미합니다. 실제 데이터의 시프트, 중첩, 주기적 패턴, 또는 결측 데이터로 인해 이러한 정렬이 깨지면 성능이 급격히 저하됩니다.

이러한 한계를 극복하기 위해, 저자들은 신호를 단순한 확률 벡터나 샘플이 아닌, Wasserstein 공간에 있는 확률 분포 (Probability Distribution) 자체로 모델링하는 새로운 프레임워크를 제안합니다.

2. 방법론 (Methodology)

가. 그래프 분포 값 신호 (GDS) 프레임워크

• 정의: 그래프 신호를 $N$차원 유클리드 공간 ($\mathbb{R}^N$) 상의 보렐 확률 측도 (Borel probability measure) 인 Wasserstein 공간 ($\mathcal{P}_p(\mathbb{R}^N)$) 의 원소로 정의합니다. 이를 Graph Distribution-valued Signal (GDS) 이라고 부릅니다.
• Wasserstein 거리: 두 분포 간의 거리를 측정하기 위해 Wasserstein 거리 ($W_p$) 를 사용합니다. 이는 한 분포를 다른 분포로 운반하는 데 필요한 최소한의 '일 (work)'을 의미하며, 분포의 평균뿐만 아니라 공분산 (변동성 및 의존성) 을 모두 고려합니다.
• 일반화: 기존 GSP 의 벡터 신호는 디랙 측도 (Dirac measure, $\delta_x$) 로 간주될 수 있으므로, GDS 프레임워크는 기존 GSP 를 특수한 경우로 포함하는 엄밀한 일반화 (strict generalization) 입니다.

나. GDS 를 위한 신호 처리 도구

• GDS 푸리에 변환 (GDS-FT): 그래프 이동 연산자 (GSO) 의 고유벡터 행렬 $U_G$를 사용하여 분포를 정점 도메인에서 주파수 도메인으로 푸시포워드 (pushforward) 합니다.
  • $\hat{\mu} := (U_G^\top)_{\#} \mu$
• GDS 컨볼루션 필터링: 그래프 필터 $F_G$ (GSO 의 다항식) 를 분포 전체에 적용하여 분포의 통계적 특성 (평균, 공분산 등) 이 그래프를 통해 어떻게 전파되는지 모델링합니다.
  • $F_G(\mu) = (F_G)_{\#} \mu$
  • 만약 $\mu$가 가우시안 분포라면, 필터링 후에도 가우시안 분포를 유지하며 평균과 공분산이 선형 변환됩니다.

다. 그래프 필터 학습 (GDS-Cop)

• 목표: 입력 분포 $\mu$를 필터링하여 목표 분포 $\mu^\star$와 Wasserstein 공간에서 거리가 최소가 되도록 필터 $F_G$를 학습합니다.
• Copula 기반 접근: 모든 노드의 결합 분포를 직접 추정하는 것은 고차원에서 어렵기 때문에, Sklar 의 정리를 활용합니다. 각 노드의 주변 분포 (Marginal distribution) 와 노드 간 의존성을 나타내는 Copula를 결합하여 결합 분포를 구성합니다.
• 최적화 문제: 가우시안 파라미터화 (평균 $m$, 공분산 $\Sigma$) 를 가정하고, Wasserstein 거리의 제곱을 최소화하는 문제를 풉니다.
  • 목적 함수: $\min_{F_G, R} \|F_G m - m^\star\|^2 + \text{Tr}(\dots)$ (평균 정렬 및 공분산 정렬)
  • 알고리즘: $F_G$와 상관 행렬 $R$에 대해 교대 최소화 (Alternating Minimization) 를 수행합니다.

3. 주요 기여 (Key Contributions)

1. GDS 프레임워크 제안: 신호를 Wasserstein 공간의 확률 분포로 모델링하여 불확실성 (uncertainty) 과 확률적 변동성 (stochasticity) 을 자연스럽게 인코딩하는 새로운 GSP 패러다임을 제시했습니다.
2. 개념적 사전 (Dictionary) 구축: 기존 GSP 의 핵심 개념 (푸리에 변환, 컨볼루션 필터링 등) 을 GDS 에 대응시키는 체계적인 매핑을 정립했습니다. 이를 통해 기존 벡터 기반 알고리즘이 GDS 프레임워크에서 어떻게 일반화되는지 증명했습니다.
3. 실험적 유효성 입증: 그래프 필터 학습 (예측) 태스크를 통해 제안된 프레임워크의 효과성을 검증했습니다.

4. 실험 결과 (Results)

• 데이터셋: 2020~2022 년 코로나 19 일별 확진자 수 데이터 (캘리포니아주 58 개 카운티) 를 사용했습니다.
• 비교 대상: 기존 GSP 방법론 (GSP-LS, GSP-RLS, GSP-LSCM, GSP-LEV) 과 비교했습니다.
• 성능 평가:
  • 마스크링 (Masking) 테스트: 일부 노드 데이터가 누락된 상황 (비완전 관측) 에서 기존 벡터 기반 방법 (GSP-LS 등) 은 성능이 급격히 저하된 반면, GDS-Cop과 GSP-LEV 는 분포 정합 기반이므로 데이터 누락에 강건하게 성능을 유지했습니다.
  • 셔플링 (Shuffling) 테스트: 시간적 정렬이 깨진 상황 (비동기적 데이터) 에서 기존 방법들은 큰 오차를 보인 반면, GDS-Cop 은 시간적 정렬에 의존하지 않아 안정적인 예측 성능을 보였습니다.
  • 정확도: 모든 윈도우 크기에서 GDS-Cop 이 가장 낮은 평균 상대 제곱 오차 (ARSE) 를 기록하며 가장 정확한 예측을 수행했습니다.

5. 의의 및 결론 (Significance)

이 논문은 그래프 신호 처리의 패러다임을 **벡터 (Vector)**에서 **분포 (Distribution)**로 전환함으로써, 실제 세계 데이터가 가진 **불완전성 (incompleteness)**과 **불확실성 (uncertainty)**을 체계적으로 처리할 수 있는 이론적 기반을 마련했습니다.

• 이론적 확장: 기존 GSP 이론을 Wasserstein 공간으로 자연스럽게 확장하여, 불규칙하거나 정렬되지 않은 그래프 구조 데이터에 대한 처리를 가능하게 했습니다.
• 실용적 가치: 센서 네트워크, 교통 시스템, 역학 데이터 등 노드 간 데이터 수집이 비동기적이거나 결측이 빈번한 실제 응용 분야에서 더 강건하고 정확한 예측 모델을 구축할 수 있는 길을 열었습니다.

결론적으로, 이 연구는 불확실성을 내재한 그래프 데이터 처리를 위한 새로운 표준 프레임워크를 제시하며, 기존 GSP 이론의 한계를 극복하는 중요한 진전을 이루었습니다.