Formal Concept Analysis (FCA) aims at classifying a set of objects described by Boolean attributes as a concept lattice. Among the various FCA extensions, Relational Concept Analysis (RCA) supports multiple binary relationships between several sets of objects. Using such relational data, RCA builds interconnected conceptual structures, i.e. concept lattices or AOC-posets. Analyzing data can benefit from exploring these interconnected structures by navigating from one concept to another. Navigation can be performed within the same structure through the classification links or from one concept of a conceptual structure to a concept of another one through one of the relations linking the lattices. This paper presents RCAviz1, an online tool which aims to support such navigation. Once the user has selected a subset of objects and attributes as a starting point for navigation, RCAviz presents the associated concept and its close neighbors. Each concept includes the objects and attributes it introduces. The user can then navigate, i.e. zoom and pan the current view, and move from one concept to another. Additional views show the previous and next conceptual structures. The history allows the user to browse its navigation.
Formal Concept Analysis (FCA) aims at classifying a set of objects described by Boolean
attributes as a concept lattice [
Among the extensions of FCA, Relational Concept Analysis (RCA) supports multiple binary relations between several sets of objects. As output, RCA builds conceptual structures (one per object set) interconnected by relational attributes, that embed the inter-object relations provided as input. Analyzing multi-relational datasets with RCA may benefit from exploring these interconnected structures by navigating from one concept to another. This navigation is therefore performed within the same conceptual structure, through the classification links, or from one concept of a conceptual structure to a concept of another one, through one of the relations linking the lattices.
FCA and RCA present a strong interest when querying a dataset using a set of attributes.
In addition to the objects that respond to the query, they provide the classification of these
objects [
Several authors investigate the potential ofered by the visualization for assisting exploring,
querying, and analyzing a classification produced by FCA [
Section 2 briefly introduces FCA and RCA basics, and a small RCA navigation example to illustrate the main features expected for a navigation tool. Section 3 presents the visualization and navigation features of RCAviz. in Section 4, we present related work on FCA and RCA visualization and exploration. Section 5 concludes with a summary of the work and a few perspectives.
This section briefly introduces FCA and RCA through an example inspired by the Knomana
project [
FCA in a nutshell FCA input is a formal context (FC) which includes a binary relation that connects each object with each of the attributes it has. E.g. the FC Plant presented in Table 1 describes four plants by their family and a few characteristics like being aromatic or comestible. FCA builds formal concepts on top of the FC and organizes these concepts as a conceptual structure. A formal concept is a maximal group of objects (extent) sharing a maximal group of attributes (intent). For instance, in Table 1, as all the plants of the group 9 = {ℎ , , } share all the attributes 9 = { , , , , , } , 9 = ( 9, 9) is a concept. The conceptual structure reflects group inclusion and highlights concept specialization. The top right part of Figure 1 presents an example of specialization of plant concepts. Concept 11, which associates 11 = { } with its common attributes 11 = 9 ∪ { } is a subconcept of 9, with 11 ⊇ 9 and 11 ⊆ 9. This figure also presents relational attributes, specific to RCA (i.e. initiated using the quantifier ∃), which are explained here after.
RCA in a nutshell RCA extends FCA to datasets that conform to the entity-relationship
model [
RC isFoundIn aspergillusFlavus aspergillusParasiticus aspergillusOchraceus aspergillusTamarii
Pest aspergillusFlavus aspergillusParasiticus aspergillusOchraceus aspergillusTamarii
RC treats cinnamomumZeylanicum chromolaenaOdorata
aspiliaAfricana ageratumConyzoides x Namxibia SouthernAfrica Nigeria Bexnin x
x Navigating within linked conceptual structures The above example is used to reveal the gradual navigation needs of the RCA outputs4. Let us suppose the user wants information about the pests that attack peanuts. Pest Concept 13 introduces and is therefore the natural entry point. Pests of 13 extent are Aspergillus ochraceus and Aspergillus parasiticus. To know the localization of these pests, the user needs to follow the relational attribute ∃ ( 20) . This attribute leads to Country concept 20 which groups Western Africa countries, i.e. Benin and Nigeria. In 20 , the relational attributes containing point to plant concepts. Going towards the Plant concept 21 indicates that 20 countries host Aspilia africana or Chromolaena odorata. 21 comports the relational attribute ∃ ( 13) , meaning that its plants treat at least one of the Aspergillus pest species that attack peanuts. It can be interpreted that way: Aspergillus species that attack peanuts are observed in Western Africa countries and are treated by plants that can be found in the countries of this region. It can be interesting here, for the user, to go back by choosing Concept 20 to look at relational attributes ∃ 6 or ∃ 9 . Choosing ∃ 9 and going to 9 , the user can see that these Western Africa countries possess plants that have characteristics that are close to the plants treating Aspergillus species attacking peanuts. This is the case of Ageratum conizoïdes which is analyzed by going to sub-concept 11 . This plant is toxic and has an antidysenteric efect, it may have antibacterial properties. These characteristics may suggest that common chemical compounds could be shared between these 3 plant species. This navigation therefore brings a research hypothesis that domain experts may study through new experimental research: can Ageratum conizoïdes be used to control Aspergillus species (i.e. Aspergillus ochraceus and Aspergillus parasiticus) attacking peanuts? 4A navigation for this example using RCAviz is presented at https://rcaviz.lirmm.fr/documentation.html#examples. A video on YouTube is also proposed.
If the answer is true, this then would mean that farmers in Western Africa have an additional local plant that can be used for controlling Aspergillus ochraceus and Aspergillus parasiticus.
This brief navigation example illustrates the main needs of a user: (i) selecting an attribute (or an object) to initiate the navigation, (ii) visualizing the neighborhood of a concept to be able to choose the next step and do not end with an empty solution, (iii) moving from one concept to a sub-concept (or a super-concept) in the same conceptual structure, (iv) jumping to a neighboring conceptual structure using a relational attribute, and (v) backtracking easily.
In the previous section, we presented the extracted data structure using an RCA classification.
As can be seen in Figure 1, this structure can be modeled as a set of Directed Acyclic Graphs
(DAG), each DAG corresponding to a context (here, one DAG for plants, one for pests and one
for countries). There is an extensive literature on the visualization of DAG (see [
RCAviz is designed to meet these requirements. The visualization consists of an initial view allowing to select the starting concept, the Concept Selector, and two coordinated views: (1) the Explorer allows to navigate step-by-step and (2) the History allows to visualize the navigation history.
Concept Selector The Concept Selector is the first view displayed when one launches RCAviz. It is designed to meet the requirement [R1]. It first allows to upload a data file. Once the file is uploaded, the user can choose a context, i.e. one of the DAGs of the dataset. Then appears the list of objects, the list of attributes and the list of concepts, as shown in Figure 2. The user can select one or more objects and one or more attributes. The selection of these elements updates the other lists according to the logical operators used, and in particular updates the list of the corresponding concepts on the right. One can for example display the concepts containing (object A and object B) and (attribute C or attribute D). When the list of objects and attributes is long, a search field allows the user to easily find the elements. The user also can select or deselect all the elements of each list. The list of selected items is displayed when hovering over Selected. When an object or an attribute is selected, the corresponding introducer concept number on the right panel appears in bold face. Once the user has found an interesting concept, they can select it from the list on the right and launch the Explorer and the History. It may seem critical to select a concept according to its index number and the selected associated objects and attributes. Thus, in a future work, we plan to show additional information on the listed concepts, such as their introduced objects and introduced attributes, or their whole extent and Explorer Figure 3 shows the History (top panel) and the Explorer (bottom). The Explorer consists of three sub-views. The central panel displays the selected concept in the center and its neighborhood above (children in the DAG) and below (parents in the DAG) [R2]. Each concept is represented as a colored rectangle composed of stacked boxes. The id is shown at the left corner of the top box. The introduced objects are presented in the box entitled “Objects”. Simple (i.e. non relational) introduced attributes appear in another box. The introduced relational attributes, when they exist, appear in the box at the bottom of the concept. When there are several relational attributes with the same relation, they are grouped by relation. In addition, when there are many relational attributes with the same relation, only their number is shown in order to save space, and thus they are not clickable.
For example, the concept 20 in the country DAG in Figure 3 has links to the concepts 6, 9, and 21 in the plant DAG and 13 in the pest DAG. The user can navigate step-by-step by clicking on the concepts [R3]. For example, if they click on the concept 23, it is positioned in the middle of the view and its parents and children are displayed below and above. ⊤, for the top (resp. ⊥ for the bottom) at the top right of a concept means that it has no parents (resp. no children). To facilitate the navigation, an opposite link, e.g. “isFoundIn-opposite”, is provided for each relational attribute. These opposite links do not correspond to a isFoundIn-opposite formal context which would be the reverse of isFoundIn. In a future work, additional information on each concept (intent, extent, etc.) will be provided to make the navigation easier.
Each DAG is represented by a color. We use a categorical color scale adapted to the representation of nominal variables [14]. In our example, the country DAG is shown in blue, the plant DAG in red, and the pest DAG in green. When the user hovers over a link, the concept in the corresponding DAG is displayed on the right panel. In Figure 3, the mouse is positioned on the red link 21, the corresponding concept is displayed with its neighborhood on the right panel. When the user clicks on the link, the left DAG is positioned in the central panel [R3] and that of the central panel is positioned in the right panel. We thus keep track of the previous exploration step [R4].
The concepts that have already been explored appear with lower brightness than the other concepts [R4]. In Figure 3, we can see that all the concepts have already been explored except one of the red DAG at the bottom left.
Finally, it is common to have a high number of parents or children. Showing all of them induces visualization and navigation issues. Therefore, if the number exceeds 5, we display a single ”super-concept”. When the user clicks on it, a pop-up displays a view similar to the Concept Selector. The user can then select one or more concepts which, after validation, are displayed in the central panel. In this release, we choose a top to bottom representation of the specialization relation as this is the common representation of partial orders by Hasse diagrams. Alternatively, we may explore a left to right representation, where a concept will be on the left of its sub-concepts, to show more sibling concepts as they will be vertically organized. History We have seen that a part of the path leading to the concept displayed is available in the left panel of the Explorer. The brightness of the concepts also makes it possible to know if a concept has already been explored. However, these functionalities do not fully meet the requirement [R4]. We therefore complete them with a view entirely dedicated to [R4]: the History. As shown in Figure 3, the history consists of two parts: a colored line at the top and a list of concepts below.
The colored line is made up of segments, each segment representing an explored concept. The color represents the DAG of the concept. The length of the line adapts to the width of the visualization so that all the concepts explored are visible. Therefore, the more concepts the user has explored, the smaller the segments representing those concepts are. The user can see if the current concept of the Explorer has already been explored with a small triangle placed above each segment representing this concept. For example, in Figure 3, we see two triangles, one on the last segment representing the concept displayed in the Explorer and one on a previous segment: this means that the current concept has already been explored once during the navigation.
The list of concepts explored with their id is displayed under the colored line. This list can be long, a horizontal slider is therefore activated when the available space is not enough to display all of them in the view. The concepts are represented by colored rectangles according to the DAG they belong to. An arrow connects two concepts if the user has moved from one to the other by navigating step-by-step. If the user clicks, in the History, on a previously explored concept, it is displayed in the Explorer and a vertical bar is used in the History to show that the sequence was not produced by a navigation step-by-step. When the user hovers over a concept, a small red cross appears at the corner. It can be used to remove this concept from the History. As selecting a concept only according to its id may be tricky, additional information (e.g. intent/extent) will be presented in a future release.
Finally, the user can save the state of their navigation as well as the history by clicking on the save button in the top bar. They can then load the file thus produced to resume their exploration. Implementation RCAviz is a web platform developed in HTML, CSS and JavaScript. The panels and the visualizations are made using the D3.js5 [15] library. Saving the history file is made possible with the FileSaver6 library. The tool is available online7. An extensive documentation containing sample datasets is available to allow anyone to use the tool with the samples or with their own datasets.
Visualizing and exploring in FCA tools There have been a lot of proposals to visualize
and explore the conceptual structures. For space reasons, we only mention some of them to
highlight the main followed directions. Some proposals visualize the structure itself such as
Conexp [16], Latviz [17], Carve (based on a decomposition tree) and DAnCe (with concept
enumeration guided by the user) [18], and the approach by expandable and collapsible concept
trees [19]. Additional views can be provided, like in RV-xplorer [20], with pie-charts showing
local view on a concept, its content and its neighboring, and statistics on the next levels to
guide the user. Other approaches do not disclose the DAG structure, such as CREDO [21] or
SearchSleuth [22] for web queries which show links and terms that can be clicked to navigate on
the underlying lattice, e.g. for specializing or generalizing the query; SORTeD [18] where terms
can be added or removed; SPARKLIS [23] for RDF data which uses lists of urls, types, operators;
or ConceptCloud [
Visualizing in RCA tools Only four tools implement RCA: Galicia, eRCA8 improved in Galatea9, RCAexplore, and a Cogui10 plugin. This last plugin was also converted as a Java library named FCA4J11. RCAexplore and Cogui have the largest functional features regarding the number of input/output and accepted quantifiers. Regarding the visualization, Galicia provides an advanced lattice representation (tridimensional, graph layout built with a force algorithm) but no specific operators to navigate within a structure or from one structure to another. RCAexplore provides a visualization tool relevant for navigating small-size structures. Compared to Galicia, eRCA/Galatea, and Cogui, RCAexplore provides a browser enabling the navigation between concepts textually described (no visualization), shows the whole structure but does not enable zooming. Concepts and relational attributes are clickable to go from one structure to a neighboring structure, but selecting a focus concept and going step-by-step using local views is not proposed. Finaly eRCA/Galatea, RCAexplore, and Cogui produce outputs in the dot file format, which can be visualized or transformed using Graphviz 12. In RCAviz, several visualization panels show local views, and allow the user to know which neighboring structure has been previously accessed or can be accessed through relational attributes. The step-by-step navigation is done by clicking on the relational attributes. The colors help to distinguish the diferent sets of objects. Table 2 synthesizes the main features of RCA tools regarding our requirements. This paper presents RCAviz, a web platform devoted to visualize and navigate within relational conceptual structures computed using RCA. First uses showed the relevance of the features adopted to navigate within and between conceptual structures. These uses also enabled to identify a need for additional features to be integrated, e.g. specifying the path length to be shown, presenting the complete conceptual structures when they are small, local computation as in [26], visualizing the ER model, showing a larger concept neighborhood, or expressing
9https://github.com/jrfaller/galatea 10http://www.lirmm.fr/cogui/ 11https://www.lirmm.fr/fca4j/ 12https://graphviz.org/
Galicia eRCA/Galatea RCAexplore
RCAviz x
Textual descr. only (concept browser) x
In concept browser and
Along relational attr.
in global visu.
x x complex queries to initiate the exploration. Additional testings will be conducted to consolidate the reliability of the software.
This release is a first step in the building of a general platform to support exploratory search in relational datasets. To this end, future development will also focus on considering implications visualization. Large user experiments will be carried out in the context of the Knomana project.
The authors wish to thank the anonymous reviewers for their valuable comments that helped improving the paper. They also warmly thank Alain Gutierrez for his strong support during this work and for enabling FCA4J to generate output files with the JSON data format as required by RCAviz. This work was supported by the French National Research Agency under the Investments for the Future Program, referred as ANR-16-CONV-0004. trenches and the stacks, IEEE Transactions on Visualization and Computer Graphics 18 (2012) 2431–2440. [14] T. Munzner, Visualization Analysis and Design, A.K. Peters visualization series, A K Peters, 2014. [15] M. Bostock, V. Ogievetsky, J. Heer, D3 data-driven documents, IEEE Transactions on
Visualization and Computer Graphics 17 (2011) 2301–2309. [16] S. A. Yevtushenko, Conexp, 2018. URL: http://conexp.sourceforge.net/. [17] M. Alam, T. N. N. Le, A. Napoli, Latviz: A new practical tool for performing interactive exploration over concept lattices, in: CLA’16, 2016, pp. 9–20. [18] T. Pattison, Interactive visualization of formal concept lattices, in: ED/GViP@Diagrams, volume 1244 of CEUR Workshop Proceedings, CEUR-WS.org, 2014, pp. 78–89. [19] S. Andrews, L. Hirsch, A tool for creating and visualising formal concept trees, in:
CSTIW@ICCS, volume 1637 of CEUR Workshop Proceedings, 2016, pp. 1–9. [20] M. Alam, M. Osmuk, A. Napoli, RV-Xplorer: A Way to Navigate Lattice-Based Views over
RDF Graphs, in: CLA’15, 2015, pp. 23–34. [21] C. Carpineto, G. Romano, Exploiting the Potential of Concept Lattices for Information
Retrieval with CREDO, J. UCS 10 (2004) 985–1013. [22] J. Ducrou, P. Eklund, SearchSleuth: The conceptual neighbourhood of an Web query, in:
CLA’07, ????, p. 14. [23] S. Ferré, Sparklis: An expressive query builder for SPARQL endpoints with guidance in natural language, Semantic Web 8 (2017) 405–418. [24] S. Ferré, CAMELIS: Organizing and Browsing a Personal Photo Collection with a Logical
Information System, in: CLA’07, Montpellier, France, 2007, pp. 112–123. [25] M. Crampes, M. Plantié, Visualizing and Interacting with Concept Hierarchies, in: Proc.
of WIMS14, ACM, 2014. [26] A. Bazin, J. Carbonnel, M. Huchard, G. Kahn, P. Keip, A. Ouzerdine, On-demand relational concept analysis, in: ICFCA 2019, volume 11511 of LNCS, Springer, 2019, pp. 155–172.