Graph Cross-Correlated Network for Recommendation

Collaborative Filtering (CF) is a prevalent technique for recommender systems that parameterizes users and items as embeddings and learns their embeddings based on historical user-item interactions [1, 15, 16, 17].

One typical type of pioneering work, Matrix Factorization (MF) [3, 4], projects the user and item indexes into embedding vectors. It reconstructs historical user-item interactions by computing the dot product between user embeddings and item embeddings. To improve the quality of these embeddings, researchers have explored incorporating various types of auxiliary information, such as content information [18, 19], social relations [20, 21], user reviews [22, 23], and knowledge graphs [24, 25, 26, 27]. Although the dot product can extract interaction information by forcing interacted user-item pairs to achieve a larger dot product value, the linear interaction modeling limits the modeling performance when dealing with complex, sparse, or implicit interactions [1, 28]. To enhance the expressive power of the models and capture more intricate interactions, researchers have explored the use of neural networks to learn the interactions [1, 29]. This approach offers a promising avenue to improve the approximation capabilities and handle complex patterns in user-item interactions.

Another line of research finds that user-item interactions form a bipartite or heterogeneous graph. In this sense, conventional CF approaches derive user/item embeddings by only considering 1-hop interactions. Therefore, graph embedding methods, initially introduced for social network data mining tasks such as node classification, clustering, and community detection [30, 31], have demonstrated significant potential in real-world recommender systems. For example, DeepWalk [32] and Node2Vec [33] adapt word embedding methods [34] to graph structures and construct the corpus by randomly walking on social networks. Inspired by this, MetaPath2Vec [35] introduces the metapath-based random walk upon heterogeneous networks to embed users, items, and any other type of nodes together.

In recent years, graph neural networks (GNNs) have garnered significant attention and have demonstrated state-of-the-art performance across various graph-related tasks [14, 36, 37, 38, 39, 40]. Recognizing the strengths of GNNs, researchers have begun incorporating them into Collaborative Filtering (CF) methods to enhance the learning of more powerful embeddings [9, 41]. For instance, NGCF [8] adapts user-to-item propagation and user-to-user propagation to extract graph embeddings for each user and item and then computes the dot product of concatenated layer-wise graph embeddings. To speed up the training process, LightGCN [9] discards the non-linear layers in NGCF and aggregates the layer-wise graph embeddings with weighted summations. UltraGCN [42] replaces the complex graph convolution process with simple auxiliary objective losses. Some recent studies further include data augmentation and self-supervised learning for enhancing graph-based recommendation models [11, 43]. Representatively, SGL [44] first introduces self-supervised learning on the user-item graph by creating multiple views of a node. It is trained using contrastive learning that maximizes agreement between these different views of the same node while minimizing agreement with views of different nodes. NCL [45] enhances the neighbor set with semantic neighbors guided by contrastive learning. SimGCL [46] is a simple but effective graph contrastive learning model with the removal of unnecessary augmentations. CGCL [47] further includes the novel strategies of candidate contrastive learning and candidate structural neighbor contrastive learning. Ultimately, these GNN-based models infer user-item interactions by computing the dot product of the super representation embedding vectors for users and items. By combining the power of GNNs with CF methods, these models leverage the graph structure of user-item interactions [10].

Although these methods have achieved state-of-the-art recommendation performance, the architecture that simply aggregates the information of users/items and their neighbors might not have enough degrees of freedom to model sophisticated user-item relationships. Despite the progress in learning more powerful embeddings, most of the aforementioned methods compute user-item relevance through a simple inner product [3, 4, 9] or MLP [1, 5]. Earily, NIA-GCN [48] conducts interactions between each central node and its neighbors before aggregation. However, this process does not consider the relevance of the user subgraph and the item subgraph. There have been few efforts to design more expressive relevance metrics or to investigate how the relevance metrics might influence eventual recommendations.

Therefore, in this paper, our proposed Graph Crossed-correlated Network for Recommendation (GCR) explores whether there exists a learnable relevance metric that can be compatible with any kind of embeddings, including CF embeddings, graph embeddings, and GNN embeddings. This not only helps to enhance the model in existing recommender systems but also enables researchers to gain a deeper understanding of recommendation systems.

Click-Through Rate (CTR) prediction is a crucial stage for online recommender systems and computational advertisements [29, 49, 50]. Existing models for CTR prediction can be largely divided into two main categories: feature-interaction methods and user-interest modeling methods.

Due to the high sparsity of raw input features and the difficulty of directly utilizing such features, feature interaction-based models have received extensive research for CTR prediction. Representatively, FM [51] first introduces the latent vectors for 2-order feature interaction to address the feature sparsity. Wide&Deep [52] conducts feature interaction by a wide linear regression model and a deep feed-forward network with joint training. AFM [53] then design the attention mechanism for cross-feature learning. DeepFM [54] further replaces the linear regression in Wide&Deep with FM to avoid feature engineering. Since the user’s historical interactions can reflect the interest, another line of work in recent advances focuses more on user interest modeling using deep neural networks and achieves state-of-the-art results. Notably, DIN [29] first designs a deep interest network with an attention mechanism between the user’s behavior sequence and the target item. DIEN [49] then further enhances DIN with gated recurrent neural units for user’s evolution patterns mining. UBR4CTR [55] and SIM [56] then design a two-stage paradigm, searching relevant items and computing their attention score with the target, to learn of the user’s life-long behaviors. DCIN [57] is a further novel model that integrates explicit and implicit decision-making contexts. Moreover, GMT [58] and NRCGI [59] then include graph sampling and graph clustering for CTR prediction with graph information inclusion in an efficient way.

We have also conducted experimental analyses of equipping the CTR prediction models with our proposed GCR on both the public dataset and the real-world industry dataset, which show that GCR can also be generalized to provide remarkable improvement on the CTR prediction task.

As depicted in Figure 1-(c), the Plain Graph Representation (PGR) module operates in two steps. Firstly, it extracts a subgraph of a specific depth for each user/item instance. Secondly, it performs information aggregation over the retrieved subgraph in an unfolding manner.

In particular, we iteratively track the neighbors of each target node $j$ with the breadth-first searching, obtaining $\{{\mathcal{N}}_{j}^{(0)},{\mathcal{N}}_{j}^{(1)},\cdots,{\mathcal{N}}_{j}^{(L)}\}$ where ${\mathcal{N}}_{j}^{(l)}$ contains the $l$-hop neighbors of $j$, and ${\mathcal{N}}_{j}^{(0)}$ contains the node $j$ itself, i.e., ${\mathcal{N}}_{j}^{(0)}={j}$. We apply the simple but effective mean-pooling operator to read out the representation for each hop of neighbors, namely as follows:

where ${\bm{e}}_{j}^{(l)}$ is the readout vector of node $j$’s $l$-hop neighbors.

Compared with GNN-based models. The superiority of our PGR to GNN-based ways for recommendation can be illustrated in the following three main aspects. Firstly, PGR is more suitable for recommendation tasks since it can extract graph information without mixing the personalized embeddings of users and items. Recursive graph convolution in Eq.(4) is initially designed for homogeneous graphs, where all users are of the same kind. Passing messages along the edges helps to better extract local graph information. However, for the recommendation task in the user-item bipartite graph, users and items have totally different semantic meanings and connecting characteristics. For example, users usually have some stationary interests and click a certain range of items, while popular items may be exposed and clicked by a great number and a wide range of users. Thus, mixing the embeddings of different types of nodes may bring in information noise when modeling the relations between users and items. Secondly, PGR, even though simple, is more robust than GNN for the recommendation task. Note that the observed connections between users/items in the recommendation are usually noisy and incomplete. Performing recursive message passing like GNNs would spread the noise along with the noisy connections, hence impeding the model training. In PGR, we use mean pooling to devise the representation for each instance, which is robust to eliminate the noise. Lastly, PGR is more computationally efficient, as no recursive updating is needed, ensuring the efficiency potential for online recommendations. Besides, PGR is parameter-free and can thus be pre-computed and stored to save time further, enhance model efficiency, and accelerate the inference process. The experimental comparisons between PGR and GNN-like models are conducted and reported in Table IV and Table V in Section V.

The success of FM [51, 54] indicates that, for recommendation tasks, employing a specially designed feature interaction model structure can greatly enhance recommendation performance compared to blindly feeding all features into an MLP structure. Earily, NIA-GCN [48] first conducts interaction between a central node and its neighbors, which shows the effectiveness of building correlations. However, there is still much to be done to study how to model the complex correlations underlying user/item subgraphs for meaningful information mining.

Building upon the practical physical semantics of multi-hop embeddings, several insights can be derived. For example, start from the view of the root target user $u$, ${\bm{e}}_{u}^{(0)\top}\cdot{\bm{e}}_{i}^{(0)}$ infers the explicit relation between the target user and the target item, ${\bm{e}}_{u}^{(0)\top}\cdot{\bm{e}}_{i}^{(1)}$ then reflects the correlation between the target user and the users who have clicked on the target item. Furthermore, ${\bm{e}}_{u}^{(0)\top}\cdot{\bm{e}}_{i}^{(2)}$ implies the correlation between the target user and relevant items that are clicked by the users who have clicked on the target item. The relations start from the view of the root target item $i$ with ${\bm{e}}_{i}^{(0)}$ also have their physical semantic meanings. Since different cross-correlations reflect user-item interactions from different angles, it is worth considering all possible cross-correlations between the target user and the target item in a flexible manner to make comprehensive recommendations. Thus, we provide two flexible ways for cross-correlation modeling: Hop-level Cross-Correlation and Element-level Cross-Correlation modeling.

Hop-level Cross-Correlation (HCC). One simple but powerful way to consider cross-correlations is to model them using the dot product. Specifically, we denote the cross-correlated relevance between the $l_{u}$-th hop of the user graph embeddings and the $l_{i}$-th hop of the item embeddings as $z_{ui}^{(l_{u},l_{i})}$. The cross-correlated terms of HCC can be formally defined as:

where $0\leq l_{u}\leq L$ and $0\leq l_{i}\leq L$. By concatenating all possible pairs into a vector, the aggregated cross-correlation of the target user $u$ and the target item $i$ can be reflected by concatenating the cross-correlations of all possible pairs as $\parallel_{l_{u}=0,l_{i}=0}^{L,L}{\bm{z}}_{ui}^{(l_{u},l_{i})}$. After aggregating the cross-correlations, the relevance score computation can be given as:

In HCC, the dimension of the cross-correlated terms $z_{ui}^{(l_{u},l_{i})}$ decreases to one. Note that the aggregated cross-correlation vector of HCC contains only $(L+1)^{2}$ scalars, meaning that the parameters of the MLP in Eq. (11) will be considerably small. This will potentially avoid the risk of overfitting and contain more information in fewer scalars.

Element-level Cross-Correlation (ECC). Another way to represent the cross-correlations between multi-hop user/item graph embeddings is by computing the element-wise product instead of the dot product to preserve more latent space information. Specifically, we refer to this as the Element-level Cross-Correlation (ECC). The computation of ECC cross-correlated terms can be expressed as follows:

where $\odot$ denotes the element-wise multiplication (Hadamard product), $0\leq l_{u}\leq L$ and $0\leq l_{i}\leq L$. After traversing all possible pairs, concatenating their element-wise multiplication into a vector, and feeding the cross-correlated terms into Eq. (11), we can arrive at:

In ECC, the dimension of the cross-correlated terms $z_{ui}^{(l_{u},l_{i})}$ is the same as the dimensions of the user/item embeddings, denoted by $d$. Thus, the total dimension of the aggregated cross-correlation vector for ECC is $(L+1)^{2}\cdot d$.

Theorem 1 (Degree of freedom). In statistics, The concept of degrees of freedom refers to the number of values within a statistic that are allowed to vary freely. When estimating statistical parameters, the degrees of freedom indicate the amount of independent information or data used in the estimation. It is calculated by subtracting the number of parameters used as intermediate steps in the estimation from the number of independent scores contributing to the estimate. Mathematically, degrees of freedom correspond to the number of dimensions in the domain of a random vector. It signifies the number of ”free” components within the vector, or rather, the number of components that need to be known before the vector is fully determined.

Analysis of Flexibility. Both HCC and ECC exhibit remarkably higher degrees of freedom than GNN-based recommendation models. For instance, as shown in Eq.(5), the concatenating aggregation used in NGCF [8] can be seen as computing the summation of the dot product for each hop of user/item graph embeddings. The concatenating aggregation cannot provide flexibility in aggregating the cross-correlation of multi-hop user-item interactions. For LightGCN [9], as illustrated in Eq.(6), the weighted summation aggregation of the cross-correlation is controlled by $2\cdot(L+1)$ parameters, resulting in the flexibility of $2\cdot(L+1)$. In the case of GCR, MLP structures are trained to flexibly aggregate the cross-correlations between users and items. The degrees of freedom for HCC and ECC can be computed as $(L+1)^{2}\cdot H_{n}^{H_{l}}$, where $H_{l}$ is the number of hidden layers in MLP, and $H_{n}$ is the number of hidden units of each layer. Specifically, given $L=2$, $d=64$, $H_{n}=256$, and $H_{l}=1$, the degrees of freedom for NGCF, LightGCN, HCC, and ECC are 0, 6, 2304, and 147456, respectively. Moreover, even when substituting the MLP used in GCR with linear regression, the degrees of freedom for HCC and ECC are 9 and 576, respectively, which are still higher than those of GNN-based models. In general, both theoretical and quantitative analyses demonstrate that GCR models have significantly higher degrees of freedom than GNN-based models.

Note that the cross-correlation aggregation, that is applied before MLP in Eq. (11) and Eq. (13), is crucial as it integrates the explicit user-item interactions as well as the implicit correlations between user-item pairs. We demonstrate the necessity of CCA in our ablation study and discuss the weight parameters assigned to each cross-correlated term in the case study in the following section.

In our framework, PGR is parameter-free, and the parameters of MLP in Eq.(11) and Eq.(13) are required to be optimized. To do so, we employ the Bayesian Personalized Ranking (BPR) loss [4, 8, 9], which has been extensively used in recommender systems. It considers the relative order between observed and unobserved user-item interactions. Specifically, BPR assumes that the observed interactions should be assigned higher prediction values than unobserved ones. The objective function is formulated as follows:

where $\mathcal{O}=\{(u,i,j)|(u,i)\in\mathcal{R}^{+},(u,j)\in\mathcal{R}^{-}\}$, $\mathcal{R}^{+}$ indicates observed user-item interactions, $\mathcal{R}^{-}$ denotes sampled negative interactions, and $\sigma(\cdot)$ is the Sigmoid function.

Flexible optimization. The components of the proposed GCR framework are task-agnostic, thus it is flexible to different recommendation tasks. For the critical CTR prediction task, we can replace the objective function with the binary cross-entropy (BCE) loss [54, 29, 49]. Formally, for each labeled user-item pair $(u,i)$ in the training set ${\mathcal{T}}$ of CTR prediction, the BCE objective function can be expressed as:

where $\hat{y}_{ui}$ is the predicted CTR and $y_{ui}$ is the ground-truth clicking label. The overall algorithm flow of each stage of our proposed GCR for recommendation is shown in Algorithm 1 and Algorithm 2.

In this subsection, we compare our proposed GCR with the other six representative recommendation baseline models. The overall recommendation comparison results are illustrated in Table III, of which the improvement is calculated by comparing the performance of GCR with the best-performed baseline (marked in underlined). From these results, we have the following observations:

• •

  Firstly, it can be seen from the table that our GCR statistically outperforms the best baseline models on all datasets with respect to all metrics. For instance, GCR demonstrates a significant improvement in Precision of 4.32%, 2.81%, and 2.32% across the three experimental datasets, respectively. Specifically, GCR brings the performance average gains of 3.15%, 2.24%, and 1.82% for Precision, Recall, and NDCG metrics respectively on the three experimental datasets.

• •

  Furthermore, SimGCL mainly obtains the best performance over all the baselines. NGCF, LightGCN, UltraGCN, SGL, GTN, NCL, and SimGCL consistently outperform GRMF and MetaPath2Vec, suggesting that considering and aggregating the graph information helps to provide better recommendation results. GCR provides a more flexible way to aggregate the graph information and thus achieves better performance.

In this subsection, we compare the recommendation performance between our GCR and the dot product, MLP, and the super-vector-based dot product when fed with the same embeddings. The compared relevance functions are specialized as follows:

• •

  Dot product [3, 4]: This is the most common relevance metric given by Eq.(2).

• •

  MLP (Multi layer perception) [1, 68]: MLP is used in NCF [1] and common CTR recommendation models [54], which also become a widely used relevance function.

• •

  Super-Vector (Super-vector-based dot product) [8, 9]: We use LightGCN to calculate the super vectors for each user and item.

The Effectiveness analysis is shown in Table IV, which provides the comparisons of the relevance functions over three different embeddings on three experimental datasets. The improvement is calculated by comparing GCR with the other best-performed relevance functions. From this result table, we can derive observations as follows.

• •

  Simply applying MLP as the relevance function cannot amplify the expressive power of the learned embedding. As stated in [61], although MLP is theoretically universal to approximate the dot product, it is difficult to approximate in practice, especially when the embeddings are optimized for the dot product.

• •

  Super-vector-based dot products can enhance the expressive power of GRMF and MetaPath2Vec embeddings. But for LightGCN, super-vector-based dot products lead to relatively worse recommendation performance. One possible reason for the degradations is that LightGCN has already utilized graph convolution layers to encode the graph information explicitly. Further applying graph convolution to graph-based embeddings will encounter the problem of high-order GNNs, e.g., the over-smoothing problem [69]. The over-smoothed embeddings are indistinguishable and negatively affect user modeling and the recommendation performance [70].

• •

  GCR statistically outperforms the other three counterparts on all three datasets with all three embeddings. In particular, with MetaPath2Vec embeddings, GCR improves over the strongest baselines w.r.t. NDCG@20 metric by 16.53%, 13.90%, and 10.74% on Gowalla, Yelp2018, and Amazon-Book, respectively. Further, GCR outperforms the other relevant functions with average gains of 9.53%, 8.20%, and 8.76% for Precision, Recall, and NDCG over the three types of embeddings on the three recommendation datasets. This phenomenon illustrates that GCR is able to alleviate the over-smoothing problem and further improve the recommendation performance of GRMF, MetaPath2Vec, and LightGCN.

Due to the necessity of real-time recommendation, besides effectiveness, model efficiency is also an important factor that needs to be considered [59]. As for the efficiency analysis, we report the average inference time of each compared method in Figure 3.

From these results, we can see the following findings: First, GCR has a negligible time cost compared to the dot product and MLP, which is acceptable given the dramatic performance improvement we achieved. Then, compared to the super-vector-based dot product, GCR is much more efficient because PGR is a parameter-free and parallelizable process. This experiment demonstrates that although GCR extracts and exploits the cross-correlations between multi-hop user/item subgraph embeddings, it achieves a good balance between time consumption and performance.

In the ablation study section, we discuss the influence of our two core components: PGR and CCA. Specifically, we compare the recommendation performance of the following six combinations:

• •

  GNN (Super-Vector): This variant uses GNN to compute the graph representation super vector and uses the dot product for interaction prediction.

• •

  GNN-HCC: This variant uses GNN for graph representation and HCC for interaction prediction.

• •

  GNN-ECC: This variant uses GNN for graph representation and ECC for interaction prediction.

• •

  PGR-MLP: This variant uses PGR for graph representation and then feeds the concatenated graph representation into a three-layer MLP for interaction prediction.

• •

  PGR-HCC: This variant uses PGR for graph representation and HCC for interaction prediction.

• •

  GCR (PGR-ECC): This variant uses PGR for graph representation and ECC for interaction prediction.

We describe the comparison results in Table V, from which we present the NDCG@20 of the above six variants on Gowalla, Yelp2018, and Amazon-Book. Without loss of generality, we conduct this experiment with MetaPath2Vec embeddings. From this result table, we can summarize the following conclusions:

• •

  PGR-based variations consistently perform better than GNN-based variations. This demonstrates that PGR is more informative than GNN for recommendation tasks. The plain representation style better extracts the information of each hop of neighbors than recursively message-passing GNNs. Therefore works better with CCA to extract the implicit relation behind user and item subgraphs.

• •

  Compared to GNN (Super-Vector), GNN-HCC/ECC consistently outperforms GNN in all three datasets. This proves that GNN (Super-Vector), which represents users/items as super-vectors, cannot fully exploit the expressive power of embeddings. Thus, by flexibly considering all possible cross-correlations with CCA, GNN-HCC/ECC outperforms GNN (Super-Vector) by significant margins.

• •

  PGR-MLP performs the worst on all three datasets. Without explicitly extracting the cross-correlations with CCA, MLP cannot model the complex interaction between user and item subgraphs. This observation verifies and substantiates the importance of cross-correlated aggregation.

Case Study. We further explore the mechanism of HCC/ECC of GCR through visualization. Specifically, in Figure 4, we visualize the weights of linear HCC/ECC by setting the number of hidden layers for MLP to zero. By visualizing the weights associated with each cross-correlated term, this figure demonstrates the following three mai observations: 1) the necessity of the cross-correlation aggregation; 2) the consistency between HCC and ECC; 3) the characteristics of the weights associated with each cross-correlated term.

• •

  The necessity of the cross-correlated aggregation. From the individual subplots in Figure 4, it appears that CCA models, including HCC and ECC, learn different weights for each cross-correlated term. This verifies that assigning different weights for each cross-correlated term helps to reduce the personalized ranking loss as well as make more accurate recommendations.

• •

  The consistency between HCC and ECC. One concern about the cross-correlated aggregation is whether the element-wise ECC tends to assign similar weight parameters as the layer-wise HCC model. As shown in the figure, after normalization, the weight parameters of HCC and ECC show similar trends on all three datasets with all three embeddings, confirming the consistency between HCC and ECC.

• •

  The characteristic of the embeddings In Figure 4, each row of subplots represents the visualization of the weights of a particular embedding, from GRMF to MetaPath2Vec to LightGCN. Comparing the tendency of the weight parameters of each embedding, the tendency of a particular embedding seems to be similar across different datasets. For GRMF, the weight parameters of $z^{(01)}$ are significantly larger than other cross-correlation terms. For MetaPath2Vec, the weight parameters of each cross-correlation term happen to be much more uniform than other embeddings, while the weight parameters of $z^{(02)}$ are slightly higher than the others. For LightGCN, the SOTA recommendation method, $z^{(00)}$ and $z^{(02)}$ have higher importance than other cross-correlation terms.

Click-Through Rate (CTR) prediction task is to predict the probability that a target user will click on a target item. It performs as an important stage in the recommendation system. Therefore, in this subsection, we have also verified the flexibility and effectiveness of GCR in equipping the CTR models for performing the CTR prediction task.

We test whether GCR can improve the CTR prediction task by running experiments on user-item clicking data. Specifically, we conduct CTR prediction experiments on the widely used Amazon-Book recommendation dataset and the WeiXin industrial dataset, and the details of these datasets are illustrated in Table II. We include six representative CTR prediction models: DIN  [29], DIEN [49], UBR4CTR [55], SIM [56], GMT [58], and DCIN [57] as our baselines. Further, we equip DIN with our GCR as the model ”DIN+GCR”, which refers to enhancing DIN with the modeling of high-order information (1-hop and 2-hop neighbors with DIN-based neighborhood sampling) and graph cross-correlation terms with our GCR model.

In Table VI, we present the AUC metric and corresponding RelaImpr value to evaluate the performance of these CTR prediction models. From this table, “DIN+GCR” outperforms the other baselines, confirming the effectiveness and flexibility of GCR on the CTR prediction task. Compared to the best baseline GMT, “DIN+GCR” shows a relative improvement of 2.79% on Amazon-Book and 1.25% on WeiXin. More importantly, “DIN+GCR” improves DIN by extracting the graph information with PGR and constructing the cross-correlation interactions with ECC, bringing a RelaImpr gain of 18.51% on Amazon-Book and 6.71% on WeiXin. These results also show the effectiveness of GCR for real-world use in industrial scenarios. Thus, it can be utilized flexibly to enhance current CTR prediction models.