Resumo Técnico: COREKG – Sumarização Personalizada Guiada por Coresets de Grafos de Conhecimento

1. Declaração do Problema

Grafos de Conhecimento (KGs) como Freebase, DBpedia e Wikidata tornaram-se centrais para aplicações como motores de busca, sistemas de recomendação e resposta a perguntas (QA). No entanto, sua escala massiva e alta conectividade impõem desafios significativos para consultas eficientes, visualização e raciocínio. Embora existam métodos gerais de sumarização de KGs para reduzir o tamanho dos dados, eles frequentemente focam na captura de padrões estruturais globais, resultando em resumos excessivamente generalizados que não atendem às necessidades específicas de informação de usuários individuais.

Abordagens personalizadas existentes, como GLIMPSE e iSummary, tentam adaptar resumos aos interesses do usuário, mas enfrentam limitações: o GLIMPSE assume históricos de consultas densos e carece de controle explícito sobre a esparsidade do resumo, enquanto o iSummary depende fortemente da cobertura da carga de trabalho agregada. Outros métodos, como PEGASUS e APEX2, utilizam heurísticas ou modelos de difusão de calor que podem carecer de garantias formais de aproximação ou lutar com registros de consultas esparsos e enviesados. Há uma necessidade de um framework que forneça sumarização personalizada de KG com garantias teóricas, eficiência computacional e robustez em diversos padrões de consultas de usuários, sem depender de dados históricos densos.

2. Metodologia

Os autores propõem o COREKG, um framework que adapta a teoria de coresets ao domínio dos Grafos de Conhecimento. Um coreset é um subconjunto pequeno e ponderado de dados que aproxima uma função de custo com limites de erro prováveis. O COREKG constrói um coreset personalizado para cada usuário amostrando triplos relevantes baseados em amostragem por importância baseada em sensibilidade.

2.1 Visão Geral do Framework

O pipeline do COREKG opera independentemente para cada usuário e consiste nas seguintes etapas:

1. Pré-processamento e Modelagem do Usuário:

   • Extração de Sementes: Cada usuário é modelado por um conjunto de "entidades semente" (nós de interesse direto) extraídas de seu histórico de consultas.
   • Filtragem de Consultas: O registro global de consultas é filtrado para reter apenas consultas que mencionam pelo menos uma das entidades semente do usuário, criando uma carga de trabalho de consultas específica do usuário.
   • Normalização: Consultas SPARQL são normalizadas (removendo duplicatas, expandindo prefixos) para garantir consistência semântica.

2. Cálculo da Pontuação de Sensibilidade:

   • Para um determinado usuário $u$ e sua carga de trabalho $Q$, a sensibilidade $s(t)$ de um triplo $t$ é calculada. Esta pontuação quantifica a importância do triplo para as consultas específicas do usuário.
   • Formalmente, $s(t) = \sum_{q \in Q} \frac{1}{|T_q|} \cdot \mathbb{I}[t \in T_q]$, onde $T_q$ é o conjunto de triplos relevantes para a consulta $q$, e $\mathbb{I}$ é uma função indicadora.
   • Triplos que aparecem frequentemente nas consultas de um usuário ou em consultas com pequenos conjuntos de respostas recebem pontuações de sensibilidade mais altas. Isso garante que a distribuição de amostragem seja adaptada ao comportamento individual do usuário, em vez de estatísticas globais.

3. Construção do Coreset (Amostragem e Ponderação):

   • Triplos são amostrados do grafo original $G$ de acordo com a distribuição de probabilidade $p(t) = \frac{s(t)}{S}$, onde $S$ é a sensibilidade total.
   • Cada triplo amostrado $t$ recebe um peso $w(t) = \frac{1}{m \cdot p(t)} = \frac{S}{m \cdot s(t)}$, onde $m$ é o tamanho da amostra. Esta ponderação corrige o viés de amostragem, garantindo que o custo esperado no coreset corresponda ao custo no grafo completo.
   • O resultado é um subgrafo ponderado (o coreset) que aproxima a utilidade do grafo completo para a carga de trabalho específica do usuário.

2.2 Garantias Teóricas

O artigo fornece um teorema formal (Teorema 4.1) que estabelece que o coreset construído $C$ aproxima o custo real do grafo completo $G$ dentro de um erro relativo limitado $\epsilon$ com alta probabilidade ($1-\delta$). O tamanho de amostra necessário $m$ depende do número de consultas $|Q|$ e dos limites de erro desejados, mas é independente do tamanho do grafo completo $|T|$.

3. Contribuições Principais

O artigo delineia quatro contribuições primárias:

• Framework COREKG: Uma abordagem guiada por coresets para sumarização personalizada de KG que adapta a teoria de coresets a dados de grafos, oferecendo garantias de aproximação prováveis e escalabilidade prática.
• Amostragem Baseada em Sensibilidade: Uma formulação que quantifica a relevância de triplos com base em cargas de trabalho de consultas específicas do usuário, garantindo robustez em diversos cenários de personalização.
• Limites Teóricos: Uma garantia de aproximação no pior caso para custos de cargas de trabalho específicas do usuário que é independente do tamanho do grafo completo, com todas as avaliações de consultas realizadas diretamente no coreset.
• Validação Empírica: Experimentos extensivos demonstrando que o COREKG supera as bases de comparação mais avançadas (GLIMPSE, PPR, iSummary, PEGASUS, APEX2) tanto na cobertura de consultas quanto na pontuação F1 em Freebase, DBpedia e Wikidata.

4. Resultados Experimentais

Os autores avaliaram o COREKG em três conjuntos de dados do mundo real (Freebase, DBpedia, Wikidata) usando cargas de trabalho de consultas SPARQL. A avaliação focou na Cobertura Estrutural (preservação de padrões de consulta) e na Pontuação F1 (precisão na resposta a consultas).

• Desempenho: O COREKG consistentemente alcançou pontuações F1 e cobertura mais altas do que todas as bases de comparação. Por exemplo, na DBpedia, o COREKG alcançou uma pontuação F1 de 58,64% e cobertura de 68,07%, superando significativamente o APEX2 (47,52% F1, 42,06% cobertura) e o iSummary (19,38% F1, 12,55% cobertura).
• Sensibilidade ao Orçamento: Através de orçamentos de resumo variados (de 1.000 a 100.000 triplos), o COREKG manteve desempenho superior. Enquanto outros métodos como o PEGASUS mostraram alta cobertura, mas pontuações F1 extremamente baixas (indicando baixa relevância), o COREKG equilibrou ambas as métricas efetivamente.
• Estudo de Ablação:
  • Amostragem Uniforme (COREKG-Uniforme): Substituir a amostragem por sensibilidade por amostragem aleatória uniforme resultou em desempenho próximo de zero, confirmando a necessidade de sensibilidade baseada em consultas.
  • Carga de Trabalho Global (COREKG-Global): Remover a condicionamento específico do usuário e usar uma carga de trabalho global degradou significativamente o desempenho, validando a necessidade de personalização.
  • Amostragem Não Ponderada (COREKG-Não Ponderada): Atribuir pesos iguais às amostras levou a uma degradação substancial do desempenho, destacando a importância da correção de viés via ponderação.

5. Significado e Alegações

O artigo alega que o COREKG aborda a lacuna crítica nos métodos de sumarização existentes ao mudar de modelagem de usuário global ou agregada para personalização explícita por usuário fundamentada em garantias teóricas.

• Eficiência: Ao manter apenas informações relevantes com base em padrões de consultas do usuário, o COREKG reduz significativamente os requisitos de armazenamento e o tempo de execução das consultas.
• Robustez: Diferentemente de métodos que dependem de difusão de calor ou históricos de consultas densos, o COREKG lida efetivamente com cargas de trabalho esparsas e enviesadas através de sua amostragem baseada em sensibilidade.
• Solidez Teórica: O método fornece uma "garantia de aproximação provável", assegurando que o resumo preserve a semântica de resposta a consultas do grafo completo até um erro relativo pequeno e limitado.

Os autores concluem que o COREKG é uma abordagem forte para sumarização personalizada de KG, oferecendo uma alternativa viável para lidar com KGs de grande escala em aplicações orientadas a dados onde a relevância específica do usuário e a eficiência computacional são primordiais. O trabalho nota explicitamente limitações relacionadas à representatividade de cargas de trabalho esparsas e à falta de garantias por consulta (em vez de agregadas), identificando estas como direções para pesquisas futuras.