Learning Multi-Granularity and Adaptive Representation for Knowledge Graph Reasoning

1 Introduction

Knowledge graphs (KGs) [Dong et al., 2014] such as Wikidata [Vrandeˇci´c, 2012] and DBPedia [Auer et al., 2007] have been widely utilized in many knowledge-intensive applications including semantic search [Noy et al., 2019; Dong, 2019], recommendation systems [Wang et al., 2018; Wang et al., 2021], and question answering [Huang et al., 2019; Saxena et al., 2020; Li et al., 2022]. A KG is a multi-relational graph containing factual triples. However, real-world KGs constructed manually or automatically are inevitably incomplete, thus predicting unknown edges as analogous to uncovering new facts is challenging. Traditional knowledge graph reasoning (KGR) methods leverage the knowledge graph embedding (KGE) [Wang et al., 2017], projecting entities and relations into low-dimensional dense vectors, to aid the inference of missing factual triples [Bordes et al., 2013; Sun et al., 2019; Liu et al., 2023; Shang et al., 2023]. Despite the better expressive capacity of KGE-based models, there remains an inherent deficiency in their explainability. For effective KGR, it is pivotal to acquire high-quality representations that not only embed the factual triples but also accurately reflect the underlying graph structure [Chen et al., 2020b].

Recent KGR studies [Zhu et al., 2021; Zhang and Yao, 2022; Teru et al., 2020; Xu et al., 2022; Mai et al., 2021] have moved away from KGE-based methods and focus instead on learning entity-independent representation from existing structures in KGs, e.g., relation paths and subgraphs. For methods based on relation paths, recent work [Zhu et al., 2021; Zhang et al., 2022; Zhang and Yao, 2022; Zhu et al., 2023] emphasizes capturing features of fixed-length relation paths between two entities in KGs, overlooking the semantic correlation between the query and local evidence contained in paths of varying lengths. Intuitively, the local evidence reasoning required is dependent on the context of the query. For example, for query (Messi, lives in, ?), we should capture evidence from the local structure of the 2-hop Path between Messi and Florida. If the query changes to (Messi, plays in, ?), 3-hop Path deserves more attention. To mine the local evidence contained in variable-length relation paths, subgraph-based methods [Teru et al., 2020; Xu et al., 2022; Mai et al., 2021] are proposed, exploiting the enclosing subgraph effectively. However, they overlook the fact that such subgraph modeling is inefficient and inevitably involves unrelated entities and relations, resulting in equal attention to different structures, increasing training difficulty, and introducing noise. Specifically, GraIL [Teru et al., 2020] and the subsequent works [Xu et al., 2022] first extract enclosing subgraphs between the query entity and other candidate entities. Then, they repeatedly apply graph neural networks (GNNs) to enclosing subgraphs. We identify the trend of repeated extraction of these enclosing subgraphs is unnecessary. As illustrated in Figure 1, while extracting 2-hop enclosing subgraphs between Messi and Florida, and Messi and Busquets respectively, the resulting subgraph structures are identical, suggesting that these methods could expend excessive time on extracting identical subgraph. Moreover, they also ignore the correlation between queries and structures, e.g., 2-hop Path and 3-hop Path between Messi and Florida are treated equally for different queries.

To address the above limitations, we propose a novel multigranularity and adaptive representation framework for KGR, referred to as MulGA. To alleviate the inefficiencies associated with explicit enclosing subgraph extraction and to expand the scope of subgraph information, MulGA initially exploits the connectivity subgraph that can be implicitly extracted via the breadth-first search (BFS) algorithm. As depicted in Figure 1, the 2-hop enclosing subgraph between Messi and Florida, which involves the longest relation path of length 3, can be replaced with a connectivity subgraph of size 3. This connectivity subgraph not only accurately models structures of the enclosing subgraph but also embodies the neighboring relations as considered in the SNRI [Xu et al., 2022]. The iterative process of the BFS aligns with the extraction of enclosing subgraphs. Consequently, a connectivity subgraph can seamlessly represent multiple enclosing subgraphs, optimizing time and resources. Additionally, MulGA presents a GNN-based multi-granularity embedding propagation module across connectivity subgraphs to produce two levels of granularity embeddings hierarchically, i.e., triple, and relation paths. Moreover, we propose a query-aware attention mechanism to select query-related edges during propagation to enrich the relation path granularity. Furthermore, to leverage query-relevant features contained in different structures, we design a self-attention-based merging mechanism that adaptively assigns query-related weights to different granularity embeddings, taking into account the correlation among them. Subsequently, subgraph granularity embeddings can be obtained by merging the above two granularity embeddings for reasoning. In experiments, we find that the proposed merging mechanism can alleviate over-smoothing in GNNs.

Our key contributions are summarized as follows:

• We adopt the connectivity subgraph to effectively model the various structures in KGs to achieve a hierarchical representation of triples, relational paths, and subgraphs, optimizing time and resources.
• To obtain multi-granularity embeddings, we design a GNN-based multi-granularity embedding propagation to learn query-related granularity embedding hierarchically.
• We introduce a self-attention-based merging mechanism that adaptively assigns query-related weight to different granularities and ultimately fuse them into robust subgraph granularity representations for reasoning.
• Extensive experiments have been conducted on 15 benchmarks involving both transductive and inductive reasoning tasks. MulGA achieves a significant improvement in mean reciprocal rank (MRR) by an average of 1.5% on transductive and 2.7% on inductive tasks.

2 Preliminary

2.1 Notations

Definition 1. (Knowledge Graph). A knowledge graph (KG) G = (E,R, T ) is defined by the set of entities E, relations R, and triples T . A triple is usually denoted as (h, r, t) ∈ T , where h ∈ E, t ∈ E and r ∈ R represent the head entity, the tail entity and the relation between h and t, respectively.

Definition 2. (Transductive KGR). Given a KG G, transductive KGR task refers to predicting either the tail entity t ∈ E given h ∈ E and r ∈ R, i.e., (h, r, ?), or the head entity h ∈ E given r ∈ R and t ∈ E, i.e., (?, r, t), where (h, r, t) /∈ G.

Definition 3. (Inductive KGR). Given a source KG GS = (ES, RS, TS) and a target KG GT = (ET , RT , TT ), where GT consists of unseen entities not in the GS: ET ∩ES = ∅, RT ⊆ RS. Inductive KGR task aims to train a model on the source KG GS and then predict either the tail entity t ∈ ET given h ∈ ET and r ∈ RT , i.e., (h, r, ?), or the head entity h ∈ ET given r ∈ RT and t ∈ ET , i.e., (?, r, t), where (h, r, t) /∈ GT .

3 Method

Figure 2 illustrates the overall architecture of MulGA. Given a query (h, r, ?) or (?, r, e), MulGA initiates by implicitly extracting the connectivity subgraph utilizing BFS. Meanwhile, MulGA propagates structural messages from the query entity to candidate entities, producing two types of granularity embeddings: triples and relation paths of varying lengths. Finally, the above two granularity embeddings are merged through the proposed self-attention-based merging mechanism, generating the final subgraph granularity embedding for reasoning.

3.1 Connectivity Subgraph

Given a query (h, r, ?), intuitively, to perform reasoning, it is vital to utilize various structural information surrounding the query entity h. The connectivity subgraph can model adequate structures around query entities for this purpose.

Definition 4. (Connectivity Subgraph). Given an entity h, a connectivity subgraph G n h can be modeled as follows:

where n is the size of the connectivity subgraph. P ih , namely a connectivity subgraph component, is the set of relation paths of length i originating from h. Besides, ⊕ denotes the combination operator on the path set.

Let E(P i,j h ) be the set of jth entity on all i-length relation paths originating from h, and E(P i,0 h ) = {h}. Therefore, the entities in P ih are denoted as E(P ih ) = E(P i,0 h ) ∪ E(P i,1 h ) ∪ · · · ∪ E(P i,i h ). Analogously, the relations in P ih are denoted as R(P ih ) = R(P i,1 h )∪R(P i,2 h )∪· · ·∪R(P i,i h ), whereR(P i,j h ) is the set of jth relation on all i-length relation paths originating from h. Besides, E(P i,j h ) =R(P i,j h ) = ∅, if j > i.

From Definition 4, a connectivity subgraph of size n encompasses all entities located at a distance no more than n from the query entity, along with their corresponding structures. Following the previous work [Xu et al., 2019], inverse edges of each factual triple and self-loop edge of each entity are added to original KGs. Specifically, if (h, r, t) exists in KGs, then (t, r-1 , h), (h, self loop, h), and (t, self loop, t) are added, where r-1 is the inverse of r, to original KGs. Therefore, the iterative formula for components can be obtained when i ≥ 1:

In this way, the connectivity subgraph can be easily implicitly extracted using the BFS algorithm. For example, as shown in Figure 2, the red arrows indicate the new connectivity subgraph component found by BFS. Furthermore, a connectivity subgraph G 3h can concurrently embody the enclosing subgraph formed between h and e, e1, e2, e3, e4, which reduces the time-consuming extraction of duplicated structures.

3.2 GNN-basedMulti-Granularity Embedding Propagation

The GNN-based multi-granularity embedding propagation (GMEP) utilizes the GNN to produce two levels of granularity embeddings, i.e., triple and relation path, of entities in G n h .

Triple Granularity Embedding

According to Definition 4, P 1 h is the set of triples in the form of (h, r, e). Therefore, taking entity e as an example, we can perform representation learning directly on P 1 h and then obtain corresponding triple granularity embedding eTh = eP 1h .

Relation Path Granularity Embedding

Similarly, in the Definition 4, P ih (2 ≤ i ≤ n) means the set of all i-length relation paths originating from h. We can perform representation learning on the P ih to obtain the corresponding embeddings. Therefore, taking entity e as an example, the relation path granularity embeddings ePh of different lengths in G n h can be denoted as ePh = [eP 2h , eP 3h , · · · , eP n h ].

Propagation Mechanism

According to Eq. 2, the triple structure P 1 h is obtained before the relational path, thus enabling the hierarchical calculation of relational path granularity based on the triple granularity. Drawing inspiration from the hierarchical message-passing mechanism in GNN [Scarselli et al., 2008], we design a propagation module that takes the query entity as initial subgraph (P 0 h ). This module dynamically expands the current graph structure following BFS, facilitating layer-by-layer propagation of structural information. Through this sequential propagation, we obtain various granularities embedding, which ensures a thorough capture of structural information contained in KGs. Consequently, we can directly apply one layer of GNN in each connectivity subgraph component. Thus, the i-th layer of our GNN can be calculated as follows:

where i denotes the i-th connectivity subgraph component; ϕ(·, ·) means MESSAGE function, which is used to pass known structural information, and can be used with most offthe-shelf KGE methods, such as TransE [Bordes et al., 2013], RotatE [Sun et al., 2019], and DistMult [Yang et al., 2015]. rit denotes the embedding of the relation between entity u in P i-1 h and entity v in P ih at the i-th layer; In (v|E(P i-1,i-1 h )) represents the entities on the E(P i-1,i-1 h ) pointing to entity v in P ih . Since multiple queries share the same connectivity subgraph, we design the attention mechanism to adaptively assign weights to each edge. αiurtv is the edge attention weight at the i-th layer corresponding to the edge (u, rt, v); σ(·) denotes the sigmoid function; [·; ·] denotes tensors concatenation; W i1 ∈ Rd×4d , W i2 ∈ R1×d , W i3 ∈ Rd×d , bi1 ∈ R1×d , bi2 ∈ R1×1 , and bi3 ∈ R1×d are trainable parameters at the i-th layer; d is embedding dimensions of the entity and relation.

Since GMEP propagates message in the connectivity subgraph from query entity h to the other entities, we can initialize the representation of the entity h as follows:

where W4 ∈ Rd×d , b4 ∈ R1×d are trainable parameters and r denotes the embedding of query relation.

Finally, we stack n layers of GNN in Eq. 3 to form GMEP module. As a result, the triple embedding eTh (1-th GNN layer) and relation path embeddings of different lengths ePh (from 2-th to n-th GNN layers) can be produced.

Subgraph Granularity Embedding

Similar to triple and relation path granularity, subgraph granularity can be derived via representation learning across the entire connectivity subgraph. However, this may result in duplicated calculations. To avoid this, given representations of connectivity components, we can merge them to generate the subgraph granularity. Taking entity e as an example, subgraph embedding of the entity e in G n h can be expressed as eGn h :

where ⊗ signifies the merging operation, and eP ih = 0, if E(P ih ) ∩ {e} = ∅. For merging operations, there are several common options, such as max, sum, mean, concat. However, the particularities of different granularity embeddings are ignored in such merging operations. To this end, we propose a self-attention-based merging mechanism, which can incorporate structural features among different granularities.

3.3 Self-Attention-basedMergingMechanism

Given n different granularity embeddings H = [eP 1h , eP 2h , · · · , eP n h ] ∈ Rn×d , the self-attention-based merging (SAM)

mechanism, inspired by the Transformer [Vaswani et al., 2017; Lee et al., 2019], is to fuse n different granularity embeddings into a subgraph embedding, i.e., Rn×d → R1×d . Concretely, the SAMmechanism consists of two functions: the multi-head attention function (MA), and the self-attention function (SA).

The Multi-head Attention Function: To tackle the limitation of simple merging methods to distinguish important granularity, we use the multi-head attention (MA) [Vaswani et al., 2017], which can be formulated as follows:

where Att(Q,K, V ) = w(QKT )V , w is an activation function; W iQ ∈ Rd×d , W iK ∈ Rd×d , W iV ∈ Rd×d are trainable parameters and the output projection matrix is WO ∈ Rmd×dfinal , where dfinal is the output dimension of the multi-head attention function.

Self-attention Function: Another evident disadvantage of simple merging operations is deemed as the neglect of relationships among different granularity embeddings. To this end, we introduce a self-attention (SA) function which can be formulated as follows:

where LN is the LayerNorm function, and rFF is any row-wise feedforward layer.

Overall Self-Attention-based Merging Mechanism: In order to fuse n different granularity embeddings into a more powerful subgraph embedding eGn h , we introduce a trainable parameter QEG ∈ R1×d that is directly optimized in an endto-end fashion, as follows:

Finally, for the query (h, r, ?), we define a simple function to score the candidate entity e, as follows:

where W5 ∈ R1×d and b5 ∈ R1×1 are trainable parameters.

3.4 Optimization

Following previous works [Dettmers et al., 2018; Vashishth et al., 2019], for each triple (h, r, t) in the KG, we first convert it to queries (h, r, ?) and (t, r-1 , ?). Taking (h, r, ?) as an example, we minimize the binary cross-entropy loss to optimize the model parameters, as follows:

where (h, r, t′j ) denotes the j-th negative triple by corrupting tail entity in (h, r, t). Since the MulGA can obtain multigranularity embedding of all entities in the KG given the query (h, r, ?) or (t, r-1 , ?), we set N = |E| - 1 in Eq. 15.

4 Experiments

4.1 Experimental Setup

Datasets and Baselines

For transductive setting, WN18RR [Dettmers et al., 2018], FB15K-237 [Toutanova et al., 2015], and NELL-995 [Das et al., 2018] are used to evaluate the performance of MulGA. For inductive setting, we use the inductive benchmark datasets provided in GraIL [Teru et al., 2020]. To evaluate the performance, we chose three categories totaling 16 baselines for transductive setting and 8 baselines for inductive setting.

Evaluation Metrics

In transductive and inductive settings, we report mean reciprocal rank (MRR), Hits@1, and Hits@10 following the filtered setting as described in [Bordes et al., 2013; Zhu et al., 2023].

4.2 Main Results

Comparison for Performance

Table 1 reports results of MulGA and all baselines in the transductive setting. As expected, models that only exploit the single granularity structural feature in KGs do not show competitive performance. Conversely, MulGA consistently achieves the best performance on most benchmarks, demonstrating the effectiveness of the unified way to obtain different granularity embeddings and our proposed merging technique. Notably, on WN18RR, FB15K-237, and NELL-995, MulGA improves MRR by 9.3%, 7.2%, and 3.1% compared with the best triple-based methods, 2.2%, 0.7%, and 1.7% compared with the best relation path-based methods, and 8.7%, 5.3%, and 1.5% compared with the best subgraph-based methods.

In the inductive setting, the experimental results are presented in Table 2. MulGA achieves the best performances on most datasets. Overall, MulGA achieves remarkable improvements over the strongest baselines w.r.t. MRR by 0.1%-8.2% in the inductive setting. Such results indicate that the utilization of different granularity features in triples, relation paths, and subgraphs is helpful for MulGA to learn similar structural information to generalize unseen entities in target KGs. Similarly, MulGA has a significant improvement on Hits@1, which means MulGA can better capture semantic correlation between queries and various structures in KGs. Specifically, MulGA improves Hits@1 by 0.1%-8.3% compared with the second best results. Additionally, WN18RR (V1-V4) inductive dataset contains many empty subgraphs [Mai et al., 2021], i.e., the enclosing subgraphs of the head and candidate entities at a given hop only have the current triple and no other valid edges. This could be the reason why the results of MulGA on the WN18RR dataset are slightly lower than A*Net. Although the sparse KG can reduce different granularity information significantly, the performance of MulGA is competitive with the previous state-of-the-art methods in WN18RR (V1-V4). Moreover, methods explicitly extracting subgraphs and surrounding neighboring relation paths, such as SNRI, suffer from scalability drawbacks as the sizes of KGs increase(FB15K-237 (V3) (V4) and NELL-995 (V3) (V4)). Expansion of the graph scale results in a rapid rise in CPU memory usage, ultimately leading to an out-of-memory (OOM) breakdown.

Comparison for Efficiency

We further select seven competitive models to compare the efficiency with MulGA and results are shown in Table 3 and Figure 3. We can draw three conclusions: (1) MulGA achieves a trade-off between performance and efficiency across diverse graph scales, i.e., from large-scale transductive to small-scale but challenging inductive reasoning tasks. (2) The inference time of MulGA is notably shorter than subgraph-based methods such as GraIL and SNRI, which require explicit enclosing subgraph extraction. This demonstrates the advantage of utilizing connectivity subgraphs in enhancing computational efficiency. (3) The wall time per epoch of MulGA is not particularly fast, mainly because it requires dynamically propagating on connectivity subgraphs with different sizes, which is harder to parallel on GPUs. However, MulGA can efficiently utilize the existing structure of KGs and thus has superior convergence speeds in both transductive and inductive tasks.

4.3 Ablation Study

Effect of Granularity Embeddings

We investigate the effect of different granularity embeddings on MulGA performance and results are presented in Table 4.

We make the following observations: (1) Reasoning only with triple granularity embedding does not yield superior results. This can be attributed to the fact that the correct entities are not located in the one-hop neighborhood of the query entity. To make accurate predictions, it is necessary to leverage more structural information between the target entity and the query entity. (2) Compared with the best results using only a single granularity, MulGA improves MRR by 4.2%-26.4%

on WN18RR, 1.3%-12.5% on WN18RR (V1), 3.9%-18.2% on FB15K-237 (V1), and 3.5%-19.0% on NELL-995 (V1), respectively. (3) For relation path granularity, we observe that the longer the relation path, the better the performance on the WN18RR and FB15K-237 (V1). Nevertheless, on WN18RR (V1) and NELL-995 (V1), the best performance does not always correspond to the longest relation path. The main reason is that stacking too many GNN layers could cause over-smoothing, i.e., there is no obvious difference between the positive and negative entities.

Furthermore, we need to determine whether the oversmoothing leads to decreased performance on NELL-995 (V1) and WN18RR (V1). To quantitatively measure the smoothness of representation, we employ the Mean Average Distance

(MAD) [Chen et al., 2020a], which depicts the smoothness by calculating the mean of average distances between two nodes. For all queries in the validation and test set, we calculate the average of the sum of MAD, namely MAD, between the positive entity and other candidate entities, and results are presented in Table 5. Since training is performed on GS, the smoothing on validation set is more representative. Our findings reveal that the smoothness of MulGA-rp-i gradually increases as the relation path length i grows, raising the risk of over-smoothing. Moreover, Table 5 indicates that applying proposed self-attention mechanism can alleviate over-smoothing. Specifically, on NELL-995 (V1) test set, the MAD of MulGArp-6 is 0.645, whereas, the MAD of MulGA is 1.11.

Effect of Merging Operations

Regarding the merging process, we compare the common operations of sum, max, mean, and concat with our proposed SAMmechanism. The results, shown in Table 6, show that compared with the best results from the common merging operations, MRR is improved by 1.0%, 2.8%, and 4.7% on WN18RR (V1), FB15K-237 (V1) and NELL-995 (V1) datasets, respectively, when using our proposed SAM mechanism. The substantial improvement in performance with SAM

mechanism is the result of considering the unique features in each granularity through adaptive weight assignment.

5 RelatedWork

We give a brief overview of different types of KGR methods. (1) KGE-Based (Triple-based) Methods: Such methods generally treat relations as operations between head and tail entities in a vector space to learn entity-specific embeddings, such as addition for TransE [Bordes et al., 2013], rotation for RotatE [Sun et al., 2019], and other complex transformations [Zhang et al., 2019]. (2) Relation PathBased Methods: Relation paths have richer local structural features than triples, and can provide more clues for KGR to infer missing triples. Relation path-based methods use multi-hop relation paths between head and tail entities directly. NBFNet [Zhu et al., 2021], RED-GNN [Zhang and Yao, 2022], and A*Net [Zhu et al., 2023] use the generalized Bellmanford algorithm [Bellman, 1958] to compute relation path representations between two entities to learn entity-independent representation. Some relation path-based KGR models also learn logical rules as a form of generalized relation path between two entities [Meilicke et al., 2018; Yang et al., 2017; Sadeghian et al., 2019; Qu et al., 2020]. (3) Subgraph-Based Methods: Some subgraph-based methods extend traditional GNNs by further considering the relational information in the whole KGs. RGCN [Schlichtkrull et al., 2018] aggregates relation-specific transformation matrices with neighborhood information. CompGCN [Vashishth et al., 2019] instead utilizes composition operators to jointly embed entities and relations in KGs. Moreover, GraIL [Teru et al., 2020], SNRI [Xu et al., 2022], and CoMPILE [Mai et al., 2021] strive to explicitly extract enclosing subgraphs, utilizing them to derive entity-independent relational semantics.

6 Conclusion

In this paper, we propose MulGA, which can efficiently produce high-quality multi-granularity embeddings of all entities for KGR. This is realized by adopting a hierarchical approach in modeling KGs structures via connectivity subgraphs, then proposing a multi-granularity message-passing module to efficiently obtain different granularity embeddings, and finally designing the SAM mechanism to facilitate adaptively assignment of weights to different granularity embeddings. Empirical results show that MulGA achieves new state-of-the-art KGR performance in both transductive and inductive settings.

Acknowledgments

We thank the reviewers for their insightful comments. This work was supported by National Science Foundation of China (Grant Nos.62376057) and the Start-up Research Fund of Southeast University (RF1028623234). All opinions are of the authors and do not reflect the view of sponsors.