Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions
Authors: Shubham Gupta
Ambedkar Dukkipati
Venue: NeurIPS 2022 Accept (2022)
Keywords: Spectral clustering
fairness
constrained clustering
consistency

Abstract: Spectral clustering is popular among practitioners and theoreticians alike. While performance guarantees for spectral clustering are well understood, recent studies have focused on enforcing "fairness" in clusters, requiring them to be "balanced" with respect to a categorical sensitive node attribute (e.g. the race distribution in clusters must match the race distribution in the population). In this paper, we consider a setting where sensitive attributes indirectly manifest in an auxiliary representation graph rather than being directly observed. This graph specifies node pairs that can represent each other with respect to sensitive attributes and is observed in addition to the usual similarity graph. Our goal is to find clusters in the similarity graph while respecting a new individual-level fairness constraint encoded by the representation graph. We develop variants of unnormalized and normalized spectral clustering for this task and analyze their performance under a fair planted partition model induced by the representation graph. This model uses both the cluster membership of the nodes and the structure of the representation graph to generate random similarity graphs. To the best of our knowledge, these are the first consistency results for constrained spectral clustering under an individual-level fairness constraint. Numerical results corroborate our theoretical findings.

Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions
Shubham Gupta IBM Research Paris-Saclay
Ambedkar Dukkipati Computer Science and Automation Indian Institute Science, Bangalore, India. ambedkarGiisc.ed ac.
Orsay 91400, France. shubhang@iisc.acc ac.inn
Abstract
Spectral clustering is popular among practitioners and theoreticians alike. While performance guarantees for spectral clustering are well understood, recent studies have focused on enforcing "fairness" in clusters, requiring them to be "balanced" with respect to categorical sensitive node attribute (e.g. the race distribution in clusters must match the race distribution in the population). In this paper, we consider a setting where sensitive attributes indirectly manifest in auxiliary representation graph rather than being directly observed. This graph specifies node pairs that can represent each other with respect to sensitive attributes and is observed addition to the usual similarity graph. Our goal to find clusters in the similarity graph while respecting new individual-level fairness constraint encoded by the representation graph. We develop variants of unnormalized and normalized spectral clustering for this task and analyze their performance under fair planted partition model induced by the representation graph. This model uses both the cluster membership of the nodes and the structure of the representation graph generate random similarity graphs. To the best of our knowledge, these are the first consistency results for constrained spectral clustering under individual-level fairness constraint. Numerical results corroborate our theoretical findings.
Introduction
Consider a recommendation service that groups news articles by finding clusters in graph which connects these articles via cross-references. Unfortunately, cross-references between articles with different political viewpoints are uncommon, this service risks forming ideological filter bubbles. To counter polarization, it must ensure that clusters topies like finance and healthcare include a diverse range of opinions. This is an example of a constrained clustering problem. The popular spectral clustering algorithm [Ng et al. 2001 von Luxburg 2007 has been adapted over the years to include constraints such as must-link and cannot-link constraints Kamvar et al., 2003 Wang and Davidson, 2010), size-balanced clusters (Banerjee and Ghosh 2006), and statistical fairness [Kleindessner et al. 2019]. These constraints can be broadly divided into two categories: (i) Population level constraints that must be satisfied by the clusters as whole (c.g. size-balanced clusters and statistical fairness); and (ii) Individual level constraints that must be satisfied at the level of individual nodes (c.g. must/cannot link constraints). To the best of our knowledge, the only known statistical consistency guarantees for constrained spectral clustering were studied in Kleindessner et al. [2019) in the context of a population level fairness constraint where the goal is find clusters that are balanced with
respect to a categorical sensitive node attribute. In this paper, we establish consistency guarantees for constrained spectral clustering under a new and more general individual level fairness constraint.
"ork done while the author was at Indian Institute Science, Bangalore.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Informal problem description: We assume the availability of two graphs: a similarity graph G in which the clusters are to be found and a representation graph R. defined on the same set of nodes as G, which encodes the "is representative of"" relationship. Our goal is to find clusters in 9 such that every node has a sufficient number of its representatives from R in all clusters. For example, g may be a graph of consumers based on the similarity of their purchasing habits and R. may be graph based on the similarity of their sensitive attributes such as gender, race, and sexual orientation, This, for instance, would then be step towards reducing discrimination in online marketplaces [Fisman and Luca 2016].
Contributions and results: First, in Section 3.1 we formalize our new individual level fairness constraint for clustering, called the representation constraint. It is different from most existing fairness notions which either apply at the population level [Chierichetti et al. 2017 Rösner and Schmidt 2018 Bercea al. 2019 Bera et al. 2019] or are hard to integrate with spectral clustering [Chen et al.) 2019, Mahabadi and Vakilian [220 Anderson et al. 2020). Unlike these notions, our constraint can be used with multiple sensitive attributes of different types (categorical, numerical etc.) and only requires observing an abstract representation graph based on these attributes rather than requiring their actual values, thereby discouraging individual profiling. Appendix A discusses the utility of individual fairness notions.
Second, in Section 3.2 we develop the representation-cwwrrs variant of unnormalized spectral clustering to find clusters that approximately satisfy the proposed constraint. An analogous variant for normalized spectral clustering is presented in Appendix B.2.
Third, in Section 4.1 we introduce R-PP, a new representation-avye aware (or fair) planted partition model. This model generates random similarity graphs G conditioned on both the cluster membership of nodes and a given representation graph R. Intuitively, R-PP plants the properties of R in G. We show that this model generates "hard" problem instances and establish the weak consistency of our algorithms under this model for a class of d-regular representation graphs (Theorems 4.1 and 4.2p. To the best of our knowledge, these the first consistency results for constrained spectral clustering under an individual-leved constraint. In fact, we show that our results imply the only other similar consistency result (but for a population-level constraint) in Kleindessner al. 2019 as special case (Appendix A).
Pl
Finally, fourth, present empirical results on both real and simulated data to corroborate our theoretical findings (Section[5) (5.. In particular, our experiments show that our algorithms perform well in practice, even when the d-regularity assumption on R. is violated.
Related work: Spectral clustering has been modified satisfy individual level must-link and
cannot-link constraints by pre- pre-processing the similarity graph Kamvar et al. 2003]. post-processing the eigenvectors of the graph Laplacian [Li et al. 2009]. and modifying its optimization problem (Yu
and Shi, 2001 2004 Wang and Davidson 2010 Wang et al., 2014 Cucuringu et al., 2016). It has also been extended to accommodate various population level constraints [Banerjee and Ghosh| 2006 Xu et al.] 2009]. We are unaware of theoretical performance guarantees for any of these algorithms.
Of particular interest to us the fairness constraints for clustering. One popular population level constraint requires sensitive attributes to be proportionally represented in clusters [Chierichetti et al..
2017 Rösner and Schmidi 2018 Bercea et al. 2019 Bera et al. 2019 [smaeili et al. 20200 2021]
For example, if 50% of the population is female then the same proportion should be respected in all clusters. Several efficient algorithms for discovering such clusters have been proposed [Schmidt ct al. 2018 Ahmadian et al. 2019 Harb and Shan 2020], though they almost exclusively Tocus on variants of k-means while we are interested in spectral clustering. [leiidesssner et al. 2019 deserve
a special mention as they develop a spectral clustering algorithm for this fairness notion. However, we recover all the results presented in Kleindessser et al. [2019] as a special case of our analysis as our proposed constraint interpolates between population level and individual level fairness based on
the structure of R. While individual fairness notions for clustering have also been explored [Chen
et al.] 2019 Mahabadi and Vakilian [020] Anderson et al. 2020) Chakrabarty and Negahbani] [021]
none of them have previously been used with spectral clustering. See Caton and Haas 2020 for
broader discussion on fairness.
2 An algorithm is called weakly consistent if it makes o(N) mistakes with probability 1 1- o(1). where N is the number of nodes in the similarity graph G [Abbe] 2018

---

A final line of relevant work concerns consistency results for variants of unconstrained spectral clustering. yon Luxburg al. (2008] established the weak consisteney of spectral clustering assuming that the similarity graph G encodes cosine similarity between examples using feature vectors drawn from a particular probability distribution. |Rohe al. [201T) Lnd and Rinaldo (2015) assume that G is sampled from variants of the Stochastic Block Model (SBM) [Holland et al. 1983] Zhang et al. [2014) allow clusters to overlap. [Binkiewizz et al. [2017] consider auxiliary node attributes, though, unlike us, their aim is to find clusters that are well aligned with these attributes. A faster variant of spectral clustering was analyzed by Tremblay et al. [2016]. Spectral clustering has also been studied on other types of graphs such hypergraphs [Ghoshdastidar and Dukkipati
201 7a bJ and strong
consistency guarantees are also known [aoo et 2017 and Zhu 2017 stronger assumptions.
Vu 2018 albeit under
Notation: Define [n] = {1, ....., } for any integer n. Let G = E)) denote a similarity graph. where V = {e1, 0....., UN } is the set of N nodes and & S V x V is the set of edges. Clustering aims to partition the nodes in 9 into K 2 2 non-overlapping clusters Cı..... ..,........ Cx V. We assume the availability of another graph, called representation gruph R = (V,8), which is defined on the same set of vertices as 9 but with different edges E. The discovered clusters .I..... Cx are required to satisfy fairness constraint encoded by R, described in Section 3.1 A, R {0, 1) ||NxNN denote the adjacency matrices of graphs G and R. respectively. We assume that G and R are undirected and that G has self-loops.
2 Unnormalized spectral clustering
We begin with brief review of unnormalized spectral clustering which will be useful in describing our algorithm in Section 3.2 The normalized variants of traditional spectral clustering and our algorithm have been deferred Appendix B. Given similarity graph G. unnormalized spectral clustering finds clusters by approximately minimizing the following metric known as ratio-cut [von Luxburg 2007
Cut(C, V.C.))
RCu((C,,..,Ck)= E
|C,1
Here, VMC, is the set difference between and C.. For any two subsets X, C V, Cut(x y) = Ex Ai counts the number of edges that have one endpoint in X and another in V. Let
D E NNN be diagonal degree matrix where D;: Eÿ= Ar for all i E [NV. It is easy to verify that ratio-cut can be expressed in terms of the graph Laplacian L = D - A and cluster membership matrix H NXXK as RCuu(C Cx) = trace( ( HHLH)), where
E
Hij
(1)
otherwise.
Thus, to find good clusters, one can minimize trace (rT [HL over all H that have the form given in T However, the combinatorial nature of this constraint makes this problem NP-hard [Wagner and Wagner 1993]. Unnormalized spectral clustering instead solves the following relaxed problem:
min НеR
(Hace(H"LIK s.t. H I.
Note that H in ( satisties HTH I. The above relaxation is often referred to the spectral relaxation. By Rayleigh-Ritz theorem [Lütkepoh]] 1996. Section 5.2.2], the optimal matrix H" is such that it has u1, u2....., ux NNN as its columns, where u, is the eigenvector corresponding to the tth smallest eigenvalue of L for all E []] The algorithm clusters the rows of H" into K clusters using k-means clustering [Lloyd 1982] to return Ci...., Cx.
Algorithm I procedure. Unless stated otherwise, we will use spectral clustering (without any qualification) refer to unnormalized spectral clustering.
summarizes this
3 Representation constraint and representation-aware spectral clustering
In this section, we first describe our individual level fairness constraint in Section 3.1 and then develop Unnormalized Representation-Awar Spectral Clustering Section 3.2 to find clusters that approximately satisfy this constraint. See Appendix B for the normalized variant of the algorithm.
3

---

Algorithm Unnormalized spectral clustering
1: Input: Adjacency matrix A, number of clusters K 2
2: Compute the Laplacian matrix L D A.
3: Compute the first K eigenvectors u ... uk of L. Let H E R be matrix that has
UI....: ug as its columns.
4: Let hy denote the jth row of H Cluster hi,..., hy into K clusters using k-means clustering.
5: Output: Clusters C,,...,Ck CK. s.t. C, = {uz E V: h3 was assigned to the 7th cluster).
3.1 Representation constraint
A representation graph R connects nodes that represent each other based sensitive attributes (e.g- political opinions). Let Let.Nx = {oy R5 = =1} be the set of neighbors of node U; in R. The size of (t) n C& specifies node representation in cluster Cg. To motivate constraint, consider the following notion of balance μ3 of clusters defined from the perspective of a particular node ez:
ICe (& [Ce ((x)
P:
min K
It is easy to see that 0 < P. < representation in all clusters. Thus, one objective could be find clusters CI....CCp CK that solve the following optimization problem.
1 and higher values of p; indicate that node it has an adequate
min Cre,,CC
[(CI,...,Ck) s.t. A 2 [iE[N]
where f(-) is inversely proportional to the quality of clusters (such as RCut) and E [0, is user specified threshold. However, is not clear how this approach can be combined with spectral clustering to develop consistent algorithm. We take different approach described below.
First, note that mi] P ming,e[[K]
[Cxl
Therefore, the balance P: of the least balanced node [C
v is maximized when its representatives Ni) are split across clusters C .C. in proportion to their sizes. Representation constraint requires this condition to be satisfied for each node in the graph.
Definition 3.1 (Representation constraint). Given a representation graph R. clusters Ci...., Cx in satisfy the representation constraint if [C& n (&x x |C& for all E [N] and le E [K], iee.
CCx (N)(t)) [Nx (i) vk E [K], vi [N].
Cxl
In other words, the representation constraint requíres the representatives of any given node to have a proportional membership in all clusters. For example, if i is connected to 30% of all nodes in R. then it must have 30% representation all clusters discovered in G. It is important to note that this constraint applies at the level of individual nodes unlike population level constraints [Chierichetti et al. 2017].
While can always be solved for a small enough value of a (with the convention that 0/0 = 1), the constraint Definition 3.1 may not always be feasible. For example, (5) can never be satisfied node has only two representatives (i.e., (i) 2) and there are K >> 2 clusters. However, as exactly satisfying constraints clustering problems is often NP-hard [Davidson and Ravi 2005), most approaches look for approximate solutions. In the same spirit, our algorithms use spectral relaxation to approximately satisfy (5) ensuring their wide applicability even when exact satisfaction is impossible.
In practice, R can be obtained by computing similarity between nodes based on one or more sensitive attributes (say by taking k-nearest neighbors). These attributes can have different types opposed to existing notions that expect categorical attributes (Appendix A). Moreover, once R has been calculated, the values of sensitive attributes need not be exposed to the algorithm, thus adding privacy. Appendix A presents a toy example to demonstrate the utility individual level fairness and shows that (5) recovers the population level constraint from Chierichetti et al. [2017) and Kleindessner et al. 2219 for particular configurations of R, thus recovering all results from Kleindessner et al. 2019 special case of our analysis.

---

Finally, while individual fairness notions have conventionally required similar individuals to be treated similarly (Dwork et al. 2012), our constraint requires similar individuals (neighbors in R) to be spread across different clusters (Definition 3.T). This new type of individual faimess constraint may be of independent interest to the community. Next, we describe one of the proposed algorithms.
3.2 Unnormalized representation-awarr spectral clustering (UREPSC)
The lemma below identifies a sufficient condition that implies the representation constraint and can be added to the optimization problem (2) solved by spectral clustering. See Appendix E for the proof.
Lemma 3.1. Let H E B have the form specified in
The condition
R ( (I- 11 H
(6)
implies that the corresponding clusters Ci....,Ca CK satisfy the constraint in 5 Here, I the N N identity matrix and 1 is a N-dimensional all-ones vector.
With the unnormalized graph Laplacian L defined in Section 2 we add the condition from Lemma 3.1 to the optimization problem after spectral relaxation in (2) and solve
min H
trace HTLH)
S.L. - R
R(I
2I--117
H= = O. N 11
Clearly, the columns of any feasible H must belong the null space of R(I 11 //). Thus, any feasible H can be expressed as H = YZ for some matrix Z E R N- where Y E IR NNN-- an orthonormal matrix containing the basis vectors for the null space of R(I 11 NN) as its columns. Here, is the rank of R(I 11T/N), Because Y I. H Z = Z'Z.
Thus, H + ZTZ I. The following problem is equivalent to by setting YZ.
min Z
trace (Z
s.t. ZZ =1
(8)
As in standard spectral clustering, the solution to 8 is given by the K leading eigenvectors of YTLY. Of course, for K eigenvectors to exist, N must be at least K YTLY has dimensions N - x- N r. The clusters can then be recovered by using k-means clustering to cluster the rows of H = YZ, in Algorithm [ Algorithm summarizes this procedure. We refer to this algorithm as unnormalized representation-avve aware spectral clustering (UREPSC). We make three important remarks before proceeding with the theoretical analysis.
Remark (Spectral relaxation). As R[- BR(I-11T/MD 11T/N) O implies the satisfaction of the representation constraint only when H has the form given in ( feasible solution to (7) may not necessarily result in representation-cri cawirre clusters. In fact, even in the unconstrained case, there are no general guarantees that bound the difference between the optimal solution of ? and the original NP-hard ratio-cut problem Kleindessner et al.) 2019]. Thus, the representation-avie discovered by solving (8) cannot be guaranteed in general (as is the case with [Kleindessner et al. 2019). Nonetheless, we show in Section that the discovered clusters indeed satisfy the constraint under certain additional assumptions.
nature the clusters
Remark (Computational complexity). Algorithm 2 has time complexity of O(N3) and space complexity of ((N2). Finding the null space of RI 11T /N) calculate Y and computing the eigenvectors of appropriate matrices are the computationally dominant steps. This matches the worst-case complexity of Algorithm| []] For small K, several approximations can reduce this
complexity, but most such techniques require K YYu and Shi 2004 Xu et al. 2009].
K to ensure the existence of K orthonormal eigenvectors of YTLY. When graph violates this assumption, we instead use the best rank R approximation of its adjacency matrix R (R < N K) and refer to this algorithm as UREPSC (APPROX.). ). This approximation of R need not have binary elements, but it works well in practice (Section 5). Appendix C provides more intuition behind this low rank approximation, contrasts this strategy with clustering to recover latent sensitive groups that can be reused with existing population level notions, and highlights the challenges associated with finding theoretical guarantees for UREPSC (APPROX.), which is an interesting direction for future work.
Remark 3 (Approximate UREPSC). Aggorthhmrreqg requires rank R S N-K
5

---

Algorithm 2 UREPSC
1: Input: Adjacency matrix A, representation graph R. number of clusters K 2 2
2: Compute Y containing orthonormal basis vectors of aull(Ri N 111))
3: Compute Laplacian L =
4: Compute leading K eigenvectors of YILY. Let contain these vectors as its columns.
5: Apply k-means clustering to rows of H = YZ to get clusters C2, C,
6: Return: Clusters C₁, Cr,c2....,CK
Analysis
This section shows that Algorithms 2 and 4 (see Appendix B) recover ground truth clusters with high probability under certain assumptions on the representation graph. We begin by introducing the representation-awarl planted partition model in Section[4.]
4.1
R-PP model
The well known Planted Partition random graph model independently connects two nodes in V with probability p if they belong the same cluster and q otherwise, where the ground truth cluster memberships are specified by function π V + [K]. Below, we define a variant of this model with respect to representation graph R and refer as the Representation-Awee (or Fair) Planted Partition model or R-PP..
Definition 4.1 (R-PP), A R-PP is defined by the tuple (T, R, p. qr s). where π V - [K] maps nodes in clusters, R. is a representation graph, and 2 p 2 q r used for sampling edges. Under this model, for all i > j.
2 0 are probabilities
p if (vy) and R.j 1,
Q ifz(u;) # T(1z) and Ruj = 1,
P(Ay
r if = ((0) and Rij = 0,
if # (Uy) and Raj = O.
Similarity graphs G sampled from R-PP have two interesting properties: (i) Everything else being equal, nodes have a higher tendency of connecting with other nodes in the same cluster (p 2 9 and r 2 s); and (ii) Nodes connected in R have a higher probability of connecting in G (p 2 r and q 2 8). Thus, R-PP plants both the clusters æ and the properties of R. into the sampled graph G. Remark 4 (R-PP and "hard" problem instances). Clusters satisfying (5) must proportionally distribute the nodes connected in R amongst themselves. However, R-PP makes nodes connected in R more likely to connect in G. even if they belong to different clusters (q 2 r). In this sense, graphs sampled from R-PP are "hard" instances for our algorithms.
When R itself has latent groups, there two natural ways to cluster the nodes: (i) Based the clusters specified by π: and (ii) Based on the clusters in R. The clusters based on option (ii) are likely not satisfy (5) as tightly connected nodes in R will be assigned the same cluster. We show in the next section that, under certain assumptions, can be defined so that the clusters encoded by satisfy (5) by construction. Recovering these ground truth clusters (instead of other natural choices like option (ii) then amounts to recovering representation-avvenn -aware clusters.
4.2 Consistency results
As noted in Section some representation graphs lead to constraints that cannot be satisfied. For our theoretical analysis, we restrict our focus to case where the constraint in is feasible. Towards this end, an additional assumption on is required.
Assumption 4.1. R is a d-regular graph for K S S N. Moreover, R4; for all e [N] and each node in R is connected to d/ K nodes from cluster for all j E [K] (including the self-loop).
Assumption ensures the existence of n for which the ground-truth clusters satisfy (5). Namely, assuming equal-sized clusters, set (v.)) k if 1) N < i < NN for all E [N] and l [K].

---

Before presenting our main results, we need additional notation. Let @ E [0,1) indicate the ground-truth cluster memberships encoded by (i.c., O2 = + i C2) and é {0, 1J indicate the clusters returned by the algorithm (Q.g 1 + i E C With J as the set of all x K permutation matrices, the fraction of misclustered nodes is defined as M( é) - minjer I @J [Lei and Rinaldo, 2015]. Theorems 4.1 and 4.2 use the eigenvalues of the Laplacian matrix in the expected case, dehned as D AA, where A E[A] is the expected adjacency matrix of a graph sampled from R-PP and D E TRNx is its corresponding degree matrix. The next two results establish high- probabillty upper bounds on the fraction of misclustered nodes for UREPSC and NREPSC (see Appendix B) for similarity graphs & sampled from R-PPP.
Theorem 4.1 (Error bound for UREPSC), Let [ank[R) S. N - K and assume that all clusters have equal sizes. Let μi S H12 - .... S pN-+ denote the eigenvalues of YTLY, where was defined in Section 3.2 Define Y MK+1 иg. Under Assumption 4.7 there exists universal constant
const C, 0). such that if y satisfies 72 z const(C, c)p. K N and p Z C'nN/N for
some C 0, then
(2 + c)
M θ) consu(C,
NN
72
for every e O with probability least 1 2N when a (1 + apprrxxmmmete algorithm for k-means clustering is used in Step 5 of Algorithm 2
Theorem 4.2 (Error bound for NREPSC). Let [ank S N K and assume that all clusters have equal sizes. Let P1 S 122 .... IN- denote the eigenvalues of -- YYLLY Q- where
Q YTDY and Y was defined in Section 3.2 Define y = MK+1 Pk and x qd s(N d) (p 9) a) + (r 8) N-d. Under Assumption 4.1 there are universal constants (o,st,(C,,a)
const (C, a),, and consta (C,a) such that if:
1.
N A1-P
VpNin I
x1-
+
OVC)
Io(a+1y'
2. A1-P
N
< const2 (C,a), a). and
Bronsts(Gaa\V/ + +cnstt (C,a)
"N In N [A1-p}² <
3. 16(2 cc)
K
and p 2 C'In N/N for some O, then,
(consts(C,a))VK const, (C, (C)
1² PN In
M(O, ① - 32(2 +c)
p)1-
?
for every e O with probability least 2N when a (1 + approxxmatte algorithm for k-means clustering is used in Step 6 of Algorithm 4.
All proofs have been deferred to Appendix D. Briefly, we show that the top K cigenvectors of L (i) recover ground-truth clusters in the expected case (Lemmas D.I to D.3) and (ii) lie in the null space of R(I - 11T/NV and hence are also the top K eigenvectors of LT (Lemma D.4). Matrix perturbation arguments then establish a high probability mistake bound in the general case when the graph 9 is sampled from a R-PP (Lemmas D.5. Next, we discuss our assumptions and use the error bounds above to establish the weak consistency of our algorithms.
4.3 Discussion
Note that I I- 11T / is a projection matrix and is its eigenvector with eigenvalue 0. Any vector
orthogonal to 1 is an eigenvector with eigenvalue 1. Thus, rank [ N - 1. Because rank/R
that Lank/R(E / < min(rank(R)) R.nk Iank([I-11/NV])) (1T N K, which is necessary for (8) to have a solution. The assumption
requiring rank(R) S N - ensures
on the size of the clusters and the d-regularity of R allows us to compute the smallest K" eigenvalues of the Laplacian matrix in the expected case. This is crucial step in our proof.
In Theorem 4.2 X defined such that the largest eigenvalue of the expected adjacency matrix under the R-PP model is given by \ (see (15) and Lemma D.2). The three assumptions in
7

---

USC
UPa
USC
UFasC
USC UsepSC
Uharsc
URapSC
LResSC
Utep52
UbppS (eppmed
Uleefi Heprec)
Accuracy vs Nodes
Accuracy #Clustors
Accuracy vs Degree
0.8
0.8
0.6
0.6
0.2
750 1000
1520
1750
40
BG
120
Degree
Dogres
<hodaz; DDggrs:: Rank LReeSC 0.1N aGroups ffor UFaISC) 0.3N
&'lustrrs der UieeSr 6:1N #Grougs ffor UFairCc 9.1N
Rank LReeSi Jeppree 1t: #Groups ter uFairsc): 0.IN
(a) Accuracy no. of nodes
(b) Accuracy vs of clusters
(c) Accuracy vs degree of R.
Figure I: Comparing UREPSC with other "unnormalized" algorithms using synthetically generated
d-regular representation graphs.
Theorem 4.2 essentially control the minimum rate at which A must grow with N. For instance, the first two assumptions can be replaced by a simpler but slightly stronger (yet practical) condition: A1 P- w( VpN In N).. This, for example, is satisfied in realistic setting where K OIn N) and d = (In N). The third assumption also controls the rate of growth of A1, but in the context of the community structure contained in Q YYT LY not increase at the expense of the community structure (e.g.. by setting p = 9 = =
encoded by the eigengap 7. So, X1 must 1).
Remark 5. In practice, Algorithms 2 and 4 only require the rank assumption on R to ensure the feasibility of the corresponding optimization problems. The assumptions on the size of clusters and d-regularity of R. are only needed for our theoretical analysis.
The next two corollaries establish the weak consistency of our algorithms as a direct consequence of Theorems 4.1 and|4.2
Corollary 4.1 (Weak consistency of UREPSC). Under the same setup as Theorem 4.1 for UREPSC, M θ o(1) with probability o(1) i w( w(vpNK Nn..
Corollary 4.2 (Weak consistency of NREPSC). Under the same setup as Theorem 4.2 for NREPSC, M(O, +) o(1) with probability 1 o(1) i w(VpNK In N/ /(11 P)).
The conditions on y are satisfied in many interesting cases. For example, when there are P protected groups in Chierichetti et al. [2017), the equivalent representation graph has P cliques that not connected to each other (see Appendix A). Kleindessner et al. [2019] show that y = (NN K) in this case (for the unnormalized variant), which satisfies the criterion given above if K is not too large.
Finally, Theorems 4.1 and 4.2 require a (1 + appprxximae solution to k-means clustering. Several efficient algorithms have been proposed in the literature for this task [Kumar et al. [2044] Arthur and Vassilvitskii] 2007 Ahmadiaa et al. 2017]. Such algorithms are also available in commonly used software packages like MATLAB and scikit-learf The assumption that p 2 C In N/N controls the sparsity of the graph and is required in the consistency proof' for standard spectral clustering as well [Lei and Rinaldo 2015).
5 Numerical results
We experiment with three types of graphs: synthetically generated d-regular and non-d-regular representation graphs and real-world dataset. See Appendix F for analogous results for NREPSC, the normalized variant of our algorithm. Before proceeding further, we make an important remark.
Remark 6 (Comparison with Kleindessner et al. (019).. We refer to the unnormalized variant of the algorithm in Kleindessner et al. [2019] as UFAIRSC. assumes that each node belongs to one the P protected groups Pl..... Pp V that are observed by the learner. UREPSC recovers UFAIRSC as a special case when R is block diagonal (Appendix A). To demonstrate the generality of UREPSC,
'The algorithm in Kumar et al. [2004] runs in linear time in N only when K is a constant. When K grows with N. one can instead use other practical variants whose average time complexity is linear in both N and K (e.g.. in scikit-learn) These variants often run with multiple seeds in practice to avoid local minima.
8

---

(mppes))
USC
UPaiSC
URepSC (sporx))
#Nodes: 1000, #Clusters: 4, #Groups: 5
1+
1000, @lusters: @Groups
Betence Wertte/BeettCCC
1.25
1.00
0.75
030
025
0.0
10
160
250
300
4.0
550
600
700
800
950
10
100
200
300
400
500
600
700
800
900
Protected groups (PS
UFarISc
Protected groups (P)
UFaiSSc
(eporos.)
Craph
(apprisc)
(a) N = 1000, K =
(b) N 1000, K = 8
Figure 2: Comparing UREPSC (APPROX.) with UFAIRSC using synthetically generated representa- tion graphs sampled from an SBM.
UtaiSC
UltepSC (eporox.)
UneirSc:
UltepSC (eporos.)
Number Clusters:
Number of Clusters:
1.0
0.8
0.6-
0.4
0.2
40
130
160
120 3440
1800
Pank of Represontation Graph (R) URapSC (apprxx)
Rank of Represe Graph (R) URadSC topprox.)
(a)
(b)
Figure 3: Comparing UREPSC (APPROX.) with UFAIRSC on FAO trade network.
we only experiment with R's that block diagonal. As UFAIRSC directly applicable in this setting, to compare with it, we approximate the protected groups by clustering the nodes in R using standard spectral clustering. Each discovered cluster then treated protected group (also see Appendix C).
d-regular representation graphs: We sampled similarity graphs from R-PP using = 0.4, q = 0.3, r 0.2. and 0.1 for various values of d, N,, and K, while ensuring that the underlying R satisfies Assumption 4.1 and rank(R} < N - k. Figure | compares UREPSC with unnormalized spectral clustering (USC) (Algorithm) T and UFAIRSC. Figure Ta shows the effect varying for fixed d = 40 and K = 5. Figure 1b varies K and keeps N = 1200 and d = 40 fixed. Similarly, Figure Tc keeps N 1200 and K = fixed and varies d. all cases, we use R P = N/10. The figures plot the accuracy y-axis and report the mean and standard deviation across 10 independent executions. As the ground truth clusters satisfy Definition 3.1 by construction, a high accuracy implies that the algorithm returns representation-aveen USC will return representation-an aware clusters for a large enough graph. However, this is not true the number of clusters increases with N (Figure lb is common in practice.
clusters. In Figure la it appears that even
Representation graphs sampled from planted partition model: We divide the nodes into P protected groups and sample a representation graph R using a (traditional) planted partition model with within (resp. across) protected group(s) connection probability given by Pin 0.8 (resp. Pout = 0.2). Conditioned on R. we then sample similarity graphs from R-PP using the same parameters before. We only experiment with UREPSC (APPROX.) violate the rank assumption. Moreover, because such an R may not be d-regular, high accuracy no longer implies representation awareness, and instead report the ratio of average individual balance -= Σi P: (see 33) to the value of RCut. Figure 2 Higher values indicate high quality clusters that are also balanced from the perspective of individuals. shows trade-off between accuracy representation awareness. One can choose an appropriate value R UREPSC (APPROX.) ) to get good quality clusters with high balance.
R. generated this way may

---

The FAO trade network from United Nations is multiplex network with 214 nodes representing countries and 364 layers representing commodities like coffee and barley (Domenico et al. 2015 Edges corresponding to the volume of trade between countries. We connect each node to hive nearest neighbors in each layer and make the edges undirected. The first 182 layers are aggregated to construct R (connecting nodes that are connected in at least one layer) and the next 182 layers are used for constructing G. Note that R constructed this way is not d-regular. To motivate this experiment further, note that clusters based only on G only consider the trade of commodities 183-364. However, countries also have other trade relations in R, leading to shared economic interests. If the members of each cluster jointly formulate their economic policies, countries have an incentive to influence the economic policies of all clusters by having their representatives in them.
A real-world network:
As before, we use the low-rank approximation for the representation graph UREPSC (APPROX.) Figure (aaure]@coppreee UREPSC (APPROX.) with UFAIRSC and has the same semantics as Figure Different plots in Figure correspond different choices of K. UREPSC (APPROX.) achieves a higher ratio of average balance to ratio-cut. In practice, user would choose R by assessing the relative importance a quality metric like ratio-cut and representation metric like average balance.
Appendix F contains results for NREPSC, experiments with another real-world network, a few additional experiments related UREPSC, and a numerical validation of our complcoty analysis. Appendix G contains plots that show both average balance and ratio-cut instead of their ratio.
Conclusion
We studied the consistency of constrained spectral clustering under new individual level fairness constraint, called the representation constraint, using a novel R-PP random graph model. Our work naturally generalizes existing population level constraints [Chierichetti et al., [217]] and associated spectral algorithms [Kleindessner et al. 2019]. Four important avenues for future work include (i) the relaxation of the d-regularity assumption in analysis (needed to ensure representation awareness ground-trun truth clusters), (ii) better theoretical understanding of UREPSC (APPROX.), )) (iii) improvement of the computational complexity of our algorithms, and (iv) exploring relaxed variants of our constraint and other (possibly non-spectral) algorithms for finding representation-zun aware clusters under such a relaxed constraint.
Acknowledgments and Disclosure of Funding
The authors would like to thank the Science and Engineering Research Board (SERB), Department of Science and Technology, Government of India, for their generous funding towards this work through the IMPRINT project: IMP/2019/000383. The authors also thank Muni Sreenivas Pydi for reviewing the manuscript and providing valuable suggestions.
References
Emmanuel Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018.
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. Symposiun on Foundations of Computer Science, 2017.
Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representatioo. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 267-275. 2019.
Nihesh Anderson, Suman K. Bera, Syamantak Das, and Yang Liu. Distributional individual fairness in clustering. arXiv, 2006. 12589, 2020.
David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. Symposium Discrete Algorithms, 2007.
10

---

Arindam Banerjee and Joydeep Ghosh. Scalable clustering algorithms with balancing constraints. Data Mining and Knowledge Discovery, 13:365-395, 2006.
Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32:4954 4965, 2019.
Ioana O. Bercea, Martin Gross, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. APPROX-RANDOM, pages 18:1-18:22, 2019.
Norbert Binkiewicz, Joshua T. Vogelstein, and Karl Rohe. Covariate assisted spectral clustering. Biometrika, 104(2):311-377, 2017.
Alessio Cardillo, Jesús
Massimiliano Zanin, Miguel Romance, David Papo, Francisco del Pozo, and Stefano Boccaletti. Emergence of network features from multiplexity. Scientific Reports, 3(1344), 2013.
Simon Caton and Christian Haas. Fairness in machine learning: A survey. arXiv, 2010.04053, 2020.
Deeparnab Chakrabarty and Maryam Negahbani, Better algorithms for individually fair k-clustering. Advances in Neural Information Processing Systems, 34, 2021.
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In Proceedings of the 36th International Conference on Machine Learning, 97:1032- 1041, 2019.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30:5029-5037, 2017.
Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, and Richard Peng. Simple and scalable constrained clustering: A generalized spectral method. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 41:445-454, 2016.
Ian Davidson and S. S. Ravi. Clustering with constraints: Feasibility issues and the k-means algorithm. In Proceedings of the 5th SIAM Data Mining Conference, pages 138-149, 2005.
Manlio De Domenico, Vincenzo Nicosia, Alexandre Arenas, and Vito Latora. Structural reducibility of multilayer networks. Nature Communications, 6(1), 2015.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. ITCS '12, pages 214-226,, 2012.
Seyed Esmaeili, Brian Brubach, Aravind Srinivasan, and John Dickerson. Probabilistic fair clustering. Advances in Neural Information Processing Systems, 33, 2020.
Seyed Esmaeili, Brian Brubach. Aravind Srinivasan, and John Dickerson. Fair clustering under bounded cost. Advances in Neural Information Processing Systems, 34, 2021.
Ray Fisman and Michael Luca. Fixing discrimination in online marketplaces. Harvard Business Review, December 2016, 2016
Chao Gao, Zongming Ma, Anderson Y. Zhang, and Harrison H. Zhou. Achieving optimal misclassifi- cation proportion in stochastic block models. Journal of Machine Learning Research, 18:1-45, 2017.
Debarghya Ghoshdastidar and Ambedkar Dukkipati. Consistency of spectral hypergraph partitioning under planted partition model. Annals of Statistics, 45(1):289-315, 2017a.
Debarghya Ghoshdastidar and Ambedkar Dukkipati. Uniform hypergraph partitioning: Provable tensor methods and sampling techniques. Journal of Machine Learning Research, 18(1):1638-1678, 2017b.
Ellarouk Harb and Lam Ho Shan. Kfc: A scalable approximation algorithm for k-center fair clustering. Advances in Neural Information Processing Systems, 33, 2020.

---

Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109-1377 1983.
Sepandar D. Kamvar, Dan Klein, and Christopher D. Manning, Spectral learning. In Proceedings of the 18th International Joint Conference on Artificial Intelligence, pages 561-566, 2003.
Matthäus Kleindessner, Samira Samadi, Pranjal Awasthi, and Jamie Morgenstern. Guarantees for spectral clustering with faireess constraints. In Proceedings of the 36th International Conference on Machine Learning, 97:3458-3405 3467,,344,,,111 2019.
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A simple linear time (1 apappooxxiationn algorithm for k-means clustering in any dimensions. Symposium on Foundations of Computer Science, 2004.
Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, 43(1):215-237, 2015.
Jing Lei and Lingxue Zhu. A generic sample splitting approach for refined community recovery in stochastic block models. Statistica Sinica, 27(4):1639-165, 2017.
Zhenguo Li, Jianzhuang Liu, and Xiaoou Tang. Constrained clustering via spectral regularization. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 421-428, 2009.
Stuart P. Lloyd. Least squares quantisation in pem. IEEE Transactions on Information Theory, 28(2): 129-137, 1982.
Helmut Lütkepohl. Handbook of matrices. Wiley, 1996.
Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering, In Proceedings of the 37th International Conference on Machine Learning. 111658666966 2020.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm.
Advances in Neural Information Processing Systems, 14, 2001.
Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the figh-dimensional stochastic blockmodel. The Annals of Statistics, 39(4):1878-199) 2011.
Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. ICALP, 2018.
Melanie Schmidt, Chris Schwiegelshonn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means clustering. arXiv, 1812.10854 2018.
Nicolas Tremblay, Gilles Puy, Remi Gribonval, and Pierre Vandergheynst. Compressive spectral clustering. In Proceedings of The 33rd International Conference on Machine Learning. 48: 1011-1011, 2016.
Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395 2007.
Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, 36(2):555-588 2008.
Van Vu. A simple svd algorithm for finding hidden partitions. Combinatories, Probability and 2018.
Computing,
Vincent Q Vu and Jing Lei. Minimax sparse principal subspace estimation in high dimensions. The Annals of Statistics, 2116))2905-9947 2013.
Dorothea Wagner and Frank Wagner. Between min cut and graph bisection. Mathematical Founda- tions of Computer Science, 111:744-550) 1993.
Xiang Wang and Ian Davidson. Flexible constrained spectral clustering. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 563-572, 2010.
12

---

Xiang Wang, Buyue Qian, and lan Davidson. On constrained spectral clustering and its applications.
Data Mining and Knowledge Discovery, 28:1-30, 2014.
Linli Xu, Wenye Li, and Dale Schuurmans. Fast normalized cut with linear constraints. IEEE Conference Computer Vision and Pattern Recognition, 2009.
Stella X. Yu and Jianbo Shi. Grouping with bias. Advances in Neural Information Processing Systems, 14:1327-1334, 2001.
Stella X. Yu and Jianbo Shi. Segmentation given partial grouping constraints. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):173-183, 2004.
Yuan Zhang, Elizaveta Levina, and Ji Zhu. Detecting overlapping communities in networks using
spectral methods. SIAM Journal on Mathematics of Data Science, 2(2):265-283, 2014.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section 3.] for the new faireess constraint, Sec- tion 3.22 and appendix B.2 for the algorithms, Section 4.1 for the new random graph model, Sections 4.2 and 4.3 3 for consistency results, and Section 5 and appendix F for numerical results.
(b) Did you describe the limitations of your work? [Yes] See Remarks | to where discuss issues with spectral relaxation, computational complexity, and lack of theoretical guarantees for the approximate variant of our algorithms. Also see Section 6
(c) Did you discuss any potential negative societal impacts of your work? [No] Our algorithms are intended learn more "fair" clusters. While one can argue about the definition of fairness itself, within the context of this work, we do not see a negative societal impact if the algorithms are used intended.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tion 4.1 and Theorems 4. and 4.2
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix D
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Code submitted as supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? (Yes) See the description of experiments in Section
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [Yes] A careful look at the plots shows that error bars present, though the variation is very small.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No] The experiments were run on standard desktop and did not require any specialized hardware.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We have added an appropriate reference for the FAO Trade Network. No code from outside sources was used.
(b) Did you mention the license of the assets? [N/A]
13

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' roure using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "WBCTd1HLx6y", "reviewer": "Reviewer_1o3a", "summary": "This paper studies the use of spectral clustering under a setting where there is an underlying auxiliary _representation_ graph on the vertices, which encodes a notion of \"fairness/balancedness\" in the clusters. The goal under this setting is to find clusters, such that each clusters contains a representative number of vertices with respect to both the sparsest cut/conductance, and also with respect to the representation graph. To study this new setting, the paper introduces a new objective function, planted partition model, and the paper also performs experiments on synthetic and a real-world dataset.  ", "questions": "- What is the comparison between different methods with regards to the ratio cut objective? Is there a tradeoff between ensuring representation fairness and the ratio cut? It would be interesting to see if there is a way to maximize both, without losing performance in either of the objectives. \n\n- How should a reader interpret $\\lambda_1$, introduced in Theorem 4.2? ", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this paper is the new setting under which it proposes to study spectral clustering. Constrained/fair clustering has received considerable attention in recent years in the machine learning community, however not much work has been done in the Spectral Clustering literature, especially in the setting that this paper proposes (similar nodes should be spread across all clusters). In section 3, the paper clearly and convincingly introduces the new objectives under representation constraints, which seem natural to consider, and then develops a sensible algorithm to optimize these objectives. Guarantees are provided in Section 4, which seem correct to my knowledge. Experimental results validate the strength of the proposed method on both synthetic and real-world data. \n\nMoreover, the paper is well-written and has a clear exposition. \n\nA minor/medium weakness of the paper is in the theoretical analysis. Although the analysis is well-done, it relies on quite strong assumptions on the representation graph (d-regularity, balanced size clusters). Especially given the fact that in practice a representation graph might be constructed by hand, these conditions from Assumption 4.1 would be hard to satisfy in practice, making the theoretical analysis less applicable. \n\nAnother medium weakness of this paper is the presentation of Theorem 4.2\nAlthough Theorem 4.1 has clear and interpretable results, theorem 4.2 is hard to parse, and it is difficult for me to understand whether the 3 conditions are easy to satisfy for example. There are many variables and constants defined ($\\lambda_1$, and a number of universal constant), which are hard to interpret. I think the paper would be improved if there is a longer/higher-level paragraph of discussion on the analysis of Theorem 4.2 to help the reader to parse it. At the moment there is just a brief discussion on lines 267-268.\n\nMinor comments:\n- I found it hard to spot the definitions, I would suggest bolding them so it's slightly easier to read (up to your preference) ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FPv9eMdL0OA", "reviewer": "Reviewer_7uut", "summary": "The paper studies spectral algorithms for clustering under individual fairness constraints. This is the first spectral algorithm for this setting; the only previous fair spectral clustering algorithm was by Kleindessner et al. (ICML'19) and considered population level fairness.\n\nThe individual fairness constraint studied in the submission is newly proposed. The new problem assumes that besides the standard similarity graph (in which the clusters shall minimize the ratio-cut), there is also a *representation graph*. An edge in the representation graph indicates the similarity of two users. Now a novel constraint is proposed, which requires that *for each vertex* its neighbors (in the representation graph) are assigned to the clusters \"evenly\" among the clusters. The goal is to minimize the ratio-cut of the clusters in the similarity graph. It is shown that the previous results of Kleindessner et al. (ICML'19) and Chierichetti et al. (NeurIPS'17) are special cases of this setting.\n\nThen spectral algorithms for this problem are derived. It is shown that under a newly introduced random graph model, which is akin to the SBM, these algorithms classify almost all vertices correctly.", "questions": "The theorems require a (1+eps)-approximation algorithm for k-Means. However, k-Means is APX-hard. The cited algorithm from reference [28] only works when k is constant. I think this should be discussed in more detail.", "limitations": "I think the limitations and the potential impact are sufficiently discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well-written and easy to follow. The proofs for the theoretical are non-trivial. The newly proposed model for individual fairness is quite intriguing since it generalizes existing notions but at the same it \"requires similar individuals to be spread across different clusters\" (see Lines 156 and 157). The latter is somewhat counterintuitive compared to more classic clustering objectives. The reason is that in the proposed problem (Equation 7 in the paper), the objective is to minimize the ratio-cut in the similarity graph (similar to typical clustering tasks) but the constraint forces to split up the neighborhoods from the representation graph (unlike typical clustering tasks). I find this quite interesting and could imagine that this setting finds more applications in the future.\n\nThe paper also has some weaknesses. The main weakness is certainly that the theoretical results only hold under a relatively strong assumption (Assumption 4.1 in the paper), which stipulates that every vertex has degree d and it must have exactly d/K neighbors from each cluster in the final clustering. This is certainly a bit unrealistic, but deriving theoretical results for these types of problems is quite difficult, so I do not hold it against the paper too much.\n\nIn conclusion, I value the merits of the paper higher than its weaknesses. I believe the newly proposed problem raises enough interesting questions to merit further study.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5PO1DgG8KWV", "reviewer": "Reviewer_yXMv", "summary": "The paper introduces an extension to graph clustering where each node needs to be \"represented\" in each cluster roughly proportionally to the size of each cluster. After defining the unnormalized (and normalized in appendix B) representation aware spectral clustering, proposes a modification to the spectral algorithm so that representation is maximized. After providing some in depth analysis of their algorithm in the planted partition, the authors present numerical results in synthetic data and one real network.", "questions": "- For spectral K-clustering another objective is using the max instead of the sum (Khandekar, R., Kortsarz, G., and Mirrokni, V. On the advantage of overlapping clusters for minimizing conductance. Algorithmica, 69(4):844–863, 2014.) Have you also considered this objective?\n- Could the error bounds in section 4 incorporate p, q, r, s similarly to [Abbe, Emmanuel and Bandeira, Afonso S and Hall, Georgina, Exact Recovery in the Stochastic Block Model]?\n- Is $\\mathcal{R}$ in 4.1 a uniformly random graph? With the difference that the connections in each cluster are *exactly* $d/K$ instead of being on average $d/K$. This would make $\\mathbb{R}$ to be approximately rank-1.\n- Why are some xlabels missing eg 300 in fig 2, 900 in fig 6d, and more?\n- What is this spike in fig 3b at rank=100 for URespSC (approx.)?\n- Why did the authors decide to combine average balance and Ratio-Cut? I would like to see both separately.\n- Representation needs to be a single graph, potentially aggregating a number of features. Could this be extended to multiple attributes (eg age, gender, income)?\n- On commercial hardware, to what sizes of graphs does this method scale?\n- According to [Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29–123, 2009] most interaction graphs have a very different structure than SBM. How do you expect your method to perform in such graphs?", "limitations": "- The theoretical guarantees are only for a very well-tailored planted partition model. This has been acknowledged by the authors as a limitation.\n- Authors have acknowledged their method's computational bottleneck.\n- Authors are up front about the scope of their analysis and have set goals to expand it.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper provides a new problem that is more expressive than previous work (originality, significance).\n- For the $\\mathcal{R}$-PP model the authors provide an in-depth analysis (quality).\n- The paper is well structured and easily understood with the correct chapters relegated to the appendix, making it an enjoyable read (clarity).\n- The appendix contains detailed proofs of the authors' claims and theorems.\n- The authors consider both unnormalized ${\\bf and}$ normalized spectral clustering.\n- The algorithm that the authors provide is simple and comes with guarantees in certain cases.\n\nWeaknesses:\n- The authors define a very interesting problem in equation 4 and then immediately abandon it for a different problem in equation 5 two paragraphs later. Remove, or move to the appendix.\n- The results section consists of describing the experimental setup, placing the plots, and never commenting on them.\n- The numerical results contain only one real network whose quality is questionable. It's not necessarily bad, but it's an arbitrary construction.\n- The authors do not present any numerical results for the time scaling of their methods (though theoretical analysis is present).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5-kPGDuTyfW", "reviewer": "Reviewer_N1aR", "summary": "This paper studies the problem of fairness in the spectral clustering algorithm. In particular, the goal is to design an algorithm which guarantees that nodes with 'similar' latent properties are evenly distributed across the clusters.\n\nTo achieve this, the paper introduces a new notion of fairness, with respect to a 'representation graph' which links nodes with shared properties. Then, it describes a new, fair spectral clustering algorithm which takes as input both the observed graph, and the representation graph, and returns a fair clustering.\nThe paper also introduces \"a representation-aware planted partition model\" which is a generalization of the classical planted partition model to take into account the representation graph.\n\nFinally, the paper provides theoretical guarantees that the new algorithm successfully recovers the correct clusters in the planted partition model, under some reasonable assumptions.", "questions": "Can this framework can be used to control for multiple sensitive characteristics simultaneously (such as race *and* gender)? As I understand it, this couldn't be captured by the representation graph. This could be an interesting question for future work.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n----------\n1. The paper is well written, well structured, and well motivated.\n2. The paper studies an interesting and relevant problem. \n3. The 'representation graph' is a novel contribution which naturally generalizes previous notions of fairness and may find uses in other applications.\n\nWeaknesses\n---------------\nMinor issues:\n1. The assumptions on the parameters in Theorem 4.2 are a little difficult to interpret. It would be useful to provide some more discussion with some intuition for how they should be interpreted.\n2. Theorem 4.2 uses $\\mathrm{const}_1$, $\\mathrm{const}_4$, and $\\mathrm{const}_5$. Should this instead be $1$, $2$, and $3$?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept