GALA framework learns invariant graph representations via environment augmentation with minimal assumptions.
problem Learning invariant graph representations from different environments without additional assumptions.
method Developed GALA framework with minimal assumptions of variation sufficiency and consistency. Uses an assistant model to differentiate graph environment changes.
result Extracting maximally invariant subgraphs to proxy predictions identifies underlying invariant subgraphs for successful out-of-distribution generalization.
A new method learns graph distributions invariant to node ordering.
problem Graphs are hard to model due to node ordering invariance issues.
method Score-based generative modeling with permutation equivariant graph neural network.
result The method achieves better or comparable graph generation results.
Novel framework improves graph learning for out-of-distribution generalization.
problem Graph out-of-distribution generalization challenges in neural networks.
method Invariant Graph Learning based on Information bottleneck theory (InfoIGL).
result Achieves state-of-the-art performance in graph classification tasks under OOD generalization.
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.
Geometric deep learning predicts knot invariants.
problem Predicting knot invariants from knot data.
method Constructing a functor from knots to graphs and using graph neural networks.
result High generalization capabilities demonstrated.
We propose an end-to-end deep learning learning model for graph classification and representation learning that is invariant to permutation of the nodes of the input graphs. We address the challenge of learning a fixed size graph representation for graphs of varying dimensions through a differentiable node attention po…
IsoGCNs learn invariant and equivariant graph features for efficient simulations.
problem Learning isometric transformation invariant and equivariant features in graphs for simulations.
method Transformation invariant and equivariant Graph Convolutional Networks (IsoGCNs).
result IsoGCNs outperform state-of-the-art methods on geometrical and physical simulation tasks.
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 tra…
Framework tackles OOD challenges in molecule property prediction by modeling environments.
problem Challenges in modeling OOD samples for molecule property prediction.
method Soft causal learning framework incorporating chemistry theories and cross-attention mechanisms.
result Demonstrates well generalization ability on seven datasets.
New invariants distinguish spatial graphs not previously possible.
problem Distinguishing spatial graphs using Dehn colorings.
method Developed vertex-weight invariants based on Dehn colorings.
result Found spatial graphs distinguishable by vertex-weight invariants.
Characterizes graphs with leveled embeddings and introduces new graph invariants.
problem Understanding the properties of leveled embeddings in spatial graphs.
method Characterization of graphs with leveled embeddings, introduction of new invariants.
result Characterization of graphs with low level number and determination of specific invariants for complete graphs and complete bipartite graphs.
A new method recovers latent potentials from graph flows, preserving ordering and stability.
problem Recovering latent potentials from graph flows is ill-posed and standard methods collapse the ordering.
method Gauge-invariant, parameter-insensitive regularization using Dirichlet energy.
result The method preserves ordering and stability across different regularization strengths.
Extends knot concordance invariant to balanced spatial graphs using grid homology.
problem Defining a concordance invariant for balanced spatial graphs.
method Using grid homology to extend the invariant from knots to spatial graphs.
result The combinatorial Υ invariant is a concordance invariant for balanced spatial graphs. We introduce invariants of spatial graphs related to the Wu invariant and the Simon invariant, and apply them to prove that certain graphs are intrinsically chiral, and to obtain lower bounds for the minimal crossing number of embedded graphs.
Graph homomorphism numbers embed graphs for classification.
problem Graph classification using graph homomorphisms.
method Embed graphs into vectors using homomorphism numbers.
result Homomorphism vectors are universal for approximating graph invariants.
Proposes local coordinate frames for improving model performance in complex dynamical systems.
problem Improving model performance in complex, non-linear, and time-dependent dynamical systems.
method Introduces roto-translation invariant local coordinate frames for geometric graphs.
result The approach outperforms state-of-the-art models in various complex scenarios.
We define the fundamental quandle of a spatial graph and several invariants derived from it. In the category of graph tangles, we define an invariant based on the walks in the graph and cocycles from nonabelian quandle cohomology.
ChebLieNet uses Lie groups to create invariant spectral graph networks.
problem Handling anisotropic data in graph neural networks.
method Develops anisotropic convolutional layers on Lie groups with Riemannian metrics.
result Demonstrates the effectiveness of balancing equivariance and invariance.
New model learns graph spectra accurately, outperforming existing methods.
problem Graph diffusion models struggle to distinguish certain graph families and their spectra.
method Leveraged random matrix theory to analytically extract spectral properties, introducing Dyson Diffusion Model.
result Dyson Diffusion Model learns graph spectra accurately and outperforms existing models.
Learning high-quality node embeddings is a key building block for machine learning models that operate on graph data, such as social networks and recommender systems. However, existing graph embedding techniques are unable to cope with fairness constraints, e.g., ensuring that the learned representations do not correla…
Invariants for trivalent graphs using algebraic colorings.
problem Creating an invariant for virtual trivalent spatial graphs.
method Colorings by virtual Niebrzydowski algebras.
result Generalization and computational implementation of invariants.
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.
This is a short review article on invariants of spatial graphs, written for "A Concise Encyclopedia of Knot Theory" (ed. Adams et. al.). The emphasis is on combinatorial and polynomial invariants of spatial graphs, including the Alexander polynomial, the fundamental quandle of a graph, and the Yamada polynomial.
New theory defines invariants for framed 3-manifolds using trivalent graphs with self-loops.
problem Defining invariants for framed 3-manifolds with semi-simple Lie groups.
method Constructing graph complexes and cocycles, including self-loops, to define invariants.
result Higher-loop invariants can be defined by graph cocycles with or without self-loops.
This paper proves a conjecture linking quantum modular forms and WRT invariants for specific graphs.
problem Proving a conjecture about quantum modular forms and WRT invariants for unimodular H-graphs.
method Constructed finite sums of rational functions, studied weighted Gauss sums, and combined results to prove the conjecture.
result WRT invariants of H-graphs yield quantum modular forms of depth two and weight one.
IMPaCT improves node classification in chronological split temporal graphs.
problem Domain adaptation challenges in graph data due to chronological splits.
method IMPaCT proposes a method to impose invariant properties based on realistic assumptions derived from temporal graph structures.
result IMPaCT achieves a 3.8% performance improvement over current SOTA method on the ogbn-mag graph dataset.
New formulas for spatial 2-bouquet graphs discovered.
problem Finding formulas for Vassiliev invariants of spatial 2-bouquet graphs.
method Introducing new Gauss diagram formulas for flat vertex isotopy classes of spatial 2-bouquet graphs.
result First simple example of a Gauss diagram formula for spatial 2-bouquet graphs.
New equivalence relation on ribbon graphs connects to virtual links.
problem Understanding virtual links through ribbon graphs.
method Introducing a new equivalence relation on ribbon graphs.
result Correspondence between virtual links and ribbon graphs.
Generative models of graph structure have applications in biology and social sciences. The state of the art is GraphRNN, which decomposes the graph generation process into a series of sequential steps. While effective for modest sizes, it loses its permutation invariance for larger graphs. Instead, we present a permuta…
The paper explores weight systems and their applications to graph and embedded graph invariants.
problem Developing weight systems for graphs and embedded graphs.
method Construction of weight systems from graph invariants and metrized Lie algebras, and extending to arbitrary embedded graphs.
result Explicit forms of generating functions and recurrence relations for weight systems on chord diagrams and embedded graphs.
Extends knot polynomial to knotted 4-valent graphs.
problem Constructing an invariant for knotted 4-valent graphs.
method Graphical calculus and Reidemeister moves for 4-valent graphs.
result Extension of sl(n) polynomial to knotted 4-valent graphs. AutoBayes automates Bayesian graph exploration for robust machine learning.
problem Learning representations invariant to nuisance variations in machine learning.
method Automated Bayesian inference framework exploring different graphical models.
result Significant performance improvement with nuisance-invariant machine learning pipelines.
Edge-homotopy and vertex-homotopy are equivalence relations on spatial graphs which are generalizations of Milnor's link-homotopy. Fleming and the author introduced some edge (resp. vertex)-homotopy invariants of spatial graphs by applying the Sato-Levine invariant for the constituent 2-component algebraically split li…
Twisted graph diagrams are virtual graph diagrams with bars on edges. A bijection between abstract graph diagrams and twisted graph diagrams is constructed. Then a polynomial invariant of Yamada-type is developed which provides a lower bound for the virtual crossing number of virtual graph diagrams.
We define some signature invariants for a class of knotted trivalent graphs using branched covers. We relate them to classical signatures of knots and links. Finally, we explain how to compute these invariants through the example of Kinoshita's knotted theta graph.
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.
RIA method improves OoD generalization for covariate shift.
problem Improving out-of-distribution generalization under covariate shift.
method Adversarial label invariant graph data augmentations for OoD generalization.
result RIA method achieves high accuracy compared to OoD baselines.
Graphoids are topological invariants of virtual graph diagrams.
problem Understanding knotted graphs with open ends in proteins and simplifying virtual spatial graphs.
method Topological interpretations of graphoids using graph Reidemeister moves.
result Virtual graphoids are useful for studying knotted graphs and simplifying spatial graphs.
Recent machine learning methods make it possible to model potential energy of atomic configurations with chemical-level accuracy (as calculated from ab-initio calculations) and at speeds suitable for molecular dynam- ics simulation. Best performance is achieved when the known physical constraints are encoded in the mac…
Defines a new invariant from graph configurations in three-manifolds.
problem Counting embeddings of graphs in rational homology spheres.
method Uses integrals on configuration spaces of points in the manifold.
result Defines the degree two part of the logarithm of the invariant for concrete computations.
By using the cohomology theory of quandles, quandle cocycle invariants and shadow quandle cocycle invariants are defined for oriented links and surface-links via broken surface diagrams. By using symmetric quandles, symmetric quandle cocycle invariants are also defined for unoriented links and surface-links via broken …
We define invariants for colored oriented spatial graphs by generalizing CM invariants, which were defined via non-integral highest weight representations of Uq(sl2). We apply the same method to define Yokota's invariants, and we call these invariants Yokota type invariants. Then we propose a volume conjecture of t…
kth-order invariant graph networks are as powerful as kth-order WL in distinguishing graphs.
problem Measuring the expressive power of graph neural network formalisms.
method Considered kth-order invariant graph networks (k-IGNs) and compared their expressive power to kth-order WL.
result k-IGNs and k-WL are equally powerful in distinguishing graphs.
Graph node embedding aims at learning a vector representation for all nodes given a graph. It is a central problem in many machine learning tasks (e.g., node classification, recommendation, community detection). The key problem in graph node embedding lies in how to define the dependence to neighbors. Existing approach…
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.
Paper introduces new link homotopy invariants and applies them to 3-bouquet graphs.
problem Milnor's triple linking number and its applications in link homotopy.
method Developed new integer-valued link homotopy invariants and applied them to 3-bouquet graphs.
result Found new integer-valued invariants derived from four terms summing to Milnor's triple linking number.
New knot invariant from 3-braids and 6-valent graphs.
problem Classical knot invariant construction.
method Using group Gn3 and plat closure of braids, define a map to framed 6-valent graphs. result Obtained a knot invariant valued in equivalence classes of graphs.
We consider the problem of undirected graphical model inference. In many applications, instead of perfectly recovering the unknown graph structure, a more realistic goal is to infer some graph invariants (e.g., the maximum degree, the number of connected subgraphs, the number of isolated nodes). In this paper, we propo…