TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization
Authors: Haowen Ma
Zhiguo Long
Hua Meng
Venue: ICML 2025 poster (2025)
Keywords: clustering
density-based clustering
mode-seeking
spectral clustering
Primary area: general_machine_learning->clustering

Abstract: Density-based mode-seeking methods generate a density-ascending dependency from low-density points towards higher-density neighbors.
Current mode-seeking methods identify modes by breaking some dependency connections, but relying heavily on local data characteristics, requiring case-by-case threshold settings or human intervention to be effective for different datasets. To address this issue, we introduce a novel concept called typicality, by exploring the locally defined dependency from a global perspective, to quantify how confident a point would be a mode. We devise an algorithm that effectively and efficiently identifies modes with the help of the global-view typicality. To implement and validate our idea, we design a clustering method called TANGO, which not only leverages typicality to detect modes, but also utilizes graph-cut with an improved path-based similarity to aggregate data into the final clusters. Moreover, this paper also provides some theoretical analysis on the proposed algorithm. Experimental results on several synthetic and extensive real-world datasets demonstrate the effectiveness and superiority of TANGO. The code is available at https://github.com/SWJTU-ML/TANGO_code.

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Cut Optimization
Haowen Ma
Zhiguo Long'
Hua Meng?
Abstract
Density-based mode-seeking methods generate a density-ascendinng dependency from low-density points towards higher-density neighbors. Cur- rent mode-secking methods identify modes by breaking some dependency connections, but rely- ing heavily on local data characteristics, requir- ing bassee threshold settings or human in- tervention to be effective for different datasets. To address this issue, we introduce novel con- cept called typicality, by exploring the locally defined dependency from global perspective, to quantify how confident a point would be a mode. We devise an algorithm that effectively and efficiently identifies modes with the help of the global-view typicality. To implement and val- idate our idea, we design clustering method called TANGO, which not only leverages typical- ity to detect modes, but also utilizes graph-cut with an improved path-based similarity to aggre- gate data into the final clusters. Moreover, this paper also provides some theoretical analysis on the proposed algorithm. Experimental results on several synthetic and extensive real-world datasets demonstrate the effectiveness and superiority of TANGO. The code is available at https:/ sithub..cmm Bt/////JJJJJMM WWW-MMLLTTAAAAOOOOA
Figure I. Illustration that whether point should be considered as mode is influenced by the global structure of the dataset, which varies with the presence of gray points. Here, each data point links to its nearest neighbor of higher density.
and Quick Shift (Vedaldi Soatto, 2008) are two of the most representative density- based modc-seeking methods. Mean Shift iteratively converges data points into multiple clusters along the path of the steepest ascent of the den- sity function. In contrast, Quick Shift enhances efficiency by establishing a denssity-ascending dependency through directly linking each data point to its nearest neighbor with higher density and uses a distance threshold to break the dependency to obtain modes and clusters, climinating the iterative process of Mean Shift. However, Quick Shift highly sensitive the threshold parameter, and it always misidentifies outliers as modes.
Building upon this, Density Peaks Clustering (DPC) (Ro- driguez & Laio, 2014) introduces novel approach to detect modes, where modes of the data (cluster centers) are se- lected based on a decision graph given by both the local density and the distance the nearest point with higher density. Each non-center point continues following the aensity- dependency like Quick Shift, ultimately connecting mode (cluster center) to complete cluster- ing. Subsequent researchers have proposed various improve- ments of DPC tailored for manifold-struuctrred, unevenly dense, and noisy data (Liu et al., 2018; Wang et al., 2023).
1. Introduction
Density-basel clustering methods (Hartigan, 1975; Ester et al., 1996; Tobin & Zhang, 2024) have gained wide atten- tion and thorough investigation due to their capability in han- dling complex data distributions. Mean Shift (Cheng, 1995)
However, local data characteristics such density and dis- tance of neighboring points are sometimes not enough to appropriately determine if a data point should be considered as a mode. As illustrated in Fig. (left), when the dataset consists of only the blue and orange points, the point P rep- resents the density peak of sparse cluster containing only a few points. In this scenario, such a small cluster would usu- ally be considered as outliers and should be merged into a
'School of Computing and Artificial Intelligence, Southwest Jiaotong University, Chengdu, China "School of Mathematics, Southwest Jiaotong University, Chengdu, China. Correspon- dence to: Zhiguo Long <zhiguolong @ swjtu.edu.en>> Hua Meng <menghua@e @ swjtu.edu.cn>.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

TANGO: Clustering with Typicality-Aware Nonlocal Mede-Secking and Graph-Cut Optimization
neighboring higher-density cluster, indicating that should not be identified mode in this case.
We introduce typicality reveal the global importance of data points under locally defined density-based de- pendency, and utilize it to detect modes in way with- out human intervention; we also provided theoretical analysis on the uniqueness and statistical property of typicality, as well as on computational efficiency of the algorithm.
On the other hand, when the gray points are included in the dataset (right, Fig. 1), the cluster whose density peak is P becomes substantially larger and forms a distinct group within the data distribution. In this case, merging it into another cluster would be inappropriate, suggesting that P should indeed be recognized as a mode.
An improved path-based similarity is devised to com- prehensively and efficiently evaluate the similarity of sub-clusters and graph-cut is employed to determine the final clusters.
In fact, despite the local distribution around P remains con- stant, the varying global patterns will change the confidence for P to be a mode. Existing approaches like (Vedaldi & Soatto, 2008; Rodriguez & Laio, 2014; Jiang et al., 2018; Wang et al., 2023) can only address such scenarios through case-by-case threshold settings or substantial human inter- vention, which is ineffective across datasets or even imprac- tical.
The rest of this paper is organized as follows: The next two sections review related work and preliminaries, and then we present the details of the proposed TANGO algo- rithm, followed by comparison of TANGO with multiple state-of-the-art algorithms on extensive datasets through experiments.
We found that the confidence for a point P to be a mode can be naturally revealed from global perspective via the density- ascending dependency. Specifically, we introduce the concept of typicality, which measures how confident a point would be mode, by considering the collective set of points that ultimately converge toward it through the density-ascending dependency, well as the strength of the dependencies. Points with higher typicality are more likely to be modes, and by comparing the typicality of point with that of its higher-density neighbor, we can determine whether to break the dependency at this point to form a mode. For example, in Fig. (left), the typicality of P is lower than that of Q, and the dependency from P to Q should be retained; while in Fig. I (right), the typicality of P is higher than that of Q and the dependency should be broken. In this way, typicality enables mode-seeking that eliminates the need for more human intervention in such cases and better captures the inherent cluster structure.
2. Related Work
Our proposed method leverages mode-secking and spectral clustering. The following discussion reviews the correspond- ing relevant literature.
2.1. Density-Based Mode-Seeking
Density-based bbase clustering by mode-seeking relies on density estimation, establishment of dependency relationships and identification of modes (e.g., density peaks).
The carlier Mcan Shift (Cheng, 1995) iteratively moves each data point to the mean of its neighborhood, which is equiva- lent establishing dependency relationships in the direction of the steepest ascent of density (Arias-Castae et al., 2016). Quick Shift (Vedaldi & Soatto, 2008) establishes depen- dency relationships by directly associating each point with its nearest neighbor of higher density, and identifies modes as points not dependending on others, which significantly ac- celerates Mean Shift. HQuickShift (Altinigneli et al., 2020) integrates hierarchical clustering with Quick Shift and Mode Attraction Graph to help determine the hyperparame- ter for establishing dependencies, to deal with the sensitivity to hyperparameters of Quick Shift. Quick Shift++ (Jiang et al., 2018) improves Quick Shift by computing density using k-nearest neighbors and identifying modal-sets (Jiang & Kpotufe, 2017) instead of point as modes, which are connected components of mutual neighborhood graph de- termined by density fluctuation parameter. DCF (Tobin & Zhang, 2021) improves the efficiency of modal-sets identifi- cation based on Quick Shift++. CPF (Tobin & Zhang, 2024) reduces the sensitivity to the density fluctuation parameter.
In this work, we develop a novel clustering algorithm TANGO, which leverages the proposed typicality to detect modes and employ graph-cut technique (Ng et al., 2001; I Long et al., 2022) with an improved path-based similarity to aggregate data into final partition. Particularly, we first partition the data into tree-like sub-clusters by a typicality- aware mode-seeking approach; then, the inter sub-cluster similarities are evaluated through an improved base- connectivity (Fischer al., 2003; Chang & Yeung, 2008; Little et al., 2020); and finally, by using a graph-cut method, we aggregate the sub-clusters from a global perspective.
The contributions of this paper are as follows:
By integrating local and overall distribution character- istics of data, a new clustering framework that fuses local and global information is proposed, introducing a new global perspective into mode-seeking methods.
Compared with Quick Shift and its variants, the essential difference of DPC (Rodriguez Laio, 2014) 4) is that it iden-
2

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
tifies modes by decision graph of density and distance. Optimizations of DPC usually focus density estimation, modes identification, and dependeney relationships. DPC- DBFN (Lotfi et al., 2020) employs fuzzy kernels to compute density and identifies connected components containing cluster centroids in mutual KNN graphs. SNN-DPC (Liu et al., 2018) considers shared nearest neighbors to better characterize similarities and further refines the dependency relationships for boundary points by KNN voting strategy. VDPC (Wang et al., 2023) utilizes two user-defined param- eters to optimize dependency relationships. DPC-GD (Du et al., 2018) and DLORE-DP (Cheng et al., 2020) address manifold-structuree data by substituting Euclidean distance with geodesic distance. However, these approaches only focus on locally defined density and dependency, lacking global characteristics of data.
Algorithm Quick Shift
Require: Dataset X, similarity matrix A, density A simi-
larity threshold т
Ensure: Mode mode, Clustering results labels
I: mode < 2; Initialize dependency matrix B as zero matrix
2: for each 2, E X do
3: 33 < argmax Aij
2y:0y>p
4: Biy f Aij
5: for each point 2; with Bi o do
if Bij < r then
Bij f
8: mode mode {2y}
9: Initialize cluster label array labels
10: for each 2; E X do
11: Te <- Iz
There also exist methods that initially create sub-clusters
12: while Te $ mode do
by utilizing the censity-ascending dependency derived from DPC and Quick Shift, and then aggregates them using other clustering techniques to obtain final clustering results. For example, to aggregate sub-clusters, FHC-LDP (Guan et al., 2021) and LDP-MST (Cheng et al., 2021) use hierarchi- cal clustering; LDP-SC (Long et al., 2022) and DCDP- ASC (Cheng et al., 2022) use spectral clustering: NDP- Kmeans (Cheng et al., 2023) applies K-means clustering with geodesic distance; DEMOS (Guan et al., 2023) uses a linkage-base based approach to aggregate these sub-clusters.
13: Find j where Bej #
14: Ie f Ij
15: labels(xx)) <- labels(1r.)
16:
return mode, labels
3. Preliminaries
Let = (x1,...,, denote set containing n data points, where 2; E Rd represents a data point. Let A E I be the similarity matrix among the data points, and ps de- note the density of vg. Assuming that dependency matrix B E gnx= has been constructed based on A, where Bij represents the dependency from 2; Zzz- The specific defi- nitions of these concepts will follow later in Section 4. In
2.2. Spectral Clustering
Spectral clustering algorithm (Ng et al., 2001; von Luxburg, 2007) is a classical graph-cut method, which partitions the vertices of a graph by applying K-means on the spectral embeddings obtained through the eigenvectors of the graph Laplacian matrix. It was noticed by (Lee et al., 2014) that the k-th smallest cigenvalue of the normalized Laplacian matrix determines whether graph could be well well-partitioned into k groups, and the upper bound on the number of ver- tices misclassified by spectral clustering has been proven by (Kolev& & Mchlhorn, 2016; Macgregor & Sun, 2022: Mizutani, 2021: Peng et al., 2017). To improve the effi- ciency of spectral clustering, sampling-basee et al., 2009; Chen et al., 2011; Cai & Chen, 2015; Huang et al., 2020) were used to reduce the size of similarity matrix and the cost of deccoppcomooiiionn, and there is also some method (Macgregor, 2023) that leverages a power method to completely avoid the time-consuming eigen-decomposition. When the number of target clusters is not pre-specified in spectral clustering, series of methods (Xiang & Gong, 2008; von Luxburg, 2007; Brandes al., 2008; Zelnik- Manor& & Perona, 2004) have been developed to deal with this situation.
this section, we briefly introduce how Quick Shift and DPC work.
3.1. Quick Shift
As described in Algorithm 1, for each data point 2; E X, Quick Shift sets Bi Au if and only if x, is the near- est higher-densin neighbor of r;, to establish the density- ascending dependency. Quick Shift then breaks the depen- dency point x; and recognize x, as a mode if A, is less than the human-determined similarity threshold. All points that converge to the same mode through the dependency are considered as in the same cluster.
methods (Yan
3.2. Density Peaks Clustering
The only difference between Density Peaks Clustering (DPC) and Quick Shift is that DPC considers not only simi- larity but also density to break the dependency and obtain modes. Specifically, DPC breaks the dependency from ø; to its nearest higher-density neighbor x, if Ai is less than the similarity threshold and (; is also larger than the den-
3

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
sity threshold simultaneously, avoiding identifying some outliers as modes.
where By: + 0 iff there is a dependency from Ij to x4 Note that the definition of typicality in Eq. (1) is recursive and actually captures the weighted influence of all points that converge to I; through the dependency relationship. For instance, as shown on the right side of Figure 2, we have T(;;) = 11; + (2, + Bg,T(2s) + Pi. and T (xx) = pl. Txx2) = (raT( + p2, T(ra) = p3+ T(xA) pt. Then [ B + B2x (B12Pt + P2) + B3:p3 + Pt, indicating that 2; collects typicality from F1,
In fact, not only Quick Shift and DPC, but also many other existing mode-seeking approaches (Jiang et al., 2018; Wang et al., 2023; Guan et al., 2023) require human intervention or case-by-case threshold setting to identify modes effectively.
4. The Proposed TANGO Algorithm
22, 33 and F4, which are all points that converge to it.
The overall framework of the proposed TANGO algorithm is shown in Figure 2. TANGO will first construct a density- ascending dependency graph by exploring local similarity and density structures; then evaluate the typicality of points by exploring the dependency from global perspective, and break some of the dependency connections by exploiting typicality to identify modes and sub-clusters; and finally, use graph-cut with improved path-based similarity to aggregate sub-clusters to achieve clustering.
Let = (Ti, T2,,...., TT) and = (p1. P2. P2) column vectors. Eq. (1) can be rewritten as:
T be two
T = BTT
(2)
Remark If we consider each data point in a dataset as individual webpage weighted by its density, and for each page there exist hyperlinks linking to its neighboring higher- density pages. Thus, the proposed typicality can also be considered as special kind of PageRank Centrality (Brin & Page, 1998; Avrachenkov & Lebedev, 2007; Avrachenkov et al., 2018; Chen et al., 2017; Litvak et al., 2006; Volkovich et al., 2007), where B.y denotes the probability from æ; jumping to Zz.- When x; is a distinct mode, it creates a so-called "attraction basin" region where all points ulti- mately converge toward x; through the dependency, and z; collects typicality from all points in its "basin".
4.1. General Definition for Typic Typicality
In the traditional mode-secking framework, algorithms like Quick Shift and DPC make data points depend on their near- est higher-density neighbors to generate a density-ascending dependency. While these methods balance efficiency and ac- curacy, with some theoretical guarantees (Jiang, 2017; Tobin & Zhang, 2024), they primarily consider local information such density and similarity break the dependency and obtain modes, making them require extensive human inter- vention such as case-by-case threshold setting or manual operation to identify modes effectively.
4.2. Typicality Based on Hierarchical Dependency
We propose a specific typicality measure based on hierar- chical dependency, where each data point only depends on its nearest neighbor with higher density. Hierarchical dependency has been widely used in many density- clustering methods such as (Vedaldi & Soatto, 2008; Ro- driguez& & Laio, 2014; Jiang et al., 2018; Guan et al., 2023; Tobin & Zhang, 2024; Cheng et al., 2021). Its consistency guarantee has also been theoretically proven by several ar- ticles such as (Jiang, 2017; Tobin & Zhang, 2024). First, we introduce some basic definitions to uncover such de- pendency within the dataset. Subsequently, we analyze the theoretical properties of corresponding typicality.
To address this drawback, we propose to further explore the dependency relationship to model a global-view "typ- icality" of points to quantify the confidence for them to be modes. We suppose that typicality should satisfy the following postulates:
(P1) Typicality should consider the own density of point. Points with higher density may have higher confidence to be modes, as they represent significant concentrations in the data distribution.
Complex data often exhibit specific manifold structures and its similarity can be better reflected by shared nearest neighbor information (Jarvis & Patrick, 1973; Liu et al., 2018). Therefore, we define a similarity measure based on shared nearest neighbors, and we further distinguish the different contribution to similarity of each shared neighbor to have better robustness.
(P2) The typicality of a point should also be related to all points that ultimately converge toward it through the Censity-ascenddiee dependency, as well as the strength of the dependencies (matrix B). If point accumulates stronger dependencies from its descendant points, then this point is more likely to be a genuine mode.
Definition 1 (Similarity). For any two data points 2;, zj X, let (x,);) and Nε(2,) denote the k nearest neighbors of x. and æy, respectively, and SNN = N*(())) n
Given these postulates, we can define typicality T; for each point 2; generally as:
T = P. D B
(1)
Nz(z)). The similarity A(z,, (or Aij) is defined as:
A(rs, EPESNN. (m..a)) exp(- d(p.z.)+d(p... )2 if
2d
4

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
Dataset
Local Structure Exploration
Hierarchical Dependency Graph
Global Structure Exploration
Denalty
Leader
Similarity Matrix A
Dependency Matri B:
expp
mnkfa
Typicality:
T(=) BuT(as) + Baf((a)) Ba)((ss +
Bupi (m( ps) + Bups +
Bupi (Baps
Global Similarity Exploration
Final Result
Spectral Clustering
PaSinin.rt) maseve, (ulngg-- Alph)wa) plx)) eis-3))
natt-aasd Similartty subckusters
Break Dependency by Typicality
+
PRSie fal
Ited 2t))
P28mm((s.7))
Figure 2. The framework of the proposed TANGO algorithm.
Iy E Nx(z)) 2j Nx;x,,, and 0 otherwise. Here, d denotes the Euclidean distance between two points, and dmax is the maximum Euclidean distance between any point and its k nearest neighbors in the dataset.
dependency constructed by allowing each point depending its leader if it exists.
Beyond that, we should further consider the strength of such dependency. For instance, if a point is closer to its leader, the dependency of them should be stronger. How- ever, directly considering similarity can lead stronger connections in dense regions and weaker connections in sparse ones. Therefore, we propose considering the position of the leader within the sequence of neighbors sorted by similarity.
Based on the above definition of similarity, we define the density of points as usual with normalization.
Definition 2 (Density). For 2; E X, let L(x;) denote the set of points most similar to xy in terms of the similarity matrix A, where le is the same one used in Definition Then, the density of Iı is:
Definition 4 (Rank). For æ; X, let (x;);) denote the list of its neighbors sorted in descending order of similarity. Let Zj leader(z.). We define rank( as
p(x;) Epe((E)) A(z,,P) P)
max Eper(H) A(x.p)
rank(x;)= = r
xj ranks r-th in Nx(e) None if xı None
To obtain the dependency matrix B, similar to Quick Shift and DPC, we can establish a hierarchical density-ascending dependency within the dataset based on similarity and den- sity information as following, known leader relationship.
(5)
That is, if o; has a leader, then rank( represents the position of leader(z;) in the list neighbors sorted in de- scending order of similarity di-
Definition 3 (Leader relationship). For Fy, let higher(1..) denote the set of points with higher density than o; and nonzero similarity 2i, i.e., higher(z;) {p X
We then define the dependency matrix B Raxn as fol- lows:
p(p) > p(xx), A(r,,p) + 0}. The leader point of x; is:
argmax Aij if higher (aagher(x.: + Ehigher(z.)
rank(a.)) )3 exp((
leader(z:) =
Bij
max(rank)
if 21 leader(x;) (6)
None otherwise.
0
otherwise
(4)
where max(rank) is the maximum value of rank among all points.
According to the above definition, leader(z;) is the point with higher density than z; that has the highest similarity to Zg. If D, has zero similarity with all points of higher density, then z; has no leader. Then the density-ascending
Note that since each point has at most one leader, each row of matrix has at most one non-zero element, and the
5

---

TANGO: Clustering with Typicality-Awar Nonlocal Mode-Secking and Graph-Cut Optimization
dependency relationship is actually in hierarchical form and partitions the data into disjoint tree-like sub-parts.
and Incrmelizzed for visuelication
0.8
When computing the typicality T, the non-zero elements of matrix B specify the weights of contribution of the points to the typicality of their respective leaders. Using ran)(r;) to compute the weight can avoid the bias favor dense region.
0.6
0.4
Density IP]
Theorem 1. For B defined in Eq. (6), there exists a unique typicality vector T such that = BUT + p (Eq. (2)) holds.
0.2
Density (0)
Typicality (P)
Typicality (0)
Number added gray points
Proof. See Appendix A.I.
As stated in the following theorem, solving for the typicality T defined by Eq. (6) is highly efficient.
Figure 3. Evolution of density and typicality for points P and Q as gray points are incrementally added Fig.
Theorem 2. For B defined by Eq. (6), data points Fi....,22 Zn sorted by density p in ascending order, then T satisfying Eq. (2) (T BTT + p) can be computed in (nn) time.
Specifically, for x; and its leader zy,
Tf;) < T(z;), then we keep the dependency from 2; to 235
Proof. From the proof of Theorem 1, it is known that BT is a lower triangular matrix with ones on the di- agonal when the data points are sorted in ascending order of density. This implies that the system of linear equations (I-B p be solved by forward substitution, com- puting Tı, T,.,,,... let T Fig, ..... Li, be the set of points whose leader is Tis we have 7, = T +... BB, :Ti, + (f,,..., is. < í and Vt= = l..... 8t. Bi,, * 0). As the graph induced by B consists of trees, we have E 8, S nn- Thus, comput- ing all T3 requires (nz operations.
if T(;)) 2 T(x;), then we break the dependency and assign Ia as mode and the root of corresponding tree-like sub-cluster.
Remark 3. That is to say, points with higher confidence to be modes should not be represented by those with lower ones. Ij can represent x; if and only if x can accumulate more typicality than (1- (1-B Txx;) from its own density Pj and other points excluding xy.- Either larger T(x;) or weaker dependency from x, to I, would reduce the ability of æj represent I;, while the density of xy and typicality accumulated from other points enhance its ability to represent 2;,
.... Tn in sequence. For each data point xi,
Based on the above theorem, to calculate T, can first sort .1, Fn by density in ascending order, and then compute 7' sequentially for i from 1 to n as: T(æ;) + T(æ,) + T(x;)- . Bi, where z, = leader(z;.. Note that when x; contributes typicality to its leader, the typicality of o; itself (Tx);)) has already been fully determined due to the ascending order of density.
Fig. 3 illustrates the evolution of density and typicality for points P and Q as gray points are incrementally added in Fig. 1. The results demonstrate that T(P) keeps growing and ultimately surpasses T(Q), allowing the algorithm to automatically determine whether to break the dependency at form mode. The procedure to calculate typicality and use it to detect modes is given in Algorithm 2.
Remark Under Theorem 1, we can also directly get the closed form T' = (1- BT) lp and expand it into the sum- mation of infinite series T (BT)) which can be more intuitive and interpretable to understand how typicality comes from, as ( y captures the weights of all l-hop paths in the dependency graph induced by B.
Remark 4. From a stochastic equation perspective, the tail behavior of typicality follows power law distribution, which means that the possibility of data points having high confidence to be modes decreases polynomially. See Ap- pendix B.
4.3. Typicality-Aware Mode-Seeking
4.4. Aggregating Mode-Centered Sub-Clusters
Typicality considers both local density distributions and global structural information as shown in Eq. (2). Points with higher typicality have higher confidence to be modes. Therefore, we break the dependency with the help of typi- cality and obtain modes accordingly.
After obtaining the modes and corresponding tree-like sub- clusters based on typicality, we then use graph-cut method to aggregate them into final cluster partitions. To better reflect the inter-sub-cluste similarities based on the overall
6

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
Algorithm 2 Typicality-Aware Mode-Seeking
The final clustering result is then obtained by applying spectral clustering these sub-clusters. Specifically, vertex in
Require: Dataset X; leaders leader: density p; rank de- fined in (5); dependency matrix B.
consider each mode-centered sub-cluster similarity graph, where the similarity between these sub- clusters is determined by the above path-based similarity PBSim(r;, ry), ) and finally the spectral clustering with Nor- malized Cut (von Luxburg, 2007) applied to aggregate these vertices into a final partition with the specified number of clusters.
Ensure: mode.
1: mode <-
2: for all x; E X do
3: T(x;) + p(x;))
4: for all x; E X sorted by ascending order of do
5: 33 f (ea
6: T(x;) + T(x;) ) + T(;)) Bij
The reason why choosing spectral clustering for merging sub-clusters is that it comprchensively considers global graph-cut cost of the whole partition, unlike other methods such as hierarchical clustering, which partitions the data greedily and ignores the global impact on the whole partition at each greedy step, thus always achieves an inferior or imbalanced partition.
7: for all I; E X do
8: if T(x:) 2 ((leader(z)) or leader(z;) = None
then
9: mode + mode U {z;}
10:
return mode
data distribution, we introduce an improved path-based similarity between them based the similarity of data points defined in Definition and inspired by (Fischer et al., 2003; Chang & Yeung, 2008; Little et al., 2020). This similarity considers global connectivity in addition to local similarity. Intuitively, the path-based similarity between two sub-clusters is the maximum "connectivity" among all paths connecting them, where the "connectivity" of each path is the minimum similarity between adjacent points on that path.
Algorithm 3 and Fig. 2 outline the overall procedure of the proposed algorithm TANGO. Here, a variant of Kruskal's algorithm is utilized to compute the path- based similarity and the procedure can be highly efficient, as shown in the following theorem.
Theorem 3. Path-based similarity between sub-clusters defined by Definition 5 can be calculated in O(nk log (nk)) time.
Proof. See Appendix A.2.
Definition 5 (Path-based similarity between sub-clusters). Let ry and r, denote the modes of two tree-like sub-clusters G2 and Gy generated by Algorithm 2, and let G be the similarity graph constructed based on the similarity matrix A. Define Più as the set of all paths in G connecting r; and Ty and let ps and Ph+1 be an adjacent pair of points on path P E P.j. The similarity between G, and Gj is given by the following path-based similarity between their modes:
4.5. Time Complexity
Let n, d be the number of data points and dimensionality for dataset. For convenience, we use q to denote the number of modes detected by Algorithm 2. The time complexity of TANGO can be analyzed as follows:
PBSim(ru.r)) = max min PEPi
C(p.. ((ph.Pn-i) (7)
Line I: O(dn lo d) for calculating A with KD- Tree, and O log(kn) + kn) for computing density and leader.
PSh<|PI
where C(p,, P1+1) = 1 if 3G, s.t. Ph. Ph+1 E Gt, and C'pa. Ph+1) = A(ph, Ph+1) p(pn) p(p)41) otherwise.
Line 2: O(n log n) for sorting data points and comput- ing T according to Theorem 1.
Before computing path-based similarity PBSim(ra, ry). we first adjust all direct similarities by weighting them accord- ing to the densities of the points, as A(ph, Ph+1) p(p)) p(pa+1), 1), ensuring that paths through high-density regions have higher "comnectivity" and those through low-density regions have lower "connectivity". Furthermore, ensure that PBSim(r., ry) is determined by pairs of points belong- ing to different sub-clusters, we set the similarity between all points in the same sub-cluster to the maximum possible value 1. More formal description about path-bases similar- ity PBSim(r,, ry) can be found in the proof of Theorem 3 in Appendix A.2.
Line 3: O(n).
Lines 4-11: O(nk log(nk)) according to Theorem 3.
Lines 12-15: O(q² + n) for spectral clustering and label assignment.
Therefore, as k.g < n, the overall time complexity of TANGO is O(nkdd), and is dominated by the similarity matrix calculation which can be easily parallelized. The practical running times are shown Appendix C.4.
7

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
Algorithm 3 TANGO
SA Quick SNN
DPC
TANGO nypicality cafter
EEER TANGO (fnal)
Require: Dataset X, parameter h.
Ensure: Clustering results labels.
1: Calculate A as in Definition I, / as in (3), and leader
in (4)
2: Calculate mode using Algorithm
3: edges + 0, CC(r;) t i(Vr, E mode), PBSim + O [2))) 2 E X and C( -.2) + } according to Definition where r(x;) denote the mode of sub-cluster which x; belongs
4: Prepare edges +
5: for all (C(a,, zy), r(z)),((r)) E edges sorted in de-
scending order of C(r; mj) do
6: if (C(((z))) # CC(r(z,)) then
7:
CC; + {p E mode CC(p) = cC(r(a:))) CC, + {p E mode CC(p) cC(r(z)))) CC(p:) < (C(((r;)) for all ps E CC;
8:
9:
for all (r), CC; CC2 do PBSim(ra. Zz)
11:
Figure 4. Results on synthetic datasets. For TANGO, the hyper- parameter is set to 20, 30, 70, and 30, respectively. Quick Shift and DPC, tune their hyperparameters achieve rea- sonable number clusters while maximizing the Adjusted Rand Index (ARI).
12: Apply Spectral Clustering on mode with PBSim to ob- tain clustering results labels 13: for all I; E X mode do
14: r(x;) f- the mode of N2
labels(x;; <- labels(r(a:))
return labels
Dataset
d
#Clusters
wdbc
569
30
heartEW
270
13
5. Experiment
segmentation
2100
19
semeion
1.993
256
10
In this section, we first visualize the clustering results of Quick Shift, DPC, and the proposed TANGO algorithm synthetic datasets; then we compare TANGO with 10 exist- ing clustering methods on 16 real-world datasets, and also apply TANGO to image segmentation tasks to further vali- date its effectiveness and efficiency; finally, we analyze the effects of the hyperparameter and proposed components (See detail in Appendix C). We also provide some additional discussion in Appendix C.7.
semeionEW
15933
256
10
ver2 310
6
3
synthetic-control
600
60
waveforrm
5000
21
3
Congress
435
16
2
mfcat-zer
2000
47
10
ionosphereEW
351
34
banknote
1372
isolet1234
6238
617
26
Leukemia
72
3571
2
MNIST (AE)
10000
64
10
Umist (AE)
575
5.1. Visualization Synthetic Datasets
Table I. Summary of real-world datasets.
Fig. 4 shows the visualization of dependency relationships and clustering results for TANGO compared with the clas- sical Quick Shift and DPC on four toy datasets, where the red arrows (with blue cross mark) in the 3rd column indi- cating the breaking of dependency via typicality, and the 4th column shows the final clustering results for TANGO. It can be observed that TANGO achieves favorable clustering results by detecting modes effectively based on typicality, while Quick Shift and DPC both perform poorer due only considering the local structure of the data.
5.2. Clustering Real-World Datasets
We compared TANGO with 10 advanced algorithms based density and local dependency relationships, well as graph-cut clustering, on real-world datasets, including LDP- SC (Long et al., 2022), DCDP-ASC (Cheng et al., 2022), LDP-MST (Cheng et al., 2021), XDP-Kmeant (Cheng et al., 2023), DEMOS (Guan et al., 2023), CPF (Tobin & Zhang,
2024), QKSPP (Jiang et al., 2018), DPC-DBEN (Lotfi et al.,
We also include a visualization on some highly- noisy syn- thetic datasets in Appendix C.7.1 to validate the robustness of TANGO to noise.
2020), USPEC (Huang et al., 2020), and KNN-SC! (tradi-
8

---

TANGO: Clustering with Typicality-Awar Nonlocal Mode-Secking and Graph-Cut Optimization
NMI
16.00 024
28.72
64.02
46.32
43.33
12:45
75.99
1926
11.76
85.01
05:40
0.52
31.91
13.00
17.52
39.38
12
$8.34
60:33
13.00
77.35
$3.67
12.02
77.06
03.52
15.43
03.00
16.43
$4.73
95.15
65
96.15
20.00 9:67
4.35
22.00
6.00
27.05
16.3
2507
3337
15.76
39.40
1423
2.00
17.72
13.72
21.21
28
23.57
634
27.60
20.76
72.90
$3.33
14.07
26.00
72.90
00
12.59
01.40
25.58 36.77
15:32
19.33
46.00
35.20
10.75
$3.6
1632
63.37
66:35
16.33
65.57
10.36
63.53
52.64
13:37 66.7
(1.2071.8
70.05
$3.11
13
56.12
18.00
66.37
(3.2
61.42
54.02 36.15
M4.33
11.01
41.34
36.04
18.05
25.69
25.59
5585
16.3
63.40
67333
17.36
63.08
1621
63.54
52.14
04.17
17.04 07
10.00 71.13
10.07
15.20
37.4
41
15,
48.59
57
(7.00
09.13
62
78.35
5:06
13:35
25.70
17.03
17.7
11.54
25.77
62.05
28.01
27/03
13.24
30.32
06 30.31
10.19 32.43
15.16
17.00
61.53
63.12
73.55
28.39 24.20
$1.34
28.00
33.02
50
19.59
0.65
23:17
25.22
39.77
59.5225664
25,64
5485
2958
53.45
39.14
20
5.63
39.00
27.04
41.40
61
46.74
05.30
03.05
57.00
55.75
57.92
28,04
52.08
50
75.12
50.04 0:37
1.50
0.27
23.20
18.44
33.53
5984
51.15
69.54
5311
0.31
2:35
0.54
25.31
30.03
30.74
43.29
53.12
12.45
39.85
08.07
53.01
01.01
05.37
91.72
Sangrance
2.5 182
12:42
24.52
12.5
25.20
13
13.79
40.13
8.22
3.30
13/72
24.00
19:12
13.03
9:73
11.02 41.30
00.00
15.24
12.20
73:34
05.00
52,72 02.05
1.37
0.90
70.50
09
10.35
19.51
10.15
52.62
46.30
96.20
14.4051.28
51.28
4.55
7:50
71.50
91.94
70.72
12.03
61.32
20.30
93.17
$5.45
15.05
37.75
20.07
23.97
23.55
00 33.33
56
00.50
04 93.05
53.40 22.00
8A
24.32
15.52
67.24
22.74
3.00
19.27
20.17
30.57
06.27
MA
50.79
27.49
70.03
14.24
22.50
19.02
16.27
77.93
59.12
10.23
NA
02.05
12.29
02:40
00.44
72:83 45.37
50.75
26.33
57.35
15
11.0
23
1380
66 K3.00
60
16.00
59.55
19.50
23:39
20.26
76 60
77:78
77.35 83.95
18.29
16.72
45
22.21
60 K2.01
d8 50.50
68 91 66.99
37.65
62 58
1166
35.51
1977
50.64 $2.80
77.3 1801
18.00
23
80.14
16 16
47 89
17.67 91.87
73.00
55.33
56
20
10
15,
57
63
16 96
06
76.43
58 94 65.22
Figure 5. Results on 16 real-world datasets (%. bold represents the best for dataset).
tional spectral clustering based on l nearest neighbor graph)
nates represent the RGB color channels. The segmentation is done by clustering this 5 5-dimensional dataset (154 401 pixels). See Appendix C.4.
We evaluated these algorithms using standard clustering metrics: Adjusted Rand Index (ARI; (Steinley. 2004)), Nor- malized Mutual Information (NMI; (Xu et al., 2003)), and Accuracy (ACC; (Yang et al. 2010)).
The effects of the hyperparameter A have been analyzed in Appendix C.5, and the ablation study of TANGO has been shown in Appendix C.6. We also provide a discussion on the limitation about TANGO in Appendix C.7.2.
For fair comparison, all algorithms were tuned to optimal hyperparameters. For TANGO, the neighborhood size k was searched from 2 to 100 with step size of 1. Algo- rithms requiring specification of the number of clusters used the ground-truth number of clusters. The detailed hyperparameter settings of the other algorithms are given in Appendix C.I.
6. Conclusion and Future Work
In this paper, we first proposed a global-view measure, i.c.. typicality, to quantify the confidence for a point to be a mode, to resolve the issue of current mode-seeking methods that they require case-by-case threshold settings or human intervention to identify modes. We also devised an effective and efficient algorithm to calculate the typicality of points, and provide theoretical analysis about it. Furthermore, the clustering method TANGO was designed by leveraging typ- icality to detect modes and form sub-clusters, and utilizing graph-cut with an improved path-based similarity. Extensive experiments on multiple synthetic and real-world datasets demonstrated the effectiveness and superiority of TANGO over state-of-the-an clustering algorithms.
Experiments were conducted on 14 UCI datasets and 2 image datasets (Table 1). All datasets were min-max nor- malized. For image datasets MNIST and Umist, we used AutoEncoder (AF) to reconstruct them into 64-dimensional representations. Fig. 5 presents the results of TANGO and 10 comparison algorithms on 16 real-world datasets. The detailed explanation has been shown in Appendix C.2.
We also obtained p < 0.05 from Friedman's 's test, and the pairwise mean rank differences between TANGO and other comparison algorithms surpassed the critical difference threshold (CD- = 2.30) in subsequent Nemenyi's 's test, indi- cating the superior performance of TANGO is not due to random chance (see Appendix C.3).
Future research could explore methods to automatically determine the number of nearest neighbors k. and to in- vestigate the effects of other types of density-aseending dependency and typicality.
To further validate the effectiveness and computational effi- ciency of TANGO, we also apply it to image segmentation using Berkeley Segmentation Dataset Benchmark and pro- vide corresponding running times. We transform each pixel into a 5-dimensional vector, where two coordinates corre- spond to the spatial location of the pixel and three coordi-
A Acknowledgments
We would like to thank the anonymous reviewers for their invaluable help to improve the paper. This work was sup-
9

---

TANGO: Clustering with Typicality-Awars Nonlocal Mode-Secking and Graph-Cut Optimization
ported by the National Natural Science Foundation of China under Grant numbers 61806170 70 and 62276218, and the Fun- damental Research Funds for the Central Universities under Grant numbers 2682022ZTPY082 and 2682023ZIPY027.
Cheng, D., Zhang, S., and Huang, J. Dense members of local cores-based density peaks clustering algorithm. Knowl. Based Syst., 193:105454, 2020.
Cheng, D., Zhu, Q.. Huang, J., Wu, Q., and Yang. L. Clus- tering with local density peaks-based minimum spanning tree. IEEE Trans. Knowl. Data Eng., 33(2):374-387 2021.
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 feel must be specifically highlighted here.
Cheng, D., Huang, J., Zhang, S., Zhang, X., and Luo, X. A novel approximate spectral clustering algorithm with dense cores and density peaks. IEEE Trans. Syst. Man Cybern. Syst., 52(4):2348-22 2360, 2022.
References
Cheng, D., Huang, J., Zhang, S., Xia, S., Wang, G., and Xie, J. K-means clustering with natural density peaks for discovering arbitrary-shapen clusters. IEEE Transactions on Neural Networks and Learning Systems, 2023.
Adamic, I.. A. and Huberman, B. A. Power-law distribution of the world wide web. Science, 287(5461):2115-2115,, 2000.
Altinigneli, M. C., Miklautz, L., Böhm, C., and Plant, C. Hierarchical quick shift guided recurrent clustering. In ICDE, pp. 1842-1845, 2020.
Cheng, Y. Mean shift, mode seeking, and clustering. IEEE Trans. Pattern Anal. Mach. Intell., 17(8):790-799, 1995.
Du, M., Ding, S., Xu, X., and Xue, Density peaks clustering using geodesic distances. Int. Mach. Learn Cybern., 98): 2018
Arias-Castro, E., Mason, D., and Pelletier, B. On the estima- tion of the gradient lines of a density and the consistency of the mean-shiff algorithm. J. Mach. Learn. Res., 17:
Ester, M., Kriegel, H., Sander, J., and Xu, A density- based algorithm for discovering clusters in large spatial databases with noise. In KDD-96, pp. 226-231, 1996.
43:1-43:28, 2016.
Avrachenkov, K. and Lebedev, D. Pagerank of scale-free growing networks. Internet Math., 3(2):207-231) 2007.
Fischer, B., Roth, V., and Buhmann, M. Clustering with the connectivity kernel. In NeurlPS, pp. 89-96, 2003.
Avrachenkov, K., Kadavankandy, A., and Litvak, N. Mean field analysis of personalized pagerank with implications for local graph clustering. CoRR, hts//800.076440 2018.
Guan, J., Li, S., He, X., Zhu, J., and Chen, Fast hierar- chical clustering of local density peaks via association degree transfer method. Neurocomputing, 455:401-418, 2021.
Brandes, U.. Delling, D., Gaertler, M., Görke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. On modularity clus- tering. IEEE Trans. Knowl. Data Eng.. 1022):172-188, 2008.
Guan, J., Li. S., Chen, X., He, X., and Chen, J. DEMOS: clustering by pruning a density-boostinn cluster tree of density mounts. IEEE Trans. Knowl. Data Eng., 35(10): 1081 10814-10830, 2023.
Brin, S. and Page, L. The anatomy of large-scale hyper- textual web search engine. Comput. Networks, 30(1-7): 107-117, 1998.
Hartigan, J. A. Clustering Algorithms. New York: Wiley, 1975.
Cai, D. and Chen, X. Large scale spectral clustering via landmark- sparse representation. IEEE Trans. Cy- bern., 45(8): 1669 669-6669-9000 1680, 2015.
Huang, D., Wang, C., Wu, J. Lai, J., and Kwoh, C.
Utrra-calable spectral clustering and ensemble clustering. IEEE Trans. Knowl. Data Eng.. 32(6):211--1222 2020.
Chang. H. and Yeung, D. Robust base- spectral clus- tering. Pattern Recognit, 41(1):191-203, 2008
Jarvis, R. A. and Patrick, E. A. Clustering using a similarity measure based on shared near neighbors. JEEE Trans. Computers, 22(11): 12255-11455 1973.
Chen, N., Litvak, N., and Olvera-Cravioto, M. Generalized pagerank on directed configuration networks. Random Struct. Algorithms, 51(2):237-274 2017.
Jiang, H. On the consistency of quick shift. In NeurlPS, pp. 46-55, 2017.
Chen, W., Song, Y., Bai, H., Lin, C., and Chang, E. Y. Parallel spectral clustering in distributed systems. IEEE
Jiang, H. and Kpotufe, S. Modal-set estimation with an application to clustering. In AISTATS, volume 54 of PMLR, pp. 1197-1206, 2017.
Trans. Pattern Anal. Mach. Intell., 33(3):568-55) 2011.
10

---

TANGO: Clustering with -ypac Nonlocal Mode-Secking and Graph-Cut Optimization
Jiang, H., Jang, J., and Kpotufe, S. Quickshift++: Prov- ably good initializations for sample-based mean shift. In ICML, volume 80 of PMLR, pp. 2299-2308, 2018.
Tobin, J. and Zhang, M. DCF: efficient and robust density-based clustering method. In ICDM, pp. 629-638, 2021.
Kolev, P. and Mehlhorn, K. A note on spectral clustering. In ESA, volume 57, pp. 57:1-57:14, 2016.
Tobin, J. and Zhang, M. A theoretical analysis of density peaks clustering and the component-wise peak-finding algorithm. IEEE Trans. Pattern Anal. Mach. Intell., 46 (2)11199-1120, 2024.
Lee, J. R., Gharan, S. O., and Trevisan, L. Multiway spec- tral partitioning and higher-order cheeger inequalities. ACM, 61(6))37:1137:30 2014.
Vedaldi, A. and Soatto, S. Quick shift and kernel methods for mode seeking. In ECCV, volume 5305 of Lecture Notes in Computer Science, pp. 705-718, 2008.
Little, A. V., Maggioni, M., and Murphy, J. M. Path- based spectral clustering: Guarantees, robustness outliers, and fast algorithms. J. Mach. Learn. Res., 21:6:1-6::: 2020.
Volkovich, Y. and Litvak, N. Asymptotic analysis for per- sonalized web search, Advances Applied Probability, 42(2):577-604, 2010.
Litvak, N., Scheinhardt, W. W., and Volkovich, Y. In- degree and pagerank of web pages: Why do they follow similar power laws? CoRR, abs/math/0607550, 2006.
Volkovich, Y., Litvak, N., and Donato, D. Determining fac- tors behind the pagerank log-log plot. In Algorithmms and Models for the Web-Graph 5th International Workshop. volume 4863 of Lecture Notes Computer Science, pp. 108-123. Springer, 2007.
Litvak, N., Scheinhardt, W. R. W., and Volkovich, Y. In- degree and pagerank: Why do they follow similar power laws? Internet Math., 4(2):175-198 2007.
von Luxburg, U. tutorial on spectral clustering. Stat. Comput., 17(4):395-416, 2007.
Liu, R., Wang, H., and Yu, X. Shared-nearest-nen neighbo--- based clustering by fast search and find of density peaks. Inf. Sci., 450:200-226, 2018.
Wang, Y., Wang, D., Zhou, Y., Zhang, X., and Quek, C. VDPC: variational density peak clustering algorithm. Inf. Sci. :22--655, 2023.
Long, Z., Gao, Y., Meng, H., Yao, Y., and Li, T. Clustering based on local density peaks and graph cut. Inf. Sci., 600: 263-286, 2022.
Xiang, T. and Gong, S. Spectral clustering with eigenvector selection. Pattern Recognit., 1111:11022-002, 2008.
Lotfi, A., Moradi, P., and Beigy, H. Density peaks cluster- ing based density backbone and fuzzy neighborhood. Pattern Recognit., 107:107449, 2020.
Xu, W., Liu, X., and Gong, Document clustering based on non-negative matrix factorization. In SIGIR, pp. 267-273, 2003.
Macgregor, P. Fast and simple spectral clustering in theory and practice. In NeurlPS, 2023.
Yan, D., Huang, L., and Jordan, M. I. Fast approximate spectral clustering. Proceedings of the 15th ACM SIGKDD, pp. 907-916. ACM, 2009.
Macgregor, and Sun, H. A tighter analysis of spectral clustering, and beyond. In ICML, volume 162, pp. 14717- 14742. PMLR, 2022.
Yang, Y., Xu, D., Nie, F., Yan, S., and Zhuang, Y. Image clustering using local discriminant models and global integration. IEEE Trans. Image Process, 19(1)):766- 2773, 2010.
Mizutani, Improved analysis of spectral algorithm for clustering. Optim. Lett., 1303):1333 2021.
Ng, A. Y., Jordan, M. I., and Weiss, Y. On spectral cluster- ing: Analysis and an algorithm. NeurlPS, pp. 449-856, 2001.
Zelnik-Manor, L. and Perona, P. Self-tuning spectral clus- tering. In NeurlPS, pp. 1601-1608, 2004.
Peng, R., Sun, H., and Zanetti, L. Partitioning well-clustered graphs: Spectral clustering works! SIAM J. Comput., (2):710-743,) 2017.
Rodriguez, A. and Laio, A. Clustering by fast search and find of density peaks. Science, 344(6191):149-11499) 2014.
Steinley, D. Properties of the Hubert-Arable Adjusted Rand Index. Psychological Methods, 93))3366339, 2004.

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
A. Proofs of Theorems
A.I. Proof of Theorem
Proof. It suffices to prove that / - BT is invertible for B defined by Eq. 6. To demonstrate this, we show the existence of a full-rank square matrix R such that R(I BT is also full-rank.
In fact, by sorting data points ,1,..., Zin in ascending order of density p. the rows and columns of dependency matrix B will be reordered into new matrix M. M can be equivalently obtained by performing row transformations given by full-rank square matrix R, and column transformations given by RT (i.e., M RBRT), where R = 1i each refers to an elementary row permutation matrix swapping two rows.
Tt, and
Note that each r; is an elementary row permutation matrix swapping two rows. It holds that r; r; = (swapping the same two rows of the identity matrix twice restores the identity matrix) and r; = r (swapping two rows of the identity matrix yields the same matrix swapping its corresponding two columns). thus r; r! I. and is easy verify RR = I.
Therefore, we have R(I - - RT RR R. RT I M Note that M represents the reordered dependency matrix B based on sorting data points in ascending order of density, thus M,-- = 0 since each r; cannot be its own leader, and for j > i, My 0 because p(zx)= S p(æz,) implying 24 cannot be the leader of z,. Therefore, M is an upper triangular matrix with zeros on the diagonal, and R(I RT
MT is a lower triangular matrix with ones on the diagonal, which is
obviously full-rank.
Thus, I- BT is full-rank and invertible, and the equation T BTT p has a unique solution T= =1 B p.
A.2. Proof of Theorem 3
Proof. We first construct an undirected weighted multigraph M = (V,E,W) according to Definition 5, where:
V is the set of vertices, with each vertex VÚ representing a sub-cluster Gj;
E is the set of undirected edges, where an edge e (G,, Gj, p, E if there is an edge in G connecting data points and g from two different sub-clusters G; and G, respectively;
W represents the weight of each edge in E. For any e (G,, Gj.P. E connecting data points p E G, and q E Gj. we have (ee)= C(p,g). q)-
Note that C(p, q) = 1 for any p, q from the same sub-cluster. Thus, the path-based similarity PBSim(r;; ry) between any two sub-clusters G; and G, is always determined by edges in E, and all data points from the same sub-cluster G, can be seen as whole (vertex in V)), and PBSim(ri; r3) can be calculated by conducting variant of Kruskal's 's algorithm (Fischer et al., 2003) on M: gradually adding edges from E to new graph M (V, Ø, 2) in descending order of W, and setting PBSim(ra,))) as W ((e) iff E E the first added edge that makes G; and G₃ belong to the same connected component of M'.
The above time complexity is O(EE log El + [VP?) (Fischer et al., 2003). As [ I nk and [V] < n, the overall time complexity will be no more than Onk log(nk)).
B. Tail behavior of Typicality
We can also model the typicality as a solution of distributional identity, and analyze the tail behavior of typicality from this perspective. Let us rewrite Eq. (1) as the following distributional identity:
N T D Σ B,T
(8)
where N is the in-degree of points in dependency graph (number of points that consider randomly chosen point in the dataset as leader), and it is an integer-valued random variable: 2 denotes equality in distribution; Tys are independent (since the dependency is hicrarchical) and distributed as T; Bys are independent and distributed as some random variable B: Tys, Bys, 3 N and p are independent.
12

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
As the in-degree distribution in graph nearly follows the power law behavior (Adamic & Huberman, 2000), we model the in-degree in dependency graph as N (X), where X is regularly varying with index oN > and N(x)) is the number of Poisson arrivals during the time interval [O, ar], when the arrival rate is 1. Thus, (XX is also regularly varying
asymptotically identical to X (Litvak et al., 2007):
P(N(X) > x)~xx AN (N(x)) as 50.
where (2) is slowly varying function.
As Theorem I has already shown the existence and uniqueness of the nontrivial solution of Eq. (8), we then have the following conclusion derived from (Volkovich & Litvak, 2010):
Theorem 4. If <1 and P(o z) o(P(NV > z)) as cc. then
P(T > x) ~ ON ON (N( as - 00
(10)
where CN = (B(B))ax(1 B(N)E(BeX)]-
Theorem can be proven in a similar manner as in (Volkovich & Litvak, 2010), by using Laplace-Stieltjes transform and Tauberian theorem. Since B and p only range from 1, the assumptions in Theorem are trivially satisfied in our scenario, indicating that the tail of typicality is strictly following the power law behavior with the same exponent N.
C. Detailed Experimental Results and Analyses
C.1. Hyperpamameter Settings of the Algorithms
The neighborhood size k was searched from 2 to 100 with a step size of in TANGO, LDP-SC, DEMOS, QKSPP, DPC- DBEN, and KNN-SC. Noise ratio parameters in DCDP-ASC and NDP-Kmeans were searched from to 0.2 with a step size of 0.001. The minimum proportion points that each cluster must contain in LDP-MST was fixed at 0.018 as described in the article. DCDP-ASC and DEMOS required manual selection of core points on decision graphs, and we used the best-performing selection for each parameter setting. In QKSPP, density fluctuation parameter was searched from 0 to I with a step size of 0.1 for each neighborhood size k. CPF searched for k and 3 parameters among preset combinations provided in the source code. USPEC searched for the number of representative points with step size of 100 from 100 to 1000 (or the nearest multiple of 100 below the maximum number of data points), and k was searched for all possible values under each representative point count.
C.2. Clustering on Real-world Datasets
Fig. 5 and Table 2 show the best experimental results and corresponding hyperparameter settings of TANGO and comparison algorithms on 16 real-world datasets. Specifically, LDP-MST on isolet 2344 and NDP- means on ionosphereF. did not produce results due to the insufficient number of local density peaks compared to the target number clusters. TANGO demonstrates superior performance across all datasets, by integrating local and global features of the data and employing a graph-cut scheme.
Especially on datasets such as banknote, Leukemia, and MNIST (AE), TANGO outperforms other algorithms by a significant margin in various metrics. Algorithms based on local density peaks such as LDP-SC, DCDP-ASC, LDP-MST, NDP-K Kmeans, and DEMOS performed poorly on multiple datasets, particularly DCDP- and LDP-MST, which often yielded clustering results close to random division. This demonstrates the challenge of achieving satisfactory clustering results using only local data features. USPEC demonstrates strong clustering ability, ranking second after TANGO on multiple datasets, but notably underperforms on datasets such as semeion and ver2 compared TANGO. Moreover, USPEC requires extensive parameter tuning, limiting its practical utility.
Mode-seeking algorithms like CPF and QKSPP also exhibit significantly weaker performance compared to TANGO, highlighting the effectiveness of TANGO for detecting modes through typicality and conducting graph-cut.
Fig. illustrates breaking in Censity-ascenddeee dependency identified by TANGO on the isolet1234 dataset (visualized in 2D using t-SNE for dimensionality reduction). The ability of TANGO to detect modes more effectively contributes to improved final clustering results.
13

---

TANGO: Clustering with Sypicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
Dataset
Motric
LDP-SC
DCDP-ASC
LDP-MST
NDP Kmmenss
DEMOS
CPF
QKSPP
DPC-DBFN
USPEC
KNN-SC
TANGO
ARI
52.46
79.26
81.76
85.01
wdhc
NM1
65.4
0.52
31.91
43.88
47.8
39.38
42.94
69 14
68.33
73,89
77.35
ACC
93.67
62.92
77.86
83.66
85.41
80.84
76,45
94.73
94.55
95.25
96.13
Par:
12/0.1
13/0.7
198
13/300
36
ARI
20.8
9:67
-0.19
22.9
8:03
27.09
36,62
20,07
13.37
35.76
39.4
beanEW
NMI
16.26
14.13
2,04
17.72
12.72
21.24
28.87
21.57
9.54
27.95
30.7
ACC
72.96
65.93
53.33
74.07
28.89
72.96
80.57
72.59
68.52
801
$1.48
ART
52.87
43.84
28.79
22.72
61.19
58
56.55
55.55
59.43
57.77
64.21
segmentation
ACC
72.81
$7.33
61.6
59.13
49.81
44,24
71.86
70.4
71.83
67.95
68.29
67.24
65.05
70.34
65.71
68.6
71.87
73.19
ARI
55.58
34,37
15.32
19.33
44.08
36.2
48.75
29.85
53.96
46.82
65.37
ACC
70.06
53.11
36,41
33.77
56.12
47.99
59 38
48.07
68.17
63.28
N1.42
Par.
18
0.2
20
14/00.1
13/0.0
72
19
ART
54,92
34,15
14.01
31.04
44.14
36,04
49.05
29.69
55.95
46.53
63.49
SemeionEW
NMI
67.33
47.36
43.49
46.21
63.54
52.14
64.17
42.04
67.64
60.49
71.11
ACC
74.07
55.24
37,41
51.98
55.13
48.02
$7.75
47.96
69.43
62.9
79.35
Par.
4
0.2
20
14/00.1
13/00
3/ 1000
75
21
ARi
22.92
-0.66
33.35
-3.1
28-38
33.17
25.27
vera
NMI
28.03
1,29
27.4
6.53
30.24
30.32
32.22
26.96
30.31
30.19
32.41
55.16
47.42
64,52
73.55
Par:
0
18
1./1.0
20/00
67
5/ 100
190
13
62.73
NMI
80.06
75.11
65.56
66.68
74,58
$1.92
79.73
72.78
82.22
81.29
84.65
synthetio-comrol
38.17
59.5
Par.
7
D
0.2
24
82/00.1
39 0.9
13
5/ 200
24
18
ARI
24.56
25.17
25.22
39.77
waveform
NMI
36.31
35.64
34,88
29.98
39.25
39.14
36.84
5.63
36.9
37.04
41.49
ACC
61.26
46.74
68.3
63,98
57.06
56.76
57.92
38.34
52.08
50.94
73.12
Par.
27
0.2
71
0.8
38 /0.5
11 1000
50
ARI
60.61
0.37
-1.66
0.27
23.39
25.46
58.34
53.63
60.61
61.35
69.54
CongressEW
NMI
53:11
0.31
2,15
28.31
30.98
50.71
53.11
52.65
59.8
ACC
88.97
61.61
58.62
61.61
54.48
58.16
87.82
86.67
88:97
89.2
91.72
ART
62.7
52.42
18.02
25.68
41.19
58.83
61.21
36.82
56.05
$2.08
66.33
71.52
61.54
72.41
infest
ACC
76.75
68.4
36.5
50.5
59.6
68.85
71.65
40.4
70.5
64.25
78.65
20/
40
ARI
3.96
1.82
12:43
21.82
25.16
22.88
26.29
13.62
15.79
49.15
EW
3.3
41.39
ACC
60.68
65.24
67.81
72.36
70.94
61.82
76.64
68.66
70.09
85.47
Par.
0
50/0.1
5./
37
200
15
ARI
82.72
62.85
1.27
-0.99
70.5
95.39
69.61
10.15
62.62
46.3
96.53
banknote
NMI
74.1
61.28
4.55
7.6
71.6
91,91
70.71
12.91
61.11
39.36
93.59
ACC
95.48
89.65
57.73
50.07
83.97
98.33
80.39
66-4
89.58
84.04
99.13
Par.
13
0
4
65 0..
29 0..8
83
10/ 1000
13
66
53.49
234
NMI
75.61
56.17
60.75
57.69
70.63
74.24
22.8
76.03
76.27
77.91
59.12
30.23
30.81
55.24
60.44
Far. 4
0
/
28 /0.8
23
18/ 1000
26
48
ARI
73.71
83.72
Leukemin
NMI
69.13
10.26
10.26
6.9
18.1
$4.9
59.72
26.38
63.92
63.92
73.99
56
Par.
6
0
12//0.1
12/0.
7070
10
ARI
72.83
45.37
30.75
26.33
57.15
65.15
71.08
23.01
73.8
59.66
83.4
MNIST(AEE
NMI
80.61
56
59.43
50.5
71.19
74.24
76.6
41.2
77.7
77.35
83.95
ACC
78.29
59.77
45.39
36.05
65.43
72.21
77.03
39.43
85.68
61.91
92.01
Par.
0.2
100
21/00.4
23/00.9
3/ 1000
33
ARI
68.46
50.5
48.91
46.39
37.45
62.58
71 16
39.61
69.79
50.84
82.88
77.13
78.04
77.67
UmisttAP)
ACC
73.04
55.13
56
60.35
45.57
63.13
74.96
47.65
74.43
$8.96
85.22
Table 2. Results 16 real-world datasets (%, bold represents the best for dataset, "Par." represents parameter settings).
C.3. Statistical Significance Test Results
We first employ Friedman's 's test in experimental results in terms ARI to determine if there exhibits significant diffrences among the performance all algorithms. After confirming that, the Nemenyi's 's test is conducted as post-hoc test to identify statistical significant diffrences between pairs of algorithms.
14

---

TANGO: Clustering with Typicality-Awart Nonlocal Mode-Secking and Graph-Cut Optimization
1.0
0.8
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure 6. Illustration of TANGO breaking some dependencies based on typicality for the isolet1234 dataset (visualized in 2D by t-SNE).
We have obtained Friedman Statistic 96.4 and p 2.9c 16 < 0.05 from Friedman's 's test, indicating significant differences in performance among the algorithms.
In subsequent Nemenyi's test, the critical difference threshold CD) 2.30 is calculated by CD qa indicates the number of algorithms and N the number of datasets, and fa = qu.us 1.96. The pairwise differences between the form of heatmap. Each cell in Fig. 7 represents the difference between corresponding
K(K+1)
where K
GN
algorithms are shown in Fig. pair of algorithms, and the larger (smaller) the value, the closer it is to red (blue). can be observed that the differences between TANGO and all the other algorithms not only surpass CD, but also significantly exceed the extent of differences among the other algorithms.
C.4. Image Segmentation and Running Times
Fig shows the segmentation results of different clustering methods 6 images from Berkeley Segmentation Dataset Benchmark, as well as corresponding running times (see the number above each image), where each image is dataset containing 154 401 samples (each sample refers to pixel). We use image segmentation efficiency of TANGO on larger datasets, and also as preliminary result (without fine-tuning the parameters) to demonstrate its promising application to other tasks. The performance of TANGO varied for different images, with overall better performance on several images (row I, row and row 5) but some flaws in some areas of other images. Note that in row 3, although the cloth and the hand blend for TANGO, the only method that successfully segments features in the face (mouth and eyes).
extension to test the
For TANGO, also show the running time of the similarity matrix calculation (parallelized with 20 threads) in parentheses, which is the main cost of the overall algorithm and can be easily parallelized. It has also been shown that the remaining part of TANGO is highly efficient (taking no more than 4 seconds across each image), which aligns with the theorems about efficiency.
The experimental environment is: Windows 11, Python 3.11, CPU 17-13700KF and 32GB RAM.
C.5. Effects the Hyperparameter
The proposed TANGO algorithm has only one hyperparameter, which the number of nearest neighbors k. Fig. illustrates the performance of TANGO and three other density-based algorithms on six real-worle datasets as the local
15

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
Pairwise Mean Rank Differences
LONSC 0.00
3.88
4.62
4.59
2.03
0.28
0.47
3.22
0.28
0.56
3.66
0.00
0.75
1.84
0.66
7:53
LO-MST-4.22
LOAMST
4.62
0.75
0.00
0.03
2.59
4.34
5.09
1.41
4.91
4.06
8.28
4.59
0.72
0.03
0.00
2.56
4.31
5.06
1:38
4.88
4.03
8.25
DEMOS
20/05-2.03
1.84
2.59
0.00
2.50
1.19
1.47
5.69
C9R
0.28
3.59
4.34
4.31
1.75
0.00
0.75
2.94
0.56
0.26
3.94
4.34
5.09
3.69
3.19
070:007
-3.22
0.06
1.41
1.38
1.19
2.94
3.69
0.00
3.50
2.66
6.88
0S866
0.28
4.16
4.91
4.88
2.31
0.56
0.19
3.50
0.00
0.84
3.38
1.47
2.66
1MK00
3.66
7.53
8.28
8.25
5.69
3.94
3.19
6.88
3.38
4.22
0.00
0C2P40C
TOMOD
Figure 7. Statistical significance test.
neighborhood parameter & varies. Here, the additional density fluctuation parameters of QKSPP and CPF are fixed at 0.7 and 0.5, respectively. From the figure, is observed that the performance of TANGO tends to stabilize k increases and demonstrates strong overall effectiveness, whereas DPC-DBFN, QKSPP, and CPF exhibit significant fluctuations within the same parameter range. Moreover, in practical applications, optimizing the density fluctuation parameters of QKSPP and CPF requires fine-tuning to achieve optimal clustering results, thus TANGO demonstrates advantages in hyperparameter stability and practicability.
For TANGO, the parameter affects the similarity measure. When k is small, the similarity may not be comprehensive enough to capture the complex distribution around two points, thus increasing & can lead to better performance. When k is relatively large, increasing k will introduce new shared nearest neighbors of two data points x; and æj. which, however, will have relatively small contribution to the similarity as these neighbors have large distance to both r; and 2j, and similarity values become stable. In this case, the subsequent process of the algorithm will have similar results and thus the performance will also become stable. Based on this, we recommend a larger k for datasets with complex distribution or having large number points, to more comprehensively capture the neighboring information around two points.
C.6. Ablation Study
To validate the effectiveness of the main components of TANGO, we conducted ablation experiments by testing the performance after removing certain components:
TANGO-a:
Removing the whole typicality- aware mode-seeking step and just directly applying spectral clustering based on path-based similarity (Eq. (7)) to all data points. This is to show that the typicality- mode-seeking step is essential.
TANGO-b:
Including the mode-secking step but not typicality aware, further validate the significance of typicality in mode-seeking procedure.
TANGO-e:
Removing the aggregation step on mode-centered sub-clusters. This is to validate that further aggregating the sub-clusters into the final partition with the specified number of clusters is necessary.
Fig. 10 illustrates the results of the ablation experiments. TANGO-a a suggests that identifying representative sub-clusters by mode--sekingg first can provide a more robust foundation than directly clustering all data points. TANGO-b performed better than TANGO-a but worse than the full TANGO, indicating that while the general mode-seeking process valuable,
16

---

TANGO: Clustering with Typicality-Awanl Nonlocal Mode-Secking and Graph-Cut Optimization
Original
TANGO
QKSPP
CPF
LDP-MIT
LDP SC
(1.59
23.94 (2047
(19 79g
23,03s (20 269
23.544
39
34.824
23.52
35, li
(1999)
16.6%
$4
76.
14.
Figure Results on Image Segmentation. fixed TANGO and LDP-SC; 300 and 9 0.9 Quick Shift++ and CPF: target number of clusters was fixed at 5 in TANGO, LDP-MST and LDP-SC.
incorporating typicality can further refine the sub-clusters and contribute to the final performance. From TANGO-c, we can that it essential further aggregate the sub-clusters into final partition, especially when specific number of clusters required. Without aggregation, the mode-centered sub-clusters, though potentially meaningful locally, still fail to form the globally superior partitions.
Overall, these results highlight that while typicality- aware mode-seeking establishes strong initial sub-clusters, the ag- gregation step is also crucial to achieve a high-quality final result. TANGO's effectiveness stems from this multi multi-stage process.
17

---

TANGO: Clustering with Typicality-Aware Nonlocal Mode-Secking and Graph-Cut Optimization
ARI
NMI
ACC
DPC-DBFN
QKSPP
CPF
TANGO
watc
CongresdeWW
75
heartW
78
All
50
136
Icolet1234
10
minatozer
20
MNIST(AE)
75-
12
80
100
22
40
60
80
100
20
100
20
80
100
Figure 9. The impact of the number of neighbors & the performance of TANGO and other density-based algorithms.
TANGO-a
TANGO-6
TANGO-c
TANGO
ARI
NMI
ACC
80
ingrenntation
Purmiion
Weneform
Inain12244
hearthir
U
heerther
Figure 10, Results of ablation study.
C.7. Additional Discussion
C.7.1. VALIDATION ON HIGHLY NOISY DATASETS
Fig. 11 visualizes the clustering results for TANGO on four noisy datasets with irregular shapes. The results demonstrate that TANGO exhibits high performance and robust to noise. This may be due to the mode-seeking step that can naturally
18

---

TANGO: Clustering with Typicality-Awer Aware Nonlocal Mode-Secking and Graph-Cut Optimization
Figure 11. Clustering results for TANGO four noisy synthetic datasets with irregular shapes.
Figure 12. The final dependency connections after the typicality-aware mode-seeking process dataset. Some dependency still wrongly maintained and would cause a significant decrease in performance. We used red circle to mark such dependency.
alleviate the impact of noise, and path-based spectral clustering has the advantage to capture complex data distribution.
C.7.2. LIMITATION
One example of limitation is that TANGO would perform worse when dealing with the dataset in Fig. 12, where the low density points uniformly around the high density points with extreme density discrepancy between them. In such a case, the typicality collected by low density points, would be less than that of higher density ones, making the dependency connections between them not broken (marked by red circles). Future work could explore whether other types of dependency can address this situation.
19


Reviews:
[{"review_id": "zzvZzG13lV", "reviewer": "Reviewer_viff", "summary": "The authors first propose a global perspective metric, typicality, to quantify the confidence of a point being a mode. This addresses the limitation of current mode-seeking methods, which require manually setting thresholds or human intervention to identify modes. They also design an efficient and effective algorithm to compute typicality and provide theoretical analysis. Furthermore, they introduce the TANGO clustering method, which leverages typicality to detect modes and form subclusters, and aggregates data into final clusters using an improved graph-cut technique based on path-based similarity.", "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": "Thank you so much for reviewing our paper. We answer your questions below.\n\nWeakness 1: The aggregation operation is done by considering each tree-like subcluster as a vertex in a similarity graph, where the similarity between these subclusters is determined by a path-based connectivity, and finally the spectral clustering (specifically, NCut method) is applied to aggregate these vertices into a final partition with the specified number of clusters. More formal clarification on path-based similarity between subclusters is included in the proof of Theorem 3 in the appendix. We will further clarify this operation in the revised version.\n\nWeakness 2: In our experiments, we have pre-specified the target number of clusters for spectral clustering as the number of ground-truth clusters for each dataset, and fixed the target number of clusters at $5$ on image segmentation task. It is a common topic when the target number of clusters is not pre-specified in spectral clustering, and there exist many classical methods such as Eigengap-based method, Modularity-based method and Self-Tuning Spectral Clustering method to deal with this situation. We can also integrate these methods to automatically determine the target number of clusters when it is not pre-specified.\n\nWeakness 3: We will make the differences between TANGO-a and TANGO-b clearer. In TANGO-a, we removed the whole typicality-aware mode-seeking step and just directly apply spectral clustering on all points in dataset with path-based similarity. This is to show that the typicality-aware mode-seeking step is essential. In TANGO-b, we include the mode-seeking step but not typicality-aware, to further validate the significance of typicality. We have conducted the ablation study you suggested by removing the aggregating component to validate its necessity, and observed significant performance decrements (ARI dropped from 39.4, 64.21, 65.37, 63.49, 39.77, 49.15, 59.57, 82.88 to 13.96, 39.44, 36.85, 36.42, 23.16, 6.01, 47.24, 37.19, resp.) on 8 datasets used in current ablation study. We will include this discussion in the revision.\n\nWeakness 4: Sorry for the confusion. In fact, the second \"labels\" is the name of the variable and \"clustering labels\" is a description of it. We will make this clearer.", "claims_and_evidence": "TANGO addresses the issue that current mode-seeking methods identify modes by breaking certain dependency connections but rely heavily on local data characteristics, requiring case-by-case threshold settings or human intervention to be effective for different datasets. Experimental results demonstrate the effectiveness of this approach.", "methods_and_evaluation_criteria": "TANGO introduces a novel evaluation metric for computing the typicality of a point and employs an improved spectral clustering technique to aggregate typical subclusters.", "theoretical_claims": "The paper presents an innovative density-based algorithm, but provides limited discussion on the theory.", "experimental_designs_or_analyses": "The experimental results are comprehensive.", "relation_to_broader_scientific_literature": "Based on the challenges in existing work, the authors propose a novel approach.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "Strengths:\n1. The authors integrate both local and global distribution characteristics of data and propose a novel clustering framework that fuses local and global information, introducing a new global perspective into mode-seeking methods.\n2. By introducing typicality, the authors reveal the global significance of data points under locally defined density-based dependencies and use typicality to detect modes in a fully automated manner. Additionally, they provide theoretical analysis and an efficient method for computing typicality.\n3. The authors design an improved path-based similarity method to comprehensively and effectively assess the similarity of subclusters and adopt a graph-cut method to determine the final clustering.\n\nWeaknesses:\n1. Section 4.4: The authors claim to aggregate subclusters using the graph-cut method after obtaining the modes and corresponding tree-like subclusters based on typicality. However, further clarification is needed on how the aggregation operation is performed.\n2. Section 4.4: The authors apply spectral clustering to tree-like subclusters based on path-based similarity to obtain the final clustering results. Since it is well known that spectral clustering requires a specified number of clusters, the method could potentially lead to a trivial solution where all data points are assigned to a single cluster if the number of clusters is not pre-specified. The authors should address this concern and clarify how this issue is resolved.\n3. Appendix C.6 (Ablation Study): The authors should further clarify the differences between TANGO-a and TANGO-b and whether the experimental settings are identical. Additionally, it is recommended that they include an ablation study examining the effect of using only the Typicality-Aware Mode-Seeking technique without applying the Aggregating Mode-Centered Subclusters technique.\n4. Minor textual errors: Line 350 contains a redundancy: \"clustering labels labels.\"", "other_comments_or_suggestions": "The authors are encouraged to carefully address the points raised in the Weaknesses section and provide strong responses.", "questions_for_authors": "None.", "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": "y6dTzg7tHi", "reviewer": "Reviewer_vHVP", "summary": "The paper introduces TANGO, a novel clustering algorithm that integrates typicality with graph-cut optimization. The primary contribution is the concept of typicality, a novel measure to quantify the confidence of a point being a mode for a cluster. Experimental results demonstrate the efficacy of the proposed algorithm.", "questions": "", "limitations": "", "rating": 2, "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": "Thank you so much for reviewing our paper. We answer your main concerns below.\n\nWeaknesses:\n\n1: Sorry for the confusion. $k$ in Line 331 is the number of nearest neighbors to define similarity (Line 198) and density (Line 211), which are the same $k$ that is the input parameter of TANGO. $k$ in Line 245 is just related to the summation of infinite series $T = \\sum_{k=0}^{\\infty}(B^\\intercal)^k\\rho$, and has nothing to do with the former ones. We will make these notations clearer.\n\n2: $p$ is not an input parameter but the number of modes (subclusters) automatically identified by Algorithm 2, and it is used to help the analysis of time complexity. We will make this more formal and clearer.\n\n3: In the hierarchical dependency, each data point only links to its nearest higher density neighbor, and this is an effective and efficient \"density hill-climbing\" procedure to assign data points to their corresponding modes. It has been widely used in many density-based clustering methods such as Quick Shift, DPC, Quick Shift++, DEMOS, CPF, and LDP-MST. Its consistency guarantee has also been theoretically proven by several articles such as \"On the consistency of quick shift\" and \"A theoretical analysis of density peaks clustering and the component-wise peak-finding algorithm\". Future research could also explore other types of dependency, as described in the right side of Line 435.\n\n4: In the dependency matrix $B$, each element $B_{ij}$ denotes the weight of dependency from point $x_i$ to $x_j$. The notation of $B$ is first specified in the Preliminaries section (Line 119, 151 and 152). We will also make the note on Line 265 more thorough.\n\n5 and 6: Thank you for your suggestions. We will make the definition of $C$ more formal. The detailed clarification on the connectivity formulation is included in the proof of Theorem 3 in the appendix. We will make it more thorough in the main body of the revision.\n\n7: We have provided the code and datasets in supplementary material for reviewer to validate its reproducibility. The parameter settings are also included in Table 2 in the appendix.\n\n8: Thank you for your suggestion to evaluate our algorithm on larger datasets. In fact, we have already provided experiments on image segmentation task with 154,401 samples per image (each image is a dataset and each pixel is a sample, as mentioned in the right side of Line 411). \n\n9: The performance of TANGO is indeed not perfect in the image segmentation task. However, we use this task as an extension to test the efficiency on larger datasets, and also as a preliminary result (without tuning the hyperparameters) to demonstrate its promising application for other tasks. The performance of TANGO varied for different images, with overall better performance on several images (row 1, row 2, and row 5) but some flaws in some areas of other images. Note that in row 3, although the cloth and the hand blend for TANGO, it is the only method that successfully segments features in the face (mouth and eyes).\n\n11: In fact, the contribution of typicality can be observed by comparing TANGO-b and TANGO in the ablation study. There are significant performance decrements when the typicality component was removed, such as \"semeion\" (ARI from 65.37 to 52.18), \"ionosphereEW\" (from 49.15 to 39.13), \"isolet1234\" (from 59.57 to 49.75) and \"Umist (AE)\" (from 85.22 to 78.67). Figure 6 has also shown the real-world advantages of typicality.\n\nOther Comments:\n\n1: We have already mentioned the t-SNE in Line 712 for Figure 6 and will make it clearer.\n\n3: TANGO (typicality) is to visualize the breaking of dependency via typicality, and TANGO (final) represents the final clustering results by TANGO, as mentioned in the right side of Line 330. We will make this clearer in the revision.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes, I have checked the proof of Theorem 1 and Theorem 2. The proof of Theorem 1 is confusing. The introduction of the \nR matrix is not clear, and it is unclear why R is a symmetric matrix. The definitions are not clearly explained.", "experimental_designs_or_analyses": "Yes, I have checked the whole experiment section.", "relation_to_broader_scientific_literature": "TANGO builds on density-based clustering by introducing typicality, a global confidence measure to identify cluster modes without manual tuning, unlike DPC and Quick Shift. It integrates graph-cut optimization with a path-based similarity metric, improving upon spectral clustering and density-peak methods. TANGO achieves superior clustering performance, outperforming 10 state-of-the-art methods across 16 real-world datasets.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:\n1. The method is theoretically sound and well-motivated.\n2. The remarks in between the definitions and other theories are refreshing and contribute to the explanations of these definitions/theorems.\n3. The visualizations showing which exact dependencies are broken by typicality are helpful in seeing that TANGO does actually address the drawbacks of other methods such as Quick Shift/DPC.\n4. The results presented are significant.\n\nWeakness\n1. It is unclear what the parameter k denotes in Line 331, Algorithm 3. k is used as nearest neighbours (Line 198), most similar density points (Line 211) and a number of hops parameter (Line 245).\n2. The method takes the total/desired number of modes as a parameter (p), so it cannot find modes on its own.\n3. It is explained why typicality as a measure is important but not why the proposed implementation through hierarchical dependencies is a good choice for typicality.\n4. What does the dependency matrix B mean? The note on Line 265 should be expanded.\n5. The path-based similarity between two sub-clusters G_i, G_j (Line 285) can be explained more clearly by formally defining C and explaining it to be the connectivity matrix before Definition 5.\n6. Also, a more convincing reason (than being intuitive) for the connectivity formulation being what it is (max over all paths of min C in that path) would be appreciated.\n7. Are the presented results reproducible?\n8. The results are limited to only small datasets, with the largest being MNIST (10k nodes). It would be important to know if the results scale to very large datasets such as ogbn-arxiv/etc. as well.\n9. TANGO performs qualitatively worse in the image segmentation results (Pg15). For example, in row 3, the cloth and the hand completely blend, and there are many “blemishes” in the segmentation mask compared to all the other methods. In row 4, TANGO completely fails to segment the wave.\n10. The ablation study, while present, is not extensively discussed or analyzed.\n11. In the ablation study, typicality appears to contribute only marginally to performance, with a low but noticeable uplift. How do its theoretical benefits translate into real-world advantages?", "other_comments_or_suggestions": "1.\tMention the method used to generate visualizations for the datasets (ex. UMAP/t-SNE).\n2.\tLine193, right column. The following statement is unclear and would help from rephrasing/breaking up: Therefore, we define a similarity measure based on shared nearest neighbors, where we distinguish the varying contribution to similarity of each shared neighbor to have better robustness.\n3. Clarify the difference between TANGO (typicality) and TANGO (final) in Fig.4", "questions_for_authors": "Refer to weakness", "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": "JgNIibpMVS", "reviewer": "Reviewer_FABQ", "summary": "This paper introduced the notion of \"typicality\" in density-based clustering, which measures the likelihood or confidence that a certain point should be a mode (a center) of a cluster. Existing techniques determine modes based on local measures (e.g., density of a point), but the premise of the paper is that in some situations, global features of the dataset will dictate whether a point should really be a mode. The measure of typicality introduced is defined recursively depending on a points density and the typicality of other nearby points. With this measure in hand, the paper presents TANGO, a framework for density based clustering that incorporated the typicality measure with a path-based similarity measure and spectral clustering. Experiments are run on several datasets.\n\n## Update after rebuttal\n\nThanks to the authors for the updates. I appreciate the larger experiments and the accompanying runtimes. Overall I still have a positive overall view of the paper.", "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": "Thank you so much for reviewing our paper. We answer your main concerns below.\n\nOverstatement about power law distribution: Thank you for pointing this out. We will correct it.\n\nWeakness 1: Thank you for the comment. To demonstrate scalability, we have expanded our evaluation to a substantially larger image segmentation dataset (each image is a dataset containing 154,401 samples, as mentioned in the right side of Line 411) in Appendix C.4, which has shown the promising results of TANGO on larger datasets and its efficiency. We will add more detailed analysis on the image segmentation experiments in the revision.\n\nWeakness 2: Thank you for pointing this out. Specifically, we use the spectral clustering method called Normalized Cut, which computes the Symmetric Normalized Laplacian of similarity matrix, and applies k-means++ on the rows of the matrix whose columns consist of the eigenvectors of Laplacian corresponding to the smallest $nc$ eigenvalues ($nc$ is the number of target clusters). For implementation, we used the \"SpectralClustering\" module from \"scikit-learn\".\n\nOther Comments and Weaknesses: Thank you for suggestions! We will address them in the revision.\n\nQuestion 1: For finding the optimal choice of $k$ in TANGO, we use \"gp_minimize\" from \"scikit-optimize\" to find the value $k$ that maximizes the ARI by iteratively selecting $k$ based on a Gaussian Process model and an acquisition function. In practice, we found that we can run just around 20 different values of $k$ from range 2 to 100, to find the optimal one.\n\nFor Question 2, please refer to the response to Weakness 1.", "claims_and_evidence": "The motivation for typically is well reasoned and Figure 1 is nice. \n\nThe experimental results do provide an indication that the method is outperforming other methods.\n\n\nThis is not major but there is a claim in the supplement that seems overstated. \"As the in-degree distribution in a graph always follows the power law behavior...\" This is overstated. There is evidence for power law distributions being strong but claiming that in-degree distributions \"always\" follow this distribution is not true. \n\nPost rebuttal: thanks to the authors for acknowledging this concern.", "methods_and_evaluation_criteria": "Strengths:\n\n* The definition of typicality and the overall methodological approach of TANGO seems reasonable\n* As far as evaluation, I appreciate the additional detail in the supplement on ablation study, the study on the effects of the hyperparamter k, and the image segmentation experiments. \n* The evaluation across several different datasets and multiple baselines in Figure 5 is good\n\nWeaknesses:\n\n* The datasets considered are on the smaller side\n* The paper mentions using spectral clustering, but there's more than one method that has been called spectral clustering and there can be many different variations of this. Would be better to state in more detail what is meant (e.g., computing top how many eigenvectors, and then clustering them with what? k-means? Or do you find low-conductance cut in the graph and use recursive bipartitioning?)\n\nPost-rebuttal: thanks to the authors for clarifying what approach they use.", "theoretical_claims": "I did not check the proofs of the theoretical claims, but the theoretical claims are appear to be straightforward algorithm runtime results. There are no surprises with these results or concerns about correctness.", "experimental_designs_or_analyses": "I checked the experimental results and comparisons with other methods. The baselines, dataset, and cluster quality metric (e.g., ARI, MNI< ACC) are reasonable. For the results in Figure 5, it seems a little strange to optimally tune hyperparameters. While this might help in ways with making comparisons fair (by in some sense finding the best case scenario for each approach), it feels somewhat unnatural in that in practical applications one typically cannot tune all hyperparameters in this way. So this somewhat hides one of the difficult parts of running these methods. Nevertheless, this not a major concern since at least this was done for all methods.", "relation_to_broader_scientific_literature": "Yes, the paper outlines the related work.", "essential_references_not_discussed": "None that I know of.", "other_strengths_and_weaknesses": "Strengths:\n\n* The definition of typically is reasonable and the paper does a good job motivating it. I think Figure 1 is helpful and it's placement at the front of the paper is good. \n* The fact that typically can be computed efficiently is a strength \n* The paper overall is fairly well written and organized\n\nWeaknesses:\n\n* The paper mentions \"some theoretical analysis\" as a contribution but it's vague early on. When we get to the details, the theoretical analysis seems mostly to be straightforward results about the complexity of computing typicality and runtime results. It would be better if the authors simply stated up front what \"theoretical analysis\" they provide, if it is really a big contribution. Otherwise, it feels a bit like the paper is trying to get credit for establishing theoretical results without stating what theory is provided. \n* TANGO seems to perform well in practice but the experimental results do not seem that extensive. The datasets considered are a bit on the small side. \n* The fact that all choices of k were tried makes me worry about runtime.", "other_comments_or_suggestions": "Just some minor suggestions:\n\n* Typo: \"garph\" instead of graph in at least one place\n* Figure 3 is good but far removed from Figure 1, which makes it cumbersome to page back and forth to get the point of this figure. Both Figures also have a lot of whitespace. You may be able to make Figure 3 smaller and just have it be a subfigure, and then use another subfigure to show the important part of Figure 1 again. Just a suggestion.\n* In the preliminaries, the paper mentions similarities, the density of a point, and the dependency. The meaning of these becomes clear later but is not specified at first, making this a confusing read for me. It might be good to either define these more carefully up front, or at least mention to the reader that specific measures of similarity, density, and dependency would follow later to keep them from thinking they are missing something important about the setup.", "questions_for_authors": "What are runtimes for the methods? \n\nHow expensive is it to run TANGO for so many choices of k?\n\nHow does TANGO perform on larger datasets?", "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": "JPlSMhRYeP", "reviewer": "Reviewer_4KVW", "summary": "The paper introduces TANGO  (Typicality-Aware Nonlocal Mode-Seeking and Graph-Cut Optimization), a clustering algorithm that leverages typicality, a global measure of a point's confidence to be a mode, to address the limitations of traditional mode-seeking methods that rely on local data characteristics and case-by-case threshold settings. TANGO integrates typicality-aware mode-seeking with graph-cut optimization and an improved path-based similarity to aggregate data into clusters. Experimental results on synthetic and real-world datasets demonstrate TANGO's effectiveness and superiority over state-of-the-art clustering algorithms.\n\n\n## update after rebuttal\n\nOur evaluation remains unchanged after reviewing the rebuttal; the paper deserves an Accept (4) score.", "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": "Thank you so much for reviewing our paper. We answer your main concerns below.\n\nConcern about the validation on highly noisy or imbalanced datasets: TANGO can indeed perform well on noisy and imbalanced datasets such as \"cluto-t4-8k\", \"cluto-t5-8k\", \"cluto-t8-8k\", \"cluto-t7-10k\" and \"unbalance\". This may be due to the mode-seeking step that can naturally alleviate the impact of noise, and path-based spectral clustering has the advantage to capture complex data distribution. We can include these in the experiments as an additional discussion.\n\nOther Comments:\n\n1: From the PageRank perspective, for each point $x_i$ and its nearest higher density neighbor (leader) $x_j$, $B_{ij}$ denotes the probability from $x_i$ jumping to $x_j$, and $x_i$ has the probability $(1-B_{ij})$ to stay. The right side of Figure 2 has shown how Eq. (1) reflects a density peak $x_i$ collecting typicality from all points in its \"attraction\". For example, as shown in the right side of Figure 2, when $T(x_i) = B_{1i} T(x_1) + B_{2i} T(x_2) + B_{3i} T(x_3) + \\rho_i$ from Eq. (1), and $T(x_1)=\\rho_1$, $T(x_2)=B_{42}T(x_4)+\\rho_2$, $T(x_3)=\\rho_3$, $T(x_4)=\\rho_4$, also from Eq. (1) respectively, then $T(x_i)=B_{1i} \\rho_1 + B_{2i} (B_{42}\\rho_4+\\rho_2) + B_{3i} \\rho_3 + \\rho_i$, indicating that $x_i$ collects typicality from $x_1$, $x_2$, $x_3$ and $x_4$, which are all points in its \"attraction\". We will make this clearer in the revision.\n\n2: The datasets in Table 2 is not much larger, and most of the algorithms as well as TANGO can complete their execution within a very short time (no more than 3 seconds). That’s why we have further presented the experimental results and corresponding running times on image segmentation task, which is done by clustering a dataset containing 154,401 samples (each image is a dataset and each pixel is a sample, as mentioned in the right side of Line 411), to show the efficiency on larger datasets.\n\n3: We will include these in ablation study.\n\n4: We will include an analysis in the revision. In Figure 9, as $k$ increases, the clustering performance of TANGO initially rises and then stabilizes. The parameter $k$ affects the similarity measure. When $k$ is small, the similarity may not be comprehensive enough to capture the complex distribution around two points, thus increasing $k$ can lead to better performance. When $k$ is relatively large, increasing $k$ will introduce new shared nearest neighbors of two data points $x_i$ and $x_j$, which, however, will have relatively small contribution to the similarity as these neighbors have large distance to both $x_i$ and $x_j$, and similarity values become stable. In this case, the subsequent process of the algorithm will have similar results and thus the performance will also become stable.\n\n5: One possible example of limitation is that TANGO would perform worse when dealing with the right side of the \"Compound\" dataset, where the low density points lie uniformly around the high density points with extreme density discrepancy between them. In such a case, the typicality of low density points would be less than that of higher density ones, making them become a single subcluster. Future work could explore whether other types of dependency can address this situation. We will include this discussion in the revision.\n\n6: $p$ is the number of modes (subclusters) detected by Algorithm 2. We will make this more formal and clearer.\n\n7: We will include more related works about spectral clustering in the revision. The reason why choosing spectral clustering is that it comprehensively considers a global graph-cut cost of the whole partition. On the other hand, hierarchical clustering partitions the data greedily and ignores the global impact on the whole partition at each greedy step, making it always achieve an inferior and imbalanced partition.\n\n8: Thank you for the suggestion. We tested applying SNN-based similarity and corresponding density to LDP-MST, LDP-SC and DEMOS, but observed still less performance than TANGO, even worse than their original implementations in some cases. This might be due to that these methods didn't employ typicality to construct tree-like subclusters, and their aggregation approaches for the subclusters also missed some important information that can be revealed by path-based spectral clustering technique. By the way, SNN-based approach has also been used in LDP-MST and LDP-SC by their authors, to determine the similarity between subclusters.\n\n9, 10 and 11: We will correct all the issues you have mentioned.", "claims_and_evidence": "Yes, the main claims in the paper are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria are well-suited for the problem and application at hand.", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "The paper advances clustering by introducing ​typicality, a global measure inspired by ​PageRank, to address limitations of local mode-seeking methods like ​Mean Shift and ​DPC. It integrates ​graph-cut optimization and ​path-based similarity, building on spectral clustering techniques. Theoretical analysis ensures efficiency, while experiments on diverse datasets demonstrate superiority over state-of-the-art methods, bridging local and global perspectives in clustering.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The paper’s strengths lie in its originality, introducing typicality as a global measure inspired by PageRank, and its significance, demonstrated through superior performance on diverse datasets and theoretical rigor. It is well-structured and clear, with effective illustrations. Weaknesses include sensitivity to the hyperparameter $k$, potential scalability issues with path-based similarity, and limited validation on highly noisy or imbalanced datasets.", "other_comments_or_suggestions": "1. It is necessary to further explain how Typicality adjusts contributions through density-weighted mechanisms (e.g., rank-based dependencies in Eq. (6)), distinguishing it from PageRank’s uniform jump probability assumption. Additionally, clarify how the recursive formula (Eq. (1)) reflects the \"attraction\" mechanism of density peaks.  \n2. Add runtime comparisons between TANGO and other algorithms on datasets of varying scales in Table 2 or the appendix to validate the practical efficiency of the claimed time complexity $O(nk^2d)$.  \n3. Expand Figure 10 to include experiments isolating the contributions of sub-cluster generation (Typicality module), path-based similarity (PBSim), and spectral clustering, demonstrating the necessity of their synergy.  \n4. Analyze the fluctuations in TANGO’s performance with varying $k$ values in Figure 9 \n5. Provide 1–2 cases where TANGO underperforms to discuss its limitations.  \n6. Define the variable $p$ in $O(p^3 + n)$ (whether it aligns with the $p$ in Algorithm 3).  \n7. Discuss classical spectral clustering methods in the related work section.  Discuss why spectral clustering was chosen for merging sub-clusters, unlike hierarchical clustering in other DPC-based techniques.\n8. The adoption of SNN-based density estimation indeed enhances the TANGO algorithm's performance, as it better captures local structures, delivering superior capability in generating sub-clusters. While other comparative algorithms likely rely on simpler density estimation methods, it remains to be verified whether the proposed algorithm would maintain its performance advantage, as demonstrated in the experiments, if the comparative algorithms (e.g., LDP-MST, DPC, DEMOS, LDP-SC) were to adopt equivalent density estimation techniques.\n9. Replace the equality symbol in Line 253, “$T(x_j) = T(x_j) + T(x_i) \\cdot B_{ij}$”, with the assignment operator “$T(x_j) \\leftarrow T(x_j) + T(x_i) \\cdot B_{ij}$”.  \n10. Add a footnote to the “Par.” column in Table 2 to clarify it represents “hyperparameter settings”.  \n11. Fix inconsistent citations (e.g., “Eq.2” → “Eq. (2)”).", "questions_for_authors": "no", "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: The paper proposes a global perspective metric (typicality) to quantify the confidence of a point being a mode, and designed an algorithm to compute typicality and provide theoretical analysis. Most reviewers have positive evaluation of the paper and, after reading the author's response, I believe that the downsides listed by the reviewer with the lowest score can be easily addressed. 

Based on this and the overall positive evaluation of the paper, I recommend accept.
Decision: Accept (poster)