Challenges of Generating Structurally Diverse Graphs

Authors: fedor  velikonivtsev
mikhail  mironov
liudmila  prokhorenkova
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-10 11:42:31

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.

Main paper: 
 introduction: 
 Figure 1 : A sample of generated graphs Many real-world objects can be naturally represented as graphs: biological and chemical entities (atoms, molecules, proteins, metabolic maps), interaction networks (social and citation networks, financial transactions), road maps, epidemic spreads, and so on. That is why the analysis of graphstructured data is an important and rapidly developing research area.To generate realistic graph structures, many random graph models have been proposed in the literature (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 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 a graph algorithm, estimate how well a heuristic algorithm approximates the true solution for a 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 GraphWorld 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-corrected 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 a 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 a set of graphs which is already a challenging task. To measure diversity, we define dissimilarity (distance) for a 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 it 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, a local graph optimization approach, an adaptation of the genetic algorithm to our problem, and a 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 to significantly improve the diversity of the generated graphs compared to basic random graph models. In addition to the numerical investigation of diversity measures, we 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 characteristics a particular graph distance is sensitive to.In summary, this work formulates and investigates the problem of generating structurally diverse graphs that can serve as 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 
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.1 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ényi 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 n nodes can be generated equally Figure 2 : Average node degree and average clustering coefficient in the Erdős-Rényi model with n = 16 and p = 0.5 (ER-0.5) or varying p (ER-mix) However, it is known that with high probability graphs generated according to the Erdős-Rényi model have typical properties and thus are all very similar to each other with high probability (Erdős et al., 1960) . For instance, as illustrated in Figure 2 , 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 of characteristics cannot be covered by the Erdős-Rényi model.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 is hard to formalize as 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 a 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 = G 1 , . . . , G N . Throughout the paper, we consider undirected graphs without self-loops and multiple edges. Assume that we are also given a distance measure D(G, G ′ ) that evaluates dissimilarity between two graphs. Then, we define diversity as:EQUATIONwhere F is some function that computes diversity given a set of pairwise distances. The choice of F is also non-trivial, and we discuss possible approaches in Section 2.3.After we have defined the distance D(•, •) and the measure of diversity, our primary goal is to find a multiset of graphs S of size N to maximize its diversity:EQUATIONwhere G n is the set of all graphs with n nodes. 2This section discusses how one can define distance between two graphs. As mentioned above, this task is highly non-trivial, and the literature on this topic is abundant (Tantardini et al., 2019; Hartle et al., 2020) .Some graph distance measures are based on 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 (a 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 a metric space since the distance between two different graphs can be equal to zero. Indeed, if we guarantee that D(G, G ′ ) = 0 if and only if G and G ′ are isomorphic, then computing the distance is at least as hard as graph isomorphism testing, which is 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 an 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 a result, our analysis of generated graphs gives some additional insights into the properties of graph distances.In this section, we 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 et al., 2023; Friedman and Dieng, 2023) discussed in more detail in Appendix A.1. 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 a 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 a 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 as 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 a 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 ′ ∈ 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 a bijection g : S → S ′ between them. Assume that for any G i , G j ∈ S we haveEQUATIONwith strict inequality for at least one pair i, 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.Uniqueness Suppose S consists of N different elements G 1 , . . . , G N . Denote by S ij the multiset obtained from S by removing G i and adding the second copy of G j for j ̸ = i, that is S ij := (S\{G i }) ∪ {G j } Then, we require Diversity(S) > Diversity(S ij ).In other words, this property requires that given N -1 elements, adding a unique element results in a higher diversity than duplicating an already existing element. This property is very intuitive since to increase the coverage it is clearly better to add a new element than to duplicate an existing one.Note that the average pairwise distance does not have the uniqueness property, thus optimizing it may lead to degenerate solutions. Clearly, the minimum pairwise distance does not have monotonicity. Moreover, it turns out that none of the measures from (Xie et al., 2023; Friedman and Dieng, 2023) has both these properties, see Appendix A.2 for the details.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 a set of graphs S asEQUATION)The parameter γ affects how strongly we penalize small pairwise distances. In an extreme case of γ → ∞, this measure becomes equivalent to Bottleneck. All our theoretical results hold for any γ > 0. 3 For our experiments, we use γ = 1, so ( 4) can be naturally interpreted as the average pairwise energy for a system of equally charged particles (we multiply by -1 to get a measure that is larger for more diverse sets of graphs).Our toy example in Figure 3b shows that when being optimized Energy leads to a diverse configuration, in contrast to Average. Regarding our formal properties, monotonicity is obviously satisfied by Energy (4). To 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 -∞.Proposition 2.1. Energy (4) satisfies both monotonicity and uniqueness.Despite having these desirable properties, Energy still has a shortcoming: it can be unboundedly large when two elements become too close to each other. However, there are currently no better alternatives, as shown in a 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 a discussion. In our experiments, we use Energy (combined with several graph distances) as our primary measure of diversity and also consider Average as an additional measure. 
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 is to 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, we restrict ourselves to measures that can be written in the following way. Suppose we are given a set of size N and any element G from this set. Denote the subset of all elements excluding G byS = {G 1 , G 2 , . . . , G N -1 }.Then, the diversity of the original set can be written as:EQUATIONwhere g is a function that is monotone w.r.t. both arguments, f (G, S) depends only on the distances {D(G, G i ) : G i ∈ S}, and c(S) is a value that depends only on S (and does not depend on G). We call such function f (G, S) a fitness of a graph G w.r.t. a set of graphs S.The measures considered in this study satisfy (5) . For instance, for Energy, g can be the sum, 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.f (G, S) = 1 N (N -1)/2 Gi∈SThe main idea of this algorithm is to build a set of diverse graphs iteratively by adding at each step the most suitable graph from a predefined set Ŝ of a much larger size. This set 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 a graph from Ŝ. At each step, the most suitable graph from Ŝ is chosen according to the fitness f (G, S), where S is the currently selected set of graphs.A detailed description of the algorithm is given in Appendix C.1. We also provide the analysis of computational complexity and a lower bound on the diversity of graphs returned by the greedy algorithm relative to the diversity of the initial set Ŝ (see Theorem C.1).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 to find a more suitable offspring by repeating the process. To prevent itself from getting stuck in local optima, the algorithm can accept a 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 at the same time introducing novel configurations to achieve a diverse set of graphs.The details of this algorithm are given in Section C.3, where we also analyze the complexity of the 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 an initial set, we randomly sample graphs and make small modifications to their structure (single edge addition/deletion). 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.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., 2023) . 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 S 0 and then iteratively enhances the diversity. At each iteration, the current set of graphs S i is used to train a generative model. Then, this model is used to generate a significantly larger set of new graphs. From this new set, a smaller subset of diverse graphs S i+1 is selected via the greedy approach. We expect that S i+1 is more diverse than S i . So, we repeat the process by training a neural generative model on the new set S i+1 . For the neural network architecture, we use Discrete Denoising Diffusion Model (DiGress) (Vignac et al., 2023) . We refer to Appendix C.5 for a detailed description of our approach. 
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.In our experiments, we consider four representative distance measures: heat and wave NetLSD (Tsitsulin et al., 2018) , Graphlet Correlation Distance (Yaveroglu et al., 2014) , and Portrait Divergence (Bagrow and Bollt, 2019) . We select these distances to be diverse: NetLSD is based on the Laplacian eigenvalues (we use NetLSD-heat and NetLSD-wave 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 as the diversity measure. Formally, we optimize and report the following measure:1N (N -1) i̸ =j 1 D(G i , G j ) + ϵ ,where ϵ 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 a sample of graphs generated by the GraphWorld 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 n = 16 nodes. We also conduct experiments with non-neural algorithms on the set of 100 graphs with size n = 64.Let us note that the algorithms introduced in Section 3 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 is 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 C.2.We assume that for most algorithms, the most time-consuming operation is computing a graph representation (that is 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.In this section, we numerically analyze how well different approaches optimize the chosen diversity measure. Table 1 shows 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 GraphWorld is far from optimal. This is not surprising since GraphWorld 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 is achieved by a combination of Greedy, Genetic, and LocalOpt (applied in this order). Such a 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. In turn, the neural-network-based method IGGM gives a significant boost in diversity for GCD and Portrait-div distances and exhibits comparative results for NetLSD-heat. Note that it uses less budget for generated graphs but also requires training a graph generative neural model several times. Analysis of structural characteristics Additionally, we analyze the structural characteristics of generated graphs. Figure 4 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 is 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 n -1, then the clustering coefficient has to be close to 1. For more algorithms and combinations of characteristics, please refer to Figure 12 in Appendix. Avg. clustering coeff.Avg. node degree Comparing graph distances Visualizing pairwise graph characteristics 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 5 . One observation that we make is that NetLSD is significantly biased towards sparse graphs (for clarity, Figure 5 shows the results for NetLSD-heat, but the wave variant has the same patterns). Indeed, for most 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-div accounts for global characteristics.f (U ′ , S \ U ) > f (U, S \ U ), replace U by U ′ .Otherwise, do nothing and repeat the process. Similarly to the genetic algorithm, we track the previous K attempts and if they fail, we accept the replacement among the last K attempts with the lowest difference between f (U ′ k , S \ U k ) and f (U k , S \ U k ). 6. Repeat the process L times, where L 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 a is the complexity of computing a graph representation, b is the complexity of calculating the distance between two representations, and L is the number of update attempts. 
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 set of graphs to be diverse. In this regard, we propose desirable properties that a 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 a 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 n 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 a proper graph distance seem to be very useful. Finally, it would be great to see practical applications of diverse graphs. 
 
 Appendix: 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 is 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.A recent paper by Friedman and Dieng (2023) suggests measuring diversity via the Vendi Score (VS). This score requires a kernel function defined on pairs of elements. Then, a 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 a 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 a good measure of coverage is expected to satisfy: monotonicity, subadditivity, and dissimilarity. Then, they show that none of the abovementioned measures satisfy all three axioms simultaneously and propose a 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 is exponential. Second, it requires the radius parameter to be defined and a good value depends on a dataset. In our setup when the set of graphs dynamically changes during the optimization, this measure cannot be applied.Let us discuss how the properties from Xie et al. (2023) relate to 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 if one of them moves apart from the other.Our monotonicity property generalizes this axiom.In this section, we revisit existing measures of diversity and show that typically used ones do not satisfy our requirements. 2 N (N -1) i̸ =j D(G i , G j ) SumAverage 1 N i̸ =j D(G i , G j ) Diameter max i̸ =j D(G i , G j ) SumDiameter i max j̸ =i D(G i , G j ) Bottleneck min i̸ =j D(G i , G j ) SumBottleneck i min j̸ =i D(G i , G j ) #Circles(t), t ≥ 0 max C⊆[N ] |C| s.t. D(G i , G j ) > t ∀ i ̸ = j ∈ C Vendi Score exp - N i=1 λ i log(λ i )Table 3 lists diversity measures discussed in previous studies (Xie et al., 2023; Friedman and Dieng, 2023) . Here we assume that S = {G 1 , . . . , G N }. There are six wellknown diversity measures defined over pairwise distances (Average, Diameter, and Bottleneck with two types of aggregation). Then, #Circles is the measure proposed in Xie et al. (2023) that also depends on the pairwise distances. Finally, Vendi Score is proposed in Friedman and Dieng (2023) and it is defined in terms of the pairwise kernels. We give the complete definition of Vendi Score below.Theorem A.1. Among the previously used measures listed in Table 3 , monotonicity is satisfied only by Average and SumAverage, while Uniqueness is satisfied only by Bottleneck.Proof. For each measure, we check whether it satisfies monotonicity and uniqueness defined in Section 2.Average 2 N (N -1) i̸ =j D(G i , G j )The monotonicity property is obviously satisfied.We prove that uniqueness is not satisfied by the following example. Consider a multiset consisting of four different values: {0, 10, 11, 12}. The distances between the values are induced from the real line. The diversity of this set is 2 4•3 (10 + 11 + 12 + 1 + 2 + 1) = 37 6 . If we replace 10 by the second copy of 0, we get a multiset {0, 0, 11, 12} with a larger value of diversity 2 4•3 (0 +11 +12 + 11+ 12 +1) = 47 6 .SumAverage1 N i̸ =j D(G i , G j )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 maxi̸ =j D(G i , G j )We prove that monotonicity is not satisfied by the following example. Consider one multiset with three elements and pairwise distances 10, 7, 4 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 to 10.To show that uniqueness is not satisfied, we consider the following example. Take a 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 is 2. If we replace 1 with the second copy of 0, we get a multiset {0, 0, 2} with the same diversity 2.SumDiameter i max j̸ =i D(G i , G j )We prove that monotonicity is not satisfied by the following example. Consider one multiset with three elements and pairwise distances 10, 7, 4 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 to 10 + 10 + 7 = 27.We prove that uniqueness is not satisfied by the following example. Consider a 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 is 2 + 2 + 1 = 5. If we replace 1 with the second copy of 0, we get a multiset {0, 0, 2} with larger diversity 2 + 2 + 2 = 6.Bottleneck mini̸ =j D(G i , G j )To show that monotonicity is violated, consider a multiset consisting of three different elements: {0, 1, 5}. The distances between the elements are induced from the real line. The diversity of this set is 1. Monotonicity requires the set {0, 1, 6} to have larger diversity. But the diversity of the set {0, 1, 6} is also equal to 1.Uniqueness is satisfied. Indeed, any multiset with pairwise different elements has diversity greater than 0, and any multiset with two copies of one element has diversity 0.SumBottleneck i min j̸ =i D(G i , G j )To show that monotonicity is violated, consider a multiset consisting of four different elements: {0, 1, 5, 6}. The distances between the elements are induced from the real line. The diversity of this set is 1 + 1 + 1 + 1 = 4. Monotonicity requires the set {0, 1, 7, 8} to have larger diversity. But the diversity of the set {0, 1, 7, 8} is also equal to 1 + 1 + 1 + 1 = 4.We prove that uniqueness is not satisfied by the following example. Consider a 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 + 1 = 4. If we replace 1 with the second copy of 9, we get a multiset {0, 9, 9, 10} with larger diversity 9 + 0 + 0 + 1 = 10.#Circles(t) maxC⊆[N ] |C| s.t. D(G i , G j ) > t ∀ i ̸ = j ∈ CWe prove that monotonicity is not satisfied by the following example. Consider one multiset with three elements and pairwise distances 10, 7, 4 and another multiset with tree elements and pairwise distances 10, 8, 4. Monotonicity requires the second set to have larger diversity, but: for t < 4 the diversity of both sets is equal to 3; for 4 ≤ t < 10 the diversity of both sets is equal to 2; for 10 ≤ t the diversity of both sets is equal to 1. Now, we fix t and prove that uniqueness is not satisfied by the following example. Consider a multiset consisting of three different elements: {0, t 2 , t}. The distances between the elements are induced from the real line. The diversity of this set is 2. If we replace t 2 by the second copy of 0, we get a multiset {0, 0, t} with the same diversity 2.Vendi Score exp -N i=1 λ i log(λ i )First, let us give a formal definition of this measure.Definition A.2 (Vendi Score, Friedman and Dieng ( 2023)). Let S = {G 1 , . . . , G N } be a multiset and let k : S × S → R be a similarity function, such that ∀i : k(G i , G i ) = 1 and the matrix K ∈ R N ×N defined by K i,j := k(G i , G j ) is positive-semidefinite and symmetric. Denote by λ 1 , . . . λ N the eigenvalues of the matrix K/N . Then, the Vendi Score is defined as the exponential of the Shannon entropy of the eigenvalues of K/N :EQUATIONwhere we use the convention 0 log 0 = 0.Our monotonicity property uses distances instead of similarities, but we can naturally reformulate it in terms of pairwise similarities by replacing the conditionD(G i , G j ) ≤ D(g(G i ), g(G j )) with the condition k(G i , G j ) ≥ k(g(G i ), g(G j)). Our uniqueness does not use the notion of distance, so we 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 positivesemidefinite symmetric matrices:EQUATIONMonotonicity requires K 1 to have higher diversity than K 2 . But Vendi Score of K 1 is 2.203 and Vendi Score of K 2 is 2.212 > 2.203.To show that uniqueness is not satisfied, consider the following example. Take two positivesemidefinite symmetric matrices:K 1 =1 0.6 0.2 0.6 1 0.9 0.2 0.9 1, K 2 = 1 1 0.2 1 1 0.2 0.2 0.2 1 (8)If Vendi Score has uniqueness property, then K 1 must have higher diversity than K 2 . But the Vendi Score of K 1 is 1.81 and Vendi Score of K 2 is 1.86 > 1.81.To illustrate the effect of γ, let us consider a simple setup when points are distributed in a square. We place 50 points uniformly at random in a unit square and optimize Energy for γ = 0.1, 0.3, 0.5, 1, 2, 3, 10. The results are shown in Figure 6 . Clearly, for small γ the coverage of the non-boundary region is not sufficient. However, for larger values (including γ = 1) the distribution looks sufficiently diverse. When two elements of a set get closer to each other, Energy can become arbitrarily large. Such behavior can cause some interpretability problems when we compare the obtained Energy for different algorithms. In terms of the desirable properties, the issue is that both monotonicity and uniqueness can be violated if not all elements are different. However, it turns out that if one requires monotonicity and uniqueness to be satisfied even when some elements coincide, then it becomes very challenging to construct a 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 in practice. Whether there exists a computationally feasible measure satisfying all the properties is currently unknown. Thus, we have chosen Energy as 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 configurations that are not sufficiently diverse, but it can be used to compare algorithms that optimize diversity. Also, recall that for numerical stability, we add a small constant to the denominator of Energy, so it does not go to 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 as a function that is optimized by an algorithm since it can lead to degenerate solutions. That is why we only use it as an assistive measure and apply it to the sets of graphs obtained by optimizing other objectives.In this section, we describe the graph distances that we use in our experiments.NetLSD (Tsitsulin et al., 2018) NetLSD treats a graph as a dynamic system and simulates heat and wave diffusion processes on nodes and edges of a given graph, followed by measuring system conditions at fixed timestamps. More formally, let λ j be the j-th smallest eigenvalue of the normalized Laplacian of a graph G. For a timestamp t, we define heat trace h t and wave trace w t of a graph G as follows:EQUATIONHere t > 0 for the heat trace and t ∈ [0, 2π) for the wave trace.Then, the heat trace signature and wave trace signature of G are defined as the collections of the corresponding traces at different timestamps, i.e., h(G) = {h t } t∈T h and w(G) = {w t } t∈Tw . As in the original article, we use 250 log-spaced timestamps between 10 -2 and 10 2 for T h and 250 equally-spaced timestamps between 0 and 2π for T w , respectively.Finally, the NetLSD distance (heat or wave) between two graphs G and G ′ is computed as any distance measure between the corresponding signatures. Following Tsitsulin et al. (2018) , we use the Euclidean distance.Graphlet Correlation Distance (GCD) (Yaveroglu et al., 2014) Graphlet Correlation Distance computes the distance between two graphs based on their graphlet statistics. Here graphlets are defined as connected graphs with 2, 3, or 4 nodes, with one of them marked. There are exactly 15 such graphs.Consider any graph G with n nodes. Choose any node v ∈ 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 v and all graphlets, we get 15 numbers corresponding to v. These numbers are not independent: if we know the counts for some graphlets, we can find the counts for some other graphlets. Getting rid of 4 redundant counts, we are left with 11 values (and the corresponding graphlets). So now we 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 × 11 Graphlet Correlation Matrix (GCM) as follows. The cell (i, j) of GCM contains Spearman's correlation coefficient between i-th and j-th columns of the matrix L. In other words, this cell contains the correlation between the number of times a node is a 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:EQUATION)Portrait Divergence (Bagrow and Bollt, 2019) The network portrait (Bagrow et al., 2008) of a graph G is a matrix B with elements b lk being the number of such nodes v that there are exactly k nodes at a distance l 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 of nodes at a distance l from each other and that the first node has k nodes at a distance l from it:EQUATIONwhere c n 2 c is the normalization over the sizes n c of the connected components. Then, the portrait divergence between two graphs G and G ′ is computed as the Jensen-Shannon divergence of the distributions P B(G) (k, l) and P B(G ′ ) (k, l).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} ∪ S can be written as Diversity({G} ∪ S) = g(f (G, S), c(S)), where g is a function that is monotone w.r.t. its arguments. The function f (G, S) is called fitness of a graph G w.r.t. a set of graphs S.The code of our experiments is publicly available at https://github.com/Abusagit/ Challenges-on-generating-structurally-diverse-graphs.Algorithm Assume that we are given a pre-generated set Ŝ of M graphs with diverse structural properties, M ≫ N . Let S be our constructed set of diverse graphs which is initially an empty set.Then, our greedy algorithm consists of N steps. We start with S = ∅ and at the first step we select a graph from the set Ŝ uniformly at random to be the first element in S. At each subsequent step, we choose G ∈ Ŝ with the maximal value of the fitness f (G, S). Then, we add this graph G to the set S.After N steps, we get a set S of size N , which is our approximation of the maximally diverse set.Analysis While being very simple, the greedy algorithm turns out to be very effective when supplied with a sufficiently diverse set Ŝ. 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. Proof. Let us prove the statement for each of the diversity measures.Average Suppose maxG1,G2∈ Ŝ D(G 1 , G 2 ) = d and this maximum is achieved for G 1 = V 1 , G 2 = V 2 for some V 1 , V 2 ∈ Ŝ.Since all pairwise distances between the elements of S ⊂ Ŝ are less than or equal to d, the average pairwise distance between the elements of S is also less than or equal to d. That is, Diversity( S) ≤ d. Therefore, to prove the theorem it is sufficient to prove that for the greedily picked S we have Diversity(S) ≥ d2 . We prove it by induction on N , which is the size of the set S. The base case N = 2 is trivial, since for every element there exists a 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 a element). Inductive step. Suppose the induction statement holds for N = k. Let us prove it for N = k + 1. Suppose the greedy algorithm picked graphs A 1 , . . . , A k , A k+1 in this order. We need to prove that the average pairwise distance between A 1 , . . . , A k , A k+1 is at least d 2 . By induction hypothesis, the average pairwise distance between A 1 , . . . , A k is at least d 2 . So, it is sufficient to prove that the average distance between A k+1 and A 1 , . . . , A k is at least d 2 . This is equivalent tok i=1 D(A i , A k+1 ) ≥ kd 2 .By the triangle inequality, we haveD(A i , V 1 ) + D(A i , V 2 ) ≥ D(V 1 , V 2 ) = d for all 1 ≤ i ≤ k.Summing these inequalities for all i, we getk i=1 D(A i , V 1 ) + k i=1 D(A i , V 2 ) ≥ kd, therefore k i=1 D(A i , V 1 ) ≥ kd 2 or k i=1 D(A i , V 2 ) ≥ kd 2 .Thus, by the construction of the greedy algorithm, we havek i=1 D(A i , A k+1 ) ≥ kd 2 .Bottleneck Suppose S = C 1 , . . . , C N and Diversity( S) = m. Suppose the greedy algorithm has already made k < N steps choosing graphs A 1 , . . . , A k , and the diversity of A 1 , . . . , A k is at leastm 2 .We define an open ball with center in G ∈ Ŝ and radius r as the set of all graphs in Ŝ such that their distance to G is less than r. Consider N open balls with centers in C 1 , . . . , C N and radius m 2 . Clearly, these balls do not intersect. Since k < N , there is at least one of N balls that does not contain any of A 1 , . . . , A k . Therefore, the distance from the center of this ball to all A 1 , . . . , A k is at least m 2 . Thus, the greedy algorithm can make one more step while still preserving the diversity of the chosen set not less than m 2 . Since we prove it for all k < N , the diversity of the greedy algorithm result on step N will be at least m 2 = 1 2 Diversity( S).Energy We prove that Diversity(S) ≥ 2 γ Diversity( S) by induction on N , which is the size of the set S. The base case N = 2 is trivial, since for every element there exists a 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 a element).Inductive step. Suppose the statement holds for N = k. Let us prove it for N = k + 1. Suppose the greedy algorithm made k steps and picked graphs A 1 , . . . , A k in this order. Suppose S = C 1 , . . . , C k+1 . We pair A 1 with the nearest graph from the set S (ties break randomly), w.l.o.g. we assume that this graph is C 1 . We pair A 2 with the nearest graph from the set S \ {C 1 }, w.l.o.g. we assume that this graph is C 2 . We pair C 3 with the nearest graph from the set S \ {C 1 , C 2 }, w.l.o.g. we assume that this graph is C 3 , etc. Note that the graph C k+1 is left unpaired. Let us prove that Diversity({A 1 , . . . , A k , C k+1 }) ≥ 2 γ Diversity( S), from which the statement of the theorem follows trivially.By the induction hypothesis, we haveDiversity({A 1 , . . . , A k }) ≥ 2 γ Diversity({C 1 , . . . , C k }). So, it is sufficient to prove that - k i=1 1 D(Ai,C k+1 ) γ ≤ -2 γ k i=1 1 D(Ci,C k+1 ) which is equivalent to k i=1 1 D(Ai,C k+1 ) γ ≥ 2 γ k i=1 1 D(Ci,C k+1 ) γ . Given that γ > 0, this inequality holds if we prove that 1 D(Ai,C k+1 ) ≥ 2 1 D(Ci,C k+1 )for every i. Rewriting the last inequality, we get D(C i , C k+1 ) ≤ 2D(A i , C k+1 ). This inequality holds since:D(C i , C k+1 ) ≤ D(C i , A i ) + D(A i , C k+1 ) ≤ 2D(A i , C k+1 ).Here the first inequality is the triangle inequality. The second inequality follows from the pairing construction which ensures that D(C i , A i ) is less than or equal to D(A i , C k+1 ). Now, let us analyze the time complexity of the greedy algorithm. Here and below, we assume that computing a graph representation for a distance D for a graph with n nodes requires a 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. 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 Ŝ, 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(bM ) operations. Using the computed distances, we update the current fitness for all graphs in O(M ) operations. The choice of an element that we add to S can be done in O(M ) operations. So, each step requires O(bM ) operations. Given that we have N steps, the resulting time complexity of the algorithm is O(aM+ bM N ) = O((a + bN )M ).Generating the set Ŝ Generating a sufficiently diverse set Ŝ is a necessary ingredient of the success of the greedy algorithm. To generate such a set, we use several random graph models with different 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 Ŝ.All models below generate graphs with a fixed number of nodes n. In our experiments, we take n = 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 a sample of graphs, we generate an (approximately) equal number of graphs for each combination of a model and its parameters.Erdős-Rényi In this model, each edge is included in the generated graph with probability p, independently from all other edges. We consider p ∈ 1 16 , 1 8 , 1 4 , 1 2 , 3 4 , 7 8 , 15 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 m reflects the number of outgoing edges added together with each new node. The probability that a new node is attached to an older node i is proportional to k i + α, where k i is the number of incoming edges of i and α > 0 is a parameter reflecting the attractiveness of nodes with zero incoming degrees.We consider m ∈ {1, 2, 4} and α ∈ {m/2, m, 2m}. Such values of α give the power-law degree distribution with parameters γ ∈ {2.5, 3, 4} (Ostroumova et al., 2013) .Holme-Kim (Holme and Kim, 2002) This is a modification of the preferential attachment model, allowing for varying the number of triangles. Again, nodes are added one by one; each node appears with m edges. Edges are also added one by one, and there are two types of edges: random and triangle-forming. Random edges connect the new node with an old one with probability proportional to 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 a neighbor of the previously chosen node and connect the new node to this neighbor.In our experiments, we take m ∈ {2, 4} and p ∈ {0.5, 1}.Random graph with power-law expected degree sequence (Chung and Lu, 2002) First, we sample a sequence W = (w 1 , . . . , w n ) from a power-law distribution with parameter γ. Then, we construct a graph by connecting the nodes i and j with probabilitywiwj k w k .Here we use γ ∈ {2, 2.5, 3, 4}.Random geometric graph (Penrose, 2003) First, n nodes are placed uniformly at random in the unit cube in R d . Then, two nodes are joined by an edge if the distance between them is at most r.We take d ∈ {2, 3}, where for d = 2 we have r ∈ {0.2, 0.3, 0.5} and for d = 3 we have r ∈ {1/3, 0.5, 0.65}.Random regular graph This model generates a random graph, each node of which has degree d.We consider d ∈ {1, 2, 4, 8, 10}.Stochastic block model (Holland et al., 1983) We divide n nodes into r sets (blocks) of (approximately) 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 q, independently from all other edges.In the experiments, we use r = 2 and r = 3. For r = 2, we use all combinations of pairs (p, q) from the set {(2s, s)EQUATION.Our implementations are based on NetworkX and igraph Python libraries.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 a 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 P 1 and P 2 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 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 it 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 of the algorithm in detail.For an initial set of graphs, we 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 or with mixed p) or can pass an already saved set of graphs through command-line 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, . . . , n (we will need these labels for the crossover procedure). Denote the generated population by S.Selecting parents We randomly select two different graphs from S as parents. To do so, we 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. 4 We denote these graphs by P 1 and P 2 .Figure 8 : Graphs from IGGM with Portrait-divCrossover Given the graphs P 1 and P 2 , we construct a new child graph C. Informally, we want C to copy some nodes and edges from P 1 and some nodes and edges from P 2 . For each label from 1 to n, we randomly and independently assign a number 1 or 2 with equal probability. If a label i has been assigned 1, then the node i is copied from P 1 , and otherwise it is copied from P 2 . After that, for each pair of nodes i < j, we determine whether C has an edge between i and j as follows:• if i was assigned 1 and j was assigned 1, then C has an edge between i and j iff P 1 has an edge between i and j;• if i was assigned 2 and j was assigned 2, then C has an edge between i and j iff P 2 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 i and j iff the selected parent has an edge between i and j.Mutation We follow Ipsen and Mikhailov (2002) and perform mutations as follows. Given a graph C, with probability α we construct a mutated graph C ′ . First, we choose a node from C uniformly at random and delete all edges connected to it. Then, we select a number k ∈ {1, 2, . . . , n -1} 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 Update We check each graph from the population and try to replace it with C ′ . By U we denote the graph giving the largest improvement after the replacement. If f (U, S \ U ) < f (C ′ , S \ U ), then we remove U from S, add C ′ to S, and call C ′ a successful child. Otherwise, C ′ is called unsuccessful, and the population S remains unchanged. Note that this procedure does not decrease the diversity of the population and keeps the size of the population equal to N .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, we accept the candidate C ′ k among the last K with the maximum value of f(C ′ k , S \ U ) -f (U, S \ U ) and replace U by C ′ k in S.Since the added child is unsuccessful, it 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. The time complexity of generating the initial population and calculating the fitness for all its elements is small in comparison with O((a + bN )L), so it does not influence the time complexity of the algorithm (given that L ≫ N ). Then, we do the following:1. At each iteration, choose a graph with probability inversely proportional to its fitness 5 and denote this graph by U .2. Pick two distinct nodes u and v from U uniformly at random. If an edge (u, v) exists in U , remove it. Otherwise, add (u, v) to the edge list of U . Using this atomic operation, we obtain a changed graph U ′ .3. Compute the fitness f (U ′ , S \ U ).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. It is not strictly required but assumed that L is divisible by K. Another parameter of the algorithm is R < K: R graphs are used to train each graph generative model. In our experiments, we set R = 10 3 , K = 10 5 , L = 10 6 .To obtain the initial set of graphs to train a generative model on, we do the following: we generate a set of 10R graphs from ER-mix and then apply the Greedy algorithm on that set, obtaining R initial graphs, which we denote S 0 and start the process.At each step t, we train a generative neural network g θt on the graphs obtained from the previous step S t-1 ; the notation θ t represents trainable parameters of the model at step t. Then, we use g θt as a fixed random graph generator to create K ≫ R graphs and apply the Greedy algorithm to choose R diverse graphs that will form the next training input. In our experiments, for g θt we use Discrete Denoising Diffusion model DiGress (Vignac et al., 2023) , which is distributed under the MIT License, with its default parameters (including model hyperparameters and training routine) to generate graphs.As a result, our procedure consists of L K steps, where at each step 1 ≤ t ≤ L K we do: 1. Train generative model g θt on the set of graphs S t-1 , initial weights are taken from the last weights of the previous iteration; 2. Generate K graphs using g θt ; 3. Apply the greedy algorithm to the generated set of graphs to obtain R graphs, denote this set by S t .Note that after each iteration, we can greedily choose N graphs from S t 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 a lot. We used the default parameters of DiGress as a proof of concept.GraphWorld 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], num_communities from {1, 2, 3, 4, 5}, avg_node_degree form [4, n -1], power_exponent from [0.5, 1).The experiments have been conducted on the machine with Intel Core i7-7800X @3.50GHz CPU, 2×NVIDIA GeForce RTX 2080 Ti GPUs and 126G RAM. It took us approximately 500 CPU hours to conduct all the experiments.Examples of generated graphs Examples of generated graphs are shown in . 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.Visualizing graph characteristics Figure 12 visualizes various characteristics of generated graphs for the ER-mix and GraphWorld baselines, IGGM, and the combination of Greedy, Genetic, and LocalOpt. It extends Figure 4 from the main text.Extended numerical results Table 4 extends the results from Table 1 and also reports the standard deviation based on five independent trials.38th Conference on Neural Information Processing Systems (NeurIPS 2024).In this work, we use the terms 'diversity' and 'coverage' interchangeably.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.We illustrate the effect of γ on the obtained diverse configurations in Appendix A.3.Since Energy is negative, for this measure we sample with probabilities proportional to -1 fitness .For Energy, we sample with probabilities proportional to -fitness. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The novelty of this paper should be better stressed, especially for the framework of measuring the diversity via energy.

2. 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.
questions: questions: N.A.
limitations: limitations: Please refer to Limitations.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: - the problem is still unsolved
- since there's not much work, there aren't obvious benchmarks to beat
- I have some doubts about the scalability (and therefore practicality) of the presented solution
- 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
questions: 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?

2.  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: limitations: Yes
paper_summary: paper_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.
Towards this, the authors first propose a new way to measure graph diversity based on the idea of energy(combined with several graph distances).
They describe several algorithms for generating diverse graphs, namely greedy, genetic based and  local optimization, and neural -based.

The 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.
strength_weakness: strength_weakness: 1. It is not clear to me whether there is a data distribution which is learned.

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?

3. What is the usage of diversity without fidelity metrics: such as structural similarity between 2 datasets( training and generated)?

Eg : see https://arxiv.org/abs/2001.08184
GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation.
See diversity and fidelity section.
questions: questions: Please see weakness.

I am mostly concerned on the application of the proposed work. How does one use it? 

Is it possible to model some data distribution+ with diversity?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

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.

W3. 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).
questions: questions: Please address W1, W2, W3 above. Additional minor comments:

- First paragraph of the introduction would benefit from citations
- L38: use `\citep` instead
- Another "classic" work relevant to the discussion on encoding structural information based on the graph Laplacian (L123) is [1].
- L175: I'd avoid using $g$ to denote the bijection
- Typos: GraphWold (L313), "graphs graphs" (Fig 3 caption)

[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: Limitations are adequately discussed.

Comments: title: Post-discussion summary
Experiments on larger graphs
Thanks
comment: We would like to thank all the reviewers for the productive discussion and positive feedback! This discussion helped us to improve the paper.

Following the suggestions, we’ve extended our discussion of scalability, added more experiments with larger graphs, and added some experiments that illustrate practical applications of diverse graphs.

We would like to conclude with some of our thoughts regarding the problem addressed in our work. The task of generating diverse graphs turns out to be a challenging problem. The challenges start with defining diversity for a set of graphs since even defining pairwise graph distance is a long-standing unsolved problem. Then, one needs to develop algorithms for the task since standard approaches cannot be directly applied. In our paper, we made the first steps to addressing these challenges. We are personally very encouraged by the obtained results. In particular, Figure 3 in the paper (and Figures 7-8 in Appendix) show that the proposed approaches allow one to generate visually nice structurally diverse graphs even when starting from simple Erdős–Rényi graphs. We hope that our work will stimulate further research in this field.
As promised above, we conducted some additional experiments for graphs on 1000 nodes. Here, when we optimize diversity, we use either GCD or NetLSD as a graph distance (as Portrait-Div is significantly slower). We analyze Genetic starting from GraphWorld. Since sufficiently diverse starting set is important for faster convergence, for GraphWorld we vary all its parameters to increase diversity of the starting sample. The obtained learning curves can be found in our code repository in `/figures` folder. These curves show how the diversity measure improves with iterations. Several conclusion can be made. First, diversity significantly increases. Second, one can see that the algorithms converge relatively fast, especially for the NetLSD graph distance. This confirms that Genetic has a good potential for scalability.
Thanks to the authors for addressing my comments.  I am raising my score.
Thanks a lot for your involvement in the discussion!

**Regarding W1**, we are happy to hear that you find the experiment promising. We plan to extend this experiment in the revised version as follows: consider the diverse graphs generated based on different graph distances (in our case - Portrait-Div, NetLSD, GCD). Then, we can evaluate various algorithms from the CLRS benchmark on these diverse sets. We expect that diverse sets are more challenging compared to the standard test sets (as shown above for Portrait-Div), but it would also be interesting to see which graph distance leads to more challenging graphs for a particular algorithm. This will give us more insights into graph distances and provide more challenging diverse sets for particular algorithms.

**Regarding W3**, we agree that it is an important issue, so let us elaborate on this challenge (and we will add this discussion to the revised version).

When scaling to significantly larger graphs, there are two aspects that one should consider: the computation cost of the chosen graph distance and the speed of convergence of the algorithm.

Regarding graph distances, their computation cost may vary significantly. For instance, there are simple graph distances based on node degrees which can be easily computed but are less expressive, while some more advanced ones are based on optimal node matching which becomes infeasible even for moderate-size graphs. Among the distances we consider in the paper, the NetLSD implementation turns out to be the fastest. Importantly, most graph distances first compute descriptors of graphs and then measure the distance (e.g., Euclidean) between these descriptors. For better scalability, we suggest using graph distances of this type since in this case we can compute the descriptor for each graph only once and then use it for all distance measurements which significantly reduces the costs.

Regarding the convergence of the algorithm (in terms of the number of graphs we are allowed to try), this issue is more tricky: the number of possible graph structures grows extremely fast with the number of nodes and thus one cannot hope to explore the whole space via simple bruteforce. Thus, the ability to scale significantly depends on the particular algorithm used.
Let us revisit the algorithms considered in the paper and discuss their potential ability to scale.
- **Greedy**. This algorithm is scalable: assuming that we pre-computed all graph descriptors, the complexity of this algorithm does not depend on the sizes of graphs. Moreover, it is easily parallelizable. However, the success of Greedy critically relies on the initial set. In the paper, we apply this algorithm to a set of graphs generated by diverse generators with different parameters. While this requires a hand-crafted list of models, the solution is very scalable: most random graph generators easily scale to large graphs. If we have a diverse set of graph generators, the greedy algorithm is a very promising model to consider.
- **Local optimization**. This approach is not scalable: it operates with small graph modifications and thus cannot effectively explore the space of all graphs. We find this algorithm suitable for the final tuning of graphs if they are already diverse. A possible way to improve the scalability of LocalOpt is to also allow larger graph modifications, especially in the early steps of the algorithm (e.g., replacing a subgraph instead of changing only one edge).
- **Genetic**. We find this algorithm promising for exploring the space of graphs since its operations (crossovers and mutations) often lead to graphs that significantly differ from the parent graphs. Additionally, we suggest incorporating stochasticity into this algorithm by sampling pairs for fitness calculations instead of evaluating all pairs. This approach could accelerate convergence by allowing more steps within the same timeframe. Finally, in our preliminary experiments on larger graphs, we noticed that Genetic works significantly better when starting with a sufficiently diverse set of graphs.
- **IGGM**. The efficiency of IGGM significantly depends on the efficiency of the underlying generative model. Thus, scaling IGGM to large graphs depends on the future development of efficient GGMs, which lies beyond the scope of this paper. But if we assume that the generative model is sufficiently cheap, IGGM is expected to scale to large graphs, similarly to the greedy algorithm discussed above.

Overall, we are working on these strategies to enhance the scalability of our framework and appreciate the reviewer's insights on this matter.

Additionally, we’ve launched more experiments with graphs on 1000 nodes to analyze how scalable are some of the approaches. Due to the limited discussion period, we don't consider larger graphs, but $n = 1000$ is already significantly larger than $n = 16$ used in most of our experiments. We plan to add the results before the end of the discussion period.
Many thanks for engaging with the points I raised.

W1. The scope of the work is not externally defined but wholly under your control. My point is that if the design of study went "deeper" into examining performance on some graph ML tasks instead of "broader" by only looking at how to generate diverse graphs, it would (in my opinion) make for a more compelling set of results. The preliminary experiments do look promising and "close the loop" on your motivating use cases.

W2. Just to clarify, this is not a criterion that I am using to penalise the work. My main point is that, in a similar vein to W1, the fit to the conference would be substantially easier to justify if some graph learning tasks were considered. The study is also fairly clearly not a theoretical one.

W3. Acknowledging the scalability weakness of the work is a step forward, but nevertheless the authors do not provide ways to address it, or indeed frame the problem in such a way that the techniques would be easy to scale up.

I am raising my score to a 4 as a result of the discussion: while the paper has some merits, I still err on the side of rejection due to its weaknesses.
I thank the authors for their answer. I increase my score.