論文の概要: Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering

• arxiv url: http://arxiv.org/abs/2406.07574v1
• Date: Tue, 4 Jun 2024 22:59:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-17 00:04:06.873838
• Title: Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering
• Title（参考訳）: グラフのバイハーモニック距離とその高次変数:理論的性質と中心性とクラスタリングへの応用
• Authors: Mitchell Black, Lucy Lin, Amir Nayyeri, Weng-Keen Wong,
• Abstract要約: バイハーモニック距離と呼ばれる有効抵抗の変種について検討する。 両調和距離がグラフの大域的位相に対するエッジの重要性を測るという考えを支持する理論的な結果をいくつか証明する。 両高調波および$k$-高調波距離のエッジ中心性とグラフクラスタリングに対する有効性について実験的に検討する。
• 参考スコア（独自算出の注目度）: 2.088672652658464
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Effective resistance is a distance between vertices of a graph that is both theoretically interesting and useful in applications. We study a variant of effective resistance called the biharmonic distance. While the effective resistance measures how well-connected two vertices are, we prove several theoretical results supporting the idea that the biharmonic distance measures how important an edge is to the global topology of the graph. Our theoretical results connect the biharmonic distance to well-known measures of connectivity of a graph like its total resistance and sparsity. Based on these results, we introduce two clustering algorithms using the biharmonic distance. Finally, we introduce a further generalization of the biharmonic distance that we call the $k$-harmonic distance. We empirically study the utility of biharmonic and $k$-harmonic distance for edge centrality and graph clustering.
• Abstract（参考訳）: 有効抵抗 (英: effective resistance) とは、理論上は興味深く、応用に有用であるグラフの頂点の間の距離である。 バイハーモニック距離と呼ばれる有効抵抗の変種について検討する。 有効抵抗は2つの頂点が十分に連結されているかを測るが、バイハーモニック距離はグラフの大域的トポロジーに対するエッジの重要性を測るという考えを支持するいくつかの理論的結果を証明する。 我々の理論的結果は、双調和距離と、その全抵抗と空間性のようなグラフの接続性に関するよく知られた尺度を結びつける。 これらの結果に基づき,バイハーモニック距離を用いた2つのクラスタリングアルゴリズムを提案する。 最後に、$k$-調和距離と呼ぶバイハーモニック距離のさらなる一般化を導入する。 両高調波および$k$-高調波距離のエッジ中心性とグラフクラスタリングに対する有効性について実験的に検討する。

関連論文リスト

• Injecting Hamiltonian Architectural Bias into Deep Graph Networks for Long-Range Propagation [55.227976642410766]
  グラフ内の情報拡散のダイナミクスは、グラフ表現学習に大きな影響を及ぼす重要なオープン問題である。 そこで我々は(ポート-)Hamiltonian Deep Graph Networksを紹介した。 我々は,非散逸的長距離伝播と非保守的行動の両方を,単一の理論的・実践的な枠組みで調整する。
  論文  参考訳（メタデータ） (2024-05-27T13:36:50Z)
• All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
  我々は、グラフ上の効果的な抵抗と最適輸送は、最大$p$を選択するまで、一つと同じものとして理解されるべきであると主張する。 最適停止時間とグラフ上のランダムウォーク,グラフソボレフ空間,ベナモ・ブレニエ型式に対する2ドルベックマン距離の明示的な接続を示す。 本稿では、ワッサーシュタイン距離が計算ボトルネックを引き起こす可能性のあるこれらの指標のさらなる利用法を提案する。
  論文  参考訳（メタデータ） (2024-04-23T17:50:52Z)
• Separation-based distance measures for causal graphs [15.37737222790121]
  最先端因果探索法は単一の因果グラフを出力するのではなく、それらの等価クラス(MEC)を出力する。 本稿では,分離距離の差が評価に適さないような距離の付加的な測定法を提案する。 我々は,既存の比較指標の違いを明らかにする実験と,おもちゃの例を用いて理論的解析を補完する。
  論文  参考訳（メタデータ） (2024-02-07T15:36:53Z)
• Alignment and Outer Shell Isotropy for Hyperbolic Graph Contrastive Learning [69.6810940330906]
  高品質なグラフ埋め込みを学習するための新しいコントラスト学習フレームワークを提案する。 具体的には、階層的なデータ不変情報を効果的にキャプチャするアライメントメトリックを設計する。 双曲空間において、木の性質に関連する葉と高さの均一性に対処する必要があることを示す。
  論文  参考訳（メタデータ） (2023-10-27T15:31:42Z)
• Projections of Model Spaces for Latent Graph Inference [18.219577154655006]
  グラフニューラルネットワークは、グラフの接続構造を帰納バイアスとして利用する。 潜在グラフ推論は、適切なグラフ構造を学習して、モデルの下流のパフォーマンスを拡散し改善することに焦点を当てる。
  論文  参考訳（メタデータ） (2023-03-21T11:20:22Z)
• A Topological Distance Measure between Multi-Fields for Classification and Analysis of Shapes and Data [0.0]
  多次元リーブグラフ(MDRG)の計算による2つのマルチフィールド間の距離測定の改善を提案する。 次に、MDRGの各リーブグラフに対応する永続図を演算することにより、永続図の階層構造を構築する。 提案手法は擬似測度および安定性特性を満たすことを示す。
  論文  参考訳（メタデータ） (2023-03-06T05:38:13Z)
• Understanding Oversquashing in GNNs through the Lens of Effective Resistance [9.640594614636047]
  本研究では,入力グラフに付加されるエッジを同定し,全体の有効抵抗を最小限に抑えるアルゴリズムを開発し,オーバーカッシングを緩和する。 我々は,GNNの性能向上のための総合的有効抵抗に基づくスイッチング戦略の有効性を示す実証的証拠を提供する。
  論文  参考訳（メタデータ） (2023-02-14T05:16:12Z)
• Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance [63.203951161394265]
  現代の機械学習では、多くの領域における観測間の相互作用や類似性によって生じる大きなグラフに遭遇することが一般的である。 本研究では,地球移動器距離(EMD)と測地コストを基礎となるグラフ上で比較し,グラフ信号のデータセットを整理する。 いずれの場合も,UDEMDをベースとした埋め込みは,他の手法と比較して高精度な距離を求めることができる。
  論文  参考訳（メタデータ） (2021-07-26T17:19:02Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。 グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。 幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-12-30T18:51:06Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)

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

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