BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs

• URL: http://arxiv.org/abs/2405.04428v2
• Date: Fri, 24 May 2024 09:00:21 GMT
• Title: BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
• Authors: Alexis Baudin, Clémence Magnien, Lionel Tabourier,
• Abstract summary: This article introduces a new algorithm designed for the exhaustive enumeration of maximal bicliques within a bipartite graph. The algorithm, called BBK for Bipartite Bron-Kerbosch, is a new extension to the bipartite case of the Bron-Kerbosch algorithm. It is faster than the state-of-the-art algorithms and allows the enumeration on massive bipartite graphs that are not manageable with existing implementations.
• Score: 0.3277163122167434
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bipartite graphs are a prevalent modeling tool for real-world networks, capturing interactions between vertices of two different types. Within this framework, bicliques emerge as crucial structures when studying dense subgraphs: they are sets of vertices such that all vertices of the first type interact with all vertices of the second type. Therefore, they allow identifying groups of closely related vertices of the network, such as individuals with similar interests or webpages with similar contents. This article introduces a new algorithm designed for the exhaustive enumeration of maximal bicliques within a bipartite graph. This algorithm, called BBK for Bipartite Bron-Kerbosch, is a new extension to the bipartite case of the Bron-Kerbosch algorithm, which enumerates the maximal cliques in standard (non-bipartite) graphs. It is faster than the state-of-the-art algorithms and allows the enumeration on massive bipartite graphs that are not manageable with existing implementations. We analyze it theoretically to establish two complexity formulas: one as a function of the input and one as a function of the output characteristics of the algorithm. We also provide an open-access implementation of BBK in C++, which we use to experiment and validate its efficiency on massive real-world datasets and show that its execution time is shorter in practice than state-of-the art algorithms. These experiments also show that the order in which the vertices are processed, as well as the choice of one of the two types of vertices on which to initiate the enumeration have an impact on the computation time.

Related papers

• PASCO (PArallel Structured COarsening): an overlay to speed up graph clustering algorithms [14.601622103700516]
  Clustering nodes of a graph is a cornerstone of graph analysis. Some popular methods are not suitable for very large graphs. This work introduces PASCO, an overlay that accelerates clustering algorithms.
  arXiv  Detail & Related papers  (2024-12-18T08:15:55Z)
• Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
  In bipartite graph analysis, enumeration of $s$-biplexes is a fundamental problem. In real-world data engineering, finding all $s-biplexes is neither necessary nor computationally affordable. We propose MVBP, that breaks the simple $2n enumeration algorithm. FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.
  arXiv  Detail & Related papers  (2024-09-27T06:23:29Z)
• A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
  We provide an efficient ($epsilon,$delta$)-DP algorithm tailored specifically for such graphs. Our algorithm works for well-clustered graphs with $k$ nearly-balanced clusters.
  arXiv  Detail & Related papers  (2024-03-21T11:57:16Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• Online Correlation Clustering for Dynamic Complete Signed Graphs [9.13755431537592]
  We consider the problem of correlation clustering for dynamic complete signed graphs. Online approximation algorithm in [CALM+21] for correlation clustering is used. This is the first online algorithm for dynamic graphs which allows a full set of graph editing operations.
  arXiv  Detail & Related papers  (2022-11-13T19:36:38Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs [3.2901541059183432]
  We present two-time approximation algorithms for hierarchical clustering. The significance of our work is demonstrated by the empirical analysis on both synthetic and real-world data sets.
  arXiv  Detail & Related papers  (2021-12-16T17:52:04Z)
• Bipartite Graph Embedding via Mutual Information Maximization [8.382665371140503]
  Bipartite graph embedding has attracted much attention due to the fact that bipartite graphs are widely used in various application domains. We propose a bipartite graph embedding called BiGI to capture such global properties by introducing a novel local-global infomax objective. Our model is evaluated on various benchmark datasets for the tasks of top-K recommendation and link prediction.
  arXiv  Detail & Related papers  (2020-12-10T04:03:39Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.