Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Authors: Minsung Hwang
Jaejun Lee
Joyce Jiyoung Whang
Venue: ICML 2025 poster (2025)
Keywords: Subgraph Reasoning
Inductive Knowledge Graph Completion
Stability
Generalization Capability
Link Prediction
Primary area: deep_learning->graph_neural_networks
TL;DR: We analyze the relationship between the stability and generalization capability of subgraph reasoning models for inductive knowledge graph completion by relating the generalization bound to the stability under the Relational Tree Mover’s Distance.

Abstract: Inductive knowledge graph completion aims to predict missing triplets in an incomplete knowledge graph that differs from the one observed during training. While subgraph reasoning models have demonstrated empirical success in this task, their theoretical properties, such as stability and generalization capability, remain unexplored. In this work, we present the first theoretical analysis of the relationship between the stability and the generalization capability for subgraph reasoning models. Specifically, we define stability as the degree of consistency in a subgraph reasoning model's outputs in response to differences in input subgraphs and introduce the Relational Tree Mover’s Distance as a metric to quantify the differences between the subgraphs. We then show that the generalization capability of subgraph reasoning models, defined as the discrepancy between the performance on training data and test data, is proportional to their stability. Furthermore, we empirically analyze the impact of stability on generalization capability using real-world datasets, validating our theoretical findings.

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Minsung Hwang' Jaejun Lee
Joyce Jiyoung Whang'
Abstract
observed entities and utilize the learned representations to predict missing links (Chung et al., 2023; Lee et al., 2023a).
Inductive knowledge graph completion aims to predict missing triplets in an incomplete knowl- edge graph that differs from the one observed during training. While subgraph reasoning mod- els have demonstrated empirical success in this task, their theoretical properties, such as stability and generalization capability, remain unexplored. In this work, we present the first theoretical anal- ysis of the relationship between the stability and the generalization capability for subgraph reason- define stability
As real-world KGs continually expand, recent research has shifted its focus to inductive KGC, where the KG that ap- pears during inference differs from the one used for train- ing (Teru al., 2020). Most models designed for trans- ductive KGC are unsuitable for inductive inference because they cannot handle unobserved entities, as these entities lack learned representations. To overcome this limitation, recent studies have adopted subgraph reasoning approaches (Teru et al., 2020; Zhu et al., 2021; Zhang & Yao, 2022). Unlike models that learn representations for individual entities and use the learned representations for link prediction, subgraph reasoning models determine the validity of a triplet by utiliz- ing the structure of the subgraph extracted around the triplet. Consequently, these models can effectively perform induc- tive link prediction using the subgraph structures extracted from the inference KG.
ing models. Specifically, the degree of consistency in subgraph reasoning model's outputs in response to differences in in- put subgraphs and introduce the Relational Tree Mover's s Distance as a metric to quantify the differ- ences between the subgraphs. We then show that the generalization capability of subgraph reason- ing models, defined as the discrepancy between the performance training data and test data, is proportional to their stability. Furthermore, we empirically analyze the impact of stability on gen- cralization capability using wealdworld datasets, validating our theoretical findings.
To theoretically explain the empirical success of KGC mod- els, several analyses have been conducted. Most of these studies focus understanding what these models are ca- pable of learning. For example, some investigate the graph structures that the models can distinguish (Barcelo et al., 2022; Huang et al., 2023), while others examine the rules within KG that the models can infer (Qiu et al., 2024). In contrast, relatively little attention has been given two criti- cal theoretical properties of subgraph reasoning models: (1) generalization capability, which refers to the discrepancy be- tween a model's performance on training and test data, and (2) stability, defined as the degree to which model's output varies in response to the changes in input. Although a recent study examined the generalization capability of knowledge graph representation learning models in a transductive set- ting (Lee et al., 2024), the stability and the generalization capability of subgraph reasoning models for inductive KGC have not been studied.
1. Introduction
Knowledge graphs (KGs) represent real-world knowledge by modeling relationships between entities as triplets (Wang et al., 2017). Due to their inherent incompleteness, nu- merous studies have focused on knowledge graph comple- tion (KGC), which aims to predict missing triplets within KGs (Bordes et al., 2013; Schlichtkrull et al., 2018). Con- ventional models for KGC operate under a transductive setting, where a KG to be completed during inference is identical the one observed during training (Bordes al., 2013). These models typically learn representations of the
In this paper, we present the first theoretical analysis of the rel relationship between stability and generalization capabil- ity of subgraph reasoning models designed for KGC. To comprehensively analyze existing subgraph reasoning mod- els, we provide the framework that can represent existing subgraph reasoning models by decomposing subgraph
'School of Computing, KAIST, Daejcon, South Korea, Corre- spondence to: Joyce Jiyoung Whang <ijwhang @ kcr>.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
soning models into two components: a subgraph extractor that extracts a subgraph associated with an input triplet from KG and Subgraph Message-Passing Neural Network (SMPNN) that computes the score of the input triplet us- ing the extracted subgraph. The proposed framework can represent well-known subgraph reasoning models, such as GralL (Teru et al., 2020), NBFNet (Zhu et al., 2021), and RED-GNN (Zhang & Yao, 2022). Within this framework, show that the differences in output scores computed by subgraph reasoning models are bounded by the Rela- tional Tree Mover's 's Distance (RTMD) between the input subgraphs, where RTMD is introduced to quantify the dif- ferences between subgraphs of KGs. We define the stability of a subgraph reasoning model as the ratio of the RTMD between the subgraphs to the difference between the scores of the subgraphs computed by its SMPNN. This measure is then used to derive generalization bound of the subgraph reasoning models for inductive KGC.
during inference have been observed during training, subgraph reasoning has been widely adopted for inductive KGC (Teru et al., 2020; Chen et al., 2021; Mai et al., 2021; Lin et al., 2022; Liu et al., 2023; Zhu et al., 2021; Zhang
& Yao, 2022; Zhu et al., 2023; Zhang et al., 2023). For instance, GraIL (Teru et al., 2020) extracts an enclosing subgraph for given triplet and labels the entities within the subgraph based on the shortest distance from the head and tail entities of the triplet. The model then computes score for the subgraph using edge attention and an R-GCN encoder (Schlichtkrull et al., 2018).
Various studies have been conducted to theoretically understand KGC models, focus- ing their expressivity (Barcelo et al., 2022; Huang et al., 2023; Qiu et al., 2024). For instance, Barcelo et al. (2022) extended the WL test (Weisfeiler & Lehman, 1968) to multi- relational graphs to explore the expressivity of GNN-based KGC models. While the expressivity of KGC models is ac- tively studied, the gencralization capability has received less attention. Recently, Lee et al. (2024) introduced frame- work called ReED that generalizes diverse knowledge graph representation learning methods and computed the general- ization bounds of the ReED framework for the transductive setting, which is not applicable to the subgraph reasoning models for inductive KGC. On the other hand, we analyze subgraph reasoning models in the inductive setting, focusing on the stability and generalization capability of subgraph reasoning models.
Theoretical Analysis on KGs
Our theoretical analysis reveals that the stability of subgraph reasoning models is a key factor influencing the generaliza- tion capability. Furthermore, we empirically validate our theoretical findings by demonstrating that RTMD can be used to infer the labels of triplets in real-world datasets, that the differences between the output scores of SMPNN are bounded by RTMD of the input subgraphs, and that stable models tend to exhibit superior generalization capability.
Our contributions can be summarized as follows:
We propose general framework for subgraph reason- ing models and derive their stability with respect to the perturbations of the subgraph structures.
Generalization Capability of Graph Neural Networks Some research has focused on the generalization capabil- ity of Graph Neural Networks (GNNs) using various ap- proaches (Scarselli et al., 2018; Garg et al., 2020; Oono & Suzuki, 2020; Ma et al., 2021; Maskey et al., 2022; Zhou et al., 2022; Ju al., 2023; Karczewski et al., 2024; Aminian et al., 2024). For example, Liao et al. (2021) computed the PAC-Bayesian generalization bound of GNNs for graph classification tasks. Furthermore, recent studies have ana- lyzed the relationship between the generalization capability and other theoretical properties of GNNs (Morris al., 2023; Franks et al., 2024; Chuang & Jegelka, 2022; Huang et al., 2024: Dong et al., 2024). For instance, Chuang & Jegelka (2022) derived the generalization bound of GIN (Xu et al., 2019) using the stability assessed by the Lipschitz con- tinuity under the Tree Mover's Distance (TMD). In contrast, we extend TMD into a form applicable to subgraphs ex- tracted from KGs and provide analysis applicable to various subgraph reasoning models.
We introduce "ecudo-metric', RTMD, specifically designed for subgraph reasoning models, and use it to compute the stability of subgraph reasoning models. We theoretically analyze the generalization bound of subgraph reasoning models and discuss the impact of the stability on their generalization capability.
We empirically show that RTMD is a suitable metric for subgraph reasoning models and examine how stability impacts generalization error on real-world KGs.
2. Related Work
Subgraph Reasoning Models for Inductive KGC Sub- graph reasoning models have been proposed to predict missing links in graphs without relying on predefined rules (Zhang & Chen, 2018). These models extract sub- graph associated with target link, relabel the nodes within the subgraph, and compute a score of the relabeled subgraph. Since these methods do not require the entities encountered
3. Inductive KGC by Subgraph Reasoning
'hiie RTMD is a pseudo-metric since there exists a pair of distinct subgraphs for which RTMD between them is O, we refer it as metric for convenience in this paper.
To provide general analysis applicable to existing subgraph reasoning approaches, we formally define the subgraph rea-
2

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
soning models for inductive KGC.
Sw with parameters is defined by
x3 (r) INITs(U)
3.1. Inductive Knowledge Graph Completion
M ([MSG (xg (xg-11)00 (u). X5 --"1 (v).", (1) (w)
knowledge graph G = (U,R,FUTT consists of a set of entities V. a set of relations R, set of triplets F C R V assumed to be known, and another set of triplets T S VxRxV for prediction, where Fnt = 0. Each triplet (h, t) is associated with label Whrt E ff11++1} +1). A label of +1 denotes a positive triplet, indicating the given triplet is true, whereas a label of -1 denotes a negative triplet, indicating the given triplet is false.
x5 (v) UPD (x9 (v), (v), (v), (MM
fw(S) RD (x5" (h), X3
(1)())) (t), GRD( (1) (w) E VsH)).)
11 where X5 (v) E Fd is embedding vector of entity
v E Vs. MSG I x Rd x R R + F is a message function, MS (t) is multiset of messages propagated to the entity v, AGG 23 Rd is an aggregation function, UPD Rd x X - R is an update function, GRD 2² + Rd is global-readout function, RD: : R x Rd x Rdd x R - R is a readout function that computes the score of the subgraph, and 0 is history function with 0(k) = k - or 0(k) = 0.
KGC is the task of predicting the labels of triplets in T based on the triplets in F. In inductive KGC, model is trained using training knowledge graph Gu = (Va, R, Fu U Th) and conducts inference on an inference knowledge graph Gi = (Vint, R, Fint U Tiur)- Note that transductive KGC is a special case of inductive KGC, where Vir = Vin and Fi Fint-
A subgraph reasoning model consists of a subgraph extractor I and an SMPNN fw- By appropriately configuring the sub- graph extractor and the functions within the SMPNN, well- known subgraph reasoning models such GralL (Teru et al., 2020), NBFNet (Zhu et al., 2021), and RED-GNN (Zhang & Yao, 2022) can be subsumed within our framework. De- tailed explanations are provided in Appendix A.
3.2. Subgraph Reasoning Models for Inductive KGC
A subgraph reasoning model uses a subgraph extractor to extract subgraph corresponding to a target triplet included T and predicts the label of the target triplet using scoring function that takes the extracted subgraph input. We formally define a subgraph extractor follows.
4. Stability of Subgraph Reasoning Models
Definition 3.1 (Subgraph Extractor). Given a knowl- edge graph G = (V, F U 7), a subgraph extractor g(G. (h, q. t)) = S is a non- non- parametric function that uti- lizes F to map a triplet (h, q, 1) E T into subgraph S. A subgraph S is denoted as S = (Vs, Es, R, INITs, (h, q, t)). where V/g and Es denote the sets of entities and triplets of the subgraph S, respectively. The function INITs: V/3 Rd generates an initial entity embedding vector with dimension do for each entity. The triplet (h, q, t) is referred to as the query triplet, and 9 is referred to as the query relation of the subgraph S. Note that h and f are always included in Vs. For each entity v in Vs. the multiset of v's neighbors is defined as Ns( = {((r, u) (u,r,u) E Es
The stability of a model refers to the degree of consistency in its outputs with respect to the changes in its inputs (Bous- quet & Elisseeff, 2002; Shalev-Shward et al., 2010). Since the subgraph extractor of a subgraph reasoning model is non parammarettiic and discrete, we define the stability of a subgraph reasoning model in terms of the stability of its SMPNN. To quantify the stability of SMPNNs, it is nec- essary measure the differences between subgraphs, as direct comparisons between subgraphs are hard to quan- tify. Therefore, we introduce the Relational Tree Mover's s Distance (RTMD) which measures differences between sub- graphs while reflecting the message- pesssagepassing mechanism of SMPNNs. Specifically, the RTMD between two subgraphs is computed as the optimal transport distance between the sets of relational computation trees of the subgraphs, where the relational computation tree represents how SMPNNs perform message-passing on the subgraphs.
A common form of subgraphs extracted by a subgraph ex- tractor is an enclosing subgraph constructed by the inter- section of the k-hop neighbor entities of h and f for each query triplet (h, g, t) (Teru et al., 2020). Given a subgraph extracted by a subgraph extractor, a scoring function of a subgraph reasoning model computes a score of the subgraph through a peessnge- In Definition 3.2, we propose framework called Subgraph Message-Passing Neural Net- works (SMPNNs),, which generalizes the scoring functions that utilize the message-passing
4.1. Optimal Transport
Optimal transport distance (Villani et al., 2009; Cuturi, 2013) is a measure used to quantify the discrepancy be- tween two probability distributions. For two multisets A = (fo 1m B = {bb,) a matrix P PA.B E Rm is referred to as a transportation plan if it satisfies
Definition 3.2 (Subgraph Message-Passing Neural Net- works). Given a subgraph S = IN, (h, q. t)). a Subgraph Message-Passie Neural Network (SMPNN)
P PA..Im PI P 1m
3

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
(1) TS (v)
RTD(
= ||INIT 1 +
INIT
llz
=
[1[
24
+w())OTTT
(on)
(wo) (p4)
%
Figure 2. A visualization of computation of the Relational Tree Distance (RTD) between two subtrees of relational computation trees. The RTD is the sum of the difference between initial entity embeddings, the penalties for different relations and queries, and the optimal transport distance between the multisets of subtrees.
Figure 1. A visualization of the construction of a depth-I relational computation tree T (v) for the entity The root entity of each subtree and the relation pointing to that subtree are derived from the multiset of e's incoming neighbors neighhors.Ns(t)..
where 1m E I is a one vector. Given a cost function 6: Ax + that maps each pair (a,, by) E A B to the transportation cost between a; and by. the optimal transport distance between A and B is defined as:
As illustrated in Figure 1, the relational computation tree is constructed by recursively adding neighboring relations and entities to the leaf nodes, which aligns with the process of updating entity embedding vectors in SMPNNs. Therefore, the relational computation tree of an entity y represents the computation tree of SMPNNs for v.
OT o = min PA.
PAstiiJ
(1)
To define the difference between the relational computa- tion trees of two entities, we consider three factors: (i) the difference between the initial embedding vectors of their root entities, (ii) the difference between the multisets of their subtrees, and (iii whether their query relations differ. However, measure the difference between the multisets of subtrees, it is necessary to first define the difference be- tween individual subtrees. Since each subtree consists of a relation and a relational computation tree, the difference between two subtrees, (r1, T()) (v1)) and (r2, T!/ (u2)) is determined by two factors: (i) the difference between the relational computation trees, 7!! (v1) and (12))) (ii) whether their relations, ri and r2, differ. This differ- ence is referred to as the relational tree distance, which is formally defined in Definition 4.2. Note that the difference between the relational computation trees is a special case of relational tree distance, obtained by introducing a virtual relation Troor shared across all relational computation trees.
The transportation plan that provides the optimal solution for Eq. 1 is referred to as the optimal transportation plan.
4.2. Relational Tree Mover's Distance
Tree Mover's Distance (TMD) (Chuang & Jegelka, 2022) is metric designed to quantify differences between graphs, particularly for analyzing the stability of wressage-passing neural networks. However, TMD cannot be directly ap- plied to analyze SMPNNs, as it only accounts for node features and graph structure, whereas the input subgraphs of SMPNNs are associated with triplets and contain edges labeled by relations. To address this issue, we propose Relational Tree Mover's Distance (RTMD), which incorpo- rates initial entity embeddings, edge labels, subgraph struc- tures, and the triplets associated with the input subgraphs to compute the differences between subgraphs. Specifi- cally, RTMD captures subgraph structures by modeling how SMPNNs process these structures, which formal- ized through the concept of relational computation tree, as defined in Definition 4.
(12). and
Definition 4.2 (Relational Tree Distance). Given two sub- 91, graphs S1 = (Vs, Ess R, INIT (h1,91,ty) t,),,),, S2 = (Vs,, Ess,, R. INiT (12, 02. 12)) and 11,12 > 0, for 2ı E Vs. V2 E Vs, and T1, E R, the relational tree distance between (r1, ((1 (v:)) and (r2, (r (v2)) is defined as
Definition 4.1 (Relational Computation Tree). Given a sub- graph S = (Vs, &s, R, INITs, (h, q. t)) and 1 > O, the depth-/ relational computation tree _ (v) of an entity E V' is defined by
RTD (ri, T (w1)). (r2, T (vz)))
T (v) = (v,0) (UB(T = (((r, T (1 ( (w)) e Ns()))
|INITs, (c:) ( + R (I[m # re) rel+1 + ail)
1
+ =u(mmx((1,1)))0Tmmm (wtpS//TTT(((((((g()) ((SUU(T (1)) SUB(T (va)))
T (v) (v))()))) (w))
where Th (v) is the depth-lrelational relational computation tree of entity u for subgraph S, w(l) is a weight function for the distance between multisets of subtrees based on the depth
where SUB ( (v)) is a multiset of subtrees of 7 (v).
The entity v is referred to as the root entity of T (v).
4

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Complction
of the subtrees, and p denotes the blank tree augmentation defined in Definition B.
Definition 4.4 (Lipschitz Continuity of SMPNNs), Given
Gn (Vr, R, U TTx) and Gint (Vut, Fint Tinr), SMPNN fw with L layers is Lipschitz continuous if there exists a constant
To quantify the difference between two multisets, we use the optimal transport distance. However, since the optimal transport distance requires the multisets to have equal sizes, and the sizes of the two multisets of neighbors may differ, we augment the smaller set by adding blank trees to match the size. This process is referred to as blank tree augmen- tation, detailed in Appendix B. Figure 2 illustrates how the relational tree distance between two subtrees is computed.
2 0 such that (f,( [wa) S 7 RTMD(S1,, S2) for any subgraphs $1 E (g e1)le E TT. U Hg(Giar E Tmm
Since Lipschitz-continuuss functions have a non-zero Lips- chitz constant, we denote 77 as the Lipschitz constant of the fw. Then, a smaller 75 indicates that the score computed by the SMPNN is less affected by the distance between sub- graphs, implying that the model is more stable. To ease of analysis, we quantify how stable an SMPNN is by defining its stability as Cj = के Therefore, the higher Cj implies the lower Lipschitz constant and the more stable SMPNN.
Finally, we define the RTMD between two subgraphs by considering (i) the difference between the head entities of the query triplets, (ii) the difference between the tail enti- ties of the query triplets, and (iii) the difference between the multisets of relational computation trees of all entities in the subgraphs. The differences between the head and tail entities are measured using the relational tree distances between their relational computation trees, while the differ- ence between the multisets of relational computation trees is quantified by the optimal transport distance. RTMD is formally defined in Definition 4.3.
Note that we assume the message, aggregation, update, global-readout, and readout functions of the SMPNNs to be Lipschitz continuous, which holds for the SMPNNS of many existing subgraph reasoning models such as GralL, NBFNet, and RED-GNN, as detailed in Appendix A. Using the Lipschitz constant of each function. derive the upper bound of the Lipschitz constant of the SMPNNs.
Definition 4.3 (Relational Tree Mover's 's Distance). Given two subgraphs S1 = (Vs,. Es, R, INIT (h1, q1, t1)), S2 = (Vs., Es,, R. IN (h2. q2. t2)) and L > 0, Re- lational Tree Mover's 's Distance (RTMD) between S1 and S. is defined by
Theorem 4.5 (Lipschitz Constant of SMPNNs). Given Gu = (Vu. R, U Tu). Gill (Vint, R, Fint U Tiat), and an SMPNN fw with L. layers, if the message, aggregation, update,
and readout functions of fw are Lipschitz continuous, then fw Lipschitz continuous with the Lipschitz constant ny and the following holds:
RTMD(S;, 8,) = RTD((FFooo) 1/ (ha)), (Frccr,
T3 (:2) (h)))+
(Froa S5 (t)), (Fron; T5p (tz)))+
OTR ((l(reet, S1 (0i) ))/ E Vss B)
1-1 (77)) (T. + 1) (TEEtI ,0)
((k) k - 1
Tf S
(F T S2 (e2)) U2 Vs, 1I)
O(k) = 0
where T (v) is the depth-L relational computation tree of entity v for subgraph S, and Froat is a virtual relation.
n = max (1 upu + dmax B(0) 11) Bd) B(O) 4(0)
upd age msg: upd agg A
While the query relation is taken into account when com- puting the difference between relational computation trees, the head and tail entities of the query triplet are considered during the computation of RTMD. This distinction arises because SMPNNs incorporate the query relations during message-passing whereas the head and tail entities serve solely as the identities of the subgraphs and are not directly utilized in the message-passing.
R| B cil)
RR ((0) A (1) D())
upd age mag! 1),
upd age
imgg
2
(1++)) = max (Add Bid, Grd
2 max (Prrl (Mirl))
where ISIS A.g.. Bingg Omg-. Dilly are the Lipschitz constants of the message function, Alls is the Lipschitz (1) B(())
constant of the aggregation function, Apds upd are the Lip- schitz constants of the update function, Aged is the Lipschitz constant of the global-readond function, Ant, Bad, Onts Dra are the Lipschitz constants of the readout fanction, and dmax is the maximum degree of Gu and Gint-
4.3. Stability of SMPNNS
Lipschitz continuity is a property of a function that holds when the difference between the outputs of a function is bounded by the difference between the inputs. Therefore, Lipschitz-continuous functions are also referred to as stable functions (Huang et al., 2024; Dong et al., 2024; Wang et al., 2022; Chuang & Jegelka, 2022). To define the stable SMPNNs, we define the Lipschitz continuity of SMPNNs with respect to the RTMD as follows.
We provide proof for Theorem 4.5 in Appendix C. Accord- ing to Theorem 4.5 and Definition 4.4, the stability increases as the Lipschitz constants of the functions in the SMPNNs become smaller. Therefore, we can compare the stability of subgraph reasoning models by comparing the Lipschitz con- stants of these functions. For instance, while the Lipschitz
5

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
constant of the aggregation function that uses sum aggre- gator is 1, the Lipschitz constant of the aggregation function that uses mean aggregator is reciprocal of the maximum degree of the KG. This indicates that the subgraph reasoning model using a mean aggregator as the aggregation function is more stable than the model using a sum aggregator as the aggregation function. Detailed calculations of the Lipschitz constants for each function are provided in Appendix A.
risk is defined as the expectation of the empirical risk:
LolSw: 7) Py (Zo(Iw)>))
To assess the generalization capability of a subgraph rea- soning model, we derive a generalization bound which is defined as the upper bound of a generalization error. The generalization error of a subgraph reasoning model with an SMPNN fw is defined by [G 0) La. (ff: 7) where G is a training KG and Gint is an inference KG. We use the expected O-margin risk since we are interested in the classification accuracy on the inference KG. Additionally, since the training KG and the inference KG are different in the inductive setting, the generalization error depends on the expected risk discrepancy in Definition 5.2.
5. PAC-Bayesian Generalization Bound of Stable Subgraph Reasoning Models for Inductive KGC
We present the first PAC-Bayesian generalization bound of subgraph reasoning models for inductive KGC and relate their stability to their generalization capability.
Definition 5.2 (Expected Risk Discrepancy). Given
5.1. Assumptions
G Gint, a subgraph reaoning model with a subgraph ex- tractor g and an SMPNN fw. and a distribution P on the parameter space of fw. for any À >> and 7 2 0, the ex- pected risk discrepancy between Gu and Gint with respect to P, X, and y is defined by
We make the following assumptions to derive the general- ization bound of the subgraph reasoning models.
A.1 Label y of triplet e in a knowledge graph G is drawn from a distribution conditional to the subgraph corre- sponding to i.e., y ~ P(Ylg((C e)), where Y is random variable that follows binomial distribution. A.2 In a knowledge graph G = (V,, R,F FUUTT T), the set of triplets F contains sufficient information for predicting the labels of the triplets in T.
D(P,),7)
(2 =In (Bwwp [exp (2 (won(ww:?) 2) La (w)))))))))))))))))
Assumption 1 follows from the underlying assumption of the subgraph reasoning models, and Assumption 2 ensures that the subgraph reasoning model can predict the label of the subgraph based solely on the given KG.
where exp is exponential function.
We utilize the PAC-Bayesian approach which computes the generalization bound based on the KL divergence between the posterior distribution Q and the prior distribution P over the parameter space. The prior distribution is defined independently of the training dataset, while the posterior distribution the distribution after training. Originally, the PAC-Bayesian approach was used to derive generalization bounds for stochastic models, while most subgraph reason- ing models are deterministic. Therefore, we present the PAC-Bayesian generalization bound of deterministic sub- graph reasoming models in Theorem 5.3 by extending the PAC-Bayesian generalization bound for stochastic classi- fiers introduced by Ma et al. (2021).
5.2. PAC-Bayesian Generalization Bound for Inductive Knowledge Graph Completion
To measure the risk of a subgraph reasoning model, we employ a 7-margin risk. The y-margin risk increases when a score for a positive triplet is less than or equal to 7y or when a score for a negative triplet is greater than or equal to -y. Note that the y-margin loss, a differentiable approximation of a 7-margin risk, is commonly used loss function for inductive KGC (Teru et al., 2020).
Definition 5.1 (y-margin Risk), Given G= (U)
Theorem 5,3 (PAC-Bayesian Generalization Bound of Deterministic Subgraph Reasoning Models). Given Gu= (V,,R,F, U Tw), Gint (Vunt Fut U Tua), and a subgraph reasoning model with a subgraph ex- tractor 9 and an SMPNN fw. for any prior dis- tribution P and posterior distribution Q on the pu- rameter space of fw constructed by adding random noise w to w such that P( [m [/ (r))).)) f [w(g(Gu, c))l, maxeeTa Is (g(GGe c)) ) fw (g(GGat (at, e))l) < 7) > 1o, and 7 > O, X > O, the following holds with proba-
and subgraph reasoning model with subgraph extractor g and an SMPNN fw with parameters w, for any 2 0, its empirical y-margin risk on G is defined by
Eo(sw:7)
1
Σ (N.T:E)T
[Jhn (g(G, (h, s [n]
[T|
where [:] an indicator function. The expected m-margin
6

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
bility at least 1 1-66 8:
In Theorem 5.4, the upper bound of the expected risk dis- crepancy increases the optimal transport distance between the multisets of subgraphs extracted from the training KG and the inference KG increases. A large optimal trans- port distance hetween the multisets of subgraphs indicates a more significant difference between the distributions of subgraph structures. This is consistent with existing analy- ses, which show that the generalization capability decreases as the difference between source and target distribution increases (Chuang & Jegelka, 2022; Shen et al., 2018). Fur- thermore, as the stability Cj of the SMPNN increases, the expected risk discrepancy decreases. A large Cj implies a smaller difference in the scores calculated for subgraphs with small distances, indicating a more stable model. Thus, subgraph reasoning model with a more stable SMPNN tends to exhibit a higher generalization capability.
(our(fw.0) 0) - (Sw 7)+ X²
+ (P. (P.A. )) 4|Tx|
2KL())P) + In
where 3)) is the expected risk discrepancy between G and Gint and (L())P) is KL divergence of Q from P.
We derive Theorem 5.3 by approximating a determinis- tic model by introducing stochastic model generated by adding random perturbations W to the fixed parameter w, which is common technique for translating a deterministic model into a stochastic model (Liao et al., 2021; Ma et al., 2021; Neyshabur et al., 2018; Lee et al., 2024). A detailed proof is provided in Appendix D.1.
5.3. Upper Bound of the Expected Risk Discrepancy
6. Experiments
To discuss the generalization capability of subgraph reason- ing models, we analyze the generalization bound presented in Theorem 5.3 which depends on both the KL divergence and the expected risk discrepancy D(P, y). The KL di- vergence represents how far the learned distribution is from the prior distribution on the parameter space, and it increases as the complexity of the model grows, e.g., increasing the norm of learnable weight matrices or the number of layers. This term arises from the definition of the PAC-Bayesian approach (McAllester, 2003) and is also present in other PAC-Bayesian generalization bounds (Liao et al., 2021; Lee et al., 2024). In contrast, the expected risk discrepancy D(P, X, 7) is a key factor that affects our generalization bound for inductive KGC, where the training KG and infer- ence KG are separately defined. Therefore, to focus on the discrepancy between the training KG and the inference KG, we derive the upper bound of the expected risk discrepancy in Theorem 5.4 and provide its implications.
In the previous section, we provided our theoretical findings on the stability and generalization capability of subgraph reasoning models for inductive KGC. To empirically val- idate our findings, we conduct experiments on real-world KGs using the inductive KGC datasets provided in Teru et al. (2020). Specifically, we use v3 of WNI8RR (WNv3), v1 of FB15K-237 (FBv1), and v2 of NELL-995 (NLv2). For the triplets in Ter and Timi, we extract 2-hop enclosing subgraphs using Fir and Fint. respectively. Further experi- mental details are provided in Appendix E.
6.1. Label Classification using RTMD
We demonstrate that RTMD is a valid metric for quantifying differences between subgraphs extracted from real-world KGs. Figure 3 presents t-SNE visualizations of subgraphs based on RTMD with layers. Specifically, the distance between points in the plot is proportional to the RTMD between subgraphs corresponding to the points. The results show that positive and negative triplets are well clustered according to their labels in WNv3. While the clustering is less distinct in FBv1 and NLv2, triplets in these datasets still exhibit a tendency to form based clusters.
Theorem 544 (Bound of D(P.A.7) Given Gv (Vu, R, F, TT), G = (Vint, Fin U Tat),, and a sub- graph reasoning model with a subgraph extractor g and an SMPNN Iw with stability C, for any prior distribution P and posterior distribution Q on the parameter space of fw: and x2 > O, the following holds:
Furthermore, for each dataset, we evaluate the classifica- tion accuracy of subgraphs corresponding to positive and negative triplets using a support vector machine (SVM) clas- sifier with an indefinite kernel exp(-0.1 x RTMD) (Luss & d' Aspremont, 2007), following Chuang & Jegelka (2022). We set the number of layers RTMD as = 2 or L 3. Table I reports the label classification accuracies of the SVM classifiers. Since the datasets contain equal numbers of positive and negative triplets, the baseline accuracy of ran- dom classification is 0.5. The classification results indicate that an SVM classifier can effectively distinguish subgraphs with different labels using RTMD, which demonstrates that
D(P, A,) ( max(O, Tal
2 OT TTRIMD(10 (Mat Ta))
1) + JC max( Tar) (Tu))
[Tad
where vb is the empty subgraph augmentation defined in Definition D.2.
The term (T Tw)) is the optimal transport dis- tance between the multisets (lg(Gn, e))ee E TwB and HL(GGant ej)e, E ]. Since the sizes of two sets of triplets differ, empty subgraph augmentation eb adds empty subgraphs to the smaller multiset of subgraphs. We provide the proof for Theorem 5.4 in Appendix D.2
7

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Complction
fullis
follis
Score DIF:
Scor Oif.
Scoom Diff
Distance (log scale)
Distance (log scale)
Distance (log scale)
(a) WNv3
(b) FBv1
(c) NLv2
(a) WNv3
(b) FBv1
(c) NLv2
Figure 3. t-SNE visualizations of subgraphs using RTMD. Blue and orange points represent positive and negative subgraphs, re- spectively. The points tend to be clustered according their labels.
Figure 4. Seatter plots of RTMD versus the score differences on WNv3. and NLv2. The maximum score difference increases as RTMD between subgraphs increases.
Table Label classification accuracies of support vector machine classifiers on WNv3, FBv1, and NLv2 using RTMD with 2 and 3 layers. Random classification accuracy is 0.5.
Correlation: -0.5759
Correlation: -0.5134
Correlation: -0.4912
Gen, Error
Gen. Error
Gen. Error
WNv3
FBv1
NLv2
L 2
0.8204
0.7743
0.8652
logiStabilliy)
logiStabillty)
logiStabiliiy)
L 0.8205
0.7739
0.8654
(a) WNv3
(b) FBv1
(c) NLv2
Figure 5. Comparisons of stability and generalization error on WNv3, FBv1, and NLv2. The dashed lines illustrate the nega- tive correlations between stability and generalization error.
RTMD is an appropriate metric for quantifying the distance between subgraphs.
6.2. Comparing RTMD with Scores
SMPNN as detailed in Appendix E. For each trained model, we compute its empirical Lipschitz constant (Chuang & Jegelka, 2022), defined as ma RTMD .82)
In Section 4.3, we defined the Lipschitz continuity of SMPNNs using RTMD and proved that existing SMPNNs are Lipschitz continuous. To further support our theoret- ical findings, we empirically demonstrate that SMPNNS are indeed Lipschitz continuous with respect to RTMD. Specifically, we use GralL (Teru et al., 2020) as represen- tative of SMPNN model, denoted as fw. and train fw using Tu of each dataset. For each pair of subgraphs S2 E HorGGr e)le lee E TTr))) U (lg(Ginr; e)le E Tm we compute RTMD(S and the score difference (S1 In this computation, the number of layers in both the RTMD and the subgraph reasoning model is set to 3. Fig- ure 4 displays the scatter plots of RTMD(S), (S1, S2) against (Si) fw fw(()) (S2) in the WNv3, FBv1, and NLv2 datasets. Across all datasets, we observe that the maximum score difference increases as RTMD increases, demonstrating the Lipschitz continuity of fw- Moreover, the results indicate that the bound defined by RTMD approximates this trend, showing that RTMD is valid metric for defining the Lips- chitz continuity of SMPNNs.
( where
S1, S2 E (( e)le E TT H[g(Ginr e)le E Tmmr))- We then utilize the reciprocal of the empirical Lipschitz con- stant of a model as its stability. To assess the generalization capability of SMPNNs, we compute the generalization error defined in Section 5. Figure presents the generalization errors of different subgraph reasoning models and their stability, along with the average Pearson correlation coeffi- cients between generalization errors and stability. Across all datasets, we observe negative average Pearson correla- tion coefficients, which indicates that generalization error decreases as the stability increases, i.c., a positive correla- tion between generalization capability and stability. Also, Table provides correlation values, p-values, and 95% con- fidence intervals regarding the correlation between stability and generalization errors WNy3, FBvl, and NLv2. Since the p-values are all below 0.01 and the 95% confidence in- tervals do not include zero, we can conclude that the ob- served correlations are statistically significant. These results confirm that our theoretical finding, i.e., stable subgraph rea- soning models exhibit high generalization capability, also holds in real-world datasets.
6.3. Comparing Stability with Generalization Errors
As described in Section 5.3, we have theoretically shown that more stable model tends to exhibit better generaliza- tion capability. To empirically validate this claim, we train 48 different subgraph reasoning models, including GralL, NBFNet, RED-GNN, and their variations, generated by per- muting the candidate functions of each component of the
7. Conclusion and Future Works
We establish the relationship between stability and the gen- eralization capability of subgraph reasoning models for in- ductive KGC. To facilitate a comprehensive analysis, we
8

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Acknowledgements
Table 2. The correlation values, p-values, and 95% confidence intervals regarding the correlation between stability and generaliza- tion errors on WNv3, FBv1, and NLv2. If the p-value lower than 0.01 and the 95% confidence interval does not include zero, we conclude that the observed correlation is statistically significant.
This work was supported by the NRF of Korea grant funded by MSIT (65% from RSS-0225-0055008 2022-NR068758) and the IITP grant funded by MSIT (30% from 20-2022-11220669, (Part 4) Development of AI Tech- nology to support Expert Decision-making that can Explain the Reasons/Grounds for Judgment Results based on Expert Knowledge).
5% from RS-
Dataset
Corr.
p-value
95% Confidence Interval
WNv3
-0.5759
0,00019
(-0.7584, -0.3097) (-0.7013, -0.2589)
FBvl
-0.5134
0.00031
NLv2
-0.4912
0.00584
(-0.7235, -0.1591)
References
Aminian, G., He, Y., Reinert, G., Szpruch, L., and Cohen, N. Generalization error of graph neural networks in the mean-field regime. In Proceedings of the 4 s1st International Conference on Machine Learning, pp. 1359- 1391, 2024.
provide a framework that can represent various existing subgraph reasoning models. In this framework, we define the stability of subgraph reasoning models with respect to RTMD. Using the PAC-Bayesian approach, we derive the first generalization bound for subgraph reasoning models in the inductive setting and show that a more stable subgraph reasoning model exhibits better generalization capability. On real-world KGs, we validate our theoretical findings and ensure they are aligned with empirical observations. Our analysis highlights the importance of designing stable sub- graph reasoning models enhance generalization capability in inductive KGC.
Barcelo, P., Galkin, M., Morris, C., and Orth, M. R. Weis- feiler and leman go relational. In Proceedings of the 1st Learning on Graphs Conference, 2022.
Bordes, A., Usunier, N., Garcia-Duran, A., Weston, J., and Yakhnenko, O. Translating embeddings for modeling multi-relational data. In Proceedings of the 27th Con- ference on Neural Information Processing Systems, pp. 2787-2795, 2013.
Bousquet, O and Elisseeff, A. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
We will further explore additional theoretical properties of subgraph reasoning models, such as their expressive power and how they relate to stability and generalization capability. Also, we plan to extend our analyses to scenarios where both unobserved entities and unobserved relations appear during inference (Lee al., 2023b; Geng et al., 2023).
Chen, J., He, H., Wu, F., and Wang, J. Topology- cor- relations between relations for inductive link prediction in knowledge graphs. In Proceedings of the 35th AAAI Con- ference on Artificial Intelligence, pp. 6271-6278, 2021.
Chuang, C.-Y. and Jegelka, S. Tree mover's distance: Bridg- ing graph metries and stability of graph neural networks. In Proceedings of the 36th Conference on Neural Infor- mation Processing Systems, pp. 1994422577 2022.
Impact Statement
This paper provides a theoretical foundation for understand- ing stability and generalization capability in subgraph rea- soning models. Our primary contributions are theoretical, aiming to advance the fundamental understanding of induc- tive knowledge graph completion. By establishing theoreti- cal insights into how stability influences generalization, our work provides guidance for designing more robust and reli- able subgraph reasoning models for knowledge graph com- pletion. Knowledge graph completion models are widely used various applications such as information retrieval, recommendation systems, and biomedical research, where ensuring model stability and generalization capability is crucial for reliable decision- decision-making. Our theoretical find- ings contribute to developing methodologies that improve model robustness, potentially leading to more reliable pre- dictions in real-world applications. We encourage future research to further explore the implications of stability and generalization in safety-critical domains.
Chung, C., Lee, J., and Whang, J. Representation learning on hyper-relational and numeric knowledge graphs with transformers. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 310-322, 2023.
Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. In Proceedings of the 27th Conference on Neural Information Processing Systems, pp. 2292- 2300, 2013.
Dong, Z., Zhang, M., Payne, P., Province, M. A., Cruchaga, C., Zhao, T., Li, F., and Chen, Y. Rethinking the power of graph canonization in graph representation learning with stability. In Proceedings of the 12th International Conference on Learning Representations, 2024.

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Feydy, J., Roussillon, P., Trouvé, A., and Gori, P. Fast and scalable optimal transport for brain tractograms. Medical Image Computing and Computer Assisted Intervention -MICCAI 2019.
Lee, J., Chung, C.,, and Whang, J. J. InGram: Inductive knowledge graph embedding via relation graphs. In Pro- ceedings of the 40th International Conference on Ma- chine Learning, Pp. 18796-18809, 2023b.
Flamary, R., Courty, N., Gramfort, A., Alaya, M. Z., Bois- bunon, A., Chambon, S., Chapel, L., Corenflos, A., Fatras, K., Fournier, N., Gautheron, L., Gayraud, N. T., Janati, H., Rakotomamonjy, A., Redko, I., Rolet, A., Schutz, A., Seguy, V., Sutherland, D. J., Tavenard, R., Tong, A., and Vayer, T. POT: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
Lee, J., Hwang, M., and Whang, J. J. PAC- Aay-ssaeii gen- eralization bounds for knowledge graph representation learning, In Proceedings of the 41st International Con- ference on Machine Learning, pp. 26589-26620, 2024.
Liao, R., Urtasun, R., and Zemel, R. A PAC-Bayesiag approach to generalization bounds for graph neural net- works. In Proceedings of the 9th International Confer- ence on Leurning Representations, 2021.
Franks, B. J., Morris, C., Velingker, A., and Geerts, F. Weisfeiler-Leman at the margin: When more expressivity matters. In Proceedings of the 41st International Confer- ence on Machine Learning, pp. 13885-13926, 2024.
Lin, Q., Liu, J., Xu, F., Pan, Y., Zhu, Y., Zhang, L.,, and Zhao, T. Incorporating context graph with logical reasoning for inductive relation prediction. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 893-903, 2022.
Garg, V. K., Jegelka, S., and Jaakkola, T. Generalization and representational limits of graph neural networks. In Proceedings of the 37th International Conference on Ma- chine Learning. pp. 3419-3430 2020.
Liu, T., Lv, Q., Wang, J., Yang. S., and Chen, H. Learning rule-induced subgraph representations for inductive rela- tion prediction. In Proceedings of the 37th Conference on Neural Information Processing Systems, pp. 3517-3535, 2023.
Geng, Y., Chen, J., Pan, J. Z., Chen, M., Jiang, S., Zhang, W., and Chen, H. Relational message passing for fully inductive knowledge graph completion. In Proceedings of the 2023 IEEE 39th International Conference on Data Engineering, pp. 1221-1233, 2023.
Luss, R. and d' d'Aspremont, A. Support vector machine classification with indefinite kernels. In Proceedings of the 21st Conference on Neural Information Processing Systems, 2007.
Huang, X., Romero, M., Ceylan, I., and Barceló, P. A theory of link prediction via relational weisfeiler-leman on knowledge graphs. In Proceedings of the 37th Con- ference on Neural Information Processing Systems, pp. 19714-19748, 2023.
Ma, J., Deng, J., and Mei, Q. Subgroup generalization and fairness of graph neural networks. In Proceedings of the 35th Conference on Neural Information Processing Systems, pp. 1048-1061, 2021.
Huang, Y., Lu, W., Robinson, J., Yang, Y., Zhang, M., Jegelka, S., and Li, P. On the stability of expressive posi- tional encodings for graphs. In Proceedings of the 12th International Conference on Learning Representations, 2024.
Mai, S., Zheng, S., Yang, Y., and Hu, H. Communicative message passing for inductive relation reasoning. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 4294-4304 2021.
Ju, H., Li, D., Sharma, A., and Zhang, H. R. Generaliza- tion in graph neural networks: Improved PAC- -AC-Bayesian bounds on graph diffusion. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pp. 6314-6341, 2023.
Maskey, S., Levie, R., Lee, Y., and Kutyniok, G. Generaliza- tion analysis of message passing neural networks on large random graphs. In Proceedings of the 36th Conference on Neural Information Processing Systems, pp. 4805-4817, 2022.
Karczewski, R., Souza, A. H., and Garg, V. On the general- ization of equivariant graph neural networks. In Proceed- ings of the 41 International Conference on Machine Learning, pp. 23159 231662238661111111 2024.
McAllester, D. Simplified PAC-Bayesian margin bounds. In Proceedingy of the 16th Annual Conference on Compu- tational Learning Theory and 7th Kernel Workshop, pp. 203-215, 2003.
Lee, J., Chung, C., Lee, H., Jo, S., and Whang. J. J. VISTA: Visual- textual knowledge graph representation learning. In Findings of the Association for Computational Linguis- fies: EMNLP 2023, pp. 7314-7328, 2023a.
Morris, C., Geerts, F., Tönshoff, J., and Grohe, M. WL meet VC. In Proceedings of the 40th International Conference on Machine Learning, pp. 25275-25300 2023.
10

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Neyshabur, B., Bhojanapalli, S., and Srebro, N. A PAC-Bayesian approach spectrally-normaaizze mar- gin bounds for neural networks. In Proceedings of the 6th International Conference on Learning Representations, 2018.
Wang, Q.. Mao, Z.., Wang, B., and Guo, L. Knowledge graph embedding: A survey of approaches and applications. IEEE Transactions Knowledge and Data Engineering, 29(12) 2743, 2017.
Weisfeiler, B. and Lehman, A. A. A reduction of graph canonical form and algebra arising during this reduction. Crauchno-Technicheskiee Informatsia, 2(9): 12-16, 1968.
Oono, K. and Suzuki, T. Optimization and generalization analysis of transduction through gradient boosting and application to multi-scale graph neural networks. In Pro- ceedings of the 34th Conference on Neural Information Processing Systems, pp. 18917-18930, 2020.
Xu, K., Hu, W., Leskovec,, J., and Jegelka, S. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations. 2019.
Qiu, H., Zhang, Y., Li, Y., and Yao, Q. Understanding ex- pressivity of GNN in rule learning. In Proceedings of the 12th International Conference Learning Representa- tions, 2024.
Yang. B., Yih, Wi-t,, He, X., Gao. J., and Deng. L. Embed- ding entities and relations for learning and inference in knowledge bases. In Proceedings of the 3rd International Conference on Learning Representations, 2015.
Scarselli, F., Tsoi, A. C., and Hagenbuchner, M. The Vapnik- Chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248-259, 2018.
Zhang, M. and Chen, Y. Link prediction based on graph neural networks. In Proceedings of the 32nd Conference Neural Information Processing Systems, 2018.
Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., and Welling, M. Modeling relational data with graph convolutional networks. In Proceedings of the 15th Extended Semantic Web Conference, pp. 593-607, 2018.
Zhang, Y. and Yao, Q. Knowledge graph reasoning with relational digraph. In Proceedings of the ACM Web Con- ference 2022, pp. 912-924, 2022.
Shalev-Shwer Saalev-Shwart..33 S., Shamir, O., Srebro, N., and Sridharan, K. Learnability, stability and uniform convergence. Jour- nal of Machine Learning Research, 11(90))2635-2677, 2010.
Zhang, Y., Zhou, Z.,, Yao, Q. Chu, X., and Han, B. AdaProp:
Learning adaptive propagation for graph neural network based knowledge graph reasoning. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3446-3457, 2023.
Shen, J., Qu, Y., Zhang, W., and Yu, Y. Wasserstein distance guided representation learning for domain adaptation. In Proceedings of the 32th AAAI Conference on Artificial Intelligence, pp. 4058 4063-006,2200 2018.
Zhou, Y., Kutyniok. G., and Ribeiro, B. OOD link prediction generalization capabilities of pressage-passingg GNNs in larger test graphs. In Proceedings of the 36th Conference on Neural Information Processing Systems, pp. 20257- 20272, 2022.
Socher, R., Chen, D., Manning, C. D., and Ng, A. Y. Rea- soning with neural tensor networks for knowledge base completion. In Proceedings of the 27th Conference on Neural Information Processing Systems, pp. 926-934, 2013.
Zhu, 7., Zhang, Z.,, Xhonneux, A. C.,, and Tang. J. Neural Bellman-Forr networks: A general graph neural network framework for link prediction. In Proceedings of the 35th Conference Neural Information Processing Systems, pp. 29476-29490 2021.
Sun, 7.,, Deng, H., Nie, J., and Tang. J. RotatE: Knowl- edge graph embedding by relational rotation in complex space. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Teru, K. K., Denis, E. G., and Hamilton, W. L. Inductive relation prediction by subgraph reasoning. In Proceed- ings of the 37th International Conference on Machine Learning, pp. 9448-9457, 2020.
Zhu, Z.. Yuan, X., Galkin, M., Xhonneux, L.-P., Zhang, M., Gazeau, M., and Tang, J. **Net: A scalable path- based reasoning approach for knowledge graphs. In Pro- ceedings of the 37th Conference on Neural Information Processing Systems, pp. 59323-59336, 2023.
Villani, C. et al. Optimal transport: old and new, volume 338. 2009.
Wang, H., Yin, H., Zhang, M., and Li, P. Equivariant and stable positional encoding for more powerful graph neu- ral networks. In Proceedings of the 10th International Conference on Learning Representations, 2022.

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
A. Instantiatation of Existing Subgraph Reasoning Models
subgraph reasoning model consists of a subgraph extractor and an SMPNN. By appropriately configuring the subgraph extractor and the functions within the SMPNN, we can represent existing well-known models for inductive KGC by subgraph reasoning. Furthermore, under Assumption I. each function satisfies Lipschitz continuous.
Assumption A.1. We assume that the Lg-norms of all weight vectors, weight matrices, and relation embedding matrices upper bounded by Additionally, we assume that the L2-norms of the entity representation vectors computed at every layer of SMPNNs are upper bounded by B.
The Lipschitz continuity for each function in SMPNNs is defined as follows: Definition A.2 (Lipschitz Continuity), A message function MSG of SMPNNs is Lipschitz continuous and only if there
exist constants A Bung. Omngg D Dmsg 2 0 that satisfies
[MSG (a1, a2, (1) MSG (b), , b2, r2, 92)
<A0 a b1lla 11112 + B ||y ball2 + mag 1 Ir * r2] + D [ + 42l
Given transportation plan PA. between A and B, aggregation function AGG of SMPNNs is Lipschitz continuous if and only there exists a constant Aggs 2 0 that satisfies
|AGG ((a:)==) - (B (bb S
(()) Agg P.
Σ
bsll2
1
An update function UPD of SMPNNs is Lipschitz continuous if and only if there exist constants A!!) B that satisfies
|UUD (1) (a). a2) - UPD (b1. b2)1l2 S A - bill2 Boal bella
Given transportation plan PA.S between A and B, global-readout function GRD of SMPNNs is Lipschitz continuous if and only if there exists a constant Agnt 2 0 that satisfies
||RD((A= = ((.))) GRD(B ((by)) S Agu Σ
P..s( - -bill2
in
readout function RD of SMPNNs is Lipschitz continuous if and only if there exist constants Ada Bed, Crd, Díd 2 0 that satisfies
[R a2, a3, (1) RD(b,, b2, b3, 92)l
<Al a -bll2 Bral a2 b2ll2 + Gailag balla Dral + q2]
where n > a, by E Rd for 1 < i,j S n. and 12, 41, 12 R.
Now, we demonstrate how GralL (Teru et al., 2020), NBENet (Zhu et al., 2021), and RED-GNN (Zhang & Yao, 2022) can be instantiated as subgraph reasoning models.
A.1. Instantiating GralL
GralL (Teru et al., 2020) can be instantiated as follows:
1.1.1. SUBGRAPH EXTRACTION
GralL extracts the enclosing subgraph for the head and tail entities of given triplet, which is constructed by the intersection of k-hop neighbors entities from the head and tail entity. Therefore, the subgraph extractor is function that extracts the enclosing subgraph for f and in the triplet (h, t).
A. 1.2. INITIALIZATION
GralL applies a double radius vertex labeling scheme to the entities within the subgraph. This scheme encodes the shortest path distances from each entity to the head and tail entities as one-hot vectors and concatenates these vectors. Therefore, by setting INIT's to the double radius vertex labeling scheme, the initial labeling of Grall. can be instantiated.
12

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Complction
A. 1.3. SUBGRAPH MESSAGE-PASSING NEURAL NETWORKS
Message Function
The message function of GralL is formulated as follows.
MSG (9) (xg
1--1) X (v), (w),
(u),
10) q.g.Eu ((a (9) ReLU 1 01 (1 (w) (u) + W (1 (1-1) X3
2 X5 (v) W [r] + W (1) R. + bi) + b2)
where ( learnable weight vectors that satisfy the Assumption A.I, and by is a learnable parameter, is a sigmoid function, and ReLU is ReL.U activation function. The Lipschitz continuity of the message function of Grall. can be formally established as follows.
WT, R. are learnable weight matrices that satisfy the Assumption A.I, 5 b, are
(XS)
51 (w.)) (t- (f-1) ((s)) - (x (1-1)
Xs1
(ua). X22
(- ra.ill
<llo
with X5,
(111) (us) - - (1)
22.00 Wll 11-1) (uz)lla
x
(w!*>)) x2 (ws)) - whi
x2 (wz)) + (a (2-3)
(0)
W a-1)) (wx)ll2
22202))
12 82
[|! x (w1)) w x (w2) la 11111 ogg [ (uz)lla
slal
[[ (x8, (wn) x3, (uz)) + (w!) w
x2, (uailla + 1: "2.00
|| x2 (ug)ilz
ag (IW!!) [allx (wn) x 2) (w2))la + | Wall ((wa)lla) + 10 10 02.
|I| / llallxg (ww2)laa
Sk|is!] (u)) x (ws)lla + 2x/1/r # ra] + xBla 111 22iin
For the attention value Origuena the following inequalities hold.
1 |ar
(la(a.))
Re (1-1) (mn) W Th xs (m)) ( [.[ (. [qi] + bI) + b2) -
a(ag)
ReLU (1-1)
X5 (u2) + + (1-1) (v:) w R.
X3
W (1) R., [0x] + b.) + b2)l
$Ia!)
ReLU
(m1) W (-
_ R.
R. [.]] b1)
ReLU
(111) (wm) + _ (1-1) (12) + w [m
w ( R. [92] + bI)l
82
x5
<11ag
ReLU 51 (u1) + 22
(1
R. [2:] b.)
Re
8 (w2) + X5
1-1)
11-1)
[,) [p2] bz))
$llag"
x (w1) + W
(-1))
(1
R
2
(w/2 59
(--) (wz) + W
(1-1)
(02) + w 8
R. [r w (gal) ||2
8/
~I1a5%1 1|a (I ||al| 1) (un) x82
(11)
(wz)lla |
2 |||
(1 ||
(1i)
x82
(1-1) (0z))lat
[|W! |aa| [m] - R. [re]112 + | ||||| R.,
[un]
R.
<|la511a (I |1a|| 10 (u x32 (22)lla w _"
|aa ||
1) (vi)
xx2
(1-1) (02))aat)
||W!"" ||2| R. - One-Hot(m1) - R., One-Hoo
+ w (
||2|| Ra One-Hot(q1) - R. - One-Hoo(pp))ll)
<11a50 [| [ (m1)
a-1) (v=))( (
-- (m: (m)) x (0x)((a
x32
||W Re
- One-Hot(q)]lla)
-
<Iaa,0 ||2 (II [ " (un) x (uz)
| - || || (w)) - xx= xx-- (0x)(2=)+++
W ( |||||| R. |21 # r2] + / w 10) | # 42l)
Sx (x|1221 (0 (wn) (-)) (uz))l || + ~||2||| -- (wn)
(bx)] / 2xx 1mm # r2] v2x 1lm # #x1))
=x - (!-1) (1m) -x ---" x 0 (01)
x (0>(11 v2n 11/m # ra] + v2n 2 # qal
13

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Therefore.
IMSG (X3, (w1), (w1): x5, [1-
a-
(w1), MSG (xgs (xg (u2); X32
(1-1) (v2), r2: (22), 92)122
Sk|lxs (11)) (un) (1-1) (12)ll 2x + rz]+
xs2
xB (191xxs [
(1-)) (wi) x52
(1
(u2)ll x²1 | - (U1) x5: [t-1)
(v2)lle + 2 * r2] + 12 92)
S(n + BK )| (1-1) (w1) (wn)
x (u2)ll2 + B و5م (v
(1
|--1)
(1-) (02)l12
X5
(2x:3 + 233 [I # r2] + 22 * 1 # 12
Finally, the Lipschitz constants of the message function of GralL are computed as follows.
mag
3R. B = BKx C 2x,3 V2 D = /23x
History Function
The history function of Grall. is ((k)
Aggregation Function
GralL uses aggregation as the aggregation function, which is formulated follows.
a
AG ((a))))
a:
We justify the Lipschitz continuity of the aggregation function of Grall. follows.
n
(A (a::)=)) - n (B (B= ((b,)))=))
a;
bylla
i=1
Σ
P .A. J( b,)ll2
i.j
P
PAslisll bbll2
where PA. is transportation plan between A, B. Finally, the Lipschitz constants of the aggregation function of GralL are computed as follows.
Also, since adding zero vectors to the sum of vectors does not change the resulting vector, the embedding vector Pagg is zero vector.
Update Function The update function of Grall. is formulated as follows
UPD (ai. a²) = ReLU(W seirai + a2)
where w is learnable weight matrix that satisfies Assumption A.1. We can justify the Lipschitz continuity of the update function of GralL follows.
(UP az) UPD b2)ll2 = RReLU a + +z) - ReLU (1)
b + b2)
sell
(()) ae + a2 w wWb, bi b2ll2
W self [aj - bi) + a2 - b2ll2
w (11)) l2/laa/ b + ||a balla
<x||as b1ll2 |g
balla
Finally, the Lipschitz constants of the update function of GralL are computed as follows.
(!)
K, ((()
upd
upd
14

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Global Readout Function Grall. uses mean aggregation the global-readout function, which is formulated follows.
1
GRD [RD(A=((a))i=))
n1 i=1
We can justify the Lipschitz continuity of the global-readout function of GralL follows.
1
[GRD(A= = ((a.))==1) GRD(B = {(b,)17=))l =
by ll2
Σ P P. j[a - b,y)l2
P -byll
where PAA.5 is transportation plan between A, B and n max 1s,l)) Finally, the Lipschitz constants of the global readout function of GraIL are computed as follows.
Agu max (ss 1s.1)
Also, since CRD(Ha; GRD(Ha,)) U f Σー= a, a;})), the embedding vector Pgnt 1/2 E a.
Readout Function The readout function of GralL is formulated as follows.
pa + a + W gas + W W. R[g] RD(a1, ag a3 q) Wa
where W.. W. Wg. g. Wg are learnable weight matrices that that satisfy Assumption A.I. We can justify the Lipschitz continuity of the readout function of GralL as follows.
RD(a1, a2, 33, 21) RD(b1, b2, by, 92)l
aa + Wa + W yag + Wg R(g] Wib,, - W,b, W W R(ea]
Wga3
Wi (a. bı) + Wi b2) + W (a3 - bą) + W. (R[91] - R(gel)]
(a,a, b1) + W (a. b2) + W (as bş) + W. Wg RR One One-Hot(gı) R One-Hot(q:)))
W [W]]/|||a b1 Wi||/|aa b2ll2 + W e 2||2| la3 byll2 || |||2| 22 One-Hot(qi) One-Hot(g)) )
Sx |a- b + k||a; bb/l2 + =l|aa; - b3l12 + 2 21 (m # 92]
Finally, the Lipschitz constants of the readout function of GralL computed follows.
An
Brd Cia K. Dra V22²
A.2. Instantiation of NBFNet
NBFNet (Zhu et al., 2021) can be instantiated as follows:
1. SUBGRAPH EXTRACTION
NBFNet computes score for given triplet based on the paths from the head entity to the tail entity using the entities' conditional representation with respect the head entity and the query relation. Thus, it does not explicitly extract subgraphs for scoring. However, from the perspective of calculating the score for specific triplet, NBFNet considers only the entities included in the union of L-hop neighbor entities from the head and tail entity. This approach is equivalent to scoring the subgraph constructed by the union of L-hop neighbor entities from the two entities.
A.2.2. INTIIALIZATION
In NBFNet, only the initial embedding vector of the head entity is initialized with the embedding vector of the query relation, while the initial representations of all other entities are initialized as zero vectors.
15

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
A.2.3. SUBGRAPH MESSAGE-PASSING NEURAL NETWORKS
Message Function NBFNet utilizes TransE (Bordes al., 2013), DistMult (Yang et al., 2015), and RotatE (Sun et al., 2019) as the message function. First, the message function with TransE is formulated follows.
MSG (x's (u). x5 (1- ( r.), = x5 (11)) (w) + W R(g] + b/ (u)
where W is a learnable weight matrix that satisfies the Assumption I. and bl") is a learnable weight vector that satisfies the Assumption A.I. We can show the Lipschitz continuity of the message function with TransE as follows.
||MG (9) (x9) 91
1) (u1), (1-1) (w) r,, 9,
r1, (1) MSG
Sq
11-1)
(u2),
x S/
11-1) (w2), r2,
(2, 12)l22
< S| (u1) w R[4 + (1) - X9 (==)(w2) (w2) - 1
R q21
b/22 lle
r2
xs (1-1) (w1) x5 S2
(--) (u2)ll2 [W,, _ [[q R R(q2l1e ll2 + || -W
r2 R(22 + [|b]2 b/2l12
(-1) (l-1((u) (un) x3, (u2)ll /2|l 1
R 2 1 [g] * %1l + | P1
w 1 + | -b
Xs
<| (1-1)( (un) - x5, (u2) (12"
v2x² Aqg # q2l + 2x 1[r * r2] 2x [r1 + r2]
Finally, the Lipschitz constants of the message function with Trans are computed as follows.
(
1, B() msg
= 0, mag 2x² + n. mig V2x²
msg
The message function with DistMult is formulated follows.
(xs MSG (-- (w).
(u). x5 (v),r, g) = diag x5 (x5- (w)) (W [R(gl + bbD)
where ( is learnable weight matrix that satisfies the Assumption 1. and bi is learnable weight vector that satisfies the Assumption A.1. We can justify the Lipschitz continuity of the message function with DistMult as follows.
[MMGG
(x5) (1x)
(1))
(1-1) (0-1((a))) (Bx), (1) - M (x(x (w2),
S2
(11) (v2), r2, g2)ll
= -I|diag
x5 (v:) (W
R[gn] + b.)) - diag x3
(1- 1) (wa) (W mg R[gal + b.9 1l2
= ||diag
x ((:))
R[g]+ b w R|ga] b!2) + diag {5]] x (u.)) diag X52 (x(1"((2)) (uz)) (w R[(a]] + +b(")
= =I|diag(
X51 ((())((u))
- - + (w!)) w ( R[4a] + b.7 b/9 )+
[diag]
x3; (1-1)((n)
diag x (0="
( R[4a] + b12)1l>
< <I|diag
X51
(t-1) (w:))
112
[w ri
[[(]]
R(00]1 || + || w [[galll + [bb/ b(2ll1)) +
||diag[
x51 ((1)))(u)) diag
(ua)
||al[( |8 R[va] + b12)
< <|diaag
[x]] (t-1) (wi))
|| [ www!!lla ||||| R[
R[4=]11
w! w
[ + !bb! b92ll2 +
|diaag
x51
(1-1) (wx))
diag
x
(-1)) (uz) | || (1) R[qu]
b )
$B 11 q2] + 2x 2 [m r2] + 2x1 [n + rel) + |
(1-1) (mx) x (uz)l(2) + +m)
Finally, the Lipschitz constants of the message function with DistMult are computed as follows.
(1) msg = x² + K, B!!) mag = 0, msg
2,3n² + 2,k, D( msg = V2
The message function with RotatE is formulated as follows.
MSG
(xg
(1- 1)
rv),
[ 044 (W, R(g] + b.)
0 0444
Ig] x
(-1) (w)
[0444 Ig] (W, + b.)
0 4
(W, R(g + b,) + 0 0444
14]x5] x (x)
[
04.4 (W, R(g] + b,))
16

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
where is element-wise vector multiplication, ( is learnable weight matrix that satísfies the Assumption A. and b is a learnable weight vector that satisfies the Assumption A. Note that the embedding dimension d should be an even number to use the RotatE. Let us show that message function with RotatE is Lipschitz continuous. Let
X1
S1
(u))
0 4.4
(W,, 1 R[qi]+ )
0g 2.
I
x
(un
Jo
0
2.4
[
(W,, 1 R(())+b.)
Y1
0 $
[ (W,, Riq R br, )+
0
I
x5
(11) 00
I
0 2
(W,, (W,,Rlqi R(r
X2 =
(2
( r2 R + bb,
0g
S2
(u1)
0 0
(W,, r, R(qa)+bra)
Y2
(2
0g.4
( r, 22 +
0 2.4
1
S2
00
0 2
,,,, [,,R[gg]+bbr)
By applying the method for deriving the Lipschitz constant for DistMult and
x||2 S |xx|2
0
[g]
x||2
S
|||||
for a vector x E Rd, we get the following inequalities.
|x] - X2
<2 <
x5
(1-1 (wi))l )11 | (1 ||||| R[g]] R|ga]l2 + || lal |lb - b,22112) (12) +
2/ 2||x8] (1-1) (wi) - (1-1)
x5 (w2) W (1) R[ool + b12
523 (V2x21) A[qi * 22l + 2x 1[m + r2] + 2x1/ri # ral) + 2||x51 21|x|5-1)00 (w1) -
(1-1) (12)) +x)
X55
11y - Y2llz
<2 (-1) (w1)ll || 112 R [[a:] R(g2]12 + (| w R 1l6/ - (12 +
2/ 81
(1-1) (w1) - (1-1)
R[ga] + b12)) Ss (12) ||2| W (1) 1/
<2B (V2x21(g 2(q # v2l + 2 * r2] + 2x Iri # ral) + 2||x|1 21 (11) - (12) + N)
Then,
MMGG
(x
(1-1)
(w1):
51
(-1)
(v1) (11),,1,)) g1) - MSG (0))))))2)))))))))))))))))))))) x52
(1-1) (02), 72, 22)12
0
(1-1) 1) (u1)
0 4
(W R(qn] by.)
[04.4
1
(1 (ui)
004.4 Ig
(W,, R(gi] + br.)
0 2
x
4
(w,, R(qn] by.)
+ 0g.4
[g
(ui)
[
(W,, r, R(gi] br,)
0u
Ig
0g
(w Pu R[ga] + brz)
[0
I
x52
a (wn)
00 0444
(W,, r, R[gi] + brz)
1|2
T
0g
8/
(w2)
044
Ig
+ bry) +
[0 10
Ig x82
a- (m
I
(W., R[gn] + brz)
X1
X2
<||
1|2
y1
y2
<|
Xall2
+
|ly: y2l12
548
112x21 * 02l + 2x 21 r2] + 2x1 # ral) + Allx (t- (u1) - x a-1) (wa)lla(x² + x)
Finally, the Lipschitz constants of the message function with RotatE are computed follows.
A (1) 4k² + 4x. B(() msg mag
0, C(O) msg
8,3x² + 8,3k, (1)) mag
4 2,3x2
17

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
History Function
The history function of NBFNet 0(k) 0.
NBFNet uses sum, mean, and max/min pooling aggregator as the aggregation function, First, the sum aggregator of NBFNet is formulated follows.
Aggregation Function
AGG ((a:))==1)
a
The Lipschitz continuity of the sum aggregator of NBFNet is formally established as follows.
||AGG ((a))==)) AGG ((b,
a
bylla
j=1
PA.B (1. [|
b
Σ
P P.Blis bylle
4.
where PA,S is transportation plan between A, B. Finally, the Lipschitz constant of the sum aggregator of NBFNet is computed as follows.
A =1
Also, since adding zero vectors to the sum of vectors does not change the resulting vector, the embedding vector Pagg is zero vector. The mean aggregator of NBFNet is formulated as follows.
AGG (A (aa))=)))
a;
We can justify the Lipschitz continuity of the mean aggregator of NBFNet as follows.
AAG ( (A= ((ar))=))) AGG ([byA =
a. Σ b
j=1
P PA A,B - b,)ll2
P PA bbilk
where PA.B is a transportation plan between A, B and is the maximum of the degree of the training KG and the inference KG since the blank tree augmentation defined in Definition B.1. Finally, the Lipschitz constant of the mean aggregator of NBFNet is computed as follows.
A agg
1
dmax
Also, since AGG(H(a,))V_) AGG(((a;)E) U E. a;))), the embedding vector Pags ΣR a;
The max pooling aggregator of NBFNet is formulated as follows.
H (A ((.))))))) A where V [[k] max a [A]
We prove the Lipschitz continuity of the max pooling aggregator of NBFNet as follows.
||GG (A4 {(a)))))) AGG (B ((b, 1)
= A v/l22
V A Wsl1
18

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
max a. [k] - max by [K:]]
Without loss of generality, we assume max; a [k] 2 max, [b]. Let in (agmax,(a{[])) Then by the definition of transportation plan, we can ensure the existence jk that satisfies A.Blinn.Jal 0. Also, there always exists non-zero minimum value of PABB- Then,
max a, [k] - max by [k]
Σ
aa [k] max [y]k|
k
asg [k]]
bj. [k]]
1
P P bb [A]]]
PA.Blin,
1
Σ
P P.ss(i,j] [ by(k:]
PA,Blikg
k=1
PAB (1, jaassa bby[k]]
min. PAB((.)))) P PABBii,]
k= 1
P A.B [ Σ
[a, bby
j. PAB PA,Bi
i
Σ
PA.sli b.ll1
mi P P
i.
Vd
PAss - b.ll2
mini...P..niij.. P J.
[.)
where d is the dimension of the vectors. Finally, If we set K as the minimum value among all non-zero values of the optimal transportation plans for (-th layer of all computation trees, the Lipschitz constant of the max pooling function of NBFNet is computed as follows.
A [1) Vd agg K
Also, since (GG(((a))) AGG(H(a))) U ((
the embedding vector 2 1 A.
The min pooling aggregator NBFNet formulated as follows.
OG (A = ((a:)) = A where V V [k] min [k(
We prove the Lipschitz continuity of the min pooling aggregator of NBFNet follows.
AGG (1) (AA = ((a:))-.) ( (B = {[b, 3>l
1 F
< Vg
min
[k] min by [+]]
Without loss of generality, we assume the min, a [k] < min, [k). Let is = argmin, (a.kk), then by the definition the transportation plan, we can ensure that the existence of the ju that satisfies P.A.slie, > Also, there always exists the
19

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion non-zero minimum value of P PA,B. then
min a, [k] min [A]]
ai. [k] min by [k]]
aic [k]] bby [b:]
P A.Blin, PA [k] bj. [A]]
Σ PA by[1]
JA. 1=1
is
P PA. bb]l:]
min PARkijjo P..lli.jl
k=1 2.j
d
Σ
P. P..s(i,
a. Σ
by(+]]
min PANliss)0 P PA
k=1
P P..sli,5llaa. - bbllı Σ
min P. PA.s(rs)/00 P P
8
vd
Σ
P P.slii.)]ll b:ll2
min P.l.ii.PPP.lllle PA.skiJ/0 P PA.
i,j
where d is the dimension of the vectors. Finally, the Lipschitz constant of the min pooling function of NBFNet is computed as follows.
vd
A agg
min P.P. PA.
Also, since AGG( AGG(H(a:)z. u ((WA)) the embedding vector 4ags
v A.
Update Function NBFNet aggregates x ((()) (v) together with the messages from neighboring entities during the aggrega-
tion process. Therefore, update function NBFNet can be represented as linear projection applied to the concatenation of the two input vectors.
UPD ( (a). a2) (w!)
(1)
W a2
where a is an activation function with the Lipschitz constant 1, and (D a learnable weight matrix that satisfies the Assumption A. The Lipschitz constants of the update function of NBFNet are computed as follows.
(1) upd
K. B(t) upd = K
Global Readout Function The global-readout function is not used in NBFNet.
GRD(A = ((a)H))) =0
Therefore, the Lipschitz constant of the global-readout function computed as zero.
grd 0
Readout Function Since NBFNet uses only the final representation of the tail entity t to calculate the final score of the subgraph, the readout function of NBFNet is formulated follows.
(1) 8 (h), X (1), GRD( (1) E VsH)).) (w) (L (D) (1))
(1)
RD
20

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Note that the MLP is Lipschitz continuous under the Assumption A.1 and let the Lipschitz constant of the MLP be Cmlp Then, prove the Lipschitz continuity of the readout function of NBFNet as follows.
RRD
(L) S1
(h1),
(L) Si (41) GRD( (1) (m) E Vs, (s.H),9))
XS2 (12), X2 (t2). GRD( (1) (u2) (u2)) E Vs. 92)
RD
= -|MLP(XS) (T)
51 (t1)) -MLP(x52
82 (tz))l
=Cmpp|> |x51 (t1) X (12)
Finally, the Lipschitz constants of the readout function of NBFNet are computed follows.
A₂ 0, Bru Cmlp: Ci Dra 0
A.3. Instantiation of RED-GNN
RED-GNN (Zhang& & Yao, 2022) can be instantiated as follows:
A.3.1. SUBGRAPH EXTRACTION
RED-GNN extracts a relational digraph for a given triplet. However, the final embedding vector of the tail entity is computed using only the embedding vectors of the h--hop neighbor entities of the head entity and the tail entity. Therefore, the subgraph extractor in RED-GNN can be defined function that extracts the subgraphs constructed by the union of L-hop neighbor entities from the head entity and tail entity.
A.3.2. INITIALIZATION
RED-GND initializes the embedding vectors of all entities in the subgraph as zero-vectors.
A.3.3. SUBGRAPH MESSAGE- PASSSNGG NEURAL NETWORKS
Message Function
The mexsage function of RED-GNN is formulated as follows.
MSG (1-1) (xg
(u), XS
(1-1) (v),r, u.r. (xS 1) (w) + R (r))
() (!-1)
( u.r.q = (w (e ( (u) W R [r] w (4))
X3
where R(() relation embedding matrix that satisfies the Assumption A.I, w w w are learnable weight matrices that satisfy the Assumption A.1, and (!) is a learnable weight vector that satisfy the Assumption A.1.
The Lipschitz continuity of the message function of RED-GNN can be shown as follows.
|MSG ① (1-1)
(u1), (
x (v1) MSG (1-1)
(11)
(x52 (u2), (1-1) X5 (12), 02)122
8,
=Ilan)) (x5i 1) (M1) + R (ri)) (1) (1-1) (u2) + R (r2))l2
Illal) (x9)
11-1) (w1) + [ri] XS²
(1-1) (w2) - R² (rz]) + (all) 022.
(1)
(1-1) (x (x (uz) + RD (r2))ll
Ilall 1(11x)) (1-1) (w1) x (-+)( ||2 + R (n)) | (re])])) + onrri a !
u2irz 11xx
(1-1) (w2) + (r
<(1xs) ((-))) - X (1-1) (1-1) (u2)ll2 + v2x1 |ri # r2l) + (Is + 3) (1) u1.r - (1)
For the attention value aai.n.g the following inequalities hold.
=la(w!") (1) ReLU (t-1) (wn) + ( n² " [m]] + _ n (4))) x5
aaw! ReLU x5 (1 (w2)) w [12) w R (xa)))
< !! (e x (wn)
(-"((a))
! R 1 [m]] w
1 (
21

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
xx w ReLLU ( (22) R [r2] w R (2:)
= =w!" (ReLLRR xx- (R (m)) ( | R [nl)) - ( (w2) + W R. [12] + W Rd [ga)))]
[q:])
- ReeLU(W ""
(wa)
<Il
4 81 (ui) W n [m] [m]
(1-1)
w x (1-1) (uz) 5 n [r>] 5 n [va]l
82
-I -lww"la/|l (x5) (-1
(us)
x5 1- (
R (r2)) + w 30 (R 0 [q1] (
R [ea]ll>
s ll (I |2|1| (-]lx(//))) (1:) x; (- (w2]22
[n]] R [r2]ll
R (0ell))
In [ (111 (ui)
(un) - X3,
11-1) (wa))l + + 1 マ r2] 22 f#
= (t-1 (us) 52 (um)ll2 2 "
(1
12] + 1 (a # 92l
Therefore, get
|MSG [1-1] (1)) (1
(xs,
(u1), (1
xs
MSG (x52 (x)-)) (12) (1-1)
XSz (u2), r2: 22)ll2
5|188, (mn) Xs.
-- (ue)ll + 2 In + + (k+ () ||x|5_-1 (u1) Xsa
(1-1)
+ 2n 1/11 # r2) 22x 16 # 92))
Finally, the Lipschitz constants of the message function of RED-GNI computed as follows.
1 issg = x3 + Brx + 1, B = 0, mig = 22 + 22 + V2n, mag = 2n + v2
History Function Since RED-GNN does not utilize x3 (e())() in its update function, it can be instantiated by the model with both (k)) k 1 and (kk) O.
Aggregation Function RED-GNI uses sum aggregation as the aggregation function. Therefore, the Lipschitz constant of the aggregation function of RED-GNN is computed follows.
A =1
Update Function RED-GNN does not utilize x5 RED-GNN can be formulated as follows.
(0()) (v) the update function. Therefore, the update function of
UPD()) X (o),
ag (w)) = 8(W a( a (v))
where 8 is activation function with the Lipschitz constant 1, w(O is learnable weight matrix that satisfies the Assumption A.1. The Lipschitz continuity of the update function of RED-GNN can be shown as follows.
(0()) (PD
a5 1 X5 (vI),
(vi) (
(0(1) (12), asg (v2) 1|2
x52
| (wI) w (0 5 (v2)ll2
-|IW 122la (m1) - as (x2)ll2 (m))
=x|la (1 (v) - a (12)l2
Therefore, the Lipschitz constants of the update function of RED-GNN are computed follows.
(!) upd
0, B upd K
22

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Global Readout Function
The global-readout function is not used in RED-GNN.
GRD(A (ax))))
Therefore, the Lipschitz constant of the global-readout function is computed
Agrd 0
Readout Function Since RED-GNN uses only the final representation of the tail entity t to calculate the final score of the subgraph, the readout function of NBFNet is formulated as follows.
11) (h). X9 (1) (t), GRD( @ (w)lu VsH)).) = =w xx (1)()) RD X
where is learnable weight vector that satisfies the Assumption A.1. The Lipschitz constants of the readout function of NBFNet are computed as follows.
An 0, Br K. G. 0, Daa 0
B. Blank Tree Augmentation
Similar to Chuang & Jegelka (2022), we introduce blank tree augmentation for the relational computation trees. handle potential variations the number of the subtrees, we define a blank tree To, which consists of single virtual root entity, This virtual root entity has no connections to any other entities within the subgraph and is assigned unique label distinct from the labels of all other entities. The blank tree To is used to augment the multisets of subtrees, ensuring that their sizes are equal. The augmentation process is formalized as follows:
Definition B.1 (Blank Tree Augmentation), Given two multisets subtrees SUB(T (vi)). SUB(T ( S2 (v2)). ), a blank tree augmentation p is defined by
(0) ( SUB(T (V2)) in < 122
(S (wi)). (T (v2)))
SUB(TT) (u))) SUB(T (12)) U 1 11 2 Y22
where O, = Uk- ll (Pblank, To) ni SUB(( ( (v1)),, m2 = [SUB(T (1g)) and Tblank is a virtual relation.
C. Proof for Lipschitz Continuity of Subgraph Message-Passing Neural Networks We provide proof for Theorem 4.5.
Theorem 4.5 (Lipschitz Constant of SMPNNs), Given an SMPNN fw with layers, Gu (Vu, U Twe) and
G (Vint R. Fist U Tit)), if the message, aggregation, update, global-readout, and readout functions Jwr are Lipschitz continuous, then fw is Lipschitz continuous with the Lipschitz constant n, and the following holds:
L+1
7
0(k) = k -
(L+1) 1)
L+1 m00)
((k) = 0
" = m upd + dmax upd
B!l) A B!l)
mig: ( A (1)
Ang:
|R|2 (1)) (1) ((I) |R|2 ((1) (1) D(l) mag: 1), upd mag:
upd
| Dra
n (L+1) max(Am Bag Ara 2 + max Virl (iar))
where L A B () Cmgg D are the Lipschitz constants of the message function, A is the Lipschitz constant of upd: und are the Lipschitz constants of the update function, Aged is the Lipschitz constant of the global-readout function, A,d, Bid. Cid, Dra are the Lipschitz constants of the readout function, and dmax is the maximum degree of G and Gint-
the aggregation function, A (1) ((I)
23

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
|Vspl- Let Xs, = [(xs, (v1))en E Vs, and Xs, Hxs Sy (12)lu E Vs, B U Va, ([ where Pgr E I is an embedding vector that makes GRD(ss,) same (1xx))(()))) (o2)lu E Vs. I)). We assume that such an embedding vector exists, and justify this for each vari- ation of global-readout function in the Appendix A. Also, we set Xx,, as the optimal transportation plan of Using the Lipschitz continuity of each func- tion in an SMPNN defined in Definition A.2, we deduce the following inequalities:
Proof. Without loss of generality, we assume [Vs 2
as GRD (HX,,
OTRID (e (Troron T [o1) E Vs (T S2
( (oo))]uz E vVs,B))
(Sw) - (S2) = RD XS. (h1)
(L)
8, (t1), GRD (fx (u1)le1 E Vs. H)) 91)
(L)
(1) (122),
(1) (12), GRD( (1) (u2)lu E Vsa 92)
RD (xS2
52
S Ana Anll| (1) (1n) - S2
(1) (h2) la + Bal | (1) (1) -
-x5, (1) (12)
Gul|GRD(H (1)
91 (w:)|01 E V) -
(12) GRD((1x (4)
E Vs. + Di + qzl
SAallsss) (2) (h1) (11)) - XS, 11)
(h2) 12 + Ball (4) - -x5, x1))) + Pra |n + 2]
Ard Σ ,xs
Us, 11 11 (1) (v:)
(vx) - -xs, {
Similar to blank tree augmentation, pairs of Fotank and virtual entities are added to the smaller set among Nss (u:) and Ns. (1z), resulting in the augmented multisets Ns, (ma) and Ns, (ry)- These augmented multisets are equivalent to the multiset whose elements are pairs of relations and root entities of each subtree in ((SUB(T)) (v:)), SUB(T!) S. (u,))). Note a transportation plan between Ns, (v:) and Vs,(w)) We set the computed message of the virtual root entity of To and virtual relation 'blakk an embedding vector Pagg E IRd that makes the aggregated message of the neighbor multiset (v) same as the aggregated message of the augmented multiset (v).). We assume that such an embedding vector exists, and justify this for each variation of aggregation function in the Appendix A.
that (())
Ns, (1)).
||x|] (1) (v:)
X5 (1)))l2
(1
([UP(() (
(0(1) (u;), AGG (HMSG (xS) (up) XS, (-")) (v:), re, ()) ux) e Nss Nss (o:)))
(PD (
(0(1) (1;), AGG AGG (x!
-- (uy) X 111)) (1))) E (w,())))))) lle
A (0()) (u:) xs. (1,))l2 W |AGG (HMSG
(01))
(-1)) (v:) rr, ux) E (v))))
AGG ( (H[MSG (M (x (1"1) (1
(111) (w,) ry, re E (s, B1)22
A (O()) (1:) - x5. (v,) 1 |AG (HMSG (-)) (ux) x5. (w). ())(0. E Ns,
r.,
(v))))
( (x (--))) (1,))
(1))) ry, ug) E Ns, (1,) M))l2
82
A (((1) (0(1)) (1:) - x5 (0,)ll2t
(0(1)
BBl) (1)
Σ Ep! p())
No, (s,) (v,) "'' [J]]IMSS ((-))
(L-1) - (I (uy) xs2
(1-1) (1-1)
upd Age
age
x5:
<Amillx
S1
(0(1)
(2))
x52
(0(1))
(0;))l2 A
Aug
ugg
P!
Na, (v.) Nop (11) (1y) 1'5 [
1x (ww)(ww)= - x5 (1-))
(1-1)
+
Bll) msggl |x|]
(L11) (ox)) - X52
(1-1) (v:)l12 + clly
1 [rv # ry] + msg 11 [m # 9el)
Let us first consider the case where the history function is defined as 0(k) = k 1. If we define the Lipschitz continuity of each layer of an SMPNN as
(1) ()) max(A upd + daaxx (10)) A (1) B(I) B(I) (1) A1)
upd agg mag: upd agg msg? |R,
2 ((() 100 c()) upd
(1) (()
1),
(2)
agg mag: upd age msg:
24

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
pa-a
p Mf
1mb
1=L-1
My Va3- uall
1=L-2
Shenl
Wi Wesry
dew 15..
1=1
Wiffoud - (6--))
A
Kil -2f ((p-))
Figure 6. Visualization of the iterative process. Each box represents the L2 norm of the difference between two entity pairs.
|R| Daa
(1+1) max(Add Bid, Ard + max maax(Vi (Vrl,, Mirl)
and (0) f S/S L, the following inequalities hold.
[|x]]] (v.) - (v,)ll
EA xs ((-1)
x (f- (og)lla
Blil (1) Σ p())
x No, (s, (ry) [t' (A 1x (av) 4- " (u,)))2 100 Bx0 (us) - x52 x0-" (v;))l any # # 92l)
2.3"
(10) + dmar ( piii (e)) (u,illt
Σ p(U)
Ns. (w)) (1)) (t's 1'l (mll w 1 1 (mpp) x52 1) ( R2 10 cin
(100 1 [n of ryd 1all Al0 D0 (or * qzl)
")"") (1x2)-1) (1x) (c,)lla+
pd))
Nsy (1)) Ne (19) K.'5'1 (ixd)) (((r)) 2 "uyDlla ı (Alr ryl 2/01 # s21)
2q 11 (1 (1x0)_1 (v.) x (1,))l++
Σ p
No. (1)) (i'''1 |1 1
x5 (a,c)
(xlry # ry 1gg # qul)
pd) 1og R.
(1x9 (1w)
x (wy)
maaa (alr o ryl + I[m * 4zl)
Pi Ng, (5,,
The above process shows how a single recursion is unrolled and applied to the next layer. The overall iteration process for layers is presented in Figure 6. Each box in the figure represents the L2 norm of the difference between embedding vectors of specific entity pair particular layer. The vertical axis corresponds layers, and the horizontal axis corresponds to some entity pairs. Hence, boxes within the same column represent the same entity pair across different layers, while
25

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
boxes in the same row represent the same layer across different entity pairs. From the above inequalities. we can infer that calculating the upper bound of each box requires evaluating the expressions corresponding to the box directly below and the one diagonally below to the right. In Figure 6, a shift to the right column indicates the neighbor sets of the entity pairs in the current column. Thus, the arrows pointing diagonally down to the right require a transportation plan, which must remain consistent for the same entity pair. The process reaches the leaf boxes corresponding to the 0-th layer by recursively applying the iterations described above. The final upper bound for the box at the L-th layer is expressed using the values derived from these leaf boxes. The coefficient for each box is equal to the number of shortest paths from the top box to the corresponding leaf box. Therefore, the coefficients of the leaf boxes correspond to the I--th row of Pascal's triangle. Additionally, the coefficient of the penalties for the relations and queries can be calculated by the summation of Pascal's triangle up to the previous layer in the same column. Therefore, get the following inequalities.
[|x55 (257)((v)) (os)-
X82 (2)))la + |2|2 (1 (rioe of rinel + 1/0 of val)
(00) 1I ())))
|x (m:)
(0) (us)]laa + [र (1 (rive o rwall + 1/x o ga))+
2g
Σ p(l)
II m(0)) |x x
Σ
L 1
II (h) (abr +rp ll9. * qal) +
L
Ns.
[
Σ pll 1)
II (()) (ug
II n0) (1b of Afol 100 * oal) + Aur
|
""3""
((1-1),((-11 Ns, (1.aa-))) Riss ())))))) (((0))) (4= 4 ,)
Σ p(2)
II ( |x (x....)))))))) - x39 ( (1,,r.-1)))a 311
1i-1
L- 11-11 2 11 ) (Ilrae-)) # +1 1l9: * qal) +
L-
Σ p(1)
1:00 slo) 4 [1 (() 1 (w,,))) ,
Ns, (s.ce- 11) Noz 1))
1000 ((0)
(-)))
-- 1 ) (1i2ce) o rrasl l/2 o oal) )..)
II (k)
||x 100 (v.) x (c,)0l2
[2 (1/rex # rmne] + 1ly: # 9=1)+
(9)
(())
Ns. (s,, (1g) (''5''
[ ( (up) x |R|²
10)) (yl 1le * qal) +
(H)
Σ
p(l-t)
Ns, (1,)) It" sn]
[I (/) -
- X (u.r)))
Σ
+ (Aleo # #zl)) +
|
Ne (st 21) Tay (3/2 2)) | )()-)) ((i Ix n)) - - (1ya--))) n)lla
Σ p(u)
(L- 1)
1 (Itr # r ry(c_1))] 1691 * ml) +
[
(( (1) (2)
Nay (( Noy (1) (:1 |ام (
( -xg(
(31re0) # rewll + llus # val)
[
II ()) k-0
[ (v:) (r))lla |R|² u mp())
(I(rma * rmn] + [[1) o gol)
p(L) Ns. (22) (eg) (''5'l (IxS) (wy)) (yyDill
(1bry fyy # azl) +
Σ
p(2- 1)
Ns, ( No (1 [''"") 5n) (m))) -g + |
(Mir x rgo]+ Inm * mz) +
(9) C'
26

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Σ
pl) Nsi (1ae-2)) Noa Noa (1(22 ( 21 (u x8 (2)(21)))lla
(((--)
(AIrRe i) eye 12 1/91 # eal) +
RF
p(l Noy (1 Ne2 (1)(e-1)) (d joby (1x9) (u,(es) x (uya))l
(4)) (44)
(I1r,ce) # reasl++ 1/21 # (i))
1.
II
(k)
[xx_] (v:) x (0ا)مl
اरح (1lrm o real + 1o0 o nal)+
(oy) [6'5' -
(2lry #ryl+ azl)
Na. (g
1)
N3 (sg
1t (')
(1x (xxp)()r))
|R|
(1le alo oal)
p
Nsy (1,c2-2)) ((( (1x (u x52 12))1
(1)(t11)
(Atr rye 171 + ll9 # oal) +
RF
p())
No, (" (vpa- (600) ,00 (600
(1xx)) (x (aya)ll
(b) (1b)
(11 # +rae)++ + l/s1 # sel) eal))
R
II (k)
(xx0] (v:) x2 (v, ||l सरा (1 * read 1o1 * aal)+
L(L) Nay (2 (1)) (6'55 [ (mp)
x (uy)lla सर (Nl of ryd + 1o0 of oa))+
9
oigh N2y (x (s Nogii 16" 5"' (up() -x (0 ا (Aln # + 42))+
p(l-1)
(
p(i) Nsy ((,(,)))))) hi0 sayy (1x (4gos) x52 (a,a))l
[Rrz (11,,0 * Aryual 1/9. # val))
(19)
If we set each transportation plan as the optimal transportation plan of the RTD((Frant: (1:)), weight function w(l) = we can bound the above equation as follows.
(v:)), (Front (1;)) with the
I.
(L) |xS] (v:) - xSa (1;))la R (1|rrooe f Troon] + 1/q + qa))
(L)
II
RTD((rmot (o.)((()))
(v:)), (Toot T (v;)))
((l((,;))
(=0
Finally if we set p!()
(ns) (v)) as the optimal transportation plan of the OTRIDS11 S2). we can get following equations.
-
AAall x35 (h1) - X5
(2) (12) + Ballx (1) (L)(t)) (ti) xx, (12)la + Da + 42]+
Agd
Σ
Pxx, N', [i, .| X (wx) x (1,))l2
is
(1(t+
(1x()/(1a)) - x12 (h2))2 + (x -x6 (tz)ll2 +
2 + max ( [ss 1. Vs..)
[ * q2l
||
27

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Complction
Σ
Pass Xs, [i.5]| (12 (us) - 82 (us))la)
(1)
+
<n <n(()t (1+1) (Ix5)) (h1)
-x3² -x(2 (12)lla+ |R12 (Tra o Troal + 1 F 92l)+
|x31
(1) ((1) - 20 (12)112+
(41)
-x52
RRI2 (1 Froor + rrood + 1ggi + 92l)+
1
Σ Pxs Nsg [i,i]
| (xx) (v.) xx52 (1) (2,)ll2+ + R2 (1 [rooe # Frood + 1(g1 # 92l))
L+1
n1 (k)
(TTD( 2 (h1)), ( (h2))) RTD( T/h (ti)), (Froot: T2 (12))) + OTRID (S 82)
[L+1
II 1=1
17 (R)
(1)
Next, we consider the case where the history function is defined as 0(k) = 0. Using the Lipschitz continuity of each function in an SMPNN defined in Definition A.2, we deduce the following inequalities:
[|x]]] (v.) x52 (25)]l2
EA 10) (wx) x (0))lla+
B a ())
Σ
p(
Nsy (o, (.s') (A (A (up) - x1-11 x (a,r)l
B [x5]
(2 (es) - -x2 (e,)lla + cfiib * dry + Dmg # aul)
3.5'
S4 x
(0)
(v.)
(c, 111 dmar w Ame Bil x (v:) -x,, ((-)) (0y)ll+
1i8' Ns. (wr) ( (''3' B 1 ((pp) xxh ((,r)) B A Will the of myl m A Dil (m of oal)
Σ pl0
2a (1x (v:)) x (v)))la + | (v:) x (w))llat
Ne toy Pi5'
E
1' 1ll (1x5) (u,)
x 0- (wy Ila + स (Ilr # ryl + 1le * 92l)
Using the same approach as for the case where ((k) = k 1, we can derive the following equation. The only difference in calculating the coefficients for the values corresponding to the leaf boxes. In this case, the coefficient of each leaf box is equal to the sum of paths from all boxes in that column to the leaf box.
(es) (ex) x (e,))la +
(Imm o rmael + 1lg # 9zl)
G.
Σ -
II (()
(xx) - x (os))la+ + :. (rmm * rmael + 1/9 3 22l)+
Σ p(L) Nsy (w)
10)
Σ
1x )
x52 (ng))lla
Sog (ry))
(Air ryy 1111 * æz))
|
Σ 1(
(k) Σ
(1-0
11 m/)))
( (wyr) - x52 (1))))))
Nzy (opr) (
5"
h-r
11 )0) (1i x rydl + I/ * oal)
Σ p!
Ns. (1,c 2.) 2)) ((0-1),
((1=1))
II 7
II 70) |x (u
-x (u (u,(c_ 11)1e
(11-1) )) 1-1)
(يا レ ? 11 )3))) (I(r # ( - 1/1 * mal) +
28

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Complction
Σ p(u NsI (()))())
(1:00-1)) Neg Kes (3co--) 11:00 (00)
II (())) (x(g) - x82 (u )lla
Σ (1:
II (/)) (217,te) # frjw))++ 1l01 # 82l) ).
L
kmr
II 11
L
(w)) + - (t
| (es) - X (us))l2+ + ार
11
(1(mou o roadl + 1/9: # 9al)+
km 7744]
Σ plly
(n)) (11)) |'-s ((+))(T))
7( 11x [xgg) - x3 (2
Ns
+ |
(Elry # ryyl + I(q # 9=1) +
R3g Nsg (1ne) ( ((+) 1-2 -
Σ p(--1
(u,,)) (ngr)ll
y00)
'"'g""
A=o
+ Pर
(1 # ryrl + 1/s # 9=l) +
Σ
plo)
Nsy (1,c0-2)) Rosa Ross (3))) 1 (()) 4 Σ
kmo 17(0)) 1 (ng 1) -x 1))l
(11-1)
II 1
) (1b,a-1)) # $ + (/ * 02l) +
k=
p())
/oaz Xo (3)(0-))) 1r (لي) (() || 50 (1:P(())))))))) (x,())))
Ne, (z(00-1) )
s(1) ((1)
{ (
II
1-
1
(11rae)) o grasl+ + 101 * mal)
L
())
(1) + Σ (-)))
T Mre ranll 1l9: # (21)+
0
Σ plu)
(''''1 (()+((()))
|x (mr) Cagrill + |,2 Σ (1-17) (A1re * rgyl + # sal) +
Ns, oy
2
((0) Σ (1=)) -
(1T)) (A1r # rg 1lm #
N2, (0 P (M
(rile 2,)3822(3.0 )i) "( ((6-)) Σ (E:)) | ( (u,,,,,,,
((--1) No. Pe
p(o)
Σ (1112) ) (1173--1) # (((4-1)] + 1i * +zl) +
+ |RF
p(1)
NsI (2((- Noo ()) 1600 ( (0) [1 - x (x,
(1))
Σイ {(=1))) (I1oz0)) # ry0rl + Jae # mnl)
+ RP
II () k-1
L
((C) + (1) | (m)) (1))ll + u (2 roodl +1 rig # gall+
Σ p())
( ('''' ((() + (5)) |x-] -
-x (n + | (4) (Mly of ryel + + * aal) +
0. Ns, (i (nys)
Σ p&-l
No, Be (" [n) (()) + (3) (up)) - x (ugr))) + m h (1[rpr A ryo) + f/1 * mz)) +
111--1 Ns, ((.()_2)).33 Moss (1)(-,))) (( ((6-1)) (1)) 11 (M - -x0 (u (aa,ill
Σ p(o)
+ IRp (x- (1rr # أامسعرر + 1/m 7 0al) +
29

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Complction
E p() Ns, (va--) Now (3(c-1)) (60)) (() 1xx 10 (1())))))))) - (u,(,,,,)))
T (1) (1lr,e)) of Mr,ee)) + I/m i oel) ))
(6)) (9) [ ( (INE((on) (us)ll+ + [R] (0) (1)
(0)
(Mooe of rmwe] + 1(m * onl) +
( Σ
plu)
Noy (1) (oon) (1x9((())) (1)) x (1g, [R
(
(1ly * ryyl + 1/0 # aal)
(1+(1)) 6,y"
(1) +
(9+ Σ
Ns, Ng (y,)) "'''" ,1' (u.)) (2
(Ilr #1y01 + 1/21 # qul) +
(9+ (9) 3
R
(1)+())
Σ p(
Roy (1,(0-))) R Rea (s (1))))))) ( ((c-ا)) (1x3) (u,(1-)))) x52 (u (1)(1=
('D (2) aa
Di
(1rque-) # r-(--1)) + 1001 + pal) +
|R (.51) + (15
(9) Σ p(l)
Ns, (11(z-1)) Ksy (3c (1 ,(00y] (1xg) (m -x (r la
(2-1) + (5)
(00,)0))
R2 (Nraa) # +xusl+ + 1/01 # #
((0) + (2) (II (IxS) x3y (v,)]l2 + | (2 (Tmm # rmndl + 1/91 # 9=l)+
(9) Σ p(t)
(1) Nsy (o))) (1x5) (mw) ( [र (2lr # ryy1+ 1[91 # gal)+
()+ Σ
p(
Ns, (1p) (o (e,,) 16''"" 1''l (1x (a.w) x (u,w)ll + ररय (1|r * rydll 1/9 92l)+
(9) (2) 3"
(1-1 Rsz (=)a-)) Rep (2)(2_)) (((-))) (1x2)) (u.(t.))) x (u (x-)l=)))lla
Σ 2(.)
(1rr 1) 2ra ma + !n , 92))+
ا(ه) Ns, () Ksz (((--1))
( (ux3))) (0) (u la
H ((0))t
(1lra # d + l0 # ml)
If we set each transportation plan as the optimal transportation plan of the (TD(nr T (v:)), weight function in Equation 3,
(Troes (3,((1;))) with the
(1rtt)) (e))lee (n1) (1-7+
12 2
w(l)=
(3)
1=1
can get the bound below
L (k)
() (v,)ll2 + p (1|mmot # rmall + 1gg + 4z)) S (L 11)
RTD(( T!D (v:)), (Tmat: (1,)))
Finally if we set (!))
Ns. (v.) (v,) as the optimal transportation plan of the OTRD (S1, S2), we can get following equations.
(St) - (w((22)
SAull(ss) (1.) (1) xxS (f2))l2 + Ballxx!0 (1)(4))) x5, (1)
(1)
(t2)ll2 + Daal (gn # g2]+
30

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Agd
Σ
Pxs Ns, [1,] x5 (u:) xs, (ug)ll2
(1)
(1x(),(()) (h1) - X33 (4) (12)l12 + ||xs, (L) (fz) (L)
(12)ll2 +
2 + max (ax [ssl))
[ # q2)
[R]2
+ Σ
Px PAs No, [ [1,51lls]] (1x)) - X5 (1)))l2
(1)
(n())
(1) - X32 (h2)ll2 + R (1 Fraee # rroul + L(qn # 92l)+
1
|x5 (t1) (tz) x5, (t2))2 (12) + |R|2 (1 /nooot F rroal + 141 # 92])+
1
Σ No, No₁ [i,s] 1.
(xx)
(v:) -x57
x552 +1))) (11))l2+ [2]2 [1 F rrood + 1l91 # q2l)
L++ II 1=1
1(L+1)
17
(k)
(RTD(( T54 (ft)):: (Troot (h2)) + RTTD( T(l: (ell(((((t))))))) (t1)); (Froors (t2 + OSI S2)
L+11
1(L+1)
II 1=1
RTMD(S
D. Proof for Generalization Bound
We prove Theorem 5.3 and Theorem 5.4.
D.1. Proof for Theorem 5.3
The risks associated with any distribution Q over the parameters of stochastic SMPNN can be defined as follows.
Ea(Q,)) E, E (a
La(Q,7) = R
Lemma D.I is a modified version the PAC-Bayesian generalization bound proposed in (Ma et al., 2021) for subgraph reasoning models.
Lemma D.1 (Generalization Bound for Stochastic Subgraph Reasoning Models), Given Gu and a subgraph reasoning model with a subgraph extractor g and an SMPNN fw. for any prior distribution P on the parameter space of fw. posterior distribution Q on the parameter space of fw. and X > O, the following holds with probability at least 5:
Lo (2. (o, + Ro)
1 (KL(II))+M) + In
X2
+D(P,A,7)
4
where D(P,), = In (Bw~p /exp (A (CG (fwlfw 7)))]
(fw,
From Lemma D.I, we derive the PAC-Bayesian generalization bound for deterministic subgraph reasoning models in Theorem 5.3.
Theorem 5.3 (PAC-Bayesian Generalization Bound of Deterministic Subgraph Reasoning Models), Given Gy=
(V..R, )T.). Gint = (Vut, R, Fir U Tinr,, and a subgraph reasoning model with subgraph extractor and an SMPNN fwo for any prior distribution P and posterior distribution Q on the parameter space of fw constructed by adding random noise to w such that P(max(maxxes If (g e)) - (g(GGGr e))l, maxeeTa Ifw ( (gGGa e)) (g(g e))l) < 2)) > }.
31

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
and 7 > O, 0, the following holds with probability at least 6:
(fw 1 La, (Sw:.))
A (2K( In 4 +
X2 - DD DD 2))
Tul
where (P, is the expected risk discrepancy between G and Gint and (L is a KL divergence of Q from P.
Proof. The posterior distribution Q is the probability distribution of w in the parameter space H. We define the following set in the parameter space H.
C = (w E H| max(max (w (g(Gu, e)) - (g(g max (fw(g(GGnn e)) fw (g(Gi e)}1) < 2 c H NETr
oE Tmn
Then, P (w E EC) >
Using Q, we create the following distributions.
2'
1
((w)
WEC
WEC
p
6
w WE HEMe 1- )@
HIC
For any r,, E Tan and w 2
Wnn w (giGin (b, r. ())) - S Cannswa((CC (g(Gin (h, 1)))
= Mhn (fw (g( Giit, (hi r. t))) - fw (g(G (h, r, t))))
= f Gg(Gi (h, r, r,t))) - fw (g (h, r, t))) -
Then,
f (g (h, r, t))) S + fw (g (h, r, t))) <
which indicates that Therefore, La (aw, 0) S Caw 7) for any w ~ 2 which means that that
[g (h, < 00] (i (h, t))) 21 4
Landsww 0) S Sow 2)
Also, for any (h, f) E Ti and ~ à
Whn (g(Gin (h, ())) ynn (o (h, I)))
Whn (f (g( (ur, (h, r, ())) - fw (n(Grr (h,r,)))
= ffw (ru (h, r,f))) - fw (g (h, f)))) 2
Then,
(g (h,r,
(1,7))) < + fw(g(Gur (h,,,,t Sy
which indicates that
[[ (h,r,, ())) 2 [g (h,r, 7l
Therefore, Zo, (Sw, 3) Ec, (Jwi 7) for any w 2 meaning that
Can
2 2) < Cai(fw.))
32

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Then, with probability at least - 6,
22
LGu (fw: 0)
<B BBw-@Canfee (fai 2 2)+ à (K(((IPP + In x
1
X²
+ +D (P.A..2)) 2))
8
4/Tul
<w. + KT(([PP) +
1
X2
+ +D (P.2, 2))
8+ T
by applying Lemma D.I. Also, the following holds:
Ql dw /
(L(P)))- =
Qn dw
wwc
WEHiC
P
Q In pP
Q
Q
dw (1 pp)
In
dw
WEC P
WEHIC
p
(1 (1-p)P
p)p
+
Qln
Qln (1 -1-11)ddw
WEC
WEHIC
-pKL(O|P) + (1 (I))) +plnp + (1 (1-p)) In(1 - p)
Since <<<<<. -12 2 <phpp (1 p) 1 p) < 0 holds. Considering that KI. divergence non-negative,
KL(ỘIP) = - (1- (1-))) p-p
-p)
= (KL(Q)P) + 2 s P2
Consequently,
(f 7) + KL( +
X
+ D (,, 2))
T
SCanlfw: 2KL(2IP))+n
4
X²
D (D.A, 2)
T7
D.2. Proof for Theorem 5.4
The degree of difference between the subgraphs extracted from the training KG and the inference KG be represented through the optimal transport between the multisets of subgraphs extracted from the sets of triplets Tir and Tin-- Since the number of the triplets differs, an empty subgraph Sblank, containing only virtual head and tail entities, is defined to facilitate the computation of optimal transport. These virtual head and tail entities are identical to the virtual entities forming the blank tree and always have initial labels distinct from all other entities. The multisets of subgraphs, extended with the empty subgraph set, are defined as follows:
Definition D.2 (Empty Subgraph Augmentation). The empty subgraph augmentation & for two triplet sets Ta and Tiat is defined as follows:
Ho(GGtt ex)le E Tnil)) U ((Swaank B. (G(G ey)le, E TT] Hag(Gin, ei)le E Taal), f[g(Gu, e,)le, E Tell U ([Sotank)) }} n1 2 n2
n2
(Tut, Tw.)
where |Tar 71, [Ta] 122-
In this case, the score calculated by the SMPNNs fw for an empty subgraph is always 0.
Now, we prove Theorem 5.4.
33

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
Theorem 5.4 (Bound of the D(P, X,))). Given Gu (Vr, R, Fu UT)), G = (Vit. R, Fit U Tmt), and SMPNN fw
with stability Cr.for uny prior distribution and posterior distribution on the parameter space of swo and X > 0, the following holds:
Tel Tint
OTRMDD( (P Tu)) 7C, max (Tar) [Tnl)
D(P, (PP.A)) S S
max(0,
1)
where ub is the empty subgraph augmentation defined in Definition D.2.
Proof. Let P (T be transportation plan between the augmented multisets of subgraphs (Tin. Tu). Then, the following equations hold.
(SmrSw 2) Lg. ()
Lg.
= Ey Con 2] -
-lEy Coa (fw: 2) (fw,
2
-Ey 1
Σ
Alyif ex)) - 2-1 -
Σ 1lunfw e() mi]
|Taal
[Trl
T.ETT
([ViSw(S) I El
(yjis((Sj) [n]]
-Eyy
P PT (EW.S))
Σ
Tul
First, consider the case that Tint hold.
Tul. For any pair of subgraphs (2) (Tatt Tx), the following inequalities
[yriw(S.) S 71
flyff(S)) S <]
1/|Tal
1
(Sw fw(() +
[Tnt
Trl
7/2
[iin
[Tu
Next, we consider the case that Tint hold.
Till
For any pair of subgraphs (2), (Tin,, Tr), the following inequalities
[w (S.)
21
f >
1/|Tm/
(ww - Sw (S,))
[Tatl
[Tul
7/2
By combining the above two inequalities and applying the Lipschitz continuity of an SMPNNin Definition 4.4.
Cemllww 2) (fwsr))
S 21
1 [wnjf(( (w S 71
)
-Ey
Σ
P Pec 1i,
[int
Tul
(E..S)) (Tu.
<EEy
Σ
P PoC.n.Tole.d
2
[fw(S)) [w;)) max(0,
1
1
y maax(1Ttt
[T/l
|iarl
Trrl
(V
2
1
<Ey
Σ
P PoCTn.T>libd
RTMD(S; S5) max(0,
JC max( (Trl
|Tnn
|Tar
(E
Ey max(O,
Tuul
1)
2 70, max( (T))
Σ
P P.
[Tnn]]
holds. If we set P (TT. as the optimal transportation plan of the OTRIND Tu)), derive the following inequalities.
Lem (fws 2) (a.(fw:)) 2
34

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
[Tl
2
<By
max(0, (0,
1) +
Σ
PoCTu Puctastlli.
|Tarl
yC' max Tinl (aar)
[Tr)
(E (Tae,
[Tll
2
max(0,
1)
OT ( Tw))
|Tint]
yCy max
Tinil
(Tr))
Trrl
2
= -0,
1) +
(VTMMD(((TTTt) Tw))
|inil
yCy max ( Tint
(Trl)
Finally, we get
Ca. (fws 2/ (f:
OPP,,,
=In Ew~p
exp
<in
Ewwp
E
exp
(x
max
[aal
1) +
2
OT RTMD (1RTMD(Y(TTa Tir))
[inn
yC, max (1it (Trl
TTr Tat
=In
exp
max
1)
OT OTRIMD (v) Tu))
yO, max Tarl (uul)
|Tr
2
max(00
1) +
OT ( Tw:))
y0, max
|mtl) (ul)
E. Experimental Details
We conduct experiments on the inductive split of three real-world KGs, WN18RR, FB15K-237, and NELL-995 from (Teru et al., 2020). Specifically, we use the v3 of WN18RR (WNv3), v1 of FB15K-237 (FBv1), and of NELL--995 (NLx2). For WNv3 and NLv2, we randomly sample 20% of the prediction triplets from both the training KG and the inference KG due to the large size of the dataset. Additionally, we split the triplet set of the training KG into two parts in a 3:1 ratio, using them as Fr and Tu. respectively. For inference KG, we use the triplets in train.txt as Firt and the triplets in test.txt as Tin-- Since all triplets in the original datasets are positive, we generate negative triplets by randomly perturbing either the head or tail entity of each positive triplet in T, following (Socher et al., 2013). The resulting positive and negative triplets are treated as the final prediction triplct sets of the training and inference KGs, Tu and Tit. respectively.
Following GralL (Teru et al., 2020), we extract 2-hop enclosing subgraphs for all positive and negative triplets. To limit the size of extracted subgraphs, we limit the maximum number of neighbors for each hop to 50. The initial embedding vectors generated by the double radius vertex labeling of GralL.
When we compute the optimal transport distance with respect to the relational tree distance in Definition 4.2, we use the Sinkhorn algorithm (Cuturi, 2013), fast approximation of optimal transport distance, due to the limit of computing time. We use GeomLoss (Feydy et al., 2019) for implementing the Sinkhorn algorithm on GPU. During the computation of the optimal transport distance with respect to the RTMD in Definition 4.3, we compute the exact solution using the POT library (Flamary al., 2021).
We use Python 3.8 and Pytorch 1.13.0 with cudatoolkit 11.7 to implement SMPNNs. In experiments, we tune the learning rate from (5e-4, le-3, 5e-3, 1e-2) by measuring the empirical risk on the training graph every epoch. The combination of the learning rate and the epoch with the lowest empirical risk is chosen. We run all models for 1000 epochs. To compute the generalization error, we use a margin of O.5, i.e., = 0.5.
In the experiment Section 1,1, we use 10% of all subgraphs from both training and inference KGs to train the support vector machine classifier and evaluate classification accuracies on the remaining subgraphs. We evaluate 5 times with different seeds: 1,2,3,4.5.
In the experiment analyzing the relationship between the scores computed by SMPNNs and RTMD in Section 6.2, we use the architecture of Grall., as described in Section A. For WNv3, we use d = 32. For FBvl and NL.2, we use d = 64. Also, for NLv2, we fix the norm of the weight matrices to 20 (Lee et al., 2024).
In the experiment analyzing the relationship between the SMPNN's stability and generalization error in Section 6.3, we use variations of three well-known SMPNNs: Grall,, RED-GNN, and NBFNet. First, we fix the message, update, and readout
35

---

Stability and Generalization Capability of Subgraph Reasoning Models for Inductive Knowledge Graph Completion
functions those of GralL while varying the aggregation and global-readout functions, selecting either a sum mean aggregator. Additionally, to consider models that do not use the global-readout function, design variation where the output of the global-readout function is set to zero vector. Second, adopt the message and update functions from RED-GNN while applying the same variations as above. Last, we explore multiple instantiations of NBFNet by varying the message and aggregation functions. Specifically, we implement message functions based on TransE, DistMult, and RotatE, and design models using a sum aggregation, a max pooling, or a min pooling as aggregation function. We also use 0(() = as the history function with sum aggregation. Note that we retain NBFNet's update, readout, and global-readout functions.
For all models, we use message, aggregation, update, -lobal-reaoout, readout, and history functions, and the number of layers. We then compare the stability and generalization error of these models. For WNv3 and FBvl, we use d 32. For NLv2, we use d = 64. Also, for FBv1 and NLv2, we fix the norm of the weight matrices to 20. We filter out the models that are not well-trained, by setting threshold for their empirical risk on the training graph. The threshold is 0,25 for WNv3, 0.2 for FBv1, and 0.05 for NLv2.
and L 3. resulting in 48 instantiations of SMPNNs. These variations include different
36


Reviews:
[{"review_id": "0CVyWIl8km", "reviewer": "Reviewer_ePj1", "summary": "This paper attempts to theoretically analyze the stability and generalization capability of subgraph reasoning models in inductive knowledge graph completion (KGC). It introduces the Relational Tree Mover’s Distance (RTMD) as a metric to quantify input subgraph variations and proposes that model stability directly influences generalization performance. A PAC-Bayesian generalization bound is derived to support this argument. Empirical experiments are conducted on real-world datasets to validate the theoretical findings, emphasizing the role of model stability in improving generalization.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Claim/Evidence #1, Theoretical Claims #1, and Other Strength/Weakness #1**\\\nAssumptions 1 and 2 in Section 5.1 and Assumption A.1 in Appendix A are the only assumptions we made in deriving our theorems: Assumptions 1 and 2 serve as fundamental premises for subgraph reasoning models[1]. Assumption A.1 is a widely adopted assumption in theoretical analysis of neural networks. Let us summarize our analysis to correct some misunderstandings: we first define subgraph reasoning models(Section 3.2) and show that each component of existing subgraph reasoning models is Lipschitz-continuous(Appendix A). We then establish that SMPNNs are Lipschitz continuous(Theorem 4.5), derive a PAC-Bayesian generalization bound of subgraph reasoning models(Theorem 5.3), and finally prove that the expected risk discrepancy of SMPNNs(Theorem 5.4), which influences the generalization bound, is bounded by the OT Distance between the training and inference triplets. This distance can be interpreted as the difference between distributions of subgraph structures. Throughout this process, we made no additional assumptions. Thus, we respectfully disagree with the assertion that our assumptions are not thoroughly validated nor generalizable to real-world settings.\n\n**Claim/Evidence #2, and Experimental Design/Analysis**\\\nOur work aims to provide a theoretical analysis of subgraph reasoning models for inductive KGC, focusing on the relationship between stability and generalization capability. Since our primary focus is on the theoretical findings, we are more dedicated to presenting the theoretical derivations empirically supported by three distinct KGs. For additional empirical validation, we added two more datasets: FBv3 and NLv3. Also, we present the p-values and 95% confidence intervals for the results regarding the relationship between stability and generalization errors in the table below:\n|Dataset|Correlation|p-value|95% Confidence Interval|\n|-|-|-|-|\n|WNv3| -0.5759 | 0.00019 | (-0.7584, -0.3097)|\n|FBv1| -0.5134 | 0.00031 | (-0.7013, -0.2589)|\n|NLv2| -0.4912 | 0.00584 | (-0.7235, -0.1591)|\n|FBv3 (added)| -0.4513 | 0.00128 | (-0.6519, -0.1918)|\n|NLv3 (added)| -0.5717 | 0.00033 | (-0.7601, -0.2945)|\n\nGiven that the p-values are all below 0.01 and the 95% confidence intervals do not include zero, we conclude that the observed correlations are statistically significant. Hence, we confirm a negative correlation between generalization errors and stability. Furthermore, our experiments covered 48 different model architectures, generated by permuting the candidate functions of each component of the SMPNN, as detailed in Appendix E. These comprehensive experiments allow our findings to be applicable across a wide range of subgraph reasoning models.\n\n**Methods/Evaluation**\\\n#1. Our framework is primarily designed as a theoretical tool for conducting a comprehensive analysis of existing subgraph reasoning models rather than being intended to propose a specific model for real-world applications. The decomposition into subgraph extractors and SMPNNs is intended to facilitate a thorough examination of the existing literature, instead of directly offering novel insights or practical improvements. While our contributions mainly involve theoretical findings on subgraph reasoning models' stability and generalization capability, they were also empirically validated using KG benchmarks.\n\n#2. Using the empirically measured Lipschitz constant as an approximation is a well-established practice in the literature[2]. Please also read our response to #2 of **Other Comment/Suggestion** of **Reviewer AdED**.\n\n**Theoretical Claim**\\\n#2. Please read our response to **Questions For Authors** of **Reviewer npm8**.\n\n**Other Comment/Suggestion**\\\n#2. Due to noisy triplets in real-world datasets, it is difficult to achieve perfect clustering. However, in the t-SNE visualization of Figure 3, most points exhibit a tendency to form label-based clusters. Also, the classification results in Table 1 indicate that a classifier can distinguish subgraphs with different labels using RTMD.\n\n**Questions For Authors**\\\n#1. Please read our response #2 in **Other Strength/Weakness** of **Reviewer AdED**.\n\n#2. As no prior metric is available for the distances between subgraphs containing relations and query triplets, we considered the extension of WWL[3] as a potential alternative. However, we finally opted to extend TMD, as it demonstrated superior capability in capturing the graph structures for non-relational, unconditioned graphs compared to WWL.\n\n#3. Since the computational efficiency of RTMD depends on the size of the subgraphs rather than the entire KG, RTMD can be efficiently applied to large-scale KGs, with a well-designed subgraph extractor.\n\n[1] Inductive Relation Prediction by Subgraph Reasoning, ICML 2020\\\n[2] Tree mover's distance: Bridging graph metrics and stability of graph neural networks, NeurIPS 2022\\\n[3] Wasserstein Weisfeiler-Lehman Graph Kernels, NeurIPS 2019", "claims_and_evidence": "1. The purported significance of stability and its effect on subgraph reasoning models are grounded in contrived assumptions (e.g., Lipschitz continuity and PAC-Bayesian bounds) that are not thoroughly validated or generalizable to real-world settings.\n2. The empirical evidence, though present, lacks comprehensive coverage and robustness. With experiments restricted to a small subset of standard datasets (WNv3, FBv1, NLv2), it is unclear if the findings extend to diverse knowledge graph scenarios or other architectures.", "methods_and_evaluation_criteria": "1. The general framework presented for subgraph reasoning models appears promising but overly theoretical. The decomposition into subgraph extractors and SMPNNs has not been convincingly demonstrated to offer novel insights or practical improvements over existing methodologies.\n2. The stability, measured via RTMD, is incorporated into a PAC-Bayesian framework and evaluated against empirical Lipschitz constants, but there is little discussion on broader evaluation paradigms or alternate metrics.", "theoretical_claims": "1. While the PAC-Bayesian bounds provide theoretical insights, their reliance on restrictive assumptions severely limits their utility in practice. For example, the assumption that discrepancies between subgraph distributions can be simplified through transport distance augmentation appears overly simplistic.\n2. The extension of Tree Mover’s Distance (TMD) to RTMD is an incremental modification and does not provide fundamentally new contributions or theoretical breakthroughs.", "experimental_designs_or_analyses": "1. The experiments are limited to a small set of datasets (WNv3, FBv1, and NLv2), which may not sufficiently represent the broad range of challenges in inductive KGC.\n2. The negative correlation observed between stability and generalization error is presented as support for the theoretical claims. However, the analyses are primarily descriptive and lack rigorous statistical testing. For instance, no confidence intervals, hypothesis testing, or robustness checks are provided to ensure the reliability of the reported correlations.", "relation_to_broader_scientific_literature": "The paper builds on prior research into the stability and generalization capabilities of GNNs, extending previous work (e.g., Lipschitz continuity and Tree Mover's Distance) to the domain of subgraph reasoning models for inductive KGC. Specifically, it adapts and applies theoretical insights, like PAC-Bayesian bounds, to analyze and ensure stability and generalization in KGC scenarios.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n1. The introduction of the Relational Tree Mover's Distance (RTMD) is a novel contribution that provides a meaningful way to measure the differences between subgraphs, complementing existing metrics like Lipschitz continuity.\n2. The paper establishes a strong theoretical foundation, connecting stability to generalization and deriving PAC-Bayesian bounds, which is an underexplored area for inductive KGC.\n\nWeak:\n1. The theoretical analysis relies on simplifying assumptions (e.g., Assumption A.1 and A.2) that may not fully align with real-world conditions in knowledge graphs.\n2. The paper's organization, especially between theoretical sections and empirical experiments, could benefit from smoother transitions or summary explanations to enhance readability.", "other_comments_or_suggestions": "See above and:\n1. Some parts of the theoretical derivations, especially related to the PAC-Bayesian generalization bound (Theorem 5.3), are difficult to follow without more detailed step-by-step explanations. Improving the clarity or providing additional examples could enhance understanding.\n2. The t-SNE visualizations (Figure 3) are useful but would benefit from additional explanation or annotations, especially for datasets where clustering is less distinct.", "questions_for_authors": "Q1. The reviewer believes that the time complexity of this model is quite high. Please provide a time complexity analysis.\nQ2. How was the Relational Tree Mover's Distance (RTMD) validated as an optimal metric compared to other potential metrics for subgraph differences? Were alternative metrics or baselines considered in the analysis?\nQ3. Given that RTMD involves optimal transport calculations, what are the scalability implications for large-scale knowledge graphs? Are there any approximations or optimizations used to ensure the approach remains computationally efficient?", "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": "yGnaei9qgc", "reviewer": "Reviewer_s8XS", "summary": "This paper presents the theoretical analysis of the relationship between stability and generalization capability in subgraph reasoning models for inductive KG completion. The authors define stability as the consistency of a model’s outputs across variations in input subgraphs and introduce the Relational Tree Mover’s Distance to quantify subgraph differences. They demonstrate that a model’s generalization capability is proportional to its stability theoretically and empirically, validating these findings on real-world datasets.\n## update after rebuttal:\nThank the authors for their detailed responses. Most of my initial concerns have been addressed. As a result, I kept my original score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Claims And Evidence**\\\nWe theoretically establish a connection between stability and generalization capability, where generalization capability refers to the gap between performance on training and test data. This indicates that more stable models tend to exhibit a smaller gap between performance on training and test data. If the performances on training data are not similar, actual performances on test data may not directly align with generalization capabilities. Therefore, our findings are not in conflict with your observations.\n\n**Methods And Evaluation Criteria**\\\nNone of our derivations and findings is an incremental extension of [1] or [2]. While [1] studies the generalization bounds of KGC models, [1] does not consider either an inductive setting or the stability of KGC models. While [2] studies the generalization of GIN, a specific non-relational GNN model, using TMD, their analysis has nothing to do with KGC or subgraph reasoning models. For more details, please read our response to **Questions For Authors** of **Reviewer npm8**.\n\n**Experimental Designs Or Analyses**\\\n#1. Our work aims to provide a theoretical analysis of subgraph reasoning models for inductive KGC, focusing on the relationship between stability and generalization capability. Since our primary focus is on the theoretical findings, we are more dedicated to presenting the theoretical derivations empirically supported by three distinct KGs. In response to the request for additional experiments, we added two more datasets: FBv3 and NLv3. The results on these datasets exhibit the same trends as our original findings. For more details, please refer to our response to **“Claims And Evidence” #2 and “Experimental Designs Or Analyses”** of **Reviewer ePj1**.\n\n#2. Our work theoretically establishes the relationship between a subgraph reasoning model’s stability and its generalization capability, where generalization capability is defined as the discrepancy between a model’s performance on training and test data. While generalization capability can be a useful base for evaluating a model, a model’s better generalization capability does not necessarily lead to its better performance on a test set. This is because the generalization capability indicates the gap between the empirical risk on training KG and the classification accuracy on the inference KG rather than the absolute accuracy on the inference KG. Nonetheless, when a model’s design choices do not significantly change empirical risk, generalization capability becomes a crucial factor, and selecting a model with higher stability can result in improved performance. In Section 4.3 and Appendix A, we provide the Lipschitz constants for the possible design choices of each component of subgraph reasoning models, which serve as a basis for comparing stability. This theoretical characterization of stability is one of our key contributions, offering a principled framework for evaluating model components beyond empirical observations. Our findings provide practical guidance for selecting model components suited for inductive KGC, emphasizing that stability should be considered alongside empirical risk. By formalizing the role of stability in generalization, our work advances the understanding of subgraph reasoning models and offers actionable insights for future research.\n\n**Questions For Authors**\\\nRelation prediction, which aims to predict the relation of the given triplet, and link prediction, which aims to predict the tail entity of the given triplet, can be reformulated as instances of the triplet classification task. For example, GraIL [3] performs link prediction by computing a score for each query triplet and comparing scores across candidate entities. Therefore, our theoretical findings are applicable to relation prediction and link prediction tasks.\n\n[1] Lee et al., “PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning”, ICML 2024.\\\n[2] Chuang and Jegelka, “Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks”, NeurIPS 2022.\\\n[3] Teru et al., “Inductive Relation Prediction by Subgraph Reasoning”, ICML 2020.", "claims_and_evidence": "The authors claimed in Lines 278-281 that: “the subgraph reasoning model using a mean aggregator as the aggregation function is more stable than the model using a sum aggregator as the aggregation function.” However, based on my practical experience, the mean aggregator tends to obtain weaker performance than the sum aggregator in KG inductive reasoning tasks. It would be better to prove this claim by the detailed results in Figure 5.", "methods_and_evaluation_criteria": "The proposed method makes sense but the novelty appears to be incremental, as the two key components are primarily derived from existing works in KGRL and GNNs:\n\n[1] PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning\n[2] Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks\n\nWhile the authors acknowledge these prior studies, the specific challenges required when transferring these components to the context of inductive subgraph reasoning are not sufficiently emphasized.", "theoretical_claims": "No, due to time constraints during the review period, I was unable to verify the details of the proof.", "experimental_designs_or_analyses": "The authors have selected three datasets—FBv1, NLv2, and WNv3—for their experiments. However, the rationale behind this specific selection is not clearly explained. It appears that these datasets may have been chosen arbitrarily, with one dataset representing each KG source. Given that the scale of the total 12 available datasets is relatively small, limiting the experiments to only three datasets may weaken the generalizability of the results.\n\nThe results presented in Figure 5 demonstrate the core claim that stable subgraph reasoning models exhibit high generalization capability. However, while this finding is reasonable, it is not particularly groundbreaking or insightful. A deeper analysis is needed to systematically compare different subgraph reasoning models from the perspective of stability, supported by their performance on real-world datasets to validate the conclusions. \n\nFurthermore, it would be more impactful to discuss the specific technical design choices in these models that influence stability, providing actionable insights for future work. For instance, the authors could propose a theoretically-aligned model design and empirically prove its superior generalization ability, which would significantly enhance the contribution of this study.", "relation_to_broader_scientific_literature": "Please check my comments in \"Methods And Evaluation Criteria\".", "essential_references_not_discussed": "I have no suggestions for additional references.", "other_strengths_and_weaknesses": "The topic is interesting and meaningful.\n\nThe draft is well-organized and easy to follow.", "other_comments_or_suggestions": "Please check my above suggestions.", "questions_for_authors": "The study focuses on label prediction settings, but the generalizability of subgraph reasoning models in link prediction tasks is more critical for KG completion. How can the findings or theoretical insights be adapted or extended to link prediction tasks?", "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": "an8bHvgkll", "reviewer": "Reviewer_AdED", "summary": "This paper proposes a theoretical analysis of the relationship between stability and generalization capability for subgraph reasoning models in inductive knowledge graph completion. They define stability as the degree of consistency in a subgraph reasoning model’s outputs in response to differences in input subgraphs and introduce the Relational Tree Mover’s Distance as a metric to quantify the differences between subgraphs.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Experimental Designs/Analyses**\\\nThe datasets used in our experiments are the standard benchmarks for inductive KGC [1], where we choose to use three distinct KGs. For additional experimental results, please read our response to **“Claims/Evidence” #2, and “Experimental Designs/Analyses”** of **Reviewer ePj1**.\n\n**Other Strengths/Weaknesses**\\\n#1. While our work presents the first analysis on the relationship between stability and generalization bound of subgraph reasoning models for inductive KGC, our analysis is limited to scenarios with unseen entities and is not directly applicable to scenarios where relations may be unseen, as we mentioned in Lines 436-439, right column. We plan to explore this direction in our future work.\n\n#2. Our framework is primarily designed as a theoretical tool for conducting a comprehensive analysis of existing subgraph reasoning models rather than being intended to propose a specific model for real-world applications. As such, computational efficiency is not a primary concern within the scope of our study. Nonetheless, we provide the time complexities of RTMD and SMPNN for reference: the time complexity of RTMD is $O(T\\_{OT}(\\max(|\\mathcal{V}\\_{S\\_1}|, |\\mathcal{V}\\_{S\\_2}|)) + L \\cdot T\\_{OT}(d\\_{max}) \\cdot \\max(|\\mathcal{E}\\_{S\\_1}|, |\\mathcal{E}\\_{S\\_2}|))$ where $T_{\\text{OT}}(m)$ denotes the time complexity for calculating the optimal transport distance between two sets of size $m$. The time complexity of SMPNN is $O(d^2L\\mathcal{E}_S+d\\mathcal{V}_S+d^2)$.\n\n#3. In Theorem 5.3, we establish the theoretical relationship between stability and generalization capability. This theoretical result is empirically validated in Section 6.3, where we demonstrate negative correlations between the stability of various subgraph reasoning models and generalization error across multiple datasets. These findings indicate a positive relationship between stability and generalization capability.\n\n#4. Our subgraph reasoning model framework is designed to subsume the existing subgraph reasoning models, including GraIL, NBFNet, and RED-GNN. Since these methods do not account for sparse or noisy connections during subgraph extraction, we follow them and utilize a simple k-hop extractor in our experiments. However, our theoretical findings are not limited to any specific subgraph extractor. Indeed, they hold for any subgraph extractor as long as the extracted subgraphs satisfy Assumption 1 in Section 5.1.\n\n#5. Although our focus is on the inductive setting, the theoretical results presented in our paper are also applicable to the transductive setting, where $\\mathcal{V}\\_{\\text{tr}} = \\mathcal{V}\\_{\\text{inf}}$ and $\\mathcal{F}\\_{\\text{tr}} = \\mathcal{F}\\_{\\text{inf}}$. This configuration does not violate any of the assumptions made throughout the paper. We want to clarify that we do not argue that stability is more critical in inductive than transductive scenarios. Given that our work is the first to examine the relationship between stability and generalization capability, comparing the importance of stability between inductive and transductive settings falls outside the scope of our study.\n\n**Other Comments/Suggestions**\\\n#1. RTMD is a pseudo-metric since there exists a pair of distinct subgraphs for which the RTMD between them is 0. However, this does not undermine the validity of our analysis because when RTMD fails to distinguish between two subgraphs, the SMPNNs also cannot distinguish between them; RTMD models the behavior of SMPNN during message passing, and a 0 RTMD value between two subgraphs indicates that SMPNNs will behave identically for those subgraphs. Also, due to the presence of relations and query triplets, RTMD is rarely 0 in practice. Thus, although RTMD is a pseudo-metric, it does not undermine our study's theoretical and empirical findings.\n\n#2. The existing metrics for measuring graph differences are not directly applicable to our setting, where both relations and query triplets are present. Also, extending these existing metrics to our setting is far from straightforward, as it necessitates incorporating relations and query triplets specific to each graph. Therefore, a direct comparison between RTMD and the existing metrics is not feasible within the scope of our paper.\n\n**Questions**\\\nOur framework is primarily designed as a theoretical tool for conducting a comprehensive analysis of existing subgraph reasoning models rather than being intended to propose a specific model for real-world applications. As such, we emphasize that computational efficiency is not a primary concern within the scope of our study. It is important to note that when using the same subgraph extractor and SMPNN configuration in our framework as those employed by the state-of-the-art models, its computational complexity is the same as the original model. Please also read our response to #2 of **Other Strengths/Weaknesses**.\n\n[1] Inductive Relation Prediction by Subgraph Reasoning, ICML 2020", "claims_and_evidence": "The claims made in this paper are generally supported by the theoretical analysis and experimental results.", "methods_and_evaluation_criteria": "The proposed method and evaluation criteria are appropriate for the problem at hand.", "theoretical_claims": "The authors should consider providing more detailed explanations and clarifications for some of the more complex proofs.", "experimental_designs_or_analyses": "The experimental designs and analyses are generally sound. However, the sample size for the experiments is relatively small.", "relation_to_broader_scientific_literature": "The key contributions of this paper are related to the broader scientific literature on knowledge graph completion and graph neural networks.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n\n1. The paper provides a novel theoretical analysis of the relationship between stability and generalization capability for subgraph reasoning models.\n\n2. The authors use real-world datasets to empirically validate their theoretical findings.\n\nWeaknesses:\n\n1. The paper lacks a comprehensive discussion of the potential limitations of the proposed methods.\n\n2. This paper lacks analysis of the computational complexity or scalability of their approach.\n\n3. The title emphasizes \"Stability and Generalization Capability,\" but there is no efficient experiment to support.\n\n4. The framework assumes subgraphs are extracted via k-hop neighbors, but this ignores sparse or noisy connections. For example, in long-tailed KGs, k-hop extraction may fail to capture relevant paths, leading to biased subgraphs. The authors do not validate robustness to extraction strategies.\n\n5. The paper does not clearly differentiate inductive KGC from transductive KGC in terms of stability requirements. While inductive models handle unseen entities, the authors do not justify why stability (e.g., sensitivity to subgraph perturbations) is more critical in this setting than in transductive scenarios.", "other_comments_or_suggestions": "1. The use of \"pseudo-metric\" is not clearly justified. \n\n2. The authors should provide a more detailed comparison of RTMD with other existing metrics for measuring subgraph differences.", "questions_for_authors": "1. How do the proposed methods compare with other state-of-the-art methods in terms of computational efficiency and scalability?", "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": "wr94EFu49I", "reviewer": "Reviewer_npm8", "summary": "The authors generalize the Tree Mover's Distance to relational graph to introduce Relational Tree Mover's DIstance (RTMD), which is a distance of sub-graphs in a relational graph. They proof the current subgraph message passing neural networks (SMPNNs) are Lipschitz contituous under the distance, so define the stability as the reciprocal of the Lipschitz constant. Then, they use PAC-Bayesian generalization bound to bound the generalization error in inductive learning on a relational graph. The upper bound is bounded by the expected risk discrepance, which is further bounded by the optimal transport distance with the cost as RTMD. Their experiments on three classic inductive knowledge graph completion dataset prove that (1) the RTMD is appropriate to quantifying the distance between subgraphs; (2) the practical SMPNNs are Lipschitz continuous under the RTMP and (3) there are correlation between models' stability and generalization error.\n\n\n## Update after rebuttal\n\nI believe that it is a good work and my concerns have been solved so I update my score from 3 to 4.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Claims And Evidence**\\\n#1. The experiments in Section 6.1 are designed to demonstrate that RTMD is a valid metric for quantifying differences between subgraphs extracted from real-world KGs. If RTMD is an appropriate metric, subgraphs with positive labels should be located closer to other subgraphs with positive labels, while being farther from subgraphs with negative labels. The t-SNE visualization in Figure 3 is intended to illustrate whether this tendency is observable. Additionally, the SVM classification results in Table 1 provide a quantitative measure of how well the two types of subgraphs can be distinguished solely based on RTMD.\n\n#2. As our work is the first to investigate the connection between the stability and generalization capability of subgraph reasoning models, there is no baseline to compare correlation coefficients. However, we can demonstrate that the negative correlation is statistically significant by the hypothesis testing results provided below. In general, a correlation is considered statistically significant if the p-value is below 0.01 and the 95% confidence interval does not include zero.\n\n| Dataset | p-value | 95% Confidence Interval |\n|-|-|-|\n| FBv1 | 0.00031 | (-0.7013, -0.2589) |\n| NLv2 | 0.00584 | (-0.7235, -0.1591) |\n| WNv3 | 0.00019 | (-0.7584, -0.3097) |\n\nAs the p-values are all below 0.01 and the 95% confidence intervals do not include zero, we conclude that there exists a negative correlation between generalization error and stability.\n\n**Essential References Not Discussed**\\\nSince the relationship between TMD and stability discussed in [2] is limited to GIN, it is infeasible to directly generalize the findings in [2] to arbitrary non-relational SMPNNs. Furthermore, our KGC problems require additional considerations of edge labels and query triplets that are not considered in TMD. These make our formulations of RTMD non-trivial extensions of TMD, and thus, we omitted TMD equations in our paper and focused on our formulations. Following your comments, we will try to elaborate more on the connections between TMD and RTMD in the camera-ready version if this paper is accepted. Please refer to our response to **Questions for Authors** for a more detailed discussion of the differences between our work and [2], including the distinction between TMD and RTMD.\n\n**Questions For Authors**\\\nThe most relevant work to ours is [1,2]. While [1] studies the generalization bound of KGRL methods under a transductive setting, where all entities are known and fixed, our work considers an inductive setting, where the entities at inference may differ from those seen during training. This more challenging setting introduces the necessity of accounting for the differences between the training KG and the inference KG, which makes every step of our analysis more difficult. Furthermore, unlike the models considered in [1], subgraph reasoning models in our analysis perform conditional message passing, where message propagation depends not only on the graph structure but also on a query triplet, further complicating the analysis. On the other hand, [2] defines TMD, a measure for quantifying difference between graphs without relations. Note that TMD is neither directly applicable nor easily extendable to our analysis since the input subgraphs of SMPNNs differ significantly from those considered in [2]. While TMD only considers node features and graph structure, the input subgraphs of SMPNNs are also associated with query triplets and labeled edges, which introduces additional challenges in incorporating the differences in relation labels and dependencies on query triplets to quantify differences between subgraphs. Moreover, our analysis applies to any model that falls under our subgraph reasoning model, whereas [2] is limited to a specific GIN architecture. Altogether, our work provides the first theoretical analysis of the relationship between the stability and the generalization capability of subgraph reasoning models for inductive KGC, addressing considerable challenges unique to the inductive setting and subgraph reasoning models.\n\n[1] Lee et al., “PAC-Bayesian Generalization Bounds for Knowledge Graph Representation Learning”, ICML 2024.\\\n[2] Chuang and Jegelka, “Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks”, NeurIPS 2022.", "claims_and_evidence": "Their two main conclusions are: 1. Lipschitz continuity of SMPNN, 2. the RTMD is an appropreiated distance 3. the stability can be used to estimate the generalization error.\n\nIn my opinion, their experiments support their claims well. A minor problem is:\n1. I can roughly understand why the t-SNE and SVM experiments can serve evidences to prove that the RTMD is an appropreiated distance, but I hope the authors can give a more intuitive explanation.\n2. I am not sure whether the correlation about -0.5 in Figure 5 means the strong correlation between stability and generalization error. Can the authors provide some baselines or some similar results on  link prediction in non-relation graphs as a reference?", "methods_and_evaluation_criteria": "Their datasets are classic inductive KGC datasets and I think their evaluation is fair.", "theoretical_claims": "I do not check the correctness and details of their theoretical claims. But I think the logic relation between their theorems are clear.", "experimental_designs_or_analyses": "See \"Claims And Evidence\". These two minor problems are about the analyses of their experiments.", "relation_to_broader_scientific_literature": "Inductive KGC is an important and practical problem. These work extend the PAC-generalization theory to inductive KGC and can further provide guidance for the research of subgraph networks on KG.", "essential_references_not_discussed": "I do not find Essential References Not Discussed. But I think some background like TMD and some related conclusion that can be induced by TMD on non-relational sub-graph NN can be introduced more detailed. For example, I think there should be an equation to introduce the TMD, to help reader understanding the connection between TMD and RTMD, as well as understanding the contribution of the work clear.", "other_strengths_and_weaknesses": "I think the overall ideas and the structure of their theorem is clear and can be understood easily. Their expression are formal and reader-friendly. Their visualization is very clear to help reader to understand these theoretical tools.", "other_comments_or_suggestions": "No other comments and suggestions.", "questions_for_authors": "My main concern is about their contribution. Because I am not familiar with the previous work, I am not sure to what extent has past work been accomplished, and which parts of this work are a direct extension, and which parts involve more difficult problems. Specifically, has previous work already done what this work involves on non-relational graphs, and this work just adds the original theorem to consider relational edges? If so, what are the non-trivial or difficult aspects?", "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:

Meta-review: This paper presents a theoretical analysis of the relationship between stability and generalization capability in subgraph reasoning models for inductive knowledge graph completion (KGC). The authors introduce the Relational Tree Mover’s Distance (RTMD) to quantify subgraph differences and derive a PAC-Bayesian generalization bound linking stability to generalization performance. Empirical validation on real-world datasets supports their theoretical claims.

Strengths:

-	The paper presents a novel theoretical framework for analyzing the stability and generalization capability of subgraph reasoning models.
-	The introduction of the Relational Tree Mover's Distance (RTMD)is a novel contribution that provides a meaningful way to measure the differences between subgraphs.
-	Empirical experiments effectively support theoretical analysis, validating the claims and demonstrating the practical relevance of the findings.

Weaknesses:

-	The experiments are limited to a small set of standard datasets, which may not be representative of diverse knowledge graph scenarios.
-	Some assumptions in the paper may not fully align with real-world KGs, and the impact of these simplifications is not thoroughly discussed.

The paper makes a valuable contribution to the understanding of subgraph reasoning models in inductive knowledge graph completion. The authors addressed some key concerns of reviewers in rebuttal with additional experiments and explanations.
Decision: Accept (poster)