Challenges of Generating Structurally Diverse Graphs

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.

Strengths

The primary strength of the work is that it is very systematic in the way that it approaches the problem. It does a thorough job of reviewing the ways in which graph distances and diversity of a set of graphs can be quantified; and the experiment results indeed achieve the main goal of optimizing structural diversity. The writing quality and clarity of the paper are also good.

Weaknesses

W1. In my opinion, the main weakness is that the work stops short of the main motivating use case of why generating diverse graphs is important. Namely, the work does not carry out an assessment of whether the generated diverse graphs actually improve performance for graph learning tasks (and to what extent; for what types of problems; which distance and diversity metrics are beneficial in practice, etc.). The paper in its current form reads like it is addressing only "half" of the motivating problem. 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

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.

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

Limitations are adequately discussed.

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.

Strengths

1. The paper propose an interesting problem of generating structurally diverse graphs and its importance in different fields such as evaluating graph neural networks and their expressive power etc. 2. The paper is easy to read. 3. The authors define an interesting idea of energy based functions for measuring diversity. 4. Empirical analysis shows better performance in comparison to baselines.

Weaknesses

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

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?

Rating

5

Confidence

3

Soundness

2

Presentation

3

Contribution

2

Limitations

Yes

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.

Strengths

+ topic is important and understudied + excellent presentation + interesting experimental results

Weaknesses

- 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

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.

Rating

7

Confidence

5

Soundness

4

Presentation

4

Contribution

4

Limitations

Yes

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.

Strengths

1. This paper is well motivated, and the generation of diverse graphs is a good domain for research. 2. This paper is well written and the idea is easy to follow. 3. The experiment results are sound.

Weaknesses

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

N.A.

Rating

5

Confidence

2

Soundness

3

Presentation

2

Contribution

2

Limitations

Please refer to Limitations.

Thanks

I thank the authors for their answer. I increase my score.

Post-discussion summary

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.