論文の概要: Neural Models for Output-Space Invariance in Combinatorial Problems
- arxiv url: http://arxiv.org/abs/2202.03229v1
- Date: Mon, 7 Feb 2022 14:34:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-08 21:11:07.575133
- Title: Neural Models for Output-Space Invariance in Combinatorial Problems
- Title（参考訳）: 組合せ問題における出力空間不変性のニューラルモデル
- Authors: Yatin Nandwani, Vidit Jain, Mausam and Parag Singla
- Abstract要約: 最近では、スドクやグラフカラーリング(GCP)など、解決されたインスタンスを使って、基礎となる制約を暗黙的に学習することで、パズルを解くために多くのニューラルモデルが提案されている。
提案アーキテクチャの欠点の1つは、変数が値に割り当てられる出力空間のサイズをまたいで一般化できないことである。
本稿では,GNNに基づくアーキテクチャを拡張して,値セットの不変性を実現する手法を提案する。
- 参考スコア（独自算出の注目度）: 20.99347257358466
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently many neural models have been proposed to solve combinatorial puzzles
by implicitly learning underlying constraints using their solved instances,
such as sudoku or graph coloring (GCP). One drawback of the proposed
architectures, which are often based on Graph Neural Networks (GNN), is that
they cannot generalize across the size of the output space from which variables
are assigned a value, for example, set of colors in a GCP, or board-size in
sudoku. We call the output space for the variables as 'value-set'. While many
works have demonstrated generalization of GNNs across graph size, there has
been no study on how to design a GNN for achieving value-set invariance for
problems that come from the same domain. For example, learning to solve 16 x 16
sudoku after being trained on only 9 x 9 sudokus. In this work, we propose
novel methods to extend GNN based architectures to achieve value-set
invariance. Specifically, our model builds on recently proposed Recurrent
Relational Networks. Our first approach exploits the graph-size invariance of
GNNs by converting a multi-class node classification problem into a binary node
classification problem. Our second approach works directly with multiple
classes by adding multiple nodes corresponding to the values in the value-set,
and then connecting variable nodes to value nodes depending on the problem
initialization. Our experimental evaluation on three different combinatorial
problems demonstrates that both our models perform well on our novel problem,
compared to a generic neural reasoner. Between two of our models, we observe an
inherent trade-off: while the binarized model gives better performance when
trained on smaller value-sets, multi-valued model is much more memory
efficient, resulting in improved performance when trained on larger value-sets,
where binarized model fails to train.
- Abstract（参考訳）: 近年,スードゥークやグラフカラーリング (GCP) などの問題解決インスタンスを用いて,基礎となる制約を暗黙的に学習することで,組合せパズルの解法として多くのニューラルモデルが提案されている。
提案アーキテクチャの欠点の1つは、しばしばグラフニューラルネットワーク(GNN)に基づいており、変数がGCPの色のセットやスドクのボードサイズといった値に割り当てられる出力空間のサイズを一般化できないことである。
変数の出力空間を 'value-set' と呼びます。
多くの研究がグラフサイズにまたがってGNNの一般化を実証しているが、同じ領域から生じる問題に対して値セットの不変性を実現するためにGNNを設計する方法は研究されていない。
例えば、たった9 x 9 sudokusでトレーニングした後、16 x 16 sudokuの解法を学ぶ。
本研究では,GNNに基づくアーキテクチャを拡張し,値集合の不変性を実現する手法を提案する。
具体的には,最近提案されたリカレントリレーショナルネットワークをモデルとした。
我々の最初のアプローチは、GNNのグラフサイズ不変性を利用して、マルチクラスノード分類問題をバイナリノード分類問題に変換する。
2つ目のアプローチは、値セットの値に対応する複数のノードを追加し、問題の初期化に応じて変数ノードを値ノードに接続することで、複数のクラスと直接連携する。
3つの組合せ問題について実験的に評価した結果,両モデルともジェネリックニューラル推論器と比較して,新しい問題に対して良好に機能することが示された。
この2つのモデルの間には,2項化モデルはより小さな値集合でトレーニングされた場合,性能が向上するが,多値モデルはよりメモリ効率が良く,より大きな値集合でトレーニングした場合には性能が向上する。
関連論文リスト
- E2GNN: Efficient Graph Neural Network Ensembles for Semi-Supervised Classification [30.55931541782854]
本研究では、グラフニューラルネットワーク(GNN)のアンサンブル学習を、人気のある半教師付き環境下で研究する。
ラベル付きノードとラベルなしノードの両方を活用することで,複数のGNNを学習可能な方法で組み立てる,効率的なアンサンブル学習者を提案する。
さまざまなGNNバックボーンと8つのベンチマークデータセットにまたがる、トランスダクティブとインダクティブ両方の設定に関する包括的な実験は、E2GNNの優位性を実証している。
論文 参考訳（メタデータ） (2024-05-06T12:11:46Z) - GraphViz2Vec: A Structure-aware Feature Generation Model to Improve
Classification in GNNs [2.0823678201707034]
GNNはノード分類やリンク予測など,さまざまなタスクの解決に広く利用されている。
本稿では,ノードの近傍構造情報を抽出する特徴抽出手法GraphViz2Vecを提案する。
これらの初期埋め込みは、様々な分類タスクにおいて、既存のモデルが最先端の結果を達成するのに役立つ。
論文 参考訳（メタデータ） (2024-01-30T17:11:04Z) - Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。
このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
論文 参考訳（メタデータ） (2023-12-16T14:09:23Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
整数プログラミングにおける分岐とバウンドのアプローチは、次の探索のために空間の一部を順序付けする必要がある。
本稿では,この問題に対処する新たなシアムグラフニューラルネットワークモデルを提案し,ノードを属性付き二部グラフとして表現する。
本手法は,ノードがランクに応じて探索される平易なフレームワークのインスタンスを解くことで評価する。
論文 参考訳（メタデータ） (2022-10-30T19:38:23Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - A Robust Stacking Framework for Training Deep Graph Models with
Multifaceted Node Features [61.92791503017341]
数値ノード特徴とグラフ構造を入力とするグラフニューラルネットワーク(GNN)は,グラフデータを用いた各種教師付き学習タスクにおいて,優れた性能を示した。
IID(non-graph)データをGNNに簡単に組み込むことはできない。
本稿では、グラフ認識の伝播をIDデータに意図した任意のモデルで融合するロバストな積み重ねフレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-16T22:46:33Z) - 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) - Position-based Hash Embeddings For Scaling Graph Neural Networks [8.87527266373087]
グラフニューラルネットワーク(GNN)は、ノードのエゴネットワークのトポロジとエゴネットワークのノードの特徴を考慮したノード表現を演算する。
ノードが高品質な機能を持っていない場合、GNNはノードの埋め込みを計算するために埋め込み層を学び、それらを入力機能として使用する。
この埋め込みレイヤに関連するメモリを削減するため、NLPやレコメンダシステムのようなアプリケーションで一般的に使用されるハッシュベースのアプローチが利用可能である。
本稿では,グラフ内のノードの位置を利用して,必要なメモリを大幅に削減する手法を提案する。
論文 参考訳（メタデータ） (2021-08-31T22:42:25Z) - Towards Deeper Graph Neural Networks with Differentiable Group
Normalization [61.20639338417576]
グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。
オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。
2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
論文 参考訳（メタデータ） (2020-06-12T07:18:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。