Set2Graph: Learning Graphs From Sets

Hadar Serviansky, Nimrod Segol, Jonathan Shlomi, Kyle Cranmer, Eilam Gross, Haggai Maron, Yaron Lipman

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:

  1. Siamese Networks look at pairs of items in isolation, ignoring the global context of the entire set.
  2. 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.
  3. 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

Set2Graph mappings from sets to sets, graphs, and hypergraphs.

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$:

  1. $\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.
  2. $\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)$.
  3. $\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

Abstract

Many problems in machine learning (ML) can be cast as learning functions from sets to graphs, or more generally to hypergraphs; in short, Set2Graph functions. Examples include clustering, learning vertex and edge features on graphs, and learning features on triplets in a collection. A natural approach for building Set2Graph models is to characterize all linear equivariant set-to-hypergraph layers and stack them with non-linear activations. This posses two challenges: (i) the expressive power of these networks is not well understood; and (ii) these models would suffer from high, often intractable computational and memory complexity, as their dimension grows exponentially. This paper advocates a family of neural network models for learning Set2Graph functions that is both practical and of maximal expressive power (universal), that is, can approximate arbitrary continuous Set2Graph functions over compact sets. Testing these models on different machine learning tasks, mainly an application to particle physics, we find them favorable to existing baselines.
BibTeX
@inproceedings{serviansky2020set,
  author = {Hadar Serviansky and Nimrod Segol and Jonathan Shlomi and Kyle Cranmer and Eilam Gross and Haggai Maron and Yaron Lipman},
  title = {{Set2Graph: Learning Graphs From Sets}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=CFOAMkL9Hq},
}
Figure