On the Role of Edge Dependency in Graph Generative Models

We would like to thank you for your detailed comments and for appreciating the novelty of our theoretical bounds. We address all comments below:

The first phrase of the paper is misleading. It says: "we introduce a novel evaluation framework for generative models of graphs", but there is no evaluation framework.

The evaluation framework that we refer to is that of evaluating graph generative models under the lens of overlap. We believe this angle is missing from the evaluation of graph generative models, in general. Typically, models are evaluated in their ability to mimic properties of the input graph, without the important constraint of generating diverse (low-overlap) graphs. This limits the effectiveness of evaluation, since by simply memorizing the input graph, a model can perfectly mimic its properties, but not be a useful generative model. For example, NetGAN/CELL is known to be able to simply reproduce the input graph. Hence, the authors suggest an early stopping criterion to prevent this from happening. This suggests that early stopping/not reproducing the input graph was an important criteria for their model design. However, this criteria was not formalized or measured in the evaluation of it. Our work formalizes this criteria and advocates using it in graph generative model evaluation going forward.

Regarding the theoretical proposition, I do not have major concerns, but the generative models and results can be improved.

Indeed our theoretical results are tight as we demonstrate with examples and can not be improved further. Regarding the generative models, our target is not to provide a state-of-the-art model, but contribute in two other significant ways: (i) in addition to providing an evaluation framework for studying graph generate models under the overlap criteria, we also provide models for which it is easy to control the overlap and do not rely on heuristic methods, such as early stopping, and (ii) show that even those simple models can perform comparably well to more complex (DL) models in matching graph statistics under a low overlap regime.

It is not clear the relation between the generative model with the theoretical contribution. The paper mentions: "We shift our focus towards empirically evaluating the real-world trade-off between overlap and performance across several specific models on real-world networks.". So, it seems a completely different paper.

Our paper consists of two contributions that we believe are connected: (i) provides theoretical bounds on the power of different graph generative models (under the hierarchy we propose) with respect to the overlap criterion, and (ii) an evaluation of the ability of different models (including our own baselines) to mimic properties of the input graph. As the models we choose fall under different levels of the hierarchy (same for the models we construct) and the evaluation is done under the overlap criterion, we believe these two contributions are strongly connected.

The proposed models are trivial, so it does not seem to be an important contribution. There is no training algorithm for p, and the search of the hyperparameter is a grid search.

The proposed models are simple as our target is not to provide a state-of-the-art model, rather to show that even simple models can perform comparably to complex DL-based models, when we restrict the latter not to simply memorize the input graph. Regarding p, there is no need for grid search. “p” simply controls the amount of overlap between the input and the generated graphs. Naturally, the higher the overlap (thus the value of “p”), the better the generated graphs will mimic the input graph. Hence, “p” is not a value to be fine-tuned, rather it is left to a practitioner to decide how much overlap will allow.

As can be observed in the results, the models can not replicate the characteristics with low overlap. So, it does not seem to fulfill the second characteristic mentioned in the paper "A should exhibit low overlap". This is even worse with the other networks.

The task of replicating characteristics under a low overlap is a hard one as our theoretical results demonstrate. Notice how even deep learning models fail at low overlap. Under our evaluation framework, the overall performance of these deep models is not clearly better than simpler models which are more interpretable and easier to control the overlap.

The details of the experiments are in the appendix, rather than the main paper.

Evaluating all of these methods in the common framework that we propose involves a lot of details, many of which are not crucial to the core takeaways of the work. We believe it is fairly standard to defer such details to the appendix, and given that the supplementary material will be published jointly with the paper, it ensures replicability of our results.

Thank you for your thoughtful review and for finding the proposed hierarchy of graph generative models interesting. We address all comments and questions below:

Overlap seems not to be a good measure for diversity of small graphs since it does not take isomorphism of graphs into account.

Thanks – this is a great point. We have considered the same issue before – one can avoid it by defining a notion of overlap that looks at the maximum edge overlap between two graphs taken over any permutation of the node ids. Unfortunately, this is a very hard metric to compute in both theory and practice, due to its connection to the graph isomorphism problem. Developing a useful metric inspired by this approach that can be computed efficiently, and studying its theoretical properties, would be a very nice direction for future work.

(1) How do you select maximal clique one by one in Algorithm 1? Is there overlap between two max cliques?

We use a fast state of the art implementation for maximal clique listing, more specifically MACE. Indeed, two maximal cliques can overlap. E.g., two 4-cliques can overlap on the 3 common nodes, but each one has a separate node not connected to each other. Hence, edges/nodes common among 2 (or more) maximal cliques have higher probability of being sampled, helping the benchmarks achieve high triangle counts in low overlap.

(2) If the input graph is sparse enough such that the connectivity is weak (for example, most node degrees are 1 or 2), then intuitively, the sampled graph G_p will be broken up seriously. Even after adding a sampled second graph G_r, how does Algorithm 1 guarantee the statistics of G_u?

Nodes of degree 1, or 2, can still be part of a maximal clique (even an edge is a maximal clique if no node can be added to it to make it a clique). Hence, there is a positive probability that edges incident to those nodes will be sampled. Indeed, however, those nodes may end up disconnected. It would be interesting to investigate strategies that can increase the connectivity of the graph while maintaining the degree distribution.

(3) Why the statistics results of GraphVAE are missing in Figures 3-6 and 9?

GraphVAE is a method designed for generating small networks (GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders), hence it faces scalability issues for moderate to large sized graphs. For this reason, we only evaluate this method on a subset of small-sized datasets. Notice that this method employs a fully connected MLP to generate all $n \choose 2$ possible edges, hence for graphs >1K we face both runtime and memory issues.

(4) How do you generate the small subgraphs of benchmarks in Table 2? Is there a unified approach for this?

Yes, we use a unified approach for all datasets. The approach is based on using a maximal clique enumeration algorithm (see answer to 1), followed by Algorithm 1 that samples either (i) each edge of a maximal clique independently for the EI benchmark, (ii) each node of a maximal clique independently for the NI benchmark, or (iii) each maximal clique independently for the FD benchmark.

(5) How large a graph can this method apply to? Do the experiments not use large datasets just because it is difficult to verify the results?

The scalability of this approach depends on the maximal clique listing algorithm used. We could easily scale to graphs of ~4-5k nodes, which is comparable (or larger) to the size of graphs that DL methods can scale to (e.g., NetGAN/CELL, or GraphRNN). For applications to larger networks, we note that our models only need some groupings of the input graph’s edges, not necessarily its maximal cliques. Therefore, edge groupings like dense subgraph discovery, decomposition methods (Elfarouk et al. 2022), and near-clique discovery (Tsourakakis et al. 2013), which are tractable to compute, could be used instead of max cliques.

(6) Is there manifest applications of your framework in practical use, e.g., spread in social for financial networks or drug discovery?

Our methods and theoretical results highlight powers and limitations of three classes of graph generative models. We provide theoretical results for the ability (or shortcomings) of each class of models to generate diverse graphs that are triangle (or k-cycle) dense. We believe our findings are useful in applications that rely on generating diverse graphs under certain constraints.

Drug discovery is such an example of constrained graph generation, where diversity is also crucial. Our results are also especially relevant to modeling social networks, which typically exhibit high triangle density. Generating realistic and diverse social network graphs is important when privacy concerns arise, when testing the robustness of community detection algorithms, and beyond.

Why do we need bounds or theoretical limits on the number of triangles and other short-length cycles?

Triangle density is a hallmark property of several types of networks. Closely related is the idea of triadic closure, that if a node A links to a node B and also to a node C, then B and C themselves are likely to be linked. This is a fundamental characteristic of social networks, among other kinds of networks, and plays an important role in network analysis. If a graph generative model is limited in its capacity to produce graphs with many triangles, it is limited in its capacity to generate many kinds of realistic networks. These bounds therefore help characterize the power of graph generative models. It has been an important goal of recent work in the area to understand theoretical limits on the ability of various graph models to represent triangle-dense graphs — for example, see the work of Seshadhri et al. (2020) on “The impossibility of low-rank representations for triangle-rich complex networks.”

Is it right that the proposed evaluation framework is to compare the overlap between generated graphs and test graphs? …What does the x-axis mean in Figure 2? I can briefly understand that the lines following the dotted line (True) are desirable but cannot understand what Figure 2 means exactly.

The x-axis in Figure 2 is the overlap of a model that was fit to an input graph; each curve represents a different method with which to fit a model, such as GraphVAE. The y-axis represents accuracy, since, as you note, it shows how closely these models match some statistic, such as triangle count, of the input graph, which is shown by the “True” dotted line. Therefore, these are essentially several plots of accuracy vs diversity. What we find is that methods overall struggle to attain high accuracy while maintaining high diversity, and as the diversity requirement is decreased even simple methods like the ones we propose can be competitively accurate as some prior deep ones.

Is triangle-based evaluation limited to the models that contain many triangles? For instance, for grid graph generation, can the proposed method capture the graph generation quality well?

The primary advantage of our proposed methods is that they are simple and allow for directly controlling overlap. They can capture any kind of graph well in the sense that if there is no restriction on overlap/diversity, by setting $p=1$, they simply output the input graph and hence capture all of its statistics. When required to generate a diverse set of graphs, however, our clique-based methods may not be suitable for certain kinds of graphs like grid graphs. Clique-based graph generation in general is more suitable for graphs like social networks, which have strong community structure.

Thank you for the thoughtful review. We address the comments and critiques below.

Can you give more examples of recent generative models (e.g., GDSS, GraphARM, DiGress, etc.) that fit the proposed categorization?

Similarly to ERGMs, auto-regressive approaches (like GraphARM, and including diffusion models like DiGress) fall into the FD category of our hierarchy. Depending on the mapping function, flow-based models (like GraphAF) are likely to be FD as well.

The definitions for EI, FD, NI models are vague, and a more formal definition for categorization is needed. For instance, is the definition of FD model formal? It’s hard to understand what “the generative models allow for any possible distribution A” means.

We believe our definitions of the EI and NI model classes are formal and unambiguous, though we are open to any specific criticisms. Regarding the FD model definition, indeed, it may be more clear to rephrase as “Any categorical distribution $\mathcal{A}$ over adjacency matrices $\boldsymbol{A} \in \{0,1\}^{n \times n}$ of undirected graphs without self-loops is an FD graph generative model.” We hope this addresses any concern about ambiguity. The FD definition will necessarily be sparser than the others, since NI and EI are carefully-constructed subsets of FD.

A detailed explanation of the strength of using overlaps for graph generative models is missing. The authors emphasize that accuracy and diversity are key characteristics to evaluate the graph generative models but it’s hard to understand why overlap can be a good evaluation framework.

Overlap is perhaps the simplest characterization of the (lack of) diversity of graphs generated by a graph generative model - roughly, it is the fraction of edges shared between two sampled graphs, in expectation. A graph generative model having high overlap means that sampling from it tends to generate similar sets of edges, rather than a diverse pool of edges. Consequently, requiring low overlap is a simple way of preventing a graph generative model from achieving high accuracy (high fidelity to the input graph, e.g., in terms of a high triangle count) by simply outputting the same or a very similar set of edges as the input graph.

Lack of comparison to commonly used metrics such as MMD or V.U.N.

These metrics are not appropriate for the setting we test, which involves generation of a graph that is similar to a single input graph. Note that we test the same setting considered in the Variational Graph Auto-Encoder (Kipf and Welling, 2016) and NetGAN (Bojchevski et al., 2018; Rendsburg et al., 2020) papers, among others. By contrast, MMD is suitable for comparison of distributions of graphs, that is, a setting with multiple input graphs and multiple out graphs. VUN is also intended for such a setting, specifically for molecule generation.

Thank you for the thoughtful and positive review. We appreciate the recognition of our theoretical framework, triangle bounds, and proposed methods. We address your concerns below.

First, I am concerned about the cubic nature of the bounds. These seem to be very loose and it is hard to see how these can be used in practice, or even to provide insight about how to structure the generative process… What is the cost of a growing number of nodes to the technique proposed for bounding the number of triangles?

Indeed, the bounds for the triangle count in terms of node count and overlap are cubic in the node count. This is not entirely surprising: the total number of possible triangles is also cubic in the node count (specifically, it is $\binom{n}{3}$), and we are showing that a model’s overlap bounds the fraction of these triangles that can appear in expectation. Further, we provide examples demonstrating the tightness of our triangle count bounds. These examples show that there must necessarily be a term that is cubic in the node count, at least in the absence of further constraints. Under specific models, we may expect overlap to scale inversely with the number of nodes: for example, with Erdős–Rényi random graphs or related models such as stochastic block model graphs, assuming we fix the average number of friends (i.e., expected node degree), the overlap scales as $O(n^{-1})$. Thus, our bounds scale subcubicly in $n$.

Importantly, we note that the triangle bounds in terms of overlap and node count are not the tightest bounds that we provide. We also provide tighter bounds in terms of overlap and volume (i.e., expected number of edges) for EI and NI models - see the proof of Theorem 1 on page 6, prior to the application of Lemma 1. These overlap/volume bounds can be significantly tighter, but we apply Lemma 1 and convert them to the simpler overlap/node count bounds to highlight the conceptual differences between different levels of our proposed hierarchy, which is our focus.

something that could facilitate seeing the applicability of the bounds would be to see some synthetic verifications but no experiments show the application of the bounds to verify their veracity of them.

Thank you for the useful suggestion. As you point out, a simulation can corroborate the tightness of our bounds. In Appendix E, we have added a plot with a simulation that shows that the example models indeed achieve the tight bounds.

I think it is important to highlight the methodological complexity of using the bounds to achieve the target structure in the sampled graphs… the process of association probabilities to the locations within the graph (either adjacency matrix, locations, or edge lists) needs to be spelled out and better described.

The sampling of a graph with any of our proposed methods (MCEI, MCNI, and MCFD) involves sampling a primary graph $G_p$ and a residual graph $G_r$. Essentially all of the novel content of our methods — specifically 1) the use of max cliques, 2) the addition of edge dependency in the MCNI and MCFD models, and 3) the ability to easily control overlap — occurs in the sampling of $G_p$. We are able to compactly describe exactly how $G_p$ is sampled in Algorithm 1 due to the simplicity of this procedure. However, due to space constraints, we unfortunately have to appendicize Algorithm 2, which explains the sampling of $G_r$. In brief, Algorithm 2 samples a $G_r$ from a simple distribution such that the union of $G_r$ and $G_p$ (i.e., the union of their edge sets) matches the node degrees of the input graph in expectation.

To the extent that we can assign probabilities to entries of the sample’s adjacency matrix, we can say this: For any given pair of nodes $i$ and $j$, if $p_p$ and $p_r$ are the probabilities that the edge $(i,j)$ occurs in $G_p$ and $G_r$, respectively, then the probability that edge $(i,j)$ occurs in the final sample (the union of $G_p$ and $G_r$) is $1 - (1-p_p)(1-p_r)$. Note that this is just a marginal probability; in the case of MCNI and MCFD, there is dependency between the appearance of different edges.