SimGNN

⠀⠀⠀

一种基于 PyTorch 的 SimGNN：一种用于快速图相似性计算的神经网络方法（WSDM 2019） 实现。

摘要

图相似性搜索是最重要的图应用之一，例如查找与查询化合物最相似的化学化合物。图相似性/距离计算，如图编辑距离（GED）和最大公共子图（MCS），是图相似性搜索及其他许多应用的核心操作，但在实际应用中计算成本非常高。受近年来神经网络方法在节点分类、图分类等图应用中取得成功的启发，我们提出了一种新颖的基于神经网络的方法来解决这一经典但极具挑战性的图问题，旨在减轻计算负担，同时保持良好的性能。所提出的 SimGNN 方法结合了两种策略。首先，我们设计了一个可学习的嵌入函数，将每张图映射为一个嵌入向量，该向量能够提供图的全局摘要信息。此外，我们还提出了一种新的注意力机制，以突出显示与特定相似度度量相关的关键节点。其次，我们设计了一种成对节点比较方法，用细粒度的节点级信息补充图级别的嵌入表示。我们的模型在未见过的图上表现出更好的泛化能力，并且在最坏情况下，其运行时间与两图节点数的平方成正比。以图编辑距离计算为例，在三个真实图数据集上的实验结果表明，我们的方法既有效又高效。具体而言，与一系列基线方法相比，包括多种图编辑距离近似算法以及现有的基于图神经网络的模型，我们的模型不仅误差率更低，而且显著缩短了计算时间。我们的研究提示，SimGNN 为未来图相似性计算和图相似性搜索的研究提供了新的方向。

本仓库提供了论文中描述的 SimGNN 的 PyTorch 实现：

SimGNN：一种用于快速图相似性计算的神经网络方法。 白云生、丁浩、卞松、陈婷、孙义周、王伟。 WSDM, 2019。 [论文]

参考的 TensorFlow 实现可在 [这里] 获取，另一份实现则位于 [这里]。

需求

代码库使用 Python 3.5.2 编写。开发过程中使用的包版本如下：

networkx          2.4
tqdm              4.28.1
numpy             1.15.4
pandas            0.23.4
texttable         1.5.0
scipy             1.1.0
argparse          1.1.0
torch             1.1.0
torch-scatter     1.4.0
torch-sparse      0.4.3
torch-cluster     1.4.5
torch-geometric   1.3.2
torchvision       0.3.0
scikit-learn      0.20.0

数据集

代码从输入文件夹中读取用于训练的图对，每个图对以 JSON 格式存储。用于测试的图对同样以 JSON 文件形式存储。每个节点的 ID 和标签必须从 0 开始编号。字典的键采用字符串形式存储，以便进行 JSON 序列化。

每个 JSON 文件具有以下键值结构：

{"graph_1": [[0, 1], [1, 2], [2, 3], [3, 4]],
 "graph_2":  [[0, 1], [1, 2], [1, 3], [3, 4], [2, 4]],
 "labels_1": [2, 2, 2, 2, 2],
 "labels_2": [2, 3, 2, 2, 2],
 "ged": 1}

键 `graph_1` 和 `graph_2` 对应边列表，用于描述图的连通性结构。类似地，键 `labels_1` 和 `labels_2` 存储每个节点的标签，标签按列表中的位置对应节点标识符。键 `ged` 则包含整数值，表示该图对的原始图编辑距离。

选项

SimGNN 模型的训练由 `src/main.py` 脚本负责，该脚本提供以下命令行参数。

输入输出选项

  --training-graphs   STR    训练图文件夹。默认为 `dataset/train/`。
  --testing-graphs    STR    测试图文件夹。默认为 `dataset/test/`。

模型选项

  --filters-1             INT         第一层 GCN 的滤波器数量。默认为 128。
  --filters-2             INT         第二层 GCN 的滤波器数量。默认为 64。
  --filters-3             INT         第三层 GCN 的滤波器数量。默认为 32。
  --tensor-neurons        INT         张量网络层的神经元数量。默认为 16。
  --bottle-neck-neurons   INT         瓶颈层的神经元数量。默认为 16。
  --bins                  INT         直方图的 bin 数量。默认为 16。
  --batch-size            INT         每批处理的图对数量。默认为 128。
  --epochs                INT         SimGNN 的训练轮数。默认为 5。
  --dropout               FLOAT       Dropout 概率。默认为 0.5。
  --learning-rate         FLOAT       学习率。默认为 0.001。
  --weight-decay          FLOAT       权重衰减。默认为 10^-5。
  --histogram             BOOL        是否包含直方图特征。默认为 False。

示例

以下命令用于训练神经网络并在测试集上进行评分。在默认数据集上训练 SimGNN 模型。

python src/main.py

使用批大小为 512、训练 100 个 epoch 的 SimGNN 模型。

python src/main.py --epochs 100 --batch-size 512

使用直方图特征训练 SimGNN。

python src/main.py --histogram

使用直方图特征并设置较大的 bin 数量训练 SimGNN。

python src/main.py --histogram --bins 32

提高学习率和丢弃率。

python src/main.py --learning-rate 0.01 --dropout 0.9

可以通过添加 --save-path 参数来保存训练好的模型。

python src/main.py --save-path /path/to/model-name

然后可以使用 --load-path 参数加载预训练模型；请注意，加载的模型将按原样使用，不会进行进一步训练。

python src/main.py --load-path /path/to/model-name

---

许可证

• GNU

SimGNN 快速上手指南

SimGNN 是一个基于 PyTorch 实现的图相似度计算神经网络模型，旨在快速估算图编辑距离（GED）。本指南将帮助你快速配置环境并运行模型。

环境准备

在开始之前，请确保你的系统满足以下要求：

• 操作系统: Linux 或 macOS (Windows 需配置相应编译环境)
• Python 版本: 推荐 Python 3.5.2 及以上 (建议直接使用 Python 3.6+ 以获得更好的兼容性)
• 核心框架: PyTorch 1.1.0+
• 主要依赖库:
  • torch-geometric (PyG)
  • networkx
  • numpy, pandas, scipy
  • tqdm, scikit-learn

国内加速建议： 安装 Python 依赖时，推荐使用清华或阿里镜像源以提升下载速度：

pip install -r requirements.txt -i https://pypi.tuna.tsinghua.edu.cn/simple

安装 PyTorch 及相关扩展时，请参考 PyTorch 官网 选择对应的 CUDA 版本命令，或使用国内镜像。

安装步骤

1. 克隆项目代码

   git clone https://github.com/benedekrozemberczki/SimGNN.git
   cd SimGNN
   

2. 安装依赖包 你可以手动安装列出的依赖，或者创建 requirements.txt 后批量安装。以下是基于原文依赖列表的安装命令（已适配国内镜像）：

   pip install networkx==2.4 tqdm==4.28.1 numpy==1.15.4 pandas==0.23.4 texttable==1.5.0 scipy==1.1.0 scikit-learn==0.20.0 -i https://pypi.tuna.tsinghua.edu.cn/simple
   
   # 安装 PyTorch 及其几何扩展 (版本号可根据实际环境调整，此处以原文版本为例)
   pip install torch==1.1.0 torchvision==0.3.0 -i https://pypi.tuna.tsinghua.edu.cn/simple
   pip install torch-scatter==1.4.0 torch-sparse==0.4.3 torch-cluster==1.4.5 torch-geometric==1.3.2 -f https://data.pyg.org/whl/torch-1.1.0+cpu.html
   

   注意：torch-scatter 等扩展库的版本必须与你的 PyTorch 版本及 CPU/CUDA 环境严格匹配。如果上述特定版本安装困难，建议安装最新兼容版本。

基本使用

1. 数据格式说明

模型训练需要成对的图数据，存储为 JSON 文件。每个文件包含两个图的边列表、节点标签以及真实的图编辑距离（GED）。示例结构如下：

{"graph_1": [[0, 1], [1, 2], [2, 3], [3, 4]],
 "graph_2":  [[0, 1], [1, 2], [1, 3], [3, 4], [2, 4]],
 "labels_1": [2, 2, 2, 2, 2],
 "labels_2": [2, 3, 2, 2, 2],
 "ged": 1}

请将训练数据放入 dataset/train/ 目录，测试数据放入 dataset/test/ 目录（或通过参数指定路径）。

2. 运行训练

使用默认配置进行训练和测试：

python src/main.py

3. 常用参数示例

• 自定义训练轮数和批次大小：

  python src/main.py --epochs 100 --batch-size 512
  

• 启用直方图特征：

  python src/main.py --histogram
  

• 保存训练好的模型：

  python src/main.py --save-path /path/to/model-name
  

• 加载预训练模型进行推理（不重新训练）：

  python src/main.py --load-path /path/to/model-name
  

• 调整学习率和 Dropout：

  python src/main.py --learning-rate 0.01 --dropout 0.9