Breaking Hard Isomorphism Benchmarks with DRESS

• URL: http://arxiv.org/abs/2603.18582v2
• Date: Tue, 24 Mar 2026 20:18:58 GMT
• Title: Breaking Hard Isomorphism Benchmarks with DRESS
• Abstract summary: $$-DRESS is a framework for structural graph refinement.<n>$$-DRESS is a member of the DRESS family of graph fingerprints.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: DRESS is a deterministic, parameter-free framework for structural graph refinement that iteratively refines the structural similarity of edges in a graph to produce a canonical fingerprint: a real-valued edge vector, obtained by converging a nonlinear dynamical system to its unique fixed point. $Δ$-DRESS is a member of the DRESS family of graph fingerprints that applies a single level of vertex deletion. We test it on a benchmark of 51,813 distinct graphs across 34 hard families, including the complete Spence collection of strongly regular graphs (43,703 SRGs, 12 families), four additional SRG families (8,015 graphs), and 18 classical hard constructions (102 family entries corresponding to 99 distinct graphs). $Δ$-DRESS produces unique fingerprints in 33 of 34 benchmark families at $k=1$, resolving all but one within-family collision among over 576 million non-isomorphic pairs. One genuine collision exists at deletion depth $k=1$, between two vertex-transitive SRGs in SRG(40,12,2,4), which is resolved by a single-step fallback to $Δ^2$-DRESS. For every family with pairwise-comparable full sorted-multiset fingerprints, the minimum observed separation margin remains at least $137 \times ε$, confirming that the reported separations are numerically robust and not artifacts of the convergence threshold. We also show that $Δ$-DRESS separates the Rook $L_2(4)$/Shrikhande pair, proving it escapes the theoretical boundary of 3-WL. The method runs in $\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ time per graph.

Related papers

• $\mathbb{SL}(n)$ Representation Learning: An Intrinsic Mixed-Curvature Space with Higher Curvature Capacities and Deeper Order-Aware Composition [47.80325814873361]
  Mixed-curvature representation learning seeks to capture rich geometric structures that cannot be adequately modeled by a single curvature regime.<n>We introduce the $mathbbSL(n)$ space, a representation geometry defined by the simple $det(A)variant=1$ constraint and a left in Schatten-$p$ structure.<n>Despite this minimal construction, $mathbbSL(n)$ exhibits pointwise negative, zero, and flag curvature around a common flagpole.
  arXiv  Detail & Related papers  (2026-09-14T05:52:14Z)
• AutoGraphForge: Towards Automated Graph Theory Discovery [0.0]
  AutoGraphForge is an automated graph-theoretic conjecturing-refuting-formalizing-trivial system.<n>A novelty filter decides via a linear program whether a candidate is already implied by known results.<n>Run for several rounds on an HPC cluster, the loop yields $6,522$ conjectures that survived the refutation dataset.
  arXiv  Detail & Related papers  (2026-09-03T07:35:29Z)
• A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph [0.0]
  Conway's 99-graph problem asks whether a strongly regular graph with parameters $mathrmsrg(99,14,1,2)$ exists.<n>We report a systematic, fully reproducible attack by an autonomous AI research agent.
  arXiv  Detail & Related papers  (2026-07-13T18:42:21Z)
• Instruction Set and Language for Hypergraphs [0.0]
  We present IsalHG, a method for representing the structure of any finite, connected hypergraph of hyperedge arity as a string.<n>Every string over $_mathrmHG$ decodes to a valid hypergraph; the alphabet is closed.<n>We contribute the representation framework, a conjecture of canonical completeness, and the first native-versus-Levi benchmark for hypergraph isomorphism.
  arXiv  Detail & Related papers  (2026-07-11T08:15:52Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  We prove optimal sampling bounds achieving $(1pmvarepsilon)$-relative error for a broad class of Lipschitz continuous classification loss functions.<n>This includes important functions such as logistic and sigmoid loss, hinge loss, and ReLU loss, as prominent and popular representative examples.
  arXiv  Detail & Related papers  (2026-05-22T15:05:33Z)
• AdaGraph: A Graph-Native Clustering Algorithm That Overcomes the Curse of Dimensionality and Enables Scientific Discovery [0.0]
  We present AdaGraph, a graph-native clustering algorithm born from the Structure-Centric Machine Learning (SC-ML) paradigm.<n>AdaGraph operates entirely within the kNN graph topology.<n>It pairs with Graph-SCOPE, the topology-based cluster validity index introduced as a separate SC-ML contribution.
  arXiv  Detail & Related papers  (2026-05-05T01:42:59Z)
• Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-Guided Graph Pruning [55.43705665875779]
  RAGP formulates prompt compression as Redundancy-Aware Graph Pruning on a multiplex graph.<n> Experiments on LongBench show that RAGP achieves an average score of 49.3 under a 4x compression ratio.
  arXiv  Detail & Related papers  (2026-05-04T01:41:31Z)
• DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
  We introduce DRESS, a framework that refines the structural similarity of edges in a graph to produce a canonical fingerprint.<n>The fingerprint is isomorphism-invariant by construction, numerically stable (all values lie in $[0,2]$), fast and embarrassingly parallel to compute.<n>$$-DRESS empirically separates all 7,983 graphs in a comprehensive Strongly Regular Graph benchmark, and iterated deletion ($k$-DRESS) climbs the staircase, achieving $(k+2)$-WL at each depthk$.
  arXiv  Detail & Related papers  (2026-02-24T12:18:42Z)
• Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
  In bipartite graph analysis, enumeration of $s$-biplexes is a fundamental problem.<n>In real-world data engineering, finding all $s-biplexes is neither necessary nor computationally affordable.<n>We propose MVBP, that breaks the simple $2n enumeration algorithm.<n>FastMVBP outperforms the benchmark algorithms by up to three orders of magnitude in several instances.
  arXiv  Detail & Related papers  (2024-09-27T06:23:29Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA) We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2024-08-03T20:08:02Z)
• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node. MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
  arXiv  Detail & Related papers  (2024-05-23T07:40:21Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  We provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
  arXiv  Detail & Related papers  (2023-03-10T00:11:18Z)
• ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion [78.8942067357231]
  ExpressivE embeds pairs of entities as points and relations as hyper-parallelograms in the virtual triple space. We show that ExpressivE is competitive with state-of-the-art KGEs and even significantly outperforms them on W18RR.
  arXiv  Detail & Related papers  (2022-06-08T23:34:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.