Relations Are Channels: Knowledge Graph Embedding via Kraus Decompositions

기술 요약: 관계는 채널이다: 크라우스 분해를 통한 지식 그래프 임베딩

문제 제기
지식 그래프 임베딩 (KGE) 모델은 링크 예측과 같은 작업을 용이하게 하기 위해 엔티티와 관계를 연속적인 벡터 공간에 표현하는 것을 목표로 합니다. 기존 접근법은 일반적으로 네 가지 계열로 분류됩니다: 단일 연산자 모델 (예: TransE, RotatE, GoldE), 다중 연산자 모델 (예: NTN), 비선형 신경 아키텍처 (예: ConvE, R-GCN), 그리고 확률적 분포 모델 (예: KG2E). 저자들은 이러한 계열 전반에 걸쳐 근본적인 격차가 있음을 식별했습니다. 즉, 어떤 모델도 관계 연산자의 수학적 구조를 첫 번째 원리 (first principles) 에서 유도하지 못한다는 점입니다. 구체적으로, 단일 연산자 모델은 여러 유효한 꼬리 (tails) 를 단일 점으로 축소하는 구조적 병목 현상으로 인해 $N$-to-$N$ 관계를 정확하게 표현하지 못하는 한계를 겪습니다. 반면, 다중 연산자 및 신경 모델은 정보 보존, 구성성 (compositionality), 또는 모델 용량과 관계 복잡성 간의 관계에 대한 이론적 보장이 종종 결여되어 있습니다.

방법론
본 논문은 양자 정보 이론, 특히 **크라우스 표현 정리 (Kraus representation theorem)**에 기반한 이론적 프레임워크를 제안하여 원칙적인 관계 연산자의 필수 구조를 정의합니다.

1. 엔티티 표현을 위한 밀도 행렬:
   엔티티를 벡터로 표현하는 대신, 본 모델은 각 엔티티를 $\rho \in S(\mathbb{R}^d)$인 밀도 행렬로 표현합니다. 이는 대칭 양의 준정부호 행렬이며, 대각합 (trace) 이 1 이하입니다. 이는 행렬의 랭크를 통해 불확실성과 다면적 구조를 표현할 수 있게 하며, 잘 입증된 엔티티는 자연스럽게 저랭크 행렬로 수렴하고 모호한 엔티티는 더 높은 랭크를 유지합니다.

2. 관계 연산자의 공리적 유도:
   저자들은 원칙적인 관계 연산자 $L(r)$이 반드시 만족해야 하는 세 가지 구조적 공리를 가정합니다:

   • 선형성: 연산자는 엔티티 표현에 대해 선형이어야 합니다.
   • 대각합 보존: 연산자는 엔티티의 총 확률 질량 (대각합) 을 보존하여 정보가 손실되거나 과장되지 않도록 해야 합니다.
   • 완전 양수성 (Complete Positivity): 연산자는 엔티티가 더 큰 상관 맥락 (예: 관계 이웃) 내에 적용될 때 결합 상태의 유효성을 보존해야 합니다.

   크라우스 표현 정리에 따라, 이 세 가지 공리는 연산자를 **크라우스 채널 (Kraus channel)**로 특징짓습니다. 결과적으로 관계 연산자는 다음과 같이 정의됩니다:
   $$L(r)(\rho) = \sum_{i=1}^{\kappa} K_i^{(r)} \rho (K_i^{(r)})^\top$$
   여기서 완전성 제약 조건은 $\sum_{i=1}^{\kappa} (K_i^{(r)})^\top K_i^{(r)} = I$입니다. 여기서 $\kappa$는 크라우스 랭크로, 관계가 헤드에서 꼬리로 매핑되는 동시 경로의 수를 나타냅니다.

3. 비유클리드 기하학으로의 일반화:
   본 프레임워크는 2 차 내적 $\langle \cdot, \cdot \rangle_w$로 정의된 임의의 메트릭 기하학 (유클리드, 타원, 쌍곡, 곱 다양체) 으로 확장됩니다. 이는 $w$-크라우스 채널을 산출하며, 여기서 완전성 제약 조건은 기하학에 맞게 적응됩니다 (예: 쌍곡 공간의 경우 $J$-유니터리 조건).

4. 모델 인스턴스 (KRAUSKGE):

   • 매개변수화: 엔티티는 양의 준정부호성과 대각합 정규화를 보장하기 위해 하삼각 행렬을 통해 매개변수화됩니다. 관계 연산자는 투영 단계 없이 직교성 (완전성) 제약 조건을 강제하기 위해 반대칭 행렬의 **케이리 변환 (Cayley transform)**을 사용하여 매개변수화됩니다.
   • 점수 부여: 삼중항 $(h, r, t)$의 타당성은 예측된 꼬리 분포와 관측된 꼬리 간의 힐베르트 - 슈미트 중첩 (overlap) 을 통해 점수화됩니다.
   • 구성: 중요한 이론적 결과는 두 크라우스 채널의 구성 자체가 유효한 크라우스 채널이라는 점입니다. 이는 보조 경로 인코더나 재정규화 없이 정확한 $k$-홉 추론을 가능하게 합니다.

주요 기여

• 공리적 특징화: 본 논문은 선형성, 대각합 보존, 완전 양수성이 관계 연산자에 대한 필수 조건이며, 이를 크라우스 채널로 유일하게 특징짓는다는 것을 확립합니다.
• KRAUSKGE 모델: 다중 경로 연산자 ($\kappa > 1$) 를 통해 $1$-to-$N$ 및 $N$-to-$N$ 관계를 자연스럽게 처리하면서 엔티티에 대한 외부 노름 제약을 제거하는 구체적이고 학습 가능한 모델을 제시합니다.
• 이론적 복잡성 측정: 저자들은 KGE 에서 최초로 이론적으로 근거된 관계별 복잡성 측정치인 크라우스 랭크를 도입합니다. 그들은 하한을 증명합니다: $\kappa(r) \ge \text{rank}(M_r)/d$. 여기서 $M_r$은 경험적 관계 행렬입니다. 이는 높은 팬아웃 (높은 행렬 랭크) 을 가진 관계가 엄격하게 $\kappa > 1$을 필요로 함을 의미합니다.
• 구성 폐쇄성: 본 프레임워크는 다중 홉 추론 체인이 근사 오차 없이 유효하다는 이론적 보장을 제공하며, 이전 연구에서 사용된 명시적 경로 인코더의 필요성을 제거합니다.
• 기존 모델의 복원: 대부분의 기존 연산자 기반 KGE 모델 (예: RotatE, GoldE, DistMult) 은 특정 임베딩 선택과 제약 조건 하에서 $\kappa = 1$인 KRAUSKGE 의 특수한 경우임이 입증됩니다.

실험 결과
본 모델은 표준 벤치마크 (FB15k-237, WN18RR, YAGO3-10, NELL-995) 에서 평가되었습니다:

• 링크 예측: $\kappa \ge 4$인 KRAUSKGE 는 FB15k-237 에서 GoldE 및 ConvE 를 포함한 강력한 베이스라인을 일관되게 능가했습니다. 성능 향상은 균일하지 않았으며, 관계 복잡성에 따라 단조 증가했습니다. 구체적으로, 베이스라인과의 격차는 $1$-to-$1$ 관계에서 MRR 1.1 포인트에서 $N$-to-$N$ 관계에서 6.0 포인트로 증가했습니다.
• 크라우스 랭크 상관관계: 학습된 유효 크라우스 랭크 ($\kappa_{eff}$) 는 관계의 경험적 팬아웃과 강한 양의 상관관계 ($\rho = 0.71$) 를 보여 이론적 복잡성 측정치를 검증했습니다.
• 다중 홉 추론: 2 홉 및 3 홉 쿼리 분할에서 KRAUSKGE 는 보조 경로 인코더를 사용하지 않고 최첨단 결과를 달성했으며, RNN 기반, RL 기반, GNN 기반 추론 모델을 능가했습니다.
• 기하학 제거 실험: 비유클리드 기하학 (타원, 쌍곡, 곱 다양체) 을 사용하는 변형 모델은 성능을 추가로 향상시켰으며, 곱 다양체 기하학이 가장 강력한 전체 결과를 산출했습니다.

의의 및 주장
본 논문은 KGE 분야의 이론적 재편성을 주장합니다. 저자들은 연산자 아키텍처의 선택을 경험적 설계 결정으로 취급하는 대신, 연산자 구조가 기본 원리 (선형성, 질량 보존, 구성적 일관성) 의 유도 가능한 결과라고 주장합니다.

• 이 연구는 "어떤 연산자가 가장 잘 수행하는가?"라는 질문을 "수학적으로 필요한 구조는 무엇인가?"라는 질문으로 전환합니다.
• 다중 경로 표현력, 구성 폐쇄성, 그리고 유계 엔티티 노름이 공리의 구조적 귀결이며, 설계된 기능이 아님을 입증합니다.
• 저자들은 KRAUSKGE 를 최종 모델이 아니라, 관계 복잡성을 이해하기 위한 원칙적인 기반을 제공하고 관계를 감사하기 위한 새로운 진단 도구 (크라우스 랭크) 를 제공하는 프레임워크로 위치시킵니다.
• 논문은 매개변수 비용 증가 ($O(\kappa^2 d^2)$로 스케일링) 와 실제에서 랭크 하한이 필요조건이지만 항상 엄격한 조건은 아니라는 점을 포함한 한계를 인정합니다. 또한 TransE 스타일의 가산 연산자는 이 선형 프레임워크 밖으로 떨어진다고 지적합니다.