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

• arxiv url: http://arxiv.org/abs/2603.18582v1
• Date: Thu, 19 Mar 2026 07:41:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-20 17:19:06.014543
• Title: Breaking Hard Isomorphism Benchmarks with DRESS
• Title（参考訳）: DRESSでハード同型ベンチマークを破る
• Authors: Eduar Castrillo Velilla,
• Abstract要約: より広範なDRESSフレームワークの一部である$-DRESSについて検討する。 $-DRESSは、51,816のグラフインスタンスをカバーする34のベンチマークファミリ間で100%内部分離を実現する。 a streamed implementation of the combination fingerprint using $mathcalO(m + B + n)$ memory.$mathcalO(n cdot I cdot d_max)$ per graph; a streamed implementation of the combination fingerprint using $mathcalO(m + B + n)$ memory.
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study the single-deletion variant $Δ$-DRESS, part of the broader DRESS framework. We demonstrate empirically that $Δ$-DRESS, a single level of vertex deletion applied to the DRESS graph fingerprint, achieves unique fingerprints within each tested SRG parameter family across all 51,718 non-isomorphic strongly regular graphs (SRGs) considered, spanning 16 parameter families: the complete Spence collection (12 families, 43,703 graphs on up to 64 vertices) plus four additional SRG families with up to 4,466 graphs per family. Combined with 18 additional hard graph families (102 graphs including Miyazaki, Chang, Paley, Latin square, and Steiner constructions), $Δ$-DRESS achieves 100% within-family separation across 34 benchmark families covering 51,816 distinct graph instances, implicitly resolving over 576 million within-family non-isomorphic pairs. Moreover, the classical Rook $L_2(4)$ vs. Shrikhande pair, SRG(16,6,2,2), is known to be indistinguishable by the original 3-WL algorithm, yet $Δ$-DRESS separates it, proving that $Δ$-DRESS escapes the theoretical boundaries of 3-WL. The method runs in polynomial time $\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ per graph; a streamed implementation of the combined fingerprint uses $\mathcal{O}(m + B + n)$ memory, where $B$ is the number of histogram bins, while the experiments reported here additionally retain the full deleted-subgraph multiset matrix for post-hoc analysis.
• Abstract（参考訳）: 本稿では,より広範なDRESSフレームワークの一部である$Δ$-DRESSについて検討する。 我々は、DRESSグラフの指紋に適用される頂点削除の1レベルである$Δ$-DRESSが、16のパラメータファミリーにまたがる全ての51,718個の非同型正則グラフ(SRG)に対して、テストされたSRGパラメータファミリー内のユニークな指紋を達成していることを実証的に証明した。 宮崎、Chang、Paley、Latin Square、Steinerといった18のグラフファミリと組み合わせて、$Δ$-DRESSは、51,816の異なるグラフインスタンスをカバーする34のベンチマークファミリに対して100%の分離を達成し、576万以上の非同型ペアを暗黙的に解決する。 さらに、古典的なRook $L_2(4)$ vs. Shrikhande 対 SRG(16,6,2,2) は元の 3-WL アルゴリズムでは区別できないことが知られているが、$Δ$-DRESS は 3WL の理論的境界から逃れることを示した。 この方法は多項式時間$\mathcal{O}(n \cdot I \cdot m \cdot d_{\max})$ per graph; 組み合わせ指紋のストリーム化実装は$\mathcal{O}(m + B + n)$ memoryを使用する。

関連論文リスト

• 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)

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

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