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

arXiv: https://arxiv.org/abs/2211.06793 · HTML: https://mlsanity.com/paper/2211.06793/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 67 references that are in the map.
- First posted on arXiv 13 Nov 2022.

## Builds on (most cited first, 15 of 15)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [TRI`EST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size](https://mlsanity.com/paper/1602.07424/) (2016)
- [A General Framework for Estimating Graphlet Statistics via Random Walk](https://mlsanity.com/paper/1603.07504/) (2016)
- [Motivo: fast motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/1906.01599/) (2019)
- [On Sampling from Massive Graph Streams](https://mlsanity.com/paper/1703.02625/) (2017)
- [WRS: Waiting Room Sampling for Accurate Triangle Counting in Real Graph Streams](https://mlsanity.com/paper/1709.03147/) (2017)
- [A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets](https://mlsanity.com/paper/1910.13011/) (2019)
- [Efficiently Estimating Motif Statistics of Large Networks](https://mlsanity.com/paper/1306.5288/) (2013)
- [Counting Motifs with Graph Sampling](https://mlsanity.com/paper/1802.07773/) (2018)
- [Waddling Random Walk: Fast and Accurate Mining of Motif Statistics in Large Graphs](https://mlsanity.com/paper/1605.09776/) (2016)
- [Distributed-Memory Parallel Algorithms for Counting and Listing Triangles in Big Graphs](https://mlsanity.com/paper/1706.05151/) (2017)
- [REPT: A Streaming Algorithm of Approximating Global and Local Triangle Counts in Parallel](https://mlsanity.com/paper/1811.09136/) (2018)
- [PES: Priority Edge Sampling in Streaming Triangle Estimation](https://mlsanity.com/paper/1812.01200/) (2018)

## Built on by (most cited first, 3 of 3)

- [RELIEF: Reinforcement Learning Empowered Graph Feature Prompt Tuning](https://mlsanity.com/paper/2408.03195/) (2024)
- [Learning and Editing Universal Graph Prompt Tuning via Reinforcement Learning](https://mlsanity.com/paper/2512.08763/) (2025)
- [FLASH: Flexible Learning of Adaptive Sampling from History in Temporal Graph Neural Networks](https://mlsanity.com/paper/2504.07337/) (2025)

## Abstract (arXiv)

As the popularity of graph data increases, there is a growing need to count the occurrences of subgraph patterns of interest, for a variety of applications. Many graphs are massive in scale and also fully dynamic (with insertions and deletions of edges), rendering exact computation of these counts to be infeasible. Common practice is, instead, to use a small set of edges as a sample to estimate the counts. Existing sampling algorithms for fully dynamic graphs sample the edges with uniform probability. In this paper, we show that we can do much better if we sample edges based on their individual properties. Specifically, we propose 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. We determine the weights of edges in a data-driven fashion, using a novel method based on reinforcement learning. We conduct extensive experiments to verify that our technique can produce estimates with smaller errors while often running faster compared with existing algorithms.