복합 질의 응답FOL 질의를 부분그래프 매칭으로 찾는가, 임베딩 공간에서 계산하는가

“딥러닝 분야의 튜링상 수상자들은 어느 대학에서 일했는가?”라는 질문은 다음 1차 논리 질의로 표현된다.

일반적으로 FOL 질의는 목표 변수 V?와 여러 구속 변수 V1, …, Vk를 포함하며, 이들은 모두 KG의 엔티티다. 위 예에서 V?는 유일한 목표 변수이고 V는 존재 한정 기호에 구속된 유일한 구속 변수다. 질의의 목표는 목표 변수를 어떤 엔티티 집합으로 기저화했을 때 질의에 정의된 FOL이 만족되는 그 엔티티 집합을 찾는 것이다.

질의 정식화에 FOL을 활용하면 상당한 유연성을 얻는다. 여러 술어·변수·중첩 부질의를 개입시키는 더 표현력 있고 풍부한 질의를 허용하므로, 사용자가 다양한 사용 사례에서 더 넓은 범위의 질의를 정의할 수 있다. 따라서 FOL로 정식화된 복합 질의를 효과적으로 다루는 진전된 기법의 개발이 결정적이 된다. KG에서 복합 질의 응답의 두 가지 인기 있는 접근은 다음과 같다.

부분그래프 매칭 기반 방법은 복합 질의, 특히 논리곱 질의에 답하는 가장 전통적인 접근이다. 주어진 질의 패턴에 부합하는 부분그래프를 KG 안에서 식별하는 것을 목표로 한다.

4.2.1부분그래프 매칭 기반 방법 개관

부분그래프 매칭 기반 방법은 질의의 구조에 부합하는 부분그래프를 찾아 지식 그래프의 질의에 답한다. 일반적 절차는 다음 세 단계다.

4.2.2대표 방법 — Ullmann 알고리즘

부분그래프 매칭은 주어진 질의 그래프 Q와 정확히 부합하는 부분그래프를 KG G에서 찾는 데 집중한다. 이 접근은 논리곱 질의처럼 질의 그래프가 작고 잘 정의되어 있고, 사용자가 정확하고 모호하지 않은 결과를 기대할 때 흔히 사용된다.

가장 대표적인 접근은 Ullmann [2]이 제안한 알고리즘이다. 기본 방식은 깊이 우선 트리 탐색으로 Q의 정점을 G의 정점으로 사상하는 모든 가능한 사상을 열거하는 것이다. 탐색 트리의 레벨 l에 있는 각 노드는 Q의 노드 vi를 G의 서로 다른 정점에 사상한다. 탐색 트리의 뿌리에서 잎까지의 각 경로는 Q의 정점을 G의 정점으로 사상하는 완전한 사상을 나타낸다. Q와 G에서 노드 인접성을 보존하는 사상은 Q로부터 G의 부분그래프로의 매칭을 나타낸다. 그런 사상이 하나도 없으면 매칭은 존재하지 않는다.

이 장난감 예제는 Ullmann 알고리즘이 질의 그래프 Q에 부합하는 대상 그래프 G의 부분그래프 집합을 찾는 방식을 보여준다. 탐색 공간이 대상 그래프의 크기에 대해 지수적으로 증가하므로 부분그래프 매칭은 NP-완전이며, 대규모 그래프에서 부분그래프 매칭을 푸는 것은 실용적이지 않다.

4.2.3부분그래프 매칭 알고리즘의 질의 언어 — SPARQL

부분그래프 매칭 알고리즘은 KG에서 관련 정보를 효율적으로 탐색하는 데 사용될 수 있으며, SPARQL [3] 같은 다양한 질의 언어에 맞춰 맞춤화될 수 있다. SPARQL은 그래프 데이터베이스의 표준 질의 언어이자 프로토콜로 제안되었다. SPARQL은 데이터를 (head entity, relation, tail entity) 형태 트리플로 구성된 유향 그래프로 모델링한다. SQL이 관계형 데이터베이스에서 데이터를 조회·수정하게 하듯, SPARQL은 KG의 엔티티 사이 관계를 기술하는 질의를 지정함으로써 NoSQL 그래프 데이터베이스에 동일한 기능을 제공한다.

전형적인 SPARQL 질의는 결과 집합에 반환할 변수를 지정하는 SELECT 절과, 매칭할 엔티티 사이 관계 패턴을 지정하는 WHERE 절로 구성된다. WHERE 절은 KG의 엔티티 사이 관계를 지정하는 트리플 패턴으로 구성된다. 각 트리플 패턴은 변수 또는 특정 엔티티일 수 있는 세 요소로 이루어지며 그들 사이의 연결을 기술한다.

SELECT ?university
WHERE {
  ?person win Turing_Award .
  ?person field Deep_learning .
  ?person workAt ?university .
}

전반적으로 SPARQL은 KG의 엔티티 사이 복잡한 관계 패턴을 조회할 수 있는 강력하고 표현력 있는 질의 언어다. 그러나 SPARQL 질의는 특히 엔티티와 관계가 많은 대규모·복잡 KG를 조회할 때 실행 계산 비용이 클 수 있다.

4.2.4요약

부분그래프 매칭은 오랫동안 KG를 조회하고 엔티티 사이의 정교한 관계를 추출하는 효과적인 기법이었다. 기계 학습 접근과 달리 KG 학습을 요구하지 않으므로 학습 단계 없이 어떤 그래프에도 적용할 수 있다. 또한 결과가 원래 그래프 구조와 속성에 직접 대응하므로 흔히 손쉽게 해석된다. 특정 요구와 질의 패턴에 맞춰 맞춤화할 수 있고, 결과 정확도와 효율을 개선하기 위해 다른 기법과 결합할 수도 있다. 그러나 다음 단점을 보인다.

• 실세계 KG 처리의 어려움 — KG는 흔히 노이즈와 상당한 불완전성을 담으며, 이는 특히 변수가 많은 복합 질의에 답할 때 부분그래프 매칭 기반 방법의 성능에 악영향을 준다. 불완전한 KG는 빈 질의 결과를 낼 수 있고, 노이즈 트리플은 잘못된 답을 낼 수 있다.
• 확장성 — 복잡도가 통상 KG 크기에 대해 지수적으로 증가하므로 대규모 KG에 적용할 때 확장성 문제를 겪는다.
• 제한된 표현력 — 내재적으로 표현력이 제한되어 KG의 특정한 복잡한 의미 관계를 포착하기 어려울 수 있다. 예컨대 “유럽 국가를 한 번도 방문하지 않은 사람을 찾아라”라는 질의는 부정(“방문하지 않은”)과 전칭 한정(“한 번도”)을 포함한다. 부분그래프 매칭 기반 방법은 부정이나 전칭 한정을 다루도록 설계되지 않았으므로 이 질의를 처리하기 어렵다.

대규모 실세계 KG를 다루는 임베딩 기반 방법의 효과성에 착안해, FOL 형태의 복합 질의를 연속 벡터로 사상하는 논리 질의 임베딩 방법이 제안되었다. 부분그래프 매칭과 비교해 논리 질의 임베딩은 불완전하고 노이즈가 있는 KG를 다룰 수 있고, 훨씬 확장 가능하며, 더 넓은 범위의 FOL 질의를 수용할 수 있다.

4.3.1논리 질의 임베딩 방법 개관

질의 응답의 목표는 식 (4.1)의 변수 V?를 대체해 논리식을 만족시키는 특정 엔티티 집합, 즉 답 집합을 식별하는 것이다. 논리 질의 임베딩의 근본 착상은 논리 질의와 엔티티를 모두 저차원 벡터 공간으로 인코딩하여, 질의를 충족하는 엔티티가 임베딩 공간에서 질의에 가까이 놓이게 하는 것이다. 질의 q를 만족하는 엔티티 집합을 Sq로 표기하며 이것이 곧 질의 임베딩이다. 이 개념에 근거해 전형적인 논리 질의 임베딩 방법은 세 주요 구성 요소로 이루어진다.

4.3.1.1 모델링

표현 학습 기반 질의 응답 해법에는 몇 가지 핵심 개념이 있다. 첫째, 질의의 답은 엔티티의 집합이므로 질의를 표현한다는 것은 집합을 표현한다는 뜻이다. 이는 엔티티와 엔티티 집합의 임베딩 공간에 대한 세심한 설계를 요구한다. 둘째, FOL 질의는 원자 논리식의 논리 연산으로 정의되므로 (1) 부질의에 대응하는 집합인 원자 논리식의 임베딩을 정의하고, (2) 부질의 임베딩을 근거로 질의 임베딩을 재귀적으로 정의해야 한다. 전체 과정이 미분 가능해야 하므로 관계 투영과 논리 연산을 임베딩의 미분 가능한 함수로 다뤄야 한다. 셋째, 임베딩을 근거로 어떤 엔티티가 집합에 속할 가능성을 측정하는 점수 함수를 제공해야 한다.

각 FOL 질의는 부질의 위에 재귀적으로 정의되며, 가장 기본적인 것은 KG의 술어에 대응하는 원자 논리식(원자 질의)이다. 원자 질의가 엔티티를 포함하면(예: Win−1(Turing Award, V)) 그 엔티티는 앵커 노드로 취급되고, 관계가 그 엔티티를 변수 노드로 표기되는 잠재 엔티티 집합으로 투영한다. 원자 질의가 변수만 포함하면(예: University(V, V?)) 관계가 한 집합을 다른 집합으로 투영한다. 따라서 각 원자 질의는 그 자체로 하나의 집합이다.

부질의를 평가할 순서를 얻기 위해 계산 그래프가 구성된다. 노드는 엔티티 또는 변수이고 엣지는 투영과 논리 연산자다. 계산 그래프는 유향 비순환 그래프(DAG)이며 시작 노드(앵커 노드)는 엔티티다. 계산 흐름은 앵커 노드에서 시작해 한 홉, 두 홉 떨어진 노드로 점차 진행하여 목표 변수 노드에 도달한다.

점수 함수. 각 논리 질의 응답 방법은 엔티티 임베딩 e와 질의 임베딩 q 사이의 적합성을 평가하는 점수 함수 φ(q, e)를 설계한다. 점수가 높을수록 엔티티가 질의를 만족할 가능성이 크고 따라서 답에 대한 신뢰도가 높다. 점수 함수는 엔티티와 질의의 임베딩 공간 설계와 일관되어야 한다.

4.3.1.2 학습 과정

논리 질의 임베딩의 순방향 계산은 통상 세 단계로 구성된다. (1) 주어진 FOL 질의를 기본 논리 연산의 표현식으로 변환한다. 즉 DAG 그래프를 계산 그래프로 삼는다. (2) 논리 표현식을 순서대로 실행해 질의의 임베딩을 생성한다. 앵커 노드의 임베딩에서 출발해 투영 P와 논리곱 C 같은 논리 연산을 반복 적용한다. (3) 질의 임베딩과 엔티티 임베딩 사이의 점수 함수를 계산한다. 교차 엔트로피 손실이나 순위 기반 손실 같은 KG 완성 태스크의 손실 함수를 레이블된 질의-답 쌍을 근거로 정의할 수 있다.

4.3.2대표 방법

세 모델의 주된 차이는 엔티티·질의·논리 연산을 어떻게 표현할지에 대한 가정에 있다.

4.3.2.1 GQE — 점(point)으로서의 질의

GQE(Graph Query Embeddings) [4]는 저차원 임베딩 공간 안에서 논리 연산을 수행한 첫 시도다. 논리곱 질의만 고려한다. 논리곱 질의는 원자 논리식으로부터 논리곱(∧)과 존재 한정(∃)으로 구성되며 논리합(∨)·부정(¬)·전칭 한정(∀)은 사용하지 않는다. 따라서 미분 가능한 연산자 두 개, 투영 P와 논리곱 C만 필요하다. GQE에서 엔티티와 질의 모두 d차원 벡터와 결합된다(e, q ∈ Rd).

같은 엔티티 유형 t(예: 단백질, 약물)를 갖는 질의 임베딩 집합이 주어지면, 논리곱 연산은 임베딩 공간에서 딥 셋 교집합(deep set intersection)을 수행한다. NN은 신경망, ⊡는 순열 불변 함수(벡터 집합의 성분별 평균 또는 최소 등), Wt는 엔티티 유형 t에 특화된 변환 행렬이다. 논리곱 연산은 입력에 대해 순열 불변이므로 ⊡도 순열 불변이어야 한다.

질의 추론을 위해 GQE는 대응하는 계산 질의 그래프를 입력으로 받아 앵커 노드의 임베딩을 나가는 관계에 따라 투영한다. 질의 DAG에서 노드가 여러 들어오는 엣지를 가지면 교집합 연산으로 들어오는 정보를 집계한다. 이 과정을 질의의 목표 변수에 도달할 때까지 계속한다.

GQE의 경우 점수 함수 φ(q, e)가 [0, 1] 범위 값을 내므로 γ = 1로 설정된다. γ = 1은 점수 함수가 코사인 유사도와 같은 범위로 정규화되도록 보장한다. 학습 질의 q에 대해 이 손실을 계산하기 위해 GQE는 학습 데이터에서 양성 예 노드 e ∈ Sq와 음성 예 노드 e′ ∉ Sq를 균일하게 샘플링한다.

4.3.2.2 Query2Box — 박스(box)로서의 질의

GQE는 논리합 같은 다른 논리 연산을 고려하지 않고 논리곱 질의에만 집중한다. 또한 질의를 d차원 공간의 단일 점으로 모델링하므로 집합을 적절히 표현하기 어렵다. 이 한계를 해결하기 위해 Query2Box [5]는 ∃, ∧에 더해 ∨가 개입하는 더 일반적인 EPFO 논리 질의를 다룬다. 질의 답 집합을 박스로, 엔티티 임베딩을 점으로 모델링한다. 질의는 중심 벡터와 오프셋 벡터로 결정되는 박스 임베딩 q = (Cen(q), Off(q))로 표현된다.

Cen(q) ∈ Rd는 박스의 중심, Off(q) ∈ Rd≥0는 박스의 오프셋이다.

• 투영 (P) — 관계 임베딩을 또 다른 박스 임베딩 rk = (Cen(rk), Off(rk))로 정의하고, 관계 rk에 대응하는 투영을 Prk(q) = q + rk로 모델링한다. 중심이 이동하고 오프셋이 커진 새 박스를 준다.
• 논리곱 (C) — 질의 답 집합을 박스로 모델링하므로, 논리곱의 기본 착상은 박스 집합 안쪽에 놓이는 더 작은 박스를 생성하는 것이다. 박스 중심에 어텐션을 수행하고 시그모이드 함수로 박스 오프셋을 축소해 교집합을 계산한다.
• 논리합 (D) — 박스 임베딩은 벡터 공간 어디에나 놓일 수 있으므로 논리합(합집합) 결과는 단순한 박스가 아니다. 이를 해결하기 위해 Query2Box는 EPFO 질의를 DNF, 즉 논리곱 질의의 논리합으로 변환해 논리합 연산을 계산의 마지막 단계로 이동시킨다. 그러면 EPFO 질의는 DNF의 각 논리곱 질의마다 얻어진 개별 박스의 집합으로 표현되고(q = q1 ∨ ⋯ ∨ qn), 어느 박스든 그 최근접 이웃 엔티티를 집계해 질의에 답한다.

점수 함수. 엔티티 e가 질의의 답인지 판정하기 위해 질의 임베딩과 엔티티 임베딩 사이의 거리를 다음과 같이 정의한다. distoutside는 엔티티와 박스의 가장 가까운 모서리·변 사이의 거리(엔티티가 박스 안이면 0)이고, distinside는 그 최근접점과 박스 중심 사이의 거리다. 점수 함수 φ(q, e)는 거리 함수의 음수로 볼 수 있다.

Query2Box는 투영·논리곱·논리합의 세 논리 연산을 지원한다. 표현력을 개선하기 위해 NewLook [7]은 차집합 연산자로 부정을 지원하도록 Query2Box를 확장한다.

4.3.2.3 BetaE — 베타 분포로서의 질의

Query2Box는 집합을 점보다 박스로 표현하는 것이 우월함을 보였다. 박스는 부피를 갖고 교집합 연산이 자연스럽게 정의되기 때문이다. 그러나 박스 임베딩은 논리합과 부정을 다루기 어렵다. 이 연산들이 더 이상 박스가 아닌 기하 형태로 이어지기 때문이다. 부정 연산을 지원하고 불확실성을 모델링하기 위해 BetaE [6]는 엔티티와 질의 모두를 d개의 독립적인 베타 분포로 모델링한다.

각 엔티티는 집합의 특수 경우로 간주되며, 집합은 q = [(α1, β1), …, (αd, βd)]로 표현된다. 일반성을 잃지 않고 d = 1일 때로 정의를 설명한다.

논리곱은 베타 분포의 가중 보간으로 모델링된다. 입력 베타 임베딩 PDF의 가중 곱을 취해 교집합을 나타내는 분포를 계산한다.

교집합 분포의 형태는 파라미터가 Σ wiαi와 Σ wiβi인 또 다른 베타 분포다. 어텐션 가중치의 합이 1이므로 Σi(wiαi − wi) = Σi wiαi − 1이라는 사실을 이용하는 것이 증명의 요령이다.

부정 연산은 입력의 여집합을 나타내는 임베딩을 출력하는 것을 목표로 하므로 그 밀도 함수는 입력 밀도 함수의 반전이어야 한다. N(N([α, β])) = [α, β]임을 확인할 수 있으며, 이는 부정의 부정이 원래 집합이라는 성질을 보존한다. 논리합은 BetaE가 직접 모델링하기 더 어렵다. 대신 2.2.3절에서 소개한 드모르간 법칙에 따라 논리곱과 부정으로 논리합을 계산한다. BetaE는 FOL 질의를 완전히 지원하므로 임의의 FOL 질의에 대한 질의 임베딩을 학습할 수 있다.

BetaE는 Query2Box와 동일한 마진 기반 교차 엔트로피 손실(식 4.10)을 사용한다.

4.3.3요약

논리 질의 임베딩 방법의 유의미한 난관은 집합의 표현이다. 집합을 표현하는 방식이 임베딩 방법의 효과성과 효율성에 영향을 주므로 결정적인 역할을 한다. GQE는 집합을 저차원 공간의 단일 점으로 표현해 집합의 특성을 포착하는 데 제한적이다. Query2Box는 박스 임베딩으로 이 한계를 해결하지만 부정 연산을 표현할 때 어려움에 부딪힐 수 있다. 반면 BetaE는 집합을 임베딩 위의 베타 분포로 표현해 불확실성과 다양성을 효과적으로 모델링한다.

논리 질의 임베딩이 복합 질의 응답에서 훌륭한 성능을 보였음에도, 이 방법들은 KG 학습을 필요로 하며 레이블된 질의-답 쌍에 크게 의존한다. 연속 벡터 표현의 임시적(ad-hoc) 가정이 야기하는 내재적 근사 오차도 답의 품질에 영향을 줄 수 있다. 이는 임베딩 기반 함수가 논리 공리를 보존함을 이론적으로 보장하고 추가 학습 신호에 덜 의존하는 알고리즘을 요구한다.

KG의 복합 질의 응답은 1차 논리 형태의 질의에 대한 답을 조회하는 과정을 지칭한다. KG의 복합 질의는 여러 단계 또는 엔티티 사이의 여러 관계를 개입시킬 수 있으므로 답하기 어렵다. 예컨대 “딥러닝을 연구한 튜링상 수상자는 어느 대학에서 일했는가?”라는 질의는 연구자와 소속, 연구자와 연구 분야, 연구자와 상 사이의 여러 관계에 대한 추론을 개입시킨다.

논리 질의 임베딩의 지속적 진전에도 이 분야는 여전히 초기 단계다. 한 가지 문제는 기존 다수의 논리 질의 임베딩 모델이 사용하는 논리 연산이 논리 법칙을 만족함을 보장하지 않아 성능이 열등해진다는 점이다. 이 한계에 대응해 FuzzQE 모델이 벡터 공간에서 퍼지 논리로 논리 연산자를 정의하여 논리 법칙 만족을 보장하고 성능을 개선하는 최신 접근으로 도입되었다.

논리 질의 임베딩 방법의 해석 가능성 개선

FuzzQE는 벡터 공간에서 퍼지 논리로 논리 연산자를 정의해 논리 법칙 만족을 보장하고 논리 연산의 미분을 가능하게 하지만, 중간 임베딩이 인코딩하는 엔티티 집합을 해석하기는 어렵다. 이는 추론 과정을 사용자에게 불투명하게 남긴다.

해석 가능성을 개선하기 위해 GNN-QE [22]는 각 중간 변수에 대한 할당 집합을 산출하는 심볼릭 방법을 따른다. 구체적으로 복합 FOL 질의를 퍼지 집합 위의 표현식으로 분해해 중간 변수의 해석 가능성을 달성한다. 표현식의 각 기본 연산은 관계 투영 또는 논리 연산(논리곱·논리합·부정)이다. 관계 투영은 머리 엔티티의 퍼지 집합과 관계가 주어질 때 꼬리 엔티티의 퍼지 집합을 예측하는 그래프 신경망(GNN)이 되도록 설계된다.

KG 질의응답을 위한 대규모 언어 모델과의 결합

이 절에서 개괄한 모든 방법은 형식적 논리 질의를 입력으로 요구한다. 실용적으로 그런 질의를 정의하는 데는 인간 전문가의 상당한 노력이 필요할 수 있다. 최근 OpenAI의 GPT-4 같은 대규모 언어 모델(LLM)은 자연어 질의를 파싱하고 이해하는 데 뛰어난 역량을 보였다. LLM과 KG를 질의응답에 통합하면 사용자가 자연어로 질문하고 KG에서 답을 조회할 수 있어 더 사용자 친화적인 상호작용을 촉진한다. 자연어 질문과 구조화된 KG 사이의 간극을 메우기 위해 LLM을 활용한 최근 연구는 두 범주로 나뉜다.

KG를 활용하면 신뢰할 수 있는 정보의 출처를 제공할 수 있어 환각(hallucination) 관련 문제를 완화하는 데 매우 유용하다. LLM을 통합해 자연어 질의와 구조화된 KG 사이의 연결을 촉진하면 맥락을 인식하고 투명한 AI 시스템을 확립할 수 있다. 이 접근은 KG의 유리한 추론 역량을 생성 기반 질의응답 영역으로 확장하여 더 신뢰할 수 있는 응답으로 이어진다.