论文解读（SUBLIME）《Towards Unsupervised Deep Graph Structure Learning》

技术分享 3年前 (2022-06-05) 0 999+

论文信息

论文标题：Towards Unsupervised Deep Graph Structure Learning
论文作者：Yixin Liu, Yu Zheng, Daokun Zhang, Hongxu Chen, Hao Peng, Shirui Pan
论文来源：2022, WWW Best Paper Award candidate
论文地址：download
论文代码：download

1 Introduction

　　Deep GSL（深度图结构学习）：在节点分类任务的监督下和GNN共同优化图结构。弊端是对标签的依赖、边分布的偏差、应用程序任务的限制等。

　　本文和监督 GSL 对比：

2 Problem Definition

　　符号定义：

　　Definition 3.1 (Structure inference). Given a feature matrix $mathbf{X} in mathbb{R}^{n times d}$ , the target of structure inference is to automatically learn a graph topology $mathrm{S} in[0,1]^{n times n}$ , which reflects the underlying correlations among data samples. In particular, $mathrm{S}_{i j} in[0,1]$ indicates whether there is an edge between two samples (nodes) $mathbf{x}_{i}$ and $mathbf{x}_{j}$ .

　　Definition 3.2 (Structure refinement). Given a graph $mathcal{G}=(mathbf{A}, mathbf{X})$ with a noisy graph structure $mathbf{A}$ , the target of structure refinement is to refine $mathrm{A}$ to be the optimized adjacency matrix $mathrm{S} in[0,1]^{n times n}$ to better capture the underlying dependency between nodes.

3 Method

　　整体框架：

　　包括两个模块：

- graph structure learning module
- structure bootstrapping contrastive learning module

3.1 Graph Learner

　　Graph Learner 生成一个带参数的图邻接矩阵 $tilde{mathrm{S}} in mathbb{R}^{n times n}$。本文的 Graph Learner 包括如下四种：

- FGP learner　　
- Attentive Learner　　
- MLP Learner　　
- GNN Learner

3.1.1 FGP learner

　　通过一个参数矩阵直接建模邻接矩阵的每个元素，没有任何额外的输入。FGP Learner：

　　　　$tilde{mathrm{S}}=p_{omega}^{F G P}=sigma(Omega)quadquadquad(1)$

　　其中，$omega=Omega in mathbb{R}^{n times n}$ 是一个参数矩阵，$sigma(cdot)$ 是一个非线性函数，使训练更稳定。FGP学习器背后的假设是，每条边都独立地存在于图中。

论文解读（SUBLIME）《Towards Unsupervised Deep Graph Structure Learning》

class FGP_learner(nn.Module):     def __init__(self, features, k, knn_metric, i, sparse):         super(FGP_learner, self).__init__()          self.k = k         self.knn_metric = knn_metric         self.i = i         self.sparse = sparse          self.Adj = nn.Parameter(             torch.from_numpy(nearest_neighbors_pre_elu(features, self.k, self.knn_metric, self.i)))      def forward(self, h):         if not self.sparse:             Adj = F.elu(self.Adj) + 1         else:             Adj = self.Adj.coalesce()             Adj.values = F.elu(Adj.values()) + 1         return Adj  def nearest_neighbors_pre_elu(X, k, metric, i):     adj = kneighbors_graph(X, k, metric=metric)     adj = np.array(adj.todense(), dtype=np.float32)     adj += np.eye(adj.shape[0])     adj = adj * i - i     return adj

FGP learner Code

　　与 FGP Learner 不同，基于度量学习的Learner [7,58] 首先从输入数据中获取节点嵌入 $mathbf{E} in mathbb{R}^{n times d}$，然后利用节点嵌入的两两相似性对 $tilde{mathrm{S}}$ 进行建模：

　　　　$tilde{mathrm{S}}=p_{omega}^{M L}(mathbf{X}, mathbf{A})=phileft(h_{omega}(mathbf{X}, mathrm{A})right)=phi(mathbf{E})quadquadquad(2)$

　　其中，$h_{omega}(cdot)$ 是一个基于神经网络的带参数 $omega$ 的嵌入函数，而且 $phi(cdot)$ 是一个非参数度量函数（如余弦相似度或闵可夫斯基距离），它计算成对相似度。

　　对于不同的 $h_{omega}(cdot)$，本文是 Attentive Learner、MLP Learner、GNN Learner 。

3.1.2 Attentive Learner

　　采用一个注意网络作为其嵌入网络：

　　　　$mathbf{E}^{(l)}=h_{w}^{(l)}left(mathbf{E}^{(l-1)}right)=sigmaleft(left[mathbf{e}_{1}^{(l-1)} odot omega^{(l)}, cdots, mathbf{e}_{n}^{(l-1)} odot omega^{(l)}right]^{top}right)quadquadquad(3)$

　　其中：

- $mathbf{E}^{(l)}$ 是第 $l$ 层嵌入矩阵，$mathbf{e}_{i}^{(l-1)} in mathbb{R}^{d}$ 是 $mathbf{E}^{(l-1)}$ 第 $i$ 行向量；　　
- $omega^{(l)} in mathbb{R}^{d}$ 是第 $l$ 层的参数向量；

class ATT_learner(nn.Module):     def __init__(self, nlayers, isize, k, knn_metric, i, sparse, mlp_act):         super(ATT_learner, self).__init__()          self.i = i         self.layers = nn.ModuleList()         for _ in range(nlayers):             self.layers.append(Attentive(isize))         self.k = k         self.knn_metric = knn_metric         self.non_linearity = 'relu'         self.sparse = sparse         self.mlp_act = mlp_act      def internal_forward(self, h):         for i, layer in enumerate(self.layers):             h = layer(h)             if i != (len(self.layers) - 1):                 if self.mlp_act == "relu":                     h = F.relu(h)                 elif self.mlp_act == "tanh":                     h = F.tanh(h)         return h      def forward(self, features):         if self.sparse:             embeddings = self.internal_forward(features)             rows, cols, values = knn_fast(embeddings, self.k, 1000)             rows_ = torch.cat((rows, cols))             cols_ = torch.cat((cols, rows))             values_ = torch.cat((values, values))             values_ = apply_non_linearity(values_, self.non_linearity, self.i)             adj = dgl.graph((rows_, cols_), num_nodes=features.shape[0], device='cuda')             adj.edata['w'] = values_             return adj         else:             embeddings = self.internal_forward(features)             embeddings = F.normalize(embeddings, dim=1, p=2)             similarities = cal_similarity_graph(embeddings)             similarities = top_k(similarities, self.k + 1)             similarities = apply_non_linearity(similarities, self.non_linearity, self.i)             return similarities   class Attentive(nn.Module):     def __init__(self, isize):         super(Attentive, self).__init__()         self.w = nn.Parameter(torch.ones(isize))      def forward(self, x):         return x @ torch.diag(self.w)

ATT_learner Code

3.1.3 MLP Learner

　　使用多层感知(MLP)作为其嵌入网络：

　　　　$mathbf{E}^{(l)}=h_{w}^{(l)}left(mathbf{E}^{(l-1)}right)=sigmaleft(mathbf{E}^{(l-1)} Omega^{(l)}right)quadquadquad(4)$

　　其中，$Omega^{(l)} in mathbb{R}^{d times d}$ 是第 $l$ 层的参数矩阵。

　　与 Attentive Learner 相比，MLP Learner 进一步考虑了特征的相关性和组合，为下游相似性度量学习生成了更多的信息嵌入。

class MLP_learner(nn.Module):     def __init__(self, nlayers, isize, k, knn_metric, i, sparse, act):         super(MLP_learner, self).__init__()          self.layers = nn.ModuleList()         if nlayers == 1:             self.layers.append(nn.Linear(isize, isize))         else:             self.layers.append(nn.Linear(isize, isize))             for _ in range(nlayers - 2):                 self.layers.append(nn.Linear(isize, isize))             self.layers.append(nn.Linear(isize, isize))          self.input_dim = isize         self.output_dim = isize         self.k = k         self.knn_metric = knn_metric         self.non_linearity = 'relu'         self.param_init()         self.i = i         self.sparse = sparse         self.act = act      def internal_forward(self, h):         for i, layer in enumerate(self.layers):             h = layer(h)             if i != (len(self.layers) - 1):                 if self.act == "relu":                     h = F.relu(h)                 elif self.act == "tanh":                     h = F.tanh(h)         return h      def param_init(self):         for layer in self.layers:             layer.weight = nn.Parameter(torch.eye(self.input_dim))      def forward(self, features):         if self.sparse:             embeddings = self.internal_forward(features)             rows, cols, values = knn_fast(embeddings, self.k, 1000)             rows_ = torch.cat((rows, cols))             cols_ = torch.cat((cols, rows))             values_ = torch.cat((values, values))             values_ = apply_non_linearity(values_, self.non_linearity, self.i)             adj = dgl.graph((rows_, cols_), num_nodes=features.shape[0], device='cuda')             adj.edata['w'] = values_             return adj         else:             embeddings = self.internal_forward(features)             embeddings = F.normalize(embeddings, dim=1, p=2)             similarities = cal_similarity_graph(embeddings)             similarities = top_k(similarities, self.k + 1)             similarities = apply_non_linearity(similarities, self.non_linearity, self.i)             return similarities

MLP Learner Code

3.1.4 GNN Learner

　　依赖于原始拓扑结构，GNN学习器仅用于结构细化任务(structure refinement task)。

　　本文采用 GCN 形成嵌入式网络：

　　　　$mathbf{E}^{(l)}=h_{w}^{(l)}left(mathbf{E}^{(l-1)}, mathbf{A}right)=sigmaleft(widetilde{mathbf{D}}^{-frac{1}{2}} widetilde{mathbf{A}} widetilde{mathbf{D}}^{-frac{1}{2}} mathbf{E}^{(l-1)} Omega^{(l)}right)quadquadquad(5)$

　　其中，$widetilde{mathbf{A}}=mathbf{A}+mathbf{I}$ 为具有自环的邻接矩阵，$widetilde{mathbf{D}}$ 为 $tilde{mathbf{A}}$ 的度矩阵。

　　GNN学习器假设两个节点之间的连接不仅与特征有关，而且还与原始结构有关。

class GNN_learner(nn.Module):     def __init__(self, nlayers, isize, k, knn_metric, i, sparse, mlp_act, adj):         super(GNN_learner, self).__init__()          self.adj = adj         self.layers = nn.ModuleList()         if nlayers == 1:             self.layers.append(GCNConv_dgl(isize, isize))         else:             self.layers.append(GCNConv_dgl(isize, isize))             for _ in range(nlayers - 2):                 self.layers.append(GCNConv_dgl(isize, isize))             self.layers.append(GCNConv_dgl(isize, isize))          self.input_dim = isize         self.output_dim = isize         self.k = k         self.knn_metric = knn_metric         self.non_linearity = 'relu'         self.param_init()         self.i = i         self.sparse = sparse         self.mlp_act = mlp_act      def internal_forward(self, h):         for i, layer in enumerate(self.layers):             h = layer(h, self.adj)             if i != (len(self.layers) - 1):                 if self.mlp_act == "relu":                     h = F.relu(h)                 elif self.mlp_act == "tanh":                     h = F.tanh(h)         return h      def param_init(self):         for layer in self.layers:             layer.weight = nn.Parameter(torch.eye(self.input_dim))      def forward(self, features):         if self.sparse:             embeddings = self.internal_forward(features)             rows, cols, values = knn_fast(embeddings, self.k, 1000)             rows_ = torch.cat((rows, cols))             cols_ = torch.cat((cols, rows))             values_ = torch.cat((values, values))             values_ = apply_non_linearity(values_, self.non_linearity, self.i)             adj = dgl.graph((rows_, cols_), num_nodes=features.shape[0], device='cuda')             adj.edata['w'] = values_             return adj         else:             embeddings = self.internal_forward(features)             embeddings = F.normalize(embeddings, dim=1, p=2)             similarities = cal_similarity_graph(embeddings)             similarities = top_k(similarities, self.k + 1)             similarities = apply_non_linearity(similarities, self.non_linearity, self.i)             return similarities

GNN Learner Code

3.2 Post-processor

　　Poster-processor $q(cdot)$的目标是将邻接矩阵 $tilde{S}$ 细化为稀疏、非负、对称和归一化邻接矩阵。

　　因此，依次采如下步骤：

- 稀疏化 $q_{s p}(cdot)$
- 激活 $q_{a c t}(cdot) $
- 对称 $q_{s y m}(cdot)$
- 归一化 $q_{text {norm }}(cdot)$

3.2.1 Sparsification

　　根据相似性创建的邻接矩阵 $tilde{mathrm{S}}$ 通常是密集的，表示一个完全连通的图结构，但实际上并没有什么意义，所以采用基于 K近邻的稀疏化。

　　具体地说，对于每个节点，保留具有 $text{top-k}$ 个连接值的边，并将其余的设置为 $0$。稀疏化的 $q_{s p}(cdot)$ 表示为：

　　　　$tilde{mathbf{S}}_{i j}^{(s p)}=q_{s p}left(tilde{mathrm{S}}_{i j}right)=left{begin{array}{ll}tilde{mathrm{S}}_{i j}, & tilde{mathrm{S}}_{i j} in operatorname{top}-mathrm{k}left(tilde{mathrm{S}}_{i}right) \0, & tilde{mathrm{S}}_{i j} notin operatorname{top}-mathrm{k}left(tilde{mathrm{S}}_{i}right)end{array}right.quadquadquad(6)$

　　其中， $top-mathrm{k}left(tilde{mathrm{S}}_{i}right)$ 是行向量 $tilde{mathrm{S}}_{i}$ 的最大 $k$ 个值的集合。注意，本文并不对 FGP learner 进行稀疏化。

　　对于大规模图，使用局部敏感近似[11] 来执行 kNN 稀疏化，其中最近邻是从一批节点而不是所有节点中选择的，这减少了对内存的需求。

def cal_similarity_graph(node_embeddings):     similarity_graph = torch.mm(node_embeddings, node_embeddings.t())     return similarity_graph

cal_similarity_graph Code

def top_k(raw_graph, K):     values, indices = raw_graph.topk(k=int(K), dim=-1)     assert torch.max(indices) < raw_graph.shape[1]     mask = torch.zeros(raw_graph.shape).cuda()     mask[torch.arange(raw_graph.shape[0]).view(-1, 1), indices] = 1.      mask.requires_grad = False     sparse_graph = raw_graph * mask     return sparse_graph

top_k Code

3.2.2 Symmetrization and Activation

　　对称化和激活的执行方式为：

　　　　$tilde{mathbf{S}}^{(s y m)}=q_{s y m}left(q_{a c t}left(tilde{mathbf{S}}^{(s p)}right)right)=frac{sigma_{q}left(tilde{mathbf{S}}^{(s p)}right)+sigma_{q}left(tilde{mathrm{S}}^{(s p)}right)^{top}}{2}quadquadquad(7)$

　　其中，$sigma_{q}(cdot)$ 是一个非线性激活。对于基于度量学习的学习器，我们将 $sigma_{q}(cdot)$ 定义为 ReLU 函数。对于 FGP learner，应用 ELU 函数来防止梯度消失。

def symmetrize(adj):  # only for non-sparse     return (adj + adj.T) / 2

Symmetrization and Activation Code

3.2.3 Normalization

　　为了保证边权值在 $[0,1]$ 范围内，我们最后对 $tilde{mathrm{S}}$ 进行了归一化。特别地，我们应用了一个对称的归一化：

　　　　$mathrm{S}=q_{text {norm }}left(tilde{mathrm{S}}^{(s y m)}right)=left(tilde{mathbf{D}}^{(s y m)}right)^{-frac{1}{2}} tilde{mathbf{S}}^{(s y m)}left(tilde{mathbf{D}}^{(s y m)}right)^{-frac{1}{2}}quadquadquad(8)$

　　其中，$tilde{mathbf{D}}^{(s y m)}$ 为 $tilde{mathbf{S}}^{(s y m)}$ 的度矩阵。

def normalize(adj, mode, sparse=False):     if not sparse:         if mode == "sym":             inv_sqrt_degree = 1. / (torch.sqrt(adj.sum(dim=1, keepdim=False)) + EOS)             return inv_sqrt_degree[:, None] * adj * inv_sqrt_degree[None, :]         elif mode == "row":             inv_degree = 1. / (adj.sum(dim=1, keepdim=False) + EOS)             return inv_degree[:, None] * adj         else:             exit("wrong norm mode")     else:         adj = adj.coalesce()         if mode == "sym":             inv_sqrt_degree = 1. / (torch.sqrt(torch.sparse.sum(adj, dim=1).values()))             D_value = inv_sqrt_degree[adj.indices()[0]] * inv_sqrt_degree[adj.indices()[1]]          elif mode == "row":             aa = torch.sparse.sum(adj, dim=1)             bb = aa.values()             inv_degree = 1. / (torch.sparse.sum(adj, dim=1).values() + EOS)             D_value = inv_degree[adj.indices()[0]]         else:             exit("wrong norm mode")         new_values = adj.values() * D_value          return torch.sparse.FloatTensor(adj.indices(), new_values, adj.size())

Normalization Code

3.3 Multi-view Graph Contrastive Learning

　　本文使用多视图对比学习来提供有效的监督信号来指导图结构学习。

3.3.1 Graph View Establishment

　　SUBLIME 将学习到的图（learner view）定义为一个视图，并用输入数据构造另一个视图（anchor view）。

Learner view

　　Learner view 采用 $S$ 作为邻接矩阵，$X$ 作为特征矩阵，即 $mathcal{G}_{l}=(mathrm{S}, mathrm{X})$。在每次训练迭代中，$mathrm{S}$ 和用于建模的参数通过梯度下降直接更新，以发现最优的图结构。

　　在 SUBLIME 中，将 learner views 初始化为建立在特征基础上的 kNN 图 [11,12]。具体来说，

对于 FGP learner，将 kNN 边对应的参数初始化为 $1$，其余的初始化为$0$；
对于 attentive learner，让 $omega^{(l)} in omega$ 中的每个元素都为 $1$。然后，根据度量函数计算特征级相似度，并通过 sparsification post-processing 得到 kNN 图；
对于 MLP learner 和GNN learner，将嵌入维数设置为 $d$，并将 $Omega^{(l)} in omega$ 初始化为单位矩阵；

learned_adj = graph_learner(features)

Learner view Code

Anchor view

　　Anchor view 扮演着 "teacher” 的角色，为GSL提供了正确和稳定的指导。

　　对于 structure refinement task ，采用原始图邻接矩阵 $A$，即 $mathcal{G}_{a}=left(mathbf{A}_{a}, mathbf{X}right)=(mathbf{A}, mathrm{X})$。

　　对于 structure inference task，采用单位矩阵 $I$ 作为图结构，即 $mathcal{G}_{a}=left(mathrm{A}_{a}, mathrm{X}right)=(mathrm{I}, mathrm{X})$。

if args.gsl_mode == 'structure_inference':     if args.sparse:         anchor_adj_raw = torch_sparse_eye(features.shape[0])     else:         anchor_adj_raw = torch.eye(features.shape[0]) elif args.gsl_mode == 'structure_refinement':     if args.sparse:         anchor_adj_raw = adj_original     else:         anchor_adj_raw = torch.from_numpy(adj_original)

Anchor view Code

3.3.2 Data Augmentation

　　数据增强：Feature mask 和 Edge drop。

Feature masking

　　为干扰节点特征，随机选择一部分特征维度，并用 $0$ 掩蔽它们。

　　形式上，对于给定的特征矩阵 $mathbf{X}$，首先采样一个掩蔽向量 $mathbf{m}^{(x)} in{0,1}^{d}$，其中每个元素都来自一个独立的概率为伯努利分布 $p^{(x)}$。然后，用 $mathbf{m}^{(x)}$ 掩码每个节点的特征向量：

　　　　$overline{mathbf{X}}=mathcal{T}_{f m}(mathbf{X})=left[mathbf{x}_{1} odot mathbf{m}^{(x)}, cdots, mathbf{x}_{n} odot mathbf{m}^{(x)}right]^{top}quadquadquad(9)$

　　其中，$bar{X}$ 为增广特征矩阵，$mathcal{T}_{f m}(cdot)$ 为特征掩蔽变换，$x_{i}$ 为 $X$ 的第 $i$ 行向量的转置。

Edge dropping

　　随机删除部分边来破坏图的结构。具体地说，对于给定的邻接矩阵 $A$，首先采样掩蔽矩阵 $mathbf{M}^{(a)} in{0,1}^{n times n}$，其中每个元素 $mathbf{M}_{i j}^{(a)}$ 是从概率为 $p^{(a)}$ 的伯努利分布中抽取的。邻接矩阵被 $mathbf{M}^{(a)}$ 屏蔽后：

　　　　$overline{mathbf{A}}=mathcal{T}_{e d}(mathbf{A})=mathbf{A} odot mathbf{M}^{(a)}quadquadquad(10)$

　　其中 $overline{mathbf{A}}$ 为增广邻接矩阵，$mathcal{T}_{e d}(cdot)$ 为边丢弃变换。

　　在 SUBLIME 中，利用这两种增强方案在 learner view 和 anchor view 上生成增强图：

　　　　$overline{mathcal{G}}_{l}=left(mathcal{T}_{e d}(mathrm{~S}), mathcal{T}_{f m}(mathbf{X})right), overline{mathcal{G}}_{a}=left(mathcal{T}_{text {ed }}left(mathbf{A}_{a}right), mathcal{T}_{f m}(mathbf{X})right)quadquadquad(11)$

　　其中，$overline{mathcal{G}}_{l}$ 和 $overline{mathcal{G}}_{a}$ 分别为增强的 learner view 和 anchor view。

　　为了在两个视图中获得不同的上下文，两个视图的 Feature masking 采用了不同的概率 $p_{l}^{(x)} neq p_{a}^{(x)}$。对于 Edge dropping，由于两个视图的邻接矩阵已经有了显著的不同，因此使用相同的丢弃概率 $p_{l}^{(a)}=p_{a}^{(a)}=p^{(a)}$。

3.3.3 Node-level Contrastive Learning

　　在获得两个增广图视图后，执行节点级对比学习，以最大化它们之间的 MI。在 SUBLIME 采用了一个来自 SimCLR[6] 的简单的对比学习框架，由以下组成部分组成：

GNN-based encoder

　　一个基于 GNN 的编码器 $f_{theta}(cdot)$ 提取增广图 $overline{mathcal{G}}_{l}$ 和 $overline{mathcal{G}}_{a}$ 的节点层表示：

　　　　$mathbf{H}_{l}=f_{theta}left(overline{mathcal{G}}_{l}right), mathbf{H}_{a}=f_{theta}left(overline{mathcal{G}}_{a}right)quadquadquad(12)$

　　其中，$theta$ 为编码器 $f_{theta}(cdot)$ 的参数，$mathrm{H}_{l}, mathrm{H}_{a} in mathbb{R}^{n times d_{1}}$（ $d_{1}$ 为表示维数）分别为 learner/anchor views 的节点表示矩阵。在 SUBLIME 中，使用 GCN 作为我们的编码器，并将其层数 $L_{1}$ 设置为 $2$。

MLP-based projector

　　在编码器之后，一个带有 $L_{2}$ 层的 MLP 投影头 $g_{varphi}(cdot)$ 将表示映射到另一个潜在空间，在其中计算对比损失：

　　　　$mathbf{Z}_{l}=g_{varphi}left(mathbf{H}_{l}right), mathbf{Z}_{a}=g_{varphi}left(mathbf{H}_{a}right)quadquadquad(13)$

　　其中，$varphi$ 为投影头 $g_{varphi}(cdot)$ 的参数，$mathbf{Z}_{l}, mathbf{Z}_{a} in mathbb{R}^{n times d_{2}}(d_{2}$（ $d_{2}$ 为投影维数）分别为 learner/anchor views 的投影后的嵌入矩阵。

Node-level contrastive loss function

　　一个对比损失 $mathcal{L}$ 被利用来强制最大化在两个视图上同一节点 $v_{i}$ 上的投影 $z_{l, i}$ 和 $z_{a, i}$ 之间的一致性。在我们的框架中，应用了对称归一化温度尺度交叉熵损失(NT-Xent)[29,35]：

　　　　${large begin{array}{l}mathcal{L}=frac{1}{2 n} sum_{i=1}^{n}left[ellleft(z_{l, i}, z_{a, i}right)+ellleft(z_{a, i}, z_{l, i}right)right] \ellleft(z_{l, i}, z_{a, i}right)=log frac{e^{operatorname{sim}left(mathrm{z}_{l, i}, mathrm{z}_{a, i}right) / t}}{sum_{k=1}^{n} e^{operatorname{sim}left(mathrm{z}_{l, i}, mathrm{z}_{a, k}right) / t}}end{array}} quadquadquad(14)$

3.4 Structure Bootstrapping Mechanism

　　使用由 $mathbf{A}$ 或 $I$ 定义的固定的 Anchor 邻接矩阵 $mathbf{A}_{a}$，SUBLIME 可以通过最大化两个视图之间的MI来学习图结构 $S$。

　　然而，使用固定的$mathbf{A}_{a}$ 可能会导致几个问题：

- Inheritance of error information。由于 $mathbf{A}_{a}$ 是直接从输入数据中得到的，所以它会携带原始图的一些自然噪声（例如，缺失或冗余的边）。如果在学习过程中不消除噪声，学习到的结构最终将继承它；
- Lack of persistent guidance。一个固定的锚点图包含有限的信息来指导GSL。一旦图形学习者捕获了这些信息，模型将很难在以下的训练步骤中获得有效的监督;
- Overfitting the anchor structure。在使两个视图之间的一致性最大化的学习目标的驱动下，学习到的结构倾向于过度拟合固定的锚定结构，从而导致与原始数据相似的测试性能；

　　受基于 bootstrap 的算法 [5,14,37] 的启发，本文设计了一个 structure bootstrapping mechanism，提供一个 bootstrap 的 Anchor 视图作为学习目标。本文解决方案的核心思想是通过学习到的 $S$ 缓慢更新锚定结构 $mathbf{A}_{a}$，而不是保持 $mathbf{A}_{a}$ 不变。即，给定衰减速率 $tau in[0,1]$，锚定结构 $mathbf{A}_{a}$ 每 $c$ 次迭代更新如下：

　　　　$mathbf{A}_{a} leftarrow tau mathbf{A}_{a}+(1-tau) mathrm{S} quadquadquad(15)$

　　随着更新过程的进行，$mathbf{A}_{a}$ 中一些噪声边的权值逐渐减小，减轻了它们对结构学习的负面影响。同时，由于学习目标 $mathbf{A}_{a}$ 在训练阶段发生了变化，它总是可以包含更有效的信息来指导拓扑的学习，过拟合问题自然得到了解决。更重要的是，Structure Bootstrapping Mechanism 利用学习到的知识来提高学习目标，从而推动模型不断发现越来越最优的图结构。此外，slow-moving average（$tau ge 0.99$）的更新确保了训练的稳定性。