A Geometric Approach to Personalized Recommendation with Set-Theoretic Constraints Using Box Embeddings

Authors: Shib Sankar Dasgupta, Michael Boratko, Andrew McCallum
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: Box Embeddings, Personalized Query, Set-based embeddings, Recommendation

Abstract:
Personalized item recommendation typically suffers from data sparsity, which is most often addressed by learning vector representations of users and items via low-rank matrix factorization. While this effectively densifies the matrix by assuming users and movies can be represented by linearly dependent latent features, it does not capture more complicated interactions. For example, vector representations struggle with set-theoretic relationships, such as negation and intersection, e.g. recommending a movie that is “comedy and action, but not romance”. In this work, we formulate the problem of personalized item recommendation as matrix completion where rows are set-theoretically dependent. To capture this set-theoretic dependence we represent each user and attribute by a hyperrectangle or box (i.e. a Cartesian product of intervals). Box embeddings can intuitively be understood as trainable Venn diagrams, and thus not only inherently represent similarity (via the Jaccard index), but also naturally and faithfully support arbitrary set-theoretic relationships. Queries involving set-theoretic constraints can be efficiently computed directly on the embedding space by performing geometric operations on the representations. We empirically demonstrate the superiority of box embeddings over vector-based neural methods on both simple and complex item recommendation queries by up to 30% overall.

Decision: reject
Reviewer scores: 5, 3, 5

Reviews and discussion:
<thread>
creation date:
1730375528598

thread_type:
official_review

<thread_object>
creator: reviewer_tc3c

<content>
summary:
This work addresses the task of personalized recommendation using set-theoretic queries. The authors frame this problem as "set-theoretic matrix completion," highlighting that traditional approaches, such as logistic matrix factorization, do not align with the set-theoretic operations needed during inference.

strengths:
1.	The study models attribute-specific query recommendation as "set-theoretic matrix completion," treating attributes and users as item sets.
2.	The paper effectively demonstrates the limitations of existing vector embedding models for this specific task.
3.	Experimental results validate the effectiveness of the proposed model.

weaknesses:
1.	The approach presented in this paper conflicts with the widely used matrix factorization model, which effectively leverages collaborative filtering signals between users and items. It is unclear how the proposed model addresses these signals.
2.	The experimental baselines are not state-of-the-art; comparing the proposed method to more advanced recommendation models would better demonstrate its advantages.
3.	Some equations are difficult to follow due to unclear notation explanations.

questions:
It is suggested that an efficiency comparison between the traditional vector embedding methods and the proposed box embedding method be discussed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730521163960

thread_type:
official_review

<thread_object>
creator: reviewer_6wmm

<content>
summary:
The authors apply box embedding to attribute-specific query recommendation.
They formulated the task of attribute-specific query recommendation and proposed a recommendation method based on box embedding for the task.
The authors also tried establishing an evaluation protocol for this new task and provided detailed analyses based on generalization spectrum gap and compound error.
On the other hand, the current manuscript severely lacks a discussion of existing recommendation fields (e.g., context-aware recommendation), and the technical novelty is unclear.

strengths:
1. The authors tried to use the latest technique in the NLP field (i.e., box embedding) for a recommendation-related task. 
2. The authors have carefully designed an evaluation protocol for attribute-specific query recommendation based on traditional collaborative filtering.

weaknesses:
1. The scope of this study is on a rather limited application, which the authors called "attribute-specific query recommendation".
2. The current manuscript lacks related work on "attribute-specific query recommendation". In addition, the authors should discuss the relationship between this study and context-aware recommender systems [a].
3. Some experimental settings are not convincing. See the following questions/comments for details.

### References
[a] Adomavicius, Gediminas, and Alexander Tuzhilin. "Context-aware recommender systems." Handbook of Recommender Systems. Boston, MA: Springer US, 2010. 217-253.

questions:
### Questions
  - (Q1) The authors used nDCG@K for model selection, but evaluated the final performance based on HR@K. Why did the authors use inconsistent metrics for validation and testing? In my opinion, HR@K with 100 negative items is a rather insensitive measure for ranking evaluation. I would like to recommend using Recall@K without negative sampling.
  - (Q2) In the current manuscript, the authors do not mention/discuss the result on MovieLens-20M (Table 7 in Appendix B.3). Also, Table 7 is not self-contained. What is the definition of VEC-*? (probably MF or NeuMF?)
 
### Comments.
   - (C1) To my understanding, "attribute-specific query recommendation" is the task where (1) item attribute values are partially observed and often missing, and (2) in the prediction phase, the positive items are conditioned not only on a user but also on a boolean query. The problem of (1) has been addressed in existing studies (e.g., [b,c]). I am not familiar with (2) in the context of item recommendation, but there might be existing research on it.  A discussion/comparison of existing studies on these points would make it easier to understand the novelty of this work.
   - (C2) In line 368, the authors report that they followed the standard sample scoring procedure described in Rendle et al. (2020). However, to my understanding, using this sampling technique is not recommended for a dataset with a small item catalog such as Last-FM, MovieLens-1M, NYC-R. It may just undermine the reliability of the reported results to reduce a small experimental cost.


## References

 [b] Wu, Le, et al. "Joint item recommendation and attribute inference: An adaptive graph convolutional network approach." Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval. 2020.

 [c] Xian, Yikun, et al. "Ex3: Explainable attribute-aware item-set recommendations." Proceedings of the 15th ACM Conference on Recommender Systems. 2021.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730528432349

thread_type:
official_review

<thread_object>
creator: reviewer_vvma

<content>
summary:
This paper proposes using box embeddings for matrix completion to improve personalized item recommendation with set-theoretic queries. Box embeddings are employed to bypass the limitation of commonly used vector embeddings, which might fail to recommend items for set-theoretic queries consisting of negotiation and intersection relationships. By representing users, items. and attributes as box embeddings, i.e., hyper rectangles in d-dimensional space, the proposed approach can jointly factorize user-item interaction matrix and item-attribute matrix. Then, users and attributes are regarded as boxes containing multiple items. As such, given a query containing set relationships between attributes, the model retrieves top items having the largest box volume shared with those of users as recommendation list. The whole model is trained to capture containing relationships, i.e., user and attribute boxes contain multiple item boxes. Experimental results on four datasets demonstrate the strong performance of the proposed method.

strengths:
1. The paper studies an interesting yet not well explored problem: personalized item recommendation with set-theoretic queries. The set nature of queries, which consists of set relationships such as negotiation and intersection, leads to an interesting research question: how to capture such relationships to make more accurate recommendations.

2. The employment of box embeddings to represent users, items, and attributes is intuitive and sensible to capture set relationships between these three.

3. Experimental results on four real-world datasets demonstrate good performance of the proposed box embedding method, outperforming vector embedding approaches.

4. The paper is well-structured and easy to follow.

weaknesses:
1. Despite showing promising recommendation results, the proposed method seems to be a direct application of box embeddings for personalized item recommendation with set theoretic queries, which is somehow a limited contribution.

2. The paper relies heavily on the theory of box embeddings but some key concepts were not described sufficiently. For example, in line 191, how to guarantee $x^\llcorner < x^\urcorner$ for all dimensions $d$; what is the definition of $VolIntGB$ in Equation 3?; what are the parameters of the model to optimize?

3. The baselines are somewhat limited. Although authors already mentioned in Section 2.1., representative baselines such as LightGCN [1] and MultiVAE [2] were not considered. Including more recent and advanced baselines will further ascertain the strength of the proposed method.

[1] He et al. Lightgcn: Simplifying and powering graph convolution network for recommendation. SIGIR 2020.
[2] Liang et al. Variational autoencoders for collaborative filtering. WWW 2018.

4. Lack of efficiency analysis. What is the advantage of using box embeddings over vector embedding w.r.t. running time?

5. Missing descriptions of some important experimental settings, e.g., how many negative sampled required to train Equations in lines 233 and 240. Moreover, ablative analysis of key hyper-parameters is also not presented. For instance, how the number of negative samples affect the model accuracy? The same questions for $w$ in line 240.

questions:
The paper introduces the notation of query in the context of recommendation systems. What is the difference between query in the context of this paper and query in the context of search engine like Google?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731950285791

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Thanking the Reviewers

comment:
We sincerely thank the reviewers for their time and thoughtful, constructive feedback. In this rebuttal, we humbly take this opportunity to address their concerns and questions regarding the related work and experimental setup, aiming to clarify the scope of our work and provide a more detailed explanation of the notations used.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731950454361

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response - Scope of our work

comment:
This general response is intended to address the questions regarding the scope of our work raised by the reviewers, and we will respond to specific questions or concerns in their respective rebuttal sections separately. We kindly request the reviewers to read the general response before reviewing our answers to the specific questions.

---


**Scope of the Work**

The task of constrained recommendation is both significant and broadly applicable in real-life scenarios, as it enables recommendation systems to meet specific and nuanced user preferences. For instance, on Netflix, a user might search for dark-comedy movies. While Netflix could broadly suggest dark-comedy films, the recommendations need to align with the user's individual interpretation of the genre. For example, one user might consider *Fargo* a dark-comedy movie, while another may not. Similarly, on Spotify, a user might be interested in exploring jazz music, but explicitly condition on excluding smooth jazz from the suggestions. On Yelp, two users might query "Italian place with free parking." A well-designed system should adapt to their distinct preferences, recommending a casual pizzeria to one user and a fine-dining Italian restaurant to the other, based on their past behavior.

At its core, even a simple attribute query, such as “Italian restaurants,” can be seen as a set-theoretic query—a conjunction between the restaurants aligning with the user's preferences and the set of Italian restaurants. As queries grow more complex, involving logical combinations of attributes, the recommendation task becomes increasingly challenging. Such scenarios are common in real-world applications, underscoring the need for recommendation systems that can interpret and satisfy these explicit set-theoretic constraints while still personalizing results to individual tastes.

While traditional recommendation systems are well-explored, they generally fall short in addressing queries that involve attributes and their logical combinations. This limitation restricts their ability to solve practical tasks where such constraints are often integral to user needs.

Our work introduces a novel framework that bridges this gap, enabling recommendation systems to effectively manage set-theoretic queries across multiple practical domains. By addressing this critical challenge, we aim to extend the functionality of recommendation systems to better meet nuanced user needs.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732430989202

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Updates in the Revised Draft

comment:
We sincerely thank the reviewers for their valuable feedback, which has greatly helped us improve our draft by incorporating stronger baselines to support our claims, enhancing the clarity of notations and experimental setup, adding a detailed discussion on time efficiency, and better positioning our work within the context of related research.

The revisions are highlighted (in **blue**) throughout the paper. Key updates are as follows:

1. **Performance of Light-GCN (Table 4)**:
    - The main results table (Table 4) has been updated to include the performance metrics for Light-GCN.
    - Relative performance trends remain consistent with previous findings.
2. **Notation Section (Sections 3.1 and 3.2)**:
    - Simplified and clarified the notations, making them more intuitive and aligned with the problem setup.
    - Included missing definitions for terms such as `Volnt`, `Vol`, `VolInt_GB`, and others to enhance readability.
3. **Updated Related Work (Appendix A.2 and A.4)**:
    - Expanded and refined discussions in the related work sections to address reviewer concerns.
    - Added sections on context-aware recommendation and set-theoretic queries in search.
4. **Time Efficiency Analysis (Appendix D)**:
    - Discussed the computational efficiency of box embeddings, highlighting their scalability and parallelizability.
    - Highlighted that box embeddings offer computational complexity similar to simple vector-based methods, significantly faster than complex methods like LightGCN.
5. **Highlighted Training Details**:
    - Explicitly detailed training procedures, including the number of negative samples used, model selection protocols, and final scoring evaluation strategy. (
    - Added a parallel coordinates plot to visualize hyperparameter choices and their impact on performance (Appendix B.2, Figure 2.)
    - Added missing experiments on NeuMF on ML20m dataset. (Table 7., appendix B.3)

The draft aims to address the specific concerns raised by reviewers and improve overall clarity and completeness. 

We humbly request further feedback from the reviewers!
</content>
</thread_object>

</thread>


Metareview: