Challenges of Generating Structurally Diverse Graphs

Thank you for your review! We address the questions and concerns below.

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.).

In 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.

We 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):

We 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.

While 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.

However, we believe that investigating particular applications should be the topic of a separate study.

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.

We 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.

From 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.

Also, 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.

We are open to further discussions on whether papers of such kind are suitable for NeurIPS.

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).

We 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.

Let 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.

We 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}$).

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

Thank 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.

Thank you for the writing suggestions, we will improve the text accordingly.

[1] P. Veličković et al. The CLRS algorithmic reasoning benchmark. ICML 2022.

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.

Thank you for your constructive comments and positive feedback! Let us address the weaknesses and questions.

the problem is still unsolved

We 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.

since there's not much work, there aren't obvious benchmarks to beat

Indeed, 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.

I have some doubts about the scalability (and therefore practicality) of the presented solution

We 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.

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?

The 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).

However, 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.

We 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.

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.

Thanks 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.

As 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.

[1] S. Agarwal et al. Contextual diversity for active learning. ECCV 2020.

[2] Y. Yang et al. Multi-class active learning by uncertainty sampling with diversity maximization. IJCV 2015.

[3] Y. Geifman et al. Deep active learning over the long tail. 2017.

We are open to further discussions!

Thanks to the authors for addressing my comments. I am raising my score.

Thank you for your review! We address the questions and concerns below.

1. It is not clear to me whether there is a data distribution which is learned.

One 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.

If 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.

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?

As 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?

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

As explained above, we do not have training data, so there is no possible comparison of structural similarity between training and generated datasets.

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

The 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:

• analyzing the performance of a graph algorithm;
• estimating how well a heuristic algorithm approximates the true solution for a graph problem;
• evaluating neural approximations of graph algorithms;
• training neural approximations of graph algorithms to improve their robustness and generalizability;
• evaluating graph neural networks and their expressive power.

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.

Is it possible to model some data distribution+ with diversity?

Yes, 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.

We hope that our responses address the raised questions and we are open to further discussions.

Thank you for your review and positive assessment of our work! We address the weaknesses below.

W1. The novelty of this paper should be better stressed, especially for the framework of measuring the diversity via energy.

To 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.

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.

We 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.

We 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.