論文の概要: Learning Product Graphs Underlying Smooth Graph Signals
- arxiv url: http://arxiv.org/abs/2002.11277v2
- Date: Fri, 12 Jun 2020 21:16:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-28 15:46:07.384567
- Title: Learning Product Graphs Underlying Smooth Graph Signals
- Title(参考訳): 滑らかなグラフ信号に基づく学習製品グラフ
- Authors: Muhammad Asad Lodhi and Waheed U. Bajwa
- Abstract要約: 本稿では,製品グラフの形式で与えられるデータから構造化グラフを学習する方法を考案する。
この目的のために、まずグラフ学習問題は線形プログラムとして表され、これは(平均的に)最先端のグラフ学習アルゴリズムより優れている。
- 参考スコア(独自算出の注目度): 15.023662220197242
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Real-world data is often times associated with irregular structures that can
analytically be represented as graphs. Having access to this graph, which is
sometimes trivially evident from domain knowledge, provides a better
representation of the data and facilitates various information processing
tasks. However, in cases where the underlying graph is unavailable, it needs to
be learned from the data itself for data representation, data processing and
inference purposes. Existing literature on learning graphs from data has mostly
considered arbitrary graphs, whereas the graphs generating real-world data tend
to have additional structure that can be incorporated in the graph learning
procedure. Structure-aware graph learning methods require learning fewer
parameters and have the potential to reduce computational, memory and sample
complexities. In light of this, the focus of this paper is to devise a method
to learn structured graphs from data that are given in the form of product
graphs. Product graphs arise naturally in many real-world datasets and provide
an efficient and compact representation of large-scale graphs through several
smaller factor graphs. To this end, first the graph learning problem is posed
as a linear program, which (on average) outperforms the state-of-the-art graph
learning algorithms. This formulation is of independent interest itself as it
shows that graph learning is possible through a simple linear program.
Afterwards, an alternating minimization-based algorithm aimed at learning
various types of product graphs is proposed, and local convergence guarantees
to the true solution are established for this algorithm. Finally the
performance gains, reduced sample complexity, and inference capabilities of the
proposed algorithm over existing methods are also validated through numerical
simulations on synthetic and real datasets.
- Abstract(参考訳): 現実世界のデータはしばしば、分析的にグラフとして表現できる不規則な構造に関連付けられる。
このグラフへのアクセスは、時にドメインの知識から自明であり、データのより良い表現を提供し、様々な情報処理タスクを促進する。
しかし、基礎となるグラフが利用できない場合、データ表現、データ処理、推論目的のためにデータ自身から学ぶ必要がある。
データからの学習グラフに関する既存の文献は、主に任意のグラフと見なされているが、実際のデータを生成するグラフは、グラフ学習手順に組み込むことができる追加構造を持つ傾向がある。
構造対応グラフ学習法は、少ないパラメータを学習し、計算、メモリ、サンプルの複雑さを減らし得る。
そこで本研究では,製品グラフの形式で提供されるデータから構造化グラフを学習する方法を考案する。
製品グラフは多くの実世界のデータセットに自然に現れ、いくつかの小さな因子グラフを通して大規模グラフの効率的かつコンパクトな表現を提供する。
この目的のために、まず、グラフ学習問題は(平均して)最先端のグラフ学習アルゴリズムを上回る線形プログラムとして提示される。
この定式化は、単純な線形プログラムを通じてグラフ学習が可能であることを示すため、独立した関心を持つ。
その後、様々な種類の製品グラフを学習するための交互最小化に基づくアルゴリズムを提案し、真の解に対する局所収束保証を確立する。
最後に,合成データと実データを用いた数値シミュレーションにより,提案アルゴリズムの性能向上,サンプル複雑性の低減,既存手法に対する推論能力を検証する。
関連論文リスト
- Joint Signal Recovery and Graph Learning from Incomplete Time-Series [24.308357458676937]
本研究では,不完全な時系列観測からグラフを学習することを目的とする。
逐次上向き最小化をブロックする手法に基づくアルゴリズムを提案する。
合成時系列と実時間時系列のシミュレーション結果から,提案手法の性能を実証した。
論文 参考訳(メタデータ) (2023-12-28T10:27:04Z) - The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph
Structure [18.00833762891405]
Graph Lottery Ticket (GLT)仮説: グラフごとに非常に疎いバックボーンが存在する。
本研究は,グラフ学習アルゴリズムの性能に直接影響を及ぼす関心の指標を8つ研究する。
任意のグラフでこれらのGLTを見つけるための単純で効率的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T00:24:44Z) - GraphGLOW: Universal and Generalizable Structure Learning for Graph
Neural Networks [72.01829954658889]
本稿では,この新たな問題設定の数学的定義を紹介する。
一つのグラフ共有構造学習者と複数のグラフ固有GNNを協調する一般的なフレームワークを考案する。
十分に訓練された構造学習者は、微調整なしで、目に見えない対象グラフの適応的な構造を直接生成することができる。
論文 参考訳(メタデータ) (2023-06-20T03:33:22Z) - Bures-Wasserstein Means of Graphs [60.42414991820453]
本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。
この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。
我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
論文 参考訳(メタデータ) (2023-05-31T11:04:53Z) - Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
コントラスト学習は、監督の有無にかかわらず、表現を学習するための第一の方法として現れてきた。
近年の研究では、グラフ表現学習における事前学習の有用性が示されている。
本稿では,グラフの対照的な目的に対する拡張を構築する際に,候補のバンクを提供するためのグラフ変換操作を提案する。
論文 参考訳(メタデータ) (2023-02-06T16:26:29Z) - State of the Art and Potentialities of Graph-level Learning [54.68482109186052]
グラフレベルの学習は、比較、回帰、分類など、多くのタスクに適用されている。
グラフの集合を学習する伝統的なアプローチは、サブストラクチャのような手作りの特徴に依存している。
ディープラーニングは、機能を自動的に抽出し、グラフを低次元表現に符号化することで、グラフレベルの学習をグラフの規模に適応させるのに役立っている。
論文 参考訳(メタデータ) (2023-01-14T09:15:49Z) - Heterogeneous Graph Sparsification for Efficient Representation Learning [15.075580975708654]
本研究では,スパーシファイアを構築するためのサンプリングベースアルゴリズムを開発し,元のグラフにおける重要な情報を確実に疎外し,保存する。
我々は,提案手法が表現学習の時間と空間の複雑さを向上すると同時に,その後のグラフ学習タスクにおいて同等あるいはさらに優れた性能を達成できることを示すため,広範囲な実験を行った。
論文 参考訳(メタデータ) (2022-11-14T16:47:06Z) - Synthetic Graph Generation to Benchmark Graph Learning [7.914804101579097]
グラフ学習アルゴリズムは多くのグラフ解析タスクで最先端のパフォーマンスを達成した。
1つの理由は、グラフ学習アルゴリズムのパフォーマンスをベンチマークするために実際に使用されるデータセットが極めて少ないためである。
本稿では,合成グラフの生成と,制御シナリオにおけるグラフ学習アルゴリズムの挙動について検討する。
論文 参考訳(メタデータ) (2022-04-04T10:48:32Z) - Product Graph Learning from Multi-domain Data with Sparsity and Rank
Constraints [17.15829643665034]
データからスパース製品グラフを学習するための効率的な反復解法を提案する。
このソルバーを拡張して、製品グラフクラスタリングに応用したマルチコンポーネントグラフファクタを推論します。
提案手法の有効性を,合成データと実データに関する数値実験を用いて実証した。
論文 参考訳(メタデータ) (2020-12-15T04:59:32Z) - GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
本稿では,グラフ構造形成の暗黙的モデルを学ぶエンドツーエンドフレームワークを提案し,その基盤となる最適化機構を明らかにする。
学習した目的は、観測されたグラフプロパティの説明として機能し、ドメイン内の異なるグラフを渡すために自分自身を貸すことができる。
GraphOptは、グラフ内のリンク生成をシーケンシャルな意思決定プロセスとして、最大エントロピー逆強化学習アルゴリズムを用いて解決する。
論文 参考訳(メタデータ) (2020-07-07T16:51:39Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳(メタデータ) (2020-06-19T13:09:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。