Home Research Papers Datasets State of the Art Pricing

Discover, visualize, and connect AI research papers. Explore the latest trends and insights in artificial intelligence research.

Product

Home
Research Papers
About

Support

Contact
Terms of Service
Privacy Policy

graphs-1

Subgraph Counting

3260 papers • 126 benchmarks • 313 datasets

This task has no description! Would you like to contribute one?

(Image credit: Papersgraph)

Benchmarks

These leaderboards are used to track progress in subgraph-counting-1

Trend

Dataset

Best Model

Actions

No benchmarks available.

Libraries

Use these libraries to find subgraph-counting-1 models and implementations

Datasets

Synthetic Graph

Subtasks

No subtasks available.

Most implemented papers

Evaluating Graph Generative Models with Contrastively Learned Features

Hamed Shirzad, Kaveh Hassani, Danica J. Sutherland•Sun Jun 12 2022

It is demonstrated that Graph Substructure Networks (GSNs), which in a way combine both approaches, are better at distinguishing the distances between graph datasets.

Content

Introduction Benchmarks Datasets Subtasks Libraries Papers

Paper Graph

Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams

H. V. Jagadish, J. Zhang, Kaixin Wang, Cheng Long, Da Yan•Sat Nov 12 2022

This paper proposes a weighted sampling algorithm called WSD for estimating the subgraph count in a fully dynamic graph stream, which samples the edges based on their weights that indicate their importance and reflect their properties.

4 0

Paper Graph

Improving Expressivity of Graph Neural Networks

Stanislaw J. Purgal•Tue Apr 07 2020

A Graph Neural Network with greater expressive power than commonly used GNNs — not constrained to only differentiate between graphs that Weisfeiler-Lehman test recognizes to be non-isomorphic is proposed.

5 0

Paper Graph

DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting

Rex Ying, Tianyu Fu, Chiyue Wei, Yu Wang•Tue Aug 15 2023

DeSCo is introduced, 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, and outperforms state-of-the-art neural methods with 137× improvement in the mean squared error of count prediction, while maintaining the polynomial runtime complexity.

7 0

Paper Graph

Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness

Stephan Günnemann, Francesco Campi, Lukas Gosch, Tom Wollschlager, Yan Scholten•Tue Aug 15 2023

This work develops efficient adversarial attacks for subgraph counting and shows that more powerful GNNs fail to generalize even to small perturbations to the graph's structure, and that such architectures also fail to count substructures on out-of-distribution graphs.

2 0

Paper Graph

Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions

Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya•Mon Dec 11 2023

We suggest the use of hash functions to cut down the communication costs when counting subgraphs under edge local differential privacy. While various algorithms exist for computing graph statistics, including the count of subgraphs, under the edge local differential privacy, many suffer with high communication costs, making them less efficient for large graphs. Though data compression is a typical approach in differential privacy, its application in local differential privacy requires a form of compression that every node can reproduce. In our study, we introduce linear congruence hashing. With a sampling rate of $s$, our method can cut communication costs by a factor of $s^2$, albeit at the cost of increasing variance in the published graph statistic by a factor of $s$. The experimental results indicate that, when matched for communication costs, our method achieves a reduction in the $\ell_2$-error for triangle counts by up to 1000 times compared to the performance of leading algorithms.

8 0

Paper Graph

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness

Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, Liwei Wang•Mon Jan 15 2024

A unified framework for quantitatively studying the expressiveness of GNN architectures is introduced, which identifies a fundamental expressivity measure termed homomorphism expressivity, which quantifies the ability of GNN models to count graphs under homomorphism.

55 0

Paper Graph

Adding a benchmark result helps the community track progress.

Subgraph Counting | State-of-the-Art