ICLR  AND Knowledge Graph
67855617
RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space
We study the problem of learning representations of entities and relations in knowledge graphs for predicting missing links. The success of such a task heavily relies on the ability of modeling and inferring the patterns of (or between) the relations. In this paper, we present a new approach for knowledge graph embedding called RotatE, which is able to model and infer various relation patterns including: symmetry/antisymmetry, inversion, and composition. Specifically, the RotatE model defines each relation as a rotation from the source entity to the target entity in the complex vector space. In addition, we propose a novel self adversarial negative sampling technique for efficiently and effectively training the RotatE model. Experimental results on multiple benchmark knowledge graphs show that the proposed RotatE model is not only scalable, but also able to infer and model various relation patterns and significantly outperform existing state of the art models for link prediction.
ICLR
Zhiqing Sun Zhihong Deng Jian-Yun Nie Jian Tang
211241737
You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings
Knowledge graph embedding (KGE) models learn algebraic representations of the entities and relations in a knowledge graph. A vast number of KGE techniques for multi relational link prediction has been proposed in the recent literature, often with state of the art performance. These approaches differ along a number of dimensions, including different model architectures, different training strategies, and different approaches to hyperparameter optimization. In this paper, we take a step back and aim to summarize and quantify empirically the impact of each of these dimensions on model performance. We report on the results of an extensive experimental study with popular model architectures and training strategies across a wide range of hyperparameter settings. We found that when trained appropriately, the relative performance differences between various model architectures often shrinks and sometimes even reverses when compared to prior results. For example, RESCAL, one of the first KGE models, showed strong performance when trained with state of the art techniques; it was competitive to or outperformed more recent architectures. We also found that good (and often superior to prior studies) model configurations can be found by exploring relatively few random samples from a large hyperparameter space. Our results suggest that many of the more advanced architectures and techniques proposed in the literature should be revisited to reassess their individual benefits.
ICLR
You Can Teach Daniel Ruffinelli Samuel Broscheit Rainer Gemulla
3144218
Semi Supervised Classification with Graph Convolutional Networks
We present a scalable approach for semi supervised learning on graph structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a localized first order approximation of spectral graph convolutions. Our model scales linearly in the number of graph edges and learns hidden layer representations that encode both local graph structure and features of nodes. In a number of experiments on citation networks and on a knowledge graph dataset we demonstrate that our approach outperforms related methods by a significant margin.
ICLR
Thomas N Kipf Max Welling
209439505
Probability Calibration for Knowledge Graph Embedding Models
Knowledge graph embedding research has overlooked the problem of probability calibration. We show popular embedding models are indeed uncalibrated. That means probability estimates associated to predicted triples are unreliable. We present a novel method to calibrate a model when ground truth negatives are not available, which is the usual case in knowledge graphs. We propose to use Platt scaling and isotonic regression alongside our method. Experiments on three datasets with ground truth negatives show our contribution leads to well calibrated models when compared to the gold standard of using negatives. We get significantly better results than the uncalibrated models from all calibration methods. We show isotonic regression offers the best the performance overall, not without trade offs. We also show that calibrated models reach state of the art accuracy without the need to define relation specific decision thresholds.
ICLR
Pedro Tabacof Luca Costabello
202750112
Dynamically Pruned Message Passing Networks for Large Scale Knowledge Graph Reasoning
We propose Dynamically Pruned Message Passing Networks (DPMPN) for large scale knowledge graph reasoning. In contrast to existing models, embedding based or path based, we learn an input dependent subgraph to explicitly model reasoning process. Subgraphs are dynamically constructed and expanded by applying graphical attention mechanism conditioned on input queries. In this way, we not only construct graph structured explanations but also enable message passing designed in Graph Neural Networks (GNNs) to scale with graph sizes. We take the inspiration from the consciousness prior proposed by and develop a two GNN framework to simultaneously encode input agnostic full graph representation and learn input dependent local one coordinated by an attention module. Experiments demonstrate the reasoning capability of our model that is to provide clear graphical explanations as well as deliver accurate predictions, outperforming most state of the art methods in knowledge base completion tasks.
ICLR
Xiaoran Xu Wei Feng Yunsheng Jiang Xiaohui Xie Zhiqing Sun Zhihong Deng
207847719
Composition based Multi Relational Graph Convolutional Networks
Graph Convolutional Networks (GCNs) have recently been shown to be quite successful in modeling graph structured data. However, the primary focus has been on handling simple undirected graphs. Multi relational graphs are a more general and prevalent form of graphs where each edge has a label and direction associated with it. Most of the existing approaches to handle such graphs suffer from over parameterization and are restricted to learning representations of nodes only. In this paper, we propose CompGCN, a novel Graph Convolutional framework which jointly embeds both nodes and relations in a relational graph. CompGCN leverages a variety of entity relation composition operations from Knowledge Graph Embedding techniques and scales with the number of relations. It also generalizes several of the existing multi relational GCN methods. We evaluate our proposed method on multiple tasks such as node classification, link prediction, and graph classification, and achieve demonstrably superior results. We make the source code of CompGCN available to foster reproducible research.
ICLR
Shikhar Vashishth Soumya Sanyal Vikram Nitin Partha Pratim Talukdar
209513260
The Logical Expressiveness of Graph Neural Networks
The ability of graph neural networks (GNNs) for distinguishing nodes in graphs has been recently characterized in terms of the Weisfeiler Lehman (WL) test for checking graph isomorphism. This characterization, however, does not settle the issue of which Boolean node classifiers (i.e. functions classifying nodes in graphs as true or false) can be expressed by GNNs. We tackle this problem by focusing on Boolean classifiers expressible as formulas in the logic FOC2, a well studied fragment of first order logic. FOC2 is tightly related to the WL test, and hence to GNNs. We start by studying a popular class of GNNs, which we call AC GNNs, in which the features of each node in the graph are updated, in successive layers, only in terms of the features of its neighbors. We show that this class of GNNs is too weak to capture all FOC2 classifiers, and provide a syntactic characterization of the largest subclass of FOC2 classifiers that can be captured by AC GNNs. This subclass coincides with a logic heavily used by the knowledge representation community. We then look at what needs to be added to AC GNNs for capturing all FOC2 classifiers. We show that it suffices to add readout functions, which allow to update the features of a node not only in terms of its neighbors, but also in terms of a global attribute vector. We call GNNs of this kind ACR GNNs. We experimentally validate our findings showing that, on synthetic data conforming to FOC2 formulas, AC GNNs struggle to fit the training data while ACR GNNs can generalize even to graphs of sizes not seen during training.
ICLR
Pablo Barcelo Egor V Kostylev Mikael Monet Jorge Perez Juan L Reutter Juan-Pablo Silva
210920362
GraphAF: a Flow based Autoregressive Model for Molecular Graph Generation
Molecular graph generation is a fundamental problem for drug discovery and has been attracting growing attention. The problem is challenging since it requires not only generating chemically valid molecular structures but also optimizing their chemical properties in the meantime. Inspired by the recent progress in deep generative models, in this paper we propose a flow based autoregressive model for graph generation called GraphAF. GraphAF combines the advantages of both autoregressive and flow based approaches and enjoys: (1) high model flexibility for data density estimation; (2) efficient parallel computation for training; (3) an iterative sampling process, which allows leveraging chemical domain knowledge for valency checking. Experimental results show that GraphAF is able to generate 68% chemically valid molecules even without chemical knowledge rules and 100% valid molecules with chemical rules. The training process of GraphAF is two times faster than the existing state of the art approach GCPN. After fine tuning the model for goal directed property optimization with reinforcement learning, GraphAF achieves state of the art performance on both chemical property optimization and constrained property optimization.
ICLR
Chence Shi Minkai Xu Zhaocheng Zhu Weinan Zhang Ming Zhang Jian Tang
210911499
Graph Constrained Reinforcement Learning for Natural Language Action Spaces
Interactive Fiction games are text based simulations in which an agent interacts with the world purely through natural language. They are ideal environments for studying how to extend reinforcement learning agents to meet the challenges of natural language understanding, partial observability, and action generation in combinatorially large text based action spaces. We present KG A2C, an agent that builds a dynamic knowledge graph while exploring and generates actions using a template based action space. We contend that the dual uses of the knowledge graph to reason about game state and to constrain natural language generation are the keys to scalable exploration of combinatorially large natural language actions. Results across a wide variety of IF games show that KG A2C outperforms current IF agents despite the exponential increase in action space size.
ICLR
Prithviraj Ammanabrolu Matthew J Hausknecht
210846466
Deep Graph Matching Consensus
This work presents a two stage neural architecture for learning and refining structural correspondences between graphs. First, we use localized node embeddings computed by a graph neural network to obtain an initial ranking of soft correspondences between nodes. Secondly, we employ synchronous message passing networks to iteratively re rank the soft correspondences to reach a matching consensus in local neighborhoods between graphs. We show, theoretically and empirically, that our message passing scheme computes a well founded measure of consensus for corresponding neighborhoods, which is then used to guide the iterative re ranking process. Our purely local and sparsity aware architecture scales well to large, real world inputs while still being able to recover global correspondences consistently. We demonstrate the practical effectiveness of our method on real world tasks from the fields of computer vision and entity alignment between knowledge graphs, on which we improve upon the current state of the art.
ICLR
Matthias Fey Jan Eric Lenssen Christopher Morris Jonathan Masci Nils M Kriege