論文の概要: Understanding GNNs for Boolean Satisfiability through Approximation Algorithms
- arxiv url: http://arxiv.org/abs/2408.15418v1
- Date: Tue, 27 Aug 2024 21:47:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-29 17:42:47.163805
- Title: Understanding GNNs for Boolean Satisfiability through Approximation Algorithms
- Title（参考訳）: 近似アルゴリズムによるブール満足度のためのGNNの理解
- Authors: Jan Hůla, David Mojžíšek, Mikoláš Janota,
- Abstract要約: 本稿では,ブール満足度という文脈におけるグラフニューラルネットワークの解釈可能性について論じる。
目標は、これらのモデルの内部の動作を軽視し、意思決定プロセスに対する洞察力のある視点を提供することです。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The paper deals with the interpretability of Graph Neural Networks in the context of Boolean Satisfiability. The goal is to demystify the internal workings of these models and provide insightful perspectives into their decision-making processes. This is done by uncovering connections to two approximation algorithms studied in the domain of Boolean Satisfiability: Belief Propagation and Semidefinite Programming Relaxations. Revealing these connections has empowered us to introduce a suite of impactful enhancements. The first significant enhancement is a curriculum training procedure, which incrementally increases the problem complexity in the training set, together with increasing the number of message passing iterations of the Graph Neural Network. We show that the curriculum, together with several other optimizations, reduces the training time by more than an order of magnitude compared to the baseline without the curriculum. Furthermore, we apply decimation and sampling of initial embeddings, which significantly increase the percentage of solved problems.
- Abstract（参考訳）: 本稿では,ブール満足度という文脈におけるグラフニューラルネットワークの解釈可能性について論じる。
目標は、これらのモデルの内部動作をデミスティフィケートし、意思決定プロセスに対する洞察力のある視点を提供することです。
これは、ブール満足度(Boolean Satisfiability)の領域で研究された2つの近似アルゴリズム(Breief Propagation)と半定プログラミング緩和(Semidefinite Programming Relaxations)との接続を明らかにすることで実現される。
これらの接続を復活させることで、私たちは影響の大きい拡張一式を導入することができました。
最初の重要な拡張はカリキュラムのトレーニング手順であり、グラフニューラルネットワークのメッセージパッシングイテレーションの数を増やすとともに、トレーニングセットの複雑性を漸進的に増加させる。
カリキュラムは,他のいくつかの最適化とともに,カリキュラムのないベースラインに比べて1桁以上のトレーニング時間を短縮することを示した。
さらに,初期埋め込みのデシメーションとサンプリングを適用し,解問題の割合を大幅に増加させる。
関連論文リスト
- GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。
提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
論文 参考訳（メタデータ） (2024-05-21T03:33:07Z) - Batch Active Learning from the Perspective of Sparse Approximation [12.51958241746014]
アクティブな学習は、機械学習エージェントと人間のアノテーションとのインタラクションを活用することで、効率的なモデルトレーニングを可能にする。
スパース近似の観点からバッチアクティブラーニングを定式化する新しいフレームワークを提案し,提案する。
我々のアクティブラーニング手法は、ラベルのないデータプールから、対応するトレーニング損失関数が、そのフルデータプールに近似するように、情報的サブセットを見つけることを目的としている。
論文 参考訳（メタデータ） (2022-11-01T03:20:28Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Simple Contrastive Graph Clustering [41.396185271303956]
既存の手法を改善するための単純なコントラストグラフクラスタリング(SCGC)アルゴリズムを提案する。
我々のアルゴリズムは、最近のコントラストの高いディープクラスタリング競合よりも、平均して7倍のスピードアップを達成している。
論文 参考訳（メタデータ） (2022-05-11T06:45:19Z) - Graph-Based Neural Network Models with Multiple Self-Supervised
Auxiliary Tasks [79.28094304325116]
グラフ畳み込みネットワークは、構造化されたデータポイント間の関係をキャプチャするための最も有望なアプローチである。
マルチタスク方式でグラフベースニューラルネットワークモデルを学習するための3つの新しい自己教師付き補助タスクを提案する。
論文 参考訳（メタデータ） (2020-11-14T11:09:51Z) - Learning Connectivity of Neural Networks from a Topological Perspective [80.35103711638548]
本稿では,ネットワークを解析のための完全なグラフに表現するためのトポロジ的視点を提案する。
接続の規模を反映したエッジに学習可能なパラメータを割り当てることにより、学習プロセスを異なる方法で行うことができる。
この学習プロセスは既存のネットワークと互換性があり、より大きな検索空間と異なるタスクへの適応性を持っている。
論文 参考訳（メタデータ） (2020-08-19T04:53:31Z) - Towards Deeper Graph Neural Networks [63.46470695525957]
グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。
いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。
本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
論文 参考訳（メタデータ） (2020-07-18T01:11:14Z) - Distributed Training of Graph Convolutional Networks [24.040921719350283]
基礎となるデータグラフを異なるエージェントに分割する分散シナリオにおいて、どのように推論を行うかを示す。
次に,GCN学習問題を解くために,分散勾配降下法を提案する。
また, 温和条件下でのGCNトレーニング問題の定常解の収束性も確立した。
論文 参考訳（メタデータ） (2020-07-13T10:04:20Z) - Learning the Travelling Salesperson Problem Requires Rethinking
Generalization [9.176056742068813]
トラベリングセールスパーソン問題(TSP)のようなグラフ最適化問題に対するニューラルネットワークソルバのエンドツーエンドトレーニングは近年,関心が高まっている。
最先端の学習駆動アプローチは、自明に小さなサイズで訓練された場合、古典的な解法と密接に関係するが、実践的な規模で学習ポリシーを大規模に一般化することはできない。
この研究は、トレーニングで見られるものよりも大きいインスタンスへの一般化を促進する、原則化されたバイアス、モデルアーキテクチャ、学習アルゴリズムを特定するために、最近の論文を統一するエンドツーエンドのニューラルネットワークパイプラインを提示している。
論文 参考訳（メタデータ） (2020-06-12T10:14:15Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳（メタデータ） (2020-05-05T18:08:23Z) - Binary Neural Networks: A Survey [126.67799882857656]
バイナリニューラルネットワークは、リソース制限されたデバイスにディープモデルをデプロイするための有望なテクニックとして機能する。
バイナライゼーションは必然的に深刻な情報損失を引き起こし、さらに悪いことに、その不連続性はディープネットワークの最適化に困難をもたらす。
本稿では,2項化を直接実施するネイティブソリューションと,量子化誤差の最小化,ネットワーク損失関数の改善,勾配誤差の低減といった手法を用いて,これらのアルゴリズムを探索する。
論文 参考訳（メタデータ） (2020-03-31T16:47:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。