Temporal Heterogeneous Graph Generation with Privacy, Utility, and Efficiency

We are quite grateful for your appreciation of our paper’s motivation, potential, and comprehensive experiments.

Also, thanks very much for your questions and suggestions. Addressing them improves the paper’s quality to the next level. Each detailed action and answer are presented in the below Q&A format.

W1. The introduction references social networks and citation networks as examples, but does not provide specific data or case studies to illustrate the severity of the issues and their potential impacts, making the discussion appear abstract.

In the introduction, the toy example aims to be an illustration to demonstrate the existence of the privacy issue.

In the main paper (i.e., Section 5.3), we presented the formal definition of an attacker in its mathematical form who knows the temporal structural background knowledge and uses it to identify victims.

• According to Table 3 in Section 5.3, we can see, in the original graph, if no protection mechanism is added, the attacker has the successful attack probability to be 0.00093. Adding our method, the same attacker only has the probability of 0.00006, which probability is decreased by 93.15% confidence and it is the largest decrease compared to other baselines.

To better address the your concern, during this rebuttal,

• First, we have extended our attack experiments in Section 5.3 to all four datasets, and the results are placed in Appendix A.8 with Table 7. In this table, we can see that our method still achieves the best performance across all datasets than all baselines. For your information, we put the table below. More detailed experimental description and analysis can be found in Appendix A.8, and the new paper is uploaded with new contents in the yellow color background.

Table. Attack Experiment on All Datasets. Successful Attack Probability (%) ($\downarrow$)

The above table with detailed description and discussion is added to Appendix A.8 within the yellow background.

• Second, we designed a new powerful attacker, which is more powerful in the temporal heterogeneous setting and can narrow down the candidate scope by distinguishing the node type. Its mathematical modeling is expressed in Eq. 28.
  • Different from the previous attacker in Eq. 23, when the node type is the same and the structural role is also the same at a certain timestamp, then the victim-candidate relationship can be established.
  • For example, it means that, in the citation network, an author who wrote 6 papers and a paper which is cited 6 times are not regarded as the same candidate by the attacker, only two authors who wrote the same paper at a certain time period will be regarded as the target.

The new experimental results across all datasets are shown below, where we can see our proposed method still performs the best in terms of privacy protection.

Table. Attack Experiment of Target Types on All Datasets. Successful Attack Probability (%) ($\downarrow$)

The above table with detailed description and discussion is added to Appendix A.9 within the yellow background.

Thanks very much for your review and appreciation of our paper’s motivation, novelty, and empirical demonstration.

Your suggestions are very actionable and helpful for further improving the quality of our paper. Also, your questions are addressed in the format of Q&A below.

W1. The details on hyperparameters are missing.

In Appendix A.5 - Implementation Details, we introduced the important hyperparameters of our proposed method. To better answer your question, we are providing more information about the hyperparameters of our method here.

• $\epsilon_- = 6$ for all datasets;
• $\epsilon_+ = 10, 13, 15, 18$ for MovieLens 100K dataset, MovieLens 20M dataset, DBLP dataset, and Taobao dataset, respectively;
• batch size = 32 for MovieLens 100K dataset and DBLP dataset, 64 for other datasets;
• node embedding dimension = 128;
• hidden dimensions are all set to 128;
• dropout rate = 0.2 in the attention layer;
• learning rate = 1e-4 for the generator and 1e-3 for discriminators;
• SGD optimizer is used for discriminators, while RMSprop optimizer is used for the generator;
• JUST (Hussein et al.,2018, cited in line 268) is applied to initialize node embeddings. In the running of JUST, we have the maximum walk length as 100; sample maximum of 10 walks starting from each node.

The above detailed information has been added to our paper in Appendix A.5 and marked in the yellow background.

W2. Attack experiments can be thoroughly evaluated on all the datasets.

To better address your concern, we have extended the attack experiments on all datasets, and the observation is consistent and robust with the previous results, i.e., our proposed method can reduce the attacker’s successful probability to the largest extent, compared to SOTA, as shown below.

Table. Attack Experiment on All Datasets. Successful Attack Probability (%) ($\downarrow$)

The above table with detailed description and analysis has been added to the paper in Appendix A.8 as Table 7, marked by the yellow background.

Q3. Can the paper provide more experimental results against DISCO (Xu et al. 2024), even in small-scale graphs? This could benefit the understanding of the pros and cons of different approaches.

First, we would like to clarify why we choose EDGE but not DISCO for the submission.

• EDGE is a also graph diffusion generation model which enjoys a lower complexity as it applies node filtering at each diffusion step
• EDGE is from last year, and so far, it is the one of the state-of-the-art of unsupervised single graph generation models with diffusion, to the best of our knowledge
• DISCO just published in September this year, and the code is not published yet. Moreover, DISCO is designed for small graphs (e.g., protein or molecular), not quite suitable for the scale-up settings.

Second, to better address your concern, during this rebuttal, we contacted the authors of DISCO and finally got the code to execute experiments.

Third, we searched the recently published papers and found another graph diffusion work, GraphMaker [1], published in October this year, and included it into our baseline.

With two new baselines, we did the new experiments on all datasets with our previous baselines.

The detailed analysis and comparison are marked by different colors, and they are updated in the paper and within the yellow background. More details can be seen in Table 2 of the paper, and we make the necessary highlights below.

• Diffusion models can produce some competitive performance for some metrics, but the balancing of utility, privacy, and efficiency is not as good as the proposed THePUff. For example, as shown in the below table, for the small dataset ML-100k, DISCO can produce similar privacy-protection results with ours but with the sacrifice of utility. GraphMaker can produce better utilizable generation, but the privacy is not guaranteed.

• Also, both DISCO and GraphMaker caused out-of-memory on middle (DBLP) and large (ML-20M and Taobao) datasets, which aligns our discussion and analysis in Table 1. For example, DISCO needs 54GB GPU memory for the small ML-100k dataset.

• The running time and GPU consumption of all baselines are also added to Appendix A.4 within the yellow background, where our method outperforms consistently.

---

Reference:

[1] Li et al., Graphmaker: Can diffusion models generate large attributed graphs? TMLR 2024

Q2. How does the paper handle the potential privacy leak via temporal relevance in the graph when designing the proposed method? Is this taken care of in the GAN part or the assembly part?

The privacy leakage can originate from multiple aspects, the temporal dependency is only one of them, and other sources can be structural background knowledge (e.g., who you connects reveal your identity to some extent) and feature background knowledge (e.g., user profile in the social network).

Suppose an attacker attacks the temporal heterogeneous social network to reveal someone’s identity, then our goal is to protect the user’s identity from being revealed at this timestamp.

Therefore, for the protection, our method dives in each timestamp and analyzes the node structural protection and node feature protection.

To be specific, the protection is taken care of in both GAN and assembler parts.

• GAN part is mainly for the structural protection, because differential-privacy-based permuted temporal heterogeneous graph by Eq. 2 and 3 are served as input for the discriminator, such that the generator can learn how to generated privacy-enhanced graphs without touching any real data.
• The assembler is mainly responsible for node feature protection, as shown in Algorithm 4 and Eq. 17, the assembler introduces randomness in the sampling process, which follows the meta-path frequency, preserves the locality but randomizes the high-order subgraph-level connection.

During this rebuttal, we also prepared comprehensive attacker experiments to show that the privacy is largely protected by our proposed method.

• First, we have extended our attack experiments in Section 5.3 to all four datasets, and the results are placed in Appendix A.8 with Table 7. In this table, we can see that our method still achieves the best performance across all datasets than all baselines. For your information, we put the table below. More detailed experimental description and analysis can be found in Appendix A.8, and the new paper is uploaded with new contents in the yellow color background.

Table. Attack Experiment on All Datasets. Successful Attack Probability (%) ($\downarrow$)

The above table with detailed description and discussion is added to Appendix A.8 within the yellow background.

• Second, we designed a new powerful attacker, which is more powerful in the temporal heterogeneous setting and can narrow down the candidate scope by distinguishing the node type. Its mathematical modeling is expressed in Eq. 28.
  • Different from the previous attacker in Eq. 23, when the node type is the same and the structural role is also the same at a certain timestamp, then the victim-candidate relationship can be established.
  • For example, it means that, in the citation network, an author who wrote 6 papers and a paper which is cited 6 times are not regarded as the same candidate by the attacker, only two authors who wrote the same paper at a certain time period will be regarded as the target.

The new experimental results across all datasets are shown below, where we can see our proposed method still performs the best in terms of privacy protection.

Table. Attack Experiment of Target Types on All Datasets. Successful Attack Probability (%) ($\downarrow$)

The above table with detailed description and discussion is added to Appendix A.9 within the yellow background.

We want to express our thanks to your review and your appreciation of our research’s potential, the considerable design of the method, and the thorough experimental evaluation.

Your raised suggestions are very actionable and we took each of them seriously with the answer below.

Q1. How is D_priv calculated in the proposed method? Any parameters involved? How does the parameter setting impact the performance of the proposed method?

To better understand the calculation of $\mathbb{D}\_{prv}$ and $\mathbb{D}\_{util}$, we add the detailed pseudo-code in Appendix A.10.

In Appendix A.10, we show the details of calculating $\mathbb{D}\_{util}$ and $\mathbb{D}\_{prv}$ using pseudo-code, i.e., how $\mathbb{D}\_{util}$ calculate the probability of input walk being sampled from real graph, and how $\mathbb{D}\_{prv}$ calculate the probability of input walk being sampled from perturbed graph.

$\mathbb{D}\_{util}$ and $\mathbb{D}\_{prv}$ share the exact same architecture. For example, in $\mathbb{D}\_{util}$, for a sampled walk, we first fetch the node embeddings of the nodes in the walk. Then, the node embeddings and the sampled walk are fed into the tri-level attention layer, followed by a fully connected layer, where probability of the sampled walk being sampled from original graph (or perturbed graph for $D\_{prv}$) is the output.

The detailed description is added to the Appendix A.10 within the yellow background, and the new paper is uploaded.

The hyperparameters and their values involved are also discussed in Appendix A.5, which are common hyperparameters in transformers and linear layers (e.g., batch size, learning rate, embedding size).