Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

The 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.

Then 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.
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.

The 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.

In 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.
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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.  
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. 

Moreover, the paper is well-written and has a clear exposition. 

A 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. 

Another medium weakness of this paper is the presentation of Theorem 4.2
Although 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.

Minor comments:
- I found it hard to spot the definitions, I would suggest bolding them so it's slightly easier to read (up to your preference) 
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. 

- How should a reader interpret $\lambda_1$, introduced in Theorem 4.2? 
limitations: yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- The paper provides a new problem that is more expressive than previous work (originality, significance).
- For the $\mathcal{R}$-PP model the authors provide an in-depth analysis (quality).
- The paper is well structured and easily understood with the correct chapters relegated to the appendix, making it an enjoyable read (clarity).
- The appendix contains detailed proofs of the authors' claims and theorems.
- The authors consider both unnormalized ${\bf and}$ normalized spectral clustering.
- The algorithm that the authors provide is simple and comes with guarantees in certain cases.

Weaknesses:
- 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.
- The results section consists of describing the experimental setup, placing the plots, and never commenting on them.
- The numerical results contain only one real network whose quality is questionable. It's not necessarily bad, but it's an arbitrary construction.
- The authors do not present any numerical results for the time scaling of their methods (though theoretical analysis is present).
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?
- 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]?
- 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.
- Why are some xlabels missing eg 300 in fig 2, 900 in fig 6d, and more?
- What is this spike in fig 3b at rank=100 for URespSC (approx.)?
- Why did the authors decide to combine average balance and Ratio-Cut? I would like to see both separately.
- Representation needs to be a single graph, potentially aggregating a number of features. Could this be extended to multiple attributes (eg age, gender, income)?
- On commercial hardware, to what sizes of graphs does this method scale?
- 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.
- Authors have acknowledged their method's computational bottleneck.
- Authors are up front about the scope of their analysis and have set goals to expand it.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.

To 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.
The 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.

Finally, the paper provides theoretical guarantees that the new algorithm successfully recovers the correct clusters in the planted partition model, under some reasonable assumptions.
strengths_and_weaknesses: Strengths
----------
1. The paper is well written, well structured, and well motivated.
2. The paper studies an interesting and relevant problem. 
3. The 'representation graph' is a novel contribution which naturally generalizes previous notions of fairness and may find uses in other applications.

Weaknesses
---------------
Minor issues:
1. 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.
2. Theorem 4.2 uses $\mathrm{const}_1$, $\mathrm{const}_4$, and $\mathrm{const}_5$. Should this instead be $1$, $2$, and $3$?
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.
review_title: null

Meta-review: metareview: The paper presents a new interesting spectral generalization of fair clustering. The new notion captures many of the previously introduced notion and unify few of them. The authors present also an algorithm for the new notion.

Overall the paper presents interesting idea and it is nicely written so it would be a nice contribution to NeurIPS program.

The suggestion of the AC is to accept the paper as a poster.
confidence: Certain
Decision: Accept