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(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.

Parameters

  • 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)

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(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.

Parameters

  • graph (DGLGraph) – The input homogeneous graph.

  • edge_weight (torch.Tensor, optional) – The edge weight tensor holding non-negative scalar weight for each edge. default: None

  • relabel_idx (bool, optional) – If true, relabel resulting node labels to have consecutive node ids. default: True

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])