완전한 KG 위 불일치 탐지를 위한
심볼릭 추론 — KompaRe

비교 추론은 점별(단일 주장) 팩트체킹 대비 고유한 강점을 지닌다. 멀티모달 가짜뉴스 탐지처럼 단일 주장 검증만으로는 불충분한 실제 상황에서, 비교 추론은 입력 단서들에 대한 더 완전한 그림을 제공하여 점별 접근으로는 보이지 않는 미묘한 패턴(불일치)을 발견하게 한다. 각 주장이 개별적으로는 일관되더라도, 두 주장을 동시에 검증하면 결과가 불일치할 수 있다.

이 장은 비교 추론 문제를 다루며, 쌍별(pairwise) 비교 추론과 집합적(collective) 비교 추론의 두 문제에 집중한다. 배경 지식그래프의 정보에 따라 입력 단서들 사이의 공통성과 불일치를 드러내기 위해 그래프 커널을 활용하고, 두 가지 알고리즘을 제안하여 효과를 입증한다. 비교 추론의 공통 빌딩 블록은 주어진 단서(트리플 또는 그 일부)의 의미 맥락을 요약하는 작은 연결 서브그래프인 지식 세그먼트(knowledge segment)다. 이를 기반으로 쌍별·집합적 추론을 가능하게 하는 핵심 알고리즘을 제시하며, 핵심 아이디어는 지식 세그먼트의 구조와 의미 정보로 모호한 모순(vague contradiction)을 발견하는 것이다.

복수의 단서가 주어졌을 때 비교 추론의 목표는 그들 사이의 공통성 그리고/또는 불일치의 추론이다. 주어진 정보가 단서 쌍이면 두 단서의 정합 여부를 판단하는 쌍별 비교 추론(쌍별 팩트체킹), 연결된 질의 그래프이면 그래프 내부의 불일치를 탐지하는 집합적 비교 추론(집합적 팩트체킹)이라 부른다.

비교 추론을 위해서는 지식그래프의 배경 정보 활용이 중요하다. 각 입력 단서의 의미를 가장 잘 표현하는 서브그래프를 찾을 수 있다면 숨은 충돌의 탐지가 쉬워진다. 이상적으로 이 서브그래프는 단서와 관련된 지식그래프 내의 의미 있는/중요한 개체와 관계를 모두 담아야 한다.

4.3.1 술어-술어 유사도 — TF-IDF 기반

핵심 아이디어는 지식그래프의 각 트리플과 그 인접 이웃 트리플들을 하나의 문서처럼 취급하고, TF-IDF 유사 가중 전략으로 술어 유사도를 계산하는 것이다. 예컨대 술어 receiveDegreeFrom의 이웃 술어로 major와 graduateFrom이 있을 수 있으며, 이들은 서로 높은 유사도를 가져야 한다. 지식그래프로 술어들의 공출현(co-occurrence) 행렬을 만들고 다음과 같이 계산한다.

4.3.2 에지 특정 지식 세그먼트

주어진 에지(트리플)의 의미 맥락을 가장 잘 특징짓는 지식 세그먼트를 찾는다. 가중 그래프용 연결 서브그래프 추출 방법으로는 재시작 랜덤워크 기반 근사 서브그래프[143], 최대 네트워크 유량[68], 더 밀집한 국소 그래프 분할[45] 등이 있다. 이 장은 지식그래프를 가중 그래프로 변환한 뒤, 질의 에지의 주어에서 목적어까지의 k-단순 최단 경로[68]를 찾아 지식 세그먼트로 삼는다.

4.3.3 서브그래프 특정 지식 세그먼트

에지 특정 추출의 아이디어를 따라, 주어진 서브그래프의 각 에지마다 지식 세그먼트를 추출하고, 모든 에지 특정 지식 세그먼트를 담은 그래프를 서브그래프 특정 지식 세그먼트라 부른다 — 즉 입력 질의 서브그래프의 에지당 하나씩, 상호 연결된 다수의 에지 특정 지식 세그먼트로 구성된다. 이는 질의 그래프 각 에지의 의미와 에지들 사이 관계의 의미를 모두 포함하는 더 풍부한 의미론을 제공한다.

4.4.1 쌍별 비교 추론 — 여섯 케이스 분류

두 단서 <s₁, p₁, o₁>와 <s₂, p₂, o₂>가 불일치하는지 알려면, 먼저 둘이 같은/유사한 사실을 가리키는지부터 판정해야 한다. 주어·술어·목적어의 일치 패턴에 따라 여섯 케이스로 나뉜다.

요약하면 — (1) 두 단서의 주어가 같고, (2) 술어가 서로 유사하거나 같으면 같은 사실을 가리키며, 나아가 목적어가 서로 무관한 두 개체라면 두 단서가 불일치할 가능성이 높다. 이 관찰에 기반하여 쌍별 비교 추론은 세 단계로 진행된다.

4.4.2 집합적 비교 추론 — 라인 그래프 대조

집합적 비교 추론은 상호 연결된 에지/트리플들로 이뤄진 질의 그래프 내부의 공통성/불일치를 찾는다. 질의 그래프의 모든 에지 쌍에 쌍별 추론을 적용하는 소박한 방법은 계산적으로 비효율적이고 불충분하다 — 약하게 연관되거나 무관한 두 단서는 검사할 필요조차 없고(비효율), 어떤 미묘한 의미론적 불일치는 셋 이상의 지식 세그먼트를 집합적으로 추론해야만 식별되기 때문이다(불충분).

질의 그래프와 그 의미 매칭 서브그래프(서브그래프 특정 지식 세그먼트)를 두 개의 라인 그래프로 변환한다. L(Q)의 에지 가중치는 연결된 두 노드의 술어-술어 유사도이고, L(KS)의 에지 가중치는 Eq 4.1의 지식 세그먼트 유사도다. 의미 매칭 서브그래프가 원 질의 그래프의 좋은 표현이라면 L(Q)의 에지-에지 유사도는 L(KS)의 지식 세그먼트 유사도와 유사해야 한다 — 이것이 두 라인 그래프를 구축하는 근거다. 요소의 중요도는 L(Q)와 L(KS) 사이 거리에 대한 영향 함수로 측정한다 — 핵심 요소를 교란하면 거리 Loss = ||H₁ − H₂||²_F에 큰 영향을 준다고 가정한다 (H₁·H₂는 각각 L(Q)·L(KS)의 가중 인접 행렬).

핵심 요소를 모두 찾은 뒤, 이들에 따라 의미 매칭 서브그래프의 일관성을 검사한다 — 의미 매칭 서브그래프의 각 지식 세그먼트 쌍에 대해 핵심 요소 중첩률이 임계값(60%)을 넘으면 그 쌍의 일관성을 검사한다. 대응 트리플이 <s₁, p₁, o₁>·<s₂, p₂, o₂>라 할 때, 먼저 <s₁, isTypeOf, s₂> 또는 <s₂, isTypeOf, s₁>가 참인지 본다 — 둘 다 거짓이면 C3·C4에 속하지 않으므로 이 쌍은 건너뛴다. 그렇지 않으면 <o₁, isTypeOf, o₂> 또는 <o₂, isTypeOf, o₁>가 참인지 보고, 둘 다 거짓이면 질의 그래프에 집합적 불일치가 있다고 판정한다. 트리플 진위 검사에는 쌍별 추론과 동일한 방법(Eq 4.2의 전달 정보량)을 사용한다.

실험 설정

데이터 그래프 — Yago[134](트리플 12,430,705개, 개체 4,295,825개, 술어 39개)와 Covid-19(Gene·Disease·Chemical 세 개체 타입; 실험에서는 핵심 개체 55,434개·트리플 5,527,628개의 부분집합 사용). 베이스라인 — 팩트체킹 2종(Knowledge Linker(KL)[30], KGMiner[130]), 링크 예측 1종(Jaccard 계수[77]), 지식그래프 완성 1종(TransE[11] — 임베딩 차원 64, 마진 1, 학습률 0.01, 1,200 에폭). 환경 — Intel Core-i7 3.00GHz CPU·64GB 메모리 데스크톱, 시스템은 2020년 11월 17일 배포.

KompaRe 기본 기능

술어-술어 유사도 검증 — exports에 대한 상위 유사 술어는 imports, hasOfficialLanguage, dealsWith로 모두 exports에 관한 구체적 의미 정보를 제공하고, livesIn에 대해서는 wasBornIn, isCitizenOf, diedIn이 상위에 올라 모두 livesIn과 밀접하다. 제안한 TF-IDF 기반 방법이 술어 간 유사도를 효과적으로 측정함을 보여준다. 노드 특정 지식 세그먼트 — 질의 노드 Barack Obama에 대해 추출된 지식 세그먼트는 핵심 의미를 제공한다: Harvard Law School과 Columbia University 졸업, 아내는 Michelle Obama, 민주당 소속, 미국 상원의원 역임, Honolulu 출생. 노드 특정 지식 세그먼트가 질의 개체의 의미 맥락을 포착할 수 있음을 보여준다.

쌍별 비교 추론 (Table 4.2 — Yago, 10개 질의 집합 × 300)

각 양성 집합은 참 주장, 각 음성 집합은 거짓 주장을 기술하는 질의들로 구성된다 — 예컨대 "출생지" 집합에서 <Alan Turing, wasBornIn, Maida Vale> + <Alan Turing, wasBornIn, United Kingdom>은 양성 쌍, <Alan Turing, wasBornIn, Maida Vale> + <Alan Turing, wasBornIn, Canada>는 음성 쌍이다. 양성 질의는 지식그래프의 참 주장 샘플링으로, 음성 질의는 양성 질의의 주어 하나를 치환하여 생성한다. 정확도는 N/M(M: 전체 질의 수, N: 올바르게 분류된 질의 수)이다. 베이스라인은 쌍별 비교 추론용으로 설계되지 않았으므로, 쌍의 각 트리플을 검사해 하나라도 거짓이면 쌍을 거짓으로, 아니면 <o₁, isTypeOf, o₂>·<o₂, isTypeOf, o₁>의 진위를 추가 검사해 하나라도 일관이면 일관으로 처리한다.

KompaRe와 KGMiner[130]가 대부분의 경우 최고 정확도를 보이나, KompaRe가 평균 정확도 최고이면서 분산도 가장 낮다.

집합적 비교 추론 (Table 4.3 — Yago, 6개 질의 집합 × 300)

쌍별 질의(에지 2개)와 달리 집합적 질의는 에지 3개를 포함한다. 예컨대 "거주지" 집합에서 <Barack Obama, livesIn, Washington,D.C.>, <Barack Obama, is, United States Senate Barack Obama>, <United States Senate Barack Obama, livesIn, United States>는 양성 트라이어드, 마지막 목적어를 Canada로 바꾸면 음성 트라이어드다. 베이스라인 처리 방식은 쌍별 설정을 따른다.

Jaccard[77]는 모든 질의를 불일치로 분류하는 경향이 있어 분산이 가장 크고, TransE[11]는 분산은 최저지만 평균 정확도가 매우 낮다. KompaRe는 대부분의 경우 최고 정확도를 보이며, 평균 정확도 최고에 분산은 두 번째로 낮다.

Covid-19 집합적 추론 (Table 4.4)

Covid-19 관련 약물과 유전자/화학물질 간 연결을 담은 질의 중 노드 8개 미만인 질의를 양성으로 쓰고, 각 양성 질의에서 노드 하나를 무작위로 골라 데이터 그래프의 무작위 개체로 치환한 것을 음성 질의로 삼는다. 베이스라인은 질의 내 모든 에지를 검사해 하나라도 거짓이면 전체를 거짓으로 처리한다.

KompaRe는 양성·음성 모두에서 최고 정확도이며, 평균 정확도 최고·분산 최저를 기록한다.

KompaRe 효율성

지식 세그먼트 추출의 실행 시간은 기반 지식그래프의 크기에 의존하며, 세 유형 중 서브그래프 특정 지식 세그먼트가 가장 시간 소모적이지만 그 실행 시간은 지식그래프 노드 수에 대해 서브선형(sub-linear)으로 확장된다(질의 그래프 크기별 곡선 비교, Fig 4.4a). 비교 추론 자체의 실행 시간(쌍별, 그리고 에지 3·4·5개의 집합적 추론)은 대응하는 지식 세그먼트의 크기에만 의존하는데, 지식 세그먼트는 보통 노드가 몇 개에서 몇십 개 수준이다(Fig 4.4b).