FDC-LGL: Fast Discrete Clustering with Local Graph Learning for Large-Scale Datasets

Shenfei Pei, Ruiyu Huang, Zengwei ZhengMathematics 2026 · DOI

TL;DR

This paper introduces FDC-LGL, a novel graph-based clustering algorithm that tackles the challenges of efficiency and scalability in large datasets. By integrating local graph learning directly into the clustering objective, FDC-LGL learns adaptive graph structures and directly outputs discrete cluster assignments, outperforming existing methods in both accuracy and speed.

What Problem Does This Paper Address?

Clustering, the task of grouping similar data points, is a cornerstone of unsupervised machine learning. Graph-based clustering methods are particularly powerful because they can capture complex relationships within data by representing samples as nodes and their similarities as edges. However, existing graph clustering algorithms face several hurdles:

  • Low Graph Learning Efficiency: Learning the optimal graph structure for clustering can be computationally expensive, especially for large datasets.
  • Poor Adaptability: Many methods struggle with datasets that have a large number of samples and clusters.
  • Post-processing Accuracy Loss: Some algorithms first learn continuous representations and then discretize them into clusters, which can lead to a loss of accuracy.

These limitations hinder the application of graph clustering in real-world scenarios with massive datasets.

Methods

FDC-LGL proposes a unified framework that combines graph learning and clustering. The core innovation lies in integrating a Local Graph Learning (LGL) module into the Normalized Cut (N-Cut) objective function.

  • Normalized Cut (N-Cut): This is a standard objective function for graph partitioning that aims to minimize the total weight of edges cut between clusters while maximizing the total volume of each cluster.
  • Local Graph Learning (LGL): Instead of relying on a fixed, pre-defined graph, FDC-LGL dynamically learns an optimized similarity matrix (denoted as A). This learning process is constrained to second-order neighbors, which allows it to capture local geometric structures efficiently without the high computational cost of global graph learning. This local constraint also makes the model more robust to noise and less sensitive to hyperparameter tuning.
  • Discrete Optimization: A key feature of FDC-LGL is that it directly outputs a discrete indicator matrix representing cluster assignments. This eliminates the need for a separate post-processing step for discretization, thereby preventing potential accuracy loss and simplifying the overall pipeline.
  • Alternating Optimization: The algorithm uses an alternating optimization strategy, iteratively updating the graph structure (A) and the cluster assignments (Y) until convergence.

Datasets

The paper evaluates FDC-LGL on a diverse range of datasets:

  • Synthetic Datasets (D1-D9): Nine datasets were generated with varying numbers of samples per cluster and up to 100 clusters to test the algorithm's performance on controlled data structures.
  • Middle-Scale Real-World Datasets: Eleven datasets were used to assess robustness and generalization across different domains, including face recognition (LFW, CALFW, FaceV5, GTdb), biological data (Colon), and general-purpose datasets (Dexter, Madelon, MUCT, Umist, Yale).
  • Large-Scale Real-World Datasets: Five large-scale datasets were employed to demonstrate the algorithm's computational efficiency: CAS-PEAL-R1, CelebA, CACD, CASIA-WebFace (WebFace), and YouTube Faces Dataset (YoutubeFace).

No new benchmarks were introduced; existing public datasets were utilized.

Key Insights and Ideas

  • Local Graph Learning is Key: The paper strongly suggests that focusing graph learning on local neighborhood information (second-order neighbors) is sufficient and highly efficient for capturing relevant cluster structures, avoiding the computational burden of global approaches.
  • End-to-End Discrete Clustering: Directly optimizing for discrete cluster assignments from the start, rather than relying on post-hoc discretization, is a significant advantage for both accuracy and simplicity.
  • Robustness to Noise and Hyperparameters: The adaptive nature of the learned graph (A) makes the algorithm less susceptible to noisy data and reduces the need for extensive hyperparameter tuning, a common pain point in graph-based methods.
  • Scalability with Performance: FDC-LGL demonstrates that it's possible to achieve high clustering accuracy on large-scale datasets without sacrificing computational efficiency, a trade-off that has plagued many previous methods.

Key Results

  • Superior Clustering Quality: FDC-LGL consistently achieved the highest or near-highest scores across all datasets for key metrics: Clustering Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI). For instance, on synthetic datasets, it maintained high performance even as cluster sizes increased, unlike some baselines that degraded significantly.
  • Significant Speedup: FDC-LGL demonstrated remarkable computational efficiency, especially on large-scale datasets. It was orders of magnitude faster than other graph learning-based methods. For example, on CelebA, it was approximately 700 times faster than FastCD and finished in under 1 second, compared to over 700 seconds for FastCD.
  • Robustness: The algorithm showed strong performance across diverse real-world datasets, indicating good generalization capabilities and robustness to varying data complexities.

Limitations and Future Work

  • Computational Trade-off: While FDC-LGL is significantly faster than many graph learning methods, it is noted to be slightly slower (2-3 times) than ultra-fast baselines like CC. This is attributed to its iterative optimization process, which updates both graph structure and labels. The authors frame this as a necessary trade-off for superior performance.
  • Hyperparameter Tuning: While the paper claims reduced sensitivity to hyperparameters, the balance parameter ($\lambda$) still requires tuning, and a grid search was used for optimization in experiments.
  • Future Work: The paper doesn't explicitly detail future work directions, but the success of the local graph learning approach and discrete optimization suggests potential for extending this framework to other unsupervised learning tasks or exploring more sophisticated local neighborhood definitions.

Summary updated

Abstract

Graph-based clustering is a fundamental task in unsupervised machine learning and has been extensively applied to complex data mining scenarios, such as pattern recognition and data classification. However, most existing graph clustering algorithms still face significant challenges, including low graph learning efficiency, poor adaptability to datasets with large numbers of samples and clusters, and inevitable accuracy loss caused by post-processing steps. To effectively tackle these critical challenges and enhance clustering performance, we propose a novel Fast Discrete Clustering algorithm integrated with Local Graph Learning, namely FDC-LGL. Based on the classical normalized cut criterion, the proposed algorithm innovatively integrates a Local Graph Learning module into the clustering objective function, efficiently and reliably learning graph structures by introducing second-order neighbor constraints. It directly outputs accurate clustering results through a discrete indicator matrix, thereby eliminating the need for additional post-processing. Extensive comparative experiments conducted on synthetic datasets, medium-scale real-world datasets, and large-scale real-world datasets demonstrate that FDC-LGL is significantly superior to other state-of-the-art graph clustering algorithms in terms of key evaluation metrics, including clustering accuracy (ACC), normalized mutual information (NMI), and the adjusted rand index (ARI), as well as computational efficiency.
BibTeX
@inproceedings{pei2026fdc,
  author = {Shenfei Pei and Ruiyu Huang and Zengwei Zheng},
  title = {{FDC-LGL: Fast Discrete Clustering with Local Graph Learning for Large-Scale Datasets}},
  booktitle = {Mathematics},
  year = {2026},
  doi = {10.3390/math14040725},
}
Figure