Graph reconstruction from random-walk co-visitation: Geometric, empirical, and controlled networks

기술 요약: 무작위 보행 공방문(Co-visitation)을 통한 그래프 재구성

문제 정의
본 논문은 무작위 보행(random walk)이 확산되는 미지의 그래프 구조로부터 그래프를 재구성하는 역문제(inverse problem)를 다룬다. 이는 동적 과정(예: 시계열, 확산 프로세스 또는 확산 추적자)은 관찰 가능하지만, 그 기저의 연결성(즉, "배선")은 관찰되지 않는 맥락에서 발생한다. 이 영역의 핵심 과제는 **재구성 가능성(reconstructibility)**이다. 무작위 보행은 실제로 통과한 에지(edge)에 대한 정보만을 전달할 수 있으며, 샘플링된 궤적에 의해 방문되지 않은 에지는 사용된 추정기와 관계없이 근본적으로 복구가 불가능하다. 두 번째 과제는 **식별 가능성(identifiability)**이다. 관측값은 노드 수준의 요약 통계량(예: 차수 시퀀스)과 동일한 구조를 공유하는 그래프들을 구별할 수 있을 만큼 충분한 쌍별(pairwise) 구조 정보를 보유해야 한다.

방법론
저자들은 구조적 정보가 노드 수준의 통계치로 붕괴되는 것을 방지하기 위해 **쌍별 관측값(pairwise observable)**과 **쌍별 모델(pairwise model)**을 활용하는 재구성 파이프라인을 제 제안한다.

1. 관측값 (공방문 행렬): 마진 점유 확률(marginal occupation probabilities)을 사용하는 대신(이는 정체 분포인 차수 분포로 수렴하여 쌍별 정보를 상실함), 이 방법은 공방문 행렬(co-visitation matrix) $C$를 사용한다. 이 행렬은 행의 합을 구하기 전, 방문된 순서쌍 $(i, j)$를 기록함으로써 특정 전이 $i \to j$를 보존한다.
2. 모델 (쌍별 에지 가중치 기저): 모델은 모든 후보 쌍에 대해 쌍별 로그 가중치 $\beta_{ij}$를 가정한다. 전이 행렬 $P$는 가중치 행렬 $S(\beta)$로부터 행 정규화를 통해 유도된다. 이 접근 방식은 각 잠재적 에지에 고유한 파라미터를 할당함으로써, 가법적인 노드 포텐셜 모델이 포착할 수 없는 클러스터 구조를 포착할 수 있게 한다.
3. 피터 (프레임 균형 Levenberg–Marquardt): 파라미터 $\beta$는 프레임 균형 Levenberg–Marquardt (fbLM) 스킴을 사용하여 관측된 공방문 행렬에 피팅된다.
   • 그룹 가중치: 잔차(residual)는 정점(vertex)별로 그룹화된다. 가중치는 특정 정점이 피팅을 지배하지 않도록 직교 프레임(Stiefel 다양체) 상에서 최적화된다. 이러한 "프레임 균형"은 가중치가 고차수 노드로 쏠리는 것을 방지하며, 고유한 정보를 가진 정점이 적절한 가중치를 받도록 보장한다.
   • 게이지 고정(Gauge Fixing): 공방문은 모든 로그 가중치의 전역적 이동($\beta \to \beta + c\mathbf{1}$)에 대해 불변이다. 이 방법은 각 제안 단계 이후 파라미터를 중심화함으로써 이 게이지를 명시적으로 고정한다.
   • 불확실성 전파: 공피합(covariance matrix)은 피셔 정보(Fisher information)로부터 유도되며, 수치적 불안정성을 피하기 위해 게이지 방향을 명시적으로 투영하여 제거한다.
4. 리드아웃 (자기 교정 결합): 최종 에지 집합은 자기 교정 결합 메트릭 $\rho_{ij} = W_{ij}/\sqrt{s_i s_j}$에 의해 결정된다(여기서 $W$는 피팅된 가중치, $s_i$는 정점 강도이다). $\rho_{ij}$가 두 엔드포인트의 평균 결합도를 초과할 경우 에지가 있는 것으로 간주한다. 이 임계값은 상대적이며 데이터 기반으로, 절대적인 컷오프나 사전 지식을 요구하지 않는다.

데이터셋 및 실험 설정
파이프라인은 다섯 가지 서로 다른 테스트베드에서 테스트된다:

• 경험적(Empirical): 다양한 크기($N=20, 100, 240$)의 이메일 통신 서브그래프(email-Eu-core).
• 기하학적 (천체물리학적): COSMOS 하늘 카탈로그에서 유도된 Delaunay 삼각측량 및 Voronoi 테셀레이션 (전체 범위 $N=119$ 및 $N=223$에서 재구성).
• 제어된(Controlled): 건전성 검사를 위한 두 개의 12-정점 그래프 (하나는 단일 순환 그래프, 하나는 트리).

실험은 두 가지 체제 하에서 수행된다:

1. 유한 보행 체제(Finite-Walk Regime): 궤적 길이 $T$의 샘플링된 궤적으로부터의 재구성.
2. 승법 노이즈 체제(Multiplicative-Noise Regime): 가우시안 노이즈로 섭동된 해석적 공방문 행렬로부터의 재구성으로, 추정기의 내성을 샘플링 커버리지와 분리하여 고립시킨다.

주요 결과

• 고충실도 재구성: 파이프라인은 모든 테스트베드에서 높은 재구성 품질을 달ien한다. 전체 규모의 기하학적 그래프에서, Delaunay 및 Voronoi 구조를 각각 0.988 및 0 % 977의 Matthews 상관 계수(MCC)로 복구한다. 경험적 이메일 그래프($N=240$)에서도 0.967의 MCC를 달성한다.
• 베이스라인과의 비교: fbLM 파이프라인은 graphical-lasso 베이스라인을 크게 압도한다. 전체 Delaunay 그래프에서 베이스라인은 0.540의 MCC를 반환한 반면, fbLM은 0.988을 기록했다.
• 커버리지 제한: 유한 보행 체제에서 제한 요인은 피팅 알고리즘이 아니라 **보행 커버리지(walk coverage)**이다. 분석 결과, 허위 음성(false negatives)은 거의 예외 없이 무작위 보행이 방문하지 않은 에지에 해당한다. 보행이 그래프를 커버하면, 추정기는 거의 완벽한 충실도로 에지를 복구한다.
• 노이즈 강건성: 모든 쌍이 후보인 승법 노이즈 체제에서, 방법은 낮은 노이즈 수준에서 그래프를 정확하게 복구한다. 40% 노이즈에서도 방법은 완벽한 에지 순위를 유지하며(AUC = 1.000), 성능 저하는 강한 에지가 리드아웃 임계값 아래로 떨어질 때만 발생하며 허위 양성(false positives) 때문은 아니다.
• 불확실성 정량화: 방법은 피셔 정보로부터 유도된 에지별 불확실성을 제공한다. 이러한 불확실성은 상당하지만(중앙값 상대 불확실성 $\sim$30–45%), 경계 또는 저커버리지 에지에 정확히 국지화되어 있으며, 내부 에지는 엄격하게 제약되어 있다.

의의 및 주장
본 논문은 그래프의 크기, 밀도 또는 기저의 인접 행렬에 대한 사전 지식 없이 작동하는 강력한 그래프 재구성 추정기를 확립한다고 주장한다. 주요 기여는 기하학적 및 경험적 네트워크의 경우 재구성 가능성이 추정기가 아닌 샘플링에 의해 결정된다는 점을 입증하는 것이다.

저자들은 다음을 강조한다:

1. 재구성 가능성은 샘플링 문제이다: 보행이 에지를 방문하지 않으면 어떤 추정기도 이를 복구할 수 없다. 제안된 방법은 궤적으로부터 가능한 모든 정보를 추출한다.
2. 쌍별 관측값이 필수적이다: 차수 분포와 동일한 그래프들을 구별하기 위해서는 마진 통계량이 아닌 공방문을 사용하는 것이 필요하다.
3. 자기 교정: 리드아웃 메커니즘은 외부 튜닝이나 절대적 임계값을 요구하지 않으므로, 미지의 그래프에도 적용 가능하다.
4. 천체물리학적 적용 가능성: 방법은 실제 천체 데이터(COSMOS 카탈로그)에서 유도된 기하학적 그래프에 성공적으로 적용되었으며, 이는 그래프 자체가 모델링 선택이 아닌 추론의 대상이 되는 프레임워크를 구축한다.

결론적으로, 추정기는 매우 효과적이지만, 유한 보행 시나리오에서의 실질적인 재구성 한계는 네트워크의 궤적 커버리지에 의해 결정되며, 이는 피팅 절차와 독립적으로 정량화하고 최적화할 수 있는 요소임을 밝힌다.