Comparing Graph Clusterings: Set partition measures vs. Graph-aware measures

An impressive number of graph clustering algorithms have been proposed, studied and compared over the past decades [4,10,17,19,21,23,25]. To identify better graph clustering techniques, one needs a way to score the techniques against one another. A typical method is to compare values of some similarity measure between ground truth partitions of given graphs and the partitions produced by the different algorithms on those graphs. However, the choice of the similarity measure used is crucial and has a huge impact on the conclusions made. In graph clustering comparison studies [8,13,18,28], set partition similarities are used as accuracy measures.