論文の概要: A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening

• arxiv url: http://arxiv.org/abs/2306.08854v1
• Date: Thu, 15 Jun 2023 04:47:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 16:33:37.050800
• Title: A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening
• Title（参考訳）: gromov-wassersteinによるスペクトル保存グラフ粗さの幾何学的展望
• Authors: Yifan Chen, Rentian Yao, Yun Yang, Jie Chen
• Abstract要約: この研究はグラフの粗大化を別の観点から研究し、グラフ距離を保存する理論を発展させた。 幾何学的アプローチは、グラフ分類や回帰のようなグラフの集合を扱う際に有用である。 この差を最小化するには、一般的な重み付きカーネル$K$-means法を用いる。
• 参考スコア（独自算出の注目度）: 19.09507367362567
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph coarsening is a technique for solving large-scale graph problems by working on a smaller version of the original graph, and possibly interpolating the results back to the original graph. It has a long history in scientific computing and has recently gained popularity in machine learning, particularly in methods that preserve the graph spectrum. This work studies graph coarsening from a different perspective, developing a theory for preserving graph distances and proposing a method to achieve this. The geometric approach is useful when working with a collection of graphs, such as in graph classification and regression. In this study, we consider a graph as an element on a metric space equipped with the Gromov--Wasserstein (GW) distance, and bound the difference between the distance of two graphs and their coarsened versions. Minimizing this difference can be done using the popular weighted kernel $K$-means method, which improves existing spectrum-preserving methods with the proper choice of the kernel. The study includes a set of experiments to support the theory and method, including approximating the GW distance, preserving the graph spectrum, classifying graphs using spectral information, and performing regression using graph convolutional networks. Code is available at https://github.com/ychen-stat-ml/GW-Graph-Coarsening .
• Abstract（参考訳）: グラフ粗化(Graph coarsening)は、元のグラフのより小さなバージョンに取り組み、その結果を元のグラフに補間することで、大規模なグラフ問題を解決する手法である。 科学計算において長い歴史があり、最近では機械学習、特にグラフスペクトルを保存する手法で人気を博している。 この研究はグラフの粗化を別の観点から研究し、グラフ距離を保存する理論を開発し、これを実現する方法を提案する。 幾何学的アプローチは、グラフの分類や回帰といったグラフの集合を扱う際に有用である。 本研究では、グラフをGromov-Wasserstein (GW) 距離を備えた距離空間上の要素とみなし、2つのグラフの距離とそれらの粗いバージョンとの差を限定する。 この差を最小限に抑えるには、カーネルの適切な選択で既存のスペクトル保存法を改善するK$-means法が一般的である。 本研究は、gw距離の近似化、グラフスペクトルの保存、スペクトル情報を用いたグラフの分類、グラフ畳み込みネットワークを用いた回帰など、理論と方法をサポートする一連の実験を含む。 コードはhttps://github.com/ychen-stat-ml/gw-graph-coarseningで入手できる。

関連論文リスト

• GSINA: Improving Subgraph Extraction for Graph Invariant Learning via Graph Sinkhorn Attention [52.67633391931959]
  グラフ不変学習(GIL)は,グラフデータとそのラベル間の不変性を発見するための効果的な手法である。 グラフシンクホーン注意機構(GSINA)を提案する。 GSINAは、制御可能な空間性と柔らかさを持つ有意義で微分可能な不変部分グラフを得ることができる。
  論文  参考訳（メタデータ） (2024-02-11T12:57:16Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• A Unified Framework for Optimization-Based Graph Coarsening [5.720402020129441]
  大きなグラフが与えられたとき、グラフ粗化は、もともと与えられたグラフの特性を保ちながら、より小さく抽出可能なグラフを学習することを目的としている。 提案するフレームワークは,グラフ学習と次元減少の一体化にある。 学習された粗大化グラフは、元のグラフと類似した$epsin(0,1)$であることが確立されている。
  論文  参考訳（メタデータ） (2022-10-02T06:31:42Z)
• Scaling R-GCN Training with Graph Summarization [71.06855946732296]
  リレーショナルグラフ畳み込みネットワーク(R-GCN)のトレーニングは、グラフのサイズに合わない。 本研究では,グラフの要約手法を用いてグラフを圧縮する実験を行った。 AIFB, MUTAG, AMデータセットについて妥当な結果を得た。
  論文  参考訳（メタデータ） (2022-03-05T00:28:43Z)
• Graph coarsening: From scientific computing to machine learning [11.728753892489776]
  本研究の目的は,科学計算に成功している粗大化手法を幅広く検討することである。 機械学習では、グラフ粗化は、グラフダウンサンプリングやグラフリダクションなど、様々な名前で呼ばれる。 このように、これらの方法の一般的な戦略は、粗グラフを定義するためにスペクトル特性に依存することである。
  論文  参考訳（メタデータ） (2021-06-22T15:31:50Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。 粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
  論文  参考訳（メタデータ） (2021-02-02T06:50:07Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。 グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。 幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-12-30T18:51:06Z)
• Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
  本稿では,graphonと呼ばれる非パラメトリックグラフモデルを学ぶための新しい原理的手法を提案する。 提案手法は, 従来の最先端手法の欠点を克服し, 合成データと実データの両方でそれを上回る。
  論文  参考訳（メタデータ） (2020-12-10T13:04:29Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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