論文の概要: Searching for polarization in signed graphs: a local spectral approach
- arxiv url: http://arxiv.org/abs/2001.09410v1
- Date: Sun, 26 Jan 2020 06:30:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 23:27:21.909451
- Title: Searching for polarization in signed graphs: a local spectral approach
- Title（参考訳）: 符号付きグラフにおける偏光探索:局所スペクトルアプローチ
- Authors: Han Xiao, Bruno Ordozgoiti, Aristides Gionis
- Abstract要約: 本稿では、符号付きグラフにおける局所偏極群を局所バイアス固有確率として求める問題を定式化する。
局所バイアスベクトルは符号付きグラフ上のチェーガー定数の局所的な類似点に関して近似保証付きコミュニティを見つけるのに利用できることを示す。
- 参考スコア（独自算出の注目度）: 16.384728228938574
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Signed graphs have been used to model interactions in social net-works, which
can be either positive (friendly) or negative (antagonistic). The model has
been used to study polarization and other related phenomena in social networks,
which can be harmful to the process of democratic deliberation in our society.
An interesting and challenging task in this application domain is to detect
polarized communities in signed graphs. A number of different methods have been
proposed for this task. However, existing approaches aim at finding globally
optimal solutions. Instead, in this paper we are interested in finding
polarized communities that are related to a small set of seed nodes provided as
input. Seed nodes may consist of two sets, which constitute the two sides of a
polarized structure.
In this paper we formulate the problem of finding local polarized communities
in signed graphs as a locally-biased eigen-problem. By viewing the eigenvector
associated with the smallest eigenvalue of the Laplacian matrix as the solution
of a constrained optimization problem, we are able to incorporate the local
information as an additional constraint. In addition, we show that the
locally-biased vector can be used to find communities with approximation
guarantee with respect to a local analogue of the Cheeger constant on signed
graphs. By exploiting the sparsity in the input graph, an indicator vector for
the polarized communities can be found in time linear to the graph size.
Our experiments on real-world networks validate the proposed algorithm and
demonstrate its usefulness in finding local structures in this semi-supervised
manner.
- Abstract（参考訳）: サイン付きグラフは、ポジティブ(親しみやすい)かネガティブ(敵対的な)のいずれかの相互作用をモデル化するために使われてきた。
このモデルは、社会における民主的熟考の過程に有害な、ソーシャルネットワークにおける分極やその他の関連する現象を研究するために使われてきた。
このアプリケーション領域における興味深い、そして難しいタスクは、署名付きグラフで偏極化されたコミュニティを検出することである。
このタスクには様々な方法が提案されている。
しかし、既存のアプローチはグローバルに最適な解を見つけることを目指している。
代わりに,我々は,入力として提供される種ノードの小さなセットに関連する分極化されたコミュニティを見つけることに関心を持っている。
シードノードは2つのセットで構成され、これは偏光構造の両側を構成する。
本稿では,符号付きグラフにおける局所偏極群を局所偏極固有問題として求める。
ラプラシア行列の最小固有値に付随する固有ベクトルを制約付き最適化問題の解として見ることにより、局所情報を追加の制約として組み込むことができる。
さらに、局所バイアスベクトルは、符号付きグラフ上のチーガー定数の局所類似性に関して近似保証を持つコミュニティを見つけるために使用できることを示した。
入力グラフのスパーシティを活用することで、分極されたコミュニティの指標ベクトルをグラフサイズに線形な時間に求めることができる。
実世界のネットワークに関する実験は,提案アルゴリズムの有効性を検証し,この半教師付き手法による局所構造探索に有用であることを示す。
関連論文リスト
- Graph Out-of-Distribution Generalization via Causal Intervention [69.70137479660113]
本稿では,ノードレベルの分散シフトの下で頑健なグラフニューラルネットワーク(GNN)をトレーニングするための,概念的に単純だが原則化されたアプローチを提案する。
本手法は,環境推定器と熟練GNN予測器を協調する因果推論に基づく新たな学習目標を提案する。
本モデルでは,様々な分散シフトによる一般化を効果的に向上し,グラフOOD一般化ベンチマーク上での最先端の精度を最大27.4%向上させることができる。
論文 参考訳（メタデータ） (2024-02-18T07:49:22Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - PARTNER: Level up the Polar Representation for LiDAR 3D Object Detection [81.16859686137435]
本稿では、極座標における新しい3次元物体検出器Partnerを紹介する。
提案手法は,ONCE検証セットにおいて3.68%,9.15%の差で従来の極性理論よりも優れていた。
論文 参考訳（メタデータ） (2023-08-08T01:59:20Z) - On the Complexity of the Bipartite Polarization Problem: from Neutral to
Highly Polarized Discussions [1.5675763601034223]
双分極問題は、重み付きラベル付きグラフ上で最も高い偏極二分法を見つけることを目標とする最適化問題である。
単一パラメータがインスタンスの分極を制御するインスタンス生成モデルを導入する。
論文 参考訳（メタデータ） (2023-07-21T14:40:41Z) - Curvature-based Clustering on Graphs [14.136746708037402]
グラフの幾何学を利用して、クラスタやコミュニティを形成する密接な連結部分構造を同定するアルゴリズムについて研究する。
本手法は, 離散リッチ曲率とそのそれに付随する幾何フローを実装し, グラフのエッジ重みを進化させて, そのコミュニティ構造を明らかにする。
論文 参考訳（メタデータ） (2023-07-19T17:35:08Z) - Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
グラフを幾何学グラフとみなす: ノードは基礎となる計量空間からランダムにサンプリングされ、その距離が指定された近傍半径以下であれば任意のノードが接続される。
ソーシャルネットワークでは、コミュニティは密集したサンプル領域としてモデル化でき、ハブはより大きな近傍半径を持つノードとしてモデル化できる。
我々は,未知のサンプリング密度を自己監督的に推定する手法を開発した。
論文 参考訳（メタデータ） (2022-10-15T08:01:08Z) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。
提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。
この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
論文 参考訳（メタデータ） (2022-06-06T14:26:34Z) - Integrating Network Embedding and Community Outlier Detection via
Multiclass Graph Description [15.679313861083239]
そこで本稿では,ノード埋め込みとアウトレーヤとコミュニティ検出を統合した非教師なしグラフ埋め込み手法(DMGD)を提案する。
DMGDにより検出された外れ値の数に関する理論的境界を示す。
我々の定式化は、外れ値、コミュニティ割り当て、ノード埋め込み関数の間の興味深いミニマックスゲームに起因する。
論文 参考訳（メタデータ） (2020-07-20T16:21:07Z) - Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
このプロセスにおける確率バイアスが、プロセスによって選択されたノードの品質にどの程度影響するかを調査する。
我々は、この近傍を正規化ラプラス行列として表されるノードの近傍部分グラフのスペクトルに基づく確率測度として簡潔に捉えた。
我々は,様々な実世界のデータセット上で,最先端ノード埋め込み技術に対する我々のアプローチを実証的に評価した。
論文 参考訳（メタデータ） (2020-05-19T20:42:43Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。