Home 推荐算法相关search

# GCN

# 卷积

卷积是两个函数ff 和gg 的数学运算，产生第三个函数hh

卷积定义公式：

​ 连续情况：

h(t)=(f∗g)(t)=def∫f(t)g(t−τ)dτh(t)=(f*g)(t)\stackrel{\mathrm{def}}{=}\int f(t)g(t-\tau) d\tau

​ 离散情况：

h(x,y)=(f∗g)(x,y)=def∑m,nf(x−m,y−n)g(m,n)\begin{aligned} &h(x,y) \\ &=(f*g)(x,y) \\ &\stackrel{\mathrm{def}}{=}\sum_{m,n}f(x-m,y-n)g(m,n) \end{aligned}

# 定义卷积的两个方法

# 谱方法

基于傅里叶变换用卷积订立将卷积操作转化为频域中的乘法操作：

  • 傅里叶变换：将输入信号和卷积核从时域转到频域，分别得到它们的傅里叶变换：

    F(u)=F{f(x)}H(u)=F{h(x)}F(u)=\mathcal{F}\{f(x)\}\\H(u)=\mathcal{F}\{h(x)\}

  • 频域乘法：在频域中对两个傅里叶变换结果进行逐点相乘：

    G(u)=F(u)⋅H(u)G(u)=F(u)\cdot H(u)

  • 逆傅里叶变换：将乘积结果通过逆傅里叶变换转换回时域：

    g(x)=F−1{G(u)}g(x)=\mathcal{F}^{-1}\{G(u)\}

# 空间方法

​ 空间方法直接在信号或图像的空间域中进行卷积运算，通过滑动窗口逐点计算卷积结果。

  • ** 翻转卷积核：** 将卷积核在空间域内翻转：h(−x)h(-x)

  • 滑动窗口：将翻转后的卷积核逐点滑动到输入信号的每一个位置

  • 加权求和：对每一个位置上的输入信号与卷积核对应元素进行加权求和：

    g(x)=(f∗h)(x)=∑af(a)h(x−a)g(x)=(f*h)(x)=\sum_af(a)h(x-a)

    对于二维图像，卷积计算也可以表示为：

    g(i,j)=∑m∑nf(i−m,j−n)h(m,n)g(i,j)=\sum_m\sum_nf(i-m,j-n)h(m,n)

# 图节点

# 普通图

给定一个图G=(V,E,W)G=(V,E,W)，XX 是节点特征矩阵，那么可以定义如下：

  • VV 是节点集，包含n=∣V∣n=|V| 个节点
  • EE 是边集，表示节点之间的连接关系
  • WW 是Rn×n\mathbb{R}^{n\times n} 中的加权邻接矩阵，表示节点之间边的权重
  • XX 是Rn×d\mathbb{R}^{n\times d} 中的节点特征矩阵，每个节点关联dd 个特征。矩阵XX 的每一列是定义在节点上的一个信号。

# 图拉普拉斯

普通图拉普拉斯矩阵LL 定义为:

L=D−WL=D-W

其中:

  • $D 是度矩阵（DegreeMatrix），是一个对角矩阵，且是度矩阵（Degree Matrix），是一个对角矩阵，且 D_{ii}=\sum_{j} W_{ij}，表示节点，表示节点 i$ 的度数，即与节点ii 相连的边的权重总和。
  • WW 是权重邻接矩阵，其中WijW_{ij} 表示节点ii 和节点jj 直接的边的权重

普通图拉普拉斯矩阵LL 的对角元素LiiL_{ii} 是节点ii 的度数，非对角矩阵LijL_{ij} 是节点ii 和节点jj 之间边的负权重，如果两个节点ii 和jj 之间没有边，那么Lij=0L_{ij}=0

归一化图拉普拉斯矩阵 L 定义为：

L=I−D−12WD−12L=I-D^{-\frac{1}{2}}WD^{-\frac{1}{2}}

  • II 是单位矩阵
  • D−12D^{- \frac{1}{2}} 是度矩阵的平方根的逆矩阵。度矩阵DD 的对角元素是各节点的度数，取其平方根再取逆矩阵

# 图傅里叶变换

图傅里叶变换是一种将传统傅里叶变换推广到图结构数据的方法。在图信号处理（Graph Signal Processing）中，它用于分析和处理定义在图节点上的信号。

# 图的傅里叶基

图GG 的傅里叶基是图拉普拉斯矩阵的正交归一特征向量的集合，具体步骤：

  • ** 特征向量和特征值：** 计算拉普拉斯矩阵 L 的特征向量和特征值。设{ul}l=1n\{u_l\}_{l=1}^n 是LL 的一组正交归一特征向量，对应的特征值为\{\lambda _l \}^n_

  • ** 拉普拉斯矩阵对角化：** 将图拉普拉斯矩阵对角化为:

    L=UΛUTL=U\Lambda U^T

    其中UU 是由特征向量构成的矩阵[u1,u2,...,un][u_1,u_2,...,u_n],Λ\Lambda 是对角矩阵，对角线上的对应的特征值[λ1,λ2,...,λn][\lambda_1,\lambda_2,...,\lambda_n].

# 图傅里叶变换

  • 定义：图上信号x∈Rnx\in\mathbb{R}^n 的图傅里叶变换定义为：

    x^=UTx\hat{x}=U^Tx

    这里，UTU^T 是特征向量矩阵的转置，xx 是图上的信号（每个节点上的值构成的向量），x^\hat x 是信号的图傅里叶变换（频域表示）

  • 逆变换：图傅里叶逆变换将频域表示的信号转换回时域表示，定义为：

    x=Ux^x=U \hat x

    这里，UU 是特征向量矩阵，x^\hat x 是频域表示的信号

# 图卷积

在图信号处理（Graph Signal Processing）中，卷积操作可以通过谱域（频域）中的计算来简化。

根据卷积定理，给定输入信号 x 和滤波信号 y，图卷积∗G*G 可以写成：

x∗Gy=U((UTx)⊙(UTy))x *_G y=U\left((U^Tx)\odot(U^Ty)\right)

  • UU 是图拉普拉斯矩阵LL 的特征向量矩阵
  • UxTU^T_x 是信号xx 的图傅里叶变换（频域表示）
  • UyTU^T_y 是滤波器yy 的图傅里叶变换（频域表示）
  • ⊙\odot 表示逐点乘积（点乘）

步骤：

  • 对信号xx 进行图傅里叶变换UTxU^Tx
  • 在频域中，对转换后的信号UxTU_x^T 和滤波器UyTU^T_y 进行逐点乘积，结果表示为gθUTx{}{g_{\theta}}U^{T}x
  • 对频域结果进行图傅里叶逆变换，得到卷积结果UgθUxTU_{g _\theta}U^T_x

# 逐点积

逐点乘积是指两个相同维度的矩阵或向量之间的元素对应相乘。假设有两个向量 $ a$ 和 bb，其长度都为 nn，则逐点乘积 $ c$ 的第 ii 个元素定义为：

ci=ai∗bic_i=a_i*b_i

假设有两个向量aa 和bb：

a=[a1,a2,a3]b=[b1,b2,b3]a=[a_1,a_2,a_3]\\b=[b_1,b_2,b_3]

它们的逐点乘积cc 为：

c=a⊙b=[a1⋅b1,a2⋅b2,a3⋅b3]c=a\odot b=[a_1\cdot b_1,a_2\cdot b_2,a_3\cdot b_3]

# 光谱图卷积神经网络

光谱图卷积神经网络（Spectral Graph Convolutional Neural Network, Spectral Graph CNN）是一种将卷积神经网络（CNN）的概念推广到图结构数据的方法。它利用图傅里叶变换在频域中进行卷积操作，从而有效地处理非欧几里得数据，如社交网络、分子结构等。以下是对图中内容的详细解释。

首先介绍光谱图卷积神经网络中第 k 层的卷积操作：

xk+1,j=h(∑i=1fkUFk,i,jUTxk,i)x_{k+1,j}=h\left(\sum_{i=1}^{f_k}UF_{k,i,j}U^Tx_{k,i}\right)

其中：

  • xk+1,jx_{k+1,j}：第k+1k+1 层中第jj 个输出信号
  • hh: 激活函数
  • fkf_k 第kk 层中的滤波器数量
  • UU：图拉普拉斯矩阵的特征向量矩阵
  • Fk,i,jF_{k,i,j}：第kk 层中的滤波器参数
  • xk,ix_{k,i}：第 k 层中的第ii 个输入信号

详细步骤

  • 图傅里叶变换：将第 k 层中的输入信号xk,ix_{k,i} 转到频域

    x^k,i=UTxk,i\hat{x}_{k,i}=U^Tx_{k,i}

  • 频域卷积：对转换后的信号逐点乘积：

    y^k,i,j=Fk,i,jx^k,i\hat{y}_{k,i,j}=F_{k,i,j}\hat{x}_{k,i}

  • 逆图傅里叶变换：将频域结果转换回时域：

    yk,i,j=Uy^k,i,jy_{k,i,j}=U\hat{y}_{k,i,j}

  • 信号叠加和激活函数：将所有滤波结果相加，并通过激活函数得到第k+1k+1 层的输出信号

    xk+1,j=h(∑i=1fkyk,i,j)x_{k+1,j}=h\left(\sum_{i=1}^{f_k}y_{k,i,j}\right)

# CNN 的缺点

  • 需要拉普拉斯矩阵的特征分解（Requiring Eigen-Decomposition of Laplacian Matrix）
  • 高计算成本（High Computational Cost）
  • 在顶点域中不具备局部化特性（Not Localized in Vertex Domain）

# ChebyNet：通过多项式近似参数化滤波器

Parameterizing Filter via Polynomial Approximation

ChebyNet 是一种改进的光谱图卷积神经网络方法，通过多项式近似来参数化卷积滤波器，从而提高计算效率并减少参数数量。以下是对 ChebyNet 方法的详细解释：

# 背景

在传统的光谱图卷积神经网络中，卷积滤波器需要显式地使用拉普拉斯矩阵的特征分解，这导致高计算成本和参数量。ChebyNet 通过多项式近似的方法来简化这一过程。

# 多项式近似

ChebyNet 使用 Chebyshev 多项式来近似卷积滤波器。具体来说，卷积滤波器 $ g_\theta被表示为拉普拉斯矩阵特征值被表示为拉普拉斯矩阵特征值 \Lambda$ 的一个多项式：

gβ(Λ)=∑k=0K−1βkΛkg_\beta(\Lambda)=\sum_{k=0}^{K-1}\beta_k\Lambda^k

  • βk\beta_k 是多项式的系数，是需要学习的参数
  • Λ\Lambda 是拉普拉斯矩阵的特征值对角矩阵

# ChebyNet 的卷积操作

通过多项式近似，ChebyNet 中的图卷积操作可以写成：

x∗Gy=Ugβ(Λ)UTx=∑k=0K−1βkLkxx*_Gy=Ug_\beta(\Lambda)U^Tx=\sum_{k=0}^{K-1}\beta_kL^kx

  • $L $ 是图的拉普拉斯矩阵。
  • LkL^k 表示拉普拉斯矩阵的 k 次幂。