CoRe-GD: A Hierarchical Framework for Scalable Graph Visualization with GNNs
Authors: Florian Grötschla
Joël Mathys
Robert Veres
Roger Wattenhofer
Venue: ICLR 2024 poster (2024)
Keywords: Graph Visualization
Optimization
Scalability
Graph Neural Networks
Primary area: general machine learning (i.e., none of the above)
TL;DR: We present CoRe-GD, a scalable GNN-based graph visualization framework using hierarchical coarsenings and positional rewiring.

Abstract: Graph Visualization, also known as Graph Drawing, aims to find geometric embeddings of graphs that optimize certain criteria. Stress is a widely used metric; stress is minimized when every pair of nodes is positioned at their shortest path distance. However, stress optimization presents computational challenges due to its inherent complexity and is usually solved using heuristics in practice. We introduce a scalable Graph Neural Network (GNN) based Graph Drawing framework with sub-quadratic runtime that can learn to optimize stress. Inspired by classical stress optimization techniques and force-directed layout algorithms, we create a coarsening hierarchy for the input graph. Beginning at the coarsest level, we iteratively refine and un-coarsen the layout, until we generate an embedding for the original graph. To enhance information propagation within the network, we propose a novel positional rewiring technique based on intermediate node positions. Our empirical evaluation demonstrates that the framework achieves state-of-the-art performance while remaining scalable.

Published as a conference paper at ICLR 2024
CORE-GD: A HIERARCHICAL FRAMEWORK FOR SCALABLE GRAPH VISUALIZATION WITH GNNS
Florian Grötschla, Joël Mathys, Robert Veres & Roger Wattenhofer
ETH Zurich
(fgroetschla, jmathys, rveres, watterhhofer/Bathh.chh
ABSTRACT
Graph Visualization, also known Graph Drawing, aims to find geometric beddings of graphs that optimize certain criteria. Stress widely used metric; stress is minimized when every pair of nodes is positioned at their shortest path distance. However, stress optimization presents computational challenges due to its inherent complexity and is usually solved using heuristics in practice. We intro- duce a scalable Graph Neural Network (GNN) based Graph Drawing framework with sub-quadratic runtime that can learn to optimize stress. Inspired by classical stress optimization techniques and force-directed layout algorithms, we create a coarsening hierarchy for the input graph. Beginning at the coarsest level, we iter- atively refine and un-coarsen the layout, until we generate embedding for the original graph. To enhance information propagation within the network, we pro- pose novel positional rewiring technique based intermediate node positions. Our empirical evaluation demonstrates that the framework achieves state-of ofttc- art performance while remaining scalable.
INTRODUCTION
Graphs, fundamental structures discrete mathematics, are ubiquitous in various fields. Visualizing graphs as node-link diagrams, where nodes are represented points circles and edges as connect- ing lines, is common practice. The quality of visualizations plays a crucial role in comprehending the underlying graph structures. For example, when represented in good way, the underlying becomes clear. A prevalent approach to enhancing graph visu-
structure of the graph in Figure | alizations involves the optimization of stress function, trying to arrange the nodes such that the Euclidean distance between any two nodes closely approximates their shortest path distance in the graph. However, achieving optimal layouts presents substantial computational challenge (Demaine et al. 2021). To address this challenge, these algorithms often resort to heuristic methods. For in- stance, force-directed algorithms conceptualize the graph as physical system governed by forces akin to springs or magnetic fields (Kamada & Kawai 1989). These algorithms simulate the system iteratively optimize graph stress, allowing nodes to reach equilibrium positions.
Figure 1: Graph Evolution with CoRe-GD: From coarse to fine. Our hierarchical approach priori- tizes global positioning before local optimization. The resulting visualization makes the underlying graph understandable. Graphs were drawn with CoRe-GD model trained for 3 dimensions.

---

Published as a conference paper at ICLR 2024
Tailoring heuristics to specific graph distributions is often necessary to produce high-quality vi- sualizations. This requirement frequently demands domain -spnains expertise but also provides an avenue for learning-basee solutions. Recent research (Giovannangeli al. 2021 Wang al. 2021) has drawn parallels between force-directed algorithms and messsage-psssing graph neural networks, where nodes communicate with their neighbors. Nonetheless, scalability remains challenge. When presented with larger graphs necessitating more global context, these methods do not scale. While extending pnessage-passing
fully connected graphs can address this limitation, it incurs quadratic computational and message complexity in the number of nodes, rendering it computationally im- practical for large graphs. We therefore propose a new framework with focus on scalability: CoRe-GD, scalable Coarsening and Rewiring Framework for Graph Drawing. CoRe-GD com- bines hierarchical graph coarsening with a novel positional rewiring technique, facilitating commu- nication beyond local neighborhoods. Notably, both coarsening and rewiring are computationally efficient and introduce only a linear message-passingg overhead.
Our approach begins with hierarchical coarsening process, generating multiple levels. At the coarsest level, nodes from the original graph are merged into supernodes, capturing global structural properties. We prioritize optimizing the positions of these supernodes quently, we reverse the coarsening process by uncontracting the supernodes, allowing us to refine the local placements. This iterative refinement continues until reach the finest coarsening level, which corresponds to the original graph. This global-first strategy enables us to generate rough initial graph drawings and then iteratively optimize them, all while keeping essential information pathways short and effective. Within each coarsening level, we employ Graph Neural Networks (GNNs). To enhance communication between nodes that might be far apart in the original graph but are close in the current visualization, we introduce additional message- messsgg--assing steps. This ad- justment is made because nodes placed far apart in the visualization, despite being nearby in the original graph, can lead to loss in quality due to the discrepancies between their shortest-path dis- tances and their current spatial separation. Therefore, these supplementary passage-passing steps facilitate better message flow to improve the layout.
initial step. Subse-
Our contributions can be summarized as follows:
1. We introduce CoRe-GD, a scalable neural framework for graph visualization based on coarsened graph hierarchies.
2. We present a novel positional rewiring technique that leverages intermediate decoded em- beddings for better information flow.
3. We perform extensive experiments various datasets, showcasing state-of-the-art perfor- mance, even compared to sophisticated handcrafted algorithms.
2 RELATED WORK
Graph Drawing. Given an undirected and connected graph G (V, E), we are concerned with finding an embedding r V - Rd such that ((e) represents the position of node v in node- link diagram. In the graph drawing literature, many metrics have been introduced to judge the performance of these layouts (Purchase,, 2002). One commonly used formulation is the notion of stress, which can be traced back to Kruskal (1964) and was first used by Kamada Kawai (1989) to generate aesthetically pleasing layouts for the class of general graphs. It is defined as:
stress(G, = Σ (II [(w)]l2 d
U.DEV,uge
where duv refers the shortest path distance between node u and v. || ||2 the Euclidean norm of x, and war == d Here, the graph can also be interpreted as a physical system with springs between all node pairs that pull or push nodes apart such that an equilibrium is reached when their distance is close to their shortest path distance in the graph. The algorithm falls into the category of force-directed graph drawing, which was previously popularized by [Eades] (1984) and further studied by Fruchterman & Reingold (1991). These algorithms can be improved using variety of heuristics (Frick et al. 1995). Another line of research uses multi-dimensional scaling (Torg erson 1952) for graph drawing. improved upon by using landmarks (Silva & Tenenbaum 2002) and pivots (Brandes & Pich| 2007). De Leeuw (1988) introduced majorization to tackle the scal-
ing problem and Gansner et al. (2005) used it directly for graph drawing. More recently, Ahmed
2

---

Published as a conference paper at ICLR 2024
et al. (2020) used Gradient Descent on the stress function, with AAhmed et al. (2022) extending the approach to stochastic GD. For very large graphs, maxent-stress was proposed by Gansner et al. (012)) Meyerhenke al. (2017) use this to draw very large graphs based multi-level coars- ening, which largely motivates our approach. The results for classical algorithms motivated a line of learning-based techniques. [Wang al. (2020) use bidirectional graph LSTTM process the graph, while Giovannangeli et al. (2021) use a U-net like architecture. Other approaches use a fully connected graph where edges are annotated with precomputed shortest path distances between node pairs WWan et al. 2021), positional encodings together with Graph Neural Network (Tiezzi et al., 2022) or Generative Adversarial Networks learn from examples (Wang et al. 2022b
Graph Neural Networks. Introduced by Scarselli et al. (2008) Graph Neural Networks (GNNs) have become state-of-the-art for many tasks in graph learning. There are two common problems approach: Their expressivity is bounded by the Weisfeiler-Lehaal (WL) algorithm (Xu et al. 2018), and
with GNNs that follow the original purely saassag-passing-baee
over many rounds is susceptible to oversmoothing (Chen et al. 2020) and oversquashing (Alon & Yahav) 2020). To address the first problem and to make GNNs more expressive, one can endow nodes with additional features such random bits (Sato et. al. 2021) subgraph isomorphisms (Bouritsas al., 2022). Another solution to facilitate information exchange between all nodes, even without using many rounds, allow message exchange between all nodes in the last layer (Alon & Yahav 2020). For some architectures, positional encodings are used to give nodes a relative sense of where they are located. They range from Laplacian PE's (Wang et al. 2022a Dwivedi al., 2022), shortest path
encodings (Li et al., 2020 Ying et al. (021) and random walks (Dwivedi et al. (202 to structural features (Chen et al., 2022). To further improve the flow of messages in the graph and alleviate the aforementioned problems, rewiring approaches change the topology of the graph that is used for message- passgngg...in....... Metrics such as the Ricci flow (Topping et al. (2021) or spectral features (Koutis & Le 2019)) can be used to decide which edges to rewire. Pei et al. (2020) propose learnable module that determines the rewired edges based on distances in a latent embedding space. Furthermore, graph coarsening approaches have also been used for GNNs (Huang et al. 2021
THE CORE-GD FRAMEWORK
Figure 2 providess overview of the CoRe-GD architecture. CoRe-GD employs a coarsening hierar- chy to optimize layouts, starting from coarser representations and progressing to the original graph. At each level, recurrent layout optimization module refines the layout via positional rewiring.
Hierarchical Optimization. The coarsening hierarchy (see Section 3.2 is computed to generate series of graphs with fewer nodes and projections from coarser finer levels. On the coarsest graph, node initialization is performed (see Section B.1). followed by embedding through an encoder network. These embeddings undergo layout optimization that improves the positioning of nodes, and the refined embeddings are transferred to the next level. The process continues until the finest level reached, representing the original graph, where a final layout optimization is conducted, and node embeddings are decoded to positions.
Layout Optimization with Positional Rewiring. Nodes in the graph that are connected over many hops lead to high stress when they are positioned too close to each other. As these nodes need many message-passing rounds to communicate with each other, we rewire the graph and add edges between nodes in close proximity. We focus on efficient rewiring methods, adding only linear overhead in message-passing complexity. We experiment with three rewiring techniques: (1) C-Nearest-Neighbor graphs, (2) Delaunay triangulations (Delaunay et al. 1934p, and (3) Radius graphs. These techniques are computationally efficient, with (1) and (2) introducing only linear number of edges. In Figure 2 (bottom part), we exemplify the utility of the rewiring for the node surrounded by a dotted cycle. This node is close to a node below it but not directly connected to it For a stress-optimized drawing, where distances should approximate shortest path distances, this leads to a high loss. However, in the rewiring that was computed based on the closeness of nodes, they become connected, letting them exchange messages through a differently parametrized graph convolution Convg. More motivation and examples for the rewiring can be found in Appendix AA3) The output is then passed to the convolution on the original topology Conv: again, and this alterna- tion of layers continues for rounds. Notably, the same decoder is used to predict final positions,
3

---

Published as a conference paper at ICLR 2024
M
M
Layou: Opdmization
Uncormact
Layout Opdmiiation
Dec
features the conment graph and encodo them
(o) Compute da intiall
G1
(b) Optimice bey with the modiée depicted below
Assign nodes enbedding of thei supemode and add nolse
St
(4) Optimize the leyout
[e] decaddr
layout optimization
the finml
Layout
Est
Camig
Cortin
Optimiee layout original topology
graph
Optiize byyout
End opamiration the topology
curmenlayout
M
Figure 2: Architecture overview of CoRe-GD: On top: (a) An encoder creates initial embeddings (b) The embeddings are then successively refined in the layoul optimization module (depiction below) before the graph is (c) uncontracted and em- beddings are projected to the new nodes (see Section 3.2). After c repetitions (with e being the number of coarsening levels), the original graph recovered, and (d) the layout is optimized one final time before (e) being decoded into the final node positions. On the bottom: Overview of the layout optimization: To refine the latent embeddings of given graph, we (1) execute GNN convo- lution the original topology. (2) The resulting embeddings are then decoded into node positions that undergo the rewiring procedure (3), resulting new set edges E" for the rewired graph. (4) These edges are then used for another GNN convolution on E' to enhance information exchange between far-away nodes. The two convolutions are alternated, and the rewiring is re-computed r times before (5) one last convolution the original topology is applied.
for nodes on the coarsest level (see Section 3.1
and while COnvE and COnvR do not share their parameters, there only exists one parametrization of each that is applied recurrently. The GNN convolutions make use of a Gated Recurrett Unit (GRU) (Huang& & graph neural networks. Moreover, the convolutions incorporate the embeddings of both endpoints u and when sending a message along the edge (u, For a formal definition the tested graph convolutions, refer to Appendix A.2. The embeddings h that indexed in both figures consistent in their usage with the provided pseudocode for both modules (see Appendix A.2).
Grötschla al. 2022) that was shown to beneficial for recurrent
3.1 NODE INITIALIZATION
To motivate the use of initial features, first analyze the requirements for Graph Drawing in terms of WL-expressiveness. The following lemma provides a first insight:
Lemma To minimize stress for arbitrary graphs, the distinguishabiliiy power for nodes has to exceed that of the k-WL algorithm for any k.
This follows directly from the fact that there exist graphs with several nodes in the same orbit, i.e., in the same equivalence class under graph automorphism. These nodes can not be distinguished by k-WL for any & as they are structurally the same. One example is cycle graphs, where all nodes are part the same orbit. Therefore, a GNN that is limited by any W- algorithm will map these nodes to the same embeddings and thus node positions (if we assume that node positions are com- puted from the node embeddings directly). For cycle graph, this clearly not desirable and will end in drawing that is far from optimal. A common way to enrich existing architectures with more expressive power is adding node features, for example, in the form of positional or structural en- codings (Rampášek et al. 2022). These features not only help distinguish nodes but also provide helpful information on the graph topology that can help solve the task at hand. Thus, CoRe-GD ini- tializes node embeddings with combination of features. While the framework allows for the use of
4

---

Published as a conference paper at ICLR 2024
any features, further choose initializations that have been proven to work well in existing Graph Drawing algorithms and models. We use (1) Laplacian Positional Encodings, (2) Distance encodings to beacon nodes, and (3) random features. Random features and laplacian PE's have been used in prior work for graph drawing (Ahmed et al. 2022 Tiezzi et al. 2022). The reasoning for the usage of distance encodings is that while knowing all-pairs aall-aass-hhorteste path distances would be preferred and has been shown to be generally useful to enhance the performance of GNNs (Zhang et al. (023)) the
computation and memory overhead make them infeasible for large instances. Knowing the distances to constant number of nodes in the graph can serve as surrogate (Ahmed et al. (022). This idea has been shown to be effective for graph drawing, e.g., in Landmark MDS (Silva & Tenenbaum 2002 or Pivot MDS (Brandes & Pich, 2007), and similar ideas were used for GNNs (You et al. 2019 J. More formally, we choose ni beacon nodes V,, = {uf...... V/g r2s 13 uniformly at random and compute du,e for every node to every beacon using separate breadth first searches. Once com- puted, we assign every node u a vector with distances to all beacon nodes (du..f..... d
u.u. )T
These distance values are represented using sine-cosine positional encodings in a transformer-style fashion (Vaswani et al. 2017) and can thus be seen generalization of sequential positional en- codings. In general graphs, a single beacon may not suffice to uniquely identify each node. Previous work routing protocols (Wattenhofer et al. (005) provides an analysis for selecting the necessary number and type of nodes in various graph classes to ensure unique identification. We employ ran- dom selection minimize additional overhead and recompute all features between training epochs.
3.2 GRAPH COARSENING
The coarsening hierarchy aims for a global-first layout optimization strategy before transitioning to progressively finer local placements. Beginning with the original graph G (V, E'), the coarsening process generates a partition P = P1.... Pk: of the node set V. This partitioning optimizes specific criteria, such as edge-cut minimization or graph spectrum preservation (Jin et al., 2020). It results in a new graph G' = (V', E'), where nodes v' E V' correspond to partition elements E P. A mapping function f V - V" assigns nodes to their respective partition (termed "supernode"). This coarsening can be iteratively applied until the graph becomes sufficiently small. In our experiments, we employ spectral- preserving coarsening (Jin et al. 2020 with a constant reduction factor to yield sequence of coarsened graphs GI...., Ge. where G. matches the original graph. This hierarchy requires approximately c E (log VI) levels. In the CoRe-GD framework, layout optimization begins at the coarsest level G1 before progressing to finer levels. Transitioning from layer é to i we apply the inverse mapping f to the embeddings of the current graph G., i.e., for nodes within the same supernode, we set the finer layer's embeddings to that of the coarser layer's supernode: (()) M/s ((e)) for every node V. To distinguish these nodes further, we randomly sample noise from a normal distribution and add it to the embeddings.
3.3 TRAINING
Inver-lnvariant Stress. Previous works (Wang et al. 2021 Giovannangeli et al. 202 apply the stress metric directly as the loss for self-supervised training. which we find to have difficulties with when working with graphs of varying sizes. Especially when scaling to bigger instances, graphs might need larger drawing area than smaller ones. However, for training our model, we prefer for the generated values to stay within the same numerical range. Therefore, we restrict the layout to [o, 1]d by applying a sigmoid activation. Unfortunately, this has the adverse effect that stress optimal layouts can have different geometries when restricted to this area: Consider the path graph with three nodes as depicted in Figure 3 When restricted to [o, 1J2, the optimal layout has a 90-degree angle at the center node, while the optimal layout that can be achieved in the unrestricted domain aligns all nodes on a line. Thus, we rescale node positions by finding the optimal scaling factor a for node positions P. such that the scaled layout P. := {a- p E P] has optimal stress among all a. This allows us to predict values in [0, 1] that represent an optimal layout when scaled to a larger area. In this sense, the drawings we generate are scale-imvrriat. The following lemma provides closed-fome solution. A proof can be found in Appendix A.5
Lemma 2 The scaling factor a can be calculated in a closed-form solution:
Enzo Wav [[()] - (2v)]lldu
O.G.T
Eajo Wie [T T(x)
5

---

Published as a conference paper at ICLR 2024
and is unique, as the stress is convex with regard to the scaling factor.
Replay Buffer. To incentivize steady improvements for every round of layout optimization, we randomize the number of rounds that we execute before backpropagating the loss through time (Werbos) 1988) during train- ing. We thus avoid training the network for the number of rounds that are used during inference, as training deep GNNs tends to become unstable and requires higher memory footprint. Instead, we use replay buffer, simi- lar to what is commonly used in Reinforcement Learning (Lin) 1992). The buffer contains fixed number of graphs and their respective node embed- dings that were generated during previous runs. We then interleave batches from the original dataset and batches from the replay buffer during training. After training a complete batch of graphs, every graph and its generated embeddings can randomly replace an element in the buffer. We store latent embeddings in the buffer instead of positions to seamlessly continue the training from a previous state in the execution. By doing so, we only have to backpropagate the loss through a few rounds at a time but expose the network embeddings that were generated after more rounds during the training. While replay techniques have been used for GNNs before (Grat- tarola et al. 202T). to the best of our knowledge, we are the first to use in- termediate latent embeddings. With this method, our trained models used in Section 4 run hundreds of GNN-convolutions without destabilizing. More details and pseudocode for the training be found in Appendix A.2
0
a)
1
b)
Figure
Part a) shows the best draw- ing inside [0, 1]2 bounding box and b) one best drawing without restrictions.
3.4 TIME COMPLEXITY
CoRe-GI was designed with scalability in mind. Apart from an efficient and practical implemen- lation, good time-complexity bounds are thus crucial, especially for larger instances. We show that the complexity of our instantiation is sub-quadratic.
Lemma Let T Teaarsens T iimi and Trevire be the runtime complexities for coarsening, initial feature computation and rewiring of connected graph g = (V. Further, let Erewire be the upper bound for the number of edges added through the rewiring. Then the following time complexity upper- bound holds for CoRe-GD without hierarchical coarsening:
TCoRe-GD E E (Tiiitiaal (VV1, (E)) + Trewire (VV) + Erewire (V)) + [E]
For CoRe-GD with hierarchical coursening, it becomes:
Thheerarehicol E (Teoarren (VV), + log [V| (Trewtre Enewire ((V)) + (E))
Notice that the term for computing the initial features disappears if we use a hierarchical coarsening the initial features only computed on the coarsest graph, which has constant size. This has the practical implication that features requiring more heavy precomputation can be used with the hierarchical approach. The log term stems from the number of coarsening levels.
We now turn our attention toward the instantiations of the CoRe-GD framework we use in our experi- ments. Namely, we use laplacian PEs, beacon distances, random features as initializations, the coars- ening borrowed from Jin et al. (2020) to compute the hierarchy, and k-nearest-neiihhoor rewiring. Laplacian PEs can be computed in )) (wiieedi et al., (022), with further improvements possible (Fowlkes et al., 2004). Beacon distances can be computed with Freadth-First-Seann -earchh (BFS) starting from every beacon node, which is in O(EE) as the number of beacons is constant. In practice, we can efficiently compute distances on the GPU using the Bellman- -Frd (Bellman) 1958 Ford Jr. 1956) algorithm with unit edge lengths. Random features only require an overhead of VV). The coarsening can be computed in sub-quadratic time (Jin et al. 2020 K-Nearest- Neighbor graphs can be computed in O([V) log [V]) using K-d-trees and only add number of edges linear in the number nodes for fixed K. We thus conclude that CoRe-GD runs in sub-quadratic time overall both for the hierarchical and non-hierarchical approach when using our instantiation.

---

Published as a conference paper at ICLR 2024
Table 1: Comparison of scale-invariant stress between classical Graph Drawing methods, learned models, and our proposed framework. Bold numbers mark the best result, underlined numbers the second best. We train all models on the individual datasets for each reported score, except CoRe- GD-mix, which was trained on mix of all datasets. Our model achieves or matches state-of-the-a on all datasets, including Rome, a popular benchmark in Graph Drawing.
Model
Rome
ZINC
MNIST
CIFAR10
PATTERN
CLUSTER
PivetMDS
388.77 1.02
29.85 0.00
173.32 + 0.12
384.64
+ 0.20
3813.30
L89
3538.25 = 0.73
neato
244.22 = 0.55
5.76 + 0.05
129.87 + 0.19
263.44 + 0.20
3188.34 = 0.59
2920.30 + 0.75
sfdp
296.05 + 1.16
20.02 + 0.27
172.63 + 0.11
+77.9700.11
3219.23
1.31
2952.95 + 1.81
(sgd)"
233.49 0.22
5.14 114::000
0.00
262.52 0.00
3181.51 0.05
2920.36 0.78
(DNNY²
248.56
9.61
147.70
264.52
0.32
3100.07
4.59
2862.95 16.17
DeepGi
235.22 + 0.71
6.19 + 0.07
129.23
0.03
262.91 + 0.13
3080.70
70
0.24
2838. 13 + 0.08
CoRe-GD (ours)
233.17 0.13
5.11 +: 0.02
129.10 0.02
262.68 +: 0.08
3067.02
0.79
2827.81 + 0.36
CoRe-GD-mix (ours)
234.60 0.10
5.21 0.02
129.24
262.90 +: 0.02
3066.1
0.20
2828. 13 0.12
4 EMPIRICAL EVALUATION
Our empirical study split in two: We first demonstrate the effectiveness of the CoRe-GD frame- work the Rome dataset, a common benchmark in the Graph Drawing community. We further add more datasets of similar sizes, as these allow us to train and evaluate all models but also let us assess different graph distributions. As these graphs are rather small (~ 100 nodes), we do not need to employ the coarsening yet. Instead, we can focus on the improvements that can be made single level. For study of scalability and the application of CoRe-GD larger graphs, we later use a subset of graphs from the suitesparse matrix collection and generate random graphs compare the runtime and quality of layouts. Code for CoRe-GD is available online _ For more background information on benchmarking for Graph Drawing tasks, we refer to Appendix A.7.4
their performance
To quantify the quality of drawings for dataset D. we report two metries: The mean eeale-invariant stress over all graph instances and the mean of scale-invariant stresses normalized by the number of node pairs in the graph:
1
Σ at, Ic), and GED
1
Σ - stress ag,re TG).
D
D
G=(VEE)D
We report both the normalized and unnormalized stress bigger graphs usually incur higher stress, which distorts the mean for mixed-size datasets (Giovannangelii et al. [202T] Tiezzi et al.) 2022). Standard deviation is reported over 5 different random seeds in all runs. Our baseline for CoRe-Gi uses random, distance beacons and laplacian PEs as well as KNN rewiring. We further investigate these choices with an ablation study in Appendix A.4 where we test different convolutions, rewiring methods, and initial features. Notably, the positional rewiring method improves performance. Fur- ther, we also train models without latent embeddings where only the positions passed between layers and observe considerably worse performance. An application of the latent node embeddings generated by CoRe-GD positional encodings for graph transformers is investigated down- stream task in Appendix A.6
Baseline comparison. We compare the performance of CoRe-GD on the Rome dataset, a popular benchmark in the Graph Drawing community that consists of graphs curated by the University of Rome (Di Battista et al. 1997) and use the same data split as introduced by Waan al.] (202T). We further extend the evaluation by including datasets from different application domains such as molecular graphs, superpixel graphs for images, and graphs that were generated with a stochastic block model that we take from Dwivedi et al. (2022) (originally proposed for GNN benchmarking). This new benchmarking framework allows us to test the performance of all algorithms on a diverse set of tasks. We the same hyperparameter configuration that achieved the best performance on Rome for all other datasets.
PivotMDS (Brandes & Pich 2007). neato (Kmada & Kawai 1989). stdp Hu 2005 and
(sgd)² (Ahmed et al. 2022) are included in the comparison as classical, non-learning--ee based draw- ing techniques. For -aaming-based approaches, we compare to DeepGD (Wang et al.
2021 and

---

Published as a conference paper at ICLR 2024
PivotMDS
neato
sidp
(sgd)²
(DNN))
DeepGD
CoRe-GD
19.53
13.25
14.28
15.24
13.01
15.33
13.24
30
32.54
31 86
32:47
32.25
35.07
Figure 4: Visual comparison Graph Drawings between classical algorithms, learned models, and CoRe-GD, Below each drawing, report the scale-invariant stress. All neural models were trained on Rome dataset. CoRe-GD generates good layouts across the board, even for regular graphs
Table 2: Comparison on subset of graphs from the suitesparse matrix collection. We note that CoRe-GD maintains competitive performance with classical baselines and underscore the necessity of coarsening in achieving such results.
CoRe-GD
Metric coarsening
coarsening
PivotMDS
neato
sfdp
(sgd)²
stress
42639 1 313
45573 1 844
65404 1 907 43110 1 274 48386 - 321 42435 1 149
(DNN)² Giovannangeli et al. 2021 Further training details and dataset information can be found in Appendix A.7.4] Table summarizes the results. CoRe-GI, (sgd)² and DeepGD are trained on each respective dataset, while CoRe-GD-mix the first 10k graphs from each training set. CoRe-GD outperforms all other methods on all datasets except CIFARIO. where it is slightly outperformed by (sgd)², the best-performing classical algo- rithm. Even though DeepGD uses message-passing on the fully connected graph with pre-computed pairwise node distances, always performs worse than CoRe-GD CoRe-GD-mis performs well overall, albeit a bit worse than CoRe-GD trained on the respective datasets, except for PATTERN, where it outperforms all other models. This demonstrates that while CoRe-GD can beat other mod- els on data trained from the same distribution, it is also possible to train general-purpose version of CoRe-GD that can be used for wide variety of graphs from different distributions. table re- porting the normalized stress values can be found in Appendix A.7.2 We do not observe any major differences between normalized and non-normalized stress. For a qualitative comparison, Figure depicts graph samples drawn with all methods. The differences become most apparent for the grid graph, where it optimal to position nodes as a rectangular grid. CoRe-GD approximates this well, while especially PivotMDS and DeepGD generate distorted drawings.
trained combination of all datasets by taking
Scalability. To demonstrate that CoRe-GD can scale beyond small graphs, we create a new dataset by sampling graphs from the suitesparse matrix collection. These graphs represent real-world in- stances stemming from fields such as power network problems, structural problems, circuit simu- lation, and more. We apply hierarchical coarsening and investigate its impact on CoRe-GD, We were not able to train DeepGD due memory limitations the GPU, message passing on the fully connected graph leads to too many gradients that accumulate on the device. Similarly, while already lagging behind the smaller datasets, did not manage get the training of (DNN)² to converge. Results are shown in Table We can observe that CoRe-GD performs competitively to existing baselines and that the coarsening is crucial achieving that performance.
8

---

Published as a conference paper at ICLR 2024
CoRe coarsening)
DespGD
DSvotM
neato
stdp
(sqd)
0.25
0.20
MMN
10a
stress
Runtime
10"
0.10
10"4
0.05
10-2
3000 Number of nodes
5000
Number nodes
Figure 5: Normalized stress and runtimes randomly generated sparse graphs (Delaunay triangula- tions of random point clouds). The green vertical line at 200 marks the train limit of DeepGD, while the blue line at 1,000 marks the limit of CoRe-GD. DeepGD could only be executed for graphs up size 5,000 before running out of GPU memory. DeepGD becomes unstable under out-of-distribution data, whereas CoRe-GD slightly degrades but still keeps up with the other baselines. The runtimes show that CoRe-GD scales better than most baselines. Further, coarsening aids with scalability for larger graphs, as the initial feature computation, which becomes progressively more expensive, only has to be done for the coarsest graph. See Appendix A.7.3 for more details on the used setup.
We further test the scaling behavior of the models when presented with sparse graphs from the same distribution but of increasing sizes. We train CoRe-GD sparse Delaunay triangulations of random point clouds up to size 1,000. DeepGD was trained on graphs up to size 200, as bigger graphs result in the aforementioned memory problems. This also happened in inference when presented with graphs of size 5,000 or bigger, due to the all-pairs-shhottss--all information that has to be computed and kept in memory. In Figure 5 (left), can observe that the training size clearly visible for DeepGD, which does not generalize well beyond its training distribution. CoRe-GD without coarsening suffers to a lesser degree, whereas CoRe-GD with coarsening manages to compete with the other baselines, albeit degrading for graphs beyond its training distribution. Computing the stress of a layout is slow and memory-intensive, which is why we cap the analysis at 5,000 nodes. As inference can be done without stress computation, on graphs up to size 25,000. We notice that, initially, CoRe-GD performs faster without coarsening compared to its coarsened counterpart. However, as the graph size increases, the computation of initial features scales with the graph size the absence of coarsening. In contrast, when coarsening is employed, this initial feature computation is only required for the coarsest, smaller graph. Overall, CoRe-GD scales well when compared to other baselines, with PivotMDS heing the clear exception.
measure the real-world runtime of all models
5 CONCLUSION
We introduce CoRe-GD, neural framework for Graph Drawing. Our approach incorporates coars- ening and a novel positional rewiring technique to achieve scalability and maintain computational efficiency. To judge the performance of CoRe-GD, we conducted evaluation encompassing estab- lished benchmark datasets such as the Rome dataset, datasets from the graph learning community. and real-world graphs sourced from the suitesparse matrix collection. The results demonstrate that CoRe-GD consistently delivers good performance and extends its capabilities to graph sizes not encountered during training. CoRe-GD's generation of latent node embeddings, rather than solely computing positions, expands its potential applications. Notably, CoRe-GD also stands out as the first neural architecture capable of achieving this level scalability, otherwise only known from sophisticated handcrafted algorithms. To accomplish this objective, we introduced encoded beacon distances as node features and employed a replay buffer to store latent embeddings for training deep recurrent GNNs, which lets run hundreds of graph convolutions recurrently to improve the lay- out without destabilizing. Both methods might hold the potential for addressing a broader range of geometric graph-related problems beyond traditional graph visualization.

---

Published as a conference paper at ICLR 2024
REFERENCES
Reyan Ahmed, Felice De Luca, Sabin Devkota, Stephen Kobourov, and Mingwei Li. Graph drawing via gradient (escent.ggd)" (gd) In Graph Drawing and Network Visualization: 28th Interna- tional Symposium, GD 2020, Vancouver, BC, Canada, September 16-18, 2020, Revised Selected Papers 28, pp. 3-17. Springer, 2020.
Reyan Ahmed, Felice De Luca, Sabin Devkota, Stephen Kobourov, and Mingwei Li. Multicriteria scalable graph drawing via stochastic gradient descent, (sgd) (2) d) JEEE Transactions on Visualization and Computer Graphics, 28(6):2388 239999993---99 2022.
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. arXiv preprint wwxxiv:0006.02005. 2020.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 748- 758. PMLR, 2021.
Richard Bellman. On a routing problem. Quarterly of applied mathematics, 16(1):87-90, 1958.
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pictro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Infor- mation Processing Systems,
2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions Pattern Analysis and Machine Intelligence, 45(1):637-668, 2022.
Ulrik Brandes and Christian Pich. Eigensolver methods for progressive multidimensional scaling of large data. In Graph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006. Revised Papers 14, pp. 42-53. Springer, 2007.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 3438-3445, 2020.
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph rep- resentation learning. International Conference on Machine Learning, pp. 1469-3489 PMLR, 2022.
Jan De Leeuw. Convergence the majorization method for multidimensional scaling. Journal of classification, 5:163-180, 1988.
Boris Delaunay al. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 1-793-800)1-2,, 1934.
Erik Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, and John Urschel. Multidimen- sional scaling: Approximation and complexity, 2021.
Giuseppe Di Battista, Ashim Garg, Giuseppe Liotta, Roberto Tamassia, Emanuele Tassinari, and Francesco Vargiu. An experimental comparison four graph drawing algorithms. Computational Geometry, 7(5-6):303- -3550333333330 1997.
Vijay Prakash Dwivedì, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations, arXiv preprint arXiv:2110.07875, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2022.
P. Eades. A heuristic for graph drawing. Congressus Numerantium, 42:149-160, 1984.
Lester R Ford Jr. Network flow theory. Technical report, Rand Corp Santa Monica Ca, 1956.
10

---

Published as a conference paper at ICLR 2024
Charless Fowlkes, Serge Belongie. Fan Chung, and Jitendra Malik. Spectral grouping using the nystrom method. IEEE transactions on pattern analysis and machine intelligence, 26(2):214 225, 2004.
Arne Frick, Andreas Ludwig, and Heiko Mehldau. A fast adaptive layout algorithm for undirected graphs (extended abstract and system demonstration). In Roberto Tamassia and loannis G. Tollis (eds.), Graph Drawing, pp. 388-403, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg. ISBN 978-3-540-49155-2.
Thomas MJ Fruchterman and Edward M Reingoid. Graph drawing by force-directed placement. Software: Practice and experience, 21(11):1 12:::11191111 11222111444 1164, 1991.
Emden Gansner, Yehuda Koren, and Stephen North. Graph drawing by stress majorization. In Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29- October 2, 2004, Revised Selected Papers 12, pp. 239-250. Springer, 2005.
Emden Gansner, Yifan Hu, and Stephen North. A maxent-stress model for graph layout. IEEE transactions on visualization and computer graphics, 19(6):27--40, 2012.
Loann Giovannangeli, Frederic Lalanne, David Auber, Romain Giot, and Romain Bourqui. Deep neural network for drawing networks,(dnn) 2),(dnn) 2. In Graph Drawing and Network Visual- ization: 29th International Symposium, GD 2021, Tübingen, Germany, September 14-17, 2021, Revised Selected Pupers 29, pp. 375-390. Springer, 2021. 20211
Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Learning graph cellular automata. Advances in Neural Information Processing Systems, 34:20983-20994, 2021.
Florian Grötschla, Joël Mathys, and Roger Wattenhofer. Learning graph algorithms with recurrent graph neural networks, 2022.
Yifan Hu. Efficient, high-quality force-directed graph drawing. Mathematica journal, 10(1):37-71, 2005.
Binxuan Huang and Kathleen M Carley, Residual or gate? towards deeper graph neural networks for inductive graph representation learning. arXiv preprint arXiv: 1904.08035 2019.
Zengfeng Huang. Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph neu- ral networks via graph coarsening. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 675-684, 2021.
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 655-665, 2022.
Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Con- ference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4452-4462. PMLR, 26-28 Aug 2020. URL https:: /ptpss/e//ccceeingg mlr.
press/v108 finn0ann....m html
Tomihisa Kamada and Satoru Kawai. An algorithm for drawing general undirected graphs. Information Processing Letters, 31(1):7-15. 1989. ISSN 0020-0190. doi: https///oi.org/ 10.10166002200019908899990000000 URL httph:ttt////mm http://wwwwwcecceeeeeeroo wwweeeettcooocceeeeeeeeeeee coon/scinnce///// article/p1100000019053
Ioannis Koutis and Huong Le. Spectral modification of graphs for improved spectral clustering. Advances in Neural Information Processing Systems, 32, 2019.
Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothe- sis. Psychometrika, 29(1):1-27, 1964.
Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 2020.

---

Published as a conference paper at ICLR 2024
Long-Ji Lin. Self-improving reactive agents based reinforcement learning, planning and teaching. Machine learning, 1-293-321, 1992.
Henning Meyerhenke, Martin Nöllenburg, and Christian Schulz. Drawing large graphs by multilevel maxent-stress optimization. IEEE transactions on visualization and computer graphics, 24(5):
1814-1827, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 2020.
HELEN C. Purchase. Metries for graph drawing aesthetics. Journal of Visual Languages doi: https://doi.or//00.10000 jvlc.2002.0232. URL http:::/t////. httppss:///www././ sci encedi rect. wwt. ctt.c///cceecc///raicce///p/p/// S 21045926X029023220
& Computing, 13(5):001-51, 2002. ISSN 1045-9264
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do-
minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15511-111,,,,,, 2022.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima.
Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Vin Silva and Joshua Tenenbaum. Global versus local methods in nonlinear dimensionality reduc- tion. Advances in neural information processing systems, 15, 2002.
Matteo Tiezzi, Gabriele Ciravegma, and Marco Gori. Graph neural networks for graph drawing.
IEEE Transactions on Neural Networks and Learning Systems, 2022.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522, 2021.
Warren S Torgerson. Multidimensional scaling: I. theory and method. Psychometrika, 17(4))401- 419, 1952.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need, 2017.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint ar arXiv:2203.00199 2022a.
Xiaoqi Wang. Kevin Yen, Yifan Hu, and Han-Wa Wei Shen. Deepgd: A deep learning framework for graph drawing using gnn. IEEE computer graphics and applications, 41(5):32 44, 2021.
Xiaoqi Wang, Kevin Yen, Yifan Hu, and Han- Wei Shen. Smartgd: A self-challenging generative adversarial network for graph drawing. arXiv preprint arXiv:2206.06433 2022b.
Yong Wang, Zhihua Jin, Qianwen Wang, Weiwei Cui, Tengfei Ma, and Huamin Qu. Deepdrawing: A deep learning approach graph drawing. IEEE Transactions Visualization and Computer 2020. doi: 00.1099/TVCG.221999944777
Graphics,
Mirjam Wattenhofer, Roger Wattenhofer, and Peter Widmayer. Geometric routing without geometry. In Andrzej Pelc and Michel Raynal (eds.), Structural Information and Communication Complex- ity. pp. 307-322, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. ISBN 978-3-540-32073- 9.
Paul J Werbos. Generalization of backpropagation with application recurrent gas market model. Neural networks, 144):3393356, 1988.
Keyulu Xu, Weihua Hu. Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 181000000 2018.
12

---

Published as a conference paper at ICLR 2024
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances Neural Information Processing Systems, 34:28877-28888 2021.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks, 2019.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of gnns via graph biconnectivity, 2023.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2110.03753, 2021.
13

---

Published as a conference paper at ICLR 2024
A APPENDIX
A.1 BASELINE ALGORITHMS
Table 3: Comparison of classical and learned graph drawing algorithms. Our method can facilitate information exchange in the graph while maintaining an efficient runtime and achieving state-of- the-art on the Rome dataset. For (sgd)?, sparse approximation with sub-quadratic runtime ex- ists. (Ahmed et 2022)
Sub-Quadratic Runtime
Global
Mean Stress
Model
Learned
Message Passing
on Rome Dataset
PivotMIDS (Brandes & Pich 2007
N/A
388.77
neato Kamada & Kawar 1989
N/A
244.22
sldp (Hu 2005
N/A
296.05
(sgd)" (Ahmed
2022
N/A
233.49
(DNNY* Giovannangeli et al. 2021
X
248.56
DeepGD Wang et al. 2021
X
235.22
CoRe-GID (ours)
233.17
An overview of the used baselines and their complexities is given in Table CoRe-GD is the only algorithm that (I) is learnable, i.e., can be adapted to different graph distributions by training on them, (2) has sub-quadratic runtime complexity, thus scaling well when applied to bigger graphs, and (3) allows for global message exchange by alleviating potential information bottlenecks with positional rewiring. Notably, CoRe-GD outperforms prior work on the Rome dataset and generally performs better than all learned baselines.
A.2 ARCHITECTURE DETAILS
Algorithm CoRe-GD
1: procedure LAYOUT OPTIMIZATIONG: (Vi, Fa), F1,,
Figure top Optimize layout for r rounds Convolution on Gi
2: for = to do
3: h +- ConvE(Ei, h4)
4:
r f- Dec(h(..)
Decode node positions
5: ER Rewiring based on I
6:
W/41 t Conve (En, k!,))
7:
end for
8: h/4 &- ConvE(Er, h1/41)
D. Finish with convolution original topology
9: return h/-=
10: end procedure
11: procedure CORE-GD(C)
b Figure 2 bottom
G Ei,,
(Ve, E.) Coarsen G into hierarchy
G. =
13: hj t Compute and encode initial features for G1 for 1 to do
Iterate through coarsening levels /
15:
h + LAYOUT OPTIMIZATION((I, r).
11 Project embeddings W/+11 Gi+1 and add noise
17:
end for go+1
<- LAYOUT OPTIMIZATION((G..
19:
pe+1 r+1
<- [))
20:
return ,+1
b Return final positions
end procedure
Algorithm provides further details the modules depicted in Figure 2 with the notation for intermediate states h. The projection of embeddings is done with a sparse matrix multiplication and first sets embeddings for all nodes to the embedding of their supernode. As this means that
14

---

Published as a conference paper at ICLR 2024
multiple nodes receive the same embeddings, add noise from normal distribution to change them slightly. It should be noted that CoRe-Gi only decodes latent embeddings to positions for the get the final output of the network. In all other steps,
purpose of computing the rewiring pass the latent embeddings to let nodes maintain more information than just their current position.
Algorithm 2 CoRe-GD Training
1: procedure CORE-GD TRAIN(Batch = ((91. /1).................... (GB: hB). replay buffer R) if Puncoarsen X (0, then
2:
Uncoarsen graphs with probability Puncuursen
3:
Fpee f- (0, Opre)
4:
Tpost (0, ppst
5:
for (9, in B do
Di in parallel
6:
nnew LAYOUT OPTIMIZATION P'pee)
7:
if G can be uncoarsened then
8:
gnew <- Next graph in the coarsening hierarchy
9:
Anew +- Project embeddings Neww to Inew and add noise
end if
11:
nnww LAYOUT OPTIMIZATION Anow, T Toss.
12:
end for
13:
elsed
14:
T+ NN(,0 for h1) in do
in parallel
16:
Unew f- LAYOUT OPTIMIZATION(G, Tppss)
Inew G end for end if
18:
20:
for (G. hnew) in B do
r + (hc(h)
22:
Compute and collect loss for layout I Randomly replace elements R with (G, knew)
23:
24:
end for
25:
Do backpropagation on collected losses
26:
end procedure
Training and backpropagating through all layers at once is costly (in terms of memory) and tends to become unstable. Still, want the trained network to be able to hundreds of the same parametrized GNN-convolutions during inference to optimize the layout a big graph. We achieve this goal by training only with few rounds of the layout optimization, but storing the resulting latent embeddings together with the graph in a replay buffer R such that they can be used in a future training batch. Doing so, we only backpropagate through a small (randomized) number of layers at time. Pseudocode for the training of batch is provided in Algorithm [ Batches are drawn alternating from replay buffer and original graphs with the encoder Enc applied before being passed to the procedure.
A.2.1 GRAPH CONVOLUTION
We use an adapted version the GIN and GRU convolution. Assuming that h is the embedding of node step f,, the GRU convolution looks follows:
h++1 GRU
((MII) wEN(v)
Σ
where GRU is a Gated Recurrent Unit and, θ a learnable MLP and || the concatenation operation. We can observe that instead of only aggregating node features from neighbors, they are first com- bined with the embedding of the target node that receives the message. We do the same adaption for the GIN convolution:
h.+1 =0, (u+o) + Σ O2(h((1(())
wEN(w)
15

---

Published as a conference paper at ICLR 2024
The GAT convolution is not adapted that way, it already incorporates this relative information. For the GNN convolution on the imput graph topology, we use two layers of the same convolution, Le., do two rounds of message passing before interleaving it with one round of message-passingg the rewired topology.
A.2.2 LAPLACIAN PE COMPUTATION
We apply the same Laplacian eigenvector positional encodings as Dwivedi et al. (022). via the factorization of the graph Laplacian:
= - U? with A being the adjacency matrix of the graph, D the degree matrix and U and the eigenvectors and eigenvalues of the eigen-decomposition. We always take the smallest Laplacian eigenvectors, denoted in 7 as "Number of Laplacian cigenvectors".
A.3 REWIRING
Figure 6: Motivation for the positional rewiring. Two nodes that are far apart in the graph are positioned close together in the drawing. To let them exchange information directly, rewire the graph based on intermediate node positions. After the layout is optimized, the nodes are moved further apart from each other.
Our positional rewiring technique is based decoding intermediate embeddings get current positions. Figure 6 motivates the rewiring further. Here, two nodes are positioned close to each other in the current drawing, while they should have distance proportional their shortest path length, which is large in this case. The two nodes are not able to exchange information directly with each other, and nessage-passing would take many rounds propagate the positioning sufficiently. The positional rewiring counters this by directly connecting these nodes and letting them optimize their relative positioning.
Input point cloud
Delaunay
Radius
Figure 7: The same point cloud rewired with three techniques.
Without considering the underlying graph topology, one consider these positions I(V) point cloud n-dimensional space. The point clouds are then converted into a graph for local- ized message passing. We experimented with three rewiring methods: K-nearest-neighbor graphs, Delaunay triangulations, and radius graphs. Figure 7 shows the same point cloud, rewired with the three methods.
16

---

Published as a conference paper at ICLR 2024
Table 4: Ablation study on CoRe-GD. Each reports the scale-invariant stress corresponding to single change of the architecture or training configuration. All runs were done on the Rome dataset.
Ablation
Stress
Normalized Stress x10*
Baseline
233.17 0.13
57.61 = 0.03
Cony
GIN
238.53 1.43
59.17 + 0.41
GAT conv
270.83 8.45
70.27 = 2.10
No beacons
233.39 0.30
$7.65 = 0.07
Initial Features
No laplacian PE
234.65 0.33
57.91 = 0.08
No random features
233.24 0.17
57.64 = 0.05
No rewiring
236.38 0.12
58.50 + 0.02
Rewiring
Delaunay
233.40 0.67
$7.69 = 0.19
Radius
234.14 14 0.68
57.81 + 0.17
Random
236.01 0.08
58.38 + 0.03
No replay buffer
236.65 1.75
58.61 + 0.50
Scale-dependent stress
234.04 0.82
57.83 + 0.21
Table 5: Ablation study for different coarsening approaches, taken from Jin et al. (2020), on the suitesparse dataset.
Metric
heavy.edge
affinity_GG .GS
kron
variation neighborhoods
stress
42800 422
42639 1 313
42699 1 248
42935 319
normalized stress (x (x10))
96.7 = 0.6
96.4 + 0.7
96.6 + 0.3
97.7 1.5
KNN For the KNN graph we add edge (u, v) for the K closest points u regarding Euclidean distance. This means the graph is directed and every node has an in-degree of exactly K. In the message-passingg step, messages are only sent along the directed edges, letting every node know about its K nearest neighbors.
Delaunay Triangulation The Delaunay triangulation the dual graph of the Voronoi diagram. In Delaunay triangulation, it holds that given any triangle, no vertex lies inside its circumeircle. As we have a triangulation, the number of edges linear in the number nodes. Moreover, the fast sequential computation time of O log VI) makes it ideal fit for rewiring technique. The downside of this approach is that it is hard to parallelize the computation, making it slow in practice. This is also what we observed during our testing.
Radius Graph In the Radius graph, two nodes connected if the Euclidean distance between them is smaller or equal to predefined threshold. For the testing in our ablation study, we set this value 0.05. Setting good radius is hard, and choosing bad value can lead bad performance as the number edges not bounded with this approach, and we can get a fully connected graph in the worst case. The radius can also be sensitive the graph size want draw, especially restrict the drawing area to [0, 1]d. Here, bigger graphs will populate the space more densely. For these reasons we prefer the KNN or Delaunay based rewiring over the Radius graph.
A.4 ABLATION STUDY
We corroborate our architectural choices with an ablation study on the Rome dataset. As can be deduced from Table every component contributes to the performance of CoRe-GD, Most notably, the chosen convolution plays major role, while the chosen rewiring method and the usage of the replay buffer also make a significant impact. This supports the claim that the GRU convolution is well-suited for recurrent GNNs. While the Delaunay rewiring performed similarly to KNN, training time is much longer for Delaunay as the triangulation is computed on the CPU. A GPU-optimized implementation could help to make it more viable in practice.
17

---

Published as a conference paper at ICLR 2024
A.5
STRESS
Restricting the domain of the graph layout can limit the solution space to become suboptimal. There- fore, want rescale node positions using a scaling factor a for node positions P such that the scaled layout Pa == {a p E PJ has optimal stress among all a. Therefore, the stress we report throughout the paper becomes scale-invariant. Recall the definition of stress:
stress(G.I) =
Σ M,PVVu
(II r(e)ll2 duv)²
We want to find the optimal aGrr which minimizes the stress loss:
aG,r arg min stress(G,1,,)) arg min ae
War -al()) dwo)
aER
To find the optimal a, take the first derivative with respect to and solve it be 0.
i
da (aress(GTT,,)))
(Ia aT(v)ll2 duv)
da V.VEVa
Wao (a: - [(u)ll2 - duv )2
da U.VVVa
0
Σ
Weo
21 ((v)]l2dw))
w,vE Visfo
Σ
Way 2 (T)) ((2))lad
Σ
r(v)ll
U,KEV
Wee [[u) - -(2))l2dur = a Σ VaVeV
Σ
Wav [ - [(v)ll3
Σ
En.oEVa Wur [T ((v)lladue
EnveV Way [T)) - [w))1
Moreover, we can verify that the solution is the unique minimum by checking if the second derivative with respect to a is positive.
82
Σ
(al(allT(u) - [(v)ll2 d
Σ
Wae (2) - [()) > 0
a2
Therefore, the following closed form solution defines the optimal atg.r:
En,veV Wuel ((u) - ((v) 12d
AG = arg min stress stress (G.
Σ E.veVVagee Wao [[(u) I'(w)ll
aERl
A.6 CORE-GD AS POSITIONAL. ENCODING
By utilizing stress as the loss, we can train CoRe-GD in an unsupervised fashion to generate node embeddings that capture pair-wise node distances in the graph. In the case of graph drawing, we usually use latent embeddings to find good layout in a low-dimensional space. However, these latent embeddings capture inherent structural information of the graph, which might be useful for other learning applications, e.g., in improving the performance of downstream tasks. We test the downstream performance using the GPS framework (Rampášek et al. 2022). where we run base- lines using initial features consisting of laplacian eigenvectors, random walk structural encodings (RWSE), and beacon encodings to test CoRe-GDi GDDs latent embeddings as well as the derived posi- tions. As seen in Table 6 CoRe-GD embeddings admit competitive performance, outperforming
18

---

Published as a conference paper at ICLR 2024
Table 6: Performance using the GPS framework using different types of positional embeddings.
Models marked with * were trained by us.
Model
ZINC
M
CIFARIO
PATTERN
CLUSTER 1
DGN (Beaini et 20211
0.168
72.838 0.417
86.680
0.034
CIN (Bodiar m. 2014
0.079 0.006
GIN-AK+ Zliao el 2021
0,080 0.001
72.19 0.13
86.850 0.057
K-Subaraph
2022
0.094 0.008
86.848 0.037
77.856 0.104
EGT Hussain et al. 2044
0.108 0.009
98.173 = 0.087
68.702
0.409
86,821 = 0.020
79.232 : 0.348
GPS+LapPE Ramppšck 2022
0.116 0.009
98.051 : 0.126
72.298
0.356
86.685 = 0.059
78.016
0.180
GPS+RWSE (Kampasck A022
0.070 0.004
71,958
0.398
GPS+CoRe-GD
0.126 1 0.010
97,876 = 0.140
0,340 72.494
86,522 = 0.405
77.454 0.157
GPS+CoRe-GD+
0.089 0.006
97.970 = 0.190
71.614
86,769 0.045
78.316 0.169
GPS+CoRe-GD-pos
0.122 - 0.009
97.884 = 0.154
72.296 0.286
86.721 = 0.020
77.722 0.168
Table 7: Final hyperparameter settings and tested configurations for CoRe-GD.
Hyperparameter
Baselines
Tested for baselines
suitesparse
Delaunay graphs
Hidden dimension
64
(32, 64, 128)
64
64
Dropout
0.0
(0.0, 0.1]
0.0
0.0
Mean number of rounds
5, [1]
5
5
Variance round number
Batch size
16/32
(16, 32, 64)
4
4
Convolution
GRU
(GIN, GAT, GRU)
GRU
GRU
# Laplacian eigenvectors
(4, 6, 6) (0. 1]
8
8
# Random inputs
1
# Beacons
(1. 2, 4, 8)
2
2
Encoding size beacon
(2, 4, 8, 16)
8
8
Rewiring
KNN
(KNN, Delaunay, Radius)
KNNN
KNNN
for KNN
[4, 6, 8) (2048, 4096)
8
8
Replay buffer size
4096
1024
1024
Coarsen algorithm
affinity_CGi -GS
heavy_edge
Coarsen reduction factor
0.8
0.8
laplacian and beacon embeddings on ZINC, PATTERN, and CLUSTER, which indicates that CoRe- GD adds additional value these embeddings through unsupervised stress minimization. Latent embeddings perform better than positions overall, indicating that they contain additional structural information. This hints at the potential of CoRe-GD embeddings for downstream tasks.
A.7 EXPERIMENTAL SETUP
A.7.1 TRAINING DETAILS
The final version of CoRe-GI trained with the same hyperparameters (except batch size) all datasets. Table 7 lists the setup and tested hyperparameters for the final model we conducted our experiments with. Due computational constraints, full grid search of all hyperparameters was infeasible. Therefore, we tuned by running a line search amongst one of the dimensions. We used the Adam optimizer with an initial learning rate of 0.0002 scheduled with the Plateau technique and patience of 12, threshold of 2, and factor of 0.7. Model selection was done by choosing the epoch with the best validation score, and we trained for 200 epochs in total. Elements in the replay buffer were replaced with a probability of 50% if the batch was part of the original dataset and a probability of 100% if the batch was sampled from the replay buffer. All training was done on an RTX 3090 with 24GB of VRAM. For all results reported in the paper use output dimension of d 2.
For DeepGD, we used the same configuration as provided by the authors, except for a reduced batch size of 16 for PATTERN, CLUSTER, and CIFARIO due the increased size of the graphs in the dataset. The values reported in the paper were produced with PivotMDS initializations, and the number of pivots
set to 10. We used the recommended epoch number of around 600, except when we hit the timeout of 48 hours. The model with the best validation loss was selected. All training done A6000 with 48GB of VRAM.
19

---

Published as a conference paper at ICLR 2024
Table 8: Comparison of scale-invariant stress between classical Graph Drawing methods, learned models, and our proposed model CoRe-GD. We train all models on the individual datasets for each reported score, except CoRe-GD-mix which was trained on a mix all datasets. Our model achieves or matches state-of-the-a on all datasets, including Rome, popular benchmark in Graph Drawing.
The reported score the scale-invariane normalized stress multiplied by 1000.
Model
Rome
ZANC
MNIST
CIFAR1O
PATTERN
CLUSTER
PivotMDS
105.12 0.13
54.46 + 0.00
34.92 0.02
27.81
0.01
257.62
0.09
249.87 + 0.11
nealo
61.31
10.39 0.09
26.26
0.04
19.04
0.01
215.61
0.03
206.33 0.07
sldp
77.06 1: 0.30
35.58 1: 0.49
3
0.01
217.81
0.10
208.73 1: 0.15
(sgd)"
58.01 + 0.03
9.30 = 0.03
26.13 0.00
18.98 = 0.00
215.31 0001
206.50 + 0.05
(DNN)²
62.71 0.91
17.06 3.05
30,06 1.51
19.12 0.02
209.58 0.34
202.33 = 1,28
DeepGD
58.55 = 0.25
11.21 = 0.14
26.13 = 0.01
19.01 0.01
208.28 + 0.04
200.43 = 0.01
CoRe-GD (ours)
57.61 = 0.03
9.26 = 0.02
26.10 + 0.00
18.99 0.01
207.27 - 0.04
199.65 = 0.02
CoRo-GD-mix (ours)
57.95 = 0.04
9.42 = 0.04
26. = 0.00
19.01 = 0.00
207.26 + 0.02
199.71 + 0.01
CoRo-GD
CoRe-GD (no coarsaning)
DeepGD
Pivot
naato
stdp
[sgd]
10a
10a
107
10
Runtime [s]
10a
stress
10
10a
10a
10a²
1000
2000
3000
4000
5000
5000
10000
15000
20000
25000
Number nodes
Number nodes
Figure 8: Non-normalized stress for performance and runtimes of the scaling measurements. Other- wise, the same Figure
For training the (DNN)² models, we used the default configuration specified by Giovannangeli et al. (2021) for stress optimization. Specifically, train for at most 200 epochs while using early stopping after 20 epochs if there no improvement time limited to 48 hours. For each dataset, trained five models, except for ZINC, which was much more unstable. (DNN)² on ZINC often did not improve upon the score achieved the very first epoch. Therefore, behavior and improved after epoch Moreover, a model on the ZINC dataset produced NaN/Inf values the stress computation for a single graph, which we replaced with (in favor of (DNN)²). All training was done on CPUs.
the validation loss. Furthermore, training
trained 30 models in total to get at least five runs that exhibited learning
A.7.2 NORMALIZED RESULTS
Table 8 shows normalized results for the Graph Drawing comparison. They are consistent with the non-normalized values, thus further underlining the performance of CoRe-GI.
A.7.3 SCALING EXPERIMENTS
run both runtime and performance experiments on physical cores of an AMD EPYC and 64GB of RAM. For DeepGD and CoRe-GD, should be noted that the preprocessing of DeepGD and the coarsening of CoRe-GD still runs on the CPU, and times measured, including all data transfers from and to the GPU. For the sake of completeness, we report the non- non-normalized results for the plot in Figure g together with a full view of the DeepGD loss.
an RTX 3090 with 24GB VRAM in addition.
20

---

Published as a conference paper at ICLR 2024
x
CoRe-GD x
CoRe-GD (no coarsening)
DeepGD
PivotMDS
x
neato
x
sFdp
(sgd)*
n=1000
1e6
1.6
350000
1.4
300000
1.2
250000
stress
stress
1.0
200000
0.6
100000
0.4
50000
2.5
Runtime [s]
Runtime [s)
1e6
1e6
4.0
3.5
stress
stress
3.0
x
Runtime [s]
Runtime [s]
Figure 9: Scatter plots depicting runtime and stress for different graph sizes n as measured for the experiments in Figure [ CoRe-GD Pareot-optimal and performs considerably better than DeepGD, which is not part of the last plot as it ran out of memory for 5000 nodes.
To evaluate the tradeoff between achieved loss and runtime further, we plot them together for fixed- size Delaunay graphs in Figure We can observe that CoRe-GD stands as being Pareto-opting for four depicted graph sizes.
A.7.4 GRAPH DRAWING BENCHMARKING AND EMPLOYED DATASETS
Benchmarking for Graph Drawing is highly non-standardized. Classical algorithms like Pivot- MDS (Brandes & Pich, 2007) or (sgd)² (Ahmed et al., 2022) only use few graphs (some of them usually from the suitesparse matrix collection, others synthetically generated) evaluate perfor- mance comparatively. While this makes it hard to judge the general performance, and the graphs can be sampled with bias, this fails, especially when neural methods employed that need differ- ent sets of graphs for training, validation, and testing. Here, both DNN and DeepGD resort to the Rome dataset by Di Battista al. (1997) that was introduced for the purpose of experimental com- parison of graph drawing algorithms. One downside of this dataset is the fact that it only contains relatively small graphs with 52.3 nodes on average. This makes unsuitable for testing state-of-the- art algorithms that focus scalability and larger graph instances. should be noted that DNN2 and DeepGD use different random splits of the dataset.
To overcome the limitations of existing benchmarks, we propose the following: We include the Rome dataset with the random split specified by Wang et al.] (2021) to compare our results to ex- isting neural methods. As also want to test the adaptability of the graph drawing algorithm to different graph distributions. we further include the ZINC, MNIST, CIFÁR1O, PATTERN, and CLUSTER datasets from Dwivedi et al. (022) that were originally proposed for the purpose of
21

---

Published as a conference paper at ICLR 2024
Table 9: Training dataset statistics for all used benchmarks, Edge counts are for directed edges.
Dataset
# Graphs
# Nodes
# Edges
License
Rome
11531
52.3
138.1
source
ZINC
12,000
23.2
49.8
CC-BY 4.0 and MIT
MNIST
55,000
70.6
564.5
CC-BY 4.0 and MIT
CIFARIO
45.000
117.6
941.2
CC-BY 4.0 and MIT
PATTERN
10,000
118.9
6,098.9
CC-BY 4.0 and MIT
CLUSTER 10,000
117.2
4,303,9
CC-BY 4.0 and MIT
Suitesparse graphs
189
502.3
6385.6
CC-BY 4.0
Delaunay graphs
200
577.77
3428.23
MIT (self-generated)
GNN benchmarking. We chose these datasets as they have predefined training/validationneess splits and are roughly the same size as the Rome dataset (with MNIST and CIFAR 10 being a bit larger), thus allowing us to train existing neural methods on them. While the original datasets contain labels, we can omit those training is done in self-supervvsed way with the goal of minimizing stress. To further evaluate scalability and performance on larger graphs, we follow (sgd)² and PivotMDS in taking graphs from the suitesparse matrix collection and creating our subset with all suitable graphs with 100 to 1000 nodes. For further evaluation of the scaling behavior, we additionally create synthetic Delaunay triangulations. This allows to create sparse graphs of any size that in the scalability study in Section
We show dataset statistics in Table 9 For any dataset that contains directed graphs, make them undirected to fit the task. We further only consider connected graphs. Disconnected graphs can always be drawn by drawing each connected component separately.
Rome Di Battista et al. 1997) The Rome dataset is provided by graphdrawing.oog org and contains graphs collected at the University of Rome, They represent Flow graphs mainly used for database and software visualization. It is common benchmark for stress optimization in the graph drawing community.
diagrams and Data-
Benchmarking GNNs Datasets (Dwivedi et al., 2022) ZINC contains molecular graphs from the ZINC database of compounds for virtual screening. MNIST and CIFARIO are generated from the classical MNIST and CIFARIO datasets by extracting superpixels, small regions of homogeneous intensity in images. PATTERN and CLUSTER are synthetic tasks where graphs were generated with the Stochastic Block Model. Statistics for all datasets are shown Table
Suitesparse Subset We select subset of suitesparse matrices (https://spare..aamu. taw.. We con- sider all quadratic matrices with 100 to 1000 columns that result in an undirected, connected graph. This results in a dataset with graphs from many different distributions and application areas, such as power network problems, structural problems, or circuit simulation problems, to name but a few.
Random Delaunay Triangulations We randomly sample the size of the graph between 100 and 1000 and create random 2D point cloud with that many points. A Delaunay triangulation is com- puted on the point cloud, resulting in a graph with planar embedding. The planarity guarantees that the graph has a linear number of edges, keeping it sparse.
A.8 MORE COARSENING EXAMPLES
Figure 10 shows additional examples of the progressive improvement and uncontraction of CoRe- GD drawings. The graphs taken from the suitesparse matrix collection.
22

---

Published as a conference paper at ICLR 2024
Figure 10: More examples of the evolution of CoRe-GD drawings. The model was trained on the suitesparse dataset and generates 3-dimensional drawings.
23


Reviews:
[{"review_id": "fn3tqWG4xH", "reviewer": "Reviewer_hLpG", "summary": "Stress is a widely used metric for graph visualization, which aims to find geometric embeddings of graphs that optimize certain criteria. As the stress optimization presents computional challenges due to its inherent complexity and is usually solved using heuristics in practice. The authors introduce a scalable Graph Neural Network based Graph Drawing framework with sub-quadratic runtime that can learn to optimize stress. Inspires by classical stress optimization techniques and force-directed layout algorithms, they create a coarsening hierarchy for the input graph. Beginning at the coarsest level, they iteratively refine and un-coarsen the layout, until generating an embedding for the original graph. The authors perform empirical evaluation demonstrating that their framework achieves SOTA while remaining scalable.", "questions": "1. Please give a more clear illustration about the graph after being processed by each module in your framework.\n2. 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.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.\tExtensive examples, clear explanations,  step-by-step formulations, and open-sourced code make this research solid, convincing and reproducible. The presentation is obviously above the average.\n2.\tExtensive experiments demonstrate the effectiveness and the scalability of the proposed framework. \n3.\tThis research provide insights about cobining the GNN with the graph combinational optimization (i.e. graph visualization). I believe this paper would benifit to the graph mining community.", "weaknesses": "1. 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.\n\n2. The work is related with graph condensation or graph summarization, and some baselines about graph condensation or summarizarion should be included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Zh9fElwLOX", "reviewer": "Reviewer_GnFx", "summary": "CoRe-GD (CGD) is a effective novel graph drawing algorithm designed with scalability and computational efficiency in mind. The main block of CGD does recurrent layout optimization using two graph neural networks and a graph rewiring step. To achieve better scalability, CGD uses an iterative graph coarsening procedure. The procedure first learns a layout for the coarsest graph view and iteratively uncoarsens the graph and recomputes the optimal layout based on the prior, coarser graph layout. \n\nExperiments show CGD is effective on an array of datasets with both real and synthetic graphs. Results also show that CGD is effective even on graph sizes larger than those seen during training. \n\nCGD has scalability evidenced both in theoretical computational complexity as well as in experiments.", "questions": "“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)\n\nThe figure 9 visualizations are a very nice way to see the effect of the graph coarsening. \n\nThough 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. \n\nWhy is DNN^2 excluded from figure 6?\n\nWhy does Figure 6.A cutoff at 5000 while 6.B cuts out at 25000?\n\nWhile I believe I have a strong understanding of the algorithm presented, I do not have a good sense of this field and the most important features, datasets, and related work.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "Originality - This work presents an original algorithm for learning graph drawing. The model also uses a recurrent GNN, enabled by memory replay. This itself is relatively original, though there are some similar related works. \nQuality - This work is high quality. The model is clear and based on a solid foundation. The results and experiments show significant improvement. \nClarity - The work is clear, understandable, and well defined. Great clarity. \nSignificance - Outside of the Graph Drawing community, it is hard to see this having a broader impact. While the authors claim in the conclusion that because it is embedding based, CGD could be expanded to other applications, there is no direct evidence of that presented. Perhaps it could be used as positional embeddings in graph transformers.", "weaknesses": "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. \n\nOtherwise, this is a pretty strong, high quality paper. \n\nFigure 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.\n\nneato 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. \n\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iwpQ16q73B", "reviewer": "Reviewer_Avgq", "summary": "The paper proposes CoreGD, which is a graph drawing framework which uses GNN submodules.  CoreGD improves over alternative methods in stress metrics and demonstrates empirically better scalability properties.", "questions": "- 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). \n\n- 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?  \n\n- Section 3's overview of Core-GD is quite hard to understand.  Some design choices aren't obvious to the reader: (i) why do we need two convolutions (Conv_E and Conv_R), (ii) what's the purpose of the rewiring module?  How exactly does the GRU fit in?  Structuring this section with equations which the reader can follow from inputs to position coordinates would have probably helped understand the sequence of operations\n\n- Table 1 suggests that Core-GD seems to achieve similar performance to DeepGD -- I'm not familiar with the differences with these methods, but some discussion regarding the speed advantages of CoreGD compared to DeepGD would be helpful to contextualize the added value of using the algorithm proposed by the authors.  \n\n- Being able to coarsen aggressively before initializing input features seems like a great advantage for large graphs -- I'm curious what the largest graph the authors were able to visualize with CoreGD is given this benefit.  The graphs in Table 1 seem to be mostly small -- are other graph drawing approaches (non-neural or neural) better able to support larger graphs?  In general, a runtime-stress curve which shows the relative performance of multiple methods would be really helpful to see where CoreGD lies on the frontier.\n\n---\n\nUpdated my score after reading the authors' responses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. The point about scale-invariant stress is nuanced and an astute observation -- the authors' lemma 2 helps support the scaling choice.\n\nS2. Performance in graph drawing benchmarks appears to be quite strong in terms of stress metrics compared to alternative approaches.  \n\nS3. Authors were able to demonstrate better scaling performance than the next-best performing alternative (DeepGD it seems) in Figure 6 -- CoreGD seems to scale considerably better and with better stability.", "weaknesses": "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).\n\nW2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZcAtMzUVxU", "reviewer": "Reviewer_Te7K", "summary": "The manuscript presents a subquadratic graph drawing algorithm aimed at large-scale graph visualization. The authors propose a hierarchical optimization process to visualize node embeddings from coarse to fine. Additionally, a positional rewiring module is utilized to improve the connection between nodes with potential relationships. The experiments show that the proposed method not only accelerates computations but also improves the visualization quality.", "questions": "Please see my comments to paper weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The paper is well-written with clear objectives and results.\n* The algorithm detail is clearly defined and described.\n* Alternative methods are discussed and compared for node initialization and positional rewiring step.\n* The experimental section evaluates the state-of-the-art methods qualitatively and quantitatively.", "weaknesses": "* 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.\n* 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}.\n* 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.\n* More graph drawing quality metrics can be reported, such as shape-based metrics and edge crossing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)