Challenges of Generating Structurally Diverse Graphs
Authors: Fedor Velikonivtsev
Mikhail Mironov
Liudmila Prokhorenkova
Venue: NeurIPS 2024 poster (2024)
Keywords: diverse graphs
random graph model
graph generative model
graph distance
Primary area: graph_neural_networks
TL;DR: We formulate and investigate the problem of generating structurally diverse graphs that can serve as representative instances for various graph-related tasks.

Abstract: For many graph-related problems, it can be essential to have a set of structurally diverse graphs. For instance, such graphs can be used for testing graph algorithms or their neural approximations. However, to the best of our knowledge, the problem of generating structurally diverse graphs has not been explored in the literature. In this paper, we fill this gap. First, we discuss how to define diversity for a set of graphs, why this task is non-trivial, and how one can choose a proper diversity measure. Then, for a given diversity measure, we propose and compare several algorithms optimizing it: we consider approaches based on standard random graph models, local graph optimization, genetic algorithms, and neural generative models. We show that it is possible to significantly improve diversity over basic random graph generators. Additionally, our analysis of generated graphs allows us to better understand the properties of graph distances: depending on which diversity measure is used for optimization, the obtained graphs may possess very different structural properties which gives a better understanding of the graph distance underlying the diversity measure.

Challenges of Generating Structurally Diverse Graphs
Fedor Velikonivtsev HSE University, Yandex Research f fvel wellikonnyandee-team.
Mikhail Mironov
Yandex Research
mironov. m. wwkkkkmm.cc..m
Liudmila Prokhorenkova
Yandex Research
o
Abstract
For many graph-related problems, can be essential to have set of structurally diverse graphs. For instance, such graphs can be used for testing graph algorithms or their neural approximations. However, to the best our knowledge, the problem of generating structurally diverse graphs has not been explored in the literature. this paper, we fill this gap. First, we discuss how to define diversity for set of graphs, why this task is non-trivial, and how one can choose proper diversity measure. Then, for a given diversity measure, we propose and compare several algorithms optimizing it: consider approaches based standard random graph models, local graph optimization, genetic algorithms, and neural generative models. We show that is possible to significantly improve diversity graph generators. Additionally, our analysis of generated graphs allows us to better understand the properties of graph distances: depending is used for optimization, the obtained graphs may possess very different structural properties which gives better understanding of the graph distance underlying the diversity measure.
basic random
which diversity measure
Introduction
Figure 1: A sample of generated graphs
Many real-world objects can be naturally represented graphs: biological and chemical entities (atoms, molecules, proteins, metabolic maps), interaction networks (social and citation networks, financial transactions), road maps, epidemic spreads, and That is why the analysis of graph- structured data is an important and rapidly developing research area.
To generate realistic graph structures, many random graph models have been proposed in the liter- ature (Boccaletti et al. 2006). Such models aim to imitate properties typically observed in natural structures: power-law degree distribution, small diameter, community structure, and others. Each
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

random graph model captures some of these properties; thus, the generated graphs are inevitably similar in certain aspects.
On the other hand, for some applications, it is important to be able to generate a set of graphs that are structurally diverse. For instance, if one needs to automatically verify the correctness of graph algorithm, estimate how well heuristic algorithm approximates the true solution for graph problem, or evaluate neural approximations of graph algorithms (Veličković and Blundell 2021). In all these cases, algorithms and models should be tested on as diverse graph instances as possible since otherwise the results can be biased towards particular properties of the test set (Georgiev et al. 2023). In other words, we need representative graphs that 'cover' (in some sense) the space of all graphs. Datasets consisting of diverse graphs can also be useful for evaluating graph neural networks and their expressive power. In this direction, Palowitch et al. (2022) propose the Graph World benchmark that consists of graphs with various statistical properties. An important part of the benchmark is the relation between graph structure and node labels: graphs with different homophily levels can be constructed. However, generated graph structures are limited to the degree-correcter stochastic block model (Karrer and Newman 2011) and thus do not cover all complex connection patterns that graphs may have.
To the best of our knowledge, the problem of generating dataset where graphs are maximally diverse has not been addressed in the literature yet. In this paper, we fill this gap. For this purpose, we first need to define diversity of set of graphs which is already challenging task. To measure diversity, we define dissimilarity (distance) for pair of graphs and then aggregate the pairwise graph distances into the overall diversity measure. In this regard, we show that popular methods of measuring diversity have significant drawbacks and suggest using Energy since satisfies certain important desirable properties.
After we have defined a performance measure for our problem, several approaches can be used to optimize it. We develop and analyze the following strategies: a greedy method based on diverse random graph generators, local graph optimization approach, an adaptation of the genetic algorithm to our problem, and method based on neural generative modeling. For the simplest greedy algorithm, we provide theoretical guarantees on the diversity of the obtained set of graphs relative to the maximal achievable diversity (for a given pre-generated set of graphs to choose from).
We empirically investigate the proposed strategies and show that it is possible significantly improve the diversity of the generated graphs compared to basic random graph models. In addition to the numerical investigation of diversity measures, also analyze the distribution of graph structural characteristics and relations between them. Here we also observe significantly improved diversity. Moreover, since we consider diversity measures based on several graph distances, our results shed light on the properties of these graph distances. Indeed, depending on the function we optimize, the structural properties of the generated graphs can vary since graph distances focus on different aspects of graph dissimilarity. Thus, by inspecting the properties of generated graphs, one can better understand what graph characteristies particular graph distance is sensitive to.
In summary, this work formulates and investigates the problem of generating structurally diverse graphs that can serve representative instances for various graph-related tasks. Still, many challenges remain to be solved and we hope that our work will encourage further theoretical and practical research in this field.
2 Defining diversity for a set of graphs
2.1 Problem setup
As discussed above, for various graph-related problems, it can be essential to have representative graphs that are structurally diverse. Intuitively, such graphs are expected to cover (in some sense) the space of all graphs [] This section discusses how to define diversity and why it is non-trivial.
Let us start with a motivating example. The most basic random graph generator is the Erdös-Rény? model. In this model, an edge between any two nodes is added with probability p independently of other edges. If n is fixed and p = 0.5, then every simple graph on nodes can be generated equally
In this work, we use the terms 'diversity' and 'coverage" interchangeably.

---

likely (assuming that the nodes are enumerated), and thus one may think that this model generates representative graphs
However, it known that with high prob- ability graphs generated according the Erdós-Rényi model have typical properties and thus all very similar to each other with high probability (Erdós et al. 1960).
dustciin cocfficcn
For instance, as illustrated in Figure for the Erdös-Rényi model with p = 0.5 (ER- 0.5), the average node degree and average clustering coefficient are concentrated near (n 1)/2 and 0.5, respectively. Varying p (ER-mix) allows one to get all possible values of these characteristics, but they are linearly dependent in expectation. Thus, the space of all possible combinations characteristics cannot be covered by the Erdös-Rénn Rényi model.
ER-0.5 ER-mix
31
mode degree
Figure Average node degree and average clustering coefficient in the Erdös-Rényí model with n = 16 and p= 0.5 (ER-0.5) or varying p (ER-mix)
Intuitively, by diverse graphs we mean those having different structural properties such as degree distribution, pairwise distances, subgraph counts, and so on. However, this intuition hard to formalize one may potentially come up with infinitely many properties. On the other hand, defining graph dissimilarity is closely related to graph distances. Graph distances have been studied for long time, and many variants capturing different graph properties exist in the literature (Tantardini et al. 2019). We review some of them in Section 2.2
Now, assume that we have a multiset of N graphs S = GI,..., GN. Throughout the paper, we consider undirected graphs without self-loops and multiple edges. Assume that are also given distance measure D(G, G") that evaluates dissimilarity between two graphs. Then, we define diversity as:
Diversity(S) = F(ID(G, G') G, eS))
(I)
where F is some function that computes diversity given set of pairwise distances. The choice of F also non-trivial, and we discuss possible approaches Section 2.3
After we have defined the distance D(.,)) and the measure of diversity, our primary goal is to find multiset of graphs S of size N to maximize its diversity:
$
arg max Gr,Ga...GGEel,
Diversity((Gr GG.
where Gn the set of all graphs with n nodes
2.2 Graph distances
This section discusses how one can define distance between two graphs. As mentioned above, this task highly non-trivial, and the literature on this topic abundant (Tantardini al. 2019 Hartle
et al. 2020).
Some graph distance measures are based the optimal node matching between two graphs: first, the correspondence between nodes is found, and then some distance between two adjacency matrices can be computed popular example of this type is graph edit distance). However, this approach can only be applied to graphs having the same number of nodes (to achieve this in general case, one may add zero-degree nodes to the smaller graph). Also, finding the optimal matching between nodes is usually computationally expensive.
Another class of distance measures is based on computing some descriptor (vector representation) for a graph and then measuring the distance between two graph representations. Such measures usually violate the positivity axiom of metric space since the distance between two different graphs can be
For simplicity, we assume that the number of nodes n is the same for all graphs. Note that n can naturally be considered as an upper bound on the number of nodes: smaller graphs can be obtained if some of the nodes have zero degrees.
3

---

equal to zero. Indeed, if we guarantee that DIG, 0f and only if G and G' are isomorphic, then computing the distance is at least as hard as graph isomorphism testing, which infeasible for most applications. Thus, when computing a graph representation, we inevitably lose some information about the graph. Various approaches for creating graph descriptors exist in the literature. Some of them use the spectrum of the graph Laplacian (or its normalized variant) that is known to encode some important structural information (ipsen and Mikhailov 2002) Wilson et al. 2005 Tsitsulin et al. 2018). Other approaches are based on local statistics, such as graphlets (Yaveroglu et al. 2014). Each graph distance captures some properties of a graph and can be insensitive to others. We refer to comparative studies of graph distances (Tantardini et al., 2019; Hartle et al., 2020) for a more comprehensive list of known measures and the analysis of their properties. In more recent work, Thompson et al. (2022) suggested graph representations based on untrained random GNN. Such representations can also be used for computing graph distances.
Our paper does not aim to answer which graph distance is better. Each distance captures particular graph properties and the resulting set of generated diverse graphs may significantly depend on this choice. In our experiments, we consider several representative options. As result, our analysis of generated graphs gives some additional insights into the properties of graph distances.
2.3 Measuring diversity for a set of elements
In this section, discuss the problem of measuring diversity for a set of elements given their pairwise distances (or similarity values). This problem was addressed in several recent papers (Xie) al. 2023 FFiedman and Dieng, 2023) discussed in more detail in Appendix A.I However, as we show, none of the proposed approaches are fully suitable for our task.
Probably the most natural and widely-used measure for quantifying diversity is the average pairwise distance between the elements. However, we note that this measure is not suitable in our case since optimizing it may lead to degenerate configurations. For instance, consider toy experiment with dots distributed on a line segment. As shown in Figure 3a optimizing the average pairwise distance forces many points to collapse into one (at the endpoints of the line segment), which is clearly not desirable behavior. This happens since Average does not take into account whether the elements of a dataset are unique or well isolated from each other.
Another possible measure that does take uniqueness of elements into account is the minimum pairwise distance (often referred to Bottleneck in the literature). However, this measure is not sensitive to all the distances but the minimal one and thus cannot distinguish vastly different configurations.
Motivated by these examples, we formulate two properties that good diversity measure is expected to satisfy. We assume that we are given a multiset S of N elements and for each pair of elements G, G' E S we know the distance D(G, G') between them. Note that we are interested in maximizing diversity for a fixed number of elements N, which simplifies the requirements since we do not have to deal with how diversity changes when the number of elements increases.
Monotonicity Suppose we are given two multisets S, S' both consisting of N different elements and bijection g: S - S' between them. Assume that for any G,, S we have
D(G G3) < D(g(G.).
with strict inequality for least one pair j. Then we require Diversity(S) < Diversity(S").
This property describes the essence of diversity measures: larger pairwise distances should lead to higher diversity values. Thus, a good measure of diversity should be monotone.
Suppose S consists of N different elements GI...., GN. Denote by Sty the multiset obtained from S by removing G, and adding the second copy of G3 for j + i, that is Sig := (SMGG.) U }G₂} Then, we require Diversity(S) > Diversity(S:)).
Uniqueness
In other words, this property requires that given N - 1 elements, adding unique element results in higher diversity than duplicating an already existing element. This property is very intuitive since to increase the coverage it clearly better add new element than to duplicate an existing one.
Note that the average pairwise distance does not have the uniqueness property, thus optimizing may lead to degenerate solutions. Clearly, the minimum pairwise distance does not have monotonicity.

---

(a) Average
(b) Energy
Figure 3: Optimized Average or Energy on a line segment
Moreover, turns out that none the measures from (Xie et has both these properties, see Appendix A.2 for the details.
2023 Friedman and Dieng 2023
Thus, we propose an alternative diversity measure motivated by the energy of a system of equally charged particles. Namely, given a constant > 0, we define the Energy of set of graphs S as
1
Σ (F)
N(N
The parameter y affects how strongly penalize small pairwise distances. In extreme case of + oC. this measure becomes equivalent to Bottleneck. All our theoretical results hold for any use 7 1, (4) can be naturally interpreted as the average pairwise energy for a system of equally charged particles (we multiply by to get a measure that is larger for more diverse sets of graphs).
0 For experiments,
Our toy example in Figure[3bJshan that when being optimized Energy leads diverse configuration, in contrast to Average. Regarding
formal properties, monotonicity is obviously satisfied by Energy (4). show uniqueness, we note that any multiset with pairwise different elements has some finite negative diversity and any multiset with two copies of one element has diversity -00.
Proposition 2.1. Energy satisfies both monotonicity and uniqueness.
Despite having these desirable properties, Energy still has shorteoming: it can be unboundedly large when two elements become too close to each other. However, there are currently no better alternatives. as shown in recent paper by Mironov and Prokhorenkova (2024) that extends the analysis of diversity measures in terms of the desirable properties they satisfy. We refer to Appendix [A.4 for discussion. In our experiments, primary measure of diversity and also consider Average as an additional measure.
use Energy (combined with several graph distances) as our
3 Algorithms for diversity optimization
In the previous section, we discussed how to measure diversity and why this task is non-trivial. In this section, we propose several approaches for diversity optimization. Our goal investigate diverse algorithms: from a basic approach based on random graph generators to a more advanced one based on neural generative modeling.
Our algorithms can be applied to arbitrary diversity measures. However, for scalability purposes, restrict ourselves measures that can be written in the following way. Suppose set of size N and any element G from this set. Denote the subset of all elements excluding G' by (G1, G2 .2..... GN-1). Then, the diversity of the original can be written as:
given
(5) where g is function that is monotone w.r.t. both arguments, S(G depends only the dis- tances (D(G, Ga) G; E S), and c(S) is a value that depends only on S (and does not de- pend G). We call such function f(G,S) fitness of graph G w.r.t.
Diversity U S) (()
of graphs S. The measures considered this study satisfy (5) For instance, for Energy, can be the sum, f(G,S) MV-11/3 E D(G.G.)7 and c(S) NNN-172 E DIG.,G,JJ For Bottleneck, g can be the minimum, f(G,S)= = min D(G, G.), and c(S) = min D(G,, Gy). Note that computing the *<
G,ES
fitness f(G. requires N distance computations.
We illustrate the effect of the obtained diverse configurations in Appendix A.3

---

It is important to note that standard machine learning approaches cannot be directly applied to our task: usually, generative algorithms require a training set that they try to imitate. In our case, there is no training set since the aim is to generate graphs that are maximally dissimilar to each other.
3.1 Greedy algorithm
The main idea of this algorithm is build set of diverse graphs iteratively by adding each step the most suitable graph from a predefined set S of much larger size. This can be either user input, the result of another algorithm, or a set of graphs generated by random graph models. The process initiates by randomly choosing graph from S. At each step, the most suitable graph from $ chosen according to the fitness S), where S the currently selected set of graphs.
detailed description of the algorithm is given in Appendix C.T We also provide the analysis of computational complexity and lower bound on the diversity of graphs returned by the greedy algorithm relative the diversity of the initial set 3 (see Theorem
3.2
Genetic algorithm
The genetic algorithm enhances the diversity of a graph population through evolutionary operations. Starting with an initial set of N graphs, it iteratively refines this set by selecting pairs of graphs as parents and generating a child through crossover and mutation processes. This child can replace the less-fit graph in the population if it increases the overall diversity; otherwise, the algorithm tries find a more suitable offspring by repeating the process. To prevent itself from getting stuck in local optima, the algorithm can accept candidate that decreases the overall diversity if the number of unsuccessful attempts exceeds a certain threshold. The algorithm iterates for a predefined number of iterations, ultimately evolving the population towards greater diversity. This approach adapts principles from genetics to solve optimization problems, as we try to preserve beneficial graph characteristics while the same time introducing novel configurations achieve diverse set of graphs.
The details of this algorithm are given in Section C.3 where we also analyze the complexity of the algorithm.
3.3 Local optimization algorithm
The main idea of the local optimization algorithm is the refinement of the diversity of a graph population by iteratively modifying individual graphs. Starting from initial set, we randomly sample graphs and make small modifications to their structure (single edge addition/delltion) Then, if the overall diversity improves, we accept the change. As in the other algorithms, we can accept less fit modifications after consecutive failed attempts to prevent stagnation at a local optimum.
The details of this algorithm are given in Section C.4 where we also analyze its computational complexity. Since local optimization makes small modifications at each step, this approach is expected to be most efficient when the input set of graphs is already sufficiently diverse. Thus, when we combine several algorithms, local optimization is always the last step.
3.4 Iterative graph generative modeling
Neural generative models are known to be a powerful tool for generating graphs that imitate a given distribution (You et al. 2018 Martinkus et al. 2022; Vignac et al. (023). Hence, we aimed to investigate whether such approaches can be used for generating graphs that are structurally diverse. In this case, there is no predefined distribution that needs to be captured. We address this via the following iterative procedure. The process starts from an initial graph set So and then iteratively enhances the diversity. At each iteration, the current set of graphs S, is used train a generative model. Then, this model is used to generate significantly larger set of new graphs. From this new set, a smaller subset of diverse graphs S1+1 selected via the greedy approach. We expect that S is more diverse than S,. So, we repeat the process by training neural generative model on the new set S441- For the neural network architecture, we use Discrete Denoising Diffusion Model (DiGress) (Vignac al. 2023). We refer to Appendix C.5 for detailed description of our approach.

---

4 Experiments
In this section, we analyze and compare the algorithms for generating diverse graphs described above. Then, we analyze generated graphs and discuss how the choice of a particular graph distance affects the structures of the obtained graphs.
Setup In our experiments. we consider four representative distance measures: heat and wave NetLSD (Tsitsulin et al., 2018). Graphlet Correlation Distance (Yaveroğlu et al. (014)) and Portrait Divergence (Bagrow and Bolli 2019). We select these distances be diverse: NetLSD is based on the Laplacian eigenvalues (we use SID-hhat and SSD--Waawwae variants), Graphlet Correlation Distance (GCD) uses local structures, while Portrait Divergence (Portrait-div) takes into account both local and global properties. A detailed description of these measures is given in Appendix B
Following Section 2.3 we choose Energy the diversity measure. Formally, we optimize and report the following measure:
1
Σ
N(N
D(G., GJG,,G,)+ GE) (F
where e is a small constant added for numerical stability, As soon as we fix the diversity measure that we rely on, the goal of each algorithm is to optimize this measure. In other words, in contrast to standard machine learning problems, we do not face the problem of overfitting.
We evaluate the following approaches described in Section 3 Greedy, Genetic, local optimization (LocalOpt), and iterative graph generative modeling (IGGM). Our evaluation also includes the comparisons against simple baseline models, specifically the Erdōs-Rényi graphs sampled with various p (ER-mix) and a sample from diverse random graph generators described in Section C.2 As an additional illustration, we also include sample of graphs generated by the Graph World benchmark (Palowitch et al. 2022). where we vary the model parameters to increase diversity of the obtained graphs. In most of the experiments, we generate N = 100 graphs with 16 nodes. We also conduct experiments with non-ncural algorithms on the set of 100 graphs with size n = 64.
Let us note that the algorithms introduced in Section can be easily combined: the output of one algorithm can serve as an input to another. Thus, we evaluate the combinations of the algorithms. We use the notation "-² to denote the transition between the consecutive algorithms. Note that Greedy the only strategy that does not generate any new graphs. Hence, its initial set should be already sufficiently diverse. Thus, we use graphs generated by diverse random graph models described in Section
We assume that for most algorithms, the most time-consuming operation is computing a graph representation (that used for distance computations). Therefore, all algorithms except IGGM use the total limit of 3M generated graphs. For IGGM, the number of generated graphs is limited to 1M since training the graph generative model is time-consuming. In the tables, we use the square brackets to denote the number of computed graph representations for an algorithm or sub-algorithm.
Numerical comparison In this section, we numerically analyze how well different approaches optimize the chosen diversity measure. [ the results for selected algorithms and baselines. For more algorithms, please refer to Table
4 in Appendix, where we also report the standard deviation.
First, we note that all the proposed algorithms significantly improve the performance of the basic algorithms ER-mix and Random Graph Generators. Similarly, the diversity of Graph World is far from optimal. This is not surprising since GraphWorka does not directly optimize the diversity of graph structures and relies on the relatively simple stochastic block model.
Among the non-neural algorithms, the best performance achieved by a combination of Greedy, Genetic, and LocalOpt (applied in this order). Such combination is natural: Greedy starting from a set generated by different random graph generators is the simplest way to get an initial diverse set of graphs. Then, Genetic uses enough randomness to create all kinds of graph patterns to choose from. After that, LocalOpt is used to make final tuning with small graph modifications. neural-network-basee method IGGM gives significant boost in diversity for GCD and Portrait-div distances and exhibits comparative results for NetL.SI DeD-.SDhheat Note that uses less budget for generated graphs but also requires training graph generative neural model several times.
turn, the
7

---

Table I: Energy optimization results; Table 4 in Appendix for the extended results
Setup
GCD
Portrait-div
NetLSD-heaa
NetL.SDwave
ER-mix
0.281
43.057
72.387
0,583
GraphWorld
0,466
3.917
5.108
0.621
Random Graph Generators
0.553
6.009
116.685
1.334
[reedy[3M]
0.156
1.274
0.681
0.123
ER-mix-beee
0.139
1.264
0.677
0.117
Greedy[M]]--eenetic(222
0.139
1.263
0.674
0.118
ER-mix
0.138
1.259
0.675
0.117
(rreddy||MM-LLLoc00002222
0.139
1,255
0.679
0.118
0.135
1.245
0.673
0.117
IGGM[IM]
0.120
1.213
0.675
0.148
Table 2: Diversity measured by Average; the graphs the same as in Table 1
Setup
GCD
Portrait-div
NetLSD-heat
NeiLSD-wave
ER-mix
4.350
0.607
0.936
6.302
GraphWorld
2.510
0.317
1.270
2.784
Random Graph Generators
2.059
0.212
0.025
1.190
Greedy[3M]
6.901
0.819
3.067
10.099
ER-mix (GneetiGGee
7.553
0.830
3.056
10.625
Greedy(LM]]--GGeeet(((2MMM
7.614
0.826
3.072
10.549
ER ER-mix [
7.734
0.831
3,056
10.621
Greedy [MoLL
7.494
0.830
3.051
10.485
Greedy| MM] - Genetic[1M] LocalOpt[IM]
7.835
0.836
3.073
10.485
[GGM[ [M]
8.687
0.854
3.066
10.364
Let us note that the basic algorithms in [ the line) are not designed to optimize Energy and thus may accidentally generate pairs of graphs that are very close to each other, leading to significantly worse diversity. Hence, as an additional illustration of our results, we also report the average pairwise distance for the same sets of graphs. The results are shown in Table 2 and they consistent with Table
and
We also conducted additional experiments on larger graphs with = 64 nodes. The results are shown Table 5 Appendix, and they are consistent with the results on smaller graphs.
Examples of generated graphs Since in our main experiments we generated 100 graphs, each having only 16 nodes, possible to visually inspect the generated graphs. To show that the generated graphs have very different structural patterns, we show some examples in Figure This sample of graphs chosen from the resulting set of the Genetic algorithm with diversity based on Portrait-div. It is clear that graphs vary in density, internal structure, number of cycles, and planarity. Importantly, these graphs are clearly distinct from the input distribution ER-mix. More examples showing all generated graphs shown in Figures 7 We see that when combined with Portrait-div, both Genetic and IGGM generate visually diverse and interesting structures. One can also notice that NetLSD tends to generate many extremely sparse graphs, while GCD generates more dense graphs.
Analysis structural characteristics Additionally, we analyze the structural characteristics of generated graphs. Figure visualizes various characteristics for the ER-mix baseline, IGGM, and the combination of Greedy, Genetic, and LocalOpt. Obtaining a set of graphs in which an individual characteristic is diverse is easy: this can be achieved with the basic ER-mix. Hence, we visualize the joint distributions of pairs of characteristics.
It is clearly seen that compared to ER-mix, our algorithms lead to significantly more diverse pairs of characteristics. Also, it worth mentioning that we often should not expect to cover all possible combinations: for instance, if the average degree is close to its maximal achievable value - 1, then the clustering coefficient has to close to For more algorithms and combinations of characteristics, please refer to Figure 12 in Appendix.

---

ER-mix Greedy(1M] Genetic[IM) >> LocalOst[1M)
IGGM
Portrait
heat
Avg. clusterine coeftiient
Avg. node degroe
node digroee
node degree
Avg. clusterina coetriiin
Efficiency
Efficiency
Efficiency
Figure Joint distribution of graph characteristics for GCD, Portrait-div, NetLSDDheat
GCD
Portrait-div
NethSD-heat
Avg. clustering coeff.
Avg. node degree
0.8
0.8
Avg. clustering
10
0.6
0.4
0.2
0.2
10
15
0.5
0.5
Avg. node degree
Efficiency
Efficiency
Figure 5: Joint distribution of graph characteristics for graphs from IGGM: comparing graph distances
Comparing graph distances Visualizing pairwise graph characteristies can help in the analysis and comparison of different graph distances. Indeed, the generated graphs significantly depend on a particular graph distance used for computing diversity. We visualize this in Figure [ One observation that we make that NetLSD is significantly biased towards sparse graphs (for clarity, Figure 5 shows the results for NetL-SD-hee of the generated graphs, the clustering coefficient is zero. Similarly, the average degree is usually small. However, despite this, the remaining NetLSD graphs may cover diverse combinations of characteristics. The fact that NetLSD is biased towards sparse graphs can also be seen in Figures 9 10 where we visualize the generated graphs. Then, Figure 5 shows the differences between GCD and Portrait-div. For instance, Portrait-div is significantly more diverse in terms of efficiency. This is natural, taking into account that GCD is based on local structures, while Portrait-dee accounts for global characteristics.
but the wave variant has the same patterns). Indeed, for most
Conclusion
In this work, we formulate the problem of generating structurally diverse graphs that can serve as representative instances for various graph-related tasks. We show that the problem is challenging as it is non-trivial to define what it means for a graphs be diverse. In this regard, we propose desirable properties that good diversity measure is expected to satisfy and choose a diversity measure based on them. Then, we show that random graph models do not provide sufficient diversity and propose various alternative approaches. Importantly, all the proposed algorithms can be applied to arbitrary diversity measures. Via a series of experiments, we show that the proposed approaches are capable of generating diverse graphs, both in terms of diversity measures and structural characteristics.

---

In this work, we have only made first step to analyzing the problem of generating diverse graphs. There are plenty of promising directions for future research, and we hope that our work will encourage researchers to dive deeper into this problem. One particularly important challenge is scalability. If the number of nodes becomes large, then the number of possible graphs grows very fast, and for some methods (e.g., LocalOpt that uses single edge modifications) covering the whole space may become infeasible. Secondly, we believe that more advanced algorithms will be developed in the future. Also, further discussions on how to measure diversity and how to choose proper graph distance seem to be very useful. Finally, it would be great to see practical applications of diverse graphs.
References
J. P. Bagrow and E. M. Bollt. An information-theorrtiic, all-scales approach to comparing networks. Applied Network Science, 4(1), 2019.
J. P. Bagrow, E. M. Bollt, J. D. Skufca, and D. Ben-Avraham. Portraits of complex networks. Europhysics Letters, 81(6):88044 2008.
A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439): 509-512, 1999.
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang. Complex networks: Structure and dynamics. Physics Reports, 424(4-5):175-308 2006.
Chung and Lu. Connected components random graphs with given expected degree sequences. Annals of Combinatorics, 6(2): 2002.
Erdös, A. Rényi, et al. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5(1):17-60, 1960.
D. Friedman and A. B. Dieng. The Vendi score: A diversity evaluation metric for machine learning. Transactions Machine Learning Research, 2023.
D. G. Georgiev, P. Lio, J. Bachurski, J. Chen, T. Shi, and L. Giusti. Beyond Grdös-Rényi: Gener- alization in algorithmic reasoning on graphs. In The Second Learning on Graphs Conference, 2023.
H. Hartle, B. Klein, S. McCabe, A. Daniels, G. St-Onge, C. Murphy, and L. Hubert-Dufresne. Network comparison and the within-ensemble graph distance. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 476(2243):01907444, 2020.
P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 137, 1983.
Holme and B. J. Kim. Growing scale-free networks with tunable clustering. Physical review E, 65 (2):026107, 2002.
M. Ipsen and A. Mikhailov. Evolutionary reconstruction of networks. Physical Review E, 66(4): 046109, 2002.
B. Karrer and M. E. Newman. Stochastic blockmodels and community structure networks. Physical review E, 83(1):016107, 10
K. Martinkus, A. Loukas, N. Perraudin, and R. Wattenhofer. SPECTRE: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators, 2022.
M. Mironov and L. Prokhorenkova. Measuring diversity: Axioms and challenges. arXiv preprint arXiv:2410.14556. 2024.
L. Ostroumova, A. Ryabchenko, and E. Samosvat. Generalized preferential attachment: tunable power-law degree distribution and clustering coefficient. In Algorithms and Models for the Web Graph: 10th International Workshop, WAW 2013, pages 185-202. Springer, 2013.
10

---

J. Palowitch, A. Tsitsulin, B. Mayer, and B. Perozzi. GraphWorld: Fake graphs bring real insights for gnns. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages
M. Penrose. Random geometric graphs. Oxford University Press, 2003.
M. Tantardini, F. leva, L. Tajoli, and C. Piccardi. Comparing methods for comparing networks. Scientific Reports, 9(1):1-19, 2019.
R. Thompson, B. Knyazev, E. Ghalebi, J. Kim, and G. W. Taylor. On evaluation metrics for graph generative models. In International Conference on Learning Representations, 2022.
A. Tsitsulin, Mottin, P. Karras, A. Bronstein, and E. Müller. NetLSD: hearing the shape of graph In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2347-2356, 2018.
Veličković and C. Blundell. Neural algorithmic reasoning. Patterns, 2(7):100273, 2021.
C. Vignac, I. Krawezuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard. Digress: Discrete denoising diffusion for graph generation. In The Eleventh International Conference Learning Representations, 2023.
R. C. Wilson, E. R. Hancock, and B. Luo. Pattern vectors from algebraic graph theory. IEEE transactions on pattern analysis and machine intelligence, 112711112-1124, 2005.
Y. Xie, Z. Xu, Ma, and Q. Mei. How much space has been explored? Measuring the chemical space covered by databases and machine-generater molecules. In The Eleventh International Conference on Learning Representations, 2023.
Ó. N. Yaveroglu, N. Malod-Dognin, D. Davis, Z. Levnajie, Janjic, R. Karapandza, A. Stojmirovic, and N. Pržulj. Revealing the hidden language of complex networks. Scientific Reports, 4:4547, 2014.
J. You, R. Ying, X. Ren, W. Hamilton, and J. Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In International conference machine learning, pages 5708-5717. PMLR, 2018.

---

A Measuring diversity of a set of elements
A.1 Related work on diversity measures
The concept of diversity is useful for various applications such as image and molecule generation or recommender systems. Diversity can be used to evaluate how representative a given dataset, how diverse is a generated set, or for choosing a representative subset from a dataset (diversity sampling). In this section, we discuss relevant studies on measuring diversity.
recent paper by Friedmman and Dieng (2023) suggests measuring diversity via the Vendi Score (VS). This score requires kernel function defined pairs of elements. Then, similarity matrix consisting of the pairwise kernel values is constructed and the Vendi Score is defined as the exponential of the Shannon entropy of the eigenvalues of the normalized similarity matrix.
Another recent work (Xie et al. 2023) investigates the problem of measuring the coverage (diversity) of set S in the context of molecular generation. The authors consider the following known measures: the average, maximum, and minimum pairwise distances. Xie et al. (2023) propose three axioms that good measure of coverage is expected to satisfy: monotonicity, subadditivity, and dissimilarity, Then, they show that none the abovementioned measures satisfy all three axioms simultaneously and propose new coverage measure called #Circles. #Circles equals the maximum number of disjoint circles with centers placed at the elements of the set. However, while satisfying all the properties, this measure has two disadvantages. First, the complexity of calculating this measure exponential. Second, it requires the radius parameter to be defined and a good value depends on dataset. In our setup when the set of graphs dynamically changes during the optimization, this measure cannot be applied.
Let discuss how the properties from Xie et al. (2023) relate our study. Monotonicity and subadditivity describe the behavior of a measure when the size of the set increases and thus are not relevant in our setup. Hence, only the dissimilarity axiom remains. This axiom requires that the diversity of a pair of elements monotonically increases one of them moves apart from the other. Our monotonicity property generalizes this axiom.
A.2 Properties of popular measures
In this section, we revisit existing measures of diversity and show that typically used ones do not satisfy our requirements.
Table 3 lists diversity measures
Table 3: Some known diversity measures
discussed in previous studies (Xie
et al. 2023 Friedman and Dieng 2023). Here we assume that S [G1.....ry, G... There are six well- known diversity measures defined over pairwise distances (Average, Di- ameter, and Bottleneck with two types of aggregation). Then, #Circles the measure proposed in Xie et al. (2023) that also depends on the pairwise dis- tances. Finally, Vendi Score is pro- posed in Friedmma and Dieng (2023) and it is defined in terms of the pair- wise kernels. We give the complete definition of Vendi Score below.
Measure
Formula
Average
Σ G,).. E4S
M(N
SumAverage
Σ DIG., Gj)
(j
Diameter
max D(G., Gg)
SumDiameter
Σ max D(G,, Gj) iti
Bottleneck
min D(G., Gj)
(f)
SumBottleneck
Σ min D(G,, G2)
jts
#Circles(!), 2
mAx (E(N)
[C] s.t. D(G;, (Vi+jeC
Vendi Score
log(AA)
Theorem A.1. Among the previously used measures listed in Table monotonicity is satisfied only by Average and SunAverage, while Uniqueness is satisfied only by Bottleneck.
Proof. For each measure, check whether it satisfies monotonicity and uniqueness defined in Section 2
Average
2 NIN-J
Σ D(G.,, Gz) i4)
12

---

The monotonicity property is obviously satisfied.
We prove that uniqueness is not satisfied by the following example. Consider multiset consisting of
four different values: {0, 10, 11, 12). The distances hetween the values are induced from the real line.
The diversity of this set 2 (10 + 11 12 ++++++1 37 If we replace 10 by the second copy of
4-3
O, we get multiset {0, 0, 11, 12) with larger value of diversity 1.3 (0+ 11 12 11 12+ 11
SumAverage
D G,)
Since SumAverage equals Average multiplied by N, their properties are similar: monotonicity is obviously satisfied for SumAverge and the same example gives the contradiction for uniqueness.
Diameter max G,) (F)
We prove that monotonicity is not satisfied by the following example. Consider one multiset with three elements and pairwise distances 10, and another multiset with tree elements and pairwise distances 10, 7, 5. Monotonicity requires the second set to have larger diversity, but the diversity of both sets is equal 10.
To show that uniqueness not satisfied, we consider the following example. Take multiset consisting of three different elements: {0, 1, 2}. The distances between the elements are induced from the real line. The diversity of this set 2. If we replace 1 with the second copy of O, we get a multiset {0, 0, with the same diversity 2.
SumDiameter
max D(G;, Gÿ) jt
We prove that monotonicity is not satisfied by the following example. Consider one multiset with three elements and pairwise distances 10, 7, and another multiset with tree elements and pairwise distances 10, 7, Monotonicity requires the second set to have larger diversity, but the diversity of both sets is equal 10 + 10 + 7 27.
We prove that uniqueness not satisfied by the following example. Consider multiset consisting of three different elements: {0, 1, 2). The distances between the elements are induced from the real line. The diversity this set is + 2
5. If we replace with the second copy of we get a multiset {0, 0, 2) with larger diversity 2 2 2 2 6.
Bottleneck
min D(G,, G₃) (F)
To show that monotonicity is violated, consider multiset consisting of three different elements: {0, 1, 1,.). The distances between the elements are induced from the real line. The diversity of this set is 1. Monotonicity requires the set (0, 1, have larger diversity. But the diversity of the set {0, 1,6) is also equal to
Uniqueness is satisfied. Indeed, any multiset with pairwise different elements has diversity greater than 0, and any multiset with two copies one element has diversity 0.
SumBottleneck
min D(G,,G)) jfz
To show that monotonicity is violated, consider a multiset consisting of four different elements: {0, 1, 5, 63. The distances between the elements are induced from the real line. The diversity of this set 1 1+1 1 + 1 1 = 4. Monotonicity requires the set {0, 1,7,8) 8} to have larger diversity. But the diversity of the set {0, 1, 7, 8} is also equal to + +1++1 1+11=111
We prove that uniqueness is not satisfied by the following example. Consider multiset consisting of
four different elements: {0, 1, 9, 10). The distances between the elements are induced from the real line. The diversity of this set is 1 + 1 + 1 = 4. If we replace with the second copy of 9, we get a multiset {0, 9, 9, 103 with larger diversity 9 +0+0++=10 10.
#Circles(t)
max CI s.t. D G.) xVi CC[N
13

---

We prove that monotonicity is not satisfied by the following example. Consider one multiset with three elements and pairwise distances 10, 7, and another multiset with tree elements and pairwise distances 10, 8, 4. Monotonicity requires the second set to have larger diversity, but: for /. < 4 the diversity of both sets is equal to 3; for I < 10 the diversity both sets is equal to 2; for S the diversity of both sets is equal to 1.
Now, we fix & and prove that uniqueness
satisfied by the following example. Consider multiset
consisting of three different elements: {0, Š. (). The distances between the elements are induced from the real line. The diversity of this set is 2. If we replace by the second copy of 0, we get multiset (0, 0, 1) with the same diversity 2.
Vendi Score
exp
Σ A log((;))
First, let us give formal definition of this measure.
Definition A.2 (Vendi Score, Friedman and Dieng 2023 Let (G,,..., GN3 be multiset and let k: 5 x 5 > IR be a similarity function, such that Vi: : kGG,, = and the matrix K E N defined by KJ, == k(G,, G3) sesitie--emideffiiie and symmetric. Denote by A1.... the cigenvalues of the matrix K/N, Then, the Vendi Score is defined as the exponential of the Shannon entropy the eigenvalues of K/N:
X logo(A))
exp
(6)
where we use the convention 0 Olog 0 = 0.
Our monotonicity property distances instead of similarities, but naturally reformulate in terms of pairwise similarities by replacing the condition D(G,, G₁) S ((g(G.),g(G)) with the condition k(G Gy) 2 k(g (G,). (G;))) Our uniqueness does not use the notion of distance, can use it as is. Thus, we can check whether the Vendi Score satisfies monotonicity and uniqueness.
We prove that monotonicity is not satisfied with the following example. Consider two positive- semidefinite symmetric matrices:
0.1
0.8
0.2
0.8
K1
0.1
1
0.4
K₂
0.2
0.4
0.8
0.4
0.8
0.4
1
Monotonicity requires K1 to have higher diversity than K2. But Vendi Score of K1 is 2.203 and Vendi Score of K2 is 2.212 2.203.
To show that uniqueness is not satisfied, consider the following example. semidefinite symmetric matrices:
Take two positive-
0.6
0.2
1
0.2
Ki
0.6
1
0.9
K₂
0.2
(8)
0.2
0.9
1
0.2
0.2
If Vendi Score has uniqueness property, then Ki must have higher diversity than K2. But the Vendi Score of K, is 1.81 and Vendi Score of K2 is 1.86
1.81.
A.3 Illustrating the effect of the Energy parameter
To illustrate the effect of 7 let us consider simple setup when points are distributed in square. We place 50 points uniformly at random in a unit square and optimize Energy for = 0.1, 0.3, 0.5, 3, 10. The results are shown in Figure 6 Clearly, for small the cover- age of the non-boundary region is not sufficient. However, for larger values (including = 1) the distribution looks sufficiently diverse.
14

---

(a) 7 = 0.1
(b) 7 = 0.3
( = 0.5
(d) y
(e) y =
(g)==
10
Figure The effect of the Energy parameter y for points distributed in a square
A.4 Unboundedness of Energy
When two elements of a set get closer to each other, Energy can become arbitrarily large. Such behavior
some interpretability problems when compare the obtained Energy for different algorithms. terms of the desirable properties, the issue is that both monotonicity and uniqueness can be violated if not all elements different. However, it turns that if one requires monotonicity and uniqueness to be satisfied even when some elements coincide, then it becomes very challenging construct measure satisfying all the desirable properties. This problem was recently addressed by Mironov and Prokhorenkova (2024) who require monotonicity and uniqueness to be satisfied for all the initial configurations and also add an important property of continuity. The authors construct two examples of measures satisfying all the properties, but both of them are NP-hard to compute and thus are infeasible to use practice. Whether there exists a computationally feasible measure satisfying all the properties is currently unknown.
Thus, have chosen Energy the best option available. The advantage of Energy is that when it is optimized, the obtained distribution is indeed diverse (see, e.g., Figure (6). In other words, Energy can be degenerate for configuration that not sufficiently diverse, but it can be used to compare algorithms that optimize diversity. Also, recall that for numerical stability, we add small constant to the denominator of Energy, it does go infinity in practice.
Importantly, for the completeness of our study, in Table 2 we report the average pairwise distance. As discussed above, this measure cannot be used can lead to degenerate solutions. That why we only use it as an assistive measure and apply it to the sets of graphs obtained by optimizing other objectives.
function that is optimized by algorithm since
B Considered graph distances
In this section, we describe the graph distances that we use in our experiments.
NetLSD (Tsitsulin et al. 2018 NetLSD treats graph dynamic system and simulates heat and wave diffusion processes on nodes and edges of a given graph, followed by measuring system conditions fixed timestamps. More formally, A; be the j-th smallest eigenvalue of the normalized Laplacian of graph G. For a timestamp 1, we define heat trace h4 and wave trace of a graph G as follows:
he Σ
Wt Σ ttj
15

---

Here t >> O for the heat trace and f E [ for the wave trace.
Then, the heal trace signature and wave trace signature of G are defined the collections of the corresponding traces at different timestamps, i.e., h(G) = (he HET, and w(G) = {wI)eTT, As in the original article, cqually-spaced timestamps between 0 and 2 for Tw. respectively.
250 log-spaced timestamps between 10-2 and 102 for Th and 250
Finally, the NetLSD distance (heat wave) between two graphs G' and G' is computed any distance measure between the corresponding signatures. Following Tsitsulin et al. (2018), we use the Euclidean distance.
Graphlet Correlation Distance (GCD) YYaeeroguu et al., 2014) Graphlet Correlation Distance computes the distance between two graphs based on their graphlet statistics. Here graphlets defined as connected graphs with 2, 3, or 4 nodes, with one them marked. There are exactly 15 such graphs.
Consider any graph with n nodes. Choose any node v E G and any graphlet R. We count the number of subgraphs in G' which are isomorphic to R, such that the marked node of R coincides with v. Doing this for fixed y and all graphlets, we get numbers corresponding to v. These numbers not independent: if we know the counts for some graphlets, we can find the counts for some other graphlets. Getting rid of redundant counts, we are left with values (and the corresponding graphlets). So now have a vector of length 11 for each node of G. We combine these vectors in a matrix L with n rows and 11 columns. Using this matrix L. we compute 11 x 11 Graphler Correlation Matrix (GCM) as follows. The cell (i,j) of GCM contains Spearman's 's correlation coefficient between i-th and j-th columns of the matrix L. In other words, this cell contains the corrllation between the number of times node is part of the i-th graphlet and the number of times the same node is a part of the j-th graphlet.
The graphlet correlation distance between two graphs G and G' is then computed as the Euclidean distance between the upper-triangular parts of their GCMs:
GG)
Σ
(GCMo(i, GCMo
(10)
ISKKJs1
Portrait Divergence (Bagrow and Bollt 2019) The network portrait (Bagrow et al.) 2008 of graph G is a matrix B with elements big being the number of such nodes v that there are exactly nodes at distance from v. This matrix captures both local and global graph statistics. Based on the portrait B, one can compute the joint probability of choosing a pair nodes at distance from each other and that the first node has A nodes at distance I from it:
k'bu
bik E.
PB(K, P(H))(())
(11)
v
n
where E. n is the normalization over the sizes n. of the connected components. Then, the portrait divergence between two graphs G and G' is computed the distributions (k. and (R(a))(k,))
divergence of the
C Algorithms for diversity optimization
In this section, we give more details on the algorithms that we use for diversity optimization. Recall that our algorithms assume that the overall diversity of a set of graphs {G} U S can be written as Diversity U.S) S), The function SG is called fitness of graph G w.r.t. set of graphs S.
where is function that is monotone w.r.t. its arguments.
The code of experiments is publicly available at https:// htt.:atthhh..oo/uuuaaa..////// oygpg//ee.....aa.oooooooe.oaaaae graphss
C.1 Greedy algorithm
Algorithm Assume that we are given a pre-generated set Š of M graphs with diverse structural properties, M > N. Let S be constructed set of diverse graphs which is initially an empty set.
16

---

Then, our greedy algorithm consists of N steps. We start with S = @ and at the first step we select graph from the set S uniformly at random to be the first element in S. At each subsequent step, we choose G' E S with the maximal value of the fitness f(G, Then, we add this graph G' to the set S. After steps, we get a set S of size N, which is our approximation of the maximally diverse set.
Analysis While heing very simple, the greedy algorithm turns out to be very effective when supplied with a sufficiently diverse set S. The following theorem provides the bounds on diversity. While in this paper we focus on the Energy diversity measure, we also provide the results for Average and Bottleneck measures.
Theorem C.I. Assume that the diversity is Energy, Average, Bottleneck. Let S be a set of graphs. If the greedy algorithm selected subset S from S, then
Diversity (S) 2 Diversity (S) for Average and Minimum,
Diversity (S) 2 2 Diversity (5) for Energy(7); where S is the maximally diverse subset of S satisfying |S| |S| N.
Proof. Let us prove the statement for each of the diversity measures.
Average Suppose max D(Gi, G2) d and this maximum is achieved for Gi = V1, G2 = V/2 Gr.GZES
for some V1, 1/2 S.
Since all pairwise distances between the elements of C S are less than or equal to d. the average pairwise distance between the elements of S is also less than equal to d. That is, Diversity($) s d. Therefore, to prove the theorem is sufficient to prove that for the greedily picked S we have Diversity(S) 2 5. We prove it by induction on N, which the size of the set S. The base case N = 2 is trivial since for every element there exists second element at distance more than or equal to d 2 (by the triangle inequality, one of the ends of any diameter can serve as such element).
Inductive step. Suppose the induction statement holds for N k. Let prove it for N k 1. Suppose the greedy algorithm picked graphs AI...., Ag, Ag+1 in this order. We need to prove that the average pairwise distance between AI,..., Av: 1 is at least 5. By induction hypothesis, the average pairwise distance between AI,..., A& is at least $. So, is sufficient to prove that the average
distance between A2+1 and A1,..., A& is at least z. This is equivalent to Σ D ARt1) kd 2
By the triangle inequality, we have D(A,, Vi) + D(A,, 12) 2 D(V, V22 = d for all 1 S S k. Summing these inequalities for all i, we get
Σ D(A VI) + Σ
D(A,, 122) 2 kd,
1=1
therefore
kd D(A, Vi) 2 kd or Σ D(A,, 2 2
Thus, by the construction of the greedy
# algorithm, we have Σ D(A,, Ax+1) A(A)) 2 kd
Bottleneck Suppose 5 Cl,..., On and (iversity(S)- = m. Suppose the greedy algorithm has already made & < N steps choosing graphs Ai...., Ak., and the diversity of A1...., A₁ is at least We define an open ball with center in G E S and radius as the set of all graphs in S such that their distance to G is less than r. Consider N open balls with centers CI....; CN and radius m Clearly, these balls do not intersect. Since l < N, there is at least one of N balls that does not contain any of Al. Therefore, the distance from the center of this ball to all A,,..,, A is at least 2
3.
Thus, the greedy algorithm can make one more step while still preserving the diversity of the chosen set not less than 2 Since we prove it for all i < N, the diversity of the greedy algorithm result on step N will be at least Th DDveersity(S).
17

---

Energy We prove that Diversity($) 2 2" ('DiversitySS) by induction on N, which is the size of the set S. The base case N = is trivial, since for every element there exists a second element at distance more than or equal / (by the triangle inequality, one of the ends of any diameter can serve as such a element).
Inductive step. Suppose the statement holds for N k. Let us prove it for N k Suppose the greedy algorithm made k steps and picked graphs AL.....A4 AA C.....: Ck+1. We pair A1 with the nearest graph from the set S (ties break randomly), w.l.o.g. assume that this graph is C1. We pair A2 with the nearest graph from the set $ [C1]. w.l.o.g assume that this graph is C2. We pair C3 with the nearest graph from the set S \ C2), w.l.o.g. we assume that this graph is C3. etc. Note that the graph Ck+1 is left unpaired, Let us prove that Diversity((A) follows trivially.
in this order. Suppose 5 =
Ag, 11+1)) 2 2 Diversity (S), from which the statement of the theorem
By the induction hypothesis, we have Diversity ((A,, AxJ) N D
C+}). So. it is sufficient to prove that D(A1, S -27 D(C,) which is equivalent to
Σ D(A1, 2 2 Σ De+) Given that y > 0, this incquality holds if we prove that C(41) 2 2 C for every i. Rewriting the last inequality, we get D Ck+1) S 2D(A,, Ck+1). This inequality holds since:
D Ck-1) D(C,, + D(A,, Ck+1) S 2D( Cx+1).
Here the first inequality is the triangle inequality. The second inequality follows from the pairing construction which ensures that ( A,) is less than or equal to D(A,, Ck+1).
Now, let us analyze the time complexity of the greedy algorithm. Here and below, we assume that computing graph representation for a distance D for graph with nodes requires numerical operations. Given that, the distance between two representations requires b numerical operations. Every distance is computed only once and then the result is cached.
Proposition C.2. The time complexity of the greedy algorithm is O((a + bN) where M |S| (the size of the initial population) and N = |S] (the size of the desired diverse population).
Proof. We do not take into account the time complexity of generating the population $ since it heavily depends on the choice of graph generators. First, we compute the descriptors for all graphs in 6, which is aM operations. For all graphs, we set their current fitness to 0. Then, at each step of the greedy algorithm, we compute the distances from all elements of \ S to an element added to S on this step, which is O(bMl) operations. Using the computed distances, we update the current fitness for all graphs in ((M) operations. The choice of an element that we add to S can be done in ((M) operations. So, each step requires Obb) operations. Given that we have N steps, the resulting time complexity of the algorithm is O(aM + bMN) = O((a + M).
Generating the set S Generating a sufficiently diverse set S is a necessary ingredient of the success several random graph models with different
of the greedy algorithm. To generate such properties. For each model, we iterate over the parameter combinations to get structurally different graphs. After this procedure, we assume that the set Š is rich enough to contain a wide variety of graphs. The next subsection describes the models used for generating the set S.
C.2 Mixture of random graph generators
All models below generate graphs with fixed number of nodes n. our experiments, we take = 16 and n = 64. The graphs are undirected and without self-loops and multiple edges. We describe only the versions of models that we use in our experiments. Some of these models have more general versions with more parameters that we do not use and do not describe. To obtain sample of graphs, we generate an (approximately) equal number graphs for each combination of model and its parameters.
18

---

Erdös-Rényi In this model, each edge is included in the generated graph with probability independently from all other edges.
We consider E
3 7 151 16 17
8 16
Preferential Attachment (Barabási and Albert 1999) In preferential attachment models, nodes are added one by one, and each new node attaches to several previous ones with probabilities depending on their degrees. Here the parameter reflects the number of outgoing edges added together with each new node. The probability that a new node is attached to an older node is proportional to K; + a, where k the number of incoming edges of and 0 is parameter reflecting the attractiveness of nodes with zero incoming degrees.
We consider m (1, 4) and {m/2, m, mn,2m). Such values of give the power-law degree distribution with parameters 7 E (2.5, 3) Ostroumova et al. 2013).
This is modification of the preferential attachment model, allowing for varying the number of triangles. Again, nodes are added one by one; each node appears with edges. Edges are also added one by one, and there are triangle-forming Random edges connect the new node with an old one with probability proportional the total degree of the old node. Each random edge can be followed by a triangle-forming edge (with probability p) or by another random edge (otherwise). To add a triangle-forming edge, we do the following: we uniformly sample neighbor of the previously chosen node and connect the new node to this neighbor.
Holme-Kim (Holme and Kim. 2002)
types of edges: random and
In our experiments, we take E {2, 4) and p {0.5,1). 1).
Random graph with power-law expected degree sequence (Chung and Lu 2002) First, we sample sequence W (Wi,... w.) from power-law distribution with parameter y. Then, construct a graph by connecting the nodes i and j with probability 10;31
Here we use 7 E (2,225,3,43.
Random geometric graph (Penrose 2003) First, nodes placed uniformly random in the unit cube in Rd. Then, two nodes are joined by an edge if the distance between them is at most
We take d (2,3), where for d = have {1/3, 0.5, 0.65].
{0.2, 0.3, 0.5) and for d 3 we have r
Random regular graph This model generates a random graph, each node of which has degree d.
We consider d {1,2, 8, 10).
Stochastic block model (Holland et al. 1983)
We divide n nodes into sets (blocks) of (approxi- mately) equal size. Each edge between two nodes from the same block is included with probability p. independently from all other edges. Each edge between two nodes from different blocks is formed with probability g, independently from all other edges.
In the experiments, we use r = and r = 3. For r = 2, we use all combinations of pairs (p, q) from the set {(2s, 8) Vs E S} 3 ((x, 2s) Vs E S}, where i 3 1 })- For r = we use
(p, 9) E (G2 1), G,, }
Our implementations are based on NenworkX and igraph Python libraries.
C.3
Genetic algorithm
This section describes our implementation of the genetic approach.
High-level description of the algorithm First, we obtain an initial population of N graphs using either specific random generator, or an ensemble of models, or user input with the size N. After that, we repeatedly do the following procedure. We choose two distinct parental graphs P1 and Pz from the population, and via crossover and mutation generate a child graph C². After that, we go over all graphs in the current population, try to replace each of them with C' and compute the difference
19

---

Figure 7: Graphs from Genetic with Portrait-div
in diversity caused by the replacement. Then, we choose the graph with the largest difference and if is positive we replace it with C"; otherwise, we do nothing. Then we repeat the procedure. We also limit the number of unsuccessful attempts and denote this parameter as K. Now let us consider all stages the algorithm in detail.
Initial population For an initial set of graphs, can either use established random graph models (e.g., generate N graphs with n nodes each using the Erdös-Rényi model with edge probability p 0.5 with mixed p) can pass already saved set of graphs through command-lin argument (for instance, the resulting population from the greedy algorithm can become the initial population for the genetic algorithm). The nodes of each graph are labeled by numbers 1,2...., (we will need these labels for the crossover procedure). Denote the generated population by
Selecting parents We randomly select two different graphs from S parents. To do assign each graph the probability proportional to its fitness w.r.t. set of all other graphs and sample two different graphs from the resulting distribution We denote these graphs by P. and Pz.
"Since Energy is negative, for this measure sample with probabilities proportional to
20

---

Figure Graphs from IGGM with Portrait-div
Crossover Given the graphs Pi and Pz. we construct new child graph C. Informally, we want C copy some nodes and edges from P1 and some nodes and edges from Ps. For each label from to n, we randomly and independently assign a number or 2 with equal probability. If a label has been assigned 1, then the node copied from P1, and otherwise it is copied from Pz. After that, for each pair of nodes < j, we determine whether C' has an edge between i and follows:
if was assigned and j was assigned 1, then C' has an edge between i and iff P1 has an edge between i and j:
if was assigned 2 and j was assigned 2, then C' has edge between i and iff Pg has an edge between i and j:
if i and j were assigned different numbers, then we randomly choose one parent, and C has an edge between and j the selected parent has an edge between and j.
Mutation We follow Ipsen and Mikhailov (2002) and perform mutations as follows. Given graph C, with probability a we construct mutated graph C". First, we choose node from uniformly at random and delete all edges connected to it. Then, we select number & E [1, 21.,, n uniformly at random. We draw k new edges from the node. These edges connect to random distinct nodes of the graph, with each node having an equal probability of being connected to. The resulting
21

---

Figure 9: Graphs from IGGM with netLSD-heat: most of the graphs are sparse
graph is denoted by C². The probability of mutation another parameter of the algorithm. mutation does not occur, then we take C" C.
Update We check each graph from the population and try to replace it with C'. By U we denote the ((" U). then
graph giving the largest improvement after the replacement. If remove U from S, add C' to S, and call C' successful child. Otherwise, C" is called unsuccessful, and the population S remains unchanged. Note that this procedure does decrease the diversity of the population and keeps the size of the population equal to N.
Number of update attempts We limit the complexity of our algorithm by the total number of update attempts L,, after which the algorithm finishes. Both successful and unsuccessful attempts are counted. To prevent the algorithm from getting stuck in a local optima, we count the number of consecutive failed updates. If there are no successful updates during the last K attempts, accept the candidate C% among the last K with the maximum value of f( S \ U) - fUU, S U) and replace by C/ in S. Since the added child is unsuccessful, decreases the diversity of the population but helps to handle plateaus, which turned out to be more effective than restricting the decrease of diversity.
Now, let us analyze the complexity of the genetic algorithm.
22

---

Figure 10: Graphs from IGGM with netLSD-wave: most of the graphs are sparse
Proposition C.3. The time complexity of the genetic algorithm is O((a + bN)L), where is the complexity of computing a graph representation,
complexity of calculating the distance between two representations, and L, is the number of update attempts.
Proof. Each step the genetic algorithm requires ( operations for the choice of parents, O(n²) for the crossover, Onn) for the mutation, where n is the number of nodes in graph, O + 6N) calculate distances between the generated child and every graph in the population, O(N) to find graph U which gives the largest improvement. So, in total, one step requires O(n² + + bN) operations. Since for all used distances we have n², we get that one step requires O(a + bN) operations. If we run the genetic algorithm for I. steps (thus generating exactly I. children), the resulting time complexity is O((a + 6N)
The time complexity of generating the initial population and calculating the fitness for all its elements small in comparison with O(aa bN)L), so does not influence the time complexity of the algorithm (given that L >> N).
23

---

Figure 11: Graphs from IGGM with GCD
C.4 Local optimization algorithm
Initial population The local optimization algorithm supports the same techniques as the genetic algorithm for defining the initial population. Namely, we can pass existing graphs through command generate graphs the fly from random graph models, e.g., ER-0.5 or ER-mix. At the beginming, we compute the fitness f G) for every graph the population
line argument
Then, we do the following:
1. At each iteration, choose graph with probability inversely proportional to its fitness and denote this graph by U.
2. Pick two distinct nodes and v from U uniformly random. If edge (u, v) exists in U. remove it. Otherwise, add (u, v) to the edge list of U. Using this atomic operation, we obtain changed graph U"
3. Compute the fitness S(U', U).
4. If ((U',SXU) > fUUS U), replace U by U.. Otherwise, do nothing and repeat the process.
For Energy, sample with probabilities proportional to fitness.
24

---

Chierny
Dricnny
Dirowecy
lng cuiterrg conficerr
Custaiing cerficc
Agg Satsiing cart
Ang. chattrng corttiies
Figure 12: Joint distribution of graph characteristics, extended figure
5. Similarly the genetic algorithm, track the previous K attempts and if they fail, accept the replacement among the last attempts with the lowest difference between f (U,, S) Ux) and f(UR, UR).
6. Repeat the process I. times, where T. is the total number of attempts.
The following proposition follows from the algorithm description.
Proposition C.4. The complexity of the local optimization algorithm is O((a + bN)L), where is the complexity of computing a graph representation, b the complexity of calculating the distance between two representations, and L is the number of update attempts.
C.5 Iterative Graph Generative Modeling (IGGM)
In this section, we describe our implementation of the approach based on iterative neural generative modeling for the task of obtaining N structurally diverse graphs.
We denote the number of generated graphs during each generation step by K and the total number of generated graphs by L. is not strictly required but assumed that L. is divisible by K. Another parameter of the algorithm is R K: R graphs are used train each graph generative model. In our experiments, we set A 103, K = 10 L = 106.
To obtain the initial set of graphs to train generative model we do the following: generate set of 10R graphs from ER-mix and then apply the Greedy algorithm on that set, obtaining R initial graphs, which we denote So and start the process.
At each step I, we train a generative neural network go, on the graphs obtained from the previous step S,-1: the notation 0g represents trainable parameters of the model at step L. Then, we use go, fixed random graph generator to create > R graphs and apply the Greedy algorithm to choose diverse graphs that will form the next training input.
25

---

Table 4: Energy optimization results for graphs with 16 nodes
Setup
GCD
Portrait-div
NetLSD-heat
NeiLSD-wave
ER-mix
0.281 +: 0.0350
43.057 =: 8.812
72.387 26.192
0.583 +: 0.0892 0.621 0.0117
GraphWorld
0.466
3.917
0.0896
5.108 0.2856
Random Graph Generators
0.553 0.0167
0.2368 6.009
116.685 8.009
1.334 + 0.0831
Greedy[IM]
0.160 0.0004
1.287 0.0029
0.682 0.0005
0.124 0.0003
Greedy[2M]
0.157 + 0.0010
1.278 0.0033
0.681 + 0.0008
0.124 + 0.0004
Greedy[3M]
0,156 + 0.0004
1.274 0.0018
0.681 = 0.0001
0.123 + 0.0003
ER-mix ]
0,139
1.264 0.0031
0,677 0.0013
0.117 0,0003
-
0.139
1.263 0.0020
0.000
0.118 0.0005
0,141 + 0.0012
1.263 0.0027
0.674 + 0.0004
0.118 + 0.0005
ER-mix Genetic[[M
-Local00((M
0,138 :: 0.0002
1.259 0.0007
0.675 + 0.0000
0.117 + 0.0001
Greedy||MM [Maedy||MM-1ocaa00mm1121
0.118
Greedy[1M] Genetic[ LocalOp[[IM]
0.135 0.0000
1.245 0.0004
0.673 0.0001
0.117 0.0001
In experiments, for 9e, use Discrete Denoising Diffusion model DiGress (Vignac al. 2023), which is distributed under the MIT License, with its default parameters (including model hyperparameters and training routine) generate graphs.
As result, our procedure consists of K steps, where at each step S sts K do:
1. Train generative model Do, the set of graphs S;-1, initial weights are taken from the last weights of the previous iteration;
2. Generate K graphs using ge.;
3. Apply the greedy algorithm to the generated set of graphs to obtain R graphs, denote this set by S..
Note that after each iteration, we can greedily choose N graphs from S, of size R. and thus obtain the set of structurally diverse graphs with the desired size.
The time complexity of the algorithm depends on the number of epochs chosen for each network training step and thus may vary lot. We used the default parameters of DiGress proof of concept.
D Experimental setup
Graph World parameters For GraphWorld, we vary the model parameters to obtain more diverse graph structures. Namely, we choose the following parameters uniformly: P2Q-ratio from [1, 10), communities from 2,, 3, 5,5), avg avg_node, mode_degree form [4, n 1], ppwer_exponent from [0.5,
Hardware setup The experiments have been conducted on the machine with Intel Core i7-7800X @3.50GHz CPU, NVIIII GeForce RTX 2080 Ti GPUs and 126G RAM. took us approximately 500 CPU hours to conduct all the experiments.
E
Additional experiments
Examples of generated graphs Examples of generated graphs shown in Figures 7 We see that when combined with Portrait-div, both Genetic and IGGM generate visually diverse and interesting structures. One also notice that NetL.DD tends to generate many extremely sparse graphs, while GCD generates more dense graphs.
Visualizing graph characteristics Figure 12 visualizes various characteristics of generated graphs GrrlhWorld
for the ER-mix and Graph World baselines, IGGM, and the combination of Greedy, Genetic, and LocalOpt. It extends Figure 4 from the main text.
Extended numerical results Table extends the results from Table and also reports the standard deviation based on five independent trials.
26

---

Table 5: Energy optimization results for graphs with 64 nodes
Sctup
GCD
Portrait-di
NetLSD-heat
NetLSD-war wave
ER-mix
0.400
2.236
452.885
0.454
GraphWorld
0.442
3.746
3,509
0,510
Random Graph Generators
0.540
5.868
112.685
1.298
Greedyf IM]
0.177
1.155
0.812
0.172
Greedy[3M
0.175
1.148
0.796
0.169
BR-mix--GGenetic(MN)
0.167
1.128
0.567
0.128
-
0,158
1.126
0.673
0.117
ER-mix Samix-xGeeetinn -
0.133
1.086
0,551
0,118
Greedy IM] +=ooco00(([(]
0.132
1.082
0.603
0.117
Greedy( [M] + GcM + 1Mc
0.128
1.060
0.673
0.116
Larger graphs We conducted experiments larger graphs with = 64 nodes, the results shown in Table 3able53and and they are consistent with the results on smaller graphs.
27

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract, we summarize the novelty and objectives generating structurally diverse graph sets and improving understanding of graph distances. In the introduction, we highlight the relevance of the problem, existing gaps, and our approach to addressing these challenges through new proposed algorithms and defining diversity.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We describe the limitations and further perspective directions of our proposed research in Section 5
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We present each theoretical result with clear assumptions stated and provide proofs for all theorems and formulas. The proofs are numbered, reos-refferenced, and appear in Appendices A.2 Cnd
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We disclose the full set of hyperparameters of graph random generators in Appendix C.2 and the used hyperparameters of the proposed algorithms and utilized
techniques in Section the main text. We also provide the source code.
5. Open Access Data and Code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide the source code with the README file that contains all configura- tions needed reproduce the results from the paper.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify the experimental setting in Section 4 For the IGGM method, we describe the parameters in the Appendix C.5
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
28

---

Justification: We provide the mean and standard deviation of the obtained metrics in Table 4 in Appendix, which is the extension of Table in the main text and the central numerical experiment of the paper. We do not provide standard deviations for the IGGM method and for additional experiments presented only Appendix due to the high computational cost.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We describe computational resources Appendix D
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research aligns with the NeurIPS Code of Ethics, conduct in every aspect of the study, including data handling, experimental procedures, and potential societal impacts. We disclose the complete set of experimental results and provide the full source code of the framework.
ethical
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The research conducted in the paper foundational and is tied any particular societal impact. The main focus of the paper is to facilitate further research in the direction of generating structurally diverse graphs, thus making current work dedicated to general case without societal implications.
Justification:
11. Safeguards
Question:
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper does not release any data models that pose high risk for misuse.
12. Licenses for Existing Assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We use DiGress as a deep learning graph generator in our IGGM method, which distributed under the MIT License. We cite the original paper and also mention the distributed license in the Appendix C.5
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We support the provided code with clean and concise annotations.
Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
29

---

The paper does not involve crowdsoureing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Justification:
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
30


Reviews:
[{"review_id": "eEEx2gFAZg", "reviewer": "Reviewer_myRm", "summary": "This paper goes through the diversity of graphs and proposes the relevant generation process for diverse graphs. Various generation methods, such as genetic algorithms and greedy algorithms (based on diverse random graph generators), are studied and theoretical results are provided to guarantee the lower bound from the diversity respective.", "questions": "N.A.", "limitations": "Please refer to Limitations.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper is well motivated, and the generation of diverse graphs is a good domain for research.\n\n2. This paper is well written and the idea is easy to follow.\n\n3. The experiment results are sound.", "weaknesses": "1. The novelty of this paper should be better stressed, especially for the framework of measuring the diversity via energy.\n\n2. The choice of the measuring of graph diversity is questionable. Overall, the matching of graphs is  combinatorics, popular metrics such as graph edit distance to measure their similarity are fundamental NP-hard problem in graph theory. I think this part should also better discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and positive assessment of our work! We address the weaknesses below.\n\n> W1. The novelty of this paper should be better stressed, especially for the framework of measuring the diversity via energy.\n\nTo the best of our knowledge, the problem of generating structurally diverse graphs hasn’t been studied before and we make the first step in this direction. Standard machine learning algorithms cannot be directly applied to this problem and thus we had to adapt them to the task at hand. Regarding diversity evaluation, we prove that typically used measures have critical drawbacks and show that energy is more suitable for this task. Our theoretical analysis is also novel.\n\n> W2. The choice of the measuring of graph diversity is questionable. Overall, the matching of graphs is combinatorics, popular metrics such as graph edit distance to measure their similarity are fundamental NP-hard problem in graph theory. I think this part should also better discussed.\n\nWe discuss the problem of comparing two graphs in Section 2.2 and Appendix A. Here, we briefly discuss measures based on the optimal node matching in lines 111-115. We don't consider such measures in our experiments since they are computationally expensive. We will add graph edit distance to this discussion, thanks for the suggestion.\n\nWe hope that these modifications address your concerns. If you have any more concerns or ideas about what should be specified in the text, please let us know.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "H33f4OWTRm", "reviewer": "Reviewer_h5vQ", "summary": "This paper focuses on the problem of generating structurally diverse graphs, an important problem for evaluating graph algorithms.  In short, if you are trying to generate a set of graphs to evaluate an algorithm's performance (runtime or otherwise) one desires a set of graphs that \"span the space\" of possible graph types in order to make robust estimates of the performance.\n\nThe paper first covers different measures of graph similarity, and then goes into 'energy' based algorithms for structure diversity optimization.   Its here that the work may lose a little novelty (its more about the problem and less about the solution).  However all-in-all, I think its a nice contribution that highlights an important (unsolved) problem in graph machine learning.", "questions": "1.  It seems like the entire question rests on the graph distance measure used, and you avoid this discussing this.  What's the best choice?  Alternatively: how could one tell what the best choice for them would be?\n\n2.  How does the work from the diversity sampling literature relate to this work (in particular the optimizations in section 3.)  Section 2.3 addresses two recent related works, but seems there are probably a lot of relevant citations here -- there's a whole cottage industry on diversity sampling.", "limitations": "Yes", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "+ topic is important and understudied\n+ excellent presentation\n+ interesting experimental results", "weaknesses": "- the problem is still unsolved\n- since there's not much work, there aren't obvious benchmarks to beat\n- I have some doubts about the scalability (and therefore practicality) of the presented solution\n- the work could probably use more connections to the diversity sampling literature, since once one has a similarity metric, it seems like this is just diversity sampling", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and positive feedback! Let us address the weaknesses and questions.\n\n> the problem is still unsolved\n\nWe agree with this and we are not expecting this problem to be completely solved in the near future. The problem is challenging, starting from the difficulties with defining diversity for a set of graphs. We hope that our work will stimulate further discussions and progress on this problem. However, we believe that we made an important step towards solving the problem: the proposed methods indeed generate quite interesting and diverse graphs, as can be seen in Figure 3.\n\n> since there's not much work, there aren't obvious benchmarks to beat\n\nIndeed, it is hard to find proper baselines for pioneering studies. Hence, the main goal of our research is to formulate the problem and see how effective are different types of approaches. However, we do our best to design strong baselines based on existing random graph generators and the GraphWorld benchmark.\n\n> I have some doubts about the scalability (and therefore practicality) of the presented solution\n\nWe expect scalability to be one of the main challenges for future studies. We mention the scalability challenges in lines 370-373 and also make some preliminary experiments with larger graphs (up to 1000 nodes) in Appendix E.3. We do not dive deeper into scalability issues since there are plenty of challenges even for small graphs. However, we do agree that the scalability question is important. Let us also mention that for some practical applications, even such small graphs can be useful: e.g., in neural algorithmic reasoning, models are usually trained on graphs of size up to 16 nodes, and molecular graphs are also small.\n\n> It seems like the entire question rests on the graph distance measure used, and you avoid this discussing this. What's the best choice? Alternatively: how could one tell what the best choice for them would be?\n\nThe problem of the best graph distance measure has been studied for a long time, and there is no clear answer yet, as all distances tend to have biases toward some graph characteristics. It is an important and long-standing problem, so we do not aim to answer this within our work and choose several representative distances for our empirical study (to show that our approaches can be applied to any chosen graph distance).\n\nHowever, we do discuss and compare graph distances in our experiments. In Appendix E.4 (Figures 12, 13), we show that depending on a chosen graph distance, the obtained graphs may significantly differ. By generating diverse graphs using a particular distance measure and then inspecting the properties of the obtained graphs, one can get new insights about what structural properties this distance measure is sensitive to. For instance, we noticed that NetLSD is biased towards sparse graphs and thus most of the obtained diverse graphs are sparse.\n\nWe believe that the best choice of a distance measure may depend on the application. For instance, in the molecular domain, substructures of a molecule may heavily determine its properties, and thus GCD can be a good option since it is sensitive to small substructure counts. On the other hand, if diverse graphs are needed for testing some graph algorithms, then diversity in terms of graph diameter or average shortest path length can be desirable, and in this case Portrait Divergence can be considered as a favorable choice.\n\n> How does the work from the diversity sampling literature relate to this work (in particular the optimizations in section 3.) Section 2.3 addresses two recent related works, but seems there are probably a lot of relevant citations here -- there's a whole cottage industry on diversity sampling.\n\nThanks for pointing this out, we will mention diversity sampling in the text. Diversity sampling refers to techniques used to select a subset of datapoints from a larger dataset that are representative of the dataset's diversity. Unfortunately, we cannot directly apply these methods to our task since diversity sampling does not go beyond the existing dataset: it is assumed that the dataset to sample from is given and one can iterate through its elements. In contrast, our goal is to generate new graphs: we cannot iterate through all non-isomorphic graphs on $n$ nodes. Section 3.1 of our paper (Greedy baseline) is the one most related to diversity sampling: in this section, we pre-generate an initial set of graphs and then choose the most diverse graphs from this set.\n\nAs far as we know, there is not much research on measures of diversity in diversity sampling literature. For instance, diversity is often defined as the sum of pairwise distances (our Average) or its modifications [1,2]. In other cases, diversity can be defined in terms of a variety of class labels or other sample features [3]. In contrast, graphs can vary in structure, connectivity, and many other properties and thus we cannot resort to such simple diversity measures in the more complex graph domain.\n\n[1] S. Agarwal et al. Contextual diversity for active learning. ECCV 2020.\n\n[2] Y. Yang et al. Multi-class active learning by uncertainty sampling with diversity maximization. IJCV 2015.\n\n[3] Y. Geifman et al. Deep active learning over the long tail. 2017.\n\nWe are open to further discussions!", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "dtUHZLNyNe", "reviewer": "Reviewer_wU7k", "summary": "The authors investigate the problem of generating graphs that are structurally diverse. Specifically, the graphs should be as different from each other as possible in terms of their properties.\nTowards this, the authors first propose a new way to measure graph diversity based on the idea of energy(combined with several graph distances).\nThey describe several algorithms for generating diverse graphs, namely greedy, genetic based and  local optimization, and neural -based.\n\nThe authors mention that in order to test many graph algorithms or models, it  requires diverse graphs. Otherwise, results might be misleading, only reflecting the tested graph types.", "questions": "Please see weakness.\n\nI am mostly concerned on the application of the proposed work. How does one use it? \n\nIs it possible to model some data distribution+ with diversity?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper propose an interesting problem of generating structurally diverse graphs and its importance in different fields such as evaluating graph neural networks and their expressive power etc.\n\n2. The paper is easy to read.\n\n3. The authors define an interesting idea of energy based functions for measuring diversity.\n\n4. Empirical analysis shows better performance in comparison to baselines.", "weaknesses": "1. It is not clear to me whether there is a data distribution which is learned.\n\n2. If in  (1)  there is no data, how does one apply the proposed idea to generate graph that follow a distribution? On what data will we evaluated GNN on?\n\n3. What is the usage of diversity without fidelity metrics: such as structural similarity between 2 datasets( training and generated)?\n\nEg : see https://arxiv.org/abs/2001.08184\nGraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation.\nSee diversity and fidelity section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We address the questions and concerns below.\n\n> 1. It is not clear to me whether there is a data distribution which is learned.\n\nOne of the main differences between our setup and previous works on graph generation is that we do not have any data distribution that we want to mimic. Our goal is to generate a set of graphs that are maximally diverse.\n\nIf we define diversity in terms of a particular graph distance then, roughly speaking, one may think that there is a latent space related to this distance measure and we want to learn a uniform distribution over this space. Our proposed non-generative algorithms (e.g., Genetic and LocalOpt) do not sample from this space but iteratively explore it with different techniques. Our generative-based algorithm IGGM aims to learn the uniform distribution mentioned above. To train the IGGM model, we start with some sufficiently diverse distribution, then learn it with a graph generative model, use this model to obtain a more diverse set of graphs, and repeat the procedure.\n\n> 2. If in (1) there is no data, how does one apply the proposed idea to generate graph that follow a distribution? On what data will we evaluated GNN on?\n\nAs mentioned above, we do not mimic a given distribution, we aim at generating a maximally diverse set of graphs. After we define what we mean by “diversity of a set of graphs”, the problem is well-defined and does not require any training set. Could you please clarify your question so we can properly address it?\n\n> 3. What is the usage of diversity without fidelity metrics: such as structural similarity between 2 datasets( training and generated)?*\n\nAs explained above, we do not have training data, so there is no possible comparison of structural similarity between training and generated datasets.\n\n> I am mostly concerned on the application of the proposed work. How does one use it?\n\nThe main question of the work is how one can generate a set of graphs that are maximally diverse. As we mention in the introduction, we foresee the following applications of the obtained graphs:\n- analyzing the performance of a graph algorithm;\n- estimating how well a heuristic algorithm approximates the true solution for a graph problem;\n- evaluating neural approximations of graph algorithms;\n- training neural approximations of graph algorithms to improve their robustness and generalizability;\n- evaluating graph neural networks and their expressive power.\n\nIn all these cases, algorithms and models should be tested on as diverse graph instances as possible since otherwise the results can be biased towards particular properties of the test set.\n\n> Is it possible to model some data distribution+ with diversity?\n\nYes, one can potentially combine a measure of diversity with similarity to a given distribution in one loss function and then use any of the proposed algorithms to optimize this.\n\nWe hope that our responses address the raised questions and we are open to further discussions.", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "eCg1U5TxNG", "reviewer": "Reviewer_VyJM", "summary": "This work considers the problem of generating graph topologies that are structurally diverse. The core argument for considering this task is that training and evaluating models for graph learning requires good \"coverage\" of the space of possible graphs to draw meaningful conclusions. The paper discusses various ways of quantifying the distance between two graphs, as well as ways for measuring diversity for a set of graphs given a distance measure. It then proposes a series of algorithms for generating structurally diverse graphs that essentially start from an initial set of graphs that are altered via local modifications; with changes being accepted if the diversity metric improves. It validates experimentally that the proposed procedures lead to more diverse graphs than, e.g., using Erdos-Renyi graphs or a pre-existing library of graph topologies.", "questions": "Please address W1, W2, W3 above. Additional minor comments:\n\n- First paragraph of the introduction would benefit from citations\n- L38: use `\\citep` instead\n- Another \"classic\" work relevant to the discussion on encoding structural information based on the graph Laplacian (L123) is [1].\n- L175: I'd avoid using $g$ to denote the bijection\n- Typos: GraphWold (L313), \"graphs graphs\" (Fig 3 caption)\n\n[1] Wilson, R. C., Hancock, E. R., & Luo, B. (2005). Pattern vectors from algebraic graph theory. IEEE transactions on pattern analysis and machine intelligence, 27(7), 1112-1124.", "limitations": "Limitations are adequately discussed.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The primary strength of the work is that it is very systematic in the way that it approaches the problem. It does a thorough job of reviewing the ways in which graph distances and diversity of a set of graphs can be quantified; and the experiment results indeed achieve the main goal of optimizing structural diversity. The writing quality and clarity of the paper are also good.", "weaknesses": "W1. In my opinion, the main weakness is that the work stops short of the main motivating use case of why generating diverse graphs is important. Namely, the work does not carry out an assessment of whether the generated diverse graphs actually improve performance for graph learning tasks (and to what extent; for what types of problems; which distance and diversity metrics are beneficial in practice, etc.). The paper in its current form reads like it is addressing only \"half\" of the motivating problem.\n\nW2. I am also unsure of the fit to the NeurIPS conference given the above, as the paper does not present findings relevant to machine learning and artificial intelligence in its current form. It may be better suited for a network science or complex networks venue. This would not be the case if the diverse graphs are then used downstream on learning-based tasks.\n\nW3. The proposed methods are fairly brute-force and quite limited in scale (experiments consider graphs with up to $n=64$ nodes, which already seem to require millions of examples). Some form of learning representation is, in my opinion, needed to make these techniques applicable on a larger scale. Furthermore, I would suggest looking into reinforcement learning as a way of carrying out the optimization process by using diversity as a reward signal for goal-directed graph construction or modification (instead of requiring \"examples\" of diverse networks as with many graph generative models, which is why they are not applicable here as the authors remark).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We address the questions and concerns below.\n\n> W1.  In my opinion, the main weakness is that the work stops short of the main motivating use case of why generating diverse graphs is important. Namely, the work does not carry out an assessment of whether the generated diverse graphs actually improve performance for graph learning tasks (and to what extent; for what types of problems; which distance and diversity metrics are beneficial in practice, etc.).\n\nIn this work, we introduce the problem of generating diverse graphs and cover several important aspects of this problem: defining diversity, testing several types of algorithms, assessing the performance. While we are motivated by some practical applications, we believe that diving deep into this is way beyond the scope of our work. First, there are plenty of challenges covered in the paper. Second, before evaluating the performance in particular applications, the first step is to generate a reasonably diverse set of graphs that can be used.\n\nWe discuss possible applications of diverse graphs in lines 26-39. For one application, namely evaluating neural algorithmic reasoning (NAR) models, we launched some preliminary experiments. We utilized the standard pipeline from the CLRS benchmark [1]. For several algorithmic tasks, we trained a standard NAR model on the train graphs from the benchmark and tested the performance on larger graphs using the following datasets: the standard CLRS test generator (ER-0.5) and the set obtained by the Genetic algorithm with Portrait-Div distance. We get the following performance (average accuracy across 5 different seeds):\n\n| Algorithm | CLSR test | Genetic Portrait-Div |\n|-|:-:|:-:|\n| Bellman-Ford  |  92  |  87 |\n| Dijkstra | 92 |  85 | | Floyd-Warshall |  31 | 29 |\n| MST-Prim | 84 | 83 |\n\nWe see that the performance drops in all the cases, implying that the obtained diverse set of graphs is more challenging compared to the baseline test set. This illustrates the importance of testing on as diverse set of graphs as possible.\n\nWhile these are preliminary results, we speculate that such diverse graphs can also be useful as a part of the training set to improve the robustness and generalizability of neural algorithmic reasoning methods.\n\nHowever, we believe that investigating particular applications should be the topic of a separate study.\n\n> W2. I am also unsure of the fit to the NeurIPS conference given the above, as the paper does not present findings relevant to machine learning and artificial intelligence in its current form. It may be better suited for a network science or complex networks venue. This would not be the case if the diverse graphs are then used downstream on learning-based tasks.\n\nWe respectfully disagree that the subject of the paper does not fit the NeurIPS scope: the topics in the NeurIPS call for papers are quite diverse and include, in particular, theoretical studies that may not directly improve downstream performance.\n\nFrom the practical perspective, our paper explores new abilities of graph generative approaches. We show how the methods can be adapted to optimize diversity. From the theoretical perspective, we conduct a theoretical analysis of diversity measures which can be of interest by itself.\n\nAlso, our problem is motivated by various practical applications and can be of interest to a part of the NeurIPS community. Here, we refer to Review h5vq which characterizes the studied problem to be an important and unsolved problem in graph machine learning.\n\nWe are open to further discussions on whether papers of such kind are suitable for NeurIPS.\n\n> W3. The proposed methods are fairly brute-force and quite limited in scale (experiments consider graphs with up to 𝑛=64 nodes, which already seem to require millions of examples).\n\nWe expect scalability to be one of the main challenges for future studies. We mention the scalability challenges in lines 370-373 and also make some preliminary experiments with larger graphs (up to 1000 nodes) in Appendix E.3.\n\nLet us mention that for some practical applications, even small graphs can be useful: e.g., in neural algorithmic reasoning, models are usually trained on graphs of size up to 16 nodes, and molecular graphs are also small.\n\nWe set our budget to 3M tested graphs as a reasonably large upper bound: algorithms may converge to reasonably diverse sets earlier. However, it is important to note that even such a budget is significantly smaller than the number of non-isomorphic graphs even for $n=16$ (lower bound for this number is $2^{n(n-1)/2} / n! = 2^{120} / 16! > 10^{14}$).\n\n> Some form of learning representation is, in my opinion, needed to make these techniques applicable on a larger scale. Furthermore, I would suggest looking into reinforcement learning as a way of carrying out the optimization process by using diversity as a reward signal for goal-directed graph construction or modification\n\nThank you for the suggestions! We believe that this can be a good research topic for further studies. Given that our work is pioneering in the field, we did not aim to cover the whole spectrum of possible approaches in the current work.\n\nThank you for the writing suggestions, we will improve the text accordingly.\n\n[1] P. Veličković et al. The CLRS algorithmic reasoning benchmark. ICML 2022.", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper addresses an important problem, i.e. generating structurally diverse graph to make evaluation of graph-based ML methods more robust, for the first time (as far as I know). While the proposed solution has some flaws (e.g. not very computationally appealing), it is a first step in addressing these challenges and it presents encouraging results. I recommend acceptance.

**Note to SAC** I will add a summary of the paper once the final decision has been taken.
Decision: Accept (poster)