Efficient and Exact Global Attention on Latent Summaries for Knowledge Graph Reasoning

1 Introduction

Knowledge graphs (KGs) underpin many real-world applications, including recommender systems [Chicaiza and D´ıaz,

∗Corresponding authors.

2021] and question answering [Wang et al., 2024]. Despite their large scale, most KGs are incomplete, which motivates the need for effective reasoning methods to infer missing links. Early approaches, such as TransE [Bordes et al., 2013] and RotatE [Sun et al., 2019], represent entities as independent vectors and model relations through simple geometric transformations. More recently, research has shifted toward graph neural networks (GNNs), including RGCN [Schlichtkrull et al., 2018] and CompGCN [Vashishth et al., 2020]. By explicitly modeling graph structure, GNNs allow entities to aggregate information from their local neighborhoods, enabling the capture of multi-hop relational patterns that are crucial for accurate link prediction.

Despite these advantages, standard GNNs face two wellknown challenges: their message-passing mechanism limits information exchange between disconnected nodes [Liu et al., 2024], and over-squashing, where information from distant nodes becomes distorted [Alon and Yahav, 2021]. To overcome these locality constraints, recent work has introduced global attention mechanisms that allow each node to attend to all others. However, full self-attention scales quadratically with the number of nodes, making it impractical for large graphs. To address this, state-of-the-art methods [Liu et al., 2024; Li et al., 2025a] commonly adopt linear attention mechanisms [Katharopoulos et al., 2020], reducing the computational cost to linear complexity. This efficiency comes at a cost: linear attention approximates the softmax operation and discards query magnitude information, often leading to overly smooth attention distributions [Fan et al., 2025]. Such smoothing weakens the model's ability to focus on highly relevant entities and makes it harder to distinguish correct triplets from hard negative samples in knowledge graph reasoning tasks. Furthermore, the behavior of linear attention varies with graph size, making it sensitive to changes in the node set during inductive inference.

In this work, we propose a different paradigm: instead of approximating attention over the full graph, we compress the graph context to enable exact attention. We introduce LaGR (Latent Graph Reasoning), a framework that resolves the trade-off between efficiency and expressivity. Our key observation is that although the number of nodes N can be large, the global semantic context of a KG often lies in a much lower-dimensional space. Building on this insight, LaGR projects node representations into a small set of M latent summaries through weighted aggregation, where M ≪N. This latent space is sufficiently compact to support exact Softmax attention for modeling global correlations. After the attention and feed-forward computations, the resulting global context is broadcast back to the original nodes. As a result, LaGR preserves linear computational complexity with respect to N while maintaining robustness to variations in graph size, which linear attention methods often lack. For clarity, Figure 1 compares the architectures of standard GNNs, linear attention models, and LaGR.

We further observe that prior work typically fuses global and local information using a single trainable scalar shared across all nodes (e.g., α · global + (1 - α) · local) [Li et al., 2025a]. This uniformweighting overlooks the fact that different nodes may require different levels of global context. To address this limitation, we introduce a node-adaptive residual fusion strategy that dynamically adjusts the contribution of global context for each node through a learned projection over local and global features. This design allows LaGR to preserve local structural patterns captured by GNNs while selectively incorporating global signals to support long-range reasoning. Our contributions are summarized as follows:

• We propose LaGR, which offers a superior efficiencyeffectiveness trade-off compared to linear attention approaches, mitigating over-smoothing and scaledependent effects while maintaining linear computational complexity.
• We introduce a node-adaptive residual fusion strategy that replaces uniform scalar interpolation with a dynamic, node-specific weighting mechanism, improving feature expressiveness.
• We conduct extensive experiments on knowledge graph reasoning benchmarks in both transductive and inductive settings. Our results demonstrate that LaGR consistently outperforms existing GNN and efficient transformer baselines.

2 RelatedWork

Knowledge graph reasoning methods can be categorized by how they model interactions between entities and relations. Embedding-based approaches, such as TransE [Bordes et al., 2013], DistMult [Yang et al., 2015], and RotatE [Sun et al., 2019], represent relations as translation operations in a vector space. Path-based methods propagate entity representations through local neighborhoods using message passing, as in CompGCN [Vashishth et al., 2020], NBFNet [Zhu et al., 2021], RED-GNN [Zhang and Yao, 2022], AdaProp [Zhang et al., 2023], and ULTRA [Galkin et al., 2024]. However, these approaches inherit well-known limitations of message-passing networks, including missing connected paths and over-squashing [Alon and Yahav, 2021]. Transformer-based methods, including HittER [Chen et al., 2021], N-Former [Liu et al., 2022], and SAttLE [Baghershahi et al., 2023], typically convert graph structures into sequential representations during encoding, which may lead to the loss of important structural information.

More recently, hybrid architectures that combine GNNs and Transformers, such as KnowFormer [Liu et al., 2024] and DuetGraph [Li et al., 2025a], have been proposed to integrate local structural information with global graph context. To enable scalable global modeling, these methods often replace Softmax attention with linear attention mechanisms [Katharopoulos et al., 2020]. While efficient, this substitution can result in over-smoothed feature representations and scale-dependent shifts in attention entropy. In contrast, we propose LaGR, which addresses these limitations while preserving scalability.

Notably, several existing methods also adopt a pooling-processing-unpooling paradigm for modeling KGs, including DiffPool [Ying et al., 2018], Graph U-Nets [Gao and Ji, 2019], and KGPCL [Li et al., 2025b]. These approaches reduce graph size by pruning paths, selecting representative nodes, or merging concepts, thereby transforming the original graph into a compact subgraph. However, such transformations remain constrained by the underlying graph structure and continue to inherit the limitations of message-passing networks. In contrast, our approach learns the pooling projection without relying on adjacency information as prior knowledge, enabling more effective modeling of global context.

3 Preliminary

3.1 Knowledge Graph

A KG is formally represented as G = (V, E,R), where V denotes the set of entities, R the set of relations, and E the set of factual triplets. Each triplet is defined as (h, r, t) ∈ E, where h, t ∈ V and r ∈ R.

3.2 Knowledge Graph Reasoning

The goal of knowledge graph reasoning is to infer missing elements in query triplets. In this work, we focus on tail prediction, where queries take the form (h, r, ?). Following common practice, head prediction queries (?, r, t) are converted into tail prediction by introducing an inverse relation r-1 , yielding the equivalent form (t, r-1 , ?).

3.3 Linear Attention

Linear attention is based on the assumption that the exponential function in Softmax attention can be approximated by a product of kernel functions [Fan et al., 2025]. This reformulation decomposes the attention computation and reduces its complexity to linear time. As a representative graph embedding method, SGFormer [Wu et al., 2023] implements linear attention as follows:

Here, N denotes the number of nodes, diag(·) constructs a diagonal matrix from its input, and ·⊤ denotes matrix transposition. Q, K, and V represent the query, key, and value matrices, respectively, with Q and K normalized by their Frobenius norms.

4 Methodology

As illustrated in Figure 2, LaGR processes the KG using both a local encoder and a global encoder in parallel, and then integrates their outputs through a node-adaptive residual fusion module. This architecture can be stacked across multiple layers. Section 4.1 describes the global encoder and analyzes its computational efficiency. Section 4.2 explains how the global context is incorporated into local representations via node-adaptive residual fusion. Section 4.3 presents the training objective of LaGR.

4.1 Global Encoder

To model long-range dependencies and the global semantic context that local message passing often fails to capture, we introduce a global encoder. As shown in Figure 2, this module follows a compress-attend-expand design that decouples the cost of global interaction from the number of graph nodes. It consists of three sequential steps: summarization, exact latent attention, and broadcasting.

Summarization. The summarization step projects N node features into M latent summaries, where M ≪ N. Let H ∈ RN×d denote the original node representations, where d is the feature dimension. Using projection matrices W1 ∈ Rd×d and W2 ∈ Rd×M , we compute a weight matrix:

where σ(·) denotes a non-linear activation, and bias terms are omitted for simplicity. A column-wise softmax is then applied to normalize the weights, and the node features are aggregated into M latent summaries:

Exact latent attention. We next apply standard attention within this compact latent space, consisting of a softmaxbased attention mechanism followed by a feedforward network [Vaswani et al., 2017]. Operating in the reduced space allows exact attention while keeping computation efficient.

Broadcasting. Finally, the broadcasting step distributes the refined global information back to individual nodes using a mirrored projection. With projection matrices W3 ∈ Rd×d and W4 ∈ Rd×M , we compute:

In contrast to summarization, a row-wise softmax is applied to obtain node-specific mixing weights. The final global features for each node are then given by:

where ˆH ∈ RM×d denotes the output of the latent attention module.

Theoretical Analysis of Latent Size

The Johnson-Lindenstrauss Lemma [Johnson et al., 1984] states that N points can be projected into a space of dimension k = Ω( log N ϵ2 )while preserving pairwise distanceswithin a factor of (1 ± ϵ). This result suggests that the geometric structure of a KG can be preserved in a latent space whose dimension M grows logarithmically, rather than linearly, with graph size. Under this paradigm, the sensitivity of model performance to changes in graph scale is bounded by O(logN), yielding improved robustness in inductive reasoning.

From an efficiency perspective, M should be as small as possible. However, recent theoretical studies on deep sequence models highlight the risk of rank collapse [Joseph et al., 2025], where representations degenerate toward a rankone subspace, severely limiting expressiveness. When M < d, latent summarization becomes a lossy compression that discards orthogonal feature components, making distinct entities increasingly indistinguishable. This observation suggests a theoretical lower bound of M ≥ d to preserve sufficient representational capacity.

We next formalize LaGR as a learnable low-rank approximation of the full-graph Softmax attention matrix to characterize constraints on the projection matrix. Let A ∈ RN×N denote the ideal all-pairs attention matrix, where Aij measures the relevance of entity j to entity i. LaGR approximates this interaction through a latent bottleneck:

Because attention is computed in an RM×M latent space, the rank of ˜ A is bounded by M. According to the EckartYoung-Mirsky Theorem [Golub et al., 1987], the optimal rank-M approximation of A with respect to the Frobenius norm ||A- ˜ A||F is achieved when the columns of ˜ Wsum align with the top-M singular vectors of A. Since these singular vectors are unavailable during training, we instead encourage the projection to implicitly capture distinct principal components across latent summaries. In this view, latent summaries are not treated as simple clusters but as basis vectors spanning the principal semantic manifold of the graph.

To support this objective, we introduce an auxiliary orthogonality regularization that promotes diversity among latent summaries by penalizing correlations in the projection weights:

Complexity Analysis

This paragraph analyzes the computational efficiency of different approaches for modeling global graph context. For clarity, we omit the feedforward network, which is shared by all methods. Standard softmax attention computes pairwise interactions between all nodes, leading to a quadratic complexity of O(N 2d). To scale to large KGs, linear attention methods approximate softmax attention using kernel-based formulations and the associativity of matrix multiplication, reducing the complexity to O(Nd2 ). In LaGR, both the summarization and broadcasting modules have a complexity of O(Nd2 + NMd), while exact attention in the latent space costs O(M 2d). Since M ≪ N, the overall complexity of the global encoder is dominated by the projection operations, resulting in a total complexity of O(Nd2 +NMd).

4.2 Node-Adaptive Residual Fusion

The need for global context varies across the graph. Some entities can be accurately represented using only their immediate neighbors, while others are affected by over-squashing or missing paths and, therefore, require broader contextual information. To account for this heterogeneity, we dynamically adjust the contribution of global features for each node through a mutual attention mechanism implemented with a fully connected layer and a residual connection. Let Hglob and Hloc be the global and local feature matrices, respectively. The fused representations are computed as:

where ∥ denotes feature concatenation along the column dimension, andWproj ∈ R2d×d is a learnable projection matrix.

Expressivity Analysis

Here, we compare our node-adaptive residual fusion strategy with scalar interpolation [Li et al., 2025a], which combines global and local features as

where α ∈ [0, 1] is a learnable scalar obtained via a sigmoid function.

For a direct comparison, we rewrite our fusion operation in Equation 8 asHproj = Hloc(Wb + I) + HglobWa, (10)

where Wa ∈ Rd×d and Wb ∈ Rd×d are column partitions of the projection matrixWproj, such that (Wa∥Wb) =Wproj.

Let Hscal and Hproj denote the hypothesis spaces induced by Hscal and Hproj, respectively. Since scalar interpolation is a special case of the projection-based formulation, it follows that Hscal ⊂ Hproj. This shows that our method strictly generalizes the expressiveness of scalar interpolation.

4.3 Training Objective

At the output layer, the final node representation is mapped to a scalar score using a multi-layer perceptron (MLP) f : Rd → R, which represents the probability that a candidate entity is a valid answer. Given a query triplet (h, r, ?) and a candidate tail entity e, we denote the normalized score as s(e|h, r) ∈ [0, 1]. Model parameters are trained by minimizing a negative sampling loss for each fact (h, r, t):

where Nhr = {e ∈ V|(h, r, e) /∈ E} is the set of negative candidates for the query (h, r, ?).

The final training objective combines the negative sampling loss with the orthogonality regularization:

5 Experiments

This section first describes the experimental setup. We then present a comprehensive evaluation that (1) assesses LaGR's performance on both inductive and transductive reasoning tasks, (2) analyzes the contribution of its key components, (3) evaluates training and inference efficiency, (4) examines score distributions under different attention mechanisms, and (5) studies the model's sensitivity to the hyperparameter M, which determines the latent summary size.

5.1 Experimental Setup

Datasets. We evaluate LaGR on both transductive and inductive benchmarks. For the transductive setting, we use four KGs of varying sizes: FB15k-237 [Toutanova and Chen, 2015], WN18RR [Dettmers et al., 2018], NELL-995 [Xiong et al., 2017], and YAGO3-10 [Mahdisoltani et al., 2013]. In the inductive setting, the training and test graphs contain disjoint entity sets while sharing the same relations. We adopt inductive benchmarks derived from FB15k-237, WN18RR, and NELL-995, each split into four variants, yielding a total of 12 subsets. For all datasets, we use the standard data splits established in prior work [Liu et al., 2024].

Baselines. We compare LaGRagainst a diverse set of representative methods, including embedding-based models, pathbased approaches, transformer-based models, hybrid methods, and other implementations such as meta-learning, geometric representation learning, and regularization-based optimization. The complete list of baselines is reported in Tables 1 and 2.

Evaluation metrics. We measure performance using standard metrics for knowledge graph reasoning: Mean Reciprocal Rank (MRR) and Hit Rate at k (H@k with k = 1, 10), where higher values indicate better performance. Following common practice, we report results under the filtered setting [Bordes et al., 2013], which removes known true triples from the ranking candidates.

5.2 Performance

Following DuetGraph [Li et al., 2025a], we adopt a coarse-tofine optimization strategy. Specifically, a pre-trained coarse model partitions entities into high- and low-score subsets, after which the proposed model refines the final rankings within each subset. For all baseline methods, we report results as published in their original papers.

Inductive datasets. Table 1 reports performance comparisons on twelve inductive benchmark subsets. Across these settings, LaGR consistently achieves the best or near-best results on almost all evaluation metrics. In particular, on FB15k-237, LaGR outperforms existing methods across all versions, improving upon the strongest baseline, DuetGraph. Although some methods, such as AdaProp and DuetGraph, perform competitively on specific metrics (e.g., Hits@10 on WN18RR v2 and NELL-995 v4), LaGR demonstrates more stable performance across datasets and splits. These results indicate that modeling global context through a fixed, compact latent summary space is effective for inductive knowledge graph reasoning.

Transductive datasets. Table 2 summarizes results on four transductive benchmarks. LaGR achieves state-of-the-art performance on most metrics across all datasets. A clear pattern is that hybrid methods, including KnowFormer, DuetGraph, and LaGR, generally outperform single-paradigm methods. For example, on FB15k-237, LaGR attains an MRR of 0.458, exceeding both embedding-based models such as HousE (0.361) and path-based methods such as AdaProp (0.417). On the larger YAGO3-10 dataset, LaGR maintains strong performance, achieving the highest MRR (0.636) and Hits@1 (56.8). While DuetGraph achieves the best Hits@10 on WN18RR and NELL-995, LaGR remains the strongest overall in terms of ranking accuracy, as reflected by MRR. These results demonstrate the effectiveness and robustness of LaGR in transductive reasoning settings.

5.3 Ablation Study

Table 3 reports a component-wise ablation study on the FB15k-237 inductive subsets, examining the impact of key design choices in LaGR. Across all subsets and evaluation metrics, the original LaGR configuration (first row) achieves the strongest overall performance.

Modeling global context through latent summaries consistently outperforms linear attention approximation (Appr), indicating the benefit of projecting a dynamic graph into a fixed latent space for inductive reasoning. The role of orthogonality regularization is particularly evident: removing this constraint (denoted by ·) leads to a noticeable performance degradation, especially on Hits@10. For example, on v3, Hits@10 drops from 70.4 to 67.9 without regularization, suggesting that promoting diverse and non-redundant latent summaries is important for effective global context modeling.

In addition, the node-adaptive projection (Proj) strategy shows strong generalization across settings. It consistently outperforms scalar interpolation (Scal), regardless of whether global information is captured through latent summaries or linear attention approximation. This result supports the use of a learnable, node-specific fusion mechanism over a uniform weighting scheme when integrating local and global features.

Overall, these findings validate the architectural design of LaGR and highlight the complementary roles of latent global modeling and adaptive projection in improving inductive reasoning performance.

5.4 Efficiency Analysis

Table 4 compares the computational efficiency of LaGR with two hybrid methods on transductive datasets of different scales. Since these methods reach their best performance within a similar number of epochs and do not employ early stopping, we report the training time per epoch.

Overall, LaGR is consistently more efficient in both model size and runtime. It uses the fewest trainable parameters on three of the four datasets, with about a 23% reduction on FB15k-237 and NELL-995 compared to the baselines. This compact design leads to clear runtime benefits: LaGR achieves the fastest training per epoch and the lowest inference time across all benchmarks. On FB15k-237, it cuts training time by over 60% and reduces inference time by nearly half relative to DuetGraph. Importantly, LaGR retains this advantage on the large-scale YAGO3-10 dataset, showing that its performance gains come from a more efficient and lightweight design rather than increased computational cost.

5.5 Analysis of Score Over-Smoothing

To assess the extent of over-smoothing, we analyze the variance of output score distributions on the four inductive subsets of FB15k-237. In this analysis, over-smoothing refers to the collapse of representations into a narrow range, which results in similar prediction scores for different candidate triples. We compute the variance of these scores as an indicator of the model's ability to produce a discriminative distribution in which the ground-truth entity is separated from negative candidates.

As illustrated in Figure 3, LaGR consistently produces higher score variance than all hybrid baseline methods across the evaluated subsets, whereas KnowFormer yields the lowest LaGR DuetGraph KnowFormer variance. Notably, on the v2 and v3 subsets, LaGR achieves variances of 6.6 and 8.3, exceeding those of the second-best model by 424.9% and 164.1%, respectively. These results suggest that LaGR better preserves feature distinctiveness, alleviating over-smoothing in deep graph reasoning models and contributing to more reliable ranking performance.

6 Conclusion

This paper proposes LaGR, a novel paradigm for capturing global interactions in knowledge graphs with linear computational complexity in the number of nodes. LaGR addresses the over-smoothing and scale-dependent shifts in attention entropy observed in prior linear attention approaches. In addition, we introduce a node-adaptive residual fusion strategy for integrating global and local representations, which improves the expressiveness of the fused features. Extensive experiments demonstrate that LaGR achieves state-of-the-art performance while remaining efficient and robust across diverse settings.

Acknowledgments

This work is supported by the Solfeggio ear training intelligent robot and cloud platform research and development project for music education (No.2024CXY0102), the 3D visualization digital twin integrated control system (No.2023CXY0111), the public technology service platform project of Xiamen City (No.3502Z20231043) and Fujian Provincial Science and Technology Major Project (No.2024HZ022003)