Choice of an evaluation metric for a graph clustering algorithm

Question

I have instances for which the only thing I know is $70\%$ of the distance matrix.

I know some of these points form groups of correlated points (each point of a group is "close" to every point of the same group). I want to find these clusters of "close" points.

I chose a distance threshold. Each pair of points closer than this distance is linked by an edge. I get then a graph to which I apply a graph clustering algorithm. In order to select the 'best' parameters, I want to choose a quality metric. My objective is to regroup the points that form very interconnected groups.

I first tried to compare the silhouettes of the clusters for different parameters, but I feel uncomfortable that $30\%$ of the pairwise distances are ignored, and I am not sure this metric is appropriate with respect to my objective. Anyone has a more appropriate measure?

Answer 1

I'd disregard the 30% of the affinity matrix you don't know. I'd try to maximize my success rate on the 70% that I do know.

If I understood correctly, the question boils down to: how to evaluate clustering algorithms?

If you have access to the ground truth (i.e. the cluster to which each data point belongs to), there are several ways: entropy and purity are the most widely used - you can find a very good explanation of both in this website. However, the best one is clustering error, which some call maximum matching. You can see a very good example in this video.

If you don't have access to the ground truth, all you can rely on are intrinsic metrics. Basically, a good clustering results in small intra-cluster variance (all data points in a cluster are close to each other) and large inter-cluster variance (all cluster centroids are far apart from each other). You can see more details in this paper.