# Social)GCF: Social Recommendation with Jacobi Polynomial-Based Graph Collaborative Filtering
## 2 Problem and Related Work  
### Problem Statement  
Recommendation problems focus on analyzing users' interest in specific items from their past interactions with items. These interactions can be either quantified explicitly by ratings given by users (e.g., like and dislike for YouTube videos or stars in Amazon customer reviews) or only shown implicitly (e.g., users' clicks on some products on Amazon). In the former case, the rating matrix can be used to represent user-item interaction, and, in the latter case, the implicit feedback data can be converted to explicit ratings.  
Recently, many methods have been proposed for recommender systems based on user-item interaction graphs [19; 20; 26; 27; 28; 29; 30]. LightGCN simplifies graph convolution by only including neighborhood aggregation [19]. Simple Graph Contrastive Learning (SimGCL) combines contrastive learning with LightGCN to mitigate popularity bias [26]. Jacobi-Polynomial-Based Graph Collaborative Filtering (JGCF) uses Jacobi polynomial bases to approximate a LightGCN-based filter from a spectral transformation view [27].  
However, practically, each user only interacts with a small subset of available items, which results in a highly sparse rating matrix, making the recommendation problem hard to solve. One common strategy to mitigate the data sparsity problem is to enrich the representation by the integration of supplementary information such as item-item relationships and user-user relationships. In many open datasets, relationships between items are not explicitly defined, but rather inferred from their co-occurrence in previous interactions [9; 31]. This method of constructing relationships can compromise the effectiveness of the recommender system if not thoughtfully implemented. Conversely, the user-user relationship data are readily accessible due to the growth of social media platforms.  
Social influence theory indicates that people are likely to be influenced by their connections and perform similar actions. Therefore, users' social relationships can be incorporated into recommendation systems to enhance performance, which is the focus of social recommendation problems.  
Cold-start problems are a critical challenge in recommender systems, where new users or items have a limited interaction history, making prediction difficult. This issue is further exacerbated in social recommendation systems, which need to integrate user information from both the interaction and social graphs.  
Formally, the graph-based social recommendation problem can be expressed as follows: The user set and item set are denoted, respectively, as \(U\) and \(I\), where \(|U|=N\) and \(|I|=M\). The social recommendation problem usually involves two graphs, the user-item interaction graph and the social graph. The user-item interaction graph is defined as \(\{(u,i,y_{ui})|u\in U,\,i\in I,\,y_{ui}\geq 0\}\), where \(y_{ui}\) is the edge weight between user \(u\) and item \(i\), and \(y_{ui}=0\) indicates there is no interaction between them. The interaction graph can be represented as an adjacency matrix \(\hat{A}_{UII}\in R^{(N+M)\times(N+M)}\). The social graph is denoted as \(\big{\{}\big{(}u_{i},\,u_{j},\,s_{ij}\big{)}|u_{i},\,u_{j}\in U,\,s_{ij}\in\{0, 1\}\big{\}}\), where \(s_{ij}=1\) if user \(u_{i}\) and user \(u_{j}\) have a social connection. The adjacency matrix of the social graph is denoted as \(\hat{A}_{S}\).