Less is More: One-shot Subgraph Reasoning on Large-scale Knowledge Graphs
Authors: Zhanke Zhou
Yongqi Zhang
Jiangchao Yao
quanming yao
Bo Han
Venue: ICLR 2024 poster (2024)
Keywords: knowledge graph reasoning
graph sampling
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: We propose the one-shot subgraph reasoning to achieve efficient as well as adaptive reasoning on knowledge graphs

Abstract: To deduce new facts on a knowledge graph (KG), a link predictor learns from the graph structure and collects local evidence to find the answer to a given query. However, existing methods suffer from a severe scalability problem due to the utilization of the whole KG for prediction, which hinders their promise on large scale KGs and cannot be directly addressed by vanilla sampling methods. In this work, we propose the one-shot-subgraph link prediction to achieve efficient and adaptive prediction. The design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps, i.e., (i) extracting only one subgraph according to the query and (ii) predicting on this single, query dependent subgraph. We reveal that the non-parametric and computation-efficient heuristics Personalized PageRank (PPR) can effectively identify the potential answers and supporting evidence. With efficient subgraph-based prediction, we further introduce the automated searching of the optimal configurations in both data and model spaces. Empirically, we achieve promoted efficiency and leading performances on five large-scale benchmarks. The code is publicly available at: https://github.com/tmlr-group/one-shot-subgraph.

Published as a conference paper at ICLR 2024
LESS IS MORE: ONE-SHOT-SUBGRAPH LINK PREDICTION ON LARGE-SCALE KNOWLEDGE GRAPHS
Zhanke Zhou' Yonggi Zhang² Jiangchao Yao?
Quanming Yao
Bo Han 1
TMLR Group, Hong Kong Baptist University
The Hong Kong University of Science and Technology (Guangzhou)
CMICC Shanghai Jiao Tong University
*Tsinghua University
(cszkzhou, bhanml) @ @comp.hkbu cemnp.hkbu.edu.he edu.hk yzhangee @ connect.ust.hk
sunarker@sjuu.et sjw.edu.cnn qyaoaa @ tsinghua.edu.cn
ABSTRACT
To deduce new facts a knowledge graph (KG), link predictor learns from the graph structure and collects local evidence to find the answer to a given query. However, existing methods suffer from a severe scalability problem due the utilization the whole KG for prediction, which hinders their promise on large- scale KGs and cannot be directly addressed by vanilla sampling methods. In this work, we propose the one-shot-subgrapt link prediction to achieve efficient and adaptive prediction. The design principle is that, instead of directly acting on the whole KG, the prediction procedure is decoupled into two steps, i.e., (i) extracting only one subgraph according to the query and (ii) predicting on this single, query- dependent subgraph. We reveal that the non-pane con-parametric and computation-efins -ffficcent heuristics Personalized PageRank (PPR) can effectively identify the potential answers and supporting evidence. With efficient subgraph-based prediction, we further introduce the automated searching of the optimal configurations in both data and model spaces. Empirically, achieve promoted efficiency and leading performances on five large-scale benchmarks. The code is publicly available at: https: /ttp://gitttt///t com/tm /mml ceaml--groupe g-ggrooooooeeeee shot sshottsuugrass subgraph.
INTRODUCTION
knowledge graph (KG) is graph-structural data with relational facts (Battaglia et al., 2018; Ji et al., 2020: Chen et al., 2020), based on which, one can conduct link prediction to deduce new facts from existing ones. The typical problem is to find the answer entity for the specific query, e.g., to find the answer Los Angeles to the query (LeBron, lives_ in, 2). With continuous advances in recent years, the link prediction on KG has been widely applied recommendation systems (Cao et al., 2019; Wang et al., 2019), online question answering (Huang et al., 2019), and drug discovery (Yu et al., 2021).
The prediction system learns from the local structure of a KG, where existing methods can be generally summarized as two categories: (1) semantic models that implicitly capture the local evidence through learning the low-dimensional embeddings of entities and relations (Bordes et al., 2013; Dettmers al., 2017; Zhang al., 2019; Wang et al., 2017); and (2) structural models that explicitly explore the KG's structure based on relational paths or graphs with recurrent neural networks (RNNs) or graph neural networks (GNNs) (Das et al., 2017: Schlichtkrull et al., 2018: Sadeghian al., 2019; Vashishth et al., 2019; Teru et al., 2020; Qu et al., 2021; Zhu et al., 2021; Zhang & Yao, 2022).
Although achieving leading performances, these structural models suffer from severe scalability problem as the entire KG has been potentially or progressively taken for prediction. This inefficient manner hinders their application and optimization on large-scale KGs, e.g., OGB (Hu et al., 2020). Thus, it raises an open question: Is all the information necessary for prediction on knowledge graphs? Intuitively, only partial knowledge stored in the human brain is relevant a given question, which is extracted by recalling and then utilized in the careful thinking procedure. Similarly, generating candidates and then ranking promising ones are common practices in large-scale recommendation systems with millions even billions of users (Cheng et al., 2016; Covington et al., 2016). These facts motivate us to conduct efficient link prediction with an effective sampling mechanism for KGs.
Correspondence Bo Han (bhanml @ www./c/mm..uuucooooo hkw...du.hkk..

---

Published as a conference paper at ICLR 2024
In this work, we propose the novel one-shot-subgraph link prediction knowledge graph. This idea paves a new way to alleviate the scalability problem of existing KG methods from a data-centric perspective: decoupling the prediction procedure into two steps with corresponding sampler and a predictor. Thereby, the prediction of a specific query is conducted by (i) fast sampling of one query-dependent subgraph with the sampler and (ii) slow prediction on the subgraph with predictor.
Nevertheless, it is non-trivial to achieve efficient and effective link prediction on large-scale KGs due to the two major challenges. (I) Sampling speed and quality: The fast sampling of the one-shot sampler should be capable of covering the essential evidence and potential answers to support the query. (2) Joint optimization: The sampler and predictor should be optimized jointly to avoid trivial solutions and to guarantee the expressiveness and udaptivity of the overall model to specific KG.
To solve these challenges technically, we first implement the one-shot-subgraph link prediction by the non-parametric and computation-effiiinn
Personalized PageRank (PPR), which is capable of effectively identifying the potential answers without requiring learning. With the efficient subgraph- based prediction, we further propose to search the data-adaptive configurations in both data and model spaces. We show unnecessary to utilize the whole KG inference; meanwhile, only a relatively small proportion of information (e.g., 10% of entities) is sufficient. Our main contributions are:
We conceptually formalize the new manner of one-shot shot-subbraph link prediction on KGs (Sec. 3) and technically instantiate it with efficient heuristic samplers and powerful KG predictors (Sec. 4.1).
We solve non-trivial and bi-level optimization problem of searching the optimal configurations in both data and model spaces (Sec. 4.2) and theoretically analyze the extrapolation power (Sec. 4.3).
We conduct extensive experiments on five large-scale datasets and achieve an average of 94.4% improvement in efficiency of prediction and 6.9% promotion in effectiveness of prediction (Sec. 5).
2 PRELIMINARIES
Notations. A knowledge graph is denoted as G = (V, E). where the entity set V, the relation set R. and factual edge set & ((,, xr vV, E R). Here, fact is formed denoted as (xc, v). Besides, a sampled subgraph of 9 is denoted as G. = (Vs, RR, E,). satisfying that V. S.V. V, R. S R, E, CE. The atomic problem of link prediction is denoted as a query (u, q, ?). i.e., given the query entity u and query relation g, to find the answer entity u, making (u, q, v) valid.
triplet and
Semantic models encode entities and relations to low-dimensional entity embeddings Hy E RIMDD and relation embeddings H E R RR)., where D, are dimensions. A scoring function fo. e.g., TranSE (Bordes et al., 2013) QuatE (Zhang et al., 2019), is necessary here to quantify the plausibility of a query triplet (u, q. v) with the learned embeddings (h.,, hgg h.)) as fo (R. IR Dr. ,I. P. >
Efficient semantic models aim to reduce the size of entity embeddings. NodePiece (Galkin et al., 2022) proposes anchor-based approach that obtains fixed-size embeddings as G -o ÿy E ERR and inference (A, .) [o.(u..), Y, where y are the scores of candidate answers, and N < MV] Designed to reduce the embedding size, NodePiece cannot reduce the graph size for structural models.
Structural models are based on relational paths or graphs for link prediction. Wherein the path-based models, e.g., MINERVA (Das et al., 2017), DRUM (Sadeghian et al., 2019), and RNNLogic (Qu et al., 2021), aim learn probabilistic and logical rules and well capture the sequential patterns in KGs. The graph-based models such as R-GCN (Schlichtkrull et al., 2018) and CompGCN (Vashishth et al., 2019) propagate the low-level entity embeddings among the neighboring entities to obtain high-level embeddings. Recent methods NBFNet (Zhu et al., 2021) and RED-GN) (Zhang & Yao, 2022) progressively propagate from u to its neighborhood in a
seart-hg (BFS) manner.
Sampling- structural models adopt graph sampling approaches to decrease the computation complexity, which can be categorized into two-fold as follows. First, subgraph-wise methods such as Grall. (Teru et al., 2020) and COMPILE (Mai et al., 2021) extract enclosing subgraphs between query entity u and each candidate answer v. Second, layer-wise sampling methods extract a subgraph for message propagation in each layer of a model. Wherein designed for node-level tasks on homogeneous graphs, GraphSAGE (Hamilton et al., 2017) and FastGCN (Chen et al., 2018) randomly sample neighbors around the query entity. While the KG sampling methods, e.g., DPMPN (Xu et al., 2019), AdaProp (Zhang et al., 2023c), and AStarNet (Zhu et al., 2023), extract a learnable subgraph in f-th layer by the GNN model in 6-th layer, coupling the procedures of sampling and prediction.
2

---

Published as a conference paper at ICLR 2024
3 One-shot-subgrapp LINK PREDICTION ON KNOWLEDGE GRAPHS
To achieve efficient link prediction, we conceptually design the one-shot-subgree manner that avoids directly predicting with the entire KG. We formalize this new manner in the following Def. 1. Definition (One-shot-subgraph Link Prediction on Knowledge Graphs). Instead of directly predict- ing on the original graph G. the prediction procedure is decoupled to two-fold: (1) one-shol sampling of query-dependent subgraph and (2) prediction on this subgraph. The prediction pipeline becomes
g (o.(u.)), Go J0p Y,
(1) <\EE) conditioned
where the sampler 96 generates only one subgraph Gs (satisfies V.l < (V) on the given query (u. q, ?). Based on subgraph Gs. the predictor fe outputs the final predictions Y.
Comparison with existing manners of prediction. In brief, semantic models follow the manner of encoding the entire G to the embeddings H (Hy, HR) and prediction (inference) without G, i.e.,
H fo.(u.0) Y, s.t. I.L.! -
which is darameter-expensivee especially when encountering large-scale graph with a large entity set. On the other hand, structural models adopt the way of learning and prediction with G. i.e.,
g fo.(u.n) Y,
that directly or progressively conduct prediction with the entire graph G. Namely, all the entities and edges can be potentially taken in the prediction of one query, which is computation-cxpensie contrast, our proposed one-shot prediction manner (Def. 1) enjoys the advantages & as follows.
By
Advantage 1 (Low complexity of computation and parameter). The one- one-shot-subee shot--obbbugphh model is (I) computation-eeficient the extracted subgraph is much smaller than the original graph, i.e. [Val < [V] and |&,] < { and (2) purameter-eficient: it avoids learning the expensive entilies' embeddings. Advantage 2 (Flexible propagation scope). The scope here refers the range of message propagation starting from the query entity u. Normally, an L-layer structural method will propagate to the full L-hop neighbors of u. By contrast, the adopted one-shot sampling enables the bound of propagation scope within the extracted subgraph, where the scope is decoupled from the model's 's depth L.
Comparison with existing sampling methods. Although promising to the scalability issue, existing sampling methods for structural models are not efficient or effective enough for learning and prediction on lcage KGs. To be specific, the random layer-wise sampling methods cannot guarantee the coverage of answer entities, L.e., 1(v Vu). J. By contrast, the learnable layer-wise sampling methods extract the query depenneen subgraph G:(² in l-th layer via the GNN model f(() in E-th layer as
g 160h (u.4), G(11) 10th (u.a), g( + .... G(L-1) 16th (u.a), Y.
coupling the sampling and prediction procedures that (1) are bundled with specific architectures and (2) with extra computation cost in the layer-wise sampling operation. Besides, the subgraph-wise sampling methods extract the enclosing subgraphs between query entity u and each candidate answer e V. and then independently reason on each of these subgraphs to obtain the final prediction Y as
(Y, (m.")) g!u.e) fo.(u.g.") Y VEV
Note these approaches are extremely expensive on large-scale graphs, as each candidate (u, v) corre- sponds to subgraph to be scored. By contrast, one-shot sampling manner enjoys the advantage 3. Advantage 3 (High efficiency in subgraph sampling). Our proposed prediction manner requires only one subgraph for answering one query, which is expected to cover all the potential answers and supporting facts. Notably, this query-specific subgraph is extracted in a one-shot and decoupled manner that does not involve the predictor, reducing the computation cost in subgraph sampling.
INSTANTIATING THE ONE-SSOTT-UURGEER
LINK PREDICTION
Note that it is non-trivial to achieve Def. 1, wherein (i) the implementation of sampler, (ii) the architecture of predictor, and (iii) the method to optimize these two modules need to be figured out. Here, the major challenge lies in the sampler, which is required to be efficient, query-dependent, and sttal-structure- preeuurreppeeevving....... In this section, we elaborate on the detailed implementation (Sec. 4.1), set up bi-level problem for optimization (Sec. 4.2), and investigate the extrapolation power (Sec. 4.3).
3

---

Published as a conference paper at ICLR 2024
Original
Query-dependent subgraph Sa
Reasoning soores
One-shot Subgraph Reasoning
Optimization Objective
(u.q.?)
Σ (
g
Gs
Y
max Fg
M M(fo-GG))
96
fe
Σ Ennis
s. Gs
Pg.
arg min
Lets (ola)
Fast sampling
Slow reasoning
The proposed framework of one-shot-subgraph link prediction. Specifically, (1) the sampler Is extracts a subgraph G3 from the whole graph G with regard to the given query, and (2) the predictor
Figure I:
fo conducts deliberative prediction the extracted subgraph G, and obtains the final predictions Y
4.1 REALIZATION: THREE-STEE PREDICTION WITH PERSONALIZED PAGERANK
Overview. As illustrated in Fig. 1, the three key steps of our method are (1) generating the sampling distribution Fg by sampler Iep- (2) sampling subgraph from the distribution G3 Pg with top-K entities and edges, and (3) predicting on the subgraph G3 and acquiring the final prediction Ý by predictor So- The three-step procedure is summarized in Algorithm and elaborated
follows.
Step-1. Generate sampling distribution. Previous studies show that e is generally near to u (Zhu al., 2021; Zhang & Yao, 2022), and the relational paths connecting u and that support the query also lie close to u (Das et al., 2017; Sadeghian et al., 2019). To efficiently capture the local evidence of u, choose the heuristic Personalized PageRank (PPR) (Page et al., 1999; Jeh & Widom, 2003) as the sampling indicator. Note that PPR is not only efficient for its non non-parametric nature but also query-dependent and local-struee www.ssttuuurpreeeec preseervng for its single-source scoring that starts from u.
Specifically, PPR starts propagation from to evaluate the importance of each neighbor of u and generates the PageRank scores as the sampling probability that encodes the local neighborhood the query entity u. Besides, it can also preserve the locality and connectivity of subgraphs by leveraging the information from a large neighborhood. Given a query entity we obtain the probability E IR
Non-paramet parmetrrai indi cator: (b+1) a + (1 at) D-1 (*)
(2)
by iteratively updating the scores up to K- 100 steps to approximate the converged scores efficiently. Here. the initial score (0)
[u) (0, 1}12 indicates the query entity
be explored. The
woo-dieensional degree matrix D R x and adjacency matrix A {0, 13 (PI(D together work as the transition matrix, wherein A;j = means an edge () E and D
= degree if else D.j = The damping coefficient (= 0.85 by default) controls the differentiation degree.
Step-2. Extract subgraph. Based on the PPR scores (Eqn. 2). the subgraph 9, 3V- &ss R.) (where R, R) is extracted with the most important entities and edges. Denoting the sampling ratios of entities and edges as ri. r (0, 1] that depend on the query relation we sample [V.]= = x [V] entities and = x|E edges from the full graph G. With the TopK [D, P. K) operation that picks up top-K K elements from candidate D w.E.. probability P, the entities V. and edges &, are given as
Entity Sampling: V3 + TT-TTop// V, K K=
Edge Sampling: E, - Topk E, (p..p.: oE o,. (E,,,)) 1=12
Step-3. Reason on the subgraph. From the model's perspective, we build the configuration space of the predictor and further utilize the advantages of existing structural models introduced in Sec. Three query-dependent message functions MESS (-) considered, including DRUM, NBFNet. and RED-GNN, which are elaborated in Appendix. B. Note the effective message is propagated from u to the sampled entities
V., Generally, the layer-wise updating of representations is formulated
4

---

Published as a conference paper at ICLR 2024
Indicating: :h <1 u), Propagation: (e+1) <DROPOOUT ACT (MEGsss h (
(4)
where 1(0 u) is the indicator function that only labels the query entity in query-dependent manner. After a L-layer propagation, the predictor outputs the final score D. of each entity oe V,
based on their representations (L) as y. = Readout(h, (L)
(ho ( E R. The loss function Lats binary cross-entropy loss on all the sampled
adopted in the training phase is the commonly-un entities. Namely, Lote = Eoev, Yo (og(ū.) + vo) log (1-9.), where yo = if o= else yo = 0.
Algorithm I One-shot--uubraaph Link Prediction on Knowledge Graphs
Require: KG g = (V. R), degree matrix D E R adjacency matrix A E [0.1) VIxM damping coefficient a, maximun PPR iterations K query (u, q, ?), sampler Iø. predictor fo.
1: # Step-1. Generate sampling distribution
2: initialize s + (u), p0) + (u).
3: for k k= 11...... K do
4: p p(++1) + a.c. + (1 (1-ay) a) A-1A.p
5: end for
6: # Step-2. Extract a subgraph G,
7: V. t TopK(V, p, X=r(
8: & - TopK(E, {P..Po : 14 ().r) K K x(E).
9: # Step-3. Reason the subgraph
initialize representations h 10==))
11: for l
do
he DDRCPOOTT/CCTAAAGSSEEESSSS (t-1) .h. (e-1) ( ( EE.)))
13: end for
14: return Prediction g. = -Redduut (hō ( th (e for each entity o E V..
4.2 OPTIMIZATION: EFFICIENT SEARCHING FOR DATA-ADAPTIVE CONFIGURATIONS
Search space. Note that hyperparameters (ri rg) and I, play important roles in Algorithm 1. Analytically, a larger subgraph with larger rg does not indicate a better performance, as more irrelevant information is also covered. Besides, deeper model with larger L can capture more complex patterns but is more likely to suffer from the over-smoothing problem (Oono & Suzuki, 2019). Overall, the (ri, r are for sampler's 's syperpparameters @hyper. In addition L, predictor's hyper-parameters Oyyper contain several intra-layer or inter-layer designs, as illustrated in Fig. 2(a).
Search problem. Next, we propose the bi-level optimization problem to adaptively search for the optimal configuration (diyper: 6i (hyper) of design choices on specific KG, namely,
Khyper arg max M(f ( I Eval).
chaper
s.t. 0 hyper arg max M[ (i
( ) Dehreses Eval
Oryeer
where the performance measurement M can be Mean Reciprocal Ranking (MRR) or Hits Note the non-parametric sampler 94 only contains hyper-parameters Φhyper- As for predictor fo. its = (Onyper: 0ream) also includes learnable Oteam that 0- -. arg ming Lets(J (J 0 9 D grain)
Search algorithm. Directly searching both data and model spaces is expensive due to the large space size and data scale. Hence, we split the search into two sub-processes as Fig. 2(b), i.e.,
First, we freeze the sampler 96 (with constant (hyper) to search for the optimal predictor so- with (1) the popee-parameters optimization for 0 hyper and (2) the stochastic gradient descent for Oiem..
Then, freeze the predictor fe- and search for the optimal sampler 94- simplifying to pure hyper- parameters optimization for &hyper in a zero- gero-gradient manner with low computation complexity.
Specifically, we follow the sequential model-based Bayesian Optimization (BO) (Bergstra et al., 2013; Hutter al., 2011) to obtain &hyyer and Biyper- Random forest (RF) (Breiman, 2001) chosen the surrogate model because has stronger power for approximating the complex and discrete
5

---

Published as a conference paper at ICLR 2024
Representation
Input Ss
Φ Phyper
Ilarnn P hypper)
Initialization
W1 lateling
Seurch with BO
retational labeling
Layer-1 prop.
Messuge Function (MESS) RED GNN, NDUNet, DRUM
Φ hyper
0 Tearn hhyper
Layer-wise Shorteut
Search
Activate Function (ACT)
with BO
Connection
Idemiity Relu, Tanh
Φ Phyper
0 learn 0 hypper
Aggregation Function (AGG) Max, Meun, Sum
(b) the two-step searching
Layen-l. prop.
Dropout Rate (0.0.5)
(u, (u.g.?)
Representation
Dimension Size 64, 128
G
9s
Concatenution
9
fo
Readout Function
Dot Product
Linear
Reudout
Output P
gtrain
gobs
Equery
(a) search space of Onyper
(c) the edge split trick
Figure 2: Illustrations of the optimization procedure. Note the predictor in (a) is with mhype--prameee and learnable parameters in each layer's propagation, and the (1.) indicates the representations in L-th layer. By contrast, the sampler only contains hyper-ppraneee srper-parameters as it does not require learning.
curvature (Grinsztajn et al., 2022), compared with other common surrogates, e.g., Gaussian Process (GP) (Williams & Rasmussen, 1995) or Multi-layer Perceptron (MLP) (Gardner & Dorling, 1998).
Acceleration in searching. We adopt data split trick that balances observations and predictions. saves time as the training does not necessarily traverse all the training facts. Specifically, partial training facts are sampled as training queries while the others are treated as observations, i.e., we randomly separate the training facts into two parts as Etrin__ g Uquueyy where the overall prediction system So Ie takes gobs as input and then predicts Equery (see Fig. 2(c)). Here, the split ratio split is to balance the sizes of these two parts as ppplit = /1 Thus, the training becomes 0" = arg ming (() Leta (Go(Gs), v) with the split query edges Equery where G. ( u, 4) with the split observation edges gobs, More technical details can be found in the Appendix. B.
4.3 THEORY: THE EXTRAPOLATION POWER OF ONE-SHOT-SUBGREE
LINK PREDICTION
Further, we investigate the extrapolation power of link prediction across graph scales, i.e. training and inference on different scales of graphs. For example, training on small subgraphs Grain and testing large subgraphs Ghrat where the ratio of entities VV /Iv! >> 1. This scenario is practical for recommendation systems on social networks that can encounter much larger graphs in the testing phase. Intuitively, training on smaller Grain can time for its faster convergence subgraphs (Shi et al., 2023), while predicting on larger gteal might gain promotion for more support of facts in Gres
Nonetheless, the Theorem I below proves that link prediction can become unreliable the test graph grows. That is, if we use a small subgraph for training and a large subgraph for testing, the predictor will struggle to give different predictions within and across sampling distributions by g, when these probabilities are arbitrarily different in the underlying graph model. Our empirical results in Fig. 4 support this theoretical finding. Hence, it necessary to strike balance of subgraphs scale.
Theorem 1. Let Giniin ~ Pg and Giest ~ P& be the training and testing graphs that are sampled from distribution Pg. Consider any two test entities u. U Viest for which we make prediction decision of fact (u, q, v) with the predictor fe. i.e., y fo( fT. Let Glest be large enough to satisfy VVVa= /oog(2 2 4/2/dmm.. where dmin is the constant of graphon degree (Diaconis & Janson, 2007). Then, for an arbitrary threshold T E [0, 1), the testing subgraph G satisfies that
Viest
2(C1 + 021191lo0)
(6)
/ Mog(2) Visst l/p)
[o )r TM/L(M
where the underlying generative function of graph signal g E L L is with the essential supreme norm as in (Maskey et al., 2022; Thou et al., 2022). The p. C2 are constants and depend on M It means any test graph can be much larger than the largest possible training graph, and supp indicates the support of a distribution. Then, if and v are isomorphic in topology and with the same representations, we have a probability at least 1 - Σt= (0) |||+]] 1)p with hidden size Ih (9) that the same predictions can be obtained whether u, generated by the same distinct g. The detailed proof can be found in Appendix. A.
where min( supp( ()ee > Mraiin max (upp(())roon]] (ayrll

---

Published as a conference paper at ICLR 2024
Table 1: Empirical results of WNI8RR, NELL-995, YAGO3-10 datasets. Best performance is indicated by the bold face numbers, and the underline means the second best. "_" means unavailable results. "H@1 1" and "H @ 10" are short for Hit@1 and Hit@ 10 (in percentage), respectively.
WNI8RR H@ 11
NELL-995
YAGO3-10
type
models
MRR1
H@ 101
MRR
H@ IT
H@ 101
MRR
H@1f
Hē 101
ConvE
0.427
39.2
49.8
0.511
44.6
61.9
0.520
45.0
66.0
Semantic Models
QuatF
0,480
44.0
55.1
0.533
46.6
64.3
0.379
30.1
53.4
RotatE
0.477
42.8
57.1
0.508
44.8
60.8
0,495
40.2
67.0
MINERVA
0.448
41.3
51.3
0,513
41.3
63.7
DRUM
0.486
42.5
58.6
0.532
46.0
66.2
0.531
45.3
67.6
RNNLogie
0.483
44.6
55.8
0.416
36.3
47.8
0.554
50.9
62.2
Structural Models
CompGCN
0.479
44.3
54.6
0.463
38.3
59.6
0,489
39.5
58.2
DPMPN
0.482
44.4
55.8
0.513
45.2
61.5
0.553
48.4
67.9
NBENet
0.551
49.7
66.6
0.525
45.1
63.9
0,550
47,9
68.3
RED-GNN
0,533
48.5
62.4
0.543
47.6
65.1
0.559
48.3
68.9
one-shot-subgraph
0.567
51.4
66.6
0.547
48.5
65.1
0.606
54.0
72.1
Table 2: Empirical results of two OGB datasets (Hu et al., 2020) with regard to official leaderboards.
OGBL-BIOKG Valid MRR1
OGBL -IRI-W2KKKG2
lype
models
Test MRR1
#Parrms
Test MRR
Valid MRR1
MParamss
TripleRB
0.8348
0.8360
469,630,002
0.5794
0.6045
500.763.337
AutoSF
0.8309
0.8317
93,824.000
0.5458
0,5510
500.227.800
PairRE
0.8164
0.8172
187.750.000
0.5208
0.5423
500.334.800
Semantic Models
ComplEx
0.8095
0.8105
187,648,000
0,4027
0.3759
1,250,569..50 550000
DistMult
0.8043
0.8055
187.648.00
0.3729
0.3506
1,250,569.500 5500
RotatE
0.7989
0.7997
187.597,000
0.4332
0,4353
1,250,435,750
TransE
0.7452
0.7456
187,648,000
0,4256
0.4272
1,250,569,500
Structural Models p
0.8430
0.8435
976,801
0.6755
0.7080
6,8312201
Table 3: Coverage Ratio of different heuristics. Bold face numbers indicate the best results in column.
WN18RR
NELL-995
YAGO3-10
heuristics
0 = 0.1 r =02
r 0.5
2 =011
0.1
r = 0.2
r = 0.5
r 0.1
r 55=22
r 0.5
Random Sampling (RAND)
0.100
0.200
0.500
0.100
0.200
0.500
0.100
0.200
0.500
PageRank (PR)
0.278
0.407
0.633
0.405
0.454
0.603
0.340
0.432
0.694
Random Walk (RW)
0.315
0.447
0.694
0.522
0.552
0.710
0.449
0.510
0.681
Breadth-fire first--eeeetee searching
firt---sasstitingg (BFS)
0.818
0.858
0.898
0.872
0.935
0.982
0.728
0.760
0.848
Personalized PageRank (PPR)
0.876
0.896
0.929
0.965
0.977
0.987
0,943
0.957
0.973
5 EXPERIMENTS
In this section, empirically verify the effectiveness of the proposed framework. The major experiments are conducted with Py PoTchh (Paszke et al., 2017) and one NVIDIA RTX 3090 GPU. The OGB datasets thousand entities (see Tab. 11), including WN18RR (Dettmers et al., 2017), NELL-995 (Xiong et al., 2017), YAGO3-10 (Suchanek al., 2007), OGBL-BIOKG, and OGBL-WIKIKG2 (Hu et al., 2020).
with one NVIDIA A A100 GPU. We use five benchmarks with more than ten
Metrics. We adopt the filtered ranking-based metrics for evaluation, i.e., mean reciprocal ranking (MRR) and Hit@k & (i.e., both Hit@1 and Hit@ 10), following (Bordes et al., 2013; Teru al., 2020; Wang et al., 2017; Zhu et al., 2021). For both metrics, a higher value indicates a better performance.
Main Results. As results shown in Tab. and Tab. our -ubssho-- link prediction method achieves leading performances on all five large-scale benchmarks over all the baselines. Especially dataset, a 16.6% improvement in Test MRR can be achieved. Note the results attribute to deep GNN (high expressiveness) and small subgraphs (essential information) extracted by sampling 10% of entities on average for answering specific queries. Which means, is unnecessary to utilize the whole KG in link prediction; meanwhile, only small proportion of entities and facts are essential for answering specific queries that can be quickly identified by the PPR heuristics. In what follows, conduct in-depth analysis of the properties of the proposed method.
on the largest OGBL-WIKIKG
The Sampling Distribution. We empirically evaluate to what extent the entities relevant to a specific query can be identified by heuristics, e.g., BFS, RW, and PPR. We quantify their power of identifying potential answers via the metric of Coverage Ratio CR = 1/1501) E E(ug,v)e If V.). i.e., the ratio of covered answer entities that remain in the set of sampled entities V,, As shown in Tab. 3 and Fig. 3, PPR gets much higher CR and notably outperforms other heuristics in identifying potential answers.
7

---

Published as a conference paper at ICLR 2024
WN18RR
NELL-995
YAGO3-10
1.0
1.0
1.0
Coverage Ratlo
0.8
Coverage
Coverage
0.4
0.4
0.4
BFS
RAND
RAND
BFS
0.2
PR
PPR
0.2
PR
PPR
0.2
PR
PPR
0.0
0.0
0.0
Ratio sampled entities
Ratio of sampled entities
Ratio of sampled entities
Figure 3: Coverage Ratio (CR) of different heuristics (CR= 1/ gree
(). L( e V3
WNISRR
NELL-95 995
YAG03-10
1.84
1.0
1.505
1.00
0.9
0.567
0.500
9.8
0.564
0.000
0.7
0.7
0.7
-0501
0.400
0.590
0.
9.4
0.358
0.5
0.580
02
0.555
Palle
02-
0.460
0.570
0.2
61
0.475
01026304 0300000 070.0.110
0102233948
0102033040320 240323222200030
sampled eages
of sampled edges
Ratio sampled odges
Figure 4: Heatmaps of validate MRR (the higher, the better) w.E. ry and r on three benchmarks.
Table 4: Comparison of effectiveness with regard to subgraph sampling.
#layers (L)
+
r
WNI8RR H@T I
NELL-995
YAGO3-10
MRR
H@ 10
MRR
H@l
H@10 10
MRR
H@l I
H@10
1.0
1.0
Out of memory
Out memory
Out of memory
0.1
1.0
0.567
51.4
66.6
0.547
48.5
65.1
0.606
54.0
72.1
1.0
1.0
0.543
49.2
64.3
0.519
45.3
62.7
0.538
46,9
66.0
0.1
1.0
0.566
51.2
66.5
0.540
48.0
63.8
0.599
53.1
71.8
1.0
1.0
0.513
46.6
59.8
0.518
45.4
61.5
0,542
47.6
66.1
0.1
1.0
0.523
47.7
60.5
0.538
47.4
63.4
0.589
52.2
70.4
A Ablation Study. (1) Training with varying scales and layers: We train the predictor from scratch with various scales of subgraphs and the number of layers. As can be seen from Tab. 4, involving all the entities with =3,=1.0 degenerates the prediction. as too many irrelevant entities are covered. Besides, a deeper predictor with a larger L consistently brings better results. These observations enlighten us to learn deeper predictor with small subgraphs. (2) Training with different heuristics: We replace the PPR sampling module with four other common heuristics. However, as shown in Tab. 5, their final prediction performances are outperformed by PPR. (3) Test-time extrapolation power across scales: As in Theorem. 1, we evaluate the extrapolation power by generalizing to various scales of subgraphs that are different from the scale of training graphs, e.g., the whole graph ri = = 1.0. As shown in Fig. 4, the predictor also suffers when prediction with more irrelevant entities, especially with larger r.. while the generally good cases a lower ri to focus the relevant entities and a high rg to preserve the local structure (of head u) within the sampled entities.
Training and Inference Efficiency. Next, conduct efficiency study to investigate the im- provement of efficiency brought by the proposed one-shot-subgraph link prediction framework. The running time and GPU memory of an 8-layer GNN are summarized in Tab. As can be seen, notable advantage of decoupling is that it has less computing cost in both terms of less running time and also less memory cost. Particularly, on the YAGO3-10 dataset, the existing GNN-based methods will run out of memory with a deep architecture. However, with the subgraph sampling of lower ratios of rg and rg. the learning and prediction of GNNs become feasible that with less memory cost and achieving state-of-the- oott performance. Hence, we show that our method is effective and also efficient that it supports the learning and prediction of deep GNNs on large-scale knowledge graphs.
Besides, we provide detailed efficiency comparison between our method (with 10% entities) and the original implementation (with 100% entities) on two SOTA methods, NBFNet and RED-GNN. Tab. shows that the training time is significantly reduced when learning with our method. Notably, on the YAGO3-10 10 dataset, 94.3% and 94.5% of training time (for one epoch) can be saved for NBFNet and RED-GNN, respectively. Besides, our method boosts the performance as advantage 2, where the performance improvement can come from a deeper GNN and a smaller observation graph (detailed analysis in Appendix. D.3). Full evaluations and more discussions elaborated in the Appendix. C.
8

---

Published as a conference paper at ICLR 2024
Doraitr
Degres wwwarpped arilks
Dasance quzty ordoy
Degree of semmmteed crt
Dellance quay undyy
Figure 5: Exemplar subgraphs sampled from WNISRR (left) and YAGO3-10 (right). The red and green nodes indicate the query entity and answer entity. The colors of the edges indicate relation types. The bottom distributions of degree and distance show the statistical properties of each subgraph.
Table 5: Comparison prediction performance with different sampling heuristics.
heuristics
WNI8RR H@@
YAGO3-10 H@@
MRR
H@@0
Random Sampling (RAND)
0.03
43.4
3.5
0.057
5.1
6,5
Bank (PR)
0.124
0.315
28.9
35.9
Random Walk (RW)
0.507
45.8
59.8
0.538
46.3
67.2
Breadth- searchin (BFS)
0.543
69.0
Personalized PageRank (PPR)
0.567
51.4
66.6
0.606
54.0
72.1
Table 6: Comparison of prediction performance with two recent GNN methods.
WNISRR
YAGO3-10 11@ 10
methods
MRR
I1@1 1
I1@ 10
Time
MRR
II@1
Time
NBFNet (100% entities)
0.551
49.7
66.6
32.3 min
0.550
47.9
68.3
493.8 min
NBFNet one-shot-subgraph (10% entities)
0.554
50.5
66.3
2.6 min
0.565
28.2 min
RED-GNN (100% entities)
0.533
48.5
62.4
68.7 min
0.559
48.3
68.9
1382.9 min
RED-GNN + one-shot-subgraph (10% entities)
0.567
51.4
66.6
4.5 min
0.606
54.0
72.1
76.3 min
Table 7: Comparison of efficiency with an 8-layer predictor and different ri. r
phase
r
Time
WNISRR
Memory
Time
NEI.I.995
Memory
Time
YAGO3-10
Memory
1.0
1.0
Out memory
Out of memory
Out of memory
0.5
0.5
26.3m
20,3GB
1.hh
20.
Out of memory
Training
0.2
1.0
12.8m
20,2GB
1.2h
18.5GB
Out of memory
6.7m
6.4GB
8.9GB
2.1h
23.1GB
0.1
1.0
7 7,2m
9.8GB
0.8h
12.1GB
1.3h
13.9GB
0.1
6.6m
5.1GB
0.3h
5,3GB
0.9h
10.2GB
1.0
7.3m
6.7GB
17.5m
12.8GB
15.0GB
0.5
0.5
6.0m
4.3GB
8.3m
4.5GB
1.1h
10.1GB
Inference
1.0
3.2m
5.8GB
4.2m
12.1GB
0.7h
14.7GB
0.2
0.2
2.8m
1.9GB
3.6m
2.5GB
0.6h
3.7GB
0.1
1.0
2.7m
2.7GB
3.1m
9.4GB
0.4h
9.7GB
0.1
0.1
2,3m
1.7GB
2.9m
1.9BB
0.4h
3.1GB
Case Study. We visualize the sampled subgraph in Fig. with the histograms of degree and distance distributions. As can be seen, the local structure of query entity u is well preserved, while the true answers are also covered in the subgraphs. More cases and analyses can be found in Appendix.
CONCLUSION
In this paper, we propose the one-shot- -ubb-ap- link prediction to alleviate the scalability problem of structural methods and achieve efficient well as adaptive learning on large-scale KGs. We discover that the -onmmmamettiic and computation-efficieen heuristics PPR can effectively identify the potential answers and support to the prediction. We further introduce the automated searching for adaptive configurations in both data space and model space. Extensive experiments on five large-scale benchmarks verify the effectiveness and efficiency of our method. Importantly, we show it unnecessary to utilize the whole KG for answering specific queries; meanwhile, only small proportion of information is essential and can identified by the PPR heuristics without learning.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
2KZ and BH were supported by the NSFC General Program No. 62376235, Guangdong Basic and Applied Basic Research Foundation Nos. 2022A151501 1652 and 2024A1515012399 HKBU Faculty Niche Research Areas No. RC-FNRA-IG/22- WANRA-IG/22-23/SCI000 and HKBU CSD Departmental Incentive Scheme. JCY was supported by 111 plan (No. BP07 19010) and National Natural Science Foundation of China (No. 62306178). QMY was in part supported by NSFC (No. 92270106) and National Key Research and Development Program of China under Grant 2033YFB2903904. The authors thank Haobo Xu for his assistance in experiments.
ETHICS STATEMENT
We would claim that this work does not raise any ethical concerns. Besides, this work does not involve any human subjects, practices data releases, potentially harmful insights, methodologies and applications, potential conflicts of interest and sponsorship, bnscriiination/iis/aaainn concerns, privacy and security issues, legal compliance, and research integrity issues.
REPRODUCIBILITY STATEMENT
The experimental setups for training and evaluation are described in detail in Sec. 5 and Appendix. C, and the experiments are conducted using public datasets. The code publicly available at: https://githee www/tml ht/mmmmlrrrrr//////////// cotplpp/oessheeeee sastrrpuub.....p
REFERENCES
P. Battaglia, J. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint
2018.
Bergstra, D. Yamins, D. Cox, et al. Hyperopt: A python library for optimizing the hyperparameters of machine learning algorithms. In Proceedings of the 12th Python in science conference, 2013.
A. Bordes, N. Usunier, A. Garcia-Duran, J. Weston, and O. Yakhnenko. Translating embeddings for modeling multi-relational data. In NeurIPS, 2013.
L. Breiman. Random forests. ML. (5(1):55533) 2001.
Y. Cao, X. Wang. X. He, Z. Hu, and Chua. Unifying knowledge graph learning and recommenda- tion: Towards a better understanding of user preferences. In WheWebConf, 2019.
J. Chen, T. Ma, and C. Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
X. Chen, S. Jia, and Y. Xiang. A review: Knowledge reasoning over knowledge graph. Expert Systems with Applications, 11:48, 2020.
Y. Chen, H. Yang, Y. Zhang, K. Ma, T. Liu, B. Han, and J. Cheng. Understanding and improving graph injection attack by promoting unnoticeability. In ICLR, 2022.
H. Cheng. L. Koc, J. Harmsen, T. Shaked, T. Chandra, H. Aradhye, G. Anderson, G. Corrado, W. Chai, M. Ispir, et al. Wide & deep learning for recommender systems. In Proceedings of the 1st workshop deep learning for recommender systems, 2016.
P. Covington, J. Adams, and E. Sargin. Deep neural networks for youtube recommendations, In Proceedings of the 10th ACM conference on recommender systems, 2016.
R. Das, S. Dhuliawala, M. Zaheer, L.. Vilnis, Durugkar, A. Krishnamurthy, A. Smola, and A. Mc- Callum. Go for walk and arrive the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR, 2017.
T. Dettmers, Minervini, P. Stenetorp, and S. Riedel. Convolutional 2D knowledge graph embed- dings. In AAAI, 2017.
10

---

Published as a conference paper at ICLR 2024
P. Diaconis and S. Janson. Graph limits and exchangeable random graphs. arXiv preprint arXiv:0712.27499 2007.
M. Galkin, E. Denis, J. Wu, and W. Hamilton. Nodepiece: Compositional and parameter-efficien representations of large knowledge graphs. In ICLR, 2022.
M. Galkin, X. Yuan, H. Mostafa, J. Tang, and Z. Zhu. Towards foundation models for knowledge graph reasoning. arXiv preprint arXiv:2310.04562, 2023.
M. Gardner and S. Dorling. Artificial neural networks (the multilayer perceptron) - a review of applications in the atmospheric sciences. Atmospheric environment, 32(14-15):2627-222 1998.
L. Grinsztajn. E. Oyallon, and G. Varoquaux. Why do tree-based models still outperform deep learning on tabular data? arXiv preprint arXiv:2207 088115 2022.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning large graphs. In NeurIPS, 2017.
W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
X. Huang, J. Zhang, D. Li, and P. Li. Knowledge graph embedding based question answering. In WSDM, 2019.
Hutter, H. Hoos, and K. Leyton- Brown. Sequential model-based optimization for general algorithm configuration. In ICLIO, 2011.
G. Jeh and J. Widom. Scaling personalized web search. WWW, 2003.
S. Ji, S. Pan, E. Cambria, Marttinen, and P. S Yu. A survey on knowledge graphs: Representation, acquisition and applications. arxiv preprint arXiv:2002.00388. 2020.
Li, Zhang, J. Cao, and M. Tan. Learning defense transformations for counterattacking adversarial examples. Neural Networks, 164:177-185, 2023.
S. Mai, S. Zheng, Y. Yang, and H. Hu. Communicative message passing for inductive relation reasoning. In AAAI, 2021.
S. Maskey, R. Levie, Y. Lee, and G. Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In NeurIPS, 2022.
S. Miao, M. Liu, and P. Li. Interpretable and generalizable graph learning via stochastic attention mechanism. ICML,, 2022.
H. Mohamed, D. Pilutti, S. James, A. Del Bue, M. Pelillo, and S. Vascon. Locality-aware subgraphs for inductive link prediction knowledge graphs. Pattern Recognition Letters, 2023.
K. Oono and Suzuki. Graph neural networks exponentially lose expressive power for node classificatio.. In ICLR, 2019.
L. Page, S. Brin, Motwani, and Winograd. The pagerank citation ranking: Bringing order the web. Technical report, Stanford infolab, 1999.
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in PyTorch. In ICLR, 2017.
M. Qu, J. Chen, L. Xhonneux. Y. Bengio, and J. Tang. Runlogic: Learning logic rules for reasoning on knowledge graphs. ICLR, 2021.
A. Sadeghian. M. Armandpour, P. Ding, and D. Z. Wang. Drum: End-to-end differentiable rule mining on knowledge graphs. In NeurIPS, 2019.
M. Schlichtkrull, T. N Kipf, P. Bloem, R. Van Den Berg, Titov, and M. Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
11

---

Published as a conference paper at ICLR 2024
Z. Shi, X. Liang, and J. Wang. Lme: Fast training of gnns via subgraph sampling with provable convergence. arXiv preprint arXiv:2302.00924, 2023.
F. Suchanek, G. Kasneci, and G. Weikum. Yago: A core of semantic knowledge. In The pp. 697-706, 2007.
Z. Sun, Z. Deng, J. Nie, and Tang, Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
7. Tang, S. Shi, B. Li, and X. Chu. Gossipft: A decentralized federated learning framework with sparsified and adaptive communication. IEEE Transactions on Parallel and Distributed Systems, 2022a.
Z. Tang, Y. Zhang. S. Shi, X. He, B. Han, and X. Chu. Virtual homogeneity learning: Defending against data heterogeneity in federated learning. In ICMI,, 2022b.
K. K Teru, E. Denis, and W. L Hamilton. Inductive relation prediction by subgraph reasoning. In ICML, 2020.
Vashishth, S. Sanyal, V. Nitin, and P. Talukdar. Composition- -ased multi-relational graph convolu- tional networks. In ICLR, 2019.
Q. Wang. Z. Mao, B. Wang, and L.. Guo. Knowledge graph embedding: A survey of approaches and applications. TKDE, 2017.
X. Wang, X. He. Y. Cao, M. Liu, and T. Chua. Kgat: Knowledge graph attention network for recommendation. In SIGKDD, 2019.
C. Williams and C. Rasmussen. Gaussian processes for regression. In NIPS, 1995.
W. Xiong, T. Hoang, and W. Wang. Deeppath: A reinforcement learning method for knowledge graph reasoning. In EMNLP, 2017.
X. Xu, W. Feng, Y. Jiang, X. Xie, Z. Sun, and Z. Deng. Dynamically pruned message passing networks for large-scale knowledge graph reasoning. In ICLR, 2019.
M. Yasunaga, H. Ren, A. Bosselut, P. Liang, and J. Leskovec. Qa-gnn: Reasoning with language models and knowledge graphs for question answering. In NAACL, 2021.
Y. Yu, K. Huang, C. Zhang, L. M Glass, Sun, and C. Xiao. Sumgnn: multi-typed drug interaction prediction via efficient knowledge graph summarization. Bioinformatics, 37(18):2988-2995 2021.
S. Zhang, Y. Tay, L. Yao, and Q. Liu. Quaternion knowledge graph embeddings. In NeurIPS, 2019.
S. Zhang, F. Liu, J. Yang, Y. Yang, C. Li, B. Han, and M. Tan. Detecting adversarial data by probing multiple perturbations using expected perturbation score. In ICML, 2023a.
Y. Zhang and Q. Yao. Knowledge graph reasoning with relational directed graph. In TheWebConf, 2022.
Y. Zhang, M. Gong, T. Liu, G. Niu, X. Tian, B. Han, B. Schölkopf, and K. Zhang. Adversarial robustness through the lens of causality. In ICLR, 2022a.
Y. Zhang, Z. Zhou, Q. Yao, and Y. Li. Efficient hyper- papam-parreeter search for knowledge graph embedding. In ACL, 2022b.
Y. Zhang, Q Yao, L. Yue, X. Wu, Z. Zhang, Z. Lin, and Y. Zheng. Emerging drug interaction prediction enabled by a flow-based graph neural network with biomedical network. Nature Computational Science, 3(12):1023-1033, 2023b.
Y. Zhang, Z. Zhou, Q. Yao, X. Chu, and B. Han. Adaprop: Learning adaptive propagation for knowledge graph reasoning. SIGKDD, 2023c.
Y. Zhou, G. Kutyniok, and B. Ribeiro. Ood link prediction generalization capabilities of message- passing gnns in larger test graphs. In NeurIPS, 2022.
12

---

Published as a conference paper at ICLR 2024
Z. Zhou, J. Yao, J. Liu, X. Guo, Q. Yao, L. He, L. Wang. B. Zheng, and B. Han. Combating bilateral edge noise for robust link prediction. NeurIPS, 2023a.
Z. Zhou, C. Zhou, X. Li, J. Yao, Q Yao, and B. Han. On strengthening and defending graph reconstruction attack with markov chain approximation. In ICML, 2023b.
Zhu, Z. Zhang, L.. Xhonneux, and Tang. Neural bellman-ford networks: general graph neural network framework for link prediction. In NeurIPS, 2021.
Z. Zhu, X. Yuan, M. Galkin, S. Xhonneux, M. Zhang, M. Gazeau, and J. Tang, A A scalable path-based reasoning approach for knowledge graphs. NeurIPS, 2023.
13

---

Published as a conference paper at ICLR 2024
Appendix
Table of Contents
A Theoretical Analysis
15
A.1 Notations
15
A.2 Complexity Analysis
15
A.3 Proof for Theorem
16
B Implementation Details
18
Full Evaluations
Setup
C.2 Comparison With Other Efficient Methods
19
C,3 The Edge Split Scheme
20
C.4 Robustness Against Data Perturbations
21
D Further Discussion
21
Design Principles
21
Contributions
................................
22
D.3 Explanation for the Improvement in Performance
oif.............................
22
D.4 Extension
23
E Case Study
24
14

---

Published as a conference paper at ICLR 2024
A THEORETICAL ANALYSIS
A.1 NOTATIONS
We summarize the frequently used notations in Tab. 8.
Table 8: The most frequently used notations in this paper.
notations
meanings
V. E.
the set of entities, relations, facts (edges) of the original KG
9 EV,
the original KG
V., Rs
the set of entities, relations, facts (edges) of the sampled KG the sampled KG generated by the sampler 96
g3 = (Vo, Es)
r))
a fact triplet in & with subject entity x, relation r and object entity o query triple with query entity u, query relation and answer entity
(u, q, v)
L
the total number of propagation steps
the f-th propagation step and E [O...
K
the maximum steps of updating the PPR scores the k-th propagation step and & E (O...K)
k-
(e)
the representation of entity at step l the sampler of the one-shot-subgraph link prediction framework the predictor of the one-shot- subgraph link prediction framework the sampling ratios of entities and edges
So
r2,r2 r2
A.2 COMPLEXITY ANALYSIS
Next, we compare three different manners from perspectives of computation and parameter.
In nutshell, semantic models are computation--effcciet but parameter-expensin while structural models are parameter-efficient but computation-expensivee Here, we aim to make the best of the both worlds by designing framework that is parameter- errfiietr-effcceent and computation-efficee one-shot-subgraph link prediction models, as will be elaborated in Sec. 3, is with the new prediction manner that G (M,,
The proposed
G. - Y. The key difference here that, instead of the original G, the predictor fo is acting on the query-dependens subgraph G3 extracted by the sampler 9ø.
By contrast, show that the proposed subgraph models make the best of both worlds: (1) subgraph models are compuration--fficien,, as the extracted subgraph is much smaller than the original graph, < [E] (2) inherits from Sadeghian al. (2019); Zhu et al. (2021); Zhang &
i.e., [Val < V and |E,|<< Yao (2022), subgraph models are also parfmeter-efffcientt: only requires the relations' embeddings but not the expensive entities' embeddings. By contrast, the semantic models need to learn entities's and only applicable in transductive settings.
embeddings, which are
detailed comparison of parameter and computation complexity is summarized in Tab. 9.
Table 9: The comparison of related works with parameter complexity and computation complexity.
Category
Parameter complexity
Computation complexity
semantic models
O(V Dy) + O(R))-Dre Dre)
( Dv) ( D LL) O( ((8)-K)+O((ES)) 0(EE) DR. LL)
structural models
O DT))
subgraph models
O(R D
15

---

Published as a conference paper at ICLR 2024
Computation Complexity
q.9.. fo
8
(u.q.
Y
G
(u, q. ?)
Gs
Y
structural
subgraph
fo
fe
g
fo
(8) semanntic
Parameter Complexity
(a) semantic model
structural model
(c) sue-sho--uuggrah model (d) complexity comparison
Figure 6: Illustrations of prediction manners. Semantic and structure models implicitly or explicitly take the whole graph 9 for prediction. Our one-shot- -use-ruuh--ubuhuphh model only requires one subgraph Gs for the prediction of one query that decreases computation complexity via decoupling So and g.
fe
(t.Ps)
(u,, 9.
gs
(H.4.?
9
g5
(1-11)
(M,)22
y
Y
f2(2)
(a) layer-wis- sampling
(b) subgraph wise sampling
Figure 7: Illustrations of sampling methods. Detailed analysis is corresponding to Sec. 3.
A.3 PROOF FOR THEOREM
Proof. Here, let Gi Pg and Glest Pg be the training and testing graphs that sampled distribution P... Let glest be large enough satisfy v /1og(2//v= // 2 4v where dmin is
the constant of graphon degree (Diaconis & Janson, 2007).
In this part, we follow Maskey al. (2022); Zhou al. (2022) with the definitions of graph message-passee passing neural network & and continuous message passing neural network L. Note that & is equivalent the message passing function of the predictor fo that generates the entity representation h in each layer é = 2. ... L. Besides, V is the continuous counterpart of 4. It uses the continuous aggregation instead of the discrete one w.r.t. the discrete graph topology in Φb
With the two above functions, |1 || can be trained and determined by the original graph grain and hyperparameters r.. r and L. Following Maskey al. (2022); Zhou al. (2022), let E (0, -/E 2|1()++1) we with probability at least 1- (01h +1)), the difference between | co and V oo is bounded by
max 1=,,2 11
1|:;
Villoc
(8) Li (M (2v2. (L
(L (M (M | //00 ||
(1 log 22 l/2)
L
x II (1L (A 2(L (2) 2 (2)t #=#+1
Then, based on the proof for Lemma B.9 in (Maskey et al., 2022), we can derive l|glloc S B(() B
[|g]loo, where Bid), Ba!e) independent of g. Specifically,
(
Σ
Lg (aan ( loo (A)) loc) x II
(I (2rtting (artnin) + I (A)rmin)) ===4+1
1,0
L (K6) (M train (1 1 (M uaan
1=1
16

---

Published as a conference paper at ICLR 2024
Then, define constants C1 C2 follows.
O=
Σ
L
(0)
(M (M (Munia)B (
t=1
L
II
(M 2(1
2 (M (1 ((llinnnee)
x
#=t+1
C2 = Σ (1 (Muriin 22/21 (2) (Muaily y3!
8=1
II ((Lg) (0) (L&)
+ 2(L (M +
(M (L ) (M
p=1+1
This, can derive the difference
log (2gg) Viveo
|| - Villoo S (C++ + C2lg1loo)
=
max Am 1,2, |Vel
where C1, C2 depends on {T. (9) (Mrtain)) ( and (T. (Mitin) that
min(supp (())))))))))))))))))))))))))(( M max(supp()))"dm))
Then, consider any two test entities u, u yrsst for which we can make a prediction decision fact (u, 9, v), we have
_ Bollo $1 Vul1 + || - +blloc
v log (2g(21151//1 V
=1|0, - vallo + V| o S S(1 + C2llela)))
The first inequality holds by the triangle inequality. In contrast, the second inequality holds since v,= v.. Note that u and e are isomorphic in the topology of the test graph (Zhou al., 2022) and thus with the same representations.
Next, with probability at least 1- 21-12(11()) |11)p, for arbitrary entity v'
Viest have
Vlog(21V**/
1 V'llo (0: + C21gglb>
V
Then, when the size of the test graph satisfied and Puc = fn (G ) READOUT(H!) (1) .h! (.) we have
Pav Puv lloo S L(Mtrain]| - D.llo0 S Pl - Tl
Specifically, if Pas 2 r, we have
Pur' Pae
Puv Puo 2 Pav
Puu 7| Puv Puv +
if Puv E T, we have
Puv' S Pae +
Pav Poo'l
S Pav + Puv - T| = Puv + T - Puv = T.
Thus, whether u, v are generated by the same or distinct g, where the underlying generative function of graph signal E _ is with the essential supreme norm in Maskey al. (2022); Zhou et al. (2022), have probability at least -th 2( (1) +11) 1)p that the same predictions obtained.
n
17

---

Published as a conference paper at ICLR 2024
B IMPLEMENTATION DETAILS
(ESS(.) and (G for GNN-based methods. The two functions of the GNN-hased methods are summarized in Tab. 10. The main differences between different methods are the combinators for the edges, the operators on the different representations, and
entity and relation representations the attention weights. Recent works (Vashishth et al., 2019; Zhu et al., 2021) have shown that the different combinators and operators only have slight influence on the performance. Compared with GralL and RED-GNN, even though the message functions and aggregation functions are similar, their empirical performances are quite different, with different propagation patterns.
Table 10: Summary of the GNN functions for message propagation. The values in O represent different operation choices that are tuned as hyper-parameters for different datasets.
method
( (ea)
MESS()
N AGG(-)
W A ((-1) where W, depends on the relation
R R-GCN (Schlichtkrull et al. 2018)
w W " +
W
Arr ( ".."), where Wo(d) depends on the direction of ACr) (V""""")))
CompGCN (Vashishth 2019)
Easehiow m (esires)
! (o (W/""!
GralL (Teru al., 2020)
W ([-1) +2.,CA Rar m (ea)
(eainsaall, is the attention weight. where (e)
NBFNet (Zhu et al., 2021)
W ( (n my) is query weight vector (t) nonlin (hi + 4,9), where
(+:
(111, un (r,r)) (,)), where
(Sum, Mean, Max, PNA) (ca)t
RED-GNN (Zhang & Yao, 2022)
EnceNtes (astee))
(
(ean is the attention weight
Design space of the predictor. From the model's perspective, we build the configuration space of the predictor and further utilize the advantages of existing structural models introduced in Sec. 2. Three query-dependent message functions MESS (-) are considered here, including DRUM (Sadeghian et al., 2019) (denoted as MORUM), NBFNet (Zhu et al., 2021) (MNBFNer), and RED-GNN (Zhang & Yao, 2022) (MREDONN). The effective message is propagated from Ug to the entities in subgraph 9g.
Generally, the message propagation can be formulated
Predictir fe: h(++)) = DROPOUT ACT (AGG (h, 1 (a.r)))))))
Note the effective message is propagated from to the entities in subgraph G,. The ranges for design dimensions of the configuration space are shown below, where the upper is intra-layer design while the lower is inter-layer design.
DROPOUT(-)
ACT(-)
AGG
MESS(.)
Dimension
(0, 0.5)
Identity, Relu, Tanh
Max, Mean, Sum
MURU MyHENer, MREDENN
16, 32, 64, 128
No. layers (L) Repre. initialization Layer-wise shorteut Repre. concatenation (4, 6, 8, 10) Binary, Relational
READOUT(-)
True, False
True, False
Lincar, Dot product
Head and tail prediction. Note that predicting a missing head in KG can also be formulated as tail prediction by adding inverse relations. For example, predicting missing head in KG (?, q, v) can
also be formulated to tail prediction by adding inverse relations as (v, quverse: ?). This formulation involves augmenting the original KG with inverse relations, following the approach adopted in other
KG methods (Zhu et al., 2021: Zhang Yao, 2022; Zhang et al., 2023c: Zhu et al., 2023; Zhang al., 2023b; Galkin et al., 2023).
18

---

Published as a conference paper at ICLR 2024
C FULL EVALUATIONS
C.I SETUP
Datasets. We use five benchmarks with more than ten-thousand entities, including WNI8RR (Dettmers et al., 2017), NELL (Xiong et al., 2017). YAGO3-10 (Suchanek et al., 2007), OGBL-BIOKG and OGBL-WIKIKGE (Hu et al., 2020). The statisties are summarized in Tab. 11.
Table 11:
Statisties of the five KG datasets with more than ten-thousand entities. Fact triplets in & used to build the graph, and Euain, eval, guest are edge sets of training, validation, and test set.
datasct
[V]
R
|E|
g
[
[
WN1&RR
40.9k
65,
59.0k
3.0k
3.1k
NELL-995
74.5k
200
112.2k
108 9k
0.5k
2.8k
YA
123 1k
1089.0K Ok
1079.0k
5.0k
5.0k
OGBL-BIOKG
93.7k
51
5088. 4k
4762.7k
162.9k
162.9h
OGBL-WIKIKG2
2500.6k
535
17137.1k
16109.26
429.5k
598.5k
Baselines. We compare our method with general link prediction methods, including (i) semantics
models: ConvE (Dettmers et al., 2017), QuatE (Zhang et al., 2019), and RotatE (Sun et al., 2019); and (ii) structural models: MINERVA (Das et al., 2017), DRUM (Sadeghian et al., 2019), RNNLogic (Qu et al., 2021), CompGCN (Vashishth et al., 2019), DPMPN (Xu et al., 2019), NBFNet (Zhu et al., 2021), and RED-GNN (Zhang & Yao, 2022). The results of these baseline are taken from their papers or reproduced by their official codes.
C.2 COMPARISON WITH OTHER EFFICIENT METHOSS
To reduce entity vocabulary to be much smaller than full entities, NodePiece (Galkin et al., 2022) represents an anchor-based approach that facilitates the acquisition a fixed-size entity vocabulary. Note that NodePiece was originally designed for semantic models, which diverges from the primary focus of our investigation centered around structural models.
As shown below, NodePicce, and original RED-GNN in the MRR metric. Additionally, it's worth noting that NodePiece lead to substantial performance degradation when tasked with reducing unique embeddings for sizable number of entities. The table below illustrates this phenomenon. In contrast, the RED-GNN, when augmented with our one-shot-subgraph method, showcases an ability to enhance performance even while learning and predicting with only 10% of entities. Furthermore, the parameter count for our structural models remains significantly lower than that of semantic models, even with the incorporation of NodePiece improvements.
one-shot-subgraph link prediction method outperforms semantic models,
Table 12: Comparison with NodePicce.
WNISRR
YAGO3-10
MRR
1@@ 10
#Params
MRR
11@10 #Params
RotatE (100% entities)
0.476
57.1
41M
0.495
67.0
123M
RotatE NodePicce (10% entities)
0.403
51.5
4.4M
0.247
48.8
4.1M
RED-GINN (100% entities)
0.533
62.4
0.02M
0.559
68.9
0.06M
RED-GNN -one-shot-ubggrahh (10% entities)
0.567
66.6
0.03M
0.606
72.1
0.09M
Besides, the other efficient link prediction method, DPMPN (Xu al., 2019), contains two GNNs, one is a full- -gagh GNN that is similar to CompGCN, and the other one is pruned. DPMPN is mixture of GNN methods, where the pruned GNN already knows the global information and adopts a layer-wise sampling manner. DPMPN requires several propagation steps to prune the message passing and sample the subgraph, while our PPR sampler can efficiently extract the subgraph without learning. In comparison, method is simpler but much more effective that it observably outperforms DPMPN. Hence, considering the differences, one-shot-subgrapp link prediction still a novel subgraph campling-based method for link prediction and achieves state-of-the--e prediction performance.
As for other sampling- based methods, the extracted subgraph by Yasunaga al. (2021) is equivalent to the Breadth-firs. firs-scarching (BFS) that is compared in our work. As it comprises all entities on the k-hop neighbors in its subgraph, the number of sampled entities could be quite large. For example,
19

---

Published as a conference paper at ICLR 2024
on the WN18RR dataset, the full 5-hop neighbors of the query entity take up 9.4% of entities and 13.5% of edges, while the full 8-hop neighbors can even take up 69.8% of entities and 89.7% of edges. As for the YAGO3-10 dataset, the full 5-hop neighbors take up 98. 98.1% of entities and 95.6% of edges, almost equal to the entire KG. could still be expensive for prediction and thus not suitable for prediction large KGs like YAGO3-10.
The sampling method of Mohamed et al. (2023) aims to extract an enclosing subgraph to answer one given query (u, q, ?), which is consistent with the previous work GralL (Teru al., 2020). Note the extracted subgraphs are different for different given triples. That is, for answering one query (u, ?), this method requires sampling subgraphs and predicting the score of N potential links on each individual subgraph, where N is the number of all entities. Hence, this method is extremely expensive and also not suitable for large KGs. By contrast, our one-shot-subgraph link prediction method only requires extracting one subgraph to answer one query rather than N subgraphs. Meanwhile, the extracted subgraph much smaller than the full k-hop neighbor. Thus, our method more efficient and more suitable for learning and prediction on large KGs.
C.3 THE EDGE SPLIT SCHEME
The edge split can be seen as a masking operation on KG, i.e., removing the query edges from the observation edges (the inputs of prediction model). It is necessary for KG learning; otherwise, the query edges for training can be found in the observation graph, which not practical and not reasonable. We further clarify the edge split scheme in the following three folds.
general perspective KG incompleteness. Note that the KG datasets are generally and naturally incomplete, and the link prediction tasks aim to predict the missing links among entities. An ideal link prediction model should be robust to the intrinsic incompleteness
KG, and the local evidence to be utilized for the prediction of specific query is also generally incomplete. In this view, the edge split can seen as a data augmentation method.
Training details about edge split. Edge split indeed influences the local connectivity of a KG, where a lower split ratio of fact:train can lead to a sparser observation graph for training. However, we afresh split the query and observation edges in each epoch, and thus, all the edges in the train be recursively used as the query edges for training. Besides, all these fact/train edges can be used in the phase as factual observations. Hence, all the edges in the training set recursively used in training and explicitly used in testing.
The influence of edge split training. We conduct further experiment with different split ratios and constrain the experiments using the same amount of training time. As the data shown below, the split ratios greatly impact the training time for one epoch, and a higher fact:train ratio leads to short training time. Besides, various split ratios only slightly influence the converged result; however, they greatly influence the speed of convergence. Specifically, higher split ratio brings faster convergence speed, especially on the YAGO3-10.
Table 13: Comparison of different split ratios.
WN18RR
YAGO3-10
MRR
H@1
H@ 10
Time
MRR
H@1 l
H& 10
Time
Fact:Train 0.70
0.566
51.1
66.7
22.9min
0.552
46.9
69.9
55.6h
Fact:Train = 0.80
0.561
50.8
66.0
16.2min
0.563
48.4
70.7
42.0h
Train 0.562
66.1
8.7min
0.586
51.4
23.2h
Fact:Train = 0.95
0.567
51.4
66.6
4.5min
0.587
51.7
71.1
12.1h
Fact: Train = 0.99
0.563
51.2
66.3
0.9min
0.598
52.9
71.9
2.5h
Table 14: Comparison of effectiveness with regard to subgraph sampling.
WN18RR H@
NELLL-995 H@ 1
YAGO3-10
MRR
H@
MRR
H@ 10
MRR
H@]
H@ 10
0,549
50.2
63.5
0,507
43.8
0.598
53.3
71.2
0.5
0.5
0.555
50.6
64.4
0.537
47.3
64.2
0.599
53.4
71.4
0.563
51.0
66.0
0.541
47.9
63.9
0.603
53.8
71.8
0.1
0.1
0.567
51.4
66.4
0.539
48.0
63.0
0.599
53.6
70.8
20

---

Published as a conference paper at ICLR 2024
Cover ratio
Cover ratio
optimal
predictor
1.0
1.0
gap
predictor
sampler
random
TV
Tv
1.0
1.0
a) structural models
(b) decoupled models
Figure 8: Illustrations of structural models (a) and decoupled subgraph models (b).
C.4 ROBUSTNESS AGAINST DATA PERTURBATIONS
Randomly adding noise. We generate a noisy dataset by randomly adding noisy edges that observed from the dataset. Specifically, the entity set and relation set are kept the same. The noise ratio is computed
2/ The Eval and geett are clean to guarantee the accurate evaluation.
As the results shown in Tab. 15, such noise does not significantly influence the prediction performance. Even in the high-noise scenario (e 50%), the MRR result nearly identical to that on the clean dataset. This result shows the preliminary robustness of adding noise, and a further investigation should be conducted with more complex noise patterns, e.g., by adopting adversarial techniques.
Table 15: Model performance (MRR) with randomly added noise.
Dataset
0% (clean) 10%
20%
30%
40%
50%
WN1SRR
0.567
0.567
0.566
0.566
0.564
0.564
NELL-995
0.547
0.547
0,547
0.547
0,547
YAGO3-I0
0.606
0.605
0.603
0.601
0.602
0.601
Randomly deleting facts. We create more incomplete KG by randomly deleting the facts in the training set. The delete ratio is computed as r = |/ The Eval and Erest are kept the same as the original dataset. As shown in Tab. 16, this kind of input perturbation greatly degenerates the performance, as the link prediction could rely heavily Here, a sparser graph with more deleted edges can not sufficiently support the prediction, and the message propagation from the query entity is also hindered. Hence, combating graph incompleteness, data heterogeneity (Tang et al., 2022b;a), noisy annotations (Zhou et al., 2023a), or adversarial attacks (Zhang et al., 2022a; Chen et al., 2022: Zhou et al., 2023b; Zhang al., 2023a; Li et al., 2023), would be a valuable direction.
the correct edges in the original dataset.
Table 16: Model performance (MRR) with randomly added noise.
Dataset
0% (full) 10%
20%
30%
40%
50%
WNISRR
0.567
0.507
0.451
0.394
0.338
0.278
NELII-995
0.547
0.515
0.483
0.446
0.412
0.365
YAGO3-10
0.606
0.553
0.489
0.434
0.385
0.329
D FURTHER DISCUSSION
D. DESIGN PRINCIPLES
Note that it is non-trivial achieve the one-shot-subgraph link prediction, where three-fold questions are required to be answered: (i) From the data's perspective, what kind sampler is suitable here? (ii) from the model's 'ss perspective, how to build up the predictor's architecture to be expressive subgraphs? (iii) from the optimization's s perspective, how to optimize the sampler and predictor jointly and efficiently?
21

---

Published as a conference paper at ICLR 2024
The major technical challenge lies in the design and implementation of an efficient and query- dependent sampler. Given a query (u, q. ?), the sampler should not only preserve the local neighbors of u that contain the potential answers and supporting facts, but also be able to distinguish different q as the essential information could be different. Accordingly, the two design principles are as follows.
Since the target entity e is unknown, freely sampling from all the entities in original & will inevitably discard the structural connection between u and promising v. This manner of existing node-wise or layer-wise sampling methods can deteriorate the message flow started from u, and thus degenerate the whole prediction process. Here, the local structure of u expected to be preserved in Gz. and each sampled entity should be reachable from u.
Principle-1: Local-struccturepprseeee
The objective of learning relation- awarr sampling here is to sample the promising targets v according to the query relation q. Note that, in common homogeneous graphs, the relation may be unnecessary, as all relations between nodes share the same semantics. However, the relation here does matter, as it presents the distinct characteristics of KG. Thus, in our design, the sampler is expected to be query relatoo-raoo in order to adapt to KGs efficiently.
Principle-2:
D.2 CONTRIBUTIONS
Here, we further explain the novelty and contributions in the following three folds.
valuable research problem. Our investigation delves into the limitations of structural models, which confront pronounced scalability challenge. These models rely on prediction over the entire Knowledge Graph, encompassing all entities and edges, with the additional burden of scoring all entities as potential answers. This approach proves to be highly inefficient, impeding their optimization when applied to large-scale KGs. As consequence, we present an open question, pondering how to conduct prediction on knowledge graphs efficiently and effectively, seeking avenues to overcome this hindrance.
A conceptual framework with several practical instantiations. In response to the prevalent scalability challenges faced by existing KG methods, we present a conceptual solution, i.e., the one-shot-subgraph link prediction manner. This novel approach promises enhanced flexibility and efficacy in design. Specifically, instead of conducting direct prediction on the complete original KG, we advocate two-step prediction process involving subgraph sampling and subgraph- based prediction. In this regard, our proposed prediction manner comprises a sampler and a predictor. Leveraging the efficiency gains derived from subgraph-based prediction, we introduce an optimization technique for subgraph-bat based searching, incorporating several well-crafted technical designs. These innovations aim to strike balance between prediction efficiency and the complexity associated with identifying optimal configurations within both data and model spaces.
Several important discoveries from experiments. Through comprehensive experimentation on three prevalent KGs, we demonstrate that our framework achieves state-of to-thh--rttt performance. Particularly noteworthy are the substantial advancements we achieve in both efficiency and effectiveness, trend that is particularly evident in the case of the large-scale dataset YAGO3-10. Our quest for optimal configurations leads us to the intriguing revelation that utilizing the entire KG for prediction is unnecessary. Instead, simple heuristics can efficiently identify small proportion of entities and facts essential for answering specific queries without the need for additional learning. These compelling findings hold significant meaning and are poised to pique the interest of the KG community.
D.3 EXPLANATION FOR THE IMPROVEMENT IN PERFORMANCE
Here, we provide a two-fold explanation for better performance follows.
Extracting subgraphs can remove irrelevant information for link prediction. Conventional structural models explicitly take all the entities and edges into prediction, ignoring the correlation between the entities and the query relation. As delineated in Sec. 5 of this paper, our one-shot-subgraph link prediction approach effectively discerns and excludes irrelevant entities while retaining the proper answers. This strategic refinement, in turn, contributes to simplifying the learning problem, thereby amplifying prediction performance. Our findings demonstrate that mere fraction (i.e. 10%) of entities suffices for answering specific queries, i.e., a subset efficiently identified by the heuristic Personalized PageRank mechanism without the need for learnable sampling.
Data perspective:
22

---

Published as a conference paper at ICLR 2024
Another supporting material is that only relying subgraph for prediction also boost the test-time performance (Miao et al., 2022). The proposed GAST method (Miao et al., 2022). aims to extract subgraph G, as the interpretation of a GNN. It inherits the same spirit of information bottleneck in building its optimization objective, iee, min - GG Y) + 3 T(G,; G).. The integrated subgraph sampler can explicitly remove the spurious correlation noisy information in the entire graph G, which is similar to our one-shot-subgraph link prediction framework.
Model perspective: The higher learning efficiency on subgraphs can further boost hyper-parameter optimization (Zhang et al., 2022b). Generally, the task of hyperparameter optimization on extensive graph datasets poses substantial challenges due the inherent inefficiencies in model training. However, the implementation of our subgraph- basee method results in a substantial improvement in training efficiency.
Consequently, we can rapidly obtain evaluation feedback for configurations sampled from the hyperparameter space. Sec. 4.2 introduces an optimization technique for subgraph- searching that features meticulously crafted technical designs. The searched configuration usually leads to deeper GNN (i.e., 8 layers, while previous studies are usually limited to 5 or 6 layers) that increases the expressiveness of prediction. These innovations aim to balance prediction efficiency and the complexity associated with identifying optimal configurations within data and model spaces, which also contributes to improved prediction performance.
D.4 EXTENSION
Note that KG learning usually focuses more on link-level tasks, e.g., link prediction. However, we firmly believe that onessho--uubgraph link prediction has the potential to be extended and adapted for various graph learning tasks. One general direction is to adapt the one-shot-subgraph link prediction framework other kinds of graph learning tasks, e.g., the node-level or graph-level tasks.
For instance, with the PPR sampler, one can sample single-source "local" subgraph for node classification or a multi-source "global" subgraph for graph classification, where the rationale of first sampling and then prediction remains applicable. Besides, enhancing the one-shot-subgraph link prediction with instance-wise adaptation also a promising direction. That is, sampling a subgraph of suitable scale for each given query, which can potentially improve the upper limit of prediction.
Furthermore, conducting link prediction with new relations or new entities is also a frontier topic. Improving the generalization extrapolation power of GNN can be vital in practice. Considering the significant few-shot in-context learning of the large language model (LLM), an appropriate synergy between the latest LLM and current GNN will be a promising direction. Improving the efficiency and scalability of predicting with large graphs is also of great importance here.
In addition, from broader perspective of trustworthy machine learning, should also consider the intrinsic interpretability and the robustness problem. These trustworthy properties can help users understand the model better and also keep in a safe and controllable way.
23

---

Published as a conference paper at ICLR 2024
E
CASE STUDY
In this section, we show the sampled subgraph different scales on three datasets as follows.
ETS
bos
0.00
800
000
412
camoted
DieNTee
Figure 9: Subgraphs (0.1% and 1%) from WNI8RR: 2=1.9- 12,2222 2 {5305}.
0.05
cos
003
206
quety enthy
Figure 10: Subgraphs (0.1% and 1%) from WN18RR: -=9, 20, (38116)
01
Degrne sampled quety enthy
Degns tampled rontle
QUARY
Figure 11: Subgraphs (0.1 % and 1%) from WNISRR: 29, q= 1, (11186).
24

---

Published as a conference paper at ICLR 2024
033
Denagy
Degres stmmppeed artiles
Dasance quety endyy
Degros samples entiles
Datance to the Q ond
Figure 12: Subgraphs (0.1% % and 1%) from WN18RR: == 20 10, (6226)
0.75
600
0.00
602
Dug atsang vol cnd Mas
Disonce the QUYY onlly
Oegrce of Sanotel cri
Disanse Lie QLAT cily
Figure 13: Subgraphs (0.1% 1% and 1%) from WN18RR: u u= 44 12, 1= -
0.22
Dendbt
6oz
Dogres alairpled crbii
Decamoe to Madt endy
Degroe of samplel cr
Dosanss 10 L36 QUMY city
Figure 14: Subgraphs (0.1% and 1 1%) from WNISRR: u 4 [44).
Degrec Sampled eriites
Dieaance gutty min
Degres samples entiles
Detance the query ent
Figure 15: Subgraphs (0.1% and 1%) from WNI8RR: u= 20,660022200
(6777) (=5777
25

---

Published as a conference paper at ICLR 2024
0.75
0.75
6023
Degres stsamp ad end
Distance quary enlyy
Degres samples entilea
Datance to the quary ond
Figure 16: Subgraphs (0.1% 1% and 1%) from WN18RR: u 2= (172).
022
602
Doproz 0f sampled sril
Jolanu the Mait onidy
Degrce of Samotol crit
Disance la Lhe QLATY Cily
Figure 17: Subgraphs (0.1 % and 1%) from WNI8RR: == 88, 12, (4621).
0.755
6oz
Dogrss atampp vol un Maa
Disunce the QUAPY only
Degroe of samplel cr
Disane4 13 the QuAry cnly
Figure 18: Subgraphs (0.1 % and 1%) from WN18RR: w 155, 15,5, (785).
0.75
0050
Dereiy
Degree sTramp en
Disance the query ently
Degine smmpled ert
Disatce 13 the BLery cnly
Figure Subgraphs (0.1% and 1 1%) from WN18RR: ==2297, -=
22037]
26

---

Published as a conference paper at ICLR 2024
0003
0033
Degrus of moled antiis
Datance the query en
Degros samples enttlia
Datance to the quary ond
Figure 20: Subgraphs (0.1% and 1 ()) from NELL-995: 4-4,9=236, (22677}.
Dog aTsamp un
Disonce Lie quy only
Dugros samplez 410./5
Dotunce 00 tse query ond
Figure Subgraphs (0. % and 1%) from NELIL-955: == 17, 1= 274, v (57735, 61381, 61381,660444 63044)
03335
0315
Degres of wwmsleeeniiii
Dalan: Us Ruay s
Dagros Sumplce 4H0LIC
Dalunce 00 Use dLary on
Figure 22: Subgraphs (0.1 and 1%) from NELL-995:
29, -- 260,
{27725, 73985).
0.25
6000
Degree sTramp en
Disance suery ently
Degres samples mnnrls
Detance to the query ert
Figure 23: Subgraphs (0.1% and 1%) from NELL-995: u 44, -= 222, (11669}
27

---

Published as a conference paper at ICLR 2024
10
6035
Degres sTsamp end Bea
Disaance query enlyy
Degres samples entilea
Dalaance to the query ond
Figure 24: Subgraphs (0.1 % and 1%) from NELL--955: 0 -= (164).
0035
00205
Degrec Gampled eniiis
Dolan: the quary 1
Dugres samplez 4n0.ks
Dotance 00 the Queyy on
Figure 25: Subgraphs (0.1 1% and 1%) from NEL.L-955: u 166, y 260, v {6364].
8315
2
6019
Degres of sasilc enilii
Dalan: Use quary 1
Dugros sumples unELIc
Dolance D0 Use d.ary art
Figure 26: Subgraphs (0.1 1% and 1 1%) from NELL-995 u= 202, 101, {399).
0:00
0020
Degree sTramp en
Disance t1e query esity
Degres samples enIris
Debance to the query erE
Figure 27: Subgraphs (0.1 %
1%) from NELL-995:
u= 255, 2222, 0 (1631, 9925, 11229).
28

---

Published as a conference paper at ICLR 2024
Dersky
0333
Degres of mopeed entiiis
Datance the query enb
Degros samples entilea
Datance the Query ond
Figure 28: Subgraphs (0. 1% and 1%) from NELL 1=13 2-0 V= (21193, 50385,00718)
6010
2.
0033
Dog aTsamp unt
Disonce the quy only
Dugros sumples 400.
Dstunce W0 the query o
Figure Subgraphs (0. % and 1%) from NEI.L-955: == 11200, q == 38, 57377 7292, 11199).
003075
goatty
Denty
Degroc of wawpeedlorrit crUlA
Oslance to the RMCY crdy
Degrie of sumplel cr
DkAncS 2h quay only
Figure 30: Subgraphs (0. 5% and 1%) from YAGO3-10: u 1 17.17.7 - 39, (54968).
603075
Desatt
Desitt
Drgine of samplled eriites
Oxtrnce to the every enkky
Degrne sooomlled ortilies
04sancee The QUay en
Figure 31: Subgraphs (0.1% % and 1%) from YAGO3-10: 20
(3458)).
29

---

Published as a conference paper at ICLR 2024
0:00011
Doraa
Derat
60305
Degros of sampled erit
Oitance do the SuRry antyy
Degree of ortile
Delancc quary andry
Figure 32: Subgraphs 1% and 1%) from YAGO3-10: w= 0= (40490}.
000075
603015
000093
Degroz of wwmpaaallliinnno criIAA
Ostaane to the MMer crdy
Degroe of Sumpiell cii
Oksunce quay only
Figure 33: Subgraphs (0.1 % and 1%) from YAGO3-10: == 2==77q=399 (3801).
003075
Denily
Degroc of www.aallaaaarrnoo crulss
Oslanee 10 the RMCY c1dy
Depree of Sumplee M11
DMAISS QUay oniyy
Figure 34: Subgraphs (0.1 and 1%) from YAGO3-10: 29. 9= 38,
(33723, 82573).
603075
030050
Destt
Drgrne of sampled ertines
Oxtence The euery trkky
Degine sfoomiied ortilie
0esancee The QUAY en
Figure 35: Subgraphs (0.1 and 1 1%) from YAGO3-10: u 55 = 38, 18,00 (1144344 (14834 67740).
30

---

Published as a conference paper at ICLR 2024
603075
Durad
Derskyy
Degros of sampled ertt
Oslance do the Suary ontb
Depree ofaemoie ortile
Delance quary andty
Figure 36: Subgraphs (0.1% 1% and 1%) from YAGO3-100 10: a == 1= (15823).
603015
De-sty
Degroe of wwmptcalllaiino cr
Ostane to the aMer crdy
Degroe of Sumplell Mri
Oksnnce Nh quay only
Figure Subgraphs (0. % and 1%) from YAGO3-10: a 108, == 0= 7271) }.
030075
003075
Dontt
Danelt
Dagroc of www.lllllorriiii crULAS
Oslanee 10 the BMCry crdy
Deprie of Sumplcc c/1
DkAnnce 2h quay only
Figure 38: Subgraphs (0.1%) % and 1%) from YAGO3-10: u 135. 9=38, (51096)
603075
Dessy
Dersty
Drgree of sampleed eriites
Oxtrnce The ewery eriiy
Degine sooomleed ortilis
0esancee The quary en
Figure Subgraphs (0.1% 1% and 1%) from YAGO3-10: u 10 1 (26722)
31

---

Published as a conference paper at ICLR 2024
603075
DursRo
Degros of sampled ort
Ostance do The suary ontby
Depree staemoee ortile
Delance quary andry
Figure 40: Subgraphs (0.1% 1% and 1%) from YAGO3-10: u= 446 0 38, (104297).
000075
603015
000093
Degroc of www.tcllorraa....oo cr
Ostane to the aaery c1dy
Degioe of Sumpiell Mit
Oksunce quay only
Figure Subgraphs (0.1% and 1%) from YAGO3-10: a 1072, q q= 0 (33994]
003075
Danity
Degroe of www.aaallllaaooooc...ooo critis crulss
Oslanee 10 the suery otdy
Depree of Sumplael CrA
DEAunSS QUaY eniyy
Figure 42: Subgraphs (0. 1 and 1%) from YAGO3-10:
1=1255, 38. 0= 12418, 28138 71366]
603075
03050
Bersty
Drgree of sampled eriites
Oxtrnce evry triky
Degine stmomlled orilles
04sance The QUAY en
Figure 43: Subgraphs (0.15 10.1% and 1%) from YAGO3-10: == 22522,2240 39, (9476, 77502].
32


Reviews:
[{"review_id": "FoFaFYTgZa", "reviewer": "Reviewer_7ny9", "summary": "This paper introduces a new method for knowledge graph (KG) link prediction which they name reasoning. The method relies on (1) sampling the KG around the entities involved (not on e.g. computing embedding on the whole KG) and (2) reasoning on top of this subgraph. This two step process ensures efficiency as the subgraph reduces the neighborhood over which the reasoning (link prediction) is done. Step (1) involved a Page Rank based procedure that selected a subgraph based on the importance of the nodes in the KG.", "questions": "* To the above point, re language usage, please fix these.\n    * E.g. it uses the term KG Reasoning while in fact solving the link prediction task (a term used only once in the whole paper!).   \n    * Repeated use of the word paradigm, even though there isn't anything that is fundamentally new theory in their proposal/approach. \n    * The use of the word 'blazes' on p.1 \n\n* p. 3, Advantage 2. Why is the exploration/exploitation relevant for the proposed algorithms? While there is some intution behind the analogy with exploitaion/exploration the algorithm doesn't really formulate the problem using this analogy. For example there is no way to trade/balance the two. So this comparison relies on broad intuition, hence this advantage is a weak one at best. \n\n* Algorithm 1. define Alpha, K, define the shape of A and D.\n\n* How is the adjacency matrix A computed in the subgraph extraction part. Since this is a KG, not a homogenous graph, there are several adjacency matrices (one for each relation). Are these combined somehow? \n\n* I think the paper would benefit from pulling some of the technical details from the supplement to the main paper, in favor of reducing some of the verbiage in the main paper. Please consider this modification.", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The paper proposes a simple, yet somewhat novel idea. While the idea is somewhat heuristic, it is nevertheless interesting to test out its performance on this problem. \n\n* The authors perform good literature review summarizing the different categories of KG link prediction methods. \n\n* The proposal is tested empirically through several experiments.", "weaknesses": "* The paper appears to use terms and phrases that make it sound quite bombastic and somewhat unscientific (see below). \n\n* Some of the language is vague and I feel like some of the technical details from the appendix would benefit the paper. \n\n* Algorithm 1 is not clearly defined (see below). \n\n* I feel like a bit more space can be allocated to the intuition behind some of the experiments (e.g. what does the degree distribution in Fig 4 imply about the method's performance qualitatively?)", "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": "", "extra_scores": {}}, {"review_id": "wK5GBbg2cv", "reviewer": "Reviewer_RRjT", "summary": "The paper studies the reasoning on large-scale knowledge graphs and proposes to extract only one query-dependent subgraph, then reasoning on this single subgraph. Specifically, the authors propose to use personalized PageRank to assign probabilities, and then extract the subgraph according to the probabilities. Three different query-dependent message functions are used in the reasoning step. The experiments are conducted on three common datasets.", "questions": "1. The hyperparameter searching is not trivial. It would be helpful if the authors could explain more about hyperparameter searching when facing a new knowledge graph and how to select the best configuration.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated. It is reasonable to consider the one-shot subgraph reasoning problem.\n2. The paper is well-written and easy to follow.\n3. The paper provides a comprehensive literature review in preliminaries.", "weaknesses": "1. Although the problem is interesting, the proposed methodology is not surprising. The main idea is to use PPR to calculate probability and select the top of entities and relations. The reasoning on the subgraph is following the existing methods.\n2. The paper emphasizes improved efficiency, but I did not find a comparison of efficiency between the proposed method and the existing ones.\n3. The hyperparameter searching looks inefficient.", "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": "", "extra_scores": {}}, {"review_id": "5AjXzUa6Xu", "reviewer": "Reviewer_FPeS", "summary": "This paper aims to address the serious scalability problem of using the entire knowledge graph (KG) for inference. To this end, one-shot subgraph reasoning on large-scale KG is proposed. This method decouples the inference process into two steps, (i) extracting only one query-dependent subgraph and (ii) reasoning on this single subgraph. This method has higher training efficiency and stronger reasoning ability.", "questions": "1.Given that the proposed method relies on a non-parametric heuristic (PPR) for sampling, how interpretable are the final predictions and reasoning steps? Can the method provide insights into why a certain answer was chosen for a given query?\n\n2.How robust is the proposed method to noise or inaccuracies in the underlying knowledge graph? Are there any guarantees regarding the robustness of reasoning results in the presence of perturbations in the data?\n\n3.What are the potential directions for future research or extensions of this work? Are there specific aspects or challenges within KG reasoning that remain open for investigation?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The motivation of model design is clear and reasonable. It is unnecessary to utilize the whole KG in reasoning, only a small proportion of entities and facts are essential for answering specific queries, which is also supported by the experiments.\n\n2.Experiments cover several benchmarks. The model is tested on multiple datasets and shows very promising results.\n\n3.The paper is well-written and generally easy to follow.", "weaknesses": "1.In the paper, there is some similar descriptions in the discussion. For example, in section 3, the first paragraph states, 'The design principle here is to first identify one subgraph, which is relevant to a given query and is much smaller than the original graph, and then effectively reason on this subgraph to obtain the precise prediction.' This is similar to Definition 1 in section 3, which states, 'Instead of directly reasoning on the original graph G, the reasoning procedure is decoupled into two-fold: (1) one-shot sampling of a query-dependent subgraph and (2) reasoning on this subgraph.' These are also similar to what is mentioned in the introduction, 'Thereby, the reasoning of a query is conducted by (i) fast sampling of one query-dependent subgraph with the one-shot sampler and (ii) slow reasoning on this single subgraph with the predictor.'\n \n2.In sections 4.4, a significant number of symbols, abbreviations, and technical terms are employed. Some symbols are not adequately explained, which may potentially cause difficulties for readers during their reading. For example, the supp() in 4.4Theorem 1 does not provide an explanation.\n\n3.The formulas in sections 4.3 and 4.4 are not labeled, such as (6) and (7).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)