# Retrieval Verification: Reviving_Life_on_the_Edge_Joint_Score_Based_Graph_Generation_of_Rich_Edge_Attributes_parsed

## Pilar: Background
**Query:** _Penelitian ini dilatarbelakangi oleh urgensi masalah, konteks situasi saat ini, serta motivasi mendasar yang mendorong perlunya dilakukan kajian._

### Rank 1 (Score: 0.8393)
**Header:** **1 Introduction**
**Content:**
```text
Generative modeling is a persistent challenge in scientific and engineering fields, with broad practical use cases. The primary goal is to understand a large database’s inherent distribution, enabling new samples to be generated. In many use cases, using a graph representation is convenient for describing the samples, such as in molecule and protein design (Du et al., 2022), neural architecture search (Oloulade et al., 2021), program synthesis (Gulwani et al., 2017), and more (Zhu et al., 2022).  
The exploration of generative modeling is a longstanding endeavor, marked by the development of various methodologies throughout the years, including variational autoencoders (Kingma & Welling, 2014), adversarial learning (Goodfellow et 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  
(Dhariwal & Nichol, 2021; Naiman et al., 2024b;a) and solve many downstream tasks (Ho et al., 2022; Naiman et al., 2023; Berman et al., 2024). Recently, the generation of graph data has gained increased attention (Li et al., 2018; You et al., 2018). In particular, the modeling of graph distributions through score-based approaches (Song & Ermon, 2019) stands out as a promising avenue that necessitates a deeper investigation.
```

### Rank 2 (Score: 0.8282)
**Header:** **2 Related Work**
**Content:**
```text
**Score-based generative models.** Diffusion and score-based models represent generative models that sample new data by iteratively denoising a simple, pre-defined distribution (Sohl-Dickstein et al., 2015; Song & Ermon, 2019; Ho et al., 2020). Song et al. (2021) showed that these methods can be described in a unified framework of SDEs. Thus, we will use the terms diffusion and score-based models interchangeably. The diffusion process consists of the forward pass, where noise is gradually added to the data until it converges to a normal Gaussian distribution, and the reverse pass, where a backward SDE is integrated using a denoising model. New samples are defined as the convergence points of the reverse pass. While several graph generative frameworks exist (Wu et al., 2020; Zhou et al., 2020), we focus on score-based approaches.
```

### Rank 3 (Score: 0.8253)
**Header:** **B.4.2 GDSS-E Baseline Implementation Details**
**Content:**
```text
**GDSS architecture.** For a detailed explanation of 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 edge-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 a 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 generation process to be a normal Gaussian injection, similar to regular diffusion methods.
```

## Pilar: Methodology
**Query:** _Tahapan penelitian, arsitektur sistem, desain eksperimen, dan prosedur pengujian dieksekusi menggunakan metodologi teknis berikut._

### Rank 1 (Score: 0.8297)
**Header:** **B.2.4 General Datasets**
**Content:**
```text
We present the datasets below and refer to Vignac et al. (2023) and Jo et al. (2022) 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).  
- **Stochastic-Block-Model (SBM)** - This dataset comprises 200 synthetic stochastic block model graphs. These graphs have communities 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 is 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).  
- **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.
```

### Rank 2 (Score: 0.8291)
**Header:** **2 Related Work**
**Content:**
```text
**Score-based generative models.** Diffusion and score-based models represent generative models that sample new data by iteratively denoising a simple, pre-defined distribution (Sohl-Dickstein et al., 2015; Song & Ermon, 2019; Ho et al., 2020). Song et al. (2021) showed that these methods can be described in a unified framework of SDEs. Thus, we will use the terms diffusion and score-based models interchangeably. The diffusion process consists of the forward pass, where noise is gradually added to the data until it converges to a normal Gaussian distribution, and the reverse pass, where a backward SDE is integrated using a denoising model. New samples are defined as the convergence points of the reverse pass. While several graph generative frameworks exist (Wu et al., 2020; Zhou et al., 2020), we focus on score-based approaches.
```

### Rank 3 (Score: 0.8275)
**Header:** **5 Experiments**
**Content:**
```text
We tested our qualitative and quantitative methods on diverse real-world and synthetic dataset benchmarks. The objective of the model is to learn from observed graphs the underlying distribution and be able to generate new unseen graphs that follow the same distribution. We refer to App. B.1 for a detailed problem specification. The particular objectives of this study are:  
- As our main focus is edge features generation, we show in Sec. 5.1 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.3). 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.4), and we conclude by ablating our model to analyze the contribution of every component to its performance (Sec. 5.5).
```

## Pilar: Gap
**Query:** _Apa kelemahan, keterbatasan ruang lingkup, atau masalah spesifik pada metode penelitian terdahulu yang belum terselesaikan?_

### Rank 1 (Score: 0.8331)
**Header:** **C.5 Standard Deviation in Experiments**
**Content:**
```text
We present the results of the quantitative evaluations with standard deviation to emphasize our method’s robustness. We show the MDP deterministic setting in Tab. 9. We show the MDP non-deterministic setting in Tab. 10. In Tab. 11, we show nuScenes. In Tab. 12, we show the general graphs experiment with standard deviation.  
Table 9: Deterministic MDPs with standard deviation.  



Table 10: Non-deterministic MDPs with standard deviation.
```

### Rank 2 (Score: 0.8284)
**Header:** **5.3 nuScenes: traffic scene generation**
**Content:**
```text
Table 2: Quantitative metrics on nuScenes.  
Learning traffic scenes can hugely contribute to autonomous 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
```

### Rank 3 (Score: 0.8267)
**Header:** **5.2 Generative MDPs**
**Content:**
```text
**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.e., **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 does 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. 4 shows a sample from the training data (left), a 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.
```

## Pilar: Objective
**Query:** _Apa tujuan utama, sasaran akhir, atau kontribusi spesifik yang dihasilkan oleh penelitian ini untuk menyelesaikan masalah tersebut?_

### Rank 1 (Score: 0.8463)
**Header:** **B.4.3 SwinGNN-E Implementation Details**
**Content:**
```text
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 to work with the original data instead. We follow the same training protocols Yan et al. (2023) implemented for other similar datasets. We report the results in the main text.
```

### Rank 2 (Score: 0.8340)
**Header:** 2. _Nodes_
**Content:**
```text
- (a) Valid Solution (VS): Measures if a generated grid is valid: has start and finish cells, and the route is not entirely blocked.  
- (b) Blocks (B): Measures the absolute distance between the average number of blocks in the grids. In this work, the used dataset has a ground-truth average of four. For example, if a generated graph contains seven blocks, the distance will be 3, as 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 original distribution has only one for each, and the model is expected to match this target distribution.  
- (d) Empty (E): Measures the absolute distance between the average number of regular cells. In this work, the dataset has a ground truth of 19 empty cells, and, similar to the previous two metrics, the generated graph should match this number.
```

### Rank 3 (Score: 0.8295)
**Header:** **B.4.2 GDSS-E Baseline Implementation Details**
**Content:**
```text
**GDSS architecture.** For a detailed explanation of 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 edge-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 a 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 generation process to be a normal Gaussian injection, similar to regular diffusion methods.
```

## Pilar: Futurework
**Query:** _Apa saran, rekomendasi penelitian lanjutan, atau agenda di masa depan yang diusulkan oleh penulis untuk mengatasi keterbatasan studi saat ini?_

### Rank 1 (Score: 0.8309)
**Header:** **2 Related Work**
**Content:**
```text
**Score-based generative models.** Diffusion and score-based models represent generative models that sample new data by iteratively denoising a simple, pre-defined distribution (Sohl-Dickstein et al., 2015; Song & Ermon, 2019; Ho et al., 2020). Song et al. (2021) showed that these methods can be described in a unified framework of SDEs. Thus, we will use the terms diffusion and score-based models interchangeably. The diffusion process consists of the forward pass, where noise is gradually added to the data until it converges to a normal Gaussian distribution, and the reverse pass, where a backward SDE is integrated using a denoising model. New samples are defined as the convergence points of the reverse pass. While several graph generative frameworks exist (Wu et al., 2020; Zhou et al., 2020), we focus on score-based approaches.
```

### Rank 2 (Score: 0.8247)
**Header:** **C.5 Standard Deviation in Experiments**
**Content:**
```text
We present the results of the quantitative evaluations with standard deviation to emphasize our method’s robustness. We show the MDP deterministic setting in Tab. 9. We show the MDP non-deterministic setting in Tab. 10. In Tab. 11, we show nuScenes. In Tab. 12, we show the general graphs experiment with standard deviation.  
Table 9: Deterministic MDPs with standard deviation.  



Table 10: Non-deterministic MDPs with standard deviation.
```

### Rank 3 (Score: 0.8241)
**Header:** **B.2.2 nuScenes Dataset**
**Content:**
```text
Consequently, we follow their success and are convinced that such scenes can be naturally generated as graphs. For this purpose, we extract a portion of 746 samples of traffic scenarios from the _mini_train_ split as defined in the nuScenes-devkit and use them for training and evaluation 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; 2. map elements, represented as x and y coordinates of their polygon; and 3. lanes, represented as discrete curves of length 8 meters each. We transform the graph into a radius graph of 30 meters and only preserve edges representing a relation whose target is an agent, e.g., lane-to-agent.  
**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 _x_ and _y_ 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 between each agent’s trajectory to the closest generated lane. Such a metric reflects the tendency of road participants to follow lane center lines, which is a natural behavior of road participants. We refer to Tan et al. (2021) for more details about the metrics and evaluation protocols.
```
