기술적 요약: 위상 데이터 분석을 통한 복잡 네트워크의 차원 감지를 위한 코드리스 사이클 필터레이션

1. 문제 제기

생물학적, 사회적, 기술적 등 다양한 영역의 복잡 네트워크는 종종 잠재된 쌍곡 기하학 구조와 일치하는 구조적 패턴을 보입니다. 이러한 잠재 공간의 유효 차원 ($D$) 을 결정하는 것은 구조적 복잡성, 커뮤니티 조직, 네트워크 탐색, 시스템 역학을 이해하는 데 필수적입니다. 프랙탈, 스펙트럼, 거리 기반 등 네트워크 차원에 대한 다양한 정의가 존재하며, $S^D/H^{D+1}$ 모델과 같은 모델 기반 접근법은 사이클 주파수를 구성 공간에 투영하여 차원을 성공적으로 추정해 왔습니다. 그러나 이러한 방법들은 새로운 대상 네트워크마다 대규모의 합성 대리 네트워크 (synthetic surrogate networks) 군집을 생성해야 하므로 계산 집약적이며, 대리 네트워크 생성 없이 위상 데이터 분석 (TDA) 과 머신러닝을 통합하는 통합된 데이터 기반 프레임워크가 부족합니다.

또한, 네트워크 과학에서의 표준 TDA 응용은 제한적이었습니다. 일반 영속 호몰로지 (ordinary persistent homology) 는 고차 심플렉스가 사이클을 채워주지 않는 한 1 차원 특징인 사이클이 무한한 영속성을 가지므로 그래프에는 적합하지 않습니다. 또한, 기존 필터레이션 방식 (예: 노드 차수 또는 리치 곡률 기반) 은 차원 추정에 필요한 특정 기하학적 서명을 포착하지 못할 수 있습니다.

2. 방법론

저자들은 대수적 위상수학과 머신러닝을 결합하여 네트워크 차원을 추정하는 양면적 접근법을 제안합니다.

A. 코드리스 사이클 필터레이션 및 확장 영속성

핵심 위상적 혁신은 코드리스 사이클(내부 현이 없는 사이클) 기반의 가중치 부여 scheme 입니다.

1. 가중치 부여: 주어진 네트워크에 대해 세 가지 엣지 가중 그래프를 구성합니다. 엣지의 가중치는 삼각형 ($C_t$), 사각형 ($C_s$), 오각형 ($C_p$) 의 특정 길이를 가진 코드리스 사이클의 국부적 밀도에 의해 정의됩니다.
2. 확장 영속성: 그래프 내의 사이클은 표준 필터레이션에서 소멸하지 않으므로, 저자들은 **확장 영속성 (extended persistence)**을 계산합니다. 이는 "차수 분할 세분화 (degree-splitting subdivision)"를 통해 엣지 가중 그래프를 위상적으로 동등한 노드 가중 그래프로 변환하는 기법을 포함합니다. 이를 통해 서브레벨 필터레이션의 탄생 값과 슈퍼레벨 필터레이션의 탄생 값 사이의 차이로 정의된 사이클의 확장 영속성을 계산하기 위해 표준 TDA 소프트웨어 (Gudhi) 를 사용할 수 있습니다.
3. 기술자: 세 가지 필터레이션 각각에 대해 모든 독립 사이클의 영속 값의 합인 **총 확장 영속성 (Total Extended Persistence)**을 계산하여 특징 벡터 $(TP_t, TP_s, TP_p)$를 도출합니다.

B. 차원 추정 접근법

이 논문은 $D$를 추정하기 위한 두 가지 방법을 제시합니다:

1. 대리 기반 k-최근접 이웃 (kNN):

   • 대상 네트워크에 대해 $D$-GR (Geometric Randomization) 절차를 사용하여 합성 대리 네트워크의 군집을 생성합니다. 이 방법은 대상의 정확한 차수 시퀀스를 보존하면서 $S^D/H^{D+1}$ 모델의 가능도를 최대화하도록 네트워크를 재연결합니다.
   • 대상 네트워크와 그 대리 네트워크들은 $(TP_t, TP_s, TP_p)$로 정의된 구성 공간에 매핑됩니다.
   • kNN 분류기는 대상 네트워크에 가장 가까운 대리 네트워크의 차원 $D$를 식별합니다.

2. 신경망 (DimNN):

   • 새로운 네트워크마다 대리 네트워크를 생성하는 것을 피하기 위해, 저자들은 **잔차 다층 퍼셉트론 (Residual Multilayer Perceptron, DimNN)**을 훈련합니다.
   • 훈련 데이터: 알려진 차원 ($D \in [1, 10]$) 과 다양한 매개변수 (차수 이질성 $\gamma$, 역온도 $\beta$) 를 가진 $S^D/H^{D+1}$ 모델에서 생성된 792,000 개의 합성 네트워크 (SynNet) 데이터베이스입니다.
   • 입력 특징: 모델은 다음을 포함하는 12 차원 특징 벡터를 사용합니다:
     • 그래프 통계: 노드 수 ($N$), 평균 차수 ($\langle k \rangle$), 차수 분포의 정규화된 2 차 모멘트 ($\langle k^2 \rangle / \langle k \rangle^2$), 최소/최대 차수, 평균 이웃 차수 ($\langle k_{nn} \rangle$).
     • 사이클 밀도: 평균 코드리스 삼각형, 사각형, 오각형 밀도 ($C_t, C_s, C_p$).
     • 위상 기술자: 총 확장 영속성 ($TP_t, TP_s, TP_p$).
   • 아키텍처: AdamW 로 훈련된 21 개의 은닉층, ReLU 활성화, 드롭아웃 (50%), 잔차 연결을 가진 심층 MLP 입니다.
   • 검증: 강건성을 검증하기 위해 MSE 손실을 사용하는 보조 회귀 모델이 훈련되었으며, 분류 모델과 높은 일치를 보였습니다.

3. 주요 기여

• 새로운 필터레이션 scheme: 차원과 관련된 기하학적 속성을 포착하도록 특별히 맞춤화된 그래프용 코드리스 사이클 밀도 기반 필터레이션 scheme 도입.
• 그래프를 위한 확장 영속성: 차수 분할 세분화를 통해 엣지 가중 그래프에 확장 영속성을 적용하여, 표준 영속성이 실패하는 네트워크 컨텍스트에서 유한한 사이클 수명 계산을 가능하게 함.
• 데이터 기반 차원 추정: 대리 네트워크 생성 없이 단일 실제 네트워크에서 직접 네트워크 차원을 추정할 수 있도록, 방대한 합성 데이터베이스로 훈련된 DimNN 개발.
• TDA 와 ML 의 통합: TDA 특징 (총 영속성) 이 차원 추정을 위한 머신러닝 모델의 정확도를 크게 향상시켜, 사이클 밀도나 차수 통계만 사용하는 모델보다 성능이 우수함을 입증.

4. 결과

• 상관관계: 네트워크 차원과 총 확장 영속성 값 사이에 음의 상관관계가 관찰되었으며, 특히 사각형과 오각형에서 두드러졌습니다 (피어슨 계수 $\rho_s \approx -0.31$, $\rho_p \approx -0.24$).
• 합성 검증:
  • kNN 대리 방법은 합성 대상에서 합리적인 정확도를 달성했으며, 혼동 행렬은 대부분의 차원에서 높은 충실도를 보였으나, 매우 이질적인 네트워크에서는 인접한 차원 간에 일부 혼란이 발생했습니다.
  • DimNN은 전체 특징 벡터를 사용하여 검증 세트에서 **83.00%**의 분류 정확도를 달성했습니다.
  • **절대 연구 (Ablation studies)**는 총 영속성을 평균 사이클 밀도 및 차수 관련 특징과 결합할 때 성능이 극대화됨을 확인했습니다. TDA 특징을 제거하면 정확도가 크게 하락했습니다.
• 실제 세계 적용:
  • 이 방법은 10 개의 잘 알려진 실제 세계 네트워크 (예: 인간 연결체, 재즈 협업, 이메일 네트워크) 에 적용되었습니다. 추론된 차원은 이전 문헌과 일치했습니다 (예: 뇌 연결체는 $D=3$ 근처, 사회 네트워크는 약간 더 높은 차원 필요).
  • 53 개의 실제 네트워크로 구성된 더 큰 데이터셋에 적용되었을 때, 모델은 1 (소프트웨어, 웹 그래프) 에서 10 (일부 사회 네트워크) 까지의 차원을 예측했습니다.
  • 강건성: 두 개의 독립적으로 훈련된 모델 (분류 및 회귀) 은 높은 일치도를 보였습니다 (합성 데이터에서 최대 88.86%), 이는 모델이 과적합이 아닌 근본적인 관계를 포착하고 있음을 시사합니다.
  • 검증: 예측된 차원과 D-Mercator 임베딩을 사용하여 생성된 대리 네트워크는 원래 네트워크의 차수 분포, 클러스터링 스펙트럼, 퍼콜레이션 임계값을 포함한 주요 위상적 속성을 성공적으로 재현했습니다.

5. 중요성 및 주장

이 논문은 복잡 네트워크 이론과 위상 데이터 분석 사이의 간극을 강건하고 효과적인 방법을 제공함으로써 연결하며, 복잡 네트워크의 숨겨진 기하학을 밝혀낸다고 주장합니다.

• 효율성: 신경망 접근법은 새로운 네트워크에 대한 재훈련이나 대리 네트워크 생성이 필요 없으므로 이전의 대리 기반 방법보다 상당한 계산적 이점을 제공합니다.
• 표현력: 이 연구는 사이클 인식 필터레이션과 확장 영속성 기술자가 차원 감지를 위한 매우 표현력 있는 특징이며, 전통적인 기하학적 기술자를 보완함을 입증했습니다.
• 일반화: 모델은 합성 훈련 데이터에서 실제 세계 네트워크로 성공적으로 이전되었으며, 이는 테스트된 매개변수 범위 내에서 실제 네트워크의 잠재 기하학적 구조가 $S^D/H^{D+1}$ 모델로 잘 표현됨을 시사합니다.

저자들은 이 프레임워크가 주로 기하학적 네트워크 ($\beta > D$) 를 대상으로 하며, 약한 기하학적 영역으로의 접근법 확장이나 더 넓은 분포 변화를 위한 신경 아키텍처 최적화는 향후 연구 방향임을 겸손하게 지적합니다. 이 논문은 TDA 에서 사이클 기반 필터레이션의 유용성과 딥러닝 지원 차원 추정의 실현 가능성에 대한 개념 증명 (proof of concept) 으로 자신을 위치시킵니다.