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

• arxiv url: http://arxiv.org/abs/2602.20833v3
• Date: Mon, 02 Mar 2026 02:08:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-03 15:39:03.903883
• Title: DRESS: A Continuous Framework for Structural Graph Refinement
• Title（参考訳）: DRESS: 構造グラフリファインメントのための継続的フレームワーク
• Authors: Eduar Castrillo Velilla,
• Abstract要約: 我々はDRESSと呼ばれるグラフ同型テストと構造解析のための新しいフレームワークを開発した。 DRESSはよく知られたベンチマークグラフで1-WLと3-WLを経験的に上回っている。 我々はDRESSを$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 vertex-deleted subgraph $G \setminus \{v\}$, connecting the framework to the Kelly--Ulam reconstruction conjecture. $Δ$-DRESS empirically distinguishes 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)$というスケールのテンソルベースの演算が必要であるため、大きなグラフに対しては計算的に禁止される。 本稿では,元-ドレス方程式(Castrillo, León, and Gómez, 2018)-エッジ上のパラメータフリーで連続的な力学系-から始め,そのプリズムグラフを1-WLが確実に分離できないペアであるK_{3,3}$と区別することを示す。 次に、三角近傍を任意の構造的モチーフに置き換え、三つの十分な条件の下で一意な固定点に収束するモティフ・ドレスと、近隣作用素、集約関数、ノルムの選択によってパラメータ化された抽象テンプレートである一般化・ドレスに一般化する。 最後に、各頂点削除された部分グラフ$G \setminus \{v\}$上でDRESSを実行する$Δ$-DRESSを導入し、フレームワークをケリー-ウラム再構成予想に接続する。 Δ$-DRESS は、Rook グラフや Shrikhande グラフのような強正則グラフ(SRG)を経験的に区別する。 その結果、DRESSファミリは、よく知られたベンチマークグラフ上の1-WLと3-WLの両方を実証的に超えるスケーラブルなフレームワークであり、$\mathcal{O}(n^4)$計算コストが禁じられることなく、DRESSファミリを確立した。

関連論文リスト

• Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization [64.88607416000376]
  普遍性と適応性の両方を達成する新しいアプローチであるUniGradを紹介し、UniGrad.CorrectとUniGrad.Bregmanの2つの異なる実現法を提案する。 どちらのメソッドも勾配の変動に適応し、強い凸関数に対する $mathcalO(log V_T)$ regret とexp-concave関数に対する $mathcalO(d log V_T)$ regret を同時に達成する。
  論文  参考訳（メタデータ） (2025-11-25T05:23:10Z)
• Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
  この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。 このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
  論文  参考訳（メタデータ） (2025-10-09T09:47:40Z)
• Escaping Saddle Points via Curvature-Calibrated Perturbations: A Complete Analysis with Explicit Constants and Empirical Validation [0.2864713389096699]
  本研究では,スムーズな非デルタ最適化において,厳密なサドル点を回避するための一階法を包括的に理論的に解析する。 我々の主な貢献は、完全に明示的な定数を持ち、勾配とサドル・エスケープ相を厳密に分離したパーチャベッド・エスケープ・ダイアンス (PSD) アルゴリズムである。 我々は、合成機能と実用的な機械学習タスクの両方の実験を通して、理論的予測を検証する。
  論文  参考訳（メタデータ） (2025-08-22T17:06:28Z)
• SeqGrowGraph: Learning Lane Topology as a Chain of Graph Expansions [17.302926840794193]
  本稿では,グラフ拡張の連鎖としてレーントポロジを学習する新しいフレームワークであるSeqGrowGraphを紹介する。 nuScenesとArgoverse 2のデータセットで評価する。
  論文  参考訳（メタデータ） (2025-07-07T09:42:37Z)
• An Efficient Loop and Clique Coarsening Algorithm for Graph Classification [14.602474387096244]
  本稿では,GTアーキテクチャ上でのグラフ分類(LCC4GC)の線形複雑度を考慮した効率的なループおよび斜め粗大化アルゴリズムを提案する。 具体的には、完全な構造表現を学ぶために、オリジナル、粗い、変換の3つのユニークなビューを構築します。 8つの実世界のデータセットの実験では、さまざまなアーキテクチャから31のベースラインを越えるLCC4GCの改善が示されている。
  論文  参考訳（メタデータ） (2024-04-18T03:03:37Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network [11.66117393949175]
  1つの固定サイズReLUネットワークの繰り返し構成が驚くほどの表現力を示すことを示す。 この結果から, 動的系を経由した連続深度ネットワークは, 動的関数が時間非依存であっても, 膨大な近似能力を有することが明らかとなった。
  論文  参考訳（メタデータ） (2023-01-29T04:12:58Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (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]
  グラフニューラルネットワーク(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)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。 我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
  論文  参考訳（メタデータ） (2022-05-03T12:09:59Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• 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)
• Sharp Representation Theorems for ReLU Networks with Precise Dependence on Depth [26.87238691716307]
  D$ReLU層を持つニューラルネットワークに対して,2乗損失下でのシャープな表現結果を証明した。 その結果、より深いネットワークはよりスムーズな関数を表現するのに優れているという仮説が実証された。
  論文  参考訳（メタデータ） (2020-06-07T05:25:06Z)
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs [10.846572437131872]
  mathbbRp$における勾配スパースパラメータの$boldsymboltheta*の推定について検討した。 損失に対する厳密な凸性および滑らかさの仮定が適切に制限されている場合、この推定器は、$G$とは独立な乗法定数までの2乗誤差リスク $fracs*n log (1+fracps*)$を達成する。
  論文  参考訳（メタデータ） (2020-05-31T20:08:13Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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