Fast and accurate graphlet estimation

A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for estimating a number of graphlets in a graph, the method comprising:

• obtaining, by the computer, a data structure representing a graph comprising vertices and edges;
• performing graph sampling, using a graph sampling technique by the computer, on the graph based on a property of the graph to obtain a subgraph of the graph, wherein the subgraph comprises a subset of vertices and edges of the graph selected by the graph sampling technique;
• determining a first number of occurrences of one or more graph features in the sampled subgraph of the graph;
• determining, based on graph combinatorics, a combinatorial relationship applicable to the first number of occurrences of the one or more graph features;
• determining, based on applying the combinatorial relationship to the first number of occurrences, a second number of occurrences of a graphlet pattern in the sampled subgraph of the graph, wherein the combinatorial relationship is between the one or more graph features and the graphlet pattern, and wherein the graphlet pattern indicates a number of vertices in a graphlet and a pattern of edges between the vertices of the graphlet;
• and
• determining, based on the second number of occurrences, a total number of graphlets associated with the graphlet pattern in the graph by scaling up the second number of occurrences based on a topological factor.

A computing system for estimating a number of graphlets in a graph, the computing system comprising:

• a set of processors;
• and
• a non-transitory computer-readable medium coupled to the set of processors storing instructions thereon that, when executed by the processors, cause the processors to perform a method for estimating a number of graphlets in a graph, the method comprising:
• obtaining, by the set of processors, a data structure representing a graph comprising vertices and edges;
• performing, using a graph sampling technique by the computing system, graph sampling on the graph based on a property of the graph to obtain a subgraph of the graph, wherein the subgraph comprises a subset of vertices and edges of the graph selected by the graph sampling technique;
• determining a first number of occurrences of one or more graph features in the sampled subgraph of the graph;
• determining, based on graph combinatorics, a combinatorial relationship applicable to the first number of occurrences of the one or more graph features;
• determining, based on applying the combinatorial relationship to the first number of occurrences, a second number of occurrences of a graphlet pattern in the sampled subgraph of the graph, wherein the combinatorial relationship is between the one or more graph features and the graphlet pattern, and wherein the graphlet pattern indicates a number of vertices in a graphlet and a pattern of edges between the vertices of the graphlet;
• and
• determining, based on the second number of occurrences, a total number of graphlets associated with the graphlet pattern in the graph by scaling up the second number of occurrences based on a topological factor.