Introduction
This is a analysis of paper “Laplacian-based Dynamic Graph Visualization”[1], telling a method using Laplacian Constrained Distance Embedding defined in giving constraint to users’ input subgraphs[2], to draw online dynamic graph. A method called stress majorization[3] is also used in this approach.
The most important issue in dynamic graph drawing is to preserve the mental map[4]. In this paper, the author choose to firstly fully generate the force directed graph for the new layout, then use LCDE to let important structures maintain their former structure.
Stress Majorization
Problem
Minimize stress function (here we suppose the case of 2D, so $x_i$ is a vector)
$$
E=\sum_{i,j\in N}w_{i,j}(\Vert x_i-x_j\Vert-d_{ij})^2
$$
Equation transformation
$$E=\sum_{i,j\in N}(w_{i,j}d_{ij}^2-2w_{i,j}d_{i,j}\Vert x_i-x_j\Vert+w_{i,j}\Vert x_i-x_j\Vert ^2)$$
$\sum_{i,j\in N}w_{i,j}d_{ij}^2$ is a constant, so we focus on the next two parts.
As already demonstrated in blog ACE,
$$\sum_{i,j\in N}w_{i,j}\Vert x_i-x_j\Vert^2=Tr(X^TL_wX)$$
As to the second term, Cauchy-Schwartz inequality:
$$
\Vert X\Vert\Vert Y\Vert\ge X^TY
$$
so
$$
\Vert x_i-x_j\Vert \Vert z_i-z_j\Vert \
\ge (x_i-x_j)^T(z_i-z_j)
$$
and
$$
\sum_{i,j\in N}\Vert x_i-x_j\Vert \ge \sum_{i,j\in N}inv(\Vert z_i-z_j\Vert )(x_i-x_j)^T(z_i-z_j)
$$
so the second term can be represented as:
$$
-w_{i,j}d_{i,j}\Vert x_i-x_j\Vert \le -Tr(X^TL_{w,z}Z)
$$
with
$$
L_{i,j}=\begin{cases}
-w_{i,j}d_{i,j}inv(\Vert z_i-z_j\Vert )&\text{$i\neq j$}\
-\sum_{i\neq j}L_{i,j}&\text{$i=j$}
\end{cases}
$$
Finally, we bound the stress function as:
$$
F^Z(X)=\sum_{i,j\in N}w_{i,j}d_{ij}^2-2Tr(X^TL_{w,z}Z)+Tr(X^TL_wX)\
E(X)\le F^Z(X)
$$
We find the minimum of F^Z(X) by differentiating by X:
$$
L_wX=L_{w,z}Z
$$
Remove the zero solution: $X_1=0$, the last n-1 rows of $L_w$ and $L_{w,z}$ form symetric positive definitive matrix.
Optimization process
We use here an iterative process, so that for each iteration, $E(t+1)\le E(t)$, we solve
$$
L_wX(t+1)=L_{w,z}X(t)
$$
in practice, we terminate the iteration when:
$$
\frac{E(X(t+1))-E(X(t))}{E(X(t))}<\epsilon
$$
We can solve the equation in each iteration by using Conjugate Gradient or Cholesky Factorization.
Intuitive interpretation
Instead of the two solutions mentioned before, there are many other ways to solve a non-linear equation, as KAMADA and KAWAI have shown, the Newton-Raphson iteration can help find local minimum, this paper shows another way.
In the tth iteration, we have already known that $\hat{X}=X(t-1)$ and we want to know $X(t)$
Considering the $i^{th}$ node, the function to be solved can be transmitted into:
$$
\sum_{j\neq i}w_{i,j}x_i－\sum_{j\neq i}w_{i,j}x_j=-\sum_{j\neq i}w_{i,j}d_{i,j}inv(\Vert \hat{x_j}-\hat{x_i}\Vert)\hat{x_j}+\sum_{j\neq i}w_{i,j}d_{i,j}inv(\Vert \hat{x_j}-\hat{x_i}\Vert)\hat{x_i}
$$
So
$$
x_i=\frac{w_{i,j}\sum_{j\neq i}(x_j+d_{i,j}(\hat{x_i}-\hat{x_j})inv(\Vert \hat{x_i}-\hat{x_j}\Vert))}{\sum_{j\neq i}w_{i,j}}
$$
We can see that for each node $j$, the ideal position of $i$ is
$$x_j+d_{i,j}\frac{\hat{x_i}-\hat{x_j}}{\Vert \hat{x_i}-\hat{x_j}\Vert}$$
We can use this to do refinement of $x_i$’s position, following the idea of KAMADA:
$$
x_i(t)\leftarrow\frac{w_{i,j}\sum_{j\neq i}(x_j+d_{i,j}(\hat{x_i}-\hat{x_j})inv(\Vert \hat{x_i}-\hat{x_j}\Vert))}{\sum_{j\neq i}w_{i,j}}
$$
Laplacian Constrained Distance Embedding
In normal graph layout, our basic goal is to minimize stress: $E=\sum_{i,j\in N}w_{i,j}(\Vert x_i-x_j\Vert -d_{ij})^2$ where $d_{ij}$ is the optimal distance of node i and j.
In this case, we want to make constraint to some structures, for example, maintain the user defined subgraphs in paper[2], so we change the stress function:
$$
E=\sum_{i,j\in F}w_{i,j}(\Vert x_i-x_j\Vert -d_{ij})^2+\alpha\sum_{i,j\in V}w_{i,j}(\Vert x_i-x_j\Vert -d_{ij})^2
$$
Where F is the set of nodes we want to give constraint.
In my opinion, we can use stress majorization to solve this problem.
Solution
Instead of using stress majorization, a more simplified approach is introduced:
$$
E=\sum_{i,j\in F}w_{i,j}(\Vert x_i-x_j\Vert -d_{ij})^2+\alpha\sum_{i,j\in N}w_{i,j}(\Vert x_i-x_j\Vert -d_{ij})^2
$$
Equation transformation
To minimize E, we derivate E with respect to X.
$$
\begin{aligned}
\frac{\partial E}{\partial X} &=\sum_{i\in N}\frac{\partial E}{\partial x_i}\
&=2\sum_{i,j\in F}w_{i,j}(\Vert x_i-x_j\Vert -d_{ij})\frac{x_i-x_j}{\Vert x_i-x_j\Vert }\&+2\alpha\sum_{i,j\in N}w_{i,j}(\Vert w_i-w_j\Vert -d_{ij})\frac{x_i-x_j}{\Vert x_i-x_j\Vert }\
&=0
\end{aligned}
$$
$$
\sum_{i,j\in F}w_{i,j}(x_i-x_j)+\alpha\sum_{i,j\in N}w_{i,j}(x_i-x_j)\
=\sum_{i,j\in F}w_{i,j} d_{ij}\frac{x_i-x_j}{\Vert x_i-x_j\Vert }+\alpha\sum_{i,j\in N}w_{i,j} d_{ij}\frac{x_i-x_j}{\Vert x_i-x_j\Vert }
$$
By expand x in F to V, we can obtain:
$$
(L_w^F+\alpha L_w^N)X=(L_{w,d}^F+\alpha L_{w,d}^N)X
$$
as
$$
L_wX=\sum_{i,j}w_{i,j}(x_i-x_j)
$$
The left side is linear and right side is not.
With
$$
\begin{aligned}
L_w^E&=\begin{cases}
-\sum_{i,l\in E}w_{i,l}&\text{$i=j$}\
w_{i,j}&\text{$i\neq j\&{i,j}\in E$}\
0&\text{Otherwise}
\end{cases}\
L_{w,d}^E&=\begin{cases}
-\sum_{i,l\in E}\frac{w_{i,l}d_{il}}{\Vert x_i-x_j\Vert }&\text{$i=j$}\
\frac{w_{i,j}d{ij}}{\Vert x_i-x_j\Vert }&\text{$i\neq j\&{i,j}\in E$}\
0&\text{Otherwise}
\end{cases}
\end{aligned}
$$
Solve equation
So our purpose is to solve the equation:
$$
(L_w^F+\alpha L_w^N)X=(L_{w,d}^F+\alpha L_{w,d}^N)X
$$
This is not linear so an approach similar to what used in stress majorization[5] is applied and can be presented as below.
$$
(L_w^F+\alpha L_w^N)X(t+1)=(L_{w,d}^F+\alpha L_{w,d}^N)X(t)
$$
%algorithm using iteration
%X0 is randomly chosen
repeat
calculate X(t+1) in left side using X(t) in right side
X(t)=X(t+1)
until
$\frac{E(X(t+1))-E(X(t))}{E(X(t))}<\epsilon$
Online Dynamic Layout
The online dynamic layout uses all the algorithms mentioned before.
- ${G_0,…,G_n}$ a sequence of graphs
- ${L_0,…,L_n}$ a sequence of corresponding layouts
- $G_0$ is generated by using force directed graph
- $E_n$ edge set of $G_n$
- $V_n$ node set of $G_n$
Initial Layout
As we have $G_n,G_{n-1},L_{n-1}$, we draw new force directed layout $L^*$ using $L_{n-1}$.(method may be explained in other bolgs)
Layout Refinement
After obtaining $L^*$, we define a new stress function:
$$
E=\sum_{i,j\in E_n}\frac{(\Vert x_i-x_j\Vert -d_{i,j}^*)^2}{d_{i,j}^2}+\alpha\sum_{i,j\in V_{n}\cap V_{n-1}}\frac{(\Vert x_i-x_j\Vert -d_{i,j})^2}{d^2_{i,j}}
$$
Then we can use LCDE mentioned before.
Reference
[1]Che L, Liang J, Yuan X, et al. Laplacian-based dynamic graph visualization[C]// Visualization Symposium. IEEE, 2015:69-73.
[2]Cao L, Zhou S. Intelligent Graph Layout Using Many Users’ Input.[J]. IEEE Transactions on Visualization & Computer Graphics, 2012, 18(12):2699-2708.
[3]Gansner E R, Koren Y, North S. Graph Drawing by Stress Majorization[C]// International Symposium on Graph Drawing. Springer, Berlin, Heidelberg, 2004:239-250.
[4]Misue K, Eades P, Lai W, et al. Layout Adjustment and the Mental Map[J]. J Visual Languages & Computing, 1995, 6(2):183-210.