Adaptive Hypothesis Testing for Dependent Graph-Valued Structures via Topological Value of Information

Motivation

• Known: 기존 연구는 causal graph, mechanistic graph, graph neural network 기반 세계 모델 등 다양한 graph-valued 예측을 다루며, 불확실성 정량화는 주로 고정된 관계 구조 하에서의 aleatoric/epistemic uncertainty(관측·파라미터 불확실성)에 초점을 맞춰왔다. Bayesian experimental design과 active learning 역시 scalar property나 고정 모델의 예측 불확실성을 대상으로 다음 실험을 선택하는 데 주로 사용되어 왔다.
• Gap: edge 가설들이 서로 독립적이지 않고 구조적으로 결합되어 있어(하나의 edge 해소가 component 병합, cycle 제거, 다른 edge 해석 변경을 유발) 국소적 edge 불확실성만으로는 그래프 수준의 전역 모호성을 효율적으로 줄일 수 없으며, 기존 causal discovery나 구조 학습 방법들은 이러한 dependent structural hypothesis를 예산 제약 하에서 어떤 순서로 검증할지에 대한 명시적 decision-layer 정책을 제공하지 않는다.
• Why: 현대 ML 시스템이 산출하는 causal graph, mechanistic graph, interaction network, graph 기반 설명 등의 신뢰성은 결국 어떤 구조적 가설을 다음에 검증할 것인가에 달려 있으며, 이는 과학적 발견(약물 설계, 반응 메커니즘 해석 등)에서 측정·계산 자원을 효율적으로 배분하는 실질적 문제와 직결된다.
• Approach: 후보 edge에 대한 확률적 belief graph를 thresholding하여 얻은 undirected graph의 Betti number(β0, β1)를 결합한 topological complexity score를 정의하고, 각 후보 테스트가 단위 비용당 기대하는 topological simplification을 Monte Carlo 시뮬레이션으로 추정해 greedy하게 다음 테스트를 선택하는 TCM 정책을 제안한다.

Achievement

1. 문제 정식화: 후보 edge를 dependent binary hypothesis로 다루고, 전역 그래프 구조를 고려한 adaptive structural hypothesis testing 프레임워크를 제시했다.
2. TCM 정책 제안: β0(connected components)와 β1(independent cycles)을 결합한 topological complexity score를 기반으로, 비용 대비 기대 위상적 단순화를 최대화하는 cost-aware greedy 테스트 선택 정책을 설계했다.
3. 광범위한 벤치마크 검증: bnlearn의 Child, Insurance Bayesian network DAG와 mech-USPTO-31k의 200개 atom-level mechanistic graph에서 cycle-dominated, fragmentation-dominated, mixed corruption regime 전반에 걸쳐 TCM이 최고의 structural efficiency를 달성하면서도 edge-level F1 성능을 유지함을 보였다.
4. 정량적 개선 수치 제시: mechanistic graph에서 CycleRank 대비 fragmentation regime 0.452→0.576, mixed regime 0.715→0.830, Bayesian network DAG에서 각각 1.062→1.471, 1.406→2.049로 structural efficiency 개선을 입증했다.

How

• Ground-truth 그래프 G⋆에서 edge를 제거(false negative)하거나 spurious edge를 주입(false positive)하여 확률적 belief graph를 생성하는 controlled corruption-and-oracle 프로토콜을 사용
• 임계값 τ로 belief graph를 thresholding하여 얻은 undirected 1-skeleton Kτ에서 β0(연결요소 수), β1 = m − n + β0(독립 사이클 수)를 계산해 topological ambiguity를 정량화
• 각 테스트 후보에 대해 노이즈가 있는 oracle 응답을 시뮬레이션하고 Bayes 규칙으로 belief를 갱신했을 때 기대되는 topological complexity 감소량을 Monte Carlo로 추정, 이를 테스트 비용으로 정규화하여 greedy하게 다음 테스트를 선택
• CycleRank 등 local uncertainty heuristic 및 structure-aware baseline과 비교하여 cycle-dominated, fragmentation-dominated, mixed corruption regime에서 structural efficiency와 edge-level F1을 평가

Originality

• 기존에 topology(예: Betti number, persistent homology)를 feature, prior, regularizer로 사용하던 것과 달리, thresholded belief graph의 위상 불변량을 adaptive test 선택을 위한 decision-layer utility로 직접 활용하는 새로운 관점을 제시
• 인과 discovery, active learning, Bayesian experimental design이 주로 scalar property나 고정 모델의 예측 불확실성을 다루던 것에서 벗어나, edge 자체가 구조적으로 결합된 가설이라는 점을 명시적으로 모델링
• 화학 반응 메커니즘(mech-USPTO-31k)과 Bayesian network 두 이질적 도메인에서 동일한 topological utility가 일관되게 작동함을 보여 프레임워크의 범용성을 시사

Limitation & Further Study

• 상위 예측기(causal discovery 모델, GNN, LLM 기반 추출기 등)를 명시적으로 모델링하지 않고 controlled corruption-and-oracle 프로토콜로 대체했기 때문에, 실제 업스트림 모델의 불확실성 분포와의 정합성 검증이 부족함
• β0, β1이라는 단순한 위상 불변량만 사용하므로, 더 세밀한 구조적 특성(예: 방향성, edge weight의 의미론적 차이, motif 수준 패턴)을 포착하지 못할 가능성이 있음
• threshold τ 선택이 성능에 미치는 민감도나 실제 도메인에서의 oracle 비용 모델링이 단순화되어 있어, 실제 실험 비용 구조와의 괴리가 존재할 수 있음
• 후속 연구로 방향성 그래프(directed graph)에 특화된 topological invariant 확장, 실제 업스트림 모델과의 end-to-end 통합, 다양한 threshold 및 비용 함수에 대한 민감도 분석이 필요함

Evaluation

총평: edge 가설 간의 구조적 의존성을 위상학적 관점에서 정량화하고 이를 adaptive test 선택 정책으로 연결한 참신하고 실용적인 접근이며, 서로 다른 두 도메인에서 일관된 성능 향상을 보여 향후 causal discovery 및 화학 메커니즘 추론 분야의 실험 설계에 유용한 프레임워크가 될 잠재력이 있다.