DRESS: A Continuous Framework for Structural Graph Refinement

• URL: http://arxiv.org/abs/2602.20833v5
• Date: Wed, 04 Mar 2026 17:09:52 GMT
• Title: DRESS: A Continuous Framework for Structural Graph Refinement
• Abstract summary: 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$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce DRESS, a deterministic, parameter-free framework 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 non-linear dynamical system to its unique fixed point. The fingerprint is isomorphism-invariant by construction, numerically stable (all values lie in $[0,2]$), fast and embarrassingly parallel to compute: each iteration costs $\mathcal{O}(m \cdot d_{\max})$ and convergence is guaranteed by Birkhoff contraction. As a direct consequence of these properties, DRESS is provably at least as expressive as the 2-dimensional Weisfeiler--Leman (2-WL) test, at a fraction of the cost ($\mathcal{O}(m \cdot d_{\max})$ vs. $\mathcal{O}(n^3)$ per iteration). We generalize the original equation (Castrillo, León, and Gómez, 2018) to Motif-DRESS (arbitrary structural motifs) and Generalized-DRESS (abstract aggregation template), and introduce $Δ$-DRESS, which runs DRESS on each vertex-deleted subgraph to boost expressiveness. $Δ$-DRESS empirically separates all 7,983 graphs in a comprehensive Strongly Regular Graph benchmark, and iterated deletion ($Δ^k$-DRESS) climbs the CFI staircase, achieving $(k{+}2)$-WL expressiveness at each depth $k$.

Related papers

• The Value of Depth in Message Passing on Sparse Graphs: A Kesten-Stigum Dichotomy [0.0]
  We study how deep does a graph neural network need to be on a sparse graph?<n>We prove that the value of depth is governed by a single number, the Kesten-Stigum ratio $=2$.<n>No local classifier of any depth beats the universal floor $e-(-)$ set by isolated roots.
  arXiv  Detail & Related papers  (2026-07-18T07:11:45Z)
• 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)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Breaking Hard Isomorphism Benchmarks with DRESS [0.0]
  $$-DRESS is a framework for structural graph refinement.<n>$$-DRESS is a member of the DRESS family of graph fingerprints.
  arXiv  Detail & Related papers  (2026-03-19T07:41:16Z)
• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  We introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman.<n>Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $mathcalO(log V_T)$ regret for strongly convex functions and $mathcalO(d log V_T)$ regret for exp-concave functions.
  arXiv  Detail & Related papers  (2025-11-25T05:23:10Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  This work proposes a novel framework based on nested evolving set processes to accelerate Personalized PageRank computation.<n>We show that the time complexity of such localized methods is upper bounded by $mintildemathcalO(R2/epsilon2), tildemathcalO(m)$ to obtain an $epsilon$-approximation of the PPR vector.
  arXiv  Detail & Related papers  (2025-10-09T09:47:40Z)
• Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation [0.2864713389096699]
  We present a comprehensive theoretical analysis of first-order methods for escaping strict saddle points in smooth non-delta optimization.<n>Our main contribution is a Perturbed-escape Descent (PSD) algorithm with fully explicit constants and a rigorous separation between gradient and saddle-escape phases.<n>We validate our theoretical predictions through experiments across both synthetic functions and practical machine learning tasks.
  arXiv  Detail & Related papers  (2025-08-22T17:06:28Z)
• SeqGrowGraph: Learning Lane Topology as a Chain of Graph Expansions [17.302926840794193]
  We present SeqGrowGraph, a novel framework that learns lane topology as a chain of graph expansions.<n>We evaluate it on nuScenes and Argoverse 2 datasets.
  arXiv  Detail & Related papers  (2025-07-07T09:42:37Z)
• An Efficient Loop and Clique Coarsening Algorithm for Graph Classification [14.602474387096244]
  We propose an efficient Loop and Clique Coarsening algorithm with linear complexity for Graph Classification (LCC4GC) on GT architecture.<n>Specifically, we build three unique views, original, coarsening, and conversion to learn a thorough structural representation.<n>Experiments on eight real-world datasets demonstrate the improvements of LCC4GC over 31 baselines from various architectures.
  arXiv  Detail & Related papers  (2024-04-18T03:03:37Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network [11.66117393949175]
  We show that the repeated compositions of a single fixed-size ReLU network exhibit surprising expressive power. Our results reveal that a continuous-depth network generated via a dynamical system has immense approximation power even if its dynamics function is time-independent.
  arXiv  Detail & Related papers  (2023-01-29T04:12:58Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs [1.3757956340051607]
  Graph Neural Networks (GNNs) are a large class of relational models for graph processing. Recent studies on the expressive power of GNNs have focused on their ability to distinguish graphs. Real-life applications often involve a much larger variety of graph types.
  arXiv  Detail & Related papers  (2022-10-08T10:14:41Z)
• 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)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  We study the first gradient descent step on the first-layer parameters $boldsymbolW$ in a two-layer network. Our results demonstrate that even one step can lead to a considerable advantage over random features.
  arXiv  Detail & Related papers  (2022-05-03T12:09:59Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth [26.87238691716307]
  We prove sharp-free representation results for neural networks with $D$ ReLU layers under square loss. Our results confirm the prevailing hypothesis that deeper networks are better at representing less smooth functions.
  arXiv  Detail & Related papers  (2020-06-07T05:25:06Z)
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs [10.846572437131872]
  We study estimation of a gradient-sparse parameter vector $boldsymboltheta* in mathbbRp$. We show that, under suitable restricted strong convexity and smoothness assumptions for the loss, the resulting estimator achieves the squared-error risk $fracs*n log (1+fracps*)$ up to a multiplicative constant that is independent of $G$.
  arXiv  Detail & Related papers  (2020-05-31T20:08:13Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  We study the power of graph neural networks (GNNs) via their ability to count attributed graph substructures. We distinguish between two types of substructure counting: inducedsubgraph-count and subgraphcount-count, and both positive and negative answers for popular GNN architectures.
  arXiv  Detail & Related papers  (2020-02-10T18:53:30Z)

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.