A Topological View of Rule Learning in Knowledge Graphs
Authors: Zuoyu Yan
Tengfei Ma
Liangcai Gao
Zhi Tang
Chao Chen
Venue: ICLR 2022 Submitted (2022)
Keywords: Inductive Relation Prediction
Topological Data Analysis
Cycle Basis
Homology

Abstract: Inductive relation prediction is an important learning task for knowledge graph completion. One can use the existence of rules, namely a sequence of relations, to predict the relation between two entities. Previous works view rules as paths and primarily focus on the searching of paths between entities. The space of paths is huge, and one has to sacrifice either efficiency or accuracy. In this paper, we consider rules in knowledge graphs as cycles and show that the space of cycles has a unique structure based on the theory of algebraic topology. By exploring the linear structure of the cycle space, we can improve the searching efficiency of rules. We propose to collect cycle bases that span the space of cycles. We build a novel GNN framework on the collected cycles to learn the representations of cycles, and to predict the existence/non-existence of a relation. Our method achieves state-of-the-art performance on benchmarks.

Under review as a conference paper at ICLR 2022
A TOPOLOGICAL VIEW OF RULE LEARNING IN KNOWLEDGE GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Inductive relation prediction is an important learning task for knowledge graph completion. One can use the existence of rules, namely a sequence of relations, to predict the relation between two entities. Previous works view rules as paths and primarily focus on the searching of paths between entities. The space of paths is huge, and one has to sacrifice either efficiency or accuracy. In this paper, we consider rules in knowledge graphs as cycles and show that the space cycles has unique structure based on the theory of algebraic topology. By exploring the linear structure of the cycle space, we can improve the searching efficiency of rules. We propose to collect cycle bases that span the space of cycles. We build a novel GNN framework on the collected cycles to learn the representations of cycles, and to predict the existenceemnnn-existenee of relation. Our method achieves state-of-the-ard performance on benchmarks.
INTRODUCTION
Knowledge graphs (KGs) are graph-structured knowledge bases that integrate human knowledge through relational triplets. In a KG, nodes represent entities and edges represent relational triplets connecting them. A relational triplet is defined as (en, r; Et). where en and e, are the head and tail entities respectively, and is the relation between them. KGs have been used in many prob- lems such as recommendation systems (Wang et al. 2018), question answering (Huang et al. 2019) Zhang et al.] 2018). biomedical research (Zhao et al. 2020b Zhu et al. 2020). and zero-shot learn- ing (Kampflmeyer et al.) 2019).
Due to the limitation of human knowledge and data extraction algorithms, cannot thoroughly define and excavate all the entities and relations in a KG (Chen et al., (020)) The incomplete struc- tures and contents of KGs significantly benefit from automatic completion algorithm. Early works (Bordes et al., 2013 Yang et al., 2014 (unn et al. 2019) focus on incorporating the attributes of entities. Recent works develop models that are agnostic of entity attributes. They can handle new entities and dynamic KGs, which are quite common.
These entity- works (Yang al., 2017 7 Sadeghian et al. 2019 Teru et al. 2020 are called inductive relation prediction models. They predict missing triplets by learning logical rules in KGs. For example, from the KG shown in Figure Ta), we can learn the rule:
3X,(X, (X, part of .Y) A (X, lives in Z) + (Y, located in Z).
Based on the learned rule, in Figure [b),, we can induce the missing triplet Unanceetter located_in in Manchester) due to the existence of the two-hop path (Cristiano, lives_in MM Manchstter) and (Cristiano, part_of ManchesterUniitte nittd))
Existing inductive relation prediction works (Yang et al., 2017 Sadeghian al., 2019) mainly view rules paths, i.c., sequences of relations connecting two entities of interest. For example, to express the rule shown in Equation| []] these methods need to enumerate all possible 2-hop paths. As Yang et al. (2017) pointed out, the number of learnable parameters of these methods is (( where [ denotes the number of relation types, and T denotes the maximum length of rules. To avoid
'Technically speaking, these methods can only learn the "and" operation hetween relations. We will be interested in expanding more sophisticated rules, but this is beyond the scope of this paper.

---

Under review as a conference paper at ICLR 2022
U1
C4
Lifly
12
U4
perror
(d)
edtron
part of
Lakers
Cristl
part
Manch ester
U3
(c)
live fn
United
Rg
61
63
65
1
0
1
Manch
V1
1
1
1
0
0
0
0
1
62
0
1
1
63
0
1
1
61
0
174
0
1 (e)
68
(a)
(b)
(f)
Figure I: (a) and (b): examples of inductive relation prediction. (c)-(f): illustrations for cycle space and cycle basis. (c): A sample graph with three nontrivial cycles, žy, 24 and 2g (highlighted with red, blue and green colors). Any two of the three will form a cycle basis. (d): Mod-2 addition of
cycles. (e): the boundary matrix of the graph in (c). Any cycle 2 satisfies Oz O. (f): the cycle
incidence matrix of the graph in (c). We show all three columns corresponding to all three nontrivial
cycles (zr, 2b and zg). our algorithm, we only pick the columns corresponding to a chosen cycle basis, e.g., the first two columns when the chosen basis is { 263-
the exponential-size search space of paths, we tackle the problem from new perspective: to view logical rules as cycles, and then learn the rules in the space of cycles. In fact, any rule can be considered a cycle by including both the relation path and the target relation itself.
The benefit of using cycles is that there is an intrinsic structure in the space of cycles. Based on the theory of algebraic topology (Munkres) 2018), the space of cycles is a vector space under certain assumptions. We can exploit the linear structure of cycle space for efficient rule learning. In particu- lar, we focus on a basis, i.e., a set of linearly independent eycles that can represent any cycle. Taking Figure [a) as example, if we choose the red cycle and the blue cycle the cycle basis, then the green cycle can be represented as their sum. Here "sum" means modulo-2 sum (Figure (d)), thus the overlapped triplet (Lebron, part_of Lakers) is canceled. By focusing the cycle basis that spans the cycle space, we decrease the parameter space from exponential to linear"
However, the choice of useful cycle basis is not trivial. Not all cycles/rules are "good", or say, providing a valid relation reasoning. For example, the green cycle in Figure a[a) reveals the rule:
3X,, X2, (X1, support, Y) A (X1, fan of X2) A (X2, lives in 2) + (Y, located in Z). (2)
This rule is not considered good. There is no strong reason that a basketball team (Y) should be located in a city (Z) just because there fan (X₂) that supports both the team and player (X2) living in the city Z. The goal of relation learning is to efficiently comb through all cycles/rules and learn the good ones. A desirable cycle basis should facilitate this process. Intuitively, the elements of the basis should be as close to good cycles possible. Revisiting the example of Figure a)) we prefer the basis consisting of the red and blue cycles (both are good rules) and avoid the green cycle.
To find suitable cycle bases for relation learning, we propose approach inspired by the theory of topological data analysis (Dey et al. 2010 Chen & Freedman, 2010 Busaryev et al., 2012). These works show that cycle bases generated from shortest path trees have favorable theoretical guarantees. In the context of relation learning, we argue that the good cycles are generally short, cycle bases. We also propose to sample
and can be easily learned using pathtest-pat-ttte--baee multiple shortest path trees and collect a family of cycle bases. This provides sufficient redundancy and coverage ensure learn good cycles/rules efficiently, experiments will show.
To fully exploit the cycle bases to learn all the good rules, we propose Cycle Basis Graph Neural Network (CBGNN). We build GNN on a new graph whose nodes represent cycles in the chosen bases, and edges represent their interaction. Through the message passing of the GNN, we are running implicit algebraic operations over the space of cycles. Our method will efficiently learn to represent good cycles, and learn to predict relations in KGs. Experiments on popular inductive relation prediction benchmarks show the efficacy of our method.
A cycle hasis of size 3 spans cycle space of size 2
2

---

Under review as a conference paper at ICLR 2022
In summary, contribution is three-fold:
1. We propose, for the first time, to investigate the inductive relation prediction problem through bysee-based perspective.
2. Inspired by the theory of topological data analysis, we propose to exploit the linear structure of the cycle space, and to compute suitable cycle bases that can best express the rules. This empowers to explore rule space more efficiently than previous path-based approaches. e
3. We propose a novel graph neural network, CBGNN. It runs implicit algebraic operations in the cycle space through the message passing of a GNN, and learns the representation good cycles and good rules. Experiments show that CBGNN achieves state-of-the-art results on various inductive relation prediction benchmarks.
2 RELATED WORKS
Graph Learning with Topology. Graph structural information have been shown enhance graph representation learning (Kipf & Welling, 2016 You et al. 2019 Ye et al. 2019). In recent years ad- vanced topological information, i.e., persistent homology (Eeelsrrunner et al. 2000 Edelsbrunner & Harer, 2010), have been applied to graph learning problem. prrsistent-homoloyy bobeeed features encode multiscale topological information regarding graph structures in view of different filter func- tions. They provide additional discriminative power for various tasks such as graph classification
(Hofer et al. 2020 Carrière et al., 2020. Hofer al., 2017; Zhao Wang 2019). link prediction Yan et al.] 2021 Bhatia et al. 2019), and node classification (Zhao et al. 2022a). From different perspective, new graph neural networks have been proposed for high-order graphs, treated as sim- plicial or cell complexes (Bodnar et al.) a). Unlike these approaches, we focus on different task, inductive relation prediction. We exploit the space of cycles and its underlying algebraic struc- ture for better graph representation learning. We believe the cycle-centric design of graph neural network is generic and can extend to many other tasks beyond relation prediction.
Finally, we note that in topological data analysis, homology localization, including computing short cycles representatives of a homology class and computing short cycle bases representing the whole homology group, is well studied theoretically (Chambers al.] 2009 Chen & Freedman 2011 Dey et al. 2011] Busaryev et al. 2012: Dey et al.] Dey & Wang 2022). In recent years, new questions have been raised regarding finding short representative cycles for classes in persistent ho- mology (Wu et al. 2017, Dey et al., 2020). Cycle information can complement persistent homology
information achieve better learning power.
Inductive relation prediction methods. Inductive relation prediction methods can be divided into two categories: path-based based methods, and GNN-based methods. Among path-based methods, AMIE (Galárraga et al.) 2013) and RuleN (Meilicke et al. (018)) are classic rule learning methods. These two methods prune the process of rule searching based on strong assumptions on the attribute of rules, thus their performances are not satisfying. To deal with the problem, Neurall.P (Yang et al.) 2017) and DRUM (Sadeghian et al. 2019) are proposed to learn the rules in a data-driven manner. However, pointed in (Sadeghian et a 2019), these works cannot learn all the rules correctly with a small number of learnable parameters.
GNN- methods such GralL (Teru al. 2020) and CoMPILE (Mai al. 2021 predict missing triplets with graph neural networks (GNNs). These methods are appealing as GNNs are able to learn better representations and achieve state-of-the-art performance in general. To predict whether a certain triplet exists in the KG, these methods first extract the corresponding vicinity graph of the triplet and then learn the rules through message passing and GNN scoring. Therefore, they can only predict the triplets one by one, with rather low computational efficiency. In the experiment part, we will empirically show the efficiency of our framework by comparing with these models.
CYCLE SPACE, CYCLE BASIS, AND THE PURSUIT OF SUITABLE BASES
In this section, explain how find suitable cycle bases that can facilitate the learning of good cycles/rules. We first introduce the background of the cycle space and cycle basis. Next, we explain our choice of suitable cycle bases, which will be the foundation of our model.
By no means our exposition is comprehensive. For more details, we refer the readers to textbooks algebraic topology and computational topology (Munkres 2018 Edelsbrunner & Harer 2010
3

---

Under review as a conference paper at ICLR 2022
Dey & Wang 2022). We focus on cycles in undirected graphs, while the definitions generalize to higher dimensions, c.g., simplicial complexes. Furthermore. we focus on the algebraic structures over Zg field, which has two elements, and 1, under modulo-2 addition and multiplication. Over Ze field, the structure of the space of cycles is simpler and more friendly to computation.
For the rest of the paper, regarding the input KG, we will use node, vertex, and entity interchange- ably. We will also use edge and triplet interchangeably. Within this section, we temporarily ignore the relation associated with each triplet. We treat the input KG as an undirected graph G = EV, where V and E denote the sets of vertices and edges, respectively.
3.1 BACKGROUND: CYCLE SPACE AND CYCLE BASIS
For ease of exposition, we assume the input graph G' is connected. The definitions can easily ex- tend to graph with multiple connected components. An elementary cycle is a closed loop, i.e., a sequence of edges, {(no, v1). (2), (Vn-1, vn), 1,)), (Un, vg]), going through distinct vertices except for the first and the last. cycle is the union of set of elementary cycles.
The set of all cycles constitute a vector space under modulo-2 additions and multiplications. Figure [dd) illustrates the mod-2 addition of cycles. There space of cycles. Assume fixed indexing of all edges and all vertices. The [V] x |E' incidence matrix, 0 also called the boundary matrix, encodes the adjacency relationship between edges and vertices. Any set of edges, called chain, corresponds to an [El-dimensional binary vector, c. The i-th entry of c, C₁ is I if and only if the chain contains the i-th edge, e, The set of all chains form vector space called the chain group. All chains one-to-one correspond to all possible |F|- dimensional binary vectors. Multiplying the boundary matrix to given chain is equivalent to taking the boundary of the chain. Figure ([]c) and (e) show a sample graph and its boundary matrix. A cycle is a chain with zero boundary. Formally, the set of all cycles of G, denoted as Zg. is the kernel space of the boundary matrix, Zg ker θ = {e | Ôc 0). In the example graph in Figure Ic), there are 3 different nontrivial cycles, highlighted in red, blue, and greer F
nice linear algebra interpretation of the
Cycle basis. cycle basis is basis spanning the cycle space Zg. Formally, a basis, Z, is a maximal set of cycles {21, {21.22... ....... ... such that (1) any cycle in Za can be written as the formal sum of cycles in the basis, V2 E 2c. 3o, E (0, 1], s.L. = Ex.e 02 and (2) cycles in Z are linearly independent, = V2, E Z, a, = O. In Figure [c). the red and the blue cycles form a cycle basis. We note that the basis is not unique. The red cycle and the green cycle form another cycle basis of the same graph. However, the number of elements in the basis, |Z]. is the same. We call
Enjez 02
the Betri number, denoted as B. We have 3 = E -VI
1, and the cycle space has size 2
3.2 THE PURSUIT OF SUITABLE CYCLE BASES
The central idea of our approach is to find "suitable cycle bases" to represent the cycle space, that we can efficiently learn the "good cycles" corresponding to "good rules". In this section, we explain how such suitable cycle bases are constructed. In theory, any basis can represent the whole cycle space, and thus can serve the purpose. However, during learning, we need to look for suitable hases that can easily represent good cycles.
Following the Occam's razor principle, we hypothesize that the good cycles tend to be short, and the desired cycle bases should generally contain short cycles. This is also manifestation of the principle from the theory of topological data analysis: short cycles are better representatives of topology (Dey) & WWang 2022; Dey et al.) 20100] Chen & Freedman| (2100). In fact, this is supported by empirical evidence in relation prediction. It was observed that good rules can be learned even when we exclude long rules from search space (Teru et al. 2020). Motivated by these works, we propose to represent good cycles using shortest path tree (SPT) cycle bases, i.e., cycle bases constructed based on shortest path trees. They generally contain relatively short cycles, and can be computed efficiently.
Formally, shortest puth tree (SPT) is spanning tree Tр C G with root p. such that for any vertex q # p. its path to p within Tp is also its shortest distance path to p within G. In other words, Tр is union of shortest paths from all vertices to the root p. A shortest path tree defines unique cycle basis, which we call the SPT cycle basis. As shown in Figure 2[a) a) and (b), given a shortest path tree,
Technically, an empty chain (contains edges) is also a cycle.
4

---

Under review as a conference paper at ICLR 2022
Tp, each non-tree edge EX forms elementary cycle with the tree Tp. We construct the basis by enumerating through all non-tree edges and collect all the corresponding elementary cycles. We denote this cycle basis (Tp) An SPT cycle basis naturally contains short cycles; each cycle is composition of an edge (u, 0) and two shortest paths the shortest path from a to p' and the shortest path from p'. Here p' is the lowest common ancestors of and within the rooted tree, Tp
Furthermore, in order to effectively express the rule, we propose to collect a family of SPT cycle bases with different tree roots, to ensure redundancy and sufficient coverage. These bases comple- ment each other and achieve the best learning efficiency in finding good cycles. The hope is that any good cycle can be easily learned by at least one of the bases.
Ideally, we can use the whole vertex set V as roots and build the collection of cycle basis (Z(T,) p VJ. This family of bases has been shown have thcoretical benefit (Dey et al., 2010 Chen & Freedman 2010). In practice, we cannot afford to construct the bases using all ver- tices as the SPT roots. We propose to sample vertices that are generally far away from each other. We perform spectral clustering on the graph and use centers of the clusters the sample vertices, S. We hypothesize that these SPT cycle bases will cover the whole graph, and their corresponding cycle bases. {Z(T,) p S}, will satisfy our needs. We call these bases the SPT cycle buses family. As validated in the appendix, these SPT cycle bases provide sufficient coverage of the target edges/triplets, with short cycle representations, compared with random cycle bases.
Generate SPT Cycle Basis
Multill
Yi
BRLSTM
P.r
Weighted
Generate SPT Cyce Basis
Sum
Misriply
VIE
BRLSTM
Yisl
Yun
(a) Input KG
(b) SPT Cycle Basis (c) Cycle Graph (d) Cycle confidence
(e) Triplet confidence
Figure 2: Architecture of CBGNN, For the input KG shown in (a), we first select the red root nodes using a clustering algorithm and obtain the corresponding SPT cycle bases in (b). Then for every SPT cycle basis. construct a new graph in (c) where nodes represent cycles in the basis and edges indicate a strong interaction between the two corresponding cycles. The initial node feature vectors extracted from corresponding cycles using BR-LSTM. With GCN MLP, confidence value for the nodes (cycles) in (d). And we can compute the confidence value of a given triplet the max confidence value of cycles passing Finally, we the weighted of triplet confidence from different SPT cycle bases as the final triplet confidence.
learn the
4 CYCLE BASIS GRAPH NEURAL NETWORK (CBGNN)
In this section, we describe how to use the SPT cycle bases family to learn a good cycle representa- tion, to find good rules, and to predict the existence/non-cxiseeee existonneextteeeeeeeoee of triplet. We propose a novel graph neural network based on the cycle bases, called the CBGNN. The input of CBGNN is a KG and the target triplets. A target triplet (Cn, r, e.) refers to query of whether the relation exists between entities én and e,. A target triplet is labeled positive if exists the KG, and negative oth- erwise. Following the tradition (Teru et al. 2020 Mai al.) 2021), we temporarily add the negative triplets into the input graph. The output of CBGNN is the confidence value of the target triplets. By explicitly constructing action between cycles, CBGNN learns representations of cycles that best serve the goal of relation prediction.
graph whose nodes correspond to cycles and edges correspond inter-
5

---

Under review as a conference paper at ICLR 2022
The overview of our method is shown in Figure Our method has two phases. In the first phase, we construct the cycle bases and build a new graph for each cycle basis (called the cycle graph). In the cycle graph, nodes represent cycles in the basis, and nodes are connected if their corresponding cycles have a strong interaction. The information of the cycles can be converted into node features in the new graph for the next phase. Details are provided in Section 4.1
In phase two (Section 4.2) we build a GNN on the cycle graph to learn the confidence value for cycles. The confidence values for cycles are mapped to the confidence values for target triplets. We construct GNNs for different cycle bases. These GNNs share weights and their aggregation is used to predict the confidence value for the target triplets.
4.1 GENERATING THE CYCLE GRAPHS
We construct cycle graphs using the SPT cycle bases family, Recall that in Section S we propose to sample vertices at different parts of the input KG and construct SPT cycle bases accordingly. In order to achieve good coverage, these vertices should be selected sufficiently apart from each other. In this way, the family of cycle bases can effectively represent all cycles at different parts of the input KG. In particular, we run spectral clustering on the input graph and partition the nodes into clusters. Then take the central nodes of the clusters (the node closest to the cluster center) the set of sample vertices, S.
Using vertices in S roots, complexity for building each SPT is O([V+ [E]). 4 For each SPT, Tp. E S, we construct its cycle basis by going through all non-tree edges. For each non-tree edge, (u, v) E EXT we find the least common ancestor of u and e in Т, in O(V)) time. In total the complexity for building one cycle basis is ((EE))) All the cycles form the desired SPT cycle basis 2(T,). We now have k cycle bases, each of which has 3 many cycles. The total running time for building k bases is O El).
the breadth-frstt-eardd algorithm to construct k SPTs. The
Note that the input graph may consist of several connected components. The cycle bases of different component graphs are independent of each other. We treat the component graphs as separate input graphs, and generate & SPT cycle bases for each of them. We essentially construct a CBGNN for each component graph, although their weights are all shared.
Cycle incidence matrix. We explicitly construct a cycle incidence matrix for each SPT cycle basis. This matrix encodes the incidence relationship between cycles and edges in the input KG. It will be used at different stages of our learning; it implicitly encodes interaction between the cycles, and meanwhile, it provides convenient way to map confidence values between cycles and triplets.
For each of the constructed cycle bases, we construct the cycle incidence matrix Cr as an |F] x B binary matrix. Each column corresponds to one cycle in the basis. Each row corresponds to an edge/triplet in the input graph. The (i.j)-th entry of the matrix is if the j-th cycle contains the i-th edge, and 0 otherwise. An edge may not be associated with any of the basis cycles and thus has all zeros in the corresponding row. See Figure ff) for an illustration. After generating is shortest path trees and their SPT cycle bases, we acquire Te cycle incidence matrices: {C/, Cr..... Ct).
Cycle feature. To use these cycles in learning, we need to extract their attributes/featurrs. We need feature representation for cycle based on the relations associated with its triplets. Inspired by existing methods on rule learning (Marcheggiani & Titov] a recurrent model, Bi- Ri-Relational LSTM (BR-LSTM), as the feature generator. It converts cycle of triplets into a fixed-length feature vector for the CBGNN to use.
Vashishth et al. (219), we propose
During the construction of the SPT cycle bases, we treat the input KG an undirected graph. But in the generation of cycle feature, we tackle the input KG as a directed graph with different edges/triplets associated with different relations. We assume that information an edge/triplet flows along both directions, and encode the cycle in a relation-awar the set of all the triplets, we assume that
manner. We denote by (u, r, v) E E
a triplet connecting nodes u and u with relation r. Here an inverse triplet (v, r- u) is also included in the KG. Here -- is defined as the inverse relation of r. Formally, we extend the triplet set of the KG as: E' = E U ((v,r ,u)((u,rr o) E E}. An illustration of the construction can be found in the appendix.
*Note the breadth-firsee first-search algorithm works only because we assume all edges are weighed one.

---

Under review as a conference paper at ICLR 2022
For each cycle, we can LSTM to encode the cycle from both directions using triplets in E'. Take Figure [ as an example, for simplicity we substitute the relations partLof, lives and lo- cated in with 71, 72 and r3. respectively. The rule be represented by (Lebron, ri, Lakers) A (Lebron, r2, I..A) + (Lakers, 13, I.A). In practice, we use the non-tree edge in the cy- cle as the first triplet in the sequence. Therefore we convert the rule into two sequences with the opposite direction: (Lakers, r3, L.A), (L.A, T22 Lebroon, (Lebron, T1, Lakers) and (L.A, r3 Lakers), (Lakers, rT', LeBrn),, (Lebron, T2, L.A). We denote the two sequence as 81 and 82. To encode the two sequences, we adopt a LSTM for each sequence, to capture the contextual information between relations:
Wnentis (ha,, C.. = (WS. (b1,c))); Wneztt: (haz, C..) LSTM (wsz: 02))
Here, for any = 1, 2, Ws, denotes the input embedding vector for sequence st. h2 and o are the initial hidden state and cell state for sequence 8;, they are initialized as zero. Wnezt, is the output features from the last layer of the LSTM. It is not needed in our setting. h2, and Cs2 are output hidden state and cell state for the whole sequence 83. We use them as the feature vector for each sequence. The final feature vector for the rule and its corresponding cycle, 2, is 22 (hez + hta)) A (Ca, + Cog), where + represents the concatenation of vectors.
4.2 GNN LEARNING WITH CYCLE GRAPHS
We propose a GNN to exploit the SPT cycle bases to learn representations of good rules and use the learned rules to predict the confidence value of certain triplets. We first build the cycle graphs for the SPT cycle bases, and then learn the confidence value for cycles and triplets.
Building eycle graphs. Recall that in Section 4.1 we obtain & cycle bases and l corresponding
OT matrices, For each cycle basis, we construct new graph in which nodes represent cycles in the cycle basis and edges indicate that the two corresponding cycles have a strong interaction. To measure the interaction between any two cycles in the basis, we compute their overlapping, i.e., the number of triplets they share. In the new graph, each cycle is connected with its top m overlapping neighbors, i.e., the top m other cycles with the most number of shared triplets. To compute the number of shared triplets between all pairs of cycles in the basis, we simply multiply the cycle incidence matrix and its transpose, Cf Cr, and read the entries of the resulting 3 x B matrix. For each cycle 2, we inspect its corresponding column in the matrix, and select the top m rows as the eycles to connect.
Learning cycle representation and confidence. To learn the representation and confidence val- ues of the desired rules, we apply classic L-layer graph convolutional network (GCN) (Kipf & Welling. 2016) to the constructed cycle graph. The input is the feature vector of cycles generated by BR-LSTM, and the output is the representation of cycles. The message passing by GCN drives the information flow between different cycles. After an L-layer GCN, the embedding of a certain node can be viewed as a combination of node representation from its L-hop neighborhood. Take Figure [ as an example, if we take {žr, 2 as the cycle basis, then and &g will be the nodes in the new graph. Because they share triplets e and e4, there is an edge between the two nodes in the new graph. Then cycle 2n can be learned by the message passing between 2, and Eg.
In the l-th layer of GCN, we can obtain the embedding matrix X = [af .2.....,r x. where of e dd is the representation of node i in the ê-th layer, l = 0, I,.,, L. Here, X is the initial cycle features from BR-LSTM, and XL is the node embedding matrix of the final layer. After the L- layer GCN, we adopt two-layer Multi-Layer Perceptron (MLP) followed by sigmoid function to learn the confidence value for each cycle in the basis: P p sigmoid( M MLP(H where P = [p1. .P.....pp! E R < Pt <
See Figure c) and (d).
Learning triplet confidence. Finally, we compute the confidence values for the triplets of KG based on the confidence values of cycles learned through GNN. We take the max confidence value of cycles/rules that pass triplet as the confidence value for the triplet. Recall that for each cycle basis, the cycle incidence matrix Cr stores the incidence relationship between cycles and triplets. The i-th row of matrix CT has I's corresponding to cycles in the basis that pass triplet e;. For triplet e, its confidence value is computed as y = mar(Cr *) @ P), where Cr *) is the i-th row of Cr, and @ denotes the element- product between two vectors. We obtain the confidence values for all target triplets: Y = [y), V2, V2,..., Fn] E R", where n is the total number of target triplets, 0 S y < 1, i 1, 1,2,..,,
7

---

Under review as a conference paper at ICLR 2022
We aggregate the output of the k GCNs obtain the final triplet confidence. Each GCN is built on one SPT cycle basis and its corresponding cycle graph. We compute the final confidence value of each triplet using weighted sum of the triplet confidence from different GCNs. Each GCN has one weight value, and the weights are learned during training. Formally, Finnll =
E Y/ E - wt We train CBGNN by minimizing the cross-entropy loss target triplets.
5 EXPERIMENTS
We compare our methods with state-of-the-ar (SOTA) inductive relation prediction models on pop- ular benchmark datasets. We also use ablation studies to demonstrate the efficacy of different pro- posed modules in our method. Further experimental details can be found in the appendix.
Datasets. We use SOTA benchmark datasets proposed in (Teru et al., 2020; Mai al., 2021). For inductive relation prediction, the entities in the training set and the test set should not be overlapped. Therefore the training and test sets are totally disjoint graphs. Details are provided in the appendix. Among these datasets, FB 15k--337 has >> 200 relation types, NELL--995 contains an average of 50 relation types, and WN18RR contains R 10 relation types.
We compare with SOTA inductive relation prediction methods including (1) path-based methods: PeuralLP YYag et al. 2017). RuleN (Meilicke al. 2018) and DRUM (Sadeghian al.) 2019) and (2) GNN-based methods: GralL (Teru al. (020) and COMPILE (Mai et al. 2021).
Baseline.
Evaluation. Similar to Teru et al. 2020: Mai et al. 2021), we use area under the precision-recal curve (AUC-PR) and Hits@ 10 scores as the evaluation metrics. To calculate the AUC-PR score, sample an equal number of non-existent triplets as the negative samples. To evaluate the Hits 10 score, rank each positive triplet among 50 randomly sampled negative triplets. We run each experiment five times (with different negative samples) and report the mean results.
Negative sampling. Following (Teru al. 2020 Mai et al. 2021), we sample negative triplets by replacing the head (or tail) of a true triplet with a uniformly random sampled entity.
Table AUC-PE C- scores of inductive relation prediction, the baseline results are copied from Teru ct al. 2020 Mai et al. 2021
WN18RR
FB 15K-237
NELL-995
Method
v1
v2
v3
v1
v2
v3
v1
v2
v3
NeuralLP
86.02
83.78
62.90
82.06
69.64
76.55
73.95
75.74
64.66
83.61
87.58
85.69
DRUM
86.02
82.06
69.71
76.44
74.03
59.86
83.99
87.71
85,94
RuleN
90.26
89.01
76.46
85.75
75.24
88.70
91.24
91.79
84.99
88.40
87.20
80.52
Grall.
90.57
CoMPILE
98.23
99.56
93.60
99.80
85.50
91.68
93.12
94.90
80.16
95.88
96.08
85.48
CBGNN
98.63
97.62
89.76
97.80
96.34
96.53
96.38
95.23
82.79
94.78
96.29
94.01
Table 2: Hit 10 scores of inductive relation prediction, the baseline results are copied from Teru et al. 2020 Mai al. 202T
WNI8RR
FB1
1KK-337
NELL-995
Method
v1
v2
v4
v1
v2
v3
v4
v2
v3
NeuralLP
74.37
68,93
46.18
67.13
52.92
$2.90
55.88
40.78
78.73
82.71
80.58
DRUM
74.37
68.93
46.18
67.13
52.92
58.73
52.90
55.88
19.42
78.55
82.71
80.58
RuleN
80.85
78.23
53.39
71.59
49.76
77.82
87.6 37.69
85.60
53.50
81.75
77.26
61.35
Grall.
82.45
78.68
73.41
64.15
82.83
89.2
93.25
91.41
73.19
COMPILE
83.60
79.82
60.69
75.49
67.64
82.98
84.67
87.44
58.38
93.87
92.77
75.19
CBGNN
98.40
96.14
62.28
96.50
97.56
96.03
94.91
94.73
84.00
94.96
95.34
92.34
Results and discussion. Table and Table show the AUC-PR scores and Hits 10 scores respec- tively. Our method outperforms all SOTA baselines in terms of Hits @ 10 (Table As for AUC-PR (Table D. our method outperforms nearly all SOTA baselines on FB 15K-237 and NELL-995. On WN18RR, CBGNN is close second, trailing marginally behind CoMPILE, but outperforming the remaining methods significantly. Note that in terms of the number of relationship types, FB15k-237 (>2000) and NELL-995 (==50) are significantly larger than WN18RR (==10). They considered much more semantically complex. This demonstrates that our novel cycle- based approach has stronger modeling power for KGs with complex semantics.
8

---

Under review as a conference paper at ICLR 2022
Computational efficiency. We compare the computational efficiency of our method and the base- lines. For a fair comparison, for all methods, we set the training epochs to 100 without early stop- ping. We run all methods 5 times and report the average time. As shown in Table [3] our method is significantly faster than existing GNN-based methods. Existing GNN-based methods, although demonstrating strong prediction power, are rather expensive. For each training/tssting triplet, a GNN method extracts subgraph within the vicinity and then applies graph convolution. Repeating over all target triplets is rather expensive in practice. On the contrary, our method construct one unified GNN for all target triplets and learn/predict their confidence values simultaneously.
Table 3: Evaluation of computational efficiency (second).
Dataset Plase
WNISRR vl Training
FB15K-237 v1
NELL-955 v1 Training
Preparation
Infereace
Preparation
Training
Infercuce
Preparation
Inference
Grall.
452.36
2230.55
1.07
704,42
9026.21
1.67
402.86
3718.22
1.79
CoMPILE
434.45
2388.28
1.46
706.19
3809.56
241
479.21
2868. 38
1.23
CBGNN
601.96
952.55
0.52
437.13
901.27
0.75
379.29
175.19
0.14
Allation studies. We perform ablation studies to validate the efficacy of different proposed modules in CBGNN. We focus on three perspectives, the choice of cycle basis generation and the cycle feature generation. To justify the usage of SPT cycle bases, we compare with a baseline using randomly generated SPT's to build cycle bases, called C'GNN-Random Both CBGNN and CBGNN-Randon generate the same number of trees/cycle bases, k = 20. To show that sampling multiple trees/cycle bases is necessary, we also add a baseline with a single SPT cycle basis, called CBGNN-Single.
For the generation of feature vectors for cycles in the cycle bases, we compare with two baselines which replace BR-LSTM with bag-of-words-like (BOW) feature vector and a classic LSTM. These method are named CBGNN-BOW and CBGNN-LSTM, respectively. The BOW feature generates a histogram of different relationship types within a given cycle. The classic LSTM takes a single direction to traverse through the loop instead of two.
Results of the baselines are compared with the proposed CBGNN in Table In terms of cycle bases generation, our method generally outperforms CBGNN-Random. This demonstrates that in most cases, the center nodes of clusters spread out and are capable of covering the whole graph. Thus for node selection, a clustering algorithm performs much better than random selection. In addition. our method also outperforms CBGNN-Single, showing the necessity to utilize multiple bases to provide better coverage. In the appendix, we will provide more experiments on the influence of the number of SPT cycle bases k on learning cycle representations.
In terms of cycle feature generation, our method outperforms CBGNN-BOW and CBGNN-LSTM on the majority of datasets. The results elucidate the efficacy of our relation- aware feature generation method, BR-LSTM. We were bit surprised to find that BOW performs well on FB15k-237 237 and is slightly better than the proposed BR-LSTM. This may be due to the high semantic complexity of this dataset (>-200 relationship types). The high number of relationship types makes LSTM and BR-LSTM hard to train, whereas BOW may perform robustly under such circumstances.
Table 4: AUC-PR scores of ablation study.
WN18RR
PB15K-257
NHL. LHSL-995
Mothod
v1
v2
v3
v8
v1
v3
v4
v1
v2
CBGNN-MLP
16.33
97.49
86.86
95.22
90.90
87.01
87.78
72.29
93.35
91.29
CRGNN-RRaddm
97.13
76.64
87.30
93.47
96.23
96.07
93.27
94.49
83.69
93.73
96.20
92.94
CBGNN-Single
55.67
81.67
81.75
72.29
80.97
CBGNN-BOW
97.46
96.0
97.61
96.85
97.00
75.31
91:00
87.53
CHGNN-LSTM
98.26
97.04
89.69
97.75
95.86
91 91.46
94.56
92.47
71.85
95.33
93.74
85.78
CBGNN
98.63
97.62
89.76
97.80
96.34
96.53
96.3
95.2
82.79
94.78
96.29
94.02
6 CONCLUSION
We provide a novel GNN-based method for inductive relation prediction in knowledge graphs, and propose cycle-centric approach that treats rule learning as cycle learning problem for the first time. We exploit the intrinsic linear structure of the space of cycles and learn suitable cycle bases to represent the rules. The learning of cycle representation is carried out via GNN that passes messages between cycles instead of nodes. Our approach achieves SOTA performance on various inductive relation prediction benchmarks, and provides novel perspective in incorporating ad- vanced topological information into graph representation learning. Also, our method can naturally be extended to tasks beyond relation prediction.

---

Under review as a conference paper at ICLR 2022
Reproducibility Statement. The details of CBGNN mentioned in Section The implementa- tion details are mentioned in Section 5 and Section A.2 of Appendix. The details of the data and the used computation resources are described in Section A.2 of Appendix.
REFERENCES
Sumit Bhatia, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. persistent homology per- spective to the link prediction problem. In International Conference on Complex Networks and Their Applications, pp. 27-39. Springer, 2019.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liö, Guido Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. arXiv preprint arXiv: 106. 12575, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang. Nina Otter, Guido Montúfar, Pietro Lio, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. arXiv preprint arXiv:2103.0322/1 2021
Antoine Bordes, Nicolas Usumier, Alberto Marcia-Duran Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling Systems (NIPS), pp. 1-9, 2013.
data. In Neural Information Processing
Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K Dey, and Yusu Wang. Annotating simplices with a homology basis and its applications. In Scandinavian workshop on algorithm theory, pp- 189-200 Springer, 2012.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike. Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In International Conference on Artificial Intelligence and Statisties, pp. 2786-2796. PMLR, 2020.
Erin W Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In Proceedings of the twenty-fifth annual symposium Computational geometry, pp. 377-385, 2009.
Chao Chen and Daniel Freedman. Measuring and computing natural generators for homology groups. Computational Geometry, 43(2):169-181 2010.
Chao Chen and Daniel Freedman. Hardness results for homology localization. Discrete & Compu- national Geometry, 45(3):425 2011.
Zhe Chen, Yuehan Wang, Bin Zhao, Jing Cheng, Xin Zhao, and Zongtao Duan. Knowledge graph completion: A review. IEEE Access, 8:192435-192456, 2020. doi: 10.1109/ACCESS.202 3030076.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In Thirty-second AAAI conference on artificial intelligence, 2018.
Tamal K. Dey and Yusu Wang. Computational Topology for Data Analysis. Cambridge University Press, 2022.
Tamal K Dey, Jian Sun, and Yusu Wang. Approximating loops in a shortest homology basis from point data. In Proceedings of the twenty-sixth annual symposium Computational geometry, pp- 166-175,1 2010.
Tamal K Dey, Anil N Hirani, and Bala Krishnamoorthy. Optimal homologous cycles, total unimod- ularity, and linear programming. SIAM Journal on Computing, 40(4):1026-1044, 2011.
Tamal K Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2587-2606. SIAM, 2020.
Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathe- matical Soc., 2010.
10

---

Under review as a conference paper at ICLR 2022
Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplifi- cation. In Proceedings 41st annual symposium on foundations of computer science, pp. 454-463. IEEE, 2000.
Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek. Amie: association rule mining under incomplete evidence in ontological knowledge bases. In Proceedings of the 22nd international conference on World Wide Web, pp. 413-422, 2013.
Christoph Hofer, Roland Kwitt, Mare Nicthammer, and Andreas Uhl. Deep learning with topo- logical signatures. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. (633-1643, 2017.
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference Machine Learning, pp. 4314 4323. PMLR, 2020.
Xiao Huang, Jingyuan Zhang, Dingeheng Li, and Ping Li. Knowledge graph embedding based question answering. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. (05-113,200 2019.
Michael Kampffmeyer, Yinbo Chen, Xiaodan Liang, Hao Wang. Yujia Zhang, and Eric P Xing. Rethinking knowledge graph propagation for zero-shot learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 11487-11496 1496, 2019.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02907, 2016.
Sijie Mai, Shuangjia Zheng, Yuedong Yang, and Haifeng Hu. Communicative message passing for inductive relation reasoning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 4294 4302, 2021.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 1506-1515, 2017.
Christian Meilicke, Manuel Fink, Yanjie Wang, Daniel Ruffinelli, Rainer Gemulla, and Heiner Stuckenschmidt. Fine-grained evaluation of rule-and embedding- systems for knowledge graph completion. In International Semantic Web Conference, pp. 3-20. Springer, 2018.
James R Munkres. Elements of algebraic topology. CRC press, 2018.
Ali Sadeghian, Mohammadreza Armandpour, Patrick Ding, and Daisy Zhe Wang. Drum: End-to- end diffcrentiable rule mining on knowledge graphs. arXiv preprint wxXiv:191.00005: 2019.
Zhiqing Sun, Shikhar Vashishth, Soumya Sanyal, Partha Talukdar, and Yiming Yang. A re-
evaluation of knowledge graph completion methods. arXiv preprint arXiv:1911.03903 2019.
Komal Teru, Etienne Denis, and Will Hamilton. Inductive relation prediction by subgraph reasoning. In International Conference on Machine Learning, pp. 9448-9457. PMLR, 2020.
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-66, 2015.
Shikhar Vashishth, Soumya Sanyal, Vikram Nitin, and Partha Talukdar. Composition multi- relational graph convolutional networks. International Conference on Learning Representa- tions, 2019.
Hongwei Wang, Fuzheng Zhang, Jialin Wang, Miao Zhao, Wenjie Li, Xing Xie, and Minyi Guo. Ripplenet: Propagating preferences the knowledge graph for recommender systems. In Proceedings of the 27th ACM International Conference on Information and Knowledge Manage- ment, pp. 417-426 2018.
11

---

Under review as a conference paper at ICLR 2022
Pengxiang Wu, Chao Chen, Yusu Wang, Shaoting Zhang, Changhe Yuan, Zhen Qian, Dimitris Metaxas, and Leon Axel. Optimal topological cycles and their application in cardiac trabecu- lae restoration. In International Conference Information Processing in Medical Imaging, pp- 80-92. Springer, 2017.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. arXiv preprint M.Kiv:177.006600 2017.
Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Link prediction with persistent homology: An interactive view. In International Conference on Machine Learning, pp. 11659- 11669, PMLR, 2021.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv: 1412.6554 2014.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. arXiv preprint urXiv:/702.0856 2017.
Ze Ye, Kin Sum Liu, Tengfei Ma, Jie Gao, and Chao Chen. Curvature graph network. In Interna- tional Conference on Learning Representations, 2019.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awe aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143. PMLR, 2019.
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. Variational reason- ing for question answering with knowledge graph. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Qi Zhao and Yusu Wang. Learning metrics for persistence-based summaries and applications for graph classification. Advances in Neural Information Processing Systems, 32:9859-9877 2019.
Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In International Conference Artificial Intelligence and Statistics, pp. 28922296222 2906. PMLR, 2020a.
Sendong Zhao, Bing Qin, Ting Liu, and Fei Wang. Biomedical knowledge graph refinement with embedding and logic rules. arXiv preprint arXiv:2012.01001,, 2020b.
Yongjun Zhu, Chao Che, Bo Jin, Ningrui Zhang, Chang Su, and Fei Wang. Knowledge-driver drug repurposing using a comprehensive drug knowledge graph. Health Informatics Journal, 26(4): 2737-2750, 2020.
A APPENDIX
A.1 AN EXAMPLE OF BR-LSTM CONSTRUCTION
In this section, we provide an example of the construction of BR-LSTM proposed in Section 4.1 Recall that in the generation of cycle feature, we tackle the input KG as directed graph with different edges/triplets associated with different relations. We assume that information edge/triplet flows along both directions, and encode the cycle in relation-aware manner. We denote by (u, r) E triplet connecting nodes and v with relation r. Here E is the set of all the triplets, we assume that an inverse triplet (v,r=l,u) is also included in the KG. Here r is defined as the inverse relation of r. Formally, we extend the triplet set of the KG as: E' = EEE (u,r=",,)](, r, v) E E}. An illustration is shown in Figure 3 Through the triplets in E', we can convert the rule shown in Figure (b) into two opposite sequences: (Cristiano, part_of, ManchesterUnnteel (Manchester, lives in Cristiano) and (Manchester United, part of Cristiano), (Cristiano, lives in, Manchester), (Manchester, located in -1, M ManchesterU nitte)))
an
(Manchester nited, located M Manchsterr)
12

---

Under review as a conference paper at ICLR 2022
part of
Cristi ano
part_ol of
Manch ester United
part of
located in
lives in
lives in
located in located_ing -n
lives in -1
Manch
ester
Figure 3: An example of BR-LSTM construction for Figure (b).
A.2 EXPERIMENTAL DETAILS.
Datasets. The datasets used in settings are subsets of KG WN18RR
Toutanova & Chen 2015),
FB15k-237 (Dettmers et al. 2018). and NELL-995 (iiong et al. 2017). Teru et al. (2020) generate these datasets by sampling disjoint subgraphs from the original datasets. For inductive relation prediction, the entities in the training set and the test set should not be overlapped. To evaluate the robustness of models, Teru al. (2020) sample four different pairs of training sets and test sets with the increasing number of nodes and edges. The details of the benchmark datasets are shown in Table 5
Experimental details. We adopt a 2-layer BR-LSTM to generate feature vectors for all the cycles in a cycle basis. Its output feature vector dimension is set to 20. 2-layer GCN (Kipf & Welling 2016) is adopted for the message passing of cycle basis, where ReLU serves the activation function between GCN layers. We combine 20 different shortest path trees to learn the good rules in the given datase In the cycle graph, select the top 2 most related cycles for each eycle. For all the modules, Adam is used as the optimizer, the dropout is set to 0.2, the epoch set to 100, the learning rate is 0.005 and the weight decay is 5e-5. We follow the settings in (Teru al. 2020 Mai et al. 202T). that is, to view all the existing triplets in KG as positive triplets and sample negative triplets by replacing the head (or tail) of the triplet with a uniformly sampled random entity. We use binary cross-entropy loss as the loss function with the negative sampling method. Considering that some inductive test sets contain few cycles, which leads the inconsistent performance between the inductive test sets and original training sets, we use the inductive training set as the validation set (while the training set and the test set are the same with (Teru al. 2020 Mai et al.) (02T)). We
In seldom cases such as NELL-995 v2. considering that we can significantly benefit from more shortest path trees, combine 50 cycle bases for relation prediction.
Table 5: Statistics of inductive benchmarks.
WNISRR
PB15K-237
NELI-995
RELATIONS
NODES
LINKS
RELATIONS
NODES
LINKS
RELATIONS
NODSE
LINKS
VI
TRAIN
9
2746
6678
183
2000
5226
14
10915
5540
TEST
225
TRAIN
10
2564
10109
TEST
10
2923
4863
176
2000
5092
79
4937
5521
V3
TRAIN
11
12078
32150
218
4000
22394
142
4647
20117
5084
7470
3000
9137
122
4921
9668
V4
9
3861
9842
222
5000
33916
77
2092
9289
TEST
9
7208
15157
204
3500
14554
3294
8520
13

---

Under review as a conference paper at ICLR 2022
run all the baseline methods with cluster of two Intel Xeon Gold 5128 processors, 192GB RAM, and one GeForce RTX 2080 Ti graphics card.
A.3 FURTHER EXPERIMENTS
Experiments with the same settings. In Section 5
we have compared the performance of our
model with the baseline results copied from (Teru et al. 2020 Mai et al. 202T]. as shown in Table I and [ For a fair comparison, we set Grail and CoMPILE as the same experimental settings as ours, and record the result in Table 6 and Table 7 Similar to the observation in Section S CBGNN consistently achieves the state-of-the-ee results in the evaluation Hit@ 10 scores and outperforms the majority of benchmark datasets when it comes to AUC-PR scores. The results further show the effectiveness of our proposed method.
Table 6: AUC-PR scores of inductive relation prediction, we keep the settings of baseline methods as the same as ours and run these methods five times for the average scores.
WNISRR
FB15K-237
NELL-995
Method
v2
GralL
96.09
95.92
85
94.02
83.98
90.66
84.74
82.34
82.88 78.07
92.35
91.45
COMPILE
98.56
99.98
94.04
99.85
83:45
92.17
90.91
91.39
94.07
95.69
83.40
CBGNN
98.63
97.62
89.76
97.80
96.34
96.53
96.38
95.23
82.79
94.78
96.29
94.02
Table @it@ 10 scores of inductive relation prediction, we keep the validation datasets of baseline methods the same as ours and run these methods five times for the average scores.
WNISRR
FB15K-237
NELL-995
Method
v1
v2
v3
v4
v2
v3
v1
v2
v3
v4
GralL.
84.04
81.63
60.65
75.34
64.63
82.00
82.54
78.16
55,00
93.27
89.74
73.94
CoMPILE
82.71
80.82
62.56
75.92
69.75
82.52
82,95
85.46
62.00
91.18
93.75
74.29
CBGNN
98.40
96.14
62.28
96.50
97.56
96.03
94.91
94.73
84,00
94.96
95.34
92.34
The influence of k. In this paragraph, we do experiments on the influence of the number of the short- est path trees which are used learn the suitable cycle basis. As is shown in Figure 4 CBGNN performs badly with single cycle basis. However, its performance grows quickly k increases from 1, and gradually converges after & large enough (10 for smaller graphs like WNISRR vl and FB15k-237 v1, and 20 for larger graphs like WNI8RR v2 and FB15k-237 v2).. The experiments show that is crucial to utilize multiple bases to guarantee better coverage. However, after k grows certain extent, the root nodes will be well spread out, and contain enough information to cover the whole graph. Therefore, the model hardly benefits from the increase of k after certain threshold. One important factor that may influence the threshold is the size of the input graph. For smaller graphs, we only needs a small number of SPT cycle bases to have a better cov- erage of the graph. While for larger graphs, may need more SPT cycle bases. But shown in Table and 20 SPT cycle bases are enough to gain state-of ofite--f--hhaaae the-art art results in most situations.
larger than
Evaluation of shortness. Recall that Section 3.2 we follow the Occam's razor principle and hypothesize that the desired cycle bases should generally contain short cycles. In this paragraph, we evaluate the shortness of the SPT cycle bases on various datasets and analyze the correlation be- tween the shortness and performance of different choices of cycle bases. To be specific, we draw his- tograms to evaluate the minimum length of cycles that pass a triplet. We compare different choices of cycle bases, including single cycle basis, 10 randomly chosen cycle bases, and 10 cycle bases chosen by the clustering algorithm, which are denoted by "Single". "Random- 10", and "Cluster- 10" respectively. The histograms shown in Figure [5] In the histogram, the x-axis denotes the mini- mum length of cycles that pass certain triplet, and the y-axis represents the proportion of triplets with certain minimum length of cycles among all triplets.
14

---

Under review as a conference paper at ICLR 2022
The influence of WN1BRR vL
The inflJence of on FB13k2377 v1
100
41
HOCPP scoees
80
30
75
30-
02
10
20
30
40
50
(a)
(b)
The influence k WN19RR v2
The influence FB15k
96
94
25-
Xumber
(c)
(d)
Figure& 4: The influence of & on WNI8RR v1, v2, and FB15k-237 v1, v2.
15

---

Under review as a conference paper at ICLR 2022
WN18RR v
VNN1RR v2
Single
Single
Rondomm Cleree11
Fandom 10
0.25
0.25
clusten-30
C70
0.7
Propordde
010
0.10
0.00
0.00
-0
Minimum
Mimimm Lonoth
(a)
(b)
fb237
0.30
0.30
Singee
Sngle Pandom 10
fondem 10
Clater-0
Clucted00
0.00
0.20
0.15
0.15
6.05
0.35
-0
-0
Minimum Le of cydle.
Minimam Length cycles
(c)
(d)
Figure 5: Histogram of shortness different datasets
As shown in Figure 5 the cycle bases selected by the clustering algorithm generally contain small cycles compared with the randomly selected cycle bases or the single cycle basis. We can find that in Table CBGNN outperforms 1BGNN-Randon on most datasets. Another interesting observation that in Figure 5 (d), the randomly selected cycle bases perform comparably with the cycle bases generated using the clustering algorithm in terms of shortness Table the performance of CBGNN Random slightly beat CBGNN on NELL-995 vl. The above observations show the correlation between the shortness of cycle bases and their performance.
NELL-995 vl. Recall that in
16


Reviews:
[{"review_id": "_knfJTf-7xN", "reviewer": "Reviewer_pNaT", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "strengths:\n- The paper is well-written and easy to follow.\n- Treating rule learning as a cycle learning problem is very interesting and novel. \n- The proposed method is shown to be effective and efficient. In terms of experimetns, the paper includes detailed experimental setup, a comprehensive set of baselines and ablation studies.\n\nweaknesses: \n- I can't understand why there is difference between Table 1/2 and Table 6/7. Is this due to random seed? Some of the entries have really big differences. For example, (NELL-995 v1, CoMPILE) in Table 7 and Table 2 are 62.00 and 58.38 respectively. Do we need some statistical testing here or reporting the variance among different runs?\n- The paper argues that the proposed method might work better on datasets with complex semantics, i.e. with more complicated relations. Given this, I would suggest running experiments on datasets like https://allenai.org/data/tuple-kb, which contains more than 1000 relations. \n", "summary_of_the_paper": "This paper addresses the problem of inductive relation prediction in knowledge graphs. The authors propose a novel GNN-based method. Treating rule learning as a cycle learning problem is very interesting. The experiments on popular knowledge graph completion datasets verify the effectiveness of the proposed method. ", "summary_of_the_review": "The paper proposes to treat rule learning as cycle learning in knowledge graphs. The approach is very interesting and novel with solid experiments showing its effectiveness. I would suggest accepting this paper. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ORKUiXQx6jR", "reviewer": "Reviewer_vHmE", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Overall the paper is well-written and easy to follow. I find the idea of viewing relational paths as graph cycles to be interesting. However, despite the authors claiming that cycle representation is distinct from the path representation in multi-hop reasoning methods such as NeuralLP, it's worth noting that the path representation is guaranteed to be a cycle in these works (as a chain rule). Therefore, the search space of the two representations is in fact the same. I would suggest the author carefully address the claims and comparisons with the multi-hop reasoning methods in sections 1 and 2.\n\n\nSome of the concepts and design choices need more elaborations and justifications:\n - The proposed method generates nodes with the spectral clustering algorithm. It's unclear why this particular algorithm is picked and how sensitive is the framework to the choice of clustering algorithms.\n - The authors generate cycles with SPT. However, other than claiming it follows Occam’s razor principle, there is no theoretical analysis or direct empirical experiment that shows the space always contains the answer cycle to the query.\n - The authors claim the cycle incidence matrix implicitly encodes interaction between the cycles. However, it's unclear why such interaction information is needed for answering the query. To justify this, the author should compare the method with a simpler baseline without the incidence matrix.\n\nCycle extraction only considers the KG's topological structure, treating the KG as an undirected graph with no edge label. I'm concerned about this approach, as the direction and the type of edge are critical to the KG. In fact, in the feature generation phase, the edge direction and type are indeed taken into consideration. It's unclear to me why not use this information at the very beginning.\n\nBesides the aforementioned issues, my main concern with this work is that the proposed framework is unnecessarily complicated.\n - It generates cycles with clustering and SPT -> computes cycle incidence matrix -> generates cycle features with bi-LSTM -> builds GNN for each cycle basis -> computes cycle confidence with GNN -> aggregate final scores with weighted sum.\n - The current ablation study is far from sufficient to justify why this framework has to be this complicated.\n - For example, one can build a frequency-based baseline with cycles generated from SPT and compare it with the proposed method.\n - For the cycle incidence matrix, one can build a baseline without the matrix.\n - To predict the edges, one can also build a simpler classifier right on top of the bi-LSTM model. It's critical to show that the additional GNN structure is indeed necessary.\n\nI'm also concerned about the method scalability. The computational costs of the proposed method grow quickly w.r.t |V|, |E| and beta. However, the largest dataset FB15K v5 only contains 5K nodes and 33K edges which is significantly smaller than the original FB15K dataset which contains 14K nodes and 272K edges. \n - It's unclear to me what does the run time shown in Table 3 correspond to. Does the time correspond to the end-to-end processing time of CBGNN? Or it is the inference time of the GNN module alone?\n\nThe analysis on the influence of k is weak. The experiment is only conducted on the smallest subset of FB15K and WN18. Instead, the authors should analyze the necessary k values against a set of KGs of increasing sizes and show how well does the k scales w.r.t |V|, |E| and beta.", "summary_of_the_paper": "The paper proposes a GNN framework to solve the inductive relation prediction problem, namely CBGNN. The framework consists of three modules: 1)  a cycle extraction module that generates cycles graphs with clustering and SPT tree search; 2) a bi-directional LSTM that converts a cycle of triplets into a feature vector, and 3) a GNN model that learns the triplet confidence using the feature vectors. In experiments, the proposed method is evaluated with a set of differentiable ILP methods and GNN methods. Some ablation studies are conducted to validate the cycle extraction module and feature generation module.\n", "summary_of_the_review": "In summary, although the idea of using cycle representation is interesting. The proposed method is unnecessarily complicated. And the current draft lacks too many justifications to the components in the proposed method. At this point, I would recommend rejection but I'm happy to raise my score if the authors address the aforementioned concerns.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "BkyCap1VE0h", "reviewer": "Reviewer_weC8", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "The approach put forward in this paper is not convincing since it's convoluted (W1), neither well-argued for and nor convincing (W2), partly unclear (W3), there is no analysis or theoretical insight (W4), and practical benefits and costs ultimately remain unclear (W5).\n\nW1 (convoluted). In a nutshell, (1) run spectral clustering to obtain central nodes, (2) compute shortest-path trees from these nodes, (3) construct a \"cycle basis\" from each tree, (4) run a BILSTM to encode each cycle in the basis, (5) construct a cycle graph from each cycle basis, (6) run a GNN to predict cycle confidences, (7) repeat (1)-(6) k times and average, (8) predict the cycle confidence of the highest-weighted cycle that contains a triple as the triple confidence, (9) train this using negative sampling.\n\nW2 (neither well-argued for and nor convincing). Many of the steps taken in this approach are heuristic and justified in a rather hand-wavy away; even key points (such as \"what is a good cycle\" and \"why a complete cycle basis\") are not precisely described. There is not clear, convincing argument for the approach. In fact, the ultimate approach suggests that if there is a single triple on a cycle that obtains a high-confidence prediction, so do all other triples on the cycle. This point alone makes the entire approach questionable: \"son(x,y) and son(y,z) -> related(x, z)\" (always true) should have a different confidence than \"related(x,z) and son(y, z) -> son(x,y)\" (clearly not always true). Another point is that it is known that useful rules may not necessarily be paths; e.g., they may require constants (e.g., \"child(x,y) and gender(x,'male')->son(x,y)\").\n\nW3 (partly unclear). The paper talks largely about how cycle bases are constructed for a given KG, i.e., for the positive edges. But what happens with the negative edges? They clearly do not appear in any cycle of the cycle base. So how is prediction actually performed +++? For the test set, is leakage of information from the test triples prevented? (+++ needs to be performed for each test triple separately, hiding all other test triples---else information is leaked.)\n\nW4 (no analysis or theoretical insight). Expressivity or properties of the proposed method are neither discussed nor rigidly analyzed.\n\nW5 (practical benefits and costs unclear). First, the method does not fully enclose its cost. What is the time/space requirement for each of the steps 1-9 above? It seems like the method is very costly and does not scale to large graphs. It's unclear why there would be any performance benefit compared to just using a GNN (since it's a part of the proposed method and the graph is larger). Second, it's completely unclear why the proposed method shows strong empirical results; there is no discussion or analysis in the paper. Except there is test leakage (e.g., by constructing a single graph with all test triples; see also +++ in W3), in which case the proposed method is obviously faster and likely to be much better empirically. Apart from the points above, the usefulness of the setting used in the study is mysterious to me (it's taken from prior work): clearly, in the context of the knowledge graphs considered in the experimental, there is entity overlap between train and test (e.g., the higher-level wordnet synsets or the types and locations for Freebase). So why perform reasoning without? The resulting graphs are likely to be quite unnatural/unrealistic.\n", "summary_of_the_paper": "The paper proposes an approach to predict the confidence of missing edges in a knowledge graph in the purely inductive setting, in which the test knowledge graph does not share any entities with the training graph. The key idea is to use cycles (or more specifically, cycle bases) as the basis for such reasoning; the paper builds and evaluates a model around this idea.\n", "summary_of_the_review": "The approach put forward in this paper is not convincing since it's convoluted (W1), neither well-argued for and nor convincing (W2), partly unclear (W3), there is no analysis or theoretical insight (W4), and practical benefits and costs ultimately remain unclear (W5).\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "AFZTnEIfi6U", "reviewer": "Reviewer_YAZM", "summary": "", "questions": "", "limitations": "", "rating": 3, "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* The problem of learning rules for inductive relation prediction is important. \n* The authors provided another view, circle-based rules, about learning logical rules.\n* The authors conduct experiments on benchmarks and the method achieves good performance.\n\nweaknesses:\n* It’s not clear what can be done by the proposed circle-based rules but cannot be done by previous chain-based rules. Actually, all circle-based rules can be regarded by chain-like rules, and by optimizing the scores of chain-like rules, one can learn high-quality rules. \n* Suppose we have learned a circle (A, B, C), if we want to rewrite it as a rule, which of the following should we use?\nA, B->C; A, C->B; B, C->A. \nIn my opinion, they are significantly different, but it seems that the proposed method cannot distinguish them based on the circle-based methods. \n* The training time and the testing time should be reported separately. \n* It would be better to use early-stopping rather than training with a fixed number of epochs for performance comparison. \n* “We hypothesize that the good cycles tend to be short, and the desired cycle bases should generally contain short cycles.”\nPersonally, I don’t think it is convincing to me, because some rules are long but interesting. Actually, according to previous literature[1,2,3], the rules with lengths of 1,2,3 are all important. The examples are as follows,\nfilm_edited_by(B,A)←nominated_for(A,B);\n partially_contains(C,A)←contains(B,A) ∧ contains(B,C); \nPerson(X) ← Car(Y1) ∧ Inside(X, Y1) ∧On(Y2, X) ∧ Clothing(Y2). \n* It would be better if the authors also compare their method with NLIL[3], which can learn more complex rules. \n* Minor issue (typo):\nO(|E||V|).\n\n\n[1] Yang, Fan, Zhilin Yang, and William W. Cohen. \"Differentiable learning of logical rules for knowledge base reasoning.\" Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017.\n\n[2] Sadeghian, Ali, et al. \"DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs.\" Advances in Neural Information Processing Systems 32 (2019): 15347-15357.\n\n[3] Yang, Yuan, and Le Song. \"Learn to Explain Efficiently via Neural Logic Inductive Learning.\" International Conference on Learning Representations. 2019.\n\n", "summary_of_the_paper": "This paper focuses on the problem of inductive relational prediction for KG completion. Previous works often regard the rules as paths, different from those works, this paper regards the rules as circles. Based on that, the authors propose a GCN-based method for learning rules. They conduct experiments on the public datasets of inductive relation prediction and the proposed method achieves better or similar performance compared to best baselines. ", "summary_of_the_review": "The paper proposed a circle-based method for rule learning, which is an interesting view. However, some claims (e.g., shorter rules are better) are not convincing, and the motivation of such a design is not clear. There is no substantial difference between the rule learned by this method and the previous works, and the search space of rules is even smaller (e.g., compared to NLIL[3]). I recommend the authors clarify these issues. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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 proposes a new approach to inductive rule prediction for knowledge graph completion. Reviewers highlighted as strengths that the paper proposes an interesting approach to an important problem that is relevant for the ICLR community. However, reviewers raised also concerns regarding model design and correctness as well as clarity of presentation (e.g., motivation, analysis, comparison to related work, evaluation). After author response and discussion, all reviewers and the AC agree that the paper is not yet ready for publication at ICLR due to the aforementioned issues.
Decision: Reject