Graph Structure Learning（图结构学习综述）

Graph Structure Learning
博主以前整理过一些Graph的文章，背景前略，但虽然现在GNN系统很流行，但其实大多数GNN方法对图结构的质量是有要求的，通常需要一个完美的图结构来学习信息嵌入。

即，真的不是万物都可Graph的。比如图结构中的错误，误连，缺失或者拓扑不平衡都会导致噪声在图中传播，会极大地影响到效果，比如药物，社交等场景应用中。然而，图中噪声的普遍性却代表着，我们需要学习关于真实世界问题更鲁棒的表示。因此图结构学习(Graph Structure Learning, GSL)的目的就是旨在共同学习优化的图结构及其表示。本篇博文整理2篇，2021年的综述论文《Deep Graph Structure Learning for Robust Representations: A Survey》和IJCAI 2022的《A Survey on Graph Structure Learning: Progress and Opportunities》。

Deep Graph Structure Learning for Robust Representations: A Survey

图形结构学习(GSL)的一般范式如上图。即

从一个原始的图结构开始。通过一个结构建模模块对图的结构进行细化/优化，也是GSL里面比较重要的模块了。
然后再输入到一般的gnn中，其中获得节点嵌入来计算学习目标函数。
其中GNNs和结构建模模块中的参数将交替（或联合）更新，直到满足预设的停止条件。

即分别对应着三个小模块：structure modeling, message propagation, and learning objectives。

structure modeling。现有一般对图结构进行细化的方法有三种1 Metric learning；2 Probabilistic modeling；3 Direct optimization。
message propagation。这里一般根据任务来设置模型。原始图结构为A*，进过gnn的传播之后表示为Z*。这三种后面再详细说明。
learning objectives。由两个部分组成，task即根据不同的任务设置，如节点分类的交叉熵和链路预测的贝叶斯个性化排序损失。reg用来正则化学习到的图结构，以满足一些先验的拓扑约束，如稀疏性和低秩性质。 L = L t a s k ( Z ∗ , Y ) + λ L r e g ( A ∗ , A ) L=L_{task}(Z^*,Y)+\lambda L_{reg}(A^*,A) L=Ltask(Z∗,Y)+λLreg(A∗,A)

Metric learning
两个节点之间的一条边的权重可以表示为两个端节点之间的距离度量。度量学习方法通过学习一对表示中的度量函数来细化图的结构即邻接矩阵A。 A i j ′ = ϕ ( z i , z j ) A'_{ij}=\phi (z_i,z_j) Aij′=ϕ(zi,zj)然后再把这个结果合并到原来的邻接矩阵中 A ∗ = g ( A , A ′ ) A^*=g(A,A') A∗=g(A,A′)这里的g一般用插值 interpolation，或者注意组合attentive combination。 A ∗ = α A ′ + ( 1 − α ) A A^*=\alpha A'+(1-\alpha)A A∗=αA′+(1−α)A同时一般会加一些稀疏正则化，因为密集图不仅带来沉重的计算负担，而且可能包含噪声。因此，通常根据边的权重作为后处理操作，从而得到一个kNN图(即每个节点有多达k个邻居)或一个eNN图（即权重小于e的边将被丢弃）。

如上图可以看到metric用的多的用高斯核函数、内积、cosine相似度、注意力或者混合，即得到这一步的操作 A i j ′ = ϕ ( z i , z j ) A'_{ij}=\phi (z_i,z_j) Aij′=ϕ(zi,zj)。然后再做post-processing处理参数问题。

Probabilistic modeling
度量学习方法是直接从成对的关系中推导出边权值，而概率建模是通过修改图的结构，即以这种确定性的方式来完成。概率建模方法假设图是通过来自特定分布的采样过程生成的，并使用可学习参数对采样边的概率进行建模。

考虑到图的结构通常用离散矩阵表示，从离散分布中采样是不可微的。因此，这些方法的一个主要障碍是如何使这些采样操作可分，并可以使用传统的梯度下降方法进行优化。其中大多数工作都采用了重参数化技巧，允许反向传播在采样过程中流动，即Gumbel-Softmax trick。也有文章都是明确对噪声进行建模，即噪声生成器+图生成器。 L = L p r o x ( A ′ , Z , E ) + L ( E ) + L ( Z ) L=L_{prox}(A',Z,E)+L(E)+L(Z) L=Lprox(A′,Z,E)+L(E)+L(Z)

Direct optimization
不同以上两种，这种方法则是直接处理图的邻接矩阵和图参数，因此图先验和优化是这类方法的核心。比如可以直接利用给定的类标签同时细化网络拓扑和学习GNN参数，即假设属于同一类的节点应该相互连接，因此可以直接约束为 L = 1 2 ∑ i , j A i , j ∗ ∣ ∣ y i − y j ∣ ∣ 2 2 L=\frac{1}{2} \sum_{i,j} A^*_{i,j} ||y_i-y_j||^2_2 L=21i,j∑Ai,j∗∣∣yi−yj∣∣22

Future

更复杂的关系
异构图
节点的初始属性嵌入
可伸缩性
泛化能力

A Survey on Graph Structure Learning: Progress and Opportunities
有一些概念跟上面的survey有重复，因此只列部分重要点，详细可看完整论文。

Graph Structure Modeling

Metric-based Approaches。使用核函数计算节点对的相似度：（1）高斯核函数，（2）内积，（3）余弦相似度，（4）扩散核函数，(5) 结合多种核函数。
Neural Approaches。使用神经网络来预测边权，如 attention或graph transformer较为流行。
Direct Approaches。将邻接矩阵作为学习的自由变量，不依赖于节点表示对边进行建模，因此具有更大的灵活性，但如何学习矩阵参数会更困难。

Postprocessing Graph Structures