Isomorphism Testing

Description from the archive archive 2025-07-28.

Benchmarks archive 2025-07-28

No benchmark for this task in the archive.

Libraries

Not in the archive: the export carries no per-task library table, so there is nothing to show at snapshot 2025-07-28.

Datasets archive 2025-07-28

No dataset record in the archive lists this task.

Subtasks archive 2025-07-28

No subtask under this task in the archive's task tree.

Parent tasks archive 2025-07-28

Most implemented papers archive 2025-07-28

10 shown of 10 papers with code (14 tagged with this task in all), ordered by repositories listed in the archive, not by stars (the archive holds no stars, so PwC's “Social” and “Latest” sorts cannot be reproduced). Papers without a page here are shown as plain text.

• Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity
  18 Aug 2023 3 repositories listed Syntology ran 5 of 26 samples · 21 unverified
  In this paper, we propose Unified Graph Transformer Networks (UGT) that effectively integrate local and global structural information into fixed-length vector representations.
• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
  16 Jun 2025 1 repository listed Syntology ran 0 of 8 samples · 8 unverified
  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…
• Covered Forest: Fine-grained generalization analysis of graph neural networks
  10 Dec 2024 1 repository listed Syntology ran 1 of 7 samples · 6 unverified
  The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing.
• PlanE: Representation Learning over Planar Graphs
  3 Jul 2023 1 repository listed
  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…
• A Practical, Progressively-Expressive GNN
  18 Oct 2022 1 repository listed Syntology ran 3 of 3 samples · 0 unverified
  Our model is practical and progressively-expressive, increasing in power with k and c.
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
  19 Sep 2022 1 repository listed
  The classical Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning with kernels and neural networks.
• Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings
  31 Jan 2022 1 repository listed Syntology ran 2 of 2 samples · 0 unverified · 2 pointer-only (licence)
  Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.
• On Graph Neural Networks versus Graph-Augmented MLPs
  28 Oct 2020 1 repository listed
  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…
• Can Graph Neural Networks Count Substructures?
  10 Feb 2020 1 repository listed
  We also prove positive results for k-WL and k-IGNs as well as negative results for k-WL with a finite number of iterations.
• On the equivalence between graph isomorphism testing and function approximation with GNNs
  29 May 2019 1 repository listed Syntology ran 2 of 2 samples · 0 unverified
  We further develop a framework of the expressive power of GNNs that incorporates both of these viewpoints using the language of sigma-algebra, through which we compare the expressive power of different types of GNNs…

Syntology lines on 6 of the papers shown; no Syntology record for the others (a paper without an arXiv id cannot be joined to the graph, and absence from the graph layer is not a recorded non-run). “Ran” means the sample executed on a synthesized fixture, not that the paper's result was reproduced. Read from the graph 2026-09-24.