Learning Vertex Representations for Bipartite Networks

Recent years have witnessed a widespread increase of interest in network representation learning (NRL). By far most research efforts have focused on NRL for homogeneous networks like social networks where vertices are of the same type, or heterogeneous networks like knowledge graphs where vertices (and/or edges) are of different types. There has been relatively little research dedicated to NRL for bipartite networks. Arguably, generic network embedding methods like node2vec and LINE can also be applied to learn vertex embeddings for bipartite networks by ignoring the vertex type information. However, these methods are suboptimal in doing so, since real-world bipartite networks concern the relationship between two types of entities, which usually exhibit different properties and patterns from other types of network data. For example, E-Commerce recommender systems need to capture the collaborative filtering patterns between customers and products, and search engines need to consider the matching signals between queries and webpages. This work addresses the research gap of learning vertex representations for bipartite networks. We present a new solution BiNE, short for Bipartite Network Embedding, which accounts for two special properties of bipartite networks: long-tail distribution of vertex degrees and implicit connectivity relations between vertices of the same type. Technically speaking, we make three contributions: (1) We design a biased random walk generator to generate vertex sequences that preserve the long-tail distribution of vertices; (2) We propose a new optimization framework by simultaneously modeling the explicit relations (i.e., observed links) and implicit relations (i.e., unobserved but transitive links); (3) We explore the theoretical foundations of BiNE to shed light on how it works, proving that BiNE can be interpreted as factorizing multiple matrices. We perform extensive experiments on five real datasets covering the tasks of link prediction (classification) and recommendation (ranking), empirically verifying the effectiveness and rationality of BiNE. Our experiment codes are available at: https://github.com/clhchtcjj/BiNE.


INTRODUCTION
N ETWORK provides a ubiquitous data structure to model interactions (i.e., edges) among entities (i.e., vertices), having been widely used in many applications such as social networks [2], knowledge graphs [3], recommender systems [4], among others [5]. However, performing predictive analytics or mining knowledge directly on networks exhibits several challenges, such as high computation complexity, low parallelizability, and inapplicability of machine learning methods [6]. To handle these challenges, substantial works focused on network representation learning (NRL). In particular, they represent a vertex as a learnable embedding vector, where the proximity between vectors encodes the information about network structure. Thus the vertex embedding can be fed into machines learning methods to address various task such as ranking, link prediction, clustering, visualization and so on.
Recent advances in NRL have primarily focused on homogeneous network like social networks where vertices having the same type [7], [8], [9], [10], or heterogeneous networks like knowledge graphs where vertices (and/or edges) are of different types [11], [12], [13]. The effectiveness and prevalence of DeepWalk [8] inspire many works [8], [14] typically apply a two-step solution: 1) performing random walks, such as based random walk [14] or meta-path-based random walk [11], on the network to obtain a "corpus" of vertices; 2) applying embedding methods on the corpus such as word2vec [15] to obtain the embeddings for vertices.
However, there has been relatively little research dedicated to NRL for bipartite networks, for which there are two types of vertices [16]. While generic network embedding methods like DeepWalk and node2vec can be applied to learn vertex representation for bipartite networks by ignoring the the vertex type information, we argue that these methods are suboptimal in doing so because of two reasons. (1) Real-world bipartite networks concern the relationship between two types of entities, which usually exhibit different properties and patterns from other types of network data. For example, E-Commerce recommender system models the collaborative filtering patterns between customers and products, and Web search engine considers the matching signals between queries and webpages. (2) The generated corpus may not preserve the characteristics of the bipartite network. The power-law distribution is a common characteristic of many real-world bipartite networks [17], but the corpus generated by a universal random walk algorithm may not preserve this property, such as the one used in DeepWalk [8]. Specifically, it generates the same number of random walks starting from each vertices and constrains the length of random walks to be the same, which may limit the the information of vertices with high degree and oversample vertices with low degree.
To address the limitations of exiting methods on embedding bipartite networks, we devise a new solution for learning vertex representation in bipartite networks, namely BiNE (short for Bipartite Network Embedding). We summarize the main contributions of this work as follows. 1) We propose a biased and self-adaptive random walk generator to preserve the long-tail distribution of vertex in bipartite networks as much as possible. Specifically, we set the number of random walks starting from each vertex based on its importance and allow each walk to be stopped in a probabilistic way instead of setting a uniform length for all random walks. 2) We propose a joint optimization framework to model the explicit and implicit relations simultaneously. Specifically, we devise a dedicated objective function for each relation and optimize them by sharing the embedding vectors, where different relations reinforce each other and lead to better vertex embeddings. 3) We reveal the theoretical foundation of BiNE, which can be interpreted as implicitly factorizing multiple matrices, offering a better understanding how BiNE works. 4) We perform extensive experiments on several real datasets covering the tasks of links prediction (classification), recommendation (personalized ranking), and visualization, to illustrate the effectiveness and rationality of BiNE. A preliminary version of this work has been published in the conference of SIGIR 2018 [1]. We summarize the main changes as follows: 1) Introduction (Section 1). We have reconstructed the abstract and introduction to highlight the motivations of the extended version. 2) Theoretical foundations (Section 4). We explore the theoretical foundations of BiNE to shed light on how it works, proving that BiNE can be interpreted as factorizing multiple matrices. 3) Experiments (Section 5). We add experiments to verify the proof, showing that the factorization-based implementation can achieve the same level of performance as BiNE in Section 5.3. In addition, we explore the performance of BiNE with different negative sampling strategies to justify our sampler design in Section 5.5. The remainder of the paper is organized as follows. We first formulate the problem in Section 2, before delving into details of the method in Section 3. We show the theoretical connections with factorization methods in Section 4 and perform empirical studies in Section 5. We review related work in Section 6 before concluding the paper in Section 7.

PROBLEM FORMULATION
We first give notations used in this paper, and then formalize the bipartite network embedding problem to be addressed. Notations. Let G = (U, V, E) be a bipartite network, where U and V denote the set of the two types of vertices respectively, and E ⊆ U × V defines the inter-set edges. u i and v j denote the i-th and j-th vertex in U and V , respectively, where i = 1, 2, ..., |U | and j = 1, 2, ..., |V |. Each edge carries a non-negative weight w ij , describing the strength between the connected vertices u i and v j ; if u i and v j are not connected, the edge weight w ij is set to zero. Therefore, we can use a |U | × |V | matrix W = [w ij ] to represent the weighted structure of the bipartite network. Problem Definition. The aim of bipartite network embedding is to map all vertices in the network into a lowdimensional embedding space, where each vertex is represented as a dense vector. In the embedding space, both the implicit relations between vertices of the same type and the explicit relations between vertices of different types should be preserved. Formally, the problem can be defined as: Input: A bipartite network G = (U, V, E) and its weight matrix W. Output: A mapping function f : U ∪ V → R d , which maps each vertex in G to a d-dimensional embedding vector. To keep the notations simple, we use u i and v j to denote the embedding vectors for vertices u i and v j , respectively. As such, we can present the embedding vectors of all vertices in the bipartite network as two matrices U = [ u i ] and V = [ v j ].

BINE: BIPARTITE NETWORK EMBEDDING
The typical objective in learning vertex embeddings is to be capable of reconstructing the network structure well [8], [14]. While the structure of normal networks is mostly reflected in the observed edges, the case is more complicated for bipartite networks -two vertices of the same type are not directly connected, but it doesn't necessarily mean that they do not have relation. This poses challenges to bipartite network embedding, such that modeling only observed edges is insufficient to retain the fidelity. Towards this end, we propose to account for both the observed edges (Section 3.1 Modeling Explicit Relations) and the unobserved but transitive edges (Section 3.1 Modeling Implicit Relations). The final vertex embeddings are achieved by jointly optimizing the two tasks (Secion 3.3 Joint Optimization).

Modeling Explicit Relations
Edges between vertices of different types in a bipartite afford us a signal to capture the explicit structure information. Similar to the modeling of 1st-order proximity in LINE [18], we preserve the explicit structure information by minimizing the difference between the empirical distribution of vertex co-occurring probability and the reconstructed distribution by the vertex embeddings. The co-occurring probability between two connected vertices u i and v j in the original bipartite network is defined as: where w ij is the weight of edge e ij . In addition, the local proximity between them in the embedding space can be estimated by their inner product [8], [14], [18], we further transform this interaction value to the probability space by the sigmoid function: where u i ∈ R d and v j ∈ R d are the embedding vectors of vertices u i and v j , respectively. After getting the empirical distribution and the reconstructed distribution, we employ the KL-divergence to measure the difference between the two distributions, and learn the embedding vectors by minimizing the difference. Thus the objective function can be defined as: Intuitively, two strongly connected vertices in the original network will be close with each other in the embedding space by minimizing the objective function. Thus the explicit structure information can be preserved.

Modeling Implicit Relations
The effectiveness of modeling implicit relations in recommendation [19], [20] (which deals with user-item bipartite network) motivates us to explore the implicit relations in bipartite networks towards real-world applications. Although a perfect reconstruction of explicit relations can fully recover the implicit relations, it is impractical to rely on this. As such, we speculate that modeling the implicit relations between vertices of the same type could bring extra benefits to explicit relation modeling. Intuitively, if there exists a path between two vertices, it implies certain implicit relation between them; the number of the paths and their length indicate the strength of the relation. However, counting the paths between two vertices comes at the cost of very high complexity, which is unaffordable for large-scale networks.
To encode such high-order implicit relations among vertices in a bipartite network, we resort to the solution of Deep-Walk. To be exact, the bipartite network is first converted to two corpora of vertex sequences by performing random walks; then the embeddings are learned from the corpora which encodes high-order relations between vertices.

Constructing Corpus of Vertex Sequences
It is a common way to convert a network into a corpus of vertex sequences by performing random walks on the network, which has been used in some homogeneous network embedding methods [8], [14]. However, directly performing random walks on a bipartite network could fail, since there is no stationary distribution of random walks on bipartite networks due to the periodicity issue [21]. To address this issue, we consider performing random walks on two homogeneous networks that contain the 2nd-order proximity between vertices of the same type. Following the idea of Co-HITS [22], we define the 2nd-order proximity between two vertices as: where w ij is the weight of edge e ij . Hence, we can use the ij ] to represent the two induced homogeneous networks, respectively. Now we can perform truncated random walks on the two homogeneous networks to generate two corpora for learning the high-order implicit relations. To generate a corpus with a high fidelity, we propose a biased and selfadaptive random walk generator, which can preserve the vertex distribution in a bipartite network. We highlight its core designs as follows: • First, we relate the number of random walks starting from each vertex to be dependent on its importance, which can be measured by its centrality. For a vertex, the greater its centrality is, the more likely a random walk will start from it. As a result, the vertex importance can be preserved to some extent. • We assign a probability to stop a random walk in each step. In contrast to DeepWalk and other work [11] that apply a fixed length on the random walk, we allow the generated vertex sequences have a variable length, in order to have a close analogy to the variable-length sentences in natural languages.
Generally speaking, the above generation process follows the principle of "rich gets richer", which is a physical phenomena existing in many real networks, i.e., the vertex connectivities follow a scale-free power-law distribution [23]. The workflow of our random walk generator is summarized in Algorithm 1, where maxT and minT are the maximal and minimal numbers of random walks starting from each vertex, respectively. D U (or D V ) output by Algorithm 1 is the corpus generated from the vertex set U (or V ). The vertex centrality can be measured by many metrics, such as degree centrality, PageRank and HITS [24], etc., and we use HITS in our experiments.

Implicit Relation Modeling
After performing biased random walks on the two homogeneous networks respectively, we obtain two corpora of vertex sequences. Next we employ the Skip-gram model [15] on the two corpora to learn vertex embeddings. The aim is to capture the high-order proximity, which assumes that vertices frequently co-occurred in the same context of a sequence should be assigned to similar embeddings. Given a vertex sequence S and a vertex u i , the context is defined as the ws vertices before u i and after u i in S; each vertex is associated with a context vector θ θ θ i (or ϑ ϑ ϑ j ) to denote its role as a context. As there are two types of vertices in a bipartite network, we preserve the high-order proximities separately. Specifically, for the corpus D U , the conditional probability to maximize is: where C S (u i ) (or C S (v j )) denotes the context vertices of vertex u i (or v j ) in a sequence S.
Following existing neural embedding methods [8], [14], [18], we parameterize the conditional probability P (u c |u i ) and P (v c |v j ) using the inner product kernel with softmax for output: where P (u c |u i ) denotes how likely u c is observed in the contexts of u i ; similar meaning applies to P (v c |v j ). With this definition, achieving the goal defined in Equations (5) will force the vertices with the similar contexts to be close in the embedding space. Nevertheless, optimizing the objectives is non-trivial, since each evaluation of the softmax function needs to traverse all vertices of a side, which is very timecosting. To reduce the learning complexity, we employ the idea of negative sampling [15].

Negative Sampling
The idea of negative sampling is to approximate the costly denominator term of softmax with some sampled negative instances [25]. Then the learning can be performed by optimizing a point-wise classification loss. For a center vertex u i , high-quality negatives should be the vertices that are dissimilar from u i . Towards this goal, some heuristics have been applied, such as frequency-based negative sampling method proposed to learn the representations for words [15]. Specifically, words with high frequency have large probability of being chosen as negative instances, which is suitable for language model since high frequency words are useless words such as he, she, it, is, the, etc. Nevertheless, high frequency vertices in bipartite networks are often the most important entities, such as popular items or active users, and the tracing phenomenon widely exiting in user buying and watching behaviors indicates us that it might be suboptimal to simply treat the high frequency vertices as negative instances. Here we propose a more grounded sampling method that caters the network data. First we employ locality sensitive hashing (LSH) [26] to block vertices after shingling each vertex by its ws-hop neighbors with respect to the topological structure in the input bipartite network. Given a center vertex, we then randomly choose the negative samples from the buckets that are different from the bucket contained the center vertex. Through this way, we can obtain high-quality and diverse negative samples, since LSH can guarantee that dissimilar vertices are located in different buckets in a probabilistic way [26].
Let N ns S (u i ) denote the ns negative samples for a center vertex u i in sequence S ∈ D U , we can then approximate the conditional probability p(u c |u i ) defined in Equation (6) as: where the probability P (z|u j ) is defined as: where σ denotes the sigmoid function 1/(1 + e −x ). By replacing p(u c |u i ) in Equation (5) with the definition of p(u c , N ns S (u i )|u i ), we can get the approximated objective function to optimize. The semantics is that the proximity between the center vertex and their contextual vertices should be maximized, whereas the proximity between the center vertex and the negative samples should be minimized.
Following the similar formulations, we can get the counterparts for the conditional probability p(v c |v j ), the details of which are omitted here due to space limitation.

Joint Optimization
To embed a bipartite network by preserving both explicit and implicit relations simultaneously, we combine their objective functions to form a joint optimization framework.
where parameters α, β and γ are hyper-parameters to be specified to combine different components in the joint optimization framework.
To optimize the joint model, we utilize the Stochastic Gradient Ascent algorithm (SGA). Note that the three components of Equation (8) have different definitions of a training instance. To handle this issue, we tweak the SGA algorithm by performing a gradient step as follows: Step I: For a stochastic explicit relation, i.e., an edge e ij ∈ E, we first update the embedding vectors u i and v j by utilizing SGA to maximize the last component L 1 = −γO 1 . We give the SGA update rule for u i and v j as follows: Step II: We then treat vertices u i and v j as the center vertex; by employing SGA to maximize objective functions L 2 = α log O 2 and L 3 = β log O 3 , we can preserve the implicit relations. Specifically, given the center vertex u i (or v j ) and its context vertex u c (or v c ), we update their embedding vectors u i (or v j ) as follows: where I(z, u i ) is an indicator function that determines whether vertex z is in the context of u i or not; similar meaning applies to I(z, v j ). Furthermore, the context vectors of both positive and negative instances are updated as: We use the embedding vectors as the representations of vertices. Concatenating the embedding and contextual vectors for each vertex may improve the representations, which we leave as future work.

Discussion
Computational Complexity Analysis. The corpus generation and joint model optimization are two key processes of BiNE. Here we discuss the computational complexity of the two processes respectively.
For the large-scale network, the complexity of generating corpus will increase since W U and W V become large and dense. To avoid processing the dense matrix, we directly perform two-step walk in the original bipartite network to generate corpora. Let vc denotes the visitation count of vertex v in the generated corpus. The context size is therefore vc · 2ws, which is a big value for vertices having high degrees. Yet we only randomly select a small batch, e.g., bs (bs vc), of the contextual vertices for each center vertex. Thus, the complexity of algorithm is O(2|E| · bs · 2ws · (ns + 1)). To some extent, all the contextual vertices of a center vertex can be trained in each iteration by setting a proper bs, because the center vertex will be visited more than once when traversing all edges. Consequently, the performance is also guaranteed while the executive efficiency of BiNE is greatly improved.

BINE AS FACTORIZING MULTIPLE MATRICES
Prior efforts have revealed that several network embedding methods like DeepWalk, LINE and node2vec can be understood as performing factorization on some purposefully designed matrices [27]. The fundamental reason is that these methods use inner product to measure the affinity of two vertices, which also forms the basis of matrix factorization [28]. In this section, we prove that the BiNE embeddings are optimized towards the objective of factorizing multiple matrices, establishing the connections between BiNE and matrix factorization.

Derivation of the Implicit Matrices
In the following analysis, let

Global Objective Functions
The optimization of log O 2 in Equation (8) is trained in an online fashion via stochastic gradient updates over the observed pairs (u i , u j ) in the corpus D U . Its global objective can be obtained by summing over the observed (u i , u j ) pairs in the corpus [29]: where which is the local objective function for a single centercontext vertex pair (u i , u j ). Let u i T θ θ θ j . = x U ij , then the local objective function uu (i, j) can be treated as a function of x U ij , in which the value of each term is mutually independent. Therefore, uu (i, j) can be simplified as: In BiNE, for each center vertex u i , its negative sample u j is uniformly sampled from N ns S (u i ). Thus, based on the importance sampling, the second term of Equation (14) can be approximated by the conditional expectation given where p(j ) = 1 ns is a conditional probability when u j samples from N ns S (u i ). Unfortunately, the conditional expectation is a random variable related to the center vertex u i , rather than a constant. As a result, the log-likelihood log O 2 in Equation (12) cannot be maximized directed. Therefore, we employ the EM-algorithm to maximize the log-likelihood log O 2 . E-Step: The expectation of uu (i, j) is: As mentioned in Section 3.2.3, the LSH-based negative sample u j is sampled from the bucket that is different from the bucket contained the center vertex u i . Let J ij be the Jaccard similarity between vertices u i and u j , then the probability, that u i and u j are mapped into the different buckets, can be computed as q(u i , u j ) = (1−(J ij ) k ) b , where b and k denote the number of # bands and the number of # rows in each band, which are two hyper-parameters in the LSH. It is noteworthy that the vertices are mapped into the same bucket of LSH with larger probability if they have a higher proximity. That is, given the center vertex u i , a context vertex is mapped to the different buckets with a small probability. Since both q(u i , u j ) and the number of context vertices are small, E[ uu (i, j)] can be approximated as: Naturally, the expectation of the log-likelihood function log O 2 can be approximated as: The optimal solution (x U ij ) * can be obtained if we maximize the expectation of log-likelihood log O 2 .
Moreover, the solution of = 0 can be calculated in a closed form as follows: In Equation (21), (x U ij ) * can be rewritten as where q(u i , u j ) is the probability that u i and u j are mapped into the different buckets in the LSH, and is the conditional probability, which can represent the proximity of center-context pair (u i , u j ) in the corpus D. (x U ij ) * tends to be a larger value if u i and u j are vertex pair with a higher proximity. This is due to the fact that p(u j |u i ) is larger and q(u i , u j ) is smaller in this case.
Similarly, we can obtain the optimal solution of (x V ij ) via maximizing log O 3 :

Approximating the Implicit Matrices
Based on the above analysis, we obtain the maximum likelihood estimation (MLE) of log O 2 by setting u i T θ θ θ j = (x U ij ) * for every center-context pair (u i , u j ). Let M U ij = (x U ij ) * be a weight which evaluates how similar between u i and u j in the embedding space. To learn the representation of vertex u i , we only need to factorize the matrix M U . Thus, the vertex learning problem is cast as a matrix factorization issue. For learning the representation of vertex v i , it can be done in the same manner.
Note that, As indicated in the above equations, we need to generate the vertex sequences for deriving the matrices M U and M V . As illustrated in subsection 5.3, the parameters for generating vertex sequences are dependent on the size of dataset. Thus, they are difficult to tune in practice. To avoid generating the vertex sequences, we approximate where ws is the window size, w is the center vertex and c is a context vertex of w. #(w, c), #(w) and #(c) denote the number of times that the center-context pair (w, c), center vertex w and context c appear in the corpus, respectively.

Lemma 2. Suppose that f (x) is a continuous function, and
Then, we have Theorem 1. Let P be the transition matrix of a random walk, and D be the generated corpus. When L D → ∞, we have Proof. Since f (x) = 1 x is a continuous function, thus According to the Lemma 1 and 2, we have Moreover, the above equation can be rewritten in the matrix form as follows: Thus, we can obtain Using the Theorem 1 on BiNE, we have where P U and P V are the transition matrix of the two homogeneous networks in BiNE. Further, the optimal solution (x U ) * and (x V ) * are replaced as: Finally, the matrix M U and M V are approximated as: However, the matrices M U and M V are not only illdefined since log 0 = −∞, but also they are dense, which leads to a computational challenge of factoring the matrices M U and M V by element-wise algorithms. Inspiring by the shifted PPMI approach [29] In this way, M U and M V become sparse matrices.

Co-factorizing Multiple Matrices
Overall, the proposed BiNE algorithm with LSH-based negative sampling can be transferred into another one in a closed form, namely BiNE-MF, which learns the vertex representation via employing the matrix factorization.
In detail, BiNE-MF can be regarded as jointly factorizing three matrices: the weighted matrix W and two complement matrices M' U , M' V , where W preserves the explicit relations in the bipartite network, and both M' U and M' V preserve the implicit relations in the bipartite network. As shown in Fig. 1, the matrix M U shares the vertex embedding matrix of U with W and the matrix M V shares the vertex embedding matrix of V with W. We set H, A, B as where O can be any matrix (i.e., loss will be zero when matrix O is reconstructed), α and β are scaling parameters to balance the importance of explicit and implicit relations. Interestingly, matrix α U = [ θ θ θ i ] and β V = [ ϑ ϑ ϑ j ] can be viewed as the context embedding matrices of U and V , respectively.
Once we obtain the matrix H, we can use symmetric SVD [29] or SMF (stochastic matrix factorization) [30] to map the vertices into a low-dimensional space and obtain the embedding matrices U and V.

Effect of Negative Sampling
As mentioned in Equation (23), LSH-based negative sampling method used in BiNE is implicitly factorizing where q(w, c) is the probability that w and c locate in the different buckets of LSH. In contrast, the frequencybased negative sampling method in SGNS [29] is implicitly factorizing Here, #(w,c) #(w) = p(c|w) represents the proximity of centercontext pair (w, c) in the corpus D. Moreover, both q(w, c) and #(c) |D| can be treated as penalty factors which contribute to measure the proximity of center vertex with its context vertices.
Assume that w and c have higher proximity, i.e., P (c|w) is larger. Then, q(w, c) used in BiNE will be smaller due to the lower probability of mapping w and c into different buckets. In this case, log #(w,c) #(w)·q(w,c) − log ns will be larger. However,

#(c)
|D| used in SGNS is undetermined since its value can be large or small. Furthermore, the large value of log #(w,c)·|D| #(w)·#(c) − log ns biases c towards infrequent vertices, which may be inconsistent with our intuition.

Computational Complexity Analysis
Computing the matrices M U (or M V ) directly is a challenging task when the homogeneous network is large and dense or the window size is large. We resort to the approximation algorithm proposed in the work [27] to reduce the computation complexity. Unlike the online training method BiNE, the MF-based methods, such as SMF and BiNE-MF, work over aggregated center-context pair statistics using triples as input, which makes the optimization more directly and salable to large bipartite networks.

EXPERIMENTS
In this section, we perform experiments on real-world datasets with the aim of answering the following research questions: RQ1 How does BiNE perform compared with state-of-theart network embedding methods? RQ2 Can the MF-based methods, such as symmetric SVD, SMF, and BiNE-MF, achieve similar performance as that of BiNE?
RQ3 Can our proposed random walk generator contribute to preserving the long-tail distribution of vertex in bipartite networks and the implicit relations mined by it be helpful to learn better vertex representations? RQ4 Does LSH-based negative sampling strategies superior to the frequency-based strategies in modeling bipartite networks? The following sections will illustrate the experimental settings before answering the above research questions. In addition, a case study that visualizes a small bipartite network is performed to demonstrate the rationality of BiNE.

Datasets
We purposefully chosen unweighted networks for link prediction, which is usually approached as a classification task that predicts whether a link exists between two vertices; while we use weighted networks for recommendation task, which is a personalized ranking task that aims to provide items of interest for a user. 1) Unweighted bipartite network. We construct two unweighted bipartite networks from Wikipedia and Tencent, respectively. Specifically, the Wikipedia dataset contains the edit relationship between authors and pages, which is public accessible 1 ; The Tencent dataset records the watching behaviors of users on movies in QQlive 2 in one month's time. 2) Weighted bipartite network. We construct other three weighted bipartite network from DBLP, Movielens and VisualizeUs, respectively. Specifically, the DBLP 3 dataset contains the publish relationship between authors and venues, where the edge weight indicates the number of papers published on a venue by an author; The Movielens 4 dataset records the rating behavior of users on movies, where the edge weight denotes the rating score of a user on a movie; The VisualizeUs 5 dataset records the tagging behavior of users on pictures, where the edge describes the number of times of tagging of a user on a picture. The statistics of our experimented datasets are summarized in Table 1. dataset. Specifically, we first treat the observed links as the positive instances, and sample an equal number of unconnected vertex pairs as the negative instances. For Tencent dataset, we treat the user-movie pairs as positive instances if the user has watched the movie for more than 5 minutes, otherwise, negative instances. For both datasets, we randomly sample 60% instances as the training set, and evaluate the link prediction performance on the remaining 40% dataset with two metrics: the ROC curve (AUC-ROC) and Precision-Recall curve (AUC-PR). 2) For recommendation task, we randomly sample 60% edges as the training data, and the remaining 40% edges are treated as testing dataset for all datasets. We rank all items in the testing set for each user and truncate the ranking list at 10 to evaluate the performance of top-10 recommendation with four IR metrics: F1, Normalized Discounted Cumulative Gain (NDCG), Mean Average Precision (MAP), and Mean Reciprocal Rank (MRR). For each metric, we compute the average score for all users, and perform paired sample T-test on it. To avoid overfitting, we generate 10 folds of train-test split, tuning hyperparameters on the first fold only for each method. We use the optimal hyper-parameter setting and report the average performance of all folds (i.e., the score of each metric and the p-value of t-test).

Baselines
We compare BiNE with three types of baselines: 1) Network Embedding Methods. We chose four representative of state-of-the-art network embedding methods as our baselines, including homogeneous and heterogeneous network embedding methods. For each method, we use the released implementations for our experiments.
• DeepWalk [8]: This method performs uniform random walks to get a corpus of vertex sequences. Then the word2vec is applied on the corpus to learn vertex embeddings for homogeneous networks. • Node2vec [14]: This approach extends DeepWalk by performing biased random walks to generate the corpus of vertex sequences. The hyper-parameters p and q are set to 0.5 which has empirically shown good results. • LINE [18]: In contrast to the above methods, this approach optimizes both the 1st-order and 2nd-order proximities in a homogeneous network without generating corpus. We use the LINE (1st+2nd) method which has shown the best performance in their paper. • Metapath2vec++ [11]: As a state-of-the-art method for embedding heterogeneous networks, it generates corpus following the predefined meta-path scheme. And the meta-path scheme chosen in our experiments are "IUI" (item-user-item) and "IUI"+"UIU" (user-itemuser), and we only report the best result between them. 2) We compare with a set of methods that are specifically designed for the link prediction task. We apply several indices proposed in [31], including Absent Links (AL), Katz Index (Katz), and Preferential Attachmenthave (PA). 3) We also compare with several competitive methods 6 that are designed for the top-K item recommendation task. 6. We use the LibRec implementation: https://www.librec.net/ • BPR [32]:This method has been widely used in recommendation literature as a highly competitive baseline [28]. It optimizes the matrix factorization (MF) model with a pairwise ranking-aware objective. • RankALS [33]: This method also optimizes the MF model for the ranking task, by towards a different pairwise regression-based loss. • FISMauc [34]: Distinct to MF, factored item similarity model (FISM) is an item-based collaborative filtering method. We employ the AUC-based objective to optimize FISM for the top-K task.

Parameter Settings
We have fairly tuned the hyper-parameters for each method. For all network embedding methods, we set the embedding size as 128 for a fair comparison; other hyper-parameters follow the default setting of their released implementations. For the recommendation baselines, we tuned the learning rate and latent factor number since they impact most on the performance; other hyper-parameters follow the default setting of the LibRec toolkit. For BiNE, we fix the loss trade-off parameter α as 0.01 and tune the other two. The minT and maxT are respectively set to 1 and 32, which empirically show good results in most cases. We test the learning rate λ of [0.01, 0.025, 0.1]. And the optimal setting of learning rate is 0.025 for the VisualizeUs/DBLP dataset and 0.01 for others. The search range and optimal setting (highlighted in red font) of other parameters are shown in Table 2. Note that besides γ is set differently -0.1 for recommendation and 1 for link prediction -other parameters are set to the same value for both tasks.
For different MF-based methods, we set α and β as the same values for pair comparison. And the optimal setting of α and β are 0.001 and 0.001 for Visual-izeUs/DBLP/Wikipedia dataset, 0.01 and 0.01 for Tencent dataset and 0.1 and 0.1 for Movielens. We test the learning rate of [0.00001, 0.00005, 0.0001, 0.0005, 0.001, 0.005, 0.01] for SMF and BiNE-MF.

Link Prediction
In this task, we first concatenate the embedding vectors u i , v j and label (i.e., the label of the positive instance is 1, otherwise 0) as a record for each instance (u i , v j ) in the dataset, then feed the record into the logistic regression classifier with L2 loss function. Table 3 illustrates the performance of baselines and our BiNE, where we have the following key observations: ** indicates that the improvements are statistically significant for p < 0.01 judged by paired t-test.
• The neural network-based methods which trained in a data-dependent supervised manner outperform the indices proposed in [31] significantly. • Metapath2vec++ and BiNE are significantly better than other neural network-based methods. This improvement demonstrates the positive effect of considering the information of node types when embedding bipartite networks. • BiNE outperforms Metapath2vec++ significantly and achieves the best performance on both datasets in both metrics. This improvement points out the effectiveness of modeling of explicit and implicit relations in different ways.

Recommendation
In this task, we adopt the inner product kernel u i T v j to estimate the preference of user u i on item v j , and evaluate performance on the top-10 results. Table 4 shows the performance of baselines and our BiNE, where we have the following key observations: • BiNE outperforms all baselines on all datasets, and the improvements are significant compared with Metap-ath2vec++ though it also considers the node type information when embedding bipartite networks. We hold that it is due to it ignores the weights and treats the two types of relations (i.e., the explicit and implicit relations) as equally. • BiNE outperforms LINE significantly though it also consider the weight information when embedding networks. The suboptimal performance obtained by LINE because of two reasons. (1) LINE ignores further high-order proximities among vertices due to it only preserves both 1st-order and 2nd-order relations when learning the representations for vertices. (2) LINE learns two separated embeddings for 1st-order and 2nd-order relations and concatenates them via post-processing, rather than optimizing them in a unified framework. Whereas BiNE mines high-order implicit relations among homogeneous vertices by performing random walks and design a joint framework to model the explicit and implicit relations jointly, where different relations reinforce each other and lead to better vertex representations.

Performance of MF-based Methods (RQ2)
Here we adopt symmetric SVD, stochastic matrix factorization (SMF) and BiNE-MF to obtain vertex embeddings 13.63%** 24.50%** 16.46%** 34.23%** 11.37%** 26.19%** 20.47%** 33.36%** 9.14%** 9.02%** 3.01%** 45.95%** ** indicates that the improvements are statistically significant for p < 0.01 judged by paired t-test. and compare their performance. The result is shown in Table 5. We have the following key observations: • SMF and BiNE-MF that much like BiNE's training process show roughly equivalent performance with BiNE. They also obtain better performance than BiNE in the three big datasets: Tencent, WikiPedia, and Movielens. This reveals one advantage of MF-based methods that they approximate the global implicit relations while the limited scale of random walk negatively impacts BiNE's performance. And this observation is in line with the work [27]. It also indicates that maxT should be specified to a large number for a large-scale network. • Symmetric SVD yields the worser result than SMF and BiNE-MF in most case. The cause of this result is the matrix H is sparse and symmetric SVD is undefined when the matrix is incomplete. In addition, addressing the relatively few observed entries is highly prone to overfitting [30]. SMF and BiNE-MF are better than symmetric SVD at handling missing entries. And the regularization in SMF [29] and nonlinear variation in BiNE-MF are also two workable ways of improving performance.

Utility of Random Walk Generator (RQ3)
In this section, we first demonstrate the effectiveness of our random walk generator on preserving the characteristics of bipartite networks, especially the power-law distribution of vertices. Then, we illustrate the effect of considering the implicit relations when learning the representations of vertices for bipartite networks.
The frequency distribution of vertices in a real YouTube dataset is plotted in Fig. 2(a). We can see that the vertices exhibit a standard power-law distribution with a slope of −1.582. By contrast, we plot the frequency distribution of vertices in a corpus obtained from our random walk generator in Fig. 2(b). We can easily find that our random  walk generator almost generates a standard power-law distribution with a slope −1.537 which is very close to that of the original network. In addition, we compare the performance of BiNE under two settings -use or not use our proposed random walk generator. As shown in Table 6, the biggest absolute improvements of BiNE using our proposed random walk generator are 4.14% and 10.25% for link prediction and recommendation, respectively. The above result indicates that the biased and self-adaptive random walk generator is helpful to capture the power-law distribution of vertices and contributes to improving the vertex representations for embedding bipartite networks. Please note that we change the value of maxT to 128 for this empirical study on Movielens dataset because of the default value may be to small to fully preserve the implicit relations for such a largescale bipartite network. Lastly, we show the performance of BiNE and its variant which ignores the implicit relations. Due to the space limitation, we only show the performance on the recommendation task from two metrics: MAP@10 and MRR@10. From Table 7, we can find that the largest absolute improvements of BiNE with implicit relations are 1.44% and 18.58% for link prediction and recommendation, respectively. It demonstrates that our proposed way of mining high-order implicit relation as the complement of explicit relations is effect to modeling bipartite networks.

Negative Sampling Strategies (RQ4)
We have analyzed the difference between LSH-based and frequency-based negative sampling methods in section 4.3, that is LSH-based method resorts to dissimilar information deriving from observed links to obtain more accurate proximity of center-context vertex pairs, while frequencybased method utilizes frequency information to lower the proximity of center vertex with context vertices having high frequency. Here, we compare the performance of BiNE with different negative sampling strategies.
As shown in Table 8, there is a slight advantage in LSH-based by comparing it with frequency-based negative sampling method. Thus, we hold that LSH-based sampling method, which uses dissimilar information obtained from user behavior data, can generate more reasonable negative samples in modeling user behavior.
Frequency-based method also shows roughly equivalent performance in most cases. An intuitive explanation is that the number of negatives is large and the probability of sampling similar vertices as negative is small via frequencybased method strategies.

Case Study
In this section, we perform a visualization study for a small bipartite network to illustrate that the rationality of our BiNE method. We extra a small collaboration bipartite  network from DBLP dataset, which contains 736 researchers and 6 international journals. A link will be established if the author has published at least 5 papers on the journal. The 6 journals are from two different research fields: SICOMP, IANDC and TIT from computer science theory, and AI, IJCV,and JMLR from artificial intelligence. As such, from the published venues of the researches, we can inference the research field of them.
We utilize the t-SNE tool [35] to map the embedding vectors of authors into 2D space. In Fig. 3, we use different color to describe different research fields of the researchers, i.e., red: "computer science theory", blue: "artificial intelligence", and show the visualization results given by different embedding approaches. From it, we can observe that Deep-Walk, Node2vec, LINE, Metapath2vec++, and our BiNE are good since researchers belonging different research fields are well seperated. As far as we are concerned, BiNE gives a better result due to it generates an obvious gap between two research fields. However, the variant of BiNE ignoring the implicit relations -BiNE' shows a worse layout than expected, which illustrate the effective of modeling highorder implicit relations for embedding bipartite networks.

Network Representation Learning
Our work is related to the neural network-based NRL methods. We first review them from the perspective of network types.
The pioneer work DeepWalk [8] and Node2vec [14] extend the idea of Skip-gram [15] to model homogeneous network, which is convert to a corpus of vertex sequences by performing truncated random walks. However, they may not be effective to preserve both explicit and implicit relations of the network. There are some follow-up works exploiting both 1st-order and 2nd-order proximities between vertices to embed homogeneous networks. Specifically, LINE [18] learns two separated embeddings for 1storder and 2nd-order relations; SDNE [36] and DVNE [7] incorporates both 1st-order and 2nd-order proximities to preserve the network structure; GraRep [37] and AROPE [38] further extends the method to capture higher-order proximities. Besides capturing high-order proximities, there are several proposals to incorporate side information into vertex embedding learning, such as vertex labels [10], [39], community information [40], textual content [41], user profiles [9], location information [42], among others. However, these methods might be suboptimal for learning vertex representations for a bipartite network by ignoring the vertex type information. In addition, the "corpus" generated by the truncated random walks may not capture the characteristics of the network structure, such as the power-law distribution of vertex degrees.
Metapath2vec++ [11] and HNE [12] and EOE [13] are representative vertex embedding methods for heterogeneous networks. Although they can be applied to bipartite network which can be seen as a special type of heterogeneous networks, they are not tailored for learning on bipartite networks. Specifically, HNE aims to integrate content and linkage structures into the embedding process, and Metapath2vec++ ignores the strength of the relations between vertices and treats the explicit and implicit relations as equally. As such, they are suboptimal for vertex representation learning for a bipartite network.
It is noteworthy that recent works have shown an increase of interest in generating vertex embedding by neighborhood aggregation encoders [43], [44]. However, these methods rely on vertex features or attributes.

Bipartite Network Modeling
As a ubiquitous data structure, bipartite networks have been mined for many applications, among which vertex ranking is an active research problem. For example, HITS [24] learns to rank vertices by capturing some semantic relations within a bipartite network. Co-HITS [22] incorporates content information of vertices and the constraints on relevance into vertex ranking of bipartite network. BiRank [16] ranks vertices by taking into account both the network structure and prior knowledge.
Distributed vertex representation is an alternative way to leverage signals from bipartite network. Unlike the ranking task, it learns a low dimensional representation of a vertex, which can be seen as the "features" of the vertex that preserves more information rather than simply a ranking score.
Latent factor model (LFM), which has been widely investigated in the field of recommender systems and semantic analysis, is the most representative model. And a typical implementation of LFM is based on matrix factorization [32], [45], [46]. Recent advances utilize deep learning methods to learn vertex embeddings on the user-item network for recommendation [28]. It is worth pointing out that these methods are tailored for the recommendation task, rather than for learning informative vertex embeddings. Moreover, they model the explicit relations in bipartite network only, which can be improved by incorporating implicit relations as shown in [19], [20].

CONCLUSIONS
We have presented BiNE, a novel approach for embedding bipartite networks. It jointly models both the explicit relations and high-order implicit relations in learning the representation for vertices. Our theoretical result reveals that BiNE can be transferred into the algorithm BiNE-MF, which is a implicit multiple matrix factorization, in a closed form. As a result, it broadens the theoretical understanding of BiNE. Extensive experiments on several tasks of link prediction, recommendation, and visualization demonstrate the effectiveness and rationality of our BiNE method.
In this work, we have only considered the information revealed in observed edges, thus it may fail for vertices that have few or even no edges. Since missing data is a common situation in real-world applications, the observed edges may not contain sufficient signal on vertex relations. To address this issue, we plan to extend our BiNE method to model auxiliary side information, such as numerical features , textual descriptions , and among other attributes [9]. In addition, the bipartite networks in many practical applications are dynamically updated [46]. Thus, we plan to investigate how to efficiently refresh embeddings for dynamic bipartite networks.
Ming Gao is currently an associate professor on School of Data Science and Engineering at East China Normal University, China. He received his doctorate from the School of Computer Science, Fudan University. His research interests include knowledge engineering, user profiling, social network analysis and mining. His works appear in major international journals and conferences, including DMKD, TKDE, KAIS, ICDE, ICDM, SIGIR, etc.
Xiangnan He a senior research fellow with School of Computing, National University of Singapore (NUS). He received his Ph.D. in Computer Science from NUS. His research interests span recommender systems, information retrieval, and multi-media processing. He has over 50 publications appeared in several top conferences such as SIGIR, WWW, MM and IJCAI, and journals such as TKDE and TOIS. His work on recommender systems has received the Best Paper Award Honourable Mention of WWW 2018 and SIGIR 2016. Moreover, he has served as the PC member for several top conferences including SIGIR, WWW, MM, KDD etc., and the regular reviewer for journals including TKDE, TOIS, TMM etc. Leihui Chen is currently a master in the School of Data Science and Engineering of East China Normal University, China. Her research interests include recommender systems, computational advertising , social network analysis and mining. She is a student member of CCF.
Aoying Zhou is a professor on School of Data Science and Engineering (DaSE) at East China Normal University (ECNU), where he is heading DaSE and vice president of ECNU. He is the winner of the National Science Fund for Distinguished Young Scholars supported by NSFC and the professorship appointment under Changjiang Scholars Program of Ministry of Education. His research interests include Web data management, data intensive computing, inmemory cluster computing and benchmark for big data. His works appear in major international journals and conferences, including TKDE, PVLDB, SIGMOD, SIGIR, KDD, WWW, ICDE and ICDM, etc.