Rens Bod and Remko Scha

### Deriving
optimal network diagrams by means of Structural Information Theory.

Introduction.

The problem
of automatically generating graphic information presentations consists
of two parts: (1) deciding on the interpretation schema that is
to be applied to the graphics, and (2) deciding on an actual graphic
object that represents the intended information if interpreted according
to this key. In this paper we focus on the second part of this problem.
Assuming that we have decided on the interpretation that is to be
used, it is often non-trivial to design a graphical object that
yields the correct information under this interpretation, and that
also avoids unwarranted suggestions. To assess the semantic validity
and pragmatic felicity of graphical information presentations, a
system must explicitly consider the perceptual Gestalts that the
graphics evokes.

For the sake
of concreteness, this paper focusses on one information presentation
problem: the automatic design of diagrams that represent networks.
It suggests that the diagrammatic representations of a network that
may be considered semantically correct are the ones that evoke a
set of Gestalts such that each of them, if a viewer applies the
contextually assumed interpretation key, (1) can be interpreted
as denoting the intended network, and (2) cannot be interpreted
differently. (We distinguish (1) and (2) because we are not sure
that interpretation keys that are in practice used for graphical
representations guarantee exclude ambiguity.) Among these representations,
we should prefer the one that avoids misleading suggestions to the
largest possible extent; a good candidate for this optimal diagram
is the one that is perceptually simplest.

To elaborate
this idea in mathematical and computational detail, we propose to
extend a formal model of Gestalt perception that was developed by
E. Leeuwenberg. This model computes a preference ordering on alternative
perceptual groupings of an input pattern, based on the information
load of their codings. The grouping that a person actually perceives
is the one with the lowest information load.

Within the
limits of its applicability, this model enables us to predict the
Gestalt that a graphical object will evoke in the person who sees
it. At the same time, Leeuwenberg's notion of information load constitutes
a plausible formal notion of simplicity that can be used as a criterion
for distinguishing between alternative diagrammatic representations
of one network. The ultimate success of this method depends, however,
on the adequacy of the visual coding language that is assumed. Leeuwenberg's
proposals about this suffer from some obvious limitations.

**Automatic
diagram design: Marks and Reiter.**

We consider
the problem of automatically generating a diagram that represents
a given network -- where we assume as given a definition of the
network as a collection of nodes and edges and predicates associated
with them, and we also assume as given a convention regarding the
graphical representation of the nodes (as squares, for instance),
of the edges (as line segments, for instance), and of the predicates
(as text labels, for instance). If so much is assumed, what is left
is essentially the problem of designing a reasonable lay-out (on
the screen or the page) of a not very large collection of connected
symbols.

Marks and Reiter
(1990) have drawn attention to the complexity of this problem. They
show that the space of lay-outs to be considered is extremely large,
and that different lay-outs may have significantly different properties;
for instance, many of them may evoke misleading suggestions in the
mind of the viewer. Marks and Reiter therefore propose a set of
preference rules to differentiate among the different lay-outs that
might be considered. These rules express plausible preferences between
alternative local decisions about the layout of a diagram; they
aim at avoiding "meaningless" perceptual groupings that
might arise because of gratuitous differentiations between the sizes,
the mutual proximities, and the mutual alignments of the graphical
symbols that constitute the diagram.

Marks and Reiter
have shown the importance of Gestalt perception phenomena for making
optimal decisions about lay-out design. But they do not attempt
to face the full extent of the Gestalt perception problem. Their
rules deal directly with the diagram elements, and don't refer explicitly
to the global Gestalt organization of the viewer's perception. In
the general case, this is not sufficient; the viewer does not assign
interpretations to just any part of the diagram, but only to the
constituents of the Gestalt which the diagram evokes. We cannot
take for granted that whatever is drawn on the screen is always
perceived as such.

Another limitation
of Marks and Reiter's system is that it is not clear how their rules
interact when there are conflicts between different preferences.
For demonstrations with a prototype system, one may sometimes be
able to choose applications which allow all preference rules to
be independent of each other; but a more generally applicable system
cannot rely on this. (Systems that try to account for Gestalt perception
by means of locally applicable preference rules always run into
this rule interaction problem. Another case in point is Lerdahl
and Jackendoff's theory about the perception of musical structure.)

In the remainder
of this paper, we sketch how a more principled method for automatic
lay-out design may be developed, based on Leeuwenberg's method of
formalizing Gestalt perception.

**Structural
Information Theory.**

Leeuwenberg's
(1969, 1971) coding theory starts out with a plausible intuitive
idea about Gestalt perception: when a person sees a visual pattern
as a certain Gestalt rather than another, this person has a mental
representation which (1) describes all or most of the details of
the visual pattern, and (2) assigns a particular constituent structure
to this pattern. (We may note an obvious analogy with the linguistic
notion of syntactic surface structure as applied to natural language
utterances.) To build a formal model of Gestalt perception, we must
therefore have (1) a formal way to code input patterns, and (2)
a formal way to code visual Gestalts which assign a specific constituent
structure to an input pattern. Assuming such coding systems, we
can then give a mathematical formulation to the problem of modelling
Gestalt perception: given an input code, what is the resulting Gestalt
code?

Leeuwenberg
has proposed a simple but powerful coding system, based on a view
on visual patterns that is now known as "turtle graphics".
The system he develops is limited to drawings that consist of discrete
straight line segments. This makes it possible to characterize input
patterns by means of an extremely simple system. A "primitive
code" of a two-dimensional line pattern is constructed by tracing
the contours of the pattern and successively noting the lengths
of line elements and the angles between them. Such a code thus consists
simply of a sequence: *angle1 length1 angle2 length2 ... angleN
lengthN.* (*"angle1"* specifies the angle of the
first linesegment with respect to a given axis; the other angles
are relative to the direction of the previous linesegment. Note
that this coding system does not specify *one *canonical coding
for a given input pattern; obviously, one pattern can be drawn in
many different orders. The system does, however, establish a well-defined
equivalence relation between alternative input codings; therefore
it is possible, in principle, to use an arbitrary input coding to
stand for this equivalence class.)

The language
that Leeuwenberg proposes for coding Gestalts is an extension of
the language that he uses to code raw input. Thus, concatenations
of pairs <angle, length> do not only serve as input codings,
but are also recognized as possible Gestalts. But, since regularities
in the input may give rise to specific perceived constituent structures,
the Gestalt coding language also provides means to encode such regularities.
For instance, out of arbitrary Gestalt codes *a, b, c* one
may build more complex codes by means of operations like iteration,
symmetry and alternation: **Iteration**(3,*a*) describes
the same pattern as *aaa*; **Symmetry**(*ab*) describes
the same pattern as *abba*; and **Alternation** (*bc,a*)
describes the same pattern as *baca.*

By employing
the higher order operations that such a Gestalt coding language
provides, an input pattern may be often be recoded in several ways.
Leeuwenberg's central assumption is, that Gestalt perception is
in fact this recoding process. His central claim about this process
is, that it results in the Gestalt that corresponds to the least
complex code -- where complexity (also called "information
load") is measured by simply counting the number of "primitive
elements" (i.e., elements from the primitive code of the input)
that still occur in the Gestalt code. For instance, if *a *and
*b* are both primitive elements, then *bbaaa *may be recoded
as **Iteration**(2,*b*) **Iteration**(3,*a*)
or as

*b* **Alternation**
(*ba,a*). The first recoding is preferred, because it contains
only 2 occurrences of the primitive elements *a* and *b,
*whereas the second recoding contains 4 such occurrences. This
predicts that the subpatterns defined by the subcodes **Iteration**(2,*b*)
and **Iteration**(3,*a*), i.e., *bb *and *aaa,
*will be perceived as constituents of the Gestalt evoked by *bbaaa.
*

A code with
a lower structural information load then alternative codes for the
same pattern, is called a *minimum code*. Coding theory thus
replaces the classical principles of Gestalt perception with a single
one: the perception of a pattern will result in an interpretation
that corresponds to a minimum code; the information load of what
is actually perceived is lower than the information load of anything
that could have been perceived alternatively. This reformulation
of the old law of Prägnanz is known as the minimum principle
of coding theory.

Leeuwenberg
often talks as if one input pattern evokes exactly one minimum code.
It is attractive to generalize Leeuwenberg's approach to one which
recognizes the possibility of a set of distinct minimum codes for
one input, if the information loads of several alternative analyses
which do not subsume each other lay close together. In the sequel
we sometimes assume such a generalization.

During the
past 20 years, Leeuwenberg and his co-workers have reported on a
number of experiments that tested predictions based on the minimum
principle. They investigated the disambiguation of ambiguous patterns,
embeddedness, closure and the perception of foreground and background.
On the whole, the results of these experiments confirmed the psychological
reality of an ordering of interpretations in terms of a measure
of perceptual simplicity computed on the basis of Structural Information
Theory. We have also used the minimum principle to solve proportional
analogy puzzles (Bod et al., 1993). A statistical generalization
of the minimum principle is one of the key ideas in a new performance
model of natural language processing (Scha, 1992; Bod, 1993).

**Coding theory
and the correctness of diagrams.**

The semantically
correct representations of a network are the ones that evoke a set
of Gestalts such that each of them, if a viewer applies the contextually
assumed interpretation key, (1) can be interpreted as denoting the
intended network, and (2) cannot be interpreted differently. It
should be emphasized here that is the Gestalts which get interpreted,
not what is physically on the screen or on the page.

Note that this
also means that an interpretation key cannot be simply inverted
to yield a set of "expressive rules" which map a network
definition onto the diagrams that represent it; in general, such
"expressive rules" can only have a heuristic status, in
that they define a set of structures that *might* represent
the diagram -- candidates for the diagram generation process to
consider.

Network diagrams
generated by reasonable expressive rules may induce Gestalt perceptions
with interpretations that are not compatible with the network they
are intended to represent. For instance, a model consisting of four
nodes, represented as squares, and four relations between these,
represented as line segments, may happen to be represented by a
diagram in which the squares are connected by the lines in such
a way that a fifth square is perceived. Such a diagram should obviously
be rejected, since it conveys the wrong information. To discover
this fifth square the system must apply coding theory.

A system such
as Marks and Reiter's does not explicitly deal with Gestalt structure.
If such a system is to avoid all possibilities for Gestalts with
unintended interpretations, it must use extremely conservative expressive
rules, which consistently avoid crossing lines and closely placed
elements. We feel it is important to try to develop a more generally
applicable approach, where a system may check candidate diagrams
for undesired interpretations, by computing the minimum codes for
each diagram, and applying the interpretation key according to the
structures defined by those minimum codes.

**Coding theory
and "conversational implicatures".**

Marks and Reiter
have drawn attention to a subtle but important problem: a diagram
that represents a network may, although it is strictly speaking "correct", be viewed as a poor and useless representation
because it creates misleading suggestions. On the analogy with certain
linguistic phenomena, such misleading suggestions have been described
as unwarranted "conversational implicatures". In particular,
Marks and Reiter point ou that it is worthwhile to avoid "meaningless" perceptual groupings that might arise because of gratuitous differentiations
between the sizes, the mutual proximities, and the mutual alignments
of the graphical symbols that constitute the diagram. What this
amounts to, is that the overall Gestalt that is evoked by the diagram
should not contain elements that do not have an interpretation in
the network domain. All structure that is there, should be meaningful.

It seems clear
that one cannot always avoid unwarranted implicatures by just obeying
locally operating preference rules. Since we are interested in properties
of the Gestalt evoked by the diagram, the system must in fact compute
this Gestalt. Leeuwenberg's work shows how we may approach this
problem.

Among the diagrams
that correctly represent a certain network, we are interested in
the diagram with a minimum of unwanted implicatures. Marks and Reiter
show that this may amount largely to a preference for diagrams without
gratuitous differentiation. We want to suggest now that a minimum
of gratuitous differentiation may correlate with minimum complexity
in Leeuwenberg's sense. The most regular diagram may be the optimal
one. To choose the least complex diagram we may therefore use the
minimum principle of Structural Information Theory. We may compare
the information loads of the perceived Gestalts of alternative possible
diagrams of a given network; the 'best' diagram is the one with
lowest information load.

Since the Leeuwenberg-coding
of a diagram contains all perceived structure, there must be a homomorphism
between this coding and the definition of the network. If, from
the point of view of the application, the network is not just a
set of nodes and edges with labels, but is composed in ameaningful
way out of particular subsets, then it is desirable that every subexpression
of a Leeuwenberg coding of a candidate diagram should correspond
to a substructure of the network. Also, further properties of (sub)codings
of a diagram should correspond to properties of the network. For
instance, if (some part of) a diagram contains symmetry, it is preferable
if this symmetry is also found in the properties of the network
itself. If not, the symmetry in the diagram is not meaningful with
respect to the model.

However, it
must be stressed that there are also conventions about representing
network-like structures in a two-dimensional space; these may work
in a different direction than the meaningfulness-constraint. Four
vertices tend to be represented in a square, whatever their connecting
edges be. "Defaults" like this must also be taken into
account.

**Conclusion.**

Summarizing,
we may describe our model as follows: First the class of diagrams
of a certain network model is defined by means of expressive mappings
(Marks and Reiter, 1990): nodes and edges in a network are directly
mapped to symbols in a network diagram. Secondly, a partial order
over this class is defined by means of the Information Load of the
codings of the diagrams. Finally, the diagram with lowest information
load whose possible interpretations are correct and maximally meaningful
with respect to the model is chosen.

As to the prospect
of implementing such a model, it is clear that comparing exponentially
many diagrams of a certain model takes exponential time. Thus, it
seems that calculating the 'best' diagram is NP-complete. In practice,
however, we are not interested in the absolutely simplest correct
representation of a network model. We might settle for a relatively
regular diagram without ambiguities and false implicatures. In order
to calculate such a diagram in a tractable way, we can apply techniques
like simulated annealing or Monte Carlo methods.

In conclusion,
we raise some basic questions: (1) do we capture all implicatures
with this method?, and (2) what extension of Leeuwenberg's coding
system provides an adequate description of visual Gestalts? These
questions should be answered by testing an implementation of the
method suggested here.

**References.**

Rens Bod, 1993:
'Using an Annotated Corpus as a Stochastic Grammar', *Proceedings
of the European Chapter of the ACL,* 1993, Utrecht.

Rens Bod, Mehdi
Dastani and Remko Scha, 1993: 'Solving Proportional Analogies using
Structural Information Theory', to appear in: *Proceedings of
the European Workshop on Case-based Reasoning,* Kaiserslautern.

Emanuel Leeuwenberg,
1969: 'Quantitative specification of information in sequential patterns'.
*Psychological Review,* **76**, 216-220.

Emanuel Leeuwenberg,
1971: 'A Perceptual Coding Language for Visual and Auditory Patterns'.*
American Journal of Psychology,* **83**, 307-349.

Joseph Marks
and Ehud Reiter, 1990: 'Avoiding Unwanted Conversational Implicatures
in Text and Graphics', *Proceedings AAAI '90,* Menlo Park,
CA.

Remko Scha,
1992: 'Virtual Grammars and Creative Algorithms', *Gramma/TTT* **1**(1).