acceptodds
Withdrawn from ICLR 2027

FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Graph neural networks (GNNs) are the standard for node representation learning and are increasingly deployed in high-stakes domains. However, the message-passing backbone of GNNs can amplify topological bias, raising concerns about the fairness of their predictions. We study group fairness at the level of downstream predictions, spanning node classification, link prediction, and node regression, and derive bounds on the demographic parity gap for any number of sensitive groups. For node classification, our bound is provably no looser than the closest prior bound; for link prediction, we are the first to bound the parity gap of the deployed, sigmoid-activated prediction rather than a pre-activation proxy; and for node regression, we establish the first such bound. Common to all three tasks, our analysis reveals two distinct sources of bias: the separation between group means and the within-group covariance of the final representations. Guided by this analysis, we embed fairness directly into the propagation mechanism by augmenting the convex feature-smoothing problem solved by APPNP with a convex constraint on the group-mean gap and a within-group covariance regularizer. Unfolding projected gradient descent on this problem yields FairProp, whose layers consist of a propagation step followed by a closed-form projection, and which provably converges linearly to the unique fair optimum. Across three tasks, we empirically demonstrate that FairProp, even with exact group-mean equalization, provides a strong inductive bias that attains excellent fairness-utility trade-offs relative to prevailing baselines on benchmark datasets.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Group Fairness, Algorithm Unrolling, Bias Analysis

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_BozCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies demographic parity gaps in node classification, link prediction, and node regression. Through theoretical analyses, the authors derive task-specific fairness bounds and point out group-mean separation and within-group covariance as key contributing factors. Motivated by these findings, the authors propose FairProp, an extension of APPNP that incorporates mean-equalization projection and within-group variance regularization. Experiments across all three tasks show that FairProp substantially reduces demographic parity gaps while preserving predictive performance, thereby improving the accuracy--fairness trade-off.

Critical strengths
  1. Comprehensive coverage of multiple graph learning tasks

A key strength of this paper is its comprehensive coverage of multiple graph learning tasks, including node classification, link prediction, and node regression (prior work primarily focuses on a single task, particularly node classification). Beyond empirical evaluation, the authors derive task-specific fairness bounds and provide a unified theoretical perspective that identifies group-mean separation and within-group covariance as key contributors to demographic parity gaps. Furthermore, FairProp addresses fairness across all three tasks, demonstrating the broad applicability of the theoretical findings and proposed approach.

  1. Clear improvements in the accuracy--fairness trade-off

Despite targeting multiple graph learning tasks, FairProp achieves substantial reductions in demographic parity gaps compared to baseline methods. As shown in Table 1, FairProp consistently improves fairness across widely used graph fairness datasets. Furthermore, it maintains comparable predictive performance in 9 of the 10 reported settings across Tables 1--3 (except for GermanCredit node regression). These results highlight FairProp’s effectiveness in improving the accuracy--fairness trade-off across diverse graph learning tasks.

Critical weaknesses
  1. Missing equal opportunity evaluation

Of the 18 baseline papers, 14 report both demographic parity and equal opportunity gaps, as these metrics capture complementary aspects of group fairness (overall positive prediction rates vs. true positive rates). However, this paper evaluates only demographic parity, despite equal opportunity being well-defined for node classification (or link prediction). This omission is particularly concerning because FairProp explicitly targets demographic parity, while its impact on equal opportunity remains unexplored. Therefore, the authors should provide an empirical or theoretical analysis of equal opportunity to ensure a more comprehensive fairness evaluation consistent with prior work, rather than deferring this issue to future work.

  1. Dependence on sensitive-group availability

While many fairness-aware GNN methods assume access to node-level sensitive attributes, either for training nodes or for all nodes, FairProp appears particularly reliant on this information, as it explicitly aligns group means and regularizes within-group covariance. This raises concerns about its applicability when sensitive attributes are unavailable or partially observed. The authors should clarify the extent to which FairProp requires sensitive attributes and evaluate its robustness to missing or inaccurate group information, for instance, by varying the error rate of sensitive-attribute assignments or incorporating a sensitive-attribute prediction module.

Questions for authors
  1. Does FairProp require sensitive-attribute information for all nodes, or is access to this information for training nodes sufficient?

  2. Can the core ideas of FairProp (mean-equalization projection and within-group variance regularization) be extended to other GNN architectures? While APPNP appears to have been chosen for its decoupling of feature propagation and prediction, it would be helpful to clarify whether FairProp is inherently limited to APPNP or can be generalized to other architectures.

Reviewer_JL1bOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes FairProp, an APPNP-based architecture that inserts a differentiable projection after each propagation step to equalize group means of node representations. An optional quadratic regularizer controls within-group variance, and a slab relaxation permits nonzero mean separation. The method is derived by unrolling projected gradient descent on a strongly convex diffusion objective. The paper also derives representation-based bounds for soft classification disparity, sigmoid link-score disparity, and mean disparity under linear regression readouts. Experiments across three tasks report substantial fairness improvements with generally modest utility losses relative to APPNP and a broad collection of fairness baselines.

Critical strengths
  1. The propagation mechanism has a clear optimization interpretation. The exact mean-equalization projection is inexpensive, differentiable, and compatible with multiple readouts. The strongly convex formulation and convergence analysis provide a useful foundation for designing fairness interventions within propagation rather than relying entirely on an additional training loss.

  2. The reported classification results suggest a useful practical trade-off. For example, Table 1 reports Credit accuracy changing from 80.9 to 80.8 while the demographic parity gap falls from 3.5 to 0.4 percentage points. The comparison spans several datasets and many baselines, with results averaged over 20 runs. These observations make the approach worth investigating, subject to resolving the protocol concerns below.

Critical weaknesses
  1. The supplied implementation does not consistently implement the stated experimental protocol, which prevents me from accepting the cross-task empirical claims as currently supported. In run_lp.py, the final evaluation passes the original full graph to evaluate_lp; evaluation.py then encodes its edge_index. Consequently, held-out positive test edges are available during test-time message passing. In addition, evaluate_lp thresholds sigmoid scores at 0.5 before computing disparity, whereas Remark 1 and Proposition 5 explicitly define the reported link-prediction metric using probabilities without a threshold. Appendix G.2 and Table 4 also identify gender as the sensitive attribute for Pokec, while the supplied classification and regression loaders use region. These are material differences in the task and fairness quantity, rather than implementation details. I cannot determine whether the tables were generated using this code or a different version. A reconciled implementation and results under a consistent protocol are necessary to assess the reported advantage.

  2. The theoretical results do not establish the full prediction-level fairness interpretation used to motivate the empirical claims. Proposition 2 and Corollary 3 bound differences of mean soft scores, while the classification metric in Section 2 uses deterministic hard labels. Equal group means and arbitrarily small covariance can still coexist with a fixed hard-label disparity when scores lie near the decision boundary; a margin assumption or a more limited claim is needed. For regression, the zero mean-gap guarantee applies to the node population used in the projection. The supplied evaluate_nr computes fairness on all nodes but MAE only on test nodes, so zero full-graph disparity does not establish zero disparity on the held-out subset. Finally, Section 4.4 argues that projecting at every step improves on an end-only projection, but the benchmark experiments do not directly compare these variants under matched training. This leaves the practical benefit of the central architectural choice insufficiently isolated.

Questions for authors
  1. Which code version produced Table 2? Please report AUC and the unthresholded sigmoid-score parity gap when held-out test edges are excluded from the encoder adjacency, using the same permitted graph information and fairness definition for all baselines. This is a request to verify the existing result.

  2. Which sensitive attribute was actually used for the Pokec results: gender or region? Please reconcile the manuscript with the loaders, specify the node population used for fairness evaluation for each method, and report test-subset classification and regression disparities alongside the full-graph values. This would clarify whether the reported fairness gains hold on the population used to assess utility.

  3. Please clarify the scope of the classification guarantee and provide a matched benchmark comparison of per-step projection with a differentiable end-only projection trained end to end. Does the proposed method retain an advantage under the same backbone, propagation depth, split, and model-selection rule? This comparison could materially change my assessment of the architectural contribution.

Reviewer_bkYeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes FairProp, which incorporates projections that equalize group means into APPNP propagation. The paper derives bounds on prediction disparity, introduces variance regularization, and proves convergence of the constrained propagation. Experiments cover node classification, link prediction, and node regression.

Critical strengths

S1. The proposed method uses a simple, differentiable projection with low computational overhead. The propagation has a clear optimization interpretation and a linear convergence guarantee.

S2. Experiments show substantial reductions in parity gaps across three tasks, while maintaining predictive performance close to APPNP on most datasets.

Critical weaknesses

W1. The bounds and experiments concern different quantities or populations. The classification bounds concern soft predictions, whereas experiments measure DP on hard predictions. Equalizing means over the full graph does not guarantee zero mean gap on test nodes. Similarly, the uniform pair distribution in Proposition 5 may differ from the link evaluation distribution.

W2. The contribution beyond FMP and FairRARI needs stronger experimental support. The paper does not establish whether projection at every step improves prediction performance over a final projection. The main results also use projection alone, leaving the practical benefit of variance regularization unclear.

Questions for authors

Q1. Do the bounds apply to hard predictions and sampled link pairs?

Q2. Is Table 3’s zero mean gap measured on test nodes?

Q3. How does FairProp compare with a final projection or a mean gap penalty?

Q4. Does variance regularization help within Proposition 7’s convergence regime?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.