CoRe-GD: A Hierarchical Framework for Scalable Graph Visualization with GNNs

Thanks for taking the time to review our paper. We are addressing the weaknesses as follows:

The motivation of the hierarchical optimization and positional rewiring is not clearly introduced. I would recommend the authors discuss the computational complexity among the proposed CoReGD, DeepGD, and SmartGD. In addition, the authors should introduce why positional rewiring is important in hierarchical optimization.

Thanks for the suggestion. We added Table 3 and a small paragraph to introduce the baselines and their computational complexity. We also improved Section 3 and now point out more clearly why the positional rewiring is useful.

I found it a bit hard to follow the method section. A diagram of the whole algorithm should be carefully introduced in this section, which can make the readers clearer to the proposed algorithm before diving into the details. It is difficult to understand the pipeline of CoReGD from Figure 2, e.g., h_1^1, h_1^l, h_1^{c+1}.

We admit that Figure 2 could have been better for introducing the algorithm. We updated the manuscript and combined Figure 2 and 3 to serve the purpose you mentioned. We also added textual descriptions to make the overview more clear.
The embeddings h_1^1, etc., are part of the figure as they also appear in the pseudocode in Appendix A.2. This makes it possible to align both the figure and the pseudocode to better understand how embeddings are passed exactly between modules.

I find the effectiveness of the proposed hierarchical optimization in Table 2 and Figure 6. However, the proposed positional rewiring, scale-invariant stress, and replay buffer do not make a significant impact on the stress metric from A.3 Table 3.

Only looking at A.3 Table 3 might not show a big numerical difference in the ablation, but one has to keep in mind that the reported values are for an optimization problem that gets increasingly harder the closer one gets to the optimum. Referring back to Table 1 (which shows the base setup for the ablation study), we fall behind several other algorithms without positional rewiring, scale-invariant stress, or replay buffer. The numerical differences might seem small at first glance (for example, 236.65 instead of 233.17 without the replay buffer), but sgd^2 (233.49) and DeepGD (235.22) would be better without it. It is unclear where the optimum on the Rome dataset lies, but these components of our method are getting closer and closer to it.

More graph drawing quality metrics can be reported, such as shape-based metrics and edge crossing.

We want to clarify that our framework is optimizing stress, and the positional rewiring is partly based on that assumption. Therefore, this is arguably the metric that needs to be used in the comparisons. However, optimizing other metrics could be interesting for future work.

In conclusion, we address the mentioned weaknesses in the new revision of the paper, especially with the changes in Section 3. We would be very grateful if you could have a look at these changes. If there are any other questions, we are of course happy to help and would otherwise be happy if you could consider raising your score.

Thank you for the review and the concrete proposals for improvements. We integrate them as follows:

W1. For the many readers unfamiliar with graph drawing benchmarks, it would be really helpful to have preliminaries as part of the main paper, and also discussions of the benchmarks to better understand the relative things being compared (I'd guess most GNN-familiar authors aren't familiar with graph drawing).

Thanks for the suggestion. This is a good point. In reality, there is no good standardized way of benchmarking algorithms for Graph Drawing, especially for neural methods. The closest we get is the Rome dataset, which was also used by previous work, but these graphs are rather small and only stem from one task/distribution. This is why we add more datasets, some used for GNN benchmarking, bigger real-world instances from the suitesparse matrix collection, and synthetically generated sparse graphs. This makes our evaluation more extensive than previous work. We added a section describing our contribution regarding benchmarking in Appendix A.7.4 that we invite you to read. Beyond that, the first paragraph of Section 4 gives an overview of the employed datasets and why they were used.

W2. An efficiency-stress curve would be great to understand relative runtimes and stress performances of the different methods in this landscape, as the authors' individual experiments suggest that CoreGD is the best performing and fastest.

We added plots in Appendix A.7.3 to show this. These show that CoRe-GD is indeed Pareto-optimal regarding runtime and layout quality.

3.1 suggests the efficiency and effectiveness for CoreGD is largely influenced by the input feature choice. Some of the features that offer high discriminability might be difficult/expensive to compute for large graphs (e.g. Laplacian PEs or beacons).

This is a good observation. First of all, we show that the features we use can be computed in sub-quadratic time. Of course, practical runtimes can still vary, but we want to point out that the computation for initial features only needs to be done for the coarsest graph, which we can bound by a maximum size (and thus assume to be constant). To back this up empirically, we compared both CoRe-GD with the coarsening hierarchy and without any coarsening in Figure 5. We can observe that for a graph size of around 12000, an inflection point is reached where the variant with coarsening becomes faster than the one without, exactly because the feature computation is becoming more and more expensive. As mention in the paper, this is one major advantage of the coarsening.

The random noise addition step in 3.2 is interesting: this would means the output drawing is stochastic, I guess. How sensitive are output drawing configurations to the noise introduced here?

Indeed, all presented algorithms used as baselines in the paper produce randomized results. For CoRe-GD, this is also the case because it uses randomized features for nodes. To judge the impact of different training runs and executions, we provide the standard variation for all results in the paper. We observe that they are rather small and comparable to the classical algorithms. To further underline this, we computed the mean and standard deviation using only one model for datasets (which we provide with the code) over 5 runs. The results are as follows:

We can observe that the standard deviation is similar to or lower than when using multiple trained models. So, on one hand, the training is relatively stable and produces similar results over different training runs, and on the other, the trained models themselves show little variation when used multiple times with different random seeds. We want to point out that the drawings can still look different in ways that do not affect stress, e.g., the graph could be rotated. This is usually not a problem in practice and something that applies to all other methods, too.

Dear authors,

Thanks for your detailed responses. In particular, I'm pleased to see the stress-runtime plots demonstrating the competitiveness of the method, and also the (significant) rework of Section 3 which helps clarity. I raised my score to a 6, which reflects my belief that this paper is above the bar. I did not increase further because of my assessment about the scope of the work and potential for interest at ICLR.

Best wishes,

-Reviewer Avgq

We want to thank the reviewer for their review and the questions they brought up. We address the two weaknesses/questions as follows:

Some training details are put in the appendix. I found that after reading the main body of the paper, I couldn't understand how the framework is applied for training and serving. I think the writing order of the paper needed to be improved. And the figure 2 is relatively hard to understand. Please give a more clear illustration about the graph after being processed by each module in your framework.

Thanks for the suggestion. We combined Figures 2 and 3 and gave them an overhaul with newly added textual descriptions and more depictions of the graph between the different processing steps to make them easier to understand. The writing in Section 3 has also been improved to make the execution clear. The main body now gives a clear overview of the algorithm, while detailed pseudocode for both training and inference is given in Appendix A.2.

Is this research related with graph condensation or graph summarization? I mean, maybe some baselines about graph condensation or summarizarion should be included if so.

Graph condensation and summarization (in the context of graph learning, we assume this is what you refer to, please correct us if we are wrong) are concerned with reducing the size of a graph while maintaining important information, usually based on label information and the graph structure. As a byproduct of the graph being reduced, this might lead to more pleasing layouts once visualized. On the other hand, the graph drawing task we are considering finds a stress-optimized spatial embedding for the original graph. These tasks are inherently different, and we do not see how a meaningful comparison with baselines for graph condensation and summarization to our method can be done. We could also not find more information on a further relation between graph drawing and condensation/summarization in the literature. If there is a comparison that you have in mind which would make sense for our task, then please let us know. Otherwise, if this was your main concern, then we would be happy if you would consider increasing your score.

We thank the reviewer for their honest review. We address the weaknesses as follows:

I am not heavily knowledgeable about the Graph Drawing community and am not fully aware of the larger impacts (if any) outside of visualizations. It seems to me like this might be a relatively niche community but would defer to other reviewers on that front.

We agree that the main relevance lies in graph visualization. However, we believe that the methods we employed (adaptive positional rewiring, replay buffer with latent embeddings for training deep GNNs, etc.) are interesting for the wider graph learning community and can be of relevance for tasks beyond graph visualization.

Otherwise, this is a pretty strong, high quality paper.

Thanks

Figure 6 seems to show that CGD does worse than neato and (sgd)2 for the larger graphs. This is a weakness given that CGD is designed with larger scale graphs in mind. neato and (sgd)2 do better on larger graphs and PivotMDS does almost as well on larger graphs but is much, much faster. This means CGD is only occupying a kind of middle ground on large graphs.

There is a tradeoff between running time and quality for all algorithms. CoRe-GD beats all neural methods regarding speed and quality and overall offers a unique tradeoff between quality and computation speed when compared to all algorithms. To make this more clear, we added scatterplots depicting the runtime and quality of the algorithms for graphs of the same size (graphs of different sizes cannot be easily compared due to different optimal stress values) in Appendix A 7.3. We can observe that CoRe-GD appears Pareto-optimal.

In addition, while I am not highly familiar with neato and (sgd)2, the fact that they are training free makes me believe they are less complex than CGD from an engineering perspective.

We are not 100% sure what you mean by "less complex" here, the strength of CoRe-GD is that it can be trained for different graph distributions without the necessity to adapt the employed heuristics of the algorithm (as they are learned and do not need human domain knowledge). One can easily retrain CoRe-GD with new graph distributions by using our existing code. This is not possible with the classical algorithms, where deliberate tuning of the heuristics is required to better fit a graph distribution. To demonstrate this adaptability, we use datasets from different domains in Table 1.

"For a cycle graph, this is clearly not desirable and will end in a drawing that is far from optimal." This is a good example. Would be good to have a visualization (maybe can go in appendix)

Thanks for the suggestion. For a cycle graph, this would lead to all nodes being positioned on the same point, which is clearly not stress optimal (as mentioned in the paper). We can add a visualization with a cycle graph and a single node representing the resulting drawing next to it, but we don't feel that this adds much to the paper. Is there another visualization that you have in mind?

Though I feel I understand it, a figure showing how the latent embeddings are transferred between supernodes and nodes in the uncoarsening step could be useful.

We generally improved the figure for the architecture by combining the old Figures 2 and 3. While doing so, we added more depictions of the graph while being processed (also one before and after the uncoarsening) and added more descriptions. We hope that this helps.

Why is DNN^2 excluded from figure 6?

The training of DNN^2 was extremely unstable and did not converge for bigger graphs (leading to huge losses). This is also why standard deviations for DNN^2 on the small datasets are by far the biggest. As the performance of DNN^2 is already severely lacking behind on small graphs, we do not see this as a significant problem. A remark on this is also contained in the paper.

Why does Figure 6.A cutoff at 5000 while 6.B cuts out at 25000?

The difference between plot 6.A and 6.B is that for 6.A, we have to compute losses, which is not necessary for 6.B (as it only measures inference runtimes). To compute the full stress loss, we have to compute all-pairs-shortest paths and compare them to the distance in the drawing. This becomes prohibitively costly in both runtime and memory requirements, which is why we had to cap the graph size for Figure 6.A. We also mention this in the paper.