- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes a graph generation method which allows conditioning on graph level topological attributes, such as number of maximum cliques, diameter and density. Many of such attributes are discrete, making them non-differentiable w.r.t. adding edges. This makes it difficult to enforce them directly through a loss. This paper takes a different approach by learning a graph-conditioned and attribute-conditioned latent distribution, which are progressively aligned using Wasserstein latent alignment. This approach makes it possible to include a wide set of conditioning attributes, while the downside of the latent alignment approach is that the attributes are soft conditioning signals, so there is no direct supervision signal from attributes during graph generation. The graph is constructed with a one-shot adjacency-based decoder. Expeirments show that the method produces graphs with similar attribute vectors, while structural evaluation metrics are mixed.
Critical strengths
The topic of conditional graph generation is very relevant and there are no great solutions for this problem yet. Most graph generation approaches do not allow conditioning on graph properties. Latent alignment is an interesting approach to this problem and it does not require the attributes to be differentiable.
Critical weaknesses
W1: Equation (11) does not specify how the graph reconstruction loss is computed. Based on (8) I assume it is an edgewise cross-entropy loss between the predicted and ground truth adjacency matrices. This means the loss assumes a fixed node ordering. However, the graph encoder uses a GNN and mean pooling making it permutation invariant. Thus, a permutation of a ground truth graph gives the same graph latent but differs in the adjacency matrix target. Graph-level graph generation typically addresses this with some kind of graph matching or fixed node ordering (not available for all graph families). It is unclear how this problem is resolved here.
W2: The mechanism for controlling graph size is indirect. The decoder works with a fixed-size adjacency matrix, and post-processing keeps the largest connected component. Thus, the requested size is only achieved if the decoder happens to produce a largest connected component with the given number of nodes. More targeted experiments would be necessary to establish that this mechanism actually reliably controls graph size. Also, it is unclear how unused nodes are handled in the reconstruction loss.
W3: Structural fidelity results are mixed, with improvements over the baselines only in some settings. This is attributed to a tradeoff between structural fidelity and attribute controllability. However, it could be that the simple adjacency-based decoder is fundamentally limited and cannot produce more complex graph structures.
W4: The number of seeds is not reported and standard deviations are not shown.
Questions for authors
Did you try interpolating or extrapolating in the attribute space, rather than using only attribute vectors computed from existing graphs? This would be the strongest application in my view.
To interpret the attribute-wise performance in Table 11, one (or both) of the following could be helpful to get a sense of scale for the reported numbers
- report average and standard deviation of each given attribute for graphs in a given dataset
- report the attribute-wise performance for some basline model(s)
8 comments
Response 2
Q: The mechanism for controlling graph size is indirect. The decoder works with a fixed-size adjacency matrix, and post-processing keeps the largest connected component. Thus, the requested size is only achieved if the decoder happens to produce a largest connected component with the given number of nodes. More targeted experiments would be necessary to establish that this mechanism actually reliably controls graph size. Also, it is unclear how unused nodes are handled in the reconstruction loss.
A: The requested node count enters the model through the attribute vector. The decoder outputs a fixed graph, and the reconstruction loss is computed over the full fixed-size adjacency matrix; padded/unused nodes therefore correspond to zero rows and columns and are supervised as non-edges. The true node count is not provided to the decoder or reconstruction loss. After retaining the largest connected component, we obtain:
| Dataset | Mean Target Nodes | Mean Generated Nodes | Mean Abs. Node Error ↓ |
|---|---|---|---|
| WordNet | 17.75 | 13.92 | 3.91 |
| Ogbn-Arxiv | 20.02 | 19.02 | 2.05 |
| MUTAG | 17.67 | 15.22 | 4.00 |
| MOLBACE | 32.27 | 26.66 | 6.26 |
| Citeseer | 19.37 | 18.06 | 1.87 |
| Average | — | — | 3.62 |
Q: To interpret the attribute-wise performance in Table 11, one (or both) of the following could be helpful to get a sense of scale for the reported numbers report average and standard deviation of each given attribute for graphs in a given dataset report the attribute-wise performance for some baseline model(s)
A: Below are the tables for attribute-wise performance of topogen compared with baseline models. The results show consistent improvements in node count, edge count, and number of cliques, for which TopoGen achieves the lowest errors across all five datasets. The gains are not uniform across all controls. Some baselines obtain lower errors for clustering, connectivity, transitivity, treewidth estimates, or diameter.
MUTAG:
| Attribute | DiGress | GraphRNN | GenStat | EDGE | TopoGen |
|---|---|---|---|---|---|
| Density | 0.66 | 0.05 | 0.04 | 0.06 | 0.02 |
| Edges | 17.67 | 7.00 | 8.33 | 9.22 | 3.78 |
| Nodes | 15.00 | 6.00 | 5.67 | 6.33 | 2.78 |
| Node Connectivity | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| Avg. Clustering | 0.00 | 0.00 | 0.00 | 0.25 | 0.06 |
| Closeness Centrality | 0.58 | 0.08 | 0.07 | 0.08 | 0.06 |
| Number of Local Bridges | 4.11 | 3.56 | 3.78 | 2.44 | 3.67 |
| Transitivity | 0.00 | 0.00 | 0.00 | 0.28 | 0.08 |
| Edge Connectivity | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| Number of Cliques | 17.67 | 7.00 | 8.33 | 9.11 | 3.78 |
| Treewidth Min Degree | 1.11 | 0.33 | 0.78 | 0.67 | 0.56 |
| Diameter | 7.89 | 3.11 | 3.11 | 3.11 | 2.22 |
| MAD / Avg. Error | 5.39 | 2.26 | 2.51 | 2.63 | 1.42 |
| SD | 0.88 | 0.21 | 0.21 | 0.28 | 0.14 |
Molbace:
| Attribute | DiGress | GraphRNN | GenStat | EDGE | TopoGen |
|---|---|---|---|---|---|
| Density | 0.55 | 0.02 | 0.02 | 0.03 | 0.02 |
| Edges | 32.60 | 9.22 | 8.65 | 7.87 | 6.57 |
| Nodes | 28.81 | 9.01 | 8.19 | 7.00 | 5.76 |
| Node Connectivity | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| Avg. Clustering | 0.01 | 0.01 | 0.01 | 0.18 | 0.07 |
| Closeness Centrality | 0.57 | 0.04 | 0.04 | 0.06 | 0.05 |
| Number of Local Bridges | 11.11 | 9.42 | 7.47 | 7.89 | 6.08 |
| Transitivity | 0.00 | 0.01 | 0.01 | 0.17 | 0.08 |
| Edge Connectivity | 0.00 | 0.00 | 0.00 | 0.00 | 0.00 |
| Number of Cliques | 32.46 | 9.38 | 8.78 | 8.53 | 7.51 |
| Treewidth Min Degree | 1.03 | 0.10 | 0.08 | 0.78 | 0.41 |
| Diameter | 12.42 | 3.51 | 3.43 | 4.41 | 3.54 |
| MAD / Avg. Error | 9.96 | 3.39 | 3.06 | 3.08 | 2.51 |
| SD | 0.91 | 0.12 | 0.12 | 0.14 | 0.13 |
Citeseer:
| Attribute | DiGress | GraphRNN | GenStat | EDGE | TopoGen |
|---|---|---|---|---|---|
| Density | 0.55 | 0.12 | 0.13 | 0.14 | 0.07 |
| Edges | 27.40 | 24.35 | 25.06 | 26.95 | 5.80 |
| Nodes | 17.77 | 14.36 | 14.24 | 13.15 | 2.04 |
| Node Connectivity | 0.41 | 0.00 | 0.00 | 0.00 | 0.03 |
| Avg. Clustering | 0.23 | 0.20 | 0.17 | 0.26 | 0.17 |
| Closeness Centrality | 0.52 | 0.11 | 0.09 | 0.12 | 0.07 |
| Number of Local Bridges | 7.95 | 7.55 | 5.96 | 4.31 | 4.55 |
| Transitivity | 0.20 | 0.18 | 0.17 | 0.19 | 0.15 |
| Edge Connectivity | 0.41 | 0.01 | 0.04 | 0.00 | 0.03 |
| Number of Cliques | 18.18 | 16.31 | 16.18 | 11.56 | 4.64 |
| Treewidth Min Degree | 2.17 | 1.40 | 1.13 | 1.36 | 1.10 |
| Diameter | 3.90 | 1.71 | 0.97 | 1.71 | 1.35 |
| MAD / Avg. Error | 6.64 | 5.52 | 5.35 | 4.98 | 1.67 |
| SD | 0.85 | 0.43 | 0.41 | 0.45 | 0.28 |
Response 3
Arxiv:
| Attribute | DiGress | GraphRNN | GenStat | EDGE | TopoGen |
|---|---|---|---|---|---|
| Density | 0.69 | 0.12 | 0.12 | 0.13 | 0.06 |
| Edges | 29.17 | 24.47 | 26.88 | 29.52 | 5.25 |
| Nodes | 18.08 | 13.12 | 13.72 | 13.76 | 1.67 |
| Node Connectivity | 0.15 | 0.01 | 0.02 | 0.02 | 0.09 |
| Avg. Clustering | 0.27 | 0.22 | 0.20 | 0.24 | 0.21 |
| Closeness Centrality | 0.49 | 0.11 | 0.10 | 0.11 | 0.08 |
| Number of Local Bridges | 8.10 | 6.86 | 6.83 | 5.30 | 5.31 |
| Transitivity | 0.16 | 0.15 | 0.14 | 0.15 | 0.13 |
| Edge Connectivity | 0.15 | 0.02 | 0.02 | 0.03 | 0.10 |
| Number of Cliques | 18.51 | 14.81 | 15.96 | 13.91 | 5.57 |
| Treewidth Min Degree | 1.95 | 1.50 | 1.59 | 1.68 | 1.35 |
| Diameter | 2.33 | 1.44 | 0.88 | 1.46 | 1.77 |
| MAD / Avg. Error | 6.67 | 5.24 | 5.54 | 5.53 | 1.80 |
| SD | 0.74 | 0.47 | 0.48 | 0.48 | 0.43 |
Wordnet:
| Attribute | DiGress | GraphRNN | GenStat | EDGE | TopoGen |
|---|---|---|---|---|---|
| Density | 0.66 | 0.12 | 0.10 | 0.13 | 0.09 |
| Edges | 15.99 | 11.81 | 12.74 | 12.09 | 3.01 |
| Nodes | 15.24 | 11.20 | 11.94 | 11.23 | 3.75 |
| Node Connectivity | 0.02 | 0.00 | 0.00 | 0.00 | 0.02 |
| Avg. Clustering | 0.04 | 0.05 | 0.07 | 0.08 | 0.21 |
| Closeness Centrality | 0.37 | 0.08 | 0.08 | 0.08 | 0.07 |
| Number of Local Bridges | 13.92 | 10.47 | 11.19 | 10.37 | 8.99 |
| Transitivity | 0.02 | 0.02 | 0.03 | 0.04 | 0.18 |
| Edge Connectivity | 0.02 | 0.00 | 0.00 | 0.00 | 0.02 |
| Number of Cliques | 15.04 | 11.12 | 11.88 | 11.14 | 3.63 |
| Treewidth Min Degree | 0.33 | 0.37 | 0.45 | 0.44 | 0.99 |
| Diameter | 1.21 | 0.82 | 0.83 | 0.91 | 1.54 |
| MAD / Avg. Error | 5.24 | 3.84 | 4.11 | 3.88 | 1.87 |
| SD | 0.38 | 0.32 | 0.32 | 0.33 | 0.54 |
Response 1
Q: Did you try interpolating or extrapolating in the attribute space, rather than using only attribute vectors computed from existing graphs? This would be the strongest application in my view.
A: Our existing OOD experiment (Table 3) evaluates control vectors outside the training distribution, and these controls are extracted from generated Barabási–Albert graphs. We also evaluated TopoGen using synthetic control vectors formed by interpolating and extrapolating pairs of held-out control vectors. For each dataset, we randomly selected 25 distinct pairs of test control vectors ((ca,cb)). For each pair, we constructed (c(α)=(1−α)ca+αcb), with $(\alpha={0.25,0.5,0.75}) $ for interpolation and (α=−0.25,1.25) for extrapolation, giving 75 interpolation and 50 extrapolation candidates per dataset. Before generation, we rejected structurally infeasible controls, including invalid node/edge counts, bounded attributes outside ([0,1]), and inconsistent node-edge-density combinations. Across the five datasets, 359/375 (95.7%) interpolation controls and 168/250 (67.2%) extrapolation controls passed these checks. The macro-average MAD is 4.58 for interpolation and 4.69 for extrapolation across the five datasets. These results show that TOPOGEN can generate graphs from control vectors at previously unseen points in the attribute space. Interpolated controls are substantially more likely to remain structurally feasible, while extrapolation is more challenging because moving outside the observed attribute space can produce invalid combinations of graph properties.
Q: The number of seeds is not reported and standard deviations are not shown.
A: Below are the results of TOPOGEN over 3 seeds with updated implementation to reduce memory with the rest of the model as is and have updated the result table in the paper.
Q: Structural fidelity results are mixed, with improvements over the baselines only in some settings. This is attributed to a tradeoff between structural fidelity and attribute controllability. However, it could be that the simple adjacency-based decoder is fundamentally limited and cannot produce more complex graph structures.
A: We agree that decoder capacity can affect structural fidelity. To address concerns about the quadratic edge decoder and evaluating on large graphs, we reran TopoGen with an implementation that reduces intermediate memory during pairwise edge prediction and extended evaluation to larger graphs. The decoder still scores all node pairs and therefore remains (O(Nmax2)), but avoids explicitly materializing an (Nmax×Nmax×H) tensor. With these reruns, TopoGen achieves the lowest SD on Citeseer, Ogbn-Arxiv, and MUTAG, and the second-lowest on MOLBACE, with an average SD of 0.304, comparable to the best baseline average of 0.30, while retaining the strongest attribute controllability. We also observe stable SD of 0.46 on Ogbn-Arxiv up to 200 nodes and SD of 0.02 on SBM graphs up to 1000 nodes. These results suggest that the earlier mixed fidelity is not solely due to a fundamental limitation of the adjacency-based decoder, although the (O(Nmax2)) scaling remains a limitation.