[논문 번역] Region or Global? A Principle for Negative Sampling in Graph-based Recommendation `with GPT`

Meosun·2025년 1월 25일

논문 번역

목록 보기

1/2

지역 또는 글로벌? 그래프 기반 추천에서의 네거티브 샘플링 원칙

저자

Zhen Yang, Ming Ding, Xu Zou, Jie Tang, Bin Xu, Chang Zhou, Hongxia Yang

초록

그래프 기반 추천 시스템은 최근 빠르게 발전하고 있으며, 사용자-아이템 상호작용을 사용자-아이템 그래프로 모델링하고 그래프 신경망(Graph Neural Networks, GNN)을 활용하여 사용자 및 아이템의 임베딩을 학습합니다. 그래프 기반 추천의 근본적인 도전 과제는 사용자-아이템 그래프에서 관찰 가능한 양성 사용자-아이템 쌍만 존재한다는 점입니다. 네거티브 샘플링(Negative Sampling)은 이러한 단일 클래스 문제를 해결하는 핵심 기술로, 다양한 추천 방법에서 널리 사용됩니다. 하지만 이전 연구들은 네거티브 샘플링 분포 설계에만 초점을 맞췄을 뿐, 네거티브 샘플링 영역에 대해서는 충분히 고려하지 않았습니다.

본 연구에서는 네거티브 샘플링을 가이드하기 위해 세 영역 원칙(Three-Region Principle)을 제안합니다. 이 원칙은 중간 영역에서 더 많은 아이템을 네거티브로 샘플링하고, 인접 및 먼 영역에서의 샘플링은 줄여야 한다고 제안합니다. 이 원칙을 기반으로, 우리는 두 가지 샘플링 전략(양성 보조 샘플링 및 노출 보강 샘플링)을 결합하여 설계된 일반적인 네거티브 샘플링 방법 RecNS를 제시합니다. 기존의 그래프 데이터에서 존재하는 네거티브 아이템을 샘플링하는 대신, 이 두 전략을 임베딩 공간에서 병합하여 네거티브 아이템 임베딩을 생성합니다.

광범위한 실험을 통해 RecNS 방법이 모든 네거티브 샘플링 기준치를 초과하는 성능을 보여준다는 것을 증명했습니다. 예를 들어 Alibaba 데이터셋에서 Recall@20 측면에서 PinSage는 10.47%, NGCF는 6.02%, LightGCN은 8.20%의 향상을 보였습니다.

핵심 용어: 네거티브 샘플링, 세 영역 원칙, 임베딩 병합, 그래프 기반 추천

1. 서론

최근 몇 년간 추천 시스템 연구의 주요 관심사는 협업 필터링(Collaborative Filtering, CF)에서 그래프 기반 추천으로의 발전입니다 [1], [2], [3], [4], [5]. 그래프 기반 추천은 사용자-아이템 상호작용을 사용자-아이템 그래프로 모델링하며, 그래프 신경망(GNN)을 활용하여 사용자와 아이템의 임베딩 학습 과정에 구조적 정보를 통합합니다.

그래프 기반 추천의 핵심 목표는 고품질의 임베딩을 학습하고 학습된 임베딩을 통해 사용자-아이템 상호작용 가능성을 추정하는 것입니다. 이는 온라인 쇼핑, 소셜 네트워크, 광고 등 다양한 분야에서 널리 활용됩니다. GNN의 급속한 발전은 그래프 기반 추천의 부상을 이끄는 근본적인 원동력으로 작용하고 있습니다. 특히, 그래프 기반 추천은 차세대 추천 기술의 핵심이 될 가능성을 보이며, 웹 스케일 애플리케이션을 지원할 수 있는 유망한 기술로 평가받고 있습니다.

그러나 사용자-아이템 그래프에서 양성 쌍(positive pair)만 관찰 가능하며, 다른 아이템은 사용자와 연결되지 않은 상태로 관찰되지 않는 쌍으로 간주된다는 점에서 중요한 도전 과제가 있습니다. 이 문제를 해결하기 위해 네거티브 샘플링(Negative Sampling)이 중요한 기술로 자리잡았습니다.

네거티브 샘플링은 이전 연구들에서 널리 채택되었으며 [9], [10], [11], [12], 샘플링 전략은 전역적으로 관찰되지 않은 아이템 영역에서 소수의 네거티브 아이템만 선택하여 양성 아이템과 구별하는 모델을 훈련하는 데 사용되었습니다. 네거티브 샘플링은 훈련 과정을 가속화하고 계산 복잡도를 줄이며 대규모 그래프 기반 추천이 가능하게 합니다. 또한, 여러 연구 결과는 네거티브 아이템의 품질이 사용자/아이템 임베딩의 품질 및 추천 작업의 효율성에 영향을 미친다는 것을 보여줍니다 [8], [13].

그림 1. 임베딩 공간에서 양성 보조 샘플링과 노출 보강 샘플링을 병합하는 RecNS의 개요.

[14]에서는 유용한 표현 학습을 위해 어려운(hard) 네거티브 샘플의 상위 5%만 필요하며 충분하다는 것을 발견했습니다. 전통적으로, 네거티브 샘플링에 있어 가장 널리 사용되는 전략은 균일 분포(uniform distribution)를 사용하는 것입니다 [4], [15]. 네거티브 아이템의 품질을 향상시키기 위해, 여러 연구에서는 새로운 네거티브 샘플링 분포를 설계하려 시도해왔으며, 이는 현재 모델을 기반으로 어려운 네거티브 아이템(hard negative items)을 샘플링하는 방식입니다 [16], [17], [18]. 그래프 기반 추천에서 네거티브 샘플링 전략(예: MCNS [19] 및 PinSage [1])은 각각 자기대조(self-contrast) 근사 및 Metropolis-Hastings, 또는 PageRank 점수를 기반으로 네거티브 아이템을 샘플링합니다. 그러나 이와 같은 연구들은 그래프 신경망(GNN)의 정보 전파 메커니즘에서 샘플링 영역의 선택을 간과하고 네거티브 샘플링 분포 설계에만 초점을 맞추고 있습니다.

예를 들어, LightGCN [4]의 실험 결과는 레이어 수가 1에서 4로 증가할 때 대부분의 경우 레이어 2에서 성능이 정점을 찍은 후 감소하기 시작한다는 것을 보여줍니다. 이러한 결과에 대응하여, 저자들은 노드의 임베딩을 1차 및 2차 이웃과 함께 매끄럽게 처리하는 것이 매우 유용하지만, 더 높은 차수의 이웃을 사용할 경우 과도한 매끄러움(over-smoothing) 문제로 인해 성능이 저하된다고 주장합니다. 사실, 네트워크 레이어를 심화할 때 과도한 매끄러움 문제는 피할 수 없으나, 보다 효과적인 네거티브 샘플링 방법을 설계하여 추천 성능을 추가로 개선할 수 있습니다.

본 논문에서는 구조적 유사성에 따라 네거티브 아이템을 샘플링하기 위해 그래프 구조를 활용합니다. 사용자-아이템 그래프에서는 짧은 홉(hop)에 위치한 이웃들이 중심 노드와 더 높은 관련성을 가질 가능성이 높습니다. 이러한 짧은 홉 이웃들을 통한 정보 전파는 성능을 향상시킬 수 있으며, 중심 노드에 대해 더 긍정적인 정보를 전달할 가능성이 높습니다. 반면, 더 긴 홉 이웃들을 통한 정보 전파는 성능 저하를 초래하며, 이는 이웃의 정보가 추천 성능에 해로울 수 있음을 보여줍니다.

우리의 접근법

위와 같은 관찰을 바탕으로, 네거티브 아이템은 글로벌하게 관찰되지 않은 영역이 아닌 특정 영역에서 샘플링되어야 한다고 주장합니다. 따라서 본 연구에서는 중간 영역(intermediate region)에서 네거티브 아이템을 샘플링하기 위한 세 영역 원칙(Three-Region Principle)을 제안합니다. 이는 네거티브 샘플링에 있어 후보 네거티브 영역으로 고려해야 할 지역을 제시하는 원칙입니다. 이후, 우리는 후보 네거티브 영역에서 네거티브 아이템을 샘플링하기 위한 네거티브 샘플링 분포를 설계하는 RecNS 방법을 제안합니다.

기여

본 논문의 주요 기여는 다음과 같습니다.

세 영역 원칙(Three-Region Principle): 기존의 글로벌하게 관찰되지 않은 아이템 영역에서 샘플링하는 대신, 중간 영역에서 네거티브 아이템을 샘플링하여 보다 유익한 후보 네거티브 아이템을 탐색하도록 가이드하는 원칙을 제안합니다.
RecNS 방법: 양성 보조 샘플링(positive-assisted sampling) 및 노출 보강 샘플링(exposure-augmented sampling)을 임베딩 공간에서 병합하여 최종 네거티브 아이템 임베딩을 생성하는 새로운 네거티브 샘플링 방법을 제안합니다. 이는 기존 그래프 기반 추천 모델에 손쉽게 통합할 수 있습니다.
광범위한 실험: 실험 결과는 RecNS가 기존 네거티브 샘플링 전략보다 우수하다는 것을 보여줍니다. PinSage, NGCF, LightGCN을 사용한 실험에서 각각 10.47%, 6.02%, 8.20%의 Recall@20 성능 향상을 보였습니다.

2. 프레임워크

본 섹션에서는 SampledRec이라는 제안된 프레임워크를 자세히 설명합니다. 이후 SampledRec의 전체적인 과정을 검토합니다. SampledRec 프레임워크의 일반적인 흐름은 그림 2에 나와 있습니다.

그림 2. SampledRec 프레임워크의 일반적인 흐름.

2.1 SampledRec 프레임워크

SampledRec은 사용자와 아이템의 임베딩을 학습하기 위해 그래프 신경망 기반의 인코더 $E_{\theta}$ , 양성 샘플러 $S_p$ , 그리고 네거티브 샘플러 $S_n$ 로 구성됩니다. 이는 각 사용자에 대해 양성 및 네거티브 아이템을 샘플링하며, 샘플링된 사용자-아이템 상호작용은 확률적 경사 하강법(SGD) 최적화를 통한 학습 데이터로 사용됩니다. 학습이 완료된 후, 추천 시스템은 특정 사용자를 위해 가장 큰 $E_{\theta}(u) \cdot E_{\theta}(v)$ 값을 가지는 상위 $K$ 개 아이템을 추천합니다.

2.2 GNN 기반 인코더

그래프 신경망 기반 인코더(GNN-based encoder)는 SampledRec에서 중요한 역할을 하며, 세 가지 모듈로 요약될 수 있습니다.

(1) 집계 모듈 (Aggregation Module)

초기 아이템 및 사용자 임베딩 행렬 $E_V \in \mathbb{R}^{N \times d}$ 와 $E_U \in \mathbb{R}^{M \times d}$ 를 유지합니다. 여기서 $N$ 과 $M$ 은 각각 아이템 및 사용자 수를 나타내며, $d$ 는 임베딩 차원을 나타냅니다. 초기 임베딩 벡터 $e_u \in \mathbb{R}^d$ 와 $e_v \in \mathbb{R}^d$ 는 조회 연산(look-up operation)을 통해 생성됩니다. 직관적으로, 두 가지 유형의 집계 연산이 있습니다: 사용자 집계와 아이템 집계:

h_u = \text{Agg}_{u \gets v}(e_v | v \in S(N_u)),

h_v = \text{Agg}_{v \gets u}(e_u | u \in S(N_v)).

여기서 $N_u$ 와 $N_v$ 는 각각 중심 사용자 $u$ 와 아이템 $v$ 의 이웃을 나타내며, $h_u$ 와 $h_v$ 는 사용자 $u$ 와 아이템 $v$ 의 집계된 임베딩입니다. $\text{Agg}_{u \gets v}$ 와 $\text{Agg}_{v \gets u}$ 는 사용자 및 아이템 집계 함수입니다. $S(\cdot)$ 는 이웃 샘플러를 나타냅니다.

(2) 전파 모듈 (Propagation Module)

사용자와 아이템 간의 더 높은 차수의 상호작용을 캡처하기 위해, 여러 전파 레이어를 쌓아 임베딩을 레이어별로 전파합니다. $h_u^l$ 와 $h_v^l$ 는 $l$ -번째 레이어에서 사용자 및 아이템 임베딩을 나타냅니다. $(l+1)$ -번째 레이어의 임베딩은 $l$ -번째 레이어에서 이웃의 임베딩과 자신의 임베딩에 따라 결정됩니다. 수학적으로, $(l+1)$ -번째 레이어의 사용자 임베딩 $h_u^{l+1}$ 는 다음과 같이 정의됩니다:

h^{l+1} = \text{Agg}_{u \gets v}(e_v^l | v \in S(N_u)),

h_u^{l+1} = f(h^{l+1}, h_u^l).

여기서 $f(\cdot)$ 는 업데이트 함수이며, 아이템 임베딩 벡터는 위에서 언급한 전파 모듈을 통해 동일한 방식으로 표현됩니다.

(3) 예측 모듈 (Prediction Module)

$L$ 개의 레이어를 전파한 후, 사용자 $u$ 와 아이템 $v$ 에 대해 각 레이어의 표현 $\{h_u^1, \cdots, h_u^L\}$ 및 $\{h_v^1, \cdots, h_v^L\}$ 를 얻습니다. 이를 사용하여 최종 사용자 및 아이템 임베딩 $e_u^*$ 와 $e_v^*$ 를 다음과 같이 계산합니다:

e_u^* = g(h_u^1, \cdots, h_u^L),

e_v^* = g(h_v^1, \cdots, h_v^L).

여기서 $g(\cdot)$ 는 융합 함수(fusion function)를 나타냅니다. 최종적으로, 일반적으로 사용되는 내적(inner product)을 통해 사용자의 특정 아이템에 대한 선호도를 다음과 같이 추정합니다:

\hat{r}_{uv} = e_u^* \cdot e_v^*.

2.3 샘플러 (Samplers)

(1) 이웃 샘플러 ( $S$ )

대규모 그래프에서 GNN을 적용하려면 중심 노드에 대한 이웃을 샘플링해야 합니다. GCN(Graph Convolutional Network)은 모든 이웃을 집계에 사용하며, PinSage는 고정된 크기의 이웃을 샘플링합니다. FastGCN [20]은 각 합성 계층에서 이웃을 샘플링할 것을 제안하며, AS-GCN [21]은 적응적 층별 이웃 샘플링 방법을 제안합니다. 이웃 샘플링은 원본 그래프 정보 전파와 계산 효율성의 균형을 맞추는 데 중요한 기술입니다.

(2) 양성 샘플러 ( $S_p$ )

SampledRec에서 사용자-아이템 그래프의 엣지는 양성 사용자-아이템 상호작용으로 가정할 수 있습니다. 따라서 양성 사용자-아이템 상호작용 집합 $O^+$ 는 다음과 같이 정의됩니다:

O^+ = \{(u, v) | u \in U, v \in V\},

여기서 $U$ 는 사용자 집합, $V$ 는 아이템 집합을 나타내며, $(u, v)$ 쌍은 사용자-아이템 그래프에서 연결된 엣지를 나타냅니다.

(3) 네거티브 샘플러 ( $S_n$ )

SampledRec에서는 네거티브 샘플러 $S_n$ 를 사용하여 네거티브 아이템 $v_n \sim S_n(u, v)$ 을 샘플링합니다. 네거티브 샘플링은 오랜 연구 역사를 가지고 있지만, 대부분의 연구는 네거티브 샘플링 분포 $p_n$ 설계에 초점을 맞추며 네거티브 샘플링 영역의 선택은 간과해왔습니다.

2.4 최적화 (Optimization)

SampledRec에서는 GNN 기반 인코더의 매개변수를 최적화하기 위해 힌지 손실(Hinge Loss)을 사용합니다. 이 손실 함수는 한 쌍의 손실(one-pair loss)을 기반으로 정의됩니다. 여기서는 기존 힌지 손실을 $k$ -쌍 손실로 확장하여 확장된 힌지 손실(Augmented Hinge Loss)을 정의하고, 그래프 기반 추천의 성능을 강화합니다. 특정 사용자 $u$ 와 해당 양성 아이템 $v$ 에 대해 $k$ 개의 네거티브 아이템 $v_n$ 을 샘플링하여 다음의 확장된 힌지 손실을 최적화합니다:

L = \frac{1}{k} \sum_{(u,v) \in O^+} \Big[ \sigma\Big(\sum_{i=1}^k e_u^* \cdot e_{v_i^n}^* \Big) - \sigma(k \cdot e_u^* \cdot e_v^*) + \gamma \Big]_+.

여기서:

$v_n^1, \cdots, v_n^k$ 는 샘플링된 $k$ 개의 네거티브 아이템을 나타냅니다.
$\sigma(\cdot)$ 는 시그모이드 함수(Sigmoid Function)입니다.
$[z]_+ = \max(0, z)$ 는 ReLU와 유사한 활성화 함수입니다.
$\gamma$ 는 사전 정의된 마진(margin)으로, $\gamma > 0$ 을 만족합니다.
$O^+$ 는 양성 사용자-아이템 쌍의 집합을 나타냅니다.
$S_n(u, v)$ 는 설계된 네거티브 샘플러입니다.

3. 세 영역 원칙 (The Three-Region Principle)

이 섹션에서는 먼저 네거티브 샘플링 문제를 소개하고 그래프 기반 추천에서의 네거티브 샘플링을 분석합니다. 이후 세 영역 원칙(Three-Region Principle)을 제안하여 네거티브 샘플링을 가이드하며, 영역 구분 기준을 제공합니다. 마지막으로, 제안된 세 영역 원칙에 대해 논의합니다.

3.1 네거티브 샘플링 문제

확장된 힌지 손실 함수 (식 5)에서 볼 수 있듯이, 네거티브 샘플링은 모델 학습에서 중요한 역할을 합니다. 이는 모델이 양성 및 네거티브 상호작용을 구별할 적절한 경계를 학습할 수 있도록 도와줍니다. 구체적으로, 네거티브 샘플러 $S_n$ 은 설계된 분포 $p_n$ 에서 네거티브 아이템을 샘플링하며, 양성에 가까운(즉, 어려운 네거티브 아이템) 네거티브는 추천 모델의 성능을 크게 향상시킬 수 있습니다.

여러 연구에서는 추천 시스템의 성능을 개선하기 위해 더 복잡한 네거티브 샘플링 분포 $p_n$ 을 설계하려는 시도가 이루어졌습니다 [16], [19], [22], [23], [24]. 하지만 초기 연구들은 실제 그래프 데이터에서 추정 분산을 줄이는 데 초점을 맞췄으며, 네거티브 샘플링 영역 선택은 충분히 탐구되지 않았습니다. 본 연구에서는 네거티브 샘플링을 위한 적절한 영역 선택을 탐구합니다.

3.2 네거티브 샘플링 분석

(1) 반복적인 GNN (Iterative GNNs)

반복적인 GNN은 사용자-아이템 그래프에서 정보를 레이어별로 전파하여 사용자와 아이템의 임베딩을 생성하는 아이디어입니다. 레이어 수는 성능에 큰 영향을 미치며, 이는 여러 연구 결과에서 확인되었습니다 [4], [15].

짧은 홉(Hop):
1~3홉의 이웃은 양성 선호도를 나타내며, 그래프 기반 추천의 성능을 향상시킵니다. 이는 사회적 영향 이론(Social Influence Theory) [25], [26]에 의해 설명될 수 있습니다. 이 이론에 따르면, 소셜 네트워크에서 사용자는 서로에게 영향을 미쳐 비슷한 선호도를 가지게 됩니다. 마찬가지로, 동일한 아이템과 상호작용한 사용자들은 동일한 커뮤니티에 속하며 동일한 선호도를 가질 가능성이 높습니다.
긴 홉(Hop):
반면, 4홉 이상의 이웃은 네거티브 선호도를 나타내며, 이는 추천 성능을 저하시킬 수 있습니다. 따라서, 네거티브 샘플링 영역은 반복적인 GNN의 전파 메커니즘에 따라 분리되어야 합니다.

(2) 분산 분석 (Variance)

최근 연구 [19]에서는 그래프 표현 학습의 네거티브 샘플링에 대한 기대 위험(Expected Risk)을 다음과 같이 이론적으로 증명했습니다:

E[\|\|(\theta_T - \theta^*)_u\|\|^2] = \frac{1}{T} \Bigg( \frac{1}{p_d(v|u)} - 1 + \frac{1}{k \cdot p_n(v|u)} - \frac{1}{k} \Bigg),

여기서:

$p_d(v|u)$ 와 $p_n(v|u)$ 는 각각 양성 및 네거티브 샘플링 분포를 나타냅니다.
$T$ 는 샘플링된 샘플 수를 나타냅니다.
$k$ 는 각 양성 사용자-아이템 쌍에 대해 샘플링된 네거티브 수입니다.

위 식은 네거티브 샘플링 분포 $p_n(v|u)$ 가 양성 분포 $p_d(v|u)$ 와 양의 상관 관계를 가지되, 부분적으로( $0 < \alpha < 1$ ) 비례해야 함을 시사합니다. 따라서 네거티브 샘플링 전략은 GNN의 전파 메커니즘과 기대 위험을 모두 충족해야 합니다.

3.3 네거티브 샘플링을 위한 세 영역 원칙 (The Three-Region Principle)

그래프 기반 추천 작업에서 GNN의 전파 메커니즘 특성을 고려하여, 우리는 사용자 $u$ 와 관련된 네거티브 샘플링을 위한 세 영역 원칙(Three-Region Principle)을 제안합니다. 이 원칙에 따라 아이템을 세 가지 영역으로 나눌 수 있습니다(그림 3 참조).

(1) 인접 영역 (Adjacent Region)

인접 영역의 아이템은 그래프 기반 추천에서 중심 사용자 $u$ 를 위해 특징 정보를 전파하는 데 주로 사용됩니다. 따라서 이 영역의 아이템은 사용자의 양성 선호도를 나타내며 네거티브로 샘플링되지 않아야 합니다. 또한, 식 (6)에 따르면 $p_n(v|u) > 0$ 을 유지해야 하며, 이는 최적 $(e_u \cdot e_v)$ 값을 보장합니다. 요약하면, 인접 영역의 아이템은 일반적으로 네거티브 샘플링에서 제외되며, 과도한 샘플링은 의미가 없습니다.

(2) 중간 영역 (Intermediate Region)

중간 영역의 아이템은 인접 아이템과 달리, 양성에 가까운 하드(hard) 네거티브 아이템으로 간주됩니다. 이 영역의 아이템은 모델 학습에 더 많은 정보를 제공할 수 있습니다. 중간 영역의 아이템은 중심 사용자 $u$ 에서 약간 떨어져 있으며, 이들을 인접 아이템으로 간주하고 정보 전파에 활용하면 성능이 저하되거나 약간만 향상될 수 있습니다. 또한, 중간 영역의 아이템을 중심 노드로 전파하면 노드 크기가 기하급수적으로 증가하여 메모리 소비가 커질 수 있습니다. 따라서 중간 영역의 아이템은 네거티브 샘플로 충분히 샘플링되어야 합니다.

(3) 먼 영역 (Distant Region)

먼 영역의 아이템은 $p_d(v|u)$ 값이 작고, 일반적으로 중심 사용자와의 관련성이 거의 없는 아이템입니다. 사용자는 일반적으로 이 영역의 아이템과 상호작용하지 않으므로 $p_d(v|u)$ 또는 $(e_u \cdot e_v)$ 값이 작습니다. 추천 시스템에서는 주로 $(e_u \cdot e_v)$ 값이 큰 상위 $K$ 개의 아이템에 관심을 갖기 때문에, 먼 영역의 아이템은 과도한 네거티브 샘플링이 무의미합니다. 결과적으로, 먼 영역의 아이템은 적게 샘플링되어야 합니다.

세 영역의 분리 기준 (Separating Criterion)

세 영역 원칙에 따라, 사용자 $u$ 와 하위 그래프(subgraph)를 기반으로 모든 아이템을 세 영역으로 나누기 위한 분리 기준을 제안합니다(그림 3 참조). 구체적으로, 사용자 $u$ 와 하위 그래프의 구조를 활용하여 계층적 너비 우선 탐색(Layer-wise Breadth-First Search, LBFS) 알고리즘을 통해 개별화된 아이템 집합을 생성합니다.

$k$ -홉 내에 위치한 아이템은 인접 아이템으로 간주됩니다.
$k$ -홉 외부에 위치한 아이템은 먼 아이템으로 간주됩니다.
$k$ -홉 내의 중간에 위치한 아이템은 중간 영역의 아이템으로 간주됩니다.

이러한 구조적 분리 기준은 사용자별로 개인화된 영역을 생성하며, 사용자-아이템 그래프의 구조를 반영하여 다양성과 개성을 나타냅니다. 중간 영역은 네거티브 샘플링에 결정적인 역할을 하기 때문에, 중간 아이템 생성에 초점을 맞추고 있습니다. 본 논문에서는 네거티브 샘플링이 글로벌 영역이 아닌 중간 영역에서 이루어져야 한다고 주장하며, 이 원칙은 이후 5.5 심화 연구 섹션에서 검증됩니다.

LBFS 알고리즘의 구체적인 과정은 아래 알고리즘 1에 설명되어 있으며, BFS를 사용하는 하위 알고리즘은 알고리즘 2에 나와 있습니다.

알고리즘 1: 계층적 너비 우선 탐색 (LBFS)

입력: 사용자-아이템 그래프 $G = (U + V, O^+)$ , $k$ -홉
출력: 중간 영역 $R_{\text{med}}$

모든 사용자 $u$ 에 대해:
- hop_num = 0, queue = [u]
$hop\_num \leq k$ -홉일 때까지 반복:
- $y = \text{BFS}(G, queue)$
- $queue = y$
- $hop\_num += 1$
- $hop\_num == k$ -홉일 경우:
  - $R_{\text{med}} = y$

알고리즘 2: 너비 우선 탐색 (BFS)

입력: 사용자-아이템 그래프 $G$ , $queue$
출력: 계층별 노드 집합 $y$

$queue$ 의 모든 노드에 대해:
- temp = queue.pop(0)
- nodes = G[temp]
- nodes를 $y$ 에 추가

3.4 세 영역 원칙에 대한 논의 (Discussion on The Three-Region Principle)

위에서 설명한 바와 같이, 세 영역 원칙은 네거티브 샘플링을 가이드하기 위한 일반적인 원칙으로 작용합니다. 글로벌하게 관찰되지 않은 아이템과 비교했을 때, 중간 영역의 아이템은 모델 학습에 더 유익한 후보 네거티브 아이템을 제공합니다. 세 영역 원칙은 비중간 아이템의 간섭을 제거하고, 중간 영역에서 정확하게 후보 네거티브 아이템을 샘플링할 수 있습니다. 요약하자면, 세 영역 원칙은 네거티브 샘플링을 위한 일반적인 원칙으로, 기존 네거티브 샘플링 전략에 글로벌 영역 대신 중간 영역을 대체하여 적용할 수 있습니다.

4. RecNS 방법 (The RecNS Method)

이 섹션에서는 제안된 네거티브 샘플링 방법인 RecNS를 설명합니다. RecNS는 기존 그래프 기반 추천 모델에 직접 통합할 수 있는 일반적인 네거티브 샘플링 방법입니다. RecNS는 네거티브 샘플링을 위해 두 가지 전략을 설계합니다: 양성 보조 샘플링(Positive-Assisted Sampling, RecNS-O)과 노출 보강 샘플링(Exposure-Augmented Sampling, RecNS-W). 이 두 샘플링 전략을 병합하여 최종 네거티브 아이템 임베딩을 생성합니다. RecNS의 학습 흐름은 알고리즘 3에 나와 있습니다.

4.1 양성 보조 샘플링 (Positive-Assisted Sampling, RecNS-O)

어려운 네거티브 아이템을 얻기 위해, 양성 아이템의 도움을 받아 네거티브 샘플링을 수행하는 양성 보조 샘플링 전략을 제안합니다. 구체적으로, 주어진 사용자 $u$ 와 해당 양성 아이템 $v$ 에 대해, 네거티브 샘플링 분포는 사용자 $u$ 뿐만 아니라 아이템 $v$ 에 의해서도 결정됩니다 [16], [19], [23]. 사용자 $u$ 의 관점에서 샘플링된 네거티브 아이템 $v_n$ 은 $u$ 의 네거티브 선호도를 반영합니다. 한편, 네거티브 아이템은 양성 및 네거티브 아이템을 구별할 충분한 분별력을 가져야 합니다 [24].

(1) 양성 보조 샘플링 분포

양성 아이템 정보를 네거티브 샘플링에 통합한다는 아이디어를 도입합니다. 먼저, 세 영역 원칙에 따라 생성된 중간 영역 $R_{\text{med}}$ 에서 $M$ 개의 후보 네거티브 아이템을 선택하여 후보 집합 $C_u$ 를 형성합니다. $M$ 은 그래프 데이터의 전체 아이템 수보다 훨씬 작습니다. 이후, 내적(inner product) 점수를 사용하여 양성 분포를 근사화하고, 추정된 네거티브 분포 $p_n$ 에서 후보 아이템 집합 $C_u$ 의 네거티브 아이템을 선택합니다.

네거티브 분포 $p_n$ 은 양성 분포 $p_d$ 와 비례 관계를 가지며, 이는 MCNS [19]에서 도출된 결과입니다. 양성 보조 샘플링 분포는 다음과 같이 계산됩니다:

p_n(v_n^p | (u, v)) = \frac{ \sigma(\alpha(e_u^* \cdot e_{v_n^p}^*) + (1-\alpha)(e_v^* \cdot e_{v_n^p}^*)) }{ \sum_{v_i \in C_u} \sigma(\alpha(e_u^* \cdot e_{v_i}^*) + (1-\alpha)(e_v^* \cdot e_{v_i}^*)) },

여기서:

$v_n^p$ : 샘플링된 네거티브 아이템
$\alpha$ : 사용자 $u$ 와 양성 아이템 $v$ 간의 영향을 균형 있게 조정하는 보조 계수
$\sigma(\cdot)$ : 시그모이드 함수
$C_u$ : 중간 영역 $R_{\text{med}}$ 에서 선택된 $M$ 개의 후보 네거티브 아이템 집합

$\alpha$ 는 하이퍼파라미터로 수동으로 튜닝할 수 있으며, 섹션 5.3 파라미터 분석에서 $\alpha$ 의 적합한 분포 선택을 논의합니다(예: 균일 분포 및 가우시안 분포).

요약하자면, 양성 보조 샘플링은 양성 정보를 네거티브 샘플링에 통합하여 결정적인 경계를 학습할 수 있도록 합니다. 확장된 힌지 손실(augmented hinge loss)을 사용하여 그래프 기반 추천 모델의 매개변수를 최적화하며, $k$ 개의 네거티브 아이템은 양성 보조 샘플링 분포 $p_n$ 에서 샘플링됩니다. 이 $k$ 개의 네거티브 아이템은 샘플링된 네거티브 집합 $P_k = \{v_n^p\}$ 을 형성합니다.

4.2 노출 보강 샘플링 (Exposure-Augmented Sampling, RecNS-W)

우리는 노출 정보를 활용하여 네거티브 아이템을 샘플링하는 노출 보강 샘플링(RecNS-W) 전략을 제안합니다. E-commerce 플랫폼은 사용자가 추천받은 아이템이 노출되었는지 여부에 대한 정보를 수집할 수 있습니다. 이러한 노출 정보는 사용자의 네거티브 선호도를 설명하는 풍부한 정보를 포함하고 있습니다.

(1) 노출 정보의 역할

노출되었으나 상호작용하지 않은 아이템(즉, 노출된 아이템)은 사용자의 글로벌 미관찰 아이템과 비교했을 때, 더 강한 네거티브 특성을 반영합니다. 또한, 노출 정보는 잘못된 네거티브 문제(false negative problem)를 완화하는 데 도움이 될 수 있습니다. 일부 연구는 노출된 아이템이 더 많은 네거티브 속성을 가지고 있기 때문에, 이들을 네거티브 샘플로 사용하는 것이 유리하다고 제안합니다. 하지만, 노출된 아이템 자체가 심각한 편향을 가질 가능성이 있기 때문에, 단순히 이들을 샘플링하는 것은 최적의 성능을 보장하지 못할 수 있습니다 [28].

(2) 노출 보강 샘플링의 구현

구체적으로, 사용자 $u$ 와 해당 노출된 아이템 집합 $E_u = \{v_e\}$ 에 대해 다음 과정을 수행합니다:

노출된 아이템 집합 $E_u$ 에서 균일 샘플링을 통해 $M$ 개의 노출된 아이템을 선택하여 후보 집합 $M_u$ 를 형성합니다.
자체 증폭 계수(self-amplified factor) $\beta$ 를 도입하여 노출 정보의 영향을 증폭합니다.
후보 집합 $M_u$ 의 아이템에 대해 사용자 $u$ 의 선호도를 내적(inner product) 점수를 통해 추정하고, 가장 높은 점수를 가진 노출 네거티브 아이템 $v_n^e$ 를 선택합니다. 이는 하드 네거티브 샘플링(hard negative sampling) 전략과 유사합니다 [16], [19].

노출 보강 샘플링은 다음과 같이 구현됩니다:

v_n^e = \underset{v_i \in M_u}{\text{argmax}} \ \sigma(\beta \cdot (e_u^* \cdot e_{v_i}^*)),

여기서:

$v_n^e$ : 샘플링된 노출 네거티브 아이템
$\beta$ : 자체 증폭 계수
$\sigma(\cdot)$ : 시그모이드 함수

(3) 자체 증폭 계수 $\beta$

$\beta$ 는 샘플링된 하드 네거티브 아이템을 활용하여 노출 아이템의 내적 점수를 수정하는 데 사용됩니다. $\beta$ 의 설계 목표는 노출된 아이템 중 후보 하드 네거티브 아이템에 속하는 아이템을 우선적으로 선택하도록 만드는 것입니다. 이로 인해 노출된 아이템 자체에서 발생할 수 있는 샘플링 편향 문제를 보정할 수 있습니다.

$\beta$ 는 다음과 같이 정의됩니다:

[ \beta = \begin{cases} 1, & \text{if } v_e \notin C_u, \\ \text{노출된 아이템의 수}, & \text{if } v_e \in C_u, \end{cases} ]

여기서 $C_u$ 는 중간 영역에서 선택된 후보 아이템 집합입니다. $\beta$ 의 크기는 $C_u$ 에 속한 노출 아이템의 수에 따라 결정됩니다.

4.3 RecNS: 병합 전략

RecNS에서 네거티브 아이템은 앞서 설명한 두 가지 샘플링 전략(양성 보조 샘플링 및 노출 보강 샘플링)을 기반으로 합니다. 이제 이 두 샘플링 전략을 결합하는 방법을 소개합니다.

본질적으로 그래프 기반 추천의 핵심 아이디어는 사용자-아이템 그래프에서 임베딩을 반복적으로 전파하는 것입니다. 따라서, 이 샘플링 전략들을 임베딩 공간에서 병합(merging in embedding space)합니다. 병합 연산은 다음과 같이 구현됩니다:

e_{v_n}^* = \text{merge}\Big(e_{v_n^e}^*, e_{v_n^p}^*\Big),

여기서:

$v_n^p$ : 양성 보조 샘플링에서 샘플링된 네거티브
$v_n^e$ : 노출 보강 샘플링에서 선택된 네거티브

병합 연산 $\text{merge}(\cdot)$ 는 추가적인 매개변수를 필요로 하지 않으며, GNN 기반 인코더에서 직접 얻은 임베딩을 병합합니다. 병합 연산은 다음과 같이 정의됩니다:

\text{merge}(e_{v_n^e}^*, e_{v_n^p}^*) = \frac{1}{k} \cdot e_{v_n^e}^* + \Big(1 - \frac{1}{k}\Big) \cdot e_{v_n^p}^*,

여기서 $k$ 는 네거티브 아이템의 수를 나타냅니다. 이는 매개변수를 추가하지 않는 비파라메트릭 병합 과정입니다.

4.4 RecNS에 대한 논의

(1) 범용성 (Universality)

RecNS는 그래프 기반 추천 모델에 플러그인 형태로 적용 가능한 범용적인 네거티브 샘플링 방법입니다. 양성 보조 샘플링은 네거티브 아이템의 품질을 향상시키며, 이는 다양한 그래프 기반 추천 모델에 널리 적용될 수 있습니다. 또한, 노출 보강 샘플링은 E-commerce 플랫폼에서 수집 가능한 노출 정보를 활용하여 네거티브 샘플링을 개선합니다.

(2) 임베딩 병합 (Embedding Mergence)

기존 네거티브 샘플링 방법은 사용자-아이템 그래프에서 단일 아이템을 샘플링하는 반면, RecNS는 양성 보조 샘플링과 노출 보강 샘플링 간 네거티브 임베딩을 병합합니다. 이러한 방법은 두 가지 후보 네거티브 아이템을 실제로 결합하여 네거티브 샘플의 품질을 향상시킵니다. 또한, 병합 연산은 다중 네거티브 샘플의 임베딩을 결합하여 복합 임베딩(compound embedding)으로 활용할 수 있는 새로운 방법을 제공합니다.

4.5 시간 복잡도 (Time Complexity)

RecNS의 계산 복잡도는 두 부분으로 나뉩니다.

양성 보조 샘플링(Positive-Assisted Sampling):
- $M$ 개의 후보 아이템을 $C_u$ 에서 샘플링하며, 계산 시간은 $O(Md)$ 입니다. 여기서 $M$ 은 샘플링된 후보 아이템의 수, $d$ 는 임베딩 차원을 나타냅니다.
노출 보강 샘플링(Exposure-Augmented Sampling):
- 이 전략의 계산 복잡도는 다음 두 부분으로 나뉩니다:
  1. 자체 증폭 계수 $\beta$ 계산: 시간 복잡도는 $O(M)$ 입니다.
  2. 노출된 네거티브 아이템 $v_n^e$ 샘플링: 이 과정의 계산 시간은 $O(Md)$ 입니다.

따라서, 노출 보강 샘플링의 총 계산 복잡도는 $O(M + Md)$ 입니다.

결론적으로, RecNS의 전체 시간 복잡도는 $O(Md)$ 로 표현할 수 있습니다.

4.6 세 영역 원칙과 RecNS

일반적으로 네거티브 샘플링은 두 가지 요소에 따라 달라집니다:
1. 그래프 구조(반복적인 GNN의 전파 메커니즘)
2. 분산 이론(Variance Theory)

세 영역 원칙(Three-Region Principle)은 네거티브 샘플링 영역을 선택하기 위한 일반적인 가이드라인으로 작용합니다. 반면, RecNS는 후보 네거티브 아이템 집합에서 효율적으로 네거티브 아이템을 샘플링하기 위한 범용적인 네거티브 샘플링 방법입니다. 세 영역 원칙은 정보성이 높은 후보 네거티브 아이템 집합을 제공하고, RecNS는 이 집합에서 네거티브 아이템을 샘플링할 수 있는 효율적인 샘플링 분포를 제공합니다.

5. 실험 (Experiments)

RecNS의 효과와 적응성을 입증하기 위해, 두 개의 데이터셋과 세 가지 대표적인 그래프 기반 추천 모델(PinSage, NGCF, LightGCN)을 대상으로 광범위한 실험을 수행했습니다. 이후 다양한 파라미터 분석을 수행했으며, 심층 연구를 통해 RecNS가 우수한 네거티브 샘플링 성능을 가지는 이유를 설명합니다.

5.1 실험 설정 (Experimental Settings)

(1) 데이터셋

RecNS는 다음 두 데이터셋에서 평가되었습니다:

Zhihu: 대형 QA 플랫폼으로, 사용자가 관심 있는 기사를 클릭하는 데이터를 포함합니다. 본 논문에서는 CCIR-2018 Challenge에서 제공된 공개 데이터셋을 사용했으며, 이 데이터셋은 기사 노출 정보와 사용자 클릭 정보를 포함합니다.
Alibaba: Taobao E-commerce 플랫폼에서 수집된 사용자 행동 데이터를 포함합니다. 이 데이터셋은 사용자의 역사적 상호작용(양성 상호작용 및 노출 정보 포함)을 샘플링한 하위 집합입니다.

아래 표는 데이터셋의 통계를 요약한 것입니다.

데이터셋	사용자 수	아이템 수	엣지 수	노출 수	밀도
Zhihu	16,015	44,175	3,284,734	3,796,551	0.00418
Alibaba	434,442	227,410	7,104,657	10,868,570	0.00006

(2) 평가 지표

RecNS는 세 가지 널리 사용되는 Top-K 평가 지표로 평가되었습니다:
1. Recall
2. NDCG (Normalized Discounted Cumulative Gain)
3. HR (Hit Rate)

$K$ 는 20으로 설정되었습니다. 모든 테스트 사용자에 대해 평균 지표를 보고하며, 사용자가 상호작용하지 않은 모든 아이템을 대상으로 지표를 계산합니다. 또한, 효율적인 유사성 검색을 위해 Faiss 라이브러리(빠른 내적 계산을 지원)를 사용했습니다.

(3) 그래프 신경망 기반 인코더

RecNS의 적응성을 확인하기 위해, 세 가지 일반적인 그래프 기반 추천 모델을 실험에 사용했습니다.

PinSage [1]:
- 웹 스케일 그래프에서 아이템 임베딩을 학습하기 위해 GraphSAGE의 핵심 아이디어를 활용합니다.
- 실험에서 두 개의 집계 계층을 쌓아 사용자 또는 아이템의 정보 전파 경로( $u \gets v \gets u$ , $v \gets u \gets v$ )를 형성했으며, 평균 집계(mean-aggregator)를 사용했습니다.
NGCF [15]:
- 사용자가 연결된 아이템에 대한 정보를 전파함으로써 사용자와 아이템 간의 상호작용을 더욱 명확히 학습하는 새로운 프레임워크를 제안합니다. NGCF는 고차 연결성을 활용하여 협업 신호를 명시적으로 삽입합니다.
LightGCN [4]:
- 그래프 합성 네트워크(GCN)를 단순화하여 더 간결하고 추천에 적합하도록 설계되었습니다. LightGCN은 사용자와 아이템 임베딩을 선형적으로 전파하며, 모든 레이어에서 학습된 임베딩의 가중 합을 최종 임베딩으로 사용합니다.

5.2 성능 비교 (Performance Comparison)

(1) 최신 네거티브 샘플링 전략과의 비교

모든 네거티브 샘플링 전략에 대한 성능 비교 결과는 아래 표 2에 요약되어 있습니다. 표에서는 가장 우수한 기준선(밑줄)과 RecNS(굵게 표시된 값)의 결과를 강조했습니다. 전반적으로, RecNS는 모든 데이터셋과 평가 지표에서 뚜렷한 성능 향상을 가져왔습니다. RecNS의 적응성을 입증하기 위해, PinSage, NGCF, LightGCN이라는 세 가지 대표적인 그래프 기반 추천 모델에 RecNS를 적용했습니다. 표 2의 결과를 통해 다음과 같은 관찰이 가능합니다:

RecNS의 우수성
RecNS는 세 가지 GNN 기반 모델(PinSage, NGCF, LightGCN)에서 모든 기준선 대비 일관되게 우수한 성능을 보였습니다. 구체적으로, RecNS는 Zhihu와 Alibaba 데이터셋에서 각각 8.28%, 10.47%의 Recall@20 성능 향상을 PinSage 인코더에서 달성했습니다. 이러한 향상은 다음 요인들에 기인합니다:
- 세 영역 원칙(Three-Region Principle): RecNS는 글로벌하게 관찰되지 않은 아이템 집합 대신 중간 영역에서 더 많은 정보를 제공하는 네거티브 아이템을 탐색합니다.
- 양성 보조 샘플링(Positive-Assisted Sampling): 사용자와 양성 아이템 간의 영향을 균형 있게 반영하여 네거티브 샘플링 분포를 설계함으로써, 양성과 네거티브를 더 명확히 구분할 수 있는 아이템을 샘플링합니다.
- 노출 보강 샘플링(Exposure-Augmented Sampling): 노출된 아이템 정보를 활용하여 샘플링 편향을 줄이고, 네거티브 아이템 품질을 개선합니다.
기준선 전략의 성능
- UniNS와 PopNS는 정적(static)이며 글로벌한 네거티브 샘플링 전략으로, 두 데이터셋에서 모두 낮은 성능을 보였습니다. 이는 이러한 전략이 일반적으로 최적의 결과를 보장하지 못함을 나타냅니다.
- AdvNS는 UniNS 및 PopNS보다 우수한 성능을 보였습니다. 이는 샘플러가 사용자의 선호 분포를 학습하고, 모델 훈련을 혼란스럽게 만드는 어려운 아이템(hard item)을 생성하기 때문입니다.
- DNS와 SimNS는 휴리스틱(heuristic) 네거티브 샘플링 전략으로, 현재 모델의 예측 점수를 기반으로 네거티브 아이템을 동적으로 샘플링하여 성능을 향상시켰습니다.
SRNS의 중요성
SRNS는 세 가지 GNN 기반 모델에서 다른 기준선 전략보다 우수한 성능을 보였습니다. 이는 잘못된 네거티브 문제(false negative problem)가 중요한 요소임을 보여줍니다. SRNS는 높은 분산(variance)을 가진 아이템을 네거티브로 샘플링하여 참된 네거티브(true negative)를 효율적으로 샘플링합니다. 그러나 RecNS는 SRNS를 능가하는 성능을 보여줬으며, 이는 RecNS가 노출 정보를 활용하여 잘못된 네거티브 문제를 완화하고, 세 영역 원칙을 적용하여 더 유익한 후보 네거티브를 제공했기 때문입니다.

(2) 노출 정보 기반 샘플링 전략과의 비교

노출 정보와 통합된 세 가지 네거티브 샘플링 방법(ExpNS, MixedNS, RNS-AS)과 RecNS를 비교한 결과는 표 3에 요약되어 있습니다. 결과를 통해 다음과 같은 관찰이 가능합니다:

ExpNS의 한계
ExpNS는 노출된 아이템만을 네거티브로 샘플링하는 전략으로, 가장 낮은 추천 성능을 보였습니다. 이는 노출된 아이템의 출처를 명확히 알 수 없으며, 사용자가 단순히 무시했거나 실제로 싫어하는 아이템일 가능성이 있기 때문입니다.
MixedNS와 RNS-AS의 개선
MixedNS는 노출 아이템과 글로벌 미관찰 아이템 간의 샘플링 가중치 $\omega$ 를 조정하며, RNS-AS는 노출 데이터와 적대적 학습(adversarial learning)을 결합하여 더 나은 성능을 보였습니다.
RecNS의 우수성
RecNS는 노출 보강 샘플링 전략을 통해 노출 정보를 네거티브 샘플링에 통합합니다. 자체 증폭 계수(self-amplified factor)를 도입하여 노출 아이템의 영향을 증폭시키고, 가장 높은 내적 점수를 가진 노출 네거티브 아이템을 샘플링합니다. 또한, RecNS는 양성 보조 샘플링과 노출 보강 샘플링을 임베딩 공간에서 병합하여 네거티브 아이템 품질을 더욱 향상시킵니다.

모델	Zhihu (Recall@20)	Alibaba (Recall@20)
PinSage+ExpNS	0.30	0.35
PinSage+MixedNS	2.09	2.79
PinSage+RNS-AS	2.98	3.52
PinSage+RecNS	3.53	4.01

5.3 파라미터 분석 (Parameter Analysis)

(1) $k$ -홉 (khop) 설정의 영향

세 영역 원칙에서 영역을 구분하는 기준인 $k$ -홉의 선택이 RecNS 성능에 미치는 영향을 분석하기 위해 실험을 수행했습니다. $k$ -홉 값을 $\{3, 5, 7\}$ 로 설정하여 다양한 중간 영역을 생성하고, Zhihu 및 Alibaba 데이터셋에서 실험을 진행했습니다. 실험 결과는 아래 표 4에 요약되어 있습니다.

모델	Zhihu ( $k$ -홉)	Alibaba ( $k$ -홉)
PinSage	3.53 ( $k=3$ )	4.01 ( $k=5$ )
NGCF	4.42 ( $k=3$ )	4.58 ( $k=5$ )
LightGCN	4.91 ( $k=3$ )	6.86 ( $k=5$ )

결론:
1. Zhihu 데이터셋에서는 $k=3$ 에서 최상의 성능을 보였으며, Alibaba 데이터셋에서는 $k=5$ 에서 최상의 성능을 보였습니다. 이는 데이터셋의 밀도 차이에 기인한 결과로 보입니다. 밀도가 높은 데이터셋에서는 짧은 전파 경로가 효과적이며, 밀도가 낮은 데이터셋에서는 더 긴 전파 경로가 성능 향상에 기여합니다.
2. $k$ -홉 값의 선택은 데이터셋 밀도에 따라 조정해야 하며, 일반적으로 밀도가 높은 데이터셋에는 $k=3$ , 밀도가 낮은 데이터셋에는 $k=5$ 를 권장합니다.

(2) 전파 레이어 수 (Number of Propagation Layers)

전파 레이어 수 $L$ 이 RecNS의 성능에 미치는 영향을 분석하기 위해 $L \in \{1, 2, 3, 4\}$ 로 설정하여 NGCF와 LightGCN 모델에서 실험을 수행했습니다. 실험 결과는 아래 표 5에 요약되어 있습니다.

모델	Zhihu (Recall@20)	Alibaba (Recall@20)
NGCF ( $L=1$ )	4.26	3.97
NGCF ( $L=3$ )	4.42	4.58
LightGCN ( $L=1$ )	4.56	4.41
LightGCN ( $L=3$ )	4.91	6.86

결론:
1. 레이어 수가 1에서 3으로 증가하면 성능이 개선되며, 대부분의 경우 $L=3$ 에서 최고 성능을 보입니다.
2. $L=4$ 에서는 성능이 다시 감소하며, 이는 GNN에서 과도한 전파로 인한 과도 매끄러움 문제(over-smoothing)로 설명할 수 있습니다. 이는 높은 차수의 이웃 정보가 노드의 임베딩을 과도하게 평탄화시켜 성능을 저하시키는 현상입니다.

(3) 네거티브 아이템 수 (Number of Negative Items)

확장된 힌지 손실(augmented hinge loss)을 통해 네거티브 아이템 수 $k$ 가 RecNS 성능에 미치는 영향을 분석했습니다. $k \in \{5, 10, 15, 20\}$ 로 설정하여 PinSage+RecNS 모델에서 실험을 수행했으며, 결과는 아래 그림 4에 요약되어 있습니다.

결론:
1. 초기에는 $k$ 를 증가시킴에 따라 성능이 개선되며, $k=15$ 에서 최적의 성능에 도달했습니다.
2. $k > 15$ 일 때는 성능이 약간 감소했으며, 이는 추가 샘플링이 모델의 학습 목적에 불필요한 편향을 추가했기 때문입니다.
3. $k=15$ 는 추천 성능과 훈련 시간을 균형 있게 유지할 수 있는 최적의 값으로 확인되었습니다.

(4) 보조 계수 $\alpha$ 의 영향

양성 보조 샘플링에서 사용자와 양성 아이템 간의 영향을 조정하는 보조 계수 $\alpha$ 의 분포에 따른 성능을 분석했습니다. $\alpha$ 를 가우시안 분포( $N(0, 1)$ , $N(0, 0.5)$ )와 균일 분포( $U(0, 1)$ , $U(0, 0.5)$ )로 설정하고, PinSage+RecNS 모델에서 실험을 수행했습니다.

결론:

균일 분포 $U(0, 1)$ 를 따르는 $\alpha$ 가 가장 우수한 성능을 보였습니다.
가우시안 분포 $N(0, 0.5)$ 도 Alibaba 데이터셋에서 유사한 성능을 보였으나, $N(0, 1)$ 은 다소 낮은 성능을 보였습니다.

(5) 주요 하이퍼파라미터의 영향

RecNS의 성능에 중요한 세 가지 하이퍼파라미터(마진 $\gamma$ , 임베딩 차원 $d$ , 후보 아이템 수 $M$ )의 영향을 분석했습니다. Zhihu 데이터셋에서 실험 결과는 아래 그림 6에 요약되어 있습니다.

결론:
1. 마진 $\gamma$ : $\gamma > 0$ 일 때 성능이 향상되며, $\gamma = 0.1$ 에서 최적의 성능을 달성했습니다.
2. 임베딩 차원 $d$ : $d=256$ 이 성능과 시간 효율성 간의 균형을 유지하는 최적값으로 확인되었습니다.
3. 후보 아이템 수 $M$ : $M=20$ 이 추천 성능과 계산 비용을 균형 있게 유지하는 최적값으로 확인되었습니다.

5.4 심층 연구 (Deeper Study)

(1) 세 영역 원칙이 네거티브 샘플링을 향상시키는가?

RecNS는 세 영역 원칙(Three-Region Principle)에 기반합니다. 그러나 이 원칙이 실제로 네거티브 샘플링에 도움이 되는지 확인하기 위해 확장된 실험을 설계했습니다. 이 실험에서는 세 가지 다른 영역(중간 영역, 먼 영역, 글로벌 미관찰 영역)에서 각각 $M$ 개의 후보 네거티브 아이템을 샘플링하는 세 가지 변형된 RecNS 전략(RecNS-Med, RecNS-Dis, RecNS-All)을 설계했습니다. 결과는 아래 그림 7에 요약되어 있습니다.

결론:
1. 먼 영역에서만 샘플링하는 경우(RecNS-Dis), 추천 성능이 급격히 저하되었습니다. 이는 먼 영역의 아이템이 추천 성능에 유의미한 기여를 하지 못함을 나타냅니다.
2. 글로벌 미관찰 영역에서 샘플링하는 경우(RecNS-All), 중간 영역과 먼 영역을 명확히 구분하지 못해 성능이 저하되었습니다.
3. 중간 영역에서 샘플링하는 경우(RecNS-Med), 가장 우수한 성능을 보였습니다. 이는 세 영역 원칙이 정보성이 높은 네거티브 후보를 제공한다는 것을 입증합니다.

(2) 양성 보조 샘플링이 네거티브 샘플링을 강화하는가?

양성 보조 샘플링이 네거티브 샘플링에 미치는 영향을 평가하기 위해 실험을 설계했습니다. 특정 사용자 $u$ 에 대해, 현재 모델에서 가장 높은 내적 점수를 가진 가장 어려운 네거티브(hardest negative)를 샘플링했습니다. 이 실험에서는 양성 보조 샘플링을 비활성화한 RecNS 변형(RecNSw/o p-a)을 사용했습니다. 결과는 Zhihu 및 Alibaba 데이터셋에서 아래 그림 8에 요약되어 있습니다.

결론:
1. 가장 어려운 네거티브 아이템을 샘플링하면 추천 성능이 저하되었습니다. 이는 잘못된 네거티브(false negative) 문제가 발생했기 때문입니다.
2. 이전 연구 [1], [36]에서도 가장 어려운 네거티브 대신 큰 점수와 높은 분산(variance)을 가진 아이템을 샘플링하는 것이 추천 성능을 향상시키는 데 유리하다고 제안했습니다.
3. RecNS는 양성 보조 샘플링을 통해 양성과 네거티브 간의 경계를 보다 명확히 구분하며, 잘못된 네거티브 문제를 완화합니다.

(3) 노출 보강 샘플링이 네거티브 샘플링을 강화하는가?

노출 보강 샘플링의 효과를 검증하기 위해 두 가지 실험을 수행했습니다. 결과는 아래 그림 9에 요약되어 있습니다.

노출 보강 샘플링 비활성화(RecNSw/o e-a):
노출 보강 샘플링을 비활성화한 경우, 추천 성능이 감소했습니다. 이는 노출 정보를 활용함으로써 샘플링 편향을 줄이고, 참된 네거티브(true negative)를 샘플링할 수 있음을 보여줍니다.
노출된 네거티브 아이템 수의 영향:
Zhihu 데이터셋에서 PinSage 인코더를 사용하여, 샘플링된 노출 네거티브 아이템의 수를 $\{1, 5, 10, 15, 20\}$ 로 설정해 실험을 수행했습니다. 결과는 노출된 네거티브 아이템의 수를 증가시켜도 성능이 개선되지 않음을 보여줍니다. 이는 노출된 아이템이 편향된 정보를 포함하고 있기 때문입니다. 따라서 RecNS는 자체 증폭 계수(self-amplified factor)를 통해 가장 정보성이 높은 노출 네거티브 아이템을 선택하도록 설계되었습니다.

6.1 그래프 기반 추천 시스템

그래프 기반 추천 시스템은 전자상거래 및 소셜 미디어와 같은 다양한 애플리케이션에서 핵심 기술로 주목받고 있습니다. 기존의 협업 필터링(collaborative filtering) 및 행렬 분해(matrix factorization) 방법은 웹 스케일 애플리케이션에는 적합하지 않았습니다. 하지만 딥러닝 기술의 발전으로 그래프 기반 모델이 추천 시스템에 활용되고 있습니다.

PinSage [1]: 웹 스케일 그래프에서 아이템 임베딩을 학습하기 위해 그래프 합성 네트워크(GCN)를 사용합니다.
LightGCN [4]: GCN을 단순화하여 사용자-아이템 상호작용 그래프에서 효율적으로 임베딩을 학습합니다.
NGCF [15]: 고차 연결성을 활용하여 사용자-아이템 관계를 명시적으로 학습하는 새로운 프레임워크입니다.

6.2 추천에서의 네거티브 샘플링

네거티브 샘플링은 추천 시스템에서 단일 클래스 문제를 해결하고 학습 속도를 가속화하기 위한 핵심 기술입니다. 기존의 네거티브 샘플링 방법은 다음과 같이 네 가지 범주로 나눌 수 있습니다:

정적 샘플러(Static Sampler):
- 균일 분포를 사용하는 Uniform Negative Sampling(UniNS) [9].
- 아이템의 인기도를 기반으로 샘플링하는 PopNS [29], [30].
어려운 네거티브 샘플러(Hard Negative Sampler):
- 현재 모델의 점수를 기반으로 하드 네거티브 아이템을 샘플링하는 DNS [16] 및 SimNS [24].
GAN 기반 샘플러(GAN-based Sampler):
- 적대적 학습(adversarial learning)을 활용하여 네거티브 아이템을 생성하는 IRGAN [17].
보조 정보 기반 샘플러(Auxiliary-based Sampler):
- 그래프 구조, 노출 정보 등 보조 정보를 활용하여 네거티브 아이템을 샘플링하는 MCNS [19] 및 RNS-AS [32].

7. 결론 (Conclusion)

본 연구에서는 그래프 기반 추천에서의 네거티브 샘플링 문제를 다루며, 세 영역 원칙(Three-Region Principle)을 제안했습니다. 이 원칙은 중간 영역에서 더 많은 아이템을 네거티브로 샘플링하도록 가이드합니다. 또한, 우리는 RecNS라는 효과적인 네거티브 샘플링 방법을 제시했으며, 양성 보조 샘플링과 노출 보강 샘플링을 병합하여 최종 네거티브 임베딩을 생성합니다.

RecNS는 세 가지 대표적인 그래프 기반 추천 모델(PinSage, NGCF, LightGCN)에서 기존 네거티브 샘플링 전략을 대체하여 성능을 크게 향상시켰습니다. 추가적으로, RecNS는 광범위한 실험에서 다른 기존 방법들과 비교하여 우수한 성능을 보였습니다.

Meosun

데이터와 AI를 잘 활용하는 Backend Developer가 되자

다음 포스트

[논문 번역] Region or Global? A Principle for Negative Sampling in Graph-based Recommendation `with GPT`

논문 번역

지역 또는 글로벌? 그래프 기반 추천에서의 네거티브 샘플링 원칙

저자

초록

1. 서론

우리의 접근법

기여

2. 프레임워크

2.1 SampledRec 프레임워크

2.2 GNN 기반 인코더

(1) 집계 모듈 (Aggregation Module)

(2) 전파 모듈 (Propagation Module)

(3) 예측 모듈 (Prediction Module)

2.3 샘플러 (Samplers)

(1) 이웃 샘플러 (SSS)

(2) 양성 샘플러 (SpS_pSp​)

(3) 네거티브 샘플러 (SnS_nSn​)

2.4 최적화 (Optimization)

3. 세 영역 원칙 (The Three-Region Principle)

3.1 네거티브 샘플링 문제

3.2 네거티브 샘플링 분석

(1) 반복적인 GNN (Iterative GNNs)

(2) 분산 분석 (Variance)

3.3 네거티브 샘플링을 위한 세 영역 원칙 (The Three-Region Principle)

(1) 인접 영역 (Adjacent Region)

(2) 중간 영역 (Intermediate Region)

(3) 먼 영역 (Distant Region)

세 영역의 분리 기준 (Separating Criterion)

알고리즘 1: 계층적 너비 우선 탐색 (LBFS)

알고리즘 2: 너비 우선 탐색 (BFS)

3.4 세 영역 원칙에 대한 논의 (Discussion on The Three-Region Principle)

4. RecNS 방법 (The RecNS Method)

4.1 양성 보조 샘플링 (Positive-Assisted Sampling, RecNS-O)

(1) 양성 보조 샘플링 분포

4.2 노출 보강 샘플링 (Exposure-Augmented Sampling, RecNS-W)

(1) 노출 정보의 역할

(2) 노출 보강 샘플링의 구현

(3) 자체 증폭 계수 β\betaβ

4.3 RecNS: 병합 전략

4.4 RecNS에 대한 논의

(1) 범용성 (Universality)

(2) 임베딩 병합 (Embedding Mergence)

4.5 시간 복잡도 (Time Complexity)

4.6 세 영역 원칙과 RecNS

5. 실험 (Experiments)

5.1 실험 설정 (Experimental Settings)

(1) 데이터셋

(2) 평가 지표

(3) 그래프 신경망 기반 인코더

5.2 성능 비교 (Performance Comparison)

(1) 최신 네거티브 샘플링 전략과의 비교

(2) 노출 정보 기반 샘플링 전략과의 비교

5.3 파라미터 분석 (Parameter Analysis)

(1) kkk-홉 (khop) 설정의 영향

(2) 전파 레이어 수 (Number of Propagation Layers)

(3) 네거티브 아이템 수 (Number of Negative Items)

(4) 보조 계수 α\alphaα의 영향

(5) 주요 하이퍼파라미터의 영향

5.4 심층 연구 (Deeper Study)

(1) 세 영역 원칙이 네거티브 샘플링을 향상시키는가?

(2) 양성 보조 샘플링이 네거티브 샘플링을 강화하는가?

(3) 노출 보강 샘플링이 네거티브 샘플링을 강화하는가?

6. 관련 연구 (Related Work)

6.1 그래프 기반 추천 시스템

6.2 추천에서의 네거티브 샘플링

7. 결론 (Conclusion)

[논문 번역] Cold-Start Recommendation based on Knowledge Graph and Meta-Learning under Positive and Negative Sampling `with GPT`

0개의 댓글

(1) 이웃 샘플러 ( $S$ )

(2) 양성 샘플러 ( $S_p$ )

(3) 네거티브 샘플러 ( $S_n$ )

(3) 자체 증폭 계수 $\beta$

(1) $k$ -홉 (khop) 설정의 영향

(4) 보조 계수 $\alpha$ 의 영향