PaperlayerView exact revision on arXiv

Source-linked AI summary

Invariant and Equivariant Graph Networks

Haggai Maron, Heli Ben-Hamu, Nadav Shamir, Yaron Lipman

arXiv:1812.09902v2cs.LGstat.ML

TL;DR

The paper tackles the absence of a full characterization of permutation-invariant and equivariant linear layers for graph and tensor data. It derives complete bases and dimension formulas, showing dimensions of 2 and 15 for edge-value invariants and equivariants, respectively, and establishes approximation of message-passing neural networks. The resulting framework supports graph networks across tensor orders and different graph sizes, while experiments report comparable state-of-the-art performance.

  • Problem

    A full characterization of invariant and equivariant linear layers for graph data was not known, limiting the available maximal bases for symmetry-aware graph networks.

  • Method

    The paper characterizes all permutation-invariant and equivariant linear layers for general tensor inputs and outputs, deriving orthogonal bases and Bell-number dimension formulas.

  • Results

    2 and 15 are the invariant and equivariant layer dimensions for edge-value data, and the model can approximate any message-passing neural network.

  • Takeaways & Limitations

    The constant basis dimensions allow the same network to be applied to graphs of different sizes, with experiments showing comparable state-of-the-art results.

  • Takeaways & Limitations

    Trace generalization did not perform well on unseen graph sizes and may require training on multiple sizes.

Abstract

from arXiv · show

Invariant and equivariant networks have been successfully used for learning images, sets, point clouds, and graphs. A basic challenge in developing such networks is finding the maximal collection of invariant and equivariant linear layers. Although this question is answered for the first three examples (for popular transformations, at-least), a full characterization of invariant and equivariant linear layers for graphs is not known. In this paper we provide a characterization of all permutation invariant and equivariant linear layers for (hyper-)graph data, and show that their dimension, in case of edge-value graph data, is 2 and 15, respectively. More generally, for graph data defined on k-tuples of nodes, the dimension is the k-th and 2k-th Bell numbers. Orthogonal bases for the layers are computed, including generalization to multi-graph data. The constant number of basis elements and their characteristics allow successfully applying the networks to different size graphs. From the theoretical point of view, our results generalize and unify recent advancement in equivariant deep learning. In particular, we show that our model is capable of approximating any message passing neural network Applying these new linear layers in a simple deep neural network framework is shown to achieve comparable results to state-of-the-art and to have better expressivity than previous invariant and equivariant bases.

1 INTRODUCTION

The paper addresses the missing full characterization of permutation-invariant and equivariant linear layers for graph and tensor data. It derives dimension formulas and orthogonal bases, and establishes expressive and practical consequences for graph networks.

  • Problem: Graph learning seeks neural functions mapping graphs or hyper-graphs to targets while respecting node-renumbering symmetries.Scalar outputs should be invariant, whereas tensor outputs should transform equivariantly under node permutations.
  • Problem: Earlier tensor constructions supplied equivariant operators but did not exhaustively characterize all possible linear layers.The paper identifies this incompleteness in prior general tensor and multi-node-set treatments.
  • Characterization: 2 and 15 are the dimensions of invariant and equivariant linear layers for edge-value data, respectively.For order-k graph tensors, the dimensions generalize to the k-th and 2k-th Bell numbers, independent of graph size.
  • Characterization: The paper provides orthogonal bases for invariant and equivariant layers on general tensor data, including multi-node-set and feature or bias extensions.The basis construction supports layers between tensor spaces of potentially different orders.
  • Implications: The constant basis size permits applying the same network to graphs with different numbers of nodes.Experiments focus on single-node-set edge-value data such as adjacency matrices and compare the proposed basis with Hartford et al. (2018).
  • Expressivity: The model can approximate any message-passing neural network, so its universal approximation power is not lower than that of message-passing neural networks.The result is stated for message-passing networks as defined by Gilmer et al. (2017).

2 PREVIOUS WORK

The paper builds on invariant and equivariant neural networks and graph-learning methods. It positions its contribution as extending symmetry-aware parameter sharing to graph and hyper-graph data.

  • Invariant and equivariant learning: Invariant and equivariant networks model functions whose outputs respect symmetries such as translations, rotations, reflections, and permutations.Equivariant layers can be viewed as parameter-sharing schemes determined by the relevant symmetry.
  • Connection: This paper reveals the structure of symmetry-induced parameter sharing for graphs and hyper-graphs.It connects group-based invariant or equivariant networks with deep learning on graph-structured data.
  • Graph learning: Graph neural networks maintain node states and propagate them according to graph structure and learned parametric functions.Subsequent work also explored graph convolution operators inspired by convolutional neural networks.

3 LINEAR INVARIANT AND EQUIVARIANT LAYERS

The paper characterizes permutation-invariant and equivariant linear layers on tensor-valued graph data through fixed-point equations, equality patterns, and Bell-number-sized orthogonal bases.

  • Fixed-point formulation: Permutation invariance and equivariance reduce to fixed-point equations for coefficient matrices under Kronecker powers of permutation matrices.For mixed-order maps R^n^k → R^n^l, equivariance uses the fixed-point condition P^(k+l) vec(L) = vec(L).
  • Orthogonal basis: Equality-pattern classes partition tensor indices according to which positions are equal, and their indicator tensors form an orthogonal basis for the fixed-point solution space.Each class corresponds one-to-one with a partition of the index positions, yielding b(l) basis tensors.
  • Characterization: For order-k tensors, invariant layers have dimension b(k), while equivariant layers have dimension b(2k), independent of node-set size n.The basis elements correspond to partitions of index positions and therefore remain constant in number as graphs change size.
  • Features and biases: The framework also covers constant layers, whose invariant and equivariant components are characterized by the same fixed-point structure.Constant invariant layers are represented by scalar constants, while constant equivariant layers satisfy the corresponding tensor fixed-point equations.
  • Features and biases: Theorem 2 extends the characterization to feature-valued tensors and biases, giving invariant dimension dd′b(k) + d′ and equivariant dimension dd′b(2k) + d′b(k).The feature dimensions are d and d′ for input and output channels, respectively.

4 EXPERIMENTS

Experiments compare the proposed basis with prior bases on synthetic graph functions, test generalization across graph sizes, and evaluate graph classification benchmarks.

  • Implementation: Networks use 1–4 equivariant linear layers with intervening ReLU activations, while invariant models add a max over the invariant basis and 1–3 fully connected layers.The method was implemented in TensorFlow using efficient row, column, and diagonal summation operators.
  • Synthetic datasets: Synthetic experiments target symmetric projection, diagonal extraction, maximal right singular vector, and trace on 40×40 matrices.The first three tasks are equivariant and trace is invariant; datasets contain 10K training and 1K test examples.
  • Synthetic datasets: The proposed basis learns functions such as trace, diagonal, and maximal singular vector that are not learned as effectively with the Hartford et al. (2018) basis.The comparison uses identical networks built from the two bases.
  • Synthetic datasets: The shared row-and-column permutation assumption introduces additional parameters associated with the diagonal and matrix transpose.Hartford et al. (2018) instead considers independently acting row and column permutations.
  • Generalization: Generalization to unseen graph sizes n = 30 and n = 50 is plausible overall, but trace generalization is poor and likely requires training across sizes.The generalization caveat specifically concerns the invariant trace task.
  • Graph classification: The graph-classification evaluation covers eight real-world datasets spanning bioinformatics and social networks, using adjacency matrices and categorical labels.The reported comparison follows a 10-fold evaluation protocol and a fixed three-layer architecture.

5 GENERALIZATIONS TO MULTI-NODE SETS

The framework extends invariant and equivariant layer characterization to tensors defined over multiple node sets. The resulting basis sizes factor across node sets and admit orthogonal bases.

  • Multi-node-set data: The framework handles data on tuples drawn from multiple node sets, with separate permutations acting on each set.Inputs and outputs are tensors indexed by tuples from V1,...,Vm, and reordering is defined using permutation matrices P1,...,Pm.
  • Fixed-point characterization: Invariant and equivariant layers are obtained as solutions to fixed-point equations under the corresponding tensor-product permutation action.The invariant equation is Mvec(L) = vec(L), while the equivariant equation is M ⊗ Mvec(L) = vec(L).
  • Basis dimension: The equivariant multi-node-set basis contains ∏ᵢ b(kᵢ + lᵢ) tensors, where Bell numbers determine the number of index-partition patterns.The basis tensors are linearly independent because their nonzero supports are pairwise disjoint.

APPENDIX A EFFICIENT IMPLEMENTATION OF LAYERS

The paper implements the order-2 equivariant basis using 15 matrix operations. These operations include identity, transpose, diagonal, row and column aggregation, global aggregation, and diagonal replication.

  • Implemented basis: 15 operations span the order-2 equivariant basis and are designed for fast execution.The operations use the all-ones vector 1 ∈ R^n.
  • Basic transformations: Identity and transpose operations preserve A or return A^T, while the diagonal operation extracts and reinstates diagonal values.These provide basic matrix and diagonal transformations within the implemented basis.
  • Row and column aggregation: Row and column sums can be replicated across rows, columns, or the diagonal.The listed operations separately aggregate rows and columns before replication.
  • Global and diagonal aggregation: Global sums and diagonal sums can be replicated across the full matrix or its diagonal, and diagonal entries can be replicated across rows or columns.These operations cover both all-element and diagonal-specific aggregation patterns.
  • Input-structure reductions: For symmetric inputs the basis reduces to 11 elements, and for zero-diagonal symmetric inputs it reduces to 6 elements while remaining more expressive than Hartford et al.'s 4-element basis.Deeper layers may still use the full 15-element basis because intermediate outputs need not retain those input constraints.

APPENDIX B INVARIANT AND EQUIVARIANT SUBSPACE DIMENSIONS

The appendix derives invariant and equivariant subspace dimensions by viewing the layers as fixed points of permutation-group representations. Bell numbers emerge from traces of permutation actions, and the resulting dimensions are independent of graph size.

  • Fixed-point method: A group-averaging projection maps a representation onto its fixed-point subspace, whose dimension equals the projection's trace.This connects invariant-layer dimension counting to representation-theoretic fixed points.
  • Bell-number interpretation: The k-th Bell number equals the k-th moment of the number of fixed points of a uniformly random permutation.This combinatorial interpretation explains why Bell numbers appear in the dimension calculation.
  • Feature dimensions: For feature-augmented order-k tensors, invariant layers have dimension dd′b(k) + d′, while equivariant layers have dimension dd′b(2k) + d′b(k).The formulas account for input and output feature dimensions d and d′.
  • Single-node-set dimensions: The invariant-layer dimension for order-k tensors is b(k), obtained by applying the projection formula to the permutation representation.The proof identifies the solution space of the fixed-point equations with the invariant subspace.
  • Generalization: The same fixed-point approach extends to equivariant layers and multi-node-set data, where tensor-product permutation actions yield the corresponding basis dimensions.The appendix uses trace multiplication and the general representation result to obtain these formulas.

APPENDIX C IMPLEMENTING MESSAGE PASSING WITH OUR MODEL

The model can emulate message passing by representing node, edge, and adjacency information in an order-2 tensor and combining basis operations with MLPs. The resulting construction represents message passing networks to arbitrary precision on compact sets.

  • Neighborhood aggregation: Adjacency-matrix multiplication is mimicked to sum over local neighborhoods, which is the key mechanism for approximating message passing.The paper states that this multiplication can be implemented using the proposed basis.
  • Message passing setup: The construction targets message passing layers using vertex features, adjacency values, and additional edge features.A message passing layer maps input features and edge information to output features through M_t.
  • Tensor representation: The data are encoded in an n × n × (1+l+d) tensor whose channels contain adjacency, edge features, and diagonal feature matrices.This representation places vertex features on diagonal matrices while retaining pairwise edge information.
  • Layer construction: The construction replicates features across rows and columns, applies an MLP to pairwise channels, and uses basis operations to process neighborhood information.These steps create an n × n × (1+l+2d) tensor and transform the message-passing inputs into usable channels.
  • Universality: The model represents any message passing network to arbitrary precision on compact sets.The approximation errors depend on MLP approximation errors, prior errors, uniform bounds, and uniform continuity.
Loading 1812.09902v2…