From Knowledge Graphs to Cognitive Graphs: History, Development, and Prospects

Knowledge graphs were introduced by Google in 2012 as a new concept. Essentially, they are a knowledge base for the semantic web. Knowledge graphs consist of nodes and edges, where nodes represent entities and edges represent relationships between entities. This is the most intuitive and easily understandable framework for knowledge representation and reasoning, laying the foundation for modern question-answering systems. From knowledge bases and reasoning engines in the 1980s to semantic networks and ontologies in the early 21st century, the core is early versions of knowledge graphs that either focus on knowledge representation or knowledge reasoning, but have always developed slowly due to small scale and unclear application scenarios. In 2012, Google’s release of a large-scale knowledge graph with 57 billion entities completely changed this situation¹; at the same time, the development of deep learning technology has also spurred a new wave of research in the field of knowledge graphs, particularly represented by knowledge graph embeddings like Trans^[1] and the use of large knowledge graphs to enhance other applications such as recommendation systems and sentiment analysis.

However, while knowledge graphs have achieved success in many applications, their methodology has always been overshadowed by several “clouds of uncertainty”, such as ambiguity issues, linking difficulties, redundancy in relationships, and combinatorial explosion. Although some remedial work addressing these issues has achieved good results, truly solving these problems may require a reconsideration of the framework and methodology of knowledge representation in the era of deep learning, thus cognitive graphs^[2] have emerged.

Cognitive graphs can be interpreted as “knowledge graphs constructed dynamically, based on raw text data, for specific problem contexts, using powerful machine learning models, with nodes containing contextual semantic information”. The application framework of cognitive graphs follows the dual process theory in cognitive psychology^[3], where System 1 is responsible for intuitive judgments based on experience, extracting important information and dynamically constructing cognitive graphs; System 2 performs relational reasoning on the graph. Since cognitive graphs retain the implicit representation of semantic information on entity nodes, models such as graph neural networks can also play a significant role beyond symbolic logic.

The theory of knowledge graphs originated in the AI boom of the second half of the 20th century, where multiple research groups independently proposed similar theories. It evolved from the semantic networks proposed by many renowned cognitive psychologists, with the most famous being ConceptNet proposed by Sowa et al. in 1984^[5]. In the spirit of symbolic thought, many early knowledge graphs limited relationships to a few special basic relationships, such as “has property”, “causes”, “belongs to”, etc., and defined a series of rules for reasoning on the graph, hoping to achieve intelligence through logical reasoning.

Figure 1 shows an example from early knowledge graphs^[6], where “ALI” represents “alikeness”, CAU represents “cause”; □ represents nodes, whose content is labeled by EQU “equal” or described by ALI.

However, the ideas of early knowledge graphs encountered many practical difficulties. For example, imperfect text data led to difficulties in structural parsing, the process of reducing to basic relationships required significant manual involvement, subtle differences in semantics were lost, and perfect reasoning rules could not be exhaustively enumerated. In fact, these problems did not stem from knowledge graphs themselves, but from the characteristics of symbolic thought. In subsequent practice, the balance of victory gradually tilted towards connectionist methods.

Semantic Web and Ontology

The Semantic Web^[7] is a vision proposed by Tim Berners-Lee, the inventor of the World Wide Web and recipient of the ACM Turing Award, in the early 20th century when natural language understanding was far less advanced than today. Fine-grained automatic querying of the web through natural language was a luxury. Even today, advanced voice assistants (e.g., Siri) can still only handle a limited number of operations, but the rapid progress of natural language understanding technology has brought hope. At that time, Tim took a different approach; if web pages could record their own information in the form of triple tags for easier machine understanding, then semantic search would be easily achievable.

To achieve this goal, resource description framework (RDF) and resource description framework schema/ontology web language (RDFS/OWL) were designed, but due to a lack of enthusiasm among internet creators, the Semantic Web has yet to be well realized, and research on related topics has gradually been replaced by knowledge graphs. However, the structured information of triples and the technologies accumulated in ontology research have become valuable knowledge assets.

Large-Scale Knowledge Graphs

The release of Google’s knowledge graph in 2012 brought this field back into the spotlight. However, constructing a large and high-quality knowledge graph is not easy. Freebase^[8] is the predecessor of Google’s knowledge graph, integrating a large number of online resources, including many private wikis. Another commonly used knowledge graph is DBpedia^[9], which extracts structured knowledge from Wikipedia to construct an ontology. Through structuring, users can query using SPARQL language. YAGO^[10] is also an open-source knowledge graph applied in IBM Watson’s question-answering system.

NELL^[11] is a project led by Professor Tom Mitchell at Carnegie Mellon University focusing on automatic knowledge learning. The NELL project initiated a wave of machine learning for knowledge graph construction, aiming to continuously acquire resources from the web for fact discovery, rule summarization, etc., involving key technologies such as named entity recognition, disambiguation, and rule induction. Figure 2 shows the automatic continuous construction framework of the NELL system.

ArnetMiner^[12] is a knowledge graph focused on the scientific field constructed by Tsinghua University’s Knowledge Engineering Laboratory, achieving key technologies such as high-precision scholar profiling, disambiguation, intelligent recommendation, and trend analysis. This work received the Test-of-Time Award from ACM SIGKDD.

Knowledge Graphs in the Era of Deep Learning

Knowledge graphs in the deep learning era have a large number of entities and relationships, but it is difficult to define logical rules across many different relationships, and “reasoning” on knowledge graphs has shifted to a paradigm of black-box model prediction. Bordes et al.^[13]’s knowledge base structure embedding and Socher et al.^[14]’s Neural Tensor Network (NTN) were the first to introduce neural networks into the study of knowledge graphs, especially NTN, which uses the average of word embeddings of entities and relationships in the knowledge graph as the representation of that node, training the neural network to determine whether the triple (head entity, relationship, tail entity) is true, achieving good results in knowledge graph completion (reasoning) tasks. Figure 3 shows the NTN knowledge base completion network. However, simply using word vectors to represent entities ignores their unique symbolic features: for example, the word vectors of the American internet celebrity “James Charles” and the famous fashion designer of the 20th century “Charles James” yield the same average result, yet their relevant attributes in the knowledge graph differ significantly.

Therefore, researchers have shifted their focus to training embeddings of large knowledge graphs themselves, with the most elegant and effective pioneering work being Bordes et al.^[1]’s TransE. The goal of this algorithm is to learn a d-dimensional vector representation for each relationship or entity in the knowledge graph. For any triple fact (h, r, t) in the knowledge graph, the algorithm requires their vector representations to satisfy h+r ≈ t, a concept derived from similar properties of word vectors. To train such embeddings, the algorithm defines the objective function:

where d(h+r, t) is the distance between vector h+r and t, typically using Euclidean distance; h’ and r’ are samples obtained via negative sampling, and the gap loss function is ultimately used for comparative learning.

A series of subsequent works, whether in naming or framework, have continued to improve upon the style of TransE. For example, to solve one-to-many and many-to-many complex relationships, TransH^[15] models relationships as planes rather than vectors, requiring the embedding vectors of head and tail entities to project onto that plane and satisfy, Figure 4 illustrates the vector space of the TransH model. Numerous improvement works in this direction, such as TransR^[16] and TransG^[17], have been well summarized in Wang et al.^[18]’s review.

Another important direction of knowledge graphs is complex problem reasoning. Knowledge graphs are often incomplete, and complex problems may not have obvious answers in the graph, or even corresponding relationships. However, through multi-step reasoning, it is still possible to obtain corresponding answers from the graph. Notable works in this direction include Xiong et al.^[21]’s Deeppath (see Figure 6), which explores reasoning paths in knowledge graphs using reinforcement learning. This idea has also inspired subsequent works, such as MINERVA using policy gradient^[22] and reward shaping by Lin et al.^[23].

Defects of Knowledge Graphs

The defects of knowledge graphs essentially stem from the limitations of using “binary first-order predicate logic” as the knowledge representation itself. For a long time, knowledge representation has been a topic of relentless pursuit by researchers. While relying solely on (head entity, relationship, tail entity) propositions can represent most simple events or entity attributes, it struggles with complex knowledge. In today’s increasing demand for fine-grained understanding of knowledge, this flaw has become the Achilles’ heel of knowledge graphs.

For instance, the fact that “Li Zhengdao and Yang Zhenning jointly proposed the theory of parity nonconservation” would typically be recorded in a knowledge graph as (Yang Zhenning and Li Zhengdao, proposed, parity nonconservation theory), where the head entity cannot be linked to other information about the two scientists; if the head entity is split, it would fail to reflect “jointly proposed”, which is not accurate. Ultimately, “…and… jointly proposed…” is a ternary relationship that cannot be directly recorded in the knowledge graph.

If this example could be improved by introducing hyperedges into the knowledge graph, the following second-order predicate logic example completely exceeds the existing framework. “The attributes of the cloned sheep are the same as those of the original body” cannot be recorded in the knowledge graph since all attributes are characterized by different relationships; in broader knowledge base theory, this is typically classified as a “rule”, requiring extensive enumeration operations to “infer” the various relational attributes of the cloned sheep. Understanding and formalizing rules often carry a strong human touch, and a high-order logic could involve massive entities, making the graph extremely redundant.

Finally, we focus on the difficulties in entity linking caused by information reduction during the construction process of knowledge graphs. The ultimate source of knowledge is the world we inhabit, with information being continuously reduced from raw speech, images, and text to knowledge graphs, retaining only the core content. However, neglecting specific experiences of individuals in the original text can lead to difficulties in disambiguating entities with the same name.

The aforementioned issues indicate that reforming knowledge graphs is imperative. With the significant advancements in natural language processing, models like BERT^[24] have enhanced text understanding and retrieval capabilities, allowing us to understand and reason directly from raw text. For example, Chen et al.^[25]’s DrQA uses neural networks to extract question answers directly from text, initiating a new wave of open-domain questioning. On the other hand, we must retain the interpretability and precise stable reasoning capabilities brought by the graph structure of knowledge graphs. Therefore, cognitive graphs have emerged.

Cognitive graphs mainly feature three innovations corresponding to three aspects of human cognitive intelligence:

1. (Long-term memory) Directly storing indexed text data, using information retrieval algorithms to access relevant knowledge instead of explicit edges in knowledge graphs.

2. (System 1 reasoning) The graph is dynamically and multi-step constructed based on queries, with entity nodes generated through relevant entity recognition models.

3. (System 2 reasoning) The nodes in the graph simultaneously possess implicit representations with contextual information, allowing for explainable relational reasoning through models like graph neural networks.

Essentially, the improvement idea of cognitive graphs is to reduce information loss during graph construction, shifting the information processing burden to retrieval and natural language understanding algorithms while retaining the graph structure for explainable relational reasoning.

In fact, cognitive graphs are inspired by human cognitive processes, where “quickly directing attention to relevant entities” and “analyzing sentence semantics for inference” are two different thinking processes. In cognitive science, the well-known “dual process theory” posits that human cognition is divided into two systems: System 1 is an intuitive, non-conscious thinking system reliant on experience and associations; while System 2 is the unique logical reasoning ability of humans, utilizing knowledge in working memory^[26] for slow yet reliable logical reasoning, being explicit and requiring conscious control, reflecting higher human intelligence.

The Challenge of Multi-Hop Reading Comprehension

Cognitive graphs were first proposed by Ding et al.^[2] and applied to multi-hop open-domain reading comprehension question answering (see Figure 7). In traditional methods, open-domain question answering often relies on large-scale knowledge graphs, while reading comprehension question answering typically focuses on single passages, where natural language processing (NLP) models (like BERT) can be directly applied. The groundbreaking DrQA system applied a simple method to use reading comprehension in open-domain question answering, namely first retrieving a small number of relevant paragraphs from the corpus (Wikipedia) based on the question, and then processing these paragraphs with NLP.

However, the article on cognitive graph question answering (CogQA) argues that such methods face the “short-sighted retrieval” problem in multi-hop question answering, where the relevance of later text to the question is low, making direct retrieval difficult and leading to poor performance.

Moreover, since BERT emerged, the benchmark dataset SQuAD for single-text reading comprehension has quickly surpassed human levels, but at the same time, there is reflection on whether these models can truly achieve reading “comprehension”. In Jia et al.^[27]’s article, they present an interesting example:

The original text states: “In January 1880, two of Tesla’s uncles put together enough money to help him leave Gospić for Prague where he was to study.” The question is: “What city did Tesla move to in 1880?” Most models can easily answer “Prague” correctly. However, if we add a sentence after the original text: “Tadakatsu moved to the city of Chicago in 1881”, these models will confidently answer “Chicago”—this is merely due to the sentence’s form resembling the question, even though the key information does not match.

This suggests that deep learning-based NLP models primarily resemble System 1 in cognition; if we are to further achieve robust reasoning, we must consider System 2.

Additionally, lack of interpretability has been a significant criticism of previous multi-layer black-box models. These models often only require inputting a question and text, with outputs indicating the answer’s position in the text; in multi-hop reading comprehension, each hop has a reason, and if a reasonable answer explanation cannot be provided, it cannot be proven that the text has been truly “understood”.

Cognitive Graph Question Answering

Cognitive graph question answering (see Figure 8) proposes a novel iterative framework: the algorithm uses two systems to maintain a cognitive graph, where System 1 extracts entity names related to the question from the text and expands nodes and aggregates semantic vectors, while System 2 utilizes graph neural networks for reasoning calculations on the cognitive graph.

As previously mentioned, the human System 1 is “non-conscious”, and System 1 in CogQA is also popular NLP black-box models, such as BERT. In the implementation of the article, the input of System 1 is divided into three parts: the question itself, the “clues” found from earlier paragraphs, and the Wikipedia document about a certain entity x (e.g., x = the movie “Old School”).

The goal of System 1 is to extract the “next-hop entity names” and “answer candidates” from the document. For example, in the case of Figure 7, it extracts the movies “Old School” and “Gone in 60 Seconds” as the next-hop entity names from the paragraph about “Quality Café”, and extracts its director “Todd Phillips” as one of the answer candidates from the paragraph about “Old School”. These extracted entities and answer candidates will be added as nodes to the cognitive graph. Additionally, System 1 will calculate the semantic vector of the current entity x, which will serve as the initial value for relational reasoning in System 2.

Subsequently, each extracted “next-hop entity name” or “answer candidate” will establish a new node in the cognitive graph and proceed to the next iteration.

Meanwhile, System 2 performs reasoning calculations on the cognitive graph, utilizing graph neural networks (GNN) for implicit reasoning calculations—each iteration passes transformed information from previous nodes to the next-hop nodes and updates the current implicit representation. Ultimately, the implicit representations of all “answer candidate” nodes will be assessed through a fully connected network with a softmax function to determine the final answer.

During the cognitive graph expansion process, if a visited node acquires new parent nodes (cyclic or convergent structures), it indicates that this point has gained new clue information, requiring a re-expansion calculation. The final algorithm flow is realized through a frontier point queue.

CogQA not only achieved the top performance on the HotpotQA dataset^[28] over three months, but the cognitive graph in the case analysis of Figure 9 also showcases its superiority in terms of interpretability:

In the tree diagram of Figure 9(1), the key to answering the question lies in determining whether Ken Pruitt’s organization is the “Senate” or the “House of Representatives”; the model answers by assessing the semantic similarity between “upper house” (a term for the Senate in the U.S.) and “Senate”; Figure 9(2) is a directed acyclic graph, where multiple reasoning paths can enhance judgment; Figure 9(3) is an example where the model arrived at an “incorrect answer”; the standard answer from the dataset is “Ten Walls”, while CogQA provided “Marijus Adomaitis”. However, upon examining the cognitive graph, it is found that Ten Walls is merely the stage name of Marijus Adomaitis, resulting in a more accurate answer—this interpretability brings benefits that traditional black-box models lack.

Prospects for the Development of Cognitive Graphs

In today’s rapidly developing natural language understanding tools, cognitive graphs are in their infancy, and many valuable directions await exploration:

1. How can reasoning in System 2 be realized? Current methods (like graph neural networks) utilize relational edges as inductive biases but still cannot perform controlled, explainable, and robust symbolic computations. How can System 1 provide feasible preliminary work for existing neural-symbolic computation methods?

2. How should text libraries be preprocessed or pre-trained to facilitate the retrieval of relevant knowledge?

3. Are there alternative approaches? The cognitive graphs introduced in this article are based on the dual-channel theory of cognitive science; are there other supporting theories? Or should a new learning architecture combining symbolic reasoning and deep learning be constructed directly?

4. How can cognitive graphs be integrated with human memory mechanisms? Human memory mechanisms include long-term and short-term memory, but their working modes and mechanisms are unclear. Long-term memory may store a memory model, which is no longer a network of concepts but a network of computational models.

5. How cognitive graphs can be combined with external feedback is a brand new problem. Of course, feedback reinforcement learning could be considered to achieve this, but specific methods and implementation patterns need to be explored in depth.

In recent years, with the rise of deep learning, related technologies for knowledge graphs have also flourished, while some shortcomings have been exposed. This article reviews the historical development of knowledge graphs, summarizes their current state, and illustrates the defects of existing knowledge graphs. Meanwhile, we delve into the promising cognitive graphs, discussing their applications in question-answering systems. Finally, we look forward to potential future directions for cognitive graphs, exploring ways to facilitate the leap from perception to cognition in artificial intelligence through cognitive graphs.

Ding Ming

CCF student member.PhD student at Tsinghua University. Main research directions include natural language processing, graph learning, and cognitive intelligence. [email protected]

Tang Jie

CCF distinguished member, former dynamic column editor of CCCF, chair of the CCF academic committee.Professor in the Department of Computer Science at Tsinghua University. Main research directions include artificial intelligence, knowledge graphs, data mining, social networks, and machine learning.

[email protected]