paper link: Towards Unsupervised Deep Graph Structure Learning

code link： TrustAGI-Lab/SUBLIME: [WWW’22] Towards Unsupervised Deep Graph Structure Learning

Concepts

Metric Learning： 学习一个变换函数， 将数据从原始的向量空间映射到新的向量空间，使得相似的点距离更近。

Overview

​ 作者认为现有的 graph structure learning (GSL) 大多为 under supervision of node classification task， 存在 the reliance on label information 以及 the bias of learned edge distribution。 后者具体而言为：node classification 一般采用 semi-supervised setting， under supervision 的节点会有更多的指导，远离 supervision 的节点间的关系很少被发现。

​ 作者为了解决上述问题，提出了 “ StrUcture Bootstrapping contrastive LearnIng fraMEwork “ (SUBLIME) 。

Problem Definition

​ 作者主要考虑两个无 node labels 任务: 1. Structure Inference (图结构不可见, 建立图结构) 2. Structure Refinement (图结构可见, 优化图结构) 。

Methodology

​ SUBLIME 由两部分组成: graph structure learning module 和 structure bootstrapping contrastive learning module 。

$\mathrm{A} \in [0, 1] ^{n \times n}$ : original adjacency matrix

$\mathrm{S} \in [0, 1] ^ {n \times n}$ ：learned adjacency matrix

$\mathrm{X} \in \mathbb{R} ^ {n \times d}$: node feature matrix

$p_{\omega}(\cdot)$: graph learner, $\omega$ is learnable parameter

$\mathrm{E} \in \mathbb{R}^{n \times d}$: node embedding

Graph Learner

​ 作者考虑四个 graph learner， 包括 full graph parameterization (FGP) learner 以及三个 metric learning-based learners (Attentive, MLP and GNN leaner)。

FGP learner

其将邻接矩阵的每个元素视为独立的可学习参数, 没有任何额外输入。FGP的假设是图中的每个边独立存在（独立超参数的含义）。

定义如公式 $\eqref{FGP_learner}$ 所示：

其中 $\omega = \Omega \in \mathbb{R} ^{n \times n}$ 为参数矩阵， $\sigma(\cdot)$ 为非线性激活函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class FGP_learner(nn.Module):
    """
    Construct a k-nearest neighbor graph adjacency matrix with ELU pre-processing.
    Parameters:
    features : np.ndarray or torch.Tensor
    Input feature matrix of shape (n_samples, n_features).
    k : int
    Number of neighbors per node (excluding self).
    knn_metric : str
    Distance metric for neighbor search (e.g., 'euclidean', 'cosine').
    i : float
    Controls negative value magnitude for non-edges (larger = stronger suppression).
    sparse : bool
    If True, returns sparse adjacency matrix; otherwise dense.
    
    Returns:
    torch.Tensor
    Pre-processed adjacency matrix where:
    - Connected edges (including self-loops) = 0
    - Non-edges = -i
    Ready for subsequent ELU activation (ELU(x) + 1).
    """
    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

        # initialize the adjacency matrix via kNN with pre-ELU processing
        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

Metric Learning-based learner

其首先从输入获得节点嵌入 $\mathrm{E}$， 随后使用节点嵌入的成对相似性对 $\tilde{\mathrm{S}}$ 进行建模。

定义如公式 $\eqref{ML_learner}$ 所示：

其中 $h_w(\cdot)$ 是参数为 $\omega$ 的神经网络（Attentive e.t.c.）， $\phi(\cdot)$ 为计算成对相似度的非参数度量函数（Metric Learning）。

Attentive Learner

其假设不同features对于边的存在贡献不同， 但是features之间没有显著的相关性（同一维度的feature权值相同）。

定义如公式 $\eqref{Attentive_learner}$ 所示：

其中 $e_i^{(l - 1)} \in \mathbb{R}^{d}$ 是 $\mathrm{E}^{(l - 1)}$ 的 $i\text{-th}$ 行向量的转置， $w^{(l)} \in \mathbb{R}^d$ 是 $l\text{-th}$ layer 的参数向量， $\odot$ 为 hadamard operation 。

第一层输入 $\mathrm{E}^{(0)}$ 为 feature matrix $\mathrm{X}$， 最后一层输出为 embedding matrix $\mathrm{E}$ 。

MLP Learner

其进一步考虑了features的相关性与组合， 有更丰富的语义信息（右乘权重矩阵等于做线性组合）。

定义如公式 $\eqref{MLP_learner}$ 所示：

其中 $\Omega^{(l)} \in \mathbf{R}^{d \times d}$ 为 $l\text{-th}$ layer 的参数矩阵。

GNN Learner

其将 features $\mathrm{X}$ 与 原始结构 $\mathrm{A}$ 整合为 embedding matrix $\mathrm{E}$ ， 但由于使用了原始结构该learner只用于 refinement 。

其假定节点之间的关系不仅依赖于 feature 也依赖于原始结构。

定义如公式 $\eqref{GNN_learner}$ 所示：

其中 $\mathrm{\tilde{A}} = \mathrm{A} + \mathrm{I}$ 为 adjacency matrix 加 self-loop， $\tilde{\mathrm{D}}$ 为 $\mathrm{\tilde{A}}$ 的 degree matrix 。

Post-processor

将模型得到的邻接矩阵优化成 稀疏、非负、对称与正则化的邻接矩阵。

Sparsification

模型输出的矩阵通常是计算昂贵的full-connected matrix， 作者采用 kNN 将其转化为稀疏矩阵 $ \tilde{S} $ . 具体而言， 对每一个节点保持 top-k 个连接值， 并将其他设为0 。

其中 $\text{top-k}(\mathrm{\tilde{S}}_i)$ 代表行向量 $\mathrm{\tilde{S}}_i$ 的 top-k 值。为了保证梯度的正常流动， 对于FGP Learner 不进行该操作。对于大规模图， 采用 batch 内的节点进行 kNN。

Symmetrization and Activation

真实世界中的图的连接都是双向并且边的权重是非负的。

其中 $\sigma_{q}(\cdot)$ 是非线性激活函数， 对于 FGP Learner 设置为 ELU function 以阻止梯度消失， 对于其他的设置为 ReLU function 。

Normalization

为了保证边权在 $[0, 1]$ 之间， 作者对 $\mathrm{\tilde{S}}$ 进行 symmetrical normalization ：

其中 $\mathrm{\tilde{D}}^{(sym)}$ 是 $\mathrm{\tilde{S}}^{(sym)} $ 的节点矩阵。

Multi-view Graph Contrastive Learning

作者通过建立两个不同的视图以构建监督信号， 并且在两个视图上进行数据增强， 最后通过 node-level contrastive learning 最大化不同视图间的互信息。

Graph View Establishment

Learner View

直接将 $\mathrm{X}$ 与 $\mathrm{S}$ 整合成为 $\mathcal{G}_l = (\mathrm{S}, \mathrm{X})$ , 并且采用 kNN 对 leaner view 进行初始化。对于 FGP Learner, 对于包含 kNN 边的参数设为 1， 其余的设置为 0 。 对于 Attentive Learner， $\mathcal{w}$ 都设置为 1 。对于 MLP Learner 和 GNN learner ，将 embedding 的维度设置为 $d$ 并且将 $\Omega^{(l)} \in w$ 为单位矩阵。

Anchor View

作为监督进行指导。 对于 refinement， 原始结构 $\mathrm{A}$ 可见， anchor view 被定义为 $ \mathcal{G}_{a} = (\mathrm{A}_{a}, \mathrm{X}) = (\mathrm{A}, \mathrm{X}) $。 对于inference， 原始结构 $A$ 不可见， anchor view 被定义为 $ \mathcal{G}_{a} = (\mathrm{A}_{a}, \mathrm{X}) = (\mathrm{A}, \mathrm{I}) $ 。 同时， 该文章采用 bootstrapping 进行 anchor view 的更新而不是 gradient descent 。

Data Augmentation

Feature Masking

对于 $\mathrm{X}$，从 Bernoulli distribution 中以 $p^{(x)}$ 的概率独立 sample 出 masking vector $ m^{(x)} \in \{ 0, 1\}^{d} $ ， 并且将每个 node 的 feature vector 进行 mask：

其中 $ \mathrm{\bar{X}} $ 为增强的 feature matrix , $ \cal{T}_{f_{m}}(\cdot) $ 为 feature masking transformation, $ \mathrm{x}_i $ 是 $ \mathrm{X} $ 的 $ \text{i-th} $ 向量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# view 1: anchor graph
if args.maskfeat_rate_anchor:
    mask_v1, _ = get_feat_mask(features, args.maskfeat_rate_anchor)
    features_v1 = features * (1 - mask_v1)

z1, _ = model(features_v1, anchor_adj, 'anchor')

# view 2: learned graph
if args.maskfeat_rate_learner:
    mask, _ = get_feat_mask(features, args.maskfeat_rate_learner)
    features_v2 = features * (1 - mask)

# get learned graph
learned_adj = graph_learner(features)

z2, _ = model(features_v2, learned_adj, 'learner')
Edge dropping

对于 $\mathrm{A}$ , 从 Bernoulli distribution 中以 $p^{(a)}$ 的概率独立 sample 出 masking matrix $\mathrm{M} ^{(x)} \in \{ 0, 1\}^{n \times n}$ 的每个元素， 并且将邻接矩阵进行 mask：

其中 $ \mathrm{\bar{A}} $ 是增强的 adjacency matrix， $ \mathcal{T}_{ed}(\cdot) $ 是 edge dropping transformation 。

​ 在不同的视图上同时利用两种增强方法：

其中 $ \bar{\mathcal{G}}_l $ 和 $ \bar{\mathcal{G}}_a $ 是增强的 learner view 以及 anchor view。 同时为了得到不同上下文 ， feature masking 采用不同的概率 $ p^{(x)}_l \neq p^{(x)}_a $ 。 由于不同邻接矩阵已经显著不同， edge dropping 概率设为一致 $ p^{(a)}_l = p^{(a)}_a = p^{(a)} s$ 。

1
2
# drop edge
Adj.edata['w'] = F.dropout(Adj.edata['w'], p=self.dropout_adj_p)

Node-level Contrastive Learning

主模型由以下部件组成

GNN-based encoder

作者采用 GCN 将 layer 设置为 2 进行特征提取：

其中 $\theta$ 是 encoder $\mathcal{f}_\theta(\cdot) $ 的参数， 并且 $\mathrm{H}_l, \mathrm{H}_a \in \mathbb{R}^{n \times d_1} $ 分别是不同视图的 representation 矩阵。

MLP-based projector

采用 $L_2$ 层 MLP 将 representation 映射到计算 contrast loss 的隐空间。

其中 $\phi$ 是 projector $\mathcal{g}_\phi(\cdot) $ 的参数， 并且 $\mathrm{Z}_l, \mathrm{Z}_a \in \mathbb{R}^{n \times d_2} $ 分别是不同视图的 projected representation 矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class GraphEncoder(nn.Module):
    def __init__(self, nlayers, in_dim, hidden_dim, emb_dim, proj_dim, dropout, dropout_adj, sparse):

        super(GraphEncoder, self).__init__()
        self.dropout = dropout
        self.dropout_adj_p = dropout_adj
        self.sparse = sparse

        self.gnn_encoder_layers = nn.ModuleList()
        
        self.gnn_encoder_layers.append(GCNConv_dense(in_dim, hidden_dim))
        
        for _ in range(nlayers - 2):
            self.gnn_encoder_layers.append(GCNConv_dense(hidden_dim, hidden_dim))
        self.gnn_encoder_layers.append(GCNConv_dense(hidden_dim, emb_dim))

        self.dropout_adj = nn.Dropout(p=dropout_adj)

        self.proj_head = Sequential(Linear(emb_dim, proj_dim), ReLU(inplace=True),
                                           Linear(proj_dim, proj_dim))

    def forward(self,x, Adj_, branch=None):

        if self.sparse:
            if branch == 'anchor':
                Adj = copy.deepcopy(Adj_)
            else:
                Adj = Adj_
            Adj.edata['w'] = F.dropout(Adj.edata['w'], p=self.dropout_adj_p, training=self.training)
        else:
            Adj = self.dropout_adj(Adj_)

        for conv in self.gnn_encoder_layers[:-1]:
            x = conv(x, Adj)
            x = F.relu(x)
            x = F.dropout(x, p=self.dropout, training=self.training)
        x = self.gnn_encoder_layers[-1](x, Adj)
        z = self.proj_head(x)
        return z, x

class GCL(nn.Module):
    def __init__(self, nlayers, in_dim, hidden_dim, emb_dim, proj_dim, dropout, dropout_adj, sparse):
        super(GCL, self).__init__()

        self.encoder = GraphEncoder(nlayers, in_dim, hidden_dim, emb_dim, proj_dim, dropout, dropout_adj, sparse)

    def forward(self, x, Adj_, branch=None):
        z, embedding = self.encoder(x, Adj_, branch)
        return z, embedding
Node-level contrastive loss function

采用 symmetric normalized temperature-scaled cross-entropy loss (NT-Xent) 最大化不同视图间的投影的一致性 ：

其中 $\text{sim}(\cdot, \cdot)$ 是 cosine similarity， $t$ 是温度参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def calc_loss(x, x_aug, temperature=0.2, sym=True):
    """
    Calculates the contrastive loss between two augmented graph views.
    :param x: features from view 1
    :param x_aug: features from view 2
    :param temperature: temperature parameter for scaling
    :param sym: whether to use symmetric loss
    """
    batch_size, _ = x.size()
    x_abs = x.norm(dim=1)
    x_aug_abs = x_aug.norm(dim=1)

    sim_matrix = torch.einsum('ik,jk->ij', x, x_aug) / torch.einsum('i,j->ij', x_abs, x_aug_abs)
    sim_matrix = torch.exp(sim_matrix / temperature)
    pos_sim = sim_matrix[range(batch_size), range(batch_size)]
    if sym:
        loss_0 = pos_sim / (sim_matrix.sum(dim=0) - pos_sim)
        loss_1 = pos_sim / (sim_matrix.sum(dim=1) - pos_sim)

        loss_0 = - torch.log(loss_0).mean()
        loss_1 = - torch.log(loss_1).mean()
        loss = (loss_0 + loss_1) / 2.0
        return loss
    else:
        loss_1 = pos_sim / (sim_matrix.sum(dim=1) - pos_sim)
        loss_1 = - torch.log(loss_1).mean()
        return loss_1

Structure Bootstrapping Mechanism

采用固定 anchor view 会带来如下问题： 1. 错误信息的继承，anchor view 是从输入中得到的会携带噪声 2.持续指导的缺失，固定 anchor view 的指导信息有限，模型一旦学习到信息后就难以继续提升 3. 对anchor view的过拟合，优化目标决定了learner view 会过度拟合固定 anchor view， 从而导致相近的性能

采用 $\mathrm{S}$ 缓慢增强 $\mathrm{A}_a$, 即给定 decay rate $\tau \in [0, 1] $ 每 c 轮 iteration 通过以下公式进行更新：

其中 $\tau > 0.99$ 以确保稳定。

1
2
3
4
5
6
7
8
9
# Structure Bootstrapping
if (1 - args.tau) and (args.c == 0 or epoch % args.c == 0):
    if args.sparse:
        learned_adj_torch_sparse = dgl_graph_to_torch_sparse(Adj)
        anchor_adj_torch_sparse = anchor_adj_torch_sparse * args.tau \
                                  + learned_adj_torch_sparse * (1 - args.tau)
        anchor_adj = torch_sparse_to_dgl_graph(anchor_adj_torch_sparse)
    else:
        anchor_adj = anchor_adj * args.tau + Adj.detach() * (1 - args.tau)

Main Code

主体训练代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def loss_gcl(model, graph_learner, features, anchor_adj):
        """
        :param model: encoder and projection
        :param graph_learner: graph learner model
        :param features: feature matrix
        :param anchor_adj: anchor adjacency matrix
        """
        # view 1: anchor graph
        if args.maskfeat_rate_anchor:
            mask_v1, _ = get_feat_mask(features, args.maskfeat_rate_anchor)
            features_v1 = features * (1 - mask_v1)
        else:
            features_v1 = copy.deepcopy(features)

        z1, _ = model(features_v1, anchor_adj, 'anchor')

        # view 2: learned graph
        if args.maskfeat_rate_learner:
            mask, _ = get_feat_mask(features, args.maskfeat_rate_learner)
            features_v2 = features * (1 - mask)
        else:
            features_v2 = copy.deepcopy(features)

        learned_adj = graph_learner(features)
        
        if not args.sparse:
            learned_adj = symmetrize(learned_adj)
            learned_adj = normalize(learned_adj, 'sym', args.sparse)

        z2, _ = model(features_v2, learned_adj, 'learner')
        
        # compute loss
        loss = calc_loss(z1, z2)

        return loss, learned_adj

# anchor view
anchor_adj_raw = torch.eye(features.shape[0])
anchor_adj = normalize(anchor_adj_raw, 'sym', args.sparse)

# graph learner
graph_learner = FGP_learner(features.cpu())

# gnn-based encoder and mlp-based projector
model = GCL(nlayers=args.nlayers, in_dim=nfeats, hidden_dim=args.hidden_dim,
                         emb_dim=args.rep_dim, proj_dim=args.proj_dim,
                         dropout=args.dropout, dropout_adj=args.dropedge_rate, sparse=args.sparse)

# optimizer
optimizer_cl = torch.optim.Adam(model.parameters(), lr=args.lr, weight_decay=args.w_decay)
optimizer_learner = torch.optim.Adam(graph_learner.parameters(), lr=args.lr, weight_decay=args.w_decay)

# train
for epoch in range(1, args.epochs + 1):
    model.train()
    graph_learner.train()
	
    # compute loss
    loss, Adj = loss_gcl(model, graph_learner, features, anchor_adj)
	
    optimizer_cl.zero_grad()
    optimizer_learner.zero_grad()
    loss.backward()
    optimizer_cl.step()
    optimizer_learner.step()
    
    # bootstrap
    anchor_adj = anchor_adj * args.tau + Adj.detach() * (1 - args.tau)
    
    # eval
   	if epoch % args.eval_freq == 0:
        model.eval()
        graph_learner.eval()
        _, embedding = model(features, Adj)