subspace

Information about subspace

Published on June 19, 2007

Author: Arkwright26

Source: authorstream.com

Content

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

Variational methods
07. 01. 2018
0 views

Variational methods

DLBLR talk
28. 05. 2017
0 views

DLBLR talk

Hierachical clustering
04. 09. 2016
0 views

Hierachical clustering

Stamatiou
29. 10. 2007
0 views

Stamatiou

Related presentations


Other presentations created by Arkwright26

transportation
07. 11. 2007
0 views

transportation

wonderful world
19. 06. 2007
0 views

wonderful world

2006911155950435
28. 04. 2008
0 views

2006911155950435

dietrich
17. 04. 2008
0 views

dietrich

ME Individual DM JG 2006
16. 04. 2008
0 views

ME Individual DM JG 2006

H106n
14. 04. 2008
0 views

H106n

DM GlobalFDI Movements240306
13. 04. 2008
0 views

DM GlobalFDI Movements240306

may30
10. 04. 2008
0 views

may30

Ulad using crop residues
09. 04. 2008
0 views

Ulad using crop residues

coral reef and climate change
07. 04. 2008
0 views

coral reef and climate change

Ian Brinkley DtF 07 06
30. 03. 2008
0 views

Ian Brinkley DtF 07 06

Temperature
14. 02. 2008
0 views

Temperature

AP Review 1400 1800
20. 02. 2008
0 views

AP Review 1400 1800

New Sony
03. 10. 2007
0 views

New Sony

Literary Vocabulary Rhyme
10. 10. 2007
0 views

Literary Vocabulary Rhyme

Chapter1McMurry
13. 10. 2007
0 views

Chapter1McMurry

FinanceTransition
16. 10. 2007
0 views

FinanceTransition

rexcor baker
15. 10. 2007
0 views

rexcor baker

kakande
28. 11. 2007
0 views

kakande

bernsteintwo
16. 10. 2007
0 views

bernsteintwo

What Is Internal Control
29. 10. 2007
0 views

What Is Internal Control

11 40 063
07. 11. 2007
0 views

11 40 063

Il Nazismo
14. 11. 2007
0 views

Il Nazismo

kryukov 20041004
12. 10. 2007
0 views

kryukov 20041004

1015 1
19. 11. 2007
0 views

1015 1

AI 120 Examples
17. 10. 2007
0 views

AI 120 Examples

galaxy physics
01. 12. 2007
0 views

galaxy physics

Qualitative tools
29. 11. 2007
0 views

Qualitative tools

pannebecker
03. 01. 2008
0 views

pannebecker

infectious
05. 01. 2008
0 views

infectious

b e flows
07. 01. 2008
0 views

b e flows

CSI pres
07. 10. 2007
0 views

CSI pres

1A Quality of our Water
02. 01. 2008
0 views

1A Quality of our Water

OPVII AldusEquity
01. 10. 2007
0 views

OPVII AldusEquity

wheat 1
04. 10. 2007
0 views

wheat 1

Lexical Semantics II
21. 11. 2007
0 views

Lexical Semantics II

Forklift Standard 12 14 99
27. 02. 2008
0 views

Forklift Standard 12 14 99

manuel scott powerpoint
25. 03. 2008
0 views

manuel scott powerpoint

skos ecoterm 2006
19. 06. 2007
0 views

skos ecoterm 2006

services
19. 06. 2007
0 views

services

Working with Automatic PGA
19. 06. 2007
0 views

Working with Automatic PGA

wider context
19. 06. 2007
0 views

wider context

weinberg wfi
19. 06. 2007
0 views

weinberg wfi

VS Mod Presentation
19. 06. 2007
0 views

VS Mod Presentation

Unicode from a distance
19. 06. 2007
0 views

Unicode from a distance

Unicode AndIndia
19. 06. 2007
0 views

Unicode AndIndia

tunable abw
19. 06. 2007
0 views

tunable abw

Tsunefum Mizuno sep14 05
19. 06. 2007
0 views

Tsunefum Mizuno sep14 05

tlstut
19. 06. 2007
0 views

tlstut

synergy redesign demo
19. 06. 2007
0 views

synergy redesign demo

acadien
19. 06. 2007
0 views

acadien

y report
19. 06. 2007
0 views

y report

Tom Worthington
19. 06. 2007
0 views

Tom Worthington

Millennials
14. 07. 2007
0 views

Millennials

vienna a6
19. 06. 2007
0 views

vienna a6

unit armorer sustainment
28. 02. 2008
0 views

unit armorer sustainment

SCI1010 C2
13. 11. 2007
0 views

SCI1010 C2

Slides 2006 fin year web3
19. 06. 2007
0 views

Slides 2006 fin year web3

MNEaula07
28. 12. 2007
0 views

MNEaula07

OUR SCAVENGER HUNT edited
16. 11. 2007
0 views

OUR SCAVENGER HUNT edited

ImplicationsResearch
03. 01. 2008
0 views

ImplicationsResearch

Jonh Roberts
31. 07. 2007
0 views

Jonh Roberts

wstechnology
19. 06. 2007
0 views

wstechnology

DiapoAnglaisdÃf
23. 10. 2007
0 views

DiapoAnglaisdÃf

QM chip
15. 10. 2007
0 views

QM chip

zend talk
19. 06. 2007
0 views

zend talk

seminarpresent
24. 02. 2008
0 views

seminarpresent

High School Counsellor Session
23. 11. 2007
0 views

High School Counsellor Session

xml cop feb05
19. 06. 2007
0 views

xml cop feb05

Value of Org RWG
19. 06. 2007
0 views

Value of Org RWG

Promo wkshp Downes
13. 03. 2008
0 views

Promo wkshp Downes

yw
17. 10. 2007
0 views

yw

WP1b
15. 10. 2007
0 views

WP1b

Regency Traffic111508 3 1
11. 03. 2008
0 views

Regency Traffic111508 3 1

Superstar
19. 06. 2007
0 views

Superstar

BUS 400
05. 10. 2007
0 views

BUS 400

950321
11. 10. 2007
0 views

950321

perry presentation
04. 03. 2008
0 views

perry presentation

vergados 1
20. 11. 2007
0 views

vergados 1

vlad
19. 06. 2007
0 views

vlad

Darstellung des HH AZM
15. 11. 2007
0 views

Darstellung des HH AZM