# Social)GCF: Social Recommendation with Jacobi Polynomial-Based Graph Collaborative Filtering
## 3 Method
### Overall Architecture
#### 3.1.2 Propagation Layer  
Essentially, the task of recommendation systems is to predict possible future user-item interactions given past interactions. This can be mathematically formulated as finding a map \(f\) from past interactions \(A\in R^{N\times N}\) to future interactions \(A^{\prime}\in R^{N\times N}\). \(A\) and \(F\) are adjacency matrices where \(A_{ij}=1\) indicates user \(i\) had past interactions with item \(j\) and \(A^{\prime}_{\cdot ij}=1\) indicates user \(i\) probably will interact with item \(j\) in the future. Formally, the optimization of the recommender system can be denoted as  
\[\min\big{|}\big{|}f(A)-A^{\prime}\big{|}~{}~{}\big{|}_{F},\] \begin{table}
\begin{tabular}{l c c c} \hline \hline  & **Unified Graph** & \multicolumn{2}{c}{**Dual Graphs**} \\ \cline{3-4}  & & **Non-Frequency Based** & **Frequency Based** \\ \hline Trust-based recommendation & [7; 13; 37] & [11; 38; 39; 42] & [41] \\ \hline Cold-start recommendation & [24] & [40] & this paper \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparisons with other papers. where \(||\cdot|\ |_{F}\) is the Frobenius norm. Since \(A\) is a symmetric matrix, we can perform eigen decomposition on it, \(A=Q\Lambda Q^{T}\), where \(Q\in R^{N\times N}\) is an orthonormal matrix whose columns are eigenvectors of \(A\), and \(\Lambda\in R^{N\times N}\) is a diagonal matrix containing all the eigenvalues of \(A\). Considering the invariance property of the Frobenius norm under orthonormal projection, we can restate the objective as  
\[ \begin{array}{l}\min||f(A)-A^{\prime}|\ \big{|}_{F}=\min||f(Q\Lambda Q^{T})-A^{ \prime}|\ \big{|}_{F}\\ =\min||f(\Lambda)Q^{T}-A^{\prime}|\ \bigg{|}_{F}\\ =\min||f(\Lambda)-Q^{T}A^{\prime}Q|\ \bigg{|}_{F}.\end{array} \]  
While the equation is still difficult to optimize directly, we can observe that the optimization is towards function \(f\) and the off-diagonal elements of \(f(\Lambda)\) do not contribute to the Frobenius norm. Then, the objective can be simplified to an equivalent least-square fitting objective,  
\[\min\sum_{i}\Bigl{(}f(\Lambda_{ii})-Q_{\cdot i}^{T}A^{\prime}Q_{\cdot i}\Bigr{)} ^{2},\]  
which shows that a good mapping function \(f\) should extract the relationship of \(\Lambda\) and the diagonals of \(Q^{T}A^{\prime}Q\). Generally, the propagation layer captures higher-order connections between users and items within the user-item interaction graph and relationships between users in the social graph. LightGCN [19] is a popular method for propagation layers due to its simplicity, and takes the form  
\[E^{(K)}=\frac{1}{K+1}\sum_{k=0}^{K}E^{(k)}=\sum_{k=0}^{K}\frac{\hat{A}^{(k)}}{ K+1}E^{(0)}.\]  
The formula suggests that the final embedding \(E^{(K)}\) is derived by applying the filter \(\sum\limits_{k=0}^{K}\hat{A}^{(k)}\) to the initial embedding \(E^{(0)}\). However, the bases of the filter are not orthogonal to each other, lacking mutual independence, and thus their ability to extract essential information in the final embedding is limited. A Jacobi polynomial is an orthogonal and expressive basis which is widely used in scientific computations. This makes it an appropriate alternative to LightGCN, which is the core of JGCF and is the main method in the propagation layer. JGCF takes a spectral view of the recommendation task, and finds the correlation of the interaction signal frequency between the training data and the test data [27]. Thus, JGCF designs a frequency filter for the recommendation task and applies Jacobi polynomials to estimate the filter. Since the signals with low frequency or high frequency in training data show a strong linear correlation with that in test data, no activation is applied and the propagation formula is  
\[E^{(K)}_{band-stop}=\frac{1}{K+1}\sum P^{a,b}_{k}\bigl{(}\hat{A}\bigr{)}E^{(0 )}.\]  
Here, \(P^{a,b}_{k}\) represents the Jacobi polynomial of order \(k\) with parameters \(a\) and \(b\). These parameters influence the filter's frequency response, allowing for control over which frequency bands are emphasized or attenuated.