論文の概要: A Unified Framework for Optimization-Based Graph Coarsening
- arxiv url: http://arxiv.org/abs/2210.00437v1
- Date: Sun, 2 Oct 2022 06:31:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 14:31:55.214904
- Title: A Unified Framework for Optimization-Based Graph Coarsening
- Title(参考訳): 最適化に基づくグラフ粗粒化のための統一フレームワーク
- Authors: Manoj Kumar, Anurag Sharma, Sandeep Kumar
- Abstract要約: 大きなグラフが与えられたとき、グラフ粗化は、もともと与えられたグラフの特性を保ちながら、より小さく抽出可能なグラフを学習することを目的としている。
提案するフレームワークは,グラフ学習と次元減少の一体化にある。
学習された粗大化グラフは、元のグラフと類似した$epsin(0,1)$であることが確立されている。
- 参考スコア(独自算出の注目度): 5.720402020129441
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Graph coarsening is a widely used dimensionality reduction technique for
approaching large-scale graph machine learning problems. Given a large graph,
graph coarsening aims to learn a smaller-tractable graph while preserving the
properties of the originally given graph. Graph data consist of node features
and graph matrix (e.g., adjacency and Laplacian). The existing graph coarsening
methods ignore the node features and rely solely on a graph matrix to simplify
graphs. In this paper, we introduce a novel optimization-based framework for
graph dimensionality reduction. The proposed framework lies in the unification
of graph learning and dimensionality reduction. It takes both the graph matrix
and the node features as the input and learns the coarsen graph matrix and the
coarsen feature matrix jointly while ensuring desired properties. The proposed
optimization formulation is a multi-block non-convex optimization problem,
which is solved efficiently by leveraging block majorization-minimization,
$\log$ determinant, Dirichlet energy, and regularization frameworks. The
proposed algorithms are provably convergent and practically amenable to
numerous tasks. It is also established that the learned coarsened graph is
$\epsilon\in(0,1)$ similar to the original graph. Extensive experiments
elucidate the efficacy of the proposed framework for real-world applications.
- Abstract(参考訳): グラフ粗化(Graph coarsening)は、大規模グラフ機械学習問題にアプローチするために広く用いられている次元削減手法である。
大きなグラフが与えられると、グラフの粗さ化は、元々与えられたグラフの性質を維持しながら、より小さなグラフを学習することを目的としている。
グラフデータはノードの特徴とグラフ行列(例えば、隣接とラプラシアン)から構成される。
既存のグラフ粗い方法はノードの特徴を無視し、グラフを単純化するためにグラフマトリックスのみに依存する。
本稿では,グラフ次元削減のための新しい最適化フレームワークを提案する。
提案するフレームワークは,グラフ学習と次元減少の一体化にある。
グラフマトリクスとノードの特徴の両方を入力とし、望ましい特性を確保しながら粗いグラフマトリクスと粗い特徴マトリクスを共同で学習する。
提案手法は,ブロックの最大化最小化,$\log$決定式,ディリクレエネルギー,正規化フレームワークを活用することで効率よく解けるマルチブロック非凸最適化問題である。
提案手法は, 有理収束性があり, 実用上, 多数のタスクに適応可能である。
また、学習された粗いグラフは元のグラフに類似した$\epsilon\in(0,1)$であることが判明した。
大規模な実験により,提案フレームワークの有効性が解明された。
関連論文リスト
- The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph
Structure [18.00833762891405]
Graph Lottery Ticket (GLT)仮説: グラフごとに非常に疎いバックボーンが存在する。
本研究は,グラフ学習アルゴリズムの性能に直接影響を及ぼす関心の指標を8つ研究する。
任意のグラフでこれらのGLTを見つけるための単純で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T00:24:44Z) - Structure-free Graph Condensation: From Large-scale Graphs to Condensed
Graph-free Data [91.27527985415007]
既存のグラフ凝縮法は、凝縮グラフ内のノードと構造の合同最適化に依存している。
我々は、大規模グラフを小さなグラフノード集合に蒸留する、SFGCと呼ばれる新しい構造自由グラフ凝縮パラダイムを提唱する。
論文 参考訳(メタデータ) (2023-06-05T07:53:52Z) - Hyperparameter-free and Explainable Whole Graph Embedding [16.03671347701557]
グラフ表現学習は、各ノードまたはグラフ全体の低次元表現ベクトルを学習しようとする。
本稿では,DHC(Degree, H-index, Coreness)定理とシャノンエントロピー(E)を組み合わせた新しいグラフ埋め込み法を提案する。
提案手法は低次元グラフの可視化において優れた性能を有する。
論文 参考訳(メタデータ) (2021-08-04T15:30:52Z) - Optimization-Based Algebraic Multigrid Coarsening Using Reinforcement
Learning [0.0]
線型方程式の系は未知の集合上のグラフを定義する。
多重グリッドソルバの各レベルは、粗グラフの適切な選択と、粗表現への写像と演算子を必要とする。
粗いグラフ選択を条件として、AMGと制限演算子を直接学習できることが示されている。
グラフニューラルネットワーク(GNN)に基づく強化学習エージェントを用いたスパース手法を提案する。
論文 参考訳(メタデータ) (2021-06-03T13:57:32Z) - Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。
与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。
実験の結果,本手法は著しい改善をもたらすことがわかった。
論文 参考訳(メタデータ) (2021-03-30T17:36:40Z) - Graph Coarsening with Neural Networks [8.407217618651536]
本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。
粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
論文 参考訳(メタデータ) (2021-02-02T06:50:07Z) - Product Graph Learning from Multi-domain Data with Sparsity and Rank
Constraints [17.15829643665034]
データからスパース製品グラフを学習するための効率的な反復解法を提案する。
このソルバーを拡張して、製品グラフクラスタリングに応用したマルチコンポーネントグラフファクタを推論します。
提案手法の有効性を,合成データと実データに関する数値実験を用いて実証した。
論文 参考訳(メタデータ) (2020-12-15T04:59:32Z) - 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) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z) - Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
グラフオートエンコーダ(GAE)は、グラフ埋め込みのための表現学習において強力なツールである。
本稿では,2つの新しい教師なしグラフ埋め込み法,適応グラフ学習(BAGE)による教師なしグラフ埋め込み,変分適応グラフ学習(VBAGE)による教師なしグラフ埋め込みを提案する。
いくつかのデータセットに関する実験的研究により、我々の手法がノードクラスタリング、ノード分類、グラフ可視化タスクにおいて、ベースラインよりも優れていることが実証された。
論文 参考訳(メタデータ) (2020-03-10T02:33:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。