Dynamically Pruned Message Passing Networks for Large-scale Knowledge Graph Reasoning
Authors: Xiaoran Xu
Wei Feng
Yunsheng Jiang
Xiaohui Xie
Zhiqing Sun
Zhi-Hong Deng
Venue:  (2020)
Keywords: knowledge graph reasoning
graph neural networks
attention mechanism

Abstract: 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 a sequential reasoning process. Each subgraph is dynamically constructed, expanding itself selectively under a flow-style attention mechanism. In this way, we can not only construct graphical explanations to interpret prediction, but also prune message passing in Graph Neural Networks (GNNs) to scale with the size of graphs. We take the inspiration from the consciousness prior proposed by Bengio to design a two-GNN framework to encode global input-invariant graph-structured representation and learn local input-dependent one coordinated by an attention module. Experiments show the reasoning capability in our model that is providing a clear graphical explanation as well as predicting results accurately, outperforming most state-of-the-art methods in knowledge base completion tasks.

Published as a conference paper at ICLR 2020
DYNAMICALLY PRUNED MESSAGE PASSING NET- WORKS FOR LARGE-SCALE KNOWLEDGE GRAPH REASONING
Xiaoran Xu', Wei Feng', Yunsheng Jiang', Xiaohui Xie', Zhiqing Sun", Zhi-Hong Deng Hulu, {xiaoran. xu, vei.feng, yunsheng. xiachui seeliiiieeeheeie miell.h...cco Carnegie Mellon University, zhiqingseandrew cmu, edu
SPeking University, zhdengépku.eda..om
ABSTRACT
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 input-dependent subgraph to explicitly model reasoning process. Subgraphs are dynamically constructed and expanded by ap- plying graphical attention mechanism conditioned on input queries. In this way. we not only construct graph- graph-structured explanations but also enable message pass- ing designed in Graph Neural Networks (GNNs) to scale with graph sizes. We take the inspiration from the consciousness prior proposed by Bengio (2017) and develop a two-GNN framework to encode input-agnostic full structure represen- tation and learn input-dependent local one coordinated by an attention module. Experiments show the reasoning capability of our model to provide clear graph- ical explanations well predict results accurately, outperforming most state- of-the-art art methods in knowledge base completion tasks.
INTRODUCTION
Modern deep learning systems should bring in explicit reasoning modeling to complement their black-box models, where reasoning takes step-by-step form about organizing facts to yield new knowledge and finally draw a conclusion. Particularly, we rely on graph-structured representation to model reasoning by manipulating nodes and edges where semantic entities relations can be explicitly represented (Battagli et al. 2018). Here, we choose knowledge graph scenarios to study reasoning where semantics have been defined nodes and edges. For example, in knowledge base completion tasks, each edge is represented by a triple (head, rel, tail) that contains two entities and their relation. The goal is to predict which entity might be tail given query (head, rel, ?).
Existing models can be categorized into embedding-based and path-based model families. The embedding-basee (Bordes al. 2013 Sun al. 2018 Lacroix al. 2018) often achieves high score by fitting data using various neural network techniques but lacks interpretability. The path- based (Xiong et al., 2017 Das et al. 2018 Shen al. 2018 Wang 2018 attempts construct an explanatory path to model an iterative decision- making process using reinforcement learning and recurrent networks. A question
can we construct structured explanations other than path to better explain reasoning in graph context. To this end, we propose to learn dynamically induced subgraph which starts with a head node and ends with predicted tail node as shown Figure
Graph reasoning can be powered by Graph Neural Networks. Graph reasoning needs to learn about entities, relations, and their composing nules to manipulate structured knowledge and produce structured cxplanations. Graph Neural Networks (GNNs) provide such structured computation and also inherit powerful fata-fitting capacity from deep neural networks (Scarselli et al. 2009 Battaglia et 2018)). Specifically, GNNs follow neighborhood aggregation scheme recursively aggregate information from neighbors to update node states. After T iterations, each node can carry structure information from its Thp neighborhood (Gilmer al.) 2017: Xu et al.) 201
GNNs need graphical attention expression to interpret. Neighborhood attention operation is a
popular way to implement attention mechanism on graphs (Velickovic al.) 2018 Hoshen 2017) by

---

Published as a conference paper at ICLR 2020
ALARO
AEWA SA SOHNE groppi
aPoot geiicii
concet Seaii
(a) The Alhlete task.
(b) The OrgamizationnfiirePereso task.
Figure 1: Subgraph visualization two examples from NELL995'ss test data. Each task has ten thousands of nodes and edges. The big yellow represents a given head and the big red represents a predicted tail. Color indicates attention gained along T step reasoning. Yellow means more attention during early steps while red means more attention at the end. Grey means less attention.
focusing on specific interactions with neighbors. Here, propose a new graphical attention mech- anism not only for computation but also for interpretation. We present three considerations when constructing attention- -nnduued-- subgraphs: (1) given a subgraph, we first attend within it select few nodes and then attend over those nodes' neighborhood for next expansion; (2) we propagate at- tention across steps to capture long-term dependency; (3) our attention mechanism models reasoning process explicitly through pipeline disentangled from underlying representation computing.
GNNs need input-dependent pruning to scale. GNNs are notorious for their poor scalability. Consider one message passing iteration on a graph with [V] nodes and EE| edges. Even the graph sparse, the complexity of O[EE] still problematic on large graphs with millions of nodes and edges. Besides, mini-batch based training with batch size B and high dimensions D would lead to E making things worse. However, we can avoid this situation by learning input-dependent pruning to run computation on dynamical graphs, as an input query often triggers a small fraction of the entire graph so that it is wasteful to perform computation over the full graph for each input.
Cognitive intuition of the consciousness prior. Bengio (017)) brought the notion of attentive awareness from cognitive science into deep learning in his consciousness prior proposal. He pointed out process of disentangling high-level factors from full underlying representation to form a low- dimensional combination through attention mechanism. He proposed to use two recurrent neural networks (RNNs) to encode two types of state: unconscious state represented by high-dimensional vector before attention and conscious state by a derived low-dimensional vector after attention.
We use two GNNs instead to encode such states nodes. We construct input dependeet subgraphs to run message passing efficiently, and also run full message passing over the entire graph to acquire features beyond local view constrained by subgraphs. We apply attention mechanism between the two GNNs, where the bottom runs before attention, called Inattentive GNN (IGNN), and the above runs on each attention-induced subgraph, called Attentive GNN (AGNN). IGNN provides representation computed on the full graph for AGNN. AGNN reinforces representation within a cohesive group of nodes to produce sharp semantics. Experimental results show that our model attains very competitive scores on HITS @ 1,3 and the mean reciprocal rank (MRR) compared to the best embedding- based method far. More importantly, we provide explanations while they do not.
2 ADDRESSING THE SCALE-UP PROBLEM
Notation. We denote training data by {( N- We denote a full graph by G = (V,E) with relations R and an input-dependent subgraph by G(æ) = (Vere), EG(a) which is an in- duced subgraph of G. We denote boundary of graph by 0G where Vac = N(Vc) Vo and (Va) means neighbors of nodes in Vg. We also denote high-order boundaries such as GGG where VaG = N(N(VG)) U N(Va) Vg- Trainable parameters include node embeddings (e, Jev.
2

---

Published as a conference paper at ICLR 2020
relation embeddings {e, hER, and weights used in two GNNs and an attention module. When per- forming full or pruned message passing, node and relation embeddings will be indexed according to the operated graph, denoted by 0 or GG()) For IGNN, use H' of size [ D to denote node hidden states step t; for AGNN,
H (a: of size |Va(=) D denote. The objective is written as Σm= (2 ysi G(r,)) 0g), where G(z;) is dynamically constructed.
The scale-up problem in GNNs. First, we write the full message passing in IGNN as
H fIGNN 0c))
(I)
where fIGNN represents all involved operations in one message passing iteration over G, including: (1) computing messages along each edge with the complexit of ((B)E))) (2) aggregating mes- sages received at each node with O ((B)))) and (3) updating node states with (BD]V For T-step propagation, the per-batch complexity is O (TB( ([E + [V])). Considering that backpropa- gation requires intermediate computation results to be saved during one pass, this complexity counts for both time and space. However, since IGNN is input-agnostic, node representations can be shared across inputs in one batch so that we can remove B to get O(DT((E) + [V])). If we sampled edge set & from such that |&| k[V1, the complexity can be further reduced to (DD(V))
The pruned message passing in AGNN can be written as
(x) = fAGNN (H' (x), H²; (c())-
Its complexity can be computed similarly as above. However, we cannot remove B. Fortunately, subgraph G(x) is not G. If we let æ be a node v, G(x) grows from a single node, i.e., (z) = {v), and expands itself each step, leading to a sequence of (G) ('))),))))))))) (x)..... GT Here, de- scribe the expansion behavior as consecutive expansion, which means no jumping across neighbor- hood allowed, so that can ensure that
(x) S G² (z) S G (x)
(3)
Many real-world graphs follow the small-world pattern, and the six degrees of separation implies (x) U G (x) R G. The upper bound of (xr) can grow exponentially in I, and there is no guarantee that G (x) will not explode.
Proposition. Given graph G (undirected or directed in both directions), we assume the probability of the degree of an arbitrary node being less than or equal to is larger than p. iee. P(deg(1) (V) d) > ps Vu E V. Considering a sequence of consecutively expanding subgraphs (Go, , Gl...., starting with GO = for all t 2 1, we can ensure
P(IVor1 < d(d ((d-1)'
(4)
d
The proposition implies the guarantee of upper-bounding (V)(w)) becomes exponentially looser and weaker as i gets larger even if the given assumption has a small d and a large p (close to 1). We define graph increment at step t as AG*(x) such that G*(z) (x) U (z). To prevent G (x) from explosion, we need to constrain (Z).
Sampling strategies. A simple but effective way to handle the large scale is to do sampling.
1. (z' å (z), (z), where sample nodes from the boundary of G²-1(x).
2. (z)(z) = aG* (z). where we take the boundary of sampled nodes from G (1r).
3. AG = âG (x) where we sample nodes twice from Gz- and from 0G (2)).
4. AG (z) = ÔG (x) where we sample nodes three times with the last from G. 1 (I)).
Obviously, we have 0G* S âGi-1(2) S (x) and Gt Ba (x) C G (x) U a (z)). Further, we let N, and N3 be the maximum number of sampled nodes in (G' and
the last sampling of (G) respectively and let N₂ be per-node maximum sampled neighbors in (x), and then we can obtain much tighter guarantee follow:
We assume per-example per-edge per-dimension time cost as unit time.
3

---

applied to àG*-1(a)) (x:). Note that the size of 0G* might be much larger we intend to sample Published as a conference paper at ICLR 2020
Σ logla
One Batch
(head, ref. !)
d [0. 11..00
a'
7
Vaosd
Thead
Attention Module
Yorw (Doodd
Vidua
V so
H
-
(')
H (K)
H (X)
M on Eggus
hop
Bast
Aud On
Attentive
Pooling or returning the last
1
V
H
H
H
M on
Inattentive GNN
Figure 2: Model architecture used in knowledge graph reasoning.
1. P((VAG)))) Ni 1)) n for (G)-)(x).
2. P(IVAGUZ)) 21 1 and (()) S N1-min(d-1,,a)) > n for dG 1
3. P((Vas)() (Ni N3)) for 8G'-1(x)
Attention strategies. Although we guarantee (oT(a)) S 1 1 T N2, by (x) and constrain the growth of Gx) by decreasing either Ni N2 Na, smaller sampling size means less area explored and less chance to hit target nodes. To make efficient selection rather than ran- dom sampling, apply attention mechanism to do the top- K selection where K can be small. We
change @Gr-1(xr) to (G* where represents the operation of attending over nodes and pick- ing the top-K. There are two types attention operations, one applied to Gz-((x) and the other
more nodes with larger N₂ to sufficiently explore the boundary. Nevertheless, we can address this problem by using smaller dimensions to compute attention, since attention on each node sealar requiring smaller capacity compared to node representation vectors computed in message passing.
3
DPMPN MODEL
3.1
ARCHITECTURE DESIGN FOR KNOWLEDGE GRAPH REASONING
Our model architecture shown in Figure consists of:
IGNN module: performs full message passing to compute full-graph node representations.
AGNN module: performs batch of pruned message passing to compute input-dependent node
representations which also make use of underlying representations from IGNN.
Attention Module: performs flow-style attention transition process, conditioned on node repre- sentations from both IGNN and AGNN but only affecting AGNN.
IGNN module. We implement it using standard message passing mechanism (Gilmer al. 2017) If the full graph has extremely large number of edges, we sample subset of edges, E C E randomly each step. For a batch of input queries, we let node representations from IGNN be shared across queries, containing no batch dimension. Thus, its complexity does not scale with batch size and the saved resources can be allocated to sampling more edges. Each node has state H., at step t, where the initial Hº:- e.. Each edge (u', v) produces message, denoted by M M.orrree) (ors,,)). step r. The computation components include:
4

---

Published as a conference paper at ICLR 2020
Message function: M (orr,,)) VIGNN (Hir. Cr. Heg) where (u',,, ET.
Message aggregation: M.:: my /N=(u) (v) Ev.,- M (o' (oim where (v',r,)) E
Node state update function: H Hep DIGNN(H,,) M en), where e V.
We compute messages only for sampled edges, (u',T, u) Êτ, each step. Functions VIGNN and JIGNN are implemented by a two-layer MLP (using leakyReL.u for the first layer and tanh for the second) with input arguments concatenated respectively. Messages sum by the square root of N" (v), the number of neighbors that send messages to v, preserving the scale of variance. We use residual adding to update each node state instead of GRU LSTM. After running for T steps, we output pooling result or simply the last, denoted by H H feed into downstream modules.
aggregated by dividing the
AGNN module. AGNN is input-dependent, which means node states depend on input query I (head, rel, ?), denoted by H ,., (z). We implement pruned message passing, running on small subgraphs each conditioned on an input query. We leverage the sparsity and only save H n. (x) for visited nodes VG*(z) When t = 0, we start from node head with V(*(=) = [Whead). When computing messages, denoted by M M (r..)). (2), we use an attending-sampliing campliingaatending procedure, explained in Section 3.2 to constrain the number of computed edges. The computation components
include:
Message function: M (v' (x) VAGNN (., (x), H (x)),, where (v',r, (x and (x) (er: qhead greil represents context vector.
Message aggregation: M
M.,. (x) (N)(o) Evi, M (or,,,) where ,,,,,,)) E E
Node state attending function: (x) = 0 1++ W WHe.; where af is an attention score.
Node state update function: H (x) (x) AAGNN H (1), M (2). c (x)), where H (x),
(x) (x)
qhead: (ret] also represents context vector.
Query context is defined by its head and relation embeddings, i.e., qread Cheed and grei = Crel- We introduce node state attending function to pass node representation information from IGNN to AGNN weighted by a scalar attention score af+1 and projected by learnable matrix W. We initialize H (x) = Hy. for node v E VGo(z), letting unseen nodes hold zero states.
Attention module. Attention over T steps is represented by sequence of node probability dis- The initial distribution a" a one-hot vector with
tributions, denoted by a' (t = 1, 1,2...,21 a [Vhhedd]] 1. To spread attention, we need to compute transition matrices T" each step. Since is conditioned on both IGNN and AGNN, we capture two types of interaction between u' and v: H (x) ~ H,,(,),, (x), and H', (x)) Ho,-- The former favors visited nodes, while the latter is used to attend to unseen neighboring nodes.
T for = softmax Σ, on (H),),()) (c) + (c)) (2 H (x()) (x), Ho:))
(1(-) = MLP(H (x), T W.IMP(H.
02 MLP(H , (W)) (x))
where Wi and W2 are two learnable matrices. Each MLP uses one single layer with the leaky ReLu activation. To reduce the complexity for computing T',
nodes v' V which contains
G'(z)
nodes with the k-largest attention scores at step t, and use nodes sampled from e'ss neighbors to compute attention transition for the next step. Due to the fact that nodes of result from the top-k pruning, the loss of attention may occur diminish the total amount. Therefore, we use renormalized version, a"
a' | a' [], to compute new attention scores. We use attention scores the final step as the probability to predict the tail node.
II practice, we smaller of edges than FGG(()) pass messages as discussed in Section 3.2
5

---

Published as a conference paper at ICLR 2020
Full Neightorhood
Full Neighborhood
Sampling
Sampling Horizon
Attending to Horizon
Attending Hortzon
Attending
Attending- Horizon
Visited Nores
Visited Nodes
Figure 3: Iterative attending--ampllng-tttee procedure balancing coverage and complexity.
3.2 COMPLEXITY REDUCTION BY ITERATIVE ATTENDING, SAMPLING AND ATTENDING
AGNN deals with each subgraph relying on input and keeps a few selected nodes in Vat(z) called visited nodes. Initially, (z)(z) contains only one node Uhead, and then Vo((x) is enlarged by adding new nodes each step. When propagating messages, we can just consider the one-hop neighborhood each step. However, the expansion goes so rapidly that covers almost all nodes after a few steps. The key address the problem is constrain the scope of nodes we can expand the boundary from, i.e. the core nodes which determine where we can go next. We call it the attending-from horizon,
G (3)),, selected according to attention scores a'. Given this horizon, we may still need node sam- pling over the neighborhood N (x)) in some cases where a hub node of extremely high degree exists to cause an extremely large neighborhood. We introduce an attending-tt -oo horizon, denoted by
)
(GG(()) inside the sampling horizon, denoted by ((G(())). The attention module runs within the sampling horizon with smaller dimensions exchanged for sampling more neighbors for larger coverage. In one word, we face a trade-off between coverage and complexity, and our strategy is to sample more but attend less plus using small dimensions to compute attention. We obtain the attending-to to horizon according to newly computed attention scores a'+1, Then, message passing
iteration at step t in AGNN can be further constrained on edges between Gz)z and (G)()=)), smaller set than EG((s) We illustrate this procedure in Figure 3
EXPERIMENTS
Datasets. We use six large KG datasets: FBISK FB15K-231 WN18, WNISRR, NELL995, and YAGO3-10. FB15K-237 (Toutanova & Chen 2015) sampled from FBISK (Bordes et al. 2013) with redundant relations removed, and WNT&RR (Detmees et al., 2018) is a subset of WNI8 (Bor-) des et al. 2013) removing triples that cause test leakage. Thus, they are both considered more challenging. NELL995 (Xiong al.) 2017) has separate datasets for 12 query relations each corre- sponding to a single-query-relation KBC task. YAGO3-10 (Mahdisoltaní largest KG with millions of edges. Their statistics shown in Table | We find some statistical differences between train and validation (or test). In a KG with all training triples as its edges, a multi-edge triple if the KG contains other triples that also
al. 2014) contains the
triple (head, rel, tail) is considered connect head and tail ignoring the direction. We notice that FB15K 5K-237 is special case compared the others, as there are no edges in its KG directly linking any pair of head and tail in valida- tion (or test). Therefore, when using training triples as queries to train our model, given a batch, for 1515K- we cut off from the KG all triples connecting the head-tail pairs in the given batch, ignoring relation types and edge directions, forcing the model to learn a composite reasoning pattern rather than a single-hop pattern, and for the rest datasets, we only remove the triples of this batch and their inverse from the KG to avoid information leakage before training on this batch. This can be regarded as a hyperparameter tuning whether to force a multi-hop reasoning or not, leading to a performance boost of about 2% in HITS @ I on FB15-237.
Experimental settings. We use the same data split protocol as in many papers (Dettmers et al. 2018 Xiong et al. 2017 Das al. 2018). We create a KG, directed graph, consisting of all train triples and their inverse added for each dataset except NELL995, since it already includes reciprocal relations. Besides, every node in KGs has a self- edge to itself. We also add inverse relations into the validation and test set to evaluate the two directions. For evaluation metrics, we use HITS@ 1,3, 10 and the mean reciprocal rank (MRR) in the filtered setting for FB15K -337,, WN WN18RR,

---

Published as a conference paper at ICLR 2020
Table 1: Statistics of the six KG datasets. PME (tr) means the proportion of multi-edge triples in
train; PME (va) means the proportion of multi-edge triples in validation; AL (va) means the average length of shortest paths connecting each head-tail pair in validation.
Dataset
#Entities
#Rels
#Train
#Valid
#Test
PME (tr)
PME (va)
AL (va)
FBI5K
14,951
1,345
483,142
50,000
59,071
81.2%
80.6%
1.22
FB15K-237
14,541
237
272,115
17,535
20,466
38.0%
0%
2.25
WN18
40,943
18
141,442
5,000
5,000
93.1%
94.0%
1.18
WNISRR
40,943
11
86,835
3,034
3,134
34.5%
35.5%
2.84
NELL995
74,536
200
149,678
543
2,818
100%
31.1%
2.00
YAGO3-10
123,188
37
1,079.040
5,000
5,000
56.4%
56.0%
1.75
Table 2: Comparison results on the FB15K-237 and WN18RR datasets. Results of are taken
from (Nguyen et al. 2018). [+] from (Dettmers et al., 20188) [C] from (Shen et al. 2018), [+] from
(Sun al.) (2018). 9 [A] from (Das et al. 2018), and [+]] from (Lacroix et al. 2018) Some collected
results only have metric score while some including ours take the form of "mean (std)".
FB15K-237
WNI8RR
Metric (%)
H@1 1
H@3
H@
MRR
H@l
H@3
H@ 10
MRR
TransE
46.5
29.4
50.1
22.6
DistMult [
15.5
26.3
41.9
24.1
39
44
49
43
DistMult [
20.6 (.4)
31.8 (.2)
29.0 (.2)
38.4 (44)
42.4 (.3)
41.3 (.3)
ComplEx
15.8
27.5
42.8
24.7
41
46
51
44
ComplEx [V]
20.8 (.2)
32.6 (.5)
29.6 (.2)
38.5 (.3)
43,9 (.3)
42.2 (.2)
ConvE
23.7
35,6
50.1
32.5
40
44
52
43
ConvE [
23.3 (.4)
33.8 (.3)
30.8 (.2)
39.6 (.3)
44.7
43.3 (.2)
RotatE [
24.1
37.5
53.3
33.8
42.8
49.2
57.1
47.6
ComplEx-N3112
56
37
57
48
NeuralLP [+]
18.2 (.6)
27.2 (13)
24.9 (.2)
37.2 (.1)
43.4
43.5 (.1)
MINERVA [V]
14.1
23.2 (.4)
20.5 (:3)
35.1 (.1)
44.5 (.4)
40.9 (.1)
MINERVA [A]
45.6
41.3
45.6
51.3
M-Walk [V]
(.3) 24.3 (:2)
23.2 (.2)
(.1)
44.5 (.2)
43.7 (.1)
DPMPN
28.6 (.1)
40,3 (.1)
53.0 (.3)
36.9 (.1)
(A4)
49.7 (18 55.8 (.5)
48.2 (.5)
FB15K, WN18, and YAGO3-10, and use the mean average precision (MAP) for NELL995's single- guery-relation KBC tasks. For NELL995, we follow the same evaluation procedure as in (Xiong ct al. 2017: Das al. 2018 Shen et al. 2018), ranking the answer entities against the negative examples given in their experiments. We run our experiments using a 12G-memory GPU, TITAN X (Pascal), with Intel(R) Xeon(R) CPU E5-2670 v3 @ 2.30GHz. Our code is written in Python based on TensorFlow 2.0 and NumPy 1.16 and can be found by the link below. We run three times for each hyperparameter setting per dataset report the means and standard deviations. See hyperparameter details in the appendix.
Baselines. We compare our model against embedding- approaches, including TransE (Bordes et al. 2013), TransR (Lin et al.) 20155). DistMult (Yang et al. 2015). ConvE (Dettmers et al. 2018 ComplE (Trouiloon et al., 2016), HolE (Nickel et al.) 2016). RotatE (Sun et al., 2018), and ComplEx-N3 (Lacroix et al. 2018). and path-based approaches that use RL methods, including DeepPath (Xiong et al. (017). MINERVA (Das al.] [018)) and M-Walk (Shen al. 2018). and also that uses learned neural logic, NeuralLP (Yang al. (007).
Comparison results and analysis. We report comparison on FB15K-23 and WN18RR in Table Our model DPMPN significantly outperforms all the baselines in HITS @ 1,3 and MRR. Compared to the best baseline, we only lose a few points in HITS 10 but gain a lot in HITS@ 1.3. We speculate that it is the reasoning capability that helps DPMPN make sharp prediction by exploiting graph-structured composition locally and conditionally. When a target becomes too vague to predict, reasoning may lose its advantage against embedding- based models. However, path- base- baselines, with a certain ability to do reasoning, perform worse than we expect. We argue that it might be inappropriate think of reasoning, a sequential decision process, equivalent to a sequence of nodes. The average lengths of the shortest paths between heads and tails as shown in Table ] suggests a very short path, which makes the motivation of using a path almost useless. The reasoning pattern should be modeled in the form of dynamical local graph-structured pattern with nodes densely connected
7

---

Published as conference paper at ICLR 2020
(A) Cenvergence Analysis (eval test)
(8) IGNN Component Analysis
(C) Sampling Horizon Analys
H@1
W/o IGNN
54
Max samplig per-nn--e--dee
57.5
H@3
57.5
Max-sampling seaaaaaningggeeee pemppig-------dee
H@10
52
max-sampling--erraee
55.0
MMR
55.0
pax-ssemlinn-per-nnee 200
Maticc Scare (%)
50
Max-sampling-ger-ooo 400
52.5
52.5
Metric Score
50.0
50.0
47.5
47.5
45.0
45.0
42
40.0
40.0
40
H@0
H
HgB0
H@1
Epoch
(D) Attending-fo to Horizon Analysis
(E) Attanding- froommm Horizon Analysis
(F) Searching Horizon Analysis
55.0
Max-attaddng--a -tr-rnng---------ppppp--
54
Max-atteding-from
Stops-in-AGht
Max-atteding maxx-atteding-t----re- -to-per-step
50
Max-atteding--ror frorn--er--lee 10
52.5
Steps-in-AGHe
Max-attading-Bt ting-tt--r---tpp 100
Max-atteding-froet from-per-step- 20
Staps-in-AGht
Max aexediigddinge to--torrtttt to-per-step
200
Max-atteding from- from-por--tttee ser-ptep--------
40
50.0
Staps-in-AGht
Metric Score (%6
Max-atteding
400
47.5
48
46-
Meuric
66-
Metric
42.5
44-
44-
42
37.5
35.0
H@1
MMR
H@l
MR
H@1
MMR
Figure 4: Experimental analysis on WN18RR. (A) Convergence analysis: we pick six model snap-
shots during training and evaluate them on test. (B) IGNN component analysis: w/o IGNN uses step to run message passing, while with IGNN uses two; (C)-(F Sampling, attending-to, attending- from and searching horizon analysis. The charts on FB15K-237 can be found in the appendix.
with each other to produce a decision collectively. We also run our model on FBISK, WN18, and YAGO3-10, 10, and the comparison results in the appendix show that DPMPN achieves a very competitive position against the best state of the art. We summarize the comparison on NELL995's tasks in the appendix. DPMPN performs the best on five tasks, also being competitive on the rest.
Convergence analysis. Our model converges very fast during training. We may use half of train- ing queries to train model to generalize as shown Figure A). Compared to less expensive smbedding-basee models, our model need to traverse a number of edges when training on one input, consuming much time per batch, but it does not need to pass a second epoch, thus saving lot of training time. The reason may be that training queries also belong to the KG's edges and some might be exploited to construct subgraphs during training on other queries.
Component analysis. Given the stacked GNN architecture. want to examine how much each GNN component contributes to the performance. Since IGNN is input-agnostic, we cannot rely on its node representations only predict tail given an input query. However, AGNN is input- dependent, which means it can be carried out to complete the task without taking underlying node representations from IGNN. Therefore, we can arrange two sets of experiments: (1) AGNN + IGNN, and (2) AGNN-only. In AGNN-only, we do not run message passing in IGNN to compute H., but instead use node embeddings Hy.., and then we run pruned message passing in AGNN as usual. We want to be sure whether IGNN is actually useful. In this setting, we compare the first which runs IGNN for two steps against the second one which totally shuts IGNN down. The results in (B) (and Figure B) in Appendix) show that IGNN brings an amount of gains in each metric on WN18RR (and F315K-23), indicating that representations computed by full-graph message passing indeed help subgraph-based message passing.
Horizon analysis. The sampling, attending-to, attending-from and searching (i.e., propagation steps) horizons determine how large area subgraph can expand over. These factors affect com- putation complexity as well as prediction performance. Intuitively, enlarging the exploring area by sampling more, attending more, and searching longer, may increase the chance of hitting target to gain some performance. However, the experimental results Figure (C(D) show that is not always the case. In Figure E),
that increasing the maximum number of attending-
8

---

Published as a conference paper at ICLR 2020
Analyse (on entreyy
18)
Analysts rtool' proporton))
(C)
Analyda aesportion:
(D)
Analys nepp's proportion)
10
1.00
1.00
1.00
8
0.50
0.50
0.50
0.25
0.25
Motrr Ray strape
0.00
0.00
-3.25
Rondle
-0.50
Saaadrg Testr Tangg
3.75
0.75
0.75
Figure 5: Analysis of attention flow on NELL995 tasks. (A) The average entropy of attention distributions changing along steps for each single-query-relation KBC task. (B)()DD) The changing of the proportion of attention concentrated at the 1,,-1,3,5 nodes per step for each task.
Wime
Time Ootton
Hau-sampiin per 28
dingtt ctop
atccatiding Pirm per dep-
Batth-ce-
Masusmpling node 35
Mas www.aatdddirrroooooo plrr
Traeers Timeett Spo.phocho
Batdho ez
Manosmpiing 250
www.iiigiiaa 201
Mux weiidiiiiiteeeee parper 40
#SA -3
Baltho 383
Maxosmpling ing per perirade 420
Misv gr stap 402
Figure 6: Analysis of time cost WN18RR: (A)-DD) measure the one-epoch training time dif- ferent horizon settings corresponding to Figure [C)(FF); (E) measures on different batch sizes us- ing horizon setting Max-ssampinng--e---dde- 2tep=20, and #Steps-in-AGNN-88 The charts on FB15K-237 can be found in the appendix.
Max-aatendingg-t---er-s-e-e
from nodes per step is useful. That also explains why we call nodes in the attending from horizon the core nodes, as they determine where subgraphs can be expanded and how attention will be propagated to affect the final probability distribution on the tail prediction. However, GPUs with limited memory do not allow for a too large number of sampled or attended nodes especially for The detailed explanations can be found in attention strategies in Section 2 where the upper bound is controlled by N, N2 and N3 (Max-attending- -attending-rro---eeee from-per-step corresponding N2, and Max-attending-toppe
to Ng). In N2, Section 3.2 sug- gests that should sample more by large N2 but attend less by small N1. Figure([r) suggests that the propagation steps of AGNN should not go below four.
N1. sanpling-per-nent
Attention flow analysis. If the flow-style attention really captures the way reason about the diverging-converge thinking pattern. Intuitively, first, search and collect ideas as much
world, its process should be conducted for the diverging thinking phase, converging thinking phase, we try to concentrate our thoughts on one point. To check whether the attention flow has such a pattern, we measure the average entropy of attention distributions changing along steps and also the proportion of attention concentrated at the 1op-1.3,5 nodes. As we expect, attention more focused at the final step and the beginning.
can; then, for the
Time cost analysis. The time cost is affected not only by the scale of a dataset but also by the horizon setting. For each dataset, we list the training time for one epoch corresponding hyperparameter settings in the appendix. Note that there is always and performance. We thus study whether we can reduce time cost a lot at the price of sacrificing a little performance. We plot the one-epoch training time in Figure (D)) using the same settings as we do in the horizon analysis. We can see that -ateending-from-per affect the training time significantly while Max-sampling per- and Max- dax--ateeniin-- to-per-siee step affect very slightly. Therefore, we can use smaller Max Max-sanpling campling-per-nut per-node and Max-attene aat-aannnning to-per- per-etetpp in order gain larger batch size, making the computation more efficiency shown in Figure 6
our standard orfde-off between complexity
and #Steps-in-AGNi in-AGNN
To further demonstrate the reasoning capability, we show visualization results of some pruned subgraphs NELL995's test data for 12 separate tasks. We avoid using the training data in order to show generalization of the learned reasoning capability. We show the visualization results in Figure I See the appendix for detailed analysis and more visualization results.
Visualization.

---

Published as a conference paper at ICLR 2020
Discussion of the limitation. Although DPMPN shows promising way to harness the scalability on large-scale graph data, current GPU-based machine learning platforms, such as TensorFlow and PyTorch, seem not ready to fully leverage sparse tensor computation which acts as building blocks to support dynamical computation graphs which varies from one input to another. Extra overhead caused by extensive sparse operations will neutralize the benefits of exploiting sparsity.
RELATED WORK
Knowledge graph reasoning. Early work, including TransE (Bordes al. 2013) and its analogues
[Wang et al. 2014 Lin et al. 50 Ji et al. 2015). DistMult (Yang et al. 2015), ConvE (Dettmers)
al., 2018) and ComplEx (Trouillon et 2016). focuses learning embeddings of entities and relations. Some recent works of this line (Sun et al.
2018 Lacroix et al.] 2018) achieve high accu- racy, Another line aims learn inference paths (Lao et al. 2011] Guu et al. [215] Lin et al., 2015a] Toutanova et al. 2016; Chen et al. [2018] Lin et al. 2018) for knowledge graph reasoning, especially DeepPath (Xiong et al. 2017), MINERVA (Das et 2018), and M- M-Walk (Shen et al. 2018). which use RI. to learn multi-hop relational paths. However, these approaches, based on policy gradients or Monte Carlo tree search, often suffer from low sample efficiency and sparse rewards, requiring a large number of rollouts and sophisticated reward function design. Other efforts include learning soft logical rules (Cohen 2016 Yang et al. 2017) or compostional programs (Liang et al. 2016).
Relational reasoning in Graph Neural Networks. Relational reasoning is regarded the key for combinatorial generalization, taking the form of entity- and relation-centriy organization to reason about the composition structure of the world (Craik) 1952 Lake et al. 2017). A multitude of recent implementations (Battaglia lia et al., (018)) encode relational inductive biases into neural networks to exploit graph-structured representation, including graph convolution networks (GCNs) (Bruna al., Henaff et al. 20155] Duvenaud et al. [2015] Kearnes et al. 2016 Defferrard et al. Nicpe
2014
al.
2016 Kipl & Welling Bronstein al. 2017) and graph neural networks (Scarselli al.j Li et al., 2016; Santoro et al. 2017] Battaglia et al. 2016; Gilmer et al. 2017). Variants of
2009
GNN architectures have been developed. Relation networks (Santoro et al.] 2017) use a simple
but effective neural module to model relational reasoning, and its recurrent versions (Santoro et al.)
2018 Palm et al. 2018) do multi-step relational inference for long periods; Interaction networks Battaglia et al. 2016)) provide general-purpose learnable physics engine, and two of its variants visual interaction networks (Watters et al. (017)) and vertex attention interaction networks (Hoshen)
2017]; Message passing neural networks (Gilmer al. 2017) unify various GCNs and GNNs into a general message passing formalism by analogy to the one in graphical models.
enhance GNNs' repre- sentation power (Velickovic et al.) 20018: Hoshen 2017] Wang et al.) 2018) Kool, 2018). These approaches often use multi-head self-attention focus on specific interactions with neighbors when aggregating messages, inspired by (Bahdanau et al.] 2015 Lin et al.] 2017] Vaswani et al.) 2017). Most graph-based attention mechanisms attend over neighborhood in a single-hop fashion, and (Hoshen] 2017) claims that the multi-hop architecture does not help to model high-order interac- tion experiments. However, a ftow-style design of attention in (Xu et al. (018b) shows a way to model long-range attention, stringing isolated attention operations by transition matrices.
Attention mechanism on graphs. Neighborhood attention operation
6 CONCLUSION
We introduce Dynamically Pruned Message Passing Nenworks (DPMPN) and apply it to large-scale knowledge graph reasoning tasks. We propose to learn an input-dependent local subgraph which is progressively and selectively constructed to model a sequential reasoning process in knowledge graphs. We use graphical attention expression, flow-style attention mechanism, to guide and prune the underlying message passing, making it scalable for large-scale graphs and also providing clear graphical interpretations. We also take the inspiration from the consciousness prior to develop a two-GNN framework to boost experimental performances.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. CoRR, (tss/1409.0433.. 2015.
Peter W. Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, and Koray Kavukcuoglu. Interaction networks for learning about objects, relations and physics. In NIPS, 2016.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanzaez-Gonzalez, Vinícius Flo- res Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pas- canu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1806.01261, 2018.
Yoshua Bengio. The consciousness prior. CoRR, abs/1709.08 2017.
Antoine Bordes, Nicolas Usumier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NIPS, 2013.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34:18-42, 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. CoRR, fos/1312.6203 2014.
Wenhu Chen, Wenhan Xiong, Xifeng Yan, and William Yang Wang. Variational knowledge graph reasoning, In NATCL-HLT, 2018.
William W. Cohen. Tensorlog: A differentiable deductive database. CoRR, abs/1605.06523, 2016.
Kenneth H. Craik. The nature of explanation. 1952.
Rajarshi Das, Shchzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krish- namurthy, Alexander J. Smola, and Andrew McCallum. Go for walk and arrive the answer: Reasoning over paths in knowledge bases using reinforcement learning. CoRR, abs/1711.05851, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. AAAI, 2018
David K. Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparrauunn Iparraguire, Rafael Kömez-Bombarelli, Timothy Hirzel, Alán Sspuru-Guzil and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS, 2015.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Kelvin Guu, John Miller, and Percy S. Liang. Traversing knowledge graphs in vector space. In EMNLP, 2015.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. CoRR, Abs/1506.001633 2015.
Yedid Hoshen. Vain: Attentional multi-agent predictive modeling. NIPS, 2017.
Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jian Zhao. Knowledge graph embedding via dynamic mapping matrix. In ACI,, 2015.
11

---

Published as a conference paper at ICLR 2020
Steven M. Kearnes, Kevin McCloskey, Mare Berndl, Vijay S. Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer- molecular design, 30 8:595-608, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. CoRR, 0es//600002200) 2017.
Wouter Kool. Attention solves your tsp approximately. 2018.
Timothée Lacroix. Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. In ICMI., 2018.
Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J Gershman. Building machines that learn and think like people. The Behavioral and brain sciences, 40:e253, 2017.
Ni Lao, Tom Michael Mitchell, and William W. Cohen. Random walk inference and learning in large scale knowledge base. In EMNLP, 2011.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. CoRR, 11.1511.. 2016.
Chen Liang, Jonathan Berant, Quoe V. Le, Kenneth D. Forbus, and Ni Lao. Neural symbolic ma- chines: Learning semantic parsers on freebase with weak supervision. In ACL, 2016.
Xi Victoria Lin, Richard Socher, and Caiming Xiong. Multi-hop knowledge graph reasoning with reward shaping. EMNLP, 2018.
Yankai Lin, Zhiyuan Liu, and Maosong Sun. Modeling relation paths for representation learning of knowledge bases. In EMNLP, 2015a.
Yankai Lin, Zhiyuan Liu, Maosong Sun, Yang Liu, and Xuan Zhu. Learning entity and relation embeddings for knowledge graph completion. In AAAI, 2015b.
Zhouhan Lin, Minwei Feng, Cícero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and
Yoshua Bengio. A structured self-attentive sentence embedding. CoRR, abs/1703.031 2017.
Farzaneh Mahdisoltani, Joanna Asia Biega, and Fabian M. Suchanek. Yago3: A knowledge base from multilingual wikipedias. In CIDR, 2014.
Dai Quoe Nguyen, Tu Dinh Nguyen, Dat Quoc Nguyen, and Dinh Q. Phung. A novel embedding model for knowledge base completion based on convolutional neural network. NAACL-HLT, 2018.
Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowl- edge graphs. In AAAI, 2016.
Mathias Niepert, Mohammed Hassan Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In ICML, 2016.
Rasmus Berg Palm, UIrich Paquet, and Ole Winther. Recurrent relational networks. In NeurlPS, 2018.
Adam Santoro, David Raposo, David G. T. Barrett, Mateusz Malinowski, Razvan Pascanu, Peter W. Battaglia, and Timothy P. Lillierap. simple neural network module for relational reasoning. In NIPS, 2017.
Adam Santoro, Ryan Faulkner, David Raposo, Jack W. Rae, Mike Chrzanowski, Théophane Weber, Daan Wierstra, Oriol Vinyals, Razvan Pascanu, and Timothy P. Lillicrap. Relational recurrent neural networks. In NeurIPS, 2018.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Nenworks, 20:61-80, 2009.
Yelong Shen, Jianshu Chen, Pu Huang, Yuqing Guo, and Jianfeng Gao. M-walk: Learning to walk graphs using monte carlo tree search. In NewrlPS, 2018.
12

---

Published as a conference paper at ICLR 2020
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. CoRR, abs/1902.10197, 2018.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality. 2015.
Kristina Toutanova, Victoria Lin, Wen tau Yih, Hoifung Poon, and Chris Quirk. Compositional learning embeddings for relation paths in knowledge base and text. In ACL, 2016.
Théo Trouillon, Johannes Welbi, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. ICML, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, 2017.
Petar Velickovic, Guillem Cucurall, Arantxa Casanova, Alejandro Romero, Pietro Lió, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710.10903, 2018.
William Wang. Knowledge graph reasoning: Recent advances, 2018.
Xiaolong Wang, Ross B. Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7794-7803, 2018.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by trans- lating hyperplanes. In AAAI, 2014.
Nicholas Watters, Daniel Zoran, Théophane Weber, Peter W. Battaglia, Razvan Pascanu, and Andrea Tacchetti. Visual interaction networks: Learning physics simulator from video. In NIPS, 2017.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ArXiv, abs/18 1iss/880,,0,26, 2018a.
Xiaoran Xu, Songpeng Zu, Chengliang Gao, Yuan Zhang, and Wei Feng. Modeling attention flow on graphs. CoRR, abs/ htss/1811.0049,, 2018b.
Bishan Yang, Wen tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. CoRR, abs/1412.6675, 2015.
Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowl- edge base reasoning. In NIPS, 2017.
13

---

Published as a conference paper at ICLR 2020
Appendix
7 PROOF
Proposition. Given graph (undirected or directed in both directions), we assume the probability
of the degree of an arbitrary node being less than or equal to is larger than p. i.e, P(deg(U)
d) P, Vu E V. Considering a sequence of consecutively expanding subgraphs (G), G starting with G = {u), for all 2 1, we can ensure
d(d
1)¹ ((d-1)"-3
did d(a-11
P(IVod1 < d 2-2 2
(6)
Proof. We consider the extreme case of greedy consecutive expansion, where G 1 UAG Gt-1 U 0G since if this case satisfies the inequality, any case of consecutive expansion can also satisfy it. By definition, all the subgraphs G are a connected graph. Here, we use AV' denote VaG for short. In the extreme case, we can ensure that the newly added nodes AV at step & belong to the neighborhood of the last added nodes AVt-1 Since for 2 each node Avt-1 already has at least one edge within Gt-1 due to the definition of connected graphs, we can have
P(AVI < |AV' (d - 1)) > -
For t I, we have P(IAVI S >> p and thus
P(IVoil S + d) > p.
(8)
For 2 2, based on |Vo. = 1 |V + ..... AV', we obtain
P([Vod 51+ d d(d + ... d(d 1)(-1) p +
which is
P(IVod v d(d - 1)¹ -2 2
2 -2
(10)
We can find that also satisfies this inequality.
14

---

Published as a conference paper at ICLR 2020
8 HYPERPARAMETER SETTINGS
Table 3: Our standard hyperparameter settings we use for each dataset plus their one-epoch training time. For experimental analysis, only adjust one hyperparameter and keep the remaining fixed as the standard setting. For NELL995, the one-epoch training time means the average time cost of the 12 single-quey--relatio tasks.
Hyperparameter
FBISK 237
FBI5K
WNI8RR
WNI8
YAGO3-10
NELL995
batchasize
80
80
100
100
100
10
n dims att n_dims
50
50
50
50
50
200
100
100
100
100
100
200
max sampling per step (in IGNN)
10000
10000
10000
10000
10000
10000
max.atiending ffom trom-ppersstep
20
20
20
20
20
100
max_sampling. crumpling-per ppr mode (in AGNN)
200
200
200
200
200
1000
max attending per step
200
200
200
200
200
1000
JGNN
2
I
1
I
n_steps_in jan_iinNNNNN
6
6
8
6
5
learning rate
0.001
0.001
0.001
0.001
0.0001
0.001
optimizer
Adam
Adam
Adam
Adam
Adam
Adam
grad.coipnorm
n.epochs
3
One-epoch training time (h)
25.7
63.7
4.3
8.5
185.0
0.12
The hyperparameters can be categorized into three groups:
Normal hyperparameters, including batch_size, n_dims aatt, n_dims, learning-rate grad.ccipnorm, and n.epochs. We set smaller dimensions, n.dims for computation in the attention module, as it uses more edges than the message passing uses in AGNN, and also intuitively, it does not need to propagate high-dimensional messages but only compute scalar scores over sampled neighbor- hood, in concert with the idea in the key-value mechanism (Bengio (017). We set n_epochs in most cases, indicating that our model can be trained well by one epoch only due to its fast convergence.
horizon, including max sampling step that controls the maximum number to sample edges per step in IGNN, and max vux_ssamlinggpes paalliinnpee__ede per_node, max max__tteediing fronnnggfooorrrrm from_per step and max aattending vo_per_step that control the maximum number to sample neighbors of each selected node per step per input, the maximum number of selected nodes for attending-from per step per input, and the maximum number of selected nodes in sampled neighborhood for attending-to to per step per input in AGNN.
The hyperparameters
charge
the sampling-attendinn
The hyperparameters in charge of the searching horizon, including n_steps_in in JGNN representing the number of propagation steps to run standard message passing IGNN, and n n_steps AGNN representing the number of propagation steps to run pruned message passing in AGNN.
Note that we tune these hyperparameters according to not only their performances but also the computation resources available us. In some cases, deal with very large knowledge graph with limited resources, we need to make a trade-off between efficiency and efffectiveness. For example, each of NELL995's single-query-relation tasks has small training set, though still with a large graph, so we can reduce the batch size in favor of affording larger dimensions and a larger sampling- attending horizon without any concern for waiting too long finish one epoch.
15

---

Published as a conference paper at ICLR 2020
MORE EXPERIMENTAL RESULTS
Table 4: Comparison results on the FB15K and WN18 datasets. Results [+] are taken from
NNickel et al.
2016), [+] from (Dettmers al. 2018), [ from (Sun et al. 2018 [9] from (Yang
et al. 2017) and from (Lacroix et al. 2018). Our results take the form of "maan (std)".
FBI5K
WNI8
Metric (%)
H@
H@3
H@ 10
MRR
H@1
H@3
H@ 10
MRR
TransE
29.7
57.8
74.9
46.3
11.3
88.8
94.3
49.5
HolE
40.2
61.3
73.9
52.4
93.0
94.5
94.9
93.8
DistMult [+)
54.6
73.3
82.4
65.4
72.8
91.4
93.6
82.2
ComplEx [+]
59.9
75.9
84.0
69.2
93.6
93.6
94.7
94.1
ConvE [
55.8
72.3
83.1
65.7
93.5
94.6
95.6
94.3
RotatE [
74.6
83.0
88.4
79.7
94.4
95.2
95.9
94.9
ComplEx N3 [+]]
91
86
96
95
NeuralLP [9]
83.7
94.5
DPMPN
72.6 (.4) 78.4 (.4) 83.4 (.5) 76.4 (.4) 91.6 91.6
93.6 (.4)
94.9 (.4)
92.8 (.6)
Table 5: Comparison results the YAGO3-10 dataset. Results of are taken from Dettmers et al. 2018). [+] from (Lacroix et al. 2018). and [+]] from (Lacroix et al. 2018).
YAGO3-10
Metric (%)
H@I 1
H@3
H@ 10
MRR
DistMult
24
38
54
34
ComplEx
55
ConvE
35
49
62
ComplEx-N3 [X]
71
58
DPMPN
48.4
59,5
67.9
55.3
Table 6: Comparison results of MAP scores (%) on NELL995's single-query-relation KBC tasks.
We take baselines' results from (Shen al. 2018). No reports found on the last two in the paper.
Tasks
NeuCFlow
M-Walk
MINERVA
DeepPath
Transh:
TransR
AthletePlaysFor Team
(0.5)
84.7 (1.3)
82.7 (0.8)
72.1 (1.2)
62.7
67.3
AthlctePlaysinI.camm League
(0.1)
97.8 (0.2)
95.2 (0.8)
92.7 (5.3)
77.3
91.2
AthettumomSStadium
93.6 (0.1)
(0.1)
92.8 (0.1)
(0.8)
71.8
72.2
AthletePlaysSport
98.6 (0.0)
98.3 (0.1)
(0.1)
91.7
87.6
96.3
TeamPlayssport
(0.4)
(8.8)
87.5
69.6
76.1
81.4
94.7 (0.3)
95.0 (0.7)
94.3
79.0)
62.0
65.7
WorksFor
86.8 (0.0)
84.2 (0.6)
82.7 (0.5)
69.9
67.7
69.2
PorsoniorrnnLocation
84.1 (0.5)
(0.0)
78.2 (0.0)
75.5
71.2
81.2
PersonLeadsOng
88.4(..1)
88.8 (0.5)
83.0
79.0
75.1
77.2
OrgHiredPerson
84.7 (0.8)
88.8 (0.6)
87.0
73.8 (1.9)
71.9
73.7
TocnnBeeongSToorg
89.3 (1.2)
TeamPlaysInI.cag
(0.3)
16

---

Published as conference paper at ICLR 2020
(A) Convergence Analysis (eval on test)
(9) IGNN Component Analysis
(C) Sampling Horizon Analysis
55
45.0
H@1
Max sax-sampling pennnnnngeeenndd
H0-0
H@3
50
With IGNN
42.5
Max-sampling-prre sanng-----oddee 50
Max-sampling 100
40.0
Max-sampling-eerree per-node 200
Metric Score (99)
45
37.5
40
Metric
32.5
27.5
25
0.5
1.0
1.5
2.0
2.5
3.0
H@1
H8
H@10
MMR
H@1
MMR
Epoch
(D) Attending to
Analysis
(E)
Attending-from Analysis
(F) Searching Analysis
45.0
45.0
45
Max atteding to per step
Max Max-enteding from penstep 5
Staps AnAN
Max-atteding -to-pe--seep
Max-atteding-from perstep
Steps-in-AGMM
Max-atteding mex--atteding-to-pe -t--pe----ttppp 100
Max-atteeding-for--- from-per--tep 20
40
Steps-in-AGHN
40.0
Max-atteding tt-pers-tpppppppppppp-
40.0
Metric Score (90
35
35.0
35.0
30-
Metn:
Metrt
25
30.0
30.0
20
27.5
25.0
H@1
MMR
H@1
MMR
H@1
MMR
Figure 7: Experimental analysis FB15K-237. (A) Convergence analysis: pick six model snapshots at time points of 0.3, 0.5, 0.7, 1, 2, and 3 epochs during training and evaluate them on test; (B) IGNN component analysis: w/o IGNV uses zero step run message passing, while with JGNN uses two steps; (C)-(F) Sampling, attending-to, attending-froe from and searching horizon analysis.
Le Time Carton denaingg lenive
22 Cart Conconena Boga Hbroaes
T0 Trus Seuching Lebbw
(C CLE Back
23
A0V1
Kart 24
Paoabad rosoaeea
Figure 8: Analysis of time cost on FB15K-237, (A)-DD) measure the one-epoch training time dif- ferent horizon settings corresponding to Figure (C) (E) measures on different batch sizes using horizon setting step=20, and AGNNN--
=aa=sseennoodsspppsstto00000 Max-atteeded-mooessseee
10 MORE VISUALIZATION RESUTLS
10.1 CASE STUDY ON THE ATHLETEPLAVSFORTE..E TASK
In the case shown in Figure the query is cereeppppprsomoohmeerrc...c turner. concept.ahieeeplasssfott
and answer sonceptsporrsttemmggee can see our model learns that (concept persomorthamerica michael turner, comeept.allletehomeestaiii concept stadiummoeventtvenee georgia dome) and (concept studiumorventveeuee georgia dome, con- stptteaanhommstuauumm.. inv, hwtpspootttammuulooooe are two important facts to support the an- swer
From Figure g we
Besides, other facts, such as camneept_ahhett..e Jarrington, harringgoon ammceprrahleteiommsssaiii concept wtw.iptttttiiieeeeeeeeeee georgia concept ppootsteennfaloomeeee provide a vivid example
and (concept.athlet
joey harringtnn, comcept.ahleetpllassfteee that person athlete with aumeeppstadimmoreeeetteeet wewpetteeeeeeeeriiadddaoooo georgia his her home stadium might play for the team concept sportsteam falcons. We have such examples more than one, like concept athlete rody white's and concept athlete quarterback matt ryan's. The entity
17

---

Published as a conference paper at ICLR 2020
cept_sportsleaque cannot help differentiate the true answer from other NFL teams, but it can at least exclude those non-NFL teams. In a word, our subgraph-structured representation can well capture the relational and compositional reasoning pattem.
concept CONT Chanse bal
Corcpp stricte Joddy, wiiii
Curcept www.://mweeeeeetttte......
encept 1th Jey hamiinsin
cooppp AOSNNI PATAEe, dky, mh
Corcept Perteet RAOGH
Whame micted sarnrr
CONSEST
concept torteeague
concept Spaterrem mn TAReeby Weme
crrestt jonr doar tew, yer.eeiite
concept AOD www.tooee wwt.://ppp.tttttattttoooooo
Figure 9: AthletePlaysForTeem.. The head is concept personmorthamerica michael turner, the query relation is poneppraaheeeelassfoteem. and the tail is wwanceptpporsttemm__ao fallloss The left is a full sub- graph derived with attonddnggnoommpppee frapeeerttrrreeeeeee200000 and the right is a further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over a 7 T-step reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
For the AthletePlaysFor Team task
Query: [cancept. htntr/omoothhmmrrramiiihheeee
caneept:ahhleeeellyssseeee concepi.sportttem..floom
Selected edges:
sencep..persemmorhhameeeoo www.aaaa.e.....mee..u.......
concept: agentbelongsttorrgmiiatiiii
concept.sportslessue.uu
concept persennortha merica. mwchmml.......... turner. sancept:shletehhmeelees
concept stadiumoreventveeee georgia. dome
sooepptsporttleague.ooo concept comeept:agenttempeeeeeeet agonteemppteswiihaaennn
hanncept.parrtseaaus...
concept sportsleague nfl.
snooept.porrtsleaque nfl. eeneep..sgnlcompeeeeeee sggnttcomptteswihaagen inv concept sportslesgue
concepi.sportster
chargers
comcept.sporttttaguee.lt
anneept:laaguestadiimm
concept sportsleague nfl., sontept:tesimplaassileegg inv concept sportsteam falcons
coneppt.sportttaaguee..ll
wancept.perreeeeeep personnarthamerica.
concept: /eaguestadiums.inv, goncept.spertsleague.o
concept stadiumstevertivenee georgia dome, concept:teamhomeeet www.hmmmmmmmmmiiimmmmmmmm inv. concept sportsteam falsons
concept immeop..ttadiumoreventteeee www.gepo.oooo....... dome. concopt:athletenn wtgt:aathhhthomstaaiimee
concegt-athlete-jpey -payyhhrringtonn
concep.sttadiumoeeeeetveee pew.:ua..eoo.g...m....
hmmeap..athleterroddyyykk
concept stadiumoreventvenee georgia dome. concept:uthletennmeetaaduuu inv. concept ceach deangelo
soncept htaplllumrrvvetteeueeeoooooooooo
concept: bonccettaahhetehhmmssaaiiii
concept. sportsleggue nil,, concept: sutrepppsubbarrtooaaganiiaii inv concept. sportsteam
cakland raiderss
concept sportstsam chargers. canoppt:ccmplllysnnnaagge, cancept sportslcague nll sanceptsporttteemm.dd seoonttsam.sd.chargrrr. cancept sportsleam cancept.sportsieem sd chargers. comeptt:ocmmmlaysssiinnttttttt
saneept:taamllyaggainttttaaa sanrept.spartsteam.
inv cancept sportsteam falcons
concept sportsteam chargers. comceppt:tammminnssagnninnttttte concept sportsteam oakland raiders srrceplsportstsammsl.ooom chharggrss.s cencett:ccmpplyysaaaiittttss concept sportsteam falcons. concepi:teammpaayiillaaeeee, concept. sporisleague concept sportstoam falcons, cancept.speree sspertsteam_faat falconss toneep::teammlyyyygggiiitttttttt int.. concept. spw.tstoootttm.... 5d sd.chargers
eancopt.sportstean httttsteaamm.kkandrrideeee
hamcegggttaammalyyggaaanttttttt cancept sportsteam sd chargers
concept sportstaam falcons. concept tamepptttam/ommmttaauui concept stadiumrreventveen concept sportsteam falcons, sonceer:ttammaasssaaintttttnt concept sportsteam.co wak.and. raiders concept concept.sporistert www.sssteammaaaleee. falcons, concept sportsteam falcons, concept: aagaaatttattttiodspprsttttaaa inv. concept athlete Jocy harrington hta.pp..tthett.oo...attrtt concept.atio athlete.joey_ht joy__hhrringtonn coneeptathiilohhmmsstauu
georgia
temeeg::tammplaysagginnnttt jiy, concept consept_sporistn sportsteam. wawksttammookkaddd.oo. raaders
concept athlete josy harrington. conoppt:aiMeeraledspppttttes concept sportsteam falcons
cencept. sww.ttsesstttttmmm.ooo falsons
ceaapttathhttt_rree roity. concept athilstehomestadium,,
ansept_.thhlate roddy white. aoncept:athletepleee athleteplaystorteem. seoepp..portttemm....
concеpt coach deangelo hall, concept:athletton athheetehomestaaluu concept stadiumoravatveenee georgia dome
18

---

Published as a conference paper at ICLR 2020
concepL.ceach..eeaaeoooo.oe
coneepl.spottllesuee.ll...
concepl.sportsiaam.llaanns
canoep..sportsieam.lllsnne
concep::eemmppayyaaaiiittteeenne
concept.sportsien oakland raiders.
coneegt.leampppyyysggeeimettttt
immopiissorttteam..aiiiee.....
concept.sportsteem oakland
raiders
cmnepi.sportttemm.ooklaasss
concept. sportstaao new york giants.
coneep..eeemplayyssaiiintneeee concept sportsteam.
cencept www.:neewwerk.giiaee
sonegg::eamppyyyaagnntttttet.e aancepl.pprrtttem.falcc..
giants concep::sammpkyssgiinttttta
sportsteam oakland raiders
10.2
MORE RESULTS
concepE JD UNCEE pencee
1996
concest Jihee
Concer Spontcann EeRte
DOPORDT gpodttte QUP 711
concept
cRncest
concept pay
the query relation is smneepttahleeepllyiineeeu and the tail concept sportsleague mlb. The left is a full sub- graph derived with attending from-pee wwwn-per.stee step=200, and the right is further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over a T T-step reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer the final step.
Figure 10: AthletePlaysInLeague The head is conceptpersomorttaamrccc....
For the AthleteelaysInLeaguee task
Query: (comepp.persoomrthaanricc....c
oag.aoai..........iiiiiiaoanoono comcept.spprttseaguue.mbb
conoeptaathhetpllyyyilleguuu
Selected key edges:
wwt.soonnortaamericaaaaat...... caneepp.persoonootaammiiia,,, wttprricccaaattttttttteeeee ttreanor,
campprr..etleellyyoloooooorrssrr concept..porsseemppsiiin
concept sportsteampoosttinn center sineppr.allleeellouuuspppsssesst inv concept personus orlando hudson
concept.athlete. haaillle_bee.hendricee
oonopp.ssorrssaampsiiiinoceeeeee
htt.://aaeaaaatooooo.oooooooaaaa conoopi.coahhjj-hharr
cmnopt.sporssaanpoaittte.eeeerr
concept.sport.assebo concept: ont.eeaeeeeeeeee.oooooooo..o.ooe
concept.spori.basebblll
concept.sport.bassbball. concept: hamppppdchaaaaaussooorro....oood
concept basebaal camcappr.ahaeepppppppppppm....op
huittertehunterrppe
concepp.personus.ooradddoo. huw.dooddodddon..oooooo concept.ahleetpaayyilllegge oacgapagggeeetaeroooooooooooooee
concept..onsenus.colaadddd..... ooncepe.enleeeppayssppttttt oonpappppao.t..oooeeeeooooooaoaa
concept concept-athlete www.aathheeebeeeeeee bew.hendrickson
concept:ccacchesnneeeeese concept.sportsleegue.
concept
hendrickson,
concept concept-ahhieteellasspporr concept sport baseball
19

---

Published as a conference paper at ICLR 2020
concept.coach..j--hattt concept: coneept:coaachesiillaguuu. concept.sporttleeggee.nm concept.coach.j::
coach jo-ch.jj1-.haddy concept: concepi:ahheeeeplayysieeauuu concept sportsieague mlb
concepl. cwa.cpccccc....... co.ch.....hardy. coneppliathheetpplayyspoott concept. sport. sprrt..aaao.lla baseball
concept.athler aatheeeehuuttr.peeee
concept: concepp..thhleogilayyssllaaa
Sancept.sportsieague
concept athlete hunter pence concept. concept sport baseball
soncept.sportsleagueembb concepl.sportseezque..mtt
concept.athlete http:eeeeeeeeeenddiiieeeeeee
concepp:.coachessiilaaauu.... concepl.coach.jjl.aaree
concept Sport footbal
vitetttvitttte wwt.ttteellmmtttteeeee manring
circeptan totee
conept ummmos
concent demmea--...
Ly. Fod Wileeed
concept mndemanentiouu
concest stad coerereee slad
On cnicerrstalllmmee (rteerut, nicffe_coboonn
CP JUNK JOO
concept spo saqUE
Figure 11: AthleteHomeStadium. The head is concept athlete eli manning, the query relation is conepprathltehooeestaiiii and the tail concept stadiumoreventvenuee giants stadium. The left is full fromm subgraph derived with max_attending, from-perr poom_per_sterr per_step=20, and the right further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over T'sttep reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer the final step.
For the AthleteHomeeSaddium task
Query: (concept. athletee wwteeeteeelimmaaeee eli.manning
Selected key edges:
boncept.athleteeell.maaa concept_athlele. aamboppaathleeeeellmaannnng concept.athleto.eil htt.hitttteeiimmannnnn.... comcepp:.atieeeeedsppottttee sonepp..portttaam.eev.o...... concept sportsleague nfl
sancapl:shhleeeplayyfooreaaa ponepp.pootteenn.ooooooor....pp
concept athlete eli manning. comcepp::ahheeeepppyyiilaaps
concep..athette..limammmi. conceee::ihheeoloorrooo...ii
concopt.mall..rchieemmmm..
concepr.teampplyysillaguue otgpa//ewe..ioooooooooooooooooon
concept.sportslaaguueenn
conceppt.temmhoomesssddiii concept.staduuooreeeeveen
concept spncepttspprtstemmmneeeww glants,
concept athlete manning
concepi. athlete eli manning
concep..sprrseesguaaail..c.
wtt.uuueeiianttttaaiuuumm stadium
concept athlete aliimanning
conopp..aao..cchie.mmmiigggggo. cwwp://miiin...oo.oooooaaaaoorro
concep..athleteeelimmaiiii
concept sportallgpor nfl.
concept:leagueetadiumss concept stadiumoreventvenue
brown stadium
atan conaapt.teamhommsttaduuu
concept.sportsteam.
concept lanrept:llaguestadduuss.um
concept.sportsieeguue.mt
conepp..tadluuurreevvveee.. -ianttsssttaiumm
proxyforro
concept.iit..esst.uuherre
concept city east ruthertord concept: proxytor, concept stadiumoreventvemue glants stadium
conepp.staddumoreventeeeuu www.buewwwpa..boo...oo www.wo..taaduum.......m......m.t concept: heapeeeptstauesssiiuuum.smm concept.sporisscague..t
For the AthletePlaysSport task
20

---

Published as a conference paper at ICLR 2020
CONPERT COL CAY gralant
concest strect, wedls
concegt sport
concest RORE
corcept
portstaa dear.ngt strsis
CincssStoo... Nockey
concept sport seebal enebal
Figure 12: AthletePlaysSport. The head conceppauhheeee.erroo..w the query relation is con- cept:athleteplayspor,, and the tail is concept sport baseball. The left is a full subgraph derived with max.attena attending from from-per.stepe steesp00 and the right a further pruned subgraph from the left based on tention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over a T-step reasoning process, where grey means less attention, a
yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
Query: (concopt.athlette.eeee wwtellevveoonnneeeee wells, concept: athhepppathlllepplysssprt concept.spori.baseeal
Selected key edges:
concept.athlete.vere
concept: athleteplaysinnleague slee
concept.sportsleague..no
concepl_athlete..veee hetpillteeveeoon.welll.e wernon_wells. concepl: coachwoocccch.o
hancopp.wwarddrohhyyurrmmma
wwwpo/nwwwwoodddddeeeeeeeeeeee series
concept. atwlett. vernon wells
concept blue jays
concept.athlele
wells, concoptt.pesssoooooooosoogggggat concept.sportsieam. blue jays
concopl.tthlete..vroo...ww
concopt:athleeopllysfiirii concepp..prtssammbblujjjyyy
condep..sthlett.eerron..elll conceettaahttteeeddoooooststtnne coneer...orrstemm..llelaaaaa
concept.sportslaagueemmbb.
concepptteemmllasiiieeguuuue.u. otrp:p/ppueuiinoooooooooocppeoe concept.sportsteemm.ooo
concee::teempxyysnleeguueee concopl.sporttiiagguemmbb
concepl.sportsiaggeeellb,
ottp://seeoeeeoaooocooooooooaeaa concptssportsseenyyaaeeee..
concept
wwwrdrrppyytooouummeeeee. world series, concept: inv. concept sportsteam dodgers
concep::temmoonttoppy..... concepl.sportseeemmyyeeee
conceppi.aport.baseeblllll
concepl.sportttammbbbeeevvvv
concept..porttttemm.bleee wtwp:ttaammbueeaaas....o
concepp..eamlaaysggannttttta. concept concopt.sportsteemm. wwt.:/spooottmaakkkeese
concept
concepl.sporrsseemm.bbeeee blue
soncoppss otg.://mem...oaooooooooooooaaaaa concepp:ieemmplayyspoo.. concept sport baseball
concept.sporrteaa..dddgge... e
comeept.sporrtteam.ddoogrr. o.tppp:tammaaaaaaittentni.ni...a http://ppa..ainnii....oooooooopo
comcept.sporrteem..ddggg..
concept:eeamwontrophyy.
comcepp.spprttteemm.dddog.
concopeteeamplaysspottt http:/pppppppp.oocppepppprrrraar
soncept.sportsicammyaaeeer
concept sponttoatnortttt
yanketessayyyyeoooooooooo yankeos
concpp::emmpaaysgaaattttteennnn inv cowcept
dodgers
comcopl.aportttoammyaaeeee
concept.sporttssammyaaaaess
congppt.sporttttam.yyaneee.
concept.teamplayssaaaiittttttttr
hit.seaammmittstthhhhhhh pittsburgh pirates
concppl.spor.bbsseballllcooo
concept sport hat.aa/............a....o..aoaaa
inv
concept.spor..aaseblll,, htg.://aaaeblll.ooo.cccaaaaaaaoo condapttteamplayssagiittttt concept.sporttteemmm yankees
concept.sportee gtgepp..sportttaamppptuuugg anttsburgh.pirrtte
concept sportsteam piltsburgh pirates. concept: sonceptt:eemppaayaggiiintteee concept sportsteam yankees
21

---

Published as a conference paper at ICLR 2020
pportsteam.pittseee -irrttes.... concept teamenttophy. conepp..wwadrrooyyyoommmem...... concept sportsteam pittsburgh pirates,
concept: concept: teamplayspoortt concept sport baseball
Forthll
Sehoop EioooUSsiie Lieretean CINy Mombusstuuueoe
concept,
CONDENt Ster
Fentect
rudta Mie Jackets
Conces m menrrrll pwarrelllarradeeens çaradiens
ConGOSE SEYE bas
Concest Spor
Figure 13: TeamPlaysSpore The head is srrcepp.ppotsteemmred..wggg the query relation is cept:eaanplaysport and the tail is concept sport hockey. The left is a full subgraph derived with max attending from per step=20, and the right is further pruned subgraph from the left based attention. The big yellow node represents the head, and the big red node represents the tail. Color on the indicates attention scores over Ttspep reasoning process, where grey means less atten- tion, yellow means more attention gained during early steps, and red means gaining more attention when getting closer the final step.
For the TeamPlaysSport task
Query: [concapt.sportsteam.rrdll ott.://ww...ooooo.oooooaaaaoooo.
conplpttteamplayssporr concept.sport.hookee)
Selected key edges:
concept spprlssttortttrredd.. www..eeddddd......eee concept:
hamplapeeeaallysaaagiisssttaam hanccpp.sportsteamm.o montrrallllnallamammmmmmoo wtw.:/mttaa..caaaieenn.. canadiens
srnegt..porttteam.rdd..wmmm
horopp....mpaayssgghhttttem....t concapt.tssooooocccccccoooc sportstea.... blue jackets
concept.sportstemm. wtw.atttmmmmotttaa.caaaaea .canadiinss
concept.sportsteam... red wings concep...emmpiyysgaintttttm.mm
ottpp//.t....coo...pppsoottteeee bakees
concop..sorttseam.rrevv..... hmmpppp.wwonttooommmccccocccaaed
conepp.spportteam.red.iigg
condep::ogaaizalionirreepppoo concept.athlete sancepptathlete.lldstroo .iddstrom
concept sportstepepttstteermeeeeddiiiiie wings,
conden::ahieetellayylinteaammm concept athlete lidstrom
conegp..spnrtteammrrrev.i....
consepssporrteammeed.wigg
conceep..portsllamm.lett
concept
htg.://awc..........oo.oooaoaaaa inv conce sportsteam leafs
coneepttttheee_lllssomo...eeeee
coneep..athleeee.lddttrom..
concept atdlelee
http://ccccccciiiicccccpppptttte concep concept sportsteam red wings
coneptt.sortttam..dddiiigg.....
caneept.soottseegueemm....
concept sportsleague.nhi concop::teamplaysiillqquuu conpoposssssoopspsssssssaa....s
concepl. pmncepl.sporlsiiaauue.ntt htt.::oooo......ooooooooooooaaaa
concept leafs
concept. puncept.sporisteam.ees concopp::eemmplayssnlaaagg concepl..portsieaquue
concept.sportsieam.leess concept::eamplaysspore o. honpppppoog...c......ooooohoooo
22

---

Published as a conference paper at ICLR 2020
budarhemer
concept
concept ARD JATTARE
corcept minsel nanaelesseer ester
Sorppan dSsay
OonCRTT City ab
concept biotechcom pary the daney
purtinnt glendale pasadeta
concept 200 Roat Jper
Figure 14: Drganizatoonnedduuutteerddddd
The head concept.companydddit the query relation is oonceptooggmmiaaionnccdqqquueeee iittreeeccc,,....eiiiiiitt and the tail is concept city burbank. The left is full subgraph derived with max attending from per and the right a further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over T-step reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
For the OrganizationFeaaQuuatteedldiiii task
Query: [concept.companyydiingg concept: httpa/ooooo....ttaaaaaaaaaaaannr ott.://ueue.roooino......o..oooa concept.city.burbank.
Selected key edges:
concepi_compate compppyycccaaccccccoommm company_disney, _disney.
concept: headquarteredin, concept.city
concept.comm company disney. concept.compee company disney.
prbeep::subbarrooorgnniiatoooo
concept website networkk
soncept:workssfr.imig iny concept..co_robbee rateooooobrrriggee
concept.company disney..
concept:proxyfor.ttt
concept.coppny.ddinne..
senceet.comppny_disneee
concept.company wwwplloompayyyinneee.. .dineey.
kattreyekkatebbbrg
concept company disney o canceent.oggellttttteeemmttttrrr
concen
concept ceo jettrey katzenberg
concept.city.burbankk concept: i ott.://hiii.n...c.oooooooooooooo
ctt.epp..clly.bbbann
comeapt.webaiteeneetwrk.. concept: sonoep::uubarrtoooggaaattttooooo
concept.company.ddinny
concept..ceo.robert.gg.. concept:worksfor, comee _isnamdaannndddeyyeeeaee
concepl.ceoo.rbbrriigg.. proxylor concept.company..it
concept.ceo.robbee
compepy ciseeyyydnnnineeey
concept.ceo roberreeerrorrriii.eoe concept:ceool, company disney
concept.cco..roberl..gg
concept.ceo.roberr.ige.
ott.://......ooo..ooooooooooooo. otgaraaeeaoe.....oiooooaaaaaaaaa concept.company disney
concept.coo.jelrreykkaazeeeeeee
concept..ee.jeetreeykkaaeee oon.pooogagaaaaaalioiiiieeeooooo concepl..ompany.disen
concpp..co.jjdirryyyaatteeeennnr
concept ceo jeffrey katzenberg.
dreamworks skg
concopl..co..iofrrey.kaloooo
conegpt.toomombbroocgggiiiiiiooo
concept..eo.jiirrey.aaazzmmoss
sondept.ceo.jeffray.lttzeee
concept concept.biotechhcoppan o oat.anayyyyoooooooooorrroooorroe concept city burbank
conpppppl burbankk
concept orreeptteecrrdaaabeeoreaaawwowt
concept recordlabel dreamworks skg. conepp.toonemmbrrddoaaaiiiittitn concept сeо jeffrey katzenberg
aoneept.ecorriiabel.reeaaaa.
concepr.oganaaatneennndddoorrorr concep
conepp..ecoddaabiccrravvooossss prpportincity.iv... concapt.raansporatioo.bbbbbbbbb. burbank...kabbbbababaabaoe pl pasaddena
concept.city. www.tcttyuuuut burbank, concept:
concept transportation burbank glendale pasadena concept.airroortincctyy concept city burbank
23

---

Published as a conference paper at ICLR 2020
CUnGept, persenus beline!
concest REan,
contege spersiiam sheee univentty
concest, Sww. micossa
emna Salmer
concept conceettpeeeert www.peeeeeiittt...ooo to sle
Cancest Jel
conoept swembtear Torsard shtriyysch
Figure 15: WorksFor. The head concep_sccentist.bameer the query relation is con- ceptoworksfor, and the tail is concept university microsoft. The left is a full subgraph derived with max max.attendie attending from wernppersstepp. step==20 and the right a further pruned subgraph from the left based on tention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over a a Ttstep reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
For the WorksFor task
Query: (concept.acieetist.balmerr
concept: concept.universttyymcrrooott!!!
Selected key edges:
wttpppttssiiiii.bbii... balmer. comepp..tomeemarrddggaaiaiittoi. concept.company. micarooff
concept scientist balmer. ammeppr.oggniaattoommmmmaappppsp inv concept university microsoft
ponccppt.compnyy miccrosoft, condett:.oonemmeeiiiigggnataiio. concept.personus wttpnnussstteeeeeeeeeeeeeeeeeeee wtw.tsteeeeeeeeeeeeeeeeeeeeeeeee ballmer wtt.:po.coomaammmcccoeeeeee
concept-universe sntiiversitymmcrooooii
atw. www.rroonsssteeeealllleee.e ballmer
concept university microsoft, ooneppp..prromeeeeddooggnnntttoo concept personus steve ballmer
prnceppt.niversiii saciiiyyymcoooool... corceell.pessooleeedoornnniiiiid concept......ooooo concepl.person. bill
concept. universiiy micitoooi..
conpppprccrggaaaatioooommmmteeee concept woncept.
balmer
concept university microsoft. conpertporoollaaeeogpppiiiiiii.o concept person. robbie bach
concept.personus.steve
soncept.personus.stee ballmer. www.prr...gooooloooooooooiiiiin.
http:///w..a..iiioooooooooooooon stt....iiiiiissstyymmrrooottt miccooooft
stw.ptsspperonsssteeeeee ballmer.........
concept personus steve ballmer, con.pptwwwrsssrr..occneeeeeeeeee
concept.persomus.stu bal.ber.......... cangge/.pooyyy..oooooopeeeeeeeee
concept.persomus.stee ballmer. oa
concept.personus.stovv
concept.personuueii
concept.person.bill. concept:worksfor.. http://wwwe..............iieeeeo
concept person robble bach, coneppe.prroneeedgggnnaaaiin,
concept. microsoft
concept. peroppl.person_rbbbeee bach, concept:workstorr cowpr/srrrr..ooooooooiieeeeeiiie
concopt.eeaallttre.miiroooot. concept:: comcept.persomussslevebb.. mellmer
concept.rarailltore.miicooo. concept: sunpatt:ubb concept.personus.stev concept.ettallstoreemlcooooos
concept.personus.see steeeeoouussssseeeeeeeeeeeeeeeee ballmer
For the PersonBornInLocatin task
Query:
(concept person mark001,
concept: prrrepttpeersonbommnnooottto....
county-york..... cork.city)
Selected key edges:
concept person mark001, pott_perso__arreeee concapt.person_mark00 concept:pent concer::peronnrauuuteerromniieee wtg.aaagoo.....tiirtttttttttee.e concept.person.c concept person mark001.
: persoongraddatteiiiomniiiveessi concept university college
concept wew.sooggggaaduutteeechhooooddo pateoooooooeeerrrrrraraaaauaaaaa
boncept.uiiversityycolleg.
concept: heaagpp:ppesongrauuuudescchhooo
concept pnncept:perssonbommnnity concept city hampshire
24

---

Published as a conference paper at ICLR 2020
concep 2O12
ConOe Wien
Maratol
SERAA Unieersyy
morpp moutty orrtctyy
circet Stat univestt CIRCUp person,
concest spersaaam uneees #dwm000
Figure 16: PersonBornInLocationn The head is concept.person.marke the query relation is con- ceptppersonorrinnooction, and the tail is concept county york city. The left is a full subgraph derived with max attending frwm-per.ssee ste-s20-=00, and the right is further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over a Ttep reasoning process, where grey means less attention, a yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
pancept_person ptt.ppeoooorro01.....11 concept hasspouse,
concept.person.marttt concept:hasspousee
concept.person.dien diiane001
concept-univeseee college. c aeesongssduateefronnniirssssssss
concept pwr.tp.mark00
concept university college. concept : persongraduuateedccooollll inv concept person mark001
sunnept.university.ccom
concept: hanagggceeeeeooaaaauaaoiiooonnnn
pencept.person.bill
concept university college. concept- comepp..esssnreeaaaeeehcoooiiieo concept person bill
soncepttuniveersilyyssseee..mum
concept.person
concept.person.bll
concept unncepp.univeersityyssta. universsty.. honneppt.erssngruuuueeecchhooooo concept- bill
concepl.city.hampslii
concept.person.dian000011 concept: aancgg::pprooonnaaauaetrmmmmnmee
concept.universiig .tt.tittyyystttuuuee .sstate..uiiersiity consept: concept.eersoonmaak0001
concept personn dianee00
univeet
concept university state university
concept.person..daaee000:
concepl.persoo_diane000
pancept:hasspouse.u
concepl.person..daae00001 concept: coneet::errommormiiioocaooo cow.://acccccccccccoccooom
concept university state university, coonepptserrsograaaaaeeerrrmmmm
inv concept person diane001
concopl.porson.diane00
concept.person.bill.. concept.personbbonniiiyy com.ppiiiiiyy.coooo......y.yyyo.
concept.person.blt concept.perentbmniicctiiio.. concept.city.yort
concept.person_bbll oec.eeeereeerroogooeeeeaoooaaner
concept.person.bill
colllee
concept concept.person.ee bill. aaneepr.ssrrooodadsaeerrrmmaleee concept.unnecccoccooo. university state university
Soncept.person..e concppppprroo///datutddccccooooo ctmp://dccccccoooooooooooccc.e..
wwwaeslaaiiiieeeeee university
concept.city.york. concep..personbbmiiiiilyyy.yyy concept.person.bill
concept.city.york, conepet:pesombomiinity.iii concept.person.daaee00
concept.universitycollees wow.eptt
concept.person_dianee)
concepl.person.diane0000 concept:
personbornincity. concept-personbonniinciii
concept.city.york
For the PersonLealsOrgamizattoon task
Query: jconnept..ourmalist.. bill plante
concept: perssonleaddoorganizziio.. concept.company.com .bn...bb)nn.
Selected key edges:
concept.journalis..bill...
concept:worken joncept.jurrnalis... bill plante. concept:
concer..tdavsiomeeoork.....
concept..elevise Soncept.tlleviiionnettworkkkk
concept televisionnetwork cbs concept:workenn concept journalist walter cronkite
25

---

Published as a conference paper at ICLR 2020
ceneett PeI PER eteR
coNSEPt
OR
concept parts sdaard, ard MurOOw
concept www.reungeee.......... www.eellllleekkkk
corcept Decola EEGASE db
sttele antharyy
concest huma humalst www.trr tww
concept www.EEE
the query relation and the tail is concept company can. cnn..pbs. The left is a full subgraph derived with max aftending frommddgggfoommmaa.. from-foooooooo pwt.-perrrrssreee step=20. and the right further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over T-step reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
Figure 17:
The head is concept.joumllis.bill
is
conopp..eleevsionnettwrrkkkkkk
concept: coneep:.aenttollaarrreeevwttnnn contppt.jurrallit..wttee...oooo condep...elevsslomeetwook.....
sancept:workstor.iigg concept.personus scsstnussccott.pelley
tenvsppiiile cbs
concept:workstt inv concept actor daniel schorr
ooncpp..teevisiioneelwrrk.....
concept:workslor.inv..
condop...llevsssommeewwrr.k.....
concppt..geeooolllaaaaavvvttttt concept person edward murrow
songpp..eeevisioneeewkk...c..
saneep..eevvsionmeewvvrccc.....
sunopp.perrouusssootpppllleeee.p
p
cbs
concept actor scne
comeaipeooonococcccccocccoaaaaa company pbs
william paley
minbepp.cily.new.yorrk.
concept city new http:////.o///oooooooooooooooooo
inv concept Seonceetteeevviionneenn televisionnetworkkeo
concept.cite haw.nw..york : coocept:: concept: wwwpeprr...nttttbbboeeeeeennnnn.
poncept.persomeurope..oo http:ppwwwliiimalleeee.
concept.personeut wttpeeeuurroewwiiammpp....e
concept: wttp://wwweooooooiiooooooeeeeeee
poncept.personeurope..oo www.lammpplleeeeea httpsooeurrope.illllaaaapp
concepl_personeuropp
concept paoopppll htgp://wwc.....amoiooooooooooonn
For the Organization task
26

---

Published as a conference paper at ICLR 2020
gouen www.gratttooooooo..oo...ooo
concept DETOONA MAL patt
pertot
CANGAPL munk TXLT SIICI1997
Stroet yoar N1992
concept cogntry serbes
5a phen year
concipt ciy namr
del FinL
SHulTT Leld states (onrest ChaMmieAn Caro7, modyamn
sireet cir-iini
JT. STM topprra afterroon
Figure 18: OrganizationHiirePersoo. The head is tion is conceptorgguiciiinniiveeees.s full subgraph derived with max attending from-per per step=200, and the right a further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node rep- resents the tail. Color on rest indicates attention scores over Tstepp reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
wtw.:utteeorroiiiicceeeeeeoooooe the query rela- and the tail is concept personmexico ryan whinne. The left is
Query: (comcopl.slateoorpoovine afternooon concept: org.anniaaiiinnirreeprssss. concppt.erroommxxicc..vvm wywntwhiteeeyyyy
Selected key edges:
concept: aldate.
concept: aldate. concept.date_n221 dal._n200e00333
wwwateorppooinnneeetteeeeee concept
aoncept: concept datellteral conleet..atellterral 62000
concept.
hat.eppddddellieerlln.200 sonntept:aldat_.ing concept.country. www..d..eeee.. states
concopt..attlliteral.20077
sanbcppt:ddatteiin concept.city.home
oonceet..attelieraln20007.. atdate..i.. concept.city.servica.
concept.daatllteeral.n2o00. concept:
concept.country.lt let.iryyyeetttttttteeeee
concept.date_n2003: conceet: concepl.cunnty.unllediitttte.
concept.dateen22003 concept: att.
concept.city.hon
concept date n2003, www.ooottaaaaaaeee.. inv, concept city service
comcopl.catee.2203.,..
condept..atteiiieraannn000......
concep..connty..uitee..aatt
concepp..ateeliieraann2226.6.... coneeptttttteeeeee.nn concept.city.homee
concept..dateliteraal...o0 wow.coocccccctttte.ccccc
concept.city.service
concepp..cuntry.eef..prriio. org.://c..e.aaaooooooooooooooooo
concept.countrr.uuk states concept:atdate.... concept.year.n11e.
states concept: con.
concept.country.unnitee. otg.aaaasse....ooooooooooaaonooa
concept.city.home. concept: concspt.year.n1992
concept.city.home. concept:atdate concep..eear..11191997
concept.cily.servicc
concept city service concept:atdate.... o owwpeprrroogaiiiiiiiiiioccocoooo
foncept.cily.service.
concept.counttylleff.ppriiii http:///w....o.ooooo.ooooooooooa
concept.ccuntty.llff.arrrie
concept.year.n19922 concept: atdate concept
concepl.year.n11992 soncept:atdale.im concept.county.unnlletsttaa
concept.year.n1992
concept:aldale..it
concept.city.home
year.eealllll n1992.
concept:atdale inv. concept tradeunion
concept.year_n199)
concept:atdate_im
sonepp..overmenntrggnaaaaaooo
concepi.year.n19997 andaaee: concept.countyyuunited....ud
sancett.yearnni99
concept:atdate atdate.ivv. concept.city.homs
concept personmexica ryan whitney, concept:
concept
governmentorganizatiin house
27

---

The left is Published as a conference paper at ICLR 2020
concept.personmexio. hot.iioorraaaaaeteeyy.... concept:workstor. conceei.rrdennio.ccoggee concept concept personmexico ryan whitney. conkept:worksfer, concept parties
concept sancepl_govermeetorrgeooo governmentorgaaiizationn house, buneggg:ppeggrbbbooossoogggggggr
penncepp_peroneeee personus.parly .parly
concep..overmmentogggiiaaaaa house. songppt.workksorrnnyccooosppp.pp
concept governmentorgaaiizatioo house conppptt.onannitiiiiiiieeprr.... concept personmexico ryan whitney
concept wttpt//rrddeeiooooorrreeeee
wonkept:workksorr.nn,, htwp://www.....oooooooooeeeeeaaa
wegptttradeunion.co
concept country left parties, coneepptorggniaatiioiiiieeppprr concept personus party
unversty
Intionnniinnn niched022
concept pansn
Marcoot
exfcept pollican
world
concept wisbrrrtorrreoooooo shoe author
Rubdy
concept sucard Iriends
concept, www..//suuuuteee Skows
Co ConsaPLerr www.epeeerooooooooc.oooo
Figure 19: AgentBelong
The head is peceepttpesoommmrrkeee the query relation and the tail is concept_ repppliicallloocctioo...
is comepptaaeembbloossttereeettiiie full subgraph derived with max attending from per step=20, and the right a further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over T-step reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
For the AgentBelongs
task
Query: (concept person mark001, concept aabeepggaggeeteeennnsssooonnnna concept geopolitiicalloattio world)
Selected key edges:
peccepttpprsso_mmrkoe concept: prrsoonbbbanngttoogggiiiiiiiioin concept.sportsteam.
pacp___proo__mrrrkne poncepl.person_mrkko0 concept: oww.ott...ooooillaaaaeeeelaaaaae www.eec.maeee...oooooooo htt.://iegeeiiinnoooooooooeaaaaa
prncept.perso__aate mark001 hmmpopppprrrotttogggttoooooienio
concept sportsteam state. university,
concept politician jobs
sencept.politician
concept.spprrtttemm.stt
concept.person_mark00
comcapt.person.greg001
concepi.malee.wordd hatpppaee.....oaooaaoooaoaooooor
concept.male.world
concept male world. pew.ett....cccllaaaccc.aaaaaoeea concept.male.wortt oet.epaee....acllooooooooooooaor
concept.male.worrd http:///ww........ooooooaaooaaon
concept male world. org.aaaaeaa....i.iii.oo..oo..aaa
mancept.mae..wordd.ccomm
concept oot.gpppiiiiiiiio.ooooooooooooor
concept persson mark00
concept_person_grggl
concept.polittcian. conepeprrrrsooeeeoooooooooaaaaan coneep canncep.sportsteam.sso stt.prrrsteem.stteeuuuveeesst
concept politician jobs
coneeppg.gggttoollaaaeeeeelllaa. concept male world
28

---

Published as a conference paper at ICLR 2020
concept.politician.joe
concept: aeg.tooollbbbraaasstttaaannnnnn. concepi.male.
concept poletiicill jobs. concept:workster concel oooooooooooooioooooooioooiooalla world
concept. wer.opt.pprson... greego01.
orregp::ppprssooooooooooooogiiip concept.sportsteg
wtt.mssstteeuuueeeeee university
concept.person.grege.
cmmepp::sgencccllooaasvvviaaaatt concepiii concept.male.wone
concept person pergoog.reggoo...
concept male world
concept.persoo..greg000
concepl.persoo..rreg001
concpi..eoolliicallcccalllo _world
concept.person.gregoo))
connept.ppoiiicalaarryyoomm colllee
concept p
orw.r//ww...............o.oooear concept recordlabel friends
stt.sammsstate.uvversstt university
congeet.person.michaal00.......
concept.geeopolltccclll//
whitney
whitney
concopl.errsommexiccorrrr..
cnve vessor
concept Epo
CONTREC spartiram horeets
contect Jpirtrrnn monete
concept sportdian cetics
concest bascotbul
Conoapt Tuntingtan
The head is maneeppsporstteammmmveeiiie mavericks, the query relation is concept:eemmplyyinnee and the tail is concept sportsleaguttt...uee .nba. The left is a full subgraph derived with max attending froddinggfrom.poo from.per.step=22 and the right is further pruned subgraph from the left based on attention. The big yellow node represents the head, and the big red node represents the tail. Color on the rest indicates attention scores over a Ttstep reasoning process, where grey means less attention, yellow means more attention gained during early steps, and red means gaining more attention when getting closer to the final step.
Figure 20: TeamPlaysInI
For the TeamPlaysInLeaauue task
Query: wwtp:ppsssootttttmaaaa.
tonoept:taamlllysiinlaquue
concept.sportsleagu..u
Selected key edges:
canceptt.porrsttammmmaaa
condept:teampplaysspot..
condept:neemllayaaggintttteennnr sttp:///eeeeeooooooooooooootteee
concept sportsteam mavericks. concep..e..mpaayssgglllttteeeenn wwt.://cccccpsttseeeeeeee..
boston celtics
concop::leammpaysaaiiiitttaa http::/swe.coooooooooooooosssooe concpplspprsssssmmmmspuu
concept.sported wtt.:/soottttaaeeeeeeee
sportbbasketball concept sport basketball.
concep:teammllaysppori...yy concept sireepttsportttemmcooo
prncept.poortbbaskttee htt.rrattaanbssttoo..cccccssooos oow.oo..eeicce..ooooooccaaayaeea htt.r//eeee..ccoooooooooooooaaaa
concegr.teamplayssport....
sereeptspoottteemmmmm spurs. concept..eemmplayssileaagu condept.sportsleague....
concept sportsleague nba, comeepp.ggentoommpeeeiiiggggggg concept sportsleague nba
29

---

Published as a conference paper at ICLR 2020
concept.sportslegge.mmm concept hwtpgpgaggemmmmmeesiiigggg...... concepi..portslegggee.oo
anccpt.ssporssten college. concept concept- teaplyysilelll, concept sportsleauee international
30


Reviews:
[{"review_id": "rylJm6TTFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a graph neural network model inspired by the consciousness prior of Bengio (2017) and implements it by means of two GNN models: the inattentive and the attentive GNN, respectively IGNN and AGNN.\n\nIntroduction outlines clearly what is the goal and why this is in principle an interesting avenue to investigate, however I found it could be more precise. In particular message passing techniques can be implemented very efficiently and are highly scalable. Section on Cognitive intuition of the consciousness prior doesn’t tell much beyond the re-stating of what it is, I am more interested in what it brings to the table and on what is the intuition behind its application to this domain.\n\nOne thing I would argue agains is that the input-dependent local subgraph requires access to the global graph, therefore going back to a conventional GNN. The argument is that the message passing can be constrained to reduce the computational burden. However, this can also be done by means of anchor graphs or other data structures, dynamic pooling and so fort. How do the authors compare to such choices?\n\nOverall I like the “global conditioning“ by means of sampling to have better local representations at each node, an idea that while it can be cast as consciousness prior it is also related to neural processes and architectures alike.\n\nThe implementation section could be made a bit clearer. Currently, for instance, there are references to prediction tasks while I think it would be nicer to have it fully self contained. Also, the aggregation strategy seems to be that of Kipf et al., is it a constraint of the model or other strategies could be used as well?\n\nThe experiment section is clearly explained and results are interesting, showing the potential of the proposed approach. Also the thorough analysis of the model is very well done.\nI wonder what is the performance when using no sampling at all, shouldn’t this be the reference?\n\nThe convergence analysis states that the model converges very fast, does it also translate to better results in case of small amount of training data?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "S1lVXlppKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to use sampling methods in order to apply graph neural networks to large scale knowledge graphs for semantic reasoning. To this end induced subgraphs are constructed in a data-dependent way using an attention mechanism. This improves the efficiency and leads to interpretable results. The experiments show some improvements over path- and embedding-based methods.\n\nThe paper is partially difficult to read and not well structured (see minor comments below). Overall, I think that the proposed GNN architecture is an original and interesting approach for this specific application. The experimental evaluation presented in the Section 4 shows clear improvements. This, however, is not true for the results presented in the appendix (Table 4). I am missing a discussion of the limitations of the proposed approach. Moreover, a thorough discussion of the hyper-parameter selection and, if possible, theoretical justification would be highly desirable and could strengthen the paper.\n\n\nMinor comments:\n\n- Section 2 start with the paragraph 'Notation', but does not contain any other paragraph.\n\n- The sampling strategy should not be introduced as part of the section 'problem formulation'.\n\n- using standard terms from graph theory for well-known concepts (such as 'induced subgraph') would improve the readability\n \n----------------------------\nUpdate after the rebuttal: The authors have addressed several of my concerns and improved the manuscript. I have raised my score from \"3: Weak Reject\" to \"6: Weak Accept\".", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1gGWFHRtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Update after the rebuttal.\nThanks for reflecting some of my comments in the revision. The presentation seems to be improved, and the additional ablation study seems to address my concerns. \n\n# Summary\nThis paper proposes a new neural network architecture for sequential reasoning task. The idea is to have two graph neural networks (GNNs), where one performs input-invariant global message passing, while the other performs input-dependent message passing locally. The input-dependent GNN employs a flow-style attention mechanism. The results on several knowledge completion datasets show that the proposed method outperforms the state-of-the-art methods.\n\n# Originality\n- The idea of learning an input-dependent subgraph using GNN seems new. \n- The proposed way to reduce the complexity by restricting the attention horizon sounds interesting and seems necessary for scaling up. \n\n# Quality\n- The overall architecture looks like a fairly complicated combination of neural networks (two GNNs with attentive mechanism). However, it is not entirely clear how much each component contributes to the performance. The experiment only shows the benefit of having IGNN.\n- The effect of the proposed complexity reduction technique is not studied in the experiment. \n- The empirical results are hard to parse, as they contain too much dataset-specific results that are not clearly explain the paper.  \n\n# Clarity\n- The paper is too dense with unnecessary details. For example, the introduction is too long (2.5 pages). The problem formulation contains too much details that deviate from the actual problem formulation. The details of each dataset (Table 1) and experimental setup can be moved to the appendix. \n- Many figures in each experiment contain too small texts with lots of unexplained dataset-specific legends. \n\n# Significance\n- Although this paper proposes an interesting neural architecture for knowledge completion tasks, it is not clear how much each component contributes to the performance. Also, the empirical results could be presented in a better way to deliver clear conclusions. ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a graph neural network model inspired by the consciousness prior of Bengio (2017) and implements it by means of two GNN models: the inattentive and the attentive GNN, respectively IGNN and AGNN. The reviewers think 
- The idea of learning an input-dependent subgraph using GNN seems new. 
- The proposed way to reduce the complexity by restricting the attention horizon sounds interesting. 
Decision: Accept (Poster)