Graph Attention Network with High-Order Neighbor Information Propagation for Social Recommendation

1 Introduction

In the era of information explosion, recommender systems are taking on increasingly important responsibilities on filtering information and make personalized recommendation for users. Collaborative filtering (CF), exemplified by matrix factorization (MF) [Koren et al., 2009] and neural matrix factorization (NeuMF) [He et al., 2017], is a widely used approach to learn user and item representations from historical interactions for personalized recommendation. The predictive advantages of incorporating user's historical interactions are demonstrated by singular value decomposition++ (SVD++) [Koren, 2008], while neural attentive item similarity (NAIS) [He et al., 2018] leverages attention networks to improve predictive accuracy. However, these approaches primarily model shallow interactions, limited to one-hop neighboring connections between users and items. GNNs offer the capacity to uncover intricate interactions between users, items, and attributes. Models like neural graph collaborative filtering (NGCF) [Wang et al., 2019a], the simplified and powered graph convolution network (LightGCN) [He et al., 2020] and neighborhood-enriched contrastive learning (NCL) [Lin et al., 2022] address limitations of conventional methods. NGCF highlights the significance of high-order connectivity. LightGCN simplifies the approach by eliminating feature transformations and nonlinear activation modules. NCL enhances graph-based CF through contrastive learning.

Although these methods make advances in recommender systems, they are often assumed to have homogeneous graph structures and struggle with structural and semantic intricacies in heterogeneous graphs. The limitation hinders their ability to effectively model graph structures containing diverse characteristics. In heterogeneous graphs , existing methods [Tang et al., 2016; Hamilton et al., 2017; Liu et al., 2018; Fan et al., 2019a] directly stack multiple GNN layers and encounter the challenge of over-smoothing. The abundance of GNN paths prevents the recommender system from effectively capturing high-order neighbor relationships. Heterogeneous graph embedding methods based on the meta-path concept, such as HERec [Shi et al., 2018] and HAN [Wang et al., 2019b], could address the utilization issue of higher-order neighbors. However, these methods are dependent on meta-path-based random walks for processing heterogeneous graphs, necessitating manually defined metapaths, which restricts the model's expressiveness and flexibility. Additionally, these models consider only the nodes at both ends of a meta-path, ignoring all intermediate nodes, which leads to a loss of information. Furthermore, in the process of path encoding, these methods follow the path leading to the target node, but actual interactions may not always adhere to this direction. Such a discrepancy can result in inaccurate predictions, failing to accurately reflect the potential diffusion network structure.

To overcome these limitations, we introduce an innovative approach called GAIPSRec. GAIPSRec adopts the universal heterogeneous graph sampling framework we proposed, which eliminates the need for manually defining meta-paths. Additionally, it can aggregate high-order information without leading to over-smoothing. This method is capable of considering all nodes on higher-order neighbor relationships, not just the terminal ones. We employ a gate mechanism to fuse sequential (LSTM) and non-sequential(coverage mechanism) dependence, encoding the information in each node along the sampled path. The introduction of the coverage mechanism improves the utilization coverage of all representation information and enhances the memory properties of the attention mechanism, thus correcting erroneous attention allocation. By incorporating the cross-dependence, our approach gains a more holistic view of the data and reflects the potential diffusion network structure. GAIPSRec is able to capture the structural and semantic information of the heterogeneous graphs by considering interaction neighbor nodes and social neighbor nodes along the sampled paths. Following path encoding, GAIPSRec performs two-level path aggregation using attention mechanism, merging latent vectors from multiple sampled paths into the final node embedding. By integrating multiple sampled paths, our model adeptly learns comprehensive semantics embedded within the heterogeneous graphs.

In summary, this research brings several significant contributions:

• We propose a universal heterogeneous graph sampling framework, which does not require manually defined meta-paths for the path sampling process, thereby enhancing the model's flexibility. It effectively captures high-order neighbor information without leading to over-smoothing.
• We consider the information from all neighboring nodes along the entire path during path encoding, in contrast to the meta-path sampling method that focuses solely on the terminal nodes.
• We employ a gate mechanism to fuse sequential and non-sequential dependence, allowing us to view interaction data from a more comprehensive perspective.
• We carry out empirical studies using two datasets sourced from real-world scenarios. The outcomes of these experiments demonstrate a clear superiority of GAIPSRec over existing state-of-the-art baseline models.

2 RelatedWork

Graph Neural Network. GNNs initially emerge in the spectral domain due to their computational complexity [Bruna et al., 2013]. Defferrard et al introduced Chebyshev polynomials [Defferrard et al., 2016] to reduce computational complexity. GCN is derived from spectral methods but has a spatial interpretation due to the specific approximations used, and this approach has had a significant impact on the field of research in spatial GNNs. [Kipf and Welling, 2016]. With the application of the attention mechanism in deep learning models [Vaswani et al., 2017], graph attention networks (GAT) uses it for aggregating information from neighboring nodes [Veliˇckovi´c et al., 2017]. Furthermore, an algorithm known as FastGCN [Chen et al., 2018] introduces layer-wise sampling to reduce variance. Cluster-GCN, an efficient algorithm for training deep and large GCNs, uses subgraph sampling to increase parallelism [Chiang et al., 2019]. Despite their efficiency, these methods solely rely on user-item interaction data, and suffer from data sparsity. Adopting social recommendation can effectively alleviate this issue [Fan et al., 2018; Huang et al., 2021].

Social Recommendation. Early heterogeneous graphbased recommendation methods employ first-order social neighbors [Tang et al., 2013]. Both matrix factorization (SocialMF) [Jamali and Ester, 2010] and probabilistic matrix factorization (SoRec) [Ma et al., 2008] for recommendation in social rating networks model social influence as a regularization term. In contrast, social recommendation models based on GNNs leverage social neighbors and multiple types of connections [Fan et al., 2019a]. An influence diffusion neural network based model(Diffnet) [Wu et al., 2019a] and another neural influence and interest diffusion network based model (Diffnet++) [Wu et al., 2020] use attention mechanism and korder information diffusion to make social recommendation. Some methods further utilize user communities to enrich recommender systems [Liu et al., 2020; Xing et al., 2022; Fatemi and Tokarchuk, 2013].

The above methods tend to combine representations of users in the social graph with the user-item graph and assign appropriate weights. However, directly stacking multiple layers of GNNs can result in over-smoothing and limit the learning potential of higher-order neighbor information in GNN-based recommendation models. Even when involving high-order neighbors, it necessitates the definition of metapaths and focuses only on the nodes at the ends. Our proposed model, GAIPSRec, is designed to handle them effectively.

3 ProposedMethod

The GAIPSRec framework, as illustrated in Fig. 1, firstly random walks with restart based on length are performed on the heterogeneous recommendation graph to obtain sampled paths and path neighbors (starting and ending nodes). Various path encoders, such as LSTM, GRU, mean aggregation, and coverage mechanism with sequential dependence, are employed to model the information propagation process along the sampled paths. The GAT is then utilized to construct subgraphs by aggregating paths. Finally, attention mechanism is applied to aggregate subgraph representations of different lengths, resulting in user embedding and item embedding. The embedding is further utilized to perform rating prediction tasks.

3.1 Path Sampling for Information Propagation

In this work, we consider users and items as nodes during the sampling stage for recommendation in heterogeneous graphs containing both social and rating relationships. We use Random Walk with Restart (RWR) to simulate the paths of information propagation in the recommendation network and sample a set number of paths of varying lengths for each type of node. By employing this sampling strategy, we sample a subset of paths from the heterogeneous graph with the combination of user-item interactions and user-user relationships, and this sampling strategy significantly reduce the number of paths. This enables our method to consider higherorder neighbor relationships and mitigate the risk of oversmoothing in multiple aggregations of GNNs. At each step of the randomwalk, there is a certain probability of restarting and returning to the start node, which increases the influence of the start node on the walk sequence. Assuming the walk starts from a user node, at each step, the next node is selected based on the probability distribution.

where prwr denotes the probability of the random walk returning to the start node, and |Nneigh| denotes the number of first-order neighbors. The probability for selecting neighbors is set to follow uniform distribution. We denote the probability of a user node selecting the next node as follows:

where |Nitem| denotes the number of ratings given by the user, and |Nuser| denotes the number of social connections of the user. The next choice for an item node is only the rating relationships. By setting the above sampling probability, the model can sample the paths that are most closely related to the central node. Compared to random walk that only considers first-order neighbor nodes, random walk with restart sampling can capture more global graph structural information. The restart probability, prwr, is a hyperparameter of the model. When prwr is small, the sampling closely resembles random walk that only considers neighbor nodes, while a large prwr may result in insufficient sampling of the specified paths. In this part, paths with different lengths are sampled for each type of nodes, enabling the learning of information propagation and neighbor influence at different orders. Finally, attention mechanism is used to aggregate the representations of subgraphs with different lengths to update the node representations.

3.2 Information Propagation Path Encoder

Previous graph-based social recommendation models often separately train user embeddings in the recommendation network and social network before fusion [Fan et al., 2019a; Wu et al., 2019b]. In this part, we incorporate simulated information propagation paths through sampling. This method effectively preserves the heterogeneous interaction information between users and items and allows item embedding to be influenced by social relationships. By modeling information propagation along the paths, the model can learn higherorder neighbor information. To avoid over-smoothing of node embeddings, caused by stacking multiple layers of graph neural networks, we combine the modeling of information propagation with the path aggregation. We use multiple encoders to simulate the information propagation process along the random walk paths and obtain path representations.

where pu→v denotes a path instance from node u to node v, and nodes u and v are referred to as path neighbors in this paper. Mpu→v denotes the representation of the path information from node u to node v, and PE refers to the propagation encoder. en and er represent the embeddings of nodes and edges, respectively. Nodes include both user nodes and item nodes, while edges encompass both user-item interactions and social relationships.

The mean encoder computes the mean of the node embeddings along the path and uses it as the path representation. LSTM and GRU are used to encode the sequence of path nodes. The node ordering is set from far to near in RNN encoders, indicating that higher-order neighbors propagate information to the central node through intermediate nodes step by step. The GAIPSRec models with the mean, LSTM, and GRU encoders are denoted as GAIPSRec-mean GAIPSReclstm, GAIPSRec-gru, respectively.

Coverage mechanism and its fusion with sequential dependence. The actual process of information diffusionmay not strictly adhere to the sequential assumption, thereby limiting the predictive performance of sequential models such as LSTM and GRU. To overcome this limitation, inspired by the coverage model in linguistics, we propose a diffusiondependent attention layer with coverage mechanism. This mechanism enables the acquisition of non-sequential structured path representations while capturing diffusion dependence. It enhances the coverage of all representation information. Subsequently, we employ a gate mechanism to integrate non-sequential and sequential structured information of path representations, yielding the final path encoding.

Given a node nj ∈ {n0, n1, . . . , nN-1}, whose original representation is a one-hot vector of the user/item ID, denoted as xj ∈ RN , where N denotes the total number of users and items. To extract more expressive and efficient node features, the original node representation x is input into a fully connected layer to obtain the node embedding vector e.

where Wj ∈ Rd×N and bj ∈ Rd are learnable parameter matrices and biases, respectively, and d denotes the embedding dimension.

The diffusion dependence attention mechanism incorporates independent attention, which can make certain nodes dominate the attention weights. This dominance by a few influential nodes may neglect the information from other nodes, resulting in an incomplete reflection of the underlying diffusion network structure. We draw inspiration from coverage models used in linguistics. We utilize a coverage vector to keep track of previous attention results, enabling better guidance for future attention learning.

At each step, the process continues from the sampling start point to the endpoint along each sampled path. For a given path Mpu→v , the nodes N pu→v from u to v are denoted as {n0, n1, . . . , nl-1} in sequence, where l is the length of the path, and nj and nk are in the sequence. The structure of the diffusion-dependent attention layer with coverage mechanism is illustrated in Fig. 2. The calculation process is as follows:

where Wv2 ∈ Rd ,We1 ,We2 ,We3 ,Wv1 ,Wv3 and Wv4 ∈ Rd×d are parameter matrices, ve, bv ∈ Rd are parameter vectors. Vk,j ∈ Rd denotes the newly introduced coverage vector, which summarizes the previous attention results. By combining the coverage vector from the previous steps and the diffusion dependence weights, the coverage vector enhances the memory properties of the attention mechanism, making the attention at each step no longer independent of each other. The diffusion-dependent node representation information is aggregated by weighted sum as follows:

The dj is the node nj's diffusion-dependent feature information. For each node nj in the path sequence, the gate mechanism is applied to fuse its own embedding representation ej with the diffusion-dependent feature information dj, resulting in node-level features with dependence-awareness, denoted as the non-sequential structural node representation rj :

where Wg1 ,Wg2 ∈ Rd×d , bg ∈ Rd . The learned activation function gj serves as a gate, allowing the discarding of unimportant information from its own embedding representation ej, while incorporating useful information from the diffusion-dependent feature information dj. This process enables the fused node representation rj to be aware of its own diffusion dependence. In addition, we learn the node's sequential structural representation through LSTM.

Subsequently, the gate mechanism is used once more to combine the node's non-sequential structural representation with the sequential structural representation, resulting in the final encoding of the node as follows:

where Wq1 ,Wq2 ∈ Rd×d , and bq ∈ Rd . This allows the final fused node representation hj to more comprehensively perceive and represent the features of sequential nodes. In the end, we calculate the average weighted sum of the nodes along the path to obtain the final path encoding.

The GAIPSRec model with the coverage mechanism is denoted as GAIPSRec-cover.

3.3 Path Aggregation

For each path length, GAIPSRec samples several paths. In this part, we employ the attention mechanism inspired by the GAT framework to aggregate paths with the same length to construct subgraphs, allowing the model to learn the heterogeneous interaction information obtained by the information propagation path encoder. We generate attention weights by aligning the path representations of corresponding paths with the central node embedding.

where epuv denotes the importance of the path pu→v to the node u, and node u can be either a user or an item. ∥ denotes concatenation. The attention weight αpuv denotes the importance of different paths to user nodes and the N p u denotes the set of nodes at distance p from node u. To reduce the potential high variance during the model training process, the multi-head attention mechanism [Vaswani et al., 2017] is employed. We use k parallel attention modules to aggregate paths in a subgraph calculated by eq.17. Finally, the outputs from the k independent computations are combined.

3.4 Subgraph Representation Aggregation

After constructing subgraphs, subgraph representation aggregation is performed. Although few researchers have explored subgraphs generated by the paths whose lengths are greater than 3, GAIPSRec can effectively learn information from higher-order neighbors, enriching the feature information of users and items. The attention mechanism in GAIPSRec adaptively learns the importance of various subgraphs and aggregates the embedding representations of different subgraphs through weighted sum to update the central node.

For all nodes of the same type (users or items), their subgraph representations with the same path length (hpu ) are subjected to linear and nonlinear transformation, and then the average is taken to obtain the ensemble representation of the subgraphs for that specific length. For instance, for users, the process is as follows:

where Pi denotes the set of paths with a specific length, and each path instance pi ∈ Pi. U denotes the set of users, and u denotes a specific user node. P denotes the set of path lengths for users or items, and Pi ∈ P. The alignment of representations for paths of different lengths is achieved through linear transformation, and then softmax normalization is applied to obtain attention weights. For user nodes, the calculation process is as follows, and item nodes are similar.

3.5 Rating Prediction

Inspired by the idea of residual connections, GAIPSRec incorporates connections by concatenating the node's original embedding with its final embedding to obtain the model's output, which can alleviate the over-smoothing problem.

Then we concatenate user embedding representations with item embedding representations, employing a multi-layer linear network to predict the ratings.

3.6 Model Training

In our paper, the Root Mean Square Error (RMSE) and Mean Absolute Error (MAE) are combined and used as the loss function for model training. Additionally, L2 regularization is applied to the model parameters to prevent over-fitting.

where the λ denotes the penalty coefficient for regularization, and Θ corresponds to the model parameters. The Adam optimizer is used to train GAIPSRec.

Rank learning aims to present a sorted array of items to users, a common approach in various recommendation systems like top-k and sequential recommendations. For every user, items they have interacted with are marked as 1 (positive samples) when their rating meets or exceeds a threshold F, or 0 (negative samples) otherwise. This implies that users are inclined to engage with items rated F or higher. Considering our datasets have ratings from 1 to 5, we conduct experiments with F = 3. Model predictions are refined using the sigmoid function, and for the task of ranking, the loss is computed using the Binary Cross-Entropy (BCE) Loss:

4 Experimental Results

4.1 Experimental Settings

Datasets. The real-world recommendation datasets Ciao[Fan et al., 2019b] and Epinions[Fan et al., 2019a] are selected for the experiments. For each dataset, 80% of the rating data are randomly sampled to form the training set, while the remaining 20% are used as the test set. Table 1 presents the relevant information for these datasets.

EvaluationMetrics. To evaluate the model's rating performance, we use the MAE and RMSE. Smaller values of MAE and RMSE indicate better performance. We use the Precision and NDCG to evaluate the ranking performance, and the bigger values indicate better performance.

Baselines. This paper selects the following representative models to compare their performance with GAIPSRec:

• Traditional social recommendation algorithm: TrustMF [Yang et al., 2016], TrustSVD [Guo et al., 2016].
• Deep neural network based recommendation algorithms: SSL-SVD [Hu et al., 2020], NeuCDCF [Vijaikumar et al., 2021], ConsisRec [Yang et al., 2021].
• Graph neural network based recommendation algorithms: GraphRec [Fan et al., 2019a], SCSVD [Guan et al., 2021], GDSRec [Chen et al., 2023], MI3Graph [Zhu et al., 2023].

Parameter Settings. In order to compare different methods, we consider the parameter configurations by crossvalidation. To ensure fairness in our comparison, all experimental results are reported as the average of five independent runs. In this paper, we use PyTorch and Dgl to implement the GAIPSRec model. The learning rate η is set to 10-4 , and the embedding dimension D is 64. The hidden layer dimension is the same as the input layer dimension, and all parameters are initialized using the Xavier uniform distribution. For both user and item nodes, we sample paths of lengths [2, 3, 4, 5], and the dropout rate is set to 0.5. We test the restart probability prwr is set to 0.2.

4.2 Comparative Experiments

In this part, we conduct comprehensive experiments to compare the proposed GAIPSRec model with existing models. The experimental results of GAIPSRec and the baseline models are presented in Table 2.

GraphRec performs better than TrustMF and TrustSVD, probably because of the utility of performing propagation information across users and items under a graph-structured neural network. GDSRec's good performance on the Ciao dataset is attributed to the fact that it utilizes both user and program statistics. MI3Graph beats most social recommendation models on the Epinions dataset due to its incorporation of multi-interaction information. GAIPSRec-cover achieves the best results on both the Ciao dataset and the Epinions dataset. Compared to the best-performing baseline model, GAIPSRec shows improvements of 3.28% and 1.64% in MAE and RMSE, respectively, on the Ciao dataset. On the Epinions dataset, GAIPSRec achieves improvements of 2.31% and 0.88% in MAE and RMSE, respectively. These results demonstrate that the model design of GAIPSRec, which combines random walk simulations for information propagation with path aggregation, is effective. Moreover, GAIPSReclstm outperforms GAIPSRec-gru, but both models show similar performance. The LSTM encoder, with its more complex network structure, has stronger representation capabilities. However, the mean encoder, GAIPSRec-mean, exhibits weaker representation capabilities compared to RNN-based encoders.

4.3 ItemRanking

In this part, we evaluate the item ranking performance of our model on Ciao and Epinions. We selected several top-n ranking algorithms for comparison: PMF [Mnih and Salakhutdinov, 2007], SVD++, NeuMF, LightGCN, GraphRec, Diffnet++, and GDSRec. The results are depicted in Table 3. It is observed that the performance differences on the Precision metric are minimal. This is attributed to the high proportion of positive samples in the dataset, resulting in generally high Precision across all models. By contrast, there is a noticeable variance in model performance on the NDCG metric, where GAIPSRec outperforms the other models. This indicates that GAIPSRec is more effective in promoting positive items to higher ranks.

4.4 Ablation Study

In this part, we conduct an ablation study to investigate the effectiveness of different modules in GAIPSRec. By comparing GAIPSRec with its variants, namely GAIPSRec-2, GAIPSRec-3, GAIPSRec-4, and GAIPSRec-neigh, we can assess the importance of each module. GAIPSRec-L removes the paths of length L and their corresponding subgraphs. GAIPSRec-neigh does not use random walk-sampled paths. Instead, it only aggregates path neighbors and performs subgraph representation aggregation on the subgraphs to demonstrate the effectiveness of information propagation modeling.

Here, we only present the experimental results on the Ciao dataset, and the results on the Epinions dataset are similar. As shown in Fig. 3, GAIPSRec-neigh does not utilize path information propagation encoding and achieves the worst results on both of the datasets. Other variants that combine information propagation modeling with path aggregation outperform GAIPSRec-neigh, indicating that the proposed random walk path sampling and path information encoding significantly improve the performance, and the combination of information propagation and path aggregation is effective.

Regarding the variants that remove paths of certain lengths and their corresponding subgraphs, on both datasets, GAIPSRec-4 performs the best, indicating that removing the subgraphs of 4th-order neighbors has relatively little impact on the model. Additionally, GAIPSRec-2 slightly outperforms GAIPSRec-3. One possible explanation is that 3rdorder neighbors are more likely to be of the same type, such as item-item relationships, which have a larger impact on the model. All variants perform worse than the complete GAIPSRec, validating the effectiveness of each part in the model.

4.5 Hyperparameter Analysis

In this part, we conduct experiments to analyze the impact of hyperparameters on the model, including the embedding dimension D, and the random walk restart probability prwr. The experiments in this section are performed using the GAIPSRec-cover model.

We conduct experiments using embedding dimensions [16, 32, 64, 128, 256]. As illustrated in Fig. 4, on both datasets, the optimal RMSE and MAE are obtained with an embedding dimension of 64. When the dimension is lower, the model's expressive power still has potential for improvement. Conversely, with higher dimensions, over-fitting may occur, leading to a drop in performance.

GAIPSRec leverages random walk with restart for path sampling to approximate the information propagation process. Restarting the random walk enhances the influence of the start node. In this part, we experiment with prwr ∈ [0, 0.6]. As depicted in Fig. 5, the model on both datasets attains optimal performance with the restart probability of 0.2.

When the restart probability is small, an increase in prwr facilitates the sampling of paths that are nearer to the center node, resulting in a decrease in both RMSE and MAE. Conversely, when the restart probability is high, an increase in prwr causes that fewer neighboring nodes are included.

5 Conclusions

This paper presents an graph attention network with information propagation and path aggregation for social recommendation. We perform sampling based on proposed universal framework for heterogeneous graph sampling, eliminating the need for manually defining meta-paths. This sampling method helps to facilitate the acquisition of information from higher-order neighbors, and alleviate the prevalent problem of over-smoothing within the GNNs and the constraints brought about by the definition of meta-paths. Our information propagation path encoding consider all the nodes along the path. Additionally, the coverage mechanism encoder with sequential dependence is used to model the information propagation process and gains a more holistic view of the data and reflects the potential diffusion network structure. We combines information propagation with path aggregation in GNNs. Subgraph representation aggregation is performed in subgraphs composed of path instances, providing users and items with richer high-order neighbor and graph structure information. Extensive experiments on real-world datasets demonstrate the effectiveness of the proposed model.

Acknowledgments

This research is supported by the Natural Science Foundation of Shaanxi Province for Distinguished Young Scholars (No. 2023-JC-JQ-54).