acceptodds
Under review as a conference paper at ICLR 2027

AdaDGL: Adaptive Distributional Negative Sampling for Robust Dynamic Graph Learning

Abstract

Dynamic graph models are commonly trained and evaluated with sampled negative edges, making their performance inherently dependent on the underlying negative sampling distribution. However, existing methods typically rely on a fixed distribution, such as random, historical, or inductive sampling. This creates a negative sampling distribution shift: models trained under one distribution can degrade substantially when evaluated under another, while evaluation with easy random negatives can overestimate model performance. We propose , an adaptive distributional negative sampling framework for robust dynamic graph learning under such shifts. During training, AdaDGL samples similarity-aware negatives from broadly covered candidates to balance hardness and coverage. At inference, it constructs hard negatives for reliable evaluation when the target distribution is unknown, and efficiently adapts the prediction head when the target distribution is known. Experiments across multiple datasets and backbones show consistent gains under different negative sampling distributions, with up to average precision improvement and training acceleration when supporting multiple target distributions.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Temporal Graph Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_W6BjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how changes in negative sampling distributions affect dynamic graph learning. It proposes AdaDGL, which samples training negatives according to their similarity to the positive destination node. For evaluation, it constructs harder negatives when the target distribution is unknown, or adapts the prediction head when the distribution is known. Experiments across multiple datasets and dynamic graph backbones show improvements under different negative sampling settings.

Critical strengths
  1. The paper addresses a practical issue: negative sampling affects both model training and evaluation difficulty. Studying performance across different sampling distributions is useful for assessing robustness.

  2. The method can be integrated into existing backbones with few architectural changes. The supplementary comparisons with matched prediction-head adaptation help separate the benefits of sampling from those of additional fine-tuning.

Critical weaknesses
  1. The method appears to offer limited novelty. Existing methods already use dynamic node embeddings to select hard negatives. AdaDGL mainly changes which node is used to compute similarity and how negatives are sampled, then fine-tunes the prediction head in a standard way. Although the results improve, these changes seem relatively small, and the paper does not clearly show what they add beyond existing hard-negative sampling methods.
  2. Theorem 4 claims that every node has a chance of being selected as a negative. But randomly choosing candidates does not guarantee this, since SNS keeps only the most similar one. With distinct similarity scores and at least two candidates sampled without replacement, the least similar node can never be selected. The authors should clarify the sampling rule and explain why the claim holds.
  3. Harder negatives do not necessarily make the evaluation more reliable. A lower AP under SNS shows that the test is harder, but not that it measures model performance more accurately. The authors should explain why choosing negatives similar to the positive destination gives a better evaluation, especially when the target negative distribution is unknown.
Questions for authors
  1. What is the main technical advance over existing hard-negative sampling methods such as NHS, and why does it help when the negative sampling distribution changes?

  2. Does SNS sample candidates with or without replacement? Under what conditions can every node be selected as a negative, as claimed in Theorem 4?

  3. What evidence, beyond a lower AP, supports SNS as a more reliable evaluation method when the target negative distribution is unknown?

Reviewer_9MDZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper shows that dynamic link prediction models are sensitive to the negative sampling distribution used in training and testing. It proposes AdaDGL: similarity-weighted negative sampling for training (DNS), hard-negative sampling for testing (SNS), and head-only fine-tuning for a known target distribution. It is tested on three backbones and nine datasets.

Critical strengths
  • The area of dynamic graphs and negative distributions are important and the paper tackles a real problem on dynamic graphs. The method is practical and clearly motivated and presented.
  • A model trained on one type of negatives (random, historical, or inductive) can perform worse on another distribution.
  • The approach based on DNS and head-only fine-tuning on existing backbones (ex: TGN, TIDFormer) is elegant, cheap, with good experimental support.
Critical weaknesses
  • Authors claim "During training, AdaDGL samples similarity-aware negatives from broadly covered candidates to balance hardness and coverage.". However "balances hardness" is not fully shown. No data to compare training negatives with random, historical, or inductive sampling.

  • Appendix A.2 – Step 3: Conclusion The term ‘Combining’ in Combining Step 2 and Step3) is not what’s intended, perhaps you mean ‘Inferring from Step 2 and Step 3’?

  • Proof in Steps 1–3 is a bit of a too large leap. Specially as the core contribution is based on DNS being better than random sampling in given env, the authors needs to provide a more robust derivation or a more detailed explanation.

  • Authors use LLN (law of large numbers), but |C| = k = 10 is fixed in all experiments. Please explain why asymptotic convergence is relevant at k=10, or provide a finite-sample bound

  • Hard-negative mining with cosine similarity/distance, embedding cache, head-only adaptation are each established ideas. Can the authors experimentally show what is unique (cache, false-negative exclusion rule, temperature schedule) more predominantly and move the closest competitors (ENS, NHS) from Appendix to main body.

  • DNS is similar to SIR and self-adversarial sampling (RotatE), as well as softmax-weighted hard-negative contrastive methods. Please explain what is different, ideally with 1 on 1 comparison

  1. Tables 19/20 add Random + Fine-tune baselines. But the main baselines are still trained with random negatives and evaluated under random, historical, inductive, and SNS distributions, while AdaDGL is trained with its own DNS.
  • Table 3 results show very small gaps and the authors give no significance test - the gaps are inside one standard deviation?

  • The 2.98× speedup is relative to retraining one model per distribution. Compared against head-only fine-tuning of a single baseline, the gain is unclear. Also Authors need to comment on SNS cost per edge.

Questions for authors

JODIE outperforms AdaTIDF on Wikipedia. As node classification does not involve negative edges, can the Authors explain how DNS, SNS or head adaptation benefits from it?

Reviewer_dmzzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes an adaptive distributional negative sampling framework for robust dynamic graph learning. The main contributions are summarized as follows: (1) The proposed framework employs similarity-aware negative sampling from a diverse candidate set to balance negative sample hardness and coverage. (2) The framework constructs hard negatives for reliable evaluation when the target distribution is unknown, and efficiently adapts the prediction head when the target distribution is known.

Critical strengths

(1) This paper addresses the negative sampling distribution shift problem in dynamic graph learning. (2) The proposed framework can be integrated with different dynamic graph models and adapt to various negative sampling distributions. (3) Extensive experimental results on multiple datasets and backbones demonstrate performance improvements.

Critical weaknesses

(1) Theorem 4 claims SNS achieves full coverage. However, SNS selects the most similar node from k randomly sampled candidates. Under this strategy, some low-similarity nodes may have zero probability of being selected, which contradicts the claimed full coverage guarantee. (2) Theorem 2 claims that DNS achieves a smaller KL divergence from the target distribution than random sampling. However, this inequality does not generally hold. In particular, the DNS distribution in Eq. (2) involves a temperature parameter, while the target distribution in Eq. (3) does not. Different temperature settings may lead to a larger KL divergence for DNS than for random sampling. (3) Eq. (4) defines coverage based on the number of nodes with zero sampling probability, where a smaller value indicates broader coverage. However, the experimental analysis in Figs. 9 and 12 treats higher coverage values as broader candidate coverage. This paper should clarify the relationship between these definitions and whether the experiments actually validate the theoretical claims. (4) Similarity-based hard negative sampling has been extensively studied. The proposed sampling strategy mainly relies on similarity-based selection and prediction-head fine-tuning. This paper should further clarify the technical differences and advantages of AdaDGL over existing negative sampling methods. (5) Table 14 reports zero false negatives across all datasets, but it is unclear whether future positive edges are considered when identifying false negatives. Moreover, this paper also should clarify whether SNS uses the same negative samples across different models to ensure fair evaluation.

Questions for authors

None.

Reviewer_bQzHOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes AdaDGL to address the sensitivity of temporal link predicition to negative sampling. The idea is to sample traiining training negatives based on similarity within a random pool of candidates, with cached embeddings to reduce computation overhead. The authors also propose hard negative eval and prediction head adaptation. Experiments show improvement across several temporal graph datasets and backbones.

Critical strengths
  1. The topic studies is definitely important. Negative sampling certainly affects training signficantly Although there's a long line of work on negative sampling for static graphs, temporal graphs are a less explored region.
  2. The reported improvements span several backbones and seem consistent
Critical weaknesses
  1. I have a main concern over the theoretical correctness. Lemma 1 uses a law-of-large-numbers argument over candidate-set size, but the algorithm fixes that size at ten. I have carefully read the proof but it seems to me increasing training epochs does not establish convergence to the full-node softmax distribution. Repeatedly drawing ten candidates only estimates the ten-candidate sampler more accurately.
  2. I am not sure if the inference complexity analysis is correct. SNS examines (\epsilon|V|) candidates per query, so its sampling cost grows with the node universe. However, Appendix B.2 states that the computations per node do not depend on that universe and claims the same asymptotic cost as random sampling.
Questions for authors

Please share your response to the two weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.