Scalable Generative Modeling of Weighted Graphs
Authors: Richard Williams
Eric Nalisnick
Andrew Holbrook
Venue: Accepted by TMLR ()

Abstract: Weighted graphs are ubiquitous throughout biology, chemistry, and the social sciences,  motivating the development of generative models for abstract weighted graph data using deep neural networks. However, most current deep generative models are designed for unweighted graphs and cannot be easily extended to weighted topologies. Among those that do incorporate edge weights, few consider a joint distribution with the topology of the graph.  Furthermore, learning a distribution over weighted graphs must account for complex nonlocal dependencies between both the edges of the graph and corresponding weights of each edge. We develop an autoregressive model BiGG-E, a nontrivial extension of the BiGG model, that learns a joint distribution over weighted graphs while exploiting sparsity to generate a weighted graph with $n$ nodes and $m$ edges in $O((n + m)\log n)$ time. Simulation studies and experiments on a variety of benchmark datasets demonstrate that BiGG-E best captures distributions over weighted graphs while remaining scalable and computationally efficient.

Published in Transactions on Machine Learning Research (October/2022 2005)
Scalable Generative Modeling of Weighted Graphs
Richard Williams
riwilliam344 Gucla edu
Deportment of Biostatistics
University of California, Los Angeles
Eric Nalisnick
natisnick@jha..om edu
Deportment of Computer Science
Johns Hopkins University
Andrew Holbrook
aholbroo Sucla edu
Department of Biostatistics
Universily of California, Los Angeles
Reviewed on OpenReview: https: /ptp::///pen/evveee. net/ forum? wwwp:://500000000000oeeeeeeeee..
Abstract
Weighted graphs are ubiquitous throughout biology, chemistry, and the social sciences, mo- tivating the development of generative models for abstract weighted graph data using deep neural networks. However, most current deep generative models are designed for unweighted graphs and cannot be easily extended to weighted topologies. Among those that do incor- porate edge weights, few consider joint distribution with the topology of the graph. Fur- thermore, learning distribution over weighted graphs must account for complex nonlocal dependencies between both the edges of the graph and corresponding weights of each edge. We develop an autoregressive model BiGG-E, a nontrivial extension of the BiGG model, that learns a joint distribution over weighted graphs while exploiting sparsity to generate a weighted graph with n nodes and m edges O((n + m) logn) time. Simulation studies and experiments on variety of benchmark datasets demonstrate that BiGG-E best captures distributions over weighted graphs while remaining scalable and computationally efficient.
1 Introduction
Graphs are useful mathematical structures for representing data in many domains, with applications rang- ing from modeling protein protein interactions (Keretsu & Sarmahi 2016) to predicting time spent. trallic (Stanojevic et al., 2018). A graph consists of of objects, called nodes, and their corresponding connec- tions, called edges, which represent the graph's topology. Edges may contain additional information in the form of edge features, which can be categorical - such bond types in molecular graphs (Jo et al. continuous such as branch lengths in phylogenetic trees (Semple et al. 2003). Edgge weights, in particular, edge features, and a graph with edge weights comprises a weighted graph.
2022)
are continuous single-dimension Weighted graphs hold many applications, such as in neuroscience (Barjuan et al. 2025), economics (Fagiolo
et al. 2010 social networks (Bellingeri et al. 2023 and phylogenetics (Bacle et al. 2025
Generative modeling of graphs is a vibrant research area, where weighted graphs require models that capture both topology and edge-weight distributions. Early approaches such as Erdös-Rénn Rényi (Erdós & Rényi 1959) and Srrabási-Albert models (Albert & Barabasi 2002) offer simple graph-generating mechanisms but fail to capture subtle dependencies observed between edges in real-world data. These limitations motivate the de- velopment of expressive deep generative models capable of learning complex, nonlinear relationships. Despite such advances, modeling graph distributions remains an ongoing challenge due to the combinatorial nature of graphs and complex dependencics among edges. Furthermore, although incorporating edge weights seems straightforward, jointly modeling discrete topology and contimoous weights introduces additional complexity, requiring the model to account. for dependencies both within and ween these two components.

---

Published in Transactions on Machine Learning Research (October/202)
Modern graph generative models including variational autoencoders (VAEs) Kipf & Welling 2016 Grover
et al.
2019), graph neural networks (Grover et al. 2019), autoregressive models (You et al. 2018 Liao et al. Li et al. 2018 Dai et al. 2020), and score-bases diffusion models (Niu et al. 2020 Jo et al. 2022
2019
Vignac ct al. 2023) primarily focus on unweighted graphs. Most limit their scope to modeling distributions over graph topology while offering limited insight into the joint modeling of topology and edge weights, and few provide scalable solutions for learning joint distributions over sparse weighted graphs. Furthermore, a significant computational bottleneck in graph generative modeling arises when jointly modeling all possible edge connections, which scales quadratically with the number of nodes. Hence, models that attempt to jointly model all possible edge connections are computationally slow and infeasible for even moderately sized graphs Autoregressive models factorize graph generation node-by-noch using a sequential decision process. BiGG, "Big Graph Generation" (Dai et al. 2020), augments this approach by directly generaling the edge set of sparse graphs, scaling to graphs with tens of thousands nodes. However, existing autoregressive methods, including BiGG, remain limited to unweighted graphs.
To address the need for efficient generative modeling over large weighted graphs, we introduce BiGG-E an autoregressive model that jointly generates both graph topologies and edge weights while preserving the scalability of its unweighted prodecessor, BiGG. We benchmark BiGG-E against three alternatives: (1) Adjacency-LSTM (Adj-LSTM), fully expressive but computationally inefficient model parameterized with a Long Short-Term Memory (LSTM; Hochreiter & Schmidhuber (1997) cell; (2) BiGG- MLP, & naive extension that appends encodings of weights to BiGG using a multilayer perceptron (MLP, Rumelhart et al. (1986)); and (3) BiGG+GCN, a two-stage model that decouples topology and weight generation.
Our contributions are as follows:
We propose BiGG-E, an application-agnosic generative model that learns joint distributions over sparse weighted graphs
We empirically demonstrate that BiGG-E maintains the efficient scaling of BiGG while outperform- ing BiGG-ML.P, AdJ-LSTM, and BiGG+GCN.
All BIGG extensions are orders of magnitude faster than Adj-LSTM and SparseDiff, a diffusion- model competitor.
We directly evaluate the joint and marginal generative performance of all models array of weighted graph distributions.
2 Background
2.1 Data
Let G = (ii....,Gigi) be an independent sample of weighted graphs from an unknown data-generating distribution p(G.), for I...., (G). Each weighted graph is defined as G, (Vi, E, W.), where fei...., Un. is the set of |V =n, n, nodes, E, V. V, is the set of E,1 m, edges, and W V2 V; - R maps edges to positive edge weights. For notational simplicity, we drop the subscript i, under the assumption that the graphs G; E G are independent and identically distributed.
For any edge (I, 1y) E E, the edge weight is (1,, uy) = wayi otherwise, it is zero. The weighted adjacency matrix W E Raxx has entries W(v,, w,). In the unweighted case, edge weights are when vy) E E and 0 otherwise. We denote the unweighted adjacency matrix by A, which encodes the graph's topology, and use W to specifically refer to the weighted adjacency matrix.
A weighted graph G under node ordering π is represented by its permuted weighted adjacency matrix W
from which the probability of observing G is given by p(G) = p(VVI n) Σ, P(W((G)) (Dai et al. 2020
Because summing over all n!! node permutations quickly becomes intractable, we follow Liao el al.
(0019)
and assume a single canonical ordering म, yielding the lower bound estimate p(G) ~ p(VV= = n)p(( W W=GG)..
Following Dai al. (2020), we estimate p([V| n) using a multinomial distribution over node counts in the training set, and model p( (=(C)) with deep autoregressive neural networks parameterized by 0. We assume all graphs are under the canonical ordering (G) and omit this notation moving forward.
2

---

Published in Transactions on Machine Learning Research (ottober/202)
2.2 Related Work
Weighted Graph Generative Models Although various models incorporate edge and node features in
the graph generative process, these features are typically categorical (Kipf & Welling 2016 Li et al.
2018
Kawai ct al. 2019) or are tailored to a specific class of graphs, such as protein graphs (Ingraham et al. 2019)
Furthermore, previous work on autoregressive models (You et al. 2018 Liao et al.) 2019 Dai et al. 2020
focuses exclusively on unweighted graphs. Most implementations on weighted graphs provide limited insight into the incorporation of edge weights. Graphite (Grover et al. 2019) proposes modeling weighted graphs by parameterizing Gaussian random variable, which introduces the possibility of infeasible negative weights. Although score-based models incorporate edge features into the graph generative process, these features are typically categorical (Vignac et al. 2023 or rely on thresholding to produce a weighted adjacency matrix W and only evaluate performance on the binarized adjacency matrix (Niu et al. 2020
Scalability Scaling generative models to graphs with thousands of nodes is an ongoing challenge, as the adjacency matrix A has (n²²) entries. In addition, many VAE (Grover et al. 2019) and diffussio (Niu et al. 2020 Vignac et al. 2023) models utilize graph neural networks, which perform convolutions over the entire adjacency matrix of the graph. SparseDiff (Qin et al. 2024) is a scalable diffuusion model on sparse graphs, interested in scaling to thousands of nodes.
but only scales to graphs with hundreds of nodes, while
Autoregressive models currently scale best with large graphs. While GraphRNN You et al. 2018 trains in Onn²) time despite using a breadth-first search ordering scheme to reduce computational overhead, GRAN Liao et al. 2019) trains in (n)) time by generating blocks of nodes the graph at a time, but trades this gain scalability for worsened sample quality as the model estimates edge densities per block of nodes. BIGG (Dai al.) 2020) leverages the sparsity of many real-world graphs and directly generates the edge set {ex} of A:
(A II po po(ealHeueeHh
(1)
BiGG trains on the order O(log n) time, generates an unweighted graph O(n + m) log time, and scales to graphs with up 50K nodes. Currently, BiGG and other autoregressive models remain limited to unweighted graphs, precluding the sampling of edge weights. These limitations motivate the need for scalable autoregressive model capable of modeling joint distributions over weighted graphs.
3 Methods and Contributions
3.1 Joint Modeling of Topology and Edge Weights
Previous autoregressive models produce unweighted graphs either by directly generating A You et al. 2018). or by directly generating the edge set (Dai et al. 2020). However, models learn over weighted adjacency matrices W. As such, we first define a joint distribution over the existence of an edge and its corresponding edge weight w. To do so, note that as w is only sampled when exists, we can naturally factor the joint probability po(e, w) of obscrving a weighted edge (e, w) as
pe(e, w) = po(e)po(wle),
(2)
where po(e) is the parameterized Bernoulli probability that an edge exists between two nodes, and pe (wle) is the probability of drawing corresponding weight given that e exists. Since w is assumed to be continuous, let Po(wle) represent the distribution of the random variable w with parameterized density fe(w). In the case where no edge exists and = 0, set w = 0 with probability 1; otherwise, if an edge exists and e e= draw a corresponding weight from a conditional distribution po (wle).
We parameterize the conditional distribution (o(w)e) as a normal random variable ele N 0) transformed with the softplus function Softplus(c) log(1 + exp(c)). In our experience, such transformation of
3

---

Published in Transactions on Machine Learning Research (otobbrr/2025)
normal random variable performs best with gradient-based optimization by providing enough flexibility in modeling distributions, where work such as Rodríguez & Dunson (2011) empirically demonstrates that a probit transformation of a random normal variable provides prior capable of generating a rich class of distributions. To ensure positivity the weights, the softplus function maps each value from the normal ristribution to positive real number. Other candidate distributions, such as the gammn and log-normal distributions, are more challenging implement because of the complexity of the likelihood the former and the heavy right-tailedness in the latter. Thus, with the coftplus-nomma conditional density placed on the weights, the term po(wle) in Equation 2 is equal to
2n (log(e--1) - 1))²
Po (wle) x
exp
(3)
20
up to a constant factor, where and o² are functions of neural network parameters 0.
3.2 Likelihood a Weighted Adjacency Matrix
There are two ways to parameterize the distribution pe () over weighted graphs: first, we may consider the probability over all entries of W in row-wise manner as
Po W)
po W (l(Wa))
(4)
where Wi is the (i,j)-th entry of W, Psy (0) is the estimated probability an edge existing between nodes o and By, Cig = when (v,,0) 12) E and otherwise 0, and Wa = W(u,, vy) is the weight of edge ey whenever (w, 2/) E. Note each entry Wi is conditioned on all prior entries, denoted as {Wa).
Next, similarly to how BiGG factors (A) in Equation
we factor the weighted edge set of W
Pe (W)
II po(exl wi)aek)) powwulen ((ei, wi)aeh)).
(5)
noting all edges up to and including es condition the generation of weight wk- We substitute Equation 3
into the terms pe po(ws (wayleiz) and po (wwleek, ((et, w)) of Equations and 5 respectively, and maximize the log-likelihood L(O; W) to train our models on weighted graphs. More details of the derivation of Equations and and the objective function are given in Appendix A.1
3.3 Models
Our main contributions use autoregressive models, which are well-suited for graph generation as they ex- plicitly capture dependencics among odges and, in our case, their weights. BiGG-E extends the original BiGG model by maintaining two states during generation: topological state inherited from BiGG and weight state that encodes all previously generated edge weights. By leveraging both states, BiGG-E jointly and autoregressively predicts the weighted edge set of W. We begin by reviewing the BiGG architecture before detailing our extensions in BiGG-E, Additional architectural details and an expanded BiGG review are provided in Appendices A.2 and A.2.1
3.3.1 Review of BiGG (Dai et al. 2020
BiGG generates an unweighted graph with an algorithm consisting two main components, both which train in Ollogn) n) time: (1) row generation, where BiGG generates each row of the lower half A using a binary decision tree; and (2) row conditioning, where BiGG deploys hierarchical data maintenance structure called Fenwick tree (Fenwick 1994h to condition the subsequent row generation all previous rows.
4

---

Published in Transactions on Machine Learning Research (October/ 2025)
[1, 28]
[vi, m4
top
[0r, u2]
[us, va]
fop
hot
Tree-LSTM Cell
Left Subtree Summary
01
14
Figure 1: Example of constructing To in the original BIGG model. The interval [e1 Ug] recursively partitioned via left-right decisions until reaching individual nodes (e-g., e1 and va). Dashed lines indicate edge. Purple arrows show the top-down context vector ht used for left-child edge predictions; orange arrows show the conditioned top-down context 6oOP used for right-child predictions. At node [u], TreeLSTM merges the left sub-tree summary (blue) with h to produce fite for left subtree conditioning.
Row Generation To sample edge connections for each node ua G, BiGG adapts a procedure from R- MAT (Chakabbarti et al., 2004) to construct binary decision tree Tu which identifies all edge connections with va by recursively partitioning the candidate edge interval [V1 V--1] into halves. Each node t E Tu corresponds to a subinterval [u;, vx] of length 4 = k - - which is split into left and right halves: Ich(t) [o,, 1:+14/21] and rch(t) [V++14/2]+1, vk]-
If an edge exists in Ich(t), the model recurses into that interval until reaching singleton interval [ey, uy]. which represents edge connection with vy- After completing the left subtree, the model recurses into rch(t), conditioned all edge connections if any formed in lch(t). BiGG conditions subsequent predictions all prior interval splits using two context vectors: (1) predictions for Ich(() use top-down hidden state (t), which sequentially encodes all left and right edge existence decisions made in To thus far; and (2) predictions for rch(() use conditioned top-down hidden state (L) computed by merging h(t with bottom-up summary state of the generated left subtree, h (Ich((). This merge is performed using a Tree-LSTM Cell Taai et al.) 2015), which encodes relevant information from the top-down and bottom-up hidden states: (ttp(t) = TreeCell, (h),r(t) hht (Ich(t)))
Hence, constructing Tu is fully autoregressive with probability
(Ta) II po po((ch())b)?P()) (oo(r(t))))) pr(rch(t)(::""()) SET.
Figure illustrates an example of constructing Tu and visualizes use of the top-down and bottom-up states in predicting Ich(t) and rch((). Finally, note that as hbbo(() is the bottom-up summary state summarizing the subtree rooted at node f, the bottom-up summary state at the root node to summarizes the entire tree T,,
Fenwick Tree To condition each decision tree Tu on all prior trees Ti to Tu-1, BiGG adopts the Fenwick tree [Fonwick] 1994] to efficiently summarize all previously generated rows A. The Fenwick tree at row u has [log(u 1)] + 1 levels, where the base level (leaves) of the tree are states hot (tg) summarizing the edge connections formed in each T,, j 1....,u Higher levels of the Fenwick tree merge these states
5

---

Published in Transactions on Machine Learning Research (october/202))
Algorithm BiGG-E Weight Sampling and Embedding
function embed weight(ws, hgg
w LSTMM(uu))
Add w to Fenwick weight tree and update tree using Equation
3: hnd TrreCell
where k & 2' = 2'
[
4: Return h end function
function sample_ (eight t, h (t), (t))
h (t) TreeCell (h (t). hg
6: Sct Mk+1 = ( (t)) and log o = foa (har (t))
7: Sample w from Section 3.1 using 1k+1, o+r
8: h = embed_ feabee__wighh((eee)
)
Return T, (edge index I represents), Wh+1, hwt
end function
to produce aggregated summaries across multiple rows. Letting g) denote the state at the j-th node the i-th level, each non-leaf node of the Fenwick tree merges its two children using Tree-LSTM cell as
g = TreeCelly rOw
(82)-1
(7)
where 1 < i [log(u + +, 1 and g/ is the bottom-up summary state of Ty. Finally, to summarize all rows 1 to u - 1, the model iteratively applies Trec-LSTM cell to produce row summary hidden state how:
TOW = TrleCell Bammmmmryy
((s where u & 2 = 2-
(8)
where & is the bit-level 'and' operator, each رiğن encodes summaries of different groups of rows of A, and how initializes (to) to condition construction of Tn so that (TT)) po (T Tu-1).
BiGG Training and Sampling Times The training procedure for BiGG consists of four steps, each running in O(log time by parallelizing computations across rows. First, since trees Tu are summarized independently, their root-level summaries are computed in parallel by traversing each tree level by level from the leaves the root. Second, the Fenwick tree is constructed from these root summaries in the same level-wise manner. Third, the model computes all row summaries heo using the Fenwick tree. Finally, for cach Tu, the model computes all left and right edge interval existence probabilitics lovel-by-level.
For graph generation, the Fenwick tree requires Onnlogn) time to construct, since updates now occur sequentially across row. Provided the graph is sparse, ie., m = O(n), the construction of all trees T, requires O(m log n) time. Thus, the total sampling time of sparse unweighted graph is O((n + m) log n).
3.4
BiGG-E
BiGG-E incorporates weight state used in tandem with the original topology state of the BiGG model to jointly predict weighted edges. We first describe the weight state, followed by the joint prediction framework.
3.4.1
Edge Weight Prediction
Constructing the Weight State To preserve BiGG's training and sampling speed-ups, BiGG-E intro- duces second Fenwick data structure referred to the Fenwick weight tree that summarizes edge

---

Published in Transactions on Machine Learning Research (October/202))
hg
Previously Sampled Weighta
Weight Embbeddinge
LSTM Oell
w
Tre-LSTM Cell
w2
Embeddings in Ia2
Compatation Path
w2
bg Computation Path
New Weight
w2
Prodiction Path
Sampled Weight
Newly Added
Weight Embbediing
w8
Figure 2: Illustration of Fenwick weight tree state construction. Sampled weights wy are passed through an LSTM obtain initial embeddings wf. which are recursively merged using Tree-LSTM cells (yellow nodes) to form higher-level summaries. To compute the current weight hidden state h summaries for wi 4y (wf) and Ws to Ws (w?) are merged. This state is used to prodict W7, which is added to the Fenwick weight tree and updated accordingly.
weights during generation. This new tree mirrors the structure of the original Fenwick topology tree used in BiGG, but is maintained separately to construct edge weight embeddings autoregressively. The Fenwick weight tree is similarly organized into [log(k - 1) + levels, where k is the current number of weights in the graph and the 0-th level corresponds initialized weight embeddings, computed using single forward pass of an LSTM: w LSTMe (wx). Higher-level embeddings w) in the Fenwick weight tree are computed using Equation 7 where w/ is now the initial embedding of the j-th weight in the graph.
To obtain summary state of all prior edge weights, use Equation g to compute the summary weight state h for weights to wk in Ollog k)) steps. C the edge weight embedding procedure in the Fenwick weight tree. Figure illustrates an example of the Fenwick weight tree embedding process, which updates the weight state recursively based on the weights generated so far.
2
Edge Weight Conditioning Because the summary weight state h encodes information about all pre- viously generated weights wi to Wk, using this state to predict the next edge weight wk+1 allows BiGG-E condition each new weight on the history of prior weights. As established in Section 3.1 each edge weight is sampled from softplus normal distribution with mean Ae and variance of parameterized by functions of 0. Computing these parameters from h in the sampling of the next weight Ws41 allows for conditioning pk+1 and of on all preceding weights:
#6+1 = (a
log o = (h"
(9)
where f and for are MLPs that output the estimated mean and log-scale variance, respectively. While this allows BiGG-E model dependencies among weights, a full generative model must also capture how edge structure and weights influence another task requiring both the topology and weight states.
7

---

Published in Transactions on Machine Learning Research (october/2055
(A) Graph Summary Initial States
(B) Construction Tip
Fenwick Trees
Jon md
Current Graph
Topology
[1rr stal
Jess mo
11's
Weight
hg"
Adding edge connections to
Updated Graph
Tos
[u m4]
305
LSTM
11/4
(er, Mt)
(1a, sta)
(Mta, m)))
Incoming
Incoming Weight State
Tre-LSTM
Merged
Weight
Topological State
Call
Prediction
Tree Update
Figure 3: Illustration of the autoregressive construction of Te, with weighted edges. Blue dashed arrows indicate the topological state; green dashed arrows indicate the weight state. These are merged with Tree- LSTM cells (yellow) output hidden states for predicting new weighted edges. New weights are embedded using an LSTM and then addod the Fenwick weight troc. Pancls (A-C) depict the process from graph summarization to final integration of Us into the graph.
3.4.2 Joint Modeling
Currently, the topology state is responsible for conditioning edge formation, while the weight state conditions edge weights. Used independently, each state informs only its respective component. However, by leveraging both states during prediction, BiGG-E models the joint interaction between topology and weights. Tet h (t) be the current top-down context at node E Tu and h be the current weight state of the most recent weight wx. BiGG-E computes the weighted graph summary state haum (1) using a Tree-LSTM cell:
h h (t) TreeCellmerg (h (h)oP(t), h.
(10)
First, when constructing Tu, BiGG-E merges h with the top-down context vectors h and fitor (t) before making predictions for Ich(l) and reh(l), respectively, using Equation TO This modifies Equation 1 to
Pe (T.).) = II (lch(t)) (t)) pe (rch(t) femm (t)),
TET.
which enables further conditioning the graph's topology the corresponding edge weights.
8

---

Published in Transactions on Machine Learning Research (October/2022
Next, when BiGG-E forms edge connection at singleton interval [.y. in Tu the model merges (() with hg using Equation 10 prior to outputting the mean and variance parameters p4-1 and o This modifies Equation to
Pk+1 ff (
log x for (hi,,) (!)
which conditions sampling edge weights on the topology of the graph, fully allowing BiGG-E to jo.jontly model weighted graphs. Algorithm [ outlines sampling a weight when an edge cxists, and Figure 3 visualizes the joint modeling weighted edges when constructing Tu.
3.4.3 BiGG-E Training and Sampling Time
The novel architectural design outlined in Section 3.4 allows BiGG-E to extend the efficient training and sampling observed from BiGG to sparse weighted graphs. Constructing the weight state with the Fenwick weight tree adds only O(log m) training time and Om loglogmm. sampling time, which preserves the overall asymptotic complexity of the model so long as m = (n). Furthermore, since BiGG-E constructs cach free Tu using BiGG's original procedure, training remains parallelizable across rows. Finally, the use of Tree-LSTM cells to merge topological and weight states does not disrupt this structure, allowing BiGG-E to maintain a training time of O(log n) and sampling time of O((n + m) log n) for sparse weighted graphs.
3.5 Comparison Models
Our code for BiGG-E and all comparison models is available at httpss//giiiabbbcccm/////lllm/ss
Adj-LSTM Adj-LSTM builds on the work of Li et al. (0188) by using an LSTM cell to parameterize the lower half of W in a row-wise fashion. To adapt to the grid-like structure W, Adj-LSTM maintains and updates row and column states autoregressively. When an edge exists between nodes v; and Uy a corre- sponding weight is sampled as described in Section 3.1 Adj-LSTM is fully expressive but slow: generating all of W requires O(n²) computations. Additional details are provided in Appendix A.3
BiGG-MLP BiGG-MLP is simple exlension of BiGG that replaces the topology leaf state (Algorithm line 9) that indicates edge existences in To with an MLP that encodes the newly sampled weight into a state embedding. The rost of the algorithm remains unchanged, maintaining a single state that summarizes topology and edge weights. However, using the same state to simultancously make left-right binary decisions and generate continuous weights severely limits BiGG-MT.P's capacity to learn each task. This comparison highlights the importance of maintaining separate topology and weight states, done in BiGG-E.
BIGG+GCN BIGG+GCN is two-stage model that decouples topology generation from edge weight sampling. First, the original BiGG model generates an unweighted graph. Then, a graph convolutional net- work (GCN) conditioned on the graph's 's topology populates each edge with edge weights. Thus, BiGG+GCN forgoes jointly modeling weighted edges and instead generates edges independently of weights. BiGG+GCN serves as a comparison for evaluating the benefits of BiGG-E's joint modeling approach.
Baseline An Erdös Rényi (ER) model independently samples edges with an estimated global edge exis- tence probability, Weights are sampled independently with replacement from the training set edge weights.
4 Experiment
We assess all models on the following: (1) do the models capture diverse distributions over weighted graphs; (2) does jointly modeling topology and edge weights improve performance, and (3) do the models scale well to large graphs? Following the evaluation protocol of Liao et al. 2019h, we compare an equal number of graphs generated by each model against a held-out test set.
To assess generative quality, we use metrics that evaluate the marginal distributions of graph topology and edge weights, and metrics that evaluate their joint distribution. For topology, we compute Maximum Mean
9

---

Published in Transactions on Machine Learning Research (October/2022
Discrepancy (MMD) Greeton et al. 2012) using test functions based on degree distributions, clustering coefficients distributions, and the spectrum of the normalized unweighted Laplacian, which are convent ional measures of topological performance used in Liao et al. (2019), Dai et al. (2020), and You et al. (2018). The lower the MMD metric, the higher in quality that graph set is relative to the test set. For all tree and lobster datasets, we also report the error rate as the percent of generated graphs that do not follow the correct structure. For edge weights, we summarize the marginal distribution using the pooled mean and standard deviation, denoted w and Sw. We additionally compute the MMD on the marginal weight distribution within each graph. To assess joint structure, we apply MMD with test functions based the weighted Laplacian spectrum and weighted degree distribution. Finally, we compute the average rank of each model within and across all datasets. Further details on the MMD test functions are provided in Appendix A.6
To evaluate scalability on larger graphs, we train on sets of 80 weighted HW-trees with sizes from {100, 200, 0.5K, 1K, 2K, 5K, 10K, 15K). Each model trained on a GV100 GPU with 3.2 GB of memory an single procision performance, and we report the MMD on the normalized Laplacian of the resulting weighted graphs against 20 test graphs. For each trained model, we record the time to sample one graph, the time to complete forward pass, backward pass, and optimizer step on one training graph, and the memory consumption used per graph during training. We also compare scalability with that of the diffusion model Sparse (Qin et al. 2024), hypothesizing that BiGG-E scales more efficiently. Finally, we expect the extended BiGG models to scale better than both Adj-LSTM and SparseDiff, while BiGG-E will retain superior generative quality on large graphs.
Data
We use the following datasets to evaluate the generative quality of our models.
Rédös- 100 graphs that represent a mull case to test whether the models capture the distri- bution of weighted graphs under Erdös Erdös-Rééní model (Erdös & Rényi 1959). We sample weights independently from the standard normal distribution and transform them with the softplus function. Hierarchical- Weight (HW-) Tree: 1,000 bifurcating trees with hierarchically sampled edge weights: for each tree T. sample pr ~ (7, 13) from the uniform distribution, then Wik ~ I[44 p4 from the gamma distribution. This yields a global weight distribution with mean 10 and standard deviation 2, and within-tree standard deviation of 1.
3D Point Cloud: 41 graphs of household objects (Neumann el al. 2013 Weights from the 3D Point Cloud graphs represent the Euclidean distance between the two nodes in each edge.
Lobster: 1,000 graphs that are path graphs with edges appended at most two edges away from the backbone. We sample weights independently from the Beta distribution as wy ~ BetaBBa,5555 15).
Phth-Threshold (PT-) Tree: 100 trees where weights and topology are coupled. We sample weights W'k ~ (10.,, independently. Starting at the root node, we add edges until the sum of outgoing edge weights exceods a threshold of For each new child, add edges recursively using the same rule: add children until the total weight of all new edges plus the path length from the root to the current node- exceeds 4. This process continues until all root-to-leaf path sums exceed 4. Yeast: 100 phylogenetic trees representing the evolutionary history of 154 Succharomyyes Cerevisiae strains inferred from DNA sequence alignments. Edge weights denote evolutionary time along each branch from ancestor to descendant (Hassler et al. 2022).
4.1 Results
Weighted Graph Distributions BiGG-E consistently outperforms competing models on topological metrics [. With the HW-tree and lobster graphs, it consistently achieves the best or most competitive MMDs. For the Erdös Erdös-Rééyi graphs, all BiGG extensions are competitive with the baseline, where the models successfully capture a known probability distribution. All models perform equally well, which expected given the graphs are fully independent. On the complex 3D point clouds, BIGG+GCN performs best on topology, with BiGG-E remaining competitive with respect. to the clustering (0.188 vs 0.179) and spectral (8.19 x 10 vs 7.33 x 10-3) MMDs. BIGG-E also achieves the lowest error rates for HW-tree and lobster graphs (2.5% and 0.5%, respectively). Finally, BiGG-MLP exhibits substantial degradation in topological quality across graph datasets, performing orders of maguilude worse on HW-tree and 3D point cloud graphs and showing moderate degradation on lobster graphs.
10

---

Published in Transactions on Machine Learning Research DOctober/2055
Table 1: Topological Accuracy Measures. The MMD metrics use the test functions from the set (Degree, Cluster, Orbit, Unweighted Laplacian (Spec)}. For the MMD metrics, smaller values are better. OOM indicates out of memory. Error is reported as the proportion of non-tree or -lobster graphs. Similar or better topological accuracy compared to the original BiGG (BiGG+GCN) shows that modeling of weights does not worsen BiGG-E's topological performance. Results are given Mean + SD over five runs. Boldfaced entries represent the best mean value. < 0.01 indicates near-zero values and statistical ties on given scale. Em-dash indicates no run was performed. Rank is best model compared with (Mean-SD, Mean, Mcan+SD)).
Methods
Datasets
BiGG-E
Adj-LSTM
BiGG-MLP
BiGG GCN
Erdös
Rényi
Deg.
(x10
2.52 0.90
30.3 = 8.6
9.56 + 2.06
4.76 1.38
2.96 0.66
Erdós-Rényi Rényi
Clus.
(x10"?)
1.68 = 1.02
3.64 + 1.18
1.66 0.94
1.58 #0.91
1.35 + 0.38
Ima 749 (499)
Orbit
(x107")
6.40 0.94
2.5
7.98 +: 0.98
8.55 2.54
6.73
0.39
mar 2846 (1349)
Spec.
(x10"")
2.21 0.05
24.4 5.9
7.38 4 1.98
3.15 0.39
2.75
0.5.1
Rank
1.67 1.15
5.00 0.00
+: 0.51
2.83 0.72
1.92 4: 0.90
Deg. (x10
0.02 0.01
14.1 3.7
2.88 + 0.38
0.08 0.00
2698. + 29.6
HW-Tree
Spec. (x10-1)
5.75 + 0.98
18.7 +
20.0 4.1
5.71 0.63
812.2 13.5
M Imar 199 (199)
Orbit (x10=*)
< 0.01
0.72 + 0.05
0.12 0.00
<
0.01
381.6 + 15.0
maa 198 (198)
Error
(%)
2.30 0.30
30.20 3.33
82.80 3.77
5.80 0.97
100.00 + 0.00
Rank
1.29 0.40
3.58 + 0.51
3.42 4: 0.51
1.71 0..40
5.00 + 0.00
Deg.
(x107")
1.50 + 1.25
OOM
26.1 0.1
0.11 0.09
534.2 2.8.1
3D Point Cloud
Clus. (x10-1)
1.88 0.16
OOM
5.77
1.74
11.5 0.04
V mar 5022 (1375)
Orbit
(x10-3)
1.75 = 1.31
OOM
17.9 5.0
0.51 0.37
102.6 1.53
E mar 10794 (3061)
Spec.
(x10->)
8.19 0.83
OOM
27.5 2.0
7.33 0:20
254.6 9.002
Rank
1.92 :: 0.29
5.00 0.00
3.00 0.00
1.08 0.29
4.00 0.000
Deg.
(x10->)
0.32 0.17
0.54 + 0.35
2.36 4: 0.45
1.17 0.70
249.1 0.7
Lobster
Clus. (x10
0.00 0.00
+ 0.15
0.00 0.00
0.00 = 0.00
85.8 :: 10.6
Mmeex 100 (55)
Spec.
(x10
2.80 0.24
3.09 0.47
4.19 + 0.60
3.27 0.44
202.1 3:312
[5 max = (51)
Orbit
(x100>)
3.33 0.57
3.75 + 0.85
29.8 3.1
12.33 4.36
156.2 2.18
Error
(%)
0.90 0.50
21.70 4.19
31.70 1.1.9
17.00 1.12
100.00 + 0.00
Rank
1.23 = 0.50
2.50 = 0.73
3.63 0.77
2.63 0.48
5.00 0.00
PT-Tree
Deg.
(x1071)
0.22
0.05
152.6 + 10.3
62.2 4: 15.0
4.05 2.80
602.8 4 48.3
Spee. (x107")
4.92
261.1
65.7
9.74 2.87
229.7 +:
V mar 452 (193)
Orbit (x10-1
0.36 0.13
349.6 + 18.1
44.7 6.0
4.64 2.000
102.2 2 + 15.0
E max 451 (192)
Error
(%)
0.00 0.00
100.00 0.000
0.00 0.000
0.00 0.00
100.00 +
Rank
1.25 0.45
4.38 + 0.43
2.75 0.45
2.00 0.00
4.64 +: 0.54
Deg.
(x10-1)
0.33 0.75
1165.1
+: 62.6
231.8 6.8
0.34 0.77
2712.4 38.4
Yeast
Spec. (x10
0.46
0.41
59.2 +
27.6 5.3
0.37 0.34
133. 3.0.8
V Imar 307 (307)
Orbit (x10"5)
0.24 0.54
743.6
210.0
219.8 + 96.6
0.47 + 1.06
1183.0
262.8
E max 306 (306)
Error
(%)
1.00 2.24
100.00 0.00
87.00 1: 4.44
1.00 2.24
100.00 + 0.00
Rank
1.38 0.38
4.13 + 0.23
3.00 +
1.63 0.38
4.88 0.23
Global Rank
1.45 0.63
4.03 + 1.00
3.25 0.58
2.01 0.7.4
4.27 +: 1.11
11

---

Published in Transactions on Machine Learning Research (October/2022
Table 2: weight Accuracy Measures. The MMD metrics use the test functions from the set {Weighted Laplacian (Spec) and Weights). For the MMD metrics, smaller values are better. OOM indicates out of memory. Marginal means and standard deviations of edge weights are given as pw and ow for underlying edge weight distributions, and to and 8w when computed from sampled graphs. For ER Graphs, edge- weights are on the underlying normal distribution scale. For HW-tree graphs, 8T represents the average standard deviation of edge weights sampled per HW-tree. Results are given as Mean + SD over five runs. Boldfaced entries represent the best mean value. Em-dash indicates no run was performed. Rank is best model compared with (Mean-SD, Mcan, SCD
Methods
Datasets
BiGG-E
Adj-LSTM
BiGG-MLP
BIGG+GCN
Erdös Rényi
(x10 $)
5.12 3313
19.4
3.31 4.12
-3.84 = 7.07
2.96 + 0.63
Erdös Brdis-Rénni
1,01 0.01
0.98 0.00
1.01 0.01
1.00 +.000
1.00
+ 0.00
Per 0.0 Tw = 1.0
Spec. MMDWT
(x10
3.79 0.43
27.1 7.3
7.38 + 1.98
4.12 0.70
2.80
0.38
(x10-5)
1.27 0.66
38.6 12.2
1.97 1.18
1,85 0.51
1.76
+ 1.12
Rank
2.42 1.18
4.92 0:29
3.25 = 0.99
2.63 0.96
1.79 0.77
HW-Tree
w
10.13 0.122
9.97
4: 0.07
10.13 1 0.14
10.03 0.10
10.04 + 0.01
S
1.86 + 0.02
1.98 + 0.04
1.93 0.02
1.96
1.96 =
Pio = 10, =
87
1.01 = 0.01
1.32 0.04
0.98 0.00
1.96 0.03
1.96 = 0.00
OT =1
Spec.
(x10-))
0.07
2.83 = 0.54
1.33 = 0.14
2.09 #012
109.3 + 1.5
MMDWT
(x10-2)
0.85 + 0.33
0.33 0.09
0.71 0.50
21.6 0.1
21.5 1.1.
Rank
2.67 + 1.49
2.50 + 1.32
2.67 = 1.30
3.50 + 1.28
3.67 # 1.22
1
(x10-l)
4.18 = 0.06
OOM
4.28 = 0.02
4.56 0.00
4.20 = 0.01
Point Cloud
(x1071)
0.96
OOM
1.04
7.37
0.98
Re 0.411
Spec.
(x10=3)
7.77
0.90
OOM
23.1 #0.6
8.52 0.92
287.6 5.4
Ow 0.096
MMDWT
(x107")
0.27
A 0.19
OOM
0.771
18.3 4.2
2.00 4: 0.78
Wtd. Deg,
(x10-5)
7.31
5.83
OOM
87.6 2.14
9.67 1:29
455.8 a 2.4
Rank
1.13
= 0.35
5.00 0.00
3.00 = 0.00
3.13 1.12
2.73 1.10
Lobster
1
(x10-1)
2.49
+: 0.01
2.50 = 0.00
2.49
= 0.01
2.50 4:0.0
2.49 =: 0.00
8up
(x10-1)
0.94
1.03 0.00
0.94
0.94 0.00
0.94 0.01
= 0.25
Spec.
(x10-3)
2.44
+ 0.16
3.09 0.47
1.19
= 0.30
3.27 1 0.48
271.7 2.4
Tw 0.095
MMDWT
(x10=")
1.33 0.45
6.36 1.34
1.21 0.36
1.60 0.30
9.15 1.71
Rank
1.92 0.67
3.79 1.23
2.42 1.16
3.21 0.78
3.67 + 1.50
PT-Trre
w
1.00 0.00
1.03 0.01
0.99
0.01
1.00 4.0.0
1,00 4: 0.00
0.29 = 0.00
0.30 = 0.00
0.28 = 0.00
0.29 0.000
0.29 0.00
Aw 1.00
Spec.
(x10-2)
1.35
18.3 0.5
2.76
1.94
21.2 0.0.
Tge Rs 0.29
MMDWT
(x10=*)
4.03 + 0.20
18.9 2.2
7.57 = 1.62
22.6 2.8
0.54 0.38
Wtd Deg.
(x10=2)
0.38 0.08
8.92 = 0.78
= 0.36
4.12 #0.11
74.0 8
Rank
1.63 0.35
4.37 0.48
3.13 0.81
2.83 1.19
3.03 # 1.72
Yeast
w
(x107f)
3.65
0.01
6.22 0.08
3.65 0.02
3.47 0.02
3.66 0.05
Sur
(x10=*)
3.71
+ 0.033
9.50 = 0.26
3.87 = 0.22
3.67 4.006
3.79 1 0.06
Mm Rz 3.63 10
Spec.
(x10-9)
3.28
0.85
98.6 4.2
18.6 2.2.
23.7 116
133.4 3.1
Ow Rs 3.68 x 10-1
MMDWT
(x10=3)
0.56
+ 0.10
31.8 9.9.
1.36 =: 0.63
34.6 43.7
5.59 à: 1.93
Wtd Deg.
(x10-4)
0.22
358.0 19.1
14.4
15.3 11.8
211.6 14.3
Rank
1.23
0.42
4.67 0.49
2.23 0.82
3.27 # 1:22
3.60 0.83
Global Rank
1.81 + 1.07
4.20 :: 1.17
2.78 :: 0.98
3.11 1.12
3.11 + 1.36
12

---

Published in Transactions on Machine Learning Research (october/2025)
Densily of All Weights Compared with Ground Truth
Densitty of Tree Standard Deviations Compared with Baseline
BGGG
4.2
BIGGE
RGGG-LFF
TNGG-MLP
TaGG-GEN
AQJUSTM
AXH-55TM
0.150
ER
GT
0.125
2.0
1.5
0.050
1.2
0.025
0.-
2.5
5.0
1.5
10.0
12.5
15.0
37.5
Density Weights Across All Thess
Standard Deviation Weights per Tee
Figure 4: Distribution of weights globally (left) and of standard deviations per HW-tree (right).
Joint Modeling BiGG-E outperforms all comparisons in jointly modeling weighted graphs, particularly on the 3D point cloud, PT-tree, and yeast graphs (Table Although BiGG+GCN achieves a lower unweighted degree distribution MMD for 3D point clouds, BiGG-E attains a lower weighted degree distribution MMD (7.31 10-3 vs 9.67 10-3). It also matches with BiGG+GCN on the weighted Laplacian MMD (2.44 10-3 vs 3.27 x 1)- where BiGG-E's more realistic edge weights improve joint modeling.
In the PT-tree dataset, where topology and edge weights are sampled jointly, BiGG-E achieves the best performance across all metries by significant margins. Although the Erdös Rényi baseline performs well on the marginal distribution of weights, which are independently and uniformly distributed, BiGG-E still distribution, while also capturing the
closely matches this distribution despite using a cottplus-paammeteriie structural dependencies exhibited in the PT-trees that the baseline cannot model. On yeast graphs, BiGG-E is comparable to BiGG+GCN on topology-only metrics but consistently leads once edge weights are included. More broadly, BiGG+GCN leverages its BiGG component on unweighted topologies that depend little on the edge weights, while BiGG-E outperforms when topology is edge weight-dependent, suggesting its joint modeling captures weighted graph structures more effectively.
In contrast to BiGG-E's stable edge weight learning, the two-stage BiGG+GCN pipeline is highly sensitive to errors in the generated topology of the graph, highlighted by the heavily inflated variance of edge weights produced in the 3D point clouds. Uncertainty in the graph topology propagates to the GCN, leading to instability in the sampled set of edge weights. BiGG-E's joint modeling scheme leads to more stable and realistic weighted graph generation by allowing uncertainty flow in both directions: uncertainty in topology of the underlying graphs propagates to uncertainty in the edge weight distribution, and vice versa.
Scalability Table shows that all BiGG extensions scale well to larger graphs, with BiGG-E performing best. Adj-LSTM's performance deteriorates rapidly even on the moderately sized Erdös-Rénys graphs and becomes computationally infeasible for the 3D point clouds, shows Adj-LSTM fails in scaling to graphs beyond even 500 nodes, where runtime becomes prohibitively slow. On the other hand, all BiGG extensions scale to graphs with thousands of nodes. In Figure 3 we empirically demonstrate that all BiGG extensions remain efficient for large graph generation, with training time scaling as Oloog n) and sampling time as O(n + m) logn), while the training times for Adj-L.STM and SparscDiff increase rapidly with respoct to graph size and quickly become impractical. Although BiGG- E's incorporation of a separate weight state slightly increases training and sampling time, the overhead is minimal and justifiable with the superior generative quality.
observed in Table [ Furthermore, Table 3
Notably, scparating the topology and weight states allows BIGG-E to improve memory efficiency. The original BiGG model applies bits compression to summarize the node intervals in Tu with binary vectors, significantly reducing neural network computation and memory usage (Dai et al. 2020). While this is not feasible in BiGG-MI.P from entangling odge weights with the topology state, incorporating bits compression into BiGG-E's topology state is trivial. Moreover, BiGG-E offers flexibility in the dimensionality of each state: we use embedding dimensions of 256 and 32 for the topology and weight states, respectively. This re-
13

---

Published in Transactions on Machine Learning Research (tttobrr/2025)
Weighted Laplacian MMD is reported. Graphs are weighted HW-trees of increasing size. Lower better. OOM indicates Out of Memory.
Table 3: Model Scaling on HW-Trees of Varying Size.
Model
100
0.5K
2K
5K
10K
15K
Erdös-Rod Rényi
0.073
0.103
0.114
0.122
0,128
0.131
0,134
BiGG-E
2.77x10->
2.65x10-*
1.31x10-*
5.60x10-4
3.13x10
6,00x10-*
5.12x10
BiGG-MLP
1.36x10-a
4.82x10-a
3.18x10-3
2.04x10-3
1.44x10-a
6.32x10-4
5.47x10-4
Adj-LSTM 6.11x10-3
9.27x10-3
OOM
OOM
OOM
0OM
OOM
BIGG+GCN
3.67x10
x00
2.78x10
x0
2.96x
4.31
1.74x10
Generation Time per Graph
Training Update Time per Graph
Memory Consumption per Graph
Generation (min)
10'
30000
10a
Trainingg (sec)
25000
Memoory (MBB
10a
10a
15000
-0-
10000
10-1
5000
20-2
10a
10
101
2500
5000 7500 10000 12500 15000 Number Nodes (n)
Number (n)
Nodes (n)
GCN
AdiL
SparseDif!
cytn + m
cylo millgn
cylog
cylogn
Figure 5: Model Scalability. Sampling time per weighted graph (left); training time per weighted graph (middle); and memory consumption per graph during training (right).
duces computational overhead and helps prevent overfitting on weights, where we empirically observe 20% reduction in BiGG-E's memory consumption. BiGG-MLP, however, uses dense MLPs to output edge embed- dings that must match the topology state's embedding dimension of 256, contributing to unstable training and increased memory use. As a result, BiGG-E matches BiGG-MLP's training time while consuming less memory and producing tigher-quality weighted graphs.
5 Conclusion and Future Work
We introduce an autoregressive model that learns complex joint distributions over graphs with edge weights. While Adj-LSTM and both BiGG extensions learn from distributions over smaller graphs, BiGG-E scales best to graphs with thousands of nodes while maintaining strong performance learning joint distributions graph topologies and edge weights. Future work consists of further improving BiGG-E, especially with respect to memory consumption. In addition, we can further explore the benefits of joint modeling edge weights and topologies by learning joint distributions over topologies and vectors of edge and node altributes, learning conditional distributions over these given node- or edge- related data. Finally and thanks to its scalability, BiGG-E may also be useful within larger regression models featuring network outcomes.
6 Acknowledgments
We would like to extend our thanks to Dr. Hanjun Dai for his help in extending the code base BiGG to use BiGG-MLP.
Richard Williams is supported by NSF grant DMS 2236854. Andrew Holbrook is supported by the NSF (DMS 2236854, DMS 2152774) and the NIH (K25 AI153816). This work was made possible by the support of the Cure Alhhiner's Fund and the Kayli Foundation.
14

---

Published in Transactions on Machine Learning Research (october/222)
References
Reka. Albert and Albert-Laszlo Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47, 2002. URL http://link. aps http///tttrct////////////
Guy Baele, Xiang Ji, Gabriel W. Hassler, John T. McCrone, Yucai Shao, Zhenyu Zhang, Andrew Holbrook, Philippe Lemey, Alexci J. Drummond, Andrew Rambaut, and Marc A. Suchard. Beast x for bayesian phylogenetie, phylogeographie and phylodynamic inference. Nature Methods, 2025. doi: 10. 10.1038/s41592 00002-0025-222 02751x2 URL https://doi. http://...0rr/111.00002221222222
Laia Barjuan, Muhua Zheng, and M Ángeles Serrano. The multiscale sclf-similarity of the weighted human brain connectome. PLOS Compulational Biology, 21(4): 20, 04 2025. doi: po. 1012888 URL https://doi.org: 1ttp://o0.111///uuraaaaaa pcbi 1012848 1012.1
M. Bellingeri, D. Bevacqua, F. Sartori, M. Turchetto, F. Scotognella, R. Alfieri, N. K. K. Nguyen, T. T. Le, Q. Nguyen, and D. Cassi. Considering weights in real social networks: A review. Frontiers in Physics, Volume 11 2023, 2023. ISSN 2296-424X. doi: 10.33899/fbhy frontiersin
URL httpss/p:://wx
Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-MAT: A Recursive Model for Graph Mining. pp. 4224446. STAM International Conference Data Mining, 2004. doi:
URL https://epubs. siam. org//o//abs//1..ooooooo 111.://11111111.99771111117777
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. Proceedings of the 37th International Conference on Machine Learning (ICML),
volume 119 of Proceedings of Machine Learning Research, pp. 2302-2312 PMLR, 2020. URL http:
/ html
//proceedings.u mlr. pttpss//11///aa2000000001011
Paul Erdös and A. Rényi. On random graphs. Publicationes Mathematicae (Debrecen), 6:290, 1959. URL
/brokenur1#snap wtw.s/aaar..ee.eeaaasae////////e htt.://ww.........a../////aaaaaa
Giorgio Fagiolo, Javier Reyes, and Stefano Schiavo. The evolution of the world trade web: a weightedd-network analysis. Journal of Evolutionary Economies, 20(4):479-5k) 2010. doi: 111007/000191-009-0116/00 URL
attps://doi.orge htt.:///.......0///00000-0000000
Peler M. Fenwick. A new data structure for cunulative frequency tables. Softw. Pract. Exper., 24(3):
327 336, March 1994. ISSN 0038-0644. doi: 00.1022//pe.43800400000 URL lhttps://oo:: http:////oo.rr/...//// 1002/ spe. spe.43888 4380240306
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A
kernel two-sample test. J. Mach. Learn. Res., 13(1):723-77 773, March 2012. ISSN 1532-4435. URL http:
//dl. acm. www.acc..ooog www./iitaiiiiin..o////o cfm?id=2503308, 2188410
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 2434-2444. PMLR, 09 15 Jun 2019. URL htttp::/procceddnggg httppp//ppreeddnggg.......e../ wtt.::/www..p......mmm http//////g/oereeee/e www.ggroveeraa.. html
Gabriel W. Hassler, Brigida Gallone, Leandro Aristide, William L. Allen, Max R. Tolkoff, Andrew Holbrook, Guy Bacle, Philippe Lemey, and Marc A. Suchard. Principled, practical, flexible, fast: A new approach to phylogenetic factor analysis. Methods in Ecology and Evolution, 13(10):2181 2197, 2022. doi:
URL https://bessjuuraall. aateessooouaassss..melllleee inlinelibrary
wiley.com http://///ooo//a///..1111//4442/
13920
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8) 1997. doi: 2..1162/nec.11997.00
15

---

Published in Transactions on Machine Learning Research (October/2025
John Ingraham, Vikas Garg, Regina Barzilay, and Tommi Jaakkola. Generative models for graph- based protein design. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: / /ttp://d//ooccnnsss.. neurips wwt..ps.cccppppprrrrrrrr...... http:/pppr.fleeeppprrre///// files//apprr2219//11e Salff433066644440000636666260003
Jachyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations, 2022. URL htttp:://aaxxxx.orraabbb//// 02514
Wataru Kawai, Yusuke Mukuta, and Tatsuya Harada. GRAM: scalable generative models for graphs with graph attention mechanism. CoRR, abs/ (bs/1906.01861, 2019. URL http:://arxxvvvorggab///// 01861
Scketoulie Keretsu and Rosy Sarmah. Weighted edge based clustering to identify protein complexes in mootein-proteds interaction networks incorporating gene expression profile. Compulational Biology and
Chemistry, 65:69-79, 2016. ISSN 1476-9271. doi: http://////ooorrr/////////////op
sci wcw.eeedireet..com/ceiiiiiieeeee wct.ccchhh....ooc/caaaaaaaaaaaaa 00tp 2016.10.000.....0
URL /
Thomas N. Kipf and Max Welling. Variational Graph Auto-Encoders.. In NIPS Workshop on Bayesian Deep Learning, BDL 2016, 2016. URL
http://grrrrre//eepppperrr/e///e 16. pdf
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter W. Battaglia. Learning deep generative models of graphs. CoRR, abs 0b031400.333,4 2018. URL. http:: org/ abs//a/3....///////// 03324
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché Buc, Emily B. Fox, and Roman Gar- nett (eds.), NeurIPS, pp. 4257-4267, 2019. URL. http:://blpp.... uni uni-trier wet.-ttrer.ddd///ooff.o.ooo dtt/a//cooo///tps//////000000 htm]#LiaoLSWHDUZZZ
M. Neumann, P. Moreno, L. Antanas, R. Garnett, and K. Kersting, Graph Kernels for Object Category Prediction in Task- Dask-Dependent Robot Grasping. In Proceedings of the Eleventh Workshop on Mining and Learning with Graphs (MLG-2013), Chicago, US, 2013.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via scoro-based generative modcling, 2020. URL lntpss///arxi www.aarwvvo.oooaaaae org/obrg 7003.00638.
Yiming Qin, Clement Vignac, and Pascal Frossard. Sparse training of discrete diffusion models for graph generation, 2024. URL sttpp://aaxiiv.or//aaaaa
A. Rodríguez and DB. Dunson. Nonparametric bayesian models through probit stick-breakinn processes. Bayesian Anal, 2011. [Accessod 11-09-2024).
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning reprosentations by back- propagating errors. Nalure, 323(688)):533 536, 1986. doi: 10.1038/323533a0.
Haşim Sak, Andrew Senior, and Françoise Beaufays. Long short-term memory based recurrent neural network architectures for large vocabulary speech recognition, 2014. URL
1128
C. Semple, M. Steel, and B.D.M.S.M. Steel. Phylogenetics. Oxford lecture series in mathematics and its applications. Oxford University Press, 2003. ISBN 9780198509424. URL htttps://bookss.oogg.. gowgle. com/ books?id==u8814ett35.
Rade Stanojevic, Sofiane Abbar, and Mohamed Mokbel. W-edge: weighing the edges of the road net-
work. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Ge- ographic Information Systems, SIGSPATIAL, '18, pp. 424-427, New York, NY, USA, 2018. Associa-
tion for Computing Machinery. ISBN 9781450358897. doi: 10.1155/977499532744966 URL https:
//ddii.org/0..144///277444//6/ 3274411
16

---

Published in Transactions on Machine Learning Research 2october/225)
Kai Sheng Tai, Richard Socher, and Christopher D. Manning. Improved semantic representations from tree- structured long short-term memory networks. CoRR, abs/1503.00075, 2015. URL http://arxiv.org:
abs/1503.00075
Clement Vignac, Igor Krawczuk, Antoine Sirandin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation, 2023. URL https://arxlv.org// wwtp:/orgga/aa////eeee 14734
Jiaxuan You, Rex Ying. Xiang Ren, William Hamilton, and Jure Leskovoe. Graphrnn: A doep generative model for graphs. CoRR, 11000088777777 2018. URL http::/dblpp.. wni-trier wttp:mmteeeeeeeddd/eerrrr.e..aee /aaiier/de//b//ooraaaa/cc/oo//// corr1802. haw.baas-ttmaaaaa---....ooaaaaea 1802-08773
17

---

Published in Transactions on Machine Learning Research (October/200) 2025)
A Appendix
A.1 Probability Calculation of Weighted Adjacency Matrix
Here, derive the probability of observing W through (1) all entries in a row-wise manner and (2) its weighted edge set. First, we define Pe(A) over unweighted graphs and then extend these probabilities to probabilities po (W) over weighted graphs. One method in estimating (A) is to directly generate all of the lower half of a row-wise fashion. Letting Ai represent the (i. (ith) element A, we have that
[-1 pa (Ay)))))))
(A
(11)
where {Agt is the set of all entries of A that come before Ay in the generation process.
Models such as Li et al. 2018) and You et al. 2018 use this direct factorization of the probability of all entries of A, leading to the computational bottleneck of O(n²) for a graph with n nodes. BiGG (Dai et al, 2020), on the other hand, leverages the sparsity many real-world graphs and directly generates the edge-set of A, leading to the probability
(o(A) (A) II (ewekk)))
(12)
where e the 1th ordered edge in G.
Given the choice of parameterization outlined in Section 3.1 follows: given edge exists between nodes and By, sample corresponding weight w from conditional distribution parameterized by (oww))).
modify equation 11 and equation 12
For readability, assume entries Wij are conditioned on all prior entries; that is, (W,;)) = po (Wa (Wa))) where {Ww} is the set of entries of W that come prior to entry Wi when traversing the lower half of A in row-by-row manner.
For each entry Wij, we must decide if an edge connects nodes o and by by sampling ei Bernoull((psj): where Pij is function of 0, and if so, sample non-negative weight wyj with probability po(wiy = 1). Thus, we note that the probabilities of particular entry Wi₁ being 0 weight waj are given by
po (W = 0) pa(eij = 0) = 1- Pij
and
pe (Wi = wij) = (ei = () = 1) = Psspoluijless = 1). We may succinctly represent the probability of Way as
( = wiy) = (1 - pty)=-eu -e (poso((wsyless))
Finally, we define the probability of W as
Pe W
2-s))-es
Next, modify equation 11 to obtain the probability of observing W over all entries
pe ()
po (v,, ()), m)))
18

---

Published in Transactions on Machine Learning Research (October/2022
On the other hand, because weight is sampled for non-edge connections, the probability of observing the edge set of W becomes
pe () = II (e wx (())))
where we factorize po(ek; wxl+) = po (exl-))oo(() (wo using equation 2
Finally, compute our likelihood objective functions. First, compute L(0; W) from equation 4 which is used to train Adj-LSTM. The training objective is the log-likelihood over all entries W, summed over the terms
(O; (eig. wij)) = (1 - eij)
-4j) log(1 - Piş) + eij log + Eig log pa (way)s
where eij log (wsyless) ley) 0 if eij = 0, and substitute Equation into the expression po po(wy lei)) when Ctj = 1. This yields the training objective for Adj-LSTM as
72
C(O; W) log
po
(W
ΣΣ
(5 (eij, wi))).
(13)
Last, from Equation 5 the objective function for all BiGG extensions is the log likelihood over the weighted edge set,
m
C(;; W)
Σ
log (o (er + logpo(wn las Mon:(ee {le,, wr)aek))
(14)
where we substitute Equation
into the expression po ((e,, wr)seh))
A.2 Model Architecture
Autoregressive models are popular sequential models designed to capture dependencies with prior obser- vations. A classical example in statistics is the AR(p) model, where each observation X, is expressed lincar combination of the previous p values in the series: X; PiX-= ς.. Deep autoregrossive models exlend this idea by introducing nonlinear function approximators, such as neural networks, to better model dependencies in sequential data. In this section, we describe in detail the primary neural network architectures used building cach autoregressive model.
LSTM Architecture The neural network architecture across all models utilizes LSTM cells, which are recurrent neural networks well-suited for modeling nonlinearities in sequential data in an autoregressive manner (Hochreter Schmidhuber 1997). An LSTM maintains state, represented as a tuple (h,, c;). where h C2 E Rd are the hidden and cell states, respectively, every time step Here, h, captures the recent memory of the sequence, while c encodes longer-term memory. Given an input x, at time step and the previous state (h--1,0,1),, the LSTM updates the state by computing (h,, c.) follows (ak el. al. 2014h:
1, (W())
X; W(O
h + b(o) w h 1 + b(s)
f, o oW!!
tanh W X ( h h + b(s))
O, (W X, Wl
hh- b(o))
C; f, 0 +i g
h, o tanh(c;)
19

---

Published in Transactions on Machine Learning Research (October/2022 2025)
where is the sigmoid function, O is the Hadamard product, and all weight matrices and bias terms are trainable parameters. i,, fú, gt, and o represent the input, forget, cell, and output gates, respectively. We will also use the notation (he+1, C2+1) = (x,,(Xx, (he, Cr)) to represent these computations. For ease of readability, we suppress subscript t moving forward.
In the graph generative modeling context, an LSTM cell serves to maintain history of the graph generated by the model at each time step. At each time step, the model must make prediction-eiie either regarding topology (i.e., the probability of whether an edge exists) or regarding edge weight parameters (o.g., producing the mcan and variance a predictions, the hidden state h is passed through an MLP. An MLP a feedforward neural network composed of an input layer, one or more hidden layers, and an output layer, where it captures nonlinear patterns in the data through activation functions applied between layers (Rumelhart al. 1986). In our architecture, use the exponential linear unit (ELU) as the activation function:
MLP
normal distribution). To compute these
frx x = aa(e- -1 <<0 0
=
ELU(x) =
where a is a tuned parameter. In our case, the imputs consist of the LSTM hidden state of the model, and the outputs are probabilities of edge connections, as well as the mean and variance components μt and of introduced in equation 3 For notational simplicity, let hg denote the current hidden state h summarizing the graph generated thus far. To compute edge existence probabilities, we set p o (fp())) where fp is the MLP that outputs scalar that is mapped to probability by the sigmoid function Similarly, the softplus-transformen normal parameters μa and of are parameterized with MLPs fp and foe, respectively: (abb)) and of = exp(f<<(hc)).
Trec-LSTM Cells Finally, note that BiGG offers a scalable approach to the typically slow process of training on graph data by leveraging an algorithm with Ologgn) runtime. This efficiency is achieved with the usage of a Tree-LSTM cell Tai et al. 2015), a variant of the standard LSTM cell that is designed for troo-structured inputs. Specifically, BiGG and its extensions employ a binary Tree-LSTM coll, where cach internal node has exactly two children. Throughout this work, we refer to these simply as Tree-LSTM cells, with the understanding that they are all binary in structure.
Each node in the tree is associated with hidden state (hj,,;), where denotes the index of the corresponding node. Leaf nodes consist of states computed directly from the model, of which no computations are made within the Tree-ISTM cell. For internal nodes, which have two children designated as the left child (I.) and right child (Jt), the summary state at node j is computed using the states of its children, jL and jR, as follows Tai et al. 2015):
i, (W hig + w
b(o) fz (w(lL)) hig + w
R
(IL)
H R + b(l)
R
fn (W
(f
L hyg w
h5n+ b(n)
gj tanh(W (9)
L h + w Whhh h b(())
0 = oW! h,2 + w
R h b(())
Cj = i, @ g; + f. Cjz faa cyn
h, o, @ tan)i(c,)
A few key differences worth noting. Unlike the standard sequential LSTM, each node in the tree maintains its own hidden state but does not receive input vector Additionally, the Tree-LSTM cell computes distinct forget gates for the left and right children - denoted fçz and f,n, respectively - which allows the model to allend to different information from each child node (Tai et al.) 2015). We use the notation h = TreeLSTM(byL, hyR) to represent the computation at internal node j based on its two children, where the use of the corresponding cell states is implied. In this way, the Treo-LSTM cell represents a mechanism for merging two input states into a single summary state that captures pertinent information from both children.
20

---

Published in Transactions on Machine Learning Research (October/2022
Finally, we note that all LSTM cells, MLPs, and Tree-LSTM cells are parameterized by neural network parameters 0, which are optimized using the objective functions given in equation 13 (Adj-ISTMM) and equation 14 (BiGG models) via gradient descent when training each model on collection of training graphs
A.2.1 Further Details BiGG (Dai et al., 2020
BiGG generates an unweighted graph with an algorithm decomposed into two main components, both of which train in (log n) time: (1) row generation, where BiGG generates each row of the lower half of using a binary decision tree; and (2) row conditioning, where BiGG deploys a hierarchical data maintenance structure called Fenwick Tree generate each row conditioned on all prior rows.
A.2.2 Row Generation
For each node ru G, BiGG constructs a binary decision tree Tu, adapted from R-MAT Chakrabarti al. 2004), to determine v,'s edge connections with the previously sequenced nodes Vi...., 1u-1- Rather than evaluating each potential connection sequentially, which incurs a cost of (n)) per row of A, BiGG first checks whether any edge exists within the interval wu-]- If so, it applies the R-MAT procedure to recursively divide this interval in half and identify the specific nodes connected to un- By partitioning the interval in halves rather than scanning all possible connections, BiGG reduces the row generation time to Ollogn). n))
Let E To correspond to the node interval [n,, ty] of length right-half of this interval as lch(t) [ug, 13+10/2]] and rch(t) = |1-- 11/22+1, Ux], respectively. To recursively generate Tu, BiGG uses the following procedure for each E T.. If is leaf in the tree - that is, corresponds to a trivial interval of a single node vy an edge forms between U/ and ev. Otherwise, BiGG considers whether an edge exists in Ich(t). so, the model recurses into Ich(t) until reaching a leaf. After constructing the entire left subtree, the model considers whether an edge exists in rch(t), conditioned on this left subtree. Tf so, the model recurses into rch(t) until reaching a leaf. All leaves the fully constructed tree thus represent nodes which connect with v. in the graph.
k - - + 1, and denote the left-half and
Each decision about the presence of an edge in the interval corresponding to node t is modeled Bernoulli random variable with probability as a function of O. To make these predictions autoregressive, BiGG maintains two context vectors. The top-down context htpP(t) encodes the history of all previous left-right decisions along the path from the root to the node t and is used to estimate the probability of an edge in the left child, Ich(t). The bottom-up up context Abot(() captures information from the already generated left subtree rooted at node i, and is used to condition the probability of an edge in the right child, rch(t), basod on the structure of lch(t). Since rch(t) is constructed only after Ich(t) and its dependencies, BiGG employs Tree-LSTM cell (Tai et all 2015) at node t to merge the top-down context with the bottom-up summary of the left subtree prior to generating rch(t). Hence, the probability of constructing each tree Tu is
(T) II po(lch(t) (()))) (t) (o( SET.
(15)
where (ttr()) TheeCello(h)?P( (t), hhoh (lch(t))), and conditioning lch(t) and rch(t) on the top-down and bottom-up context vectors allows BiGG to generate all of Tu autoregressively. Equation [5 also implies that the probabilities of edges po(e)) in Equation are modeled a sequence of left-right edge existence Bernoulli decisions, which are then included in the objective function for all BiGG models. Figure provides an example of constructing Tu and visualizes the top-down and bottom-up states used to predict left and right edge existence decisions.
prooides
A.2.3 Fenwick Tree
The construction of Tu Section A.2.2 enables modeling the dependencies among edge connections within a single row of A. To make BiGG fully autorogressive, however, must also capture dependencies between rows. For this purpose, BiGG incorporates the Fenwick tree (Fenwick [994]. a data structure designed to efficiently maintain prefix sums by performing sum operations over an array of length in Olog n) time.
21

---

Published in Transactions on Machine Learning Research (October/2022 2025)
To maintain history of all previously generated rows in the graph, BiGG modifies the Fenwick tree to store summary representations of each row generated so far. This structure enables BiGG to compute summary state of the first rows in (log u) time.
The Fenwick topology tree is structured into [log(u-1)] levels. At the base- 0-the leaves the tree represent independent row embeddings for each TT. These embeddings are constructed using a bottom-up traversal: information starting from the leaf nodes of Tu propagates upward through the tree, culminating in root-level summary that captures the overall structure of Tu and therefore summarizes all node connections with Uu. Entries along higher levels of the Fenwick topology tree represent merged state summaries each combining information from multiple lower-level embeddings to produce collective summary state across several rows.
Let g) = (h,c) c) denote the hidden and cell states represented by j-th node on the i-th level g) of the Fenwick topology tree. Any given non-leaf node 8) consists of merging two children nodes one level below as
g TreeCelly (g (g2
(16)
Here, 0 S < [log(u - 1)] + 1 and 1 S 2F where gy denotes the bottom-up summary state of Tj. To compute a representation of all previously generated rows at each iteration, the model iteratively applies another Tree-LSTM cell over the relevant summaries to produce the row-level summary state h..
tow TreeCellaummag
( where 2 2 2
2 =
(17)
where & is the bit-level 'and' operator. Thus, the Fenwick topology tree enables BIGG to generate rows in an autoregressive manner: the hidden state h defined in equation equation 17 contains history of all rows generated in A so far and is used as the initial state for constructing the next decision tree, Tu+1- Similarly, during training, the binary structure the Fenwick row tree allows the initialization of row states for each row of A to computed in (log n) time.
A.2.4 BiGG Training Procedure
BiGG divides the training procedure into four main components, which all run on O(log n) lime:
First, because all decision trees Tu are known a priori during training, bottom-up summaries are computed from the leaves to the root of each tree. Importantly, the summary state for each row is independent of those for other rows, allowing these computations to be performed in parallel.
2. Next, using the root-level summaries from each Tw, the model computes internal nodes g) of the Fenwick topology tree in a level-wise manner using equation 16
Once the Fenwick topology tree is constructed, BiGG concurrently computes the row summary states h in parallel using equation
4. Finally, given each row-level summary h,ow, the model computes all left and right edge existence probabilitics in parallel, traversing from the root to the leaves of cach tree, as defined in equation [5]
Finally, we note that for graph generation, the trees T, must be constructed sequentially. However, each Tu can still be built in O(log n) time, reducing the overall runtime from O(n?) O((n + m) logn).
A.3 Adjacency-LSTM Motivation
The primary issue with using an LSTM to build the adjacency matrix a graph is that most recurrent neural networks are best suitod for lincar data. Flattening an adjacency matrix and using an LSTM is one potential avenue for building a model, but suffers from significant drawbacks the flattened vector varies based upon the node ordering म, and the model sacrifices the underlying structure of A. YYou et al. 2018
22

---

Published in Transactions on Machine Learning Research (ettober/202)
Algorithm 2 Adjacency-LSTM Sampling Algorithm
Input: Number of nodes
1: Initialization Initial row node state $Ñ.0 (bo,o: Co,0)
2: for = 1...., 12 do
3: 8:0 = si-1,i-1 + Pos(n + 1- (initialize new row node state]
for j < do
Si - (-1z)
fconcatenate previous node states of row i and column j}
Pij (lfr()))))
7:
Sample edge eij Bernoulli(p.s)
8:
if edge exists then
9:
Mij = =ff(h;) (hij)
10:
log 2 = (hos)
11:
Eij Normal(jig, 0tj)
12:
wij log(1 + exp(eij))
13:
else
14:
Wij =
15:
end if
16:
embed(eig, wiy) Cat(Eij, for (wis), Pos(n + 1 i), Pos(n - + 5))
17:
st = L=TMMeebee((e)) :: (update adjacency state with edge embedding)
18:
s S = Sp)it(st,)
19: end for
20: s = (set final row node state for subsequent row generation)
21: end for
Output: with (1.2.... n} and E {eij, Wiy li-1sst
Generative models such GraphRNN and GRAN, which recurrent neural networks to build generative models of graphs, circumvent this issue by using node-level and graph-level recurrent networks that maintain edge generation and the global structure of the graph, respectively. Adj-LSTM was inspired by such mot and instead uses a partitioning of the hidden state to take advantage of the grid structure of the adjacency matrix directly. We will also show that partitioning the hidden state of a single LSTM provides greater generative quality, as this facilitates information passing between the states of the row and column nodes.
To adapt the LSTM architecture
two-dimensional adjacency matrix, partition the hidden state of where h and h are the prior hidden states of the row and column nodes corresponding to entry Aij. As all state updates are the same regardless of which entry Aij is being generated, we drop the subscripts and j moving forward.
h
R
the LSTM into b.j = h
1.j
We re-compute the linear recurrence (4) using this partitioning of the hidden state. First, we note the dimensions of each weight and bias vector. Suppose that the hidden dimension is haim and the embedding dimension is idim- Then have the following:
1. h h
h E Rhaim
h E 2haai and W
R 2hatim X2haim
Xıj hi
W. R 2haam Xiamm.
2haii
Hence, we can partition the weight matrices and bias vector from the LSTM equations by defining the following partitions for cach weight matrix:
U
R
W
(18)
U
23

---

Published in Transactions on Machine Learning Research 2october/2255
Table Performance on updating the states simultaneously ("Joint") vs separately (" ("Independent")
Update Mode
Deg.
Clus.
Top Spoc.
Wt. Spec.
MMDWt
Error
Joint
2.46e-1
0.0
9.98e
8.5le 2.46e
4.93e-3
0.065
Independent
3.27e
6.20e
2.98e
6.40e
0.275
VRR VeR
VRC VCc
WA =
(19)
where each U Rhaim and each V**
I hacm Xhaim
Using the partitioning from 18 and 19
and partitioning the bias vector as b
we can partition the
bc
LSTM update equations as
R h
U + vRRn - VRC + b UCx+ + v +
Jointly updating the row and column states allows for the transfer of information between the row and column nodes via the weight matrices V and VCR, which we hypothesized would mitigate the issue of long-term memory as the model predicting entries row-wise, information early in the row-generation process becomes lossy without the joint update property of the LSTM with partitioned hidden state.
To test this hypothesis, we trained the lobster graphs on two models: one which uses the single LSTM- update on the concatenated row and column states, and the other which uses two LSTMs that update the row and the column states independently, which corresponds to setting VCR = VRC = 0 in Equalion 19 As observed in Table the LSTM joint update provides superior results on all observed metrics.
A.4 Tree Weight Generation
The hierarchical sampling scheme of the HW-tree weights provided means of testing for autoregressiveness in the models with respect to the edge weights. There are two main quantities of interest: the global variance of weights pooled across all HW-trees, Var(wsy), and the variance of weights found in a single HW-tree, Var(wiyl (x)) Note a few preliminaries that are easily derived from their respective distributions
(1 ~ UU( = TE(μ)) 10 and Var(ux) =3
2. wij ~ T( ( E(wiylus)) = and Var(wiyl ( =
Importantly, the variance of the weights found in each tree is free the parameter μą. Next, an application of iterative expectation and variance yield the mean and variance of weights pooled from all trees as
E(wyy F (waylua) (xx())= 10.
Var(wy) E,, [Var,,, (wtglpx + Var, (wnglaz)) [mx)] = (1) + (yx, = 1
Thus, for autoregressiveness in the models, we observe that weights pooled from all HW-trees have variance Var(w)y) 4, whereas weights from single HW-tree have variance Var(wiylus, 1.
24

---

Published in Transactions on Machine Learning Research (ottober/202)
A.5 Further Training Details
Hyperparameters For Adj-LSTM, node states were parameterized with a hidden dimension of 128 and use a 2-layer LSTM. An embedding dimension of 32 was used to embed edge existence, and an embedding dimension of 16 was used to embed the weights. Positional encoding was used on the initialized row states.
For all models using BiGG, use a hidden dimension of 256 with position encoding the row states, used in the original BiGG model. The weight state we use for BiGG-E has hidden dimension of 16 for model runs and 32 for scalability runs, For BiGG-E and BIGG+GCN, bits compression of 256 was used on the topology state.
Training Procedure Both models were trained using the Adam Optimizer with weight decay and initial learning rate of Le-3, The learning rate is decreased to 1e-5 when training loss plateus. Separate plateus are used for the weight parameters and the topology paramcters.
For the lobster data set, we train BiGG-E and BiGG-MLP for 250 epochs and validate at the 100 and 200th epochs. We plateau weight at epoch 50 and topology at epoch 100. We train Adj-LSTM for 300 epochs and validate every 100 epochs. We decay the learning rate at the 25 and 100th epochs.
For the HW-tree data set, we train BiGG-E and BiGG-MLP for 550 epochs and validate every 100
epoch. We plateu weight at epoch 150 and topology at epoch 200. We train Adj-LSTM for 100 epochs and validate every 25 epochs, where the learning rate is plateaued at epochs 25 and 50. For the Erdös Rényi data set, BiGG-E was trained for 500 epochs and validated every 250 epochs. We platcu weight at epoch 100 and topology at epoch 500. Due to slow training and poor conver- gence, the Adjacency-LSTM was only trained for 27 epochs.
For the 3D Point Cloud data set, BiGG-E was trained for 3000 epochs and validated every 1000 epochs. We plateu weight at epoch 500 and topology epoch Adj-LAMM was reported out of memory for this dataset.
For the PT-tree graphs, BiGG-E was trained for 1000 epochs. We plateu weight and topology at 500 epochs.
BiGG-MLP and BiGG+GCN follow the training protocol for BiGG-E. For the convolutional network, two convolutions were used and each component was trained jointly on the same objective function used on BiGG-E.
Baseline Models The global probability of an edge existing between two nodes based on the training data, and then constructing Erdös-Rényí graphs with that probability edge existence, as done in (You et al. 2018). Weights were sampled with replacement from all possible training weights in order to produce weighted graphs.
model baseline estimates were generated by first estimating the
Regularization We use the following to regularize our models, noting there is propensity for the models to overtrain on the edge weights and decrease generative quality of the graphs. We believe this is directly related to the issuc of balancing two losses the topological and weight losses - which is further compounded by the fact learning the topology of a graph is much more challenging than the edge weights due to super- exponentially growing configuration space of graphs with respect to the number of nodes n. We note while BiGG-E had a tendency to overtrain on edge weights when plateauing the loss, the effect was much more prominent with BiGG-MLP, and regularization attempts were less successful with BiGG-MLP than on BiGG-E. As such, we use the following regularization on all models:
We use weight decay on the Adam optimizer with decay 1e on topology parameters and 1 on weight parameters.
Prior to inputting the sampled weight through the embedding LSTM, we standardize the weight as = .. (w - w) where and sw and the mcan and standard deviation of all training weights, respectively. We note this is because the model is general purpose and must handle weights of varying magnitudes, where larger weights can potentially saturate the output of the embedding LSTM.
25

---

Published in Transactions on Machine Learning Research 2october/225)
The loss for weight is scaled down by factor of 10 to balance the topology and weight losses. Upon plateauing both sets of parameters, the scale was increased to a factor of 100 for all graphs except the PT-tree graphs.
When both losses were plateaued, the weight loss was updated every other epoch instead of every epoch to allow more fine-tuning of the graph topology without encouraging overtraining on the edge weights.
A.6 Further Experimental Setup Details
Here, we provide additional details on our experimental setup. First, we describe the metrics used in detail, followed by controls used ensure fair comparison across models.
Evaluation Metries We divide metries into three main groups: topology-only metrics, weight-only
metrics, and joint metrics. We describe each metric in more detail here. First, we consider our topology-only
metrics, noting these metrics are identical to the ones used in Liao et al. (2019). You et al. (0018). and Dai
et al. 20200:
MMD on Degree (Deg.): distributions of unweighted degrees are computed for each graph. We
use the Gaussian Total Variation kernel when computing the MMD (Liao al. 2019).
MMD on Cluster (Clus.): distributions of unweighted clustering coefficients are computed for each graph. We use the Gaussian Total Variation kernel when computing the MMD.
MMD On Orbit: distributions of the number of occurrences of orbits with 4 nodes (Liao et al.
2019h.
MMD on Spectrum (Spec.): distributions of the spectral (set of eigenvalues) of each graph's normalized unweighted Laplacian matrix are computed. We use the Gaussian Total Variation kernel when computing the MMD.
Error: this represents the percentage of graphs that do not hold global graph property. For example, in the tree and yeast dataset, this is the percentage of graphs that not true bifurcating trees with the correct number of leaves.
Next, consider our weight-only metrics:
Global mean (17): We pool all edge weights from all graphs to compute the global mean weight generated by each model.
Global standard deviation (sw): We pool all edge weights from all graphs to compute the global standard deviation generated by each model.
Within tree standard deviation (sr): For the tree dataset, we compute the standard deviation of weights found within each tree and then compute the mean of those standard deviations.
MMD on Marginal Weights (MMDWT): We consider the marginal distribution of weights per graph. We use the Gaussian earth mover distance (EMD) (Liao et al. 2019) when computing the MMD, as we found the EMD was a distance metric capable of considering outliers in the edge data sets. We found that the wildly different scales edge weights were on led to sensitivies to the MMDs, so the bandwidth a was tuned to an appropriate value using random partitions the training graphs for each graph dataset, as needed.
Finally, consider our joint metrics:
MMD Weighted Spectrum (Spec.): distributions of the spectral (set of cigenvalues) of each graph's 's normalized weighted Laplacian matrix are computed. We use the Gaussian Total Variation kernel when computing the MMD.
MMD on Weighted Degree (Wtd. Deg.): for each graph. We use the Gaussian Total Variation kernel when computing the MMD.
distributions of unweighted degrees are computed
Finally, we report the rank of each model within and across all datasets. The rank computed by comparing the various metrics from the set (Mean SD, Mean, Mean + SD). For the global rank, ranks across datasets are pooled. Results reported as Mean Rank + SD Rank.
26

---

Published in Transactions on Machine Learning Research (october/2255
Model Comparison To ensure fair comparison between all models when running experience, we imple- mented the following controls:
We ran each model using the same seeds and reported the mean statistic and standard deviation
ans mean = standard deviation.
Each model was trained on and compared with the same set of training and test graphs, respectively.
All MMD computations used the same hyperparameters and kernels.
27


Reviews:
[{"review_id": "heVYfejbbn", "reviewer": "Reviewer_EaE3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this work, the authors extend the BiGG model for generating large-scale unweighted graphs to BiGG-E, generating weighted graphs while preserving the scalability, and in particular, the runtime complexity, of BiGG. The authors leverage the Fenwick tree construction from BiGG to also sample edge weights but do this in a joint modeling approach which allows to condition an edge weight on both the previously generated topological and edge weight features. The authors demonstrate empirically that BiGG-E's joint modeling approach outperforms naive extensions of BiGG as well as decoupled generation of topology and edge weights and scales to graphs up to 15K nodes.\n\nI find the paper to be clear and properly motivated but I have doubts about the statistical significance of the results (see below for details).", "claims_and_evidence_yn": "No", "claims_explanation": "To my understanding, the main claims of the paper are:\n\n**C1**: *BiGG-E is an extension of BiGG to support weighted graphs while maintaining the scalability of BiGG.*\n\nBiGG-E maintains the scalability of BiGG by leveraging the Fenwick tree also for the weights, essentially only adding one parallel computational stream to BiGG. The authors further demonstrate this empirically, showing that generation time, memory requirements, and training time between BiGG and BiGG-E are fairly similar.\n\n**C2**: *BiGG-E's joint modeling approach is more effective than naive extensions of BiGG.*\n\nThe authors provide two more extensions of BiGG as baselines which I would agree are straightforward ways to incorporate edge weights into BiGG: Generating edge weights directly based on the current topological state (BiGG-MLP) and first generating the graph and then predicting the edge weights after (BiGG-GCN). BiGG-E appears to surpass both approaches but I have some doubts about the standard error of the numbers in Table 1 and 2: In Table 1, no error bars are given. Considering the small size of the training datasets and the small MMD scores of the BiGG baselines, I wonder whether these results are statistically significant. In particular, the authors should have repeated these experiments multiple times and report standard error of these scores. In Table 2, the authors appear to provide standard deviation (SD). However, the SD is so high that the results do not appear to be statistically significant. However, it could be that I am misunderstanding these scores. Unfortunately, the paper does not provide a lot of explanation to the exact computation and meaning of these scores.", "audience_yn": "Yes", "audience_explanation": "The paper is highly interesting to the graph generative community. In particular, the question of how to properly generate weighted graphs, and the investigation  into different approaches to do so, as done in this work, are of some significance to the field.", "requested_changes": "Regarding my concerns on the validity of **C2** above, I recommend the following changes:\n\n* The authors should provide more explanation to the computation and interpretation of the different MMD metrics computed for topological and edge weight quality of the compared models. In particular, the authors should make clear whether the SD in Table 2 refers to the standard deviation of the edge weight accuracy.\n\n* The authors should repeat their experiments multiple times and provide error bars for their reported scores to asses whether the results are statistically significant.", "broader_impact_concerns": "n/a", "additional_comments": "n/a", "extra_scores": {}, "extra_text": {}}, {"review_id": "j1gS1mEQg0", "reviewer": "Reviewer_UjLQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a graph generative model that builds upon the autoregressive BiGG model, with a focus on weighted graph data. Benchmark experiments show some improvements over the chosen baselines. However, I have major concerns regarding the novelty of the method and the comprehensiveness of the performance evaluation, which affect the overall scientific contribution of this manuscript.", "claims_and_evidence_yn": "No", "claims_explanation": "## 1. Insufficient baseline comparisons\n\nThere are many recent and powerful graph generative models published in the research community. Many of them have conducted experiments on molecular or vision weighted graph datasets—such as those listed in references [1–6]—which include discrete edge labels, and some have also experimented with data containing continuous edge labels, such as [2]. The authors mention and discuss some of these papers but do not compare their model’s performance against them. Even if the paper specifically focuses on weighted graph generation, it would still be worthwhile to compare against variants of these baselines to provide a fair and comprehensive assessment of model performance.\n\n## 2. Lack of novelty in model design\nThe proposed BiGG-E model closely resembles the original BiGG model in many aspects, including its reliance on the Fenwick data structure. It appears to be more of an engineering refinement of the original model, rather than one that introduces substantial methodological innovation.\n\n## 3. Limited relevance of benchmark datasets\nMost of the benchmark datasets used are standard plain graph datasets with stochastically generated (synthetic) edge labels. This setup does not effectively demonstrate the practical value of modeling weighted graphs, nor does it convincingly show that the model captures real-world data distributions.\n\nReference:\n\n[1] SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generation\n\n[2] Joint generative modeling of scene graphs and images via diffusion models\n\n[3] Digress: Discrete denoising diffusion for graph generation\n\n[4] Score-based generative modeling of graphs via the system of stochastic differential equations\n\n[5] Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation\n\n[6] Equivariant Denoisers Cannot Copy Graphs: Align Your Graph Diffusion Models", "audience_yn": "No", "audience_explanation": "While the manuscript presents an attempt to extend the BiGG model to weighted graph generation, it currently appears underdeveloped in several key areas. The level of methodological innovation is limited, the writing and structure need refinement for better clarity, and the experimental evaluation lacks depth and comprehensive baseline comparisons. Given these concerns, I feel that the manuscript, in its current form, does not yet meet the standards expected for publication at TMLR as an original research contribution. I encourage the authors to further strengthen the novelty, improve the clarity of presentation, and conduct more thorough experiments to better support their claims.", "requested_changes": "Please address concerns regarding the model's novelty and the performance evaluation protocol to strengthen the contributions.\n\nThe writing and structure of the paper can also be improved for better clarity and readability. Please rephrase the second setence of the abstract for clarity: \"However, most current deep generative models are either designed for unweighted graphs and are not easily extended to weighted topologies or incorporate edge weights without consideration of a joint distribution with topology.\"", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7xECSRtwLm", "reviewer": "Reviewer_cekc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work targeted on a scalable graph generation problem where graphs may contain weighted edges. Specifically, it proposes BIGG-E, built on top of a previous research work BIGG. To summarize, the contributions are as follow:\n1. This work proposes a new graph generative model adopted from BIGG to tackle the weight graph generation problem.\n2. Experiments support the claims that BiGG-E demonstrate better performance in generating large weight graphs.\n\n**strengths**:\n1. The paper is well structured and have clearly demonstrated the target problem to be solve\n2. The proposed component that enable BiGG to model weight graph, BiGG-E, is novel and the design is reasonable.\n\n**weakness**:\n1. While the proposed component is novel, it is a modification on top of an existing model. I'd like to see a better justification of why it is designed in that way rather than other model architecture choices. \n2. The overall contributions of the work are insufficient for a long paper submission, I suggest the authors considers a short paper venue or a workshop submission\n3. The work propose datasets for modeling and evaluation, specifically, it turns the graph datasets used in BIGG into weight graph datasets. Moreover, the edge weight are assigned by sampling from some simple distribution (normal/uniform/etc...) and with some simple transform. While the experiment demonstrate that BiGG perform well on the modified datasets. It not clear this is a valid assessment. I will suggest the authors try their methods on some real weighted graph datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "My major concern is on the evaluation -- again since to me the edge weight distribution may be too simple, it doesn't necessarily support the validity of the propose components.", "audience_yn": "Yes", "audience_explanation": "Weight graph is common in real world but to my knowledge there are limited research working on this. Such work could be interesting to some audience working on this area", "requested_changes": "Better weight graph datasets should be introduced to further prove the effectiveness of the propose method.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)