論文の概要: Reinforcement Learning for Graph Coloring: Understanding the Power and
Limits of Non-Label Invariant Representations
- arxiv url: http://arxiv.org/abs/2401.12470v1
- Date: Tue, 23 Jan 2024 03:43:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-24 16:53:32.143537
- Title: Reinforcement Learning for Graph Coloring: Understanding the Power and
Limits of Non-Label Invariant Representations
- Title（参考訳）: グラフ彩色のための強化学習:非ラベル不変表現のパワーと限界を理解する
- Authors: Chase Cummins and Richard Veras
- Abstract要約: 本稿では,グラフ着色問題の解法を近似ポリシ最適化モデルで学習できることを示す。
また、グラフの行列表現を取り込み、それを置換することにより、グラフのラベル付けがモデルの性能に重要であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Register allocation is one of the most important problems for modern
compilers. With a practically unlimited number of user variables and a small
number of CPU registers, assigning variables to registers without conflicts is
a complex task. This work demonstrates the use of casting the register
allocation problem as a graph coloring problem. Using technologies such as
PyTorch and OpenAI Gymnasium Environments we will show that a Proximal Policy
Optimization model can learn to solve the graph coloring problem. We will also
show that the labeling of a graph is critical to the performance of the model
by taking the matrix representation of a graph and permuting it. We then test
the model's effectiveness on each of these permutations and show that it is not
effective when given a relabeling of the same graph. Our main contribution lies
in showing the need for label reordering invariant representations of graphs
for machine learning models to achieve consistent performance.
- Abstract（参考訳）: レジスタ割り当ては、現代のコンパイラにとって最も重要な問題の1つです。
事実上無制限のユーザ変数と少数のCPUレジスタを持つため、競合のないレジスタに変数を割り当てるのは複雑な作業である。
本稿では,グラフカラー化問題としてレジスタ割り当て問題を用いる方法を示す。
PyTorch や OpenAI Gymnasium Environments のような技術を用いて、近似ポリシー最適化モデルがグラフの着色問題を解決することができることを示す。
また、グラフの行列表現を取り込み、それを置換することにより、グラフのラベル付けがモデルの性能に重要であることを示す。
次に、各置換に対してモデルの有効性を検証し、同じグラフのレバーベリングを与えられると効果がないことを示す。
我々の主な貢献は、一貫したパフォーマンスを達成するために、機械学習モデルのためのグラフの不変表現をラベルで並べ替える必要性を示すことである。
関連論文リスト
- Imbalanced Graph Classification with Multi-scale Oversampling Graph Neural Networks [25.12261412297796]
本稿では,表現力のあるマイノリティグラフ表現を学習するマルチスケールオーバーサンプリンググラフニューラルネットワーク(MOSGNN)を提案する。
サブグラフレベル、グラフレベル、ペアワイズグラフ学習タスクを共同で最適化することで、これを実現する。
16のバランスの取れないグラフデータセットの実験では、MOSGNN i)が5つの最先端モデルを大幅に上回っている。
論文 参考訳（メタデータ） (2024-05-08T09:16:54Z) - Deep Prompt Tuning for Graph Transformers [55.2480439325792]
ファインチューニングはリソース集約型であり、大きなモデルのコピーを複数保存する必要がある。
ファインチューニングの代替として,ディープグラフプロンプトチューニングと呼ばれる新しい手法を提案する。
事前学習したパラメータを凍結し、追加したトークンのみを更新することにより、フリーパラメータの数を減らし、複数のモデルコピーを不要にする。
論文 参考訳（メタデータ） (2023-09-18T20:12:17Z) - There is more to graphs than meets the eye: Learning universal features with self-supervision [2.882036130110936]
本稿では,複数のグラフに一般化可能な自己スーパービジョンによる特徴学習の課題について検討する。
提案手法では,(1)下流ノード分類の性能向上,(2)同じ家系の未確認グラフに再利用可能な学習機能,(3)より効率的なトレーニング,(4)コンパクトで一般化可能なモデルを提案する。
論文 参考訳（メタデータ） (2023-05-31T14:08:48Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳（メタデータ） (2022-12-08T23:36:00Z) - Similarity-aware Positive Instance Sampling for Graph Contrastive
Pre-training [82.68805025636165]
トレーニングセット内の既存グラフから直接正のグラフインスタンスを選択することを提案する。
私たちの選択は、特定のドメイン固有のペアワイズ類似度測定に基づいています。
さらに,ノードを動的にマスキングしてグラフ上に均等に分配する適応ノードレベルの事前学習手法を開発した。
論文 参考訳（メタデータ） (2022-06-23T20:12:51Z) - GraphCoCo: Graph Complementary Contrastive Learning [65.89743197355722]
グラフコントラスト学習(GCL)は、手作業によるアノテーションの監督なしに、グラフ表現学習(GRL)において有望な性能を示した。
本稿では,この課題に対処するため,グラフココというグラフ補完型コントラスト学習手法を提案する。
論文 参考訳（メタデータ） (2022-03-24T02:58:36Z) - Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
正準グラフ着色問題の解法としてグラフニューラルネットワークを用いる方法を示す。
マルチクラスノード分類問題としてグラフカラー化を行い,教師なし学習戦略を利用する。
論文 参考訳（メタデータ） (2022-02-03T14:24:12Z) - Graph2Graph Learning with Conditional Autoregressive Models [8.203106789678397]
グラフ・ツー・グラフ学習のための条件付きオートレアモデルを提案する。
本稿では,グラフアルゴリズムの挑戦的部分グラフ予測実験を通じて,その表現能力について述べる。
論文 参考訳（メタデータ） (2021-06-06T20:28:07Z) - Structural Information Preserving for Graph-to-Text Generation [59.00642847499138]
グラフ・トゥ・テキスト生成の課題は、入力グラフの意味を保存した文を生成することである。
入力情報を保存するためのモデルとして,より豊かなトレーニング信号を活用することで,この問題に取り組むことを提案する。
グラフからテキストへの生成のための2つのベンチマークに関する実験は、最先端のベースラインに対するアプローチの有効性を示しています。
論文 参考訳（メタデータ） (2021-02-12T20:09:01Z) - Graph topology inference benchmarks for machine learning [16.857405938139525]
本稿では,グラフ推論手法の相対的メリットと限界を明らかにするために,いくつかのベンチマークを導入する。
我々はまた、文学において最も顕著な技法のいくつかを対比している。
論文 参考訳（メタデータ） (2020-07-16T09:40:32Z) - Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
グラフオートエンコーダ(GAE)は、グラフ埋め込みのための表現学習において強力なツールである。
本稿では,2つの新しい教師なしグラフ埋め込み法,適応グラフ学習(BAGE)による教師なしグラフ埋め込み,変分適応グラフ学習(VBAGE)による教師なしグラフ埋め込みを提案する。
いくつかのデータセットに関する実験的研究により、我々の手法がノードクラスタリング、ノード分類、グラフ可視化タスクにおいて、ベースラインよりも優れていることが実証された。
論文 参考訳（メタデータ） (2020-03-10T02:33:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。