GNN

dataset 会包含如下信息:

1. node 信息 (feature, label)
2. edge 信息 (feature, label)
3. graph 信息 (feature, label)
4. connectivity 信息

以上信息中, connectivity 是必需的, 其它数据可能会缺少. 例如:

TUDataset 的 ENZYMES 数据集: 没有 edge 相关的信息, 也没有 graph 的 feature (attribute) 信息, 因为 ENZYMES 数据集主要是通过 node 和 connectivity 信息对 graph 的 label 进行预测

以 TUDataset 的 ENZYMES 数据集为例:

http://www.chrsmrrs.com/graphkerneldatasets/ENZYMES.zip

1. ENZYMES 是一个 `graph focused` 的数据集, 即它是为了对 graph 进行分类. 除此以外,还有 `node focused` (对 node 进行分类)
2. 一个有 600 个 graph, 记为 N
3. graph 分为 6 类, 表示 6 种不同类型的酶 (如裂解酶, 转移酶, 连接酶…)
4. 一共 19580 个 node, 记为 n, node 的 label 表示它是酶的某种组成部分 (可能指的是氨基, 羧基, 羟基等)
5. 一共 74564 条边, 记为 m, 因为每条边用了两条有向边表示, 所以实际是 74564/2 条无向边,

├── ENZYMES_A.txt
├── ENZYMES_graph_indicator.txt
├── ENZYMES_graph_labels.txt
├── ENZYMES_node_attributes.txt
├── ENZYMES_node_labels.txt

from torch_geometric.datasets import Planetoid

dataset = Planetoid(root='/tmp/Cora', name='Cora')
print(f"{len(dataset)} graph")
print(f"{dataset.num_classes} classes")
print(f"{dataset.num_node_features} node features")
print(f"{dataset.num_edge_features} edge features")
print("--- graph[0] ---")
data = dataset[0]
print(f"{data.num_nodes} nodes")
print(f"{data.num_edges} edges")
print(f"x: {data.x.shape} ")
print(f"y: {data.y.shape} ")

1 graph
7 classes
1433 node features
0 edge features
--- graph[0] ---
2708 nodes
10556 edges
x: torch.Size([2708, 1433]) 
y: torch.Size([2708]) 

cora 是 `node focused` (对 node 进行分类)

1. 包含一个 graph
2. 2708 个 node 代表 2708 篇论文
3. node 的 feature[i] 代表是论文是否包含 keywords[i], keywords 一共 1433 个
4. node 的 label 代表论文属于 7 个 class 中哪一个:
   1. Case_Based
   2. Genetic_Algorithms
   3. Neural_Networks
   4. Probabilistic_Methods
   5. Reinforcement_Learning
   6. Rule_Learning
   7. Theory

pytorch-geometric 通过 Data 来封装 graph

• data.x 表示 node 的 feature, [num_nodes, num_node_features]
• data.edge_index, 表示邻接表 [2, num_edges]
• data.edge_attr, 表示 edge feature, [num_edges, num_edge_features]
• data.y 表示 graph label, [1, *] (即 graph focused) 或 node label, [num_nodes, *] (即 node focused)

例如:

import torch
from torch_geometric.data import Data

edge_index = torch.tensor([[0, 1, 1, 2],
                           [1, 0, 2, 1]], dtype=torch.long)

x = torch.tensor([[-1], [0], [1]], dtype=torch.float)
data = Data(x=x, edge_index=edge_index)

使用 TUDataset 解析 tudataset:

from torch_geometric.datasets import TUDataset
dataset = TUDataset(root='/tmp/ENZYMES', name='ENZYMES')
print(f"{len(dataset)} graph")
print(f"{dataset.num_classes} classes")
print(f"{dataset.num_node_features} node features")
print(f"  {dataset.num_node_labels} node labels")
print(f"  {dataset.num_node_attributes} node attributes")
print(f"{dataset.num_edge_features} edge features")
print(f"  {dataset.num_edge_labels} edge labels")
print(f"  {dataset.num_edge_attributes} edge attributes")
print("--- graph[0] ---")
data = dataset[0]
print(f"{data.num_nodes} nodes")
print(f"{data.num_edges} edges")
print(f"first 5 edges: \n{data.edge_index[:,:5]} ")
# data.x 的 shape 为 [:,3], 它是 ndoe label 的 one-hot 编码
print(f"first 5 x:\n{data.x[:5,:]} ")
print(f"y:\n{data.y}")

# TUDataset 的构造函数接受一个 use_node_attr/use_edge_attr 参数, data.x 是否包含
# {node,edge}_attributes.txt 数据
dataset = TUDataset(root='/tmp/ENZYMES', name='ENZYMES', use_node_attr = True)
print("---use_node_attr---")
print(f"{dataset.num_node_attributes} node attributes")
data = dataset[0]
print(f"data.x shape: {data.x.shape[1]}={dataset.num_node_attributes}+3")

600 graph
6 classes
3 node features
  3 node labels
  0 node attributes
0 edge features
  0 edge labels
  0 edge attributes
--- graph[0] ---
37 nodes
168 edges
first 5 edges: 
tensor([[0, 0, 0, 1, 1],
        [1, 2, 3, 0, 2]]) 
first 5 x:
tensor([[1., 0., 0.],
        [1., 0., 0.],
        [1., 0., 0.],
        [1., 0., 0.],
        [1., 0., 0.]]) 
y:
tensor([5])
---use_node_attr---
18 node attributes
data.x shape: 21=18+3

根据 pyg 的 tu_dataset.py 的代码 (torch_geometric/datasets/tu_dataset.py), data.x 实际上是 node label 的 one-hot 编码 (如果使用了 use_node_attr, 还会有 node attribute), data.y 是 graph label. 因为 ENZYMES 数据集主要是根据 node label (氨基,羧基,羟基?) 及其连接关系对 graph 进行分类 (裂解酶, 转移酶, 连接酶…)

model = Net()
data = dataset[0]
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

model.train()
for epoch in range(50):
    optimizer.zero_grad()
    out = model(data)
    loss = F.nll_loss(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()

model.eval()
_, pred = model(data).max(dim=1)
correct = float(pred[data.test_mask].eq(data.y[data.test_mask]).sum().item())
acc = correct / data.test_mask.sum().item()
print('Accuracy: {:.4f}'.format(acc))

Accuracy: 0.7970

如上面的例子所示, gcn 总是针对 node 做 feature 的变换, 它不会改变图的结构. 那如何让它处理 ENZYMES 数据集, 即能输出一个和 node 无关的 global classification?

一种方法是加入一个 global node, 这个 node 和所有 node 相连, 训练时只针对这个 node 计算 loss

另一种方法是用 global pooling, 类似于图片上的 global average pooling, 即把所有的 node 的值平均

GCN Layer (https://arxiv.org/pdf/1609.02907.pdf) 定义了一种简单的 aggregation 的方法

\(\mathbf{x}_{i}^{(k)}=\sum_{j \in \mathcal{N}(i) \cup\{i\}} \frac{1}{\sqrt{\operatorname{deg}(i)} \cdot \sqrt{\operatorname{deg}(j)}} \cdot\left(\mathbf{\Theta}^{\top} \cdot \mathbf{x}_{j}^{(k-1)}\right)\)

• \(\mathbf{x}_{i}^{(k)}\), 表示 node \(i\) 经过第 \(k\) 次 conv 的结果
• \(j \in \mathcal{N}(i) \cup\{i\}\), 表示 \(i\) 和 \(i\) 的所有 neighbour node
• \(\mathbf{\Theta}^{\top} \cdot \mathbf{x}_{j}^{(k-1)}\), \(j\) 先和一个矩阵相乘
• \(\frac{1}{\sqrt{\operatorname{deg}(i)} \cdot \sqrt{\operatorname{deg}(j)}}\), 结果用 \(i\), \(j\) 的 degree 进行 normalize, degree 是指 node 的边数
• \(\sum_{j \in \mathcal{N}(i) \cup\{i\}}\), 最后求和 (或者 max, average)

gcn 在做 aggregation 时可以抽象为以下几步:

1. 前面的 \(\mathbf{\Theta}^{\top} \cdot \mathbf{x}_{j}^{(k-1)}\), 以及计算 degree. 这些处理不需要查找 \(\mathcal{N}(i)\)
2. 查找 \(j \in \mathcal{N}(i)\)
3. 使用 \(x_i^{k-1}\), \(x_j^{k-1}\) 的信息进行计算得到 \(t_i^{k-1}\)
4. 使用 max/sum/average 等针对 \(t_i^{k-1}\) 进行聚合得于 \(x_i^k\)

pyg 通过 MessagePassing 类对上面四步进行了抽象, 使得用户可以把精力放在 1, 3 两步上, 例如 gcn 可以写成:

class GCNConv(MessagePassing):
    def __init__(self, in_channels, out_channels):
        super().__init__(aggr='add')  # "Add" aggregation (Step 5).
        self.lin = torch.nn.Linear(in_channels, out_channels)

    def forward(self, x, edge_index):
        # x has shape [N, in_channels]
        # edge_index has shape [2, E]

        # Step 1: Add self-loops to the adjacency matrix.
        edge_index, _ = add_self_loops(edge_index, num_nodes=x.size(0))

        # Step 2: Linearly transform node feature matrix.
        x = self.lin(x)

        # Step 3: Compute normalization.
        row, col = edge_index
        deg = degree(col, x.size(0), dtype=x.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        deg_inv_sqrt[deg_inv_sqrt == float('inf')] = 0
        norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]

        # Step 4-5: Start propagating messages.
        return self.propagate(edge_index, x=x, norm=norm)

    def message(self, x_j, norm):
        # x_j has shape [E, out_channels]

        # Step 4: Normalize node features.
        return norm.view(-1, 1) * x_j

当用户主动调用 propagate 时, pyg 会自动做类似的动作:

propagate()
  j = neighbour(i)
  temp[j] = message(x[j], ...)
  x[i] = max(temp[j])

forward () 和 message() 相当于需要用户实现的 1, 3 步.

gcn 工作时以整个 graph 为输入 (它甚至包含没有 label 的 node), 并计算每个 node 的特征.

graphsage (Graph SAmple and aggreGatE) 工作时:

1. sample, 以单个 node A 为中心, 通过 k step 采样出固定个数的 node
2. aggregate k 次, 每次用不同的 aggregator.
3. predict 得到 A 的特征

整个过程和 mini-batch SGD 有些类似.

另外, GraphSage 被称为 inductive, 是指在 sample 时会忽略那些没有 label 的 neighbour, 这些 node 的特征和连接关系并不会参与到训练过程.

当 graph 加入一个新的 node 时, 以这个 node 为中心执行一次 graphsage 算法就可以得到 node 的特征. 而 gcn 需要针对新的 graph 重新训练才可以.

https://arxiv.org/pdf/1403.6652.pdf 2014/6

deepwalk 是一种 node embedding 算法

1. 在 graph 上随机 walk, 得到一个 node 序列
2. 在 node 序列上使用 skip-gram 得到 embedding

https://arxiv.org/pdf/1707.05005.pdf 2017/6

graph2vec 是一种 graph embedding 算法