Modeling Relational Data with Graph …

1 Modeling Relational data with Graph convolutional NetworksMichael Schlichtkrull University of N. Kipf University of BloemVU van den BergUniversity of TitovUniversity of WellingUniversity of Amsterdam, CIFAR graphs enable a wide variety of applications, in-cluding question answering and information retrieval. De-spite the great effort invested in their creation and mainte-nance, even the largest ( , Yago, DBPedia or Wikidata)remain incomplete. We introduce Relational Graph Convo-lutional Networks (R-GCNs) and apply them to two standardknowledge base completion tasks: Link prediction (recoveryof missing facts, subject-predicate-object triples) and en-tity classification (recovery of missing entity attributes). R-GCNs are related to a recent class of neural networks operat-ing on graphs, and are developed specifically to deal with thehighly multi- Relational data characteristic of realistic knowl-edge bases.

2 We demonstrate the effectiveness of R-GCNs asa stand-alone model for entity classification. We further showthat factorization models for link prediction such as DistMultcan be significantly improved by enriching them with an en-coder model to accumulate evidence over multiple inferencesteps in the Relational Graph , demonstrating a large improve-ment of on FB15k-237 over a decoder-only IntroductionKnowledge bases organize and store factual knowledge, en-abling a multitude of applications including question an-swering (Yao and Van Durme 2014; Bao et al. 2014; Seyler,Yahya, and Berberich 2015; Hixon, Clark, and Hajishirzi2015; Bordes et al. 2015; Dong et al. 2015) and informa-tion retrieval (Kotov and Zhai 2012; Dalton, Dietz, and Al-lan 2014; Xiong and Callan 2015b; 2015a). Even the largestknowledge bases ( DBPedia, Wikidata or Yago), despiteenormous effort invested in their maintenance, are incom-plete, and the lack of coverage harms downstream applica-tions.

3 Predicting missing information in knowledge bases isthe main focus of statistical Relational learning (SRL).Following previous work on SRL, we assume that knowl-edge bases store collections of triples of the form (subject,predicate, object). Consider, for example, the triple (MikhailBaryshnikov,educatedat,Vaganova Academy), where wewill refer toBaryshnikovandVaganova Academyas enti-ties and toeducatedatas a relation. Additionally, we as-sume that entities are labeled with types ( ,Vaganova Equal contribution. Canadian Institute for Advanced ResearchMikhail BaryshnikovVaganova prizeawardededucated_atcitizen_of:countr y:university:award:ballet_dancerFigure 1: A knowledge base fragment: The nodes are en-tities, the edges are relations labeled with their types, thenodes are labeled with entity types ( ,university).)

4 Theedge and the node label shown in red are the missing in-formation to be marked as auniversity). It is convenient to rep-resent knowledge bases as directed labeled multigraphs withentities corresponding to nodes and triples encoded by la-beled edges (see Figure 1).We consider two fundamental SRL tasks: link predic-tion (recovery of missing triples) and entity classification(assigning types or categorical properties to entities). Inboth cases, many missing pieces of information can be ex-pected to reside within the Graph encoded through the neigh-borhood structure knowing thatMikhail Baryshnikovwas educated at theVaganova Academyimplies both thatMikhail Baryshnikovshould have the label person, and thatthe triple (Mikhail Baryshnikov,livedin,Russia) must be-long to the knowledge Graph . Following this intuition, wedevelop an encoder model for entities in the Relational graphand apply it to both entity classification model, similarly to Kipf andWelling (2017), uses softmax classifiers at each node in thegraph.

5 The classifiers take node representations supplied bya Relational Graph convolutional network (R-GCN) and pre-dict the labels. The model, including R-GCN parameters, islearned by optimizing the cross-entropy link prediction model can be regarded as an autoen-coder consisting of (1) an encoder: an R-GCN producinglatent feature representations of entities, and (2) a decoder:a tensor factorization model exploiting these [ ] 26 Oct 2017to predict labeled edges. Though in principle the decoder canrely on any type of factorization (or generally any scoringfunction), we use one of the simplest and most effective fac-torization methods: DistMult (Yang et al. 2014). We observethat our method achieves competitive results on standardbenchmarks, outperforming, among other baselines, directoptimization of the factorization ( vanilla DistMult). Thisimprovement is especially large when we consider the morechallenging FB15k-237 dataset (Toutanova and Chen 2015).

6 This result demonstrates that explicit Modeling of neighbor-hoods in R-GCNs is beneficial for recovering missing factsin knowledge main contributions are as follows. To the best of ourknowledge, we are the first to show that the GCN frame-work can be applied to Modeling Relational data , specificallyto link prediction and entity classification tasks. Secondly,we introduce techniques for parameter sharing and to en-force sparsity constraints, and use them to apply R-GCNsto multigraphs with large numbers of relations. Lastly, weshow that the performance of factorization models, at theexample of DistMult, can be significantly improved by en-riching them with an encoder model that performs multiplesteps of information propagation in the Relational Neural Relational modelingWe introduce the following notation: we denote directed andlabeled multi-graphs asG= (V,E,R) with nodes (entities)vi Vand labeled edges (relations)(vi,r,vj) E, wherer Ris a relation Relational Graph convolutional networksOur model is primarily motivated as an extension of GCNsthat operate on local Graph neighborhoods (Duvenaud et ; Kipf and Welling 2017) to large-scale Relational and related methods such as Graph neural networks(Scarselli et al.)

7 2009) can be understood as special cases ofa simple differentiable message-passing framework (Gilmeret al. 2017):h(l+1)i= ( m Migm(h(l)i,h(l)j)),(1)whereh(l)i Rd(l)is the hidden state of nodeviin thel-th layer of the neural network , withd(l)being the di-mensionality of this layer s representations. Incoming mes-sages of the formgm( , )are accumulated and passedthrough an element-wise activation function ( ), such astheReLU( ) = max(0, ).2 Midenotes the set of incomingmessages for nodeviand is often chosen to be identical tothe set of incoming ( , )is typically chosen to bea (message-specific) neural network -like function or simplya linear transformationgm(hi,hj) =Whjwith a weightmatrixWsuch as in Kipf and Welling (2017).1 Rcontains relations both in canonical direction ( )and in inverse direction ( ).2 Note that this represents a simplification of the message pass-ing neural network proposed in (Gilmer et al.

8 2017) that suffices toinclude the aforementioned models as special type of transformation has been shown to be veryeffective at accumulating and encoding features from lo-cal, structured neighborhoods, and has led to significant im-provements in areas such as Graph classification (Duvenaudet al. 2015) and Graph -based semi-supervised learning (Kipfand Welling 2017).Motivated by these architectures, we define the followingsimple propagation model for calculating the forward-passupdate of an entity or node denoted byviin a Relational (di-rected and labeled) multi- Graph :h(l+1)i= r R j Nri1ci,rW(l)rh(l)j+W(l)0h(l)i ,(2)whereNridenotes the set of neighbor indices of nodeiun-der relationr ,ris a problem-specific normaliza-tion constant that can either be learned or chosen in advance(such asci,r=|Nri|).Intuitively, (2) accumulates transformed feature vectorsof neighboring nodes through a normalized sum.

9 Differentfrom regular GCNs, we introduce relation-specific transfor-mations, depending on the type and direction of an ensure that the representation of a node at layerl+ 1can also be informed by the corresponding representation atlayerl, we add a single self-connection of a special relationtype to each node in the data . Note that instead of simple lin-ear message transformations, one could choose more flexi-ble functions such as multi-layer neural networks (at the ex-pense of computational efficiency). We leave this for neural network layer update consists of evaluating (2)in parallel for every node in the Graph . In practice, (2) can beimplemented efficiently using sparse matrix multiplicationsto avoid explicit summation over neighborhoods. Multiplelayers can be stacked to allow for dependencies across sev-eral Relational steps. We refer to this Graph encoder modelas a Relational Graph convolutional network (R-GCN).

10 Thecomputation Graph for a single node update in the R-GCNmodel is depicted in Figure RegularizationA central issue with applying (2) to highly multi-relationaldata is the rapid growth in number of parameters with thenumber of relations in the Graph . In practice this can easilylead to overfitting on rare relations and to models of verylarge address this issue, we introduce two separate meth-ods for regularizing the weights of R-GCN-layers:basis-andblock-diagonal-dec omposition. with the basis decom-position, eachW(l)ris defined as follows:W(l)r=B b=1a(l)rbV(l)b,(3) as a linear combination of basis transformationsV(l)b Rd(l+1) d(l) with coefficientsa(l)rbsuch that only the coeffi-cients depend onr. In the block-diagonal decomposition, werel_1 (in)rel_1 (out)rel_N (in)rel_N (out)..+rel_1rel_NReLUself-loopself-loop Figure 2: Diagram for computing the update of a singlegraph node/entity (red) in the R-GCN model.