Dive into Twitter's recommendation system I - RealGraph

RealGraph: User Interaction Prediction at Twitter

Start from this one, I will write a series of articles to go through the details of Twitter’s recommendation system.

The first article is about Twitter’s in-network candidate retriever - RealGraph¹. This paper

1. is a bit old, first published in 2014, and the core algorithm is the traditional LR

2. mainly focus on the feature engineering work. This is also the inherent need of using LR

3. proposes a framework to produce a directed and weighted graph where
   the nodes are Twitter users, and the edges are labeled with interactions between a directed pair of users

4. conducts a detailed feature experiement and explains the feature importance

Twitter’s recommendation system

In Twitter’s official blog, they share the architecture.

Twitter’s recommendation system

Compared to common recommendation system, this one:

1. has the similar architecture, candidate retriever + ranking + post-ranking

2. heavily rely on graph algorithms for candidate retriever, like RealGraph and Social Graph

3. find candidates from people you follow (In-Network) and from people you don’t follow (Out-of-Network). The For You timeline consists of 50% In-Network Tweets and 50% Out-of-Network Tweets on average

And the most important component in ranking In-Network Tweets is Real Graph.

Real Graph

What’s is RealGraph?

The RealGraph is a directed, edge-labeled, weighted graph where the nodes are Twitter users, and the edges are labeled with interactions (from a fixed, extensible set) between a (directed) pair of users. Each edge also has a weight that is interpretable as tie strength and defined as the probability of any interaction going from the edge source to the edge destination in the future.

We can see that Twitter is modeling the interaction between two users into a binary classification problem.

RealGraph has been used:

1. in user recommendation system Who To Follow, it is a random walk algorithm that runs on the Twitter social graph. The output weights of RealGraph is used to guide the random walk

2. as an effective pre-processing mechanism for finding the top-k connections of a user. Directly use the weight to measure the user relevance

3. in other products, like search on Twitter, and the Discover page. The weights are used as the input feature for personalized scoring

4. for discovering similar users on Twitter² that has applications in ads targeting, collaborative filtering and community detection

The pipeline

RealGraph consists of three components:

1. Graph and feature generation, how to build the user connections and features

2. Feature scoring, how to train a LR model

3. Application, how to apply to downstream jobs

The pipeline

Graph generation

Add a edge for user pairs if:

1. A follows B

2. B is in A’s phone or email address book (only if the requisite permissions have been granted by the users)

3. A interacted with B

The RealGraph is computed on a daily basis in a incremental way to prevent snowballing:

1. merge new edges with previous day’s RealGraph

2. decay historical interaction values and remove an edge if the most recent interaction is too old

Edge features

Three variants for follow relationship:

1. a one-directional follow (the most common)

2. two-directional follows (where both users follow each other)

3. SMS-follow where A not only follows B, but has opted in to receive all of B’s tweets as either SMS or in application notifications

They store the number of days since the edge created as the feature.

Two kinds of interactions:

1. Visible interactions (from B’s viewpoint)

   1. A retweets B’s tweet

   2. A favorites B’s tweet

   3. A mentions B (via their handle), or Amessages B

2. Implicit interactions

   1. A clicks on B’s tweet or on a link within the tweet

   2. A visits B’s profile page.

Then create several dense features for interactions:

1. Non-zero days: the number of days when such an interaction happens

2. Mean and variance: the mean and variance of interaction counts (computed over non-zero interaction days)

3. Decayed count: a daily exponentially-decayed interaction count (EWMA)

4. Days since last interaction: number of days since the last interaction of this type

5. Elapsed days: number of days since the first interaction of this type happened

And some extra features:

1. the number of different non-zero interaction types for an edge as we have found diversity of historical interactions between two users to be a good indicator

2. the number of common friends (users that both follow and are followed by A and B) to measure closeness in terms of the graph

3. topic-related edge features on each edge, the number of common topics between source user’s interested-in and destination user’s known-for based on a 300 topic taxonomy

User features

Aggregation the edge features as the source user’s sending-feature and the destination users’s received-feature

Other features represents user activity and reputation:

1. These include number of tweets in the last week

2. language

3. country

4. number of followers

5. number of people they follow

6. PageRank on the follow graph

🤔 My comment: there is a good example of how to design features for graph relationships. Feature engineering is all RealGraph need

Model training and scoring

The target is defined as to predict interactions in a period given feature values before beginning of that period (and taken from a period of the same length).

They also add heuristic rules to filter out noisy edges, a edge is valid:

1. only if the destination user wrote at least one tweet in the test period, and if the source user had created at least one interaction in the test period

2. 🤔 My comment: guess this is just for reduce the training data size

Regarding the label:

1. The training label for an edge is set to 1 or -1 depending on the existence of any interaction. 🤔 My comment: why not 0 or 1, Twitter doesn’t share any detail, guess they just scale the result of sigmoid

2. Thus, the training task is to learn what combination of features in a period can predict whether there will be any interaction on the same edge in the future. 🤔 My comment: here every interaction is treated the same, this is not a good approach, some interactions like retweet should be more important than click

Evaluation

Two ways of evaluation:

1. Feature importance test, calculate AUC for different feature groups

2. User survey, nothing special here

How to extract the graph data:

1. One week of interaction data

2. Build a RealGraph for the first day of week using the remaining day’s data

3. To emphasize the implicit interaction, they give it 5x weight of implicit interactions while sub-sampling

4. If there is any interaction in the following days, the label will 1 and vice versa

5. They don’t balance the positive and negative instance

6. 🤔 My comment: yeah, negative sample ratio doesn’t affect the result much. They don’t mention how to build validation dataset, I guess they are using the data from next week

Here are the AUC results for each feature group.

We can see that:

1. non_zero_days has a big gain of 0.019

2. user reputation has another moderate gain of 0.003

3. user activity has another big gain of 0.022, including number of posted tweets, number of sent favorites and user’s country

Conclusion

That’s it, there is nothing magic but hard feature engineering work with LR model. But this is still a very good example for feature engineering.

Weekly digest

1. 大语言模型的涌现能力：现象与解释, how to explain the emergent ability of LLM? The author summarize the popular ideas and shares his own thought

2. Cheating is All You Need. This is an advertorial but still bring interesting ideas on the influence of LLMs for programmers.

   1. software engineering exists as a discipline because you cannot EVER under any circumstances TRUST CODE. Bug is the nature of coding, so is LLM’s code

   2. all the winners in the AI space will have data moats. This is the essential part of construct context for LLMs

3. THE AI INDEX REPORT from stanford

4. The Recommendation System at Lyft, hmm Lyft is still using LightGBM

5. Simply explained: how does GPT work?

What’s next

Let’s continue the journey of Twitter’s recommendation system, next article will be about the out-network candidate retriever - Social Graph (GraphJet: Real-Time Content Recommendations at Twitter)³

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

2. http://snap.stanford.edu/mlg2013/submissions/mlg2013_submission_20.pdf

3. https://www.vldb.org/pvldb/vol9/p1281-sharma.pdf