論文の概要: Ironing the Graphs: Toward a Correct Geometric Analysis of Large-Scale Graphs

• arxiv url: http://arxiv.org/abs/2407.21609v1
• Date: Wed, 31 Jul 2024 13:47:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-01 12:27:41.686697
• Title: Ironing the Graphs: Toward a Correct Geometric Analysis of Large-Scale Graphs
• Title（参考訳）: グラフのアイアンリング: 大規模グラフの正確な幾何学的解析に向けて
• Authors: Saloua Naama, Kavé Salamatian, Francesco Bronzino,
• Abstract要約: 古典的な埋め込み技法は、多様体の各点における曲率を見逃すので、正確な幾何学的解釈をもたらすことはできない。 本稿では,離散リッチフローに基づく離散リッチフローグラフ埋め込み(dRfge)を提案する。 この論文の主な貢献は、離散リッチフローの一定曲率とエッジ上の安定距離メトリクスへの収束性を初めて証明したことである。
• 参考スコア（独自算出の注目度）: 2.2557806157585834
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph embedding approaches attempt to project graphs into geometric entities, i.e, manifolds. The idea is that the geometric properties of the projected manifolds are helpful in the inference of graph properties. However, if the choice of the embedding manifold is incorrectly performed, it can lead to incorrect geometric inference. In this paper, we argue that the classical embedding techniques cannot lead to correct geometric interpretation as they miss the curvature at each point, of manifold. We advocate that for doing correct geometric interpretation the embedding of graph should be done over regular constant curvature manifolds. To this end, we present an embedding approach, the discrete Ricci flow graph embedding (dRfge) based on the discrete Ricci flow that adapts the distance between nodes in a graph so that the graph can be embedded onto a constant curvature manifold that is homogeneous and isotropic, i.e., all directions are equivalent and distances comparable, resulting in correct geometric interpretations. A major contribution of this paper is that for the first time, we prove the convergence of discrete Ricci flow to a constant curvature and stable distance metrics over the edges. A drawback of using the discrete Ricci flow is the high computational complexity that prevented its usage in large-scale graph analysis. Another contribution of this paper is a new algorithmic solution that makes it feasible to calculate the Ricci flow for graphs of up to 50k nodes, and beyond. The intuitions behind the discrete Ricci flow make it possible to obtain new insights into the structure of large-scale graphs. We demonstrate this through a case study on analyzing the internet connectivity structure between countries at the BGP level.
• Abstract（参考訳）: グラフ埋め込みアプローチはグラフを幾何学的実体、すなわち多様体に投影しようとする。 この考え方は、射影多様体の幾何学的性質がグラフ特性の推論に有用である、というものである。 しかし、埋め込み多様体の選択が誤って実行されると、それは誤った幾何学的推論につながる可能性がある。 本稿では,古典的な埋め込み手法は,多様体の各点における曲率を欠いているため,正確な幾何学的解釈を導出できないことを論じる。 正確な幾何学的解釈を行うためには、グラフの埋め込みは正則な定曲率多様体上で行うべきである。 この目的を達成するために、グラフ内のノード間の距離を調整する離散リッチフロー(dRfge)に基づく離散リッチフローグラフ埋め込み(dRfge)を提案する。 この論文の主な貢献は、離散リッチフローの一定曲率とエッジ上の安定距離メトリクスへの収束性を初めて証明したことである。 離散リッチフローを使うことの欠点は、大規模グラフ解析においてその使用を妨げた高い計算複雑性である。 この論文のもう1つの貢献は、最大50kノードのグラフに対するリッチフローを計算可能にする新しいアルゴリズム解である。 離散リッチフローの背後にある直感は、大規模グラフの構造に関する新たな洞察を得ることを可能にする。 本稿は、BGPレベルにおける各国間のインターネット接続構造の分析に関するケーススタディを通じて、これを実証する。

関連論文リスト

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。 我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。 最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
  論文  参考訳（メタデータ） (2024-09-08T18:55:57Z)
• DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing [72.70197960100677]
  グラフ構造学習(GSL)はグラフニューラルネットワーク(GNN)を改良したグラフで強化する上で重要な役割を果たしている。 GSLソリューションは、通常、タスク固有の監督(ノード分類)による構造改善に焦点を当てるか、GNN自体の固有の弱点を見落としている。 本稿では,典型的なGNNにおけるオーバー・スカッシングの問題を効果的に緩和する,自己教師付きグラフ構造-機能共分法について検討する。
  論文  参考訳（メタデータ） (2024-01-23T14:06:08Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• How Curvature Enhance the Adaptation Power of Framelet GCNs [27.831929635701886]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データのモデリングにおいて強力に実証されている。 本稿では,離散グラフリッチ曲率によるGNNの拡張手法を提案する。 曲率に基づくGNNモデルは、ホモフィリーグラフとヘテロフィリーグラフの両方において、最先端のベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2023-07-19T06:05:33Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs [122.06927400759021]
  本稿では,グラフニューラルネットワーク (GNN) と多様体ニューラルネットワーク (MNN) の関係について検討する。 これらのグラフ上の畳み込みフィルタとニューラルネットワークが連続多様体上の畳み込みフィルタとニューラルネットワークに収束することを示す。
  論文  参考訳（メタデータ） (2023-05-29T08:27:17Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。 幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。 次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
  論文  参考訳（メタデータ） (2023-05-05T14:04:52Z)
• Heterogeneous manifolds for curvature-aware graph embedding [6.3351090376024155]
  グラフ埋め込みは、広範囲のGraph MLアプリケーションで使用されている。 そのような埋め込みの質は、空間の幾何学がグラフの幾何学と一致するかどうかに決定的に依存する。
  論文  参考訳（メタデータ） (2022-02-02T18:18:35Z)
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
  2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。 p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。 sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
  論文  参考訳（メタデータ） (2021-01-29T21:49:50Z)
• Computationally Tractable Riemannian Manifolds for Graph Embeddings [10.420394952839242]
  我々は、ある曲面リーマン空間におけるグラフ埋め込みを学習し、最適化する方法を示す。 我々の結果は、機械学習パイプラインにおける非ユークリッド埋め込みの利点の新たな証拠として役立ちます。
  論文  参考訳（メタデータ） (2020-02-20T10:55:47Z)

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

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