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

论文信息

论文标题：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 X∈Rn×d , the target of structure inference is to automatically learn a graph topology S∈[0,1]n×n , which reflects the underlying correlations among data samples. In particular, Sij∈[0,1] indicates whether there is an edge between two samples (nodes) xi and xj .

　　Definition 3.2 (Structure refinement). Given a graph G=(A,X) with a noisy graph structure A , the target of structure refinement is to refine A to be the optimized adjacency matrix S∈[0,1]n×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 生成一个带参数的图邻接矩阵 ˜S∈Rn×n。本文的 Graph Learner 包括如下四种：

• • FGP learner　　
  • Attentive Learner　　
  • MLP Learner　　
  • GNN Learner　　

3.1.1 FGP learner

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

　　　　˜S=pFGPω=σ(Ω)(1)

　　其中，ω=Ω∈Rn×n 是一个参数矩阵，σ(⋅) 是一个非线性函数，使训练更稳定。FGP学习器背后的假设是，每条边都独立地存在于图中。

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 不同，基于度量学习的Learner [7,58] 首先从输入数据中获取节点嵌入 E∈Rn×d，然后利用节点嵌入的两两相似性对 ˜S 进行建模：

　　　　˜S=pMLω(X,A)=ϕ(hω(X,A))=ϕ(E)(2)

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

　　对于不同的 hω(⋅)，本文是 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) 是第 l 层嵌入矩阵，e(l−1)i∈Rd 是 E(l−1) 第 i 行向量；　　
  • ω(l)∈Rd 是第 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)

3.1.3 MLP Learner

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

　　　　E(l)=h(l)w(E(l−1))=σ(E(l−1)Ω(l))(4)

　　其中，Ω(l)∈Rd×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

3.1.4 GNN Learner

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

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

　　　　E(l)=h(l)w(E(l−1),A)=σ(˜D−12˜A˜D−12E(l−1)Ω(l))(5)

　　其中，˜A=A+I 为具有自环的邻接矩阵，˜D 为 ˜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

3.2 Post-processor

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

　　因此，依次采如下步骤：

• • 稀疏化 qsp(⋅)
  • 激活 qact(⋅)
  • 对称 qsym(⋅)
  • 归一化 qnorm (⋅)

3.2.1 Sparsification

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

　　具体地说，对于每个节点，保留具有 top-k 个连接值的边，并将其余的设置为 0。稀疏化的 qsp(⋅) 表示为：

　　　　˜S(sp)ij=qsp(˜Sij)={˜Sij,˜Sij∈top−k(˜Si)0,˜Sij∉top−k(˜Si)(6)

　　其中， top−k(˜Si) 是行向量 ˜Si 的最大 k 个值的集合。注意，本文并不对 FGP learner 进行稀疏化。

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

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

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

3.2.2 Symmetrization and Activation

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

　　　　˜S(sym)=qsym(qact(˜S(sp)))=σq(˜S(sp))+σq(˜S(sp))⊤2(7)

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

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

3.2.3 Normalization

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

　　　　S=qnorm (˜S(sym))=(˜D(sym))−12˜S(sym)(˜D(sym))−12(8)

　　其中，˜D(sym) 为 ˜S(sym) 的度矩阵。

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())

3.3 Multi-view Graph Contrastive Learning

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

3.3.1 Graph View Establishment

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

Learner view

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

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

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

learned_adj = graph_learner(features)

Anchor view

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

　　对于 structure refinement task ，采用 原始图邻接矩阵 A，即 Ga=(Aa,X)=(A,X)。

　　对于 structure inference task，采用单位矩阵 I 作为图结构，即 Ga=(Aa,X)=(I,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)

3.3.2 Data Augmentation

　　数据增强：Feature mask 和 Edge drop。

Feature masking

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

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

　　　　¯X=Tfm(X)=[x1⊙m(x),⋯,xn⊙m(x)]⊤(9)

　　其中，ˉX 为增广特征矩阵，Tfm(⋅) 为特征掩蔽变换，xi 为 X 的第 i 行向量的转置。

Edge dropping

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

　　　　¯A=Ted(A)=A⊙M(a)(10)

　　其中 ¯A 为增广邻接矩阵，Ted(⋅) 为边丢弃变换。

---

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

　　　　¯Gl=(Ted( S),Tfm(X)),¯Ga=(Ted (Aa),Tfm(X))(11)

　　其中，¯Gl 和 ¯Ga 分别为增强的 learner view 和 anchor view。

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

3.3.3 Node-level Contrastive Learning

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

GNN-based encoder

　　一个基于 GNN 的编码器 fθ(⋅) 提取增广图 ¯Gl 和 ¯Ga  的节点层表示：

　　　　Hl=fθ(¯Gl),Ha=fθ(¯Ga)(12)

　　其中，θ 为编码器 fθ(⋅) 的参数，Hl,Ha∈Rn×d1（ d1 为表示维数）分别为 learner/anchor views 的节点表示矩阵。在 SUBLIME 中，使用 GCN 作为我们的编码器，并将其层数 L1 设置为 2。

MLP-based projector

　　在编码器之后，一个带有 L2 层的 MLP 投影头 gφ(⋅)  将表示映射到另一个潜在空间，在其中计算对比损失：

　　　　Zl=gφ(Hl),Za=gφ(Ha)(13)

　　其中，φ 为投影头 gφ(⋅) 的参数，Zl,Za∈Rn×d2(d2（ d2 为投影维数）分别为 learner/anchor views 的投影后的嵌入矩阵。

Node-level contrastive loss function

　　一个对比损失 L 被利用来强制最大化在两个视图上同一节点 vi 上的投影 zl,i 和 za,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)

3.4 Structure Bootstrapping Mechanism

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

　　然而，使用固定的Aa 可能会导致几个问题：

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

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

　　　　Aa←τAa+(1−τ)S(15)

　　随着更新过程的进行，Aa 中一些噪声边的权值逐渐减小，减轻了它们对结构学习的负面影响。同时，由于学习目标 Aa 在训练阶段发生了变化，它总是可以包含更有效的信息来指导拓扑的学习，过拟合问题自然得到了解决。更重要的是，Structure Bootstrapping Mechanism 利用学习到的知识来提高学习目标，从而推动模型不断发现越来越最优的图结构。此外，slow-moving average（τ≥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__