Skip to Main content Skip to Navigation
Journal articles

Learning to count: A deep learning framework for graphlet count estimation

Abstract : Graphlet counting is a widely-explored problem in network analysis and has been successfully applied to a variety of applications in many domains, most notatbly bioinformatics, social science and infrastructure network studies. Efficiently computing graphlet counts remains challenging due to the combinatorial explosion, where a naive enumeration algorithm needs O($N^k$) time for $k$-node graphlets in a network of size $N$. Recently, many works introduced carefully designed combinatorial and sampling methods with encouraging results. However, the existing methods ignore the fact that graphlet counts and the graph structural information are correlated. They always consider a graph as a new input and repeat the tedious counting procedure on a regular basis even if it is similar or exactly isomorphic to previously studied graphs. This provides an opportunity to speed up the graphlet count estimation procedure by exploiting this correlation via learning methods. In this paper, we raise a novel Graphlet Count Learning (GCL) problem: given a set of historical graphs with known graphlet counts, how to learn to estimate/predict graphlet count for unseen graphs coming from the same (or similar) underlying distribution. We develop a deep learning framework which contains two {\em convolutional neural network} (CNN) models and a series of data {\em preprocessing techniques} to solve the GCL problem. Extensive experiments are conducted on three types of synthetic random graphs and three types of real world graphs for all 3,4,5-node graphlets to demonstrate the accuracy, efficiency and generalizability of our framework. Compared with state-of-the-art exact/sampling methods, our framework shows great potential, which can offer up to two orders of magnitude speedup on synthetic graphs and achieves on par speed on real world graphs with competitive accuracy.
Complete list of metadatas

Cited literature [58 references]  Display  Hide  Download

https://hal.inria.fr/hal-02942321
Contributor : Konstantin Avrachenkov <>
Submitted on : Thursday, September 17, 2020 - 5:05:37 PM
Last modification on : Wednesday, October 14, 2020 - 3:57:38 AM

File

Learning2Count_arxiv.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Xutong Liu, Yu-Zhen Janice Chen, John C. S. Lui, Konstantin Avrachenkov. Learning to count: A deep learning framework for graphlet count estimation. Network Science, Cambridge University Press, 2020, pp.30. ⟨10.1017/nws.2020.35⟩. ⟨hal-02942321⟩

Share

Metrics

Record views

27

Files downloads

123