最近在学习图信号处理的相关知识，想进行一些应用层面的实践，恰巧遇到一篇十分具有启发性的推荐算法的论文，故以此文进行简单总结，也作为自己的学习笔记。
Reference:
一个无向图 G G G（Graph） 可以定义为： G = ( V , E ) G=(V,E) G=(V,E)。即无向图由节点集合 V V V和边缘集合 E E E构成。 V = { 1 , 2 , . . . , N } V=\{1,2,...,N\} V={1,2,...,N}， N N N为节点个数。部分节点之间存在“连接”（译为links或edges），这些连接集合表示为 E E E。具体地，任意不同的两个节点为 i , j ∈ V i,j\in V i,j∈V，则 E = { i , j , w i j } E=\{i,j,w_{ij}\} E={i,j,wij}，表示节点 i i i与节点 j j j间的连接权值 w i j w_{ij} wij。
上述的三元组合表达方式并不是非常理想的，我们并不能通过这种表达方式发掘图本身的特征，因此，矩阵被广泛应用于图的表达。基本地，定义邻接矩阵 A A A，则一个带有 N N N个节点的图可以用大小为 N ∗ N N*N N∗N的 A A A表示，其中 A ( i , j ) = w i j A(i,j)=w_{ij} A(i,j)=wij。
除了 A A A以外，还有一些常用的矩阵表达方式，分别具有不同的性质，也能够反映不同的图的特征。在此之前，先定义 d i d_i di为节点 i i i的维度，其为节点 i i i的所有连接权值的总和。然后，定义维度矩阵 D = d i a g ( d 1 , d 2 , . . . , d N ) D=diag(d_1,d_2,...,d_N) D=diag(d1,d2,...,dN)，其中 d i a g ( ) diag() diag()将向量转变为对角矩阵。
注：为了方便描述，下述的图都给定为简单图，在简单图中， A A A的元素只由0和1构成。1表示该边存在，反之则为0。如果不是简单图，这些矩阵依然满足下述定义式。
给定无向图 G = ( V , E ) G=(V,E) G=(V,E)，其对应的关联矩阵 ∇ \nabla ∇是一个长宽为 [ ∣ E ∣ ∗ ∣ V ∣ ] [|E|*|V|] [∣E∣∗∣V∣]的矩阵。对于矩阵里的每一条边 e = n i n j e=n_in_j e=ninj，可以任意给定一个方向。之后，如果节点 x x x是边缘 e e e的起始节点，则 ∇ e x = − 1 \nabla_{ex}=-1 ∇ex=−1，如果节点 x x x是终止节点，则 ∇ e x = 1 \nabla_{ex}=1 ∇ex=1。
即，每一行有且仅包含了一个1和一个-1，其余都是0元素。
Laplacian Matrix可由Incidence Matrix得到： L = ∇ T ∇ L=\nabla^T\nabla L=∇T∇。
同时，若给定一个简单图（simple graph）的邻接矩阵 A A A和维度矩阵 D D D。则这个图的Laplacian Matrix也可定义为： L = D − A L = D-A L=D−A
上述两式是等价的。具体地，
L
L
L的元素为：
L
i
,
j
=
{
d
i
i
=
j
−
1
n
o
d
e
i
i
s
a
d
j
a
c
e
n
t
t
o
j
0
o
t
h
e
r
w
i
s
e
L_{i,j}=\left\{ \begin{aligned} d_i & &{i=j} \\ -1 & &{node\ i\ is\ adjacent\ to\ j}\\ 0 & &{otherwise} \end{aligned} \right.
Li,j=⎩⎪⎨⎪⎧di−10i=jnode i is adjacent to jotherwise
拉普拉斯矩阵
L
L
L具有半正定的特性，且各行各列累加都为0。
下面给出半正定的证明： 令 λ i \lambda_i λi和 v i v_i vi为 L L L的某一特征值和特征向量对。则有：
λ i = v i T L v i = v i T ∇ T ∇ v i = ( ∇ v i ) T ( ∇ v i ) ≥ 0 \lambda_i=v_i^TLv_i=v_i^T\nabla^T\nabla v_i=(\nabla v_i)^T(\nabla v_i)\geq0 λi=viTLvi=viT∇T∇vi=(∇vi)T(∇vi)≥0
所以 L L L为半正定矩阵。
一个简单图的对称标准化拉普拉斯矩阵
L
s
y
m
L^{sym}
Lsym定义如下：
L
s
y
m
=
D
−
1
2
L
D
−
1
2
=
I
−
D
−
1
2
A
D
−
1
2
L^{sym} = D^{-\frac 12}L D^{-\frac 12} = I - D^{-\frac 12}AD^{-\frac 12}
Lsym=D−21LD−21=I−D−21AD−21
具体地，
L
s
y
m
L^{sym}
Lsym的元素为：
L
i
,
j
s
y
m
=
{
1
i
=
j
a
n
d
d
i
≠
0
−
1
d
i
d
j
n
o
d
e
i
i
s
a
d
j
a
c
e
n
t
t
o
j
0
o
t
h
e
r
w
i
s
e
L^{sym}_{i,j}=\left\{ \begin{aligned} 1 & &{i=j \ and \ d_i \neq 0} \\ -\frac{1}{\sqrt{d_id_j}} & &{\ node\ i \ is\ adjacent\ to\ j} \\ 0 & &{otherwise} \end{aligned} \right.
Li,jsym=⎩⎪⎪⎪⎨⎪⎪⎪⎧1−didj
10i=j and di̸=0 node i is adjacent to jotherwise
L
s
y
m
L^{sym}
Lsym在进行了标准化（对角线的值为1）的同时，保留了对称特性。
随机游走标准化拉普拉斯矩阵
L
r
w
L^{rw}
Lrw定义如下：
L
r
w
=
D
−
1
L
=
I
−
D
−
1
A
L^{rw}=D^{-1}L=I-D^{-1}A
Lrw=D−1L=I−D−1A
具体地，
L
r
w
L^{rw}
Lrw的元素为：
L
i
,
j
r
w
=
{
1
i
=
j
a
n
d
d
i
≠
0
−
1
d
i
n
o
d
e
i
i
s
a
d
j
a
c
e
n
t
t
o
j
0
o
t
h
e
r
w
i
s
e
L^{rw}_{i,j}=\left\{ \begin{aligned} 1 & &{i=j \ and \ d_i \neq 0 } \\ -\frac{1}{d_i} & &{\ node\ i\ is\ adjacent\ to\ j}\\ 0 & &{otherwise} \end{aligned} \right.
Li,jrw=⎩⎪⎪⎪⎨⎪⎪⎪⎧1−di10i=j and di̸=0 node i is adjacent to jotherwise
L
r
w
L^{rw}
Lrw在进行了标准化的同时，使得每一行的和为0，但失去了对称特性。
以上的三种矩阵表述根据不同的需要，可以十分有力的表达图的结构。但表达的也仅仅是图的结构，就好比是设计好了一栋连接错综复杂的大楼，每一个节点还等着我们去赋值。给定任意一个无向图的邻接矩阵
A
A
A，假定节点数为
N
N
N，则任意的长度为
N
N
N的信号都可以作为这个无向图的图信号，其各个位置的值代表对应节点的值。
类比于一维信号的离散时间变换（Discrete Fourier Transform），GFT的变换将图信号线性映射到某一组正交基，但不同于DFT的将不同角频率的三角函数作为正交基，GFT的正交基取决于其Graph的结构，或者更确切地说，是取决于其描述Graph的各种上述提到的矩阵。不过，和DFT类似的是，GFT的目标也是通过线性映射来获取图信号所包含的不同的频率成分。
对于一个有限长的一维信号，其短时傅里叶变换能够将其分解为不同频率的正弦波的累加和。越高频率的正弦波周期越短，即在短时间内的振荡变化越快。将这个概念衍生到图信号的变换来：节点可以类比于一维信号里时间的概念，对于任意一个节点，与其相连接的节点相比较，如果变化（Variation）剧烈，则可以认为这个节点的频率很高，与瞬时频率比较类似。
定义信号
x
x
x在节点
i
i
i的变化程度
z
(
i
)
z(i)
z(i)，一种很常用的度量方式如下式：
z
(
i
)
=
∑
j
∈
N
i
w
i
,
j
(
x
(
i
)
−
x
(
j
)
)
z(i)=\sum_{j \in N_i} w_{i,j}(x(i)-x(j))
z(i)=j∈Ni∑wi,j(x(i)−x(j))
其中
N
i
N_i
Ni为节点
i
i
i的所有邻接节点。
整个图的变化度量可以定义为上式的加权和：
v
a
r
i
a
n
c
e
=
∑
i
=
1
N
z
(
i
)
x
(
i
)
=
∑
i
=
1
N
∑
j
∈
N
i
w
i
,
j
(
x
(
i
)
−
x
(
j
)
)
x
(
i
)
variance=\sum_{i=1}^{N}z(i)x(i)=\sum_{i=1}^N\sum_{j \in N_i}w_{i,j}(x(i)-x(j))x(i)
variance=i=1∑Nz(i)x(i)=i=1∑Nj∈Ni∑wi,j(x(i)−x(j))x(i)
不难发现，给定任意一个无向图
G
G
G的拉普拉斯矩阵
L
L
L，上式其实就是
x
T
L
x
x^TLx
xTLx，该式可称为瑞利熵（Rayleigh Quotient）。现在，我们要依次寻找正交基的基向量
u
u
u，来使得
u
T
L
u
u^TLu
uTLu的值可能小。
由于
L
L
L满足各行各列累加都为0，因此下式永远成立：
1
T
L
1
=
0
1^TL1=0
1TL1=0
其中
1
1
1为全1列向量。显然，标准化后的
1
1
1向量可以当作这一组正交基的起点向量，表示最低频率成分，记作
u
1
=
1
N
1
u_1=\frac{1}{\sqrt{N}}1
u1=N
11。
由于 L L L为半正定，所以对任意向量 v v v，必定满足 v T L v ⩾ 0 v^TLv \geqslant 0 vTLv⩾0。寻找 u 2 u_2 u2，使得 u 2 T L u 2 u_2^TLu_2 u2TLu2最小，并且与 u 1 u_1 u1正交。以此类推，直到找到N个正交向量组成正交基为止。
事实上，这些向量
U
=
{
u
1
,
u
2
,
.
.
.
,
u
N
}
U=\{u_1,u_2,...,u_N\}
U={u1,u2,...,uN}就是
L
L
L的特征向量，并且其特征值从0开始由小到大排列。
L
=
U
Λ
U
T
L=U\Lambda U^T
L=UΛUT
在无向图的前提下， L L L是一个对称矩阵，所以必定能找到标准正交的N个 u u u和其对应的特征值。
给定一个无向图，对于任意图信号
x
x
x，其可以由拉普拉斯矩阵的特征向量线性加和构成，加和的系数即为变换后的向量
x
~
\tilde {x}
x~。因此有：
x
=
U
x
~
x=U\tilde x
x=Ux~
其中
x
~
=
U
T
x
\tilde x=U^Tx
x~=UTx。则
x
~
\tilde x
x~中的每一个元素代表了各个频率成分。
从图中可以看出，当特征值越大，过零点就越多，印证了特征值越大，基向量越高频的性质。
