Reviving Life on the Edge: Joint Score-Based Graph Generation of Rich Edge Attributes
Authors: Nimrod Berman
Eitan Kosman
Dotan Di Castro
Omri Azencot
Venue: Accepted by TMLR ()

Abstract: Graph generation is integral to various engineering and scientific disciplines. Nevertheless, existing methodologies tend to overlook the generation of edge attributes. However, we identify critical applications where edge attributes are essential, making prior methods potentially unsuitable in such contexts. Moreover, while trivial adaptations are available, empirical investigations reveal their limited efficacy as they do not properly model the interplay among graph components. To address this, we propose a joint score-based model of nodes and edges for graph generation that considers all graph components. Our approach offers three key novelties: (1) node and edge attributes are combined in an attention module that generates samples based on the two ingredients, (2) node, edge and adjacency information are mutually dependent during the graph diffusion process, and (3) the framework enables the generation of graphs with rich attributes along the edges, providing a more expressive formulation for generative tasks than existing works. We evaluate our method on challenging benchmarks involving real-world and synthetic datasets in which edge features are crucial. Additionally, we introduce a new synthetic dataset that incorporates edge values. Furthermore, we propose a novel application that greatly benefits from the method due to its nature: the generation of traffic scenes represented as graphs. Our method outperforms other graph generation methods, demonstrating a significant advantage in edge-related measures.

Published in Transactions on Machine Learning Research (1/2025)
Reviving Life on the Edge: Joint Score-Based Graph Genera- tion of Rich Edge Attributes
Nimrod Berman Bosch, Ben- Gurion University
Eitan Kosman
Bosch
Dotan Di Castro Bosch
Omri Azencot Ben- Gurion University
Reviewed on OpenReview: https: // openreview. net/ forum? id= PaddpadSmPPPp
Abstract
Graph generation integral to various engineering and scientific disciplines. Nevertheless, existing methodologies tend overlook the generation of edge attributes. However, we identify critical applications where edge altributes are essential, making prior methods potentially unsuitable in such contexts. Moreover, while trivial adaptations are available, empirical investigations reveal their limited efficacy as they do not properly model the interplay among graph components. To address this, we propose joint score-based model of nodes and edges for graph generation that considers all graph components. Our approach offers three key novelties: (1) node and edge attributes are combined
an attention module that generates samples based on the two ingredients, (2) node, edge and adjacency information mutually dependent during the graph diffusson process, and (3) the framework enables the generation of graphs with rich attributes along the edges, providing more expressive formulation for generative tasks than existing works. We evaluate our method on challenging benchmarks involving real-world and synthetic datasets in which edge features are crucial. Additionally, we introduce a new synthetic dataset that incorporates edge values. Furthermore, we propose a novel application that greatly benefits from the method due to its nature: the generation of traffic scenes represented as graphs. Our method outperforms other graph generation methods, demonstrating significant advantage in edge-related measures.
1 Introduction
Generative modeling a persistent challenge in scientific and engincering fields, with broad practical use cases. The primary goal is understand large database's 's inherent distribution, enabling samples be generated. In many cases, using graph representation is convenient for describing the samples, such in molecule and protein design (Du et al. 2022). neural architecture search (Oloulade et al. 2021). program
sesthesis Guulwani et al. 2017). and more (Zhu et al. 2022
The exploration of generative modeling is a longstanding endeavor, marked by the development various methodologies throughout the years, including variational autoencoders (Kingma Welling 2014), adversarial learning (Goodfellow al.) 2014), normalizing flows (Rezende Mohamed] (2015), and diffusion models
(Sohl-Dickstein et al. 2015). These approaches have been used to generate various information types

---

Published in Transactions on Machine Learning Research (1/2025)
DDariwal & Nichol 2021
Naiman et al. 2024b a) and solve many downstream tasks (Ho et al. 2022 Naiman
et al.] (Li et al. 2018 You et al.
2023 Berman et. al.,
2024 Recently, the generation of graph data has gained increased attention
2018). In particular, the modeling of graph distributions through score-based
approaches (Sog & Ermon
2019
stands out as a promising avenue that necessitates a deeper investigation.
Generally, a graph contains several components that have mutual dependencies. One is the nodes, a set of entities with possibly assigned attributes. The second is the adjacency information that specifies the nodes' connectivity with potentially assigned features. For example, one could use this structure to model a molecule, where nodes represent atoms with atomic numbers as their attributes, and the adjacency information represents the intramolccular bonds and their types. The involvement of several components in the graph whose attributes have a mutual interplay introduces the challenge of modeling the components altogether along with their relations. In order to address this challenge, a discrete diffusion approach for generating categorical node and edge attributes was proposed (Vignac et al. 2023). However, extending to sampling real-valued attributes remains non-trivial. Yct, while a discrete diffusion process fits well in certain cases, we advocate in this work the consideration of a more general problem with continuous score-based frameworks.
Recent works on casse-based models for graph generation have made significant strides but remain limited in scope (Niu et al.) 2020 Jo et al.] 2022 Fan et al. 2023). While proficient in their designated tasks, these models either completely exclude edge attributes or treat. graph components separately, limiting their capacity to capture complex relational structures. We address these limitations with a unified framework that enables the generation of node and edge attributes. An exemplary task with dominant edge attributes is shown in Fig. [1 This task involves translating a driving scene into a graph representation, similar to the approach in VectorNet (Gao et al., 2020). One prominent feature is the existence of edge attributes that introduce relative and interactional information between the road participants. For instance, an edge feature like a "looking at" flag-w Hag-whichh indicates if one vehicle is actively observing motheer-capuun situational awareness crucial in dense traffic. This relational cue, such as mutual acknowledgment during lane changes, is necessary for accurately modcling driving bohavior but emerges only from the interaction itsclf, making it impossible to derive from node features alone. This and less expressive versions of such represent ation are prevalent in motion prediction literature (Huang et al. 2022), with models utilizing it often leading the prediction task leaderboards (Cacsar et al. )020). Consequently, representation. An additional natural example originates from Markov Decision Processes (MDPs), where edge features like transition probabilities and rewards capture the dynamics of state transitions. Without edge features, this information would have to be redundantly stored at the node level, increasing complexity and obscuring transition flow. Encoding these properties directly on edges provides a compact, interpretable representation that preserves the MDP's natural structure.
are interosted in generating scenes for this type of
The closest evidence to graph generation with attributes appears in " "Attributed Graph Generation" " (Peitfeer III et al. 2014 Lemaire et al. 2024). However, this formulation only associates attributes with the nodes, leaving the edges free from additional attributes besides the adjacency matrix. As we find critical tasks where edge attributes are dominant, we want to promote awareness of this problem to enable the generation of graphs with richer information and more expressiveness than the current formulation of attributed graphs. Consequently, in this study, we leverage the evident insight that edge attributes convey neighborhood information and provide instrumental data absent in the adjacency matrix crucial for generating edge attributes. We propose to encode graph distributions via a joint Stochastic Differential Equation (SDE), describing the evolution of node and edge attribules. Importantly, our technique jointly solves for graph elements. Consequently, it benefits from the synergetic connections between nodes and edges. In comparison, GDSS (Jo et al.) 2022) proposed similar diffusion system for adjacency and nodes that opt for a scparated solution that may be sub-optimal in encoding certain graphs. We solve our joint SDE by further strengthening the dependencies between nodes and edges. In practice, this is achieved by combining node, edge, and adjacency information in an attention module, maximizing the mutual interplay of the graph components. Overall, our approach is designed to maximally exploit the information encoded in the nodes and edges and their interactions.
We consider challenging benchmarks with important edge features to evaluate our approach. We use the term edge-important graph datasets to refer to datasets containing graphi where edge features play a crucial role in conveying information. Specifically, we introduce a new synthetic dataset of grid mazes whose graphs are based on Markov decision processes. In this setting, edge attributes encode the probability of moving
2

---

Published in Transactions on Machine Learning Research (1/2025)
Type: motorsytle
Typer car Position:
Position: Fe
Type: truck
Position: X,, Velocity: kmmb
Velocity: Arnk
Velocity:
Ded Becyys distmme at,
Type:
Position: Xo, ys Velocity: 10 kmmh
(a) Simulation of possible traffic with two cars, truck, and a motorcycle.
(b) The correspouding graph representation of the scene.
Figure 1: Example of a graph with attributed edges. It illustrates graph in Figure Ib that represents the driving scene in Figure Ia Each node represents an entity within the scene and encodes node attributes such as one of the types car, truck, motorcycle, velocity, position, history trajectory, etc. Additionally, edges aftributed with relative information such distance, velocities, relative accelerations, and flag indicating whether the vehicle's driver, represented by the source node, looks at the vehicle represented by the target node. For illustration purposes, we use a graph with only a few edges, but additional edges could be incorporated to represent more complex relationships.
between grid cells. Additionally, we offer traffic scene generation on nuScenes (Caesar et al. 2020) as a new benchmark for evaluating odporrat generative graph methods. Finally, we define and estimate edge-related error metries, allowing to compare edge capabilities of generative models quantitatively. Our main contributions can be summarized as follows:
We extend the graph generation task to enable the generation of more expressive graph structures by formulating the graph generation with edge attributes. We propose a joint SDE framework for generating graphs with this information and demonstrate the importance of generating all graph components encompassing multiple node and edge attributes. We establish new links between graph generation in MDPs and real-world traffic scenarios. We advocate for a comprehensive benchmark for edge-basee based graph generation and lay the groundwork for future research integrating multiple edge attributes into various graph-based applications.
We introduce a novel inductive bias for score-based models in graph generation, leveraging a newly formulated SDE approach that captures the interplay between edges and nodes. Additionally, model incorporates an architectural bias to facilitale the propagation of edge information for better score estimation.
We thoroughly evaluate our approach on diverse benchmarks and conduct ablation studies. Our results demonstrate superior performance over bascline models, excelling across various standard evaluation protocols for graph generation tasks, particularly in edge metrics.
2 Related Work
Score- generative models. Diffusion and score-based models represent generative models that sample new data by iteratively denoising simple, pre-defined distribution (Sohl-Dickstein et al. 2015 Song & Ermon 2019 Ho et al. 2020). [ong et al. (2021) showed that these methods can be described in unified Tramework of SDEs. Thus, we will use the terms diffusion and score-based models interchangeably. The diffusion process consists the forward pass, where noise gradually added to the data until it converges to normal Gaussian distribution, and the reverse pass, where backward SDE is intogratod using a denoising model. New samples are defined the convergence points of the reverse pass. While several graph generative frameworks exist (W et al. 2020 Zhou et. al. 2020), focus score-based approaches.
3

---

Published in Transactions on Machine Learning Research (1/2025)
Discrete and continuous graph diffusion models. Haefeli et al. (2022) suggest discrete perturbations
of the data distribution through denoising diffusion kernel. Similarly, DiGress (Vignac et al. 2023) uses discrete diffusion methods (Austin et al. 2021 to produce discrete graphs containing categorical node and edge values. Recently, GraphARM (Kong et al. 2023 designed a modc-absorbing autoregressive diffusion for efficient and high-quality sampling. Others proposed a discrete diffusion process that utilize graph sparsity to gain efficiency (Chen et al. 2023). While is argued that discrete modeling of graphs may be beneficial, it is unclear how to sample real-valued attributes in existing frameworks. We insist that many real-world problems are naturally defined by continuous values, which requires the development of general graph generative model. To this end, several works have proposed score-based methods for graph generation, though they often face limitations in modeling edge attributes. Niu et al. (2020) introduced permutation-invarre model based on graph neural networks (GNNs) for learning data distributions of adjacency matrices. To extract binary neighborhood information, the real-valued diffusion output is discretized via thresholding. Subsoquently, GDSS (Jo et al., (022) uses separate stochastic differential equations to model node attributes and the adjacency malrix independently. Yet, this separation may limit the information exchange between nodes and adjacency. Recently, SwinGNN (Yan et al. 2023 proposed non-invariant approach that permutes the adjacency matrix for graph generation. While this method addresses the permutation invariance, it still fails to generate edge features, which remain unmodeled in this framework.
Following the success of graph score-based models, we are motivated to further extend this framework to include edge features. This achieved by a careful inspection of GDSS (Jo et al. 2022), which results in the conclusion that separate scores for different components may lack context for the generation task. While trivial extensions exist, we find them to be unsatisfactory in solving even simple edge feature generation tasks, let alone challenging graph benchmarks. Instead, we address this problem by proposing a joint SDE for all graph components, combined with dedicated GNN architecture to exploit edge features. We show that our method greatly outperforms naive adaptations, demonstrating the necessity of each and every component we introduce as a whole.
Eage- GNNs. We also mention a few works that consider edge-based GNNs for various tasks. Schlichtkrull et al. (2018) offered decomposition for relational data. In [Gong & Cheng (2019), the authors exploit edge features via a doubly stochastic normalization. Similarly, [Wang et al. (2021) extended GNNs to handle edge features and node features. Motivated by these works, we explore graph generation by considering node and odge attributes.
3 Background
We briefly discuss the essential components of score-based models on Fuclidean domains Rd. We refer to (Song et al. 2021) for further details. A diffusion process is defined by {x(t))__ with t E [0, 77, where x(0) is sampled from the data distribution x(0) Po; and x(T) ~ pr, with pr being a simple prior distribution such as standard normal. Diffusion processes are the solutions of SDEs of the form,
dx fxx t)dt + gdw
(1)
where f(.tt) Idd - IR is the drift coefficient, g E F is the diffusion scalar, and is standard Wiener process. We adhere standard notations and denote the probability density of x(t) as pc(x), and the transition kernel from x(s) to x(t) for < t as (x(()(t x(s)).
The process described in Eq. 1 is generative, it allows for the ioneration of samples from x(T) pr, which can then be propagated backward through a reverse process. A well- result by Anderson 1982 shows that the following reverse-time SDE is the reverse diffusion process,
dx [f(x -9² V²V,x log (x) + gdw
(2)
where W is a reverso-time Wiener process, and dł denotes an infinitesimal negative timestep. Integration of Eq. 2 from time T time allows an effective sampling from Po- Unfortunately, estimating the score, vx log (x), is difficult for all timesteps except for L = T, which is defined as the prior distribution. Thus,
4

---

Published in Transactions on Machine Learning Research (1/2025)
GCN
X E
GCN
GCN
X
x b
GMH
GMH
GMH
(B
E
GCN
GMH
GNM
ATTN
MLP
concat
Figure 2: Our architecture. On the left, we show the score modules (Eq. 15 On the right (Blue), our GCN module constructed of GNM (Eq. layers. On the right (Red), the GMH module is constructed of attention (ATTN) layers.
coore-based models
(Song & Ermon
2019 train an estimator sx t) with the objective of min E, E x. [[50(x,,)) t) Vx, (x xo)
(3)
4 Method
Our method for generalive modeling of graphs based on two novelties. First, we propose a joint score-based model of node and edge attributes (Sec. 4.1p The sample's score is evaluated for all graph components jointly. Second, combine node, edge, and adjacency information in the attention module (Sec. 4.2). With these two key ingredients, achieve modeling of graphs as whole.
4.1 A Joint SDE Model
The main goal of our model is represent the data distribution of graphs, denoted po- A graph with n nodes is 2-tuple G = E), where X E =x are the node attributes and E E Iaxaxx is the edge attributes tensor. We refer to App. B.1 for a detailed formulation. Importantly, the adjaccncy matrix A E {0, 10.1) 1 can be recovered from E by a simple mask such as
= (max &
[Ejz))
(4)
where = (x) < and clse o The motivation behind the masking to emulate the graph structure throughout the process and at the conclusion the GNN feedforward operation. We chose e 0.01 for all datasets. Thus, encoding G (X, F.) sufficient to fully capture the underlying structure of the graph. The choice of Eq. 4 is particularly suitable for the datasets considered in our study, As we show hereunder, it effectively filters out low-probability transitions for MDPs, while for traffic generation, small distances correspond to invalid links. In both cases, serves to remove insignificant connections, improving the model's I's focus on meaningful relationships.
We would like to generate new graphs G Po, which we achieve by defining a diffusion process from Po pT (and back), as we describe below. We follow the general outline in Sec. 3 A diffusion process on {G, (X,, Er) is given by the SDE,
dG, f(Gr, t)dt + gdw
where f is the drift transformation on set of graphs G, i.c., f(,t) 9 G. The corresponding reverso-time SDE reads
dG, ([G () Va pr (G.)) gdw
(6)
5

---

Published in Transactions on Machine Learning Research (1/2025)
where in Eq. and Eq. we abuse the notation that appeared in Eq. 1 and Eq. 2 while keeping the equivalent meaning for g. w, W and dž on graphs. Analogously to Eq. 3 the score Va, log pog))(G.) is estimated using a graph neural network whose objective is
min Ey (Ep Por [[so(Gr,t) - Va. log (Ge Go)l
(7)
where Go Pu, G. Pos Go).
GDSS considered dilfusion process similar to Eq. However, they use separate processes for the nodes and adjacency instead of solving the joint SDE. Consequently, nodes and neighbors affect each other only through the score function. On the other hand, we aim to solve it jointly for nodes and edges, allowing them to interact during the diffusion process through the score calculation. This modification will also be emphasized below, where we elaborate on our graph neural network.
4.2 Node and Digee-Depnndet GNN
Similar to existing works NNu et al. 2020: Jo et al. 2022]. we adopt the framework of Graph Neural Networks (Wu et al. 2020). This architecture maintains permutation equivariance, ensuring that the model learns a desired head attention module (Back et al., 2021). A fundamental element within our strategy is the Graph Neural Module (GNM), where nodes, edges, and adjacency exchange information. The illustration of our architecture is given in Fig. 2
intpuuttttionnivviiiina distribution (Niu et al. 2020). Moreover, we utilize the graph multi-
Graph neural module. Given an intermediate estimation of node and edge attributes, denoted by X₁ and E,, respectively, the GNM module is defined via
GN,(X, F.) = A,X,Wx + tanh(B(rep(AA) O F.WE)),
(8)
where ④ is the element-wise product, Wx WE are neural network weights. B[] sums the values of each node incoming edges frewwre and the operator rep(-) takes a matrix and repeats it v times along the third dimension. Inspired by Kipf & Welling (2017), we construct the matrix Å, by scaling the adjacency A, with the degree matrix Dr, i.e., = @ A, @ D where D, diagonal matrix encoding the number of edges per node. Finally, A, is extracted via Eq. The GNM module learns how to propagate information to each node from its neighboring nodes while also absorbing information from incoming and outgoing edges. As shown in later ablation experiment, this capability enables the propagation of edge feature information. Essentially, the left side of the addition learns to propagate node features to other nodes and edges, and the right side of the addition does so for the edge features. Finally, the output shape of this operation is x n x d where the batch size, n is the number of nodes in the graph and d is the number of features.
Attention module. We also employ a commonly-usee used attention module, ATTN (Baek et al. 2021 ATTN(X,, Ex) = avg (Q.K? /Vd,,, with Q: :- GNMo(X,, Ex) and K, == GNMx Et), avg(-) is the mean over the axis of the different attention channels and d, is the attention dimension. Previous studies, such as Jo et al. (202)), have demonstrated the effectiveness of attention as simple yet powerful model. It facilitates efficient information propagation through both nodes and edges. The output dimension of the attention operation is b x n x n x l where is the batch size, n is the nodes size and, k is the number of features on each edge.
Our graph neural network. We utilize the GNM and ATTN modules construct our full graph neural network to compute the score se(Ge,t) t). To simplify notation, we define H H(hh) }. J, M) as the module that takes collection of vectors { with J elements, concatenates them, and feeds the result through multilayer perceptron (MLP) M:
H((h))J,M) = M (concau (
J is determined by hyper- parammeee and plays a role in enabling the model capture multiple propagation flows at each level of the graph neural network. Then, we define two components that will be used to generate

---

Published in Transactions on Machine Learning Research (1/2025)
the node and edge attributes. The graph convolutional network (GCN) and graph multi-head attention (GMH) are given by
GCN Eb) H(GGNM(X, Edj),,
(10)
GMH(X, Ex) == ((AATTN(X, Ex)) Mo)
(11)
The GCN and GMH components compress information across different activations.
Finally, define the score so so(Gt, () by
sa(Gr, = (60 (X,, Er, (X,, E,,
(12)
To estimate the aforementioned score function, we use feed-forward neural networks Fx and FE as follows. Given initial node and edge attributes, denoted as X! = X and E. = E, respectively, the model sequentially alters its inputs as they pass through the layers by
x = (X) = t) E == 1 - GMH((X"",EE) E.
(13)
(14)
Here, X1, Ej denote the node and edge attributes representing the output of the 1-th layer, I E [1, Lj. It incorporates multiple hierarchical latent representations, enabling the model to capture multiple propagation steps and different levels of information abstraction. We also considered using GMH instoad of GCN to compute the node scores; however, we found that both approaches yielded similar performance. Consequently, we opted for GCN due to simplicity. Conversely, we found that utilizing GMH was crucial for achieving superior results for calculating edge scores. Our computation is completed by
sp (X,, E,,t) = H((X)), L, Mox) s (X,, E,,t) H((E)), L.
(15)
Importantly, our Eq. allows for proper digestion of the edge information by the score network and its propagation through the entire score model. We consider this formulation to be crucial for estimating the score, as demonstrated in Sec. 5.4. Finally, we briefly conduct a complexity analysis. The attention mechanism governs the time complexity. Specifically, both GMH and GCN modules introduce an O component for time that scales linearly with the number of attention heads and the input/ /outuut feature dimensionalitiess Storage for edge features requires O(n2v), with being the number of features. Thus, our approach is similar in time and memory complexity to other mate-of-theeatt models such DiGress (Vignac ct al. 2023) and GDSS (Jo et al.] 2022). In addition to the thcoretical analysis, we conduct an empirical complexity evaluation, detailed in (App. C.1
5
Experiments
We tested our qualitative and quantitative methods on diverse real-world and synthetic dataset benchmarks. The objective of the model is to Iearn from observed graphs the underlying distribution and be able to generate new unseen graphs that follow the same distribution. We refer to App. B.I for detailed problem specification. The particular objectives of this study are:
As our main focus is edge features generation, we show in Sec. 5. that incremental modifications of GDSS are ineffective, highlighting the non-trivial importance of our approach.
We introduce a new challenging synthetic dataset of Markov decision processes (Sec. 5.2 Further, we present a new use case: a real-world traffic generation task (Sec. 5.3h. To the best of our knowledge, we are the first to tackle this task via graph generation.
We evaluate the score estimation quality (Sec. 5.4h, and we conclude by ablating our model analyze the contribution of every component to its performance (Sec. 5.5
7

---

Published in Transactions on Machine Learning Research (1/2025)
Homogeneity: 100%
Homogencity: 63.9%
Homogeneity: 53.8%
Homogencity: 99%
Homogeneity: 100%
-0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
-0.5
0.0
0.5
(a)
Ground-Truth
(b) GDSS-E
(c) Joint-SDE-Model
(d) GNM-Based-Model
(e) Ours
Figure 3: Our ablation study shows that GDSS-E and the other variants yield inferior distributions compared to our approach concerning the ground-trus taanh data distribution estimation.
5.1 Synthetic Dataset Ablation Experiment
In this section, we conduct in-depth study to assess the performance gains from incorporating different components. Our goal is to remonstrate that the current baseline, even with incremental adjustments for edge feature generation, is ineffective for this task, whereas our approach effectively learns both inter- and intra-edge feature attributes as intended.
Dataset. We utilize synthetic dataset of 1000 complete graphs with ten nodes each, with only edge attributes. The nodes do not contain any information. Let E be the set of odges in a sampled graph. Each E belongs to IR2 and the two features in are sampled randomly from only one of the Gaussian clusters depicted in Fig. 3a Additionally, the graph edges homogeneous, i.e., they are all sampled from the same cluster (the upper right the lower left).
Baseline and variants. To create a solid baseline, we adapt GDSS to handle multiple edge features, and we name it GDSS-E. Refer to App. B.4.2 for more details. We consider GDSS-E to be vanilla model without any of the components that we proposed in this work. Then, to ablate our two model components, we separate each and add them the vanilla baseline model. We denote the baseline with our joint SDE model (Eq. 7 as jpint-SDE-Moded, and the baseline with our GNM model (Eq. S as WNM--ased-Modee Finally, our approach is based on GDSS-E and comprises both components. Note that all the variant's 'ss score estimations are similar to the base model.
Evaluation. Fig. 3 contains scatter plots of the edge distributions for the different basclines. For this visualization, we generate 50 complete graphs with 5000 edges in total. The desired result would be a generation of edge features similar to the ground truth in Fig. 3a A good model should generate the same visual clustering as the ground truth. Further, to evaluate the edge features quantitatively, we consider the homogeneity of edges. We check the percentage of graphs that are homogeneous, meaning all edges in the graph belong to single cluster, as in the real data. Then, we compute the average percentage of this test. for the 5000 generated samples per method. We detail the homogeneity score above each plot, where good models should yield 100% as the ground truth.
Results. Fig. 3b shows that GDSS-E roughly approximates the distribution. However, the two clusters appear blureed, making it difficult to differentiate between them. In addition, fails to learn the homogeneity characteristics of the data. The joint-SDE-Modeel (Fig. 3cb presents improved results by estimating denser Gaussian clusters. Alas, fails to yield a fino-grained generation as some samples are outside the original distribution (e.g., the points around 0). Further, this model also fails in the homogeneity task. The GNM- Based-Model (Fig. [clp generates blurred and non-separated clusters. Nevertheless, it successfully models homogeneous edge fcatures, achieving 99% homogeneity score. Finally, our approach (Fig. Bel demonstrates a similar distribution to the ground truth in terms of separation and clusters' structure, as well as perfect homogeneity score.
These results shed light on the importance of our components. On the one hand, our joint SDE process accurately models the underlying distribution, but it struggles with preserving homogeneity, i.c., with interactions between the graph edges. On the other hand, the GNM-based model succeeds in maintaining
8

---

Published in Transactions on Machine Learning Research (1/2025)
Train Data
GDSS-E
Ours
Figure 4: A qualitative comparison between the original data (left), GDSS-E (middle), and our method (right) on the deterministic MDP grid maze dataset. Blocks are colored blue (squares), and start and finish nodes in yellow (diamonds) and green (triangles), respectively. Our graphs consistently have four blocks, one start node, and one finish node, required.
homogeneous aspects, but is challenged by the data distribution. We conclude that our new components are important: 1) the joint SDE process crucial in modeling intra-edge interactions, and 2) the GNM module is instrumental in capturing inter-edge relationships.
5.2 Generative MDPs
Reinforcement Learning (RL) environments typically consist of multiple states and the probabilities move from one state to another. These environments often formalized as Markov Decision Processes (MDPs), which can be viewed as directed graphs, where nodes represent states and edge attributes represent the transition probabilities. We strive to explore the connection between generative modeling of graphs and MDPs. Indeed, access to many diverse RL environments is often limited in practice, and we aim to extend and diversify available envirouments.
In this context, introduce a new synthetic MDP dataset of grid mazes. Each grid has 5 x cells (nodes), including start cell and finish cell and 25 cells in total. There are also block cells that the agent cannot traverse, while the remaining cells are emply and walkable. The agents take one action per cell {up, left, down, right). The maze is encoded via graph whose nodes are the cells, and edges are the optional transitions. The nodes in the graph, each with a single feature, represent the discrete category of each cell (start, finish, block, empty). The attributes on the edges are the continuous probabilitios moving from the current coll to one of its adjacent cells. Here, we consider two settings of using this data: (1) deterministie grid maze, where edge features are binary in {0, 1); and (2) non-deterministic grid maze, where edge attributes are probabilitics in [0, 1], and the sum of all features per cell is one. Further details these datascts and their MDP graphs are provided in App. B.2.1
A unique characteristic of our MDP graphs is their multiple attributes per edge. To the best of our knowledge, this scenario has yet to be studiod in existing generative works. In particular, prior works are designed
Table 1: Quantitative graph generation metrics on deterministic and non-deterministic grid mazes.
deterministic
non-deterministic unt not MV+ MDV1
Method
degl cl1
unt not MV1 VSt B,,
SF|
E1 degl
cl
VSt
BJ
SF4 EJ
GDSS-E
0.73 0.06 97 100 34% 9% 0.96 1.28 2.23
0.40 0.02
99 100 6%
1%
26%
0.39 0.83
SwinGNN-E
0.44
0.064
100 100 17%
62% 2
1.68 3.69
0.51
0.05
100
100 21%
1.9%
72%
2.8
2.6 5.4
Ours
0.17 0.006 100 100 68%
34%
0.1 0.58
0.31
0.013
100
100 38%
6%
33%
0.02
0.88 0.8

---

Published in Transactions on Machine Learning Research (1/2025)
to construct only single edge value. To compare our approach against strong baselines, we consider the state-of-the-art GDSS and modify it to GDSS-F as discussed in Sec. 5.1 Furthermore, we use variant of SwinGNN (Yan et al. 2023), state-of-the-art score-based graph generative model, to generate multiple edge and node features as an additional bascline and denote it as SwinGNN-E. We don not consider DiGress as a baseline due to significant disparities in the output format. DiGress (Vignac el al., 2023 solely produces discrete attributes, whereas our requirements necessitate continuous ones. Morcover, adapting DiGress to generate multiple edge attributes entails non-trivial modifications, rendering it unsuitable for direct. comparison in our experimental framework.
To quantitatively evaluate the graphs, we utilize common metrics such as the degree (deg) and cluster (cl). We do not use the orbit. metric since the grid maze MDPs are directed cyclic graphs. Additionally, we adapted the uniqueness (un) and novelty (no) metrics (Martinkus et al.] 2022) to evaluate the models' ability to generate graphs that differ from the training set and are distinct from each other. Further, we introduce five new datasot-specific and edge-based metrics that mcasure the quality of generated graphs and edge features. Valid solution (VS) tests if the grid is valid, i.e., it has start. and finish cells with viable route between them. Blocks (B) measures the distance between the average number of blocks in the grid, where in our dataset, the ground-truth value is four. Start and finish (SF) calculates the distance between the average number of start and finish cells. To clarify, in our context, start and finish are nodes classified as yellow or green, as shown in Fig. f There is exactly one starting cell and one ending cell. Empty (E) computes the distance between the average number of regular cells, which is always 19. For (B), (SF), and (E), the distance is defined as the absolute difference between the fixed original number of cells and the corresponding values in the generated graph. For example, if graph is generated with one starting cell, one finishing cell, and five blocks, then the calculations would be F = [2- 2| = 0, B = 55 - 4| 1, and E = |19 18| = 1. The final result is the average of the same calculation for each graph. Finally, MDP validity (MV) estimates the percentage of valid edge features in the generated graphs. Features are valid if the sum of the outgoing edges of a node is equal to 1. The results of our evaluation on grid maze MDPs are shown in Tab. D
The deterministic setting. Our approach better captures the graph statistics measured by the degree (deg) and cluster (cl) metrics, showing a significant gap concerning GDSS-E and SwinGNN-E. Further, our graphs' edge-based metric, MV, is twice the baseline result, i.c., 68% vs. 34%. These results emphasize our model's ability to capture edge attribute complexities. Finally, our model achieves strong results in the metrics that estimate node generation compared to GDSS-E. It is essential to highlight that although SwinGNN achieves a high percentage of valid solutions (VS), this metric docs not consider whether there are multiple start or finish points. While its B, SF, and E metrics are relatively high, indicating that the model struggles to grasp the statistical features of the graph nodes as required compared to our model. We also present a qualitative comparison of the real training data, the generated graphs obtained with GDSS-E, and our approach. Fig. shows sample from the training data (left), graph generated with GDSS-E (middle), and our generated graph (right). The colored nodes are blocks (blue) and start and finish cells (yellow and green, respectively). Our method yields a valid graph, respecting the correct number of blocks and start and finish points. In contrast, GDSS-E has two starting points and five block nodes.
The non-deterministic case. In this setting, where edge features are real-valued, edge features are valid if their MV measure is e 0.001 close to one. Further, the edge values follow a specific pre-defined distribution, and thus, in addition to MV, we also measure the MDP distribution validity (MDV). Namely, the percentage of edges that follow the distribution above. Notably, the measures in Tab. [ show that our model performs x 3 times better than the bascline on the edge-related metrics, MV and MDV. These results affirm our framework's 's ability to capture and generate diverse and complex multiple-edge altributes effectively.
5.3 nuScenes: traffic scene generation
Table 2: Quantitative metrics muScenes.
Learning traffic scenes can hugely contribute to au- tonomous driving. To the best of our knowledge, we are the first to suggest a generation of traffic scenes as graphs. We leverage the idea that a scene with elements such as cars, tracks, traffic lights, lanes, and
Method degl <4 unt
V1. 04 T.
CR. L.J
GDSS-E SG-E
1.05 0.03 15 34 3.9
0.66 0.96 0.5% 208
0.79
0.01
39
42
0.76
1.27 1.08 0.6% 302
Our 0.77
-7
7
51 51
0.36
0.8 0.080.3% 194
10

---

Published in Transactions on Machine Learning Research (1/2025)
can be represented graph. In this graph,
each node is an agent containing the trajectory across time, and each directed edge represents the effect of one agent on another. Edge features such as Euclidean distances and angles are optional. In what follows, we use nuScenes (Cacsar et al. 2020), a public dataset that is broadly used for trajectory prediction (Liu et al. 2021). Primarily, the challenge is predict future trajectory from the history traces of a road participant. We transform cach scene into a vector-graph representation, similar VectorNet (Gao et al. 2020p. The latter work was the first to utilize graph representation of the scenes, where nodes represent agents and map elements, which are later processed via GNNs to predict the target. Refer to App. B.2.2 for more details.
We evaluate our model using standard graph metrics for directed graphs alongside established traffic generation protocols (Tan et al., 2023 Feng et al., 2023 Specifically, we compute Maximum Mean Discrepancy (MMD) (Gretonn et al. 2012) metrics for vehicles (V), objects (O), and lanes (L), as well as collision rate (CR) and lane alignment (L.A). , In particular, we assess MMD over the æ and y coordinates of vehicle trajectories (V), lane curves (I), and other map objects (O). Collision Rate (CR) quantifies the frequency of collisions between generated agents, while Lane Alignment (I.A) measures the distance from each agent's trajectory to the nearest lane, reflecting the tendency of agents to follow lane centerlines a natural road behavior. For more details on these metrics and evaluation protocols, refer to (Tan et al. 2021 h. Further information on presents our results compared to the GDSS-F and SwinGNN-E (SG-E) baselines, demonstrating that our model outperforms these baselines on most general and traffic-seecffic metrics. Notably, our model captures lane location statistics (L) with approximately a tenfold improvement over the baselines.
graph representation, training, and evaluation protocols is provided in App. B.2.1 Tab. 2
5.4 Comparison of Score Losses
In this experiment, we compare the behavior of graph generation models in terms the node and edge score losses on the train and test sets. We report these losses throughout training on the nuScenes dataset Fig. 5 The left column corresponds to the train set, and the right to the test set. The top row shows the node losses, whereas the bottom row shows the edge losses. We blue and orange for the loss measures of our method and GDSS-E, E, respectively. While the node score losses comparable for both models, our method yields significantly better edge losses. Train Losses
Test Losses
Node loss
106
Ours
GDSS
105
104
10a
Edge loss
1
103
102
10a
10
1
101
103
iterations
iterations
Figure 5: We plot the node and edge scores of GDSS-E and our model on the train (left) and test (right) sets.
5.5 Ablation Study
Edgo-basod graphs benchmark ablation. We extend our ablation study Sec. 5.1 and consider the four model variants. We perform our quantitative ablation over deterministic MDP (MDP-D), non-deterministcc MDP (MDP-ND), and nuScenes. We report the results of the metrics deg, cl, and MV LA in Tab. We
11

---

Published in Transactions on Machine Learning Research (1/2025)
Table Ablation study of the four variants of our model.
Method
Planar
SBM
MDP-D
MDP-ND
nuScense
degl
clp
orbi
degl
clt
orb]
degl
clt
MV
clp
dVgd clp LA +
GDSS-E
0.945 0.96 0.66
0.74
1.57 0.25
0.73
0.06
34%
0.40
0.02
26%
1.05 0.03
208
Joint-SDE-Model
1.02 0.94 0.26
0.2
1.04 0.05
0.71
0.05
57%
1.67
0.54
2%
1.4
0.02
243
GNM-Based-Mode
0.038 0.95 0.22
0.34
0.7 0.05
0.23
0.02
55%
0.35
0.07
33%
0.99
1e-5
179
Ours
0.025 0.38 0.23 0.46 0.63 0.04
0.17 0.006
68%
0.31
0.013
33%
0.77
6e-7 194
omit some metrics due to space constraints. However, the trend is similar in those metrics as well. Our results indicate that the proposed model obtains the best results across all datasets and metrics, except for LA in nuScenes. Further, we find that only incorporating edge-based GNM, leads to inconsistent behavior. However, jointly modeling node and edge attributes attains a notable gain error metrics. Finally, using both components leads the best results.
General graphs benchmark ablation. Although our study focuses edge-important graph benchmarks, apply our method to general graph generation tasks and extend the ablation study to show the robustness of our model to different diverse datasets. To leverage the edge attribute abilities of our model, we augment every graph with edge attributes per edge. Specifically, we compute the n-th power of the adjacency matrix, and then, for cach edge Cab between nodes a and b, we assign the corresponding value encoded in the power matrix. The edge features contain the number of paths between a and b with n steps, where we set n = Tab. 3 we report the results on the Planar and SBM datasets. We observe trend similar to the previous ablation, and our method outperforms the other variants. In addition to the ablation study, we compare general graph benchmarks with augmented features at App. real-world molecule dataset at App. C.3.2 Tn both experiments, we show that our model can learn the graph distribution better with edge features, and we achieve competitive results concerning solid baselines.
Furthermore, we test our model on
6
Conclusion
While graph generation models must consider all graph elements and their interactions, existing works focus only on adjacency and node attributes. Further, seore-based methods utilize a separate diffusion process per graph element, which limits the interaction between the sampled components. This work suggests a joint score-basod model for node and edge features. Our framework maximizes learning from graph elements by combining node and edge attributes in the attention-building adjacency information are mutually dependent by construction in the diffusion process. We extensively test our approach on multiple synthetic and real-world benchmark datasets compared to recent strong baselines. Further, we introduced a new synthetic dataset for benchmarking edge- based approaches. Our results show that exploiting edge information is instrumental to performance in general and in edge-related metrics.
block module. Moreover, node, edge, and
the future, we aim to incorporate certain inductive biases into the generation pipeline. For instance, challenging benchmarks such as MDPs and nuScenes could greatly benefit from this approach, as current. methods are limited in their ability to fully capture the underlying rules of the data. Additionally, generating new samples with diffusion frameworks is costly and difficult to scale to large graphs. We plan to address these limitations by enabling variation in the number of nodes within the diffusion process, thus allowing for non-fi con-fxed-sizee graphs. Finally, increasing the expressivity of GNNs by relaxing the permutation invariance property represents an exciting avenue for further research.
12

---

Published in Transactions on Machine Learning Research (1/2025)
References
Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12 (3):313-326, 1982.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Danicl Tarlow, and Rianne Van Den Berg. Structured demoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:17981-17999 2021.
Jinheon Back, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multisct pooling. In 9th International Conference on Learning Representations, ICLR, 2021.
Nimrod Berman, Taan Naiman, Idan Arbiv, Gal Fadlon, and Omri Azencot. Sequential disentanglement by extracting static information from A single sequence element. In Forty-first International Conference on Machine Learning, ICML, 2024.
Holger Caesar, Varun Bankiti, Alex H Lang, Sourabh Vora, Venice Erin Liong, Qiang Xu, Anush Krishnan, Yu Pan, Giancarlo Baldan, and Oscar Beijbom. nuScenes: A multimodal dataset for autonomous driving. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11621-11631, 2020.
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degreo-guided graph generation via discrete diffusion modeling, aixiv preprint orXiv:2305.00 04111, 2023.
Nachiket Deo, Eric Wolff, and Oscar Beijbom. Multimodal trajectory prediction conditioned on lane-graph traversals. In Proceedings of the 5th Conference on Robot Learning, volume 164 of Proceedings of Machine Learning Research, pp. 203 212. PMLR, 08-11 Nov 2022.
Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in neural information processing systems, 34:8780 8794, 2021.
Yuanqi Du, Tianfan Fu, Jimeng Sun, and Shengchao Liu. Molgensurvey: A systematic survey in machine lcarning models for molecule design. arXiv preprint arXiv:2208. 14500, 2022.
Wenqi Fan, Chengyi Liu, Yunqing Liu, Jiatong Li, Hang Li, Hui Liu, Jiliang Tang, and Qing Li. Generative diffusion models on graphs: Methods and applications. arXio preprinl NT5:2330200299) 2023.
Lan Feng, Quanyi Li, Zhenghao Peng, Shuhan Tan, and Bolei Zhou. Traffiegen: Learning to generate diverse and realistic traffic scenarios. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pp. 3567-3575. IEEE, 2023.
Jiyang Gao, Chen Sun, Hang Zhao, Yi Shen, Dragomir Anguelov, Congcong Li, and Cordelia Schmid. Vectornet: Encoding hd maps and agent dynamics from vectorized representation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
Liyu Gong and Qiang Cheng. Exploiting edge features for graph neural networks. In Proceedings of the IEEE/CVP conference on compuler vision and pallern recognilion, pp. 9211-9219 9219, 2019.
Tan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Advances in neural information processing systems, 27, 2014.
Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723 773, 2012.
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Poundations and Trends& in Programming Languages, 4(1-2))1-119, 2017.
Xiaojic Guo and Liang Zhao. A systematic survey on deep generative models for graph generation. IEEE Transactions Pallern Analysis and Machine Intelligence, 45(5):5370-533) 2022.
13

---

Published in Transactions on Machine Learning Research (1/2025)
Kilian Konstantin Hacfeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. arXiv preprint arXiv:2210.01549, 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840 6851, 2020.
Jonathan Ho, William Chan, Chitwan Saharia, Jay Whang, Ruiqi Gao, Alexey Gritsenko, Diederik P Kingma, Ben Poole, Mohammad Norouzi, David J Fleet, et al. Imagen video: High definition video generation with diffusion models. arXiv preprint arXiv:2210.00 023003, 2022.
Yanjun Huang, Jiatong Du, Ziru Yang, Zewei Zhou, Lin Zhang, and Hong Chen. A survey trajectory- prediction methods for autonomous driving. IEEE Transactions on Intelligent Vehicles, 7(3):652-66) (744, 2022.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, pp- 10362 10383. PMLR, 2022.
BycoungDo Kim, Scong Hyeon Park, Scokhwan Lee, Elbek Khoshimjonov, Dongsuk Kum, Junsoo Kim, Jeong Soo Kim, and Jun Won Choi. Lapred: Lane-aware prediction of multi-modal future trajectories of dynamic agents. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 14636 14645, 2021.
Diederik P Kingma and Jimmy Ba. 0rXiv:1412.6900 2014.
Adam: A method for stochastic optimization. arXiv preprint
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In 2nd International Conference Learning Representations, ICLR, 2014.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR, 2017.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. In International Conference on Machine Learning, ICML, volume 202 of Proceedings of Machine Learning Research, pp. 17391-17408. PMLR, 2023.
Valentin Lemaire, Youssef Achenchabe, Lucas Ody, Houssem Eddine Souid, Gianmarco Aversano, Nicolas Posocco, and Sabri Skhiri. SANGEA: Scalable and attributed network generation. In Proceedings of the 15th Asian Conference on Machine Learning, volume 222 of Proceedings of Machine Learning Research, pp. 678 693. PMLR, 2024.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. XiXiv preprint orXin:1803. 803.03343, 2018.
Jianbang Liu, Xinyu Mao, Yuqi Fang, Delong Zhu, and Max Q-H Meng. A survey on deep-learning approaches for vehicle trajectory prediction in autonomous driving. In 2021 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 978-985. IEEE, 2021.
Mengmeng Liu, Hao Cheng, Lin Chen, Hellward Broszio, Jiangtao Li, Runjiang Zhao, Monika Sester, and Michael Ying Yang. Laformer: Trajectory prediction for autonomous driving with lane-aware scene constraints. arXiv preprint arXiv:2302. 13933, 2023.
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In International Conference on Machine Learning, pp. 15159-15179. PMLR, 2022.
Ila Naiman, Nimrod Berman, and Omri Azencot. Sample and predict your latent: modality-free sequential disentanglement via contrastive estimation. In International Conference on Machine Learning, pp. 25694- 25717. PMLR, 2023.
14

---

Published in Transactions on Machine Learning Research (1/2025)
Ilan Naiman, Nimrod Berman, Itai Pemper, Idan Arbiv, Gal Fadlon, and Omri Azencot. Utilizing image transforms and diffusion models for generative modeling of short and long time series. Aduances in Neural Information Processing Systems, NewrIPS, 2024a.
Ilan Naiman, N. Benjamin Erichson, Pu Ren, Michael W. Mahoney, and Omri Azencot. Generative modeling of regular and irregular time scries data via koopman vacs. In The Twelfth International Conference Learning Representations, ICLR, 2024b.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation vía score- based generative modeling. In International Conference on Artificial Intelligence and Statistics, pp. 4474 4484. PMLR, 2020.
Babatounde Moctard Oloulade, Jianliang Gao, Jiamin Chen, Tengfei Lyu, and Raeed Al-Sabri. Graph neural architecture search: A survey. Tsinghua Science and Technology, 27(:)669 708, 2021.
Joseph J Pfeiffer III, Sebastian Moreno, Timothy La Fond, Jennifer Neville, and Brian Gallagher. At- tributed graph models: Modeling network structure with correlated attributes. In Proceedings of the 23rd international conference on World wide web, pp. 831-842, 2014.
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows In International conference on machine learning, pp. 1530 1538. PMLR, 2015.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In The Semantic Web: 15th International Conference, ESWC, pp. 593-607, Springer, 2018
Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 2004.
(ecuupp_1):D431-DD0
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008
Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning- ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part 27, pp. 412-422. Springer, 2018
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibriun thermodynamics. In International conference on machine learning, pp. 2256 2265. PMLR, 2015.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neurol information processing systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modcling through stochastic differential equations. In 9th International Conference on Learning Representations, ICLR, 2021.
Shuhan Tan, Kelvin Wong, Shenlong Wang, Sivabalan Manivasagam, Mengye Ren, and Raquel Urtasun. Scenegen: Learning to generate realistic traffic scenes. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 892-901, 2021.
Shuhan Tan, Boris Ivanovic, Xinshuo Weng, Marco Pavone, and Philipp Kraehenbuehl. Language conditioned traffic generation. arXiv preprint arXin:2307.079477 2023.
Clément Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
15

---

Published in Transactions on Machine Learning Research (1/2025)
Ziming Wang, Jun Chen, and Haopeng Chen. Egat: Edge-featured graph attention network. In Artificial Neural Networks and Machine Learning-CCANN, pp. 253 263-264.22 Springer, 2021.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Gemiesse, Ancesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 9 (2):513-530, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1))4-24, 2020.
Qi Yan, Zhengyang Liang, Yang Song, Renjie Liao, and Lele Wang. Swingmn: Rethinking permutation invariance diffusion models for graph generation. arXiv preprint arXiv:3307.06600 2023.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International conference on machine learning, pp. 5708 5717. PMLR, 2018.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57 81, 2020.
Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. Tn Learning Graphs Conference, pp. 47-1. PMLRR 2022.
16

---

Published in Transactions on Machine Learning Research (1/2025)
A
Appendix
B Additional Details
B.1 Problem Statement
The main problem our work focuses on is given group of observed graphs drawn from ii.d unknown distribution denoted Po- We want to learn model M that will allow us to sample a new unseen graph G G= G F) where X E IR represents the node attributes and E E R.xaxx represents the edge attributes tensor from the observed distribution po- This problem is frequently called "unconditional generation" (Guo & Zhao 2022). While prior works focused on sampling graphs from Po that contain only node features, that are graphs with limited expressiveness in the sense that edge information depicts solely the graph topology, sampling high-dimensional odge features is somewhat overlooked, disabling the ability to learn distributions po that contain edge features. Our work focuses on learning model M that will learn to generate new samples from observed Po containing node and edge features.
B.2 Datasets
B.2.1 MDP Grid Maze Datasets
Motivation. We propose an innovative link between graph generation techniques and Markov Decision Processos (MDPs). Generating various environments for agents is crucial in Reinforcement Learning (RL) for effective task learning. However, there are instances where access to diverse environments is limited. Favironments can be formalized as MDPs, and MDPs can be represented as directed graphs. Thus, we are motivated to create a new dataset whose graphs contain node and edge attributes and are directed graphs. Such data will diversify the common standard benchmarks today that include undirected graphs and contain only one type of feature, either for nodes or edges.
Datasct Description. We create two variants of the MDP grid maze datasot: deterministic and non- deterministic. In both settings, the grid is the same. However, the probability of an action is different. In both datasets, the graph contains 25 nodes. A node of the next possible cell values: -1 for the block cell, 0 for the empty cell, 1 for the stating cell and finally, a a~ [0.5, 1] for the finish point. Blocks and the finish line could also be considered as prizes or punishments; however, in our graph representation, blocks are cells that are out of reach. The other two coordinates of u represent the I and y positions in the maze. An outgoing edge euv E IR between node u and v equals to p(ulu, a), which is the probability of getting to node from u given an action a: There are four actions: A (left, up, right, down). Note, valid MDP is where for all state u E S, v E S and actions A the sum of all actions:
R3 in the graph contains in its first coordinate one
Σ p(ulu, a) 1.
(16)
EES
An equivalent constraint is that all node's outgoing edges u will sum to 1. Finally, the graph's connectivity is decided by the following rules: (1) Moving toward a cell categorized as block impossible. Therefore, there is an edge toward blocks with probability zero. (all Cuv values are 0). (2) Block colls have no outgoing edges. (3) The grid perimeter is closed; thus, moving outside the grid is impossible. (4) Finally, all other moves are legal. The values of the edge features determined by the defined probabilities of p(ulu, a), which we will explain later for both deterministic and non-deterministic setups.
In Fig 6 we present the grid (lefl) and its graph representation (center) without edge values for simplicity (we later present a more straightforward graph with edge values). In addition, we show a permuted representation of the same graph (right). There are 25! ways to represent the same graph. Although it looks completely different, both representations represent the same grid maze. The yellow cell is the starting point, the green cell is the ending point, dark blue is the block cells, and the gray cells are neutral.
17

---

Published in Transactions on Machine Learning Research (1/2025)
In Fig show the complete representation, including the edges. The figure illustrates an arbitrary MDP graph, where each edge feature serves as channel. We showcase the four edge feature channels along with their corresponding values, For simplicity, we divide the representation into four different graph representations. In practice, each edge in the data represents the probability per action in an arbitrary coordinate order. Therefore, we have only one graph with multiple edge features. For instance, the inner odge of the top-left yellow node on Fig 7 denoted node '1", would have the value of
61, = (1,0,1,,
(17)
which is the value of this edge given the left, right, up, and down actions in this order. The figure's nodes are distinguished by color and shape for clarity. Blocks are represented as dark blue squares, while start and finish nodes are marked in yellow diamond and green triangles, respectively. Empty walkable nodes are displayed in light blue.
Grid Representation
Graph Representation
Permuted Graph Representation
Figure On the left is a grid representation the MDP grid maze. The yellow cell is the starting point, and the ending is the green cell. The dark blue cells are blocks. In the center, structured graph represents the grid by the rules described in the appendix. On the right, the same grid is represented by different permutation of the nodes. Both graphs are equal, and there are n! different graphs, where is the number of nodes.
Non-deterministic edges. MDPs are sometimes non-deterministic. That means, given a state and a desired action, it is only sometimes guaranteed to succeed. We create the non-deterministic dataset variation simulate this setup and challenge the edge attributes generation. In this dataset, the grids and the nodes are staying the same. However, the edge attributes are now continuous instead of being binary, Still, the decided to
outgoing sum of edges from certain node must sum up to to be valid MDP. Further, apply the next arbitrary distribution over the edge. Denote leguel = z" as the number of outgoing edges. given a desired action and nodes u, the rate of success is: p(E|u, a) = - 0.1 z". And p(klu, a) = 0.1 for any other node & neighbor u.
Dataset generator. We will provide the complete code for generating the grids and their corresponding MDPs. The generator enables control of grid size, number of ending points, and number of blocks. In addition, if these parameters are valid, the code generates only valid graphs with a start and an end. Finally, the generator gets the desired grids and randomly samples grids with the above parameters.
Dataset statistics. First, our grids are x 5. Second, there is only one ending point. Therefore, we have one starting cell and one ending cell. Finally, we set the number of blocks to be preciscly These configurations are for every grid in the dataset. We generate 1000 valid grids and split them into 80% training and 20% for testing and validations.
18

---

Published in Transactions on Machine Learning Research (1/2025)
Grid
Left
Right
0
0
0
0
0
1
0
Up
Down
1
0
0
0
1
0
1
0
0
Figure 7: In the first line, a 3 x 3 grid example, Note that in the real dataset, the grids are 5 x 5. Below, we present the four actions and show the probabilitics of moving from one state to another over the edges given a specific action.
19

---

Published in Transactions on Machine Learning Research (1/2025)
Evaluation protocols Besides the general graph generation metrics for directed graphs (degree, clustering, novelty, and uniqueness), we consider several dataset-specific metrics to evaluate node and edge generation quality.
1. Edges
(a) MDP Validity (MV): Check if the sum of the outgoing edges of a node is one. It is constraint of an MDP that the sum of probabilities is one. In the non-deterministic setup, the values are continuous, and therefore, we could be done to fix this constraint if necessary. However, we evaluate the hard constraint to measure the model's ability to capture the edge feature distributions.
0.01 gap from one. Note normalization of the edges
(b) MDP Distribution Validity (MDV): As described before, the edge distribution is different in the non-deterministic setup. Therefore, we specifically test the model's ability to generate edges with approximately the same distribution. Consequently, we test whether each node's distribution we defined for the non-deterministic setup applics with an e 0.01 gap.
2. Nodes
(a) Valid Solution (VS): Measures generated grid is valid: has start and finish cells, and the route is not entirely blocked.
(b) Blocks (B): Mcasures the absolute distance between the average mumber of blocks in the grids. In this work, the used dataset has a ground-trin truth average of four. For example, if generated graph contains seven blocks, the distance will be 3, the original distribution has only 4 blocks. The model is expected to match this target distribution.
(c) Start and Finish (SF): Measures the absolute distance between the average number of end and start cells; there are always exactly two in the setup we used. For example, if a generated graph contains two starting cells and two finish cells, the distance will be 2, as the origi- nal distribution has only one for each, and the model is expected to match this target distribution.
(d) Empty (F): Measures the absolute distance between the average number of regular cells. In this work, the dataset has a ground truth 19 empty cells, and, similar to the previous two metrics, the generated graph should match this number.
B.2.2 nuScenes Dataset
The nuScenes dataset (Caesar et al. 2020 serves as crucial resource for trajectory prediction research autonomous driving, featuring vast collection of real-world sensor data recorded in the urban environments of Boston and Singapore. This dataset provides essential coordinates of vehicles, lanes, and other map entitics from 1000 scenes, each lasting 20 seconds, and is published at 2Hz. Primarily, it is broadly used for trajectory prediction [Liu et al. 2021). Prior works used raster representations of the scenes combined with vision-based architectures to process the rasterized image. VectorNet (Gao et al. 2020) was the first to utilize a sparse graph representation of the scenes, where nodes represent agents and map elements, which are later processed via GNNs to predict the target. has paved the way to its graph-based successors (Kim et al. 2021 Deo
ct al. 2022 Liu et al. 2023), now crowned as the current statc-of-the-art that tops the leader-boards of this field.
Consequently, we follow their success and are convinced that such scenes can be naturally generated as graphs. For this purposc, we extract portion of 746 samples of traffic scenarios from the mini frain split as defined in the nuScenes-devkit and use them for training and ivaluation with 80%, 20% train, test split. Each sample is transformed into a graph with nodes of 3 types: 1. agents, with a feature vector representing an 8-second trajectory; map elements, represented as and y coordinates of their polygon; and 3. lancs, represented as discrete curves of length 8 meters each. We transform the graph into radius graph of 30 meters and only preserve edges representing a relation whose target is agent, e.g., lane-to-agent.
20

---

Published in Transactions on Machine Learning Research (1/2025)
Evaluation. For evaluating the results for nuScenes graph generation, we use the standard protocol of evaluating the MMD over each node type, i.e, the and coordinates of the trajectories of vehicles (V); the coordinates of the lane curves (L) and other map objects (O), Additionally, we evaluate the Collision Rate (CR), which measures the rate of collisions between generated agents, and the Lane alignment (LA), which sums up the distances belween each agent's trajectory to the closest generated lane. Such a metric reflects the tendency of road participants follow lane center lines, which natural behavior of road participants. We refer to Tan al. (2021) for more details about the metries and evaluation protocols.
B.2.3 Molecule Datasets
The Quantum Mechanics 9 database (Wu et al. 2018 contains around 130k small organic molecules with up to 9 heavy atoms and their physical properties in equilibrium, computed using density functional theory calculations. To evaluate our and other methods, we repeat the protocol presented in [Vgnac al.
QM9
2023
Jo et al. (2022) and refer to them to learn more about the metrics and the evaluation protocols.
B.2.4
General Datasets
We present the datasets below and refer to Vignac et al. (023 and Jo et al. (0022) for more information about the evaluation process and protocols.
Ego-small 200 small ego graphs drawn from larger Citeseer network dataset (Sen et al. 2008
Grid 100 standard 2D grid graphs. BRENDA database [Schomburg et al. 2004
(SBM) This dataset comprises 200 synthetic stochastic block model graphs. These graphs have communitios ranging from two to five, with each community containing between 20 to 40 nodes. The probability of inter-community edges is 0.3, and intra-community edges 0.05. Validity is determined based on the number of communities, the number of nodes in each community, and a statistical test as done in Martinkus et al. (2022).
Stochastic-Block-Modde
Planar This dataset comprises 200 synthetic planar graphs, each containing 64 nodes. The criteria for a valid graph within this dataset necessitate a two-fold condition: 1) the graph is connected, ensuring that every node has a path to every other node, and 2) the graph must exhibit planarity, meaning you can draw it on a two-dimensional plane without any edge crossings.
B.3 Limitations
Our approach exhibits superior performance compared to other methods on the MDP and nuScence datasets. However, there remains a quality disparity between the generated and original graphs. For example, in the MDP dataset, the generated graphs occasionally fail to adhere to the original constraints of start and end cells. We anticipate that an effective generative method would autonomously learn and adhere to such constraints. We believe that incorporating inductive bias regarding specific tasks can contribute to those tasks. Moreover, while score-based and diffusion methods typically demonstrate optimal performance across various downstream tasks in graph generation, scaling these methods to very large graphs containing millions of nodes and edges presents challenge yet to be fully addressed.
B.4 Implementation Details
B.4.1
Architecture and Hyperparameters
We refer to Sec. 4 in the main text to describe the method architecture and inplementation details. We present. the hyperparameters per dataset in Tab. 4 We used Adam (Kingma & Ba 2014) optimizer and the same learning rate of 0.01, weight decay of 0.0001, and EMA of 0.999 for all datasets. In addition, for sampling, we used the Euler prodictor, Langevin corrector, signal-to-noiso-rale of 0.7, and sampling with 1000 steps for all datascts. Finally, we use a single VP forward diffusion process (Song et al. 2021) stochastic differential equation for both the nodes and the edges. We refer to Jo et al.
(SNR) of 0.05, scale epsilon
21

---

Published in Transactions on Machine Learning Research (1/2025)
Table 4: Hyperparameters for each dataset.
Hyperparameter
MDP MDD--nn--et nuScense QM9 Planar SBM Ego Small Grid
Module
Attention layers
5
5
4
4
5
4
Edges channels
4
2
2
2
2
2
Initial channels
1
1
1
1
1
1
1
Hidden channels
8
8
8
8
8
8
8
8
Final channels
4
4
4
4
4
4
4
Attention Heads
4
4
4
4
4
4
Hidden dimension
32
32
16
32
32
32
32
Training
Batch size Epochs
256
256
128
1024
64
26
128
7
5000
5000
5000
400
5000
5000
5000
5000
SDE
Smin
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
Bmax
3
3
1
1
1
1
2022 for more details about each hyperparameter. We will publish the complete code, including the datasets, evaluation protocols, and experiment environment, upon acceptance.
B.4.2 GDSS-E Baseline Implementation Details
GDSS [Jo ct al. 2022) is statc-of-the-art method for graph generation. However, none of the other methods are adapted to generale multiple continuous edge features and directed graphs. Therefore, to create solid baseline for directed, multi-edge attribute graph datasets, we create an extension of GDSS called GDSS-E. E. In this section, we describe GDSS and then how we adapt it to our context.
GDSS diffuusin framework. In their paper, the authors adopt general dilfusion SDE modeling approach similar to that in Eq. 6 The main distinction from our framework is that they decompose the diffusion process into a system of SDEs (outlined in their paper Eq. 3). We highlight the advantages of our approach in Sec and demonstrate its empirical improvements in the ablation study in Sec where the joint SDE model shows enhanced capability over GDSS-E learning the edge data distribution.
GDSS architecture. For a detailed explanation their architectural choices, please refer to Section 3.2 of their paper. Briefly, due to the multiple SDE equation formulation, their model employs two separate Graph Neural Networks (GNNs): one for learning the score of the adjacency matrix and another for learning the node features. In contrast, our approach suggests using a single GNN to jointly model both graph components. Aside from this key difference, our architecture is constructed similarly to GDSS, with the addition of an odge-information propagation mechanism within the GNN's building block, as outlined in Sec. 4.2 Finally, we outline below additional differences and adjustments needed to adapt GDSS to the tasks and context of our paper.
Directed graphs. To adapt GDSS to directed graph, we need to delete the symmetry inductive bias of the method. First, we deleted the symmetry inductive biases in the attention module of the backbone architecture. In addition, the generated noise and the whole diffusion process are set to be symmetric, meaning they generate symmetric noise patterns. Therefore, we change all aspects of the diffusion and gencration process to be a normal Gaussian injection, similar regular diffusion methods.
Multiple edge features We need to enable the model to generate multiple features technically. GDSS outputs an adjacency matrix A E NN*N where N the number of nodes. We adjust the network parameter return E E NxNXC where the first feature is the adjacency information, and the rest of the channels are the attributes of the edges. We will publish this implementation code in the project code.
22

---

Published in Transactions on Machine Learning Research (1/2025)
B.4.3 SwinGNN-E Implementation Details
We adapt SwinGNN Yan et al. 2023) to the edge-important benchmarks. We construct similar changes as we did for GDSS-E regarding directed graphs, and for multiple edge features, we modify the one-hot encoding configuration work with the original data instead. We follow the same training protocols Yan et al. (2023) implemented for other similar datascts. We report the results in the main text.
B.4.4 Permutation equivariance and invariance
Niu et al. (2020) show that the neural backbone of generative model is permutation equivariant, then the learned distribution by the model will be permutation invariant. This trait is essential for graph datasets since ideally want equal probability of sampling different permutations of the same graph. Following our model architecture, all our hmethi iots are edge-wise, node-wise, GNN-wise. Therefore, we preserve the permutation equivariance of the neural backbone model.
Yan et al. (023)) show that equivariance can be violated but restored with a specific invariant sampling technique. However, their study discovers one main drawback our and other permutation equivariant models do not suffer from. The drawback that if graphs in the observed dataset have few permuted representations, it significantly damages the model generation quality. They showed on synthetic dataset that if there are ss 0.01% permuted representations, their model fails to learn the distribution. On the other hand, they show that equivariant models are indeed, as expected theoretically, robust for such cases.
C Additional Experiments and Analysis
C.1 Time and Memory Comparison
In addition to the theorctical analysis discussed in the main text, we also conduct empirical evaluations regarding time and memory usage. We compare our model vs the GDSS-E baseline presented the experiment section. By employing our innovative joint SDE rather than multiple SDE's like in GDSS, our models demonstrate superior performance in terms of both time efficiency and memory consumption compared to GDSS-E.
Table 5: Time and memory comparison. Time the amount of time train cach model, both models trained on same device with the same seed and number of training epochs. Memory is the maximum memory consumption during the run.
Method
nuScenes
MDP-D MMB)
Time(Sec) Memory(MBB) Time(Sec)
GDSS-E
23, 004
2, 122
8, 030
2, 485
Ours
15, 137
1, 926
8, 014
1, 719
C.2 Impact of increasing edge-feature size adjacency matrix estimation.
Our method masks the adjacency matrix (Fq. 4 questioning the impact of increasing edge feature size on adjacency estimation. We found that feature distribution complexity, not size, may influence adjacency matrix topology. The Degree metric reliably compares adjacency matrices across different graph sizes, unlike the Cluster metric. In muScenes, our method achieves a Degree score of 0.77, while in MDP, it's around five times smaller at 0.17. We hypothesize that this is due nuSccnes' more complex node fcature distribution despite MDP having twice the number of edge features (2 4).
C.3 Graph Benchmarks
Although we do not claim have superior distribution estimation for graphs where edge features are not necessary, and, in addition, our method is designed for directed graphs in contrast to all other methods, in
23

---

Published in Transactions on Machine Learning Research (1/2025)
Table 6: General graphs datasets evaluation. *** means out of computation resources.
Method
Planar clp
SBM
Ego
Small
Grid
deg.
orb
deg!
clp
orb deg!
cl4
orby
degt
clp
orb.
SPECTRE
1.42
1.35
1.33
2.12
1.37
0.51 0.046
0.14
0.73
GraphVAE
0.87
1.13
0.83
1.41
0.97
0.52
0.13
0.23
0.052
1.48
0
0.87
EDP-GNN
0.985
1.29
0.97
1.1
1.43
0.88
0.062
0.097
0.009
0.45
0.32
0.51
DiGress
1.36
0.97
1.47
1.16
1.32
1.16
0.12
0.17
0.035
0.87
0.03
1.28
GDSS
0.945
0.96
0.66
0.74
1.57
0.25
0.025
0.087
0.015
0.37
0.01
0.42
Our w.o. edge features
0.032
0.71
0.34
0.47
1.1
0.05
0.02
0.043
0.052
0.07
0.012
0.45
Our
0.025 0.38 0.23 0.46
0.63
0.04 0.02 0.036
0.046
0.01
0.007
0.39
Table 7: Molecule QM9 dataset.
Method
Val w/ot
Unit
FCD1
NSPDK4
GDSS
93.2%
94.6%
2.9
0.003
DiGress
95.5%
94.1%
0.578
0.0009
Our
96.7%
95.2%
3.6
0.006
the following two experiments, we compare our model to strong baselines on regular graph benchmarks. The generated edge features we use are arbitrary, and incorporating other engineered features on the edges, such as spectral features, could further improve our model. However, this is not our primary focus, and we leave such exploration for future research.
C.3.1 General Graphs Benchmarks
To leverage the edge altributes ability of our model, we augment every graph with edge altributes per edge. Specifically, we compute the n-th power of the adjacency matrix, and then, for each edge eab between nodes a and b, we assign the corresponding value encoded in the power matrix. The edge features contain the number of paths between and with n steps, where we set n 2.
We compare our method with strong graph generation baselines: SPECTRE MMrtinkus et al. 2022 GraphVAE (Simonovsky & Komodakis 2018 EDP-GNN (Ho et al. 2020). DiGress Vignac et al. (2023) and
GDSS [J et al. 2022). We follow the training and evaluation protocols detailed in Jo et al. (2022); Vignac ct al. 2023). We present the results in Tab. 6 Our model achieves state-of-the-art performance in several cases. In particular, in complex and large graphs such as SBM, Planar, and Grid, our method is a strong competitor in terms of the degree metric compared with other methods. These results show that our method is capable of learning complex graph structures. Moreover, we report our results with standard deviation in App. 12 to show the robustness of our model. In addition, to make a fair comparison, we exccuted the benchmark with our model, excluding edge features. Our method achieves slightly lower results when edge features are not utilized. However, it still surpasses other methods in general.
C.3.2 Molecule Graph Benchmark
QM9: molecule generation. We additionally consider the QM9 dataset (wu et al. 2018 that contains edge types and node features of atoms of molecules. We refer the reader to App. B.2.3 to learn about the dataset, evaluation protocol, and metrics. We report in Tab. 7 the results our evaluation in comparison to GDSS and DiGress. Importantly, we emphasize that DiGress explicitly designed to handle the generation of edge types it leverages transition kernels. Nevertheless, our method shows strong results, achieving the best scores the validity w/o (Val w/o) and Uniqueness (Uni) metrics.
24

---

Published in Transactions on Machine Learning Research (1/2025)
C.4 General Graphs Ablation Study Cont.
We extend the ablation study over the general graph benchmarks presented in Sec 5.5 and report the results in Tab The results support the claimed contributions of our model components, as presented in the main text.
Table 8: Ablation study of our four variants of our model on four different datasets.
Method
Ego
Small
Grid clp
degl
cl4
orb.
degl
orb,
GDSS-E
0.141
0.352
0.171
0.37
0.01
0.42
Joint-SDE-Model
0.063
0.167
0.062
1.8
0
1.44
GNM-Based- Model
0.021
0.038
0.048
0.49
0.006
0.51
Ours
0.04
0.02
0.036
0.046
0.01
0.007
C.5 Standard Deviation in Experiments
We present the results of the quantitative evaluations with standard deviation to emphasize method's robustness. We show the MDP deterministic setting in Tab. We show the MDP non-deterministic setting in Tab. 10 In Tab.
11 we show mnScenes. In Tab. 12 we show the general graphs experiment with standard
deviation.
Table 9: Deterministic MDPs with standard deviation.
Method
deg
4
unf
not
MV
VS f
B
SF L
GDSS-E
0.73
0.025
0.06 +: 0.002
97
100
34% 1%
9% d. 2%
0.96 + 0.16
1.28 = 0.05
2.23 0.16
Our
0.17 + 0.02
0.006 + 0.001
100 +
100 + 0
68% + 1%
84% + 4%
0.1 + 0.04
0.58 + 0.13
0.48 + 0.18
Table 10: Non-deterministic MDPs with standard deviation.
Method
deg L
el
m
of
MV
MDV
VS
SF 1
E J
GDSS-E
0.40 0.02
0.02 =
100
6% + 1%
0.5%
26% 2%
0.39 0.03
0.83 : 0.1
0.4 0.1
Our
0.31 + 0.01
0.01 0.001
100 4:
100 1:0
38% 1: 2%
6% 1: 0.5%
33% + 1%
0.02 :: 0.02
0.88 1: 0.1
0.8 4: 0.01
25

---

Published in Transactions on Machine Learning Research (1/2025)
Table 11: Quantitative metrics on nuScenes with standard deviation.
Method
degl
e4
un
no
V4
O
L
CRL
L.4.
GDSS-E
1.05 = 0.1
0.03 + 0.003
15 1 5
34 31
3.9 0.19
0.66 + 0.13
0.96 + 0.14
0.5%
208 + 21
Our
0.77 + 0.08
6e -e - 4e
51 3
51
0.36 - 0.01
0.8 + 0.1
0.08 + 0.03
0.3%
194 = 15
Table 12: General graph datasets evaluation with standard deviations of our method
Datasct
degree 4
cluster 4
orbit
Planar
0.025 + 0.009
0.38 + 0.06
0.23 + 0.005
SBM
0.46 + 0.09
0.63 + 0.04
0.05 + 0.0001
Ego Small
0.02 0.011
0.036 + 0.0087
0.046 0.0073
Grid
0.01 0.003
0.007 + 0.001
0.39 0.07
26

---

Published in Transactions on Machine Learning Research (1/2025)
C.6
Graphs Visualizations Generated by Our Model
e=3, n=4
e=15, n=10
e=5, n=6
e=7, n=6
e-17,
e-7,
e-5, n-6
7,
e=11, n=8
e= 18, n 13
e= n=4
2 2, n
e=4, n=4
e=5,
e=3, n=4
6=7,
Figure 8: General graphs Ego Small
e=233, n=62
e=199, n=64
e= 179, n=65
e=844, n=174
e=394, n=98
382, n=
76
43435, 107
46466, n 125
e 662, 156
e 122, n
e 03-8, n
e=242,
e=287, n=90
e=371, n=106
e=379, n=106
Figure 9: General graphs SBM
27

---

Published in Transactions on Machine Learning Research (1/2025)
c=196, n=64
c=191, n=64
c=199, n=64
c=181, n=64
e= 182, n=64
e= 194. n=64
e= 188, n=64
e= 200, n=64
180, n=64
e= 191, n=64
e=185, n=64
196, n=64
c=179, n=
c=194, n=64
c= c=185, n=
e=194, n=64
Figure 10: General graphs Planar
HO
Figure 11: Molecule Graphs QM9
28


Reviews:
[{"review_id": "vs1ZKSSFi4", "reviewer": "Reviewer_TbWc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\nThe paper addresses an important and challenging problem in the field of graph generation, which is a key contribution to the domain.\nThe approach of modeling the complete graph generation process end-to-end is particularly intriguing and shows promise for advancing current methods.\n\nWeaknesses\n\nLack of clear motivation for the proposed method:\nWhile the paper argues that “edge attributes are essential in various domains where information cannot be encoded otherwise,” it doesn’t clearly illustrate which features cannot be represented as node features. This weakens the argument that previous models lack expressiveness. For instance, in the driving scene example, relative velocity, acceleration, and distance could be derived from node features. Including simple toy examples to support this claim would help strengthen the paper’s motivation.\n\nPresentation of the method:\nThe technical contribution, namely the joint SDE model, is introduced without sufficient discussion of the key considerations and challenges involved in designing this particular model. For example, the model appears to parameterize all possible connections  E_{ijk} , despite the fact that most real-world graphs are sparse. Does this create limitations for the model? Is this the reason previous works haven’t used this approach?\n\nMoreover, the advantage of predicting the adjacency matrix  $A$  via $E_{ijk}$  isn’t made clear. How does this compare to using a simpler approach like  $A = \\sigma(X X^t)$ , where  $X$  represents node features?\n\nSimilarly, the GNN architecture is not well-justified. Are there any specific challenges posed by the diffusion problem that necessitate the architectural choices made in this model?\n\nInsufficient discussion of graph topology generation:\nIn the first toy experiment, complete graphs are used, but it’s not clear how this experiment demonstrates the unique contributions of the proposed approach. What is the advantage over running a standard diffusion model with an MLP, where each element is a concatenation of all edge information? More discussion is needed to clarify the differences and justify the method’s novelty.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the challenge of modeling graph generation as a diffusive process. The primary claim is that previous approaches fall short in jointly modeling all graph components, particularly integrating both node and edge attributes within a single diffusive step.\n The proposed method is evaluated on a traffic scene generation task, as well as synthetic tasks involving edge attribute generation on complete graphs and grid mazes.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the weakness stated above.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tNMlQjscp7", "reviewer": "Reviewer_v9yH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nThe experiments are well designed with clear statements of their objectives. Except for the details of the metrics employed, experimental procedures, results, and discussions are mostly reasonable.\n\n\n\n# Weaknesses\n\nA major weakness is that there are incorrect or unclear statements, and the manuscript needs to be revised by improving the clarity. In the following, I will provide several examples, but I would like to request the authors to review the manuscript again and improve the clarity.\n\nIn Equation 8, $\\bar{A}_t$ is a $n\\times n$ matrix, $E_t$ is a $n\\times n\\times v$ tensor, and the element-wise product between them is mathematically illegal. \n\nMetrics used in Section 5.2 are not easy to understand, possibly due to grammatical errors. For example, given the following sentence,\n> \"Start and finish (SF) calculates the distance between the average number of start and finish cells, which are always two in our grids.\"\nit is not clear i) which distance the authors use and ii) what is the distance between the average number of start and finish cells. If the sentence were \"the distance between the average numbers of start and finish cells\" or \"the distance between the average number of start and finish cells of generated mazes and that of ground truth ones\", it would be clear except for which distance were used. \n\nMetrics in Section 5.3 are also not easy to understand. Most of the explanations are excluded from the main text, and are moved to the appendix, although these are essential to understand the experimental results. In addition, the explanations are not clear. For example, MMD is used without its explanation (does it stand for the maximum mean discrepancy?).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a generative model of graphs with a focus on edge attributes. The proposed model is based on a score-based model, and has two main features. One is that it jointly models the diffusion process of the nodes and adjacency matrix (while GDSS models separate diffusion processes for them).  The other feature is a graph neural module (GNM), which computes a node-wise latent representation by combining both node and edge attributes.\n\nThe authors demonstrate the effectiveness of the proposed method by experiments.\n\nThe first experiment is an ablation study using a synthetic dataset. The result demonstrates that both features are essential for reliable graph generation with edge features, suggesting that the joint SDE process is essential for inter-edge interactions, while the GNM is essential for intra-edge interactions.\n\nThe second experiment imposes a maze MDP generative task. The authors make use of several statistics of a maze environment to see whether those of the generated maze match with those of the ground truth one. The result shows that the proposed method could generate more realistic mazes than the others in terms of the statistics.\n\nThe third experiment uses a traffic scene generation task, where the relationship between cars, tracks, traffic lights, and others is encoded into a graph. In specific, a node corresponds to an entity and the edge feature represents the Euclidean distance between the two entities. The result also shows the effectiveness of the proposed method in many metrics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "# Typos\n- Equations are referred by \"Eq. equation 1\", which is likely to be due to a misuse of a LaTeX command \\eqref. Please revise it.\n\n# Clarity\n\nI would request the authors to improve the clarity at least by addressing the concerns raised in the weakness, but desirably by reviewing the whole manuscript again and fixing unclear statements.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "RseYSNKtxZ", "reviewer": "Reviewer_ZnJ5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper introduces a novel method for graph generation. It addresses the specific problem of generating graphs with continuous edge features, something that was until then not sufficiently addressed in the literature. The approach relies on a diffusion-based generation process, with specific modules specializing in handling edge features, and allowing inter-dependency between edge features and node features. The authors then provide extensive experiments showing the abilities of their model on different tasks, such as generating Markov decision processes, molecular graphs or urban driving scenarios, as well as ablation studies to show the specific strengths and weaknesses of their two components: a score based on both edges and node features, and a specific attention-based architecture for learning inter-dependency among edge and node features.\n\n\n# Strengths:\n* The problem addressed by the paper, namely generation of graphs with rich, non-discrete edge features is a highly interesting one. It is true that edge features carry crucial information in a wide array of cases.\n* The method presented is relevant to the problem at hand. The architecture is coherent with the claims of the paper.\n* Section 4 presents the approach in a mostly clear way (although some clarifications could be made, see below).\n* Most of the content necessary for understanding is present, and some finer details are provided to answer basic interrogation that a reader could have.\n* The approach is tested on a large number of experiments, especially very relevant ablation studies, and seem to yield promising results (which need to be completed, see below).\n* The approach is (as far as I know) novel and original.\n\n# Weaknesses:\n## Major:\n\n* Some crucial metrics are lacking in the results. The metrics presented only measure the generated graphs' similarity to the training set. Yet we could expect measures of:\n  * Novelty: showing that the model generates graphs that are not present in the training set\n  * Diversity: showing that the model generates a large number of diverse graphs and not only graphs that are very similar to one another (i.e. some kind of mode collapse). The standard deviations (which are only provided in the appendix) do not show diversity.\nWithout those, the model presented could consistently generate only a handful of preexisting graphs without this appearing in the current metrics. Of course, some qualitative illustration could complement this (such as some examples of generated graphs in appendix, like it was done for EGO, SBM and QM9, but for the other cases).\n\n* While most of the information required is \"there\", the writing and presentation are sometimes quite confusing. This hinders a quick and efficient reading of the paper. Some entire sections look like a draft. Examples include:\n  * Some concepts/acronyms are used before being explicited (e.g. SDE, MDP, MMD)\n  * Some results and important points are in the Appendix, or missing, while they should be in the main text (e.g. Appendix B.1, metrics variances, clean experimental tasks description);\n  * Some notions are not described formally enough, leading to ambiguity for things that should be clear:\n    * homogeneity in 5.1-evaluation: \"edges whose both features belong to only one of the cluster\" is ambiguous;\n    * equation 8 uses some implicit broadcasting on the edge-related term, which leads to ambiguity. Maybe the dimensions of both weight tensors should be given to make everything clear immediately\n    * What is f in practice in eq 5? Thus what is in practice the limit distribution (at time T) in the diffusion process (from which you sample for generating)?\n  * Section 5.2 (and the associated appendix B.2.1) is not well written. It is very laborious to read, especially since lot of critical information (e.g. definition of the features, of the data) is in the appendix which is badly written (almost looks like a draft sometimes). There are also inconsistencies in the terminology (e.g. obstacles are called blocks in the appendix). Please clarify especially clearly and concisely what the node features, edge features and constraints are, but I think that a strong polishing of section 5.2 and App.B.2.1 is needed.\n* The relevance and robustness of parameter epsilon for equation 4 is never addressed. Nonetheless, since equation 4 is not differentiable and not part of the training process, it seems that the model has no reason to \"learn\" that there will be an edge iff this criterion is met. It thus seems really arbitrary, and could lead to absurd results in many cases (for instance if the learned features are slightly shifted, you could easily go from a complete graph to a graph with no edge despite very little change in the learned model). An analysis of this criterion's role could be suitable, and mechanism for avoiding instability.\n\n## Minor:\nBelow are the minor concerns.\n* GDSS is evoked and used as the main comparison baseline in this paper. Some more formal details as to how it works and its differences with this approach would be highly relevant (even if in the appendix).\n* Most figures rely only on color to differentiate certain crucial elements. This should be avoided as much as possible. Using shapes or symbol will significantly improve accessibility.\n* Both halves of figure 2 should be more clearly separated, and the fact that the right is a \"detailed view\" of the element in the left could be made slightly clearer (textual indication in the figure for instance).\n* All equations are written as \"Eq. equation\"\n* 5.1: what do you mean \"sampled randomly from only one of the clusters\"? Please detail this (cf. the \"homogeneity\" comment above)\n* from the described process, it seems that the number of nodes of the generated graph is fixed in advance, right? Even though the paper focuses on generating edge features, this is a strong limitation which should be addressed, I think.\n* some redundancy could be avoided between the introduction and related works, as many works are cited in both.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a novel method for graph generation. It addresses the specific problem of generating graphs with continuous edge features, something that was until then not sufficiently addressed in the literature. The approach relies on a diffusion-based generation process, with specific modules specializing in handling edge features, and allowing inter-dependency between edge features and node features. \n\nThe authors then provide extensive experiments showing the performance of their model on different tasks, such as generating Markov decision processes, molecular graphs or urban driving scenarios, as well as ablation studies to show the specific strengths and weaknesses of their two components: a score based on both edges and node features, and a specific attention-based architecture for learning inter-dependency among edge and node features.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In reference to the \"Major\" weaknesses in the previous section:\n\n* Polishing the paper overall, and specifically section 5 (making technical points very clear) is necessary for the paper to be non-ambiguous on several points. All critical information should be in the main paper rather than the appendix.\n* The metrics for evaluating the generated graphs are relevant and good, but not sufficient to show the good performance of the approach as a generative model. The analysis of the results lacks a study of diversity and novelty of the generated graphs. Adding such metrics is necessary, I think, for for guaranteeing that the claims of the paper are fulfilled.\n* Addressing the \"minor\" weaknesses above would strengthen the work.", "broader_impact_concerns": "Not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper was reviewed by three expert reviewers. All reviewers expressed significant concerns about the clarity of presentation. The authors revised the manuscript and improved the clarity, and two reviewers recommended weak acceptance of the paper, while one reviewer recommended weak rejection.

It is also my view that the paper could be further improved in terms of clarity. A "minor revision" is thus recommended for the paper, and I request that the final version of the manuscript considers the reviewers' comments, as well as the following:

- Please provide intuition for the different components of the proposed model. 
- Revise subsection 4.2.
    - In Equation (8), what is $tanh(B[rep(\tilde{A}_t) \odot E_t W_E ])$ expected to learn? Please provide more details.
    - What is the output of the GNM module? Is it an $n \times d$ matrix that stores the new representations of the nodes?
    - What is the output of the ATTN module? Is it an $n \times n$ matrix that stores the attention scores for the different pairs of nodes?
    - In Equations (10) and (11), the outputs of $J$ different GNM and ATTN modules are concatenated and fed to an MLP. Are those GNM and ATTN modules just $J$ randomly initialized instances of those modules?
    - Equations (10) - (15) need to be further discussed.
- Fix issues with parenthetical and narrative citations (e.g., first paragraph of subsection 4.2).
- Fix typos and grammatical errors (e.g., in page 5, fix the following: "in Eqs. equation 1 and equation 2...").
Decision: Accept (poster)