Conceptual graph
Encyclopedia
Conceptual graphs are a formalism for knowledge representation. In the first published paper on CGs, John F. Sowa
(Sowa 1976) used them to represent the conceptual schemas used in database systems. The first book on CGs (Sowa 1984) applied them to a wide range of topics in artificial intelligence, computer science, and cognitive science.
Since 1984, the model has been developed along three main directions.
A linear notation, called the Conceptual Graph Interchange Format (CGIF), has been standardized in the ISO standard for Common Logic
.
The diagram on the right 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:
[Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)
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 the Common Logic Interchange Format (CLIF), those letters are mapped to variables, as in the following statement:
(exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))
As this example shows, the asterisks on the coreference labels *x and *y in CGIF map to existentially quantified variables in CLIF, and the question marks on ?x and ?y map to bound variables in CLIF. A universal quantifier, represented @every*z in CGIF, would be represented forall (z) in CLIF.
Reasoning can be done by translating graphs into logical formulas, then applying a logical inference engine.
s of Charles Sanders Peirce, which were one of the origins of conceptual graphs as proposed by Sowa.
In this approach, developed in particular by Dau (Dau 2003), conceptual graphs are conceptual diagrams rather than graphs in the sense of graph theory, and reasoning operations are performed by operations on these diagrams.
can be summarized as follows:
COGITANT and COGUI are tools that implement the GBKR model. COGITANT http://cogitant.sourceforge.net/ is a library of C++ classes that implement most of the GBKR notions and reasoning mechanisms. COGUI http://www.lirmm.fr/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).
(FCA) and other tools and languages for representing and reasoning about concepts. Following is a sample of some currently active researchers on conceptual graphs, many of whom combine CGs with FCA and other notations for logic.
John F. Sowa
John Florian Sowa is the computer scientist who invented conceptual graphs, a graphic notation for logic and natural language, based on the structures in semantic networks and on the existential graphs of Charles S. Peirce. He is currently developing high-level "ontologies" for artificial...
(Sowa 1976) used them to represent the conceptual schemas used in database systems. The first book on CGs (Sowa 1984) applied them to a wide range of topics in artificial intelligence, computer science, and cognitive science.
Since 1984, the model has been developed along three main directions.
A graphical interface for first-order logic
In this approach, a formula in first-order logic (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 for Common Logic
Common logic
Common logic is a framework for a family of logic languages, based on first-order logic, intended to facilitate the exchange and transmission of knowledge in computer-based systems....
.
The diagram on the right 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:
[Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)
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 the Common Logic Interchange Format (CLIF), those letters are mapped to variables, as in the following statement:
(exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))
As this example shows, the asterisks on the coreference labels *x and *y in CGIF map to existentially quantified variables in CLIF, and the question marks on ?x and ?y map to bound variables in CLIF. A universal quantifier, represented @every*z in CGIF, would be represented forall (z) in CLIF.
Reasoning can be done by translating graphs into logical formulas, then applying a logical inference engine.
A diagrammatic calculus of logics
Another research branch continues the work on existential graphExistential graph
An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote on graphical logic as early as 1882, and continued to develop the method until his death in 1914.-The graphs:...
s of Charles Sanders Peirce, which were one of the origins of conceptual graphs as proposed by Sowa.
In this approach, developed in particular by Dau (Dau 2003), conceptual graphs are conceptual diagrams rather than graphs in the sense of graph theory, and reasoning operations are performed by operations on these diagrams.
A 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 (Chein and Mugnier 2009),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 (problems on conjunctive queries in relational databases, constraint satisfaction problem, ...),
- the formalism is logically founded, i.e., it has a semantics in first-order logic 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 90's as a central notion, and complexity results and efficient algorithm have been obtained in several domains.
COGITANT and COGUI are tools that implement the GBKR model. COGITANT http://cogitant.sourceforge.net/ is a library of C++ classes that implement most of the GBKR notions and reasoning mechanisms. COGUI http://www.lirmm.fr/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
- Resource Description FrameworkResource Description FrameworkThe Resource Description Framework is a family of World Wide Web Consortium specifications originally designed as a metadata data model...
(RDF) - semantic networkSemantic networkA semantic network is a network which represents semantic relations among concepts. This is often used as a form of knowledge representation. It is a directed or undirected graph consisting of vertices, which represent concepts, and edges.- History :...
- knowledge representationKnowledge representationKnowledge representation is an area of artificial intelligence research aimed at representing knowledge in symbols to facilitate inferencing from those knowledge elements, creating new elements of knowledge...
- Concept mapConcept mapFor concept maps in generic programming, see Concept .A concept map is a diagram showing the relationships among concepts. It is a graphical tool for organizing and representing knowledge....
- conceptual schemaConceptual schemaA conceptual schema or conceptual data model is a map of concepts and their relationships. This describes the semantics of an organization and represents a series of assertions about its nature...
People
There is a lively worldwide conceptual graphs research community, which began with a series of seven annual workshops that met from 1986 to 1992. In 1993, the workshops were upgraded to the International Conferences on Conceptual Structures (ICCS), which have been held annually in Europe, Australia, North America and Asia (in 2010). Since the mid 1990s, the ICCS community has broadened its scope to include formal concept analysisFormal concept analysis
Formal concept analysis is a principled way of automatically deriving an ontology from a collection of objects and their properties. The term was introduced by Rudolf Wille in 1984, and builds on applied lattice and order theory that was developed by Birkhoff and others in the 1930s.-Intuitive...
(FCA) and other tools and languages for representing and reasoning about concepts. Following is a sample of some currently active researchers on conceptual graphs, many of whom combine CGs with FCA and other notations for logic.
- Galia Angelova – Bulgaria
- Jean-François Baget – France
- Tru Cao – Vietnam
- Michel Chein – France
- Madalina Croitoru – France
- Dan Corbett – USA
- Harry Delugach – USA
- David Genest – France
- Ollivier Haemmerle – France
- Adil Kabbaj – Morocco
- Pavel Kocura – UK
- Michel Leclère – France
- Robert Levinson – USA
- Philippe Martin – Australia
- Guy Mineau – Canada
- Aldo de Moor – The Netherlands
- Bernard Moulin – Canada
- Mehdi Mekni – Canada
- Marie-Laure Mugnier – France
- Ulrik Petersen – Denmark
- Heather Pfeiffer – USA
- Simon Polovina – UK
- Henrik Schaerfe – Denmark
- John Sowa – USA
- Albena Strupchanska – Bulgaria
- Gerd Stumme – Germany
Resources
- Conceptual Structures Home Page. Yearly international conferences. Old site: Conceptual Graphs Home Page
- Graph-Based Knowledge Representation (book)
- John F. Sowa
- Sowa, John F., "Laws, Facts, and Contexts: Foundations for Multimodal Reasoning"
- University of Aalborg Online Course
- CoGui
- Cogitant
- Formal Concept Analysis, Uta Priss, Napier University, UK.