  Negative sampling plays a crucial role in training successful sequential
recommendation models. Instead of merely employing random negative sample
selection, numerous strategies have been proposed to mine informative negative
samples to enhance training and performance. However, few of these approaches
utilize structural information. In this work, we observe that as training
progresses, the distributions of node-pair similarities in different groups
with varying degrees of neighborhood overlap change significantly, suggesting
that item pairs in distinct groups may possess different negative
relationships. Motivated by this observation, we propose a Graph-based Negative
sampling approach based on Neighborhood Overlap (GNNO) to exploit structural
information hidden in user behaviors for negative mining. GNNO first constructs
a global weighted item transition graph using training sequences. Subsequently,
it mines hard negative samples based on the degree of overlap with the target
item on the graph. Furthermore, GNNO employs curriculum learning to control the
hardness of negative samples, progressing from easy to difficult. Extensive
experiments on three Amazon benchmarks demonstrate GNNO's effectiveness in
consistently enhancing the performance of various state-of-the-art models and
surpassing existing negative sampling strategies. The code will be released at
\url{https://github.com/floatSDSDS/GNNO}.
