# On Finding and Enumerating Maximal and Maximum \(k\)-Partite Cliques in \(k\)-Partite Graphs
## 5 A Special Class of Multipartite Graphs  
We now consider and formalize a special class of \(k\)-partite graphs that can arise in a variety of classification contexts, from social tagging [30] to data alignment [31]. A good example arises in functional genomics. In this particular application, terms from multiple ontologies, each ontology represented as a partite set, are annotated to a common set of entities, in this case genes, which is then represented as a partite set of its own. Consider, for example, annotations from Gene Ontology [32] versus those from Mammalian Phenotype Ontology [33]. The former consists of relations between genes based on descriptive terminology about cellular location, biological process and/or molecular function. The latter maintains known relations between genes and the traits they influence. By examining overlaps common to these two ontologies, terms from one can be mapped onto terms of the other. To realize this class, let \(S\) denote a finite set. We define a \(k\)-partite set intersection graph to be a \(k\)-partite graph in which one partite set, say the first, contains \(\mid\!S\!\mid\)'singleton vertices', one for each distinct element of \(S\), and every other partite set contains some number of'subset vertices' that represent (not necessarily distinct) nonempty subsets of \(S\). A pair of vertices in different partite sets is joined by an edge iff the element or subset(s) they represent intersect. A sample 3-partite set intersection graph is shown in Figure 6, where vertices are labeled with the elements and subsets they represent. In contrast, a 3-partite graph that is not a 3-partite set intersection graph is depicted in Figure 7.  
We now show that the time required to enumerate maximal \(k\)-partite cliques can be reduced for \(k\)-partite set intersection graphs. Let \(G\) denote such a graph, with vertex set \(\{u_{1},\,u_{2},\,\ldots\,,\,u_{n}\}\). To take advantage of \(G\)'s singleton structure, we compress it into a bipartite set intersection graph, \(G_{b}\), in which all subset vertices are fused into a single partite set. We denote the vertex set of \(G_{b}\) by \(\{v_{1},\,v_{2},\,\ldots\,\,v_{n}\}\), where \(v_{i}\) represents the same element or subset as does \(u_{i}\) for \(1\leq i\leq n\). Interpartite edges in \(G_{b}\) are decided based on intersections, just as with \(G\). Thus, the neighborhood (set of neighbors) of a singleton vertex is unaffected. This construction is illustrated in Figure 8.  
As we shall prove shortly, we need only call MBEA [15] (currently the fastest published algorithm for enumerating maximal bicliques in bipartite graphs) on \(G_{b}\), then check each maximal biclique it produces to determine whether the corresponding vertices in \(G\) cover all partite sets. We call this algorithm MMCE-SI, for maximal multipartite clique enumeration on set intersection graphs, See Algorithm 2. Figure 8: An example of graph compression. The \(k\)-partite set intersection graph of Figure 6 has been reduced to a bipartite set intersection graph. Figure 6: A 3-partite set intersection graph. Singleton vertices that represent \(a\), \(b\), \(c\), \(d\), and \(e\) comprise one partite set. Subset vertices that represent \(\{a\), \(b\), \(d\)}, \(\{a\), \(d\), \(e\), and \(\{d\), \(c\}\) comprise a second partite set. A third partite set consists of subset vertices that represent \(\{b\), \(e\)} and \(\{b\), \(c\)}. Figure 7: A 3-partite graph that is not a set intersection graph. Nodes labeled 0 and 1 in the leftmost partite set cannot both be singleton vertices, since otherwise nodes 2 and 3 must be adjacent. By the same token, nodes labeled 3 and 4 in the rightmost partite set cannot both be singleton vertices, else nodes 1 and 2 must be adjacent. But node 2 in the middle partite cannot be a singleton vertex either, because that would require nodes 0 and 4 to be adjacent.