論文の概要: Breaking Hard Isomorphism Benchmarks with DRESS

• arxiv url: http://arxiv.org/abs/2603.18582v2
• Date: Tue, 24 Mar 2026 20:18:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-26 14:25:25.789341
• Title: Breaking Hard Isomorphism Benchmarks with DRESS
• Title（参考訳）: DRESSでハード同型ベンチマークを破る
• Authors: Eduar Castrillo Velilla,
• Abstract要約: $$-DRESSは構造グラフの洗練のためのフレームワークです。 $-DRESSは、グラフ指紋のDRESSファミリーのメンバーです。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: DRESSは、グラフ内のエッジの構造的類似性を反復的に洗練して正準指紋を生成する構造グラフ精製のための決定論的・パラメータフリーなフレームワークであり、非線形力学系をそのユニークな固定点に収束させることで得られる実数値エッジベクトルである。 $Δ$-DRESSは、単一の頂点削除レベルを適用したグラフ指紋のDRESSファミリーのメンバーである。 我々は、強い正則グラフ(43,703のSRG、12のファミリー)、追加のSRG族(8,015のグラフ)、古典的なハード構造(99の異なるグラフに対応する102のファミリー)の完全なスペンスコレクションを含む、34のハードファミリーにわたる51,813のグラフのベンチマークでそれを検証した。 Δ$-DRESSは34のベンチマークファミリーのうち33のユニークな指紋を$k=1$で生成し、5億6600万以上の同型でないペアの中で1つの内部衝突を除いて解決する。 1つの真の衝突は削除深さ$k=1$で、SRG(40,12,2,4)の2つの頂点遷移SRGの間に存在し、これは1ステップのフォールバックで$Δ^2$-DRESSに解決される。 ペアワイズ比較可能なフルソート・マルチセット指紋を持つすべての家族において、最小観察される分離マージンは少なくとも137 \times ε$であり、報告された分離が数値的に堅牢であり、収束閾値のアーティファクトではないことを確認している。 また、$Δ$-DRESS は Rook $L_2(4)$/Shrikhande 対を分離し、3WL の理論的境界を逃れることを示す。 この方法は $\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ time per graph で実行される。

関連論文リスト

• DRESS: A Continuous Framework for Structural Graph Refinement [0.0]
  本稿では,グラフ内のエッジの構造的類似性を洗練し,標準指紋を生成するフレームワークDRESSを紹介する。 フィンガープリントは構成上は同型不変であり、数値的には安定である(すべての値は$[0,2]$)。 $-DRESSは、包括的なStrongly Regular Graphベンチマークで7,983グラフを実証的に分離し、反復削除(k$-DRESS)が階段を登り、各深さk$で$(k+2)$-WLを達成する。
  論文  参考訳（メタデータ） (2026-02-24T12:18:42Z)
• Efficient Top-k s-Biplexes Search over Large Bipartite Graphs [4.507351209412066]
  二部グラフ解析において、$s$-ビスプレックスの列挙は基本的な問題である。 実世界のデータエンジニアリングでは、すべての$sビプレックスを見つけることは必要でも、計算的にも安価でもない。 単純な2n列挙アルゴリズムを破るMVBPを提案する。 FastMVBPは、いくつかのインスタンスで最大3桁のベンチマークアルゴリズムより優れている。
  論文  参考訳（メタデータ） (2024-09-27T06:23:29Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  そこで我々はMixture-of-Graphs (MoG)を導入し、各ノードに対して動的に調整されたプルーニングソリューションを選択する。 MoGには複数のスパシファイアの専門家が組み込まれており、それぞれが独自のスパーシリティレベルとプルーニング基準によって特徴付けられ、各ノードに対して適切な専門家を選択する。 5つのGNNを備えた4つの大規模OGBデータセットと2つのスーパーピクセルデータセットの実験により、MoGはより高い空間レベルのサブグラフを識別することを示した。
  論文  参考訳（メタデータ） (2024-05-23T07:40:21Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion [78.8942067357231]
  ExpressivEは、一対の実体を点として埋め込み、仮想三重空間に超平行グラフとして関係を埋め込む。 我々は、ExpressivEが最先端のKGEと競合し、W18RRでさらに優れています。
  論文  参考訳（メタデータ） (2022-06-08T23:34:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。