論文の概要: Structure from Voltage
- arxiv url: http://arxiv.org/abs/2203.00063v1
- Date: Mon, 28 Feb 2022 20:06:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-03 04:42:51.197381
- Title: Structure from Voltage
- Title(参考訳): 電圧からの構造
- Authors: Robi Bhattacharjee, Alex Cloninger, Yoav Freund
- Abstract要約: 有効抵抗(ER)はグラフの構造を問う魅力的な方法である。
我々は、$n$の頂点が$n2$のグラフにおけるスケーリング抵抗を使用することで、電圧と有効抵抗の有意義な制限が得られることを示す。
また、計量グラフに「基底」ノードを加えることで、選択された点から他のすべての点までのすべての距離を計算する単純で自然な方法が得られることを示す。
- 参考スコア(独自算出の注目度): 7.627299398469962
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Effective resistance (ER) is an attractive way to interrogate the structure
of graphs. It is an alternative to computing the eigen-vectors of the graph
Laplacian. Graph laplacians are used to find low dimensional structures in high
dimensional data. Here too, ER based analysis has advantages over eign-vector
based methods. Unfortunately Von Luxburg et al. (2010) show that, when vertices
correspond to a sample from a distribution over a metric space, the limit of
the ER between distant points converges to a trivial quantity that holds no
information about the structure of the graph. We show that by using scaling
resistances in a graph with $n$ vertices by $n^2$, one gets a meaningful limit
of the voltages and of effective resistances. We also show that by adding a
"ground" node to a metric graph one gets a simple and natural way to compute
all of the distances from a chosen point to all other points.
- Abstract(参考訳): 有効抵抗(ER)はグラフの構造を問う魅力的な方法である。
これはグラフラプラシアンの固有ベクトルを計算するに代わるものである。
グラフラプラシアンは高次元データにおいて低次元構造を見つけるために用いられる。
ここでも、ERベースの解析は等ベクトル法よりも有利である。
残念ながら、Von Luxburg et al. (2010) は、頂点が計量空間上の分布からのサンプルに対応するとき、遠点間のERの極限はグラフの構造に関する情報を持たない自明な量に収束することを示した。
我々は、$n$頂点が$n^2$のグラフにおけるスケーリング抵抗を使用することで、電圧と有効抵抗の有意な制限が得られることを示す。
また、計量グラフに「接地」ノードを加えることで、選択された点から他の全ての点までの距離を計算するための単純で自然な方法が得られることを示す。
関連論文リスト
- Force-directed graph embedding with hops distance [5.214207581551816]
グラフトポロジと構造的特徴を保存できる新しい力によるグラフ埋め込み法を提案する。
私たちの方法は直感的で、並列化可能で、非常にスケーラブルです。
提案手法をいくつかのグラフ解析タスクで評価し,最先端の非教師なし埋め込み技術と比較して競争性能が向上することを示す。
論文 参考訳(メタデータ) (2023-09-11T23:08:03Z) - Effective resistance in metric spaces [65.94598202303497]
有効抵抗(ER)はグラフの構造を問う魅力的な方法である。
サンプルのサイズが無限大になるにつれて、任意の2点間のERが自明な量に収束することを示す。
領域を固定し続けることにより、点数が無限大になるにつれて、領域ベースのERが非自明な極限に収束することを示す。
論文 参考訳(メタデータ) (2023-06-27T17:43:18Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳(メタデータ) (2023-06-05T00:01:17Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳(メタデータ) (2023-02-02T08:33:36Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳(メタデータ) (2022-08-18T09:19:01Z) - Multiscale Graph Comparison via the Embedded Laplacian Distance [6.09170287691728]
非常に異なるサイズのグラフを比較するために,埋め込みラプラシアン距離 (ELD) を提案する。
我々のアプローチはまず、図形構造を尊重する共通の低次元ラプラシア埋め込み空間にグラフを投影する。
距離は自然スライスされたワッサーシュタインアプローチによって効率的に計算できる。
論文 参考訳(メタデータ) (2022-01-28T12:13:08Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳(メタデータ) (2021-11-12T07:08:13Z) - Improved Reconstruction of Random Geometric Graphs [3.930410971186142]
ランダムな幾何グラフの古典的モデルを考えると、$n$の点が一様に領域$n$の正方形に散らばっている。
グラフ距離と近距離推定のハイブリッドを用いてユークリッド距離を推定する。
本手法は, グラフ距離と近辺点数に基づく短距離推定のハイブリッドを用いてユークリッド距離を推定する。
論文 参考訳(メタデータ) (2021-07-29T20:37:28Z) - Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。
グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。
幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
論文 参考訳(メタデータ) (2020-12-30T18:51:06Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-10-25T18:12:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。