Restart and Random Walk in Local Search for Maximum Vertex Weight Cliques with Evaluations in Clustering Aggregation

1 Introduction

We deal with a simple undirected graph G = (V,E,w) where V is the vertex set, an edge e ∈ E is a 2-element subset of V , and w : V ↦→ R≥0 is a weighting function on V . A clique C is a subset of V such that each pair of vertices in C is mutually adjacent. The Maximum Vertex Weight Clique (MVWC) problem is to find a clique with the greatest total vertex weight. This problem exists in many real-world applications like [Brendel and Todorovic, 2010; Brendel et al., 2011]. In this paper we are concerned in finding a clique whose total vertex weight is as great as possible.

However, the MVWC problem is difficult to approximate [Feige, 2005]. Up to now, there are two types of algorithms: complete algorithms [ ¨Osterg˚ard, 2001; ¨Osterg˚ard, 2002; Kumlander, 2004; Yamaguchi and Masuda, 2008; Shimizu et al., 2012; Jiang et al., 2017] and incomplete ones [Pullan, 2008; Wu et al., 2012]. Furthermore, algorithms for the maximum weight independent set and minimum weight vertex cover problems can also work e.g., [Xu et al., 2016].

∗Corresponding author

1.1 Local Search for MVWC

Local search often suffers from the cycling problem, i.e., the search may spend too much time visiting a small area, thus various tabu strategies have been proposed to deal with this problem. Such examples can be found in two recent MVWC solvers MN/TS [Wu et al., 2012] and LSCC [Wang et al., 2016]. The former adopted a randomized tabu strategy to escape from local optima, while the latter utilized the strong configuration checking strategy to do so. Nevertheless, such tabu strategies still fail to prevent the local search frommoving in cycles, thus both MN/TS and LSCC need to restart periodically. More specifically they both adopted a parameter L to control how often the local search restarts. However, this parameter needs to be trained before the solver is being run. Furthermore it is unreasonable to use a fixed value for L during the search, since some parts of the search space can be more restrictive while some other parts can be less restrictive. Also it is difficult to understand why a particular value for L is suitable. Hence, we will propose a novel heuristic to restart at a good time point. It might be the first time to address this fundamental problem in local search for MVWC.

LSCC consists in two phases: (1) randomly generating a maximal clique C and then (2) improving C in a deterministic way. In each local move, LSCC selects the neighboring clique with the greatest weight according to the strong configuration checking criterion. However, using a deterministic heuristic to select a neighboring solution may be problematic, since a sequence of steps would be simply repeated without improving the best C found so far. Hence, we will adopt random walk to guide the search to move in different directions.

1.2 Our Contributions

We develop a solver named RRWL 1 (Restart and Random Walk in Local Search) based on the restart and the random walk strategies. Roughly if a solution is revisited in some particular situation, the search will restart. Also, when the search has no other options except dropping vertices, it will use random walk.

1 https://github.com/Fan-Yi/Restart-and-Random-Walk-inLocal-Search-for-MVWC

For showing the effectiveness, we compared RRWL with LSCC 2 , FastWClq [Cai and Lin, 2016] and WLMC [Jiang et al., 2017] on DIMACS [Johnson and Trick, 1996], BHOSLIB [Xu et al., 2005] and large sparse graphs 3 , as well as some graphs derived from the Winner Determination Problem (WDP) [Wu and Hao, 2015; Fang et al., 2016]. Experimental results show that

1. on DIMACS, RRWL outperforms LSCC and FastWClq in terms of the average solution quality as well as the best solution quality; moreover, it finds a new bestknown solution on MANN a81.clq.
2. on BHOSLIB, RRWL generally outperforms LSCC and greatly outperforms FastWClq.
3. on large sparse graphs, RRWL is comparable with FastWClq and greatly outperforms LSCC.
4. on the WDP graphs, the solution returned by RRWL in any run was proved to be optimal by WLMC; moreover, it locates the optimal solutions in a shorter time in many cases.

Since these graphs vary greatly in the sizes as well as the densities, our solver is much more robust than previous ones.

We also evaluate our solver on a number of real data sets in the application of clustering aggregation. Clustering is the task to partition a set of data objects into groups such that objects in the same group are similar, while objects in different groups are dissimilar. It is one of the most fundamental problems in data mining. Clustering aggregation, also known as ensemble clustering or consensus clustering, aims to combine multiple base clusterings into a probably better one. Formally, given a set of n data objects O = {o1, o2, ..., on}, a base clustering Ci on O is obtained by applying an exclusive clustering algorithm with a specific set of input parameters. Ci consists of k disjoint clusters ci1, ci2, ..., cik. These clusters form a partitioning of O, i.e., ⋃kj=1 cij = O and cip ∩ ciq = ∅ for all p ̸= q. Hence a clustering is a partitioning of the set O, and a cluster is a subset of O. Multiple base clusterings can be generated by different clustering algorithms with different parameters. Their qualities are generally very different. The goal of clustering aggregation is to pursue a better final clustering based on the information revealed from these base clusterings.

We follow the idea of [Li and Latecki, 2012] to formulate clustering aggregation as an MVWC problem, and evaluate our solver in this scenario. Experimental results on a number of real data sets demonstrate that our solver outperforms the other state-of-the-art for solving the derived MVWC problem and helps improve the final clustering results.

2 Preliminaries

Given an edge e = {u, v}, we say that u and v are neighbors, and u and v are adjacent to each other. Also we use N(v) =

2 In [Wang et al., 2016], there are LSCC and LSCC+BMS. LSCC is better on DIMACS and BHOSLIB. LSCC+BMS is better on large sparse graphs. For simplicity, we write both versions as LSCC if it is understood from the context or there are no confusions.

3 http://networkrepository.com/networks.php

{u|u and v are neighbors.} to denote the set of v's neighbors. A maximal clique is a clique which is not a subset of any other clique. Given a weighting function w : V ↦→ R≥0, the weight of a clique C, denoted by w(C), is defined to be ∑v∈C w(v). We use age(v) to denote the number of steps since last time v changed its state (inside or outside the candidate clique).

2.1 The Benchmark

The DIMACS, BHOSLIB and large graphs were originally unweighted. To obtain the corresponding MVWC instances, researchers use the method in [Pullan, 2008]. For the i-th vertex vi, w(vi) = (i mod 200) + 1. Also we compare state-of-the-art MVWC solvers in winner determination and clustering aggregation.

2.2 Multi-neighborhood Search

Usually for finding a good weighted clique, the local search moves from one clique to another until the cutoff arrives, then it returns the best clique that has been found. There are three operators: add, swap and drop, which guide the local search to move in the clique space. In [Fan et al., 2016], two sets Sadd and Sswap were defined as below which ensures that the clique property is preserved.

We use ∆add, ∆swap and ∆drop to denote the increase of w(C) for the operation add, swap and drop respectively. Obviously, we have (1) for a vertex v ∈ Sadd, ∆add(v) = w(v); (2) for a vertex u ∈ C, ∆drop(u) = -w(u); (3) for a vertex pair (u, v) ∈ Sswap, ∆swap(u, v) = w(v) - w(u).

2.3 The Strong Configuration Checking Strategy

Recently, [Cai et al., 2011] proposed the configuration checking (CC) strategy to reduce cycling. The CC strategy works as follows. If a vertex is removed out of the candidate set, it is forbidden to be added back into the candidate set until its configuration has been changed. Typically, the configuration of a vertex refers to the state of its neighboring vertices.

The CC strategy is usually implemented with a Boolean array named confChange, where confChange(v) = 1 means that v's configuration has changed since last time it was removed, and confChange(v) = 0 otherwise.

Later [Wang et al., 2016] modified CC into a more restrictive version, which is called strong configuration checking (SCC), to deal with the MVWC problem. The main idea of the SCC strategy is as follows: after a vertex v is dropped from or swapped from C, it can be added or swapped back into C only if one of its neighbors is added into C.

In details, the SCC strategy works as follows. (1) Initially confChange(v) is set to 1 for each vertex v; (2) When v is added, confChange(n) is set to 1 for all n ∈ N(v); (3) When v is dropped, confChange(v) is set to 0; (4) When (u, v) ∈ Sswap are swapped, confChange(u) is set to 0.

Lastly, whether a vertex is allowed to be added or swapped into the candidate clique is also referred to as its tabu status.

3 ARevisiting based Restart Strategy

We first discuss the drawback of local search for MVWC, and propose a novel condition in which the search will restart.

3.1 Drawback in Local Search for MVWC

Usually in local search for propositional satisfiability, vertex cover, etc., the search will periodically pick a random unsatisfied constraint, and then selects a local move to satisfy this constraint. Thus the search is able to traverse the search space by such steps. In contrast, in the case of MVWC, the hard constraints are always satisfied, and each local move tries to maximize the clique weight. Hence, for MVWC the number of neighboring solutions is relatively small, i.e., there are relatively few possible local moves for the next step. Considering the definitions of Sadd and Sswap, the search is not extensive. It may be restricted in a cycle even though we have intelligent tabu strategies, so restart is needed to improve extensive search in local search for MVWC.

Now the problem is how to determine whether the search is restricted in a cycle. Since local search method does not allow us to memorize the whole search history, we have to develop various heuristics to estimate this condition.

3.2 First Growing Step

Usually in local search there is an objective function value which needs to be maximized. This function value will be increased and decreased periodically during the search. In current state-of-the-art MVWC solvers, the objective function value refers to the clique weight.

In each period, after the first step which increases the clique weight, we detect revisiting (Line 27 in Algorithm 2).

Revisiting is not a sufficient condition for restart

One may think that the search should restart once a solution is revisited, yet this is not the case. The local search sometimes revisits a solution due to the drop operations, and such revisiting does not mean that the search is restricted in a cycle. Hence, when a solution is revisited, we should consider whether the clique is being extended or shrunk.

Even though a solution is revisited, we have little sense whether the local search will choose to repeat a previous step. If a candidate solution is revisited, with the tabu status of the vertices nearby the same as before, then the selected local move would simply repeat a previous step, i.e., the search is probably restricted in a cycle, so restart is needed. Otherwise, if a solution is revisited, with the tabu status of the vertices nearby different from that before, the search can get rid of the cycle easily, so restart is unreasonable.

Extending and shrinking periods

In our algorithm, we employ a predicate lastStepImproved such that lastStepImproved = true iff the clique weight was increased in the last step. Then we use this predicate to check whether the clique is being extended or shrunk. Obviously when a vertex is added, the search is in the extending period; when a vertex is dropped, the search is in the shrinking period. However, when a pair of vertices, namely (u, v), are swapped, the clique may be extending or shrinking. More specifically, if w(u) < w(v), the clique is extending; otherwise the clique is shrinking.

If a solution is revisited together with the same lastStepImproved value as before, then the search is quite probably restricted in a cycle. In other words if we consider revisiting only when lastStepImproved = true (or lastStepImproved = false), the restart strategy may become more reasonable.

Why only consider extending periods

Some intuitive analyses suggest that considering revisiting in the extending period is more reasonable.

In the shrinking period, vertices are probably being dropped. In both MN/TS and LSCC, when a vertex is selected to be dropped, no tabu status is considered. So even though a solution is revisited in this period, we are not certain whether the tabu status of the vertices nearby is close to that before, therefore we are unsure whether the search is restricted in a cycle.

In the extending period, vertices are being added or swapped. In both MN/TS and LSCC, when a vertex is selected to be added or swapped into the candidate clique, it has to satisfy the tabu requirements. In this sense if a solution is revisited in this period, it seems that the tabu requirements fail to prevent the search from being restricted, so restart is reasonable.

Why choose the first growing step

Suppose that a solution is visited in the first growing step and later it is revisited in the second growing step. Obviously these two situations have different recent histories, therefore the tabu status of the latter situation may be different from the that of the previous situation. So we are unsure whether the search is restricted in a cycle. However, if both situations occur in the first growing step, we are quite confident that the search is restricted in a cycle.

Readers may think that our restart strategy may be too cautious, i.e., the search may spend too much time in a nonpromising area. Yet experiments still show that our solver restarts more frequently than previous solvers.

3.3 Implementations of Detecting Revisiting

We use a hash table to approximately detect revisiting. Since the collisions, i.e., different solutions may share the same hash entry, are rare in our settings, we do not resolve them.

Definition 1 Given a clique C and a prime number p, we define the hash value of C, denoted by hash(C), as (∑vi∈C 2i ) mod p, which maps a clique C to its hash entry hash(C).

At the beginning, we calculate (2i mod p) iteratively with different values of i, based on the proposition below.

Our solver will save these values in an array for later references. Hence, in Theorem 2 below, the subformulas (2i mod p) can be computed in constant complexity. So the hash value of the current clique can be updated in O(1) complexity as well.

Theorem 2 Let C be the current clique, then we have

1. hash(C ∪ {vi}) = [hash(C) + (2i mod p)] mod p;

Throughout this paper, we set p = 109 + 7. If we use a larger prime number, the chance of collision will decrease. Thus, we set this parameter simply based on the memory capacity of our machines. With this prime number p, our hash table consumes around 1 GB memory. While in our experiments, our solver performs less than 3 × 108 steps in any run. Therefore, given the 109 +7 hash entries, the number of collisions is negligible.

4 RandomWalk for Dropping Vertices

In MN/TS and LSCC, when a vertex is selected to be added or swapped into the candidate clique, it has to satisfy the tabu requirements. Thus the tabu requirements guide the search to move in different paths. However, when a vertex is selected to be dropped, no tabu requirements exist and the one with the smallest weight is chosen. Thus if a local optimum is revisited, the candidate clique will probably be shrunk in the same way as before, and thus it may probably repeat previous steps.

In the case of adding and swapping, the clique weight may increase and lead to a new best-found clique, so best-picking is necessary. However, in the case of dropping, it is unclear why greedy search is reasonable. In local search for propositional satisfiability, vertex cover etc., it is desired to break as few hard constraints as we can. However, in local search for MVWC, the clique weight constraint is soft, so the minimum break heuristic may not be reasonable here.

In RRWL, when there are no options for the next step except dropping vertices, we randomly drop one vertex from the clique (See Line 22 in Algorithm 2). With random walk, even though a local optimum is revisited, different sub-cliques will be generated in different times, and later different add or swap operations will be applied. The search will switch to different cliques nearby and hence the local area will be searched more thoroughly.

5 The RRWL Algorithm

The top level algorithm is shown in Algorithm 1, where the localMove() procedure is shown in Algorithm 2.

Algorithm 1: RRWL

input : A graph G = (V,E,w) and the cutoff output: The best clique that was found 1 C ∗ ← C ← ∅; lastStepImproved ← true; 2 step ← 1; confChange(v) ← 1 for all v ∈ V ; 3 while elapsed time < cutoff do localMove() ;

4 return C ∗ ;

In Algorithm 2, the vertices of the operations are explicit from the context and thus omitted. All ties are broken in favor of the oldest one just like LSCC. Notice that when the conditions in Lines 9 or 18 hold, the clique weight was decreased in the last step and is increased in this step, so this is the first growing step.

Algorithm 2: localMove

1 if C = ∅ then 2 add a random vertex into C; 3 while Sadd ̸= ∅ do add a random vertex from Sadd ; 4 lastStepImproved ← true; 5 firstGrowingStep ← false; 6 v ← a vertex in Sadd such that confChange(v) = 1 with the biggest ∆add; otherwise v ← NL; 7 (u, u′ ) ←a pair in the Sswap such that confChange(u′ ) = 1 with the biggest ∆swap; otherwise (u, u′ ) ← (NL, NL); 8 if v ̸= NL then 9 if lastStepImproved = false then 10 firstGrowingStep ← true; 11 if (u, u′ ) = (NL, NL) or ∆add >∆swap then C ← C ∪ {v}; else C ← C\{u} ∪ {u′ }; 12 lastStepImproved ← true; 13 else 14 if (u, u′ ) = (NL, NL) or ∆swap < 0 then 15 if w(C) > w(C ∗ ) then C ∗ ← C; 16 lastStepImproved ← false; 17 else 18 if lastStepImproved = false then 19 firstGrowingStep ← true; 20 lastStepImproved ← true; 21 x ←a vertex in C with the biggest ∆drop; 22 if (u, u′ ) = (NL, NL) then drop a random vertex ; 23 else 24 if ∆drop > ∆swap then C ← C\{x}; 25 else C ← C\{u} ∪ {u′ }; 26 apply SCC rules; step ← step+1; 27 if firstGrowingStep = true then 28 mark hash(C); 29 if hash(C) remarked then drop all vertices ;

6 Evaluations on Hand-crafted Graphs

To evaluate individual impacts, we disable the random walk strategy in RRWL and develop another solver named RSL.

6.1 Experimental Setup

For LSCC, the search depth L was set to 4,000. When solving large crafted graphs, LSCC employs the BMS heuristic, and the parameter k was set to 100, as in [Wang et al., 2016]. For FastWClq, the parameters k0 and kmax for the dynamic BMS heuristic were set to 4 and 64 respectively, as in [Cai and Lin, 2016]. WLMC was compiled by gcc 4.4.7 and all other solvers were compiled by g++ 4.7.3. The experiments on DIMACS, BHOSLIB and WDP graphs were conducted on a cluster equipped with Intel(R) Xeon(R) CPUs X5650 @2.67GHz with 16GB RAM, running Red Hat Santiago OS. The experiments on the large crafted graphs were conducted on a cluster equipped with Intel Xeon E5-2670 v3 2.3GHz with 32GB RAM, running CentOS6.

Each solver was executed on each instance with seeds from 1 to 100 on DIMACS and BHOSLIB, from 1 to 10 on the large crafted graphs and from 1 to 10 on WDP graphs, as in [Wang et al., 2016], [Cai and Lin, 2016] and [Jiang et al., 2017] respectively. Since WLMC is an exact solver, it was executed only once on each WDP instance. The cutoff was set to 500s for RSL and RRWL on the WDP graphs, while the cutoff was set to 1,000s for all solvers on all other instances. For each algorithm (except WLMC) on each instance in DIMACS, BHOSLIB and large crafted graphs, we report the maximum weight ("wmax") and averaged weight ("wavg") of the cliques found by the algorithm. To make the comparisons clearer, we also report the difference ("δmax") between the maximum weight of the cliques found by RRWL and that found by LSCC or FastWClq. Similarly δavg represents the difference between the averaged weights. A positive difference indicates that RRWL performed better, while a negative value indicates the opposite. For RRWL, RSL and WLMC on each WDP instance, since they returned the same quality solutions in all runs, we report the average time needed to locate the best-found solutions in each group.

6.2 DIMACS and BHOSLIB

These graphs are dense. Experimental results show that

1. on each instance in DIMACS, RRWL performs at least as well as LSCC,
2. on several instances in DIMACS, RRWL substantially outperforms both LSCC and FastWClq;
3. in BHOSLIB, RRWL performs generally better than LSCC and greatly outperforms FastWClq.

Further experiments show that LSCC performs worse than RSL and RSL performs worse than RRWL, so both the restart and the random walk strategies have their own contributions. For the sake of space, we only list all the graphs on which RRWL and LSCC found different wmax or wavg in Table 1. Notice that on MANN a81.clq, we found wmax = 111,341. So far as we know, this is a new best-known solution.

Now we analyze the performances. (1) When local search is done on dense graphs, Sadd and Sswap are big, so there are many options for the next step. In this situation revisiting in the first growing step is not so frequent. (2) In these graphs, the vertex degrees are usually bigger than 400 and close to each other, and the vertex weights are in uniform distribution. Therefore, even though revisiting in the first growing step occurs, it is relatively easy to get rid of the cycles. (3) Since DIMACS and BHOSLIB graphs were originally derived from hard combinatorial models, they present complicated structures. Therefore better intensive search is needed and thus random walk improves the performances. (4) Since the vertex degrees are close, the bounds in FastWClq are loose, so graph reduction is ineffective.

6.3 Large Crafted Graphs

We used the benchmark in [Cai and Lin, 2016]. Some graphs have millions of vertices and dozens of millions of edges. Also they are very sparse. The average degree is usually around 10∼50. There is a recent solver named LMY-GRS

[Fan et al., 2016], and we adopt its data structures. Since it falls behind RRWL 4 , so we omit it in this section.

Experimental results show that RRWL and FastWClq returned the same wmax and wavg on all instances except 5 instances (See Table 2). Moreover, both of them outperform LSCC+BMS greatly. Further experiments show that RSL and RRWL returned the same values on all instances except ca-hollywood-2009. On this instance, RSL and FastWClq returned the same values. For the sake of space, in Table 2, we simply list some largest graphs in this benchmark.

Thanks to the power-distribution law, graph reduction is powerful. Therefore, FastWClq finds good solutions, and is able to confirm the optimality of the returned solution on many graphs. In contrast, the local search in LSCC+BMS is seriously restricted, because both Sadd and Sswap are very small. Hence, LSCC+BMS falls behind FastWClq.

RRWL is a pure local search solver, so it must be able to traverse the search space quite comprehensively. Here, the restart strategy guides the search to different parts of the search space. Since the graph structures are relatively simple in this benchmark, so better intensive search is not needed and thus the contribution of random walk is not observed.

4 https://github.com/Fan-Yi/Restart-and-Random-Walk-inLocal-Search-for-MVWC-in-Large-Sparse-Graphs

6.4 Winner Determination ProblemGraphs

An important application of MVWC is to solve the winner determination problem (WDP), because WDP can naturally be formulated as MVWC.

We compared RRWL and RSL with WLMC on the WDP benchmark 5 provided in [Lau and Goh, 2002], which has been used to test MVWC algorithms. The benchmark contains 499 instances with up to 1,500 items and 1,500 bids, and can be divided into 5 groups by the item number and the bid number. Each group is labeled as REL-m-n, where m is the number of items and n is the number of bids. The REL-1000-1500 group contains 99 instances, while all other groups contain 100 instances. Thus with 10 seeds, both RSL and RRWL performed a total of 4,990 runs in this benchmark.

When formulated as MVWC, the graphs contain up to 1,500 vertices with density from 0.06 to 0.33. Therefore the average density of WDP graphs is significantly smaller than that of the DIMACS and BHOSLIB graphs, and bigger than that of the large crafted graphs.

Experimental results show that the solutions returned by RSL and RRWL were all proved to be optimal by WLMC, i.e., both solvers found the optimal solutions in all runs. In Table 3, we present the averaged time (seconds) needed to locate the respective solutions for each solver in each group ("LocateTime"). Since WLMC is able to confirm the optimality of the returned solution, we also report the time needed to find and prove the optimal solution ("RunTime"). From this table, we can find that our solvers often locate the optimal solutions in a shorter time. Also it may be the first time that incomplete solvers achieve state-of-the-art in this benchmark.

Since the density of these graphs lie between those graphs in the previous benchmarks, the local search is moderately restricted, so the restart strategy guides the search away from cycling and thus avoids a significant amount of useless steps. Also because of the relatively low density, the bounds in WLMC are tight and the branching technique is able to analyze the graph structures effectively, so WLMC performs well. Although the WDP graphs have practical backgrounds, they involve randomness. Therefore they still serve as handcrafted graphs. The real-world impacts of finding an MVWC on them are not clear.

5 All the vertex weights are rounded down to an integer just like [Jiang et al., 2017].

6.5 Restart Frequencies

Further experiments show that sparse graphs lead to high restart frequencies. For example on frb59-26-5.clq whose density is 0.89, our solver restarts every 1,300 steps on average; on in143.wclq whose density is 0.31, it restarts every 150 steps; and on soc-livejournal whose density is 3.4 × 10-7 , it restarts every 60 steps.

7 Evaluations in Clustering Aggregation

We follow the essential idea of [Li and Latecki, 2012] to formulate clustering aggregation as an MVWC problem. In the first experiment, we compare RRWL with state-of-theart MVWC solvers on those graphs derived from clustering aggregation on real data sets. Experimental results show that our solver RRWL outperforms all other solvers 6 . In the second experiment, we embed our solver into the algorithm framework of [Li and Latecki, 2012] (CA+RRWL 7 ) to evaluate the overall performance, and compare it to other recent clustering aggregation methods. Experiments show that CA+RRWL is competitive.

7.1 Recent Clustering Aggregation Algorithms

The COMUSA algorithm proposed in [Mimaroglu and Erdil, 2011] first constructs a similarity graph based on the coassociation matrix. Then it identifies new clusters by iteratively selecting a pivot data object and expanding the cluster with its immediate free neighbors which are most similar to the pivot. [Huang et al., 2015] proposed two algorithms termed weighted evidence accumulation clustering (WEAC) and graph partitioning with multi-granularity link analysis (GP-MGLA). WEAC integrates the reliability of each base clustering into the co-association matrix and uses agglomerative algorithms to obtain the final clustering. GP-MGLA models the three levels of granularity in clustering aggregation, i.e., data objects, clusters and base clusterings, in a single bipartite graph, and partitions it to divide data objects into the final clusters. [Huang et al., 2016a] proposed to sparsify the co-association matrix of "microcluster" with the knearest neighbors strategy and learn new similarities based on random walks. Two algorithms, probability trajectory accumulation (PTA) and probability trajectory based graph partitioning (PTGP) were proposed to obtain the final clustering with the learned similarities. PTA is based on agglomerative algorithms, while PTGP is based on the graph partitioning technique. [Huang et al., 2016b] formulated clustering aggregation as a binary linear programming problem and proposed a solver based on max-product belief propagation on a factor graph.

6 Since WLMC only deals with integer weights, we do not include it in this section.

7 https://github.com/Fan-Yi/Restart-and-Random-Walk-inLocal-Search-for-MVWC-in-Clustering-Aggregation

7.2 Experimental Setup

We now introduce the data sets and the MVWC formulation.

The Data Sets

The evaluations are performed on 7 real data sets from the UCI machine learning repository [Lichman, 2013], including Iris, Zoo, Semeion Handwritten Digit (Semeion), Pen Digits (PD), Vowel, ISOLET and Letter Image Recognition (Letter).

The detailed information of these data sets are given in Table 4. For instance, Iris has 150 data objects; each of them has 4 attributes; and the data objects are from 3 classes.

The MVWC Formulation

To generate multiple base clusterings for each data set, we use two classic clustering algorithms, k-means and completelinkage, and vary the desired cluster number k in the range shown in Table 5. For instance, on Iris data set, we vary k from 2 to 10 with a step size of 1 for both k-means and complete-linkage algorithms. As a result, we obtain 18 base clusterings with a total of 108 clusters.

Then a simple undirected and vertex-weighted graph is constructed. Each vertex represents a cluster. If two clusters ci and cj, which are from two different clusterings, contain some common data objects, we say that they are overlapping. For any two non-overlapping clusters, there is an edge connecting the vertices representing them. For robustness in our experiments, we tolerate slight overlap between clusters. That is, for the adjacency matrix A = (aij)n×n, aij = 1 if |ci∩cj | min(|ci|,|cj |) < 0.05, and aij = 0 otherwise. The basic statistics of the derived graph of each data set are given in Table 5. Note that since k-means may return different clusterings for the same data set and the same k due to its randomness in initialization, we construct 100 graphs for each data set and report the average edge number and average vertex degree davg. Obviously, the derived graphs are all very dense.

The weight of each vertex is defined as the sum of the silhouette coefficients of the data objects belonging to the corresponding cluster. Specifically, in a certain clustering, the silhouette coefficient for the tth data object, St, is defined as St = bt-at max(at,bt) where at is the average distance from the tth data object to the other data objects in the same cluster as t, and bt is the minimum average distance from the tth data object to data objects in a different cluster, minimized over clusters. The weight wi on vertex i, which represents the cluster ci is defined as: wi = ∑t∈ci St. 8

7.3 Comparisons of Different MVWC Solvers

In the first experiment, we compare RRWL with state-of-theart MVWC solvers on the derived graphs. In consideration of the randomness of k-means, we generate 10 graphs for each data set and report the average performance.

The algorithms for comparison include FastWClq, LSCC, LSCC+BMS, simulated annealing based on maximal clique (SAMC) [Li and Latecki, 2012], and MWBC, which serves as the baseline, just returns the set of vertices belonging to the same base clustering and having the maximum sum of weights. For SAMC, we use the same parameters as in [Li and Latecki, 2012], i.e., q = 0.3, β = 0.999, and iteration number n = 100. The parameters of FastWClq, LSCC and LSCC+BMS are the same as before.

FastWClq, LSCC, LSCC+BMS and our solver are implemented in C++ and invoked from MATLAB on a PC with Intel(R) Core(TM) i7 processor up to 3.4 GHz and 16 GB RAM. We set the cut off to be 10 minutes and used one seed. Results Table 6 shows that RRWL is the unique solver which finds best cliques in all data sets, which shows the robustness and superiority of our solver. Comparing Tables 5 and 6 we find that the bigger the graph is, the more difficult it is to find an MVWC. For example, most solvers work well on Iris and Zoo while very few solvers work well on ISOLET and Letter. This also shows that our algorithm is more scalable. We also evaluate RSL in this scenario, but find no difference from RRWL. In fact the clustering aggregation graphs are simple, so random walk for better intensive search is not needed.

7.4 Comparisons of Final Clustering Results

In the second experiment, we replace the SAMC solver with ours in the algorithm framework of [Li and Latecki,

8 Sometimes wi may be a negative number. In this situation, we assign 0 to wi and remove all the edges incident to i.

2012] to evaluate its performance for clustering aggregation (CA+RRWL). The cut off time is set to be 5 minutes. The comparison clustering aggregation algorithms include COMUSA [Mimaroglu and Erdil, 2011], WEAC+SL [Huang et al., 2015], WEAC+CL [Huang et al., 2015], WEAC+AL [Huang et al., 2015], GP-MGLA [Huang et al., 2015], ECFG [Huang et al., 2016b], PTA+SL [Huang et al., 2016a], PTA+CL [Huang et al., 2016a], PTA+AL [Huang et al., 2016a], PTGP [Huang et al., 2016a] and CA+SAMC [Li and Latecki, 2012]. For these algorithms, we follow the author-recommended or default settings and parameters.

Note that COMUSA, ECFG, CA+SAMC and our CA+RRWL can automatically determine the cluster number in the aggregated clustering, while the rest algorithms need it as an input parameter. For fair comparisons, we follow the experimental protocol in [Huang et al., 2016b] and specify the cluster number for those "non-automatic" algorithms to be the one automatically estimated by CA+SAMC. For CA+SAMC and our CA+RRWL, there may be a couple of data objects which are not covered by the aggregated clustering or are covered by more than one cluster due to the slight overlap. In that case, we perform the post-processing [Li and Latecki, 2012] to assign such data objects to their nearest clusters.

The quality of the final aggregated clustering is measured in terms of the normalized mutual information (NMI) [Strehl and Ghosh, 2002]. A higher NMI indicates that the aggregated clustering matches the ground-truth class memberships better. In consideration of the randomness of k-means, we run experiment on each data set 100 times with one seed and report the average NMI.

Results As shown in Table 8, CA+RRWL consistently improves CA+SAMC which shows the contributions of our solver. Also CA+RRWL is very competitive in clustering aggregation compared with other state-of-the-art techniques.

8 Conclusions and FutureWork

In this paper, we developed a local search MVWC solver. Experimental results show that RRWL outperforms state-ofthe-art solvers on DIMACS and reports a new best-known solution. It is the unique solver which achieves state-of-theart performances in both standard and large crafted graphs, as well as the graphs derived from the winner determination problem. Also it helps improve the final clustering results on real data sets.

The main contributions include: (1) a restart strategy to improve extensive search; (2) a random walk strategy to improve intensive search; (3) a fast approximate hash table to detect revisiting.

As for future works we will study variants of the restart strategy in the context of MVWC. Also, we will apply these methods to solve other problems.

Acknowledgments

We thank all anonymous reviewers for their valuable comments. We thank Yanyan Xu for proofreading the submission of this paper. This work is supported by ARC Grant FT0991785, NSF Grant No. 61463044, NSFC Grant No. 61572234, Grant No. [2014]7421 from the Joint Fund of the NSF of Guizhou province of China, and the US NSF under Grant IIS-1302164.

We gratefully acknowledge the support of the Griffith University eResearch Services Team and the use of the High Performance Computing Cluster "Gowonda" to complete this research. This research was also supported by use of the NeCTAR Research Cloud and by QCIF(http://www.qcif.edu.au). The NeCTAR Research Cloud is a collaborative Australian research platform supported by the National Collaborative Research Infrastructure Strategy.