Formal Interpretation of Graphs

Graphs are simple structures composed on nodes and arcs that are used pervasively in computer science as well as many other desciplines. However, their appearantly simple structure leads to a huge breadth of interpretation. For example, what is the difference between a typed-link graph and a bipartite graph? How does a graph map onto a hypertext? What is the nature of typed (or untyped) nodes and typed (or untyped) links in a graph? This paper addresses some of these issues.

WARNING: Work in progress.

Background

Simple Classification of Typed and Untyped Graphs

Graphs, in their simplest form, are merely collections of points (called nodes) with arrows or lines (called directed or undirected arcs) between specific nodes.

Nodes may or may not be more than just points. Typically they are descriptively labeled with the name of the object, class, concept or state they are intended to represent. Nodes may also be typed with the class of object they represent. Typically, type is indicated by some visual attribute such as shape of label surround, color, or font.

Arcs may or may not be more than just lines or arrows. Although they may be labeled, it is not typical that they are labeled with some individual designation (as nodes typically are), but rather, if they are labeled, it is usually with their type. Typed arcs may also be destinguished by visual attributes such as line style, arrow head style, or color.

Given these two attributes, labeling and typing, on both nodes and links (this paper does not deal with attributes like cyclicity and hierarchy), one would expect 2⁴ or 16 classification of graphs. A few simple examples follow.

Some Applications of Graphs

Graphs are used in a very wide range of activity, spanning both informal and formal uses. Examples of informal uses include concept mapping in education where teachers use labeled graphs to convey "non-linear" information to students, and students construct similar graphs so evaluated that the teacher can evaluate their understanding of the topic. For example, Gowin [Gowin ??] documents a student's concept map about water. Another slightly more disciplined but still informal use concept maps, is in the Graphical Issue-Based Information Systems (gIBIS) [Conklin 87], an example of which is pictured in the figure above about productivity and moral.

Formal uses of graphs are amenable to computer support and interpretation. For example, Gaines' KDraw system [Gaines 91] is a graphical interface to the CLASSIC knowledge representation language [Borgida 89]. In this graphical systems, concepts, roles, individuals, constraints, and rules are visually distinct node types; while the various relationships among the nodes, such as is-a, exception, and has-constraint are expressed as arcs between the nodes. The example demonstrates that, although the arcs are not labeled and are not (for the most part) visually distinct, they are implicitly typed as per the following diagram (which is also a graph, but not a KDraw graph!):

Another formal graph is Conceptual Graphs [Sowa 84]. Conceptual Graphs is also a knowledge representations intended to map onto first-order logic. These graphs are bipartite where concept nodes (boxes) are always separated from one another by relation nodes (circles). The example illustrates the sentince "Tom beleives Mary wants to marry a sailor." Here, the arcs are untyped and unlabeled, but the nodes are typed and labeled. But note that there are two levels of typing: the system types concept and relation are quite distinct from the user types such as PERSON and SAILOR. Although this it may not be quite as obvious from the example, the KDraw CLASSIC system exhibits a similar property. This is a critical distinction.

A 3-level Theory of Typed Graphs

There is little doubt that there is a distinction between objects and types (although the distinction may sometimes be contextual). For example, in object oriented programming languages, there is firm distiction between classes and instances of the class. The distinction is blurred by languages that have metaclasses which describe classes which are instances of metaclasses. Furthermore, the notion of classes and objects themselves are constituents of a higher order of type, implicit in the programming language, which needs to be modeled. One may therefore choose to divide types into two subsection: a system level, which corrosponds to the implicit assumptions of the reprentation system; and a user level, which corrosponds to the types that are manipulatable by the user. Thus, there are three partitions (or levels) over the constituents of a graph system:

System types
User types
Objects

The system type level is the base theory on which the particular domain (e.g. object oriented programming languages, CLASSIC, Conceptual Graphs, or gIBIS) is based on. That is, the system level constitutes the fundamental and minimal principles on which a computation agent relies to interpret any particular statement in the domain of discourse. In the OO programming language domain, the system type level contains the concepts of class and object. In the CLASSIC domain, it contains primitive, concept, individual, role, rule, and constraint as well as the relations between them. In the the Conceptual Graphs domain it, contains concept and relation. In the gIBIS domain, it contains issue, position, and argument as well as the relationships such as responds-to and objects-to.

The user type level constitutes type objects that are all subtypes of one (or possibly more) of the system types. The user types may be extended, modified, and deleted by the user just as objects may be be created, modified, and deleted by the user. Manipulating user types does not interfer with a computational agent's ability to parse the statement expressed by the graph because all the user types are can be understood by virtue of being subtypes of one (or more) of the system types. The statement may be nonsensical, but it is parsable. In the OO programming language domain, the user type level may contain a list-of-integer, which is a subtype of the system type class. In the CLASSIC domain, it may contain employee and salary, which are subtypes of system types primitive and role respectively (see the forman example). In the the Conceptual Graphs domain it, may contain PTNT and PERSON, which are subtype of system types Relation and Concept respectively (see the example). In the gIBIS domain there are no user types because the this system is restricted to a static set of types which the user may not manipulate -- all types are system types.