| 学习路线指引（点击解锁） | 知识定位 | 人群定位 |
|---|---|---|
| 李 Python实战微信订餐小程序 李 | 进阶级 | 本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。 |
| Python量化交易实战 | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
1 Introduction论文标题：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
Deep GSL（深度图结构学习）：在节点分类任务的监督下和GNN共同优化图结构。弊端是对标签的依赖、边分布的偏差、应用程序任务的限制等。
本文和监督 GSL 对比：
2 Problem Definition符号定义：
Definition 3.1 (Structure inference). Given a feature matrix X∈Rn×dX∈Rn×dmathbf{X} in mathbb{R}^{n times d} , the target of structure inference is to automatically learn a graph topology S∈[0,1]n×nS∈[0,1]n×nmathrm{S} in[0,1]^{n times n} , which reflects the underlying correlations among data samples. In particular, Sij∈[0,1]Sij∈[0,1]mathrm{S}_{i j} in[0,1] indicates whether there is an edge between two samples (nodes) xiximathbf{x}_{i} and xjxjmathbf{x}_{j} .
Definition 3.2 (Structure refinement). Given a graph G=(A,X)G=(A,X)mathcal{G}=(mathbf{A}, mathbf{X}) with a noisy graph structure AAmathbf{A} , the target of structure refinement is to refine AAmathrm{A} to be the optimized adjacency matrix S∈[0,1]n×nS∈[0,1]n×nmathrm{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
- graph structure learning module
Graph Learner 生成一个带参数的图邻接矩阵 S∈Rn×nS∈Rn×ntilde{mathrm{S}} in mathbb{R}^{n times n}。本文的 Graph Learner 包括如下四种：
-
- FGP learner
- Attentive Learner
- MLP Learner
- GNN Learner
- FGP learner
通过一个参数矩阵直接建模邻接矩阵的每个元素，没有任何额外的输入。FGP Learner：
S=pFGPω=σ(Ω)(1)S=pωFGP=σ(Ω)(1)tilde{mathrm{S}}=p_{omega}^{F G P}=sigma(Omega)quadquadquad(1)
其中，ω=Ω∈Rn×nω=Ω∈Rn×nomega=Omega in mathbb{R}^{n times n} 是一个参数矩阵，σ(⋅)σ(⋅)sigma(cdot) 是一个非线性函数，使训练更稳定。FGP学习器背后的假设是，每条边都独立地存在于图中。
ruby
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] 首先从输入数据中获取节点嵌入 E∈Rn×dE∈Rn×dmathbf{E} in mathbb{R}^{n times d}，然后利用节点嵌入的两两相似性对 SStilde{mathrm{S}} 进行建模：
S=pMLω(X,A)=ϕ(hω(X,A))=ϕ(E)(2)S=pωML(X,A)=ϕ(hω(X,A))=ϕ(E)(2)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ω(⋅)hω(⋅)h_{omega}(cdot) 是一个基于神经网络的带参数 ωωomega 的嵌入函数，而且 ϕ(⋅)ϕ(⋅)phi(cdot) 是一个非参数度量函数（如余弦相似度或闵可夫斯基距离），它计算成对相似度。
对于不同的 hω(⋅)hω(⋅)h_{omega}(cdot)，本文是 Attentive Learner、MLP Learner、GNN Learner 。
3.1.2 Attentive Learner采用一个注意网络作为其嵌入网络：
E(l)=h(l)w(E(l−1))=σ([e(l−1)1⊙ω(l),⋯,e(l−1)n⊙ω(l)]⊤)(3)E(l)=hw(l)(E(l−1))=σ([e1(l−1)⊙ω(l),⋯,en(l−1)⊙ω(l)]⊤)(3)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)
其中：
-
- E(l)E(l)mathbf{E}^{(l)} 是第 lll 层嵌入矩阵，e(l−1)i∈Rdei(l−1)∈Rdmathbf{e}_{i}^{(l-1)} in mathbb{R}^{d} 是 E(l−1)E(l−1)mathbf{E}^{(l-1)} 第 iii 行向量；
- ω(l)∈Rdω(l)∈Rdomega^{(l)} in mathbb{R}^{d} 是第 lll 层的参数向量；
- E(l)E(l)mathbf{E}^{(l)} 是第 lll 层嵌入矩阵，e(l−1)i∈Rdei(l−1)∈Rdmathbf{e}_{i}^{(l-1)} in mathbb{R}^{d} 是 E(l−1)E(l−1)mathbf{E}^{(l-1)} 第 iii 行向量；
reasonml
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)作为其嵌入网络：
E(l)=h(l)w(E(l−1))=σ(E(l−1)Ω(l))(4)E(l)=hw(l)(E(l−1))=σ(E(l−1)Ω(l))(4)mathbf{E}{(l)}=h_{w}{(l)}left(mathbf{E}{(l-1)}right)=sigmaleft(mathbf{E}{(l-1)} Omega^{(l)}right)quadquadquad(4)
其中，Ω(l)∈Rd×dΩ(l)∈Rd×dOmega^{(l)} in mathbb{R}^{d times d} 是第 lll 层的参数矩阵。
与 Attentive Learner 相比，MLP Learner 进一步考虑了特征的相关性和组合，为下游相似性度量学习生成了更多的信息嵌入。
reasonml
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 形成嵌入式网络：
E(l)=h(l)w(E(l−1),A)=σ(D˜−12A˜D˜−12E(l−1)Ω(l))(5)E(l)=hw(l)(E(l−1),A)=σ(D−12AD~−12E(l−1)Ω(l))(5)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)
其中，A˜=A+IA~=A+Iwidetilde{mathbf{A}}=mathbf{A}+mathbf{I} 为具有自环的邻接矩阵，D˜D~widetilde{mathbf{D}} 为 AAtilde{mathbf{A}} 的度矩阵。
GNN学习器假设两个节点之间的连接不仅与特征有关，而且还与原始结构有关。
reasonml
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-processorPoster-processor q(⋅)q(⋅)q(cdot)的目标是将邻接矩阵 SStilde{S} 细化为稀疏、非负、对称和归一化邻接矩阵。
因此，依次采如下步骤：
-
- 稀疏化 qsp(⋅)qsp(⋅)q_{s p}(cdot)
- 激活 qact(⋅)qact(⋅)q_{a c t}(cdot)
- 对称 qsym(⋅)qsym(⋅)q_{s y m}(cdot)
- 归一化 qnorm (⋅)qnorm (⋅)q_{text {norm }}(cdot)
- 稀疏化 qsp(⋅)qsp(⋅)q_{s p}(cdot)
根据相似性创建的邻接矩阵 SStilde{mathrm{S}} 通常是密集的，表示一个完全连通的图结构，但实际上并没有什么意义，所以采用基于 K近邻的稀疏化。
具体地说，对于每个节点，保留具有 top-ktop-ktext{top-k} 个连接值的边，并将其余的设置为 000。稀疏化的 qsp(⋅)qsp(⋅)q_{s p}(cdot) 表示为：
S(sp)ij=qsp(Sij)=⎧⎩⎨⎪⎪Sij,0,Sij∈top−k(Si)Sij∉top−k(Si)(6)Sij(sp)=qsp(Sij)={Sij,Sij∈top−k(Si)0,Sij∉top−k(Si)(6)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) , & tilde{mathrm{S}}_{i j} notin operatorname{top}-mathrm{k}left(tilde{mathrm{S}}_{i}right)end{array}right.quadquadquad(6)
其中， top−k(Si)top−k(Si)top-mathrm{k}left(tilde{mathrm{S}}_{i}right) 是行向量 SiSitilde{mathrm{S}}_{i} 的最大 kkk 个值的集合。注意，本文并不对 FGP learner 进行稀疏化。
对于大规模图，使用局部敏感近似[11] 来执行 kNN 稀疏化，其中最近邻是从一批节点而不是所有节点中选择的，这减少了对内存的需求。
cpp
def cal_similarity_graph(node_embeddings):
similarity_graph = torch.mm(node_embeddings, node_embeddings.t())
return similarity_graph
cal_similarity_graph Code
irpf90
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
对称化和激活的执行方式为：
S(sym)=qsym(qact(S(sp)))=σq(S(sp))+σq(S(sp))⊤2(7)S(sym)=qsym(qact(S(sp)))=σq(S(sp))+σq(S(sp))⊤2(7)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)
其中，σq(⋅)σq(⋅)sigma_{q}(cdot) 是一个非线性激活。对于基于度量学习的学习器，我们将 σq(⋅)σq(⋅)sigma_{q}(cdot) 定义为 ReLU 函数。对于 FGP learner，应用 ELU 函数来防止梯度消失。
ruby
def symmetrize(adj): # only for non-sparse
return (adj + adj.T) / 2
Symmetrization and Activation Code
3.2.3 Normalization为了保证边权值在 [0,1][0,1][0,1] 范围内，我们最后对 SStilde{mathrm{S}} 进行了归一化。特别地，我们应用了一个对称的归一化：
S=qnorm (S(sym))=(D(sym))−12S(sym)(D(sym))−12(8)S=qnorm (S(sym))=(D(sym))−12S(sym)(D(sym))−12(8)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)
其中，D(sym)D(sym)tilde{mathbf{D}}^{(s y m)} 为 S(sym)S(sym)tilde{mathbf{S}}^{(s y m)} 的度矩阵。
maxima
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 EstablishmentSUBLIME 将学习到的图（learner view）定义为一个视图，并用输入数据构造另一个视图（anchor view）。
Learner view
Learner view 采用 SSS 作为邻接矩阵，XXX 作为特征矩阵，即 Gl=(S,X)Gl=(S,X)mathcal{G}_{l}=(mathrm{S}, mathrm{X})。在每次训练迭代中，SSmathrm{S} 和用于建模的参数通过梯度下降直接更新，以发现最优的图结构。
在 SUBLIME 中，将 learner views 初始化为建立在特征基础上的 kNN 图 [11,12]。具体来说，
-
- 对于 FGP learner，将 kNN 边对应的参数初始化为 111，其余的初始化为000；
- 对于 attentive learner，让 ω(l)∈ωω(l)∈ωomega^{(l)} in omega 中的每个元素都为 111。然后，根据度量函数计算特征级相似度，并通过 sparsification post-processing 得到 kNN 图；
- 对于 MLP learner 和GNN learner，将嵌入维数设置为 ddd，并将 Ω(l)∈ωΩ(l)∈ωOmega^{(l)} in omega 初始化为单位矩阵；
- 对于 FGP learner，将 kNN 边对应的参数初始化为 111，其余的初始化为000；
ini
learned_adj = graph_learner(features)
Learner view Code
Anchor view
Anchor view 扮演着 "teacher” 的角色，为GSL提供了正确和稳定的指导。
对于 structure refinement task ，采用 原始图邻接矩阵 AAA，即 Ga=(Aa,X)=(A,X)Ga=(Aa,X)=(A,X)mathcal{G}_{a}=left(mathbf{A}_{a}, mathbf{X}right)=(mathbf{A}, mathrm{X})。
对于 structure inference task，采用单位矩阵 III 作为图结构，即 Ga=(Aa,X)=(I,X)Ga=(Aa,X)=(I,X)mathcal{G}_{a}=left(mathrm{A}_{a}, mathrm{X}right)=(mathrm{I}, mathrm{X})。
stylus
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
为干扰节点特征，随机选择一部分特征维度，并用 000 掩蔽它们。
形式上，对于给定的特征矩阵 XXmathbf{X}，首先采样一个掩蔽向量 m(x)∈{0,1}dm(x)∈{0,1}dmathbf{m}^{(x)} in{0,1}^{d}，其中每个元素都来自一个独立的概率为伯努利分布 p(x)p(x)p^{(x)}。然后，用 m(x)m(x)mathbf{m}^{(x)} 掩码每个节点的特征向量：
X¯¯¯¯=Tfm(X)=[x1⊙m(x),⋯,xn⊙m(x)]⊤(9)X¯=Tfm(X)=[x1⊙m(x),⋯,xn⊙m(x)]⊤(9)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)
其中，X¯X¯bar{X} 为增广特征矩阵，Tfm(⋅)Tfm(⋅)mathcal{T}_{f m}(cdot) 为特征掩蔽变换，xixix_{i} 为 XXX 的第 iii 行向量的转置。
Edge dropping
随机删除部分边来破坏图的结构。具体地说，对于给定的邻接矩阵 AAA，首先采样掩蔽矩阵 M(a)∈{0,1}n×nM(a)∈{0,1}n×nmathbf{M}^{(a)} in{0,1}^{n times n}，其中每个元素 M(a)ijMij(a)mathbf{M}_{i j}^{(a)} 是从概率为 p(a)p(a)p^{(a)} 的伯努利分布中抽取的。邻接矩阵被 M(a)M(a)mathbf{M}^{(a)} 屏蔽后：
A¯¯¯¯=Ted(A)=A⊙M(a)(10)A¯=Ted(A)=A⊙M(a)(10)overline{mathbf{A}}=mathcal{T}_{e d}(mathbf{A})=mathbf{A} odot mathbf{M}^{(a)}quadquadquad(10)
其中 A¯¯¯¯A¯overline{mathbf{A}} 为增广邻接矩阵，Ted(⋅)Ted(⋅)mathcal{T}_{e d}(cdot) 为边丢弃变换。
在 SUBLIME 中，利用这两种增强方案在 learner view 和 anchor view 上生成增强图：
G¯¯¯l=(Ted( S),Tfm(X)),G¯¯¯a=(Ted (Aa),Tfm(X))(11)G¯l=(Ted( S),Tfm(X)),G¯a=(Ted (Aa),Tfm(X))(11)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)
其中，G¯¯¯lG¯loverline{mathcal{G}}_{l} 和 G¯¯¯aG¯aoverline{mathcal{G}}_{a} 分别为增强的 learner view 和 anchor view。
为了在两个视图中获得不同的上下文，两个视图的 Feature masking 采用了不同的概率 p(x)l≠p(x)apl(x)≠pa(x)p_{l}^{(x)} neq p_{a}^{(x)}。对于 Edge dropping，由于两个视图的邻接矩阵已经有了显著的不同，因此使用相同的丢弃概率 p(a)l=p(a)a=p(a)pl(a)=pa(a)=p(a)p_{l}{(a)}=p_{a}{(a)}=p^{(a)}。
3.3.3 Node-level Contrastive Learning在获得两个增广图视图后，执行节点级对比学习，以最大化它们之间的 MI。在 SUBLIME 采用了一个来自 SimCLR[6] 的简单的对比学习框架，由以下组成部分组成：
GNN-based encoder
一个基于 GNN 的编码器 fθ(⋅)fθ(⋅)f_{theta}(cdot) 提取增广图 G¯¯¯lG¯loverline{mathcal{G}}_{l} 和 G¯¯¯aG¯aoverline{mathcal{G}}_{a} 的节点层表示：
Hl=fθ(G¯¯¯l),Ha=fθ(G¯¯¯a)(12)Hl=fθ(G¯l),Ha=fθ(G¯a)(12)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θ(⋅)fθ(⋅)f_{theta}(cdot) 的参数，Hl,Ha∈Rn×d1Hl,Ha∈Rn×d1mathrm{H}_{l}, mathrm{H}_{a} in mathbb{R}^{n times d_{1}}（ d1d1d_{1} 为表示维数）分别为 learner/anchor views 的节点表示矩阵。在 SUBLIME 中，使用 GCN 作为我们的编码器，并将其层数 L1L1L_{1} 设置为 222。
MLP-based projector
在编码器之后，一个带有 L2L2L_{2} 层的 MLP 投影头 gφ(⋅)gφ(⋅)g_{varphi}(cdot) 将表示映射到另一个潜在空间，在其中计算对比损失：
Zl=gφ(Hl),Za=gφ(Ha)(13)Zl=gφ(Hl),Za=gφ(Ha)(13)mathbf{Z}_{l}=g_{varphi}left(mathbf{H}_{l}right), mathbf{Z}_{a}=g_{varphi}left(mathbf{H}_{a}right)quadquadquad(13)
其中，φφvarphi 为投影头 gφ(⋅)gφ(⋅)g_{varphi}(cdot) 的参数，Zl,Za∈Rn×d2(d2Zl,Za∈Rn×d2(d2mathbf{Z}_{l}, mathbf{Z}_{a} in mathbb{R}^{n times d_{2}}(d_{2}（ d2d2d_{2} 为投影维数）分别为 learner/anchor views 的投影后的嵌入矩阵。
Node-level contrastive loss function
一个对比损失 LLmathcal{L} 被利用来强制最大化在两个视图上同一节点 viviv_{i} 上的投影 zl,izl,iz_{l, i} 和 za,iza,iz_{a, i} 之间的一致性。在我们的框架中，应用了对称归一化温度尺度交叉熵损失(NT-Xent)[29,35]：
L=12n∑ni=1[ℓ(zl,i,za,i)+ℓ(za,i,zl,i)]ℓ(zl,i,za,i)=logesim(zl,i,za,i)/t∑nk=1esim(zl,i,za,k)/t(14)L=12n∑i=1n[ℓ(zl,i,za,i)+ℓ(za,i,zl,i)]ℓ(zl,i,za,i)=logesim(zl,i,za,i)/t∑k=1nesim(zl,i,za,k)/t(14){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使用由 AAmathbf{A} 或 III 定义的固定的 Anchor 邻接矩阵 AaAamathbf{A}_{a}，SUBLIME 可以通过最大化两个视图之间的MI来学习图结构 SSS。
然而，使用固定的AaAamathbf{A}_{a} 可能会导致几个问题：
-
- Inheritance of error information。由于 AaAamathbf{A}_{a} 是直接从输入数据中得到的，所以它会携带原始图的一些自然噪声（例如，缺失或冗余的边）。如果在学习过程中不消除噪声，学习到的结构最终将继承它；
- Lack of persistent guidance。一个固定的锚点图包含有限的信息来指导GSL。一旦图形学习者捕获了这些信息，模型将很难在以下的训练步骤中获得有效的监督;
- Overfitting the anchor structure。在使两个视图之间的一致性最大化的学习目标的驱动下，学习到的结构倾向于过度拟合固定的锚定结构，从而导致与原始数据相似的测试性能；
- Inheritance of error information。由于 AaAamathbf{A}_{a} 是直接从输入数据中得到的，所以它会携带原始图的一些自然噪声（例如，缺失或冗余的边）。如果在学习过程中不消除噪声，学习到的结构最终将继承它；
受基于 bootstrap 的算法 [5,14,37] 的启发，本文设计了一个 structure bootstrapping mechanism，提供一个 bootstrap 的 Anchor 视图作为学习目标。本文解决方案的核心思想是通过学习到的 SSS 缓慢更新锚定结构 AaAamathbf{A}_{a}，而不是保持 AaAamathbf{A}_{a} 不变。即，给定衰减速率 τ∈[0,1]τ∈[0,1]tau in[0,1]，锚定结构 AaAamathbf{A}_{a} 每 ccc 次迭代更新如下：
Aa←τAa+(1−τ)S(15)Aa←τAa+(1−τ)S(15)mathbf{A}_{a} leftarrow tau mathbf{A}_{a}+(1-tau) mathrm{S} quadquadquad(15)
随着更新过程的进行，AaAamathbf{A}_{a} 中一些噪声边的权值逐渐减小，减轻了它们对结构学习的负面影响。同时，由于学习目标 AaAamathbf{A}_{a} 在训练阶段发生了变化，它总是可以包含更有效的信息来指导拓扑的学习，过拟合问题自然得到了解决。更重要的是，Structure Bootstrapping Mechanism 利用学习到的知识来提高学习目标，从而推动模型不断发现越来越最优的图结构。此外，slow-moving average（τ≥0.99τ≥0.99tau ge 0.99）的更新确保了训练的稳定性。
4 Experiments数据集
Node classification in structure inference scenario
Node classification in structure refinement scenario
Node clustering in structure refinement scenario
5 Conclusion本文对无监督图结构学习问题进行了首次研究。为了解决这个问题，我们设计了一种新的方法，即崇高的方法，它能够利用数据本身来生成最优的图结构。为了学习图的结构，我们的方法使用对比学习来最大限度地提高学习到的拓扑结构和一个自增强的学习目标之间的一致性。大量的实验证明了学习结构的优越性和合理性。
-
论文信息
-
1 Introduction
-
2 Problem Definition
-
3 Method
-
3.1 Graph Learner
-
3.1.1 FGP learner
-
3.1.2 Attentive Learner
-
3.1.3 MLP Learner
-
3.1.4 GNN Learner
-
3.2 Post-processor
-
3.2.1 Sparsification
-
3.2.3 Normalization
-
3.3 Multi-view Graph Contrastive Learning
-
3.3.1 Graph View Establishment
-
3.3.2 Data Augmentation
-
3.3.3 Node-level Contrastive Learning
-
3.4 Structure Bootstrapping Mechanism
-
4 Experiments
-
5 Conclusion
__EOF__
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rmTZUF8u-1654318147820)(https://blog.csdn.net/BlairGrowing)]Blair - 本文链接： https://blog.csdn.net/BlairGrowing/p/16339629.html
- 关于博主： 评论和私信会在第一时间回复。或者直接私信我。
- 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
- 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角**【[推荐](javascript:void(0)】**一下。
