Fast computation of permutation equivariant layers with the partition algebra

• URL: http://arxiv.org/abs/2303.06208v1
• Date: Fri, 10 Mar 2023 21:13:12 GMT
• Title: Fast computation of permutation equivariant layers with the partition algebra
• Authors: Charles Godfrey, Michael G. Rawson, Davis Brown, and Henry Kvinge
• Abstract summary: Linear neural network layers that are either equivariant or invariant to permutations of their inputs form core building blocks of modern deep learning architectures. Examples include the layers of DeepSets, as well as linear layers occurring in attention blocks of transformers and some graph neural networks.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear neural network layers that are either equivariant or invariant to permutations of their inputs form core building blocks of modern deep learning architectures. Examples include the layers of DeepSets, as well as linear layers occurring in attention blocks of transformers and some graph neural networks. The space of permutation equivariant linear layers can be identified as the invariant subspace of a certain symmetric group representation, and recent work parameterized this space by exhibiting a basis whose vectors are sums over orbits of standard basis elements with respect to the symmetric group action. A parameterization opens up the possibility of learning the weights of permutation equivariant linear layers via gradient descent. The space of permutation equivariant linear layers is a generalization of the partition algebra, an object first discovered in statistical physics with deep connections to the representation theory of the symmetric group, and the basis described above generalizes the so-called orbit basis of the partition algebra. We exhibit an alternative basis, generalizing the diagram basis of the partition algebra, with computational benefits stemming from the fact that the tensors making up the basis are low rank in the sense that they naturally factorize into Kronecker products. Just as multiplication by a rank one matrix is far less expensive than multiplication by an arbitrary matrix, multiplication with these low rank tensors is far less expensive than multiplication with elements of the orbit basis. Finally, we describe an algorithm implementing multiplication with these basis elements.

Related papers

• Symmetry Discovery for Different Data Types [52.2614860099811]
  Equivariant neural networks incorporate symmetries into their architecture, achieving higher generalization performance. We propose LieSD, a method for discovering symmetries via trained neural networks which approximate the input-output mappings of the tasks. We validate the performance of LieSD on tasks with symmetries such as the two-body problem, the moment of inertia matrix prediction, and top quark tagging.
  arXiv  Detail & Related papers  (2024-10-13T13:39:39Z)
• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
  Global Covariance Pooling (GCP) has been demonstrated to improve the performance of Deep Neural Networks (DNNs) by exploiting second-order statistics of high-level representations.
  arXiv  Detail & Related papers  (2024-07-15T07:11:44Z)
• Geometric Clifford Algebra Networks [53.456211342585824]
  We propose Geometric Clifford Algebra Networks (GCANs) for modeling dynamical systems. GCANs are based on symmetry group transformations using geometric (Clifford) algebras.
  arXiv  Detail & Related papers  (2023-02-13T18:48:33Z)
• Connecting Permutation Equivariant Neural Networks and Partition Diagrams [0.0]
  We show that all of the weight matrices that appear in Permutation equivariant neural networks can be obtained from Schur-Weyl duality. In particular, we adapt Schur-Weyl duality to derive a simple, diagrammatic method for calculating the weight matrices themselves.
  arXiv  Detail & Related papers  (2022-12-16T18:48:54Z)
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups [115.58550697886987]
  We provide a completely general algorithm for solving for the equivariant layers of matrix groups. In addition to recovering solutions from other works as special cases, we construct multilayer perceptrons equivariant to multiple groups that have never been tackled before. Our approach outperforms non-equivariant baselines, with applications to particle physics and dynamical systems.
  arXiv  Detail & Related papers  (2021-04-19T17:21:54Z)
• LieTransformer: Equivariant self-attention for Lie Groups [49.9625160479096]
  Group equivariant neural networks are used as building blocks of group invariant neural networks. We extend the scope of the literature to self-attention, that is emerging as a prominent building block of deep learning models. We propose the LieTransformer, an architecture composed of LieSelfAttention layers that are equivariant to arbitrary Lie groups and their discrete subgroups.
  arXiv  Detail & Related papers  (2020-12-20T11:02:49Z)
• Algebraic Neural Networks: Stability to Deformations [179.55535781816343]
  We study algebraic neural networks (AlgNNs) with commutative algebras. AlgNNs unify diverse architectures such as Euclidean convolutional neural networks, graph neural networks, and group neural networks.
  arXiv  Detail & Related papers  (2020-09-03T03:41:38Z)
• Applying Lie Groups Approaches for Rigid Registration of Point Clouds [3.308743964406687]
  We use Lie groups and Lie algebras to find the rigid transformation that best register two surfaces represented by point clouds. The so called pairwise rigid registration can be formulated by comparing intrinsic second-order orientation tensors. We show promising results when embedding orientation tensor fields in Lie algebras.
  arXiv  Detail & Related papers  (2020-06-23T21:26:57Z)
• The general theory of permutation equivarant neural networks and higher order graph variational encoders [6.117371161379209]
  We derive formulae for general permutation equivariant layers, including the case where the layer acts on matrices by permuting their rows and columns simultaneously. This case arises naturally in graph learning and relation learning applications. We present a second order graph variational encoder, and show that the latent distribution of equivariant generative models must be exchangeable.
  arXiv  Detail & Related papers  (2020-04-08T13:29:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.