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 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(graph, e_weights=None, relabel_idx=True)[source]ο
Descriptionο
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:
DGLGraph
- 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
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 bi-directed (undirected) graph. Call