Loading...
墨滴

梁一灵

2021/04/19  阅读:32  主题:默认主题

图神经网络笔记1-3——图信号处理

图和图移位算子

  • 图被定义为三元组集合:

节点 表示 个不同 label 的集合;

:有序对 表示 可以影响

权重 上的一个数字,表示 影响 的程度。

  • 有向图与无向图

在无向图中, 等价于 ,且 ,在有向图中 是从 指向 的箭头,权重 不一定等于

  • 带权图与无权图

对于无权图若边之间存在连接,通常认为 的权重是单位 “1”,即 ,而带权图上的权重可以根据需要定义为任意值。

  • 图的矩阵表示

邻接矩阵: , for all ,对于无向图,

节点的度:节点 的度是其所有邻接点的权重之和,即

度矩阵:

  • 拉普拉斯矩阵

Laplace 矩阵定义为:

归一化的邻接矩阵: ,即

归一化的 Laplace 矩阵:

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

  • 图移位算子(Graph Shift Operators)

图移位算子 可以是图的任何一种矩阵表示,如 等等。

图上的信号

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

考虑一个有 个节点的图 和其上定义的图移位算子 ,那么一个图信号就是一个**向量 **,其中分量 是和图节点 有关的量。为了强调图是信号固有的,可以把信号写成对的形式

图移位算子 与信号 的乘法表示信号在图上的扩散,扩散后信号 ,分量 ,权重越大,扩散输出贡献越大;

信号扩散序列 ,其中 信号扩散

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

图卷积滤波器

图卷积滤波器是图信号线性处理的工具。给定图 和移位算子 ,以及一系列系数 ,则图上的卷积滤波器是 的多项式序列,它由 确定:

滤波器作用到图信号 上:

是滤波器 与信号 的图卷积。

实际中 不会取到无穷,图卷积的输出 ,图卷积聚集了从局部到全局的信息,是扩散序列元素的线性组合。

时序卷积是图卷积的特例

时序卷积输出: 时序卷积

时序信号可表示为线图上的图信号

其中 是线图的邻接矩阵:

于是时间序列能够表示为作用在初始信号 上的 的多项式:

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

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

其中 的含义是信号 在图上经过 跳传播后的信号。

图傅里叶变换

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

这里分析的图是对称图(通常为无向图),即 。设 个特征值, 为对应的 个单位正交特征向量组, ,令 ,于是:

图傅里叶变换 :给定图移位算子 ,图上信号 的傅里叶变换:

图上信号 的傅里叶变换实际上就是 特征向量空间的投影运算,称 为信号 的频域表示。

图傅里叶逆变换:给定图移位算子 ,频域信号 的逆傅里叶变换:

显然

图滤波器的频率响应(定理):图卷积滤波器 ,图信号 的滤波表示 ,则原信号 的傅里叶变换 和卷积输出信号 的傅里叶变换 之间的关系是:

证明: ,则 ,因此滤波输出:

两边用 作用:

在图频域,滤波器是对角矩阵 在系数 下的多项式,这样一来原时域信号 上的卷积运算在傅里叶变换下转换为了频域中的点积运算

其中:

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

梁一灵

2021/04/19  阅读:32  主题:默认主题

作者介绍

梁一灵