Message Passing for Hyper-Relational Knowledge Graphs (STARE) - Leitura de Artigo

Mikhail Galkin, Priyansh Trivedi, Gaurav Maheshwari, Ricardo Usbeck, Jens Lehmann: Message Passing for Hyper-Relational Knowledge Graphs. EMNLP (1) 2020: 7346-7359

Abstract

Hyper-relational knowledge graphs (KGs) (e.g., Wikidata) enable associating additional key-value pairs along with the main triple to disambiguate, or restrict the validity of a fact.

In this work, we propose a message passing based graph encoder - STARE capable of modeling such hyper-relational KGs. Unlike existing approaches, STARE can encode an arbitrary number of additional information (qualifiers) along with the main triple while keeping the semantic roles of qualifiers and triples intact.

We also demonstrate that existing benchmarks for evaluating link prediction (LP) performance on hyper-relational KGs suffer from fundamental flaws and thus develop a new Wikidata-based dataset - WD50K.

[Dataset KG hiper relacional: poderia ser usado nas tarefas de exploração de KG?]

Our experiments demonstrate that STARE based LP (link prediction) model outperforms existing approaches across multiple benchmarks. We also confirm that leveraging qualifiers is vital for link prediction with gains up to 25 MRR points compared to triple-based representations.

[Considerar os qualificadores em tarefas de link prediction leva a melhores resultados. Será que isso também acontece em tarefas de busca exploratória? Se sim, como avaliar?]

1 Introduction

The task of link prediction over knowledge graphs (KGs) has seen a wide variety of advances over the years (Ji et al., 2020). The objective of this task is to predict new links between entities in the graph based on the existing ones. A majority of these approaches are designed to work over triple-based KGs, where facts are represented as binary relations between entities.

[Predição de link somente com as triplas. O KG é incompleto então o objetivo é completar o mesmo]

This additional information can be provided in the form of key-value restrictions over instances of binary relations between entities in recent knowledge graph models. Such restrictions are known as qualifiers in the Wikidata statement model or triple metadata in RDF* and RDF reification approaches.

[Olhar essa ref: Thomas Pellissier-Tanon, Gerhard Weikum, and Fabian Suchanek. 2020. Yago 4: A reasonable knowledge base. In Extended Semantic Web Conference, ESWC 2020.] 

In this work, we propose an alternate graph representation learning mechanism capable of encoding hyper-relational KGs with arbitrary number of qualifiers, while keeping the semantic roles of qualifiers and triples intact. To accomplish this, we leverage the advances in Graph Neural Networks (GNNs), many of which are instances of the message passing framework, to learn latent representations of nodes and edges of a given graph.

[Somente vértices e arestas, não usa literais e não faz a predição de qualificadores]

Recently, GNNs have been demonstrated to be capable of encoding mutli-relational (tripled based) knowledge graphs. Inspired by them, we further extend this framework to incorporate hyper relational KGs, and propose STARE , which to the best of our knowledge is the first GNN-based approach capable of doing so (see Sec. 4).

[Multi relacional o RDF-Star não é]

2 Related Work

HINGE (Rosso et al., 2020) also adopts a convolutional framework for modeling hyper-relational facts. A main triple is iteratively convolved with every qualifier pair as a quintuple followed by min pooling over quintuple representations. Although it retains the hyper-relational nature of facts, HINGE operates on a triple-quintuple level that lacks granularity of representing a certain relation instance with its qualifiers. Additionally, HINGE has to be trained sequentially in a curriculum learning fashion requiring sorting all facts in a KG in an ascending order of the amount of qualifiers per fact which might be prohibitively expensive for large-scale graphs.

[Diferencial da proposta STARE em relação ao HINGE. Toda proposta deve apresentar a sua diferença em relação aos trabalhos relacionados de modo a justificar uma nova abordagem]

As hyper-edges contain multiple nodes, such hyperedges are closer to n-ary relations r(e1, . . . , en) with one abstract relation. The attribution of entities to the main triple or qualifiers is lost, and qualifying relations are not defined.

[Hiper relacional e hiper grafo requerem abordagens diferentes]

3 Preliminaries

GNNs on Undirected Graphs: Consider an undirected graph G = (V, E), where V represents the set of nodes and E denotes the set of edges. Each node v from V has an associated vector hv and neighbourhood N (v).

GNN on Directed Multi-Relational Graphs: In case of a multi-relational graph G = (V, R, E) where R represents the set of relations r, and E denotes set of directed edges (s, r, o) where nodes s from V and o from V are connected via relation r.

[Multi relacional direcionado]

Hyper-Relational Graphs: In case of a hyper-relational graph G = (V, R, E), E is a list (e1, . . . , en) of edges with ej = V × R × V × P(R × V) for 1 ≤ j ≤ n, where P denotes the power set. A hyper-relational fact ej from E is usually written as a tuple (s, r, o, Q), where Q is the set of qualifier pairs {(qri, qvi)} with qualifier relations qri from R and qualifier values qvi from V. (s, r, o) is referred to as the main triple of the fact. We use the notation Qj to denote the qualifier pairs of ej . For example, ... (Albert Einstein, educated at, University of Zurich, (academic degree, Doctorate), (academic major, Physics))

[Eu usei Q e o Q pode ser um R ou um P. Seria o caso de mudar para simplificar?]

[Outra definição de hyper KG]

4 STARE

STARE incorporates statement qualifiers {(qri, qvi)}, along with the main triple (s, r, o) into a message passing process.

[É uma equação]

This formalisation allows to (i) incorporate an arbitrary number of qualifier pairs and (ii) can take into account whether entities/relations occur in the main triple or the qualifier pairs. STARE is the first GNN model for representation learning of hyper-relational KGs that has these characteristics.

STARE for Link Prediction. STARE is a general representation learning framework for capturing the structure of hyper-relational graphs, and thus can be applied to multiple downstream tasks. In this work, we focus on LP and leave other tasks such as node classification for future work. In LP, given a query (s, r, Q), the task is to predict an entity corresponding to the object position o.

[Pode ser o objeto como saída ou pode ser um score de uma tripla dada]

5 WD50K Dataset

Recent approaches for embedding hyper-relational KGs often use WikiPeople and JF17K as benchmarking datasets. We advocate that those datasets can not fully capture the task complexity.

In WikiPeople, about 13% of statements contain at least one literal. Literals (e.g. numeric values, date-time instances or other strings, etc) in KGs are conventionally ignored (Rosso et al., 2020) by embedding approaches, or are incorporated throughspecific means (Kristiadi et al., 2019). However, after removing statements with literals, less than 3% of the remaining statements contain any qualifier pairs. Out of those, about 80% possess only one qualifier. This fact renders WikiPeople less sensitive to hyper-relational models as performance on triple-only facts dominates the overall score.

The authors of JF17K reported the dataset to contain redundant entries. In our own analysis, we detected that about 44.5% of the test statements share the same main (s, r, o) triple as the train statements. We consider this fact as a major data leakage which allows triple-based models to memorize subjects and objects appearing in the test set.

[Mas serviriam para as tarefas de busca exploratória pq a existência de literais nos qualificadores não é um problema e nem as entradas redundantes]

To alleviate the above problems, we propose a new dataset, WD50K, extracted from Wikidata statements. ... This step results in the removal of all literals in object position. Similarly, all literals are filtered out from the qualifiers of the obtained statements. To increase the connectivity in the statements graph, all the entities mentioned less than twice are dropped.

[Critérios que não fazem diferença para a tarefa de busca exploratória]

6 Experiments

[EU preciso avaliar o efeito da presença de contexto nas tarefas de busca exploratória. Seria o caso de comparar a busca COM e SEM contexto? Mas comparar usando quais métricas?]

6.1 Evaluating STARE on the LP Task

6.2 Impact of Ratio of Statements with and Without Qualifier Pairs

We observe that across all metrics, STARE (H) + Transformer (H) performs increasingly better than Transformer (H), as the ratio of qualifier pairs increases in the dataset

[Mais qualificadores, melhor o resultado da tarefa de LP]

To do so, we create multiple variants of WD50K, each containing statements with up to n qualifiers(n =[1 .. 6]). In other words, for a given number n, we collect all the statements which have less than n qualifiers. If a statement contains more than n qualifiers, we arbitrarily choose n qualifiers amongst them. Thus, the total number of facts remains the same across these variants.

[Variar o número de qualificadores]

6.4 Comparison to Triple Baselines

To further understand the role of qualifier information in the LP task, we design an experiment to gauge the performance difference between models on hyper-relational KG and triple-based KG. Concretely, we create a new triple-only dataset by pruning all qualifier information from the statements in WikiPeople, JF17K, and WD50K. That is, two statements that describe the same main fact (s, r, o, {(qr1, qv1), (qr2, qv2)} and (s, r, o, {(qr3, qv3), (qr4, qv4)}) are reduced to one triple (s, r, o). Thus, the overall amount of distinct entities and relations is reduced, but the amount of subjects and objects in main triples for the LP task is the same.

[Perda de informação, o certo não seria reificar?]

Based on the above observations [resultados das tabelas] we therefore conclude, that information in hyper-relational facts indeed helps to better predict subjects and objects in the main triples of those facts.

A Further details on WD50k - https://zenodo.org/record/4036498#.YuwZYFTMLIU

WD50k consists of 47,156 entities, and 532 relations, amongst which 5,460 entities and 45 relations are found only within qualifier (qp, qe) pairs. Fig. 5 illustrates how qualifiers are distributed among statements, i.e., 236,393 statements (99.9%) contain up to five qualifiers whereas remaining 114 statements in a long tail contain up to 20 qualifiers.

@inproceedings{StarE,
  title={Message Passing for Hyper-Relational Knowledge Graphs},
  author={Galkin, Mikhail and Trivedi, Priyansh and Maheshwari, Gaurav and Usbeck, Ricardo and Lehmann, Jens},
  booktitle={EMNLP},
  year={2020}
}

Sparse Representation

Figure 7: Sparse representation for hyper-relational facts. Each fact has a unique integer index k which is shared between two COO matrices, i.e., the first one is for main triples, the second one is for qualifiers. Qualifiers that belong to the same fact share the index k.

[Duas tabelas de um banco relacional com um ID de tripla que as liga, não usa literais]

 

Storing full adjacency matrices of large KGs is impractical due to O(|V|2) memory consumption. GNNs encourage using sparse matrix representations and adopting sparse matrices is shown to be scalable to graphs with millions of edges. As illustrated in Figure 7, we employ two sparse COO matrices to model hyper-relational KGs.

The first COO matrix is of a standard format with rows containing indices of subjects, objects, and relations associated with the main triple of a hyper-relational fact. In addition, we store index k that uniquely identifies each fact. The second COO matrix contains rows of qualifier relations qr and entities qe that are connected to their main triple (and the overall hyper-relational fact) through the index k, i.e., if a fact has several qualifiers those columns corresponding to the qualifiers of the fact will share the same index k.

The overall memory consumption is therefore O(|E| + |Q|) and scales linearly to the total number of qualifiers |Q|. Given that most open-domain KGs rarely qualify each fact, e.g., as of August 2019, out of 734M Wikidata statements approximately 128M (17.4%) have at least one qualifier, this sparse qualifier representation saves limited GPU memory.

[A tarefa de treinamento vai ler sequencialmente e não vai buscar caminhos, assim as duas tabelas atendem mas na exploração pode ser necessário perguntar qual a relação entre A e B e a resposta dessa relação pode ser um caminho no grafo. Esse tipo de consulta em tabelas relacionais usando SQL recursivo é mais custoso]