{'fraction_non_alphanumeric': 0.030021569749526786, 'fraction_numerical': 0.00981643702953735, 'mean_word_length': 4.482142857142857, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
n-Level Graph Partitioning

We present a multi-level graph partitioning algorithm based on the extreme idea to contract only a single edge on each level of the hierarchy. This obviates the need for a matching algorithm and promises very good partitioning quality since there are very few changes between two levels. Using an efficient data structure and new flexible ways to break local search improvements early, we obtain an algorithm that scales to large inputs and produces the best known partitioning results for many inputs. For example, in Walshaw's well known benchmark tables we achieve 155 improvements dominating the entries for large graphs.


Introduction
Many important applications of computer science involve processing large graphs, e.g., stemming from finite element methods, digital circuit design, route planning, social networks, etc. Very often these graphs need to be partitioned or clustered such that there are few edges between the blocks (pieces).
A successful heuristic for partitioning large graphs is the multilevel graph partitioning approach (MGP) depicted in Figure 1 where the graph is recursively contracted to a smaller graph with the same basic structure. After applying an initial partitioning algorithm to this small graph, the contraction is undone and, at each level, a local refinement method improves the partition induced by the coarser level. Section 2 explains the method in more detail. Most systems instantiate MGP in a very similar way: Maximal matchings are contracted between two levels that try to include as many heavy edges as possible. Local refinement uses a linear time variant of local search. MGP has two crucial advantages over most other approaches to graph partitioning: We get near linear execution time since the graph shrinks geometrically and we get good partitioning quality since a good solution on some level yields a good initial solution on the next finer level, i.e., local search needs little work to further improve the solution.
Our central idea is to get even better partitions by making subsequent levels as similar as possible -we (un)contract only a single edge between two levels. We call this n-GP since we have (almost) n levels of hierarchy. More details are described in Section 3. n-GP has the additional advantage that there is no longer a need for an algorithm finding heavy matchings. This is remarkable insofar as a considerable amount of work on approximate maximum weight matching was motivated by the MGP application [24,5,22,18]. Still, at first glance, n-GP seems to have substantial disadvantages also. Firstly, storing each level explicitly would lead to quadratic space consumption. We avoid this by using a dynamic graph data structure with little space overhead. Secondly, choosing maximal matchings instead of just a single edge for contraction has the side effect that the graph is contracted everywhere, leading to a more uniform distribution of node weights. We solve this problem by explicitly factoring node weights into the edge rating function prioritizing the edges to be contracted. Already in [13,14] edge ratings have proven to lead to better results for graph partitioning. Perhaps the most serious problem is that the most common approach to local search is to let it run for a number of steps proportional to the current number of nodes. In the context of n-GP this could lead to a quadratic overall number of local search steps. Therefore, we develop a new, more adaptive stopping criteria for the local search that drastically accelerates n-GP without significantly reducing partitioning quality.
We have implemented n-GP in the graph partitioner KaSPar (Karlsruhe Sequential Partitioner). Experiments reported in Section 5 indicate that KaSPar scales well to large networks, computes the best known partitions for many instances of a "standard benchmark" and needs time comparable to system that previously computed the best results for large networks. Section 6 summarizes the results and discusses future directions.

More Related Work
There has been a huge amount of research on graph partitioning so that we refer to introductory and overview papers such as [7,8,26,30]  KaSPar was developed partly in parallel with KaPPa (Karlsruhe Parallel Partitioner) [14]. KaPPa is a "classical" matching based MGP algorithm designed for scalable parallel execution and its local search only considers independent pairs of blocks at a time. Still, for k = 2, its interesting to compare KaSPar and KaPPa since KaPPa achieves the previously best partitioning results for many large graphs, since both systems use a similar edge ratings, and since running times for a two processor parallel code and a sequential code could be expected to be roughly comparable.
There is a long tradition of n-level algorithms in geometric data structures based on randomized incremental construction (e.g, [11,1]). Our motivation for studying n-level are contraction hierarchies [10], a preprocessing technique for route planning that is at the same time simpler and an order of magnitude more efficient than previous techniques using a small number of levels.

Preliminaries
Consider an undirected graph G = (V, E, c, ω) with edge weights ω : E → R >0 , node weights c : V → R ≥0 , n = |V |, and m = |E|. We extend c and ω to sets, i.e., c( for some parameter ǫ. The last term in this equation arises because each node is atomic and therefore a deviation of the heaviest node has to be allowed. The objective is to minimize the total By default, our initial inputs will have unit edge and node weights. However, even those will be translated into weighted problems in the course of the algorithm. Contracting an edge {u, v} means replacing the nodes u and v by a new node x connected to the former neighbors of u and v. We set c(x) = c(u) + c(v). If replacing edges of the form {u, w} , {v, w} would generate two parallel edges {x, w}, we insert a single edge with ω({x, w}) = ω({u, w}) + ω({v, w}). Uncontracting an edge e undoes its contraction. Partitions computed for the contracted graph are extrapolated to the uncontracted graph in the obvious way, i.e., u and v are put into the same block as x.
Local Search is done by moving single nodes between blocks. The gain g B (v) of moving node v to block B is decrease in total cut size caused by this move. For example, if v has 5 incident edges of unit weight, 2 of which are inside v's block and 3 of which lead to block b then g B (v) = 3 − 2 = 1 3 n-Level Graph Partitioning Figure 2 gives a high-level recursive summary of n-GP. The base case is some other partitioner used when the graph is sufficiently small. In KaSPar, contraction is stopped when either only 20k nodes remain, no further nodes are eligible for contraction, or there are less edges than nodes left. The latter happens when the graph consists of many independent components. if G is small then return initialPartition(G, k, ǫ) pick the edge e = {u, v} with the highest rating contract e; P:= n-GP(G, k, ǫ); uncontract e activate(u); activate(v); localSearch() return P Figure 2: n-GP.
As observed in [14] Scotch [20] produces better initial partitions than metis, and therefore we also use it in KaSPar . The edges to be contracted are chosen according to an edge rating function. KaSPar adopts the rating function which fared best in [14]. As a further measure to avoid unbalanced inputs to the initial partitioner, KaSPar never allows a node v to participate in a contraction if the weight of v exceeds 1.5n/(20k). Selecting contracted edges can be implemented efficiently by keeping the contractable nodes in a priority queue sorted by the rating of their most highly rated incident edge. In order to make contraction and uncontraction efficient, we use a "semidynamic" graph data structure: When contracting an edge {u, v}, we mark both u and v as deleted, introduce a new node w, and redirect the edges incident to u and v to w. The advantage of this implementation is that edges adjacent to a node are still stored in adjacency arrays which are more efficient than linked lists needed for a full fledged dynamic graph data structure. A disadvantages of our approach is a certain space overhead. However, it is relatively easy to show that this space overhead is bounded by a logarithmic factor even if we contract edges in some random fashion (see [4]). In Section 5 we will demonstrate experimentally that the overhead is actually often a small constant factor. Indeed, this is not very surprising since the edge rating function is not random, but designed to keep the contracted graph sparse. Overall, with respect to asymptotic memory overhead, n-GP is no worse than methods with a logarithmic number of levels.

Local Search Strategy
Our local search strategy is similar to the FM-algorithm [6] that is also used in many other MGP systems. We now outline our variant and then discuss differences.
Originally, all nodes are unmarked. Only unmarked nodes are allowed to be activated or moved from one block to another. Activating a node v ∈ B ′ means that for blocks Node v is then inserted into the priority queue P B using g B (v) as the priority. We call a queue P B eligible if the highest gain node in P b can be moved to block B without violating the balance constraint for block B. Local search repeatedly looks for the highest gain node v in any eligible priority queue P B and moves v to block B.
When this happens, node v becomes nonactive and marked, the unmarked neighbors of v get activated and the gains of the active neighbors are updated. The local search is stopped if either no eligible nonempty queues remain, or one of the stopping criteria described below applies. After the local search stops, it is rolled back to the lowest cut state reached during the search (which is the starting state if no improvement was achieved). Subsequently all previously marked nodes are unmarked. The local search is repeated until no improvement is achieved.
The main difference to the usual FM-algorithm is that our routine performs a highly localized search starting just at the uncontracted edge. Indeed, our local search does nothing if none of the uncontracted nodes is a border node, i.e., has a neighbor in another block. Other FM-algorithms initialize the search with all border nodes. In n-GP the local search may find an improvement quickly after moving a small number of nodes. However, in order to exploit this case, we need a way to stop the search much earlier than previous algorithms which limit the number of steps to a constant fraction of the current number of nodes |V |.
Stopping Using a Random Walk Model. It makes sense to make a stopping rule more adaptive by making it dependent on the past history of the search, e.g., on the difference between the current cut and the best cut achieved before.
We model the gain values in each step as identically distributed, independent random variables whose expectation µ and Variance σ 2 is obtained from the previously observed p steps. In Appendix A we show how from these (purely heuristical, i.e., technically unwarranted) assumptions we can derive that it is unlikely that the local search will produce a better cut if where α and β are tuning parameters and µ is the average gain since the last improvement. For the variance σ 2 , we can also use the variance observed throughout the current local search. Parameter β is a base value that avoids stopping just after a small constant number of steps that happen to have small variance. Currently we set it to ln n.

Trial Trees
It is a standard technique in optimization heuristics to improve results by repeating various parts of the algorithm. We generalize several approaches used in MGP by adapting an idea initially used in a fast randomized min-cut algorithm [15]: After reducing the number of nodes by a factor c, we perform two independent trials using different random seeds for tie breaking during contraction, initial partitioning, and local search. Among these trials the one with the smaller cut is used for continuing upwards. This way, we perform independent trials at many levels of contraction controlled by a single tuning parameter c. As long as c > 2, the total number of contraction steps performed stays O(n).

Experiments
Implementation. We implemented KaSPar in C++ using gcc-4.3.2. We use priority queues based on paring heaps [28] available in the policy-based elementary data structures library (pb ds) for implementing contraction and refinement procedures. In the following experimental study we compared KaSPar to Scotch 5.1, kMetis 4.0 and the same version of KaPPa as in [14].
System. We performed our experiments on a single core of an Intel Xeon Quad-core Processor featuring 2x4 MB of L2 cache and clocked at 2.667 GHz of a 2 processor Intel Xeon X5355 node with 16 GB of RAM running Suse Linux Enterprise 10.
Instances. We report results on two suites of instances summarized in Table 1. rggX is a random geometric graph with 2 X nodes that represent random points in the unit square and edges connect nodes whose Euclidean distance is below 0.55 ln n/n. This threshold was chosen in order to ensure that the graph is almost connected. DelaunayX is the Delaunay triangulation of 2 X random points in the unit square. Graphs bcsstk29..fetooth and ferotor..auto come from Chris Walshaw's benchmark archive [27]. Graphs bel, nld, deu and eur are undirected versions of the road networks of Belgium, the Netherlands, Germany, and Western Europe respectively, used in [3]. Instances af shell9 and af shell10 come from the Florida Sparse Matrix Collection [2]. coAuthorsDBLP, coPapersDBLP, citationCiteseer, coAuthorsCiteseer and cnr2000 are examples of social networks taken from [9]. When not otherwise mentioned, we perform 10 repetitions for the small networks and 5 repetitions for the other. We report the arithmetic average of computed cut size, running time and the best cut found. When further averaging over multiple instances, we use the geometric mean in order to give every instance the same influence on the final figure. Configuring the Algorithm. We use two sets of parameter settings fast and strong.  Note that this are considerably less parameters compared to KaPPa. In particular, there is no need for selecting a matching algorithm, an edge coloring algorithm, or global and local iterations for refinement. Figure 3 shows the number of edges touched during contraction (KaSPar strong, small and large instances). We see that this scales linearly with the number of input edges and with a fairly small constant factor between 2 and 3. Interestingly, the number of local search steps during local improvement ( Figure 4) decreases with increasing input size. This can be explained by the sublinear number of border vertices that we have in graphs that have small cuts and by small average search space sizes for the local search. Indeed, Figure 5 in the appendix indicates that the average length of local searches grows only logarithmically with n. All this translates into fairly complicated running time behavior. Still, Figure 6 in the appendix warrants the conclusion that running time scales "near linearly" with the input  size. 1 The term in the running time depending on k grows sublinearly with the input size so that for very large graphs the number of blocks does not matter much.

Does the Random Walk Model Work? We have compared KaSPar fast with a variant
where the stopping rule is disabled (i.e., α = ∞). For the small instances this yields about 1 % better cut sizes at the cost of an order of magnitude larger running time. This is a small improvement both compared to the improvement KaSPar achieves over other systems and compared to just repeating KaSPar fast 10 times (see Table 2).
Do Trial trees help? We use the following evaluation: We run KaSPar strong and measure its elapsed time. Then for different values of initial partitionings a we repeat KaSPar strong without trial trees( c = 0 ), until the sum of the run times of all repetitions exceeds the run time of KaSPar strong. Than for different values a we compare the best edge cut achieved during repeated runs to the one produced by KaSPar strong. Finally, we average the obtained results over 5 repetitions of this procedure. If we then quality the computed partitions, we usually get almost identical results (a fraction of a percent difference). However, most of the time trial trees are a bit better and for road networks we get considerable improvements. For example, for the European network we get an improvement of 10 % on average over all k.
Comparison with other Systems. Table 2 summarizes the results by computing geometric means over 10 runs for the small instances and over 5 runs for the large instances and social networks. We exclude the European road network for k = 2 because KaPPa runs out of memory in that case. Detailed per instance results can be found in the appendix. KaPPa strong produces 5.9 % larger cuts than KasPar strong for small instances (average value) and 8.1 % larger cuts for the large instances. This comparison might seem a bit unfair because KaPPa is about five times faster. However, KaPPa is using k processors in parallel. Indeed, for k = 2 KaSPar strong needs only about twice as much time. Also note that KaPPa strong needs about twice as much time as KaSPar fast while still producing 6 % larger cuts despite running in parallel. The case k = 2 is also interesting because here KaPPa and KaSPar are most similar -parallelism does not play a big role (2 processors) and both local search strategies work only on two blocks at all time. Therefore 6 % improvement of KaSPar over KaPPa we can attribute mostly to the larger number of levels. Scotch and kMetis are much faster than KaSPar but also produce considerably larger cuts -e.g., 32 % larger for large instances (kMetis, average). For the European road network, the difference in cut size even exceeds a factor of two. Such gaps usually cannot be breached by just running the faster solver a larger number of times. For example, for large instances, Scotch is only a factor around 4 faster than KaSPar fast, yet its best cut values obtained from 5 runs are still 12.7 % larger than the average values of KaSPar fast.
For social networks all systems have problems. KaSPar lags further behind in terms of speed but extends its lead with respect to the cut size. We mostly attribute the larger run time to the larger cut sizes relative to the number of nodes which greatly increase the number of local searches necessary. A further effect may be that the time for a local search step is proportional to the number of partitions adjacent to the nodes participating in the local search. For "well behaved" graphs this is mostly two, but for social networks which get denser on the coarser levels this value can get larger.
The Walshaw Benchmark [27] considers 34 graphs using k ∈ {2, 4, 8, 16, 32, 64} and balance parameter ǫ ∈ {0, 0.01, 0.03, 0.05} giving a total of 816 table entries. Only cut sizes count -running time is not reported. We tried all combinations except the case ǫ = 0 which KaSPar cannot handle yet. We ran KaSPar strong with a time limit of one hour and report the best result obtained in the appendix. KaSPar improved 155 values in the benchmark table: 42 for 1%, 49 for 3% and 64 for 5% allowed imbalance. Moreover, it reproduced equally sized cuts in 83 additional cases. If we count only results for graphs having over 44k nodes and ǫ > 0, KaSPar improved 131 and reproduced 27 cuts, thus summing up to 63% of large graph table slots. We should note, that 51 of the new improvements are over partitioners different from KaPPa. Most of the improvements lie in the lower triangular part of the table, meaning that KaSPar is particularly good for either large graphs, or smaller graphs with small k. On the other hand, for small graphs, large k, and ǫ = 1% KaSPar was often not able to obtain a feasible solution. A primary reason for this seems to be that initial partitioning yields highly infeasible solutions that KaSPar is not able to to improve considerably during refinement. This is not astonishing, since Scotch targets ǫ = 3% and does not even guarantee that.

Conclusion
n-GP is a graph partitioning approach that scales to large inputs and currently computes the best known partitions for many large graphs, at least when a certain imbalance is allowed. It is in some sense simpler than previous methods since no matching algorithm is needed. Although our current implementation of KaSPar is a considerable constant factor slower than the fastest available MGP partitioners, we see potential for further tuning. In particular, thanks to our adaptive stopping rule, KaSPar needs to do very little local search, in particular for large graphs and small k. Thus it suffices to tune the relatively simple contraction routine to obtain significant improvements. On the other hand, the adaptive stopping rule might also turn out to be useful for matching based MGP algorithms.
A lot of opportunities remain to further improve KaSPar. In particular, we did not yet attempt to handle the case ǫ = 0 since this may require different local search strategies. We also want to try other initial partitioning algorithms and ways to integrate n-GP into other metaheuristics like evolutionary search.
We expect that n-GP could be generalized for other objective functions, for hypergraphs, and for graph clustering. More generally, the success of n-GP also suggests to look for more applications of the n-level paradigm.
An apparent drawback of n-GP is that it looks inherently sequential. However, we could probably obtain a good parallel algorithm by contracting small sets of highly rated, independent edges in parallel. Indeed, in the light of our results for KaSPar the complications coming from the need to find maximal matchings of heavy edges seem unnecessary, i.e., a parallelization of n-GP might be fast and simple.
[18] J. Maue and P. Sanders. Engineering algorithms for approximate weighted matching. In

A Derivation of Stopping Rules
Consider a situation where p steps of local search have been performed with average value µ and variance σ 2 . Then in the next s steps, we can expect a deviation from the expectation (p + s)µ by something of the order √ sσ 2 . The expression (p + s)µ + √ sσ 2 is maximized for s * := σ 2 4µ 2 . Now the idea is to stop when for some tuning parameter x, (p+s * )µ+x √ s * σ 2 > 0, i.e., it is reasonably likely that a random walk modelling our local search can still give an improvement. This translates to the condition p > σ 2 µ 2 ( x 2 − 1 4 ) or simply pµ 2 ≫ σ 2 .