Relations Are Channels: Knowledge Graph Embedding via Kraus Decompositions

Resumo Técnico: Relações São Canais: Incorporação de Grafos de Conhecimento via Decomposições de Kraus

Declaração do Problema
Os modelos de Incorporação de Grafos de Conhecimento (KGE) visam representar entidades e relações em espaços vetoriais contínuos para facilitar tarefas como previsão de links. As abordagens existentes geralmente se enquadram em quatro famílias: modelos de operador único (e.g., TransE, RotatE, GoldE), modelos de múltiplos operadores (e.g., NTN), arquiteturas neurais não lineares (e.g., ConvE, R-GCN) e modelos de distribuição probabilística (e.g., KG2E). Os autores identificam uma lacuna fundamental em todas essas famílias: nenhuma deriva a estrutura matemática de um operador de relação a partir de primeiros princípios. Especificamente, os modelos de operador único sofrem de um gargalo estrutural onde não podem representar exatamente relações $N$-para-$N$ (colapsando múltiplos caudas válidos para um único ponto), enquanto os modelos de múltiplos operadores e neurais frequentemente carecem de garantias teóricas quanto à preservação de informação, composicionalidade ou à relação entre capacidade do modelo e complexidade relacional.

Metodologia
O artigo propõe um quadro teórico fundamentado na teoria da informação quântica, especificamente o teorema da representação de Kraus, para definir a estrutura necessária de um operador de relação principista.

1. Representação de Entidade como Matrizes de Densidade:
   Em vez de representar entidades como vetores, o modelo representa cada entidade como uma matriz de densidade $\rho \in S(\mathbb{R}^d)$, uma matriz simétrica semidefinida positiva com traço $\le 1$. Isso permite a representação de incerteza e estrutura multifacetada via posto da matriz, onde entidades bem atestadas convergem naturalmente para matrizes de baixo posto e as ambíguas mantêm posto mais alto.

2. Derivação Axiomática de Operadores de Relação:
   Os autores postulam três axiomas estruturais que qualquer operador de relação principista $L(r)$ deve satisfazer:

   • Linearidade: O operador deve ser linear nas representações de entidade.
   • Preservação de Traço: O operador deve preservar a massa de probabilidade total (traço) da entidade, garantindo que nenhuma informação seja perdida ou inflada.
   • Positividade Completa: O operador deve preservar a validade do estado conjunto quando aplicado a uma entidade dentro de um contexto correlacionado maior (e.g., uma vizinhança relacional).

   Pelo teorema da representação de Kraus, esses três axiomas caracterizam o operador como um canal de Kraus. Consequentemente, o operador de relação é definido como:
   $$L(r)(\rho) = \sum_{i=1}^{\kappa} K_i^{(r)} \rho (K_i^{(r)})^\top$$
   sujeito à restrição de completude: $\sum_{i=1}^{\kappa} (K_i^{(r)})^\top K_i^{(r)} = I$. Aqui, $\kappa$ é o posto de Kraus, representando o número de caminhos concorrentes através dos quais a relação mapeia uma cabeça para uma cauda.

3. Generalização para Geometrias Não Euclidianas:
   O quadro é estendido para geometrias métricas arbitrárias (euclidiana, elíptica, hiperbólica, variedades produto) definidas por um produto interno quadrático $\langle \cdot, \cdot \rangle_w$. Isso produz canais $w$-Kraus, onde a restrição de completude se adapta à geometria (e.g., condições $J$-unitárias para espaços hiperbólicos).

4. Instanciação do Modelo (KRAUSKGE):

   • Parametrização: As entidades são parametrizadas via matrizes triangulares inferiores para garantir semidefinição positiva e normalização de traço por construção. Os operadores de relação são parametrizados usando a transformada de Cayley de uma matriz antissimétrica para impor a restrição de ortogonalidade (completude) sem etapas de projeção.
   • Pontuação: A plausibilidade de uma tripla $(h, r, t)$ é pontuada via a sobreposição de Hilbert-Schmidt entre a distribuição de cauda prevista e a cauda observada.
   • Composição: Um resultado teórico chave é que a composição de dois canais de Kraus é, ela mesma, um canal de Kraus válido. Isso permite raciocínio exato de $k$ saltos sem codificadores de caminho auxiliares ou renormalização.

Principais Contribuições

• Caracterização Axiomática: O artigo estabelece que linearidade, preservação de traço e positividade completa são as condições necessárias para operadores de relação, caracterizando-os unicamente como canais de Kraus.
• Modelo KRAUSKGE: Um modelo concreto e treinável que lida naturalmente com relações $1$-para-$N$ e $N$-para-$N$ através de operadores de múltiplos caminhos ($\kappa > 1$), enquanto elimina a necessidade de restrições de norma externas nas entidades.
• Medida de Complexidade Teórica: Os autores introduzem o posto de Kraus como a primeira medida de complexidade por relação fundamentada teoricamente em KGE. Eles provam um limite inferior: $\kappa(r) \ge \text{posto}(M_r)/d$, onde $M_r$ é a matriz de relação empírica. Isso implica que relações com alta dispersão (alto posto de matriz) exigem estritamente $\kappa > 1$.
• Fechamento de Composição: O quadro fornece uma garantia teórica de que cadeias de raciocínio de múltiplos saltos são válidas sem erros de aproximação, removendo a necessidade de codificadores de caminho explícitos usados em trabalhos anteriores.
• Recuperação de Modelos Existentes: A maioria dos modelos KGE baseados em operadores existentes (e.g., RotatE, GoldE, DistMult) é mostrada como casos especiais de KRAUSKGE com $\kappa = 1$ sob escolhas e restrições específicas de incorporação.

Resultados Experimentais
O modelo foi avaliado em benchmarks padrão (FB15k-237, WN18RR, YAGO3-10, NELL-995):

• Previsão de Links: O KRAUSKGE com $\kappa \ge 4$ superou consistentemente bases fortes (incluindo GoldE e ConvE) no FB15k-237. Os ganhos de desempenho não foram uniformes; aumentaram monotonicamente com a complexidade da relação. Especificamente, a lacuna sobre as bases cresceu de 1,1 pontos de MRR em relações $1$-para-$1$ para 6,0 pontos em relações $N$-para-$N$.
• Correlação de Posto de Kraus: O posto de Kraus efetivo aprendido ($\kappa_{eff}$) mostrou uma forte correlação positiva ($\rho = 0,71$) com a dispersão empírica das relações, validando a medida de complexidade teórica.
• Raciocínio Multi-salto: Em divisões de consulta de 2 saltos e 3 saltos, o KRAUSKGE alcançou resultados state-of-the-art sem usar qualquer codificador de caminho auxiliar, superando modelos de raciocínio baseados em RNN, RL e GNN.
• Ablação de Geometria: Variantes usando geometrias não euclidianas (elíptica, hiperbólica, variedades produto) melhoraram ainda mais o desempenho, com a geometria de variedade produto produzindo os resultados gerais mais fortes.

Significado e Alegações
O artigo alega uma reorientação teórica do campo KGE. Em vez de tratar a escolha da arquitetura do operador como uma decisão de design empírica, os autores argumentam que a estrutura do operador é uma consequência derivável de princípios fundamentais (linearidade, preservação de massa e consistência composicional).

• O trabalho muda a questão de "qual operador performa melhor?" para "qual estrutura é matematicamente necessária?".
• Demonstra que a expressividade de múltiplos caminhos, o fechamento de composição e normas de entidade limitadas são corolários estruturais dos axiomas, não recursos projetados.
• Os autores posicionam o KRAUSKGE não como um modelo final, mas como um quadro que fornece uma fundação principista para entender a complexidade relacional e oferece uma nova ferramenta de diagnóstico (posto de Kraus) para auditoria de relações.
• O artigo reconhece limitações, incluindo o custo aumentado de parâmetros (escalando como $O(\kappa^2 d^2)$) e o fato de que o limite inferior de posto é uma condição necessária, mas nem sempre apertada na prática. Também nota que operadores aditivos no estilo TransE ficam fora deste quadro linear.