Multi-hop Knowledge Base Question Answering (KBQA) aims to find answer entities in the knowledge base that are multiple hops away from the entities in the question. Information retrieval-based (IR-based) methods extract a pivotal subgraph from the entire KB to locate candidate answers and then evaluate their plausibility through semantic matching with the question. However, we observed that the extracted subgraphs often include nodes that are weakly related or irrelevant to the question. Without a proper node filtering mechanism, the number of irrelevant nodes grows as the number of hops increases, leading to excessive consumption of computational resources. To address these challenges, this study introduces an efficient LLM-based subgraph retrieval method for multi-hop knowledge base question answering, M-ER. The framework leverages Monte Carlo Tree Search (MCTS) to transform subgraph exploration into a tree-structured search process. During the MCTS selection phase, nodes that are highly relevant to the question are prioritized for inclusion in the subgraph, eliminating the need to traverse all nodes in the KB. The framework further incorporates a large language model (LLM) to refine the search direction, ensuring that exploration remains focused on nodes relevant to the question. In addition, selected nodes are quantitatively scored, and these scores are fed back into the node selection process to effectively filter out irrelevant candidates, thereby improving the quality of the subgraph. This mechanism not only narrows the search space but also enhances the overall efficiency of multi-hop KBQA. Experiments on the WebQSP benchmark demonstrate that M-ER achieves 78.88% on the Hits@1 metric, while also improving computational efficiency. These results not only validate the effectiveness of M-ER, but also offer a viable technical path to balance performance and computational efficiency.

Text-based knowledge graph completion methods take advantage of pre-trained language models (PLM) to enhance intrinsic semantic connections of raw triplets with detailed text descriptions. Typical methods in this branch map an input query (textual descriptions associated with an entity and a relation) and its candidate entities into feature vectors, respectively, and then maximize the probability of valid triples. These methods are gaining promising performance and increasing attention for the rapid development of large language models. According to the property of the language models, the more related and specific context information the input query provides, the more discriminative the resultant embedding will be. In this paper, through observation and validation, we find a neglected fact that the relation-aware neighbors of the head entities in queries could act as effective contexts for more precise link prediction. Driven by this finding, we propose a relation-aware anchor enhanced knowledge graph completion method (RAA-KGC). Specifically, in our method, to provide a reference of what might the target entity be like, we first generate anchor entities within the relation-aware neighborhood of the head entity. Then, by pulling the query embedding towards the neighborhoods of the anchors, it is tuned to be more discriminative for target entity matching. The results of our extensive experiments not only validate the efficacy of RAA-KGC but also reveal that by integrating our relation-aware anchor enhancement strategy, the performance of current leading methods can be notably enhanced without substantial modifications.

Reasoning paths are reliable information in knowledge graph completion (KGC) in which algorithms can find strong clues of the actual relation between entities. However, in real-world applications, it is difficult to guarantee that computationally affordable paths exist toward all candidate entities. According to our observation, the prediction accuracy drops significantly when paths are absent. To make the proposed algorithm more stable against the missing path circumstances, we introduce soft reasoning paths. Concretely, a specific learnable latent path embedding is concatenated to each relation to help better model the characteristics of the corresponding paths. The combination of the relation and the corresponding learnable embedding is termed a soft path in our paper. By aligning the soft paths with the reasoning paths, a learnable embedding is guided to learn a generalized path representation of the corresponding relation. In addition, we introduce a hierarchical ranking strategy to make full use of information about the entity, relation, path, and soft path to help improve both the efficiency and accuracy of the model. Extensive experimental results illustrate that our algorithm outperforms the compared state-of-the-art algorithms by a notable margin. Our code will be released at https://github.com/7HHHHH/SRP-KGC.

Autonomous exploration in large-scale environments is impeded by two critical challenges, namely, suboptimal viewpoint selection resulting from inadequate feature extraction and the continuously rising computational costs as the environment expands. Existing methods struggle to simultaneously tackle these dual challenges within cohesive frameworks. In response, we present an efficient autonomous exploration framework with contrastive-driven reinforcement learning. Inspired by human cognitive mechanisms that reinforce crucial information recognition through contrast, our study implements contrastive constraints on nodes of varying utility levels within high-dimensional feature spaces, achieving a decoupling of their latent representations. This capability empowers decision networks to explicitly capture key regional characteristics, thereby enhancing the precision of optimal viewpoint selection. Moreover, to mitigate the issues of backtracking and redundant exploration, we design specialized training rules that enforce effective action constraints, further enhancing viewpoint selection. Additionally, we propose a novel graph rarefaction algorithm to tackle computational costs, simplifying computational complexities while maintaining performance standards. Compared to the state-of-the-art (SOTA) approaches, our method achieves 6.7% shorter path lengths, while also demonstrates robust generalization capabilities through real-world robotic experiments across multiple real-world scenarios.

Sampling from large dataset is commonly used in the frequent patterns (FPs) mining. To tightly and theoretically guarantee the quality of the FPs obtained from samples, current methods theoretically stabilize the supports of all the patterns in random samples, despite only FPs do matter, so they always overestimate the sample size. We propose an algorithm called multiple sampling-based FPs mining (MSFP). The MSFP first generates the set of approximate frequent items ($AFI$), and uses the$AFI$to form the set of approximate FPs without supports (${\mathrm{ AFP}}^{*}$), where it does not stabilize the value of any item’s or pattern’s support, but only stabilizes the relationship$\ge $or$AFI$and${\mathrm{ AFP}}^{*}$, and can successively prune the patterns not contained by the$AFI$and not in the${\mathrm{ AFP}}^{*}$. Then, the MSFP introduces the Bayesian statistics to only stabilize the values of supports of${\mathrm{ AFP}}^{*}$’s patterns. If a pattern’s support in the original dataset is unknown, the MSFP regards it as random, and keeps updating its distribution by its approximations obtained from the samples taken in the progressive sampling, so the error probability can be bound better. Furthermore, to reduce the I/O processes in the progressive sampling, the MSFP stores a large enough random sample in memory in advance. The experiments show that the MSFP is reliable and efficient.

Many studies take sampling to apply fuzzy C-means (FCM) to very large data sets. However, comparing with the plenty algorithms for sampling-based FCM, few research works theoretically study the generalization error. In this article, we take the concept probably approximately correct learning to study it, and define the generalization error as the maximum difference between the empirical risks and the real risks of solutions in solution space. First, we analyze this generalization error under finite solution space, and prove two theorems by Hoeffding's inequality, where one of them relies on a reasonable hypothesis. Then, we discuss the situation in which the solution space is infinite, and propose a theorem and a corollary by another hypothesis, where the results under finite solution space are used in the proofs. Finally, we bound the generalization error from the perspective of the FCM algorithm's convergence, where we take Taylor expansion to transform the risk function to the linear form and estimate the upper bound of its Vapnik-Chervonenkis (VC) dimension. The hypotheses proposed in this article are all intuitive and common phenomena in practice. Our results show the upper bound of the generalization error under the given minimum probability, which can offer insight into the stability of sampling-based FCM and can guide in its application.