論文の概要: Signed Graph Learning: Algorithms and Theory

• arxiv url: http://arxiv.org/abs/2507.09717v1
• Date: Sun, 13 Jul 2025 17:33:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:23.865132
• Title: Signed Graph Learning: Algorithms and Theory
• Title（参考訳）: サイン付きグラフ学習:アルゴリズムと理論
• Authors: Abdullah Karaaslanli, Bisakh Banerjee, Tapabrata Maiti, Selin Aviyente,
• Abstract要約: 実世界のデータは、しばしばデータサンプル間の関係を通して表現され、グラフ構造を形成する。 現在のグラフ学習研究は主に符号なしグラフに焦点を当てている。 我々はスムーズな符号付きグラフ信号の集合をキャプチャする手法を開発した。
• 参考スコア（独自算出の注目度）: 17.374356596021936
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Real-world data is often represented through the relationships between data samples, forming a graph structure. In many applications, it is necessary to learn this graph structure from the observed data. Current graph learning research has primarily focused on unsigned graphs, which consist only of positive edges. However, many biological and social systems are better described by signed graphs that account for both positive and negative interactions, capturing similarity and dissimilarity between samples. In this paper, we develop a method for learning signed graphs from a set of smooth signed graph signals. Specifically, we employ the net Laplacian as a graph shift operator (GSO) to define smooth signed graph signals as the outputs of a low-pass signed graph filter defined by the net Laplacian. The signed graph is then learned by formulating a non-convex optimization problem where the total variation of the observed signals is minimized with respect to the net Laplacian. The proposed problem is solved using alternating direction method of multipliers (ADMM) and a fast algorithm reducing the per-ADMM iteration complexity from quadratic to linear in the number of nodes is introduced. Furthermore, theoretical proofs of convergence for the algorithm and a bound on the estimation error of the learned net Laplacian as a function of sample size, number of nodes, and graph topology are provided. Finally, the proposed method is evaluated on simulated data and gene regulatory network inference problem and compared to existing signed graph learning methods.
• Abstract（参考訳）: 実世界のデータは、しばしばデータサンプル間の関係を通して表現され、グラフ構造を形成する。 多くのアプリケーションでは、観測データからこのグラフ構造を学習する必要がある。 現在のグラフ学習研究は、主に正のエッジのみからなる符号なしグラフに焦点を当てている。 しかし、多くの生物学的・社会的システムは、正の相互作用と負の相互作用の両方を考慮し、サンプル間の類似性や相違性をとらえる符号付きグラフによってよりよく説明されている。 本論文では,スムーズな符号付きグラフ信号の集合から符号付きグラフを学習する手法を開発する。 具体的には、ネットラプラシアンをグラフシフト演算子(GSO)として使用し、スムーズな符号付きグラフ信号を、ネットラプラシアンによって定義された低域符号付きグラフフィルタの出力として定義する。 符号付きグラフは非凸最適化問題を定式化することにより学習され、観測された信号の総変動はネットラプラシアンに対して最小化される。 提案手法は乗算器の交互方向法(ADMM)と高速アルゴリズムを用いて,ノード数を2次から線形に減らした。 さらに、アルゴリズムの収束の理論的証明と、サンプルサイズ、ノード数、グラフトポロジの関数としての学習ネットラプラシアンの推定誤差のバウンドが提供される。 最後に、シミュレーションデータと遺伝子制御ネットワークの推論問題に基づいて、既存の符号付きグラフ学習法と比較した。

関連論文リスト

• Online Proximal ADMM for Graph Learning from Streaming Smooth Signals [9.34612743192798]
  我々は,潜伏グラフ上でスムーズな観測ストリームを用いたオンライングラフ学習のための新しいアルゴリズムを開発した。 我々のモダス・オペランは、グラフ信号を逐次処理し、メモリと計算コストを抑えることです。 提案手法は,現在最先端のオンライングラフ学習ベースラインと比較して,(準最適性の観点から)追跡性能が向上することを示す。
  論文  参考訳（メタデータ） (2024-09-19T17:12:03Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Graph Laplacian Learning with Exponential Family Noise [8.594140167290098]
  指数関数的家族雑音によるグラフ信号から学習するための多目的グラフ推論フレームワークを提案する。 本フレームワークは,連続的なスムーズなグラフ信号から様々なデータタイプまで,従来の手法を一般化する。
  論文  参考訳（メタデータ） (2023-06-14T02:09:52Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。 これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。 我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
  論文  参考訳（メタデータ） (2022-12-15T22:11:34Z)
• Signed Graph Neural Networks: A Frequency Perspective [14.386571627652975]
  グラフ畳み込みネットワーク(GCN)は、正のリンクのみを含む符号なしグラフ用に設計されている。 我々は2つの異なる符号付きグラフニューラルネットワークを提案し、その1つは低周波情報のみを保持し、もう1つは高周波情報を保持する。
  論文  参考訳（メタデータ） (2022-08-15T16:42:18Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
  ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。 本稿では,2つのクラスタリングアルゴリズムについて述べる。 さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
  論文  参考訳（メタデータ） (2021-10-06T13:14:44Z)
• 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)

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

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