Page 227 - 《软件学报》2026年第2期

706 软件学报 2026 年第 37 卷第 2 期

边连通性. 这种表示方式不仅保留了图 G 的局部结构信息, 还揭示了不同分区之间的交互关系.
K 的采样. 采样过程始于
本文利用分区间的连通性, 通过子图采样器 S 基于多跳信息对分区进行固定大小为
随机选择一个分区作为起始点, 随后依据相似性度量 (如公式 (2) 所示) 自内而外地采样其多跳邻域内的分区, 直
至达到预定的采样数量 K. 所选分区的索引集可表示为:

 ( )
 idx = S ¯ A,K






 ( ) (5)
 E idx v si ,v t j = 1,∀v si ∈ ¯ V s ,v t j ∈ ¯ V t






 N idx (v ci ) = 1,∀v ci ∈ ¯ V c ,c ∈ idx
N×N N
其中, 边采样矩阵 N idx ∈ {0,1} , (s,t) ∈ idx×idx, 节点采样矩阵 N idx ∈ {0,1} 初始化为全零矩阵, 对于采样分区内的
节点, 其对应位置的元素设为 1; 对于未采样分区内的节点, 保持为 0.
值得注意的是, 只有当两个分区均被用于生成子图时, 它们之间的连通性才得以保留; 否则, 这些连接将被忽
略. 因此, 根据邻接矩阵 A sub 和节点特征矩阵 X sub , 可以构建完整的子图:


 A agg = A+λT





 A sub = A agg ⊙ E idx (6)





X sub = X ⊙ N idx
其中, T 是 A 的聚合矩阵 (详见公式 (1)), λ 是超参数, ⊙ 表示逐元素相乘.
通过这种方法生成的子图不仅具有强大的内部连通性, 还能有效地从相邻节点中聚合信息. 在子图样本中聚
合更大邻域的信息, 使得本文能够捕获更复杂的图属性, 同时保留局部结构, 以便学习子图之间的判别关系. 在
提出的基于分区的子图采样机制中, 本文对其 4 个阶段的时间复杂度进行了评估. 具体来说, 粗化阶段的时间复杂
O |V|log|V| , 这主要由节点合并的层次聚类过程决定; 分区阶段使用贪心图增长算法, 其时间复杂度为
(
)
度为
O(|V|×|E|), 这取决于图中节点和边的数量; 细化阶段使用边界 Kernighan-Lin 算法进行微调, 其时间复杂度为
( ) ( )
2 2
O |V| ; 采样阶段的时间复杂度为 O C , 其中 C 为分区数量, 且 C ≪ |V|, 因此该阶段的时间开销相对较小.
值得注意的是, 虽然贪心图增长算法和边界 Kernighan-Lin 算法在采样机制中有所应用, 但它们并不参与后续
的训练和测试过程的反向传播. 在训练和测试时, 只需将分区结果加载到 GPU 内存中, 用于采样阶段以及随后的
前向传播和反向传播过程. 这避免了在每次迭代中都重复执行这些耗时的分区和细化算法, 从而显著降低了总体
时间开销. 同时, 为了确保比较的公平性, SRM 采用了较浅的网络结构, 减轻了额外的计算负担.
2.2 局部和全局分支融合
为了全面建模局部与全局信息, 本文设计了局部和全局分支来分别处理子图批次和图的建模. 为了保持结构
的完整性, 并使解码器能够把握局部与全局特征间的关联, 本文引入横向连接 [31] 整合这两个分支的信息:

 ( inp inp )
 F = w f ·Cat X ,X

 sub who


 out inp
 X = X + F (7)
 sub sub


 out inp
 X = X +mean(F batch )
who who
inp
其中, X 、 X inp 、 X out 和 X out 分别表示生成的子图和整个图的输入和输出节点特征. F 是融合特征, mean(F batch )
sub who sub who
是训练批次中融合特征的平均值. w f 是可学习的参数, Cat(·,·) 表示向量拼接操作, 用于将不同来源的特征合并成
一个统一的特征向量. 基于此, 模型能够同时考虑局部和全局信息, 从而提高了结构保持的能力.
2.3 节点正则化
在提升图表示质量的同时, 引入节点扰动会不可避免地改变输入图中原有节点的局部依赖关系, 进而在重构
过程中引入显著的结构波动性. 为应对此挑战, 本文提出了一种节点正则化方法. 该方法通过引入由节点平滑性、
连通性和稀疏性导出的新监督信号, 旨在提取有意义的结构信息并增强模型的稳定性.
平滑性技术在众多应用中发挥着关键作用, 尤其是在恢复原始信号 [3] 方面. 然而, 大多数现有方法都建立在相