dgl.geometry¶
The dgl.geometry
package contains geometry operations:
Farthest point sampling for point cloud sampling
Neighbor matching module for graclus pooling
Note
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
[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 tosample distance. Finally, we pick the point with the maximum such distance. This process will be repeated forsample_points
 1 times. Parameters
 Returns
The sampled indices in each batch.
 Return type
tensor of shape (B, npoints)
Examples
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
[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 bidirected (undirected) graph. Call
dgl.to_bidirected
if you are not sure your graph is bidirected.
 Parameters
Examples
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])
 NOTE: The input graph must be bidirected (undirected) graph. Call