Pith. sign in

REVIEW 4 major objections 5 minor 25 references

Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that minimizing a fairness-modularity score defined on a protected-group network is exactly equivalent to demographic-parity-fair community partitioning, and realizes this in the FairFN algorithm.

desk verdict A genuine reformulation of fair partitioning as modularity minimization, but the greedy algorithm's connection to the theorem is unproven. read the letter →

arxiv 2505.22684 v1 pith:2XROR5EX submitted 2025-05-27 cs.SI cs.LG

Yufeng Wang , Yiguang Bai , Tianqing Zhu , Ismail Ben Ayed , Jing Yuan This is my paper · ORCID
classification cs.SIcs.LG
keywords faircommunitydetectionmodularityoptimizationfairness-modularitydemographicparityprotectedgroupnetworkgreedyagglomerativeclusteringunbalanceddata
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that fair community partitioning can be recovered directly from modularity: it constructs a protected group network, defines its modularity as fairness-modularity $Q^P$, and proves that $Q^P \ge 0$ with equality exactly when every community contains each protected group in the same proportion as the whole network. That makes minimizing $Q^P$ logically equivalent to enforcing demographic parity in the partition, so fair detection becomes a two-objective modularity problem instead of a post-hoc penalty. The authors add a simple filter to the classic greedy modularity-merging routine: only merge a pair when it raises conventional modularity and lowers $Q^P$, yielding the Fair Fast Newman (FairFN) algorithm. On LFR, synthetic, and real networks, FairFN reports near-zero $Q^P$, fairness ratios close to 1, and modularity competitive with or above baselines, including on unbalanced and weighted networks. A reader should care because the proof pins fairness to a single measurable quantity that any modularity-based method can optimize, not a separate clustering formulation.

What carries the argument

The load-bearing object is the protected group network $G^P$: the union, over protected groups, of complete directed graphs on each group's vertices, with self-loops, so its adjacency matrix is block-diagonal with all-ones blocks $1_{|P_w|}$. Its degree vector assigns every vertex in $P_w$ the degree $|P_w|$, and $m^P = \frac{1}{2}\sum_w |P_w|^2$ counts the corresponding undirected edges with self-loops as half edges. Fairness-modularity $Q^P$ is simply the standard modularity of this auxiliary network. It measures how much more internally connected communities are inside the protected-group cliques than a random null model would expect; that surplus is zero only when protected groups are spread proportionally across communities. The algorithm's mechanism is a $\Delta Q^P < 0$ filter on greedy merges, so the merge that maximizes conventional modularity gain is accepted only if it also decreases $Q^P$.

What would settle it

Run FairFN on a graph constructed so that, at some stage, every modularity-increasing merge joins two vertices or communities from the same protected group, so each such merge has $\Delta Q^P > 0$ and is rejected; the algorithm then halts with $Q^P > 0$ and a fairness ratio below 1, even though a fair partition of the same graph exists. Searching small graphs for any run that terminates with $Q^P > 0$ would settle whether the greedy trajectory reaches the fair optimum.

Watch

Extended reading notes

Core claim

At the center of the paper is Theorem 3.3: for any partition of the protected group network $G^P$, the fairness-modularity $Q^P$ is always nonnegative, and $Q^P=0$ if and only if $|C_u \cap P_w|/|C_u| = |P_w|/n$ for every community $C_u$ and protected group $P_w$ — the standard demographic-parity fairness condition. The equality condition comes from applying Cauchy-Schwarz to the trace formula $Q^P = \frac{1}{2m^P}\left(\sum_{u,w}|C_u \cap P_w|^2 - \frac{1}{2m^P}\sum_u(\sum_w |C_u \cap P_w||P_w|)^2\right)$; equality forces the ratios $|C_u\cap P_w|/|P_w|$ to be constant across $w$, and since the $P_w$ partition all vertices that constant is $|C_u|/n$. Consequently, finding a fair partition is exactly minimizing $Q^P$, and the paper expresses fair community detection as the multi-objective problem $\max_S \{Q, -Q^P\}$.

Load-bearing premise

The paper proves fairness is equivalent to $Q^P=0$, but it does not prove that FairFN's greedy merging rule, which only takes merges with negative $\Delta Q^P$, will actually drive $Q^P$ all the way to zero rather than stopping at an unfair local minimum.

Editorial extensions

If this is right

  • Any modularity optimizer can be converted into a fair community partitioner by restricting merges to those with $\Delta Q^P < 0$; the paper demonstrates this on Fast Newman and notes the framework also covers Louvain and CNM.
  • On the most unbalanced synthetic dataset, with protected-group proportions $(0.01,0.49,0.5)$, FairFN's partition of 17 communities keeps the 1% minority distributed instead of segregated, while $Q$ stays high.
  • Reported $Q^P$ values are near zero across all datasets, so the global fairness optimum characterized by Theorem 3.3 is approached by a simple greedy rule in practice, not just in theory.
  • Weighted observed networks do not undermine fairness: with intra-community edges weighted 50 and inter-community edges 10, FairFN still reaches $FR=0.9860$, $AWD=0.0014$.
  • The added cost is $O((m+n)n)$, the same order as the original Fast Newman routine, though the paper acknowledges this still limits very large networks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: because $Q^P$ gives a continuous certificate of demographic parity, it could serve as a generic regularizer added to k-means, spectral clustering, or graph-cut objectives, replacing bespoke balance or KL penalties.
  • Editorial inference: Proposition C.2 shows merging two fair communities keeps fairness, so fair partitions form a family closed under coarsening; hierarchical or streaming algorithms could therefore maintain exact fairness by construction at every resolution.
  • Editorial inference: the sharp late-stage rise in the $\alpha$ threshold resembles a phase transition and might be usable as an automatic stopping rule, flagging the point where further modularity gains would force unfair merges.
  • Editorial inference: a post-processing pass that moves individual vertices across community borders while monitoring $Q^P$ could rescue runs that stop at a local minimum with $Q^P>0$, turning FairFN into an exact fair partitioner on small graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper introduces a 'protected group network' G^P, defined as the union of complete directed graphs over each protected group, and defines a 'fairness-modularity' QP equal to the modularity of G^P. Theorem 3.3 states that QP is always nonnegative and vanishes exactly when every community has the same protected-group proportion as the whole network (demographic parity). The authors then formulate fair community partitioning as the multi-objective problem of maximizing the ordinary modularity Q while minimizing QP, and propose FairFN, a greedy agglomerative algorithm that merges communities only when the fairness-modularity increment is negative. Experiments on LFR benchmarks, synthetic datasets, and six real-world datasets compare FairFN with FN, variational fair clustering, fair spectral clustering, balanced fair k-means, and fair clustering ensemble, reporting higher fairness ratio, lower average Wasserstein distance, and competitive modularity.

Significance. The concept of fairness-modularity is elegant, and Theorem 3.3 provides a clean, parameter-free characterization of demographic parity as the global minimum of a modularity-type objective. If the connection between this global minimum and the proposed greedy algorithm were established, the work would be significant because it would allow a large family of modularity-optimization algorithms to be adapted for fairness. The proof of Theorem 3.3 is elementary and transparent, and the experimental comparison covers a reasonable set of baselines and datasets. However, the algorithmic claim is not actually supported by the theorem: the paper proves a property of global minimizers of QP while the algorithm performs only local greedy decreases, and no argument is given that the greedy trajectory reaches the fair global minimum or even that it does not stall at an unfair local minimum.

major comments (4)
  1. [Section 3 (General Framework) and Algorithm 1] Theorem 3.3 characterizes global minimizers of QP, but Algorithm 1 only accepts a merge when ΔQP < 0. No proof is given that this greedy procedure reaches a global minimum of QP or that its termination point is fair. In fact, for two protected groups with sizes A and B, defining the imbalance s(C) = B·|C∩P1| − A·|C∩P2|, direct algebra from Eq. (7) shows that ΔQP(C,D) < 0 holds iff s(C)·s(D) < 0. Consequently, if all remaining communities have imbalances of the same sign, no merge is admissible and the algorithm terminates with QP > 0, even though a fair partition (for example, the single-community partition, by Proposition C.2) exists. The 'negative feedback' discussion in Appendix G.2 is heuristic and does not exclude this state. The near-zero QP values in Tables 1 and 2 therefore reflect properties of the specific protected-group assignments tested, not a proven property of the algorithm.
  2. [Appendix C, Corollary C.1] The proof of the upper bound in Corollary C.1 is incorrect. For the partition C = P (each protected group is one community), Eq. (28) evaluates to QP = (1/(2mP)) [ Σ_w |P_w|^2 − (1/(2mP)) Σ_w |P_w|^4 ]. However, Eq. (29) replaces the second term with (1/(2mP)) Σ_w |P_w|^2, which drops a factor of |P_w|^2. The equality to 1 − 1/(2mP) does not follow from the previous line. The upper bound may still be true, but the proof as written is invalid and needs repair.
  3. [Section 2, Eq. (4), and Appendix A] The directed modularity formula in Eq. (4) defines m_directed as Σ_i k_i^in + Σ_i k_i^out, which is twice the number of directed edges. The standard directed modularity of Leicht and Newman uses the number of directed edges, m = Σ_i k_i^in = Σ_i k_i^out. The equality in Lemma 3.2's proof works out for symmetric directed graphs only because of a cancellation between the prefactor and the null-model denominator, but Eq. (4) is not the standard directed modularity and the statement 'The number of edges is then m_directed = ...' is incorrect. This should be corrected or explicitly clarified as a nonstandard convention.
  4. [Algorithm 1, lines 9–10] The pseudocode is incomplete: if no pair (C_i, C_j) satisfies ΔQP_ij < 0, the 'Find the pair' step has no defined output and the loop's behavior is unspecified. Additionally, line 10 writes 'C_i = C_i ∩ C_j', which should be a union; as written, the merged community would be empty. The algorithm should specify the behavior when no fair merge exists, for example by stopping or by falling back to a modularity-only merge, and the union operation should be corrected.
minor comments (5)
  1. [Section 4.3 and Algorithm 1] The text in Section 4.3 states that 'we adaptively increase the parameter α' during merging, but Algorithm 1 treats α as a fixed input and the pseudocode contains no update rule for α. The adaptive scheme should be specified precisely so that the experimental results are reproducible.
  2. [Section 4.2, Eq. (14)] The average Wasserstein distance AWD uses the symbol WD(p_u, p) but the Wasserstein distance is never defined. Please provide a definition or a reference.
  3. [Section 3, paragraph before Eq. (7)] There is a typo: 'protecctd' should be 'protected'.
  4. [Figures 3f and 5] The axis labels in Figures 3f and 5 appear to be missing due to rendering issues; the x-axis should be labeled 'number of communities' and the y-axis 'threshold of α'.
  5. [Section 4.1 and Appendix D] The construction of the kNN graph introduces a free parameter k=10, but the paper does not discuss its influence on fairness or modularity results; a sensitivity analysis or at least a comment on the choice would strengthen the experimental section.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 3.3 is a direct derivation and fairness results are externally validated by FR/AWD.

full rationale

The central claimed derivation, Theorem 3.3, states that QP >= 0 with equality iff |C_u ∩ P_w| / |C_u| = |P_w| / n. This is a direct algebraic consequence of Eq. (7) and the Cauchy-Schwarz inequality in Appendix B; no fitted parameter, external benchmark, or author-specific assumption enters the theorem. The protected-group network and fairness-modularity are constructed from the protected-group partition, and the theorem proves their equivalence to the demographic-parity condition rather than assuming it. FairFN's merge rule (Algorithm 1, line 9) does enforce ΔQP < 0, so the reported decrease in QP (Figure 3d, Table 2) is an invariant of the algorithm, but the fairness claims are independently checked with FR (Eq. 12) and AWD (Eq. 14) and against external baselines (VFC, FSCN, BFKM, FCE), so no fitted input is being relabeled as a prediction. The only self-citation of note is Ziko et al. (2021), used as the VFC baseline and related work; I. B. Ayed is a co-author of the present paper, but that baseline is not load-bearing for the core derivation. The gap between global minimizers of QP and the local greedy trajectory of FairFN is a real correctness risk, not a circularity: it concerns whether the algorithm reaches the theorem's zero, not whether the theorem reduces to its inputs.

Assumptions & free parameters 3 free parameters · 6 assumptions · 1 invented entities

The theorem itself rests only on standard algebra plus the demographic-parity definition. The algorithm introduces alpha and the unproven greedy-to-global bridge. The protected group network is a construction with no external falsifiable handle.

free parameters (3)
  • alpha = 4, 64, 8, 4, 4, 4, 4 (Table 3); 8 and 64 in weighted/unbalanced experiments
    Stopping threshold that loosens FN's merge criterion; chosen per dataset with no stated selection rule or sensitivity analysis.
  • k (kNN graph construction) = 10
    Real datasets converted to networks with k-nearest neighbors; graph topology directly affects detected communities.
  • subsample size = 5000
    Adult, Bank, Census1990, Creditcard and Diabetic subsampled to 5000 nodes before network construction; results depend on this reduction.
assumptions (6)
  • domain assumption Protected groups P_1,...,P_r partition V: V = union of P_w and P_i ∩ P_j = empty for all i,j.
    Used to build G^P in Section 3; real datasets with missing or multiple attribute values are preprocessed to fit this assumption.
  • domain assumption Fairness is demographic parity: |C_u ∩ P_w| / |C_u| = |P_w| / n for all u,w.
    This is the fairness notion embedded in QP and validated by FR/AWD; alternative fairness definitions are not considered.
  • domain assumption The modularity null model (configuration model) is the correct basis for both community quality Q and fairness-modularity QP.
    Inherited from Newman and Girvan; the whole method presupposes modularity's validity.
  • ad hoc to paper Directed modularity formula (4) with m_directed = sum of in and out degrees is the correct directed extension.
    This nonstandard edge count appears in Section 2 and Lemma 3.2 and yields a scaling inconsistent with Eq (7) and standard directed modularity; the theorem itself does not depend on this lemma.
  • ad hoc to paper Greedy local decrease of QP (delta QP < 0) is a sufficient mechanism to reach a fair partition.
    Algorithm 1 enforces this but no proof connects it to global minimization of QP or to the equality condition of Theorem 3.3.
  • standard math Cauchy-Schwarz inequality.
    Used in Appendix B to prove QP >= 0 and the equality condition.
invented entities (1)
  • Protected group network G^P
    purpose: Encodes protected attributes as a complete within-group graph so that its modularity QP measures fairness; QP = 0 iff demographic parity holds.
    A mathematical construction derived from the protected attribute partition; it has no external observable consequences beyond the fairness notion it defines, so it cannot be independently falsified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning." pith.science (2026). https://pith.science/paper/2XROR5EX

@misc{pith2026250522684,
  author       = {Pith},
  title        = {Pith review of: Recovering Fairness Directly from Modularity: a New Way for Fair Community Partitioning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2XROR5EX}},
  note         = {Machine review of arXiv:2505.22684}
}
read the original abstract

Community partitioning is crucial in network analysis, with modularity optimization being the prevailing technique. However, traditional modularity-based methods often overlook fairness, a critical aspect in real-world applications. To address this, we introduce protected group networks and propose a novel fairness-modularity metric. This metric extends traditional modularity by explicitly incorporating fairness, and we prove that minimizing it yields naturally fair partitions for protected groups while maintaining theoretical soundness. We develop a general optimization framework for fairness partitioning and design the efficient Fair Fast Newman (FairFN) algorithm, enhancing the Fast Newman (FN) method to optimize both modularity and fairness. Experiments show FairFN achieves significantly improved fairness and high-quality partitions compared to state-of-the-art methods, especially on unbalanced datasets.

Figures

Figures reproduced from arXiv: 2505.22684 by the authors.

Figure 1
Figure 1. depicts an example of a protected group network, with three protected groups of vertices (in three different colors) including self-loops. Figure 1a represents a fair community partitioning result, where members of each protected group are mostly distributed evenly across communities. Figure 1b shows the community partition missing fairness, which may lead to the segregation or underrepresentation of certain groups.… view at source ↗
Figure 2
Figure 2. Communities detected and protected groups of each community partition in the LFR [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Experiment results in the given LFR network. The number of communities ranges from [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The proportion of protected groups in different communities. The X-axis represents [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]
Figure 5
Figure 5. Figure 5: The threshold of α in synthetic clustering datasets and real-world datasets. The number of communities ranges from 100 to finish due to the threshold in the beginning stage being nearly zero. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    K., Chakrabarty, D., Flores, N

    Bera, S. K., Chakrabarty, D., Flores, N. J., and Negahbani, M. Fair algorithms for clustering. Curran Associates Inc., Red Hook, NY, USA, 2019

    work page 2019

  2. [2]

    D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E

    Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008 0 (10): 0 P10008, oct 2008

    work page 2008

  3. [3]

    On modularity clustering

    Brandes, U., Delling, D., Gaertler, M., Gorke, R., Hoefer, M., Nikoloski, Z., and Wagner, D. On modularity clustering. IEEE Transactions on Knowledge and Data Engineering, 20 0 (2): 0 172--188, 2008

    work page 2008

  4. [4]

    Fair clustering through fairlets

    Chierichetti, F., Kumar, R., Lattanzi, S., and Vassilvitskii, S. Fair clustering through fairlets. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS'17, pp.\ 5036–5044, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964

    work page 2017

  5. [5]

    Clauset, A., Newman, M. E. J., and Moore, C. Finding community structure in very large networks. Phys. Rev. E, 70: 0 066111, Dec 2004

    work page 2004

  6. [6]

    Ant colony optimization based on random walk for community detection in complex networks

    Di, J., Bo, Y., Jie, L., Da-you, L., and Dong-xiao, H. Ant colony optimization based on random walk for community detection in complex networks. Journal of Software, 23 0 (3): 0 451, 2012

    work page 2012

  7. [7]

    Community detection in graphs

    Fortunato, S. Community detection in graphs. Physics Reports, 486 0 (3-5): 0 75--174, 2010

    work page 2010

  8. [8]

    and Newman, M

    Fortunato, S. and Newman, M. E. 20 years of network community detection. Nature Physics, 18 0 (8): 0 848--850, 2022

    work page 2022

Show all 25 references
  1. [9]

    Fast complex network clustering algorithm using local detection

    Jin, D., Liu, D.-Y., Yang, B., Liu, J., He, D.-X., and Tian, Y. Fast complex network clustering algorithm using local detection. Dianzi Xuebao(Acta Electronica Sinica), 39 0 (11): 0 2540--2546, 2011

    2011

  2. [10]

    and Honavar, V

    Khademi, A. and Honavar, V. Algorithmic bias in recidivism prediction: A causal perspective (student abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 34 0 (10): 0 13839--13840, Apr. 2020

    2020

  3. [11]

    Guarantees for spectral clustering with fairness constraints

    Kleindessner, M., Samadi, S., Awasthi, P., and Morgenstern, J. Guarantees for spectral clustering with fairness constraints. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine...

    2019

  4. [12]

    Leicht, E. A. and Newman, M. E. J. Community structure in directed networks. Phys. Rev. Lett., 100: 0 118703, Mar 2008

    2008

  5. [13]

    One-stage fair multi-view spectral clustering

    Li, R., Hu, H., Du, L., Chen, J., Jiang, B., and Zhou, P. One-stage fair multi-view spectral clustering. In Proceedings of the 32nd ACM International Conference on Multimedia, MM '24, pp.\ 1407–1416, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400706868

    2024

  6. [14]

    and Pitoura, E

    Manolis, K. and Pitoura, E. Modularity-based fairness in community detection. In Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM '23, pp.\ 126–130, New York, NY, USA, 2024. Association for Computing Machinery...

    2023

  7. [15]

    Newman, M. E. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103 0 (23): 0 8577--8582, 2006

    2006

  8. [16]

    Newman, M. E. J. Fast algorithm for detecting community structure in networks. Phys. Rev. E, 69: 0 066133, Jun 2004

    2004

  9. [17]

    Newman, M. E. J. and Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E, 69: 0 026113, Feb 2004

    2004

  10. [18]

    Balanced fair k-means clustering

    Pan, R., Zhong, C., and Qian, J. Balanced fair k-means clustering. IEEE Transactions on Industrial Informatics, 20 0 (4): 0 5914--5923, 2024

    2024

  11. [19]

    Scikit-learn: Machine learning in python

    Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in python. J. Mach. Lea...

    2011

  12. [20]

    N., Albert, R., and Kumara, S

    Raghavan, U. N., Albert, R., and Kumara, S. Near linear time algorithm to detect community structures in large-scale networks. Phys. Rev. E, 76: 0 036106, Sep 2007

    2007

  13. [21]

    and Bergstrom, C

    Rosvall, M. and Bergstrom, C. T. An information-theoretic framework for resolving community structure in complex networks. Proceedings of the National Academy of Sciences, 104 0 (18): 0 7327--7331, 2007

    2007

  14. [22]

    and Davidson, I

    Wang, B. and Davidson, I. Towards fair deep clustering with multi-state protected variables, 2019

    2019

  15. [23]

    Scalable spectral clustering with group fairness constraints

    Wang, J., Lu, D., Davidson, I., and Bai, Z. Scalable spectral clustering with group fairness constraints. In Ruiz, F., Dy, J., and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings ...

    2023

  16. [24]

    Fair clustering ensemble with equal cluster capacity

    Zhou, P., Li, R., Ling, Z., Du, L., and Liu, X. Fair clustering ensemble with equal cluster capacity. IEEE Transactions on Pattern Analysis and Machine Intelligence, 47 0 (3): 0 1729--1746, 2025

    2025

  17. [25]

    M., Yuan, J., Granger, E., and Ayed, I

    Ziko, I. M., Yuan, J., Granger, E., and Ayed, I. B. Variational fair clustering. In AAAI Conference on Artificial Intelligence, 2021

    2021

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.