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

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）

边鉴别（Edge Discriminating）

双通道编码（Dual-Channel Encoding）

模型训练（Model Training）

实验（Model Training）

实验设置

实验结果

结论

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