論文の概要: Graph Pooling with Maximum-Weight $k$-Independent Sets

• arxiv url: http://arxiv.org/abs/2208.03523v1
• Date: Sat, 6 Aug 2022 14:12:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-09 13:43:50.694726
• Title: Graph Pooling with Maximum-Weight $k$-Independent Sets
• Title（参考訳）: 最大$k$非依存集合によるグラフプーリング
• Authors: Davide Bacciu, Alessio Conte, Francesco Landolfi
• Abstract要約: 最大ウェイト$k$非依存集合のグラフ理論的概念に基づくグラフ粗化機構を導入する。 我々は、経路長の歪み境界の理論的保証と、粗化グラフにおける重要な位相特性を保存できることを証明した。
• 参考スコア（独自算出の注目度）: 12.251091325930837
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph reductions are fundamental when dealing with large scale networks and relational data. They allow to downsize tasks of high computational impact by solving them in coarsened structures. At the same time, graph reductions play the role of pooling layers in graph neural networks, to extract multi-resolution representations from structures. In these contexts, the ability of the reduction mechanism to preserve distance relationships and topological properties appears fundamental, along with a scalability enabling its application to real-world sized problems. In this paper, we introduce a graph coarsening mechanism based on the graph-theoretic concept of maximum-weight $k$-independent sets, providing a greedy algorithm that allows efficient parallel implementation on GPUs. Our method is the first graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data (images, sequences). We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. We leverage these concepts to define a graph pooling mechanism that we empirically assess in graph classification tasks, showing that it compares favorably against pooling methods in literature.
• Abstract（参考訳）: 大規模ネットワークやリレーショナルデータを扱う場合、グラフの削減が基本である。 粗い構造でそれらを解くことで、高い計算負荷のタスクを縮小できる。 同時に、グラフリダクションは、構造からマルチレゾリューション表現を抽出するために、グラフニューラルネットワークの層をプールする役割を担っている。 これらの文脈において、距離関係と位相特性を保存するための還元機構の能力は、その応用を現実のサイズの問題に適用できるスケーラビリティとともに、基本的なものと考えられる。 本稿では,最大重量$k$非依存集合のグラフ理論的概念に基づくグラフ粗大化機構を導入し,GPU上での効率的な並列実装を実現するグレディアルゴリズムを提案する。 本手法は, 正規データ(画像, シーケンス)における制御可能な等間隔粗粒化機構の最初のグラフ構造対応である。 我々は、経路長の歪み境界の理論的保証と、粗化グラフにおける重要な位相特性を保存する能力を証明する。 これらの概念を利用して,グラフ分類タスクにおいて経験的に評価するグラフプーリング機構を定義し,文献のプーリング手法と比較した。

関連論文リスト

• GraphCroc: Cross-Correlation Autoencoder for Graph Structural Reconstruction [6.817416560637197]
  グラフオートエンコーダ(GAE)はノード埋め込みからグラフ構造を再構築する。 我々はGAE表現能力を著しく向上する相互相関機構を導入する。 また、さまざまな下流タスクに適したフレキシブルエンコーダアーキテクチャをサポートする新しいGAEであるGraphCrocを提案する。
  論文  参考訳（メタデータ） (2024-10-04T12:59:45Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• SynGraphy: Succinct Summarisation of Large Networks via Small Synthetic Representative Graphs [4.550112751061436]
  大規模ネットワークデータセットの構造を視覚的に要約するSynGraphyについて述べる。 入力グラフに類似した構造特性を持つために生成されたより小さなグラフを描画する。
  論文  参考訳（メタデータ） (2023-02-15T16:00:15Z)
• Graph Kernel Neural Networks [53.91024360329517]
  本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。 これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。 私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
  論文  参考訳（メタデータ） (2021-12-14T14:48:08Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  本稿では,重要なグラフ構造情報を活用するために,クロスビューグラフプーリング(Co-Pooling)手法を提案する。 クロスビュー相互作用、エッジビュープーリング、ノードビュープーリングにより、相互にシームレスに強化され、より情報的なグラフレベルの表現が学習される。
  論文  参考訳（メタデータ） (2021-09-24T08:01:23Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  本稿では,その構造的依存関係に応じてノード間の相互作用をキャプチャするグラフマルチセットトランス (GMT) を提案する。 実験の結果,GMTはグラフ分類ベンチマークにおいて,最先端のグラフプーリング法を著しく上回っていることがわかった。
  論文  参考訳（メタデータ） (2021-02-23T07:45:58Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。 粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
  論文  参考訳（メタデータ） (2021-02-02T06:50:07Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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