論文の概要: 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でハード同型ベンチマークを破る
- 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 で実行される。
関連論文リスト
- $\mathbb{SL}(n)$ Representation Learning: An Intrinsic Mixed-Curvature Space with Higher Curvature Capacities and Deeper Order-Aware Composition [47.80325814873361]
混合曲率表現学習は、単一の曲率構造によって適切にモデル化できないリッチな幾何学的構造を捉えることを目指している。
例えば、$mathbbSL(n)$ space, a representation geometry defined by the simple $det(A)variant=1$ constraint and a left in Schatten-$p$ structure。
この最小構成にもかかわらず、$mathbbSL(n)$ は共通のフラグポールの周りに点方向の負、零、およびフラグ曲率を示す。
論文 参考訳（メタデータ） (2026-09-14T05:52:14Z) - AutoGraphForge: Towards Automated Graph Theory Discovery [0.0]
AutoGraphForgeは、自動グラフ理論の導出-拡散-ホルマライゼーション-自明なシステムである。
新規性フィルタは、既知の結果によって既に候補が示唆されているか否かを線形プログラムを介して決定する。
HPCクラスタ上で数ラウンド実行されると、リフューテーションデータセットを生き残った6,522ドルの予想が生成される。
論文 参考訳（メタデータ） (2026-09-03T07:35:29Z) - A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph [0.0]
コンウェイの99グラフ問題はパラメータ $mathrmsrg(99,14,1,2)$ の強い正則グラフが存在するかどうかを問うものである。
我々は,自律型AI研究エージェントによる,体系的で完全に再現可能な攻撃を報告した。
論文 参考訳（メタデータ） (2026-07-13T18:42:21Z) - Instruction Set and Language for Hypergraphs [0.0]
IsalHG は任意の有限連結なハイパーグラフの構造を文字列として表現する手法である。
$_mathrmHG$上のすべての文字列は有効なハイパーグラフにデコードされる。
我々は、表現フレームワーク、標準完全性予想、およびハイパーグラフ同型のための最初のネイティブ・ヴァース・レヴィベンチマークに貢献する。
論文 参考訳（メタデータ） (2026-07-11T08:15:52Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - AdaGraph: A Graph-Native Clustering Algorithm That Overcomes the Curse of Dimensionality and Enables Scientific Discovery [0.0]
本稿では,Structure-Centric Machine Learning(SC-ML)パラダイムから生まれたグラフネイティブクラスタリングアルゴリズムであるAdaGraphを紹介する。
AdaGraphは、完全にkNNグラフトポロジー内で動作する。
Graph-SCOPEは、独自のSC-MLコントリビューションとして導入されたトポロジベースのクラスタ妥当性インデックスである。
論文 参考訳（メタデータ） (2026-05-05T01:42:59Z) - Mapping Text to Multiplex Graph: Prompt Compression as Lévy Walk-Guided Graph Pruning [55.43705665875779]
RAGPは、多重グラフ上の冗長性を考慮したグラフプルーニングとして、即時圧縮を定式化する。
LongBenchの実験では、RAGPは平均スコア49.3を4倍の圧縮比で達成している。
論文 参考訳（メタデータ） (2026-05-04T01:41:31Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。