論文の概要: A Neural Framework for Learning Subgraph and Graph Similarity Measures
- arxiv url: http://arxiv.org/abs/2112.13143v1
- Date: Fri, 24 Dec 2021 21:46:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-29 11:55:40.701900
- Title: A Neural Framework for Learning Subgraph and Graph Similarity Measures
- Title（参考訳）: グラフとグラフの類似度を学習するためのニューラルネットワークフレームワーク
- Authors: Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan
Chakaravarthy, Yogish Sabharwal, Sayan Ranu
- Abstract要約: サブグラフ編集距離(サブグラフ編集距離、SubgraphEdit distance、SED)は、サブグラフの類似性を示す最も表現力のある尺度の1つである。
本研究では,グラフペアの学習セットとそのSED値からSEDを学習する問題について検討する。
我々は,SEDを連想させる構造を持つ埋め込み空間を学習するNEUROSEDと呼ばれる新しいシアムグラフニューラルネットワークを設計する。
- 参考スコア（独自算出の注目度）: 7.996891124160055
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Subgraph similarity search is a fundamental operator in graph analysis. In
this framework, given a query graph and a graph database, the goal is to
identify subgraphs of the database graphs that are structurally similar to the
query. Subgraph edit distance (SED) is one of the most expressive measures for
subgraph similarity. In this work, we study the problem of learning SED from a
training set of graph pairs and their SED values. Towards that end, we design a
novel siamese graph neural network called NEUROSED, which learns an embedding
space with a rich structure reminiscent of SED. With the help of a specially
crafted inductive bias, NEUROSED not only enables high accuracy but also
ensures that the predicted SED, like true SED, satisfies triangle inequality.
The design is generic enough to also model graph edit distance (GED), while
ensuring that the predicted GED space is metric, like the true GED space.
Extensive experiments on real graph datasets, for both SED and GED, establish
that NEUROSED achieves approximately 2 times lower RMSE than the state of the
art and is approximately 18 times faster than the fastest baseline. Further,
owing to its pair-independent embeddings and theoretical properties, NEUROSED
allows approximately 3 orders of magnitude faster retrieval of graphs and
subgraphs.
- Abstract（参考訳）: グラフ解析において、グラフ類似性探索は基本的な演算子である。
このフレームワークでは、クエリグラフとグラフデータベースが与えられた場合、クエリに構造的に類似したデータベースグラフのサブグラフを特定することが目的である。
サブグラフ編集距離(sed)は、サブグラフの類似性の最も表現力のある尺度の1つである。
本研究では,グラフペアの学習セットとそのSED値からSEDを学習する問題について検討する。
そこで我々は,SEDを連想させる構造を持つ埋め込み空間を学習するNEUROSEDと呼ばれる新しいシアムグラフニューラルネットワークを設計する。
NEUROSEDは特殊に製作された帰納バイアスの助けを借りて、高い精度を実現するだけでなく、予測されたSEDが真のSEDと同様に三角形の不等式を満たすことを保証する。
この設計はグラフ編集距離(GED)をモデル化するのに十分一般的なものであり、予測されたGED空間が真のGED空間のようにメートル法であることを保証している。
SEDとGEDの両方において、実際のグラフデータセットに関する大規模な実験により、NEUROSEDは最先端のベースラインの約18倍の速度でRMSEの約2倍の速度で達成されていることが証明された。
さらに、ペア独立な埋め込みと理論的性質のため、neurosedはグラフやサブグラフの検索を約3桁高速化できる。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。