Graph clustering with local search optimization: The resolution bias of the objective function matters most

Results of a recent comparative experimental assessment of methods for network community detection applied to benchmark graphs indicate that the two best methods use different objective functions but a similar local search-based optimization (LSO) procedure. This observation motivates the following research question: Given the LSO optimization procedure, how much does the choice of the objective function influence the results and in what way? We address this question empirically in a broad graph clustering context, that is, when graphs are either given as such or are $k$-nearest-neighbor graphs generated from a given data set. We consider normalized cut, modularity, and infomap, as well as two new objective functions. We show that all these objectives have a resolution bias, that is, they tend to prefer either small or large clusters. When removing this bias, by forcing the objective to generate a given number of clusters, LSO achieves similar performance across the considered objective functions on benchmark networks with built-in community structure. These results indicate that the resolution bias is the most important difference between objective functions in graph clustering with LSO. Spectral clustering is an alternative to LSO, which has been used to optimize the popular normalized cut and modularity objectives. We show experimentally that LSO often achieves superior performance than spectral clustering on various benchmark, real-life, and $k$-nearest-neighbor graphs. These results, the flexibility of LSO  and its efficiency, provide arguments in favor of this optimization method.

Figure 1

Model graph for showing the resolution limits. The circles represent strongly connected “modules” with $q-r$ internal edges, while the lines represent $r$ edges each.

Figure 2

The resolution limits of graph clustering objectives as a function of the graph size. We used $r=1$ and $q=46$, which corresponds to modules that are cliques with 10 nodes. The resolution limit of the parabola objective is the same as that of modularity.

Figure 3

Normalized mutual information as a function of the mixing parameter for various objective functions; the Small 1000 data set (top) and the Big 5000 data set (bottom). The error bars indicate standard deviation.

Figure 4

Normalized mutual information as a function of the mixing parameter, when the number of clusters has been fixed to the actual number of clusters. We show results for the Small 1000 data set (top) and the Big 5000 data set (bottom). The error bars indicate standard deviation.

Figure 5

The value of the objective as a function of the mixing parameter on the Small 1000 data set. “Random” is the objective value reached by the optimizer on a randomly rewired graph, “truth” is the objective value of the ground truth clustering. LSO is the value reached by the optimizer, and LSO$\times 20$ is the best objective value of 20 restarts. The objectives shown are as follows: modularity (top left), parabola (top right), w-log-v (bottom left), and infomap (bottom-right).

Figure 6

Accuracy of the clustering methods on the two moons data set, as a function of the variance of the noise.