CS Paper Radar

Subgraph Filtering for Fair Graph Neural Networks

Haohui Lu, jiyuan Tian, Fangyu Zhou, Shahadat Uddin

cs.LG ·submitted 2026-08-26 22:40 UTC · v1
benchmark

Abstract

Graph neural networks (GNNs) can exhibit unfair behavior even when sensitive attributes are excluded from node features, because graph topology and message passing propagate group-correlated signals under sensitive homophily. Existing fairness-aware GNN methods mainly constrain representations or prediction distributions at a global level, without explicitly controlling the local structural pathways through which biased information propagates during aggregation. We propose Subgraph Filtering for Fair Graph Neural Networks (SF-GNN), a lightweight and architecture-agnostic framework that mitigates structural bias at its source. SF-GNN identifies bias-prone edges by combining sensitive homophily with structural propagation amplifiers, including hub participation and triadic closure. It then incorporates stochastic edge filtering into each message-passing step to selectively downweight or remove these edges while preserving the remaining graph structure. Training further incorporates a statistical-parity regularizer with a warm-up schedule to stabilize optimization. Experiments on five benchmark datasets show that SF-GNN achieves consistent fairness improvements while maintaining competitive predictive performance, leading to a better fairness--accuracy trade-off than recent fairness-aware GNN baselines.

Comment
ICONIP 2026

Closest papers

Nearest neighbours by meaning across the whole index.

FairProp: Fair Node Representation Learning via Differentiable Propagation Layers

cs.LG cs.SI ·2026-10-05 ·Emmanouil Kariotakis, Aritra Konar
similarity 0.77
Abstract

Graph neural networks (GNNs) are the standard tool for node representation learning and are increasingly used in high-stakes settings. Their message-passing backbone, however, can amplify topological bias, raising fairness concerns. We study group fairness at the level of downstream predictions for node classification, link prediction, and node regression, and bound the demographic parity gap for an arbitrary number of sensitive groups. Our node classification bound is provably no looser than the closest prior result. For link prediction, ours is the first bound on the parity gap of the deployed sigmoid-activated prediction rather than a pre-activation proxy, and for node regression we provide the first such bound. Across all three tasks, the analysis identifies two distinct sources of bias: the separation between group means and the within-group covariance of the final representations. Building on this insight, we embed fairness into propagation itself by augmenting the convex smoothing problem underlying APPNP with a convex group-mean constraint and a within-group covariance regularizer. Unfolding projected gradient descent on this problem yields FairProp, whose layers pair a propagation step with a closed-form projection and which provably converges linearly to the unique fair optimum. Experiments on three tasks show that FairProp, even with exact group-mean equalization alone, provides a strong inductive bias that achieves excellent fairness-utility trade-offs against strong baselines.

0.06

Investigating the Effect of k-NN Preprocessing on Developing Graph Neural Networks: A Fairness-Based Perspective

cs.LG cs.AI ·2026-09-27 ·Nikolaos Zafeiropoulos, Emmanouil Mavrikos, George E. Tsekouras
published similarity 0.69
Abstract · Accepted for presentation at the 2025 16th International Conference on Information, Intelligence, Systems & Applications (IISA), IEEE. Proce…

In this paper, a methodology to design fair graph convolutional neural networks (GCNs) is developed and tested over several application data sets. The graphs that are used as inputs to the network are constructed by a k-nearest neighbor-based preprocessing procedure, while fairness issues are considered in terms of the equalized odds criterion. To effectively incorporate the above heterogenous information, the equalized odds criterion is directly embedded into the model's optimization objective through an additional fairness-driven loss functional term. The proposed methodology investigates how varying the neighborhood size in the k-NN algorithm during graph construction influences both the classification performance and the fairness of the resulting models. Extensive experimentation is conducted on three real-world tabular datasets with known biases, evaluating the interplay between graph structure and fairness enforcement. The results demonstrate that the choice of the value of the parameter k critically impacts the performance trends, either steadily improving or peaking at intermediate values depending on dataset characteristics, while the application of fairness constraints significantly mitigates disparities in false positive and false negative rates across groups defined by the protected variable at hand, without incurring major sacrifices in overall accuracy. This study highlights the importance of jointly optimizing the graph construction process and fairness objectives in GCN-based learning, providing a systematic approach toward building more equitable and effective graph-based models.

0.24

Individual Fairness via Local Predictive Consistency

cs.LG ·2026-10-23 ·Zhouting Zhao, Tin Lok James Ng
top venue similarity 0.69
Abstract

Individual fairness in machine learning requires that similar individuals receive similar predictions. Most existing definitions are pairwise in nature, imposing a Lipschitz constraint that must hold either globally across all pairs of data instances or locally within specified neighborhoods. In practice, however, such pairwise constraints may be overly restrictive and may not directly identify which individuals receive locally inconsistent predictions. We study local predictive consistency as a node-level relaxation of pairwise individual fairness, where each prediction is compared with a similarity-weighted average of predictions in its local neighborhood. This yields an interpretable node-level fairness score and a corresponding regularized learning approach based on local residuals. Since graph-based individual fairness depends critically on the underlying similarity structure, we make the construction of the neighborhood graph explicit and discuss threshold selection through graph-coverage diagnostics. Our approach applies to binary classification, regression, and time-to-event prediction. We further compare this formulation with pairwise constraint-based approaches and analyze the resulting fairness--performance trade-offs.

0.29

Fairness-Aware Network Embeddings: Methods, Applications, and Challenges

cs.SI cs.AI ·2026-08-19 ·Ella Has, Harshith Kumar Yadav, Gaurav Dixit, Mykola Pechenizkiy, Akrati Saxena
survey similarity 0.66
Abstract

Network embedding methods learn low-dimensional representations of graph-structured data to support downstream tasks such as node classification, link prediction, and influence maximization. However, real-world networks often reflect structural inequalities arising from demographic imbalances, homophily, and other societal biases, which fairness-agnostic embedding methods can encode and amplify. To address this issue, numerous fairness-aware network embedding methods have been proposed to mitigate bias while preserving embedding utility. This survey presents a comprehensive overview of fairness-aware network embeddings for complex networks. We propose a taxonomy that categorizes existing methods along three main complementary dimensions: underlying embedding approach (spectral, random walk, graph neural network, Bayesian, and method-agnostic), fairness intervention strategy (pre-processing, in-processing, and post-processing), and fairness objective criterion (embedding- or task-level). We further compare methods with respect to group versus individual fairness and assumptions regarding sensitive attributes. Finally, we discuss current limitations and highlight promising future research directions. This survey provides a unified perspective on fairness-aware network embedding and serves as a reference for developing fair and trustworthy network representation learning methods.

0.34

Toward Equitable Low-Carbon Mobility: Fairness-Aware Demand Prediction for Expanding Bike-Sharing Systems

cs.LG ·2026-08-26 ·Man Luo, Yixuan Zhao
similarity 0.62
Abstract

Bike-sharing systems are an important component of low-carbon urban mobility, but continued expansion creates challenges in both cold-start prediction and equitable resource allocation. Newly deployed stations lack historical ridership records, causing a mismatch between training and inference for graph-based models on evolving networks. Historical demand may also encode structural inequalities, as lower ridership in low-income neighborhoods can reflect limited infrastructure access rather than weak latent demand. Models trained directly on such data may therefore reinforce existing mobility disparities. We propose FairGIN, a fairness-aware graph neural network for demand prediction in expanding bike-sharing systems. FairGIN integrates three components. Expansion-Simulated Increment Training stochastically simulates network expansion during training to reduce the cold-start distribution gap. Attention-Based Knowledge Transfer combines station-adaptive temperature scaling with orthogonal embedding alignment to transfer representations from data-rich existing stations to data-sparse new stations. Fairness-Aware Optimization introduces income-stratified regularization and an equity-calibrated deployment score to support more inclusive station placement. Experiments on NYC and Seattle demonstrate that FairGIN achieves state-of-the-art predictive accuracy across diverse expansion scenarios while substantially reducing income-based disparities without compromising overall system efficiency.

0.13

Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks

cs.LG ·2026-09-25 ·Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous, Ryan A. Rossi, Baris Coskunuzer +5 more
code/data similarity 0.62
Abstract

Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers a natural way to reduce these costs, but removing edges indiscriminately can distort important communication structure and degrade predictive performance. We introduce Scaffold, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. Scaffold explicitly controls two complementary structural quantities: dilation, which measures the length of rerouting paths induced by removed edges, and congestion, which measures how strongly these rerouted paths concentrate on the retained support. By jointly controlling dilation and congestion, Scaffold preserves short communication paths while avoiding structural bottlenecks. To our knowledge, Scaffold is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion. Across 19 homophilic and heterophilic benchmarks spanning small to large graphs, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, Scaffold recovers or closely approaches full-graph GNN performance while using less than half the memory of full-graph training and reducing end-to-end training time, including sparsification overhead. We provide an open-source software package at https://github.com/siddhartha047/Scaffold.

0.25

FairPGT: Partitioned Graph Transformers for Dual-Level Fair Graph Clustering

cs.LG cs.AI ·2026-11-17 ·Siamak Ghodsi, Amjad Seyedi, Sahar Tahmasebi, Eirini Ntoutsi, Sören Auer
theorycode/data similarity 0.62
Abstract · Under review. 36 pages, 8 figures, 5 tables. Code: https://github.com/SiamakGhodsi/FairPGT

Clustering on attributed graphs can produce demographically biased clusters, particularly when communities align with protected groups. Graph transformers can amplify this bias through same-group attention, while global attention limits scalability. We propose FairPGT, a partitioned graph transformer for fair graph clustering. FairPGT restricts attention to METIS partitions and connects them through routing tokens, which divides the quadratic cost of attention by the number of partitions. A graph-aware self-training target guides clustering, with a provably bounded deviation from the standard DEC target. Fairness is imposed at two levels: a mutual-information term promotes demographic parity in cluster assignments, while a normalized cross-group attention ratio (nCGAR) guides attention toward group neutrality through self-distillation. We prove that the nCGAR correction moves attention toward neutrality and establish a condition preventing overshooting. Across seven benchmarks, FairPGT achieves the best clustering performance and statistical parity on the three largest graphs (Credit, Pokec-n, Pokec-z), with a statistical-parity gap approximately ten times lower than DMoN, and is Pareto-dominated on only one dataset. On controlled stochastic block models, FairPGT attains 97% of the derived upper bound on NMI for exactly fair clustering when communities and protected groups coincide. These graphs further show that, under strong alignment, assignment-level fairness alone makes the attention group-heterophilous, whereas attention-level fairness alone improves neutrality without ensuring fair clusters. Code for reproducibility is available at https://github.com/SiamakGhodsi/FairPGT.

0.42

Certifying Graph Neural Networks Against Label and Structure Poisoning

cs.LG ·2026-11-02 ·Lukas Gosch, Xichuan Chen, Yan Scholten, Stephan Günnemann
top venue similarity 0.61
Abstract · Published at the International Conference on Machine Learning (ICML) 2026

Robust machine learning for graph-structured data has made significant progress against test-time attacks, yet certified robustness to poisoning - where adversaries manipulate the training data - remains largely underexplored. For image data, state-of-the-art poisoning certificates rely on partitioning-and-aggregation schemes. However, we show that these methods fail when applied in the graph domain due to the inherent label and structure sparsity found in common graph datasets, making effective graph-partitioning difficult. To address this challenge, we propose a novel semi-supervised learning framework called deep Self-Training Graph Partition Aggregation (ST-GPA), which enriches each graph partition with informative pseudo-labels and synthetic edges, enabling effective certification against node-label and graph-structure poisoning under sparse conditions. Our method is architecture-agnostic, scales to large numbers of partitions, and consistently and significantly improves robustness guarantees against both label and structure poisoning across multiple benchmarks, while maintaining strong clean accuracy. Overall, our results establish a promising direction for certifiably robust learning on graph-structured data against poisoning under sparse conditions.

0.46