論文の概要: Local Algorithms for Estimating Effective Resistance
- arxiv url: http://arxiv.org/abs/2106.03476v1
- Date: Mon, 7 Jun 2021 10:08:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 17:22:35.892001
- Title: Local Algorithms for Estimating Effective Resistance
- Title（参考訳）: 有効抵抗推定のための局所アルゴリズム
- Authors: Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci
- Abstract要約: 本研究では,大規模グラフ上での有効抵抗を推定するための複数のエンファンローカアルゴリズムを設計する。
主アルゴリズムは任意の頂点対 $s,t$ と任意に小さな加算誤差の間の有効抵抗を近似する。
いくつかのベンチマークデータセットについて広範な実験を行い、アルゴリズムを検証した。
- 参考スコア（独自算出の注目度）: 26.54556748340991
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Effective resistance is an important metric that measures the similarity of
two vertices in a graph. It has found applications in graph clustering,
recommendation systems and network reliability, among others. In spite of the
importance of the effective resistances, we still lack efficient algorithms to
exactly compute or approximate them on massive graphs.
In this work, we design several \emph{local algorithms} for estimating
effective resistances, which are algorithms that only read a small portion of
the input while still having provable performance guarantees. To illustrate,
our main algorithm approximates the effective resistance between any vertex
pair $s,t$ with an arbitrarily small additive error $\varepsilon$ in time
$O(\mathrm{poly}(\log n/\varepsilon))$, whenever the underlying graph has
bounded mixing time. We perform an extensive empirical study on several
benchmark datasets, validating the performance of our algorithms.
- Abstract（参考訳）: 有効抵抗はグラフ内の2つの頂点の類似性を測定する重要な指標である。
グラフクラスタリング、レコメンデーションシステム、ネットワーク信頼性などに応用されている。
効果的な抵抗の重要性にもかかわらず、巨大なグラフ上でそれらを正確に計算したり近似したりする効率的なアルゴリズムはいまだに欠けている。
本研究では,入力のごく一部だけを読み込むアルゴリズムであり,性能保証を保証できるアルゴリズムである,効率的な抵抗を推定するいくつかの \emph{local algorithms} を設計した。
説明するために、本アルゴリズムは任意の頂点対$s,t$と任意の小さな加法誤差$\varepsilon$ in time $o(\mathrm{poly}(\log n/\varepsilon))$の間の有効抵抗を近似する。
いくつかのベンチマークデータセットについて広範な実験を行い、アルゴリズムの性能を検証する。
関連論文リスト
- Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
グラフクラスタリングフレームワーク textitPCon を開発した。
既存のソリューションの多くをフレームワークに還元できることを示します。
本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
論文 参考訳（メタデータ） (2022-11-22T12:45:27Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。
我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。
RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
論文 参考訳（メタデータ） (2022-10-21T15:56:13Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Efficient block contrastive learning via parameter-free meta-node
approximation [1.1470070927586016]
サブサンプリングは最適ではなく、誤った負のサンプリングはサンプリングバイアスにつながる。
本稿では,メタノードをベースとした近似手法を提案する。
6つのベンチマークで、最先端グラフクラスタリングよりも有望な精度向上を示す。
論文 参考訳（メタデータ） (2022-09-28T12:56:35Z) - A Fast PC Algorithm with Reversed-order Pruning and A Parallelization
Strategy [22.31288740171446]
PCアルゴリズムは観測データに基づく因果構造発見のための最先端のアルゴリズムである。
条件付き独立テストが実行された場合、最悪の場合、計算コストがかかる可能性がある。
これにより、タスクが数百から数千のノードを含む場合、アルゴリズムは計算的に難解になる。
本稿では、2つのノードを独立にレンダリングする条件セットが非特異であり、特定の冗長ノードを含む場合、結果の精度を犠牲にしない、という批判的な観察を提案する。
論文 参考訳（メタデータ） (2021-09-10T02:22:10Z) - Large-Scale Network Embedding in Apache Spark [1.3769786711365102]
本稿では,Apache Sparkを用いた大規模グラフへのネットワーク埋め込みのための効率的かつ効率的な分散アルゴリズムを提案する。
提案手法は数時間で数十億のエッジを持つグラフを処理でき、最先端のアプローチよりも少なくとも4倍高速であることを示す。
論文 参考訳（メタデータ） (2021-06-20T04:42:24Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Fast Graph Attention Networks Using Effective Resistance Based Graph
Sparsification [70.50751397870972]
FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。
我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
論文 参考訳（メタデータ） (2020-06-15T22:07:54Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。