論文の概要: Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming

• arxiv url: http://arxiv.org/abs/2409.07794v1
• Date: Thu, 12 Sep 2024 06:53:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-13 17:27:46.009776
• Title: Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming
• Title（参考訳）: 反復線形計画法によるバランス付符号グラフの効率的な学習
• Authors: Haruki Yokota, Hiroshi Higashi, Yuichi Tanaka, Gene Cheung,
• Abstract要約: データから直接バランスの取れたラプラシアングラフを学習する高速な手法を提案する。 合成および実世界のデータセットに対する実験により、バランスの取れたグラフ学習法が競合する手法より優れていることが示された。
• 参考スコア（独自算出の注目度）: 26.334739062500674
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.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 has no cycles of odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map simply to ones in a similarity-transformed positive graph Laplacian, thus enabling reuse of well-studied spectral filters designed for positive graphs. We propose a fast method to learn a balanced signed graph Laplacian directly from data. Specifically, for each node $i$, to determine its polarity $\beta_i \in \{-1,1\}$ and edge weights $\{w_{i,j}\}_{j=1}^N$, we extend a sparse inverse covariance formulation based on linear programming (LP) called CLIME, by adding linear constraints to enforce ``consistent" signs of edge weights $\{w_{i,j}\}_{j=1}^N$ with the polarities of connected nodes -- i.e., positive/negative edges connect nodes of same/opposing polarities. For each LP, we adapt projections on convex set (POCS) to determine a suitable CLIME parameter $\rho > 0$ that guarantees LP feasibility. We solve the resulting LP via an off-the-shelf LP solver in $\mathcal{O}(N^{2.055})$. Experiments on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables the use of spectral filters and graph convolutional networks (GCNs) designed for positive graphs on signed graphs.
• Abstract（参考訳）: 符号付きグラフは、正と負の両方のエッジウェイトを備え、データ内の反相関と同様にペアの相関を符号化する。 バランスの取れた符号付きグラフは、奇数の負のエッジのサイクルを持たない。 バランスの取れた符号グラフのラプラシアンは、類似性変換された正グラフラプラシアンにおいて単にそれに対応する固有ベクトルを持ち、したがって正グラフのために設計されたよく研究されたスペクトルフィルタの再利用を可能にする。 データから直接バランスの取れたラプラシアングラフを学習する高速な手法を提案する。 具体的には、各ノード $i$ に対して、その極性 $\beta_i \in \{-1,1\}$ とエッジウェイト $\{w_{i,j}\}_{j=1}^N$ を判定するために、CLIME と呼ばれる線形プログラミング (LP) に基づくスパース逆共分散の定式化を拡張し、エッジウェイト $\{w_{i,j}\}_{j=1}^N$ と接続ノードの極性 -- すなわち、正負のエッジが同じ/対極性のノードを接続する。 各LPに対して、コンベックスセット(POCS)上のプロジェクションを適用して、LPの実現性を保証する適切なCLIMEパラメータ$\rho > 0$を決定する。 我々は、既製のLPソルバを$\mathcal{O}(N^{2.055})$で解く。 合成および実世界のデータセットに対する実験により、我々のバランスの取れたグラフ学習法は競合する手法よりも優れており、符号付きグラフ上の正のグラフのために設計されたスペクトルフィルタとグラフ畳み込みネットワーク(GCN)の使用を可能にしている。

関連論文リスト

• 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 Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests [8.30255326875704]
  磁気ラプラシアン$Delta$,すなわち,エッジの少ない部分グラフに基づくスペクトル近似のスペーサーについて検討する。 ラプラシアン接続の自然推定器の選択に関する統計的保証を提供する。 本稿では,角度同期型ランキングとグラフに基づく半教師付き学習の2つの実用的応用について検討する。
  論文  参考訳（メタデータ） (2022-08-31T12:23:53Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Correlation detection in trees for partial graph alignment [3.5880535198436156]
  グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。 我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。 この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
  論文  参考訳（メタデータ） (2021-07-15T22:02:27Z)
• 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)

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

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