{"id":"877cdbfe-7937-48ea-9915-0dfb267c8d34","arxiv_id":"2412.09947","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"Fairwos learns pseudo-sensitive features from graph data and enforces fairness by aligning embeddings with nearby same-label nodes, claiming fair GNNs without sensitive attributes.","lead":"A new method, Fairwos, trains graph neural networks to be fair without access to sensitive attributes like race or gender, by learning proxy features and matching predictions between similar users. The paper claims theoretical guarantees and better fairness-accuracy trade-offs than existing no-sensitive-attribute baselines, but the proof relies on a questionable Markov chain assumption.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's bound relies on a Markov chain s → G → x0 → z → ŷ that the Fairwos architecture does not satisfy, because z is computed from both G and x0, not from x0 alone.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: Theorem 1's proof assumes a Markov chain that the Fairwos architecture does not realize. My independent reading of Sections III and IV confirms this. The encoder produces node features x0 from G, but the subsequent GNN consumes both the adjacency matrix and x0, so z_u can (and in general will) carry information about G_u that is not present in x0_u. The proof simply asserts the chain without derivation, and no experiment tests the mediation assumption. Since the abstract promises a theoretical demonstration that minimizing dependence on pseudo-sensitive attributes bounds unfairness, and this demonstration collapses, the paper's primary contribution is reduced to a heuristic with modest empirical gains. I therefore find no reason to move away from the reader's rejection. The proposed rewiring test would settle the point definitively: if z is invariant to edge rewiring given x0, the chain holds; otherwise it does not. I also note the secondary flaw in Theorem 2 (dropping the nonzero neighbor-sum term), but the Markov-chain issue alone is sufficient to invalidate the central claim. I agree with the reader's verdict of REJECT and recommend no change.","tokens_in":20595,"tokens_out":6542,"duration_ms":71277,"concrete_test":"Train Fairwos on a benchmark (e.g., Bail) to convergence. For a set of held-out nodes u, compute x0_u = Encoder(G_u). Then rewire each node's local neighborhood randomly (preserving degree or using random neighbors of the same size) while holding node features X0 fixed, and pass the modified graph through the trained GNN to obtain z'_u. If the average ||z_u − z'_u||2 is statistically significantly above the numerical precision floor, then z depends on G beyond x0, contradicting the Markov chain s → G → x0 → z and invalidating Theorem 1's bound. This is a direct, model-specific falsification test that does not require estimating mutual information.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim (Theorem 1, Section IV.A) states 0 ≤ I(s; ŷ_u) ≤ I(s; z_u) ≤ I(G_u; z_u) ≤ Σ_t I(x0_t; z_u), and the proof asserts the Markov chain s → G_u → x0_u → z_u → ŷ_u 'due to the existence of an encoder.' In the actual pipeline (Section III.B–D), x0_u = Encoder(G_u; Θ*_enc) is extracted first, then the GNN classifier takes G = (V, E, X(0)) as input and computes z_u through message passing (Eq. 7–8). Thus z_u is a function of both the graph adjacency and x0_u. The asserted chain requires z_u ⊥ G_u | x0_u, i.e., that x0_u is a sufficient statistic for all graph information used by the GNN. This is not established and is generally false: a fixed low-dimensional vector cannot encode arbitrary neighborhood structure, and the graph edges enter every aggregation layer. Consequently, the inequality I(G_u; z_u) ≤ Σ_t I(x0_t; z_u) does not follow; if anything, x0 is a function of G, so the data processing inequality gives no such bound. Since the paper's abstract and conclusion rest on this theoretical guarantee, the central justification for Fairwos is unsupported. (A further issue: Theorem 2 drops the nonzero neighborhood term in Eq. 28 by claiming it is 0, which is also inconsistent with the algorithm.)","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Fairwos, a framework for training fair graph neural networks when sensitive attributes are not available during training. The method has three main components: an encoder that maps node attributes and graph structure to low-dimensional pseudo-sensitive attributes X(0); a counterfactual search procedure that, for each node, finds real nodes with the same label but different pseudo-sensitive attributes and uses those as graph counterfactuals; and a fair representation learning step that penalizes the distance between original and counterfactual embeddings, with per-attribute weights updated through a KKT-based scheme. The authors claim a theoretical guarantee that reducing the mutual information between pseudo-sensitive attributes and GNN embeddings bounds the unfairness of predictions, and they report experiments on six datasets showing improved fairness-utility trade-offs relative to several baselines.","tokens_in":20973,"tokens_out":3107,"duration_ms":36928,"significance":"If the theoretical guarantee were valid, the paper would make a meaningful contribution: it addresses a practical and timely problem, fairness without sensitive attributes for graph data, and it proposes a concrete mechanism, pseudo-sensitive attributes generated by an encoder, with graph counterfactuals selected from real data rather than by unrealistic perturbation. The experimental study is broad, covering six datasets and two backbone GNNs, and the reported results are generally favorable. However, the central theoretical claim is the load-bearing justification for the method, and it rests on a conditional-independence assumption that the proposed architecture does not satisfy. The empirical results alone, while suggestive, do not establish the fairness mechanism, especially because the standard deviations in Table II are large and no statistical significance tests are reported. The paper should therefore not be accepted in its current form.","major_comments":[{"comment":"The proof of Theorem 1 relies on the Markov chain s -> G_u -> x0_u -> z_u -> yhat_u, which requires z_u to be conditionally independent of G_u given x0_u. This does not hold for the actual architecture: in Section III.C, the GNN classifier takes G = (V, E, X(0)) as input and computes z_u through message passing over the graph adjacency (Eqs. 7-8), so z_u carries information about G_u beyond x0_u. Consequently, the inequality I(s; yhat_u) <= I(G_u; z_u) <= sum_t I(x0_t; z_u) does not follow from the stated assumptions. Since the abstract and conclusion rest on this theoretical guarantee, the central justification for Fairwos is unsupported unless the mediation assumption is derived from the architecture or explicitly tested.","section":"Section IV.A, Theorem 1"},{"comment":"The proof of Theorem 2 drops the neighborhood aggregation term in Eq. (28) with the claim that the second term is 0. This is inconsistent with the algorithm: graph counterfactuals are found by searching for different real nodes (Eq. 12), so the neighborhoods N(u) and N(tilde u) are generally different, and the aggregation difference term is generally nonzero. Additionally, the proof assumes ||tilde x0_u - x0_u|| = 1 for a single perturbed attribute, but the real-node search changes the pseudo-sensitive attribute vector in a data-dependent way, not as a unit-norm single-coordinate perturbation. Thus Theorem 2 does not provide a valid bound for the actual counterfactual generation procedure.","section":"Section IV.A, Theorem 2"},{"comment":"There is a circularity concern in the fairness argument. The pseudo-sensitive attributes X(0) are produced by an encoder trained with labels (Eqs. 4-5), and the counterfactual search in Eq. (12) uses both these pseudo-sensitive attributes and the (pseudo-)labels. The fairness loss in Eq. (15) then aligns original and counterfactual embeddings, effectively encouraging the model to be invariant to variations in the same pseudo-sensitive attributes that were used to select the counterfactuals. This only reduces unfairness if pseudo-sensitive attributes mediate all sensitive influence on predictions. That mediation assumption is precisely what the paper needs to establish, but it is asserted rather than proven or tested.","section":"Section III.D and fair representation learning"}],"minor_comments":[{"comment":"Algorithm 1 contains incorrect equation references: line 1 says 'optimizing (2)' but the encoder is trained with Eq. (5), and line 4 says 'optimizing Eq. (7)' but the GNN classifier loss is Eq. (10).","section":"Section III.F, Algorithm 1"},{"comment":"Definitions labeled 3.1 and 3.2 appear in Section II.B but are numbered as if they belong to Section III; the definition numbering should be corrected.","section":"Section II.B"},{"comment":"The KKT derivation for the lambda update is missing the factor alpha: the first-order condition of Eq. (19) is alpha D_i^K + 2 lambda_i - a_i + b = 0, but Eq. (20) omits alpha, and this omission propagates to the closed-form update in Eq. (24).","section":"Section III.F, Eqs. (19)-(21)"},{"comment":"The notation in Theorem 1 is inconsistent: the final bound is written as sum_t I(x0_i; z_u), mixing indices i and t, and the role of T is not defined precisely.","section":"Section IV.A, Theorem 1 statement"},{"comment":"The first dataset column is labeled 'Recidivism' while the dataset is called 'Bail' in Table I and Section V.A.1; the table header should be consistent with the dataset name.","section":"Table II"},{"comment":"The claims of superior performance are based on means with overlapping standard deviations (e.g., Fairwos versus FairGKD\\S on several datasets in Table II); reporting statistical significance tests or confidence intervals would make the empirical comparison more convincing.","section":"Section V.B"}],"recommendation":"reject","confidential_remarks":"The theoretical section is the paper's centerpiece, and both theorems contain load-bearing errors that cannot be repaired with local edits: Theorem 1 assumes a Markov chain that the architecture does not satisfy, and Theorem 2 drops a nonzero term that is incompatible with the real-node counterfactual search. Without the theoretical guarantee, the paper is an empirical heuristic with suggestive but not statistically robust results. I therefore recommend rejection, although the problem setting and the pseudo-sensitive-attribute idea are worth pursuing in future work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [Name],\n\nHere's my read on arXiv:2412.09947 (Fairwos). The paper combines two known ideas: an encoder that produces pseudo-sensitive attributes (as in FairRF) and a same-label nearest-neighbor alignment loss (as in CAF), plus a weight-updating scheme for the pseudo-attributes. That combination is new and the empirical study is reasonably thorough: six datasets, two backbones, ablation, hyperparameter sensitivity, runtime. The fairness gains over baselines are modest but real in several cases, and the accuracy rarely tanks.\n\nThe problem is the theory. Theorem 1 claims 0 ≤ I(s; ŷ) ≤ I(s; z) ≤ I(G; z) ≤ Σ I(x0_t; z), and the proof relies on the Markov chain s → G → x0 → z → ŷ. That chain requires z to be conditionally independent of G given x0. But the actual pipeline computes x0 = Encoder(G), then feeds G = (V, E, X(0)) into a GNN; the adjacency enters every message-passing layer. A fixed low-dimensional x0 cannot be a sufficient statistic for the graph neighborhoods that drive z. So the chain doesn't hold, and the bound I(G; z) ≤ Σ I(x0_t; z) doesn't follow. The abstract and conclusion lean on this guarantee, so the central theoretical justification is unsupported. Theorem 2 has a related problem: it drops the neighborhood-difference term in Eq. (28) by claiming it's zero, which is false when the counterfactual node has a different neighborhood. The 'graph counterfactual' is also not a counterfactual; it's a real node found by nearest-neighbor search. That's an overstatement, though the heuristic might still be reasonable.\n\nOne more thing: the paper uses sensitive attributes for model selection on the validation set (implementation details say the best model is saved based on validation performance, and the validation split has sensitive attributes). If the claim is fairness without sensitive attributes, that's a leak that should be acknowledged or addressed.\n\nSo where does that leave it? The method is a legitimate extension of existing work, and the empirical evidence, while modest, is not nothing. But the theoretical guarantee is the paper's selling point and it's wrong. The authors would need to either fix the analysis (e.g., bound the influence of x0 directly, or state the mediation assumption as an unproven condition) or drop the theory and reframe the paper as a heuristic method with empirical evaluation. With that revision, it could be a reasonable workshop or short-paper contribution; as it stands, the main claim doesn't hold up.\n\nI'd send it to peer review rather than desk reject, because the flaw is specific and fixable and the problem is worth studying. But I wouldn't cite the current version, and I wouldn't bring it to reading group as a model of how to do theory.\n\nBest,\n[Name]","headline":"The method is a reasonable combination of known ideas with modest empirical gains, but the theoretical guarantee that anchors the paper doesn't survive contact with the actual architecture.","tokens_in":21437,"tokens_out":3813,"would_cite":false,"duration_ms":35298,"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":"The paper claims that GNN fairness can be enforced without sensitive attributes by learning pseudo-sensitive proxies and minimizing a mutual-information upper bound on the hidden protected attribute.","keywords":["graph neural networks","counterfactual fairness","fairness without sensitive attributes","pseudo-sensitive attributes","node classification","graph counterfactual","representation learning"],"falsifier":"Train Fairwos on a public graph benchmark with the true sensitive attribute withheld and with it available only for evaluation; then estimate $I(s;z_u)$ and $\\sum_t I(x^0_t;z_u)$ on test nodes and test conditional independence of $z_u$ and $G_u$ given $x^0_u$. A trained model that violates the inequality, or whose embedding still depends on graph structure beyond the pseudo-attributes, shows the theorem's hypothesis is not met.","tokens_in":20365,"feed_emoji":"⚖️","tokens_out":9281,"duration_ms":89226,"temperature":0.7,"pith_summary":"Fairwos aims to make graph neural network predictions fair even when sensitive attributes such as race or gender are unavailable at training time. It first learns low-dimensional pseudo-sensitive attributes from the non-sensitive features and graph structure, then finds graph counterfactuals by searching the real dataset for same-label nodes with different pseudo-attributes, and trains the GNN so original and counterfactual embeddings are close. The paper's central theoretical claim is that reducing the mutual information between pseudo-sensitive attributes and the learned representation also reduces an upper bound on the mutual information between the hidden sensitive attribute and the prediction. This matters because privacy laws often forbid collecting protected attributes, yet unfairness can still flow through correlated features and network structure. If the bound holds, Fairwos offers a principled, attribute-free route to counterfactual-style fairness for GNNs.","feed_headline":"One bound makes GNN fairness work without sensitive attributes","feed_subtitle":"Fairwos finds realistic counterfactuals in real data and shrinks the provable upper bound on prediction bias.","key_machinery":"The load-bearing objects are the pseudo-sensitive attributes $x^0_u = \\mathrm{Encoder}(G; \\Theta^*_{\\mathrm{enc}})$, low-dimensional representations of non-sensitive features and graph structure, and the counterfactual-consistency loss that minimizes the distance between the embedding of the original subgraph and the embeddings of its top-$K$ real-data counterfactuals. The identity that carries the argument is Theorem 1's mutual-information chain, which connects the disparity loss to the hidden sensitive attribute's influence on predictions. A per-attribute weight $\\lambda_i$, updated by a KKT-based scheme, concentrates fairness regularization on the pseudo-attributes that contribute most to bias while preserving utility.","core_discovery":"The central discovery, on the paper's own terms, is that the gap between the hidden sensitive attribute $s$ and the prediction $\\hat y_u$ is controlled by the dependence of the GNN embedding $z_u$ on the pseudo-sensitive attributes $x^0_u$. Theorem 1 states the chain $0 \\le I(s;\\hat y_u) \\le I(s;z_u) \\le I(G_u;z_u) \\le \\sum_t I(x^0_t;z_u)$, and the framework is built to shrink the rightmost term: learn $x^0$ from non-sensitive attributes and graph structure, find real graph counterfactuals by nearest-neighbor search under the constraints $y_i = y_j$ and $x^0_i \\neq x^0_j$, and train with a weighted disparity loss between original and counterfactual embeddings. Because the counterfactual comes from real data rather than by perturbing a protected attribute, the method avoids unrealistic counterfactuals while still attacking the root cause of bias.","pith_inferences":["Beyond the paper, the bound suggests a practical fairness audit: with true protected labels available only for evaluation, one can estimate $I(s;z_u)$ and the pseudo-attribute sum on held-out nodes and use any violation as a warning that the fairness guarantee is not operating.","Beyond the paper, the real-data counterfactual search could replace sensitive-attribute perturbation in other counterfactual fairness pipelines, since it only needs pseudo-attributes and labels.","Beyond the paper, the dynamic weight update defines a simplex-constrained trade-off; generalizing $\\lambda_i$ to continuous or probabilistic pseudo-attributes would let the same idea apply to non-categorical protected proxies.","Beyond the paper, the Markov-chain assumption could be stress-tested by measuring residual dependence of $z_u$ on the graph after conditioning on $x^0_u$; if the residual is large, an additional debiasing step on graph structure would be needed."],"forward_implications":["If the representation ignores the pseudo-sensitive attributes, Theorem 1 forces the prediction's dependence on the hidden sensitive attribute toward zero through the chain of inequalities.","Sensitive attributes are not needed anywhere in training, only for evaluating fairness on the test set.","Counterfactuals are selected from the real dataset, so the method does not rely on unrealistic perturbations of a protected variable.","The per-pseudo-attribute weights $\\lambda_i$ are re-estimated during training, so fairness regularization concentrates on the attributes most responsible for bias while preserving utility.","The framework is compatible with different GNN backbones (GCN and GIN are tested), so it can be added to existing architectures."],"supporting_citations":[{"why":"It supplies the counterfactual-consistency training design that Fairwos follows for fair representation learning.","marker":"[12]"},{"why":"It motivates using real-data counterfactuals instead of perturbing sensitive attributes, because perturbing the protected variable creates unrealistic counterfactuals.","marker":"[16]"},{"why":"It introduces the idea of using related or proxy attributes as pseudo-sensitive attributes for fair classifiers without sensitive data.","marker":"[24]"},{"why":"It defines the fairness-without-sensitive-attributes graph setting and provides the state-of-the-art baseline that Fairwos is compared against.","marker":"[28]"},{"why":"It provides the pseudo-group clustering baseline (KSMOTE) used in the experimental comparison.","marker":"[38]"}],"fun_headline_variants":["Fair GNNs without sensitive data? New framework says yes","Pseudo-attributes unlock fairness in graph neural nets","Graph fairness via real-data counterfactuals, no sensitive labels","Fairwos: fair GNNs minus sensitive attributes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee assumes that a node's learned embedding depends on its graph neighborhood only through the pseudo-sensitive attributes, even though the actual GNN consumes the full graph, so this mediation link is asserted rather than tested.","fun_headline_variants_meta":{"raw":{"variants":["Fair GNNs without sensitive data? New framework says yes","Pseudo-attributes unlock fairness in graph neural nets","Graph fairness via real-data counterfactuals, no sensitive labels","Fairwos: fair GNNs minus sensitive attributes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00045,"raw_usage":{"total_tokens":2310,"prompt_tokens":1026,"completion_tokens":1284,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":642,"completion_tokens_details":{"reasoning_tokens":1228}},"tokens_in":642,"tokens_out":1284,"duration_ms":8969,"temperature":1.0,"reasoning_tokens":1228,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:33:38.213688+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train Fairwos on a public graph benchmark with the true sensitive attribute withheld and with it available only for evaluation; then estimate $I(s;z_u)$ and $\\sum_t I(x^0_t;z_u)$ on test nodes and test conditional independence of $z_u$ and $G_u$ given $x^0_u$. A trained model that violates the inequality, or whose embedding still depends on graph structure beyond the pseudo-attributes, shows the theorem's hypothesis is not met.","supporting_citations":[{"cited_title":"Agarwal, H","cited_arxiv_id":null,"evidence_quote":"It supplies the counterfactual-consistency training design that Fairwos follows for fair representation learning."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It motivates using real-data counterfactuals instead of perturbing sensitive attributes, because perturbing the protected variable creates unrealistic counterfactuals."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It introduces the idea of using related or proxy attributes as pseudo-sensitive attributes for fair classifiers without sensitive data."},{"cited_title":"Yan, H.-T","cited_arxiv_id":null,"evidence_quote":"It provides the pseudo-group clustering baseline (KSMOTE) used in the experimental comparison."}],"review_version":1}