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

• arxiv url: http://arxiv.org/abs/2602.20833v5
• Date: Wed, 04 Mar 2026 17:09:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-05 16:56:46.881188
• Title: DRESS: A Continuous Framework for Structural Graph Refinement
• Title（参考訳）: DRESS: 構造グラフリファインメントのための継続的フレームワーク
• Authors: Eduar Castrillo Velilla,
• Abstract要約: 本稿では,グラフ内のエッジの構造的類似性を洗練し,標準指紋を生成するフレームワークDRESSを紹介する。 フィンガープリントは構成上は同型不変であり、数値的には安定である(すべての値は$[0,2]$)。 $-DRESSは、包括的なStrongly Regular Graphベンチマークで7,983グラフを実証的に分離し、反復削除(k$-DRESS)が階段を登り、各深さk$で$(k+2)$-WLを達成する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce DRESS, a deterministic, parameter-free framework 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 non-linear dynamical system to its unique fixed point. The fingerprint is isomorphism-invariant by construction, numerically stable (all values lie in $[0,2]$), fast and embarrassingly parallel to compute: each iteration costs $\mathcal{O}(m \cdot d_{\max})$ and convergence is guaranteed by Birkhoff contraction. As a direct consequence of these properties, DRESS is provably at least as expressive as the 2-dimensional Weisfeiler--Leman (2-WL) test, at a fraction of the cost ($\mathcal{O}(m \cdot d_{\max})$ vs. $\mathcal{O}(n^3)$ per iteration). We generalize the original equation (Castrillo, León, and Gómez, 2018) to Motif-DRESS (arbitrary structural motifs) and Generalized-DRESS (abstract aggregation template), and introduce $Δ$-DRESS, which runs DRESS on each vertex-deleted subgraph to boost expressiveness. $Δ$-DRESS empirically separates all 7,983 graphs in a comprehensive Strongly Regular Graph benchmark, and iterated deletion ($Δ^k$-DRESS) climbs the CFI staircase, achieving $(k{+}2)$-WL expressiveness at each depth $k$.
• Abstract（参考訳）: 本稿では,グラフ内のエッジの構造的類似性を反復的に洗練して正準指紋を生成する,決定論的・パラメータフリーなフレームワークDRESSを紹介する。 フィンガープリントは構成によって同型不変であり、数値的に安定であり(すべての値は$[0,2]$)、高速で恥ずかしいほど計算に並列である:各反復は$\mathcal{O}(m \cdot d_{\max})$で、収束はバーコフの収縮によって保証される。 これらの性質の直接的な結果として、DRESS は少なくとも 2-次元Weisfeiler--Leman (2-WL) テストと同程度、コスト ($\mathcal{O}(m \cdot d_{\max})$ vs. $\mathcal{O}(n^3)$) で表される。 元の方程式 (Castrillo, León, and Gómez, 2018) を Motif-DRESS (orbitrary structure motifs) と Generalized-DRESS (abstract aggregate template) に一般化し、表現力を高めるために各頂点削除部分グラフ上でDRESSを実行する$$$-DRESSを導入する。 $Δ$-DRESSは、包括的なStrongly Regular Graphベンチマークで7,983グラフを実証的に分離し、反復削除($Δ^k$-DRESS)はCFI階段を登り、各深さ$k$で$(k{+}2)$-WL表現性を達成する。

関連論文リスト

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

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

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