图的基本定义啥的就不写了,满大街都是。从 Laplace 矩阵开始的。

谱图理论基础

Laplace 矩阵

来源

考虑微积分中的 Laplace 算子。对多元函数 $f(x_1,\cdots,x_n)$,Laplace 算子 $\Delta$ 定义为 $$ \Delta f=\sum_{i=1}^n \dfrac{\partial^2 f}{\partial x_i^2}. $$ 我们用右侧差分代替各个函数的导数,即 $$ f'(x)\approx \dfrac{f(x+\Delta x)-f(x)}{\Delta x}. $$ 为简便起见,考虑二元函数 $f(x,y)$,并且统一步长为 $1$。此时二维平面变成了一张图,节点是所有格点,每个点连接了上下左右四个格点。对节点 $(x,y)$,它的四个邻居是 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$.

容易算出差分形式的 Laplace 算子为

$$ \Delta f(x,y)\approx f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y). $$

把它推广到图 $G(V,E)$,$f:V\to\mathbb{R}$,有

$$ \begin{pmatrix} \Delta f(x_1)\\ \vdots\\ \Delta f(x_n) \end{pmatrix}=-(D-W) \begin{pmatrix} f(x_1)\\ \vdots\\ f(x_n) \end{pmatrix}. $$

Laplace 矩阵定义为 $D-W$ 而不是 $W-D$,是因为这样是半正定矩阵,而不是半负定矩阵。

性质

  • $\forall x\in\mathbb{R}^n,x^TLx=\sum_{(u,v)\in E}w_{uv}(x_u-x_v)^2$,
  • $L$ 对称半正定,
  • 最小特征值为 $0$,其中一个特征向量为所有分量为 $1$ 的向量,
  • 特征值 $0$ 的重数为连通子图的个数,
  • 所有非 $0$ 特征值的特征向量必然与 $1$ 正交(更一般地,实对称矩阵不同特征值的特征向量正交)。

中心性(Centrality)

几种简单的中心性的度量:

  • Degree centrality: $k_u$ ($k_u^{\rm in},k_u^{\rm out}$),
  • Closeness centrality: $c_{CL}(u)=\left(\sum_v d_{uv}\right)^{-1}$,
  • Betweenness centrality: 点对 $v,w$ 的个数 which 有通过 $u$ 的最短路径(有多条则按比例算),

此外还有下面几种不那么 trivial 的。

Katz centrality (Eigenvalue centrality)

Perron-Frobenius 定理

我们要先介绍 Perron-Frobenius 定理,它描述了非负矩阵的谱的一些有趣性质。完整内容和证明请参考 https://dna049.com/perronFrobeniusTheory

定义(置换相似) 两个矩阵称为置换相似的,若存在置换矩阵 $P$ 满足 $P^TXP=Y$.

对于图的邻接矩阵,置换操作等价于更改节点的编号顺序。

定义(可约矩阵) 设 $A\in M_n$,称 $A$ 可约,若 $A$ 置换相似于一个形如 $\begin{pmatrix}B&0\\C&D\end{pmatrix}$ 的矩阵,其中 $B,D$ 是方阵。否则称 $A$ 不可约。

图的邻接矩阵可约,等价于图不连通。

定义(谱半径) 矩阵 $A$ 的谱半径 $\rho(A)$ 定义为矩阵 $A$ 的所有特征值的绝对值的最大值。

定理(Perron-Frobenius) 设 $A$ 是非负不可约矩阵,则

  1. $\rho(A)>0$ 且 $\rho(A)$ 是矩阵 $A$ 的一个单重特征值
  2. $A$ 有一个对应于 $\rho(A)$ 的正特征向量
  3. $A$ 的每个非负特征向量都对应于特征值 $\rho(A)$

Katz 的心路历程

$A$ 为邻接矩阵。对于 degree centrality,我们把各节点的中心度写成列向量,有 $$ c_0=A \begin{pmatrix} 1\\ \vdots\\ 1 \end{pmatrix}. $$ 这只考虑了自己的影响力,没有考虑邻居的影响力。我们希望把它改成邻居的 degree centrality 之和,即 $$ c_1=\sum_{v:(u,v)\in E} c_0(v)= Ac_0. $$ 进一步套娃,有 $c_{r+1}=Ac_r$. 但这样下去会发散,我们需要加上个衰减因子。根据 Perron-Frobenius 定理,记最大特征值为 $\lambda$,我们让 $c_{r+1}=\lambda^{-1}Ac_r$. 又记 $\lambda$ 的正特征向量为 $x$,有 $$ \lim_{r\to\infty} c_r=\left(\sum_i x_i\right)x. $$ 证明留作习题。而我们其实只关心节点之间的中心度的相对大小,所以 $x$ 可以随便乘个系数。我们令 $|x|=1, x_i>0$,然后定义 eigenvalue centrality (Katz centrality):

$$ c_E(u)=x_u. $$

PageRank centrality

这是 Google 的网页排序指标。我们假设一个网络中,网页(顶点)$u$ 有 $x_u$ 的人在访问。下一时刻,有一部分人会从其他页面跳转而来。跳转的概率是 $\alpha$,等概率跳转到该页面连接的其他页面。则跳转到 $u$ 的人数是: $$ \alpha\sum_{v:(v,u)\in E}\dfrac{x_v}{k_v^{\rm out}}. $$ 此外,还会有一些新人到来,这部分是个常数 $\beta$. 于是有 $$ x_v=\alpha\sum_{u:(u,v)\in E}\dfrac{x_u}{k_u^{\rm out}}+\beta. $$ 用 $D$ 表示出度矩阵,$\mathbf{1}$ 为 $n\times 1$ 的全 $1$ 向量,有 $$ x=\beta(I-\alpha D^{-1}A)^{-1}\mathbf{1}. $$ 请自行证明那个矩阵可逆。

HITS (hubs and authorities)

HITS (Hyperlink-Induced Topic Search) 与 PageRank 算法一样,也是一种用于对网页进行排序的算法。

网页有两个功能:hub 和 authority。Hub 是网站导航方面的功能,比如臭名昭著的 hao123,authority 是真正的内容,比如我这篇文章(?)。我们给每个节点 $u$ 两个中心性:hub centrality $h_u$ 和 authority $a_u$. 我们希望:

  • 被高 $h$ 的节点指向,说明内容质量 $a$ 高
  • 指向高 $a$ 的节点,说明索引质量 $h$ 高

有了! $$ \begin{align} h_u&=\alpha\sum_{v:(u,v)\in E}a_v,\\ a_v&=\beta \sum_{u:(u,v)\in E}h_u. \end{align} $$

写成矩阵就是 $$ \begin{align} h &= \alpha Aa,\\ a &= \beta A^Th. \end{align} $$

然后 $$ \begin{align} AA^Th&=\dfrac{1}{\alpha\beta} h,\\ A^TAa&=\dfrac{1}{\alpha\beta}a. \end{align} $$

$h$ 是 $AA^T$ 的特征向量,根据 Perron-Frobenius 定理,要想 $h$ 是正的,他只能是最大特征值的特征向量,这个最大特征值就是 $\dfrac{1}{\alpha\beta}$。$a$ 同理。给出合适的归一化条件,就可以求出 $h$ 和 $a$。

Network Cohesion

团(clique)是全连接子图。

核心(core):$k$-core 表示子图内每个顶点的度都不小于 $k$(只统计内部边)

我们发现有一个有趣的性质:如果 $(u,v)$ 和 $(u,w)$ 都是边,往往 $(v,w)$ 也是边(共同好友),这一性质叫过渡性(transitivity)。我们想要引入聚类系数(clustering coefficient)来刻画过渡性。

我们称 $uvw$ 是长度为 2 的闭合路径,如果 $(u,v),(u,w),(v,w)$ 都是边。定义聚类系数 $$ C=\dfrac{\sharp{\text 长度为 2 的闭合路径}}{\sharp{\text 长度为 2 的路径}}. $$

物以类聚(homophily)

鲁迅曾经说过,物以类聚,人以群分。在图中,属性相似的节点可能更倾向于互相连接,这一特点就叫 homophily。

属性向量

我们要构造 $y$ 和 $z$. 首先每个节点 $u$ 都有一个属性 $x_u$。设一共有 $m$ 条边,我们把 $(u,v)$ 和 $(v,u)$ 看成同时存在的两条边,这时就有 $2m$ 条边。我们给边编号 $j=1,\cdots,2m$,边 $e_j=(u,v)$,则 $y_j=x_u,z_j=x_v$.

例如 $E={(1,2),(1,3)}$, 则 $y=(x_1,x_2,x_1,x_3),z=(x_2,x_1,x_3,x_1)$. 他们都是 $2m$ 维向量。显然 $y$ 和 $z$ 的变化趋势是否相同可以反映 homophily。下面介绍两种衡量方式:assortativity coefficient 和 modularity。

Assortativity coefficient

定义 assortativity coefficient 为 $y,z$ 的相关系数: $$ r=\dfrac{{\rm Cov}(y,z)}{\sqrt{{\rm Var}(y){\rm Var}(z)}}, $$ 容易验证,可以展开为如下形式: $$ r=\dfrac{2\sum_{(u,v)\in E}x_ux_v-2m\bar x_E^2}{\sum_{u\in V} k_u x_u^2-2m\bar x_E^2}. $$ 其中 $m$ 为边数,$k_u$ 为 degree, $\bar x_E=\dfrac{1}{2m}\sum_{u\in V} k_u x_u$.

我们有 $-1\leq r\leq 1$. $r$ 越大越说明鲁迅说的对。$r$ 要是 $-1$ 则恰恰相反。

Modularity

Assortativity coefficient 适合连续属性,而它更适合离散的分类属性。假设某个 factor 有 $I$ 个取值,例如三个不同的班级,$x_u$ 采用 one-hot 编码,即 $u$ 如果属于第 $i$ 类,则 $x_u^{(i)}=1$, 否则 $x_u^{(i)}=0$. 类似地有 $y^{(i)},z^{(i)}$ 都是 $2m$ 维向量。定义 modularity: $$ Q=\sum_{i\in I} {\rm Cov}(y^{(i)},z^{(i)}). $$ 将其用 $x$ 表示可以得到 $$ \begin{align} Q&=\sum_{i\in I}Q^{(i)},\\ Q^i&=\dfrac{1}{m}\sum_{(u,v)\in E}x_u^{(i)}x_v^{(i)}-\left(\bar x^{(i)}_E\right)^2. \end{align} $$ $Q$ 越大越好,但 $Q\leq 1$(自行证明)。

Agglomerative Clustering

聚类是机器学习中的一个重要话题。这里我们简要介绍以下 agglomerative clustering。它是层次聚类中自底向上的算法(还有一种自顶向下的 divisive clustering)。Agglomerative clustering 可以采用许多不同的方式来度量两个聚类的相似度,这里介绍的是使用 modularity $Q$ 作为相似程度的实现。

  • 首先假设每个节点都是单独的一类;
  • 考虑合并其中两个节点,有 $n(n-1)/2$ 种合并方式,穷举选择使 $Q$ 最大的一种;
  • 现在只剩 $n-1$ 个类别了,重复上述步骤,选择一种使得 $Q$ 最大的方式合并其中两个类别;
  • 重复直到只剩一类;
  • 合并的过程可以画出一个树形图,它叫 dendrogram。

然后就可以目测 dendrogram 来决定分几类了。