Brief

<aside> ⭐ A generalizable, scalable and accurate neural subgraph counting algorithm

</aside>

中文说明 (Brief in Chinese)

Main Contributions

1. Canonical Partition:
   • Introduce "canonical partition" for accurate subgraph counting.
   • Avoids double-counting or missing patterns.
   • Predict pattern position distribution in graphs.

1. Subgraph-based Heterogeneous Message Passing:
   • Enhance graph neural networks with subgraph structure.
   • Improves accuracy and scalability in subgraph counting.
   • Outperforms expressive GNNs like GIN and ID-GNN.

1. Gossip Propagation:
   • Improve count prediction accuracy.
   • Leverage inductive biases like homophily and antisymmetry.
   • Introduce "gossip propagation" with learnable gate.

1. Generalization Framework:
   • Use synthetic data for model training.
   • Enables accurate subgraph counting on real-world datasets.
   • Ensures adaptability to various real-world scenarios.

Evaluation

Authors

Tianyu Fu, Chiyue Wei, Yu Wang*, and Rex Ying*

Paper

WSDM24_DeSCo_camera_ready.pdf