Loading...
Accelerating network layouts using graph neural networks
Title / Series / Name
Publication Volume
Publication Issue
Pages
Editors
Keywords
General Chemistry
General Biochemistry,Genetics and Molecular Biology
General Physics and Astronomy
General Biochemistry,Genetics and Molecular Biology
General Physics and Astronomy
URI
https://hdl.handle.net/20.500.14018/27121
Abstract
Graph layout algorithms used in network visualization represent the first and the most widely used tool to unveil the inner structure and the behavior of complex networks. Current network visualization software relies on the force-directed layout (FDL) algorithm, whose high computational complexity makes the visualization of large real networks computationally prohibitive and traps large graphs into high energy configurations, resulting in hard-to-interpret “hairball” layouts. Here we use Graph Neural Networks (GNN) to accelerate FDL, showing that deep learning can address both limitations of FDL: it offers a 10 to 100 fold improvement in speed while also yielding layouts which are more informative. We analytically derive the speedup offered by GNN, relating it to the number of outliers in the eigenspectrum of the adjacency matrix, predicting that GNNs are particularly effective for networks with communities and local regularities. Finally, we use GNN to generate a three-dimensional layout of the Internet, and introduce additional measures to assess the layout quality and its interpretability, exploring the algorithm’s ability to separate communities and the link-length distribution. The novel use of deep neural networks can help accelerate other network-based optimization problems as well, with applications from reaction-diffusion systems to epidemics.
Topic
Publisher
Place of Publication
Type
Journal article
Date
2023-03-21
Language
ISBN
Identifiers
10.1038/s41467-023-37189-2