Accelerating Spectral Clustering under Fairness Constraints
Authors: Francesco Tonin
Alex Lambert
Johan Suykens
Volkan Cevher
Venue: ICML 2025 poster (2025)
Keywords: fairness
spectral clustering
difference of convex
scalability
Primary area: social_aspects->fairness
TL;DR: We improve the computation time for fair spectral clustering thanks to a new difference-of-convex formulation.

Abstract: Fairness of decision-making algorithms is an increasingly important issue. In this paper, we focus on spectral clustering with group fairness constraints, where every demographic group is represented in each cluster proportionally as in the general population. We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework. To this end, we introduce a novel variable augmentation strategy and employ an alternating direction method of multipliers type of algorithm adapted to DC problems. We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work, which required a computationally expensive eigendecomposition. Numerical experiments
demonstrate the effectiveness of our approach on both synthetic and real-world benchmarks, showing significant speedups in computation time over prior art, especially as the problem size grows. This work thus represents a considerable step forward towards the adoption of fair clustering in real-world applications.

Accelerating Spectral Clustering under Fairness Constraints
Francesco Tonin Alex Lambert
Johan A.K. Suykens?
Volkan Cevher'
Abstract
Agarwal al., 2019; Aghaei et al., 2019; Amini et al., 2019; Davidson & Ravi, 2020; Celis et al., 2018; Singh al., 2023; Ali et al., 2023).
Fairesss of maiiinnn-maingggggo algorithms is an in- creasingly important issue. In this paper, we focus spectral clustering with group fairnsss con- straints, where every demographic group is rep- resented in each cluster proportionally as in the general population. We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the differ- ence of convex functions (DC) framework. To this end, we introduce novel variable augmenta- tion strategy and employ an alternating direction method of multipliers type of algorithm adapted to DC problems. We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared prior work, which required computationally expen- sive eigendecomposition. Numerical experiments demonstrate the effectiveness of our approach on both synthetic and real-world benchmarks, show- ing significant speedups in computation time over prior art, especially as the problem size grows. This work thus represents a considerable step for- ward towards the adoption of fair clustering in real-world applications.
In clustering research, Chierichetti et al. (2017) introduced demographic fairness by imposing fairness constraints to ensure balanced representation across protected groups in clusters. Initially applied two groups in Chierichetti et al. (2017), this concept expanded to multiple groups (Rös- ner & Schmidt, 2018; Bera et al., 2019a) and primarily explored in prototype-based clustering (Chierichetti et al., 2017:
& Wang, 2013; Bera et al., 2019a). Kleindessner et al. (2019) adapted this notion of fairness to spectral clustering (Shi & Malik, 2000; Von Luxburg, 2007) and known as fair spectral clustering (Fair SC), Al- though recent advances (Wang et al., 2023) have sped up the computation of Fair SC, the reliance on the computationally expensive eigendecomposition of the fairness-constrained graph Laplacian still limits the application of Fair SC to real-world problems.
From an optimization standpoint, SC can be cast as a trace maximization problem with orthonormality constraints (Bach & Jordan, 2003), falling into the differences of convex functions (DC) framework. This problem class has spurred substantial interest (Tao et al., 1986; Le Thi & Pham Dinh, 2018), and efficient DC-based algorithms have been de- veloped for various ML tasks including feature selection (Le Thi et al., 2015), reinforcement learning (Piot et al., 2014) and (kernel) PCA (Beck Teboulle, 2021; Tonin et al., 2023). However, these algorithms do not extend di- rectly Fair SC due to their lack of consideration for the faimess constraints, the integration of which within the DC framework remains unexplored in the existing literature.
1. Introduction
Algorithmic Dacksion-maakig systems leveraging machine learning (ML) are increasingly being used in critical do- mains such as healthcare, social policy, and education, rais- ing concerns about the potential for these algorithms to exhibit unfair behavior towards certain demographic groups (Hardt et al., 2016; Buolamwini & Gebru, 2018; Choulde- chova Roth, 2020). In response to these concerns, the field of fair ML has proposed mathematical fairness for- mulations for various ML tasks, e.g., (Dwork et al., 2012: Zafar al., 2017; Samadi et al., 2018; Donini et al., 2018;
In this work, we cast the Fair SC problem into the DC framework and develop an efficient alternating direction becthod-of-mulipphe (ADMM)-type algorithm through a suitable variable augmentation, achieving higher compu- tational efficiency over existing algorithms (Kleindessner et al., 2019; Wang et al., 2023). Our specific contributions can be summarized as follows:
'LIONS, EPFL, Switzerland SEAAIUS KU Leu- ven. Belgium. Correspondence to: Francesco Tonin <francesco.tom @eptl.ch>.
Novel Algorithu Design: We develop a new efficient optimization method for Fair SC by casting the prob- lem the DC framework and by designing novel
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Accelerating Spectral Clustering under Fairness Constraints
variable augmentation suitable for efficient DC opti-
C1
C2
mization within ADMM type of algorithm.
Efficient Solution via DC: We show that each associ- ated ADMM subproblem can be solved efficiently. In particular, our approach can exploit fast gradient-band based algorithms for the DC framework. This results in better computational efficiency of our method, avoiding the expensive eigendecomposition of modified Laplacian required by exisiting algorithms.
3: X
X:t 361
C₁
Empirical Validation:
Through numerical experiments, we demonstrate the effectiveness of our approach both synthetic and real-world benchmarks, showing significant speedups in computation time, especially with larger sample size and number of clusters.
C2
Figure I: Illustrative example of fair clustering. Red and blue colors indicate h = 2 different demographic groups. Clustering with k = 2 of the left-hand side data can result in two possible partitionings: the top clustering C1, C2 or the bottom clustering C₁, C%2, where balance(C(1.2)) and (Cl.,ce(C(1.2))
This paper is structured follows. Section 2 reviews the group fairness constraints for spectral clustering and the existing algorithms for Fair SC. Section 3 presents our new algorithm for Fair SC. The numerical experiments in Sec- tion 4 show the advantage of our method in computational efficiency over existing algorithms on multiple benchmarks. Proofs are deferred to the Appendix.
in fair clustering such that each cluster contains the same number of elements from each group V..
2. Problem Formulation
Definition 2.1 (Balance (Chierichetti et al., 2017)). For clustering of type (1), define the balance of the cluster C/ as
Given a symmetric real matrix M E TR X(M) E IR" is the vector of its eigenvalues ordered decreas- ingly. Ig is the identity matrix of size $ X s. |1:1Ip denotes the Frobenius norm. For a convex set C, <c(-) its indicator function: on C and +oc otherwise. The Fenchel-Legendre transform of function f is f*, For an integer s > [s] denotes the set {1.....
Notation:
IV, n nn e,
balance(C)) min
[0, 1].
(3)
VV nC
An example of fair clustering is shown in Figure 1, with ground-truth labels shown for visualization purposes. In group-level fairess (Chierichetti et al., 2017), the higher the balance of each cluster, the fairer the clustering. A perfectly balanced clustering means that objects from all groups are presented proportionately in each cluster. The following definition due to Kleindessner et al. (2019) gives the corresponding group fairness condition.
2.1. Group-fair clustering
Given a set of data points, the goal of clustering is to par- tition the dataset into disjoint subsets such that data points in the same subset are more similar to each other than to those in the other subsets. Formally, let D = {x; E IR Ji=1 be a dataset n data points. Clustering partitions D into k clusters:
in
Definition 2.2 (Group fairness). A clustering such as (1) is group fair with respect to a group partition (2) if the proportion of each group in all clusters is the same as in D, i.e. for s [h] and 7 [k:].
C1 U...UUC
(1)
such that the resulting clustering has high intra-cluster sim- ilarity and low inter-cluster similarity. Clustering can be encoded in clustering indicator matrix Q E RRak where qu : 1 if z E Cj, and 0 otherwise, for i [n]] and ( [k]. We now review the notion of group fairness in clustering. Suppose we are also given h groups partitioning the dataset D (e.g., based on sensitive data such as nationality or cen- sus):
V. n Gil GG
V.
(4)
Groups can be encoded in group indicator matrix G Ruxh with gis := 1 if 2; E V., and 0 otherwise, for [n], E [M]. The fairness condition (4) can be represented in matrix form using the indicator matrices Q and G. This is done in Wang et al. (2023) by considering the matrices
D V.U....U
(2)
where V. Vn = for i + j. Chierichetti et al. (2017): Bera (2019a) proposed the following notion of balance
A = G Q and = (G' 1n) (QT TT) The entries of
A and B are asl VV, G and bat [V&] |Gt| for
2

---

Accelerating Spectral Clustering under Fairness Constraints
E [b]] and / [k]. The group-fairness condition
condition (4) is then
with modified affinity Mz = Z MZ E (()-))x(--))
equivalent to n A A= B,
By Bach & Jordan (2003), the solution Y is given by the lt largest eigenvectors of Mz by the eigenvalue problem
Fo Q=000.
-
(5)
where Fb = 1--G-112 -n= gunh and =
س- R². n
MzY = YA.
(8)
where A = diag(An-n--s An--n-:.... An-h) is the diagonal matrix of eigenvalues of Mz. Finally, the solution to the original problem (6) is recovered as H- D 1-1/22y.
2.2. Fair spectral clustering
Given the dataset D, in this work we consider a positive definite kernel K : Rd x Rd + R and define the affin- ity matrix K E R2xn as Kij gree matrix D E Ruxx as Dai وー= Ki (Alzate & Suykens, 2008). The spectral clustering solution is obtained by solving an eigenvalue problem of size n X n and cor- responds to the eigenvectors H E Rn*k associated with the & largest eigenvalues of the normalized affinity matrix M := 1-11011/K00 DD-1/ 1/2, Typically as in normalized SC, the clustering indicators are then obtained by applying k-means to the rows of D D-
This algorithm is denoted o-FSC as it is the original algo- rithm for Fair SC. o-FSC requires two major computational steps. The first one is the explicit computation of the null space of Fx This can be done by the SVD of F, which has time complexity (nh²). The second major computational step is the eigenvalue decomposition of Mz. This step has complexity O( h)*). Due to the cubic complexity of eigendecomposition, the o-FSC algorithm is only suitable for small n and is not scalable to real-world datasets.
my) and the de-
2.2.2. S-FSC ALGORITIIM
Remark 2.3. Spectral clustering with kernel as affinity func- tion is particularly useful in clustering applications where data matrix. Our algorithm
In Wang et al. (2023), the authors proposed a more efficient version of the o-FSC algorithm. Wang et al. (2023) rewrite the eigenvalue problem (8) terms of a new matrix s.t. they can efficiently apply the the implicitly restarted Amoldi method (Sorensen, 1992) for computing eigenpairs. First note that (8) can be rewritten by left-multiplication with Z as
the input data is given can also be applied in the standard SC setting (Shi & Ma- lik, 2000; Von Luxburg, 2007) where the input is given as a graph with adjacency matrix W, by considering .M- = D-1/2WD D-1/2, We can regularize the problem by working with p.s.d. M == M + (1 + In for small >> 0. In fact, it holds that (M) 2 -1, vi = -.....;1. nh, the eigenval- ues of the normalized Laplacian L - D-1 LD-1/2 1/2, with L L= D- - W, lie in [0, 2]. This regularization does not alter the solution space as it only shifts the eigenvalues. This is a well-studied regularization technique that is widely used, e.g., in kernel methods (Bishop & Nasrabadi, 2006).
(ZZJ MZZ ) ZY = ZYA,
(9)
as Z = In-h. This leads to the following projected eigenvalue problem AY' = Y'A, where A = PMP e R=*" with P = zz and Y' = ZY. It is possible to show that an eigenvalue/eigeeveeoor pair (2, 1/) of A, with x being one of its largest h eigenvalues, is also an eigenvalue/cigenveeoor pair of Mz with y = Z ZTy'. There- fore, one can solve Problem (8) by finding the smallest eigenvectors of (9). Note that, for the sake of avoiding the computation of Z, Wang et al. (2023) use the rows of H' = D-1/yy' instead of H = D D-1/2zy' in the k- means step, with Y' being the top i eigenvectors of A. The complexity of s-FSC for each eigensolver iteration is O(n² nh2 + nkk²), with constants depending on the num- ber of required restarts of the Arnoldi method; in general, this depends on the initial vector and properties of M, in particular the distribution of its eigenvalues (Stewart, 2001). While the s-FSC algorithm improves efficiency over o-FSC, its scalability remains limited by the eigendecomposition routine, which in practice exhibits significant computational cost.
The group fairness constraint was incorporated into the framework in Kleindessner et al. (2019) by adding the linear constraint (5) to the spectral clustering problem:
max HER s.t.
Tr(H MH)
HTH H = Ik FTH=0
(6)
with normalization F = D-1/2 as reviewed in Ap-
pendix D.2. We now review existing algorithms for (6).
2.2.1. O-FSC ALGORITHM
The nullspace-based algorithm for solving (6) proposed in Kleindessner et al. (2019) is as follows. Since the columns of H live in the null space of FT, we can write H- = ZY, for some Y E ((=-A where Z E p=x(n-A) is an or- thonormal basis of null(FT) Consequently, the optimiza- tion problem (6) is equivalent to the following trace maxi- mization where the linear constraints are removed:
3. Algorithm
In this section, we design an ADMM-like algorithm for Fair SC. This is done by reformulating the problem within the dif- ference of convex functions (DC) framework and devising a
max Tr TY TYTTM2Y M2Y) s.t. YTY = Ik. (7) (
3

---

Accelerating Spectral Clustering under Fairness Constraints
new variable augmentation allowing efficient dualization of the ADMM subproblem. Our specific construction leads to efficient gradient-based algorithms avoiding the expensive aigendecomposition routines on the n x n matrices.
ADMM framework. The ADMM approach in the context of difference of convex functions has been investigated in, e.g., (Sun et al., 2018a; Chuang al., 2022; Tu et al., 2020). However, naively applying the existing ADMM algorithms to the Fair SC problem results in intermediate arg min prob- lems that are not easy to solve, involving large matrix in- versions. To arrive at efficient solutions, we introduce a novel variable augmentation scheme, where the linear con- straint couples the ADMM variable Y with M instead of directly with H. This specific design choice is crucial for decomposing the problem into a subproblem w.r.t. H that can be efficiently tackled through dualization within the DC framework. Moreover, as we will demonstrate empir- ically, enforcing fairness on H instead of H effectively promotes the same group balance. Let us then write (10) with the proposed variable augmentation as a composite function with linear constraints:
Difference of convex functionn. To leverage the effi- ciency of DC optimization, we recast Problem 6 as the minimization of difference of convex functions. However, directly applying DC optimization to Problem 6 would ne- cessitate computing M1/2, computationally demanding operation akin to solving the original problem. To circum- vent this challenge, we formulate our DC problem in terms of M instead of M. This choice allows us to bypass the computation of M2/2 without sacrificing solution quality, as we will demonstrate empirically that optimizing with M yields solutions exhibiting comparable fairness those obtained with M. Note that in practice we never compute 22 explicitly, we only need to compute matrix-vects products. Formally, we define f,g, h: Ban* + R {+0) as follows:
min H,Y ER ((H)) s.t. MH = (11)
We form the augmented Lagrangian
((H) = |
9 ( 1.s (ss((H) (H);
L(H,Y, g(H) + M(Y) - f(MH)
MH) = 40) (F H).
+ (P, YY
(12)
Remark 3.1. Here, the orthogonality constraints corre- spond to belonging the Stiefel manifold Sh {H E Ra*k| H H- }. While the constraint H E S is not itself convex, it can be relaxed into convex constraint by considering the convex hull of the Stiefel manifold as the solutions necessarily lie on the boundary (Uschmajew, 2010, Lemma 2.7).
+ MM Y
where P are the Lagrange multipliers and a is the penalty parameter. The ADMM algorithm corresponds to the fol- lowing iterations:
H(++1) arg min (1,,
(13)
HERaxK
Using this notation, our proposed DC formulation reads
((+1)) arg min ((H(++)) Y, y())
(14)
YERuxk
g + MH) (MMH) HER
min
(10)
p(++)) = p(() + a -
(15)
Note that Problem 10 corresponds to solving a modified (6) with 2 instead of M in the cost function. Notice that, with- out the fairness constraints, (10) reduces to finding the top k eigenvectors of 2 (Bach& & Jordan, 2003). While efficient optimization algorithms with DC for the simpler variance- maximization case without faimess constraints (i.e., h 0) have been studied in previous work (e.g., in the PCA litera- ture (Thiao et al., 2010; Beck & Teboulle, 2021; Tonin et al., 2023)), the main challenge here is to develop an efficient algorithm that can handle the additional complexity intro- duced by the fairness constraints. In this work, we derive dual framework that is amenable to fast gradient-basee based optimization of (10), as opposed to the eigendecomposi- tion routines used in o-FSC (Kleindessnerr et al., 2019) and s-FSC (Wang et al., 2023).
Our algorithm is summarized in Algorithm 1. The penalty (++1) is updated according to the standard rule suggested in (Boyd et al., 201 1) and detailed in Appendix B. We now analyze the two subproblems separately.
3.1. Subproblem with respect to H
Our approach to solving Problem (13) consists in the fol- lowing steps. First, we remark that it can be written as a difference of convex functions. Such problems have been widely studied in the literature (Tao et al., 1986), and in our case dualization is possible and strong duality holds. Next, we solve the dual problem using iterative techniques, as we can provide an explicit form for the corresponding gradient using standard properties of the Fenchel-Legende conjugates. Finally, we can get back the primal solution that is exactly the solution to Problem (13) by computing the SVD of well-chosen matrix.
Novel variable augmentation. To address the Fair SC problem, we propose to first cast the problem into an
4

---

Accelerating Spectral Clustering under Fairness Constraints
Algorithm 1 Proposed ADMM-type method for Fair SC
is computationally cheap in the context of relatively small number of clusters. Overall, the computational complexity per iteration associated to the computation of dual solu- tion V is bounded by the sum of: (i) the computation of VT M2V that scales as (kk)² (ii) the SVD of V M2V that costs (Ak")) (iii) the matrix products for Vg" (MV) in O(kk² + k2) (iv) the computation of VΦ that scales as ((nk), In the experiments, we solve Problem (16) using a fast L-BFGS optimization algorithm. Note that M is not explicitly computed one can use the associative property to perform consecutive multiplications, e.g. V M2V can be computed as (VT M)(M)..
Input: affinity matrix K
E R=x"; group matrix F E
Raxh; & E N; (0)) >
1: Compute normalized affinity matrix
M
D- D-1/2KD-1 1/2 1/2
2: Initialization 00 = 0, y 0. p()) =0
3: La(H, P) = g(H) + +h() - ((
+ +) 1 - |
4: 00.1.. - do
5:
H(++1) = arg minH Loto (H, y(i), p(i)
y(+1)= = arg miny Lato (H(t)), ,Y,)
6:
7: p(+1)) p()) (MHH))) V(it)))
8: Update a (1+11 according to (19)
Computing the primal solution. Once the dual solution V is computed, one can recover the corresponding primal solution H(++) by
9:
end for
10: Apply k-means clustering to the rows of H'
D D-
(V. MH) s.t. H = lR- HER
max
(17)
Proposition 3.2. Let Φ: X + f(x) (P.X) -
This step can be performed by 11 LR computing the SVD of the matrix V M LSR with complexity O(kk²).
2 ||| - -Y1]² and assume that a 1. Then Problem (13) can be written as a DC. Moreover, it holds that
arg min (,,,,(),l))))) arg min g(H) (MHH) HERaxx
3.2. Subproblem with respect to Y
HEROXK
We now turn to solving Problem (14), i.e.
and the dual problem reads
arg min a VERUXE
|
r 1| (pl0)
inf VERWxk x (*(V) g (MV).
(16)
2
(18)
s.t. Y 0.
Finally, strong duality holds.
The linear constraints be removed by using suitable parameterization Y QZ where Q E (n-X) is the ma- trix of an orthonormal basis of the nullspace of F that can be obtained from the SVD of F similarly to the technique employed in Section 2.2.1. Then Z E (n is the new variable, resulting the problem in Z without linear con- straints. The problem is solved by nullifying the gradient in closed-form solution, i.e., 2 Q M MH(++)) 2Q p())
The condition a < 1 is not a limiting assumption as the ADMM is known converge for small values (Nocedal & Wright, 1999). To solve (16), we assume that M is full rank, which typically happens when the affinity matrix K comes from positive definite kernels associated with infinite dimensional feature spaces, such as the Gaussian kernel, and the data dataset does not contain any duplicates.
and (i-1) = Q2. The computational complexity in this step is dominated by matrix-vector products in Okm?²) and by the SVD of F in O(h??). We note that this SVD is in practice fast as h is typically very small.
This assumption is needed to guarantee the existence of the gradients of the terms of Problem (16) that are detailed in the following proposition.
Proposition 3.3. Let V (V + p(t) a)))).
Raxk, and A: V Then (V(V) = ||v|
Complexity analysis. The complete ADMM-like algo- rithm is summarized in Algorithm 1. The runtime is dom- inated by matrix multiplication applying M to an n x k matrix (i.e.. the variable and its dual V), with complexity On? k),, where typically i < n. The improvement is there- fore in the efficiency of the core operations. In fact, while for an n matrix both matrix multiplication and matrix eigendecomposition have the same ((n²) complexity, the former is much more efficient in practice. The proposed efficient gradient- based algorithm avoids the eigendecompo- sition routines and is shown to achieve significantly higher computational efficiency in practice in Section 4.
[[(()) VII t ||A(V) g" (MV) = TT (VV M2V)
20 ( and
Gradient- based techniques for the dual problem. Solv- ing Problem (16) can be done by using iterative gradient- based techniques, as all the quantities involved are easy to compute. Indeed, o² is a quadratic form whose gradient is trivial and, for g" (MV), we exploit the fact that its gradient is known in closed-fone form (Tonin et al., 2023) and expressed through the SVD of the matrix V M2V E IR txk; this SVD
5

---

Accelerating Spectral Clustering under Fairness Constraints
Table I: m-SBM. Runtime and balance for m-SBM bench- mark with l- = 50, h = 5 and varying n.
o-FSC
S-FSC
Ours
10
12
Metric
o-FSC
s-FSC
Ours
Time (s)
96.39
75.61
3.29
5000
Balance
1.00
1.00
1.00
-5
Time (s)
235.62
88.99
5.29
7500
Balance
1.0
1.0
1.0
C-O, G-O C-O, G-1 e C-1, G-O C-1,
Time (s)
495.70
107.94
9.19
10000
Balance
1.0
1.0
1.0
Fair clustering of Elliptical dataset. The clus- tering label is represented by different colors, and sensitive attributes by shapes. The legend "C-i, G-j" for Cluster-i, Group-j. These plots show that our method produces as- signments comparable to exact algorithms (o-FSC, s-FSC), Critically, we achieve this with reduced computations.
Figure 2:
Convergence analysis. While ADMM convergence is well-established for convex problems (Eckstein & Bertsekas, 1992; Boyd et al., 2011) 1),, obtaining convergence results for nonconvex problems is an active area of research. Existing results rely on problem-specffic assumptions such as in the nonconvex consensus setting (Hong et al., 2016), or require structural properties such as bounded Hessians (Li & Pong, 2015) or continuity (Wang et al., 2019) preventing their direct application to Problem 6. Other works (Sun al., 2018b; Pham et al., 2024) exploit the difference of convex functions structure but are limited to differentiable convex functions h with Lipschitz continuous gradient. Finally, another line of works rely on making additional assump- tions on the sequence of iterates (Shen et al., 2014; Jiang et al., 2014; Magnusson et al., 2016), yielding weaker re- sults. In particular, applying Proposition 3 from Magnusson et al. (2016) to (11), we characterize the convergence of the ADMM algorithm as specified in the following proposition, whose formal details can be found in Appendix D.I.
Table 2: Real-world data. Runtime for multiple Fair SC real-world problems with k = 25.
Time (s)
Dataset
n
o-FSC
s-FSC
Ours
LastFMNet
5576
103.82
19.08
4.59
Thyroid Census
7200
279.03
30.49
7.38
32561
136.60
15.78
4area
35385
166.92
25.85
(Kleindessner et al., 2019) and its state-of-the-art scalable extension (s-FSC) (Wang et al., 2023). We apply the pro- posed algorithm to problems of different sizes, quantify the fairness of the computed clusters, and compare solutions with exact methods. We also study the effect of the number of clusters & on runtime and conduct a sensitivity analysis on the penalty parameter a. Experiments are implemented in Python 3.10 on machine with 3.6GHz Intel i7-9700K processor and 64GB RAM.
Proposition 3.4. Provided that the sequence of dual vari- ables p() generated by Algorithm I converges, any limit point (H*, (H)) of the primal sequence (H(6), (() satisfies the first-order conditions.
The proof of Proposition 3.4 relics on (i) Problem (II) hav- ing finitely defined closed constraints sets, (ii) local solu- tions for subproblems, and (iii) limit solutions enjoying regular set of constraint gradient vectors. Beyond theoreti- cal guarantees, ADMM algorithms have been successfully applied to a wide array of nonconvex problems in machine learning, e.g., (Xu et al., 2012; Sun & Fevotte, 2014). Em- pirical evidence on a wide range of tasks for both synthetic and real-world datasets presented the next section demon- strates the strong practical performances of Algorithm
Datasets. We consider the following synthetic datasets: m- SBM, RandLaplace, and Elliptical. The m-SBM benchmark (Kleindessner et al., 2019) is modification of the stochas- tic block model (Holland et al., 1983) to take fairness into account. has ground-truth perfectly fair clustering, where the n nodes are partitioned in l groups and assigned to a fixed fair clustering with & clusters. In the experiments, we vary n and set k 50, h and edge connectivity prob- ability ioog " )1/10_ The RandLaplace dataset is graph induced by random n x symmetric adjacency matrix W with each node randomly assigned to one of h = 2 groups. Elliptical has k = 2 clusters and h = 2 groups, as defined in (Feng et al., 2024). We consider the following rorl-world datasets, summarized in Table 10 in Appendix. LastFMNet
4. Numerical Experiments
Through numerical evaluations on both synthetic and real- world datasets, we show the efficiency of the proposed ADMM-type algorithm with DC dualization for Fair SC. We compare with the original Fair SC algorithm (o-FSC)
6

---

Accelerating Spectral Clustering under Fairness Constraints
(Rozemberezki & Sarkar, 2020) (n 5576, h 6) is the graph of follower relationship between users of the Last.fm website; the groups correspond to different nationalities. Thyroid (Quinlan, 1987) (n = 7200, h 3) contains 21 attributes of patients divided into three groups: not hypothy- roid, hyperfunction, and subnormal functioning. Census (Kohavi et al., 1996) (n = 32561, = 7) contains attributes from 1994 US census data, with 7 groups repre- senting demographic categories. 4area (Ahmadian et al., 2019) (n 35385, h 4) represents researchers from four areas of computer science: data mining, machine learning, databases, and information retrieval. The RBF kernel is used for Thyroid, Census, and 4area, while the remaining datasets are given as graphs through Remark 2.3.
60
0.2
Balance
40
Time
0.1
20
k
k
s-FSC
Ours
LastFMNet
200
0.6
Time (8)
Balance
0.5
100
Metrics The average balance, as introduced in
Chierichetti et al. (2017), is used to measure how fair clustering is; it is the average over all clusters of (3). It is value in [0, 1], where value of corresponds to perfectly fair clustering, i.e., (4) holds. Note that our approach follows the established line of works on fair spectral clustering, which do not provide guarantees in the general case on the balance of the clustering given by (6), as discussed Kleindessner et al. (2019), similarly to how the relaxed spectral clustering only approximates the optimal normalized cut solution (Shi & Malik, 2000). All reported running times averaged over 5 trials. Additional results and detailed setups are provided in Appendix A and B.
| I 50
60
k:
s-FSC
Ours
(b) 4area
Figure 3: Runtime and fairness across k. Fair SC on real- word datasets (a) LastFMNet, (b) 4area with s-FSC (Wang et al., 2023) (blue) and the proposed algorithm (orange). In each dataset, the left plot shows the runtime comparison and the right plot shows the average balance, for multiple num- bers k of clusters. Left plots show that method is con- sistently faster than s-FSC, with even better efficiency gains as k increases. Right plots compare the balance achieved by both methods, showing our method mantains the fairness in terms of balance of the exact algorithm.
4.1. Experimental results
Synthetic benchmarks. In this experiment, we compute the Fair SC solution on the m-SBM benchmark (Klein- dessner et al., 2019) to evaluate the performance and ef- ficiency of our proposed method. The results are presented in Table 1. The experiment is carried out for sample sizes (5000, 7500, 10000). Our method consistently outper- forms both o-FSC and S-FSC in runtime. For instance, at = 10000, method is approximately 54 times faster than o-FSC and 12 times faster than S-FSC. In terms of average balance, recall that Problem 6 is able to recover the ground-truth fair clustering in m-SBM (Kleindessner et al., 2019). This is confirmed in the experiments, where the balance is consistently 1.0 for all three methods across sam- ple sizes, demonstrating that all methods equally respect the faimess constraints. We also consider the Elliptical dataset (Feng al., 2024) (k = h 2) and visualize the found clustering in Figure 2, showing that our method achieves comparable labels to the exact algorithms.
Fair SC problem with k = 25 clusters. As shown in Table 2, our method consistently outperforms both o-FSC and s-FSC in terms runtime across all datasets. For instance, on the LastFMNet dataset with n 5576, our method shows a runtime of 4.59 seconds, which is significantly faster than both o-FSC (103.82 seconds) and s-FSC (19.08 seconds). Similar trends are observed for the other datasets, with our method achieving even higher speedups for larger datasets. For example, on the 4area dataset with n = 35385, our method takes 25.85 seconds compared to 166.92 seconds by s-FSC. Overall, o-FSC cannot complete the task within 500 seconds for the larger datasets (Census and 4area), and S-FSC takes considerably longer than our method.
Figure 3 compares runtime and average balance of the com- puted clustering by our method and s-FSC across multiple numbers of clusters h E 50] on LastFMNet and 4area datasets. terms of runtime, we observe that our method scales better in l than s-FSC, especially Mest. This
Real-world data. compare the performance of our proposed method with o- FSC (Kleindessner et al., 2019) and s-FSC (Wang et al., 2023). The runtime of the algorithms was measured for
We now test on real-world datasets to
7

---

Accelerating Spectral Clustering under Fairness Constraints
" 5000
7500
10000
400
400
400
Time (s)
200
200
200
10
k 25
k:
k 10
k:
50
25
k: 50
Ours
s-FSC
o-FSC
Figure 4: Scalability. Runtime (in seconds) of our algorithm, s-FSC, and o-FSC RandLaplace at multiple sample sizes (5000, 7500, 10000) with h = 5 and k (10, 25, 50).
Table 3: Comparison of clustering cost, balance, and time speedup exact algorithm.
Table 4: Comparison with methods FFSC and UFSC using different objectives for fair spectral clustering. Time is in seconds, "Cost" is the clustering cost, "Fairn." indicates the fairness constraint | H and "Ortho." indicates T H 71(² Our method is
Dataset
Method
Clustering
Balance
Time
s-FSC
1.057 .663
0.0105
4. 4.16x
the orthogonality constraint || significantly faster than both methods, while consistently achieving better fairness and orthogonality than FFSC.
LastFM
Ours
1.0861.074 074
0.0093.1.0113
1x
S-FSC
0.353 us00
0.0029 0000s
4.13
Thyroid
Ours
0.353 01.8
0.0030
1
Dataset
Mathod
Time
Cost (
Balance
Faim.
Ortho. (L)
Census
S-FSC
134.539 667
0.0004
x
FFSC
33.74
1067.9 99
0,2701
4,032
3.91E-00
Ours
1.30973314.9771
0.0004
1x
LasFM
UFSC
16.36
1.11:244
4.13E-13
Ours
4.59
1.09
0.0093
0.000014
1,368-11
S-FSC
235.268 6.44
0.3884
6.45 x
FFSC
56.11
3080.85
0.0170
15.79
1,026-01
4area
Ours
242.000
0.3823+.0200
1x
Thyroid
0.0026
1,25E-24
3.77E-10
Ours
7.38
0.35
0.0030
0.0000001
2.18E-11
FFSC
193,92
146669.39
0.0051
9.47
2.14E+00
Censas
UTSC
timed
Qurs
15.78
130.97
0.0004
0.000012
1.12
trend shows that more iterations are needed for convergence of the additional eigenvectors in the eigendecomposition routines, while our method involves the computation of the SVD of small & & matrix; in the context of a small number of clusters, this SVD is computationally cheap. The plots for each dataset show that method offers efficient solution for Fair SC on multiple real-world datasets while achieving comparable average balance than the com- peting exact algorithm.
2.661:000
4aren
UFSC
rimed out 0,3823
Ours
25.85
242.00
0.000001
4.22E-10
between 8x faster than SOTA (Wang et al., 2023).
Scalability in LandLaplace We use the Randlaplace dataset to illustrate the scalability of our method. Figure 4 presents the runtime our method, s-FSC, and o-FSC for different sample sizes n ranging from 5000 to 10000 with varying numbers of clusters requires less time than both compared methods across all clusters and sample sizes. These findings suggest that method better scales with increasing sample size and cluster numbers, demonstrating the practicality of our method for real-world problems of varying sizes.
compare our method with the exact approach using eigendecomposition (s-FSC) Table 3, where we report the clustering cost, standard metric evaluate spectral clustering (Shi & Malik, 2000), i.e., Tr(HT M HH) where ft is computed from the 0-1 clustering indicator matrix obtained by applying k-means on H. The results show that our method consistently achieves comparable clustering costs and balance to the exact eigendecomposition approach across all datasets fraction the runtime, with speedups
(10, 25, 50). Our method
8

---

Accelerating Spectral Clustering under Fairness Constraints
Table 5: Sensitivity analysis of penalty parameter a.
ing the fairness constraints as M H instead of H. Empiri- cal evaluations show significant speedups with comparable clustering and fairness metrics to exact algorithms. Fu- ture works include investigating model- based formulations within kernel-based settings and applying our framework to more general constrained spectral clustering by accom- modating other constraints whenever the DC formulation is maintained. For example, it might be possible to extend our framework to constrained spectral clustering, e.g., lin- ear constraints for must-link and cannot-link constraints, by considering modified indicator function ht).), accomodat- ing other constraints or fairness metrics as DC functions. ADMM could then be applied with appropriate modifica- tions to the subproblem w.r.t. Y.
Iter.
Cost
Bal.
Faim. Constr.
Ortho. Constr.
0.005
4.0
25.
1.0
7.822 0012e-081s.e
1.05e 14
0.01
7.
25.992.0m oo
1.0g.
8.866-00811 mooss mooos
1.07e-14a6.60 14
0.05
6.61.40
26.091.001
1.0..
2.30e-07ar.2z-0
1.02e- 1iee144ste 16
0.1
m.
26.061.00
1.0g.0
1.27e 0615.9407
9.92e 15 is
Comparative analysis with other spectral methods. We compare with different formulations of spectral clustering with fairness constraints that deviate from (6) for compre- hensive analysis. In particular, FFSC (Feng et al., 2024) and UFSC (Zhang& & Wang, 2024) do not adopt the prob- lem of (Kleindessner et al., 2019). FFSC instead introduces fairness by changing the SC objective with a different regu- larization term. UFSC learns an induced fairer graph where eigendecomposition is applied. Comparative results are shown in Table 4. Our method is 12 faster and achieves significantly better spectral clustering cost. FFSC's modi- fied objective shows a different balance-clusterine trade-off with higher balance but worse clustering and group faimess. Note the two different measures of fairness, where balance promotes same number of individuals in each cluster (3), and group fairness ensures proportional representation (4). Overall, these methods' solutions are far from the exact one of (6) leading to higher spectral cost, potential instability when orthogonality is not enforced, and longer runtimes.
Impact Statement
A faster fair spectral clustering algorithm can have a signif- icantly positive societal impact as it can facilitate a more widespread adoption of fairer clusterings in applications with larger real-word datasets. The approach presented in this paper aims at advancing the field of Machine Learning. No other potential societal consequences of our work are deemed necessary to specifically highlight here.
Acknowledgements
LIONS-EPFL. was supported by Hasler Foundation Pro- gram: Hasler Responsible AI (project number 21043). LIONS-EPFL was sponsored by the ARO under Grant Number 1911NF-2441-00488 LIONS-EPFL was supported by the Swiss National Science Foundation (SNSF) under grant number 200021_205011 ESAT-STADIUS was su- ported by the Flemish Government (AI Research Program); IBOF//3/064; KU Leuven C1 project C14/24/103.
Sensitivity analysis of a. We conduct a sensitivity analy- sis of our algorithm w.r.t. the ADMM penalty parameter a. Table 5 presents key indicators obtained on the RandLaplace dataset with n 1000, k 25 over 5 runs, detailing how varying the initial a influences the number of ADMM it- erations, the final objective cost, the attained balance, and the final feasibility of the orthogonality and linear fairnsss constraints. All tested a values lead to solutions with similar final cost and constraint satisfaction, as well as perfect bal- ance (1.0) for the studied dataset. This observation suggests that our algorithm is robust to changes in a. As a increases, the faster convergence due to higher penalty on primal feasi- bility comes at the cost of slightly worse fairesss constraint satisfaction. Given this slight decrease with larger a, in our experiments we opt for a smaller ( = 0.005 and update it as detailed in Appendix B.
References
Agarwal, A., Dudík, M., and Wu, Z. S. Fair regres- sion: Quantitative definitions and reduction baasedttoo--aeed algo- rithms. In International Conference on Machine Learning (ICML), pp. 120-129, PMLR, 2019.
Aghaei, S., Azizi, M. J., and Vayanos, P. Learning optimal and fair decision trees for non-discriminative decision- making. In International Conference on Artificial Intel- ligence and Statistics (AISTATS), volume 33, pp. 1418 1426, 2019.
5. Conclusion
We design significantly faster algorithm for Fair SC than previous
Our main contributions lie in (i) reformulating the Fair SC problem into differences of con- vex functions problem where we avoid expensive matrix routines using 2 instead of 1/2 and (it) showing that the ADMM subproblems can be solved efficiently, thanks to the DC dualization enabled by our design choice of includ-
Ahmadian, S., Epasto. A., Kumar, R., and Mahdian, M. Clustering without overerepresnttation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019.
Ali, J., Kleindessner, M., Wenzel, F,, Budhathoki, K.,
9

---

Accelerating Spectral Clustering under Fairness Constraints
Cevher, V., and Russell, C. Evaluating the fairness of discriminative foundation models in computer vision. In Proceedings of the 2023 AAAI/ACM Conference on AI, Ethics, and Society, pp. 809 833, 2023.
Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair Clustering Through Fairlets. In Advances in Neural Information Processing Systems (NeurIPS), volume 30. Curran Associates, Inc., 2017.
Alzate, C. and Suykens, J. Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence (T-PAMI), 32(2):335-347, 2008.
Chouldcchova, A. and Roth, A. A snapshot of the frontiers of fairness in machine learning. Communications of the ACM, 63(5):82-89, 2020.
Chuang, C.-S,, He, H., and Zhang, 7. A unified Douglas- Rachford algorithm for generalized DC programming. Journal of Global Optimization, 82(2):331-349, 2022.
Amini, A., Soleimany, A. P., Schwarting, W., Bhatia, S. N., and Rus, D. Uncovering and mitigating algorithmic bias through learned latent structure. In Proceedings of the 2019 AAAI/ACM Conference on Al, Ethics, and Society, pp. 289-295, 2019.
Davidson, I. and Ravi, S. Making existing clusterings fairer: Algorithms, complexity results and insights. In Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), volume 34, pp. 3733-3740, 2020.
Bach, F. and Jordan, M. Learning spectral clustering. In Advances in Neural Information Processing Systems (NeurIPS), volume 16. MIT Press, 2003.
Donini, M., Oneto, L.,, Ben-David, S., Shawe- Shawe-Taylor, J. S., and Pontil, M. Empirical risk minimization under fairness constraints. volume 31, 2018
Backurs, A., Indyk, P., Onak, K., Schieber, B., Vakilian, A., and Wagner, T. Scalable fair clustering, In International Conference on Machine Learning (ICML), pp. 403-413. PMLR, 2019.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pp. 214-226, 2012.
Beck, A. and Teboulle, M. Dual randomized coordinate de- scent method for solving a class of nonconvex problems. SIAM Journal on Optimization, 31(3):1877-1896 2021.
Eckstein, J. and Bertsekas, P. On the Douglas Douglas-Racchood Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Program- ming, 55(1-33:293-318, 1992.
Bera, S., Chakrabarty, D., Flores, N., and Negahbani, M.
Fair Algorithms for Clustering. In Advances in Neural Information Processing Systems (NeurIPS), volume 32. Curran Associates, Inc., 2019a.
Feng, R., Zhong, C., and Pan, T. Fair spectral clustering based on coordinate descent. Symmetry. 17(1):12, 2024.
Bera, S., Chakrabarty, D., Flores, N., and Negahbani, M. Fair algorithms for clustering. volume 32, 2019b.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. volume 29, 2016.
Bishop, C. M. and Nasrabadi, N. M. Pattern recognition and machine learning, volume 4. Springer, 2006.
Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: steps, Social Networks, 129):109-137, 1983. ISSN 0378-8733.
Boyd, S., Parikh, N., Chu, F.,, Peleato, B., Eckstein, J., al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine learning. 3(1): 1-12, 2011.
Hong, M., Luo, Z.-Q.. and Razaviyayn, M. Convergence analysis of alternating direction method of multipliers for family of nonconvex problems. SIAM Journal on Optimization, 26(1):337-364 2016.
Buolamwini, J. and Gebru, T. Gender shades: Intersec- tional accuracy disparities in commercial gender classi- fication. In Conference on fairness, accountability and iransparency, pp. 77-91. PMLR, 2018
Jiang, B., Ma, S., and Zhang, S. Alternating direction method of multipliers for real and complex polyno- mial optimization models. Optimization, 63(6)8883-898 2014.
Cereira-Perpinán M. A. and Wang, W. The k-modes al- gorithm for clustering. arXiv preprint arXiv: 1304. 6478, 2013.
Celis, E., Keswani, V., Straszak, D., Deshpande, A., Kathuria, T., and Vishnoi, N. Fair and diverse dpp- based data summarization. In International Conference on Ma- chine Learning (ICML), pp. 716-725. PMLR, 2018
Kleindessner, M., Samadi, S., Awasthi, P., and Morgen- stern, J. Guarantees for Spectral Clustering with Fairness Constraints. International Conference on Machine Learning (ICML), pp. 3458-346 PMLR, May 2019.
10

---

Accelerating Spectral Clustering under Fairness Constraints
Kohavi, R. et al. Scaling up the accuracy of naive- classifiers: A decision-tree hybrid. In KDD, volume 96, pp. 202-207, 1996.
low-rank factorization. Optimization Methods and Software, 2922):39-2663,
Shi, J. and Malik, J. Normalized cuts and image segmenta- tion. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 22(8):888 905, 2000.
Le Thi, H. A. and Pham Dinh, T. De programming and dea: thirty years of developments. Mathematical Program- ming, 169(1):5 00, 2018.
Singh, H., Kleindessner, M., Cevher, V., Chunara, R., and
Le Thi, H. A., Le, H. M.. and Pham Dinh, T. Feature selection in machine learning: an exact penalty approach using a difference of convex function algorithm. Machine Learning, 101:163-186, 2015.
Russell, C. When do minimax-faij learning and empirical risk minimization coincide? In International Conference on Machine Learning (ICML), pp. 31969-31989. PMLR, 2023.
Li, G. and Pong. T. K. Global Convergence of Split- ting Methods for Nonconvex Composite Optimization. SIAM Journal on Optimization, 25(4):2434 2460, Jan- uary 2015.
Sorensen, D. C. Implicit application of polynomial filters in ak-step amoldi method. SIAM Journal on Matrix Analysis and Applications, 13(1):357-335) 1992.
Stewart, G. W. Matrix Algorithms: Volume II: Eigensystems. SIAM, 2001.
Magnusson, S., Weeraddana, P. C., Rabbat, M. G., and Fis- chione, C. On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimiza- tion Problems. IEEE Transactions on Control of Network Systems, 3(3):296-309) 2016.
Sun, D. L. and Fevotte, C. Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence. pp. 6201-6205. IERE, 2014.
Nocedal, J. and Wright, S. J. Numerical optimization. Springer, 1999.
Sun, T., Yin, P., Cheng, I.., and Jiang, H. Alternating di- rection method of multipliers with difference of convex functions. Advances in Computational Mathematics, 44 (3):723-744, June 2018a.
Pham, T. N., Dao, M. N., Eberhard, A., and Sultanova, N. Bregman Proximal Linearized ADMM for Minimizing Separable Sums Coupled by Difference of Functions. Journal of Optimization Theory and Applications, 203(2): 1622-1658, 2024.
Sun, T., Yin, P., Cheng, L., and Jiang, H. Alternating di- rection method of multipliers with difference of convex functions. Advances in Computational Mathematics, 44 (3)723-744,, 2018b.
Piot, B., Geist, M., and Pietquin, O. Difference of con- vex functions programming for reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 27. Curran Associates, Inc., 2014.
Tao, P. D. et al. Algorithms for solving class of non- convex optimization problems. methods of subgradients. In North-Holland Mathematics Studies, volume 129, pp.
249-271. 1. Elsevier, 1986.
Quinlan, R. Thyroid Disease. UCI Machine Learning Repos- itory, 1987. DOI: https///oi.ogg/1124443/235
Thiao, M., Tao, P. D., and An, L. A DC programming ap- proach for sparse eigenvalue problem. In International Conference on Machine Learning (ICML), pp- 1063- 1070, 2010.
Rösner, C. and Schmidt, M. Privacy preserving clustering with constraints. In ICALP, 2018.
Rozemberczki, B. and Sarkar, R. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM international conference on information & knowledge management, pp. 1325-1334, 2020.
Tonin, F., Lambert, A., Patrinos, P., and Suykens, J. Extend- ing kernel PCA through dualization: Sparsity, robustness and fast algorithms. In International Conference on Ma- chine Learning (ICML), 2023.
Tu, K., Zhang, H., Gao, H., and Feng, J. A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convee problems. Journal of Global Optimization, 76(4):665-693, 2020.
Samadi, S., Tantipongpipat, U., Morgenstern, J. H., Singh, M., and Vempala, S. The price of fair pea: One extra di- mension. In Advances in Neural Information Processing Systems (NeurIPS), volume 31. Curran Associates, Inc., 2018.
Uschmajew, A. Well-posedness of convex maximization problems on stiefel manifolds and orthogonal tensor prod- uct approximations. Numerische Mathematik, 115:309- 331, 2010.
Shen, Y., Wen, Z., and Zhang, Y. Augmented Lagrangian alternating direction method for matrix separation based

---

Accelerating Spectral Clustering under Fairness Constraints
Von Luxburg, U. A tutorial spectral clustering. Statistics and Computing, 17(4):395-416, 2007.
Wang, J., Lu, D., Davidson, I., and Bai, Z. Scalable Spectral Clustering with Group Fairness Constraints. In Interna- tional Conference on Artificial Intelligence and Statistics (AISTATS), pp. 6613-6629. PMLR, April 2023.
Wang, Y., Yin, W., and Zeng, J. Global Convergence of ADMM Nonconvex Nonsmooth Optimization. Journal of Scientific Computing, 78(1):29-63, 2019.
Xu, Y., Yin, W., Wen, Z., and Zhang, Y. An alternating di- rection algorithm for matrix completion with nonnegative factors. Frontiers of Muthematics in China, 7:365-384 2012.
Zafar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. P. Fairness Constraints: Mechanisms for Fair Classifi- cation. In International Conference on Artificial Intelli- gence and Statistics (AISTATS), volume 54, pp. 962-970. PMLR, 2017.
Zhang. X. and Wang, Q. dual laplacian framework with effective graph learning for unified fair spectral clustering. Neurocomputing, 601:128210, 2024.
12

---

Accelerating Spectral Clustering under Fairness Constraints
A. Additional experimental results
A.I. Real-world data
LastFMNet
0.2
Balance
Time
0.1
2
25
50
25
50
k
k:
S-FSC
Ours
Figure 5: Fair spectral clustering on LastFMNet with s-FSC ( (Wang et al., 2023) (blue) and the proposed algorithm (orange). The plot uses the same structure as Figure 3 in the main body.
Thyroid
3
Balance
Time
10
2
50
25
50
k
k:
S-FSC
Ours
Figure 6: Fair spectral clustering on Thyroid with s-FSC (Wang et al., 2023) (blue) and the proposed algorithm (orange). The plot uses the same structure as Figure 3 in the main body.
In this experiment, we evaluate the runtime and average balance of the proposed algorithm for Fair SC on the real-world datasets summarized in Table 10. The affinity graphs for Thyroid, Census, and 4area obtained by radial basis function (RBF) kernel k(;,,22 my) exp(-7 ||æ; - 2zyl 11 where 1/d and y 1/d 0.01 for the smaller Thyroid, with rr d i = 1,..., We compare with the fastest available Fair SC algorithm, i.e., s-FSC from (Wang et al., 2023), Here, we report the complete results for the LastFMNet, Thyroid, 4area, and Census datasets in Figures 5 to 8.
We compare the runtime and average balance of the computed clustering across multiple numbers of clusters k: E (2....,50). Our method consistently outperforms state-of-the-are s-FSC terms of runtime across all datasets while maintaining approximately the same level of balance. Our method overall scales better & than s-FSC, especially in LastFMNet. Both methods require longer time for larger values. s-FSC requires more iterations for convergence the additional eigenvectors in the eigendecomposition routines, while method involves the computation of the SVD of small k matrix; this is computationally cheap for a small number of clusters, which is usually the case in applications. Our method also involves the MH matrix product with complexity O(nkk) k) for dense M; however, matrix multiplication is in practice significantly more efficient than the eigendecomposition. In terms of average balance, the clustering computed by our method achieves approximately the same balance to s-FSC. Balance on Thyroid and Census is low for both algorithms, which means that, in the Fair SC clustering, some groups are under-represented across multiple clusters. Overall, our method
13

---

Accelerating Spectral Clustering under Fairness Constraints
4area
0.6
Time (8)
Balance
0.5
100
0.4
25
50
S-FSC
Ours
Figure 7: Fair spectral clustering on 4area with s-FSC (Wang et al., 2023) (blue) and the proposed algorithm (orange). The plot uses the same structure as Figure in the main body.
Census
-10
Time (S)
Balance
25
S-FSC
Ours
Figure 8: Fair spectral clustering Census with s-FSC (Wang al., 2023) (green) and the proposed algorithm (blue). The plot uses the same structure as Figure 3 in the main body.
offers more efficient solution for Fair SC on real-world datasets, without compromising the fairness of the results w.r.t. the exact Fair SC solution. This makes promising choice for applications where both efficiency and fairness are crucial.
A.2. Scalability in RandLaplace
In this experiment, we employ the Randl dataset to evaluate the scalability of our proposed algorithm w.r.. sample size different k. The RandLaplace dataset is generated by random X n symmetric adjacency matrix and protected groups randomly assigned according a Bernoulli distribution with probability 0.3. The performance comparison between approach and the existing Fair SC methods, o-FSC (Kleindessner et al., 2019) and s-FSC (Wang et al., 2023), is depicted in Figure 4 and reported for completeness in Table 6 here. The results show that our algorithm outperforms the compared ones in terms of computational time for all tested sample sizes and cluster sizes. These results indicate that our algorithm exhibits superior scalability as the data size and number of clusters increase, underscoring our enhanced applicability for Icaler-scale problems.
A.3. Additional visualizations on synthetic data
We provide additional figures of the clustering results to illustrate the effectiveness of our method to preserve the clustering structure while satisfying the fairness constraints. We consider the 2D datasets from (Feng et al., 2024): the Elliptical dataset with 2, and the DS-577 dataset with l 3, h Figure shows the clustering results on the Elliptical
14

---

Accelerating Spectral Clustering under Fairness Constraints
Table 6: Running time in seconds for the RandLaplace dataset with different configurations (number of samples π E (5000, 7500, 10000} and clusters &o E {10, 25, 5. Standard deviations in parentheses.
(a) k 10, h
71
o-FSC
S-FSC
Ours
5000
68.12 (2.48)
4.00 (0.09)
3.50 (0.10)
7500
199.72 (3.20)
11.22 (0.27)
4.42 (0.12)
10000
454.68 (5.50)
23.99 (0.31)
5.93 (0.23)
(b) 25, h
(c) 50,
71
o-FSC
s-FSC
Ours
O-FSC
S-FSC
Ours
5000
71.58 (2.0)
8.73 (0.30)
3.84 (0.09)
5000
99.41 (3.0)
32.52 (2.11)
3.85 (0.09)
7500
204.72 (4.62)
28.10 (2.25)
4.52 (0.16)
7500
233.97 (8.35)
43.66 (7.36)
5.29 (0.11)
10000
481.18 (6.91)
42.93 (3.91)
5.93 (0.10)
10000
508.63 (9.78)
74.94 (7.62)
7.70 (0.16)
Table 7: Running time in seconds (average and standard deviation over 5 runs) for the m-SBM benchmark from Table and the considered real-world datasets from Table 2.
Time (s)
Dataset
O-FSC
s-FSC
Ours
m-SMB 5000)
96.39 (3.62)
75.61 (2.58)
3.29 (0.11)
m-SMB (n 7500)
235.62 (4.48)
88.99 (4.35)
5.29 (0.21)
M-SMB (n 10000)
495.70 (9.49)
107.94 (5.10)
9.19 (0.36)
LastEMNet
103.82 (2.87)
19.08 (1.96)
4.59 (0.30)
Thyroid
279.03 (4.21)
30.49 (3.17)
7.38 (0.16)
Census
136.60 (0.69)
15.78 (1.06)
4area
166.92 (0.73)
25.85 (1.4)
dataset (top) and the DS-577 dataset (bottom). These plots show that our method produces assignments comparable to exact algorithms (o-FSC.s-FSC). Critically, we achieve this with reduced computations, as shown in the main paper, which constitutes our main contribution.
A.4. Additional metrics and dataasets
In main body, we follow the setups of (Kleindessner et al., 2019; Wang et al., 2023) and report the average balance. For completeness, also report the minimum balance for Table with 25 in Table 8.
Table 8: Minimum balance for the considered real-world datasets from Table 2.
Dataset
Time (s-FSC)
Time (Ours)
Min. Balance (s-FSC)
Min. Balance (Ours)
LastFM 19.08
4.59
0.0027
0.0029
Thyroid 30.49
7.38
0.0011
0.0012
Census
136.60
15.78
0.0001
0.0001
4area
166.92
25.85
0.1582
0.1517
We also evaluate on the common FacebookNet dataset (Wang et al., 2023) that collects Facebook friendship links with n = 155, h = 2. We show results in Table 9. These results further demonstrates the computational advantage our method, while achieving similar clustering quality to exact algorithms.
15

---

Accelerating Spectral Clustering under Fairness Constraints
on cotaset
cfSc
PFSC
Curs
32.
12.5
12.1
Prts
300
50, G-3
163
Go G:
10.1
C1.00
Cleb
25.
64,
735
2.5
50
50
52-
24-
2.5
2.-
61-
02
20-
-55
-5
-.5
-50-
-00
-1
-75
-3
-13
Clustering Visualizarions on do577 detaset
6-55
01.2
C2.02
C1 02
C2:00
02000
Figure 9: Clustering results on synthetic datasets. The top panel shows the Elliptical dataset with k = 2, h 2, and the bottom panel shows the DS-577 dataset with & = 3, / = 3. Our method preserves the clustering structure while satisfying fairness constraints.
Table 9: Running time in seconds for the FacebookNet dataset with balance and spectral clustering cost.
#Clusters
Method
Time (s)
Balance
SC Cost
2
o-FSC
0.798
1.00
0,126
2
s-FSC
0.193
1.00
0.126
2
Ours
0.055
1.00
0.133
25
o-FSC
9.908
0.84
14.114
25
s-FSC
6.422
0.84
14.114
25
Ours
0.131
0.84
14.128
50
o-FSC
12.243
0.58
37.084
50
s-FSC
11.558
0.58
37.084
50
Ours
0.215
0.58
37.100
B. Additional experimental details
Experimental setups. Regarding optimization of the dual DC problem, we employ the LBFGS algorithm in the scipy implementation with backtracking line search using the strong Wolfe conditions with initialization from the standard normal distribution; the stopping condition is given by gtol = 10 ftol= = 10 10-4. The ADMM algorithm run with (0) 0.005, 7 10. The compared methods o-FSC (Kleindessner al., 2019) and s-FSC (Wang et al., 2023) employ the scipy eigendecompositiinn routine. For S-FSC, use [ shift, suggested in their paper. The k-means algorithm is run to obtain the clustering indicators for all compared methods. The real-world datasets used in the experiments are summmarized in Table 10.
The update rule for a in Algorithm is standard in ADMM (Boyd et al., 2011) and given by
()
if R
F
a (1+1)
a00/T
if
|t0 || R(
||
(19)
(
otherwise
with primal and dual residuals R(O (1 (1) yiu and (() - y(+1)). The parameters and μ are set to
16

---

Accelerating Spectral Clustering under Fairness Constraints
Table 10: Description of the real-world datasets used for the experiments.
Dataset
Samples (1)
Groups (h)
Group type
Last
5576
Nationality
Thyroid
7200
Disease
Census
32561
Demographic
4area
35385
4
Research field
and 10, respectively.
C. Additional discussions on related works
Our method follows the established line of work on Fair SC, which enforces fairness via linear constraints in the embed- ding (Kleindessner al., 2019; Wang al., 2023). There exist other spectral clustering methods that do follow this line of work and enforce fairness via different means. (Feng al., 2024) introduce faimess by changing the SC objective with different fairness regularization term; they do not employ the group-fairesss constraint F H = O. They apply coordinate descent to this new objective where they relax the discrete clustering indicator constraint without orthogonality constraints H H = I. Therefore, (Feng et al., 2024) solves different problem than (6): their solution is far from the exact one leading to higher spectral cost and potential training instability. Another related work is (Zhang & Wang, 2024). Our work designs a much faster method for the existing Fair SC problem defined in (Kleindessner et al., 2019). (Zhang & Wang, 2024) instead focuses on improving fairness and orthogonal to our algorithmic contribution: it learns an induced fairer graph where Fair SC is applied. Future work could combine our method on top of (Zhang & Wang, 2024) by applying our faster algorithm to their learned graph.
Other works on fair clustering include (Bera et al., 2019b; Backurs et al., 2019), which are not directly comparable to our work as they do not consider the spectral clustering objective. (Bera et al., 2019b) propose LP-based k-(means, median, center) clustering. Using their formulation our work would ignore the RatioCut objective, resulting in suboptimal solutions wr.t. the spectral objective. (Backurs et al., 2019) use fairlets for prototype-based clustering. However, extending the fairlet analysis, which relies on the k-median and k-center cost of the fairlet decomposition, to the spectral setting not trivial, SC involves spectral embedding step followed by clustering in the embedding space, where reassigning points within fairlet can significantly alter the spectral embedding and hence potentially violating fairness, making it non-trivial to incorporate their analysis in the fair SC case. The primary contribution of our present work is to design significantly faster method for the already established Fair SC problem defined in (Kleindessner et al., 2019), rather than designing alternative fair clustering problems.
D. Proofs and derivations
D.I. Proofs of Assumptions of Proposition 3.4
We prove the convergence result from Proposition 3.4 by applying Proposition 3 from Magnusson al. (2016) to specific ADMM structure. There they consider problems of the form
min 2.2
u(x) +0²)
(20)
s.t.
x 2
(21)
Ax + Bz
(22)
We can already cast Problem 11 into this structure by letting
X' Sh and u(x) (f)x)
Z {a e n F Y 0} and (2)) 0
A = M, B and c 0.
17

---

Accelerating Spectral Clustering under Fairness Constraints
To apply their result, verify that four key assumptions hold, namely Assumption D.I, Assumption D.2, Assumption D.4 and Assumption D.5 that be found in Magnusson et al. (2016).
Assumption D.1. The functions u and are continuously differentiable.
This is satisfied in our setting.
Assumption D.2. The sets X' and 2 are closed and can be expressed in terms finite number of equality and inequality constraints. In particular,
X' far E Raak (b(a) 0, ((x) s
(23)
Z {a Rank 10(z) = 0, axx) s 0)
(24)
where v. o, 0, a are continuously differentiable functions.
This is clear from the definition of the spaces X' and 2, a proof is provided for the case of the Stiefel manifold in the following lemma.
Lemma D.3 (Smooth Representation of Orthogonal Matrix Constraints). Let A E Raxm be a matrix satisfying the orthogonality constraint A I, where In denotes the m x identity matrix. Then there exists a smooth function Rum mm((+1)/22 such that the constraint can be equivalently expressed as
fo R (b(z)= =0}-
where x veo(A) is the vectorization of matrix A.
Proof. Let x E gm denote the vectorization of matrix obtained by column-wise stacking:
011
apl
apm
Under this vectorization scheme, the (k, element of A corresponds to the ((j 1)m + k)-th component of æ, i.c.. agj Ij The orthogonality constraint AT A Im is equivalent to requiring that the columns of A form an orthonormal system. Specifically, for 1 sisj m:
akakk dij.
where diy denotes the Kronecker delta. Expressing this constraint in terms of the vectorized representation we obtain:
n
71--))4470-1144 = dey-
We now define the function gum (m)(+11)/2 with components:
(xy( Σ M(-D)+kk - -ijs Isigj S m.
The orthogonality constraint A 4m is then equivalent to the condition (xxx) = 0. To establish smoothness, observe that each component Phy (I) is a quadratic polynomial in the elements of z. Since polynomial functions possess derivatives of all orders, each thy is smooth (i.c., C.). Consequently, the vector-valued function & is smooth. Therefore, the orthogonality constraint on matrix admits smooth representation.
18

---

Accelerating Spectral Clustering under Fairness Constraints
Assumption D.4. At every step from Algorithm I, the solutions of sub-Problem 13 and sub-Problem 14 computed locally globally optimal.
This assumption allows solutions the subproblems be only locally optimal. In case, both subproblems allow global optimality.
Assumption D.5. Let L denote the set of limit points of the sequence (x, H10 Y JeN IeN and let ( L. The set of constraint gradient vectors
Cx = (Vi. 1, dim 3) (V) o,(3) 0}
(25)
associated to X' is linearly independent. Similarly, the set of constraint gradient vectors C2 (2) is linearly independent.
This assumption is regularity assumption that is usually satisfied in practice according to Magnusson et al. (2016). The following lemmas are dedicated to proving that it holds in our case.
Lemma D.6 (Linear Independence of Orthogonal Constraint Gradients). Let Rum be identified with the matrix A E | where Api Fp. for 1...., and i I,..., Define (ii( = =p Tpi - 8ig for 1 S i S m. C(x) = (V (x)) sis j S m). If AT
then (T)) linearly independent at
Proof. Suppose there exist scalars Xij (with Dij = Xze) such that
Σ
V (3) O.
Isisism
Let be the m x m symmetric matrix with entries Asg = Xıj. Define the scalar function
S(A)
Σ
(()b)(()=
m Σ
X 2
(aF
-
1 - AAAAAAAA-)))
1sisism
1j=1
where az denotes the i-th column of A. For any perturbation H E Ruxm the directional derivative of at A in the direction of H is
Df(A)[H TT(HHH A+ A))))
= =Tr(H- AA)
-(ve vec (AA)).
By the chain rule, and since we assumed Σ Aij V (x) = 0, we have
Xij Vatiy(A), vec(H) ) 0, AH.
Df(A)[H =
Σ Isisism
This implics vec(AA) = O, and hence AA = Since AT at ã, A has full column rank, and thus A = This implics Ài = 0 for all j. Therefore, the only linear combination of the gradients V (z that equals zero is the trivial one, which proves that C(z) linearly independent.
Lemma D.7. Let F R and E R.n Define = voc H)) E Rk and consider the constraint FT H Let 8(2) vec(F" H) E hbk The set of constraint gradients
C(2) = (V))(22) i hk]
linearly independent at any such that F whenever F' has full column rank.
Proof. Using the Kronecker product identity vee vee (AB) (1 @ A) vec( B), we can express 0(2) as:
(()) = (T & F FT)= = Mz.
19

---

Accelerating Spectral Clustering under Fairness Constraints
where M 14 & FT Rhkxxn
Since (z) is linear, its Jacobian is the constant matrix M. The gradient of the i-th component of (z), denoted (z), is the i-th row of M transposed. Thus, the set (z2) consists of the rows of M.
The rows of are linearly independent if and only if M has full row rank, which is hk. We have:
rank(M) [M) = rank(I rank(F") = krank(F).
Therefore, (M) hk if and only if rank (F) h. This means the gradients in C(2) are linearly independent if and only if F has full column rank (if rank(F) = h). For instance, this is the case in the Fair SC problem when h is set to be the number of groups minus I (Wang et al., 2023). This can be guaranteed by solving (6) with == F( h - 1], i.e. removing the last column of F, which guarantees that rank(F) = h - with same range (Wang et al., 2023). This holds regardless of the order of the groups (Wang et al., 2023).
D.2. Derivation of Problem 6
In this subsection, we review the derivation of the fair spectral clustering problem (6). First, recall that spectral clustering aims at partitioning D into clusters by minimization of a normalized cut objective, as detailed in (Shi Malik, 2000;
Von Luxburg, 2007). The spectral clustering problem is defined
min TER
(TTTLT) s.t. TT Ik-
(26)
Because of the normalized cut objective, Problem 26 is also often referred to as the normalized spectral clustering problem, to distinguish it from the spectral clustering problem with mincut criterion without normalization. By substituting T= D-122p I/2H in Problem 26, we obtain the equivalent problem in terms of the normalized Laplacian L:
min Tr(H LH) s.t. H -k
(27)
HER
Solving the spectral clustering problem amounts finding the k eigenvectors of i. corresponding to the k smallest eigenvalues and then applying k-means clustering to the rows of D-1/2 H. The fair spectral clustering problem is obtained by adding the fairness constraint (5) to the spectral clustering problem (26):
min TERax
Tr(T LT)
S.L. T DT Ia.
Fg FTT= 0.
(28)
By substituting T 1-2 H as above, we obtain the equivalent Fair SC problem in terms of the normalized Laplacian L:
min
Tr( LH) s.t. H Ix.
FTH ===0, 0,
(29)
HEROXA
where F= 1-2/ Now, we have that for all H E Raxk
Tr(HTin = (H - -Tr DH 1/11//2DD (WDD--) Tr (HTH)) H) -Tr (H MH).
On the Stiefel manifold, the quantity Tr (H H) is constant so that the minimizers of Problem 29 are the maximizers of Problem 6.
D.3. Proof of Proposition 3.2
Proof. Expanding d () to recover the expression of the augmented Lagrangian shows that H + 6(MH) is convex as long as < 1. Then, following Proposition 3.1 from (Tonin et al., 2023), equivalently we can write the problem as
inf HeR
((HH)
sup (VV, MH) - o² = inf VER=Xa
g(H)+ + inf (V- (V,
(30)
H
VERTxt
inf HEBBKR.VERR..
9(H) + (V( (V,MH)
(31)
inf (*(V)-
sup
{MVV H) (HH)
(32)
VEREXR
HERaok
inf VERNXA
(*(V)= - g" (MVV),
(33)
20

---

Accelerating Spectral Clustering under Fairness Constraints
where we used the self-adjointness of M.
D.4. Proof of Proposition 3.3
Proof. We begin by the derivation of x (V)::
(²(V) sup () - (ZZ)
(34)
1 |21 + (P,2) +
sup Z)
2 1 - -
(35)
2
sup(
1
1| v
||V]] (P, + 1 y1
(36)
2
||]]2
1
1 v112 (P.
a 1z - Y y13
(37)
2
nVV By nullifying the gradient in Z, we find that the critical point 2 satisfies n(V + P - aY), where 1 I- which in turn gives
(Vv)= 1V12 |ln(V + VII
(38)
(P.n(V + - aY))
(39)
a 2/2 (n(V + aY) 11
(40)
We now prove that 9 (MV) Tr (T-)))TTVTVP (VVTM2V) by using that the Fenchel-Leegndree conjugate of g is the Schatten 1-norm, also called the nuclear norm: g²) = Ek=1 (A(U)/ = |U'l,, We then have
sup (MV, H) |VVIs, Tr (VVTMAV). H H
(41)
where the last equality is obtained by exploiting the SVD of MV.
21


Reviews:
[{"review_id": "WSJ00PvoZD", "reviewer": "Reviewer_1h8o", "summary": "This work considers fair spectral clustering, demonstrating a reformulation of the fairness constraints which allows for a considerable improvement in the runtime of existing fair algorithms. Specifically, by reformulating the trace maximization problem often used for FSC into one of multiple subproblems in the difference of convex functions setting, state of the art methods for the unfair problem are able to be employed with fairness considerations. Algorithmic ideas are sketched theoretically and further validated with experiments on real and synthetic datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the valuable feedback and address the remaining concerns below.\n\n> Q1. Expand on the convergence analysis.\n\nOur convergence analysis is based on the theory for ADMM applied to nonconvex problems from [1], which analyzes the convergence of ADMM for structured nonconvex problems of the form presented in our Equation (11) (a composite function minimization with linear constraints).\n\nApplying Proposition 3 from [1] to our specific ADMM structure, we can assert the following: Provided the sequence of dual variables ($P^{(i)}$) generated by the algorithm converges (i.e., $\\lim_{i\\to \\infty} P^{(i)} = P^\\star$ for some $P^\\star$), and under mild assumptions (Assumptions 7, 8, 9 in [1], which correspond to our problem having closed sets, local solutions being found for subproblems, and regularity assumptions), then any limit point ($H^\\star, Y^\\star$) of the primal sequence ($H^{(i)}, Y^{(i)}$) satisfies first-order conditions. \n\nWe will revise the paragraph on \"Convergence analysis\" on page 6 to more formally state in a separate Proposition the convergence guarantee and its conditional nature on dual convergence based on [1], due to the technical challenges in this nonconvex setting.\n\n> Q2. Balance interepretation as $k$ changes.\n\nFig. 2 shows that balance typically decreases as the number of clusters $k$ increases. \nThis trend is not unique to our algorithm.\nIt is observed in both our method (orange line) and the exact s-FSC algorithm (blue line).\nAs $k$ increases, the expected size of each cluster diminishes.\nSmaller clusters can lead to a greater number of highly unbalanced groups.\nThe reported balance metric is the average of (3), i.e., the minimum ratio of group ratios in each single cluster [2]. \nConsequently, even if a few clusters exhibit poor balance (due to small cluster size), this can significantly lower the balance score.\nSimilar trends and reasonings can be found in [2, Sec. 6.1].\nFrom a theoretical angle, [2, Theorem 1] notes that, if $k$ increases for fixed $n$, the fairness recovery of fair SC (in the SBM setting) becomes looser.\nWe also note that the primary contribution of our present work is to design a significantly faster method for the _existing_ Fair SC problem, rather than improving the balance of Fair SC.\n\n> Q3. Rank of $M$.\n\n- This is a technical assumption needed to compute the gradient of $g^\\star$ from Proposition 3.3.\n- Regarding duplicates in the data. While in regression it may be meaningful to have duplicated data as the same input can result in a different output (e.g., a different measurement), in unsupervised learning the duplicates just lead to a simple re-weighting of the empirical risk. Therefore, one can simply filter the duplicates in a pre-processing step.\n- This assumption can be satisfied using infinite-dimensional kernels $\\kappa$. Specifically, this is always the case with universal kernels (e.g., the Gaussian kernel) [4].\n- In case the given data leads to $M$ not being full rank, the problem can be regularized with $\\mathcal{M} := M+(1+\\omega)I$ for small $\\omega>0$. This is a well-studied regularization technique that is widely used, e.g., in kernel methods [3].\n\n> Q4. DC applicability to other settings.\n\nThe reviewer raises an interesting point regarding the applicability of our framework to more general setting/notions. \n\nFor example, it might be possible to extend it to constrained spectral clustering.\nBy considering a modified indicator function $h(\\cdot)$, our framework can accommodate other constraints/fairness metrics whenever the DC formulation is maintained. The ADMM algorithm (Algorithm 1) can then be applied with appropriate modifications to the subproblem w.r.t. $Y$. For instance, linear constraints have been used in the literature to encode must-link and cannot-link constraints within spectral clustering [5].\n\nWe will add a remark in the final version of the paper to reflect this potential broader application of our method.\n\n---\n\n[1] Magnússon et al. \"On the convergence of alternating direction lagrangian methods for nonconvex structured optimization problems.\" IEEE Transactions on Control of Network Systems (2015).\n\n[2] Chierichetti et al. Fair Clustering Through Fairlets. NeurIPS 2017.\n\n[3] Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning. Springer, 2006\n\n[4] Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.\n\n[5] Kawale et al. \"Constrained spectral clustering using l1 regularization.\" International Conference on Data Mining (2013).", "claims_and_evidence": "Claims are well supported by theoretical analysis and experimental validations. My only concerns are with respect to the convergence analysis and problem assumptions (see questions).", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I skimmed the proofs deferred to the appendix and did not note any major issues. I do feel the paper lacks a more thorough theoretical treatment of the convergence guarantees (discussed in Section 3.2). Moreover some of the problem assumptions are not immediately clear to me (see my questions).", "experimental_designs_or_analyses": "The experimental design appears valid / standard for the problem at hand.", "relation_to_broader_scientific_literature": "The authors effectively contrast their results against prior work in spectral clustering (with and without fairness constraints). As a non-expert on this problem, the paper caught me up to speed well.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths: \nThe paper is well written and provides a nice introduction to spectral clustering + the methods leveraged to ensure added fairness constraints are met. Moreover, the results (experimental in particular) are compelling to demonstrate a significant computational improvement over the prior state of the art.\n\nWeaknesses: \nThe noted assumption that M is full rank seems potentially weak in practice. For example, the authors note that this is violated when datasets have duplicates--a very common issue when collecting data. Correct me if I'm wrong on this!", "other_comments_or_suggestions": "n/a", "questions_for_authors": "Can you explain why the balance is worse for your algorithm for small values of k?\n\nIs the assumption that full rank assumption on M standard? In what contexts might this not hold / how much does it weaken the presented results?\n\nCan you expand on the convergence guarantee of this algorithm?\n\nCan this difference of convex function reframing be used to capture other notions of fairness (ie. not just the notion of balance)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Tz1Mcjy8qV", "reviewer": "Reviewer_jPJw", "summary": "This paper studies the problem of fair spectral clustering. The authors propose an ADMM-like algorithm for optimization with theoretical guarantee, and the experimental results show effectiveness in improving fairness.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1. Our contribution within the broader literature\n\nWe note that our primary contribution is to design a significantly faster method for the *existing* well-established Fair SC problem as defined in [1], rather than improving the balance of Fair SC.\n\nWe respectfully disagree that the performance of our method and s-FSC is \"mostly comparable\".\nOur method achieving similar balance to the exact algorithm validates the quality of our found solution.\nOur method consistently improves computational efficiency over SOTA s-FSC, as shown in Tab. 2,3 and Fig. 2,3. \nThe improvement is particularly evident as the sample size $n$ and number of clusters $k$ grow, as shown in Tab. 1 and Fig. 3.\nCrucially, these speed-ups stem from the fact that our algorithm replaces the eigendecomposition of s-FSC with significantly more efficient DC steps, resulting in a more scalable approach for Fair SC on real-world datasets.\n\nWe want to emphasize that our work may not limit itself to “unsupervised clustering\".\nClustering is unsupervised by definition and is the main focus of this work, as stated in the Introduction.\nOur proposed DC framework exhibits favorable properties for applicability to broader settings, e.g., following work could consider constraints on the clustering solution (e.g., must-link/cannot-link constraints) to be integrated directly into the optimization problem as long as they preserve the DC structure.\n> Q2. Additional insights for the theoretical results\n\nThe main contribution of this paper is designing much faster methods for spectral clustering with fairness constraints.\nThis is done by reformulating the fair SC problem into a DC functions problem (Eq. (10)).\nUsing this new formulation, an ADMM-type algorithm can be used to efficiently perform fair SC. \nThis is because there is no need to compute the eigendecomposition of the Laplacian matrix.\n\nIn short, Proposition 3.2 derives the dual of the DC formulation. This is important because existing work either relied on expensive eigendecomposition or did not consider the fairness constraints. Proposition 3.3 provides the exact closed-form expressions for all the terms involved in the dual problem so that gradient-based techniques can be applied.\n> Q3. Additional metrics and baselines\n\nTo address the reviewer's concern, we have conducted additional comparisons between our method with the very recent FFSC method [FEN24] to enrich the comparative analysis. \nWe also report the group-fair constraint metric (Definition 2.2). We report the results in *Table iKL4-1* in the rebuttal.\n\nWe observe that **our algorithm is 7-12x faster than FFSC and results in significantly better spectral clustering cost and fairness constraint satisfaction**.\nFFSC modifies the objective with additional regularization, so it solves a different problem than ours, resulting in a different balance-clustering trade-off with higher balance but substantially worse clustering quality and group fairness metric.\nNote that these are two different measures of fairness, where balance promotes the same number of group individuals in each cluster (Eq. (3)), and the latter is related to the proportion of each group in all clusters being the same as in the general population (Eq. (4)). Additional details are given in the *Response to Q1 of Reviewer iKL4*.\n\nWe additionally ran our method on the FacebookNet dataset in *Q1 to Reviewer ztMM* and also report the minimum balance metric in *Q5 to Reviewer ztMM*.\n> Q4. Large-scale experiments\n\nOur current experiments include datasets of size up to ~35,000 samples, in line with the scale of datasets commonly used in the fair SC literature, e.g., [2,FEN24].\nTo address the reviewer's concern, we additionally tested on the Diabetes dataset ($n=253,680,k=2$).\nOur method results in a fair clustering in 123.36s, whereas the s-FSC (previous SOTA for [1]) did not even converge after 24 hours.\nOur method achieves fairness constraint satisfaction $||F^\\top H||^2=0.000064$ (closer to 0 is better), 0.78 balance, 1.99 SC cost, and orthogonality $||H^\\top H-I||^2=6.49 \\times 10^{-9}$ (closer to 0 is better).\nThis experiment shows that **our method allows to scale Fair SC to problems that were not even possible to solve in reasonable time** with previous algorithms.\n> Q5. Fig. 2 intuition.\n\nFig. 2 showcases runtime and balance comparing our method and the SOTA s-FSC exact baseline. \nThe left plots show that **our method consistently outperforms s-FSC** in terms of runtime, with even better efficiency gains as $k$ increases.\nThe right plots compare the balance achieved by both methods, showing **our method does not decrease the fairness** compared to the exact algorithm. We will clarify this in the caption.\n\n[1] Kleindessner et al. Guarantees for Spectral Clustering with Fairness Constraints. ICML 2019\n\n[2] Wang et al. Scalable spectral clustering with group fairness constraints. AISTATS 2023\n\n[FEN24] Feng et al. Fair Spectral Clustering Based on Coordinate Descent. Symmetry 2024", "claims_and_evidence": "Overall the claims are justified by evidences. However, the performance of s-FSC and the proposed method seems mostly comparable on all the datasets, as shown in Tab. 3. The only difference is in compuatational time, but both methods take at most few minutes. This poses question on the advantages or superiority of the proposed method.", "methods_and_evaluation_criteria": "The methods and criteria for comparison are limited. For example, only one recent work is considered as the alternative baseline, and only balance is considered as the fairness metric. This makes evaluating the significance of this work hard. Furthermore, most experiments are conducted on low-dimensional data, while experiments on high-dimensional and large-scale datasets are needed to validate the effectiveness.", "theoretical_claims": "I have checked the proofs and theoretical results. However, there is no insight provided for the two propositions, and therefore it is hard to conclude theoretical contributions.", "experimental_designs_or_analyses": "The experimental designs look sound", "relation_to_broader_scientific_literature": "This paper can be of contribution to fair unsupervised learning. However, I am not sure if the discussion leads to a significant contribution, as the setup is limited to unsupervised clustering.", "essential_references_not_discussed": "I don't see any essential references missing.", "other_strengths_and_weaknesses": "N/A.", "other_comments_or_suggestions": "Fig. 2 is a bit uninformative. I am not sure what conclusions I should draw from it.", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "btUMo41Aso", "reviewer": "Reviewer_iKL4", "summary": "This work addresses the issue of fairness in spectral clustering by proposing a new efficient method for fair spectral clustering (Fair SC). The authors introduce a novel algorithm that casts the Fair SC problem within the difference of convex functions (DC) framework and employs an alternating direction method of multipliers (ADMM) type of algorithm adapted to DC problems. The key contributions include a new variable augmentation strategy and the use of gradient-based algorithms to solve the subproblems efficiently, avoiding the computationally expensive eigen-decomposition required by previous methods. The paper demonstrates the effectiveness of the proposed method through numerical experiments on both synthetic and real-world datasets, showing significant speedups in computation time over prior art, especially as the problem size grows.\n\n## Update after rebuttal\n\nThanks for your explanation, I will maintain my rating.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1. Comparative analysis with recent works [FEN24, ZHA24]\n\nWe first provide discussions, followed by experiments.\n- Our work designs a much *faster* method for the *existing* Fair SC problem defined in [3]. [ZHA24] focuses on improving balance and is orthogonal to our algorithmic contribution: it learns an induced fairer graph where Fair SC is applied. Future work could combine our method on top of [ZHA24] by applying our faster algorithm to their learned graph.\n- [FEN24] does not adopt [3]. They instead introduce fairness by changing the SC objective with a different fairness regularization term; they do not employ the group-fairness constraint $F^\\top H=0$. They apply coordinate descent to this new objective where they relax the discrete clustering indicator constraint _without_ orthogonality constraints $H^\\top H=I$. Therefore, [FEN24] solves a different problem than (6): their solution is far from the exact one of (6) leading to higher spectral cost and potential training instability.\n\nWe ran additional experiments comparing with FFSC [FEN24], following the setup in Tab. 2. **Our method is 7–12x faster and achieves significantly better spectral clustering cost and fairness constraint satisfaction.** \n\nFFSC's modified objective shows a different balance-clustering trade-off with higher balance but worse clustering and group fairness. Note the two different measures of fairness, where balance promotes same number of individuals in each cluster (Eq. (3)), and group fairness ensures proportional representation (Eq. (4)).\n\n**Table iKL4-1:** Comparison with FFSC [FEN24]\n|Dataset|Method|Time (s) (↓)|Spectral Clustering Cost (↓)|Balance (↑)|Group Fairness $\\|\\|F^\\top H\\|\\|^2$ (↓)|$\\|\\|H^\\top H - I\\|\\|^2$ (↓)|\n|---|---|---|---|---|---|---|\n|LastFM|FFSC|33.74|1067.906|**0.2701**|4.032|3.91E+00|\n|LastFM|Ours|**4.59**|**1.086**|0.0093|**0.000014**|**1.36E-11**|\n|Thyroid|FFSC|56.11|3080.848|**0.0170**|15.79|1.02E+01|\n|Thyroid|Ours|**7.38**|**0.353**|0.0030|**0.000001**|**2.18E-11**|\n|Census|FFSC|193.92|146669.885|**0.0051**|9.47|2.14E+00|\n|Census|Ours|**15.78**|**130.973**|0.0004|**0.000012**|**4.12E-10**|\n|4area|FFSC|237.35|285174.392|**0.6403**|58.30|2.66E+00|\n|4area|Ours|**25.85**|**242.000**|0.3823|**0.000001**|**4.22E-10**|\n\nWe also ran on new datasets in *Q1 to Reviewer ztMM* and *Q4 to Reviewer jPJw*.\n> Q2. Feasibility of changes.\n\nWe address the two changes:\n- Casting the Fair SC problem directly as DC using $M$ requires computing $M^{1/2}$, with complexity akin to the original problem. Standard SC seeks the top eigenvectors of $M$, which are identical to those of $M^2$. Thus, without fairness constraints, optimizing with $M^2$ yields the same solution. Extensive empirical evidence confirms that even with fairness constraints, this substitution preserves clustering quality.\n- Enforcing fairness via $MH$ instead of $H$ enables efficient dualization of the ADMM subproblem.  While in general $F^\\top (MH)=0$ isn’t strictly equivalent to $F^\\top H=0$, it enforces fairness on the affinity-weighted embeddings $MH$, which we noticed promotes similar groups. One intuition is that in the simpler SC case, where $H$ is top eigenvectors of $M$ as $MH = H \\Lambda$ with $\\Lambda$ eigenvalues, the constraint $F^\\top (MH)=0$ matches $F^\\top H = 0$. As shown in Tab. 3, our method achieves comparable balance and clustering cost to the exact algorithm on multiple real-world problems.\n\nWhile we agree that a stronger theoretical link would be ideal, we noticed that establishing it is challenging and remains an open problem.\nExtensive empirical validation supports the feasibility of this choice, making the method a strong candidate for efficient Fair SC.\n> Q3. Additional visualizations and implementation details\n\nWe consider 2D datasets from [FEN24]: 'Elliptical, 'DS-577'. Figures are at https://imgur.com/a/GiBnUIs\n\nClustering labels are shown by color; sensitive groups by shape. Legend: “C-i, G-j” for Cluster-$i$, Group-$j$.\n\nThese plots show that our method produces assignments comparable to exact algorithms (o-FSC, s-FSC). Critically, we achieve this with reduced computations, as shown in the main paper. We emphasize that our main contribution lies in accelerating Fair SC - not improving fairness metrics over the existing Fair SC.\n\nFollowing reviewer suggestions, we will revise tables to bold best results. App. B provides implementation details, including hyperparameters, optimization settings, and $\\alpha$-update rule. We will also release our code.\n> Q4. Convergence rate.\n\nFor ADMM convergence, see *Q1 to Reviewer 1h8o*. Regarding rates: Deriving rates for ADMM in general nonconvex settings is challenging and typically requires assumptions difficult to verify in general for our (10). While a rate analysis is promising future work, our method shows significantly higher computational efficiency as detailed in the *Q4 to Reviewer ztMM*.\n\n[3] Kleindessner et al. Guarantees for Spectral Clustering with Fairness Constraints", "claims_and_evidence": "The claims made in the paper are supported by clear and convincing evidence. The authors provide a detailed derivation of the proposed algorithm and demonstrate its effectiveness through extensive experiments. The main claims are:\n1. The algorithm achieves higher computational efficiency compared to existing methods (o-FSC and s-FSC).\n2. The method maintains the fairness constraints while achieving comparable clustering quality.\n\nThe evidence provided includes:\n1. Theoretical analysis of the DC framework and ADMM algorithm.\n2. Numerical experiments on synthetic datasets (m-SBM, RandLaplace) and real-world datasets (LastFMNet, Thyroid, Census, 4area).\n3. Comparison of runtime and balance metrics with existing methods.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense for the problem at hand. The authors use standard benchmarks and metrics to evaluate the performance of their algorithm. The evaluation criteria include: runtime, balance, clustering cost.\nThe methods are well-suited for the problem, as they address the computational inefficiency of previous methods while maintaining fairness constraints.", "theoretical_claims": "When the authors switch the problem 6 (traditional fair spectral clustering optimization problem) in the work to their proposed optimization problem, they made two changes:\n1. Use $M^2$ instead of $M$,\n2. Enforce fairness on $MH$ instead of $H$.\n\nIt would be better to mathematically prove the feasibility of these two changes instead of empirical results.", "experimental_designs_or_analyses": "The experimental designs and analyses are valid. The experiments include:\n- Comparison of runtime and balance metrics with existing methods (o-FSC and s-FSC).\n- Sensitivity analysis of the ADMM penalty parameter α.\n- Scalability analysis on datasets of varying sizes and cluster numbers.\n\nHowever, it would be better to include more benchmark dataset and baseline method, like [FEN24](https://www.mdpi.com/2073-8994/17/1/12), [ZHA24](https://www.sciencedirect.com/science/article/pii/S0925231224009810?casa_token=T6cg70BHqNAAAAAA:Ow9fzmBXvJE6p3Y5vmFyUPCA-35q3KdbX2BwaSI5b1kHxBGhlxRtZp_CmyxOrokXzyvdN9oO), and other state-of-art methods for fair spectral clustering.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-related to the broader scientific literature. The authors reference and build upon previous work in fair machine learning, spectral clustering, and optimization methods.", "essential_references_not_discussed": "There are a few essential references that could be included for a more comprehensive understanding of the context. For example, there are several new fair spectral clustering (also gradient based) methods proposed in recent years. Could you review more related work and explain the difference, and the novelty of this work?", "other_strengths_and_weaknesses": "**Strength:**\n1. The proposed method significantly improves the computational efficiency of Fair SC.\n2. The algorithm is shown to be effective on both synthetic and real-world datasets.\n\n**Weakness:**\n1. There exists some other fair spectral clustering method, like [FEN24](https://www.mdpi.com/2073-8994/17/1/12), [ZHA24](https://www.sciencedirect.com/science/article/pii/S0925231224009810?casa_token=T6cg70BHqNAAAAAA:Ow9fzmBXvJE6p3Y5vmFyUPCA-35q3KdbX2BwaSI5b1kHxBGhlxRtZp_CmyxOrokXzyvdN9oO). [FEN24](https://www.mdpi.com/2073-8994/17/1/12) claims that they reach the same time complexity as this work. Could you add a more baseline method to this work for comparison to illustrate the strength of the proposed method.\n2. When the authors switch the problem 6 (traditional fair spectral clustering optimization problem) in the work to their proposed optimization problem, they made two changes:\n    - Use $M^2$ instead of $M$,\n    - Enforce fairness on $MH$ instead of $H$.\nCould you add some theoretical analysis to explain the feasibility of these two changes?\n3. This work could review more recent related work and discuss their limitations.\n4. The performance of spectral clustering and fairness looks worse than other methods.", "other_comments_or_suggestions": "Some suggestions about writing:\n1. For tables, the method with better numerical results could be highlighted.\n2. Since this work is related to clustering, some figures for clustering results would be necessary to illustrate the effectiveness of the proposed method to maintain the performance and fairness.\n3. Providing more details on the implementation of the proposed algorithm.\n4. Could further add theory to convergence rate analysis.", "questions_for_authors": "Please see weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uOm5YRFSu7", "reviewer": "Reviewer_ztMM", "summary": "- This paper proposes a computationally efficient algorithm for the fair spectral clustering problem.\n- The key of the proposed algorithm is the use of DC (Difference of Convex functions), which leads to the ADMM framework.\n- The authors claim that the proposed method is empirically faster than two existing algorithms, o-FSC and s-FSC.\n- The main distinction is that the proposed algorithm is based on gradient-based optimization, whereas the two existing algorithms rely on eigendecomposition routines.\n\n## update after rebuttal\n- Thank you for the clarifications. I will maintain my rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Q1. FacebookNet dataset\n\nTo address the reviewer's concern, we ran additional experiments on FacebookNet.\n\n**Table ztMM-1:** Clustering results on FacebookNet\n|#Clusters|Method|Time (s)|Balance|SC Cost|\n|---|---|---|---|---|\n|2|o-FSC|0.798|1.00|0.126|\n|2|s-FSC|0.193|1.00|0.126|\n|2|Ours|0.055|1.00|0.133|\n|25|o-FSC|9.908|0.84|14.114|\n|25|s-FSC|6.422|0.84|14.114|\n|25|Ours|0.131|0.84|14.128|\n|50|o-FSC|12.243|0.58|37.084|\n|50|s-FSC|11.558|0.58|37.084|\n|50|Ours|0.215|0.58|37.100|\n\n**These results further demonstrates the computational advantage of our method**, while achieving similar clustering quality to exact algorithms.\nWe tested on a new large-scale dataset in *Reply to Q4 of Reviewer jPJw*.\n> Q2. ADMM convergence.\n\nPlease refer to *Reply to Q1 of Reviewer 1h8o*. \n> Q3. Proof of Proposition 3.2.\n\nOur proof relies on the identification of $\\phi(MH)$ as $\\sup_{V} \\langle V, MH \\rangle - \\phi^\\star(V)$ which holds true as $H \\mapsto \\phi(MH)$ is convex. The infimum over $H$ is performed over the whole function $g(H) - \\phi(MH)$, explaining how we coupled the infimums over the different variables to go from (24) to (25). We will add parentheses to better highlight that the problem we are tackling is $\\inf_{H} \\left [ g(H) - \\sup_{V} \\langle V, MH \\rangle - \\phi^\\star(V) \\right ]$.\n\nThe equivalence between solving $\\inf_H g(H) + \\phi(MH)$ and $\\inf_V \\phi^\\star(V) - g^\\star(MH)$ is precisely the goal of Proposition 3.2. It was established in [Tonin et al. 2023] for the case of abstracts linear spaces and non-self-adjoint operators, the proof here follows a similar structure.\n> Q4. Balance interpretation.\n\nAs noted in [1], Problem (6) doesn't guarantee perfect balance in general. Enforcing it may degrade spectral objective ($Tr(H^\\top M H)$), so a trade-off is intrinsic to Fair SC.\n\nOur key contribution is a much faster algorithm for solving the *existing* Fair SC formulation. Fig. 2 shows our method achieves similar balance to the exact eigendecomposition, but does so substantially faster. Future work can explore regularizations to further improve balance.\n> Q5. Additional recent baselines and minimum balance.\n\nOur method follows the established line of work on fair SC, which enforces fairness via linear constraints in the embedding [1,2].\n- [Bera et al.] propose LP-based $k$-(means, median, center) clustering. Using their formulation in our work would ignore the RatioCut objective, resulting in suboptimal solutions wr.t. the spectral objective.\n- [Backurs et al.] use fairlets for prototype-based clustering.  However, extending the fairlet analysis, which relies on the $𝑘$-median and $𝑘$-center cost of the fairlet decomposition, to the spectral setting is not trivial. SC involves a spectral embedding step followed by a clustering in the embedding space, where reassigning points within a fairlet can significantly alter the spectral embedding and hence potentially violating fairness, making it non-trivial to incorporate their analysis in the fair SC case.\n\nThe primary contribution of our present work is to design a significantly faster method for the already established Fair SC problem defined in [1], rather than designing alternative fair clustering problems. Therefore, these baselines are not directly comparable w.r.t. problem scope and spectral solution quality. We agree that they offer valuable alternative perspectives on fairness in the more general clustering literature and we will discuss them in our Related Works section.\n\nFor balance, we follow [1,2] in reporting average balance, but also include minimum balance for Tab. 2 with $k=25$ per the reviewer’s suggestion.\n\n**Table ztMM-2:** Min balance\n|Dataset|Time (s-FSC)|Time (Ours)|Min. Balance (s-FSC)|Min. Balance (Ours)|\n|---|---|---|---|---|\n|LastFM|19.08|**4.59**|0.0027|0.0029|\n|Thyroid|30.49|**7.38**|0.0011|0.0012|\n|Census|136.60|**15.78**|0.0001|0.0001|\n|4area|166.92|**25.85**|0.1582|0.1517|\n\n> Q6. Theoretical complexity.\n\nComplexities of methods are:\n- o-FairSC: Computes null space ($O(nh^2)$) and eigendecomposition ($O((n-h)^3)$).\n- s-FairSC: Each eigensolver iteration costs $O(n^2+nh^2+nk^2)$, with the constant depending the Laplacian spectrum.\n- Ours: Dominated by matrix multiplications (applying $M$ to an $n \\times k$ matrix), with $O(n^2 k)$. Since $k \\ll n$, and modern libraries optimize this operation, we gain substantial practical speedups.\n\nThe improvement is therefore in the efficiency of the core operations. In fact, while for an $n \\times n$ matrix both matrix multiplication and matrix eigendecomposition have the same $n^3$ complexity, the former is much more efficient in practice. In the final version, we will add a separate paragraph on computational complexity detailing the above points.\n\n[1] Kleindessner et al. Guarantees for Spectral Clustering with Fairness Constraints  \n[2] Wang et al. Scalable Spectral Clustering with Group Fairness Constraints", "claims_and_evidence": "- Overall, the claims are supported by the experiments.\n- The gap between the theoretical and empirical complexities of s-FSC and the proposed algorithm could be discussed more thoroughly (see **Questions For Authors** below for details).", "methods_and_evaluation_criteria": "- Several experimental setups (e.g., metrics) are aligned with those used in existing methods.\n- The FacebookNet dataset was used in both Kleindessner et al. (2019) and Wang et al. (2023); however, this paper does not consider it.", "theoretical_claims": "- Theoretical convergence of the proposed algorithm\n   - While ADMM convergence is well-known for convex problems, as the authors mentioned, does the proposed ADMM with the fairness constraint also guarantee theoretical convergence?\n- Question about the proof of Proposition 3.2: \n   - In Eq. (24), $\\inf_{V}$ is applied to $-\\langle V, MH \\rangle$, where it appears that $H$ is not a variable with respect to the infimum operator. \n   However, in Eq. (25), $\\inf_{H, V}$ is applied to $-\\langle V, MH \\rangle$, and in Eq. (26), $\\sup_{H}$ is applied to $\\langle MV, H \\rangle$.\n   - How can the duality (or equivalence) be proven? Or, are these results well-established?", "experimental_designs_or_analyses": "- Questions about the comparison between s-FSC and the proposed method:\n   - Figure 2: For $k = 2$, neither s-FSC nor the proposed method appears to achieve high balance (0.2 for LastFMNet and over 0.5 for the 4area dataset), which is far from the perfect fairness (balance = 1). Can these results be considered fair?\n- Additional experiments/metrics would enhance the practical effectiveness of the proposed algorithm:\n   - Baselines: While the objective of the proposed algorithm aligns closely with those of o-FSC and s-FSC, given that the paper considers the spectral clustering for group fairness, it would be beneficial to compare it with other existing algorithms for group fairness. Examples are:\n      - Bera et al. (2019) https://proceedings.neurips.cc/paper_files/paper/2019/file/fc192b0c0d270dbf41870a63a8c76c2f-Paper.pdf, \n      - Backurs et al. (2019) https://proceedings.mlr.press/v97/backurs19a/backurs19a.pdf \n   - Metrics: - The average balance metric used is a relaxed version of the commonly adopted balance metric in the fair clustering literature, which is defined as the minimum of Eq. (3) over the cluster indices $l \\in [k]$. Computing the minimum balance would strengthen the experiment section of this paper.", "relation_to_broader_scientific_literature": "- The faster optimization can improve the practical applicability of the proposed algorithm in real-world.", "essential_references_not_discussed": "- Fairness in constrained spectral clustering (https://doi.org/10.1016/j.neucom.2025.129815)\n   - This work was very recently accepted. However, I believe the authors should at least conceptually compare their approach with this study.", "other_strengths_and_weaknesses": "- N/A", "other_comments_or_suggestions": "- N/A", "questions_for_authors": "- Complexity of s-SFC and the proposed algorithm:\n   - While Sections 2.2.2 and 3.2 claim that both s-FSC and the proposed algorithm theoretically have a complexity of $O(n^2)$, the experimental results indicate that the proposed algorithm significantly reduces computation time on real-world datasets. Can the authors explain why?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "- N/A"}}]

Author rebuttal:

Meta-review: This paper presents a new take on fair spectral clustering, with a focus on runtime/scalability.  The theory is solid and the experimental results are strong but can be expanded (see following).  This AC is broadly discounting reviewer jPJw’s very negative score because (i) some of the complaints just miss the point, e.g., Table 3 shows a baseline s-FSC compared against the proposed method with similar objective scores, but dramatically improved runtimes - that’s the point - and (ii) a lack of response to what I view as a comprehensive and convincing rebuttal on the authors’ part.  This AC does strongly suggest that the authors make the additional changes that iKL4, jPJw, and others bring up - that there are other spectral methods that would provide good baselines, and to compare against them, especially the ones with similar asymptotic runtimes as mentioned in iKL4’s review.  It’s great the authors already ran against FFSC in the rebuttal, with the same runtime lifts as in Table 3 against s-FSC, but for longer-term impact it’s always good to compare against the full slate of methods.
Decision: Accept (poster)