AdNGCL: Adaptive Negative Scheduling for Graph Contrastive Learning

arXiv:2605.03076 · cs.LG · Submitted 2026-05-04 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "AdNGCL: Adaptive Negative Scheduling for Graph Contrastive Learning".

Tom: The gist The proposed framework, AdNGCL, introduces an adaptive negative scheduling mechanism to Graph Contrastive Learning that formulates negative selection as a loss-gated, budget-constrained process across hard, intermediate,

Jane: First, who's behind it and why it matters.

Title and authors: Tom: We started by looking at the title and the authors of this paper, "AdNGCL: Adaptive Negative Scheduling for Graph Contrastive Learning." It immediately tells us they are focused on making negative selection dynamic rather than static.

Jane: The authors are Adnan Ali, Jinlong Li, Syed Muhammad Israr, and Ali Kasif Bashir. They’re clearly people deeply involved in graph contrastive learning research.

Lu: They’ve been working in areas spanning recommendation systems and anomaly detection on attributed networks for consumer electronics security.

Meng: That sounds like they are tackling real-world problems where accurate representation matters, like identifying issues in IoT networks or suggesting personalized content.

Tom: So the core idea is that static negative sampling fails because it doesn't account for how important those negatives are dynamically during training and the cost involved.

Jane: They propose AdNGCL to solve this by formulating negative selection as a loss-gated, budget-constrained process across hard, intermediate and easy strata.

Lu: This means they’re not just sampling blindly; they're making decisions about negatives based on where the samples fall in terms of their hardness.

Meng: So it’s an intelligent way to manage the supervision we feed into the model while keeping a close eye on computational resources.

Tom: Exactly. It moves us from uniform rules to something that adapts its strategy based on what the model is learning at any given moment.

Jane: And they specifically mention that this dynamic adjustment helps prevent issues like representation collapse where all embeddings converge to similar points without meaningful separation twenty-two, twenty-three <ref:2605.03076#pg2,representation collapse where all embeddings converge to similar points without meaningful separation>.

Lu: They also note that without effective negatives, models trained only on positive pairs often overfit to training data twenty-four, leading to poor generalization in downstream tasks twenty-five <ref:2605.03076#pg2,on positive pairs often overfit to training data 24 , leading to poor>.

Meng: So the goal is twofold: get better separation between entities and ensure the model generalizes well beyond what it saw during training.

Tom: And they argue that high-quality negatives promote robustness to noise and perturbations in graph structures, which is important for consumer electronics applications such as recommender systems where accurate discrimination improves personalized content delivery, or IoT networks where it aids in anomaly detection amid complex device interactions two <ref:2605.03076#pg2,for consumer electronics applications such as recommender systems where accurate discrimination improves>.

Jane: That’s a direct link between having good negatives and the real-world performance we expect from these models.

Lu: However, they point out that most methods construct negatives via fixed, uniform rules that ignore semantic proximity, hardness, and training dynamics fourteen, which weakens the contrastive signal and slows convergence <ref:2605.03076#pg2,semantic proximity, hardness, and training dynamics 14 , which weakens the contrastive signal>.

Meng: So the lack of attention to those three factors—proximity, hardness, and training dynamics—is what makes static methods fall short here.

Tom: Which is why AdNGCL is trying to incorporate that sample hardness and dynamic scheduling into a principled framework twenty-six, twenty-seven <ref:2605.03076#pg2>.

The paper's summary: Tom: So what’s the actual summary of this paper? They are taking the core GCL idea and adding this adaptive negative scheduling mechanism called HANS.

Jane: They summarize it as a framework with five core modules: Graph Data Augmentation, Learning, Contrastive Samples and Loss, Hardness-Aware Negative Scheduling HANS, and finally Embedding Extraction and Downstream Evaluation.

Lu: The augmentation module modifies the input graph’s structure to create multiple augmented views using techniques like Edge Removal or Feature Masking.

Meng: So they are trying to generate richer data from the original graph before even starting the learning process.

Tom: Then in the learning module, a two-layer Graph Convolutional Network encoder maps these augmented views into a latent space for comparison.

Jane: The positive sample pair is formed by node embeddings h one i and h two i derived from those two augmented views, representing the same semantic entity in different views.

Lu: The negative sample set Ni is constructed by pairing an anchor embedding h one i with embeddings of other nodes from both views, i <ref:2605.03076#pg1>.e., (h one i, h two j) where j is not equal to i and vj is any node in the graph V.

Tom: The contrastive loss L maximizes agreement between positive pairs and minimizes agreement with negative pairs.

Jane: And this whole setup is governed by the HANS mechanism which we just talked about, which manages the negative selection process adaptively.

Lu: So HANS treats it as a budgeted scheduling problem involving stratification into hard, intermediate and easy sets based on similarity s(·, ·).

Meng: The budgeting involves capping total negatives per anchor by a global budget theta max in the range of zero to one, and per-category caps theta cat max.

Tom: And then they have the bootstrap scheduling where each category is gradually activated using a warm-up phase, where eta cat t is the fraction of the fixed category budget used.

Jane: This whole process ensures that increments are applied only when performance plateaus because of a loss gate check.

Lu: They also introduce Loss-Aware Step Size to modulate update magnitudes based on category loss shares and training saturation.

Meng: That sounds like they’re using the loss dynamics to decide how aggressively we should adjust our negative sample inclusion, which is really smart engineering.

Tom: And finally, once the global budget is saturated, they introduce a swapping phase where negatives are periodically re-sampled from their hardness pools to increase variety and prevent contrastive saturation.

Jane: It’s a lot of moving parts designed to ensure we maximize contrastive signal per unit compute while controlling those false-negative exposures.

Lu: The overall goal is to have compact, discriminative, and generalizable embeddings by prioritizing informative hard negatives when they remain discriminative and using stochastic swapping to prevent saturation.

The paper's improvements: Tom: So the paper really highlights some specific improvements they suggest over previous work. They show that increasing the hard negative proportion from ten percent to forty percent yields systematic gains across datasets, which shows how important informative negative pressure is <ref:2605.03076#pg3>.

Jane: That’s a strong finding because it shows that we should be actively seeking out those harder negatives instead of just accepting whatever comes with the training process.

Lu: They also show that the optimal maximum negative budget theta max is dataset dependent; sparse and low-homophily graphs benefit from higher budgets, around seventy to one hundred percent, versus dense graphs saturating near forty to sixty percent.

Meng: That’s a practical piece of information because it lets us tailor our strategy based on whether we are working with a sparse or dense graph.

Tom: And they reveal that efficiency analyses show diminishing returns beyond those plateaus, which really underscores HANS’s role in balancing accuracy and compute for deployment.

Jane: They also found that their mechanism prevents premature exposure to overly difficult samples by only increasing allocation when the smoothed category loss has decreased by at least a factor of gamma over e epochs, which avoids the risks of static heuristics that lead to poor generalization.

Lu: This addresses the instability issue where we might push things too hard too fast.

Meng: That’s exactly what we want to avoid; not letting us get stuck in a local optimum just because we kept adding more data.

Tom: And they also show that the optimal maximum negative budget theta max is dataset dependent, which means this isn't a one-size-fits-all approach.

Jane: So it’s not about using a fixed budget for every single graph type; it’s about finding the right constraints for each scenario.

Lu: They also show that their framework aims to be compact, discriminative, and generalizable by prioritizing informative hard negatives when they remain discriminative and using stochastic swapping to prevent contrastive saturation.

Meng: That focus on quality over sheer quantity seems like the most important engineering principle here.

Conclusion: Tom: So wrapping up this discussion on "AdNGCL: Adaptive Negative Scheduling for Graph Contrastive Learning," the main implication is that negative mining can be treated as a constrained, loss-gated scheduling problem.

Jane: They’ve achieved this by combining similarity-based stratification with warm-start with a loss gate, loss-aware step sizes under local and global caps, and stochastic swapping at a fixed budget.

Lu: The big picture is that they are aiming to maximize contrastive signal per unit compute while curbing false-negative exposure.

Meng: From an engineering standpoint, it means faster and more stable convergence with fewer negatives, plus stronger performance on sparse graphs via higher theta max, and lower memory latency than static curricula.

Tom: It’s a lot of structure to follow, but it provides a very concrete way to approach this problem.

Jane: It’s definitely a sophisticated method that should be considered when we're designing new contrastive learning systems for graph data.

Lu: We think the framework gives us a principled way to handle the complexity of negative mining in these representations.

University of Science and Technology of China · Hainan University · Manchester Metropolitan University

cs.LG

Submitted: 2026-05-04

Updated: 2026-10-13

Comments: Substantially revised methodology and experimental evaluation. Updated HANS scheduling and candidate-management mechanisms, independently evaluated baselines under a unified evaluation protocol, and expanded ablation, sensitivity, and computational analyses

Code: https://github.com/mhadnanali/AdNGCL

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 89/100

The gist: The gist The proposed framework, AdNGCL, introduces an adaptive negative scheduling mechanism to Graph Contrastive Learning that formulates negative selection as a loss-gated, budget-constrained

Key concepts

Hardness-Aware Negative Scheduling (HANS)
HANS treats negative mining as a budgeted scheduling problem. It sorts negatives into hard, intermediate, and easy groups based on similarity. It then gradually activates these categories using a warm-up phase, only increasing the allocation when performance plateaus.
Loss Gate (Adjustment Trigger)
The Loss Gate acts as an adjustment trigger in HANS. It monitors whether the smoothed category loss has decreased significantly over several epochs. This mechanism ensures that negative sample allocations are increased only when performance shows signs of improvement, preventing unnecessary increases.
Adaptive Allocation and Swapping
This component modulates update magnitudes based on how much loss each category contributes. If the global budget is full, a swapping phase occurs where negatives are periodically re-sampled from their hardness pools to introduce variety and avoid contrastive saturation.

Terminology

Summary

The gist The proposed framework, AdNGCL, introduces an adaptive negative scheduling mechanism to Graph Contrastive Learning that formulates negative selection as a loss-gated, budget-constrained process across hard, intermediate, and easy strata.

AdNGCL Framework Overview

AdNGCL is a graph contrastive learning framework that incorporates a novel hardness-aware scheduling mechanism to learn node embeddings without supervision The framework consists of five core modules: (1) Graph Data Augmentation, (2) Learning, (3) Contrastive Samples and Loss (Loss), (4) Hardness-Aware Negative Scheduling (HANS), and (5) Embedding Extraction and Downstream Evaluation.

Graph Data Augmentation

The graph data augmentation module modifies the input graph’s structure and features to create multiple augmented views It employs three techniques, including Edge Removal, which creates a temporary binary masking matrix Mˆe where entries are drawn from a Bernoulli distribution B(1 − pe), and Feature Masking, which utilizes two strategies to cope with dataset diversity. Specifically, View 1 generates a binary mask vector νˆ1 ∈ B(1 − pf) to compute the augmented feature matrix Xˆ 1, and View 2 applies a more refined masking strategy involving fixed columns and 2-dimensional feature masking for the remaining unfixed columns.

Contrastive Learning and Loss Function

The learning module utilizes a two-layer Graph Convolutional Network (GCN) encoder followed by a projection head to map augmented graph views into a latent space. The positive sample pair is formed by the node embeddings h 1 i and h 2 i derived from the two augmented views, representing the same semantic entity in different views. The negative sample set Ni is constructed by pairing an anchor embedding h 1 i with embeddings of other nodes from both views, i.e., Ni = (h 1 i, h 2 j) j!= i, vj ∈ V. The contrastive loss L maximizes agreement between positive sample pairs and minimizes agreement with negative sample pairs

Hardness-Aware Negative Scheduling (HANS)

The HANS algorithm treats negative mining as a budgeted scheduling problem It proceeds in four stages, starting with Negative Sample Stratification, where negatives are partitioned into hard, intermediate, and easy sets based on similarity s(·, ·). Budgeting involves capping the total negatives per anchor by a global budget θmax ∈ (0, 1] and per-category caps θ cat max. Bootstrap Scheduling gradually activates each category using a warm-up phase, where the fraction of the fixed category budget used is denoted by η cat t. The Loss Gate (Adjustment Trigger) checks if the smoothed category loss has decreased by at least a factor γ over the last e epochs before increasing the allocation, ensuring that increments are applied only when performance plateaus.

Adaptive Allocation and Swapping

HANS introduces Loss-Aware Step Size to modulate update magnitudes based on category loss shares and training saturation. The step size ∆η cat t is defined by the minimum of four factors, ensuring that negative sample inclusion is strictly governed by the informativeness of the category as reflected in the loss dynamics while respecting resource constraints. Furthermore, a Swapping phase is introduced once the global negative sample budget θmax is saturated and each category has reached its per-category cap. This swapping involves periodically re-sampling negatives from their respective hardness pools to increase variety and prevent contrastive saturation.

Experimental Findings and Implications

Experiments on nine benchmark graph datasets demonstrate that AdNGCL consistently advances state-of-the-art performance—achieving the best accuracy on seven datasets and second-best on the remaining two—while offering explicit control over computational cost. Ablation studies show that increasing the hard negative proportion from 10% to 40% yields systematic gains across datasets, underscoring the importance of informative negative pressure. The optimal maximum negative budget θmax is dataset dependent: sparse/low-homophily graphs benefit from higher budgets (70–100%), whereas dense graphs saturate near 40–60%. Efficiency analyses further reveal diminishing returns beyond these plateaus, underscoring HANS’s role in balancing accuracy and compute for CE deployments.

Computational Complexity

The total cost per epoch is dominated by (i) the GNN encoder, (ii) similarity evaluation for the contrastive loss, and (iii) HANS scheduling. The amortized similarity cost per epoch is O(θmaxn 2d + 1/Tint O(n 2d + n 2log n). In conclusion, AdNGCL’s loss-gated budgeting systematically strengthens contrast while controlling compute.

Conclusion and Future Directions

AdNGCL recasts negative mining as a constrained, loss-gated scheduling problem over hardness strata By combining (i) similarity-based stratification, (ii) warm-start with a loss gate, (iii) loss-aware step sizes under local/global caps, and (iv) stochastic swapping at a fixed budget, the framework aims to maximize contrastive signal per unit compute while curbing false-negative exposure. Future directions include replacing manual budgets with auto-tuned schedules that learn θmax, per-category caps, and step sizes from simple self-supervised signals during training. The framework is designed to yield testable predictions: faster and more stable convergence with fewer negatives, stronger performance on sparse graphs via higher θmax, and lower memory/latency than static curricula.

Acknowledgments

This should be a simple paragraph before the References to thank those individuals and institutions who have supported your work on this article

References

[1] Z. Zhao, J. Liu, N. Huang, P. Jiao, and H. Wu, “Graph contrastive learning for multi-behavior recommender system,” IEEE Transactions on Consumer Electronics, vol. 71, no. 2, pp. 7269–7279.

[2] B. Xu, J. Wang, Z. Zhao, H. Lin, and F. Xia, “Unsupervised anomaly detection on attributed networks with graph contrastive learning for consumer electronics security,” IEEE Transactions on Consumer Electronics, vol. 70, no. 1, pp. 4062–4072.

[3] G. Ni, Z. Chen, J. Jiang, J. Luo, and Y. Ma, “Incremental updates based on graph theory for consumer electronic devices,” IEEE Transactions on Consumer Electronics, vol. 61, no. 1, pp. 128–136.

[4] S. Li, W. Li, A. M. Luvembe, and W. Tong, “Graph contrastive learning with feature augmentation for rumor detection,” IEEE Transactions on Computational Social Systems, vol. 11, no. 4, pp. 5158–5167.

[5] C. Niu, G. Pang, and L. Chen, “Affinity uncertainty-based hard negative mining in graph contrastive learning,” IEEE Transactions on Neural Networks and Learning Systems, vol. 35, no. 9, pp. 11 681–11 691.

[6] W. Ju, Z. Fang, Y. Gu, Z. Liu, Q. Long, Z. Qiao, Y. Qin, J. Shen, F. Sun, Z Xiao et al.

Improvements for AI systems

  1. Bold header: Loss-gated, budget-aware scheduling via HANS

This framework formulates negative selection as a loss-gated, budget-constrained process across hard, intermediate, and easy strata. This allows the system to dynamically adjust step sizes based on contrastive loss trends under both global and per-category budgets, which optimizes quantity and informativeness during training.

  1. Bold header: Adaptive negative sampling for sparse vs. dense graphs

The scheduler proposes using a higher proportion of negative samples (70% to 90%) for sparse datasets, in contrast to dense datasets (40% to 60%), which directly addresses the dataset density and hardness levels limitations of previous static methods.

  1. Bold header: Enhanced robustness against overfitting and instability

The mechanism prevents premature exposure to overly difficult samples by only increasing allocation when the smoothed category loss has decreased by at least a factor γ over the last e epochs, thereby avoiding the risks of static heuristics that lead to poor generalization.

  1. Bold header: Controlled computational cost for CE deployment

The system implements a strategy where increasing negatives consistently raises training time, but the final conclusion suggests using 40–60% budgets can retain accuracy while cutting training time by 30–50%, which is critical for on-device learning pipelines.

  1. Bold header: Improved embedding discriminative quality

AdNGCL ensures the learned embeddings are compact, discriminative, and generalizable by prioritizing informative hard negatives when they remain discriminative and using stochastic swapping to prevent contrastive saturation.

Related papers