HiGen: Hierarchical Graph Generative Networks

Dear reviewer, We appreciate your valuable feedback and review. Here are our responses to your concerns

1. We have incorporated training and sampling pseudocode into the appendix, complementing the visual representations in Figures 1 and 2 to illustrate and improve the readability of the proposed method.

2.a Our evaluation methodology aligns with established practices in the literature for comparing generated graph quality, comparing not only widely accepted metrics such as MMD for structure-based statistics against the best results reported in the baseline papers but also evaluating and reporting the recent GNN-based performance metrics. The reported improvements in graph generation quality, together with enhanced sampling time and scalability to large point cloud graphs, where many existing methods face challenges, signify a substantial advancement. Complexity and sampling time analysis also supports the scalability of the proposed method.

2.b Theoretical Framework: The proposed method is supported by theoretical results that contribute to its effectiveness. The hierarchical chain structure for graph generation (eq. (1)), the use of separate networks for modeling communities and bipartites, the application of multinomial models (as demonstrated in Theorem 3.1), and decomposition of the multinomial distributions as a recursive model (Theorem 3.2 and Lemma B.3), all form part of a robust theoretical foundation. The focus on multinomial distribution for edge weight is justified by the need to reverse a graph coarsening algorithm that preserves the number of edges in the community and cross-community in the coarsened hierarchical graph. The weights in such a hierarchical graph can best be described by a multinomial distribution (more details are presented in section 3 and lemma B.2). Since the multinomial is a joint distribution over all the edges in the graph, in order to get a scalable and efficient generative model it is crucial to break it into distribution of the sub-graphs (as presented by factorization results in Theorem 3.1) and also to describe this joint distribution as an autoregressive generative model (Theorem 3.2 for group-wise autoregressive generation or Lemma B.3 for edgewise autoregressive generation). Moreover, the term "learning multi-scale" in the introduction and the conclusion refers to the hierarchical and cluster-based generative model inherent in our approach.

Typos: are fixed in the new version.

We hope these have addressed your questions. Your insights and suggestions are highly valued and we remain committed to addressing any outstanding concerns you may have.

Dear reviewer,

Thank you for your thorough review and the insightful feedback. We are pleased to see that you found the proposed hierarchical graph generative model compelling and recognized its novelty. Here are our responses to your questions:

1. We have included a complete complexity analysis together with pseudocodes for training and graph sampling in the revised version of the manuscript.
2. Molecule graph generation: HiGen offers a versatile framework for efficient and scalable graph generation, emphasizing on capturing the hierarchical and community structures in graphs. In order to generate attributed graphs, such as molecules, we need to modify the proposed community generation and cross-community predictor to learn attributed edges or use the graph generation models with such capability.

One strategy for extending HiGen for graphs with edge types involves assigning a weight vector $\mathbf{w}\_{i, j}^l \in \mathbb{Z}^d$ to each edge $e\_{i, j}^l = (i, j)$, where $d$ is the number of edge types and each feature indicates the number of one specific edge type that the edge $e\_{i,j}^l$ at a level $l$ is representing. The autoregressive multinomial and binomial generative models offered in this work can then be applied to each dimension so that the attributed graph at level $l+1$ is generated based on its parent attributed graph $\mathcal{G}^l$. Note that, in this approach, the attribute of node $v_i$ can be added as a self loop edge $e\_{i,i} = (i, i)$ with weight $\mathbf{w}\_{i,i}=\mathbf{x}\_i$.

Another approach is training an additional predictor, such as a GNN model for edge/node classification, dedicated to predicting edge and node types based on the graph structure. We incorporated a detailed discussion for attributed graph generation in Appendix C.

3. In our experiments, we predefined the number of levels. However, the flexibility of this generative model extends to datasets with a varying number of levels, for which we can augment $\mathcal{HG}$s with fewer levels by appending empty graphs at the top levels during training, ensuring these levels are not sampled. During generation, we can sample the number of levels from the empirical distribution (histogram) observed in the training graphs. Currently, we utilize the empirical distribution of the training dataset solely to estimate the total number of edges $w_0$, implicitly indicating the final size of the graph.

Regarding the number of communities at level $l$, it corresponds to the number of nodes at the parent level. Each node at level $l-1$ becomes a community in the subsequent level.

Community sizes: It is worth mentioning that a notable feature of the proposed multinomial autoregressive (AR) model is that it does not require an extra model to estimate the community sizes before generation. At the initiation of the process for generating community $\mathcal{C}\_i$, the total and remaining weight of the community are set based on its parent node weight, ($r_i = w\_{ii}^{l-1}$). progressively adds new nodes and samples their edges using the recursive multinomial/binomial process outlined in Theorem 3.2 until the remaining weight reaches $0$. Further details are provided in Algorithm 2 in Appendix C.

4. Although Novelty metric was used in (Martinkus et al., 2022) to ensure diverse graph generation, it doesn’t seem to serve as a distinctive metric as it was reported as 100% across all the generative algorithms for SBM and Protein datasets in that study.

In contrast, random-GNN-based metrics such as GNN RBF (using MMD with RBF kernel) and GNN F1 PR (harmonic mean of improved precision+recall), that we reported in table 1 for Ego dataset and appendix E, exhibit strong correlation with the graph diversity (Thompson et al., 2022).

We hope our response has addressed all your questions. We highly value your insights and suggestions and are committed to addressing any outstanding concern you may have.

Dear reviewer,

Thank you for your thorough review and the insightful feedback. We are pleased to see that you found the proposed method compelling and recognized its strengths. In response to your suggestion, we have included a complete complexity analysis together with pseudocodes for training and graph sampling in the revised version of the manuscript. We hope this addition addresses your concern. Your feedback is highly valuable and we are committed to addressing any outstanding concern you may have.

Dear reviewer,

Thank you for your thorough review and the insightful and constructive feedback. We are pleased to see that you found the proposed method compelling and recognized its strengths. In the following, we answer your questions:

1. Connected Graph Assumption: Indeed, the proposed method is not restricted to connected graphs and has the capability to model and generate graphs with disconnected components as well. HiGen learns to reverse a graph coarsening algorithm such as Louvain, and if a graph is disconnected, the output of the coarsening algorithm is an $\mathcal{HG}$ which has a disconnected graph at the top level ($l=1$ in figure (1.a)). To illustrate, let's consider the example graph in Figure 1.a being disconnected into two left and right components (by removing the edge between the yellow and blue communities and the edge between the cyan and orange communities, and subsequently removing their corresponding edge with $weight=1$ at the top level ($l=1$)), therefore the coarsened graph at the top level is a disconnected community composed of two components. Consequently, in a hierarchical graph generation, HiGen first generates a community with two disconnected components for the $l=1$ then the subsequent final graph (leaf level graph) will be a disconnected graph. An advantageous feature of the proposed model is its ability to enforce connected graph generation by constraining the total sum of the candidate edge weights to $v_t >0$ in the recursive stick-breaking process. This was achieved by modeling and sampling an auxiliary variable $v’_t >= 0$ from the binomial distribution in theorem 3.2 and then setting its effective value as $v_t = v’_t +1$. This guarantees that there is at least one edge between the new node and the already generated community in the autoregressive community generation process. As our experimental datasets had connected graphs, we modeled them as connected using the aforementioned technique. However, to potentially generate disconnected graphs, we need to relax the community generation at level $l=1$ to include disconnected communities while we can restrict to connected community generation for the rest of the levels, $l>1$.

2. Capturing and maintaining of global graph structure: Indeed, a key advantage of the proposed hierarchical method is its ability to condition the graph generation at each level on the graph at the parent level, as modeled by $p(\mathcal{G}^l | \mathcal{G}^{l-1})$. Therefore, when generating community graphs at level $l$, the previously generated coarser graph at its parent level inherently encapsulates the global structure of the graph, therefore concatenating its node/edge embedding in community and bipartite generation (eq (6, 7) ) effectively captures global structure and long-range interactions within the graphs. Therefore, by looking at its parent graph, HiGen ensures maintaining control over the global graph distribution while the non hierarchical methods lack such capability. This mechanism enables HiGen to take advantage of consistency across multiple levels of global graph abstraction throughout the hierarchical generation process.

I hope these have addressed all your questions. We highly value your insights and suggestions and are committed to addressing any outstanding concern you may have.

Dear reviewer,

We appreciate your comprehensive review and the insightful feedback. In the following, we answer the questions and provide clarification on the concerns:

Attributed Graph: HiGen offers a versatile framework for efficient and scalable graph generation, emphasizing the capture of hierarchical and community structures in graphs. Adapting HiGen to handle attributed graphs involves reversing the partitioning (coarsening) algorithms tailored for clustering attributed graphs like molecular structures, for example a GNN-based clustering method inspired by the spectral relaxation of modularity metric for graphs with node attributes proposed by Tsitsulin et al., (2020). Toward that goal, we need to modify the proposed community generation and cross-community predictor to learn attributed edges or use the graph generation models with such capability.

Extending HiGen for graphs with edge types involves assigning a weight vector $\mathbf{w}\_{i, j}^l \in \mathbb{Z}^d$ to each edge $e{i, j}^l = (i, j)$, where $d$ is the number of edge types and each feature indicates the number of one specific edge type that the edge $e_{i,j}^l$ at a level $l$ is representing. The autoregressive multinomial and binomial generative models presented in this work can then be applied to each dimension so that the attributed graph at level $l+1$ is generated based on its parent attributed graph $\mathcal{G}^l$. Note that, in this approach, the attribute of node $v_i$ can be added as a self loop edge $e_{i,i} = (i, i)$ with weight $\mathbf{w}\_{i,i}=x_i$. Consequently, the model only needs to predict the edge attributes (or edge types) , aligning with HiGen's edge weight generation capabilities.

Another approach, as you mentioned, is training an additional predictor, such as a GNN model for edge/node classification, dedicated to predicting edge and node types based on the graph structure. This model doesn’t have the difficulties associated with graph topology generation – such as graph isomorphism, automorphism and edge independence – focusing solely on predicting edge/node attributes. This additional model can be tailored to specific application requirements and characteristics. However, the primary focus of this work is to demonstrate the efficiency and scalability of the hierarchical framework. Addressing attributed graphs is acknowledged as a potential future avenue for research.

• Performance Dependence on Partitioning Algorithm: In Table 12 (Appendix E), the performance of the proposed model is compared for two families of graph partitioning algorithms: modularity based Louvain algorithm and spectral clustering based algorithm. These results demonstrate the robustness of HiGen against different graph partitioning functions. Furthermore, in Table 2, the performance of HiGen is provided for the large point cloud dataset against two different hyperparameters of graph coarsening algorithm, $L=2$ vs $L=3$.

• Comparison of HiGen and HiGen-m: The performance difference between HiGen and HiGen-m is primarily attributed to the modeling choices for the probability distribution of community edges' weights at the leaf level. HiGen employs a mixture of Bernoulli distributions for this purpose, while HiGen-m opts for a mixture of multinomial distributions. The key distinction lies in the nature of the edge weights at the leaf level in our experiments, where the distribution of binary edge weights at the leaf level can be better specified by a mixture of Bernoulli. This can explain why HiGen outperforms HiGen-m in most metrics.