首页 > 其他分享 >Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

时间:2023-04-16 14:55:59浏览次数:52  
标签:Convolutional mathbf Deeper Semi sym smoothing Laplacian tilde alpha

目录

Li Q., Han Z. and Wu X. Deeper insights into graph convolutional networks for semi-supervised learning. AAAI, 2018.

本文分析了 GCN 的实际上就是一种 Smoothing, 但是如果层数过多就会导致 over-smoothing.

符号说明

  • \(\mathcal{G = (V, E)}\), 图;
  • \(|\mathcal{V}| = n\);
  • \(A \in \mathbb{R}^{n \times n}\), 邻接矩阵;
  • \(L = D - A\), Laplacian matrix;
  • \(L_{sym} := D^{-1/2} L D^{-1/2}\);
  • \(L_{rw} := D^{-1} L\);
  • \(X = [\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_n]^T \in \mathbb{R}^{n \times c}\), feature matrix;

Laplacian smoothing

  • GCN 的每一层实际上就是如下的一个过程:

    \[Y = \tilde{D}^{-1/2} \tilde{A}^{-1/2} \tilde{D}^{-1/2} X, \]

    这里 \(\tilde{A} = A + I, \tilde{D} = \sum_j \tilde{A}_{ij}\).

  • 在图论中, Laplacian smoothing 被定义为:

    \[\hat{Y} = X - \gamma \tilde{D}^{-1} \tilde{L} X = (I - \gamma \tilde{D}^{-1} \tilde{L}) X = \Big( (1 - \gamma) I + \tilde{D}^{-1} \tilde{A} \Big) X. \]

  • 倘若 \(\gamma=1\), 则其退化为 \(\tilde{D}^{-1} \tilde{A}X\), 这是在一般的 rankdom walk 的机制下推导出来的 Laplacian smoothing.

  • 自然地, 在对称的 Laplacian 矩阵 \(\tilde{L}_{sym}\) 的框架下, 我们就得到了一般的 GCN 的方式.

  • 总的来说, 我们可以认为, 相较于普通的 MLP, GCN 更具优势的点在于它能够将相似的点的信息聚在一起, 从而获得更好的判别性质.

  • 但是, 倘若我们不断地叠加 GCN 就会产生 over-smoothing 的现象, 这可以通过如下的定理中理解.

Theorem 1. 如果图 \(\mathcal{G}\) 不包含 bipartite 成分, 则对于任意的 \(\mathbf{w} \in \mathbb{R}^n, \alpha \in (0, 1]\) 有

\[\lim_{l \rightarrow +\infty} (I - \alpha L_{rw})^l \mathbf{w} = [\mathbf{1}^{(1)}, \mathbf{1}^{2}, \ldots, \mathbf{1}^{(k)}] \bm{\rho}_1, \\ \lim_{l \rightarrow +\infty} (I - \alpha L_{sym})^l \mathbf{w} = D^{1/2}[\mathbf{1}^{(1)}, \mathbf{1}^{2}, \ldots, \mathbf{1}^{(k)}] \bm{\rho}_2. \\ \]

这里, 我们假设 \(\mathcal{G}\) 有 \(k\) 个连通的部分, 并令:

\[\mathbf{1}_j^{(i)} = \left \{ \begin{array}{ll} 1 & v_j \in C_i, \\ 0 & v_j \not \in C_i. \\ \end{array} \right . \]

proof:

只需证明 \((I - \alpha L_{rw}), (I - \alpha L_{sym})\) 的特征值在 \((-1, 1]\), 且特征值 1 所对应的特征向量为 \(\mathbf{1}, D^{1/2} \mathbf{1}\).

注: 文中说 \(I - \alpha L_{sym}\) 的特征值为 \(D^{-1/2}\mathbf{1}\), 这似乎是错的, 因为

\[\begin{array}{ll} (I - \alpha L_{sym}) D^{1/2} \mathbf{1} &= D^{1/2} \mathbf{1} - \alpha L_{sym} D^{1/2} \mathbf{1} \\ &= D^{1/2} \mathbf{1} - \alpha D^{-1/2} L D^{-1/2} D^{1/2} \mathbf{1} \\ &= D^{1/2} \mathbf{1} - \alpha (I - D^{-1/2} A D^{-1/2}) D^{1/2} \mathbf{1} \\ &= D^{1/2} \mathbf{1} - \alpha (D^{1/2}\mathbf{1} - D^{-1/2} A\mathbf{1}) \\ &= D^{1/2} \mathbf{1} - \alpha (D^{1/2}\mathbf{1} - D^{-1/2} D\mathbf{1}) \\ &= D^{1/2} \mathbf{1} - \alpha 0 \\ &= D^{1/2} \mathbf{1}. \end{array} \]

\(D^{-1/2}\mathbf{1}\) 是如何证明出来的?

代码

official

标签:Convolutional,mathbf,Deeper,Semi,sym,smoothing,Laplacian,tilde,alpha
From: https://www.cnblogs.com/MTandHJ/p/17323284.html

相关文章

  • ASEMI代理ADI亚德诺AD8400ARZ10-REEL车规级芯片
    编辑-ZAD8400ARZ10-REEL芯片参数:型号:AD8400ARZ10-REEL标称电阻:10kΩ雨刮器电阻:50Ω清晰度:8BitsTempco分压器:15ppm/°C电容Ax,电容Bx:75pF电容Wx:120pF关机电流:0.01μA关闭雨刮器电阻:100Ω输入电流:±1μA输入电容:5pF电源范围:2.7-5.5V  一般说明:AD8400ARZ10-R......
  • AD823AARZ-RL-ASEMI代理亚德诺AD823AARZ-RL车规级芯片
    编辑-ZAD823AARZ-RL芯片参数:型号:AD823AARZ-RL−3dB带宽:17MHz全功率响应:4.8MHz斜率:30V/µs输入电压噪声:14nV/√Hz输入电流噪声:1fA/√Hz初始偏移量:0.12mV输入偏置电流:0.3pA输入失调电流:0.3pA输入共模电压范围:−0.2to+3.8V输入电阻:10Ω输入电容:0.6pF共模抑制比:73dB线性输出电......
  • ASEMI代理ADI亚德诺AD8400ARZ10-REEL车规级芯片
    编辑-ZAD8400ARZ10-REEL芯片参数:型号:AD8400ARZ10-REEL标称电阻:10kΩ雨刮器电阻:50Ω清晰度:8BitsTempco分压器:15ppm/°C电容Ax,电容Bx:75pF电容Wx:120pF关机电流:0.01μA关闭雨刮器电阻:100Ω输入电流:±1μA输入电容:5pF电源范围:2.7-5.5V 一般说明:AD8400ARZ10-REEL提供单通道、双通......
  • Stochastic Training of Graph Convolutional Networks with Variance Reduction
    目录概符号说明Motivation本文方法代码ChenJ.,ZhuJ.andSongL.Stochastictrainingofgraphconvolutionalnetworkswithvariancereduction.ICML,2018.概我们都知道,GCN虽然形式简单,但是对于结点个数非常多的情形是不易操作的:多层的卷积之后基本上每个结点......
  • ASEMI代理ADA4940-1ACPZ-R7原装ADI车规级ADA4940-1ACPZ-R7
    编辑:llASEMI代理ADA4940-1ACPZ-R7原装ADI车规级ADA4940-1ACPZ-R7型号:ADA4940-1ACPZ-R7品牌:ADI/亚德诺封装:LFCSP-16批号:2023+引脚数量:16安装类型:表面贴装型ADA4940-1ACPZ-R7汽车芯片ADA4940-1ACPZ-R7特征小信号带宽:260MHz超低功率1.25mA极低谐波失真−122dBTHD,50kHz时1MHz时的......
  • ASEMI代理ADA4940-1ACPZ-R7原装ADI车规级ADA4940-1ACPZ-R7
    编辑:llASEMI代理ADA4940-1ACPZ-R7原装ADI车规级ADA4940-1ACPZ-R7型号:ADA4940-1ACPZ-R7品牌:ADI/亚德诺封装:LFCSP-16批号:2023+引脚数量:16安装类型:表面贴装型ADA4940-1ACPZ-R7汽车芯片ADA4940-1ACPZ-R7特征小信号带宽:260MHz超低功率1.25mA极低谐波失真−122dBTHD,50k......
  • ASEMI代理AD9959BCPZ原装ADI车规级AD9959BCPZ
    编辑:llASEMI代理AD9959BCPZ原装ADI车规级AD9959BCPZ型号:AD9959BCPZ品牌:ADI/亚德诺封装:LFCSP-56批号:2023+安装类型:表面贴装型引脚数量:56类型:车规级芯片工作温度:−40°C~125°CAD9959BCPZ特征4个同步DDS通道@500MSPS之间的独立频率/相位/振幅控制通道频率/相位/振幅变化的匹配延迟......
  • ASEMI代理AD9959BCPZ原装ADI车规级AD9959BCPZ
    编辑:llASEMI代理AD9959BCPZ原装ADI车规级AD9959BCPZ型号:AD9959BCPZ品牌:ADI/亚德诺封装:LFCSP-56批号:2023+安装类型:表面贴装型引脚数量:56类型:车规级芯片工作温度:−40°C~125°CAD9959BCPZ特征4个同步DDS通道@500MSPS之间的独立频率/相位/振幅控制通道频率/相位/振幅......
  • ASEMI代理ADI亚德诺AD8210YRZ-REEL7车规级芯片
    编辑-ZAD8210YRZ-REEL7芯片参数:型号:AD8210YRZ-REEL7偏移电压(RTI):±1.0mV超温(RTI):±1.8mV差分输入阻抗:2kΩ共模输入阻抗:5MΩ共模输入电压范围:−2~+65V差分输入电压范围:250mV共模抑制:120dB输出电压范围:0.05~4.9V输出阻抗:2Ω小信号−3dB带宽:450kHz斜率:3V/µs......
  • AD8226ARZ-R7-ASEMI代理亚德诺AD8226ARZ-R7车规级芯片
    编辑-ZAD8226ARZ-R7芯片参数:型号:AD8226ARZ-R7输入电压噪声:22nV/√Hz输出电压噪声:120nV/√Hz电流噪声:100fA/√Hz输入偏移:200μV输出偏移:1000μV输入偏置电流:20nA输入失调电流:1.5nA斜率:0.4V/μs电源电压:±18V储存温度范围:−65°Cto+150°C  一般说明:AD82......