論文の概要: Blind Extraction of Equitable Partitions from Graph Signals

• arxiv url: http://arxiv.org/abs/2203.05407v1
• Date: Thu, 10 Mar 2022 15:03:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-11 19:06:09.423621
• Title: Blind Extraction of Equitable Partitions from Graph Signals
• Title（参考訳）: グラフ信号からの等価パーティションのブラインド抽出
• Authors: Michael Scholkemper and Michael Schaub
• Abstract要約: ネットワークのエッジの知識を必要とせずに、ネットワークの公平な分割を回復することを目的としたブラインド識別問題について検討する。 等価な分割を抽出する簡単なスペクトルアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding equitable partitions is closely related to the extraction of graph symmetries and of interest in a variety of applications context such as node role detection, cluster synchronization, consensus dynamics, and network control problems. In this work we study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network's edges but based solely on the observations of the outputs of an unknown graph filter. Specifically, we consider two settings. First, we consider a scenario in which we can control the input to the graph filter and present a method to extract the partition inspired by the well known Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea to a setting where only observe the outputs to random, low-rank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions. Finally, we establish theoretical bounds on the error that this spectral detection scheme incurs and perform numerical experiments that illustrate our theoretical results and compare both algorithms.
• Abstract（参考訳）: 等価なパーティションを見つけることは、グラフ対称性の抽出や、ノードの役割検出、クラスタ同期、コンセンサスダイナミクス、ネットワーク制御問題など、さまざまなアプリケーションコンテキストへの関心と密接に関連している。 本研究では,ネットワークのエッジの知識を必要とせず,未知のグラフフィルタの出力の観測のみに基づいて,ネットワークの公平な分割を回復することを目的としたブラインド識別問題について検討する。 具体的には2つの設定を考えます。 まず、グラフフィルタへの入力を制御できるシナリオを検討し、よく知られたWeisfeiler-Lehman (color refinement)アルゴリズムにインスパイアされた分割を抽出する方法を提案する。 第2に、このアイデアをグラフフィルタのランダムで低ランクな励起にのみ出力を観測する設定に一般化し、関連する等値分割を抽出する単純なスペクトルアルゴリズムを提案する。 最後に, このスペクトル検出方式がもたらした誤差の理論的境界を定め, 理論結果を説明する数値実験を行い, 両アルゴリズムを比較した。

関連論文リスト

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNClerは、Heterophilous Node Clusteringの新しいアプローチである。 HeNClerは異種グラフコンテキストにおけるノードクラスタリングタスクの性能を大幅に向上させることを示す。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Entropy Neural Estimation for Graph Contrastive Learning [9.032721248598088]
  グラフ上のコントラスト学習は、ノードの区別可能な高レベル表現を抽出することを目的としている。 本稿では,データセットのビュー間のペアワイズ表現を対比する,単純かつ効果的なサブセットサンプリング戦略を提案する。 7つのグラフベンチマークで広範な実験を行い、提案手法は競合性能を実現する。
  論文  参考訳（メタデータ） (2023-07-26T03:55:08Z)
• A Sparse Graph Formulation for Efficient Spectral Image Segmentation [0.0]
  スペクトルクラスタリングは、セグメンテーション問題を解決する最も伝統的な方法の1つである。 単純なグリッドグラフに余分なノードを含めることで、スパースグラフを定式化します。 元の正規化カットアルゴリズムをこのグラフに適用すると、スペクトル画像セグメンテーションの単純でスケーラブルな方法が導かれる。
  論文  参考訳（メタデータ） (2023-06-22T19:06:27Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
  本稿では,隠れ変数の存在を考慮した共同グラフ学習法を提案する。 従来の考察から得られた構造を利用して凸最適化問題を提案する。 提案したアルゴリズムを異なるベースラインで比較し、合成グラフと実世界のグラフ上での性能を評価する。
  論文  参考訳（メタデータ） (2022-12-04T13:03:41Z)
• LoNe Sampler: Graph node embeddings by coordinated local neighborhood sampling [0.7614628596146599]
  局所グラフ近傍サンプリングは、ノード表現学習のアルゴリズムの中心にある基本的な計算問題である。 そこで我々はLoNe Samplerを提案する。LoNe Samplerはローカル近傍サンプリングによる離散ノード埋め込みを生成するアルゴリズムスイートである。
  論文  参考訳（メタデータ） (2022-11-28T08:04:26Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。 近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
  論文  参考訳（メタデータ） (2021-06-26T06:24:51Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  グラフ信号定常性の概念に依存するオフライン手法を提案する。 我々の検出器は、漸近的でない不等式オラクルの証拠を伴っている。
  論文  参考訳（メタデータ） (2020-06-18T15:51:38Z)
• Heterogeneous Graph Neural Networks for Malicious Account Detection [64.0046412312209]
  GEMは、悪意のあるアカウントを検出するための、最初の異種グラフニューラルネットワークである。 我々は、デバイス集約とアクティビティ集約という2つの基本的な弱点に基づいて、異種アカウントデバイスグラフから差別的埋め込みを学習する。 実験により、我々のアプローチは、時間とともに競合する手法と比較して、常に有望な結果が得られることが示された。
  論文  参考訳（メタデータ） (2020-02-27T18:26:44Z)
• Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question [13.625395368083641]
  一致するグラフの1つが二部ネットワークであり、一方が一部ネットワークであるような共通的な設定に対処する。 本稿では,二部グラフと一部グラフのグラフマッチング問題を,非方向のグラフィカルモデルを用いて定式化する。 両部ネットワークを単部ネットワークに変換するという単純なアプローチよりも,我々の手法がより正確なマッチングを実現する方法を示す。
  論文  参考訳（メタデータ） (2020-02-05T05:24:54Z)

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

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