{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:42:23Z","timestamp":1760146943847,"version":"build-2065373602"},"reference-count":40,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2024,12,25]],"date-time":"2024-12-25T00:00:00Z","timestamp":1735084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the National Natural Science Foundation of China","award":["62172242","62271274","2023Z213"],"award-info":[{"award-number":["62172242","62271274","2023Z213"]}]},{"name":"Ningbo Science and Technology Plan Project","award":["62172242","62271274","2023Z213"],"award-info":[{"award-number":["62172242","62271274","2023Z213"]}]},{"name":"Laboratory of Intelligent Home Appliances, College of Science and Technology, Ningbo University","award":["62172242","62271274","2023Z213"],"award-info":[{"award-number":["62172242","62271274","2023Z213"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Research on the fairness of spectral clustering has gradually increased attention. Normally, existing methods of fair spectral clustering add a fairness constraint to the original objective function so that fairness is guaranteed. However, similar to the solver of traditional spectral clustering, that of fairness spectral clustering has to relax a discrete value condition into an arbitrary one, which leads to the deterioration of both fairness and clustering quality. Moreover, the eigen-problem is inevitable in the solver, which takes O(n3) time complexity and is not available for large-scale data. In this paper, we propose a fair spectral clustering algorithm by employing the coordinate descent method to find the solution. As the relaxation of the discreteness condition is discarded, the fairness is improved. Furthermore, we refine the process of coordinate descent by avoiding redundant calculations, and as a result, the time complexity is reduced from O(n3) to O(n2). Additionally, the importance of clustering quality and fairness is symmetric; hence, we achieve a trade-off between them by adjusting the parameters. The experimental findings, obtained from both real-world and synthetic datasets, clearly illustrate that our proposal delivers superior fairness and clustering quality with the best BAL compared to other fair clustering methods. In addition, our method is more efficient than existing fair spectral clustering algorithms.<\/jats:p>","DOI":"10.3390\/sym17010012","type":"journal-article","created":{"date-parts":[[2024,12,25]],"date-time":"2024-12-25T19:19:32Z","timestamp":1735154372000},"page":"12","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fair Spectral Clustering Based on Coordinate Descent"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-3733-5107","authenticated-orcid":false,"given":"Ruixin","family":"Feng","sequence":"first","affiliation":[{"name":"College of Science and Technology, Ningbo University, Ningbo 315211, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Caiming","family":"Zhong","sequence":"additional","affiliation":[{"name":"College of Science and Technology, Ningbo University, Ningbo 315211, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tiejun","family":"Pan","sequence":"additional","affiliation":[{"name":"College of Science and Technology, Ningbo University, Ningbo 315211, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,12,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","article-title":"Data clustering: 50 years beyond K-means","volume":"31","author":"Jain","year":"2010","journal-title":"Pattern Recognit. Lett."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3593","DOI":"10.1109\/TNNLS.2020.3015795","article-title":"Fast and Effective Active Clustering Ensemble Based on Density Peak","volume":"32","author":"Shi","year":"2021","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1119","DOI":"10.1109\/TNNLS.2020.3040379","article-title":"Learnable Subspace Clustering","volume":"33","author":"Li","year":"2022","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"952","DOI":"10.1109\/TNNLS.2015.2430821","article-title":"Hybrid Sampling-Based Clustering Ensemble with Global and Local Constitutions","volume":"27","author":"Yang","year":"2016","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/TNN.2005.845141","article-title":"Survey of clustering algorithms","volume":"16","author":"Xu","year":"2005","journal-title":"IEEE Trans. Neural Netw."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","year":"2007","journal-title":"Statist. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1109\/TNNLS.2018.2861209","article-title":"Spectral Embedded Adaptive Neighbors Clustering","volume":"30","author":"Wang","year":"2019","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1418","DOI":"10.1109\/TCYB.2018.2884715","article-title":"Incomplete Multiview Spectral Clustering with Adaptive Graph Learning","volume":"50","author":"Wen","year":"2020","journal-title":"IEEE Trans. Cybern."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3494672","article-title":"A review on fairness in machine learning","volume":"55","author":"Pessach","year":"2022","journal-title":"ACM Comput. Surv."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1080\/0309877X.2021.1895093","article-title":"Validity and fairness of utilising student evaluation of teaching (SET) as a primary performance measure","volume":"46","author":"Cook","year":"2021","journal-title":"J. Furth. High. Educ."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Zhang, J.M., and Harman, M. (2021, January 22\u201330). Ignorance and Prejudice in Software Fairness. Proceedings of the 2021 IEEE\/ACM 43rd International Conference on Software Engineering (ICSE), Madrid, Spain.","DOI":"10.1109\/ICSE43902.2021.00129"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"4933","DOI":"10.1109\/TNNLS.2019.2959129","article-title":"Reducing Estimation Bias via Triplet-Average Deep Deterministic Policy Gradient","volume":"31","author":"Wu","year":"2020","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3444","DOI":"10.1109\/TNNLS.2020.3010888","article-title":"Achieving Fair Load Balancing by Invoking a Learning Automata-Based Two-Time-Scale Separation Paradigm","volume":"32","author":"Yazidi","year":"2021","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_14","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. (2017). Fair clustering through fairlets. Adv. Neural Inf. Process. Syst., 5036\u20135044."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"130698","DOI":"10.1109\/ACCESS.2021.3114099","article-title":"An overview of fairness in clustering","volume":"9","author":"Chhabra","year":"2021","journal-title":"IEEE Access"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Baumann, J., and Heitz, C. (2022, January 22\u201323). Group Fairness in Prediction-Based Decision Making: From Moral Assessment to Implementation. Proceedings of the 2022 9th Swiss Conference on Data Science (SDS), Lucerne, Switzerland.","DOI":"10.1109\/SDS54800.2022.00011"},{"key":"ref_17","unstructured":"Bera, S., Chakrabarty, D., Flores, N., and Negahbani, M. (2019). Fair algorithms for clustering. Adv. Neural Inf. Process. Syst., 4954\u20134965."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5914","DOI":"10.1109\/TII.2023.3342888","article-title":"Balanced Fair K-Means Clustering","volume":"20","author":"Pan","year":"2023","journal-title":"IEEE Trans. Ind. Informat."},{"key":"ref_19","unstructured":"Kleindessner, M., Samadi, S., Awasthi, P., and Morgenstern, J. (2019, January 10\u201315). Guarantees for spectral clustering with fairness constraints. Proceedings of theInternational Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ahmadian, S., Epasto, A., Kumar, R., and Mahdian, M. (2019, January 4\u20138). Clustering without over-representation. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA.","DOI":"10.1145\/3292500.3330987"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Li, J., Wang, Y., and Merchant, A. (2023). Spectral Normalized-Cut Graph Partitioning with Fairness Constraints. Frontiers in Artificial Intelligence and Applications, IOS Press.","DOI":"10.3233\/FAIA230416"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Ghadiri, M., Samadi, S., and Vempala, S. (2021, January 3\u201310). Socially fair k-means clustering. Proceedings of the FAccT\u2014Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual.","DOI":"10.1145\/3442188.3445906"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Abbasi, M., Bhaskara, A., and Venkatasubramanian, S. (2021, January 3\u201310). Fair clustering via equitable group representations. Proceedings of the FAccT\u2014Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual.","DOI":"10.1145\/3442188.3445913"},{"key":"ref_24","unstructured":"Dickerson, J., Esmaeili, S., Morgenstern, J.H., and Zhang, C.J. (2024). Doubly Constrained Fair Clustering. Adv. Neural Inf. Process. Syst., 13267\u201313293."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012, January 8\u201310). Fairness through awareness. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Cambridge, MA, USA.","DOI":"10.1145\/2090236.2090255"},{"key":"ref_26","unstructured":"Chakrabarti, D., Dickerson, J.P., Esmaeili, S.A., Srinivasan, A., and Tsepenekas, L. (2022, January 28\u201330). A New Notion of Individually Fair Clustering: \u03b1-Equitable k-Center. Proceedings of the International Conference on Artificial Intelligence and Statistics, Virtual."},{"key":"ref_27","unstructured":"Kleindessner, M., Awasthi, P., and Morgenstern, J. (2020). A notion of individual fairness for clustering. arXiv."},{"key":"ref_28","unstructured":"Mahabadi, S., and Vakilian, A. (2020, January 13\u201318). Individual fairness for k-clustering. Proceedings of the International Conference on Machine Learning, Virtual."},{"key":"ref_29","unstructured":"Jung, C., Kannan, S., and Lutz, N. (2019). A center in your neighborhood: Fairness in facility location. arXiv."},{"key":"ref_30","unstructured":"Brubach, B., Chakrabarti, D., Dickerson, J., Khuller, S., Srinivasan, A., and Tsepenekas, L. (2020, January 13\u201318). A pairwise fair and community-preserving approach to k-center clustering. Proceedings of the International Conference on Machine Learning, Virtual."},{"key":"ref_31","unstructured":"Wang, J., Lu, D., Davidson, I., and Bai, Z. (2023, January 25\u201327). Scalable spectral clustering with group fairness constraints. Proceedings of the International Conference on Artificial Intelligence and Statistics, Valencia, Spain."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Dhillon, I.S., Guan, Y., and Kulis, B. (2004, January 22\u201325). Kernel k-means: Spectral clustering and normalized cuts. Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and data Mining, Seattle, WA, USA.","DOI":"10.1145\/1014052.1014118"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"3233","DOI":"10.1109\/TNNLS.2018.2889976","article-title":"Parallel Coordinate Descent Newton Method for Efficient L1 -Regularized Loss Minimization","volume":"30","author":"Bian","year":"2019","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Nie, F., Liu, H., Wang, R., and Li, X. (2024). Parameter-Free Multiview K-Means Clustering with Coordinate Descent Method. IEEE Trans. Neural Netw. Learn. Syst., Early Access.","DOI":"10.1109\/TNNLS.2024.3373532"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"5571","DOI":"10.1109\/TSP.2016.2591510","article-title":"Efficient and non-convex coordinate descent for symmetric nonnegative matrix factorization","volume":"64","author":"Vandaele","year":"2016","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1109\/TPAMI.2023.3279394","article-title":"A Novel Normalized-Cut Solver With Nearest Neighbor Hierarchical Initialization","volume":"46","author":"Nie","year":"2024","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_38","first-page":"2371","article-title":"Coordinate Descent Method for k-means","volume":"44","author":"Nie","year":"2021","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_39","unstructured":"Antony, J. (2023). Design of Experiments for Engineers and Scientists, Elsevier."},{"key":"ref_40","unstructured":"Wang, B., and Davidson, I. (2019). Towards fair deep clustering with multi-state protected variables. arXiv."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/1\/12\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T16:59:54Z","timestamp":1760115594000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/17\/1\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,25]]},"references-count":40,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["sym17010012"],"URL":"https:\/\/doi.org\/10.3390\/sym17010012","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2024,12,25]]}}}