GNN笔记1-3——图信号处理

作者: Ice_spring | 来源:发表于2021-04-20 00:32 被阅读0次

图和图移位算子

图被定义为三元组集合： $G=\{V,E,W \}$ ：

节点 $V$ ： $V=\{1,2,\cdots,n\}$ 表示 $n$ 个不同 label 的集合；

边 $E$ ：有序对 $(i,j)\in E$ 表示 $j$ 可以影响 $i$ ；

权重 $W$ ： $w_{ij}\in W$ 是 $(i,j)$ 上的一个数字，表示 $j$ 影响 $i$ 的程度。

有向图与无向图

在无向图中， $(i,j)$ 等价于 $(j,i)$ ，且 $w_{ij}=w_{ji}$ ，在有向图中 $(i,j)$ 是从 $j$ 指向 $i$ 的箭头，权重 $w_{ij}$ 不一定等于 $w_{ji}$ 。

带权图与无权图

对于无权图若边之间存在连接，通常认为 $(i,j)$ 的权重是单位 “1”，即 $w_{ij}=1$ ，而带权图上的权重可以根据需要定义为任意值。

图的矩阵表示

邻接矩阵： $A = [w_{ij}]_{n\times n}$ , for all $(i,j)\in E$ ，对于无向图， $A=A^T$ ；

节点的度：节点 $i$ 的度是其所有邻接点的权重之和，即 $d_i=\sum_{j=1}^nw_{ij}$ ；

度矩阵：

$D=diag(A1)=\left[ \begin{array}{ccc} d_1 & \ldots & \ldots&\ldots \\ \vdots & d_2 & \ldots&0 \\ \vdots & \vdots & \ddots&\vdots \\ \vdots & 0 & \ldots &d_n \end{array} \right]$

拉普拉斯矩阵

Laplace 矩阵定义为： $L=D-A=diag(A1)-A$ ；

归一化的邻接矩阵： $\overline{A}:=D^{-1/2}AD^{-1/2}$ ，即 $(\overline{A})_{ij}=\frac{w_{ij}}{\sqrt{d_id_j}}$ ；

归一化的 Laplace 矩阵： $L=D^{-1/2}(D-A)D^{-1/2}=I-\overline{A}$ 。

归一化的原因：1. Express weights relative to the nodes’ degrees ; 2. 算法和计算上的考量。

图移位算子(Graph Shift Operators)

图移位算子 $S$ 可以是图的任何一种矩阵表示，如 $S=A$ 、 $S=L$ 、 $S=\overline{A}$ 、 $S=\overline{L}$ 等等。

图上的信号

图信号是我们在图上进行信号处理时的对象；

考虑一个有 $n$ 个节点的图 $G$ 和其上定义的图移位算子 $S$ ，那么一个图信号就是一个**向量 $x=[x_1,\cdots,x_n]^T$ **，其中分量 $x_i$ 是和图节点 $i$ 有关的量。为了强调图是信号固有的，可以把信号写成对的形式 $(S,x)$ ；

图移位算子 $S$ 与信号 $x$ 的乘法表示信号在图上的扩散，扩散后信号 $y=Sx$ ，分量 $y_i=\sum_j w_{ij}x_j$ ，权重越大，扩散输出贡献越大；

信号扩散序列 $x^{(k+1)}=Sx^{(k)}$ ，其中 $x^{(0)}=x=S^0x,\quad x^{(1)}=Sx^{(0)}=S^1x,$$x^{(k)}=Sx^{(k-1)}=S^kx$ ，
[图片上传失败...(image-fd789-1618849866619)]

信号的扩散即信号在图上的传播，扩散一次该信息将被传播到其单跳邻居， $k$ 次则传播到 $k$ 跳邻居。

图卷积滤波器

图卷积滤波器是图信号线性处理的工具。给定图 $G$ 和移位算子 $S$ ，以及一系列系数 $h_k$ ，则图上的卷积滤波器是 $S$ 的多项式序列，它由 $\{h_1,\cdots,h_{\infty}\}$ 确定：
$H(S) =\sum_{k=0}^\infty h_kS^k$
滤波器作用到图信号 $x$ 上：
$y=H(S)x=\sum_{k=0}^\infty h_kS^kx$
称 $h{*_S}x$ 是滤波器 $h=\{h_k\}_{k=1}^\infty$ 与信号 $x$ 的图卷积。

实际中 $k$ 不会取到无穷，图卷积的输出 $y=h{*_S}x=h_0S^0x+h_1S^1x+\cdots + =\sum_{k=0}^{K-1}h_kS^kx$ ，图卷积聚集了从局部到全局的信息，是扩散序列元素的线性组合。
[图片上传失败...(image-74e34-1618849866619)]

时序卷积是图卷积的特例

时序卷积输出： $y_n=\sum_{k=0}^{K-1}h_kx_{n-k}$

image.png

时序信号可表示为线图上的图信号 $(S,x)$ ：
[图片上传失败...(image-71f446-1618849866619)]

其中 $S$ 是线图的邻接矩阵：

image-20210416132337178.png

于是时间序列能够表示为作用在初始信号 $x$ 上的 $S$ 的多项式：
$y=h{*_S}x=h_0S^0x+h_1S^1x+\cdots + =\sum_{k=0}^{K-1}h_kS^kx$

卷积运算是输入信号移位的线性组合：

image-20210416132438388.png

如果设 $S$ 为任意图移位算子，则可以恢复到图卷积，因此图卷积也可以说是时序卷积的推广：

image.png

其中 $S^kx$ 的含义是信号 $x$ 在图上经过 $k$ 跳传播后的信号。

图傅里叶变换

图形傅里叶变换是分析图信息处理的工具。

这里分析的图是对称图(通常为无向图)，即 $S^H=S$ 。设 $\lambda_1\leq \lambda_2\leq\cdots \leq \lambda_n$ 为 $S$ 的 $n$ 个特征值， $\{v_1,v_2,\cdots,v_n\}$ 为对应的 $n$ 个单位正交特征向量组， $Sv_i=\lambda_iv_i$ ，令 $V=[v_1,v_2,\cdots,v_n]$ ， $\Lambda=diag([\lambda_1,\cdots,\lambda_n])$ ，于是：
$S=V\Lambda V^H,\quad V^HV=I$
图傅里叶变换 ：给定图移位算子 $S=V\Lambda V^H$ ，图上信号 $x$ 的傅里叶变换：
$\tilde{x}=V^Hx$
图上信号 $x$ 的傅里叶变换实际上就是 $x$ 在 $S$ 特征向量空间的投影运算，称 $\tilde{x}$ 为信号 $x$ 的频域表示。

图傅里叶逆变换：给定图移位算子 $S=V\Lambda V^H$ ，频域信号 $\tilde{x}$ 的逆傅里叶变换：
$\tilde{\tilde{x}}=V\tilde{x}$
显然 $\tilde{\tilde{x}}=V\tilde{x}=V(V^Hx)=Ix=x$ 。

图滤波器的频率响应(定理)：图卷积滤波器 $h=\{h_1,\cdots,h_{\infty}\}$ ，图信号 $x$ 的滤波表示 $y=\sum_{k=0}^\infty h_kS^kx$ ，则原信号 $x$ 的傅里叶变换 $\tilde{x}=V^Hx$ 和卷积输出信号 $y$ 的傅里叶变换 $\tilde{y}=V^Hy$ 之间的关系是：
$\tilde{y}=\sum_{k=0}^\infty h_k\Lambda^k\tilde{x}$

证明： $S=V\Lambda V^H$ ，则 $S^k=V\Lambda^k V^H$ ，因此滤波输出：
$y=\sum_{k=0}^\infty h_kS^kx=\sum_{k=0}^\infty h_kV\Lambda^k V^Hx$
两边用 $V^H$ 作用：
$\begin{aligned} \tilde{y}&=V^Hy=V^H\sum_{k=0}^\infty h_kV\Lambda^k V^Hx\\ &=\sum_{k=0}^\infty h_k\Lambda^k\tilde{x} \end{aligned}$

在图频域，滤波器是对角矩阵 $\Lambda$ 在系数 $h_k$ 下的多项式，这样一来原时域信号 $x$ 上的卷积运算在傅里叶变换下转换为了频域中的点积运算：
$\begin{aligned} \tilde{y}&=\sum_{k=0}^\infty h_k\Lambda^k\tilde{x}=\tilde{h}(\lambda)\tilde{x} \\ \end{aligned}$

其中：

$\tilde{y}_i=\sum_{k=0}^\infty h_k\lambda_i^k\tilde{x}_i=\tilde{h}(\lambda_i)\tilde{x}_i$

将 $\tilde{h}(\lambda)=\sum_{k=0}^\infty h_k\lambda^k$ 定义为图滤波器的频域响应，可以看到频域响应多项式的系数与图滤波器系数相同。需要特别指出的是，频域响应与图是无关的(频域响应不依赖于特定的图)，因此在图滤波器中，图的作用仅仅是确定实例化响应的特征值，当给定一个图，响应在 $\tilde{h}(\lambda)$ 上被实例化，而 $\tilde{h}(\lambda)$ 只是个单变量解析函数，它由滤波系数决定。

GNN笔记1-3——图信号处理

图和图移位算子

图上的信号

图卷积滤波器

时序卷积是图卷积的特例

图傅里叶变换

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读