論文の概要: DRESS: A Continuous Framework for Structural Graph Refinement

• arxiv url: http://arxiv.org/abs/2602.20833v2
• Date: Thu, 26 Feb 2026 18:10:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-27 14:31:23.920943
• Title: DRESS: A Continuous Framework for Structural Graph Refinement
• Title（参考訳）: DRESS: 構造グラフリファインメントのための継続的フレームワーク
• Authors: Eduar Castrillo Velilla,
• Abstract要約: 我々はDRESSと呼ばれるグラフ同型テストと構造解析のための新しいフレームワークを開発した。 DRESSはノード削除部分グラフ$G setminus v$で動作し、フレームワークをケリー・ウラムの再構成予想に接続する。 ベンチマークグラフでは1-WLと3-WLをどちらも上回り,$mathcalO(n4)$計算コストを抑えることができた。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Weisfeiler-Lehman (WL) hierarchy is a cornerstone framework for graph isomorphism testing and structural analysis. However, scaling beyond 1-WL to 3-WL and higher requires tensor-based operations that scale as $\mathcal{O}(n^3)$ or $\mathcal{O}(n^4)$, making them computationally prohibitive for large graphs. In this paper, we start from the Original-DRESS equation (Castrillo, León, and Gómez, 2018) -- a parameter-free, continuous dynamical system on edges -- and show that it distinguishes the prism graph from $K_{3,3}$, a pair that 1-WL provably cannot separate. We then generalize it to Motif-DRESS, which replaces triangle neighborhoods with arbitrary structural motifs and converges to a unique fixed point under three sufficient conditions, and further to Generalized-DRESS, an abstract template parameterized by the choice of neighborhood operator, aggregation function and norm. Finally, we introduce $Δ$-DRESS, which runs DRESS on each node-deleted subgraph $G \setminus \{v\}$, connecting the framework to the Kelly--Ulam reconstruction conjecture. Both Motif-DRESS and $Δ$-DRESS empirically distinguish Strongly Regular Graphs (SRGs) -- such as the Rook and Shrikhande graphs -- that confound 3-WL. Our results establish the DRESS family as a highly scalable framework that empirically surpasses both 1-WL and 3-WL on well-known benchmark graphs, without the prohibitive $\mathcal{O}(n^4)$ computational cost.
• Abstract（参考訳）: Weisfeiler-Lehman(WL)階層はグラフ同型テストと構造解析の基盤となるフレームワークである。 しかし、1-WLから3-WL以上のスケーリングには、$\mathcal{O}(n^3)$または$\mathcal{O}(n^4)$というスケールのテンソルベースの演算が必要であるため、大きなグラフに対しては計算的に禁止される。 本稿では、エッジ上のパラメータフリーで連続的な力学系であるOriginal-DRESS方程式(Castrillo, León, and Gómez, 2018)から始まり、1-WLが確実に分離できないペアであるK_{3,3}$とプリズムグラフを区別することを示す。 次に、三角近傍を任意の構造的モチーフに置き換え、三つの十分な条件の下で一意な固定点に収束するモティフ・ドレスと、近隣作用素、集約関数、ノルムの選択によってパラメータ化された抽象テンプレートである一般化・ドレスに一般化する。 最後に、各ノード削除された部分グラフ$G \setminus \{v\}$上でDRESSを実行する$Δ$-DRESSを紹介し、フレームワークをケリー-ウラム再構成予想に接続する。 Motif-DRESS と $Δ$-DRESS はいずれも,Rook や Shrikhande といった 3WL を格納する強正則グラフ (SRG) を実証的に区別する。 その結果、DRESSファミリは、よく知られたベンチマークグラフ上の1-WLと3-WLの両方を実証的に超えるスケーラブルなフレームワークであり、$\mathcal{O}(n^4)$計算コストが禁じられることなく、DRESSファミリを確立した。

関連論文リスト

• An Efficient Loop and Clique Coarsening Algorithm for Graph Classification [14.602474387096244]
  本稿では,GTアーキテクチャ上でのグラフ分類(LCC4GC)の線形複雑度を考慮した効率的なループおよび斜め粗大化アルゴリズムを提案する。 具体的には、完全な構造表現を学ぶために、オリジナル、粗い、変換の3つのユニークなビューを構築します。 8つの実世界のデータセットの実験では、さまざまなアーキテクチャから31のベースラインを越えるLCC4GCの改善が示されている。
  論文  参考訳（メタデータ） (2024-04-18T03:03:37Z)
• Weisfeiler-Lehman goes Dynamic: An Analysis of the Expressive Power of Graph Neural Networks for Attributed and Dynamic Graphs [1.3757956340051607]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための大規模なリレーショナルモデルである。 GNNの表現力に関する最近の研究は、グラフを識別する能力に焦点を当てている。 実生活のアプリケーションは、しばしばより広い種類のグラフを含む。
  論文  参考訳（メタデータ） (2022-10-08T10:14:41Z)
• ExpressivE: A Spatio-Functional Embedding For Knowledge Graph Completion [78.8942067357231]
  ExpressivEは、一対の実体を点として埋め込み、仮想三重空間に超平行グラフとして関係を埋め込む。 我々は、ExpressivEが最先端のKGEと競合し、W18RRでさらに優れています。
  論文  参考訳（メタデータ） (2022-06-08T23:34:39Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。 GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
  論文  参考訳（メタデータ） (2022-05-07T04:11:23Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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