In formal concept analysis, 2-dimensional formal contexts are bipartite graphs. In this work, we generalise the notions of context and concept to graphs that are not bipartite. We then study the complexity of the enumeration and identify the structure of the set of such concepts.
Formal concept analysis (FCA) is a mathematical framework centered on the
notions of formal context (data) and formal concept (significant patterns). Most
of the simpler real-life data sets take the form of formal contexts and the
interesting patterns are often variations on the theme of formal concepts, making
FCA well-suited for applications in any field that deals with data [
Formal contexts in their basic form are binary tables – i.e. bipartite graphs
for which a bipartition into independent sets is given. One of the most important
generalizations of FCA, Polyadic Concept Analysis (PCA) [
We believe that it would be interesting, ultimately, to generalise FCA to npartite hypergraphs that are not n-uniform in order to create new opportunities of applications involving exotic data. In this work, as a first step toward this goal, we focus on the case of n-partitioned graphs (2-uniform hypergraphs) with n > 2. We define the corresponding “concepts”, briefly study the complexity of their enumeration and show that they form a complete n-lattice, implying that known algorithms can be used to compute them. 1 i.e. hypergraph such that all its hyperedges have size n 2 i.e. the set of graph vertices is decomposed into n disjoint sets such that no two graph vertices within the same set are adjacent
This section briefly presents the basic notions in formal concept analysis and
polyadic concept analysis. For a deeper look into the 2-dimensional case, we
refer the reader to [
Definition 1 A (formal) context is a triple (S1, S2, R) in which S1 and S2 are sets of what is commonly referred to as objects and attributes and R is a binary relation between objects and attributes representing the fact that an object is described by an attribute.
A formal context is usually represented by a crosstable.
R a b c d e 1 × × 2 × × × 3 × × × 4 × × 5 × × Definition 2 Let C = (S1, S2, R) be a context. A (formal) concept of C is a pair (E ⊆ S1, I ⊆ S2) such that E × I ⊆ R and both E and I are maximal for this property.
In other words, a concept is a maximal rectangle full of crosses up to permutation of objects or attributes, also called in graph theory: a full bipartite subgraph or a biclique.
In our Fig. 1 example, (1, ab) and (23, bd) are concepts.
The set of concepts can be ordered by the inclusion relation on both objects
and attributes and then forms a complete lattice (i.e. graph of concepts). Every
complete lattice is isomorphic to the concept lattice of some context [
The notions of formal contexts and concepts have been extensively studied and
are successfully used in various fields such as data mining, data analysis,
information retrieval, source code error correction, machine learning and for
building taxonomies and ontologies [
An n-context can be represented by an n-dimensional crosstable.
a b c a b c a b c 1 × × × × 2 × × × × 3 × × × ×
γ α
β Definition 4 Let C = (S1, . . . , Sn, R) be an n-context. An n-concept of C is an n-tuple (T1, . . . , Tn) such that Ti ⊆ Si, Qi∈{1,...,n} Ti ⊆ R and there is no d ∈ {1, . . . , n} and k ∈ Sd \ Td such that (T1, . . . , Td ∪ {k}, . . . , Tn) respects this property.
In other words, an n-concept is a maximal n-dimensional box full of crosses in C up to permutations inside dimensions.
In our Fig. 2 example, ({1, 2, 3}, {a}, {α, β}) and ({2}, {a, b}, {γ}) are 3concepts.
The set of all the n-concepts in an n-context, together with the n
quasiorders induced by the inclusion relation on the subsets of each dimension, forms
an n-lattice and each complete n-lattice is isomorphic to the concept lattice of
an n-context, as stated in the basic theorem of polyadic concept analysis [
A set X ⊆ V of vertices is a clique if there is an edge between any two of its elements. A clique is maximal if it is not contained in another clique. An independent set is a set of vertices that does not contain any edge. An independent set is maximal if it is not contained in any independent set. A vertex cover is a set of vertices that contains at least one vertex from every edge. A vertex cover is minimal if it does not contain any vertex cover. A (maximal) independent set in a graph G is a (maximal) clique in the complementary graph G and reciprocally. The complement of a (maximal) independent set is a (minimal) vertex cover and reciprocally.
We will use M(G) to denote the set of maximal cliques in a graph G.
A graph G = (V, E) is k-partite iff V can be partitioned into k independent sets. 3 α 3 α β γ γ a b
Snumbers
2
A complete k-partite graph is a k-partite graph such that there is an edge between every pair of vertices that do not belong to the same independent set.
In our running example, the subgraphs induced by the vertices sets {1, b, α} and {1, a, b} are, respectively, complete tripartite and bipartite graphs.
Bidimensional formal contexts (S1, S2, R) are bipartite graphs (S1 ∪S2, R) for which a bipartition is given. In graph terminology, 2-concepts are thus maximal complete bipartite subgraphs of the context. 3
k-Partite Graphs as Contexts FCA offers tools to find and manipulate patterns in bipartite graphs. What happens to these patterns and tools when the input graph is not bipartite ? 3.1
Let us start by defining the objects we are looking for. The central patterns in FCA are concepts : maximal complete bipartite subgraphs of the context. When the context is k-partite, a natural generalisation can then be expressed as follows.
Definition 5 Let G = (V, E) be a graph and S = (S1, . . . , Sk) a partition of V into k independent sets. Let {j1, . . . , jm} ⊆ {1, . . . , k}. An m-2concept of (S, E) is a tuple C = (Cj1 , . . . , Cjm ), Cjx 6= ∅, Cjx ⊆ Sjx , such that Sx∈{1,...,m} Cjx induces a maximal complete m-partite subgraph of G and there is no (Cj1 , . . . , Cjm , Cjm+1 ) with this property.
In “m-2concept”, the m means that we consider an m-partite graph as “concept” (m dimensions are involved in the pattern) and the 2 means the pattern is found in a 2-uniform graph. We have chosen to define them as m-tuples instead of k-tuples with m ≤ k in order to avoid having to consider the m − k empty components and confusion with k-concepts from PCA.
We will now suppose, for the remainder of this paper, that our running example is partitioned as in Fig. 4. In this case, (1, b, α) is a 3-2concept and (1, ab) and (23, βγ) are 2-2concepts. The tuple (3, c, βγ) is not a 3-2concept because the induced subgraph is complete bipartite, not complete tripartite3. The tuple (1, α) is not a 2-2concept because (1, b, α) is a 3-2concept.
2-2concepts are the formal concepts with non-empty intents and extents. It is important to note that Si, i ∈ {1, . . . , k}, is a complete 1-partite subgraph – though (Si) is not necessarily a 1-2concept.
We will use T ((S, E)) to denote the set of m-2concepts, 1 < m ≤ |S|, of a k-partite graph (V, E) together with a partition S of V into k independent sets. 3 Two sets are considered {3} and {c,βγ} without relations between {c} and {βγ} Proposition 1 Let (V, E) be a graph and S = (S1, . . . , Sk) a partition of V into k independent sets.
T ((S, E)) = M((V, E ∪ X)) with X = Si∈{1,...,k} S2i Proof. In G = (V, E Si∈{1,...,k} S2i ), we have that ∀i ∈ {1, . . . , k}, Si is a clique. Let C = (Cj1 , . . . , Cjm ) with Cji ⊆ Sji be such that Si∈{1,...,m} Cji is a maximal clique in G. By definition, any two vertices x ∈ Cja and y ∈ Cjb , a 6= b are neighbours in G. As such, they are neighbours in (V, E) too. Clearly, that makes C an m-partite complete subgraph of (V, E). The maximality property holds from one graph to the other so C is an m-2concept of (V, E).
Let C = (Cj1 , . . . , Cjm ) be an m-2concept of (V, E). By definition, any two vertices x ∈ Cja and y ∈ Cjb , a 6= b are neighbours in (V, E). As such, they are neighbours in G. As, ∀i ∈ {1, . . . , k}, Si is a clique, Si∈{1,...,m} Cji is a clique in G. The maximality property once again holds from one graph to the other so Si∈{1,...,m} Cji is a maximal clique in G. tu a b 1 c 2 3 α β γ We now have to characterise the structure of the set T ((S, E)). We will show that it forms a k-lattice when put together with the appropriate quasi-orders. The best way to do this is to show that T ((S, E)) is isomorphic to the concept k-lattice of a k-context.
Let K((S, E)) = (S1 ∪ {s1}, . . . , Sk ∪ {sk}, R) be a k-context such that si 6∈ Si (x1, . . . , xk) ∈ R ⇐⇒ ∀xi 6= si, xj 6= sj, ∃e ∈ E such that xi, xj ∈ e Note that, potentially, xi = xj. In the context K((S, E)) each cross corresponds to a clique of the graph (V,E), including 1-element ones, with the elements si representing the fact that a clique does not intersect the set Si. Figure 6 illustrates the 3-context corresponding to our running example..
Clearly, if (X1, . . . , Xk) is a k-concept of K((S, E)), then ∀i ∈ {1, . . . , m}, si ∈ Xi.
a b c s2 a b c s2 a b c s2 a b c s2
Theorem 1. Let (V, E) be a graph and S a k-partition of (V, E) into k independent sets. The set of m-2concepts of (S, E), together with the k quasi-orders induced by the inclusion relation on each independent set, forms a k-lattice. Proof. Let (X1, . . . , Xk) be a k-concept of K((S, E)) = (S1 ∪ {s1}, . . . , Sk ∪ {sk}, R). By definition, Qi∈{1,...,k}(Xi \ {si}) ⊆ R. From the construction of K((S, E)), we get that ∀xi ∈ Xi\{si}, xj ∈ Xj \{sj}, ∃e ∈ E such that xi, xj ∈ e. This means that the tuple (Xj1 \ {sj1 }, . . . , Xjm \ {sjm }), such that the different Xji \ {sji } are the non-empty components of (X1 \ {s1}, . . . , Xk \ {sk}), is an m-2concept of (S, E).
Let (Cj1 , . . . , Cjm ) be an m-2concept of (S, E). By definition, ∀A ∈ Qi∈{1,...,m} Cji , ∀x, y ∈ A, ∃e ∈ E such that x, y ∈ e. As such, the tuple (X1, . . . , Xk) such that Xi = ( {si} Ci ∪ {si} if i ∈ {j1, . . . , jm}
otherwise is a k-concept of K((S, E)). tu
This implies that algorithms [
In Fig. 6, the 3-concepts are (1s1, bs2, αs3) (23s1, s2, βγs3) (1s1, abs2, s3) (12s1, bs2, s3) (3s1, cs2, s3) (123s1, s2, s3) (s1, abcs2, s3) (s1, s2, αβγs3) which yield the m-2concepts of our running example once the si and empty sets are removed. 4
In this paper, we have extended the notions of formal context and concept to graphs that are not bipartitioned in order to allow the handling of a different kind of data. We have shown that, given a k-partition of the graph into independent sets, the set of such m-2concepts forms a k-lattice. This allows the use of any k-lattice algorithm to compute m-2concepts.
The next step would be to generalise the notion of n-concept to hypergraphs that are not n-partite n-uniform. This, however, is not as straightforward as m-2concepts. Indeed, the k-lattice structure of m-2concepts comes from the fact that a clique with n vertices can freely be converted into 2n hyperedges (the subsets of vertices). Converting an edge (a, b) into two singletons (a) and (b) does not add complexity. However, converting an hyperedge (a, b, c) into a triangle (a, b), (b, c), (a, c) can potentially create new triangles that do not correspond to existing hyperedges of size 3.