Exact Graph Learning via Integer Programming

논문 제목: 정수 계획법을 통한 정확한 그래프 학습 (Exact Graph Learning via Integer Programming)
저자: Lucas Kook, Søren Wengel Mogensen

이 논문은 복잡한 시스템 내 변수 간의 의존성 구조를 데이터로부터 추론하는 그래프 학습 (Graph Learning) 또는 인과성 발견 (Causal Discovery) 문제를 해결하기 위해, 조건부 독립성 검사와 **정수 계획법 (Integer Programming, IP)**을 결합한 새로운 프레임워크인 **GLIP (Graph Learning via Integer Programming)**을 제안합니다.

아래는 논문의 주요 내용을 기술적으로 요약한 것입니다.

---

1. 문제 정의 (Problem)

• 배경: 의료, 자연과학, 사회과학 등 다양한 분야에서 변수 간의 인과적 또는 통계적 의존 관계를 그래프로 표현하고 이를 데이터로부터 학습하는 것이 핵심 과제입니다.
• 기존 방법의 한계:
  • 제약 기반 (Constraint-based) 방법 (예: PC, FCI 알고리즘): 조건부 독립성 검사를 순차적으로 수행하여 간선을 제거하는 방식입니다. 하지만 유한 표본에서의 조건부 독립성 검사는 통계적 검정력 (power) 이 낮거나 가정에 민감하여, 잘못된 간선 제거로 이어질 수 있습니다. 또한, 이산적 탐욕 (greedy) 전략을 사용하여 전역 최적해를 보장하지 못합니다.
  • 점수 기반 (Score-based) 방법: 데이터와 그래프의 적합도를 측정하는 점수를 최적화합니다. 하지만 전역 최적해를 보장하기 어렵거나, 데이터 생성 과정에 대한 강한 분포적 가정 (예: 선형 가우시안) 을 요구하는 경우가 많습니다.
  • 정확한 (Exact) 방법의 한계: 기존에 제안된 정확한 방법들 (예: Answer Set Programming 기반) 은 소규모 그래프 (노드 수 $d \le 6$) 에서는 작동하지만, 그래프 크기가 커지면 계산 비용이 급증하여 실용성이 떨어집니다.

2. 방법론 (Methodology)

저자들은 그래프 학습 문제를 **혼합 정수 계획법 (Mixed-Integer Programming, MIP)**으로 재구성하고, 이를 효율적으로 해결할 수 있는 최소 길이 인코딩 (Minimal-length Encoding) 기법을 도입했습니다.

2.1 최적화 문제 설정

• 목적 함수: 조건부 독립성 검사의 $p$-값과 그래프가 함의하는 분리 (separation) 구조 간의 불일치를 최소화하는 점수를 정의합니다.
  • $f(G, D_n) = \sum w_{ijC} | \mathbb{I}(i \perp \perp j | C \text{ in } G) - \mathbb{I}(p_{ijC} > \alpha) |$
  • 이는 제약 기반 방법의 직관 (조건부 독립성) 을 유지하면서도, 전역 최적해를 찾는 최적화 문제로 변환합니다.
• 변수:
  • $x$: 간선 존재 여부 (이진 변수).
  • $l$: 두 노드 간의 최소 연결 경로 길이 (정수 변수).
  • $z$: 분리/연결 여부 (이진 변수).
  • $w$: 보조 변수 (목적 함수의 절대값 선형화 등).

2.2 핵심 기술: 최소 길이 인코딩 (Minimal-length Encoding)

기존의 정수 계획법 접근법 (예: Eberhardt et al., 2025) 은 모든 가능한 경로를 변수로 표현하여 변수 수가 $O(d!)$로 증가하는 문제가 있었습니다. GLIP 은 다음과 같은 혁신을 제시합니다:

• 개념: 두 노드가 조건부 독립인지 여부는 모든 경로를 확인하는 것이 아니라, **조건부 독립을 위반하는 가장 짧은 경로 (최소 연결 경로)**의 존재 여부만 확인하면 충분합니다.
• 구현: 각 조건부 집합 $C$에 대해 두 노드 $i, j$ 사이의 **최소 연결 경로 길이 ($l^C_{\{i,j\}}$)**를 변수로 정의합니다.
• 효율성: 이 인코딩을 통해 변수의 수가 입력된 $p$-값의 수에 대해 **선형 (Linear)**으로 증가하도록 설계되었습니다. 이는 기존 방법의 계승적 (factorial) 증가와 대조적입니다.
• 제약 조건: 그래프의 분리 기준 (d-separation, m-separation, c-separation 등) 을 만족시키기 위해 경로 길이를 연결하는 일련의 선형 제약 조건 (Constraints) 을 정의합니다. 예를 들어, $l^C_{\{i,j\}} \le l^C_{\{i,k\}} + l^C_{\{k,j\}} + \text{penalty}$ 형태의 재귀적 관계를 통해 최소 길이를 정확히 계산하도록 강제합니다.

2.3 지원되는 그래프 클래스

GLIP 은 다양한 그래프 클래스에 적용 가능합니다:

• DAG (Directed Acyclic Graph): 방향성 비순환 그래프.
• ADMG (Acyclic Directed Mixed Graph): 잠재 변수를 가진 방향성 비순환 그래프.
• DMG (Directed Mixed Graph): 사이클이 허용된 방향성 혼합 그래프 (선형 가우시안 가정 하).
• Chain Graphs: 방향 및 무방향 간선이 혼합된 그래프.

3. 주요 기여 (Key Contributions)

1. 전역 최적해 보장: 제안된 GLIP 알고리즘은 주어진 조건부 독립성 검출 결과에 대해 **전역 최적 (Globally Optimal)**인 그래프를 보장합니다. 이는 탐욕적 알고리즘이 놓칠 수 있는 최적해를 찾을 수 있음을 의미합니다.
2. 비모수적 접근 (Nonparametric): 데이터의 분포 (가우시안 등) 나 함수적 형태에 대한 가정을 하지 않으며, 오직 조건부 독립성 검사의 결과 ($p$-값) 만을 사용합니다.
3. 확장성 (Scalability): 최소 길이 인코딩을 통해 변수 수를 줄여, 기존 정수 계획법 기반 방법 ($d \le 6$) 보다 훨씬 큰 그래프 ($d \approx 9 \sim 14$) 까지 정확한 학습이 가능해졌습니다.
4. 오픈 소스 패키지: glip이라는 R 패키지를 공개하여 DAG, ADMG, Chain Graph 학습을 지원합니다.

4. 실험 결과 (Results)

• 성능 비교 (정확한 방법 vs GLIP):
  • 기존 Answer Set Programming (ASP) 기반 방법 (Hyttinen et al.) 과 비교 시, 작은 그래프 ($d < 6$) 에서는 유사하거나 더 빠르고, 큰 그래프 ($d \ge 6$) 에서는 훨씬 더 많은 인스턴스에서 시간 제한 (600 초) 내에 해를 찾았습니다.
  • 특히 $d=9$ 이상의 DAG 학습에서 GLIP 이 ASP 보다 우세한 성능을 보였습니다.
• 성능 비교 (근사 방법 vs GLIP):
  • PC, FCI, NOTEARS 등 기존 근사 방법들과 비교 시, GLIP 은 **구조적 해밍 거리 (SHD)**와 분리 거리 (SEP) 측면에서 동등하거나 더 우수한 성능을 보였습니다.
  • 특히 표본 크기가 작을 때 ($n=400$) 조건부 독립성 검사의 오류를 보정하여 더 정확한 그래프를 복원하는 "오류 수정 (Error-correcting)" 특성을 입증했습니다.
• 벤치마크 데이터: ALARM, ASIA, CHILD, HEPAR2, SACHS 등 실제 및 합성 데이터셋에서 GLIP 이 다른 방법들보다 우수한 또는 최상의 성능을 기록했습니다.

5. 의의 및 결론 (Significance)

• 이론적 의의: 그래프 학습 문제를 정수 계획법으로 엄밀하게 공식화하고, 최소 길이 인코딩을 통해 계산 복잡도를 획기적으로 낮추는 이론적 토대를 마련했습니다.
• 실용적 의의:
  • Warm-start 전략: 빠른 근사 알고리즘 (PC, FCI) 의 결과를 초기 해 (warm-start) 로 사용하여 GLIP 의 최적화 시간을 단축하는 전략을 제안했습니다.
  • 신뢰성: 전역 최적해를 보장하므로, 중요한 의사결정이 필요한 분야에서 그래프 구조 추론의 신뢰도를 높여줍니다.
  • 유연성: 다양한 그래프 클래스와 조건부 독립성 기준을 지원하며, 도메인 지식 (예: 특정 노드가 싱크 노드여야 함) 을 제약 조건으로 쉽게 추가할 수 있습니다.

결론적으로, GLIP 은 조건부 독립성 검사의 강점과 최적화 기법의 정확성을 결합하여, 기존 방법들의 한계를 극복하고 더 크고 복잡한 시스템의 인과 구조를 정확하게 학습할 수 있는 새로운 표준을 제시합니다.