Papers › Mitigating Degree Biases in Message Passing Mechanism by Utilizing Community Structures

Mitigating Degree Biases in Message Passing Mechanism by Utilizing Community Structures

28 Dec 2023arXiv:2312.16788archive 2025-07-28

Van Thuy Hoang, O-Joun Lee

This study utilizes community structures to address node degree biases in message-passing (MP) via learnable graph augmentations and novel graph transformers. Recent augmentation-based methods showed that MP neural networks often perform poorly on low-degree nodes, leading to degree biases due to a lack of messages reaching low-degree nodes. Despite their success, most methods use heuristic or uniform random augmentations, which are non-differentiable and may not always generate valuable edges for learning representations. In this paper, we propose Community-aware Graph Transformers, namely CGT, to learn degree-unbiased representations based on learnable augmentations and graph transformers by extracting within community structures. We first design a learnable graph augmentation to generate more within-community edges connecting low-degree nodes through edge perturbation. Second, we propose an improved self-attention to learn underlying proximity and the roles of nodes within the community. Third, we propose a self-supervised learning task that could learn the representations to preserve the global graph structure and regularize the graph augmentations. Extensive experiments on various benchmark datasets showed CGT outperforms state-of-the-art baselines and significantly improves the node degree biases. The source code is available at https://github.com/NSLab-CUK/Community-aware-Graph-Transformer.

PaperPDFCode

Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.

Code

nslab-cuk/community-aware-graph-transformer officialmentioned in papermentioned on GitHubpytorchMITSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity... (arXiv:2308.09517; that paper's own run record: 19 ran (of which 0 constructed an object rather than computing a result; 13 with no instrument failure: 0 honoured, 0 violated, 13 with no contract checked; 6 where Syntology's instrument failed) · 7 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Node ClassificationNode ClusteringSelf-Supervised Learning

Results from the paper archive 2025-07-28

TaskDatasetModelMetricValueRank at snapshotLeaderboardReport
Node Classification AMZ Photo CGT Accuracy 95.73±0.84 #2 of 14 Archive leaderboard report
Node Classification Amazon Computers CGT Accuracy 91.45±0.58 #7 of 12 Archive leaderboard report
Node Classification Citeseer CGT Accuracy 76.59±0.98 #11 of 71 Archive leaderboard report
Node Classification Cora CGT Accuracy 87.10±1.53 #17 of 73 Archive leaderboard report
Node Classification Pubmed CGT Accuracy 86.86±0.12 #18 of 70 Archive leaderboard report
Node Classification Wiki-CS CGT Accuracy 84.61±0.53 #1 of 6 Archive leaderboard report

Ranks are positions in the archive's leaderboards as they stood at the 2025-07-28 snapshot. Results published since then are not among these rows, so a rank here is not a current standing.

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections