李宏毅机器学习第十三周GNN2

摘要

本文内容分为主要三部分。首先，介绍了Spectral-Based Convolution基于谱域的卷积计算的GNN，了解了傅里叶变换的基本概念以及如何以其为基础构造卷积操作。简要了解了ChebNet对于两个问题的解决方案。简单介绍了GCN。其次，以pytorch_gerometric实现了GCN网络，基于ESOL数据集实现了根据分子结构预测可溶性。最后，阅读了一篇研究GNN文献，该文献主要提出了一种针对无边节点的网络框架——Edgeless-GNN，并设计了topology-aware loss function。在不同规模的数据集上证明了框架与损失函数的稳定性与优越性。

Abstract

The content of this article is divided into three main parts. Firstly, the Spectral-Based GNN is introduced, and the basic concepts of Fourier transform and how to construct convolution operations based on it are introduced. A look at ChebNet’s solution to two problems, and a brief introduction to GCN will be contained in this article. Secondly, the GCN network is implemented by pytorch_gerometric, and the solubility is predicted according to the molecular structure based on the ESOL dataset. Finally, A research GNN paper has been read, which mainly proposes a network framework for edgeless nodes——Edgeless-GNN, and designs the topology-aware loss function. The stability and superiority of the framework and the loss function are proved on datasets of different scales.

一、GNN第二部分Spectral-Based Convolution

将本层feature map与filter做傅里叶变换，二者相乘之后做反傅里叶变换得到下一层的feature map

0. Fourier Transfrom

本部分是该课程的数学基础

任何一个周期函数都能等价为一系列的正（余）弦函数的和，这就是傅里叶级数

将一个周期函数经过傅里叶变换，也就是将一个时域上的函数表达，转换为其频域和相位的表示

通过对图片的傅里叶变换，可以根据变化后数据的频率特征，提取图片中的特征

傅里叶变换的目的是可将时域（即时间域）上的信号转变为频域（即频率域）上的信号，随着域的不同，对同一个事物的了解角度也就随之改变，因此在时域中某些不好处理的地方，在频域就可以较为简单的处理

傅里叶变换公式：$F(w)=F[f(t)]={\int }_{-\infty }^{\infty }f(t)e^{-iwt}dt$

其中w代表频率，t代表时间，$e^{-iwt}$为复变函数

从物理角度理解傅里叶变换是以一组特殊的函数（三角函数）为正交基，对原函数进行线性变换，物理意义便是原函数在各组基函数的投影。

1. Fourier Transform

以下内容关于信号与系统课程内容

2. Spectral Graph Theory

下列为课程中符号的说明

• Graph:$G=(V,E),N=|V|$
• $A\in R^{N\times N}$，邻接矩阵/权重矩阵
  • $A_{i,j}=0if{e}_{i.j}\notin E,else{A}_{i,j}=w(i,j)$
• 仅考虑无向图
• $D\in R^{N\times N}$，度矩阵
  • $D_{i,j}=f(x)=\{\begin{array}{l}d(i)ifi=j(sumofrowiinA\\ 0ifi\ne j\end{array}$
• $f:V\to R^N$，图的信号，$f(i)$表示节点i的信号
  

2.1 基础概念介绍

假设上述为城市路网图，函数表示城市的特征
令$L=D-A$，则有L半正定。且L是对称矩阵
对L做如下解析，$L=U\Lambda U^T$

• 其中，$\Lambda =diag({\lambda }_0,\dots ,{\lambda }_{N-1})\in R^{N\times N}$
• $U=[u_0,\dots ,u_{N-1}]\in R^{N\times N}$，正交
  ${\lambda }_l$为频率，$u_l$为${\lambda }_l$对应的basis
  
  上图中，f的各个分量表示对应节点的信号强度，根据上述理论有$L,\Lambda ,U$
  相应的有下图，表中显示了不同频率$\lambda$时，各个节点对应的信号强度$u$
  
  离散区间的傅立叶basis
  其数学公式为$X(k)=DFT[x(n)]={\sum }_{n=0}^{N-1}x(n)e^{-j\frac{2\pi }{N}nk},0\le k\le N-1$
  其中，$x(n)$是时域离散采样序列，N为时域离散采样序列的长度，$X(k)$为频域离散采样序列
  下图为DFT basis，其频率越大，相邻两个节点之间信号变化量越大
  
  Interpreting vertex frequency
  拉普拉斯矩阵是一种对图的操作，若赋予其一个图信号f，则$L_f=(D-A{)}_f=D_f-A_f$，操作如下图
  对于$L_f$的第一个分量a，用${\vec{D}}_1$表示度矩阵D的第一行元素组成的向量，用${\vec{A}}_1$表示邻接矩阵第一行元素组成的向量，则有$a={\vec{D}}_1\cdot f-{\vec{A}}_1\cdot f$
  第一项为节点$v_0$的信号，第二项为节点$v_0$的邻接节点，该分量为$v_0$与其邻接节点的差值的总和

$(L_f)(v_i)={\sum }_{v_j\in V}{w}_{i,j}(f(v_i)-f(v_j))$，其中$w_{i,j}$是邻接矩阵(i,j)位置的元素
$$\begin{gathered} f^T{L}_f={\sum }_{v_i\in V}f(v_i){\sum }_{v_j\in V}{w}_{i,j}(f(v_i)-f(v_j)) \\ ={\sum }_{v_i\in V}{\sum }_{v_j\in V}{w}_{i,j}(f^2(v_i)-f(v_i)f(v_j)) \\ =\frac{1}{2}{\sum }_{v_i\in V}{\sum }_{v_j\in V}{w}_{i,j}(f^2(v_i)-f(v_i)f(v_j)+f^2(v_j)-f(v_j)f(v_i)) \\ =\frac{1}{2}{\sum }_{v_i\in V}{\sum }_{v_j\in V}{w}_{i,j}(f(v_i)-f(v_j){)}^2 \end{gathered}$$
上述公式表达两个节点之间变换的强度，或称图信号的平滑程度
特征向量对应$\lambda$值较小时，其所属的图信号频率越低
如下图中，随着$\lambda$的增大，频率越来越高，相邻两个节点之间的变化强度也随之增大

2.2 信号在谱域与向量域之间的变换

相应的有信号的图傅里叶变换$\hat{x}=U^{T}x$，将信号从向量域转换至谱域/频域
将图结构上的特征转换为不同频率上的信号强度

harmonically related exponentials for periodic signals
周期信号的谐波相关指数$a_{1}cos({\omega }_0{t}_0)+a_{2}cos(2w{\omega }_0{t}_0)+a_{3}cos(3{\omega }_0{t}_0)+\dots$
其目的是将频域中信号转换至时域，即上图中问号的部分，亦是上述过程的反操作
若要确定$t_0$时刻，信号$x(t)$在时域上的信号大小

• 首先，要确定一倍频时$cos({\omega }_0{t}_0)$的大小，其次要确定该频率下对应信号的强度$a_1$
• 随后依次确定各个频率上的相关参数，然后两两相乘
• 最后求和即为该时刻下信号的大小
  
  上述过程是信号系统领域的处理方式，若将其应用在图处理方面，则有如下过程
  已知在各个频率上各个节点对应的信号大小，如在${\lambda }_0$频率下对应节点$v_0$的信号强度为$u_0$的第一个分量乘以$f$
  注：$u_0$的第一个分量对应节点$v_0$在${\lambda }_0$频率下对应的信号大小；整个$u_0$表示所有节点在${\lambda }_0$频率下对应的信号大小
  现在需要做的操作即是各个节点在所有频率上的信号大小求和，得到其在时域上的特征图，即$x=U\hat{x}$
  
  若要将频域上的信号转换至向量域，首先要进行filtering，然后反傅立叶变换
  Filtering
  若在频域上有信号Signal，对于下图中蓝色折线的filter，将两者相乘得到过滤后信号Filtered singal
  
  $$\begin{gathered} y=U\hat{y}=U{g}_{\theta }(\Lambda )U^{T}x \\ =g_{\theta }(U\Lambda U^T)x \\ =g_{\theta }(L)x \end{gathered}$$
  其中$g_{\theta }(\Lambda )$是需要学习的参数
  上式即$y=g_{\theta }(L)x$
  其中$g(\cdot )$可以式任意参数
  例如其为$g_{\theta }(L)=log(1+L),{\lambda }_{max}<1$
  上述部分主要描述了谱域图理论的基础概念，以及从向量域到谱域的傅立叶变换、从谱域到向量域的反傅立叶变换，但该过程中仍存在诸多问题，以下给出问题的描述与ChebNet对这些问题的解决方案

3. 问题的描述与ChebNet的解决方案

3.1 问题描述

对于这种方式有问题1：其复杂度为O(N)，这对于规模较大的图结构数据是难以接受的

另一种情况下，$g_{\theta }(L)=cos(L)$
对于$g_{\theta }(L)=L$，$v_0$无法接收到$v_3$的参数
而对于$g_{\theta }(L)=L^2$，则全部节点可以共享信号
由下列引理3，有对于N个节点的连通图，$L^N$可以保证全部节点之间共享信号

但对于CNN而言，其卷积核仅考虑在感受野范围内的本地信息，若使用上述方式共享信号，那么对于网络而言没有本地信息的概念，即问题2：not localize

3.2 ChebNet

3.2.1 基于ChebNet给出上述两个问题解决方案

$g_{\theta }(L)={\sum }_{k=0}^K{\theta }_k{L}^k$
设置为$L^k$，则其是K-localized，同时其学习的复杂度也是O(K)，这解决了前面提到的两个问题
此时向量域信号的公式如下
$y=U{g}_{\theta }(\Lambda )U^{T}x=U({\sum }_{k=0}^K{\theta }_k{\Lambda }^k)U^{T}x$

3.2.2 问题3的提出与解决

但正如上述公式给出的那样，其将频域/谱域内参数转换至向量域所需进行的计算复杂度为O(N^2)，即问题3
ChebNet对于问题3的解决方案是使用Chebyshev polynomial切比雪夫多项式，该多项式可由L拉普拉斯矩阵递归计算，其公式如下
$T_0(x)=1,T_1(x)=x,T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x),x\in [-1,1]$
对于该模型为了使得变量分布在[-1,1]范围内
令$\tilde{\Lambda }=\frac{2\Lambda }{{\lambda }_{max}}-1,\tilde{\lambda }\in [-1,1]$
经过上述修改后，需要学习的参数变为$g_{{\theta }^{\prime }}(\tilde{\Lambda })={\sum }_{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{\Lambda })$
此时向量域上的信号可以表示为$y=g_{{\theta }^{\prime }}(L)x={\sum }_{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x$
将上述公式展开有$y={\theta }_0^{\prime }{T}_0(\tilde{L})x+{\theta }_1^{\prime }{T}_1(\tilde{L})x+{\theta }_2^{\prime }{T}_2(\tilde{L})x+\cdots +{\theta }_K^{\prime }{T}_K(\tilde{L})x$
若令${\overline{x}}_0=x,{\overline{x}}_1=\tilde{L}x,{\overline{x}}_k=2\tilde{L}{\overline{x}}_{k-1}-{\overline{x}}_{k-2}$
则有$$\begin{gathered} y={\theta }_0^{\prime }{\overline{x}}_0+{\theta }_1^{\prime }{\overline{x}}_1+\cdots +{\theta }_k^{\prime }{\overline{x}}_k \\ =[{\overline{x}}_0,{\overline{x}}_1,\dots ,{\overline{x}}_K][{\theta }_0,{\theta }_1^{\prime },\dots ,{\theta }_K^{\prime }] \end{gathered}$$
对于这种计算方式，设计算${\overline{x}}_k=2\tilde{L}{\overline{x}}_{k-1}-{\overline{x}}_{k-2}$的复杂度为O(E)，则总的复杂度为O(KE)，从而解决了问题3

• ChebNet的计算方式

直观来讲，根据上述方法可以由下图中橙色部分$x_i$确定下图中蓝色部分KaTeX parse error: Double subscript at position 9: g_\theta_̲{i,1}，从而合成出$y_1$，即节点$v_1$在向量域上的信号

3.3 GCN

$y=g_{{\theta }^{\prime }}(L)x={\sum }_{k=0}^K{\theta }_k^{\prime }{T}_k(\tilde{L})x,K=1$
$$\begin{gathered} y=g_{{\theta }^{\prime }}(L)x={\theta }_0^{\prime }x+{\theta }_1^{\prime }\tilde{L}x \\ ={\theta }_0^{\prime }x+{\theta }_1^{\prime }(L-1)x \\ ={\theta }_0^{\prime }x+{\theta }_1^{\prime }(D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}})x \\ =\theta (1+D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}})x \end{gathered}$$

上图中最后部分的$h_v$即是对于在点集V中节点v的输出

4. Tasks, Dataset, and Benchmark

本部分介绍GNN在各个领域中的应用

4.1 Graph Classification

在SuperPixelMNIST或CIFAR10数据集上执行图结构数据分类任务结果如下图
表中显示了数据集的域、名称、图结构数量以及图中节点数量
图中有四组图片，各组中第一张为原图，第二张为包含超像素节点的图结构数据，第三张是使用knn得到的结果。
在原图的基础上进行一定操作得到第二张图，网络要通过处理得到第三张图并根据其进行分类

4.2 Regression&Node Classification

在ZINC分子图数据集上执行回归任务，给定一个分子结构，估计其溶解度
在Stohastic Block数据集上执行节点分类任务。给定一个图模式结构，在图中识别可以匹配该模式的节点组合；半监督节点分类，确定图中各个节点所属类别。

4.3 Edge classification

即旅行商问题，找出经过所有节点且开销最低的一条路径

4.4 Results

1. SuperPixel：在此任务上普通GCN的效果是不如MLP的，但经过优化后的GatedGCN-E*效果相较于GCN有显著提升且效果优于MLP

   • 

2. Regression：结果与在SuperPixel任务中类似

   • 

3. SBM：

   • 

4. TSP

   • 
   • 下图是在不同层下各个模型的效果，需要指出随着模型的增大，效果并没随之上涨，相反在增大到一定程度之后，均有下跌。GCN尤为严重
   • 
   • GCN的feature map在经过一定次数的迭代之后，连通节点的参数会趋于一致。
   • 解决方法是DropEdge，随机丢弃图中的一些边，这同样可以解决over-smoothing的问题
     • over-smoothing在上篇中已经给出解释，此处不在阐述

5. Graph Generation

用于生成图片的传统模型，例如VAE、GAN或是Auto-regressive-based model

6. Summary

• GAT和GCN是最为常用GNN模型
• 尽管GCN是数字驱动的，但通常情况下倾向于忽略其数学细节
• GNN在深层结构下会丢失一些信息
• 大多深度学习模型可以被修改或设计用于图结构数据
• 相关领域的理论分析未来应该被完成
• GNN可以被应用于多种任务

二、实验内容

1. 数据集和问题定义

本次实验的内容为基于分子结构预测物质可溶性，使用pytorch_gerometric进行开发，数据集为pytorch_geometric中的MoleclueNet的ESOL数据集

其中使用SMILES字符串编码表达分子结构，为了处理分子数据，需要安装rdkit。

2. 数据集与数据结构展示

from torch_geometric.datasets import MoleculeNet

data = MoleculeNet(root=".", name="ESOL")
print(data)

print("Dataset type: ", type(data))
print("Dataset features:", data.num_features)
print("Dataset target:", data.num_classes)
print("Dataset sample:", data[0])
print("Dataset Size:", len(data))

上述代码展示了数据集，其中包含1128个分子，每种分子有9个特征，存在734个分类

print(data[0].x)
print(data[0].edge_index.T)
print(data[0].y)

print("Dataset sample smiles:", data[0]["smiles"])

上述代码展示了第一种分子的参数，因输出较长故不作展示。edge_index描述边集

from rdkit import Chem
from rdkit.Chem import Draw

molecule = Chem.MolFromSmiles(data[0]["smiles"])
Draw.MolToFile(molecule, "mol.png")
print(f"Type of molecule: {type(molecule)}") 

上述代码基于SMILES字符串，生成分子式，写入mol.png，即下图

3. 网络框架定义

embedding_size = 64

class GCN(nn.Module):
    def __init__(self):
        # Initialization
        super().__init__()
        torch.manual_seed(42)

        # GCN Layers，第1层网络将特征转化为embedding
        self.initial_conv = GCNConv(data.num_features, embedding_size)
        self.conv1 = GCNConv(embedding_size, embedding_size)
        self.conv2 = GCNConv(embedding_size, embedding_size)
        self.conv3 = GCNConv(embedding_size, embedding_size)

        # output layer，输出是一个线性层，将128维向量转成预测值，该值是个标量，维度和y相同，X2是因为下面要cat两个pooling
        self.out = Linear(embedding_size*2, 1)

    def forward(self, x , edge_index, batch_index):
        # 1st Conv layer
        hidden = self.initial_conv(x, edge_index)
        hidden = torch.tanh(hidden)

        # Other layers
        hidden = self.conv1(hidden, edge_index)
        hidden = torch.tanh(hidden)
        hidden = self.conv2(hidden, edge_index)
        hidden = torch.tanh(hidden)
        hidden = self.conv3(hidden, edge_index)
        hidden = torch.tanh(hidden)

        # Global pooling
        hidden = torch.cat((gmp(hidden, batch_index), gap(hidden, batch_index)), dim=1)

        out = self.out(hidden)

        return out, hidden

model = GCN()
print(model)

输入特征量为9，嵌入量为64。第一层将网络特征转换为embedding，后续接入三个gcn layer，每层后均有tanh激活。torch.cat将最大池化与平均池化两个向量连接在一起，维度变为128。输出层为线性层，将128维向量转换为标量。

4. dataloader

from torch_geometric.loader import DataLoader

loss_fn = torch.nn.MSELoss()
optimizer = torch.optim.Adam(model.parameters(),lr=0.0001)

data_size = len(data)
batch_size = 64
train_loader = DataLoader(data[:int(data_size*0.8)], batch_size=batch_size, shuffle=True)
test_loader = DataLoader(data[int(data_size*0.8):], batch_size=batch_size)

5. training

def train(data):
    for batch in train_loader:
        optimizer.zero_grad()

        pred, embeding = model(batch.x.float(), batch.edge_index, batch.batch)
        loss = torch.sqrt(loss_fn(pred, batch.y))

        loss.backward()
        optimizer.step()

    return loss, embeding

print("Start training ...")
losses = []
for epoch in range(1001):
    loss, h = train(data)
    losses.append(loss)
    if epoch%100 == 0:
        print(f"Epoch {epoch} | Training loss {loss}")

训练过程如下

6. analyzing

import seaborn as sns
import matplotlib.pyplot as plt

losses_float = [float(loss) for loss in losses]
loss_indices = [i for i, l in enumerate(losses_float)]
sns.lineplot(losses_float)
plt.show()

这里使用了seaborn进行数据可视化，效果如下

三、文献阅读

1. 题目

题目：Edgeless-GNN: Unsupervised Representation Learning for Edgeless Nodes

作者：Yong-Min Shin, Student Member, IEEE, Cong Tran, Member, IEEE, Won-Yong Shin, Senior Member, IEEE, and Xin Cao

期刊：IEEE Transactions on Emerging Topics in Computing, doi: 10.1109/TETC.2023.3292240.

2. abstract

Existing GNN networks cannot solve the problem of embedding edgeless nodes because it is impossible for messages to be delivered to edgeless nodes without connections. This paper proposes that Edgeless-GNN can solve the above problems, so that GNN can generate node embeddings for unsupervised learning, and even generate node embeddings for edgeless nodes. The paper also proves the superiority of its network in the edgeless node embedding task and the stability of incomplete node attributes, and the effectiveness of topology-aware loss function.

现有GNN网络无法解决嵌入无边节点的问题，因为消息传递到没有连接的无边节点是不可能。该论文提出了Edgeless-GNN用于解决上述问题，使得GNN能够无监督学习生成节点嵌入，甚至可以为无边节点生成节点嵌入。该论文还证明了其网络在无边节点嵌入任务上的优越性以及对不完整节点属性的稳定性，其感知逻辑的损失函数topology-aware loss function的有效性。

3. 网络架构

在数据预处理阶段，将新增的无边节点、给出的数据集分为两类进行处理。训练过程中，对于其中的无边节点构造代理图，代理图分别在推断过程中表示空间法处理以及作为图的补充在训练过程中。对于数据集中的一般情况直接用GNN处理，但损失函数采用本文中的topology-aware loss function。在推断过程，输入为代理图，首先进一步的扩充代理图，然后经单一前馈处理后用于下游任务。

3.1 问题定义

给定网络$G=(V,E)$和两组节点属性X和X’，无边节点的归纳嵌入旨在以嵌入向量对未知的结构信息和可用的属性信息以无监督编码的方式来生成无边节点中的向量表示。

3.2 GNN结构

在每一层中，GNN模型通过使用两个具有可学习参数的函数聚合其邻居的潜在表示来更新节点的表示。形式上，在GNN的第p层，AGGREGATE§如下聚集计算图$G_c$中节点$v_i$的局部邻域的（潜在）特征信息：
m i p ← A G G R E G A T E ( p ) ( { h j p − 1 ∣ v j ∈ N i ⋃ { v i } } ) m_i^p\leftarrow AGGREGATE^{(p)}(\{h_j^{p-1}|v_j\in N_i\bigcup \{v_i\}\}) mip​←AGGREGATE(p)({hjp−1​∣vj​∈Ni​⋃{vi​}})
其中，$h_j^{p-1}$表示第(p-1)层的节点$v_j$的潜在表示向量，$N_i$表示$G_c$中$v_i$的邻居节点集，$m_i^p$是第p层的聚合信息。

自循环通常被添加到计算图$G_c$中以用于自信息保存。在更新步骤中，通过使用每个节点及其来自AGGREGATE§的聚合信息，生成下一层的潜在表示，如下所示：
$$h_i^p\to UPDAT{E}^{(p)}(h_i^{p-1},m_i^p)$$

于每个节点$v_i$，最初使用节点属性$x_i\in X$作为表示向量(即$h_i^0＝x_i$），并且在最后一层的表示是嵌入向量$z_i$。在本文中，Z表示第i行对应于$z_i$的嵌入矩阵。

3.2.1 GCN中的更新与聚合

$$AGGREGAT{E}_i^{(p)}=\sum _j\frac{1}{\sqrt{degree(i)+1}\sqrt{degree(j)+1}}{h}_j^{p-1}$$

$$UPDAT{E}_i^{(p)}=\sigma (W^p\cdot m_i^p)$$

$\sigma (\cdot )$为激活函数，$degree(\cdot )$为各节点的度

3.2.2 GraphSAGE中的更新与聚合

$$AGGREGAT{E}_i^{(p)}=\frac{1}{degree(i)+1}\sum _j{h}_j^{(p-1)}$$

$$UPDAT{E}_i^{(p-1)}=\sigma (W^p\cdot concat(h_i^{p-1},m_i^p))$$

$concat(\cdot ,\cdot )$是两个输入向量的级联运算，$W_p$是可学习的权重矩阵

3.3 Edgeless-GNN

在GNN的前馈过程中，$G_c$的典型选择是底层网络本身，构造了两个代理图$G_p=(V,E_p)$和$G_p^{all}=(V^{all},E_p^{all}）$，作为GNN的原始计算图$G_c$的替代。代理图$E_p,E_p^{all}$的边是由相同的代理图构造过程创建的，可以将其描述为具有两个输入$f_p(\cdot ,\cdot )$的函数。$f_p(\cdot ,\cdot )$的输入分别包括一个要扩展的计算图（若从头开始构建，则为∅）和一组节点属性。形式上，使用$f_p(\cdot ,\cdot )$来创建$E_p=f_p(\varnothing ,X)$和$E_p^{all}=f_p(G_p,X^{all})$。在框架中，生成的代理图被用作计算图，即在训练期间$G_c=G_p$，在推理期间$G_c=G_p^{all}$。

在训练阶段，代理图$G_p$用于获得V的表示，如下所示：
$$Z=GN{N}_{\theta }(G_p,X,V)$$
其中$GN{N}_{\theta }(\cdot ,\cdot ,\cdot )$的第三个自变量表示要计算感兴趣的节点集。$Z\in R^{N\times d}$的每一行表示V中每个节点的向量表示；d是表示空间的维度；$\theta$表示在Edgeless-GNN中使用的GNN模型的一组模型参数。

$\theta$通过损失函数$L(Z,E)$学习。嵌入式Z通过在根据节点属性构建的$G_p$运行GNN模型来找到，然后通过利用底层网络G中每个节点的网络结构来优化。以这种方式，该模型学习同时使用由$f_p(\cdot ,\cdot )$生成的计算图，合并G的拓扑信息。

在推理阶段，该阶段归纳地找到V’中无边节点的表示。包含无边节点的节点属性集，$X^{all}=X\bigcup X^{\prime }$, 被传递到经过训练的GNN模型以计算$Z^{\prime }\in R^{M\times d}$用于表示无边节点V’通过如下的简单前馈计算：
$$Z^{\prime }=GN{N}_{\theta }(G_p^{all},X^{all},V^{\prime })$$
V’中节点的表示可根据仅用于消息传递所需的感兴趣节点来有效地计算。最后，能够使用Z’执行各种下游任务（即V’中无边节点的嵌入向量）。

选择一个kNN图（kNNG）作为代理图构建函数$f_p(\cdot ,\cdot )$。此外，对于kNNG构造，使用余弦相似性来测量两个节点属性之间的相似性。

4. 文献解读

4.1 Introduction

GNN因其通过消息传递的高表达能力而成为一种成功的图表示学习模型，它通过边交换节点中的潜在信息以获得更丰富的信息。然而，它将相对较少的注意力集中在发现拓扑信息不可用的无边节点的嵌入上。因此需要设计适当的损失函数，通过训练底层GNN模型来精确发现无边缘节点的信息，这并不简单，特别是对于无监督学习的情况。基于上述观点，该论文提出了Edgeless-GNN，使 GNN 能够为属性网络中的无边缘节点生成向量表示，用于执行各种下游任务。

4.2 创新点

1. proxy graph

该论文构建了一个proxy graph，它建立在节点属性之间的相似性之上，这是一种代替原GNN计算图的由给出的网络结构定义的手段。作者注意到，这个新的代理图是在同质假设下生成的，即底层网络中的相邻节点往往具有相似的节点属性。

2. topology-aware loss function

该论文提出了一种拓扑感知损失函数，用于无监督训练模型参数，无需任何节点标签，充分利用已知的网络结构。新损失函数不仅利用了节点对的一阶邻近性，而且还利用了学习节点嵌入中的二阶正关系。这使得模型能够学习给定网络的拓扑结构，同时在代理图中新创建的边上执行消息传递。由于Edgeless-GNN框架是归纳式的，因此可以通过以相同的方式扩展连接有边节点和使用节点属性的无边节点的计算图来直接推断无边节点的表示，以促进 GNN 的前馈过程。

首先生成节点四元组$(v_i,v_j,v_n,v_t)$的多个样本，其中$(v_i,v_j)\in E,(v_i,v_n)\notin E$，且$v_t$是$v_i$的2-hop邻居。然后，将采样的四元组与针对V中的所有节点计算的嵌入式$Z=GN{N}_{\theta }(G_p,X)$一起沿着传递到训练循环中的损失函数中。无监督学习的拓扑感知损失函数：
$$L(Z,E)=L_0(Z,E)+\alpha L_{2nd}(Z,E)$$
其中，$\alpha >0$，该项是在上式中的两个损失项之间平衡的超参数。第一项公式如下
$$L_0(Z,E)=E_{ij}^{+}+D_{in}{E}_{in}^{-}$$
其中，$E_{ij}^{+},E_{in}^{-}$分别表示正节点对$(v_i,v+j)$和负节点对$(v_i,v_n)$的一般能量函数，$D_{in}$公式如下
$$D_{in}=\text{exp}(\frac{\beta }{d_{sp}(v_i,v_n)})$$
$d_{sp}(v_i,v_n)$是$v_i,v_n$之间的最短距离。$\beta >0$，该项是控制负节点对的超参数
$$E_{ij}^{+}=\varphi (sim(z_i,z_j))$$

$$E_{ij}^{-}=\varphi (sim(z_i,z_n))$$

其中$sim(\cdot )$是余弦相似性，对于超参数$\gamma >0和b\ge 0$，$\varphi (x)={\gamma }^{-1}\log (1+exp(-\gamma x+b))$。

$L_{2nd}$公式如下
$$L_{2nd}(Z,E)=J_{it}{E}_{ij}^{+}$$
$J_{it}$为杰卡尔德Jaccard相似度

上图说明了正负节点对与二阶邻近性的节点关系。正节点对和负节点对分别受到吸引力和排斥力。作用于二阶正节点对迫使彼此靠近。

计算损失后，使用梯度下降优化更新模型参数$\theta$。

3. Performance analysis of the framework

分析了Edgeless-GNN框架的计算复杂度，该框架与网络大小呈线性关系。Edgeless-GNN能以即插即用的方式采用各种GNN。此外，与无边节点相比，在处理可以被感知节点时，通过适当选择现有的GNN模型来执行下游任务，因为信息传递可以沿着边进行。

以下是文中对于Edgeless-GNN的计算复杂度为线性的证明过程

Theorem 4.1.EdgelessGNN框架的计算复杂度在k和|V|中至多是线性的。

Proof：GNNs的前馈过程包括AGGREGATE和UPDATE函数的计算，其计算复杂度由$O(2|E||V|)$给出。在EdgelessGNN框架中，选择kNNG作为实现时，计算图中的边数取决于$f_p(\cdot ,\cdot )$。最好的情况是通过在最小化图密度的意义上选择每个节点的k个邻居能够创建所有边，其中生成了$k|V|/2$条边，从而计算复杂度为$\Omega ((k+1)|V|)$。对于最坏的情况，对应边的互斥选择，生成$k|V|$条边；复杂度为$O((2k+1)|V|)$。因此，Edgeless-GNN的计算复杂度最终为$O(k|V|)$，即k和|V|的线性复杂度，这完成了定理4.1的证明。

4.3 实验过程

4.3.1 Datasets

对于所有实验，考虑没有孤立节点的最大连通分量，以确保在推理阶段不会出现没有真实边缘的无边节点。

Cora、Citeseer和Pubmed。每个节点都是来自不同研究主题的出版物，每个节点代表类别标签，如果一个出版物引用了另一个出版物，则存在一条边。

维基百科。 Wiki 数据集是网页网络，其中节点是维基百科中的 Web 文档。

Coauthor-CS。其中节点是作者，如果它们是论文的共同作者，则连接起来。属性矩阵包含每位作者论文中的关键词，类别标签表示每位作者最活跃的研究领域。

4.3.2 Downstream Tasks With Performance Metrics

为了在归纳系统中验证所提出的框架相对于基准方法的性能，考虑三个下游任务并通过五个指标评估性能。链接预测、节点分类和社区检测任务。

链接预测：旨在预测可能存在的边。在研究中，通过计算嵌入式获得重构图${\hat{G}}^{all}$来预测无边节点所关联的边，即${\hat{G}}^{all}=\sigma (Z^{all}{Z}^{all\text{T}})$，其中$\text{T}$表示矩阵的转置。即专注于预测两种类型的边的集合，包括连接V’中两个节点的边以及连接V中一个节点和V’中另一个节点的边。对该任务采用平均精度（AP）和曲线下面积（AUC）评估。

节点分类：旨在将新节点分类到其真实类别中。以监督方式使用一部分节点嵌入式来训练逻辑回归分类器。针对此任务采用$macro-F_1,micro-F_1$评估。

社区检测：旨在无监督地发现社区集合。将标准聚类技术之一的k均值聚类应用于$V^{all}$中所有节点的嵌入式，然后为每个节点分配社区标签以预测新节点的真实社区。采用归一化互信息（NMI）来评估NMI。

4.3.3 Benchmark Methods

DEAL：这种最先进的方法旨在解决归纳链路预测问题。将使用节点属性的MLP编码器和使用单热节点表示的线性编码器生成的嵌入式进行对齐，以学习节点属性和网络结构之间的连接，以便编码器生成链接预测无边节点的score。

Graph2Gauss(G2G)：G2G 模型训练MLP编码器，将每个节点表示为高斯分布，以固定嵌入式中的不确定性因此。

Inference only with node attributes (Att-Only)：作为基线，属性矩阵仅用于推理，即属性矩阵本身被视为节点的嵌入式。

4.3.4 参数设置

选择GraphSAGE作为框架的基础模型。通过Adam优化器训练GNN模型，学习率为0.0005，权重衰减率为0.0005。嵌入空间的维度设置为 64。所有模型均在Python 3.7.7、PyTorch 1.5.1和PyTorch Geometric 1.6中实现。实验在配备 Intel Core i7-9700K 3.60 GHz CPU、32GB RAM和NVIDIA GeForce RTX 2080显卡的机器上运行。在kNNG构造中，所有实验均设置k = 3。将节点集随机分为训练/验证/测试集，比例为85/5/10%。为了模拟的归纳设置，占节点 15% 的验证和测试集被视为新的无边节点，并假设在训练期间未知。使用根据不同数据集和下游任务找到的最佳超参数值。在调整过程中，在指定范围内使用以下超参数值： α ∈ { 2 , 3 , 4 } , b ∈ { 0 , 1 } , β ∈ { 1 , 2 } , γ ∈ { 2 , 3 , 4 } \alpha\in\{2, 3, 4\},b\in\{0, 1\},\beta\in\{1, 2\},\gamma\in\{2, 3, 4\} α∈{2,3,4},b∈{0,1},β∈{1,2},γ∈{2,3,4}。对于每次评估，都会对 10 个不同的训练/验证/测试集进行实验，以计算平均分数。

4.4 结论

研究旨在回答以下六个关键研究问题。

• RQ1：与最先进的归纳无边网络嵌入方法相比，Edgeless-GNN框架对各种下游任务的性能提高了多少？
• RQ2：与现有GNN模型的无边节点变体相比，Edgeless-GNN框架对各种下游任务的性能提高了多少？
• RQ3：模型超参数如何影响Edgeless-GNN框架的性能？
• RQ4：底层 GNN 模型如何影响Edgeless-GNN框架的性能？
• RQ5：Edgeless-GNN框架对节点属性噪声的鲁棒性如何？
• RQ6：Edgeless-GNN框架具有包括图形大小在内的重要参数，其可扩展性如何？

RQ1. Comparison with Benchmark Methods

下表显示了Edgeless-GNN框架与上文中提到的用于归纳网络嵌入的三种基准方法之间的性能比较，涉及所有五个真实数据集且使用了五个性能指标。

1. Edgeless-GNN框架始终优于最先进的方法，除了节点分类和社区检测中的一种情况。对于 Citeseer数据集,Edgeless-GNN获得的$micro-F_1$与DEAL几乎相同，性能差距仅为 0.04%；这表明类标签具有很强的区分性信息，因此额外构建kNNG的收益相对较低。
2. 使用 Wiki 数据集进行节点分类时，Edgeless-GNN与第二佳方法之间的性能差距最大；$Macro-F_1,micro-F_1$的最大改进率分别达到 29.5% 和 12.5%。
3. 在Pubmed和CoauthorCS数据集的链接预测任务上，G2G方法常表现出较差的性能，通常甚至不如Att-Only。
4. 对于给定的数据集，EdgelessGNN相对于基准方法的最高增益往往是在节点分类或社区检测任务中实现的。这是因为表现第二好的DEAL最初是为链接预测任务而设计的。
5. Edgeless-GNN相对于基准方法的性能增益在社区检测任务中高于在节点分类任务中。然而，对于Pubmed数据集，社区检测的总体得分较低，但Att-Only的表现相当不错，这可能表明属性信息与底层网络结构不一致。因此，对于该框架，Pubmed的这种内在特征是不利于性能的因素，因为EdgelessGNN试图通过学习的参数来捕获网络结构。

RQ2. Comparison with Variants of GNN Models for Edgeless Nodes

为了处理无边节点，针对现有GNN模型做出了以下两种基于GraphSAGE的变体

SAGE-kNNG1：该版本采用了GraphSAGE中的损失函数和GNN架构，同时在训练阶段使用底层网络G作为计算图。然而，在推理阶段，由于缺乏无边节点的连通性信息，基于每个无边节点的节点属性$X^{all}$的相似性，通过kNNG构造在现有G基础上生成边，以便与训练好的GraphSAGE模型一起执行消息传递。

SAGE-kNNG2：按照在Edgeless-GNN中的方法，利用节点属性生成的kNNG进行训练和推理。

下表显示了Edgeless-GNN和GNN模型的两种变体在使用所有数据集的五个性能指标方面的性能比较。

从下表(TABLE4)和上表(TABLE3)中，两种kNNG基线方法SAGE-kNNG1和SAGE-kNNG2表现出相当不令人满意的性能，甚至远不如Att-only。这表明仅代理图构建不足以带来令人满意的性能，损失函数的重新设计起着重要作用。与GraphSAGE相比，新设计的损失函数不仅考虑了负节点对之间的最短距离，还考虑了节点对的二阶正关系。因此，该研究表明利用节点对的高阶邻近性对于提高下游任务的性能具有重要意义。

RQ3. Hyperparameter Sensitivity

研究了超参数$\alpha ,\beta ,k$对Edgeless-GNN性能的影响。使用 Cora 和 Citeseer 数据集报告实验结果。

在下图中，根据不同$\alpha$值绘制了下游任务的性能，同时将$\beta ,k$的值分别固定为1和3。

对于Cora数据集，无论下游任务如何，在$\alpha =3$时往往会达到最大值。当$\alpha$超过该值时，二阶邻近效应会过度放大，从而导致嵌入失真。

在Citeseer数据集上观察到类似的趋势；但过度放大的影响不太明显，甚至$Macro-F_1$在$\alpha =4$时实现了最大性能。

在下图中，根据不同的$\beta$值绘制了性能，同时将$\alpha ,k$的值固定为3。

在$\beta >1$的情况下，性能趋于恶化。相反，当$\beta =0$时，性能也会降低。因此，将$\beta$设置为接近1的低值可以获得令人满意的性能。

下表显示了在将$\alpha ,\beta$分别固定为3和1时不同k值的性能。

性能对 k 的值不敏感。由于k的鲁棒性，可以选择相当低的k值（例如k=3）来降低GNN前馈过程中的计算复杂度。

RQ4. Comparative Study Among Various GNN Models

在下图中，使用Cora数据集展示了在Edgeless-GNN框架中使用各种GNN模型的不同下游任务的性能。在实验中，采用了以下三种广泛使用的GNN模型：GCN(Edgeless-GCN)、GraphSAGE(Edgeless-SAGE)和GIN(Edgeless-GIN) 。

对于每个任务，Edgeless-SAGE始终优于其他模型。Edgeless-GCN在链路预测和社区检测方面比Edgeless-GIN表现更好，而在节点分类方面却出现相反的趋势

RQ5. Robustness to Incomplete Node Attributes

在缺少某些节点属性的更实际的体系中评估性能。为此，通过随机屏蔽 { 20 , 40 , 60 , 80 } % \{20, 40, 60, 80\}\% {20,40,60,80}% 的节点属性来创建不完整的属性网络。仅显示 Cora 数据集的结果。缺失的信息被遮蔽为零，表明信息不存在。

EdgelessGNN框架与五种基准方法之间的性能比较如下表所示

研究结果表明，虽然所有方法的性能都会随着缺失节点属性的增加而下降，但EdgelessGNN在所有性能指标下的表现都比其他方法优越。因此即使代理图是使用一组不完整的节点属性构建的，框架对于节点属性的可观察性程度也是鲁棒的。

RQ6. Empirical validation ofthe Complexity analysis

为了凭经验验证定理4.1中所示的复杂性分析，使用Pubmed数据集进行实验，该数据集的节点数量足够大，可以灵活地更改图大小，并假设为全批次设置。

进行了两个实验，分别验证复杂度与节点数量和k值的依赖性。

下图中，图a和图b分别显示了不同|V|和k下测得的运行时间（以秒为单位）。图中还显示了渐近实线，即证明了线性复杂度。

综上，Edgeless-GNN框架可以明显的提升GNN模型在包含无边节点的图结构数据的效能。

小结

本周主要进行了Spectral-Based GNN的学习，但对于傅里叶变换的认识并不足，如果有充分时间将在后续学习中补足。以下简单介绍该部分的内容。
首先简要介绍了信号系统领域傅里叶变换的基础概念。然后基于该概念以及离散傅里叶变换了解了如何将傅里叶变换应用于图结构数据中，即谱域图理论。主要包括谱域与向量域信号以及信号如何在两者之间变换。随后提出了两个使用谱域图理论构造神经网络需要面临的问题，即计算复杂度较大以及非本地信息。基于这两个问题介绍了ChebNet的向量域信号公式，但使用该公式将谱域转换至向量域的计算复杂度较大，即问题3。由此ChebNet根据切比雪夫多项式设计了拉普拉斯矩阵的递归计算。最后一部分简要介绍了GCN。

参考文献

[1] Y. -M. Shin, C. Tran, W. -Y. Shin and X. Cao, “Edgeless-GNN: Unsupervised Representation Learning for Edgeless Nodes,” in IEEE Transactions on Emerging Topics in Computing, doi: 10.1109/TETC.2023.3292240.