Neural Message Passing

In GNN’s our object of interest is assigned as the nodes in our Graph. Usually, the main objective in GNNs is to build powerful representations of the nodes, edges, or both via their relationships.

The fundamental difference between GNNs and traditioanl Neural Networks, is that during the training, we’re explicitly using operators that transfer data between node representations “along the edges”. This is called message passing. Let’s start with an example to prime the basic idea.

Let nodes represent users, and their features are things like their persona features: demographic, onboarding survey question, etc. Let edges be the social network graph: are they friends? And let’s add some decoration to the edges, such as the number of DM’s exchanged between them on the platform. If we are the social media company who wants to introduce ad-shopping to our platform, we may start with those persona features but we’d ideally like to use something about this network of communication. In theory, people who communicate and share content with each other a lot, may have similar taste. Somewhat tellingly we introduce a concept called a message function, which allows features to be sent from node-to-node. The message function uses features from each node, and the edge between them, written mathematically as:

for $h_i^{\left(k\right)}$ the features at node $i$ and $h_j^{\left(k\right)}$ at node $j$ respectively. The features of the edge are $e_{ij}$ and $ℳ$ is some differentiable function. Note that the superscript ${\phantom{}}^{\left(k\right)}$ refers to the layer as is normal in back-prop notation. Some simple examples include:

1. $m_{ij}^{\left(k\right)}=h_i^{\left(k\right)}$ which means “take the features from a neighbor node”

2. $m_{ij}^{\left(k\right)}={\displaystyle \frac{h_i^{\left(k\right)}}{c_{ij}}}$ which means “average by the number of edges between i and j”

There are many very powerful message passing schemes that use learning from other areas of Machine Learning – like adding an attention mechanism on node features – but this book won’t dive deep into this theory.

The next function we’ll introduce is the aggregation function, which is a function which takes as input the collection of messages and aggregates them. The most common ones are very natural:

1. concatenate all the messages

2. sum all the messages

3. average all the messages

4. take the max of the messages

Finally, we will use the output of the aggregation as part of our update function, which takes node features, aggregated message functions, and then applies additional transformations. If you’ve been wondering “where does this model learn anything?”, the answer is in the update function. The update function usually has a weight matrix associated to it, so as you train this neural network you are learning the weights in the update function. The simplest examples of update functions are to multiply a weight matrix by the vectorized output of your aggregation, and then apply an activation function per vector.

This chain of message-pass, aggregate, update is the core of GNNs, and encompasses a broad capability. They’ve been useful for ML tasks of every kind, including recommendations. Let’s see some direct applications to recommendation systems.

Applications

Let’s revisit some of the high-level ideas that GNN’s may touch in the recsys space.

Random Walks

Random walks in Graph Neural Networks (GNNs) refer to methods that use random walks on the user-item interaction graph to learn effective node (i.e., user or item) embeddings. The embeddings are then used to make recommendations. In the context of graphs, a random walk is an iterative process of starting on a particular node, and the stochastically moving to another connected node via a randomized choice.

One popular random walk-based algorithm for network embedding is DeepWalk, which has been adapted and extended in many ways for various tasks, including recommendation systems.

Here’s how a random walk GNN approach might work in a recommendation context:

1. Random Walks Generation Start by performing random walks on the interaction graph. Starting from each node, you make a series of random steps to other connected nodes. This results in a set of paths or “walks” that represent the relationships between different nodes.

2. Node Embeddings The sequences of nodes generated by the random walks are treated similarly to sentences in a corpus of text, and each node is treated like a word. Word2Vec or similar language modeling techniques are then used to learn embeddings for the nodes (i.e., vector representations), such that nodes appearing in similar contexts (i.e., in the same walks) have similar embeddings.

3. Recommendations Once you have learned node embeddings, you can use them to make recommendations. For a given user, you might recommend items that are “close” to that user in the embedding space, according to some distance metric. This can use all of the techniques we’ve previously developed for recommendations from latent space representations.

This approach has some nice properties:

• It can capture the high-order connections in the graph. Each random walk can explore a part of the graph that’s not directly connected to the starting node.

• It can help with the sparsity problem in recommender systems because it uses the structure of the graph to learn representations, which requires less interaction data.

• It naturally attempts to handle cold-start issues. For new users or items with few interactions, their embeddings can be learned from connected nodes.

Nevertheless, there are some challenges with this approach. Random walks can be computationally expensive on large graphs, and it might be difficult to choose appropriate hyperparameters, such as the length of the random walks. Also, this approach may not work as well for dynamic graphs where interactions change over time, since it doesn’t inherently consider temporal information.

This method implicitly assumes that the nodes are hetergeneous and so co-embedding them via connections is very natural. While it was not an explicit requirement, the type of sequence embeddings DeepWalk builds tends to structurally assume this. Let’s break this rule to accomodate learning between heterogeneous types in our next architecture example, metapaths.

Metapath and Heterogeneity

Metapath was introduced to improve explainable recommendations and integrate the ideas of knowledge graphs with GNNs.

A metapath is a path in a heterogeneous network (or graph) that connects different types of nodes via different types of relationships. Heterogeneous networks contain different types of nodes and edges, representing various types of objects and interactions. Beyond simply users and items, the node types can be “carts of items” or “viewing sessions” or “channel used for purchase”.

Metapaths can be used in Graph Neural Networks for handling heterogeneous information networks (HINs). These networks provide a more comprehensive representation of the real world. When used in a GNN, a metapath provides a scheme for how information should be aggregated and propagated through the network. It defines the type of paths to be considered when pooling information from a node’s neighborhood.

For example, in a recommender system, you might have a heterogeneous network with users, movies, and genres as node types, and “watches” and “belongs to” as edge types. A metapath could be defined as “User - watches → Movie - belongs to → Genre - belongs to → Movie - watches → User”. This metapath represents a way of connecting two users through the movies they watch and the genres of those movies.

A popular method that utilizes metapaths is the Heterogeneous Graph Neural Network (Hetero-GNN) and its variants. These models leverage the metapath concept to capture the rich semantics in HINs, enhancing the learning of node representations.

Metapath-based models have shown promising results in various applications, as they allow you to explicitly encode much more abstract relationships into the message passing mechanisms mentioned above.

If higher order modeling is your thing, buckle up for the last concept we’ll cover in this book. State of the art, and full of high-level abstractions. Language Model backed agents are at the absolute cutting edge of ML Modeling.

LLM Recommenders

Natural languge is a wonderful interface to ask for recommendations. If I want a coworker’s recommendation for lunch, maybe I’ll show up at their desk and say nothing – hoping they’re remember their latent knowledge of my preferences, identify the time-of-day context, recall the availability of restaurants based on day-of-week, and keep in mind that yesterday I had a pastrami sandwich.

More effectively, would be to simply ask “any suggestions for lunch?”

Like my astute coworker, models may be more effective at providing recommendations if you simply ask them to. This also adds the capability of defining more precisely what kind of recommendation I want. A popular application of LLMs is to ask them for recipes that use a set of ingredients. Thinking through this in the context of the kind of recommenders we’ve built, there are some hurdles to building a recommender of this kind. It probably needs some user modeling, but it’s very dependent on the items specified. This means that there’s a very low signal for each combination of specified items.

An LLM on the other hand, is quite effective at the auto-regressive nature of this task: given a few ingredients, what’s most likely to be included next in the context of a recipe. By generating several items like this, a ranking model can augment this to provide a realistic recommender.

Instruct Tuning for Recs

In the previous discussion of instruct pairs, we saw that ultimately the training was learning a rank comparison between two responses. This kind of training should feel quite similar. In a recent paper TALLRec, the authors use a similar setup to teach user preferences to the model.

As the paper mentions, one collects historical interaction items into two groups based on their ratings: user likes and user dislikes. They collect this information into natural language prompts to format a final “Rec Input”:

1. “User Preference: $[ite{m}_1,...,ite{m}_n$]

2. “User Preference: $[ite{m}_1,...,ite{m}_n$]

3. “Will the user will enjoy the “User Preference: $[ite{m}_{n+1}$"

These follow the same training pattern as InstructGPT from above. The authors achieve dramatically improved performance on recommender problems than an untrained LLM for recs, however those should be considered baselines as it’s not their target task.

LLM Rankers

So far in this chapter, we’ve thought of the LLM as a recommeder in totality, but instead, the LLM can be used as simply the ranker. The most trivial approach to this is to simply prompt the LLM with the relevant features of a user, and a list of items, and ask it to suggest the best options.

While naive, variants on this approach have seen somewhat surprising results in very generic settings: “the user wants to watch a scary movie tonight, and isn’t sure which will be the best if he doesn’t like gore: movie-1, movie-2, etc…​”. But we can do better.

Ultimately, like LTR approaches, we can think of pointwise, pairwise, and listwise. If we wish to use an LLM for a pointwise ranking, then we should constrain our prompting and responses, to a setting in which these models may be useful. Take for example a recommender for scientific papers; a user may wish to write what their working on, and the LLM helpfully suggest papers of relevance. While a traditional search problem, this is a setting in which our modern tools can bring a lot of utility: LLM’s are effective at summarizing and semantic matching, which means that from a large corpus semantically similar results may be found, and then the agent can synthesize the output of those results into a cogent response. The biggest challenge here is hallucination, or suggesting papers that may not exist.

Pairwise and listwise can be thought of similarly: distilling the reference data into a shape that the unique capabilities of these LLMs can make significant assists.

While we’re near the topic of search and retrieval, it’s important to mention one of the ways in which recommendation can help LLM applications: retrieval augmentation.

Recs 4 AI

We’ve seen how Large Language Models can be used to generate recommendations, but how to recommenders improve LLM applications? LLM agents are extremely general in their capabilities, but lack specificity on many tasks. If you ask an agent: “which of the books I read this year were written by non-western authors”, the agent has no chance of success. Fundamentally, this is because the general pretrained models have no idea what books you’ve read this year. To solve for this, you’ll want to leverage retrieval-augmentation, i.e. “providing relevant information to the model from an existing data store”. The data store may be a SQL Database, a lookup table, or a vector database, but ultimately the important component here is that somehow from your request, you’re able to find, and then provide relevant information to an Agent.

One assumption we’ve made here, is that your request is interpretable by your retrieval system. In the above example, you’d like the system to automatically understand the “which of the books I read this year” as an information retrieval task equivalent to something like

SELECT * FROM read_books
WHERE CAST(finished_date, YEAR) = CAST(today(), YEAR)

Here I’ve just made up a SQL database, but you can imagine schema to satisfy this request. Converting from the request to this SQL is now yet another task you need to model – maybe it’s the job of another Agent request.

In other contexts, you actually want a full scale recommender to help with the retrieval: if you want users to ask an agent for a movie tonight, but if you want to continue to use your deep understanding of their taste, you may first filter the potential movies by the user’s preference, and then only send movies your recommender model think are great for them. The Agent can then service the text request from a subset of movies that are already determined to be great.

The intersection of LLMs and Recommendation Systems is going to dominate much of the conversation in Recommendation Systems for a while. There’s a lot of low-hanging fruit in bringing the knowledge of recommender systems to this new industry. As Eugene Yan quoted recently:

I think the key challenge, and solution, is getting them [LLMs] the right information at the right time. Having a well-organized document store can help. And by using a hybrid of keyword and semantic search, we can accurately retrieve the context that LLMs need.

Wilfred Meynell