Papers Isomorphism Testing
“Isomorphism Testing” 태그가 달린 논문 14편 · 필터 해제
Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
We propose and study Hierarchical Ego Graph Neural Networks (HEGNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradig…
Isomorphism TestingCovered Forest: Fine-grained generalization analysis of graph neural networks
The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. However, MPNNs' generalization abilities -- …
Graph SimilarityIsomorphism TestingTransitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity
Graph representation learning (GRL) methods, such as graph neural networks and graph transformer models, have been successfully used to analyze graph-structured data, mainly focusing on node classification and link predi…
Graph ClassificationGraph Representation LearningIsomorphism TestingLink Prediction+4PlanE: Representation Learning over Planar Graphs
Graph neural networks are prominent models for representation learning over graphs, where the idea is to iteratively compute representations of nodes of an input graph through a series of transformations in such a way th…
Isomorphism TestingRepresentation LearningA Practical, Progressively-Expressive GNN
Message passing neural networks (MPNNs) have become a dominant flavor of graph neural networks (GNNs) in recent years. Yet, MPNNs come with notable limitations; namely, they are at most as powerful as the 1-dimensional W…
Graph LearningIsomorphism TestingGradual Weisfeiler-Leman: Slow and Steady Wins the Race
The classical Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning with kernels and neural networks. Originally developed for graph isomorphism testing, the algorithm iteratively refines vert…
Graph LearningIsomorphism TestingLocal Graph Embeddings Based on Neighbors Degree Frequency of Nodes
We propose a local-to-global strategy for graph machine learning and network analysis by defining certain local features and vector representations of nodes and then using them to learn globally defined metrics and prope…
Isomorphism TestingWeisfeiler-Lehman meets Gromov-Wasserstein
The Weisfeiler-Lehman (WL) test is a classical procedure for graph isomorphism testing. The WL test has also been widely used both for designing graph kernels and for analyzing graph neural networks. In this paper, we pr…
Isomorphism TestingWeisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings
Graph isomorphism testing is usually approached via the comparison of graph invariants. Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.e., …
Computational EfficiencyIsomorphism TestingOpen-Ended Question AnsweringGraph Deformer Network
Convolution learning on graphs draws increasing attention recently due to its potential applications to a large amount of irregular data. Most graph convolution methods leverage the plain summation/average aggregation to…
Isomorphism TestingOn Graph Neural Networks versus Graph-Augmented MLPs
From the perspective of expressive power, this work compares multi-layer Graph Neural Networks (GNNs) with a simplified alternative that we call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments nod…
Community DetectionIsomorphism TestingCan Graph Neural Networks Count Substructures?
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 an…
Computational chemistryIsomorphism TestingOn the equivalence between graph isomorphism testing and function approximation with GNNs
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…
Graph RegressionIsomorphism TestingDimension Reduction via Colour Refinement
Colour refinement is a basic algorithmic routine for graph isomorphism testing, appearing as a subroutine in almost all practical isomorphism solvers. It partitions the vertices of a graph into "colour classes" in such a…
Dimensionality ReductionIsomorphism TestingMath