Brief
![DeSCo_poster.1.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/50902001-6347-4df6-b51a-a8e5864a2769/DeSCo_poster.1.png)
<aside>
⭐ A generalizable, scalable and accurate neural subgraph counting algorithm
</aside>
中文说明 (Brief in Chinese)
Main Contributions
![workflow.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/9122e1ac-86bf-49ad-b032-fe9ded825b54/workflow.png)
- Canonical Partition:
- Introduce "canonical partition" for accurate subgraph counting.
- Avoids double-counting or missing patterns.
- Predict pattern position distribution in graphs.
![截屏2023-10-20 13.15.39.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/232cdbe9-c6c4-40cd-be5d-1b2b130569ff/%E6%88%AA%E5%B1%8F2023-10-20_13.15.39.png)
- 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.
![截屏2023-10-20 13.16.00.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/26c040c7-bded-40da-81b9-af642b25cc5e/%E6%88%AA%E5%B1%8F2023-10-20_13.16.00.png)
- Gossip Propagation:
- Improve count prediction accuracy.
- Leverage inductive biases like homophily and antisymmetry.
- Introduce "gossip propagation" with learnable gate.
![截屏2023-10-20 13.16.07.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/14014d36-bbba-4b88-bde3-22b90412e9db/%E6%88%AA%E5%B1%8F2023-10-20_13.16.07.png)
- Generalization Framework:
- Use synthetic data for model training.
- Enables accurate subgraph counting on real-world datasets.
- Ensures adaptability to various real-world scenarios.
![截屏2023-10-20 13.17.12.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/872ec0bc-5050-44f7-a4ad-59954daeb3ae/%E6%88%AA%E5%B1%8F2023-10-20_13.17.12.png)
Evaluation
![截屏2023-10-20 13.17.59.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/1ee53664-5d2d-4679-8c53-556cf9cf79b8/%E6%88%AA%E5%B1%8F2023-10-20_13.17.59.png)
![截屏2023-10-20 13.18.24.png](https://prod-files-secure.s3.us-west-2.amazonaws.com/755760cf-23a5-4652-996f-6baff6b101ae/b44d03d8-0f12-4605-9dad-e68f54d93e17/%E6%88%AA%E5%B1%8F2023-10-20_13.18.24.png)
Authors
Tianyu Fu, Chiyue Wei, Yu Wang*, and Rex Ying*
Paper
WSDM24_DeSCo_camera_ready.pdf