論文の概要: Can Hybrid Geometric Scattering Networks Help Solve the Maximal Clique Problem?

• arxiv url: http://arxiv.org/abs/2206.01506v1
• Date: Fri, 3 Jun 2022 11:09:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-06 14:39:37.286838
• Title: Can Hybrid Geometric Scattering Networks Help Solve the Maximal Clique Problem?
• Title（参考訳）: ハイブリッド幾何散乱ネットワークは最大斜め問題の解決に役立つか?
• Authors: Yimeng Min, Frederik Wenkel, Michael Perlmutter, Guy Wolf
• Abstract要約: NP-hard maximal clique (MC) 問題の近似解に対する幾何散乱に基づくグラフニューラルネットワーク(GNN)を提案する。 実験の結果,提案手法は解の精度と推論速度の点で代表的GNNベースラインよりも優れていた。
• 参考スコア（独自算出の注目度）: 12.953897563456271
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a geometric scattering-based graph neural network (GNN) for approximating solutions of the NP-hard maximal clique (MC) problem. We construct a loss function with two terms, one which encourages the network to find a large set of nodes and the other which acts as a surrogate for the constraint that the nodes form a clique. We then use this loss to train a novel GNN architecture that outputs a vector representing the probability for each node to be part of the MC and apply a rule-based decoder to make our final prediction. The incorporation of the scattering transform alleviates the so-called oversmoothing problem that is often encountered in GNNs and would degrade the performance of our proposed setup. Our empirical results demonstrate that our method outperforms representative GNN baselines in terms of solution accuracy and inference speed as well as conventional solvers like GUROBI with limited time budgets.
• Abstract（参考訳）: NP-hard maximal clique (MC) 問題の近似解に対する幾何散乱に基づくグラフニューラルネットワーク(GNN)を提案する。 損失関数を2つの項で構成し、1つはネットワークにノードの大規模な集合を見つけるよう促し、もう1つはノードがクライクを形成する制約の代理として振る舞う。 この損失を利用してGNNアーキテクチャをトレーニングし、各ノードがMCの一部である確率を表すベクトルを出力し、ルールベースのデコーダを適用して最終的な予測を行う。 散乱変換の組み入れは、GNNでしばしば発生するいわゆる過平滑化問題を緩和し、提案したセットアップの性能を低下させる。 実験の結果,提案手法は時間予算に制限のあるGUROBIのような従来の解法と同様に,解の精度と推論速度において代表的GNNベースラインよりも優れていた。

関連論文リスト

• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  本稿では,集約中に含まれるノード数を削減する手法を提案する。 線形変換された特徴の重み付け和を用いてノード表現の近似を学習し、スパース分解によりこれを実現できる。 提案手法は推論高速化のために設計された他のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-25T17:52:16Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs [13.871690454501389]
  本稿では,グラフ上のCO問題を解くために,複雑なフィルタバンクと局所的な注意機構を活用する新しいGNNアーキテクチャであるGCONを紹介する。 GCONはすべてのタスクで競争力があり、他の特別なGNNベースのアプローチよりも一貫して優れています。
  論文  参考訳（メタデータ） (2024-05-31T00:02:07Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。 このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
  論文  参考訳（メタデータ） (2023-12-16T14:09:23Z)
• $\rm A^2Q$: Aggregation-Aware Quantization for Graph Neural Networks [18.772128348519566]
  グラフニューラルネットワーク(GNN)のための集約型混合精度量子化(rm A2Q$)を提案する。 本手法は,ノードレベルのタスクとグラフレベルのタスクで最大11.4%,9.5%の精度向上を実現し,専用ハードウェアアクセラレータで最大2倍の高速化を実現する。
  論文  参考訳（メタデータ） (2023-02-01T02:54:35Z)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  本稿では,正規化によるGNNの性能向上に焦点をあてる。 グラフ中のノード次数の長期分布を調べることにより、GNNの新しい正規化法を提案する。 ResNormの$scale$操作は、尾ノードの精度を向上させるために、ノード単位の標準偏差(NStd)分布を再設定する。
  論文  参考訳（メタデータ） (2022-06-16T13:49:09Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。 我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
  論文  参考訳（メタデータ） (2021-10-27T11:48:50Z)
• Edgeless-GNN: Unsupervised Inductive Edgeless Network Embedding [7.391641422048645]
  ネットワークを新たに入力したユーザなど,エッジレスノードを埋め込む問題について検討する。 我々は,非教師付き帰納学習により,エッジレスノードに対してもノード埋め込みを生成可能な新しいフレームワークであるEdgeless-GNNを提案する。
  論文  参考訳（メタデータ） (2021-04-12T06:37:31Z)
• Graph Neural Networks for Motion Planning [108.51253840181677]
  低次元問題に対する高密度固定グラフ上のGNNと高次元問題に対するサンプリングベースGNNの2つの手法を提案する。 RRT(Rapidly-Exploring Random Trees)におけるクリティカルノードの特定やサンプリング分布の学習といった計画上の問題にGNNが取り組む能力について検討する。 臨界サンプリング、振り子、6つのDoFロボットアームによる実験では、GNNは従来の分析手法の改善だけでなく、完全に接続されたニューラルネットワークや畳み込みニューラルネットワークを用いた学習アプローチも示している。
  論文  参考訳（メタデータ） (2020-06-11T08:19:06Z)

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

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