Source-linked AI summary
Parallel Maximum Clique Algorithms with Applications to Network Analysis and Storage
Ryan A. Rossi, David F. Gleich, Assefaw H. Gebremedhin, Md. Mostofa Ali Patwary
TL;DR
Finding maximum cliques is computationally hard, yet large social and information networks make fast exact analysis valuable. This paper develops a parallel branch-and-bound solver with aggressive pruning and applies it to network analysis and compression. It reports roughly linear runtime scaling and finds a maximum clique in a social network with nearly two billion edges in about 20 minutes.
Problem
Maximum clique is NP-hard even to approximate, raising concern that exact algorithms may be impractical for large-network analysis.
Source: §1 · p. 1Method
The paper proposes an exact parallel branch-and-bound clique finder that uses heuristic cliques, upper bounds, and aggressive pruning.
Source: §1 · p. 1Results
Takeaways & Limitations
The solver is applied to temporal strong components and to create a clique-based ordering for graph compression.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We propose a fast, parallel maximum clique algorithm for large sparse graphs that is designed to exploit characteristics of social and information networks. The method exhibits a roughly linear runtime scaling over real-world networks ranging from 1000 to 100 million nodes. In a test on a social network with 1.8 billion edges, the algorithm finds the largest clique in about 20 minutes. Our method employs a branch and bound strategy with novel and aggressive pruning techniques. For instance, we use the core number of a vertex in combination with a good heuristic clique finder to efficiently remove the vast majority of the search space. In addition, we parallelize the exploration of the search tree. During the search, processes immediately communicate changes to upper and lower bounds on the size of maximum clique, which occasionally results in a super-linear speedup because vertices with large search spaces can be pruned by other processes. We apply the algorithm to two problems: to compute temporal strong components and to compress graphs.
1. INTRODUCTION
The paper presents an exact parallel maximum-clique finder for large social and information networks, then applies it to temporal strong components and graph compression. Its motivation is that real-world graph structure may let well-designed exact algorithms avoid worst-case behavior despite the problem’s hardness.
1. INTRODUCTION
- A maximum clique in a social network with nearly two billion edges is found in about 20 minutes, with roughly linear empirical runtime scaling.The solver significantly outperforms the authors’ earlier finder [39] and an off-the-shelf clique enumerator.Source: §1 · p. 1
- The exact solver uses branch and bound with aggressive pruning, beginning with a heuristic clique and upper bounds on the graph or individual neighborhoods.It also uses implicit graph edits, periodic updates, and a tunable implementation; workers immediately share upper and lower bounds, sometimes enabling super-linear speedup.Source: §1 · p. 1
- The method is applied to temporal strong components, whose computation is NP-complete and can be reduced to finding a maximum clique in a temporal reachability graph.The paper discusses components found in Twitter and phone-call networks.Source: §1 · pp. 1–2
- For graph compression, the authors use cliques to create an ordering that makes many edges local, reporting results nearly as good as heuristics designed specifically for compression.This addresses an easier problem than compression itself.Source: §1 · pp. 1–2
2. CLIQUES IN SOCIAL AND INFORMATION NETWORKS
The section evaluates clique finding and clique structure across social and information networks. It reports that the initial heuristic often finds the maximum clique and that the relationship between largest cores and cliques varies across network types.
2. CLIQUES IN SOCIAL AND INFORMATION NETWORKS
- The study considers 32 networks in eight broad classes, with an appendix covering about 74 social and information networks; the reported runtime plot shows linear scaling from 1,000 to 100 million vertices.For these analyses, the authors discard edge weights and self-loops, keep the largest strongly connected component, and remove non-reciprocated directed edges.Source: §2 · p. 2, Figure 1 · p. 3
- 17 of 32 networks, and 52 of 74 appendix networks, have their largest clique found by the initial heuristic.The authors report that this often helps the exact algorithm terminate quickly.Source: §2 · p. 3
- In collaboration and most web-link networks, the largest k-core is a maximum clique, while social networks show a larger difference between the two.The authors suggest this may reflect a fundamental difference between collaboration and social relationships.Source: §2 · p. 3
- Technological networks have surprisingly large cliques, while the largest Twitter clique combines spam and legitimate high-follower accounts.The authors suggest the Twitter clique members likely reciprocate all follower relationships.Source: §2 · p. 3
3. BOUNDS ON MAXIMUM CLIQUE SIZE
The section develops upper bounds on maximum clique size that support early termination and pruning. It combines graph-wide bounds with bounds on reduced neighborhoods, with total work for the latter bounded by the number of edges and triangles.
3. BOUNDS ON MAXIMUM CLIQUE SIZE
- A clique of size k requires every vertex to have degree k−1, so the largest core number K(G) gives the upper bound K(G) + 1 on clique size.Core numbers can be computed in linear time.Source: §3 · p. 3
- Greedy coloring in degeneracy order gives a potentially tighter clique-size upper bound L(G), with L(G) ≤ K(G) + 1.The passage states that this bound can be computed in linear time with careful implementation.Source: §3 · p. 3
- Applying clique-size bounds to each reduced neighborhood graph supports pruning vertices that cannot belong to a maximum clique.The reduced neighborhood contains a vertex and its neighbors not yet removed; the figure summary identifies networks where the largest core number tightly bounds the largest clique.Source: §3 · pp. 3–4, Figure 2 · p. 3
- Computing the bounds across all neighborhood graphs takes O(|E| + |T|) total work, where |T| is the number of triangles.The passage counts O(|E|) vertices and O(|E| + |T|) edges across those neighborhoods.Source: §3 · p. 4
4. MAXIMUM CLIQUE ALGORITHMS
The algorithm combines heuristic clique finding, core-based pruning, and bounded branch-and-bound search, then parallelizes neighborhood exploration with workers sharing updated bounds. These steps are paired with efficient graph updates and ordering choices to reduce search work.
4. MAXIMUM CLIQUE ALGORITHMS
- The exact solver improves on earlier pruning by using tight clique bounds and adds parallelism and other optimizations.It maintains a best clique, prunes vertices and neighborhoods that cannot contain a larger one, and searches each remaining neighborhood.Source: §4 · p. 4, §4.3 · p. 5
4.1 Our fast heuristic clique finder
- The heuristic greedily builds cliques around vertices in degeneracy order, using core numbers to guide and prune the search.It can itself find the maximum clique in over half of the social networks considered.Source: §4.1 · p. 4
4.2 Initial pruning
- A heuristic clique of size |H| lets the solver remove vertices whose core numbers are below |H|, sometimes certifying optimality and reducing memory use.The paper reports this certification for the LiveJournal network.Source: §4.2 · p. 4
4.4 Performance Optimization
- Implicit deletion marks and periodic graph rebuilds support efficient graph updates; the implementation also uses fast neighborhood intersections and O(1) edge checks on small graphs.The authors say periodic rebuilds reduce intersection costs and may improve cache locality.Source: §4.3 · p. 5, §4.4 · p. 6
4.3 Searching
- The search tests degree, neighborhood-core, and coloring bounds before recursively exploring candidate cliques.It processes vertices by increasing reduced degree and removes each vertex after its neighborhood search finishes.Source: §4.3 · p. 5
4.5 Parallelization
- Workers explore neighborhoods in parallel and broadcast improved clique bounds, allowing other workers to terminate searches early and sometimes yielding superlinear speedup.The shared-memory implementation also uses global arrays and locked updates to reduce communication.Source: §4.5 · p. 6
5. PERFORMANCE RESULTS
On social and information networks, pmc solves all tested instances and substantially outperforms the compared clique finders. Its parallel speedups vary by benchmark type, while neighborhood-core bounds help on difficult DIMACS instances.
Benchmark scope
- The 20-year-old DIMACS clique challenge provides an established difficult benchmark: its graphs are small (45–1500 vertices) yet contain enormous numbers of edges and triangles compared with social networks.Source: §5 · p. 6
Social and information networks
- pmc solves all 30 difficult social and information networks, runs over 1000 times faster than BK on some problems, and is about 50 times faster than FMC.Figure 6 compares a serial pmc version and its variants with three existing algorithms.Source: Figure 6 · p. 7, §5 · p. 7
Parallel speedup
- Social-network speedups are mild on 16 cores for the largest problem, while DIMACS speedups are roughly linear and sometimes superlinear.The authors attribute superlinear performance to quicker returns from unfruitful branches during parallel exploration.Source: §5 · p. 7
Performance profiles
- The performance profiles summarize how many test problems each solver handles within a given speed factor of the best solver.The paper notes that BK solves around 80% of the Figure 6 test set.Source: §5 · p. 7
Neighborhood-core bounds
- Neighborhood cores greatly reduce work in most hard DIMACS cases serially, and in parallel are never worse than about 1.44 times the fastest method.The performance profiles compare versions with and without neighborhood cores; the serial variant incurs a large work increase in a few cases.Source: Figure 7 · p. 7, §5 · pp. 7–8
6. MAXIMUM CLIQUE APPLICATIONS
This section applies maximum-clique search to temporal strong components and graph compression. It reports fast component identification and compares clique-based compression ordering with native and LLP orderings.
6.1 Temporal strong components
- A temporal strong component is found by turning temporal reachability into a graph, removing non-reciprocated edges, and finding a maximum clique.The resulting clique is the largest set whose pairs have temporal paths between them.Source: §6.1 · p. 8
- All tested temporal networks’ largest components were identified in under a second after reachability-network construction.The result applies after computing the reachability network.Source: §6.1 · p. 8
- Contact-network components were about 100 vertices; interaction-network components were roughly 20–30% of nodes, while retweet components were smaller than those in symmetric networks.The authors suggest the similar contact-network sizes may reflect different collection periods; they identify the components as candidate community centers and note possible relevance to seeded viral campaigns.Source: §6.1 · pp. 8–9
6.2 Ordering for network compression
- Clique-based ordering compressed two Facebook graphs better than native order and comparably to, though slightly worse than, LLP (Table 3).The ordering repeatedly removes large cliques and sorts vertices within each clique by degree.Source: §6.2 · p. 9, Table 3 · p. 9
7. RELATED WORK
Prior work has studied exact maximum-clique algorithms and maximal-clique enumeration, including approaches tailored to social and information networks. This paper distinguishes its focus on fast maximum-clique solving and temporal strong components.
7. RELATED WORK
- Unlike maximal-clique enumeration work, this paper emphasizes fast maximum-clique solving for social and information networks and temporal strong components.The related work notes that enumeration has received more attention in data mining and cites Du et al. as exploiting network properties to enumerate maximal cliques faster.Source: §7 · p. 9
- Most prior exact maximum-clique work was sequential; cited parallel approaches include a multithreaded method without core-number pruning [33] and a MapReduce method.The review also points to exact-algorithm reviews and computational studies [40].Source: §7 · p. 9
8. CONCLUSIONS
The paper concludes that its algorithm finds maximum cliques on billion-edge social networks in minutes and scales linearly across the tested graph range. It applies the method to temporal strong components and graph compression.
8. CONCLUSIONS
- The algorithm finds maximum cliques on billion-edge social networks in minutes and exhibits linear runtime scaling from 1,000 to 100 million vertices.The applications include finding largest temporal strong components through a static reachability graph and producing a graph-compression-friendly ordering.Source: §8 · p. 9