Graph Probability Aggregation Clustering
Yuxuan Yan, Na Lu, Difei Mei, Ruofan Yan, Youtian Du · 2025
Read Graph Probability Aggregation Clustering by Yuxuan Yan, Na Lu, Difei Mei, Ruofan Yan, Youtian Du (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-19897.txt.
Introduction
Yuxuan Yan and co-authors propose a clustering method that joins two classic views in 2025. Global clustering scores a whole split at once but can yield coarse groups. Local clustering leans on fine links between points but can lack coherence and speed. Their method, built on graphs, treats group membership as a probability.
The graph based fuzzy method merges a global goal with a local constraint. The full problem is cast as a multi constraint optimization task. A standard Lagrange approach solves it step by step. The blend aims to keep groups both tight up close and sound at the whole data scale.
Catalog record
| CREATOR | Yuxuan Yan, Na Lu, Difei Mei, Ruofan Yan, Youtian Du |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19897
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Probability Aggregation Clustering Yuxuan Yan, Na Lu, Difei Mei, Ruofan Yan, Youtian Du Abstract Traditional clustering methods typically focus on either cluster-wise global clustering or point-wise local clustering to reveal the intrinsic structures in unlabeled data. Global clustering optimizes an objective function to explore the relationships between clusters, but this approach may inevitably lead to coarse partition. In contrast, local clustering heuristically groups data based on detailed point relationships, but it tends to be less coherence and efficient. To bridge the gap between these two concepts and utilize the strengths of both, we propose Graph Probability Aggregation Clustering (GPAC), a graph-based fuzzy clustering algorithm. GPAC unifies the global clustering objective function with a local clustering constraint. The entire GPAC framework is formulated as a multi-constrained optimization problem, which can be solved using the Lagrangian method. Through the optimization process, the probability of a sample belonging to a specific cluster is iteratively calculated by aggregating information from neighboring samples within the graph. We incorporate a hard assignment variable into the objective function to further improve the convergence and stability of optimization. Furthermore, to efficiently handle large-scale datasets, we introduce an acceleration program that reduces the computational complexity from quadratic to linear, ensuring scalability. Extensive experiments conducted on synthetic, real-world, and deep learning datasets demonstrate that GPAC not only exceeds existing state-of-the-art methods in clustering performance but also excels in computational efficiency, making it a powerful tool for complex clustering challenges. I Introduction Clustering algorithms [ 1 , 2 , 3 ] , as a fundamental technique in data mining, play a crucial role in uncovering hidden patterns within unlabeled data. It helps identify intrinsic structures of unlabeled data, which can significantly improve our understanding and analysis of the underlying relationships between data points [ 4 ] . Clustering algorithms maximize similarity within data clusters and minimize similarity between data clusters [ 5 ] . Over the years, numerous clustering methods have been developed, with applications spanning a wide range of domains, such as image recognition [ 6 , 7 ] , representation learning [ 8 ] , and social networks [ 9 ] . These diverse applications highlight the versatility and importance of clustering in both theoretical and practical data science. Conventional clustering methods are widely favored by researchers because of their strong interpretability and stable optimization properties. From a data processing perspective, clustering algorithms can be categorized into two main approaches: local clustering and global clustering. Local clustering methods focus on point-wise data relationships, performing clustering through message passing between nodes. Hierarchical clustering [ 10 ] is the most classical method, which groups data sequentially based on a hierarchy of points. For example, the First Integer Neighbor Clustering Hierarchy (FINCH) [ 11 ] algorithm merges nearest neighbors to perform agglomerative hierarchical clustering. Additionally, local clustering methods often utilize graph data for information transfer. Affinity Propagation (AP) [ 12 ] , for instance, updates responsibility and availability messages between data points to progressively determine the clustering structure of unlabeled data. These methods typically rely on heuristic algorithms rather than explicit objective functions to frame the clustering problem, emphasizing the detailed relationships between instances to achieve finer data division. However, practical challenges persist, including theoretical simplicity, the need to tune additional hyperparameters [ 13 , 14 ] , and higher computational costs [ 10 , 12 ] . In contrast to local clustering, global clustering methods aim to find a cluster-wise partition that optimizes the specific objective function. K-means and its variants [ 15 , 16 , 17 ] are among the most commonly used clustering algorithms, partitioning datasets based on cluster centers. Their widespread use is due to their theoretical simplicity and robustness [ 18 , 19 ] . However, global clustering methods have notable drawbacks, including sensitivity to initialization [ 20 ] , reduced effectiveness in high-dimensional spaces [ 21 , 22 ] , inconsistent performance [ 23 , 24 ] , and limited precision in data division. Fuzzy mathematics [ 25 ] provides a new perspective for clustering. Fuzzy clustering [ 26 ] , introduces the concept of fuzzy sets [ 27 ] , allowing data samples to belong to multiple clusters simultaneously. Fuzzy C-Means (FCM) [ 28 ] is the most prominent fuzzy clustering algorithm, which iteratively updates the cluster centers and the membership matrix to achieve clustering. Subsequently, several fuzzy clustering algorithms [ 29 , 30 , 31 , 32 , 33 ] have been derived from modifications of FCM. Knowledge-induced Multiple Kernel Fuzzy Clustering (KMKFC) [ 34 ] integrates the relative density-based knowledge extraction method and multiple kernel mechanism into FCM to better extract knowledge, improve adaptability, and guide the cluster centers. However, these methods remain rooted in incremental improvements of classical algorithms, which inherently limit their performance due to the constraints of the foundational algorithms. To this end, researchers have explored new frameworks [ 35 , 36 , 22 ] for fuzzy clustering. One such approach is Fast Fuzzy Clustering based on Anchor Graph (FFCAG) [ 22 ] , which combines anchor-based similarity graph construction with fuzzy membership matrix learning to mitigate the high computational cost and sensitivity to noise that is common in traditional fuzzy clustering methods. Similarly, Graph-based Soft-Balanced Fuzzy Clustering (GBFC) [ 37 ] uses the membership matrix in the Spectral Clustering (SC) framework and introduces a balancing constraint to regularize the clustering results. However, despite these advancements, these approaches still face limitations related to model theory, parameter selection, and overall algorithm performance. In this paper, we introduce a novel graph-based fuzzy clustering algorithm, Graph Probability Aggregation Clustering (GPAC), which offers a new perspective of clustering by integrating graph theory with fuzzy techniques. As illustrated in Fig. 1 , GPAC utilizes an objective function for global clustering throughout the entire dataset, while incorporating a constraint to perform local clustering within neighborhoods. By combining the strengths of graph and fuzzy clustering, GPAC provides greater flexibility and robustness for the clustering process and hyperparameter tuning. The global clustering is driven by the objective function composed of two key components: a clustering term and a self-constrained term. The clustering term is designed to promote coherence of the clustering predictions across the global data distribution. It encourages the model to assign similar samples to the same cluster. The self-constrained term, acting as a regularization term, on the other hand, addresses the issue of cluster size imbalance. It penalizes solutions where a disproportionate number of samples are assigned to a small subset of clusters, thus preventing trivial solutions brought by the clustering term. We demonstrate that our objective function effectively leverages both similarities and dissimilarities among samples, showcasing its ability to capture the intrinsic structure of the data. Additionally, we prove that a special case of our objective function is mathematically equivalent to minimizing the sum of cosine distances within clusters. For local clustering, a local consistency constraint is employed to learn the local structural relationships within the data. This constraint preserves the intricate relationships among the neighboring nodes in the graph, facilitating more accurate and meaningful clustering results. By incorporating both objective function and constraint, graph-based knowledge is aggregated by a fuzzy way to effectively capture both local and global structural relationships within the dataset.