# subspace

60 %
40 %
News-Reports

Published on June 19, 2007

Author: Arkwright26

Source: authorstream.com

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

## #iterations presentations

#### Stamatiou

 User name: Comment:

## Related presentations

#### FAP CEO is One of the Clicker Games Disguised as B...

November 21, 2018

#### Black Friday Sale 2018, Black Friday Furniture Dea...

November 21, 2018

#### What is Glutathione and What It is For

November 21, 2018

#### Do You Really Need An Agent For A Property Search

November 21, 2018

#### How to prepare a winning government tender proposa...

November 21, 2018

#### Asia-Pacific Healthcare Analytics Market

November 21, 2018

## Related pages

### Linear subspace - Wikipedia, the free encyclopedia

In linear algebra and related fields of mathematics, a linear subspace (or vector subspace) is a vector space that is a subset of some other (higher ...

### Subspace - Wikipedia, the free encyclopedia

In mathematics. A space inheriting all characteristics of a parent space. A subset of a topological space endowed with the subspace topology; Linear ...

### Subspace -- from Wolfram MathWorld

Subspace. Let be a real vector space (e.g., the real continuous functions on a closed interval, two-dimensional Euclidean space, the twice differentiable ...

### Subspace - Memory Alpha - Wikia

Subspace is an integral part of the space-time continuum, distinct, yet coexistent with normal space. Subspace and normal space are confluenced together.

### dict.cc | subspace | Wörterbuch Englisch-Deutsch

Übersetzung für subspace im Englisch-Deutsch-Wörterbuch dict.cc.

### Urban Dictionary: subspace

Subspace is one of those "once-in-a-lifetime" gaming programs that decrease in popularity due to its lack of advertising. Its also the most generic ship ...