Negative Sampling, 링크 예측에서 없는 간선을 고르는 기준

2026년 4월 29일 | 개발 공부

---

Negative Sampling은 링크 예측에서 실제로 존재하는 간선(positive edge)만으로 학습하지 않고, 그래프에 연결되지 않은 노드 쌍을 일부 뽑아 negative edge로 같이 넣는 절차다. 링크 예측은 “어떤 두 노드 사이에 간선이 생길 가능성이 있는가”를 맞히는 문제인데, positive만 보면 모델은 구분을 배울 수 없다. 그래서 없는 간선을 함께 보여 주고, 이 둘을 가르는 점수를 학습시킨다.

나는 처음에 negative sampling을 꽤 단순하게 봤다. 그래프에 없는 간선 중에서 아무거나 뽑으면 되는 줄 알았다. 그런데 최근 GNN 링크 예측 실험에서 false positive와 false negative를 edge 단위로 펼쳐 보니, 이 단계가 생각보다 앞쪽에 있었다. 어떤 negative를 뽑았는지에 따라 AUC가 쉬워지기도 하고, threshold sweep에서 보이는 오류 방향도 달라진다. 모델 해석을 하고 있다고 생각했는데, 사실은 샘플링 정책을 같이 읽고 있었던 셈이다.

1. positive와 negative는 대칭 라벨이 아니다

분류 문제처럼 보면 positive와 negative는 그냥 1과 0이다. 하지만 그래프에서는 이 둘이 완전히 대칭이 아니다. positive edge는 적어도 관측 데이터 안에서 실제로 존재한 관계다. 반면 negative edge는 “관측되지 않은 관계”일 뿐이다. 특히 추천, 지식 그래프, 소셜 그래프처럼 데이터가 빠질 수 있는 영역에서는 없는 것과 아직 보지 못한 것이 쉽게 섞인다.

작은 toy graph에서는 닫힌 세계 가정을 두고 “현재 edge set에 없으면 negative 후보”라고 둘 수 있다. 내가 굴리는 GNN 실험도 이 정도의 통제된 판에서 시작했다. 그래도 여기서조차 조심할 지점이 있다. test positive로 빼 둔 edge는 train graph 안에서는 사라져 보인다. 만약 train graph 기준으로만 negative 후보를 만들면, 나중에 맞혀야 할 held-out positive가 negative 후보에 섞일 수 있다. 이건 모델이 어려운 문제를 푸는 게 아니라, 평가판이 스스로 꼬이는 쪽에 가깝다.

구분	겉으로 보이는 뜻	실험에서 따로 적어야 할 기준
positive edge	관측된 실제 간선	train/validation/test로 어떻게 holdout했는지
negative edge	관측되지 않은 노드 쌍	원본 graph 기준인지, train graph 기준인지
hard negative	positive처럼 보이는 negative	공통 이웃, 거리, degree 같은 난이도 조건
easy negative	멀리 떨어진 명백한 negative	너무 많으면 평가가 쉬워지는지

2. “없는 간선”의 후보 공간을 먼저 고정해야 한다

negative sampling에서 제일 먼저 정해야 할 것은 후보 공간이다. 전체 노드 쌍 중 self-loop를 빼고, 이미 존재하는 edge를 빼고, 그 나머지에서 뽑는 방식이 가장 단순하다. 그런데 여기서 “이미 존재하는 edge”를 어느 시점의 그래프로 볼지가 중요하다. 원본 graph의 모든 positive를 제외할 것인지, train graph에 남은 edge만 제외할 것인지에 따라 후보가 달라진다.

링크 예측 평가에서는 보통 validation/test positive를 일부러 숨긴다. 그래서 train graph만 보면 그 edge는 없는 간선처럼 보인다. 하지만 평가 관점에서는 그 edge가 바로 맞혀야 할 positive다. 나는 이 지점이 은근히 헷갈렸다. 모델 입력으로 쓰는 graph와, negative 후보를 만들 때 기준으로 삼는 graph가 항상 같아야 한다고 생각하기 쉽기 때문이다. 실제로는 둘을 분리하는 편이 안전하다. 모델은 train graph만 보되, negative 후보에서는 원본 positive 전체를 제외해야 평가 라벨이 덜 꼬인다.

이 기준을 적어 두면 split stability도 더 선명해진다. 같은 seed를 줬는데 결과가 달라지는 문제를 고칠 때는 edge 순서, train graph의 node 보존, random seed만 보는 게 아니다. negative candidate universe가 같은지도 같이 봐야 한다. seed가 같아도 후보 목록 자체가 달라지면, 모델이 본 negative 예제가 달라지고, 그 뒤의 AUC와 FP/FN 표도 다른 이야기가 된다.

3. 쉬운 negative와 어려운 negative는 다른 문제를 만든다

전체 non-edge에서 균등하게 뽑으면 구현은 쉽다. 작은 그래프에서는 이 정도로도 실험을 시작할 수 있다. 다만 이 방식은 대체로 쉬운 negative를 많이 만든다. 서로 멀리 떨어져 있고 공통 이웃도 거의 없는 노드 쌍은 모델 입장에서 구분이 쉽다. 이런 샘플이 많으면 점수표는 좋아 보이지만, 실제로 헷갈리는 후보를 얼마나 구분하는지는 잘 안 보일 수 있다.

반대로 hard negative를 일부러 많이 넣으면 평가는 훨씬 까다로워진다. 공통 이웃이 많거나, degree가 비슷하거나, 같은 community 안에 있는 non-edge를 negative로 뽑으면 모델은 더 미묘한 차이를 배워야 한다. 이때 점수가 떨어진다고 해서 모델이 무조건 나빠진 것은 아니다. 문제를 더 어려운 쪽으로 바꾼 결과일 수 있다. 그래서 negative sampling 정책을 적지 않은 AUC 표는 읽을 때 늘 한 박자 늦춰야 한다.

내가 요즘 보는 GNN 결과에서도 이 차이가 중요했다. `reduced_plus_degree`는 false negative가 거의 없고 negative edge를 positive로 올리는 쪽으로 자주 틀렸다. `propagation_only`는 반대로 positive edge를 놓치는 쪽이 더 컸다. 이 해석은 모델 구조만으로 끝나지 않는다. negative edge가 얼마나 어려운 후보였는지, 같은 graph family 안에서 어떤 context를 가진 pair였는지까지 같이 봐야 한다. false positive-heavy라는 말도 샘플링된 negative의 난이도를 벗어나면 의미가 줄어든다.

4. threshold sweep도 negative sampling 위에서 읽힌다

최근 threshold sweep을 하면서 0.5 cutoff 하나로 FP/FN을 자르는 게 너무 거칠다는 생각을 했다. threshold를 낮추면 false negative를 줄일 수 있고, 대신 false positive가 늘어난다. 여기까지는 익숙한 trade-off다. 그런데 이 곡선도 결국 어떤 negative를 test에 올렸는지 위에서 그려진다. test negative가 너무 쉬우면 threshold를 낮춰도 false positive가 덜 늘 수 있고, hard negative가 많으면 작은 cutoff 이동에도 false positive가 확 튈 수 있다.

그래서 threshold sweep을 calibration처럼 쓰려면 최소한 두 가지가 필요하다. 첫째, threshold를 test edge에서 직접 고르면 안 된다. validation에서 고른 threshold를 test에 적용해야 한다. 둘째, validation negative와 test negative가 비슷한 난이도 분포에서 왔는지 확인해야 한다. validation은 쉬운 negative 위주인데 test는 hard negative 위주라면, threshold 하나가 잘 일반화될 가능성은 낮다.

이걸 적고 나니 edge-case table을 보는 순서도 조금 바뀌었다. 전에는 probability가 0.5 위냐 아래냐를 먼저 봤다. 이제는 그 edge가 어떤 negative 후보군에서 나온 것인지, 같은 graph family 안에서 쉬운 pair인지 어려운 pair인지도 옆에 붙이고 싶다. score calibration과 sampling policy를 따로 적어야, 나중에 모델을 고쳐야 하는지 샘플링을 고쳐야 하는지 덜 헷갈린다.

5. 내가 남겨 두는 체크리스트

링크 예측 실험을 다시 짤 때는 negative sampling을 보조 함수로 밀어 넣기 전에, 아래 항목을 먼저 적어 두려고 한다. 이건 거창한 이론이라기보다, 결과표를 나중에 다시 열었을 때 “이 숫자가 어떤 판에서 나온 숫자인가”를 잃지 않기 위한 작은 메모에 가깝다.

• 후보 공간: 원본 graph의 모든 positive를 제외했는지, train graph 기준으로만 제외했는지 적는다.
• 난이도 분포: uniform negative인지, 공통 이웃이나 거리 조건을 둔 hard negative인지 구분한다.
• 샘플 비율: positive와 negative를 1:1로 맞췄는지, 실제 class imbalance를 일부 반영했는지 적는다.
• seed와 중복: 같은 seed에서 후보 목록이 재현되는지, replacement를 허용했는지 확인한다.
• 분리된 기준: 모델 입력 graph와 negative 후보 graph를 같은 객체로 뭉개지 않는다.
• threshold 검증: test에서 고른 cutoff를 성능처럼 말하지 않고, validation-selected threshold를 따로 둔다.

결국 negative sampling은 “없는 간선 몇 개 뽑기”가 아니라, 링크 예측 문제가 어떤 종류의 구분 문제인지 정하는 단계다. 쉬운 non-edge를 많이 뽑으면 모델은 명백한 부재를 잘 맞히는 쪽으로 보이고, hard negative를 넣으면 관계가 생길 법한 후보를 더 까다롭게 가르는 쪽으로 평가된다. 둘 중 하나가 항상 맞다기보다, 내가 지금 평가하고 싶은 사용 장면과 맞아야 한다.

당분간 GNN 실험에서는 평균 AUC 옆에 negative sampling 메모를 같이 붙일 생각이다. GraphSAGE 입력판, split stability, edge-case table, threshold sweep을 아무리 촘촘히 만들어도, negative 후보가 어떻게 만들어졌는지 빠지면 해석의 바닥이 비어 버린다. 모델이 negative를 잘 구분한 것인지, 내가 너무 쉬운 negative를 준 것인지. 그 한 줄을 분리해 적는 것만으로도 결과표 앞에서 덜 허둥대게 된다.

관련해서 이전에 정리한 GraphSAGE feature importance 조합 읽기와 threshold sweep 글을 같이 보면 흐름이 이어진다. 그 글들이 feature와 cutoff를 보는 쪽이었다면, 이번 메모는 그보다 한 칸 앞에서 “비교할 negative가 어떻게 만들어졌는가”를 따로 적어 두자는 쪽에 가깝다.