Fairness-aware Message Passing for Graph Neural Networks

1 Introduction

• GNNs may inherit sensitive-attribute biases, and message passing can worsen group separation because connected nodes are often in the same sensitive group.This can limit adoption in applications such as healthcare, credit scoring, and job hunting.Source: §1 · p. 1
• Existing fair-GNN methods adapt regularization, adversarial debiasing, contrastive learning, or feature and topology changes, but their effects with message passing remain difficult to understand.The paper identifies message passing as important to both utility and bias.Source: §1 · p. 1
• GMMD derives message passing from an optimization objective combining graph smoothness and fairness regularization, with weights that trade off utility and fairness.It encourages aggregation from nodes in different sensitive groups and subtraction of representations from the same group; the paper also proposes GMMD-S based on its theoretical analysis.Source: §1 · p. 2
• The authors report that GMMD achieves a superior trade-off between prediction performance and fairness on real-world datasets.They also report theoretical analysis of downstream fairness metrics.Source: §1 · p. 2

Graph Neural Networks

• Most GNN variants use message passing for pattern extraction and interaction modeling, and many can be viewed as gradient steps for graph signal denoising.The passage distinguishes spectral-based from spatial-based approaches, including GCN [4], GraphSage [3], APPNP [7], and GAT [32].Source: §2 · p. 2

Fairness in Graph Learning

• Prior fair-GNN work includes adversarial debiasing that prevents sensitive-attribute prediction from learned fair node representations [9] [16], fair random-walk network embeddings, and fairness-conscious contrastive learning [39].FMP [40] proposes fair message passing with transparency, but its bias-mitigation process lacks direct theoretical understanding based on fairness metrics.Source: §2 · p. 2
• The paper identifies insufficient understanding of how fairness-aware message passing debiases GNN predictions and proposes an approach with theoretical analysis.The cited prior work includes methods that either omit a fairness-aware message-passing component or lack a thorough account of its effect.Source: §2 · p. 2

3 Notations and Problem Definition

• The graph is an undirected attributed graph G = (V, E, X), with node features X and adjacency matrix A; the setup defines a normalized Laplacian and neighbor sets.The binary sensitive attribute partitions nodes into groups S0 and S1.Source: §3 · pp. 2–3
• Many popular GNN message-passing schemes can be understood as gradient steps for graph signal denoising with smoothness regularization.GCN [4], GAT [32], and APPNP [7] are given as examples; these models may inherit biased representations from graph structure [10].Source: §3 · p. 3
• For fair semi-supervised node classification, labeled nodes provide training labels, while the model predicts unlabeled-node labels subject to accuracy and sensitive-attribute fairness criteria.The sensitive attribute is represented as s over the nodes.Source: §3 · p. 3

4.1 Fairness-aware Message Passing - GMMD

• GMMD performs one-step gradient descent on an objective combining graph smoothness with MMD-based fairness regularization.Its update aggregates representations across sensitive groups and subtracts representations within the same group.Source: §4.1 · pp. 3–4

4.2 Theoretical Analysis

• For binary classification, minimizing representation discrepancy is equivalent to minimizing demographic-parity difference, and GMMD is shown to minimize an upper bound on that fairness metric.The analysis considers two message-passing layers and connects optimizing the third MMD term to reducing the upper bound.Source: §4.2 · p. 5

4.3 Simple Fairness-aware Message Passing - GMMD-S

• GMMD-S simplifies the fairness regularizer to the cross-group MMD term, avoiding same-group pairwise similarity calculations while retaining a provable route to minimizing demographic-parity difference.The paper describes this simplification as improving algorithmic efficiency.Source: §4.3 · p. 5

4.4 Model Framework and Training Method

• The model transforms input features with an MLP, applies GMMD or GMMD-S message passing for K layers, then uses Softmax predictions and cross-entropy training.The method can replace the GCN-style propagation component with other GNN backbones, and balanced sensitive-group sampling is used for efficient training.Source: §4.4 · pp. 5–6

5.1 Experimental Setup

• Experiments cover German, Credit, and Bail with two-layer GCN backbones, standard splits, utility and group-fairness metrics, and five-run averages.Utility is measured with AUC, F1-score, and Accuracy; fairness with demographic parity and equal opportunity.Source: §5.1 · p. 6

5.2 Overall Performance Comparison

• On real-world graphs, GMMD and GMMD-S achieve the best average rank across all datasets and evaluation metrics, with ranks 2.4 and 2.6, indicating a better utility-fairness trade-off.Source: §5.2 · pp. 6–7

5.3 Parameter Analysis and Empirical Analysis on Theory

• The effect of smoothness weight λs differs by graph: increasing it stabilizes accuracy on Bail but can lower German accuracy and worsen its ∆DP.The authors recommend selecting λs and λf with homophily and sensitive homophily in mind; they report useful ranges of 0.5–1.0 for λs and 1–5 for λf.Source: §5.3 · p. 7
• With increasing K, utility first rises then falls while ∆DP and ∆EO drop; the authors suggest K=2–4 to balance fairness and accuracy.The utility decline at larger K is attributed to over-smoothing.Source: §5.3 · p. 8, Figure 2 · p. 8
• The analysis relates inter-group kernel similarity to fairness: ∆DP decreases as similarity increases, while the text also describes GMMD minimizing inter-group similarity to mitigate bias.The authors note that smoothness regularization can initially improve accuracy while producing unfair predictions.Source: §5.3 · p. 8, Figure 3 · p. 8
• The ablation finds that smoothness alone supports utility but introduces bias, fairness regularization alone improves fairness, and the full model achieves the best performance.With sampling, the model has the same reported average rank as training without sampling: 2.4.Source: §5.3 · p. 8
• GMMD and GMMD-S outperform FairVGNN on utility and fairness in most cases with GIN and GAT backbones, demonstrating framework flexibility.The reported GIN and GAT results are on Bail; other dataset results are in the appendix.Source: §5.3 · pp. 8–9, Table 3 · p. 9

5.5 Visualization and Case Study

• Same-label node pairs have larger kernel similarity, and GMMD assigns higher weights to same-label edges across sensitive groups to preserve utility.In the case-study panels, node color indicates class, shape indicates sensitive group, and blue-line width scales with kernel similarity.Source: §5.5 · p. 9, Figure 4 · p. 9

6 Conclusion

• GMMD derives fairness-aware GNN message passing from an optimization problem with smoothness and fairness constraints.The paper interprets the mechanism as aggregating representations from different sensitive groups while subtracting representations from the same group.Source: §6 · p. 9
• The authors state that theoretical analysis supports GMMD's downstream fairness performance.Source: §6 · p. 9
• Experiments on graph benchmarks are reported to validate GMMD's utility and fairness performance.Source: §6 · p. 9

A.1 Derivation of Fairness-aware Message Passing based on MMD

• GMMD's fairness-aware message passing is derived by taking a one-step gradient of the objective with smoothness and MMD fairness terms.The derivation defines kernel similarity as kij = e−α∥Fi−Fj∥2.Source: §A.1 · p. 13

A.2 Derivation of Simplified Fairness-aware Message Passing

• GMMD-S uses a simplified fairness term and derives its message passing with a one-step gradient; its coefficients weight cross-group pairs by kernel similarity.Source: §A.2 · pp. 13–14

B The Training Algorithm

• Training encodes node features with an MLP, samples nodes for fairness regularization, applies K fairness-aware GNN layers, then updates parameters with cross-entropy loss.Source: B The Training Algorithm · p. 14

C Different Backbones

• The framework replaces its base message-passing term with another GNN's message passing, a change the authors say generalizes to most GNN models.Source: C Different Backbones · p. 14, §C.2 · p. 15

C.1 GMMD with GIN

• For GIN, GMMD combines the GIN message-passing operation with the fairness-aware formulation.Source: §C.1 · p. 14

C.2 GMMD with GAT

• For GAT, attention scores form an adjacency matrix used in GMMD; GMMD-S can also use GAT by replacing P with eP.Source: §C.2 · pp. 14–15

D.1 Time Complexity Analysis

• The complexity analysis uses a K-layer GCN backbone, while the framework is described as agnostic to the choice of GNN model.The passage defines |E| as the number of edges.Source: §D.1 · p. 15
• GMMD and GMMD-S add fairness-passing costs of O(c^2KN^2) and O(c^2KN_0N_1), respectively; equal sampling from each sensitive group is used to improve efficiency.The total iteration complexities also include backbone-related terms.Source: §D.1 · p. 15

E Fairness Metric for Group Fairness

• Equal opportunity measures parity in positive predictions among positive instances, while demographic parity measures prediction independence from the sensitive attribute.The paper uses the absolute differences between groups for both metrics; smaller differences indicate greater fairness.Source: E Fairness Metric for Group Fairness · p. 15

F.1 Proof of Theorem 4.1

• Theorem 4.1 relates minimizing representation discrepancy between sensitive groups to minimizing demographic-parity difference in the model prediction for binary classification.The proof identifies the final representation before softmax as the relevant model output and considers K=2.Source: §F.1 · pp. 16, 18
• Theorem 4.1's proof uses binary classification and a Lipschitz-continuous softmax, with L<1 as the stated Lipschitz condition.The proof also defines deviation relative to the mean feature value.Source: §F.1 · p. 16

F.2 Proof of Theorem 4.2

• Theorem 4.2 states that, for an arbitrary graph, the representation discrepancy after fairness-aware message passing is upper-bounded when K=2.The stated bound depends on group mean representations and maximal feature deviation; the proof assumes a two-layer GNN.Source: §F.2 · pp. 18–19

G.1 Datasets Details and Statistics

• Table 4 reports homophily and heterophily statistics for the graph datasets used in the paper.Source: Table 4 · p. 20

G.1.1 Homophily Ratio based on labels

• Edge homophily is the proportion of edges connecting nodes with the same class.Source: §G.1.1 · p. 20

G.1.2 Sensitive Attribute Homophily

• Sensitive-attribute homophily measures same-attribute edges; the paper notes that higher values may produce more similar within-group representations and biased predictions.Source: §G.1.2 · p. 20

G.2 Datasets

• The German, Bail, and Credit graphs represent bank clients, defendants released on bail, and credit-card users, respectively, with gender, race, and age as sensitive attributes.Source: §G.2 · p. 21

G.3 Baselines

• Fairness baselines span counterfactual stability (NIFTY [39]), feature and topology debiasing (EDITS [10]), and fair prediction or message passing (FairGNN [9], FairVGNN, FMP [40], MMD).Source: §G.3 · p. 21

G.4 Setup and Hyper-parameter settings

• Experiments use two-layer GNNs, Adam, validation-based hyperparameter selection, and dataset-specific sample counts of 100, 200, and 6000 for German, Bail, and Credit.The methods use official or PyTorch Geometric baseline implementations and grid search.Source: §G.4 · pp. 21–22

H.1 Additional Results of Different Backbones

• Across different backbones, GMMD variants achieve strong utility and fairness performance compared with FairVGNN, supporting the framework's flexibility across message-passing approaches.Source: §H.1 · p. 22, Table 5 · p. 22

H.2 Additional Hyper-parameter Analysis

• Larger α values promote fairness with little influence on accuracy, while increasing M first improves accuracy and then can reduce it; M=2 or M=4 is sufficient for good fairness performance.The α and M analyses vary α over {0.1, 0.3, 0.7, 1} and M over {1, 2, 4, 6}.Source: §H.2 · pp. 22–23, Figure 5 · p. 22, Figure 6 · p. 23

H.3 Addtional Results on Case Study

• In most case-study examples, GMMD assigns higher weights to inter-sensitive-group edges connecting nodes with the same label, which the authors link to retaining utility while mitigating fairness issues.Source: §H.3 · p. 23, Figure 7 · p. 23

H.4 Running Time Comparison

• The running-time comparison reports efficiency for GMMD and GMMD-S and indicates their superior performance does not result from greater model complexity.The table reports running time, with seconds as its unit.Source: Table 6 · p. 23, §H.4 · p. 24

• GMMD and its efficient, simplified variant GMMD-S are proposed to mitigate biased GNN predictions.Source: I Additional Discussion on Potential… · p. 24
• The current message-passing method is derived from smoothness and fairness regularization using Maximum Mean Discrepancy (MMD).Source: I Additional Discussion on Potential… · p. 24
• Exploring other fairness regularization terms for learning fair graph representations remains a future direction.Source: I Additional Discussion on Potential… · p. 24
• Further theoretical analysis of utility performance could clarify how to control the utility–fairness trade-off.Source: I Additional Discussion on Potential… · p. 24