WORKS FOR LARGE-SCALE KNOWLEDGE GRAPH REASONING
Year: 2020

Abstract:
We propose Dynamically Pruned Message Passing Networks (DPMPN) for largescale knowledge graph reasoning. In contrast to existing models, embeddingbased or path-based, we learn an input-dependent subgraph to explicitly model reasoning process. Subgraphs are dynamically constructed and expanded by applying graphical attention mechanism conditioned on input queries. In this way, we not only construct graph-structured explanations but also enable message passing designed in Graph Neural Networks (GNNs) to scale with graph sizes. We take the inspiration from the consciousness prior proposed by Bengio (2017) and develop a two-GNN framework to encode input-agnostic full structure representation and learn input-dependent local one coordinated by an attention module. Experiments show the reasoning capability of our model to provide clear graphical explanations as well as predict results accurately, outperforming most stateof-the-art methods in knowledge base completion tasks.

heading: 1 INTRODUCTION
text: Modern deep learning systems should bring in explicit reasoning modeling to complement their black-box models, where reasoning takes a 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 or relations can be explicitly represented (Battaglia et al., 2018). Here, we choose knowledge graph scenarios to study reasoning where semantics have been defined on 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 a tail given query 〈head, rel, ?〉. Existing models can be categorized into embedding-based and path-based model families. The embedding-based (Bordes et al., 2013; Sun et al., 2018; Lacroix et al., 2018) often achieves a high score by fitting data using various neural network techniques but lacks interpretability. The pathbased (Xiong et al., 2017; Das et al., 2018; Shen et al., 2018; Wang, 2018) attempts to construct an explanatory path to model an iterative decision-making process using reinforcement learning and recurrent networks. A question is: can we construct structured explanations other than a path to better explain reasoning in graph context. To this end, we propose to learn a dynamically induced subgraph which starts with a head node and ends with a predicted tail node as shown in Figure 1.
Graph reasoning can be powered by Graph Neural Networks. Graph reasoning needs to learn about entities, relations, and their composing rules to manipulate structured knowledge and produce structured explanations. Graph Neural Networks (GNNs) provide such structured computation and also inherit powerful data-fitting capacity from deep neural networks (Scarselli et al., 2009; Battaglia et al., 2018). Specifically, GNNs follow a neighborhood aggregation scheme to recursively aggregate information from neighbors to update node states. After T iterations, each node can carry structure information from its T -hop neighborhood (Gilmer et al., 2017; Xu et al., 2018a).
GNNs need graphical attention expression to interpret. Neighborhood attention operation is a popular way to implement attention mechanism on graphs (Velickovic et al., 2018; Hoshen, 2017) by
focusing on specific interactions with neighbors. Here, we propose a new graphical attention mechanism not only for computation but also for interpretation. We present three considerations when constructing attention-induced subgraphs: (1) given a subgraph, we first attend within it to select a few nodes and then attend over those nodes’ neighborhood for next expansion; (2) we propagate attention 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 |E| edges. Even if the graph is sparse, the complexity of O(|E|) is 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 O(BD|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 (2017) brought the notion of attentive awareness from cognitive science into deep learning in his consciousness prior proposal. He pointed out a process of disentangling high-level factors from full underlying representation to form a lowdimensional combination through attention mechanism. He proposed to use two recurrent neural networks (RNNs) to encode two types of state: unconscious state represented by a 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 on nodes. We construct input-dependent subgraphs to run message passing efficiently, and also run full message passing over the entire graph to acquire features beyond a 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 so far. More importantly, we provide explanations while they do not.

heading: 2 ADDRESSING THE SCALE-UP PROBLEM
text: Notation. We denote training data by {(xi, yi)}Ni=1. We denote a full graph by G = 〈V, E〉 with relations R and an input-dependent subgraph by G(x) = 〈VG(x), EG(x)〉 which is an induced subgraph of G. We denote boundary of a graph by ∂G where V∂G = N(VG) − VG and N(VG) means neighbors of nodes in VG. We also denote high-order boundaries such as ∂2G where V∂2G = N(N(VG)) ∪ N(VG) − VG. Trainable parameters include node embeddings {ev}v∈V ,
relation embeddings {er}r∈R, and weights used in two GNNs and an attention module. When performing full or pruned message passing, node and relation embeddings will be indexed according to the operated graph, denoted by θG or θG(x). For IGNN, we use Ht of size |V| ×D to denote node hidden states at step t; for AGNN, we use Ht(x) of size |VG(x)| × D to denote. The objective is written as ∑N i=1 l(xi, yi;θG(xi),θG), where G(xi) is dynamically constructed.
The scale-up problem in GNNs. First, we write the full message passing in IGNN as
Ht = fIGNN(Ht−1;θG), (1) where fIGNN represents all involved operations in one message passing iteration over G, including: (1) computing messages along each edge with the complexity1 of O(BD|E|), (2) aggregating messages received at each node with O(BD|E|), and (3) updating node states with O(BD|V|). For T -step propagation, the per-batch complexity is O(BDT (|E|+ |V|)). Considering that backpropagation 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 use a sampled edge set Ê from E such that |Ê | ≈ k|V|, the complexity can be further reduced to O(DT |V|). The pruned message passing in AGNN can be written as
Ht(x) = fAGNN(H t−1(x),Ht;θG(x)). (2)
Its complexity can be computed similarly as above. However, we cannot remove B. Fortunately, subgraph G(x) is not G. If we let x be a node v, G(x) grows from a single node, i.e., G0(x) = {v}, and expands itself each step, leading to a sequence of (G0(x), G1(x), . . . , GT (x)). Here, we describe the expansion behavior as consecutive expansion, which means no jumping across neighborhood allowed, so that we can ensure that
Gt(x) ⊆ Gt−1(x) ∪ ∂Gt−1(x) ⊆ Gt−2(x) ∪ ∂2Gt−2(x). (3) Many real-world graphs follow the small-world pattern, and the six degrees of separation implies G0(x) ∪ ∂6G0(x) ≈ G. The upper bound of Gt(x) can grow exponentially in t, and there is no guarantee that Gt(x) will not explode. Proposition. Given a 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 d is larger than p, i.e., P (deg(v) ≤ d) > p,∀v ∈ V . Considering a sequence of consecutively expanding subgraphs (G0, G1, . . . , GT ), starting with G0 = {v}, for all t ≥ 1, we can ensure
P ( |VGt | ≤
d(d− 1)t − 2 d− 2
) > p d(d−1)t−1−2 d−2 . (4)
The proposition implies the guarantee of upper-bounding |VGt(x)| becomes exponentially looser and weaker as t 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 ∆Gt(x) such that Gt(x) = Gt−1(x) ∪ ∆Gt(x). To prevent Gt(x) from explosion, we need to constrain ∆Gt(x).
Sampling strategies. A simple but effective way to handle the large scale is to do sampling.
1. ∆Gt(x) = ∂̂Gt−1(x), where we sample nodes from the boundary of Gt−1(x).
2. ∆Gt(x) = ∂Ĝt−1(x), where we take the boundary of sampled nodes from Gt−1(x).
3. ∆Gt(x) = ∂̂Ĝt−1(x), where we sample nodes twice from Gt−1(x) and from ∂Ĝt−1(x).
4. ∆Gt(x) = ∂̂Ĝt−1(x), where we sample nodes three times with the last from ∂̂Ĝt−1(x).
Obviously, we have ∂̂Ĝt−1(x) ⊆ ∂̂Ĝt−1(x) ⊆ ∂Ĝt−1(x) and Gt−1(x) ∪ ∂Ĝt−1(x) ⊆ Gt−1(x) ∪ ∂Gt−1(x). Further, we let N1 and N3 be the maximum number of sampled nodes in ∂Ĝt−1(x) and
the last sampling of ∂̂Ĝt−1(x) respectively and let N2 be per-node maximum sampled neighbors in ∂̂Gt−1(x), and then we can obtain much tighter guarantee as follow:
1We assume per-example per-edge per-dimension time cost as a unit time.
1. P (|V∆Gt(x)| ≤ N1(d− 1)) > pN1 for ∂Ĝt−1(x).
2. P (|V∆Gt(x)| ≤ N1N2) = 1 and P (|V∆Gt(x)| ≤ N1 ·min(d−1, N2)) > pN1 for ∂̂Ĝt−1(x).
3. P (|V∆Gt(x)| ≤ min(N1N2, N3)) = 1 for ∂̂Ĝt−1(x).
Attention strategies. Although we guarantee |VGT (x)| ≤ 1 + T min(N1N2, N3) by ∂̂Ĝt−1(x) and constrain the growth of Gt−1(x) by decreasing either N1N2 or N3, smaller sampling size means less area explored and less chance to hit target nodes. To make efficient selection rather than random sampling, we apply attention mechanism to do the top-K selection where K can be small. We
change ∂̂Ĝt−1(x) to ∂̂Gt−1(x)̃ where ∼ represents the operation of attending over nodes and picking the top-K. There are two types of attention operations, one applied to Gt−1(x) and the other
applied to ∂̂Gt−1(x)̃. Note that the size of ∂̂Gt−1(x)̃ might be much larger if we intend to sample more nodes with larger N2 to sufficiently explore the boundary. Nevertheless, we can address this problem by using smaller dimensions to compute attention, since attention on each node is a scalar requiring a smaller capacity compared to node representation vectors computed in message passing.

heading: 3 DPMPN MODEL

heading: 3.1 ARCHITECTURE DESIGN FOR KNOWLEDGE GRAPH REASONING
text: Our model architecture as shown in Figure 2 consists of:
• IGNN module: performs full message passing to compute full-graph node representations. • AGNN module: performs a batch of pruned message passing to compute input-dependent node
representations which also make use of underlying representations from IGNN. • Attention Module: performs a 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 et al., 2017). If the full graph has an extremely large number of edges, we sample a subset of edges, Êτ ⊂ 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 v has a state Hτv,: at step τ , where the initial H0v,: = ev . Each edge 〈v′, r, v〉 produces a message, denoted by M τ 〈v′,r,v〉,: at step τ . The computation components include:
• Message function: Mτ〈v′,r,v〉,: = ψIGNN(H τ v′,:, er,H τ v,:), where 〈v′, r, v〉 ∈ Êτ . • Message aggregation: Mτv,: = 1√Nτ (v) ∑ v′,rM τ 〈v′,r,v〉,:, where 〈v′, r, v〉 ∈ Êτ .
• Node state update function: Hτ+1v,: = H τ v,: + δIGNN(H τ v,:,M
τ v,:, ev), where v ∈ V .
We compute messages only for sampled edges, 〈v′, r, v〉 ∈ Êτ , each step. Functions ψIGNN and δIGNN are implemented by a two-layer MLP (using leakyReLu for the first layer and tanh for the second) with input arguments concatenated respectively. Messages are aggregated by dividing the sum by the square root of Nτ (v), the number of neighbors that send messages to v, preserving the scale of variance. We use a residual adding to update each node state instead of a GRU or a LSTM. After running for T steps, we output a pooling result or simply the last, denoted by H = HT , to feed into downstream modules.
AGNN module. AGNN is input-dependent, which means node states depend on input query x = 〈head, rel, ?〉, denoted by Htv,:(x). We implement pruned message passing, running on small subgraphs each conditioned on an input query. We leverage the sparsity and only save Htv,:(x) for visited nodes v ∈ VGt(x). When t = 0, we start from node head with VG0(x) = {vhead}. When computing messages, denoted byM t〈v′,r,v〉,:(x), we use an attending-sampling-attending procedure, explained in Section 3.2, to constrain the number of computed edges. The computation components include:
• Message function: M t〈v′,r,v〉,:(x) = ψAGNN(H t v′,:(x), cr(x),H t v,:(x)), where 〈v′, r, v〉 ∈
EGt(x) 2, and cr(x) = [er, qhead, qrel] represents a context vector.
• Message aggregation: M tv,:(x) = 1√Nt(v) ∑ v′,rM t 〈v′,r,v〉,:(x), where 〈v ′, r, v〉 ∈ EGt(x).
• Node state attending function: H̃t+1v,: (x) = at+1v WHv,:, where at+1v is an attention score.
• Node state update function: Ht+1v,: (x) = Htv,:(x) + δAGNN(Htv,:(x),M t v,:(x), c t+1 v (x)), where
ct+1v (x) = [H̃ t+1 v,: (x), qhead, qrel] also represents a context vector.
Query context is defined by its head and relation embeddings, i.e., qhead = ehead and qrel = erel. We introduce a node state attending function to pass node representation information from IGNN to AGNN weighted by a scalar attention score at+1v and projected by a learnable matrix W . We initializeH0v,:(x) = Hv,: for node v ∈ VG0(x), letting unseen nodes hold zero states. Attention module. Attention over T steps is represented by a sequence of node probability distributions, denoted by at (t = 1, 2 . . . , T ). The initial distribution a0 is a one-hot vector with a0[vhead] = 1. To spread attention, we need to compute transition matrices T t each step. Since it is conditioned on both IGNN and AGNN, we capture two types of interaction between v′ and v: Htv′,:(x) ∼Htv,:(x), andHtv′,:(x) ∼Hv,:. The former favors visited nodes, while the latter is used to attend to unseen neighboring nodes.
T t:,v′ = softmaxv∈Nt(v′) (∑
r α1(H
t v′,:(x), cr(x),H t v,:(x)) + α2(H t v′,:(x), cr(x),Hv,:) ) α1(·) = MLP(Htv′,:(x), cr(x))TW1MLP(Htv,:(x), cr(x)) α2(·) = MLP(Htv′,:(x), cr(x))TW2MLP(Hv,:, cr(x)) (5)
whereW1 andW2 are two learnable matrices. Each MLP uses one single layer with the leakyReLu activation. To reduce the complexity for computing T t, we use nodes v′ ∈ V
Gt(x)̃ , which contains
nodes with the k-largest attention scores at step t, and use nodes v sampled from v′’s neighbors to compute attention transition for the next step. Due to the fact that nodes v′ result from the top-k pruning, the loss of attention may occur to diminish the total amount. Therefore, we use a renormalized version, at+1 = T tat/‖T tat‖, to compute new attention scores. We use attention scores at the final step as the probability to predict the tail node.
2In practice, we can use a smaller set of edges than EGt(x) to pass messages as discussed in Section 3.2

heading: 3.2 COMPLEXITY REDUCTION BY ITERATIVE ATTENDING, SAMPLING AND ATTENDING
text: AGNN deals with each subgraph relying on input x and keeps a few selected nodes in VGt(x), called visited nodes. Initially, VG0(x) contains only one node vhead, and then VGt(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 it covers almost all nodes after a few steps. The key to address the problem is to 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, Gt(x)̃, selected according to attention scores at. Given this horizon, we may still need node sampling over the neighborhood N(Gt(x)̃) in some cases where a hub node of extremely high degree exists to cause an extremely large neighborhood. We introduce an attending-to horizon, denoted by
N̂(Gt(x)̃), inside the sampling horizon, denoted by N̂(Gt(x)̃). The attention module runs within the sampling horizon with smaller dimensions exchanged for sampling more neighbors for a 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 horizon according to newly computed attention scores at+1. Then, message passing
iteration at step t in AGNN can be further constrained on edges between Gt(x)̃ and N̂(Gt(x)̃), a smaller set than EGt(x). We illustrate this procedure in Figure 3.

heading: 4 EXPERIMENTS
text: Datasets. We use six large KG datasets: FB15K, FB15K-237, WN18, WN18RR, NELL995, and YAGO3-10. FB15K-237 (Toutanova & Chen, 2015) is sampled from FB15K (Bordes et al., 2013) with redundant relations removed, and WN18RR (Dettmers et al., 2018) is a subset of WN18 (Bordes et al., 2013) removing triples that cause test leakage. Thus, they are both considered more challenging. NELL995 (Xiong et al., 2017) has separate datasets for 12 query relations each corresponding to a single-query-relation KBC task. YAGO3-10 (Mahdisoltani et al., 2014) contains the largest KG with millions of edges. Their statistics are shown in Table 1. We find some statistical differences between train and validation (or test). In a KG with all training triples as its edges, a triple (head, rel, tail) is considered as a multi-edge triple if the KG contains other triples that also connect head and tail ignoring the direction. We notice that FB15K-237 is a special case compared to the others, as there are no edges in its KG directly linking any pair of head and tail in validation (or test). Therefore, when using training triples as queries to train our model, given a batch, for FB15K-237, 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@1 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 et al., 2018). We create a KG, a 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-loop 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-237, WN18RR,
FB15K, WN18, and YAGO3-10, and use the mean average precision (MAP) for NELL995’s singlequery-relation KBC tasks. For NELL995, we follow the same evaluation procedure as in (Xiong et al., 2017; Das et 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 link3 below. We run three times for each hyperparameter setting per dataset to report the means and standard deviations. See hyperparameter details in the appendix.
Baselines. We compare our model against embedding-based approaches, including TransE (Bordes et al., 2013), TransR (Lin et al., 2015b), DistMult (Yang et al., 2015), ConvE (Dettmers et al., 2018), ComplE (Trouillon 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., 2017), MINERVA (Das et al., 2018), and M-Walk (Shen et al., 2018), and also that uses learned neural logic, NeuralLP (Yang et al., 2017).
Comparison results and analysis. We report comparison on FB15K-23 and WN18RR in Table 2. 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 a 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-based baselines, with a certain ability to do reasoning, perform worse than we expect. We argue that it might be inappropriate to 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 1 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
3https://github.com/anonymousauthor123/DPMPN
with each other to produce a decision collectively. We also run our model on FB15K, WN18, and YAGO3-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 training queries to train model to generalize as shown in Figure 4(A). Compared to less expensive embedding-based 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 a 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, we 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 to predict a tail given an input query. However, AGNN is inputdependent, 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 Hv,: but instead use node embeddings as Hv,:, 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 set which runs IGNN for two steps against the second one which totally shuts IGNN down. The results in Figure 4(B) (and Figure 7(B) in Appendix) show that IGNN brings an amount of gains in each metric on WN18RR (and FB15K-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 a subgraph can expand over. These factors affect computation 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 a target to gain some performance. However, the experimental results in Figure 4(C)(D) show that it is not always the case. In Figure 4(E), we can see that increasing the maximum number of attending-
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 a limited memory do not allow for a too large number of sampled or attended nodes especially for Max-attending-from-per-step. The detailed explanations can be found in attention strategies in Section 2 where the upper bound is controlled by N1N2 and N3 (Max-attending-from-per-step corresponding to N1, Max-sampling-per-node to N2, and Max-attending-to-per-step to N3). In N1N2, Section 3.2 suggests that we should sample more by a large N2 but attend less by a small N1. Figure 4(F) suggests that the propagation steps of AGNN should not go below four.
Attention flow analysis. If the flow-style attention really captures the way we reason about the world, its process should be conducted in a diverging-converging thinking pattern. Intuitively, first, for the diverging thinking phase, we search and collect ideas as much as we can; then, for the 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 top-1,3,5 nodes. As we expect, attention is more focused at the final step and the beginning.
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 to our standard hyperparameter settings in the appendix. Note that there is always a trade-off between complexity 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 6(A)-(D), using the same settings as we do in the horizon analysis. We can see that Max-attending-from-per-step and #Steps-in-AGNN affect the training time significantly while Max-sampling-per-node and Max-attending-to-per-step affect very slightly. Therefore, we can use smaller Max-sampling-per-node and Max-attending-to-per-step in order to gain a larger batch size, making the computation more efficiency as shown in Figure 6(E).
Visualization. To further demonstrate the reasoning capability, we show visualization results of some pruned subgraphs on 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 1. See the appendix for detailed analysis and more visualization results.
Discussion of the limitation. Although DPMPN shows a 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.

heading: 5 RELATED WORK
text: Knowledge graph reasoning. Early work, including TransE (Bordes et al., 2013) and its analogues (Wang et al., 2014; Lin et al., 2015b; Ji et al., 2015), DistMult (Yang et al., 2015), ConvE (Dettmers et al., 2018) and ComplEx (Trouillon et al., 2016), focuses on learning embeddings of entities and relations. Some recent works of this line (Sun et al., 2018; Lacroix et al., 2018) achieve high accuracy. Another line aims to learn inference paths (Lao et al., 2011; Guu et al., 2015; 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 al., 2018), and M-Walk (Shen et al., 2018), which use RL 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 as the key for combinatorial generalization, taking the form of entity- and relation-centric organization to reason about the composition structure of the world (Craik, 1952; Lake et al., 2017). A multitude of recent implementations (Battaglia et al., 2018) encode relational inductive biases into neural networks to exploit graph-structured representation, including graph convolution networks (GCNs) (Bruna et al., 2014; Henaff et al., 2015; Duvenaud et al., 2015; Kearnes et al., 2016; Defferrard et al., 2016; Niepert et al., 2016; Kipf & Welling, 2017; Bronstein et al., 2017) and graph neural networks (Scarselli et al., 2009; Li et al., 2016; Santoro et al., 2017; Battaglia et al., 2016; Gilmer et al., 2017). Variants of 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 a general-purpose learnable physics engine, and two of its variants are visual interaction networks (Watters et al., 2017) and vertex attention interaction networks (Hoshen, 2017); Message passing neural networks (Gilmer et al., 2017) unify various GCNs and GNNs into a general message passing formalism by analogy to the one in graphical models.
Attention mechanism on graphs. Neighborhood attention operation can enhance GNNs’ representation power (Velickovic et al., 2018; Hoshen, 2017; Wang et al., 2018; Kool, 2018). These approaches often use multi-head self-attention to 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 interaction in experiments. However, a flow-style design of attention in (Xu et al., 2018b) shows a way to model long-range attention, stringing isolated attention operations by transition matrices.

heading: 6 CONCLUSION
text: We introduce Dynamically Pruned Message Passing Networks (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, a 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.

heading: Appendix

heading: 7 PROOF
text: Proposition. Given a 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 d is larger than p, i.e., P (deg(v) ≤ d) > p,∀v ∈ V . Considering a sequence of consecutively expanding subgraphs (G0, G1, . . . , GT ), starting with G0 = {v}, for all t ≥ 1, we can ensure
P ( |VGt | ≤
d(d− 1)t − 2 d− 2
) > p d(d−1)t−1−2 d−2 . (6)
Proof. We consider the extreme case of greedy consecutive expansion, where Gt = Gt−1 ∪∆Gt = Gt−1 ∪ ∂Gt−1, since if this case satisfies the inequality, any case of consecutive expansion can also satisfy it. By definition, all the subgraphs Gt are a connected graph. Here, we use ∆V t to denote V∆Gt for short. In the extreme case, we can ensure that the newly added nodes ∆V t at step t only belong to the neighborhood of the last added nodes ∆V t−1. Since for t ≥ 2 each node in ∆V t−1 already has at least one edge within Gt−1 due to the definition of connected graphs, we can have
P ( |∆V t| ≤ |∆V t−1|(d− 1) ) > p|∆V t−1|. (7)
For t = 1, we have P (|∆V 1| ≤ d) > p and thus P ( |VG1 | ≤ 1 + d ) > p. (8)
For t ≥ 2, based on |VGt | = 1 + |∆V 1|+ . . .+ |∆V t|, we obtain P ( |VGt | ≤ 1 + d+ d(d− 1) + . . .+ d(d− 1)t−1 ) > p1+d+d(d−1)+...+d(d−1) t−2 , (9)
which is
P ( |VGt | ≤
d(d− 1)t − 2 d− 2
) > p d(d−1)t−1−2 d−2 . (10)
We can find that t = 1 also satisfies this inequality.

heading: 8 HYPERPARAMETER SETTINGS
text: The hyperparameters can be categorized into three groups:
• Normal hyperparameters, including batch size, n dims att, n dims, learning rate, grad clipnorm, and n epochs. We set smaller dimensions, n dims att, 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 a sampled neighborhood, in concert with the idea in the key-value mechanism (Bengio, 2017). We set n epochs = 1 in most cases, indicating that our model can be trained well by one epoch only due to its fast convergence. • The hyperparameters in charge of the sampling-attending horizon, including
max sampling per step that controls the maximum number to sample edges per step in IGNN, and max sampling per node, max attending from per step and max attending to 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 a sampled neighborhood for attending-to per step per input in AGNN. • The hyperparameters in charge of the searching horizon, including n steps in IGNN representing
the number of propagation steps to run standard message passing in IGNN, and n steps in 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 to us. In some cases, to deal with a very large knowledge graph with limited resources, we need to make a trade-off between efficiency and effectiveness. For example, each of NELL995’s single-query-relation tasks has a 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 samplingattending horizon without any concern for waiting too long to finish one epoch.

heading: 9 MORE EXPERIMENTAL RESULTS

heading: 10 MORE VISUALIZATION RESUTLS

heading: 10.1 CASE STUDY ON THE ATHLETEPLAYSFORTEAM TASK
text: In the case shown in Figure 9, the query is (concept personnorthamerica michael turner, concept:athleteplays-forteam, ?) and a true answer is concept sportsteam falcons. From Figure 9, we can see our model learns that (concept personnorthamerica michael turner, concept:athletehomestadium, concept stadiumoreventvenue georgia dome) and (concept stadiumoreventvenue georgia dome, concept:teamhomestadium inv, concept sportsteam falcons) are two important facts to support the answer of concept sportsteam falcons. Besides, other facts, such as (concept athlete joey harrington, concept:athletehomestadium, concept stadiumoreventvenue georgia dome) and (concept athletejoey harrington, concept:athleteplaysforteam, concept sportsteam falcons), provide a vivid example
that a person or an athlete with concept stadiumoreventvenue georgia dome as his or her home stadium might play for the team concept sportsteam falcons. We have such examples more than one, like concept athlete roddy white’s and concept athlete quarterback matt ryan’s. The entity con-
cept sportsleague nfl cannot help us 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 pattern.

heading: For the AthletePlaysForTeam task
text: Query : ( concept personnor thamer ica michae l tu rner , concept : a th le tep lays fo r team , concept spor ts team fa lcons )
Selected key edges : concept personnor thamer ica michae l tu rner , concept : agentbe longstoorgan iza t ion , concep t spo r t s l eague n f l concept personnor thamer ica michae l tu rner , concept : athletehomestadium , concept stadiumoreventvenue georgia dome concep t spo r t s league n f l , concept : agentcompeteswithagent , concep t spo r t s l eague n f l concep t spo r t s league n f l , concept : agentcompeteswithagent inv , concep t spo r t s l eague n f l concep t spo r t s league n f l , concept : teamplays in league inv , concept spor ts team sd chargers concep t spo r t s league n f l , concept : leaguestadiums , concept stadiumoreventvenue georgia dome concep t spo r t s league n f l , concept : teamplays in league inv , concept spor ts team fa lcons concep t spo r t s league n f l , concept : agen tbe longs toorgan iza t ion inv , concept personnor thamer ica michae l tu rner concept stadiumoreventvenue georgia dome , concept : leaguestadiums inv , concep t spo r t s l eague n f l concept stadiumoreventvenue georgia dome , concept : teamhomestadium inv , concept spor ts team fa lcons concept stadiumoreventvenue georgia dome , concept : ath letehomestadium inv , c o n c e p t a t h l e t e j o e y h a r r i n g t o n concept stadiumoreventvenue georgia dome , concept : ath letehomestadium inv , concep t a th le te roddy wh i t e concept stadiumoreventvenue georgia dome , concept : ath letehomestadium inv , concept coach deange lo ha l l concept stadiumoreventvenue georgia dome , concept : ath letehomestadium inv , concept personnor thamer ica michae l tu rner concep t spo r t s league n f l , concept : subpa r t o f o rgan i za t i on i nv , concept spor ts team oak land ra iders concept spor ts team sd chargers , concept : teamplaysinleague , concep t spo r t s l eague n f l concept spor ts team sd chargers , concept : teamplaysagainstteam , concept spor ts team fa lcons concept spor ts team sd chargers , concept : teamplaysagainst team inv , concept spor ts team fa lcons concept spor ts team sd chargers , concept : teamplaysagainstteam , concep t spor ts team oak land ra iders concept spor ts team sd chargers , concept : teamplaysagainst team inv , concept spor ts team oak land ra iders concept spor ts team fa lcons , concept : teamplaysinleague , concep t spo r t s l eague n f l concept spor ts team fa lcons , concept : teamplaysagainstteam , concept spor ts team sd chargers concept spor ts team fa lcons , concept : teamplaysagainst team inv , concept spor ts team sd chargers concept spor ts team fa lcons , concept : teamhomestadium , concept stadiumoreventvenue georgia dome concept spor ts team fa lcons , concept : teamplaysagainstteam , concep t spor ts team oak land ra iders concept spor ts team fa lcons , concept : teamplaysagainst team inv , concept spor ts team oak land ra iders concept spor ts team fa lcons , concept : a th le te ledspo r t s team inv , c o n c e p t a t h l e t e j o e y h a r r i n g t o n c o n c e p t a t h l e t e j o e y h a r r i n g t o n , concept : athletehomestadium , concept stadiumoreventvenue georgia dome c o n c e p t a t h l e t e j o e y h a r r i n g t o n , concept : a th le te ledspor ts team , concept spor ts team fa lcons c o n c e p t a t h l e t e j o e y h a r r i n g t o n , concept : a th le tep lays fo r team , concept spor ts team fa lcons concep t a th le te roddy wh i te , concept : athletehomestadium , concept stadiumoreventvenue georgia dome concep t a th le te roddy wh i te , concept : a th le tep lays fo r team , concept spor ts team fa lcons concept coach deangelo hal l , concept : athletehomestadium , concept stadiumoreventvenue georgia dome
concept coach deangelo hal l , concept : a th le tep lays fo r team , concep t spor ts team oak land ra iders concep t spo r t s league n f l , concept : teamplays in league inv , concept spor ts team new york g iants concept spor ts team sd chargers , concept : teamplaysagainst team inv , concept spor ts team new york g iants concept spor ts team fa lcons , concept : teamplaysagainstteam , concept spor ts team new york g iants concept spor ts team fa lcons , concept : teamplaysagainst team inv , concept spor ts team new york g iants concept spor ts team oak land ra iders , concept : teamplaysagainst team inv , concept spor ts team new york g iants concept spor ts team oak land ra iders , concept : teamplaysagainstteam , concept spor ts team sd chargers concept spor ts team oak land ra iders , concept : teamplaysagainst team inv , concept spor ts team sd chargers concept spor ts team oak land ra iders , concept : teamplaysagainstteam , concept spor ts team fa lcons concept spor ts team oak land ra iders , concept : teamplaysagainst team inv , concept spor ts team fa lcons concept spor ts team oak land ra iders , concept : agentcompeteswithagent , concep t spor ts team oak land ra iders concept spor ts team oak land ra iders , concept : agentcompeteswithagent inv , concept spor ts team oak land ra iders concept spor ts team new york g iants , concept : teamplaysagainstteam , concept spor ts team sd chargers concept spor ts team new york g iants , concept : teamplaysagainstteam , concept spor ts team fa lcons concept spor ts team new york g iants , concept : teamplaysagainst team inv , concept spor ts team fa lcons concept spor ts team new york g iants , concept : teamplaysagainstteam , concept spor ts team oak land ra iders
10.2 MORE RESULTS

heading: For the AthletePlaysInLeague task
text: Query : ( concept personnor thamer ica mat t t reanor , concept : a th le tep lays in league , concept spor ts league mlb )
Selected key edges : concept personnor thamer ica mat t t reanor , concept : a t h l e t e f l y o u t t o s p o r t s t e a m p o s i t i o n , concep t spo r t s teampos i t i on cen te r concept personnor thamer ica mat t t reanor , concept : a t h l e t ep l aysspo r t , concep t spo r t baseba l l concep t spor ts teampos i t i on cen te r , concept : a t h l e t e f l y o u t t o s p o r t s t e a m p o s i t i o n i n v , concept personus or lando hudson concep t spor ts teampos i t i on cen te r , concept : a t h l e t e f l y o u t t o s p o r t s t e a m p o s i t i o n i n v , concept a th le te ben hendr ickson concep t spor ts teampos i t i on cen te r , concept : a t h l e t e f l y o u t t o s p o r t s t e a m p o s i t i o n i n v , co nc ep t co ac h j j ha rd y concep t spor ts teampos i t i on cen te r , concept : a t h l e t e f l y o u t t o s p o r t s t e a m p o s i t i o n i n v , concep t a th le te hun te r pence concep t spor t baseba l l , concept : a t h l e t e p l a y s s p o r t i n v , concept personus or lando hudson concep t spor t baseba l l , concept : a t h l e t e p l a y s s p o r t i n v , concept a th le te ben hendr ickson concep t spor t baseba l l , concept : a t h l e t e p l a y s s p o r t i n v , c onc ep t co ac h j j ha rd y concep t spor t baseba l l , concept : a t h l e t e p l a y s s p o r t i n v , concep t a th le te hun te r pence concept personus or lando hudson , concept : a th le tep lays in league , concept spor ts league mlb concept personus or lando hudson , concept : a t h l e t ep l aysspo r t , concep t spo r t baseba l l concept a th le te ben hendr ickson , concept : coachesinleague , concept spor ts league mlb concept a th le te ben hendr ickson , concept : a t h l e t ep l aysspo r t , concep t spo r t baseba l l
concep t coach j j ha rdy , concept : coachesinleague , concept spor ts league mlb concep t coach j j ha rdy , concept : a th le tep lays in league , concept spor ts league mlb concep t coach j j ha rdy , concept : a t h l e t ep l ayssp o r t , concep t spo r t baseba l l concept a th le te hunter pence , concept : a th le tep lays in league , concept spor ts league mlb concept a th le te hunter pence , concept : a t h l e t ep l aysspo r t , concep t spo r t baseba l l concept spor ts league mlb , concept : coachesin league inv , concep t a th le te ben hendr ickson concept spor ts league mlb , concept : coachesin league inv , con ce p t co ac h j j ha rd y

heading: For the AthleteHomeStadium task
text: Query : ( concep t a th le te e l i mann ing , concept : athletehomestadium , concept s tad iumoreventvenue giants s tad ium )
Selected key edges : concep t a th le te e l i mann ing , concept : personbe longstoorgan izat ion , concept spor ts team new york g iants concep t a th le te e l i mann ing , concept : a th le tep lays fo r team , concept spor ts team new york g iants concep t a th le te e l i mann ing , concept : a th le te ledspor ts team , concept spor ts team new york g iants concep t a th le te e l i mann ing , concept : a th le tep lays in league , concep t spo r t s l eague n f l concep t a th le te e l i mann ing , concept : f a the ro fpe rson inv , concept male archie manning concept spor ts team new york g iants , concept : teamplaysinleague , concep t spo r t s l eague n f l concept spor ts team new york g iants , concept : teamhomestadium , concept s tad iumoreventvenue giants s tad ium concept spor ts team new york g iants , concept : personbe longs toorgan iza t ion inv , concep t a th le te e l i mann ing concept spor ts team new york g iants , concept : a th l e t ep lays fo r t eam inv , concep t a th le te e l i mann ing concept spor ts team new york g iants , concept : a th le te ledspo r t s team inv , concep t a th le te e l i mann ing concep t spo r t s league n f l , concept : teamplays in league inv , concept spor ts team new york g iants concep t spo r t s league n f l , concept : agentcompeteswithagent , concep t spo r t s l eague n f l concep t spo r t s league n f l , concept : agentcompeteswithagent inv , concep t spo r t s l eague n f l concep t spo r t s league n f l , concept : leaguestadiums , concept s tad iumoreventvenue giants s tad ium concep t spo r t s league n f l , concept : a t h l e t e p l a y s i n l e a g u e i n v , concep t a th le te e l i mann ing concept male archie manning , concept : fa thero fperson , concep t a th le te e l i mann ing concep t spo r t s league n f l , concept : leaguestadiums , concept stadiumoreventvenue paul brown stadium concept s tad iumoreventvenue giants stad ium , concept : teamhomestadium inv , concept spor ts team new york g iants concept s tad iumoreventvenue giants stad ium , concept : leaguestadiums inv , concep t spo r t s l eague n f l concept s tad iumoreventvenue giants stad ium , concept : p rox y fo r i n v , c o n c e p t c i t y e a s t r u t h e r f o r d c o n c e p t c i t y e a s t r u t h e r f o r d , concept : p roxy for , concept s tad iumoreventvenue giants s tad ium concept stadiumoreventvenue paul brown stadium , concept : leaguestadiums inv , concep t spo r t s l eague n f l
For the AthletePlaysSport task
Query : ( concep t a th le te ve rnon we l l s , concept : a t h l e t ep l aysspo r t , concep t spo r t baseba l l )
Selected key edges : concep t a th le te ve rnon we l l s , concept : a th le tep lays in league , concept spor ts league mlb concep t a th le te ve rnon we l l s , concept : coachwontrophy , concept awardt rophytournament wor ld ser ies concep t a th le te ve rnon we l l s , concept : agen tco l l abo ra tesw i thagen t inv , concep t spor ts team blue jays concep t a th le te ve rnon we l l s , concept : personbelongstoorgan izat ion , concep t spor ts team blue jays concep t a th le te ve rnon we l l s , concept : a th le tep lays fo r team , concep t spor ts team blue jays concep t a th le te ve rnon we l l s , concept : a th le te ledspor ts team , concep t spor ts team blue jays concept spor ts league mlb , concept : teamplays in league inv , concept sportsteam dodgers concept spor ts league mlb , concept : teamplays in league inv , concept sportsteam yankees concept spor ts league mlb , concept : teamplays in league inv , concep t spo r t s t eam p i t t sbu rgh p i r a t es concept awardt rophytournament wor ld ser ies , concept : teamwontrophy inv , concept sportsteam dodgers concept awardt rophytournament wor ld ser ies , concept : teamwontrophy inv , concept sportsteam yankees concept awardt rophytournament wor ld ser ies , concept : awardtrophytournament is thechampionshipgameof thenat ionalspor t ,
concep t spo r t baseba l l concept awardt rophytournament wor ld ser ies , concept : teamwontrophy inv , concep t spo r t s t eam p i t t sbu rgh p i r a t es concept spor ts team blue jays , concept : teamplaysinleague , concept spor ts league mlb concept spor ts team blue jays , concept : teamplaysagainstteam , concept sportsteam yankees concept spor ts team blue jays , concept : teamplayssport , concep t spo r t baseba l l concept sportsteam dodgers , concept : teamplaysagainstteam , concept sportsteam yankees concept sportsteam dodgers , concept : teamplaysagainst team inv , concept sportsteam yankees concept sportsteam dodgers , concept : teamwontrophy , concept awardt rophytournament wor ld ser ies concept sportsteam dodgers , concept : teamplayssport , concep t spo r t baseba l l concept sportsteam yankees , concept : teamplaysagainstteam , concept sportsteam dodgers concept sportsteam yankees , concept : teamplaysagainst team inv , concept sportsteam dodgers concept sportsteam yankees , concept : teamwontrophy , concept awardt rophytournament wor ld ser ies concept sportsteam yankees , concept : teamplayssport , concep t spo r t baseba l l concept sportsteam yankees , concept : teamplaysagainstteam , concep t spo r t s t eam p i t t sbu rgh p i r a t es concept sportsteam yankees , concept : teamplaysagainst team inv , concep t spo r t s t eam p i t t sbu rgh p i r a t es concep t spor t baseba l l , concept : teamplaysspor t inv , concept sportsteam dodgers concep t spor t baseba l l , concept : teamplaysspor t inv , concept sportsteam yankees concep t spor t baseba l l , concept : awardt rophytournament is thechampionsh ipgameof thenat iona lspor t inv ,
concept awardt rophytournament wor ld ser ies concep t spor t baseba l l , concept : teamplaysspor t inv , concep t spo r t s t eam p i t t sbu rgh p i r a t es concep t spo r t s team p i t t sbu rgh p i ra tes , concept : teamplaysagainstteam , concept sportsteam yankees concep t spo r t s team p i t t sbu rgh p i ra tes , concept : teamplaysagainst team inv , concept sportsteam yankees
concep t spo r t s team p i t t sbu rgh p i ra tes , concept : teamwontrophy , concept awardt rophytournament wor ld ser ies concep t spo r t s team p i t t sbu rgh p i ra tes , concept : teamplayssport , concep t spo r t baseba l l

heading: For the TeamPlaysSport task
text: Query : ( concept spor ts team red wings , concept : teamplayssport , concept spor t hockey )
Selected key edges : concept spor ts team red wings , concept : teamplaysagainstteam , concept spor ts team montrea l canadiens concept spor ts team red wings , concept : teamplaysagainst team inv , concept spor ts team montrea l canadiens concept spor ts team red wings , concept : teamplaysagainstteam , concep t spor ts team b lue jacke ts concept spor ts team red wings , concept : teamplaysagainst team inv , concep t spor ts team b lue jacke ts concept spor ts team red wings , concept : works fo r inv , c o n c e p t a t h l e t e l i d s t r o m concept spor ts team red wings , concept : o rgan iza t ionh i redperson , c o n c e p t a t h l e t e l i d s t r o m concept spor ts team red wings , concept : a th l e t ep lays fo r t eam inv , c o n c e p t a t h l e t e l i d s t r o m concept spor ts team red wings , concept : a th le te ledspo r t s team inv , c o n c e p t a t h l e t e l i d s t r o m concept spor ts team montreal canadiens , concept : teamplaysagainstteam , concept spor ts team red wings concept spor ts team montreal canadiens , concept : teamplaysagainst team inv , concept spor ts team red wings concept spor ts team montreal canadiens , concept : teamplaysinleague , concep t spor ts league nh l concept spor ts team montreal canadiens , concept : teamplaysagainstteam , concep t spor ts team lea fs concept spor ts team montreal canadiens , concept : teamplaysagainst team inv , concep t spor ts team lea fs concept spor ts team blue jacke ts , concept : teamplaysagainstteam , concept spor ts team red wings concept spor ts team blue jacke ts , concept : teamplaysagainst team inv , concept spor ts team red wings concept spor ts team blue jacke ts , concept : teamplaysinleague , concep t spor ts league nh l c o n c e p t a t h l e t e l i d s t r o m , concept : worksfor , concept spor ts team red wings c o n c e p t a t h l e t e l i d s t r o m , concept : o rgan i za t i onh i redpe rson inv , concept spor ts team red wings c o n c e p t a t h l e t e l i d s t r o m , concept : a th le tep lays fo r team , concept spor ts team red wings c o n c e p t a t h l e t e l i d s t r o m , concept : a th le te ledspor ts team , concept spor ts team red wings concept spor ts team red wings , concept : teamplaysinleague , concep t spor ts league nh l concept spor ts team red wings , concept : teamplaysagainstteam , concep t spor ts team lea fs concept spor ts team red wings , concept : teamplaysagainst team inv , concep t spor ts team lea fs concept spor ts league nh l , concept : agentcompeteswithagent , concep t spor ts league nh l concept spor ts league nh l , concept : agentcompeteswithagent inv , concep t spor ts league nh l concept spor ts league nh l , concept : teamplays in league inv , concep t spor ts team lea fs concept spor ts team leafs , concept : teamplaysinleague , concep t spor ts league nh l concept spor ts team leafs , concept : teamplayssport , concept spor t hockey

heading: For the OrganizationHeadQuarteredInCity task
text: Query : ( concept company disney , concept : o rgan i za t i onheadquar te red inc i t y , concep t c i t y burbank )
Selected key edges : concept company disney , concept : headquarteredin , concep t c i t y burbank concept company disney , concept : subpa r t o f o rgan i za t i on i nv , concept websi te network concept company disney , concept : works fo r inv , concep t ceo robe r t i ge r concept company disney , concept : p ro xy f o r i n v , concep t ceo robe r t i ge r concept company disney , concept : pe rson leadsorgan iza t ion inv , concep t ceo robe r t i ge r concept company disney , concept : ceoof inv , concep t ceo robe r t i ge r concept company disney , concept : pe rson leadsorgan iza t ion inv , concep t ceo je f f r ey ka tzenbe rg concept company disney , concept : o rgan iza t ionh i redperson , concep t ceo je f f r ey ka tzenbe rg concept company disney , concept : o rgan iza t ion terminatedperson , concep t ceo je f f r ey ka tzenbe rg concept c i ty burbank , concept : headquar tered in inv , concept company disney concept c i ty burbank , concept : headquar tered in inv , concept b io techcompany the wal t d isney co concept websi te network , concept : subpar to fo rgan iza t i on , concept company disney concep t ceo robe r t i ge r , concept : worksfor , concept company disney concep t ceo robe r t i ge r , concept : p roxy for , concept company disney concep t ceo robe r t i ge r , concept : person leadsorgan iza t ion , concept company disney concep t ceo robe r t i ge r , concept : ceoof , concept company disney concep t ceo robe r t i ge r , concept : topmemberoforganizat ion , concept b io techcompany the wal t d isney co concep t ceo robe r t i ge r , concept : o rgan iza t ion te rm ina tedperson inv , concept b io techcompany the wal t d isney co concep t ceo je f f rey ka tzenberg , concept : person leadsorgan izat ion , concept company disney concep t ceo je f f rey ka tzenberg , concept : o rgan i za t i onh i redpe rson inv , concept company disney concep t ceo je f f rey ka tzenberg , concept : o rgan iza t ion te rm ina tedperson inv , concept company disney concep t ceo je f f rey ka tzenberg , concept : worksfor , concept record label dreamworks skg concep t ceo je f f rey ka tzenberg , concept : topmemberoforganizat ion , concept record label dreamworks skg concep t ceo je f f rey ka tzenberg , concept : o rgan iza t ion te rm ina tedperson inv , concept record label dreamworks skg concep t ceo je f f rey ka tzenberg , concept : ceoof , concept record label dreamworks skg concept b io techcompany the wal t d isney co , concept : headquarteredin , concep t c i t y burbank concept b io techcompany the wal t d isney co , concept : o rgan i za t i onheadquar te red inc i t y , concep t c i t y burbank concept record label dreamworks skg , concept : works fo r inv , concep t ceo je f f r ey ka tzenbe rg concept record label dreamworks skg , concept : topmemberoforganizat ion inv , concep t ceo je f f r ey ka tzenbe rg concept record label dreamworks skg , concept : o rgan iza t ion terminatedperson , concep t ceo je f f r ey ka tzenbe rg concept record label dreamworks skg , concept : ceoof inv , concep t ceo je f f r ey ka tzenbe rg concept c i ty burbank , concept : a i r p o r t i n c i t y i n v , concept t ranspor ta t ion burbank g lenda le pasadena concept t ranspor ta t ion burbank g lenda le pasadena , concept : a i r p o r t i n c i t y , concep t c i t y burbank

heading: For the WorksFor task
text: Query : ( concep t sc ien t i s t ba lmer , concept : worksfor , c o n c e p t u n i v e r s i t y m i c r o s o f t )
Selected key edges : concep t sc ien t i s t ba lmer , concept : topmemberoforganizat ion , concept company microsof t concep t sc ien t i s t ba lmer , concept : o rgan iza t ion te rm ina tedperson inv , c o n c e p t u n i v e r s i t y m i c r o s o f t concept company microsoft , concept : topmemberoforganizat ion inv , concept personus steve ba l lmer concept company microsoft , concept : topmemberoforganizat ion inv , c o n c e p t s c i e n t i s t b a l m e r c o n c e p t u n i v e r s i t y m i c r o s o f t , concept : agentco l labora teswi thagent , concept personus steve ba l lmer c o n c e p t u n i v e r s i t y m i c r o s o f t , concept : pe rson leadsorgan iza t ion inv , concept personus steve ba l lmer c o n c e p t u n i v e r s i t y m i c r o s o f t , concept : pe rson leadsorgan iza t ion inv , c o n c e p t p e r s o n b i l l c o n c e p t u n i v e r s i t y m i c r o s o f t , concept : o rgan iza t ion terminatedperson , c o n c e p t s c i e n t i s t b a l m e r c o n c e p t u n i v e r s i t y m i c r o s o f t , concept : pe rson leadsorgan iza t ion inv , concept person robbie bach concept personus steve bal lmer , concept : topmemberoforganizat ion , concept company microsof t concept personus steve bal lmer , concept : agen tco l l abo ra tesw i thagen t inv , c o n c e p t u n i v e r s i t y m i c r o s o f t concept personus steve bal lmer , concept : person leadsorgan izat ion , c o n c e p t u n i v e r s i t y m i c r o s o f t concept personus steve bal lmer , concept : worksfor , c o n c e p t u n i v e r s i t y m i c r o s o f t concept personus steve bal lmer , concept : p roxy for , c o n c e p t r e t a i l s t o r e m i c r o s o f t concept personus steve bal lmer , concept : subpar to f , c o n c e p t r e t a i l s t o r e m i c r o s o f t concept personus steve bal lmer , concept : agentcont ro ls , c o n c e p t r e t a i l s t o r e m i c r o s o f t concep t pe rson b i l l , concept : person leadsorgan izat ion , c o n c e p t u n i v e r s i t y m i c r o s o f t concep t pe rson b i l l , concept : worksfor , c o n c e p t u n i v e r s i t y m i c r o s o f t concept person robbie bach , concept : person leadsorgan izat ion , c o n c e p t u n i v e r s i t y m i c r o s o f t concept person robbie bach , concept : worksfor , c o n c e p t u n i v e r s i t y m i c r o s o f t c o n c e p t r e t a i l s t o r e m i c r o s o f t , concept : p ro xy f o r i n v , concept personus steve ba l lmer c o n c e p t r e t a i l s t o r e m i c r o s o f t , concept : subpa r to f i nv , concept personus steve ba l lmer c o n c e p t r e t a i l s t o r e m i c r o s o f t , concept : agen tcon t ro l s i nv , concept personus steve ba l lmer

heading: For the PersonBornInLocation task
text: Query : ( concept person mark001 , concept : personborn in loca t ion , con cep t co un t y yo r k c i t y )
Selected key edges : concept person mark001 , concept : persongraduatedf romunivers i ty , c o n c e p t u n i v e r s i t y c o l l e g e concept person mark001 , concept : persongraduatedschool , c o n c e p t u n i v e r s i t y c o l l e g e concept person mark001 , concept : persongraduatedf romunivers i ty , c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y concept person mark001 , concept : persongraduatedschool , c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y concept person mark001 , concept : pe rsonborn inc i t y , concept c i t y hampsh i re
concept person mark001 , concept : hasspouse , concept person diane001 concept person mark001 , concept : hasspouse inv , concept person diane001 c o n c e p t u n i v e r s i t y c o l l e g e , concept : persongradua ted f romun ivers i t y inv , concept person mark001 c o n c e p t u n i v e r s i t y c o l l e g e , concept : persongraduatedschool inv , concept person mark001 c o n c e p t u n i v e r s i t y c o l l e g e , concept : persongradua ted f romun ivers i t y inv , c o n c e p t p e r s o n b i l l c o n c e p t u n i v e r s i t y c o l l e g e , concept : persongraduatedschool inv , c o n c e p t p e r s o n b i l l c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y , concept : persongradua ted f romun ivers i t y inv , concept person mark001 c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y , concept : persongraduatedschool inv , concept person mark001 c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y , concept : persongradua ted f romun ivers i t y inv , c o n c e p t p e r s o n b i l l c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y , concept : persongraduatedschool inv , c o n c e p t p e r s o n b i l l concept c i ty hampsh i re , concept : pe rsonbo rn i nc i t y i nv , concept person mark001 concept person diane001 , concept : persongraduatedf romunivers i ty , c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y concept person diane001 , concept : persongraduatedschool , c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y concept person diane001 , concept : hasspouse , concept person mark001 concept person diane001 , concept : hasspouse inv , concept person mark001 concept person diane001 , concept : personborn in loca t ion , c onc ep t co un t y yo r k c i t y c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y , concept : persongradua ted f romun ivers i t y inv , concept person diane001 c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y , concept : persongraduatedschool inv , concept person diane001 concep t pe rson b i l l , concept : pe rsonborn inc i t y , c o n c e p t c i t y y o r k concep t pe rson b i l l , concept : personborn in loca t ion , c o n c e p t c i t y y o r k concep t pe rson b i l l , concept : persongraduatedf romunivers i ty , c o n c e p t u n i v e r s i t y c o l l e g e concep t pe rson b i l l , concept : persongraduatedschool , c o n c e p t u n i v e r s i t y c o l l e g e concep t pe rson b i l l , concept : persongraduatedf romunivers i ty , c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y concep t pe rson b i l l , concept : persongraduatedschool , c o n c e p t u n i v e r s i t y s t a t e u n i v e r s i t y concep t c i t y yo rk , concept : pe r sonbo rn inc i t y i nv , c o n c e p t p e r s o n b i l l concep t c i t y yo rk , concept : pe r sonbo rn inc i t y i nv , concept person diane001 c o n c e p t u n i v e r s i t y c o l l e g e , concept : persongradua ted f romun ivers i t y inv , concept person diane001 concept person diane001 , concept : pe rsonborn inc i t y , c o n c e p t c i t y y o r k

heading: For the PersonLeadsOrganization task
text: Query : ( c o n c e p t j o u r n a l i s t b i l l p l a n t e , concept : person leadsorgan izat ion , concept company cnn pbs )
Selected key edges : c o n c e p t j o u r n a l i s t b i l l p l a n t e , concept : worksfor , concep t te lev i s i onne twork cbs c o n c e p t j o u r n a l i s t b i l l p l a n t e , concept : agen tco l l abo ra tesw i thagen t inv , concep t te lev i s i onne twork cbs concep t te lev is ionne twork cbs , concept : works fo r inv , c o n c e p t j o u r n a l i s t w a l t e r c r o n k i t e
concep t te lev is ionne twork cbs , concept : agentco l labora teswi thagent , c o n c e p t j o u r n a l i s t w a l t e r c r o n k i t e concep t te lev is ionne twork cbs , concept : works fo r inv , concep t pe rsonus sco t t pe l l ey concep t te lev is ionne twork cbs , concept : works fo r inv , c o n c e p t a c t o r d a n i e l s c h o r r concep t te lev is ionne twork cbs , concept : works fo r inv , concept person edward r murrow concep t te lev is ionne twork cbs , concept : agentco l labora teswi thagent , concept person edward r murrow concep t te lev is ionne twork cbs , concept : works fo r inv , c o n c e p t j o u r n a l i s t b i l l p l a n t e concep t te lev is ionne twork cbs , concept : agentco l labora teswi thagent , c o n c e p t j o u r n a l i s t b i l l p l a n t e c o n c e p t j o u r n a l i s t w a l t e r c r o n k i t e , concept : worksfor , concep t te lev i s i onne twork cbs c o n c e p t j o u r n a l i s t w a l t e r c r o n k i t e , concept : agen tco l l abo ra tesw i thagen t inv , concep t te lev i s i onne twork cbs c o n c e p t j o u r n a l i s t w a l t e r c r o n k i t e , concept : worksfor , concep t nonp ro f i t o rgan i za t i on cbs even ing concep t pe rsonus sco t t pe l l ey , concept : worksfor , concep t te lev i s i onne twork cbs concep t pe rsonus sco t t pe l l ey , concept : person leadsorgan izat ion , concep t te lev i s i onne twork cbs concep t pe rsonus sco t t pe l l ey , concept : person leadsorgan izat ion , concept company cnn pbs concep t ac to r dan ie l scho r r , concept : worksfor , concep t te lev i s i onne twork cbs concep t ac to r dan ie l scho r r , concept : person leadsorgan izat ion , concep t te lev i s ionne twork cbs concep t ac to r dan ie l scho r r , concept : person leadsorgan izat ion , concept company cnn pbs concept person edward r murrow , concept : worksfor , concep t te lev i s i onne twork cbs concept person edward r murrow , concept : agen tco l l abo ra tesw i thagen t inv , concep t te lev i s i onne twork cbs concept person edward r murrow , concept : person leadsorgan izat ion , concep t te lev i s i onne twork cbs concept person edward r murrow , concept : person leadsorgan izat ion , concept company cnn pbs concep t te lev is ionne twork cbs , concept : o rgan i za t i onheadquar te red inc i t y , concep t c i t y new york concep t te lev is ionne twork cbs , concept : headquarteredin , concep t c i t y new york concep t te lev is ionne twork cbs , concept : agentco l labora teswi thagent , concept personeurope wi l l i am pa ley concep t te lev is ionne twork cbs , concept : topmemberoforganizat ion inv , concept personeurope wi l l i am pa ley concept company cnn pbs , concept : headquarteredin , concep t c i t y new york concept company cnn pbs , concept : personbe longs toorgan iza t ion inv , concept personeurope wi l l i am pa ley concep t nonpro f i t o rgan iza t i on cbs even ing , concept : works fo r inv , c o n c e p t j o u r n a l i s t w a l t e r c r o n k i t e concept c i t y new york , concept : o rgan i za t i onheadqua r t e red i nc i t y i nv , concep t te lev i s i onne twork cbs concept c i t y new york , concept : headquar tered in inv , concep t te lev i s i onne twork cbs concept c i t y new york , concept : headquar tered in inv , concept company cnn pbs concept personeurope wi l l iam paley , concept : agen tco l l abo ra tesw i thagen t inv , concep t te lev i s i onne twork cbs concept personeurope wi l l iam paley , concept : topmemberoforganizat ion , concep t te lev i s i onne twork cbs concept personeurope wi l l iam paley , concept : personbe longstoorgan izat ion , concept company cnn pbs concept personeurope wi l l iam paley , concept : person leadsorgan izat ion , concept company cnn pbs
For the OrganizationHiredPerson task
Query : ( concep t s ta teo rp rov ince a f te rnoon , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney )
Selected key edges : concep t s ta teo rp rov ince a f te rnoon , concept : atdate , c o n c e p t d a t e l i t e r a l n 2 0 0 7 concep t s ta teo rp rov ince a f te rnoon , concept : atdate , concept date n2003 concep t s ta teo rp rov ince a f te rnoon , concept : atdate , c o n c e p t d a t e l i t e r a l n 2 0 0 6 concep t da te l i t e ra l n2007 , concept : a tda te inv , concep t coun t r y un i t ed s ta tes concep t da te l i t e ra l n2007 , concept : a tda te inv , concept c i ty home concep t da te l i t e ra l n2007 , concept : a tda te inv , c o n c e p t c i t y s e r v i c e concep t da te l i t e ra l n2007 , concept : a tda te inv , c o n c e p t c o u n t r y l e f t p a r t i e s concept date n2003 , concept : a tda te inv , concep t coun t r y un i t ed s ta tes concept date n2003 , concept : a tda te inv , concept c i ty home concept date n2003 , concept : a tda te inv , c o n c e p t c i t y s e r v i c e concept date n2003 , concept : a tda te inv , c o n c e p t c o u n t r y l e f t p a r t i e s concep t da te l i t e ra l n2006 , concept : a tda te inv , concep t coun t r y un i t ed s ta tes concep t da te l i t e ra l n2006 , concept : a tda te inv , concept c i ty home concep t da te l i t e ra l n2006 , concept : a tda te inv , c o n c e p t c i t y s e r v i c e concep t da te l i t e ra l n2006 , concept : a tda te inv , c o n c e p t c o u n t r y l e f t p a r t i e s concep t coun t r y un i t ed s ta tes , concept : atdate , concept year n1992 concep t coun t r y un i t ed s ta tes , concept : atdate , concept year n1997 concep t coun t r y un i t ed s ta tes , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney concept c i ty home , concept : atdate , concept year n1992 concept c i ty home , concept : atdate , concept year n1997 concept c i ty home , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney c o n c e p t c i t y s e r v i c e , concept : atdate , concept year n1992 c o n c e p t c i t y s e r v i c e , concept : atdate , concept year n1997 c o n c e p t c i t y s e r v i c e , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney c o n c e p t c o u n t r y l e f t p a r t i e s , concept : works fo r inv , concept personmexico ryan whi tney c o n c e p t c o u n t r y l e f t p a r t i e s , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney concept year n1992 , concept : a tda te inv , concept governmentorganizat ion house concept year n1992 , concept : a tda te inv , concep t coun t r y un i t ed s ta tes concept year n1992 , concept : a tda te inv , concept c i ty home concept year n1992 , concept : a tda te inv , concept t radeunion congress concept year n1997 , concept : a tda te inv , concept governmentorganizat ion house concept year n1997 , concept : a tda te inv , concep t coun t r y un i t ed s ta tes concept year n1997 , concept : a tda te inv , concept c i ty home concept personmexico ryan whi tney , concept : worksfor , concept governmentorganizat ion house
concept personmexico ryan whi tney , concept : worksfor , concept t radeunion congress concept personmexico ryan whi tney , concept : worksfor , c o n c e p t c o u n t r y l e f t p a r t i e s concept governmentorganizat ion house , concept : personbe longs toorgan iza t ion inv , concept personus par ty concept governmentorganizat ion house , concept : works fo r inv , concept personmexico ryan whi tney concept governmentorganizat ion house , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney concept t radeunion congress , concept : o rgan iza t ionh i redperson , concept personus par ty concept t radeunion congress , concept : works fo r inv , concept personmexico ryan whi tney concept t radeunion congress , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney c o n c e p t c o u n t r y l e f t p a r t i e s , concept : o rgan iza t ionh i redperson , concept personus par ty

heading: For the AgentBelongsToOrganization task
text: Query : ( concept person mark001 , concept : agentbe longstoorgan iza t ion , c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d )
Selected key edges : concept person mark001 , concept : personbe longstoorgan izat ion , c o n c e p t s p o r t s t e a m s t a t e u n i v e r s i t y concept person mark001 , concept : agentco l labora teswi thagent , concept male wor ld concept person mark001 , concept : agen tco l l abo ra tesw i thagen t inv , concept male wor ld concept person mark001 , concept : personbe longstoorgan izat ion , c o n c e p t p o l i t i c a l p a r t y c o l l e g e concep t spo r t s t eam s ta te un i ve rs i t y , concept : personbe longs toorgan iza t ion inv , c o n c e p t p o l i t i c i a n j o b s concep t spo r t s t eam s ta te un i ve rs i t y , concept : personbe longs toorgan iza t ion inv , concept person mark001 concep t spo r t s t eam s ta te un i ve rs i t y , concept : personbe longs toorgan iza t ion inv , concept person greg001 concep t spo r t s t eam s ta te un i ve rs i t y , concept : personbe longs toorgan iza t ion inv , concept person michael002 concept male world , concept : agentco l labora teswi thagent , c o n c e p t p o l i t i c i a n j o b s concept male world , concept : agen tco l l abo ra tesw i thagen t inv , c o n c e p t p o l i t i c i a n j o b s concept male world , concept : agentco l labora teswi thagent , concept person mark001 concept male world , concept : agen tco l l abo ra tesw i thagen t inv , concept person mark001 concept male world , concept : agentco l labora teswi thagent , concept person greg001 concept male world , concept : agen tco l l abo ra tesw i thagen t inv , concept person greg001 concept male world , concept : agentcont ro ls , concept person greg001 concept male world , concept : agentco l labora teswi thagent , concept person michael002 concept male world , concept : agen tco l l abo ra tesw i thagen t inv , concept person michael002 c o n c e p t p o l i t i c a l p a r t y c o l l e g e , concept : personbe longs toorgan iza t ion inv , concept person mark001 c o n c e p t p o l i t i c a l p a r t y c o l l e g e , concept : personbe longs toorgan iza t ion inv , concept person greg001 c o n c e p t p o l i t i c a l p a r t y c o l l e g e , concept : personbe longs toorgan iza t ion inv , concept person michael002 c o n c e p t p o l i t i c i a n j o b s , concept : personbe longstoorgan izat ion , c o n c e p t s p o r t s t e a m s t a t e u n i v e r s i t y c o n c e p t p o l i t i c i a n j o b s , concept : agentco l labora teswi thagent , concept male wor ld
c o n c e p t p o l i t i c i a n j o b s , concept : agen tco l l abo ra tesw i thagen t inv , concept male wor ld c o n c e p t p o l i t i c i a n j o b s , concept : worksfor , c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d concept person greg001 , concept : personbe longstoorgan izat ion , c o n c e p t s p o r t s t e a m s t a t e u n i v e r s i t y concept person greg001 , concept : agentco l labora teswi thagent , concept male wor ld concept person greg001 , concept : agen tco l l abo ra tesw i thagen t inv , concept male wor ld concept person greg001 , concept : agen tcon t ro l s i nv , concept male wor ld concept person greg001 , concept : agentbe longstoorgan iza t ion , c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d concept person greg001 , concept : personbe longstoorgan izat ion , c o n c e p t p o l i t i c a l p a r t y c o l l e g e concept person greg001 , concept : agentbe longstoorgan iza t ion , c o n c e p t r e c o r d l a b e l f r i e n d s concept person michael002 , concept : personbe longstoorgan izat ion , c o n c e p t s p o r t s t e a m s t a t e u n i v e r s i t y concept person michael002 , concept : agentco l labora teswi thagent , concept male wor ld concept person michael002 , concept : agen tco l l abo ra tesw i thagen t inv , concept male wor ld concept person michael002 , concept : agentbe longstoorgan iza t ion , c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d concept person michael002 , concept : personbe longstoorgan izat ion , c o n c e p t p o l i t i c a l p a r t y c o l l e g e c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d , concept : works fo r inv , concept personmexico ryan whi tney c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d , concept : works fo r inv , c o n c e p t p o l i t i c i a n j o b s concep t reco rd l abe l f r i ends , concept : o rgan iza t ionh i redperson , concept personmexico ryan whi tney concept personmexico ryan whi tney , concept : worksfor , c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d concept personmexico ryan whi tney , concept : o rgan i za t i onh i redpe rson inv , c o n c e p t g e o p o l i t i c a l l o c a t i o n w o r l d concept personmexico ryan whi tney , concept : o rgan i za t i onh i redpe rson inv , c o n c e p t r e c o r d l a b e l f r i e n d s

heading: For the TeamPlaysInLeague task
text: Query : ( concept sportsteam maver icks , concept : teamplaysinleague , concept spor ts league nba )
Selected key edges : concept sportsteam maver icks , concept : teamplayssport , concep t spo r t baske tba l l concept sportsteam maver icks , concept : teamplaysagainstteam , concep t spo r t s team bos ton ce l t i cs concept sportsteam maver icks , concept : teamplaysagainst team inv , concep t spo r t s team bos ton ce l t i cs concept sportsteam maver icks , concept : teamplaysagainstteam , concept spor ts team spurs concept sportsteam maver icks , concept : teamplaysagainst team inv , concept spor ts team spurs concep t spo r t baske tba l l , concept : teamplaysspor t inv , concept spor ts team co l lege concep t spo r t baske tba l l , concept : teamplaysspor t inv , concep t spo r t s team marsha l l un i ve rs i t y concep t spor t s team bos ton ce l t i cs , concept : teamplaysinleague , concept spor ts league nba concept spor ts team spurs , concept : teamplaysinleague , concept spor ts league nba concept spor ts league nba , concept : agentcompeteswithagent , concept spor ts league nba
concept spor ts league nba , concept : agentcompeteswithagent inv , concept spor ts league nba concept spor ts team col lege , concept : teamplaysinleague , c o n c e p t s p o r t s l e a g u e i n t e r n a t i o n a l

Review summaries:
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.