Temporal Heterogeneous Graph Generation with Privacy, Utility, and Efficiency
Authors: Xinyu He
Dongqi Fu
Hanghang Tong
Ross Maciejewski
Jingrui He
Venue: ICLR 2025 Spotlight (2025)
Keywords: Temporal Graph
Heterogeneous Graph
Graph Generation
Primary area: learning on graphs and other geometries & topologies

Abstract: Nowadays, temporal heterogeneous graphs attract much research and industrial attention for building the next-generation Relational Deep Learning models and applications, due to their informative structures and features. While providing timely and precise services like personalized recommendations and question answering, this rich information also introduces extra exposure risk for each node in the graph. The distinctive local topology, the abundant heterogeneous features, and the time dimension of the graph data are more prone to expose sensitive information and narrow down the scope of victim candidates, which calls for well-defined protection techniques on graphs. To this end, we propose a Temporal Heterogeneous Graph Generator balancing Privacy, Utility, and Efficiency, named THePUff. More specifically, we first propose a differential privacy algorithm to perturb the input temporal heterogeneous graph for protecting privacy, and then utilize both the perturbed graph and the original one in a generative adversarial setting for THePUff to learn and generate privacy-guaranteed and utility-preserved graph data in an efficient manner. We further propose 6 new metrics in the temporal setting to measure heterogeneous graph utility and privacy. Finally, based on temporal heterogeneous graph datasets with up to 1 million nodes and 20 million edges, the experiments show that THePUff generates utilizable temporal heterogeneous graphs with privacy protected, compared with state-of-the-art baselines.

Published as a conference paper at ICLR 2025
TEMPORAL HETEROGENEOUS GRAPH GENERATION WITH PRIVACY, UTILITY, AND EFFICIENCY
Xinyu He; Dongqi Fu", Hanghang Tong, Ross Maciejewski, Jingrui He University of Illinois Urbana- Chaaaa--,aaaiinn Meta AI, Arizona State University [xhe34, htong, jingrui]@illinee edu, {dongei fu (ul Creta. com,
ABSTRACT
Nowadays, temporal heterogeneous graphs attract much research and industrial attention for building the next-generation Relational Deep Learning models and applications, due to their informative structures and features. While providing timely and precise services like personalized recommendations and question an- swering, this rich information also introduces extra exposure risk for each node in the graph. The distinctive local topology, the abundant heterogeneous features, and the time dimension of the graph data are more prone to expose sensitive in- formation and narrow down the scope of victim candidates, which calls for well- defined protection techniques on graphs. To this end, we propose Temporal Heterogeneous Graph Generator balancing Privacy, Utility, and Efficiency, named TFF. More specifically, we first propose differential privacy algorithm perturb the input temporal heterogencous graph for protecting privacy, and then utilize both the perturbed graph and the original one in a generative adversarial set- ting for THEPUFF to learn and generate privacy-guaranin graph data an efficient manner. We further propose 6 new metrics in the tempo- ral setting to measure heterogeneous graph utility and privacy. Finally, based on temporal heterogeneous graph datasets with up to I million nodes and 20 million edges, the experiments show that THEPUFF generates utilizable temporal hetero- geneous graphs with privacy protected, compared with state-of-the-er baselines.
and stilitt-preseere
INTRODUCTION
Recently, temporal heterogeneous graphs have emerged as one of the most important fundamental components for the next-generation Relational Deep Learning (Fey et al.] 2024), owing to their comprehensive expressiveness. Equipped with temporal heterogeneous graphs, modern Relational Deep Learning models (Robinson et al./ | (0224) target to provide timely and precise applications like personalized recommendations (Qi et al. [203]] Ban et al. 2024). question answering (Li et al., 20246), classification and regression (Zheng et al., 2024] Xu et al. 2024a Wang et al., 2024a), and alignment (Zeng et al. 2023 Yu et al. 2025). During the service- prrviciig process, privacy has become an alarming concern, especially in the era of big data and AI. Then, a natural question arises: how can learn the distribution of temporal heterogeneous graphs, such that can generate utilizable data with privacy- prootcc-rotected and also take the large scalability into account?
Compared with texts and images, protecting privacy in relational data even more challenging, because the complex topology introduces additional structural information to expose the uniqueness of entities. For example, in a social network, the neighbors surrounding different users are often different, which can be leveraged by attackers to easily locate the victim and reveal the identity by the isomorphism of the ego-network (i.e., 1-hop neighbors), called neighborhood relationships attacker queries (Zhou & Pei 2008).
Beyond that, the woen-world graphs often involve heterogeneity and temporality (Fu al. 2022a Li et al. 2023 Tieu et al. 2024 [Lin et al. 2024), which makes the entity's 's existence even more unique and enlarges the exposure risk. First, heterogencous graph means the node type (and edge type) in a graph can be more than one (Shi et al. 2017 Yang et al. 2022). For example, in the citation network, the node types can include 'paper', "author', and "venue" and the edge types can have 'cite', 'write', and 'work at'. Second, graph structures (and features) can evolve over time. In citation network, the structure evolves when new papers are published and new citation relationships are established.
"Equal Contribution

---

Published as a conference paper at ICLR 2025
dite with shutland
Prek
Carbeen Datribution
Graph Generator
Genembed Graph
G
Milwayy Dis
Djr
perturbation
advrscrie Dilliin
Original Gruphh
5
Pertuttation
Equivalence classes in (1,3,5), (6,7) (4hv, 12ly Equivalance classes in g: [1.5,7), (3).. (4,6) (2)
Juily Dichiminttrr
12
Perturied Graph
pre tretrnngng
Figure 1: Left: A Toy Example of Attack and Protection on a Static Homogeneous Graph: Attacker with Structural Background Knowledge vs. Graph Perturbation based Protection. The second col- umn of the table shows the probability that an attacker can successfully identify the victim with background knowledge, and the third column shows the success probability with the same back- ground knowledge on the perturbed graph. Right: Overview of THEPUFF framework.
Overall, the heterogeneous and time-dependent structures and features of original graphs bring extra risk expose privacy by making nodes more unique, which creates unprecedented challenges for graph generative models to preserve privacy when generating utilizable large-scale graph data.
To bridge this gap, we propose Temporal Heterogeneous Graph Generator balancing Privacy, Utility, and Efficiency, named THEPUFF, In brief, THEPUFF relies on an adversarial learning manner, where THEPUFF tries to explore the distribution of anvacy-guaranteed graphs and utility- preserved graphs and then generates the synthetic graph that preserves both privacy and utility.
To protect privacy and defend attackers, the graph perturbation methods provide promising direc- tion (Zheleva & Getoor 2007 Liu & Terzi, 2008 Nguyen et al. 2015 Hoang et al. 2021] Fu et al.) 2022b). motivation case study is shown in Figure I where we demonstrate an attacker associated with the background knowledge of node signature structural query (Nguyen et al. (2015), i.e., nodes with the same structural information (c.g., node degree) form the victim candidates. The toy exam- ple in Figure shows that one simple edge perturbation can decrease this attacker's confidence. For example, the attacker aims to reveal the node identity of node #6 and knows its degree is 2, then in the original graph G, the attacker has 1/2 probability of identifying node #6 correctly. But if graph is perturbed into graph G, the attacker has 0 probability of identifying node #6, because node #6 is now transferred to another class for the new degree is 3.
Hence, in our THEPUFT, we first propose an error-bounded differential privacy perturbation algo- rithm for temporal heterogeneous graphs and an efficient and effective privacy-utility adversarial learning method for generating temporal heterogeneous graphs. To demonstrate the performance, we (1) propose 6 metrics for measuring the utility and privacy of temporal heterogeneous graphs to verify the generation, (2) conduct extensive attacking experiments on THEPUFF, (3) design various ablation studies, parameter analysis, and convergence visualization.
2 PRELIMINARY ANALYSIS
To make THEPUFF'S generation enable privacy-utility balancing and also fit the large-scale graph data, we analyze the current SOTA graph diffusion models (Zhang et al. 2023) and systemati- cally explain (1) why they are insufficient for this setting and (2) why Generative Adversarial Net- work (Goodfellow et al. 2014) (instanced by Transformers (Vaswani et al. 2017)) is the best fit.
Table 1: Diffusion based Graph Generation
Ditlusion type
Complexity Lx"
Complexity Bottleneck
DiGress Viignne al.
2023
Denoising Diffusion
link prediction for all possible edges
EDP-GNN Nuu dl
2020
Score Matching wi Langovia Dynamies
noise sampling for adjaccacy cutrics
Mpman(ke m)). .m is number of edges
link prediction for possible
EDGE et 2023
Denoising Diflusion.
edges between selected nndes
GmphGDDP Huang
2022
Strchastic Differential Equatiins
En
sampling for adjacency entries link prediction for all possible odges
DISCO
Xu st al. 2024g
Continous-time Markov Chain
Lad
Diffusion-based Graph Generation. With the help of diffusion techniques, diffusson graph gener- ation models learn the distribution of the adjacency matrix by diffusing into an empty or random graph. Despite their success in molecule generation and protein modeling (Wu al. 2022 Luo et al. 2022). all those methods share a high time complexity on the same scale of O due to leve- prediction noise generation, where L is diffusion steps and n is number of nodes. Pre- vious works are summarized in Table This poses an efficiency concern when dealing with large graphs. Importantly, the diffusion method has inherent advances in privacy protection due to the
2

---

Published as a conference paper at ICLR 2025
noise-adding process, our experiments show in Sec. 5.2 However, most methods do not provide the privacy guarantee, with the only exception of (Wei et al. 2023) that considers per-instance differ- ential privacy for vector data in discrete diffusion models. Therefore, choose transformer- GAN for large-scale and satpay--uiiity-avveeeeee graph generation, as stated below.
Transformer-based Generative Adversarial Network (GAN). With the development of trans- formers, researchers find that transformers can effectively serve as generators and discriminators of GAN in the context of image generation (Jiang et al. 2021). More recently, transformer-basee large language models have also been successfully utilized to be generators and discriminators for fake news detection (Wang al., 2024b). By representing the graph with extracted random walks, the transformer is also made available for graphs as well (Ling et al.] (022). Moreover, in graph generation, by generating random walks instead of directly generating an adjacency matrix, we can bypass edge-level sampling and prediction, which would lead to high computational costs.
3 NOTATION
We use bold lowercase letters for vectors (e.g., a), bold capital letters for matrices (e.g., A), and parenthesized superscripts to denote the time indices (e.g., (t). To be specific, in the graph ad- jacency matrix, (i, means the connection between node v, and node uy. Also, we denote the perturbation operation as i.e., A is the perturbed matrix of A, the perturbation operation is related to privacy protection and introduced in Sec. 4
Temporal Heterogeneous Graph Modeling, Formally, a heterogeneous graph means the number of types of objects (i.e., nodes) greater than or the number of types of links (i.e., edges) is greater than 1 (Sun et al. 201T). Moreover, the relationship between node type and edge type is deterministic, i.c., if two edges belong to the same type. then the two edges share the same starting node type as well as the ending node type (Sun & Han 2012). Hence, we use o to denote the node type and do not assign extra symbols for the edge type throughout the paper. For modeling a temporal heterogeneous graph 9, we denote each edge triplet ((1), o;); (1z, oy), where o is the node type of node vi, and is the timestamp that nodes v and Uj connects.
4 PROPOSED FRAMEWORK: THEPUFF
As shown in FigureD D our goal is to generate a synthetic graph G" that enjoys both privacy guarantee and high utility. To this end, first, we need privacy-preserving graph sample ς to provide the distribution of privacy-preserved structures. Second, we can then set the original graph as the utilizable sample, and develop the adversarial generative model to fit the distribution of & and g and
graph g"_ In this section, we first introduce the overall working flow of the proposed THEPUFF framework in Sec. [.T] Then, we introduce the details about how to perturb a temporal heterogeneous graph with privacy guaranteed in Sec. 4.2 Finally, we introduce how to design the privacy-utility adversarial learning setting to generate viable temporal heterogeneous graphs in Sec. 4.3
generate privacy-preservinn
4.1 OVERVIEW OF THEPUFF
The overview of THEPUFF is shown in Figure I The red arrows indicate the privacy-guaranter graph operation, where: a perturbation M is called to transform the original graph g into G. the de- tails are introduced in Sec. 4.2 Then, the blue and green arrows stand for privacy-utility adversarial learning: (1) Privacy Discriminator ppr is designed to guarantee the privacy of the generated graph, which aims to discriminate the generated graph G* and the perturbed graph G; (2) Utility Discrim- inator Dai is designed for preserving the graph utility, which aims discriminate the generated graph G* and the original graph G. To optimize this adversarial training,
We first pre-train Dou such that can distinguish an original graph G with any other graph patterns. Then, in the iterations of adversarial training, we alternatively (1) train Dpe with fixed the Gener- ator G, and (2) train Generator G with fixed ppp and fixed Dail-
After adversarial training, the generation ability of Generator G is improved, such that (1) Privacy Discriminator Dpr could not distinguish graph G" from 9 (i.e., privacy guaranteed), and (2) Util- ity Discriminator Dami could not distinguish graph G* from G (i.e., utility preserved). Upon this optimization, Generator G will output the
and urility-prseerved graph data.
3

---

Published as a conference paper at ICLR 2025
4.2
GRAPH STRUCTURE PERTURBATION BASED ON DIFFERENTIAL PRIVACY
Here, we seek to perturb the input graph & into 9. which (1) not only randomizes the graph structural distribution bounded by edge-level differential privacy (2) but also preserves the temporal hetero- geneous graph topology in terms of the degree distribution. The main advantage of preserving the topology information includes maintaining the discrimination differently for the discriminator in adversarial training to avoid the training collapse.
Before we introduce the detailed operation, need to first reformat the temporal heterogeneous graph by a time-respecting representation, i.e., representing all edges (regardless of edge types) that share the same timestamp into one snapshot. This time-respecting representation is more convenient for operation illustration and theoretical analysis and, meanwhile, will not influence follow-up ad- versarial learning. The graph is represented as g = { _ G(m)), where each snapshot has the adjacency matrix A (t) E R and n is the number of all appeared nodes in the lifetime of G such that A (4) allows dangling nodes.
Definition 4.1 (Adjacent Temporal Snapshots). At the timestamp t, two snapshots git) and git) are adjacent snapshots. if and only if g(t) and ((t) have the same set of nodes and differ in only one edge existence. For example, Eij exists in G(t) but not in Git), vice versa.
More precisely, based on the heterogeneous graph definition (Sun Han 2012), the two node types determine the edge type, then the above definition also applies to heterogeneous graphs.
Definition 4.2 (Adjacent Temporal Graphs). Two temporal graphs G and & are adjacent, if and only if they have the same time length from t = 1 to t = T) and only one pair of adjacent snapshots exists with the identical rest.
In the static setting, edge-level differential privacy (Blocki et al. 2012 Qin et al. 2017 Fu et al. 2023) describes that: given two adjacent graphs G and G (i.e., differ in one edge existence), a randomized mechanism M satisfies the edge-level differential privacy under a constant budget >> 0, if and only if
Pr[M(A) S] S (r) S) x ef
where A denotes the adjacency matrix of G and Á denotes the adjacency matrix of T.
The general idea of the above differential privacy is that two adjacent graphs (e.g., one edge differ- ence between two graphs) are indistinguishable through the perturbation algorithm M. Then, this perturbation algorithm MI satisfies the differential privacy (e.g., edge-level differential privacy). The intuition is that the randomness of M does not make the small divergence produce a considerably different distribution, such that the randomness of M is not the cause of the privacy leak. Likewise, the temporal edge-level differential privacy can be defined as follows.
Definition 4.3 (Temporal Edge-Level Differential Privacy). Given two adjacent temporal graphs G (G ..... G(()) and ğ ((2)) ...,,,)T),, temporal randomized mechanism M = (M(U), MM(2) ..... M((T) satisfies the temporal edge- differential privacy under the budget 8 > O, ifan only if
(T( (1) E 1 < Pr[M (A()) (A))) E SSt) x ee(o .and Σe ss, for t E (1, T}
Next, introduce proposed temporal randomized mechanišm M- (M(() MI M and give the proof under temporal edge-level differential privacy.
Perturbation Operations. For a snapshot g(t) at time t, M()) contains two independent perturbation operations, i.e., absent edge flip (! and existing edge flip M! proposed to be directly applied on adjacency matrix A (1) to obtain A (1), The absent edge flip is responsible for adding an absent edge, and the existing edge flip tries to delete an existing edge. These two perturbation operations are sequentially and interchangeably operated on the structure (i.e., adjacency matrix A (4)) of snapshot g(t) to get the perturbed structure (i.e., adjacency matrix A (t) for the new snapshot g(t), Following this way, we apply M(() (M M!()) each snapshot g(t) such that we can get the perturbed
temporal graph ف = ()))) g(a).... (. M and (!( are expressed below.
MTO = 1/e
Prob. of adding an absent edge,
(2)
Prob. of ignoring that absent edge,
4

---

Published as a conference paper at ICLR 2025
1/e-"0
M
Prob. of deleting an existing edge,
1/ee Prob. of ignoring that existing edge,
(3)
where e is Euler's number, and an absent edge means A (i.j) O. Then, given the privacy budget
(1) O, with the probability 1/cft", M will flip A (i, from 0 to 1; or M(( will do nothing
A (") (i with the probability 1- 1/E-= similarly on c(0) 0.
When sequentially executing M and M single snapshot graph G, they are executed on different edge sets (i.e., existing edge set and absent edge set) and do not overwrite each other. In practice, given the high sparsity of real-world graphs, iterating through non-existing edges could lead to high time complexity. Therefore, we apply M by first sampling a larger edge set (contains mostly non-existing edges and small portion of existing edges), then remove those existing edges, and sample the number of edges we need to append. In this way, the time complexity of graph perturbation is approximately the number of edges to be sampled. The general graph perturbation process is summarized in Alg. in Appendix A..)
Theorem 4.1. The proposed perturbation operation for temporal heterogeneous graphs an c- edge-level differential privacy algorithm, which is bounded by 2 max(e") in Appendix A.I)
each t. (Proof
Data-Driven e(0) Determination. According to our perturbation strategy, the perturbation process may result in privacy-preee preserving graph but a totally different topological distribution, thus hurting the utility of the original graph. Also, the dramatic change compared with the original graph is prone to collapse the adversarial training of the next stage.
Hence, we remedy the graph distortion caused by inserted and deleted edges with respect to the degree distribution. To achieve that, from the data-driven angle, we give the relation between e! and (4) for g(() based on the expectation of numbers of added edges and detected edges at each time t. For the notation clarity, the following equation expressed in the homogeneous setting but
can be easily extended to the heterogeneous graph by constraining node types.
(1
((n10)2 m)
(1) - In (n(1) - ml
(4)
where (4) denotes number of non-dangling nodes in G(),, (4) denotes number of edges in g()),
4.3 PRIVACY-UTILITY ADVERSARIAL GENERATION
To integrate the privacy of perturbed graph & and the utility of original graph G. propose privacy-utility adversarial learning method. The method consists of three modules: Privacy Discrim- inator pry. Utility Discriminator Dant and Generator G. During the adversarial training, we extract sampled subgraphs (e.g., via random walks) as model inputs. To be specific, at each time f, if node has connections, we can use heterogeneous random walk method (Ling et al., 2021) to get multiple
temporal .... ii J. for 02, .... }}},, where Uj denotes a node and o, denotes the node type of vy. Finally, we design an assembler for ag- gregating generated walks of generator G into a privacy-guaranteed and heterogeneous graph g"
I-node sequences. The i-th sequence is denoted as w = { 2/2 12)
Utility-preservingg Discriminator Dun- This discriminator is designed to distinguish generated graphs 9 and original graphs G, such that if the generator G can bypass discriminator Dumi. i.e., Dunl cannot distinguish the generated walks sampled from real graphs, then the generated graph is 'close enough' to the real graph and thus preserves the utility. On the other side, given a number of walks sampled from the real graph (Wi, W2, ..... Wi) ] and some generated walks (Wi, Wi,.., Wr). dis- criminator Duul should have confident bound for
A Σ Dan (W,))
Σ Duni(W
(5)
where we omit superscript for time in (!()) so that W; means the i-th walk in the sampled walks that consists of walks sampled from different nodes and different timestamps.
To achieve the above goal, we extend our discriminator Dui from bi-level self-attention (Zhou et al.) 2020) to the tri-level self-attention. On top of that, we first use model-agnostic projection (Hussein
5

---

Published as a conference paper at ICLR 2025
al. 2018) map node v/ into embedding vector hn Then, with sampled walk Wi() (2)
(1)
[1 .. u (t) J. for, 02, oJ tri-level self-attention mechanism ATN is
(1) AT (0) 18) (h W (eme) о ( W
(6)
Vdz
AT (Us. 1,) (h. Wrode) o (h, W
E
h
ddk
rE(L....TY
AT (or, (o, Woppe o (0, W type
(8)
vdz where o, is the one-hot embedding of node type oN. Matrices Whime, Wande, W are the time- level, node-level, and type-level query weight matrices; Wiee, W node-level, and type-level key weight matrices.
Q Whype are the time-level, k
To integrate attention from the three levels, we define the pooling operation of tri-level self-attention
Z = (softmax A time) + softmax [ mode) + softmax A (),e))V where Wv (v,:) = h,, and Wy is the value weight matrix.
Finally, the multi-hear attention layers are followed by a fully connected layer and softmax func- tion to output a score estimating the probability that the input walk is sampled from the real graph.
To train Dan for fulfilling the goal in Eq. 5 the objective function for optimizing Danl is minimize I(W)
La ((W), (W")) Σ
Dwn(W) - (us((W))
(10)
where (W} and {W*) are the mini-batches of sampled walks.
For realization, we choose to train Duii with randomly generated negative samples instead of gen- erated ones from generator G. whose operation actually allows us to detach Duii from the min-max manner (Goodfellow et al. al.||22111 2014)). In this way, Pun acts like a good scoring function for the penalty in the adversarial training. Although involving Donl with the generator might lead to higher utility, will increase computation complexity, the difficulty of model tuning, and the risk of training col- lapse. Our experiments corroborate that training Daul separately is sufficiently good for generation.
Privacy-guaranter Discriminator pry- This discriminator aims to discriminate generated graph g" and perturbed graph J. Again, if the discriminator Dpr cannot discriminate walks in the gener- ated graph and walks sampled from the perturbed graph, the privacy of the generated graph can be guaranteed. On the contrary, good Dpry should satisfy
(11)
where (W,, W2, W } are random walks sampled from ف. and (WT, Wy..., W3} are walks generated by generator G.
With similar intuition as Dan, Dpr shares the same neural architecture as Dun. The objective func- tion for training Dan is defined
[(W)
Lo (DW), (w")) = Σ (Mp) - prr (Vi:)
(12)
where Dar and generator G are trained alternatively.
Generator G. The generator aims to generate synthetic graphs that are both privacy-guaranted and preserved. We first introduce how generate temporal heterogeneous walks, and then introduce how the generated walks get constrained by the designed loss function to preserve both privacy and utility. In the next subsection, we introduce how the assembler aligns the generated walks into a temporal heterogeneous graph.
To begin with, we sample timestamped nodes with type based on the perturbed graph G. which could ensure higher privacy- prreecc-r than just sampling from the original graph G. In the following sec- tions, we omit the time superscript of oft)) for brevity, i.c., e; denotes a node with timestamp for the following sections. The walk generation relies the hidden states of recurrent neural architectures

---

Published as a conference paper at ICLR 2025
(e.g., LSTM (Hochreiter & Schmidhuber, [997)) generate length-L walk, i.e., the generator sequentially samples timestamped nodes with type based on the hidden state, which corresponding mechanism is described as follows. For sampling the 1-th node in walk generation, i.c., the I-th block in LSTM fo. for I E {1,..., LJ, we have (m,, h4) fo(mi-1,0-1)) 01-1), at = 9c((,), vi);
(ht), /* sample node type *
(13)
2t 9v (hr, 01), / sample timestamped node * where 2y is the l-th timestamped node, or is the node type, h4 and my are the hidden state and memory state of LSTM,, and a, is the input for the next recurrent block:
go is implemented with a fully connected layer and Gumbel Softmax, which aims to sample the node type based on the hidden state.
is implemented by a bag of fully connected layers, each corresponding to one node type; given the sampled node type from go. the corresponding fully connected layer generates an expected timestamped node embedding h". Given that, we can sample from timestamped node embeddings (t) in & based on the distance of embedding vectors, detailed distance function is stated in Eq. 14
= fa (o(choo((o))) + (h(.))))) fo and fo are both fully-connected layers, where byy is the timestamp of node et.
For initialization, we have ag 0, mg fo(2), where So is fully connected layer and is sampled from normal distribution z ~ ./ (O, 1). For Jv. a timestamped node by with type of is sampled by the highest probability based on the vector distance as
(14)
Σ v st. o(v)=o where o(v) means the node type of a node v.
e Ilke A8
Note that we do not enforce adjacent nodes to share the same timestamp to increase the diversity of the generated graph. In the next assembly step, edges connecting nodes from different timestamps will be added to both snapshots.
To generate the privacy-guaranie and cellitt-preserving graph, the walks generated by G try to bypass both Duii and pev. Therefore the loss function for training G is defined as
1(W"H H
Cs((W*)) =- Σ (Dai((W))) + (Pp))))))
(15)
The general training process is summarized in Alg. 4 in Appendix A.3
Clain 4.1. Since utility discriminator Dunt is pre-trained as shown in lines 3-6 of Alg. 2. and the generator G does not touch any real data as only listening to decisions of discriminators, our generative and adversarial game can be rewritten in the form of Eq. 2 and Eq. 3 of (Wi) et al. 2219). In (Wu et al.) [2019) generative adversarial networks have been proved to have an outstanding generalization property that can be interpreted constraining the input and output under differential privacy constraints.
Thus, we only need to make one extra assumption that the sampled temporal heterogeneous sub- graphs are independent and identically distributed, and then we can reach a generalization bound of our adversarial learning from the perspective of differential privacy (Wu al. 2019). which means the adversarial learning is also under differential privacy if the discriminator is well converged (i.e., stable). Note that this assumption is mild, since all subgraphs originate from whole larger graph, we can assume they are identically distributed; because we independently sample each subgraph, we can also assume they are independently distributed.
Assembler. Here, we extend the assembling mechanism in (Ling et al. 202 to assemble temporal heterogencous graph. First, we generate a sufficient number of walks from the generator. Then we construct scoring matrix S by counting the existing edges in the generated walks and find all meta-paths in the generated walks. To construct the generated graph, we start with sampling a node i1 Pr(v) according probability
Eveg(S (S(u,)))
Pr(m = u) Σ., EN Σnyes S(U,, mty)
(16)
where S(u, v) counts how many connections exist between node and in the generated walks.
7

---

Published as a conference paper at ICLR 2025
Then, we sample meta-path according to the meta-path's frequency. Following that meta-path O = (o1....o)), we sequentially sample the next node 1;41 (2 2 1) with node type 0,-1 according to probabilities proportional to the scoring matrix, where o(t) is the type of node
Pr(e++1 = =u) = [(((u) = 0 (S(; u))
(17)
= S(e,,))
Finally, we add all edges in the generated meta-path instances into the generated graph. Note that the timestamp of graphs naturally goes with the timestamp of nodes. The overall algorithms and time complexity can be found in Appendix and
5
EXPERIMENTS
5.1 EXPERIMENTAL SETTING
Datasets. To test the performance, we utilize 4 real-world publicly-available temporal heteroge- neous graph datasets from academic citation graphs (DBLP), online rating graphs (ML-100k, ML- 20M), and million-node online shopping graphs (Taobao).
Baselines. The comparison baselines include 4 categorical graph generative models. HGEN (Ling et al. 2021) is a heterogeneous graph generation algorithm. TagGen (Zhou et al. 2020 and TG- GAN (Zhang et al., 202I) are temporal graph generation algorithms. EDGE (Chen et al. 2023) designed for plain graph generation based diffusion models. DISCO (Xu et al. 2024b) is
discrete-state continuous-ting timusstttmmmeee diffusion model for plain graph generation. GraphMaker (Li et al. 2024a) is a diffusion model designed for attributed graph generation. Our THEPUFF stands for the temporal and heterogeneous graph generation.
Evaluation Metrics. We propose 6 metrics measuring 4 different aspects of temporal heterogeneous graph generation quality, including plain graph utility, temporal graph utility, heterogeneous graph utility, and overall privacy.
Plain Graph Utility: We propose Node Degree Distribution by Maximum Mean Discrepancy Dis- tance (i.e., MMD), named Degree in short, which is expressed as
1
Dist Dist(dori:: dgen)
T Σ MMD(d or gen).
(18)
where d (1) dgen are degrees of nodes in the original and generated graphs at time t, and MMD is averaged over all timestamps,
MMD x') = kerlæ, x) + ker(a', , x²) 2ker(x,
(19)
where the kernel function ker(.) is Σ}= -a, and k and ay constants. In the evalua- tion, we set & = 1 and a 4.
Temporal Graph Utility: We extend the Clustering Coefficient (i.e., Cluster), Size of the Largest Connected Component (i.e., LCC), and Triangle Count (i.c., TC) to the temporal setting, by calcu- lating those metrics at each timestamp and using MMD between the sequences of metrics over time of the original graph 9 and the generated graph G*. Taking LCC as an example,
(20)
Heterogeneous Graph Utility: For each timestamp, we count the number of length-2 and length-3 meta-path instances and get probability distribution meta-paths. Cross Entropy is applied for length-2 and length-3 respectively to measure distance, and the mean over time is taken to evaluate the overall performance. The corresponding metrics are named Meta-2 and Meta-3. Specifically, we only preserve the meta-paths that exist in the original graph, and all other meta-paths in the generated graph are combined into one category. For example, the MovieLens 100k dataset, we consider length-2 meta-path distributions over M2 l'user-occupationn" 'movie-genre', 'user- movie", 'none of above').
T Σ
exp(Pr (m))
Dist Dist(Prr(MM). Prg- (M))
Σ log
Pr(((m) (m))
(21)
T
Σ cxp (r (m))
t=1 MEM
where (ro(m) denotes the probability distribution of the meta-path m in the graph G, and is is collection of meta-path m.
'Dtaset statistics and more implementation details are summarized in Appendix A.5 http:///ghhha..cm///myuueht/ttth
Code is
8

---

Published as a conference paper at ICLR 2025
Overall Privacy: EO-Rate is defined the ratio of overlapped edges (i.e., in terms of existence and edge type) between the original graphs and the generated graph, which is used to analyze the privacy- property of the generation, and is averaged over time.
1 EO-Rate (g") = T
T
ledges(g(()) n edges(g*())) edgess(-(())
(22)
5.2 MAIN RESULTS
In Table 2 we report the average and standard deviation of the generated temporal heterogeneous graphs with respect to the proposed metrics. In general, our proposed THEPUFF framework generates very competitively utilizable temporal heterogeneous graphs compared with the state-of- the-art baselines, especially in the large-scale datasets, DBLP, MovieLens 20M (i.e., ML-20M), and Taobao datasets. Also, we observe that the plain graph generative model, EDGE (Chen et al. 2023) can achieve good performance on small-scale datasets, but it relies on diffusion model for the gen- eration process, which requires costly computational resources, especially high space complexity. We also discuss the convergence of adversarial training in Appendix AA.6 briefly analyze the time complexity in Appendix A.4 and show ablation studies in Appendix A.7
Table 2: Comprehensive Evaluation of Generated Temporal Heterogeneous Graphs, where e denotes scientific notation (e.g., le 2 = 0.01), purple, teal, and cyan denote the first, second, and third place
Thiliy
Privey
Methoc's
Clustrr (1)
(C()))
(OC
Degiee (4)
Mcte-2(1)
Mote-3 (U)
EO-Rat
HGRN
5.87l (ey
1.00
1.305 1.399
1,289 4toe-11
3.903 (8du03ke11)
TagGen
3.021e
1.000ga0-)
1.570
1.50 (45-0009
1.310
2:238r (a3u53ke-t
ML ML-100K
TG-GAN
4.987
1.000
2.143
2.097
1.527
1.308 (2
2.00t - 7ateniy
EDGE
3.960
10000
2.556 1e6
1.069
4774
1.313
5.4886 (4
DISCO
3,807c
1.00
1100
3.632
138--1
L.13 1313 1653
J. 1886e (azberi)
GruphMaler
1.084
1.00
1.385
1.302 2 sudu-t
-2 4.380 1032002e
THiPU
2,536e
L
3.547
2530-1)
1.31 1,315 1009
2.947e pas dizemily
IIGEN
12200,
a.000.0mm
0.012 1.00
3.0640 Lubaaee
Tagtien
1.574r
1.000
0.000:200
3.359
0.919 2 230e
1.164 E4 (o)
DBLP
TG-GAA
6.NNI
1000
0.000
1.49iic
1.79k 134
0.01 as on
2,000 paruasse
EDGE
Generates Empty Graph
DISCO
00M
GraphMaker
00M
THcPUAr
0.000
1,192222
2,400
1.205,y5.7231--
1889
6 6.908e,
IIGEN
2:217 (auue-)
2.552e
1.52 (09
4.268e, ussassend
TagGien
7.05 (200)
1.00
0.000:2000
1,263 (SDA))
1,29
5. 5.105e (sbo))
20M
TG-GAN
2.15 (221540-19
1.006 jaamm
2.216
3.481
1825 a6-
1,267 a1
2.80 (82095e-1)
EDGB
00M
DISCO
OOOMM -..
GraphMaker
00M
THEPPUr
0.000
0.000
5. 1.168, 200)
5.506
1 1081646353
1:200
2:305 Lasseity
IIGEN
0.000
1,1922
0.000..amm
6.13Fe
1253
0.613
1.12 pa2le sasterry
TagGien
(.000
1.19% 1g
0.000
5.
1.50
0.013
2.022 -3
(alassent)
Tuobuo
TG-GAN
(000)
1,192
(2192 (2000)
4,982 (1n04))
7.204
1.08 (ee-
5.021 (a2asee-
EDGE
-0OOO---- -.-
DISCO
GraphMaker
00M
THEPUEF
a.000
L1922 (2)
5:637 1a0
7.545
(.613
4.367e (aaa
5.3 ATTACKER EXPERIMENT
To further evaluate the privacy of our generated graphs, we perform an attack experiment the DBLP dataset in addition to the EO-Rate metric. We consider the same attack scenario as the toy example in Figure. [ i.e., at time f, nodes sharing the same degree with the target victim are possible candidates. Mathematically, the successful attack probability (i.c., for accurately identifying the target) can be modeled as follows. At a certain timestamp t, the attack probability of node i is
(t)
gen
p;
(23)
Ensor 1 [v]
(t)
gen
where is indicator function, dyen; dori are node degree functions of the generated graph and original graph.
Table 3: Graph Attack on DBLP
Finally, we measure the model's privacy performance by the mean of 2¹a)) over timestamps and all nodes. We compare the attack probabilities of graphs generated by THEPUFF, HGEN,
Baseline Orignal HIGEN
Suivessool Attact Probuctiiy (4)
0.033
0.009
DPOGAN
0.008
THaPUPROas)
0.006 33
9

---

Published as a conference paper at ICLR 2025
and a state-of-the-ar privevcntill-pivacyy-- baasacc--baedddde graph generation method, DPGGAN (Yang et al. 2020), and get the following results; we also calculate the successful attack probability on the origi- nal graph for reference. The results shown in Table We can observe that TTHEPUrF-generatte graphs give attackers the lowest confidence of a successful attack, and THEPUFF is also the most stable one with the smallest standard deviation (i.e. numbers inside the parenthesis in Table 3)
5.4 PARAMETER ANALYSIS
We analyze the model performance with different choices of 8+ and 6- on MovieLens 100K. THEPUFF is trained with 6- {1,2, 4, 5, 6, 7, 7,8) and 8+ is estimated by Eq. 4 Also. the pair of E- and E+ is shared across all timestamps (1.2..... T). We draw the curve of EO-Rate with respect to c- in Figure 2 In general, the smaller budget can preserve more privacy, which aligns with the theoretical differential pri- vacy. EO-Rate increases with e- when e is larger than 3, because the number of perturbed edges decreases when e- in- creases, then the perturbed graph will be very close to the real graph. In this way, the synthetic graph will be closer to the real graph too, and its edges will be more likely to overlap with the edges in the real graph. is interesting that the EO-Rate will also increase when the number of perturbed edges increases beyond a certain boundary (c_ less than 3 in case). This is because the more random the perturbed graph is, the harder the process will be. In this case, the utility-preserving discriminator will dominate over the privacy- guaranteed discriminator and generate a synthetic graph more like a real graph. The full results of parameter analysis in terms of all metrics are shown in Table
83275
6800
63000
2013
63122
Figure 2: EO-Rate w.r. Budget
Discriminator's learning
Table 4: Parameter Study Results on ML01 where denotes the scientific notation.
Caiit
Privacy
Chaster (1)
TC
ICC
Degne (
Meta22 (L)
Meta-3
FO-Rate
T.508e Lag soeuntt
2.00
0.56)
1.13 ane-+::
2855
Lg 958
1.913r secce
1.532
1,31 m
1.81 24
5,370 5,377le (y
2.000
0,200 assentt
0.077
L.78
14
1.31 21 40m-1:
1.200 1.5400 (44200001)
2. 2,50k sote-1y
2.000
L.82
1.31 mm
1.367 19
3.20Me to
2.000
L.08
1. ema-a:
10000
5,10de ma
2.000
0.557 0.2t0-
6660
1.13 2004--1
1.575
2,00
1,31 (a00
moce-:
1.872 (8145-00
5. 3,500e,
1. 1..00
0.
(.68
1.318 mm
20000
RELATED WORK
Graph generative models have been extensively studied recently. Recently, a generative model called EDGE (Chen et al. 2023) is proposed, which develops a diffusion based model that first diffuses graphs to empty graphs by the step-by-step edge removal process. By modeling that trajectory with the denoising model, it reversely decomposes the denoising model and generates edges. These mod- els are only designed for static and plain graphs. HGEN (Ling et al. (222]) tackles the heterogeneous graph generation problem with heterogeneous trained to discriminate synthetic heterogeneous walks and real walks. TagGen (Zhou et al. 2020) generates synthetic temporal walks by doing 'addition' and 'deletion' to sampled walks. Generated walks are scored to assemble a synthetic temporal graph with discrete timestamps. TG-GAN (Zhang et al. 2021) uses the temporal random walk-based generator-discriiinaat continuous-time temporal graph generation problem. Most graph generative models ignore the fact that complex heterogeneous and temporal information may increase the exposure of the private in- formation of nodes (c.g., identities of social network users) (Jiang et al.] 2023 Fu et al., 2023 Li
GAN framework, where a discriminator
framework to solve the
al. 2015 Liu al. 2021), ), and this challenge largely remains open. To the best of our knowledge, THEPUFF is first to deal with temporal heterogeneous graph generation with guaranteed privacy.
7 CONCLUSION
In THEPUFF, a differential privacy algorithm is first proposed to perturb the input graph. Then, privacy-utility adversarial learning setting is developed to generate both privacy-guaranter and heterogeneous temporal graphs. By extensive experiments, we demonstrate the effectiveness of TFFPUFF, especially in large-scale datasets.
10

---

Published as a conference paper at ICLR 2025
ETHIC STATEMENT
To the best of the authors' knowledge, this research is not related any ethical issues; all the datasets used in this research are publicly available, and the necessary references and links are provided along with datasets in the main body of the paper.
ACKNOWLEDGMENTS
This work is supported by NSF (2117902, 2324770), and DHS (17STQQAC0001-0074
TSSQAAC0001-08-000 The content of the information in this document does not necessarily re- flect the position the policy of the Govemment, and no official endorsement should be inferred. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.
REFERENCES
Yikun Ban, Jiaru Zou, Zihao Li, Yunzhe Qi, Dongqi Fu, Jian Kang, Hanghang Tong, and Jingrui He. Pagerank bandits for link prediction. In NeurIPS, 2024.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The jonsooonnnnnndesstauus transform itself preserves differential privacy. In FOCS, 2012.
Xiaohui Chen, Jiaxing He, Xu Han, and Liping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. In ICML, 2023.
Matthias Fey, Weihua Hu, Kexin Huang, Jan Eric Lenssen, Rishabh Ranjan, Joshua Robinson, Rex Ying, Jiaxuan You, and Jure Leskovec. Position: Relational deep learning graph rep- resentation learning on relational databases. In Forty-first International Conference on Ma- chine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL net. forumorrmmmmmm (at.rrummmddBBmmmmimmamm
pettps:/opperress
Donggi Fu, Liri Fang, Ross Maciejewski, Vetle I. Torvik, and Jingrui He. Meta-learned metrics over multi-evolution temporal graphs. KDD, 2022a.
Dongqi Fu, Jingrui He, Hanghang Tong, and Ross Maciejewski. Privacy-preserving graph analytics: Secure generation and federated learning. CoRR, 2022b.
Dongqi Fu, Wenxuan Bao, Ross Maciejewski, Hanghang Tong, and Jingrui He. graph machine learning from data to computation: survey. SIGKDD Explor, 2023.
lan J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial networks. CoRR, 2014.
Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. 2015.
Anh-Tu Hoang, Barbara Carminati, and Elena Ferrari. Privacy-presen sequential publishing of knowledge graphs. In ICDE, 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Comput., 1997.
Han Huang, Leilei Sun, Bowen Du, Yanjie Fu, and Weifeng Lv. Graphgdp: Generative diffusion processes for permutation invariant graph generation. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 201-210) IEEE, 2022.
Rana Hussein, Dingqi Yang, and Philippe Cudré- Mauroux. Are meta-paths necessary?: Revisiting heterogeneous graph embeddings. In CIKM, 2018.
Honglu Jiang, Jian Pei, Dongxiao Yu, Jiguo Yu, Bei Gong, and Xiuzhen Cheng. Applications of differential privacy in social network analysis: A survey. IEEE Trans. Knowl. Data Eng., 2023.
Yifan Jiang, Shiyu Chang, and Zhangyang Wang. Transgan: Two pure transformers can make one strong gan, and that can scale up. Advances in Neural Information Processing Systems, 34: 14745-14758, 2021.
11

---

Published as a conference paper at ICLR 2025
Mufei Li, Elconora Kreacic, Vamsi K. Potluru, and Pan Li. Graphmaker: Can diffusion models generate large attributed graphs? Transactions on Machine Learning Research, 2024a. ISSN 2835-8856.
www..netee/oomid-deeeeeeee GGMKA
Yan Li, Yingjiu Li, Qiang Yan, and Robert Deng. Privacy leakage analysis in online social networks. Computers & Security, 49:239-254, 2015.
Zihao Li, Dongqi Fu, and Jingrui He. Everything evolves in personalized pagerank. In WwW, 2023.
Zihao Li, Dongqi Fu, Mengting Ai, and Jingrui He. Apex?: Adaptive and extreme summarization for personalized knowledge graphs. CoRR, 2024b.
Xiao Lin, Zhining Liu, Dongqi Fu, Ruizhong Qiu, and Hanghang Tong. Backtime: Backdoor attacks on multivariate time series forecasting. In NeurIPS, 2024.
Chen Ling, Carl Yang, and Liang Zhao. Deep generation of heterogeneous networks. In ICDM, 2021.
Bo Liu, Ming Ding, Sina Shaham, Wenny Rahayu, Farhad Farokhi, and Zihuai Lin. When machine learning meets privacy: A survey and outlook. ACM Computing Surveys (CSUR), 54(2):1-36, 2021.
Kun Liu and Evimaria Terzi. Towards identity anonymization on graphs. In SIGMOD, 2008
Shitong Luo, Yufeng Su, Xingang Peng, Sheng Wang. Jian Peng, and Jianzhu Ma. Antigen-specife antibody design and optimization with diffusion- based generative models for protein structures. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp.
Curran Associates, Inc.,
2022. URL
hwwr://prrooedddnng......r.....s www.ips. ct/ccc//eaaa cttpspprcppppppppeeepeeeeeee httpr//g.....oooo.ooo//////////r httaaaperrflleeseppe/////00
file htte///fadaaaaaa11f1fffeeeeeeeee httpa//e1111111111ee222620220330 -annrr----pappe-CCCfeeeeeeeeee f
Hiep H. Nguyen, Abdessamad Imine, and Michaël Rusinowitch. Anonymizing social graphs via uncertainty semanties. In CCS, 2015.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. In International Con- ference on Artificial Intelligence and Statistics, pp. 4474-4484. PMLR, 2020.
Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1920-1931, 2023.
Zhan Qin, Ting Yu, Yin Yang, Issa Khalil, Xiaokui Xiao, and Kui Ren. Generating synthetic decen- tralized social graphs with local differential privacy. In CCS, 2017.
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan Eric Lenssen, Yiwen Yuan, Zecheng Zhang. Xinwei He, and Jure Leskovec. Relbench: A benchmark for deep learning on relational databases. CoRR, abs/2407 20060, 2024. doi:
48550/ARXIV.2444 20060.. BtLLhttps:/// //doi org/10 48550 arxiv. 2407 20060
Chuan Shi, Yitong Li, Jiawei Zhang, Yizhou Sun, and Philip S. Yu. A survey of heterogencous information network analysis. IEEE Trans. Knowl. Data Eng., 2017.
Yizhou Sun and Jiawei Han. Mining heterogeneous information networks: structural analysis approach. SIGKDD Explor., 2012.
Yizhou Sun, Jiawei Han, Xifeng Yan, Philip S. Yu, and Tianyi Wu. Pathsim: Meta path-based top-k similarity search in heterogeneous information networks. Proc. VLDB Endow, 2011.
Jie Tang, Jing Zhang. Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: Extraction and mining of academic social networks. In KDD, 2008
Katherine Tieu, Donggi Fu, Yada Zhu, Hendrik Hamann, and Jingrui He. Temporal graph neural In NewrlPS, 2024.
tangent kernel with
12

---

Published as a conference paper at ICLR 2025
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 1998-6008 2017. URL http:ss///prrccceingg..ooo neuripps.
Abstract. Abstraaac html
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 140444249.1,34,, 2022.
Limei Wang, Kaveh Hassani, Si Zhang, Dongqi Fu, Baichuan Yuan, Weilin Cong, Zhigang Hua, Hao Wu, Ning Yao, and Bo Long. Learning graph quantized tokenizers for transformers. CoRR, 2024a.
Yifeng Wang, Zhouhong Gu, Siwei Zhang, Suhang Zheng, Tao Wang, Tianyu Li, Hongwei Feng, and Yanghua Xiao. Llm-gan: Construct generative adversarial network through large language models for explainable fake news detection. arXiv preprint arXiv:2409.01777 2024b.
Rongzhe Wei, Eleonora Kreačić, Haoyu Wang, Haoteng Yin, Eli Chien, Vamsi K Potluru, and Pan Li. On the inherent privacy properties of discrete denoising diffusion models. arXiv preprint arXiv:2310.15524. 2023.
Bingzhe Wu, Shiwan Zhao, Chaochao Chen, Haoyang Xu, Li Wang, Xiaolu Zhang, Guangyu Sun, and Jun Zhou Generalization in generative adversarial networks: A novel perspective from pri- vacy protection. In NeurlPS, 2019.
Lemeng Wu, Chengyue Gong, Xingehao Liu, Mao Ye, and Qiang Liu. Diffusion-based molecule generation with informative prior bridges. Advances in Neural Information Processing Systems, 35:36533-36555 -6155333-665... 2022.
Zhe Xu, Kaveh Hassani, Si Zhang, Hanqing Zeng, Michihiro Yasunaga, Limei Wang, Dongqi Fu, Ning Yao, Bo Long, and Hanghang Tong. Language models are graph learners. CoRR, 2024a.
Zhe Xu, Ruizhong Qiu, Yuzhong Chen, Huiyuan Chen, Xiran Fan, Menghai Pan, Zhichen Zeng, Mahashweta Das, and Hanghang Tong. Discrete-state continuous-time diffusion for graph gener- ation. arXiv preprint arXivv2405.10 1416, 2024b.
Carl Yang, Haonan Wang, Ke Zhang, Liang Chen, and Lichao Sun. Secure deep graph generation with link differential privacy. arXiv preprint wiXiv:2055.0045: 2020.
Carl J. Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. Heterogeneous network repre- sentation learning: A unified framework with survey and benchmark. 2022.
Qi Yu, Zhichen Zeng, Yuchen Yan, Lei Ying, R Srikant, and Hanghang Tong. Joint optimal transport and embedding for network alignment. In WWW, 2025.
Zhichen Zeng, Si Zhang, Yinglong Xia, and Hanghang Tong. Parrot: Position-aware regularized optimal transport for network alignment. In Proceedings of the ACM Web Conference 2023, pp- 372-382, 2023.
Liming Zhang, Liang Zhao, Shan Qin, Dieter Pfoser, and Chen Ling. TG-GAN: continuous time temporal graph deep generative models with time-validity constraints. In WWW, 2021.
Mengchun Zhang, Maryam Qamar, Taegoo Kang. Yuna Jung, Chenshuang Zhang, Sung-Ho Ho Bae, and Chaoning Zhang. A survey graph diffusion models: Generative Al in science for molecule, protein and material. CoRR, abs/2304.01563 2023. doi: 1144550/ARX1122330005555 URL
Pattps://dos www.oo..........o..o.ooooo...... 18550/0axXtt 2304. 01565
Elena Zheleva and Lise Getoor. Preserving the privacy sensitive relationships in graph data. In PinKDD, 2007.
13

---

Published as a conference paper at ICLR 2025
Lecheng Zheng, Dongqi Fu, Ross Maciejewski, and Jingrui He. Drgnn: Deep residual graph neural network with contrastive learning. Transactions on Machine Learning Research, 2024.
Bin Zhou and Jian Pei. Preserving privacy in social networks against neighborhood attacks. In ICDE, 2008.
Dawei Zhou, Lecheng Zheng, Jiawei Han, and Jingrui He. A data-driven graph generative model for temporal interaction networks. In KDD, 2020.
Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. Learning tree-based deep model for recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 1079 1088, 2018.
14

---

Published as a conference paper at ICLR 2025
A
APPENDIX
The supplementary material contains the following information:
Appendix
A.
A.2
Proof of Theorem
Appendix
A.3
Pseudo codes.
Appendix
A.
Time complexity analysis.
Appendix
A.5
Datasets and implementation details.
Appendix
A.
Convergence of THEPUFF training.
Appendix
A.7
Ablation study.
Appendix
A.
Attack Experiments on all Datasets
Appendix
A.9
Sype-Distinguishable Attack Experiments on all Datasets
Appendix Pseudo-code of Discriminators in THEPUFF
Appendix
A. 10
Pseudo-code of Assembler in THEPUFF
A.1 PROOF OF THEOREM 4.1
Proof sketch. For the proposed perturbation operation, first prove that edge-level differential privacy is guaranteed for each timestamp, and we then prove that temporal edge-level differential privacy is guaranteed for the entire temporal graph. Denoting the perturbed adjacency matrix as M( (A (,), the probability of the perturbed matrix equals certain matrix ((t) is
Pr[M(() (A(1) (1) = S = II Pr [ (A (9) = (
(24)
where the M includes two randomizations M. and (
Then, given two snapshots (+) and ( the ratio of the probability of perturbing on A and (() and outputting the same output can be expressed as follows,
Pr M (A (1) 8h"]
Pr " (A(t,))) S(i
Pr ( (A(i))) 56. 11
s.t. for i.j (1,2. =
II
Pr M (A S()]
Pr " (A(t,))) S(i. m..y Pr Pr S(+.))
(25)
which general formula over all possible edges. be specific, given two adjacent snapshots g(t) and g(t), we can denote the difference as an absent edge (u, v). e.g., g does not have but
(())) does. Then, according to Eq. 25 the ratio I' of the marginal probability of outputting the same output in the equation below, where the first term represents that M successfully flips A(u, v)(0)
and M can do nothing the flipped A(u, v)()) based on our design.
Pr e) = 0 Pr|A(u, v)(0)
Pr(A(u, 0) +00 Pr(A(e,)))) 0
r
Pr o)) = =1 Pr[A(u, v)(0 1+11
Pr(A(u, 2) Pr[A(u, oj = =1
_/
1/
1/
(26)
Moreover, we have analyzed the differential privacy scenario that the later mechanism can overwrite (e.g., MI flips the edge that M has just flipped) in the next section, and the bound is looser than in Eq. 26 (i.e., larger than + - which suggests that forbidding the overwrite is a safer way to protect privacy.
Then, we can derive Theorem 4.1 based on Eq. 26
A.2 ADDITIONAL PROOF FOR THEOREM 4.1
Here, extend to analyze the scenario when the later perturbation (e.g., (() can overwrite the former perturbation (e.g., (t) and derive the corresponding differential privacy bound.
Similarly, we start from Eq. 25
(() (A(1) S(0)
for i, E (1,2.....
MM( (A(1)) = S(0
(27)
P (A(i.))) S(i,))
PriM!!)) (A(i.)) = S(i
II
II
F4. Pr (A(i,))) S(i,j)
Pr(M (r(M)(((((,)))) = =S(i,j)
15

---

Published as a conference paper at ICLR 2025
which is general formula over all possible edges. To be specific, given two adjacent snapshots G(t) and g(o), denote the difference does not have it but ((0) does. Then, according to Alg. and Eq. 25 the marginal probability P of outputting the same output is as follows.
absent edge (u, v) without loss of generality, e.g., g
= = r Pr[A(u, 0) = + Pr[A(u, v)
Pr[A(u, 0)(() = 1 Pr(A Pr(A(u, v)(0) = =1
=1
Mf
Pr[A(u, v1( =0 1 Pr[A(u, v) = 0]
+
Pr(A(u, =1 Pr[A(u, u) = ()(0))
M
Pr[A(u, D)(1) = 0)
Pr[A(u, () 0 -
Pr[A(u, 7)()) 1]
Pr Pr[A(u, v)(0)
M(
M(
1/e
1/ee
1/ee
1/
1/ee
X
+
1 1 1/6--
_/
1/e
2
- + c (1)
2
where the first term represents that M successfully flips and M ignores, the second term means that MI successfully flips and (1))) also flips and overwrites, and the third terms means that M(
ignores and MD flips.
A.3
PSEUDO CODES
Algorithm Graph Perturbation based on Differential Privacy
Input:
graph snapshot ((), privacy budgets e- and
Output:
graph snapshot (())
1: for certain edge type do
/* Apply M( */
2: for edge in non-existing do
3: Randomly generate a probability a
4: if 1/ee* then
5: Add edge to set append set
6: end if
7: end for
7* Apply (*
8: for edge in existing_set do
9: Randomly generate a probability a
a 1/E then
11: Add edge to set del.set
end if
13: end for
end for
15: residual.set seL.diff(existing.eet del_set)
16: g(+) = set. set uniionrrrrrii sppend_set)
16

---

Published as a conference paper at ICLR 2025
Algorithm 2 Privacy-Utility Adversarial Training
Input:
sampled walks (W} from G, sampled walks (W from G. randomly sampled walks (W²)
Output:
synthetic walks generator G
1: while until not converge do
2: Initialize Dunl D pev. C
3: for batches in (W), ]. B' in (W") do
4: Calculate LB.. (1,, B3) in Eq. 10
5: Update Duil
6: end for
7:
end while
8:
while until not converge do
9:
for batches B in (W} do
10:
Initialize noise 2 = {2] (0, 1)}
11:
G()
12:
Calculate LE (B, B*) in Eq.
13:
Update Dar
14:
Calculate Lo (B*) in Eq. 12
Update G
16: end for
end while
A.4 THEORETICAL AND EMPIRICAL. COMPLEXITY ANALYSIS
Theoretical Time Complexity Analysis For the overall training process, the time complexity of THEPUFF mostly depends on the number of walks sampled (which typically can be approximately OEE) or V(k)V)), ), k is a constant indicating the number of walks sampled starting from one node, depending on graph sparsity). For each training iteration, the time complexity for forward will be mainly composed of three parts: LSTM with / (i.e,, length of walks, typically less than 5) steps, and two tri-level attention networks with time complexity ((12 + do)), where dl is the dimension of node embedding and d, is the length of one-hot embedding of the node type. Similarly, the time complexity for graph generation mostly depends on the number of walks to be generated.
Compared with diffusion- generation methods, our training and generation process both follow a node-by-node sampling procedure, whereas reverse process in current diffusion graph generation models follow edge-by-edge sampling procedure. Therefore, our work has a complexity linear to [V| while diffusion graph generation models have complexities quadratic to V (Table. D. Al- though probability prediction module (tri-level attention layer) might have higher complexity compared to diffusion models with simpler architecture (e.g.. MPNN), we consider that hyper- parameters (1, d, d.) much smaller than [V,, (empirically, they actually do), method is still more efficient compared with diffusion- methods, especially when [V] reaches thousands to even millions.
Empirical Running Time Comparison To give a better illustration from the practical viewpoint, the overall training process of MI.-10KK given sampled walks (sampling 5 walks of length 5 starting from each node) and initialized nodes' temporal embeddings takes around 350 seconds; the gener- ation process by generating 300,000 walks (which should be much larger than the number of walks needed) takes around 250 seconds. Also note that ML-100k is a cleaned dense dataset, whereas large graphs (which often sparser) mostly do not require sampling many as 5 walks from each node.
More importantly, report the total running time of all basclines generating the temporal hetero- geneous graphs for ML-1000 dataset in Table 2 below, given diffusion methods are prone to OOM on larger datasets.
17

---

Published as a conference paper at ICLR 2025
Table 5: Running Time Comparison on ML-100k Dataset.
Methods
Running Time
HGEN
1120s
TagGen
2730s
TG-GAN
4731s
EDGE
7hrs
DISCO
3500s
GraphMaker
4hrs
THEPUFF (ours)
350s
Empirical GPU Storage Comparison Here, also report the GPU analysis for all baselines the ML-100k dataset. For DISCO baseline, its actual GPU usage can be 54GB, verified on a Tesla A100 80 GB machine.
Table GPU Consumption on MI.-100k Dataset.
Methods
GPU Usage
HGEN
~ 610MB
TagGen
23GB
TG-GAN
940MB
EDGE
12GB
DISCO
32GB
GraphMaker
1100MB
THEPUFF (ours)
712MB
A.5 DATASETS AND IMPLEMENTATION DETAILS
Table 7: Temporal Heterogeneous Graph Datasets
Type
#Nodes
#Node Types
#Edgees
#Edge Types
Time
MovicLens 100k Harper & Konstan 2015
Rating 2,644
102,625
months
DBLP Lang DBLg et ad. 2008
Citation
17,876
$1.137
10 years
MovieLeus Tlappe Konsian
Rating
165,790
20.027.541
21 years
Tachao 7hu al. 2018
E.Commerce
1,009,827
3
2,932,288
2
10 hours
Datasets. Detailed dataset statistics summarized in Table For the DBLP dataset, we retrieve the subgraph by constraining the paper venue as KDD. Moviel.ens-10007 DBLI MovieLens- 20M and Taobad are publicly available.
MovieLens- 100k, node types are user, movie, genre, and occupation; edge types are user- movie, movie-genre, and occrpacnnnniion.
DBLP, node types are paper, author, field of study, and affiliation; edge types are author- paper-paper, outhor-afiliation, and paper-field of study.
In MovieLens-20M,, node types are user, movie, genre; edge types are user-movie and movie- genre.
In Taobao, node types are user, item, and category; edge types are user-item and item-category.
Baselines. Non-temporal baselines (i.e., HGEN and EDGE) are run in snapshot-to-snapshol way. E.g., for dataset = considered as the generated temporal heterogeneous graph.
((T) and non-temporal baseline F(-), G* (F.,
For non-heterogeneous baselines (i.e., TagGen, TG-GAN, and EDGE), node type information is ignored when running baselines. When evaluating performances, node types are considered the same as in the original graph.
httpp::/wwee
18

---

Published as a conference paper at ICLR 2025
Hyperparameters. Table implemented with the following hyperparameters:
___ 8 for all datasets, c is decided by Eq.
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 Le for the generator and 1e for discriminators:
SGD optimizer used for discriminators, while RMSprop optimizer is used for the gener- ator;
JUST (Hussein et al. 2018) 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.
Hyperparamters for HGEN, TagGen and TG-GAN are set as the default or recommended value in their public code repositories. Hyperparameters for EDGE that batch size is set to due to memory limitation.
recommended values except
Machine Configuration. All experiments performed Linux platform with Intel(R) Xeon(R) Gold 6240R CPU and Tesla V100 SXM2 32GB GPU.
Reproducibility. The code will be published on the authors' websites upon the paper's publication.
A.6 CONVERGENCE OF THEPUFF TRAINING
In this section, discuss the convergence of the adversarial training part of THEPUFF (lines 8 17 in Alg. (4). In practice, our generator G updated every 2-5 iterations while privacy discriminator Drro updated every iteration. An illustration of the training process on the largest dataset (Taobao) is attached in Figure In the training process, we first see a decrease of LTPrO to the lowest point, and then increase of LD,.. G gradually starting to outperform Dpre.
3.00
-0.50
33 -0.75
-125
D. pit Lakk
Rutil bode
11.0
Bumn
200
600
800
1000
Figure 3: Training curve of generatorldiseriiinnatoss on Taobao
A.7 ABLATION STUDY
Here, we also conduct an ablation study on the dataset Moviel.ens 100k and Moviel.ens 20M. The results are shown in Table 8 where we trained our framework without either the quility-preserving discriminator (Dont) or the grivacy-guarantes discriminator (Der)). It can be observed that with only the generator and urility-rreeeriigg discriminator (i.e., w/o ppre), our THEPUFF can also generate the comparable privacy-guant privacy-uarratted synthetic graph, which proves our design Eq. [ that the nodes are sampled from the perturbed graph G. thereby precccypeeeerved information obtained from differential privacy perturbation M is transferred to the generator G.
19

---

Published as a conference paper at ICLR 2025
Table Ablation Study Experiment Results.
Datasets
Methods
Unily
Privncy
Claster (1)
TCC (J)
LCC
Degree (1)
Meta-2 (J)
Meta:3 (Q)
EO-Rate (1)
MLL-100
Dans!
(0.00))
0.280 asien)
BAWD Sa
1000 90000n
1.51 coauna))
2.319: aozett) 2,068 2
Dgro
0.216 (1.00)))
0.073, "
1,313 s00en1)
roa--h)
wio Dan
0.874 o0zent)
0.500 aster))
1.401 10tee?)
1
wdo Daro
0.0, 1.00
0.0
0.512
0.
1.55 3.900-
1.26% 0000-1)
1.0
A.8
ATTACK EXPERIMENT ON ALL DATASETS
Here, we follow the attacker model expressed in Eq 23 and test the privacy protection effective- ness baseline methods across all datasets. The results are shown below, where we can see the proposed THEPUFF method can reduce the successful attack probability to the largest extent.
Table 9: Attack Experiment on All Datasets.
Successful Áttack Probability (%) (L)
Baseline Dataset
ML-I00K
DBLP
ML-20M
Taobao
Original HGEN
4.192
0.093
0,352
0.006
0.037
0.009
0.007 (0.005)
1.3c 1.3e (2.0e-7)
DPGGAN
0.037 4)
0.008 (1.3e 4)
OOM
OOM
THEPUIF(Ours)
0.021(0.0077
0.006 (9e 6)
7.5e (6.0e
7.9e 5 (6.2e
(..20
A.9 ATTACKING USSERS/AUTHOR ON ALL DATASETS
Here, we design a more complicated attacker model by extending the attacker in Eq 23 as follows. For specific node type of attacker's interest,
otherwise d
d [1]
(e) and Ogen
(28)
Eveg- 11 Hidfon [v]== afo (owwi (s] d [=]=
o
(t) where the added Ogen [i] means the node type of node at time on the generated graph.
Therefore, we can now test how the baselines protect the privacy of certain types of entities, e.g., internet users in ML-100K dataset, ML-20M dataset, Taobao datasets, and authors in DBLP datasets.
The results are shown in the table below, where our proposed THEPUFF also achieves the best performance across all datasets.
Table 10: Attacking Users/Authors on All Datasets.
Successful Attack Probability (%) (L)
Baseline Dataset
100k
DBLP
ML-20M
Taobao
Original HGEN
11.73
0.113
0.427
0.021
(0.008)0008)
0.013
9.3e (7.2c 9)
(1.4e 5. 5)
DPGGAN
0. (0005)).004)
0.024
OOM 6.9e
OOM
THEPUFF(Ours)
0. 0.095
0.007 0.00778.2e (8.2e-9)
3.6e (2.4e-5)
(8.6e-
A. PSEUDO-CODE OF Dust AND Dpre
Here we show the details of calculating Data and Drre using pseudo-code, i.e., how Data calculate the probability of input walk being sampled from real graph, and how Dpru calculate the probability of input walk being sampled from perturbed graph.
As Buss and Dyre share the exact same architecture, we only show the pseudo-code of Duras pseudo-code for Iprro is exactly a copy of IDiit
In detail, for a sampled walk, we first fetch the node embeddings of the nodes in the walk (line l). Then, the node embeddings and the sampled walk are fed into the tri-level attention layer (line 3), followed by a fully connected layer (line 4 - 5) where probability of the sampled walk being sampled from original graph (or perturbed graph for D3 pru) is the output.
20

---

Published as a conference paper at ICLR 2025
Algorithm 3 Pseudo-code of Datta
Input:
Sampled walk W; = {Lo
2i
(t) for 02 .2.... J: node embedding vectors {h/0}:
tri-level attention layer described in Eq. 6 fully connected layer with weight matrix Wo E Rddx and biases E R².
Output:
Probability that W; is sampled from the real graph.
1: Fetch embeddings H E Rixd, where i-th row (t) is the embedding of v!!
2: Compute tri-level attention scores A time A node A type through Eq.
3: Calculate output of attention layer Z in Eq.
4: Calculate 2-dimensional output of fully connected layer [po.P1]" ZWo b
5: Output probability e"0+e"1
ePo
A.11 PSEUDO-CODE ASSEMBLER
To better explain how assembler handle the temporal information, pseudo-code for assembling tem- poral heterogeneous graph from scoring matrix and meta-path frequencies is shown below. Note that time superscripts (6) of nodes emitted in Eq. 16 and Eq. 17 for brevity.
In detail, after we sample a sufficient amount of temporal heterogeneous random walk from gen- erator, count the frequencies of edges and meta-paths get scoring matrix and meta-path frequencies po- With these two as inputs, assembler iteratively assembles the generated temporal heterogeneous graph follows. In each iteration, we first sample starting node based on node degrees in the scoring matrix (line 2). Then, we sample a meta-path that starts with the starting node's 's node type based on meta-path frequencies (line 3). Finally, we iteratively sample the of the nodes in the sampled meta- path one by one and add the sampled edges to the assembled graph (line 8): the subsequent node is sampled based on next node type and scoring matrix (line 5), and the edge between the sampled subsequent node and current node is added to the assembled graph (line 6- 7). Finally, after we get desired amount of edges, the sampling iteration (line 9) stops and output the final assembled temporal heterogeneous graph.
Algorithm 4 Pseudo-code of Assembler
Input:
Scoring matrix S; meta-path frequencies po-
Output:
Assembled temporal heterogeneous graph 9 = (.))
1: while not enough edges do
2: Sample starting node vi (t1) based on probability Eq.
3: Sample meta-path O (o),...or) po
4: for in 1, 1,.,, do
5: Sample i++1 (f++1) based on probability in Eq. 17
6: Add edge (u) (i+1) to g(4))
(ta)
7: Add edge (u. (f41) ((+41) to g(t++))
8: end for
9: end while
21


Reviews:
[{"review_id": "VTwuS72Usz", "reviewer": "Reviewer_9W8E", "summary": "The paper proposes a differentially private method to generate temporal heterogeneous graphs. The method first perturbs the input temporal heterogeneous graph for privacy protection. A generative adversarial network is trained using the perturbed graph and the original graph to generate large-scale and privacy-utility-adversary graph. The paper proposes six metrics to evaluate the graphs.", "questions": "1. Though the graphs are evaluated on the proposed metrics, it seems a good idea to see and understand their performances on some specific tasks.  \n1. What is the motivation for performing only the node signature structural query?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well written and easy to follow. \n1. The problem of privately generating temporal heterogeneous graphs is interesting and relevant. \n1. The paper introduces six novel metrics to the temporal and heterogeneous nature of graphs, allowing for more precise evaluation of the generated graphs.", "weaknesses": "1. The details on hyperparameters are missing. \n1. Attack experiments can be thoroughly evaluated on all the datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kEGAmbH89a", "reviewer": "Reviewer_jsYy", "summary": "The introduces THEPUFF, a framework for generating temporal heterogeneous graphs that balances privacy, utility, and efficiency. THEPUFF employs a differential privacy algorithm to perturb input graphs, protecting privacy, and then uses a generative adversarial setting to learn and produce synthetic graph data that preserves both privacy and utility. The authors propose six new metrics to measure the utility and privacy of the generated graphs in a temporal setting. Extensive experiments on large-scale datasets demonstrate THEPUFF's ability to generate utilizable graphs with protected privacy compared to state-of-the-art baselines. The framework includes a privacy-preserving graph sample for distribution, an adversarial generative model for fitting the distribution, and an assembler for aggregating generated walks into a final graph. THEPUFF's effectiveness is validated through comprehensive evaluations and attacker experiments, showing it generates graphs with lower successful attack probabilities, indicating stronger privacy protection. The paper concludes that THEPUFF is the first work to address temporal heterogeneous graph generation with guaranteed privacy.", "questions": "1. How is D_priv calculated in the proposed method? Any parameters involved? How does the parameter setting impact the performance of the proposed method?\n2. 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?\n3. 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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper addresses a significant gap in the field by proposing a method for generating temporal heterogeneous graphs with a focus on privacy preservation, which is increasingly important in data-sensitive applications.\n2. THEPUFF is designed to balance three key aspects: privacy, utility, and efficiency, which are often competing considerations in data generation tasks. This balance is achieved through a sophisticated approach that includes differential privacy algorithms and generative adversarial networks (GANs).\n3. The paper provides a thorough experimental evaluation using multiple real-world datasets, demonstrating THEPUFF's effectiveness and scalability compared to baselines using various metrics. \n4. The paper is generally good written and easy to follow.", "weaknesses": "1. As far as I am concerned, the key challenge in generating temporal graphs lies in the potential privacy leak in the temporal sense. The paper does not emphasize enough how such a challenge is tackled in the proposed method. \n2. The paper carried out comparative experiments against baselines like EDGE (Chen et al. 2023), while excluding other state-of-the-art baselines like DISCO (Xu et al. 2024). Justifications should be provided to the choice of baselines. \n3. Some technical details are missing, like the functional form of D_priv, which hampers a smooth understanding of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2iohokh3TZ", "reviewer": "Reviewer_ynGq", "summary": "This paper introduces an innovative model, THEPUFF, for temporal heterogeneous graph generation that balances privacy protection and data utility. By leveraging adversarial learning and differential privacy perturbation, THEPUFF effectively safeguards privacy while preserving usability, with comprehensive experiments demonstrating its robustness and utility. Suggestions for improvement include clarifying methodological details, adding comparative experiments with existing methods, incorporating additional attack tests, and providing efficiency analysis. Overall, THEPUFF shows strong practical potential and innovation, and further optimization could make significant contributions to privacy protection in relational data.", "questions": "See the weaknesses above", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The use of adversarial learning and differential privacy perturbation is well-justified, and the paper provides six metrics to comprehensively evaluate the model’s effectiveness in privacy and utility preservation.\n2. The model is designed for applications that require scalable, privacy-sensitive graph data generation, with potential uses in recommendation systems, question answering, and beyond.\n3. Extensive experiments, including attack simulations, ablation studies, and parameter analyses, validate the robustness and practicality of the model across diverse scenarios.", "weaknesses": "1. 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.\n2. While THEPUFF claims efficiency, the paper lacks explicit efficiency metrics or runtime comparisons, which would substantiate this claim and assess scalability\n3. The model’s privacy resilience could be more comprehensively assessed by testing against a broader range of privacy attacks, such as structural or attribute inference attacks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)