DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting

• URL: http://arxiv.org/abs/2308.08198v2
• Date: Wed, 20 Dec 2023 02:31:25 GMT
• Title: DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
• Authors: Tianyu Fu, Chiyue Wei, Yu Wang, Rex Ying
• Abstract summary: We introduce DeSCo, a scalable neural deep subgraph counting pipeline. It is designed to accurately predict the count and occurrence position of queries on target graphs post single training. DeSCo is evaluated on eight real-world datasets from various domains.
• Score: 13.790533532989269
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce DeSCo, a scalable neural deep subgraph counting pipeline, designed to accurately predict both the count and occurrence position of queries on target graphs post single training. Firstly, DeSCo uses a novel canonical partition and divides the large target graph into small neighborhood graphs, greatly reducing the count variation while guaranteeing no missing or double-counting. Secondly, neighborhood counting uses an expressive subgraph-based heterogeneous graph neural network to accurately count 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. Our open source project is at https://github.com/fuvty/DeSCo.

Related papers

• Exact Acceleration of Subgraph Graph Neural Networks by Eliminating Computation Redundancy [49.233339837170895]
  This paper introduces Ego-Nets-Fit-All (ENFA), a model that uniformly takes the smaller ego nets as subgraphs. ENFA can reduce storage space by 29.0% to 84.5% and improve training efficiency by up to 1.66x.
  arXiv  Detail & Related papers  (2024-12-24T03:21:03Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Stochastic Subgraph Neighborhood Pooling for Subgraph Classification [2.1270496914042996]
  Subgraph Neighborhood Pooling (SSNP) jointly aggregates the subgraph and its neighborhood information without any computationally expensive operations such as labeling tricks. Our experiments demonstrate that our models outperform current state-of-the-art methods (with a margin of up to 2%) while being up to 3X faster in training.
  arXiv  Detail & Related papers  (2023-04-17T18:49:18Z)
• Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
  Link prediction is a fundamental problem for graph-structured data computation. This paper presents a scalable solution, that we call ScaLed, which utilizes sparse enclosing subgraphs to make predictions. By leveraging the smaller sampled subgraph, ScaLed can scale to larger graphs with much less overhead while maintaining high accuracy.
  arXiv  Detail & Related papers  (2022-06-23T22:48:44Z)
• Personalized Subgraph Federated Learning [56.52903162729729]
  We introduce a new subgraph FL problem, personalized subgraph FL, which focuses on the joint improvement of the interrelated local GNNs. We propose a novel framework, FEDerated Personalized sUBgraph learning (FED-PUB), to tackle it. We validate our FED-PUB for its subgraph FL performance on six datasets, considering both non-overlapping and overlapping subgraphs.
  arXiv  Detail & Related papers  (2022-06-21T09:02:53Z)
• GREED: A Neural Framework for Learning Graph Distance Functions [8.323580169763726]
  We design a novel siamese graph neural network called GREED, which learns GED and SED in a property-preserving manner. Through extensive 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.
  arXiv  Detail & Related papers  (2021-12-24T21:46:40Z)
• Uniformity in Heterogeneity:Diving Deep into Count Interval Partition for Crowd Counting [56.44300325295678]
  We propose a novel count interval partition criterion called Uniform Error Partition (UEP) MCP criterion selects the best count proxy for each interval to represent its count value during inference. We propose a simple yet effective model termed Uniform Error Partition Network (UEPNet)
  arXiv  Detail & Related papers  (2021-07-27T06:24:15Z)
• Learning Graph Neural Networks with Positive and Unlabeled Nodes [34.903471348798725]
  Graph neural networks (GNNs) are important tools for transductive learning tasks, such as node classification in graphs. Most GNN models aggregate information from short distances in each round, and fail to capture long distance relationship in graphs. In this paper, we propose a novel graph neural network framework, long-short distance aggregation networks (LSDAN) to overcome these limitations.
  arXiv  Detail & Related papers  (2021-03-08T11:43:37Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
  arXiv  Detail & Related papers  (2020-07-03T09:30:07Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.