Conceptual graph

Conceptual graphs (CGs) 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.
Contents
A graphical interface for firstorder logic
In this approach, a formula in firstorder 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.
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 graphs 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 graphbased knowledge representation and reasoning model
Key features of GBKR, the graphbased 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 firstorder logic and the inference mechanisms are sound and complete with respect to deduction in firstorder 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 [1] is a library of C++ classes that implement most of the GBKR notions and reasoning mechanisms. COGUI [2] 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 Framework (RDF)
 semantic network
 knowledge representation
 Concept map
 conceptual schema
References
 Chein, M., Mugnier, M.L. (2009),Graphbased Knowledge Representation: Computational Foundations of Conceptual Graphs, Springer, 2009. [3].
 Dau,F.  The Logic System of Concept Graphs with Negation and Its Relationship to Predicate Logic, volume 2892 of LNCS, Springer, 2003.
 Sowa, John F. (1984), Conceptual Structures: Information Processing in Mind and Machine, AddisonWesley, Reading, MA, 1984.
 Sowa, John F. (1976), "Conceptual Graphs for a Data Base Interface", IBM Journal of Research and Development 20(4), 336–357, July 1976. PDF file.
External links
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 analysis (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
 JeanFranç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
 MarieLaure 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
 GraphBased 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.
Categories: Knowledge representation
 Diagrams
 Applicationspecific graphs
Wikimedia Foundation. 2010.
Look at other dictionaries:
Conceptual Graph — Konzeptgraphen oder Begriffsgraphen, abgekürzt Kg (englisch conceptual graph, CG) sind ein von John F. Sowa entwickeltes logisches Sprachsystem für die semantische Beschreibung von abgegrenzten Wissensdomänen. Neben der üblichen Darstellung von… … Deutsch Wikipedia
Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges … Wikipedia
Conceptual Graphs — Konzeptgraphen oder Begriffsgraphen, abgekürzt Kg (englisch conceptual graph, CG) sind ein von John F. Sowa entwickeltes logisches Sprachsystem für die semantische Beschreibung von abgegrenzten Wissensdomänen. Neben der üblichen Darstellung von… … Deutsch Wikipedia
Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia
Conceptual clustering — is a machine learning paradigm for unsupervised classification developed mainly during the 1980s. It is distinguished from ordinary data clustering by generating a concept description for each generated class. Most conceptual clustering methods… … Wikipedia
GRaPHInt — The Genome based Research and Population Health International Network (GRaPH Int) is an international collaboration of experts and researchers focused in the area of population health. The principal goal of the network is to promote the… … Wikipedia
Graph of desire — The graph of desire is a conceptual tool from the psychoanalytic theory of Jacques Lacan.HistoryLacan devised numerous quasi mathematical diagrams to represent the structure of the unconscious and its points of contact with empirical and mental… … Wikipedia
List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia
Concept Graph — Konzeptgraphen oder Begriffsgraphen, abgekürzt Kg (englisch conceptual graph, CG) sind ein von John F. Sowa entwickeltes logisches Sprachsystem für die semantische Beschreibung von abgegrenzten Wissensdomänen. Neben der üblichen Darstellung von… … Deutsch Wikipedia
Existential graph — An existential graph is a type of diagrammatic or visual notation for logical expressions, proposed by Charles Sanders Peirce, who wrote his first paper on graphical logic in 1882 and continued to develop the method until his death in 1914.The… … Wikipedia