PyTorch Cluster

---

本包是一个小型扩展库，包含高度优化的图聚类算法，专为 PyTorch 使用而设计。 该包包含以下聚类算法：

• Graclus 算法，源自 Dhillon 等人：无需特征向量的加权图划分：一种多级方法（PAMI 2007）
• 体素网格池化 算法，源自 Simonovsky 和 Komodakis 等人：图卷积神经网络中的动态边条件滤波器（CVPR 2017）
• 迭代最远点采样 算法，源自 Qi 等人：PointNet++：度量空间中点云的深度层次特征学习（NIPS 2017）
• k-NN 和 半径 图生成
• 基于**最近邻** 的聚类
• 随机游走采样 算法，源自 Grover 和 Leskovec 等人：node2vec：可扩展的网络特征学习（KDD 2016）

所有包含的操作均可处理多种数据类型，并且同时支持 CPU 和 GPU。

安装

二进制包

我们为所有主流操作系统、PyTorch 和 CUDA 组合提供了 pip 轮子文件，详情请见 这里。

PyTorch 2.11

要安装适用于 PyTorch 2.11 的二进制包，只需运行：

pip install torch-cluster -f https://data.pyg.org/whl/torch-2.11.0+${CUDA}.html

其中 ${CUDA} 应根据您的 PyTorch 安装情况替换为 cpu、cu126、cu128 或 cu130。

	cpu	cu126	cu128	cu130
Linux	✅	✅	✅	✅
Windows	✅	✅	✅	✅
macOS	✅

PyTorch 2.10

要安装适用于 PyTorch 2.10 的二进制包，只需运行：

pip install torch-cluster -f https://data.pyg.org/whl/torch-2.10.0+${CUDA}.html

其中 ${CUDA} 应根据您的 PyTorch 安装情况替换为 cpu、cu126、cu128 或 cu130。

	cpu	cu126	cu128	cu130
Linux	✅	✅	✅	✅
Windows	✅	✅	✅	✅
macOS	✅

PyTorch 2.9

要安装适用于 PyTorch 2.9 的二进制包，只需运行：

pip install torch-cluster -f https://data.pyg.org/whl/torch-2.9.0+${CUDA}.html

其中 ${CUDA} 应根据您的 PyTorch 安装情况替换为 cpu、cu126、cu128 或 cu130。

	cpu	cu126	cu128	cu130
Linux	✅	✅	✅	✅
Windows	✅	✅	✅	✅
macOS	✅

注意： 我们还为 PyTorch 1.4.0、1.5.0、1.6.0、1.7.0/1.7.1、1.8.0/1.8.1、1.9.0、1.10.0/1.10.1/1.10.2、1.11.0、1.12.0/1.12.1、1.13.0/1.13.1、2.0.0/2.0.1、2.1.0/2.1.1/2.1.2、2.2.0/2.2.1/2.2.2、2.3.0/2.3.1、2.4.0/2.4.1、2.5.0/2.5.1、2.6.0、2.7.0/2.7.1 以及 2.8.0 提供了旧版本的二进制包（操作步骤相同）。 对于旧版本，您需要明确指定最新支持的版本号，或者使用 pip install --no-index 进行安装，以避免手动从源码编译。 您可以在 这里 查找最新支持的版本号。

从源码安装

请确保已安装至少 PyTorch 1.4.0，并验证 cuda/bin 和 cuda/include 是否分别位于您的 $PATH 和 $CPATH 中，例如：

$ python -c "import torch; print(torch.__version__)"
>>> 1.4.0

$ python -c "import torch; print(torch.__version__)"
>>> 1.1.0

$ echo $PATH
>>> /usr/local/cuda/bin:...

$ echo $CPATH
>>> /usr/local/cuda/include:...

然后运行：

pip install torch-cluster

在没有 NVIDIA 驱动的 Docker 容器中运行时，PyTorch 需要评估计算能力，可能会失败。 在这种情况下，请通过设置 TORCH_CUDA_ARCH_LIST 来指定计算能力，例如：

export TORCH_CUDA_ARCH_LIST = "6.0 6.1 7.2+PTX 7.5+PTX"

功能

Graclus

一种贪心聚类算法，每次选择一个未标记的顶点，并将其与未标记的邻居中边权重最大的顶点配对。 GPU 实现改编自 Fagginger Auer 和 Bisseling：用于贪心图匹配的 GPU 算法（LNCS 2012）

import torch
from torch_cluster import graclus_cluster

row = torch.tensor([0, 1, 1, 2])
col = torch.tensor([1, 0, 2, 1])
weight = torch.tensor([1., 1., 1., 1.])  # 可选的边权重。

cluster = graclus_cluster(row, col, weight)

print(cluster)
tensor([0, 0, 1])

VoxelGrid

一种聚类算法，它在点云上覆盖一个用户定义大小的规则网格，并将位于同一个体素内的点归为一类。

import torch
from torch_cluster import grid_cluster

pos = torch.tensor([[0., 0.], [11., 9.], [2., 8.], [2., 2.], [8., 3.]])
size = torch.Tensor([5, 5])

cluster = grid_cluster(pos, size)

print(cluster)
tensor([0, 5, 3, 0, 1])

FarthestPointSampling

一种采样算法，每次从剩余点集中选取距离其他点最远的点进行采样。

import torch
from torch_cluster import fps

x = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]])
batch = torch.tensor([0, 0, 0, 0])
index = fps(x, batch, ratio=0.5, random_start=False)

print(index)
tensor([0, 3])

kNN-图

计算与最近 k 个点之间的图边。

参数：

• x (Tensor): 节点特征矩阵，形状为 [N, F]。
• k (int): 邻居的数量。
• batch (LongTensor, 可选): 批量向量，形状为 [N]，用于将每个节点分配到特定的示例。batch 需要排序。（默认值：None）
• loop (bool, 可选): 如果为 True，图将包含自环。（默认值：False）
• flow (string, 可选): 与消息传递结合使用时的流动方向（"source_to_target" 或 "target_to_source"）。（默认值："source_to_target"）
• cosine (boolean, 可选): 如果为 True，将使用余弦距离代替欧几里得距离来寻找最近邻。（默认值：False）
• num_workers (int): 用于计算的工作线程数量。如果 batch 不为 None，或者输入位于 GPU 上，则此参数无效。（默认值：1）

import torch
from torch_cluster import knn_graph

x = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]])
batch = torch.tensor([0, 0, 0, 0])
edge_index = knn_graph(x, k=2, batch=batch, loop=False)

print(edge_index)
tensor([[1, 2, 0, 3, 0, 3, 1, 2],
        [0, 0, 1, 1, 2, 2, 3, 3]])

半径-图

计算与给定距离内所有点之间的图边。

参数：

• x (Tensor): 节点特征矩阵，形状为 [N, F]。
• r (float): 半径。
• batch (LongTensor, 可选): 批量向量，形状为 [N]，用于将每个节点分配到特定的示例。batch 需要排序。（默认值：None）
• loop (bool, 可选): 如果为 True，图将包含自环。（默认值：False）
• max_num_neighbors (int, 可选): 每个元素最多返回的邻居数量。如果实际邻居数量超过 max_num_neighbors，则随机选择返回的邻居。（默认值：32）
• flow (string, 可选): 与消息传递结合使用时的流动方向（"source_to_target" 或 "target_to_source"）。（默认值："source_to_target"）
• num_workers (int): 用于计算的工作线程数量。如果 batch 不为 None，或者输入位于 GPU 上，则此参数无效。（默认值：1）

import torch
from torch_cluster import radius_graph

x = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]])
batch = torch.tensor([0, 0, 0, 0])
edge_index = radius_graph(x, r=2.5, batch=batch, loop=False)

print(edge_index)
tensor([[1, 2, 0, 3, 0, 3, 1, 2],
        [0, 0, 1, 1, 2, 2, 3, 3]])

最近邻

将 x 中与 y 中给定查询点最近的点聚类在一起。 batch_{x,y} 向量需要排序。

import torch
from torch_cluster import nearest

x = torch.Tensor([[-1, -1], [-1, 1], [1, -1], [1, 1]])
batch_x = torch.tensor([0, 0, 0, 0])
y = torch.Tensor([[-1, 0], [1, 0]])
batch_y = torch.tensor([0, 0])
cluster = nearest(x, y, batch_x, batch_y)

print(cluster)
tensor([0, 0, 1, 1])

随机游走采样

从由 (row, col) 给出的图中，从 start 中的所有节点索引处采样长度为 walk_length 的随机游走。

import torch
from torch_cluster import random_walk

row = torch.tensor([0, 1, 1, 1, 2, 2, 3, 3, 4, 4])
col = torch.tensor([1, 0, 2, 3, 1, 4, 1, 4, 2, 3])
start = torch.tensor([0, 1, 2, 3, 4])

walk = random_walk(row, col, start, walk_length=3)

print(walk)
tensor([[0, 1, 2, 4],
        [1, 3, 4, 2],
        [2, 4, 2, 1],
        [3, 4, 2, 4],
        [4, 3, 1, 0]])

运行测试

pytest

C++ API

torch-cluster 还提供了一个 C++ API，其中包含了 Python 模型的 C++ 等效实现。

export Torch_DIR=`python -c 'import torch;print(torch.utils.cmake_prefix_path)'`
mkdir build
cd build
# 如需支持 CUDA，可添加 -DWITH_CUDA=on
cmake ..
make
make install

PyTorch Cluster 快速上手指南

torch-cluster 是一个为 PyTorch 设计的高性能图聚类算法扩展库，支持 CPU 和 GPU 加速。它提供了包括 Graclus、体素网格池化（Voxel Grid）、最远点采样（FPS）、k-NN 图构建等常用图神经网络操作。

环境准备

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

• 操作系统: Linux, Windows, 或 macOS
• Python: 3.6+
• PyTorch: 1.4.0 或更高版本（推荐 2.0+）
• CUDA (可选): 如需 GPU 加速，请确保已安装 NVIDIA 驱动，且 cuda/bin 和 cuda/include 已加入环境变量 $PATH 和 $CPATH。

验证 PyTorch 安装：

python -c "import torch; print(torch.__version__)"

安装步骤

方法一：使用预编译二进制包（推荐）

这是最快且最稳定的安装方式。请根据你的 PyTorch 版本和 CUDA 版本选择对应的命令。

注意：请将 ${CUDA} 替换为你的实际环境标识（如 cpu, cu118, cu121 等）。若不确定，可访问 PyG Wheels 查看支持的组合。

PyTorch 2.x 通用安装命令：

pip install torch-cluster -f https://data.pyg.org/whl/torch-2.1.0+${CUDA}.html

示例（PyTorch 2.1 + CUDA 11.8）：

pip install torch-cluster -f https://data.pyg.org/whl/torch-2.1.0+cu118.html

示例（仅 CPU 版本）：

pip install torch-cluster -f https://data.pyg.org/whl/torch-2.1.0+cpu.html

国内加速提示：如果下载速度慢，可在命令前添加国内镜像源参数，例如： pip install ... -i https://pypi.tuna.tsinghua.edu.cn/simple

方法二：从源码安装

如果预编译包不匹配你的环境，可以选择从源码编译。需确保已安装 C++ 编译器和 CUDA Toolkit（如需 GPU）。

pip install torch-cluster

Docker 环境特别说明： 如果在无 NVIDIA 驱动的 Docker 容器中编译，需手动指定计算能力架构：

export TORCH_CUDA_ARCH_LIST="6.0 6.1 7.0 7.5 8.0"
pip install torch-cluster

基本使用

以下展示最常用的 k-NN 图构建 和 最远点采样 (FPS) 功能。

1. 构建 k-NN 图 (k-NN Graph)

根据节点特征矩阵，为每个节点连接距离最近的 $k$ 个邻居。

import torch
from torch_cluster import knn_graph

# 节点特征矩阵 [N, F]
x = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]])
# Batch 向量，表示所有节点属于同一个图
batch = torch.tensor([0, 0, 0, 0])

# 构建 k=2 的最近邻图
edge_index = knn_graph(x, k=2, batch=batch, loop=False)

print(edge_index)
# 输出: tensor([[1, 2, 0, 3, 0, 3, 1, 2],
#               [0, 0, 1, 1, 2, 2, 3, 3]])

2. 最远点采样 (Farthest Point Sampling)

迭代地采样距离已选点集最远的点，常用于点云下采样。

import torch
from torch_cluster import fps

# 点云坐标
x = torch.tensor([[-1., -1.], [-1., 1.], [1., -1.], [1., 1.]])
batch = torch.tensor([0, 0, 0, 0])

# 采样比例为 50%，不从随机点开始
index = fps(x, batch, ratio=0.5, random_start=False)

print(index)
# 输出: tensor([0, 3]) (具体结果可能因实现细节略有不同，但保证分散性)

3. 其他核心功能简述

• Graclus 聚类: graclus_cluster(row, col, weight) - 基于边权重的贪婪图聚类。
• 体素网格池化: grid_cluster(pos, size) - 将点云划分为规则网格进行聚类。
• 半径图构建: radius_graph(x, r, batch) - 连接半径 $r$ 内的所有点。
• 随机游走采样: random_walk(row, col, start, walk_length) - 生成随机游走路径。

所有函数均自动支持 GPU 张量输入，只需将 Tensor 移至 CUDA 设备即可加速计算。