论文题目：Homophily-oriented Heterogeneous Graph Rewiring
论文发表：WWW 2023
论文领域：图神经网络，图重连
论文背景：
随着互联网的快速发展，异构图（HG）呈爆炸式增长。最近，异构图神经网络（HGNN）在学习HG方面显示出巨大的潜力。目前对HGNN的研究主要集中在一些具有强同源性的HG上（由元路径连接的节点往往具有相同的标签），而对那些不太同源的HG的讨论很少。最近，关于具有异质性的齐次图的研究很多。然而，由于异质性，将他们的方法扩展到处理异质性HG是不容易的。在这项工作中，基于实证观察，我们提出了一种元路径诱导度量来衡量HG的同质性。我们还发现，当前的HGNN在处理具有较少同质性的HG时可能会出现性能退化。因此，提高HGNN对非同源HG的泛化能力至关重要。为此，我们提出了HDHGR，这是一种面向同质性的深度异构图重布线方法，可以修改HG结构以提高HGNN的性能。我们从理论上验证了HDHGR。此外，在真实世界的HG上进行的实验证明了HDHGR的有效性，它最多可以带来10%以上的相对增益。
1，提出了一种新方法，元路径诱导度量（meta-path-induced metric），可以衡量异构网络的节点相似程度。可基于该指标来量化分析同构节点对HGNN的影响
2，提出了新方法HDHGR，一种基于同质性导向的深度异构图重连线方法，通过降低异质性来提升异质图神经网络（HGNNs）的性能。该方法具有通用性，可应用于含或不含元路径输入的HGNNs模型。从复杂性度量角度，我们提供了理论分析，证明该方法对增强HGNNs的广泛性能力具有显著效益。
3，在不同的异构图的数据集上的实验证明了方法的有效性
定义1，异构图，图的节点和边都有着各自的类型。与同构图的区别是看边的类型是否多个
元路径的定义，代表的是节点和边的组合关系
元路径的子图的定义，表示的是该子图内是一个同构图，其中所有的边属于元路径中
异构图神经网络，从不同的类型的边，基于不同的权重从边上来捕获邻域信息。
元路径子图的同构性比率，衡量整个图的同构率。表示的是同构边的数量占总的边的比例。
异构图重连的定义：图重连技术的目标是通过更新边来学习到最优的图。异构图重连模型的工作分为两个阶段，相似度学习和基于相似度的异构图重连。
整个异构图重连算法的架构为
在实验中发现，HGNN在有着同构元路径子图上的异构图上比只有非同构元路径子图的图数据效果更好。
数据发现，整个异构图的表现和元路径子图同构率相关。
那么对于整个图来说，有异质图同配率的定义为
它通过计算基于不同跳数元路径的子图上的最大同质性比率，得出给定图的最大潜在同质性比率。
本文的核心算法HDHGR（Homophily-oriented Deep Heterogeneous Graph Rewiring method）算法。整个算法的架构图为
对于语义空间下的节点相似度，通常考虑两个部分：NAD（neighborhood attribute distribution）和NLD（neighborhood label distribution）
基于节点与节点之间的cos相似度
可以得到属性相似度矩阵和标签相似度矩阵
把异构图作为一个同构部分来进行编码
节点与节点之间相似度在元路径诱导子图中为
节点和标签的损失函数为
最终的损失函数为
每一个元路径子图都包含不同的语义信息和不同的相似度。需要对所有的子图进行优化。
直接对每一个元路径子图进行优化，会导致MSL不能充分学习到一些重要元路径的信息。同时一些元路径会对MSL训练有负面效果。所以给每一个元路径以一个不一样的权重
采用多目标优化方法来确定各目标的权重系数。具体而言，该方法基于高效的Frank-Wolfe优化器，在现实假设条件下求解𝜆Φ𝑖（𝑖 = 1,...,𝑀）的帕累托最优解。
获得了每一对目标节点对的相似度后，可以移除低相似度的边，增加高相似度的边。有三个参数来调节这个过程：
K值，每一个节点能够被加上的最大的边的数量；
ε阈值，高于该值的相似度的边被添加；
γ值，低于该值的相似度的边才被删除；
使用复杂度衡量来分析HGNN的同构性和泛化能力。复杂度CM的定义为
基于异构图的性质，H是有着不同参数的RGCN，S是异构图数据，在这里使用表征一致性来作为CM。该度量方式基于Davies-Bouldin index（戴维斯-波尔丁指数），这是一种用于评估聚类算法性能的指标，常用于衡量类内距离与类间距离的比值。
那么μ是类𝑖的聚类质心。S可被视为类内距离的标量度量，M是类i和类j之间的分离度的标量。
最终的CM可以写为
当p=2时，CM可以看作是类间类内的比率。有以下的定理
在异构图G = (V, E, 𝜙,𝜓)上，给定元路径集合R，我们考虑一个二分类任务，其条件是每个节点𝑣𝑖 ∈ V的邻居节点在元路径𝑟下与𝑣𝑖属于同一类的概率为𝑃𝑟。对于任意元路径类型𝑟 ∈ R，当𝑃𝑟 → 1时，HGNN的泛化能力上界达到最优。
采用的的数据集
其中包含4个异构数据集（FB-American，Actor，Liar， IMDB）和2个同构数据集（ACM，DBLP）
对比算法
HDHGR可通过HGNN训练实现解耦，所以选择4个同构GNN（GCN，GAT，H2GCN，LINKX）和5个异构GNN算法（RGCN，HAN，HGT，SHGN）。
此外为了验证算法在异构图重连领域的有效性，对比了三个异构图结构学习算法（LDS，IDGL，HGSL）
评价指标
使用F1-macro和F1-micro作为评价HGNN的指标，使用平均相关提升，来衡量HDHGR的效果。
平均相关提升(average relative improvement ARI)的定义
在非同构图上的实验结果
有如下的结论：
1，同质性对异构图神经网络性能具有重大影响；
2，HDHGR处理后的异构图数据，HGNN的表现总是得到提升；
3，HDHGR在非同构图数据上表现更优。
图结构学习和图重连方法的比较中，引入原始的元路径方法 OriMetapath 方法，直接加入后获得了不佳的表现。一个合理的解释是原始方法包含大量的跨类节点间的连接。而HDHGR可以减少大量的冗余边。HDHGR和其他方法比较都表现更佳
消融实验
探讨使用不同的信息去学习MSL，只使用标签信息 w/o Label，只使用属性信息 w/o attr，均分所有的meta-path的权重而不通过学习权重 w/o MO。
整体论文架构分为核心观点的给出，理论证明，实验验证的环节，很规范的学术文章。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。