This work relaxes GNN symmetries to approximate automorphisms, improving model performance.
problem Improving graph neural network performance on asymmetric graphs.
method Formalizing approximate symmetries via graph coarsening, introducing a bias-variance formula.
result Best generalization performance achieved by choosing a larger symmetry group than automorphisms but smaller than permutations.
This paper classifies topological symmetry groups for Petersen family graphs.
problem Understanding symmetries of graphs embedded in 3D space.
method Examined all embeddings of Petersen family graphs in S3 and classified their topological symmetry groups. result Identified all possible groups that can be realized as topological symmetry groups for each graph in the Petersen family.
The symmetries of complex molecular structures can be modeled by the {\em topological symmetry group} of the underlying embedded graph. It is therefore important to understand which topological symmetry groups can be realized by particular abstract graphs. This question has been answered for complete graphs; it is natu…
This paper identifies all topological symmetry groups for Heawood family graphs.
problem Understanding symmetries of spatial graphs in 3D space.
method Analyzing automorphisms of graphs embedded in S3. result All graphs in the Heawood family are intrinsically chiral.
This paper determines all possible topological symmetry groups of generalized Petersen graphs.
problem Identifying all topological symmetry groups of generalized Petersen graphs.
method Analyzing embeddings of generalized Petersen graphs in S3 and considering homeomorphisms. result All groups that can be topological symmetry groups of generalized Petersen graphs are identified.
SA-GFN corrects biases in GFlowNets due to graph symmetries.
problem Systematic biases in state transition probability computations.
method Incorporates symmetry corrections into the learning process through reward scaling.
result Eliminates need for explicit state transition computations.
We characterize all groups which can occur as the topological symmetry group or the orientation preserving topological symmetry group of some embedding of the Petersen graph in S^3.
SymPE breaks symmetries in equivariant networks, improving performance across various tasks.
problem Equivariant networks cannot break symmetries, leading to poor performance in tasks with symmetrical inputs.
method Novel equivariant conditional distributions and randomized canonicalization.
result SymPE significantly improves performance of group-equivariant and graph neural networks.
We classify all groups which can occur as the topological symmetry group of some embedding of the Heawood graph in S3.
In this paper, we compute the graph skein algebra of the punctured disk with two holes. Then, we apply the graph skein techniques developed here to establish necessary conditions for a spatial graph to have a symmetry of order p, where p is a prime. The obstruction criteria introduced here extend some results obtai…
We give a necessary and sufficient condition for the mapping class group of the pair of the 3-sphere and a graph embedded in it to be isomorphic to the topological symmetry group of the embedded graph.
We prove that for every closed, connected, orientable, irreducible 3-manifold, there exists an alternating group A_n which is not the topological symmetry group of any graph embedded in the manifold. We also show that for every finite group G, there is an embedding Γ of some graph in a hyperbolic rational homology 3-sp…
New neural networks learn graph symmetries.
problem Learning from graph data without considering vertex relations.
method Constructs equivariant neural networks to Aut(G) group.
result Characterizes learnable, linear, Aut(G)-equivariant functions.
New equivariant filters improve graph classification.
problem Designing deep learning models for graph symmetries.
method Nonlinear spectral filters (NLSFs) that are equivariant to graph functional shifts.
result NLSFs outperform existing spectral GNNs in graph classification.
Symmetric graphs flow without singularities on their axis.
problem Preserving symmetry in mean curvature flow.
method Weak solution approach, introducing 'vanity', mean curvature flow approximation.
result Singularities occur only on the axis of symmetry.
Graphs of neural networks are represented to preserve symmetry, improving performance across various tasks.
problem Lack of equivariance in neural network representations of other neural networks.
method Represent neural networks as computational graphs and use graph neural networks to preserve permutation symmetry.
result Single model encodes diverse neural architectures, outperforming state-of-the-art methods.
The study examines the stretch factors of outer automorphisms and their latent symmetry.
problem Understanding stretch factors of outer automorphisms in free groups.
method Analyzes the latent symmetry of graphs and uses it to bound stretch factors.
result A precise notion of latent symmetry provides a lower bound on the number of folds required.
We determine for which m, the complete graph Km has an embedding in S3 whose topological symmetry group is isomorphic to one of the polyhedral groups: A4, A5, or S4.
We determine for which n, the complete bipartite graph Kn,n has an embedding in S3 whose topological symmetry group is isomorphic to one of the polyhedral groups: A4, A5, or S4.
This paper bounds min-entropy leakage for Blowfish privacy using graph symmetries.
problem Bounding min-entropy leakage for Blowfish privacy mechanisms.
method Organizing analysis over symmetrical partitions corresponding to orbits of graph automorphism groups.
result Demonstrates a construction meeting the bound with asymptotic equality, showing tightness.
New graph foundation models respect symmetries for broader applicability.
problem Tailored graph machine learning architectures limit broader applicability.
method Investigates symmetries for label and feature permutations, proving network universal approximator.
result Universal approximator on multisets respecting node and feature permutations.
In this review we establish various connections between complex networks and symmetry. While special types of symmetries (e.g., automorphisms) are studied in detail within discrete mathematics for particular classes of deterministic graphs, the analysis of more general symmetries in real complex networks is far less de…
New neural architectures invariant to sign flips and basis symmetries for graph representation learning.
problem Learning invariant graph representations from eigenvectors.
method SignNet and BasisNet neural architectures that are invariant to sign flips and basis symmetries.
result Proven to be universal, approximating any continuous function of eigenvectors with desired invariances.
For each n≤6, we characterize all the groups which can occur as either the orientation preserving topological symmetry group or the topological symmetry group of some embedding of Kn in S3.
We present the concept of the topological symmetry group as a way to analyze the symmetries of non-rigid molecules. Then we characterize all of the groups which can occur as the topological symmetry group of an embedding of the complete graph K_{4r+3} in S^3.
Geometric GNNs improve graph discrimination through GWL.
problem Discriminating geometric graphs embedded in Euclidean space.
method Proposed a geometric version of the Weisfeiler-Leman test (GWL) for geometric graphs.
result Characterized the expressive power of geometric GNNs based on physical symmetries.
Develops SymGCP for tensor decompositions with general symmetry.
problem Handling symmetry in tensor decompositions for better model accuracy.
method Introduces SymGCP, a generalized CP decomposition that accounts for any subset of tensor modes' symmetry.
result SymGCP enables efficient and scalable tensor decomposition with improved model robustness and accuracy.
We classify all groups which can occur as the orientation preserving topological symmetry group of some embedding of a Möbius ladder graph in S3.
The paper tackles learning symmetries in data without expert knowledge.
problem Learning symmetries in data from raw data without prior knowledge.
method Develops methods to select eigenvectors for orthogonal symmetries and compares their effectiveness.
result The problem of learning symmetries is as hard as the graph automorphism problem in the worst case, but can be simplified with certain restrictions.
We characterize which automorphisms of an arbitrary complete bipartite graph Kn,m can be induced by a homeomorphism of some embedding of the graph in S3.
The paper connects link symmetries to finite subgroups of O(3).
problem Understanding symmetries of flat fully augmented links.
method Developed a dictionary linking graph automorphisms to link symmetries, constructing infinite link classes.
result Symmetry groups of b-prime flat fully augmented links match finite subgroups of O(3).
Study G2-manifolds from symplectic SU(3)-manifolds with T2-symmetry.
problem Understanding G2-manifolds from symplectic SU(3)-manifolds. method Cohomological lifting of multi-toric graphs.
result Compact part of G2-moment graph can be obtained cohomologically from the base. Graph Metanetworks process diverse neural architectures efficiently.
problem Processing diverse neural architectures efficiently.
method Builds metanetworks using graph neural networks to process graphs representing input neural networks.
result Proves GMNs are expressive and equivariant to parameter permutation symmetries.
In this paper we complete the classification of topological symmetry groups for complete graphs Kn by characterizing which Kn can have a cyclic group, a dihedral group, or a subgroup of Dm×Dm where m is odd, as its topological symmetry group.
A new graph signature invariant to graph automorphisms.
problem Graph symmetry and feature generation.
method Power spectrum signature derived from squared graph Fourier transform.
result Power spectrum signature is stable under graph perturbations.
An ordered and oriented 2-component link L in the 3-sphere is said to be achiral if it is ambient isotopic to its mirror image ignoring the orientation and ordering of the components. Kirk-Livingston showed that if L is achiral then the linking number of L is not congruent to 2 modulo 4. In this paper we study orientat…
ELD compares graphs by their embedded Laplacian eigenvectors, resolving ambiguities.
problem Comparing graphs of different sizes and structures.
method ELD uses symmetrization and perturbation techniques to compare graph embeddings.
result ELD resolves ambiguities in graph comparisons, making it a natural pseudo-metric.
Study the symmetry and winding numbers of curves defined by sums of exponentials.
problem Understanding the geometry and topology of curves defined by sums of exponentials.
method Analyzing the continuous transition of the graph of the curve as a parameter changes.
result Determined winding numbers and cusp points for curves defined by sums of exponentials.
This article presents a survey of some recent results in the theory of spatial graphs. In particular, we highlight results related to intrinsic knotting and linking and results about symmetries of spatial graphs. In both cases we consider spatial graphs in S3 as well as in other 3-manifolds.
We study recursive-cube-of-rings (RCR), a class of scalable graphs that can potentially provide rich inter-connection network topology for the emerging distributed and parallel computing infrastructure. Through rigorous proof and validating examples, we have corrected previous misunderstandings on the topological prope…
Symmetry in neural networks affects generalization, as shown by CLT and RG transformations.
problem Improving generalization in neural networks by incorporating physical symmetries.
method Evaluation of symmetry constraints and expressivity in MLPs and GNNs using the CLT as a test case.
result Overly complex or overconstrained models generalize poorly, revealing a competition between symmetry constraints and expressivity.
E-NFs generate molecules and their positions while preserving Euclidean symmetries.
problem Generating molecules with their positions while preserving Euclidean symmetries.
method Integrating E(n) graph neural networks into a differential equation to create an invertible equivariant function.
result E-NFs significantly outperform baselines and existing methods in log-likelihood for particle systems and molecules.
We review some recent results in the generic rigidity theory of planar frameworks with forced symmetry, giving a uniform treatment to the topic. We also give new combinatorial characterizations of minimally rigid periodic frameworks with fixed-area fundamental domain and fixed-angle fundamental domain.
It is shown that for any locally knotted edge of a 3-connected graph in S3, there is a ball that contains all of the local knots of that edge and is unique up to an isotopy setwise fixing the graph. This result is applied to the study of topological symmetry groups of graphs embedded in S3.
Frame Averaging makes neural networks invariant or equivariant to new symmetries.
problem Designing neural networks that respect symmetries while being expressive and efficient.
method Introduces Frame Averaging (FA) as a systematic framework to adapt architectures to become invariant or equivariant to new symmetries.
result Frame Averaging guarantees exact invariance or equivariance while being simpler to compute than full group averaging.
New method breaks symmetry in neural networks, improving sample efficiency.
problem Symmetry in neural networks limits their ability to learn unique features.
method Introduces 'relaxed equivariance' to overcome symmetry limitations.
result Equivariant multilayer perceptrons (E-MLPs) can now break symmetry at the sample level.
VDWs enhance graph neural networks for analyzing complex data.
problem Analyzing data on non-Euclidean geometries.
method Incorporating vector diffusion wavelets into geometric graph neural networks.
result VDW-GNNs effectively analyze synthetic and real-world data.
We consider when automorphisms of a graph can be induced by homeomorphisms of embeddings of the graph in a 3-manifold. In particular, we prove that every automorphism of a graph is induced by a homeomorphism of some embedding of the graph in a connected sum of one or more copies of S2×S1, yet there exist au…