論文の概要: DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
- arxiv url: http://arxiv.org/abs/2308.08198v1
- Date: Wed, 16 Aug 2023 07:58:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-17 14:22:29.086934
- Title: DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
- Title（参考訳）: DeSCo: 汎用的でスケーラブルなディープグラフカウントを目指す
- Authors: Tianyu Fu, Chiyue Wei, Yu Wang, Rex Ying
- Abstract要約: サブグラフカウントは、ソーシャルネットワーク分析のためのモチーフカウントなど、さまざまな領域で有用である。
DeSCoはスケーラブルなニューラルネットワークサブグラフカウントパイプラインで、1回のトレーニング後にターゲットグラフ上のクエリカウントと発生位置を正確に予測することを目的としている。
DeSCoは、さまざまなドメインから8つの実世界のデータセットで評価される。
- 参考スコア（独自算出の注目度）: 13.790533532989269
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subgraph counting is the problem of counting the occurrences of a given query
graph in a large target graph. Large-scale subgraph counting is useful in
various domains, such as motif counting for social network analysis and loop
counting for money laundering detection on transaction networks. Recently, to
address the exponential runtime complexity of scalable subgraph counting,
neural methods are proposed. However, existing neural counting approaches fall
short in three aspects. Firstly, the counts of the same query can vary from
zero to millions on different target graphs, posing a much larger challenge
than most graph regression tasks. Secondly, current scalable graph neural
networks have limited expressive power and fail to efficiently distinguish
graphs in count prediction. Furthermore, existing neural approaches cannot
predict the occurrence position of queries in the target graph.
Here we design DeSCo, a scalable neural deep subgraph counting pipeline,
which aims to accurately predict the query count and occurrence position on any
target graph after one-time training. Firstly, DeSCo uses a novel canonical
partition and divides the large target graph into small neighborhood graphs.
The technique greatly reduces the count variation while guaranteeing no missing
or double-counting. Secondly, neighborhood counting uses an expressive
subgraph-based heterogeneous graph neural network to accurately perform
counting in each neighborhood. Finally, gossip propagation propagates
neighborhood counts with learnable gates to harness the inductive biases of
motif counts. DeSCo is evaluated on eight real-world datasets from various
domains. It outperforms state-of-the-art neural methods with 137x improvement
in the mean squared error of count prediction, while maintaining the polynomial
runtime complexity.
- Abstract（参考訳）: サブグラフカウント(Subgraph counting)は、あるクエリグラフの発生を大きなターゲットグラフでカウントする問題である。
大規模サブグラフカウントは、ソーシャルネットワーク分析のためのモチーフカウントや、トランザクションネットワークにおけるマネーロンダリング検出のためのループカウントなど、さまざまなドメインで有用である。
近年,スケーラブルなサブグラフカウントの指数関数的実行複雑性に対処するために,ニューラル手法を提案する。
しかし、既存のニューラルカウントアプローチは3つの側面で不足している。
第一に、同じクエリのカウントは、異なるターゲットグラフ上でゼロから数百万まで様々であり、ほとんどのグラフ回帰タスクよりもはるかに大きな課題を呈する。
第二に、現在のスケーラブルグラフニューラルネットワークは表現力に制限があり、カウント予測においてグラフを効率的に区別できない。
さらに、既存のニューラルアプローチでは、ターゲットグラフにおけるクエリの発生位置を予測できない。
ここでは,1回のトレーニング後に任意のグラフ上でクエリカウントと発生位置を正確に予測することを目的とした,スケーラブルなニューラルディープグラフカウントパイプラインであるDeSCoを設計する。
まず、DeSCoは新しい標準分割を使用し、大きなターゲットグラフを小さな近傍グラフに分割する。
この技術は、欠落やダブルカウントを保証しながら、カウントのバリエーションを大幅に減らす。
第二に、地区カウントは表現的部分グラフに基づく異種グラフニューラルネットワークを用いて、各地区で正確にカウントを行う。
最後に、ゴシップ伝播は、モチーフカウントの帰納バイアスを利用するために、学習可能なゲートで近隣のカウントを伝搬する。
DeSCoは、さまざまなドメインから8つの実世界のデータセットで評価される。
多項式ランタイムの複雑さを維持しつつ、カウント予測の平均二乗誤差を137倍改善することで、最先端のニューラルメソッドよりも優れています。
関連論文リスト
- Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳（メタデータ） (2024-01-12T17:57:07Z) - Stochastic Subgraph Neighborhood Pooling for Subgraph Classification [2.1270496914042996]
Subgraph Neighborhood Pooling (SSNP) は、ラベル付けトリックのような計算コストの高い操作をすることなく、サブグラフとその周辺情報を共同で集約する。
実験により、我々のモデルは、トレーニングにおいて最大3倍高速でありながら、最先端の手法(マージンが最大2%)より優れています。
論文 参考訳（メタデータ） (2023-04-17T18:49:18Z) - Path Integral Based Convolution and Pooling for Heterogeneous Graph
Neural Networks [2.5889737226898437]
グラフニューラルネットワーク(GNN)は、ディープラーニングをグラフ構造データセットに拡張する。
画像予測に使用する畳み込みニューラルネットワーク(CNN)と同様に、畳み込み層とプーリング層がグラフ予測タスクにおけるGNNの成功の基礎となっている。
論文 参考訳（メタデータ） (2023-02-26T20:05:23Z) - Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
リンク予測はグラフ構造化データ計算の基本的な問題である。
本稿では,スパース囲み部分グラフを用いて予測を行うScaLedというスケーラブルな解を提案する。
より小さなサンプルサブグラフを活用することで、ScaLedは高い精度を維持しながらオーバーヘッドをはるかに少なく大きなグラフにスケールすることができる。
論文 参考訳（メタデータ） (2022-06-23T22:48:44Z) - Personalized Subgraph Federated Learning [56.52903162729729]
本稿では,新たなサブグラフFL問題,パーソナライズされたサブグラフFLを導入する。
本稿では,Federated Personalized sUBgraph Learning (FED-PUB)を提案する。
オーバーラップしないサブグラフとオーバーラップするサブグラフの両方を考慮して,FED-PUBのサブグラフFL性能を6つのデータセットで検証した。
論文 参考訳（メタデータ） (2022-06-21T09:02:53Z) - Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors
to Sequences [55.329402218608365]
本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。
1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。
その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
論文 参考訳（メタデータ） (2022-02-07T16:38:36Z) - GREED: A Neural Framework for Learning Graph Distance Functions [8.323580169763726]
我々はGREEDと呼ばれる新しいシアムグラフニューラルネットワークを設計し、GEDとSEDをプロパティ保存方式で学習する。
最大700万のエッジを含む10のグラフデータセットを通じて、GREEDは最先端技術よりも正確であるだけでなく、最大3桁高速であることを示す。
論文 参考訳（メタデータ） (2021-12-24T21:46:40Z) - Uniformity in Heterogeneity:Diving Deep into Count Interval Partition
for Crowd Counting [56.44300325295678]
一様誤差分割(UEP)と呼ばれる新しいカウント間隔分割基準を提案する。
MCP基準は、推論中にそのカウント値を表すために、各インターバルのベストカウントプロキシを選択する。
統一誤り分割ネットワーク(UEPNet)と呼ばれる単純で効果的なモデルを提案する。
論文 参考訳（メタデータ） (2021-07-27T06:24:15Z) - Learning Graph Neural Networks with Positive and Unlabeled Nodes [34.903471348798725]
グラフニューラルネットワーク(GNN)は、グラフのノード分類など、トランスダクティブな学習タスクのための重要なツールです。
ほとんどのGNNモデルは、各ラウンドで短い距離から情報を集約し、グラフで長距離関係をキャプチャできません。
本論文では,これらの制限を克服するために,新しいグラフニューラルネットワークフレームワーク,LSDAN(Long-Short distance aggregation Network)を提案する。
論文 参考訳（メタデータ） (2021-03-08T11:43:37Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。