Source-linked AI summary
Guarantees for Spectral Clustering with Fairness Constraints
Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, Jamie Morgenstern
TL;DR
The paper asks how to incorporate proportional demographic representation into spectral clustering without necessarily sacrificing clustering quality. It develops constrained normalized and unnormalized spectral-clustering variants and analyzes them theoretically and empirically. The methods recover fair clusterings with high probability in a stochastic block model and often produce fairer real-data clusterings at minimal additional objective cost.
Problem
Spectral clustering lacks an established treatment of proportional demographic representation, motivating study of fairness constraints and their objective-value cost on graph data.
Method
The paper incorporates proportional-representation constraints into normalized and unnormalized spectral clustering and analyzes the methods on a fair-clustering stochastic block model.
Results
The algorithms recover the fair clustering with high probability in the stochastic block model and often find fairer real-data clusterings with objective values very close to standard spectral clustering.
Takeaways & Limitations
In some real-data scenarios, higher demographic proportionality and clustering objective value need not be at odds.
Takeaways & Limitations
The proposed algorithms do not guarantee exact fairness, and the price of exact fairness in spectral clustering remains an open direction.
Abstract
from arXiv · showhide
Given the widespread popularity of spectral clustering (SC) for partitioning graph data, we study a version of constrained SC in which we try to incorporate the fairness notion proposed by Chierichetti et al. (2017). According to this notion, a clustering is fair if every demographic group is approximately proportionally represented in each cluster. To this end, we develop variants of both normalized and unnormalized constrained SC and show that they help find fairer clusterings on both synthetic and real data. We also provide a rigorous theoretical analysis of our algorithms on a natural variant of the stochastic block model, where $h$ groups have strong inter-group connectivity, but also exhibit a "natural" clustering structure which is fair. We prove that our algorithms can recover this fair clustering with high probability.
1. Introduction
The paper extends fairness-aware clustering to spectral clustering, seeking proportional demographic representation while preserving clustering quality when a good fair clustering exists. It develops constrained normalized and unnormalized methods, proves recovery guarantees in a stochastic block model, and reports fairer real-data clusterings often at minimal objective cost.
- Motivation: Chierichetti et al. define fair clustering as proportional representation of demographic groups in every cluster.Prior work studied this notion for k-center, k-median, and k-means objectives.
- Contributions: The paper incorporates proportional-representation constraints into both normalized and unnormalized spectral clustering.The approach is analogous to constrained spectral clustering with must-link constraints.
- Contributions: Unlike methods that always enforce fairness regardless of objective cost, these algorithms guide spectral clustering toward a good fair clustering when one exists.The methods do not guarantee that their output is fair in every instance.
- Theoretical analysis: The algorithms recover the fair clustering with high probability in a stochastic block model with strong inter-group connectivity and a natural fair clustering structure.The paper presents this as a rigorous analysis of constrained spectral clustering.
- Empirical findings: Real-data experiments find fairer clusterings than standard spectral clustering, often with objective values very close to the standard method.This suggests that, in some scenarios, higher proportionality need not substantially increase the clustering objective.
2. Spectral Clustering
Unnormalized spectral clustering relaxes the discrete RatioCut minimization into an orthogonality-constrained eigenvector problem, then uses k-means on the resulting embedding rows to infer clusters.
- Objective: Unnormalized spectral clustering partitions a weighted graph into k clusters by minimizing the RatioCut objective.The graph uses positive edge weights to encode similarity, with zero weight for nonedges.
- Objective: A clustering is encoded by a discrete matrix H, making RatioCut equal to Tr(H^T L H), where L is the unnormalized graph Laplacian.The discrete optimization can therefore be written as minimizing this trace subject to H having the clustering form.
- Relaxation: Spectral clustering relaxes the discrete constraint by requiring only H^T H = I_k.This produces an orthogonality-constrained trace minimization problem.
- Relaxation: The relaxed optimum uses orthonormal eigenvectors corresponding to the k smallest eigenvalues of L.These eigenvectors form the columns of H.
- Rounding: The algorithm applies k-means to the rows of H to infer a clustering, but the resulting RatioCut value is not generally guaranteed to be near optimal.The relaxation does not preserve a one-to-one correspondence between solutions and discrete clusterings.
3. Adding Fairness Constraints
The paper encodes proportional demographic representation as linear constraints within spectral clustering, then solves constrained eigenvalue problems for fair unnormalized and normalized variants.
- Fairness notion: Fairness requires each cluster to represent every demographic group in approximately the same proportions as the full data set.The balance of a cluster increases as its group representation becomes more proportional.
- Constraint formulation: Group-membership vectors and centered group indicators encode proportionality constraints as linear constraints on the spectral embedding H.The constraint matrix F uses columns f^(s) − (|V_s|/n)·1_n for h−1 groups.
- Constrained spectral clustering: The proposed approach replaces the unconstrained spectral relaxation with a fairness-constrained optimization problem before applying k-means to the resulting embedding.This parallels constrained spectral-clustering methods that impose linear constraints for must-link relationships.
- Algorithm: The constrained problem is solved by projecting into the nullspace of F^T, computing the k smallest eigenvectors of Z^T LZ, and setting H = ZY.The formulation requires k ≤ n−h+1 so that a feasible solution exists.
- Variants and complexity: The resulting procedures are presented as Algorithms 2 and 3 for unnormalized and normalized spectral clustering, respectively.Their stated complexity is O(n^3) time and O(n^2) space, matching standard spectral clustering's worst-case complexity when the number of clusters is arbitrary.
- Design choice: Running standard spectral clustering separately on each demographic group is not a sufficient alternative for deriving a fair clustering.The paper addresses this idea separately and reports that it does not work.
4. Analysis on Variant of the Stochastic Block Model
The paper analyzes fair spectral clustering on a stochastic block model with multiple meaningful clusterings, proving high-probability recovery under stated conditions and observing broader empirical success.
- Model: The model contains h demographic groups and k ground-truth clusters in which every group has the same proportion as in the full data set.
- Model: The graph distinguishes pairs by cluster and group membership through connection probabilities a, b, c, and d, with a > b > c > d.
- Model: The fair cluster partition can have a larger RatioCut than the group partition, because within-group cross-cluster connectivity is stronger than within-cluster cross-group connectivity.
- Theoretical guarantees: The theorem gives separate misclassification bounds for unnormalized and normalized constrained SC, involving constants, approximation factor, connection probabilities, cluster count, and ln n.
- Scope and limitations: The authors suspect some theorem conditions and k-dependent error bounds are stronger or looser than necessary, while experiments find success beyond the theorem’s balance and cluster-size assumptions.
- Theoretical guarantees: The normalized and unnormalized algorithms are weakly consistent under the stated assumptions, with the misclassified fraction tending to zero as n grows.
- Proof strategy: The proof combines eigenvalue and eigenvector analysis, Davis–Kahan perturbation bounds, and results on k-means applied to perturbed eigenvectors.
5. Related Work
Related work situates the paper among constrained spectral clustering, stochastic block model consistency, and fairness methods for unsupervised learning.
- Constrained spectral clustering: Prior constrained spectral clustering incorporates must-link or cannot-link knowledge through linear constraints in RatioCut or NCut optimization problems.
- Stochastic block models: Earlier SBM analyses establish consistency under eigenvalue or degree assumptions, whereas this paper states assumptions and guarantees directly using connection probabilities a, b, c, and d.
- Stochastic block models: The authors identify their work as providing consistency results for constrained spectral clustering methods that were not previously available to their knowledge.
- Fairness: Fair clustering research builds on proportional representation across demographic groups and includes approximation algorithms for k-center, k-median, and k-means.
- Fairness: Existing fair unsupervised learning methods, like this paper, assume the demographic group of each data point is known.
6. Experiments
The experiments compare standard and fairness-constrained spectral clustering on synthetic stochastic block models and real networks, measuring error, demographic balance, and clustering objectives. Fair variants recover fair clusterings under several synthetic conditions and improve balance on real data, usually with limited objective-cost changes.
- Synthetic Data: Synthetic experiments measure misclassification error relative to the fair ground-truth clustering and examine performance as n, k, and perturbation levels vary.The experiments compare standard unnormalized and normalized spectral clustering with Algorithms 2 and 3.
- Synthetic Data: When cluster sizes differ and Assumption (10) is slightly violated, both fair algorithms still recover the fair ground-truth clustering; Algorithm 3 reaches almost zero error at n = 1000.Under strong violations, Algorithm 2 fails while Algorithm 3 still succeeds.
- Synthetic Data: For fixed n, error increases monotonically with k for both fair algorithms, with a stronger increase for Algorithm 2 and a rate dependent on F.The experiments could not establish whether the theoretical error guarantees are tight in k.
- Real Data: On high-school friendship networks, fair variants improve balance by 10% / 15% while almost not changing RatioCut or NCut.Figure 5 evaluates balance on the left axis and RatioCut or NCut on the right axis.
- Real Data: On DRUGNET, fair variants improve balance by 5% / 18% / 86% / 167% on average over k, while the three-group case incurs a moderate RatioCut or NCut increase.The network is evaluated with two demographic groups and, separately, three ethnic groups.
7. Discussion
The paper concludes that fairness constraints can be incorporated into spectral clustering with theoretical recovery guarantees and empirical improvements in demographic proportionality. It identifies exact fairness costs and robustness characterization as directions for future work.
- Discussion: The algorithms recover fair ground-truth clusterings with high probability in a natural stochastic block model.The paper presents this as part of its rigorous theoretical analysis.
- Discussion: Real-data experiments provide evidence that higher demographic proportionality is often achievable at minimal additional cost in the clustering objective.The conclusion describes this as strong empirical evidence.
- Discussion: Future work should characterize the price of satisfying fairness constraints exactly and the robustness of the algorithms to perturbations in group assignments.The paper notes that exact fairness and rigorous robustness characterization remain open directions.
A. Adding Fairness Constraints to Normalized Spectral Clustering
The normalized spectral clustering variant imposes fairness as linear constraints, reduces the constrained problem to a projected generalized eigenproblem, and applies k-means to the resulting embedding.
- Formulation: Normalized spectral clustering minimizes Tr(H^T L H) subject to H^T D H = I_k, then relaxes the discrete clustering representation.The normalized objective is the NCut objective.
- Fairness Constraint: Fairness is encoded by requiring F^T H = 0, where F contains centered group-membership vectors for h − 1 groups.The centered vectors are f^(s) − (|V_s|/n) · 1_n.
- Reduction: Substituting H = ZY, with Z spanning the nullspace of F^T, converts the constrained problem into a reduced normalized spectral objective.The reduced constraint is Y^T Z^T D ZY = I_k.
- Eigenproblem: Factoring Z^T D Z = Q^2 and substituting Y = Q^−1X yields an orthogonally constrained eigenproblem involving Q^−1 Z^T L Z Q^−1.A solution uses eigenvectors corresponding to the k smallest eigenvalues.
B. Computational Complexity of our Algorithms
The fairness-constrained algorithms retain the standard spectral clustering worst-case asymptotic complexity when the number of clusters is arbitrary.
- Computational Complexity: Both fairness-constrained Algorithms 2 and 3 use O(n^3) time and O(n^2) space, matching standard spectral clustering’s worst-case complexity.The stated costs include the additional nullspace-basis and matrix computations.
C. Proof of Theorem 1
The proof analyzes the expected and observed matrices underlying the fair spectral-clustering algorithms, then establishes eigenstructure and high-probability concentration needed for recovery.
- Proof structure: The proof proceeds through eigenanalysis, deviation bounds, and recovery arguments for the fair spectral-clustering algorithms.The first part studies W and Z^T LZ; subsequent parts study observed-versus-expected deviations and derive Theorem 1.
- Eigenvalues and eigenvectors: Under a > b > c > d ≥ 0, the shifted expected adjacency matrix has rank kh or k + h − 1 when a − c = b − d.The rank characterization follows from the number and structure of its nonzero eigenvalues.
- Eigenvalues and eigenvectors: The leading eigenvalue is strictly larger than the repeated positive eigenvalues associated with the group and cluster structure.The proof establishes λ1 > λ2 = . . . = λh > 0 and λ1 > λh+1 = . . . = λh+k−1 > 0.
- Eigenvalues and eigenvectors: The relevant positive eigenvalues exceed the absolute values of the remaining eigenvalues, creating the separation used in the spectral analysis.Both repeated positive-eigenvalue families dominate the magnitudes of the lower eigenvalues.
Part 3: Proving Theorem 1 for Algorithm 2 (unnormalized SC with fairness constraints)
For unnormalized fair spectral clustering, the proof compares empirical and expected eigenspaces, aligns them by an orthogonal transformation, and transfers row separation into a misclassification guarantee.
- Embedding: Algorithm 2 clusters rows of ZY, where Y contains eigenvectors for the k smallest eigenvalues of Z^T LZ.The proof compares this empirical embedding with the analogous expected embedding.
- Eigenvalue separation: The k smallest expected eigenvalues are λ1 − λ1, λ1 − λh+1, …, λ1 − λh+k−1, and the next eigenvalue determines the eigengap.The eigengap is the minimum of the two possible gaps involving λh+k and λ1.
- Perturbation analysis: Davis–Kahan and perturbation bounds show that the empirical eigenspace is close to the expected eigenspace up to an orthogonal transformation.The argument combines Weyl’s perturbation theorem with the sinΘ theorem.
- Row geometry: In the ideal embedding, rows are identical within clusters and have distance 2k/n across different clusters.Orthogonal transformation preserves these row-equality and row-distance properties.
- Recovery guarantee: A (1 + M)-approximation for k-means yields a bound on the number of misclassified vertices when applied to the embedded rows.The bound is expressed using the cluster sizes and the embedding perturbation.
Part 4: Proving Theorem 1 for Algorithm 3 (normalized SC with fairness constraints)
For normalized fair spectral clustering, the proof establishes positive definiteness, rescales the transformed Laplacian, controls eigenspace perturbations, and applies the same row-separation argument to recover clusters.
- Well-definedness: The matrix Z^T DZ is positive definite, so Algorithm 3 is well-defined.The proof obtains this from concentration and the relation between the expected and observed degree matrices.
- Normalized embedding: Algorithm 3 applies k-means to rows of ZQ^-1X, where X contains eigenvectors of Q^-1Z^T LZQ^-1 for its k smallest eigenvalues.Q is the positive definite square root of Z^T DZ.
- Normalization: Because Q^-1Z^T LZQ^-1 = (λ1 − a)^-1 Z^T LZ, normalization rescales eigenvalues without changing eigenvectors.The square root satisfies Q = √(λ1 − a) I under the analyzed model.
- Perturbation analysis: The normalized proof bounds perturbations of the empirical embedding relative to an orthogonally transformed expected embedding.The argument controls the relevant matrix differences before invoking the k-means misclassification result.
- Row geometry: In the ideal normalized embedding, within-cluster rows coincide and distinct-cluster rows have squared separation 2k/[n(λ1 − a)].Right multiplication by an orthogonal matrix preserves these relationships.
- Recovery guarantee: The proof concludes by applying the k-means misclassification bound under the concentration conditions of Theorem 1.The final parameter choices ensure the intermediate bounds imply the theorem’s stated conditions.
D. Why Running Standard Spectral Clustering on Each Group Vs Separately is not a Good Idea
Running standard spectral clustering separately within demographic groups can destroy the cross-group structure needed to recover a fair global clustering, even when standard global SC succeeds.
- Naive strategy: Separately clustering each group and merging the resulting kh clusters is proposed as a way to seek high-balance k-clusterings.The approach runs standard spectral clustering with k clusters on each of h groups.
- Counterexample: In the 12-vertex example, global standard SC recovers a minimum-RatioCut clustering that is perfectly fair and also recovered by the fair algorithms.Both clusters have balance 1.
- Counterexample: Within-group SC splits V2 differently because the fair two-way partition is not its minimum-RatioCut solution.Thus V2 is not returned as the desired pair of clusters by standard SC on its induced subgraph.
- Failure of merging: No merger of the separately obtained V1 and V2 clusters can reconstruct the fair ground-truth partition.The failure follows from the incorrect within-group clustering of V2.
- Structural explanation: The failure is structural and extends beyond the displayed graph to a random-graph model with large within-cluster and V2 connectivity parameter a and small parameter b.The model assigns edge probabilities according to the intersections among C1, C2, and V2.