論文の概要: Representation Learning for Frequent Subgraph Mining
- arxiv url: http://arxiv.org/abs/2402.14367v1
- Date: Thu, 22 Feb 2024 08:11:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 15:51:36.197375
- Title: Representation Learning for Frequent Subgraph Mining
- Title（参考訳）: 頻繁なサブグラフマイニングのための表現学習
- Authors: Rex Ying, Tianyu Fu, Andrew Wang, Jiaxuan You, Yu Wang, Jure Leskovec
- Abstract要約: Subgraph Pattern Miner (SPMiner) は、大きなターゲットグラフに頻繁なサブグラフを見つけるための新しいニューラルネットワークである。
5ノードと6ノードのモチーフでは、SPMinerは正確な列挙法よりも100倍速く、最も頻繁なモチーフをほぼ完全に識別できる。
SPMinerは、10ノードの頻繁なモチーフを確実に特定できる。
- 参考スコア（独自算出の注目度）: 64.32430554934021
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Identifying frequent subgraphs, also called network motifs, is crucial in
analyzing and predicting properties of real-world networks. However, finding
large commonly-occurring motifs remains a challenging problem not only due to
its NP-hard subroutine of subgraph counting, but also the exponential growth of
the number of possible subgraphs patterns. Here we present Subgraph Pattern
Miner (SPMiner), a novel neural approach for approximately finding frequent
subgraphs in a large target graph. SPMiner combines graph neural networks,
order embedding space, and an efficient search strategy to identify network
subgraph patterns that appear most frequently in the target graph. SPMiner
first decomposes the target graph into many overlapping subgraphs and then
encodes each subgraph into an order embedding space. SPMiner then uses a
monotonic walk in the order embedding space to identify frequent motifs.
Compared to existing approaches and possible neural alternatives, SPMiner is
more accurate, faster, and more scalable. For 5- and 6-node motifs, we show
that SPMiner can almost perfectly identify the most frequent motifs while being
100x faster than exact enumeration methods. In addition, SPMiner can also
reliably identify frequent 10-node motifs, which is well beyond the size limit
of exact enumeration approaches. And last, we show that SPMiner can find large
up to 20 node motifs with 10-100x higher frequency than those found by current
approximate methods.
- Abstract（参考訳）: ネットワークモチーフとも呼ばれる頻繁なサブグラフの同定は、実世界のネットワークの特性の分析と予測に不可欠である。
しかし,大きなモチーフの発見は,サブグラフカウントのnpハードサブルーチンだけでなく,可能なサブグラフパターンの数の指数関数的増加にも起因して,依然として困難な課題である。
本稿では,大規模対象グラフにおける頻繁な部分グラフの探索を近似する新しいニューラルネットワークであるsubgraph pattern miner (spminer)を提案する。
SPMinerは、グラフニューラルネットワーク、順序埋め込みスペース、ターゲットグラフに最も頻繁に現れるネットワークサブグラフパターンを特定するための効率的な検索戦略を組み合わせる。
SPMinerはまずターゲットグラフを多くの重なり合う部分グラフに分解し、各サブグラフを順序埋め込み空間にエンコードする。
SPMinerは、順番埋め込み空間における単調ウォークを使用して、頻繁なモチーフを識別する。
既存のアプローチやニューラルネットワークの代替手段と比較して、SPMinerはより正確で、高速で、スケーラブルである。
5ノードと6ノードのモチーフに対して、SPMinerは正確な列挙法よりも100倍速く、最も頻繁なモチーフをほぼ完全に識別できることを示す。
さらに、spminerは頻繁に発生する10ノードのモチーフを確実に識別することができる。
最後に、spminerは最大20個のノードモチーフを、現在の近似手法より10-100倍高い周波数で発見できることを示した。
関連論文リスト
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening [18.688057947275112]
グラフグラフニューラルネットワーク(サブグラフGNN)は,グラフをサブグラフの集合として表現することで,メッセージパスGNNの表現性を向上する。
以前のアプローチでは、ランダムにまたは学習可能なサンプリングによって選択されたサブグラフのサブセットのみを処理することを提案していた。
本稿では,これらの問題に対処する新しいSubgraph GNNフレームワークを提案する。
論文 参考訳（メタデータ） (2024-06-13T16:29:06Z) - Tensorized Hypergraph Neural Networks [69.65385474777031]
我々は,新しいアジャケーシテンソルベースのtextbfTensorized textbfHypergraph textbfNeural textbfNetwork (THNN) を提案する。
THNNは高次外装機能パッシングメッセージを通じて、忠実なハイパーグラフモデリングフレームワークである。
3次元視覚オブジェクト分類のための2つの広く使われているハイパーグラフデータセットの実験結果から、モデルの有望な性能を示す。
論文 参考訳（メタデータ） (2023-06-05T03:26:06Z) - 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) - Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
グラフ上の部分グラフ同型カウントは重要な問題である。
本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
論文 参考訳（メタデータ） (2023-02-07T05:32:11Z) - Digraphwave: Scalable Extraction of Structural Node Embeddings via
Diffusion on Directed Graphs [20.432261314154804]
Digraphwaveは、有向グラフ上の構造ノード埋め込みを抽出するスケーラブルなアルゴリズムである。
この2つの組込み強化は、自己同型アイデンティティの分類において、マクロF1スコアの顕著な増加につながることが示されている。
論文 参考訳（メタデータ） (2022-07-20T19:03:35Z) - Subgraph Frequency Distribution Estimation using Graph Neural Networks [17.02487540304784]
本稿では,グラフニューラルネットワークを用いた新しい表現学習フレームワークであるGNNSを提案する。
我々のフレームワークは、ノード、サブグラフ、グラフの階層的な埋め込みを学習する推論モデルと生成モデルを含む。
学習したモデルと埋め込みを用いて、サブグラフを高度にスケーラブルで並列な方法でサンプリングし、これらのサンプリングされたサブグラフに基づいて周波数分布推定を行う。
論文 参考訳（メタデータ） (2022-07-14T06:23:38Z) - Subgraph Neural Networks [14.222887950206662]
本稿では,不整合部分グラフ表現を学習するためのサブグラフニューラルネットワークSubGNNを紹介する。
SubGNNは、挑戦的なバイオメディカルデータセットで非常によく機能する。
論文 参考訳（メタデータ） (2020-06-18T13:54:30Z) - Structural Temporal Graph Neural Networks for Anomaly Detection in
Dynamic Graphs [54.13919050090926]
本稿では,動的グラフの異常エッジを検出するために,エンドツーエンドの時間構造グラフニューラルネットワークモデルを提案する。
特に,まずターゲットエッジを中心にした$h$ホップ囲むサブグラフを抽出し,各ノードの役割を識別するノードラベル機能を提案する。
抽出した特徴に基づき,GRU(Gated Recurrent Unit)を用いて,異常検出のための時間的情報を取得する。
論文 参考訳（メタデータ） (2020-05-15T09:17:08Z) - Analyzing Neural Networks Based on Random Graphs [77.34726150561087]
様々なタイプのランダムグラフに対応するアーキテクチャを用いて,ニューラルネットワークの大規模評価を行う。
古典的な数値グラフ不変量は、それ自体が最良のネットワークを選び出すことができない。
また、主に短距離接続を持つネットワークは、多くの長距離接続が可能なネットワークよりも性能が良いことも見出した。
論文 参考訳（メタデータ） (2020-02-19T11:04:49Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。