論文の概要: Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment

• arxiv url: http://arxiv.org/abs/2208.08726v1
• Date: Thu, 18 Aug 2022 09:19:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-19 14:09:08.282322
• Title: Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment
• Title（参考訳）: balance & gershgorin disc perfect alignmentによる効率的な符号付きグラフサンプリング
• Authors: Chinthaka Dinesh, Gene Cheung, Saghar Bagheri, Ivan V. Bajic
• Abstract要約: 強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
• 参考スコア（独自算出の注目度）: 51.74913666829224
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A basic premise in graph signal processing (GSP) is that a graph encoding pairwise (anti-)correlations of the targeted signal as edge weights is exploited for graph filtering. However, existing fast graph sampling schemes are designed and tested only for positive graphs describing positive correlations. In this paper, we show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. In response, we propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Specifically, given an empirical covariance data matrix $\bar{\bf{C}}$, we first learn a sparse inverse matrix (graph Laplacian) $\mathcal{L}$ corresponding to a signed graph $\mathcal{G}$. We define the eigenvectors of Laplacian $\mathcal{L}_B$ for a balanced signed graph $\mathcal{G}_B$ -- approximating $\mathcal{G}$ via edge weight augmentation -- as graph frequency components. Next, we choose samples to minimize the low-pass filter reconstruction error in two steps. We first align all Gershgorin disc left-ends of Laplacian $\mathcal{L}_B$ at smallest eigenvalue $\lambda_{\min}(\mathcal{L}_B)$ via similarity transform $\mathcal{L}_p = \S \mathcal{L}_B \S^{-1}$, leveraging a recent linear algebra theorem called Gershgorin disc perfect alignment (GDPA). We then perform sampling on $\mathcal{L}_p$ using a previous fast Gershgorin disc alignment sampling (GDAS) scheme. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
• Abstract（参考訳）: グラフ信号処理(GSP)の基本前提は、エッジ重みとしてターゲット信号のペアワイズ(アンチ)相関を符号化したグラフをグラフフィルタリングに利用することである。 しかし、既存の高速グラフサンプリングスキームは正の相関を記述した正のグラフに対してのみ設計・試験されている。 本稿では,強い反相関を持つデータセットに対して,正と負の両方のエッジ重みを含むグラフを示す。 そこで本研究では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 具体的には、経験的共分散データ行列 $\bar{\bf{C}}$ が与えられたとき、まず、符号付きグラフ $\mathcal{G}$ に対応するスパース逆行列 (グラフ Laplacian) $\mathcal{L}$ を学ぶ。 ラプラシアン $\mathcal{L}_B$ の固有ベクトルを、バランスの取れた符号グラフ $\mathcal{G}_B$ -- エッジウェイト拡張による $\mathcal{G}$ をグラフ周波数成分として定義する。 次に、低パスフィルタ再構成誤差を2ステップで最小化するサンプルを選択する。 まず、ラプラシアン $\mathcal{l}_b$ のすべてのゲルシュゴリン円板左端を最小の固有値 $\lambda_{\min}(\mathcal{l}_b)$ で整列し、類似性変換 $\mathcal{l}_p = \s \mathcal{l}_b \s^{-1}$ を用いて、ゲルシュゴリン円板完全整列 (gdpa) と呼ばれる最近の線形代数定理を利用する。 次に、以前のfast gershgorin disc alignment sampling (gdas) スキームを用いて$\mathcal{l}_p$のサンプリングを行う。 実験の結果, 有署名グラフサンプリング手法は, 既存の高速サンプリング方式を, 様々なデータセット上で明らかに上回っていた。

関連論文リスト

• Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming [26.334739062500674]
  データから直接バランスの取れたラプラシアングラフを学習する高速な手法を提案する。 合成および実世界のデータセットに対する実験により、バランスの取れたグラフ学習法が競合する手法より優れていることが示された。
  論文  参考訳（メタデータ） (2024-09-12T06:53:50Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
  グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。 ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。 代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
  論文  参考訳（メタデータ） (2021-06-03T07:22:48Z)
• Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection [58.5350491065936]
  グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。 最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。 本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-10-25T18:12:50Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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