ContextGNN: Beyond Two-Tower Recommendation Systems

Thank you for your review. Please refer to our general answer which addresses your concerns regarding more advanced baselines beyond NGCF. We have also uploaded our code base to ensure reproducibility of the presented results: https://anonymous.4open.science/r/ContextGNN-DBCA/README.md.

GNN backbone design: In order to disentangle performance improvements of the overarching model architecture from the GNN backbone, we use the same GNN backbone as introduced in RelBench [1], which operates on historical, temporal-aware subgraphs which are sampled on-the-fly during training and evaluation. The GNN backbone takes in raw multi-modal input features across different types (numerical, categorical, multi-categorical, text, absolute time, relative time, etc), encodes them into a shared embedding space, and then uses a heterogeneous GNN to perform message passing on top. In particular, we use a heterogeneous version of the GraphSAGE model with sum-based neighbor aggregation.

[1] Robinson et al.: RelBench: A Benchmark for Deep Learning on Relational Databases (2024)

Thank you for your review. Please refer to our general answer for additional baselines/experiments, and the requested efficiency/scalability studies. In summary, we conducted additional experiments on next-item prediction and static link prediction. We find that ContextGNN outperforms sequential recommendation models and is on par to static link prediction models on small-scale datasets. Additionally, we want to highlight that our end-to-end architecture is designed to be scalable and efficient. Our hybrid model is combined in such a way to have minimal overhead compared to the two components in isolation since the vast majority of the model parts are shared between the two paradigms.

We have also uploaded our code base to ensure reproducibility of the presented results: https://anonymous.4open.science/r/ContextGNN-DBCA/README.md. Our code also highlights our technical contributions such as our sampled softmax procedure, the fusion of ranking scores obtained from (approximated) k-NN/MIPS search with ranking scores coming from items in the user’s local subgraph, and the integration of bidirectional sampling in order to ensure that the readout of item nodes is well-defined in a user-centric subgraph.

Time complexity: Given that the time complexity of a standard two-tower GNN is $\mathcal{O}(|\mathcal{E}|)$, the total time complexity of our model is $\mathcal{O}(|\mathcal{E}| + |\mathcal{V} \cap \mathcal{R}| + |\mathcal{N}|)$, where $\mathcal{V} \cap \mathcal{R}$ refers to the items within a user’s subgraph and $\mathcal{N}$ refers to the set of negative samples.

In contrast, a standard two-tower GNN needs to be executed on the user, the positive item and the set of negative items $\mathcal{N}$, ending with a much higher time complexity of $\mathcal{O}((2 + |\mathcal{N}|) * |\mathcal{E}|)$. This fundamental difference is also observed in measured runtimes, where ContextGNN is 3 to 5 times faster.

Thank you for your review. Please refer to our general answer which shows the application of ContextGNN in other domains (i.e., static link prediction, next-item recommendation). We have also uploaded our code base to ensure reproducibility of the presented results: https://anonymous.4open.science/r/ContextGNN-DBCA/README.md. Please note that we only report MAP on RelBench [1] datasets since this is the recommended metric on this benchmark suite. In our additional experimentation, we report other metrics as well (e.g., HitRate@K, Recall@K, NDCG@k).

We have checked all formulas in our paper multiple times, but cannot find any error in these. We kindly ask you to provide the equation which has an error.

Parameter Sensitivity Analysis: We found ContextGNN to be very stable across different hyper-parameters, and thus we only tune three parameters in total: number of hidden units, batch size and learning rate. It is important to note that model performance has overall low variance across these different parameters: For example, on the user-item-purchase task on rel-amazon, the model performance across different hyperparameters ranges from 2.63 to 2.71.

Sparse User-Behavior: ContextGNN overcomes sparse user behavior via its two-tower model. In particular, most/all of the recommendations for cold-start users will stem from the two-tower fallback model since the local interaction graph is sparse. This again proves the importance of a hybrid architecture, since cold start users cannot properly be addressed by pair-wise representations, but two-tower models are too general for richer interaction graphs. ContextGNN finds a nice balance to accommodate different types of users into a robust and single architecture.

[1] Robinson et al.: RelBench: A Benchmark for Deep Learning on Relational Databases (2024)

Thank you for your review. Please refer to our general answer which addresses all your concerns regarding novelty, dataset scale, and comparison to more advanced recommendation baselines. In summary, we conducted additional experiments on next-item prediction and static link prediction. We find that ContextGNN outperforms sequential recommendation models and is on par to static link prediction models on small-scale datasets.

Related Work: Thanks for the feedback. We will improve the related work in our revised manuscript. Previously, GNN-based RecSys models have been mostly applied in the static bipartite graph setting (ignoring node features, frequency, seasonality, multi-behavioral interactions, etc) on small-scale datasets only. From NGCF onwards, research has focused on (1) simplifying models (LightGCN [1], Ultra-GCN [2], etc) or by adding self-supervision (e.g., based on contrastive learning via graph augmentations) to improve performance on these small-scale datasets [3, 4, 5]. These findings are orthogonal to our work, but still embrace a two-tower architecture under the hood. The line of work that comes closest to ContextGNN is related to encoding identity- and position-awareness into GNNs in order to relate user-item pairs [6, 7, 8, 9]. However, these methods face scalability challenges as they require a candidate set in advance. ContextGNN builds a trade-off between these two paradigms by bringing scalability and fallback logic into pair-wise embedding models in an elegant way.

Technical Contributions: In order to disentangle performance improvements of the overarching model architecture from the GNN backbone, we use the same GNN backbone as introduced in RelBench [10], which operates on historical, temporal-aware subgraphs which are sampled on-the-fly during training and evaluation. The GNN backbone takes in raw multi-modal input features across different types (numerical, categorical, multi-categorical, text, absolute time, relative time, etc), encodes them into a shared embedding space, and then uses a heterogeneous GNN to perform message passing on top. On the training/inference procedure side, technical contributions include the integration of a sampled softmax procedure, the fusion of ranking scores obtained from (approximated) k-NN/MIPS search with ranking scores coming from items in the user’s local subgraph, and the integration of bidirectional sampling in order to ensure that the readout of item nodes is well-defined in a user-centric subgraph. Our entire implementation is written to account for mini-batches of different sizes in a vectorized and GPU-accelerated manner. We have uploaded our code base to also show these technical contributions: https://anonymous.4open.science/r/ContextGNN-DBCA/README.md.

[1] He et al.: LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation (2020)

[2] Mao et al.: UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation (2021)

[3] Yu et al.: Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation (2022)

[4] Wu et al.: Self-supervised Graph Learning for Recommendation (2021)

[5] Cai et al.: LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation (2023)

[6] You et al.: Identity-aware Graph Neural Networks (2021)

[7] You et al.: Position-aware Graph Neural Networks (2019)

[8] Zhu et al.: Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction (2021)

[9] Zhang et al.: Link Prediction Based on Graph Neural Networks (2018)

[10] Robinson et al.: RelBench: A Benchmark for Deep Learning on Relational Databases (2024)

Thank you for the response.

Thank you very much for your review and your positive feedback. Please refer to our general answer for additional baselines/experiments, and efficiency/scalability studies.

As you correctly pointed out, the locality study reveals that a vast majority of ground-truth items are not part of a user’s local subgraph, and hence are not aggregated into its user representation. Still, the user representation holds valuable information about past interactions and collaborative signals. However, ContextGNN falls back to the two-tower model in order to compute a ranking score for these “distant” items. The key idea is that the model learns to give more weight to the two-tower part in case such long-range/exploratory interactions frequently happen in the dataset, either on a per-user basis or on a global level. In practice, it is often not feasible to leverage more than 3-hops when using subgraph sampling approaches, and deeper GNNs are limited to full-batch processing on smaller-scale datasets. We still use recent tricks such as skip-connections to mitigate the effects of oversmoothing in our GNN backbone.

Efficiency: Reviewer U3kG requested an additional efficiency study. We want to highlight that our end-to-end architecture is designed with scalability and efficiency in mind. Our hybrid model is combined in such a way to have minimal overhead compared to the two components in isolation since the vast majority of the model parts are shared between the two paradigms. To verify, we report the runtime in seconds to reach 1000 optimization steps across different models:

| Model                        | rel-hm | rel-stack |
| GraphSAGE (1 negative)       |   275s |       37s |
| GraphSAGE (10 negatives)     |   293s |       44s |
| GraphSAGE (100 negatives)    |    OOM |       OOM |
| Pair-wise Part (NBFNet)      |    77s |       21s |
| Two-tower Part (ShallowItem) |    92s |       22s |
| ContextGNN (200k negatives)  |    94s |       23s |

Most importantly, since ContextGNN only requires user GNN embeddings in its two-tower part, it is faster compared to any two-tower GNN by a very significant factor (i.e., a two-tower GNN such as GraphSAGE requires to run the GNN on both positive and negative items). In particular, two-tower GNNs scale very poorly when increasing the number of negative samples to train against. For training recommendation systems, a large number of negative examples is important to allow learning of discriminative features (see below for a quantitative analysis). However, In the simplest case (one negative pair per positive pair), a two-tower GNN needs to be executed three times already. ContextGNN does not have this limitation and can consider up to 1M negatives before running into GPU memory limitations.

Scalability: Reviewer U3kG requested an additional scalability study. ContextGNN is very scalable and is evaluated across a diverse range from medium to large-scale datasets, which outpass commonly used datasets such as Gowalla (29k users/40k items), Yelp2018 (31k users/38k items), and Amazon-Book (52k users/91k items) by a large factor:

|   Dataset  | #Nodes |
| rel-amazon |    15M |
| rel-avito  |    21M |
| rel-event  |    41M |
| rel-hm     |    16M |
| rel-stack  |     4M |
| rel-trial  |     5M |

In order to scale the shallow embedding part of ContextGNN, we make use of a sampled softmax formulation, which allows us to scale to up to 1M negative samples on commodity GPUs (15GB of memory). For this, we report model performance and runtime when sweeping over the number of negatives:

| Number of negatives |      rel-hm     | rel-trial (sponsor) |
|                     |  MAP  | Runtime |    MAP   |  Runtime |
|                  10 |  1.36 |     77s |     18.0 |     421s |
|                 100 |  2.00 |     77s |     19.6 |     423s |
|               1,000 |  2.35 |     78s |     22.4 |     425s |
|              10,000 |  2.70 |     82s |     26.8 |     426s |
|             100,000 |  2.93 |     93s |     26.9 |     427s |

We found that increasing the corpus of negative samples increases final model performance at the expense of a small bit of runtime. This intuitively makes sense, as just a small number of uniformly sampled negatives may not sufficiently differentiate between positive examples and challenging negative counterparts. In practice, we use the largest number of negative samples possible without running into GPU memory limitations.

[1] Wang et al.: Neural Graph Collaborative Filtering (2020)

[2] He et al.: LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation (2020)

[3] Mao et al.: UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation (2021)

[4] Yu et al.: Are Graph Augmentations Necessary?: Simple Graph Contrastive Learning for Recommendation (2022)

[5] Wu et al.: Self-supervised Graph Learning for Recommendation (2021)

[6] Cai et al.: LightGCL: Simple Yet Effective Graph Contrastive Learning for Recommendation (2023)

[7] Xia et al.: Multi-Behavior Sequential Recommendation with Temporal Graph Transformer (2022)

[8] Robinson et al.: RelBench: A Benchmark for Deep Learning on Relational Databases (2024)

Additional Experiments: Reviewers requested additional experiments with alternative baselines (GUBd, uwX2, U3kG and 7mVo) and alternative datasets (pueu). While we want to point out that we already evaluate ContextGNN on 8 different tasks, and it is non-trivial to transfer related work to the RelBench [8] setting, we agree that this is a great suggestion. As such, we conducted two more lines of experiments to further strengthen our experimental evaluation:

We use ContextGNN to perform temporal next-item recommendation on the ICJAI Contest dataset [7], which is a common dataset utilized to evaluate sequential recommendation models (Bert4Rec, TGT et al.). As per evaluation protocol, we report HitRate@k and NDCG@k over 99 sampled negatives per entity (random HitRate@10 performance =0.1):

| Model      |  HR@1 |  HR@5 | NDCG@5 | HR@10 | NDCG@10 |
| DeepFM     | 0.138 | 0.332 |  0.244 | 0.469 |   0.290 |
| Bert4Rec   | 0.141 | 0.356 |  0.261 | 0.467 |   0.297 |
| Chorus     | 0.140 | 0.345 |  0.247 | 0.457 |   0.283 |
| HyRec      | 0.137 | 0.323 |  0.229 | 0.442 |   0.266 |
| NMTR       | 0.141 | 0.360 |  0.254 | 0.481 |   0.304 |
| MATN       | 0.142 | 0.375 |  0.273 | 0.489 |   0.309 |
| MBGCN      | 0.137 | 0.332 |  0.228 | 0.463 |   0.277 |
| TGT        | 0.148 | 0.399 |  0.293 | 0.519 |   0.330 |
| ContextGNN | 0.411 | 0.603 |  0.513 | 0.667 |   0.534 |

We observe that ContextGNN is able to out-perform all baselines on all metrics on this task (e.g., ~170% improvement on HitRate@1).

Reviewers also requested comparison to GNN-based RecSys models such as LightGCN, Ultra-GCN, etc. Although our main focus in ContextGNN is on mid to large-scale real-world use-cases which are temporal and heterogeneous, we additionally evaluate ContextGNN on the well-known static link prediction task in Amazon-Books, which is a small-scale dataset that does not come with input features, only considers users with at least ten interactions, and evaluates on 10% randomly selected interactions independent of time.

| Model      | Recall@20 | NDCG@20 |
| NGCF       |    0.0337 |  0.0261 |
| LightGCN   |    0.0410 |  0.0318 |
| Ultra-GCN  |    0.0681 |  0.0556 |
| LightGCL   |    0.0585 |  0.0436 |
| SimGCL     |    0.0478 |  0.0379 |
| SGL        |    0.0468 |  0.0371 |
| ContextGNN |    0.0451 |  0.0377 |

We can see that ContextGNN is able to outperform both NGCF and LightGCN, while it is slightly underperforming compared to, e.g., Ultra-GCN or LightGCL. Given the relatively small size of this dataset, much of the progress in GNN-based recommendation systems has centered on two key directions: (1) simplifying GNN architectures, as seen in the progression from NGCF to LightGCN and Ultra-GCN, and (2) incorporating self-supervised learning techniques, such as SimGCL, SGL, and LightGCL, to enhance the learning signal. Note that we did not make any modifications to our GraphSAGE-like GNN backbone nor do we introduce complex self-supervision pipelines, yet we achieve superior performance compared to both NGCF and LightGCN on this task. Exploring how ContextGNN can benefit from a more lightweight GNN backbone or complementary learning signals, akin to those in SimGCL, SGL, or LightGCL, presents an exciting direction for future research.

Thank you very much!