Alternatives to the Laplacian for Scalable Spectral Clustering with Group Fairness Constraints
Recent research has focused on mitigating algorithmic bias in clustering by incorporating fairness constraints into algorithmic design. Notions such as disparate impact, community cohesion, and cost per population have been implemented to enforce equitable outcomes. Among these, group fairness (balance) ensures that each protected group is proportionally represented within every cluster. However, incorporating balance as a metric of fairness into spectral clustering algorithms has led to computational times that can be improved. This study aims to enhance the efficiency of spectral clustering algorithms by reformulating the constrained optimization problem using a new formulation derived from the Lagrangian method and the Sherman-Morrison-Woodbury (SMW) identity, resulting in the Fair-SMW algorithm. Fair-SMW employs three alternatives to the Laplacian matrix with different spectral gaps to generate multiple variations of Fair-SMW, achieving clustering solutions with comparable balance to existing algorithms while offering improved runtime performance. We present the results of Fair-SMW, evaluated using the Stochastic Block Model (SBM) to measure both runtime efficiency and balance across real-world network datasets, including LastFM, FacebookNet, Deezer, and German. We achieve an improvement in computation time that is twice as fast as the state-of-the-art, and also flexible enough to achieve twice as much balance.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification
The eigendeomposition of nearest-neighbor (NN) graph Laplacian matrices is the main computational bottleneck in spectral clustering. In this work, we introduce a highly-scalable, spectrum-preserving graph sparsification …
ClusteringOn a 'Two Truths' Phenomenon in Spectral Graph Clustering
Clustering is concerned with coherently grouping observations without any explicit concept of true groupings. Spectral graph clustering - clustering the vertices of a graph based on their spectral embedding - is commonly…
ClusteringDiffusion MRIGraph ClusteringSpectral Graph Clustering+1Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix
Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data by performing clustering on the learned optimal embedding across views. Though demonstrating promising performance in vario…
ClusteringVocal Bursts Intensity PredictionMultiple-View Spectral Clustering for Group-wise Functional Community Detection
Functional connectivity analysis yields powerful insights into our understanding of the human brain. Group-wise functional community detection aims to partition the brain into clusters, or communities, in which functiona…
ClusteringCommunity DetectionFunctional ConnectivitySpectral clustering and model reduction for weakly-connected coherent network systems
We propose a novel model-reduction methodology for large-scale dynamic networks with tightly-connected components. First, the coherent groups are identified by a spectral clustering algorithm on the graph Laplacian matri…
Clustering