Introduction

Knowledge Graphs, such as Wikidata, contain rich relational information between entities and have been widely used as a structured format for storing and representing relational information. With the surge of Large Language Models (LLMs) nowadays (e.g. ChatGPT), there is a rising trend in the research of combining Knowledge Graphs with LLMs in multiple ways to solve various kinds of problems.

In this post, we introduce some of the latest findings where the use of Knowledge Graph is combined with LLMs.

Chain of History (CoH) reasoning

Temporal Knowledge Graph (TKG) is a subset of Knowledge Graphs having some directions and timestamps. This allows capturing how relationships evolve over time or the order in which they occur. It holds significant practical value across various applications. For example, a TKG might show that “Albert Einstein” (entity) “published” (relationship with time) the theory of relativity in “1905” (timestamp). Most advanced research on TKGs mainly focuses on predicting future facts based on given historical facts.

Recent supervised methods primarily rely on Graph Neural Networks (GNNs) to capture structural information (e.g. entities and relationships). They can learn representations for entities and relationships by aggregating information from neighboring nodes in the graph. This helps identify patterns and connections within the TKG. While GNNs capture structure, they might not fully grasp the semantic meaning of entities, relationships, and timestamps in a TKG. They focus on learning patterns from labeled data, which might not translate well to understanding the underlying meaning of the data. Fortunately, with the assistance of LLMs, their capability in this direction has been gradually explored. However, issues still remain. For example, over-complicated historical information may confuse LLMs and make it hard for them to give accurate answers. When you input a large paragraph to LLMs, models may struggle to select useful information and could possibly generate an answer irrelevant to the question.

To address the existing issues, Chain-of-History (CoH) reasoning method for TKG prediction is proposed. Instead of providing LLMs with all histories at once in the traditional approach, CoH provides LLMs with high-order histories (e.g. information not directly related to the query) step-by-step. Specifically, CoH adopts LLMs to explore important high-order history chains step-by-step and reason the answers to the query only based on inferred history chains in the last step.

First-Order Histories

• These are the individual events or pieces of information considered most relevant to answering the query.
• The LLM analyses the provided information and identifies these key elements.

Second-Order Histories

• These are formed by combining the first-order histories in a specific order.
• They represent sequences of events that could have led to the current situation or answer the query. Second-order histories go beyond isolated events and capture the causal relationships between them.

This process continues where chains of first-order histories, forming more intricate event sequences are formed for third-order, fourth-order etc histories.

Extensive experimental results demonstrate the superiority of CoH, and its effectiveness in enhancing the performance of graph-based models for TKG prediction.

Right for Right Response

Knowledge Graph Question Answering (KGQA) methods seek to answer Natural Language questions using the relational information stored in Knowledge Graphs. With the recent advancements of LLMs and their remarkable reasoning abilities, there is a growing trend to leverage them for KGQA. However, existing methodologies have only focused on answering factual questions, such as “In which city was Simone Biles born”. In this case, questions involving commonsense reasoning that real-world users may pose more often, such as “Do I need separate visas to see the ‘Venus of Willendorf’ and attend the Olympics this summer”, are left out.

A verifiable methodology for performing KGQA using LLMs called Right for Right Reasons (R3) is proposed to solve this issue. R3 casts the problem of common sense KGQA as a tree-structured search, in which every reasoning step is either grounded on Knowledge Graph facts, or based on surfaced commonsense axioms, a key property that makes the reasoning procedure completely verifiable.

In this example workflow, R3 first identifies the anchor entities(The central entities mentioned in the query that are most relevant to finding the answer) of a query and obtains the relevant sub-graph for these entities. Next, it surfaces a commonsense axiom from the LLM that will guide the reasoning steps in that branch of the search tree. Then, at each depth level of the tree, it checks whether the common- sense axiom can be satisfied with the available KG facts, and if possible, provides an answer grounded on a subset of them. If the available KG triples are insufficient, by backward-chaining from the axiom, it selects the next entity to obtain its relevant KG sub-graph to continue the search. Each branch can continue up to a maximum depth, and if an answer is not obtained at its bottom, a new commonsense axiom will be surfaced which will guide search in a new branch until the search tree reaches its maximum breadth.

Experimental evaluations across three different tasks — question answering, claim verification, and preference matching — showcase R3 as a superior approach, outperforming existing methodologies and notably reducing instances of hallucination and reasoning errors.

KnowPhish

Phishing attacks are one of the most impactful types of scams, harming both individuals and businesses. Many efforts have been made to counter phishing attacks. Among these, Reference-Based Phishing Detectors (RBPDs), which work by comparing the logos on a target webpage to a known set of logos, have been established as the state-of-the-art phishing detection paradigm, garnering considerable research attention.

Specifically, an RBPD consists of a Brand Knowledge Base (BKB) containing brand information (e.g., the logos and legitimate domains of brands) and a detector backbone that uses information from this BKB for phishing detection. To detect if a web page is a phishing page, RBPDs first identify the webpage’s brand intention, that is, the brand that the webpage presents itself as (e.g., a webpage with a Adobe logo and appearance has the brand intention of Adobe). Then, if the webpage is detected to have an intention of a certain brand, but its domain does not match the legitimate domains of that brand, the webpage is classified as a phishing attempt.

However, RBPD has its limitations as well, such as not being able to identify textual Brand Intention. Therefore, a large-scale multimodal BKB named KnowPhish containing rich logo variants, aliases, and domain information of each brand was recently constructed and publicly released, along with a LLM-based approach to identify the brand intention of webpages in conjunction with the alias information in KnowPhish. This approach can be directly integrated with any standard visual RBPD, enabling it to detect brand intention through both visual and textual modalities. The resulting multimodal phishing detection approach, named KnowPhish Detector (KPD), is able to detect phishing webpages with or without logos.

KnowPhish has been shown to dramatically improve the performance of RBPDs. It is also significantly faster than DynaPhish, another detection framework by 30 or more times, especially when using image-based RBPDs. Moreover, incorporating the multimodal approach(incorporating various data sources such as images, text, audio, etc) KPD, can substantially boost the number of detected phishing webpages.

Conclusion

This post explored how Knowledge Graphs (KGs) and Large Language Models (LLMs) are being combined to address challenges in various tasks. The key takeaways are:

• Temporal Knowledge Graphs (TKGs) with LLMs: The Chain-of-History (CoH) reasoning method offers a promising approach for TKG prediction. By breaking down complex historical information into steps for LLMs, CoH improves reasoning accuracy, especially when combined with graph-based models.
• KG Question Answering (KGQA) with LLMs: The Right for Right Reasons (R3) methodology tackles common-sense KGQA. R3 leverages LLMs to surface commonsense knowledge and guide the reasoning process. This verifiable approach reduces errors and hallucinations compared to existing methods.
• Phishing Detection with LLMs: The KnowPhish approach demonstrates the power of LLMs in enhancing Reference-Based Phishing Detectors (RBPDs). By incorporating a multimodal Brand Knowledge Base (BKB) and LLM-based brand intention identification, KnowPhish significantly improves phishing detection rates and speeds compared to traditional methods.

Overall, the combination of Knowledge Graphs and LLMs opens exciting possibilities for tackling complex tasks that require reasoning and knowledge representation. As research in this area progresses, we can expect even more innovative applications that leverage the strengths of both these technologies.

References

• Li, Y., Huang, C., Deng, S., Lock, M. L., Cao, T., Oo, N., Hooi, B., & Lim, H. W. (2024). KnowPhish: Large Language Models Meet Multimodal Knowledge Graphs for Enhancing Reference-Based Phishing Detection (Version 1). arXiv. https://doi.org/10.48550/ARXIV.2403.02253
• Toroghi, A., Guo, W., Pour, M. M. A., & Sanner, S. (2024). Right for Right Reasons: Large Language Models for Verifiable Commonsense Knowledge Graph Question Answering (Version 1). arXiv. https://doi.org/10.48550/ARXIV.2403.01390
• Xia, Y., Wang, D., Liu, Q., Wang, L., Wu, S., & Zhang, X. (2024). Enhancing Temporal Knowledge Graph Forecasting with Large Language Models via Chain-of-History Reasoning (Version 1). arXiv. https://doi.org/10.48550/ARXIV.2402.14382