論文の概要: GREED: A Neural Framework for Learning Graph Distance Functions

• arxiv url: http://arxiv.org/abs/2112.13143v3
• Date: Fri, 21 Apr 2023 22:52:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-26 00:54:21.003077
• Title: GREED: A Neural Framework for Learning Graph Distance Functions
• Title（参考訳）: GREED:グラフ距離関数学習のためのニューラルネットワークフレームワーク
• Authors: Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, Sayan Ranu
• Abstract要約: 我々はGREEDと呼ばれる新しいシアムグラフニューラルネットワークを設計し、GEDとSEDをプロパティ保存方式で学習する。 最大700万のエッジを含む10のグラフデータセットを通じて、GREEDは最先端技術よりも正確であるだけでなく、最大3桁高速であることを示す。
• 参考スコア（独自算出の注目度）: 8.323580169763726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Among various distance functions for graphs, graph and subgraph edit distances (GED and SED respectively) are two of the most popular and expressive measures. Unfortunately, exact computations for both are NP-hard. To overcome this computational bottleneck, neural approaches to learn and predict edit distance in polynomial time have received much interest. While considerable progress has been made, there exist limitations that need to be addressed. First, the efficacy of an approximate distance function lies not only in its approximation accuracy, but also in the preservation of its properties. To elaborate, although GED is a metric, its neural approximations do not provide such a guarantee. This prohibits their usage in higher order tasks that rely on metric distance functions, such as clustering or indexing. Second, several existing frameworks for GED do not extend to SED due to SED being asymmetric. In this work, we design a novel siamese graph neural network called GREED, which through a carefully crafted inductive bias, learns GED and SED in a property-preserving manner. Through extensive experiments across 10 real graph datasets containing up to 7 million edges, we establish that GREED is not only more accurate than the state of the art, but also up to 3 orders of magnitude faster. Even more significantly, due to preserving the triangle inequality, the generated embeddings are indexable and consequently, even in a CPU-only environment, GREED is up to 50 times faster than GPU-powered baselines for graph / subgraph retrieval.
• Abstract（参考訳）: グラフの様々な距離関数のうち、グラフとサブグラフの編集距離(GEDとSED)は、最もポピュラーで表現力のある尺度である。 残念ながら、両方の正確な計算はNPハードである。 この計算ボトルネックを克服するために、多項式時間で編集距離を学習し予測するニューラルアプローチが注目されている。 かなりの進歩がなされているが、対処すべき制限がある。 第一に、近似距離関数の有効性はその近似精度だけでなく、その性質の保存にも関係している。 詳しくは、GEDは計量であるが、その神経近似はそのような保証を提供しない。 これにより、クラスタリングやインデックス化といった距離関数に依存する高次タスクでの使用が禁止される。 第2に、SEDが非対称であるため、GEDの既存のフレームワークはSEDに拡張されない。 本研究では,GREEDと呼ばれる新しいサイムズグラフニューラルネットワークを設計し,慎重に設計した帰納バイアスを用いて,プロパティ保存方式でGEDとSEDを学習する。 最大700万のエッジを含む10の実際のグラフデータセットにわたる広範な実験を通じて、GREEDは最先端技術よりも正確であるだけでなく、最大3桁高速であることを示す。 さらに、三角形の不等式を保存するため、生成された埋め込みはインデックス化可能であり、CPUのみの環境でもGREEDはグラフ/グラフ検索のためのGPUベースのベースラインよりも最大50倍高速である。

関連論文リスト

• SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
  グラフ計算のための特徴指向最適化を備えたスケーラブルグラフニューラルネットワーク(GNN)であるSCARAを提案する。 SCARAはノードの特徴からグラフの埋め込みを効率的に計算し、機能の結果を選択して再利用することでオーバーヘッドを減らします。 利用可能な最大10億のGNNデータセットであるPapers100M(1110万ノード、1.6Bエッジ)を100秒でプリ計算するのが効率的である。
  論文  参考訳（メタデータ） (2022-07-19T10:32:11Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• Source Free Unsupervised Graph Domain Adaptation [60.901775859601685]
  Unsupervised Graph Domain Adaptation (UGDA) はノード分類のラベル付けコストを削減するための実用的価値を示している。 既存のUGDAメソッドの多くは、ソースドメインのラベル付きグラフに大きく依存している。 現実のシナリオでは、ソースグラフはプライバシーの問題のためにアクセスできない。 我々は、Source Free Unsupervised Graph Domain Adaptation (SFUGDA) という新しいシナリオを提案する。
  論文  参考訳（メタデータ） (2021-12-02T03:18:18Z)
• Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
  グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。 本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。 実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
  論文  参考訳（メタデータ） (2020-10-29T08:55:33Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。 本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
  論文  参考訳（メタデータ） (2020-08-03T08:48:41Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Isometric Graph Neural Networks [5.306334746787569]
  我々はIsometric Graph Neural Networks (IGNN) の学習手法を提案する。 IGNNは、任意のGNNアルゴリズムがノード間の距離を反映した表現を生成するために、入力表現空間と損失関数を変更する必要がある。 我々はケンドールのタウ(KT)の400%まで、一貫した実質的な改善を観察する。
  論文  参考訳（メタデータ） (2020-06-16T22:51:13Z)
• Graph Neural Distance Metric Learning with Graph-Bert [10.879701971582502]
  我々は、新しいグラフニューラルネットワークに基づく距離距離距離学習アプローチ、すなわちGB-DISTANCE(GRAPH-BERTベースのニューラル距離)を導入する。 GB-DISTANCEは、事前訓練された Graph-BERT モデルに基づいて、グラフ表現を効果的に学習することができる。 さらに、GB-DISTANCEは距離メートル法の基本特性も維持できる。
  論文  参考訳（メタデータ） (2020-02-09T18:58:31Z)

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

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