1. 文章小引

文章题目：识图之要，在于图识：参考图以重连，同音相求
文章刊载：新近发表于Arixv，岁在乙巳，仲夏之月
文章门类：图神之络，重连之术
文章代码：https://github.com/harel147/REFine
文章缘起：

2. 文章撮要

图神经网络（GNNs）长于析图结构之数，然遇异亲图则困，盖因相连之节点，往往属异类。虽此难常以专筑之GNN架构解之，然于此境，图形重布犹为未足穷之策。吾辈既立连接边缘同态、GNN嵌入平滑及节点分类之理，遂启增强同态之需。于此基上，吾等创一重布之框架，该框架以参考图增图之同态，且从理上证重布之图亦具同态。为广其用，吾等又倡一标签驱动之扩散法，以节点特征与训练标签构同态参考图。经广量仿真，析原始图与参考图同态于重布图同态及下游GNN性能之影响。吾等于十一实数据集上评吾法，结果表明，此法优于既有重布之术及异亲图专筑之GNN，于保高效与可扩之同时，增节点分类之精。

3. 相关介绍

3.1 背景介绍

是故，本文立论，边缘同质之性、图谱之学，与 GNN 嵌入之平顺及 GNN 之效能，遂有理实之通联。
理析有云，于低同质之图，欲使学习节点得准确分类，则其嵌入于图谱，必难平顺。此与 GNN 之讯息递传机理相悖，于多般情形，GNN 倾向于沿图谱结构，使嵌入平顺。

为系统制控图谱之同质率，乃取自流形之学的扩散之术。利用未尽之信息（节点之特征与节点之标签），构同质图谱为参照。

本文又立数种图谱同质之度，以衡图谱中标签相关之异同，其要者有：边同质性、节点同质性、类同质性、邻节点同质性。尤重边同质率，此乃最简且最常见之度，量化连接同标签节点之边之比。

今之研习，处理异质图构之GNN架构有：MixHop者，聚多跳邻信息以拓GNN；GPRGNN者，引广义PageRank权重之自适应习得机制；H2GCN者，纳高阶连接模式以益消息传递；CAGNN者，用共享混合器自适应地融邻信息。

全图之边同质率，可定义为

3.2 用参考图以控同质率

实验之研显，GNN于同质图上之表现胜于异质图，此乃标准GNN架构所致。
迪利克雷能量，此度乃摄嵌入于全图结构中变之平滑，小值示邻接节点间之微变（平滑），大值示邻接节点间之巨变（波动）。
GNN中之信息传递机制，每致节点嵌入之平滑。GNN之本质，乃降平滑度项$tr(Z^T, LZ)$，然此非恒宜，或致过度平滑。

定理一：

上式之不等式右端，乃线性可分离嵌入之平滑度下限也。同质性愈高，则下限愈小，使 GNN 更易得平滑且线性可分离之嵌入。反之，于异性图，增界之下限，反增消息传递所引平滑之可能，损及线性可分离性之风险。
图之同质性愈高，GNN学得线性可分、故更效之节点嵌入之潜能愈大。

四、增同质之图重连法

参考图Gr定义为（v，Er），依Er之边增删k条边以改边集，定E(k)。

其中Sk为k条边之随机子集，k。>0表添边，k<零表删边。

四一 添边

定题

故有，

当合乎条件，则依参考图添边，于期中增同质。

四二 删边

当k<0时，图重连g(k)乃删自 ℰ∩ℰ_r^c之边，其数如|k|，而择之随机。

当合乎条件，则依参考图删边，于期中增同质。

四三 真实世界数据集上验之

边添以重连，于康奈尔数据集之效，其列各表异 $g_{r,p}$之用。 具异质性，由异 p 值制之。

边刈除于Cora数据集之效

当合乎条件，去边增同质性（红线下之绿线），否则减之。然，同质性高非必增GCN之效，盖或生过度挤压也。

5. 图重连之术

若特征空间能提供与标签相契之意义相似度，则基于特征亲和力之参考图当为同性。吾之要旨，乃将节点特征与训练标签相合，以构参考图，非惟同性，且可推于未标节点。
本文引扩散之法，由全可节点特征 𝐗 所建之图，使标签信息流布于未标记之节点，以“成”所缺之标签。此法得窥特征与标签间之共构，故所生者，较之常情独构者，尤胜焉。 十 所造参考图，其同质性更胜。

本图重连算法之步骤：

• 对原象行分群
• 依节点之特征与节点之标签，为每一聚类构参考图。
• 于每一聚中，依参考图行图重连之术。
• 通过联缀聚类间之边，以构连性愈强之图

建参考图Gr之始，当以节点特征向量构亲和矩阵WD。于i，j属{1,2,...,n}，d(,)乃距度，ϵ为控亲率尺度之超参数。

次之，以标准之内核归一法，对亲和率矩阵施以归一之术，得数据核D。故可求对角矩阵D1，其主对角元乃WD之总和，以之得中矩阵D'。复以D'与D2合为对角矩阵，再行归一之步骤。

就节点标签之亲和性矩阵而言，立二进制矩阵之定义

同然，$W_p$可基于具标签亲合之图回归之连续标签而构，以施于$W_D$之同归一化于矩阵$W_p$以归一之。生标签核P。

上述P与D之积，τ = PDP，乃以标签为导之扩散过程，含三步：一者，以可用标签行类内传播；二者，循节点特征相似性遍历诸节；三者，终以标签行传播。
故可依 $\tau$ 以定参考图之边集，盖 $\tau$ 之元素连续，故可裁之，得与无权图之邻接矩阵相应之二进制矩阵。首当计算 $\tau$ 之每行之平均。示公式如左。
$$\mu_i = \frac{1}{n}\sum_{j=1}^n\tau(i,j) $$
依此平均值$\mu$，可得不裁之核

可延展之性
此算法倚核操作，故计算之费甚巨，不适宜于巨图。为保可扩之性，乃用METIS算法，将图g聚为N子类。$N=\frac{|V|}{c}$，C者，聚类之大小也，为超参数。每集群$g_l$，据其参照图，独立重接之，终以合并诸连接聚类，重建全图，且存原图聚类间之边。

REFine算法伪代码为

六、实验之设

六·一 基础之验

对算法：SDRF、FoSR、BORF，
节点分类之验，其数据为

盖算法本乎同质性，故于异质图亦大有裨益。算法于异质图神经网络之框架，意义非凡，所采框架有MixHop、H2GCN、GPRGNN、OrderedGNN，及本算法基于标准GNN（GCN、GATv2、APPNP三者）之图重连算法。验之数据如下

六·二 消融之验

一、同质与算法之进
察得同质率愈低之数据，本算法加入后，于GNN之测试准确度提升愈大。

二、唯用训练标签为亲和性矩阵
即意味着以τ = P代τ = PDP，测试准确率随之 |k| 增而降，验之，但恃训标而不顾数据，则于未标节点之泛化力，其效甚微。

数据者

三，聚类规模超参数
聚类之众，则效增而时耗亦长。

7. 概要

主者，异质图之图重连算法也，合三术以成之。METIS聚类以减全图之算，析为小图；用亲和矩阵以构参考图；聚类间图重连之术也。

8. 个体之思

之图重连算法，渐施于异质图。通用领域之baseline已高，当于图神经网路之支脉，以探掘之。