論文の概要: Cycle-tree guided attack of random K-core: Spin glass model and
efficient message-passing algorithm
- arxiv url: http://arxiv.org/abs/2110.05940v3
- Date: Tue, 19 Jul 2022 06:05:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 17:02:18.825612
- Title: Cycle-tree guided attack of random K-core: Spin glass model and
efficient message-passing algorithm
- Title（参考訳）: ランダムKコアのサイクルツリー誘導攻撃:スピンガラスモデルと効率的なメッセージパッシングアルゴリズム
- Authors: Hai-Jun Zhou
- Abstract要約: 最小攻撃セットは、Kコアの完全な崩壊を引き起こす最小数の頂点を含む。
ここでは、この最適初期条件問題に、サイクルツリー最大パッキングのスピングラスの観点から取り組む。
CTGAの性能と時間効率は、正規ランダムおよびエルド・オス・レニイランダムグラフアンサンブルで検証される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The K-core of a graph is the maximal subgraph within which each vertex is
connected to at least K other vertices. It is a fundamental network concept for
understanding threshold cascading processes with a discontinuous percolation
transition. A minimum attack set contains the smallest number of vertices whose
removal induces complete collapse of the K-core. Here we tackle this
prototypical optimal initial-condition problem from the spin-glass perspective
of cycle-tree maximum packing and propose a cycle-tree guided attack (CTGA)
message-passing algorithm. The good performance and time efficiency of CTGA are
verified on the regular random and Erd\"os-R\'enyi random graph ensembles. Our
central idea of transforming a long-range correlated dynamical process to
static structural patterns may also be instructive to other hard optimization
and control problems.
- Abstract（参考訳）: グラフのk-コアは、各頂点が少なくとも k 個の他の頂点に接続される極大部分グラフである。
これは不連続なパーコレーション遷移を伴う閾値カスケード過程を理解するための基本的なネットワーク概念である。
最小攻撃セットは、Kコアの完全な崩壊を引き起こす最小数の頂点を含む。
本稿では,サイクルツリー最大パッキングのスピングラス的視点から,このプロトタイプ最適初期条件問題に取り組み,サイクルツリー誘導攻撃(CTGA)メッセージパッシングアルゴリズムを提案する。
CTGAの性能と時間効率は、正規ランダムとErd\"os-R'enyiランダムグラフアンサンブルで検証される。
長距離相関力学過程を静的構造パターンに変換するという我々の中心的な考え方は、他のハード最適化や制御問題にも寄与するかもしれない。
関連論文リスト
- Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。
既存のGCメソッドは複雑な最適化プロセスに悩まされており、過剰な計算資源を必要とする。
我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。
CGCはより効率的な凝縮プロセスで最先端の性能を達成する。
論文 参考訳（メタデータ） (2024-05-22T14:57:09Z) - Disentangled Condensation for Large-scale Graphs [31.781721873508978]
グラフニューラルネットワーク(GNN)の高価なトレーニングコストを節約するための興味深いテクニックとして、グラフ凝縮が登場した。
本稿では, 凝縮過程を2段階のGNNフリーパラダイムに分解し, ノードを独立に凝縮し, エッジを生成することを提案する。
この単純で効果的なアプローチは、中規模グラフの精度に匹敵する精度で最先端の手法よりも少なくとも10倍早く達成できる。
論文 参考訳（メタデータ） (2024-01-18T09:59:00Z) - MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
スペクトルクラスタリングは、優れたパフォーマンス、簡単な実装、強力な適応性のために人気があり、魅力的です。
我々は,MeanCutを目的関数として提案し,非破壊グラフ分割の次数降下順で厳密に最適化する。
本アルゴリズムの有効性は,実世界のベンチマークによる検証と顔認識の適用によって実証される。
論文 参考訳（メタデータ） (2023-12-07T06:19:39Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Hierarchical cycle-tree packing model for $K$-core attack problem [0.0]
ここでは、この挑戦的な最適化問題に対して、階層的なサイクルツリーパッキングモデルを導入している。
統計物理学のレプリカ対称キャビティ法を用いて,このモデルを解析する。
関連する階層的サイクルツリー誘導攻撃(tt hCTGA)は、通常のランダムグラフに対するほぼ最適な攻撃解を構築することができる。
論文 参考訳（メタデータ） (2023-03-02T06:47:33Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Total Variation Graph Neural Networks [5.571369922847262]
最近提案されたグラフニューラルネットワーク(GNN)は、教師なしの最小カット目標を用いて訓練されている。
本稿では,最小カットの厳密な緩和を最適化し,クラスタ割り当てを計算するGNNモデルを提案する。
論文 参考訳（メタデータ） (2022-11-11T14:13:14Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。