Introduction
Finding the heaviest interconnected clusters within a network, known as the Maximum Weight Clique Problem (MWCP), is a fundamental challenge in graph theory with applications ranging from social network analysis to bioinformatics. However, as real-world datasets scale to millions of vertices and tens of millions of edges, traditional exact algorithms often fail due to exponential time complexity and memory constraints.
FastWClq is a high-performance algorithm designed specifically for these massive scales. By interleaving greedy clique construction with aggressive graph reduction, it consistently outperforms state-of-the-art solvers in both speed and solution quality, often proving optimality for million-node graphs in less than a second.
The MWCP Challenge in Massive Graphs
The MWCP asks for a subset of vertices where every vertex is connected to every other vertex (a clique), such that the sum of the vertex weights is maximized. While finding a simple clique is computationally straightforward, finding the maximum weight one is NP-hard.
In the era of massive data, we encounter graphs like social networks (e.g., Orkut) or web links (e.g., web-uk-2005) that overwhelm traditional branch-and-bound techniques. Conversely, existing heuristic local search methods can find good solutions but often suffer from slow convergence and an inability to prove optimality. FastWClq addresses these gaps by prioritizing efficiency and aggressive pruning.
Methodology: The FastWClq Approach
FastWClq breaks the traditional "reduce then solve" pipeline by using an iterative loop that integrates construction and reduction.
1. Interleaved Construction and Reduction
The algorithm builds a clique and immediately uses its weight to prune the graph. A smaller graph then facilitates the discovery of even better cliques, creating a virtuous cycle of simplification and optimization. If the graph is eventually reduced to an empty set, the algorithm has mathematically proven that the best clique found is the global optimum.
2. Benefit Estimation Function
To decide which vertex to add to a growing clique, FastWClq employs a novel benefit function $\hat{b}(v)$. This function balances a vertex's own weight (a lower bound) with the weight of its "effective neighborhood" (an upper bound), providing a more effective "look-ahead" than simple greedy selection.
3. Dynamic Best from Multiple Selection (BMS)
Rather than checking every possible vertex or picking one randomly, FastWClq uses a dynamic sampling strategy. It begins with a small sample size ($k$) to maintain speed and exponentially increases $k$ when improvements stall, allowing the search to become increasingly thorough as the search space narrows.
4. Novel Branching-Based Reduction
The authors introduce a new reduction rule ($UB_1$) that calculates a tighter upper bound on the possible weight of any clique containing a specific vertex. By considering whether a clique contains a vertex's heaviest neighbor, the rule allows for much more aggressive pruning than standard neighborhood-weight checks.
Experimental Evaluation
The algorithm was evaluated on 102 massive real-world graphs from the Network Data Repository, including social networks, infrastructure maps, and biological pathways. Since many original benchmarks were unweighted, weights were assigned using a deterministic formula: $w(v_i) = (i \mod 200) + 1$.
Key Results
FastWClq demonstrated superior performance across multiple metrics:
- Solution Quality: FastWClq found better or equal solutions compared to the previous state-of-the-art (LSCC+BMS) on 89 out of 90 large instances. As shown in the detailed results, FastWClq frequently reaches the best-known values (indicated by asterisks) significantly faster than competitors.
- Massive Speedups: On 46 of the graphs, FastWClq proved the optimal solution in an average of 0.902 seconds. For the massive
inf-road-usagraph (24M vertices), it found the solution in just 5.67 seconds, while competing exact solvers failed to provide any result within an hour. - Robustness: Even when competitors were given up to 36 times more processing time (e.g., 3600s for MaxWClq), FastWClq maintained its lead in solution quality.
Conclusion and Future Work
FastWClq proves that for many real-world "power law" graphs, a high-quality clique can be used to delete the vast majority of the graph, enabling rapid optimization. By avoiding computationally expensive techniques like graph coloring in favor of linear-time scans and bit-indicators, the algorithm achieves unprecedented scalability.
Future work may involve refining the reduction rules to be more "complete," allowing for optimality proofs in even more complex cases. Additionally, applying this interleaved framework to other combinatorial problems, such as the Maximum Independent Set, remains a promising avenue for research.
Summary updated