Fugu-MT 論文翻訳(概要): Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT

論文の概要: Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT

arxiv url: http://arxiv.org/abs/2211.13708v1
Date: Thu, 24 Nov 2022 16:52:48 GMT
ステータス: 処理完了
システム内更新日: 2022-11-28 18:50:00.204741
Title: Reduction Algorithms for Persistence Diagrams of Networks: CoralTDA and PrunIT
Title（参考訳）: ネットワークの永続化ダイアグラムの削減アルゴリズム: CoralTDA と PrunIT
Authors: Cuneyt Gurcan Akcora, Murat Kantarcioglu, Yulia R. Gel and Baris Coskunuzer
Abstract要約: 計算コストが高いことが、トポロジカルデータ分析の成功を妨げる主要な障害となっている。我々は,大規模グラフの完全永続化図を計算するために,2つの新しい,驚くほど単純で効果的なアルゴリズムを開発した。大規模ネットワークにおける実験により,新しい手法で最大95%の計算ゲインが得られることが示された。
参考スコア（独自算出の注目度）: 27.411830935369498
License: http://creativecommons.org/publicdomain/zero/1.0/
Abstract: Topological data analysis (TDA) delivers invaluable and complementary information on the intrinsic properties of data inaccessible to conventional methods. However, high computational costs remain the primary roadblock hindering the successful application of TDA in real-world studies, particularly with machine learning on large complex networks. Indeed, most modern networks such as citation, blockchain, and online social networks often have hundreds of thousands of vertices, making the application of existing TDA methods infeasible. We develop two new, remarkably simple but effective algorithms to compute the exact persistence diagrams of large graphs to address this major TDA limitation. First, we prove that $(k+1)$-core of a graph $\mathcal{G}$ suffices to compute its $k^{th}$ persistence diagram, $PD_k(\mathcal{G})$. Second, we introduce a pruning algorithm for graphs to compute their persistence diagrams by removing the dominated vertices. Our experiments on large networks show that our novel approach can achieve computational gains up to 95%. The developed framework provides the first bridge between the graph theory and TDA, with applications in machine learning of large complex networks. Our implementation is available at https://github.com/cakcora/PersistentHomologyWithCoralPrunit
Abstract（参考訳）: トポロジカルデータ分析(TDA)は、従来の方法ではアクセスできないデータの本質的な特性について、重要かつ補完的な情報を提供する。しかし、高い計算コストは、特に大規模複雑なネットワーク上の機械学習において、実世界研究におけるtdaの応用を阻害する主要な障害である。実際、引用、ブロックチェーン、オンラインソーシャルネットワークといった現代のネットワークの多くは数十万の頂点を持ち、既存のTDAメソッドの適用は不可能である。我々は,この主要なtda制限に対処するために,大規模グラフの正確なパーシステンスダイアグラムを計算するための2つの新しい,驚くほど単純だが効果的なアルゴリズムを開発した。まず、$(k+1)$-core of a graph $\mathcal{g}$ suffices to compute its $k^{th}$ persistence diagram, $pd_k(\mathcal{g})$。第2に,グラフに対するプルーニングアルゴリズムを導入し,支配的頂点を取り除いて永続化図を計算する。大規模ネットワークにおける実験の結果, 計算能力は95%まで向上することがわかった。開発されたフレームワークは、グラフ理論とtdaの間の最初の橋渡しを提供し、大規模複雑なネットワークの機械学習に応用できる。実装はhttps://github.com/cakcora/PersistentHomologyWithCoralPrunitで公開しています。

関連論文リスト

T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文参考訳（メタデータ） (2023-10-05T02:58:29Z)
SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
論文参考訳（メタデータ） (2023-08-03T07:00:04Z)
A fast topological approach for predicting anomalies in time-varying graphs [0.0]
トポロジカルデータ解析(TDA)からの永続化ダイアグラム(PD)は、点間距離が明確に定義されたデータ形状記述法として人気がある。本稿では,グラフデータから形状情報を抽出する計算効率の良いフレームワークを提案する。実際のデータアプリケーションでは、暗号取引ネットワークの異常な価格予測において、我々のアプローチは最大で22%上昇する。
論文参考訳（メタデータ） (2023-05-11T01:54:45Z)
Learning Graph Algorithms With Recurrent Graph Neural Networks [8.873449722727026]
我々は、単純なグラフ問題を末尾から末尾まで小さなグラフで学習し、より大きなインスタンスに拡張する、反復的なアーキテクチャ設計に重点を置いている。 We use (i) skip connection, (ii) state regularization, and (iii) edge convolutions to guide GNNs to extrapolation。
論文参考訳（メタデータ） (2022-12-09T15:42:22Z)
Certified Graph Unlearning [39.29148804411811]
グラフ構造化データは実際にユビキタスであり、しばしばグラフニューラルネットワーク(GNN)を使用して処理される我々は,GNNのemph認定グラフアンラーニングのための最初のフレームワークを紹介する。ノード機能、エッジ、ノードアンラーニングの3つの異なるタイプのアンラーニング要求を検討する必要がある。
論文参考訳（メタデータ） (2022-06-18T07:41:10Z)
Large-Scale Network Embedding in Apache Spark [1.3769786711365102]
本稿では,Apache Sparkを用いた大規模グラフへのネットワーク埋め込みのための効率的かつ効率的な分散アルゴリズムを提案する。提案手法は数時間で数十億のエッジを持つグラフを処理でき、最先端のアプローチよりも少なくとも4倍高速であることを示す。
論文参考訳（メタデータ） (2021-06-20T04:42:24Z)
Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文参考訳（メタデータ） (2021-03-30T08:58:45Z)
Co-embedding of Nodes and Edges with Graph Neural Networks [13.020745622327894]
グラフ埋め込みは、高次元および非ユークリッド特徴空間でデータ構造を変換しエンコードする方法である。 CensNetは一般的なグラフ埋め込みフレームワークで、ノードとエッジの両方を潜在機能空間に埋め込む。提案手法は,4つのグラフ学習課題における最先端のパフォーマンスを達成または一致させる。
論文参考訳（メタデータ） (2020-10-25T22:39:31Z)
Simple and Deep Graph Convolutional Networks [63.76221532439285]
グラフ畳み込みネットワーク(GCN)は、グラフ構造化データに対する強力なディープラーニングアプローチである。その成功にもかかわらず、現在のGCNモデルは、エムの過度に滑らかな問題のため、ほとんどが浅くなっている。本稿では,2つの単純かつ効果的な手法を用いて,バニラGCNモデルを拡張したGCNIIを提案する。
論文参考訳（メタデータ） (2020-07-04T16:18:06Z)
Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文参考訳（メタデータ） (2020-07-03T09:30:07Z)
Geometrically Principled Connections in Graph Neural Networks [66.51286736506658]
我々は、幾何学的深層学習の新興分野におけるイノベーションの原動力は、幾何が依然として主要な推進力であるべきだと論じている。グラフニューラルネットワークとコンピュータグラフィックスとデータ近似モデルとの関係:放射基底関数(RBF) 完全連結層とグラフ畳み込み演算子を組み合わせた新しいビルディングブロックであるアフィンスキップ接続を導入する。
論文参考訳（メタデータ） (2020-04-06T13:25:46Z)

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

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