이 글은 Jiyoon Blog의 원문을 읽고 핵심 개념과 설계 쟁점을 재구성한 정리다. 원문을 복제하지 않고, 관련 연구 자료와 함께 사실·해석·미확인 범위를 구분한다.

결론

그래프 추천에서 중요한 것은 모델 이름보다 어떤 관계를 따라, 얼마나 멀리, 어떤 확률로 걸을지를 정하는 일이다. 사용자의 조회·완료·북마크·재방문 같은 활동 강도를 사용자-콘텐츠 그래프의 엣지 가중치로 반영하면, 단순한 활동 여부보다 개인의 관심 강도를 random walk에 포함할 수 있다.[1]

다만 활동량을 그대로 가중치로 쓰면 헤비 유저·인기 콘텐츠·노출 편향이 그래프를 지배할 수 있다. 따라서 log1p 포화, 사용자별 정규화, 시간 감쇠, 인기 패널티, 노출 로그, 재랭킹을 함께 설계해야 한다.

1. 왜 Random Walk 기반 추천인가

그래프 기반 추천은 학습 모델을 추가하기 전에 사용할 수 있는 강한 기준선이다. 재현성 분석 연구는 여러 신경망 추천 논문을 재현한 뒤, 일부 사례에서 잘 조정된 ItemKNN·그래프 기반 휴리스틱이 신경망 방법과 경쟁하거나 앞섰다고 보고했다.[2]

Random Walk 계열의 장점은 다음과 같다.

  • 그래프만 있으면 동작해 초기 서비스에 적용하기 쉬움
  • 경로와 확률로 추천 근거를 설명할 수 있음
  • 희소 행렬 연산으로 배치 계산 가능
  • 임베딩·GNN을 도입하기 전 기준선으로 사용 가능
  • 최근 활동과 연결해 개인화 범위를 조정 가능

이는 신경망 추천이 불필요하다는 뜻은 아니다. 모델 복잡도를 높이기 전에 단순 기준선과 비교해 실제 개선을 확인해야 한다는 의미다.[2][5]

2. PageRank: 전체 그래프의 중요도

PageRank는 링크 구조에서 중요한 노드를 계산하기 위해 제안된 알고리즘이다. Random Surfer가 링크를 따라 이동하다가 일정 확률로 임의의 페이지로 이동한다고 볼 때, 장기간 머무는 비율이 PageRank 점수가 된다.[4]

PR(v) = (1 - d) / N + d × Σ PR(u) / out(u)
  • d: 링크를 따라갈 확률, damping factor
  • 1-d: 임의 노드로 이동하는 teleport 확률
  • out(u): u에서 나가는 링크 또는 가중치 합

추천에 전체 PageRank를 그대로 적용하면 모든 사용자에게 비슷한 인기 콘텐츠가 노출된다. 따라서 전체 인기 목록·콜드스타트 기본값에는 유용하지만, 개인화 추천에는 출발점 분포가 필요하다.

3. Personalized PageRank: 사용자에서 출발하기

Personalized PageRank(PPR)는 teleport 분포를 전체 노드가 아니라 사용자가 최근 활동한 콘텐츠 또는 관심 노드 집합에 둔다. 그래서 Random Walk with Restart라고도 부른다.[1]

PPR_s(v) = (1 - d) × s(v) + d × Σ PPR_s(u) × P(u → v)

d가 작으면 출발점 주변을 짧게 탐색하고, d가 크면 더 먼 노드까지 탐색한다. 탐색 범위를 넓히면 다양성이 생길 수 있지만, 다중 홉에서 잡음과 인기 편향이 커질 수 있다.

4. 사용자-콘텐츠 그래프의 P3와 RP3β

사용자와 콘텐츠가 노드이고 활동이 엣지인 이분 그래프에서는 다음 세 걸음이 자연스럽다.

나
 → 내가 활동한 콘텐츠
 → 그 콘텐츠를 활동한 다른 사용자
 → 그 사용자가 활동한 새 콘텐츠

이 세 걸음의 도착 확률을 추천 점수로 사용하는 방식이 P3 계열이다. 연구 문헌에서는 P3α를 사용자-아이템 그래프의 세 단계 random walk 기반 모델로 설명하며, 엣지 정규화 값에 α를 적용해 강한 관계와 약한 관계의 차이를 조절한다.[2][5]

RP3β는 여기에 도착 아이템의 인기도 패널티를 추가한다. 대략 다음과 같은 구조다.

RP3β score(i, j)
 = P3α score(i, j) / popularity(j)^β
  • β = 0: P3α와 동일한 방향
  • β 증가: 인기 아이템 감점 증가
  • 실무 판단: Recall·NDCG뿐 아니라 커버리지·롱테일 비율과 함께 조정

P3α와 RP3β는 학습 없이도 계산 가능한 그래프 기준선이며, 단순하다는 이유로 약한 기준선이라고 가정하면 안 된다.[2][5]

5. 활동 강도를 엣지 가중치로 만들기

“활동했다/안 했다”를 0과 1로만 표현하지 않고 활동 강도를 가중치로 넣으면 이동 확률이 달라진다. 콘텐츠를 깊게 본 사용자는 해당 콘텐츠로 이동할 확률이 커지고, 그 콘텐츠를 깊게 본 다른 사용자로 이동할 확률도 커진다.[1]

신호 설계

신호 의미 주의점
조회 관심 가능성 제목·썸네일에 끌린 것일 수 있음
체류 시간 실제 소비 가능성 콘텐츠 길이로 정규화 필요
완료 끝까지 소비 짧은 콘텐츠에 유리
재방문 반복 관심 가능성 이해 부족으로 반복했을 가능성
북마크·공유 명시적 가치 표시 발생 빈도가 낮고 희소함

처음에는 정책 가중치의 합으로 시작할 수 있다.

raw(u,i) = Σ signal_weight(e) × time_decay(e)
w(u,i) = log(1 + raw(u,i))

여기서 log1p는 활동이 늘수록 가중치가 계속 커지는 것을 완화한다. 부정 신호는 음수 엣지로 만들기보다 가중치에서 제외하거나 재랭킹 필터로 분리하는 편이 안전하다.[1]

사용자별 정규화

활동량이 많은 사용자는 다양한 콘텐츠에 큰 엣지를 만들 수 있다. 이 사용자를 통과하는 경로가 과도하게 많아지면 특정 헤비 유저의 취향이 전체 추천에 스며든다.

따라서 다음 중 하나를 고려한다.

  • 사용자별 활동량 합으로 정규화
  • 사용자 내부 순위 또는 percentile 사용
  • 사용자별 최대값 clipping
  • 신규·저활동 사용자와 헤비 유저의 평가 분리

시간 감쇠

최근 활동과 오래된 활동을 같은 무게로 볼지 결정해야 한다.

w(u,i) = log(1 + Σ signal_weight(e) × 0.5^(age(e)/half_life))

반감기가 짧으면 최근 취향을 반영하고, 길면 누적 관심을 유지한다. 이 값은 도메인 정책이므로 검증 데이터에서 선택해야 한다.

6. 노출 편향과 되먹임 고리

노출되지 않은 콘텐츠는 활동할 기회 자체가 없다. 인기 콘텐츠가 많이 노출되고, 활동이 쌓이고, 더 많이 추천되는 되먹임 고리가 생긴다.[1]

완화 방법은 다음과 같다.

  • 노출 로그와 활동 로그를 함께 저장
  • 노출 대비 활동률로 가중치 보정
  • RP3β의 인기 패널티 조정
  • 저노출·신규 콘텐츠 슬롯을 재랭킹에서 보장
  • 탐색·활용 비율을 별도 정책으로 관리

클릭하지 않았다는 사실을 즉시 부정 선호로 해석하지 않는 것도 중요하다. 보이지 않았거나 노출 위치가 낮았을 수 있기 때문이다.

7. 그래프 구조 선택

그래프 엣지 의미 장점 주의점
사용자-콘텐츠 사용자의 콘텐츠 활동 강도 개인화가 직접적 사용자 수에 따라 그래프 증가
콘텐츠-콘텐츠 함께 소비된 콘텐츠 관계 미리 계산하고 빠르게 서빙 개인 맥락 희석
이종 그래프 활동·카테고리·개념 관계 혼합 신규 콘텐츠에 도달 경로 제공 엣지 종류별 가중치 균형 필요

활동 엣지만으로는 아무도 활동하지 않은 신규 콘텐츠에 도달하기 어렵다. 콘텐츠-개념·카테고리·작성자 엣지를 함께 둔 이종 그래프는 이 문제를 완화할 수 있지만, 각 관계의 의미와 가중치를 별도로 정의해야 한다.[1]

8. 오프라인 계산과 요청 시 Random Walk

오프라인 희소 행렬 계산

P3·RP3β를 희소 행렬 곱으로 계산하면 배치 갱신에 적합하다.

P_ui = normalize(W).power(alpha)
P_iu = normalize(W.T).power(alpha)
S    = P_iu × P_ui
S    = S / popularity^beta
  • 장점: 계산 결과가 안정적이고 추천 시 빠름
  • 단점: 마지막 활동이 갱신 주기만큼 늦게 반영됨
  • 최적화: 콘텐츠별 top-K 이웃만 보존해 메모리 절약

요청 시 Random Walk 시뮬레이션

최근 활동을 즉시 반영하려면 사용자 출발점에서 짧은 random walk를 요청 시 실행할 수 있다. Pinterest Pixie는 대규모 그래프에서 사용자별 query를 받아 실시간 그래프 추천을 수행한 사례로 소개된다.[3]

  • 장점: 최근 활동 반영이 빠름
  • 단점: 메모리·지연시간·동시성·캐시 설계 필요
  • 운영 지표: p50/p95/p99 지연, 요청당 walk 수, early stop 비율, graph cache hit

Pixie 논문은 수십억 노드·엣지 규모 그래프에서 실시간 추천 시스템을 설명하지만, 그 수치와 구조를 모든 서비스에 그대로 적용할 수 있다는 뜻은 아니다.[3]

9. 평가 설계

활동 강도를 넣은 효과를 확인하려면 기준선을 분리해야 한다.

  1. 인기순 추천
  2. 이진 엣지 P3α/RP3β
  3. 활동 강도 엣지 P3α/RP3β
  4. ItemKNN 등 고전 기준선
  5. 필요할 때 임베딩·GNN 모델

평가 지표는 다음과 같이 구성한다.

  • Recall@K
  • NDCG@K
  • 사용자 활동량 구간별 성능
  • 카탈로그 커버리지
  • 롱테일 노출 비율
  • 시간순 분할 성능
  • 추천 후 깊은 활동률
  • p95/p99 서빙 지연

무작위 분할보다 과거 활동으로 학습·계산하고 미래 활동으로 평가하는 시간순 검증이 적절하다. 추천 목적이 “클릭”이 아니라 “깊은 활동”이라면 최종 지표도 완료·재방문·북마크 등 해당 목적과 맞춰야 한다.[1][2]

10. 운영 설계 체크리스트

수집
  → 신호 정의·정규화
  → 시간 감쇠
  → sparse graph 생성
  → P3/RP3β 계산
  → candidate 생성
  → 신규·중복·정책 필터
  → 최종 reranking
  → 노출·활동 로그 저장
  → 시간순 평가·모니터링

확인해야 할 운영 항목은 다음과 같다.

  • 활동 이벤트 중복 제거와 late event 처리
  • 사용자 삭제·탈퇴·동의 철회 반영
  • 콘텐츠 삭제·비공개 상태 반영
  • 모델/그래프 버전과 가중치 파라미터 기록
  • 추천 결과의 설명 경로 보존
  • graph build 실패 시 마지막 정상 버전 rollback
  • 인기 편향·롱테일·사용자군별 성능 모니터링
  • PII를 그래프 키나 로그에 직접 노출하지 않기

확인된 사실과 미확인 범위

  • 원문 확인: PageRank·PPR·P3·RP3β와 활동 강도 엣지 설계, 정규화·시간 감쇠·노출 편향·평가 논점을 확인했다.[1]
  • 연구 대조: PageRank의 Random Surfer 모델과 그래프 추천 기준선·재현성 논의를 관련 연구로 대조했다.[2][4][5]
  • 규모 사례: Pixie가 Pinterest의 대규모 그래프 실시간 추천 시스템으로 소개된 사실은 확인했지만, 그 성능 수치를 다른 서비스에 일반화하지 않았다.[3]
  • 미확인: 원문의 활동 강도 가중치·β·반감기 값이 실제 운영에서 최적이라는 증거, 특정 데이터셋의 개선폭, 온라인 A/B 결과는 확인되지 않았다.

참고 자료

[1] Jiyoon Blog — PageRank에서 RP3β까지

[2] A Troubling Analysis of Reproducibility and Progress in Recommender Systems Research

[3] Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time

[4] The PageRank Citation Ranking: Bringing Order to the Web

[5] When Newer is Not Better: Does Deep Learning Really Benefit Recommendation From Implicit Feedback?

※ 이 글은 원문을 기반으로 한 학습·설계 정리이며, 특정 추천 모델의 품질·성능·사업 효과를 보장하는 벤치마크가 아니다.

Sources

[1] https://jiyoonmik.github.io/blog/graph-random-walk-activity-recommendation [2] https://ar5iv.labs.arxiv.org/html/1907.06902 [3] https://arxiv.org/abs/1711.07601 [4] http://ilpubs.stanford.edu:8090/422 [5] https://arxiv.org/html/2305.01801v1