Inductive Relation Prediction Using Analogy Subgraph Embeddings
Authors: Jiarui Jin
Yangkun Wang
Kounianhua Du
Weinan Zhang
Zheng Zhang
David Wipf
Yong Yu
Quan Gan
Venue: ICLR 2022 Poster (2022)
Keywords: Link Prediction
Relation Modelling
Heterogeneous Graphs
Knowledge Graphs

Abstract: Prevailing methods for relation prediction in heterogeneous graphs aim at learning latent representations (i.e., embeddings) of observed nodes and relations, and thus are limited to the transductive setting where the relation types must be known during training.  Here,  we propose ANalogy  SubGraphEmbeddingLearning (GraphANGEL), a novel relation prediction framework that predicts relations5between each node pair based on the subgraphs containing the pair, as well as other  (analogy)  subgraphs with the same graph patterns.   Each graph pattern explicitly represents a specific logical rule, which contributes to an inductive bias that facilitates generalization to unseen relations and leads to more explainable predictive models. Moreover, our method also removes the limited neighborhood constraint of graph neural networks. Our model consistently outperforms existing models on heterogeneous graph based recommendation as well as knowledge graph completion.  We also empirically demonstrate our model’s capability in generalizing to new relations while producing explainable heat maps of attention scores across the discovered logic.

Published as a conference paper at ICLR 2022
INDUCTIVE RELATION PREDICTION USING ANALOGY SUBGRAPH EMBEDDINGS
Jiarui Jin Yangkun Wang Kounianhua Du't, Weinan Zhang Quan Gan Zheng Zhang?, Yong Yu', David Wipf 'Shanghai Jiao Tong University, AAmazon
(jinjiarui9) 97, espylacopa, 774581965, wnzhang, yyu) jtu edu. cn, (quagan, zhaz, daviwipf) @amazon. com
ABSTRACT
Prevailing methods for relation prediction in heterogeneous graphs including knowledge graphs aim at learning the latent representations (i.e., embeddings) of observed nodes and relations, and are thus limited to the transductive setting where the relation types must be known during training. In this paper, we pro- pose ANalogy SubGraph Embedding Learning (GraphANGEL)), novel relation prediction framework that predicts relations between each node pair by checking whether the subgraphs containing the pair are similar to other subgraphs containing the considered relation. Each graph pattern explicitly represents a specific logical rule, which contributes to an inductive bias that facilitates generalization to un- seen relation types and leads to more explainable predictive models. Our model consistently outperforms existing models in terms of heterogeneous graph based recommendation well as knowledge graph completion. We also empirically demonstrate the capability of our model in generalizing to new relation types while producing explainable heat maps of attention scores across the discovered logics.
INTRODUCTION
Relation modeling aims to learn the relations between nodes, leading to advances in a wide range of applications, e.g., recommender systems (Koren al., 2009), knowledge graphs (Bordes et al., 2013), and biology (Yasunaga et al., 2021). 1). As most relational data in the real world is hetero- geneous, a principal way is to organize it into heterogeneous graph. The dominant paradigms for relation prediction can be categorized into matrix factorization techniques (Nickel et al., 2011; 2012), statistical relational learning approaches (Richardson & Domingos, 2006; Singla & Domingos, 2005), and neural-em -ee-ledmeeeedbbbeeeeeeeee based methods (Bordes et al., 2013; Dettmers et al., 2018). Among these, neural-embedding based methods which learn to encode relational information using low- dimensional representations of nodes and relations, have shown good scalability (Bordes al., 2013) and inductive learning capability (Battaglia et al., 2018) in terms of validating unseen nodes.
Results of such methods show that graph neural networks (GNNs) are able condense the neigh- borhood connectivity pattern of each node into a node-specific low-dimensional embedding and successfully exploit such local connectivity patterns and homophily. Recent advances further reveal the logical expressiveness of GNNs (Barceló et al., 2019) and support their inductive ability to generalize to unseen nodes (Teru et al., 2020; Zhang & Chen, 2019).
In contrast, a limited study has been conducted (Yang et al., 2014) on the inductive learning capability for unseen relation types. Such inductive ability, if successfully exploited, can directly improve logical expressiveness of GNNs and enable them to effectively capture the underlying logical semantics (e.g., logical rules). Note that this is more challenging than unseen nodes, since it usually hard define the "neighborhood" of a relation type topologically.
In this paper, we propose Nalogy SubGraph Embedding Learning (GraphANGEL.), a new relation prediction paradigm that holds a strong inductive bias to generalize to unseen relation types. Given pair of nodes to predict the existence of a specific relation between them, the core idea is to extract
Work done during internship at Amazon Web Services Shanghai Al Lab. Weinan Zhang and Quan Gan the corresponding authors.

---

Published as a conference paper at ICLR 2022
some analogy subgraphs containing the pair, and compare them against other subgraphs sharing similar shapes. We call these shapes graph patterns.
Taking Figure
example, the task is to predict whether Person E lives in London. We construct three patterns involving the relation Live. The first is targer pattern containing the source and target nodes, i.e., Person and London, for which relation live. The second is supporting pattern that includes live as evidence supporting the existence. The third is refuting pattern that does not include live as baseline for comparison. If an edge does exist between the two nodes, the subgraphs matching the target pattern should be more similar to those matching supporting patterns than the refuting patterns. Following the above intuition, we find set of subgraphs that match each of the patterns. Then we compare the first set against the set matching supporting patterns, and also against the set matching refuting patterns, using a neural network. As shown in the bottom part of the figure, the subgraphs in the second set share the higher similarity with the one the first set, so the prediction result this case that there exists a live.
to predict the existence of the
Given triplet (s, v,,4) f), GraphANGEL consists of the following stages: (1) determining target patterns from s, as well as supporting and re- futing patterns from r, (2) retrieving subgraphs matching each pattern (3) computing the rep- resentations of each set and then the similarity between the subgraph set matching target pat- tern and the set matching supporting/refuting patterns, and the final prediction based on the similarities. For the first stage, our architecture design only involves the graph patterns in pair, 3-cycle, and 4-cycle shapes, which is efficient to match and already shows good results. For the second stage, we introduce efficient searching and sampling techniques to find the subgraphs matching the patterns. We use a GNN with at- tention in the third stage to combine the sets of subgraphs as well their node features. The attention module can simultaneously produce an explainable heat map across the discovered patterns. Notably, none of the above stages requires explicitly learning representation of r, the relation are predicting, thus, GraphANGEL naturally generalizes to modeling unseen relation types.
Subgraphs of Supporting Pattern
Subgraphis of Returing
Subgraphi() Target Patten
Figure 1: An illustrative example of motivation.
We benchmark GraphANGEL on heterogeneous graph based recommendation and knowledge graph completion tasks with the state-of the-trrr methods. For the evaluation of inductive capabilities, we construct several new inductive benchmarks by either removing or adding relations from knowledge graph datasets. Extensive experimental comparisons on these benchmarks exhibit the superiority of our method under both transductive and inductive settings.
2 BRIDGING LOGICAL EXPRESSIONS AND GRAPH PATTERNS
We begin with bridging logical expressions and graph patterns based on two intuitions/assumpiion:::
A relation can often be inferred from other relations with a combination of simple logical rules
that do not involve too many nodes.
One can predict relation existence by finding whether the subgraphs containing the pair are similar to the subgraphs containing an edge with the same relation.
Take Figure as an example where we wish to predict whether Person lives in London. An example of the first intuition goes as follows: if Person E watches the soccer matches with club Arsenal, which based in London, then Person E may also live in London. However, such logical rules (so called chain-like logic rules in (Yang et al., 2017)) may not always hold, requiring probabilistic inference. For instance, Person G watches the matches with FC Barce lona, which is Based in Barcelona, but he does not live in the same city. To make more accurate predictions, we need to combine other possible logical rules, such as "Friends often live in the same city" in this case, Person E. and Person H are friends, and Person и 1 i vees
2

---

Published as a conference paper at ICLR 2022
g
(a)
(b)
(C)
Hh...
I
Supporting Pattern
S
Edga(æ, (2)e
Refuting Pattern
Target Pattern
I
Epd
Ilp
I1
Source(2) (2) A Target(y) Eáge( x [d)o(=.))
Edge, y) A Edgo(s; =)
Edge, v) A Edge(z, s)
A (d)
EAge(=.
Figure Illustration of GraphANGEL's relation prediction workflow, where different edge colors in the graph G represent different relation types, and dashed edges in & represent the triplet (s, t) we wish to predict. The left box shows the patterns considered in our implementation, where black edges mean matching edges irrespective of relation types. The bottom boxes show the logical function of the three patterns.
in London (some of them construct certain patterns are called tree-like logic rules (Yang & Song, 2019) or graph-like rules (Shi et al., 2020)).
The second intuition tells us that we can predict whether Person lives in London by checking if the subgraphs containing the pair (Person E, London) (named target subgraphs, e.g. Person Arsenal- London) are similar to the subgraphs containing a 1 live relation (named supporting subgraphs, e.g. Person I Chelsea London). Similarity computation is done by neural network. To determine whether the two sets of subgraphs are similar, we additionally compare the target subgraphs against another set of subgraphs that do not contain the relation (named refuting subgraphs, e.g. Person E Person G Barce mareelll ona) as a haseline. A variety of options exist for selecting the refuting subgraphs, ranging from selecting those having the same topology regardless of the actual relation types, to those having both the same shape and relation types.
In addition, we do not include the edge of live in the supporting subgraphs to avoid information leakage. We also require the supporting subgraphs and refuting subgraphs to have the same shape as that of the target subgraphs in order to make similarity computation focus more on the node features and relation types rather than the topology, and that is why we call both supporting subgraphs and refuting subgraphs analogy subgraphs. This enables us to predict ivve relation with the pipeline above without learning explicit embedding for 1 vive relation, unlike prior works. The reason is that the information of live relation can be implicitly expressed by the other relations found the supporting and refuting subgraphs, e.g. live can be expressed by watch ch and based. This serves as the basis for our model's generalizability to relations that have no occurrence in the training set.
We can describe what kind of subgraphs we are looking for in the above example with logical expressions. The target subgraphs above will have the logical expression Source(x) A Target (y) A Edge(æ, 2) A Edge(2, y), where Source (z) means if node is the source node s, Target(y) means node is the target node f, and Edge(x, 2) means there exists an edge regardless of relation type between and Our task is to determine whether an edge of relation type exists between and f. The supporting subgraphs will have Edge(r, z) A Edge(z, y) A Edge, (z, y), meaning that the subgraph can be any 3-cycle except that there must be edge with relation type r. The refuting subgraphs will have Edge(I, 2) A Edge(2, y) A -Edge, (Ir, y). meaning that it can be any 2-path except that the starting node and ending node must not have an edge with relation in between. This leads to the concept of graph patterns, defined as follows:
Definition 1 (Graph Pattern). A graph pattern is a logical function that takes in a subgraph as input and returns a boolean value, consisting of logical operators (-, V) as well as indicator operators determined by the existence of nodes and edges, the latter includes:
(z) and Target(x). returning true iff is the source node and target node, respectively. Edge(x, y), returning true iff there exists an edge between node x and y. Edge,((z y), returning true iff there exists an edge of relation r between node x and y.
We call subgraph S matches graph pattern II if true is returned when S is applied II. Such operation is already well supported in graph databases (Francis et al., 201 8), and in the following sections we give more efficient algorithms that perform matching with simple patterns.
3

---

Published as a conference paper at ICLR 2022
Table 1: A summary of how to construct target, supporting, and refuting patterss.
Base Pattern p 1
Target Pattern II
Supporting Pattern 1 Edge, (z, A IIp
Refuting Pattern 1I -Edge, (z, y) 1
(ource( (aargetly) AI
3 MODELING RELATION WITH ANALOGY SUBGRAPH EMBEDDINGS
For each graph G (V,ERR) where V denotes node set. & denotes edge set and R is relation set, as Figure shows, we outline how GraphANGEL works for each triplet (s, r, t) to predict the existence for the edge of type r connecting source node and target node as follows. (a) We start by determining P target patterns denoted as IT;.... .... ITp. For each I we also determine its corresponding supporting pattern I and refuting pattern 1 (b) We then sample a set of K' target subgraphs ( ) matching ITp Q supporting subgraphs ( matching i and Q refuting subgraphs {S (5= matching IT . (c) For each pattern Np, we next compute the representation of each sampled subgraph and obtain the set of target subgraph embeddings (e7, k= 1Q
supporting subgraph embeddings ) and refuting subgraph embeddings {Epa)g=1 (d) We P.K (pp, -=1,A=1 and the set (e p p=1.g=1 as well
finally compute a similarity score between the set ) P.K
P.Q
1.0=1 pm to get the relation prediction result. as (e and (Ep.g) pm
We summarize the notations in Appendix A1, show the training algorithm in Algorithm describe the details in the following subsections, and provide the overall time complexity in Appendix A3.
Pattern Construction. During train- ing, we set for each II, the target pat- tern I1, the supporting pattern I1 and the refuting pattern II using Table 1. Since pattern matching is NP-complete like subgraph matching (Lewis, 1983), we first designate be- fore training a set of patterns [1I, | whose pattern matching can be com- puted in manageable time. In practical, we use Pairs, 3-cycles, and 4-cycles.
Algorithm 1: GraphANGEL
Input: Graph G. Patterns II, for each tuple (8, r. 1) do for each pattern IIp do
Ilp.
Construct IT; 1 ITp
Retrieve K subgraphs {S p. k== matching IT;
K
Retrieve Q subgraphs
{S p.g p.gla=1 matching I
12
Retrieve Q subgraphs (Spp) matching nT
Compute c. 2.g0 Pp.g via Eq. (1).
end Compute s+, via Eq. (2). Update parameters according Eq. (3).
Subgraph Retrieval. Although gen- eral graph pattern matching is sup- ported in graph databases (Francis et al., 2018), more efficient solutions exist for simpler graph patterns, especially when we only consider pairs, 3-cycle and 4-cycle shapes. Searching and retrieving the subgraphs matching patterns in Pair shape is trivial since reduces to finding edges with given relation, so the following discussion only involves 3-cycle and 4-cycle patterns. We coe-compute all subgraphs matching 3-cycle patterns and uniformly sample a number of subgraphs matching 4-cycle patterns, and store them into a buffer by our algorithms, summarized as follows, with pseudocode, correctness proofs and complexity analysis in Appendix A2.
end
3-cycles. We first partition the node set by the node degrees into two sets V V1 UV2. VI contains the nodes whose degrees are less than {| and V22 contains the rest. For each u, v, w V1, check if they form a 3-cycle. Then, for each u E V2. we enumerate all pairs of its neighbors and see if they are connected. The complexity to find all the subgraphs is O( 4-cycles. For each node, we find all 2-paths (u, U, w)) whose starting node u has the largest degree, i.e., d, max (dw, d,, d. and then store them in Tu.. Each pair of 2-paths that shares the same ending node forms a 4-cycle. this regard, 4-cycles can be uniformly sampled by first sampling u, with the probability in proportion to |Tam. |T... - 11. and then choosing two distinct nodes v. from Taw- The complexity to sample n4 ny-cycle subgraphs is (maxx(44 (1a-x(e4eeycee: [8] ))-
Then, we perform pattern matching for 3-cycles and 4-cycles for each subgraph as follows.
Target patterns. Matching 3-cycle target patterns reduces to finding common neighbors of and t, which takes O(d, + d,) time where d, and d, are degrees of s and t. Matching 4-cycle target pattern reduces to finding whether the neighbors of s and are connected, taking O(d,d.) time.
4

---

Published as a conference paper at ICLR 2022
Table 2: Patterns 1p considered in our experiments.
Task
Pair
3-cycle (with type)
4-cycle (with type)
Knowledge Graph Completion
true
Edgela, Edge(2.9]
Edge(z, a] (dge(z,w) w) Edge
Heterogenneous Graph Recommendation
Edgo, (2,3)
Bdg Bdge, (2, w. BAge,
(wr..(ww.))
Supporting patterns. Matching supporting patterns reduces finding subgraph containing an edge of type r in the precomputed result. One can efficiently retrieve with a precomputed inverted map with relation r as key and the actual subgraphs containing it as value.
Refuting patterns. Matching refuting patterns reduces to random walks, followed by checking whether the starting node and the ending node has an edge of type
We further design a series of novel uniform sampling algorithms such that the time complexity
of sampling n refuting cases of II I13-cycta or Il4-cycla reduces to O(V)+ + |l + +n). See detailed descriptions in Appendix A2.
Representation Computation. We apply a neural network (()) over each subgraph S7. Sp. and Sp.g to obtain graph-level representations p. ep Pp.9 following
ei. = = (Sp.k) ep. = (Sp.) pp.q (Sp.)
In the implementation, we adopt single layer R-GCN (Schlichtkrull al., 2018) followed by any readout function, e.g., Mean(-), Max(-) Φ(-). We also empirically study the effect of using other GNNs with different number of propagation layers as (.)) in Appendix A6.5.
Similarity Computation. We deploy a neural network (-) to measure the similarity s+ between the set of subgraphs matching ... I and the set of subgraphs matching ....... II and the similarity& s between the set of subgraphs matching ..,,..., , IIp and the set of subgraphs matching II Hpp which can be formulated as
8 = V (1e = =1, P: = 1,... K}, (ep P 1,..., piq .).....,))). v ((e p I..... P, k- I...., K}. tep. :p 1...., Pig L....,...1. Q1)
There many choices of measuring the similarity between two sets. In the implementation, adopt a co-attention mechanism (Lu et al., 2016) as (.),,, because even within the same pattern, the subgraphs having similar node features more important than others.
We put the concrete formulation of ((-) and (-) in the Appendix A3.3 and A3.4.
Loss Function. For each tuple (s r, t), we have the binary label y in the training dataset D to denote the relation existence. We here train the model by logistic loss with negative sampling:
D= Σ
(y logg ú (1 - y) log(1 -)))
(arret)D
where ý the final prediction calculated with normalized similarity as 9 -8
Inference. We perform pattern matching find the target, supporting, and refuting subgraphs on the testing graph, and compute the prediction score ÿ exactly as what we do in training. We predict that an edge exists if 9 larger than a threshold (as hyper-parameter, 0.5 in our implementation).
There are two main limitations of GraphANGEL. The first one is that GraphANGEL would not work reliably the assumptions (intuitions) in Section are violated. Examples include when node and t are disconnected or topologically far away when (s,r,t) t) is removed, so that one may not be able to find 3-cycle or 4-cycle target subgraphs. The prediction in this case can only rely on Pair patterns, i.e.. comparing if the source-target pair is similar to the incident nodes of edges with relation r or not. The second one that current online subgraph sampling algorithms are slow. To make sampling efficient, the subgraph retrieval stage requires finding and storing all 3-cycles and 4-cycles (See Appendix A3.1 1 for the space complexity analysis). For static graphs, is one-time preprocessing step. although the results can be stored on external storage. We also provide the incremental searching and retrieving algorithms to address the dynamic graphs in the real-world scenario in Appendix A3.2. See further discussions on these limitations in Appendix 14.1.
Limitations.
5

---

Published as a conference paper at ICLR 2022
Table 3: Result comparisons with baselines heterogeneous graph recommendation task.
Models
LasPM
Yelp
Amazion
Douhan Book
AUC
ACC
F1
AUC
ACC
F1
AUC
ACC
F1
AUC
ACC
F1
HeGGNN
0.7936
0.7258
0.7177
0.9083
0.8297
0.8205
0.7744
0.7108
0.7109
0.8737
0.7912
0.7915
HAN
0.8915
0,8337
0.8296
0.9156
0.8488
0,8426
0.8487
0.7682
0.7572
0.9244
018501
0.8458
TAHIN
0.8910
0.8463
0.8337
0.9067
0.8490
0.8535
0,7718
0,7644
0.9253
0.8497
0,8373
HGT
0.8394
0.7939
0.7882
0.9006
0.8375
0.8334
0.7125
0.6482
0.6296
0,9132
0.8364
0.8222
R-GON
0.8526
0.8393
0.8341
0.9098
0.8427
0.8323
0,8130
0.7408
0.7366
0.9203
0.8413
0.8271
GraphNGEE
0.8934
0,8519
0.8465
0.9167
0.8498
0.8514
0.8601
0.7746
0.7746
0.9256
0.8512
0.8479
GraphANGEL, sycle
0.8961
0.8514
0.8467
0.9201
0.8506
0.8521
0,8609
0,7752
0.7716
0.9242
0,8502
0.8378
GraphANGEL
0.8979
0.8524
0.8469
0.9231
0.8512
0.8533
0
0.7790
0.7753
0.9311
0,8601
0.8543
GrapbANGEL.
0.9001
0.8611
0.8589
0.9337
0.8701
0.8577
0,8700
0.7810
0.7813
0,9410
0,8640
0.8591
4 EXPERIMENT
4.1 EXPERIMENT SETUP AND COMPARED ALGORITTMS
Recommendation on Heterogeneous Graph. We evaluate our model on four heterogeneous graph benchmark datasets in various fields: LastFM (Hu al., 2018 Yelp (Hu et al., 2018b), Amazon (Ni et al., 2019), and Douban Book (Zheng et al., 2017). The baselines we compare against are: HetGNN (Zhang et al., 2019a), HAN (Wang et al., 2019b), TAHIN (Bi et al., 2020), HGT (Hu et al., 2020), and R-GCN (Schlichtkrull et al., 2018). As the recommendation task can naturally be regarded as the relation predictions between each user and item pair, for each triplet, we formulate the task as a binary classification task. We split each dataset into 60%, 20%, and 20% for training, validation and test sets, respectively. Following the setting of (Zhang et al., 2019a), we generate an equal number of negative triplets with the same relation type in the test set, and report Area Under ROC Curve (AUC), Accuracy (ACC), and Fl score. More details of the datasets and experimental configurations as well as the implementation details for baselines are reported in Appendix A5.
Knowledge Graph Completion. We compare different methods on two benchmark datasets: FB15k- 237 (Toutanova & Chen, 2015) and WNI8RR (Dettmers al., 2018), which are constructed from Freebase (Bollacker et al., 2008) and WordNet (Miller, 1995), respectively. The baselines we compare against are: MI.N (Singla & Domingos, 2005), TransE (Bordes et al., 2013), ConvE (Dettmers et al., 2018), ComplEx (Trouillon et al., 201 6), PLoiicNet (Qu & Tang, 2019), RotatE (Sun et al., 2019a), RNNLogic (Qu et al., 2020), ComplEx-N3 (Lacroix et al., 2018), GralL (Teru et al., 2020) and QuatE (Zhang et al., 2019b). For each triplet, we mask the source or target node, and let each method predict the masked node. We use the filtered setting during evaluation on the standard training-vale validdttonott split, randomly break ties for triplets with the same score (Sun et al., 2019b) and report Mean Rank (MR), Mean Reciprocal Rank (MRR), and Hit@ K (K=1,3,10).
In each task, implement GraphANGEL we proposed in Section 3. Concretely, we imply GraphANGEL with ΠI upon the logical patterns shown in Table 2. For further investigations on the influence of different graph patterns, here introduce GraphANGELa- cyclee variant of GraphANGEL without using patterns in 3-cycle shapes; and GraphANGELa cycle, another variant without using patterns in 4-cycle shapes. For recommendation tasks on heterogeneous graphs, since the number of edge types is usually small, we can enumerate all the relation type combination in each pattern. This allows us to make the pattern II, specific to relation types. We denote this variant as GraphANGEL*. As the main advantage of our model is that it can generalize to relation types unseen during training without fine-tuning, we both evaluate the overall performance of GraphANGEI in standard relation prediction tasks and its generalizability to unseen relation types against other -tate-of-in thet methods. We exam the robustness of GraphANGEL by adding the Gaussian noise into the heterogeneous graphs and report the results in Appendix A6.5, We also compare the training and inference time of GraphANGEL against baseline models and report results in Appendix A6.7.
4.2 RESULT ANALYSIS OF STANDARD TASKS
Heterogeneous Graph Based Recommendation. In recommendation scenarios, edges between user and item nodes are generally more likely to exist if they share neighboring users or items. In other words, users close in the graph may share similar interests and items close usually share similar attributes. Table 3 summarizes the performances of GraphANGEL and baselines on four different kinds of recommendation tasks. We observe that GraphANGEL significantly outperforms the baselines across all datasets in terms of AUC, ACC, and Fl metrics. Almost all prevailing baseline methods on heterogeneous graph are based sampling through metapath. One explanation is that

---

Published as a conference paper at ICLR 2022
Table 4: Result comparisons with baselines knowledge graph completion task.
FB F51-2233
WN18RR
Models
MR
MRR
Hit@!
Hit@3
Hit 10
MR
MRR
Hit@!
Hir@3
Hit@
pLogicNet
173
0.332
0.237
0.367
0.524
3408
0.441
0.398
0.446
0.537
TransE
181
0.326
0.229
0.363
0,521
3410
0.223
0.235
0.401
0.531
ConvE
244
0.325
0.237
0.356
0.501
4187
0.430
0.400
0.440
0.520
ComplEx
339
0.247
0.158
0.275
0.428
5261
0.440
0,410
0,460
0.510
MI.N
1980
0.098
0.067
0.103
0.160
115599
0.259
0.191
0.322
0.361
RotatE
177
0.338
0.241
0.375
0.533
3340
0,476
0,428
0.492
0.571
RNNLogiC
232
0.344
0.252
0,380
0,530
4615
0.483
0.446
0.497
0.558
ComplEx-N3
159
0.370
0.272
0.400
0.561
3452
0.491
0.440
0.500
0.581
GralL.
205
0.322
0.223
0.361
0.520
35339
0.401
0.352
0.438
0.501
QuatE
87
0.348
0.248
0.382
0,550
2314
0.488
0.438
0.508
0.582
GraphANGEL,
1.99
0.366
0.270
0.398
0,560
2919
0.492
0.463
0.497
0.590
GraphANGEL
165
0.351
0.239
0.381
0.548
2914
0.493
0.465
0.502
0.587
GraphANGEL
151
0.374
0.275
0.408
0.564
2834
0,504
0.470
0.515
0.598
43
20.003
40.002
20.004
10.004
#25
20.003
20.002
20,004
20.004
given a specific pattern, these metapaths can be roughly regarded as target patterns, but without constructing supporting and refuting patterns in Table 1.
Knowledge Graph Completion. In knowledge graphs, the connection between two nodes is de- termined by both logic and node attributes. Table 4 summarizes all experimental results. As can be seen, GraphANGELL outperforms all baselines across all datasets. One explanation is that most knowledge graph embedding techniques focus on mining the hidden information in each tuple, which is similar to only considering the patterns in Pair shapes in Table 1. However, other patterns contain information involving multiple relations, which enables to model the logics.
In order to better illustrate our performance of these relations with few occurrences in the training set, we solely report the results of testing each model the 20% relations with few occurrence in Table A4 (see Appendix A6.1 for details). From the comparison between Tables 4 and A4, we can observe that with few shots of relations, GraphANGEL can have better generalization ability. One reason is that embeddings of the relations with few occurrences cannot be trained with plenty of data samples, resulting in low expressive power of the relations. contrast, GraphANGEL does not learn the embeddings directly, but learns to represent the relations of the related logics. However, it is still more challenging to model these relations that lead to a drop in performance.
Amazon
Douban Book
Amazon
Douban Book
0.00
3.57
0,0
0.00
1.54
0.72
0.02
0.3
0.07
2.50
6.77
335
0.72
6.05
0.900
1:90
0.75
0.04
1:0
634
3.2
0.2
0,00
6.00
0.81
Cul2
5.00
8.00
Target Subgraphs
Number Target Subgraphs X
Number Analogy Subgraphs
Number Anelogy Subgraphs Q
Figure 3: Performance change of GraphANGEL with different number of subgraphs in terms of ACC and AUC.
4.3 EFFECT OF DIFFERENT PATTERNS
We systematically investigate the effect of three shapes of patterns used in GraphANGEL. For each dataset, evaluate the effect of the patterns in 3-cycle and 4-cyele shapes by the performance of GraphANGELs
and GraphANGEL4 different composition logical rules, as shown Table 1, patterns in Pair shape are the most general but include the least structure information, while those in 4-cycle shape are rich in the structure but less common. Hence, these patterns have their unique power in representing logics. Although it is hard to determine whether 3-cycle or 4-cycle shaped patterns is more powerful, as shown in Tables 3, 4 and A4, GraphANGEL with patterns all shapes achieves the best performance. Besides the pattern type, we also investigate how the number of sampled subgraphs affects the performance. Taking Amazon and Douban Book datasets as examples, we show the performance of GraphANGEL under different K and Q in terms of ACC and AUC in Figure 3. One explanation is that the subgraphs following target patterns are constricted within the neighborhood of source and target nodes, the number of which is much smaller than subgraphs following supporting and refuting patterns.
Since different shapes of patterns represent
7

---

Published as a conference paper at ICLR 2022
Table 5: Result comparisons with baselines generalization setting by randomly removing 20% relations. See Appendix A6.2 for full version and Appendix A6,2 for results of dropping 5%, 10%, 15% The numbers in brackets show the descent degree.
Models
FB F51--333
WNISRR
Hit
Hir@3
Hir@
Hir@1 1
Hit 3
Hit 10
PLogicNee'
0.112(52. 79..2.77. L)
0.17%))1.2%.L)
0,257(51.08) ()
0.141(6.66%L)
0.222/50.255 ()
0.267(50.3%.)
TransE"
(.101(55.9%..
0.246652.8% 0.163(55.1%L)
0.072(46.7%L)
0.200X50.1%4 19k_))
0.260(5100%.)
ConvE"
0. 0.104(56. 19.1)
0,247(50.7%. (.108()0.0%.)
1)
0.201(49.89) ()
0.223(49. 33.
0.268(48.55
ComplEx*
0.078(50.699.)
0.142(48.4%.)
0.226(47.2%% 2).
0.214(4.8%%)
0.236(48.7%)
0.267(47.6%))
MLN'
0,031(53.7%
0.049)52.4%.)
0.070(56.3%|]
0.092(51.8%
0.154(52.2%:.
0.178(50.7%]]
RotatE"
0.121(49.8%..)
0.187(50.1%%)
0.271(49.1%LL
0.238(44.3%L)
0.260(47.1%.J)
0.296(48.2%
RNNLogic"
0.124:50.7% 1)
0.240154.6% 0.172(5..7%L)
0.260X47.6%8 0.244(5.22%L)
0.281(49.7%.]
ComplEx-N3"
0.142(47.2%%_)
(2.66(4966%L))
0,289(48.5%
0.269(46.2%k.) 0.250(43.2%L.
0.311(46.4%%_
GralL*
0.125/43.9%_. L)
(185(48.8%LL)
0,263(49.4%) L)
0.222(49.3%8 0.19((44.7%L)
0.267(46.8%.L)
QuatE"
0.127(48.7%%J)
0.190(00.3%L)
0.282(48.7%..)
(.24((33.9%.L
0,255(49.895
0. (.300(47)8)))
GraphANGEL
0.168(37.6%%)
0.333(40.5% 0.230(42.25L)
0.277(40.2% 2%)
0.291
0.329(44.3%0)
GriphANGELA
0.147(38.7%..)
(222(41179%-)
0,328(40.28) L)
0.278(40. 29%
0.291 1%
0. 0.326(44.4%.)
GraphANGEL
0.173(37.2%.)
0.238(41.5%
0.337(40.1% J)
0.284(39.5%
0.2994118%
0.334(44.1%)
4.4 RESULT ANALYSIS OF GENERALIZATION STUDY
We further evaluate these models in a scenario where generalizing from existing relations to unseen relations is required. Concretely, we use the same datasets with knowledge graph completion and randomly split R into two partitions Reeen and Runseen Each model is trained and validated only with the relations in Reeen During testing, the training and validation triplets in Rumeeen are added back to the original graph. We report results test triples with relations in Runseon only.
We cannot directly use the baselines above for unseen re- lations since those relation embeddings are never trained. Therefore, we combine them with EmbedRule, which es- timates the relation embedding by finding number of most common relation sequences that cooccur with the un- seen relation, and composing those embeddings thereafter (Yang et al., 2014). We superscript the name with an as- terisk for models enhanced by EmbedRule (e.g. TransE*),
0.40
0.35
pLogichet
0.30
TransE"
Hltg3
ConvE
0.25
ComplEx
RotatE
RNNiogicc
Results in Table illustrate that our model is significantly less affected than other models when we drop 20% rela- tions from the training and validation sets. We additionally report the results of dropping or adding 5% 10%, 15% relations in Appendix A6.2, These results on FB 15k-237 are summarized in Figure 4, where we see that our model obtains the better generalization ability.
ComplEx-N3"
0.15
GraphANGEL
0%
10%
15%
20%
Dropping Percentage of Relations in Training
Figure Illustrations generalization abil- ity for GraphANGEL against baselines.
4.5 RESULT ANALYSIS OF EXPLAINABLE ATTENTION MAP
Besides the performance, we further show that our model can produce explainable heat maps of attention scores across the discovered logic. We here provide an illustration on the recommendation task based on Douban Book graph, where we are required to predict the relation existence be- tween each user and book pair. In Douban Book, define the graph patterns based on the node types, such as 4-cycle shaped patterns: User Book Author Book denoted as (b, a), User Book Year - Book denoted as (b, y). and User User User Book denoted as (u, u). In Figure 5, the rows represent the supporting subgraphs while the columns represent the target subgraphs. Each cell represents the similarity between a target subgraph (at the top) and a supporting subgraph (at the bottom). The color of each cell shows the attention weight for corre- sponding pair of supporting and target subgraphs. We can observe that the deep color of the cell located at target and supporting subgraphs following (b, a) patterns, which indicates that the logic User A Book A Author A Book + User A Book has high confidence and can be strong evidence to support the relation prediction.
+
4'
%
(h.
(h.c)
(b.n)
(b.4)
(0.0)
(b,))
(..0
(..)
(..
60.30
(u 90
6 m
04 40
tu
(u.10
00.30
00.30
(4,
(h.n)
(b.4)
(6.0)
(h,y
(b,3
(sLu
(uLa)
(b.4)
(b.4)
(b.0)
(h.a)
(.,y
(b.y)
6x
(b.0)
(b.n)
(b.0)
(h.4)
02,9
(0.9)
(1.1)
(v.0)
(u.00
(u.30
(n.n)
(v.0)
Figure 5: Illustrations of generated heat map of attention scores. See Appendix A6.3 for the full version with subgraph structure.
8

---

Published as a conference paper at ICLR 2022
5 RELATED WORK
Heterogeneous graphs such knowledge graphs (Bordes et al., 2013; Schlichtkrull et al., 2018) and social networks (Zhang et al., 2019a; Jin et al., 2020) that encode facts about the world surrounding us, have motivated work on automatically predicting new statements based on known ones. Roughly speaking. existing approaches can be summarized into three main branches, namely matrix factoriza- tion techniques (Nickel et al., 201 2012), statistical relational learning approaches (Richardson & Domingos, 2006; Singla & Domingos, 2005), and reural-embedddingbaaee 2013; Dettmers et al., 2018). Our work focuses on the study of souurallembedding-bbee bbaedd models as they embed nodes and relations into wwwdimensioonal spaces (Bordes et al., 2013; Schlichtkrull et al., 2018; Trouillon al., 2016; Yan et al., 2019; Teru et al., 2020), showing good scalability and strong generalization ability. One dominant paradigm (Ji et al., 2015; Lin et al., 2015) in this branch constructed based on translation (Bordes et al., 2013) or rotation (Sun et al., 2019a) assumptions. The key idea behind this kind of models is that for a positive instance, the source node should be as close as possible to the target node through the relation, serving as a translation or rotation.
methods (Bordes et al.,
Although there are multiple successful stories in this line of works, these models are all trained on individual instances, regardless of their local neighborhood structures. As stated in (Schlichtkrull et al., 2018), explicitly modeling local structure can be an important supplement to help recover missing relations. Inspired by the success of GNNs in modeling structured neighborhood information, another line of literature (Schlichtkrull et al., 201 8: Zhang & Chen, 2018) learns the relation embedding based on its neighborhood subgraph using graph convolution layers. With a similar approach, recent work (Zhang & Chen, 2019; Teru al., 2020) illustrates the inductive capabilities of generalization to unseen nodes. However, these approaches fail to generalize to unseen relation types, as it is indirect to introduce the "neighborhood" for relation type upon the graph structure.
Meanwhile, our work also relates to previous researches (Qu et al., 2019; Qu & Tang, 2019; Zhang al., 2020; Qi et al., 2018; Zheng al., 2019) studying effectively combine GNNs techniques with symbolic logic rule-based approaches (Giarratano & Riley, 1998; Jackson, 1998; Lafferty et al., 2001; Taskar al., 2012; Richardson & Domingos, 2006; Singla & Domingos, 2005). However, these methods, as originally proposed, are transductive in nature. Unlike our method, they still require learning relation type specific embeddings, whereas we treat the relation prediction as a graph pattern matching problem, independent of any particular relation type identity. There also other work (Yang et al., 2014) that designs a logical rule extraction approach based on the potential generalization ability of transition-base various neural-emben emwedddieeddddbbbbieee based models, this set of models constitute our baselines in the inductive setting. Notably, comparing to the message passing neural network (Gilmer et al., 2017), the current prevailing GNN framework, as illustrated in Figure A2, GraphANGEL is able to avoid the GNNs' limitation of using neighbor nodes by using nodes satisfying certain logical patterns (See detailed discussion in Appendix 14.1).
methods. As this method can incorporate with
Another popular link prediction approach is to directly infer the likelihood of relation existence using a local neighborhood or local subgraph (Schlichtkrull et al., 2018; Zhang & Chen, 2018; Hu et al., 2020). A significant difference between those works and our approach in the formulation of the loss function. Let fr be any function that maps vector to a scalar score parametrized by and e, be scalar function, then the prior works' loss function often take the form L = (sstrAteD {(fr(h))) (h"),,) v). meaning that the score computation explicitly depends on the embedding of relation to be predicted. Ours, in contrast, has the form L E(....t) E(d(h' function and d is distance function between two vectors, which are embeddings of set of subgraphs. Consequently, our loss function É does not require representation of r.
ht),,, d(h', h h -)),)) where é is a scalar
CONCLUSION
We propose a novel relation prediction framework that predicts the relations between each node pair based the subgraph containing the pair and other subgraphs with identical graph patterns, and has a strong inductive bias for the generalization to unseen relation types. With these graph patterns, we introduce several graph pattern searching and sampling techniques, which can efficiently find subgraphs matching the patterns in triangle and quadrangle shapes. In the future, we plan to further extend GraphANGEL to more complex structures (i.e., compositional logical rules).

---

Published as a conference paper at ICLR 2022
Acknowledgments. The Shanghai Jiao Tong University Team is supported by Shanghai Municipal Science and Technology Major Project (201SSHZDZX0022) and National Natural Science Founda- tion of China (62076161, 62177033). We would also like thank Wu Wen Jun Honorary Doctoral Scholarship from Al Institute, Shanghai Jiao Tong University.
REFERENCES
Pablo Barceló, Egor V Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. In International Conference on Learning Representations, 2019. 28, 29
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 10Xivv8806.0/1 2018.
Ye Bi, Liqiang Song, Mengqiu Yao, Zhenyu Wu, Jianming Wang, and Jing Xiao. A heterogeneous information network based cross domain insurance recommendation system for cold start users. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 2211 1-200, 2020. 6, 30
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250, 2008.
Antoine Bordes, Nicolas Usunier, Alberto Barcia, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Neural Information Processing Systems (NIPS), pp. 1-9, 2013. 1, 6, 9, 20, 30, 33, 34
Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Y Hammerla. Relational graph attention networks. arXiv preprint arXiv: /904.0509 2019. 20,
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018. 1, 6, 9, 20, 30
Andrey A Dobrynin, Roger Entringer, and Ivan Gutman. Wiener index of trees: theory and applica- tions. Acta Applicandae Mathematica, 66(3):211-22 1-249,224492 2001. 26
Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345, 1962. 26
Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin. Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. Cypher: An evolving query language for property graphs. In Proceedings of the 2018 International Conference on Management of Data, pp. 1433- 1445, 2018. 3,4
Giorgio Gallo and Stefano Pallottino. Shortest path algorithms. Annals of operations research, 13(1):
1-79, 1988. 26
Joseph C Giarratano and Gary Riley. Expert systems. PWS publishing co., 1998.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212 2017. 9,
William Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran As- neurips cc/ httpssccccppppppppeeeeee ptppp/pp/////iieeeeeeee pdf. 26, 33
sociates, Inc., 2017. URL ht / httptpttttt/toooooooooooo httpt:ppsp//ppcceeeieeeeeeeeeeee
Junxian He, Graham Neubig, and Taylor Beng-Kirkpatrick. Efficient nearest neighbor language models. arXiv preprint arXiv:2 042 2021. 26
10

---

Published as a conference paper at ICLR 2022
Binbin Hu, Chuan Shi, Wayne Xin Zhao, and Tianchi Yang. Local and global information fusion for top-n recommendation heterogeneous information network. Proceedings of the 27th ACM International Conference Information and Knowledge Management, pp. 1683-1686, 2018a.
Binbin Hu, Chuan Shi, Wayne Xin Zhao, and Philip S Yu. Leveraging meta-patt path based context for top-n recommendation with a neural co-attention model. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1531-15400 1540, 2018b. 6
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In
Proceedings of The Web Conference 2020, pp. 2704-2727 2710, 2020. 6, 9, 20, 30
Peter Jackson. Introduction to expert systems. Addison- Wesley Longman Publishing Co., Inc., 1998.
Guoliang Ji, Shizhu He, Liheng Xu, Kang Liu, and Jun Zhao Knowledge graph embedding via dynamic mapping matrix. In Proceedings of the 53rd anmual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: Long papers), pp. 687-696, 2015. 9
Jiarui Jin, Jiarui Qin, Yuchen Fang, Kounianhua Du, Weinan Zhang, Yong Yu, Zheng Zhang, and Alexander Smola. An efficient neighborhoodd based interaction model for recommendation heterogeneous graph. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 75-84, 2020. 9
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. arXiv preprint 2019. 26
Urvashi Khandelwal, Angela Fan, Dan Jurafsky, Luke Zettlemoyer, and Mike Lewis. Nearest neighbor machine translation. arXiv preprint arXiv:2010.00710, 007000 2020. 26
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint (XXv:16690002000 2016. 26,
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:/810.05999 2018. 26
Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 4208):30-37, 2009. 1
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for
knowledge base completion. In International Conference on Machine Learning, pp. 2863-2872.
PMLR, 2018. 30
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. 2001. 9
Harry R Lewis. Computers and intractability. a guide to the theory of np-completeness, 1983. 4
Yankai Lin, Zhiyuan Liu, Huanbo Luan, Maosong Sun, Siwei Rao, and Song Liu. Modeling relation paths for representation learning of knowledge bases. arXiv preprint arXiv: 1506. 00379, 2015. 9
Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh. Hierarchical question -imooe co-attention for visual question answering. arXiv preprint arXiv: 1606600061., 2016. 5, 21, 26
George A Miller. Wordnet: a lexical database for english. Communications of the ACM, 38(11): 39 41, 1995. 6
Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefenstette. Differentiable reasoning on large knowledge bases and natural language. In Proceedings of the AAAI conference artificial intelligence, volume 34, pp. 5182-5190, 2020a. 29
Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. Learning reasoning strategies in end-to-end differentiable proving. In International Conference on PMLR, 2020b. 29
Machine Learning, pp.

---

Published as a conference paper at ICLR 2022
Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly-labeles reviews and fine-grain rre-grained aspects. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLLP), pp. 188-197, 2019.
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. three-way model for collective learning on multi-relational data. In leml, 2011. 1,9
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. Factorizing yago: scalable machine learning for linked data. In WWW, 2012. 1,9
Siyuan Qi. Wenguan Wang, Baoxiong Jia, Jianbing Shen, and Song-Chun Chun Zhu. Learning human- object interactions by graph parsing neural networks. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 401-417 2018.
Meng Qu and Jian Tang. Probabilistic logic neural networks for reasoning. arXiv preprint arXiv: (eti::/906.0444 2019. 6, 30,0,,3 32
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. arXiv preprint arXiv:1905.06214, 2019. 9
Meng Qu, Junkun Chen. Louis- Xhonneux, Yoshua Bengio, and Jian Tang, Rnnlogic: Learning logic rules for reasoning on knowledge graphs. arXiv preprint arXiv:2010.04029, 2020. 6, 30
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine learning, 62(1-2): 107-136, 2006. 1,
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018. 5, 6, 9, 20, 25, 30, 32
Hongzhi Shi, Yong Li, et al. Differentiable learning of graph-like logical rules from knowledge graphs. 2020.
Parag Singla and Pedro Domingos. Discriminative training of markov logic networks. In AAAI, volume 5, pp. 868-873, 2005. 1, 6, 9, 30
Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. arXiv preprint ArXiv:992.100997 2019a. 6, 9, 20, 30, 33, 34
Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-evaluation of knowledge graph completion methods. arXiv preprint arXiv:/911.03903 2019b.
Ben Taskar, Pieter Abbeel, and Daphne Koller. Discriminative probabilistic models for relational data. arXiv preprint 1301.v1 2012. 9
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pp. 9448-9457. PMLR, 2020. 1, 6, 9, 30
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, pp. 57 67-66, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In International Conference on Machine Learning, pp. 2071-2080. PMLR. 2016. 6, 9, 30, 33
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017. 26
Alastair Walker. An efficient method for generating discrete random variables with general distributions. ACM Transactions Mathematical Sofwware (TOMS), 30):2533-266 1977. 18
12

---

Published as a conference paper at ICLR 2022
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, sighyyperformant package for graph neural networks. arXiv preprint arviv / 1909.01315, 2019a. 30
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. In The World Wide Web Conference, pp. 4022-20322 2019b. 6, 20, 30
Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel. Niprolog: Reasoning with weak unification for question answering in natural language. arXiv preprint arXiv:1906.066 2019. 29
Bo Yan, Matthew Walker, and Krzysztof Janowicz. A time-aware inductive representation learning strategy for heterogeneous graphs. In Proceedings of the 15th International Workshop Mining and Learning with Graphs (MLG'19) at KDD, volume 19, 2019. 9
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference knowledge bases. arXiv preprint arXiv:1412.6575, 2014. 1, 8, 2.
Fan Yang. Zhilin Yang, and William W Cohen. Diffcrentiable learning of logical rules for knowledge base reasoning. arXiv preprint arXiv:1702.08360 2017. 2
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. arXiv preprint arXiv: 1tXvv:/91000288/1 2019. 3
Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering, arXiv preprint arXiv:2104.063778 2021.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heterogeneous graph neural network. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 793-803, 803, 2019a. 6, 9, 20, 30
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5177 2018. 9, 26
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. arXiv preprint arXiv: /2058, 2019. 1,9
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embeddings. arXiv preprint
1rXiv:1904.1028/ 2019b. 6, 30
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. arXiv preprint 1XXv:20011.185000 2020.
Jing Zheng, Jian Liu, Chuan Shi, Fuzhen Zhuang, Jingzhi Li, and Bin Wu. Recommendation in heterogeneous information network via dual similarity regularization. International Journal of Data Science and Analytics, 3(1):35 48, 2017. 6
Xin Zheng, Zhirui Zhang, Junliang Guo, Shujian Huang, Boxing Chen, Weihua Luo, and Jiajun Chen. Adaptive nearest neighbor machine translation. arXiv preprint arXiv:2105. 13022, 2021. 26
Zilong Zheng, Wenguan Wang, Siyuan Qi, and Song-Chun Zhu. Reasoning visual dialogs with structural and partial observations. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 6669-6678 2019. 9
13

---

Published as a conference paper at ICLR 2022
A1 ILLUSTRATIONS OF NOTATIONS
graph pattern
logical pattern
notation
Edge(x, 2)
n
A Edge
target node
target subgraph
target logical expression
notation
Watch(Person E, AAseeall Base(Arsenal) London) Source(Person E) Target(London)
S* p,k
K
Q
pa
supporting subgraph
S p.k
target subgraph set
Spa
refuting subgraph set
l (st p q=1
{St p.k p.kk k=1
K
{5 p q=1
Q supporting subgraph embedding set
K target subgraph embedding set
K
target
subgraph embedding set
ep.
p.k
Pp.
(ep.a) q=1
[ep4) 9-1
Figure A1: An illustrated example of notations in GraphANGEL.
In this paper, we begin by bridging the logical expression and the graph pattern. Taking Fig- ure Al as example, we aim to predict the relation Live between the source and target nodes (i.e.. Person E and London). We consider the 3-cycle graph pattern. Formally, we use HI where p 1, P denote certain graph pattern. For each ΠI, we use IIş to de- note the corresponding target pattern, II to denote the corresponding supporting pattern, II to denote the corresponding refuting pattern. Concretely, as shown in Table 1, we can define I1 = Edge(æ, 2) Edge(z, y). II; = Edge(æ, 2) Edge(z, y) A Source(z) A Target(y), I = Edge(æ, 2) =)A Edge y) / /Edge (I, y). П = Edge 2) Edgee AEEge, (x, y). According to these patterns, we can retrieve the corresponding subgraphs the graph shown in Figure 1) and construct the corresponding subgraph sets. Figure Al illustrates tar- get subgraph representing the logical expression Wat Wateeherrrse Lendon) ce ([PPeersnnn) A Target(London) We use S p, to denote the k-th sampled target subgraph following the target pattern II, where k = 1, 1,2,..., K, Sp. denote the q-th sampled supporting subgraph following the supporting pattern I Sp. to dentoe the g-th sampled refuting subgraph following the refuting pattern 11, where q 1, ......
Arsenal
For each 1I, after applying pattern retrieval and sampling introduced in Appendix A2, we build set of target subgraphs denoted as (8
set of supporting subgraphs denoted as (Spt) set of 1- We then learn representation for each subgraph, and obtain of corresponding target subgraph embeddings denoted ( of corresponding supporting subgraph embeddings denoted as (ett, 1 set of corresponding refuting subgraph embeddings denoted as (c
1
refuting subgraphs denoted as 1
A2 PSEUDOCODE, CORRECTNESS PROOFS, AND COMPLEXITY ANALYSIS FOR 3-CYCLE AND 4-CYCLE PATTERN RETRIEVAL AND SAMPLING
In this section, we first summarize the complexity of retrieving and sampling subgraphs following the graph patterns in 3-cycle and 4-cycle with the following theorem:
14

---

Published as a conference paper at ICLR 2022
Theorem 1. (Time Complexity of Retrieval and Sampling) Given graph G (V. and a graph pattern Ily-c in 3-cycle and a graph pattern elz-e in 4-cycle, the time complexity of retrieving all the (supporting) subgraphs satisfying 113 11z-cycle is O(EE)), ), of retrieving all the (supporting) sub- graphs satisfying I14-eycle is (maxx[E) (N-cccce)) where Na-cycle is the number of quadratic cycles in G and also the trivial lower bound of the time complexity. For uniform sampling algorithms, the time complexity of sampling n4-eyyla supporting cases of ey4- is O[EE} n4 As there are usually more refuting cases than supporting ones, the time complexity of sampling v refuting cases 1f lly-cycle
I1g-cycle is O(V) + |&| + n.)
In the following subsections, we show the proof of Theorem by providing the pseudocode of retrieval and sampling algorithms along with the correctness proof and complexity analysis in Appendix A2.1 and A2.2 respectively.
A2.1 PSEUDOCODE, CORRECTNESS PROOFS, AND COMPLEXITY ANALYSIS FOR 3-CYCLE AND 4-CYCLE PATTERN RETRIEVAL
In this part, we first provide two algorithms for searching and retrieving supporting subgraphs following the graph patterns in 3-cycle (i.e., Ils-cyele) in Part 1; and one algorithm for searching and retrieving supporting subgraphs following the graph patterns in 4-cycle (i.e., Ilg-cycle) in Part
Part 1. In Algorithm 2, we present the pseduocode for searching and retrieving all the supporting subgraphs following the pattern Iī I13-cycle- The input is graph G = (V. E) and the output is a set B containing all the supporting subgraphs satisfying Ill-eycle- We denote the degree of node by da. and the set of neighbor nodes node u graph G by Ng)
Algorithm 2: Search and Retrieval Algorithm A for I13-cycle
Vi + {uld, > { 1/2 + fulda S { B B
foreach E Vi do foreach E V/ do
foreach w E V1 do if (u, r) B - B [uu, (
and (u, w) E and (v, w) E then w]
end
end end end
foreach
E 1/2 do foreach E (u) do
foreach w E (u) do if (v. w) E & then
B- BU v, v, w}}
end
end
end end
Now, we investigate the correctness and the time complexity of Algorithm 2.
Proof. For any 3-cycle (i.c., 3 nodes connected by 3 edges) (u, v, w). if the degrees of all three nodes are greater than |g] (i.e., du > | and d, > |&] and d. > ( it will be enumerated in the first loop. Otherwise, if the degree of any node is not greater than [g] the 3-cycle will be cnumerated the second loop.
In order to analyze the time complexity, we first investigate an upper bound of V1 = {u du > {8
2|8|
Σ d,
Σ
du
Mi
2
NEW
REVi
15

---

Published as a conference paper at ICLR 2022
For the first main loop of the algorithm, we have
Σ
1
MI
< =
(5)
u. 14-
For the second main loop, we have
Σ Σ
1=
Σ
d S
El
S 2 0((E)5)
(6)
NEVa (a,,)E (u.r)EE
NEV/
Summarizing the analysis above, we conclude that the overall time complexity O((E))).
Alternatively, we provide another searching and retrieving algorithm for all the supporting subgraphs following Ilz-cycle in Algorithm The inputs and outputs of the algorithm are consistent with Algorithm 2.
Algorithm 3: Search and Retrieval Algorithm for Tyz-cycle
+ 0 foreach Vdo
foreach e E <Ng(u) where du S dr do foreach (V) where du S dy do if (v. w) E & then
B [(u, v, w,w)]
end end
end end
Next, we analyze and prove the correctness and the time complexity of Algorithm 3.
Proof. It is not difficult to find that each 3-cycle (u, u, we) satisfying d, 2 d, 2 du is enumerated.
To analyze the time complexity, let consider how many enumerated:
ΣΣ Σ 1
Σ WEV (w.a)e du
Σ
Σ
Σ dp.
NEV (ue)ee (w.s)ee Sdu dw Sdu
(ui
wEV
(M,n)eR duSdu
From Eq. (4), know that for each satisfying d, > [8| 2| different us the outer loop. Hence, we have
since d, d > [8]3, there most
Σ
Σ du = Σ de Σ
NEV
(u.tee
NEV
(2.N)e
to So
dy
Σ
([d,,
du S 1812
[d,> 1812 de Σ
VEV
(N.
do
Σ wEV
do < S [8]3]
d Σ 1+ du 181$ do Σ
(8)
(u. do Sdu
(u.vles
duSdu
d, < 1813/
18)2 + [d, > |8|5 (1))d.)
NEV
=1 Σ d, 2
vEV
where [:] represents the boolean indicator function (i.e., [x] 1 if is true; otherwise false).
Therefore, the overall time complexity is also O(
16

---

Published as a conference paper at ICLR 2022
Part 2. In Algorithm 4, demonstrate the algorithm for searching and retrieving all the supporting subgraphs following graph patterns in 4-cycles (i.e., Iey-cccl).. The inputs, outputs, and notations similar to those in Algorithm 2.
Algorithm 4: Search and Retrieval Algorithm for 114
B < 0
foreach do To + { for each a E.V foreach E (N) where du I dy do
foreach E Ng)(v) where dw I du do
foreach x E To do
B t BU v, v, end
Tw +- Tw [
end
end end
We provide the correctness and the time complexity of Algorithm 4 as follows.
Proof. For correctness, we can see from the algorithm that every 4-cycle (u, v, w. x) satisfying du 2 max d dz) enumerated.
For time complexity, let N4-eycle denote the number of quadratic cycles in g. We first have the time complexity ((Ng-cyc1e) of the innermost loop. For the outer three loops, us consider how many ws are enumerated:
ΣΣ Σ t
1
Σ
Σ (u.e)CE
Σ (w, EE
dy-
(9)
(U, (WIe)EE du Sdu
a
a
(u. du Sd
Sdu
du Sdy
From Eq. (8), we have
Σ
d, 2
(10)
(E, dn.Sd.
Thus, the overall time complexity is O(max(1E] N4 NN-ccclo))
L
A2.2 PSEUDOCODE, CORRECTNESS PROOFS, AND COMPLEXITY ANALYSIS FOR 3-CYCLE AND 4-CYCLE PATTERN SAMPLING
From the subsection above, we know that given graph G = (V, E), we have different algorithmic complexities depending on the graph pattern I1. For 1ls-cycle (i.e., 3-cycles), the time complexity of retrieving all supporting subgraphs is O({E)²) ). For IT Tyccca (i.e., 4-cycles), the time complexity is O(max(|E) 2 NNs-yycee), where Na-cycle is the number of quadratic eycles in G.
However, for large-scale graphs. it is impractical to retrieve all quadratic-cycle graph patterns since Na-cyele could be large. In addition, the number of refuting cases for both IIs-cycle and IIg-cycle may also be large. These problems may lead to the high computational cost of these search algorithms. Realizing this, we further introduce the technique of uniform sampling to keep the time complexity within an acceptable level.
Therefore, in following, we first provide one algorithm for uniformly sampling and retrieving graph patterns following 11 in Part I; and two algorithms for uniform sampling and retrieving graph patterns following the refuting patterns in 3-cycle shape (i.e., IT Iī-eycla) and 4-cycle shape (i.c., _14-cyc1a) in Part 2. As reminder, while practical, another approach to obtain graph patterns following Ilz-yccaa and II - is random walk, although random walk is often not efficient enough.
Part We present the algorithm for sampling and retrieving all the supporting subgraphs following Th Tyccccl in Algorithm 5. The inputs to the algorithm graph = (V,E) and 744 14cclcll: rep-
17

---

Published as a conference paper at ICLR 2022
resenting the number of subgraphs sample. The output is set B containing all sampled graph patterns.
Algorithm 5: Uniform Sampling and Retrieval Algorithm for 11 cycle
B (
foreach V do
Tww < {} for w EV
foreach E (u) where dy I dd do
foreach w E (V(v) where du S du do
Tuw Tuw U {v}
end
end end
foreach (u, w) where Tuo j Ø do
Cuon t [Tumll Twnn - 1)
end
e
Engo Cuw
foreach (u, w) where Tuw # Ø do
Paw f Cuw
end
for i +- 1 to M2- eycle do
Sample (u, w. where Taw + Ø with probability Paw
Uniformly sample two different nodes u and x from Twm
(u, w) & then
- B [(u, U, w,,))
end
end
We provide the correctness and the time complexity of Algorithm as follows.
Proof. For correctness, we can observe from the algorithm that every 4-cycle (u, w. x)) satisfying du 2 max day, d&e) is counted in Tuw exactly once, where v E Taw and x E Tuw We sample (u, w) with the probability of occurrence of the 4-cycle (u, w. .r), then sample different and uniformly from Tuw.
For time complexity, it has been proved in Algorithm 4 that the time complexity of computing T is O(EE).) Notably, there are O(EE} non-empty Ts.
Therefore, if we sample (u, w) through Alias Method (Walker, 1977), then the overall time complexity is O(E : + n4-cycle).
Part We further provide two path sampling algorithms. In most practical cases, there are many more refuting examples than supporting ones, and if we assume then Algorithm 6 can be used to sample graph patterns following refuting patterns in 3-cycle shape (i.e., [lz-yyeee; and A Algorithm to sample graph patterns following refuting patterns in 4-cycle shape (i.e., IT ITa-cycia).
Algorithm 6 displays the algorithm for uniformly sampling subgraphs following Tg- in g. The inputs, outputs, notations are identical to those in Algorithm 5. We provide the correctness and the time complexity of Algorithm follows.
Proof. For correctness, shown in the algorithm, we formulate the sampling of refuting cases of 1ls-cycle into uniformly sampling three-node paths, namely (u, v, w). We first sample the intermediate node of the path (i.e., v), where there dd,dd, - 11//2 three-node paths with as its intermediate node. Next, we sample v with probability Pe to ensure uniformity, where p, d,, E, (d, 1), and then sample its two neighbors to form the path.
Using Alias Method, the overall time complexity is O(D) + [1] n)), where the computation for the degree requires O([E)), the first two loops require O(V)), and the last loop requires O(n). n
18

---

Published as a conference paper at ICLR 2022
Algorithm Uniform Sampling and Retrieval Algorithm for cyyle
B 3-1 0 foreach do Ca t du(du= 1)
end
+ En Cu
foreach E do
Pa t C
end
for i + 1 to n do
Sample with probability Pe Uniformly sample two different neighbor nodes (i.e., u and w) of v
if (u, w) & then
- B [(u, v, w.)
end end
Algorithm 7: Uniform Sampling and Retrieval Algorithm for II cyycle
B+ 0
foreach (u, v) E do if d, and du = 2 and (V(()) (V) = then Cue
end else
Cae f (dg 1) (de 1) 1)
end
end
+ Eng Cue
foreach (u, v) E & do
Pas t Cue/c
end
for i + to do
Sample (v, w) with probability Pew Uniformly sample neighbor node u of v Uniformly sample neighbor node x of if u o and (u,x) & & then +- BU U, u,w, end
end
In Algorithm 7, we present the algorithm for uniformly sampling graph patterns following II -yyila in G. We provide the correctness and the time complexity of Algorithm follows.
Proof. Analogous to Algorithm 6, we formulate the sampling of refuting cases of II eycie into uniformly sampling four-node paths namely (u, v, w,, xr). first analyze the correctness of the algorithm, we first sample the intermediate edge of the path (i.e., (v, w)). There are (d.-1) 1)) (dy - three-edge paths (including 3-cycles) where the intermediate edge is (v, w). Hence, we sample (e, w) with the probability proportional to (d, 1) (dw 1). and then sample neighbor node u from and another one x from w, and reject the case when it forms a 3-cycle.
To guarantee the time complexity, do not sample the edge (v, w) when and have the only common neighbor, thus W [v)
(d,-1)-(dww-) S when e + 0, i.e., we reject with probability no more
than J, the expected time complexity is O(I) + +
19

---

Published as a conference paper at ICLR 2022
Algorithm 8: Implementation of GraphANGEL.
Input: Graph G, Patterns I...... Ip, Source-targer node dataset D. Output: Prediction for each (8,r,
for each pattern p do
Construct 11p. 11 11p.
Search/Sample and retrieve subgraphs following Hp through Algorithms 2,3,4,5,6,7. Store all the subgraphs in B. end
for each (s, 1, D
for each logic пI do
Sample and retrieve K subgraphs S7,6 matching IT, in B.
Sample and retrieve Q subgraphs Sit matching 11 in B.
Sample and retrieve Q subgraphs Sp.g matching II, in B. Compute epp. ep.0 cv. according to Eq. (1).
end
Compute s², according to Eq. (2).
Calculate ' via ÿ -
Re-sample and retrieve subgraphs following 1I, through Algorithms 6,7,5,
Update B with the re-sampled subgraphs. Update parameters by minimizing loss L shown in Eq. (3).
end
Notably, these algorithms are valuable because the number of the refuting cases are considerable in practice, and they make GraphANGEL more relevant for practical deployment.
A3
IMPLEMENTATION ALGORITHM OF GRAPHANGEL
A3.1 ALGORITHM FOR IMPLEMENTATION OF GRAPHANGEL ON STATIC GRAPHS
For the heterogeneous graph based recommendation task, we follow (Hu et al., 2020; Wang et al., 2019b; Zhang et al., 2019a) to predict the existence edge between each given node pair (s, while in the knowledge graph completion task, follow (Bordes et al., 2013; Sun et al., 2019a; Dettmers et al., 2018) to mask head and tail entities instead relation prediction. As the input of model is triplet (s, r, t), one score all the possible triplets matter either relation tail entity (i.e., node) / is masked. We then rank all these tuples for evaluation.
Overall Time Complexity of Original Algorithm. Theorem 1 shows the time complexity of searching and retrieving the subgraphs following the pre-defined 3-cycle and 4-cycle shaped patterns: ( & n44-yye=)) for sampling Tyc-c subgraphs satisfying 11 O(V)+ |8| + +n) for sampling n refuting cases of Tī-eycle 4-
Besides the subgraph retrieval part, the main components of GraphANGEL are the representation computation part (i.e., ))) and the similarity computation part (i.e., W) We further analyze the time complexity of these parts as follows.
For 4, described in Section 3, employ R-GCN (Schlichtkrull al., 2018) (See Appendix A3.3 for details). One can use other GNN architectures (e.g., R-GAT (Busbridge et al., 2019)). Hence, without loss of generality, we analyze the time complexity of the general GNNs following the message passing framework (Gilmer et al., 2017), most of whose update functions can be formulated as H [I+1) = (L II) (()), where H E R x is the embedding matrix obtained after / steps of propagation, and L represents the Laplacian matrix for the graph, defined by = D AD- ,, A the adjacency matrix and D is the diagonal degree matrix, W 12d. xdx-1 is the trainable transformation matrix. The 1-th propagation layer, the matrix multiplication has computational complexity O 1- d, x di-1), where [+ the number of nonzero entities in the Laplacian matrix, and the di and d are the current and previous transformation size. Then, the time complexity of t with I. layers is O |++ de x dj-1).
20

---

Published as a conference paper at ICLR 2022
(a) GraphANGEL
(b) GCN, GraphSAGE, GAT
Asseral
Arsonal
(c) SEAL
(d) PPNP, APPNP
Figure A2: An illustrated example of nodes and edges involved in GraphANGEI. and other existing approaches, where nodes and edges in grey are activated while the other colors of nodes and edges represent their types. As introduced in Table 2, we here show the results of two graph patterns in 3-cycle shape. For clarity and simplicity, in this case, the number of layers of GNN models are constrained as one.
For V, as Section 3 shows, we use a co-attention mechanism (Lu et al., 2016) (See Appendix A3.4 for details). Without loss of generality, let Naead denote the number of heads. Then, the time complexity of V is O(PP K)+ (P x Q) d² -Neead).
Then, the overall time complexity of Algorithm is to sum up all the above computation costs.
In Algorithm 1, we retrieve and sample subgraphs for every source-target node pair, which can be time-consuming. Algorithm 8 introduces additional steps that precompute all the graph patterns and their satisfying subgraphs
data preprocessing step.
The intuition behind this is very straightforward that, as shown in Table 2, the graph patterns considered in this paper quite simple, involving at most four nodes. For knowledge graphs, it's acceptable to pre-compute all the supporting subgraphs of 3-cycle shaped graph pattern using Algorithm 2 or 3. We also develop novel search and retrieval algorithm (as shown in Algorithm 4) retrieve all the supporting subgraphs with O ((max(()) Na ce-cyat)), However, as the number of supporting cases of 4-cycle shaped graph pattern (i.e., N4-cyclo) is too large (as shown in Table A3), while practical, we uniformly sample N4-cycle subgraphs following supporting graph patterns in 4-cycle shape using Algorithm 6. 14 1y-cc is dyper-parameted which we set as the number of 3-cycles in graph (i.e., f14-cycle Ng-cyclo). All these subgraphs into buffer B. For heterogeneous graphs, since the graph schema of these graphs are usually not complex. We can cover all possible graph patterns by enumerating on the graph schema. Similarly, this enables us to pre-compute the graph patterns and store all the retrieved and sampled subgraphs following each graph pattern in the buffer B. We then can build an index of the buffer by the graph patterns as well as the subgraphs following each graph pattern. During training, of the whole graph for each source- source-target node pair. Compared with the original one in Algorithm 1, we reduce the complexity and improve the efficiency. We can further set update interval to refresh B
sample and retrieve subgraphs in the buffer instead
21

---

Note that all the algorithms introduced in Appendix A2 mainly focus searching and retrieving the subgraphs in the context of the static graphs. However, the graphs used in the real-world scenario almost are dynamic graphs, which always need be modified and updated. In the followings, we show the (incremental) subgraph retrieval algorithms which updates the old buffer (denoted as Baia) calculated by the old graph (denoted as GoIa) to the new buffer (denoted as Basv) computed by new graph (denoted as I.es). Formally, we use Geex (Vues: Enou) and Gold (Vora, EGIa) to denote the new graph and the old graph respectively, where Voia and Vnez denote node sets, Eold and Ensw Published as a conference paper at ICLR 2022
by re-sampling the supporting cases of Iyc-c and refuting cases of cyy-cyele and eyy-eycle- While practical, we find that whether refreshing or not would not bring much influence, and establish an ablation study for the buffer size in Appendix A6.6.
Let n3-cyce "s-cycle" "4- "y-cyclo denote the number of refuting samples of 115 and 11 cyclle respectively, In practice, we set = fyg-cyele -l-cyyle - 2- 2.NN-aycte We sample refuting cases of II3 cycla and IL4-yycle respectively and store them into B.
Space Complexity of Storing subgraphs. From the above analysis, we know that if we choose to store all the supporting subgraphs, the space complexity of storing these subgraphs is ( Na-eycle)- While practical, is complexity is ( -4-cycle): and (n)) for implementation.
And for the subgraphs of refuting cases, the space
Notably, this space complexity is different from the space complexity of the algorithms in Theorem 1, which is the same its time complexity.
Algorithm Search and Retrieval Algorithm for eyg- in (a) Shape
Vi+ (u Voiald, > o), 1/2 t {u Voialda S o) where <- |Eoial /a/pi//([/)))) /(I Vozel B B- ()
foreach V/ do
foreach E V1 do
foreach w E A AV new do
tu r) Eo1s and (u,w) E A and (w, E AE then B - B U (u, v, w))
end
end end end
foreach
u E 1/2 do foreach E NN (u) do
foreach w E NN Agt (u) do
if (v. w) E A then - BU (u, e, w)}
end
end end
end
A3.2 ALGORITHM FOR IMPLEMENTATION OF GRAPHANGEL ON DYNAMIC GRAPHS
denote node sets. We do not introduce the relation sets, as subgraph retrieval does not consider the relations. We use Aold and Asov to denote the adjacency matrices of Gaov and Goia regardless of the edge types (i.e., relations).
Let Ag (AV-, AE-) denote a graph including all the nodes and edges removed from Gold comparing Gaexi and Ag+ (AV+, A denote graph consisting of all the nodes and edges added to Sola comparing to Inev- As some edges in Ag+ may connect the a node in Gold and a new node further divide AG+ into two graphs. One is graph including all the edges connecting these nodes, denoted as Ag+ = (Avt new? AEt,). And the rest edges together with corresponding nodes construct another graph denoted as AG = (AV A&ta). Hence, putting AG- aside, the original new graph Ineu be divided into three parts to consider: Gold.
nodes and
22

---

Published as a conference paper at ICLR 2022
Algorithm 10: Generation of Uniform Sampling Rate for Each Node and Edge
Following is Generation of Uniform Sampling Rate for Each Node foreach E V do Cu - (d
end
En, Cu
foreach E V do Pa - Cu/C
end
Following is Generation of Uniform Sampling Rate for Each Edge
foreach (u, u) E & do
d, = and d, = 2 and (W) (WV(()) = then
Can + 0
end else
Cue (dx 1) (dv - 1)
end
end
Eup Cuv foreach (u, u) E & do Pue t Cue/C
end
AGueu and AGoia- Notably, these three parts have overlapping nodes but do not have overlapping edges, as shown in Figure A3.
To efficiently obtain AG-, Agoi and AGrex from Gola and Gnex. we can first compute AG by comparing Inev to Gola (or comparing Anau Aoia). We can then calculate A AV+ consisting of the nodes in Vneu but not in Vola by
Gnew
(a)
D Vnew+ AV- Voia- Next, we can calculate
A E+ by referring to Aner- And, DE+ can be derived new
(b)
by AE Ezew AE Eo1s -
(c)
Gold
From Algorithms 2,3,4,6,7,5, we can see that the buffer B only store the of nodes (i.e., node IDs) of each subgraph in- stance. These IDs for subgraphs following the supporting graph patterns in 3-cycle shape represent all the 3-cycles in the graph, and the IDs for subgraphs following the sup- porting graph patterns in 4-cycle shape represent a number of uniformly sampled 4-cycles in the graph. Therefore, we are seeking for an efficient way to update the buffer from Boia. the buffer computed by Goia. to Beev the buffer com- puted by Snav- From the above analysis. we are required search and retrieve all the new subgraphs following eycce and uniformly sample the new subgraphs fol- lowing II As the time complexity of sampling n refuting subgraphs following 11ş-cycle or 11 eycle in Suex is O(Daevl + +1 +n) (as shown in Theorem 1), and thus it's yet efficient directly re-compute these refuting subgraphs.
(d)
A Anew
(f)
(c)
AG
Figure A3: An illustrated example of divid- ing Gace (including the nodes and edges in the black box) into Gota (including the nodes and edges the blue eircle), Afues (includ- ing the nodes and edges the green eircle) and AG.aa (including the nodes and edges in purple color). when putting Ag aside. Note that there is overlapping nodes but overlap- ping edges between Goza and AGaz. AGue and AGae. (a)() denote the two types of 3 3-cycles and (c)- denote five types of 4- cycles not within either Gois or AGnev-
We summarize the pipeline of updating the buffer B in Algorithm 11 where [-] denotes the flooring function, and provide detailed descriptions follows.
Firstly, we deal with "delete modifications" from Gold to Gnex (i.e., Ag-) by removing all the instances that include the nodes in AV- Secondly, for
23

---

Published as a conference paper at ICLR 2022
S
(b) Graph pattem considered GraphANGEL
(a) An instance of Heterogeneous Graph
(c) Nodes edges activated
v
S
s
(d) An instance of Homogeneous Graph
(e) Graph pattern considered GraphANGEL
(f) edges GraphANGEL
Figure A4: An illustrated example of how GraphANGEL works on both the heterogencous graph shown in (a) and the homogeneous graph shown in (d), where the colors of the nodes and edges represent their types in the heterogeneous graph. For the heterogeneous graph, GraphANGEL can automatically find the graph pattem by scanning on the graph schema by given shapes (e.g.. Pair, 3-cycle, 4-cycle). pattern in (b). Based on the graph and graph pattern, we show the nodes and edges activated GraphANGEL in (c), where the nodes and edges in colors are activated and those in black are not activated. However, for the homogeneous graph, since there is graph pattern based the node and edge type, design the graph pattern directly based the shape (i.e., hexagon shape in (e)). We then show the nodes and edges activated in (f), where nodes and edges red construct a subgraph following target pattern the green ones compose a subgraph following analogy pattern.
show an example graph
subgraphs following 1ğ--cycle. these 3-cycles might either in AG or include the nodes and edges across Gold and AG For the former one, we can directly apply Algorithm or 3 in Ag while for the latter one, we need to consider two different cases, shown as (a) and (b) in Figure A3. For searching and retrieving subgraphs in (b) shape, it's practical to directly enumerate all the edges in AV new- as A naz is expected to be small. However, (Vial is large in the most time, and thus develop Algorithm to efficiently search and retrieve subgraphs in (a) shape, whose design is analogous to Algorithm 2.
Thirdly, for IT cy-cecle. similar TT- --ycycle there also two classes of subgraphs. For the first one, we can uniformly sample number subgraphs following I1g- by directly applying Algorithm in AG+ For the second one, we need to consider five different cases, shown as (c), (d), (e), (f), (g) in Figure A3. We can simultaneously deal with (c), (d), (e) by uniformly sampling edges in AVia where the sample rate of edges can be computed by using Algorithm 10. For (f) and (g), we first uniformly sample a 3-cycle in one of Goia and G which similar Algorithm 6, and then uniformly sample one node in the other one of Goid and g The sample rate in these cases can also obtain by using Algorithm
For Toyoc and NT considering Algorithm 7 and 5 only have the linear complexity, we directly re-sample the refuting cases of I15-cyc1e and 114-cycle by running these algorithms on Gaew-
Time Complexity of Incremental Updating Algorithm. As shown in Algorithm 11, there are mainly four parts: removing the instances including the nodes in AV searching and retrieving the supporting cases of 115- : sampling the the supporting cases of II; T sampling the refuting cases of Iy-oycle and II, 1 Let [B]
denote the number of instances in the buffer B.
The first part requires O([B.aal |AV-1) computations, the second part requires O A -VVial + |Eozal miimmmmm/v// A |aas 1
new
| computations, the third part requires O( nou
AAY Vasa n4-cycle] + Votal + |oLa| + AVoia + AEora +|AVneul +IEeee
| [Eul
N4-cycle]
24

---

Published as a conference paper at ICLR 2022
Table A1: Main statistics of heterogencous graphs.
Datasets Relations (A-B)
#B
#A-B
Datasets
Relations (A-B)
#B
#A-B
User-Artist
2,101
18.746
92,834
User-Item
6.170
2,753
146,230
User-User
2,101
2,101
25,434
Item- Item-View
2,753
3,857
5,694
LastFM
Amuzon
User- Tag
2,101
12,648
186,479
Item Branndrand
2,753
334
2,753
Artist-Tag
18,746
12,648
186,479
User-User
6.170
6,170
37,958
User-Business
16.239
14.284
198.397
User-Book
13,024
22.347
598,420
User-U 16,239
16,239
158,590
User-User
13,124
13,024
169,150
Yelp
User-Ciu City 16,239
47
76,875
Douban Book
User- Geor-Group
13,024
2,936
1,189,271
Business-City
14,284
47
14,267
Beok-Author
22.347
10,805
21,907
musiness-Gentt
14,284
511
40,009
Book- Publisher
22,347
1,815
21,773
Table A2: Main statistics of knowledge graphs
Datascts
#Entitics
#Relations
#Training
#Validation
#Test
FB15k-237
14,541
237
272.115 86,835
17.535 3,304
20,466
WNI8RR 40,943
11
3.134
Extal l 74- eyyeeell)), ), the fourth part requires n(Veeul++ +/nexl [ mml)), where [:] denote the Feas
E
floor function. The overall complexity is to sum up the above computations. One can easily conclude that when the numbers of new nodes and edges are relatively much smaller than the numbers of old nodes and edges, Algorithm 1l is more efficient than re-running the subgraph retrieval algorithms on the new graph, which are the common cases in the real-world scenario.
A3.3 DETAILED FORMULATION OF IN GRAPHANGEL
As introduced in Section 3, we apply neural network (-) over each subgraph. These subgraphs can P,K
be from either target subgraph set {St ppp p== ==1 supporting subgraph set {S P.Q refuting subgraph set {Spc p=l.gg= as shown in Eq. (1). Formally, + maps each subgraph p. S or Sp.g to the corresponding graph-level representations k, ej.g or ep.a- In the implementation, adopt single layer R-GCN (Schlichtkrull al., 2018) followed by any readout function (e.g., Mean(-), Max(-)) as (-))
P.Q
Taking Sp.6 instance,
hv.,, to denote the embedding of node in the subgraph namely E S and N (v) denote the of neighbor nodes of node in Sp.t regarding relation type r. We compute hn.p.. by
hv.p.k =
Σ
W. + Wox,);
(11)
PER REN Sp.A (0)
where denote the input node features learnable node embeddings, W. denote trainable parame- ters, and a is non-linearity function such as ReLU. After updating the embedding vectors of all the nodes, we further compute e by e = Mean((hu.p.el 3),,). Computations of e and ep.q are similar.
Specifically, in the case of Pair shape, R-GCN reduces an MLP, and thus & here generally would not be worse than what an MLP could achieve.
A3.4 DETAILED FORMULATION OF & IN GRAPHANNEL
As stated Section 3, we deploy a neural network (r()) to measure the similarity s between the set of subgraphs matching MT -T, ... ITК and the set of subgraphs matching II II :...; IT: and the similarity between the set of subgraphs matching II; .I, II;, and the set of subgraphs matching U1; 11 1I.
......,,II,,,
Take the computation of + as example. We first reshape the subgraph embedding tensors ex, into matrices: E = CONCAT((e,,, = I,...,P;k P; = I,..,,K E (dx(Pxk), and similarly form et. to E E (Px(Q))) where is the hidden representation size. We then compute the affinity matrix as
A tan W.E+) E (PxK))((Xx))
(12)
where W. E dd are trainable weights. With the affinity matrix A, one possible way of computing attention is to simply maximize out the affinity, namely at [j] Max; (Ai,) ) and a [ Max; (A,)).
25

---

Published as a conference paper at ICLR 2022
Table A3: Main statistics of patterns in heterogeneous and knowledge graphs
Patterns
LastEM
Amazon
Yelp
Douban Book
FB15k-237
WNI8RR
3-cycle
29K
56K
137K
620K
519K
11 11,590K
4-cycle
28M
52M
81M
62M
51M
2,623M
average coverage of 3-hop neighhorhood
78%
72%
78%
79%
78%
68%
average coverage of 4-hop neighborhood
98%
92%
97%
99%
99%
90%
Instead of using the max activation, we follow (Lu al., 2016), considering this affinity matrix as feature and learning the attention map via following:
H W.E,, H E+
(13)
which are used to compute the attention map among E and E+ through
softmax(w, tanh H" + H A)), at sof softmaxww' ta tanttt" +
(HHA))
(14)
where W. E IRdxd and W+ E Rddd, w, E Rd and wt E Rd are the weight parameters. a* E
RPxx)) and a E (PPx)), We finally obtain the set embedding via
h = E'ta ='a
(15)
which is the weighted average of the subgraph embeddings in matrix E+ and E*. The similarity of supporting patterns is g+ h+ h². Computation of 8 similar.
A4 FURTHER ANALYSIS OF GRAPHANGEL
A4.1 LIMITATIONS OF GRAPHANGEL
In order to further analyse the limitations of GraphANGEL, first compare framework with exsiting GNN methods. As shown in Figure A2, we provide an illustrated example of nodes and edges activated and not activated in various GNN models, including GCN (Kipf & Welling, 2016), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2017), SEAL (Zhang & Chen, 2018), PPNP and APPNP (Approximate PPNP) (Klicpera et al., 2018), and our model GraphANGEL. With a limited number of GNN layers, one can easily observe that these existing approaches only involve all context within the "neighborhood"" Instead, GraphANGEL leverages the graph structure by searching and retrieving the subgraphs in the whole graph, which not only removes the limitation of neighborhood constriction but also selects pattern (i.e., logic) related information. Figure A2 depicts an illustrated example of the edges activated in GraphANGEL comparing to other GNNs, where we can see that our method can be regarded as to restrict the message passing within the subgraphs satisfying certain pre-defined patterns, (e.g., Tyy-ycle IT o.
Although from the analysis above, we can see that GraphANGEL can succeed in those cases where existing GNN models fail; however, leveraging logically-indueed graph patterns can also be limitation of GraphANGEL. especially when it is hard to find or design such graph patterns. For example, if the two nodes for the link prediction are far away from each other, the graph patterns considered in our experiments may be not able to cover the cases, and it is also hard to define what graph pattern should be, which is previously pointed out in Section 3. We argue that such cases are rare in real-world graphs as they are usually scale-free, meaning that the topological distance is usually small. The topological distance of graphs are well measured by Wiener index, and detailed theoretical description and empirical study can be found in (Dobrynin et al., 2001). Due to the high computation costs for shortest path algorithms (Floyd, 1962; Gallo & Pallottino, 1988), in this paper, instead, we calculate the fraction of 3-hop and 4-hop neighborhoods over all the nodes for every node in each dataset, average them, and report the results in Table A3, which shows that 3-hop and 4-hop neighborhoods can cover almost all the nodes in the graph. Since there is no connectivity requirement between the source and target nodes in the target pattern as shown Table 1, unlikely to fail to find at least one subgraph satisfying the target patterns.
The other limitation pointed out in Section 3 is the time complexity of Algorithm I and the storage complexity of Algorithm 8. We provide the complexity analysis in Appendix A3 and report the overall time of training and inference in Appendix A6.7. We argue that there is a recent trend in building language models (Khandelwal et al., 2019; He et al., 2021; Khandelwal et al.. 2020; Zheng et al., 2021) by searching and storing the representation vectors of neighbor nodes. Comparing to these methods, our subgraph retrieval only search, retrieve and further store the node IDs, which
26

---

Published as a conference paper at ICLR 2022
Table A4: Comparable results with baselines, where there 20% least frequent relations. See Appendix A6.1 for the full version. The numbers in brackets show the descent degree comparing to Table A4.
FB FB15k-237
WNI8RR
Models
Hit@1
H
Hit@
Hir@1
Hir@3
Hit@: 10
PLogieNet
0.209x11 1.8%)
0.342(6.81%.
0.500(4.585_J
0.341(14.3%.)
0.406(8.97%L)
0,491(8.575)
TransB
0.197(14.0%% ()
0.339(6.615% (
(.494(5.18%..
0.123(8.89%))
0.367(8.48%
0.487(8. (9%))
ConvE
0.207(12.7%.
0.324(8 (91.8.999..
0,478(4.5988]) ))
0.364(9.0098L)
0.391(1.19%L)
0.479(7.8888 889))
ComplEx
0.140)11.4%LL
(.2611).09%8..
0.375(8.54%%) (.
0.428(6.96%L)
(475(6.86%L.
MI.N
0.051(23.9%% L)
0.077(25.2%.)
0. (
0.166(13.1%.)
0.285(11.39%L)
0.333(7.76%)
RotatE
0.211(12.3%L)
0.351 ()
0.505(5.32%%_)
0.445(9.57%L) (.38))
0.529(7.38%..
RNNLogic
0.219(13.256
0.499(5.76%%.) (.353))2.5%..)
0.444(10.7%LU) 0.407(8.61%L)
0.511(8.425..)
ComplEX--N3
(.24
0.407(7.49% 0.534(.88%..) (.8%))
L)
O.456(..74%L)
0.539(7.15%.)
GralL
0.315(12.8%. (.197(11.5%.)
0,484(6.8458 84%
0.307(12.7%.)
0.387(11.%%.
(2.58)
QuatE
0.219(11.7%L)
0.355(7.145%_)
0.521(5.30%
0.400(8.75%LL
0.462(9.06%%)
(..35().06%k.)
GraphA sycle
(2243(9887%.)
0.539(3.80% (.3%4)353%%.)
1)
0.418(9.88%L)
0.549(6.935 0.465(6.42%L)
GraphANGEL44
0.215(9.96%)
0.526(3.94%%) 0.366(4.04%.)
(.221(.37%..
0.467(6.92%U)
0,5496644%%.
NGEE.
0.24%(9.62%.j L)
0.394(3.27%
(..41())
0,481(6..11%. 0.429(8.79%L)
0.557
Table A5: Comparable results with baselines, where there are 20% least frequent relations. Here we report the results in term of MR, MRR, Hit@K K (K=1,3,10).
FBI5k-237
WNISRR
Models
Hir
H
Hit 10
MR
MRR
Hit
Hit
Hir
PLogicNet
192
0.284
0.209
0.342
0.500
3891
0.378
0.341
0.406
0.491
TransE
198
0.296
0.197
0.339
0.494
3713
0,203
0.123
0.367
0.487
ConvE
266
0.295
0.207
0.324
0.478
4561
0.391
0.364
0.391
0.479
ComplEx
367
0.226
0,261
0.409
5709
0.375
0.428
0.475
MLN
2235
0.087
0.051
0.077
0.143
13056
0,225
0,166
0.285
0.333
RotatE.
200
0.302
0.211
0,351
0.505
3630
0.435
0.386
0.445
0.529
RNNLogie
263
0.302
0,219
0.333
0.499
4659
0.438
0,407
0.444
0,511
ComplEx-N3
177
0.334
0,242
0,361
0.534
3481
0.448
0.407
0,456
0,539
Grall.
230
0.281
0.197
0.315
0,484
3949
0.362
0.307
0.387
0.458
QuadE
101
0.296
0.219
0.355
0.521
2705
0.421
0.400
0.462
0,535
GruphANGEL ayyat
174
0.324
0.243
0.384
0.539
3139
0,445
0,418
0.465
0,549
GriphANGEL, 44GGL---ycs cycii
181
0.317
0.215
0,366
0.526
3169
0.450
0.421
0.467
0,549
GraphANGEL.
167
0.336
0.248
0.394
0.541
3108
0.458
0.429
0.481
0.557
are relatively much more retrieval-efffcient and storage-efffcient than searching and storing the representation vectors of nodes.
Besides the above discussions about the limitations pointed out in Section 3, we also provide the following discussions regarding the assumptions proposed in Section 2.
One of the assumptions introduced in Section 2 is that existing relations is enough to cover unseen relations by logical inference, which motivates us to not explicitly construct embeddings for the relation to predict. However, this assumption also disables GraphANGEL to consider the correlations among unseen relations. other words, it's not possible for current GraphANGEL. to incorporate unseen relations solution is to incorporate our model with EmbedRule (Yang et al., 2014) to first generate explicit embeddings for each unseen relations by EmbedRule, and then apply GraphANGEL to generate the final predictions. Considering that both EmbedRule and GraphANGEL have strong generalizability to unseen relations, it is hard to say which one plays a more important role in this case. Hence, leave it as future work.
part of the graph after actually observing them during inference. One possible
The other one of the assumptions is to bridge the graph patterns with logical rules. Therefore, GraphANGEL is capable of distinguishing different semantics of the same relation as long as the local subgraphs, hence contexts, are different.
A4.2 EXTENSIONS OF GRAPHANGEL TO HOMOGENEOUS GRAPH
One may consider that heterogeneous graph may be another potential limitation of GraphANGEL. However, we note that extending GraphANGEL to homogeneous graphs is possible with graph patterns that are not tepe-sensitive, i.e., not containing type-specific indicator operators Edge, (z. y). In other words, the graph patterns will be purely based on topology. For example, we can define 6-cycle for the graph in Figure A4(d).
27

---

Published as a conference paper at ICLR 2022
Table A6: Result comparisions with basclines on generalization setting by randomly removing 5% relations. Here report the results in term of MR, MRR, Hit@K (K=1,3,10).
FB15k-253 -37
WN18RR
Models
MR
MRR
Hit@
Hit
Hit@
MR
MRR
Hit@1
Hit@3
Hit@
pLogicNett
185
0.309
0.220
0.341
0,487
3646
0.410
0.370
0.414
0.500
TransE"
191
0.306
0.215
0.338
0.489
3614
0.209
0.230
0.378
0.499
ConvE"
268
0.292
0,213
0.320
0.450
4605
0.387
0.361
0.396
0.469
ComplEix
366
0.227
0.145
0.252
0.393
5681
0,404
0.371
0.423
0.472
ML."
2277
0.083
0.056
0.087
0.135
13288
0.220
0.168
0.273
0.306
RotatE'
189
0,317
0.227
0.353
0,500
3624
0,439
0.398
0.458
0.531
RNNLogic*
248
0.319
0.235
0.353
0,493
4865
0,456
0.419
0.472
0.523
ComplEx-N33
167
(1,350)
0.256
0.380
0.527
3625
0,466
0.418
0.475
0.551
GralL.
221
0,296
0,205
0.332
0.478
3817
0.372
0.326
0.402
0.459
QuarE"
93
0.327
0.233
0.360
0.520
2453
0.461
0.413
0.480
0.547
GraphANGEL cyyle
166
0.349
0.259
0.379
0.532
3061
0,468
0.441
0.472
0.566
GraphA NGEL cycle
173
0.335
0.229
0.365
0.525
3049
0.472
0.446
0.480
0.558
GraphANGEL
158
0.357
0.263
0.388
0.537
2948
0.482
0.450
0.492
0.572
Table A7: Result comparisions with baselines on generalization setting by randomly removing 10% relations. Here report the results in term of MR, MRR, Hi (K=1,3,10).
FBI5k-237
WN18RR
Models
MR
MRR
Hit@l 1
H
Hit@ 10
MR
MRR
Hit@
H
Hit@ 10
PLogicNet*
204
0.272
0.194
0.298
0.429
4021
0,361
0.326
0.365
0.440
Transt:
215
0.264
0.185
0.294
0.422
4057
0.180
0.109
0.324
0.430)
CouvE"
290
0.263
0.285
0.405
4982
0.348
0.324
0.356
0.421
ComplEx"
393
0.207
0,132
0.229
0,359
6102
0.369
0.3444
0.386
01.288
MLN"
2475
0.007
0.05
0.077
0,120
14436
0.194
0.143
0,241
0,270
RotatE"
207
0.279
0.199
0.307
0,437
3941
0.391
0.353
0,403
0,470
RNNI agiee
275
0.280
0,2006
0.310
114331
5469
0.395
0.364
0.408
11.452
ComplEx-N3*
187
0.304
0.224
0,331
0,462
4084
0.404
0.362
0.412
0.479
GraiL"
243
0.261
0.181
0,293
0,423
4208
0.327
0,287
0.359
0,410
Quatl
128
0.286
0,203
0,313
0,452
2731
0,402
0,360
0.417
0,477
GraphANGEL cycle
184
0.306
0,,26
0,333
0,4666
34009
0.412
0.386
0.414
0.490
GraphANGEL
192
0.293
0.200
0.319
0,460
3392
0.414
0.388
0.419
0,489
GraphANGEL
176
0,313
0.232
0.343
0.475
3259
0.423
0.398
0.434
0.504
Following the analysis above, although nodes t and v in both Figure A4(a) and (d) have similar neighborhood structures, our GraphANGEL is able to project these two source-target node pairs (i.e., (s,r,() and (v,r, ()) into different embeddings on both heterogeneous and homogeneous graphs.
A4.3 EXTENSIONS OF GRAPHIANGEL TO COMPLEX LOGIC
Another potential limitation of GraphANGEL is that the graph searching stage limits the model's capability of exploring more complex graph patterns. We admit that the graph pattern involved in our paper is simple and rudimentary, but we argue that efficient finding arbitrary graph patterns including those complex ones should be mainly investigated by graph database and pattern matching literature, which is definitively not the focus of our paper. Our key idea is general since one can pre-define any pattern search and retrieve subgraphs.
Moreover, the following corollary shows that the representations of complex logical formulas can be derived from those of simpler ones. This, to some extent, provides the theoretical support of only involving simple graph patterns (e.g., Pair, 3-cycle, 4-cycle) in the implementation.
Lemma 1. (Barceló et al., 2019) (Expressive Power on Logic Expressions of Nodes) Each First- Order Classifier with 2 variables (FOC2) can be captured by Aggregation and Combination GNN formulated as
x
c (1-1) AGG( (x) (2=/1-11111 E No(i)))) ViEV,
(16)
where AG) Easx and COM( y) (x yA+ b).
E R." be the representation vector of subgraph S., where cp = if subgraph S. matches graph pattern Ie and e, = otherwise, and ... II are sub-formulas of I1 in the order where if II is a sub-formula of II then k < l. Suppose that the representation vectors e and e. of subgraph Sr and S, matching pattern II and II respectively, are given. If takes either of the following forms:
Corollary 1. (Expressive Power on Logic Expressions of Subgraphs) Let e₂ =
TT= -1
28

---

Published as a conference paper at ICLR 2022
Table A8: Result comparisions with baselines generalization setting by randomly removing 15% relations. Here report the results in term of MR, MRR, Hit@ (K=1,3,10).
FB F515-2337
WN18RR
Models
MR
MRR
Hit
H
Hir@
MR
MRR
Hir@1
Hir603
Hit0e
pLogicNer*
230
0.222
0.158
0.245
0.351
4532
0.295
0.266
0.298
0.359
TransE"
249
0.202
0.142
0.224
0,323
4705
0.138
0.083
0.248
0.329
ConvE'
324
0.217
0.158
0.236
0.335
5568
0.288
0.268
0.294
0.348
ComplEx*
444
0.170
0.109
0.189
0.295
6891
0.303
0.282
0.317
0.351
MLN'
2633
0.065
0,044
0.229
0.107
15360
0.173
0.127
0.215
0.241
RotatE"
237
0.221
0.160
0.245
0.352
0,319
0.287
0.325
0.376
RNNL lgic"*
311
0.225
0.165
0.249
0.350
6221
0.313
0.292
0.327
0.368
ComplEx-N3*
210
0.252
0,185
0.268
0.377
4557
0,334
0.297
0.337
0.392
GraIL
275
0.213
0,147
0.239
0.347
4728
0,267
0.234
0.291
0.334
QuatE
120
0.226
0.169
0.252
0.358
3055
0.312
0.289
0.330
0.361
GraphANGEL cycle
210
0.250
0.185
0.273
0,385
3823
0.340
0.319
0.343
0.407
GraphANGELI La
216
0,243
0.165
0.264
0.381
3797
0.344
0.323
0.349
0.407
GraphANGEE.
0.259
0.192
0.351
0.324
Table A9: Result comparisions with baselines generalization setting by randomly removing 20% relations. Here we report the results in term MR, MRR, Hit@ (K=1,3.10).
FBI5K-237
WNI8RR
Models
Hi1603
Hit@
MR
Hit@
Hir
pLogicNer*
0.162
0.112
0.179
0.257
5146
0.216
0.222
0,267
TransE'
280
0.146
0.101
0.163
0.246
5285
0.100
0.072
0.200
0.260
ConvE"
366
0.162
0.104
0.178
0.247
6280
0.215
0.201
0.223
0,268
ComplEx*
501
0.128
0.078
0.142
0.226
7786
0.228
0,214
0.236
0.267
MLN'
3029
0.046
0,031
0.049
0.070
17669
0.121
0.092
0.154
0.178
RotatE"
269
0.176
0.121
0.187
0.271
48499
0.218
0.238
0.260
0.296
RNNLogic**
349
0.151
0.124
0.172
0.240
6728
0.248
0.244
0.260
0.281
ComplEx-N3*
232
0,208
0,142
0.208
0.289
5064
0,259
0,250
0.269
0,311
Grall."
304
0.173
0.125
0.185
0,263
5315
0.212
0.195
0.222
0,267
QuatE
137
0.173
0.127
0.190
0.282
3702
0,248
0.255
0.308
GrahhNGELLs-eyn
223
0.225
0.168
0,230
0.333
4098
0.297
0.277
0.291
0.329
GraphANGEL
227
0.206
0,147
0.222
0.328
4146
0.297
0,278
0.291
0.326
GraphANGHI.
208
0.227
0.173
0.238
0.337
3956
0.305
0.284
0.299
0.334
II = II A II
IT IT TT
Then there exists W E RxP, WV E RXP,, and b E R.,, such that
e, min(max (W + W + b, 1)
is representation vector of subgraph S₂ matching II.
Proof.
The entries of the p-th columns of W W and b depend on the formulas of 1 as follows.
if TTg. I then W =1 1.
if II
II A II then W 1, Wr 1, and by -1 ip and by 0.
if IT IT V IT then W 1, W
ip if II -II, then W ip = -1 and b 1.
All other values in the p-th columns of W W and b are O. Our proof follows the proof of Lemma in (Barceló et al., 2019). The only differences are: (1) the input of the basic logic formula in (Barceló et al., 2019) is nodes while in our paper is subgraph, thus the basic logic in (Barceló et al., 2019) is the color of nodes (i.e., Col(.)), but in setting is the graph pattern for subgraphs; (2) only involve the basic logical operators A, V and - in our paper.
Besides the prior literature (Barceló et al., 2019) studying the theoretical expressive power of GNNs, our work is also kind of related to a thread of works (Minervini et al., 2020a;b; Weber et al., 2019) on Neural Theorem Provers, where they first assume template rules and then find which relations satisfy them. In contrast, patterns and use the subgraphs to represent the rules. This intuition enables our model empowered by the expressive power of GNNs, and also allows our work to identify new relation types.
work bridges the connection between logical expression and graph
29

---

Published as a conference paper at ICLR 2022
Table A10: Result comparisions with baselines on generalization setting by randomly adding 5% relations. Here we report the results in terms of MR, MRR. Hit@k K (K=1,3,10).
FB15k-253 237
WN18RR
Models
MR
MRR
Hit@1
H
Hit@
MR
MRR
Hit@!
Hit@3
Hit@
pLogieNet"
187
0.305
0.218
0.337
0,482
3680
0.405
0.366
0.410
0.494
TransE"
197
0.296
0.208
0.330
0.474
3716
0.202
0.122
0.364
0.483
ConvE"
275
0.282
0.206
0.309
0.435
4731
0.374
0.348
0.382
0.452
ComplEix
366
0.227
0.145
0,253
0.393
5681
0.404
0.377
0.423
0.469
ML."
2277
0.083
0.056
0.087
0.136
13281
0.220
0.162
0.273
0.306
RotatE'
191
0
0.222
0.345
0.492
3590
0.438
0.398
0.452
0.526
RNNLogic*
252
0.315
0.231
0.347
0,484
5019
0,442
0,411
0.457
0.513
ComplEx-N33
171
01,343
0.253
0.370
0,516
3728
0,369
0.323
0.405
0.462
GralL.
223
0,293
0.213
0.332
0.475
3842
0,368
0.323
0.399
0.457
QuarE"
95
0.323
0.231
0.355
0.515
2481
0.458
0.411
0.473
0.543
GraphANGEL cyycle
170
0.340
0.251
0.373
0.525
3104
0,458
0.434
0,465
0.555
GraphA NopphANGEL,. cycle
176
0..39
0.225
0.354
0.514
31099
0.461
0.434
0.470
0.552
GraphANGEL
161
0.349
0.258
0.382
0.527
3004
0.471
0.440
0.480
0.558
Table All: Result comparisons with different GNNs as subgraph embedding methods (i.e., 4) on heterogeneous recommendation task.
LastFM
Yelp
Amazon
Douban Book
Models
AUC
ACC
F1
AUC
ACC
F1
AUC
ACC
F1
AUC
ACC
F1
GraphANGEL
0,860
0.832
0.825
0.918
0.846
0.835
0.843
0.758
0.745
0.917
0.843
0.831
GraphANGEL
0.873
0.843
0.830
0.927
0,855
0.843
0.854
0.767
0.752
0,923
0.849
0.838
GraphANGEI ocN
0.900
0.861
0.859
0.934
0.870
0.858
0.870
0.781
0.781
0.941
0.864
0.859
GraphANGEI,
0.906
0.864
0,861
0.933
0.870
0.856
0.874
0.782
0.783
0.940
0.865
0.858
GraphANGEL
72
0.901
0.860
0,862
0.934
0.871
0.857
0.873
0.784
0.783
0.937
0.860
0.857
22 ccN
GraphANGEL GAT
0.907
0.861
0.862
0.933
0.871
0.854
0.874
0.784
0.785
0,940
0.863
0.859
A5 DETAILED EXPERIMENTAL SETTINGS
A5.1 DATASET STATISTICS
The statistics of the datasets of heterogeneous graph based recommendation and knowledge graph completion used in our paper are displayed in Table A1 and Table A2, respectively. We also report the statistic of the patterns used in the datasets in Table A3, which can be regarded as the supporting evidence of using these patterns, since it is unlikely to fail to find at least one subgraph satisfying these patterns.
A5.2 BASELINES
For the baseline methods, we employ these baseline methods based on Deep Graph Library (DGL) (Wang et al., 2019a) following their original setting or directly use their original implementations: (1) HetGNN (Zhang et al., 2019a) is a unified framework that jointly considers heterogeneous structured information as well as heterogeneous content information.
(2) HAN (Wang et al., 2019b) is a hicrarchical attention mechanism designed on heterogencous graph to capture node-level and semantic-level information. (3) TAHIN (Bi et al., 2020) is cross domain model from both source and target domain, which is then incorporated with three-level attention aggregations to get node representation. (4) HGT (Hu et al., 2020) is heterogeneous graph transformer architecture that characterizes the heterogeneous attention over each relation. (5) R-GCN (Schlichtkrull et al., 2018) combines graph neural networks with factorization models for link prediction. (6) PLogicNet (Qu & Tang, 2019) is an EM-based algorithm that simultaneously trains rule generator as well as reasoning predictor with logic rules. (7) TransE (Bordes et al., 2013) is a translation- based relation prediction model. (8) ConvE (Dettmers et al., 2018) is convolution based relation prediction model. (9) ComplEx (Trouillon et al., 2016) uses the composition of complex embeddings to handle large variety of binary relations. (10) MLN (Singla & Domingos, 2005) leverages domain knowledge to predict relations. (11) RotatE (Sun et al., 2019a) is a rotation-
relation prediction model. (12) RNNLogic (Qu et al., 2020) defines the joint distribution of all possible triplets by using Markov logic network which can be efficiently optimized with the variational EM algorithm. (13) ComplEx-N3 (Lacroix et al., 2018) introduces regularizer based on tensor nuclear p-norms for relation prediction. (14) GraIL (Teru et al., 2020) reasons over local subgraph structures and holds a strong inductive bias to learn entity-independent relational semantics. (15) QuatE (Zhang et al., 2019b) introduces
30

---

Published as a conference paper at ICLR 2022
Table A12: Result comparisons with different GNNs subgraph embedding methods (i.c., b) knowledge graph completion task.
15k-237
WNISRR
Models
MR
MRR
Hit@1
Hit
Hir@
MR
MRR
Hir@1
Hir@3
Hit@ 10
GraphANGEL.22
236
0.324
0.222
0.356
0.524
3476
0.410
0.367
0.445
0.511
GraphANGEL
pay
230
0.328
0.226
0,361
0.528
3484
0.402
0.365
0.446
0,510
GraphANGEL
151
0.374
0.275
0,408
0.564
2834
0.504
0.470
0.515
0.598
GraphA 41
141
0.376
0.276
0.410
0.564
2836
0.505
0.470
0.514
0.601
GraphANGEL
141
0.373
0.275
0.408
0.564
2829
0.505
0.470
0.514
0.597
GraphANGEII DAT
22
153
0.377
0.275
0.408
0.562
2821
0.506
0.469
0.513
0.598
Table A13: Comparable results with baselines on robustness setting by randomly adding 5% noises. See Appendix A6.5 for detailed configuration on heterogeneous graph recommendation task.
Models
LastFM
Yelp
Amazon
Douban Book
AUC
ACC
F1
AUC
ACC
F1
AUC
ACC
F1
AUC
ACC
F1
HeGGNN
0.7756
0.7924
0.6984
0.8897
0.8104
0.7984
0.7532
0.6932
0.6962
0.8511
0.7723
0.7701
HAN
0.8736
0.8186
0.8134
0.8964
0.8313
0.8257
0,8315
0.7543
0.7424
0,9052
0.8335
0.8286
TAIIN
0.8724
0.8323
0.8187
0.8903
0.8334
0.8226
0.8344
0.7553
0.7512
0,9082
0.8354
0.8223
HGT
0.8212
0,7749
0,77188
0,8784
0.8183
0.8142
0.6962
0.6333
0.6150
0.8922
0.8171
0.8032
R-GCN
0,8355
0.8225
0.8173
0.8916
0.8258
0.8156
0.7969
0.7258
0.7218
0,9019
0.8247
0,8107
GrahANGEL, sycle
0.8808
0.8392
0.8343
0.9036
0.8379
0.8394
0.8490
0,7680
0.7644
0.9126
0.8392
0.8360
GmphANGELL
0.8853
0.8411
0,8365
0.9090
0.8403
0.8418
0.8502
0.7650
0.7623
0,9131
0.8391
0.8277
GraphANGEL
0,8808
0,8323
0,8302
0,90122
0.8310
0.8376
0,8462
0.7620
0.7582
0.9084
0.8357
0.8235
GrapbANGEL
0.8901
0.8511
0.8492
0.9230
0.8602
0.8481
0.8600
0.7720
0.7710
0,9301
0.8544
0.8492
quaternion embeddings, whose framework can be regarded as a generalization of ComplEx on hypercomplex space while offering better geometrical interpretations.
A5.3 PAPPE-PPRAMMTERS
We keep all hyper-parameter settings in their original implementations, except the following ones for fair comparisons. All models involving GNN layers are set to have similar layers (2 or 3 layers, depending on the performance) and are trained for the same number of epochs. We fix model configurations across all experiments. For all baseline GNN models and GraphANGEL, the dimension size of the embeddings is set to 128, and the learning rate space is {0.001, 0.0001 ]. The dropout of input is set to 0.6, of edge is set to 0.3. Notably, the results reported in our paper are comparable with those in their original papers. the implementation of subgraph retrieval, the graph patterns in the implementation are reported in Table 2, and we search and retrieve all the supporting cases of 3-cycle and sample the same number of the supporting cases of 4-cycle, whose numbers are reported in Table A3. The number of the refuting cases of 3-cycle and 4-cycle is twice of the number of the supporting cases. The number of target subgraphs K is set as 32 and the number of analogy subgraphs Q (for both supporting and refuting patterns) is set 64. The experimental comparisons are conducted with 10 different random seeds.
We report the main statistics of patterns in each datasets in Table A3, which includes the numbers of 3-cycles and 4-cycles. We further report the buffer sizes of each dataset as follows, which is in proportion to the numbers of the patterns. The buffer sizes of the supporting subgraphs of 3-cycles are: 4.5MB for LastFM, 8. 8.7MB for Amazon, 21 ..2MB for Yelp, 96.2MB for Douban Book, 80. 50. for 237, 161 161.4MB for WNISRR where we sample twice number of the supporting subgraphs of 3-cycles in FB15k 15k-237 for WNI8RR. And, the buffer size of the supporting subgraphs of 4-cycles, and the refuting subgraphs of 3-cycles and 4-cycles can be easily derived by the above buffer size, since we store the node IDs into the buffer.
A5.44 HARDWARE, SETTINGS
The models are trained under the same hardware settings with an Amazon EC2 p3.8x xaage instance! where the GPU processor is NVIDIA Tesla V100 processor and the CPU processor Intel Xeon ES-2686 v4 (Broadwell) processor.
Detailed setting of AWS E2 instance can be found at https:/ //aws ama zoazon. com/ec2/ mnstance-types/2nne
31

---

Published as a conference paper at ICLR 2022
Table A14: Comparable results with basclines robustness setting by randomly adding 5% noises on knowledge graph completion task. See Appendix A6.5 for detailed configuration.
FBI55-237
WNI8RR
Models
MR
MRR
Hir
H
Hit 10
MR
MRR
Hit
Hit6f3
Hir@ 10
PLogicNet
180
0.318
0.229
0.350
0.498
3532
0.427
0,380
0.420
0,518
Thansil
187
0.316
0.218
01,346
0.499
3534
0.217
0.231
0.380
0.512
ConvE
253
0.286
0.229
0.326
0.478
4351
0.401
0.378
0.420
0.484
ComplEx
345
0.238
0.147
0.267
0.404
5452
0.420
0.394
0.441
0.494
MLN
2143
0.088
0,060
0.094
0.525
12667
0.236
0.172
0.285
0.334
RotatE.
184
0.325
0.233
0.361
0.518
3531
0.445
0.404
0.470
0,552
RNNLogie
240
0.324
0.243
0.366
0.502
4768
0,468
0,453
0.484
0.534
ComplEx-NN
163
0.358
0.264
0
0.550
3535
0,482
0.454
0,489
0.575
Grall..
214
0.310
0.2115
0.324
0.480
3754
0.386
0.339
0.419
0.486
QuatE
0.330
0.235
0.367
0.531
2410
0.471
0.422
0.489
0,557
GraphANGELa--re -eya
163
0.356
0.265
0.385
0.550
2968
0,482
0,457
0.486
0,580
GraphANGEL
168
0.345
0.230
0.372
0.530
3002
0,482
0.453
0,494
0.574
GraphANGEL.
153
0.363
0.267
0.390
0.552
2910
0.489
0.460
0.495
0.581
A6 ADDITIONAL RESULTS
1 ADDITIONAL RESULTS OF STANDARD TASK
We show the results of comparisons between GraphANGEL against the baseline methods testing with 20% least frequent relations in terms of MR, MRR, Hit@1 1, Hir@3 and Hit@ 10 in Table A5.
A6.2 ADDITIONAL RESULTS GENERALIZATION STUDY
Table A6 shows the results of performance in terms of MR, MRR, H (K=1,3,10) after randomly removing 5% relations. We also report the results after randomly dropping 10%, 15% and 20% in Ta- bles A7, A8 and A9. In addition to randomly dropping the relations, also evaluate the performance when we randomly adding 5% relations by combining the existing relations through Composition Rules, Inverse Rules, Symmetric Rules, Subrelation Rules discussed in (Qu & Tang, 2019). The results are reported in Table A10. These experimental results verify that GraphANGEL is significantly less affected by dropping or adding relations, which demonstrates the better generalizability of our model to unseen relation types against these state-of-the-ee methods.
A6.3 ADDITIONAL RESULTS OF HEAT MAP
We show the detailed attention heat map of Douban Book dataset in Figure A5 and Figure 5 in the main text a simplification of this figure. One can see that based on the heat map, we can not only have a global view for each graph pattern, but also see the importance of each subgraph.
Specifically, Figure A5 visualizes the attention heat map between target subgraphs and supporting subgraphs when predicting relations between users and books. The rows represent the supporting subgraphs while the columns represent the target subgraphs. We denote each subgraph as a tuple of node IDs, e.g., S (N107, 611, a33, 612). Each cell represents the similarity between target subgraph (at the top) and a supporting subgraph (at bottom). The color of each cell shows the attention weight for corresponding pair of supporting and target subgraphs. We can observe that the deep color of the cell located at the interaction of Sž and S indicates more similarity. We can see from the figure that the cells with darkest color have both target subgraph and supporting subgraph as (u., b., a. b.), which indicates a subgraph with User Book - Author Book pattern, meaning that this particular pattern is more influential in predicting User Book relation. Notably, this result reveals a simple logic User A Book A Author A Book = User A Book indicating a simple factor that the users are likely to interested in the book sharing the same authors with his reading ones. Hence, our method can intuitively be regarded as the logical collaborative filtering technique working on graph. Similarly, we can find that 3-cycle pattern (Person) - Impersonate -1 - (Person) A (Person)- - Nationality- (Nation) = (Person) - -atii aonality---lllll (Nation) plays an important role in FB15k-237 dataset, where inverse relations are denoted with a superseript
A6.4 ADDITIONAL. RESULTS OF ABLATION STUDY OF SUBGRAPH EMBEDDING METHODS
In Section 3, we use R-GCN (Schlichtkrull et al., 2018) with single layer (denoted as GraphANGEL +1 scn) as example of $. In this subsection, we further investigate the effect of +
32

---

Published as a conference paper at ICLR 2022
20
(roe))
[Maze A1.
(eser Ys.
Co-Attention Between Target and Supporting Subgraphs
(101220012
1oazz//1
0.14
$32
Masas, Dizee Rgg Paza
(Hsses Bazu
P2i Poas
(11a7.1110 yr.
0.12
R1zz. / P121
$33
(igzaellape) Liza Noza
Moza s2
(1ao Maza
Wzo. Bgg.
Ligo Rara
0.10
(
$4
Manalou Bas
(MzuM
(ugo
0.08
Brscs)
Prass Bgy Argz
P1012-212
Sg5
Moosa Pags
0.06
Mag. Aass
Ugg. Reps
Mag.
Mags.aas
MMazn (11))
Gagguby
Agg.
0.04
$
Mazo
Maggallee by
MMasashyen
(Mazo.b11.)) 92g..b2
0.02
y2.b2z
S37
(loss Menon Waggsbaa
(Maaen Magze
Mlose Mag00 (Magp.
0.00
Figure A5: Illustrations of generated heat map of attention scores. While Figure can provide global view for each graph pattern, this figure can the importance of detailed subgraphs.
by applying different GNNs including GCN (Kipf & Welling, 2016) (denoted as GraphANGEL
GAT (Hamilton et al., 2017) (denoted as GraphANGELair> R-GAT (Busbridge et al., 2019) (denoted as GraphA x1 GAT). We do not choose knowledge embedding based methods including TransE (Bordes et al., 2013), RotatE (Sun al., 2019a), ComplEx (Trouillon al., 2016), as these approaches sntervisions/rrddennn on the subgraph embeddings, which require sig-
need to introduce additional nificant modifications on the framework of GraphANGEL. We do not change any other settings of GraphANGEL for fair comparison, and report the results on heterogeneous recommendation task and knowledge graph completion task in Tables All and A12 respectively. Results shows that there are slight differences between GraphANGEL R- acn and GraphANGEL dar One possible explanation is that as our retrieved subgraphs only includes few nodes (e.g. 2,3,or nodes), there is no requirement of GraphANGEL. to mine some complex structure (e.g., high-order neighborhood).
We further study the impact of using the multiple layers of GNNs. We establish a series of variants using two layers of of R-GCN and R-GAT, denoted as GraphANGEL Gox and GraphANGEL GAT Results reported Tables All and A12 show that there are only slight differences when comparing to GraphANGEL g-oo and GraphANGEL R- GAT which is consistent with the above explanation.
A6.5 ADDITIONAL RESULTS OF EFFECT OF NOISY GRAPHS
In order to further investigate the robustness of GraphANGEL, we randomly generate some noises and add them into the training graphs. Concretely, for heterogeneous graphs and knowledge graphs shown in Tables A1 and A2, we randomly change the source or target node of cach triplet (s, r, t) with probability 5%. Since the heterogeneous graphs have the node types, our changes made by replacing the current source or target node with a randomly sampled node in the same node type. We compare model with all the baselines and report the results for heterogeneous graph recommendation and knowledge graph completion tasks in Tables A13 and A14. These results show that our method can consistently outperform these baseline methods, sometimes, even are less influenced by the noises. One explanation is that if we introduce noises in the labels then the learnable subgraph embeddings s and will simultancously be influenced by the noises. These influences might be counteracted according to Eq. (3).
A6.6 ADDITIONAL. RESULTS OF ABLATION STUDY OF BUFFER SIZE
We establish an ablation study to investigate the impact of the buffer size B in Algorithm 8. We here focus on the number of the subgraphs following 113-cycle and 1lg-cycle. From Appendix A3,
know that we search and sample N₂ Na-cycle subgraphs following TT and I - where
33

---

Published as a conference paper at ICLR 2022
Amezon
Douban Book
Amazon
Douben Book
1.00
637
5.1
0.79
6:01
577
0.70
0.06
6:6
631
Number of Supporting 3-cycles
Number Supporting 3-cycles
Number Supporting 4-cycles
Number Supporting 4-cycles
Figure A6: Performance change GraphANGEL with different of buffer in term ACC and AUC. where we investigate the performance of GraphANGEL using 0.25, 0.5, 0.75 number of supporting instance in 3-cycles (i.c., IT -yz-cycoe) or 0.25, 0.5, 0.75 number of supporting instance in 4-cycles (i.c., IT aeyycc on Amazon and Douban Book datasets.
Ns-cycle is the number of subgraphs following 113-cyete We reduce the number of either subgraphs following I1 -ygeyete II- eycle- Results reported in Figure A6 shows that once the numbers of supporting 3-cycles and 4-cycles surpass 0.5-N3 0.5-N3-cyete e-cella and 0.75-N, 105-NNa-yctt respectively, there will be significant difference further increase the buffer size.
(a) Amazon
(b) FB15k-277
20000
1000
Training Time (second)
10000
R-GC'
80
Trahning Time (sncond)
17500
800
(second)
15000
8000
GropAAGELL Aoocl
-60
12500
600
6000
10000
400
4000
5000
2500
Training
Inference
Training
Inference
Figure A7: Time comparisons of GraphANGEL against bascline models on Amazon dataset in (a) and on FB15k-237 dataset in (b).
A6.7 ADDITIONAL RESULTS TIME COMPLEXITY
We first compare the time complexity of GraphANGEL in term of both training and inference times on Amazon dataset against aforementioned baseline methods. Result in Figure A7(a) reveals that GraphANGEL is more efficient than HGT and HAN in term of training time and is more efficient than R-GCN and HGT in term of inference time. One possible explanation that HAN, HGT, and R-GCN contain the whole graph, which is much more complex than sampled subgraphs. We further evaluate the training and inference time GraphANGEL. against the baselines on FB 15k-237 dataset and report the results Figure A7(b). As the prevailing methods on knowledge completion task mainly based on either on translation (Bordes et al., 2013) or rotation (Sun et al., 2019a) assumptions regardless of the graph structure, they are naturally more efficient than GNN based relation prediction models. We do note that our efficiency is comparable against other graph neural networks (i.e., R-GCN) which have also been tried on knowledge graphs.
34

---

Published as a conference paper at ICLR 2022
Algorithm 11: Incremental Updating Algorithm for B
B
for each v E AV- do
Remove all the instances including v in B. end
# Following is Search and Retrieval for I1 eyyee in Ag
Search, retrieve and store the instances following eyg-cycle in A using Algorithm 2 or # Followings is Search and Retrieval for I1 cycle in (a) Shape
Search, retrieve and store the instances following 1 g-ecle in (a) shape using Algorithm 9, Followings is Search and Retrieval for TT - in (b) Shape
for each u E Vold do for each (u, w) E AV+. new do if (u, v)) E A and (u, w) E A then Add (u, v, w) into B.
end
end end
# Following is Uniform Sampling for IT To in Ag
Sample and store [ [aasl -l- instances following II cyete in ACtiu using Algorithm 5.
# Following is Uniform Sampling for - in (c), (d), (e) Shapes
Compute sample rate PAgila
adge
by running purple part in Algorithm on AG
for i + to |AEtt Rg-cycl- do Sample (u, v) A with probability
Pagt edge edge
Sample (w. a)) E A with probability Pagt.
if ((u, w/ E &o2a U AEt and (v,x) Eoia U AE or (u,, w) E Eord U A and (u, z) E Eold A then
Add (u.v, w, x) into B. end end
Following is Uniform Sampling for II in (f), (g) Shapes edge Compute sample rate Pstna and prodo by running blue part in Algorithm 10 Gold and AG+ nev.
for i + 1 to Feuul2 n4-cycla] do Sample AV* with probability prode..
Sample Voia with probability prode Uniformly sample two different neighbor nodes u, w E Void of v.
if (u, AEt and (w, æ²) A then
Add (u, c x) into B. end
end
for i +- 1 to
[Eau ng-cycle] do
Sample x Voia with probability mode
Sample AV+ nex with probability y hode
AV+ Uniformly sample two different neighbor nodes u, Dew of if (u, x)) E E and (w, E E then Add (u, e, w, x) into B.
end
end
# Following is Uniform Sampling for TI--yycle and I1 Ilg-cycle E 3 [atal F4 myccyel and [ [ eycyycee refuting cases of I5-- and U1 - from Goez using Algorithms 7 and 5 with linear computation costs.
Re-sample and store
35


Reviews:
[{"review_id": "lXe_66Cgy5", "reviewer": "Reviewer_y1cR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Strengths:\n\n1) The proposed method doesn’t require learning explicitly embeddings for the relation types, which makes it quite effective. The ability to generalize to unseen relation types has been shown with an exhaustive set of experiments.\n\n2) The gains provided in all the tables are very significant and the results in Tables 5 and 6 are particularly interesting and very substantial. \n\n3) The monotonic increase in the performance reported in section 5.3 clearly demonstrates the importance of the number of the subgraphs that are used.\n\n4) The attention heatmaps in Figure 5 are indeed very informative and interesting. Figures 5 and A4 clearly support the authors’ claim about their method being explainable, further aiding its utility.\n\n5) The authors have also put some effort on providing the extension of their method to complex logic in section A 4.3. It will be interesting to see some empirical work for that in the future. Although trivial, they have also mentioned the extension to homogeneous graphs.\n\n6) The authors also provide various search and sampling algorithms while also noting the proofs of correctness and performing the complexity analysis for all of them. The proposed techniques are certainly useful in practice, at least for sparse graphs such as Wordnet. \n\n\nWeaknesses (and questions for authors):\n\n1) Is it possible for the authors to compare against strong baselines methods for knowledge graph completion such [1] and [2]? I understand that the publication time for [1] is within 3 months of this submission, but it might be good to provide the results on at least one of the knowledge graph datasets to ensure completeness.\n\n2) The authors’ claim about bridging logical expressions and graph patterns based on the two intuitions provided at the beginning of section 2 are indeed very sound and they have provided some examples in the subsequent paragraphs. Can they also provide reference to some relevant works that have explicitly identified such patterns?\n\n3) Although the computation of 3-cycles and 4-cycles as a preprocessing step and storing explicitly is reasonable, this can limit the practical usage of this method, for which the authors suggest the use of Buffer B in section A 3.1. Can the authors provide more experimental details regarding the use of buffer and its size on various datasets? Can they also provide some statistics on the number of 3-cycles and 4-cycles generated for the benchmark graphs? An ablation study for the total number of cycles used in the training data could also be very useful.\n\n4) Is there any specific reason that the authors used R-GCN? From Equation 11, it seems that some learnable parameters are required for the relation types present in training data, thus I expect that one can use any recent Graph based method proposed to operate on KGs. Can they also elaborate on the reason as to why a single layer has been used?\n\n5) Can the authors also elaborate whether they have considered the graphs as directed or undirected? All the algorithms seem to be operating on undirected graphs. If that is the case, can they explain the reason to do so? The direction of the edges is extremely important in the benchmark graphs since it has explicit meaning. (If they have considered directed graphs, please ignore this point)\n\n6) Can the authors also provide some more empirical runtime details, particularly on the Freebase dataset?\n\n7) The authors mention this statement - “We note that such cases are rare in real-world graphs as they are usually scale-free, meaning that the topological distance is usually small.” at the end of section A 4.1 . Can they provide references to some relevant works that have explicitly studied this? At least for real-world knowledge graph completion tasks, the nodes can definitely be far away, with the hop distance (shortest path length) of the order of the diameter of the training graph.\n\n[1] Zhu, Zhaocheng, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. \"Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction.\" arXiv preprint arXiv:2106.06935 (2021).\n\n[2] Zhang, Shuai, Yi Tay, Lina Yao, and Qi Liu. \"Quaternion knowledge graph embeddings.\" arXiv preprint arXiv:1904.10281 (2019)\n", "summary_of_the_paper": "The authors propose a framework, which they refer to as GraphANGEL, for inductive relation prediction in heterogeneous graphs. One of the main and inarguably the most important aspects of this work is modeling the task of relation prediction as a subgraph matching problem. Since the method doesn’t require learning embeddings for relation types explicitly, it can easily generalize to new relations. Furthermore, since the proposed method requires generation of explicit graph patterns that represent logical rules, the method becomes inherently explainable. The authors further provide various algorithms for searching and retrieving subgraphs from the training data with appropriate proofs and runtime complexity wherever required. Exhaustive experiments have been conducted to demonstrate the efficacy of the proposed approach and the results provided in the main paper as well as the appendix thoroughly support the authors’ claims. The heatmaps provided in section 5.5 and A 6.3 further aid the claims about explainability and are indeed very interesting.\n\nFormulating the problems of link and relation prediction as subgraph matching have been extensively studied in the literature and there is conclusive evidence that such approaches work very well.\n\nIt is also very informative that the authors talk about the limitations of their work in section A 4.1 . \n", "summary_of_the_review": "Overall the paper is very well written, contains extensive experiments supporting their claims and proofs of correctness as well as runtime complexity analysis for all proposed algorithms, ensuring completeness. It will be very helpful if the authors can further address some of the  questions and weaknesses as pointed out in the previous subsection of this review, particularly the inclusion of some recent and strong knowledge graph completion baselines. I look forward to the rebuttal and am willing to improve the score if the authors can provide a satisfactory response. \n\nAfter addressing these minor pointers, I believe that the contributions will be worth presenting at the conference. I additionally support the simplicity of the proposed approach and given its versatility, it can be plugged with various types of  deep learning based components used for subgraph embedding computation and similarity computation.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "eJXCbYPpgXt", "reviewer": "Reviewer_1Ki2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "**Strengths**\n1. The core idea is deep rooted in real world applications and combines the expressive power of GNNs and raw graph pattern matching. \n2. The method is independent of the relation type and thus can be applied for *unseen* relations which makes the method more generalizable. \n3. Authors do extensice experimentation to prove the effectiveness of their method on heterogeneous graph recommendation datasets and knowledge graph relation prediction. Moreover to support the claims of generalization to unseen relation types, author conduct a separate experimentation which shows decent improvements over baseline methods.\n4. Paper is well written and authors do a good job of explaining their method to the reader.\n\n**Weaknesses/Questions**\n1. Since the method relies on retrieval of subgraphs, the time complexity can take a hit. However, to resolve this issue authors limit the subgraph computation to pairs, 3-cycles and 4 cycles and precompute all such subgraphs and store on disk. This can result in high storage requirements.\n2. While the gains in inductive setting are decent, the gains for knowledge graph completion and heterogeneous graph recommendation tasks are marginal. \n\nQ. How are the ties resolved while ranking for knowledge graph completion task? Please consider mentioning this in the main text. \nFor more reference please take a look at Section 4 of [this](https://drive.google.com/file/d/1WhTapGnWM8u50E8vCcx_acGBEngUBu-i/view) paper. ", "summary_of_the_paper": "This paper introduces a new framework for relation prediction by using \"analogy\" subgraphs. Authors extract some analogy subgraphs ( similar in shape ) containing the pair of source (*s*) and target (*t*) nodes, and compare them against other subgraphs sharing similar shapes. The method works by first storing base patterns (limited to pairs, 3-cycles and 4-cycles to manage complexity) and building three sets of subgraphs on top of each of these base patterns, *target*, *supporting* and *refuting* patterns for a given triplet *<s, r, t>*. Authors then sample *K* target subgraphs, and *Q* subgraphs each from *supporting* and *refuting*. This sampling is done for all *P* base patterns. These sets of subgraphs are then converted into a single vector representation using GNNs. The final prediction is derived by calculating the distance between embeddings for *target* and *supporting* (denoted as *s+*) and, *target* and *refuting* (denoted as *s-*) and feeding these numbers to a neural network, treating the final relation prediction problem as a binary classification problem.", "summary_of_the_review": "Authors propose a new relation prediction framework *GraphANGEL* which is generalizable and combines GNNs and graph pattern matching. The experimentation done in the paper is extensive and shows the effectiveness of the method. \nOverall I feel the authors make a significant contribution to the relation prediction literature and I would like to recommend **accepting** this work. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "d7kztLrfGCV", "reviewer": "Reviewer_jqL2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Pros:\n- The approach presented is simple and based on intuition from the real world.\n- The approach is inductive and thus can be applied to unseen relations at inference time.\n- Comparing multiple target subgraphs with multiple supporting/refuting subgraphs allows the use of non-local explicit structure at the prediction time. \n- Proposes efficient methods for pre-computing sub-graphs with 3-cycle and 4-cycle patterns.\n- The comparison of the target with the supporting/refuting subgraphs is done using a co-attention module that allows for interpretability which can be important in certain domains like the medical domain.\n- The ablation analysis is quite thorough supporting the design choices of their model.\n\nCons:\n- While the approach is general, but the experiments are conducted by using patterns of up to 4-cycle which can be a problem if the target nodes s and t are quite far in the graph and/or the graph is disconnected. This is also pointed out by the authors.\n- Because there is no explicit embedding for relation, it will not be possible to incorporate unseen relations as a part of the graph after actually observing them during inference. For instance, r1_unseen (e.g. basedin), r2_unseen(e.g. live) are 2 unseen relations observed during inference. Knowing r1_unseen can help with r2_unseen as pointed out by authors as well in the paper. As far as I know, there is no way for RGCN to incorporate the new relationship without explicitly re-training, it will miss out on using r1_unseen for predicting about r2_unseen. While having an explicit embedding/matrix for relation would actually be useful in that setting.\n- The results are marginally better and the error bars (from multiple runs) are not shown which makes it harder to say if the difference is statistically significant. It would be great to have that just for the models in the main table.\n- The approach precomputes the subgraphs which would be a single-time operation in a static graph. The authors also allude to this fact in Limitations on page 5.  But this may not be the case for heterogeneous recommendation settings, where I would expect that the graph to evolve very fast. In that scenario, I am concerned that there is a need to precompute the subgraphs again?\n", "summary_of_the_paper": "The paper proposes a novel inductive relation prediction framework called ANalogy SubGraph Embedding Learning (GraphANGEL). The core idea of the approach is to compare a target subgraph (containing the nodes s and t between which the relation r is to be predicted) with other subgraphs in the graph that supports/refute the presence of the relationship. If the target subgraph is closer to the supporting pattern/subgraph then the target relationship r should also exist or vice versa. The subgraphs are constructed using 3 graph patterns namely pairs, 3-cycles, and 4-cycles.  The proposed approach is inductive as the approach doesn’t build an explicit embedding for relationships (unlike existing approaches) for prediction but masks the relationship edge while computing the subgraph representations for the supporting subgraphs. The paper proposes to precompute patterns like pair, 3-cycle, and 4-cycle and their corresponding subgraphs which are then retrieved during training and inference to get the target, supporting and refuting subgraphs. Considering specifically pairs, 3-cycles, and 4-cycles helps to keep the approach tractable. The approach is shown to consistently outperform existing approaches on heterogeneous recommendation and Knowledge Graph Completion (in both inductive and transductive settings for relation prediction) tasks.", "summary_of_the_review": "8: accept, Good Paper\n\nEven though the proposed approach is simple, inductive, and is shown to be better than considered baselines, the gains seem to be marginal especially without error bars. Even in the inductive setting (i.e. section 5.4), the proposed approach doesn’t provide a significant boost compared to the baselines especially compared to CompEx-N3* baseline. For other reasons for my score please refer to the Cons section above. \n\nBut, I think the proposed approach is interesting because of its simplicity and the problem it is trying to solve and I am on the fence leaning towards a weak acceptance. But, I am willing to raise my score if the authors can provide error bars that will validate that the results are statistically significant. I also think that the authors should add a discussion about how to scale the method when the graph changes especially in the recommendation setting. Is there a need to resample the subgraphs which means that this computation cost is no longer one-time and should be reported as a part of at least the training time imho (i.e in fig. A5)? If not, then this should strengthen the contributions of the paper and discussed (in Appendix perhaps if there is no space). \n\nAnother interesting analysis to have is to see the performance of GraphANGEL based on the count of relations that are added for generalization study in section 5.4. Maybe, there is an interesting pattern there.  Even going a step further, instead of splitting the relations randomly split them based on the frequency of occurrence of the relation. I think that these additions will make this paper more impactful. \n\nEdit: Updated after reading response from the authors.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "PvNd4xhuF1x", "reviewer": "Reviewer_fant", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "Strengths: \n1. The idea of considering different analogy graph patterns as negative and positive ones with respect to target patterns is interesting that allows the relations to be inferred from similar relations. \n2. Paper is mostly explained well and easy to follow. \n3. Experiments show improved results for two tasks on 6 six datasets with significant margins. \n4. Time complexity is provided to get different graph patterns. \n5. The method can be plugged into any kind of GNN to see the significance of subgraph patterns being compared. \n\nWeaknesses: \nI find the idea interesting. However, I have some strong concerns: \n1. What about the graphs with noise since the majority of the real-world graphs have errors or noise? The method seems to focus on learning from similar subgraph patterns that would lead to incorrect results in the case of noisy graphs. \n2. I do not get the idea that says subgraphs have the same topology. All the subgraphs look similar (triangle and quadrangle) and would not make much difference in terms of structure. \n3. I believe the majority of the learning would be from the feature embeddings. I don’t see any exploitation/ usage of graph structure in the proposed method. \n4. The points mentioned under limitations in the paper are quite important. The results would be severely affected in case of missing links/ information in the graph. Also, how to overcome the second limitation. The problem would increase with larger/dense graphs. \n5. Experiments should have been conducted with different GNN architectures to see the significance of the proposed graph pattern comparisons. \n\nQuestions to authors: \n1. What happens if a relation is being used in a different context i.e., the presence of ambiguity. Does that mean the method produces incorrect results? \n2. Did you consider cases where there are rare relations? For example, if the graph has a relation “live” only once in the graph. \n3. How large graphs can the proposed method handle? ", "summary_of_the_paper": "The paper proposes GraphANGEL, a relation prediction framework that checks if subgraphs containing the node pair for predicting relation are similar to other subgraphs containing the particular relation. The overall idea is based on graph patterns in which analogy subgraphs are extracted for a node pair and compared against similar shape subgraphs. These subgraphs are based on three kinds of patterns I.e., target patterns, supporting patterns, and refuting patterns. The framework considers heterogeneous graph based recommendation as well as knowledge graph completion. Experiments are conducted for the above two tasks on six datasets against several baselines from the area of relation prediction.", "summary_of_the_review": "The idea of the paper is different. Experiments show improved results. However, I have concerns about the methodology that majorly considers the feature embeddings without exploiting the graph structure. More experiments (mentioned in the main review) could be conducted to back the idea. Also, the points under limitations can severely affect the method in different scenarios.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "6oR55xu3fEx", "reviewer": "Reviewer_3Zrj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Pros:\n\n- A solid paper, well-motivated, and well-presented. The authors provide detailed examples to demonstrate the main idea of the proposed method, making the paper easy to follow.\n\n- The method combines the logic/subgraph patterns and graph representation learning together to build an explainable reasoning method for relation prediction, such that it can be generalized to unseen relations.\n\n- Experiments on graph recommendation and link prediction demonstrated the effectiveness of the method. It can further produce explainable heat maps of attention scores to help users understand the reasoning process of relation prediction.\n\nCons:\n\n- The main weakness of the method, I think, is its poor robustness, as it requires each triple to have supporting patterns. The authors also pointed out this in the paper. I think the constraints of logical patterns are too strong. Maybe, loosening some constraints, such as not requiring the subgraphs to have the same shapes, would be helpful? I do not know—just a free discussion.\n\n- In my view, the proposed method would cost more time than others, as it has an additional process of subgraph retrieval.\n\nDetailed comments:\n\n- It seems that the authors only provide the complexity analysis of retrieval and sampling. What about the overall time complexity of the proposed method? In my view, the method could cost more time than other baselines, such as those purely embedding-based methods for link prediction.\n\n- What is the standard for choosing baselines of link prediction? It seems that some recent strong methods are not included.", "summary_of_the_paper": "The paper proposes a novel inductive method for relation prediction over heterogeneous graphs. The method extracts supporting and refuting subgraphs to judge whether a relation exists between two nodes. In this way, the relation embedding can be implicitly expressed by the other relations in the subgraphs. The method is generalized to unseen relations. The method uses GNNs to encode subgraphs for similarity computation. Experiments on graph recommendation and link prediction demonstrated the effectiveness of the method.", "summary_of_the_review": "A solid, well-motivated, and well-presented work. Although the method would suffer from poor robustness, it is a meaningful attempt to connect logic/subgraph patterns and graph representation learning for explainable reasoning.\n\n--- after rebuttal ---\n\nThe authors' response addressed my concerns. I would raise the score to 8.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an approach to predict relations between node pairs in heterogeneous graphs, with application to recommendation and knowledge-base completion. 

The author's approach is to compute similarities between subgraphs that are neighborhoods of nodes where the relation holds or not to score a relation. The authors use graph neural networks to scores these subgraphs. The type of subgraphs that are considered are pairs of nodes, 3- and 4- cyles to make inference and training tractable. The paper lies in the stream of work that combines logical reasoning and neural network, even though in that particular instance it mostly combines graph mining techniques and neural networks. 

The reviewers unanimously liked the presentation of the paper and the high empirical performance. The rebuttal addressed most of the remaining concerns.
Decision: Accept (Poster)