Improved LSH for privacy-aware and robust recommender system with sparse data in edge environment

When more and more web services are appearing in the network, the possibility that a web service would be selected is becoming smaller and smaller. Therefore, users often do not rate enough web services, and hence, historical QoS data are often not sufficient for determining a target user’s similar neighbors, i.e., data sparsity problems occur [9]. Many studies have tried to alleviate the data sparsity problems. Jing [10] proposed a sparse probabilistic matrix factorization method (SPMF) by employing Laplacian distribution to determine the service/user latent feature; Laplacian distribution has the ability to generate sparse coding and help to recommend the tail services. Hu [11] proposed an enhanced memory-based collaborative filtering method to discover potential similarity relationships between users or items by using limited user-item interactions; thus, they incorporate user similarity reinforcement and item similarity reinforcement into a comprehensive framework and make more reliable rating predictions. Qi [12] put forward a structural balance theory (SBT)-based recommendation method for the sparsity of big rating data in E-commerce. According to the rule of structural balance theory, indirect friends of a target user are discovered and “possibly similar product items” are recommended to him or her.

In order to produce more reasonable and comprehensive recommended results under sparse data conditions, auxiliary information is incorporated to the recommendation methods. Wang [13] integrates time information into collaborative filtering method, and a hybrid personalized random walk algorithm for searching indirect similar user/service is proposed to alleviate the data sparsity problem. Hu [14] proposed a hierarchical Bayesian model called collaborative deep learning (CDL), which performs deep representation learning for the content information and collaborative filtering for the ratings’ matrix. By CDL, deep feature representation extracted from content information can capture similarities and discover implicit relationships between users and items. However, one drawback of these methods based on auxiliary resource is high dependency on auxiliary information that increases the storage cost and raises privacy or security concerns.

Through the above methods we mentioned, the remarkable role of data sparsity in service recommendation has been considered; however, they still have several drawbacks. First, they are vulnerable to privacy leakage when cross-platform QoS data are demanded to be fused to achieve better recommendation performances. Second, similarity calculation or model training of large-scale data repeatedly may block high efficiency and scalability when QoS data increase and update constantly.

Data fusion in distributed environment often leads to privacy issues. Anonymity technique is a common way to protect private information of the user. Zhang [15] adopted anonymity technique by local recoding and combines the t-ancestors (similar to K-means) with the aggregation clustering algorithm for solving the problem of privacy information disclosure to third party. Casino [16] implements K-anonymity through microaggregation technology to protect user privacy during service recommendation. Memon [17] generalizes and blurs the unique location information of users by applied K-anonymity, so as to protect the location information of users while recommending services. However, the recommendation accuracy of the above three methods decreases accordingly while certain data are distorted simultaneously. In terms of protecting privacy information in QoS data, Dou [18] focuses on finding the “representative” QoS values in users’ historical records, which can be implemented and shared by distributed platforms, while the user privacy information contained in certain QoS values may still be partially disclosed to the public. Zheng [19] takes “the amount of data that a user needs to be open” as an adjustable parameter and model multiobjective optimization problem as NP-hard with high time complexity, thus obtaining a good compromise between the availability and privacy of the data; however, a small amount of QoS data opened may also be leaked to some extent. Zhu [20] obscures real QoS data by adding random value to each service-specific QoS data; then, user similarity and service recommendation are calculated by obfuscated data to protect privacy values, but QoS values of the user itself in this way will still be partially leaked.

Due to the unique characteristics of LSH (i.e., neighboring points are still close after hashing with large probability), LSH has already been utilized to secure users’ privacy in service recommendation for privacy-preserving and efficient outcome [21‐23]. However, LSH-based recommendation methods often face the below difficulty: it does not take into account the sparsity data problem, which decreases the recommendation robustness severely.

Based on the above analysis, existing service recommendation methods can seldom cope with the sparse data issue and privacy-preservation requirements simultaneously. Considering this challenge, we bring forth a novel recommendation method that is not only robust but also privacy preserving in the following sections.

To simplify the following discussion, the symbols to be recruited in this paper can be described as below. For facilitation, the recommendation problem can be formalized by a four-tuple (M, U, E, m_i.j.q) as below:

In view of the above formal symbol representation, the privacy-preserving recommendation problem with sparse data can be described as follows: a recommender system integrates the distributed m_i.j.q data to discover appropriate services for a target user; during the above process, real QoS values cannot be leaked to the outside. To tackle this issue, we introduce a novel method in Section 4.

To clarify the idea of this paper, an intuitive example is demonstrated in Fig. 1 to introduce our motivation in detail.

In Fig. 1, we can see that historical QoS data are distributed in two edge platforms: Google and Microsoft. Suppose that there are a total of n candidate services {m₁, …, m_n} and four users {u₁, u₂, u₃, u₄}; several QoS data records m_i.j.q in each distributed edge platform are also provided where “m_i.j.q = 0” means that u_i has never rated m_j before. In this situation, the size of service intersection between users is fairly small, which seriously hinders a target user from finding his/her similar neighbors and interested services. Therefore, the recommender system needs to integrate the QoS values from both Google and Microsoft so as to make a more comprehensive decision; afterwards, similarity between different users, e.g., u₁ and u₂, can be obtained for seeking similar neighbors in recommender system, and then, more accurate and comprehensive recommended results can be achieved in a privacy-preserving way.

In view of this, a novel service recommendation method adapted to data sparsity and privacy preservation is presented in the next section.

Locality-sensitive hashing (LSH) has been put forward by Aristides Gionis in 1999 [7] and has been proved to be appropriate for fast approximate querying millions of data; the accuracy of query results is same as that of “brute force” query basically and widely used in many fields, such as videos and image queries. The main idea of LSH theory can be shown as in Fig. 2. First, original data space is converted into a LSH data space by hyperplanes in Fig. 2a. Afterwards, (1) two neighboring points like A and B in the original data space are still neighbors with high probability (i.e., A and B are on the same side of the hyperplane l₁) in LSH data space; (2) two dissimilar points like A and C (or B and C) are still not neighbors with high probability (i.e., the two points are on the different sides of the hyperplane l₂) in LSH data space. Furthermore, the distance from the point to the hyperplane can be calculated to find the nearest neighbors or the most similar neighbors.

We utilize the example in Fig. 2b to illustrate the distance calculation process. Assume that two points a and b are on the same side of the hyperplane l₁ in LSH data space, \( \overrightarrow{op} \) (\( \overrightarrow{op}\ne \) 0) is a normal vector of hyperplane l₁ while vectors \( \overrightarrow{oa} \) and \( \overrightarrow{ob} \) are used to compute the distance between points a and b to the hyperplane, respectively. We assume O₁ and O₂ are projection points of points a and b on normal vector \( \overrightarrow{op} \), OO₁ and OO₂ are corresponding to the projection distance (i.e., the distance from the point to hyperplane) of vectors \( \overrightarrow{oa} \) and \( \overrightarrow{ob} \) to the normal vector \( \overrightarrow{op} \). Then, according to dot product principle, the distance OO₁ (or OO₂) from the point a (or b) to hyperplane l₁ can be obtained by formula (1). Here, \( \left\Vert \overrightarrow{op}\right\Vert \) represents the modulus of normal vector \( \overrightarrow{op} \) and symbol “ ∘ ” represents the dot product between two vectors. Thus, the distance from each point to the hyperplane can be gained in LSH data space, which makes it easier to find out the nearest neighbors of fixed points.

In the above example, we have observed the basic theory and three advantages of LSH technique. First, transforming the original data into LSH data space greatly improves the efficiency and scalability of the process for similar neighbors finding. Second, the original data in LSH data space is transparent to users, through which user privacy can be protected significantly. Third, distributed data could be integrated into a unified LSH data space, which improves the accuracy of uniform calculation considerably. Therefore, the LSH technique is extended in this paper to achieve the goal of privacy-preserving service recommendation with sparse data in edge environment.

Concretely, our method mainly includes three steps as elaborated in the reminder of this subsection.

Experiments are implemented on Movielens dataset, which contains ratings of 3900 movies from 6040 users. To validate the prediction performance, we compare SerRec_sparsity-LSH with three state-of-the-art methods: Random, WSRec [24], and SBT-Rec [12]. Random is a benchmark that chooses services randomly; WSRec predicts the missing QoS data by considering the average QoS of the target service invoked by all users and the average QoS of all services invoked by the target user; SBT-Rec first searches for the indirect neighbors of the target user through social balance theory and collaborative filtering, and then recommends optimal services based on the derived neighbors. The experiments were running on a laptop with an i7-6500U CPU (2.50 GHz) and 16.0 GB RAM, Windows 7 operation system and Python 3.6. The experiments were executed 50 times, and average values are applied ultimately.

Four groups of experiments are performed and evaluated. Four parameters are displayed in the experiments: m and n mean the number of users and services, respectively; L and R mean the number of hash tables and hash functions, respectively.

LSH is a kind of hash technique, which means that although LSH can protect the sensitive information of users when performing service recommendation, the effect of privacy preservation of LSH cannot be measured easily. For simple experiments, we only test the discrete data in Movielens dataset without testing other data types popular in the big data environment, e.g., continuous data type [25‐29], Boolean data type [30], and fuzzy data type [31‐33]. In addition, we only test a single criterion (user rating) without discussing the popular cases with multiple criteria [34‐44] and their inner linear correlations [45‐48], nonlinear correlations [49‐66], and weights [67‐73]. Therefore, we hope to refine our method by addressing these more complicated situations in the future research.