{"id":"35dc4eba-6ac5-4190-ac48-98ca9b2931f5","arxiv_id":"2504.15075","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"DegFairGT adds degree-weighted edges between similar non-adjacent nodes within communities and injects structural similarity into self-attention, improving degree fairness, classification, and clustering on six benchmarks.","lead":"This paper presents DegFairGT, a graph transformer that reduces degree bias by adding edges between low-degree nodes that are structurally similar and by injecting structural similarity into self-attention. It is relevant to anyone building graph neural networks for social, recommendation, or citation systems, where low-degree nodes are often underrepresented.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reported gains may be inflated by hyperparameter selection on test metrics; validation-based tuning is not described.","rationale":"The reader's weakest assumption was that D_ij = 1/sqrt(d_i d_j) is an unvalidated heuristic. That is a real concern about the mechanism, but it is not the most load-bearing issue for the central claim. Even if D_ij is a crude proxy, adding edges between low-degree nodes in the same community could still improve fairness for reasons unrelated to structural similarity, so the empirical claim could survive. The more serious threat is that the reported hyperparameters appear to be chosen by looking at test-set metrics. Table 9 and Figure 7 report test performance for every grid point and then select the best; Section 4.1.4 does not state that a validation set was used for model selection. If the test set informed hyperparameter choice, the reported improvements over baselines are optimistic, and the comparison may not be fair because baseline tuning is not described. This attacks the reliability of all headline numbers, not just the interpretation of D_ij. A validation-based re-selection experiment would settle it: if gains persist under nested validation, the claim is credible despite the heuristic; if they shrink, the central claim is overstated. The paper does provide a code repository and multiple sensitivity analyses, which is positive, but it also lacks formal verification and the 'learnable' augmentation is not actually parameterized. Overall, the reader's CONDITIONAL verdict is appropriate; our concern reinforces it rather than changing it.","tokens_in":26457,"tokens_out":9007,"duration_ms":84848,"concrete_test":"Re-run the six benchmarks with hyperparameters selected on the validation split only: for each dataset, perform grid search over xi in {0.2,0.4,0.6,0.8}, zeta in {0.2,0.4,0.6,0.8}, alpha in {0.01,0.1,0.5,1,10}, M in {3,5,7,9}, and p in {2,...,8} using validation accuracy and validation Delta-SP/Delta-EO, then evaluate the selected model on the held-out test set once. Compare to Tables 3, 6, and 7. If DegFairGT's advantage over the strongest baseline drops by more than 20% relative in Delta-SP/Delta-EO or 1 percentage point in accuracy, the reported gains are not robust.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim depends on DegFairGT outperforming baselines in Tables 3-7. Section 4.4.2 selects xi=0.8, zeta=0.2, M=5, alpha=1.0, and beta1/beta2 by grid search using test accuracy, Delta-SP, and Delta-EO (Table 9, Figures 7a-7c). Section 4.1.4 says hyperparameters are determined with a grid search but does not state that selection used the validation split. If the test set was used to choose hyperparameters, the reported numbers are optimistically biased and the comparison to baselines, whose tuning procedure is not described, is unfair. Additionally, Eq. (1)-(4) contain no learnable parameters in the augmentation: D_ij is a fixed degree-weighting, and the Bernoulli sampling via Gumbel-Softmax has no learned weights, so 'learnable structural augmentation' is a mischaracterization. The load-bearing issue is not the heuristic D_ij per se, but that the empirical wins may not survive proper validation-based hyperparameter selection.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DegFairGT, a graph transformer framework that aims to mitigate degree bias in graph representation learning. The method constructs an augmented graph by combining the original adjacency matrix with a degree-weighted structural similarity matrix D_ij = 1/sqrt(d_i d_j), restricted to node pairs in the same k-means community within k-hop reachability, and then samples edges via Bernoulli draws relaxed with Gumbel-Softmax. The transformer encoder uses a structural self-attention that injects high-order proximity and the degree-weighted score into attention computation. A self-supervised loss reconstructs the p-step transition probability matrix and the input features, together with a BCE loss that regularizes the augmentation, and the model is pre-trained without labels before downstream evaluation. Experiments on six datasets report degree-fairness metrics (Delta-SP, Delta-EO), node classification accuracy, and clustering conductance/modularity compared with twelve baselines, including graph transformers and augmentation-based methods.","tokens_in":26705,"tokens_out":4785,"duration_ms":40918,"significance":"If the reported results hold under a proper validation protocol, the paper would make a useful empirical contribution to degree-fair graph representation learning: it combines degree-weighted edge augmentation with structure-aware self-attention, evaluates on six benchmarks with ten random splits, and reports improvements across fairness, accuracy, and clustering. The availability of source code is a positive reproducibility feature, and the ablation and sensitivity analyses (Tables 8-10, Figure 7) provide useful information about the contribution of the augmentation and attention modules. However, the central claim of a 'learnable' augmentation is not reflected in the equations, and the hyperparameter selection protocol, as described, risks optimistic bias in the headline comparisons. These issues are load-bearing for the novelty and reliability of the reported gains, so they must be addressed before the contribution can be fully assessed.","major_comments":[{"comment":"The 'learnable structural augmentation' contains no learnable parameters. In Eq. (4), A'ij is sampled from a Bernoulli distribution with fixed probability A~ij = xi*Aij + zeta*Dij, where xi and zeta are hyperparameters; the Gumbel-Softmax relaxation merely makes the discrete sampling differentiable and does not introduce any learned transformation. Consequently, statements in Section 3.1 that the augmentation is 'end-to-end trainable through edge perturbation, making itself learn structural similarity between node pairs' and in Section 3.3 that 'the augmentation module could learn to produce a fully connected graph or remove too many edges' are not supported by the described architecture. Because 'learnable structural augmentation' is a stated contribution that differentiates the method from heuristic augmentation baselines, this mischaracterization needs to be corrected, or the method must be extended with genuinely learnable parameters that shape the sampling probabilities.","section":"Section 3.1, Eqs. (1)-(4)"},{"comment":"The hyperparameter selection appears to use test-set metrics. The text states that xi and zeta are 'determined with a grid search' and that the chosen values 'have a better performance (higher accuracy and lower Delta-SP and Delta-EO)', and Table 9 reports exactly these test metrics for all combinations. Similarly, Figure 7 selects the number of clusters M, the p-step range, and alpha based on plots that show test accuracy, Delta-SP, and Delta-EO. Section 4.1.4 does not state that any of these selections were made on a validation split. If the test set was used to choose hyperparameters, the results in Tables 3-7 are optimistically biased, and the comparison with baselines, whose tuning procedure is not described, is not a controlled fair comparison. The authors should either clarify that all hyperparameters were selected using validation data, or re-run the experiments with a strictly validation-based selection protocol for both DegFairGT and the baselines.","section":"Section 4.4.2, Table 9 and Figure 7"},{"comment":"The degree-weighted score D_ij = 1/sqrt(d_i d_j) is the only structural-similarity signal in the augmentation, yet it is introduced without derivation, formal justification, or comparison against alternative structural similarity measures (e.g., Jaccard similarity of neighborhoods, Adamic-Adar, or role-similarity). The paper argues intuitively that low-degree pairs should be favored, but it does not validate that this particular inverse-degree product is the right way to capture structural similarity for informative message-passing edges. Since the claimed fairness gains rest on this choice, the authors should provide a principled motivation or an ablation that compares alternative scores to show that the specific form of D matters.","section":"Section 3.1.2, Eq. (3)"}],"minor_comments":[{"comment":"The sentence ending with 'over time, presenting challenges in capturing temporal dependencies and structural changes' is a fragment and appears to be an incomplete leftover from a different discussion; it should be revised or removed.","section":"Section 2"},{"comment":"In the Graphormer row under Computers, the value '10.76±173' appears to be a typo; likely '10.76±1.73'.","section":"Table 4"},{"comment":"The text says 'The hyperparameters alpha2, beta1, and beta2 are determined with a grid search', but the loss in Eq. (16) uses alpha, not alpha2; please make the notation consistent.","section":"Section 4.1.4"},{"comment":"The matrix A^(k) = sum_{l=1}^k A^l is a reachability indicator matrix, not a transition probability matrix; calling it 'the transition matrix of G at k-step' is misleading and should be reworded (e.g., 'reachability matrix').","section":"Section 3.1.1, Eq. (2)"},{"comment":"In the UGT row, the Photo and WikiCS columns report identical values (9.41 +/- 0.25 and 14.31 +/- 0.39 for Delta-SP and Delta-EO, respectively); please check if one pair was accidentally copied from the other.","section":"Table 3"},{"comment":"The subplots do not distinguish which line corresponds to Delta-SP, Delta-EO, and accuracy; adding a legend or direct labels would greatly improve readability.","section":"Figure 7"},{"comment":"The sentence 'if zeta = 0.2 is large' is likely a typo; it should probably read 'if zeta is large' or 'if zeta = 0.8 is large'.","section":"Section 4.4.2"}],"recommendation":"major_revision","confidential_remarks":"The paper's core empirical protocol is solid in terms of repetitions and coverage, but the two load-bearing issues--the absence of learnable parameters in the augmentation and the apparent test-set hyperparameter selection--need direct fixes. I would also encourage the authors to temper the 'first graph transformer model addressing degree biases' novelty claim, since UGT already uses structural-similarity-based edge generation and transition-matrix reconstruction; the differentiation should be made crisper in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: DegFairGT is a plausible recipe for improving degree fairness in node classification and clustering, and the paper reports consistent gains on six datasets. It deserves a serious referee, but the empirical claims are weakened by a tuning protocol that appears to select hyperparameters on the test set, and one of its two headline components is not actually learnable.\n\nWhat is new: the specific combination—community-restricted, k-hop-bounded edge augmentation weighted by inverse square-root degree, a structural self-attention that injects the same degree score and a shared-neighbor proximity vector, and a p-step transition reconstruction loss with a BCE regularizer on the augmented adjacency—does not appear in earlier work. The experiments are reasonably thorough: three benchmarks, ten runs, mean/std, and ablations showing both modules help. The paper honestly lists its own limitations (quadratic attention, degree/community-only structural similarity) and ships code.\n\nSoft spots. First, 'learnable structural augmentation' overstates what Eq. (1)-(4) do. D_ij is a fixed heuristic, ξ and ζ are hyperparameters, and the Bernoulli sampling is made differentiable with Gumbel-Softmax but contains no learned weights. The learning happens downstream in the transformer and losses. That is a naming and framing problem, not a fatal one, but it matters because the text claims the augmentation can adapt to graph structures.\n\nSecond, and more consequential, the hyperparameter selection is not described as using a validation split. Sections 4.1.4 and 4.4.2 grid-search α, β1, β2, ξ, ζ and report the chosen values' accuracy and fairness metrics—the same test metrics used in the main tables. If the test set influenced the selection, the gains over baselines are optimistically biased. The paper needs to state the split explicitly or redo selection on validation. The D_ij heuristic itself is ad hoc but not damning; it is a reasonable prior and the ablation supports it.\n\nVerdict: This is a solid applied-GNN paper whose central claim is plausible but not fully nailed down. A careful referee should ask for validation-based hyperparameter selection and a correction to the 'learnable' terminology. I would bring it to a reading group and cite it in related work, but I would hold off on building on the exact numbers until the tuning issue is resolved.","headline":"A plausible, well-engineered recipe for degree fairness that overstates itself slightly by calling a fixed heuristic 'learnable' and by selecting hyperparameters on test metrics.","tokens_in":27176,"tokens_out":3279,"would_cite":true,"duration_ms":29546,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph transformer that adds edges between similarly low-degree nodes in the same community can cut degree bias in node classification while improving accuracy on standard benchmarks.","keywords":["degree bias","graph representation learning","learnable graph augmentation","graph transformer","structural self-attention","fairness","node classification","graph clustering"],"falsifier":"Run DegFairGT against a variant in which $D_{ij}$ is replaced by a constant for all context pairs, so edges are sampled uniformly within the same community and $k$-hop range; if $\\Delta SP$ and $\\Delta EO$ stay unchanged, the degree-weighted score is not the cause of the fairness gains, while degradation would confirm the structural ranking is load-bearing. The same experiment can be repeated on a star-like graph where low-degree nodes share few features, testing whether the k-means community restriction removes informative low-degree pairs.","tokens_in":26267,"feed_emoji":"⚖️","tokens_out":8930,"duration_ms":74173,"temperature":0.7,"pith_summary":"Graph neural networks update node representations by passing messages along edges, so nodes with few connections receive few messages and tend to be misclassified—a degree bias that grows on graphs with long-tailed degree distributions. This paper claims that the bias can be mitigated by adding edges between non-adjacent nodes that share a community and have similarly low degree, and by making the transformer's attention explicitly aware of that structural role similarity. The proposed model, DegFairGT, is reported to lower two degree-fairness metrics ($\\Delta SP$ and $\\Delta EO$), raise node classification accuracy, and improve clustering quality on six benchmark networks compared with existing GNNs, augmentation methods, and graph transformers. The method is fully unsupervised with respect to labels, using a self-supervised loss that preserves the graph's $p$-step transition probabilities and regularizes the edge augmentation. If the claim holds, degree bias is not an unavoidable property of graph structure but a problem of which non-adjacent nodes are chosen to exchange messages.","feed_headline":"Graph transformer counters degree bias with low-degree links","feed_subtitle":"Adding edges between similarly low-degree nodes in the same community shifts the fairness-accuracy trade-off.","key_machinery":"The load-bearing object is the degree-weighted structural-similarity score $D_{ij} = 1/\\sqrt{d_i d_j}$, which ranks candidate context nodes by the product of their degrees and is used both to sample new edges and to bias attention. Context candidates are first restricted to non-adjacent pairs inside the same k-means feature cluster that are reachable within $k$ hops; the score is then blended with the original adjacency matrix as $\\tilde A = \\xi A + \\zeta D$, and edges are sampled from a Bernoulli distribution relaxed with Gumbel-Softmax so the whole augmentation is differentiable. The same structural information reaches the transformer through a high-order proximity vector $s_{ij}$, computed from shared $k$-hop neighborhoods, and through a linearly transformed $D_{ij}$ added to each attention logit. A self-supervised reconstruction of the log-scaled $p$-step transition matrix, combined with a binary cross-entropy loss between the original and augmented adjacency matrices, prevents the augmentation from collapsing into a fully connected or barren graph. These three pieces—degree-weighted edge sampling, structural attention bias, and structure-preserving regularization—jointly carry the argument.","core_discovery":"The central claim is that a graph transformer can overcome degree bias by learning to add intra-community edges between non-adjacent nodes with similar low degree and by injecting the same structural-role information into self-attention. The paper argues that random or heuristic edge perturbations either add noisy long-range messages or destroy original topology, whereas edges sampled with probability proportional to the degree-balanced score $D_{ij} = 1/\\sqrt{d_i d_j}$—restricted to nodes in the same k-means cluster within $k$ hops—provide informative messages to under-represented nodes while preserving homophily within the community. On six citation, co-purchase, and reference networks, the resulting embeddings are reported to give the best or near-best degree fairness (lower $\\Delta SP$, $\\Delta EO$), the highest node classification accuracy on five of six datasets, and the lowest conductance or highest modularity on clustering in most cases. The paper also presents an ablation showing that each module contributes, and a Pareto-style analysis indicating that DegFairGT shifts the fairness-accuracy trade-off compared with degree-modulated and graph-transformer baselines.","pith_inferences":["A testable extension is to replace the degree product $1/\\sqrt{d_i d_j}$ with other structural-role scores (shared-neighborhood Jaccard, graphlet counts, or role embeddings) inside the same augmentation pipeline; if fairness improves further, the inverse-degree proxy is not the limiting factor.","The method's reliance on k-means clusters of node features implies a hidden homophily assumption; on heterophilic graphs, the same pipeline might filter out informative low-degree nodes, so a degree-biased augmentation may need a community definition based on structure rather than features.","The paper's Pareto analysis suggests that fairness methods should be compared by how far they move the fairness-accuracy frontier, not by a single fairness metric; this is an implicit methodological shift for the field.","Because the transformer's quadratic attention limits scale, swapping the self-attention encoder for a linear transformer while keeping the degree-weighted augmentation would reveal whether the augmentation alone, rather than the attention, drives the fairness gains."],"forward_implications":["If the central claim is correct, adding intra-community edges between similarly low-degree nodes should shrink the prediction gap between low- and high-degree groups without the accuracy penalty that usually accompanies fairness constraints.","Graph transformers that sample context nodes without degree-role similarity should show higher degree bias on sparse networks, as the paper reports for Cora and Citeseer.","The fairness gains should transfer to other transductive node-classification benchmarks with long-tailed degree distributions and recoverable community structure, since only hyper-parameters change between datasets.","Preserving the $p$-step transition matrix of the original graph is the mechanism presented for keeping clustering quality while modifying the adjacency matrix."],"supporting_citations":[{"why":"Defines the graph transformer architecture used as the primary baseline, the model shown to exhibit degree bias in the paper's motivating figure.","marker":"[4]"},{"why":"Provides GRADE, a structural-fairness augmentation baseline that samples edges from k-subgraphs; the paper's sampling scheme is positioned against it.","marker":"[7]"},{"why":"Supplies the spatial-encoding idea (shortest-path distances) in Graphormer that the structural self-attention extends to a high-order proximity vector.","marker":"[12]"},{"why":"Introduces the generalized-degree fairness metrics $\\Delta SP$ and $\\Delta EO$ and the DegFairGNN baseline that modulates message passing by node degree.","marker":"[14]"},{"why":"GCA, the centrality-based adaptive augmentation baseline, whose node-centrality bias is compared with the degree-weighted structural bias.","marker":"[15]"},{"why":"Provides the p-step transition matrix preservation objective and structural-identity edge generation that inspire the self-supervised reconstruction loss.","marker":"[32]"},{"why":"Gumbel-Softmax reparameterization used to make the Bernoulli edge sampling differentiable in the augmentation module.","marker":"[43]"},{"why":"Noise-contrastive estimation used to pre-compute the log-scaled p-step transition matrix in the structure-preservation loss.","marker":"[45]"}],"fun_headline_variants":["Graph transformer learns fair links for low-degree nodes","Augmenting graphs with fair edges reduces degree bias","Add intra-community edges to balance degree bias","Fair graph transformer adds edges within communities"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that two non-adjacent nodes in the same feature cluster within $k$ hops are informative message partners when they both have low degree, as quantified by the inverse square root of the product of their degrees.","fun_headline_variants_meta":{"raw":{"variants":["Graph transformer learns fair links for low-degree nodes","Augmenting graphs with fair edges reduces degree bias","Add intra-community edges to balance degree bias","Fair graph transformer adds edges within communities"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001163,"raw_usage":{"total_tokens":4873,"prompt_tokens":1059,"completion_tokens":3814,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":675,"completion_tokens_details":{"reasoning_tokens":3756}},"tokens_in":675,"tokens_out":3814,"duration_ms":22973,"temperature":1.0,"reasoning_tokens":3756,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:33:40.991015+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DegFairGT against a variant in which $D_{ij}$ is replaced by a constant for all context pairs, so edges are sampled uniformly within the same community and $k$-hop range; if $\\Delta SP$ and $\\Delta EO$ stay unchanged, the degree-weighted score is not the cause of the fairness gains, while degradation would confirm the structural ranking is load-bearing. The same experiment can be repeated on a star-like graph where low-degree nodes share few features, testing whether the k-means community restriction removes informative low-degree pairs.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides GRADE, a structural-fairness augmentation baseline that samples edges from k-subgraphs; the paper's sampling scheme is positioned against it."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the spatial-encoding idea (shortest-path distances) in Graphormer that the structural self-attention extends to a high-order proximity vector."},{"cited_title":"AAAI Conf","cited_arxiv_id":null,"evidence_quote":"Introduces the generalized-degree fairness metrics $\\Delta SP$ and $\\Delta EO$ and the DegFairGNN baseline that modulates message passing by node degree."},{"cited_title":"Web Conf., 2021, pp","cited_arxiv_id":null,"evidence_quote":"GCA, the centrality-based adaptive augmentation baseline, whose node-centrality bias is compared with the degree-weighted structural bias."},{"cited_title":"AAAI Conf","cited_arxiv_id":null,"evidence_quote":"Provides the p-step transition matrix preservation objective and structural-identity edge generation that inspire the self-supervised reconstruction loss."},{"cited_title":"”Categorical reparam- eterization with gumbel-softmax,” in Proc","cited_arxiv_id":null,"evidence_quote":"Gumbel-Softmax reparameterization used to make the Bernoulli edge sampling differentiable in the augmentation module."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Noise-contrastive estimation used to pre-compute the log-scaled p-step transition matrix in the structure-preservation loss."}],"review_version":1}