PaperlayerView exact revision on arXiv

Source-linked AI summary

Sign and Basis Invariant Networks for Spectral Graph Representation Learning

Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, Stefanie Jegelka

arXiv:2202.13013v4cs.LGstat.ML

TL;DR

Processing eigenvectors requires invariance to sign flips and, in repeated eigenspaces, arbitrary basis choices. The paper introduces SignNet and BasisNet to enforce these symmetries, proves universality under certain conditions, and reports strong empirical performance across graph and mesh tasks.

  • Problem

    Eigenvector-based models must handle sign ambiguity and the infinitely many basis choices arising in higher-dimensional eigenspaces.

  • Method

    SignNet and BasisNet are neural architectures that impose sign and basis invariance on eigenvector inputs, respectively.

  • Results

    The networks are provably universal under certain conditions and, with Laplacian eigenvectors, go beyond several existing spectral methods and positional encodings while improving performance across evaluated tasks.

  • Takeaways & Limitations

    The architectures provide general invariant processing of eigenvectors for graph representation learning and may extend to other eigenvector-based settings.

  • Takeaways & Limitations

    Experiments cover graph machine learning and one triangle-mesh task, while broader applications and general-subspace settings remain future directions.

Abstract

from arXiv · show

We introduce SignNet and BasisNet -- new neural architectures that are invariant to two key symmetries displayed by eigenvectors: (i) sign flips, since if $v$ is an eigenvector then so is $-v$; and (ii) more general basis symmetries, which occur in higher dimensional eigenspaces with infinitely many choices of basis eigenvectors. We prove that under certain conditions our networks are universal, i.e., they can approximate any continuous function of eigenvectors with the desired invariances. When used with Laplacian eigenvectors, our networks are provably more expressive than existing spectral methods on graphs; for instance, they subsume all spectral graph convolutions, certain spectral graph invariants, and previously proposed graph positional encodings as special cases. Experiments show that our networks significantly outperform existing baselines on molecular graph regression, learning expressive graph representations, and learning neural fields on triangle meshes. Our code is available at https://github.com/cptq/SignNet-BasisNet .

1 INTRODUCTION

Eigenvectors encode rich structural information across graphs and manifolds, but their sign and basis ambiguities complicate neural processing. SignNet and BasisNet address these symmetries with invariant architectures that are universal under certain conditions and improve expressive graph learning.

  • Motivation: Laplacian eigenvectors encode graph and manifold structure and support positional encodings, spectral operations, and graph neural network applications.They capture information such as clusters, subgraph frequencies, and connectivity, while supporting graph Transformers and spectral GNNs.
  • Problem: Eigenvectors are ambiguous because each eigenvector can independently flip sign, while repeated eigenvalues permit infinitely many basis choices within an eigenspace.Prior positional-encoding methods use random sign flips during training, but learning all 2^k sign choices is challenging; general basis invariance is harder still.
  • Contribution: SignNet and BasisNet enforce sign and basis invariance, respectively, and are universal under certain conditions for continuous invariant functions of eigenvectors.With Laplacian eigenvectors, they can go beyond spectral graph convolutions, spectral invariants, and several existing positional encodings.
  • Evaluation: Experiments evaluate the models on molecular graph regression, expressive graph representation learning, and texture reconstruction on triangle meshes.These experiments illustrate empirical benefits attributed to the models’ approximation power and invariances.

2 SIGN AND BASIS INVARIANT NETWORKS

The paper defines the required permutation, sign, and basis symmetries for eigenvector processing, then builds invariant architectures from even functions and orthogonal projectors. SignNet and BasisNet combine these components with neural networks, while Expressive-BasisNet exposes the full universal-approximation regime at impractical computational cost.

  • Symmetries: For symmetric matrices such as normalized graph Laplacians, eigenvectors form orthonormal bases whose processing should respect row permutations and changes of eigenspace basis.Node-output models typically require permutation equivariance, while graph-level outputs may require permutation invariance.
  • Sign invariance: Sign invariance requires f(v1,…,vk)=f(s1v1,…,skvk) for every si∈{−1,1}, capturing all eigenvector ambiguities when eigenvalues are distinct.This is invariance to the product group {−1,1}^k and is a special case of basis invariance.
  • Basis invariance: Basis invariance requires f(V1,…,Vl)=f(V1Q1,…,VlQl) for Qi∈O(di), because any orthonormal basis of an eigenspace can be rotated by an orthogonal matrix.The relevant symmetry group is O(d1)×…×O(dl), with eigenspace counts and dimensions varying across matrices.
  • BasisNet: BasisNet maps an eigenspace basis V to its projector VV^⊤, then applies a permutation-equivariant invariant graph network to the projector.The projector removes dependence on the particular orthonormal basis, while simultaneous row and column permutations preserve node equivariance.
  • Universality: The architectures universally approximate relevant invariant and equivariant functions under stated conditions, including O(d)-invariant maps on compact domains.For multiple eigenspaces, a decomposition theorem reduces product-group invariance to constituent-group invariances, with universality proved for some model instances.
  • SignNet: SignNet processes each eigenvector through the even form φ(vi)+φ(−vi), concatenates the resulting representations, and applies ρ.The constituent networks can be unrestricted, while permutation equivariance can be implemented with architectures such as DeepSets, Transformers, or GNNs.
  • Expressive-BasisNet: Expressive-BasisNet replaces selected components with arbitrary-order invariant graph networks to recover theoretical power, but universal approximation requires O(n^n)-sized intermediate tensors.The paper contrasts this theoretically powerful but computationally impractical variant with the efficiency and expressive power of SignNet and BasisNet.

3 THEORETICAL POWER FOR GRAPH REPRESENTATION LEARNING

SignNet and BasisNet extend spectral graph methods while respecting eigenvector symmetries, including sign flips and basis changes. They can represent spectral convolutions, spectral invariants, and previously proposed graph positional encodings, with stronger graph-discrimination capabilities than some spectral and message-passing baselines.

  • Spectral graph convolutions: SignNet and BasisNet generalize spectral graph convolutions, while BasisNet also covers parametric spectral graph convolutions.Theorem 2 states universal approximation of all spectral graph convolutions by SignNet and all parametric spectral graph convolutions by BasisNet.
  • Spectral graph convolutions: SignNet and BasisNet can distinguish infinitely many pairs of non-isomorphic graphs that spectral graph convolutions or spectral GNNs cannot distinguish.This establishes a strict expressive advantage over those spectral architectures.
  • Spectral invariants: BasisNet universally approximates graph angles, while eigenvalues and graph angles determine short-cycle counts, connectivity, and vertex-wise closed-walk counts.The stated properties include the number of length 3, 4, or 5 cycles and the number of length k closed walks from any vertex to itself.
  • Spectral invariants: Message-passing GNNs cannot express the listed cycle, connectivity, and closed-walk properties, while positional encodings with these networks can go beyond graph angles.Message passing can distinguish all trees, despite the existence of non-isomorphic trees sharing eigenvalues and graph angles.
  • Graph positional encodings: SignNet and BasisNet can approximate many existing graph positional encodings by representing them as spectral convolution matrices or their diagonals.The covered encodings include heat-kernel, random-walk, diffusion, p-step random-walk, generalized PageRank, and landing-probability distance encodings.
  • Graph positional encodings: The framework connects graph positional encodings to shape-analysis descriptors such as heat and wave kernel signatures on triangle meshes.These descriptors are diagonals of spectral convolutions computed from a discrete Laplacian.

4 EXPERIMENTS

Experiments evaluate SignNet across molecular graph regression, graph-property prediction, and mesh texture reconstruction. Across these settings, SignNet improves positional-encoding performance and captures useful structural information while adding modest computational cost.

  • Graph regression: Across four base models on ZINC, SignNet positional encodings achieve the best test MAE, including cases where Laplacian PE with random sign flipping cannot improve over no PE.The best reported model is PNA combined with SignNet, achieving 0.084 test MAE.
  • Graph regression: A non-sign-invariant learned positional encoding reaches 0.148 test MAE, compared with 0.198 for Laplacian PE and 0.121 for fully sign-invariant SignNet.Processing eigenvectors independently reduces the learned sign configurations from 2^k to two, but remains less effective than SignNet.
  • Efficiency: SignNet adds modest computational cost: GatedGCN training time rises from 8.2 to 10.6 seconds per iteration, a 29% increase accompanying over 50% lower test MAE.Eigenvectors are precomputed once; processing all 12,000 ZINC graphs takes 15 seconds.
  • Graph regression: SignNet outperforms domain-agnostic state-of-the-art methods on ZINC and ZINC-full, while its mean score on Alchemy is second best and within one standard deviation of the best.On ZINC, SignNet scores 0.084 versus 0.090 for GNN-LSPE, 0.139 for SAN, and 0.122 for Graphormer.
  • Counting substructures and regressing graph properties: With the same 4-layer GIN base model, SignNet significantly boosts performance on both substructure-counting and graph-property-regression tasks, whereas sign-flip augmentation is less consistent.The evaluated graph properties include connectedness, diameter, and radius.
  • Neural fields on manifolds: On mesh texture reconstruction, SignNet improves over the original Intrinsic NF model and other baselines, especially on the LPIPS perceptual metric, using fewer parameters than the original model.The experiments use 1023 eigenvectors of the cotangent Laplacian on cat and human models.

5 RELATED WORK

Prior graph methods use diverse positional encodings, including Laplacian eigenvectors, but existing eigenvector-based approaches do not fully address basis and sign symmetries.

  • Graph methods use Laplacian eigenvectors as positional encodings for message-passing GNNs and graph-adapted Transformers.
  • Existing Laplacian-eigenvector methods do not address basis invariance and only partially address sign invariance.
  • Other positional encodings derive from random walks, diffusion kernels, shortest paths, or unsupervised node embeddings.

6 CONCLUSION AND DISCUSSION

SignNet and BasisNet provide invariant eigenvector-processing architectures with theoretical universality and empirical benefits across graph and mesh tasks.

  • SignNet and BasisNet are invariant to sign flips and choices of eigenspace bases, respectively.
  • Both architectures are provably universal under certain conditions and can go beyond spectral graph convolutions, spectral invariants, and other positional encodings.
  • Experiments show effective graph positional encodings that improve message passing graph neural network performance.
  • Experiments include graph machine learning tasks and a particular task on triangle meshes, with possible applicability to recommender systems and shape analysis.

A UNIVERSALITY FOR MULTIPLE SPACES

The paper establishes a decomposition-based route to universal invariant architectures, extending SignNet and BasisNet across eigenspace symmetries and matrix settings.

  • Universality: The Decomposition Theorem represents any continuous function invariant to a product group as an aggregation of individually invariant transformations.
  • Universality: Unconstrained-SignNet and Unconstrained-BasisNet represent arbitrary sign- or basis-invariant functions, while Expressive-BasisNet also handles permutation equivariance universally.
  • Universality: Expressive-BasisNet requires high-order tensors for universality under permutation equivariance and includes sign-invariant functions as a special case.
  • Architecture properties: The architectures’ listed properties include permutation equivariance, universality for appropriate invariant functions, and computational tractability.
  • Implementation: Figure 5 integrates SignNet with a GNN prediction model using GIN for φ and an MLP for ρ, processing each eigenvector and its negation independently.
  • Generalizations: The architectures generalize to nonsymmetric diagonalizable matrices and complex eigenvectors, replacing transposes with conjugate transposes in the projector construction.
  • SignNet: For real eigenvectors, arbitrary nonzero scaling is an invariance, which SignNet handles by using unit-normalized vector inputs.
  • BasisNet: Basis invariance for real eigenspaces is expressed through changes of basis ViWi with Wi in GLR(di), and BasisNet uses orthogonal projectors of eigenspaces.

C.1 SIGN AND BASIS AMBIGUITIES IN NUMERICAL EIGENSOLVERS

Numerical eigensolvers can return eigenvectors differing by signs or bases, and real-world graph datasets commonly contain repeated eigenvalues requiring basis-invariant processing.

  • Numerical eigensolvers: Dense symmetric eigensolvers can differ across NumPy and SciPy by choices of eigenvector signs or eigenspace bases, while remaining deterministic within a framework.
  • Numerical eigensolvers: Sparse eigensolver scipy.linalg.eigsh uses a randomly initialized iterative method, so returned eigenvector signs and bases can differ between calls.
  • Real-world graph spectra: Graph datasets frequently contain higher-multiplicity eigenspaces, making basis invariance necessary for symmetry-respecting eigenvector functions.
  • Real-world graph spectra: Higher-multiplicity eigenspaces appear across multi-graph and single-graph datasets, sometimes with dimensions large relative to graph size.
  • Graph symmetries: Graph automorphisms can produce repeated eigenvalues when an automorphism maps an eigenvector to a linearly independent eigenvector with the same eigenvalue.
  • Random-graph limitation: Random Erdős-Rényi graphs typically lack repeated eigenvalues and nontrivial automorphisms, contrasting with the multiplicities observed in real-world graphs.

D.1 CAT MODEL VISUALIZATION

The cat-model visualization shows that SignNet’s learned representations can encode bilateral symmetry and structural patterns distinct from individual Laplacian eigenvectors, while full outputs may remain high-frequency and task-specific.

  • CAT MODEL VISUALIZATION: SignNet’s learned φ(v) + φ(−v) representation encodes bilateral symmetry, assigning similar values to the cat’s left and right feet.Some eigenvectors distinguish the two feet, whereas this learned component does not.
  • CAT MODEL VISUALIZATION: The full SignNet output has high-frequency principal components that appear close to the texture reconstruction target.The authors suggest structurally interpretable mappings may emerge when training across multiple models.
  • CAT MODEL VISUALIZATION: On ZINC, SignNet learns positional-encoding components associated with min-cuts and appendage atoms that qualitatively differ from single graph eigenvectors.The model uses GIN for φ, an MLP for ρ, summation over eigenvectors, and all eigenvectors as input.
  • CAT MODEL VISUALIZATION: SignNet’s learned positional encodings on fluorescein do not exactly match any individual Laplacian eigenvector.The visualization compares all normalized Laplacian eigenvectors with principal components of the learned encodings.

G PROOFS OF UNIVERSALITY

The proofs establish exact sign-invariant representations through symmetrization and basis-invariant representations through orthogonal projectors, with permutation-equivariant approximation supplied by invariant graph networks.

  • Universal Representation: A continuous sign-invariant function can be represented as h(v) = φ(v) + φ(−v), and permutation equivariance is preserved when φ is permutation equivariant.The converse uses φ(v) = h(v)/2.
  • Universal Representation: A continuous O(d)-invariant function of V can be written as h(V) = φ(VV^T), because VV^T is unchanged by right multiplication with orthogonal matrices.This converts basis-invariant processing into processing the orthogonal projector onto V’s column space.
  • Universal Approximation: On compact domains, invariant graph networks universally approximate continuous O(d)-invariant and permutation-equivariant functions through the representation V ↦ IGN(VV^T).The proof factors the target through the projector and invokes universal approximation for invariant graph networks.

G.1 PROOF OF DECOMPOSITION THEOREM

The decomposition proof factors invariant functions through per-input quotient embeddings and a continuous shared function, yielding the basis for universal SignNet and BasisNet representations and approximations under compactness assumptions.

  • G.1 PROOF OF DECOMPOSITION THEOREM: The theorem assumes continuous group actions and Euclidean embeddings of quotient spaces; these conditions hold for finite or compact matrix groups and can follow from Whitney embedding.Invariant-polynomial embeddings also apply when the base space is Euclidean and the group is a finite or compact matrix Lie group.
  • G.1 PROOF OF DECOMPOSITION THEOREM: The Decomposition Theorem factors any continuous product-space invariant function as f(v1, …, vk) = ρ(φ1(v1), …, φk(vk)).Each φi is invariant to its corresponding group action, and identical spaces with identical groups can share the same φi.
  • G.1 PROOF OF DECOMPOSITION THEOREM: The proof identifies the quotient of a product action with the product of quotient spaces, then embeds each quotient into Euclidean space.Compactness is preserved through quotienting, embedding, and finite products.
  • G.2 SIGN INVARIANT UNIVERSAL REPRESENTATION: SignNet universally represents continuous sign-invariant functions on k unit eigenvectors using shared φ outputs symmetrized by sign reversal and a continuous ρ.The unit-sphere domain is compact, and the sign quotient is real projective space.
  • G.2 SIGN INVARIANT UNIVERSAL REPRESENTATION: With additional compact features, SignNet extends the same representation by applying φ to each eigenvector-feature pair and symmetrizing only the eigenvector.The feature-aware representation uses ψ: R^(n+d) → R^(2n−2+d).
  • G.2 BASIS INVARIANT UNIVERSAL APPROXIMATION: BasisNet universally represents basis-invariant functions on products of Stiefel manifolds, while permutation-equivariant approximation requires Expressive-BasisNet.The latter approximation is only up to arbitrary ε and is described as impractically expensive.
  • G.2 UNIVERSAL APPROXIMATION: Universal approximation follows when the per-input invariant families and the combining family each universally approximate their respective continuous function classes.The resulting approximation error is bounded by ε in the sup norm.

H.1 SPECTRAL GRAPH CONVOLUTION

SignNet and BasisNet can universally approximate spectral graph convolutions under compactness, while their invariant representations can distinguish graph families that spectral graph convolutions and spectral GNNs cannot.

  • SPECTRAL GRAPH CONVOLUTION: Spectral graph convolutions are sign invariant, but arbitrary eigenvector-specific parameters are not necessarily basis invariant within repeated eigenspaces.If parameters depend only on eigenvalues, equal eigenvalues enforce equal filters and restore basis invariance.
  • SPECTRAL GRAPH CONVOLUTION: SignNet universally approximates spectral graph convolutions, while BasisNet and Expressive-BasisNet universally approximate parametric spectral graph convolutions for compact node-feature domains.Normalized-Laplacian eigenvalues and unit-norm eigenvectors provide the required compactness.
  • SPECTRAL GRAPH CONVOLUTION: The approximation constructs sign-invariant node contributions with φ and aggregates them through a permutation-equivariant sum implemented by ρ.Continuous eigenvalue-dependent filters can be handled by approximating h(λi)viv_i^T X.
  • SPECTRAL GRAPH CONVOLUTION: BasisNet represents eigenspace contributions through h(μ)V V^T X, using invariant projectors and 2-IGN operations for eigenvalue filtering, matrix-vector multiplication, and scalar-vector multiplication.Expressive-BasisNet is stronger than BasisNet and therefore also approximates these functions.
  • EXPRESSIVITY: SignNet and BasisNet can distinguish infinitely many non-isomorphic graph pairs that spectral graph convolutions and spectral GNNs cannot distinguish.The construction uses graphs with the same degree sequence, while SignNet and BasisNet can detect bipartiteness through the largest normalized-Laplacian eigenvalue.
  • EXPRESSIVITY: The graph pairs share degree sequence {3, 2, 2, 2, 1}, causing identical spectral-convolution outputs up to permutation, but differ in bipartiteness detectable from eigenvalue 2.The construction extends to an infinite family by adding nodes while preserving the degree sequence.

H.2 EXISTING POSITIONAL ENCODINGS

SignNet and BasisNet can approximate existing spectral graph convolutions, positional encodings, and graph invariants, including properties that message passing networks cannot distinguish.

  • Spectral graph convolutions: SignNet and BasisNet universally approximate diagonals of spectral graph convolution matrices when eigenvalues lie in a compact set.SignNet handles vector inputs, while BasisNet can approximate the full convolution matrix.
  • Existing positional encodings: SignNet and BasisNet approximate heat-kernel and random-walk node positional encodings, while BasisNet additionally covers diffusion, p-step random-walk, generalized PageRank, and landing-probability distance encodings.These positional encodings are related to spectral graph convolution matrices or their diagonals.
  • Distance encodings: BasisNet can approximate distance-encoding matrices derived from diffusion, p-step random walks, generalized PageRank, and landing probabilities.Shortest-path distances require a discontinuous function that BasisNet cannot learn, although it can learn the inside matrix arguments.
  • Spectral invariants: BasisNet universally approximates graph angles, which determine 3-, 4-, and 5-cycle counts, connectivity, and length-k closed-walk counts.Because these properties are integer-valued, approximation error below 1/2 suffices to distinguish graphs differing in them.
  • Construction: The graph-angle construction computes basis-invariant quantities from eigenspace projectors ViVi^⊤, followed by permutation-equivariant or invariant processing.A 2-IGN computes projector diagonals, while elementwise networks or DeepSets handle subsequent transformations and readouts.
  • Comparison with message passing: Message passing GNNs cannot distinguish a cycle C2k from two disjoint cycles Ck + Ck, so they cannot determine connectivity, certain cycle counts, or length-k closed walks.The graphs have the same number of nodes and every node has degree 2.

J.3 LEARNING SPECTRAL GRAPH CONVOLUTIONS

The spectral graph convolution regression experiments evaluate SignNet and BasisNet against message-passing, spectral GNN, and Transformer baselines on image-derived graphs.

  • Experimental setup: Table 9 reports sum of squared errors over 50 images, with lower values indicating better spectral graph convolution regression.The table has no test set and reports means and standard deviations.
  • Results: SignNet and BasisNet perform strongly with DeepSets and Transformers without message passing, beating spectral GNNs GPR-GNN and ARMA on all tasks.The result validates the theoretical expressivity claims in Section 3.1.
  • Results: SignNet and BasisNet outperform all other methods on band-rejection and comb filters and are mostly close to the best model on the remaining filters.Baselines include message-passing GNNs, spectral GNNs, and Transformers using different treatments of eigenvectors.

K.1 HARDWARE, SOFTWARE, AND DATA DETAILS

The paper uses freely available graph, image, and mesh datasets with PyTorch-based implementations, while evaluating sign-invariant encodings and configuring SignNet and BasisNet for several tasks.

  • Hardware and software: All experiments fit on one GPU at a time, with most runs using a server equipped with 8 NVIDIA RTX 2080 Ti GPUs.Implementations use Python, PyTorch, DGL, and PyTorch Geometric.
  • Data: The datasets include ZINC, Alchemy, synthetic graph-property and substructure datasets, image datasets, and cat and human meshes.The paper states that the data are freely available online.
  • Graph regression: The ZINC experiments use an 8-layer GIN encoder for each eigenvector and an MLP aggregator, with sum aggregation handling variable-sized inputs.The eigenvector is treated as a scalar node feature.
  • Sign ambiguity experiments: On ZINC, random sign flips, absolute eigenvector values, and majority-sign canonicalization are all significantly poorer positional encodings than SignNet.Absolute values create sign invariance but destroy positional information because the transformation is non-injective.
  • Spectral convolution regression: The spectral-convolution node-regression experiments resize images to 32×32, producing 1024-node graphs, and limit every model to 50,000 parameters.Evaluation uses only the 28×28 interior nodes rather than boundary-connected nodes.
  • Texture reconstruction: Texture reconstruction uses the lowest 1023 nontrivial cotangent-Laplacian eigenvectors, with SignNet parameter counts kept no larger than the original model.Both φ and ρ are MLPs in this experiment.
Loading 2202.13013v4…