Maho Asada
email: asada@db.soc.i.kyoto-u.ac.jp

Masatoshi Yoshikawa
email: yoshikawa@i.kyoto-u.ac.jp

Yang Cao

"When and where do you want to hide?" -Recommendation of location privacy preferences with local differential privacy

Keywords: Privacy preference, Location data, Matrix factorization, Local differential privacy

In recent years, it has become easy to obtain location information quite precisely. However, the acquisition of such information has risks such as individual identification and leakage of sensitive information, so it is necessary to protect the privacy of location information. For this purpose, people should know their location privacy preferences, that is, whether or not he/she can release location information at each place and time. However, it is not easy for each user to make such decisions and it is troublesome to set the privacy preference at each time. Therefore, we propose a method to recommend location privacy preferences for decision making. Comparing to existing method, our method can improve the accuracy of recommendation by using matrix factorization and preserve privacy strictly by local differential privacy, whereas the existing method does not achieve formal privacy guarantee. In addition, we found the best granularity of a location privacy preference, that is, how to express the information in location privacy protection. To evaluate and verify the utility of our method, we have integrated two existing datasets to create a rich information in term of user number. From the results of the evaluation using this dataset, we confirmed that our method can predict location privacy preferences accurately and that it provides a suitable method to define the location privacy preference.

Introduction

In recent years, due to the popularization of smartphones and the development of GPS positioning equipment, location information for people has been able to be obtained quite precisely and easily. Such data can be utilized in various fields such as marketing and urban planning. In addition, there are many applications that do not function effectively without location information [START_REF] Kanza | An online marketplace for geosocial data[END_REF]. Because of such value, market maintenance to buy and sell it has started [START_REF] Kanza | An online marketplace for geosocial data[END_REF].

However, on the other hand, by publishing accurate location information, there are privacy risks associated with such as individuals being identified [START_REF] De Montjoye | Unique in the crowd: The privacy bounds of human mobility[END_REF].

Due to such risks, privacy awareness regarding location information among people is very high. One of the most risky situations is when smartphones are used. This is because we are sending location information to them when using many applications [START_REF] Fawaz | Location privacy protection for smartphone users[END_REF].

In order to prevent privacy risks under such circumstances, it is necessary to anonymize or obfuscate location information. One of the countermeasures is a primitive one: turn off location information transmission manually when using a smartphone. There is also a method of applying a location privacy protection technique. Various techniques are used for protection, including k-anonymity [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF] [6], differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF] [START_REF] Jiang | Publishing trajectories with differential privacy guarantees[END_REF], and encryption [START_REF] Wasef | Rep: Location privacy for vanets using random encryption periods[END_REF]. Fawaz [START_REF] Fawaz | Location privacy protection for smartphone users[END_REF] proposed a system that applies these privacy protection technologies to smartphones. This system controls the accuracy of the location information sent to each application. The user needs to input how accurate he/she wants to send the respective location information to each application.

In these countermeasures, to avoid a privacy risk by the disclosure of location information, the user has to decide location privacy preference for each location, that is, whether or not he/she publishes the location data at a certain place and time. However, we think that there is a problem in such a situation. What is the best privacy preference is unclear, and it may be different for each user. Therefore, individual users need to determine their location privacy preferences. However, most users find it difficult to determine these preferences themselves [START_REF] Sadeh | Understanding and capturing people's privacy policies in a mobile social networking application[END_REF], and it is troublesome to set the privacy preference at each time.

Therefore, we need a system to recommend location privacy preferences for decision support when choosing a user's location information privacy preference and for the promotion of safe location information release. Recently, one such system was developed using the concept of item recommendation, which is used for online shopping. Item recommendation regards the combination of location and time as an item and whether or not to release location information as a rating of the item, and it predicts the rating of an unknown item using other users' data. Zhang [START_REF] Zhao | Privacy-aware Location Privacy Preference Recommendations[END_REF] proposed a method of recommending by collaborative filtering.

We focus on the problems of existing location privacy preference recommendation methods and propose a recommendation method to solve these problems. The contributions of this research are as follows.

1. Clarifying the definition of location privacy preference: In location privacy preservation, it is important to define where and when we want to preserve location privacy, which has various granularities. Although many location privacy protection methods have been proposed in the literature, none of them addresses the problem of how to set location privacy preference. Therefore, we generate recommendation models using various granularities for time information and compare their usefulness. From these results, we find the best granularity that will produce trade-offs between the density of spatial data for the recommendation and the consideration of time.

Applying matrix facrorization to location privacy preference recommendation:

Because location privacy preferences are very sensitive, the Table 1. A comparison of our method with related work [START_REF] Zhao | Privacy-aware Location Privacy Preference Recommendations[END_REF].

Method

How to preserve privacy Related work [START_REF] Zhao | Privacy-aware Location Privacy Preference Recommendations[END_REF] Collaborative filtering (inaccurate for a large amount of data) Add noise that is not strict mathematically

Our method

Matrix Factorization (accurate for a large amount of data) Add noise based on local differential privacy system must recommend them accurately. Collaborative filtering, which was used in the method by Zhang [START_REF] Zhao | Privacy-aware Location Privacy Preference Recommendations[END_REF], experiences problems that when the number of users and products increase; accurate prediction cannot be achieved, and only the nature of either the user or product can be considered well. Therefore, we propose a method to improve by utilizing matrix factorization. As a result of experiments, we confirm that we can predict accurate evaluation values with a probability of 90% for large amount of data. 3. Recommendation with local differential privacy: Matrix factorization is involved in privacy risk, because each user needs to send their data to the recommendation system[1] [START_REF] Frey | Collaborative filtering under a sybil attack: analysis of a privacy threat[END_REF]. Location privacy preferences encompass location information of the users at a certain times and whether the information is sensitive for him/her. However, a location privacy preference recommendation that achieves highly accurate privacy protection has not been proposed so far. Actually, the method by Zhang [START_REF] Zhao | Privacy-aware Location Privacy Preference Recommendations[END_REF] did not preserve privacy in a strict mathematical sense. Therefore, we propose a recommendation method that realizes it with local differential privacy, which refers to the method by Shin [START_REF] Shin | Privacy enhanced matrix factorization for recommendation with local differential privacy[END_REF]. A comparison of our method with related work is shown in Table 1. We confirm that our method maintain precision that is the same as that achieved a method without privacy protection. 4. Generating a location information privacy preference dataset: A challenge in experiments for testing the performance of our methods is that no appropriate location privacy preference dataset is available in literature.

The only available real-world dataset of location privacy preference [START_REF] Parris | Crawdad st andrews/locshare dataset[END_REF] has few users. Such data is not suitable for the evaluation of the method using matrix factorization [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. In addition, we need bulk data in the evaluation because there are many users of recommendation in the real world. Therefore, we created an artificial dataset that combines such the location privacy preference dataset and a trajectory dataset with a large number of users.

This paper is organized as follows: We describe the knowledge necessary for realizing our goal in Section 2. Then, we describe our method in Section 3 and evaluate and discuss about our method in Section 4.

Preliminaries

Matrix factorization

Matrix factorization is one of the most popular methods used for item recommendation, which predicts the ratings of unknown items. This is an extension of collaborative filtering to improve the accuracy for the large amount of data by dimentionality reduction.

We consider the situation in which m users rate any item in n items. We express each user's rating of each item by M ⊂ {1, • • • , m} × {1, • • • , n}, and the number of ratings as M = |M|, for the user i's rating of item j. Matrix factorization predicts the ratings of unknown items given {r ij : (i, j) ∈ M}. To make a prediction, we consider a ratings matrix R = m × n, a user matrix U = d × m, and an item matrix V = d × n. The matrices satisfy the formula: R ≈ U T V .

In matrix factorization, the user i's element, i.e. the i-th column of U , is expressed by

u i ∈ R d , 1 ≤ i ≤ m,
and the item j's element, i.e. the j-th column of V , is expressed by v j ∈ R d , 1 ≤ j ≤ n, which are learned from known ratings. The user i's rating of item j is obtained by the inner product of u T i and v j . In learning, we obtain the matrices U and V , which minimize the following:

1 M ∑ (i,j)∈M (r ij -u T i v j ) 2 + λ u m ∑ i=1 ||u i || 2 + λ v n ∑ j=1 ||v j || 2 (1)
λ u and λ v are positive variables for regularization.

U and V are obtained by updating using the following formulae:

u t i = u t-1 i -γ t • {∇ ui ϕ(U t-1 , V t-1 ) + 2λ u U t-1 i } (2) v t j = v t-1 j -γ t • {∇ vj ϕ(U t-1 , V t-1 ) + 2λ v V t-1 j } ( 3
)
γ t is the learning rate at the tth iteration, and ∇ ui ϕ(U, V ) and ∇ vj ϕ(U, V ) are the gradients of u i and v j . They are obtained from derivative of (1) and expressed by the followings:

∇ ui ϕ(U, V ) = - 2 M ∑ j:(i,j)∈M v j (r ij -u T i v j ) (4)
∇ vj ϕ(U, V ) = - 2 M ∑ i:(i,j)∈M u i (r ij -u T i v j ) (5)
We predict the ratings of the unknown items by calculating U and V by these formulae.

Local differential privacy

We use local differential privacy to expand the matrix factorization into a form that satisfies privacy preservation. This approach is an extension of differential privacy [START_REF] Dwork | Differential privacy: A survey of results[END_REF], in which a trusted server adds noise to the data collected from the users. However, we assume that the server can not be trusted and use local differential privacy, in which users add noise to the data before sending the data to the server.

The idea behind local differential privacy is that for a certain user, regardless of whether or not the user has certain data, the statistical result should not change. The definition is given below:

Definition 1 (Local differential privacy) We take x ∈ N ,x ′ ∈ N . A mech- anism M satisfies ϵ-local differential privacy if M satisfies the following: P r[M (x) ∈ S] ≤ exp(ϵ)P r[M (x ′ ) ∈ S]
∀S ⊆ Range(M ) is any output that M may generate. A randomized response [START_REF] Warner | Randomized response: A survey technique for eliminating evasive answer bias[END_REF] is used to realize local differential privacy, which decides the value to output based on the specified probability when inputting a certain value. Each user can add noise to the data according to their own privacy awareness, since he/she can decide the probability.

Definition of the location privacy preference

The location privacy preference is defined by the following: Definition 2 (Location privacy preference) The location privacy preference p u (t, l), in which the user u wants to hide location information at time t in location l, is expressed by the following:

p u (t, l) = { 1 (P ositive) 0 (N egative)
1 (P ositive) means that he/she can publish location information, and 0 (N egative) means that he/she does not want to publish location information.

The time t is expressed as a slot of time divided by a certain standard, and the division method varies depending on the reference time. Additionally, the location l is represented by a combination of geographic information and a category of place or either of these. Geographical information represents the latitude and longitude or certain fixed areas, and the category represents the property of a building located in that place such as a restaurant or a school. There are various granularity regarding how to represent this information as mentioned in Section 1. As the granularity of information changes, the number of items in the recommendation and the degree of consideration of the nature of the time/location change, which influence the utility of the recommendation. However, it is not clear what kind of granularity is the best. Therefore, we confirm the best granularity, that is, the definition of best location information privacy preferences.

Recommendation method

Framework

We propose a location privacy preference recommendation method that preserves privacy. When a user enters location privacy preferences for a certain number of places and time combinations, the method outputs location privacy preferences for a combination of unknown places and times. We assume the recommendation system exists on an untrusted server. We also assume an attacker who tries to extract the location and time of users' visit and their rating based on the output of the system. Our method aims for compatibility between high availability as a recommendation scheme and privacy protection. We realize the former by matrix factorization and the latter by local differential privacy.

First, we show a rough flow for the recommendation of the location privacy preference using the normal matrix factorization below:

1. The recommendation system sends the user matrix U and item matrix V to the user. 2. The gradients are calculated by using the user's data and step 1 and sent to the system. 3. The system updates U and V by the calculated gradients.

This operation is performed a number of times, and there is a risk that the user's data is leaked to the attacker. Therefore, we add noise to the data in step 2 above to avoid such risks. When the user calculate the gradients to update U and V , noise that satisfies local differential privacy is added to the information regarding "when and where the user visits" and "whether he/she wants to publish the location information." The gradients calculated based on the noise-added data are sent to the recommendation system. We show the overview of our method in Fig. 1.

Addition of noise

We preserve privacy for the information, that is, when and where the user visits and whether he/she wants to publish their location information. In privacy protection process, we refer the method by Shin [START_REF] Shin | Privacy enhanced matrix factorization for recommendation with local differential privacy[END_REF].

First, we will describe how to add noise to the information regarding the time and location of the user's visits. Let y ij be a value indicating whether or not user i has visited place j, which is 1 if he/she has visited the place and 0 otherwise. The following equation holds:

∑ (i,j)∈M (r il -u T i v j ) 2 = ∑ n i=1 ∑ m j=1 y ij (r ij - u T i v j ) 2
. Therefore, equation ( 5) can be transformed as follows:

∇ vj ϕ(U, V ) = -2 n ∑ i:(i,j)∈M y ij u i (r ij -u T i v j ).
To protect information regarding the time and location of the user's visits from privacy attacks, we should add noise to a vector Y i = (y ij ) 1≤j≤m . We use a randomized response, and the value y * ij is obtained by adding noise to y ij as follows. Next, we describe a method of privacy protection for information on whether to disclose location information for a certain place and time combination. We add noise η ijl , which is based on a Laplace distribution, to the value

y * ij =    0,
g ij = (g ijl ) 1≤l≤d = -2u i (r ij -u T i v j ).
The noise-added value g * ijl is expressed as follows:

g * ijl = g ijl + η ijl .
Each user adds noise to his/her own data in the above way, and the noiseadded gradients, {(y * ij g * ij1 , . . . g * ijd ) : j = 1, . . . , m}, are sent to the server. By repeating the operation k times, updating the value of the matrix using the slope calculated using the data with noise added, we find the matrix for predicting the evaluation value.

Evaluation

Overview

In this section, we describe the evaluation indices and points of view to consider when verifying the utilities of our method.

We evaluate the approximation between the true ratings value. We describe the details of these metrics in Section 4.3.

In the evaluations, we compare the utilities of the recommendation methods using normal matrix factorization and local differential privacy. In addition, we evaluate the method from the following three viewpoints:

1. What is the best location privacy preference definition? 2. How much impact does changes in the privacy preservation level make? 3. What impact does changes in the number of unknown evaluation values make?

More detailed results of the evaluation can be found in [?].

Dataset

In the evaluation, we use artificial data combining the location privacy preference dataset and the position information dataset.

For the location privacy preference dataset, we use LocShare acquired from the data archive CRAWDAD [START_REF] Parris | Crawdad st andrews/locshare dataset[END_REF]. This dataset was obtained from 20 users in London and St. Andrews over one week from April 23 to 29 in 2011, with privacy preference data for 413 places. This dataset has few users, so it is not suitable for the evaluation of our method using matrix factorization [START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. In addition, we need bulk data in the evaluation because there are many users of recommendation in the real world. Therefore, we generated an artificial dataset by combining the location privacy preference dataset with the trajectory dataset Gowalla, which was acquired from the location information SNS in the U.S. This dataset includes check-in histories of various places from 319,063 users collected from November 2010 to June 2011. The total number of check-ins is 36,001,959, and the number of checked-in places is 2,844,145.

Metrics

We describe the metrics for verifying the utility of our method.

We measure how accurately the recommendation can predict the ratings. The predicted value in the recommendation can be classified based on the true evaluation value as in Table 2. For example, TP (True Positive) is the number of data that are truly Positive (can be released) and whose predicted values are also Positive. We calculate the number of TP, FP, TN, and FN results from the prediction result and measure the following two indices.

-False Positive Rate: The false positive rate is the percentage of false positives predicted relative to the number of negatives.

F P R = F P T N + F P

This metric is an index for verifying whether the location information that the user wants to disclose is not erroneously disclosed. The lower the false positive rate, the higher the accuracy of the privacy protection.

-Recall: Recall is the proportion of data predicted to be positive out of the data that are actually positive.

Recall = T P T P + F N

Recall is an index for verifying whether the location information that the user can publish is predicted to be positive, since if the released location information decreases, the benefit decreases. The higher the recall value is, the higher the utility of the recommendation.

Evaluation process

We evaluate our method from the three viewpoints mentioned in 4.1, and we adopt each of the following methods.

1. We used 10-fold cross validation, that divides the users into training data and test data , in which 90% of the users are regarded as training data and 10% of the users are regarded as test data. 2. Among the user's data included in the test data, we regard the known evaluation value as unknown according to the values of the U nknown Rate mentioned later. 3. We predict the evaluation value by using the test data and the training data which have undergone conversion processing and calculate the metrics. 4. We repeat the above process 100 times and verify the average of the evaluation indices.

In the evaluation, we change the value of one of the following parameters: time, ϵ, U nknown Rate. time is the length of the standard when dividing time into multiple slots. ϵ is privacy protection level when using local differential privacy. U nknown Rate is the ratio of what is regarded as unknown.

Results

We describe the results of experiments to confirm the utility of the recommendation method. The best location privacy preference definition: When defining the location privacy preference, the best definition regarding the granularity of the information is not yet clear. In this experiment, we examine the influence of changing the granularity of time on the utility. We change the criterion for dividing time into multiple slots as follows: time = 2, 3, 4, 6, 8, 12, the other parameters are set as follows: ϵ = 0.01 and the U nknown Rate = 0.1. The results are shown in Fig. 2.

From these results, we confirm that the precision drops when the granularity is small, that is, when the criterion time is short. This is because the coarser the definition of the granularity is, the smaller the number of goods in the recommendation, and the matrix used for prediction becomes dense. On the other hand, however, we confirm that the accuracy drops even if the granularity is too large. Therefore, in defining the location privacy preference, we should choose the criterion with the highest utility. In this evaluation, the best criterion is 8 hours.

Impact of changes in the privacy preservation level:

The strength of the privacy protection can be adjusted with the value ϵ in local differential privacy. The smaller the value of ϵ, the more privacy is protected. On the other hand, there is a risk that the utility of the recommendation decreases as the added noise become large. Therefore, we examine the influence of changing the privacy protection level on the utility. In this evaluation, we change the privacy protection level as follows: ϵ = 0.0001, 0.0003, 0.001, 0.005, 0.01, the other parameters are set as follows: time = 6 and the U nknown Rate = 0.1. The results are shown in Fig. 3.

From the results, we confirm that a normal recommendation is more useful in general, and as the value of ϵ increeases, the usefulness increases. On the other hand, however, the change in the usefulness due to the change in the value of ϵ is small for ϵ = 0.003. Larger values do not have a significant effect on the usefulness. We should select the maximum parameter that can maintain prediction accuracy, since a stronger privacy protection level is achieved for a smaller value of ϵ. Therefore, in this evaluation, the best privacy protection level is ϵ = 0.001.

Impact of changes in the number of unknown evaluation values:

We verify how much each user should know his/her privacy preference for an accurate prediction. In the evaluation, we regard a certain number of evaluated data as unevaluated in generating the model and verify the influence of the number of unknown evaluation values on the utility. We change the parameter for the percent- From these results, we confirm that the utility tends to decrease as the number of unevaluated data values increases. This is because the accuracy of the recommendation will be reduced if the training dataset is small. From these results, ideally, the user should know the location privacy preference nearly as much as possible, for about 70% of all products.

In all the evaluation, we compare the utility of the models using normal matrix factorization and local differential privacy. Since appreciable differences were not observed in devising the parameters, we confirm that the recommendation method can maintain an accuracy comparable to that of normal matrix factorization.

Conclusion

We propose a location privacy preference recommendation system that uses matrix factorization and achieves privacy protection by local differential privacy. We also confirm how to determine the best location privacy preference definition.

We evaluate our method using an artificial dataset from a location privacy preference dataset and a trajectory dataset. From its results, we confirm that our method can maintain the utility at a level that is the same as a method without privacy preservation. In addition, we confirm the best parameters, the granularity of the location privacy preference definition, the privacy protection level, and the number of rated items.

Fig. 1 .

 1 Fig. 1. Overview of our method.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Results when the time granularity is changed.

Fig. 4 .

 4 Fig. 4. Results when the U nknown Rate is changed.

Table 2 .

 2 A measure representing true or false values of the result.

	True rating
	Positive	Negative
	Predicted rating Positive TP (True Positive) FP (False Positive)
	Negative FN (False Negative) TN (True Negative)


Shun Takagi

Yang Cao

Yasuhito Asano

Masatoshi Yoshikawa

Geo-Graph-Indistinguishability: Protecting Location Privacy for LBS over Road Networks ⋆

Keywords: Location Privacy, Geo-Indistinguishability, Road Network, Differential Privacy

In recent years, Geo-Indistinguishability (GeoI) has been increasingly explored for protecting location privacy in location-based services (LBSs). GeoI is considered a theoretically rigorous location privacy notion since it extends differential privacy to the setting of location privacy. However, GeoI does not consider the road network, which may cause insufficiencies in terms of both privacy and utility for LBSs over a road network. In this paper, we first empirically evaluate the privacy guarantee and the utility loss of GeoI for LBSs over road networks. We identify an extra privacy loss when adversaries have the knowledge of road networks and the degradation of LBS quality of service. Second, we propose a new privacy notion, Geo-Graph-Indistinguishability (GeoGI), for protecting location privacy for LBSs over a road network and design a Graph-Exponential mechanism (GEM) satisfying GeoGI. We also show the relationship between GeoI and GeoGI to explain theoretically why GeoGI is a more suitable privacy notion over road networks. Finally, we evaluate the empirical privacy and utility of the proposed mechanism in real-world road networks. Our experiments confirm that GEM achieves higher utility for LBSs over a road network than the planar Laplace mechanism for GeoI under the same empirical privacy level.

INTRODUCTION

In recent years, the spread of smartphones and the improvement of GPS has led to a growing use of location-based services (LBSs). While such services have provided enormous benefits to individuals and society, the exposure of the user's location raises privacy issues. By using the location information, it is easy to identify sensitive personal information, such as that pertaining to home and family. Many methods for protecting location information have been proposed in the past decade. Most of these methods perturb the true location by using a location privacy-preserving mechanism before sending it to an LBS provider or sharing it with a third party. A mechanism takes a true location as input and outputs a perturbed location that follows a probability distribution over a location domain.

Andrés et al. [START_REF] Andrés | Geo-indistinguishability: Differential privacy for location-based systems[END_REF] defined a formal notion of location privacy based on the well-known concept of differential privacy. The definition is called geo-indistinguishability (GeoI), and an output of a mechanism achieving it guarantees indistinguishability of the true location from other locations, that is, strong privacy protection. This notion is derived from differential privacy [START_REF] Dwork | Differential privacy[END_REF], which provides a rigorous guarantee of indistinguishability of two neighboring databases. One of the most appealing features of GeoI, inherited from differential privacy, is the guarantee of privacy protection against any attacker to a certain degree.

However, since the proposal of GeoI, many studies [START_REF] Chatzikokolakis | Constructing elastic distinguishability metrics for location privacy[END_REF][START_REF] Oya | Is geo-indistinguishability what you are looking for[END_REF][START_REF] Yu | Dynamic differential location privacy with personalized error bounds[END_REF] have identified its weaknesses. Yu et al. [START_REF] Yu | Dynamic differential location privacy with personalized error bounds[END_REF] showed that GeoI did not protect location privacy against the optimal inference attack [START_REF] Shokri | Quantifying location privacy[END_REF], and they proposed the framework that adapted GeoI to the expected inference error [START_REF] Shokri | Protecting location privacy: optimal strategy against localization attacks[END_REF], a complementary notion of GeoI. Chatzikokolakis et al. [START_REF] Chatzikokolakis | Constructing elastic distinguishability metrics for location privacy[END_REF] focused on the fact that GeoI did not consider privacy for semantic information (such as population density) and proposed a mechanism that guarantees the protection of this privacy by using a graph whose weight of edges contains such information. However, this graph does not consider a road network. Oya et al. [START_REF] Oya | Is geo-indistinguishability what you are looking for[END_REF] quantified the privacy against an adversary who knows that the true location is one of two locations. The researchers showed that an output of the mechanism achieving GeoI results in a worse quality of service to protect the user's location privacy.

In this study, we find that GeoI provides inadequate privacy guarantee and insufficient utility for some LBSs over road networks, such as the k-nearest neighbor search (e.g., searching for k restaurants nearest to the user location). In such LBSs, the quality of service can be improved by taking advantage of the road network instead of the Euclidean space. This is because objects can usually move only on a predefined set of trajectories as specified by the road network and it is natural for these LBSs to use the distance on the road network [START_REF] Cho | An efficient and scalable approach to CNN queries in a road network[END_REF][START_REF] Kolahdouzan | Voronoi-based k nearest neighbor search for spatial network databases[END_REF][START_REF] Papadias | Query processing in spatial network databases[END_REF]. GeoI may not be practical for LBSs over a road network because it assumes that [START_REF] Akiba | Fast shortest-path distance queries on road networks by pruned highway labeling[END_REF] the perturbed location can be any location in a continuous plane and [START_REF] Cao | Priste: From location privacy to spatiotemporal event privacy[END_REF] the distance between locations is measured by the Euclidean distance.

Due to assumption [START_REF] Akiba | Fast shortest-path distance queries on road networks by pruned highway labeling[END_REF], GeoI may result in unexpected privacy loss. For example, as shown in Fig. 1, if a user's perturbed location is unreasonable, such as a position on the sea, an adversary can realize that such a location is impossible, which may cause unexpected privacy leakage. Next, due to assumption [START_REF] Cao | Priste: From location privacy to spatiotemporal event privacy[END_REF], GeoI may offer inadequate utility for LBSs over a road network. Taking k-nearest neighbor search using shortest path for example, as shown in Fig. 2, a user of LBS searching the nearest restaurant expects that restaurant 2 will be returned in a higher probability than restaurant 1. This is because the path to restaurant 1 is farther than to restaurant 1 because of the river. However, if the user uses a GeoI mechanism, the probabilities outputting restaurants 1 and 2 are the same since the two Euclidean distances between restaurants and the user are the same.

In this paper, we study how to protect location privacy while preserving high utility for LBS over a road network. Our contributions are threefold. First, we identify two insufficiencies of GeoI by two empirical evaluations. We quantitatively analyze the change of the inference error w.r.t. adversaries having the knowledge of road network or not when the location is protected by the planar Laplace mechanism that Andrés et al. [START_REF] Andrés | Geo-indistinguishability: Differential privacy for location-based systems[END_REF] proposed, and show its privacy leakage. Additionally, we propose the formulation of the utility of the mechanism for LBSs over a road network. We compute its utility of the planar Laplace mechanism on a graph (PLG), which is our extension of PLM for LBSs over a road network, on two real-world road networks, which shows that it performs poorly w.r.t. this formulation. Second, we propose a new privacy notion based on differential privacy, called Geo-Graph-Indistinguishability (GeoGI) that takes a road network into consideration so that we can construct a more suitable mechanism than GeoI mechanism for protecting location privacy in LBSs over a road network. We design a Graph-Exponential Mechanism (GEM) satisfying GeoGI. We also show the relationship between GeoI and GeoGI to explain theoretically why GeoGI is more suitable privacy notion for LBSs over a road network. Third, to better understand the proposed mechanism, we empirically evaluate privacy and utility of the approach in the case of two real-world road networks in Japan; the results verify that the proposed GEM for GeoGI achieves higher utility than PLM for GeoI when both mechanisms have the same empirical privacy level.

Preliminary and Problem Setting

Geo-Indistinguishability [10]

In this section, we describe the definition of Geo-Indistinguishability (GeoI). Let X be a set of locations and let Z be a set of query outputs. Intuitively, a mechanism K achieving GeoI guarantees that K(x) and K(x ′ ) are similar to a certain degree for any two locations x, x ′ ∈ X . This means that even if an adversary obtains an output of the mechanism, he cannot distinguish the true location from other locations to a certain degree.

The multiplicative distance d P that expresses the distance between two probability distributions σ 1 and σ 2 on S is defined as

d P (σ 1 , σ 2 ) = sup S∈S | ln σ1(S)
σ2(S) | with the convention that | ln σ1 (S) σ2(S) | = 0 if both σ 1 and σ 2 are zero and ∞ if only one of them is zero. d(x, x ′ ) represents the Euclidean distance between x and x ′ . Given ϵ ∈ R + , ϵ-GeoI is defined as follows.

Definition 1. (ϵ-geo-indistinguishability) The mechanism satisfies

ϵ-GeoI iff ∀x, x ′ ∈ X , Z ⊆ Z d P (Pr(K(x) ∈ Z), Pr(K(x ′ ) ∈ Z)) ≤ ϵd(x, x ′ ) (1)
Mechanism satisfying ϵ-GeoI The authors of [START_REF] Andrés | Geo-indistinguishability: Differential privacy for location-based systems[END_REF] introduced a mechanism called planar Laplace mechanism (PLM) for achieving ϵ-GeoI. The probability distribution that PLM generates is called the planar Laplace distribution and, as its name suggests, is derived from a two-dimensional version of the Laplace distribution as follows: Pr(P LM ϵ (x) = z) = ϵ 2 2π e -ϵd(x,z) .

Problem Statement

As we described in Section 1, some LBSs improve their services by using a road network. In this paper, we assume these LBSs, where the road network G is defined as a weighted undirected graph (V, E). Let V be a set of vertices which represent points on the road network, each of which has a coordinate on the Euclidean plane, and let E be a set of edges. The weight w(a, b) of edges between connected vertices a ∈ V and b ∈ V represents the shortest distance of the road on the Euclidean plane connecting the two vertices a and b, which leads to w(a, b) ≥ d(a, b). Then, d s (v, v ′ ) represents the shortest path length between v ∈ V and v ′ ∈ V , and following inequality holds. This is because d(v, v ′ ) stands for the shortest distance as the crow flies while d s (v, v ′ ) stands for the shortest distance on the road network.

d s (v, v ′ ) ≥ d(v, v ′ ) (2)
In these LBSs, a user who wants to receive the service sends a vertex that represents his location to an untrusted LBS provider, and the LBS provider performs the service's computations w.r.t. the vertex (using the road network) and provides the service. Furthermore, we assume that there is no trusted server. Hence, a user needs to protect privacy on his device by himself.

Quantification of Utility and Privacy Guarantee

When a user uses a mechanism to protect his privacy, the quality of the service the user receives degrades. Shokri et al. [START_REF] Shokri | Quantifying location privacy[END_REF] generally quantified this quality loss, referred to as service quality loss (SQL), in LBSs when a user uses mechanism K:

SQL(π u , K, d q ) = ∑ r,r ′ π u (r) Pr(K(r) = r ′ )d q (r, r ′ ) (3)
Here, π u is the probability distribution representing the probability of user's location, called a prior of the user. d q (r, r ′ ) represents the metric of a degree of dissimilarity, which depends on the LBS. Thus, this means the expected value of a degree of dissimilarity between the actual location of the user and the location obfuscated by mechanism K. A weight is the shortest distance on a road connecting two vertices. πu(r) The probability of being at location r when accessing the LBS.

πa(r)

The adversary's knowledge about user's location that represents the probability of being at r. K A mechanism. Given a location, K outputs a perturbed location. d(x, x ′ ) Euclidean distance between x and x ′ . ds(v, v ′ ) The shortest path length on the graph between v and v ′ .

natural idea that the longer the Euclidean distance between the true location and the obfuscated location is, the worse the service becomes. We call this SQL e .

Shokri et al. also quantified the degree of a privacy protection by a mechanism. The researchers translated location privacy into adversarial error (AE) by measuring how accurately an adversary could infer the user's true location. Formally, AE can be formulated as follows:

AE(π a , K, h, d q ) = ∑ r,r ′ ,r π a (r) Pr(K(r) = r ′ ) Pr(h(r ′ ) = r)d q (r, r) (4)
Here, π a is the probability distribution representing the adversarial knowledge about the user's actual location, called a prior of the adversary. An inference mechanism h outputs an inferred point by drawing a point according to the probability distribution when given an obfuscated point, which stands for the inference of the adversary. Thus, Pr(h(r ′ ) = r) means the probability of estimating r as the actual location of the user when the adversary observes r ′ . Therefore, AE represents the expected value of a degree of dissimilarity d q (r, r) between the user's true location r and the location r the adversary infers. As in the case of SQL, the researchers used the Euclidean distance as d q .

The major notations in this paper are summarized in Table 1.

Evaluating Privacy and Utility of Geo-Indistinguishability

In this section, we empirically show two insufficiencies of GeoI caused by considering a road network. First, we describe the model of an adversary [START_REF] Shokri | Protecting location privacy: optimal strategy against localization attacks[END_REF]. Then, we show the insufficiency of the privacy guarantee by modeling an adversary who considers the road network and quantifying the accuracy of the attack of this adversary. Next, we describe the formulation of the utility of an output of the mechanism [START_REF] Shokri | Quantifying location privacy[END_REF]. Then, we propose the way of applying it for LBSs over a road network, and we show by experimentations with two real-world road networks that PLM performs poorly for this formulation.

Empirical Privacy Evaluation

We assume that the adversary also uses a road network to infer the user's actual location because a road network is publicly available. In the paper [START_REF] Andrés | Geo-indistinguishability: Differential privacy for location-based systems[END_REF], the authors did not consider such an adversary, and we empirically show that if the adversary considers a road network, this may lead to privacy leakage even if the mechanism satisfies GeoI, which is referred to as an insufficiency of the privacy protection.

Adversarial model First, we describe the model of the adversary who tries to infer the user's actual location. Shokri et al. [START_REF] Shokri | Protecting location privacy: optimal strategy against localization attacks[END_REF] modeled the adversary who knows the prior π a and the mechanism that the user uses and can solve problems with any computational complexity. Although this assumption is advantageous for the adversary, showing the protection against this adversary will guarantee strong privacy. When the adversary obtains the user's obfuscated location r ′ , he tries to infer the user's true location by the optimal inference attack. In this attack, an adversary solves the following mathematical optimization problem and obtains the optimal probability distribution and constructs the optimal inference mechanism h w.r.t. his knowledge; by using this mechanism with input r ′ , he estimates the user's true location.

minimize h ∑ r,r ′ ,r π a (r) Pr(K(r) = r ′ ) Pr(h(r ′ ) = r)d p (r, r) subject to ∑ r h(r ′ )(r) = 1, ∀r ′ , h(r ′ )(r) ≥ 0, ∀r ′ , r (5)
We model an adversary who knows a road network in this way. If an adversary knows a road network, the domain of his prior π a is V , and d p is d s because we assume that the adversary also tries to improve his inference w.r.t. the shortest distance. In this setting, this is a linear programming problem because Pr(h(r ′ ) = r) represents a variable and the other terms are constant so that the objective function and the constraints are linear. We solve this problem using CBC (coin-or branch and cut)1 solver of the PuLP library of Python.

Experiment

In the following paragraph, we show that the adversary who knows a road network can attack with higher accuracy than can the adversary who does not know it. To make this easy to understand, we use a simple synthetic data illustrated in Figure 3. This map consists of 1600 squares with the side length of 100 m; that is, the area dimensions are 4000 m * 4000 m, and each lattice point has a coordinate. The red line through the center represents the road where the user is considered to be, and the other area represents locations where the user must not be, such as on the sea. Thus, we assume that the user's location is determined according to a uniform distribution on the red line and inside the black frame to make an output of the mechanism planarly spread; the adversary who does not consider uses the prior given by the uniform distribution inside the black frame, and the adversary who considers the road network uses the prior given by the uniform distribution on the red line inside the black frame. Then, Fig. 4 shows AE e of each adversary w.r.t. the privacy parameter ϵ of the mechanism. Comparing AE e of both adversaries, it is clear that the adversary with the prior considering the road network can estimate the user's true location more accurately.

Remark 1 This results from that the PLM could obfuscate the user's location to a place where the user must not be; in the case of Fig. 3, anywhere except the red line. Thus, determining this place contributes to the accuracy of the attack. Fig. 4 shows that an adversarial error could become approximately half in this particular case, so this is an insufficiency of the privacy protection of GeoI.

Utility

If a user uses LBSs over a road network and uses a mechanism on the Euclidean plane, such as PLM, the user or the LBS provider needs to map the perturbed location to a vertex of the road network because the LBS provider presumes that the user is located at a vertex of the graph to take advantage of a road network. For example, in the LBS that searches for the nearest restaurants, the LBS provider needs to compute the shortest path length between vertices where the user and restaurants are located. If the user is located outside of the graph, the shortest path length cannot be computed. Then, it is worth noting that if the user (rather than the service provider) performed the mapping to the vertex before the user sent the perturbed location, it would prevent the perturbed location from being the location where the user must not be and would improve the privacy protection. In this view, we propose the mechanism on the graph, which is defined as the algorithm that outputs the perturbed vertex when given a vertex. Then, we can formulate SQL on a road network as SQL s using the shortest path length as the metric.

SQL s (π u , K) = SQL(π u , K, d s ) = ∑ v,v ′ π u (v) Pr(K(v) = v ′ )d s (v, v ′ ) (6)
In this formulation, we anticipate the lower utility of an output of the mechanism achieving GeoI because it cannot consider SQL s due to the definition using the Euclidean distance. For example, if there is a river with no bridges so that the user cannot cross it, the opposite riverside is far away and obfuscating to the opposite riverside results in the lower utility (see Fig. 2). However, GeoI may consider the opposite riverside to be close. Then, we can also formulate the adversarial error over a road network that we call AE s as follows:

AE s (π a , K, h) = AE(π a , K, h, d s ) = ∑ r,r ′ ,r π u (r) Pr(K(r) = r ′ ) Pr(h(r ′ ) = r)d s (r, r) (7)
This formula expresses the expected value of the shortest path length between the actual location and the location that an adversary with the prior of π a infers with inference mechanism h when a user uses mechanism K. Intuitively, this represents the adversarial error on a road network because we use the shortest path length d s as the metric. Thus, when the adversary can infer the true location on the road network with a high accuracy, the formula (7) will have a small value. It can be stated that if AE s is small, the privacy protection level of the mechanism is low.

Experiments Here, we empirically show that the mechanism satisfying GeoI may perform worse w.r.t. SQL s than we expect, since the definition of GeoI considers SQL as SQL e . To illustrate this, we compare SQL s and SQL e of the same GeoI mechanism. As we stated, we use a mechanism on a graph for LBSs over a road network. Then, we propose a natural and straightforward way of converting PLM to a planar Laplace mechanism on a graph (PLG). First, a user perturbs the location using PLM. Next, the user maps the perturbed location on the Euclidean plane to the nearest vertex on the road network. Fig. 5 is an example of an output of PLG. Formally, we formulate this mechanism as follows:

P r(P LG ϵ (v) = w) = ∫ Sw Pr(P LM ϵ (x v ) = z)dz (8)
Here, x v is the coordinate of vertex v, and let S w be a Voronoi cell of vertex w when the Voronoi diagram created from the graph on the Euclidean plane is given. We refer the reader to the appendix for the proof. Thus, it is assumed that this is a straightforward way of GeoI mechanism in our setting where a user needs to output a vertex as we stated in Chapter 2.2, and because we cannot use PL, it is reasonable to use this mechanism instead of PL. We compute SQL s and SQL e on two road networks. We used OpenStreetMap2 to retrieve two maps of areas of two cities, Tokyo and Akita, in Japan with dimensions of 4000 m*4000 m as in Fig. 6.

We plot the results in Fig. 7 and Fig. 8 around the range where SQL is reasonable. If the user uses the same mechanism (i.e., the same ϵ), it is observed that the utility for the LBS over a road network is worse. This outcome is caused by the difference of the Euclidean distance and the shortest path length between two vertices. Additionally, it is observed that the difference between SQL s and SQL e on the Akita graph is larger than that on the Tokyo graph at the same SQL e because the difference between the two distances on the Akita graph is larger than that on the Tokyo graph.

Remark 2 GeoI constrains the mechanism to use the Euclidean distance so that the mechanism cannot improve its utility of the output for LBSs using a road network. Regardless of how hard we try to improve the utility of the mechanism output, as long as there is the constraint of GeoI, the mechanism cannot consider a road network, and we cannot improve the mechanism. Additionally, we showed that SQL s of PLG is worse on two graphs; however, there may be a road network that results in much worse utility than we showed. Unless the mechanism considers a road network, the mechanism cannot guarantee high utility.

GEO-GRAPH-INDISTINGUISHABILITY

In this section, we propose a new definition of location privacy called Geo-Graph-Indistinguishability (GeoGI) for LBSs using a road network, which is tolerant to the weaknesses of GeoI. We first formally define GeoGI, and then propose a mechanism satisfying GeoGI which is called Graph-Exponential Mechanism (GEM). Finally, we clarify the relationship between GeoI and GeoGI, and describe validity of the definition of GeoGI.

Definition

Given a graph G = (V, E) representing a road network, let W be a set of vertices that a mechanism outputs. Then, mechanism K on the graph returns the random vertex w ∈ W according to a probability distribution when given a vertex v ∈ V . Then, given ϵ ∈ R + , ϵ-Geo-Graph-Indistinguishability is defined as follows.

Definition 2. (ϵ-Geo-Graph-Indistinguishability

) A mechanism K on a road network G = (V, E) satisfies ϵ-Geo-Graph-Indistinguishability iff ∀v, v ′ ∈ V, ∀W ⊆ W, d P (Pr(K(v) ⊆ W ), Pr(K(v ′ ) ⊆ W ) ≤ ϵd s (v, v ′ ) (9)
The definition can be also formulated as ∀v, v ′ ∈ V, ∀W ⊆ W, Pr(K(v)⊆W ) Pr(K(v ′ )⊆W ) ≤ e ϵds(v,v ′ ) . This formulation implies that GeoGI is an instance of d X -privacy [START_REF] Chatzikokolakis | Broadening the scope of differential privacy using metrics[END_REF] proposed by Chatzikokolakis et al. as are GeoI and differential privacy. The authors showed that an instance of d X -privacy guaranteed strong privacy. We refer the reader to the appendix for further details. Intuitively, this definition guarantees that for any v, v ′ ∈ V , the closer to v ′ a vertex v is w.r.t. the shortest path length, the more similar K(v) and K(v ′ ) are.

It is worth noting that the definition of GeoGI includes a given graph representing a road network, and this results in the privacy protection level and utility varying depending on the road network even if the privacy parameter ϵ remains the same.

Graph Exponential Mechanism

In this section, we propose a mechanism that achieves ϵ-GeoGI. Given parameter ϵ ∈ R + and graph G = (V, E), we define GEM ϵ for any user's location v ∈ V and perturbed location w ∈ W as follows.

Definition 3. GEM ϵ takes v as an input and outputs w with the following probability.

Pr(GEM

ϵ (v) = w) = α(v)e -ϵ 2 ds(v,w) ( 10
)
where α is a normalization factor and α

(v) = 1 ∑ w∈V e -ϵ 2 ds(v,w) .
The pseudocode of GEM is described in Appendix (Section 8.3) due to space limitation. This mechanism employs the idea of exponential mechanism [START_REF] Mcsherry | Mechanism design via differential privacy[END_REF] that is one of the general mechanisms for achieving differential privacy. Theorem 2. GEM ϵ satisfies ϵ-GeoGI.

We refer the reader to the appendix for the proof. This mechanism considers a road network so that high utility for LBSs over a road network can be expected. Moreover, since this mechanism satisfies GeoGI, strong privacy based on differential privacy is guaranteed.

Creating the Probability Distribution and Drawing a Random Point

Because we assume that the LBS provider is untrusted and there is no trusted server, a user needs to create this distribution by himself and choose the perturbed vertex according to the distribution. In this section, we describe a method to do this and its issues caused by the number of vertices.

To create the probability distribution, (i) the user gets shortest path lengths to all vertices from the vertex where the user is located. (ii) Then the user computes e -ϵ 2 ds and based on this distribution, (iii) chooses a point. Phase (i) is acceptable if the server which has enough computing power computes the all shortest lengths and sends users it in advance. This is because the shortest path length can be computed by Dijkstra's algorithm; this computational complexity of this operation depends on the data structure. if we use a naive method, it is O(|E| + |V | 2 ), and it can be improved by using Fibonacci heap to O(|E| + |V | log |V |), where |V | and |E| represent the counts of edges and vertices. However, There is a problem if the user needs to compute it and the size of vertices is large because the user uses a mobile phone with limited computing power. So we have to consider the better algorithm. On a road network, a fast algorithm computing the shortest path length has been studied; we refer the reader to [START_REF] Akiba | Fast shortest-path distance queries on road networks by pruned highway labeling[END_REF] that may be applied to our algorithm. Phase (ii) is no problem because it computational complexity is O(|V |). For phase (iii), when the number of vertices is much larger than we expected, we may not be able to effectively sample the vertices according to the distribution. This problem has also been studied and is known as consistent weighted sampling (CWS): we refer the reader to [START_REF] Manasse | Consistent weighted sampling[END_REF][START_REF] Wu | Improved Consistent Weighted Sampling Revisited[END_REF]. We believe that these studies can be applied to our algorithm and it can be computed even if the size of vertices is somewhat large.

Analyzing the relationship between GeoI and GeoGI

In this section, we describe the relationship between GeoI and GeoGI. There are two major differences: one is the domain, and the other is the distance metric.

First, we state the difference of the location domain. We can design a GeoI mechanism on the Euclidean plane; however, the same cannot be done for GeoGI because GeoGI constrains a mechanism to use a vertex on the graph due to the definition using the shortest path length. Since we exploit the mechanism for LBSs using a road network, the constraint does not pose a problem. Moreover, this constraint prevents the perturbation to a location where the user must not be located and improve the privacy guarantees, as we stated in Section 3.1. We refer the mechanism which meets this constraint as a mechanism on the graph.

The other difference is the used metric. In this part, we assume the mechanism on a graph; otherwise, we cannot design a GeoGI mechanism. Then, the following theorem holds due to the used metric of GeoGI. Theorem 3. If a mechanism on the graph satisfies ϵ-GeoI, it satisfies ϵ-GeoGI. This is due to the definition of a graph that represents the road network. Using Inequality (2), we derive the following inequality:

d P (Pr(K(v) ⊆ (W )), Pr(K(v ′ ) ⊆ (W ))) ≤ ϵd(v, v ′ ) ≤ ϵd s (v, v ′ ) ( 11
)
This inequation shows that the GeoI mechanism is also the GeoGI mechanism, but the reverse is not always true. For example, PLG satisfies both GeoI and GeoGI. This means that GeoGI relaxes the restriction of GeoI. Thus, we can design a more suitable mechanism which improves the utility for a road network.

It is worth noting whether this relaxing of the definition leads to weakening of the guarantees of privacy protection. In short, GeoGI has no guarantees of privacy protection w.r.t. the Euclidean distance so that if a user uses a mechanism that satisfies GeoGI to protect the location, the adversary may easily distinguish the user's location in terms of the Euclidean distance. In what follows, we show this fact using the notion of the true probability (TP). The probability that an adversary can distinguish user's location is represented as

T P (π u , K, h) = ∑ v,v,w π u (v) Pr(K(v) = w) Pr(h(w) = v)δ(v, v) (12)
Here δ(v, v) is a function that returns 1 if v = v holds and otherwise returns 0. TP means the expected value of a probability that an adversary can remap the obfuscated location to the true location. We assume a set of graphs, each of which has only two vertices. The Euclidean distance between the vertices is the same for all the graphs, but the weight of the edge between them is different for each graph (Fig. 9). Next, we assume that each prior the user and the adversary have is a uniform distribution on two vertices of this graph, and we compute TP of PLG and GEM. Fig. 10 shows the change of TP when the weight, that is, the shortest path length, changes. Due to the guarantee of the Euclidean distance of GeoI, PLG does not degrade TP even if the shortest path length changes, however, since GeoGI does not have a guarantee of the Euclidean distance, GEM significantly degrades TP, which means that the adversary can know the user's true location.

GeoGI can achieve better utility than can GeoI by guaranteeing privacy protection in terms of the shortest path length instead of the Euclidean distance. This idea comes from the interpretation of privacy; in this paper, we assume that privacy and the utility can be interpreted as the shortest path length on the graph and that it should be acceptable for LBSs on a road network. Therefore, GeoGI may not be suitable for protecting location privacy if the privacy should be interpreted as the Euclidean distance, e.g., querying the weather conditions where we need to protect a wide range of locations.

Discussion

We assume that a graph representing the road network is given in GeoGI. We note that setting a different graph (road network) in the definition of GeoGI implies a different privacy model. Thus, GeoGI can be personalized. For example, a conservative user may want to use a global graph in GeoGI that covers all possible locations on Earth, while a liberal user may use a smaller graph in GeoGI that only covers the city of her residence. The graph may also depend on application scenarios in practice. For example, if the application is vehicle navigation, the graph should cover all highway road network instead of pedestrian lanes. In summary, the privacy level and utility depend on the shape of the graph, such as its density and size, and its relationships should be shown because this has the potential to lead to improvement of the privacy protection and utility. This topic is left to future research.

Additionally, the utility and the privacy protection level depend on the vertex where the user uses the GeoGI mechanism because, as opposed to the Euclidean plane that spreads uniformly, each vertex relates differently with other vertices and because to satisfy GeoGI, the mechanism needs to vary the probability distribution depending on the vertex's relationship. This complexity obscures the mechanism performance for a user, and a user will not know how to adjust the privacy parameter. Then, we propose a way of measuring the performance of the mechanism used by a user located at a certain vertex. We formulate the mechanism's utility as SQLr s and its privacy protection level as AEr s as follows:

SQLr s (v, K) = ∑ v ′ Pr(K(v) = v ′ )d s (v, v ′ ) ( 13
)
AEr s (v, K, h) = ∑ v ′ ,v Pr(K(r) = r ′ ) Pr(h(v ′ ) = v)d s (v, v) (14)
When a user is located at vertex v, SQLr s represents the expected value of the shortest path length between v and the perturbed vertex v ′ . AEr s represents the expected value of the shortest path length between v and vertex v inferred by the adversary with inference mechanism h (in this case, we assume optimal inference attack). We show SQLr s and AEr s of the Akita graph using GEM with ϵ = 0.002 in Figures 11 and12, respectively. As we can see, the utility loss (i.e., SQLr s ) and privacy (i.e., AEr s ) differ on different locations in spite of the same privacy parameter. We can develop a tool to visualize the privacy and utility of the mechanism under different privacy parameters, which may help users to determine a proper privacy parameter. We defer this to a long version of this work.

EXPERIMENTS

In this section, we show that GEM outperforms the GeoI mechanism in terms of utility and privacy protection for LBSs on a road network. To demonstrate this conclusion, we performed two experiments as follows. First, since GEM, in contrast to PL, may perturb the input location to a location that is out of the road network, such as on the sea (as stated in Section 3.1), it is assumed that GEM achieves better privacy guarantee when the adversaries have the knowledge of road networks. To show this, we computed AE e of GEM on the synthetic graph we used in section 3.1. Next, because GEM, in contrast to PLG, considers a road network (as stated in Section 3.2), it is assumed that the output quality of GEM is higher than PLG. To show this, we computed SQL s of GEM for two cities we used in section 3.2. Additionally, we compared the results with those of PL and PLG.

Privacy Protection Level of GEM

We computed AE e of GEM on the graph of Fig 3 . As in section 3.1, we assume that the adversary knew the road network so that his prior was a uniform distribution on the red line inside the black frame. Since GEM, in contrast to PL, outputs only the locations on the red line, it is assumed that AE e of GEM is higher than that of PLM. To fairly compare AE e of each mechanism, we performed the comparison under the same utility SQL e .

As is shown in Fig 13, AE e of GEM is higher than that of PL in case of the adversary who knows a road network. This means that GE can protect user privacy more strongly than can PL because GE guarantees that the output is on the road network.

Utility of GEM

We computed SQL s of GEM on two graphs of Fig 6 . Since GEM considers the road network, it is assumed that SQL s of GEM is higher than that of PLG. To fairly compare SQL s of each mechanism, we performed the comparison under the same AE s . Then, we assumed that both the priors that a user and an adversary have are uniform distributions on the graph with a range of 2000 m from the centers of maps.

As we can see from Figures 14 and15, SQL s of GEM is lower than that of PLG. Thus, a GEM output has higher utility for LBSs using a road network than does a PLG output. Additionally, it can be said that the difference of the SQL between PLG and GEM is larger on the Akita graph than on the Tokyo graph. The reason is that the difference between the Euclidean distance and the shortest path length is larger for vertices of the Akita graph.

RELATED WORK

Location Privacy on a Road Network

To the best of our knowledge, this is the first study to propose the perturbation with the differential privacy approach over the road network. However, several studies explored location privacy on a road network.

Tyagi et al. [START_REF] Tyagi | Location privacy preserving techniques for location based services over road networks[END_REF] studied location privacy over a road network for VANET users, and they show that there are no comprehensive privacy-preserving techniques or frameworks that cover all privacy requirements or issues to maintain the desired level of location privacy.

Wang et al. [START_REF] Wang | Privacy-aware mobile services over road networks[END_REF] and Wen et al. [START_REF] Wen | A method of location privacy protection in road network environment[END_REF] proposed the method of privacy protection for the user who wishes to receive location-based services and travels over roads. The authors use k-anonymity as the protection method and take advantage of the road network constraints.

A series of key features distinguish our solution from these studies: a) we use the differential privacy approach so that our solution has a guarantee of privacy protection against any attacker and b) we assume that there is no trusted server. We highlight these two points as advantages of our proposed method.

State-of-the-Art Privacy Models

Since GeoI was published, many related applications have been proposed. To et al. [START_REF] To | A framework for protecting worker location privacy in spatial crowdsourcing[END_REF] developed an online framework of privacy-preserving spatial crowdsourcing service using GeoI. Tong et al. [START_REF] Tong | A jointly differentially private scheduling protocol for ridesharing services[END_REF] proposed a framework of privacypreserving ridesharing service based on GeoI and differential privacy approach. It may be possible to improve these applications by using GeoGI instead of GeoI. Additionally, Bordenabe et al. [START_REF] Bordenabe | Optimal geo-indistinguishable mechanisms for location privacy[END_REF] proposed an optimized mechanism satisfying GeoI; it may be possible to apply this method to GeoGI.

According to [START_REF] Andrés | Geo-indistinguishability: Differential privacy for location-based systems[END_REF], if a user uses the GeoI mechanism multiple times, this causes privacy degradation due to correlations in the data; this scenario also applies to GeoGI. This issue remains a difficult and intensely investigated problem in the field of differential privacy. There are two kinds of approaches attempting to solve this problem. The first is to develop a mechanism for multiple perturbations that satisfies existing notion, such as differential privacy and GeoI [START_REF] Kairouz | The composition theorem for differential privacy[END_REF][START_REF] Chatzikokolakis | A predictive differentially-private mechanism for mobility traces[END_REF]. Kairouz et al. [START_REF] Kairouz | The composition theorem for differential privacy[END_REF] studied the composition theorem and proposed a mechanism that upgrades the privacy guarantee. Chatzikokolakis et al. [START_REF] Chatzikokolakis | A predictive differentially-private mechanism for mobility traces[END_REF] proposed a method of controlling privacy using GeoI when locations are correlated. The second approach is to propose a new privacy notion for correlated data [START_REF] Xiao | Protecting locations with differential privacy under temporal correlations[END_REF][START_REF] Cao | Priste: From location privacy to spatiotemporal event privacy[END_REF]. Xiao et al. [START_REF] Xiao | Protecting locations with differential privacy under temporal correlations[END_REF] proposed δ-location set privacy to protect each location in a trajectory when a moving user sends locations. Cao et al. [START_REF] Cao | Priste: From location privacy to spatiotemporal event privacy[END_REF] proposed PriSTE, a framework for protecting spatiotemporal event privacy. We believe that these studies can be applied to our work.

CONCLUSION AND FUTURE WORK

In this paper, by evaluating privacy and utility of PL, we have shown that the definition of GeoI is insufficient for LBSs over a road network to protect privacy and output the useful perturbed location. The core of our proposal is a new notion of privacy that we call GeoGI, which takes the place of GeoI for such LBSs, and a mechanism GEM, based on the exponential mechanism, to perturb the user location. We have shown how GeoGI relates to GeoI and that GeoGI is a more suitable privacy definition for such LBSs w.r.t. privacy protection and utility. We also have shown the effectiveness of our proposed approach by comparing GEM with PLG in the example of two cities in Japan.

In the future, we aim to extend the privacy model to several graphs. Although in this paper, we represented a road network as an undirected graph, it should be represented as a directed graph because of the existence of one-way roads, and this may degrade the utility. Additionally, we need to consider the movement mode such as walking, driving, and flying. Finally, we need to pay attention to the fact that multiple perturbations of correlated data such as trajectory data may degrade the level of protection even if the mechanism satisfies GeoGI as in case of GeoI and differential privacy. This topic has been intensely studied, and we believe that it can be applied to GeoGI. We plan to solve these problems in future research.

APPENDIX

Proofs

Theorem 1. PLG ϵ on graph G = (V, E) satisfies ϵ-GeoI on graph G.

Proof. This proposition can be formulated as follows for all vertices v, v ′ ∈ V, W ⊆ W,

d p (Pr(P LG(v) ⊆ W ), Pr(P LG(v ′ ) ⊆ W )) ≤ ϵd(v, v ′ ) (15)
Furthermore, we derive

∀v, v ′ ∈ V, w ∈ W, Pr(P LG(v) = w) ≤ e ϵd(v,v ′ ) Pr(P LG(v ′ ) = w) (16)
Since PL ϵ satisfies ϵ-GeoI, for all z ∈ Z, we derive

Pr(P L ϵ (x v ) = z) ≤ e ϵd(xv,x v ′ ) Pr(P L ϵ (x v ′ ) = z) (17)
By the theorem of integral inequality we obtain

∫ Sw Pr(P L ϵ (x v ) = z)dz ≤ ∫ Sw e ϵd(xv,x v ′ ) Pr(P L ϵ (x v ′ ) = z)dz = e ϵd(xv,x v ′ ) ∫ Sw Pr(P L ϵ (x v ′ ) = z)dz (18)
Using ( 8) and ( 18), we obtain

Pr(P LG(v) = w) ≤ e ϵd(v,v ′ ) Pr(P LG(v ′ ) = w) (19)
This concludes the proof.

Theorem 2. GEM ϵ satisfies ϵ-GeoGI.

Proof. This proposition can be formulated for all vertices v, v ′ ∈ V, W ⊆ W:

d p (Pr(GEM (v) ⊆ W ), Pr(GEM (v ′ ) ⊆ W )) ≤ ϵd s (v, v ′ ) ( 20
)
The ratio of Pr(GEM (v) = w) and Pr(GEM (v ′ ) = w) is expressed as follows:

Pr(GEM (v) = w)

Pr(GEM (v ′ ) = w) = α(v)e
Next, we show that the following inequality holds:

α(v) α(v ′ ) < e ϵ 2 ds(v,v ′ ) (23)
The inequality 23 is expressed as follows for any v, v ′ ∈ V, w ∈ W of any graph G: ∑

d X -privacy

As we stated in section 4, GeoGI is an instance of d X -privacy: due to this characterization, we can give two characterizations of GeoGI that mathematically show the guarantee of strong privacy protection. In this section, we stated the characterizations of GeoGI.

Hiding function

The first characterization uses the concept of a hiding function ϕ : V → V . For any hiding function and a secret location v ∈ V , when an attacker who has a prior distribution that expresses the user's location information obtains each output w ∼ K(v), w ′ ∼ K(ϕ(v)) of a mechanism satisfying ϵ-GeoGI, the following inequality holds for the multiplicative distance between its two posterior distributions:

d P (p(v|w), p(v|w ′ )) ≤ 2ϵd s (ϕ) (26)
Let d s (ϕ(v)) = sup v∈V d s (v, ϕ(v)) be the maximum distance between an actual vertex and its hidden version. This inequality guarantees that the adversary's conclusions are the same (up to 2ϵd X (ϕ)) regardless of whether ϕ has been applied or not.

Informed attacker

The other characterization is shown by the multiplicative distance between the prior distribution and its posterior distribution that is derived by obtaining an output of the mechanism. By measuring its distance, we can determine how much the adversary has learned about the secret. We assume that an adversary (informed attacker) knows that the vertex v where the user is located in N . When the adversary obtains an output of the mechanism. The following inequality holds for the multiplicative distance between his prior distribution π |N (v) = π(v|N ) and its posterior distribution p |N (v|w) = p(v|w, N ):

d P (π |N , p |N (v|w)) ≤ ϵd s (N ) (27)
Let d s (N ) = max v,v ′ ∈N d s (v, v ′ ) be the maximum distance between vertices in N . This inequality guarantees that when d s (N ) is small, the adversary's prior distribution and its posterior distribution are similar. In other words, the more the adversary knows about the actual location, the less he cannot learn about the location from an output of the mechanism.

Pseudocode of GEM Algorithm 1: Graph Exponential Mechanism (GEM).

Input: v, G, ϵ. Output: Sanitized location w of input v. 1 initialization; 2 Compute shortest distances to all other vertices from v by Dijkstra's algorithm and calculate e -ϵ 2 ds ; 3 Normalize to make a distribution ; 4 Draw random vertex w according to the distribution; 5 return w.

Fig. 1 .

 1 Fig. 1. Perturbation of the location to the unreasonable location.

Fig. 2 .

 2 Fig. 2. Difference of the Euclidean distance and the shortest path length on a road network.

Fig. 3 .Fig. 4 .

 34 Fig. 3. A synthetic map. The dimensions are 4000 m*4000 m, and each lattice point has a coordinate. The red line indicates the road, and a user is located inside the black frame.

Fig. 5 .

 5 Fig. 5. Output of PLG.

Fig. 6 .Fig. 7 .

 67 Fig. 6. Tokyo(left) and Akita(right) road networks.

Fig. 8 .Theorem 1 .

 81 Fig. 8. SQLs and SQLe of PLG vs. ϵ on the Akita graph.

Fig. 9 .

 9 Fig. 9. Changeing the shortest path length of the graph.

Fig. 10 .

 10 Fig. 10. Change of TP according to GEM and PLG.

Fig. 11 .Fig. 12 .

 1112 Fig. 11. SQLrs of each vertex on Akita graph.

Fig. 13 .

 13 Fig. 13. AEe when using GEM and PLM against the adversary who knows the road network.

Fig. 14 .

 14 Fig. 14. SQLs of PLG and GEM w.r.t. AEs on the Tokyo graph.

Fig. 15 .

 15 Fig. 15. SQLs of PLG and GEM w.r.t. AEs on the Akita graph.

-ϵ 2

 2 ds(v,w) α(v ′ )e -ϵ 2 ds(v ′ ,w) = a(v) a(v ′ ) e ϵ 2 (ds(v ′ ,w)-ds(v,w)) (21) When -d s (v, w) + d s (v ′ ,w) has the maximum value for w ∈ W , (21) reaches the maximum value too. Due to the triangle inequality, the inequality ∀w ∈ W, -d s (v, w)+ d s (v ′ , w) ≤ -d s (v, w) + d s (v ′ , v) + d s (v, w) = d s (v, v ′) holds, and the following inequality is derived:Pr(GEM (v) = w) Pr(GEM (v ′ ) = w) ≤ α(v) α(v ′ ) e ϵ 2 ds(v,v ′ )

w∈V e -ϵ 2

 2 ds(v ′ ,w) -e ϵ 2 ds(v,v ′ ) ∑ w∈V e -ϵ 2 ds(v,w) < 0 (24)Using the triangle inequality, we have∀w ∈ W, d(v, w) -d(v, v ′ ) ≤ d s (v ′ , w), e -ϵ 2 ds(v ′ ,w) ≤ e -ϵ 2 (ds(v,w)-ds(v,v ′ )) .Therefore, ∑ w∈V (e -ϵ 2 ds(v ′ ,w) -e -ϵ 2 (ds(v,w)-ds(v,v ′ )) ) ≤ ∑ V \v (e -ϵ 2 ds(v ′ ,V ) -e -ϵ 2 ds(v ′ ,V ) ) < 0Using (22) and (23), we obtainPr(GEM (v) = w) Pr(GEM (v ′ ) = w) < e ϵ 2 ds(v,v ′ ) e ϵ 2 ds(v,v ′ ) = e ϵds(v,v ′ )(25)

Table 1 .

 1 Shokri et al. used the Euclidean distance from a Summary of notation

	Symbol	Meaning
	LBSs Location-based Services.
	u, a A user and an adversary.
	X	Set of locations of users on the Euclidean plane.
	Z	Set of query outcomes that represent the users' perturbed locations
	G	Weighted undirected graph (V, E) that represents a road network.
	V	Set of vertices on the Euclidean plane.
	E	Set of edges.

https://projects.coin-or.org/Cbc

https://openstreetmap.jp/

⋆ This work was supported by JSPS KAKENHI Grant Numbers (S) No. 17H06099, (A) No. 18H04093, (C) No. 18K11314.