=Paper=
{{Paper
|id=Vol-2378/shortAT2
|storemode=property
|title=Biseau: An Answer Set Programming Environment for High-Level Specification and Graph Visualization applied to FCA
|pdfUrl=https://ceur-ws.org/Vol-2378/shortAT2.pdf
|volume=Vol-2378
|authors=Lucas Bourneuf
|dblpUrl=https://dblp.org/rec/conf/icfca/Bourneuf19
}}
==Biseau: An Answer Set Programming Environment for High-Level Specification and Graph Visualization applied to FCA==
https://ceur-ws.org/Vol-2378/shortAT2.pdf
Biseau: An Answer Set Programming
Environment for High-Level Specification and
Graph Visualization applied to FCA
Lucas Bourneuf
Univ Rennes 1
lucas.bourneuf@inria.fr
Abstract. When studying mathematical relations, soon arise the need
to visualize the resulting structures. This often leads to tedious devel-
opment or time consuming copy-pasting of visualization routines. This
paper presents Biseau, a programming environment aiming at simplifying
the visualization task. Biseau takes advantage of Answer Set Program-
ming, enabling user to write, maintain, debug and reuse close to speci-
fication encodings, and eventually obtain a graphical display of mathe-
matical relations. This paper shows as a use-case how Formal Concept
Analysis can be efficiently described at the level of its properties, without
needing a costly development process. Biseau uses the graphviz software
to render in real-time the calculated graphs to user, thanks to an Answer
Set Programming to (graphviz) dot compiler. More generally, it is shown
that Biseau leads on to a general method to prototypes new software
features, which could unify the development process before the efficiency
race. As such, it reproduces the core results of existing tools like LatViz
or In-Close. We hope that it will help to speed up the prototyping process
and simplify the exchange and reuse of proof of concept implementations.
1 Introduction
Software environments oriented towards data mining use efficient implementa-
tions of data structures and their visualizations. For instance, in Formal Concept
Analysis, LatViz is a lattice visualization software, allowing end-user to explore
the lattice structure efficiently [1]. In-Close implements efficient concept mining
algorithms and provides a concept tree visualization of contexts [2]. All these
softwares work with a formal model that provides an abstract view and a fixed
search space on the data. Users cannot work on the model itself, they are ex-
pected to use the implemented methods, not to design new ones. In contrast,
Biseau is a software focused on designing and exploring elements of the data
Copyright c 2019 for this paper by its author. Copying permitted for private and
academic purposes.
2 L. Bourneuf
structure, rather than the data itself [3]. It is a general purpose model builder
that relies on graphs and logic languages.
Graphs are rendered in multiple ways. Biseau uses dot, a generic graph de-
scription language specified by the graphviz software, which provides a gallery of
visualization engines [4]. Together with a graph data structure, Biseau offers a
logical view of the associated exploration methods. A pure declarative language
is used for this purpose, Answer Set Programming (ASP). It allows users to
transcript the formal properties they are looking for in a straightforward way.
ASP has already been applied to FCA to accomplish expressive query languages
for formal contexts [5, 6].
Biseau is supplied with a graphical user interface and a command line in-
terface to write an ASP encoding, from which the dot files and the resulting
visualizations are generated. The main interest of Biseau is therefore to build
graph visualizations directly from formal relations. As such, it is not dedicated
to lattices only, and their (efficient or scalable) exploration, as performed by
specialized software such as LatViz or In-Close. It provides instead a general
purpose programming environment that is able to visualize graph structures.
Biseau is therefore suited for rapid design and easy testing of extensions in the
framework of FCA. It is freely available under the GNU/GPL license1 .
2 From ASP to Dot With Biseau
Biseau implements an ASP to dot compiler. The graph is therefore defined in
intension: instead of describing manually all objects and properties, the user
specify their definitions, and let the ASP solver infers all necessary relations.
A given ASP encoding yields so-called "stable models" consisting of true
facts, which can be represented by atoms like link(woman,human). For each
stable models found from the ASP user encoding, Biseau will convert atoms
into dot lines. For instance, the ASP atom link(woman,human) will translate
to woman -> human in the dot output. This controlled vocabulary will be only
partially explored in Section 3, but note that it maps the full dot language,
including colors, shapes, and general graph options. A complete documentation
is available online2 .
Biseau internal process can be seen as a compilation from ASP models to
dot, then from dot to image (the last one being delegated to graphviz software).
3 Build and Visualize Galois Lattices With Biseau
This section shows how to build FCA basic mathematical relations in order to
get a visualization of the Galois lattice in Biseau. The context in Table 1 will be
used as case study, encoded in ASP using rel/2 atoms.
1
https://gitlab.inria.fr/lbourneu/biseau
2
https://gitlab.inria.fr/lbourneu/biseau/blob/master/doc/user-doc.mkd
Biseau: An Environment for Specification and Visualization 3
male female adult child human
man × × ×
woman × × ×
boy × × ×
girl × × ×
Table 1: Formal context of human relations. It can be encoded in ASP in atoms such
as rel(man,male) and rel(woman,adult).
3.1 Mining the Formal Concepts
In a formal context defined by objects O, attributes A, and the binary relation
R ⊆ O × A, a formal concept is a pair (X, Y ), such as:
X = {x ∈ O |(x, y) ∈ R ∀y ∈ Y } (1)
Y = {y ∈ A |(x, y) ∈ R ∀x ∈ X} (2)
Where X ⊆ O and Y ⊆ A. The search for formal concepts in ASP can be
expressed like in the above definition:
1 ext(X):− rel(X,_) ; rel(X,Y): int(Y).
2 int(Y):− rel(_,Y) ; rel(X,Y): ext(X).
rel(X,_) fixes variable X as the first term of a relation, i.e. an object. No-
tation rel(X,Y): int(Y) ensure that there is a relation between X and all at-
tributes Y of the intent. As a consequence, the extent ext(X) holds for all objects
X in relation with all attributes of the intent. The second rule is a symmetric
definition for the concept’s intent. ASP search comes with the guarantee that all
minimal fixed points will be enumerated. Therefore, each answer set is a different
concept, or the supremum or infimum (where extent or intent are empty sets).
These models/concepts are aggregated in order to produce an encoding contain-
ing ext/2 (and int/2) atoms, where ext(N,A) (int(N,A)) gives an element of
N-th concept’s extent (intent).
3.2 Galois lattice
A Galois lattice is defined by the partial order on the concepts, i.e. a graph
with concepts as nodes, and an edge between a concept and its successors in the
ordering:
1 % Shortcut to infimum, supremum and concepts identifiers.
2 c(N):− ext(N,_). c(N):− int(N,_).
3 % Ordering of two concepts: the first has all objects of the second.
4 contains(C1,C2):− c(C1) ; c(C2) ; C1!=C2 ; ext(C1,X): ext(C2,X).
5 % Concepts linked to another in the Galois Lattice .
6 link(C1,C3):− contains(C1,C3) ; not link(C1,C2): contains(C2,C3).
7 % Annotate nodes with extent and intent.
8 annot(upper,X,A):− ext(X,A). annot(lower,X,B):− int(X,B).
4 L. Bourneuf
These lines yield the visualization shown in Figure 1. Line 2 enables the
access to the infinum, supremum and concepts with one atom. Line 4 yields
pairs of concepts that are included, based on their extent. Line 6 ensure that a
link exists in the lattice between a concept C1 containing another concept C3
if there no link between C1 and a concept C2 smaller than C3. The annot/3
atoms are a Biseau convention (as link/2), allowing us to print the extent and
intent of each concept, respectively above and below the node.
3.3 Reduced Labelling
The reduced labelling of a lattice is computed as the set of specific objects and
attributes for each concept. This can be defined as specext/1 and specint/1
atoms in ASP, using the following lines along the search for formal concepts in
section 3.1:
1 % An outsider is any object or attribute linked to
2 % an attribute or object not in the concept.
3 outsider(X):− ext(X) ; rel(X,Z) ; not int(Z).
4 outsider(Y):− int(Y) ; rel(Z,Y) ; not ext(Z).
5 % The specific part of each concept contains no outsider.
6 specext(X):− ext(X) ; not outsider(X).
7 specint(Y):− int(Y) ; not outsider(Y).
With these lines and the collapsing into one model described in section 3.1,
we obtain specext/2 and specint/2 atoms, describing the AOC poset elements,
attached to each concept. We can then replace the previously defined annot/3
definitions in section 3.2 with the reduced labelling:
1 annot(upper,X,A):− specext(X,A). annot(lower,X,B):− specint(X,B).
Using these definitions, Biseau produces the Figure 2.
4 Discussion & Conclusion
The main contribution of Biseau lies into the straightforward use of the structure
specifications to produce a simple code and a proper visualization. To achieve
that feat, Biseau is compiling a controlled subset of ASP atoms to dot lines,
effectively building a dot formatted file that is compiled to an image by graphviz
software. This enables definition of graphs in intension and gives an abstract
access to dot expressions, letting the user focus on the fast prototyping of data
exploration and the elaboration of mathematical properties.
In other words, Biseau allows user to work on the model in which data are
processed, instead of providing an implementation of a single model to be used
on particular data, as usually performed in field-specialized softwares.
In this paper, FCA was implemented with Biseau with a focus on the ASP
implementation, although more generally it can be extended with scripts, units
of ASP or Python to add to (or run on) the model encoding. Scripts may expose
some options to tune their behavior, and integrate other programs implementing
Biseau: An Environment for Specification and Visualization 5
Fig. 1: Visualization of the Galois Lat- Fig. 2: Visualization of the Galois Lat-
tice of context in Table 1 using Biseau, tice of context in Table 1 using Biseau,
with extent and intent shown for each with reduced labelling.
node/concept.
standard operations efficiently, such as In-Close for concept mining. When a
Biseau encoding is correctly specified, it is basically a working proof of concept,
which can be distributed as a standalone script, or adapted into a stand-alone
program, iteratively replacing ASP parts by other programs.
Biseau current state is a fully working proof of concept, although it misses a
lot of features typically found in text editors and IDEs, that could help user to
write and maintain the ASP code. It also runs into ASP typical limits, such as
the absence of float numbers handling and scaling problem.
Future work will focus on Biseau as a proof of concept generator, through the
automatic generation of standalone programs, and built-in embedding of other
paradigms such as linear programming.
References
1. M. Alam, T. N. N. Le, and A. Napoli. Steps towards interactive formal concept
analysis with latviz. In FCA4AI@ECAI, 2016.
2. S. Andrews. In-close, a fast algorithm for computing formal concepts. In Interna-
tional Conference on Conceptual Structures, 2009.
3. L. Bourneuf. An Answer Set Programming Environment for High-Level Specification
and Visualization of FCA. In FCA4AI’18 - 6th Workshop “What can FCA do for
Artificial Intelligence?”, pages 1–12, Stockholm, Sweden, July 2018.
4. E. R. Gansner and S. C. North. An open graph visualization system and its ap-
plications to software engineering. Softw. Pract. Exper., 30(11):1203–1233, Sept.
2000.
5. P. Hitzler and M. Krötzsch. Querying formal contexts with answer set programs. In
Proc. of the 14th Int. Conf. on Conceptual Structures: Inspiration and Application,
ICCS’06, pages 260–273, Berlin, Heidelberg, 2006. Springer-Verlag.
6 L. Bourneuf
6. S. Rudolph, C. Săcărea, and D. Troancă. Membership constraints in formal concept
analysis. In Proc.of the 24th Int. Conf. on Artificial Intelligence, IJCAI’15, pages
3186–3192. AAAI Press, 2015.