Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Each language version is independently generated for its own context, not a direct translation.

1. 문제 상황: "정답은 하나인데, 답안지는 여러 개일 수 있다?"

Imagine you are a detective trying to identify a suspect based on a blurry photo (input).

기존 방식: AI 가 "범인은 김철수입니다!"라고 단정적으로 말합니다. 하지만 김철수가 범인이 아닐 수도 있는데, AI 는 그 가능성을 알려주지 않습니다.
이 연구의 목표: "범인은 김철수일 가능성이 90% 이상입니다. 만약 김철수가 아니라면, 이 3 명의 다른 용의자 중 하나일 겁니다"라고 **확실한 범위 (Set)**를 제시하고 싶었습니다.

하지만 여기서 큰 문제가 생깁니다. 범인은 **사람 (단순한 객체)**이 아니라 **분자 (복잡한 구조)**입니다.

분자 A 와 분자 B 는 원자 배열이 똑같지만, 원자들의 이름 (레이블) 만 바뀌어 있을 수 있습니다. (예: 왼쪽에 있는 탄소와 오른쪽에 있는 탄소를 바꿔도 같은 분자입니다.)
기존 AI 는 "이게 정답이고 저게 오답이야"라고 딱 잘라 말하지만, 구조는 같는데 이름만 다른 경우를 구별하지 못해 엉뚱한 불확실성을 계산할 수 있습니다.

2. 해결책 1: "거울 속의 그림자"를 비교하는 자 (Z-Gromov-Wasserstein 거리)

이 연구는 **"Z-Gromov-Wasserstein (Z-GW)"**이라는 새로운 자를 고안했습니다.

비유: 두 개의 복잡한 퍼즐 (그래프) 을 비교한다고 상상해 보세요.
- 기존 자는 "퍼즐 조각 1 번이 A 위치, 2 번이 B 위치"라고 딱 맞춰야만 같다고 봅니다.
- **이 연구의 자 (Z-GW)**는 "조각들의 관계가 똑같은가?"를 봅니다. "A 가 B 옆에 있고, B 가 C 위에 있는 구조"가 같다면, 조각의 번호가 바뀌어도 똑같은 퍼즐로 인정합니다.
- 마치 거울에 비친 그림자를 비교하듯, 구조적 본질만 보고 거리를 재는 것입니다. 이를 통해 AI 가 예측한 분자와 실제 분자가 '구조적으로 얼마나 비슷한지'를 정확히 측정할 수 있게 됩니다.

3. 해결책 2: "상황에 맞는 안전벨트" (SCQR)

기존의 불확실성 측정법은 모든 상황에 똑같은 크기의 안전벨트를 채워줍니다.

"어떤 질문이든 정답을 찾을 확률이 90% 이면, 답을 5 개씩 줘라"라고 합니다.
하지만 쉬운 질문에는 5 개가 너무 많고 (비효율적), 어려운 질문에는 5 개가 너무 적어 정답을 놓칠 수 있습니다.

이 연구는 **SCQR (점수 기반 적응형 양자 회귀)**이라는 기술을 도입했습니다.

비유: 상황에 따라 길이가 조절되는 스마트 안전벨트입니다.
- 쉬운 질문 (명확한 분자 스펙트럼): "이건 확실히 A 분자야!" → 안전벨트를 짧게 조여 답을 1~2 개만 줍니다. (정확도 유지하면서 효율 극대화)
- 어려운 질문 (모호한 스펙트럼): "이건 A 일 수도 있고 B 일 수도 있어..." → 안전벨트를 길게 풀어 답을 10~20 개 줍니다. (정답을 놓치지 않도록 보호)
이렇게 입력 데이터의 난이도에 따라 예측 범위를 적응적으로 조절합니다.

4. 실제 실험: "분자 찾기 게임"

연구진은 이 방법을 두 가지 게임에 적용해 보았습니다.

합성 게임 (그림에서 그래프 맞추기): 그림을 보고 어떤 색으로 칠해진 그래프가 나올지 예측하는 게임.
- 결과: 안전벨트 (예측 집합) 를 상황에 맞게 조절하니, 정답을 놓치지 않으면서도 불필요한 후보를 줄일 수 있었습니다.
실제 게임 (질량 분석기로 분자 찾기): 화학 물질의 스펙트럼 (지문 같은 것) 을 보고 어떤 분자인지 맞추는 게임.
- 결과: 기존 방식은 정답을 찾을 확률은 높았지만, 후보 목록이 너무 길어서 (평균 24 개) 실용적이지 않았습니다.
- 이 연구의 방식 (SCQR): 난이도에 따라 후보 목록을 평균 15 개로 줄이면서도 정답을 찾을 확률 (90% 이상) 은 유지했습니다. 마치 "너무 많은 용의자 목록을 정밀하게 필터링해서 핵심 용의자만 남긴 것"과 같습니다.

5. 요약: 이 연구가 왜 중요한가?

이 논문은 **"복잡한 구조 (그래프) 를 예측할 때, AI 가 '내가 얼마나 확신하는지'를 정직하게 알려주는 방법"**을 제시했습니다.

구조를 무시하지 않음: 분자나 네트워크처럼 이름이 바뀌어도 같은 것을 구별해냅니다.
유연함: 쉬운 문제는 간결하게, 어려운 문제는 넓게 예측하여 실용성을 높였습니다.
신뢰성: "이 예측은 90% 확률로 정답을 포함한다"는 수학적 보장을 제공합니다.

결국, 이 기술은 화학, 의료, 물리학 등 고가의 실험이 필요한 분야에서 AI 의 예측을 신뢰하고, 불필요한 실험을 줄이는 데 큰 도움을 줄 것입니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의 (Problem)

이 논문은 지도 학습 그래프 예측 (Supervised Graph Prediction, SGP) 과 관련된 불확실성 정량화 (Uncertainty Quantification) 문제를 다룹니다.

배경: 분자 식별 (화학), 장면 이해 (컴퓨터 비전) 등 다양한 분야에서 입력 (텍스트, 이미지, 스펙트럼 등) 을 구조화된 그래프 (노드와 엣지로 구성) 로 매핑하는 예측 모델이 필요합니다.
한계: 기존 그래프 예측 모델들은 단일 예측값을 제공하지만, 실험적 검증 비용이 높은 분야 (예: 신약 개발) 에서는 신뢰 구간 (Confidence Set) 이나 불확실성 범위를 제공하는 것이 필수적입니다.
도전 과제:
1. 구조적 복잡성: 그래프는 유클리드 공간이 아닌 비유클리드, 조합적 (combinatorial) 공간에 존재하며, 노드 순열 (permutation) 에 불변해야 합니다.
2. 불확실성 정량화 부재: 기존 Conformal Prediction (CP) 은 주로 유클리드 공간의 실수 값에 적용되었으며, 그래프와 같은 복잡한 구조적 출력 공간에 적용하기 위한 이론적 프레임워크와 적합한 점수 함수 (nonconformity score) 가 부족했습니다.

2. 방법론 (Methodology)

저자들은 그래프 출력에 대한 분포 자유 (distribution-free) 커버리지 보장을 제공하는 새로운 Conformal Prediction 프레임워크를 제안합니다.

가. Z-Gromov-Wasserstein (Z-GW) 거리를 활용한 비동일성 점수 (Nonconformity Score)

핵심 아이디어: 그래프는 노드 라벨링 순서에 따라 달라질 수 있으므로, 순열 불변 (permutation-invariant) 인 거리 측정이 필요합니다. 이를 위해 Z-Gromov-Wasserstein (Z-GW) 거리를 도입했습니다.
Z-네트워크 (Z-networks): 그래프를 노드와 엣지의 속성 정보를 포함하는 일반화된 메트릭 공간으로 정의합니다.
점수 함수: 예측된 그래프 $\hat{y}$ $\overset{y}{^}$ 와 후보 그래프 $y$ $y$ 사이의 거리를 비동일성 점수로 사용합니다.
$s(x, y) = GW^Z_p(f_\theta(x), y)$
- 여기서 $f_\theta(x)$ 는 사전 학습된 그래프 예측 모델의 출력입니다.
- 실제 구현에서는 Fused Gromov-Wasserstein (FGW) 거리를 사용하여 구조적 정보와 노드/엣지 속성 정보를 동시에 고려합니다.
유효성 증명: 이 점수 함수는 그래프의 순열 불변성을 만족하며, 몫 공간 (quotient space, 동형인 그래프들을 하나의 클래스로 간주) 에서 Conformal Prediction 의 유효성 (Coverage Guarantee) 을 수학적으로 증명했습니다.

나. Score Conformalized Quantile Regression (SCQR)

문제: 기존 CP 는 모든 입력에 대해 단일 전역 임계값 (global threshold) 을 사용하여, 입력에 따른 불확실성 차이 (heteroscedasticity) 를 반영하지 못합니다.
해결: SCQR을 제안하여 입력 의존적 (input-dependent) 인 적응형 예측 집합을 생성합니다.
- 비동일성 점수의 조건부 분위수를 추정하기 위해 Quantile Regression을 활용합니다.
- 입력의 복잡도 (예: 후보 집합의 크기, 스펙트럼 임베딩 등) 를 조건 변수로 사용하여 임계값을 동적으로 조정합니다.
- 이를 통해 쉬운 입력에는 좁은 예측 집합을, 어려운 입력에는 넓은 예측 집합을 제공하면서도 한계 커버리지 (marginal coverage) 보장은 유지합니다.

다. 실용적 제한 사항 처리

그래프 공간은 조합적으로 매우 크기 때문에 모든 가능한 그래프를 나열하여 예측 집합을 만드는 것은 불가능합니다.
따라서 입력 의존적 후보 라이브러리 (Candidate Library, $L(x)$ ) 와 교집합을 취하여 유한한 예측 집합을 구성합니다 (예: 질량 스펙트럼에서 질량이 일치하는 분자 후보들).

3. 주요 기여 (Key Contributions)

Z-GW 기반 Conformal Graph Prediction 프레임워크: 그래프 출력에 대한 순열 불변 비동일성 점수를 정의하고, 몫 공간에서의 유효성을 이론적으로 증명했습니다.
SCQR (Score Conformalized Quantile Regression) 제안: 복잡한 구조적 출력 공간 (그래프 등) 에 적용 가능한 적응형 Conformal Prediction 방법을 개발했습니다.
실험적 검증: 합성 데이터 (이미지 $\to$ 그래프) 와 실제 문제 (질량 스펙트럼 $\to$ 분자 식별) 에 대한 실험을 통해 프레임워크의 효과성과 유연성을 입증했습니다.

4. 실험 결과 (Results)

실험은 Synthetic Coloring Task (이미지에서 그래프 복원) 와 Metabolite Identification (MassSpecGym 벤치마크, 질량 스펙트럼에서 분자 식별) 에서 수행되었습니다.

커버리지 유효성 (Coverage Validity):
- 두 작업 모두에서 명목상 90% 커버리지 ($1-\alpha = 0.9$) 를 달성했습니다. (예: Coloring 90.2%, Metabolite 89.0~89.5%)
- 이는 제안된 Z-GW 기반 점수 함수가 그래프 공간에서 Conformal Prediction 의 이론적 보장을 잘 따름을 의미합니다.
효율성 (Efficiency - 예측 집합 크기):
- SCQR 의 적응성: SCQR 은 입력 특성에 따라 예측 집합 크기를 동적으로 조절합니다.
  - Metabolite Task: SCQR 을 스펙트럼 임베딩 (DREAMS) 에 조건부로 적용한 경우, 기존 CP 대비 평균 예측 집합 크기를 24 에서 15 로 감소시켰으며, 평균 감소율은 77.1% 에서 **84.8%**로 향상되었습니다.
  - Coloring Task: 후보 집합 크기에 조건부 SCQR 을 적용했을 때, CP 와 유사한 성능을 보였으나 여전히 높은 감소율 (95% 이상) 을 유지했습니다.
거리 측정의 영향:
- FGW (Fused GW) 는 구조 정보와 노드/엣지 속성 정보를 모두 고려하여, 순수 GW 나 FNGW 보다 더 작은 예측 집합 (더 높은 효율성) 을 생성했습니다.

5. 의의 및 결론 (Significance)

구조적 예측의 불확실성 정량화: 그래프와 같은 비유클리드, 구조적 출력 공간에서 신뢰할 수 있는 불확실성 범위를 제공하는 최초의 체계적인 프레임워크 중 하나입니다.
실용적 가치: 분자 발견, 신약 개발 등 실험 비용이 높은 분야에서 모델의 신뢰도를 높이고, 불확실성이 큰 경우에만 추가 실험을 수행하도록 유도하여 연구 효율성을 극대화할 수 있습니다.
확장성: 이 프레임워크는 메시 (meshes), 점 구름 (point clouds), 분포 (distributions) 등 Z-네트워크로 표현 가능한 다른 구조적 출력 공간으로도 자연스럽게 확장 가능합니다.

요약하자면, 이 논문은 Z-Gromov-Wasserstein 거리를 활용하여 그래프 예측의 순열 불변성을 보장하고, SCQR을 통해 입력별 불확실성을 고려한 적응형 예측 집합을 생성함으로써, 구조적 머신러닝의 신뢰성을 획기적으로 높인 연구입니다.