(p,q)-biclique counting and enumeration for large sparse bipartite graphs.

Area of Science:

• Graph Theory and Algorithms
• Computational Mathematics
• Data Mining and Network Analysis

Background:

• Bipartite graphs are fundamental structures in various applications, including network analysis and machine learning.
• Efficiently counting and enumerating bicliques (complete subgraphs) is crucial for tasks like graph neural network (GNN) optimization and densest subgraph detection.
• Existing methods struggle with scalability and efficiency for large, sparse bipartite graphs, lacking effective solutions for biclique enumeration.

Purpose of the Study:

• To develop efficient algorithms for counting and enumerating (p, q)-bicliques in large sparse bipartite graphs.
• To propose an advanced method, BCList++, that improves upon baseline approaches by reducing computational complexity.
• To extend biclique enumeration techniques to uncertain bipartite graphs using an efficient method, IUBCList.

Main Methods:

• Introduced BCList, a branch-and-bound algorithm with pruning techniques for biclique enumeration.
• Developed BCList++, employing a layer-based exploration strategy and a cost model for optimized biclique enumeration.
• Proposed IUBCList, building on BCList++ with pruning techniques for handling uncertain bipartite graphs.

Main Results:

• BCList++ demonstrated significant performance improvements, outperforming baseline methods by up to three orders of magnitude on real-world datasets.
• The cost model in BCList++ effectively guides the selection of computation layers, enhancing efficiency.
• IUBCList achieved substantial speedups, outperforming baseline methods by up to two orders of magnitude on uncertain bipartite graphs.

Conclusions:

• BCList++ provides a scalable and efficient solution for (p, q)-biclique counting and enumeration in large sparse bipartite graphs.
• The developed methods, particularly BCList++ and IUBCList, offer significant advancements in computational graph theory.
• The findings highlight the potential of biclique analysis for optimizing graph neural networks and other complex network applications.