Graph Drawing Stress Model with Resistance Distances

\authororcid Yosuke Onoue0000-0003-2739-3249 · 2025

Read Graph Drawing Stress Model with Resistance Distances by \authororcid Yosuke Onoue0000-0003-2739-3249 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21901.txt.

Introduction

Yosuke Onoue challenges a convention in graph drawing, the algorithms that lay out networks as readable pictures. Stress-based drawing places nodes so that picture distances match graph distances, traditionally the shortest-path distance. Shortest paths, however, capture only local structure and can distort the global shape of a network.

Onoue proposes resistance distance instead, a quantity from the graph Laplacian's spectrum that electrical engineers know as effective resistance. Resistance distance reflects global structure and embeds naturally into Euclidean space. The accompanying algorithm, Omega, precomputes a fast resistance-distance embedding and samples random node pairs for stochastic gradient descent. Random sampling proved more robust than earlier pivot-based sampling, giving lower, more stable stress. Experiments showed better neighborhood preservation and cluster faithfulness. The algorithm runs in linear time in the number of edges.

Catalog record

CREATOR\authororcid Yosuke Onoue0000-0003-2739-3249
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-21901

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Graph Drawing Stress Model with Resistance Distances \authororcid Yosuke Onoue0000-0003-2739-3249 Abstract This paper challenges the convention of using graph-theoretic shortest distance in stress-based graph drawing. We propose a new paradigm based on resistance distance, derived from the graph Laplacian’s spectrum, which better captures global graph structure. This approach overcomes theoretical and computational limitations of traditional methods, as resistance distance admits a natural isometric embedding in Euclidean space. Our experiments demonstrate improved neighborhood preservation and cluster faithfulness. We introduce Omega, a linear-time graph drawing algorithm that integrates a fast resistance distance embedding with random node-pair sampling for Stochastic Gradient Descent (SGD). This comprehensive random sampling strategy, enabled by efficient pre-computation of resistance distance embeddings, is more effective and robust than pivot-based sampling used in prior algorithms, consistently achieving lower and more stable stress values. The algorithm maintains O ⁡ ( | E | ) O(|E|) complexity for both weighted and unweighted graphs. Our work establishes a connection between spectral graph theory and stress-based layouts, providing a practical and scalable solution for network visualization. \onlineid 6265 \vgtccategory Research \vgtcpapertype algorithm/technique \authorfooter Yosuke Onoue is with Nihon University. E-mail: [email protected] \teaser A comparison of layouts for the web-Stanford graph ( |V|=255,265,|E|=1,941,926 ) generated by SparseSGD (Conventional) and Omega (Proposed). Nodes are colored based on their core number. The conventional SparseSGD method produces a dense, unreadable "hairball," obscuring the graph’s structure. In contrast, our proposed Omega algorithm successfully untangles the graph, revealing distinct structural components and separating the high-core nodes (center) from peripheral structures. The zoomed-in views highlight how Omega preserves the fine-grained local structure that is lost in the SparseSGD layout. Introduction keywords Stress model, resistance distance, force-directed layout, graph drawing, network visualization Force-directed algorithms are a cornerstone of network visualization, producing aesthetically pleasing and structurally meaningful layouts [ 36 ] . Stress models seek to arrange nodes such that geometric distances match ideal graph-theoretic shortest distances [ 20 ] . For decades, the community has relied on graph-theoretic shortest distance as the standard. This convention presents theoretical and computational challenges. Graph-theoretic shortest distances may not admit an isometric embedding in Euclidean space [ 22 ] , meaning any layout has inherent stress. Computing all-pairs shortest paths is expensive, particularly for large or weighted graphs. The choice of ideal distance profoundly impacts layout quality, underscoring the need for a metric better suited for specific visual tasks [ 30 ] . We propose replacing graph-theoretic shortest distance with low-rank resistance distance as the ideal metric for stress models. Resistance distance, derived from the pseudo-inverse of the graph Laplacian [ 19 ] , offers key advantages. It can be isometrically embedded in Euclidean space, eliminating inherent stress and making it compatible with stress optimization. This spectral foundation allows resistance distance to capture global graph structure, such as clusters and bottlenecks, more effectively than path-based measures. While shortest-path layouts excel at path-following, resistance-distance layouts produce improved neighborhood and cluster faithfulness. Our experiments confirm clear improvements in these metrics over conventional methods. To operationalize these benefits, we introduce Omega, a novel linear-time graph drawing algorithm built upon the SparseSGD framework [ 40 ] . Omega is our name for the complete layout method that integrates three key components: (1) RDMDS for computing low-rank resistance distance embeddings, (2) a novel comprehensive random node-pair sampling strategy, and (3) SparseSGD optimization. The low-rank structure of resistance distance allows for the efficient pre-computation of an embedding, which forms the basis of our algorithm and enables the random sampling approach. This sampling strategy is the key algorithmic innovation that distinguishes Omega from traditional pivot-based methods, consistently achieving lower stress values than the pivot-based strategies used in prior SparseSGD implementations. The result is an algorithm that produces higher-quality visualizations, with a favorable asymptotic complexity that is particularly advantageous for weighted graphs. The main contributions of this work are: • A new stress model paradigm using low-rank resistance distance as the ideal distance, which yields layouts with improved neighborhood preservation and cluster faithfulness compared to traditional models. • Omega, a novel linear-time graph drawing algorithm that integrates resistance distance computation with a random sampling strategy for SparseSGD. We show this sampling is more effective and robust than pivot-based methods, a benefit unlocked by the efficient, on-demand calculation of resistance distances. • A demonstration of Omega’s O(|E|) complexity for both weighted and unweighted graphs, offering a theoretical performance advantage over existing scalable stress-based methods. The remainder of this paper is organized as follows. Section 1 reviews related work in graph drawing, stress models, and resistance distance applications. Section 2 introduces the mathematical foundation of resistance distances and presents our stress model formulation. Section 3 presents RDMDS, a linear-time algorithm for obtaining low-rank resistance distance embeddings in Euclidean space. Section 4 describes the Omega algorithm in detail. This includes the linear-time eigenvalue computation and the SparseSGD framework with resistance distances. Section 5 presents computational experiments. We compare faithfulness metrics, drawing results, sampling strategies, and computational performance. Section 6 provides a gallery of drawing examples and discusses their qualitative features. Section 7 discusses the theoretical implications and practical benefits of our approach. Finally, Section 8 concludes the paper and outlines directions for future research. 1 Related Work Our work builds upon three main areas of research: stress-based graph drawing, spectral graph theory, and the use of resistance distance in graph algorithms. 1.1 The Evolution of Stress Models in Graph Drawing Kamada and Kawai [ 17 ] pioneered "stress" in graph drawing, formulating layout as an energy minimization problem matching geometric distances to graph-theoretic shortest distances. Gansner, Koren, and North [ 15 ] achieved a breakthrough with stress majorization. Scalable methods include multilevel techniques [ 14 , 26 ] , low-rank approximations [ 18 ] , and sparse models. Ortmann et al. [ 32 ] introduced the sparse stress model, optimizing over a sparse subset of node pairs. Zheng et al. [ 40 ] adapted this to SGD with SparseSGD, using pivot-based sampling for million-node graphs. Brandes and Pich [ 2 ] proposed PivotMDS for classical MDS. Extensions include constrained layouts [ 9 , 38 , 8 ] and non-Euclidean spaces [ 27 , 4 , 39 , 28 ] . However, these works predominantly use graph-theoretic shortest distance. The choice of ideal distances has received limited discussion [ 30 ] . We propose resistance distance as a theoretically grounded alternative. 1.2 Spectral Graph Theory and Resistance Distance Resistance distance, first introduced by Klein and Randic [ 19 ] , is a metric derived from an analogy to electrical circuits, where it represents the effective resistance between two nodes. It is formally defined for any pair of vertices and has found applications in diverse fields, from chemistry to machine learning [ 19 ] . Its theoretical foundation lies in spectral graph theory [ 5 ] , which studies a graph’s properties via the eigenvalues and eigenvectors of its Laplacian matrix. The eigenvectors of the Laplacian are central to the definition of resistance distance and are famously used in spectral clustering to find community structure [ 37 ] . Koren [ 21 ] also explored the direct use of Laplacian eigenvectors for spectral graph drawing, establishing a fundamental link between a graph’s spectral properties and its visual representation. From

Read the complete text