A conceptual graph (CG) is a formalism for
knowledge representation
Knowledge representation (KR) aims to model information in a structured manner to formally represent it as knowledge in knowledge-based systems whereas knowledge representation and reasoning (KRR, KR&R, or KR²) also aims to understand, reason, and ...
. In the first published paper on CGs,
John F. Sowa used them to represent the
conceptual schemas used in
database system
In computing, a database is an organized collection of data or a type of data store based on the use of a database management system (DBMS), the software that interacts with end users, applications, and the database itself to capture and anal ...
s. The first book on CGs applied them to a wide range of topics in
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
,
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, and
cognitive science
Cognitive science is the interdisciplinary, scientific study of the mind and its processes. It examines the nature, the tasks, and the functions of cognition (in a broad sense). Mental faculties of concern to cognitive scientists include percep ...
.
Research branches
Since 1984, the model has been developed along three main directions: a graphical interface for
first-order logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
, a
diagrammatic
A diagram is a symbolic Depiction, representation of information using Visualization (graphics), visualization techniques. Diagrams have been used since prehistoric times on Cave painting, walls of caves, but became more prevalent during the Age o ...
calculus of logics, and a
graph-based
knowledge representation and reasoning
Knowledge representation (KR) aims to model information in a structured manner to formally represent it as knowledge in knowledge-based systems whereas knowledge representation and reasoning (KRR, KR&R, or KR²) also aims to understand, reason, and ...
model.
Graphical interface for first-order logic

In this approach, a formula in
first-order logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
(predicate calculus) is represented by a labeled graph.
A linear notation, called the Conceptual Graph Interchange Format (CGIF), has been standardized in the
ISO standard
The International Organization for Standardization (ISO ; ; ) is an independent, non-governmental, international standard development organization composed of representatives from the national standards organizations of member countries.
Me ...
for
common logic.
The diagram above is an example of the ''display form'' for a conceptual graph. Each box is called a ''concept node'', and each oval is called a ''relation node''. In CGIF, this CG would be represented by the following statement:
In CGIF, brackets enclose the information inside the concept nodes, and parentheses enclose the information inside the relation nodes. The letters x and y, which are called ''coreference labels'', show how the concept and relation nodes are connected. In CLIF, those letters are mapped to variables, as in the following statement:
As this example shows, the asterisks on the coreference labels and in CGIF map to existentially quantified variables in CLIF, and the question marks on and map to bound variables in CLIF. A universal quantifier, represented in CGIF, would be represented in CLIF.
Reasoning can be done by translating graphs into logical formulas, then applying a logical
inference engine.
Diagrammatic calculus of logics
Another research branch continues the work on
existential graphs of
Charles Sanders Peirce
Charles Sanders Peirce ( ; September 10, 1839 – April 19, 1914) was an American scientist, mathematician, logician, and philosopher who is sometimes known as "the father of pragmatism". According to philosopher Paul Weiss (philosopher), Paul ...
, which were one of the origins of conceptual graphs as proposed by Sowa. In this approach, developed in particular by Dau , conceptual graphs are conceptual
diagram
A diagram is a symbolic Depiction, representation of information using Visualization (graphics), visualization techniques. Diagrams have been used since prehistoric times on Cave painting, walls of caves, but became more prevalent during the Age o ...
s rather than graphs in the sense of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, and reasoning operations are performed by operations on these diagrams.
Graph-based knowledge representation and reasoning model
Key features of GBKR, the graph-based knowledge representation and reasoning model developed by Chein and Mugnier and the Montpellier group, can be summarized as follows:
* All kinds of knowledge (ontology, rules, constraints and facts) are labeled graphs, which provide an intuitive and easily understandable means to represent knowledge.
* Reasoning mechanisms are based on graph notions, basically the classical notion of
graph homomorphism; this allows, in particular, to link basic reasoning problems to other fundamental problems in computer science (e.g., problems concerning
conjunctive queries in
relational database
A relational database (RDB) is a database based on the relational model of data, as proposed by E. F. Codd in 1970.
A Relational Database Management System (RDBMS) is a type of database management system that stores data in a structured for ...
s, or
constraint satisfaction problems).
* The formalism is logically founded, i.e., it has a semantics in
first-order logic
First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...
and the inference mechanisms are sound and complete with respect to deduction in first-order logic.
* From a computational viewpoint, the graph homomorphism notion was recognized in the 1990s as a central notion, and complexity results and efficient algorithms have been obtained in several domains.
COGITANT and COGUI are tools that implement the GBKR model. COGITANT is a library of
C++ classes that implement most of the GBKR notions and reasoning mechanisms. COGUI is a graphical user interface dedicated to the construction of a GBKR knowledge base (it integrates COGITANT and, among numerous functionalities, it contains a translator from GBKR to
RDF/S and conversely).
See also
*
Alphabet of human thought
*
Chunking (psychology)
In cognitive psychology, chunking is a process by which small individual pieces of a set of information are bound together to create a meaningful whole later on in memory. The chunks, by which the information is grouped, are meant to improve shor ...
*
Resource Description Framework
The Resource Description Framework (RDF) is a method to describe and exchange graph data. It was originally designed as a data model for metadata by the World Wide Web Consortium (W3C). It provides a variety of syntax notations and formats, of whi ...
(RDF)
*
SPARQL (Graph Query Language)
*
Semantic network
A semantic network, or frame network is a knowledge base that represents semantic relations between concepts in a network. This is often used as a form of knowledge representation. It is a directed or undirected graph consisting of vertices, ...
References
Bibliography
*
*
*
*
* {{cite journal, title=Conceptual graphs for the analysis and generation of sentences
, first1=Paola , last1=Velardi , first2=Maria Teresa , last2=Pazienza , first3=Mario , last3=De' Giovanetti , journal=IBM Journal of Research and Development , volume=32 , number=2 , date=March 1988 , pages=251–267 , publisher=IBM Corp. Riverton, NJ, USA , doi=10.1147/rd.322.0251
External links
Conceptual Graphs Home PageAnnual international conferences (ICCS)at
DBLP
DBLP is a computer science bibliography website. Starting in 1993 at Universität Trier in Germany, it grew from a small collection of HTML files and became an organization hosting a database and logic programming bibliography site. Since Novem ...
Conceptual Graphs on John F. Sowa's Website
Knowledge representation
Diagrams
Application-specific graphs