About 6600 words in this article, recommended reading time is 5 minutes.
The theme of this presentation is research on explainable knowledge graph reasoning.
The report is divided into the following 5 parts:
-
Research Background
-
Frontier Progress
-
Research Motivation
-
Recent Research
-
Research Outlook
01 Research Background
1. Introduction
First, let’s introduce the background. After more than 70 years of development, artificial intelligence has progressed from computational intelligence that can store and calculate, to perceptual intelligence that can hear, see, recognize, and speak. Many systems have performed excellently in this aspect, but there is still a long way to go to achieve ideal cognitive intelligence. Cognitive intelligence hopes that machines can understand, reason, and explain data models and principles. A significant characteristic of cognitive intelligence is its reliance on background knowledge. For example, new internet concepts or buzzwords, such as “996” and “YYDS”, are built on group consensus and heavily depend on background knowledge. Learning and modeling these concepts that align with cognitive intelligence characteristics is currently a challenge, and learning and representing this background knowledge is a critical technology.
2. Knowledge Graph
A knowledge graph is a technology and tool that carries and represents background knowledge, organizing entities and relationships from the real world into a network in the form of a graph, structuring knowledge. In the example of the knowledge graph above, the entities and relationships in the knowledge graph can be abstracted as nodes and edges in the graph, characterized by:
-
It is a directed graph, and its edges are directed.
-
It is a heterogeneous graph, with nodes and edges of different types, also known as heterogeneous information networks.
-
It contains rich information, allowing nodes and edges to be bound with extensive attribute information for more detailed descriptions of knowledge.
-
It is usually very large in scale.
3. Downstream Applications of Knowledge Graphs
Knowledge graphs are widely used in applications requiring background knowledge or knowledge acquisition, with typical examples including: information retrieval, question answering/chat systems, language and image understanding, etc.
Information retrieval utilizes knowledge graphs for intelligent inference between concepts and fuzzy queries, while providing knowledge cards for key concepts to enhance user experience.
In question answering/chat systems, when interacting with a question-answering assistant or chat system, it can solve task-oriented question-answering issues, where knowledge graphs play a core role.
In language and image understanding, knowledge graphs are used to achieve understanding of linguistic data, textual data, and image data, helping to learn relationships between concepts through knowledge growth, such as in recent active research in VQA and image relationship reasoning.
4. Knowledge Graph Reasoning
The core function in the applications mentioned above is knowledge graph reasoning. Knowledge graph reasoning refers to the ability to derive new knowledge based on existing knowledge within the knowledge graph. For example, in the relationship knowledge graph of people shown above, if it is known that X is related to Z, and Z is related to M, where Z is X’s wife and M is Z’s child, the system can infer that X is M’s father, which is a simple reasoning relationship.
Knowledge graph reasoning can be viewed from two angles: one is from the perspective of logical deduction, which is a truth value judgment problem under multiple propositional constraints. The other is to understand knowledge graph reasoning from the graph perspective, where link prediction problems can be modeled and analyzed, predicting associations between nodes based on the nodes in the graph; for example: given two entities, predict what kind of edge exists between them, i.e., what kind of relationship; given a certain entity and a certain edge, predict which entities are associated with that entity.
02 Frontier Progress
1. Main Methods
The main methods of frontier progress can be divided into four parts: first, deductive logic and rules; second, graph-structured reasoning; third, knowledge graph embedding representation; fourth, deep neural network models.
2. Deductive Logic and Rules
This method is a very classic and common approach. It converts natural language queries into combinations of logical operators, expressing such queries through combinations and implementing them with specific programming languages. Notable implementations of graph queries include SPARQL, Cypher, Datalog, and other inductive logic programming languages. The characteristics of deductive logic reasoning are:
-
The accuracy of reasoning is very good.
-
It has good interpretability, as it is logical.
-
It requires experts to formulate a large number of reasoning rules.
-
It has poor generalization ability for unknown rules.
A recent hot topic in research is how to use machine learning and deep learning to automatically discover reasoning rules.
3. Graph-Structured Reasoning
Here, graph structure is believed to have two characteristics: one is path features, represented by algorithms such as PRA and extended algorithms, which extract path features between nodes through graph traversal algorithms or random walk methods, predicting node connections based on path features. Its characteristic is that it provides path interpretability during reasoning, but its problem is that it cannot solve the issue of reasoning nodes that are not connected. Based on traditional methods, the search space is relatively large. The second is the graph-structured method, represented by Grall, which utilizes a message-passing mechanism to extract structural information of the target entity, providing subgraph interpretability; however, the current method of subgraph structure is not mature, as knowledge graphs are usually large, and the traversal methods for all subgraph structures in the graph are very important.
4. Knowledge Graph Embedding Representation
This method embeds high-dimensional, discrete data from knowledge graphs into a low-dimensional continuous vector space by designing a scoring function, representing entities and relationships as numerical vectors for computation. Representative models include TransE type, and recent research includes the RotateE model or models embedded in hyperbolic space. The characteristics of this method are shallow neural networks that achieve semantic representation of knowledge graphs through specific embedding space structures.
5. Deep Neural Network Models
Deep neural network models design entities and relationships as query pairs, matching query pairs with entities and relationships to obtain similarity scores for reasoning judgments through deep neural networks. Recent research hotspots include Transformer or graph neural networks.
Knowledge graph embedding models and deep network models are both considered neural network models. Their commonality is that they both design a scoring function, train using a data-driven approach, and employ gradient backpropagation methods. Their advantages include good generalization performance, ease of numerical computation and parallelization, and scalability, which can effectively alleviate the dimensionality disaster of graph structures. However, their disadvantages include only being able to see the similarity of input and output values, lacking interpretability, and not knowing what happens inside the model, making it a black-box process, thus having poor interpretability and weak robustness to noise, only allowing for single-step reasoning.
6. Summary of Existing Methods
Here, a summary of the main reasoning methods is provided. It can be found that methods based on logical deduction rules and graph structures are symbol-based methods, which have good interpretability but poor generalization performance, and are offline computation methods. Knowledge graph embedding and deep neural network models have good generalization performance but poor interpretability.
Recent research focuses on how to integrate symbolic and connectionist models to obtain explainable knowledge graph reasoning models.
03 Research Motivation
1. Explainability of Knowledge Graph Reasoning
The sources of explainability for knowledge graph reasoning have been classified:
-
Logical explainability: a natural source of explainability for knowledge graphs, providing logical grounds for explanations.
-
Graph structure explainability: the graph structure has path features, such as metapath and subgraph structural features.
-
Neural network model explainability: post-hoc explainability, which can analyze feature significance through some post-hoc interpretability methods of neural networks. Representative methods include visualization of the Attention mechanism, which is still not very mature; another is the CAM or Graph CAM method; and another is using embedding space theory analysis methods, where RotateE or hyperbolic space performs very well, but cannot explain parameter changes well.
2. Reinforcement Learning
How to effectively integrate symbolic and connectionist models is a recent research hotspot. The focus here is on integrating reinforcement learning into knowledge reasoning.
Reinforcement learning has received a lot of attention in the past decade, widely applied in control, games, and robotics. It models a learning process as a Markov process, where an agent interacts with the environment and trains the model by maximizing long-term cumulative rewards. Interaction with the environment generates trajectories; if the knowledge graph is modeled as a reinforcement learning process, it can yield reasoning results and the reasoning path, explaining knowledge graph reasoning through the reasoning path.
3. Knowledge Graph Reasoning Based on Reinforcement Learning
The specific method of integration is to view the knowledge graph as an environment, modeling the agent as a deep neural network, combining the advantages and disadvantages of symbolic and connectionist approaches to complement each other, allowing the model to simultaneously possess the generalization performance of neural networks and path interpretability. Additionally, since deep reinforcement learning is a sequential process, it can handle multi-hop reasoning processes.
04 Recent Research
1. Knowledge Graph Reasoning Based on Hierarchical Reinforcement Learning
The first work carried out is a knowledge graph reasoning model based on hierarchical reinforcement learning.
The background of this research is to solve the multi-semantics problem in knowledge graphs. For example, the entities in the FreeBase knowledge graph are pre-trained using TransE, and the relationships are represented by subtracting related entities, visualized through PCA dimensionality reduction, revealing that the relationships have multiple semantic clusters, indicating patterns that appear in the pre-trained model. Multiple semantic clusters can cause ambiguity, leading to reduced reasoning accuracy.
How to solve the multi-semantics problem in knowledge graph reasoning? Combining recent discoveries in neuroscience, articles published in Science indicate that the decision-making process of humans or higher animals is a hierarchical reasoning process, a subconscious process that gradually resolves multi-semantics and ambiguity through multiple observations and reasoning to obtain a reasoning structure. The mechanism of hierarchical decision-making is the core mechanism of cognitive processes, which is the conclusion of this paper. For example, in the process of recognizing a golden monkey, a subconscious process is first recognizing it as an animal, then as a primate, and finally recognizing it as a golden monkey. This is a process from high-level to low-level, from coarse to fine-grained conceptually, which reflects a hierarchical mechanism.
Hierarchical reinforcement learning differs from traditional reinforcement learning models by further structuring the decision space, decomposing the problem into several sub-problems for decision-making. Hierarchical reinforcement learning resembles human thinking, improving the accuracy of knowledge reasoning and addressing multi-semantics issues.
The specific implementation of hierarchical reinforcement learning involves designing two nested reinforcement learning processes: one is a high-level policy function, and the other is a low-level policy function. The high-level policy controls state transitions between knowledge graph entities, while the low-level policy controls transitions between semantic clusters, with semantic clusters constructed using TransE embeddings.
Specifically, the high-level policy function is a GRU-based policy function capable of storing historical vectors, with a reward function that is a γ-decaying reward function. The low-level policy function is a process that hierarchically decomposes the state space, with a reward function that is a binary reward of 0 or 1.
The training objective is to maximize the reward, using gradient policy optimization to train the model. Due to the nested nature of the high-level and low-level policy functions, an alternating fixed optimization approach is employed, training the reasoning model through Monte Carlo sampling trajectories.
The evaluation metrics used are average accuracy, average ranking score, and Hit@X. The datasets are common sense knowledge graphs FB15K, NELL995, and WN18RR, with FB15K exhibiting significant multi-semantics phenomena.
Link prediction experiments have been conducted, with the graph illustrating the results of entity prediction experiments, showing that the model performs well on most datasets, particularly on multi-semantics datasets.
The second experiment involves predicting facts, determining whether a certain relationship exists between two given entities, which is a binary classification problem. The model performs slightly better on FB15K-237.
Hierarchical reinforcement reasoning can provide interpretable reasoning paths; the graph illustrates that compared to MINERVA, it can offer better reasoning paths during the reasoning process.
In summary, a hierarchical reinforcement learning knowledge reasoning model is proposed, which mimics human thinking methods and learns hierarchical semantic clusters of relationships in knowledge graphs, thereby helping to solve multi-semantics issues in the reasoning process. Experiments show that this model achieves competitive results on standard datasets and performs better on multi-semantics problems. This work was published at IJCAI 2020.
2. Knowledge Graph Reasoning Based on Bayesian Reinforcement Learning
The second work involves a Bayesian reinforcement learning knowledge graph reasoning model.
Research has found that a significant issue with knowledge graph reasoning based on reinforcement learning is:
-
Training is difficult to stabilize, with high variance in Monte Carlo sampling and sparse rewards.
-
It is challenging to utilize prior knowledge, such as pre-trained corpora, attribute information, and prior distributions of relationships and entities.
-
Single-point distributions of entities and vectors cannot express semantic uncertainty.
Utilizing Bayesian reinforcement learning tools to model uncertainty reasoning. Assuming parameters follow a certain probability distribution, the right graph shows that the advantage of Bayesian learning is the ability to express uncertainty.
Using Bayesian reinforcement learning has the advantage of expressing uncertainty in entities and relationships, which is beneficial for balancing exploration-exploitation relationships. Through randomness, regularization terms can be introduced to stabilize the training optimization of Q networks/policy networks, while the Bayesian reinforcement mechanism can utilize the prior distribution of knowledge.
The method is relatively simple: assume the entities and relationships in the knowledge graph follow a Gaussian distribution, designing a reasonable knowledge graph Q function for reasoning.
Defining knowledge graph reasoning as a Markov decision process, where the environment is the knowledge graph, the state is the position of entities within the knowledge graph, actions are the set of entities that can connect to this position, the policy function is based on maximizing Q values, and the reward function is binary (0, 1).
The definition of the Q function is a state-action value definition, where St is the state and represents the expected reward for future reasoning Q. Directly solving the Q function is usually difficult, so it is fitted using neural networks. The specific implementation is to fit the Q function’s hidden state using Bayesian LSTM, outputting Q values through a Bayesian linear regression network.
There are two types of execution and optimization strategies, which are off-policy methods, meaning the optimization strategy differs from the execution strategy function. The optimization strategy adopts a greedy strategy to ensure training utilization. The execution strategy is ensured through Thompson sampling, generating randomizations of Q values to guarantee exploration of the environment.
The final objective function is to minimize the variational free energy of the Q function network, optimizing through trajectory sampling and using Monte Carlo gradients for approximate optimization, specifically implemented through Bayesian backpropagation to train the Bayesian neural network.
In knowledge graph experiments, the graph illustrates the results of fact prediction experiments, which is a binary classification prediction problem, predicting the relationship between two given entities. The model achieves relatively good results on NELL995.
The entity prediction experiment shows that the model can achieve superior results.
In link prediction experiments on small-scale knowledge graphs, where the maximum reasoning length is set to 2, single-step reasoning also achieves certain effects.
The Bayesian reinforcement learning model, without adopting a random distribution method, shows that compared to MINERVA, the Bayesian reinforcement learning model converges faster and can introduce prior distributions, resulting in better convergence through pre-training on Gaussian distributions of entities.
Visualizing the reasoning process through box plots, the example demonstrates how to reason about where Argentina is, achieving uncertainty reasoning and realizing uncertainty in Q value distributions.
The graph illustrates that the GaussianPath model generates some interpretable reasoning paths during the reasoning process.
In summary, a Bayesian reinforcement learning knowledge reasoning model is proposed, capable of expressing uncertainty in multi-hop reasoning paths. This model utilizes the characteristics of Bayesian networks to introduce prior knowledge, accelerating and stabilizing the training of reinforcement learning networks. Experiments show that this model achieves competitive results on standard datasets. This work was published at AAAI 2021.
3. Automatic Meta-Path Mining in Heterogeneous Information Networks
The third work involves the application of knowledge graph reasoning based on reinforcement learning, focusing on automatic meta-path mining in heterogeneous information networks.
A heterogeneous information network refers to a network where the types of nodes and relationships on the graph exceed one, with definitions broader than knowledge graphs. Common examples include movie networks, citation networks, and knowledge graphs.
Meta-path is a commonly used method in heterogeneous information networks, representing a sequence of entity relationships that express semantic features between entities. For example, “APA” can characterize the relationship of co-authorship, while “APVPA” can characterize the relationship of belonging to the same research group. This has generated a series of classic works in graph data mining.
Meta-path has a wide range of applications in information retrieval, data mining, and recommendation systems.
The advantages of meta-path include accurate semantic expression, high efficiency, structural characteristics of graphs, and good interpretability. However, it requires manual design, as constructing meta-paths is a non-end-to-end method, and designing long sequence meta-paths is relatively difficult.
Methods to automatically obtain meta-paths include greedy tree methods, K-shortest paths, and graph traversal methods to obtain meta-paths. However, these methods face challenges in computationally discrete spaces, with large search spaces. Our research proposes an automatic meta-path mining model for heterogeneous information networks, utilizing reinforcement learning to derive reasoning path patterns to obtain meta-paths.
The method for automatic meta-path mining in heterogeneous information networks utilizes reinforcement learning for multi-hop reasoning to obtain path instances and performs reductions on typed directed graphs to derive meta-paths.
This work’s reinforcement learning framework is similar to the previous two works, but with slight differences in state and action settings. The state includes tuples of vd entities; actions involve the stay of entities in the heterogeneous information network, with the action space consisting of connected edges and entities; rewards are based on a γ-decaying reward function.
Knowledge graphs usually have large scales, with millions of entities and facts. Directly assigning table vectors to each entity can consume significant storage and computational resources. This work proposes a representation method based on type context, effectively reducing the storage issue of entity vectors by averaging type vectors.
The specific path instance reduction method is based on the lowest ancestor method, obtaining meta-paths through root node searches in type graphs. For example, the entity type DAG can be used to find the type of Person through the lowest ancestor search method, ultimately obtaining the type and type combinations to derive meta-paths.
The experimental section utilizes the mined meta-paths for link prediction. The datasets used are Yago and NELL, which are large-scale heterogeneous information networks or knowledge graphs. Yago and NELL have over a million entities, with Yago containing over 800,000 types and NELL having over 700 types. The key difference from knowledge graphs is the abundance of type information.
According to the link prediction experiments, it can be seen that the paths mined through reinforcement learning, even as a relatively simple linear regression of path features, can achieve good results.
Additionally, the weights of meta-paths can be obtained through the regression of reinforcement learning inference. For instance, in the Yago dataset, the relationship representing citizenship can be characterized by the relationships Person BorIn Country and Person BorIn District LocatedIn Country, effectively depicting the isCitizenOf relationship. The model can derive different weighted meta-paths, discover longer meta-paths, and compare meta-paths to find synonymous meta-paths.
In summary, a reinforcement learning model is proposed, capable of mining meta-paths in large-scale heterogeneous information networks. Using contextual representations significantly alleviates the scalability issues of heterogeneous information networks. Experiments demonstrate that even with simple linear regression, the mined meta-paths can perform well in large-scale heterogeneous information networks, indicating that the core limitation of heterogeneous information networks is the quality of meta-paths. This work was published at AAAI 2020.
05 Summary and Outlook
-
Research in deep learning and neural networks has entered the next stage, requiring deeper investigations into the interpretability and robustness of neural networks.
-
Future research on the explainability of knowledge graphs can combine first-order logic reasoning with neural networks to enhance the logical consistency of knowledge graph reasoning, thereby improving its interpretability.
-
Further practical query tasks, such as question answering systems and information retrieval, can be realized to achieve end-to-end explainable knowledge reasoning.
-
Utilizing decomposition models or methods like GNNExplainer to establish some post-hoc interpretability measures for existing models.
06 Q&A Session
Q: How to evaluate the comprehensibility of generated explanations?
A:The comprehensibility of explanations generally involves more post-hoc interpretability, such as trustworthiness. In this research work, more pre-hoc interpretability methods are employed. The specific ability of interpretability is relatively subjective, and existing methods for evaluating interpretability are primarily used for post-hoc interpretability.
That concludes today’s sharing. Thank you all.
Speaker
Wang Guojia,Postdoctoral researcher at the School of Computer Science, Wuhan University,currently interested in research directions such as knowledge graph reasoning and graph neural networks, having published 6 papers in journals and conferences such as AAAI, IJCAI, and WWWJ.
Editor: Wang Jing
Proofreader: Lin Yilin
