超越平滑: 具有边异质判别的无监督图表示学习

Title: Beyond Smoothing: Unsupervised Graph Representation Learning&nbsp with Edge Heterophily Discriminating
Cite: Liu, Y., Zheng, Y., Zhang, D., Lee, V. C., & Pan, S. (2023). Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4), 4516-4524. https://doi.org/10.1609/aaai.v37i4.25573

摘要（Abstract）

无监督图表示学习（Unsupervised graph representation learning, UGRL）引起了越来越多的研究关注，并且在多个图分析任务中取得了期望的结果。依赖于同质性假设（homophily assumption），现有的UGRL方法倾向于沿所有的边平滑（smooth）学习到的节点表示，而忽略了那些连接节点的具有不同属性的异质边的存在。因此，当前的方法很难推广到不同节点广泛连接的异质图，并且也容易收到对抗性攻击。

为了解决这个问题，我们提出了一种新颖的、具有边异质性判别的无监督图表示学习方法（unsupervised Graph Representation learning method with Edge hEterophily discriminaTing, GREET），它通过判别（discriminating）和利用（leverageing）同质边和异质边来学习表示。

为了区分两种类型的边，我们构建了一个边鉴别器（edge discriminator），从特征和结构信息推断边同质或异质。

我们通过最小化精心设计的（crafted）枢轴锚定排名损失（pivot-anchored ranked loss），以无监督的方式训练边鉴别器，其中随机采样的节点对充当枢轴。节点表示通过对比从判别的同质边和异质边获得的双通道编码来学习到。

通过有效的相互作用方案，边判别和表示学习可以在训练阶段相互促进。我们在14个基准数据集和多个学习场景上进行了广泛的实验，以证明GREET的优越性。

为了解决存在的挑战，本文的方法要识别和利用这些同质/异质边。自然的产生两个问题：

1、在无监督信号的场景下如何区分两种边？
构建边鉴别器（利用节点的属性和结构信息）
2、如何将边鉴别器和表示学习模块进行耦合
（1）利用边鉴别器的鉴别结果划分视图进行表示学习；（2）利用学习到的节点表示再对边进行重新鉴别；两部分交替训练，互为补充。**

相关工作介绍（Related Work）

图神经网络（Graph Neural Networks，GNNs）

图神经网络旨在通过基于谱理论的图卷积对图结构化数据进行建模或空间信息聚合。从图信号处理的角度来看，大多数GNN可以呗视为低通图滤波器，可以平滑图拓扑上的特征，从而在相邻节点之间产生相似的表示。不幸的是，这一特性阻碍了GNN在异质图中的能力，在异质图中，不同的节点往往倾向于连接起来。最近的一些GNN尝试通过新颖的设计来解决这个问题。比如高级聚合函数，和网络架构，然而他们主要关注半监督学习，而没有探索无监督学习的工作。

无监督图表示学习（Unsupervised Graph Representation Learning，UGRL）

无监督图表示学习旨在学习图上的低维节点表示。早期的方法通过最大化邻近节点之间的表示相似性来学习（在相同的随机游走内或相同边内）。

最近的工作将对比学习应用于UGRL，通过最大化两个增强图视图之间的一致性优化模型。然而，现有的 UGRL 方法由于采用低通滤波 GNN 编码器和增加平滑度（smoothness-increasing）的学习目标，往往会平滑每个连接节点对的表示，导致其性能未达到最佳（sub-optimal performance），尤其是在有噪声或异质图上。
另一种方法旨在从多个基于边的预定义图视图中学习表示。不同的是，GREET从具有单一边类型的途中学习同质图和异质图。这更具挑战性。

符号表示与问题描述

Notation（符号）
\(G=(V,E)\)，其中图\(G\)，节点集合\(V\)，边集合\(E\in{V×V}\)，节点个数\(n\)，边个数\(m\)
特征矩阵\(X\in{{R^{n×{d_f}}}}\)，第\(i\)行\(x_i\)表示节点\(v_i\)的第\(d_f\)维特征向量。
表示图\(G\)的邻接矩阵为\(A\in{R^{n×n}}\)，当\(e_{i,j}\in{E}\)时\(A_{ij}=1\)，否则\(A_{ij}=0\)
利用特征矩阵和邻接矩阵，图可以表示为\(G=(A,X)\)
归一化邻接矩阵表示为：\(\widetilde{A}=D^{-1/2}AD^{-1/2}\)，其中\(D\)是对角度矩阵，\(D_{ii}=\sum_{j}A_{ij}\)
图的拉普拉斯矩阵：\(L=D-A\)
归一化的拉普拉斯矩阵：\(\widetilde{L} = I −\widetilde{A}\)

问题描述
我们旨在解决节点级的无监督图表示学习（UGRL）问题。
目标是学习表示映射函数\(F:R^{n×d_{f}}×R^{n×n}\rightarrow{R^{n×d_{f}}}\)计算表示矩阵\(F(X,A)=H\)，第\(i\)行代表节点\(v_i\)的低维表示\(h_i\)，（其中低维度表示\(d_{r}\ll{{d_f}}\)）。
这些表示可以保存并用于下游任务，例如节点分类。

基本概念补充
“概念-邻接矩阵”：是一个存放顶点间关系（边）的二维数组。

“概念-特征值和特征向量”：特征值是指设A是n阶方阵，如果存在数m和非零n维列向量x，使得成立Ax=mx，则称m是A的一个特征值。非零n维列向量x称为矩阵A的对应于特征值m的特征向量，简称A的特征向量。

特征值和特征向量的意义及应用

“概念-对角度矩阵”：对角矩阵：除了对角线上的元素，其余元素都为0。对角度矩阵D：对角线上存储节点度的对角矩阵。

方法（Methodology）

GREET主要由两个组件构成：区分同质和异质边的边判别模块，以及利用两种类型的边生成信息丰富的节点表示的双通道表示学习模块。

在边判别模块中，边判别器将边分为同质边和异质边。

在双通道表示学习模块中，通过应用双通道编码组件分别对两个判别视图（views）执行低通和高通滤波器的图卷积来构造节点表示。

两个主要的组件以相互促进的方式进行训练，其中枢轴锚定排序损失（pivot-anchored ranking loss）用于训练边鉴别器，稳健的双通道对比损失用于学习信息丰富的节点表示，以及利用有效的交替训练策略使得在两个组件上的训练逐渐相互促进。

边鉴别（Edge Discriminating）

为了区分同质边和异质边，我们构建了一个边鉴别器，学习估计每个边同质的概率。（类似于计算一条边两端节点的相似程度）
给定两个相邻的节点，它们的同质概率本质上与两个因素有关：包含其语义信息的节点特征和反应其拓扑作用/地位的结构特征。
直接整合结构和特征信息的工具是GNN，然而GNN倾向于平滑特征，而丢失了异质相关的知识。因此，我们考虑另一种方案，也就是用向量结构编码对结构特征进行建模。这样，有效的证据可以通过将节点结构编码与原始特征连接被保留。本文在进行初次视图划分时使用的表示采用【原始属性+结构编码】的结构。

特别的，我们采用基于随机游走扩散过程的结构编码来捕捉图的结构信息。节点\(v_i\)的\(d_s\)维位置编码\(s_i\)可以通过基于\(d_s\)步随机游走的图扩散来计算。即节点\(v_i\)的\(d_s\)维位置编码可以从\(d_s\)次随机游走的转移矩阵中得到：
\(s_i={[{T_{ii},T^2_{ii},...,T^{d_s}_{ii}}]}\in{R^{d_s}}\)(1)
其中\(T=AD^{-1}\)是随机游走转移矩阵（random walk transition matrix），或者称为随机游走算子。这里\(s_i\)的计算使用了一个低复杂度随机游走矩阵的算法，即仅仅考虑节点i到自身的转移概率。

参考：可学习的GNN位置编码

补充：
"Random Walk Transition Matrix" 是一个矩阵，通常用于表示这些状态之间的转移概率。这个矩阵的行和列对应于状态集合中的不同状态，矩阵中的每个元素表示从一个状态转移到另一个状态的概率。这些概率必须满足以下条件：1、每一行的元素之和等于1，因为在每个状态下，下一步只能移动到状态集合中的某个状态。2、转移概率可能会随时间变化，这取决于具体的随机游走模型。
将原始特征和结构编码作为输入，边鉴别器利用两个MLP层估计同质概率：
\(h^{'}_i=MLP_1([x_i||s_i]), h^{'}_j=MLP_1([x_j||s_j]),\theta_{i,j}=(MLP_2([h^{'}_i||h^{'}_j])+MLP_2([h^{'}_j||h^{'}_i]))/2,(2)\)

其中\([·||·]\)表示串联操作，\(h^{'}_i\)是节点\(v_i\)的中间嵌入，\(\theta_{i,j}\)是边\(e_{i,j}\)的估计边同质的概率。

为了使估计的概率不受边方向的影响，我们将第二个MLP层应用于不同顺序的嵌入。（此处作者考虑到去除边两端节点的顺序因素，实际在计算同配概率时，对两个节点的表示进行了不同顺序的拼接以计算概率，最终将两者的结果取平均作为最终概率。）

利用估计的概率\(\theta_{i,j}\)，目标是从伯努利分布\(w_{i,j}~Bernoulli(\theta_{i,j})\)中采样边\(e_{i,j}\)二元同质指标\(w_{i,j}\)，其中\(w_{i,j}=1\)表示同质性，\(w_{i,j}=0\)表示异质性。然而采样是不可微分的，这使得鉴别器难以训练。为了解决这个问题，我们使用Gumbel-Max重参数化技巧近似二元指标\(w_{i,j}\)。具体来说，离散的同质性指标\(w_{i,j}\)被放宽（relaxed）为连续的同质性权重\(\hat{w}_{i,j}\)，它使用以下公式计算：\(\hat{w}_{i,j}=Sigmoid((\theta_{i,j}+log{\delta}-log(1-\delta))/\tau_{g}),(3)\)
这里的\(\delta\sim{Uniform(0,1)}\)是采样的Gumbel随机变量，\(\tau>0\)是一个超参数，\(\tau\)越接近0，\(\hat{w}_{i,j}\)越尖锐（更靠近0或1）。

参考：重参数化技巧

利用估计的边同质性指标，我们将原始图\(G=(A,X)\)区分为同质图视图和异质图视图，\(G^{hm}=(A^{(hm)},X)\)和\(G^{ht}=(A^{(ht)},X)\)。为了使边鉴别可训练，我们没有明确地将边分为同质和异质类别，而是当边在同质或者异质视图上工作时为每个边分配一个软权重：
\(A^{(hm)}_{i,j}=\hat{w}_{i,j}, A^{(ht)}_{i,j}=1-\hat{w}_{i,j}, for\quad e_{i,j}\in{E},(4)\)

双通道编码（Dual-Channel Encoding）

模型训练（Model Training）

实验（Model Training）

实验设置

实验结果

结论

--------------------------------------未完待续----------------------------------