Source-linked AI summary
On Learning Sets of Symmetric Elements
Haggai Maron, Or Litany, Gal Chechik, Ethan Fetaya
TL;DR
Learning sets whose elements have their own symmetries remains underexplored despite applications including image deblurring and multi-view recognition. The paper introduces DSS layers, proves their universal approximation and expressivity properties, and reports consistent improvements across diverse tasks and data types.
Problem
Existing set-learning work gives limited attention to sets whose elements themselves obey symmetries, despite applications involving images, graphs, and point-clouds.
Method
DSS layers characterize linear maps equivariant to both element reordering and within-element symmetries while sharing information across set elements.
Results
DSS networks are universal for invariant and equivariant functions, strictly more expressive than Siamese networks, and consistently improve over previous approaches across diverse tasks and data types.
Takeaways & Limitations
DSS provides a unified framework that generalizes DeepSets and several prior architectures for learning sets of symmetric elements.
Takeaways & Limitations
When per-element symmetry transformations may differ, the corresponding equivariant networks are practically reduced to Siamese networks; the theory also assumes universal approximation for general continuous functions.
Abstract
from arXiv · showhide
Learning from unordered sets is a fundamental learning setup, recently attracting increasing attention. Research in this area has focused on the case where elements of the set are represented by feature vectors, and far less emphasis has been given to the common case where set elements themselves adhere to their own symmetries. That case is relevant to numerous applications, from deblurring image bursts to multi-view 3D shape recognition and reconstruction. In this paper, we present a principled approach to learning sets of general symmetric elements. We first characterize the space of linear layers that are equivariant both to element reordering and to the inherent symmetries of elements, like translation in the case of images. We further show that networks that are composed of these layers, called Deep Sets for Symmetric Elements (DSS) layers, are universal approximators of both invariant and equivariant functions, and that these networks are strictly more expressive than Siamese networks. DSS layers are also straightforward to implement. Finally, we show that they improve over existing set-learning architectures in a series of experiments with images, graphs, and point-clouds.
1. Introduction
The paper addresses learning unordered sets whose elements also have intrinsic symmetries, proposing DSS layers that share information across elements while respecting both symmetry types.
- The paper targets sets of symmetric elements, where element order and within-element transformations both define relevant symmetries.
- Siamese architectures process each element independently before fusion, potentially discarding low-level information that intermediate sharing can preserve.
- DSS layers characterize equivariant linear maps for these sets and share information between elements at every layer.
- DSS networks are universal approximators for invariant and equivariant functions and are strictly more expressive than Siamese networks.
- Across image, graph, and point-cloud tasks, DSS layers consistently improve over previous set-learning approaches.
2. Previous work
Prior work developed architectures for unordered sets and for sets of images, using permutation-equivariant processing, Siamese models, view pooling, or specialized equivariant operations.
- Set-learning research proposed permutation-equivariant neural layers followed by pooling, with universal approximation results for invariant functions.
- For multi-view 3D data, earlier methods commonly used Siamese convolutional networks followed by view pooling for classification and segmentation.
- Other multi-view approaches jointly process views with rotation-group convolutions or use mean-removal layers for 3D reconstruction.
- Equivariance has also guided architectures for images, sets, graphs, and other structured data.
3. Preliminaries
The preliminaries define group symmetries and equivariant networks, then frame equivariant-layer design as a parameter-sharing problem that generalizes DeepSets.
- A group G represents transformations of an input, with equivariance preserving the transformation and invariance removing its effect.
- G-equivariant networks compose linear G-equivariant layers with pointwise activations such as ReLU.
- G-invariant networks add an invariant layer and an MLP to an equivariant network.
- Characterizing equivariant layers means finding linear operators that commute with every group element, thereby defining parameter sharing.
- DeepSets gives the permutation-equivariant form λI_n + β11^T and establishes universality for invariant networks built from such layers.
4. DSS layers
DSS layers model sets whose elements have both permutation symmetry across set members and a shared internal symmetry, using equivariant transformations that couple elements at every layer.
- 4.1. Sets with symmetric elements: The symmetry group is G = S_n × H, combining arbitrary reordering of n elements with the same H transformation applied to every element.This framework includes DeepSets, tabular data, and image sets as special cases.
- 4.1. Sets with symmetric elements: When different H transformations may be applied independently to each set element, the corresponding equivariant networks are practically reduced to Siamese networks.This defines a scope boundary for the shared-transformation setup used by DSS layers.
- 4.2. Characterization of equivariant layers: The paper fully characterizes linear G-equivariant layers as the span of two H-equivariant operators, one acting on each element and one on the aggregate of the remaining elements.The proof matches the constructed operator space to the full equivariant space by comparing dimensions.
- 4.2. Characterization of equivariant layers: A DSS layer applies shared H-equivariant operators to each element and to an aggregate of the other elements, enabling information sharing throughout the network.For image sets, this corresponds to convolutions on individual images and on their summed input, followed by summation of the outputs.
- 4.3. Relation to prior work: DSS layers generalize prior image-specific aggregation approaches by applying aggregation at every layer and extending beyond images to arbitrary symmetric elements.The paper also discusses applications to point clouds and graphs.
5. A universal approximation theorem
The paper proves that DSS networks retain universal approximation for invariant and equivariant functions under stated compact-domain conditions. The construction uses shared set descriptors and shows why DSS networks can exceed Siamese architectures in expressivity.
- 5. A universal approximation theorem: A polynomial invariant descriptor can uniquely identify H-orbits, providing the element-level representation needed by the universality construction.The descriptor satisfies u(x) = u(y) exactly when x and y lie in the same H-orbit.
- 5.1. Invariant functions: DSS networks are universal approximators of continuous G-invariant functions on compact domains avoiding the exceptional set E, provided H-invariant networks are universal.The theorem assumes K is G-stable and K ∩ E = ∅.
- 5.1. Invariant functions: The invariant-function proof combines an S_n-invariant aggregate with each element before encoding H-orbits and then constructing a unique invariant descriptor for the set.The shared aggregate preserves relative-position information that would otherwise be lost by independent element processing.
- 5.3. Relation to Siamese networks: DSS networks are strictly more expressive than Siamese networks because omitting the shared aggregate yields the larger wreath-product symmetry, while DSS networks can simulate those architectures.The paper reports that DSS-based architectures perform better than Siamese networks on several tasks.
- 5.2. Equivariant functions: DSS networks are likewise universal approximators of continuous G-equivariant functions under the analogous compact-domain and H-equivariance universality assumptions.The result covers R^(n×d) to R^(n×d) equivariant functions and yields the other output types by reduction.
- 5.3. Examples: The universality results apply to tabular data and sets of images when the corresponding H-invariant and H-equivariant element networks are themselves universal.For image sets, H is the group of circular translations.
6. Experiments
Experiments compare DSS and its variants with established set-learning architectures across classification, selection, and reconstruction tasks involving images, graphs, and point-clouds. Across these settings, early aggregation with DSS generally improves learning, although aggregation choices vary by task.
- Experiments: The evaluation compares DSS with MLP, DeepSets, Siamese, Siamese+DS, and DSS variants using similarly sized models and five random initializations.Reported results are means and standard deviations over the five initializations.
- Classification with multiple measurements: DSS(sum) achieves significantly higher signal-classification accuracy than DeepSets, Siamese, and Siamese+DS, while DSS(Sridhar) fails on this task.The task uses sets of 25 noisy measurements of one-dimensional periodic signals.
- Selection tasks: In frame selection, sum-based early aggregation reaches significantly higher accuracy than late aggregation, DSS(max), and DSS(Aittala), while graph representations slightly improve results over point-clouds for almost all methods.The shape-selection experiments use human-shape sequences represented as point-clouds or graphs.
- Selection tasks: DSS consistently improves highest-quality image selection over Siamese+DS by 1% to 3%.Each input contains 20 degraded images, and the target is the image closest to the original in L1 norm.
- Color-channel matching: Early aggregation significantly outperforms DS+Siamese in color-channel matching and burst deblurring experiments.The comparisons use U-net architectures for color-channel matching and sets of five blurred, noisy images for burst deblurring.
- Summary of experiments: DSS layers improve learning across diverse tasks and data types compared with earlier architectures such as Siamese+DS.The experiments span classification, selection, burst image deblurring, and general equivariant tasks on images, graphs, and point-clouds.
7. Conclusion
The paper presents a principled framework for deep networks on sets of symmetric elements, characterizes their equivariant maps, and demonstrates benefits across diverse tasks and data types.
- The approach characterizes equivariant maps for sets with symmetries, analyzes their expressive power, and improves standard set-learning approaches across multiple tasks and data types.
Supplementary material
The supplementary material extends the characterization of equivariant layers to multiple features, arbitrary products of permutation groups, and related invariant or equivariant outputs.
- For multiple features, any linear G-equivariant layer combines two linear H-equivariant functions, with parameter-space dimension 2E(H)ff′.
- Theorem 5 characterizes layers producing per-element, global, and scalar outputs using sums over set elements followed by H-invariant or H-equivariant functions.
- For products of permutation groups, equivariant bases are formed by tensor products of bases for the component groups, yielding dimension E(H1)·E(H2).
- These bases can be implemented with Kronecker-product identities by applying the component equivariant maps along the corresponding dimensions.
- The supplementary constructions recover the main theorem as a special case when one permutation group is Sn.
C. Equivariant layers for order dependent action
For order-dependent actions that apply different element symmetries to different set members, the relevant group is a semidirect product and its equivariant layers have a shared global interaction term.
- When H acts transitively on element indices, the group combines independent per-element H actions with set permutations through a semidirect product.
- Every linear equivariant layer consists of an H-equivariant per-element map together with a shared global summation term.
- The resulting space of linear equivariant maps has dimension E(H) + 1.
- All off-diagonal blocks share one parameter, whereas diagonal blocks represent the same H-equivariant function.
D.1. Proof of Lemma 1
The proof reduces the dimension of the equivariant-layer space to the null space of a fixed-point equation and evaluates it through a projection operator.
- The dimension of linear G-equivariant layers equals the dimension of the null space solving the fixed-point equation g · L = L.
- The null-space dimension can be obtained by applying the trace function to the projection operator onto that null space.
- The derivation uses the Kronecker-product representation P(g) ⊗ P(g) and multiplicativity of the trace under Kronecker products.
D.2. Proof of Theorem 2
The proof constructs invariant descriptors in stages: first augment each element with a shared sum, then encode element symmetries and set permutations, and finally approximate the resulting composition with equivariant networks.
- Domain assumption: The construction excludes a low-dimensional exceptional set E where the shared sum contains repeated coordinates, although power-sum descriptors can make E smaller.Random noise is noted as one way to move data away from E.
- Descriptor construction: The construction first concatenates each element with the sum of all set elements, producing a representation that can be computed equivariantly.This shared summary is the first stage before applying element-wise invariant encoding.
- Descriptor construction: Applying the element descriptor and then a permutation-invariant polynomial set descriptor yields a G-invariant mapping that is injective on G-orbits.The resulting descriptor therefore distinguishes inputs modulo both element symmetries and set permutations on the stated domain.
- Function decomposition: The target invariant function is written as a composition of the element encoder, set encoder, and a final continuous map on the descriptor space.Compactness and quotient-space arguments establish continuity of the induced maps needed for approximation.
- Network approximation: Universal approximation of the three component maps by equivariant networks gives a uniform approximation of their composition.The proof invokes MLP universality for the final polynomial and continuous maps, while the descriptor stages are implemented with equivariant layers.
- Descriptor construction: An H-invariant polynomial descriptor uniquely identifies each element up to the element symmetry group H.The descriptor satisfies u(x)=u(y) exactly when y is obtained from x by an H action.
E.1. Signal classification experiment
The signal-classification experiment generates noisy sets of replicated one-dimensional signals and compares several set-processing architectures under fixed training protocols.
- Data preparation: The dataset contains 30,000 training examples and 3,000 test and validation examples across sine, rectangular, and saw-tooth signals.Frequencies and amplitudes are sampled from [1, 10], while each example contains 25 noisy copies of one clean signal.
- Data preparation: Signal parameters are randomized over frequency, amplitude, horizontal shift, and vertical shift to form the classification examples.Horizontal shifts use [0, 2π], and vertical shifts use [−5, 5].
- Models and training: The compared models include MLP, Siamese, DSS, max-pooled DSS, Siamese-plus-DeepSets, and DeepSets variants.The listed architectures use different feature widths but are trained under the same general experimental protocol.
- Models and training: Training uses batch size 64, up to 200 epochs, and validation-based early stopping across the listed architectures.Reported training time ranges from 15 minutes for MLP to 5 hours for the DSS(Aittala) variant.
G. Multi-view reconstruction
The multi-view reconstruction experiment tests a DSS-based modification of a mean-subtraction architecture on fixed three-view inputs from three object classes.
- Task: The task predicts a 3D object structure from a set of images by lifting pixels into normalized object-coordinate space.NOCS canonicalizes shape pose and scale, making view aggregation a union operation.
- Architecture: The baseline architecture subtracts the mean of all set elements after each convolutional block, while the DSS modification processes the summed elements with a separate convolution before addition.The paper identifies mean subtraction as a specific DSS-related aggregation variant and tests a corresponding architectural modification.
- Results: The Sridhar+DSS modification significantly improves reconstruction performance for 2 of 3 object classes.The comparison uses cars, airplanes, and chairs under the original experimental settings.
- Evaluation: Results are reported as two-way Chamfer distance multiplied by 100 against the reconstruction ground truth.Table 4 compares the published Sridhar et al. results with the proposed Sridhar+DSS model.