Fact Verification on Knowledge Graph via Programmatic Graph Reasoning (2025)

Abstract: Fact verification on knowledge graphs (KGs) uses the structured representation of entities and relations as evidence for validating claims. Previous methods for KG-based fact verification predominantly use natural language inference (NLI) models to predict entailment between claims and KG triples, based on implicit reasoning. We propose Programmatic Graph Reasoning (PGR), a novel framework that integrates large language models (LLMs) for fact verification on KGs. PGR explicitly encodes the reasoning process as a graph reasoning program composed of predefined functions to verify claims step by step. These functions are executed sequentially for graph reasoning and final result prediction. By making the graph reasoning process explicit, PGR ensures more precise and transparent reasoning steps compared to implicit methods. Experimental results on the FactKG dataset demonstrate that PGR achieves state-of-the-art performance with 86.82% accuracy, outperforming all the baseline models. Further analysis confirms the interpretability and effectiveness of our method in handling complex graph reasoning.

## introduction fact verification has become an essential task in natural language processing (nlp) due to the growing prevalence of misinformation across various platforms. fact verification based on knowledge graphs (kgs) leverages the structured representation of entities and relationships as evidence to support or refute claims @xcite . existing approaches typically retrieve relevant triples from the kg and use them as evidence to verify the claim. these methods follow an nli-based reasoning paradigm, employing natural language inference (nli) models @xcite to predict the entailment between the evidence and the claim. recent advances in large language models (llms) have demonstrated remarkable capabilities in natural language understanding and reasoning @xcite @xcite . existing methods @xcite also leverage llms to improve accuracy in kg-based fact verification. by utilizing the in-context learning capabilities of llms, these approaches can achieve high accuracy in few-shot settings. the reasoning process in these methods resembles nli models, where the llm verifies the claim using an evidence-claim pair. the reasoning process for kg-based fact verification involves logical reasoning over subgraphs in the knowledge graph that correspond to the given claim. this graph reasoning process can be performed step by step, similar to the reasoning approach used by human fact-checkers @xcite . considering the complexity of graph reasoning involving entities, relations, and logical structures, a programmatic approach can provide an efficient way to manage multi-variable and multi-step operations, ensuring precise graph reasoning. we propose a novel approach called programmatic graph reasoning (pgr), which leverages the language understanding and programming capabilities of llms for fact verification on kgs. in this framework, we define the fundamental functions-match, search, and verify-with clearly specified input-output formats and functionalities. pgr consists of two main steps: program generation and graph reasoning. in program generation, a graph reasoning program is generated for claim verification, constructing reasoning steps using the defined functions. in graph reasoning, the program is executed step by step to predict the final verification result. unlike nli-based methods with implicit reasoning, pgr explicitly represents the reasoning process as a structured program. this explicit representation not only enhances interpretability but claim : alfredo zitarrosa was born in a city and the leader is called raul fernando sendic rodriguez. program generation llm f1 search(('alfredo_zitarrosa', 'born in', 'unknown')) knowledge graph f2 search(('unknown', 'leader', 'raúl_fernando_sendic_rodríguez')) @xmath0, 'in', entity_ 2)) f4 verify(result_1) @xmath1, 'country', 'uruguay']] @xmath2, compared to implicit reasoning. we evaluated our proposed method on the fac-tkg dataset @xcite . the experimental results show that our approach achieves the state-ofthe-art result across all model evaluations, reaching 86.82% accuracy. in the few-shot model comparison, pgr consistently outperforms others, obtaining the highest accuracy across all five claim types in the dataset, further validating the effectiveness of the our method. additionally, we analyzed the interpretability of pgr and the effectiveness of the generated programs, underscoring the advantages of explicit reasoning in enhancing both predictive performance and explainability. ## related work fact-checking with knowledge graphs (kgs) has emerged as a promising approach to verify the veracity of claims by leveraging structured knowledge. factkg @xcite ) is a fact verification dataset built on dbpedia @xcite , a large-scale general-purpose knowledge graph. the claims in factkg are generated based on the webnlg corpus @xcite , with additional data generation steps to create more diverse claims that incorporate more kg triples, requiring complex reasoning for verification. existing methods for fact-checking on factkg include bert-based @xcite approaches and gear @xcite , a multi-evidence reasoning framework. gear has been adapted and optimized for kg-based fact verification, improv-ing its performance in factkg dataset @xcite . the rapid development of large language models (llms) has significantly enhanced both language understanding and logical reasoning capabilities @xcite @xcite . the advent of gpt-4 @xcite further extends the applications of llms to a wide range of tasks, including those related to reasoning and knowledge graphs @xcite @xcite . recent research has explored the use of llms in kg-based fact verification, particularly through few-shot learning approaches. kg-gpt @xcite , similar to structgpt @xcite , integrates llms with few-shot learning for fact verification on kgs. these methods demonstrate that llms can be effectively applied to kg-based tasks and show strong reasoning capabilities in few-shot settings, offering new possibilities for improving performance in this domain. large language models (llms) have demonstrated remarkable versatility in solving various tasks including reasoning @xcite through in-context learning @xcite , where only a few prompt examples are required to guide the model. programfc @xcite introduces a novel fact-checking approach that leverages llms to generate programs for claim verification. this method decomposes the verification of a complex claim into multiple sub-claims, which are verified independently in a stepwise manner. such a multi-step reasoning strategy closely resembles the human fact-checking process @xcite . in addition to program-based reasoning, the reasoning performance of llms can be significantly enhanced through chain-of-thought (cot) prompting and knowledge-grounded reasoning @xcite @xcite , which enables the model to perform more accurate multi-step reasoning. recent researches have shown that decomposing multi-step reasoning tasks using llms not only improves accuracy but also offers stronger interpretability, making the verification process more transparent and comprehensible @xcite . ## programmatic graph reasoning this section presents our proposed method, programmatic graph reasoning(pgr), for fact verification on kg, which defines essential functions for retrieving and validating evidence from a knowledge graph. the methodology focuses on the definition of functions, the generation of graph reasoning programs, and the execution of programs for accurate fact verification. figure 1 illustrates the complete process of the proposed pgr framework for kg-based fact verification. the pgr framework consists of two main components: 1. program generation: given a claim, pgr generates a structured program composed of graph reasoning functions that represent the reasoning process. 2. graph reasoning: the generated program is executed to perform step-by-step graph reasoning, with each function operating on kg to verify the claim. ## conclusion in this paper, we propose a novel approach, programmatic graph reasoning (pgr), for kg-based reasoning. experimental results on the factkg dataset for kg-based fact verification show that pgr achieves the highest accuracy among competing methods. pgr converts the claim verification process into a step-by-step graph reasoning process by generating executable programs composed of fundamental graph reasoning functions. our approach effectively handles complex graph reasoning tasks while maintaining strong interpretability. the program generation paradigm offers high generalizability. by leveraging llms with fewshot prompting, pgr can perform graph reasoning tasks with minimal training resources. unlike nli approaches, pgr provides an explicit reasoning chain in the form of graph-based logic, ensuring a more interpretable and accurate reasoning process. pgr introduces a modular design for kg-based reasoning tasks, offering a promising foundation for future extensions. the modularity of pgr enables flexible adaptation by reconfiguring the combination of core functions and customizing the handling of intermediate output. in future work, we plan to explore the applicability of this framework to more challenging reasoning settings.