Semantic SPARQL similarity search over RDF knowledge graphs

Leitura do artigo

Artigo de entrada: ZHENG,  W.  et  al.  Semantic  SPARQL  similarity  search  over  RDF  knowledge graphs. Proceedings of the VLDB Endowment, [s.l.], vol. 9, no. 11, p. 840–851, 2016. ISSN: 21508097, DOI: 10.14778/2983200.2983201

0 Resumo

A característica schema-free de dados RDF torna difícil para o usuário conhecer completamente o esquema que compõe a base de dados e permite que a mesma informação seja representada em fragmentos de grafos de estrutura diferentes (não isomorfos). Uma query em SPARQL que considere o segundo problema é usualmente expressa através de UNIONs de várias subqueries.

No framework proposto, dada uma query "simples" em SPARQL, o sistema retorna respostas com subgrafos do KG semanticamente similares a essa query. 

Uma nova medida de similaridade chamada semantic graph edit distance é proposta e incorpora tanto a similaridade sintática quanto a semântica.

Em termos de performance, é aplicada uma sumarização semântica do KG, na forma de um índice, que suporta tanto a poda de alto nível quanto a de aprofundamento.

1 Introdução 

Um exemplo de query usando o KG da DBPedia (domínio aberto) que apresenta os problemas inerentes a ser schema-free é apresentado.

Nessa proposta, é necessário especificar uma query em SPARQL que representa a estrutura de um subgrafo de interesse para que os demais subgrafos semânticamente similares sejam identificados e as respostas geradas.

Quanto a limitações dos trabalhos relacionados, alguns focam somente na similaridade sintática (estrutural), outros na similaridade semântica (conceitual) mas de modo separado. Na similaridade sintática, os rótulos de algumas arestas podem não coincidir mas os dos vértices e a estrutura de ligação devem ser isomorfos OU a estrutura de ligação pode variar mas os rótulos de vértices e arestas não OU uma aresta pode ser substituída pelo caminho mínimo entre dois vértices, etc .... Quanto a similaridade semântica, exploram a hierarquia de conceitos (subTypeOf) e sinônimos para rótulos.

A proposta trata de diferentes entradas e saídas se comparado com abordagens de schema matching ou ontology alignement. A abordagem é baseada em instâncias e não em schema. São considerados 3 tipos de equivalência semântica: generalização de conceitos, redirecionamento de arestas e indução por inferência.

As métricas de similaridade sintática/estrutural de grafos como graph edit distance (the minimum number of edit operations required to transform g1 into g2) e neighborhood information são consideradas em conjunto com concept-level similarity e diverse semantically equivalent structure patterns em uma única métrica.

2 SEMANTIC GRAPH PATTERN

Premissas: (1) todo vértice do KG é uma entidade que um tipo associado (rdf:type). Caso não tenha, alguma técnica deve ser empregada para descobrir o tipo ou associar ao tipo "Thing" e (2) existem bases de conhecimento que podem ser usadas como Dicionário de Instâncias Semanticamente Equivalentes (Dictionary of Semantic Instances) como o Probase ou técnicas de NLP que permitem gerar essas bases de conhecimento.

Dictionary of Semantic Instances: uma tabela onde cada linha contém um conjunto de entidades (Ds) ou par de entidades (Dp) com significado equivalente. Por exemplo uma linha contém uma lista de automóveis alemães, outra linha contém uma lista de nomes de lagos da Dinamarca, uma terceira linha contém uma lista com pares <Nome de Pessoa, País de Nascimento>, e uma quarta linha contém outra lista com pares <país, língua oficial> . Essa tabela é dada como entrada para os algoritmos.

Algorithm1 GSP SingleEntity: trata de listas de entidades do mesmo tipo (Ds) que podem estar representadas de modo diferente no KG. Para uma entidade vij do tipo tj que pertence ao Ds e ao KG, o algoritmo considera a Ontologia de hierarquia de tipos para identificar o tipo tk mais distante da raiz na estrutura (que o tipo tj pertence). Se tk for diferente de tj, analisar os vizinhos de vij. (??Pq usou similaridade de strings ao lidar com os vizinhos ?? O exemplo (Lake e LakeOfDenmark) ilustra mas não justifica !!! )

Algorithm 2 GSP EntityPairs: trata de pares de entidades do mesmo tipo (Dp) que podem estar representadas de modo diferente no KG. Para um par (vij, uij) que pertence ao Dp e ao KG, o algoritmo acha os caminhos px entre (vij, uij) no KG. Em cada caminho px, substituir vij por tv (tipo de vij no KG) e uij por tu (tipo de uij no KG) e calcular o número de pares de entidades que são ligadas no KG por caminhos no padrão px(tv, tu). O caminho com maior número de pares é adicionado na lista P (semantic graph pattern). (?? Não menciona o uso da Ontologia Oc ??)

Ambos os algoritmos recebem como entrada o KG, o Dicionário correspondente e uma Ontologia Oc / Op de hierarquia de tipos e predicados (subTypeOf/sub-PredicateOf).

Semantic Graph Patterns (P): gerados por ambos os algoritmos, podem ser de 3 tipos: 

• generalização/hierarquia de conceitos (Pc): por exemplo em um subgrafo o tipo é "Lago da Dinamarca" e em outro subgrafo o tipo é "Lago" mas na Ontologia "Lago da Dinamarca" é subtipo de "Lago"
• redirecionamento de arestas (Pe): por exemplo em um subgrafo temos <s, p1, o> e em outro temos <o, p2, s> onde p1 e p2 são equivalentes. É interessante pensar em expressar um fato em voz ativa ou passiva (João {é empregado da} Microsoft <=> Microsoft {é empregadora de} João) 
  
• indução por inferência (Pi): por exemplo em um subgrafo é possivel especificar o local de nascimento como a cidade e em outro como o país mas como saber qual é o país de nascimento para o primeiro caso? Inferindo o país usando a relação cidade -> estado -> país.
  

3 PROBLEM FORMALIZATION

Nove primitivas de edição de grafos que possuem um custo c associado: Semantic Vertex Insertion, Semantic Vertex Deletion, Semantic Vertex Substitution, Semantic Edge Insertion, Semantic Edge Deletion, Semantic Edge Substitution, Semantic Edge Redirection, Semantic Star Substitution e Semantic Path Substitution

O custo associado nas 3 primeiras operações depende da distância entre os tipos na Ontologia (Oc / Op). A distância é igual a 1 - Jaccard (interseção / união) do conjuntos de hierarquia de tipos de ti (tipo do vértice vi que representa uma entidade) até o tipo raíz t0 (Thing). O custo de inserir ou de deletar é calculado de ti a t0, o custo de substituir ti por tj, é calculado pela distância entre ti e tj. O mesmo pode ser aplicado a hierarquia de propriedades em relação as arestas para as 3 operações seguintes. 

Obs.: A medida graph edit distance (sintática) considera somente inserir, deletar e substituir nós e inserir, deletar e substituir arestas. O custo associado dessas operações não está vinculado a uma Ontologia de hierarquia de tipos (subTypeOf/subPredicateOf) e costuma ser fixo e igual a 1. 

As 3 últimas operações (shortcut operations), estão associadas aos Semantic Graph Patterns (conforme seção anterior). O custo de substituição é igual a 0 uma vez que são padrões semanticamente equivalentes extraídos do KG pelos dois algoritmos vistos.

Semantic Graph Edit Distance: dados dois grafos g1 e g2, sged(g1,g2) é o custo mínimo requerido em transformar g1 em g2 usando as nove primitivas de edição anteriormente citadas. O cálculo é NP-hard uma vez que é baseado na graph edit distance (ged) que já foi provada ser NP-hard.

Problem Statement:  Dado um KG e uma query q, o objetivo é gerar um conjunto de k subgrafos ( A = { g1, g2, ..., gk} ) cuja semantic edit distance de gi e q sejam as menores possíveis. 

A proposta trata esse problema em duas fases: uma offline e outra online. 

4. SEMANTIC SUMMARY GRAPH (Offline)

Semantic Fact: dada uma tripla (v1; r; v2) que é um fato básico que pertence a G, se v1 é do tipo t1 e v2 é do tipo t2 então uma tripla (t1; r; t2) pode ser gerada.

Semantic Graph: é o grafo SG gerado a partir de G considerando todas os semantic facts possíveis. 

Abstract Semantic Fact: considerando o grafo SG e Ontologia Oc / Op de hierarquia de tipos e predicados (subTypeOf/sub-PredicateOf) é possível gerar novas triplas do tipo (t1', r', t2') onde t1 é um subtipo de t1', t2 é um subtipo de t2' e r é um subpredicado de r'. Ou seja, são novas triplas em níveis de abstração mais altos  e que acabam representando as triplas de níveis inferiores. 

Abstract Semantic Graph: é o grafo ASG gerado a partir de SG e Oc / Op considerando todas os abstract semantic facts possíveis. Vários níveis de ASG podem ser gerados recursivamente de acordo com o nível de hierarquia presente na Ontologia Oc / Op. 

Semantic Summary Graph: é composto por um grafo multinível Gs onde o nível 1 é composto pelo G (fatos básicos), o nível 2 é composto pelo SG (fatos semânticos), o nível 3 é composto pelo ASG gerado pelo SG e os níveis subsequentes são formados pelos ASG com níveis de abstração cada vez mais altos.

O índice é criado com os grafos de nível 2 em diante. E o número de níveis controlado pelo summarization ratio que é a razão entre o somatório do número de vértices e arestas do nível i em relação ao nível anterior.

Remark. Although some similar efforts can be found for keyword search [20, 9], our proposed semantic summary graph differs from them: (1) Le et al., split the RDF graph into smaller partitions and then identify a set of templates serving as summary of these partitions [9]. (2) The graph schema index in [20] does not consider multi-level summarization.

5. QUERY REWRITING AND PRUNING

Três formas de reescrita para gerar o conjunto Qs: 

1. Star Rewriting: substituir um um subgrafo g centrado no vértice v por uma aresta <v,r,u> de acordo com semantic graph patterns to tipo generalização/hierarquia de conceitos (Pc), 
2. Path Rewriting: verificar se existe um caminho no grafo que pode ser substituído por uma aresta de "atalho", também chamado de semantic path substitution
   
3. Query Summarization: mesmos passos das construção do Semantic Summary Graph, ou seja, usar a Ontologia Oc / Op de hierarquia de tipos e predicados (subTypeOf/sub-PredicateOf) para gerar novos abstract semantic facts e montar o summarized query graphs (Q2 e Q3)

Dois níveis de poda: 

Alto nível: realizar o match de cada qk que pertence ao summarized query graphs Qs sobre o índice semantic summary graph Gs. Mas esse match não retorna subgrafos g do KG G e sim gs no nível de sumarização s, então é necessário identificar as arestas e vértices candidatos para cada qk até chegar nas instâncias de G fazendo operações de aprofundamento.

Aprofundamento: também chamado de drill-down e apresentado no Algorithm 3 Drill-downPruning. Se está no nível 1, das instâncias, então os vértices e arestas candidatos são a resposta. Caso contrário, dado o conjunto de arestas candidatas do nível k para a query qk, obter o conjunto de arestas cobertas pelos Gs de nível k-1. Para cada query qk-1 coberta pela query qk obter a aresta mais similar a essa query do conjunto de arestas. Repetir para os níveis anteriores até chegar ao nível 1, das instâncias.

6. ANSWER GENERATION

<< não entendi essa seção >>

7 Experimento

Dataset1. DBpedia (5,040,948 vertices and 61,481,483 edges) + DBpedia Ontology + 236 SPARQL Queries (QALD-47 benchmark) -> em caso de UNION foi usada só uma parte da query para o framework derivar o resto. 

Dataset2. Yago (Wikipedia,Word-Net, and GeoNames; 10,538,013 entities and 183,041,129
edges) + 10 consultas baseadas em um trabalho anterior 

Métricas: precisão e cobertura para o Dataset1 (golden standard) para a eficiência, Tempo de resposta para o desempenho e fact coverage ratio (razão entre os fato extraídos pela operação e todos os fatos existentes em G) para a eficácia das 3 operações de short cut. 

Figuras 11, 12 e 13 apresentam exemplos de semantic graph patterns (Pc, Pe, Pi) extraídos com os algorítimos 1 e 2. 

Foi realizada a comparação com 3 outros métodos (*vide próximo tópico) e a proposta apresentou melhor F1 (tabela 2)

Tabelas 4 e 5 apresentam o resultado das operações de shortcut. A eficácia das 3 shortcut operations (edge redirection, star substitution, and path substitution) estão associadas aos Semantic Graph Patterns identificados através dos algortimos 1 e 2.

O tempo e o tamanho do índice de sumarização também foram avaliados em relação ao parâmetro do grau de sumarização (tabela 6) - summarization ratio. Quanto maior o summarization ratio menores os valores de precisão, cobertura e F1 por outro lado o tempo de resposta é reduzido a medida que o summarization ratio aumenta. 

O resultado de F1 e o tempo de resposta foram medidos para diferentes Top K em cada proposta e também foi realizada a inclusão de ruído no dataset para avaliar a robustez de cada proposta. 

8 Trabalhos relacionados

NeMa (estrutura / sintática): propose the neighborhood-based similarity measure, which unifies both the label matching cost and neighborhood matching cost.

SLQ (nível do conceito / semântica): introduces a framework that integrates a set of transformation functions, such as “synonym”, “ontology” and “distance” (i.e., transforming an edge to a shortest path).

gStore (não citado nessa seção mas usado na comparabilidade): is built based on the exact subgraph matching. However, due to the same reason, it can only find the matches that are isomorphic to the query graph, which results in low recall.

9 Conclusão

Em tempo de execução, as queries são reescritas e,  tanto a poda de alto nível quanto a de aprofundamento, são aplicadas para reduzir o espaço de busca e a complexidade da solução.