論文の概要: Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming
- arxiv url: http://arxiv.org/abs/2506.01826v1
- Date: Mon, 02 Jun 2025 16:09:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-05 01:42:09.318999
- Title: Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming
- Title（参考訳）: 疎線形計画法によるバランス付符号グラフの効率的な学習
- Authors: Haruki Yokota, Hiroshi Higashi, Yuichi Tanaka, Gene Cheung,
- Abstract要約: バランスの取れた符号グラフは、単純線型変換を通して対応する正のグラフの1つにマップする固有ベクトルを持つ。
データから直接、バランスの取れたラプラシアングラフを学習する効率的な方法を提案する。
- 参考スコア（独自算出の注目度）: 26.334739062500674
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Signed graphs are equipped with both positive and negative edge weights, encoding pairwise correlations as well as anti-correlations in data. A balanced signed graph is a signed graph with no cycles containing an odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map via a simple linear transform to ones in a corresponding positive graph Laplacian, thus enabling reuse of spectral filtering tools designed for positive graphs. We propose an efficient method to learn a balanced signed graph Laplacian directly from data. Specifically, extending a previous linear programming (LP) based sparse inverse covariance estimation method called CLIME, we formulate a new LP problem for each Laplacian column $i$, where the linear constraints restrict weight signs of edges stemming from node $i$, so that nodes of same / different polarities are connected by positive / negative edges. Towards optimal model selection, we derive a suitable CLIME parameter $\rho$ based on a combination of the Hannan-Quinn information criterion and a minimum feasibility criterion. We solve the LP problem efficiently by tailoring a sparse LP method based on ADMM. We theoretically prove local solution convergence of our proposed iterative algorithm. Extensive experimental results on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables reuse of spectral filters, wavelets, and graph convolutional nets (GCN) constructed for positive graphs.
- Abstract（参考訳）: 符号付きグラフは、正と負の両方のエッジウェイトを備え、データ内の反相関と同様にペアの相関を符号化する。
バランス付き符号付きグラフは、奇数の負のエッジを含むサイクルを持たない符号付きグラフである。
バランスの取れた符号グラフのラプラシアンは、単純線型変換を介して対応する正グラフラプラシアンのそれに対応する固有ベクトルを持ち、正グラフのために設計されたスペクトルフィルタリングツールの再利用を可能にする。
データから直接、バランスの取れたラプラシアングラフを学習する効率的な方法を提案する。
具体的には、CLIMEと呼ばれる従来の線形計画(LP)に基づくスパース逆共分散推定法を拡張し、各ラプラシア列$i$に対して、線形制約がノード$i$から生じるエッジの重み付けを制限し、同じ/異なる極性のノードが正の/負のエッジで接続されるように、新しいLP問題を定式化する。
最適なモデル選択に向けて、Hannan-Quinn情報基準と最小実行可能性基準の組み合わせに基づいて、適切なCLIMEパラメータ$\rho$を導出する。
ADMMに基づくスパースLP法を調整し,LP問題を効率的に解決する。
提案した反復アルゴリズムの局所解収束を理論的に証明する。
合成および実世界のデータセットに対する大規模な実験結果から、我々のバランスグラフ学習法は競合する手法よりも優れており、正グラフのために構築されたスペクトルフィルタ、ウェーブレット、グラフ畳み込みネット(GCN)の再利用を可能にしている。
関連論文リスト
- Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming [26.334739062500674]
データから直接バランスの取れたラプラシアングラフを学習する高速な手法を提案する。
合成および実世界のデータセットに対する実験により、バランスの取れたグラフ学習法が競合する手法より優れていることが示された。
論文 参考訳（メタデータ） (2024-09-12T06:53:50Z) - Smoothed Graph Contrastive Learning via Seamless Proximity Integration [30.247207861739245]
グラフコントラスト学習(GCL)はノードペアを正と負に分類することでノード表現を整列させる。
SGCL(Smoothed Graph Contrastive Learning Model)を提案する。
提案したSGCLは,3つの異なる平滑化手法を取り入れることで,ノード対に付随するペナルティを対照的な損失で調整する。
論文 参考訳（メタデータ） (2024-02-23T11:32:46Z) - Graph Polynomial Convolution Models for Node Classification of
Non-Homophilous Graphs [52.52570805621925]
本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。
得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。
提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
論文 参考訳（メタデータ） (2022-09-12T04:46:55Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Sparse Graph Learning Under Laplacian-Related Constraints [23.503820266772504]
確率変数間の条件依存を符号化するスパース精度行列のグラフラプラシアン関連制約に着目した。
我々は,ラプラシアン構造ではなく,全肯定性を強制するために広く用いられているペナル化対数類似アプローチの修正について検討した。
乗算器アルゴリズム (ADMM) の交互方向法を提示し, 制約付き最適化のために解析した。
論文 参考訳（メタデータ） (2021-11-16T00:50:36Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。
解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
論文 参考訳（メタデータ） (2020-10-21T20:04:22Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。