論文の概要: Deep Learning and Spectral Embedding for Graph Partitioning

• arxiv url: http://arxiv.org/abs/2110.08614v1
• Date: Sat, 16 Oct 2021 16:57:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-19 17:12:36.205754
• Title: Deep Learning and Spectral Embedding for Graph Partitioning
• Title（参考訳）: グラフ分割のための深層学習とスペクトル埋め込み
• Authors: Alice Gatti, Zhixiong Hu, Tess Smidt, Esmond G. Ng, Pieter Ghysels
• Abstract要約: 本稿では,グラフニューラルネットワークに基づくグラフ分割分割アルゴリズムを提案する。 グラフの各ノードに対して、ネットワークは各パーティションの確率を出力する。
• 参考スコア（独自算出の注目度）: 0.13999481573773068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a graph bisection and partitioning algorithm based on graph neural networks. For each node in the graph, the network outputs probabilities for each of the partitions. The graph neural network consists of two modules: an embedding phase and a partitioning phase. The embedding phase is trained first by minimizing a loss function inspired by spectral graph theory. The partitioning module is trained through a loss function that corresponds to the expected value of the normalized cut. Both parts of the neural network rely on SAGE convolutional layers and graph coarsening using heavy edge matching. The multilevel structure of the neural network is inspired by the multigrid algorithm. Our approach generalizes very well to bigger graphs and has partition quality comparable to METIS, Scotch and spectral partitioning, with shorter runtime compared to METIS and spectral partitioning.
• Abstract（参考訳）: 本稿では,グラフニューラルネットワークに基づくグラフ分割分割アルゴリズムを提案する。 グラフの各ノードに対して、ネットワークは各パーティションの確率を出力する。 グラフニューラルネットワークは、埋め込み相と分割相の2つのモジュールから構成される。 埋め込み位相は、まずスペクトルグラフ理論に着想を得た損失関数を最小化する。 分割モジュールは、正規化されたカットの期待値に対応する損失関数によって訓練される。 ニューラルネットワークのどちらの部分も、重いエッジマッチングを用いたセージ畳み込み層とグラフ粗さに依存しています。 ニューラルネットワークのマルチレベル構造は、マルチグリッドアルゴリズムにインスパイアされている。 我々のアプローチは、より大きなグラフに非常によく一般化し、metis、scotch、spectral partitioningに匹敵するパーティション品質を持ち、metisやspectral partitioningに比べてランタイムが短い。

関連論文リスト

• GNN-LoFI: a Novel Graph Neural Network through Localized Feature-based Histogram Intersection [51.608147732998994]
  グラフニューラルネットワークは、グラフベースの機械学習の選択フレームワークになりつつある。 本稿では,古典的メッセージパッシングに代えて,ノード特徴の局所分布を解析するグラフニューラルネットワークアーキテクチャを提案する。
  論文  参考訳（メタデータ） (2024-01-17T13:04:23Z)
• Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective [53.999128831324576]
  グラフニューラルネットワーク(GNN)は、グラフ表現学習の先駆けとなった。 本研究では,特徴学習理論の文脈におけるグラフ畳み込みの役割について検討する。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。 単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。 ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
  論文  参考訳（メタデータ） (2022-04-20T08:24:43Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  本稿では,このグラフからBernoulliをサンプリングしたグラフ上でGNNをトレーニングすることで,WNN(Graphon Neural Network)を学習する問題を考察する。 これらの結果から着想を得た大規模グラフ上でGNNを学習するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T15:05:59Z)
• Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning [0.13999481573773068]
  本稿では,強化学習とグラフ畳み込みニューラルネットワークに基づくグラフ分割手法を提案する。 提案手法はMETISやスコッチと同様の仕切り品質を実現する。 この方法は、あるクラスのグラフから別のグラフに一般化し、 suitesparse sparse matrix collectionの様々なグラフでうまく機能する。
  論文  参考訳（メタデータ） (2021-04-08T06:54:24Z)
• Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
  グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。 CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。 提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
  論文  参考訳（メタデータ） (2020-10-25T22:39:31Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  ローカルノードの類似性と接続性、グローバル構造をトレードオフする教師なしグラフ埋め込みを導入する。 埋め込みは一般化されたグラフ Laplacian に基づいており、固有ベクトルは1つの表現においてネットワーク構造と近傍近傍の両方をコンパクトにキャプチャする。
  論文  参考訳（メタデータ） (2020-09-30T04:59:10Z)
• Geom-GCN: Geometric Graph Convolutional Networks [15.783571061254847]
  本稿では,この2つの弱点を克服するために,グラフニューラルネットワークのための新しい幾何集約手法を提案する。 提案したアグリゲーションスキームは置換不変であり、ノード埋め込み、構造近傍、二レベルアグリゲーションという3つのモジュールから構成される。 また,このスキームをGeom-GCNと呼ばれるグラフ畳み込みネットワークに実装し,グラフ上でトランスダクティブ学習を行う。
  論文  参考訳（メタデータ） (2020-02-13T00:03:09Z)
• Hierarchical Representation Learning in Graph Neural Networks with Node Decimation Pooling [31.812988573924674]
  グラフニューラルネットワーク(GNN)では、プール演算子は入力グラフの局所的な要約を計算し、そのグローバルな特性をキャプチャする。 グラフトポロジ全体を保存しながら粗いグラフを生成するGNNのためのプール演算子であるNode Decimation Pooling (NDP)を提案する。 NDPは、最先端のグラフプーリング演算子よりも効率的であり、同時に、様々なグラフ分類タスクにおける競合性能にも達する。
  論文  参考訳（メタデータ） (2019-10-24T21:42:12Z)

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

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