{'fraction_non_alphanumeric': 0.03855876878628774, 'fraction_numerical': 0.009111870433647248, 'mean_word_length': 4.816448537728228, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
MGDCF: Distance Learning via Markov Graph Diffusion for Neural Collaborative Filtering

Collaborative filtering (CF) is widely used by personalized recommendation systems, which aims to predict the preference of users with historical user-item interactions. In recent years, Graph Neural Networks (GNNs) have been utilized to build CF models and have shown promising performance. Recent state-of-the-art GNN-based CF approaches simply attribute their performance improvement to the high-order neighbor aggregation ability of GNNs. However, we observe that some powerful deep GNNs such as JKNet and DropEdge, can effectively exploit high-order neighbor information on other graph tasks but perform poorly on CF tasks, which conflicts with the explanation of these GNN-based CF research. Different from these research, we investigate the GNN-based CF from the perspective of Markov processes for distance learning with a unified framework named Markov Graph Diffusion Collaborative Filtering (MGDCF). We design a Markov Graph Diffusion Network (MGDN) as MGDCF's GNN encoder, which learns vertex representations by trading off two types of distances via a Markov process. We show the theoretical equivalence between MGDN's output and the optimal solution of a distance loss function, which can boost the optimization of CF models. MGDN can generalize state-of-the-art models such as LightGCN and APPNP, which are heterogeneous GNNs. In addition, MGDN can be extended to homogeneous GNNs with our sparsification technique. For optimizing MGDCF, we propose the InfoBPR loss function, which extends the widely used BPR loss to exploit multiple negative samples for better performance. We conduct experiments to perform detailed analysis on MGDCF. The source code is publicly available at https://github.com/hujunxianligong/MGDCF.


INTRODUCTION
Personalized recommendation systems are widely used by Internet applications to select items that can match users' preferences from a large number of candidate items. Collaborative filtering (CF) is a technique used by a lot of personalized recommendation systems. It assumes that if two users A and B are interested in the same item, user B is more likely to have A's preference on a different item than that of a random user. Neural collaborative filtering techniques leverage neural networks to learn vector representations of users State-of-the-art GNNs that can effectively exploit high-order neighbor information Can be considered as Markov processes for distance learning and items based on known user-item interactions, and the similarity between vector representations of users and items can reflect the preference of users on items. Neural collaborative filtering techniques have attracted researchers and engineers from various fields, and they have been used to build personalized recommendation systems for applications such as social networks [5,28,31,32], e-commerce [7,8,35], and Micro-video platforms [25,26]. In recent years, Graph Neural Networks (GNNs) have been utilized to build CF models and they have shown promising performance. Recent state-of-the-art GNN-based CF approaches simply attribute their performance improvement to the high-order neighbor aggregation ability of GNNs. However, we suppose that this should be further discussed since many powerful GNNs such as JKNet and DropEdge, which can effectively take advantage of high-order neighbor information on various tasks, show poor performance on the CF task. Figure 1 reports the performance of Matrix Factorization (MF) [12] and several 4-layer GNNs on the CF task, where MF is a fundamental CF model and the four GNN-based CF models simply extend MF by applying state-of-the-art GNNs on a heterogeneous user-item interaction graph for vertex representation learning. The four GNNs, including JKNet [29], DropEdge [20], APPNP [10], and S 2 GC [34], are powerful deep GNNs that can alleviate the oversmoothing problem to effectively take advantage of high-order neighbors, and S 2 GC is equivalent to the popular state-of-the-art GNN-based CF model LightGCN [3]. However, Figure 1 shows that JKNet and DropEdge show almost the same performance with MF, with only APPNP and S 2 GC(LightGCN) obtaining obvious performance improvements. This suggests that leveraging GNNs that can effectively exploit high-order neighbors will not necessarily result in superior performance on the CF task. Inspired by [33,34], we find that GNNs that show superior performance on CF tasks, such as APPNP and S 2 GC (LightGCN), can be considered as Markov processes that learn distances between vertex representations, which may explain their performance improvements.

No obvious improvement
In this paper, we investigate the GNN-based CF from the perspective of Markov processes for distance learning with a unified framework named Markov Graph Diffusion Collaborative Filtering (MGDCF). To generalize state-of-the-art models such as APPNP and LightGCN, we investigate the Markov processes associated with these models and design a Markov Graph Diffusion Network (MGDN) based on them. To explain MGDN, we show the theoretical equivalence between the output of MGDN and the optimal solution of a distance loss function, which can facilitate the optimization of CF models. In addition, we find that MGDN not only can generalize heterogeneous GNNs such as APPNP and LightGCN, but also can be extended to homogeneous GNNs with a sparsification technique. To optimize MGDCF, we propose the InfoBPR loss by simply extending the widely used Bayesian Personalized Ranking (BPR) loss [18] to support multiple negative samples, which improves the performance of MGDCF.
In summary, the contributions of this paper are as follows: •

RELATED WORK 2.1 Graph Neural Networks
Graph Neural Networks (GNNs) are proposed to perform deep learning on graphs. Early GNNs such as Graph Convolutional Networks (GCNs) [9], Graph Attention Networks (GATs) [23], and Graph-Sage [2] learn vertex representations by aggregating 1-hop neighbors. These GNNs exploit high-order neighbors via a traditional deep GNN architecture, which simply stacks multiple GNN layers with non-linear activations. However, these models may suffer from the over-smoothing problem when more than two GNN layers are used [1,6,9]; therefore, they can not effectively take advantage of high-order neighbor information. JKNet [29] and DropEdge [20] improve these models with skip connections and edge dropout, which effectively alleviate the over-smoothing problem. Recently, various Graph Diffusion Networks (GDNs) [11] have been proposed to directly deal with neighbors within K hops ( > 1) with one GNN layer, which is more efficient. Many powerful GNN models such as APPNP [10] and S 2 GC [34] are GDNs. With techniques such as Personalized PageRank [16], GDNs can obtain a propagation scheme for high-order neighbors that can avoid over-smoothing.

Neural Collaborative Filtering
Neural networks play an important role in modern collaborative filtering models. SLIM [15] and Multi-VAE [13] utilize linear autoencoders or deep autoencoders to encode known interactions and reconstruct scores of unknown interactions. Matrix factorization (MF) [12] is an essential collaborative filtering approach, which projects users and items as low-dimensional vector representations, and uses the dot product based distances between vector representations to reflect the relevance between users and items. MF can benefit from neural network techniques for efficient learning of vertex representations. Neural Collaborative Filtering (NCF) [4] suggests to replace the dot product with a similarity learned with a multilayer perceptron (MLP). However, research [19] shows that with a proper hyper-parameter selection, such as a proper coefficient of L2 regularization, a simple dot product substantially outperforms the proposed learned similarities, showing that it is non-trivial to improve MF models with deep neural networks.
With the development of GNN techniques, a lot of GNN-based CF research emerges, which can model the user-item interactions with bipartite graphs and exploit GNNs to learn representations for users and items. GCMC [21] exploits graph convolutional networks to aggregate neighbor information to build an auto-encoder for matrix completion. Pinsage [31] utilizes GNNs to encode both the graph structure and item features. It designs an efficient sampling strategy based on random walk, which enables it to handle largescale datasets. NGCF [24] is a deep GNN architecture consisting of multiple crafted graph convolutional layers, which can capture the interactions between each vertex and its neighbors. LightGCN [3] is a state-of-the-art GNN-based CF model, which removes the transformation and non-linear activations of graph convolutional layers and can effectively learn vertex representations via message propagation. Unlike these approaches, which focus on GNN architectures, some recent research design advanced loss functions to improve GNN-based CF models. Wu et al. introduce self-supervised graph learning (SGL) techniques into CF models [27] and implement it on the state-of-the-art model LightGCN. SGL relies on graph data augmentation to generate different views for a self-supervised learning (SSL) loss, which can exploit multiple negative samples for optimization. UltraGCN [14] resorts to replace explicit GNN layers with a constraint loss, which can directly approximate the limit of infinite-layer graph convolutions. UltraGCN's constraint loss also can exploit multiple negative samples.
Different from popular GNN-based CF research such as NGCF and LightGCN, which focus on designing deep GNN architectures to exploit high-order neighbors, we investigate the GNN-based CF from the perspective of Markov processes for distance learning with a unified framework named Markov Graph Diffusion Collaborative Filtering (MGDCF). Our unified framework can generalize state-of-the-art models such as Light-GCN and APPNP, which are heterogeneous GNNs, and it can also be extended to homogeneous GNNs with our sparsification technique. In addition, we propose InfoBPR to optimize MGDCF, which extends the widely used BPR loss to exploit multiple negative samples for better performance.

PRELIMINARY 3.1 Problem Definition
We focus on featureless collaborative filtering problems, where the attributes of users and items are unknown and only user-item interaction information is provided. Formally, a heterogeneous useritem interaction graph G = ( ∪ , ) is given, where and denote the set of users vertices and items vertices, respectively, and is the set of edges between users and items. Accordingly, we use and to denote the ℎ user vertex and the ℎ item vertex, respectively. In terms of the edge set = {( , )}, we use ( , ) to represent the edges between and , where the edges correspond to the observed interactions between users and items. Instead of , we employ a sparse adjacency matrix M → ∈ R | |× | | to represent edges for computation, where each element M → is set to 1 or 0 to denote whether the edge between the user and the item is observed. Given G, our model aims to predict unobserved interactions (edges) between user vertices and item vertices, which can reflect the potential interest of users.

Matrix Factorization and GNN-based Collaborative Filtering
Most GNN-based approaches such as LightGCN can be considered as extensions of the Matrix Factorization (MF) approach, which is a simple yet powerful baseline approach. Thus, we first introduce the MF approach. MF aims to embed user and item vertices into a low-dimensional continuous semantic space, where the distance between user and item vertices can reflect users' interests. Formally, MF employs an embedding table ∈ R × to model the learned low-dimensional features of users and items vertices, where is the number of vertices and ≪ . In terms of the optimization, is randomly initialized and then optimized with a combined loss L ( ) = L ( ) + Ψ 2 L 2 ( ) during training. The ranking loss L , such as Binary Cross-Entropy (BCE) [4] and Bayesian Personalized Ranking (BPR) [18], measures the relevance between users and items based on the doc product of learned embeddings of users and items, where larger dot product result corresponds to higher relevance. In addition, the L2 loss L 2 , which is multiplied with the L2 coefficient Ψ 2 , is also applied on the vertex representations , which is crucial for the performance of MF [19].
MF is extended by GNN-based CF approaches, which aims to learn high-order vertex representations ∈ R × by applying a GNN model on the embedding table ∈ R × . A GNN-based CF model can be represented as follows: where denotes the GNN model, and is the adjacency matrix of the constructed graph. For optimization, GNN-based approaches employ MF's loss function L and apply it on the learned highorder vertex representations instead of the embedding table , that is L ( ) = L ( ) + Ψ 2 L 2 ( ). In the official implementations of many GNN-based approaches, the L2 loss L 2 is usually applied on the GNN's parameters rather than its output . However, we empirically find that these GNN-based models can still achieve competitive performance with L 2 applied on instead of GNN's parameters. To simplify the analysis, in this paper, we only apply the L2 regularization on . , which learns vertex representations by trading off two types of distances via a Markov process. Then, we show that MGDN not only can generalize state-of-the-art models such as LightGCN and APPNP, which are heterogeneous GNNs, but also can be extended to homogeneous GNNs with our sparsification technique. Finally, we introduce the InfoBPR loss to optimize MGDCF, which extends the widely used BPR loss to exploit multiple negative samples for better performance.

Distance Learning with Markov Graph Diffusion Networks
In this section, we first introduce Markov Graph Diffusion Networks (MGDN) and then show how it is related to distance learning. Our approach is motivated by the fact that GNNs such as APPNP and LightGCN (S 2 GC) show superior performance on the CF task. Different from JKNet and DropEdge, which adopt a traditional deep GNN architecture that stacks multiple GCN layers to exploit highorder neighbor information, APPNP and LightGCN are Graph Diffusion Networks (GDNs), which directly handle neighbors within K hops ( > 1) with one GNN layer. Formally, a K-layer GDN can be defined by: where is the number of vertices, andˆ∈ R × is an affinity matrix of entriesˆdenoting the propagation weight from the ℎ vertex to the ℎ vertex. Note that on heterogeneous graphs, the affinity matrixˆdefines the relevance between users and items, while on homogeneous graphs, the affinity matrixˆdefines the relevance between users or the relevance between items. Many GDNs adopt GCN's normalization strategy and computeˆfollows: where˜= + and˜= < =0˜i s the degree matrix of˜. In addition, we observe that APPNP and LightGCN can be considered as a Markov Process related to distance learning of vertices, which is highly related to the CF task. Inspired by this, we design Markov Graph Diffusion Networks (MGDN) for distance learning by adding constraint on the coefficients { } of Equation 2 as follows: where Γ is used to for normalization to force =0 = 1.0: Equation 4 can be treated as a Markov Process as follows: → +∞, we have lim →+∞ˆ= 0, and the vertex representations converge as follows: which is also the optimal solution of the Normalized Laplacian Regularization [33] as follows: where the loss function L ( , ) can be considered as a distance loss function. As shown in Figure 2, L ( , ) constrains the output vertex representations by trading off two types of distances: •˜ √˜− √˜ 2 constrains the distances between the output vertex representations of linked vertices. Minimizing these distances increases the smoothness [6] of vertex representations over the graph, and they are highly related to the CF task whether on heterogeneous graphs or homogeneous graphs. and differentiating L with respect to , we have To find˜that can minimize L we solve the Equation below By introducing = 1 1+ , theñ By ignoring the scaling coefficients 1 − and Γ , we find that˜, which is the optimal solution of L , becomes the same as the vertex representations learned by MGDN (Equation 9). Note that the reason that the scaling coefficients can be ignored is that scaling the vertex representations will not affect the ranking of items, which is based on dot product. To arrive at a practical implementation, we implement MGDN in the form of a Markov Process (Equation 6, 7, and 8) since it only relies on efficient sparse matrix operations. This allows us to implement MGDN in the message-passing framework, which is widely adopted by GNN-based collaborative filtering models. Especially, MGDN generalizes some state-of-the-art GNN-based collaborative filtering models such as LightGCN and APPNP: • Relation of MGDN to LightGCN By setting = 1.0 and = 1.0, Equation 7 becomes ( ) =ˆ( −1) + (0) , and we have: which corresponds to LightGCN's implementation. Especially, such setting results in Γ = + 1, corresponding to LightGCN's mean pooling operation. • Relation of MGDN to APPNP By treating as the teleport probability of Personalized PageRank and setting = 1 − , Equation 7 becomes: and Γ = + (1 − ) −1 −1 = 1.0, which corresponds to APPNP's implementation.

Heterogeneous MGDN
MGDN can be applied on the heterogeneous user-item interaction graph (Hetero-MGDN). The middle part of Figure 2 corresponds to a HeteroMGDN. As shown in Figure 2, the distancẽ √˜− √˜ 2 that Hetero-MGDN tries to minimize corresponds to the distance between users and their interested items, which is directly related to the objective of CF tasks. To implement Hetero-MGCN, we first use to denote the adjacency matrix as follows: where (M → ) ′ denotes the transpose of M → . Then, we compute the affinity matrixˆwith Equation 3. Finally, we stack users' input embeddings and items' input embeddings to construct ∈ R ( | |+| |)× and then perform MGDN with andˆ. The stateof-the-art approaches LightGCN and APPNP can be considered as implementations of Hetero-MGDN.

Homogeneous MGDN
MGDN can also be applied on homogeneous graphs to handle CF tasks ( Figure 3). Homogeneous MGDN (Homo-MGDN) can achieve competitive performance with Hetero-MGDN by applying MGDN on a constructed homogeneous item-item graph that captures cooccurrence relations ( , ) between items. Note that although we can also construct a homogeneous graph for users, we empirically find that constructing a homogeneous item-item graph is sufficient and we can just use the input embedding as the vertex representations for users. As shown in the right part of Figure 3, the distance˜ √˜− √˜ 2 that Homo-MGDN tries to minimize corresponds to the distance between items that have high co-occurrence relations. Figure 3 shows the framework of Homo-MGDN. Based on the heterogeneous graph G, we construct a homogeneous item-item graph to model the relations between items. As with GCN, most Graph Diffusion Networks such as APPNP and S2GC are based on the assumption that the edge weight between and should represent an unnormalized joint probability ( , ). Approaches such as TextGCN [30] obtain ( , ) by scanning all the cooccurrence of and , which is time-consuming without parallel computation frameworks. Different from these approaches, we first build an item-item transition matrixM → to model the item-item conditional transition probability ( | ) (the left part of Figure 3), and then propose an efficient sparsification approach to approximate ( , ) withM → (the middle part of Figure 3). Our sparsification approach is efficient since it does not require calculating the exact value of ( , ). The sparsification involves some complex tricks and we describe the details in Section 5.2.
After sparsification, we obtain the adjacency matrix for a sparsified item-item graph. Based on , we compute the affinity matrixˆwith Equation 3 and simply apply MGDN on the sparse item-item graph to learn vertex representations for items.
The sparsification is crucial for Homo-MGDN not only because it can approximate ( , ) for homogeneous graph construction, but also because it can provide a sparse affinity matrix for efficient computation. As with [11], we can perform our model on sparsified affinity graphs without obvious performance degradation.

Optimization with InfoBPR Loss
Bayesian Personalized Ranking (BPR) loss [18] is a widely used ranking loss employed by many GNN-based CF models such as NGCF and LightGCN. BPR is defined as follows: where ( , ) computes the dot product between the learned vertex representations of user and item and ( ) = 1 1+ − is the sigmoid operation. The BPR loss can be transformed into the following form: where ∼ ( ) samples a random item vertex from with uniform distribution. Equation 18 shows that the BPR loss can be considered as a softmax loss function for binary classification tasks. Inspired by InfoNCE [22], we extend the BPR loss as a multi-class classification loss, with which our model can better maximize the mutual information between users and their interested items [17]. Our InfoBPR loss is defined as follows: where E { }∼ ( { }) samples a set of item vertices from with uniform distribution. When = 1, our InfoBPR loss becomes the BPR loss. With InfoBPR, we optimize MGDCF with a combined loss:

THEORETICAL ANALYSIS 5.1 MGDN Improves the Optimization of CF Models
In this section, we introduce how MGDN benefits CF models. We first introduce the domination of loss functions on CF tasks, which may cause the failure of GNNs on CF tasks. Based on this, we analyze why MGDN can obtain superior performance on CF tasks.

Domination of Loss Function.
As mentioned in Section 3.2, the same loss L is applied on the vertex representations for both MF and GNN-based approaches. Formally, we use * and * to denote the vertex representations optimized by MF and GNN-based approaches, respectively, which are as follows: Based on the above two Equations, we raise a question: Whether the learned vertex representations of GNN-based CF models are dominated by the loss function L , resulting in the same performance as MF? Here, the domination of L means that learning with MF (Equation 22) and GNN-based models (Equation 23) will result in the same performance, although GNN-based models introduces an extra condition that = ( , ) into Equation 23.
Theoretically, we can prove that L can dominate for GNNbased models if the following two conditions are satisfied: can be an arbitrary vector. Formally, for ∀ ∈ R , these exists a such that = ( , ).
Based on this and the fact that MDGN models (such as APPNP and LightGCN) are not dominated by MF and outperform MF with significant improvement (Figure 1), we can infer that the second condition of domination ("The objectives Equation 22 and Equation 23 are perfectly optimized") is not satisfied and attribute the performance improvement to the better optimization ability of the MGDN model. In Section 6.4.1, we empirically show that although MGDN does not apply any regularization on the vertex representation (Section 5.1.1), the distance loss may implicitly affect the optimizer and result in a more efficient and effective optimization.

Sparsification with Transition Probability
In this section, we provide details about our sparsification technique. First, we introduce how to obtain an item-item transition matrix to model the conditional transition probability between items ( | ).
Then, we introduce how it is exploited by our sparsification technique to approximate ( , ), which is intractable. Given the sparse interaction matrix M → , we can easily obtain the sparse user-item transition matrix as follows: where D → = < | | =0 M → is the diagonal degree matrix of users in the heterogeneous graph. The rows of M → are normalized and each elementM → ofM → is the transition probability from user to item , which is denoted as ( | ). Similarly, we can obtain the item-user transition matrix as follows: where M → = (M → ) ′ is the transpose of M → , and D → = < | | =0 M → is the diagonal degree matrix of items in the heterogeneous graph.
Given the two transition matriciesM → andM → , we can easily obtain the user-user transition matrix as follows: where each elementM → ofM → is a conditional probability ( | ). It is known that ( , ) is intractable if only the conditional probabilities ({ ( | )}) are provided. Therefore, we propose a sparsification approach to approximate ( , ) with these conditional transition probabilities.
Our sparsification approach approximates ( , ) with the following steps: • First, we compute the affinity weights (propagation weights) between vertices based on GCN's propagation scheme, which is also used by most Graph Diffusion Networks such as APPNP and S 2 GC. • Then, we sparsify the item-item graph by keeping a small portion (100 − )% of edges with the highest affinity weights and removing the remaining % edges. • Finally, we use 1.0 to approximate ( , ) for the kept edges.
Although the above steps seem to be simple, it is still a non-trivial task, since the sparsification relies on the affinity weights, while existing approaches usually obtain the affinity weights based on ( , ) (the edge weights), which is what we want to approximate and is intractable. To address the problem, we design a solution that can sort the affinity weights without calculating the exact value of ( , ). GCN's affinity weight defined in Equation 3 corresponds to the following equation in the form of probability: GivenM → , we can efficiently obtainˆas follows: whereM → ⊙ (M → ) ′ denotes the Hadamard product (elementwise product) ofM → and its transpose, and (·) ⊙ 1 2 denotes the  Hadamard power of an matrix. SinceM → = ( | ), the elements ofˆobtained by Equation 29 can be defined as follows: Equation 29 obtains the affinity weight of GCN's propagation scheme in Equation 28 and does not require calculating the intractable ( , ). As mentioned before, we then remove % of edges based on the values ofˆ, and use 1.0 to approximate the unnormalized ( , ) as the edge weights for the remaining edges. After removing the self-loops, we obtain the adjacency matrix for the sparsified item-item graph, which is denoted as . Figure 4 shows the distribution of affinity weights before sparsification on two datasets, where the orange lines denote the thresholds for sparsification. The affinity weights exhibit long tail distributions on both datasets, and only a small portion of edges are assigned with high affinity weights. For the two datasets, we set % = 97% to remove 97% of the edges, which are on the left side of the orange lines in Figure 4, and use 1.0 to approximate the edge weights of the remaining 3% edges on the right side of the orange lines.

EXPERIMENT
This paper focuses on building a unified framework to generalize some state-of-the-art GNN-based CF models such as APPNP and LightGCN. In this section, we conduct experiments to perform detailed analyses of each component of our unified framework. We implement MGCDF with TensorFlow 1 and the source code is publicly available 2 .

Datasets and Baselines
We conduct experiments with three publicly available benchmark datasets, including Gowalla, Yelp2018, and Amazon-Book [3,24]. The three datasets are used by popular GNN-based CF approaches such as NGCF and LightGCN. The statistics of the three datasets are shown in Table 1. Some of the baselines are optimized with the BPR loss, including: • MF [12]: MF is a fundamental CF model and all the GNNbased baselines are built upon MF. • NGCF [24], JKNet [29], and DropEdge [20]: There GNNbased CF models adopt a traditional deep GNN architecture, which stacks multiple GNN layers together with non-linear activations and residual connections. • APPNP [10] and LightGCN [3]: These models are stateof-the-art GNN-based CF models, and they can be considered as implementations of our unified MGDN model.
Since Hetero-MGDCF and Homo-MGDCF are optimized with In-foBPR, we also introduce baselines optimized with advanced ranking losses, including: • SGL-ED [27]: SGL-ED relies on graph data augmentation to generate different views for a self-supervised learning (SSL) loss, which can exploit multiple negative samples for optimization. Note that the performance of SGL-ED is not reported in Table 2 and 3 due to the lack of official results for SGL-ED under = 4. • UltraGCN and UltraGCN [14]: UltraGCN directly approximates the limit of infinite-layer graph convolutions with a constraint loss, which also can take advantage of multiple negative samples. As with most of our baselines and Hetero-MGDCF, UltraGCN is a heterogeneous GNN that only considers user-item relations. However, UltraGCN is a hybrid model that combines heterogeneous and homogeneous GNNs to incorporate different types of relations, which is not investigated by this paper. Therefore, the performance of UltraGCN is only reported in Table 4 and discussed in Section 6.4.3.

Evaluation Metrics and Parameter Settings
We employ normalized discounted cumulative gain (NDCG@20) and Recall@20 as evaluation metrics, which are also adopted by other state-of-the-art approaches such as LightGCN [3] and Ul-traGCN [14]. In terms of the parameter settings, we set (the dimensionality of both the input embeddings and the output vertex representations ) to 64 for all the approaches except for NGCF, which learns ( +1) -dimensional vector representations by concatenating the input embeddings and the output of K GNN layers. We set = 2 for Homo-MGDCF and = 4 for all other models. Note that a K-layer Homo-MGDCF can exploit neighbors within hops in the constructed homogeneous graphs, which correspond to neighbors within 2 hops in the heterogeneous graphs. For Hetero-MGDCF and Homo-MGDCF, we set = 0.1 and = 0.9; therefore, their GNN encoder MGDN is equivalent to an APPNP model. For other hyper-parameters such as the dropout rates, their settings may be different across different models and different datasets. This is because different models may rely on different hyper-parameter settings to achieve their best performance. More details about the parameter settings can be found in the source code. Table 2 and Table 3 show the performance of different approaches. From the results, we have the following observations:

Performance Analysis
• NGCF, JKNet, and DropEdge are deep GNNs and they perform almost the same with MF, showing that it is non-trivial to improve CF models with GNNs. Especially, JKNet and    DropEdge are powerful deep GNNs that can effectively take advantage of high-order neighbor information, and they obtain no obvious performance improvement, verifying that exploiting high-order neighbors with GNNs will not necessarily result in superior performance on the CF task.

Detailed Analysis
6.4.1 Impact of MGDN. We show the performance of MF and several GNN-based CF models during optimization in Figure 5. In this section, we focus on approaches optimized with BPR loss, including MF, JKNet, DropEdge, APPNP (MGDN), and LightGCN (MGDN). We implement APPNP and LightGCN as Hetero-MGDN models and adopt the loss function described in Section 3.2, which is different from the official implementation and results in slight differences in performance.
In Figure 5, all the GNN-based models converge faster than MF, showing that GNNs may implicitly affect the optimization. However, the final performance of JKNet and DropEdge is only slightly higher than MF, showing that the performance of these GNN models is dominated by the loss function L . APPNP and LightGCN are Hetero-MGDN models, and they lead to not only a faster optimization, but also a better optimization result. This shows that although MGDN does not apply any regularization on the vertex representation (Section 5.1.1), the distance loss L (Equation 10) may implicitly affect the optimization and result in a more efficient and effective optimization.

Impact of Homogeneous Graph Construction for Homo-MGDCF.
Homo-MGDCF constructs a sparse homogeneous item-item graph via sparsification, and we use % to denote the percentage of edges removed by sparsification. We vary % from 95.0% to 99.99% and report the performance of Homo-MGDCF in Figure 6, where the blue lines represent the performance of Hetero-MGDCF. The results show that Homo-MGDCF can achieve competitive performance with Hetero-MGDCF with sparse item-item graphs of % ≤ 97%. When we remove more edges by increasing % from 97.0% to 99.99%, the performance of Homo-MGDCF becomes worse than Hetero-MGDCF on the Gowalla and Yelp2018 datasets. However, on the Amazon-Book dataset, the performance first increases and reaches the max value when % = 99.9%, and then declines when varying % from 99.9% to 99.99%. Especially, Homo-MGDCF outperforms Hetero-MGDCF with significant improvement when % = 99.9%. This shows that our sparsification approach has the potential ability to suppress noisy relational information with a proper setting of %.
6.4.3 Impact of InfoBPR lOSS. As shown in Figure 5, Hetero-MGDCF and Homo-MGDCF, which are optimized with InfoBPR loss, converge extremely faster than other approaches, which are optimized with the BPR loss. Moreover, Figure 5 also shows that InfoBPR also enables Hetero-MGDCF and Homo-MGDCF to obtain superior optimization results with significant performance improvement. This shows that InfoBPR can result in a more efficient and effective optimization than BPR.
We also compare InfoBPR with other loss functions besides BPR. Table 4 shows the performance of models optimized with advanced loss functions that support multiple negative samples, including SGL-ED, UltraGCN , UltraGCN, Hetero-MGDCF, and Homo-MGDCF. Here we report performance under = 3 due to the lack of official results for SGL-ED under = 4. SGL-ED introduces a self-supervised learning (SSL) loss, which relies on extra data augmentations and needs to be used together with the BPR loss. UltraGCN adopt a well-crafted ranking loss that carefully assigns different weights for different negative samples. Compared to these losses, our InfoBPR loss is way simpler and it simply extends the BPR loss to support multiple negative samples. Despite In-foBPR's simplicity, our models Hetero-MGCDF and Homo-MGCDF can achieve competitive performance with UltraGCN and SGL-ED across different datasets, showing that InfoBPR is a simple yet powerful ranking loss. In terms of UltraGCN, it is a hybrid model that combines heterogeneous and homogeneous GNNs to incorporate different types of relations, which is not investigated by this paper. Although such a combination brings UltraGCN superior performance on the Amazon-Book dataset, our Hetero-MGCDF and Homo-MGCDF still can match UltraGCN on Gowalla and Yelp2018. In this paper, we only investigate heterogeneous or homogeneous GNNs, and we will consider hybrid models that combine heterogeneous and homogeneous GNNs in the future.

CONCLUSIONS
In this paper, we investigate the GNN-based CF from the perspective of Markov processes for distance learning with a unified framework named Markov Graph Diffusion Collaborative Filtering (MGDCF). We show that state-of-the-art GNN-based CF approaches such as APPNP and LightGCN can be generalized with a Markov process that trades off two types of distances, which can boost the optimization of CF models. We also verify that such a Markov process can be used to build both heterogeneous GNNs and homogeneous GNNs for the CF task, and these GNNs can further benefit from the advanced ranking loss InfoBPR to achieve superior performance. In the experiments, we have some interesting observations. For example, our homogeneous graph construction strategy may implicitly suppress the noisy information. In the future, we will investigate these observations to further extend our unified framework.