Towards Differential Privacy in Sequential Recommendation: A Noisy Graph
  Neural Network Approach
With increasing frequency of high-profile privacy breaches in various online
platforms, users are becoming more concerned about their privacy. And
recommender system is the core component of online platforms for providing
personalized service, consequently, its privacy preservation has attracted
great attention. As the gold standard of privacy protection, differential
privacy has been widely adopted to preserve privacy in recommender systems.
However, existing differentially private recommender systems only consider
static and independent interactions, so they cannot apply to sequential
recommendation where behaviors are dynamic and dependent. Meanwhile, little
attention has been paid on the privacy risk of sensitive user features, most of
them only protect user feedbacks. In this work, we propose a novel
DIfferentially Private Sequential recommendation framework with a noisy Graph
Neural Network approach (denoted as DIPSGNN) to address these limitations. To
the best of our knowledge, we are the first to achieve differential privacy in
sequential recommendation with dependent interactions. Specifically, in
DIPSGNN, we first leverage piecewise mechanism to protect sensitive user
features. Then, we innovatively add calibrated noise into aggregation step of
graph neural network based on aggregation perturbation mechanism. And this
noisy graph neural network can protect sequentially dependent interactions and
capture user preferences simultaneously. Extensive experiments demonstrate the
superiority of our method over state-of-the-art differentially private
recommender systems in terms of better balance between privacy and accuracy.
Wentao Hu, Hui Fang
# Towards Differential Privacy in Sequential Recommendation: A Noisy Graph Neural Network Approach

###### Abstract

With increasing frequency of high-profile privacy breaches in various online platforms, users are becoming more concerned about their privacy. And recommender system is the core component of online platforms for providing personalized service, consequently, its privacy preservation has attracted great attention. As the gold standard of privacy protection, differential privacy has been widely adopted to preserve privacy in recommender systems. However, existing differentially private recommender systems only consider static and independent interactions, so they cannot apply to sequential recommendation where behaviors are dynamic and dependent. Meanwhile, little attention has been paid on the privacy risk of sensitive user features, most of them only protect user feedbacks. In this work, we propose a novel DIfferentially Private Sequential recommendation framework with a noisy Graph Neural Network approach (denoted as DIPSGNN) to address these limitations. To the best of our knowledge, we are the first to achieve differential privacy in sequential recommendation with dependent interactions. Specifically, in DIPSGNN, we first leverage piecewise mechanism to protect sensitive user features. Then, we innovatively add calibrated noise into aggregation step of graph neural network based on aggregation perturbation mechanism. And this noisy graph neural network can protect sequentially dependent interactions and capture user preferences simultaneously. Extensive experiments demonstrate the superiority of our method over state-of-the-art differentially private recommender systems in terms of better balance between privacy and accuracy.

## 1 Introduction

Recent years have witnessed the tremendous development of various online platforms such as Facebook, Amazon and eBay, they are playing an increasingly important role in users' daily life. And recommender system is the core component of online platforms for providing personalized services, it takes advantage of abundant personal information to recommend items or services that match user preference [1]. The direct access to sensitive personal information makes recommender system a common target of privacy attacks and thus aggravates users privacy concern. [2] find that the actions of arXiv users would be potentially "visible" under targeted attack and they propose to change the privacy settings of the recommender algorithm to mitigate such privacy risk. [3] points out that mobile health applications pose new risks to privacy as they need a large volume of health data to be collected, stored and analyzed. And [4, 5] show that users' sensitive attributes such as racial information, sexual orientation and political inclinations can be precisely predicted from their interaction history in online platforms by attribute inference attack [6, 7]. Even the outputs of recommender systems are likely to reveal users' sensitive attributes and actual interactions to malicious attackers [8, 9]. In a nutshell, despite the ubiquity of recommender system in various online platforms, it is vulnerable to privacy attacks and may cause leakage of sensitive personal information. Besides, the enactment of General Data Protection Regulation (GDPR) [10] raises users' awareness of privacy and makes it more urgent to devise privacy-preserving recommender systems.

Existing recommender systems (RSs) can be mainly classified into two categories: one category is traditional RSs which includes content-based and collaborative filtering RSs; the other category is sequential RSs [11, 12]. Traditional
RSs model users' historical interactions in a static and independent way, so they can only capture the static long-term preference but ignore to consider short-term interest and the sequential dependencies among user interactions. In contrast, sequential RSs treat user interactions as a dynamic sequence and take sequential dependencies into account to capture both long-term and short-term interest [13]. Figure 1 is an illustration of sequential RS, where each user's interactions are indexed chronologically to form a historical interaction sequence. And sequential RSs need to predict users' next interacted items based on their historical behavior sequences [14; 15; 16; 17]. Due to the capability of capturing users' dynamic and evolving preferences, sequential RSs are quite important and popular in modern online platforms and have attracted much attention in academia. Therefore, we focus on sequential RSs in this paper and derive to build a privacy-preserving sequential RS that can simultaneously resist to privacy attacks and retain considerable recommendation performance.

Previous studies on privacy-preserving RSs mainly adopt anonymisation [18], encryption [19; 20] and differential privacy [21; 22] to protect sensitive user information. The drawback of anonymisation-based RSs is that they cannot provide a provable privacy guarantee or resist to reconstruction attacks [23; 24]. Meanwhile, encryption-based RSs bring heavy computation overhead and fail to prevent attackers from inferring sensitive user information based on the exposed output of RSs [4]. So we resort to differential privacy [25] to build a privacy-preserving sequential RS on account of its provable privacy guarantee and lightweight computation overhead. On the other hand, differentially private sequential RSs are quite under-explored because of the challenge to consider sequential dependencies in differential privacy. Existing differentially private RSs are all based on traditional RSs, which can further be divided into two categories. The first category focuses on neighbor-based collaborative filtering [4; 26; 27], where noise is added into the calculation of item/user similarity matrix to protect users' sensitive interactions. The second category is based on matrix factorization [22; 21; 28; 29]. They add noise into the objective function or gradients in order to protect users' ratings or the fact that a user has rated an item. Despite their effectiveness being partially validated, we argue that these solutions suffer from the following three major limitations.

First, they model users' preferences based on static rating matrix, thus cannot capture dynamic and evolving preferences in users' interaction sequences. Second, interactions are considered to be independent and equally important in existing differentially private RSs. Nevertheless, users' behavior sequences are characterized by complicated sequential dependencies [15; 30] and the most recent interactions may have greater influence on user preferences [11], thus these solutions are not applicable in sequential recommendation. Third, they only protect users' explicit ratings or implicit feedbacks while neglect protection on users' side information such as user demographics. [31] show that there are privacy risks on users' side information, for example, user gender can be accurately inferred from users' ratings. Although [6] design a dual-stage perturbation strategy to protect sensitive user features, they ignore to protect on users' interactions let alone dependent behavior sequences. In short, none of these differentially private RSs focus on protecting users' sensitive features and interactions simultaneously in order to achieve a better balance between privacy and utility.

To bridge the above research gaps, we propose a differentially private sequential recommendation framework called DIPSGNN to protect user features and sequentially dependent interactions at the same time. Specifically, we first take advantage of piecewise mechanism [32] to protect users' sensitive features at input stage and use the perturbed features to initialize user embedding. Then, a gated graph neural network [33] is employed to capture sequential dependencies and dynamic preferences in users' behavior sequences. In this gated graph neural network, we innovatively add calibrated noise into the aggregation step based on aggregation perturbation mechanism [34] to prevent attackers from inferring users' private interactions based on the exposed recommendation results. To summarize, the main contributions of our work are as follows:

Figure 1: A toy example of sequential RS. Each user’ interactions are indexed chronologically to form a interaction sequence. And sequential RSs need to predict the next items that users will interact based on historical interaction sequences.
1. To the best of knowledge, we are the first to achieve differential privacy for dependent interactions in sequential recommendation.
2. We propose a novel aggregation scheme that can protect time-dependent interactions and capture user preferences without considerably impairing performance.
3. Both users' features and interactions are well-protected in DIPSGNN which offers a better balance between privacy and accuracy.
4. Theoretical analysis and extensive experiments on three real-world datasets demonstrate the effectiveness and superiority of DIPSGNN over state-of-the-art differentially private recommender systems.

The rest of this article is structured as follows. Section 2 reviews the related work. Section 3 introduces the preliminaries and problem setup. Section 4 elaborates on the technical details of our proposed DIPSGNN. Section 5 discusses the experimental results and analyses. Finally, we conclude this article and propose several future directions in Section 6.

## 2 Related Work

In this section, we review three lines of studies related to our work including: sequential recommendation, differentially private recommender systems and privacy-preserving graph neural network.

### Sequential Recommendation

Sequential recommendation recommends the next item based on the chronological sequence of users' historical interactions. The earliest work [35] on sequential recommendation leverages Markov decision process to model item transition. Later, FPMC [36] fuses the idea of Markov chains with matrix factorization, it learns the first order transition matrix by assuming next item is only relevant with the previous one. Nevertheless, these conventional methods combine past components independently and neglect long range dependency. For stronger ability to model long-term sequential dependency, deep learning based methods represented by recurrent neural networks (RNN) [37; 38; 39] and attention mechanism [15; 40; 41] have been in blossom in sequential recommendation. For example, [39] combines the architecture of RNN and Convolutional Neural Network to capture complex dependencies in user behavior sequences. And attention-based neural networks such as Transformer [42; 43] and BERT [16] use attention scores to explore item-item relationships and achieve remarkable performance in sequential recommendation. Recently, graph neural networks (GNN) [44; 45; 17] have attracted much interest in sequential recommendation, as the input data can be represented by graphs. SRGNN [46] converts user behavior sequences into directed graphs and learns item embeddings on these graphs with gated graph neural network [33]. APGNN [47] promotes SRGNN by fusing personalized user characteristics with item transition patterns in user behavior graphs in order to better model user preferences. SUGRE [30] reconstructs loose item sequences into tight item-item interest graphs based on metric learning, which further improves the performance of GNN in sequential recommendation. By elaborately modeling user interest based on graphs constructed from interaction sequences, GNN-based methods have demonstrated great effectiveness in sequential recommendation.

### Differentially private recommender systems

Differential privacy [25] has been introduced into recommender systems since [4]. It adds noise into calculation of item-similarity matrix in order to protect users' explicit ratings. After that, [27] protect users' implicit feedbacks by applying binary randomized response [48] on them and then send the perturbed feedbacks to the centralized server to calculate a private item-similarity matrix. Aside from neighborhood-based collaborative filtering, there is another line of works which are based on matrix factorization (MF) [49]. [22] integrate objective perturbation into MF to make sure the final item embedding learned by MF satisfy differential privacy. Besides, they decompose the noise component into small pieces so that it can fit with the decentralized system. [21] build a differentially private MF framework by using a novel connection between differential privacy and bayesian posterior sampling via stochastic gradient langevin dynamics. And [29] further divide user ratings into sensitive and non-sensitive ones then add different amount of noise on these two kinds of ratings when calculating gradients. Finally, they achieve a uniform privacy guarantee for sensitive ratings. However, these differentially private recommender systems can only protect static rating matrix and assume that interactions are independent and equally important. They largely ignore the sequential dependencies and users' dynamic preference, which makes them inadequate for sequential recommendation. Meanwhile, the protection on user features is overlooked in these works. Though [6] shed light on the protection towards user demographics, it lacks the ability to protect interactions let alone dependent behavior sequences.
### Privacy-preserving graph neural network

Graph neural networks (GNNs) have been broadly employed in sequential recommendation as users' interaction sequences can be easily transformed into graph data. However, rich node features and edge information in GNNs make them vulnerable to privacy attacks. [50; 51; 52] show that private edges can be recovered from GNNs via the influence of particular edge on model output. To mitigate such privacy risk, various privacy-preserving techniques for GNNs are emerging. [53] propose a privacy-preserving representation learning framework on graphs from mutual information perspective. [54] perturb graphs based on combinatorial optimization to protect private node labels. Nevertheless, these methods cannot provide a formal privacy guarantee. To address this limitation, differential privacy (DP) has been applied to protect privacy in GNNs. [50] propose LapGraph to provide DP protection for sensitive edges by adding laplace noise into adjacency matrix. It can be regarded as a data mask method with formal differential privacy guarantee. But [55; 56] argue that adding noise into adjacency matrix destroys original graph structure and ruins the neighborhood aggregation inside GNNs. To remedy this defect, [34] propose an aggregation perturbation mechanism to safeguard the privacy of edges in undirected and unweighted graphs, which differs from the directed and weighted graphs in our work. More specifically, it forces the sensitivity of embedding update process equal to one by normalizing each row of embedding matrix. However, we find that this normalization step makes embedding matrix deviate too much from its true value and brings excessive noise. To resolve this problem, we normalize the rows of embedding matrix with tunable threshold for different datasets and achieves better utility.

## 3 Preliminaries

### Differential Privacy

Differential privacy [25] is a powerful tool to provide formal privacy guarantee when processing sensitive data. It ensures the output of a randomized algorithm is insensitive to the deletion/addition of one individual record in a database by adding calibrated noise to the algorithm. The formal definition of differential privacy is as follows.

**Definition 1** (Differential Privacy).: _A randomized algorithm \(\mathcal{A}\): \(\mathcal{X}^{n}\rightarrow\mathcal{Y}\) is \((\epsilon,\delta)\)-differentially private, if for all neighboring datasets \(X,X^{\prime}\in\mathcal{X}^{n}\) and all \(S\subseteq\mathcal{Y}\),_

\[\Pr[\mathcal{A}(X)\in S]\leq e^{\epsilon}\cdot\Pr\left[\mathcal{A}\left(X^{ \prime}\right)\in S\right]+\delta. \tag{1}\]

where \(\Pr[\cdot]\) represents probability, \(\epsilon>0\) is privacy budget and \(\delta>0\) is failure probability. A smaller \(\epsilon\) or \(\delta\) brings a stronger privacy guarantee but forces us to add more noise in the randomized algorithm. Besides, neighboring datasets denote a pair of datasets differing at most one record. In our work, user interaction sequences are transformed into graphs and we focus on edge-level differential privacy, so neighboring datasets represent two graphs differ at only one edge. Besides graph topology data, our work also involves multidimensional numerical and categorical user feature data. [57] propose a hybrid differential privacy notion to properly perturb heterogeneous data types in social networks. They utilize edge-level differential privacy to protect graph topology data and local differential privacy [58] to protect user attributes. Inspired by hybrid differential privacy notion, we also integrate local differential privacy into our model to protect user features, as user feature data and graph topology data have different characteristics. The formal definition of local differential privacy is as follows:

**Definition 2** (Local Differential Privacy).: _A randomized function \(f(\cdot)\) satisfies \(\epsilon-\mathrm{LDP}\) if and only if for any two respective inputs \(x\) and \(x^{\prime}\) of one user and all output \(y\),_

\[\Pr\left[f(x)=y\right]\leq e^{\epsilon}\cdot\Pr\left[f\left(x^{\prime}\right) =y\right], \tag{2}\]

where \(\epsilon\) is also called privacy budget. A lower \(\epsilon\) provides stronger privacy guarantee but forces us to add heavier noise on each user's data. In local differential privacy, the perturbation of each user's data guarantees that an external attacker cannot easily infer which of any two possible inputs \(x\) and \(x^{\prime}\) from one user is used to produce the output \(y\). Thus, the true input value of this user is protected with high confidence.

### Problem Statement

Let \(U=\{u_{i}\}_{i=1}^{|U|}\) and \(V=\{v_{j}\}_{j=1}^{|V|}\) be the set of users and items in the system, respectively. Each user \(u\) has a behavior sequence in the chronological order \(S^{u}=\{v_{s}^{u}\}_{s=1}^{n_{u}}\) (\(v_{s}^{u}\in V\), and \(n_{u}\) is the length of user \(u\)'s behavior sequence) and a sensitive feature vector \(\mathbf{x}_{u}\). We convert each \(S^{u}\) into a directed weighted graph \(\mathcal{G}^{u}=(\mathcal{V}^{u},\mathcal{E}^{u})\), where \(\mathcal{V}^{u}\) and \(\mathcal{E}^{u}\) represent the set of item nodes, and the set of edges, respectively. All numerical features in \(\mathbf{x}_{u}\) are normalized into \([-1,1]\) with min-max normalization and all categorical features are encoded into one-hot vectors. Based on \(\{\mathcal{G}^{u}|u\in U\}\) and \(\{\mathbf{x}_{u}|u\in U\}\), the goal of our work is to _build a differentially private sequential recommendation framework to
generate accurate top-\(K\) recommendation list for each user, meanwhile prevent outside malicious attackers from inferring users' sensitive features and sequentially dependent interactions._

## 4 Methodology

Our proposed DIPSGNN seeks to protect sensitive user features and interactions without sacrificing considerable performance in sequential recommendation. Figure 2 depicts the overview of DIPSGNN: we first protect users' features by perturbing them at input stage. Then, we convert each user's behavior sequence \(S^{u}\) into a user behavior graph \(\mathcal{G}^{u}\) and feed it into DIPSGNN to update user embedding and item embedding. And we add calibrated noise in DIPSGNN layer to prevent the leakage of user interactions from recommendation results. Finally, the updated user embedding and item embedding are concatenated to make next-item recommendation. We will elaborate on details of these components subsequently.

### User Feature Protection

To protect sensitive user features, we adopt the strategy to perturb them at input stage with local differential privacy. Concretely, we add noise to raw user features based on piecewise mechanism (PM) [32], as it can handle multi-dimensional numerical and categorical features. With the post-processing property of differential privacy, user features will keep private during recommendation. Suppose user \(u\)'s feature vector consists of \(n\) different features, where each numerical feature is represented by a single number and each categorical feature is represented by a single one-hot vector. Thus, user \(u\)'s feature vector \(\mathbf{x_{u}}=\mathbf{x_{1}}\oplus\mathbf{x_{2}}\oplus\cdots\oplus\mathbf{x _{n}}\in\mathbb{R}^{d_{0}}\) (\(d_{0}\geq n\)), where \(\oplus\) is the concatenation operation. In this part, we aim to perturb user features with privacy budget \(\epsilon_{1}\). If we perturb each feature equally, then the privacy budget for each feature shrinks to \(\epsilon_{1}/n\). This will harm the utility of the perturbed data as the incurred noise variance is not minimized in this case. To achieve the lowest incurred noise variance, we randomly select \(k\) (\(k<n\)) features from \(\mathbf{x}_{u}\) and perturb each of them with privacy budget \(\epsilon_{1}/k\), while the non-selected features are dropped by masking them with \(0\) to avoid privacy leakage. We further follow [32] to set \(k\) as:

\[k=\max\{1,\min\{n,\lfloor\frac{\epsilon_{1}}{2.5}\rfloor\}\}. \tag{3}\]

For each \(\mathbf{x}_{i}\) in the \(k\) selected features, if it is a numerical feature, we first normalize it into \([-1,1]\) with min-max normalization and then perturb it by executing Algorithm 1 with privacy budget \(\epsilon=\frac{\epsilon_{1}}{k}\). On the contrary, if the selected \(\mathbf{x}_{i}\) is a categorical feature, as it is represented by an one-hot vector, we perturb it with optimized unary encoding (OUE) method [59]. Because OUE method will minimize the variance when perturbed one-hot vector has a higher dimension. The details of OUE method are shown in Algorithm 2. By integrating the perturbation for numerical features and categorical features, the whole process of PM are depicted in Algorithm 3. Theorem 1 guarantees that it satisfies \(\epsilon_{1}\)-local differential privacy.

Figure 2: The framework of DIPSGNN. First, user features are perturbed and protected at input stage. Next, we construct user behavior graph based on user interaction sequence. Then, user behavior graph is protected with our newly designed DIPSGNN at embedding update stage. Finally, we utilize updated user embedding and item embedding to make next-item recommendation without leakage of user features and interactions.
**Theorem 1**.: _Algorithm 3 satisfies \(\epsilon_{1}\)-local differential privacy._

Proof.: Please see appendix. 

### Behavior Graph Construction

To capture the complex sequential dependencies and transition patterns, we convert each user's behavior sequence \(S^{u}\) into a user behavior graph \(\mathcal{G}^{u}=(\mathcal{V}^{u},\mathcal{E}^{u})\). Inspired by [47, 46], \(\mathcal{G}^{u}\) is a directed and weighted graph whose topological structure can be represented by two adjacency matrices, \(\mathbf{A}_{u}^{out}\) and \(\mathbf{A}_{u}^{in}\). The weights in \(\mathbf{A}_{u}^{out},\mathbf{A}_{u}^{in}\) are the
occurrence number of consecutive interactions between two items. For instance, the weight in position \([i,j]\) of \(\mathbf{A}_{u}^{out}\) is \(\text{Count}(v_{i},v_{j})\), which means the number of times that user \(u\) interacts with \(v_{i}\) first, and then immediately with \(v_{j}\). It should be noted that we drop the normalization step [47; 46] to divide \(\text{Count}(v_{i},v_{j})\) by the outdegree of \(v_{i}\), otherwise the deletion of one interaction in \(S^{u}\) will affect one row rather than one element in \(\mathbf{A}_{u}^{out}\) or \(\mathbf{A}_{u}^{in}\), which impedes the subsequent differential privacy analysis.

\[\mathbf{A}_{u}^{out}[i,j] =\text{Count}(v_{i},v_{j}), \tag{4}\] \[\mathbf{A}_{u}^{in}[i,j] =\text{Count}(v_{j},v_{i}).\]

### User Behavior Protection: DIPSGNN

As we mentioned before that malicious outside attackers can infer user interactions from recommendation results, we need to add noise into the recommendation algorithm in order to protect interactions. Instead of perturbing user behavior graph at input stage, we choose to add calibrated noise into GNN propagation step to protect user interactions. The reason lies in that perturbation on user behavior graph will destroy original graph structure and distort aggregation process inside GNNs [55; 56], we will show the superiority of aggregation perturbation over graph structure perturbation by empirical experiments. In this section, we will dive into the details of aggregation perturbation inside DIPSGNN. As user characteristics impact their preferences, we consider user features when initializing user embedding. User \(u\)'s embedding \(\mathbf{e}_{u}^{(0)}\) and item \(v_{i}\)'s embedding \(\mathbf{e}_{i}^{(0)}\) are initialized as:

\[\mathbf{e}_{u}^{(0)}=\widehat{\mathbf{x}}_{u}\mathbf{E}_{U},\;\mathbf{e}_{i}^ {(0)}=\mathbf{x}_{i}\mathbf{E}_{V}, \tag{5}\]

where \(\widehat{\mathbf{x}}_{u}\in\mathbb{R}^{1\times d_{0}}\) is perturbed feature of user \(u\) in Algorithm 2 and \(\mathbf{E}_{U}\in\mathbb{R}^{d_{0}\times d^{\prime}}\) is user embedding matrix. Similarly, \(\mathbf{x}_{i}\in\mathbb{R}^{1\times|V|}\) and \(\mathbf{E}_{V}\in\mathbb{R}^{|V|\times d}\) are respectively item one-hot encoding and item embedding matrix. Then, we feed the initialized user embedding and item embedding into DIPSGNN and update them iteratively.

At each time step \(t\) of node update, we fuse user embedding \(\mathbf{e}_{u}^{(t-1)}\) with item embedding \(\mathbf{e}_{i}^{(t-1)}\) to update them together. \(\mathbf{h}_{i}^{(t-1)}=\mathbf{e}_{i}^{(t-1)}\oplus\mathbf{e}_{u}^{(t-1)}\in \mathbb{R}^{1\times(d+d^{\prime})}\) denotes the joint embedding at \(t-1\) time for item \(v_{i}\), where \(\oplus\) is the concatenation operation. Combining the joint embedding of all items, we can get a joint embedding matrix \(\mathbf{H}^{(t-1)}\in\mathbb{R}^{|V|\times(d+d^{\prime})}\). To bound the sensitivity of joint embedding matrix and facilitate the privacy analysis, we clip each row of \(\mathbf{\bar{H}}^{(t-1)}\) to make its norm equal to a constant \(C\). And \(C\) can be properly tuned on different datasets for better utility.

\[\mathbf{\bar{H}}_{i}^{(t-1)}=\mathbf{h}_{i}^{(t-1)}*\frac{C}{||\mathbf{h}_{i }^{(t-1)}||_{2}},\;i=1,\cdots,|V|, \tag{6}\]

where \(\mathbf{\bar{H}}_{i}^{(t-1)}\) means \(i\)-th row of \(\mathbf{\bar{H}}^{(t-1)}\). Then, we use sum aggregation to aggregate information from incoming and outgoing neighbors. This step directly accesses the adjacency matrices, \(\mathbf{A}_{u}^{in}\) and \(\mathbf{A}_{u}^{out}\), which contain sensitive structure information of interactions in user behavior sequences. Therefore, we need to add calibrated noise in this step to protect sensitive interactions:

\[\mathbf{\widehat{H}}_{out}^{(t)} =\mathbf{A}_{u}^{out}\cdot\mathbf{\bar{H}}^{(t-1)}+\mathcal{N}( \sigma^{2}\mathbb{I}), \tag{7}\] \[\mathbf{\widehat{H}}_{in}^{(t)} =\mathbf{A}_{u}^{in}\cdot\mathbf{\bar{H}}^{(t-1)}+\mathcal{N}( \sigma^{2}\mathbb{I}),\]

where \(\mathcal{N}(\sigma^{2}\mathbb{I})\in\mathbb{R}^{|V|\times(d+d^{\prime})}\) denotes a noise matrix with each element drawn from Gaussian distribution \(\mathcal{N}(0,\sigma^{2})\) independently and \(\mathbf{\widehat{H}}_{out}^{(t)},\mathbf{\widehat{H}}_{in}^{(t)}\) are privately aggregated embedding matrices. Theorem 2 will prove that this step satisfies edge-level differential privacy. Besides, the post-processing property of differential privacy [60] guarantees that any operation afterwards will keep private with respect to adjacency matrices, thus we can protect sensitive interactions during recommendation. After neighborhood aggregation, we conduct a linear transformation on the aggregated embedding matrices and get intermediate representation of node \(v_{i}\) as follows:

\[\mathbf{a}_{out_{i}}^{(t)} =(\mathbf{\widehat{H}}_{out}^{(t)}\cdot\mathbf{W}_{out})_{i}+ \mathbf{b}_{out}, \tag{8}\] \[\mathbf{a}_{in_{i}}^{(t)} =(\mathbf{\widehat{H}}_{in}^{(t)}\cdot\mathbf{W}_{in})_{i}+ \mathbf{b}_{in},\] \[\mathbf{a}_{i}^{(t)} =\mathbf{a}_{out_{i}}^{(t)}\oplus\mathbf{a}_{in_{i}}^{(t)},\]

where \(i\) in \((\mathbf{\widehat{H}}^{(t)}\cdot\mathbf{W})_{i}\) denotes the \(i\)-th row, \(\mathbf{b}_{out},\mathbf{b}_{in}\in\mathbb{R}^{1\times d}\) are bias terms, and \(\mathbf{W}_{out},\mathbf{W}_{in}\in\mathbb{R}^{(d+d^{\prime})\times d}\) are learnable parameter matrices. \(\mathbf{b}_{out},\mathbf{b}_{in},\mathbf{W}_{out},\mathbf{W}_{in}\) are shared by all users. Then, we leverage gated recurrent unit
(GRU) to combine intermediate representation of node \(v_{i}\) with its hidden state of previous time, and then update the hidden state of current time:

\[\mathbf{e}_{i}^{(t)}=\text{GRU}(\mathbf{a}_{i}^{(t)},\mathbf{e}_{i}^{(t-1)}). \tag{9}\]

It worths noting that \(\mathbf{e}_{i}^{(t-1)}\) has been normalized in Equation (6) as a part of \(\mathbf{h}_{i}^{(t-1)}\) and user embedding \(\mathbf{e}_{u}\) will also be updated implicitly in this process. The whole aggregation step in DIPSGNN are shown in Algorithm 4, and Theorem 2 proves its privacy guarantee.

**Theorem 2**.: _For any \(\delta\in(0,1)\), propagation steps \(T\geq 1\), and noise standard deviation \(\sigma>0\), Algorithm 4 satisfies edge-level \((\epsilon_{2},\delta)\)-differential privacy with \(\epsilon_{2}=\frac{TC^{2}}{2\sigma^{2}}+\frac{C\sqrt{2T\log(1/\delta)}}{\sigma}\)._

Proof.: Please see appendix. 

### Prediction and Training

After finishing the update of all DIPSGNN layers, we get the final representation of all items. Then, we need to obtain a unified representation for each user to conduct next-item prediction. First, we apply a readout function to extract each user's local preference vector \(\mathbf{z}_{l}\) and global preference vector \(\mathbf{z}_{g}\) from item representations. \(\mathbf{z}_{l}\) is defined as \(\mathbf{e}_{u_{u}}^{(T)}\), which is the final representation of the last item in user \(u\)'s behavior sequence \(S_{u}\), and \(\mathbf{z}_{g}\) is defined as:

\[\alpha_{s} =\mathbf{q}^{\top}\sigma(\mathbf{W}_{1}\mathbf{e}_{n_{u}}^{(T)}+ \mathbf{W}_{2}\mathbf{e}_{s}^{(T)}+\mathbf{c}), \tag{10}\] \[\mathbf{z}_{\text{g}} =\sum_{s=1}^{|n_{u}|}\alpha_{s}\mathbf{e}_{s}^{(T)},\]

where \(e_{s}^{(T)}\) refers to the final representation of the \(s\)-th item in \(S_{u}\), \(\mathbf{q}\in\mathbb{R}^{d}\) and \(\mathbf{W}_{1},\mathbf{W}_{2}\in\mathbb{R}^{d\times d}\) are learnable weight matrices. Following [47], we concatenate updated user embedding \(\mathbf{e}_{u}^{(T)}\) with the local and global preference vectors, then user \(u\)'s unified representation \(\mathbf{z}_{u}\) can be expressed as:

\[\mathbf{z}_{u}=\mathbf{W}_{3}(\mathbf{z}_{g}\oplus\mathbf{z}_{l}\oplus \mathbf{e}_{u}^{(T)}), \tag{11}\]

where \(\mathbf{W}_{3}\in\mathbb{R}^{d\times(2d+d^{\prime})}\) is a learnable matrix and \(d,d^{\prime}\) are the dimension of item and user embedding respectively. With user \(u\)'s unified representation and final representation of all items, we can compute the predicted probability of the next item being \(v_{i}\) by:

\[\hat{\mathbf{y}}_{i}=\frac{\exp(\mathbf{z}_{u}^{\top}\cdot\mathbf{e}_{i}^{(T )})}{\sum_{j=1}^{|V|}\exp(\mathbf{z}_{u}^{\top}\cdot\mathbf{e}_{j}^{(T)})}. \tag{12}\]
And, the loss function is cross-entropy of the prediction \(\hat{\mathbf{y}}\) and the ground truth \(\mathbf{y}\):

\[\mathcal{L}(\hat{\mathbf{y}})=-\sum_{i=1}^{|V|}\mathbf{y}_{i}\log \left(\hat{\mathbf{y}}_{i}\right)+\left(1-\mathbf{y}_{i}\right)\log\left(1- \hat{\mathbf{y}}_{i}\right). \tag{13}\]

Finally, we use the back-propagation through time (BPTT) algorithm to train the proposed DIPSGNN.

## 5 Experiments

### Experimental Settings

We evaluate the performance of all methods on three real-world datasets: ML-1M2, Yelp3 and Tmall4. In ML-1M and Tmall, we have 3 categorical user features like age range, gender and occupation, while in Yelp, we have 6 numerical user features like number of ratings, average rating and etc. For Tmall dataset, we use the click data from November 1 to November 7. After obtaining the datasets, we adopt 10-core setting to filter out inactive users and items following [30]. Table 1 shows their statistics after preprocessing. For each user, we use the first \(80\%\) of its behavior sequence as the training set and the remaining \(20\%\) constitutes the test set. And hyperparameters are tuned on the validation set which is a random \(10\%\) subset of the training set. The codes for our experiments will be released upon acceptance.

Footnote 2: grouplens.org/datasets/movielens/.

Footnote 3: [https://www.yelp.com/dataset](https://www.yelp.com/dataset).

Footnote 4: tianchi.aliyun.com/dataset/dataDetail?dataId=42.

To evaluate the performance of DIPSGNN, we compare it with six non-private baselines (BPRMF, SASRec, HRNN, LightGCN, SRGNN, and APGNN) and two private ones (DPMF and EdgeRand):

* **BPRMF**[61] is a widely used learning to rank model with a pairwise ranking objective function;
* **SASRec**[15] is a sequential prediction model based on attention mechanism;
* **HRNN**[37] uses a Hierarchical RNN model to provide personalized prediction in session-based recommendation;
* **LightGCN**[62] is a simplified graph convolution network for recommendation;
* **SRGNN**[46] utilizes the gated graph neural networks to capture item transitions in user behavior sequences;
* **APGNN**[47] considers user profiles based on SRGNN and captures item transitions in user-specific fashion;
* **DPMF**[22] is a differentially private matrix factorization method. The original one are based on explicit feedback, we denote it as DPMF_exp. There is only implicit feedback in Tmall, so we modify it with the same negative sampling strategy as BPRMF to fit in implicit feedback and denote it as DPMF_imp. We also evaluate DPMF_imp on other three datasets where ratings larger than \(1\) are regarded as positive interactions;
* **EdgeRand** is a graph structure perturbation method to protect user behaviors and the protection on user features is the same as DIPSGNN. Specifically, we add gaussian noise to the adjacency matrices of user behavior graphs to achieve the same level \((\epsilon,\delta)\)-differential privacy as DIPSGNN for fair comparison. It can be seen as a data desensitization method for graphs with formal differential privacy guarantee. The only difference between EdgeRand and existing LapGraph [50] is that one uses gaussian mechanism and the other uses laplace mechanism. As DIPSGNN uses the notation of \((\epsilon,\delta)\)-differential privacy, so we take EdgeRand as our baseline and regard it as the state-of-the-art method to protect edges in GNN following [34].

Motivated by [46; 47], we adopt Recall@\(K\) and MRR@\(K\) with \(K=5,10,20\) as our evaluation metrics. We run all the evaluations \(5\) times with different random seeds and report mean value for each method. The maximum length for

\begin{table}
\begin{tabular}{c c c c} \hline \hline Dataset & ML-1M & Yelp & Tmall \\ \hline Users & 5,945 & 99,011 & 132,724 \\ Items & 2,810 & 56,428 & 98,226 \\ Interactions & 365,535 & 1,842,418 & 3,338,788 \\ Avg. Length & 96.07 & 27.90 & 36.18 \\ User features & 3 & 6 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Statistics of datasets after preprocessing.
user behavior sequences are \(100,30,50\) for ML-1M, Yelp and Tmall respectively, which are slightly larger than the average length of user behavior sequences. We set the dimension of item embedding \(d=100\) and user embedding dimension \(d^{\prime}=50\) following [47], other hyperparameters are tuned to their optimal values on validation set. The model is trained with Adam optimizer and we train DIPSGNN 10 epochs as we observe that our model can reach convergence at that time. For all baseline methods, we use the optimal hyperparameters provided in the original papers.

As for the privacy specification setting, the privacy budget \(\epsilon_{1}\) for protecting user features in EdgeRand and DIPSGNN is set to \(20\) by default following [6]. And the privacy budget \(\epsilon_{2}\) for protecting user behaviors is set to \(5\) by default in all private methods, we numerically calibrate the noise standard deviation \(\sigma\) according to this privacy budget following [34]. \(\delta\) is set to be smaller than the inverse number of edges. Meanwhile, the different privacy budgets for user features and user behaviors capture the variation of privacy expectations of heterogeneous data types, if all the data types are treated as equally sensitive, it will add too much unneeded noise and sacrifice utility [57]. The effect of different privacy budgets will be further discussed by empirical experiments.

### Performance Comparisons

Table 2 reports the performance comparisons between DIPSGNN and other baselines in terms of Recall@20, MRR@20, Recall@10 and MRR@10.5 We have the following observations: (1) the non-private graph based method SRGNN and APGNN achieve the best performance among non-private methods, demonstrating the strong power of adopting graph neural networks to capture complex item transitions and dynamic user preferences in sequential recommendation. (2) As for private baselines, DPMF with explicit feedback outperforms that with implicit feedback, because explicit feedback carries more accurate information about user preferences. But these two DPMF methods both perform much worse than EdgeRand and DIPSGNN. We attribute this phenomenon to that DPMF assumes interactions as independent while EdgeRand and DIPSGNN consider complex dependencies between items by building model on user behavior graphs. This highlights the importance to take into account the dependencies between interactions rather than treating them as independent when protecting user interactions. (3) Our DIPSGNN consistently yields better performance than the state-of-the-art EdgeRand method for protecting interactions on all three datasets. Their relative gap in terms of Recall@20 is \(19.99\%,6.16\%,2.95\%\) on ML-1M, Yelp and Tmall respectively. And their difference is also significant in terms of other metrics, which verifies the effectiveness of DIPSGNN. Moreover, DIPSGNN even outperforms the best non-private baseline APGNN in terms of MRR@20, Recall@10 and MRR@10 on ML-1M. A possible explanation is that controlled amount of noise during training may improve the generalization performance on test set [63]. (4) The performance of DIPSGNN is more competitive than commonly used deep learning recommendation methods such as LightGCN, HRNN and SASRec. And it also beats SRGNN on ML-1M and Yelp. This demonstrates the feasibility of applying DIPSGNN in real-world applications to provide accurate recommendation and protect sensitive user information simultaneously.

Footnote 5: We can get similar results regarding \(K=5\). Due to space limitation, we do not report.

\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{Type} & \multirow{2}{*}{Method} & \multicolumn{4}{c}{ML-1M} & \multicolumn{4}{c}{Yelp} & \multicolumn{4}{c}{Tmall} \\ \cline{2-13}  & & R@20 & M@20 & R@10 & M@10 & R@20 & M@20 & R@10 & M@10 & R@20 & M@20 & R@10 & M@10 \\ \hline \multirow{8}{*}{Nonp} & BPRMF & 4.56 & 0.81 & 2.20 & 0.65 & 4.38 & 1.01 & 2.58 & 0.89 & 15.19 & 6.77 & 12.28 & 6.57 \\  & SASRec & 6.69 & 1.20 & 3.44 & 0.98 & 4.70 & 1.03 & 2.69 & 0.89 & 14.46 & 5.08 & 10.46 & 4.81 \\  & HRNN & 18.43 & 4.70 & 11.70 & 4.24 & 1.49 & 0.33 & 0.83 & 0.29 & 13.34 & 5.82 & 10.45 & 5.62 \\  & LightGCN & 8.53 & 1.67 & 4.59 & 1.40 & 6.18 & 1.41 & 3.65 & 1.24 & OOM & OOM & OOM & OOM \\  & SRGNN & 21.01 & 5.15 & 13.09 & 4.61 & 7.24 & 1.77 & 4.41 & 1.58 & 24.85 & 11.55 & 20.42 & 11.24 \\  & APGNN & 21.26 & 5.29 & 13.23 & 4.75 & 7.26 & 1.81 & 4.46 & 1.62 & 24.86 & 11.57 & 20.38 & 11.26 \\ \hline \multirow{4}{*}{Priv} & DPMF \_imp & 3.15 & 0.66 & 1.77 & 0.57 & 0.41 & 0.10 & 0.25 & 0.09 & 1.95 & 0.36 & 1.18 & 0.30 \\  & DPMF\_exp & 3.40 & 0.71 & 1.89 & 0.61 & 1.30 & 0.32 & 0.83 & 0.28 & - & - & - & - \\  & EdgeRand & 17.61 & 4.28 & 10.88 & 3.82 & 6.82 & 1.66 & 4.17 & 1.49 & 20.35 & 9.80 & 16.61 & 9.54 \\ \hline \multirow{2}{*}{Ours} & DIPSGNN & **21.13** & **6.11** & **14.04** & **5.63** & **7.24** & **1.78** & **4.45** & **1.59** & **20.95** & **9.98** & **17.15** & **9.71** \\  & Improve & 19.99\%* & 42.76\%* & 29.04\%* & 47.38\%* & 6.16\%* & 7.23\%* & 6.71\%* & 6.71\%* & 2.95\%* & 1.84\%* & 3.25\%* & 1.78\%* \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparative results of different approaches on all datasets. Bold number means DIPSGNN outperforms EdgeRand. Statistical significance of pairwise differences between DIPSGNN vs. EdgeRand is determined by a paired t-test (\({}^{*}\) for \(p<0.01\)). OOM denotes out-of-memory and R denotes Recall, M denotes MRR for succinctness. Nonp means non-private baselines and Priv means private baselines.
### Effect of Privacy Budget

To analyze the trade-off between privacy and accuracy with different privacy budgets, we first fix the budget for protecting user features \(\epsilon_{1}\) at its default value \(20\) and change the budget for protecting user interactions \(\epsilon_{2}\) in \(\{3,4,5\}\). The experimental results in terms of Recall@20 are presented in Figure 3. We can observe that both EdgeRand and DIPSGNN generally perform better with a larger \(\epsilon_{2}\), as the noise added on the adjacency matrices or item embedding matrix in GNN will both decrease when \(\epsilon_{2}\) rises thus brings more accurate recommendation. Meanwhile, DIPSGNN always outperforms EdgeRand except when \(\epsilon_{2}=3\) on Tmall. And the performance gap between them tends to enlarge with a larger \(\epsilon_{2}\), this confirms again the effectiveness of our proposed DIPSGNN for protecting user interactions. Similarly, we also conduct experiments by changing the budget for user feature protection \(\epsilon_{1}\) in \(\{10,20,30\}\) with the fixed privacy budget \(\epsilon_{2}=5\) for user interaction protection. Figure 4 shows experimental results in terms of Recall@20. The performance of EdgeRand and DIPSGNN consistently rises with a larger \(\epsilon_{1}\). As we add less noise to user features when \(\epsilon_{1}\) increases, it will facilitate more accurate modeling of user interests, leading to more satisfying recommendation results. And DIPSGNN outperforms EdgeRand all the time which again shows the superiority.

### Hyperparameter Study

#### 5.4.1 Effect of GNN Propagation Steps

In this section, we first study the influence of GNN propagation steps \(T\) on the performance of EdgeRand and DIPSGNN. We fix privacy guarantees at their default values and change GNN propagation steps \(T\) in \(\{1,2,3\}\). Figure 5 shows the experimental results obtained on three datasets. It can be observed that the performance of DIPSGNN and EdgeRand both obviously decrease with larger aggregation steps \(T\). Besides, the performance decline of EdgeRand is apparently more pronounced than DIPSGNN. This is because EdgeRand adds noise to the original adjacency matrix which distorts the neighborhood aggregation inside GNNs [55, 56] and the distortion effect will become larger with more aggregation steps. Contrarily, DIPSGNN aggregates information from neighbors based on unperturbed adjacency matrix. The slight performance decrease of DIPSGNN comes from the fact that we need to add more noise on node embedding matrix to maintain the same privacy guarantee, this can be derived from Theorem 2.

#### 5.4.2 Effect of Embedding Norm

We then investigate how the norm of each row in node embedding matrix affects the performance of DIPSGNN. As we can see from Theorem 2 that a smaller \(C\) forces us to add less noise on the embedding matrix at the same privacy

Figure 4: Recall@20 of DIPSGNN and EdgeRand with different \(\epsilon_{1}\) (privacy budget for protect user features).

Figure 3: Recall@20 of DIPSGNN and EdgeRand with different \(\epsilon_{2}\) (privacy budget for protect user interactions).
guarantee, but if \(C\) is too small, the elements of embedding matrix may diverge too much from their true value. To find the proper \(C\) for each dataset, we fix privacy guarantees at their default values, GNN propagation steps \(T=1\), then select \(C\) from \(\{0.2,0.4,0.6,0.8,1\}\) for ML-1M, \(\{0.1,0.3,0.5,0.7,0.9\}\) for Yelp and Tmall. The experimental results in terms of Recall@20 are shown in Figure 6. In general, Recall@20 continues to fall with a larger \(C\) on ML-1M and Yelp, it reaches the highest value at \(C=0.2\) and \(C=0.1\) on ML-1M and Yelp respectively. On Tmall, Recall@20 first increases and reaches the highest value at \(C=0.3\), then decreases when \(C\) becomes larger. We can make a general conclusion that a large \(C\) may bring excessive noise and low utility on these three datasets.

### Importance of User Features

To verify the necessity of protecting user features to get a better balance between privacy and accuracy, we compare the performance of DIPSGNN with other three variants of DIPSGNN. **Nonp** means no noise is added on user features or the training of GNN by setting \(\epsilon_{1}=\infty\) and \(\epsilon_{2}=\infty\). **Nonp-U** means no user features are exploited and user embedding is initialized by user id. Similarly, **Priv** means the normal DIPSGNN with perturbed user features and noise added on node embedding matrix during the training of GNN. And in **Priv-U**, perturbed user features are replaced by user id for initializing user embedding, but the same amount of noise is added on the node embedding matrix during the training of GNN. We show the experimental results in Figure 7 and have the following findings. In both non-private and private settings, adding user features can help to capture more accurate user preference and improve recommendation performance. It illustrates the importance of taking user side information, besides user-item interactions, into consideration for a better balance between privacy and accuracy.

## 6 Conclusions and future work

With the enactment of General Data Protection Regulation (GDPR), there is an urgent need to protect sensitive user information on various online platforms. And recommender system is the core component of online platforms, it takes advantage of rich personal information to provide personalized service. Therefore, its privacy preservation is of great concern to users and regulators. A privacy-preserving recommender system will greatly alleviate privacy concern and increase user engagement on the platform, thus promote the commercial profit and sustainable development of the platform.

Figure 5: Recall@20 of DIPSGNN and EdgeRand with different GNN aggregation steps \(T\).

Figure 6: Recall@20 of DIPSGNN with different embedding norm \(C\).
In this paper, we address how to protect sensitive user features and interactions concurrently without great sacrifice of accuracy in sequential recommender system. We propose a differentially private sequential recommendation framework named DIPSGNN. DIPSGNN protects sensitive user features by adding noise to raw features at input stage. The noise scale is determined by piecewise mechanism which can process numerical and categorical features to make them satisfy local differential privacy. And the post-processing property of differential privacy will guarantee that user features are always well protected in the recommendation algorithm. As for the protection on user interactions, we first transform interaction sequences into directed and weighted user behavior graphs. Then, user behavior graphs are fed into gated graph neural network to model sequential dependencies and user preference. In this graph neural network, we design a novel aggregation step to protect adjacency matrices of user behavior graphs, thus to protect user behaviors. Concretely, calibrated noise is added into the aggregation step to make it satisfy differential privacy with respect to adjacency matrices of user behavior graphs. And we empirically demonstrate the superiority of this aggregation perturbation method than conventional graph structure perturbation method for protecting user interactions. Besides, extensive experimental results on three datasets (ML-1M, Yelp and Tmall) evidence that our proposed DIPSGNN can achieve significant gains over state-of-the-art differentially private recommender systems.

For future work, we will extend our framework to other popular graph neural networks such as graph attention networks (GATs) [45] and GraphSAGE [64]. Besides, we are also interested in incorporating personalized privacy preferences into our framework, as users vary substantially in privacy attitudes in real life [65].

## Appendix A Proof of Theorem 1

Proof.: First, we prove Algorithm 1 satisfies \(\epsilon\)-local differential privacy.

In Algorithm 1, \(C=\frac{\exp(\epsilon/2)+1}{\exp(\epsilon/2)-1}\), \(l(x)=\frac{C+1}{2}\cdot x-\frac{C-1}{2},r(x)=l(x)+C-1\). If \(c\in[l(x),r(x)]\), then

\[\Pr(x^{\prime}=c|x) =\frac{\exp(\epsilon/2)}{\exp(\epsilon/2)+1}\cdot\frac{1}{r(x)-l( x)}\] \[=\frac{\exp(\epsilon)-\exp(\epsilon/2)}{2\exp(\epsilon/2)+2}=p.\]

Similarly, if \(c\in[-C,l(x))\cup(r(x),C]\), then

\[\Pr(x^{\prime}=c|x) =(1-\frac{\exp(\epsilon/2)}{\exp(\epsilon/2)+1})\cdot\frac{1}{2C- r(x)+l(x)}\] \[=\frac{\exp(\epsilon/2)-1}{2\exp(\epsilon)+2\exp(\epsilon/2)}= \frac{p}{\exp{(\epsilon)}}.\]

Then if \(x_{1},x_{2}\in[-1,1]\) are any two input values and \(x^{\prime}\in[-C,C]\) is the output of Algorithm 1, we have:

\[\frac{\Pr(x^{\prime}\mid x_{1})}{\Pr(x^{\prime}\mid x_{2})}\leq\frac{p}{p/\exp (\epsilon)}=\exp(\epsilon).\]

Figure 7: Performance of DIPSGNN compared with three ablation models.
Thus, Algorithm 1 satisfies \(\epsilon\)-LDP. In Algorithm 2, we let \(\epsilon=\frac{\epsilon_{1}}{k}\), so perturbation of numerical feature satisfies \(\frac{\epsilon_{1}}{k}\)-LDP. Analogously, we prove the perturbation of categorical features in Algorithm 2 satisfies \(\frac{\epsilon_{1}}{k}\)-LDP. Suppose \(\mathbf{x}_{1}\) and \(\mathbf{x}_{2}\) are any two \(m\)-dimensional one-hot vector for perturbation and the output is \(\mathbf{x}^{\prime}\). In \(\mathbf{x}_{1}\) and \(\mathbf{x}_{2}\), \(\mathbf{x}_{1}[v_{1}]=1,\mathbf{x}_{2}[v_{2}]=1\)\((v_{1}\neq v_{2})\) and all other elements are \(0\). Let \(p=0.5\) and \(q=\frac{1}{\exp(\epsilon/k)+1}\), \(p>q\), we have:

\[\frac{\Pr(\mathbf{x}^{\prime}\mid\mathbf{x}_{1})}{\Pr(\mathbf{x} ^{\prime}\mid\mathbf{x}_{2})}=\frac{\prod_{i\in[m]}\Pr(\mathbf{x}^{\prime}[i ]\mid\mathbf{x}_{1}[i])}{\prod_{i\in[m]}\Pr(\mathbf{x}^{\prime}[i]\mid \mathbf{x}_{2}[i])}\] \[=\frac{\Pr(\mathbf{x}^{\prime}[v_{1}]\mid\mathbf{x}_{1}[v_{1}]) \Pr(\mathbf{x}^{\prime}[v_{2}]\mid\mathbf{x}_{1}[v_{2}])}{\Pr(\mathbf{x}^{ \prime}[v_{1}]\mid\mathbf{x}_{2}[v_{1}])\Pr(\mathbf{x}^{\prime}[v_{2}]\mid \mathbf{x}_{2}[v_{2}])}\] \[\leq\frac{\Pr(\mathbf{x}^{\prime}[v_{1}]=1\mid\mathbf{x}_{1}[v_{1 }]=1)\Pr(\mathbf{x}^{\prime}[v_{2}]=0\mid\mathbf{x}_{1}[v_{2}]=0)}{\Pr( \mathbf{x}^{\prime}[v_{1}]=1\mid\mathbf{x}_{2}[v_{1}]=0)\Pr(\mathbf{x}^{ \prime}[v_{2}]=0\mid\mathbf{x}_{2}[v_{2}]=1)}\] \[=\frac{p}{q}\cdot\frac{1-q}{1-p}=\exp(\frac{\epsilon_{1}}{k}).\]

Thus, the perturbation of categorical feature also satisfies \(\frac{\epsilon_{1}}{k}\)-LDP. As Algorithm 3 is composed of \(k\) times perturbation of numerical or categorical feature, and all of them satisfy \(\frac{\epsilon_{1}}{k}\)-LDP, so Algorithm 3 satisfies \(\epsilon_{1}\)-LDP based on the composition theorem of differential privacy. 

## Appendix B Proof of Theorem 2

Proof.: The proof of Theorem 2 uses an alternative definition of differential privacy (DP), called Renyi Differential Privacy (RDP) [66] which is defined as follows,

**Definition 3** (Renyi Differential Privacy).: _A randomized algorithm \(\mathcal{A}\) is \((\alpha,\epsilon)\)-RDP for \(\alpha>1,\epsilon>0\) if for every adjacent datasets \(X\sim X^{\prime}\), we have:_

\[D_{\alpha}\left(\mathcal{A}(X)\|\mathcal{A}\left(X^{\prime}\right)\right)\leq\epsilon\]

_, where \(D_{\alpha}(P\|Q)\) is the Renyi divergence of order \(\alpha\) between probability distributions \(P\) and \(Q\), defined as:_

\[D_{\alpha}(P\|Q)=\frac{1}{\alpha-1}\log\mathbb{E}_{x\sim Q}\left[\frac{P(x)}{Q (x)}\right]^{\alpha}\]

A basic mechanism to achieve RDP is the Gaussian mechanism. Let \(f:\mathcal{X}\rightarrow\mathbb{R}^{d}\) and we first define the sensitivity of \(f\) as,

\[\Delta_{f}=\max_{X\sim X^{\prime}}\left\|f(X)-f\left(X^{\prime}\right)\right\| _{2}\]

Then, adding Gaussian noise with variance \(\sigma^{2}\) to \(f\) as:

\[\mathcal{A}(X)=f(X)+\mathcal{N}\left(\sigma^{2}\mathbf{e}_{d}\right),\]

where \(\mathcal{N}\left(\sigma^{2}\mathbf{e}_{d}\right)\in\mathbb{R}^{d}\) is a vector with each element drawn from \(\mathcal{N}(0,\sigma^{2})\) independently, yields an \((\alpha,\frac{\Delta_{f}^{2}\alpha}{2\sigma^{2}})\)-RDP algorithm for all \(\alpha>1\)[66].

As the analysis on \(\mathbf{A}_{u}^{out}\) and \(\mathbf{A}_{u}^{in}\) is the same, so we use \(\mathbf{A}\) to denote \(\mathbf{A}_{u}^{out}\) or \(\mathbf{A}_{u}^{in}\). If we delete an interaction from user \(u\)'s behavior sequence, \(\mathbf{A}_{u}^{out}\) and \(\mathbf{A}_{u}^{in}\) will both only change by 1 at a single position. Let \(\mathbf{A}\) and \(\mathbf{A}^{{}^{\prime}}\) be two neighboring adjacency matrix that only differ by 1 at a single position. Specifically, there exist two nodes \(p\) and \(q\) such that:

\[\begin{cases}|\mathbf{A}_{i,j}-\mathbf{A}_{i,j}^{{}^{\prime}}|=1&\text{if $i=p$ and $j=q$},\\ \mathbf{A}_{i,j}=\mathbf{A}_{i,j}&\text{otherwise}.\end{cases}\]

The sensitivity of sum aggregation step is:

\[||\mathbf{A}\cdot\bar{\mathbf{H}}^{(t-1)}-\mathbf{A}^{{}^{\prime}} \cdot\bar{\mathbf{H}}^{(t-1)}||_{F} \tag{14}\] \[=(\sum_{i=1}^{|V|}\|\sum_{j=1}^{|V|}(\mathbf{A}_{i,j}\bar{\mathbf{ H}}_{j}^{(t-1)}-\mathbf{A}_{i,j}^{{}^{\prime}}\bar{\mathbf{H}}_{j}^{(t-1)})\|_{2}^{2})^{1/2}\] \[=(\|\mathbf{A}_{p,q}\bar{\mathbf{H}}_{p}^{(t-1)}-\mathbf{A}_{p,q}^ {{}^{\prime}}\bar{\mathbf{H}}_{p}^{(t-1)}\|_{2}^{2})^{1/2}\] \[=\|(\mathbf{A}_{p,q}-\mathbf{A}_{p,q}^{{}^{\prime}})\bar{\mathbf{ H}}_{p}^{(t-1)}\|_{2}\] \[=\|\bar{\mathbf{H}}_{p}^{(t-1)}\|_{2}\] \[=C\]
where \(\tilde{\mathbf{H}}_{j}^{(t-1)}\) is the \(j\)-th row of row-normalized feature matrix \(\tilde{\mathbf{H}}^{(t-1)}\). The sensitivity of each aggregation step is \(C\) so it satisfies \((\alpha,C^{2}\alpha/2\sigma^{2})\)-RDP based on Gaussian mechanism. And, aggregation in DIPSGNN can be seen as an adaptive composition of \(T\) such mechanisms, based on composition property of RDP [66], the total privacy cost is \((\alpha,TC^{2}\alpha/2\sigma^{2})\)-RDP.

As RDP is a generalization of DP, it can be converted back to standard \((\epsilon,\delta)\)-DP using the following lemma.

**Lemma 3**.: _If \(\mathcal{A}\) is an \((\alpha,\epsilon)\)-RDP algorithm, then it also satisfies \((\epsilon+\log(1/\delta)/\alpha-1,\delta)-DP\) for any \(\delta\in(0,1)\)._

Therefore, \((\alpha,TC^{2}\alpha/2\sigma^{2})\)-RDP in DIPSGNN is equivalent to edge-level \((\epsilon_{2},\delta)\)-DP with \(\epsilon_{2}=\frac{TC^{2}\alpha}{2\sigma^{2}}+\frac{\log(1/\delta)}{\alpha-1}\). Minimizing this expression over \(\alpha>1\) gives \(\epsilon_{2}=\frac{TC^{2}}{2\sigma^{2}}+C\sqrt{2T\log(1/\delta)}/\sigma\). So we conclude that the aggregation in DIPSGNN satisfies edge-level \((\epsilon_{2},\delta)\)-DP with \(\epsilon_{2}=\frac{TC^{2}}{2\sigma^{2}}+C\sqrt{2T\log(1/\delta)}/\sigma\). 

## Acknowledgment

This work is supported by Shanghai Rising-Star Program (Grant No. 23QA1403100), Natural Science Foundation of Shanghai (Grant No. 21ZR1421900), National Natural Science Foundation of China (Grant No. 72192832), Graduate Innovation Fund of Shanghai University of Finance and Economics (Grant No.CXJJ-2022-366) and the Program for Innovative Research Team of Shanghai University of Finance and Economics.
