Source-linked AI summary
FMP: Toward Fair Graph Message Passing against Topology Bias
Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, Xia Hu
TL;DR
The fairness effect of GNN message passing remains underexplored, despite concerns that topology bias contributes to biased node representations. The paper analyzes this mechanism and proposes FMP, which combines fairness and prediction objectives in message passing. On three real-world datasets, FMP achieves lower prediction bias with competitive prediction performance.
Problem
Prior fair-representation methods refine training losses, while the fairness effect of message passing itself remains underexplored.
Source: §1 · p. 1Method
FMP uses sensitive-attribute information in message passing and a unified optimization framework integrating fairness and prediction objectives.
Source: §1 · pp. 1–2Results
FMP achieves the lowest prediction bias in demographic parity and equal opportunity across datasets, reducing demographic parity by 49.69% in Pokec-z versus the lowest-bias baseline.
Source: §5.2.2 · p. 7Takeaways & Limitations
Experiments on three real-world node-classification datasets report that FMP mitigates bias while preserving prediction performance, with negligible computation overhead.
Source: §1 · p. 2, §5.2.2 · p. 7The synthetic-graph analysis assumes node attributes follow a Gaussian mixture model with group-specific means and covariance matrices.
Source: §3 · p. 3
Abstract
from arXiv · showhide
Despite recent advances in achieving fair representations and predictions through regularization, adversarial debiasing, and contrastive learning in graph neural networks (GNNs), the working mechanism (i.e., message passing) behind GNNs inducing unfairness issue remains unknown. In this work, we theoretically and experimentally demonstrate that representative aggregation in message-passing schemes accumulates bias in node representation due to topology bias induced by graph topology. Thus, a \textsf{F}air \textsf{M}essage \textsf{P}assing (FMP) scheme is proposed to aggregate useful information from neighbors but minimize the effect of topology bias in a unified framework considering graph smoothness and fairness objectives. The proposed FMP is effective, transparent, and compatible with back-propagation training. An acceleration approach on gradient calculation is also adopted to improve algorithm efficiency. Experiments on node classification tasks demonstrate that the proposed FMP outperforms the state-of-the-art baselines in effectively and efficiently mitigating bias on three real-world datasets.
1. Introduction
Topology bias in graphs can cause message passing to amplify representation bias, yet how message passing affects fairness remains underexplored. FMP addresses this gap with a fairness- and prediction-aware message-passing scheme, evaluated on three real-world datasets.
1. Introduction
- Same-sensitive-attribute nodes are more likely to connect, and their aggregation-induced representation similarity is a major source of graph representation bias.The paper calls this connectivity pattern topology bias.Source: §1 · p. 1
- Existing fair-representation methods use regularization, adversarial debiasing, or contrastive learning, while the fairness effect of message passing itself remains underexplored.The paper asks whether message passing can retain useful neighbor information while mitigating bias inherited from topology.Source: §1 · p. 1
- The authors theoretically show that aggregation inevitably accumulates representation bias when topology bias is large, then formulate FMP to combine fairness and prediction objectives.FMP uses Fenchel conjugate and gradient descent to generate fair-and-predictive representations.Source: §1 · p. 1
- FMP integrates graph smoothness and fairness in a unified optimization framework, with an acceleration method to reduce gradient computational complexity.The introduction reports theoretical and empirical validation of the acceleration method.Source: §1 · p. 2
- FMP achieves a superior trade-off between prediction performance and fairness versus state-of-the-art methods on three real-world datasets, with negligible computation overhead.Experiments evaluate its effectiveness and efficiency on node classification tasks.Source: §1 · p. 2
2. Preliminaries
The preliminaries establish graph and node-feature notation, describe GNN aggregation as neighbor-based feature updating, and situate representative aggregation in graph signal denoising. They also define label and sensitive homophily and note that the message-passing relationship to sensitive homophily lacks fundamental understanding.
2. Preliminaries
- A graph is represented by its adjacency matrix, with self-inclusive neighborhoods, node features, and a normalized sensitive-attribute incident vector.Nodes have binary sensitive attributes, and feature aggregation uses graph topology and neighboring features.Source: §2 · p. 2, §2.1 · p. 2
2.1. GNNs as Graph Signal Denoising
- Representative GCN and SGC aggregation is connected to graph signal denoising with Laplacian regularization.The passage states that aggregation applies a normalized self-loop adjacency matrix to transformed features and relates this to one-step gradient descent.Source: §2.1 · p. 2
2.2. Label and Sensitive Homophily in Graphs
- Label and sensitive homophily measure the fractions of edges joining nodes with matching labels or sensitive attributes, respectively.The preliminaries identify a missing fundamental understanding of message passing’s relationship to sensitive homophily.Source: §2.2 · p. 3
3. Graph Topology Enhances Bias in GNNs
The section quantifies when GCN-like message passing enhances representation bias and relates that effect to sensitive homophily and graph structure. Its sufficient condition links bias enhancement to the reduction in group-mean distance and the groups’ connection degrees.
3. Graph Topology Enhances Bias in GNNs
- Under the stated Gaussian-mixture and graph assumptions, GCN-like message passing enhances bias when (ν1 − ν2)^2 min{ζ1, ζ2} > 1.Here, ν1 − ν2 is the reduction coefficient for the distance between sensitive-group mean attributes, and ζ1 and ζ2 are their connection degrees.Source: §3 · p. 4
- Sufficiently high sensitive homophily can enhance representation bias; as ϵsens approaches 1, the stated condition has ν1 − ν2 = 1 and min{ζ1, ζ2} > 1.The authors also report that bias enhancement depends on representation geometry: mean distance and covariance, with message passing reducing mean distance in a way that can work against fairness.Source: §3 · p. 4
- Larger graphs can enlarge bias because group connection degrees grow with node count, making the sufficient bias-enhancement condition easier to satisfy.The analysis says the mean distance approximately remains constant as n increases.Source: §3 · p. 4
- Higher edge density can enlarge bias because connection degrees rise with density while the mean distance approximately remains constant.The resulting sufficient condition is more readily satisfied in dense graphs.Source: §3 · p. 4
- A more balanced sensitive-attribute ratio can enlarge bias because the difference between intra- and inter-group connection probabilities increases.The text links this difference to aggregation using more neighbors with the same sensitive attribute.Source: §3 · p. 4
4. Fair Message Passing
FMP formulates message passing to pursue graph smoothness and fair node representations together, then solves the resulting optimization with a structured propagation-and-debiasing algorithm. Its analysis describes the debiasing steps and reports lower extra computation than direct gradient calculation.
4.1. The Optimization Framework
- FMP frames aggregation as jointly preserving graph smoothness and fair node representations, with regularization coefficients controlling their trade-off.The smoothness term encourages connected nodes to have similar representations; the fairness term corresponds to demographic parity in predicted probabilities across sensitive groups.Source: §4.1 · pp. 4–5
4.2. Algorithm for Fair Message Passing
- FMP uses Fenchel conjugacy to turn the fairness objective into a bilevel optimization, then applies a predict-then-correct algorithm in closed form.Its propagation phase uses a skip connection; subsequent steps update aggregated features, reshape a probability-space perturbation, and mitigate feature bias.Source: §4.2 · p. 5
4.3. FMP Analysis
- The analysis interprets FMP as conventional aggregation followed by low-rank debiasing in probability space, transformed back to representation space.The dual variable gives the perturbation direction, and nodes with different sensitive attributes receive opposite perturbations.Source: Figure 2 · p. 5, §4.3 · p. 6
- FMP’s extra perturbation computation is O(ndout), compared with O(n^2dout) for directly calculating the back-propagation gradient tensor.The paper describes the extra cost as negligible on real-world graphs, where n is far smaller than the number of edges m; it also says the method has no trainable weights during forwarding.Source: §4.3 · p. 6
5. Experiments
FMP is evaluated through synthetic bias-enhancement experiments and node classification on three real-world datasets. It achieves the lowest prediction bias across those datasets, with competitive accuracy and a better DP–accuracy trade-off than regularization and adversarial debiasing in many tested models.
5. Experiments
- The experiments assess FMP’s effectiveness and efficiency against state-of-the-art methods on real-world datasets, reporting a superior fairness–prediction trade-off with negligible computation overhead.The reported real-world evaluation compares prediction performance and fairness metrics.Source: §5 · p. 6
5.1. Synthetic Experiments
- Higher sensitive homophily generally corresponds to greater bias enhancement, as do higher graph density, larger node count, and a more balanced sensitive-attribute ratio.The synthetic experiments measure bias enhancement using demographic-parity difference during message passing.Source: §5.1 · pp. 6–7
5.2.1. EXPERIMENTAL SETTINGS
- The real-world node-classification evaluation uses Pokec-z, Pokec-n, and NBA, measuring accuracy alongside demographic parity and equal opportunity.Pokec datasets use region as the sensitive attribute and working field as the label; NBA uses nationality and above-median salary.Source: §5.2.1 · p. 7
5.2.2. EXPERIMENTAL RESULTS
- Existing GNNs underperform MLP on fairness metrics across all three datasets; on Pokec-z, MLP demographic parity is lower than GAT, GCN, SGC, and APPNP by 32.64%, 50.46%, 66.53%, and 58.72%, respectively.The authors attribute higher prediction bias to aggregation among same-sensitive-attribute nodes and topology bias in graph data.Source: §5.2.2 · p. 7
- FMP achieves the lowest demographic parity and equal-opportunity prediction bias on all three datasets, with best NBA accuracy and comparable accuracy on Pokec-z and Pokec-n.Its demographic parity reductions versus the lowest-bias baseline are 49.69%, 56.86%, and 5.97% on Pokec-z, Pokec-n, and NBA, respectively.Source: §5.2.2 · p. 7
- FMP attains a better DP–accuracy trade-off than adversarial debiasing and regularization for many GNNs and MLPs.Figure 4 compares the trade-off curves on three real-world datasets; curves closer to the bottom-right indicate better trade-offs.Source: §5.2.2 · p. 8, Figure 4 · p. 8
6. Related Works
Prior graph-fairness methods address bias through approaches such as regularization, adversarial debiasing, Bayesian methods, fair walks, and contrastive learning. The paper focuses on the comparatively underexplored role of message passing in fairness and develops FMP to use neighbor information while debiasing representations.
6. Related Works
- Spatial GNNs explicitly aggregate neighbors’ information, while spectral GNNs define graph convolution through graph theory.The discussion names GCN and GAT as spatial-based examples and cites spectral-based approaches.Source: §6 · p. 8
- Graph-fairness work includes fair walks, adversarial debiasing, Bayesian approaches, and contrastive learning, but these approaches are described as overlooking message passing’s fairness role.The cited approaches include fair walk, adversarial debiasing [Dai & Wang, 2021], and contrastive learning [Agarwal et al., 2021].Source: §6 · p. 8
- The paper reports that aggregation can enhance representation bias under topology bias and proposes an efficient, transparent FMP scheme that uses neighbor information while debiasing representations.Source: §6 · p. 8
7. Conclusion
The paper concludes that message passing can enhance representation bias under large sensitive homophily, while FMP aims to learn fair representations without sacrificing prediction performance. The supplied proof excerpt also introduces a categorical-sensitive-attribute case and an entropy bound based on pairwise KL divergence.
7. Conclusion
- The authors conclude that message passing enhances representation bias under large sensitive homophily and that FMP learns fair representations while preserving prediction performance.They report real-world node-classification experiments demonstrating effectiveness and efficiency against state-of-the-art baselines.Source: §7 · p. 8
B. Proof of Theorem 1
- The proof extends the analysis to categorical sensitive attributes with class priors and Gaussian conditional node-attribute distributions.The excerpt defines the marginal feature distribution as a mixture of the class-conditional Gaussians.Source: B. Proof of Theorem 1 · p. 11
- The proof states that the entropy of the mixed Gaussian distribution can be upper bounded using pairwise KL divergence.It invokes an inequality based on a variational lower bound and the entropy–KL relationship.Source: B. Proof of Theorem 1 · pp. 11–12
C. Proof of Theorem 2
The proof models message passing on a synthetic graph through within- and between-group connection probabilities and conditional node-feature distributions. It derives a condition under which aggregation increases the KL divergence between sensitive-group representations, corresponding to increased bias.
C. Proof of Theorem 2
- The synthetic-graph setup makes edges depend on sensitive attributes, with node count, density, sensitive homophily, and group ratio determining the graph-generation setting.Conditional on sensitive attributes, the excerpt assumes edge generation is independent of node attributes.Source: C. Proof of Theorem 2 · pp. 12–13
- Aggregation reduces the covariance of node attributes through averaging, and the proof represents each sensitive group’s aggregated features with Gaussian distributions.The derivation then compares KL divergence for the original and aggregated group distributions.Source: C. Proof of Theorem 2 · pp. 13–14
- The proof derives that bias increases after message passing when (ν1 − ν2)^2 min{ζ1, ζ2} > 1.The condition follows from comparing KL divergence between the aggregated sensitive-group distributions with the original distributions.Source: C. Proof of Theorem 2 · p. 14
D. More Details on FMP Derivation
The derivation casts fairness as a prediction-probability difference, then uses Fenchel conjugacy and a predictor-corrector iteration to implement fair message passing. FMP combines propagation with skip connections and iterative bias mitigation.
D.1. Proof on Fairness Objective
- The fairness objective is expressed as the average prediction-probability difference between sensitive groups.The expression compares predicted probabilities conditioned on the two sensitive-attribute values.Source: §D.1 · p. 14
D.2. Fenchel Conjugate
- Fenchel conjugacy transforms the fairness objective into a variational representation and the original problem into a bi-level optimization.The text identifies the conjugate of a general convex function as the transformation tool.Source: §D.2 · p. 14
D.3. Fair Message Passing Scheme.
- The fairness proximal operator is an element-wise projection onto an l∞ ball with radius λ_f.The scheme also defines normal aggregation with a skip connection to transformed input features.Source: §D.3 · p. 15
- FMP uses propagation with a skip connection followed by bias mitigation through feature updates and primal-dual perturbation updates.The primal-dual iteration takes a gradient descent step, a proximal ascent step, and a second gradient descent step.Source: §D.3 · pp. 14–15
E. More Discussions on Message Passing
The discussion analyzes when message passing amplifies representation bias and gives supporting derivations for the fairness-gradient and proximal computations. Larger sensitive homophily, graph size, and connection density can make bias enhancement easier to satisfy.
E. More Discussions on Message Passing
- For sufficiently large sensitive homophily, aggregation preserves the groups’ mean distance while reducing covariance, satisfying the stated bias-enhancement condition.The analysis gives ν1 = 1, ν2 = 0 and ζ1, ζ2 > 1 in this case.Source: E. More Discussions on Message Passing · p. 15
- At fixed graph density, larger node counts increase average degree and concentrate aggregated representations, making bias enhancement easier to satisfy.The mean distance is described as nearly constant while ζ1 and ζ2 grow roughly with node count.Source: E. More Discussions on Message Passing · p. 16
- At fixed node count, higher connection density concentrates representations by increasing the amount of same-sensitive-attribute neighbor information aggregated.The analysis says the mean distance remains constant as density rises.Source: E. More Discussions on Message Passing · p. 16
F. Proof of Theorem 3
- The fairness-gradient derivation uses the row-wise softmax derivative and chain rule to express gradients with respect to node representations.The softmax Jacobian is given as yI_N − y^⊤y.Source: F. Proof of Theorem 3 · pp. 16–17
G. Proof of Proposition 1
- For the l1 fairness norm, the conjugate uses the l∞ dual norm, and the derivation proceeds through element-wise subproblems.The section then examines the proximal operator of that conjugate.Source: G. Proof of Proposition 1 · p. 17
H. Dataset Statistics
The appendix reports dataset characteristics, relates several message-passing schemes to graph-signal denoising, and situates FMP among graph fairness work. Across the three real-world datasets, sensitive homophily exceeds label homophily.
H. Dataset Statistics
- Pokec-n, Pokec-z, and NBA are the three node-classification datasets, and each has sensitive homophily higher than label homophily.Table 3 is identified as reporting statistical information on the datasets.Source: H. Dataset Statistics · p. 17, Table 3 · p. 18
I. More Discussion on GNNs as Graph Signal Denoising
- GAT aggregation is described as attention-based denoising under a condition linking its attention scores to local-smoothness coefficients, while APPNP corresponds to an exact solution and one gradient-descent step.The GAT equivalence condition is that c_i + c_j is equivalent to e_ij.Source: §I · p. 18
J. Related Works
- Prior fair-graph methods include adversarial, Bayesian, PAC-Bayesian, and contrastive approaches, while FMP examines topology’s role in representation bias and proposes fair message passing.The passage says prior approaches ignore graph topology in terms of fairness.Source: J. Related Works · pp. 18–19
K.1. More Synthetic Experimental Results
The appendix reports synthetic bias trends, hyperparameter effects, and runtime comparisons. It finds that bias enhancement varies with graph conditions, fairness and smoothness settings affect the fairness–accuracy trade-off, and FMP is faster than APPNP in the reported comparisons.
K.1. More Synthetic Experimental Results
- Higher sensitive homophily generally increases bias enhancement; higher density, larger graphs, and balanced sensitive-group ratios also correspond to greater enhancement.The synthetic results report these trends across different initial covariance matrices.Source: §K.1 · p. 19
K.2. Hyperparameter Study
- Accuracy and demographic parity are highly sensitive to smoothness: larger values usually raise accuracy but also prediction bias on Pokec-n and Pokec-z, whereas NBA shows the opposite accuracy trend.The passage attributes the difference to whether graph data has high label homophily.Source: §K.2 · p. 19, Figure 6 · p. 20
- An appropriate fairness hyperparameter improves the fairness–prediction trade-off by setting a suitable perturbation-vector update step size.The hyperparameter controls the update step size in probability space.Source: §K.2 · p. 19
K.3. Running Time Comparison
- FMP has 46.97% and 15.03% time overhead over MLP on Pokec-n and Poken-z, respectively; versus APPNP, its running time is lower with 64.07% and 41.45% time overhead.The running-time comparison covers Pokec-n and Poken-z.Source: §K.3 · p. 20, Figure 7 · p. 20
- Regularization adds little runtime over vanilla methods, while GCN with adversarial debiasing incurs 88.58% time overhead over vanilla GCN.The regularized GCN overhead is 6.41%.Source: §K.3 · p. 20