Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability

We thank the reviewer for the careful review and valuable comments. Let us address the concerns one by one.

1. On the scalability of our algorithm, we have demonstrated it on graphs of size 100,000. Please note that the largest graph in the second row of Figure 2 has size $10\times 10^4=10^5$ (sorry for the tiny text, we will amplify it in our updated version). We did not scale to larger graphs (e.g., 500,000, or 1,000,000) not because our algorithm cannot bear the large scales, but only because the baseline methods cannot, which results in lacking comparison objects for us. That is also why, as shown in Table 1, in our PC environment, we cannot compare with any baseline on large real-world datasets, but just plant in the last column the results from (Orecchia et al., 2022) whose operating environment includes a cluster of machines.

2. Regarding the weak theoretical results, we think that as the first step on the hierarchical overlapping clustering (HOC) study, a constant approximation factor (although not very large) for the dual $k$-HOC problem is not so bad. As a by-product of our theory, our study on 2-OC (which is ever one of the central topics on overlapping clustering before our work) achieves theoretical guarantees on both primal and dual problems. The main obstacle of getting a better guarantee for $k$-HOC stems from the complicated hybrid structure during the recursions of the 2-OC algorithm. Further investigating this process could be an interesting next step on $k$-HOC study. We believe that there is better guarantee since the actual performance of our $k$-HOC as shown in Figure 2 is almost perfect on synthetic datasets.

We thank the reviewer again and are happy to address any remaining concerns.

We thank the reviewer for the careful review and valuable comments. Let us address the concerns one by one.

Q1: Yes, these four conditions of Property 2.6 can be simplified since (3) implies that every $N\in S$ is ordered between $X$ and $Y$. However, we cannot say that it's a maximal set that satisfies (1) and (2) only since (4) is necessary (this also relates to Q4, and sorry for inaccurate statement therein). Please refer to the toy example in Figure 3, Appendix A.2. Nodes $N_1$ and $N_5$ form a maximal anti-chain between $b$ and $R$ satisfying (1) and (2), and the belonging factors of $b$ to them are $1/2$ and $1/4$, respectively. But $b$, $N_1$ and $N_5$ all belong totally to $R$, which makes Property 2.6 abort (rhs=3/4). The reason is that the path $(b, N_2, N_4, R)$ leaks even though $\{N_1, N_5\}$ is a maximal anti-chain, while (4) blocks this leak.

Q2: Yes, the condition after “if” is quite natural, “for any node set S” is better.

Q3: Note that in Fig 1(b), the contribution of cost from $(b,c)$ and $(c,d)$ are $3w(b,c)$ and $3w(c,d)$, respectively, since $|N_1|=|N_2|=3$. By our definition, indeed, the partial assignment of $c$ to $N_2$ doesn’t hurt the cost that $(b, c)$ contributes to. This is because $(b, c)$ belongs entirely only to $N_1$. When $(a, c)$ and $(b, c)$ are removed from $G$, the cost of any HOC will certainly decrease since the edge number becomes less. But now the optimal HOC should be of shape $D_2$ (exchanging labels of $a, b$ and $d, e$) since the MCA of $(a,b)$ has size only $2$. In this case, $D_1$ indeed has negative impact on the cost when compared to $D_2$. This is quite natural and desirable, isn’t it? (Maybe you just have some misunderstanding in calculating the cost of $D_1$).

As for $D_3$, we indeed want to say there is a cost to having too many assignments. But this cost mainly comes from enlarging the clusters themselves after excessive assignments. As long as you agree with our setting that a cluster can be treated as an MCA of an edge only if the edge is entirely contained in the cluster, then everything will be easy to understand. This setting is consistent with Dasgupta’s cost for HC. For example, In Fig 1(c), we do not treat $N_2$ as the MCA of $(c, d)$ even though $d$ belongs to $N_2$. Note that although the assignment of an endpoint of an edge does not impact on a cluster that is not an MCA, it does impact on the belonging factors to all MCAs. As for your doubt that $N_1$ and $R$ should both be partially MCAs of $(b, c)$ in Fig. 1(b), now that we have defined MINIMAL common ancestor, the partial order between two CAs $N_1$ and $R$ should be avoided.

Q4: The statement here is indeed not accurate. Our original intention is to point out the analogue of significance between the longest anti-chains on HC and HOC. But as shown by the instance in our response to Q1, not any maximal anti-chain necessarily blocks all paths from leaves to the root. We believe that a slight modification of this instance will give evidence to refute a longest anti-chain also. The leaf stick that you propose is another counter example and does not violate condition (3) in Def. 2.1. We can only say that a longest anti-chain is located, intuitively, as far down from the root as possible to block leaf-to-root paths. Thanks for pointing out this.

Q5: Sure. We will mention Moseley and Wang’s dual for HC when we define $k$-HOC dual on Page 5.

Q6: Yes, Moseley and Wang proved a similar limitation of $1/3$ off the trivial upper bound $n*w(e)$ for the binary HC clustering. We will briefly mention it in the discussion of Th. 3.1 in our updated version.

(Since there is a strict limit 5000 on the character number, we continue our response in the rebuttal to Reviewer 3QxV on the top.)

We thank the reviewer for the careful review and valuable comments. Let us address the concerns one by one.

1. Regarding the speed-up version that makes the comparison of Algorithm 2 not “formal”, let’s look at the two strategies. The first is a good initialization with two non-overlapping clusters and using “move” instead of “exchange” during local search. We don’t think this harms the results of Algorithm 2 much for the following reason. Let’s consider another process as follows. We proceed Algorithm 2 rigorously first until the exchange-based local search gets stuck. By Theorem 3.6, we get our approximation guarantee $\frac{2}{3\sqrt{6}}-\Theta(\frac{1+\epsilon}{n})$. Then we go on to move nodes following the "move" strategy. Since we move nodes only if the cost gets better, when all nodes get stuck, we have no worse cost than that we have from Algorithm 2, or say, this is also an approximation algorithm with the same factor $\frac{2}{3\sqrt{6}}-\Theta(\frac{1+\epsilon}{n})$. This looks like we have started our local search from a good overlapping initial clustering. The only difference of our strategy is that, in practice, we start our local search from a good non-overlapping clustering, which doesn’t seem like to be as good. However, the almost perfect NMI results in Figure 2 demonstrate that even this strategy that should not seem so good is not bad at all.

The second strategy is batch migration. In Algorithm 2, the nodes are exchanged one by one until get stuck. Now we move more than one node in each iteration. This strategy makes no difference in effectiveness from the original algorithm, because the final state of both process is “getting stuck”. Since the approximation guarantee holds for any initialization, any state that makes all nodes stuck can be viewed as a terminating state with this guarantee. So even Algorithm 2 itself can use batch migration without any loss in approximation guarantee.

2. The definition of NMI metric for overlapping clustering has been provided in Appendix C.3. We have also prompted its place in the paragraph of “Datasets and evaluation” (Page 7) in the main text.

3. Regarding no qualitative results on real-world datasets, we evaluate the effectiveness of our algorithm on synthetic datasets. Due to lack of ground truth on real-world datasets, we are not able to verify the quality of our clustering on them. Nevertheless, we can compute the objective scores as the Reviewer 4xK8 suggested (Q10 therein). However, there is still no way for us to compare it with the baseline methods since no baseline can terminate within a reasonable time on large graphs when run on a personal computer. This also demonstrates the priority of our algorithm in scalability.

4. Regarding W1, we think that 2-OC is the foundation of $k$-HOC, just like that bipartition is the foundation of approximate algorithms of hierarchical clustering. We have paid much attention to 2-OC for both dual and primal versions, and achieved approximation guarantees. Yes, we have not achieved an approximation guarantee for the primal $k$-HOC problem since we have not found a proper way to analyze recursions of 2-OC. We think primal $k$-HOC needs more novel insights and is an interesting open problem.

We thank the reviewer again and are happy to address any remaining concerns.

We thank the reviewer for the thorough review and the recognition of our work. We hope that our study will encourage other researchers to pay attention to hierarchical and overlapping graph clustering, since we think this hybrid structure has a great potential significance in recognizing real-world data organizations.

============================================

(Sorry for occupying this space for the response to Reviewer 4xK8 due to the strict limit on character number.)

Q7: In our proof of Th. 3.3, we focus on the ratio $cost^*_D/cost^*_P$ (Lemma B.4). We want to give an upper bound on this ratio such that proper bounds in terms of $n\cdot w(E)$ can be given to both of them ($cost^*_D$ is far from $n\cdot w(E)$, while $cost^*_P$ is far from 0, the farther the better). Since these two costs correspond to the same 2-OC partitioning, we consider the bilinear forms of both the primal and the dual versions of the cost, that is, bilinear combination of the total edge weights within clusters and the corresponding cluster sizes. Note that the total edge weights within a cluster is the multiplication of cluster size and density. When divided by a size term on both numerator and denominator, this ratio becomes related to density (although there is a size term multiplied on each density). Now the density of the densest subgraph can cover this ratio. Since density is closely related to node degree, we turn the density ratio to degree ratio for better comprehension. When the degree distribution varies wildly, the degree ratio $d max/d avg$ is not a good proxy of density ratio, and the bound in Th. 3.3 is not so good. But when the degree ratio is close to $1$, these two ratios get close, and now the cluster density of each cluster becomes uniform and the cost is mainly determined by the cluster sizes. Now the primal cost is roughly the sum of squares of two cluster sizes (ignoring the bad cut edges outside), while the dual cost is roughly twice of the product of two cluster sizes. This yields a high-quality upper bound for $cost^*_D/cost^*_P$.

Q8: The stochastic block model (SBM) is not hierarchical. It has two variants, hierarchical SBM (HSBM) and overlapping SBM (OSBM), but there has been no variant like HOSBM yet, since an HOSBM, in our opinion, should be built on a proper formulation of HOC graph, just like what we propose in our submission. However, please note that any variant of SBM can be attributed to a (flat) stochastic adjacency matrix, in which the probability can be specifically set for each pair of nodes after calculation. In our settings, the hierarchical and overlapping features have been implied by $p_1, p_2, p_3$ that imply hierarchies and by $1-(1-p_3)^2$ that implies the density within overlapping areas (please refer to the 2nd paragraph of Appendix C.2).

Q9: The formal definition of NMI for overlapping clustering has been given in Appendix C.3. It is a natural generalization of the classic NMI for non-overlapping partition.

Q10: In Fig. 2, we have demonstrated the cost results for all synthetic datasets (see the 2nd column for both levels). For real datasets, since no baseline method can deal with the large graphs listed in Table 1 (with our computing environment of PC), we have no object to compare with. So we didn’t list the costs. However, the effectiveness of our algorithm has been evaluated in Fig. 1. Nevertheless, we have calculated the primal costs of the four networks in Table 1, those are $1.35E11$, $1.63E12$, $1.43E11$ and $1.65E10$ for Amazon, Youtube, DBLP-all and DBLP-cm, respectively.

After all, regarding to W1 on the significance of Algorithm 1, please refer to our response to Reviewer 7SG8, the second item.

Hope we have addressed all the concerns. If there are any remaining questions, we are happy to address them.