{"id":"637a8dd0-dbde-4a49-b311-a16ff31dfd77","arxiv_id":"2505.22684","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Minimizing a newly defined fairness-modularity is proved to be exactly equivalent to enforcing equal protected-group proportions in every community, and a greedy Fast Newman variant is proposed to optimize it.","lead":"The paper introduces a fairness-modularity score built from a protected-group network and proves that driving it to zero is equivalent to making every community mirror the global protected-group proportions. It then adds this score as a constraint to the Fast Newman community detection algorithm and reports fairer partitions on benchmark and real datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"FairFN's greedy constraint ΔQP<0 only permits merging communities with opposite protected-group imbalance, so it can provably stall at QP>0; the paper offers no guarantee or test ruling this out.","rationale":"The reader's weakest assumption is the unproven bridge from greedy ΔQP < 0 merging to the global minimum characterized by Theorem 3.3. My pass confirms that the theorem itself is internally valid for the QP defined in Eq. (7): the Cauchy-Schwarz argument in Appendix B gives QP ≥ 0, with equality exactly when |C_u ∩ P_w|/|C_u| = |P_w|/n for every community and protected group. The serious soft spot is precisely the algorithmic bridge, and it can be made more concrete than the reader's general statement: for two protected groups, the condition ΔQP < 0 is equivalent to the two communities having opposite imbalance signs. Hence the greedy process can reach a state in which all remaining communities have the same imbalance sign, at which point no admissible merge exists and QP remains positive. This is a structural failure mode, not merely an absence of a convergence proof. The m_directed scaling inconsistency between Section 2 and Appendix A is also present, but it does not invalidate Theorem 3.3 because Eq. (7) can stand as the definition of QP; I therefore do not treat it as the primary concern. The empirical tables may still be accurate for the tested datasets, and the proposed test would determine whether the failure mode occurs in practice. Since the paper already received a conditional verdict, and this concern strengthens the condition rather than overturning the theoretical result, the verdict should remain unchanged.","tokens_in":18681,"tokens_out":20353,"duration_ms":219073,"concrete_test":"Implement Algorithm 1 exactly as written and run it on synthetic LFR graphs with two protected groups of sizes 140 and 60 (n=200, mixing parameter 0.3), setting α large enough (e.g., 10^6) that only the ΔQP < 0 condition stops the loop. Record the final QP and FR over 20 random seeds. If any run terminates with QP > 0 and FR < 1 while the one-community partition has QP = 0 and FR = 1, the greedy trajectory is not equivalent to globally minimizing QP, and the paper's central algorithmic claim needs qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.3 is correct for the globally minimized QP defined in Eq. (7): QP ≥ 0 and QP = 0 exactly at demographic-parity-fair partitions. The load-bearing gap is the unsupported leap from Theorem 3.3 to the claim that the FairFN trajectory recovers fairness. Algorithm 1, line 9, accepts a merge only if ΔQP(C_i,C_j) < 0. For two protected groups of sizes A and B, define the imbalance of a community C with a_A(C) nodes in group A and a_B(C) in group B as s(C) = B·a_A(C) − A·a_B(C). Direct algebra from Eq. (7) gives ΔQP(C,D) < 0 iff s(C)·s(D) < 0. Thus the only admissible merges are between communities whose protected-group imbalances have opposite signs. If the remaining communities are all biased in the same direction, no merge is admissible and the algorithm terminates with QP > 0, even though a fair partition (e.g., the single-community partition, by Proposition C.2) exists. Nothing in Sections 3, 4, or Appendix H rules out such a state; the 'negative feedback' heuristic in Appendix G.2 only operates while opposite imbalances remain. The paper's near-zero QP results therefore depend on the particular protected-group assignments used, not on a proven property of the algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19012,"tokens_out":9948,"duration_ms":87101,"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":[{"comment":"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.","section":"Section 3 (General Framework) and Algorithm 1"},{"comment":"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.","section":"Appendix C, Corollary C.1"},{"comment":"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.","section":"Section 2, Eq. (4), and Appendix A"},{"comment":"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.","section":"Algorithm 1, lines 9–10"}],"minor_comments":[{"comment":"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.","section":"Section 4.3 and Algorithm 1"},{"comment":"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.","section":"Section 4.2, Eq. (14)"},{"comment":"There is a typo: 'protecctd' should be 'protected'.","section":"Section 3, paragraph before Eq. (7)"},{"comment":"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 α'.","section":"Figures 3f and 5"},{"comment":"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.","section":"Section 4.1 and Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The core theorem appears correct, and the protected-group-network formulation is a fresh and potentially useful perspective. However, the gap between the global-minimum characterization and the greedy algorithm is substantial: as written, the algorithm can provably stall at an unfair partition, so the paper's central algorithmic claim is not supported. This is fixable within the manuscript's scope by adding a formal analysis of the greedy dynamics or by modifying the algorithm to guarantee progress toward QP = 0, but it requires more than cosmetic changes. The paper also contains a flawed proof in Appendix C and an incorrect directed-modularity convention. The promised code is not yet available, which limits reproducibility; the adaptive α scheme should be documented before the code release."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the protected-group-network construction and Theorem 3.3 are a real contribution, and FairFN performs well in the reported experiments. But the paper overclaims the link between the theorem and the algorithm. The greedy rule ΔQP<0 can stall at QP>0, so the promise that minimizing QP yields fairness does not carry over to FairFN as stated.\n\nWhat's actually new: formulating fairness as modularity on a complete block-diagonal graph with self-loops, and the Cauchy-Schwarz proof that QP=0 iff demographic parity holds. That is a clean reformulation that makes fair partitioning a modularity-optimization subproblem. The general framework, adding a fairness check to any agglomerative modularity optimizer, is a useful packaging, and FairFN is a concrete instantiation. The experiments are extensive: several baselines, real datasets, and the fairness gains are large.\n\nSoft spots, in order of importance.\n\nFirst, the stress-test concern is correct. For two protected groups of sizes A and B, the delta QP for merging communities C and D is proportional to s(C)s(D), where s(C)=B·|C∩P1|−A·|C∩P2|. So only merges between opposite-sign imbalances are admissible. If all remaining communities have the same sign, FairFN stops with QP>0 even though a fair partition (the single-community partition) exists. The negative-feedback mechanism in Appendix G.2 only operates while opposite imbalances remain. The near-zero QP values in the tables reflect the particular protected-group assignments used; nothing rules out the stall on other inputs. This is the central gap: Theorem 3.3 concerns global minimizers, and the algorithm has no proven connection to them.\n\nSecond, the directed modularity normalization in Section 2 and Appendix A is off by a factor of two relative to Leicht and Newman. It does not invalidate Theorem 3.3, since the zero condition is scale-invariant, but it affects the delta QP thresholds and the stopping rule.\n\nThird, Corollary C.1's upper-bound proof appears to drop a term: when C=P, the squared inner sum is Σ|P_u|⁴, not Σ|P_u|², so the claimed bound 1−1/(2mP) doesn't follow.\n\nMinor: no comparison with Manolis and Pitoura (2024) even though it is the closest modularity-fairness baseline; per-dataset α with no sensitivity analysis; no code or error bars. All are addressable.\n\nBottom line: the paper deserves serious refereeing. The theorem is a genuine contribution, and FairFN is likely useful in practice, but the authors should either temper the fairness-recovery claim, prove something about the greedy trajectory, or empirically test for the same-sign stall condition. I would accept it to review and press on that point.","headline":"A genuine reformulation of fair partitioning as modularity minimization, but the greedy algorithm's connection to the theorem is unproven.","tokens_in":19503,"tokens_out":5727,"would_cite":true,"duration_ms":52969,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["fair community detection","modularity optimization","fairness-modularity","demographic parity","protected group network","greedy agglomerative clustering","unbalanced data"],"falsifier":"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.","tokens_in":18473,"feed_emoji":"⚖️","tokens_out":10929,"duration_ms":98194,"temperature":0.7,"pith_summary":"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.","feed_headline":"Minimize a single score to get fair communities","feed_subtitle":"A score of zero fairness-modularity means every community mirrors the network's demographics; FairFN chases that zero.","key_machinery":"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$.","core_discovery":"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\\}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the modularity objective and the Fast Newman greedy agglomeration that FairFN extends with a fairness filter.","marker":"Newman (2004)"},{"why":"Defines modularity $Q$ in the form used for both the observed graph and the protected group network.","marker":"Newman & Girvan (2004)"},{"why":"Gives directed-graph modularity, which Lemma 3.2 uses to justify treating $G^P$'s symmetric directed edges as an undirected network.","marker":"Leicht & Newman (2008)"},{"why":"Introduces the fairness ratio metric used to evaluate partitions and the fairlets formulation that motivates the fairness definition.","marker":"Chierichetti et al. (2017)"},{"why":"Defines the average Wasserstein distance metric used to measure protected-group distribution mismatch.","marker":"Wang & Davidson (2019)"},{"why":"Provides the variational fair clustering baseline that FairFN is compared against.","marker":"Ziko et al. (2021)"},{"why":"Provides the fair spectral clustering baseline with balance constraints.","marker":"Kleindessner et al. (2019)"},{"why":"Provides the balanced fair k-means baseline.","marker":"Pan et al. (2024)"},{"why":"Provides the fair clustering ensemble baseline.","marker":"Zhou et al. (2025)"}],"fun_headline_variants":["Zero fairness-modularity equals perfect demographic parity","FairFN: minimize fairness-modularity, get fair communities","Minimize one score: fairness-modularity gives fair partitions","Zero fairness-modularity iff demographic parity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Zero fairness-modularity equals perfect demographic parity","FairFN: minimize fairness-modularity, get fair communities","Minimize one score: fairness-modularity gives fair partitions","Zero fairness-modularity iff demographic parity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000766,"raw_usage":{"total_tokens":3385,"prompt_tokens":924,"completion_tokens":2461,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":2397}},"tokens_in":540,"tokens_out":2461,"duration_ms":16798,"temperature":1.0,"reasoning_tokens":2397,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:43:43.915300+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives directed-graph modularity, which Lemma 3.2 uses to justify treating $G^P$'s symmetric directed edges as an undirected network."},{"cited_title":"Fair clustering through fairlets","cited_arxiv_id":null,"evidence_quote":"Introduces the fairness ratio metric used to evaluate partitions and the fairlets formulation that motivates the fairness definition."},{"cited_title":"and Davidson, I","cited_arxiv_id":null,"evidence_quote":"Defines the average Wasserstein distance metric used to measure protected-group distribution mismatch."},{"cited_title":"M., Yuan, J., Granger, E., and Ayed, I","cited_arxiv_id":null,"evidence_quote":"Provides the variational fair clustering baseline that FairFN is compared against."},{"cited_title":"Guarantees for spectral clustering with fairness constraints","cited_arxiv_id":null,"evidence_quote":"Provides the fair spectral clustering baseline with balance constraints."},{"cited_title":"Balanced fair k-means clustering","cited_arxiv_id":null,"evidence_quote":"Provides the balanced fair k-means baseline."},{"cited_title":"Fair clustering ensemble with equal cluster capacity","cited_arxiv_id":null,"evidence_quote":"Provides the fair clustering ensemble baseline."}],"review_version":1}