Clustering with Geometric Modularity

We thank the reviewer for their comments. We reply to the weaknesses and questions.

Q. Connection between geometric modularity and density-based clustering.

Thanks for raising this point. We will clarify it in the final version. The main reason for introducing this notion in metric spaces is that input to density-based clustering algorithms is often points in a vector space. We focus on DBSCAN because (i) we were able to give a theoretical explanation regarding the effectiveness of using geometric modularity, (ii) the empirical performance is also very good. DBSCAN is also one of the most widely used clustering algorithms. For $k$-means, etc. it is not clear how we would tune the hyperparameter $\rho$ as we mention in our reply to Reviewer WBYe. Exploring further applications of this notion is an interesting direction for future work.

Q. Experiments for reproducibility.

Thanks for the suggestion. We will add an Appendix with full details of all the parameters. We will also make the code available before publication.

Q. HDBSCAN.

We will report this experiments in the final paper. And also post results on this discussion thread as soon as they are available.

We thank the reviewer for their comments. We reply to the weaknesses and questions.

Q. No algorithm description.

We thought that the algorithm as described in the text was sufficient, but thanks for pointing this out, we will add it in the new version.

Q. Geometric modularity frequenty used.

We are very confused by the statement that geometric modularity is frequently used. We are not aware of any work mentioning “geometric modularity”. We acknowledge that there are various works on graph modularity but one of the novelties of this work is to introduce a notion of modularity for (pseudo)metric spaces.

It seems that there is a confusion here: the fact that the input exhibits clusters does not mean that the algorithm can find them. The assumptions used here only state that there is an underlying clustering and not that this clustering is tailored to the algorithm since similar assumptions have appeared in the literature before. In fact, such an analysis is lacking for most algorithms and, for example, DBSCAN with poor parameter choices would fail to recover the clusters.

Q. Agree with claim Geometric Modularity tracks AMI", but this is known to the community.

We are not aware of any work connecting geometric modularity with AMI (also because we are not aware of any other work mentioning the quantity “geometric modularity” that we introduce here). If the reviewer could point us to these works, we could reference them in our paper.

Q. Get rid of parameter choice, what is the point?

The main point here is that there is no such thing as getting rid of parameters. The only way to do this is to set them to default values and show that they are good, or to show that they can be auto-tuned using a data-dependent fashion. We take the latter approach. We believe it is not straightforward to choose $\epsilon$ in a data-dependent fashion, but picking $\rho$ is easier as outlined in Section 4. As $\rho$ can be auto-tuned, once $\rho$ is fixed we use geometric modularity can be used to pick $\epsilon$.

Q. More experiments with HDBSCAN, $k$-means.

Thanks for the suggestion we will add experiments with HDBSCAN. For $k$-means we are less sure what the reviewer has in mind. Selecting $k$ is indeed the part hard of the problem (in practice) and so for a fair comparison that will require us comparing heuristics that are very different from those for density based clustering, which is our focus in this paper.

We will post results with HDBSCAN on this discussion forum as soon as they are available.

Q. Computing modularity in linear time as a contribution.

Graph Modularity would require a computational time proportional to the number of edges of the graph (which is at least as large as the number of vertices). Our new geometric modularity framework takes a more global vision of the dataset (by looking at all pairwise distances) and that can be done in time linear in the number of data elements. This is indeed one of the contributions, and while the proof itself is simple, we believe this is what makes the approach attractive in practice.

Q. I do not see a straightforward break-down if we apply the geometric modularity to other clustering methods, even k-means/median/center. Is there any foreseeable problem?

This is indeed an interesting research direction to explore. However, as mentioned above picking $k$ itself is not usually an easy problem, and unlike in the case of density-based algorithms it is not clear how we would pick $\rho$. Although Geometric modularity with a fixed value of $\rho$, e.g. 0.8 does work well most of the time, to obtain better results, we do need to be able to tune $\rho$.

We thank the reviewer for their comments. We reply to the weaknesses and questions.

Q. Relation to Newman Modularity.

Geometric modularity is a modularity framework for Euclidean spaces, it deals with distances and not similarity edges. This is a fundamental difference between the two definitions. In particular, the definition in Newman would have limited meaning in Euclidean space and would not have the properties that we show for our definition. We note that we have cited Newman’s paper on graph modularity and we will add a citation to this one (thanks for the pointer).

Q. Experimental Results.

DPC always reports one cluster in the experiments we have performed (and simply doesn't run in reasonable time for larger datasets), the bound on AMI follows directly. Although it is possible that hyperparameters of DPC could be tuned, as our key contribution is better auto-tuning of DBSCAN hyperparameters, we believe it is fair that we compare to other available methods out of the box that also claim to autotune hyperparameters. 

The fact that the geometric modularity (for squared Euclidean distance) can be computed in linear time is actually key to the implementation. Computing other measures (as the one suggested below) requires a time quadratic in the number of input points, and so are not scalable. The geometric modularity measure is the only measure among the ones listed above that is scalable.

Q. Writing. Motivation for AMI.

We apologize if the writing appeared as lacking rigor. We are working on an improved version that we will soon post. AMI is one of the most standard ways of measuring cluster quality — proposed as an improvement to NMI which often favors clusters with outliers.  See for example [1].

Q. Description of local search heuristic.

Thank you for your comment, we will add this to the new version we will post. But in short, it is the standard local search approach, tentatively move one point from one cluster (picked at random) to another (random) cluster - accept the move if the geometric modularity increases, reject otherwise. Stop if no accepting move is found for a certain preset number of attempts.

Q. Reproducibility Statement.

We will also include this in the new version we post.

Q. Isotonic Regression.

The only place we suggest using isotonic regression is to autoselect $\rho$. While we expect the #clusters obtained to be a decreasing function of $\rho$, this is not a formal statement as DBSCAN clusters may exhibit different behavior from expectation (this was not the case in our experiments). Since the way we select $\rho$ is to pick the most stable part of the curve for #clusters v $\rho$ we recommend making the curve monotonic (if needed to remove outliers) before picking $\rho$. We will clarify this in the Appendix in the revised version of the paper with some plots and more explanation.

[1] Systematic Analysis of Cluster Similarity Indices: How to Validate Validation Measures. Marijn M. Gösgens, Alexey Tikhonov, Liudmila Prokhorenkova. Proceedings of the 38th International Conference on Machine Learning. PMLR 139:3799-3808, 2021.

We thank the reviewer for their comments. We reply to the weaknesses/questions, which we believe are related.

Q: Why not geometric modularity itself?

Thanks for pointing this out. Optimizing geometric modularity directly is an interesting open problem. Optimizing directly is NP-hard (same reason as the original modularity) and we do not think that classic approaches such as local search would lead to any formal result in this space. We focused on a new algorithm based on DBSCAN because it had interesting theoretical properties (as shown in our paper) and also because the experimental results were quite interesting. We will expand the discussion in the final version of the paper.

Q. Clarification about geometric modularity and differences with prior work.

Thanks for pointing this out. A key difference between the two modularities is that one deals with distances (our case) and the other with similarity. Although the definition of geometric modularity itself does not require $d$ to be a metric, the theoretical analysis we present does as it uses the triangle inequality (our theoretical analysis also works with somewhat weaker variants of triangle inequality, but some constraints are required). This is why we cannot directly adopt a version of modularity defined over weighted graphs; though the definition itself is very similar and is indeed inspired by work in graph modularity.

Q. Performance Gap between OPTICS and DBSCAN.

Although OPTICS does give a way to automatically perform hyperparameter selection on DBSCAN, it does not in fact consider all possible (or even a large range of possible) values of $\epsilon$ and then perform hyperparameter autotuning. Instead, it uses a clever heuristic to order the points according to distances, and looks for steep changes in these distances as a means to identify when a new cluster has been discovered. This parameter $\xi$ is what controls this and its effect is also presented in our additional experiments. This approach works quite well in very low dimensions, but starts to suffer in even modest dimensions.