Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Authors: Yicheng Pan
Renjie Chen
Pengyu Long
Bingchen Fan
Venue: ICML 2025 poster (2025)
Keywords: hierarchical overlapping clustering
approximation algorithm
scalability
Primary area: general_machine_learning->clustering
TL;DR: We have proposed a cost function for hierarchical overlapping clustering on graphs, and developed an approximation algorithm for it.

Abstract: Hierarchical and overlapping clustering are two prevalent phenomena that often coexist in real-world system. While numerous studies have examined these two structures separately, characterizing and evaluating their hybrid forms remains an open challenge. To bridge this gap, we initiate the study of hierarchical overlapping clustering on graphs by introducing a new cost function and establishing its rationality through several intuitive properties. We further develop an approximation algorithm that achieves a constant approximation factor for its dual version. Our approach employs a recursive overlapping bipartition framework based on local search, enabling a highly scalable speed-up variant. Experimental results demonstrate that this speed-up algorithm outperforms all baseline methods significantly in both effectiveness (across synthetic and real datasets) and scalability.

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Yicheng Pan
Renjie Chen
Pengyu Long'
Bingehen Fan
Abstract
each structure in isolation, the hybrid structure of hierar- chical overlapping clustering (HOC) that permits overlaps between hierarchical clusters offers a more accurate repre- sentation of complex relational data observed in real-world scenarios. For instance, in social networks, an individual may belong to multiple distinct groups, and these groups can form larger overlapping communities centered around different themes. In cooperation networks, the coauthors of paper can be regarded cluster may belong to more than one research field due to the diversity of topics. The inherent complexity of the hy- brid structure presents a formidable challenge in clustering research. While HC and OC have been extensively studied as separate paradigms, the critical domain of HOC remains largely unexplored. In this paper, address this problem.
Hierarchical and overlapping clustering are two prevalent phenomena that often coexist in real- world system. While numerous studies have ex- amined these two structures separately, character- izing and evaluating their hybrid forms remains open challenge. To bridge this gap, we initiate the study of hierarchical overlapping clustering graphs by introducing new cost function and establishing its rationality through several intu- itive properties. We further develop an approxi- mation algorithm that achieves constant approx- imation factor for its dual version. Our approach employs a recursive overlapping bipartition frame- work based on local search, enabling highly scalable speed-up variant. Experimental results demonstrate that this speed-up algorithm outper- forms all baseline methods significantly in both effectiveness (across synthetic and real datasets) and scalability.
base-level cluster, and this
Constructing cost function is a usual starting point for the research on both HC and OC. Similarly, a proper cost function is helpful to evaluate the quality of HOC, which formulates the HOC problem as an optimization task. In this paper, we propose new cost function for HOC, and present an approximation algorithm for it. Our contributions are summarized follows.
1. Introduction
(1) Cost function. We propose a cost function (Definition 2.8) that is the first one for HOC to our best knowledge. The cost function is evaluated on HOC graphs, and can be unified with Dasgupta's cost function for HC trees in the specific case of non-overlap. We give comprehensive study on the rationality of this cost function by providing examples and series of properties including compatibility (Property 2.11). additivity of nodes (Property 2.12) and binary optimality (Property 2.13).
Clustering on graphs is a major task in machine learning and has a wide range of applications in many areas. Two funda- mental categories have attracted in-depth study. The first is hierarchical clustering (HC) that requires recursive parti- tioning of graph into smaller clusters to form cluster tree (Dasgupta, 2016; Li & Pan, 2016; Cddan-Addad et al., 2019; Charikar & Chatziafratis, 2017; Moseley & Wang, 2017:
Naumov et al., 2021). The other is overlapping clustering (OC) that allows data points to belong to multiple clusters (Orecchia et al., 2022: Zhang al., 2007; Shen al., 2009: Chen et al., 2010; Nicosia et al., 2009; Whang et al., 2016; Li et al., 2017; Yang & Leskovec, 2012a). Both structural patterns are prevalent in real systems. Compared to using
(2) Approximation algorithm. Based on our cost function, we formulate the primal and the dual versions of the HOC problem, respectively. We provide an a 3/6 O L+s )- approximation algorithm (Algorithm 2) for the dual KOHOC problem, where E Z is an upper bound of key clusters (explained in Definition 2.10), is the number of graph nodes, and is an arbitrarily small positive constant. We also show that our algorithm achieves approximation factor (1 a) + dmaz/daug) for the primal 2-OC problem.
n
SState Key Laboratory of Complex & Critical Software Envi- ronment, Beihang University. Correspondence to: Yicheng Pan <yichengp@ buaa.edu.cn>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
(3) Effectiveness and scalability. We accelerate our ap-

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
proximation algorithm by some simple heuristics during the local search process, and verify its effectiveness and scalability by experiments. On effectiveness, experimental results demonstrate that on random graph models with good embedded HOC structures, our algorithm outperforms all other baselines and reconstructs the ground truths almost perfectly. On scalability, benefiting from our elaborate cost function and simple local search strategy, on real datasets with around one million vertices and three million edges, the runtime of our speed-up algorithm implemented on sin- gle laptop is only around 20% of the runtime of the fastest baseline method proposed by (Orecchia et al., 2022) that is run on a server with a cluster of machines.
was one of the most popular cost functions for flat non- overlap clustering. Many researchers have extended modu- larity to the scope of OC. (Nepusz et al., 2008) and (Nicosia et al., 2009) proposed the concept of belonging factor that represents the intensity of node or an edge belonging to a cluster. A function of the belonging factor was introduced to the definition of modularity to make it applicable to OC, and heuristic algorithm was proposed based on maximizing the OC modularity. (Zhang et al., 2007), (Shen et al., 2009) and (Chen et al., 2010) also proposed their own definitions of belonging factor and cost functions based on modular- ity. Inspired by these works, our cost function also utilizes belonging factor for HOC.
On the worst-case guarantee analysis for OC, (Khandekar et al., 2014) formulated the problem of minimizing the max- imum or the sum of conductances of overlapping clusters, with or without a bounded number of clusters. They pro- posed the algorithms that achieve Oloog -ppapppoxiiiaooon factors for the four kinds of versions, where n is the number of vertices. The techniques behind the proof include the tree decompositions (Räcke, 2002; 2008; Harrelson et al., 2003) and a dynamic programming. As claimed in their work, the complexity of the dynamic program hinders the scalability of their methods.
1.1. Related work
Hierarchical graph clustering, The most popular cost function for HC is proposed by (Dasgupta, 2016). Given a weighted graph G = (V, E, w) and a cluster tree T, Das- gupta's 's cost is defined as
T (G) Das?
Σ AEEE
why (II
(1)
where V j denotes the least common ancestor (LCA) of and j in T. V(i V j) represents the set of descendant leaf nodes under j. and (i V j) its size. On similarity- based graphs, optimization of HC trees can be performed by minimizing Dasgupta's 's objective. The intuition is that for good clustering tree, the edges with large weights ought to be placed as far down from the root as possible, which makes the number of leaves covered by its LCA as small as possible. Dasgupta also showed that both minimizing Das" DGs"(G) and maximizing Das (G) are NP-hard.
Another representative work for OC is attributed to (Orec- chia et al., 2022), in which two cost functions called e- overlapping ratio-cut (e-ORC) and X-hybrid ratio-cut (A- HCUT) respectively are proposed for OC with two over- lapping clusters. Both cost functions are designed based the ratio-cut objective, and treat the overlapping part of the two clusters as a penalty. Concretely, given a graph G = (V, E, w. μ1) with non-negative edge weights to, vertex measure f4, and two overlapping clusters I. and R of vertices, they define two ratio-cut-like measures to be qF qr|L, L, R] = w(L \ R, R \ L)/ min (((i) (R) and qv [L, R = /)LnR) min(p(L), p()).,((R) (.R).. Then the c-ORC problem is defined to be the minimization of qu [L, R under the condition that Φv [L, R| S e, and the X-HCUT problem is the minimization of qr [T., R] + Aqv [T. Rt). These two problems are defined with hyper-parameters, which restricts the applications and scalability of OC algorithms that solve them. Moreover, since the edge weights w and vertex mea- sure ş are usually derived from independent systems and have different units, the linear combination of qu [4, R] and gv [ R] in X-HCUT is less explainable. However, for both <-OCC and X-HCUT, (Orecchia et al., 2022) gave a nearly-linear-ting Ollog n) japrroximmtio algorithm called cm + improve.
Along this line of study, Dasgupta showed that recursive bipartition applying Arora's 's seminal algorithm for spars- est cut problem (Arora et al., 2009) yields Ollog 1.3 n)- approximation, and it was improved by (Roy & Pokutta, 2016) and (Charikar & Chatziafratis, 2017: Cohen-Addad et al., 2019) to Olog n) and O Vlo respectively. is also known to be SSE-hard to achieve any constant approxi- mation factor for this objective (Charikar & Chatziafratis, 2017). Moseley and Wang studied the dual of Dasgupta's s cost function and showed that the average linkage algo- rithm achieves a (1/3)-appmsl approxiioonnnno (Moseley & Wang, 2017). This factor has been improved by a series of works to 0.336 (Charikar et al., 2019), 0.4246 (Ahmadian et al., 2019) and 0.585 (Alon et al., 2020), respectively. There are also some studies considering the problem of maximiz- ing Dasgupta's 's cost function on dissimilarity based graphs (Cohen-Addad et al., 2019; Charikar et al., 2019; Rahgoshay & Salavatipour, 2021; Naumov et al., 1021).
With regard to HOC, there is much less work. There are two methods for dissimilarity-based vector data, for which some heuristics based on density criterion (Jeantet et al., 2020) and cut metrics (Gama al., 2018) are utilized during the
Overlapping graph clustering. Newman and Girvan pro- posed modularity in 2004 (Newman& & Girvan, 2004), which
2

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
clustering process. However, no cost function and theoreti- cal analysis have been developed yet, which is just what our work addresses.
by R. (2) There are n nodes of D with in-degree of O, corresponding to all the nodes in V, referred to as leaf nodes. (3) For each non-root node of D, its parent node set {N1, NN.......... which is the collection of nodes it points to directly, forms an anti-chain.
2. A cost function for HOC
On an HOC graph, two nodes satisfying X S Y means that V(X) is a subset of (Y)). Note that we do not need the converse also holds, because although syntactically we have V(X) S V(Y), semantically in practice, X and Y may have unrelated meanings from two different systems that are organized by different mechanisms, HOC graph extends the concept of HC tree by allowing each non-root node to have multiple parent nodes that are incomparable with each other. It is canonical representation for hierarchical set containment that subset is only allowed to point to minimal set that contains it. If each non-root node has out out-de one, an HOC graph degenerates into an HC tree. The distance (X, Y) is the length of the shortest path from X to Y. The height of D is the maximum distance from any leaf to the root, that is. max dis(v, R). The width of an HOC graph is the length of the longest anti- chain that consists of non-leaf nodes. For any node N on D, Let N denote the set of N parent nodes and N_ denote the set of N's 's children nodes. Figure demonstrates three HOC graphs of height 2 for a graph G' that consists of two triangles intersecting at a single node, in which D2 is an HC tree without overlap, while the other two are overlapping.. Definition 2.2 (MCA set). The MCA set for nodes and in D is defined as M.n. = {NIN E D,u, V(N), and VX E N-, u & V(X) & V(X)).
In this section, we formulate our cost function for HOC. First of all, we briefly introduce the underlying idea. HOC can be represented by directed acyelic graph, called HOC graph, that is a natural generalization of HC tree. Inspired by Dasgupta's cost function (Eq. 1) for HC, we extend the LCA of an edge to its minimal common ancestor (MCA) set, and introduce the belonging factor to measure the de- gree by which a node, cluster, or an edge belongs to an ancestor. Intuitively, for a similarity-based graph, a quality HOC graph should contain heavy edges into clusters that are small and as far down from the root of the HOC graph as possible. Overlapping is desirable when a node has strong connections to more than one cluster simultaneously, in which case, the belonging factor allows to suppress the cost contributed by the edges incident to that node. This is the crucial idea of our cost function for HOC.
Preliminaries. An undirected weighted graph G (V, E, w) is specified by node set V, an edge set E C {(u, o)lu, v E V}. and a weight function w : E + R+. Let n = [V] and m = [E] represent the number of nodes and that of edges, respectively. The degree of a node u, denoted by du, is the sum of weights of all edges inci- dent to u, i.e., du = E(ug)e w(u, v). Denote by G[U] the induced subgraph of G on the node set U. For any A, B&B C V. let E(A)- = {(, (u, E E, E,u,v E A), E(A, B) (uu, ((,,)) E E,u E A, E B}. w(A) E(u.)EE(A) w(,,)) w)A,B) B) = ((U.)EE(A,B) w(u, v). For node V, V,,(e, A) = EOEA(VE w(v, a). For any E' C E. E. EeEr w(e).
The term "minimal" in the above definition means that any child node of this common ancestor of and v is not a common ancestor any more, and thus cannot be further reduced. This is an extension of the unique LCA on HC trees to multiple ones on HOC graphs. For convenience, when u, v are two endpoints of an edge, we also say a common ancestor of this edge (u, u). As illustrated in D3 of Figure I, Mac = NN), Moe = (R).
Partial ordering relationship of two nodes N and N' on directed acyclic graph D, denoted by N < N', means that N' is reachable from N, and we say that N and N' are comparable in this case, and incomparable otherwise. An anti-chain L- = {N1, Ny.... on D is a set of nodes on D satisfying that any two nodes T. are incomparable.
Then we introduce belonging factor that is a key ingredient of our cost function. We define two kinds of belonging factors an HOC graph D, node-to-node and edge-to- node belonging factors, that are generalizations of those proposed by (Nepusz et al., 2008) and (Nicosia et al., 2009) for OC. The belonging factor of node X (resp. edge (n, v)) to node Y represents the degree for which X (resp. edge (u, v)) belongs to Y.
HC on graph G is represented by an HC tree T. It has n leaves corresponding to the nodes of G. For any internal node N, let V(N) be the set of leaves that treat N as an an- cestor. Let u V be u and o's LCA on T. A weighted graph G c= (V, E, w) is similarity-based if the larger wou,, v) is, the more similar u and v are. The cost function for HOC dis- cussed in this paper is proposed for similarity-basee graphs.
Definition 2.3 (node-to-node belonging factor). The node- to-node belonging factor of X to Y, denoted by ax,y, is defined recursively. First, define the node-to-node belonging factor for each parent-child node pair on D, whose value can be assigned freely as long as it satisfies the following two constraints: (1) 0 S axx S for all X D and
Definition 2.1 (HOC graph). Given a graph G, an HOC D) on G is a directed acyclic graph that satisfies the following three constraints: (1) There is only one node of D with out-degree of 0, referred to as the root node and denoted
3

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
d
R
N 2
N
b
(a) The original graph G (b) HOC graph D1
(c) HOC graph D2
(d) HOC graph Ds
Figure An example HOC graphs. The costs (C)(C) = 18, Pa (C) = H1 Pa (G) = 24.
YE (2) ox,y = 1 for each non-root node X E D. Second, for other relationships X and Y, ax,Y defined as
(u, ) in graph G, let X E Mun be one of its MCA. The edge-to-node belonging factor (((..e) of (u, v) with respect to X is defined ((,,)) J/u,y)/ EYEM.. K(a.o) where
f (a.0) au,X Qe.X.
Σ NEX- OX,N ANY
X Y
aX,Y
B ((u.w) is normalized over all MCAs of (u, 2) guarantee that the mass of its belonging factors to its all MCAs sums to 1. A natural option is the uniform allocation to each parent. That is, for each non-root node X E and Y e X
otherwise
To hetter understand the belonging factor, we give an equiv- alent and intuitive definition via path-oriented interpretation, thereby uncovering the multiplicative intuition embedded in this concept. For any two comparable nodes X Y. denote by Px,y the of all paths from X Y. For each path p [Po,Pi P.. Pten(p)) E Px,y, let po X, Pten(p) = Y, len(p) be the length of p. Then the node- to-node belonging factor axxY is equivalently defined as QX,Y EpePx.y [( Opp.P::+1 if $ Y.X # Y. and has the same values as Eq. (2) for the other cases. That is, ox, is the sum of the multiplication of all be- longing factors of parent-child pairs along each path from X to Y. The equivalence is easy to verify by induction. The node-to-node belonging factor has some fundamental properties.
1
OX.Y
X-I
33)
We adopt this definition of belonging factor Section As illustrated in D1 of Figure 1, the leaf has two minimal ancestors N1 and N2, for each of which has belonging factor 1/2, and all edges in G' belongs totally to N1 No. In D3. the leaves b, and d have both N1 and N₂ as their minimal ancestors with belonging factor 1/2 to each, and the edge- to-node belonging factors of (b, c) and (c, d) to either N₁ or N₂ are 1/2. We also demonstrate another toy example of 3-length path in Appendix A.2.
Now, we ready to introduce HOC cost function based the edge-to-node belonging factor.
Property 2.4. If Y is the only parent node of X, then αx,Y = 1. Property 2.5. The node-to-node belonging factor of any node to the root is 1, that is, NN,R for any N E D. Property 2.6. For two nodes X, Y of satisfying S and any node set 5, if (1) 5 an anti-chain, (2) for any p E Px,,, Ip Ss 1, then xxxy Eveg axNN ON.Y
Definition 2.8 (cost function for HOC). Given a graph G and an HOC graph of G, the cost function of D on G defined
HD(G)= Σ w(u,v). v)
(uan -MVVVVV NEM
Σ
(u.N)E
Property 2.4 unifies HOC graph and common HC tree. Prop- erty 2.5 coincides with the common sense that any cluster and leaf belong totally to the root. Property 2.6 implies that the node-to-node belonging factor of X to its ances- tor Y can be disassembled by some (minimal) anti-chain that blockades all paths from X to Y. The proofs of the above properties are provided in Appendix A. Based on node-to-node belonging factor, we define the edge-to-node belonging factor as follows.
The cost function contains two summations. The first is over all edges, and the second is over the MCAs the endpoints of corresponding edge. Compared with Dasgupta's cost function (1), H (G) generalizes it from HC to HOC by assigning belonging factor for each MCA of each edge.
Definition 2.9 (HOC problem). The HOC problem on a similarity-bas based graph G defined as minp H (G)) under some proper constraints on the HOC graph D.
Definition 2.7 (edge-to-node belonging factor). For an edge

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
The intuition behind minimizing the cost function on similarity-based graphs is the same as Dasgupta's cost func- tion, that is, to assign heavy edges to the clusters as small as possible. On an HOC graph, this can be achieved by ensuring that the MCAs of these edges are as far down from the root as possible.
graph by recursively calling 2-OC algorithm in a top-down fashion. In Section 3, our algorithm for k-HOC proceeds in this way.
Next, we give some fundamental properties of our HOC cost function, and prove them in Appendix A.4.
Property 2.11 (Compatibility). If D is an HC tree, then (G) Das DG) = -((a,)e w(u, v) lu V vl.
As illustrated in Figure 1, according to Definition 2.8, the costs of D1. D2 and D3 are 18, 21 and 24, respectively. We provide the calculating process in Appendix A.3. We can see that D1, which is intuitively more reasonable than D2 and D3. has the smallest cost. It is also demonstrated that introducing overlaps has the advantage of reducing the MCAs of edges, thereby decreasing their costs (compare D2 to D1). On the other hand, this comes at the expense of increasing the number of descendant leaves of the ances- tors. So, excessive overlap gets punished (compare D1 to Da). Therefore, our cost function balances insufficient and excessive overlaps.
Property 2.12 (Additivity nodes). For any node N D. let ER denote the set of edges treating N as an MCA, i.c., EX = v),, E E,N E Marh- The HOC cost function can be rewritten as HD(G)= = ENED (V(NV) E(W.DEE ((M,,)) w((u,)).
Property 2.13 (Binary optimality). As long as the con- straints for the HOC problem are not violated, binary branch- ing on each non-leaf node (i.e., the number of children is at most 2) is desirable for an optimal HOC graph.
Property 2.11 indicates that our cost function for HOC can be unified with Dasgupta's cost. That is, under the constraint of hierarchical non-overlapping clustering, for HOC problem degrades to Dasgupta's 's objective whose optimization is NP-hard (Dasgupta, 2016). Property 2.12 provides an alternative interpretation of the cost function from another perspective, for which it can be seen as the sum of costs associated with each node. Note that Dasgupta's ' cost also has the last two properties.
Remark. Note that HOC is quite different from HC since it allows possibly an exponential number of overlapping clusters without any restriction, and thus proper constraints on D are necessary. However, we need to be very careful in formulating the constraints. In fact, there is trivial solution that treats two endpoints of each edge as a cluster, which achieves the minimum cost 2w E). This solution is in fact an intuitive way for overlapping cluster settings since only similar nodes can be linked together, but due to the large number of clusters, it makes no sense. This quite different from the optimization of Dasgupta's 's cost function for HC. A natural restriction HOC graphs may be on the number of clusters. However, since an HOC graph has hierarchical clusters, we seek to have a meaningful constraint on the cluster number. To this end, we utilize the width of an HOC graph, which is the length of the longest anti-chain on it. Definition 2.10 HO- problem). The k-HOC problem on similarity-based graph G is defined as minp H HP(() (G) for which the width of the HOC graph D is at most k.
cost function
Primal and dual versions of HOC problem. Next, we introduce the primal and the dual HOC problems. Note that besides the trivial lower bound 2w(E) for HD(G). we also have a trivial upper bound nw(FF, since the size of any common ancestor of two leaves on D is at most n. So, we define the primal k-HOC problem, denoted by k-HOC-P, to be (HI as Definition 2.9. We define the dual k-HOC prob- lem, denoted by k-HOC-D, to be maxd(nw(E)) (G))), that is, by Definition 2.8, maximizing BN E(,,)) (w(u,w) ENEM,,. (n.w) (n (V(N)I) over D. This cost the compatible counterpart of Mosley and Wang's dual HC cost (Moseley & Wang, 2017) in the HOC setting. The solutions to the primal and dual problems achieve optima on the same HOC graph. Similarly, let k- OC-P and k-OC-D denote the corresponding versions of OC problem, respectively.
To better understand this problem, let us consider a non- overlapping HC tree first. Therein, the width means the largest number of bottom and smallest non-overlapping clus- ters whose children are all leaves. They can be considered as a set of key clusters that are closest to the leaves on the tree. Similarly, on an HOC graph, since a longest anti-chain is located, intuitively, as far down from the root as possible to blockade leaf-to-roon to-root paths, the width measures the number of incomparable bottom clusters that contain the leaves.
3. An algorithm for HOHOC
Moreover, define k-OC problem be the H-HOC prob- lem in which we additionally restrict the height of D at most 2, in which case HOC degrades to OC. A fundamental case is 2-OC that allows only two overlapping clusters. 2-OC can be considered as a key ingredient of HOC with multiple clusters since it could be a nice way to construct a HOH
In this section, propose our algorithm for the k-HOC problem. We adopt Eq. (3) as the node-to-node belonging factor. Since our algorithm is recursive process of 2-OC, we study 2-OC first, and then apply it to k-HOC Note that overlapping bipartition is a fundamental problem for OC, and is also the theme (Orecchia et al., 2022)'s 's theoretical
5

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Algorithm 1 Algorithm for 2-OC
initialization). After that, the nodes in A, B, C exchange pairwisely the condition that current cost can be am- plified by 1+ e/n² times, that is, costtemp (A', B', C") > (ere/nn")costemm((4 B, C) where A,, B', C' are the node sets after exchanging corresponding to A, B, C respectively, and E > 0 is a small constant. It doesn't tt terminate until no pair of nodes meets the exchange condition. For the worst- case guarantee, we have the following theorem.
Input: an undirected graph G (V.E.w) w) Output: node sets A, B and C' for 2-OC 4 |V v
2 f 1p2p
Define a new costremp (Aammmp(AAA) (A, C) = w(E) - w(A, + aw(B)
Divide arbitrarily V into three disjoint parts A, B, C satisfying |A| |C| = pn, B = 2p)n, such that the edge with the maximum weight are not in E(A, repeat
Theorem 3.1. Algorithm I achieves an approximation fac- 2 - -(=+)) for 2-OC-D with time complexity
for 3v6
Exchange any two nodes from different sets of A, B, C whenever costremp can be amplified by more than 1+ e/n" times
O(e n2 log m) for any c > 0.
The idea of the proof of Theorem 3.1 is as follows. Since nww(E) is a trivial upper bound on the objective function, we only have to show that costaual
until get stuck
return A, B, C.
2 0 (((
3.8
nw E). Since Algorithm 1 fixes the sizes of A, B, C, we only need to build the relationship between (E) and edge weights of different parts in the cost function. A lower bound on the latter related to w (E) (Inequality (11)) can be obtained by the three stuck exchange conditions when the iteration terminates. The detailed proof of Theorem 3. is provided in Appendix B.2. Moreover, we have the following proposition to demonstrate the tightness of our guarantee in some sense.
study. So our 2-OC problem has its own interests from the perspective of our new cost function. Compared with the complicated "cut-matching and improve" approach of (Orecchia et al., 2022), our method for 2-OC takes a simple local search heuristic based on our cost function, which makes our algorithm much more scalable.
3.1. An approximation algorithm for 2-OC
Cost functions for 2-OC. In the 2-OC setting, given a graph G = (V, E, w), we restrict the height of the HOC graph to 2 and the number of children of the root R to 2. Suppose that two clusters N1 A UUA B and N2 = B. By Definition 2.8, the cost function of 2-OC-P can be formulated as costprimat (A, B, C)- =
Proposition 3.2. For the complete graph Km, the optimal 2-OC-D value OPT(Ka)
3/6 -0( ner(E).
Proposition 3.2 implies that, if an approximation algorithm for 2-OC-D is designed based on the upper bound nw E)) of costduol. the optimal approximation factor cannot be better than 3/6 ( Its proof is provided in Appendix B.3.
CU B overlap
[w((A) + w(A, (IA + BJ) + [w.B, B, C) + w (
ICI) + [LAI+2[BI+ B BB) + woA, (A, C)n, and 2-OC-P can be
Approximation guarantee algorithm for 2-OC-P. We also show that Algorithm algorithm for 2-OC-P. We simply treat the output of Algo- rithm as the result for 2-OC-P, and we have the following approximation guarantee for 2-OC-P.
formulated
actually a good approximation
min A,B.CVV
(A, cost (A, B,C)
(2-OC-P)
We also have the cost function cost (A, B)C) = (w((+
B) ((B) |C| + (w(B+ + +C- mn(B) ||| for 2-OC-D, and
Theorem 3.3. The approximation factor of Algorithm I for 2-OC-P is - a)(1 + dmaa fimaz/dan dang).. ) where dman is the maximum degree of all nodes, davg is the average degree, and a 2 - 0 ((_tt).
2-OC-D can be formulated as
costaval (Ast C,) A.B.CCV
max
(2-OC-D)
3/6
The derivation of the forms of costprimal and costaual is presented in Appendix I. We remark that although our cost functions for 2-OC look complicated, they are hyper- parameter free and natural from the perspective of HOC, which is superior the objective proposed by (Orecchia et al., 2022). Then we propose our algorithm for 2-OC.
We prove Theorem 3.3 in Appendix B.4. By this theorem, we have two corollaries for regular and bounded-degree graphs, respectively.
Corollary 3.4. If the graph G is d-regular, then the approx- imation factor of Algorithm 1 for 2-OC-P on G is 2(1 a).
Approximation algorithm for 2-OC. Algorithm is sim- ple local search process for 2-OC. It first defines a surrogate cost function costsemp (A, B, C* = w(E) w(A C) +
Corollary 3.5. If the degree of each node in unweighted graph G is upper bounded by a constant d, then the ap- proximation factor of Algorithm 1 for 2-OC-P on G is (1 + d)(1 a).
rw B), and initializes A, B, C arbitrarily (e.g. a random
6

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Algorithm 2 Algorithm for k-HOC
bitmap of each internal node whose length is n indicates the memhership of each leaf. It is necessary check whether ((k) bitmaps are the same, which takes (nk log k) time, In the edge removing step, redundant edge (X, Y) can be identified by reversing it and checking the reachability from X to Y. This takes O(n + k)9) time. Combining all three parts, the total runtime is Okk "nn" log m).
Input: an undirected graph G (V, E, w). an integer
k S
Output: k-HOC graph D
initialize D with all leaves pointing to the root r
S + [r}
repeat
Xmaz f- arg m (A(X)
For the approximation guarantee, we have
Apply Algorithm 1 to the subgraph induced by X and obtain two internal nodes Xr, XR
Theorem 3.6. Algorithm 2 achieves an approximation fac- tor 2 O l+t)) for the dual k-HOC problem.
S 3 S) {XXaz) S + SU (X1, Xn)
3/6
Add x and N to D as Xmaz's left and right child, respectively, and redirect the leaves to their correspond- ing parents
Proof. To prove Theorem 3.6, we only have to show that the dual cost is least that of Algorithm which is lower bounded by
2 - - -nw(E). Then the approx- 3/6
until |S] = k or each set in S has size
imation factor follows from the fact that nw upper bounds the dual cost of any HOC graph.
Merge identical nodes in D into a single one while keep- ing all the connections on them Remove all redundant directed edges (X, for which there is another path from X to Y in D return D.
Note that Algorithm achieves a dual cost at least 3-0 ((+))) -nw(E) for 2-OC-D, in which nw((E is an upper bound for the cost of the dual HOC problem with any constraints. So, Theorem 3.6 follows if the final dual cost is no less than the one after the first round of invoking Algorithm 1.
3.2. An approximation algorithm for k-HOC
Now we turn to k-HOC. We assume that & I n for practical significance. Since the width of the HOC graph is no more than k; we invoke the 2-OC algorithm k - 1 times to guar- antee this. We first construct a binary tree (excluding the leaves) for the internal nodes, and then merge the identical ones that consists of the same set of leaves, while keeping all directed edges on them. In each iteration, the splitting cluster is chosen greedily according to the relative benefit of cost. Formally, we define A(X)= = costauat (X) for the most bottom clusters X, where costauet (X) ) is the dual cost obtained by the 2-OC algorithm on the subgraph induced by
Let N₁ and N₂ be the two overlapping clusters that Algo- rithm 1 yields in the first round of the repeat loop, and E E be an edge that treats Ni or N2 as common ancestor. Then the root is not an MCA of e, since otherwise, forms an chain with N1 or N₂. In the next iterations, r will not be included in the MCA set of e during both splitting and merg- ing process. Since N, and N₂ have the same size, no matter how the belonging factors of e change, the final primal cost that e contributes will not exceed that after the first round of invoking Algorithm 1. This proves Theorem 3.6.
[=(()
X. In each round, we choose the X with the largest A(X) to split. This procedure is described as Algorithm 2.
A speed-up version. Algorithms 1 and 2 have theoretical significance, but are not efficient enough in practice. More- over, the setting of fixed sizes of A, B and C' in Algorithms is too rigid to fit for flexible scenarios. For scalability and practical application of our algorithm, we propose the speed-up version (Algorithm 3) of Algorithm I and use it in Algorithm 2 to yield our speed-up up algorithm for HOHOC. Their effectiveness and scalability will be verified in Section 4. Two easy heuristics are proposed for acceleration, and the pseudocode is presented as Algorithm 3.
Now we show that D output by Algorithm 2 is a legal k- HOC graph. By definition 2.1, we have to show that the parents of any non-root node form an anti-chain, and the width of D is at most k. For any node X, since we remove all the directed edges (X,Y) YY for which there is another path from X to Y in D, X- is obviously an anti-chain. Since times, the width of D before merging is at most k. Since merging does not increase the width, the final D is a HOHOC graph.
the 2-OC algorithm is called for at most
(I) Initialization based on ratio-cut (Hagen & Kahng, 1992):
Instead of the random strategy for the initial trisection, we use the spectral clustering algorithm RatioCut to split the node set into two pieces, denoted by X, Y, let A = X, B = 0, Y Then the nodes move greedily among A, B, and C instead of exchange.
Time complexity. The runtime of Algorithm 2 consists of three parts: the recursive division, merging identical nodes and removing redundant edges. In the division step, it calls Algorithm 1 at most A= - times, which takes O(ke-1n 'n log m) time. In the node merging step, an ef- ficient implementation leverages bitmaps and sorting. The
(2) Batch migration: Starting from the initial A, B, C,
7

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Algorithm 3 Speed-up algorithm for 2-OC
that consists of the top-A eigenvectors of the Laplacian ma- trix. Since this method need deal with pal- distance, it is not able to work on large graphs.
an undirected graph G (V, E, w). batch migra- tion number L
Input:
Output: node sets A, B and C' for 2-OC
cm cm+ improve (Orecchia et al., 2022) is a nearly linear-time Ollog n) japproxximation algorithm that works for overlap- ping bipartition only. We substitute cm + improve for the 2-OC algorithm that used in our k-HOC process. How- ever, there are many hyper-parameters to adjust in it, and we have chosen some mild values in experiments.
X,Y < RatioCul(G)
A + B C.
repeat
Calculate the delta of costatat when each node moves to the other two sets, and select the one with the larger increment as the potential action at that node
Datasets and evaluation. For synthetic datasets, we employ the overlapping stochastic block model (OSBM), a gener- alized version of SBM that allows for overlapping clusters. We introduce it in Appendix C.I. In our experiments we modify OSBM to preset two hierarchies. We assume that each node belongs to at most two clusters. Thus, the total number of nodes is exactly the sum of entries in the upper triangle of the membership matrix Z. For simplicity of implementation, all clusters are of the same size and have the same size of overlaps between clusters. For a 2-level hicrarchical structure, we choose three probability values 0 S p1 S P2 S P3 S 1, in which p1 is the inter-link proba- bility between clusters on the first level, p2 is the inter-link probability between clusters on the second level, and Ps is the intra-link probability within each cluster. So now, the probability of edge presence between any two nodes in the overlapping region is - (1 - pa)².
Let S be the node set that brings costdual increment L + min([]]) ()
Move the top-t nodes with the largest increment until S is empty
return A, B, C.
calculate the variation of the cost for each node when it moves to another set, and select batch of l nodes with positive and the largest variation of cost to move in one step UNTIL all nodes get stuck. In our experiment, we set f = 32. If there are less than nodes that need to move, we move all of them.
Replacing Algorithm with Algorithm 3 in Algorithm 2, we get the speed-up version of k-HOC algorithm.
4. Experiments
We use NMI for OC (McDaid et al., 2011) for evalua- tions, and its formal definition is provided in Appendix C.2. Since NMI is only suitable for non-hierarchical clus- ters, we evaluate our algorithm at each level of HOC graphs. For real datasets, we adopt Amazon, Youtube, and DBLP (Yang & Leskovec, 2012b) that are provided by http::/ssapp http://aaa.ssaaa....o.. used in (Orecchia et al., 2022). Due to lacking ground truth for HOC, we onlu evaluate scalability on the real datasets.
In this section, we verify by experiments the effectiveness and scalability of the speed-up version of Algorithm 2, which demonstrates the validity of our cost function as well. Our experiments were performed on a personal computer equipped with 2.3GHz quad-core Intel i5 processor with 8GB memory. For the source codes and datasets. please refer to https: / h/gittttuuu wig...hb..... com/ Hardict, /HOC.
edu / data a and are also
Baselines. We include three baselines, named Dasgupta, OHC'20 (Jeantet et al., 2020) and cm + improve (Orecchia et al., 2022), respectively. The latter two are not fit for the HOC settings directly and require some modifications. Then introduce each method and our modifications.
Effectiveness. We demonstrate in Figure 2 the results on OSBM datasets with varying sizes. We show the time, cost, and NMI results of our k-HOC algorithm and the baselines. It can be observed that the runtime of our HOC algorithm that generates four overlapping bottom clusters for dense graph of size 5000 is only around 80s, and that for sparse graph of size 10 is less than 15min, while keeping ex- tremely high NMIs. We do not show the results of OHC'20 for sparse graphs since it is not able to terminate in one hour for graph of size 10a. The cost results indicate that our algorithm outperforms OHC'20, and we have indeed gained benefits of cost from overlapping when compared with the non non-overlapping counterpart of Dasgupta's 's cost. We evalu- ate NMI on the two hierarchies respectively. For OHC'20, since it cannot restrict the hierarchy numbers, in each round of evaluation, we choose the level that achieves the highest NMI compared with the ground truth. The NMIs of our
Dasgupta is simply the speed-up version of Algorithm 2 except that it always keeps B empty in the subroutine Al- gorithm 1. So, it degrades to optimizing Dasgupta's 's cost with width l in our local search fashion. We adopt this baseline in order to see whether we can really benefit from overlapping compared with the non-overlapping counterpart of Dasgupta's cost.
OHC'20 (Jeantet et al., 2020) works for HOC on dissimilarity-base based vector data only. It is a density-based algorithm that proceeds in an agglomerative bottom-up fash- ion. To fit to similarity- based graph clustering in our set- tings, we feed to OHC'20 as input the spectral embedding
8

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
1040
1.0
1.0
10a
10"
0.8
tmesis)
10"
MDC cost
10a
THU LeLeee
0.6
0.4
0..4
104
Dasngtt
107
0.2
C20
109
10a
2
(500))
num of (o0es()e500)
of 500e
of nodes]/c5000
1400
1.0
1.0
1200
0.9
1000
(imess)
800
HDC csst
1011 Jevell
0.0
mm) Iev87
0.8
1034
HDc
0.7
0.6
10'
0.6
200
0.5
HGC
HDC
0.5
10
10a
7 num nodes (x101)
num nodes (x101)
num nodes (H1)
num modes (X101)
Figure 2. The results of time, cost, and NML. In each figure. the z-axis indicates the graph size. The graphs in the first row are small and dense, while those in the second row are large and sparse. We take k: = in OSBM, and in each cluster, the size ratio of overlapping non-overlapping is 9:1. In the fist row, Pl 10 P2 x 10 3 Ps 0.5. In the second row, Pl 10 P2 2 x 10 ps = 5 x 10-3. Regard to the last two columns of NMI results, "level 1" is the first level that contains the two high-level clusters, and "level 2" the second one that contains the four low-level clusters. Each point calculated on average over trials, and error bar indicates standard deviation.
k-HOC algorithm on both levels are almost 1.0 on dense graphs, and also above 0.95 on sparse graphs, which demon- strates that it achieves high accuracy in reconstruction each level. We visualize a result in Appendix C.4.
benefits from our elaborate cost function and the simple local search strategy.
Table I. Scalability performance on real datasets
Scalability. The first column of Figure 2 has demonstrated that our k-HOC algorithm is efficient on synthetic graphs, especially much better than OHC'20. Next, on large real datasets, we show in Table the advantage of our algorithm over cm + improve in scalability. For a fair comparison, compare our 2-OC algorithm with it. It can be seen that the runtime of our algorithm that is run a laptop on all datasets is much shorter than the runtime of cm + improve that is run on a server 1 In particular, on Youtube dataset that has around one million nodes and three million edges, the runtime of our algorithm implemented on a single personal computer is less than 12 minutes, which is only around 20% of the runtime of cm + improve that run on server. Although (Orecchia et al., 2022) has showed that cm + àmprove has nearly linear runtime based on the solid nearly linear-time algorithm of (Chen et al., 2022) for the maximum-flos problem, they actually use the HIPR implementation (Cherkassky et al., 1994) with the push- labeled method. This possibly limits the efficiency of em + improve. The advantage of our algorithm in efficiency
dataset
n
m
time
cm time
Amazon
334863
925872
<3min
15-18min
Youtube
1134890
2987624
< <12min
55-75min
DBLP-all
317080
1049866
<3min
DBLP-cm
83114
409541
<1s
2-4min
5. Conclusions and future work
Conclusions. In this paper, we study the HOC problem on graphs from the aspects of cost function, algorithm and scalability. We have proposed a cost function and given some fundamental properties. We have developed an ap- proximation algorithm that achieves constant factor for the dual k- H-H problem. A speed-up version of our algorithm based some easy heuristics during local search has good performances in HOC reconstruction and good scalability.
Future work. There are many directions worth further study. The first is about approximation algorithm for the primal k-HOC problem for k > 2. Although we know the complementary relationship between the primal and the dual problems, the approximation guarantees are quite different. The second is about variant versions of the HOC problem, c.g., having other constraints on HOC graphs and alternative definitions of node-to-node and edge-to- belonging factors. These flexible settings may adapt to different application scenarios.
cm + improve can't 't terminate in a few hours on too large datasets when it is run on our computer. Due to the mismatch of computing resources, the results in the last column of Table I are from Table 3 of the original paper (Orecchia et al., 2022) whose experimental operating environment reported to include a cluster of machines with 24 Cores (2x 24 core Intel Xeon Silver 4116 CPU @ 2. 10GH2), 48 threads and 128GB RAM. In sharp contrast, we have only used personal computer.

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Acknowledgements
Cherkassky, B. V., Goldberg, A. V., and Radzik, T. Shortest paths algorithms: Theory and experimental evaluation. In Sleator, D. D. (ed.), Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA, pp- 516-525. ACM/SIAM, 1994, URL http: http:/dd.aacee acm. org/ citation. cfm? 11=:1d==311- 4464. 314
The authors gratefully acknowledge the anonymous review- ers for the constructive comments that have improved this work. This work partly supported by National Key R&D Program of China (2021 YFB3500700), and partly supported by State Key Laboratory of Complex & Critical Software Environment (CCSE-2024ZX-20),
Cohen-Addad, V., Kanade, V., Mallmann- Hallmann-Trenn, F., and Mathieu, C. Hierarchical clustering: Objective functions and algorithms. Journal of the ACM (JACM), 66(4): 2019.
Impact Statement
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Dasgupta, S. A cost function for similarity-baser hierarchi- cal clustering. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 1 118-127, 2016.
References
Gama, F., Segarra, S., and Ribeiro, A. Hierarchical overlap- ping clustering of network data using cut metrics. IEEE Trans. Signal Inf. Process. over Networks, 4(2):392-406, 2018.
Ahmadian, S., Chatziafratis, V., Epasto, A., Lee, E., Mah- dian, M., Makarychev, K., and Yaroslavtsev, G. Bisect and conquer: Hierarchical clustering via max-uncut bi- section. arXiv preprint wrXiv:1912.06983. 2019.
Hagen, L. and Kahng, A. New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Sys- tems, 11(9):107410885, 1992. doi: 10.1109/43.159933
Alon, N., Azar, Y., and Vainstein, D. Hierarchical cluster- ing: A 0.585 revenue approximation. In Conference Learning Theory, pp. 163-162. PMLR, 2020.
Arora, S., Rao, S., and Vazirani, U. Expander flows, geo- metric embeddings and graph partitioning. Journal of the ACM (JACM), 56(2): 2009.
Harrelson, C., Hildrum, K., and Rao, S. A polynomial-time tree decomposition to minimize congestion. In Proceed- ings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 34-43. ACM, 2003.
Charikar, M. and Chatziafratis, V. Approximate hierarchical clustering via sparsest cut and spreading metrics. In Proceedings of the Twenty-Eights Anmual ACM-SIAM Symposium on Discrete Algorithms, pp. 841-854. SIAM, 2017.
Jeantet, I., Miklós, Z., and Gross-Amblard, D. Overlap- ping hierarchical clustering (OHC). In IDA, volume 12080 of Lecture Notes in Computer Science, pp. 261- 273. Springer, 2020.
Khandekar, R., Kortsarz, G., and Mirrokni, V. S. On the advantage of overlapping clusters for minimizing conduc- tance. Algorithmicaa, 69(4):844886 863, 2014.
Charikar, M., Chatziafratis, V., and Niazadeh, R. Hierarchi- cal clustering better than linkage- In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Dis- crete Algorithuss, pp. 2291-2304. SIAM, 2019.
LeCun, Y., Bottou, L.,, Bengio, Y., and Haffner, Gradient- based learning applied to document recognition. Proceed- ings of the IEEE, 86(1 2:228823344 1998.
Chen, D., Shang, M., Lv, Z., and Fu, Y. Detecting over- lapping communities of weighted networks via a local algorithm. Physica A: Statistical Mechanics and its Ap- plications, 389(19)4417744888 2010.
Li, A. and Pan, Y. Structural information and dynamical complexity of networks. IEEE Transactions on Informa tion Theory, 62(6):3290-3333) 2016.
Chen, L., Kyng, R., Liu, Y. P.. Peng, R., Gutenberg. M. P., and Sachdeva, Maximum flow and minimum-cost flow in almost-linear time. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Den- ver, CO, USA, October 31 November 3, 2022, pp. 612- 623. IEEE, 2022. doi: 10. 10.1009FOCCS445522222222 2022..7..22200020 URL https:: /tt....o/g/...111////555./ 2022. 00064.
Li, P., Dau, H., Puleo, G., and Milenkovic, O. Motif cluster- ing and overlapping clustering for social network analysis. In IEEE INFOCOM 2017-1EEE Conference on Computer Communications, pp. 1-9. IEEE, 2017.
McDaid, A. F., Greene, D., and Hurley, N. Normalized mu- tual information to evaluate overlapping community find- ing algorithms. arXiv preprint / 2011.
10

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Moseley, B. and Wang, Approximation bounds for hier- archical clustering: Average linkage, bisecting k-means, and local search. Advances in Neural Information Pro- cessing Systems, 30, 2017.
Yang, J. and Leskovec, J. Community-afillation graph model for overlapping network community detection. In 2012 IEEE 12th international conference data mining, pp. 1170-11111 IEEE, 2012a.
Naumov, S., Yaroslavtsev, G., and Avdiukhin, D. Objective- based hierarchical clustering of deep embedding vectors. In AAAI, pp. 9055-9063, AAAI Press, 2021.
Yang. J. and Leskovec, J. Defining and evaluating network communities based ground-truth. In Proceedings of the ACM SIGKDD Workshop Mining Data Semantics, pp. 1 8, 2012b.
Nepusz, T., Petróczi, A., Négyessy, L., and Bazsó, F. Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E, 77(1):01617, 2008.
Zhang, S., Wang, R.-., and Zhang, X.-S. Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and its Applications, 374(1):483 490, 2007.
Newman, M. E. and Girvan, M. Finding and evaluating community structure networks. Physical review E, 69 (2):026113, 2004.
Nicosia, V., Mangioni, G., Carchiolo, V., and Malgeri, M. Extending the definition modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment, 2009(03): 2009.
Orecchia, L., Ameranis, K., Tsourakakis, C., and Talwar, K. Practical almost-linear-tim approximation algorithms for hybrid and overlapping graph clustering. In Inter- national Conference on Machine Learning, pp. 17071- 17093. PMLR, 2022.
Räcke, H. Minimizing congestion in general networks. In Proceedings of the 43rd Symposium on Foundations of Computer Science, pp. 43-52. IEEE Computer Society, 2002.
Räcke, H. Optimal hierarchical decompositions for con- gestion minimization in networks. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 255-2644 ACM, 2008
Rahgoshay, M. and Salavatipour, M. R. Hierarchical clustering: New bounds and objective. arXiv preprint arXiv:2111.08861 2021.
Roy, A. and Pokutta, S. Hierarchical clustering via spread- ing metrics. Advances in Neural Information Processing Systems, 29, 2016.
Shen, H., Cheng, X., Cai, K., and Hu, M.-B. Detect overlap- ping and hierarchical community structure in networks. Physica A: Statistical Mechanics and its Applications, 388(8):170--177 2009.
Whang, J. J., Gleich, D. F., and Dhillon, I. S. Overlapping community detection using neighborhood-inflate seed expansion. IEEE Transactions on Knowledge and Data Engineering, 28(5): 2016.

---

Hierarchical Overlapping Clustering Graphs: Cost Function, Algorithm and Scalability
A. Supplements to the cost function for HOC
In this section, we provide some supplementary proofs and examples for our HOC cost function.
A.1. Proofs of the properties of belonging factor
(1) Proof of Property 2.4
Proof. By Definition 2.3, Erex- aX,Y = 1. When Y is the only parent of X, ax,y = 1.
(2) Proof of Property 2.5
Proof. We prove by induction. We group the nodes HOC graph D by the distances from the root R. For each integer
i, let S; {N E D]dis(N, R) i). Then we prove the property by induction on i. For each N É S1, since |N |
1, we
have NR 1. Suppose that for each X E Sk, ax, 1, and then for each N E Sx+1, by the recursive definition of a. ON,R = 2 XEN ON,x ox,R Exen ON, =.
(3) Proof of Property 2.6
Proof. Since S is anti-chain and every path from X to Y passes through one node in S, all paths from X to Y can be divided into |S] subsets according to whether node N E S is on the path or not. Then Property 2.6 can be verified directly by the definition of a.
lem(p)-1
Σ
ax,
pEPx,Y
len(p) II
1
Σ
OppPi11
NES p:NEp
i=0
len(p)-1
-1
len(p)-1 -1 II
Σ
II
Optpitt
Ppp.Pi+1
NES
PEPX.N
1=0
PEPNYY
t=
Σ
ax.N
-NNYY
NES
A.2. A toy example of belonging factor
R
N
No
N
N2
N
(a) Original graph G: path of nodes.
(b) An HOC graph of G.
Figure 3. Illustration of HOC.
In order to better understand node-to-node and edge-to-node belonging factors, we give an example this section.
12

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
As shown in Figure graph G is path of 4 nodes, and possible HOC graph is shown in Figure (b).
Table demonstrates the MCA set of each leaf node pair. Table 3 shows the node-to-node belonging factor of each child-to-paren node pair on the HOC graph, and those of any others can be calculated by Definition 2.3. For example,
Nb.N, = C,,N, ON + Obb,N2 CN2..N4 = 1 +
2
2 2
4'
1
1
Ob.N, 00,N2 N.2..N
2
4
Table 2.
MCA sets
node pair (u, v)
(a. b)
(a,c)
(0, d)
(b, c)
(b. (c,d)
Muv
}
{ {R)
{N2)
{Ns} {Na}
Table 3. node-to-node node belonging factors (child to parents)
node pair (X,Y)
(a, N1)
N))
(b, N2)
(c. N2)
(c,
(d,
ax.Y
1
1/2
1/2
1/2
1/2
1
node pair (X,Y)
(N1
(N2, N1)
(N2, Ns)
(N3, Ns)
(N1, R)
(Ns, R)
ax,Y
1
1/2
1/2
We can also verify the properties of the node-to-node belonging factor. Here we only verify Property 2.6, and other properties can be easily verified. Let X b. N4, S {Ni, N2). We can verify that S satisfies all conditions of Property 2.6. Then
Σ NES
1
1 3
OlD,N4 N4
O8,N ONNN, Ob,N. N,NI.N, 00,N2 N.2.NN
2
1
+
2
2
4'
Again, let X b, = R.S (Na, Ns). Then
O& Σ
CbN AN.R = Ob,N, ON,,R + Ob..g CN,.
3
x1+
1
x x1=1.
4
NES
Table 4. edge-to-node belonging factors
edge (u, v)
MCAs
B
(a,
N1
1
(b, c)
N₂ 1
(c, d)
N3
1
Table 4 shows edge-to-node belonging factors all edges and their MCAs. Because each edge has only one MCA, its edge-to-node belonging factor
A.3. Cust calculation for the running example
For reading convenience, we demonstrate the example again in Figure 4.
In D1. all edges have only one MCA, so the edge-to-node belonging factors of them are 1. The graph contains 6 edges in all, and each MCA has descendant leaf' nodes, resulting the cost H Pi (G) 6 18.
D2 is not overlapping. For (a, b), (a, c), (b, c), their MCA has 3 descendant leaf nodes. For (d, e), the MCA has 2 descendant leaf nodes. For (c, d), (c, e), their MCA has 5 descendant leaf nodes. All together, the cost DD (G) 3 x 2+2x5 = 21.
In Dz, consider terms separately corresponding to the edges. Taking (b, c) as an example, it has two MCAs. Due to symmetry, the edge-to- to--to--nna node belonging factors (b, c) regarding to both ancestors are 0.5. Therefore, the cost contributed by (b, e) x
Thus, the cost Ds (G) 104 +0.x4)
x 4 x1xx== 24.
13

---

Hierarchical Overlapping Clustering Graphs: Cost Function, Algorithm and Scalability
R
N
2
N
N2
(a) The original graph G
(b) HOC graph D1
(c) HOC graph D2
(d) HOC graph Ds
Figure example HOC graphs. The costs H = 18, H Pa (c) = 21, H1 Pa Pa (G) 24.
A.4. Proofs of properties of the cost function
(1) proof of Property 2.11 (compatibility)
Proof. When an HC tree, the MCA of edge (u, v) is unique and degenerates to the LCA on the HC tree, and the edge-to-node belonging factor is also 1. Then, we get
(G)
Σ (u,D)E
v) Σ NE
P(.n) (V(NN)) = E
w(u V Das PG).
(u,D)E
(2) Proof of Property 2.12 (additivity nodes)
Proof. It follows easily by exchanging the summations in the definition of H HD(D).
(D)
Σ
w(u,v) Σ
B(a.e)
IV(NN)
=E
[V(N) Σ
((.e)) co(u.u)
(a.
NEM
NED
(a
(3) Proof of Property 2.13 (binary optimality)
N'
N
N
N₁
N2
Na
N
N2
(a) The original local structure
(b) After binary branching
Figure 5. Binary optimality of HOC graphs
Proof. As shown in Figure 5, assume that (a) represents local pattern of non-leaf node on HOC graph D, where node N has at least three children Nr, N₂, and N₃. For any edge (u, v) treating N as an MCA, u and v cannot belong
14

---

B w(u, v). The above Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
both to any individual cluster of N1, N2 or Ng. since otherwise, N would not be the MCA of them. Without loss of generality, let's assume that belongs to N1 and belongs to N2 (or belongs to N₂ and N3 simultaneously).
Now, the binary branching operation inserts a new node X as the parent of N1 and N₂, which turns into the structure shown in (b). As a result, the MCA for (u, v) becomes X. Then we show that after the binary branching, the overall cost H D (G) does not increase.
After binary branching, since every original path from to N via N1 passes through X now, and ax 1, we have N,,,N Nu,,N" 2 Ou,XX. For the same reason, Ov,,N 2 X., Therefore, ((M.o) 2 (u., Additionally, we have [V()) < ((N),, implying that w(u, v) (V < w(u, e)) (V..))VV [VV]]. This leads to a reduction in the cost function associated with this term. Note that the cost reduction holds for any such edge (u, u) that treats N as an MCA. By Property 2.12, the cost function can be expressed as ENED ((N)I-E(
operation affects only the cost of single node. For other nodes, the edge-to-node belonging factor and the number of descendant leaf nodes remain unchanged, thus their values do not change. As a result, the overall cost D (G) does not increase..
B. Supplements to the algorithms
In this section, we provide some supplements to our algorithms.
B.1. Primal and dual problems of 2-OC
Following is the derivation process of the forms of cost and costdual for 2-OC.
(G)
Σ
w(u.v)
Σ
BAY (U,,)
(VNN
(U.
NEM w0
Σ
U(A + (B)) +
Σ
w(u, (|4 + +IBI)
(AA)
((A.))
+
Σ
+ +CI)+ +
Σ
w(u, e + +C)
(u.))E((C)
(,,))E((BCC)
Σ
w(u,v) v) (SM..) [B) + ((..)) (1B[+(C1))
(L,))E((B)
Σ (LL,)E((A,C)
w(u, v)n
( BI) + w/ A, () |B)) + (CC) (CC)) + BB C) + (C))
$2 (BA + B + (C4)+
= (w(A) + w w(A, B - B + (w(B, + (1C)
+B( ||| B|
|C|
2 + (A, C)n.
Explanation of the derivation: We classify the edges into six parts, denoted by F(A),, F(A, B), F(B, C), F(C)), F((), E'A, C), and calculate the cost of each part separately. For (u, v) E E(A), E(A, B), the only MCA is N1, ((L))
1, L.(V(N = |4|| + |B]. Similarly, for (u, v) E E(C), E(B, the only MCA is N2, ((..)) = L,IV( = |B] + +C). For (u, E E)B), the MCAS are N2, and (2M,)) = ((u.0) = Z- For (u, v) E E(A, C), the only MCA is R,
(R...) = 1, (V)) = n.
15

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Observe that
| + 2 + |C|
| + | + |C|,
< n
2
| + [B| - n,
w(B) = w(A) + + + w((C) + w(,, B) + C) + w(A,
[4] + B -
[ |C| |
A + 2| + |C1
A
Then we have
costprimal (A, B, C)
+ (4 wBB | + 2 + 101
+ w(A, C)n
2
|A| + |C
(w(A) + w B)) + (00 (v
)+ (),
2
w(A) + w.A B) + w(B)
|01 - [w(C) + + (B, C) w(B)
now F))
|A|
2
2
- (ew(E) (W(A++ + B) w(B)}
w(bb)
|0| - wB + C) 2 |.A.
2
B.2. Proof of Theorem 3.1
We prove Theorem 3.1 with two lemmas respectively.
Lemma B.1. The time complexity of Algorithm I is O n log
Proof. Let wmar be the maximum edge weight, then w ()() S mw xw(B) S mmWmass and so costremp w(E) w(A, CbB) S (1 +L+20 #))Wwaa. Observe that the edge with the maximum weight is not in E(A, C) the initial state, and costremp Wmaz. In each iteration, costremp inereases by 1 + v times, then the maximum number of iterations O n² log log.). ). In each iteration, it takes O time to calculate the variation caused by the swap of each node pair and update w (A, C*) and wBB). Therefore, the overall time complexity is 0 log
no more than log1+ + ((1 + (c))meemz///man
Lemma B.2. The approximation factor of Algorithm
is
2 (=))) That is, A, B, C output by the algorithm satisfy 3v6
2
1 +
))
cost.bull 2
-
posttuual(A, ,O),
3v6
where A", B", C* is an optimal solution.
Proof. Let's consider the status of A, B, C after the termination of Algorithm 1. Note that exchanging any two nodes from any two of sets A, B, C at this time cannot make costtemp (A', C') larger than (1 + , costtemmp (A, B, C') any more, where A', B', C' denote the corresponding sets after the exchange, respectively. Let coslatd = cosltemp (A, B, C). In other words, an exchange performed on any pair of nodes, then cost S (1 + ,. )costold. where cost denotes costtemp after the exchange. Define A cost costatd, and then we get A , costoia-
Next, we analyze the A value caused by node exchange. First of all, let's establish some relationships on node swap for later use. For a E A, b E B, c E C, consider the following three cases.
(1) Swap a and b: (AA,, C") - w(A, C) = w(b, C) - w(a, C), wBB) - w(B) = w(a, B) - "w(a, b) - w(b, B). (2) Swap and et (AA', C²) w(A, C) (cc,, A) + w(,, A), wi (B') - w(B -w(b, B) + w(c, B) w(b e).
16

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
C
a
b
TBC
A
B
C
Figure 6. Illustration of 2-OC clustering and node swap
(3) Swap and c:
wcc, A) wla, A) + w(c, C) + 2wc(a, c), w(BB) w w(B) = 0. Recall that A = cost cost = -- (w((A - w0, + +x (B)) wB)). Therefore, by substituting the above equations, we can obtain the value of A for each case.
-
(1) For any A, b E B, swapping a, we have A - wb, C) + (a C)+ -) w(a, b)- w((,, B)) S fo costald Summing over all a, we have
-pnw(B, B, C) + (1 mp) (A,C) + x ((1 - 2p) (A, - w(A, B) 2pnw S - - - 2p)n costatd.
(4)
(2) For any E B,C E C, swapping b, c, by the symmetry of A, C, we have
-prw (A, - m (A, C) x(1 ( 2p) (B, (B,C) C) w(B, C) 2pnw(B)) S E 1pp01 costotd.
(3) For any a E E C, swapping a, c, A wia, C) + w(c. A) w(a, A) w(c, C) -20(a, for costotd. Summing over all a, c, we have
pmao(A,) + pmm C) 2pmw 2pmm 210 (A, C) S m3 p2 costald;
and then
ep ep2 costord
((AA) -w(C) pr w( +
(6)
2pm
Summing Inequalities (4) and (5), we get
((-p+ (1-p+(1- (1-2))))) - x) (w(A, B) + w(B,C) 4penw B) (-2+ 4p)))(44AA)))) + 2cp(1 22)ccotood
Substituting x
p into Inequality (7), we get I+2p
4p +D
w(B < (-2 4p)re((A,C))) 2ep(1 22pcoollatd
1 1 2p
1+ 2p
Multiplying the coefficient
4p²n-tp on both sides of Inequality (6), we get 1+2p
Ap²n + (wv( (A) + w()) <
4p2n +
pn
w (),
4p2n + 2pooollod
(9)
1 2p
1 2p
pn
1 2p
2pn
17

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Summing up Inequalities (8) and (9), we have
4p'n + ((E) E) + p w() (-2+ 4p)m
4p2n +p
2pm -
w w(A
1 + 2p
1 2p
1 + 2p
pm
4p2n +
epp
+2cp(1 2p)cost +
(10)
1 2p
2pn
After removing wB) on the left, we get
4yEn + P
4p2n +
2pm -
w (B( 2
(2 (2-4p)) 4p)m +
w w(1,
1 1 2p
1 2p
pm
4p2n +
ep
2ep(1 2p)cosloodd
(II)
1 2p
2pm
So w/ (o(AC) is upper bounded as
4p2n+p ((E) + 2ep(1 2p)coslata + I+2p
4ppn+p
ep² postolld
w(A,C) <
1+2p
2pm.
(2 4p)n + 1p²n+22
2pm-1
1+2p
4p²n² + pm ((E))
2mp( -bp + 1)c
p² + 1)(3p + 1)c
w(E)) + 2(2p 1)(2n 2np 1)
w (E)
2n² 2pm
2n²
2np
( nn w(E) + ( w(E)
2p +
n )} w(E))
2pº + A
(12)
So
2 (1-20²- -0 (1+E) (1(+t) woE.
Therefore,
(w(A+ B) - w w(B)) C1 w(B () w((B))
) |
cost (A,
2
2
(w(A + B) + w(B + + - wl ()()))p
(w(E) w(A,C) C)
1+t)
1 1 2p² A
w/ (F))p
1 1
2p + p θ
nw(E) (E)
n
(1tc)
2p p O
cost (A", (A" B,, C*).
(13)
n
The fact cost & (ww(E) EE) is used for the last inequality. Substituting p= into Inequality (13), we get
- (1+c) ( cost (A', CC))
cost (A,
(14)
3366
Remarks:
We have a rounding error in costavat A B, C') incurred by setting [AI.BB),C to be integers in the above proof. But because the error is additive and aggregated only a constant multiple of w(E), it can be absorbed safely in (1+e)
By Lemma B.I, B.2, Theorem follows.
18

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
B.3. Proof of Proposition 3.2
Proof. We show that the optimal 2-OC-D value OPT(K,) B), [C7. Let
-( 3/6
( ()). Consider any A, B, C, let |A].
((,,,,2) costddal (A, C) (x(x - 1)
y(v - 1)
+ 2((3 - 1)
yz yly 1) 2;
xy
2
and our goal is 2E
(æ, y/, z).
First prove that fz, y, 2) takes the maximum value when x = y. Consider (z, y. 2)
=== Ur *+=), then we have
+
+
1/
f1 U,
2
I +
+
+
-1)
+ (x + 2)y +
1l 1)
I x 2 1ly -
2ryz
x2(x 2)
2
2
2
2
r
2
(2 +
2)² -
4rz
(x + 2)² - 4xz
y
4
2
2 0,
which indicates that when is given, f gets maximum when x So our problem transformed into
g(x,8)= = (ar - 1)x + 2ay + y(y -
1)
max
x,
2.yE22.22+yz2
2
which is equivalent to
(x 1)x 2x(n 2x) (n 2x) 2x 1)
max h(x) 0<z<>
x.
After simplification
2x
122 4x
(n
2x
h(z)= (x 1)x (n (2))
(x 1)x
x.
2
2
and taking derivative
11²
1' (x) -3x +
2
we know that h(x) achieves the maximum value
n²-n
For the optimal solution value, we have
OPT(K,)
n n
n2
12
2
n
n2
71
n1
n²
6
2
3
6
Finally, note that nwo F) n(n-1) 1)
3 nn
Then we have
OPT(K.)
6
n2 n
2
(1-
1
2
V
now (ww(E)
3/6
n²
3V6
+
Vn²
n
3/6
7
This completes the proof of Proposition 3.2.
19

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
B.4. Proof of Theorem 3.3
In the section, we prove Theorem 3.3 that provides an approximation guarantee for 2-OC-P.
Proof. Let cost and primal be the optimal objective values, costaval and costorimal be the values that Algorithm outputs, for 2-OC-D and 2-OC-P, respectively. Let a be the approximation factor of Algorithm 1 to ne for the dual problem, and b be the approximation factor of Algorithm I to cost primal for the primal problem. We have the following relationship.
Lemma B.3. S (1 - a] + cost cost primat)
Proof.
Note the following relationships hold.
cost + cost doal costprimal + costduaa n w(B),
and
cosldual 2 a now E).
Therefore, we have
costprimal (E) costdual <nw(EE= anw(E) (1 ()(osstyrimat + cost duat
That is,
costprimat/cost primal S (1 a)(1 (1+ + costiual/ cost prisat))
Lemma B.3 follows.
Since we already have 2 ( if we can give an upper bound cost cost costprimatt primat then also have an upper
3/6
bound on The following lemma provides this upper bound.
Lemma B.4. For 2-OC-D and 2-OC-P, cost cost primat Prnaa Pavg dmaaa Danan/Daog where Pang EWE)/VVV is the average density, Pmax is the maximum density of all induced subgraphs, dmax is the maximum degree of all nodes, and davg is the average degree of all nodes.
Note that Lemma B.4 also holds for the dual and primal cost ratio determined by any HOC graph.
Proof. Let A", B", C* be the optimal solution (no matter whether it is primal or dual because the two problems are equivalent), let cost* primal denote costprimal (A", B", C*)) and cost dostd denote cost (A", B B CC*) for short.
cost diall
=["" (C"| w (A") + (A', + 2" (B*) + +AA
1 w ( (B", + 2 (B'))
cost primal (IA7) + (B")) - B²) + マー (B*)
+(B")+1C*)) w w w (B*) + nw
Consider two cases cost" /cost" primal-
(1) If t /cost* /costtrimal
primal S 1, then 2(1 - a).
20

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
(2) If cost cost primat
1, namely costdual 2 cost" primots substituting into the specific form of the objective function,
we have
|0*|
w (A*) + w (A', + 2" w (B+)) + +1A71 (00 + (B",
1
1 " (B*) (B", (²) + 2
1
(IA*) + (B*)) w (A*) + (A", B3) + + zw (B")
0118)++00
10 (B*
2 w (1²)) nw (A* C*).
Then we get
(10*) - |A|| - (B w (A*) + w (A", BB) + 1
2 w (B*)
+ (IA7) - |B - -C'1) (W (1
2 (B*))
nw (A*,C*)
This holds if and only if
(|C*) + - + +,
C*)),
which implics that
+ B²) w((C) wB'
B C*)) 2
Without loss of generality, we assume that |C*| 2 A ww (A*) + (A", BB) 2 wCC)) + w(B" C*). We consider two types of scaling for cost primal
Scale I: replace [A"| with |C*| for the numerator, remove (A',,, C*) for the denominator, replace |C*|| with |A*), and then we get
cost dual cost primal
(00--114110000000034000040444444 wBt)) [0))))))((
[ (+ C*))
|C*1
B-| + |
Scale 2: replace the numerator w<C*) + w(B", with w(A") w(A', BB), remove the denominator Contents of BB) and then we have
cost dual cost" primal
AACCCCHHHHBC0HHHHH0HHHHCCC000000 +w + (1A-) + (wo
(|A+++ + +CCCCCC)CCCCCCHH00H00)))0))111))
w (44)) w(C*) + (CC)++ (AA,
Therefore,
cost dual
< max |I.
|
w(A") + w(A", + (w((")
cost primall
[A+ + B+| w(C') + wBB C*) (B*) + w( C+)
21

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
Let
|C*
A + |Ba
((A)) (A", B*) ww(B = w(C*) + w B C*) (B w w(* C+)
We have
| |B*
V|.
1 x8
and
w((A)) + w(A", ((A,B*))))))))
(B())) = y/
w EE) + y
2
Recall that [C*| |A* u(A")= w w(C')+++ (B",, C*), and observe that the density of the induced subgraph to be the maximum density of the induced subgraph to be the average density of G, and then
w(E(G))))
G[A** B*] should be large. Set Pmax maXUgv
G. (GGUU) to be the edge set of G(U), Paog
w(E)
T
w(A) + w B²) + (B²)
x(++2)
w (E) M
w(A + B*) |3
S Pmex.
A + 3
1+ y
A"
We have
v(1 + x)
Pmas
1 + y
Pavg
Now according the value of min(x, v). we consider the following two cases.
(1) S y. have
(1 y)
x x+ ay
4 xy
y(1 + x)
Pmas
1 1
1 1
1
1
Pang
(2) x > y. we have
y(1 +x)
y(1 + x)) 1 y
Pmaz
y
<
14x
Pong
Therefore,
min [ [+1 w w((C)) + Ba C*) + f + w(A ) }
|C*1
w(A*) + ww(A B²) (B²)
Pmaaz
(B'
Pavg
Then for cost cost primats we have
cost* cost* primal
duol
{
Pmaz
Pmaz
max
Pang
Pong
Calculating Prazz difficult. However, can be observed that the average degree dman on G(U), and w/ w(E(G(U)) ditl So, we have an upper bound on Pmans that is
w (E((()
d UU
dmax
Pman
U
2
2
On the other hand,
w(E)
davg
V
dang
Pang
V
V
2
22

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
This implies that
Pina
dmaa
Pavg
davg
Therefore,
Juat)ual_ cost primal
Pman
Amaz and this completes the proof of Lemma B.4. davg
Pang
Combining Lemmas B.3 and B.4, Theorem 3.3 follows.
C. Supplements to Experiments
In this section, we provide supplementary information and results on our experiments.
C.1. Definition OSBM
OSBM specified by a pair real numbers pt, P2 (0 S Pi S S 1), and k symmetric membership matrix Z, in which each row column indicates a cluster and each entry natural number. Zyy * j) represents the number of overlapping nodes between the i-th and the j-th clusters, and Zú represents the number of nodes in the i-th cluster that do not present overlap. Denote by CI,...a the planted overlapping clusters, P1 represents the inter-link probability between each pair of clusters, while P2 represents the intra-link probability within each cluster. For two nodes in the overlapping region, we have two independent samples, and the edge exits if either of the samples generates one. Equivalently, the probability of edge presence between any two nodes in the overlapping region is (1 - p2)²
C.2. Definition of the NMI for OC
The normalized mutual information (NMI) was originally developed as a distance measure for non overlaaaggg partitions. The work in (McDaid et al., 2011) put forward the NMI for OC that represents a natural generalization from the original NMI. Formally, for two different groups of overlapping clusters X = {x1, .2..... = {yı 92, ...) on the same graph G (V, E), where Fz. V/s are clusters, let p(x;) |z, p(y) / VI. p( y₁) |z, yy I/V]. should be noted that, unlike the classic NMI used for non-overlapping partitions, p(x,,) and p(y.) cannot be interpreted probability distributions due the overlaps within X and Y. We define the entropy of random variables, joint entropy and mutual information respectively as follows:
H(X) =- Σ p(x;) logp(z),, H(Y) = Σ plg))logp((n p(y:),
MYY
H(X,Y) Σ
p(ui, Mi) log p( Vz),
1(X : :Y) =)=H(()) H(Y) H(X,Y)
Then the NMI of X, Y is defined as
I(X:Y) NMI(X,Y) ((X)
NMT(X, Y) is in the range 00, 1). and equals 1 if and only if X and Y are exactly coincident.
C.3. Evaluation the MNIST dataset
To show intuitively that our algorithm is able to find out the blurred overlapping of datasets, on the MNIST dataset (LeCun et al., 1998), which is benchmark of handwritten digits containing ten classes of images labeled by 0 ~ 9, respectively. We select two pairs of labels that are easily confused by hand writing, i.c., 1 vs. 7, 3 vs. 8, and construct a k-nearest neighbor graph for each of them. Each node of the graph represents an image of handwritten digit, and the similarity is measured by applying the Gaussian kernel function to the Euclidean distance of pixel vectors. We remark that not all embeddings (e.g., word embeddings) that are generated by modern-day Al models are suitable for
2-OC algorithm
23

---

Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability
clustering. We just find that pixel vector in MNIST is somewhat a good use-case to showcase results of overlapping. ambiguous samples.
The parameters, NMI, size of the overlapping part, the costs of ground truth (GT, non-overlap) and 2-OC output are summarized in Table 5. NMI is calculated with the non-overlapping ground truth of data points, although our algorithm gives overlapping results. However, the NMI for the labels vs. 7 is above 0.9, and only digits, which can be viewed as ambiguous ones, are allocated in the overlapping part. We demonstrate all of them in Figure 7(a). For the labels 3 vs. there are 60 ambiguities. We demonstrate four of them in Figure 7(b). A significant factor that impacts the accuracy of our algorithm is that we simply use the pixel vectors of digits which is very rough representation of images.
7
7
7
7
(a) labels
133
(b) labels 3 vs. 8
Figure 7, Demonstrations the ambiguous samples our 2-OC algorithm yields.
Table 5. Parameters and results the MNIST dataset
label
size
k
NMI overlapping size
GT cost (non-overlap)
2-OC cost
us.
7877
7293
100
0.926
7.37 10
7.33 x 10
3 us.
7141
6825
100
0.812
60
6.47 10
6.54 x 109
C.4. Visualization of four overlapping clusters
We visualize in Figure 8 4-HOC results of Algorithm 2 on small graph that is generated from OSBM and contains 100 nodes and 629 edges. It has four embedded overlapping clusters of size 27, each of which contains 22 or 24 nodes that entirely belong to the cluster. There are 6 overlapping regions, each of which corresponds to a pair of overlapping clusters out of the 4 ones, and each region contains nodes. We label them from 91 to 100. We demonstrate the ground-truth membership of all nodes in Tables 6 and The edge presence probabilities are p1 0.01, P2 = 0.05 and ps 0.3.
Table Membership level-2 nodes in each the four clusters. Each diagonal entry numbers the nodes that belong exclusively to the corresponding cluster. The entry (i.j) + j) denotes the node numbers in the overlapping region between clusters and j. In the visualization, the corresponding colors clusters 2, 3, and are red, green, blue, and yellow respectively, while overlapping nodes
are the mixed colors of their clusters.
cluster label
2
3
4
1
1-22
96
91,97
92,98
2
96
23-44
93,99
94,100
3
91,97
93,99
45-66
95
4
92,98
94,100
95
67-90
24

---

Hierarchical Overlapping Clustering Graphs: Cost Function, Algorithm and Scalability
Table Membership of level-1 nodes in each of the two clusters. Clusters and form one cluster, denoted by (1, 2,,2, on level 1, while
clusters 3 and 4 form the other one, denoted 4).
cluster label
(1,2)
(3,4)
(1,2)
1-44,96.
91-94, 97-100
(3,4)
91-94, 97-100
45-90,95
(a) Ground truth of the 1 clusters (Level 1).
(b) The result of our algorithm (Level 1).
Dain
(c) Ground truth of the 4 clusters (Level 2).
(d) The result of our algorithm (Level 2).
Figure 8. Visualization of a 4-HOC clustering.
Table List of misclassified nodes given by our algorithm on level
node number cluster label in ground truth cluster label by the k-HOC algorithm
100
(1,2).(3.4)
(3,4)
Table List of misclassified nodes given by our algorithm on level
node number cluster label in ground truth cluster label by the k-HOC algorithm
100
2,4
4
70
4
3,4
Our algorithm bipartitions the node set at the first level into two overlapping clusters, consists of red and green (1 and 2). the other blue and yellow (3 and 4). It achieves NMI 0.964 this level. At the second level, it achieves NMI 0.959 for the four ground-truth overlapping clusters. In Figure 8, we visualize this result. Our algorithm successfully captures the overall outlines of the clusters, except membership errors on only two nodes, whose labels are 70 and 100. We list them in Tables 8 and 9. The node 100 is misclassified into oon-overlapping region on the first level while the node 70 is misclassified into overlapping communities on the second level.
25


Reviews:
[{"review_id": "9xlNRJoxOl", "reviewer": "Reviewer_3QxV", "summary": "Two variants of graph clustering are Hierarchical Clustering and Overlapping\nClustering. While there are some studies of both variants, they were not\npreviously considered simultaneously. The paper proposes a reasonable cost\nfunction that combines both variants, and investigates algorithms that minimize \nthis cost function.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n============================================\n\n(Sorry for occupying this space for the response to Reviewer 4xK8 due to the strict limit on character number.)\n\nQ7: 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$.\n\nQ8: 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).\n\nQ9: 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.\n\nQ10: 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.\n\nAfter all, regarding to W1 on the significance of Algorithm 1, please refer to our response to Reviewer 7SG8, the second item.\n\nHope we have addressed all the concerns. If there are any remaining questions, we are happy to address them.", "claims_and_evidence": "Claim 1: the proposed cost function for HOC makes sense.\n\nThe paper supports this claim by showing that it reduces to previous\nvariants for Hierarchical clustering trees.\nIt also discusses additional properties that supports the intuitive\nmeaning of this newly proposed cost function.\n\nClaim 2: There are effective algorithms for minimizing the proposed cost\nfunction. \n\nThe paper proposes such algorithms, and experimentally verifies their\nperformance.", "methods_and_evaluation_criteria": "The main tool for the algorithm is local search.", "theoretical_claims": "Partially", "experimental_designs_or_analyses": "Experiments look fine. I also like the toy examples in the appendix.", "relation_to_broader_scientific_literature": "Yes, to the best of my knowledge.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "It is an interesting result that may encourage others to look at both hierarchical and overlapping graph clustering models.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n38IsoXHTa", "reviewer": "Reviewer_sxS7", "summary": "This work introduces and studies the hierarchical overlapping clustering (HOC) problem. In the clustering literature, many works have focussed on either (i) overlapping or (ii) hierarchical clustering; this work's aim is to reconcile both topics.\n\nAs a first contribution -- inspired by the well-known Dasgupta cost function -- this paper introduces a cost function for overlapping hierarchical clustering. The proposed cost function has serveral desirable properties such as compatibility, additivity, and binary optimality.\n\nAs a second contribution, the paper further proposes approximation algorithms for the dual and primal variants of the new cost function. These approximation algorithms hold for a restricted variant of the HOC problem, namely the $k$-HOC problem and the $2$-HOC problem.\n\nAs a final contribution, the algorithm is tested on synthetic and real-world dataset. To speed up the algorithm, the paper uses local search heuristics.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful review and valuable comments. Let us address the concerns one by one.\n\n1. 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.\n\nThe 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\nWe thank the reviewer again and are happy to address any remaining concerns.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I checked them.", "experimental_designs_or_analyses": "The experiment section is slightly discoupled from the main theoretical body of the work\n\n**1** The proposed algorithms are rather slow ($O(n^4)$ factor in the running time) which prohibits the algorithm from being applied at a large scale. This requries the paper to introduce local search heuristics to make the algorithms implementable. As such, Algorithm 2 is not 'formally' compared.\n\n**2** $k$-HOC experiments are only performed on synthetic data, and it is not clear to me how some metrics (such as NMI) are computed for overlapping settings for both methods compared.\n\n**3** No qualitatative results on real-world datasets; the real-world datasets are only used for scalability experiments. There are experiments on MNIST in the appendix, however the NMI in those experiments is calculated using non-overlapping clusters.", "relation_to_broader_scientific_literature": "The paper effectively positions its contributions within existing literature on hierarchical and overlapping clustering, referencing Dasgupta (2016), Orecchia et al. (2022), and other foundational works.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**S1)** The paper studies a new important problem, that is worth to study. The problem formulation itself is quite intuitive, and a natural way to combine the hierarchical and overlapping clustering problems. This work could potentially lay the groundwork for future algorithms to be developed on. Throughout the main body and appendix the paper also states and proves intuitive properties of the cost function, which is a nice contribution.\n  \n**S2)** The paper also introduces 2 approximation algorithms for the new objective function, one for the $2$-OC problem, and another $k$-HOC problem. These algorithms could provide a good starting point for future work on HOC.\n\n**S3)** Finally, the theory for the cost function and the proofs for the approximation guarantees seem sound to me - and non-trivial for the most part.\n\n\n**W1)** The approximation guarantees are given on fairly restricted settings; for the primal and dual variants of $2$-OC and $k$-HOC. the $2$-OC problem studies the overlapping bipartition problem, and contains no hierarchical structure. The $k$-HOC problem does have a hierarchical component, but restricts itself to at most $k$ clusters/nodes. The approximation guarantee on the latter is only given on the dual variant of the problem (which in general is a bit easier to prove, like the dual of Dasgupta's cost function (Mosely & Wang, 2017)). It seems that the approximation guarantee follows rather directly from the approximation guarantee of the dual of $2$-OC.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7XUZikZfVk", "reviewer": "Reviewer_4xK8", "summary": "The paper formally introduces the problem of hierarchical overlapping clustering. Overlapping and hierarchical clusterings have been studied more extensively separately. The only preexisting works that have studied them together have been in the distance setting (edge weights are distances) with no formal objectives and guarantees. This paper provides those formalities in the similarity setting (edge weights are similarities).\n\nIn hierarchical clustering, clusters are nested into clusters, creating a tiered structure of clusters which can be represented as a tree (the root = the set of all data, the leaves = individual data, and intermediate nodes = clusters). With overlaps, any cluster can have partial belonging to another cluster up the hierarchy. The total belonging (sum over belongings of a single cluster to all other clusters) is, naturally, 1. It has a nice probabilistic interpretation: If I 1/2 belong to one cluster, then maybe I flip a coin to determine my belonging. The hierarchies of belongings are designed such that these probabilities are preserved (if I 1/2 belong to X and 1/2 to Y, and X 1/2 belongs to Z but Y doesn't belong to Z, then I 1/4 belong to Z).\n\nTheir objective function directly extends Dasgupta's cost objective, perhaps the most famous and natural hierarchical clustering objective. Effectively, this objective deems that highly similar points should be tightly packed into small clusters. In the overlapping setting, partial belongings are accounted for. A minimum common ancestor of two points is defined as a cluster containing both points whose children contain at most one of the points each. In Dasgupta's setting, this would be the size of the smallest cluster containing the points, but there may be multiple \"MCAs\" with overlaps. With Dasgupta, the cost contribution of $(x, y)$ is $w(x, y)$ scaled by the size of the MCA, but in this paper, it's a convex combination of the sizes of the many MCAs (again, with a nice probabilistic interpretation). They also define the dual to this objective, which is akin to the work of Moseley and Wang in the hierarchical (non-overlapping) setting.\n\n\nThe authors then propose two algorithms. The first is a simple local search algorithm for the problem of (non-hierarchical) overlapping-clustering with only 2 overlapping clusters allowed. While this problem has been studied before, it is new in the context of how their objective simplifies to this setting. The algorithm achieves an O(1)-approximation for the dual and an O(d_ratio)-approximation for the original problem, where d_ratio is the maximum degree divided by the average degree.\n\nThe second algorithm solves the general problem when the width of the hierarchy is bounded by k (except at the leaves). This shown only to approximate the dual, but it does so with the same factor as the previous algorithm and on the more general case.\n\nFinally, they run the latter algorithm against a set of baseline algorithms. This includes one of the previous papers on hierarchical overlapping clustering. The algorithms are run on data generated by an overlapping stochastic block model and on real snap datasets. The latter does not have ground truths for hierarchical clustering, so they only test runtime. On synthetic data, they show that output much better clusterings (as measured by NMI, which they don't define). On all datasets, they show their algorithm is acceptably scalable.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful review and valuable comments. Let us address the concerns one by one.\n\nQ1: 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.\n\nQ2: Yes, the condition after “if” is quite natural, “for any node set S” is better.\n\nQ3: 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$).\n\nAs 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.\n\nQ4: 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.\n\nQ5: Sure. We will mention Moseley and Wang’s dual for HC when we define $k$-HOC dual on Page 5.\n\nQ6: 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.\n\n(Since there is a strict limit 5000 on the character number, we continue our response in the rebuttal to Reviewer 3QxV on the top.)", "claims_and_evidence": "Yes, they are substantiated by accompanied proofs in the appendix as well as formal experiments. I would say the experiments are somewhat limited in scope, partly due to the difficulty of finding real datasets for hierarchical clusterings with ground truth. However: why not compute your proposed dual objective scores for all tested datasets and see how the algorithms compare?", "methods_and_evaluation_criteria": "Yes, though more testing could have been done (see my question about more options).", "theoretical_claims": "I did not verify the correctness of proofs in the appendix, but some of them were plain to see how they worked and the others are certainly plausible. Proofs were mentioned to be in the appendix wherever applicable.", "experimental_designs_or_analyses": "The experimental designed seemed okay to me, though, as mentioned, there may be more tests they could run.", "relation_to_broader_scientific_literature": "This is the first proposal of a formal objective for hierarchical overlapping clustering. It is notably defined off a seminal work by Dasgupta on regular hierarchical clustering. This is certainly an interesting area that I am surprised has not been studied this rigorously before. It could certainly open up an entirely new niche of study, though I do have qualms with their formulation (discussed later).", "essential_references_not_discussed": "None that are essential.", "other_strengths_and_weaknesses": "Strengths\n1. Very interesting niche that should be studied\n2. Nice extensions of seminal works by Dasgupta and Moseley & Wang\n3. Shows some nice simple algorithms for this problem\n4. Solid set of experiments\n\nWeaknesses\n1. I have significant qualms with the proposed model, all of which can be found in the \"Questions\" section\n2. Algorithm 1 is extremely limited (flat overlapping clustering, only 2 clusters). It doesn't even consider the hierarchical aspect, which seems central to this paper. That being said, it is interesting in useful, but it's the only algorithm they propose that approximates their proposed objective as opposed to it's dual, and it's rather disappointing in its limitation.\n3. Experiments could be extended\n\nUltimately, I believe this paper should be published since it initiates an interesting field of study. It also seems to do it in the \"right way\" with its foundations in the Dasgupta paper, however, the formulation and results are weak. I lean towards acceptance, but am not sure if this truly meets the bar for ICML.", "other_comments_or_suggestions": "I basically formulated these in the \"Questions\" section. There are typos/weird phrasings around, but I did not write them down. It doesn't significantly impede comprehension.", "questions_for_authors": "1. Are (3) and (4) necessary for Property 2.6? I would think they would be implied by the fact that S is an anti-chain and N in S is ordered between X and Y.\n- EDIT:I see (1) and (2) don't cover the \"maximality\" aspect, but can't you just say it's a maximal set that satisfies those two properties? I think that would be much more natural\n\n2. Along the same lines, shouldn't the statement be \"For two nodes X and Y... for any node set S...\" Instead of \"if\" there is a node set S? There would only not exist such a set if they were parent/child right?\n\n3. Consider the example from your paper Fig 1(b). Here, c is assigned 1/2 to both N1 and N2. Am I correct to say that there is only one MCA of (b, c), which is N1, and only one MCA of (c, d), which is N2? Then, the contribution of cost from these edges are just $2w(b, c)$ and $2w(c, d)$ respectively, which is the minimum contribution possible. This feels like cheating to me - shouldn't the partial assignment of c to N2 hurt how much (b, c) contributes to the cost?\n\nFor instance, say we removed the edges (a, c) and (b, c) from the graph 1(a) entirely. Shouldn't there be some negative impact on the cost, now that c is partially assigned to N1 and N2? It SHOULD just be assigned to N1, but it doesn't seem like a loss to add another assignment in this case. This doesn't seem like a desirable property.\n\nI think this issue is something you're hiding behind the example 1(d). You're trying to say there IS  a cost to having too many assignments, but that only happens when pairs of vertices are given multiple overlapping assignments unnecessarily, since it increases the number of MCAs there are for an edge. Ultimately, I think my problem here is how you've defined MCA: it feels like N1 AND R should both be partially MCAs of (b, c) in 1(b), since c's assigned partially to N1 and N2.\n\nNote: The issues here are not resolved by bounding the width of the graph.\n\n4. You claim that the longest anti-chain blocks all paths from leaves to root. Is this actually true? Consider the HC tree which is a leafy stick (a and b merge, then they merge with c, then d, ...). The longest anti-chain here is just a single node! Unless, that is, if you include leaves in the anti-chains (but they aren't included in the width, so it seems weird...) You might want to require that there is some anti-chain that DOES do this (e.g., the children of the nodes in the chain consist of precisely the set of leaves).\n- EDIT: Is this actually covered by condition (3) in definition 2.1? I may have just missed this\n\n5. Dual HOC: Can you briefly mention the Moseley and Wang dual when you define this on page 5? Since this is the corresponding problem in the HOC setting.\n\n6. In Proposition 3.2, you talk about using approximation methods based off the max potential dual, n*w(e). In HC, Moseley and Wang did a lot of analysis with this max potential dual, and there are similar limitations (I think it's 1/3 or 1/2). It would be great to find where this happens and cite it here! I can't remember off the top of my head .\n\n7. Can you give some intuition as to why the algorithm approximation for the primal is dependent on the degree ratios?\n\n8. I don't know much about stochastic block models - are they hierarchical in structure? I would think you'd want a hierarchical one to show what happens when you're not just representing a flat clustering.\n\n9. What is NMI?\n\n10. Why not compute your proposed dual objective scores for all tested datasets and see how the algorithms compare?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LyE5GhhZKg", "reviewer": "Reviewer_7SG8", "summary": "This paper studies hierarchical overlapping clustering (HOC), in which vertices are assigned to a hierarchical structure of overlapping clusters. In comparison with non-overlapping HC, we construct a DAG rather than an HC tree.\n\nThe paper introduces an objective function for this problem, generalising Dasgupta's cost function for HC, and gives a constant-factor approximation algorithm for the dual objective. Finally, the paper includes some experimental evaluation and compares the algorithm with non-hierarchical overlapping clustering algorithms, finding that the new algorithm has a faster running time.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the careful review and valuable comments. Let us address the concerns one by one.\n\n1. 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.\n\n2. 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.\n\nWe thank the reviewer again and are happy to address any remaining concerns.", "claims_and_evidence": "The paper claims three contributions:\n\n1. The introduction of a new cost function for hierarchical overlapping clustering. This is a new problem, not previously studied and so the introduction of such a cost function is quite original. The given objective function extends Dasgupta's cost in a sensible way to the case with overlapping clusters.\n2. An approximation algorithm for the dual of the proposed cost function. This is theoretically justified and the claim stands as stated. However, I feel that it is not particularly significant given that the approximation is based on universal bound on the cost of any output produced by the proposed algorithm. That is, there is no theoretical proof that the algorithm performs better on instances with a better optimal cost.\n3. The scalability of the proposed algorithm is demonstrated through empirical evaluation. The evaluation justifies the claim, although the tested datasets are of relatively small size (up to 10000) and so it is not clear that the proposed algorithm applies in practical scenarios.", "methods_and_evaluation_criteria": "My only concern with the evaluation criteria is the size of the tested datasets. It would be interesting to see if the proposed algorithm could scale to 100,000 vertices, or more.", "theoretical_claims": "The theoretical claims appear sound, although I did not check the proofs in detail.", "experimental_designs_or_analyses": "See the answers above.", "relation_to_broader_scientific_literature": "The results build on the cost function for hierarchical clustering proposed by Dasgupta, and generalise this in a reasonable way to the problem of detecting overlapping clusters, which has been studies only in the non-hierarchical setting.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "I feel that the proposed cost function is interesting, but the key weakness of the paper is in the theoretical results. It would be interesting to prove a guarantee on the performance of the algorithm that depends on the optimal cost function of a specific graph.\n\nEdit:\nBased on the responses of the authors, I have raised my score.", "other_comments_or_suggestions": "The text in figure 2 is unreadable - it would be better to make it bigger.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Both of hierarchical and overlapping clustering are important topics in machine learning, and the current submission studies hierarchical overlapping clustering. All the reviewers gave positive evaluation on the submission, and it should be a clear accept for the paper.

The reviewers listed several downsides on the experimental studies of the paper, and I hope that the authors could take the reviewers' comments into account when preparing the next version of the paper.
Decision: Accept (poster)