Voronoi Lifting (Pointcloud to Hypergraph)

Description

This lifting builds Voronoi hypergraph based on the given pointcloud through support set sampled with Farthest-Point Sampling (FPS). Formally, Voronoi graph $G = (V, E)$ of point cloud $\mathcal{X}$ based on the support point set $\mathcal{Y}$ is built in following fashion:

$V = \mathcal{X} ∪ \mathcal{Y}$ $E = \{ (x, y) \in \mathcal{X} \times \mathcal{Y} \ | \ argmin_{y \in \mathcal{Y}}(d(x, y)) \ \text{for all} \ x \in \mathcal{X} \}$, where $d(\cdot, \cdot)$ is a distance metric

In this lifting procedure $\mathcal{Y} \subseteq \mathcal{X}$ is sampled via FPS, and $d(\cdot, \cdot)$ is Euclidean distance metric. Since we built a hypergraph instead of a graph there is exactly one hyperedge $H_{y_i}$ for every $y_i \in \mathcal{Y}$ (representing the Voronoi cluster for point $y_i$) and it is defined in the following way:

$H_{y_i} = \{x_0, x_1, ..., x_k, y_i\}$, where $(x_j, y_i) \in E$

Visualization of Voronoi lifting on stanford bunny (each color cluster is a different hyperedge):

Authors & references

This lifting is adapted from Suk et al. LaB-GATr (GitHub repo).

Implemented by team MIA-UT: Julian Suk (@sukjulian), Patryk Rygiel (@PatRyg99)

From https://github.com/pyt-team/challenge-icml-2024/pull/34