# Mining Maximal Induced Bicliques using Odd Cycle Transversals ††thanks: This
work was supported by the Gordon & Betty Moore Foundation’s Data-Driven
Discovery Initiative under Grant GBMF4560 to Blair D. Sullivan.

Kyle Kloster
Blair D. Sullivan22footnotemark: 2
North Carolina State University. Andrew van der Poel22footnotemark: 2

###### Abstract

Many common graph data mining tasks take the form of identifying dense
subgraphs (e.g. clustering, clique-finding, etc). In biological applications,
the natural model for these dense substructures is often a complete bipartite
graph (biclique), and the problem requires enumerating all maximal bicliques
(instead of identifying just the largest or densest). The best known algorithm
in general graphs is due to Dias et al., and runs in time $O(M|V|^{4})$, where
$M$ is the number of _maximal induced bicliques_ (MIBs) in the graph. When the
graph being searched is itself bipartite, Zhang et al. give a faster algorithm
where the time per MIB depends on the number of edges in the graph. In this
work, we present a new algorithm for enumerating MIBs in general graphs, whose
run time depends on how “close to bipartite” the input is. Specifically, the
runtime is parameterized by the size $k$ of an odd cycle transversal (OCT), a
vertex set whose deletion results in a bipartite graph. Our algorithm runs in
time $O(M|V||E|k^{2}3^{k/3})$, which is an improvement on Dias et al. whenever
$k\leq 3\log_{3}|V|$. We implement our algorithm alongside a variant of Dias
et al.’s in open-source C++ code, and experimentally verify that the OCT-based
approach is faster in practice on graphs with a wide variety of sizes,
densities, and OCT decompositions.

Keywords: bicliques, odd cycle transversal, parameterized algorithms,
enumeration, bipartite

###  1 Introduction

Bicliques (complete bipartite graphs) naturally arise in many data mining
applications, including detecting cyber communities [19], data compression
[2], epidemiology [25], artificial intelligence [32], and gene co-expression
analysis [16, 17]. In many settings, the bicliques of interest are _maximal_
(not contained in any larger biclique) and/or _induced_ (each side of the
bipartition is independent in the host graph), and there is a large body of
literature [4, 7, 8, 21, 24, 25, 28, 34] giving algorithms for enumerating all
such subgraphs. Many of these approaches make strong structural assumptions on
the host graph; the case when the host graph is bipartite has been
particularly well-studied, and the iMBEA algorithm of Zhang et al. has been
empirically established to be state-of-the-art [34]. In general graphs, the
only known non-trivial algorithm for enumerating maximal induced bicliques
(MIBs) is that of Dias et al. [7].

We consider the problem of efficiently enumerating all MIBs in general graphs.
In particular, we design an algorithm OCT-MIB that extends ideas from iMBEA to
work on non-bipartite graphs by using an _odd cycle transversal_ (OCT set): a
set of nodes $O$ such that $G[V\setminus O]$ is bipartite. We prove that our
algorithm has runtime $O(Mnm\cdot n_{O}^{2}\cdot 3^{n_{O}/3})$ where
$n_{O}=|O|$, $M$ is the number of MIBs in the graph, and $n$ and $m$ denote
the number of vertices and edges in the graph, respectively. This is
asymptotically faster than the approach of Dias et al. whenever the OCT set
has size $n_{O}\leq 3\log_{3}(n)$. Since all graphs have OCT sets (although
they can be size $O(n)$, as in cliques), our algorithm can be run in the
general case; its correctness does not require minimality or optimality of the
OCT set.

We also present several additional algorithms which may be of independent
interest. The first is LexMIB, a modification of the algorithm of Dias et al.
[7], which addresses a flaw in the original method and enumerates all MIBs in
time $O(Mn^{4})$. The second is for a variant of biclique enumeration where we
are only interested in bicliques with one part inside a specified independent
set of the host graph. Specifically, given a graph $G=(V,E)$ with $V$
partitioned into $X\cup Y$ with $X$ an independent set, we wish to enumerate
all _maximal crossing bicliques_ (MCBs) $A\times B$ with $A\subseteq X$,
$B\subseteq Y$. We give an algorithm MCB which enumerates all maximal crossing
bicliques in time $O(|X||Y|m)$ per MCB.

Further, we implement both OCT-MIB and LexMIB in open source C++ code, and
evaluate their performance on a suite of synthetic graphs with known OCT
decompositions. Our experiments show that OCT-MIB is generally at least an
order of magnitude faster than LexMIB, and verify that in practice, our
parameterized approach yields the best performance even when the distance to
bipartite (OCT set size) is $\Omega(\log(n))$, far exceeding the constant
values typically required by such algorithms.

We begin with preliminaries and a brief discussion of related work, then
describe the flaw from the original method in [7] along with our corrected
version in Section 3. We outline our main algorithm OCT-MIB in Section 4, and
state the correctness and complexity for OCT-MIB in Section 5. Finally, we
present our experimental evaluation in Section 6.

In Appendix A we begin by identifying a typo in the runtime of iMBEA from [34]
and show that its runtime is $O(Mmn)$, where $M$ is the number of MIBs. We
include detailed descriptions of the mechanics of OCT-MIB and MCB, along with
proofs of their correctness and runtime in Appendices B and C, respectively.
In Appendix D we describe our random graph generator and the hardware we use
for our experiments, along with an additional experiment comparing OCT-MIB and
LexMIB.

###  2 Preliminaries

####  2.1 Related work

The complexity of finding bicliques is well-studied, beginning with the
results of Garey and Johnson [9] which establish that in bipartite graphs,
finding the largest balanced biclique is NP-hard but the largest biclique
(number of vertices) can be found in polynomial time. Finding the biclique
with the largest number of edges was shown to be NP-complete in general graphs
[33], but the case of bipartite graphs remained open for many years. Several
variants (including the weighted version) were proven NP-complete in [6], and
in 2000, Peeters finally resolved the problem, proving the edge maximization
variant is NP-complete in bipartite graphs [27]. Particularly relevant to the
mining setting, Kuznetsov showed that enumerating maximal bicliques in a
bipartite graph is #P-complete [20], the NP-completeness analogue for counting
problems [31].

For the problem of enumerating maximal _induced_ bicliques, the best known
algorithm in general graphs is due to Dias et al. [7]; in the non-induced
setting, other approaches include a consensus algorithm [4], an efficient
algorithm for small arboricity [8], and a general framework for enumerating
maximal cliques and bicliques [10]. We note that, as described, the method in
[7] may fail to enumerate all MIBs; we describe a graph eliciting this
behaviour, along with a modified algorithm (LexMIB) with proof of correctness
in Section 3. We note that our correction increases the runtime of the
approach from $O(n^{3})$ to $O(n^{4})$ per MIB.

There has also been significant work on enumerating MIBs in bipartite graphs.
We note that since all bicliques in a bipartite graph are necessarily induced,
non-induced solvers for general graphs (such as [4]) can be applied, and have
been quite competitive. The best known approach, however, is an algorithm due
to Zhang et al. [34] that directly exploits the bipartite structure111Due to a
typo in their runtime (see Section A), the worst-case complexity of this
algorithm is not an improvement on the $O(n^{2})$ time per MIB of several
other approaches. However, in practice, the experimental results in [34]
support this being faster than [4].. This algorithm works by iterating over
one partition of the bipartite graph and iteratively building maximal
bicliques. They maintain special subsets of the iterated-over partition for
each biclique and leverage the structure implied by bipartite graphs to
efficently enumerate all of the maximal bicliques. Other approaches in the
bipartite setting include frequent closed itemset mining [21] and
transformations to the maximal clique problem [24]; faster algorithms are
known when a lower bound on the size of bicliques to be enumerated is assumed
[25, 28].

In this work, we extend techniques for bipartite graphs to the general setting
using odd cycle transversals, a form of “near-bipartiteness” which arises
naturally in many applications [12, 26, 29]. Although finding a minimum size
OCT set is NP-hard, the problem of deciding if an OCT set with size $k$ exists
is fixed parameter tractable (FPT), with algorithms in [22] and [15] running
in times $O(3^{k}kmn)$ and $O(4^{k}n)$, respectively. Although it is possible
for graphs to have minimum OCT sets as large as $O(n)$ (as in cliques, for
example), in practice many graphs from common problem domains have OCT sets of
size at most 40 [14].

Other algorithms for OCT include a $O(\sqrt{log(n)})$-approximation [1], a
randomized polynomial kernelization algorithm based on matroids [18], and a
subexponential algorithm for planar graphs [23]. Since our algorithm only
requires a valid OCT set (not a minimal or optimal one), any of these
approaches or one of several high-performing heuristics may be used to pre-
process the data. Recent implementations [11] of a heuristic ensemble
alongside algorithms from [3, 14] alleviate concerns about finding an OCT
decomposition creating a barrier to usability for our algorithm.

####  2.2 Notation and terminology

Let $G=(V,E)$ be a graph. We denote $n=|V|$ and $m=|E|$, and use $N(v)$ to
represent the neighborhood of a node $v\in V$. An independent set $T$ in $G$
is a _maximal independent set_ (MIS) if $T$ is not contained in any other
independent set of $G$. We use $\mathcal{I}(S)$ to denote all nodes which are
independent from a set $S$ and $\mathcal{C}(S)$ to denote all nodes which are
completely connected to a set $S$.

A biclique $A\times B$ in a graph $G=(V,E)$ consists of disjoint sets
$A,B\subset V$ such that every vertex of $A$ is connected to every vertex of
$B$. We say a biclique $A\times B$ is _induced_ if both $A$ and $B$ are
independent sets in $G$. A biclique is _maximal_ in $G$ if no biclique in $G$
properly contains it. Given a fixed independent set $X\subseteq V$, we define
a _crossing_ biclique with respect to $X$ to be an induced biclique $A\times
B$ such that $A\subseteq X$ and $B\subseteq V\setminus X$.

If $G$ is bipartite, we write $G[L,R]$, where the vertices are partitioned as
$V=L\cup R$ and we refer to the two partitions as the left and right “sides”
of the graph. For a biclique $A\times B$ in $G[L,R]$, by convention we list
the “left” set first, i.e. $A\subseteq L$ and $B\subseteq R$.

If $G$ has OCT set $O$, we denote the corresponding OCT decomposition of $G$
by $G[L,R,O]$, where the induced subgraph $G[L,R]$ is bipartite, and called
the _bipartite part_. We write $n_{L},n_{R},$ and $n_{O}$ for $|L|,|R|,$ and
$|O|$, respectively. We let $n_{B}=n_{L}+n_{R}$. Given an arbitrary vertex set
$T\subset V$ we abbreviate $T^{O}=T\cap O$ and $T^{L,R}=T\setminus O$.

We present algorithms for enumerating maximal induced bicliques in two
settings. The first setting, Maximal Induced Biclique Enumeration, is our
primary focus.

Input: A graph $G=(V,E)$. Output: All maximal induced bicliques in $G$.
Maximal Induced Biclique Enumeration

The second setting, Maximal Crossing Biclique Enumeration arises as a
subproblem in our approach to Maximal Induced Biclique Enumeration.

Input: A graph $G=(V,E)$; with $V$ partitioned into $X\cup Y$ s.t. $X$ is
independent in $G$. Output: All maximal bicliques $A\times B$ in $G$ where
$A\subseteq X$ and $B\subseteq Y$. Maximal Crossing Biclique Enumeration

###  3 Lexicographic Enumeration

In this section we identify graphs containing maximal induced bicliques which
would not be discovered by the algorithm of Dias et al. as originally stated
in [7], which we refer to as Dias. We then describe a modified approach, which
we prove is guaranteed to output all maximal induced bicliques in
lexicographic order222We believe Dias could also be modified by removing the
if conditions on lines 9 and 11 to output all MIBs in non-lexicographic order,
with runtime $O(Mn^{3})$, but did not focus on this alternate strategy. in
time $O(Mn^{4})$, where $M$ is the number of MIBs in the graph.

For the reader’s convenience we have transcribed the pseudo-code of Dias from
[7] in Algorithm 1. Line 13 relies on a subroutine described in the original
paper, which finds the lexicographically least biclique containing a given set
of nodes in $O(n^{2})$ time. For consistency with [7], we let $N_{j}$ be the
neighbors of node $j$ and $\bar{N}_{j}$ the non-neighbors throughout this
section.

1:Graph $G=(V,E)$, order on V

2:List of all bicliques of $G$ in lexicographic order

3:Find the least biclique $B*$ of $G$

4:$Q\leftarrow\emptyset$

5:insert $B*$ in the queue $Q$

6:while $Q\neq\emptyset$ do

7: find the least biclique $B=X\cup Y$ of $Q$

8: remove $B$ from $Q$ and output it

9: for each vertex $j\in V\setminus B$ do

10: $X_{j}\leftarrow X\cap\\{1,\dots,j\\}$; $Y_{j}\leftarrow
Y\cap\\{1,\dots,j\\}$

11: if $X_{j}\cap N_{j}\neq\emptyset$ or $Y_{j}\cap\bar{N}_{j}\neq\emptyset$
then

12: $X^{\prime}_{j}\leftarrow(X_{j}\setminus N_{j})\cup\\{j\\}$;
$Y^{\prime}_{j}\leftarrow Y_{j}\setminus\bar{N}_{j}$

13: if there exists no $\l\in\\{1,\dots,j-1\\}\setminus B_{j}$ such that
$X^{\prime}_{j}\cup Y^{\prime}_{j}\cup\\{l\\}$ extends to a biclique of $G$
then

14: find the least biclique $B^{\prime}$ of $G$ containing $X^{\prime}_{j}\cup
Y^{\prime}_{j}$, if any

15: if $B^{\prime}\neq\emptyset$ and $B^{\prime}\in Q$ then

16: Include $B^{\prime}$ in $Q$

17: Swap contents of $X_{j}$ and $Y_{j}$, repeat lines 9 to 14 (once per for
loop)

Algorithm 1 Dias pseudo-code [7].

We point out that the queue $Q$ needs to be able to recall all MIBs which have
been stored in it, which can easily be accomplished by augmenting the data
structure without impacting the complexity. Furthermore, the pseudo-code in
Algorithm 1 was corrected in line 12 to exclude $j$ from the range of $l$
values.

In the proof of correctness in [7] they show that for any MIB $B^{\prime}$
there exists a node $j\in B^{\prime}$ and another MIB $B$ which does not
contain $j$, but does contain both
$B^{\prime}_{j-1}=B^{\prime}\cap\\{1,\dots,j-1\\}$ and some
$l\in\\{1,\dots,j-1\\}\setminus B^{\prime}_{j-1}$. They examine the maximal
such $j$ for each $B^{\prime}$, and consider the iteration where $B$ and $j$
are defined as such (lines 7 and 8). Without loss of generality, assume that
$j$ should be added to $X_{j}$ (as defined in line 9). If $Y_{j}$ only
contains non-neighbors of $j$ and $X_{j}$ contains non-neighbors of $j$ which
are not in $B^{\prime}$, then no biclique will be found in line 15. Thus the
algorithm as written will not produce all of the MIBs, as shown in Figure 1.

012345 Figure 1:  An example of a graph where Dias would not find all MIBs.
The MIB $C=\\{1,3\\}\times\\{5\\}$ would not be found. In the notation of the
algorithm $j=3$ and $B=\\{0,1,4\\}\times\\{2\\}$ should yield $C$. Note that
$\\{0,1,4\\}\times\\{2\\}$ is the lexicographically least biclique. Consider
when $B=\\{0,1,4\\}\times\\{2\\}$ and $j=3$, $X_{j}=\\{0,1\\}$ and no biclique
is found as $\\{0,1,3\\}$ have no common neighbors. When $X_{j}=\\{2\\}$ the
biclique $\\{2,3\\}\times\\{4\\}$ is found. Thus $C$ is not added to $Q$. We
note that when $B=\\{0,1,4\\}\times\\{2\\}$ and $j=5$, we would add the
bicliques $\\{1,4\\}\times\\{5\\}$ and $\\{0,5\\}\times\\{2\\}$ to $Q$. When
$B=\\{0,5\\}\times\\{2\\}$ (line 5), no new bicliques are added to $Q$ and
then the next least biclique output in line 5 would not be $C$.

####  3.1 Modified Dias

We now describe LexMIB and show that it finds all MIBs in lexicographic order.
The first issue in Dias arises when in line 8, $Y_{j}$ is empty and $X_{j}$
does not contain any neighbors of $j$. In this case, we fail to satisfy the
if-condition in line 9. The problem is resolved by appending an additional or-
condition in line 9: “or $|Y_{j}|=0$”.

The other problematic case is when $Y^{\prime}_{j}$ is empty and $X_{j}$
contains non-neighbors of $j$ which are not in the lexicographically next MIB
(e.g. node $0$ for $\\{1,3\\}\times\\{5\\}$ in Figure 1). In this case,
$B^{\prime}=\emptyset$ in line 13, so we add a new else-if clause to the
conditional: “else if $B^{\prime}=\emptyset$ and $Y^{\prime}_{j}=\emptyset$
then for all $v\in N_{j}$ find the least biclique containing $(N(v)\cap
X^{\prime}_{j},\\{v\\})$”.

We now argue that LexMIB will find any biclique $B^{\prime}$ missed by Dias in
the above manner. Let $S=B^{\prime}\cap X^{\prime}_{j}$. Let $v_{1}$ be the
least node in $B^{\prime}$ which shares an edge with $j$. Consider the
iteration of the above process where $v=v_{1}$. Clearly all of $S$ is
contained in $N(v_{1})\cap X^{\prime}_{j}$. Furthermore due to the maximality
of $j$, the original argument from [7] can be used to show that finding the
least biclique containing $(N(v_{1})\cap X^{\prime}_{j},\\{v\\})$ returns
$B^{\prime}$. In Figure 1 where biclique $C$ is missed, when $j=3$ and
$B=\\{0,1,4\\}\times\\{2\\}$, $v_{1}=5$ and $N(v_{1})\cap
X^{\prime}_{j}=\\{1,3\\}$, which returns this previously missing biclique
$C=\\{1,3\\}\times\\{5\\}$.

This augmentation increases the delay time of the algorithm to be $O(n^{4})$
since finding the least biclique may be called $O(n)$ times within the for
loop at line 7, which itself has $O(n)$ iterations. Note that this addition
does not alter their argument for the bicliques being output in lexicographic
order.

###  4 Algorithms

Here we describe two novel algorithms for biclique enumeration: OCT-MIB which
enumerates all MIBs in a general graph $G$ by using an OCT decomposition
$G[L,R,O]$ to drive a divide and conquer approach, and MCB which computes all
MIBs with one partition in a designated independent set. In OCT-MIB, removing
an OCT set from $G$ enables use of efficient methods for enumerating MIBs in
the bipartite setting, such as Zhang et al.’s iMBEA algorithm. Then a given
MIB, $A\times B$, in the bipartite graph $G[L,R]$ can be checked for
maximality in $G$ by attempting to add vertices from $O$ to $A\times B$.

Each MIB not found in $G[L,R]$ necessarily contains at least one vertex $v\in
O$, allowing us to enumerate them by iterating over each vertex $v\in O$ and
identifying all MIBs that contain $v$. This process requires careful
bookkeeping that we organize using the observation that in all MIBs containing
a given vertex $v$, one side of the biclique must be an independent set
completely connected to $v$. Hence, we proceed with constructing “seed”
bicliques from independent sets in $N(v)$. We then “grow” these into maximal
bicliques by adding vertices from an MIS in $O$ containing $v$.

Next we will provide more detailed algorithm outlines for both OCT-MIB and
MCB.

1:Graph $G=(V,E)$, partitioning of $V$ into $L,R,O$, where $L$ and $R$ are
independent sets

2:$\mathcal{M}$, all maximal induced bicliques of $G$

3:$\mathcal{M}\leftarrow\emptyset$

4:$B_{1}\leftarrow$ maximal bicliques in $G[L,R]$

5:for $b\in B_{1}$ do

6: if $b$ is maximal in $G$ then

7: add $b$ to $\mathcal{M}$

8:$I_{O}=\texttt{MIS}(O)$

9:for $S\in I_{O}$ do

10: $T\leftarrow\emptyset$ $\triangleright$ to hold bags

11: Fix $\phi$ an order of $S$

12: for $v\in S$ do

13: $B_{2}\leftarrow$ unique initial bicliques via MCB & MIS

14: for $b\in B_{2}$ do

15: if not-future-max($b$, $G$) then

16: remove $b$ from $B_{2}$

17: if maximal($b$, $G$) then

18: add $b$ to $\mathcal{M}$ (and keep $b$ in $B_{2}$)

19: if $B_{2}$ is not empty then

20: add bag $B_{2}$ to $T$

21: while $T$ is not empty do

22: Pick $\mathcal{B}\in T$ and let $T\leftarrow T\setminus\mathcal{B}$

23: for $v\in S$: $\phi(v)>\phi(w)\,\forall\,w\in S\cap\mathcal{B}$ do

24: $B_{3}\leftarrow\emptyset$

25: for biclique $b\in\mathcal{B}$ do

26: $b*\leftarrow$ expand $b$ with $v$

27: if not-future-max($b*$, $G$) then

28: continue

29: $B_{3}\leftarrow B_{3}\cup\\{b*\\}$

30: if maximal($b*$, $G$) then

31: add $b*$ to $\mathcal{M}$ (and keep $b*$ in $B_{3}$)

32: if $B_{3}$ is not empty then

33: add $B_{3}$ to $T$

Algorithm 2 OCT-MIB pseudo-code.
Key phases: Bipartite (Lines 2–5), Initialization (Lines 10–18), and Expansion
(Lines 19–31).

Figure 2:  Runtime ratios of OCT-MIB to LexMIB with varying edge densities
(Left) and coefficient of variance (Right). Each curve corresponds to a fixed
$n_{B}$ and $n_{O}$; for settings where OCT-MIB completed but LexMIB timed out
on some instances, we display both upper (dashed, using 3600s for LexMIB) and
lower (solid, using infinity for LexMIB) bounds on the ratio. For edge
density, each point is averaged over 10 randomly generated instances (5 with
OCT-OCT density equal to $\bar{d}$ and 5 with it fixed to $5\%$, so as to
ensure the results are not an artifact of the OCT-OCT density; when
$\bar{d}=5\%$ there are only 5 instances); note that both algorithms timed out
on all instances with $n_{B}$ = $300$ when edge density was greater than
$0.15$. For cv, points are an average over 5 instances.

####  4.1 Algorithm outline

In both MCB and OCT-MIB we take an independent set $S$ and build bicliques
$A\times B$ such that $S_{I}:=S\cap(A\times B)\subseteq A$. We let
$\bar{S_{I}}:=A\setminus S_{I}$. During the initialization phase we find
bicliques of the form $A\times B$ where $A$ contains exactly one node from
$S$. During this phase, we enumerate MISs in a subgraph using MIS [30]; in
OCT-MIB, we also utilize MCB.

We then “grow” the bicliques found during initialization in the expansion
phase by repeatedly adding a node $w\in S\setminus A$ to $S_{I}$ and removing
nodes from $B$ and $\bar{S_{I}}$ to ensure $A\times B$ is still an induced
biclique. We refer to this process as _expanding with $w$_. In MCB we let
$S=X$, and in OCT-MIB we let each MIS in $O$ be $S$ once. While MCB only
contains initialization and expansion phases, OCT-MIB also contains the
bipartite phase alluded to earlier, where the MIBs which are completely
contained in $L\cup R$ are found. (Line 2 of Algorithm 2; this can be
completed using e.g. iMBEA).

We employ an ordering $\phi$ on the vertices of $S$ to limit the amount of
redundant expansions we make. We say $A\times B$ is _near-maximal_ if $A\times
B$ is maximal with respect to $V\setminus(S\setminus S_{I})$ and there is some
set of nodes $S^{\prime}\subseteq S\setminus A$ such that $(A\cup
S^{\prime})\times B$ is a maximal biclique. We allow $S^{\prime}=\emptyset$ so
maximal bicliques are also near-maximal. We refer to near-maximal bicliques
where all of the missing nodes occur later in $\phi$ as _future-maximal_ , and
we only expand on future-maximal bicliques (discarding all others). We group
bicliques which contain the same set of $S$-nodes in _bags_. During the
expansion phase we iterate over the bags, expanding their set of bicliques
with all $x\in S$ such that $\phi(x)>\phi(y)$ for all $y\in S$ occuring in
some biclique in the bag. For each $S$-node we expand with, we create a new
bag to hold the new future-maximal bicliques. The general approach of OCT-MIB
is outlined in Algorithm 2. The pseudo-code for MCB is similar but does not
include a bipartite phase (lines 2 to 5) and only uses MIS in initialization.

###  5 Theoretical Guarantees

We now state the correctness and asymptotic complexity of OCT-MIB. The
corresponding proofs rely on details from Appendix B.1 and can be seen in
Appendix B.2.

[] OCT-MIB finds all maximal induced bicliques.

[] Given a graph $G$ with OCT decomposition $G[L,R,O]$, OCT-MIB runs in
$O(Mmnn_{O}^{2}I_{O})$ time, where $M$ is the number of MIBs and $I_{O}\leq
3^{n_{O}/3}$ is the number of maximal independent sets in $O$. Its space
complexity is $O(Mn)$.

###  6 Empirical Evaluation

In this section we evaluate the performance of OCT-MIB on a suite of synthetic
graphs with a variety of sizes, densities, degree distributions, and OCT
decomposition structures, to see how various aspects of the graph impact the
runtime. We benchmark against LexMIB, our modified version of the approach
described in [7] (see Section 3).

$(\bar{d},b)$ | $n_{B}$ | $n_{O}$ | $\bar{M}$
---|---|---|---
(5%, 1:10) | 1000 | - | 3717.8
1000 | 20 | 16631.0
(5% 1:1) | 1000 | - | 50424.4
600 | 10 | 962305.8
(10%, 1:1) | 600 | - | 86239.0
300 | 5 | 185760.4
Table 1:  Comparison of the average number of MIBs $\bar{M}$ in bipartite and
near-bipartite graphs with equivalent expected edge density $\bar{d}$ and
balance $b$.

####  6.1 Experimental setup and data

We implemented OCT-MIB and LexMIB 333 The experiments described in this
manuscript were run using an early implementation of LexMIB which output
bicliques according to a fixed ordering different from that described in [7].
The implementation available at [13] removes this inconsistency.  in C++; we
note that no prior implementation of Dias was available. All code is open
source under a BSD 3-clause license and publicly available at [13]. Hardware
specifications are in Appendix D.

Figure 3:  Runtime ratios of OCT-MIB to LexMIB with varying OCT sizes (Left)
and expected OCT-$G[L,R]$ edge densities (Right). Each data point represents
the average over 5 random instances with $n_{B}=1000$ and $b=1:10$. For
settings where OCT-MIB completed but LexMIB timed out on some instances, we
display both upper (dashed, using 3600s for LexMIB) and lower (solid, using
infinity for LexMIB) bounds on the ratio. In the OCT-$G[L,R]$ edge density
experiment, the expected edge density is $5\%$ within $O$ and between $L$ and
$R$.

##### Data.

Our datasets are generated using a modified version of the random graph
generator of Zhang et al. [34] that augments the random bipartite graph to
have OCT sets of known size. The generator allows a user to specify the sizes
of $L$, $R$, and $O$ ($n_{L}$, $n_{R}$, and $n_{O}$), the expected edge
densities between $L$ and $R$, $O$ and $\\{L,R\\}$, and within $O$, and
control the coefficient of variation (cv; the standard deviation divided by
the mean) of the expected number of neighbors in the larger partition over the
smaller partition and in $\\{L,R\\}$ over the OCT set. The generator
identifies the set $O$ when it creates each graph; these sets $O$ are used in
OCT-MIB, but the techniques mentioned in Section 2.1 could also be used to
find a valid OCT set. For additional details on the generator and parameter
settings see Appendix D.

Unless otherwise specified, the following default parameters are used:
expected edge density $\bar{d}=5\%$, $cv=0.5$, $n_{B}=1000$ and $b=$1:10;
additionally, the edge density between $O$ and $L\cup R$ is the same as that
between $L$ and $R$. For all experiments where it was appropriate we tested
two OCT sizes, $n_{O}=10$ and $n_{O}=\max(5,3\log_{3}(n))$. Our default
timeout was one hour (3600s).

We note that many of our graphs are significantly smaller than those used in
[34], due to an explosion in the number of MIBs in even slightly non-bipartite
instances (see Table 1). Our graph corpus was designed to include instances
with approximately the same number of MIBs as those in [34] for all
experiments evaluating variation in the bipartite subgraph.

####  6.2 Comparison of OCT-MIB and LexMIB

We first measured the impact of the heterogeneity of the degree distribution
by varying the cv between $L$ and $R$ from $0.3$ to $1.2$ in steps of $0.05$
(cv between $O$ and $\\{L,R\\}$ is still 0.5). As seen in the right panel in
Figure 2, the ratio of the runtime of OCT-MIB to that of LexMIB generally
decreases as cv increases when $n_{B}=200$, but is at least consistent, and
possibly increases when $n_{B}=1000$.

In order to evaluate the effect of edge density, we restricted our attention
to graphs with 1:1 balance (as in [34]), where $n_{B}\in\\{150,200,300\\}$ and
uniform expected edge density ranges from $0.05$ to $0.25$ in steps of $0.05$.
Internal density within $O$ was either set to match edge density or fixed to
be $0.05$. As seen at left in Figure 2, the ratio of the runtime of OCT-MIB to
that of LexMIB decreases as the expected density increases to $0.15$, after
which it is likely to continue to decrease but can not be determined due to
LexMIB timing out.

Finally, as was done in [34], we tested the effect of the size $n_{B}$ and
balance $b$ of the bipartite subgraph on runtime. This was particularly
challenging due to the significant increase in the number of MIBs at lower
balance ratios (see Table 1). Results and discussion are in Appendix D (Figure
6); the effect of making the bipartite subgraph more imbalanced was similar
for both algorithms.

####  6.3 Varying OCT structures

This set of experiments explores how OCT-MIB performs on graphs with widely
varying OCT sizes and densities.

We tested $n_{O}$ by varying it from $0$ to $18$ in steps of size $2$ (left
panel of Figure 3), noting that the runtime of OCT-MIB tends to increase
relative to that of LexMIB as $n_{o}$ increases. We examined the impact of the
density between $O$ and $\\{L,R\\}$ by varying it from $0.01$ to $0.09$ in
steps of size $0.02$ (right panel of Figure 3), observing that the runtime of
OCT-MIB slightly increases relative to that of LexMIB as the expected density
increases. In the latter we let the cv between $O$ and $\\{L,R\\}$ be 0.

We also looked at graphs where the structure of $O$ was optimal for OCT-MIB
(independent) and adversarial (perfect matching) with respect to the number of
MISs in $O$. For the best case we fixed $n_{B}=10,000$ and the balance at
1:10, while setting $n_{O}\in\\{5,10,25\\}$, and edge density to $0.005$ and
$0.01$. For this experiment, we increased the timeout to 7200 seconds. Table 2
shows the comparatively modest growth in runtime as the independent OCT set is
increased from 5 to 25.

$n_{O}$ | $\bar{d}=0.5\%$ | $\bar{d}=1\%$
---|---|---
5 | 312.7 | 1345.8
10 | 597.8 | 2828.1
25 | 1552.1 | 6683.9
Table 2:  Runtimes for OCT-MIB on graphs with $n_{b}=10000$ and independent
sets $O$. Each entry represents the average runtime (seconds) over 5 random
graphs.

Figure 4:  Evaluation of OCT-MIB and LexMIB with varying expected OCT-$G[L,R]$
edge densities (Left) and varying edge density within the OCT set (Right),
expressed in terms of average runtime per MIB. Each data point represents the
average over 5 random instances with $n_{B}=1000$, $b=1:10$, and expected edge
density $5\%$ in the portion of the graph where edge density is not being
varied. For the setting where we varied the density within the OCT set and
$n_{O}=3\log_{3}(n_{B})$, LexMIB timed out on all instances with density
greater than 0.03.

For graphs with worst-case OCT sets (perfect matching), we let $n_{B}$ be
$300$ or $600$, $n_{O}=3\log_{3}(n)$, and set the balance to 1:1. As seen in
Table 3, OCT-MIB outperforms LexMIB by nearly an order of magnitude.

To evaluate the effect of the edge density within $O$, we generated graphs
where the expected density within the OCT set varied from $0.01$ to $0.19$ in
steps of size $0.02$ (see the right panel of Figure 4). In order to best
observe the impact of the density within the OCT set we let the cv between the
OCT set and $\\{L,R\\}$ be 0. It does not appear that the density within the
OCT set has much impact on LexMIB’s runtime. This is likely because LexMIB’s
runtime is heavily influenced by the average degree in $G$, which does not
increase significantly as the density within $O$ increases. However the
runtime of OCT-MIB increases as the density within $O$ increases, which is not
surprising due to higher density in $O$ creating more MISs in the OCT set.
Furthermore, this shows that there are likely many regimes where the average
time spent per MIB is on the order of thousandths of a second.

In the left panel of Figure 4, we present data from the same OCT-$G[L,R]$ edge
density experiment as in the right panel of Figure 3, displayed as average
time per MIB. One might believe that increasing the density between $O$ and
$\\{L,R\\}$ would increase the number of MIBs, so the increase in runtime
observed in Figure 3 follows naturally. However average time per MIB actually
decreases for OCT-MIB as the density is increased from 0.07 to 0.19 in both
settings. We hypothesize that this may be because more MIBs are found in the
expansion phase as the density increases, due to more OCT nodes being in the
MIB on average. Our complexity analysis tells us that finding MIBs in the
expansion phase should take less time than the initialization phase. These
results are particularly interesting because when contrasting them with those
where the expected edge density within the OCT set is increased (right panel
of Figure 4), we observe a converse effect.

Finally, we evaluated both algorithms on graphs with large values of $n_{O}$
(where OCT-MIB’s computational complexity is worse than that of LexMIB) and
confirmed that in this scenario, LexMIB is the preferable algorithm in both
theory and practice. Specifically, on graphs where $n_{B}=200$, OCT-MIB was
faster than LexMIB when $n_{O}=20$, but at $n_{O}=40$, it was already an order
of magnitude slower. The effect was even more pronounced for a corpus where
$n_{B}=400$: LexMIB had average runtimes of $119s$ and $603s$ when $n_{O}$ was
$40$ and $80$, respectively, whereas OCT-MIB timed out ($3600$s) on 9/10
instances (finishing a single $n_{O}=40$ instance in $2409$s).

Algorithm | $n_{B}=300$ |  | $n_{B}=600$
---|---|---|---
LexMIB | (74.0, -) |  | (3420, 4)
OCT-MIB | (19.8, -) |  | (634, -)
Table 3:  Runtimes for OCT-MIB and LexMIB on adversarially created graphs.
Each entry represents the average runtime (seconds) on completed instances and
the number of timeouts ($3600s$). For each $n_{B}$, we used 5 random graphs
with $\bar{d}=5\%$, $b$ = 1:1, $n_{O}=\lfloor 3\log_{3}(n_{B})\rfloor$, and an
OCT set which is a perfect matching.

###  7 Conclusions

We present a new algorithm OCT-MIB for enumerating maximal induced bicliques
in general graphs, with runtime parameterized by the size of an odd cycle
transversal. Additionally, we describe a flaw in the algorithm of Dias et al.
[7], and give a corrected variant LexMIB.

It is particularly noteworthy that OCT-MIB has the best-known complexity for
enumerating MIBs even when the parameter is logarithmic in the instance
size—far from the constant regime often necessary for FPT approaches to be
efficient.

We implement and benchmark both algorithms on a corpus of synthetic graphs,
establishing that in practice, OCT-MIB is typically an order of magnitude
faster than LexMIB—even when $n_{O}$ is $O(\log(n))$. We also confirm that
OCT-MIB finishes on graphs with over 1,000,000 MIBs in minutes, and enumerates
all MIBs in sparse graphs ($\bar{d}=1\%$) where $n=10,000$ and $n_{O}$ is
$O(\log(n))$ in less than two hours.

Our experiments also demonstrate that size may not be the most important
feature of an OCT set in determining OCT-MIB’s runtime in practice. Although
this paper focused on the algorithm’s performance in the setting where an OCT
decomposition with given $n_{O}$ was known, it would be interesting to further
analyze how the edge structure within the OCT set impacts the runtime (for
example, we know that the number of maximal independent sets in $O$ plays a
key role in OCT-MIB’s execution), and whether OCT sets found by different
algorithms/heuristics are more or less advantageous for biclique enumeration.

We also point out that Maximal Crossing Biclique Enumeration for which we give
an $O(M|X||Y|m)$ algorithm is a novel problem in its own right and may be
well-motivated by applications where large independent sets naturally arise.

Finally, we note that the current implementation of OCT-MIB could be improved
by replacing the MIS-enumeration algorithm with that of [30] and the bipartite
phase with the implementation of iMBEA used in [34].

### References

  * [1] A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev, $O(\sqrt{logn})$ approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, STOC, 2005, pp. 573–581.
  * [2] P. Agarwal, N. Alon, B. Aronov, and S. Suri, Can visibility graphs be represented compactly?, Discrete & Computational Geometry, 12 (1994), pp. 347–365.
  * [3] T. Akiba and Y. Iwata, Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover, Theoretical Computer Science, 609 (2016), pp. 211–225.
  * [4] G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. Hammer, and B. Simeone, Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics, 145 (2004), pp. 11–21.
  * [5] N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. on Computing, 14 (1985), pp. 210–223.
  * [6] M. Dawande, P. Keskinocak, J. Swaminathan, and S. Tayur, On bipartite and multipartite clique problems, J. of Algorithms, 41(2001), pp. 388–403.
  * [7] V. Dias, C. De Figueiredo, and J. Szwarcfiter, Generating bicliques of a graph in lexicographic order, Theoretical Computer Science, 337 (2005), pp. 240–248.
  * [8] D. Eppstein, Arboricity and bipartite subgraph listing algorithms, Inf. Process. Lett., 51 (1994), pp. 207–211.
  * [9] M. Garey and D. Johnson, Computers and intractability: a guide to NP-completeness, 1979.
  * [10] A. Gély, L. Nourine, and B. Sadi, Enumeration aspects of maximal cliques and bicliques, Discrete applied mathematics, 157(7), (2009) pp. 1447–1459.
  * [11] T. Goodrich, E. Horton, and B. Sullivan, Practical Graph Bipartization with Applications in Near-Term Quantum Computing, arXiv preprint arXiv:1805.01041, 2018.
  * [12] N. Gülpinar, G. Gutin, G. Mitra, and A. Zverovitch, Extracting pure network submatrices in linear programs using signed graphs, Discrete Applied Mathematics, 137 (2004), pp. 359–372.
  * [13] E. Horton, K. Kloster, B. D. Sullivan, A. van der Poel, MI-bicliques, https://github.com/TheoryInPractice/MI-bicliques, October 2018.
  * [14] F. Hüffner, Algorithm engineering for optimal graph bipartization, International Workshop on Experimental and Efficient Algorithms, 2005, pp. 240–252.
  * [15] Y. Iwata, K. Oka, and Y. Yoshida, Linear-time FPT algorithms via network flow, SODA, 2014, pp. 1749–1761.
  * [16] M. Kaytoue-Uberall, S. Dupelessis, and A. Napoli, Using formal concept analysis for the extraction of groups of co-expressed genes, Modelling, Computation and Optimization in Information Systems and Management Sciences, 2008, pp. 439–449.
  * [17] M. Kaytoue, S. Kuznetsov, A. Napoli, and S. Duplessis, Mining gene expression data with pattern structures in formal concept analysis, Information Sciences, 181 (2011), pp. 1989–2011.
  * [18] S. Kratsch and M. Wahlström, Compression via matroids: a randomized polynomial kernel for odd cycle transversal, ACM Transactions on Algorithms (TALG), 10 (2014), pp. 20:1–20:15.
  * [19] R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, Trawling the Web for emerging cyber-communities, Computer Networks, 31 (1999), pp. 1481–1493.
  * [20] S. Kuznetsov, On computing the size of a lattice and related decision problems, Order, 18 (2001), pp. 313–321.
  * [21] J. Li, G. Liu, H. Li, and L. Wong, Maximal biclique subgraphs and closed pattern pairs of the adjacency matrix: A one-to-one correspondence and mining algorithms, IEEE Trans. Knowl. Data Eng., 19 (2007), pp. 1625–1637.
  * [22] D. Lokshtanov, S. Saurab, and S. Sikdar, Simpler parameterized algorithm for OCT, International Workshop on Combinatorial Algorithms, 2009, pp. 380–384.
  * [23] D. Lokshtanov, S. Saurab, and M. Wahlström, Subexponential parameterized odd cycle transversal on planar graphs, LIPIcs-Leibniz International Proceedings in Informatics, 18 (2012).
  * [24] K. Makino and T. Uno, New algorithms for enumerating all maximal cliques, Scandinavian Workshop on Algorithm Theory, 2004, pp. 260–272.
  * [25] R. Mushlin, A. Kershenbaum, S. Gallagher, and T. Rebbeck, A graph-theoretical approach for pattern discovery in epidemiological research, IBM Systems J., 46 (2007), pp. 135–149.
  * [26] A. Panconesi and M. Sozio, Fast hare: A fast heuristic for single individual SNP haplotype reconstruction, International workshop on algorithms in bioinformatics, 2004, pp. 266–277.
  * [27] R. Peeters, The maximum edge biclique problem is NP-complete, Discrete Applied Mathematics, 131 (2003), pp. 651–654.
  * [28] M. Sanderson, A. Driskell, R. Ree, O. Eulenstein, and S. Langley, Obtaining maximal concatenated phylogenetic data sets from large sequence databases, Molecular biology and evolution, 20 (2003), pp. 1036–1042.
  * [29] J. Schrook, A. McCaskey, K. Hamilton, T. Humble, and N. Imam, Recall Performance for Content-Addressable Memory Using Adiabatic Quantum Optimization Entropy, 19 (2017).
  * [30] S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM J. on Computing, 6 (1977), pp. 505–517.
  * [31] L. Valiant, The complexity of enumeration and reliability problems, SIAM J. on Computing, 8 (1979), pp. 410–421.
  * [32] R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, Ordered sets, 1982, pp. 445–470.
  * [33] M. Yannakakis, Node-and edge-deletion NP-complete problems, STOC, 1978, pp. 253–264.
  * [34] Y. Zhang, C. A. Phillips, G. L. Rogers, E. J. Baker, E. J. Chesler, and M. A. Langston, On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types, BMC Bioinformatics, 15 (2014).

## Appendices

###  Appendix A Extremal Case for Zhang et al.

The $O(\mathcal{B}m)$ runtime444 where $\mathcal{B}$ is the number of MIBs
found stated for the algorithm iMBEA in [34] contains a typo. The corrected
runtime is $O(\mathcal{B}nm)$. In their analysis they bound the number of
nodes in their seach tree and derive their complexity by bounding the time
spent on each one by $O(m)$. They show that the number of intermediate search
tree nodes is at most $\sum_{i=0}^{d-1}(n-1)^{i}$, which is $O(\mathcal{B})$,
and that the number of leaves is at most $(n-1)^{d}$ which is said to be
$O(\mathcal{B})$. However, by the geometric series, the number of leaves can
only be bounded by $O(\mathcal{B}n)$, giving an $O(\mathcal{B}n)$ bound on the
number of search tree nodes. We now provide an example of a graph where the
number of leaves is $\Omega(\mathcal{B}n)$, implying that the number of leaves
cannot be $O(\mathcal{B})$ in the general case.

Graphs which are a perfect matching plus an apex to one node from each edge in
the matching provide an example of a graph family where this extremal behavior
manifests. Note that these graphs are bipartite with $n_{a}$ nodes in the
smaller partition and $n_{b}=n_{a}+1$ in the larger. See Figure 5 for the
instance where $n_{a}=4$ and $n_{b}=5$. There are $\mathcal{B}=(n_{a}+1)$ MIBs
in such a graph. Assume the nodes in the smaller partition are labeled
$a_{1},\dots,a_{n_{a}}$. For $1<i<n_{a}$, iMBEA attempts to expand the
biclique containing $a_{i}$ and its two neighbors with all nodes in
$\\{a_{i+1},\dots,a_{n_{a}}\\}$, each of which creates a leaf in the search
tree. Thus there are $\sum_{i=2}^{n_{a}-1}n_{a}-i=\Omega({n_{a}}^{2})$ leaves
created and the number of leaves is
$\Omega(\mathcal{B}n_{a})=\Omega(\mathcal{B}n)$.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$ Figure 5:  An
example of a graph in which iMBEA would run in time $\Omega(Bmn)$.

###  Appendix B OCT-MIB Algorithm

Here we provide the details of the mechanics of OCT-MIB. Please refer to
Section 4.1 for an outline of OCT-MIB. Both OCT-MIB and MCB utilize the
_blueprint_ data structure, described below.

Definition. A blueprint is an octuple of sets
$(S_{I},~{}IF_{I},~{}CC_{I},~{}S_{W},~{}S_{P},~{}IF_{O},~{}CC_{O},~{}O_{IF})$
and a specified node $next$. The sets $S_{I},S_{W},S_{P}\subseteq S$ satisfy

  * $\bullet$

$S_{I}\subseteq S$ contains the $S$-nodes in the biclique

  * $\bullet$

$S_{W}:=\\{x\in S\,|\,\phi(x)>\phi(w)\forall w\in S_{I}$}

  * $\bullet$

$S_{P}:=S\setminus(S_{I}\cup S_{W})$.

The sets $IF_{I},IF_{O},CC_{I},CC_{O}\subseteq V(G)\setminus S$ with

  * $\bullet$

$IF_{I}\subseteq\mathcal{I}(S_{I})$

  * $\bullet$

$IF_{O}:=\mathcal{I}(S_{I})\setminus IF_{I}$

  * $\bullet$

$CC_{I}\subseteq\mathcal{C}(S_{I})$

  * $\bullet$

$CC_{O}:=\mathcal{C}(S_{I})\setminus CC_{I}$,

and the set $O_{IF}:=(\mathcal{I}(S_{I})\cap O)\setminus S$. Finally,

$next:=\displaystyle{\operatorname*{argmin}_{s\in\\{S_{W}\cap\mathcal{I}(IF_{I})\cap\mathcal{C}(CC_{I})\\}}\phi(s)}.$

By design, $(S_{I}\cup IF_{I})\times CC_{I}$ is an induced biclique and is
represented by the blueprint. We refer to blueprints and the bicliques they
represent interchangeably in the description and discussion of the algorithms.

Within $S$, $S_{W}$ is the set of nodes that are still candidates to be
expanded with, while $S_{P}$ is the set of nodes that have been considered to
be in a biclique with the current $S_{I}$ elsewhere. We use $IF_{O}$ and
$CC_{O}$ to check near-maximality, and $O_{IF}$ to check global maximality in
OCT-MIB. The vertex $next$ is used to prevent expansions which produce
bicliques which are not future-maximal. We defer complete descriptions of the
algorithmic mechanics to Appendix B.1 (OCT-MIB) and Appendix C (MCB),
respectively.

####  B.1 OCT-MIB Algorithm

We begin by explaining checks for various properties of a blueprint, including
not-future-max($b$, $G$) and maximal($b,G$). If the node we are expanding with
is ordered later than $next$, then we are able to detect that the expansion
will not yield a new blueprint. We say that a biclique is _invalid_ if
$CC_{I}$ is empty. A blueprint $b$ is _not future-maximal_ if at least one of
the following conditions is met; (i)
$S_{P}\cap(\mathcal{C}(CC_{I})\cap\mathcal{I}(IF_{I}))\neq\emptyset$, (ii)
$CC_{O}\cap(\mathcal{I}(CC_{I})\cap\mathcal{C}(IF_{I}))\neq\emptyset$, or
(iii) $IF_{O}\cap(\mathcal{I}(IF_{I})\cap\mathcal{C}(CC_{I}))\neq\emptyset$.
Note conditions (ii) and (iii) imply $b$ is not near-maximal. Finally a
blueprint $b$ is _maximal_ $(S_{W}\cup
O_{IF})\cap(\mathcal{C}(CC_{I})\cap\mathcal{I}(IF_{I}))=\emptyset$. We note
that each of these checks can be done in $O(m)$ time.

Bipartite phase. We run the algorithm from Appendix A on $G[L,R]$, and for
each biclique found we check if an OCT node can be added to either side, which
can be done in $O(m)$ time. If an OCT node cannot be added then we have found
a MIB.

Initialization phase. Recall that OCT-MIB iterates over MISs in $O$; let
$S=s_{1},\dots,s_{|S|}$ be the current MIS. For each $s_{i}$ we create a new
bag $r_{i}$ which will hold blueprints. Let $S_{I}=\\{s_{i}\\}$,
$S_{W}=\\{s_{i+1},\dots,s_{|S|}\\}$, $S_{P}=\\{s_{1},\dots,s_{i-1}\\}$ and
$O_{IF}=O\setminus(N(s_{i})\cup S)$. Now we find candidate blueprints in three
rounds, adding the future-maximal ones to $r_{i}$.

In the first round, for each MIS $I\subseteq N(s_{i})$, we check if any node
from $\overline{N}_{L}(s_{i}):=L\setminus N(s_{i})$ or
$\overline{N}_{R}(s_{i}):=R\setminus N(s_{i})$ is in $\mathcal{C}(I)$. If no
node from either set is completely connected to $I$, we create a candidate
blueprint where $CC_{I}=I$, $CC_{O}=N(s_{i})\setminus I$, $IF_{I}=\emptyset$,
$IF_{O}=(L\cup R)\setminus N(v_{i})$, and $S_{I}$, $S_{W}$, $S_{P}$, and
$O_{IF}$ are defined as above. Otherwise we continue on to processing the next
MIS in $N(s_{i})$ and do not create a candidate blueprint for $I$.

In the second round, we run MCB on the subgraph induced on
$\overline{N}_{L}(s_{i})\cup(N(s_{i})\setminus L)$ with
$X=\overline{N}_{L}(s_{i})$. Then for each returned MCB $A\times B$, we find
the set of nodes
$\overline{N}_{R}(s_{i})^{+}:=\overline{N}_{R}(s_{i})\cap(\mathcal{I}(A)\cap\mathcal{C}(B))$.
We create a candidate blueprint with $CC_{I}=B$, $CC_{O}=N(s_{i})\setminus B$,
$IF_{I}=A\cup\overline{N}_{R}(s_{i})^{+}$, $IF_{O}=(L\cup
R)\setminus(N(v_{i})\cup A\cup\overline{N}_{R}(s_{i})^{+})$, and $S_{I}$,
$S_{W}$, $S_{P}$, and $O_{IF}$ defined as above.

In the third round, we run MCB on the subgraph induced on
$\overline{N}_{R}(s_{i})\cup(N(s_{i})\setminus R)$ with
$\overline{N}_{R}(s_{i})$ as the designated independent set. For each returned
MCB $A\times B$, we check if
$\overline{N}_{L}(s_{i})\cap(\mathcal{I}(A)\cap\mathcal{C}(B))=\emptyset$. If
so, we create a candidate blueprint where $CC_{I}=B$,
$CC_{O}=N(s_{i})\setminus B$, $IF_{I}=A$, $IF_{O}=(L\cup
R)\setminus(N(v_{i})\cup A)$, and $S_{I}$, $S_{W}$, $S_{P}$, and $O_{IF}$ are
defined as above. Otherwise, we continue processing the next MCB (without
creating a candidate blueprint for $A\times B$).

We check each candidate blueprint for future-maximality, adding it to $r_{i}$
if true, and discarding it otherwise. If the blueprint is maximal we add
$(S_{I}\cup IF_{I})\times CC_{I}$ to the set of maximal bicliques and let
$next=\infty$. If the blueprint is not maximal because an OCT node can be
added to it we also let $next=\infty$; if it is not maximal because of an
$S$-node later in the ordering we let $next$ be the first such node from
$S_{W}$. The blueprint remains in $r_{i}$ in either case. As long as $r_{i}$
is non-empty we add it to $T$, the set of bags to be processed in the
expansion phase.

Expansion phase. We now process bags from $T$ until it is empty. We refer to
removing a bag $b$ from $T$ and expanding on all of the blueprints in $b$ with
a vertex $v$ as _branching on $b$ with $v$_. In OCT-MIB $S_{I}$, $S_{W}$,
$S_{P}$, and $O_{IF}$ are the same in all blueprints in a given bag and we
branch on a bag with all of the nodes in $S_{W}$ in the order which matches
the order of $S$; $w_{1},\dots,w_{|S_{W}|}$.

Let $w_{i}$ be the node we are currently branching with and $c_{i}$ be a bag
we create to hold new blueprints formed by expanding with $w_{i}$. Let
$P=(S_{I},~{}IF_{I},~{}CC_{I},~{}S_{W},~{}S_{P},~{}IF_{O},~{}CC_{O},~{}O_{IF},~{}next)$
be the blueprint currently being expanded with. If we can detect that the
expansion will not yield a new blueprint we terminate this expansion.
Otherwise we create a new blueprint
$P^{\prime}=(S_{I}^{\prime},~{}IF_{I}^{\prime},~{}CC_{I}^{\prime},~{}S_{W}^{\prime},~{}S_{P}^{\prime},~{}IF_{O}^{\prime},~{}CC_{O}^{\prime},~{}O^{\prime}_{IF},~{}next^{\prime})$
as follows.

Let $S_{I}^{\prime}=S_{I}\cup\\{w_{i}\\}$, $IF_{I}^{\prime}=IF_{I}\setminus
N(w_{i})$, $CC_{I}^{\prime}=CC_{I}\cap N(w_{i})$,
$S_{W}^{\prime}=\\{w_{i+1},\dots,w_{|S_{W}|}$,
$S_{P}^{\prime}=S_{P}\cup\\{w_{1},\dots,w_{i-1}\\}$,
$IF_{O}^{\prime}=IF_{O}\setminus N(w_{i})$, $CC_{O}^{\prime}=CC_{O}\cap
N(w_{i})$, and $O^{\prime}_{IF}=O_{IF}\setminus N(w_{i})$. If
$(S_{I}^{\prime}\cup IF_{I}^{\prime})\times CC_{I}^{\prime}$ is invalid or it
is not future-maximal, we terminate the expansion.

We must consider the case where the tuples $(CC_{I}^{\prime},IF_{I}^{\prime})$
from different blueprints are identical after expansion. To handle this we
maintain a hashtable for the current $w_{i}$ being branched with, and hash
each tuple $(CC_{I}^{\prime},IF_{I}^{\prime})$ and terminate if we find a
conflict. This hashtable can be discarded once we finish branching with the
current node.

If the expansion has not been terminated then $P^{\prime}$ is future-maximal
so we add $P^{\prime}$ to $c_{i}$. If the blueprint is maximal we add
$(S_{I}^{\prime}\cup IF_{I}^{\prime})\times CC_{I}^{\prime}$ to the set of
maximal bicliques and let $next^{\prime}=\infty$. If the blueprint is not
maximal solely because of nodes from $O_{IF}^{\prime}$ we also let
$next^{\prime}=\infty$, but if it is not maximal because of a node from
$S_{W}^{\prime}$ we let $next$ be the first such node from $S_{W}^{\prime}$.
The blueprint remains in $c_{i}$ in either case. Once again we continue the
expansion phase until all bags have been branched upon.

####  B.2 Correctness & Complexity: OCT-MIB

We now provide proofs of the correctness and asymptotic complexity of OCT-MIB,
which were originally stated in Section 5.

See 5

###### Proof.

Suppose that there is a MIB $A\times B$ that OCT-MIB does not find. If there
are no nodes from $O$ in $A\cup B$ then the biclique would be found in the
bipartite phase, thus we may assume there is a node from $O$ in the biclique.

Without loss of generality we may assume that $A$ contains OCT-nodes and that
if $A$ contains nodes from $L$ or $R$ then $B$ contains nodes from the other.
We let $A^{O}=A\cap O$ and $A^{L,R}=A\setminus A^{O}$. Note that $A^{O}$ must
be contained in some MIS $S$ in $O$. Let $a_{1}^{O}$ be the first node in
$A^{O}$ with respect to $\phi$; we show that when we initialize with
$a_{1}^{O}$, $B\subseteq CC_{I}$ and $A^{L,R}\subseteq IF_{I}$ for some
blueprint in $r_{a_{1}^{O}}$. $A^{L,R}$ is either empty or contains nodes from
one of $\\{L,R\\}$, and we show that a candidate blueprint as described above
is created in both cases.

By definition, $B$ must be contained within an MIS $I_{B}$ in $N(a_{1}^{O})$.
If $A^{L,R}$ is empty and a candidate blueprint with $B\subseteq CC_{I}$ is
not created in the first round, then there must be nodes in
$\overline{N}_{L}(a_{1}^{O})$ or $\overline{N}_{R}(a_{1}^{O})$ which are in
$\mathcal{C}(I_{B})$. If a node $\bar{l}$ from $\overline{N}_{L}(a_{1}^{O})$
is in $\mathcal{C}(I_{B})$ then $\bar{l}\times I_{B}$ is a crossing biclique
in the instance of MCB called in the second round. Thus a maximal crossing
biclique which contains $I_{B}$ is returned and a candidate blueprint with
$B\subseteq CC_{I}$ is created. Otherwise a node $\bar{r}$ from
$\overline{N}_{R}(a_{1}^{O})$ is in $\mathcal{C}(I_{B})$ and $\bar{r}\times
I_{B}$ is a crossing biclique in the instance of MCB called in the third
round, leading to the creation of a candidate blueprint with $B\subseteq
CC_{I}$.

If $A^{L,R}\neq\emptyset$, assume without loss of generality that
$A^{L,R}\subseteq L$. Then there is a crossing biclique $A^{L,R}\times B$ in
the instance of MCB called in the second round, and a candidate blueprint with
$B\subseteq CC_{I}$ and $A^{L,R}\subseteq IF_{I}$ is created.

If a candidate blueprint with $B\subseteq CC_{I}$ and $A^{L,R}\subseteq
IF_{I}$ is pruned away because of an $S_{P}$ node, then $A\times B$ is not a
maximal biclique. So there exists a blueprint $P^{*}$ in $r_{a_{1}^{O}}$ where
$B\subseteq CC_{I}$ and $A^{L,R}\subseteq IF_{I}$. Expanding $P^{*}$ so that
$S_{I}=A$ would yield the biclique $A\times B$ as $(S_{I}\cup IF_{I})\times
CC_{I}$. Thus as long as we expand for each node in $A$ we will find the
biclique $A\times B$.

Assume that an expansion with a node in $A$ is not made and let $a^{O}_{k}$ be
the first such node. The blueprint would not have been discarded because of
$CC_{I}^{\prime}$ being empty or a node from $S_{P}^{\prime}$ or
$O^{\prime}_{IF}$ being in
$\mathcal{C}(CC_{I}^{\prime})\cap\mathcal{I}(IF_{I})$, as this would imply
$A\times B$ is not a MIB. If a node from from $CC_{O}^{\prime}$ or
$IF_{O}^{\prime}$ made $P^{*}$ not near-maximal when expanding with the node
prior to $a^{O}_{k}$ in $A$, $a^{O}_{k-1}$, consider a blueprint $Q^{+}$
formed by adding nodes from $IF_{O}^{\prime}$ to $IF_{I}^{\prime}$ and
$CC_{O}^{\prime}$ to $CC_{I}^{\prime}$ such that $(S_{I}^{\prime}\cup
IF_{I}^{\prime})\times CC_{I}^{\prime}$ forms a future-maximal biclique. This
blueprint must exist at the bag created by expanding with $a^{O}_{k-1}$ and it
contains $B$ in $CC_{I}$ and $A^{L,R}$ in $IF_{I}$. We now let that blueprint
be $P^{*}$.

Thus $a^{O}_{k}$ must be greater than $next$ for blueprint $P^{*}$ at the bag
with $S_{I}=a^{O}_{1},\dots,a^{O}_{k-1}$. Because of how we constructed
$next$, it is not in $S_{I}$. Therefore $next$ is not in $A$ but because $X$
is an independent set, it is independent from $A$. Furthermore $next$ is
completely connected to $B$ because it is completely connected to $CC_{I}$ and
$B\subseteq CC_{I}$. Thus $A\times B$ would not be a maximal biclique and we
obtain a contradiction. We can apply this argument inductively to show the
complete correctness of the algorithm.

∎

See 5

###### Proof.

We note that $G$ has no isolates, therefore $n_{L}$ and $n_{R}$ are $O(m)$. We
first compute the complexity of finding a maximal biclique when iterating over
a single MIS $S$ in OCT. In the initialization phase, finding the MISs in
round one takes $O(mn)$ time per MIS. Finding the MCBs in rounds two and three
takes $O(mnn_{O})$ per MCB. This is because the arboricity of $Y$ in each call
to MCB is $O(n_{O})$. Therefore the time it takes to initialize a blueprint is
$O(mn_{O})$ not $O(mn)$ [5]. Because of how we have utilized $next$, each node
in $S$ is expanded with $O(1)$ times per MIB. Each expansion can be done in
$O(m)$ time, and thus the total time spent expanding is $O(mn_{O})$ per
maximal biclique. Since we only expand on blueprints which are future-maximal,
every expansion is accounted for.

There may be an additional $O(n_{O})$ initializations of a blueprint. Thus the
total complexity of finding a single maximal biclique when iterating over $S$
is $O(mnn_{O}^{2})$. A biclique can be found once per MIS in OCT, and thus the
total complexity of OCT-MIB is $O(Mmnn_{O}^{2}I_{O})$, where $M$ is the number
of maximal bicliques and $I_{O}$ is the number of MIS’s in OCT.

The space complexity for storing a single blueprint is $O(n)$ and since all
blueprints which are stored are future-maximal there is one blueprint per MIB
stored at any given time.

∎

###  Appendix C MCB Algorithm

Figure 6:  Runtimes of OCT-MIB and LexMIB under varied bipartite balance
conditions. For $n_{B}=200$ (Left, and $n_{B}=1000$ (Right), each curve
represents the runtime in seconds of an algorithm on graphs with a given OCT
size and varied balance. See the Extended Results: Size/Balance paragraph for
details on timeouts.

In this section we present the details of our algorithm MCB for finding all
maximal crossing bicliques, along with proofs of correctness and runtime
complexity.

####  MCB Description

Given an instance $(G,X,Y)$, MCB enumerates all maximal crossing bicliques.
MCB makes use of the same checks as OCT-MIB as described in Section B.1.

Initialization phase. Recall that $S=X$ in MCB. To begin this phase, we fix an
order of $S$, $v_{1},\dots,v_{|X|}$. For each $v_{i}$ we create a new bag
$r_{i}$ which will hold blueprints. We let $S_{I}=\\{v_{i}\\}$,
$S_{W}=\\{v_{i+1},\dots,v_{|X|}\\}$, $S_{P}=\\{v_{1},\dots,v_{i-1}\\}$. We
then find all maximal independent sets in $G[N(v_{i})]$ in $O(|Y|m)$ time per
_MIS_ [30]. For each _MIS_ $I$ we create a blueprint where $CC_{I}=I$,
$CC_{O}=N(v_{i})\setminus I$, and $S_{I}$, $S_{W}$, and $S_{P}$ are defined as
above. In MCB $IF_{I}$, $IF_{O}$, and $O_{IF}$ are not used in any blueprints.

For each blueprint, if it is not future-maximal, we discard it; otherwise, we
add it to $r_{i}$. If the blueprint is maximal we add $S_{I}\times CC_{I}$ to
the set of maximal crossing bicliques and let $next=\infty$. If it is not
maximal we let $next$ be the first node from $S_{W}$ which is completely
connected to $CC_{I}$. The blueprint remains in $r_{i}$ in either case. As
long as $r_{i}$ is non-empty we add it to $T$, the set of bags to be processed
in the expansion phase.

Expansion phase. Once we have initialized with each $v_{i}$, we process bags
from $T$ until it is empty. We refer to branching in the same manner as in
Section B.1. Note that $S_{I},S_{W},$ and $S_{P}$ are the same in all of the
blueprints at bag $b$. We will branch on $b$ with all nodes in $S_{W}$, which
we order $x_{1},\dots,x_{|S_{W}|}$ to be consistent with the order of $S$. Let
$x_{i}$ be the node we are currently branching on $b$ with and $c_{i}$ be a
bag we create to hold new blueprints formed by expanding with $x_{i}$. When
branching with $x_{i}$, we iterate over the blueprints in $b$ and expand on
them one at a time. Whether an expansion is terminated or completed, we
continue with expanding the next blueprint in $b$.

Let $P=(S_{I},~{}CC_{I},~{}S_{W},~{}S_{P},~{}CC_{O},~{}next)$ be the blueprint
currently being expanded on. If we determine the expansion will not yield a
future-maximal blueprint, we terminate. Otherwise we will create a new
blueprint $P^{\prime}$ with values
$(S_{I}^{\prime},~{}CC_{I}^{\prime},~{}S_{W}^{\prime},~{}S_{P}^{\prime},~{}CC_{O}^{\prime},~{}next^{\prime})$
as follows. We let $S_{I}^{\prime}=S_{I}\cup\\{x_{i}\\}$,
$CC_{I}^{\prime}=CC_{I}\cap N(x_{i})$,
$S_{W}^{\prime}=\\{x_{i+1},\dots,x_{|S_{W}|}\\}$,
$S_{P}^{\prime}=S_{P}\cup\\{x_{1},\dots,x_{i-1}\\}$, and
$CC_{O}^{\prime}=CC_{O}\cap N(x_{i})$. If $S_{I}^{\prime}\times
CC_{I}^{\prime}$ is invalid or it is not future-maximal we terminate this
expansion.

We must consider the case where two $CC_{I}^{\prime}$’s from different
blueprints are identical after expansion. To handle this we maintain a
hashtable for the current $x_{i}$ being branched with, and hash each
$CC_{I}^{\prime}$, terminating if we find a conflict. This hashtable can be
discarded once we finish branching with the current node.

The blueprint $P^{\prime}$ is future-maximal if it has not been discarded, so
we add it to $c_{i}$. If the blueprint is maximal we add $S_{I}^{\prime}\times
CC_{I}^{\prime}$ to the set of maximal crossing bicliques and let
$next=\infty$. If it is not maximal we let $next$ be the first node from
$S_{W}^{\prime}$ which is completely connected to $CC_{I}^{\prime}$.
$P^{\prime}$ remains in $c_{i}$ in either case. Once we have expanded on all
blueprints from $b$ we add $c_{i}$ to $T$ if it is non-empty, continuing to
branch on any bag in $T$ that has not yet been branched on.

####  C.1 Correctness & Complexity: MCB

We now establish the correctness and asymptotic complexity of MCB.

######  Theorem C.1.

MCB finds all maximal crossing bicliques.

###### Proof.

Suppose there is a maximal crossing biclique $A\times B$, $A\subseteq S=X$,
$B\subseteq Y$ that our algorithm does not find. Consider the ordering of $A$
which is consistent with the ordering of $S$ that we fixed upon initialization
and let $a_{1}$ be the first node. Upon initialization $B$ must be contained
in an MIS in $a_{1}$’s neighborhood. Let $P^{*}$ be a blueprint which has this
property. Applying the expansions which lead to $S_{I}=A$ to blueprint $P^{*}$
yields $A\times B$ as $S_{I}\times CC_{I}$. Thus we must show that each of
these expansions are made for some $P^{*}$.

Assume that an expansion with a node in $A$ is not made and let $a_{k}$ be the
first such node. The blueprint would not have been discarded because of
$CC_{I}^{\prime}$ being empty or a node from $S_{P}^{\prime}$ being completely
connected to $CC_{I}^{\prime}$, as this would imply $A\times B$ is not a
maximal crossing biclique. If a node from $CC_{O}^{\prime}$ was completely
independent from $CC_{I}^{\prime}$ when expanding with the node prior to
$a_{k}$ in $A$, $a_{k-1}$, consider a blueprint $Q^{+}$ formed by adding a
maximal independent set of the $CC_{O}^{\prime}$ nodes which can be added to
$CC_{I}^{\prime}$ in $Q$. This blueprint must exist at the bag created by
expanding with $a_{k-1}$ and it contains $B$ in $CC_{I}$. We now let $Q^{+}$
be $P^{*}$.

Thus $a_{k}$ must be greater than $next$, $x$, for blueprint $P^{*}$ at the
bag with $S_{I}=a_{1},\dots,a_{k-1}$. Because of how we constructed $next$, we
know that $x$ is not in $S_{I}$. Therefore $x$ is not in $A$ but because $X$
is an independent set, it is independent from $A$. Furthermore $x$ is
completely connected to $B$ because it is completely connected to $CC_{I}$ and
$B\subseteq CC_{I}$. Thus $A\times B$ would not be a maximal biclique and we
obtain a contradiction. We can apply this argument inductively to show the
complete correctness of the algorithm. ∎

######  Theorem C.2.

MCB runs in $O(M|X||Y|m)$ on the instance $(G,X,Y)$, where $M$ is the number
of maximal crossing bicliques. The space complexity of MCB is $O(Mn)$.

###### Proof.

First note that if a node in $X$ has no neighbors in $Y$ it will not be in any
biclique so we can delete it, and vice versa. Therefore $|X|$ and $|Y|$ are
$O(m)$.

We view the complexity of our algorithm through the lens of the amount of time
it takes to find each maximal crossing biclique. First note that the time it
takes to initialize a single blueprint and check it for maximality is
$O(|Y|m)$, while the time it takes to expand a blueprint is $O(m)$. Now
consider a maximal blueprint $P$ which is found via expanding from a bag $H$.
The bag $H$ is formed by branching on a series of other bags, $H$’s
_ancestors_ ; $A_{1},\dots,A_{t}$. One could trace the expansions which led to
$P$ to find the corresponding blueprint in each ancestor bag. Let $A_{F}$ be
the closest ancestor bag of $H$ where the corresponding blueprint is maximal
if such a bag exists and let $A_{F}=A_{1}$ otherwise. Because of how we have
utilized $next$, for each node $v$ in $X$ there is at most one total expansion
of a corresponding blueprint from a bag in $\\{A_{F},\dots,A_{t}\\}$. Thus the
total time spent expanding is $O(|X|m)$ per blueprint. Furthermore because we
only expand future maximal blueprints every expansion is accounted for.

We note that there may be an additional $O(|X|)$ initializations of a
blueprint, which impacts the complexity. Thus the total complexity of finding
a single maximal crossing biclique is $O(|X||Y|m)$.

The size of each blueprint is $O(n)$ and there is one blueprint stored per MIB
at a given time, thus the space complexity of MCB is $O(Mn)$. ∎

###  Appendix D Data and Infrastructure

##### Random Graphs

Our random graph generator is based on the bipartite generator555The authors
of [34] generously provided source code for the generator used in their paper.
used in [34] and requires the user to specify $n_{L}$, $n_{R}$, and $n_{O}$,
the expected edge densities between $L$ and $R$, $O$ and $\\{L,R\\}$ and
within $O$, as well as the coefficient of variance (cv = standard deviation
divided by mean) of the degrees of the smaller partition of $L$ and $R$. We
also allow the generator to take in a seed for random number generation.

To add the edges between $L$ and $R$, the edge density and cv values are used
to assign vertex degrees to the smaller partition of $\\{L,R\\}$, and then
neighbors are selected from the other partition uniformly at random; this was
implemented in the generator of [34]. Edges are added between $O$ and
$\\{L,R\\}$ via the same process, only with the corresponding edge density and
cv values. Finally, we add edges within $O$ with an Erdős-Rényi process; where
the edge probabilities correspond to the expected densities (no cv value is
used here).

##### Hardware

All experiments were run on identical hardware; each server had four Intel
Xeon E5-2623 v3 CPUs (3.00GHz) and 64GB DDR4 memory. The servers ran Fedora 27
with Linux kernel 4.16.7-200.fc27.x86_64. The C/C++ codes were compiled using
gcc/g++ 7.3.1.

##### Extended Results: Size/Balance

To evaluate the effect of $n_{B}$ and $b$, we generated 5 instances for all
pairwise combinations of $n_{B}\in\\{200,1000\\}$ and $b\in\\{$1:1, 1:2, 1:10,
1:100$\\}$ and ran both OCT-MIB and LexMIB, see Figure 6. When $n_{B}$ was
1000, OCT-MIB timed out ($3600s$) on 90% of instances with balance 1:1 and
1:2. LexMIB timed out on 100% of instances at these settings, as well as 70%
of those with balance 1:10. Larger timeouts are needed to fully understand the
performance in these settings.