图异常检测：GraphSAGE 归纳式方法及其与GCN的对比

GCN的基本原理

GCN由Kipf和Welling在2016年提出，是一种基于谱图理论的图卷积网络。GCN的核心思想是将传统卷积神经网络（CNN）中的卷积操作推广到图结构数据上。

GCN的层更新公式为：

$$H^{(l+1)}=\sigma \left({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{\left(l\right)}{W}^{\left(l\right)}\right)$$

其中： - $\tilde{A}=A+I$ 是添加了自环的邻接矩阵 - $\tilde{D}$ 是 $\tilde{A}$ 的度矩阵 - $H^{\left(l\right)}$ 是第 $l$ 层的节点特征 - $W^{\left(l\right)}$ 是可学习的权重矩阵 - $\sigma$ 是非线性激活函数

GCN的优缺点

优点： 1. 理论基础扎实，基于谱图理论 2. 模型简洁，易于实现 3. 在小型图上表现良好

缺点： 1. 转导式学习（Transductive Learning），难以处理未见过的节点 2. 需要整个图的邻接矩阵，难以处理大规模图 3. 固定的聚合方式，缺乏灵活性 4. 存在过平滑（Over-smoothing）问题，层数增加时性能下降

GraphSAGE的基本原理

GraphSAGE由Hamilton等人在2017年提出，是一种归纳式图表示学习方法。与GCN不同，GraphSAGE通过采样和聚合邻居信息来生成节点嵌入，使得模型可以处理大规模图和动态变化的图结构。

GraphSAGE的关键创新在于： 1. 通过采样固定数量的邻居，避免处理整个图 2. 将节点自身信息与邻居信息进行聚合 3. 支持多种可学习的聚合函数

GraphSAGE的更新过程包含三个步骤：

1. 邻居采样：对每个节点，随机采样固定数量的邻居

2. 信息聚合：使用聚合函数整合邻居信息 $$h_{N\left(v\right)}^k={\text{AGGREGATE}}_k\left(\right\{h_u^{k-1},\forall u\in N\left(v\right)\left\}\right)$$

3. 节点更新：将节点自身表示$h_v^{k-1}$与聚合后的邻居信息$h_{N\left(v\right)}^k$进行拼接，然后通过全连接层和非线性变换： $$h_v^k=\sigma (W^k\cdot \text{CONCAT}(h_v^{k-1},h_{N\left(v\right)}^k\left)\right)$$ 最后进行归一化： $$h_v^k=h_v^k/\parallel h_v^k{\parallel }_2$$

其中，$N\left(v\right)$ 是节点 $v$ 的采样邻居集合，$\text{AGGREGATE}$ 是聚合函数。这种设计使得GraphSAGE能够同时利用节点自身特征和局部结构信息。

GraphSAGE的聚合函数

GraphSAGE提供了多种聚合函数选择：

1. Mean Aggregator：计算邻居特征的平均值 $${\text{AGGREGATE}}_{\text{mean}}=\text{MEAN}\left(\right\{h_u,\forall u\in N\left(v\right)\left\}\right)$$

2. Max-pooling Aggregator：对邻居特征进行非线性变换后取最大值 $${\text{AGGREGATE}}_{\text{max}}=\text{MAX}\left(\right\{\sigma (W_{\text{pool}}{h}_u+b),\forall u\in N\left(v\right)\left\}\right)$$

3. LSTM Aggregator：使用LSTM处理邻居特征序列 $${\text{AGGREGATE}}_{\text{LSTM}}=\text{LSTM}\left(\right\{h_u,\forall u\in N\left(v\right)\left\}\right)$$

GraphSAGE的优缺点

优点： 1. 归纳式学习（Inductive Learning），可以处理未见过的节点 2. 通过邻居采样策略，可以处理大规模图 3. 灵活的聚合函数，适应不同类型的图结构 4. 可以通过小批量训练减少内存需求

缺点： 1. 采样策略可能导致信息损失 2. 聚合函数的选择需要经验 3. 多层堆叠时仍存在过平滑问题

计算范式

GCN：采用转导式学习，需要在训练时看到整个图，难以处理新节点。

GraphSAGE：采用归纳式学习，通过学习聚合函数，可以为未见过的节点生成嵌入。

可扩展性

GCN：需要整个图的邻接矩阵，空间复杂度为O(|V|²)，难以处理大规模图。

GraphSAGE：通过邻居采样，每次只处理固定数量的邻居，空间复杂度与采样数量相关，可以处理大规模图。

聚合方式

GCN：使用固定的归一化拉普拉斯矩阵进行聚合，缺乏灵活性。

GraphSAGE：提供多种聚合函数（均值、最大值、LSTM等），可以根据图的特性选择合适的聚合方式。

内存需求

GCN：需要将整个图加载到内存中。

GraphSAGE：可以通过小批量训练和邻居采样减少内存需求。

适用场景

GCN：适合小型静态图，如引文网络、社交网络的子图等。

GraphSAGE：适合大规模图、动态变化的图，以及需要处理新节点的场景，如大型社交网络、推荐系统等。

GraphSAGE实现

下面是使用PyTorch Geometric实现GraphSAGE的核心代码：

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import SAGEConv

class GraphSAGE(nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, num_layers=2, 
                 dropout=0.5, aggr='mean'):
        super(GraphSAGE, self).__init__()
        
        self.num_layers = num_layers
        self.dropout = dropout
        
        self.convs = nn.ModuleList()
        
        # 输入层
        self.convs.append(SAGEConv(in_channels, hidden_channels, aggr=aggr))
        
        # 隐藏层
        for _ in range(num_layers - 2):
            self.convs.append(SAGEConv(hidden_channels, hidden_channels, aggr=aggr))
            
        # 输出层
        self.convs.append(SAGEConv(hidden_channels, out_channels, aggr=aggr))
    
    def forward(self, x, edge_index):
        for i, conv in enumerate(self.convs):
            x = conv(x, edge_index)
            
            if i < self.num_layers - 1:
                x = F.relu(x)
                x = F.dropout(x, p=self.dropout, training=self.training)
        
        return x

GCN实现

下面是使用PyTorch Geometric实现GCN的核心代码：

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class GCN(nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, num_layers=2, 
                 dropout=0.5):
        super(GCN, self).__init__()
        
        self.num_layers = num_layers
        self.dropout = dropout
        
        self.convs = nn.ModuleList()
        
        # 输入层
        self.convs.append(GCNConv(in_channels, hidden_channels))
        
        # 隐藏层
        for _ in range(num_layers - 2):
            self.convs.append(GCNConv(hidden_channels, hidden_channels))
            
        # 输出层
        self.convs.append(GCNConv(hidden_channels, out_channels))
    
    def forward(self, x, edge_index):
        for i, conv in enumerate(self.convs):
            x = conv(x, edge_index)
            
            if i < self.num_layers - 1:
                x = F.relu(x)
                x = F.dropout(x, p=self.dropout, training=self.training)
        
        return x

两种模型的训练代码

下面是训练GraphSAGE和GCN模型的代码示例：

def train(model, data, optimizer):
    model.train()
    optimizer.zero_grad()
    
    # 前向传播
    out = model(data.x, data.edge_index)
    
    # 计算损失
    loss = F.cross_entropy(out[data.train_mask], data.y[data.train_mask])
    
    # 反向传播
    loss.backward()
    optimizer.step()
    
    return loss.item()

def test(model, data):
    model.eval()
    
    with torch.no_grad():
        out = model(data.x, data.edge_index)
        pred = out.argmax(dim=1)
        
        # 计算准确率
        train_acc = pred[data.train_mask].eq(data.y[data.train_mask]).sum().item() / data.train_mask.sum().item()
        val_acc = pred[data.val_mask].eq(data.y[data.val_mask]).sum().item() / data.val_mask.sum().item()
        test_acc = pred[data.test_mask].eq(data.y[data.test_mask]).sum().item() / data.test_mask.sum().item()
    
    return train_acc, val_acc, test_acc