Generative Modelling of Structurally Constrained Graphs
Authors: Manuel Madeira
Clement Vignac
Dorina Thanou
Pascal Frossard
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Generative Models
Constrained Diffusion
Primary area: diffusion_based_models
TL;DR: We propose a constrained discrete diffusion framework for generating graphs that adhere to specific structural properties. This framework achieves state-of-the-art performance on both synthetic and digital pathology datasets.

Abstract: Graph diffusion models have emerged as state-of-the-art techniques in graph generation; yet, integrating domain knowledge into these models remains challenging. 
Domain knowledge is particularly important in real-world scenarios, where invalid generated graphs hinder deployment in practical applications.
Unconstrained and conditioned graph diffusion models fail to guarantee such domain-specific structural properties. 
We present ConStruct, a novel framework that enables graph diffusion models to incorporate hard constraints on specific properties, such as planarity or acyclicity.
Our approach ensures that the sampled graphs remain within the domain of graphs that satisfy the specified property throughout the entire trajectory in both the forward and reverse processes. This is achieved by introducing an edge-absorbing noise model and a new projector operator.
ConStruct demonstrates versatility across several structural and edge-deletion invariant constraints and achieves state-of-the-art performance for both synthetic benchmarks and attributed real-world datasets. 
For example, by incorporating planarity constraints in digital pathology graph datasets, the proposed method outperforms existing baselines, improving data validity by up to 71.1 percentage points.

Generative Modelling of Structurally Constrained Graphs
Manuel Madeira EPFL, Lausanne, Switzerland manuel madeira@epfl.... ch
Clément Vignac EPFL, Lausanne, Switzerland
Dorina Thanou EPFL, Lausanne, Switzerland
Pascal Frossard EPFL, Lausanne, Switzerland
Abstract
Graph diffusion models have emerged as state-of-the-art techniques in graph gener- ation; yet, integrating domain knowledge into these models remains challenging. Domain knowledge is particularly important in real-world scenarios, where in- valid generated graphs hinder deployment practical applications. Unconstrained and conditioned graph diffusion models fail to guarantee such domain structural properties. We present ConStruct, novel framework that enables graph diffusion models to incorporate hard constraints planarity or acyclicity. Our approach ensures that the sampled graphs remain within the domain of graphs that satisfy the specified property throughout the entire trajec- tory in both the forward and reverse processes. This achieved by introducing an edge-absorbing noise model and new projector operator. ConStruct demonstrates versatility across several structural and edge-deletion invariant constraints and achieves state-of-the-ar thet performance for both synthetic benchmarks and attributed real-world datasets. For example, by incorporating planarity constraints digital pathology graph datasets, the proposed method outperforms existing baselines, improving data validity by up to 71.1 percentage points.
specific properties, such
Introduction
Learning how to generate realistic graphs that faithfully mirror target distribution crucial for tasks such as data augmentation in network analysis discovery of novel network structures. This has become a prominent problem in diverse real-world modelling scenarios, ranging from molecule design [55] and inverse protein folding [86] to anti-money laundering [45] or combinatorial optimization [76]. While the explicit representation of relational and structural information with graphs encourage their widespread adoption in numerous applications, their sparse and unordered nature make the task of graph generation challenging.
In many real-world problems, we possess priori knowledge about specific properties of the target distribution of graphs. Incorporating such knowledge into generative models a natural approach to enforce the generated graphs to comply with the domain-specifie properties. Indeed, common generative models, even when conditioned towards graph desired properties, fail to offer guarantecs. This may however become particularly critical in settings where noncompliant graphs real-world application failures. Many of these desired properties are edge-related, i.c., constraints in the structure of the graph. For example, in digital pathology, graphs extracted from tissue slides are planar [26, 69]. Similarly, in contact networks between patients and healthcare workers within hospitals, the degrees of healthcare workers upper bounded to effectively prevent the emergence of superspreaders and mitigate the risk of infectious disease outbreaks [32, 1]. In graph generation,
lead to
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Coustrained Graph Discrete Diffusion G²
Forward (1 slep)
Ox
G
Revers (1 step)
Training
Sampling
Reverse step)
G
Forward steps)
GT-1
G
Projector
Cressuntrogy
Preterior
GNNo
GNNA
Figure I: Constrained graph discrete diffuusion framework. The forward process consists of an edge deletion process driven by the edge-absorbing noise model, while the node types may switch according to the marginal noise model. At sampling time, the projector operator ensures that sampled graphs remain within the constrained domain throughout the entire reverse process. In the illustrated example, the constrained domain consists exclusively of graphs with no cycles. We highlight in gray the components responsible for preserving the constraining property.
diffusion models have led to state-of-the-art performance [79, 64, 7]. in line with their success on other data modalities [75, 29]. However, constrained generation still lags behind its unconstrained counterpart: despite the remarkable expressivity of graph diffusion models, constraining them to leverage specific graph properties remains a particularly challenging task [41].
In this paper, we propose ConStruct, a constrained graph discrete diffusion framework that induces specific structural properties in generative models. Our focus lies broad family of structural properties that hold upon edge deletion, including graph planarity or absence of cycles or triangles, for example. ConStruct operates within graph discrete diffusion, where both node and edge types lie in discrete state-spaces [79, 27, 17,6 64, 10J. Notably, ConStruct is designed to preserve both the forward and reverse processes the diffusion model within distribution with respect to a specified structural prop- erty. To accomplish this, we introduce two main components: an edge absorbing noise model and an efficient projector of the target property. The former casts the forward process as an edge deletion pro- cess and the reverse process as an edge insertion process. Simultaneously, the projector ensures that the inserted edges in the reverse process, predicted by trained graph neural network, do not violate the structural property constraints. We theoretically ground the projector design by proving that it can retrieve the optimal graph under a graph edit distance setting. Additionally, we further enhance effi- ciency by leveraging incremental constraint satisfaction algorithms, opposed to their full graph ver- sions, and blocking edge hash table to avoid duplicate constraint property satisfaction checks. These two components enable reduction in computational redundancy throughout the reverse process.
We empirically validate the benefit of promoting the match of distributions between the training and generative processes in terms of sample quality and constraint satisfaction on a set of benchmark datasets, outperforming unconstrained methods. We demonstrate the flexibility of ConStruct by testing it with three distinct structural properties constraints: graph planarity, acyclicity and lobster components. To further illustrate the utility of ConStruct to performance of our model in generating biologically meaningful cell-cell interactions, represented through planar cell graphs derived from digital pathology data. We focus on the generation of simple yet medically significant tertiary lymphoid structures [44, 18, 58, 28, 69]. Our experiments demon- strate a significant improvement cell graph generation with ConStruct compared to unconstrained methods [52], notably achieving an increase of up to 7 7..1 percentage points in terms of cell graph va-
applications, we evaluate the

---

lidity. These results open new venues for innovative data augmentation techniques and novel instance discovery, addressing key challenge in digital pathology and real-world applications in general.'
Related Work
By decomposing the graph generation task into multiple denoising steps, graph diffusion models have gained prominence due to their superior generative performance in the class of methods that predict the full adjacency matrix at once (c.g., VAEs [40, 74, 78, 37J. GANs [16, 42, 54], and normalizing flows [48, 53, 47, 51).. Diverse diffusion formulations have emerged to address various challenges in the graph setting, encompassing score-based approaches [60, 38, 85] and discrete diffusion [79, 27, 64]. They have also been employed intermediate steps in specific generative schemes, such as hierarchical generation through iterative local expansion [7].
The explicit incorporation of structural information (beyond local biases typical of GNNs) has been shown to be an important prior for enhancing the expressiveness of one-shot graph generative models. For example, in the GAN setting, SPECTRE [54] conditions graph spectral properties to capture global structural characteristies and achieve improved generative performance. Graph diffusion models are similarly amenable to conditioning techniques [79, 31], which, despite enabling the guidance of the generation process towards graphs with desired properties, do not guarantee the satisfaction of such properties. In contrast, autoregressive models can ensure constraint satisfaction through validity checks at each iteration, effectively addressing this challenge. Although graph diffusion models can leverage formulations that are invariant to permutations, thus avoiding the sensitivity to node ordering that characterizes autoregressive approaches [87, 46, 14], they still lag behind in ensuring constraint satisfaction.
Previous graph diffusion approaches to address this challenge can be categorized according to the nature of the state spaces they assume. In the continuous case, aligned with successful outcomes in other data modalities [12], PRODIGY [72] offers efficient guidance for pre-trained models by relaxing adjacency matrices and categorical node features into continuous spaces, subsequently finding low-overhead projections onto the constraint-satisfyye
set at each reverse step. This approach can impose structural and molecular properties for which closed-form projections be derived. However, it does not guarantee constraint satisfaction, facing a trade-off between performance and constraint satisfaction due to mismatched training and sampling distributions. This challenge arises from the continuous relaxation approach, which, while effective within the plug-and-play controllable diffusion framework, imposes an implicit ordering between states that can yield suboptimal graph representations when remapping to the inherently discrete graph space. Additionally, the proposed projection operators cannot be derived for some combinatorial constraints over the graph structure that are frequently encountered in real-world scenarios, such as planarity and acyclicity.
Then, in discrete state-spaces, EDGE [10] leverages node-wise maximum degree hard constraint due to its degree guidance but it is limited to this particular property. Similarly, GraphARM [41], graph autoregressive diffusion model, allows for constraint incorporation in the autoregressive manner. However, this method requires learning a node ordering, a task that is at least as complex as isomorphism testing. Therefore, to the best of knowledge, ConStruct consists of the first constrained graph discrete diffusion framework covering a broad class of structural (potentially combinatorial) constraints.
3 Constrained Graph Diffusion Models
We now introduce our framework on generative modelling for structurally constrained graphs. We first present the graph diffusion framework and then focus on the new components for constrained graph generation.
3.1 Graph Diffusion Models
We first introduce the mathematical notation adopted in the paper.
Our code and data are available at https: http::////.ttta.oooo///aaaaaaaas
3

---

G
G
G
Projector(P, G !,'))
Figure 2: Projector operator. At each iteration, we start by sampling a candidate graph Gr-1 from the distribution Pe (G" provided by the diffusion model. Then, the projector step inserts in an uniformly random manner the candidate edges, discarding those that violate the target property, P. i.e. acyclicity this illustration. the end of the reverse step, we find a graph Gt that is guaranteed to comply with such property.
Notation We define graph as = EX, where X and denote the sets of attributed nodes and edges, respectively. We consider the node and edge features to be categorical and to lie in the spaces X' and & of cardinalities b and c, respectively. Thus, 24 denotes the node attribute of node and Egj the edge attribute of the edge between nodes and j. With H = {v- (Vi,..., .......,,)))
E then x; H² and eij Ho+1, since we consider the absence of edge between two nodes as an edge type ("no edge" type). These are stacked in tensors X E {0, 1 and E E (0.1)xxnx(et1)) respectively. So. equivalently to the set notation, also have G (X, E). Additionally, we define the probability simplex, A ((Ao: A1......4-11 E IR A for all - 11.
{0, 1), Et= U/2 = 1}. their corresponding one-hot encodings
We then recall the core components of generative models based on graph diffusion, a state-of-the-art framework in several applications [38, 79]. Graph diffusion models composed of main processes: a forward and a reverse one. The forward process consists a Markovian noise model, with T timesteps. that allows progressively perturb a clean graph G its noisy version G where T'. This process is typically modelled independently for nodes and edges. The reverse
t e process consists of the opposite development, starting from a fully noisy, G and iteratively refining it until a new clean sample is generated. This process uses denoising neural network (NN), the only learnable part of the diffusion model. The NN is trained predict probability distribution over node and edge types of the clean graph G. After its training, we combine the NN prediction with the posterior term of the forward process to find the distribution pa (G (G' "G"), from where we sample a one-step denoised graph. The reverse process results from applying this sampling procedure iteratively until we arrive to a fresh new clean graph Go. Both processes are illustrated in Figure
In some tasks, we are interested generating instances of a specific class of graphs that conform to well-defined structural properties and align with the training distribution. Importantly, these structural properties do not fully define the underlying distribution; rather, the model must still learn this distribution within the specific class of graphs. This approach becomes particularly crucial in scenarios where we possess domain knowledge but lack sufficient data for an unconstrained model to capture strict dependencies, allowing us to reduce the task's ' hypothesis space. This need also applies to many real-world applications, where generated graphs become irrelevant if they do not meet certain conditions, as they may be infeasible or lack physical meaning (e.g., drug design). Despite the remarkable expressivity of graph diffusion models, incorporating such constraints into their generative process remains largely unsolved problem.
3.2 Constrained Graph Discrete Diffusion Models
We now introduce ConStruct, a framework that efficiently constrains graph diffusion models based on structural properties. Constraining graph generation implies guaranteeing that such target structural properties not violated in the generated graphs. We build on graph discrete diffusion due to its intrinsic capability to effectively preserve fundamental structural properties (e.g., sparsity) of graphs throughout the generative process [64, 79, 27].
successful way of imposing constraints to diffusion models in continuous state-spaces consists of constraining the domain where the forward and reverse processes occur [50, 22, 23]. However,

---

constraining domains over graphs, which are inherently discrete, poses a challenging combinatorial problem. Instead, we propose to constrain the graph generative process with specific structural properties. In our approach, we explore the broad class of graph structural properties that hold under edge deletion, namely edge-deletion invariant properties.
Definition 3.1. (Edge-Deletion Invariance) Let P be boolean-valued application defined on graphs. referred to as property. P is said to be edge-deletion invariant if. for any graph G and any subset of edges E C E, it satisfies:
P(G) True
P(G') = True, with G' = G²=
(X, B).
Many properties that are observed in real-world scenarios edge-deletion invariant. For example, graph planarity is observed in road networks [83], chip design [8], biochemistry [73] or digital pathology [36]. In evolutionary biology [25] or epidemiology [70], find graphs that must not have cycles. Additionally, if we consider the extensions of discrete diffusion to directed graphs (e.g.. Asthana et al. [3]), there are several domains where graph acyclicity is critical: neural architecture search, bayesian network structure learning [88], or causal discovery [67]. Also, maximum degree constraints are quite common in the design of contact networks [32, 1J. Finally, it worth noting that Definition 3.1 is extendable to continuous graph-level features through a binary decision (e.g., by thresholding continuous values into boolean values).
Provided that the training graphs satisfy the target structural properties, ConStruct enforces these properties in the generated graphs by relying two main components: an edge-absorbing noise model and a projector. These two components are described in detail below.
3.3 Edge-deletion Aware Forward Process
Our goal is to design forward process that yields noisy graphs that necessarily satisfy the target property. This process is typically modelled using transition matrices. Thus, [Qxli = q(0" j|z.-1 i) corresponds to the probability of a node transitioning from type to type j. Similarly, for edges we have (Qrl. = q(ee = jlee-1 = =t). These are applied independently to each node and edge, yielding g (X'-IQxx 1 Consequently, can directly jump č timesteps in the forward step through the categorical distribution given by:
g(G' = EXQ))
with Qx= ... Q'x and Q = Q ....... Q'e- Noising a graph amounts sampling graph from this distribution. For the nodes, we use the marginal noise model [79] due to its great empirical performance. Importantly, to preserve the constraining structural property throughout the forward process, and, consequently, throughout the training algorithm (see Algorithm 1, in Appendix A. we propose the utilization of an
noise model [4]. This noise model forces each edge to either remain in the same state or to transition to an absorbing state (which we define to be the no-edge state) throughout the forward process. This edge noise model poses the forward as an edge deletion process, converging to limit distribution that yields graphs without edges. Therefore, we obtain the following transition matrices:
and Q' - a'As! I (1 - L.egg
Q - a1
2
where a' and a ans transition from 1 to with & according to the popular cosine scheduling [59] and the cnntual-informatiion based noise schedule (a' 1 (T + [4], respectively. The vectors 1. E (1)& and 1, E (1)c+1 are filled with ones, and m'x E A and e'g E Ho+1 are row vectors filled with the marginal node distribution and the one-hot encoding of the no-edge state, respectively.
3.4
Reverse Process
The reverse process of the diffusion model is fully characterized by the distribution Po G We detail how to build from the predictions of denoising graph neural network, GNN,, and the posterior term of the forward process in Appendix A.2. Importantly, the latter imposes the reverse process as an edge insertion process, yet does not necessarily ensure the target structural property. To handle that, we propose an intermediate procedure for each reverse step. Provided noisy graph G
5

---

at timestep f. we do not accept directly G sampled from graph. Instead, we iteratively insert the newly added edges to Gt-1 in random order, discarding the ones that lead the violation of the target property. Therefore, we only have G G if none of the candidate edges breaks the target property. We refer to the operator that outputs G (t-1 provided G+-1 and G by discarding the violating edges as the projector. Its implementation is illustrated in Figure 2 and described Algorithm 2, in Appendix A.3. Importantly, this procedure merely interferes with the sampling algorithm (refer to Algorithm 3, in Appendix A.3) and ensures that the diffusion model training remains unaffected, fully preserving its efficiency.
as the one step denoised
Despite its algorithmic simplicity, the design of our projector is theoretically motivated by the result below. We denote the graph edit distance [68] with uniform cost between two graphs G1 and G2 by G G2) (see Definition B.I).
Theorem 1. (Simplified) Let Gt = Projector (P,, " , be the set of all possible one-step denoised graphs outputted by ConStruct. If we define G as any optimal solution of:
minGec GFD(G ,G),
where C- {G
E E G)P(G) = True, G G G³) and 9 is the set of all unattributed graphs, then G can be recovered by our projector, i.e.. G E EG'
The relationship between the projector, the candidate element G (the instance we aim to project onto a constrained set) and the specified target property P (defining the constrained set) can be analogized to the conventional projection operator continuous state spaces. However, while projection in continuous spaces is typically straightforward, this is not the case for discrete state spaces, where, for instance, there often lacks an inherent notion of order between different states. In particular, projecting into an arbitrary subclass of graphs is complex general combinatorial problem to which there is no efficient solution. For example, finding the maximum planar subgraph of a given graph is NP-hard [11]. Therefore, the novelty of our method is introduced by considering an additional dependency on G to make such problem efficiently approachable, we use the previous iterate, G which we know by construction that verifies the target property, as reference. This information is added into the optimization problem through the formulation of the set C. Importantly, this formulation is consistent with the designed noise for the diffusion model, as it complies with the reverse process as an edge insertion process (i.e., G C G1-1). The complete version of this theorem and extensions for specific constraints can be found in Appendix B.
Importantly, the utilization of the projector breaks the independent sampling of new edges since the insertion of an edge now depends on the order by which we insert them at given timestep. This sac- rifices the tractability of an evidence lower bound for the diffusion model's 's likelihood. In exchange, it conserves all the sampled graphs throughout the reverse process in the constrained domain. Therefore, the edge-absin edge-absorbing noise model and the projector jointly ensure that the graph distributions of the training and sampling procedures match, within the predefined constrained graph domain. With these blocks in place, we are now able to both train and sample from the constrained diffusion model.
3.5 Implementation Improvements
We further enhance the efficiency of the sampling algorithm with the two improvements detailed below.
Blocking Edge Hash Table Throughout the reverse process, we keep in memory the edges that have already been rejected in previous timesteps (higher t). Therefore, once edge is rejected, it is blocked throughout the rest of the reverse process. This prevents the repetition of redundant constraint satisfaction checks since we know a priori that inserting a previously rejected edge would lead to constraint violation. We store this information in a hash table, where both the lookup and update operations
((1), causing minor overhead. Since only perform the validity check, of complexity O(V). once for each edge if it is a candidate edge, we either insert it or block it -, it incurs a O(n² I V) overhead throughout the full reverse process. Note that we lose any dependency on the number of timesteps of the reverse process, which is typically the limiting factor in diffusion models efficiency due its required high values (T R 10a).
Our reverse process consists solely of edge insertion steps, making it well- suited for the application of incremental algorithms. These algorithms efficiently check whether newly
Incremental Algorithms

---

added edges preserve the target property by updating and checking smartly designed representations of the graph. This approach contrasts with full graph counterparts, leading to significant efficiency gains by reducing redundant computation. For instance, while the best full planar testing algorithm is O(n) [30], its fastest known incremental test has amortized running time of ((a(q.) n)), where q is the total number of operations (edge queries and insertions), and a denotes the inverse- peerse-Ackermann function [43] (often considered "almost constant" complexity). More details for different properties in Appendix C.
At each reverse step, the denoising network makes predictions for all nodes and pairs of nodes. This results in O(n²) predictions per step. Thus, the complexity of the sampling algorithm of the underlying discrete diffusion model is T In addition, the complexity overhead imposed by the projector is (NN Here, V represents the complexity of the property satisfaction algorithm and N is the total number of times this algorithm applied throughout the reverse process. So, in total, we have On + NV). Our analysis in Appendix C shows that incremental property satisfaction algorithms have notably low complexity. For instance, in cases like acyelicity, lobster components, and maximum degree, we have V = O(Eanded)). Since the projector adds one edge at time, we have V = 0(1. Additionally, since the blocking edge hash table limits us to perform at most one property satisfattion check per newly proposed edge (either we have never tested it or it is already blocked), N corresponds to the total number of different edges proposed by the diffusion model across the whole reverse process. A reasonable assumption is that the model proposes N = O(E)) edges throughout the reverse process, with |E] referring to the number of edges of the clean graph. This is for example true if the model is well trained and predicts the correct graph. Most families of graphs are sparse, meaning that ((E)/n2) - O as n + co. For example, planar and tree graphs can be shown to satisfy EE|n? (1)n). Thus, we necessarily have N < n². For these reasons, we directly find O(NV) < TT) highlighting the minimal overhead imposed by the projector compared to the discrete diffusion model. This explains the low runtime overhead observed for ConStruct, as detailed in Appendix D.3 (9% for graphs of the tested size). Therefore, we can conclude that asymptotically Onn-T + NV)= = On""T), i.e., the projector overhead becomes increasingly negligible relative to the diffusion algorithm itself as the graph size increases, highlighting the scalability of our method.
4 Experiments
In this section, we first explore the flexibility of ConStruct to accommodate different constraints in synthetic unattributed graph datasets. Then, we test its applicability to real-world scenario with digital pathology data.
4.1 Synthetic Graphs
Setup We focus on three synthetic datasets with different structural properties: the planar dataset [54], composed of planar and connected graphs; the tree dataset [7], composed of con- nected graphs without cycles (tree graph); and the lobster dataset [46], composed of connected graphs without cycles, where no node more than 2 hops away from a backbone path (lobster graph). We follow the splits originally proposed for each of the datasets: 80% of the graphs are used in the training set and the remaining 20% are allocated to the test set. We use 20% of the train set as validation set. Statistics of these datasets are shown in Appendix E. As the graphs in these datasets are unattributed, we can specifically isolate ConStruct's capability of incorporating structural information in comparison to previously proposed methods, which are described in Appendix E.2. From here on, we use DiGress+ to denote the DiGress model with the added extra features described in Appendix A. and HSpectre to refer to the model proposed by Bergmeister et al. [7].
Regarding performance metrics, we follow the evaluation procedures from Martinkus al. [54]. We assess how close the distributions of different graph statistics computed from the generated and test sets are. To accomplish that, we compute the Maximum Mean Discrepancy (MMD)² for the node degrees (Deg.), clustering coefficients (Clus.), orbit count (Orbit), eigenvalues of the normalized graph Laplacian (Spec.), and statisties from wavelet graph transform (Wavelet). To summarize this set of metrics, we compute the ratios against the corresponding metrics from the training set and then average them (Ratio). We also compute the proportion of generated graphs that are non-isooorphic to each other (Unique), the proportion that are non-isomorphic to any graph in the training set (Novel),
"To align with previous literature, we actually compute MMD?
7

---

Table 1: Graph generation performance synthetic graphs. We present the results over five sampling runs of 100 generated graphs each, in the format mean + standard error of the mean. The remaining values retrieved from Bergmeister et al. [7] for the planar and tree datasets, and from Dai et al. [14] and Jang et al. [34] for the lobster dataset. For the average ratio computation, we follow [7] and do not consider the metrics whose train set MMD is O. We recompute the train set MMDs according
to our splits but, for fairness, in the retrieved methods the average ratio metric is not recomputed.
Planar Datssnt
Model
Deg
Clus.
OrNt
Spec.
Waveler
Rati
Valid
Unqque
Novel
V.U.N.
Property 1
Trail set
0.0002
0.0310
0,0025
0.0055
0,0012
1.0
100)
100
0.0
0.0
100
GrapMRNN (87)
0.0499
0.277M
1.2545
0.9499
0.1014
400.3
0.0
1(0)
1(0)
0.0
SPECTRE 146]
0.3426
0,0039
0.0019
35.0
0.0755
0.0012
0/0159
0.007
5.1
77.5
77.5
EDXGE
0.766
0.3229
0.7737
0.0257
0.3627
431.4
0.0
100
00251
0.2590
0,5813
019664
0.3314
251.9
0.0
100
100
19033 [14]
00000
0.0070
0,0967
0.0105
0,005
16.0
62.5
35.0
42.5
Gruph [24]
0.0325
0.2106
0.4236
0.0430
0.0959
210.3
7.5
100
100
75
EtSpectre tose shoo [7]
0.0003
0.0245
0,6006
3.0104
0.0030
1.7
67.5
100
100
67.5
p8ppor [7]
00005
0.0626
BX001 7
0,0075
0.0013
2.1
95.0
100
100
95.0
INGroo+
0.0005 MU0EI
0,04 300
0. 0.0048 45x0
0.0055 M100L
0.0020 ac a01
3.6 m13
+13
100.0 WM
100.0 mm)
76.4 4..
764 +1
ConSSima
0.0003 -000
0.0401
0,0004 -000
0.063 WI00:
0,0009 mc
1.1
10000
100.0 m06
-10
100,0
1000
Trait
0.000)
0,0000
0,0000
0,0030
1,0
100
100
GRAN (06)
0.1884
0.0080
0.0199
0,251
0,3274
600.0
0.0
100
100
0.0
EXGiness [79]
0.0001
0.0030
0.0000
0.0113
0.0043
1.5
90.0
100
1100
90.0
EDGGE [00]
0.2675
0.0000
0.7357
0.2677
0.4200
850.7
0.0
7.5
100
0.0
BwR [17]
0.0016
0.1239
0.0033
0.9490
0.0888
11.4
0.0
100
100
0.0
19035 [14)
0.004
0.0000
03000
0.0119
00058
5.2
190
57.5
3000
75.0
Grnghhien [24]
00005
0.0000
010000
0,I11
0.0122
51.3
95.0
100
100
95.0
HSSpecue (one abo0 [7]
0.0004
0.0000
0.0000
0,0280
0:0055
2.1
82.5
100
HSppctu [7]
0.0003
0.0000
0,0000
0,0117
0.0147
100
0.0002
0.0000
0.0032
1,3
10000
97,0
ConStret
DU0003
0,0000
0,0034
83,0
100.0
Lobster Dutaeet
Triis set
0.0002
0.0000
0,0000
0.0070
0.0070
1.0
100
100
0.0
0.0
100
GragMRNN (87)
0.000
0.000
0.000
100
(46]
0.018
0.000
0.001
0.027
88.0
GruphGess [24]
0.040
0.247
GrughGeee Redex [5]
BIGG [14)
0.000
0.000
0.000
0.009
100
GDSS
0.117
0.002
0.149
18.2
100
Rell [17)
0.516
0.000
01342
100
636
100
63.6
GERI [54]
0.002
01.00
01001
72.7
100
72.7
<72.7
HGGT [35]
0.005
0,000
0.015
DiGiesss (79)
0.021
01,000
0.004
51.5
100
100
54.5
DXGros+
0.0005 JU0E:
0,0000 40 300
0.0000 4sro
0.0144 momms
0.0093 sc.
1.5 a1
70.0
as.0
96.6 4s5
60.4 a1z
76.8.i
Contiinac
0.8003 410E1
0.0000 40:000
0,0000
401011
0.003 HID
0,0074 HEMI
1,3-00
85.8-7
406
47.0
83.
1000
and the proportion of generated graphs that are valid (Valid). Graphs are considered valid if they planar and connected, trees, or lobster graphs, when the generative model is trained on the planar, tree, or lobster dataset, respectively. We merge these three metrics through the proportion of generated graphs that are simultaneously valid, unique and novel (V.U.N.).
Constraining Criteria Various constraining criteria are chosen for ConStruct according to the structural properties of each dataset. For the planar dataset, we use planarity. For the tree dataset, we impose the absence of cycles. For the lobster dataset, we constrain the graph domain to those graphs whose connected components are lobsters. To check to what extent these criteria are verified by the compared methods, we compute the proportion of generated graphs that comply with the selected constraining criterion of the corresponding dataset (listed under the "Property" column in Table I),
Graph Generation Performance We present the results in Table 1. For the planar dataset, ConStruct achieves nearly optimal performance, clearly outperforming all other methods. It is actually the first method to achieve 100% V.U.N., indicating state-of-the-art performance. Moreover, in terms of average ratio, it clearly outperforms all other methods, with the average ratio approaching 1, suggesting high sample quality. Regarding the lobster dataset, ConStruct exhibits a similar trend, demonstrating superior performance compared to DiGress+. It leads to state-of-the-ant results in both average ratio and V.U.N. metrics. The lower novelty and uniqueness values (< (<100%) are attributed to the dataset's 's smaller size. fact, we train both models on 64 examples (80% of the train set) while generating 100 graphs in each run. Conversely, for the tree dataset, ConStruct is outperformed by DiGress+ due to the marginally lower expressivity of the edge-absorbing noise model for this particular case (see Appendix H.1 for details). As a sanity check, we observe that for all three datasets, ConStruct ensures the constraining property for all generated graphs. However, the validity values are below 100% (except for planar) since connectedness of the generated graph is not guaranteed. In
8

---

Table 2: Graph generation performance digital pathology graphs. We present the results for each method over five sampling runs of 100 generated graphs each, in the format mean + standard error of the mean.
Law TIS Daisert
Model
Raiio
Cora.1 1
Planar 1
VU.N.1
x(0)
<[]]-
H1311
TLS Valid
Toan
0.0023
0,0000
0.0000
0.0000
0,0000
0.0000
100
Reeclin (53)
104.6
-0.
0,6256
0:2350
0.0000
0.0010
Graplelen (24)
212.7
0.7354
0.1880 scae
0.0470
0,0000
0,0000
BICG [14)
152.0
99.5
23.3.M
0.6184
0.1410
0,0470
IU0620
0.0470
0,0070
SPECT
427.0
05.3
51.2
0.20
0,0000
010000
010000
(100000
0,0000
DiGrew+
4.9
95.0
19.
18.6 a13
0,7306 wndin
0,1410
0.0030 22/00
1.0000
0.0000
0,0000
15.6
ConSimet
95.4 203
100.0
96.4 203
0.0781 uoi
0,2350
20:00
019900 J008N
TU0000 (0080
0,0000
20.000
0,0000 20/000
96.2 2t?
High 1L.5 Desaset
0,4512
0.6395
0.7770
100
Baseline Lx]]
st3
storm
559.1
100.0
48.1
0.3311
0,3620
0.4613
0,7500
0.7523
BIGG [14]
307.7
0.3706
0.4850
0.5970
0,7484
0.7515
SPEC
938.1
-1.3-11
0.0-m0
0.0-00
0,5190mim
0. 0.3585
0-4015 samma
0.9130
0.9059
400177
0.6804
0.0
10.5
40x8
84
7.
0.3194 mion
0, 0.3888-
0.3508 4p10s
D 0.4878
0.6254 -0res
0.6887
CenSiimet
6.6
99.
10000 m
998 m3
0,3778 mose
0,5437 scars
0:3799 s00117
0.5 muress
0.678
-03177
0.6798 sea
88.0 a1
general, this property is not ensured by one-shot models and cannot be included as a constraining property since it is not edge-deletion invariant.
4.2 Digital Pathology Cell Graphs
Setup In the next set of experiments, we explore digital pathology data. Due to the their natural representation of relational data, graphs are widely used capture spatial biological dependencies from tissue images, We focus on cell graphs, whose nodes represent biological cells and edges serve as proxies for local cell-cell interactions. We build these structures from the genomic and clinical data available from the Molecular Taxonomy of Breast Cancer International Consortium (METABRIC) molecular dataset [13, 66, 15]. Each node is attributed with one of the nine possible phenotypes, which extensively characterizes a cell both anatomically and physiologically (more details in Appendix F.2). Regarding edges, we followed the typical procedure for cell graphs in digital pathology [36, 35, 2, 82]: first we employ Delaunay triangulation on the cell positions to construct the graphs, followed by edge thresholding to discard long edges. Our focus lies on generating biologically meaningful Tertiary Lymphoid Structures (TLSs), further described in Appendix F.3. Thus, we extract non-overlapping 4-hop subgraphs centered at nodes whose class is "B" from the whole-slide graphs In terms of dimensionality, we obtain graphs with b = 9, corresponding to the 9 phenotypes detailed in Appendix F.2, and e 1. We explore two datasets: one comprising graphs with high TLS content and another consisting of graphs with low TLS content, based domain-speciff metrics (see below). We provide their statistics in Appendix F.4. We open-source both of them, representing to the best of our knowledge the first open-source digital pathology datasets specifically tailored for graph generation. For the sake of comparison, besides ConStruct and DiGress+, we implement a non-deep learning baseline method proposed in [52] for this setting, which essentially captures 1-hop dependencies of cell graphs (see Appendix F.5). Additionally, we run BiGG [14], GraphGen [24], and SPECTRE [54]. These are the methods that, besides DiGress, can handle attributed graphs and attain non-zero V.U.N, for the planar dataset in Table 1, which we consider a proxy for performance in the digital pathology datasets due to the structural similarities (i.e., planarity) between the datasets.
Metries The TLS embedding, K [Ko..... KG] E 1R6 has been proposed to quantify the TLS content in a cell graph [69, 52]. See Appendix F33 for more details. Based on this metric, we define a graph G to contain low TLS content if k2 (G) < 0.05 and high TLS content if kzz(G) > 0.05 [52]. To evaluate the generative performance, we adopt the average ratio for structural graph statistics (Ratio) and V.U.N. metries used in Section 4.1. Here consider planar and connected graph valid graph. Thus, we explicitly present the proportion of generated graphs that are connected (Conn.) and (Planar). Furthermore, for biologically meaningful evaluation of the generated cell graphs, the domain metrics. We report the MMD between the distributions of the components of k. We also consider the proportion of graphs that are planar, connected, and verify the low or high TLS content condition (TLS Valid), depending on the train set used.
Constraining criterion We use graph planarity as target structural property for ConStruct, as cell graphs are extracted from tissue slides using Delaunay triangulation, thus necessarily planar.

---

Results ConStruct outperforms all baselines across all summary evaluation metrics (shown in light gray in Table 2) for cell graph generation on both datasets. Unlike the synthetic datasets, here the structural distribution is conditioned on the node types, which is inherently a more complex task. This complexity contributes to the poor performance of the several unconstrained models. Constraining the edge generation process allows to significantly alleviate this modelling complexity, highlighting the benefits of ConStruct in such scenarios. We emphasize the substantial improvement in the V.U.N. of the generated graphs, with values approaching 100% using our framework, which aligns with the main motivation behind the proposed method. Interestingly, it also promotes the generation of more connected graphs. Finally, the I-hop baseline model, while capturing the node type dependencies to some extent, as illustrated by the MMD on the components of K, completely fails to capture structure-based dependencies.
Additionally, we carry out some experiments for molecular datasets in Appendix G: we explore the utilization of planarity for constrained molecular generation and showcase how ConStruct can be used for controlled generation. Finally, we explore fikelihood-base variants of ConStruct, as well as some ablations to the projector in Appendix H.
5 Limitations and Future Directions
In our work, we cover edge-deletion invariant properties. However, ConStruct can be easily extended to also handle adge-insertion invariant properties (i.e., properties that hold upon edge insertion). This extension can be useful in domains where constraints such as having at least n cycles in a graph are important. To achieve this, we can simply "invert" the proposed framework: design the transition matrices with the absorbing state an existing edge state (instead of the no-edge state) and a projector that removes edges progressively (instead of inserting them) while conserving the desired property.
In the particular context of molecular generation, Appendix G illustrates that, while purely structural constraints can guide the generation of molecules with specific structural properties (c.g., acyclicity), for general properties shared by all molecules (c.g.. planarity) they are too loose. In contrast, autoregressive models thrive in such setting due to the possibility of molecular node ordering (e.g.. via canonical SMILES) and the efficient incorporation of joint node-edge constraints (e.g., valency). Therefore, although it consists of fundamentally different setting than the one considered in this paper, incorporating joint node-edge constraints into ConStruct represents an exciting future direction.
Additionally, the induced sparsity created by the edge-absorbing noise model presents opportunities for further exploitation. By leveraging this sparsity. future extensions of ConStruct could enhance sampling efficiency and improve the underlying diffusion model's 's scalability for generating larger graphs.
6 Conclusion
In this paper, we introduced ConStruct, a framework that allows to integrate domain knowledge via structural constraints into graph diffusion models. By constraining the diffusion process based on a diverse set of geometric properties, we enable the generation of realistic graphs in scenarios with lim- ited data. To accomplish that, we leverage an edge-absorbing noise model and a projector operator to ensure that both the forward and reverse processes preserve the sampled graphs within the constrained domain and, thus, maintain their validity. Despite its algorithmic simplicity, our approach overcomes the arbitrarily hard problem of projecting given graph into combinatorial subspace in an efficient and theoretically grounded manner. Through several experiments on benchmark datasets, we show- case the versatility of ConStruct across various structural constraints. For example, in digital pathology datasets, our method outperforms existing approaches, bringing the validity of the generated graphs close to 100%. Overall, ConStruct opens new avenues for integrating domain-specifee knowledge into graph generative models, thereby paving the way for their application in real-world scenarios.
Acknowledgements
We thank Cédric Vincent-Cual Cuaz, Nikolaos Dimitriadis, Vaishnavi Subramanian, Yiming Qin, Sevda Ögüt, and Laura Toni for helpful discussions and feedback. We also thank Andreas Bergmeister and Yunhui Jang for helping set up the code to reproduce their experiments.
10

---

References
[1] Bijaya Adhikari, Bryan Lewis, Anil Vullikanti, José Mauricio Jiménez, and Aditya Prakash. Fast and near-optimal monitoring for healthcare acquired infection outbreaks. In PLoS Compu- tational Biology, 2019. 1,5
[2] David Ahmedt-Aristizabal. Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson. A survey graph-based deep learning for computational histopathology. In Computerized Medical Imaging and Graphics, 2022. 9,
[3] Rohan Asthana, Joschua Conrad, Youssef Dawoud, Maurits Ortmanns, and Vasileios Bela- giannis. Multi-conditioned graph diffusion for neural architecture search. In Transactions on Machine Learning Research (TMLR), 2024. 5
[4] Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Struc- tured denoising diffusion models discrete state-spaces. In Advances in Neural Information Processing Systems (NeurIPS), 2021. 5, 33
[5] Davide Bacciu and Marco Podda. Graphgen-redux, A fast and lightweight recurrent model for labeled graph generation. In International Joint Conference on Neural Networks (IJCNN) 2021. 8, 26
[6] Kaustav Bera, Kurt A Schalper, David L Rimm, Vamsidhar Velcheti, and Anant Madabhushi. Artificial intelligence in digital pathology - new tools for diagnosis and precision oncology. In Nature Reviews Clinical Oncology, 2019. 27
[7] Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Efficient and scalable graph generation through iterative local expansion. In International Conference on Learning Representations (ICLR), 2023. 2, 3, 7, 8, 24, 26
[8] Sandeep Bhatt and Frank Thomson Leighton. framework for solving vlsi graph layout problems. In Journal of Computer and System Sciences, 1984. 5
[9] Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain C Vaucher. Guacamol: benchmark- ing models for de novo molecular design. In Journal of Chemical Information and Modeling, 2019. 31
[10] Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. In International Conference on Machine Learning (ICMI),, 2023. 3, 26
[11] Markus Chimani, Ivo Hedtke, and Tilo Wiedera. Exact algorithms for the maximum planar subgraph problem: New models and experiments. In Journal of Experimental Algorithmics (JEA), 2019.
[12] Jacob Christopher, Stephen Baek, and Ferdinando Fioretto. Constrained synthesis with projected diffusion models. ArXiv, 2024. https: bttps://arxits org/ htg/abb//4400 03559. 3
[13] Christina Curtis, Sohrab P Shah, Suet-Feung Chin, Gulisa Turashvili. Oscar M Rueda, Mark J Dunning, Doug Speed, Andy Lynch, Shamith Samarajiwa, Yinyin Yuan, et al. The genomic and transcriptomic architecture of 2,000 breast tumours reveals novel subgroups. In Nature, 2012. 9, 27
[14] Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International Conference on Machine Learning (ICML), 2020.
3, 8, 9, 26
[15] Esther Danenberg, Helen Bardwell, Vito RT Zanotelli, Elena Provenzano, Suet-Feung Chin, Oscar M Rueda, Andrew Green, Emad Rakha, Samuel Aparicio, Ian Ellis, et al. Breast tumor microenvironment structures are associated with genomic features and clinical outcome. In Nature Genetics, 2022. 9, 27
[16] Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular grap. International Conference on Machine Learning (ICML) Workshops, 2018.
11

---

[17] Nathaniel Lee Diamant, Alex M Tseng, Kangway V Chuang, Tommaso Biancalani, and Gabriele Scalia. Improving graph generation by restricting graph bandwidth. International Conference on Machine Learning (ICML), 2023. 8, 26
[18] Carie-Ca Dieu-Nosjean, Nicolas A Giraldo, Hélène Kaplon, Claire Germain, Wolf Her- man Fridman, and Catherine anti-tumor responses in human cancers. In Immunological Reviews, 2016. 2, 27
Tertiary lymphoid structures, drivers of the
[19] Radoslav Dimitrov, Zeyang Zhao, Ralph Abboud, and Ismail Ceylan. Plane: Representation learning over planar graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2024. 31,32 32
[20] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Conference on Artificial Intelligence Workshops, 2020. 17
[21] Kianoush Falahkheirkhah, Alex Xijie Lu, David Alvarez-Melis, and Grace Huynh. Domain adaptation using optimal transport for invariant learning using histopathology datasets. In Medical Imaging with Deep Learning, 2024. 27
[22] Nic Fishman, Leo Klarner, Valentin De Bortoli, Emile Mathieu, and Michael Hutchinson. Diffusion models for constrained domains. In Transactions on Machine Learning Research (TMLR), 2023. 4
[23] Nic Fishman, Leo Klarner, Emile Mathieu, Michael Hutchinson, and Valentin De Bortoli. Metropolis sampling for constrained diffusion models. In Advances in Neural Information Processing Systems (NeurIPS), 2023. 4
[24] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain-agnostic labeled graph generation. In The Web Conference, 2020. 8, 9, 26
[25] Ryan Gregory. Understanding evolutionary trees. In Evolution: Education and Outreach,
2008. 5
[26] Cigdem Gunduz, Bülent Yener, and S Humayun Gultekin. The cell graphs of cancer. In Bioinformatics, 2004. 1, 27
[27] Kilian Konstantin Haefeli, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Diffusion models for graphs benefit from discrete state spaces. Learning Graphs Conference (LOG) Extended Abstracts, 2022. 2, 3,
[28] Beth A Helmink, Sangeetha M Reddy, Jianjun Gao, Shaojun Zhang, Rafet Başar, Rohit Thakur, Keren Yizhak. Moshe Sade-Feldman Jorge M Blando, Guangehun Han, Vancheswaran Gopalakrishnan, Yuanxin Xi, Hao Zhao, Rodabe N Amaria, Hussein Tawbi, Alexandria Cogdill, Wenbin Liu, Valerie S LeBleu, Fernanda G Kugeratski, Sapna Pradyuman Patel, Michael Davies, Patrick Hwu, Jeffrey E. Lee, Jeffrey Gershenwald, Anthony Lucci, Reetak- shi Arora, Scott E Woodman, Emily Z. Keung, Pierre olivier Gaudreau, Alexandre Reuben, Christine N Spencer, Elizabeth M Burton, Lauren Haydu, Alexander J Lazar, Roberta Zapas- sodi, Courtney W Hudgens, Debora A Ledesma. Sufey Ong. Michael Bailey, Sarah Warren, Disha Rao, Oscar Krijgsman, Elisa A Rozeman, Daniel S Peeper, Christian Blank, Ton M Schumacher, Lisa H Butterfield, Monika A Zelazowska, Kevin M McBride, Raghu Kalluri, James P Allison, Florent Petitprez, Wolf Herman Fridman. Catherine Sautès-Fridman hen, Katayoun Rezvani, Padmanee Sharma, Michael T Tetzlaff, Linghua Wang, and Jennifer A Wargo. B cells and tertiary lymphoid structures promote immunotherapy response. In Nature, 2020. 2, 27
Fridman, Nir Haco-
[29] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[30] John Hopcroft and Robert Tarjan. Efficient planarity testing. In Journal of the ACM (JACM), 1974. 7, 23
[31] Han Huang. Leilei Sun, Bowen Du, and Weifeng Lv. Conditional diffusion based on discrete graph structures for molecular graph generation. AAAI Conference on Artificial Intelligence, 2023. 3
12

---

[32] Hankyu Jang, Samuel Justice, Philip M Polgreen, Alberto M Segre, Daniel K Sewell, and Sriram V Pemmaraju. Evaluating architectural changes alter pathogen dynamics in a dialysis unit: for the edc mind-healthcare group. In IEEF/ACM International Conference on Advances Social Networks Analysis and Mining (ASONAM), 2019. 1,5
[33] Yunhui Jang, Dongwoo Kim, and Sungsoo Ahn. Graph generation with K2-trees. In Interna- tional Conference on Learning Representations (ICLR), 2023. 8, 26
[34] Yunhui Jang, Seul Lee, and Sungsoo Ahn. A simple and scalable representation for graph generation. In International Conference on Learning Representations (ICLR), 2023. 8, 26
[35] Guillaume Jaume, Pushpak Pati, Behzad Bozorgtabar, Antonio Foncubierta-Rodrigee Florinda Feroce, Anna Maria Anniciello, Tilman T Rau, Jean-Philippe Thiran, Maria Gabrani, and Orcun Goksel. Quantifying explainers of graph neural networks in computational pathology. In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020. 9, 27
(36] Guillaume Jaume, Pushpak Pati, Valentin Anklin, Antonio Foncubierta, and Maria Gabrani. Histocartography: toolkit for graph analytics in digital pathology. International Conference on Medical Image Computing and Computer-Assister Intervention (MICCAI) Workshops, 2021.
5, 27 27
[37] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning (ICML), 2018. 3
[38] Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International Conference Machine Learning (ICML), 2022. 3, 4, 8, 26
[39] Laya Jose, Sidong Liu, Carlo Russo, Annemarie Nadort, and Antonio Di leva. Generative adversarial networks in digital pathology and histopathological image processing: review. In Journal of Puthology Informatics, 2021. 27
[40] Thomas N Kipf and Max Welling. Variational graph auto-encoders. ArXiv, 2016. https: wwwp///////b/.reeeee
3
[41] 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), 2023. 2,3
[42] Igor Krawczuk, Pedro Abranches, Andreas Loukas, and Volkan Cevher. Gg-gan: A geomet- ric graph generative adversarial network. OpenReview, 2020. https://openreviee net/ forum?id=ql ixx3xiiixxx3xxx1o... 3
[43] Johannes A La Poutré. Alpha-algorithms for incremental planarity testing (extended abstract).
In ACM symposium on Theory of Computing, 1994. 7, 23
[44] Hee Jin Lee, In Ah Park, In Hye Song. Su-Jin Shin, Joo Young Kim, Jong Han Yu, and Gyungyub Gong, Tertiary lymphoid structures: prognostic significance and relationship with tumour- infiltrating lymphocytes triple-negative breast cancer. Journal of Clinical Pathology, 2015. 2.
[45] Xujia Li, Yuan Li, Xueying Mo, Hebing Xiao, Yanyan Shen, and Lei Chen. Diga: Guided diffusion model for graph recovery in anti-money laundering. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
[46] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in neural information processing systems (NeurlPS), 2019. 3, 7, 8, 24, 26
[47] Phillip Lippe and Efstratios Gavves. Categorical normalizing flows via continuous transforma- tions. In International Conference on Learning Representations (ICLR), 2021. 3
13

---

[48] Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances in Neural Information Processing Systems (NeurIPS), 2019. 3
[49] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations (ICLR), 2018. 24
[50] Aaron Lou and Stefano Ermon. Reflected diffusion models. In International Conference on Machine Learning (ICML), 2023.
[51] Youzhi Luo, Keqiang Yan, and Shuiwang Ji. Graphdf: A discrete flow model for molecular graph generation. In International Conference on Machine Learning (ICML), 2021. 3
[52] Manuel Madeira, Dorina Thanou, and Pascal Frossard. Tertiary lymphoid structures generation through graph-based diffusion. In International Conference on Medical Image Computing and Computer-Assisted Intervention (MICCAI) Workshops, 2023. 2, 9, 27, 28, 29
[53] Kaushalya Madhawa, Katushiko Ishiguro, Kosuke Nakago, and Motoki Abe. Graphnvp: An invertible flow model for generating molecular graphs. ArXiv, 2019. abs/1905. 11600. 3
org/
[54] 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 (ICML), 2022. 3, 7, 8, 9, 24, 26
[55] Rocío Mercado, Tobias Rastemo, Edvard Lindelöf, Günter Klambauer, Ola Engkvist, Hongming Chen, and Esben Jannik Bjerrum. Graph networks for molecular design. In Machine Learning: Science and Technology, 2021. 1
[56] Puria Azadi Moghadam, Sanne Van Dalen, Karina Chornenka Martin, Jochen K Lennerz. Stephen S F Yip. Hossein Shahrabi Farahani, and Ali Bashashati. A morphology focused diffusion probabilistic model for synthesis of histopathology images. In IEEE/CVF Winter Conference on Applications of Computer Vision (WACV), 2022. 27
[57] Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI Conference on Artificial Intelligence, 2019. 17
[58] Luis Erazo, Janet L Rhodes, Valentine Marion, and Roslyn A Kemp. Tertiary lymphoid structures in cancer considerations for patient prognosis. In Cellular & MMoleularr Immunology, 2020. 2, 27
[59] Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International Conference on Machine Learning (ICML), 2021.
[60] Chenhao NIu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[61] Costantino Pitzalis, Gareth W Jones, Michele Bombardieri, and Simon A Jones. Ectopic lymphoid- structures in infection, cancer and autoimmunity, In Nature Reviews Immunology. 2014. 27
[62] Daniil Polykovskiy, Alexander Zhebrak. Benjamin Sanchez-Lengeling Sergey Golovanov. Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, al. Molecular sets (moses): benchmarking platform for molecular generation models. In Frontiers in Pharmacology, 2020. 31
[63] Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Gunter Klambauer. Fréchet chemnet distance: a metric for generative models for molecules in drug discovery. In Journal of Chemical Information and Modeling, 2018. 31, 32
[64] Yiming Qin, Clement Vignac, and Pascal Frossard. Sparse training discrete diffusion models for graph generation. ArXiv, 2023, https://arxta: org/ wwg//bs/////eeooeeoeooooeee abs/2311 02142. 2, 4, 17
14

---

[65] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations (ICLR), 2018. 24
[66] Oscar M Rueda, Stephen-John Sammut, Jose A Scoane, Suet-Feung Chin, Jennifer L Caswell- Jin, Maurizio Callari, Rajbir Batra, Bernard Pereira, Alejandra Bruna, Raza Ali, et al. Dynamics of breast-cancer relapse reveal late-recurring er-positive genomic subgroups. In Nature, 2019. 9, 27
[67] Pedro Sanchez, Xiao Liu, Alison Q'Neeil and Sotirios A Tsaftaris. Diffusion models for causal discovery via topological ordering. In International Conference on Learning Representations (ICLR), 2022. 5
[68] Alberto Sanfeliu and King-Sun Fu. A distance measure between attributed relational graphs for pattern recognition. In IEEE transactions systems, man, and cybernetics, 1983, 6, 19
[69] Nadine S Schaadt, Ralf Schönmeyer, Germain Forestier, Nicolas Bricu, Peter Braubach, Katha- rina Nekolla, Michael Keyer-Hermann, and Friedrich Feuerhake. Graph-based description of tertiary lymphoid organs at single-cell level. In Public Library of Science (PLoS) Computational Biology, 2020. 2, 9, 27, 28
[70] Claire Seibold and Hannah L Callender. Modeling epidemics on a regular tree graph. In Letters
in Biomathematics, 2016. 5
[71] Ahmed M Serag, Adrian Ion-Margineanu, Hammad Qureshi, Ryan McMillan, Marie- Judith Saint Martin, James Diamond, Paul G O'Reilly, and Peter Hamilton. Translational ai and deep learning in diagnostic pathology. In Frontiers in Medicine, 2019. 27
[72] Kartik Sharma, Srijan Kumar, and Rakshit Trivedi. Plug-and-play controllable graph generation with diffusion models. In International Conference on Machine Learning (ICML), 2024.
[73] Howard E Simmons III and John E Maggio. Synthesis of the first topologically non-planar molecule. In Tetrahedron Letters, 1981.
[74] Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. In International Conference on Artificial Neural Networks (ICANN), 2018.
[75] Jascha Sohh-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning (ICML), 2015.
[76] Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
[77] Alex M Tseng, Nathaniel Diamant, Tommaso Biancalani, and Gabriele Scalia. Complex preferences for different convergent priors in discrete graph diffusion. International Conference on Machine Learning (ICML) Workshops, 2023. 33
[78] Clement Vignac and Pascal Frossard. Top-n: Equivariant set and graph generation without exchangeability. In International Conference on Learning Representations (ICLR), 2021. 3, 32
[79] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. In International Conference Machine Learning (ICMI), 2022. 2, 3, 4, 5, 8, 17, 26, 31, 32
[80] Clément Vignac, Nagham Osman, Laura Toni, and Pascal Frossard. Midi: Mixed graph and 3d denoising diffusion for molecule generation. In Joint European Conference Machine Learning and Knowledge Discovery in Databases (ECMI/PKDD), 2023. 31
[81] Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. In Chemical Science, 2018. 31
15

---

[82] Zhenqin Wu, Alexandro E Trevino, Eric Wu, Kyle Swanson, Honesty J Kim, H Blaize D' D'Angio, Ryan Preska, Gregory W Charville, Piero D Dalerba, Ann Marie Egloff, et al. Graph deep learning for the characterization of tumour microenvironments from spatial protein profiles in tissue specimens. In Nature Biomedical Engineering, 2022. 27
[83] Feng Xie and David Levinson. Topological evolution of surface transportation networks. In Computers, Environment and Urban Systems, 2007. 5
[84] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations (ICLR), 2019. 17
[85] Qi Yan, Zhengyang Liang. Yang Song, Renjie Liao, and Lele Wang. Swingnn: Rethinking permutation invariance in diffusion models for graph generation. Transactions on Machine Learning Research (TMLR), 2024. 3
[86] Kai Yi, Bingxin Zhou, Yiqing Shen, Pietro Liò, and Yuguang Wang. Graph denoising diffusion for inverse protein folding. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2024. 1
[87] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrmn: Generat- ing realistic graphs with deep auto-regressive models. In International Conference on Machine Learning (ICML). PMLR, 2018. 3, 26
[88] Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: A variational autoencoder for directed acyclic graphs. In Advances in neural information processing systems (NeurIPS), 2019. 5
16

---

A
Graph Discrete Diffusion Model
In this section, we further detail the design of the graph discrete diffusion model used to illustrate the constraining framework of ConStruct.
A.1 Training Algorithm
The denoising neural network is trained using the cross-entropy loss between its predicted probabilities for each node and edge types, De = (frx fff) and the actual node and edge types of a clean graph, G (X, E):
L(D G) CE (f*, X) + CE E),
(4)
where À is an hyperparameter that is tuned to balance both loss terms.
As shown by Vignac et al. [79]. the loss in Equation (4) is node permutation invariant. Thus, if we also consider an equivariant architecture, the diffusion model is endowed of the desired equivariance properties, allowing the model to dodge the node ordering sensitivity from which, for example, autoregressive models suffer. For this reason, we adopt a Graph Neural Network, GNNg, as the denoising neural network of our diffusion model. In particular, we employ the exact same denoising network architecture of DiGress [79], a Graph Transformer [20].
Importantly, the edge-absorbing noise model used in ConStruct increases graph sparsity throughout the forward trajectory. Consequently, beyond the distribution preserving guarantees, it also allows for the efficient computation of cxtra features on the noisy graphs that otherwise the GNN, would not be able to capture. Following Vignac et al. [79], these are fed as supplementary input to the denoising network (see Algorithm I and Algorithm 3). further enhancing its expressivity beyond the well-known limited representational power of GNN architectures [84, 57]. More coneretely, besides the spectral (eigenvalues and eigenvectors of the Laplacian) and structural (number of cycles) features from DiGress, we also consider some additional features. We add as graph features the degree distribution and the node and edge type distributions. While the former enhances the positional information within the graph, the latter helps making more explicit to the model the prevalence of each class in the dataset. Additionally. we add auxiliary structural encodings to edges to boost edge label prediction. We compute the Adamic-Ade index to aggregate local neighborhood information and the shortest distance between nodes to encode node interactions. Due to computational limitations, only consider information within 10-hop radius for these computations. These additional features were previously proposed by Qin et al. [64].
Provided such loss function and denoising neural network architecture, the necessary elements are in place for the training of the diffusion model, which is defined in Algorithm 1.
Algorithm 1: Training Algorithm for Graph Discrete Diffusion Model
Input: Graph dataset D
repeat
Sample G - () D:
Sample ~ u(1...., T):
Sample G ~ XQ's x EQ'
5
h - (G",t))
// Compute extra features
6x 6. + GNNo(G",.
loss + CE(PX, X) + CE E);
optimizer. sloss:
until convergence of GNN:;
A.2 Parameterization of the Reverse Process
The distribution pe (et (G') fully defines the reverse process. Under an independence assumption between nodes and edges, this distribution can be modelled as:
( (Gt
II pa(a)
II ISiJ5a
(5)
15i5n
17

---

To compute each of these terms, we use the GNN predictions through the following marginalization.
po pa (G*) = Σ Epo G²) D (x),
(6)
zEd
where p. (a:) denotes the GNN, predicted probability of node i being of type Similarly, for the edges have Pa Po = Eees Po e, G*) p. (c). To compute the missing term in Equation (6), we equate it to the posterior term of the forward process:
x11 10 x
if q = x) > 0,
pa pa( (
G9)
x
otherwise,
where denotes transposition.
A.3 Sampling Algorithm
In this section, we first introduce the algorithm describing the proposed projector operator in Algo- rithm 2. This projector is employed at each time step to keep the sampled graphs throughout the reverse process within the constrained domain. The full sampling algorithm shown Algorithm
Algorithm 2: Projector
Input: Constraining property P, noisy graph G (X', E²), and candidate graph Gt-1 (X+-1, )t-1)
G ( 1- E*);
E' E E";
// Get candidate edges
repeat
Sample e' ~ E'; if P(G insert(e')) then
G t Gt-l_ insert(e')
// Insert only valid edges
end
E' + E' {et;
until
10 return Gt-1,
Algorithm 3: Sampling Algorithm for Constrained Graph Discrete Diffusion Model
Input: Number of graphs to sample N and constraining property P for i 1 to N do
Sample from the training set distribution;
// Sample number of nodes // Sample from limit distribution
Sample G" qx (n) x qr(n);
for 1 = T to 1 do
h f(G ; xx P + GNNo h);; Gr-1 po
// Compute extra features
// Sample from distribution in Equation (5)
Gt-1 + Projector( Gt-1 1G)):
end
Store G
end
18

---

B Theoretical Analysis
In this section, we theoretically analyse the projector. We start by defining a notion of distance between graphs [68].
Definition B.1. Let G1 and G2 be two unattributed graphs. The graph edit distance with uniform
cost, denoted by GED(G1, G2), is defined as:
GED GG) (c1 (G) ==1
min
Σ c((e)== = min (OL al(er.....ee))
(8)
where E(g1.92) 92) denotes the set of edit paths that convert G1 into G2 (up to isomorphism), d(e) = a > 0 is the uniform cost of each usual set of elementary graph edit operators and [(e ((x,...,eex) refers to the cardinality of the edit path.
Importantly, in this analysis we choose GED due to its permutation invariance properties. We only define it over unattributed graphs for an objective evaluation as ConStruct only operates the graph structural level. Moreover, as our generative process imposes a fixed number of nodes throughout the whole reverse process, the relevant elementary edits for GED are edge insertion and deletion.
Additionally, we use the notation G 3 G' to denote that G' = (X', E") is a subgraph of G = E) i.e., that up an isomorphism, we have E 3 E' and X X'. For brevity, we slightly abuse notation and also define the union between graph, G = (X, E), and a set of edges, E", to be the graph whose edges result from the union of its edges with those of the set, i.e. GUE' G' (U,EU)), Similarly, we have G E' = G" = E
The next results are organized in the following way: the first theorem proves that for any edge- deletion invariant constraining property (Definition 3.1), our projector can retrieve a graph that results from projection onto the constrained under the GED sense. Then, we prove that when considering acyclicity as target structural property, the projector is guaranteed to output the optimal (projected) samples. We finally show that this second property does not hold for all edge-deletion invariant properties, giving counter-examples for the cases of planarity, maximum degree and lobster components.
Theorem 1. Let:
be the edge-deletion invariant (Definition 3.1) constraining property of the projector: G be noisy graph obtained at timestep I;
Gt-1 1 be sampled graph from pe (G* |G*), i.e., the one-step denoised candidate graph
directly proposed by the diffusion model when taking G as input;
g' = Projector(P,,C Gt ,G)) be the set of all possible final one-step denoised graph
outputted by ConStruct.
We define (G*,e") any optimal solutions of the following optimization problem:
mingee GED(G'-1 (GG)
min GEC
min (E) 1,G)
al (((e....,,))]
where {G E GIP(G) True, G 3 G with 9 the set of all unattributed graphs. Then, ee)) can be recovered by our projector, i.e. G E E
Proof. If ( E C, the theorem is trivially verified since the output of the projector is directly Gt-1 well as the solution of the minimization problem. Therefore, for the rest of the proof, we only consider the case Čt- & C.
Now, since the reverse process of the diffusion model is an edge insertion process, we have Gt-1 Go U Eeandidate C G Also, we notice that the projector amounts to randomly remove the edges that not in Go from Ćt-1 until we find graph within the constraint set (equivalently, it entails adding as many edges as possible to G while ensuring that the graph remains within the constraint set). Thus, it suffices to prove that for (G*, e²)) necessarily have optimal edit path e* (ci..., et) from -x11 G* exclusively composed of edge deletions. In this case, our projector can necessarily produce G*.
19

---

Let (G', be such a solution, and define G.2 the graph resulting from the 1 first edits e (ei, eÿ) with i < k. We will prove by induction that, for all S i S k, e is only composed of edge deletions such that G C G.
i 1= Since &r-1 & C and Gr-1 5 G³, we have that P(G--1)= False. As P is edge-deletion invariant, inserting any set of edges E to G+-1 implies that
P(G--))= False = P(Č'- = False.
(10)
Therefore, have:
min GED(G (EE) GEC
min GED U Ecandidate: G U E6) (G'U
(11)
min (GC
0x Beandidute \ Eal
(12)
min @eannddia UE Egl (G.UBG)EC
(13)
min (GrURo)EC
UED GED(G U, G U Ea)
(14)
= min CED(G"-UUEEC GEC
(15)
Thus, we conclude that any edge insertions would take us further away from the constraint set. Therefore, ef cannot represent an edge insertion. However, it could still be an edge deletion such that G & G.1 In this case, an extra edge insertion would be necessary to recover G in G which is required since G* G", i.e.,
min GED(G"-1,C0 ,) S min GED(G,, G).
(16)
GEC
GEC
Contrarily, if ej is an edge deletion such that G G we have:
min GED(G" > GEC
min GED(G,, GEC
(17)
since G c G3 C Gt-1 Therefore, we verify the intended property io =rri= 1.
1 1< i < k: We have - & C because 1 False. Otherwise G would be the solution since G C G Hence for any set of inserted edges E,
min GED(G", S min GED G, GEC
(18)
GEC
implying that ez is an edge deletion. By the same token, if G & G then necessarily an extra insertion edit would be necessary to recover G further in G*, so we have again:
min GED(GG--1.G) S min GED G), GEC
(19)
GEC
which, as seen before, is suboptimal. Thus, Et is an edge deletion such that G C C. By noticing that G G", we conclude our proof. This induction shows that only an edit path e* composed of edge deletions such that all intermediate graphs contain G¹ leads an optimal projection w.r.t GED.
Critical analysis of the result in Theorem 1: See Section 3.4 for a critical analysis of this result.
In the following theorem we prove that the projector always picks the solution of the optimization problem, i.e., that any element of g is actually a solution of the optimization problem in Theorem In this proof, we use the concept of connected component of graph, i.e., a subgraph of the given graph in which there is a path between any of its two vertices, but no path exists between any vertex in the subgraph and any vertex outside of it. Therefore, any edge inserted between two nodes in the same connected component leads to a cycle. Importantly, we trivially consider an isolated node as connected component.
Theorem 2. Under the same conditions of Theorem 1, if P returns true for graphs with no cycles, have:
Gt-l argmingec G .G).
20

---

Proof. Following the proof of Theorem 1, if we define again G GH U Bcandidate we have:
min GED ,) GEC
min (G"URG)EC
GED(G' Bcandidute: G U Ea)
min
Beandidate
EGl
[Bcl P(C'UEc)=Iue Ba Ecasdidass
|Bal:
(Fal P(G'UEE) Thie, Fic Fandins))
where the first equality is just change of variables and the second comes from Eeandidate 5 Eg. as shown in Theorem 1. This shows that solution to argmingec GED G) maximizes the number of edges added to G This is general result under the conditions of Theorem 1 and specific for graphs with no cycles. We now want to show that any element of G is a solution to this optimization problem.
We define cCCeandiatee as the number distinct connected components of G' reached by Eaandidate- We remark that the considered graphs all have the same fixed number of nodes. A well-known result for graphs without cycles that, under the provided setting, the maximum number edges from Evandidate that insert is [CCandidatee - 1, ie., sequentially insert edge per pair of separate connected components. Thus, we have:
max
EEcl S [CCanddidate!
[Eal P(G Eg Eceniiioe
On the other hand, the only edges from Ecandidate that the projector rejects the ones creating cycles. This means that the refused edges would not reduce the number of separate connected components, since they would connect vertices already in the same connected component. Thus, for graph we necessarily have:
Grojecter G U Errojector E g
Eppojoccorr 2 [CCaandidate
which tightly matches the upper bound for the optimization problem seen above. Consequently, Eprojection = |CCcandidate and any Gprojector E E is necessarily solution of the optimization problem, i.e.:
G argmingec GED(C ,G)
For other edge-deletion invariant properties, we provide examples of Grojeeter with a different number of edges inserted by the projector, |Fpojeccor in Figure 3. These necessarily counter- examples to what was proved in Theorem Nevertheless, the opposite relation still holds from Theorem 1.
acyclic graphs (G argminigee GED G)).
Overall, Theorem 1, Theorem 2, and the coumtessexample in Figure show that the problem that the projector is addressing is not so trivial such that it can always output the optimal graph in the GED sense for all the edge-deletion invariant properties. Nevertheless, our projector still guaranteed to produce graphs that meet the specified structural constraints.
21

---

Constraint
Gt
1¹-1
Gt-1
Prooeectrr
2
Planar
W
Maximum
Degree
Lobster Components
Figure 3: Examples of different Gt that can be yielded by Projector Gt-1, G*) for given (column "Constraint"), G and (t-1 (columns with the respective name) that lead to the insertion of a different number of edges. For the maximum degree row, the example given considers that the maximum allowed degree is 2. For the column Gt-1, the dashed lines represent the candidate edges. For the column Gt-1, the green lines denote the actually inserted edges by the projector.
22

---

C Incremental Algorithms
As discussed in Section 3.5, utilizing the projector in the edge insertion reverse process (i.c., G G²-l) allows to further enhance efficiency by leveraging incremental algorithms for graph property satisfaction checking. These algorithms avoid performing a full property satisfaction check on the new graph at each timestep. Instead, they assume that the previous graph (i.e., before the new edge was added) already satisfies the target structural property. Incremental algorithms focus on verifying the impact of the newly added edge by updating and checking only the affected parts of smartly designed data structures. In other words, contrary to their full graph counterparts, incremental algorithms allow for property satisfaction checks at a local level. This approach accelerates the property satisfaction checking process by reducing redundant computation.
In this section, we discuss the incremental property satisfaction algorithms for the edge-deletion invariant properties analysed throughout the paper. We also note that due to the combinatorial nature of edge-deletion invariant properties, each property satisfaction algorithm is specific to the property in question. There no general efficient property satisfaction checker for all edge-deletion invariant properties. Consequently, we address each property on case-by-case basis.
Planar The best performing full property satisfaction algorithm known for planarity is (nn) [30],
while its fastest known incremental test has amortized running time of (ga n)) [43] ("almost constant" complexity), where q is the total number of operations (edge queries and insertions), and a denotes the inverse-Ackermann function.
Acyclicity In generic undirected graphs (our case), the usual full tests via DFS/BES have a com- plexity of On + [E]), i.e., the algorithms have to traverse the full graph to reject the existence of any cycle. However, for the dynamic case, given that G has no cycles, we can only check the added edges, Eadded. connect nodes already in the same connected component. This check can be efficiently performed we keep an updated hashtable that maps each node to the index of the connected component it belongs at that iteration (an isolated node is connected component) and another one with all the nodes belonging to each connected component. Whenever there is a new edge proposed, check if the nodes are already in the same connected component. If not, insert the edge and update the two hashtables accordingly; otherwise, we reject the edge since would create cycle. Therefore, the eycle check can be done in ( (Fatte)))
Lobster Components Its global test involves removing twice the leaves of the graph and checking if the remaining connected components are paths. This algorithm has complexity of O(E)) For the incremental version, we can use similar approach to that of the absence of cycles but additionally check if the newly connected node is not more than two hops away from the path in its connected component, as lobster graphs are specific instances of forest graphs. If, again, we keep track of the paths of each connected component in hashtable, still get incremental algorithm of complexity E(ddel))) )) for this property.
Maximum Degree The optimal full property satisfaction algorithm has complexity of ((n) since it has to perform a degree check across all nodes. The incremental version is naturally just a check for nodes that are vertices of Exided- Again, if we keep an updated hashtable with the degree of each node, this can be quickly performed in O ((Eaadeel).
quick
23

---

D Experimental Details
D.1 Training Details
As mentioned in Section 4, we follow the splits originally proposed for each of the unattributed datasets (lobster [46], planar [54], and tree [7]): 80% the graphs are used in the train set and the remaining 20% allocated the test set. We 20% of the train as validation for the lobster dataset, the original splits provided in the open-source code from Liao et al. [46] use the validation In contrast, we follow Martinkus et al. [54]'s protocol, isolating completely the validation samples from the train (again, 20% of the train split). any case, the test splits are coincident between our approach and the one from Liao et al. [46]. For the digital pathology datasets, we follow the same protocol.
We note that
as a subset of the train set, i.e., all the samples in the validation are used train.
These splits and the hyperparameters used for each model are provided in the computational imple- mentation of the paper the default values for each of the experiments. For each configuration, we save the five best models in terms of negative log likelihood and the last one (for ConStruct, we compute the likelihood of the corresponding unconstrained model) and pick the best performing model across those six checkpoints. Regarding the optimizer, we used the AMSGrad [65] version of AdamW [49] with learning rate of 0.0002 and weight decay of le-12 for all the experiments.
D.2 Resources
All experiments were in single Nvidia V100 32Gb GPUs. We present the training times of the diffusion model for each dataset in Table 3.
Table 3: Training times for the diffusion model in different datasets.
Dataset
Training Time (h)
Planar
48
Tree
44
Lobster
50
High TLS
61
Low TLS
QM9
9.5
MOSES
335.5
GuacaMol
502
The baseline model for the digital pathology dataset does not use any GPU. takes 0.6s to train and 2 minutes to sample from. The sampling times for ConStruct can be found in Appendix D.3. As the order magnitude of training times is significantly larger than one of sampling times, Table provides a good estimate of the total computational resources required for this paper.
D.3 Runtimes
A major advantage of our framework is that it does not interfere with the training of the diffusion model, preserving its efficiency. Therefore, there no overburden the training time caused by ConStruct. For this reason, in this section we only analyse the different sampling runtimes. In particular, we track the sampling times DiGress+ and the ones of ConStruct with and without the efficiency boosting components described in Section 3.5 (edge blocking hashtable and incremental property satisfaction algorithm).
Additionally, natural procedure to ensure 100% constraint verification solely using DiGress+ is to first directly perform unconstrained generation and then applying a validation process to filter out the ones that do not verify the constraint. This a posteriori filtering requires a full graph property check, run only once after the graph has been generated but that thus more computationally expensive when compared to their incremental versions employed by ConStruct. The complexity comparison between full graph property check ran only once vs an incremental check for each added edge is property specific. However, the main bottleneck of the posteriori filtering is that it

---

wastes computational resources in case of graph rejection (i.e., in the case of graph not verifying the property, all the resources used in its generation and full graph property checking are wasted) and requires restarting the sampling from zero again with additional property check at the end. Furthermore, this procedure has be performed sequentially, since we can only check the graphs constraint satisfaction after their generation. ConStruct avoids such redundancy and, thus, waste of computation by generating property satisfying graphs by design: throughout the reverse process, we know that the previous graph verified the property, newly added edges (via incremental algorithm) that have not been checked yet (via edge blocking hashtable).
can just check property satisfaction for the
We compare the sampling runtimes of the aforementioned algorithmic variants in the table below. We run this experiment for the tree dataset, where we use acylicity as target structural property. We picked this dataset due to its simpler incremental check, descrihed Appendix
Table Runtimes comparison. We performed five sampling runs for each method and present their results in the format mean & standard eгror of the mean. For each run, we generated 100 graphs. All our experiments were run in a single Nvidia V100 32Gb GPUs. ConStruct [efficient] uses the edge blocking hashtable and the incremental version of the property satisfaction algorithm, while ConStruct [baseline] does not. DiGress+ refers to regular unconstrained generation, while DiGress+ [rejection] applies a posteriori filtering of unconstrained generation until we get the intended amount of graphs.
Dataset
Sampling Time
DiGress+
266.0 40.1
DiGress+ [rejection]
310.7 45.5
ConStruct [efficient]
290.2 40.1
ConStruct [baseline]
349.0 40.3
By implementing the edge blocking hashtable and the incremental checker, we observe a significant efficiency improvement: the additional runtime imposed by ConStruct over the unconstrained setting decreases from 31% to 9%. This trend should hold for other datasets as far as both lookup and update operations in hashtables (O(1) and incremental property checks more efficient than full-graph constraint checks, which is the typical case.
ConStruct also outperforms the posteriori filtering of unconstrained generation. In this case, we used an unconstrained model that generates constraint satisfying properties 97% (DiGress+ in Table of the paper), therefore largely benefitting the unconstrained model. For example, if we considered the digital pathology setting, where we can have only 6.6% (see Table 2, high TLS dataset, DiGress+) of the generated graphs with the unconstrained model satisfying the constraint, the amount of wasted computation would be dramatically larger, implying much worse runtime. In such setting, ConStruct would be approximately 12 times more efficient in generating valid graphs than DiGresst. Additionally, this gap in sampling efficiency may become particularly critical in settings where the amount of generated graphs is much larger, is the for molecular generation (two orders of magnitude greater than in the settings with synthetic datasets, see Appendix G).
25

---

E Synthetic Datasets
In this section, we provide further information about the unattributed synthetic datasets used in Section 4.1.
E.1 Statistics
In Table 5, provide the minimum, maximum, and average number of nodes, minimum, maximum, and average number of edges, and the number of training, validation and test graphs used for each synthetic unattributed dataset.
Table 5: Synthetic dataset statistics. # #rain, # Val and #Test denote the number of graphs considered in the train, validation and test splits, respectively.
Dataset
Min. nodes
Max. nodes
Avg. nodes
Min. edges
Max. edges
Avg. edges
# #'Train
# VVl
# TTTes
Planur
64
64
64
173
181
177.8
128
32
40
Tree
64
64
64
63
63
63
128
32
40
Lobster
11
99
50.2
10
49.2
20
E,2
Compared Methods
In Section 4, we compare ConStruct with several unconstrained graph generative models. We consider:
the two first widely adopted autoregressive models for graph generation, GraphRNN [87]
and GRAN [46];
two spectrally conditioned methods: SPECTRE [54] is a GAN-based approach and HSpec-
[7] consists of iterative local expansion method that takes advantage of a score-based
formulation for intermediate steps;
we also compare the original implementation DiGress [79] without the additional
features described in Appendix A.I;
GraphGen [24] is scalable autoregressive method based on graph canonization through
minimum DFS codes. Importantly, this method is domain- and supports attributed
graphs by default;
GraphGen-Redux [5] improves over GraphGen by jointly modelling the node and edge labels;
BwR [17] and GEEL [34] also explore more scalable graph representations via bandwidth restriction schemes, which are then fed to other graph generation architectures;
HDDT [33] leverages
K -tree representation of graphs capture their hierarchical structure in an autoregressive manner;
GDSS [38] is purely score-based formulation for graph generation;
BiGG [14] a parallelizable autoregressive model that takes advantage of graph sparsity to
scale for large graphs;
EDGE [10] is a degree-guided scalable discrete diffusion method (more details in Section 2).
26

---

F Digital Pathology
In this section, we go through additional information related to the digital pathology datasets.
E1
Digital Pathology Primer
Digital pathology consists of an advanced form of pathology that involves digitizing tissue slides into whole-slide images (WSI), allowing for computer-based -bssed analysis and storage. Deep learning approaches quickly integrated digital pathology processing methods, primarily focusing on extracting image-level representations for tasks such as slide segmentation and structure detection. These have also been used for downstream tasks such as cancer grading, or survival prediction [6. 71J. However, existing image- based approaches face challenges with the sizes of WSIs, requiring their patching. This procedure raises a trade-off between the context and the size of the patch provided to the model. Moreover, image-based deep learning lacks efficient representations of biological entities and their relations, resulting in less interpretable models. Recently. entity grapph based approaches have emerged as promising alternative to evade such limitations [36, 2]. These graphs are built by directly assigning nodes to biological entities and modelling their interactions with edges [26, 36), providing enhanced predictive performance and interpretability [35, 82).
Importantly, most of the deep learning contributions in the digital pathology realm have been in the discriminative setting. However, digital pathology could profoundly benefit from the development of generative formulations in several dimensions: first, there is is lack of high-quality annotated samples, mostly due to their heavy ethical and privacy regulation. Besides, collecting these samples remarkably costly, both economically and in terms of time and labor required [36]. Most of the discriminative approaches are also eettance-bssed The developed models then become highly sensitive to distribution shifts, which is a common challenge across biomedical datasets, for instance due to batch effects [21]. The development of generative models in digital pathology can address these limitations by enabling both the generation of synthetic data and distribution-baal
characterisations of the data. Even though some approaches have been carried out using image-based methods (e.g.. GANs [39] or even diffusion models [56]), these lack the advantages of graph-based approaches. To the best of our knowledge, graph-based generative modelling in digital pathology has only been explored by Madeira et al. [52]. Despite the promising results for data augmentation settings, only an off- shellf graph generative model (DiGress) is explored and in proprictary dataset.
F22 Building Whole-slide Cell Graphs
We build the whole-slide cell graphs from the genomic and clinical data available from the Molecular Taxonomy of Breast Cancer International Consortium (METABRIC) molecular dataset². This dataset has been extensively used in previous breast cancer studies [66, 13. 15]. Using the single cell data, we mapped 32 different annotated cell phenotypes grounded manner. We used the mapping detailed in Table 6. Therefore, each node is assigned to one of the resulting nine possible phenotypes. We assume these phenotypes to extensively characterize a cell both anatomically and physiologically.
more generie phenotypes in a biologically
Regarding edges, we followed the typical procedure for cell- sell-graphs in digital pathology [36, 2, 82]; first we used Delaunay triangulation on the cell positions to build them. Then, we discard edges longer than 25 j.m. We note that we obtain different graphs than the ones considered by Danenberg et al. [15]. In terms of dimensionality, we obtain graphs with b = 9 and = 1. We focus on the generation of simple yet biologically meaningful structures, Tertiary Lymphoid Structures (TLSs), further described in the next section. Thus, we extract 4-hop non non-overlapping subgraphs centered at nodes whose class is "B-cell" from the whole-slide graphs.
F.3 Tertiary Lymphoid Structures
Tertiary Lymphoid Structures (TLSs) are simple yet biologically meaningful structures. Structurally, TLSs are well-organized biological entities where clusters of B-cells are enveloped by supporting T-cells. Typically observed in ectopic locations associated with chronic inflammation [61, 69], these structures have been linked to extended disease-free survival in cancer [28, 44, 18, 58, 69], thus
Data retrieved from http::://aaooooorr/rcrrttt/////s
27

---

Table 6: Mapping used to convert the original phenotypes to the adopted phenotypes.
Original Phenotype
Mapping Phenotype
XX8-18"CXCL11
Epithelial
HER2*
MHC*
CK8-18"ERR"
CK!
CK!
CK8-18 ER
CKmodER"
MHC & I1'i
Basal
Ep CD57+
MHC CD'
CRCCXC
Ep Ki67+
CK+ CXCLI2+
CD15
Endothelial
Endothelial
Macrophages & granulocytes
Macrophages/Gramuloeees
Macrophages
Granulocytes
Fibroblasts Fibroblasts FSP1+
Fibroblast
Myofibroblasts
Myofibroblast
Myofibroblasts PDPN+
CD4 T cells
T
CD4+ T cells & APCs
CD8 T cells
TReg & TEx
B cells
B
CD57+
Marker
Ki67+
CD38+ lymphocytes
CD38+ Lymphocyte
constituting an important indicator for medical prognosis in cancer. Since these are small structures when compared with the size of whole-slide graph, we extract non-overlapping 4-hop subgraphs centered at nodes whose class is "B", corresponding to cells, from the WSI graphs. This procedure is illustrated in Figure 4.
As mentioned in Section 4.2, the TLS content of cell graph can quantified using the TLS embedding, k = jKo.... .., As| E I [69, 52]. This TLSS-like organization metric considers only edges between B and T-cells and classifies them into several categories: a edges link two cells of the same type, while ?; edges connect a B to T-cell, where is the number of B-cell neighboring the B-cell vertex (see Figure 4). Therefore, the entry of x is defined as the proportion of y edges whose index is larger than i:
EBT
|E
Σ3 E
Ky (G)
(20)
EST
Exa
where |BT|| [Ea], and Enyl correspond to the number of edges whose both vertices are B or T-cells, of a edges and of 7 edges in given graph, G. Note that, by definition, the entries take values between 0 and and monotonically non-increasing with i.
28

---

Stedked
Maken Facclaiid
Figure 4: Extraction of cell subgraph (center) from WSI graph (left). From this cell subgraph, we can then compute the TLS embedding based on the classification of the edges into different categories, shown on the right. We can observe cluster of B-cells surrounded by some support T-cells, characteristic of high TLS content.
F.4 Statistics of digital pathology datasets
In this section we provide the statistics for the low and high TLS content datasets. In Table 7, we provide their structural statistics and, in Table 8, the prevalence for each of the nine phenotypes (after mapping) across all the nodes in the datasets. In Figure 5, we provide their entry-wise distributions for the TLS embedding,
Table 7: Digital pathology datasets statistics. Here, we report the same stats as in Table 5. # #Train, VVll and #Test denote the number of graphs considered the train, validation, and test splits, respectively.
Dataset
Min. nodes
Max. nodes
Avg. nodes
Min. edges
Max. edges
Avg. edges
#'Tain
# Val
# Test
High TLS
20
81
57.9
39
203 204
143.8
128
32
40
Low TLS
20
51.7
37
123.7
128
32
40
Table 8: Prevalence (in %) of the different cell phenotypes for the digital pathology datasets.
Lymphoeyte
Endothelial
Fpithelial
MarrplaggssKnnnnncyyss
Myotihroblast
High TLS
39.3
1.9
4.6
9.4
4.4
6.3
0.6
7.2
26.4
Low
33.4
14.1
F.5 Baseline Method for Digital Pathology
The non-deep learning method used as baseline for the digital pathology dataset follows Madeira et al. [52]. This model leamss three distributions by counting the frequencies of given events in the train dataset. In particular:
Categorical distribution for the number of nodes, where the probability of sampling a given number of nodes is the same as its proportion in the train dataset, D i.e.:
P(JX = k) [G Dwaain [X = k}]
D
Categorical distribution for the cell phenotypes, where the probability for each cell phenotype corresponds to its marginal probability the dataset:
P(Ph(v) = ph;) = EGED Danii H Ph(p) = ph,
ΣOED X
where Ph(v) refers to the phenotype of node v. and ph, denotes the specific phenotype labeled as These consist of the phenotypes described in Appendix F.2 with fixed (arbitrary) order.
Bernoulli distribution for the edge type (no edge edge) conditioned on the phenotypes of its two vertices, again computed based on its marginal distribution in the train set.
P(Edge Ph(11) = ph, Ph(v2) = ph,) EGEDrain K( Uz) C(G) (U1, U2) E}
Ece Deran [C(G)]
where C(G) {v] X Ph(vi) = ph,} x {12 X Ph(12) ph,} for 1 S ph, ph. 9
29

---

Low TLS
High TLS
x(O)
x(O)
10-
1.0
1122
x(1)
K( (1)
x(2)
2)
0.00
0.2
0.6
0.8
1.0
0.0
0122
0.4
0.8
1.0
k(3)
K:(3)
0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
x(4)
K( ((4
20
0
1.0
01.2
x(5)
K (5)
10
Figure 5: Distributions of the TLS embedding entries for the low TLS (left) and the high TLS (right) datasets.
To sample a new graph, we first sample number of nodes for the graph from the first distribution. Then, for each of those nodes sample a cell phenotype from the second distribution. Finally, between every pair of cells, we sample an edge type given the two phenotypes previously sampled from the third distribution. This sampling algorithm described in Algorithm 4.
Algorithm 4: Sampling Algorithm for the Digital Pathology Baseline
Input: Number of graphs to sample N
for i == to N do
Sample | ~ P([)):
// Sample number of nodes
for n to [X] do
[ ~ P(Ph(z)) end
// Sample node phenotypes
for
1 <<ijj $ 9 do E[i,j] P(Edge Ph(X[[]), Ph(X()))
// Sample edges
end
Store (X, F));
end
30

---

G Molecular Datasets
G.1 Exploring Planarity
In this section, we show the results for 3 molecular datasets: QM9 [81], MOSES [62] and Gua- caMol [9]. Importantly, for QM9 and GuacaMol, we include formal charges as additional node labels, since this information has been shown beneficial for diffusion- based molecular generation [80]. For MOSES, such information not available.
The metrics used to evaluate generation were:
FCD Fréchet ChemNet Distance [63], similar to Fréchet Inception Distance (FID) but for molecules, represented SMILES. This metric evaluates the similarity between the gener- ated and test molecule sets, providing an indicator for the sample quality in unconstrained settings;
Uniqueness proportion of not repeated molecules across all the generated molecules;
Novelty proportion of generated molecules that not in the train set;
Valid proportion of generated molecules that are valid. This metric evaluates sample validity.
In particular, we explore planarity as target structural property the molecular setting, as previously suggested by recent works in discriminative tasks [19]. Therefore, we also include the proportion of planar molecules from the generated set as an evaluation metric. As a remark, QM9 and MOSES are exclusively composed of planar molecules. GuacaMol contains 3 non-planar molecules out of 1273104 molecules the train set and 3 non-planar molecules out of 238706 molecules in the test set. We considered these non-plan non-planar examples negligible in model rrainingevaaluation, thus fully preserving the original dataset. The validation set has 79568 planar molecules. The results are shown in Table 9.
Table 9: Graph diffusion performance on molecular generation. The constraining property used for ConStruct is planarity. We performed five sampling runs for each method and present their results in the format mean + standard error of the mean. For each run, we generated 10000, 25000, and 18000 generated molecules for QM9, MOSES, and GuacaMol, respectively, following the protocol from Vignac et al. [79]. Note that for MOSES and GuacaMol, we do not report their benchmarking metrics, focus overview comparative analysis of the two methods, DiGress+ and ConStruct. The FCD is computed using the official implementation from Preuer et al. [63].
QM9 Dataset
Model
FCD
Unique t
Novel
Valid
Planarity
DiGress+
0.2090 +0.0068
96.0 20.1
36.6 #0.1
99.0 20.0
99.7 40.1
ConStruct
0.3443 #0.0061
96.1 #0.1
40.1 #0.2
98.5 #0.0
100.0 #0.0
MOSES Dataset
Model
FCD
Unique
Novel
Valid
Planarity
DiGress+
0.5447 40.0080
100.0 20.0
93.5 20.1
87.5 20.1
100.0 20.0
ConStruct
0.6068 20.0045
100.0 20.0
93.7 20.1
84.1 20.1
100.0 20.0
GuacaMol Dataset
Model
FCD
Unique t
Novel ?
Valid
Planarity
DiGress+
0.9663 +0.0063
100.0 40.0
100.0 =0.0
84.7 +0.2
99.9 40.0
ConStruct 1.0538 +0.0045
100.0 40.0
100.0 =0.0
81.9 #0.1
100.0 +0.0
We only observe an incremental improvement in the planarity satisfaction of the output graphs of ConStruct, since DiGress+ learns to almost always generate planar graphs. As consequence, the constrained model ends up being marginally less expressive than the unconstrained one, as extensively discussed in Appendix H. This impacts both sample quality and sample validity. In fact, while for the discriminative setting, the main aim is to design fully expressive architectures for classes of
31

---

graphs as broad as possible, e.g., PlanE [19] for planar graphs, in constrained generation this is not the case. As exemplified, planarity is too loose of a constraint, since the atoms composing molecules typically have low degrees and it becomes highly unlikely for the unconstrained diffusion model to violate planarity. This ends up slightly harming the performance of the constrained generative model without bringing the benefits of increased validity, as observed in Section 4.
As side note for the interested reader, the low values of novelty for QM9 are a result of the nature of this dataset, which consists of an exhaustive enumeration of small molecules satisfying a given set of properties [78, 79]. Therefore, there is small room for the generation of new molecules within such space.
G.2 Controlled Molecular Generation
In many real world scenarios, want generate molecules to target different goals, ranging from specific drug interactions to particular material properties. In such cases, we are not interested in generating any realistic molecules, but in obtaining molecules that are endowed with given properties matching our specific objectives. Constrained graph generation appears as promising research direction to accomplish such tasks, as the generated molecules will necessarily verify the enforced properties by design. In this section, we explore how to use ConStruct to successfully address such challenge.
One relevant property of molecules is acyclicity. In molecules, this structural property dictates distinct chemical characteristics compared their cyclic counterparts. In fact, acyclic molecules are frequently encountered in natural products and pharmaceuticals, where their linear structures con- tribute to enhanced solubility, bioavailability, and metabolic stability. Additionally, acyclic molecules offer simplified synthetic routes and reduced computational complexity in modeling studies.
We explore the generation of acyclic molecules by picking the absence of cycles as constraining property for ConStruct. Importantly, in contrast to all the experiments in the paper, we do not train with only graphs that verify the property. Instead, use the two models trained in the unconstrained setting (from previous section): one with edge-absorbing transitions (ConStruct) and another with marginal edge transitions (DiGress+). We then sample from these models using the absorbing noise model and the projector for acyclicity. The results are presented in Table 10.
Table 10: Controlled graph diffusion for acyclic molecules. The constrained property used is acyclicity. Constrained DiGress+ denotes a model that trained with marginal noise model, but where the sampling is performed using the edge-absorbing noise model and projector. Both models were trained in the full QM9 dataset. We performed five sampling their results in the format mean + standard error of the mean. For each run, we generated 10000 molecules, following the protocol from Vignac al. [79]. The FCD is computed using the official implementation from Preuer et al. [63].
for each method and present
QM9 Dataset
Model
Unique
Novel 1
Valid
Acyclicity t
Constrained DiGress+
80.7 a0.1
64.7 40.2
81.3 10.3
100.0 40.0
ConStruct
79.2 40.2
68.8 #0.1
99.8 #0.0
100.0 +0.0
We observe that both methods output only acyclic molecules, which is a necessary consequence of the utilization of the projector. As the set of acyclic molecules is subset of the of unconstrained molecules, we verify some repetition among the generated samples. This leads to a decrease in the values of uniqueness for both models when compared to the unconstrained setting. Most remarkably, while the validity of the molecules generated by the model trained with the marginal noise model is significantly lower than the observed one for the unconstrained sampling setting, ConStruct preserves its high validity values (even higher than in the unconstrained setting). This result validates the foundation upon which ConStruct laid: with the marginal noise model, the forward process distribution does not match the reverse one when employing the projector, harming the molecular validity of the generated instances. In contrast, the edge-absorbing noise model of ConStruct allows the forward and reverse processes to match, staying in distribution.
32

---

H Variants of ConStruct - Performance Analysis and Extensions
In this section, we perform some ablations to ConStruct/iirress+ to further analyse its performance and explore methodological extensions to the proposed method.
H.1 Performance Analysis
From Table 1, observed that, for the specific case of the tree dataset, DiGress+ outperforms ConStruct. To explain why, we start by noting that approximately 97% of the graphs generated by DiGress+ already comply with the target structural property. This value indicates that DiGress+ had access to sufficient data and it is sufficiently expressive to learn the dependencies of tree graphs almost perfectly, leaving little room for improvement with ConStruct. In contrast, for the lobster and planar datasets, the corresponding values of DiGress+ are significantly lower, hinting the pertinence of ConStruct in such scenarios.
However, this observation alone does not explain the slight performance gap. To investigate further, we ran DiGress+ with an edge-absorbing noise model but without projector, designating it as DiGress+ labsorbing] in Table 11. We observe a significant decrease performance with this modification. This suggests that it is the choice of the noise model that is hindering ConStruct's performance for this dataset. In fact, ConStruct outperforms DiGress+ [absorbing], emphasizing the relevance of the projector step. In any case, we remark that we did not adjust the variance schedule beyond the one proposed by Austin et al. [4], leaving room for potential improvement in this aspect. Importantly, we observe dataset dependency of performance by applying the same modified model to the planar dataset (again, see Table 11), where it exhibits a significantly better average ratio compared to DiGress+. This observation aligns with recent research indicating that there is clear evidence that an optimal noise model can be deduced a priori from dataset statistics [77].
H.2 Posteriori Modifications
An advantage of our setting is that the projector merely interferes with the sampling algorithm, avoiding to affect the efficiency of the diffusion model training. Otherwise, if we were to directly block the model's predictions, it would require constraint satisfaction check for each potentially added edge at every forward pass, resulting in prohibitive computational overhead.
In constrast, we could also consider the opposite setting: only applying a posteriori modifications graphs generated by the unconstrained model. Two possible alternatives emerge:
DiGress+ [rejection] reject the final samples generated by the unsconstrained model that do not satisfy the provided constraint. While we should expect a good performance from this approach, wastes computational resources as it requires discarding the rejected graphs and restarting the whole sampling process until we get the desired amount of generated graphs.
DiGress+ [projection]- we only apply the projector to the final samples generated by the unconstrained method. For example, in the case of planarity as target property, we could find the maximal planar subgraphs of the generated samples. This method would necessarily provide a more efficient sampling procedure (as we only execute the projector step once).
We provide the results in synthetic graphs for both methods in Table 11. We observe that DiGress+ [rejection] attains great V.U.N. values, as expected. Nevertheless, we analyse its alarming compu- tational inefficiencies in Appendix D.3. Additionally, we that DiGress+ (projection) achieves worse performance than ConStruct. We attribute this result to the fact that such a scheme fails to inform the generative model about the constraining condition throughout the reverse process, thus not harnessing the full expressivity of the diffusion model. We also attribute the anomalously good performance of this method for the tree dataset to the optimal properties of the projector in such case (see Theorem 2).
Finally, considering the two extreme cases described above (blocking edges at every forward pass vs a posteriori modifications). we conclude that ConStruct finds itself in a sweet spot in the trade-off between additional computational burden and constraint integration into the generative process.
33

---

H.3 Likelihood- based constrained generation
We also consider two variants of ConStruct where the projector is no longer independent from the diffusion model. Instead, we use the associated likelihoods to each of the sampled candidate edges at a given time step I, po ( IG") to define an order by which we add the edges. Therefore, instead of uniformly sampling them at random, propose two methods of integrating such information:
Deterministic: add the edges with higher po(e) |G') first.
Stochastic: we sample without replacement from the set of candidates edges, where the probability of sampling each of them is proportional to the respective pa(e,; "
We present the results for these likelihood observe, for all the analysed datasets, the three ConStruct variants are statistically equivalent in terms of performance.
variants of ConStruct in Table 11. As we can
terms of efficiency, there is no meaningful difference among the three methods: even though the uniformly random sampling does not have access ple 'I'), nor sort the order of the corresponding edges, the computational overburden of these operations is negligible. We remark that the theoretical analysis performed in Appendix also holds for the stochastic fikelihood-base variant, but not for the deterministic one, as the latter is not able to select any permutation from the candidate edges with non-zero probability: up to the degenerate cases where different candidate edges have the same p(el) G always selects candidate edges by the same order.
Table 11: Graph generation performance on synthetic graphs. DiGresst, ConStruct are retrieved from Table 1, from which we follow the same experimental protocol. DiGress+ [absorbing] denotes DiGress+ with an edge-absorbing noise model. DiGress+ [rejection] refers to the baseline that rejects the unconstrainedly generated graphs that do not satisfy the constraint and resamples until the intended number of valid graphs is reached, while DiGress+ [projection] directly applies the projector on unconstrainedly generated graphs. ConStruct [model det] and ConStruct [model- stoch) denote the deterministic and stochastic likelihood-baace variants of ConStruct.
Planar Dutueet
Model
Des.
Cls.
Spec.
Wavelet 1
Vuidd
Unique
Novel
V.I.N.
Property 1
0,0300
0,0005
0.0038
0,0022
100
0.0
DiGinass
0.0008 wIum
0.0410
0,0048 stoe
0,0056 sume
0,0020 same
3.6
76.4
100.0
103.0
76.4.12
76.4
0.0033 -Ini
0.0405 -1me
0.0095 -1084
0.0055
0.0009
1:1411
100.0
100.0 4co
100.0-1
10000:4 404
100.0 40
DNUieeee (sneoehingl
0.0883 -3094
0.0000 stowe
0/0010 sauee
2.4
41.4 c1
100.
1000--00
43.4 =18
43.4 st
DiGresss [ssjection]
0,0418
0.0022 JUNK
0.0054 a5000
abvics
2.6
100.0
100.0.00
DiGress (projcctio]
0.0003 Jac8I
0,8347 20000
0.0013 JAUN2
0.0056 Jl0Wo
1.6
100.0
103.0.00
dei]
ConSorcct (moode.
0,0005
0,0050
100,0
100.0
Tiee Dataset
Trán sct
0.0001
0.0000
0,0000
0.0075
0,0030
1.0
100
100
0.0
0.0
100
DiGross
0.0000 -1000
0,0000 -1000
0,0092 -5080
0.0072 4010
91.6 wmx
100.0
100.0 -m0
91.6 4m13
97.0
Ditiresse (aoortiing
U100014
0100000
010000
0,0479
0/04114
72.8
100.0
103.0
72.8
DiGress [nseection]
0.0002 J03.81
0.0000
0.0000 J0080
0,0093 a5006
0,0012 aaro0
100,0 aus
100.0
103.0 am0
100.0
100.0
DiGress [projcttion]
0,2002 J008I
0,0000 22030
0,0000 JA080
0,0092 a80844
0,0031
abroxt
a.2
94.0 m33
100.0
103.0 220
94.0
100.0
Confermct (marde-- der]]
0.0003 -1mee
0.00000-100 -3
0.00000
-ammn
0.00766
0/0074
verere
1.9
83.2-13
100.0 4c0
100.0-mm
100.0
ConSoruct (mode: stoch)
0,0004 .000
0,0000 .2030
0,0000
J0000
0,0072
J0000
0,0034
1.9 233
43.2 .13
100.0 250
100.0 200
83.2 117
1000 uM
Lobster Datract
0,0000
0,0000
0,0070
0.0
DiGrass
0.0005 -1000
0.0000
0,0000
0,01
0,0093
1.8
70.0
98.0
96
60.4
76.8.1
Contiruce
0,0000
-1030
0.0000 s1om
010499 serero
0/0474 strmes
1.5
85.8-22
98.8 m0
97.0 +89
K1.5 95
100.0 .n
Ditiresce (roeetioon
BU00R1 J00081
0,0000
33030
0.00000 J00000
0.0130 30 J00013
0,0106 atrecs
2.1 JA2
100,0
96.4
95.6 22.
91300 un
1100 cM
DiGress (pejecttoo]]
0.0000
420000
0,0000 assmo
0,0109 asress
asvess
08.2
ConStrct (mode) del]
0.0000 JACAOO
0,0093 atrins
0.0075 atric
08.8
97.0 aB.
$3.4
(medee) stech)
34

---

Visualizations
In this section, we provide several visualizations of the final generated graphs, comparing them to the ones observed in the different datasets. We also visually expose the effect the projector different timesteps.
L.1 Graphs generated by ConStruct
Here we visually compare the graphs from the different datasets the ones generated by ConStruct.
L1.1 Synthetic Datasets
We provide plots of the sampled graphs from ConStruct for the different datasets: planar in Figure 6, tree Figure 7, and lobster in Figure
Figure 6: Uncurated set of dataset graphs (top) and generated graphs by ConStruct (bottom) for the planar dataset.
Figure 7: Uncurated set of dataset graphs (top) and generated graphs by ConStruct (bottom) for the tree dataset.
35

---

Figure 8: Uncurated set of dataset graphs (top) and generated graphs by ConStruct (bottom) for the lobster dataset.
I.1. Digital Pathology
We provide plots of the sampled graphs from ConStruct for the low TLS content dataset in Figure and for the high TLS content dataset in Figure 10. We also provide several snapshots throughout the reverse process of ConStruct in Figure 11 to illustrate it as edge insertion procedure.
Figure 9: Uncurated set of dataset graphs (top) and generated graphs by ConStruct (bottom) for the low TLS dataset. The phenotype color key is presented in Figure 4.
Figure 10: Uncurated set of dataset graphs (top) and generated graphs by ConStruct (bottom) for the
high TLS dataset. The phenotype color key is presented in Figure 4.
36

---

Figure 11: Reverse processes for generation of low (top) and high (bottom) TLS content graphs using ConStruct. We start from a graph without any edge on the left (1 T) and progressively build the graph, as consequence of absorbing noise model. The node types switch along the trajectory due to the marginal noise model. On the right, have fresh new sample (t 0). The phenotypes color key is presented Figure 4.
1.2 Visualizing Intermediate Graphs (Before and After Projector)
In this section, we provide some visualizations of intermediate graphs obtained throughout the reverse process for three different datasets: planar, tree, and lobster. Figure 12, we highlight the effect of the projector in rejecting the candidate edges that lead to property violation.
J Impact Statement
The primary objective this paper is to enhance graph generation methodologies by enabling the integration of hard constraints into graph diffusion models. Although this problem holds signifi- cance for several real-world applications, including digital pathology and molecular generation, as exemplified in the paper, well protein design, the potential implications extend advances in biomedical and chemical research. This development has the capacity to yield both positive and negative societal outcomes. Nonetheless, despite the potential for real-world impact, currently do not identify any immediate societal concerns associated with the proposed methodology.
For the particular case of the digital pathology setting, while the generated graphs are able to mimic clinically relevant structures, they remain too small to have any direct clinical impact. Pathologists whole-slide images for informed decisions, whose corresponding cell graphs typically comprise a total number of nodes to 4 orders of magnitude above the graphs generated at this stage.
37

---

Planar
tw
t-3
Tree
Lobster
Figure 12: Visualizations of intermediate graphs throughout the reverse process. The notation follows the one of the rest of the paper: we obtain G after applying the projector on Gr-1, which in turn obtained from G through the diffusion model. From the new edges obtained in dr-1, we color them in green when they do not break the constraining property and in red otherwise. We can observe that the red edges are rejected. To better emphasize the edge rejection by the projector, we do not use fully trained model and use a trajectory length, T, smaller than usual, resulting in less accurate edge predictions.
38

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the claims found in the abstract and introduction are properly supported in Sections 3 and 4. Additionally, proofs for the theoretical claims are in Appendix and experimental extensions in Appendices D.3, G and H.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We explicitly outline the assumptions underlying our approach in Section 3.2. We discuss the limitations and potential further improvements and extensions in Section Besides, we discuss in detail the performance limitations of our approach in Appendix H. Finally, we also discuss computational efficiency and scalability of the proposed method in Section 3.5 and appendices C, D.2 and D.3
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specifiiattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
39

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide simplified version of the theoretical guarantees of the proposed
method in Section 3.4. The full versions of our theoretical results, where the required assumptions are clearly stated, are provided in Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: Regarding the proposed method, first describe it in Section 3. Further detailed information on the method and its algorithmic implementation in Appendix A. Additional information the experimental setup (dataset splitting procedure, the model selection criteria, and optimizer) are provided in Appendix D. 1. For the new datasets, we extensively deseribe their construction process in Appendix F. We also provide the model checkpoints. Based on this information, both the results and newly generated datasets are reproducible.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution
specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
40

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: The provided repository includes the newly proposed datasets and code to download all additional datasets used. also allows for reproducing the experimental results, with clear instructions on how to set up the required environment and the commands needed replicate the various experiments described in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nipp) cc/
htapii/gguidees/deSSuuiii snsssiccynloylo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss. wwtpccccccpppc.cceccceec weaccc/guiess/eee httpg//ddde/odeSumiiieeeeeee ssiioooliccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe the training details in Appendix D. Additionally, the data splits and the optimal hyperparameter configuration for each of the experiments can be found in the provided code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
41

---

Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide all results in terms of graph generation performance in the format "mean + standard error of the mean", contrarily to what has been common practice in the graph generation community until this point. As stated in the paper, the dispersion metric (standard error of the mean) is computed across several runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide detailed information about the used resources in Appendix D.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eerrpp.epeee i
Answer: [Yes]
Justification: We preserved anonymity in our submission. Our submission abides by the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
42

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss potential positive and negative societal impacts in Appendix J.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The release of our data and models does not pose direct risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
43

---

Answer: [Yes]
Justification: We cite all the works from where code and/or data was retrieved both in the paper and in the repository provided. For the particular case of the newly generated datasets, we cite the original open-source dataset from where we built upon, respecting their license terms.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide extensive information about the new datasets in Appendix F. The code is properly organized and commented.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No crowdsourcing or human subjects were involved in the experiments con- ducted for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
44

---

15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing or human subjects were involved the experiments con- ducted for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
45


Reviews:
[{"review_id": "x97vSPG70I", "reviewer": "Reviewer_wnSX", "summary": "This paper presents ConStruct, a framework incorporating structural constraints into graph generation models using a discrete graph diffusion process. By introducing an edge-absorbing noise model and a projector operator, ConStruct ensures generated graphs meet specific properties like planarity or acyclicity, crucial for real-world applications. The framework significantly improves the validity of generated graphs, demonstrated through experiments on synthetic benchmarks and real-world datasets such as digital pathology, achieving up to a 71.1 percentage point increase in graph validity. It mainly focuses on addressing the challenge of integrating domain knowledge into graph generative models, enhancing their practical deployment.", "questions": "Please answer my listed weakness above.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Maintaining the structural constraint of the generated graph is an important but challenging problem for diffusion-based graph generative models.\n\n2. The design of the edge-absorbing noise model and projector operator is reasonable and technically sound. Especially the efficiency consideration of incremental validity checks.\n\n3. The experimental results are good compared with recent SOTA baselines, including diffusion-based methods. The extensive results provided in appendix also well support the advantage of proposed method.\n\n4. The presented evaluation on Digital Pathology Graph dataset is interesting, and the released dataset seems useful for future research.", "weaknesses": "1. As explained by the authors, the proposed method can only deal with a specific type of structural constraint, i.e., edge-deletion invariance, but the discussion on the possible impact of this limitation is not well clarified. For example, what other normally-seen constraint \n\n2. Lack of complexity analysis. Instead, only the runtime measurement is provided.\n\n3. This method might not be able to deal with large graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer’s constructive feedback and requests for clarification. We have addressed the raised questions below:\n\n**W1**: An example of other purely structural constraints that ConStruct does not cover by default are edge-insertion invariant properties, *i.e.*, properties that hold upon edge insertion. This type of constraint can be useful, for instance, in the molecular generation domain, where we could impose constraints like \"the generated graph should at least have a cycle\" (we explore the inverse setting — acyclic molecular generation — in Appendix G.2). We note, nevertheless, that edge-insertion invariant properties could be easily captured by our framework through two simple modifications: design the transition matrices with the absorbing state in the existing edge state (instead of in the no-edge state) and a projector that progressively removes edges (instead of inserting them) while preserving the desired property. This simple inversion of ConStruct would allow it to cover edge-insertion invariant properties. In item 3 of the global rebuttal, we discuss other meaningful constraints that ConStruct does not cover but that could be extended to as future work, even if not purely structural. We propose to explicitly add this discussion to the paper.\n\nAdditionally, an example of a structural constraint that is completely outside the scope of ConStruct can be seen in graph stochastic models. Since the validity of these types of graphs is determined via statistical tests (thus, not deterministically), it is difficult to constrain the generation in that setting. An example of this occurs in the graph generation benchmark SBM dataset (from Stochastic Block Model), where validity is checked using a Wald test [1]. To the best of our knowledge, constrained diffusion towards such graph structural properties remains an open problem.\n\n**W2**: Since the projector is the only component incurring overhead, ConStruct only interferes with the complexity of the sampling algorithm, leaving the efficiency of the training algorithm intact. As described in Section 3.5, through the use of a blocking edge hash table and incremental property satisfaction algorithms, we are able to minimize the increase in complexity imposed by the projector. The complexity analysis for the blocking edge hash table is provided directly in Section 3.5. The complexity analysis for all the different edge-deletion invariant properties explored in the paper (planarity, acyclicity, lobster components, and maximum degree) can be found in Section 3.5 (planarity) and in Appendix C (all of them). We also provide a more explicit comparison between the underlying discrete diffusion algorithm and the incurred overhead by the projector in item 1 of the global rebuttal. We remark that due to the combinatorial nature of edge-deletion invariant properties, each property satisfaction algorithm is specific to the property at hand. Therefore, there is no general efficient property satisfaction algorithm for all edge-deletion invariant properties, and we have to address each property on a case-by-case basis.\n\n**W3**: Item 1 of the global rebuttal details the minor overhead imposed by the projector within the diffusion framework. It also addresses the method’s (high) scalability relative to the underlying discrete diffusion framework. In particular, we demonstrate that as the generated graph size increases, the overhead of ConStruct becomes increasingly negligible compared to the underlying discrete diffusion framework. Therefore, as far as that discrete diffusion framework is able to scale, ConStruct remains a viable option.\n\n[1] - Martinkus, Karolis, et al. \"Spectre: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators.\" ICML, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6EMrOYItoc", "reviewer": "Reviewer_ZwhZ", "summary": "The paper presents a novel diffusion model, ConStruct, to generate graphs that follow certain pre-specified properties. ConStruct involves an edge-absorbing forward process and a projected edge-addition reverse process to sample graphs that satisfy pre-specified constraints. The novelty of their method comes from a simple random-sampling-based projection algorithm that samples constrained graphs at each diffusion step. Experimental results show that ConStruct can generate more realistic synthetic graphs that have a pre-defined constraint for the whole domain. They also show its applicability to real-world pathology graphs, by leveraging the fact that they tend to be planar.", "questions": "See above weaknesses.", "limitations": "The authors do not adequately discuss the limitations of their work and the potential negative impacts of their work. It will be really useful to elaborate on the limitations of their work, e.g., limited to structural constraints of a certain kind. Furthermore, since they are using a pathology dataset of breast cancer studies, the authors must discuss the potential negative societal impacts of their analysis, particularly when the \"planar\" generated graphs are used as a data augmentation tool for the downstream application for cancer detection or such.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to read. \n- Experimental results are comprehensive for the synthetic graph datasets and use all representative metrics. \n- The paper also provides results of a real-world pathology dataset to highlight how structurally constraining the diffusion model is useful once we can establish some structure on the real-world graphs. In particular, they consider the planarity of the breast cancer pathology cell graphs. \n- ConStruct provides efficient ways to solve an otherwise NP-hard problem of projecting to hard constraints of acyclicity and planarity. The sampling time of ConStruct is at par with its unconstrained counterparts, which is quite impressive.", "weaknesses": "- It is not clear how applicable such domain-level constraints will be for real-world graphs that do not have a well-defined constraint. While the motivating example of pathology cell graphs is appreciated, it is difficult to see how it generalizes.\n- The idea is similar to PRODIGY which can be applied to any diffusion model and constraint including discrete models in the latest version [1] (which can be ignored but worthwhile to mention). Upon ignoring the minor requirement of an edge-absorbing forward process, ConStruct can be seen as an approximation of the projection operator where the distance is calculated as a GED instead of the Euclidean distance between the adjacency matrices. Thus, the novelty of the proposed method is limited. \n- Furthermore, the authors claim that PRODIGY distorts the underlying diffusion process even though PRODIGY takes a fractional step to the closest noisy graph that satisfies the given constraint. On the other hand, ConStruct finds a random graph that satisfies the constraint and takes a full step in that direction. Thus, it seems intuitively that ConStruct distorts the process more than PRODIGY, as opposed to the authors' claims.\n- The major novelty of the method comes from the proposed projection algorithm that tries to circumvent the NP-hardness by iteratively adding a random edge if it satisfies the constraint, which can be seen as a simple randomized greedy algorithm, which is quite well-studied in the discrete optimization literature. Theorem 1 in this vein is a bit trivial since it is expected that the optimal graph will belong to a randomly-edited set but it is not clear how easily it will be sampled for an arbitrary constraint. In the absence of this analysis, the proposed projection algorithm is not suitable for application.\n- While the authors compare against SPECTRE, they do not provide an elaborate discussion with this important related work that proposed this problem of including structurally-constrained generative models. \n- The proposed framework is limited to edge-deletion invariant (or more formally, downward-closed) constraints while the PRODIGY framework can theoretically handle a larger range of constraints including box constraints.\n- ConStruct is limited to non-attributed structural constraints due to the edit distance formulation and thus, cannot be applied to important molecular constraints.\n\n[1] Sharma, Kartik, Srijan Kumar, and Rakshit Trivedi. \"Diffuse, Sample, Project: Plug-And-Play Controllable Graph Generation.\" Forty-first International Conference on Machine Learning. 2024", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the detailed comments and pertinent questions. We address the raised concerns below:\n\n**W1**: We acknowledge that our model is tailored for the task of constrained generation, which requires the explicit and unambiguous definition of the constraint, as reflected in the paper's title. Despite not universal, we believe our framework is quite general. It proves effective for various properties in structurally constrained synthetic graphs and digital pathology, outperforming unconstrained models, and can also be used to guide unconstrained models (e.g., generating acyclic molecules, App. G.2). Additionally, we (non-exhaustively) enumerate several real-world applications beyond digital pathology where essential constraints are well-defined and edge-deletion invariant (l. 144-147, pg 4).  \n\n**W2**: Both works indeed address similar tasks. However, they differ fundamentally: PRODIGY offers efficient guidance of pre-trained models by relaxing adjacency matrices to continuous spaces (implicitly imposing an order between states) and finding low overhead projections there. Yet, it does not guarantee constraint satisfaction and faces a trade-off between performance and constraint satisfaction due to mismatched train/sample distributions. In contrast, ConStruct, while also suitable for guided generation (App. G.2), is designed for constrained generation. It treats adjacency matrices as discrete, where there are no efficient solutions for projections into arbitrary subclasses of graphs (e.g. maximum planar subgraph is NP-hard). This results from the lack of inherent ordering between states and the combinatorial nature of the domains of valid graphs. Nonetheless, ConStruct ensures constraint satisfaction with matched distributions, thereby improving performance over unconstrained models, and maintains efficiency through incremental algorithms and blocking edge hash tables. Thus, ConStruct is not an approximation of continuous-space projections and we believe it to be a full contribution in itself.\n\n**W3**: Our mention to the potentially compromised smoothness of the diffusion process refers to the thresholding step required by PRODIGY to convert the continuous adjacency matrix back to a discrete one, either at the end of the diffusion process (continuous diff.) or at each reverse step (discrete diff., a variant not available at submission). This step can disrupt smoothness as it is sensitive to the implicit ordering between states, may not yield the most appropriate discrete matrix for the original continuous relaxation, and does not guarantee constraint satisfaction. Despite notably reducing the distortion of the diffusion process, PRODIGY's fractional constraint enforcement does not address this drawback.\n\nIn contrast, ConStruct operates directly on discrete state-spaces and avoids this limitation. ConStruct adjusts a graph from the previous reverse step by inserting the property preserving newly proposed edges, which are typically very few, promoting the process smoothness. Although edges are chosen in random order in the default implementation, Section H.3 empirically shows that this approach is not inferior to methods that order edge insertion based on predicted likelihoods by the diffusion model. \n\n**W4**: Theorem 1 provides useful guarantees about the proposed projector and helps understand the problem complexity. We agree that analyzing how often the projector retrieves the optimal graph is valuable; indeed, Theorem 2 shows that for the acyclicity constraint, the proposed projector *always* retrieves the optimal graph. Table 3 provides counter-examples demonstrating that this is not true for planarity, maximum degree, and lobster components. Since ConStruct generates new edges based on the diffusion model and not randomly, characterizing this subset to obtain more refined results (e.g., probabilistic bounds) for arbitrary properties is far from trivial. Finally, we believe that ConStruct is indeed well-suited for application as it shows significant performance improvements, high efficiency, and guaranteed property satisfaction.\n\n**W5**: We did not initially consider SPECTRE as closely related because it is GAN-based and it addresses unconstrained generation by producing eigenvectors and eigenvalues of the Laplacian and generating graphs conditioned on these. We did not find steps handling constraints, apart from the auxiliary eigenvector refinement matrices construction (must belong to the special orthogonal group). We would be happy to discuss SPECTRE’s relevance if the reviewer clarifies why it is particularly pertinent.\n\n**W6**: While ConStruct does not cover all PRODIGY constraints (e.g., molecular properties, see W7), it does handle a meaningful subset, including all of those tested on non-attributed datasets (edge count, triangle count, maximum degree). Crucially, ConStruct also handles combinatorial constraints (e.g., planarity, acyclicity), which PRODIGY cannot.\n\n**W7**: ConStruct does not handle node feature-dependent constraints found in molecular generation. However, molecular generation is dominated by autoregressive models due to their ability to perform validity checks at each step with minimal overhead [1]. The possibility of node ordering in molecules (via canonical smiles) explains this success. In contrast, ConStruct is designed for settings where node ordering is not suitable, such as digital pathology, focusing on purely structural constraints. While integrating node-dependent constraints into ConStruct is an exciting prospect, we believe that our focus on structural constraints does not diminish our contribution in a fundamentally distinct setting, as highlighted by Reviewer FDH7 in W1.\n\n**Limitations**:\nWe appreciate the reviewer's suggestion and have elaborated on the specified points in the final manuscript (items 3 and 4 of global rebuttal). Overall, we believe we have addressed the limitations of our work adequately, a view also supported by Reviewer FDH7", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6UebvZq44Q", "reviewer": "Reviewer_FDH7", "summary": "The authors proposed ConStruct, a graph generative framework that enables hard-constraining graph topological properties that hold upon edge deletion throughout the entire sampling trajectory. Specifically, the authors model the forward (data-to-prior) process using an edge absorbing noise model, and they predict the reversed edge insertion process using a GNN projector.", "questions": "**Q1.** Please clarify the definition of $\\Delta^b$ in Page 5, line 171.\n\n**Q2.** During the reverse sampling process, how to guarantee the existence of a feasible $G^{t-1}$ among the candidates induced by discarding some newly added edges from $G^t$ to $\\widehat{G}^{t-1}$ (or equivalently, the intersection of $\\mathcal{C}$ and $\\mathcal{G}^{t-1}$ in Theorem 1 is not empty)? If there is no feasible candidate, will the generative procedure be prematurely existed? \n\n**Q3.** Following **W2**, I notice that there is a seemingly discrepancy between the training and sampling process. The effect of the projector is absent during the training process. I hope the authors can add some analysis and clarifications on why the edge predictor trained without projector can still provide satisfactory samples.", "limitations": "The authors adequately discussed the limitations of the proposed method.\n\nThey discuss in detail the performance limitations of their approach in Appendix H.1. They also point out potential further improvements and extensions to their approach in Section 5. Finally, they discuss computational efficiency and scalability of the proposed method in Section 3.5 and Appendices D.2 and D.3.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "**S1.** The proposed method is the first graph constrained discrete generative framework. The hard-constraining graph generation task is challenging and meaningful.\n\n**S2.** The authors provided theoretical guarantee for the generation quality of ConStruct.\n\n**S3.** The authors improve the sampling efficiency using the incremental constraint satisfaction algorithm in the spirit of curriculum learning.", "weaknesses": "**W1.** The ConStruct is only applicable to edge-deletion invariant properties (Definition 3.1). Thus, it cannot be applied to hard-constrain more complicated and general graph properties, e.g. chemical properties for molecules. \n\nHowever, this limitation does NOT weaken the contribution of this paper and should be considered a future research direction of hard-conditioned graph generation.\n\n**W2.** The projector module (Figure 2 and Algorithm 3) introduces intractability in likelihood estimation of the graph, making it hard to estimate the likelihood of the graph instances generated by ConStruct.\n\n**W3.** ConStruct seems to be a autoregressive method, which means that the sampling complexity is in proportional to the graph size. In contrast, the diffusion-based method generates the whole graph and keeps refining it along the generative trajectory. Thus, it seems that ConStruct takes more generative steps for large graphs (w.r.t the amount of nodes and edges) when compared to diffusion-based models. I recommend the authors to assess the time complexity and efficiency of this model compared to diffusion-based methods.\n\n**W4.** It seems that the authors did not compare their method against the two mentioned (Page 3, line 88-89) discrete-diffusion graph generative models EDGE [1] and Graph-ARM [2]. By the way, I recommend the authors to cite the latest or published version rather than the ArXiv versions.\n\n[1]. Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. 2023. Efficient and degree-guided graph generation via discrete diffusion modeling. In Proceedings of the 40th International Conference on Machine Learning (ICML'23), Vol. 202. JMLR.org, Article 181, 4585–4610.\n\n[2]. Kong, L., Cui, J., Sun, H., Zhuang, Y., Prakash, B.A., & Zhang, C. (2023). Autoregressive Diffusion Model for Graph Generation. *International Conference on Machine Learning*.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the importance of the topic under consideration and for the insightful comments. We address the reviewer's concerns in the following points:\n\n**W1**: We agree with the reviewer and do also envision the extension to joint node-edge constraints, e.g. valency constraints in molecular generation, as an exciting future direction. We extend on this topic on item 3 of the global rebuttal.\n\n**W2**: We remark that, despite the lack of a tractable evidence lower bound for the likelihood, the proposed projector pushes ConStruct to remarkable empirical performance, outperforming unconstrained models. \n\n**W3**: Even though ConStruct allows for constrained generation in a similar manner to autoregressive models, it is actually a diffusion-based framework. \nWe thoroughly analyse its complexity and efficiency in section 3.5 and appendix C. Based on this, we provide a more explicit comparison in terms of complexity to the underlying discrete diffusion methods in item 1 of the global rebuttal. From such comparison, we are able to conclude that ConStruct is a scalable method.\n\n**W4**: For EDGE, we do compare for planar and tree datasets (Table 1). We did not test it in the digital pathology setting because we only picked \"the methods that, besides DiGress, attain non-zero V.U.N. for the planar dataset in Table 1, which we consider as a proxy for performance in the digital pathology datasets due to the structural similarities between the datasets\" (ll. 310-312, pg. 9). In fact, the digital pathology dataset is even more challenging since it contains attributed planar graphs. \n\nFor GraphARM, unfortunately the authors do not report results on any of the used datasets, neither provide their code (to the best of our knowledge), which makes meaningful comparisons difficult. \n\nWe appreciate the reviewer's suggestion to update citations and have addressed this. \n\n**Q1**: $\\Delta^k$ denotes the $k$-simplex: \n\n$$\n\\left\\lbrace \\left(\\lambda_0, \\lambda_1, \\ldots, \\lambda_k\\right) \\in \\mathbb{R}^{k+1} \\mid \\lambda_i \\geq 0 \\text{ for all } i,  \\text{ }  \\sum_{i=0}^k \\lambda_i = 1 \\right\\rbrace.\n$$\n\nWe added this clarification to the notation paragraph and we corrected its usage in l.171 accordingly (to $\\Delta^{b-1}$).\n\n**Q2**: If all the newly proposed edges (inserted from $G^t$ to $\\hat{G}^{t-1}$) by the diffusion model lead to constraint violation, then the graph remains the same as in the previous step, $G^{t-1}=G^t$ (so the intersection of $\\mathcal{C}$ and $\\mathcal{G}^{t-1}$ is trivially non-empty). We do not early exit the reverse process in such case because the denoising network takes as input both $G^t$ and the timestep $t$. Therefore, even if for a given timestep $t$ all the proposed edges are rejected, the model predicted probabilities can change in the next reverse step, since the model has now a different input (still the same graph $G^{t-1}$($=G^t$) but the timestep is $t-1$). Note that the case where the diffusion model does not propose any new edge (as we dot not lower nor upper bound the number of edge insertions at each step) falls within that case as well. \n\nAdditionally, we remark that the diffusion model outputs a probability distribution over graphs, from which we sample the proposed graph. As a result, the proposed edges at each reverse step are not deterministic, even with the same inputs (thus outputs) to the model.\n\n**Q3**: In training, as the edge-absorbing noise model only removes edges, the training noisy graphs necessarily remain within the domain of graphs that satisfy the desired edge-deletion invariant property. Therefore, the denoising network is only trained for graphs that satisfy the desired property.\n\nIn sampling, even though the posterior term of the edge absorbing noise model ensures the reverse as an edge insertion process (this is a direct implication from using eq. 6 in eq. 5), it does not guarantee that the successive graphs remain within the domain of graphs which satisfy the desired property. \nIn fact, since the denoising neural network is not a perfect edge predictor and the edges are sampled independently, sometimes we obtain intermediate graphs that are outside of such domain, inducing out-of-distribution prediction to the denoising neural network for the next step. To counter this, the projector is used to push back the graph generative trajectory to the domain where the model was actually trained. Note that the projector is only used to correct the trajectory when it gets out of the desired domain and does not interfere whenever the trajectory is within domain. Therefore, the projector is actually reducing the discrepancy between training and sampling processes and promoting in-distribution prediction for the denoising neural network, resulting in improved performance both in terms of sample quality and validity. \n\nThese results are aligned with the intuition provided in other constrained diffusion models for continuous state-spaces that also empirically validated the benefit of promoting the match of distributions between training and sampling [1,2,3].\n\n[1] - Lou, Aaron, and Stefano Ermon. \"Reflected diffusion models.\" ICML, 2023.\n\n[2] - Fishman, Nic, et al. \"Metropolis Sampling for Constrained Diffusion Models.\" NeurIPS, 2024.\n\n[3] - Liu, Guan-Horng, et al. \"Mirror diffusion models for constrained and watermarked generation.\" NeurIPS, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global Rebuttal

We kindly thank all the reviewers for their time and valuable feedback on our work. 

As a brief overview, our paper presents ConStruct, the first graph constrained diffusion framework to fully run in the discrete setting. ConStruct guarantees the satisfaction of edge-deletion invariant constraints through the application of a specific edge-absorbing noise model and a new projector operator. These components ensure matched training and sampling distributions, thereby improving performance over unconstrained models in synthetic datasets and real-world applications. 

___

In response to the reviewers' comments, we have updated our paper to include a series of clarifications and minor corrections to enhance the understanding of our work. We enumerate these updates below:
 
1) **Complexity Comparison**: in response to reviewers wnSX and FDH7, we provide a more explicit comparison between the underlying diffusion model and the overhead incurred by the projector in terms of complexity:

    "At each reverse step (out of a total of $T \approx 1000$ steps), the denoising network makes predictions for all nodes and pairs of nodes. This results in $O(n^2)$ predictions per step. Thus, the complexity of the sampling algorithm of the underlying discrete diffusion model is $O(n^2 T)$. In addition, the complexity overhead imposed by the projector is $O(N V)$. Here, $V$ represents the complexity of the property satisfaction algorithm, and $N$ is the number of times this algorithm is applied. So, in total, we have $O(n^2T + NV)$.

    Our analysis in Appendix C shows that incremental property satisfaction algorithms have notably low complexity. For instance, in cases like acyclicity, lobster components, and maximum degree, we have $V=O(|E_\text{added}|)$. Since the projector adds one edge at a time, we have $V=O(1)$. Additionally, since the blocking edge hash table limits us to perform at most one property satisfaction check per newly proposed edge (either we have never tested it or it is already blocked), $N$ corresponds to the total number of different edges proposed by the diffusion model across the whole reverse process. Thus, we necessarily have $N \leq n^2$. For these reasons, we directly find $O(N V) \ll O(n^2 T)$, highlighting the minimal overhead imposed by the projector compared to the discrete diffusion model. This explains the low runtime overhead observed for ConStruct, as detailed in Section D.3 (9\% for graphs of the tested size).

    A reasonable assumption is that the model inserts $N = O(|E|)$ edges throughout the reverse process. This is for example true if the model is well trained and predicts the correct graph. Besides, most families of graphs are sparse, meaning that $\frac{|E|}{n^2} \to 0$ as $n\to \infty$. For example, planar and tree graphs have to satisfy $|E| / n^2 = O(1/n)$. Therefore, we can conclude that asymptotically $O(n^2T + NV) = O(n^2T)$, *i.e.*, the projector overhead becomes increasingly negligible relative to the diffusion algorithm itself as the graph size increases. This further highlights the scalability of our proposed method."

2) **Notation and Citations**: in response to reviewer FDH7, we add the definition of $\Delta^k$ as the $k$-simplex to the notation paragraph of the paper and we updated our citations of GraphARM and EDGE to their published version;

3) **Limitations on Constraints**: in response to all reviewers, we provide more information regarding the limitation of ConStruct to edge-deletion invariant constraints:

    "In our work, we cover edge-deletion invariant properties. However, ConStruct can be easily extended to also handle edge-insertion invariant properties (*i.e.*, properties that hold upon edge insertion). This extension is particularly useful in domains where constraints such as having at least $n$ cycles in a graph can be important. To achieve this, we can simply "invert" the proposed framework: design the transition matrices with the absorbing state in an existing edge state (instead of the no-edge state) and a projector that removes edges progressively (instead of adding them) while conserving the desired property. 

    In the particular context of molecular generation, Appendix G illustrates that, while purely structural constraints can guide the generation of molecules with specific structural properties (e.g., acyclicity), for general properties shared by all molecules (e.g., planarity) they are too loose. In constrast, autoregressive models thrive in such setting due to the possibility of molecular node ordering (e.g., via canonical smiles) and the efficient incorporation of *joint node-edge* constraints. Therefore, even though it consists of a fundamentally different setting than the one considered in this paper, incorporating joint node-edge constraints into ConStruct represents an exciting future direction for our work."

4) **Impact on digital Pathology**: in response to reviewer ZwhZ, we extend the already existing impact statement (appendix J) with a more detailed stance in the potential impact of our work for the particular setting of digital pathology:

    "For the particular case of the digital pathology setting, while the generated graphs are able to mimic clinically relevant structures, they remain too small to have any direct clinical impact. Pathologists use whole-slide images for informed decisions, whose corresponding cell graphs typically comprise a total number of nodes 3 to 4 orders of magnitude above the graphs generated at this stage."

    If deemed appropriate by the reviewers, we are also considering moving Appendix J to the main body of the paper.
___
We reiterate our appreciation for the valuable feedback provided by the reviewers and hope that the updated version of the paper, along with the individual replies to each reviewer, have addressed the main concerns raised. We remain open to any further discussion.

Meta-review: This paper introduces ConStruct, a novel framework that incorporates structural constraints into graph generation models using a discrete graph diffusion process. By employing an edge-absorbing noise model and a projector operator, ConStruct ensures that generated graphs adhere to specific properties, such as planarity or acyclicity, which are crucial for practical applications. The framework demonstrates a significant improvement in the validity of generated graphs, as evidenced by experiments on both synthetic benchmarks and real-world datasets, such as digital pathology, showing a substantial increase in graph validity.

The reviewers unanimously recommend that this manuscript be accepted. However, they also suggest including some relevant baselines and conducting a theoretical analysis of the sample complexity. The authors are advised to incorporate the reviewers’ feedback when preparing the final version of the paper.
Decision: Accept (poster)