GraphMaker: Can Diffusion Models Generate Large Attributed Graphs?

We highly appreciate your detailed and insightful feedback. We address the individual questions as follows.

1. The manuscript presents an evaluation that examines how well models trained on the generated training data align with the models trained on the original training data, when applied to the original test data. The evaluation result shows that stochastic block model (SBM), when equipped with the empirical distribution computed from the original data $P(Y)\prod_v\prod_f P(X_{v, f} | Y_v)$, is a strong baseline. The proposed GraphMaker models only marginally outperform SBM. One possible explanation is that the graphs used in the empirical study are too homophilous, and thus the label-conditioning mechanism of GraphMaker could be essentially learning inter-cluster and intra-cluster edge densities employed by SBM. A natural question is then if the authors considered benchmarking on less homophilous graphs, where GraphMaker is more likely to have an edge in performance.

This is indeed a critical insight. Various homophily measures have been developed to measure the similarity between nodes and their neighbors in a graph [1-3], in particular the proportion of nodes that have the same label as their neighbors. These papers have pointed out that Cora and Citeseer are highly homophilous, and it’s likely that Amazon Photo and Amazon Computer also have this issue. When we apply SBM to such graphs, with high probability the generated nodes will be connected to neighbors that have the same label. In addition, the node attributes can also be approximately conditionally independent of each other given the node label, as shown in Table 8 in the Appendix. These two factors may explain the competitive performance achieved by SBM for MPNNs, which perform localized smoothing.

We agree that more heterophilous datasets with more complicated attribute, label, and structure correlations can be better testbeds. We plan to include such datasets in the next version of the paper.

2. Lack of performance comparison against recent diffusion-based graph generative models like EDGE

As mentioned in the above unified response, we agree that a direct comparison will help us better understand the strengths and limitations of the proposed model. We plan to include some previous diffusion-based graph generative models as additional baselines in the next version of the manuscript.

3. What is GraphMaker-E doing? How does it differ from GraphMaker-Async?

We apologize for not well articulating the presentation for this variant. As elaborated in the above unified response, we replace the trained attribute diffusion model with $P(Y)\prod_v\prod_f P(X_{v, f} | Y_v)$, the empirical distributions computed from the original data, as explained in section 4.1. This allows a direct comparison of the structure generation capability of GraphMaker against baselines without attribute generation capability.

[1] Pei et al. Geom-GCN: Geometric Graph Convolutional Networks.

[2] Zhu et al. Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs.

[3] Lim et al. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods.

Again, we thank the reviewer for the efforts in providing valuable feedback. We address the individual questions as follows.

1. What’s the difference between link prediction and graph generation?

Link prediction considers the scenario of inferring additional edges from an existing incomplete graph [1, 2]. In contrast, graph generation requires creating a graph from scratch without leveraging an existing incomplete graph [3, 4].

2. What is the time complexity of GraphMaker for edge generation? What is the minibatch strategy introduced in the introduction part?

GraphMaker first samples a noisy graph from the prior distribution, and then repeatedly refines it. At each timestep, it computes node representations with an MPNN, and then performs binary classification for all node pairs. This yields a time complexity of $O(TN^2)$, where $T$ is the number of diffusion steps and $N$ is the number of nodes. While this appears to be costly, we only need to perform node representation computation once per diffusion step, which can be used for all node pairs. Besides, binary classification for multiple node pairs given node representations can be performed in parallel. In addition, the optimal $T$ is less than 10 based on empirical studies. In terms of wall clock time, generating the largest graph (13K nodes) considered in the paper with the most costly GraphMaker model takes less than 10 minutes on an NVIDIA RTX A6000 GPU during inference.

Another issue is the space complexity of $O(N^2)$, which prevents us from performing binary classification for all node pairs at once on a single GPU. Hence we adopt the minibatch strategy. During training, we use a minibatch of node pairs for a gradient update. During inference, we generate the whole graph structure by iterating over minibatches of node pairs.

For larger graphs, we agree that $O(N^2)$ indeed will be problematic, and we may leverage methods for approximate nearest neighbor. For example, locality sensitive hashing [5] hashes similar data points into the same bucket with high probability, and therefore it avoids all pair comparisons.

3. Lack of performance comparison against recent diffusion-based graph generative models

As mentioned in the above unified response, we agree that a direct comparison will help us better understand the strengths and limitations of the proposed model. We plan to include some previous diffusion-based graph generative models as additional baselines in the next version of the manuscript.

4. What are the application scenarios of large attributed graph generation?

As mentioned in the above unified response, this task can benefit the understanding of attributed complex networks for network science and the sharing of sensitive networked data for public usage.

[1] Liben-Nowell & Kleinberg. The Link Prediction Problem for Social Networks.

[2] Zhang & Chen. Link Prediction Based on Graph Neural Networks.

[3] You et al. GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models.

[4] Yoon et al. Graph Generative Model for Benchmarking Graph Neural Networks.

[5] Indyk & Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality.

Thank you so much for reviewing our paper and bringing valuable questions. We address the individual questions as follows.

1. Motivation of the decoupled approach GraphMaker-Async is not well articulated. Besides, the choice of the word ``decoupled'' is misleading.

We provided a motivation for choosing GraphMaker-Async over GraphMaker-Sync from the perspective of edge dependency modeling in the above unified response.

We used the word ``decoupled'' as GraphMaker-Async consists of two subnetworks trained independently and once trained it first generates attributes and then edges conditioned on fixed attributes. We are open to other options if the reviewer has suggestions for better alternatives.

2. What is the difference between node attributes and labels as both of them are categorical in section 2?

The confusion comes from the fact that one important application of our generative model is to generate and publish synthetic graphs without sharing the original data. ML models (such as Graph Neural Networks) can be trained over these synthetic graphs and are expected to achieve similar performance as those trained directly over the original graphs. To evaluate our model for this application, we adopted node classification and link prediction tasks as a proof of concept and considered the large-attributed graphs that are widely used for node classification tasks [1, 2]. The node labels defined by the node classification tasks are used as the conditional information in our generation process. It is true that distinguishing labels and attributes is often just an artifact, defined by an ML task, which is irrelevant to the data generation procedure. However, if a downstream ML task is given, using the labels as conditions may indeed help. In our case, we find that directly viewing the node label as a node attribute yields worse performance for more than 80% cases for the downstream node classification tasks as shown in section 4.4.

3. How are node attributes obtained for GraphMaker-E with an external approach conditioned on node labels?

As explained in the unified response, we leverage the empirical distribution $P(Y)\prod_v\prod_f P(X_{v, f} | Y_v)$ computed from the original data for the experiments in this paper. We agree it’s better to mention it explicitly in 3.5 rather than 4.1.

4. What is the application scenario of large attributed graph generation?

As elaborated in the first paragraph and unified response, firstly, large attributed graph generation can enhance the understanding of complex networks [3, 4]. Secondly, the generated graphs can be shared with the public in replacement of the original sensitive data while preserving data utility.

[1] Kipf et al. Semi-Supervised Classification with Graph Convolutional Networks.

[2] Shchur et al. Pitfalls of Graph Neural Network Evaluation.

[3] Watts & Strogatz. Collective dynamics of ‘small-world’ networks.

[4] Barabási & Albert. Emergence of scaling in random networks.

Based on the response (especially on the applications and some technical details), I have increased my score to 5.