트위터 추천 알고리즘 RealGraph 정리 How does Twitter Recommend "For You" Timeline?

How does Twitter Recommend "For You" Timeline?

아래 다이어그램은 오픈 소스 알고리즘을 기반으로 한 트위터 추천 타임라인의 세부 파이프라인을 보여준다.

 

The process involves 5 stages

https://blog.twitter.com/engineering/en_us/topics/open-source/2023/twitter-recommendation-algorithm

1. Candidate Sourcing ~ 5억개(500million) 트윗으로 시작하기
2. Global Filtering ~ 최대 1,500개의 후보 생성하기
3. Scoring & Ranking ~ 4,800만 개의 파라미터 신경망, 트위터 blue boost
4. Filtering ~ 작성자 및 콘텐츠 다양성 확보
5. Mixing ~ 광고 추천 및 팔로우한 유저(Who to Follow)와 함께 믹싱

 

추천 시스템은 일반적인 2단계 접근 방식을 따르지만 Candidate 생성 단계의 다양한 구성 요소로 차별화된다. 이를 통해 fine ranking 단계에 다양한 종류를 가진 Tweet 셋을 제공하여 소비자에게 매력적인 셋을 제공하고자 한다.

• Real graph: 해당 유저의 네트워크 내부에 속한 콘텐츠를 추천 (이전 상호 작용을 기반으로 향후 상호 작용의 가능성 예측)
• GraphJet: 실시간 Users-Tweets 상호작용을 캡처하는 In-Memory 그래프 시스템 (Tweet 선택은 PageRank와 유사한 알고리즘을 사용)
• SimCluster: 플랫폼에서 가장 많이 팔로우하는 사용자를 기반으로 하는 community discovery 알고리즘. (트위터 사용자는 자신의 커뮤니티를 기반으로 트윗 추천 받음)
• TwHIM: 모든 Twitter entities(사용자, 트윗, 광고 등)의 벡터 표현을 학습하는 그래프 알고리즘. (벡터 공간에서 계산된 유사성 메트릭을 기반으로 추천)

 

RealGraph - User Interaction Prediction at Twitter

아래는 'RealGraph: User Interaction Prediction at Twitter'의 본문을 해석하여 정리한 내용이다. (참고: https://www.ueo-workshop.com/wp-content/uploads/2014/04/sig-alternate.pdf)

 

소셜 네트워크에서 개인화를 위한 일반적인 요구 사항은 특정 사용자의 기존 관계에 대한 관계 강도를 추정하는 것이다. 이 작업에서는 사용자 간의 직접적인 상호작용을 기반으로 사용자 간의 직접적인 상호 작용을 기반으로 관계 강도를 계산하는 프레임워크를 제공한다. 

 

RealGraph 프레임워크는 다음과 같은 방향성 및 가중치가 부여된 그래프를 생성한다.

• node: 트위터 사용자
• edge: 방향이 지정된 사용자 쌍 간의 상호 작용으

 

또한, 각 방향이 지정된 edge에는 edge source에서 edge destination으로 향후 상호 작용이 발생할 확률인 가중치도 있다. 프레임워크는 과거 데이터를 사용하여 로지스틱 회귀 기반 모델을 학습한 다음, 이 모델을 사용하여 edge 특징에 점수를 매겨 가중치를 생성한다. 

 

트위터에서는 RealGraph의 여러 애플리케이션을 제공한다.

• 더 나은 사용자 추천을 계산하고, 사용자 검색 결과의 관련성을 개선하며, 강한 관계와 약한 관계를 구분함으로써 이점을 얻을 수 있는 모든 작업에서 향상된 성능을 제공하는 데 사용된다.
• 마지막으로, 학습 방법론의 효과와 애플리케이션 관점에서의 성능을 모두 기반으로 RealGraph에 대한 평가도 제공한다.

 

# Index 

이 백서의 나머지 부분은 다음과 같이 구성된다. 

• 섹션 1에서는 RealGraph 전체적인 개요를 설명한다. 
• 섹션 2에서는 RealGraph 프레임워크의 개요와 엣지 기능 및 관련 애플리케이션에 대해 설명한다. 
• 섹션 3에서는 RealGraph 프레임워크에 대한 평가를 제공한다. 
• 섹션 4에서는 몇 가지 관련 작업에 대해 설명한다. 
• 섹션 5에서 백서를 마무리한다.

 

섹션1. Introduction

트위터에서 사용자는 서로 팔로우(서로의 콘텐츠를 받아볼 수 있는 기능)뿐만 아니라 다양한 상호 작용을 통해 서로 연결될 수 있다. 

• 서로의 콘텐츠 클릭 (즉, 다른 사람의 트윗) 
• 다른 사람의 트윗을 리트윗 (자신의 팔로워에게 전파) 
• 마음에 들어요 표시하기 등 

 

상호 작용 데이터를 통해 트위터에서 각 양방향 연결에 대해 정량적인 'Strength' 값을 할당한다. 이 값은 사용자 행동에 대한 이해도를 높이는 것 외에도 폭넓게 활용된다.

• 더 나은 사용자 추천 
• 사용자 검색 결과의 관련성 개선 
• 긴밀한 관계와 약한 관계를 구분

 

이는 모든 작업에서 향상된 성능 제공한다. 예를 들어, (트위터 사용자는 프로필 페이지로 이동하기 위해) 직접 연결을 검색하는 경우가 많으며, 더 많이 상호작용하는 사용자를 노출하면 제품에 대한 만족도와 사용률이 높아진다. 

 

1.1 Tie Strength (결합 강도)

(그래프 DB로 표현하면 Edge Weight로도 볼 수 있을 것 같다.)

 

트위터에서 Tie Strength를 계산하는 문제는 몇 가지 특징이 있다.

• 첫째, 다양한 상호작용이 존재하며 tie strength에 매우 다른 영향을 미칠 수 있다.
  • 두 개의 계정을 팔로우하지만 1) 한 계정의 트윗에 리트윗하고 2) 다른 계정의 트윗에 좋아요를 하는 경우 어느 쪽의 관계가 더 강한지 알 수 있을까?
• 둘째, 트위터는 2억 5천만 명 이상의 활성 사용자와 수십억 개의 팔로잉 edge를 보유하고 있다.
  • 활성 사용자가 2억 5천만 명 이상이며, 매일 수십억 건의 상호 작용이 매일 수십억 건의 상호작용이 이루어진다. 프레임워크는 이러한 규모를 처리할 수 있어야 한다.
• 마지막으로, 계산된 tie strength를 어떻게 해석할 것인가에 대한 질문이 있다.
  • 이상적으로는 계산된 가중치를 일반적이고 쉽게 해석할 수 있는 메트릭으로 만들어 다양한 사용 사례에 적용할 수 있도록 하는 것이 이상적이다.

 

1.2 RealGraph, tie strength 측정 프레임워크 

트위터에서 tie strength를 측정하기 위해 구축한 RealGraph라는 프레임워크를 소개한다. RealGraph는 node가 트위터 사용자이고, edge는 (지시된) 사용자 쌍 간의 상호 작용(고정된 확장 가능한 집합에서)으로 레이블이 지정된 가중치 그래프이다. 

 

또한 각 edge에는 tie strength로 해석할 수 있는 가중치가 있으며, 이는 향후 edge source에서 edge destination으로의 모든 상호 작용이 발생할 확률로 정의된다. 가중치는 엣지 레이블을 특징으로 사용하고 과거 상호 작용 데이터를 사용하여 학습한다. 

• (i) 다양한 설정에서 쉽게 해석할 수 있다는 점, (사용자 검색 예시로 돌아가서 실제로 사용자가 상호작용을 원하는 제안을 선호한다는 점 
• (ii) 단순한 과거 요약이 아닌 미래를 내다보는 tie strength의 한 척도라는 점 
• (iii) 애플리케이션이 점수를 직접 사용할 수 있도록 (미래 상호작용의 확률을 통해) tie strength에 대한 정량적 척도를 제공한다는 점 

위와 같은 이유로 RealGraph 가중치는 일반적으로 적용할 수 있다는 점을 강조하고 있다. 

 

예를 들어, 임계값 메커니즘과 함께 상호 작용 확률을 관련성 필터로 사용할 수 있다. 또한 이 프레임워크는 edge 라벨과 학습 파이프라인을 애플리케이션에 대한 사용자 지정 가중치를 학습하도록 조정할 수 있도록 구축되어 있다는 점에 주목한다.

 

RealGraph 첫 번째 사용 예시) Who To Follow, 랜덤 워크 알고리즘

2011년 말에 구축된 이후 RealGraph는 트위터 내에서 다양한 애플리케이션에 사용되었다. RealGraph의 첫 번째 적용(그리고 원래의 동기)은 트위터의 사용자 추천 시스템인 'Who To Follow'에 있었다.

 

이전 작업에서 자세히 설명한 바와 같이, Who To Follow의 기본 구성 요소는 트위터 소셜 그래프에서 실행되는 '랜덤 워크 알고리즘'이다. 이 알고리즘은 가중치에 따라 랜덤 워크를 안내하기 위해 RealGraph output을 쉽게 사용할 수 있다. 이 알고리즘은 팔로워와 더 강한 유대 관계를 맺고 있는 사용자에게 추천을 편향되게 한다. 또한 외부 추천에 유용한 RealGraph 관련 애플리케이션도 주목할 만 하다. 사용자의 상위 k 인맥을 찾기 위한 효과적인 전처리 메커니즘으로 사용할 수 있으며, 이는 정보 손실을 제한하면서 애플리케이션에 쉬운 스케일링 체계를 제공할 수 있다. (심하게 왜곡된 분포에 대응) 마지막으로, 다양한 관련성 제품(예: 트위터 검색 및 Discover 페이지)은 RealGraph 가중치를 사용하여 개인화된 결과 점수를 매긴다.

 

섹션 2. RealGraph 프레임워크

이제 트위터에서 RealGraph 프레임워크의 구현에 대해 자세히 알아보자. 트위터의 프레임워크는 주로 Hadoop의 Pig에서 구현된다. Hadoop에서 실행하면 트위터의 중요한 요구 사항인 수억 명의 사용자로 시스템을 확장할 수 있다. 그림 1에서 볼 수 있듯이, 트위터에는 기본적으로 그래프(및 feature) 생성, feature 스코어링 및 애플리케이션의 세 가지 구성 요소로 구성된 작업의 'pipeline'이 있다.  (그래프 생성 단계는 섹션 2.1에 자세히 설명되어 있다.) 

 

각 사용자에 대해 팔로우하는 사람, 주소록에 있는 사람1, 상호작용한 사용자의 조합을 사용하여 나가는 edge set을 얻는다. 또한 각 edge에는 source 사용자에서 target 사용자로 상호 작용이 발생하는 시기와 빈도 등의 정보가 포함된 기능이 레이블로 지정된다. (이러한 edge 특징과 해당 집계된 vertex 특징은 섹션 2.2의 모델 점수화 단계에서 사용되며, 여기서는 별도로 학습된 로지스틱 회귀 모델을 적용합니다.) 

 

학습된 모델은 edge 및 vertex 특징을 모두 사용하여 각 그래프 edge에 적용되어 가중치, 즉 이 edge에서 향후 상호 작용이 발생할 확률을 계산한다. 2.3절에서는 추천 및 검색을 위해 RealGraph 가중치를 적용하는 Hadoop 계산의 예를 제시한다.

 

2.1 Graph 생성

특정 기간에 사용자 A에서 사용자 B로 연결되는 에지가 RealGraph에 추가되는 방법에는 세 가지가 있다

• (i) A가 B를 팔로우하는 경우
• (ii) B가 A의 전화 또는 이메일 주소록에 있는 경우 (다시 말하지만, 사용자가 필요한 권한을 부여한 경우에만 해당)
• (iii) A가 B와 상호작용한 경우

현재, 트위터는 매일 RealGraph를 계산하기 때문에 이러한 edge를 매일 추가한다. 그런 다음 이를 전날의 RealGraph와 병합하여 집계 버전을 생성한다. 이 데이터가 눈덩이처럼 불어나는 것을 방지하기 위해 과거 상호 작용 값을 감쇠시키고 가장 최근 상호 작용이 너무 오래된 경우 에지를 제거한다. (매개 변수로 조정 가능)

• 다양한 에지 특징을 가진 그래프 에지에 대한 자세한 내용은 섹션 2.1.1에 설명되어 있다.
• 또한 그래프 정점에 사용자 특징을 연결하는데, 이는 2.1.2절에 나와 있다.

 

2.1.1 Edge Features

팔로우 edge

트위터에서는 RealGraph의 팔로우 관계를 세 가지로 분류한다.

1. 단방향 팔로우(가장 일반적)
2. 양방향 팔로우(두 사용자가 서로 팔로우하는 경우)
3. 그리고 A가 B를 팔로우할 뿐만 아니라 B의 모든 트윗을 SMS 또는 비신청 알림으로 수신하도록 opt-in한 SMS 팔로우

또한 이러한 각 기능에 Boolean 값을 저장할 뿐만 아니라 수량도 저장한다. 팔로우 edge의 경우, edge가 생성된 이후 일수를 저장한다. 주소록 edge에도 이 수량을 저장한다.


인터랙션 edge

인터랙션 에지는 약간 다른 방식으로 처리된다. 사용자 A에서 B로의 두 가지 종류의 상호작용을 수집한다

1. 눈에 보이는(Visbile) 상호작용 (B의 관점에서): A가 B의 트윗을 리트윗하거나, A가 B의 트윗을 마음에 들어요 표시하거나, A가 B를 멘션하거나, A가 B에게 메시지를 보내는 경우
2. 암묵적(Implicit) 상호작용: A가 B의 트윗을 클릭하거나 트윗에 포함된 링크를 클릭한 경우, A가 B의 프로필 페이지를 방문하는 경우

이러한 각 상호작용에 대해 트위터에서는 각 상호작용의 발생 빈도, 강도 및 최근 시점을 파악하기 위해 여러 시계열 관련 값을 수집한다. 

• Non-zero days(0이 아닌 일수): 해당 상호작용이 발생한 일 수이다.
• Mean and variance(평균 및 분산): 상호작용의 평균 및 분산 카운트(Non-zero days에 대해 계산됨)
• Decayed count(감쇠 횟수): 매일 지수적으로 감쇠하는 인터랙션 횟수(*EWMA)
• Days since last interaction(마지막 인터랙션 이후 일수): 이 유형의 마지막 상호작용 이후 일수
• Elapsed days(경과 일수): 이 유형의 첫 번째 상호 작용이 발생한 이후의 일수 발생한 일수

마지막으로, 위에 언급한 것 외에 몇 가지 다른 edge 기능이 있다.

• 먼저, 두 사용자 간의 과거 상호작용의 다양성이 좋은 지표가 될 수 있다는 것을 발견했기 때문에 에지에 대해 0이 아닌 다양한 상호작용(non-zero interaction) 유형의 수를 나타내는 기능이 있다.
• 또한 그래프에서 친밀도를 측정하기 위해 공통 친구(A와 B가 모두 팔로우하고 있는 사용자) 수에 대한 기능도 있다.
• 또한 각 에지에 몇 가지 토픽 관련 edge 기능을 추가한다. 이를 계산하기 위해 300개의 토픽 분류와 고정밀 토픽 모델링 시스템을 사용하여 [10]에 설명된 대로 각 사용자에 대해 관심 있는 토픽과 알려진 토픽을 할당한다. 그 결과 소스 사용자의 관심 토픽과 대상 사용자의 알려진 토픽 간의 공통 토픽 수와 같은 몇 가지 에지 특징이 생성된다.

*EWMA(Exponentially Weighted Moving Average: 지수가중이동평균): 가장 큰 이점은 무엇보다도 공정 평균의 작은 변화를 감지하는 데 활용할 수 있다는 사실이다.

 

2.1.2 User Features

이전 섹션에서 설명한 각 edge 기능 유형에 대해 값을 집계하여 source 사용자에게는 보내는 기능으로, target 사용자에게는 받는 기능으로 사용한다. 예를 들어, 사용자의 총 리트윗 수에 대한 EWMA는 모든 발신 edge에 대한 리트윗 상호작용의 EWMA를 합한 값이다. 반면에 mention 평균은 사용자 이름이 포함된 트윗의 일일 평균이다. 또한 각 사용자의 활동과 평판에 대한 몇 가지 기능도 포함되어 있다. 여기에는 지난 한 주 동안의 트윗 수, 언어, 국가, 팔로워 수, 팔로우하는 사람 수, 팔로우 그래프의 페이지 순위 등이 포함된다.

 

 

2.2 Model Training and Scoring

트위터의 PigML 파이프라인을 사용해 로지스틱 회귀 모델을 주기적으로 훈련하고 매일 업데이트된 RealGraph edge를 점수화하는 데 사용한다. edge가 주어지면, 우리는 분류를 위해 edge 특징(섹션 2.1.1)과 source 사용자와 target 사용자 모두의 vertex 특징(섹션 2.1.2)을 사용한다. 

학습의 목표는 해당 기간이 시작되기 전(그리고 동일한 길이의 기간에서 가져온) 특징값이 주어진 기간의 상호작용을 예측하는 것이다. 사용자 활동의 변동에 따른 영향을 제거하기 위해 훈련 데이터셋을 만들 때 두 가지 필터를 적용한다. target 사용자가 테스트 기간에 최소 한 번 이상 트윗을 작성한 경우와 source 사용자가 테스트 기간에 최소 한 번 이상 상호작용을 생성한 경우에만 edge가 훈련 인스턴스가 될 수 있다.

훈련 과제는 이진 분류 문제로 설정되며, 상호작용의 존재 여부에 따라 edge에 대한 훈련 레이블이 1 또는 -1로 설정된다. 따라서 학습 과제는 특정 기간에 어떤 특징의 조합이 미래에 동일한 에지에서 상호작용이 있을지를 예측할 수 있는지 학습하는 것이다. 

이 특별한 설정은 두 가지 이유로 존재한다

1. 원래의 목표였던 서로 다른 종류의 특징을 결합하고 구별하는 법을 여전히 학습하기 위해서입니다. 
2. 상호작용의 결합을 예측하는 것은 매우 일반적이므로 다양한 사용 사례를 포착할 수 있습니다. 

Feature의 효과를 평가하기 위해, 피처를 10개 그룹으로 분류하고 점진적인 AUC 개선을 계산한다. 자세한 내용은 섹션 3에 나와 있다.

 

2.3 Applications

RealGraph 가중치의 몇 가지 적용 사례를 간략하게 설명하겠다. RealGraph 가중치는 edge에서의 향후 상호작용 확률에 해당하므로 사용자 간의 유대 강도를 정량적으로 측정할 수 있다는 점을 기억하자. 이를 통해 사용자의 팔로잉을 구분하여 상호작용이 없는 edge는 다운그레이드하고, 동시에 크고 반복적인 상호작용이 있는 edge는 업그레이드할 수 있다. 이러한 로컬 그래프 '가지치기 pruning'를 통해 그래프 기반 알고리즘이 고품질의 에지에 더 쉽게 집중할 수 있다.

이제 트위터에서 RealGraph 가중치를 사용하는 몇 가지 그래프 알고리즘을 살펴보겠다.

• 트위터의 사용자 추천은 소셜 그래프에서 실행되는 개인화된 PageRank와 같은 개인화된 알고리즘에 의해 이루어진다.
• 또한 트위터에서는 각 사용자에 대해 개인화된 페이지랭크가 높은 대규모 계정 세트(신뢰 서클이라고 함)를 계산하여 저장하고, 이를 검색 및 발견과 같은 다양한 시스템에서 관련성을 높이기 위해 사용한다.
• 이러한 개인화된 페이지랭크 계산(랜덤 워크를 통해 구현됨)에 RealGraph 가중치를 통합함으로써 더 나은 개인화를 달성할 수 있다. 

이제 개인화된 PageRank 계산이 Hadoop에서 실행되기 때문에 이러한 작업이 원활하게 이루어진다. 

 

신뢰 서클 (Circle of Trust)

신뢰 서클의 개인화 개선은 사용자 추천에 도움이 될 뿐만 아니라, 사용자의 신뢰 서클 트윗이 검색 결과 페이지에서 더 높은 순위를 차지하기 때문에 개인화된 트윗 검색의 품질도 향상된다. 신뢰 서클의 또 다른 적용 사례로는 트위터 사용자 검색을 위한 TypeAhead(자동 완성 기능이라고도 함)가 있으며, 이 기능 역시 RealGraph 가중치가 강화된 신뢰 서클의 클릭률을 개선했다.

또한 광고 타겟팅(ads targeting), 협업 필터링(collborative filtering) 및 커뮤니티 감지(commnutiy detection)에 적용되는 트위터에서 유사한 사용자를 발견하는 문제에 대해서도 언급했다. 

두 명의 트위터 사용자가 비슷한 사용자 집합을 팔로우하면 유사한 사용자로 간주한다. 트위터 유사도 계산은 RealGraph에서 유사도 계산(코사인 유사도)을 실행하여 상호 작용도 고려한다. (유사도 프레임워크에 대한 자세한 내용은 원저 참고)

 

섹션 3. Evaluation

이 섹션에서는 RealGraph의 성능에 대한 평가를 제공한다. 

RealGraph에 대한 평가는 두 가지 종류가 있다:

1. 자체 학습 과제에서 RealGraph의 효과를 측정하는 자체 평가
2. 메트릭의 품질을 향상시키는 데 있어 RealGraph의 효과를 측정하는 애플리케이션 관점에서의 평가

이 두 가지 평가의 결과를 제시한다.

1. 먼저, 특징을 여러 그룹으로 나눈 다음 3.1절의 순방향 단계별 절차를 사용하여 각 그룹에 대한 곡선 아래 면적(AUC)을 계산하여 RealGraph의 학습 효과를 평가한다.
2. 그런 다음 3.2절에서 상위 k 에지의 결정 정밀도를 적용하기 위해 소규모 사용자 설문 조사를 수행하여 RealGraph의 품질을 평가합니다.

 

3.1 Self-evaluation

이 평가에서는 섹션 2에 설명된 대로 과거 상호작용을 사용하여 RealGraph 모델을 구축한 다음 AUC 지표를 사용하여 이러한 모델을 평가한다. 일주일간의 인터랙션 데이터가 주어지면, 앞서 설명한 기능을 사용하여 RealGraph 모델을 구축한 후 에 대해 앞서 설명한 기능을 사용하여 모델을 구축한다. 

이전과 마찬가지로 나머지 요일에 대한 일일 상호작용을 두 가지 유형으로 나눈다. 

1. visible interactions (리트윗, 마음에 들어요, 멘션, 쪽지 포함)
2. implicit interactions (트윗 클릭, 링크 클릭, 프로필 클릭 포함)

 

visible interaction 에는 implicit interaction 의 5배 가중치를 부여하여 하위 표본을 추출한다.

첫 번째 날 집계된 RealGraph의 모든 edge는 해당 edge가 다음 주에 상호작용을 본 경우 1로, 그렇지 않은 경우 -1로 레이블이 지정된다는 점을 기억하라. 트위터는 긍정적인 훈련 인스턴스와 부정적인 훈련 인스턴스 간의 명시적인 균형을 맞추지 않는다. 이 데이터를 사용하여 L2 정규화와 함께 확률적 경사 하강 로지스틱 회귀를 사용하여 모델을 학습하고 모델의 AUC를 결정한다.

이 평가 결과는 Table 1에 나와 있다. 

• 처음 두 그룹은 리트윗, 마음에 들어요, 메시지와 같은 기록 기능에 서로 다른 시계열을 사용했다. 
• 다음 그룹은 암시적 상호작용과 에지 유형(팔로우 에지, 양방향 또는 SMS)을 추가했다. 그런 다음 사용자의 평판과 총 팔로우 수, 총 팔로워 수와 같이 네트워크에서 추출한 피처를 기반으로 한 피처를 사용했다. 
• 또한 사용자가 연관된 토픽과 관련된 기능을 추가하는 것이 미치는 영향도 평가했다. 주어진 엣지에 대해 겹치는 토픽의 수를 피처 값으로 사용했다. 다음으로 게시한 트윗 수, 보낸 마음에 들어요 수, 사용자의 국가와 같은 사용자 활동 요약에서 얻은 기능을 사용했다. 
• 마지막 기능 세트는 사용자의 주소록에서 얻었다. 새로운 기능 추가에 따른 AUC의 개선은 두 번째 열에 나와 있다. 

분명히 알 수 있듯이, vertex 기능을 추가하는 것이 상당히 유용했다. 또한, edge 피처의 일관성(non-zero days에 의해 반영됨)도 향후 상호작용을 예측하는 좋은 지표이다. 마지막으로, 사용자 활동은 확실히 향상된 사용자 활동과 관련이 있다. 따라서 상호작용 가능성도 높아진다.

 

섹션 4. Realted Work

여기에서 관련 업무에 대한 간략한 설문조사를 제공한다.

 

트위터는 일반적인 개인화 프레임워크의 역할을 하는 것을 목표로 하는 직접 비교할 만한 작업은 없다. 우리와 가장 유사한 작업 가장 가까운 작업은 [L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social networks]로, 저자들은 개인화된 페이지랭크에 최적화된 로지스틱 엣지 가중치 모델 가중치를 기반으로 개인화된 PageRank 모델 가중치를 기반으로 미래의 친구 순위를 비친구보다 높게 더 높은 순위를 매길 수 있도록 최적화된 모델을 구축한다.

 

트위터의 작업은 결과 에지 가중치가 사용자와 트윗의 순위를 매기는 데에만 사용되는 것이 아니라는 점에서 기본 목표가 다르다. 사용자와 트윗의 순위를 매기는 데만 사용되는 것이 아니라, 더 중요한 것은 트위터에서 검색, 추천 및 타겟팅을 위한 일반적인 개인화 프레임워크의 역할을 한다는 점이디.

 

사용자 참여 예측은 웹 검색, 스폰서 검색 광고, 웹 검색, 스폰서 검색 광고 및 디스플레이 광고에 대해서도 사용자 참여 예측이 연구되었다. 상호작용 로그 데이터를 사용하여 [M. Ageev, Q. Guo, D. Lagun, and E. Agichtein. Find it if you can: a game for modeling different types of web search success using interaction data.] 검색 성공 모델을 개발한다. 검색 성공 모델을 개발하고 검색 성공 예측을 위한 효과적인 모델을 훈련한다. 

 

섹션 5. Conclusion

이 백서에서는 트위터에서 개발한 사용자 상호작용 예측 프레임워크인 RealGraph에 대해 소개했다. RealGraph는 이질적인 인터랙션 데이터를 사용하여 미래의 잠재적인 사용자 인터랙션을 효과적으로 예측한다. 사용자 상호작용의 예측 점수는 연결 강도로도 해석할 수 있어 다양한 애플리케이션에서 RealGraph를 사용할 수 있다. 이러한 애플리케이션의 성공적인 배포를 통해 RealGraph는 트위터에서 그래프 처리 도구의 필수 구성 요소로 자리 잡았다. 

 

또한 향후 RealGraph에 대한 작업 방향은 여러 가지가 있다.

• 첫째, 현재 RealGraph는 배치 모드로만 업데이트되므로 실시간 신호를 소비하도록 프레임워크를 확장하는 것이 즉각적인 관심사가 될 수 있다. 또한 실시간 업데이트를 처리하는 데 온라인 학습 접근 방식이 적합할 수 있다.
• 둘째, 일부 사용자 인터랙션은 다른 인터랙션보다 시간에 훨씬 더 민감하므로 시간 감쇠 효과의 모델링을 개선할 수 있으므로 기능에 시간 패턴을 통합하는 것이 매우 유용할 수 있다.
• 셋째, 더 나은 예측 성능을 위해 사용자 간의 의존성을 탐색하는 것도 흥미로울 것이다. 예를 들어, 두 사용자의 속성이 비슷하다면 한 사용자가 항상 다른 두 사용자와 동시에 상호 작용할 수 있다.

 

요약

RealGraph는 Candidate 생성 알고리즘 중 가장 간단한 작업에 속한다고 한다. 과거 상호작용을 기반으로 앞으로 어떤 사용자와 상호작용할지 예측하는 것이 핵심이다. 사용자 A에서 사용자 B로 연결되는 Edge가 존재할 수 있는 경우는 다음 세 가지이다:

• A가 B를 팔로우하는 경우
• B가 A의 전화 또는 이메일 주소록에 있는 경우
• A가 B와 상호 작용한 경우

 

이 모델은 단순 로지스틱 회귀 모델이다. 이 모델은 Hadoop에서 매일 배치 작업으로 실행된다.

 

로지스틱 회귀 모델

 

사용되는 데이터는 다음과 같다.

• The binary target: 주어진 기간 동안 상호작용(메시지, 마음에 들어요, 리트윗 등)이 발생했나요?
• Edge features
  • 특정 상호작용 이후 일수
  • 인터랙션 횟수의 평균 및 분산
  • 매일 기하급수적으로 감소하는 인터랙션 횟수
  • 마지막 인터랙션이 발생한 이후 일수
  • 첫 번째 상호작용이 발생한 이후 일수
• User features
  • 들어오는 에지와 나가는 에지에 대한 집계된 에지 기능 값
  • 지난 한 주 동안의 트윗 수
  • 언어
  • 국가
  • 팔로워 수
  • 팔로우하는 사람 수
  • 팔로우 그래프의 PageRank

 

이 모델의 점수를 사용하여 향후 상호작용 가능성에 따라 사용자 순위를 매긴다. 그러면 이제 Top 사용자의 Tweet을 선택할 수 있다. 선택한 Tweet에 다양성을 추가하여 같은 사용자의 Tweet이 너무 많지 않도록 하는 것이 중요하다.

 

 

(RealGraph는 트위터의 오래된 시스템으로 곧 더 이상 사용되지 않고 새로운 시스템으로 대체될 가능성이 높다.)

---

Refs

https://www.ueo-workshop.com/wp-content/uploads/2014/04/sig-alternate.pdf

https://github.com/twitter/the-algorithm 

https://blog.twitter.com/engineering/en_us/topics/open-source/2023/twitter-recommendation-algorithm

https://newsletter.theaiedge.io/p/deep-dive-how-to-build-the-twitter?utm_source=substack&utm_medium=email