Mitigating Degree Bias in Graph Representation Learning with Learnable Structural Augmentation and Structural Self-Attention
Van Thuy Hoang, Hyeon-Ju Jeon, and O-Joun Lee · 2025
Read Mitigating Degree Bias in Graph Representation Learning with Learnable Structural Augmentation and Structural Self-Attention by Van Thuy Hoang, Hyeon-Ju Jeon, and O-Joun Lee (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15075.txt.
Introduction
Van Thuy Hoang, Hyeon-Ju Jeon, and O-Joun Lee fix a fairness flaw inside graph neural networks. Their 2025 paper names the flaw degree bias: hub nodes with many links dominate the message passing these networks learn from, while low-degree nodes get too few messages and stay poorly represented. Patching it is delicate, since borrowing messages from faraway nodes can inject noise and warp the graph.
Their model, DegFairGT, learns which non-adjacent nodes play similar roles in the same community, then builds informative edges between them under a homophily guard. A structural self-attention step scores those similarities, and a self-supervised task keeps the altered graph faithful to the original's reachability patterns. Across six data sets the model beat strong baselines on fairness measures, node classification, and clustering alike.
Catalog record
| CREATOR | Van Thuy Hoang, Hyeon-Ju Jeon, and O-Joun Lee |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-15075
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Mitigating Degree Bias in Graph Representation Learning with Learnable Structural Augmentation and Structural Self-Attention Van Thuy Hoang, Hyeon-Ju Jeon, and O-Joun Lee Abstract Graph Neural Networks (GNNs) update node representations through message passing, which is primarily based on the homophily principle, assuming that adjacent nodes share similar features. However, in real-world graphs with long-tailed degree distributions, high-degree nodes dominate message passing, causing a degree bias where low-degree nodes remain under-represented due to inadequate messages. The main challenge in addressing degree bias is how to discover non-adjacent nodes to provide additional messages to low-degree nodes while reducing excessive messages for high-degree nodes. Nevertheless, exploiting non-adjacent nodes to provide valuable messages is challenging, as it could generate noisy information and disrupt the original graph structures. To solve it, we propose a novel Degree Fairness Graph Transformer, named DegFairGT, to mitigate degree bias by discovering structural similarities between non-adjacent nodes through learnable structural augmentation and structural self-attention. Our key idea is to exploit non-adjacent nodes with similar roles in the same community to generate informative edges under our augmentation, which could provide informative messages between nodes with similar roles while ensuring that the homophily principle is maintained within the community. By considering the structural similarities among non-adjacent nodes to generate informative edges, DegFairGT can overcome the imbalanced messages while still preserving the graph structures. To enable DegFairGT to learn such structural similarities, we then propose a structural self-attention to capture the similarities between node pairs. To preserve global graph structures and prevent graph augmentation from hindering graph structure, we propose a Self-Supervised Learning task to preserve p-step transition probability and regularize graph augmentation. Extensive experiments on six datasets showed that DegFairGT outperformed state-of-the-art baselines in degree fairness analysis, node classification, and node clustering tasks. I Introduction Graphs provide a robust framework for capturing complex data by representing the relationships among entities in a wide range of domains, such as molecular structures and social networks [ 1 ] . However, real-world graphs often have long-tailed degree distributions, which could negatively affect GNNs’ ability to learn low and high-degree nodes [ 2 ] . That is, GNNs update node representations by aggregating information from neighboring nodes through message passing, following the homophily principle, which assumes that connected nodes tend to have similar features. As a result, low-degree nodes receive a few messages from neighborhoods, which can cause bias or under-representation. Meanwhile, high-degree nodes receive overabundant messages, leading to inherent limitations of message passing, e.g., over-smoothing problems [ 3 ] . To illustrate this problem, Figure 1 shows that GT [ 4 ] , one of the recent graph transformer models, exhibits degree bias on Photo and Computers datasets [ 5 ] . We can intuitively infer that the degree bias problem arises from insufficient messages from correlated nodes, not merely from the number of neighbors. This indicates that the graph topology could significantly influence the balance of messages under the message propagation in GNNs [ 6 ] . Figure 1 : Low-degree nodes are more misclassified than other nodes in the GT model [ 4 ] on Photo and Computers datasets. The miss-classification rate is higher for low-degree nodes compared to high-degree nodes. To address this problem, most recent studies aim to deliver additional messages to low-degree nodes or remove redundant messages from high-degree nodes, mainly classified into three main groups: graph augmentation, observation range expansion, and neighborhood aggregation modulation. The graph augmentation-based methods generate or remove edges randomly or heuristically to observe graphs with different views [ 7 , 8 ] . The main idea is that augmentation schemes, e.g., edge perturbation, will continuously change the set of neighbors of each node and could help GNNs aggregate more messages to update node representations. The graph augmentations involve modifying graph structures, e.g., adding or removing edges, to enhance model performance and address the degree bias problem. However, in real-world graphs, graph structures often remain stable, reflecting intrinsic relationships and dependencies among nodes [ 9 , 10 ] . Some observation range expansion methods aim to expand the range of neighborhoods surrounding target nodes to capture high-order relationships and more information at each node representation update [ 11 , 12 , 13 ] . Several studies aim to adjust the model weights to distill sufficient messages during the message-passing aggregation [ 14 ] . Nevertheless, as the degree bias originates from graph structure imbalance, aggregation modulation can not adapt properly to the varying size and structure graphs. Although graph neural network strategies have shown effectiveness in mitigating degree bias, there are two limitations in existing studies that still limit their ability. First, it is challenging to discover correlated nodes with high structural similarity to provide informative messages for each target node. Most graph augmentation-based methods ignore the structural similarity between node pairs when forming edges, forcing GNNs to learn noisy and redundant messages. The augmentation methods randomly add or drop edges to generate multiple graph views, which could mainly benefit low-degree nodes to obtain more messages from distant nodes [ 8 , 15 , 16 ] . While randomly adding edges can bring more messages from non-adjacent nodes, the nodes could contain noisy and irrelevant information, which could force GNNs to aggregate redundant messages, resulting in suboptimal performance. That is, pairs of nodes formed into edges should be strongly correlated to their structural similarity, which then could naturally enable GNNs to learn their representations and map them closely in the latent space. Moreover, randomly dropping edges could severely degrade the low-degree node representations as they can be more under-represented due to the lack of messages. Second , it is challenging to achieve both degree fairness and graph structure preservation simultaneously. For augmentation-based methods, randomly adding edges can hinder preserving the original graph structures since any edge connecting two non-adjacent nodes forces GNNs to map node representations close significantly. Besides, although several methods consider structural features [ 15 ] , their indistinction between generated and original edges causes loss of local connectivity and high-order proximity [ 15 , 7 , 8 ] . Similarly, some observation range expansion methods ignore the distinctive messages between k -hop distances rooted at each node to its neighbors and even treat k -subgraph neighborhoods as complete graphs [ 17 , 11 ] . The loss of learning structural distance information and proximity between non-adjacent nodes hinders GNNs from preserving global graph structures. In this study, we propose a novel framework, DegFairGT, to mitigate degree biases via structural graph augmentations and graph transformers. The main idea is to exploit non-adjacent nodes with high structural similarity to form informative edges rather than random edge perturbation through graph augmentation, which could generate arbitrary edges and provide noisy information as well as disrupt the original graph structure. More precisely, we first compute a structural similarity score for each node pair, which reflects how similar the two nodes are in terms of their graph structure. The structural similarities are then used as a probability weight for sampling new edges under our augmentation. By doing so, our augmentation can connect correlated non-adjacent nodes with high similarity, enabling more balanced messages and enabling the model to maintain the homophily principle. To enable DegFairGT to learn such structural similarities,