Mapping multisets to vectors
summary
Shows that sum/mean/max pooling with piecewise‑linear nets cannot be reliably injective on continuous features, while analytic (non‑polynomial) activations plus a simple neural layer produce injective embeddings of multisets with output dimension 2N d + 1. Introduces a sorting-based pooling: project to many 1D directions, sort each projection (m ≈ 2D+1), then concatenate; this is injective and yields provable bi‑Lipschitz embeddings with distortion between about √n and n^2. Experiments: better long‑range graph learning and compact point‑cloud models, at the cost of higher runtime.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:05Motivation for multiset functions
- 13:05Injectivity with analytic networks
- 26:25Bi-Lipschitz and sorting methods
- 34:54Multidimensional sorting and GNNs
- 44:12Variable-sized multisets and graphs
- 48:33Experiments with SortMPNN and FSW-GNN
- 51:48Conclusion and future work
- 1:01:00Q&A
related talks
01h 04mRandomized Embeddings and Neural Networks
28mConstructing Informative Features for Discriminative Learning
48mMad Max: Affine Spline Insights into Deep Learning
01h 34mAlgorithmic High-Dimensional Geometry II
37mLinear representations of concepts in modern AI models
34mThe physics of deep learning using tensor networks
49mComputation in Very Wide Neural Networks
56mHow neural networks learns simple functions?