Hierarchical overlapping clustering: cost function, algorithm and scalability

Thank the reviewer for the valuable comments. We address the concerns as follows.

W1) We totally agree that a running example for all definitions would be extremely useful. For a newly defined problem, there are always too many things to introduce. When we prepared this manuscript, we hope to include as many as possible in the constrained space. So, we move some intuitive examples to the appendix.

W2) OK, we use 2-OC algorithm as a subroutine for the $k$-HOC problem, which is our main purpose in this paper. However, we believe that our 2-OC cost has its own interests since it is a counterpart of Orecchia et al. (2022)’s work that is the baseline competitor in the scalability experiment.

W3) The primal and dual versions of HOC problem are similar to those in the scenario of HC, since for both problems, the sum of the primal and dual cost is fixed. There have been plenty of studies on both primal and dual of HC cost, but not on HOC yet. So, we believe that there are also many problems that worth study along these two lines for HOC.

Q1) Yes, of course. We would like to add another section in the supplementary material (and also adjust the contents in the main body) to illustrate all the definitions.

Thank the reviewer for the valuable comments. We address the concerns one by one.

W1) Due to the space constraint, we only mentioned on Lines 33-36 two possible applications in social and cooperation networks. In our opinion, although we haven’t had a complete example to demonstrate the superiority of HOC structure, since HOC better reflects the real organization of datasets than HC and OC, the study on HOC is significant.

W2) The technical description of the HOC graph and the objective function is generalized from HC trees. Since there are several new concepts, such as belongs factors, minimal common ancestor set, anti-chain, etc., it is really a bit difficult to follow. We will improve the description clearer in further version. We define the directed edges to point upwards like a rooted tree, because we often need to find the minimal common ancestor set of two leaves, which may be convenient if we define it like this.

W3) Yes, a stronger upper bound than $nw(E)$ for the optimal dual cost would be much helpful to improve the approximation factor. If we can show that $OPT \leq \beta nw(E)$, then combining with the factor $\alpha$ we already have, we can get a stronger guarantee $\alpha / \beta$. However, such a non-trivial $\beta$ seems not easy to have, and we think it is a problem of independent interest.

W4) The hardness of $k$-HOC problem is still open. We only know that it is easy when $k$ is as large as the number of edges. For smaller $k$, we don’t know, even if $k=2$.

Q1) Do you mean to have a better guarantee on the graphs that have high objective, or say, on well overlapping clustered graphs? There is some work for HC problem on well clustered graphs, and having similar results for HOC seems interesting also. We have no idea about this problem.

Q2) Hardness of $k$-HOC is open yet.

Thank the reviewer for the valuable comments. We address the concerns one by one.

W1) Sorry for non-intuitive explanations. We say that “although $X$ is nominally a subset of $Y$ , they are possibly unrelated in meaning and clustered by different mechanism”, we mean that even if $X$ is a subset of $Y$, there is not necessarily a directed edge $(X,Y)$ on the HOC graph, because although syntactically we have $X \subseteq Y$, semantically in practice, they may have unrelated meanings from two different systems that are organized by different mechanisms.

On line 191, we can observe that $\alpha_{X,Y}$ in the formula above is defined recursively by layers. The alternate definition afterwards is formulated directly for all pairs $X$ and $Y$. That is, $\alpha_{X,Y}$ is the multiplication of all belonging factors of all parent-child pairs along the unique path from $X$ to $Y$. "keeps the same for the other two cases" means that $\alpha_{X,Y}$ has the same values in the cases of “$X=Y$” and “otherwise” as before, respectively.

In the remark starting on Line 240, the “width” of an HOC graph is defined to be the length of the longest anti-chain of the HOC graph. We say that “it can be considered as a set of key clusters that are close to the leaves on the HOC graph", we seek to capture the “minimal” incomparable clusters. Intuitively, as the clusters aggregate, the cluster level gets high, and the number of incomparable clusters decreases. Consider a non-overlapping HC tree, our definition of width means the number of bottom and smallest clusters, which are the key ones that contain the leaves directly. Similarly, the width of an HOC graph measures the number of the lowest incomparable key clusters that contain the leaves.

W2) Please note that $k$-HOC problem does not restrict to have at most $k$ clusters/nodes. Here $k$ is the restricted width. To be sure, our approximation factor for $k$-HOC is built on that for $2$-OC, but our analysis for $2$-OC is original. In the theoretical study of HC, for both primal and dual problems, a good bipartition is usually the foundation of hierarchical structure. We think HOC is no exception. Regard to the feeling that the dual version is a bit easier to prove for HC, maybe it is due to the hardness of bipartition problem, e.g., sparsest cut, min-bisection, etc., which hinders people to get a constant guarantee for the primal problem of HC. On the contrary, we have constant guarantee for the dual variant.

W3a) Yes, after speed-up for the scalability, the original approximation algorithm (Alg. 2) is not “formally” compared. We think it is acceptable since the speed-up algorithm also follows the local search heuristics (note that Alg. 2 is also a local search). At least, the local search strategy has been verified to be effective and efficient.

W3b) $k$-HOC experiments are only performed on synthetic data because there is no proper real data that has ground truth of HOC. The results corresponding to Dasgupta’s cost in Figure 1 are non-overlapping. The purpose is to demonstrate that compared with using non-overlapping HC cost, our local search algorithm can really benefit from our HOC cost when allowing overlap. Meanwhile, the running time is competitive.

W3c) There is no suitable real data that has manifest ground truth for overlapping clustering, which is the main obstacle in real data evaluation. The experiments on MNIST are devoted to showcase the overlapping data points in our results of image classification. The NMIs in Table 5 are calculated for OC (according to its definition in Section C.1), in which the ground truths are non-overlapping, while our results are overlapping.

Minor points & typos: We thank the reviewer for the advice in organization, format and figure use.

Q1) See the response to W1).

Q2) The hardness of $k$-HOC and 2-OC problems are still open. Due to the complicated form of cost function and the hybrid structure, we don’t think it is easy, and this direction is of independent interest.

Q3) The guarantee of the speed-up version of our algorithm is actually unknown. It is usually a predicament that an algorithm with strict theoretical guarantee is unable to compete with heuristic algorithms or popular solvers. However, we also think that it is interesting to analyze our heuristics for speed-up.

Q4) See the response to W3b).

Q5) The Dasgupta variant return $k$ non-overlapping clusters. See the response to W3b).

Thank the reviewer’s valuable comments. Let us address the concerns one by one.

W1. We provide the formal definitions of cost functions of HC and our HOC in Line 73 (Eq. (1)) and Line 226 (Def 2.8), respectively, and point out that the latter is a generalization from HC by assigning a belonging factor for each minimal common ancestor of each edge. All essential ingredients in our cost function are properly defined in advance. We also provide the cost function for OC in Lines 112-116, which is obviously different from our cost function. Sorry for not having much space to present the differences more.

W2. An evaluation on HOC need an HOC graph model. We have not designed such a model specifically, but utilized the standard OSBM model. The new model design is not the focus of our experiments. We only want to intuitively demonstrate the result of our method by picture.

W3. A major contribution of Orecchia et al. 2022 is the practical nearly linear time complexity of their approximation algorithm. They use the seminal work of Chen et al. (2022) to compute max-flow in theory, but use the HIPR implementation (Cherkassky et al., 1994) of the push-relabel method in experiments. Efficiency is a major contribution in their experiments, and thus we have reasons to believe that they have optimized their implementation. Even if that is not so, please note the huge gap between the runtime of their method and ours demonstrated in Table 1, especially when we consider the difference of experimental operating environments, theirs on a server with 24 Cores and 128GB memory, while ours on a personal computer. This just reflects the value of our cost function (quite different from theirs) and method, simple, easy to implement, and highly efficient.

W4. As we mentioned in the response to W2, the hierarchical aspect should be evaluated by a new HOC graph model. Here, we just use the standard OSBM model for a demonstration. Note that we achieve a high NMI=0.92 on the second level, which implies that the overlapping partition on the first level (as we describe in Line 1452, one cluster of red and yellow, the other one of green and purple) is also accurate.

W5. We agree, and will clarify it early.

W6. Thanks. We will consider our wording carefully.

References:

Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. FOCS, 612-623, 2022.

Cherkassky, B. V., Goldberg, A. V., and Radzik, T. Shortest paths algorithms: theory and experimental evaluation. SODA, 516–525, 1994.

Thank you for your response. On the motivation of HOC, we think that there is no essential difference between point data and graph data. Of course, we are willing to give a more concrete example to clarify the significance of HOC on graphs if we have more space.

Regarding the NMI of zero by the OHC’20 algorithm, it results from the “seemly” total misclassification of the four clusters on the first level. Note that even you have a good clustering for the four ground-truth clusters on the second level, you possibly achieve an NMI of zero on the first level. Consider four equal-sized clusters $A$, $B$, $C$, $D$ on Level 2, and the ground truth on Level 1 are two clusters $A\cup B$ and $C\cup D$. Even you achieve a perfect NMI of $1$ on Level 2, if you have a wrong clustering of $A\cup C$ and $B\cup D$ (while keeping the four intact clusters), then the NMI on Level 1 is just zero! It is actually not a serious mistake that you have misclustered the four clusters on the first level maybe only because of a slight difference in the density of linkage among the clusters, but the NMI is very low. This is also the reason why our HOC algorithm has low NMIs (less than $0.7$) on Level 1 of the first two random graphs, but it has high NMIs (more than $0.9$) on Level 2. In the 5 trials on both graphs, we have one trial each that makes a mistake on the first level and gets an NMI of almost zero. This also causes large standard deviations on these two graphs.

Thank the reviewer. Let us give a practical scenario of HOC. Consider a coauthorship network, in which nodes represent authors and edges represent coauthorship. Then the bottom level clusters are cliques that correspond (although maybe not exactly) to the article that coauthored by a group of people. Since a person is likely to coauthor with many others for many times, such cliques must overlap. However, the granularity of article level is not high enough. Imagine the article level. There must be articles that are written on the same topic (e.g., language model, GNN, clustering, etc.) and include the same author(s). This similarity of articles can be indicated by coauthorship also. Certainly, the topics can overlap (e.g., the article that uses GNN for clustering belongs to the two clusters of GNN and clustering). This forms an upper level of overlapping clustering structure. Moreover, topics belongs to higher level areas (e.g., deep learning, combinatorial optimization, approximation algorithm, etc.), and overlaps happen when a topic belongs to more than one area (e.g., clustering belongs to combinatorial optimization and approximation algorithm, etc.). More widely, (higher) research areas overlap due to interdisciplinary study (e.g., bioinformatics belongs to TCS and biology). This demonstrates a classic HOC structure, and looking at any single perspective of HC or OC alone has its own limitation. We believe that similar story also happens in many other practical scenarios such as social networks, world wide webs, e-commerce websites, etc, which indicates the significance of HOC study on graphs.

Thank the reviewer’s valuable comments. Let us address the concerns one by one.

W1) There are indeed several methods for overlapping clustering, as what we have introduced in the related work. However, except Orecchia et al. (2022) that we choose as the only baseline competitor, no work provides cost function and guarantee on performance, while based only on some heuristics like density or cut metrics during the computing processes. This is why we, and also Orecchia et al. (2022), haven’t contained them as baselines.

W2) Yes, a more extensive evaluation of method is preferable for a new concept. In our paper, cluster number, overlapping percentage, density of clusters, balance of clusters, etc., are all factors that are worth evaluation. We once have a comprehensive evaluation on our 2-OC algorithm that has an excellent performance, but have not presented it in our submission. However, in present version, we mainly focus on the accuracy and scalability of our method. Thanks for your advice to have more experiments.

W3) We are usually in a predicament when we try to involve a baseline method but the source code is hard to compile correctly, especially when it has a complicated computing process for theoretical guarantee. That is the case for Orecchia et al. (2002)’s work. Neither debug nor reimplementation are easy. However, we can see the huge gap between the scalabilities of their work and ours demonstrated in Table 1, especially when we consider the difference of experimental operating environments, theirs on a server with 24 Cores and 128GB memory, while ours on a personal computer. This just reflects the value of our method, simple, easy to implement, and highly efficient.

Small note: Thanks, we will use a proper citation format in future version.

Q1) The NMI for overlapping clustering is proposed by Lancichinetti et al. (2009), and we also give the formal definition in Appendix C.1 (as we state in Lines 445-446).

References:

Lorenzo Orecchia, Konstantinos Ameranis, Charalampos Tsourakakis, and Kunal Talwar. Practical nearly-linear-time approximation algorithms for hybrid and overlapping graph clustering. In International Conference on Machine Learning, pp. 17071–17093. PMLR, 2022.

Andrea Lancichinetti, Santo Fortunato, and János Kertész. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3):033015, 2009.