## 3 Materials and Methods
### Measures  
In the present subsection, we introduce different metrics to quantify information loss, disclosure risk, and utility. **Definition 12** (Information loss [8]). : _We define the information loss for \(\widetilde{pDB}\) as the average Relative Error (RE) of the published frequent itemset. The RE is calculated over all published frequent patterns \(X\in\widetilde{pDB}\), as follows:_  
\[RE(\widetilde{pDB})=\frac{1}{|(\widetilde{pDB})|}\sum_{X\in p\widetilde{DB}} \frac{|\text{noisy }freq(X)-freq(X)|}{\max\{freq(X),0.01n\}},\]  
_where \(n\) denotes the number of users in \(sDB\) and \(0.01n\) is a sanity bound that mitigates the effect of the queries with values close to zero (as in [8])._  
**Definition 13** (Disclosure risk). : _We define the disclosure risk based on the Jensen-Shannon distance as:_  
\[DR(\widetilde{pDB})=1-JS(pDB,\widetilde{pDB}),\]  
_where the Jensen-Shannon distance is:_  
\[JS(pDB,\widetilde{pDB})=\sqrt{\frac{D(pDB_{dist}||m)+D(\widetilde{pDB}_{dist} ||m)}{2}},\]  
_where \(\widetilde{pDB}\) is the sanitized version of the frequent sequential pattern \(pDB\), \(m\) is the pointwise mean between \(pDB_{dist}\) and \(\widetilde{pDB}_{dist}\), and \(D\) is the Kullback-Leibler divergence [21]._  
Figure 1: Process of sequential patterns’ sanitization through our graph-based differentially private algorithm. Concerning the utility, different metrics have been proposed in the literature. For instance, References [9; 13; 22] used the _F-score_, while [11] used the False Negative Rate (FNR) as defined in [12]. We consider that the _F-score_ is more general than the FNR, since it combines the precision and recall, while the FNR only measures \(1-recall\). **Definition 14** (_F-score_[22]). : _Denote as \(\widehat{pDB}\) the set of frequent itemsets generated by a differentially private frequent itemset mining algorithm, and \(pDB\) is the set of correct frequent itemsets, then:_  
\[precision(\widehat{pDB})=\frac{\widehat{|pDB}\cap pDB|}{\widehat{|pDB}|},\ recall(\widehat{pDB})=\frac{\widehat{|pDB}\cap pDB|}{|pDB|},\]  
_and:_  
\[\text{F-score}(\widehat{pDB})=\frac{2*precision(\widehat{pDB})*recall( \widehat{pDB})}{precision(\widehat{pDB})+recall(\widehat{pDB})}\]  
To validate the utility of the protected sequential patterns in a recommendation task, we implemented the Extended Patricia Trie (_EPT_) that takes, as input, a set of sequential patterns and a set of item weights (i.e., some value associated with an item, for instance a cost) to predict the next items. Our implementation inspired by [23] uses a Patricia trie structure to represent sequential patterns. Once the trie is built, the algorithm searches, in a depth manner, the next items as a recommendation. To measure the utility in the recommendation task, we propose two metrics:  
**Definition 15** (Confidence Value (CV)). : _To measure how accurate the recommendation is, we use the following equation:_  
\[CV(SP_{test})=\frac{1}{|SP_{test}|}\sum_{S\in SP_{test}}f(S),\]  
_where:_  
\[f(S)= \begin{cases}1,&\text{if the next item of $SP_{train}\in SP_{test}$}\\ \\ 0,&\text{if the next item of $SP_{train}\
otin SP_{test}$}\end{cases} \]  
_where \(SP_{train}\) is the sequential patterns used for training the model and PC is the set of sequences used in the testing step._  
Thus, it assigns a value to the items that are correctly predicted. In this equation, if the evaluated item belongs to the set \(SP_{test}\), then the function returns 1; otherwise, it returns 0. **Definition 16** (Coverage). : _This metric allows measuring if the EPT is sufficiently varied to make predictions of different cases. Specifically, the Coverage (CG) shows the percentage of cases that could be evaluated from the test set.