The dgl.geometry package contains geometry operations:

  • Farthest point sampling for point cloud sampling

  • Neighbor matching module for graclus pooling


This package is experimental and the interfaces may be subject to changes in future releases.

Farthest Point Sampler

Farthest point sampling is a greedy algorithm that samples from a point cloud data iteratively. It starts from a random single sample of point. In each iteration, it samples from the rest points that is the farthest from the set of sampled points.

class dgl.geometry.farthest_point_sampler(pos, npoints, start_idx=None)[source]

Farthest Point Sampler without the need to compute all pairs of distance.

In each batch, the algorithm starts with the sample index specified by start_idx. Then for each point, we maintain the minimum to-sample distance. Finally, we pick the point with the maximum such distance. This process will be repeated for sample_points - 1 times.

  • pos (tensor) – The positional tensor of shape (B, N, C)

  • npoints (int) – The number of points to sample in each batch.

  • start_idx (int, optional) – If given, appoint the index of the starting point, otherwise randomly select a point as the start point. (default: None)


The sampled indices in each batch.

Return type:

tensor of shape (B, npoints)


The following exmaple uses PyTorch backend.

>>> import torch
>>> from dgl.geometry import farthest_point_sampler
>>> x = torch.rand((2, 10, 3))
>>> point_idx = farthest_point_sampler(x, 2)
>>> print(point_idx)
    tensor([[5, 6],
            [7, 8]])

Neighbor Matching

Neighbor matching is an important module in the Graclus clustering algorithm.

class dgl.geometry.neighbor_matching(graph, e_weights=None, relabel_idx=True)[source]


The neighbor matching procedure of edge coarsening in Metis and Graclus for homogeneous graph coarsening. This procedure keeps picking an unmarked vertex and matching it with one its unmarked neighbors (that maximizes its edge weight) until no match can be done.

If no edge weight is given, this procedure will randomly pick neighbor for each vertex.

The GPU implementation is based on A GPU Algorithm for Greedy Graph Matching

NOTE: The input graph must be bi-directed (undirected) graph. Call dgl.to_bidirected

if you are not sure your graph is bi-directed.

param graph:

The input homogeneous graph.

type graph:


param edge_weight:

The edge weight tensor holding non-negative scalar weight for each edge. default: None

type edge_weight:

torch.Tensor, optional

param relabel_idx:

If true, relabel resulting node labels to have consecutive node ids. default: True

type relabel_idx:

bool, optional


The following example uses PyTorch backend.

>>> import torch, dgl
>>> from dgl.geometry import neighbor_matching
>>> g = dgl.graph(([0, 1, 1, 2], [1, 0, 2, 1]))
>>> res = neighbor_matching(g)
    tensor([0, 1, 1])