Learning resolution parameters for graph clustering
Loading...
Citations
Scopus:
Altmetric:
Altmetric::
Download
Associated Records
Authors
File Licence
Date
2019-05-13
Source Title
WWW '19 The World Wide Web Conference
Journal Title
Journal ISSN
Volume Title
Publisher
ACM
Melbourne Authors
Affiliation
Computing and Information Systems
Document Type
Conference Paper
Subject Code
Citation
Veldt, N., Gleich, D. F. & Wirth, A. (2019). Learning resolution parameters for graph clustering. Liu, L (Ed.) White, R (Ed.) WWW '19 The World Wide Web Conference, pp.1909-1919. ACM. https://doi.org/10.1145/3308558.3313471.
Access Status
Open Access
Access URL
Open Access URL
Open Access at PMC
Linked Resource URL
NHMRC Grant Code
ARC Grant Code
Description
Abstract
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.