A Fast Sampling Method of Exploring Graphlet Degrees of Large Directed and Undirected Graphs

Pinghui Wang, Xiangliang Zhang, Zhenguo Li, Jiefeng Cheng, John C. S. Lui, Don Towsley, Junzhou Zhao, Jing Tao, Xiaohong GuanarXiv 2016 · arXiv

Graphlets—small, connected network subgraphs—are fundamental building blocks for analyzing network topology. While global graphlet counts provide a macro-level view of a network, understanding the specific role a node plays within these structures requires calculating graphlet orbit degrees. However, as networks grow into the millions of nodes and edges, counting these node-specific positions becomes computationally explosive.

This paper introduces SAND and SAND-3D, a suite of fast sampling algorithms designed to estimate node-specific graphlet degrees for large undirected and directed graphs. These methods achieve speedups of several orders of magnitude compared to traditional brute-force enumeration while maintaining high accuracy.

The Challenge: Node-Specific Structural Roles

In network analysis, nodes are not just points; they occupy distinct structural positions called automorphism orbits. For example, in a three-node path (A—B—C), the center node (B) acts as a hub, while the outer nodes (A and C) are leaves. These positions are structurally different even though they belong to the same graphlet.

Overview of 2-, 3-, and 4-node undirected graphlets and 3-node directed graphlets with their corresponding orbits labeled in blue.

Counting how many times a specific node appears in each possible orbit yields a "graphlet orbit degree signature." This signature is a highly descriptive feature vector used for critical tasks like protein function prediction or social network link prediction. However, for a highly connected node in a massive graph, enumerating every 3- or 4-node subgraph it belongs to is a combinatorial nightmare. Prior to this work, no scalable sampling methods existed specifically for node-level graphlet orbit degrees.

Methodology: SAND and SAND-3D

Instead of exhaustive counting, the authors propose a hybrid sampling framework. The core of the approach involves:

  1. Targeted Samplers: Six distinct sampling methods (e.g., Randgraf-3-1, Randgraf-4-2) were developed to sample connected induced subgraphs (CISes) that include a specific target node. Each method is optimized to capture specific orbits efficiently.
  2. Hybrid Frameworks: SAND (for undirected graphs) and SAND-3D (for directed graphs) combine these samplers. Because directed graphs are significantly more complex—having 30 distinct orbits for 3-node graphlets alone—sampling becomes a necessity rather than just an optimization.
  3. Variance-Weighted Estimation: To ensure accuracy, the framework calculates unbiased estimates for each orbit degree. When multiple samplers can estimate the same orbit, they are combined using a minimum variance weighting technique.
  4. Mathematical Optimization: The authors identified linear relationships between different undirected orbit degrees. SAND leverages these equations to algebraically deduce certain orbit counts, skipping unnecessary sampling steps entirely.

Key Results and Performance

The algorithms were evaluated on large-scale datasets from the Stanford Network Analysis Platform (SNAP), including Flickr, Pokec, and Wiki-Talk. The results demonstrate a paradigm shift in performance:

  • Massive Speedups: For undirected graphs, SAND was up to 183x faster than state-of-the-art enumeration (4-Prof-Dist). For directed graphs, SAND-3D achieved an astronomical 36,034x speedup on the Wiki-Talk dataset.
  • High Accuracy: Despite the speed, the sampling remains robust. For the most frequent orbits, the Normalized Root Mean Square Error (NRMSE) was consistently below 0.1 across various datasets.
Accuracy of SAND across different datasets, showing the Normalized Root Mean Square Error (NRMSE) for undirected orbits 1 through 14.

Conclusion and Future Directions

By shifting the focus from graph-centric to node-centric sampling, the authors have enabled the analysis of local structural signatures in graphs that were previously too large to process. While the current implementation focuses on 3- and 4-node graphlets, future work aims to extend these methods to 5-node structures and further optimize the distribution of sampling budgets. These fast-to-compute signatures open new doors for real-time machine learning applications in massive social and biological networks.

Summary updated

Abstract

Exploring small connected and induced subgraph patterns (CIS patterns, or graphlets) has recently attracted considerable attention. Despite recent efforts on computing the number of instances a specific graphlet appears in a large graph (i.e., the total number of CISes isomorphic to the graphlet), little attention has been paid to characterizing a node's graphlet degree, i.e., the number of CISes isomorphic to the graphlet that include the node, which is an important metric for analyzing complex networks such as social and biological networks. Similar to global graphlet counting, it is challenging to compute node graphlet degrees for a large graph due to the combinatorial nature of the problem. Unfortunately, previous methods of computing global graphlet counts are not suited to solve this problem. In this paper we propose sampling methods to estimate node graphlet degrees for undirected and directed graphs, and analyze the error of our estimates. To the best of our knowledge, we are the first to study this problem and give a fast scalable solution. We conduct experiments on a variety of real-word datasets that demonstrate that our methods accurately and efficiently estimate node graphlet degrees for graphs with millions of edges.
BibTeX
@misc{wang2016fast,
  author = {Pinghui Wang and Xiangliang Zhang and Zhenguo Li and Jiefeng Cheng and John C. S. Lui and Don Towsley and Junzhou Zhao and Jing Tao and Xiaohong Guan},
  title = {{A Fast Sampling Method of Exploring Graphlet Degrees of Large Directed and Undirected Graphs}},
  year = {2016},
  eprint = {1604.08691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.08691},
}
Figure