Noname manuscript No. (will be inserted by the editor) Rand-FaSE: Fast Approximate Subgraph Census

Abstract Determining the frequency of small subgraphs is an important graph mining primitive. One major class of algorithms for this task is based upon the enu-meration of all sets of k connected nodes. These are known as network-centric algorithms. FaSE is a ex-act algorithm for subgraph counting that contrasted with its past approaches by performing the isomor-phism tests while doing the enumeration, encapsulat-ing the topological information in a g-trie and thus largely reducing the number of required isomorphism tests. Our goal with this paper is to expand this ap-proach by providing an approximate algorithm, which we called Rand-FaSE. It uses an unbiased sampling es-timator for the number of subgraphs of each type, al-lowing an user to trade some accuracy for even faster execution times. We tested our algorithm on a set of representative complex networks, comparing it with the exact alternative, FaSE. We also do an extensive analy-sis by studying its accuracy and speed gains against pre-vious sampling approaches. With all of this, we believe FaSE and Rand-FaSE pave the way for faster network-centric census algorithms