Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers Aryan Esmailpour

Khoi Le

Stavros Sintos

Department of Computer Science University of Illinois Chicago USA

Department of Computer Science University of Illinois Chicago USA

Department of Computer Science University of Illinois Chicago USA

arXiv:2608.20767v1 [cs.DS] 21 Aug 2026

Abstract Bipartite graphs are a fundamental representation for relational data arising in recommendation systems, market-basket analysis, social networks, and communication graphs. A key challenge in these settings is to store and transmit large bipartite graphs compactly while preserving exact structural and path information. We study biclique-based representations of bipartite graphs 𝑮 = (𝑽, 𝑼 , 𝑬), where the edge set is encoded using a collection of complete bipartite subgraphs. We focus on the Weighted Biclique Covering problem, which minimizes the total number of vertices used across all bicliques, and introduce a generalized variant that additionally penalizes the number of bicliques, capturing practical overheads in storage, transmission, and model complexity. While the weighted biclique covering problem is known to be NP-Complete, we show that the generalized variant is also NPComplete. Despite this hardness, many real-world bipartite graphs admit low-dimensional geometric embeddings or can be well approximated by them. Leveraging this observation, we develop the first approximation algorithms with provable guarantees for the (generalized) weighted biclique covering problem on geometric bipartite graphs. Specifically, for 𝛿-disk bipartite graphs in low𝑑 spaces, we design a polynomial-time algorithm that dimensional ℓ∞ achieves an 𝑂 (log |𝑼 | · log𝑑 |𝑽 |)-approximation, combining ideas from greedy set cover, geometric range searching, and densest subgraph optimization. We also show how our algorithms extend to ℓ𝛼𝑑 metrics for any 𝛼 ≥ 1. Finally, we evaluate our algorithms on real-world bipartite datasets and show that they efficiently compute significantly smaller biclique-based representations than natural baselines, while scaling to large graphs.

1

Introduction

Bipartite graphs provide a natural and expressive framework for modeling relational data arising in a wide range of applications, including social and biological networks, job matching, dating platforms, recommendation systems, and resource allocation [63]. As modern datasets continue to grow in scale, the corresponding graphs often contain massive numbers of vertices and edges, making both storage and algorithmic processing increasingly challenging. In particular, the cost of running classical graph algorithms can become prohibitive as graph size and density increase. Graph representation and compression techniques have therefore emerged as essential tools for mitigating these challenges. A common goal of such methods is to reduce the size of the graph, typically by decreasing the number of explicitly stored edges, while preserving its essential structural properties. For many downstream tasks, however, it is crucial that the compressed representation preserves path information, namely reachability and shortest-path

𝑽

𝑼

1

a

3

2

b

c

d

e

f

Figure 1: Example of graph compression using biclique edge covers. The red edges belong to the first biclique (𝐾2,4 defined by {1, 2} × {𝑎, 𝑏, 𝑐, 𝑑}), and the blue edges belong to the second biclique (𝐾2,4 defined by {2, 3} × {𝑐, 𝑑, 𝑒, 𝑓 }). The purple edges belong to both bicliques. The total size of this cover is 6 + 6 = 12. An optimal biclique partition (disallowing overlaps) is given by {1, 2} × {𝑎, 𝑏, 𝑐, 𝑑 }, {2, 3} × {𝑒, 𝑓 }, and {3} × {𝑐, 𝑑 }, which results in a total size of 6 + 4 + 3 = 13. relationships between vertices. When this information is retained, the compressed graph can be used directly by path-sensitive algorithms such as matching, flow, and shortest-path computations, leading to substantial improvements in efficiency for large and dense graphs. Motivating scenario. Consider a cloud computing environment consisting of multiple computing nodes connected by a network. A bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) is initially stored on a machine 𝐴, but an expensive downstream graph algorithm, such as shortest paths, matching, or flow computation, must be executed on a computing node 𝐵. A natural approach is to transfer the graph from 𝐴 to 𝐵 and run the algorithm on the explicit edge representation. However, transferring the entire graph requires sending at least |𝑬 | objects over the network, and the subsequent running time of many classical graph algorithms also depends directly on the number of edges. For large and dense graphs, both the communication cost and the computational cost on 𝐵 can therefore become prohibitively expensive. This motivates the need for a compact representation that can be transmitted more efficiently and, at the same time, supports faster execution of downstream graph algorithms by replacing the original graph with a smaller path-preserving representation. A variety of graph compression and representation techniques [8, 12, 26, 28, 56] can be applied prior to transfer. However, most existing approaches incur substantial overhead when reconstructing complete path information, limiting their usefulness for downstream graph analytics. To address this limitation, prior work [29] and more recently [16] proposed a biclique-based representation that preserves exact path information. Specifically, the edge set of the bipartite graph 𝑮 is partitioned into complete bipartite subgraphs (bicliques). For a biclique 𝑆 ⊆ 𝑮 with vertex sets 𝑽𝑆 ⊆ 𝑽 and 𝑼𝑆 ⊆ 𝑼 , the |𝑽𝑆 | · |𝑼𝑆 | edges are replaced by a single auxiliary

Aryan Esmailpour, Khoi Le, and Stavros Sintos

node 𝑤 𝑆 connected to all vertices in 𝑽𝑆 ∪ 𝑼𝑆 . This transformation replaces |𝑽𝑆 | · |𝑼𝑆 | edges by |𝑽𝑆 | + |𝑼𝑆 | edges while preserving path information in the resulting graph. The size of biclique 𝑆 in the new representation is defined by |𝑽𝑆 | + |𝑼𝑆 |. Limitations of biclique partitions. While biclique partitions can yield compact graph representations, this line of work suffers from two important limitations. First, the requirement that the bicliques form a partition of the edge set is overly restrictive. Under this requirement, each edge of 𝑮 must belong to exactly one biclique, severely limiting the flexibility of the representation. Second, prior work does not explicitly study the optimization problem of constructing a representation of minimum size. In contrast, we observe that requiring only a cover of the edges by bicliques (allowing edges to appear in multiple bicliques) is sufficient to preserve path information using the same node-replacement construction. Furthermore, covering the edges by bicliques can lead to strictly smaller representations because every partition is a cover, however not every cover is a partition. Consequently, allowing coverings can only improve the quality of the resulting representation. Figure 1 presents an example illustrating that a biclique cover yields a smaller representation. Weighted biclique covering. Motivated by these observations, we study the problem of covering the edges of a bipartite graph 𝑮 with bicliques so as to minimize the size of the resulting representation, which is known as the Weighted Biclique Cover problem (WBC) [58]. Prior work on WBC has primarily only focused on upper and lower bounds on the optimal solution size [20, 24, 58, 59]. The problem has also been studied in the role-mining literature under the name edge-RMP [60], where it is shown to be NP-complete. Existing approaches for WBC (and equivalently edge-RMP) [48, 50, 60] rely on heuristics and do not provide theoretical guarantees. A generalized cost model. While we provide the first approximation algorithms for the WBC problem on certain classes of graphs, minimizing only the total size of the selected bicliques does not fully capture several realistic deployment scenarios. In many practical settings, an additional fixed cost is incurred for each selected biclique, independent of its size. Returning to the cloud computing scenario, suppose that the edges of each biclique are transferred as a single packet. Each packet incurs a fixed overhead that is independent of its payload (e.g., a network header). Let 𝑐 denote this per-biclique overhead. To better capture such costs, we introduce a generalized objective that accounts for both the total size of the selected bicliques and their number. We formalize this extension as the Generalized Weighted Biclique Cover problem (GWBC), whose goal is to minimize the sum of the sizes of the selected bicliques plus 𝑐 times their number. Although the GWBC problem has not been explicitly defined in prior work, it naturally interpolates between two known problems. When 𝑐 = 0, GWBC reduces to the WBC problem. In contrast, for sufficiently large values of 𝑐, GWBC reduces to the bipartite dimension problem, which seeks to minimize the number of bicliques needed to cover all edges of the input graph. While inapproximability results and exact algorithms for specific graph classes are known for the bipartite dimension problem on specific graph classes [4, 13, 14, 30, 37, 42, 46, 49, 57, 68], these results do not extend to GWBC.

Geometric structure and our approach. Despite the long history of WBC and its relevance to data compression and distributed computation, no approximation algorithms with theoretical guarantees are known, either for WBC or for its generalized variant GWBC. In this paper, we build on the observation that many graphs arising in practice are naturally disk graphs [7, 43, 45] (also referred to as proximity graphs [1]) or intersection graphs [39–41] or can be well approximated as such. In these graphs, nodes are embedded as points in a geometric space, and edges connect pairs of nodes that are sufficiently close. For example, social networks and coauthorship graphs can often be embedded, with small error, into the space of user profiles with low intrinsic dimension [62, 64]. More generally, for many networks across diverse domains (e.g., social, transportation, Internet), suitable embeddings exist that approximately preserve structural properties and shortest paths of the original graphs [62, 66, 67]. Although these graphs can be represented implicitly via their geometric embeddings, most classical graph algorithms require an explicit edge-based representation. Consequently, even geometrically embedded graphs must often be materialized and transmitted as conventional graphs. In this paper, we leverage the geometric structure of bipartite disk and intersection graphs to design the first approximation algorithms with provable guarantees for both WBC and GWBC.

1.1

Problem Definitions and our Contributions

Let 𝑮 (𝑽, 𝑼 , 𝑬) be a bipartite graph with two sets of vertices 𝑽 and 𝑼 , with 𝑛 = |𝑽 | + |𝑼 |, and a set of edges 𝑬 ⊆ 𝑽 × 𝑼 , with 𝑚 = |𝑬 |. For a subgraph 𝐺 ′ ⊆ 𝐺, let V (𝐺 ′ ) (or U (𝐺 ′ )) be the vertices of 𝑽 (or 𝑼 ) that are included in 𝐺 ′ . We also define D (𝐺 ′ ) = V (𝐺 ′ ) ∪ U (𝐺 ′ ), and |D (𝐺 ′ )| = |V (𝐺 ′ )| + |U (𝐺 ′ )|. Let E (𝐺 ′ ) be the set of edges in the subgraph 𝐺 ′ . Definition 1.1. (Biclique) A subgraph 𝑆 ⊆ 𝑮 of a given bipartite graph 𝑮 is a biclique (also called complete bipartite subgraph) if for every pair 𝑣 ∈ V (𝑆) and 𝑢 ∈ U (𝑆), (𝑣, 𝑢) ∈ E (𝑆). Definition 1.2. (Biclique Edge Cover) A collection of subgraphs S = {𝑆 1, . . . , 𝑆𝜅 }, is called a biclique edge covering of a given graph 𝑮, if for every 𝑖 = 1, . . . , 𝜅, 𝑆𝑖 is a biclique of 𝑮, and for each 𝑒 ∈ E (𝐺) there exists at least one 𝑆 𝑗 ∈ S, such that 𝑒 ∈ E (𝑆 𝑗 ). Next, we define two optimization problems studied in this paper. Definition 1.3. (Weighted Biclique Covering (WBC)) Given a bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) the goal is to construct a biclique ∑︁ edge cover S = {𝑆 1, . . . , 𝑆𝜅 } for 𝑮, with minimum cost 𝜇 (S) = |D (𝑆𝑖 )|. 𝑆𝑖 ∈ S

Definition 1.4. (Generalized Weighted Biclique Covering(GWBC)) Given a bipartite graph 𝑮 and a rational parameter 𝑐 ≥ 0 the goal is to construct a biclique edge cover S = {𝑆 1, . . . , 𝑆𝜅 } for 𝑮, with Í minimum cost 𝜎 (S) = 𝑐 · 𝜅 + 𝑆𝑖 ∈ S |D (𝑆𝑖 )|. In order to study the hardness we also define the decision version of the problems: Given a parameter 𝜏 > 0 the goal is to decide whether there exists a biclique edge cover S such that 𝜇 (S) ≤ 𝜏 for the WBC problem and 𝜎 (S) ≤ 𝜏 for the GWBC problem. We refer to these problems as dWBC and dGWBC, respectively. For a real number 𝛽 > 1, an algorithm is a 𝛽-approximation algorithm for the GWBC (resp. WBC) problem if it returns a biclique

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

edge cover S such that 𝜎 (S) ≤ 𝛽 · 𝜎 (S ∗ ) (resp. 𝜇 (S) ≤ 𝛽 · 𝜇 (S ∗ )), where S ∗ is the biclique edge cover with the minimum cost. For any 𝛼 ≥ 1, let 𝜓𝛼 : R𝑑 × R𝑑 → R be the distance function in ℓ𝛼𝑑 metric, defined as follows. For every pair of points 𝑣, 𝑢 ∈ R𝑑 , Í  1/𝛼 𝛼 𝜓𝛼 (𝑣, 𝑢) = where 𝑣 ( 𝑗) (resp. 𝑢 ( 𝑗)) 𝑗={1,...,𝑑 } |𝑣 ( 𝑗) − 𝑢 ( 𝑗)| is the 𝑗-th coordinate of point 𝑣 (resp. 𝑢). For 𝛼 = ∞ we have, 𝜓 (𝑣, 𝑢) = max 𝑗={1,...,𝑑 } |𝑣 𝑗 − 𝑢 𝑗 |. Next, we formally define the 𝛿-disk bipartite graph and the intersection bipartite graph. Definition 1.5. (𝛿-disk bipartite graph) A bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) is a 𝛿-disk bipartite graph in ℓ𝛼𝑑 metric if 𝑽 and 𝑼 are two finite sets of points in R𝑑 , and for any pair of points 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 there exists an edge (𝑣, 𝑢) ∈ 𝑬 if and only if 𝜓𝛼 (𝑣, 𝑢) ≤ 𝛿. A hyper-rectangle 𝑟 in R𝑑 is defined as 𝑟 = ×𝑑𝑗=1 𝐼 𝑗 , where each 𝐼 𝑗 is an interval specifying the range along the 𝑗-th coordinate. A hyper-rectangle is called a box if all its side lengths are equal, that is, if all intervals 𝐼 𝑗 have the same length. Definition 1.6. (Intersection bipartite graph) Graph 𝑮 (𝑽,𝑼,𝑬,R𝑉,R𝑈) is an intersection bipartite graph in R𝑑 if every node 𝑣 ∈ 𝑽 (𝑢 ∈ 𝑼 ) is associated with hyper-rectangle 𝑟 𝑣 ∈ R𝑉 (𝑟𝑢 ∈ R𝑈 ) in R𝑑 , and for any pair of points 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 there exists an edge (𝑣, 𝑢) ∈ 𝑬 if and only if 𝑟 𝑣 ∩ 𝑟𝑢 ≠ ∅. Our Contributions. Our results are summarized as follows. • In Section 2, we show that dGWBC is NP-complete. • To the best of our knowledge, no approximation algorithms with provable guarantees have previously been studied for the WBC problem, nor for its generalization GWBC, either on general graphs or on restricted graph classes. In Section 3, we present the first polynomial time 𝑂 (log𝑑+1 𝑛)-approximation algorithm for the 𝑑 metric. GWBC (and WBC) problem on 𝛿-disk graphs in the ℓ∞ • In Section 4, we extend our algorithmic framework to the more general class of intersection bipartite graphs. This extension yields also the first approximation algorithms for the WBC and GWBC problems on interval graphs and 𝑘-nearest-neighbor bipartite graphs. Moreover, we discuss how our techniques for the WBC and GWBC problems on 𝛿-disk graphs generalize to the ℓ𝛼𝑑 metric for any 𝛼 ≥ 1. In particular, we present a practical 𝑂 (𝜆 log 𝑛)approximation algorithm that applies to any ℓ𝛼𝑑 metric, where 𝜆 is the range cover size parameter defined in Subsection 4.2.1. • We implement our practical algorithm for 𝛿-disk graphs under 𝑑 and ℓ 𝑑 metrics, for both WBC and GWBC. In Section 5, both the ℓ∞ 2 we evaluate our methods on real-world datasets and show that they consistently outperform all baselines, producing (generalized) weighted biclique covers that are significantly smaller (often by up to a factor of four) while achieving comparable running times and substantially lower memory usage.

2

Hardness of GWBC

In Appendix B, we show a simpler proof that holds for any constant 𝑐 reducing from the dWBC problem. In this section we show a more involved proof that holds for any 𝑐 ≥ 0. It is known that covering the edges of a bipartite graph with the minimum number of bicliques (the bipartite dimension problem) is NP-complete [53]. Similarly, minimizing the total size of the bicliques in a cover (the

dWBC problem) is also NP-complete [60]. In this section, we show that dGWBC is NP-complete for any rational value 𝑐 ≥ 0. We use the reduction from Vertex Cover introduced in [60] for proving the hardness of dWBC. Let 𝐽 = (𝑊 , 𝐹 ) be an instance of Vertex Cover, where 𝑊 = {𝑤 1, . . . , 𝑤𝑛 }, |𝐹 | = 𝑚, together with an integer 𝐾. The goal is to decide whether 𝐽 admits a vertex cover of size at most 𝐾. We construct a bipartite graph 𝑮 = (𝑽, 𝑼 , 𝑬) as follows. For every vertex 𝑤𝑖 ∈ 𝑊 , we introduce two vertices 𝑥𝑖 , 𝑦𝑖 ∈ 𝑽 and one vertex 𝑧𝑖 ∈ 𝑼 , and add the edges (𝑥𝑖 , 𝑧𝑖 ), and (𝑦𝑖 , 𝑧𝑖 ). Thus, 𝑁 (𝑧𝑖 ) = {𝑥𝑖 , 𝑦𝑖 }. Next, for every edge 𝑒 = {𝑤𝑖 , 𝑤 𝑗 } ∈ 𝐹 , with 𝑖 < 𝑗, we introduce four new vertices 𝑝𝑒1, 𝑝𝑒2, 𝑝𝑒3, 𝑝𝑒4 ∈ 𝑽 and five new vertices 𝑢𝑒1, 𝑢𝑒2, 𝑢𝑒3, 𝑢𝑒4, 𝑢𝑒5 ∈ 𝑼 . Their neighborhoods are defined as follows: 𝑁 (𝑢𝑒1 ) = {𝑥𝑖 , 𝑝𝑒1, 𝑝𝑒2 }, 𝑁 (𝑢𝑒2 ) = {𝑦 𝑗 , 𝑝𝑒2, 𝑝𝑒3 }, 𝑁 (𝑢𝑒3 ) = {𝑦𝑖 , 𝑝𝑒3, 𝑝𝑒4 }, 𝑁 (𝑢𝑒4 ) = {𝑥 𝑗 , 𝑝𝑒4, 𝑝𝑒1 }, 𝑁 (𝑢𝑒5 ) = {𝑝𝑒1, 𝑝𝑒2, 𝑝𝑒3, 𝑝𝑒4 }. The vertices 𝑝𝑒1, . . . , 𝑝𝑒4 are private to the gadget corresponding to 𝑒, i.e., they do not occur in the gadget of any other edge of 𝐽 . This completes the construction of 𝑮. The above construction is exactly the bipartite graph used in the reduction of [60]. We next describe a useful normal form for biclique covers of 𝑮. Consider any biclique edge cover S of 𝑮. Without loss of generality, for every 𝑤𝑖 ∈ 𝑊 , the two edges incident to 𝑧𝑖 are covered in one of the following two ways: (1) one biclique contains 𝑧𝑖 together with both 𝑥𝑖 and 𝑦𝑖 ; or (2) two bicliques containing 𝑧𝑖 are used, one whose 𝑽 -side is {𝑥𝑖 } and one whose 𝑽 -side is {𝑦𝑖 }. Indeed, since 𝑁 (𝑧𝑖 ) = {𝑥𝑖 , 𝑦𝑖 }, any biclique containing 𝑧𝑖 has 𝑽 -side equal to {𝑥𝑖 }, {𝑦𝑖 }, or {𝑥𝑖 , 𝑦𝑖 }. Bicliques having the same singleton 𝑽 -side can be merged by taking the union of their 𝑼 sides. Such a merge does not increase either the total biclique size or the number of bicliques. Furthermore, suppose that the cover contains the biclique {𝑥𝑖 , 𝑦𝑖 }× {𝑧𝑖 } and also some biclique whose 𝑽 -side is {𝑥𝑖 }. We may add 𝑧𝑖 to the 𝑼 -side of the latter biclique and replace {𝑥𝑖 , 𝑦𝑖 } × {𝑧𝑖 } by {𝑦𝑖 } × {𝑧𝑖 }. This preserves all covered edges, does not change the number of bicliques, and does not increase their total size. The same argument applies if there exists a biclique whose 𝑽 -side is {𝑦𝑖 }. Thus, we may additionally assume that whenever the first case occurs, there is no other biclique in S whose 𝑽 -side is exactly {𝑥𝑖 } or exactly {𝑦𝑖 }. Since 𝑐 ≥ 0, all of these transformations do not increase 𝜎 (S) = 𝜇 (S) + 𝑐 |S|. We call 𝑤𝑖 selected if the second case occurs. The following observation gives the lower bounds on the number of bicliques that will be needed for the additional 𝑐 |S| term in the GWBC objective. All missing proofs in this section are shown in Appendix A. Lemma 2.1. Suppose that 𝑘 ′ vertices of 𝐽 are selected. Then the bicliques covering the vertex gadgets require at least 𝑛 + 𝑘 ′ bicliques. Moreover, every edge gadget requires at least four additional bicliques. If neither endpoint of an edge 𝑒 ∈ 𝐹 is selected, then its gadget requires at least five additional bicliques. These bounds can be summed over the edge gadgets. We also use the corresponding lower bounds on the total biclique size established by the reverse-direction analysis of the reduction

Aryan Esmailpour, Khoi Le, and Stavros Sintos

in [60]. In our terminology, if 𝑘 ′ vertices are selected, the vertex gadgets contribute at least 3(𝑛 − 𝑘 ′ ) + 4𝑘 ′ = 3𝑛 + 𝑘 ′ to the total biclique size. In addition, every edge gadget contributes at least 18, and an edge gadget whose two endpoints are both unselected contributes at least 20. These are incremental per-gadget bounds beyond the contribution of the vertex gadgets. For the dGWBC instance, we set the target value to 𝜏𝑐 = 3𝑛 + 𝐾 + 18𝑚 + 𝑐 (𝑛 + 𝐾 + 4𝑚) = 3𝑛 + 18𝑚 + 𝑐 (𝑛 + 4𝑚) + (1 + 𝑐)𝐾 . We next establish the correctness of the reduction. Lemma 2.2. The graph 𝐽 has a vertex cover of size at most 𝐾 if and only if the constructed graph 𝑮 admits a biclique edge cover S satisfying 𝜎 (S) ≤ 𝜏𝑐 . Finally, we conclude to the next theorem. Theorem 2.3. For any rational value 𝑐 ≥ 0, the dGWBC problem is NP-complete.

3

Approximation Algorithms

We design an approximation algorithm for the GWBC problem for 𝑑 metric, where 𝑑 = 𝑂 (1). any 𝑐 ≥ 0 in 𝛿-disk bipartite graphs in ℓ∞ Since our algorithm also works for 𝑐 = 0, it is also valid for the WBC 𝑑 metric a ball with center a point 𝑢 ∈ R𝑑 and problem. In the ℓ∞ radius 𝛿 is a box 𝜌𝑢 in R𝑑 with center 𝑢 and equal size side lengths 2𝛿. It is straightforward that if 𝑮 is a 𝛿-disk bipartite graph then for every 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 , (𝑣, 𝑢) ∈ 𝑬 if and only if 𝑣 ∈ 𝜌𝑢 . Throughout the section, we consider that 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 |, 𝑛 = 𝑛𝑉 + 𝑛𝑈 , 𝑚 = |𝑬 |, and without loss of generality 𝑛𝑉 ≤ 𝑛𝑈 . High level ideas. Before we proceed with the technical details we give the high level ideas of our algorithm. We first focus on WBC and then extend to GWBC. We start by reducing WBC to an instance of the weighted set cover problem. Each edge corresponds to an element, and each biclique to a set including its edges, with weight equal to the number of nodes in the biclique. We apply the classical greedy 𝑂 (log 𝑛) = 𝑂 (log 𝑛𝑈 )-approximation algorithm for weighted set cover, which also yields an 𝑂 (log 𝑛𝑈 )-approximation for WBC. Let Δ denote the set of uncovered edges at the beginning of an iteration of the greedy algorithm. The algorithm selects the ∗)| biclique 𝑆 ∗ that minimizes | E| D(𝑆(𝑆 ∗ )∩Δ| . However, a fundamental obstacle arises: the number of bicliques in a graph may be exponential in the number of nodes. As a result, a naive implementation of the greedy algorithm is computationally expensive. A key observation is that the greedy algorithm does not require selecting the optimal biclique in each iteration. It suffices to find a ∗)| )| biclique 𝑆 such that | E| D(𝑆(𝑆)∩Δ| ≤ 𝛾ˆ · | E| D(𝑆(𝑆 ∗ )∩Δ| . In this case, the greedy algorithm yields an 𝑂 (𝛾ˆ · log 𝑛𝑈 )-approximation. A natural first attempt is to compute a densest subgraph of 𝐺 restricted to uncovered edges. The densest subgraph problem finds a subgraph that maximizes the ratio of the number of edges over the number of nodes in polynomial time [33]. Although this objective matches the greedy criterion for our algorithm, the resulting subgraph is not necessarily a biclique. To address this, we exploit the geometric structure of 𝛿-disk graphs using a range tree [25] built over 𝑽 . A range tree creates 𝑂 (𝑛𝑉 log𝑑 −1 𝑛𝑉 ) hyper-rectangles C, such that for any hyper-rectangle 𝜌 in R𝑑 there are always

𝑂 (log𝑑 𝑛𝑉 ) pairwise disjoint hyper-rectangles in C that contains exactly the points in 𝜌 ∩ 𝑽 . Using this property we show that there should exist a hyperrectangle 𝑥 ∈ C and a subgraph 𝐺𝑥 (𝑉𝑥 , 𝑈𝑥 , 𝐸𝑥 ) such that i) 𝑉𝑥 ⊆ 𝑽 , ii) 𝑈𝑥 is the set of points in 𝑼 within distance 𝛿 from all points in 𝑉𝑥 , iii) 𝐸𝑥 is the set of uncovered edges between 𝑉𝑥 and 𝑈𝑥 , and iv) 1 the densest subgraph of 𝐺𝑥 contains at least · |E (𝑆 ∗ ) ∩ Δ| 𝑂 (log𝑑 𝑛𝑉 ) edges. Using these observations, we show that the procedure of iterating over all 𝑥 ∈ C and computing the densest subgraph in 𝐺𝑥 will lead to an 𝑂 (log(𝑛𝑈 ) log𝑑 (𝑛𝑉 ))-approximation algorithm for the WBC problem in polynomial time. For the GWBC problem, we proceed in a similar manner. As before, we reduce GWBC to an instance of the weighted set cover problem; however, in this case, the weight of each biclique (set) is defined as the number of its vertices plus the parameter 𝑐. Due to the presence of the parameter 𝑐, the classical densest subgraph formulation is no longer appropriate. Instead, we introduce the 𝑐-densest subgraph problem, in which, given a graph, the objective is to find a subgraph that minimizes the ratio of the number of vertices plus 𝑐 to the number of edges. We show how known results in graph theory yield efficient exact or approximate solutions for the 𝑐-densest subgraph problem.

3.1

Expensive approx. algorithm for GWBC

Given a bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬), we map GWBC to the wellknown weighted set cover problem. In the weighted set cover problem we are given a universe A of 𝑁 items and a family of subsets 𝑻 = {𝑇1, . . . ,𝑇𝑀 } of A such that each subset 𝑇𝑖 is associated with a weight 𝑤𝑖 ≥ 0. The goal is to select a family of sets 𝑇 ′ ⊆ 𝑻 such that every element 𝑎 ∈ A is covered by at least one set in 𝑇 ′ and Í 𝑇𝑖 ∈𝑇 ′ 𝑤 𝑖 is minimized. It is known that a greedy algorithm that in 𝑖 each iteration selects the set 𝑇𝑖 with the smallest ratio 𝑤 𝑏𝑖 , where 𝑏𝑖 is the number of uncovered items in A contained in 𝑇𝑖 , is an 𝑂 (log 𝑁 )-approximation for the weighted set cover problem [21]. We can straightforwardly map our problem to an instance of the weighted set cover problem. The universe is defined as A = 𝑬, i.e., all edges we must cover. For every biclique 𝑆 in 𝑮 we construct a set 𝑇𝑆 = E (𝑆) with weight 𝑤 𝑆 = 𝑐 + |D (𝑆)|. For every set cover in the set system (A, 𝑻 ) of weight 𝑊 there exists a biclique cover S in 𝑮 with cost 𝜎 (S) = 𝑊 , and vice versa. Thus, the greedy algorithm that 𝑆 chooses in each iteration the biclique 𝑆 that minimizes 𝑤 𝑏𝑆 , where 𝑏𝑆 is the number of uncovered edges in E (𝑆), returns an 𝑂 (log 𝑛𝑈 )approximation for the GWBC problem. Even more generally, any algorithm that chooses in each iteration a biclique 𝑆 such that 𝑤𝑆 ′ 𝑤𝑆 ′ 𝑏𝑆 ≤ 𝛾ˆ · min𝑆 𝑏𝑆 ′ , returns an 𝑂 (𝛾ˆ · log 𝑛𝑈 )-approximation for the GWBC problem. In the next section, for 𝛿-disk bipartite graphs we show how we can compute in polynomial time an 𝑂 (log𝑑 𝑛𝑉 )approximation of the biclique with the minimum ratio of weight over number of newly covered elements.

3.2

Fast approx. algorithm for GWBC

Before describing our algorithm, we first introduce two technical tools that are central to our approach. 3.2.1 Range tree [25]. A range tree is a tree-based geometric data structure that is used for range aggregation queries in R𝑑 , where 𝑑 = 𝑂 (1). While a range tree has various interesting properties, we only mention the main property that we need for our algorithm. Let

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

𝑃 be a set of points in R𝑑 and let T be the range tree constructed over 𝑃. The range tree T constructs a set C of 𝑂 (|𝑃 | · log𝑑 −1 (|𝑃 |)) canonical axis-aligned hyper-rectangles in R𝑑 . Let 𝜌 be any hyperrectangle in R𝑑 . We know that there exists a subset of 𝑂 (log𝑑 |𝑃 |) Ð pairwise disjoint hyper-rectangles 𝐶 (𝜌) ⊆ C such that 𝑥 ∈𝐶 (𝜌 ) (𝑃 ∩ 𝑥) = 𝑃 ∩ 𝜌. For every 𝑥 ∈ C let 𝑥¯ be the minimum volume axisaligned hyper-rectangle such that 𝑥 ∩ 𝑃 = 𝑥¯ ∩ 𝑃. Without loss of ¯ generality, we assume every 𝑥 in C is minimal, i.e., 𝑥 = 𝑥. 3.2.2 𝑐-densest subgraph. Given a bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬), the problem of computing the densest subgraph asks to compute a E (𝑋 ) | subgraph 𝑋 ⊆ 𝑮 such that ||D (𝑋 ) | is maximized. Two common techniques to solve the densest subgraph problem are the max-flow based algorithm [33], and an LP-based algorithm [15]. There exists also a greedy 2-approximation algorithm that runs in time linear to the size of the input graph [15]. For the GWBC problem we are interested in a variation of the densest subgraph problem that we call 𝑐-densest subgraph problem. Given a bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) and a rational number 𝑐 ≥ 0, the goal is compute a subgraph 𝑋 ⊆ 𝑮 | such that | D| E(𝑋(𝑋) )|+𝑐 is maximized. We defer to Appendix C.1 the details of how the known exact max-flow–based algorithm for the standard densest subgraph problem can be extended to obtain an exact polynomial-time algorithm for the 𝑐-densest subgraph problem. For our purposes even a 𝑂 (1)approximation algorithm for the 𝑐-densest subgraph problem is sufficient. As shown in Appendix C.1, Chekuri et al. [18] gives an 𝑂 (1)-approximation for the 𝑐-densest subgraph problem in linear time. Putting everything together, we get the next result. Lemma 3.1. Given a bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) and a rational number 𝑐 ≥ 0, there exists an exact algorithm for the 𝑐-densest subgraph problem that runs in 𝑂 ((|𝑽 | + |𝑼 |) · |𝑬 | · log(max{|𝑽 |, |𝑼 |, 𝑐})) time. There also exists an 𝑂 (1)-approximation algorithm with running time 𝑂 (|𝑽 | + |𝑼 | + |𝑬 |). Let DenSub(𝑮, 𝑐) denote the procedure that returns an 𝑂 (1)approximation of the 𝑐-densest subgraph problem on a bipartite graph 𝑮. 3.2.3 Approximation algorithm. As we mentioned in Subsection 3.1 we will implement an approximate version of the greedy algorithm, where in each iteration 𝑖 it computes a biclique 𝑆𝑖 such that 𝑤𝑆𝑖 𝑏𝑆𝑖

𝑤𝑆 ′

≤ 𝑂 (log𝑑 𝑛𝑉 ) min𝑆𝑖′ 𝑏 ′𝑖 , where 𝑤 𝑆𝑖 = |D (𝑆𝑖 )| +𝑐 and 𝑏𝑆𝑖 is the 𝑆𝑖

number of edges in E (𝑆𝑖 ) that have not been covered by bicliques already selected in the previous iterations. We initialize a hash table 𝐵 such that for each edge (𝑣, 𝑢) ∈ 𝑬, we set 𝐵(𝑣, 𝑢) = 1 if (𝑣, 𝑢) is not yet covered by the current biclique cover S, and 𝐵(𝑣, 𝑢) = 0 otherwise. We also construct a range tree T over 𝑽 and let C be the set of its canonical hyper-rectangles. Next, consider any iteration of the greedy algorithm, where S contains the currently selected bicliques and hash-table 𝐵 is up to date. For example, consider the beginning of the 𝑖-th iteration where S = {𝑆 1, . . . , 𝑆𝑖 −1 }. We go through every canonical hyperrectangle 𝑥 ∈ C. We construct the bipartite graph 𝐺𝑥 (𝑉𝑥 , 𝑈𝑥 , 𝐸𝑥 ) where 𝑉𝑥 = 𝑽 ∩ 𝑥, 𝑈𝑥 = {𝑢 ∈ 𝑼 | 𝑥 ⊆ 𝜌𝑢 }, and 𝐸𝑥 = {(𝑣, 𝑢) ∈ 𝑬 | 𝑣 ∈ 𝑉𝑥 , 𝑢 ∈ 𝑈𝑥 , 𝐵(𝑣, 𝑢) = 1}. Recall that 𝜌𝑢 is a box in R𝑑 with center 𝑢 and equal side lengths 2𝛿. In other words, we create the bipartite graph that contains all vertices from 𝑽 in 𝑥, all vertices from 𝑼 whose boxes completely cover 𝑥 and all uncovered edges

Algorithm 1: RT-BC 𝑑 , and 𝑐 ≥ 0 Input: A 𝛿-disk bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) in ℓ∞ Output: A biclique edge cover S of 𝑮 1 S ← ∅, 𝑖 = 1; 2 Initialize hash table 𝐵 with 𝐵(𝑣, 𝑢) ← 1 for every (𝑣, 𝑢) ∈ 𝑬; 3 Build T on 𝑽 and let C be its canonical hyper-rectangles; 4 while there exists (𝑣, 𝑢) ∈ 𝑬 with 𝐵(𝑣, 𝑢) = 1 do 5 𝜙 ∗ ← +∞, 𝑆 ′ ← ∅; 6 foreach 𝑥 ∈ C do 7 𝑉𝑥 ← 𝑽 ∩ 𝑥, 𝑈𝑥 ← {𝑢 ∈ 𝑼 | 𝑥 ⊆ 𝜌𝑢 }; 8 𝐸𝑥 ← {(𝑣, 𝑢) ∈ 𝑬 | 𝑣 ∈ 𝑉𝑥 , 𝑢 ∈ 𝑈𝑥 , 𝐵(𝑣, 𝑢) = 1}; 9 Construct 𝐺𝑥 (𝑉𝑥 , 𝑈𝑥 , 𝐸𝑥 ); 10 𝑆 (𝑥 ) ← DenSub(𝐺𝑥 , 𝑐), 𝑏𝑥 ← |𝐸 (𝑆 (𝑥 ) )|; 11 if 𝑏𝑥 = 0 then continue; (𝑥 ) 12 𝜙ˆ ← | D (𝑆 ) |+𝑐 ; 𝑏𝑥

13 14 15 16 17 18 19

ˆ if 𝜙ˆ < 𝜙 ∗ then 𝜙 ∗ ← 𝜙,

𝑆 ′ ← 𝑆 (𝑥 ) ;

Define biclique 𝑆𝑖 induced by D (𝑆 ′ ); foreach 𝑣 ∈ V (𝑆𝑖 ), 𝑢 ∈ U (𝑆𝑖 ) do 𝐵(𝑣, 𝑢) ← 0; S ← S ∪ {𝑆𝑖 }; 𝑖 ← 𝑖 + 1; return S;

between these vertices. We call DenSub(𝐺𝑥 , 𝑐) and let 𝑆 (𝑥 ) be the (𝑥 ) ) |+𝑐 returned subgraph of 𝐺𝑥 . We set 𝑥𝑖 = arg min𝑥 ∈ C | D (𝑆 , and 𝑏 𝑆 (𝑥 )

let 𝑆𝑖 be the biclique such that D (𝑆𝑖 ) = D (𝑆 (𝑥𝑖 ) ) and E (𝑆𝑖 ) consists of all edges in 𝑬 between V (𝑆 (𝑥𝑖 ) ) and U (𝑆 (𝑥𝑖 ) ). As we show in the correctness proof, 𝑆𝑖 is a valid biclique of 𝑮. For every 𝑣 ∈ V (𝑆𝑖 ) and 𝑢 ∈ U (𝑆𝑖 ) we set 𝐵(𝑣, 𝑢) = 0. We add 𝑆𝑖 in S and continue with the next iteration of the greedy algorithm. The greedy algorithm terminates when all edges are covered, i.e., 𝐵(𝑣 ′, 𝑢 ′ ) = 0 for every edge (𝑣 ′, 𝑢 ′ ) ∈ 𝑬. We present the pseudocode of our algorithm in Algorithm 1. Correctness and analysis. Recall that without loss of generality we consider that 𝑛𝑉 ≤ 𝑛𝑈 . Lemma 3.2. 𝜎 (S) ≤ 𝑂 (log(𝑛𝑈 ) log𝑑 (𝑛𝑉 ))𝜎 (S ∗ ), where S ∗ is the biclique edge cover that minimizes 𝜎 (S ∗ ). Proof. From Subsection 3.1 it is sufficient to show that in each it𝑖 ) |+𝑐 eration 𝑖 of our algorithm we select a biclique 𝑆𝑖 such that | D (𝑆 ≤ 𝑏𝑆𝑖 ∗ Ð | D (𝑆𝑖 ) |+𝑐 𝑑 𝑂 (log 𝑛𝑉 ) 𝑏 ∗ , where 𝑏𝑆𝑖 = |E (𝑆𝑖 ) \ ( 𝑗 ∈ [𝑖 −1] E (𝑆 𝑗 ))| and 𝑆𝑖

∗

| D (𝑆 ) |+𝑐 𝑆𝑖∗ is the biclique that minimizes 𝑏 𝑖∗ . 𝑆 𝑖

First, it is straightforward to see that 𝑆𝑖 is a valid biclique in 𝑮. In fact, for every 𝑥 ∈ C if 𝑣 ∈ V (𝑆 (𝑥 ) ) and 𝑢 ∈ U (𝑆 (𝑥 ) ), it holds that (𝑣, 𝑢) ∈ 𝑬. Indeed, notice that by the construction of 𝑉𝑥 and 𝑈𝑥 , for every 𝑣 ∈ 𝑉𝑥 and 𝑢 ∈ 𝑈𝑥 , 𝜓 (𝑣, 𝑢) ≤ 𝛿. Hence for every vertex 𝑣 in the subset of 𝑉𝑥 that is selected in 𝑆 (𝑥 ) and every vertex 𝑢 in the subset of 𝑈𝑥 that is selected in 𝑆 (𝑥 ) it holds that (𝑣, 𝑢) ∈ 𝑬.

Aryan Esmailpour, Khoi Le, and Stavros Sintos

Ñ We note that 𝑦 = 𝑢 ∈ U (𝑆 ∗ ) 𝜌𝑢 is a hyper-rectangle in R𝑑 and 𝑖 since 𝑆𝑖∗ is a biclique it holds that V (𝑆𝑖∗ ) ⊆ 𝑦. From the definition of a range tree, let 𝐶 (𝑦) be the set of 𝑂 (log𝑑 𝑛𝑉 ) canonical hyper-rectangles of T that cover all points in V (𝑆𝑖∗ ). For every hyper-rectangle 𝑧 ∈ 𝐶 (𝑦) let 𝜉𝑧 = |((V (𝑆𝑖∗ ) ∩ 𝑧) × U (𝑆𝑖∗ )) \ Ð ( 𝑗 ∈ [𝑖 −1] E (𝑆 𝑗 ))|, i.e., the number of uncovered edges among vertices of V (𝑆𝑖∗ ) in 𝑧 and vertices of U (𝑆𝑖∗ ). By definition notice that Í 𝑏𝑆𝑖∗ = 𝑧 ∈𝐶 (𝑦) 𝜉𝑧 . Let 𝑧 ′ be the canonical hyper-rectangle in 𝐶 (𝑦) 𝑑

such that 𝜉𝑧 ′ = max𝑧 ∈𝐶 (𝑦) 𝜉𝑧 . Since there are 𝑂 (log 𝑛𝑉 ) canonical hyper-rectangles in 𝐶 (𝑦), we have that 𝜉𝑧 ′ ≥ more, |V (𝑆𝑖∗ ) ∩ 𝑧 ′ | ≤ |V (𝑆𝑖∗ )|. Hence, |V (𝑆𝑖∗ ) ∩ 𝑧 ′ | + |U (𝑆𝑖∗ )| + 𝑐 𝜉𝑧 ′

𝑏𝑆 ∗ 𝑖 𝑂 (log𝑑 𝑛𝑉 )

. Further-

(1)

Next, notice that 𝑧 ′ is a canonical hyper-rectangle in C that our ′ algorithm visits and computes the subgraph 𝑆 (𝑧 ) . By definition, ′

|D (𝑆𝑖 )| + 𝑐 |D (𝑆 (𝑧 ) )| + 𝑐 . ≤ 𝑏 𝑆𝑖 𝑏𝑆 (𝑧 ′ )

(2)

Finally, notice that 𝑉𝑧 ′ ⊇ V (𝑆𝑖∗ ) ∩ 𝑧 ′ , 𝑈𝑧 ′ ⊇ U (𝑆𝑖∗ ) and by construction, 𝐸𝑧 ′ contains all uncovered edges between the vertices in 𝑉𝑧 ′ and 𝑈𝑧 ′ . The procedure DenSub(𝐺𝑧 ′ , 𝑐) computes the subgraph ′

| E𝐺 ′ (𝑆 (𝑧 ) ) |

𝑧 𝑆 (𝑧 ) ⊆ 𝐺𝑧 ′ that approximately maximizes the ratio | D (𝑆 (𝑧 ′ ) ) |+𝑐 , ′

up to a constant factor, where E𝐺𝑧 ′ (𝑆 (𝑧 ) ) are the edges in 𝐸𝑧 ′ be′ ′ tween nodes in V (𝑆 (𝑧 ) ) and U (𝑆 (𝑧 ) ). By definition every edge in 𝐸𝑧 ′ is an uncovered edge of 𝑬, so equivalently DenSub(𝐺𝑧 ′ , 𝑐) ′ computes the subgraph 𝑆 (𝑧 ) ⊆ 𝐺𝑧 ′ that approximately minimizes ′

| D (𝑆 (𝑧 ) ) |+𝑐 ′ | E𝐺 ′ (𝑆 (𝑧 ) ) |

= | D (𝑆 𝑏

(𝑧 ′ ) ) |+𝑐

′ 𝑆 (𝑧 )

𝑧

, up to a constant multiplicative factor.

Hence, by the near-optimality of DenSub(𝐺𝑧 ′ , 𝑐) we have that ′

|V (𝑆𝑖∗ ) ∩ 𝑧 ′ | + |U (𝑆𝑖∗ )| + 𝑐 |D (𝑆 (𝑧 ) )| + 𝑐 ≤ 𝑂 (1) · . 𝑏𝑆 (𝑧 ′ ) 𝜉𝑧 ′

4

(3)

Extensions

We show how the algorithm from Subsection 3.2.3 can be extended to intersection bipartite graphs. We also describe how to adapt the algorithm to 𝛿-disk bipartite graphs in ℓ𝛼𝑑 for 𝛼 ≥ 1.

4.1

|D (𝑆𝑖∗ )| + 𝑐 ≤ 𝑂 (log 𝑛𝑉 ) . 𝑏𝑆𝑖∗ 𝑑

′

𝑑, Theorem 3.4. Given a 𝛿-disk bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) in ℓ∞ where 𝑑 = 𝑂 (1), such that 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 | (and without loss of generality 𝑛𝑉 ≤ 𝑛𝑈 ), and |𝑬 | = 𝑚, there exists an 𝑂 (log(𝑛𝑈 ) · log𝑑 (𝑛𝑉 ))-approximation algorithm for the GWBC (and WBC) problem for any 𝑐 ≥ 0, that runs in 𝑂 (𝑛𝑉 · (𝑛𝑈 + 𝑚) · 𝑚 · log𝑑 −1 (𝑛𝑉 )) time and uses 𝑂 (𝑛𝑈 + 𝑚 + 𝑛𝑉 log𝑑 −1 𝑛𝑉 ) space.

Intersection bipartite graphs

Let 𝑮 (𝑽, 𝑼 , 𝑬, R𝑉 , R𝑈 ) be an intersection bipartite graph. Our algorithm is an extension of the algorithm in Section 3.2.3. The high level idea is that for each hyper-rectangle 𝑟 𝑣 ∈ R𝑉 we construct a point 𝑝 𝑣 in R2𝑑 and for each 𝑟𝑢 ∈ R𝑈 a hyper-rectangle 𝜌ˆ𝑢 in R2𝑑 , such that 𝑟 𝑣 ∩ 𝑟𝑢 ≠ ∅ if and only if 𝑝 𝑣 ∈ 𝜌ˆ𝑢 . A hyperrectangle 𝑟 in R𝑑 is defined as 𝑟 = [𝑟 (1) − , 𝑟 (1)+ ] × . . . × [𝑟 (𝑑 ) − , 𝑟 (𝑑 )+ ], where [𝑟 ( 𝑗 ) − , 𝑟 ( 𝑗 )+ ] is the interval of 𝑟 in 𝑗-th dimension. For every 𝑣 ∈ 𝑉 let 𝑝 𝑣 be the point in R2𝑑 defined by the corners of 𝑟 𝑣 : 𝑝 𝑣 = (𝑟 𝑣(1) −, . . . , 𝑟 𝑣(𝑑 ) −, 𝑟 𝑣(1)+, . . . , 𝑟 𝑣(𝑑 )+ ). Let 𝑃 = {𝑝 𝑣 | 𝑣 ∈ 𝑽 } and let T be the range tree constructed on 𝑃. For every 𝑟𝑢 ∈ R𝑈 , we construct a hyper-rectangle 𝜌ˆ𝑢 = (−∞, 𝑟𝑢(1)+ ] × (−∞, 𝑟𝑢(2)+ ] × . . . × (−∞, 𝑟𝑢(𝑑 )+ ] × [𝑟𝑢(1) − , ∞) × [𝑟𝑢(2) − , ∞) × . . . × [𝑟𝑢(𝑑 ) − , ∞). For every 𝑥 ∈ C, we define 𝑉𝑥 = {𝑣 ∈ 𝑽 | 𝑝 𝑣 ∈ 𝑥 }, and 𝑈𝑥 = {𝑢 ∈ 𝑼 | 𝑥 ⊆ 𝜌ˆ𝑢 }. All the other steps of the algorithm follow verbatim. The correctness of the method and extensions to interval and 𝑘-NN bipartite graphs are given in Appendix D.1. Theorem 4.1. Given an intersection bipartite graph 𝑮 (𝑽,𝑼,𝑬, R𝑉,R𝑈 ) in R𝑑 , where 𝑑 = 𝑂 (1), such that 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 | (and without loss of generality 𝑛𝑉 ≤ 𝑛𝑈 ), and |𝑬 | = 𝑚, there exists an 𝑂 (log(𝑛𝑈 ) · log2𝑑 (𝑛𝑉 ))-approximation algorithm for the GWBC (and WBC) problem for any 𝑐 ≥ 0, that runs in 𝑂 (𝑛𝑉 · (𝑛𝑈 + 𝑚) · 𝑚 · log2𝑑 −1 (𝑛𝑉 )) time and uses 𝑂 (𝑛𝑈 + 𝑚 + 𝑛𝑉 log2𝑑 −1 𝑛𝑉 ) space.

From Equations (1), (2), and (3), we get |D (𝑆𝑖∗ )| + 𝑐 |D (𝑆𝑖 )| + 𝑐 . ≤ 𝑂 (log𝑑 𝑛𝑉 ) · 𝑏 𝑆𝑖 𝑏𝑆𝑖∗ □ Lemma 3.3. Our algorithm runs in 𝑂 (𝑛𝑉 ·(𝑛𝑈 +𝑚)·𝑚·log𝑑 −1 (𝑛𝑉 )) time and uses 𝑂 (𝑛𝑈 + 𝑚 + 𝑛𝑉 · log𝑑 −1 𝑛𝑉 ) space. Proof. The range tree T is constructed in 𝑂 (𝑛𝑉 log𝑑 −1 𝑛𝑉 ) and there are 𝑂 (𝑛𝑉 log𝑑 −1 𝑛𝑉 ) canonical hyper-rectangles. For each 𝑥 ∈ C we create the graph 𝐺𝑥 in 𝑂 (𝑛𝑉 +𝑛𝑈 +𝑚) time and the procedure DenSub(𝐺𝑥 , 𝑐) is executed in 𝑂 (𝑛𝑈 + 𝑚) time (Lemma 3.1). Hence each iteration of our greedy algorithm runs in 𝑂 (𝑛𝑉 · (𝑛𝑈 + 𝑚) · log𝑑 −1 (𝑛𝑉 )) time. In each iteration of the greedy algorithm at least one new edge is covered so the overall time of our algorithm is bounded by 𝑂 (𝑛𝑉 · (𝑛𝑈 +𝑚) ·𝑚 · log𝑑 −1 (𝑛𝑉 )). Finally, our algorithm constructs the range tree T with space 𝑂 (𝑛𝑉 log𝑑 −1 𝑛𝑉 ). All the other steps of the algorithm including the algorithm for the 𝑐densest subgraph problem (Lemma 3.1) use linear space with respect to the size of the graph 𝑮. □ Putting everything together we conclude to Theorem 3.4.

4.2 𝛿-disk graph for any ℓ𝛼𝑑 We next discuss how the algorithm from Theorem 3.4 extends to ℓ𝛼𝑑 𝑑 metric, an edge (𝑣, 𝑢) ∈ 𝑬 exists if and only if for any 𝛼 ≥ 1. In the ℓ∞ 𝑣 lies in an axis-aligned box 𝜌𝑢 of side length 2𝛿 centered at 𝑢. More generally, for any 𝛼, we define the ball ⃝𝑢 = {𝑝 ∈ R𝑑 | 𝜓𝛼 (𝑢, 𝑝) ≤ 𝛿 }, and observe that (𝑣, 𝑢) ∈ 𝑬 if and only if 𝑣 ∈ ⃝𝑢 . The correctness of our algorithm relies on range trees, which decompose any hyperrectangle into 𝑂 (log𝑑 𝑛𝑉 ) canonical regions. However, for 𝛼 ≠ ∞, the region ⃝𝑢 is not a hyper-rectangle, and therefore range trees cannot be applied. We show two approaches for handling metrics ℓ𝛼𝑑 for any 𝛼 ≥ 1. The first is a theoretical approach based on the notion of 𝜀-bicliques that are graph structures that approximate standard bicliques. We present the theoretical approach in Appendix D.2. The second is a practical approach, which we also employ in our experimental evaluation. 4.2.1 Practical approach. The theoretical approach constructs an 𝜀-biclique edge cover rather than an exact biclique cover and relies on an advanced geometric data structure (BBD tree). In practice, however, when our goal is to compute a biclique edge cover for general metrics ℓ𝛼𝑑 with 𝛼 ≥ 1, we instead employ an 𝑅-tree [38] or a k-d

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

tree [10]. The 𝑅-tree and k-d tree are the most widely used geometric data structures for range aggregation queries, where the query range can be any convex region. The 𝑅-tree (or k-d tree) constructed over 𝑽 induces a collection C of 𝑂 (|𝑽 |) canonical axis-aligned hyper-rectangles in R𝑑 . For any convex region 𝜌 ⊆ R𝑑 , there exists a subset 𝐶 (𝜌) ⊆ C of 𝜆 pairwise disjoint hyper-rectangles such that Ð 𝑥 ∈𝐶 (𝜌 ) (𝑽 ∩ 𝑥) = 𝑽 ∩ 𝜌. While for range trees and BBD-trees the parameter 𝜆 is provably bounded, in the case of 𝑅-trees it can be as large as 𝑂 (𝑛𝑉 ) in the worst case. Nevertheless, in practice 𝜆 is typically much smaller and is often observed to be 𝑂 (log 𝑛𝑉 ). We refer to 𝜆 as the range cover size. For any given 𝛼 ≥ 1, we construct an 𝑅-tree or k-d tree over 𝑽 and execute the algorithm from Subsection 3.2.3, iterating over the canonical hyper-rectangles of the 𝑅-tree (resp. k-d tree) instead of those of the range tree. Using the same analysis, but assuming a range cover size of 𝜆 instead of 𝑂 (log𝑑 𝑛𝑉 ), we obtain the following result. Theorem 4.2. Given a 𝛿-disk bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) in ℓ𝛼𝑑 , where 𝛼 ≥ 1 and 𝑑 = 𝑂 (1), such that 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 |, and |𝑬 | = 𝑚, there exists an 𝑂 (𝜆 · log(𝑛𝑈 ))-approximation algorithm for the GWBC (and WBC) problem for any 𝑐 ≥ 0, where 𝜆 is the range cover size, that runs in 𝑂 (𝑛𝑉 · (𝑛𝑈 + 𝑚) · 𝑚) time and uses 𝑂 (𝑛𝑈 + 𝑛𝑉 + 𝑚) space. Remark 1. Due to its practicality in all our experiments we use the algorithm from Theorem 4.2. Remark 2. The running times stated in our theorems are loose worst-case upper bounds. In practice, performance is significantly better. Specifically, each greedy iteration typically covers many edges (rather than a single edge), the edges in 𝐺𝑥 are much smaller than 𝑚, and only a small subset of canonical hyper-rectangles needs to be examined per iteration. If the greedy algorithm runs for 𝜅 1 iterations, each 𝐺𝑥 contains at most 𝜅 2 edges, and at most 𝜅 3 hyperrectangles are visited per iteration, a more realistic running time is 𝑂 (𝜅 3 (𝑛𝑈 + 𝜅 2 )𝜅 1 ).

5

Experiments

In this section, we implement the practical algorithm from Theorem 4.2 and compare its effectiveness and efficiency against standard baseline methods for WBC and GWBC on both real and semisynthetic datasets. Specifically, for each algorithm we evaluate the following metrics: (i) the total size of the returned biclique edge cover, (ii) the maximum memory consumption, and (iii) the running time required to compute a biclique edge cover. All datasets and our code can be found in [27].

5.1

Datasets

We evaluate our algorithms on three real geometric datasets Adults [9], Default of Credit Card Clients [65], MAGIC Gamma Telescope [11], two real bipartite graphs MovieLens100K [35], MovieLens1M [36], two matrix datasets WorldCities, 162bit from [23] corresponding to real bipartite graphs, and one semi-synthetic dataset POPSIM [51]. In the datasets Adults, Credit, Gamma, and POPSIM, each data point lies in R𝑑 and is associated with a categorical attribute. In all cases, we normalize the coordinates so that they lie in the range [0, 1]. We select a categorical attribute to partition the input points into two disjoint sets, 𝑽 and 𝑼 , thereby defining the bipartition. We

consider five values of 𝛿 and construct the corresponding 𝛿-disk bipartite graphs. For a fixed value of 𝛿, a vertex 𝑣 ∈ 𝑽 and a vertex 𝑢 ∈ 𝑼 are connected by an edge if 𝜓𝛼 (𝑣, 𝑢) ≤ 𝛿. In our experiments, 𝑑 metric space (𝛼 = {2, ∞}). For POPSIM, we we use the ℓ2𝑑 and ℓ∞ construct two additional geometric bipartite graphs: a large and very sparse graph, called POPSIM-S, in which the average degree is 3.5, and a large and very dense graph, called POPSIM-D, in which the average degree is greater than 325. We show all statistics of our datasets in Table 1. While Adults, Credit, Gamma, and POPSIM datasets are inherently geometric, this is not the case for the real bipartite graphs MovieLens100K and MovieLens1M. In these datasets, one side of the bipartite graph corresponds to users, the other to movies, and edges represent user ratings. Similarly, the bipartite graphs derived by the matrix datasets WorldCities and 162bit are not geometric. However, our algorithm RT-BC operates on geometric bipartite graphs. Therefore, we embed the original bipartite graphs into a geometric space while attempting to preserve their edge structure with minimal distortion. More specifically, given a bipartite graph 𝐺 (𝑈 , 𝑉 , 𝐸), we construct an embedding 𝐺 ′ in R𝑑 , for a sufficiently large dimension 𝑑, such that every 𝑢 ∈ 𝑈 and 𝑣 ∈ 𝑉 is mapped to points 𝑝𝑢 , 𝑝 𝑣 ∈ R𝑑 , and edges are induced by a distance threshold, i.e., (𝑢, 𝑣) ∈ 𝐸 ⇐⇒ 𝜓𝛼 (𝑝𝑢 , 𝑝 𝑣 ) ≤ 𝑟 . Our objective is to ensure that 𝐺 ′ approximates 𝐺 as closely as possible, so that the experimental evaluation reflects the performance of RT-BC rather than artifacts introduced by the embedding process. In practice, we fix 𝛼 = 2 (Euclidean distance) and 𝑟 = 1, and optimize over the embedding coordinates in dimension 𝑑 using a gradient-based optimization procedure. We enforce that all original edges of 𝐺 are preserved in 𝐺 ′ , while minimizing the number of additional induced edges, ideally introducing none. Our approach is inspired by the geometric graph embedding framework of [47]. For both MovieLens100K and MovieLens1M, we construct embeddings in R256 that are highly accurate, introducing only at most 18 additional edges overall. For WorldCities and 162bit, we construct embeddings in R256 introducing no additional edges. We report summary statistics (including the number of vertices, number of edges, dimensionality, and grouping attribute) for all datasets (for 𝛼 = 2) and all values of 𝛿 in Table 1. We also show the statistics for 𝛼 = ∞ in Table 3.

5.2

Algorithms

We describe the algorithms compared in our experiments. Our algorithm: RT-BC. We implemented our practical algorithm (with provable guarantees) from Theorem 4.2. To generate the canonical hyper-rectangles we use a modified implementation of SciPy’s KDTree. For the WBC problem, we use Charikar’s 2approximation algorithm [15] to compute the densest subgraph, as implemented in [3]. For the GWBC problem, we modified the implementation of the exact algorithm [33] for the densest subgraph problem, as shown in Section 3 to solve the 𝑐-densest subgraph. Baselines. For each WBC and GWBC problem, we compare our approach against three baselines. The first two baselines share the same high level approach: They are greedy algorithms and run in two phases. In the first phase they generate a candidate set of bicliques. In the second phase they run a greedy algorithm to

Aryan Esmailpour, Khoi Le, and Stavros Sintos

Dataset

𝛿 𝑚 𝑛 𝑑 Group Attribute 0.05 47,963 0.1 445,724 0.15 1,415,555 Adults 14,846 5 Sex 0.2 3,016,343 0.25 5,498,540 0.002 889,671 0.003 1,739,709 0.004 2,710,136 Credit 28,726 6 Sex 0.005 3,750,745 0.006 4,824,359 0.13 194,737 0.14 284,626 0.15 399,339 Gamma 18,905 10 Class 0.16 541,050 0.17 711,158 0.04 1,468,984 0.06 2,660,732 0.08 3,801,451 POPSIM 8,591 2 Race 0.1 4,857,704 0.12 5,844,122 POPSIM-S 5,625,395 3,211,965 2 Race POPSIM-D 122,880,782 755,182 2 Race MovieLens100K 100,000 2,700 256 MovieLens1M 1,000,000 10,000 256 WorldCities 7,518 415 256 162bit 37,118 7,203 256 -

Table 1: Statistics of 𝛿-disk graphs in our experiments for ℓ2𝑑 . compute a biclique edge cover using the selected candidate bicliques. The third baseline is the CPGR algorithm from [16]. • Role: This is a heuristic for the edge-RMP problem in rolemining [48, 60], which is equivalent to WBC for bipartite graphs. It uses the RoleMiner algorithm [61] to generate a candidate set of bicliques. • AMBEA: It constructs a candidate set of bicliques by enumerating all maximal bicliques using AMBEA [55]. • CPGR: This is the state-of-the-art algorithm for constructing a biclique partition, as implemented in [16]. Details of Role and AMBEA. Following candidate generation, the first two baselines employ the same greedy selection criteria. For the WBC problem, the greedy procedure chooses in each iteration the biclique that minimizes the ratio of the number of nodes over the number of uncovered edges. For the GWBC problem, the greedy procedure chooses the biclique that minimizes the ratio of the number of nodes plus 𝑐 over the number of uncovered edges. We initially observed that, in all cases, Role and AMBEA run significantly slower than our algorithm and frequently exceed available memory limits. This behavior is primarily due to the extremely large number of candidate bicliques generated by the baselines. This behavior is consistent with prior observations. For example, in [60], the authors generated synthetic datasets with fewer than 400 vertices and reported more than 6,000 candidate bicliques, with running times exceeding 60 seconds. In our setting, the effect is 𝑑 with 𝛿 = 0.1, even more pronounced: On the Adults dataset in ℓ∞ Role requires 5,473 seconds, generates 1,130,246 candidate bicliques, and reaches a peak memory usage of 42,068 MB. To ensure a fair and feasible comparison, we introduce an earlystopping criterion for Role and AMBEA. At a high level, we constrain all algorithms to operate within comparable time budgets. Specifically, we allow baselines to spend between 10% and 35% of

our algorithm’s total execution time generating candidate bicliques. Under this setting, both baselines still require slightly more total running time than our algorithm. Consequently, our evaluation grants the baselines an advantage by allowing them to run longer and generate more candidate bicliques, while remaining within feasible time and memory limits. Additionally, the consecutively generated candidates by both of our baselines tend to share many vertices. Thus, to ensure the quality of candidates, we also randomly shuffle the vertex order before generating them. Details of CPGR. Across all datasets we evaluated, we observed that CPGR produced representations that were substantially larger than those produced by RT-BC. This behavior is expected, since biclique partitioning is substantially more restrictive than biclique covering (every biclique partition is a biclique cover, but not vice versa), and the objective in [16] is not to compute a minimum-size biclique partition. Consequently, we omitted this baseline from most of our figures, although we still report some examples of the sizes of its computed representations. Setup. All experiments were conducted on a Windows 11 workstation equipped with an Intel Core i7-9700 CPU and 32 GB of DDR4 RAM. All algorithms were implemented in Python 3.12.9. The AMBEA algorithm [55] used in AMBEA, however, is a parallel implementation written in C++. It was compiled as a standalone executable and invoked via Python subprocesses. As a result, AMBEA enjoys an additional performance advantage compared to both Role and RT-BC. Memory usage was monitored using the Python library psrecord, with a 3-second polling interval to minimize measurement overhead.

5.3

Experimental results for WBC

In this section, we first provide a comprehensive comparison of our algorithm (RT-BC) against Role and AMBEA on all versions of Adults, Credit, Gamma, and POPSIM, for different values of 𝛿, as reported in Table 1. For each setting, we report the size of the returned representation, the peak memory usage during execution, and the running time of each algorithm. We omit CPGR from these experiments because, in all cases, it returns representations that are substantially larger than those of the other baselines. We discuss the performance of CPGR separately later. Experiments are conducted under both ℓ2 and ℓ∞ metrics. Since the observed trends are consistent across the two settings, we present the results for the ℓ2 metric here and defer the ℓ∞ results to Appendix E. As discussed above, to ensure a fair comparison, we apply an early-stopping criterion that allows the baselines to run slightly longer than our algorithm, as illustrated in Figure 2(c). This enables a direct comparison of the quality of the resulting representations, as well as the peak memory consumption, under comparable time budgets. As shown in Figure 2(a), our algorithm RT-BC consistently outperforms both Role and AMBEA in terms of representation size across all datasets and for all values of 𝛿. The only exception occurs for the Adults dataset with 𝛿 = 0.05, where all algorithms produce representations of comparable size. In this instance, the corresponding bipartite graph is sparse, with a low average degree leaving limited room for improvement. As the graphs become

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

0.25

0.002 0.003 0.004 0.005 0.006

5000

500

BaselineAMBEA BaselineRole RT-BC

800 600

300 c

400

6000

Memory (MB)

BaselineAMBEA BaselineRole RT-BC

7000 5000 4000 100

200

Baseline/Dataset Role AMBEA CPGR Original RT-BC

300 c

400

600 500 400 300 200 100

0.13

0.14

0.15

0.16

500

15000 10000 5000 100

200

300 c

400

500

20000 10000

BaselineAMBEA BaselineRole RT-BC

2000 1000

Result

7000 6000 5000 4000 3000 2000

25000

BaselineAMBEA BaselineRole RT-BC

0.12

0 0.04 0.06 0.08 0.10 0.12

0.17

Result

BaselineAMBEA BaselineRole RT-BC

20000

0.10

BaselineAMBEA BaselineRole RT-BC

30000

3000

BaselineAMBEA BaselineRole RT-BC

0.08

0.04 0.06 0.08 0.10 0.12

Memory (MB)

200

2000

0.06

(c) Running time in seconds Figure 2: Experimental results for WBC in ℓ2𝑑 across all datasets Credits Gamma 1e6 1e6 1e6 BaselineAMBEA BaselineAMBEA 3.0 1.50 1.5 BaselineRole BaselineRole 2.5 1.25 RT-BC RT-BC 1.0 2.0 1.00 1.5 0.75 0.5 0.50 1.0 100 200 300 400 500 100 200 300 400 500 100 500 c c (a) Size of representation

Memory (MB)

100

200 0.002 0.003 0.004 0.005 0.006

Result

BaselineAMBEA BaselineRole RT-BC

4000

BaselineAMBEA BaselineRole RT-BC

0.04

0.13 0.14 0.15 0.16 0.17 (b) Peak memory in MB

400

650000 600000 550000 500000 450000

0.17

4 3 2 1 0

0.002 0.003 0.004 0.005 0.006

1000

1000

0.16

BaselineAMBEA BaselineRole RT-BC

6000

10000

0.15

Time (s)

BaselineAMBEA BaselineRole RT-BC

BaselineAMBEA BaselineRole RT-BC

15000

POPSIM 1e6

BaselineAMBEA BaselineRole RT-BC

0.13 0.14 (a) Size of representation

25000 BaselineAMBEA 20000 BaselineRole RT-BC 15000 10000 5000 0 0.05 0.10 0.15 0.20 0.25

1500

1.0 0.8 0.6 0.4 0.2

1e6

Result

Result 0.20

Memory (MB)

0.15

Adults

Result

2

Time (s)

0.10

Memory (MB)

0.05

0 0.05 0.10 0.15 0.20 0.25

Memory (MB)

3

BaselineAMBEA BaselineRole RT-BC

1

2000 Time (s)

4

Gamma

Result

BaselineAMBEA BaselineRole RT-BC

Time (s)

Result Memory (MB)

8 6 4 2 0

Credits 1e6

Memory (MB)

Adults 1e6

POPSIM BaselineAMBEA BaselineRole RT-BC

200

300 c

400

500

BaselineAMBEA BaselineRole RT-BC

20000 15000 10000 5000

100

200

300 c

400

500

(b) Peak memory in MB 𝑑 across all datasets Figure 3: Experimental results for GWBC in ℓ∞

100

200

300 c

400

Adults 𝛿 = 0.2 Gamma 𝛿 = 0.16 POPSIM-S POPSIM-D MovieLens100K MovieLens1M WorldCities 4,668,513 738,232 7,038,915 108,138,671 188,227 2,336,652 13,429 3,024,324 551,686 5,387,872 122,279,423 108,014 1,079,149 7,427 5,242,099 1,082,100 11,250,790 245,761,564 200,000 1,908,017 15,036 6,032,686 1,082,100 11,250,790 245,761,564 200,000 2,000,000 15,036 1,012,402 379,675 3,396,491 904,425 101,152 952,869 6,034 Table 2: Representation size produced by each baseline for WBC on each dataset.

500

162bit 52,577 51,368 74,236 74,236 40,590

Aryan Esmailpour, Khoi Le, and Stavros Sintos

larger and denser, however, the advantage of RT-BC becomes increasingly pronounced. For example, on real-world datasets, RT-BC produces representations that are up to four times smaller than those returned by both baselines (e.g., on the Credit dataset). The improvement is even more substantial on the semi-synthetic POPSIM dataset, where the representation produced by RT-BC is approximately 26 times smaller than those produced by the baselines. This behavior can be attributed to the low intrinsic dimensionality of the POPSIM dataset and the highly geometric manner in which it is generated. The tree data structure employed by RT-BC performs particularly well in low-dimensional settings. By exploring the canonical hyper-rectangles, the algorithm is able to identify regions 𝑥 whose corresponding subgraphs 𝐺𝑥 capture near-optimal bicliques, leading to significantly more compact representations. Next, in Figure 2(b), we compare the peak memory usage across all datasets. RT-BC consistently uses significantly less memory than both baselines. In some cases, our method requires up to three times less memory than the baselines (e.g., Gamma dataset). These results are consistent with our theoretical analysis. As shown in Theorem 4.2, our algorithm uses asymptotically only linear space with respect to the size of the input graph. In contrast, the memory consumption of the baselines is dominated by the total size of the candidate bicliques they generate, which is typically very large. Finally, Role and AMBEA exhibit similar behavior, producing biclique edge covers of comparable size. In some cases, AMBEA outperforms Role due to its parallel C++ implementation of the candidate biclique generation step, which allows it to explore more candidates within the same time budget. Comprehensive comparison of all baselines on small, large, sparse, and dense bipartite graphs. Table 2 reports the representation size returned by RT-BC and all baselines (Role, AMBEA, and CPGR) across a diverse collection of bipartite graphs; for reference, we also report the size of the original edge-based representation, obtained without applying any compression algorithm. To ensure a fair comparison, we configure all baselines so that their running times are roughly comparable to that of RT-BC. The datasets in this comparison consist of two representative geometric bipartite graphs, Adults and Gamma; two variants of POPSIM, capturing both sparse and very large dense instances; and four real, non-geometric bipartite graphs, namely MovieLens100K, MovieLens1M, WorldCities, and 162bit, after first embedding them into a geometric space. Across all real bipartite graphs, RT-BC consistently produces smaller representations than all compared baselines. Finally, CPGR often returns a representation whose size is close to, or even the same as, that of the original graph, suggesting that biclique partitioning is not an effective approach for WBC on these instances. There are two main reasons for this. First, as discussed above, constructing a biclique partition is substantially more restrictive than constructing a biclique cover. Second, the implementation of CPGR from [16] is restricted to graphs satisfying 𝑚 ≥ 2·(max{|𝑽 |, |𝑼 |}) 3/2 , a condition that does not hold for many of the graphs in our evaluation.

5.4

Experimental results for GWBC

In Figure 3, we report the representation size and peak memory usage of our algorithm and the baselines for the GWBC problem under the ℓ∞ metric, for varying values of 𝑐 and a fixed value of 𝛿.

Specifically, we use 𝛿 = 0.1 for Adult, 𝛿 = 0.002 for Credit, 𝛿 = 0.13 for Gamma, and 𝛿 = 0.04 for POPSIM. Fixing 𝛿 isolates the effect of 𝑐 on the quality and memory footprint of the resulting representations. As in the WBC experiments, all algorithms are evaluated under comparable time budgets to ensure a fair comparison. Since the running-time trends are consistent with those observed for WBC, we defer the detailed timing results to Appendix E. Consistent with our earlier observations, our algorithm RT-BC outperforms both baselines across all evaluation metrics, consistently producing smaller representations while using less memory. Notably, the performance gap between our method and the baselines becomes even more pronounced in the GWBC setting. For example, on the Gamma dataset with 𝛿 = 0.13, under the WBC objective RT-BC produces a representation that is 2-times smaller than those returned by the baselines. In contrast, for the GWBC problem under the same value of 𝛿 and with 𝑐 = 500, RT-BC returns a representation that is 3-times smaller than the baselines. Similar trends are observed for the remaining bipartite graphs, including MovieLens and the two matrix datasets; therefore, we omit them from the figures. We observe occasional memory spikes for AMBEA. This behavior is due to the combination of early stopping and the randomized vertex ordering used at each run to avoid repeatedly exploring the same regions of the graph.

6

Related work

Lossless compact representations for graphs have been studied extensively [8, 12, 26, 28, 56]. While these techniques often achieve high compression ratios, the resulting representations are typically not directly usable by general-purpose graph algorithms and may require substantial reconstruction overhead. Feder and Motwani [29] introduced a graph compression method that preserves path information by partitioning edges into bicliques; Chavan et al. [16] later improved its running time. In contrast, we study biclique coverings rather than partitions and explicitly formulate the optimization problem of minimizing the representation size. Unlike prior heuristic approaches, we provide approximation algorithms with provable guarantees for meaningful graph classes. The WBC problem has been studied in theory [20, 24, 58, 59]. This body of work primarily focuses on establishing upper and lower bounds on the cost of an optimal solution. The decision version was later shown to be NP-Complete in [44, 60]. For an overview of WBC and its data mining applications, see [48]. To the best of our knowledge, no approximation algorithms or inapproximability results are known. Existing approaches are limited to heuristics without theoretical performance guarantees [48, 50, 60]. A related and well-studied variant is the bipartite dimension problem where the goal is to find the minimum number of bicliques whose union of edges covers all edges of the graph. It is known to be NP-hard [34, 53] and admits strong inapproximability results [13, 30, 37, 42, 57, 68]. On the positive side, the problem is fixed-parameter tractable [14, 31, 52] and exact polynomial-time algorithms are known for some graph classes [4, 46, 49]. A variety of problems have been studied on 𝛿-disk graphs, including the densest subgraph problem [39], the maximum clique problem [22], and others [2, 17]. Recently, Lahn et al. [43] designed

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

an efficient algorithm for the maximum cardinality bipartite matching problem on 𝛿-disk bipartite graphs.

7

Future Work

Several directions remain for future work. For large 𝑐 the GWBC problem reduces to the bipartite dimension problem, which is NPhard to approximate [37, 57]. It is an open question whether similar inapproximability results hold for smaller values of 𝑐. Another direction is to design approximation or exact algorithms for WBC and GWBC on graph classes beyond intersection bipartite graphs. Finally, it would be interesting to integrate our representations into graph compression pipelines and evaluate the resulting compression ratios on real-world graphs.

References [1] Pankaj K Agarwal, Xiao Hu, Stavros Sintos, and Jun Yang. On reporting durable patterns in temporal proximity graphs. Proceedings of the ACM on Management of Data, 2(2):1–26, 2024. [2] Pankaj K Agarwal and Jiangwei Pan. Near-linear algorithms for geometric hitting sets and set covers. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 271–279, 2014. [3] Heer Ambavi, Mridul Sharma, and Varun Gohil. Densest-subgraph-discovery. https://github.com/varungohil/Densest-Subgraph-Discovery, 2020. GitHub repository. [4] Jérôme Amilhastre, Marie-Catherine Vilarem, and Philippe Janssen. Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs. Discrete applied mathematics, 86(2-3):125–144, 1998. [5] Sunil Arya and David M Mount. Approximate range searching. Computational Geometry, 17(3-4):135–152, 2000. [6] Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891–923, 1998. [7] Aistis Atminas and Viktor Zamaraev. On forbidden induced subgraphs for unit disk graphs. Discrete & Computational Geometry, 60(1):57–97, 2018. [8] Max Bannach, Florian Andreas Marwitz, and Till Tantau. Faster graph algorithms through dag compression. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), pages 8–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2024. [9] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: https://doi.org/10.24432/C5XW20. [10] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509–517, 1975. [11] R. Bock. MAGIC Gamma Telescope. UCI Machine Learning Repository, 2004. DOI: https://doi.org/10.24432/C52C8B. [12] Gregory Buehrer and Kumar Chellapilla. A scalable pattern mining approach to web graph compression with communities. In Proceedings of the 2008 international conference on web search and data mining, pages 95–106, 2008. [13] Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, and Andreas Karrenbauer. Nearly tight approximability results for minimum biclique cover and partition. In European Symposium on Algorithms, pages 235–246. Springer, 2014. [14] Sunil Chandran, Davis Issac, and Andreas Karrenbauer. On the parameterized complexity of biclique cover and partition. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Schloss Dagstuhl-LeibnizZentrum für Informatik, 2017. [15] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In International workshop on approximation algorithms for combinatorial optimization, pages 84–95. Springer, 2000. [16] Akshar Chavan, Sanaz Rabinia, Daniel Grosu, and Marco Brocanelli. Speeding-up graph algorithms via clique partitioning. Networks, 88(1):85–98, 2026. [17] Chandra Chekuri, Sariel Har-Peled, and Kent Quanrud. Fast lp-based approximations for geometric packing and covering problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1019– 1038. SIAM, 2020. [18] Chandra Chekuri, Kent Quanrud, and Manuel R Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1531–1555. SIAM, 2022. [19] Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. Journal of the ACM, 72(3):1–103, 2025. [20] FRK Chung, P Erdős, and Joel Spencer. On the decomposition of graphs into complete bipartite subgraphs. In Studies in Pure Mathematics: To the Memory of Paul Turán, pages 95–101. Springer, 1983. [21] Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233–235, 1979.

[22] Brent N Clark, Charles J Colbourn, and David S Johnson. Unit disk graphs. Discrete mathematics, 86(1-3):165–177, 1990. [23] Timothy A. Davis and Yifan Hu. The university of florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1):1:1–1:25, 2011. doi:10.1145/ 2049662.2049663. [24] Akbar Davoodi, Ramin Javadi, and Behnaz Omoomi. Edge clique covering sum of graphs. Acta Mathematica Hungarica, 149:82–91, 2016. [25] Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer, 2008. [26] Laxman Dhulipala, Igor Kabiljo, Brian Karrer, Giuseppe Ottaviano, Sergey Pupyrev, and Alon Shalita. Compressing graphs and indexes with recursive graph bisection. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1535–1544, 2016. [27] Aryan Esmailpour, Khoi Le, and Stavros Sintos. Datasets and code for: Compact representations of geometric bipartite graphs via weighted biclique covers. https: //github.com/KhoiLe01/WBC_experiment. [28] Wenfei Fan, Yuanhao Li, Muyang Liu, and Can Lu. Making graphs compact by lossless contraction. In Proceedings of the 2021 International Conference on Management of Data, pages 472–484, 2021. [29] Tomás Feder and Rajeev Motwani. Clique partitions, graph compression and speeding-up algorithms. Journal of Computer and System Sciences, 51(2):261–272, 1995. [30] Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187–199, 1998. [31] Herbert Fleischner, Egbert Mujuni, Daniël Paulusma, and Stefan Szeider. Covering graphs with few complete bipartite subgraphs. Theoretical Computer Science, 410(21-23):2045–2053, 2009. [32] Aristides Gionis. Algorithmic methods for mining large graphs, lecture 3: Finding dense subgraphs. Lecture notes presented at Bertinoro International Spring School (BISS), 2016. Available at: https://users.ics.aalto.fi/gionis/biss2016-lec3. pdf. [33] Andrew V Goldberg. Finding a maximum density subgraph. 1984. [34] Lee-Ad J Gottlieb, John E Savage, and Arkady Yerukhimovich. Efficient data storage in large nanoarrays. Theory of Computing Systems, 38(4):503–536, 2005. [35] GroupLens Research. MovieLens 100K Dataset. https://grouplens.org/datasets/ movielens/100k/, 1998. Released April 1998. Accessed May 17, 2026. [36] GroupLens Research. MovieLens 1M Dataset. https://grouplens.org/datasets/ movielens/1m/, 2003. Released February 2003. Accessed May 17, 2026. [37] Hermann Gruber and Markus Holzer. Inapproximability of nondeterministic state and transition complexity assuming p≠ np. In International Conference on Developments in Language Theory, pages 205–216. Springer, 2007. [38] Antonin Guttman. R-trees: a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data, page 47–57, New York, NY, USA, 1984. Association for Computing Machinery. doi:10.1145/602259.602266. [39] Sariel Har-Peled and Saladi Rahul. Approximating densest subgraph in geometric intersection graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), pages 43–1, 2025. [40] Sariel Har-Peled and Everett Yang. Approximation algorithms for maximum matchings in geometric intersection graphs. In 38th International Symposium on Computational Geometry, SoCG 2022, page 47, 2022. [41] Satyabrata Jana, Anil Maheshwari, Saeed Mehrabi, and Sasanka Roy. Maximum bipartite subgraphs of geometric intersection graphs. International Journal of Computational Geometry & Applications, 33(03n04):133–157, 2023. [42] Subhash Khot and Ashok Kumar Ponnuswami. Better inapproximability results for maxclique, chromatic number and min-3lin-deletion. In International Colloquium on Automata, Languages, and Programming, pages 226–237. Springer, 2006. [43] Nathaniel Lahn, Sharath Raghvendra, and Jiacheng Ye. A faster maximum cardinality matching algorithm with applications in machine learning. Advances in Neural Information Processing Systems, 34:16885–16898, 2021. [44] Xuemin Lin. On the computational complexity of edge concentration. Discrete Applied Mathematics, 101(1):197–205, 2000. URL: https://www.sciencedirect.com/ science/article/pii/S0166218X99002073, doi:10.1016/S0166-218X(99)002073. [45] D Lokshtanov, F Panolan, S Saurabh, J Xue, and M Zehavi. Bipartizing (pseudo-) disk graphs: Approximation with a ratio better than 3. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). LIPIcs, 2024. [46] Anna Lubiw. A weighted min-max relation for intervals. Journal of Combinatorial Theory, Series B, 53(2):151–172, 1991. [47] Hiroshi Maehara. Space graphs and sphericity. Discrete Applied Mathematics, 7(1):55–64, 1984. [48] Barsha Mitra, Shamik Sural, Jaideep Vaidya, and Vijayalakshmi Atluri. A survey of role mining. ACM Comput. Surv., 48(4), February 2016. doi:10.1145/2871148. [49] Haiko Müller. On edge perfectness and classes of bipartite graphs. Discrete Mathematics, 149(1-3):159–187, 1996.

Aryan Esmailpour, Khoi Le, and Stavros Sintos

[50] Frances J Newbery. Edge concentration: A method for clustering directed graphs. In Proceedings of the 2nd International Workshop on Software configuration management, pages 76–85, 1989. [51] Khanh Duy Nguyen, Nima Shahbazi, and Abolfazl Asudeh. Popsim: An individual-level population simulator for equitable allocation of city resources. Algorithmic Fairness in Artificial intelligence, Machine learning and Decision making (AFair-AMLD23), 2023. [52] Igor Nor, Danny Hermelin, Sylvain Charlat, Jan Engelstadter, Max Reuter, Olivier Duron, and Marie-France Sagot. Mod/resc parsimony inference: Theory and application. Information and Computation, 213:23–32, 2012. [53] James Orlin. Contentment in graph theory: covering graphs with cliques. In Indagationes Mathematicae (Proceedings), volume 80, pages 406–424. Elsevier, 1977. [54] James B Orlin. Max flows in o (nm) time, or better. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 765–774, 2013. [55] Zhe Pan, Xu Li, Shuibing He, Xuechen Zhang, Rui Wang, Yunjun Gao, Gang Chen, and Xian-He Sun. Ambea: Aggressive maximal biclique enumeration in large bipartite graph computing. IEEE Transactions on Computers, 73(12):2664–2677, 2024. doi:10.1109/TC.2024.3441864. [56] Ryan A Rossi and Rong Zhou. Graphzip: a clique-based sparse graph compression method. Journal of Big Data, 5(1):10, 2018. [57] Hans Ulrich Simon. On approximate solutions for combinatorial optimization problems. SIAM Journal on Discrete Mathematics, 3(2):294–310, 1990. [58] T. Tarjan. Complexity of lattice-configurations. 1975. [59] Zsolt Tuza. Covering of graphs by complete bipartite subgraphs; complexity of 0–1 matrices. Combinatorica, 4:111–116, 1984.

[60] Jaideep Vaidya, Vijayalakshmi Atluri, Qi Guo, and Haibing Lu. Edge-rmp: Minimizing administrative assignments for role-based access control. J. Comput. Secur., 17(2):211–235, April 2009. [61] Jaideep Vaidya, Vijayalakshmi Atluri, and Janice Warner. Roleminer: mining roles using subset enumeration. In Proceedings of the 13th ACM Conference on Computer and Communications Security, CCS ’06, page 144–153, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1180405.1180424. [62] Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 501–510, 2014. [63] Barry Wellman et al. Structural analysis: From method and metaphor to theory and substance. Contemporary Studies in Sociology, 15:19–61, 1997. [64] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD workshop on mining data semantics, pages 1–8, 2012. [65] I-Cheng Yeh. Default of Credit Card Clients. UCI Machine Learning Repository, 2009. DOI: https://doi.org/10.24432/C55S3H. [66] Xiaohan Zhao, Alessandra Sala, Haitao Zheng, and Ben Y Zhao. Efficient shortest paths on massive social graphs. In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom), pages 77–86. IEEE, 2011. [67] Xiaohan Zhao and Haitao Zheng. Orion: shortest path estimation for large social graphs. In 3rd Workshop on Online Social Networks (WOSN 2010), 2010. [68] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 681–690, 2006.

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

A

Missing proofs from Section 2

These bicliques cover all edges incident to the vertices 𝑧𝑖 . They use

Proof of Lemma 2.1. An unselected vertex 𝑤𝑖 requires one biclique containing 𝑧𝑖 , whereas a selected vertex requires two such bicliques. Moreover, a single biclique cannot contain both 𝑧𝑖 and 𝑧 𝑗 for 𝑖 ≠ 𝑗, since 𝑁 (𝑧𝑖 ) ∩ 𝑁 (𝑧 𝑗 ) = ∅. ′ Hence, if 𝑘 vertices are selected, the vertex gadgets require at least (𝑛 − 𝑘 ′ ) + 2𝑘 ′ = 𝑛 + 𝑘 ′ bicliques. Now consider an edge 𝑒 = {𝑤𝑖 , 𝑤 𝑗 } ∈ 𝐹 . Consider the four edges (𝑝𝑒1, 𝑢𝑒1 ),

(𝑝𝑒2, 𝑢𝑒2 ),

(𝑝𝑒3, 𝑢𝑒3 ),

(𝑝𝑒4, 𝑢𝑒4 ).

No two of these edges can belong to the same biclique. Indeed, for any two distinct edges in this collection, at least one of the two corresponding cross edges is absent from 𝑮. Therefore, at least four distinct bicliques are necessary to cover them. Each of these bicliques contains one of the private vertices 𝑝𝑒1, . . . , 𝑝𝑒4 . Consequently, none of them is a biclique already counted for a vertex gadget, since no private vertex 𝑝𝑒𝑟 is adjacent to any 𝑧𝑖 . Furthermore, a biclique containing a private vertex of the gadget corresponding to 𝑒 cannot contain a private vertex of a different edge gadget. Thus, the four bicliques can be charged uniquely to the gadget corresponding to 𝑒. It remains to consider the case in which neither 𝑤𝑖 nor 𝑤 𝑗 is selected. Consider the following five edges: (𝑥𝑖 , 𝑢𝑒1 ),

(𝑦 𝑗 , 𝑢𝑒2 ),

(𝑦𝑖 , 𝑢𝑒3 ),

(𝑥 𝑗 , 𝑢𝑒4 ),

(𝑝𝑒1, 𝑢𝑒5 ).

No two of these five edges can be contained in the same biclique. For two of the first four edges this follows because each of 𝑥𝑖 , 𝑦 𝑗 , 𝑦𝑖 , 𝑥 𝑗 is adjacent to exactly its corresponding vertex among 𝑢𝑒1, 𝑢𝑒2, 𝑢𝑒3, 𝑢𝑒4 within this gadget. Moreover, 𝑢𝑒5 is adjacent to none of 𝑥𝑖 , 𝑦 𝑗 , 𝑦𝑖 , 𝑥 𝑗 , so the last edge cannot share a biclique with any of the first four. Hence, at least five distinct bicliques are needed to cover these five edges. We claim that each of these five bicliques contains a private vertex of the gadget 𝑒. This is immediate for the biclique covering (𝑝𝑒1, 𝑢𝑒5 ). Consider, for example, a biclique covering (𝑥𝑖 , 𝑢𝑒1 ). Since 𝑤𝑖 is not selected, by the normal form described above there is no biclique whose 𝑽 -side is exactly {𝑥𝑖 }. Therefore, such a biclique must contain another vertex on its 𝑽 -side. The only other neighbors of 𝑢𝑒1 are 𝑝𝑒1 and 𝑝𝑒2 , so the biclique must contain one of these private vertices. The same argument applies to (𝑦 𝑗 , 𝑢𝑒2 ), (𝑦𝑖 , 𝑢𝑒3 ), and (𝑥 𝑗 , 𝑢𝑒4 ). Thus, all five required bicliques contain private vertices of the gadget 𝑒. They are therefore distinct from the vertex-gadget bicliques and cannot simultaneously be charged to any other edge gadget. Hence, the lower bounds are additive over the edge gadgets. □ Proof of Lemma 2.2. We first prove the forward direction. Suppose that 𝐶 ⊆ 𝑊 is a vertex cover of 𝐽 of size 𝑘 ≤ 𝐾. For every vertex 𝑤𝑖 ∉ 𝐶, we create the biclique {𝑥𝑖 , 𝑦𝑖 } × {𝑧𝑖 }. For every vertex 𝑤𝑖 ∈ 𝐶, we instead create the two bicliques {𝑥𝑖 } × {𝑧𝑖 }

and

{𝑦𝑖 } × {𝑧𝑖 }.

(𝑛 − 𝑘) + 2𝑘 = 𝑛 + 𝑘 bicliques and initially contribute 3(𝑛 − 𝑘) + 4𝑘 = 3𝑛 + 𝑘 to the total biclique size. We next cover the edges of every edge gadget. Consider an edge 𝑒 = {𝑤𝑖 , 𝑤 𝑗 } ∈ 𝐹 , where 𝑖 < 𝑗. Since 𝐶 is a vertex cover, at least one of 𝑤𝑖 , 𝑤 𝑗 belongs to 𝐶. Suppose first that 𝑤𝑖 ∈ 𝐶. We add 𝑢𝑒1 to the 𝑼 -side of the existing biclique whose 𝑽 -side is {𝑥𝑖 }, and add 𝑢𝑒3 to the 𝑼 -side of the existing biclique whose 𝑽 -side is {𝑦𝑖 }. We then introduce the following four bicliques: {𝑝𝑒1, 𝑝𝑒2 } × {𝑢𝑒1, 𝑢𝑒5 }, {𝑝𝑒3, 𝑝𝑒4 } × {𝑢𝑒3, 𝑢𝑒5 }, {𝑦 𝑗 , 𝑝𝑒2, 𝑝𝑒3 } × {𝑢𝑒2 }, and {𝑥 𝑗 , 𝑝𝑒4, 𝑝𝑒1 } × {𝑢𝑒4 }. These bicliques, together with the two existing bicliques containing 𝑥𝑖 and 𝑦𝑖 , cover all edges of the gadget corresponding to 𝑒. If instead 𝑤 𝑗 ∈ 𝐶, we use the symmetric construction. We add 𝑢𝑒2 to the 𝑼 -side of the existing biclique whose 𝑽 -side is {𝑦 𝑗 } and add 𝑢𝑒4 to the 𝑼 -side of the existing biclique whose 𝑽 -side is {𝑥 𝑗 }. We then introduce {𝑥𝑖 , 𝑝𝑒1, 𝑝𝑒2 } × {𝑢𝑒1 }, {𝑦𝑖 , 𝑝𝑒3, 𝑝𝑒4 } × {𝑢𝑒3 }, {𝑝𝑒2, 𝑝𝑒3 } × {𝑢𝑒2, 𝑢𝑒5 }, and {𝑝𝑒4, 𝑝𝑒1 } × {𝑢𝑒4, 𝑢𝑒5 }. Therefore, every edge of 𝐽 contributes exactly four new bicliques. The four new bicliques have total size 16, while the two additions of gadget vertices to already existing bicliques increase the total biclique size by 2. Hence, every edge gadget contributes exactly 18 to the total biclique size. Consequently, the resulting biclique edge cover S satisfies |S| = 𝑛 + 𝑘 + 4𝑚 and 𝜇 (S) = 3𝑛 + 𝑘 + 18𝑚. It follows that 𝜎 (S) = 𝜇 (S) + 𝑐 |S| = 3𝑛 + 𝑘 + 18𝑚 + 𝑐 (𝑛 + 𝑘 + 4𝑚) = 3𝑛 + 18𝑚 + 𝑐 (𝑛 + 4𝑚) + (1 + 𝑐)𝑘 ≤ 3𝑛 + 18𝑚 + 𝑐 (𝑛 + 4𝑚) + (1 + 𝑐)𝐾 = 𝜏𝑐 . This proves the forward direction. For the reverse direction, suppose that 𝑮 admits a biclique edge cover S satisfying 𝜎 (S) ≤ 𝜏𝑐 . By applying the normalization described above, we may assume that S is in normal form without increasing its cost. Let 𝐶 ′ ⊆ 𝑊 be the set of selected vertices, and let 𝑘 ′ = |𝐶 ′ |.

Aryan Esmailpour, Khoi Le, and Stavros Sintos

Part 𝑽

Part 𝑼

𝑎

𝑐

𝑎1

𝑐1

Copies of 𝑎

Copies of 𝑐

𝑎2

𝑐2

𝑏1

𝑑1

𝑏2

𝑑2

𝑘 -blow-up (𝑘 = 2)

𝑏

𝑑

Copies of 𝑏

Copies of 𝑑

(a) Graph 𝑮

(b) Graph 𝑘𝑮

Figure 4: Illustration of the blow-up graph construction with 𝑘 = 2. (a) A bipartite graph 𝑮 with vertices 𝑽 = {𝑎, 𝑏} and 𝑼 = {𝑐, 𝑑 }. (b) The constructed graph 𝑘𝑮. Solid black edges connect corresponding copies, while dashed red edges connect noncorresponding copies. Let 𝐹 ′ ⊆ 𝐹 denote the set of edges having at least one endpoint in 𝐶 ′ , and define 𝑞 = |𝐹 \ 𝐹 ′ |. Thus, 𝑞 is the number of edges of 𝐽 having neither endpoint selected. By Lemma 2.1, the vertex gadgets require at least 𝑛 +𝑘 ′ bicliques. Each of the 𝑚 − 𝑞 edge gadgets corresponding to an edge in 𝐹 ′ requires at least four additional bicliques, whereas each of the 𝑞 remaining edge gadgets requires at least five additional bicliques. Hence, ′

|S| ≥ 𝑛 + 𝑘 + 4(𝑚 − 𝑞) + 5𝑞 = 𝑛 + 𝑘 ′ + 4𝑚 + 𝑞.

(4)

Similarly, by the size lower bounds from [60], the vertex gadgets contribute at least 3𝑛 +𝑘 ′ to the total biclique size. Each edge gadget corresponding to an edge in 𝐹 ′ contributes at least 18, whereas every edge gadget corresponding to an edge in 𝐹 \ 𝐹 ′ contributes at least 20. Therefore, 𝜇 (S) ≥ 3𝑛 + 𝑘 ′ + 18(𝑚 − 𝑞) + 20𝑞 = 3𝑛 + 𝑘 ′ + 18𝑚 + 2𝑞.

(5)

Combining Equations (4) and (5), and using 𝑐 ≥ 0, we obtain 𝜎 (S) = 𝜇 (S) + 𝑐 |S| ≥ 3𝑛 + 𝑘 ′ + 18𝑚 + 2𝑞 + 𝑐 (𝑛 + 𝑘 ′ + 4𝑚 + 𝑞) = 3𝑛 + 18𝑚 + 𝑐 (𝑛 + 4𝑚) + (1 + 𝑐)𝑘 ′ + (2 + 𝑐)𝑞. Since 𝜎 (S) ≤ 𝜏𝑐 , it follows from the definition of 𝜏𝑐 that (1 + 𝑐)𝑘 ′ + (2 + 𝑐)𝑞 ≤ (1 + 𝑐)𝐾 . Since 𝑐 ≥ 0, we have 2 + 𝑐 ≥ 1 + 𝑐, and therefore (1 + 𝑐) (𝑘 ′ + 𝑞) ≤ (1 + 𝑐)𝑘 ′ + (2 + 𝑐)𝑞 ≤ (1 + 𝑐)𝐾 . Since 1 + 𝑐 > 0, we conclude that 𝑘′ + 𝑞 ≤ 𝐾 . Starting from 𝐶 ′ , for every edge in 𝐹 \ 𝐹 ′ we add an arbitrary endpoint of that edge. Since there are 𝑞 such edges, the resulting set 𝐶 is a vertex cover of 𝐽 and satisfies |𝐶 | ≤ 𝑘 ′ + 𝑞 ≤ 𝐾 . Thus, 𝐽 admits a vertex cover of size at most 𝐾.

□

Proof of Theorem 2.3. First, dGWBC belongs to NP. Given a collection of bicliques, we can verify in polynomial time that every selected subgraph is a biclique, that all edges of the input graph are covered, and that the total cost is at most the prescribed threshold.

Moreover, we may assume that a biclique edge cover contains at most |𝑬 | bicliques. Indeed, if a biclique does not contain an edge that is uncovered by all other bicliques, then that biclique can be removed without increasing the cost. Hence, a polynomial-size certificate always exists. For NP-hardness, let 𝑐 ≥ 0 be arbitrary. Given an instance (𝐽, 𝐾) of Vertex Cover, we construct the graph 𝑮 and the threshold 𝜏𝑐 = 3𝑛 + 𝐾 + 18𝑚 + 𝑐 (𝑛 + 𝐾 + 4𝑚) as described above. The graph 𝑮 contains 𝑂 (𝑛 + 𝑚) vertices and edges, and its size is independent of the value of 𝑐. Moreover, 𝜏𝑐 can be computed in polynomial time. By Lemma 2.2, 𝐽 has a vertex cover of size at most 𝐾 if and only if 𝑮 admits a biclique edge cover S satisfying 𝜎 (S) ≤ 𝜏𝑐 . Therefore, dGWBC is NP-hard for any rational value 𝑐 ≥ 0. Together with membership in NP, this proves the theorem. □

B

Simpler proof that GWBC problem is NP-Complete for constant 𝑐

It is known that covering the edges of a bipartite graph with the minimum number of bicliques (the bipartite dimension problem) is NP-complete [53]. Similarly, minimizing the total size of the bicliques in a cover (the dWBC problem) is also NP-complete [60]. The GWBC problem generalizes both objectives by jointly accounting for the number and total size of the selected bicliques. Indeed, when 𝑐 = 0, GWBC reduces to WBC, while for sufficiently large 𝑐 (e.g., 𝑐 ≥ 𝑛 6 ), it reduces to the bipartite dimension problem (the term Í 𝑐𝜅 dominates the weight term 𝑆𝑖 ∈ S |D (𝑆𝑖 )|). Since both extremes are NP-complete, we show that for any fixed integer value of 𝑐, the decision version dGWBC is also NP-complete. To prove the hardness of dGWBC, we present a polynomial-time reduction from the dWBC problem. Let 𝑮 (𝑽, 𝑼 , 𝑬) be a bipartite graph and let 𝜏 be a positive integer representing the target maximum weight for the dWBC problem over 𝑮. We construct a corresponding graph and target cost for the dGWBC problem as follows. Let 𝑚 = |𝑬 | be the number of edges in 𝑮. We choose an integer 𝑘 such that 𝑘 > 𝑐𝑚. We define the graph 𝑮 ′ to be a 𝑘-blow-up of 𝑮, denoted as 𝑘𝑮. For every vertex 𝑥 ∈ D (𝑮), we create 𝑘 copies in 𝑘𝑮, denoted by {𝑥 1, 𝑥 2, . . . , 𝑥𝑘 }. If (𝑢, 𝑣) ∈ 𝑬, we connect every copy of 𝑢 to every copy of 𝑣 in 𝑘𝑮. Thus, if 𝑢 ∈ 𝑽 , 𝑣 ∈ 𝑼 , and (𝑢, 𝑣) ∈ 𝑬, then for all 𝑖, 𝑗 ∈ [𝑘], there is an edge between 𝑢𝑖 and 𝑣 𝑗 in 𝑘𝑮. More formally, we set D (𝑘𝑮) = {𝑥𝑖 | 𝑥 ∈ D (𝑮), 𝑖 ∈ [𝑘]} and E (𝑘𝑮) = {(𝑢𝑖 , 𝑣 𝑗 ) | (𝑢, 𝑣) ∈ E (𝑮), 𝑖, 𝑗 ∈ [𝑘]}. An example of this construction is shown in Figure 4. We set the target cost for the dGWBC problem on 𝑘𝑮 to be 𝜏 ′ = 𝑘𝜏 + 𝑐𝑚. We now show that a solution to WBC on 𝑮 with cost at most 𝜏 corresponds to a solution to GWBC on 𝑘𝑮 with cost at most 𝜏 ′ , and vice versa. Lemma B.1. There exists a biclique edge cover S for 𝑮 such that 𝜇 (S) ≤ 𝜏, if and only if there exists a biclique edge cover S ′ for 𝑘𝑮 such that 𝜎 (S ′ ) ≤ 𝑘𝜏 + 𝑐𝑚.

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

Proof. We begin by showing the first direction. Let S = {𝑆 1, . . . , 𝑆𝑟 } Í be a biclique edge cover of 𝑮 satisfying 𝜇 (S) = 𝑟𝑗=1 |D (𝑆 𝑗 )| ≤ 𝜏. We construct a cover S ′ for 𝑘𝑮 by expanding each biclique in S. For each 𝑆 𝑗 ∈ S, we define a corresponding subgraph 𝑆 𝑘𝑗 in 𝑘𝑮 such that D (𝑆 𝑘𝑗 ) = {𝑣𝑖 | 𝑣 ∈ D (𝑆 𝑗 ), 𝑖 ∈ [𝑘]}. Since 𝑆 𝑗 is a biclique in 𝑮, it follows from the construction of 𝑘𝑮 that for every 𝑣 ∈ V (𝑆 𝑗 ) and 𝑢 ∈ U (𝑆 𝑗 ), all edges between copies of 𝑢 and copies of 𝑣 exist in 𝑘𝑮. Therefore, 𝑆 𝑘𝑗 is a biclique in 𝑘𝑮. The collection S ′ = {𝑆 1𝑘 , . . . , 𝑆𝑟𝑘 } forms a valid biclique edge cover for 𝑘𝑮 since every edge (𝑢𝑖 , 𝑣 𝑗 ) in E (𝑘𝑮) corresponds to an edge (𝑢, 𝑣) in E (𝑮), which is covered by some 𝑆𝑙 . Therefore, the edge (𝑢𝑖 , 𝑣 𝑗 ) is covered by 𝑆𝑙𝑘 ∈ S ′ . The size of each blownup biclique is |D (𝑆 𝑘𝑗 )| = 𝑘 · |D (𝑆 𝑗 )|, by definition. Therefore, the Í total weight portion of the cost of the cover S ′ is 𝑟𝑗=1 |D (𝑆 𝑘𝑗 )| = 𝑘 ·𝜇 (S) ≤ 𝑘𝜏. Regarding the constant cost component of 𝜎, note that |S ′ | = |S| = 𝑟 . Since a trivial edge cover consisting of individual edges has size 𝑚 (since |𝑬 | = 𝑚), we can assume without loss of generality that 𝑟 ≤ 𝑚. Thus, the total cost for S ′ is: 𝑟 ∑︁ |D (𝑆 𝑘𝑗 )| ≤ 𝑐𝑚 + 𝑘𝜏 . 𝜎 (S ′ ) = 𝑐 |S ′ | + 𝑗=1

This completes the first part of the lemma. Next, we show the other direction. Let S ′ be a biclique edge cover of 𝑘𝑮 satisfying the cost constraint. For all vertices 𝑥 ∈ D (𝑘𝑮) let 𝑛𝑥 (S ′ ) denote the number of bicliques in S ′ that contain the vertex 𝑥. The total weight component of the cost function 𝜎 (S ′ ) Í Í can be written as 𝑆 ′ ∈ S ′ |D (𝑆 ′ )| = 𝑥 ∈ D (𝑘𝑮 ) 𝑛𝑥 (S ′ ). For each vertex 𝑥 ∈ D (𝑮), we identify the copy in 𝑘𝑮 that contributes the least to the weight of the cover. Formally, we define 𝑖 (𝑥) = arg min 𝑗 ∈ [𝑘 ] {𝑛𝑥 𝑗 (S ′ )} to be the index of the copy of 𝑥 appearing in the fewest bicliques in S ′ . We construct a cover S for 𝑮 by projecting the bicliques of S ′ onto these specific copies. Specifically, for each 𝑆 ′ ∈ S ′ , we construct a set 𝜋 (𝑆 ′ ) = {𝑥 ∈ D (𝑮) | 𝑥𝑖 (𝑥 ) ∈ D (𝑆 ′ )}. We discard any empty sets resulting from this projection. Finally, we set S = {𝜋 (𝑆 ′ ) | 𝑆 ′ ∈ S ′ }. We first verify that S is a valid cover for 𝑮. Consider any edge (𝑢, 𝑣) ∈ 𝑬. By the definition of 𝑘𝑮, the copies 𝑢𝑖 (𝑢 ) and 𝑣𝑖 (𝑣) are connected by an edge in 𝑘𝑮. Therefore, there must be some biclique 𝑆 ′ ∈ S ′ covering the edge {𝑢𝑖 (𝑢 ) , 𝑣𝑖 (𝑣) }. By our construction, 𝑢 and 𝑣 will both be included in 𝜋 (𝑆 ′ ), implying 𝜋 (𝑆 ′ ) covers the edge (𝑢, 𝑣). Furthermore, it is easy to check that for all 𝑆 ′ ∈ S ′ , the subgraph 𝜋 (𝑆 ′ ) is a biclique in 𝑮, since 𝑆 ′ is a biclique in 𝑘𝑮, by definition. Thus, every 𝑆 ∈ S is a biclique, and S is a valid biclique cover for 𝑮. Now we analyze the cost 𝜇 (S). By definition, for all 𝑥 ∈ D (𝑮), the number of bicliques in S containing 𝑥 (i.e., 𝑛𝑥 (S)) is at most Í 𝑛𝑥𝑖 (𝑥 ) (S ′ ). By our choice of 𝑖 (𝑥), we have 𝑛𝑥𝑖 (𝑥 ) (S ′ ) ≤ 𝑘1 𝑘𝑗=1 𝑛𝑥 𝑗 (S ′ ). Summing over all vertices in 𝑮, we obtain: 𝑘

∑︁

𝜇 (S) =

𝑛𝑥𝑖 (𝑥 ) (S ′ ) ≤

𝑥 ∈ D (𝑮 )

1 = 𝑘

∑︁ 𝑥 ∈ D (𝑮 )

1 ∑︁ 𝑛𝑥 (S ′ ) 𝑘 𝑗=1 𝑗

1 © ∑︁ ª 𝑛𝑥 (S ) ≤ ­ 𝑛𝑥 (S ′ ) + 𝑐 |S ′ | ® 𝑘 𝑥 ∈ D (𝑘𝑮 ) «𝑥 ∈ D (𝑘𝑮 ) ¬ ∑︁

′

1 1 𝑐𝑚 = 𝜎 (S ′ ) ≤ (𝑘𝜏 + 𝑐𝑚) = 𝜏 + . 𝑘 𝑘 𝑘 Since 𝜇 (S) must be an integer (as it is a sum of vertex counts) and we chose 𝑘 > 𝑐𝑚, we have 𝑐𝑚 𝑘 < 1. This implies 𝜇 (S) ≤ 𝜏, and the result follows. □ Theorem B.2. For any fixed integer 𝑐 ≥ 0, the dGWBC problem is NP-complete. Proof. First, we observe that dGWBC is in NP. Given a collection of subgraphs, we can verify in polynomial time whether each subgraph is a biclique, whether they cover all edges in 𝑬, and whether the total cost 𝜎 is at most the given threshold. Next, we show NP-hardness. We choose 𝑘 = 𝑐𝑚 + 1 (so that we have 𝑘 > 𝑐𝑚). Since 𝑚 ≤ 𝑛 2 we have that 𝑘 is bounded by a polynomial in 𝑛. Consequently, the constructed graph 𝑘𝑮, which has 𝑘 · 𝑛 vertices, has size polynomial in the size of the input graph 𝑮. By Lemma B.1, the instance of dWBC has a solution with cost at most 𝜏 if and only if the instance of dGWBC has a solution with cost at most 𝑘𝜏 + 𝑐𝑚. □

C Missing details from Section 3 C.1 Algorithm for the 𝑐-densest subgraph problem We first review the exact algorithm for the densest subgraph problem. Given 𝑮, Goldberg [33] created a max-flow instance to check E (𝑋 ) | whether there exists a subgraph 𝑋 such that ||D (𝑋 ) | ≥ 𝛾, for any real number 𝛾. They construct the directed graph 𝐺 ′ (𝑉 ′, 𝐸 ′ ) such that 𝑉 ′ = 𝑽 ∪ 𝑼 ∪ {𝑠, 𝑡 }, where 𝑠 is the source and 𝑡 is the Ð Ð sink node. Furthermore 𝐸 ′ = 𝑬 ∪ ( 𝑣 ∈𝑽 (𝑠, 𝑣)) ∪ ( 𝑢 ∈𝑼 (𝑠, 𝑢)) ∪ Ð Ð ( 𝑣 ∈𝑽 (𝑣, 𝑡)) ∪ ( 𝑢 ∈𝑼 (𝑢, 𝑡)). Each edge (𝑣, 𝑢) ∈ 𝑬, with 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 , is replaced by two directed edges (𝑣, 𝑢) and (𝑢, 𝑣), each of capacity 1. The capacity of each edge (𝑠, 𝑣) (or (𝑠, 𝑢)) is deg(𝑣) (or deg(𝑢)), and the capacity of each edge (𝑣, 𝑡) (or (𝑢, 𝑡)) is 2𝛾, where deg(𝑣) is the degree of node 𝑣 in graph 𝑮. Let 𝑋¯ be the subgraph of 𝑮 such that D (𝑋¯ ) = (𝑽 ∪ 𝑼 ) \ D (𝑋 ) and E (𝑋¯ ) = {(𝑢, 𝑣) ∈ 𝑬 | 𝑣 ∈ V (𝑋¯ ), 𝑢 ∈ U (𝑋¯ )}. Let also E (𝑋, 𝑋¯ ) be the edges in 𝑬 between nodes in D (𝑋 ) and D (𝑋¯ ). They show that Í E (𝑋 ) | ¯ i) ||D 𝑣 ∈ D (𝑋¯ ) deg(𝑣) + |E (𝑋, 𝑋 )| + 2𝛾 |D (𝑋 )| ≤ 2|𝑬 |, (𝑋 ) | ≥ 𝛾 ⇔ ′ and ii) the cost of the 𝑠-𝑡 cut of 𝐺 defined by the nodes D (𝑋 ) in the Í 𝑠 side and nodes D (𝑋¯ ) in the 𝑡 side is exactly 𝑣 ∈ D (𝑋¯ ) deg(𝑣) + |E (𝑋, 𝑋¯ )| + 2𝛾 |D (𝑋 )|. Hence by the max-flow min-cut theorem, they compute a max-flow on 𝐺 ′ and if its value is at most 2|𝐸| and 𝑋 ≠ ∅ then they run their procedure for a larger value of 𝛾. Otherwise, they run their procedure for smaller values of 𝛾. By running a binary search on the values of 𝛾 they get the densest subgraph from 𝑮, which is the subgraph 𝑋 returned in the last step of the binary search where the cost of the 𝑠-𝑡 min-cut was at most 2|𝑬 | and 𝑋 ≠ ∅. For the 𝑐-densest subgraph problem, we have a similar construction. In fact, the graph 𝐺 ′ we compute is exactly the same. We | decide whether there exists a subgraph 𝑋 such that | D| E(𝑋(𝑋) )|+𝑐 ≥ | 𝛾. Following the analysis in [32, 33] we get | D| E(𝑋(𝑋) )|+𝑐 ≥ 𝛾 ⇔ Í ¯ 𝑣 ∈ D (𝑋¯ ) deg(𝑣) + |E (𝑋, 𝑋 )| +2𝛾 |D (𝑋 )| ≤ 2|𝑬 | −2𝛾 ·𝑐. We compute a max-flow on 𝐺 ′ and if its value is at most 2|𝐸| − 2𝛾 · 𝑐 then we run our procedure for a larger value of 𝛾. Otherwise, we run our

Aryan Esmailpour, Khoi Le, and Stavros Sintos

procedure for smaller values of 𝛾. We note that we can also run a binary search on 𝛾 since the function © ∑︁ ª 𝑓 (𝛾) = min ­ deg(𝑣) + |E (𝑋, 𝑋¯ )| + 2𝛾 |D (𝑋 )| ® − 2|𝑬 | + 2𝛾 ·𝑐 𝑋 ⊆𝐺 ¯ «𝑣 ∈ D ( 𝑋 ) ¬ is a non-decreasing function. Overall, notice that 𝛾 can take 𝑂 (|𝑬 | · (|𝑽 | + |𝑼 |)) different values so the binary search executes 𝑂 (log(max{|𝑽 |, |𝑼 |, 𝑐})) steps. In each step of the binary search a maximum flow is computed on 𝐺 ′ that contains 𝑂 (|𝑽 | + |𝑼 |) nodes and 𝑂 (|𝑬 |) edges. Using [54], the max-flow (min 𝑠-𝑡 cut) on 𝐺 ′ is computed in 𝑂 ((|𝑽 | + |𝑼 |)|𝑬 |) time. Using the recent breakthrough of the max-flow problem [19], we can compute the max-flow in each iteration of the binary search in |𝑬 | 1+𝑜 (1) time. Next, we consider the approximation algorithm. Chekuri et al. [18] consider the problem of maximizing 𝑔 (||ED(𝑋(𝑋))| | ) and show that the greedy peeling algorithm gives a 1/3-approximation in linear time when 𝑔 is concave and satisfies 𝑔(0) = 0. Their analysis uses the assumption 𝑔(0) = 0 to establish that 𝑡/𝑔(𝑡) is nondecreasing. In our case, 𝑔(𝑡) = 𝑡 + 𝑐 does not satisfy 𝑔(0) = 0 when 𝑐 > 0; 𝑡 however, 𝑔 (𝑡𝑡 ) = 𝑡 +𝑐 is nondecreasing for every 𝑐 ≥ 0. Hence, the same analysis applies and yields an 𝑂 (1)-approximation for the 𝑐-densest subgraph problem. Putting everything together, we conclude with Lemma 3.1.

Interval bipartite graphs. A graph 𝑮 (𝑽, 𝑼 , 𝑬, I𝑉 , I𝑈 ) is an interval bipartite graph if for every 𝑣 ∈ 𝑽 (resp. 𝑢 ∈ 𝑼 ), 𝑣 is associated with an interval 𝐼 𝑣 = [𝐼 𝑣− , 𝐼 𝑣+ ] ∈ I𝑉 (resp. 𝑢 is associated with𝐼𝑢 = [𝐼𝑢− , 𝐼𝑢+ ] ∈ I𝑈 ) and (𝑣, 𝑢) ∈ 𝑬 if and only if 𝐼 𝑣 ∩ 𝐼𝑢 ≠ ∅. Notice that this is an intersection bipartite graph in R1 . Hence, the next theorem follows directly from Theorem 4.1. Theorem D.1. Given an interval bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬, I𝑉 , I𝑈 ) such that 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 | (and without loss of generality 𝑛𝑉 ≤ 𝑛𝑈 ), and |𝑬 | = 𝑚, there exists an 𝑂 (log(𝑛𝑈 ) · log2 (𝑛𝑉 ))-approximation algorithm for the GWBC (and WBC) problem for any 𝑐 ≥ 0, that runs in 𝑂 (𝑛𝑉 · (𝑛𝑈 + 𝑚) · 𝑚 · log(𝑛𝑉 )) time. 𝑘-NN bipartite graphs. A graph 𝑮 (𝑽, 𝑼 , 𝑬, 𝑘) is a 𝑘-NN bipartite graph in R𝑑 if (𝑣, 𝑢) ∈ 𝑬 if and only if 𝑢 is one of the 𝑘-nearest neighbors of 𝑣 in 𝑼 and 𝑣 is one of the 𝑘-nearest neighbors of 𝑢 in 𝑽 . We assume that there are no ties in the 𝑘-nearest-neighbor distances; ties can be handled by a consistent arbitrary perturbation. For every 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 , let 𝑅𝑣 = 𝜓 ∞ (𝑣, k-NN(𝑣, 𝑼 )) respectively. Hence, (𝑣, 𝑢) ∈ 𝑬

𝜌b𝑢 = (−∞, 𝑟𝑢(1)+ ] × · · · × (−∞, 𝑟𝑢(𝑑 )+ ] × [𝑟𝑢(1) − , ∞) × · · · × [𝑟𝑢(𝑑 ) − , ∞). (6)

Indeed, the two hyper-rectangles 𝑟 𝑣 and 𝑟𝑢 intersect if and only if, for every coordinate 𝑗 ∈ [𝑑], the intervals [𝑟 𝑣( 𝑗 ) − , 𝑟 𝑣( 𝑗 )+ ] and [𝑟𝑢( 𝑗 ) − , 𝑟𝑢( 𝑗 )+ ] intersect. This is equivalent to 𝑟 𝑣( 𝑗 ) − ≤ 𝑟𝑢( 𝑗 )+

and

𝑟 𝑣( 𝑗 )+ ≥ 𝑟𝑢( 𝑗 ) −

for every 𝑗 ∈ [𝑑]. Equivalently, 𝑟 𝑣(1) − ∈ (−∞, 𝑟𝑢(1)+ ], . . . , 𝑟 𝑣(𝑑 ) − ∈ (−∞, 𝑟𝑢(𝑑 )+ ], 𝑟 𝑣(1)+ ∈ [𝑟𝑢(1) − , ∞), . . . , 𝑟 𝑣(𝑑 )+ ∈ [𝑟𝑢(𝑑 ) − , ∞), which, by the definition of 𝑝 𝑣 , is precisely 𝑝 𝑣 ∈ 𝜌b𝑢 . Hence Equation (6) holds. Now consider the 𝑖-th iteration of the greedy procedure and let Ù 𝑦= 𝜌b𝑢 . 𝑢 ∈ U (𝑆𝑖∗ )

Since 𝑆𝑖∗ is a biclique, for every 𝑣 ∈ V (𝑆𝑖∗ ) and every 𝑢 ∈ U (𝑆𝑖∗ ) we have 𝑟 𝑣 ∩ 𝑟𝑢 ≠ ∅. By Equation (6), 𝑝 𝑣 ∈ 𝜌b𝑢 for every 𝑢 ∈ U (𝑆𝑖∗ ). Therefore, {𝑝 𝑣 | 𝑣 ∈ V (𝑆𝑖∗ )} ⊆ 𝑦. Since 𝑦 is a hyper-rectangle in R2𝑑 , all steps of the proof of Lemma 3.2 follow almost verbatim, with 𝑂 (log2𝑑 𝑛𝑉 ) canonical hyper-rectangles instead of 𝑂 (log𝑑 𝑛𝑉 ).

𝑑 Ö

[𝑢 ( 𝑗 ) − 𝑅𝑢 , 𝑢 ( 𝑗 ) + 𝑅𝑢 ] ×

𝑗=1

𝑑 Ö

(−∞, 𝑢 ( 𝑗 ) ] ×

𝑗=1

𝑑 Ö

[𝑢 ( 𝑗 ) , ∞).

𝑗=1

By construction, 𝑝 𝑣 ∈ 𝜌𝑢 if and only if, for every 𝑗 ∈ [𝑑], 𝑢 ( 𝑗 ) − 𝑅𝑢 ≤ 𝑣 ( 𝑗 ) ≤ 𝑢 ( 𝑗 ) + 𝑅𝑢

We show that for every 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 , 𝑝 𝑣 ∈ 𝜌b𝑢 .

𝜓 ∞ (𝑣, 𝑢) ≤ 𝑅𝑣 and 𝜓 ∞ (𝑣, 𝑢) ≤ 𝑅𝑢 .

𝑝 𝑣 = 𝑣 (1) , . . . , 𝑣 (𝑑 ) , 𝑣 (1) − 𝑅𝑣 , . . . , 𝑣 (𝑑 ) − 𝑅𝑣 , 𝑣 (1) + 𝑅𝑣 , . . . , 𝑣 (𝑑 ) + 𝑅𝑣 .

𝜌𝑢 =

For intersection bipartite graphs we extend the proof of Lemma 3.2. We first recall why the transformation to R2𝑑 preserves the edge relation. For every 𝑢 ∈ 𝑼 , define

⇐⇒

⇐⇒

We map every 𝑣 ∈ 𝑽 to a point 𝑝 𝑣 ∈ R3𝑑 defined as For every 𝑢 ∈ 𝑼 , we define the hyper-rectangle 𝜌𝑢 ⊆ R3𝑑 as

D Missing details from Section 4 D.1 Extension to other graph structures

𝑟 𝑣 ∩ 𝑟𝑢 ≠ ∅

𝑅𝑢 = 𝜓 ∞ (𝑢, k-NN(𝑢, 𝑽 )),

and

and 𝑣 ( 𝑗 ) − 𝑅𝑣 ≤ 𝑢 ( 𝑗 ) ≤ 𝑣 ( 𝑗 ) + 𝑅𝑣 . These conditions are equivalent to 𝜓 ∞ (𝑣, 𝑢) ≤ 𝑅𝑢

and

𝜓 ∞ (𝑣, 𝑢) ≤ 𝑅𝑣 ,

⇐⇒

𝑝 𝑣 ∈ 𝜌𝑢 .

respectively. Therefore, (𝑣, 𝑢) ∈ 𝑬

(7)

We can now apply the algorithm from Section 3.2.3 in R3𝑑 . The correctness and approximation analysis now follow from Lemma 3.2. In particular, for the biclique 𝑆𝑖∗ used in the 𝑖-th iteration of that proof, let Ù 𝑦= 𝜌𝑢 . 𝑢 ∈ U (𝑆𝑖∗ ) ∗ Since 𝑆𝑖 is a biclique, Equation (7) implies that {𝑝 𝑣 | 𝑣 ∈ V (𝑆𝑖∗ )} ⊆ 𝑦. Since 𝑦 is a hyper-rectangle in R3𝑑 , it can be decomposed into

𝑂 (log3𝑑 𝑛𝑉 ) canonical hyper-rectangles. Thus, all steps of the proof of Lemma 3.2 follow verbatim, with 𝑂 (log3𝑑 𝑛𝑉 ) canonical hyperrectangles instead of 𝑂 (log𝑑 𝑛𝑉 ).

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

Theorem D.2. Given a 𝑘-NN bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬, 𝑘) in R𝑑 , where 𝑑 = 𝑂 (1), such that 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 | (and without loss of generality 𝑛𝑉 ≤ 𝑛𝑈 ), and |𝑬 | = 𝑚, there exists an 𝑂 log(𝑛𝑈 ) ·
log3𝑑 (𝑛𝑉 ) -approximation algorithm for the GWBC (and WBC) problem for any 𝑐 ≥ 0. The algorithm runs in 𝑂 𝑛𝑉 · (𝑛𝑈 + 𝑚) · 𝑚 ·
log3𝑑 −1 (𝑛𝑉 ) time.

D.2

Extension to any ℓ𝛼𝑑 metric: Theoretical approach

We first define the notion of an 𝜀-biclique. Given a graph 𝑮 and an arbitrarily small constant 𝜀 ∈ (0, 1), let 𝑮 ′ (𝑽 ′, 𝑼 ′, 𝑬 ′ ) be a graph where 𝑽 ′ = 𝑽 , 𝑼 ′ = 𝑼 , and 𝑬 ′ = {(𝑣, 𝑢) | 𝜓𝛼 (𝑣, 𝑢) ≤ (1 + 𝜀)𝛿 }. Note that 𝑬 ′ contains all edges of 𝑮, as well as additional pairs (𝑣, 𝑢) with distance greater than 𝛿 but at most (1 + 𝜀)𝛿. An 𝜀-biclique 𝑆 ′ of 𝑮 is defined as any biclique of the graph 𝑮 ′ . Observe that every biclique of 𝑮 is also an 𝜀-biclique. An 𝜀-biclique edge cover S is a collection of 𝜀-bicliques whose union covers all edges of 𝑮. Instead of a range tree, we use the construction and properties of the BBD-tree [5, 6]. A BBD-tree is a hierarchical geometric data structure designed for range aggregation queries in R𝑑 , where 𝑑 = 𝑂 (1). Let T ′ denote the BBD-tree constructed over 𝑽 . The BBD-tree induces a collection C of 𝑂 (|𝑽 | log |𝑽 |) canonical axisaligned hyper-rectangles.1 For any convex region 𝜌 ⊆ R𝑑 , there exists a subset 𝐶 (𝜌) ⊆ C of 𝑂 (𝜀 −𝑑 +log |𝑽 |) pairwise disjoint hyperÐ rectangles such that 𝑽 ∩𝜌 ⊆ 𝑥 ∈𝐶 (𝜌 ) (𝑽 ∩𝑥) ⊆ 𝑽 ∩(⊕𝜀 𝜌). Here, ⊕𝜀 𝜌 denotes the Minkowski sum of 𝜌 with a ball of radius 𝜀 · radius(𝜌), that is, the region obtained by expanding 𝜌 by 𝜀 · radius(𝜌) in all directions, where radius(𝜌) denotes the radius of 𝜌. As in the range

tree construction, we assume without loss of generality that each hyper-rectangle 𝑥 ∈ C is minimal with respect to 𝑽 . The algorithm for general ℓ𝛼𝑑 metrics closely follows the algorithm from Theorem 3.4, with the following modifications: (i) the hash table 𝐵 is defined over all pairs (𝑣, 𝑢) with 𝑣 ∈ 𝑽 and 𝑢 ∈ 𝑼 ; (ii) we use a BBD-tree T ′ to get C constructed over 𝑽 ; and (iii) in each iteration, for every hyper-rectangle 𝑥 ∈ C, we define a graph 𝐺𝑥 (𝑉𝑥 , 𝑈𝑥 , 𝐸𝑥 ) where 𝑉𝑥 = 𝑽 ∩ 𝑥, 𝑈𝑥 = {𝑢 ∈ 𝑼 | 𝑥 ∩ 𝑽 ⊆ ⊕𝜀 𝜌𝑢 }, and 𝐸𝑥 = {(𝑣, 𝑢) | 𝑣 ∈ 𝑉𝑥 , 𝑢 ∈ 𝑈𝑥 , 𝜓𝛼 (𝑣, 𝑢) ≤ (1 + 𝜀)𝛿, 𝐵(𝑣, 𝑢) = 1}. Using the same arguments as in the correctness proof of Lemma 3.2, while accounting for the multiplicative (1 + 𝜀) approximation and the covering guarantees of the BBD-tree, it is straightforward to show that the algorithm returns an 𝜀-biclique edge cover S satisfying 𝜎 (S) ≤ 𝑂 ((𝜀 −𝑑 + log 𝑛𝑉 ) log 𝑛𝑈 ) · 𝜎 (S ∗ ), where S ∗ denotes an optimal biclique edge cover of 𝑮. We emphasize that S ∗ is not an optimal 𝜀-biclique cover. Skipping the remaining details, we conclude with the following theorem. Theorem D.3. Given a 𝛿-disk bipartite graph 𝑮 (𝑽, 𝑼 , 𝑬) in ℓ𝛼𝑑 , where 𝑑 = 𝑂 (1) and 𝛼 ≥ 1, 𝑛𝑉 = |𝑽 |, 𝑛𝑈 = |𝑼 | (with 𝑛𝑉 ≤ 𝑛𝑈 ), and |𝑬 | = 𝑚, there exists an algorithm that returns an 𝜀-biclique edge cover S such that 𝜎 (S) ≤ 𝑂 ((𝜀 −𝑑 +log 𝑛𝑉 ) log 𝑛𝑈 ) ·𝜎 (S ∗ ), where S ∗ is an optimal solution to the GWBC problem for any 𝑐 ≥ 0. The algorithm runs in 𝑂 (𝑛𝑉3 𝑛𝑈2 log 𝑛𝑉 ) time and uses 𝑂 (𝑛𝑉 𝑛𝑈 + 𝑛𝑉 log 𝑛𝑉 ) space. 1 A hyper-rectangle in the canonical set of a BBD-tree may contain a hole; that is,

each region 𝑥 ∈ C can be represented as the difference of two hyper-rectangles. For simplicity, we treat each such region 𝑥 as a standard hyper-rectangle, since all properties and arguments we claim remain unchanged.

E

Additional experiments

Aryan Esmailpour, Khoi Le, and Stavros Sintos

Result

4

6

2 0

Gamma 1e6

BaselineAMBEA BaselineRole RT-BC

2 0.05

0.10

0.15

0.20

0.25

BaselineAMBEA BaselineRole RT-BC

6

4

POPSIM 6 Result

BaselineAMBEA BaselineRole RT-BC

6

Result

8

Credits 8 1e6

Result

Adults 1e6

4 2

0.002 0.003 0.004 0.005 0.006

0.13

0.14

0.15

0.16

BaselineAMBEA BaselineRole RT-BC

4 2 0

0.17

1e6

0.04

0.06

0.08

0.10

0.12

10000

40000 30000

20000

BaselineAMBEA BaselineRole RT-BC

20000 10000

15000 10000 5000

00.002 0.003 0.004 0.005 0.006

0.05 0.10 0.15 0.20 0.25

BaselineAMBEA BaselineRole RT-BC

Memory (MB)

20000

BaselineAMBEA BaselineRole RT-BC

Memory (MB)

30000

Memory (MB)

Memory (MB)

(a) Size of representation

40000 30000

BaselineAMBEA BaselineRole RT-BC

20000 10000

0.13 0.14 0.15 0.16 0.17

0.04 0.06 0.08 0.10 0.12

2500 2000 1500

3000

BaselineAMBEA BaselineRole RT-BC

Time (s)

12500 BaselineAMBEA 10000 BaselineRole RT-BC 7500 5000 2500 0 0.002 0.003 0.004 0.005 0.006

Time (s)

BaselineAMBEA 4000 BaselineRole RT-BC 3000 2000 1000 0 0.05 0.10 0.15 0.20 0.25

Time (s)

Time (s)

(b) Peak memory in MB

1000 500 0.13 0.14 0.15 0.16 0.17

BaselineAMBEA BaselineRole RT-BC

2000 1000

0 0.04 0.06 0.08 0.10 0.12

(c) Running time in seconds 𝑑 across all datasets Figure 5: Experimental results for WBC in ℓ∞

250 200 150

BaselineAMBEA BaselineRole RT-BC

1000 Time (s)

300

Gamma

800

Time (s)

BaselineAMBEA BaselineRole RT-BC

350 Time (s)

Credits

600 400

100

200

300 c

400

500

100

200

300 c

400

500

POPSIM

BaselineAMBEA BaselineRole RT-BC

800 700 600 500 400 100

200

300 c

BaselineAMBEA BaselineRole RT-BC

2000 Time (s)

Adults

400

500

(a) Running time in seconds 𝑑 across all datasets Figure 6: Experimental results for GWBC in ℓ∞

1500 1000 500

100

200

300 c

400

500

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

Dataset

𝛿 𝑚 𝑛 𝑑 Grouping Attribute 0.05 64, 280 0.1 854,381 Adults 0.15 2,589,297 14,846 5 Sex 0.2 5,990,399 0.25 8,714,044 0.002 1,538,057 0.003 2,912,661 Credit 0.004 4,437,255 28,726 6 Sex 0.005 6,034,989 0.006 7,805,033 0.13 1,511,959 0.14 1,961,614 Gamma 0.15 2,477,054 18,905 10 Class 0.16 3,057,096 0.17 3,702,052 0.04 1,753,508 0.06 3,090,592 POPSIM 0.08 4,328,986 8,591 2 Race 0.1 5,442,100 0.12 6,449,440 𝑑. Table 3: Statistics of the 𝛿-disk graphs used in our experiments for ℓ∞

Related documents

• Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers#659317
• Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers#657181
• On graphs with a unique minimum hull set#490208
• Retained-Set Descent for Diagonal Ramsey Numbers#1084471
• On a problem concerning $\mathbb Z_3$-Ramsey numbers#1064332