【GNN报告】 北京大学张牧涵：谱图神经网络有多强大？
目录
1、简介
报告嘉宾：张牧涵（北京大学）
报告题目：谱图神经网络有多强大
报告摘要：
谱图神经网络（Spectral GNN）是一种基于图信号滤波器的图神经网络，广泛应用于节点任务。大量知名的GNN可以归入谱GNN，比如ChebyNet、GCN、和BernNet，但是对谱GNN表达能力的分析一直相对欠缺。我们首先将谱GNN简化为线性GNN（Linear GNN），并证明了Linear GNN在温和条件下可以产生任意一维输出，间接给出了谱GNN的万能逼近定理。我们随后建立了谱GNN表达能力和Weisfeiler-Lehman Test之间的联系，后者常用于刻画消息传递图神经网络的表达能力。最后，我们分析了基选择的问题并提出了一种新的谱GNN－JacobiConv。JacobiConv使用Jacobi Basis，且仅使用线性层就达到了SOTA的性能。
参考文献：
Xiyuan Wang, Muhan Zhang, How Powerful are Spectral Graph Neural Networks,ICML 2022
https://arxiv.org/abs/2205.11172v2
Code: https://github.com/GraphPKU/JacobiConv
报告人简介：
张牧涵博士，北京大学人工智能研究院、智能学院助理教授，北京通用人工智能研究院研究员，国家优青（海外）项目获得者，北京大学博雅青年学者。2015年本科毕业于上海交通大学IEEE试点班，2019年于美国圣路易斯华盛顿大学获得计算机科学博士学位，2019-2021年期间曾担任Facebook AI研究科学家。在ICML，NeurIPS，ICLR，AAAI，KDD 等机器学习顶级会议发表论文15篇（其中一作11篇，通讯4篇）。入选清华大学AMiner评选的AI2000人工智能最具影响力学者。作为图神经网络的早期研究者，提出了多种经典算法，包括图分类的Sortpooling算法、链路预测的SEAL算法、矩阵补全的IGMC算法等，成果被多次写入图深度学习标准库。担任NeurIPS 2022 领域主席、ICML 2022领域主席、 IEEE BigData 2021副主席，并常年担任 NeurIPS、ICML、ICLR、AAAI、IJCAI和 JMLR、TPAMI、TNNLS、TKDE、TSP、AOAS、JAIR等顶级会议和期刊的审稿人。
2、谱图神经网络有多强大？
背景
λ（频率）刻画了节点之间的变化程度
0对应的那4个节点都是相同的值，代表是低通的
其他三个变化剧烈
对某个节点特征进行可视化和数据分析
GCN就是一个低通滤波器，GPRGNN是一个科学系的滤波器（g是离散的）
理论有3个条件，对于第一个条件使用多个单独的滤波器
- 输出单维的
- 不能有多个相同的特征值
- 原始图信号需要包含所有频域分量
不仅可以区分不同图，还可以区分同一个图上不同节点
不能有多个相同的特征值，自同构<3，只需要图不那么对称即可
图只要具有丰富的信息，很好满足原始图信号需要包含所有频域分量
多重特征值判断：
谱分解（直观上就是图没那么对称即可满足）
如何保证所有频率都存在：
看初始nodeX特征在频域分量上的投影都不为0，只要有一个初始的rich节点特征，一般就可以满足该条件
结论
抛弃非线性（包含MLP），使用linear GNN就可以达到强有力的模型表示能力
Linear GNN不会无中生有产生一些频率，在Node级任务上Linear GNN即可满足
核心结论
核心模块JacobiConv
实验
结论
3、小结
多重特征与图对称性相关+图频率与初始特征rich与否相关
问答
1、高通对应变化剧烈信号，那低通会不会对高频信号有梯度爆炸现象产生？
实际文章中对高通信号做了一个限制，抑制高通信号。
2、阶数高，滤波器拟合效果变差，未来咋高阶上有什么可以优化的点吗？
残差连接+泛化能力的优化
3、GNN存在过平滑，那在您的谱图模型上会有这个问题吗？
不会，谱图上不存在过平滑。低频信号是导致过平滑的原因，但是在谱图上不仅有低通信号还有高通信号，因此不会出现。
4、1-WLTest
用于图级任务，node任务不那么需要图结构信息，节点特征往往足够分类，但是链接预测和图级任务上和图结构息息相关。
5、Trans+GNN的结合发现过拟合现象消失，但是怎么解释？
Trans本质上用了distance编码，且是计算全局所有节点之间距离，相当于在拟合高阶的滤波器，变相的变成一个高通的甚至任意的可学习的滤波器。
6、在连接预测任务上，目前大多都是抽取子图做的，那有没有不基于子图的？
有，可以直接计算node-pair之间的表示；补充：对于稀疏图直接用GCN和GAT时足够，但是图非常稠密等下抽取子图更有增益（貌似那个老师口误。。）