🤖 AI

Generating Graph-like Rules for Knowledge Graph Reasoning via Diffusion Models

이 논문은 기존 방법들의 한계를 극복하고 지식 그래프 추론을 위한 해석 가능한 그래프 형태의 규칙을 효과적으로 생성하기 위해 지도 학습 기반의 사전 훈련과 강화 학습을 결합한 2단계 훈련 전략을 활용하는 새로운 프레임워크인 GRiD를 제안한다.

원저자: Haoxiang Cheng, Yunfei Wang, Chao Chen, Kewei Cheng, Zhipeng Lin, Haoxuan Li, Changjun Fan, Shixuan Liu

게시일 2026-06-01

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Haoxiang Cheng, Yunfei Wang, Chao Chen, Kewei Cheng, Zhipeng Lin, Haoxuan Li, Changjun Fan, Shixuan Liu

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

큰 그림: "잃어버린 연결 고리" 퍼즐 풀기

**지식 그래프(Knowledge Graph)**를 거대한 사실들의 퍼즐이라고 상상해 보세요. 각 조각은 두 대상 사이의 연결(예: "튜링"과 "영국"이 "태생지"로 연결됨)입니다. 때때로 이 조각들이 빠져 있을 때가 있습니다. **지식 그래프 추론(Knowledge Graph Reasoning)**의 목표는 그 빠진 조각들이 어디에 들어갈지를 알아내는 것입니다.

오랫동안 컴퓨터는 **규칙(rules)**을 찾는 방식으로 이 문제를 해결하려 노력해 왔습니다. 규칙을 간단한 설명서라고 생각하면 쉽습니다. *"만약 어떤 사람이 대학교에서 일하고, 그 대학교가 특정 도시에 있다면, 그 사람은 그 도시에서 태어났다."*와 같은 식이죠.

문제점: "사슬형 규칙" vs "웹형 규칙"

기존 방식 (사슬형 규칙):
대부분의 이전 방법들은 구슬이 한 줄로 꿰어진 것 같은 단일 사슬 형태의 규칙만을 찾았습니다.

비유: 기차를 상상해 보세요. A 칸이 B 칸에 연결되어 있고, B 칸이 C 칸에 연결되어 있습니다. 그것은 직선입니다.
결함: 현실 세계는 복잡합니다. 누군가가 특정 국가의 시민인지 알기 위해서는 그 사람이 그곳에 '거주'하고, '직장'이 있으며, '배우자'도 그곳에 있다는 세 가지 조건이 모두 필요할 수도 있습니다. 단순한 "기차" 형태의 사실들은 이러한 복잡성을 담아낼 수 없습니다. 이는 마치 거미줄을 오직 하나의 직선으로만 설명하려는 것과 같습니다.

새로운 문제 (탐색의 악몽):
만약 기존의 방식으로 이러한 복잡한 웹 형태의 규칙(가지가 뻗어 나오거나 루프가 있는 형태)을 찾으려 한다면, 그것은 매 초마다 기하급수적으로 커지는 건초더미 속에서 특정 바늘을 찾는 것과 같습니다. 너무 많은 가능성을 하나하나 확인해야 하기 때문에 컴퓨터는 길을 잃게 됩니다.

새로운 문제 ("블랙박스" 학습):
최근 확산 모델(Diffusion Models)(DALL-E와 같은 이미지 생성 기술의 기반)이라는 AI 모델들이 복잡한 구조를 만드는 데 매우 능숙해졌습니다. 하지만 이들은 보통 이미지나 데이터 포인트를 완벽하게 "재구성"하는 방식으로 학습합니다.

불일치: 규칙 마이닝(rule mining)에서 우리는 규칙이 시각적으로 얼마나 "완벽한가"를 신경 쓰는 것이 아니라, 그 규칙이 논리적으로 참인가 그리고 유용한가를 중요하게 여깁니다. 이미지의 픽셀 차이를 측정하는 표준적인 학습 방식은 논리적 규칙이 좋은지 판단하는 데 적합하지 않습니다. 이는 요리사에게 고기를 맛보게 하는 대신, 스테이크 사진을 똑같이 그려내라고 가르치는 것과 같습니다.

해결책: GRiD

저자들은 복잡한 웹 형태의 규칙을 구축하는 똑똑한 2단계 설계자 역할을 하는 새로운 프레임워크인 GRiD를 제안합니다.

1단계: "견습생" 단계 (지도 학습 기반 사전 학습)

AI가 창의력을 발휘하기 전에, 먼저 기초적인 구성 요소를 배워야 합니다.

비유: 견습 건축가에게 기존의 유효한 건축 구조물(지식 그래프의 서브그래프) 사진 수천 장을 주는 것과 같습니다. 아직 무언가를 발명할 필요는 없습니다. 그저 "벽", "보(beam)", "지붕"이 올바르게 맞물렸을 때 어떤 모습인지 배우는 과정입니다.
GRiD가 하는 일: 이 모델은 "디노이징(denoising, 잡음 제거)" 과정을 사용합니다. 유효한 규칙을 가져와서 이를 뒤섞고(노이즈 추가), 다시 원래의 상태로 되돌리는 법을 가르칩니다. 이를 통해 AI는 아직 그것이 '최선의' 규칙인지 따지기 전에, 규칙이 어떻게 구축되는지에 대한 구조적 패턴을 배웁니다.

2단계: "마스터 셰프" 단계 (강화 학습)

이제 AI는 구조를 만드는 법을 배웠습니다. 이제 어떤 구조가 실제로 퍼즐을 푸는 데 '좋은' 것인지 배워야 합니다.

비유: 견습생은 이제 요리사가 되었습니다. 스테이크를 요리할 수는 있지만, 그 스테이크가 맛있는지는 별개의 문제입니다. 논문은 일반적인 요리 수업이 "맛"을 가르쳐주지 않는다고 말합니다. 그래서 GRiD는 **강화 학습(Reinforcement Learning, RL)**을 사용합니다.
작동 방식: AI가 규칙을 생성합니다(스테이크를 요리합니다). 그러면 "심판"(보상 시스템)이 그 맛을 봅니다. 심판은 사진을 보는 것이 아니라 논리를 체크합니다: "이 규칙이 실제로 누락된 사실을 예측하는 데 도움이 되는가? 확신이 있는가? 충분한 범위를 다루는가?"
보상: 규칙이 좋으면 AI는 "금메달(긍정적 보상)"을 받습니다. 규칙이 나쁘면 "엄지 아래로(부정적 피드백)"를 받습니다. AI는 더 많은 금메달을 얻기 위해 자신의 전략을 조정합니다. 이를 통해 AI는 단순히 데이터의 형태가 아니라 논리의 품질로부터 직접 학습할 수 있습니다.

실제 적용 방식

입력: 당신은 AI에게 "나는 '시민권' 관계에 대한 규칙을 찾고 싶다"라고 말합니다.
생성: AI는 빈 노이즈 캔버스에서 시작합니다. 단계별로 연결과 노드를 추가하며 천천히 "노이즈를 제거(denoise)"해 나가는데, 이때 2단계에서 배운 "금메달"의 안내를 따릅니다.
출력: AI는 복잡한 웹 형태의 규칙을 만들어냅니다.
- 예시: 단순히 "거주한다 -> 시민이다"가 아니라, "거주한다 AND 직장이 있다 AND 배우자가 그곳에 거주한다 -> 시민이다"와 같은 규칙을 생성할 수 있습니다.
결과: 이렇게 만들어진 복잡한 규칙들은 거대한 퍼즐(지식 그래프)의 빈 조각들을 채우는 데 사용됩니다.

결과: 왜 중요한가

이 논문은 6개의 서로 다른 데이터셋(가계도부터 의료 데이터베이스, 영화 배우 데이터까지)을 통해 테스트를 진행했습니다.

더 높은 정확도: GRiD는 누락된 사실을 예측하는 데 있어 거의 모든 다른 방법보다 뛰어난 성능을 보였습니다.
"콤보" 효과: 가장 흥สนใจ로운 발견은 사슬형 규칙(단순한 선)과 웹형 규칙(복잡한 웹)이 함께 작동할 때 가장 효과적이라는 점이었습니다.
- 비유: 사슬형 규칙을 식사의 "기본 반찬"이라고 생각하면 됩니다. 믿음직하며 대부분의 영역을 커버합니다. 웹형 규칙은 "매콤한 양념"입니다. 모든 것을 다루지는 못하지만, 단순한 규칙이 실패하는 까다롭고 모호한 사례들을 해결하는 데 필요한 특유의 풍미를 더해줍니다.
효율성: 이러한 복잡한 규칙을 찾는 것이 계산적으로 매우 무거워 보이지만, GRiD는 모든 가능성을 일일이 검색하는 대신 직접 생성하기 때문에 놀라울 정도로 빠르고 효율적입니다.

요약

GRiD는 컴퓨터가 복잡하고 다면적인 논리 규칙을 찾는 법을 가르치는 새로운 방법입니다. 이는 확산 모델의 구조적 학습(유효한 모양을 배우는 것)과 비디오 게임의 피드백 루프(승리하는 법을 배우는 것)를 결합합니다. 이를 통해 단순한 직선형 규칙이 그동안 어려움을 겪었던 복잡한 추론 퍼즐을 해결할 수 있게 해줍니다.

기술 요약: 확산 모델(Diffusion Models)을 통한 지식 그래프 추론용 그래프 형태 규칙 생성

1. 문제 정의

지식 그래프(Knowledge Graph, KG) 추론은 누락된 사실을 추론하기 위해 해석 가능한 논리적 규칙에 크게 의존합니다. 그러나 기존의 규칙 마이닝 방식은 다음과 같은 두 가지 주요 한계점에 직면해 있습니다:

구조적 제한: 현재의 접근 방식은 주로 체인 형태의 규칙(선형적인 관계의 시퀀스)에 집중되어 있습니다. 이러한 구조는 효율적이기는 하지만, 복잡한 KG 스키마에서 발견되는 순환(cycle), 분기(branch), 중첩된 제약 조건과 같은 더 풍부한 관계 패턴을 포착하지 못합니다. 이는 공동 다중 관계 제약이 필요한 시나리오에서 모호한 예측을 초래합니다.
계산적 병목 현상: 규칙 발견을 일반적인 그래프 형태의 규칙(규칙의 본체가 유향 그래프를 형성하는 경우)으로 확장하면, 탐색 공간이 조합 폭발( $O(|R|^L)$ 인 체인 방식과 비교하여 $O((L|R|)^L)$ )을 일으킵니다. 전통적인 탐색 기반 패러다임은 이러한 지수적 복잡성을 극복하는 데 어려움을 겪습니다.
생성 모델의 불일치: 확산 모델은 다른 도메인에서는 성공을 거두었으나, 규칙 마이닝에 직접 적용하기는 어렵습니다. 표준 확산 모델 훈련은 미분 가능한 재구성 손실(reconstruction loss)을 최적화하는 반면, 규칙의 품질은 비미분적인 이산적 지표(예: 신뢰도(confidence), 커버리지(coverage), PCA 신뢰도)를 사용하여 평가됩니다. 이는 훈련 목적 함수와 고품질 규칙 생성이라는 의미론적 목표 사이에 불일치를 발생시킵니다.

2. 방법론: GRiD 프레임워크

저자들은 GRiD(Generating Graph-like Rules with Diffusion)를 제안합니다. 이는 규칙 발견을 조건부 이산 생성 과정(conditional discrete generative process)으로 재정의한 프레임워크입니다. GRiD는 이산 탐색과 비미분적 지표의 문제를 해결하기 위해 2단계 훈련 전략을 채택합니다.

2.1 이산 확산 정식화 (Discrete Diffusion Formulation)

GRiD는 규칙의 본체를 $A \in \{0, 1, \dots, |R|, \emptyset\}^{S \times S}$ 인 유향 인접 행렬로 모델링합니다. 여기서 $S$ 는 최대 노드 수이고 $R$ 은 관계 집합입니다.

조건화(Conditioning): 생성은 타겟 헤드 관계 $r_h$ 와 확산 타임스텝 $t$ 에 따라 조건화됩니다.
순방향 과정(Forward Process): 깨끗한 규칙 행렬 $A_0$ 는 범주형 마르코프 전이 과정(D3PM 프레임워크)을 통해 노이즈 $A_T$ 로 점진적으로 오염됩니다. 이때 에지는 유지되거나 모든 관계 유형으로부터 균등하게 재샘플링됩니다.
역방향 과정(Reverse Process): 그래프 트랜스포머 디노이징 네트워크 $f_\theta$ 는 FiLM(Feature-wise Linear Modulation)을 통해 타겟 관계와 타임스텝을 조건으로 하여 노이즈로부터 깨끗한 행렬을 재구성하는 법을 학습합니다.

2.2 2단계 훈련 전략

규칙 품질 지표의 비미분성을 해결하기 위해, GRiD는 지도 학습(SL)과 강화 학습(RL)을 통합합니다.

단계 A: 지도 학습 사전 훈련 (Supervised Pre-training, SL):
- 목표: 구조적 사전 지식(structural priors)을 학습하고 웜 스타트(warm start)를 제공합니다.
- 방법: 모델은 KG 메타 그래프에서 샘플링된 서브그래프를 재구성하도록 훈련됩니다. 목적 함수는 구조적 재구성을 위한 가중치 적용 교차 엔트로피 손실과, (커버리지 및 신뢰도에 기반한) 스칼라 품질 점수를 예측하는 보조 손실을 결합합니다. 이를 통해 직접적인 이산 지표 최적화 없이도 학습된 표현을 규칙 품질 신호와 정렬합니다.
단계 B: 강화 학습 미세 조정 (Reinforcement Learning, RL Fine-tuning):
- 목표: 비미분적인 규칙 품질 지표를 직접 최적화합니다.
- 방법: 디노이징 과정을 디노이징 네트워크가 확률적 정책(stochastic policy) 역할을 하는 마르코프 결정 과정(MDP)으로 프레임화합니다.
- 보상 신호: 완전한 규칙이 생성되면, 커버리지(Coverage), 신뢰도(Confidence), PCA 신뢰도의 기하 평균을 계산하여 보상을 산출합니다.
- 최적화: 모델은 분산을 최소화하고 기대 에피소드 수준 보상을 최대화하기 위해 베이스라인을 포함한 REINFORCE 알고리즘을 사용하여 미세 조정됩니다. 탐색을 장려하기 위해 엔트로피 정규화가 사용됩니다.

2.3 추론 파이프라인

추론 단계에서 모델은 노이즈가 섞인 인접 행렬로부터 시작하여 반복적인 조건부 디노이징을 수행함으로써 이산적인 그래프 형태의 규칙 본체를 생성합니다. 생성된 그래프는 논리적 규칙(헤드 및 테일 변수 식별)으로 파싱된 후 KG 구조적 제약 조건에 따라 필터링됩니다.

3. 주요 기여

프레임워크 혁신: 규칙 발견을 반복적인 조합 탐색에서 조건부 이산 확산 과정으로 전환하여, 복잡한 그래프 형태의 구조를 생성할 수 있게 하는 GRiD를 제 제안하였습니다.
훈련 전략: 구조적 패턴 인식을 위한 SL 사전 훈련과 비미분적 규칙 품질 지표에 생성 과정을 정렬하기 위한 RL 미세 조정을 결합한 2단계 훈련 파이프라인을 도입했습니다.
실증적 검증: 6개의 벤치마크 데이터셋(FB15K-237, YAGO3-10 및 도메인 특화 데이터셋 포함)에 대한 광범한 실험을 통해 GRiD가 지식 그래프 완성(KGC) 작업에서 경쟁력 있는 성능을 달음을 입증했습니다.
규칙 유형에 대한 통찰: 그래프 형태의 규칙이 체인 형태의 규칙을 보완한다는 것을 확인하는 절제 연구(Ablation studies)를 수행했습니다. 체인 형태의 규칙이 지배적인 논리적 정규성을 포착하는 반면, 그래프 형태의 규칙은 융합 가중치(fusion weight)가 낮을 때(약 0.1~0.2) 복잡한 스키마에서 필수적인 모호성 해소를 제공합니다.

4. 실험 결과

성능: GRiD는 대부분의 기존 규칙 기반 베이스라인(예: AnyBURL, AMIE, Neural-LP, RNNLogic)보다 우수한 성능을 보이며, 6개 데이터셋 전반에서 임베딩 기반 및 GNN 기반 방식과 대등한 경쟁력을 유지합니다. 특히, 전통적인 규칙 기반 방식이 확장성 문제에 직면하기 쉬운 대규모 KG에서 최고 또는 차석의 결과를 달성했습니다.
절제 연구 결과:
- 그래프 vs 체인: 그래프 형태와 체인 형태의 규칙을 결합하는 것이 각각 단독으로 사용하는 것보다 일관되게 높은 성능을 보여, 두 유형의 상호 보완성을 입증했습니다.
- RL의 필요성: RL 미세 조정은 SL 전용 사전 훈련에 비해 지표가 약 10% 개선됨을 보여주며, 규칙 품질을 위한 직접적인 최적화의 필요성을 증명했습니다.
- 그래프 크기: 최대 그래프 크기 $S=6$ 노드면 복잡한 KG에 충분하며, 이는 표현력과 계산 효율성 사이의 균형을 맞춥니다.
- 융합 가중치: 그래프 형태의 규칙이 최종 점수 산출 시 작고 통제된 비율(10-20%)로 기여할 때 최적의 성능을 달성하며, 이는 지배적인 추론 패러다임이라기보다 보완적인 신호로서 작동함을 의미합니다.

5. 의의 및 주장

본 논문은 GRiD가 확산 모델의 생성 능력을 활용함으로써 그래프 형태의 규칙을 찾는 근본적인 병목 현상을 해결한다고 주장합니다. RL 미세 조정을 통해 이산적 규칙 품질 지표와 연속적 생성 모델 사이의 간극을 성공적으로 메움으로써, 본 프레임워크는 기존의 마이닝 방식으로는 접근할 수 없었던 복잡한 관계 패턴(순환, 분기)을 포착하는 그래프 형태의 규칙을 효율적으로 발견할 수 있게 합니다.

저자들은 그래프 형태의 규칙이 체인 형태의 규칙을 대체하는 것이 아니라, 풍부하고 복잡한 스키마를 가진 KG에서 모호성을 해결하는 중요한 보완 메커니즘 역할을 한다고 강조합니다. 이 연구는 철저한 탐색에서 학습 가능한 최적화 절차로의 전환을 시사합니다. 향후 연구로는 샘플링 편향을 완화하기 위해 밑바닥 KG 분포로부터 직접 규칙을 생성하는 방법과 더 정밀한 구조적 평가 지표를 개발하는 방안을 탐구할 예정입니다.