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

秦者云 等: 基于结构关系建模的自监督图表示学习 705

算法 2. 子图采样阶段伪代码.
[ ]
¯ ¯
¯
¯ 和边集 ; 分区数量 ; 跳数限制 ; 分
¯
¯
输入: 输入图分区集合: {V 1 ,E 1 },...,{V C ,E C } , 其中每个分区包含节点集 V i E i K H
¯ A;
区相似度矩阵 P; 分区邻接矩阵
输出: 子图邻接矩阵 A sub ; 子图节点特征矩阵 X sub .
S ← ∅
1. 初始化已选分区集合
2. 随机选择分区 s 作为起始分区, 并将其加入 S
3. 初始化索引队列 idx ← ∅, 并将 (s,0) 压入 idx
4. 当 idx 非空且 |S | < K 时, 执行以下步骤:
5. 从 idx 中弹出一个元素 (u,hop)
6. 遍历基于 ¯ A 与 u 相邻的每个分区 p
7. 如果 p 不在 S 中且 hop < H:
[ ]
8. 根据相似度 P u, p 选择 p:
9. 将 p 加入 S
|S | ⩾ K:
10. 如果
11. 跳出循环
hop < H:
12. 如果
13. 将 (p,hop+1) 压入 idx
14. 初始化 E idx 和 N idx 为零矩阵
15. 遍历 idx 中所有元素对 (s,t)
( ) ( )
t
16. 遍历分区 s 和 中的所有节点对 v si ,v t j , 将 E idx v si ,v t j 设为 1
17. 遍历 idx 中的每个分区 c 及其节点 v ci , 将 N idx (v ci ) 设为 1
18. 计算聚合矩阵 A agg ← A+λT
19. 计算子图邻接矩阵 A sub ← A agg ⊙ E idx
20. 计算子图节点特征矩阵 X sub ← X ⊙ N idx
21. 返回 A sub 和 X sub
2.1.2 分区阶段和细化阶段
在分区阶段, 本文利用分区边界将最粗的图 G L 划分为若干个相互平衡的独占群组, 确保每个群组包含原始图
G 0 中大约 1/C 的节点. 而在细化阶段, 则通过贪婪图生长算法以及边界 Kernighan-Lin [31] , 将粗图 G L 的分区结果有
效地投影回原始图 G 0 的层次结构中.
2.1.3 采样阶段
在完成了分区和细化步骤后, 图 G 被成功地分割为 C 个分区, 其表示形式如下:

[ ] [{ } { }]
¯
G = ¯ G 1 ,..., ¯ G C = V 1 , ¯ E 1 ,..., ¯ V C , ¯ E C (3)

¯ V c 的节点 G 中的任
c
其中, 每个分区 ¯ G c 仅包含属于分区 (即 ¯ V c = N/C) 和第 个分区中的边 E c . 值得注意的是, 图
何节点均归属于且仅归属于一个分区.
此外, 为了更好地表示图 G C 个子矩阵的集合, 具体形式如下:
2
的结构特性, 其邻接矩阵被重新构造为
 ¯ ... 
 A 11 ¯ A 1C 
 
 
 . . 
 . 
 . . . 
¯ A =  .  (4)
 . . 
 
 
 
...
¯ A C1 ¯ A CC
¯
¯
其中, 每个对角子矩阵 ¯ A CC ∈ R | V c| ×| V c| 反映了分区 ¯ G c 内部的边连接情况, 而 ¯ A sc 则描述了分区 ¯ G s 与分区 ¯ G c 之间的