extfieldsofstudy:
Computer Science
Mathematics

text:
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.


Fingerprint Protected Password Authentication Protocol

With the rapid development of industrial Internet of things (IIOT), a variety of cloud services have been deployed to store and process the big data of IIOT.The traditional password only authentication is unable to meet the needs of security situation in IIOT. Therefore, a lot of mobile phone assisted password authentication schemes have been proposed. However, in existing schemes, the secret information is required to be stored in the user’smobile phone.Once the phone is lost, the secret informationmay be obtained by the opponent, which will bring irreparable loss to the user. To address the above problems, we propose a fingerprint protected password authentication schemewhich has no need to store the secret parameter in the mobile phone. When a user logs in, he uses his mobile phone to generate the private key which is used to decrypt the encrypted text generated during the registration phase. The process of generating the private key needs to enter the password and the fingerprint. When the computer interacts with the mobile phone, the user’s password will be blinded so that it can protect the user’s password from adversary’s attacks. Theoretical analysis and experimental results show that our scheme improves the security of the user’s secret.Meanwhile, our scheme can resist the opponent’s dictionary attacks, replay attacks, and phishing attack. Our scheme can reduce the storage pressure of the mobile phone and is easy to deploy.

Introduction
The rapid development of industrial Internet of things (IIOT) has reformed many aspects of user's daily life. A variety of cloud services have been deployed to store and process the big data of IIOT [1][2][3][4]. Due to the openness of public network, these cloud services suffer from a wide range of attacks [5][6][7][8].
Text-based passwords remain the dominant authentication technique for various online services and systems, because it is accessible and convenient. Most of them require their own password and the user has to manage multiple passwords to their accounts.
However, password authentication schemes have inherent limitations. Firstly, the user is prone to use a simple password for convenience. If the length of the password is short, its information entropy will be very low. Therefore, the user's password will be easily compromised by attackers. After obtaining the user's password, the opponent can use the password to access the user's account and steal user's private information. In addition, the user may use a single password to authenticate to multiple services. If one of the user's accounts information leaks, it would pose a threat to the security of other accounts. What is worse, users often forget their passwords and try to login via trial-and-error, which means that a malicious online service would learn not only a user's password to that service, but to many other services, possibly also through a cross-site impersonation attack. The low information entropy and the repeated setting of the password are common problems in the process of password setting and password usage. These above problems are also easily exploited by attackers. Moreover, malicious service providers may also launch attacks against the user. For example, the CEO of Facebook allegedly used Facebook login data to access the private mails of some business rivals and journalists in 2004 [9]. Hence, protecting users' passwords has become extremely important for individuals.

Security and Communication Networks
To avoid the limitation of password authentication mechanism, researchers have proposed many schemes [10][11][12]. Adding an additional factor is one of the common ways to protect user's password. With the extensive use of mobile phones in recent years, users often use mobile phone to manage personal information and store many credentials or secrets on the mobile phone. Consequently, the research on mobile phone assisted password authentication is one of the important trends.
In 2004, Wu et al. [13] proposed a scheme using the mobile phone as an authentication token with the help of a trusted agent P. When a user wants to authenticate to a remote server, he/she is required to communicate with the agent P first. The agent P sends a session name to the mobile phone and the PC client. The user compares the session name showing on the mobile phone and the PC client. Then the user sends the result to the agent P. However, this scheme requires the agent to be secure and trustworthy, which is a strong assumption in practice. Moreover, the mobile phone is required to interact with the agent several times and is prone to man-in-the-middle attack. In addition, the involvement of a trust agent makes the scheme hard to be deployed.
The scheme [14] proposed by Thanh et al. uses a mobile phone and an authentication server to assist the user during login authentication. In this scheme, with the help of the mobile phone and the authentication server, the client and the server is not required to communicate directly through the public network while sending or receiving credentials. However, the authentication server is utilized to receive the data transmitted by the mobile terminal through the GSM network, which is considered to be an insecure transmission channel. Therefore, the response phase is prone to be attacked by the opponents. When the user uses a mobile phone to send a message to the authentication server through the GSM network, it is not hard for the opponent to hijack the user's message. The adversary can use the hijacked information to authenticate with the server.
Considering the security of information transmission in the authentication phase, the scheme in [15] uses the mobile phone as the intermediary to transmit the user's secrets securely. It uses the QR code and the camera to encrypt the key during the authentication phase. But this scheme requires adding a bar code on the device in advance. If there are plenty of authentication devices or services, many QR codes are required to be predeployed, which is not practical for deployment.
The scheme in [16] is put forward to resist session hijacking and phishing attacks. The client PC is independent to the mobile device and just performs calculations in the scheme, while the mobile phone records the user's password. They share a session key to against session hijacking. However, the mechanism requires the terminal to calculate and establish a pair of public keys with each server. If there are a number of services, the setting will be cumbersome, which will bring much overhead to the mobile phone. What is more, this scheme needs to establish a secure channel between the client PC and server, which greatly reduces the availability of this scheme.
In [17], a method for users to authenticate with the server on an unreliable computer is provided. The main idea is that the mobile phone scans the QR code on the computer, encrypts the QR code, and then uses it to authenticate with the server. However, this scheme requires the trusted mobile phone and the server to set up a shared key in advance, which is difficult to realize in the practice. Moreover, mobile phone and computer need to communicate with the server several times during the authentication phase, which makes this scheme time consuming.
In the SPA (single password authentication) scheme proposed by Acar et al. [18], it requires additional cloud storage to store the user's data and assist the user to register and log in. However, the scheme needs to set a secure channel between the client and the storage when the client sends the blind signature private key to the storage, which is a strong assumption. Furthermore, this scheme also requires a trusted cloud storage to store the ciphertext, which is not readily accessible in practice. Moreover, the user and the cloud storage require a lot of data transmission and interaction during the authentication phase, making time consuming. Acar et al. also proposed a different SPA scheme based on a mobile device. In this scheme, a trusted mobile device is used to assist users to register and log in. The user uses the password to encrypt the authentication key and then store the ciphertext on the trusted mobile phone device. When the user wants to access his account, he inputs his password to decrypt the ciphertext to get his authentication key and then authenticate with the server. But this scheme also requires the mobile device and server to be trusted, and no collusion between the server and mobile phone, which is a very harsh security requirement for mobile devices. In addition, if the mobile device is lost, which is a very common situation, user's ciphertext stored on the mobile device can be cracked offline by adversaries, which will lead to serious consequences.
In the password authentication method based on mobile phone assistance, there is a method based on fingerprint, which attracts much attention. The scheme [19] proposed using a fingerprint to replace the PIN code to authenticate the user's identity. However, fingerprint information is still stored in the mobile phone in this scheme. If the fingerprint information is cracked by adversaries, it will pose a security threat to the user. So this scheme cannot protect the user's privacy very well. The scheme [20] proposes a solution that enables a user to authenticate with a remote server through a password and fingerprint. However, this scheme requires a secure channel between the client and the server, which is difficult to deploy in the actual scenario. Moreover, the mobile device is also required to be trusted. It means that if the mobile device is lost, the ciphertext and the fingerprint parameters stored on the phone can be cracked by attackers.
The password authentication method based on mobile phone assistance has received extensive attention and has been widely studied. However, these schemes have security risks in terms of user's privacy: the mobile phone has to store the user's privacy or credentials during the authentication process and the mobile phone must be trusted. Otherwise the user's privacy stored in the mobile phone can be cracked forcedly by the adversary. In March 2016, FBI announced that it can crack the IOS to obtain the suspect's mobile phone terminal information [21]. This means that there is no mature technology that can fully guarantee the user's privacy stored in the mobile devices at present. So it is risky to store the user's secret information on the mobile phone. This risk will affect the security of the authentication scheme based on mobile phone assistance extensively.
Although authentication schemes assisted by mobile phone are popular, there are a lot of defects and hidden danger in this kind of authentication schemes. At present, most authentication schemes with mobile phone assistance have to store the user's private information on the mobile phone to help authentication. Moreover, in most schemes, the mobile phone is required to be fully trusted. However, in March 2016, FBI announced that it can crack the IOS system to obtain the suspect's mobile phone terminal information. This means that there is no mature technology that can fully guarantee the user's privacy stored in the mobile devices at present. So it is risky to store the user's secret information on the mobile phone. HCR (Hidden Credential Retrieval from a Reusable Password) [22] is a protocol that can be used by the user to store his information on an unreliable remote server. When the user wants to obtain his information, he can get his own encrypted information by a preset password and do not have to disclose the password to the server. However, this protocol needs to set up a secure channel to transmit the private key during the registration phase. Meanwhile, the private key has been saved on the server for a long time, which is an insecure operation. Existing three party authentication schemes participated with mobile phone, computer, and server often require the user's encrypted information saved on the mobile phone; meanwhile, the mobile phone must be reliable. What is more, the scheme assumes a secure channel to transmit secret information. This assumption and deployment are too difficult to be implemented in an actual situation, which greatly reduces the availability and security of the authentication scheme.
To solve these difficult problems, we propose a fingerprint protected password authentication (FPPA). Our new scheme has eliminated the complete credibility of the phone and the security channel between the phone and the server. When the user logs in he uses his mobile phone to generate the private key which is used to decrypt the ciphertext generated during the registration phase. The user needs to enter his password and fingerprint at the private key generation process. When the computer interacts with the mobile phone, the user's password will be blind. So the password can be protected from adversaries' attacks. Our scheme does not need to store any user's secret information on the mobile phone. Even if the mobile phone is stolen by adversaries, the private information in it will not be leaked. Security analysis proves that this scheme can protect the user's password against dictionary attacks and session hijacking attacks even without the assumption of secure storage and a secure channel between phone and server. Experimental results show that our scheme is essentially the same as the current schemes in terms of performance and has a significant advantage in the storage of mobile terminal over other schemes. The main contributions of our work can be summarized as follows: (I) In order to ensure the security of the user's secret information in the IIOT, a fingerprint protected password authentication protocol which has no need to store the secret parameter in the mobile phone is proposed.
(II) Our scheme can resist the opponent's dictionary attacks, replay attacks, and phishing attack.
(III) Our scheme has good performance and strong practicability.
The rest of the paper is organized as follows. Section 2 introduces the preliminary knowledge of the paper. Section 3 introduces the model of the system model and the adversary model respectively. Section 4 introduces the overview of the FPPA scheme. Section 5 describes the security analysis and proof. Performance analysis and evaluation are presented in Section 6. Finally, Section 7 concludes.

Blind Signature.
Blind signature scheme is a basic cryptographic primitive to guarantee the anonymity of participants. A blind signature scheme consists of two entities: a message sender and a signer. It allows the sender to obtain the signature of a given message without revealing any information about the message and the corresponding signature. The basic principle of blind signature is the application of two commutative algorithms. One algorithm is to conceal information, called blind transformation, and the other is the signature algorithm.
The characteristics of blind signature are as follows: (I) The content of the message is blind to the signer.
(II) The signer cannot associate the signed message with the actual message signed. Even if he saves all the documents he signed, he cannot distinguish the real content of the documents he signed.

HKDF (Halting Key Derivation Functions). HKDF [23]
is a protocol that can generate strong security key through a general weak password. It can choose the cost of the calculation, which is applied to the password-based encryption system. HKDF includes two algorithms: HKDF.prepare() and HKDF.extract().
( , , ) → , V. HKDF.prepare() takes as input a password , a random string r, and a parameter t of cycle calculations and returns a random token y and its ciphertext v.
( , V) → . HKDF.extract() takes as input a password and a ciphertext v and either returns a token y or fails to halt in polynomial time. If the password is not correct, this algorithm will always be a loop operation without output feedback 0.
In this paper, we use a HKDF algorithm to generate a strong key using a private key, and user or system can establish a suitable parameter value to select the corresponding calculation cost.

System and Adversary Model
3.1. System Model. The system model of the scheme is shown in Figure 1. It mainly includes the following three entities: mobile phone (MP), personal computer (PC), and cloud server (CS). MP is in charge of user's authentication key and generation of the ciphertext during the registration phase. It interacts with the PC in the authentication phase, so that the user's blind password and fingerprint parameters are processed during this phase. In addition to the basic functions of the mobile phone, it should be able to register the user's fingerprint data and connect to the PC via Bluetooth, USB, or Wi-Fi, in order to communicate with PC.
PC is responsible for the password input and interacts with mobile phone to generate session key when the user logs on. PC should ensure that it is connected to the Internet and can communicate with the CS and mobile phones.
CS stores users' authentication key and their ciphertext at the end of the registration phase and provides users with their corresponding ciphertext information. Meanwhile, it verifies user's identity in the login phase. Accordingly, the CS should be able to connect to the Internet and has a powerful database to store user's information.
The registration phase includes step A, and the login phase includes steps B, C, and D.

The Adversary
Model. The adversary model is defined as follows: (I) PC is distrusted. In the login phase, if the user's PC is infected by malwares, the keyboard may record the user's password. If the user accesses a phishing site, the adversary may also record the user's password.
(II) User uses mobile phone during the registration and login phase, while the mobile phone is prone to be lost or be implanted with malwares. If the phone was infected by malwares, the adversary may impersonate as the user to communicate with the PC.
(III) The CS authenticates the user and provides application services. In the registration phase, the CS is trusted. After that, the CS may suffer from replay attack or dictionary attacks. In addition, the CS may also be curious about user information.

Design Rationale of the FPPA Scheme.
Our FPPA protocol allows a user register and authenticate with online services using his password and mobile phone securely. During the authentication protocol, the mobile phone may be lost or compromised by malwares, so the information stored on the mobile phone may be exposed by adversaries. At the same time, when the user logs on, the mobile phone interacts with the PC. If the mobile phone gets the user's password, it may also be stolen by the adversary. Therefore, it is required that authentication information and encrypted data should not be stored in the mobile phone. To avoid the case that the password is stolen by adversaries during the authentication phase, it is required that the PC encrypts the password after the user enters his password.
To this end, we improve the existing HCR protocol, which is deployed on the PC and mobile phone, such that user can interact with the distrusted mobile phone. In the HCR protocol, the private key needs to be transmitted in a secure channel and stored safely for a long time. Our scheme replaces the private key parameter with the user's fingerprint so that our scheme does not require the secure channel, or the longterm storage.

The Detailed
Process of the FPPA Scheme. Our scheme includes a mobile phone, a PC, and a CS during the registration phase and the login phase. The user enters his password and fingerprint on the phone and PC to register and log on. The CS is responsible for the registration and authentication when the user wants to access the CS.
The system initialization definition is as follows: p: a prime number; name: the user name; pwd: the user's password; G: a cyclic abelian group of order p; F: a multiplicative domain of order p; e: the user's fingerprint; s: the user's private key; y: the user's authentication key; v: the ciphertext of the authentication information; ℎ() : {0, 1} * → : a cryptographic hash function, which is to be viewed as a random oracle; ∈ : a random number generated by the system; f : a hash function; HKDF: a key derivation function, which consists of two functions: HKDF.prepare() and HKDF.extract().
Generally, in the previous mobile phone based authentication scheme, the mobile phone stores user's authentication information. The user's password is encrypted and stored on the mobile phone, or the user's secret key is encrypted with his password and stored on the mobile phone. If the phone is compromised by the adversary, the adversary is likely to get the user's password or authentication information.
In our FPPA scheme, the mobile phone does not store the user's authentication information. The authentication key is regenerated by himself when he wants to log on. Even if the device is stolen, it will not pose threat to the user's password, fingerprint, or encrypted information. Moreover, when the user sends the name to the server in the registration phase, he/she can also choose to send a random identity ID, so that he/she can preserve his/her anonymity. Even if several CSs are in collusion with each other, the user cannot be attacked.
Registration and login phase are as follows:

Registration Phase.
In this phase, before the user accesses to the service provided by the CS, he/she is required to register to be a legal user. The user can register through the mobile phone, after the completion of registration phase, the user name name and service information are sent to the PC side.
The process is detailed as follows, as is shown in Figure 2.
(I) Mobile phone generates the user's private key s according to the user's password pwd and fingerprint parameter e. The user's private key s is generated as follows: (II) The mobile phone side generates the user's authentication key y and the ciphertext of authentication key v based on the HKDF function and the private key s. The operation is as follows: .
( , , ) → , V, where r is a random string generated by the system; t is the number of loop operations. Note that t can be selected according to the security requirements of the user. If the value of t is larger, the computation would be more time consuming. So the generated key is more secure.
(III) The mobile phone sends the authentication key y, the ciphertext v, and the user name name to the CS. Meanwhile, the mobile phone sends the user name name and CS information server to the PC. The user just remembers the user name name and password pwd, and the mobile phone does not store any secret information of the user.

Login Phase.
When the user wants to access the CS, he/she needs to send a login request to the CS. The user enters his own password and fingerprint data to generate a private key and then decrypts the ciphertext to obtain the authentication key. The server determines whether to accept the logon request or not after the server computes and compares the authentication information. The specific operation is as follows, as is shown in Figure 3 (I) The PC sends name to the CS, and then the CS retrieves the corresponding information according to name. After that, the CS sends the corresponding ciphertext v and certified random number chal to the PC.
(II) The user enters his password on the PC. The system generates a blind parameter d and then calculates the blinded password to the mobile phone.  .
(VI)The PC obtains the response by computing ( , ℎ ) → and sends the response response to the CS.
(VII)Finally, the CS computes ← ( , ℎ ) and compares it with the response received. This logon is successful if these two parameters are identical.

FPPA Protocol.
Our FPPA protocol has three types of entities: the PC client who wants to use a password and fingerprint to access services, the CS who registers and authenticates clients, and mobile phone who assists PC client to complete registering and logging.
Our FPPA protocol consists of following algorithms: UserGen. This algorithm is run by the user to generate a user name name and an l-bit password pwd.
Register. The user registers with the server by inputting his password and fingerprint on the mobile phone. In the end, the mobile phone outputs an authenticated key y and ciphertext of the authenticated key v. The mobile phone sends (name, y, v) to the CS and sends (name, server) to the PC.
Store. The PC stores the user name name. The mobile phone does not store user's any information. The user just needs to remember his name and password.
Retrieve. The PC client uses its user name name to retrieve its ciphertext v from the server. The server sends the ciphertext v and challenge chal to the PC client.  PreAuth. The user inputs his password pwd in the PC side and inputs his fingerprint e on the mobile phone. The PC client interacts with the mobile phone using the blind signature. At the end of the blind signature, the PC client generates the private key s and decrypts the ciphertext v using s. The PC client obtains the authenticated key y after decrypting the ciphertext.
Authenticate. The user uses his authenticated key y and change chal to prove to the server that he owns the corresponding account credential. Finally, the CS outputs accept or reject.

Security Game.
Our FPPA scheme assumes that the user has a mobile phone and PC client, so that the user can enter his own password and fingerprint on these devices. However, mobile phones may be lost. Therefore, malicious adversaries may use the user's data stored on the mobile phone to access the server, and even decrypt the ciphertext brutally. What is more, the PC client and the server are also easily attacked by adversaries [24,25]. We divide the potential attacks into two types: Insider attack (Game One) and Outsider attack (Game Two). Let x be a security parameter, such that all hash functions have at least l≥2x bits of output. Let | | << 2 be the length of the password dictionary. k is the length of the user's password. ∈ . Let neg(k) be a negligible function of k if ∃K finite:∀k>K: ( ) < − [26][27][28].
Game One (Outsider Attack). In this game, the adversary can control the PC side. He can perform the Store step with the mobile phone and PC. He can also perform the PreAuth step with the server by acting as a malicious PC. The adversary may also control the PC side and then launch the Retrieve request. We assume the times of requests are q. The adversary can control the mobile phone side and perform Retrieve step with the PC side by simulating the mobile phone side. In the algorithm of our scheme, mobile phone can only receive data from the PC side but cannot initiate requests to the PC side. If the adversary got the user's password through the game or guessed the private key s without the password, we consider the adversary win [29,30].

Definition 1.
We assume that the probability of adversary winning the Game One is P1. If P1≤max[q/|D|+neg(k), 1/2|s|], we consider that FPPA is in accord with the security based on Game One.
Game Two (Insider Attack). In this game, the adversary can control the server side. He can launch an offline dictionary attack on the server to get the ciphertext of the user's password. We assume that the adversary can initiate T times offline dictionary attacks against HKDF.extract. If the adversary got the user's password through the game, we consider the adversary wins.

Definition 2.
We assume that the probability of the adversary winning the Game Two is P2. If 2 ≤ /| |+2 /| | + ( ), we consider that FPPA is in accord with the security based on Game Two.

Definition 3.
If FPPA is in accord with the security based on Game One and Game Two, we consider the FPPA is security.

Security of FPPA
Theorem. FPPA is in accord with the security based on Definition 3.
Prove. (I) FPPA can provide security based on Game One.
Game One. (1)The adversary simulates the PC side and performs Store with mobile phone to get the user's name name. The adversary performs PreAuth with server side and retrieves user secret key ciphertext v and challenge chal according to the user's name. According to v is generated by the algorithm of HKDF [23], if someone inputs wrong password to decrypt the ciphertext, the HKDF would compute circularly with no output. So the adversary cannot get user's password through v. Consequently, P1 is a small value that can be ignored.
(2)The adversary simulates the PC side, generates a password pwd0, and performs Retrieve with mobile phone. This interaction process is similar to the interaction process in the algorithm of HCR and just replaces the signature private key in HCR into fingerprint parameters. The probability of guessing password in this game is the same as that in HCR [22]. So the probability of the adversary guessing the password: P[guess password]≤q/|D|+neg(k). The probability of the adversary winning this game: P1≤q/|D|+neg(k).
(3)The adversary controls the PC side and guesses the private key s without password. The probability of the adversary guessing private key: P[guess s]≤1/2 |s| . The probability of the adversary winning this game: P1≤1/2 |s| .
(4)The adversary performs Retrieve with PC side by simulating mobile phone. The adversary can get the blinded password of the user. So the probability of the adversary guessing the password is the same as the analysis of (b). The probability of the adversary guessing the password: P[get the password] ≤q/|D|+neg(k).The probability of the adversary winning this game: P1≤q/|D|+neg(k).
(II) FPPA can provide security based on Game Two.
Game Two. Malicious server launches offline dictionary attacks on the ciphertext stored on itself. It generates a private key s' and tries to decrypt ciphertext: HKDF.extract (s',v).
In summary, FPPA can provide security based on Game One and Game Two, so FPPA is a secure protocol.

Test Plan and Scenario.
We rented Ali CS to authenticate with the user in order to make the test scenario more close to the actual one. Ali CS deployed in Qingdao and the distance between Qingdao and Xi'an is 1058.6km.
As shown in the Figure 4, 1 describes that the mobile phone computes and generates authenticate key y and authenticate key ciphertext v. And then the mobile phone sends v to the CS in the end of registration phase. 2, 3, and 4 describe that the mobile phone and the PC compute and generate authenticate key y to authenticate with CS in login phase. Android device, a PC and CS are used to simulate our scheme. We evaluate the usability of our scheme from the aspects of time and storage. We test the user's registration and login time in four different scenarios. In terms of storage capacity, we mainly analyze and evaluate the storage capacity of the Android device. The experimental devices of our scheme are a PC, a CS, and an Android device. The specific parameters of the experimental devices are as follows: We use Ali CS located in Qingdao as the CS in our scheme. RAM of the CS is 1GB. It has a single-core processor. The operating system of it is windows Server 2008.
We use HP Compad dx7408 MT DT PC as the computer in our scheme. It has a dual-core processor. RAM of the computer is 2GB. The operating system of it is windows 7(32 bits).
We tested our scheme in 4 cases.
Case 1. The user registers and logs in, and then enters his password and fingerprint. We test the time spent on registration phase and login phase and then test several sets of data to find the average time for one user spent on registration and login phase. The Android device used in this scenario is the Android simulator.
Case 2. The length and complexity of passwords are different for different users. In order to analyze the influence of different passwords on our scheme, we select 20 groups of users. We test the time of these users spent on registration phase and login phase. The Android device used in this scenario is the Android simulator.
Case 3. Due to the different system settings, different length of fingerprint parameters is generated in this case. We test the time spent on registration phase and login phase while the length of the fingerprint is 128b, 256b, and 512b. The Android device used in this scenario is the Android simulator.  We test the time spent on registration phase and login phase. We divide the total time of registration phase K into two parts: k1 and k2 in this experiment. As shown in Figure 5, k1ms is the time spent on the registration phase starting from the user's registration on the Android device to the end of the generation of authenticated key ciphertext. k2ms is the time spent on sending the authenticated key to the CS.
The total time T ms of the login phase is divided into five parts. As shown in Figure 6, t1 is the time spent on requesting the corresponding authentication key ciphertext from the user's PC. t2+t4 is the time spent on blinding the user's password and generating the authentication key. t3 is the time spent on signing the blinded password with fingerprint data on the Android device. t5 is the time spent on sending the user authentication information to the CS.

Experiment Data of Case 1
(I) Registration Phase. In this case, the user enters the user name, password, and fingerprint on the Android device for registration. The length of user's fingerprint is 256b. As shown in Table 1, we measured 10 groups of data. We can calculate that the average registration time is 216.9ms through the following data.  and 128b). We measure the time (k1, k2) spent during the registration phase. The measured result is shown in Table 5.   Table 3, when different users enter a different password to register, the difference between the longest and the shortest time is 81ms which is less than the human reaction time. Users cannot feel the difference in the length or complexity of passwords. Therefore, the length and complexity of the password have little impact on the user's registration time. The comparison of the time spent by different users in the registration phase is shown in Figure 7.
As shown in Table 4, when different users enter their password to login, the difference between the longest and the shortest time is 54ms, which is less than the human reaction time. Therefore, the length and complexity of the password have little impact on the user's login time. The comparison of the time spent during the login phase is shown in Figure 8.
When the length of the fingerprint is different, the maximum difference of the time among users during the registration phase is 9ms. The maximum difference of the time spent in the login phase is 10ms which has little effect on users. When the length of the fingerprint is 128b, 256b,    and 512b, the comparison of the time spent in the registration phase and the login phase is shown in Figure 9. In Case 4, the user enters the same password and fingerprint on different Android devices. As shown in Tables 7 and 8, the total time spent on registering and logging in on mobile devices is less than the total time spent on the Android simulator. There is no difference in their transmission time. The main difference is the calculation time on Android devices. In the existing Mobile SPA scheme, the total time (26ms) spent in the registration phase is the transmission time and the computation time on the mobile terminal. The time spent on the two mobile phones in this paper is 37ms and 40ms. The difference of the time between them is small, so it has little effect on the performance of the scheme. In the SPA Mobile scheme, the time (38ms) spent in the login phase is the computation time on the server side, computing time on the mobile phone, and the transmission time. The total time of our scheme is 152ms and 151ms. Compared with the scheme of Mobile SPA, the time difference of our scheme is larger. However, our scheme has blind signature operation in the login phase and regeneration of the key operation and so on which greatly improve the security of the system. The time Users' using different Android device in registration and login is shown in Figure 10.
We can see from above test scenarios that the running time of our scheme during the registration phase is k1; the running time of our scheme in the login phase is t3+t2+t4; the total running time of our scheme is k1+t3+t2+t4 called w. The propagation delay time between the computer and the mobile phone is brief, so we consider t3 as the running time in the Android device. We can calculate the total running time w according to the Case 4. The comparison diagram of the time running in the distinct Android device is shown in Figure 11. We can see from Figure 11 that our scheme running in the Bluestacks costs the longest time. That is because there are some gaps in processor and set parameters between Bluestacks and Android mobile phone which influences the efficiency of our scheme.
In the storage capacity of mobile phones, the Mobile SPA scheme requires storing MAC key on the phone to authenticate with the CS. A server corresponds to a MAC key, while the length of a MAC key is 128 bytes. In our scheme, the mobile device only needs to store the user's fingerprint data. The maximum length of fingerprint data is 512 bits (64 bytes). If the user registers 2000 servers, in the Mobile SPA scheme, the user requires 250kb storage capacity while the user requires 0.0625kb storage capacity in our FPPA scheme. Meanwhile, our scheme does not need to store data in the mobile phone for a long time.
In conclusion, although our scheme has a significant increase in the login phase, the user has little effect on the use in terms of user experience. Meanwhile, our scheme adds the blind signature operation and regeneration of the key operation and so on which greatly improve the security of the system. What is more, our scheme only stores the user's fingerprint in the mobile phone temporary. Because only a small amount information is stored in our scheme, the storage pressure of the mobile terminal is reduced. Therefore, our scheme has a high application value.

Summary
Passwords are widely deployed to secure users' access to cloud services in IIOT. However, passwords are prone to dictionary attack and phishing. Therefore, protecting the user's password when authenticating the user's identity has become a widespread concern. In this paper, we use the mobile phone to assist user's authentication. Specifically, we use both password and fingerprint to generate a secret key and then we use the secret key and HKDF function to generate the authentication key. Due to the characteristic of HKDF function, any adversary cannot get the key or password or decrypt the ciphertext through exhausting enumerating attacks. There is no user's secret information on the mobile phone, so even if the mobile phone is lost, it will not pose a security risk to the user's account. Finally, we prove the security of the scheme and evaluate the performance of our scheme. Results show that our scheme can resist dictionary attacks and attacks against the user's mobile phone. Meanwhile, there is no significant difference between our scheme and the existing three party authentication schemes, in terms of performance. In addition, our scheme reduces the storage pressure on the mobile phone. Overall, our scheme has high practicality.

Data Availability
The data used to support the findings of this study are included within the article.

Conflicts of Interest
The authors declare no conflicts of interest.