論文の概要: The graph alignment problem: fundamental limits and efficient algorithms
- arxiv url: http://arxiv.org/abs/2404.12418v1
- Date: Thu, 18 Apr 2024 15:31:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-22 17:04:06.797299
- Title: The graph alignment problem: fundamental limits and efficient algorithms
- Title（参考訳）: グラフアライメント問題:基本極限と効率的なアルゴリズム
- Authors: Luca Ganassali,
- Abstract要約: グラフ同型問題のノイズバージョンは、エッジの大部分を保存する2つのグラフのノード間のマッチングを見つけることを目的としている。
この論文は、この問題の基本的な情報理論的限界を理解すること、および、基礎となるデータのアライメントを回復できるアルゴリズムを設計および分析することに焦点を当てている。
- 参考スコア（独自算出の注目度）: 0.9246334723892301
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail.
- Abstract（参考訳）: この論文は、グラフアライメント問題、グラフ同型問題のノイズバージョンについて研究し、エッジのほとんどを保存する2つのグラフのノード間のマッチングを見つけることを目的としている。
グラフがランダムな植込みバージョンに着目して、この問題の基本的な情報理論的限界を理解することに興味を持ち、データ内の基盤となるアライメントを復元できるアルゴリズムを設計および分析することに興味を持っている。
これらのアルゴリズムに対して、我々は、それらが成功するか失敗する体制に対して、いくつかの高い確率保証を与える。
関連論文リスト
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph
Structure [18.00833762891405]
Graph Lottery Ticket (GLT)仮説: グラフごとに非常に疎いバックボーンが存在する。
本研究は,グラフ学習アルゴリズムの性能に直接影響を及ぼす関心の指標を8つ研究する。
任意のグラフでこれらのGLTを見つけるための単純で効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T00:24:44Z) - FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。
本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。
提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-10-21T07:58:03Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。
関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文 参考訳（メタデータ） (2022-07-04T19:33:06Z) - Deep graph matching meets mixed-integer linear programming: Relax at
your own risk ? [8.05409526074409]
グラフマッチング問題のMILP定式化を統合する手法を提案する。
同様のアプローチは、グラフマッチング解決器の最適保証と品質レベルの導入によって導かれる。
実験により,いくつかの理論的知見が得られ,深部グラフマッチング手法の方向性を導出する。
論文 参考訳（メタデータ） (2021-08-01T08:29:55Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳（メタデータ） (2020-10-20T05:54:31Z) - Graph Information Bottleneck for Subgraph Recognition [103.37499715761784]
本稿では,深層グラフ学習における部分グラフ認識問題に対するグラフ情報ブートネック(GIB)の枠組みを提案する。
この枠組みの下では、最大情報でありながら圧縮的な部分グラフ(IB-subgraph)を認識できる。
IB-サブグラフの特性を3つのアプリケーションシナリオで評価する。
論文 参考訳（メタデータ） (2020-10-12T09:32:20Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。