Progressive Prefix-Memory Tuning for Complex Logical Query Answering on Knowledge Graphs

Xingrui Zhuo, Shirui Pan, Jiapu Wang, Gongqing Wu, Zan Zhang, Rui Li, Zizhong Wei, Xindong WuIJCAI 2025 · DOI · OpenReview

TL;DR

This paper introduces Progressive Prefix-Memory Tuning (PPMT), a novel framework designed to improve how Pre-trained Language Models (PLMs) answer complex logical queries on knowledge graphs. PPMT tackles the "impossible language" problem in serialized queries by using a Prefix-Memory Rectification (PMR) mechanism to clean up query segments and a progressive fine-tuning strategy to better capture logical semantics, leading to significant performance gains.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are powerful tools for representing structured facts, but answering complex logical queries (KGCQA) over them is challenging. While Pre-trained Language Models (PLMs) have shown promise in this area due to their ability to understand query semantics, they struggle with "impossible language" – the disordered syntax and fragmented contexts that arise when complex logical queries are serialized into plain text. This noise hinders PLMs' ability to grasp the true logical meaning, leading to errors. Existing methods often try to mitigate this by adding prompt tokens, but this can further fragment the context. The paper aims to address this by directly rectifying the "impossible language" within serialized queries before or during the PLM's processing.

Methods

The core of the proposed solution is the Progressive Prefix-Memory Tuning (PPMT) framework, which has two main components:

  1. Prefix-Memory Rectification (PMR) Mechanism: This mechanism is embedded within the self-attention blocks of a PLM. It uses specific prefixes to access "memory stores" containing rectification parameters. These parameters are designed to "polish" the language segments of entities, relations, and queries by correcting textual noise. Essentially, it's a way to fine-tune the PLM's internal representations to be more robust to the imperfections of serialized queries. The PMR mechanism involves trainable memory vectors and specific linear layers to scale and translate encoding results, aiming to rectify local noise.
  2. Progressive Fine-Tuning Strategy: After the PMR mechanism polishes the query, a progressive fine-tuning strategy is employed. This strategy optimizes the model in stages, first focusing on the query graph embedding (which captures richer logical context) and then using knowledge translation constraints to guide conditional gradient updates. This approach helps the model learn logical semantics more effectively and corrects potential biases introduced by the inductive logical context. The fine-tuning process involves two loss functions: one for query graph embedding ($L_g$) and another for knowledge translation embedding ($L_k$), with a KL divergence term used to balance them.

Datasets

The experiments were conducted on two widely used KGCQA benchmarks:

  • FB15k-237
  • NELL-995

These datasets were pre-processed by [Ren et al., 2020]. The paper also mentions training and evaluation across five fundamental query types (1p, 2p, 3p, 2i, and 3i) and a broader range of nine query types (1p, 2p, 3p, 2i, 3i, ip, pi, 2u, and up).

Key Insights and Ideas

  • "Impossible Language" is a Real Bottleneck: The paper clearly demonstrates that the way complex logical queries are serialized into text creates significant noise that degrades PLM performance, even for models like ChatGPT. This highlights a fundamental challenge in applying PLMs to structured reasoning tasks.
  • Prefixes as Contextual Polishers: The idea of using specific prefixes to access memory-based rectification parameters is novel. It suggests that by conditioning the self-attention mechanism with learned "prefix embeddings," we can guide it to selectively apply noise-correction strategies tailored to entities, relations, and the overall query.
  • Progressive Fine-Tuning for Robustness: The multi-stage fine-tuning approach, which balances direct query understanding with knowledge translation constraints, is crucial. It prevents the model from over-relying on potentially noisy direct interpretations and encourages a more robust understanding of underlying logical structures.
  • Memory Matrices Outperform Simple Prefixes: Ablation studies suggest that the memory matrices, which store rectification parameters, offer greater improvement than simple prefix tokens alone. This implies that finer-grained, spatially-aware adjustments are more effective at noise reduction.

Key Results

The PPMT framework achieved significant improvements over state-of-the-art baselines on both FB15k-237 and NELL-995 datasets.

  • Superior Performance: PPMT consistently outperformed other methods in terms of average HR@3 and MRR.
  • Effectiveness of Components: Ablation studies showed that removing the PMR mechanism (prefix tokens or memory matrices) or the progressive fine-tuning strategy led to performance degradation, confirming the importance of each component. The progressive fine-tuning strategy, particularly the $L_g$ component, was found to be critical.
  • Adaptability: The framework demonstrated adaptability across different BERT-based backbones (BERT, Distil-BERT, RoBERTa), indicating its generalizability.

Limitations and Future Work

  • Memory Size Optimization: The optimal size of the memory matrices (S) varied across datasets, suggesting that finding the ideal size might require dataset-specific tuning. The paper explored a range of S values and found improvements within specific ranges for each dataset.
  • FFN Integration: While the paper shows that fine-tuning the Feed Forward Network (FFN) module enhances performance by integrating pre-trained information with memory parameters, further analysis of different FFN combinations could be explored.
  • Adaptability to Other PLMs: While tested with BERT variants, the paper suggests exploring adaptability to other pre-trained language models.

The paper's contribution lies in providing a robust solution to the "impossible language" problem in PLM-based KGCQA, paving the way for more reliable logical reasoning over knowledge graphs.

Summary updated

Abstract

Conducting complex logical queries over knowledge graphs remains a significant challenge. Recent research has successfully leveraged Pre-trained Language Models (PLMs) to tackle Knowledge Graph Complex Query Answering (KGCQA) tasks, which is attributed to PLMs' ability to comprehend logical semantics of queries through context learning. However, existing PLM-based KGCQA methods usually overlook the harm of disordered syntax or fragmented contexts within a serialized query, posing the problem of “impossible language” to limit PLMs in grasping the logical semantics. To address this problem, we propose a Progressive Prefix-Memory Tuning (PPMT) framework for KGCQA tasks, which effectively rectifies erroneous segments in serialized queries to assist PLMs in query answering. First, we propose a prefix-memory rectification mechanism embedded in a PLM module. This mechanism assigns rectification parameters in memory stores to polish the language segments of entities, relations, and queries through specific prefixes. To further capture the logical semantics in queries, we design a progressive fine-tuning strategy, which optimizes our model through a conditional gradient update process guided by knowledge translation constraints. Extensive experiments on widely used KGCQA benchmarks demonstrate the significant superiority of PPMT in terms of HR@3 and MRR. Our codes are available at https://github.com/lazyloafer/PPMT.
BibTeX
@inproceedings{zhuo2025progressive,
  author = {Xingrui Zhuo and Shirui Pan and Jiapu Wang and Gongqing Wu and Zan Zhang and Rui Li and Zizhong Wei and Xindong Wu},
  title = {{Progressive Prefix-Memory Tuning for Complex Logical Query Answering on Knowledge Graphs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/413},
}
Figure