Generative Modelling of Structurally Constrained Graphs

Authors: manuel  madeira
pascal  frossard
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 17:58:16

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.

Main paper: 
 introduction: 
 Learning how to generate realistic graphs that faithfully mirror a target distribution is crucial for tasks such as data augmentation in network analysis or 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 a priori knowledge about specific properties of the target distribution of graphs. Incorporating such knowledge into generative models is a natural approach to enforce the generated graphs to comply with the domain-specific properties. Indeed, common generative models, even when conditioned towards graph desired properties, fail to offer guarantees. This may however become particularly critical in settings where noncompliant graphs can lead to real-world application failures. Many of these desired properties are edge-related, i.e., 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 are upper bounded to effectively prevent the emergence of superspreaders and mitigate the risk of infectious disease outbreaks [32, 1] . In graph generation, Figure 1 : Constrained graph discrete diffusion 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 on a 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, 64, 10] . Notably, ConStruct is designed to preserve both the forward and reverse processes of the diffusion model within distribution with respect to a specified structural property. 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 process and the reverse process as an edge insertion process. Simultaneously, the projector ensures that the inserted edges in the reverse process, predicted by a 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 its efficiency by leveraging incremental constraint satisfaction algorithms, as opposed to their full graph versions, and a blocking edge hash table to avoid duplicate constraint property satisfaction checks. These two components enable a 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 real-world applications, we evaluate the 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 demonstrate a significant improvement in cell graph generation with ConStruct compared to unconstrained methods [52] , notably achieving an increase of up to 71.1 percentage points in terms of cell graph va-lidity. These results open new venues for innovative data augmentation techniques and novel instance discovery, addressing a key challenge in digital pathology and real-world applications in general. 1 
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 (e.g., VAEs [40, 74, 78, 37] , 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 as 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 on graph spectral properties to capture global structural characteristics 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-satisfying set at each reverse step. This approach can impose structural and molecular properties for which closed-form projections can 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 a node-wise maximum degree hard constraint due to its degree guidance but it is limited to this particular property. Similarly, GraphARM [41] , a 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 our knowledge, ConStruct consists of the first constrained graph discrete diffusion framework covering a broad class of structural (potentially combinatorial) constraints. 
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.We first introduce the mathematical notation adopted in the paper.< l a t e x i t s h a 1 _ b a s e 6 4 = " 0 K1 K c Z q 4 p p A + K T m J M R 7 J R d L R + v o = " > A A A C G H i c b V D L S g M x F M 3 U V 6 2 v q k s 3 w S J U q H V G p L o s u q j L C v Y B f Z F J 0 z Y 2 M x m S O 0 I Z 5 j P c + C t u X C j i t j v / x v S x 0 N Y D g Z N z 7 u X e e 9 x A c A 2 2 / W 0 l V l b X 1 j e S m 6 m t 7 Z 3 d v f T + Q V X L U F F W o V J I V X e J Z o L 7 r A I c B K s H i h H P F a z m D m 8 n f u 2 J K c 2 l / w C j g L U 8 0 v d 5 j 1 M C R u q k z 5 s y Y I q A V D 7 x W F R W 8 p F R 8 4 u z 5 R x u D g h E p b g d w Z k T 5 3 C p D a e d d M b O 2 1 P g Z e L M S Q b N U e 6 k x 8 2 u p K H H f K C C a N 1 w 7 A B a E V H A q W B x q h l q F h A 6 J H 3 W M H S y h W 5 F 0 8 N i f G K U L u 5 J Z Z 4 P e K r + 7 o i I p / X I c 0 2 l R 2 C g F 7 2 J + J / X C K F 3 3 Y q 4 H 4 T A f D o b 1 A s F B o k n K e E u V y Y G M T K E U M X N r p g O i C I U T J Y p E 4 K z e P I y q V 7 k n U K + c H + Z K d 7 M 4 0 i i I 3 S M s s h B V 6 i I 7 l A Z V R B F z + g V v a M P 6 8 V 6 s z 6 t r 1 l p w p r 3 H K I / s M Y / b A G f 9 w = = < / l a t e x i t > Projector(P, Ĝt 1 , G t ) < l a t e x i t s h a 1 _ b a s e 6 4 = " K k 3 J B i 3 6 u O 9 z w I u l 1 O r p O 1 Z N S x U = " > A A A B 6 n i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K R I 9 B D 3 q M a B 6 Q r G F 2 M k m G z M 4 u M 7 1 C W P I J X j w o 4 t U v 8 u b f O E n 2 o I k F D U V V N 9 1 d Q S y F Q d f 9 d n I r q 2 v r G / n N w t b 2 z u 5 e c f + g Y a J E M 1 5 n k Y x 0 K 6 C G S 6 F 4 H Q V K 3 o o 1 p 2 E g e T M Y X U / 9 5 h P X R k T q A c c x 9 0 M 6 U K I v G E U r 3 d 8 8 Y r d Y c s v u D G S Z e B k p Q Y Z a t / j V 6 U U s C b l C J q k x b c + N 0 U + p R s E k n x Q 6 i e E x Z S M 6 4 G 1 L F Q 2 5 8 d P Z q R N y Y p U e 6 U f a l k I y U 3 9 P p D Q 0 Z h w G t j O k O D S L 3 l T 8 z 2 s n 2 L / 0 U 6 H i B L l i 8 0 X 9 R B K M y P R v 0 h O a M 5 R j S y j T w t 5 K 2 J B q y t C m U 7 A h e I s v L 5 P G W d m r l C t 3 5 6 X q V R Z H H o 7 g G E 7 B g w u o w i 3 U o A 4 M B v A M r / D m S O f F e X c + 5 q 0 5 J 5 s 5 h D 9 w P n 8 A K K O N v A = = < / l a t e x i t > G t< l a t e x i t s h a 1 _ b a s e 6 4 = " q I t m a o e l 9 k Z G L r 7 5I 0 i 6 R D z Q o N 4 = " > A A A B 9 H i c b V D J S g N B E K 2 J W 4 x b 1 K O X x i B 4 M c y I R I 9 B D 3 q M Y B Z I x t D T 6 U m a 9 C x 2 1 w T C M N / h x Y M i X v 0 Y b / 6 N n e W g i Q 8 K H u 9 V U V X P i 6 X Q a N v f V m 5 l d W 1 9 I 7 9 Z 2 N r e 2 d 0 r 7 h 8 0 d J Q o x u s s k p F q e V R z K U J e R 4 G S t 2 L F a e B J 3 v S G N x O / O e J K i y h 8 w H H M 3 Y D 2 Q + E L R t F I b m d A M b 3 N H l M 8 c 7 J u s W S X 7 S n I M n H m p A R z 1 L r F r 0 4 v Y k n A Q 2 S S a t 1 2 7 B j d l C o U T P K s 0 E k 0 j y k b 0 j 5 v G x r S g G s 3 n R 6 d k R O j 9 I g f K V M h k q n 6 e y K l g d b j w D O d A c W B X v Q m 4 n 9 e O 0 H / y k 1 F G C f I Q z Z b 5 C e S Y E Q m C Z C e U J y h H B t C m R L m V s I G V F G G J q e C C c F Z f H m Z N M 7 L T q V c u b 8 o V a / n c e T h C I 7 h F B y 4 h C r c Q Q 3 q w O A J n u E V 3 q y R 9 W K 9 W x + z 1 p w 1 n z m E P 7 A + f w C i r J I H < / l a t e x i t > Ĝt 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " c M G C y 1 k F P + z n k V H r v V 6 1 z K m M 4 P k = " > A A A B 7 n i c b V D L S g N B E O y N r x h f U Y 9 e B o P g x b A r E j 0 G P e g x g n l A s o b Z y S Q Z M j u 7 z P Q K Y c l H e P G g i F e / x 5 t / 4 y T Z g y Y W N B R V 3 X R 3 B b E U B l 3 3 2 8 m t r K 6 t b + Q 3 C 1 v b O 7 t 7 x f 2 D h o k S z X i d R T L S r Y A a L o X i d R Q o e S v W n I a B 5 M 1 g d D P 1 m 0 9 c G x G p B x z H 3 A / p Q I m + Y B S t 1 L x 9 T P H M m 3 S L J b f s z k C W i Z e R E m S o d Y t f n V 7 E k p A r Z J I a 0 / b c G P 2 U a h R M 8 k m h k x g e U z a i A 9 6 2 V N G Q G z + d n T s h J 1 b p k X 6 k b S k k M / X 3 R E p D Y 8 Z h Y D t D i k O z 6 E 3 F / 7 x 2 g v 0 r P x U q T p A r N l / U T y T B i E x / J z 2 h O U M 5 t o Q y L e y t h A 2 p p g x t Q g U b g r f 4 8 j J p n J e 9 S r l y f 1 G q X m d x 5 O E I j u E U P L i E K t x B D e r A Y A T P 8 A p v T u y 8 O O / O x 7 w 1 5 2 Q z h / A H z u c P y S y P O g = = < / l a t e x i t > G t 1 < l a t e x i t s h a 1 _ b a s e 6 4 = " v 7 G e 2 Q 6 y / v Y f 3 l F a + w P r T 9 / K 7 + k = " > A A A C A H i c b V C 7 S g N B F J 2 N r x h f q x Y W N o N B i I V h V y R a B i 1 i G c E 8 I N k s s 5 P Z Z M j s g 5 m 7 Q l i 3 8 V d s L B S x 9 T P s / B s n j 0 K j B y 4 c z r m X e + / x Y s E V W N a X k V t a X l l d y 6 8 X N j a 3 t n f M 3 b 2 m i h J J W Y N G I p J t j y g m e M g a w E G w d i w Z C T z B W t 7 o e u K 3 7 p l U P A r v Y B w z J y C D k P u c E t C S a x 7 E b h e G D E i p 1 k v h 1 M 7 w A 6 7 1 4 M Q 1 i 1 b Z m g L / J f a c F N E c d d f 8 7 P Y j m g Q s B C q I U h 3 b i s F J i Q R O B c s K 3 U S x m N A R G b C O p i E J m H L S 6 Q M Z P t Z K H / u R 1 B U C n q o / J 1 I S K D U O P N 0 Z E B i q R W 8 i / u d 1 E v A v n Z S H c Q I s p L N F f i I w R H i S B u 5 z y S i I s S a E S q 5 v x X R I J K G g M y v o E O z F l / + S 5 l n Z r p Q r t + f F 6 t U 8 j j w 6 R E e o h G x 0 g a r o B t V R A 1 G U o S f 0 g l 6 N R + P Z e D P e Z 6 0 5 Y z 6 z j 3 7 B + P g G F 6 6 V c g = = < / l a t e x i t > p ✓ (G t 1 |G t )Figure 2 : Projector operator. At each iteration, we start by sampling a candidate graph Ĝt-1 from the distribution p θ (G t-1 |G t ) 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 in this illustration. In the end of the reverse step, we find a graph G t-1 that is guaranteed to comply with such property.Notation We define a graph as G = (X, E), where X and E 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 E of cardinalities b and c, respectively. Thus, x i denotes the node attribute of node i and e ij the edge attribute of the edge between nodes i and j. WithH k = {v = (v 1 , . . . , v k ) | v i ∈ {0, 1}, k i=1 v i = 1}, their corresponding one-hot encodings are then x i ∈ H b and e ij ∈ H c+1 , since we consider the absence of edge between two nodes as an edge type ("no edge" type). These are stacked in tensors X ∈ {0, 1} n×b and E ∈ {0, 1} n×n×(c+1) , respectively. So, equivalently to the set notation, we also have G = (X, E). Additionally, we define the probability simplex,∆ k = {(λ 0 , λ 1 , . . . , λ k-1 ) ∈ R k | λ i ≥ 0 for all i, k-1 i=0 λ i = 1}.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 are composed of two main processes: a forward and a reverse one. The forward process consists of a Markovian noise model, q, with T timesteps, that allows to progressively perturb a clean graph G to its noisy version G t , where t ∈ {1, . . . , T }. This process is typically modelled independently for nodes and edges. The reverse process consists of the opposite development, starting from a fully noisy, G T , and iteratively refining it until a new clean sample is generated. This process uses a denoising neural network (NN), the only learnable part of the diffusion model. The NN is trained to predict a 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 p θ (G t-1 |G t ), 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 G 0 . Both processes are illustrated in Figure 1 .In some tasks, we are interested in 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., in drug design). Despite the remarkable expressivity of graph diffusion models, incorporating such constraints into their generative process remains a largely unsolved problem.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 are 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] .A 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 a boolean-valued application defined on graphs, referred to as a property. P is said to be edge-deletion invariant if, for any graph G and any subset of edges Ẽ ⊂ E, it satisfies:P (G) = True =⇒ P (G ′ ) = True, with G ′ = (X, E \ Ẽ).Many properties that are observed in real-world scenarios are 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] , we 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, 1] . Finally, it is 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 on two main components: an edge-absorbing noise model and a projector. These two components are described in detail below.Our goal is to design a forward process that yields noisy graphs that necessarily satisfy the target property. This process is typically modelled using transition matrices. Thus, [Q t X ] ij = q(x t = j|x t-1 = i) corresponds to the probability of a node transitioning from type i to type j. Similarly, for edges we have [Q t E ] ij = q(e t = j|e t-1 = i). These are applied independently to each node and edge, yielding q(G t |G t-1 ) = (X t-1 Q t X , E t-1 Q t E ). Consequently, we can directly jump t timesteps in the forward step through the categorical distribution given by:EQUATIONwith QtX = Q 1 X . . . Q t X and Qt E = Q 1 E . . . Q t E .Noising a graph amounts to sampling a 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.1), we propose the utilization of an edge-absorbing 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 a limit distribution that yields graphs without edges. Therefore, we obtain the following transition matrices:EQUATIONwhere α t and α t ABS transition from 1 to 0 with t according to the popular cosine scheduling [59] and the mutual-information-based noise schedule (α t = 1 -(T + t + 1) -1 ) [4] , respectively. The vectors 1 b ∈ {1} b and 1 c ∈ {1} c+1 are filled with ones, and m ′ X ∈ ∆ b and e ′ E ∈ H c+1 are row vectors filled with the marginal node distribution and the one-hot encoding of the no-edge state, respectively.The reverse process of the diffusion model is fully characterized by the distribution p θ (G t-1 |G t ). We detail how to build it from the predictions of a 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 a noisy graph G t at timestep t, we do not accept directly Ĝt-1 , sampled from p θ (G t-1 |G t ), as the one step denoised graph. Instead, we iteratively insert the newly added edges to Ĝt-1 in a random order, discarding the ones that lead to the violation of the target property. Therefore, we only have G t-1 = Ĝt-1 if none of the candidate edges breaks the target property. We refer to the operator that outputs G t-1 provided Ĝt-1 and G t by discarding the violating edges as the projector. Its implementation is illustrated in Figure 2 and described in 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.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 G 1 and G 2 by GED(G 1 , G 2 ) (see Definition B.1).Theorem 1. (Simplified) Let G t-1 = Projector(P, Ĝt-1 , G t ) be the set of all possible one-step denoised graphs outputted by ConStruct. If we define G * as any optimal solution of:EQUATIONC = {G ∈ G|P (G) = T rue, G ⊃ G t }and G is the set of all unattributed graphs, then G * can be recovered by our projector, i.e., G * ∈ G t-1 .The relationship between the projector, the candidate element Ĝt-1 (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 in 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 a 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 t : to make such problem efficiently approachable, we use the previous iterate, G t , which we know by construction that verifies the target property, as a 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 t ⊂ G t-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 a given timestep. This sacrifices the tractability of an evidence lower bound for the diffusion model's likelihood. In exchange, it conserves all the sampled graphs throughout the reverse process in the constrained domain. Therefore, the 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.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 an 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 are O(1), causing minor overhead. Since we 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 2 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 to its required high values (T ≈ 10 3 ).Incremental Algorithms Our reverse process consists solely of edge insertion steps, making it wellsuited for the application of incremental algorithms. These algorithms efficiently check whether newly 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 O(α(q, n)), where q is the total number of operations (edge queries and insertions), and α denotes the inverse-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(n2 ) 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 total number of times this algorithm is applied throughout the reverse process. So, in total, we have O(n 2 T + N V ). 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 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. 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 O(|E|/n 2 ) → 0 as n → ∞. For example, planar and tree graphs can be shown to satisfy |E|/n 2 = O(1/n). Thus, we necessarily have N ≤ n 2 . For these reasons, we directly find O(N V ) ≪ 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 Appendix D.3 (9% for graphs of the tested size). Therefore, we can conclude that asymptotically O(n 2 T + N V ) = O(n 2 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. 
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 a real-world scenario with digital pathology data.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 connected graphs without cycles (tree graph); and the lobster dataset [46] , composed of connected graphs without cycles, where no node is 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.1 and HSpectre to refer to the model proposed by Bergmeister et al. [7] .Regarding performance metrics, we follow the evaluation procedures from Martinkus et 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) 2 for the node degrees (Deg.), clustering coefficients (Clus.), orbit count (Orbit), eigenvalues of the normalized graph Laplacian (Spec.), and statistics from a 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-isomorphic to each other (Unique), the proportion that are non-isomorphic to any graph in the training set (Novel), Table 1 : Graph generation performance on 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 are 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 0. We recompute the train set MMDs according to our splits but, for fairness, in the retrieved methods the average ratio metric is not recomputed. and the proportion of generated graphs that are valid (Valid). Graphs are considered valid if they are 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 1 ).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-art results in both average ratio and V.U.N. metrics. The lower novelty and uniqueness values (<100%) are attributed to the dataset's smaller size. In 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 Table 2 : Graph generation performance on 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.Low TLS Dataset Model Ratio ↓ Conn. ↑ Planar ↑ V.U.N. ↑ κ(0) ↓ κ(1) ↓ κ(2) ↓ κ(3) ↓ κ(4) ↓ κ(5) ↓ TLS Valid ↑Train set 1.0 100 100 0.0 0.6928 0.0000 0.0000 0.0000 0.0000 0.0000 100Baseline [52] 194.6 ±3.0 50.3 ±0.7 10.0 ±0.5 0.0 ±0.0 0.6256 ±0.0228 0.2350 ±0.0000 0.2350 ±0.0000 0.0470 ±0.0470 0.0000 ±0.0000 0.0000 ±0.0000 0.0 ±0.0 GraphGen [24] 212.7 ±4.2 100.0 ±0.0 33.3 ±0. 5 33.0 ±1.8 0.7354 ±0.0220 0.1880 ±0.0470 0.0470 ±0.0470 0.0000 ±0.0000 0.0000 ±0.0000 0.0000 ±0.0000 33.3 ±0.5 BiGG [14] 132.0 ±6.3 99. 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.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 to 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 c = 1. We explore two datasets: one comprising graphs with high TLS content and another consisting of graphs with low TLS content, based on domain-specific 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.The TLS embedding, κ = [κ 0 , . . . , κ 5 ] ∈ R 6 , has been proposed to quantify the TLS content in a cell graph [69, 52] . See Appendix F.3 for more details. Based on this metric, we define a graph G to contain low TLS content if k 1 (G) < 0.05 and high TLS content if k 2 (G) > 0.05 [52] . To evaluate the generative performance, we adopt the average ratio for structural graph statistics (Ratio) and V.U.N. metrics used in Section 4.1. Here we consider a planar and connected graph as a valid graph. Thus, we explicitly present the proportion of generated graphs that are connected (Conn.) and (Planar). Furthermore, for a biologically meaningful evaluation of the generated cell graphs, we use the domain metrics. We report the MMD between the distributions of the components of κ. 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.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 1-hop baseline model, while capturing the node type dependencies to some extent, as illustrated by the MMD on the components of κ, 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 likelihood-based variants of ConStruct, as well as some ablations to the projector in Appendix H. 
limitations and future directions: 
 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 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 in 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 (e.g., acyclicity), for general properties shared by all molecules (e.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 a 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 scalability for generating larger graphs. 
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 limited 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 a given graph into a combinatorial subspace in an efficient and theoretically grounded manner. Through several experiments on benchmark datasets, we showcase 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-specific knowledge into graph generative models, thereby paving the way for their application in real-world scenarios. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a 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 a direct risk of misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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? • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this section, we further detail the design of the graph discrete diffusion model used to illustrate the constraining framework of ConStruct.The denoising neural network is trained using the cross-entropy loss between its predicted probabilities for each node and edge types, pG = (p X , pE ) and the actual node and edge types of a clean graph, G = (X, E):EQUATIONwhere λ 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, GNN θ , 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 extra features on the noisy graphs that otherwise the GNN θ would not be able to capture. Following Vignac et al. [79] , these are fed as a supplementary input to the denoising network (see Algorithm 1 and Algorithm 3), further enhancing its expressivity beyond the well-known limited representational power of GNN architectures [84, 57] . More concretely, 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 in 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-Adar index to aggregate local neighborhood information and the shortest distance between nodes to encode node interactions. Due to computational limitations, we only consider information within a 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, all the necessary elements are in place for the training of the diffusion model, which is defined in Algorithm 1.Input: Graph dataset D repeat Sample G = (X, E) ∼ D; Sample t ∼ U(1, ..., T ); Sample G t ∼ X Qt X × E Qt E ; h ← f (G t , t) ; // Compute extra features pX , pE ← GNN θ (G t , h); loss ← CE(p X , X) + λ CE(p E , E);optimizer. step(loss); until convergence of GNN θ ;The distribution p θ (G t-1 |G t ) fully defines the reverse process. Under an independence assumption between nodes and edges, this distribution can be modelled as:EQUATIONTo compute each of these terms, we use the GNN θ predictions through the following marginalization:EQUATIONwhere pX i (x) denotes the GNN θ predicted probability of node i being of type x. Similarly, for the edges we have p θ (e t-1 ij |G t ) = e∈E p θ (e t-1 ij |e ij = e, G t ) pE ij (e). To compute the missing term in Equation ( 6), we equate it to the posterior term of the forward process:EQUATIONwhere ′ denotes transposition.In this section, we first introduce the algorithm describing the proposed projector operator in Algorithm 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 is shown in Algorithm 3.Algorithm 2: Projector Input: Constraining property P , noisy graph G t = (X t , E t ), and candidate graph Ĝt-1 = ( Xt-1 , Êt-1 )G t-1 ← ( Xt-1 , E t ); E ′ ← Êt-1 \ E t ; // Get candidate edges repeat Sample e ′ ∼ E ′ ; if P (G t-1 . insert(e ′ )) then G t-1 ← G t-1 . insert(e ′ ) ;// Insert only valid edges end // Sample number of nodes Sample G T ∼ q X (n) × q E (n) ; // Sample from limit distributionE ′ ← E ′ \ {e ′ }; until E ′ = ∅; return G t-1 ;for t = T to 1 do h ← f (G t , t) ; // Compute extra features pX , pE ← GNN θ (G t , h); Ĝt-1 ∼ p θ (G t-1 |G t ) ; // Sample from distribution in Equation (5) G t-1 ← Projector(P, Ĝt-1 , G t ); end Store G 0 ; endIn this section, we theoretically analyse the projector. We start by defining a notion of distance between graphs [68] . Definition B.1. Let G 1 and G 2 be two unattributed graphs. The graph edit distance with uniform cost, denoted by GED(G 1 , G 2 ), is defined as: 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 at 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.GED (G 1 , G 2 ) = minAdditionally, we use the notationG ⊃ G ′ to denote that G ′ = (X ′ , E ′ ) is a subgraph of G = (X, E),i.e., that up to an isomorphism, we have E ⊃ E ′ and X = X ′ . For brevity, we slightly abuse notation and also define the union between a 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.,G ∪ E ′ = G ′ = (X, E ∪ E ′ ). Similarly, we have G \ E ′ = G ′ = (X, E \ E ′ ).The next results are organized in the following way: the first theorem proves that for any edgedeletion invariant constraining property (Definition 3.1), our projector can retrieve a graph that results from a projection onto the constrained set 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:• P be the edge-deletion invariant (Definition 3.1) constraining property of the projector; • G t be a noisy graph obtained at timestep t;• Ĝt-1 be a sampled graph from p θ (G t-1 |G t ), i.e., the one-step denoised candidate graph directly proposed by the diffusion model when taking G t as input; • G t-1 = Projector(P, Ĝt-1 , G t ) 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:EQUATIONwhere C = {G ∈ G|P (G) = T rue, G ⊃ G t }, with G the set of all unattributed graphs. Then, (G * , e * ) can be recovered by our projector, i.e. G * ∈ G t-1 .Proof. If Ĝt-1 ∈ C, the theorem is trivially verified since the output of the projector is directly Ĝt-1 , as well as the solution of the minimization problem. Therefore, for the rest of the proof, we only consider the case Ĝt-1 / ∈ C. Now, since the reverse process of the diffusion model is an edge insertion process, we have Ĝt-1 = G t ∪ E candidate ⊃ G t . Also, we notice that the projector amounts to randomly remove the edges that are not in G t from Ĝt-1 until we find a graph within the constraint set (equivalently, it entails adding as many edges as possible to G t while ensuring that the graph remains within the constraint set). Thus, it suffices to prove that for (G * , e * ) we necessarily have an optimal edit path e * = (e * 1 , ..., e * k ) from Ĝt-1 to G * exclusively composed of edge deletions. In this case, our projector can necessarily produce G * . Let (G * , e * ) be such a solution, and define G * :i the graph resulting from the i th first edits e * :i = (e * 1 , ..., e * i ) with i ≤ k. We will prove by induction that, for all 1 ≤ i ≤ k, e * :i is only composed of edge deletions such that G t ⊂ G * :i . i = 1: Since Ĝt-1 / ∈ C and Ĝt-1 ⊃ G t , we have that P ( Ĝt-1 ) = F alse. As P is edge-deletion invariant, inserting any set of edges E to Ĝt-1 implies thatEQUATIONTherefore, we have:EQUATION= minEQUATION≤ minEQUATION= minEQUATION= minEQUATIONThus, we conclude that any edge insertions would take us further away from the constraint set.Therefore, e * 1 cannot represent an edge insertion. However, it could still be an edge deletion such that G t ̸ ⊂ G * :1 In this case, an extra edge insertion would be necessary to recoverEQUATIONContrarily, if e * 1 is an edge deletion such that G t ⊂ G * :1 , we have:EQUATIONsince G t ⊂ G * :1 ⊂ Ĝt-1 . Therefore, we verify the intended property for i = 1.1 < i ≤ k: We have G * :i-1 / ∈ C because P (G * :i-1 ) = F alse.Otherwise G * :i-1 would be the solution since G t ⊂ G * :i-1 . Hence for any set of inserted edges E, minEQUATIONimplying that e * i is an edge deletion. By the same token, if G t ̸ ⊂ G * :i , then necessarily an extra insertion edit would be necessary to recover G t further in G * , so we have again:EQUATIONwhich, as seen before, is suboptimal. Thus, e * i is an edge deletion such that G t ⊂ G * :i . By noticing that G * :k = 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 t leads to 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 t-1 is actually a solution of the optimization problem in Theorem 1. In this proof, we use the concept of connected component of a 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 a connected component. Theorem 2. Under the same conditions of Theorem 1, if P returns true for graphs with no cycles, we have:G t-1 = argmin G∈C GED( Ĝt-1 , G).Proof. Following the proof of Theorem 1, if we define again Ĝt-1 = G t ∪ E candidate , we have:min G∈C GED( Ĝt-1 , G) = min (G t ∪E G )∈C GED(G t ∪ E candidate , G t ∪ E G ) = min {E G | P (G t ∪E G )=True, E G ⊂Ecandidate} |E candidate \ E G | = max {E G | P (G t ∪E G )=True, E G ⊂Ecandidate} |E G |,where the first equality is just a change of variables and the second comes from E candidate ⊃ E G , as shown in Theorem 1. This shows that a solution to argmin G∈C GED( Ĝt-1 , G) maximizes the number of edges added to G t . This is a general result under the conditions of Theorem 1 and not specific for graphs with no cycles. We now want to show that any element of G t-1 is a solution to this optimization problem.We define |CC candidate | as the number of distinct connected components of G t reached by E candidate .We remark that the considered graphs all have the same fixed number of nodes. A well-known result for graphs without cycles is that, under the provided setting, the maximum number of edges from E candidate that we can insert is |CC candidate | -1, i.e., we sequentially insert an edge per pair of separate connected components. Thus, we have:max {E G | P (G t ∪E G )=True, E G ⊂Ecandidate} |E G | ≤ |CC candidate | -1.On the other hand, the only edges from E candidate that the projector rejects are 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 a graph Overall, Theorem 1, Theorem 2, and the counter-examples in Figure 3 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 is still guaranteed to produce graphs that meet the specified structural constraints.G projector = G t ∪ E projector ∈ G t-As discussed in Section 3.5, utilizing the projector in the edge insertion reverse process (i.e., G t ⊂ G t-1 ) allows us 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 is no general efficient property satisfaction checker for all edge-deletion invariant properties. Consequently, we address each property on a case-by-case basis.Planar The best performing full property satisfaction algorithm known for planarity is O(n) [30] , while its fastest known incremental test has amortized running time of O(α(q, n)) [43] ("almost constant" complexity), where q is the total number of operations (edge queries and insertions), and α denotes the inverse-Ackermann function. 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% of the graphs are used in the train set and the remaining 20% are allocated to the test set. We use 20% of the train set as validation set. We note that for the lobster dataset, the original splits provided in the open-source code from Liao et al. [46] use the validation set as a subset of the train set, i.e., all the samples in the validation set are used to train.In contrast, we follow Martinkus et al. [54] 's protocol, isolating completely the validation samples from the train (again, 20% of the train split). In 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.These splits and the hyperparameters used for each model are provided in the computational implementation of the paper as 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 a learning rate of 0.0002 and weight decay of 1e-12 for all the experiments.All our experiments were run in a single Nvidia V100 32Gb GPUs. We present the training times of the diffusion model for each dataset in Table 3 . The baseline model for the digital pathology dataset does not use any GPU. It 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 of magnitude of training times is significantly larger than the one of sampling times, Table 3 provides a good estimate of the total computational resources required for this paper.A major advantage of our framework is that it does not interfere with the training of the diffusion model, preserving its efficiency. Therefore, there is no overburden in 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 of 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, a 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 is thus more computationally expensive when compared to their incremental versions employed by ConStruct. The complexity comparison between a full graph property check ran only once vs an incremental check for each added edge is property specific. However, the main bottleneck of the a posteriori filtering is that it wastes computational resources in case of graph rejection (i.e., in the case of a 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 an additional property check at the end. Furthermore, this procedure has to 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, so we can just check property satisfaction for the newly added edges (via incremental algorithm) that have not been checked yet (via edge blocking hashtable).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, described in Appendix C. 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 are more efficient than full-graph constraint checks, which is the typical case.ConStruct also outperforms the a posteriori filtering of unconstrained generation. In this case, we used an unconstrained model that generates constraint satisfying properties 97% (DiGress+ in Table 1 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 a much worse runtime. In such setting, ConStruct would be approximately 12 times more efficient in generating valid graphs than DiGress+. Additionally, this gap in sampling efficiency may become particularly critical in settings where the amount of generated graphs is much larger, as is the case for molecular generation (two orders of magnitude greater than in the settings with synthetic datasets, see Appendix G).In this section, we go through additional information related to the digital pathology datasets.Digital pathology consists of an advanced form of pathology that involves digitizing tissue slides into whole-slide images (WSI), allowing for computer-based 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, 71] . 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-graph based approaches have emerged as a 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 a lack of high-quality annotated samples, mostly due to their heavy ethical and privacy regulation. Besides, collecting these samples is remarkably costly, both economically and in terms of time and labor required [36] . Most of the discriminative approaches are also instance-based. 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-based 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-the-shelf graph generative model (DiGress) is explored and in a proprietary dataset.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 3 . 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 to 9 more generic phenotypes in a biologically 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.Regarding edges, we followed the typical procedure for cell-graphs in digital pathology [36, 35, 2, 82 ]: first we used Delaunay triangulation on the cell positions to build them. Then, we discard edges longer than 25 µ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 c = 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-overlapping subgraphs centered at nodes whose class is "B-cell" from the whole-slide graphs.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 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 B cells, from the WSI graphs. This procedure is illustrated in Figure 4 .As mentioned in Section 4.2, the TLS content of a cell graph can be quantified using the TLS embedding, κ = [κ 0 , . . . , κ 5 ] ∈ R 6 [69, 52] . This TLS-like organization metric considers only edges between B and T-cells and classifies them into several categories: α edges link two cells of the same type, while γ j edges connect a B to a T-cell, where j is the number of B-cell neighboring the B-cell vertex (see Figure 4 ). Therefore, the entry i of κ is defined as the proportion of its γ edges whose index is larger than i:EQUATIONwhere |E BT |, |E α |, and |E γj | correspond to the number of edges whose both vertices are B or T-cells, of α edges and of γ j edges in a given graph, G. Note that, by definition, the entries of κ take values between 0 and 1 and are monotonically non-increasing with i. 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, κ. The non-deep learning method used as baseline for the digital pathology dataset follows Madeira et al. [52] . This model learns 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 train , i.e.:P (|X| = k) = |{G ∈ D train : |X| = k}| |D train | ,• Categorical distribution for the cell phenotypes, where the probability for each cell phenotype corresponds to its marginal probability in the dataset:P (Ph(ν) = ph i ) = G∈Dtrain |{ν ∈ X : Ph(ν) = ph i }| G∈Dtrain |X|, where Ph(ν) refers to the phenotype of node ν, and ph i denotes the specific phenotype labeled as i. These consist of the phenotypes described in Appendix F.2 with a fixed (arbitrary) order.• Bernoulli distribution for the edge type (no edge vs edge) conditioned on the phenotypes of its two vertices, again computed based on its marginal distribution in the train set.P (Edge | Ph(ν 1 ) = ph i , Ph(ν 2 ) = ph j ) = G∈Dtrain |{(v 1 , v 2 ) ∈ C(G) : (v 1 , v 2 ) ∈ E}| G∈Dtrain |C(G)| , where C(G) = {v 1 ∈ X : Ph(v 1 ) = ph i } × {v 2 ∈ X : Ph(v 2 ) = ph j } for 1 ≤ ph i < ph j ≤ 9.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 a 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.In many real world scenarios, we want to 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 a 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 to their cyclic counterparts. In fact, acyclic molecules are frequently encountered in natural products and pharmaceuticals, where their linear structures contribute 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, we 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 was trained with a 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 runs for each method and present their results in the format mean ± standard error of the mean. For each run, we generated 10000 molecules, following the protocol from Vignac et al. [79] . The FCD is computed using the official implementation from Preuer et al. [63] 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 a subset of the set 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 is 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.In this section, we perform some ablations to ConStruct/DiGress+ to further analyse its performance and explore methodological extensions to the proposed method.From Table 1 , we 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+ [absorbing] in Table 11 . We observe a significant decrease in 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 a 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 no clear evidence that an optimal noise model can be deduced a priori from dataset statistics [77] .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 a constraint satisfaction check for each potentially added edge at every forward pass, resulting in a prohibitive computational overhead.In constrast, we could also consider the opposite setting: only applying a posteriori modifications to graphs generated by the unconstrained model. Two possible alternatives emerge:• DiGress+ [rejection] -we 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, it 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 computational inefficiencies in Appendix D.3. Additionally, we see 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.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 t, p θ (e t-1 ij |G t ), to define an order by which we add the edges. Therefore, instead of uniformly sampling them at random, we propose two methods of integrating such information:• Deterministic: we add the edges with higher p θ (e t-1 ij |G t ) 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 p θ (e t-1 ij |G t ).We present the results for these likelihood-based variants of ConStruct in Table 11 . As we can observe, for all the analysed datasets, the three ConStruct variants are statistically equivalent in terms of performance. In terms of efficiency, there is no meaningful difference among the three methods: even though the uniformly random sampling does not have to access p(e t-1 ij |G t ), 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 B also holds for the stochastic likelihood-based 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(e t-1 ij | G t ), it always selects candidate edges by the same order. 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 of the projector in different timesteps.Here we visually compare the graphs from the different datasets to the ones generated by ConStruct.We provide plots of the sampled graphs from ConStruct for the different datasets: planar in Figure 6 , tree in Figure 7 , and lobster in Figure 8 . We provide plots of the sampled graphs from ConStruct for the low TLS content dataset in Figure 9 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 an edge insertion procedure. In this section, we provide some visualizations of intermediate graphs obtained throughout the reverse process for three different datasets: planar, tree, and lobster. In Figure 12 , we highlight the effect of the projector in rejecting the candidate edges that lead to property violation.The primary objective of this paper is to enhance graph generation methodologies by enabling the integration of hard constraints into graph diffusion models. Although this problem holds significance for several real-world applications, including digital pathology and molecular generation, as exemplified in the paper, as well as protein design, the potential implications extend to 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, we 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 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. The notation follows the one of the rest of the paper: we obtain G t-1 after applying the projector on Ĝt-1 , which in turn is obtained from G t through the diffusion model. From the new edges obtained in Ĝt-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 a fully trained model and use a trajectory length, T , smaller than usual, resulting in less accurate edge predictions.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal 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 or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Our code and data are available at https://github.com/manuelmlmadeira/ConStruct.To align with previous literature, we actually compute MMD 2 .Data retrieved from https://zenodo.org/records/7324285 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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 

2. Lack of complexity analysis. Instead, only the runtime measurement is provided.

3. This method might not be able to deal with large graphs.
questions: questions: Please answer my listed weakness above.
limitations: limitations: None.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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. 
- 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.
- 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.
- 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. 
- 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.
- ConStruct is limited to non-attributed structural constraints due to the edit distance formulation and thus, cannot be applied to important molecular constraints.

[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
questions: questions: See above weaknesses.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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. 

However, this limitation does NOT weaken the contribution of this paper and should be considered a future research direction of hard-conditioned graph generation.

**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.

**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.

**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.

[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.

[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*.
questions: questions: **Q1.** Please clarify the definition of $\Delta^b$ in Page 5, line 171.

**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? 

**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: limitations: The authors adequately discussed the limitations of the proposed method.

They 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.

Comments: title: Appreciation for Your Efforts and Feedback
comment: Dear Reviewers and Area Chairs,

Thank you for managing our submission. We are pleased to see that our rebuttal successfully addressed the reviewers' concerns. We greatly value the feedback provided, which has clearly enhanced the quality of our paper.

If there are any remaining issues or additional points that need further attention, please let us know. We really appreciate your time and consideration.

Best regards,

The Authors
We thank the reviewer for their time, constructive feedback, and the updated score. We will incorporate the additional discussions and clarifications into the revised version of the paper.
I thank the authors for providing additional discussion and clarifications regarding their work that positions their paper better in my opinion. I believe they should thus include all these points in their revised version. I don't think non-attributed settings is a major weakness but worth mentioning as a limitation and potential for future research. I will raise my scores now that I think we are on the same page.
[1] - Xie et al. "Topological evolution of surface transportation networks." Computers, Environment and Urban Systems, 2009.

[2] - Bhatt et al. "A framework for solving VLSI graph layout problems." Journal of Computer and System Sciences, 1984.

[3] - Simmons III et al. "Synthesis of the first topologically non-planar molecule." Tetrahedron Letters, 1981.

[4] - Jaume et al. "Histocartography: A toolkit for graph analytics in digital pathology." MICCAI Workshop on Computational Pathology. PMLR, 2021.

[5] - Gregory. "Understanding evolutionary trees." Evolution: Education and Outreach, 2008.

[6] - Seibold et al. "Modeling epidemics on a regular tree graph." Letters in Biomathematics, 2016.

[7] - Asthana, Rohan, et al. "Multi-conditioned Graph Diffusion for Neural Architecture Search." arXiv, 2024.

[8] - Zhang, Muhan, et al. "D-vae: A variational autoencoder for directed acyclic graphs." NeurIPS, 2019.

[9] - Sanchez et al. "Diffusion models for causal discovery via topological ordering." arXiv, 2022.

[10] - Jang et al. "Evaluating architectural changes to alter pathogen dynamics in a dialysis unit: for the CDC MInD-healthcare group." International Conference on Advances in Social Networks Analysis and Mining, 2019.

[11] - Kong et al. "Autoregressive diffusion model for graph generation." ICML, 2023.
**Comparison with PRODIGY**: We agree with the reviewer that the two methods can be used to address different sets of constraints and, more importantly, that the main difference between PRODIGY and ConStruct consists of the different tasks addressed by both, as accurately described by the reviewer. The fact that both tasks are different lead to fundamental differences in the two approaches. For example, PRODIGY does not have to necessarily guarantee constraint satisfaction, whilst ConStruct does.

The comment regarding guidance points towards our section G.2. There, we use the projector to control the generation of an unconstrained model (i.e., trained with a noise model that does not preserve the structural constraint across the forward process). This approach is similar to PRODIGY's procedure but uses our projector instead. Even though this approach accomplishes satisfactory performance, it is significantly outperformed by a ConStruct model (where the noise model preserves the constraint) in terms of validity: 81.3\% vs 99.8\%. As discussed in that section, this experiment is meaningful to reinforce the foundation upon which ConStruct is designed: matching the forward and reverse domains allows for in distribution prediction of the denoising neural network, improving constrained generation performance. We apologize if this reference was misleading.

To address the reviewer's concerns, we propose to extend our paragraph dedicated to PRODIGY of our related work section (ll. 80-87, page 3) to make a more explicit distinction between both methods on the different nature of constraints addressed and, specially, on the different tasks tackled by each of them.

**Contribution of the method**: We thank the reviewer for acknowledging the suitability of our method for application. Our intention with the provided theoretical analysis is to provide insights to the reader that underscore the complexity of the problem and substantiate the design of our projector. For instance, Theorem 1 implies that a deterministic projector based on edge sampling likelihoods from the diffusion model is not guaranteed to have the optimal graph in its output set, as elaborated in Appendix H.3. Also, Theorems 1 and 2 and the counter-examples in Figure 3 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 is *guaranteed* to produce graphs that meet the specified structural constraints. Considering this, we remain open to discussing and refining any specific claims in our manuscript that might be seen as overstated by the reviewer.

**Attributed settings**: We appreciate the reviewer’s opinion but do not fully understand why the absence of node feature-dependent constraints is seen as a *major* weakness. As argued in W7 of rebuttal, ConStruct targets applications where node ordering is not feasible. In contrast, node-edge joint constraints are primarily useful for constrained molecular generation, a domain where node ordering is possible and thus perfectly suited for autoregressive models. Due to their ability to perform very efficient validity checks at each step, these models already successfully solve such task. While integrating node-edge constraints is an interesting potential extension to ConStruct, we believe that our focus on structural constraints adresses our intended applications and does not constitute a fundamental weakness.

____

We believe that the constructive feedback provided by the reviewer has guided us toward addressing their concerns more effectively. In light of these improvements, we hope the reviewer might consider revising their score.
We thank the reviewer for the detailed reply to our rebuttal. We address the raised concerns below:

**Motivation**: We agree with the reviewer that the flexibility provided by the unsconstrained graph generation of mimicking any data distribution is extremely convenient. 
However, in many real-world scenarios, this flexibility alone is not sufficient to yield satisfactory performance without incorporating additional priors into the generative model. 
This approach is particularly relevant in data scarce settings — such as due to high costs, ethical/privacy concerns, or a lack of high-quality annotated data — or where instances that do not adhere to specified constraints are either infeasible or lack physical meaning.
Constrained generation is a valuable method for incorporating such priors by hard-constraining the hypothesis space to valid instances (in our cases, graphs), thereby reducing the search space and potentially enhancing the efficacy of the learning process. 
We note, nevertheless, that just enforcing such constraint does not identify the underlying distribution; instead, there is still the need to learn the underlying distribution within the constrained domain. 

As outlined in our rebuttal (W1), constrained generation indeed requires an explicit and unambiguous definition of the constraints. We understand the reviewer’s concerns about identifying structural constraints *a priori*, but we do not view this as a limitation. Instead, constrained generation is a practical choice for settings where practitioners have established explicit constraints through expertise or problem exposure and wish to leverage them for a more effective learning process. Typical sources of such constraints include the physics of the problem, application domain constraints, or detailed knowledge about the data acquisition process. We highlight several real-world examples (some mentioned in the paper) where such prior knowledge is available and can be effectively applied using ConStruct, showcasing its versatility.

- *Planarity*: design of road networks [1], chip design [2], biochemistry [3] or digital pathology [4].

- *Acyclicity*: evolutionary biology [5] or epidemiology [6]. Additionally, if we consider the extension of discrete diffusion for directed graphs, e.g. [7], for which ConStruct is still applicable, there are several domains where the generation of directed acyclic graphs is critical: neural architecture search or bayesian network structure learning [8], causal discovery [9], etc. 

- *Maximum Degree*: design of contact networks [10, 11].

**Comparison to SPECTRE**:
Even though we still see some relevant differences between ConStruct and SPECTRE - such as, 1) ConStruct enforces constraints by default, while SPECTRE requires learning such dependencies even with explicit structural information; or 2) SPECTRE uses spectral properties to inform the model about global graph structure, whereas ConStruct can still be used to constrain generation for local level properties (e.g., maximum degree) -, we agree with the reviewer that the latter is the first method, to the best of our knowledge, that recognizes the importance of explicitly incorporating structural information (other than locality biases from common GNNs) as powerful priors for the expressiveness of one-shot graph generative models. Therefore, we will add this discussion into our final version of the manuscript. We thank the reviewer for the constructive feedback.
Thanks for the rebuttal! However, I don't agree with the authors' views on certain topics and hope we can discuss and reach a conclusion. 

**Motivation:** The major problem I have with this is that the structural constraint of the underlying graphs must be known beforehand. As noted, this helps in the case of synthetic graphs which are specifically formed of such a constraint and maybe some generalizations can happen for specific use-cases as identified by authors for pathology graphs and planarity. However, the major benefit of graph generation is that it can approximate a distribution just from data. What this paper proposes is to include an additional constraint that identifies the underlying distribution. This is good if the proposed method is motivated as a way to simulate synthetic NP-hard structural distributions, which takes time to generate otherwise. However, in the absence of such a clear motivation and an expectation to generalize to real-world graphs, it is not clear how the users would be able to identify structural constraints of arbitrary graph distributions before training. 

**Comparison with SPECTRE:** SPECTRE trains generative model by explicitly conditioning the eigenspectrum of the training data. This explicit conditioning on the underlying distribution is similar to the idea of explicitly constraining on the structural constraint of planarity and acyclicity that the current paper looks at. For example, if we have graphs with 2 connected components, it can be inferred from the number of non-zero eigenvalues in the training graphs. However, this discussion is absent in the current work but is extremely important. 

**Comparison with PRODIGY:** This paper also requires further discussion that the authors have not acknowledged. The difference is not in continuous vs discrete or combinatorial vs not. PRODIGY constraints are also inherently combinatorial as opposed to what the authors are claiming. They have particularly considered P-space matroid constraints while ConStruct focuses on NP-hard constraints. However, more importantly, the difference is that ConStruct is a discrete diffusion model trained to generate graphs given a structural constraint on the distribution while PRODIGY aims to do plug-and-play controllable graph generation to satisfy arbitrary constraints. The authors have been inconsistent in claiming (with the guidance comment) that they may be doing the same problem as PRODIGY, then such an experimental validation would be essential to show.

**Contribution of the method:** The theorems that assist the proposed method are not quite generalizable. Theorem 1 barely shows that a satisfiable constrained graph can be sampled, which is also possible through a simple random sampling. Theorem 2, on the other hand, is specific to a single constraint. I agree that any such theoretical proof will be extremely hard to prove for a general graph constraint. However, in that case, the authors should not overclaim their contributions in terms of constraint satisfaction with discrete graphs. The experiments are strong enough to validate the method's usefulness. 

**Attributed settings:** I am not diminishing the contributions but I would like to keep my opinion that this is a major weakness in using the method in real-world settings.
We thank the reviewer for their time and the score update. We remain open to any further clarifications.
Thanks for the detailed responses. I hope the authors to thoroughly scrutinize the manuscript to ensure the notation system is correct and self-contain.

I raise my score to 7 because my Q2 is fully addressed. The setting is new and important, the proposed method is sounded. The logic flow of the paper is smooth. The theoretical analysis is adequate. 

I cannot give a higher rate because this paper is restricted to 'edge-deletion-invariant constraints', which is not general enough.
[1] - Mercado, Rocío, et al. "Graph networks for molecular design." Machine Learning: Science and Technology 2021