EDGE-Rec: Efficient and Data-Guided Edge Diffusion For Recommender Systems Graphs

Denoising diffusion models (Ho et al., 2020) form a prominent class of models that have proven remarkably effective across a variety of generation and sampling tasks where the data distribution is high-dimensional, such as video, image synthesis and graph generation (Liu et al., 2023). However, generative modeling of graphs has historically focused on smaller graphs for applications such as molecule generation (Vignac et al., 2023; Liu et al., 2023). Recent work involving graph generation with diffusion models show promising results for reconstructing large undirected graphs with thousands of nodes (Wang et al., 2023; Bergmeister et al., 2024). Prior work also presents promising results with guided denoising steps incorporating score functions to evaluate graphs generated during denoising (Jo et al., 2022).

Recommendation systems focus on using historical user-item interaction data (such as reviews) to predict/recommend new items for users. Previous research in this space applies diffusion models to augment sparse data, model user dynamics/preference distributions, model item latent distributions, or perform sequential recommendation (Wang et al., 2023; Yang et al., 2023; Ma et al., 2024). In contrast to prior research in diffusion-based recommendation systems, we aim to construct a recommender system based on graph diffusion models by formulating the problem as a graph completion task. We focus primarily on the graph structure of the user-item interaction space.

Our proposed method involves representing historical user-item interactions as edges between nodes in a bipartite graph with real-valued edge weights. These weights can represent the strength of these interactions (e.g. a rating out of 5). We also utilize latent space representations of users and items to condition the denoising process for the prediction of new interaction links (recommendations). In recommendation systems, the set of users and items (as well as their attributes) is fixed, so we focus on noising edge attributes of the interaction graph such as the adjacency matrix and edge weights in a continuous manner. Additionally, since recommender systems graphs are bipartite, we can represent the edge weights between users and items in a weighted interaction matrix, forming a 2D array similar to an image where each pixel represents the corresponding interaction strength between a user and item.

To the best of our knowledge, our work is the first to consider the interaction graph in a recommender system with both node features (per user and item) and the strength of interactions as edge weights. By conditioning on node features in the denoising model, we are able to guide the diffusion of weights over all possible interaction edges in the graph to approximate the expected interaction strengths.

In the traditional formulation of denoising diffusion models (Ho et al., 2020), the forward diffusion process gradually adds Gaussian noise to the original data, $\mathbf{x}_{0}\sim q(\mathbf{x})$, over $T$ diffusion steps to reach random Gaussian noise, $\mathbf{x}_{T}\sim\mathcal{N}(0,\mathbf{I})$. Each diffusion step corrupts the noised representation from the previous step:

Where $\{\beta_{t}\}_{t=1}^{T}$ are the noise-schedule hyper-parameters controlling the amount of noise added at each step. Note $\beta_{t}\in(0,1)$.

Ho et al. (2020) also provide the analytical form for $\mathbf{x}_{t}$ given $\mathbf{x}_{0}$:

Where $\alpha_{t}=1-\beta_{t}$ and $\widebar{\alpha}_{t}=\Pi_{i=1}^{t}\alpha_{i}$. This enables any arbitrary step of the diffusion process to be generated extremely quickly for any given $\mathbf{x}_{0}\sim q(\mathbf{x})$, simply by sampling $\epsilon\sim\mathcal{N}(0,\mathbf{I})$. The diffusion steps can be tuned by choosing an appropriate set of $\{\beta_{t}\}_{t=1}^{T}$.

The reverse diffusion process aims to gradually recover the original data $\mathbf{x}_{0}$ given the fully corrupted $\mathbf{x}_{T}$. Ho et al. (2020) show that the posterior Gaussian, $p(\mathbf{x}_{t-1}|\mathbf{x}_{t},\mathbf{x}_{0})$, is tractable (when conditioned on $\mathbf{x}_{0}$) and has the analytical form:

Above, the conditioning on $\mathbf{x}_{0}$ is necessary for the posterior to be tractable. The primary goal of a diffusion model is to learn the initial distribution such that arbitrary Gaussian noise can be gradually denoised to produce outputs from the original input data distribution $q(\mathbf{x})$. Without conditioning on $x_{0}$, we need:

The model, parameterized by $\theta$, is trained to approximate either the mean, $\mu_{\theta}$, and variance, $\Sigma_{\theta}$, or to predict the added noise, $\epsilon$. Generally, the latter approach has lower variance and this parameterization more closely resembles Langevin dynamics with a loss that resembles the denoising score matching objective (Ho et al., 2020):

where $\epsilon_{\theta}(\cdot)$ is the noise predicted by the model. We use this vanilla diffusion approach over the space of weighted interaction matrices (applying isotropic noise in the forward steps, and training our GDiT architecture to predict the added noise in the reverse process). Inspired by text-conditioned image-generation methods (Rombach et al., 2022), our approach also conditions on user features, $\mathcal{U}$, as well as item features, $\mathcal{I}$, such that the model predicts $\epsilon_{\theta}(\mathbf{x}_{t},t,\mathcal{U},\mathcal{I})$ and learns the posterior distribution $p_{\theta}(\mathbf{x}_{t-1}|\mathbf{x}_{t},\mathcal{U},\mathcal{I})$.

We take inspiration from the notion of “active node” sampling in the interaction graph from EDGE (Wang et al., 2023), thus enforcing the same mechanism of scalable local diffusion. Below, we highlight some key differences between our method and prior works.

1. (1)

   Sets of active nodes are sampled a priori and kept fixed throughout the diffusion. This means that our diffusion process is defined on the space of $n\times m$ sub-matrices (called “patches”), whose values represent all ratings in a sub-sample of $n$ users and $m$ items from the dataset. During training this translates to a batch of $n\times m$ interaction matrix patches which are corrupted in the forward process. The model is trained to predict the added noise within these patches given the corrupted data, time-step, and feature information for the $n$ users and $m$ items within each patch.

2. (2)

   For all user-item pairs within a sampled $n\times m$ patch, we consider real-valued interaction strengths as opposed to binary interactions (e.g. ratings from 1-5 for the MovieLens datasets (Harper and Konstan, 2015)). This makes the task more difficult but at the same time closer to applications of recommendation systems. The interaction strengths are mapped to the continuous interval $[-1,1]$, with $0$ representing a neutral interaction, and positive and negative values corresponding to favorable and unfavorable interactions, respectively.

3. (3)

   With a large (and dense) enough dataset it is reasonable to assume that the distribution of these interaction strengths will be roughly Gaussian, or can easily be transformed to a standard Gaussian in an invertible manner, such as with a quantile transformation. This motivates the usage of the vanilla diffusion method over the space of (transformed) weighted interaction matrices.

4. (4)

   In contrast to EDGE, we noise all edges within a patch at the same time, without employing additional selection at each step. This is made computationally feasible by the a priori subsampling of the active edges, which makes each subsample of size significantly smaller than the entire graph.

5. (5)

   In contrast to DiffRec, we contract the weights of the interaction graph edges to be samples from a standard Gaussian distribution. While DiffRec stops the forward process at some partially-noised time-step to encode historical interaction information as a latent prior, we hope to remove this requirement by conditioning on user and item features, enabling generation by sampling directly from random noise.

We train and evaluate our proposed method, EDGE-Rec, on the MovieLens datasets ML-100k and ML-1M (Harper and Konstan, 2015). Evaluation is performed using a set of standard metrics for recommendation systems based on the top-$K$ predictions from the model. We train each model for at least 10000 iterations with a batch size of 16 and patch size at least $50\times 50$. We construct a custom time-aware 90-10 train-test split of the edges to ensure consequentiality and the absence of overlap in the time ranges covered by training and validation split.

Training consists of sampling random patches of specified size $n\times m$ from the target graph. Uniform random sampling of the full weighted interaction matrix over at least 10000 iterations allows most if not all of the users and items to be included during training. The model is provided patches corrupted to uniformly sampled time-steps, the time-steps each patch is noised to, and user-item features for each patch. Unknown interactions are optionally masked, and, if a user has not interacted with an item, the expected or true interaction strength is set to 0 (neutral).

Finally, we train the GDiT model by maximizing the usual denoising formulation of the ELBO objective, which we regularize at the single step level using Bayesian Personalized Ranking loss (Rendle et al., 2012) to encourage coherent rankings. At sampling time, we reconstruct patches of ratings from random noise. Notably, given a patch we have access to the known training edges, which precede the test edge edges. This allows to frame the sampling problem as a matrix completion problem. Inspired from inpainting techniques for image completion (Lugmayr et al., 2022), we replace the known portion of the patch with the known noised ratings from the training set to further condition the generation on the a priori information and ecourage accurate generation of new ratings that “complete” the already-available ones. These candidates are discarded at test time.

We also propose a new method of denoising larger subgraphs by randomly tiling the encompassing subgraph with smaller patches at each reverse-diffusion step. As a result, the entire interaction matrix is denoised uniformly during the sampling process, instead of independently as when patches are naively denoised sequentially.

Figures 7 and 8 depict plots for the chosen suite of evaluation metrics for various top-K values. In particular, note that EDGE-Rec surpasses DiffRec baselines (included in Appendix A) for most patch sampling tasks on edge densities above around $55\%$ (in terms of known interactions). Additionally, we observe that scaling up denoising sampling using our novel tiling method does not significantly degrade recommendations, with sufficient subgraph density.

We propose a graph-diffusion-based recommendation model that predicts continuous interaction strengths. Building on advancements in conditioned diffusion models, we generate recommendations by conditioning on user and item features. By tuning the size of the patch, our model shows promising performance, despite the patch size being two orders of magnitude smaller than the complete graph. Assuming one can identify dense patches of the graph with high accuracy, this makes the training process highly scalable in the number of users and items. However, in highly sparse production-level environments, identifying such patches can be a challenge, as it essentially reduces to the retrieval problem. This makes the assumption of a dense patch size particularly strong and a clear limitation of the method. If available, future work could pair this ranking methodology with a trained retrieval model that produces high-density patches of candidate user-item pairs.