Conceptual Graphs

Origin. John F. Sowa, "Conceptual Graphs for a Data Base Interface" (IBM Journal of Research and Development 20(4), 1976, 336–357), then the defining book Conceptual Structures: Information Processing in Mind and Machine (Addison-Wesley, 1984), presenting the graphs as a synthesis of Peirce's existential graphs and the semantic networks of AI (see Existential Graphs.md). The mathematical consolidation is due to the Montpellier school: Michel Chein and Marie-Laure Mugnier, "Conceptual Graphs: Fundamental Notions" (Revue d'Intelligence Artificielle 6(4), 1992, 365–406), and their book Graph-based Knowledge Representation: Computational Foundations of Conceptual Graphs (Springer London, 2009). The Conceptual Graph Interchange Format CGIF is Annex B of ISO/IEC 24707, Common Logic (2007; second edition 2018).

Models. Knowledge as labeled bipartite graphs — concept nodes for entities, relation nodes for the relations among them — with reasoning performed by graph operations rather than by formula manipulation, and a logical semantics kept in step through Sowa's operator φ, which sends each graph to a first-order formula. The simple graphs are a diagrammatic form of the positive conjunctive existential fragment of first-order logic, and their deduction relation is graph homomorphism, so the formalism identifies a knowledge-representation problem with a graph-theoretic and a database problem at once. Against its neighbours in this division: where Description Logic.md builds a variable-free concept language around decidable subsumption, conceptual graphs keep full n-ary relations and accept an NP-complete core; where Formal Concept Analysis.md derives its concepts from object-attribute data, here the concepts and relations are the vocabulary a modeller declares. The extensions with nested contexts and negation return to the formalism's ancestor, Peirce's existential graphs, and reach full first-order logic.

Formalism.

Vocabulary (support): a partially ordered set of concept types; a partially ordered set of relation types with fixed arities; individual markers and the generic marker *.

Simple graph: a finite bipartite graph; concept nodes labeled [Type: marker], relation nodes labeled (type) with ordered edges to the concept nodes filling their argument places. Normal form: each individual marker occurs on at most one concept node.

The operator φ (Sowa 1984): Each concept node with the generic marker becomes an existentially quantified variable; each node [T: x] contributes T(x); each relation node (r) on arguments x₁ … xₙ contributes r(x₁, …, xₙ). φ(G) = the existential closure of the conjunction; the type orders translate as implications T ⊑ T′ ↦ ∀x (T(x) → T′(x)).

Canonical formation rules (Sowa 1984): copy, restrict (replace a type by a subtype, or the generic marker by an individual), join (merge two concept nodes with the same label), simplify (remove a duplicate relation node). Each rule specializes: G derivable from H by the rules iff G ≤ H in the specialization order.

Projection: A projection from H to G is a graph homomorphism mapping concept nodes to concept nodes and relation nodes to relation nodes, preserving edges and decreasing labels in the type orders. G ≤ H iff there is a projection from H to G.

Complexity: projection (equivalently, deduction between simple graphs) is NP-complete — the same problem as conjunctive-query evaluation and containment (Chandra and Merlin, 1977; see Datalog.md).

Extensions: Nested graphs: concept nodes containing graphs as contexts. Negation: Peirce-style negative contexts over simple graphs give full first-order logic; Dau, The Logic System of Concept Graphs with Negation (Springer, 2003), is the worked-out system. Rules (if G then H), constraints, and typed nested variants, all in Chein–Mugnier 2009.

CGIF: a linear, machine-readable syntax for the graphs; a dialect of Common Logic, whose model theory it shares (ISO/IEC 24707, Annex B).

Symbols.

Metatheory. Projection is sound for the φ-semantics (Sowa 1984): a projection from H to G yields φ(G), with the type-order formulas, entailing φ(H). Completeness is Chein and Mugnier's (1992), with a normal-form condition: projection is complete only onto graphs in normal form, since two concept nodes carrying the same individual marker denote one object that a homomorphism cannot split. With that normalization, deduction between simple graphs coincides with homomorphism and with conjunctive-query containment, hence is NP-complete, and the simple graphs are deductively equivalent to the positive conjunctive existential fragment of first-order logic (Mugnier and Leclère, 2007). The identification transfers both ways: tractable subclasses of conjunctive queries are tractable projection classes, and Baget (2005) showed RDF entailment is a projection-style homomorphism problem, NP-complete with the same polynomial cases. For the full language, concept graphs with negative contexts are equivalent to first-order logic (Dau 2003), so their deduction problem is undecidable, with intermediate fragments such as simple graphs with atomic negation in between (Leclère and Mugnier, 2006). The ISO Common Logic standard gives CGIF a model theory shared with CLIF, making graph interchange a matter of notation rather than semantics.

Applies to. Knowledge representation and ontology modelling, as the graph-shaped alternative to description logics. Natural-language interfaces to databases, the application the formalism was built for (Sowa 1976). Ontology-mediated query answering, since simple-graph deduction is conjunctive-query answering (see Datalog.md). Semantic-web reasoning, through the projection reading of RDF entailment. Knowledge interchange, through CGIF in ISO/IEC 24707.

Limitations. The simple graphs express only positive existential conjunctions: no negation, no disjunction, no universal quantification, and nothing counted; with negative contexts the graphs are full first-order logic, undecidable, and projection is no longer the proof procedure. Completeness of projection requires normal form, so systems that must keep coreferent nodes separate need the extended coref-projection (Chein and Mugnier, ICCS 2004) rather than plain homomorphism. The NP-completeness of the core is a worst case over the graph structure, and the tractable classes are exactly those of conjunctive queries, not anything the diagrams add. The vocabulary orders only atomic types, so conjunctions of types and banned combinations need added machinery. And the diagrams add nothing to the semantics: a graph means what φ sends it to, so the cognitive claims of Sowa's subtitle — information processing in mind — are outside what the metatheory establishes.

© 2026 Lingenic LLC