Presentation Transcript
Graph Drawing by Subspace Optimization : Graph Drawing by Subspace Optimization Yehuda Koren
ATandamp;T Labs-Research
Visualization of Large Graphs : Visualization of Large Graphs Untangling is complicated
Time and space complexity Drawing area limitations
Orientation/navigation issues
Visualization of Large Graphs : We address the algorithmic challenges Visualization of Large Graphs Untangling is complicated
Time and space complexity
Force-directed graph drawing : Force-directed graph drawing Graph drawing = Energy minimization
Hence, the drawing algorithm is an optimization process Initial (random) layout Final (nice) layout Iteration 1: Iteration 2: Iteration 3: Iteration 4: Iteration 5: Iteration 6: Iteration 7: Iteration 8: Iteration 9:
Force-directed graph drawing : Suitable energies induce:
Adjacency preservation: short edges
Uniform node distribution: prevent overcrowding
Symmetry: isomorphic sub-graphs are drawn identically Force-directed graph drawing Graph drawing = Energy minimization
Hence, the drawing algorithm is an optimization process Initial (random) layout Final (nice) layout
We concentrate on two methods : We concentrate on two methods 2. Stress minimization 1. Eigen-projection More details later…
Drawing graphs in subspaces : Drawing graphs in subspaces 2-D layout is characterized by axes
Constrain layout axes to vector space
Replace problem as follows:
Benefits of working in subspace : Benefits of working in subspace Smaller search space may reduce #iterations
Can simplify energy (reduce time and space requirements)
Easier to find the global optimizer
But how can we create such a subspace???
Two stages: : Two stages:
Preliminaries : Preliminaries A k-D subspace is defined by a set of k basis vectors
We arrange the basis in the matrix
Our subspace is - the range of
Subspace restriction can be easily plugged into algorithms based on matrix algebra
Adequate subspaces for graph drawing : Adequate subspaces for graph drawing Find a set of basis vectors, such that:
Each vector is a 'nice' embedding of the graph (or part of it)
Fast to compute
We offer two options:
High dimensional embedding (HDE)
Low eigenspace of the Laplacian
1. The HDE subspace : 1. The HDE subspace Choose k pivot nodes, uniformly distributed on the graph: Here, k=50, (this is a typical number, independent of |V|)
Constructing a k-D HDE : Constructing a k-D HDE
Vector vi shows the graph from the 'viewpoint' of pi , the i –th pivot node
Smart combination of many such viewpoints can yield a nice layout Basis vector vi is associated with pivot node pi
The basis vectors are defined as:
Graph-theoretic distance between nodes pi and j
2. Low eigenspace of Laplacian : 2. Low eigenspace of Laplacian The Laplacian of the graph is the matrix L, where:
Low eigenspace of Laplacian : Low eigenspace of Laplacian The basis vectors are the k eigenvectors of the Laplacian associated with the lowest eigenvalues
It is known that these vectors minimize the ratio:
- The Euclidean distance between i and j in the k-D layout Shorten edges while separating non-adjacent nodes
Optimization within subspace : Optimization within subspace
Eigen-projection : Eigen-projection Solve: Shorten edges while separating non-adjacent nodes Squared edge lengths Squared distances between non-adjacent nodes
Eigen-projection : Eigen-projection Equivalent to: Optimal solution is the two low eigenvectors of L
Eigen-projection in subspace : Eigen-projection in subspace – nxk matrix of basis vectors Reminder: Substitute: n-D problem k-D problem
Eigen-projection in subspace : Eigen-projection in subspace Solution - the two low generalized eigenvectors of:
Eigen-projection in subspace : Eigen-projection in subspace Solution - the two low generalized eigenvectors of:
Results : Results Bfw782a graph (|V|=782, |E|=3,394) Eigen-projection Eigen-projection in 50-D HDE
Results : Results 4elt graph (|V|=15,606, |E|=45,878) Eigen-projection Eigen-projection in 50-D HDE
Slide24 :
The Stress energy : The Stress energy Introduced by [Kamada and Kawai, 1989]; based on minimizing the energy:
A nice drawing relates to good isometry
Euclidean distance
The Stress energy : The Stress energy Global optimization is impossible
Common optimization methods:
Gradient descent
Localized Newton-Raphson
Majorization
Minimizing Stress by majorization : Minimizing Stress by majorization We cannot express the stress energy by matrix algebra…
But, we can bound it using matrix algebra!
We use a convex quadratic function that touches the stress at current point: Optimum by solving nxn system:
Slide28 : Layouts Stress energy
Slide29 : Layouts The stress must be decreased Stress energy
Slide30 : Layouts Again… Stress energy
Slide31 : Layouts And again… Stress energy
Slide32 : Layouts …Till convergence Stress energy
Optimizing Stress in subspace : Optimizing Stress in subspace Perform each iteration of the majorization algorithm within a subspace Substitute: n-D problem k-D problem
Optimizing Stress in subspace : Optimizing Stress in subspace Minimum is the solution of a kxk linear system:
Sparse Stress energy : Sparse Stress energy Optimization within a subspace allows us to use sparse stress energy
Full stress - terms (all pairs): Choose a set of pivot nodes, uniformly distributed on the graph
A sparse stress contains terms
Sparse Stress energy : Sparse Stress energy Space limitations allow full stress to deal with up to ~20,000 nodes on 32bit memory
Sparse energy vastly reduces time and space limitations
Works much better in subspace!
Why?
Sparse energy cannot characterize the optimal layout in the full space
But, it can distinguish the nice layout from other layouts in a carefully crafted small subspace How about quality of results??
Results might be pretty good : Results might be pretty good Qh882 |V|=882, |E|=1533 Finan512 |V|=74,752, |E|=261,120
But sometimes not as good as desired… : But sometimes not as good as desired… Sparse stress in 50-D HDE Full, unrestricted stress Bcpwr07 |V|=1612, |E|=2106
Smart initialization by subspace restriction : Smart initialization by subspace restriction A significant decrease of overall running time
More robust against local minima
The 'food chain' of layout optimization:
Conclusions : Conclusions Restriction to carefully designed subspaces can accelerate layout creation
Also, can serve as a smart initialization to a more demanding process
Works with algorithms involving matrix algebra
Still looking for better ways to construct subspaces
The End : The End
Catch the
buzz on authorSTREAM
Copyright © 2002-2008 authorSTREAM. All rights reserved.