subspace

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