将 t-sne 的结果“捕捉”到常规网格 - 可扩展性问题

Question

我正在尝试使用 t-sne 根据视觉相似性来排列图像，类似于表情符号的这个很酷的示例（来源）：

但 t-sne 的输出只是一个“点云”，而我的目标是在规则的、接近正方形的、密集的网格中显示图像。所以我需要以某种方式将 t-sne 的输出转换为网格上的 (x,y) 位置。

到目前为止，我已经遵循了这篇精彩博客文章中的建议：我将其表述为线性分配问题，以找到常规网格的最佳嵌入。我对结果很满意，例如：

我的问题是“捕捉到网格”阶段是一个巨大的瓶颈，我需要我的方法能够很好地扩展大量图像（10K）。为了解决线性分配问题，我使用 Jonker-Volgenant 算法的 Java 实现，其时间复杂度为 O(n^3)。因此，虽然 t-sne 是 nlogn 并且可以很好地扩展到 10K 图像，但对齐到规则网格的部分最多只能处理 2K 图像。

我认为潜在的解决方案：

1. 从总共 10K 图像中随机采样 2K 图像
2. 将 10K 图像分为 5 份并创建 5 个地图。这是有问题的，因为存在“先有鸡还是先有蛋”的问题，如何做好划分呢？
3. 以准确性换取性能：大约在接近线性的时间内解决线性分配问题。我想尝试这个，但我找不到任何现有的实现可供我使用。
4. 以不同的、更有效的方式实现“对齐网格”部分。

我正在使用 Java，但 cpp 中的解决方案也很好。我想我不是第一个尝试这个的人。有什么建议么？想法？

谢谢！