A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Graph Substructure Networks (GSN) improves GNN expressivity by counting subgraph isomorphisms.
PathNNs improve graph neural networks by distinguishing non-isomorphic graphs.
Explains differences between WL and folklore-WL formulations in graph neural networks.
This paper explores different graph neural network functions to improve graph isomorphism.
Graph Neural Networks (GNNs) have achieved much success on graph-structured data. In light of this, there have been increasing interests in studying their expressive power. One line of work studies the capability of GNNs to approximate permutation-invariant functions on graphs, and another focuses on the their power as…
Deep learning models have achieved huge success in numerous fields, such as computer vision and natural language processing. However, unlike such fields, it is hard to apply traditional deep learning models on the graph data due to the 'node-orderless' property. Normally, adjacency matrices will cast an artificial and …
Graph neural networks struggle to distinguish certain graph structures.
Weisfeiler-Leman struggles with graph isomorphism; enhanced architectures improve generalization.
SpeqNets improve graph neural networks by scaling and adapting to graph sparsity.
Enhanced GNN with expanded attention window and partially random embeddings.
Line graph transformation aids graph isomorphism tests by excluding challenging graph properties.
Enhances GNNs by capturing node relationships, outperforming 2-WL test.
Improved graph neural network bounds using graph diffusion matrix.
This study compares GNNs and GA-MLPs, finding GA-MLPs can distinguish graphs but not count walks.
Machine learning identifies 3-manifold triangulations using isomorphism signatures.
kth-order invariant graph networks are as powerful as kth-order WL in distinguishing graphs.
In recent years there has been a rapid increase in classification methods on graph structured data. Both in graph kernels and graph neural networks, one of the implicit assumptions of successful state-of-the-art models was that incorporating graph isomorphism features into the architecture leads to better empirical per…
Graph neural networks (GNNs) are powerful machine learning models for various graph learning tasks. Recently, the limitations of the expressive power of various GNN models have been revealed. For example, GNNs cannot distinguish some non-isomorphic graphs and they cannot learn efficient graph algorithms. In this paper,…
New benchmarks improve model performance by accounting for isomorphism classes in multi-relational datasets.
We present Graph Random Neural Features (GRNF), a novel embedding method from graph-structured data to real vectors based on a family of graph neural networks. The embedding naturally deals with graph isomorphism and preserves the metric structure of the graph domain, in probability. In addition to being an explicit em…
Graphs indistinguishable by GNNs are fully characterized.
We propose a new Graph Neural Network that combines recent advancements in the field. We give theoretical contributions by proving that the model is strictly more general than the Graph Isomorphism Network and the Gated Graph Neural Network, as it can approximate the same functions and deal with arbitrary edge values. …
Graph Neural Networks outperform the Weisfeiler-Lehman algorithm in representation power.
Geometric duality connects graph isomorphism and knot equivalence.
PiNet improves graph classification efficiency and accuracy.
ESAN improves graph neural networks by processing subgraphs.
In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically -- showing promising results. The following work investigates GNNs from a theoretical…
Graph neural networks (GNNs) have emerged recently as a powerful architecture for learning node and graph representations. Standard GNNs have the same expressive power as the Weisfeiler-Leman test of graph isomorphism in terms of distinguishing non-isomorphic graphs. However, it was recently shown that this test cannot…
We study the robustness to symmetric label noise of GNNs training procedures. By combining the nonlinear neural message-passing models (e.g. Graph Isomorphism Networks, GraphSAGE, etc.) with loss correction methods, we present a noise-tolerant approach for the graph classification task. Our experiments show that test a…
Graph homomorphism numbers embed graphs for classification.
Graph neural networks (GNN) rely on graph operations that include neural network training for various graph related tasks. Recently, several attempts have been made to apply the GNNs to functional magnetic resonance image (fMRI) data. Despite recent progresses, a common limitation is its difficulty to explain the class…
The ability of a graph neural network (GNN) to leverage both the graph topology and graph labels is fundamental to building discriminative node and graph embeddings. Building on previous work, we theoretically show that edGNN, our model for directed labeled graphs, is as powerful as the Weisfeiler-Lehman algorithm for …
Recent methods for generating novel molecules use graph representations of molecules and employ various forms of graph convolutional neural networks for inference. However, training requires solving an expensive graph isomorphism problem, which previous approaches do not address or solve only approximately. In this wor…
GNNs with random node initialization are shown to be universally expressive.
Graphs possess exotic features like variable size and absence of natural ordering of the nodes that make them difficult to analyze and compare. To circumvent this problem and learn on graphs, graph feature representation is required. A good graph representation must satisfy the preservation of structural information, w…
Dominant knots have isomorphic Seifert and Tait graphs.
In this paper, we study a new graph learning problem: learning to count subgraph isomorphisms. Different from other traditional graph learning problems such as node classification and link prediction, subgraph isomorphism counting is NP-complete and requires more global inference to oversee the whole graph. To make it …
A new GNN model SPIN achieves state-of-the-art performance on diverse real-world datasets.
This work generalizes graph neural networks (GNNs) beyond those based on the Weisfeiler-Lehman (WL) algorithm, graph Laplacians, and diffusions. Our approach, denoted Relational Pooling (RP), draws from the theory of finite partial exchangeability to provide a framework with maximal representation power for graphs. RP …
Study extends GNN VC dimension bounds to Pfaffian activation functions.
Mapper-GIN simplifies 3D point cloud classification with lightweight structure.
Extends graph similarity theory to improve MPNNs' generalization abilities.
Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressive power of graph neural networks (GNN). It was shown that the popular message passing GNN cannot distinguish between graphs that are indistinguishable by the 1-WL test (Morris et al. 2018; Xu et al. 2019). Unfortunately, many s…
TOGL adds topological info to GNNs, improving graph and node classification.
The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) v…
Algorithm determines spatial graph isomorphism with vertex, edge colorings and orientations.
Can neural networks learn to compare graphs without feature engineering? In this paper, we show that it is possible to learn representations for graph similarity with neither domain knowledge nor supervision (i.e.\ feature engineering or labeled graphs). We propose Deep Divergence Graph Kernels, an unsupervised method …
We consider a method popular in the literature of associating a two-step nilpotent Lie algebra with a finite simple graph. We prove that the two-step nilpotent Lie algebras associated with two graphs are Lie isomorphic if and only if the graphs from which they arise are isomorphic.