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

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.