Introduction
Many problems in machine learning require taking an unordered set of items and predicting the relationships between them. Examples include clustering data points, finding the Delaunay triangulation of a set of 2D points, or reconstructing the origins of particle trajectories in physics simulations.
This paper introduces Set2Graph, a novel and computationally efficient neural network architecture designed to learn mappings from unordered sets of objects to graphs (or hypergraphs). By combining a universal set-to-set model with a simple broadcasting layer and an edge-wise MLP, the authors mathematically prove their model is a universal approximator for equivariant set-to-graph functions, demonstrating state-of-the-art results across diverse tasks.
The Challenge: Equivariance and Complexity
To solve set-to-graph problems, models must be permutation equivariant—meaning if you shuffle the input set, the output graph's nodes must shuffle in the exact same way. Existing approaches have significant flaws:
- Siamese Networks look at pairs of items in isolation, ignoring the global context of the entire set.
- Graph Neural Networks (GNNs) require a pre-existing graph structure (like a K-nearest neighbor graph) to pass messages, which biases the results. Furthermore, standard GNNs are known to lack universal expressive power.
- Fully Equivariant Models that are universal require high-order tensors. This causes memory and computational requirements to explode exponentially, making them intractable for real-world data.
The authors tackle the challenge of building a set-to-graph model that is both computationally tractable and provably universal.
The Set2Graph Architecture
The authors propose a surprisingly simple three-part architecture to map a set of $n$ items to $k$-edges (e.g., $k=2$ for standard graph edges, $k=3$ for triangles). The model is defined as $F^k = \psi \circ \beta \circ \phi$:
- $\phi$ (Set-to-Set Context): The input set is passed through a standard, universal set-to-set model (like DeepSets). This step allows every item to gather global context from the entire set while maintaining permutation equivariance.
- $\beta$ (Broadcasting): A non-learnable layer that constructs candidate edges. For a standard graph ($k=2$), it simply takes the context-rich node features from step 1 and concatenates them for every possible pair $(i, j)$.
- $\psi$ (Edge-wise Processing): A standard Multi-Layer Perceptron (MLP) is applied independently to every concatenated edge feature vector to predict the final edge weight or probability.
The Theoretical Breakthrough: The authors prove that you do not need intractable, high-order tensor operations to achieve universality in set-to-graph problems. This simple composition of low-order operations is mathematically guaranteed to approximate any continuous equivariant set-to-graph function.
Experimental Validation
The authors evaluated their model on three distinct tasks, consistently outperforming baselines:
- Particle Physics (Vertex Reconstruction): Using simulated datasets from the Large Hadron Collider (LHC), the goal is to cluster particle trajectories based on their unobserved point of origin. Set2Graph outperformed all baselines (Siamese, GNNs, and a physics-specific geometric algorithm called AVR) by 5-10% across F1, Rand Index, and Adjusted Rand Index on complex bottom and charm jets.
- Delaunay Triangulation: Given 2D point clouds uniformly sampled in a unit square, the model must predict the valid Delaunay triangulation graph. Set2Graph achieved an F1 score of 0.947, crushing GNNs (~0.74-0.81) and Siamese networks (~0.89-0.91).
- 3D Convex Hull: This task requires predicting which triplets of points form the triangular faces of a 3D point cloud's convex hull (a set-to-3-edge problem). Set2Graph successfully predicted convex hull triangles, achieving AUC-ROCs of 0.97 to 0.99+. To manage the memory efficiency of predicting 3-edges (which normally requires an $N \times N \times N$ tensor), the authors restricted the broadcasting layer ($\beta$) to K-Nearest Neighbor neighborhoods.
Key Insights
- Low-order tensors are enough: While mapping graphs to graphs universally requires heavy, high-order tensors, mapping sets to graphs universally only requires low-order tensors (set-to-set) combined with a simple broadcasting step.
- Global context beats local comparisons: Set2Graph vastly outperforms Siamese networks because its first step ($\phi$) embeds the global context of the entire set into each node before evaluating the edges, leading to much smarter relational predictions.
Limitations and Future Work
Currently, when used for clustering, the model predicts edge probabilities but does not strictly guarantee that the final output forms a mathematically valid clustering (i.e., perfectly disjoint cliques). Adapting the model to enforce this constraint natively is an area for future work.
Additionally, the authors propose a promising future direction: using Set2Graph as an intermediate layer within larger neural networks. By allowing a model to construct a "latent graph" (like a scene graph) from a set of inputs, it could significantly improve reasoning and performance on broader, more complex machine learning tasks.
Summary updated