論文の概要: Learning to Count Isomorphisms with Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2302.03266v1
- Date: Tue, 7 Feb 2023 05:32:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-08 17:17:47.962974
- Title: Learning to Count Isomorphisms with Graph Neural Networks
- Title(参考訳): グラフニューラルネットワークによる同型の数え方学習
- Authors: Xingtong Yu, Zemin Liu, Yuan Fang, Xinming Zhang
- Abstract要約: グラフ上の部分グラフ同型カウントは重要な問題である。
本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
- 参考スコア(独自算出の注目度): 16.455234748896157
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subgraph isomorphism counting is an important problem on graphs, as many
graph-based tasks exploit recurring subgraph patterns. Classical methods
usually boil down to a backtracking framework that needs to navigate a huge
search space with prohibitive computational costs. Some recent studies resort
to graph neural networks (GNNs) to learn a low-dimensional representation for
both the query and input graphs, in order to predict the number of subgraph
isomorphisms on the input graph. However, typical GNNs employ a node-centric
message passing scheme that receives and aggregates messages on nodes, which is
inadequate in complex structure matching for isomorphism counting. Moreover, on
an input graph, the space of possible query graphs is enormous, and different
parts of the input graph will be triggered to match different queries. Thus,
expecting a fixed representation of the input graph to match diversely
structured query graphs is unrealistic. In this paper, we propose a novel GNN
called Count-GNN for subgraph isomorphism counting, to deal with the above
challenges. At the edge level, given that an edge is an atomic unit of encoding
graph structures, we propose an edge-centric message passing scheme, where
messages on edges are propagated and aggregated based on the edge adjacency to
preserve fine-grained structural information. At the graph level, we modulate
the input graph representation conditioned on the query, so that the input
graph can be adapted to each query individually to improve their matching.
Finally, we conduct extensive experiments on a number of benchmark datasets to
demonstrate the superior performance of Count-GNN.
- Abstract(参考訳): グラフに基づく多くのタスクが繰り返しグラフパターンを利用するため、グラフ上の部分グラフ同型カウントは重要な問題である。
古典的な手法は通常、計算コストを抑えながら巨大な検索スペースをナビゲートする必要があるバックトラックフレームワークに導かれる。
最近の研究では、グラフニューラルネットワーク(gnns)を使用して、クエリグラフと入力グラフの両方の低次元表現を学習し、入力グラフ上の部分グラフ同型の数を予測する。
しかし、典型的なGNNでは、ノード上のメッセージを受信して集約するノード中心のメッセージパッシング方式を採用しており、同型カウントの複雑な構造マッチングでは不十分である。
さらに、入力グラフ上では、可能なクエリグラフの空間は巨大であり、入力グラフの異なる部分が異なるクエリにマッチするようにトリガーされる。
したがって、多様な構造化クエリグラフにマッチする入力グラフの固定表現を期待することは現実的ではない。
本稿では,これらの課題に対処するため,サブグラフ同型カウントのための新しいGNNであるCount-GNNを提案する。
エッジレベルでは、エッジがグラフ構造を符号化するアトミック単位であることを考えると、エッジ上のメッセージはエッジ隣接に基づいて伝播・集約され、きめ細かい構造情報を保存できるエッジ中心のメッセージパッシングスキームを提案する。
グラフレベルでは、クエリに条件付けされた入力グラフ表現を変調し、入力グラフを各クエリに個別に適応させ、マッチングを改善する。
最後に,多数のベンチマークデータセットに対して,Count-GNNの優れた性能を示す広範囲な実験を行った。
関連論文リスト
- Learning on Large Graphs using Intersecting Communities [13.053266613831447]
MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。
MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。
本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
論文 参考訳(メタデータ) (2024-05-31T09:26:26Z) - SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
グラフニューラルネットワーク(GNN)は、グラフやネットワークのような非ユークリッドデータ上での機械学習の分野に革命をもたらした。
本稿では,ノード表現をインジェクティブに更新する結合型グラフ畳み込み機構を提案する。
また,WL-SortPoolと呼ばれるグラフプーリングモジュールを設計し,重要なサブグラフパターンをディープラーニングで学習する。
論文 参考訳(メタデータ) (2024-04-21T13:11:59Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳(メタデータ) (2023-05-18T07:27:18Z) - FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。
本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。
提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-10-21T07:58:03Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳(メタデータ) (2022-03-03T09:53:53Z) - Interactive Visual Pattern Search on Graph Data via Graph Representation
Learning [20.795511688640296]
視覚分析システムGraphQは、ループ内、サンプルベース、サブグラフパターン検索をサポートする。
高速で対話的なクエリをサポートするために、グラフニューラルネットワーク(GNN)を使用して、グラフを固定長潜在ベクトル表現としてエンコードする。
また,NuroAlignと呼ばれるノードアライメントのための新しいGNNを提案し,クエリ結果の検証と解釈を容易にする。
論文 参考訳(メタデータ) (2022-02-18T22:30:28Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。
最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。
本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
論文 参考訳(メタデータ) (2020-11-19T06:03:35Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳(メタデータ) (2020-10-20T05:54:31Z) - Inverse Graph Identification: Can We Identify Node Labels Given Graph
Labels? [89.13567439679709]
グラフ識別(GI)は、グラフ学習において長い間研究されており、特定の応用において不可欠である。
本稿では,逆グラフ識別(Inverse Graph Identification, IGI)と呼ばれる新しい問題を定義する。
本稿では,グラフアテンションネットワーク(GAT)を用いたノードレベルのメッセージパッシング処理を,GIのプロトコルの下でシンプルかつ効果的に行う方法を提案する。
論文 参考訳(メタデータ) (2020-07-12T12:06:17Z) - Graph Pooling with Node Proximity for Hierarchical Representation
Learning [80.62181998314547]
本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。
その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
論文 参考訳(メタデータ) (2020-06-19T13:09:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。