Learning Resolution Parameters for Graph Clustering
  Finding clusters of well-connected nodes in a graph is an extensively studied
problem in graph-based data analysis. Because of its many applications, a large
number of distinct graph clustering objective functions and algorithms have
already been proposed and analyzed. To aid practitioners in determining the
best clustering approach to use in different applications, we present new
techniques for automatically learning how to set clustering resolution
parameters. These parameters control the size and structure of communities that
are formed by optimizing a generalized objective function. We begin by
formalizing the notion of a parameter fitness function, which measures how well
a fixed input clustering approximately solves a generalized clustering
objective for a specific resolution parameter value. Under reasonable
assumptions, which suit two key graph clustering applications, such a parameter
fitness function can be efficiently minimized using a bisection-like method,
yielding a resolution parameter that fits well with the example clustering. We
view our framework as a type of single-shot hyperparameter tuning, as we are
able to learn a good resolution parameter with just a single example. Our
general approach can be applied to learn resolution parameters for both local
and global graph clustering objectives. We demonstrate its utility in several
experiments on real-world data where it is helpful to learn resolution
parameters from a given example clustering.
