ICLR 21： SSGC SIMPLE SPECTRAL GRAPH CONVOLUTION

1. model

其中 公式11 T 就是 所谓的 diffusion matrix，这里选用 对称 归一化邻接矩阵 ，这个 形式 理解起来就是 SGC 的升级版本， 因为SGC只是 用了第 k层的表征，k过大还是会出现过拟合， SSGC 这里 是 对 k层所有的表征 进行求和。

这里对于 xi和 hi 强制其 二范数的平方=1， 且在q（H）中利用两者差值来减小差异。作者声称 通过余弦距离 而非 欧氏距离，但这里两者做差 就是欧氏距离吧，余弦距离，不应该是 两个向量的内积 相似吗？
q（H）中的第一项：就是拉普拉斯正则项，最小化第一项就是 当 归一化邻接矩阵 ij处元素=1，两者距离minimize，（相连接节点距离相近，特征相似） 若Aij=0，则两者之间的距离则不 影响 损失的大小。---- 正则项会使得 相邻节点更加相似，即拉近距离，但不会推远

这篇文章写的不是很清楚，这段从 However开始，就是一些经验的做法了，作者说出 12拉普拉斯 正则会 因为过平滑导致 次优，但前面作者的论点一直是 sgc只用k层会过平滑， 这里 汇集k层的 就不会，但这里 对于k项还是说出会过平滑。其实实质是 公式11 就类似于 JKnet，每一层都到最后一层sum。

因此，为了效果好一点，当公式11 k=0，单位阵，就是原始 X 经过线性变化的值，作者在 k>0的层进行消息传递时，每一层都会加上一个最初始X ，等到k层 求完之后， 经过一个 参数矩阵W 进行softmax。

请注意： 和APPNP不同的是，这里的 init残差X0是 原始特征X，而不是XW， 且 线性转化都是 在k层聚合后，进行整体的 W转换维度， 这需要在代码中仔细看看， 因为appnp包括 GCNII等，都是选择先 进行 降维，以减小消耗。 但是 如果 从矩阵 乘法的角度 来看： 括号外的W 乘到里层，对于TXW采用结合律 XW 后面αXW，这样就变成 TX0+αX0，这 就和 appnp 很相似了。

唯一不同的就是 SSGC 每一层 的表征 只是 最开始X 经过 TkX得到的，而 APPNP则是 每一层表征是 由上一层 得到的（上一层= AX+H0）， 即 SSGC 每层的表征都是 可以独立预先求解的，而不是依赖于上一层，需要逐步求解，这一点很像SGC

2. APPNP联系

作者在这个比较容易 混淆的 地方 也举出了例子，通过layer1和layer2举例说， 第一层 Z1 = TX0W + XW 两者是 alpha=0.5是相同的。
但当layer=2， APPNP ： Z2 = （1-alpha) Z1+ XW = (1-alpha)T{(1-alpha)TXW+alphaXW} + alphaXW = (1-alpha)(1-alpha)TTWXW +…+. 这很容易 看出 APPNP 和SSGC的 不同。

此外 因为优化器反向传播 需要对 W求导， 链式法则 在非线性上 变得复杂， 本文直接采用线性 XW， 没有看过ppnp代码，估计也是一个linear吧。

3. 相似的方法对比复杂度

4. 实验

4.1 聚类

采用 仅基于数据固有信息的内部标准 来选择 调节最好的 K

4.2 社区检测

Reddit 上进行 inductive 学习

4.3 节点分类

OGB的实验 作者发现 products和 arxiv上无法超过graphsage， 同时发现 mlp在这两个上都超过了softmax，他采用 mlp替换了 linear classifier，（SSGC+MLP），发现还是有部分效果。

4.4 文本分类

4.5 层数和 参数alpha

table9 关于 alpha的实验，很小的alpha 才有一些提升， alpha是 初始残差的权重，当其=0，对比 节点分类那节的实验，SSGC wo/init residual 的效果 是比 SGC要好的，但是 低于 APPNP，因此很小的残差也有用。

文章除了 在那里和 APPNP进行了对比，其余的地方都很少和 APPNP进行对比，比如探究文本分类，层数和OGB上，有一些不完善，从文章的复杂度来将，本文 在 SGC的基础上 存储了多层，超过SGC是大概率的。
没有添加残差之前，是不如APPNP的， 作者为了增加残差，同时减小复杂度，是增加了一个类似的init的残差， 但因为每层表征是独立的，反向传播无需复杂度的消耗。

5. think

SGC 后续的工作也很多， SIGN SAGN GAMLP等都是 针对 SGC 没能获得 多个感受野信息，从而 预先计算 进行拼接。加入注意力等等（不同感受野 attention 计算方式不同，采用拼接求和等等）
APPNP后续的经典工作 就是 GCNII，加入单位映射、初始残差等。 pagerank 幂迭代 有关pagerank markov的通俗讲解

看完代码之后，本文实质上就是1/k * SGC多层求和 + 了一个 最开始的 alpha*AX。确实没有 对X 先进行特征转化。
采用了大量实验，来弥补novelty。

这篇文章的 每一层alpha还是像 appnp一样是 固定的， 可以采用 多种 attention，会增加参数(一个大小为k的向量），且不能提前计算。

6.code

代码里面 ssgc+Mlp

或者ssgc处理cora

是原文这里的 处理 ，作者先得到整体的表征，最后的model只是 采用 一个 linear来实现 W，这里的求和 emb 最开始 赋值为 alpha*X 在每一层 都是 加上 （1-alpha）*features ，features的计算公式 是多次稀疏矩阵adj和X的乘法，第一层传播一次。此外这里 将1/k 放到求和符号里面，即(1-alpha)*features/degree， 再看 原文的公式 会发现 1/k 和K次求和αX 约去，则就加上一次的 αX就行。

model

聚类细节

这里 对AX 传播后的表征 进行奇异值分解，得到usv，emb和这个右奇异值转置进行内积，送入kmeans， 循环结束的条件 参考了 AGC




即当下一次的 标签距离大于 上一次 就跳出，选取上一次的作为最优，或者max_iter 。 聚类没有真实标签，这里采用
和kmeans 预测的 标签进行 比较 这里具体做法参考 ： AGC Attributed Graph Clustering via Adaptive Graph Convolution

SSGC+MLP

作者在论文里面提到 过于 OGB的部分数据，发现 MLP 效果好于 softmax，因此 采用 MLP替换了 SSGC中最后一层的softmax
具体实现：

这里类名是 SGC的原因是，其 基于 pyG的SGC 修改的 source。 在最后一行， 直接将 emb 输出，而不经过 log_softmax.

损失这里 直接 计算 nll_loss 。
softmax,logsoftmax,nll_loss, cross_entroy 具体见：多分类损失函数
cross_entroy = log_softmax + nll_loss

log_softmax = log+softmax 单独做 log+softmax 速度慢，且存在溢出风险 一般合并这两个操作 上面链接 评论区的一个回复

softmax : 将 值 映射到(0,1)
logsoftmax: 将softmax值 映射到（-∞，0）

nll_loss: 将输入取反，计算和label的 乘积 求和 再平均

例子 ------------------------- 很直观 ：example

因此 SSGC+MLp这里没有 进行 log_softmax, 直接 emb 和对应的 标签 进行了 损失计算（ 把emb 该节点的类别 所在列的值 取反和 标签相乘求和 再平均）

交叉熵：是 对应 真实的标签 和 求得的 标签 乘积求和，，， 真实的标签是 one-hot， 对应的 类别 元素=1， 取出来预测的emb，先通过 log_softmax 到（-∞，0） 在进行nll_loss时候， 取相反数 值映射到（0，+∞）， 两者乘积求和平均为损失， 若想让该损失小，则其值 越接近于0+越好， 则回推， log_softmax 的值 越接近于 0-越好。 则 softmax的值 越接近于 1 越好。 因此 两个类别（真实和预测的）会产生一致性约束

关于 这几个联系 model 最后一层是 linear 采用 cross_entroy. 是softmax 采用 nll
链接 stackoverflow里面关于softmax+negative_log_likelihood

什么是 对数似然 log likelihood
链接 主要从 离散和连续 随机变量 对于参数估计问题进行阐述，negative 是 为了目标函数求最小化，加个负号。 log 是将 指数乘法 变成 加法（原因：乘法不稳定等） 。 似然就是 通过 采样得到的样本去 衡量分布，去拟合分布的参数。 结合上文的多分类问题，我们通过 gnn 得到 emb，emb经过softmax得到 标签的 概率分布，通过和 真实分布 进行最大似然估计，得到损失，最小化损失，以使得 预测分布准确。

交叉熵和最大似然估计结合 花书 5.5 上说明了 最大化似然==最小化负对数似然 == 最小化 交叉熵

SSGC 不采用softmax 直接 nll 不会使得 节点的emb（没有采用logsoftmax）变化么？，，，，，， nll 则会让 节点的 emb 对应的 那类的那一维度的 值变化？ 还是不太理解 这里不 采用 softmax 而是单独采用 nll（作者原文说 这样是 MLP了）

自己测试了一下：



这里 target 是 nll_loss 自动将 target （不是onehot）编码成 和 lsm 大小相同的 tensor（3*8），实现了 one-hot，和lsm进行元素间点乘— == 1/3(2.1469+2.3010+1.3672) = 1.9384

SSGC+MLP 不就是 假设 标签那维度 特征作为 概率值，，，好奇怪，