論文の概要: Gradual Weisfeiler-Leman: Slow and Steady Wins the Race

• arxiv url: http://arxiv.org/abs/2209.09048v1
• Date: Mon, 19 Sep 2022 14:37:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-20 20:05:14.466116
• Title: Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
• Title（参考訳）: 徐々にweisfeiler-leman: ゆっくりと着実にレースに勝つ
• Authors: Franka Bause and Nils M. Kriege
• Abstract要約: Weisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 本研究では, 着色速度を緩やかに収束させることができる, 漸進的な地区改良のための枠組みを提案する。 提案手法は,既存のグラフカーネルの新しい変種を導出し,最適割り当てによるグラフ編集距離を近似するために用いられる。
• 参考スコア（独自算出の注目度）: 4.416484585765029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning and central for successful graph kernels and graph neural networks. Originally developed for graph isomorphism testing, the algorithm iteratively refines vertex colors. On many datasets, the stable coloring is reached after a few iterations and the optimal number of iterations for machine learning tasks is typically even lower. This suggests that the colors diverge too fast, defining a similarity that is too coarse. We generalize the concept of color refinement and propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring and thus provides a more fine-grained refinement hierarchy and vertex similarity. We assign new colors by clustering vertex neighborhoods, replacing the original injective color assignment function. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments regarding vertex similarity. We show that in both tasks, our method outperforms the original color refinement with only moderate increase in running time advancing the state of the art.
• Abstract（参考訳）: 古典的なWeisfeiler-Lemanアルゴリズムは、グラフ学習には基本的であり、グラフカーネルやグラフニューラルネットワークの成功には中心となる。 もともとグラフ同型テストのために開発されたアルゴリズムは、頂点色を反復的に洗練する。 多くのデータセットでは、安定的な色付けは数回のイテレーションで達成され、機械学習タスクの最適なイテレーション数は通常さらに少ない。 これは、色があまりにも速く、粗い類似性を定義することを示唆している。 カラーリファインメントの概念を一般化し、安定した着色に緩やかな収束を可能にする段階的な近傍リファインメントの枠組みを提案し、より微細な精細化階層と頂点類似性を提供する。 我々は頂点近傍をクラスタリングして新しい色を割り当て、元の入射色割り当て関数を置き換える。 本手法は,既存のグラフカーネルの新しい変種を導出し,頂点類似性に関する最適割り当てを通じてグラフ編集距離を近似するために用いられる。 いずれの課題においても,本手法は動作時間の適度な増加を伴い,元のカラーリファインメントよりも優れることを示す。

関連論文リスト

• PF-GNN: Differentiable particle filtering based approximation of universal graph representations [20.544160526945234]
  グラフニューラルネットワーク(GNN)は、グラフ同型に対する1-WL色補正テストによって、表現力に制限があることが知られている。 本研究では,学習過程を厳密な同型解法で導くことによって,GNNを普遍化する手法を提案する。 我々のアルゴリズムはエンドツーエンドで微分可能であり、任意のGNNをバックボーンとして適用することができ、よりリッチなグラフ表現を線形に増加させて学習することができる。
  論文  参考訳（メタデータ） (2024-01-31T11:26:03Z)
• How to guess a gradient [68.98681202222664]
  我々は、勾配が以前考えられていたよりもより構造化されていることを示す。 この構造をエクスプロイトすると、勾配のない最適化スキームが大幅に改善される。 厳密な勾配の最適化と勾配の推測の間に大きなギャップを克服する上での新たな課題を強調した。
  論文  参考訳（メタデータ） (2023-12-07T21:40:44Z)
• Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks [5.620334754517149]
  本稿では,グラフカラー化の競争的構築を見つけるために,深層強化学習が有効かどうかを検討する。 提案手法であるReLColでは,深層Q-ラーニングとグラフニューラルネットワークを用いて特徴抽出を行う。 グラフカラー化問題のさらなる研究には,強化学習が有望な方向であることを実証する。
  論文  参考訳（メタデータ） (2023-04-08T15:41:01Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  グラフマイニングのための非段階的決定層を持つ新しいグラフ深層モデルを提案する。 提案モデルでは,現行モデルと比較して最先端性能を実現している。
  論文  参考訳（メタデータ） (2022-07-18T04:34:08Z)
• Evolutionary Algorithm for Graph Coloring Problem [0.0]
  グラフ色問題(GCP)は、コンピュータ科学において最も研究されているNP-HARD問題の一つである。 本稿では、色数の理論上界、すなわち最大外度+1から始める。 進化の過程で、いくつかの色は、世代ごとに動的に色の数を減らすために使われない。
  論文  参考訳（メタデータ） (2021-11-17T12:16:57Z)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  グラフカラー化のための"古典的"メタヒューリスティックス(classical metaheuristics)の最高のツールと、ディープニューラルネットワークを組み合わせた新しいフレームワークを提案する。 アルゴリズムにおけるディープラーニングの寄与についての研究は、この問題に対するより良い解を得るのに有用な関連パターンを学習することが可能であることを強調している。
  論文  参考訳（メタデータ） (2021-09-13T13:17:41Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。 提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。 すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
  論文  参考訳（メタデータ） (2021-09-01T08:24:02Z)
• Adapting Stepsizes by Momentumized Gradients Improves Optimization and Generalization [89.66571637204012]
  textscAdaMomentum on vision, and achieves state-the-art results on other task including language processing。 textscAdaMomentum on vision, and achieves state-the-art results on other task including language processing。 textscAdaMomentum on vision, and achieves state-the-art results on other task including language processing。
  論文  参考訳（メタデータ） (2021-06-22T03:13:23Z)
• Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
  エッジを現在のグラフに追加する動的設定について検討する。 次に、ランダム化された検索の予測時間を分析し、高品質な解を再計算する。
  論文  参考訳（メタデータ） (2021-05-26T13:00:31Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)

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

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