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.
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.
This thesis explores GNNs, categorizing them into local and global approaches.
problem Understanding the convergence of global GNNs and connecting local and global approaches.
method Categorization of GNNs into local and global, study of Invariant Graph Networks, connecting local and global approaches, and using local MPNN for graph coarsening.
result Established a connection between local and global GNN approaches.
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.
Simple proof shows graph neural networks are versatile.
problem Proving the universality of graph neural networks.
method Introduced a Graph Homomorphism Model to prove universality.
result Simple proofs of graph neural network universality.
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…
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.
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.
PiNet learns graph representations invariant to node permutations.
problem Graph classification and representation learning invariant to node permutations.
method Differentiable node attention pooling, permutation invariant graph neural network.
result Significant accuracy improvement in isomorphic graph classification with limited training data.
Graph isomorphism can be tested using GNNs, proving their expressive power.
problem Testing graph isomorphism using Graph Neural Networks (GNNs).
method Equivalence between GNNs' function approximation and graph isomorphism testing, using sigma-algebra.
result Equivalence between graph isomorphism testing and GNN function approximation.
ABI adapts to graph data for fast, scalable inference.
problem Challenges in inference on graph-structured data.
method Amortized Bayesian Inference (ABI) framework for graph data.
result ABI successfully addresses challenges in graph data inference.
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.
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.
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.
ISP improves GNN expressivity by stratifying nodes based on graph invariants.
problem Graph Neural Networks struggle with expressivity and structural heterogeneity.
method Invariant-Stratified Propagation (ISP) using ISP-WL and ISPGNN.
result ISP achieves enhanced expressivity beyond 1-WL, with theoretical guarantees and practical improvements.
This paper proves new universality theorems for invariant and equivariant GNNs.
problem Designing GNNs that are invariant or equivariant under node permutations.
method Introduced a new class of invariant and equivariant GNNs with a single hidden layer.
result Universal invariant and equivariant GNNs can be constructed with a single set of parameters.
New algorithm uses GNNs to optimize rewards in graph-structured data.
problem Optimizing rewards in molecule design with graph-structured data.
method Embedding permutation invariance into GNNs and using GNTK for regret bounds.
result First GNN confidence bound and phased-elimination algorithm with sublinear regret.
Unified graph scattering transforms improve theoretical properties of graph neural networks.
problem Improving theoretical guarantees for graph neural networks.
method Introducing windowed and non-windowed geometric scattering transforms for graphs.
result Unified family of graph scattering transforms with provable stability and invariance.
Graph convolutional Gaussian processes learn functions on graphs.
problem Learning translation-invariant relationships on non-Euclidean domains.
method Bayesian nonparametric method using graph convolutional neural networks.
result Graph convolutional Gaussian processes outperform existing methods on images and triangular meshes.
Enhances GNNs by capturing node relationships, outperforming 2-WL test.
problem Inability of conventional GNNs to fully capture node relationships due to permutation invariance.
method Develops permutation-sensitive aggregation mechanism using permutation groups.
result Proves superior expressivity compared to 2-WL test and not less than 3-WL test.
New research limits what GNNs can compute and generalizes their performance.
problem Limits of GNNs in computing graph properties and generalization bounds.
method Novel graph-theoretic formalism and data-dependent generalization bounds.
result Proves GNNs can't compute certain graph properties and provides tighter generalization bounds.
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.
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.
Graph normalizing flows use neural networks for graph prediction and generation.
problem Efficiently processing and generating graph data with reduced memory usage.
method Reversible graph neural network model combining auto-encoder and normalizing flows.
result Graph normalizing flows achieve competitive results in graph generation and prediction.
Study evaluates neural networks based on random graph structures and finds key performance indicators.
problem Understanding and optimizing neural network architectures using graph theory.
method Evaluation of neural networks with random graph structures, focusing on structural and numerical properties.
result A new numerical graph characteristic selects a set of quasi-1-dimensional graphs that perform well.
The paper presents a method for analyzing shape graphs using specific features.
problem Analyzing geometric and topological variations in shape graphs.
method Curated set of topological, geometric, and directional features for shape graph analysis.
result The feature representation is effective for tasks like group comparison and classification.
Paper compares expressive power of GNNs, proving approximation guarantees for practical architectures.
problem Understanding the expressive power of Graph Neural Networks (GNNs).
method Theoretical framework comparing invariant and equivariant GNNs, proving approximation guarantees for practical architectures.
result Folklore Graph Neural Networks (FGNN) are the most expressive architectures for a given tensor order.
New invariant for special alternating links based on graph Laplacian.
problem Developing an invariant for special alternating links.
method Using the Laplacian matrix of the Tait graph, invariant is defined.
result A specific quadratic trace expression is invariant under flype moves.
A new graph neural network framework captures long-range interactions efficiently.
problem Efficiently modeling long-range interactions in graph neural networks for PDEs.
method Proposes a multi-level graph neural network framework using multipole methods.
result Captures interaction at all ranges with only linear complexity, learning discretization-invariant solution operators.
Graph kernels for metric graphs using tropical algebra.
problem Comparing graphs representing different metric spaces.
method Purely based on geometry and topology, invariant under edge subdivision.
result Capture complementary geometric and topological information.
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.
New graph neural networks can distinguish graphs better than previous models.
problem Graph isomorphism tests limit the expressive power of GNNs.
method Developed k-order invariant and equivariant graph neural networks, and a reduced 2-order network.
result A reduced 2-order network with a single quadratic operation has 3-WL expressiveness, surpassing message passing models.
Unified theory linking node embeddings and graph representations.
problem Clarifying the relationship between node embeddings and graph representations.
method Using invariant theory, the paper establishes a theoretical framework bridging node embeddings and structural graph representations.
result Proves equivalence between node embeddings and structural graph representations, showing they are interchangeable for various tasks.
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.
New LCM aggregator improves GNN performance and efficiency.
problem Graph neural networks' sensitivity to aggregation function choice.
method Learnable commutative monoid for graph aggregation.
result LCM aggregator achieves performance competitive with recurrent aggregators.
Paper optimizes graph neural networks for better structural graph classification.
problem Improving graph neural networks for structural graph classification.
method Focus on aggregation functions, specifically sum and histogram-based functions, to enhance discrimination.
result Design of a graph neural network that learns discriminative graph representations.
Graph neural networks (GNNs) have been shown to replicate convolutional neural networks' (CNNs) superior performance in many problems involving graphs. By replacing regular convolutions with linear shift-invariant graph filters (LSI-GFs), GNNs take into account the (irregular) structure of the graph and provide meaning…
Quantum GNNs outperform classical GNNs in jet tagging.
problem Classifying partons initiating jets from high-energy particle collisions.
method Comparison of classical and quantum GNNs and their equivariant counterparts.
result Quantum GNNs outperformed classical GNNs in binary classification tasks.
Explains differences between WL and folklore-WL formulations in graph neural networks.
problem Understanding the differences between WL and folklore-WL formulations in graph neural networks.
method Visual explanation of differences between WL and folklore-WL formulations.
result Clarifies the differences between WL and folklore-WL formulations.
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.
Graph scattering transforms are stable to metric perturbations of network topology.
problem Stability of graph data representations under metric perturbations.
method Extending scattering transforms to network data using multiresolution graph wavelets and graph convolutions.
result Graph scattering transforms are stable to metric perturbations of the underlying network topology.
Geom-GCN improves graph neural networks by preserving structural information and capturing long-range dependencies.
problem Weaknesses in MPNNs' aggregators: loss of structural information and lack of long-range dependencies.
method Proposes a geometric aggregation scheme with three modules: node embedding, structural neighborhood, and bi-level aggregation.
result Achieved state-of-the-art performance on various graph datasets.
Steerable E(3) Graph Neural Networks incorporate geometric and physical covariant information.
problem Incorporating covariant information like position, force, velocity, or spin in graph neural networks.
method Steerable E(3) Equivariant Graph Neural Networks (SEGNNs) that use steerable MLPs to incorporate geometric and physical covariant information.
result SEGNNs improve upon classic linear point convolutions and recent equivariant graph networks that send invariant messages.
Two architectures that generalize convolutional neural networks (CNNs) for the processing of signals supported on graphs are introduced. We start with the selection graph neural network (GNN), which replaces linear time invariant filters with linear shift invariant graph filters to generate convolutional features and r…
Proposes SGCN for spatially structured data.
problem Lack of node neighbor ordering in GCNs.
method Uses spatial features to learn from graphs with spatial positions.
result Empirically outperforms state-of-the-art methods.
PARD generates graphs efficiently and invariantly to node ordering.
problem Graph generation sensitivity to node ordering.
method Integrates autoregressive and diffusion models with a partial order for nodes and edges.
result PARD achieves state-of-the-art performance on molecular and non-molecular datasets.
We introduce a new cohomology theory for planar trivalent graphs with perfect matchings. The graded Euler characteristic of the cohomology is a one variable polynomial called the 2-factor polynomial that, if nonzero when evaluated at one, implies that the perfect matching is even and therefore the graph is 4-face color…
Geometric GNNs model 3D atomic systems with rotations and translations.
problem Modeling 3D atomic systems with geometric graphs and machine learning.
method Invariant, equivariant, and unconstrained GNN architectures.
result Geometric GNNs leverage physical symmetries and chemical properties.