TL;DR
This paper introduces "Lifting," a novel Monte Carlo sampling framework for efficiently estimating graphlet counts in massive networks. Lifting offers a unified approach to sample all graphlet types simultaneously, scales to large networks and complex graphlets, and provides theoretical guarantees on unbiasedness and controlled variance, outperforming existing methods in many scenarios.
What Problem Does This Paper Address?
Understanding the structure of large networks (like social networks, biological networks, or the internet) is crucial for many applications. A key way to do this is by analyzing "graphlets" – small, recurring subgraph patterns (e.g., triangles, wedges). However, accurately counting these graphlets in massive networks is computationally challenging. Existing methods either require full network access, are limited to small graphlets, or suffer from slow convergence and bias. This paper aims to bridge this gap by providing an efficient, scalable, and theoretically sound method for estimating graphlet statistics in large-scale networks.
Methods
The core contribution is the Lifting framework, a Monte Carlo sampling technique. Instead of directly sampling graphlets, Lifting works inductively:
- Bottom-Up Construction: It starts with a small, connected subgraph (a CIS) and "lifts" it to a larger one by adding a new vertex from its neighborhood. This process is repeated until a graphlet of the desired size is formed.
- Probabilistic Sampling: The probability of adding a vertex is determined by local neighborhood information and pre-computed functions based on vertex degrees. This allows for calculating the probability of sampling any specific graphlet without needing global network information.
- Unbiased Estimators: The paper proposes three variants of the Lifting estimator:
- Unordered Lift: Samples connected induced subgraphs (CISs) and classifies their type.
- Ordered Lift: Tracks the order in which vertices are added, providing an estimator for ordered sequences.
- Shotgun Lift: A more efficient variant that samples multiple graphlets in a single "shot" by exploring the neighborhood of a partially formed graphlet. This significantly boosts sampling efficiency.
- Theoretical Guarantees: The authors provide theoretical proofs that their estimators are unbiased and offer bounds on their variance, showing it scales with the maximum degree of the graph.
Datasets
The experiments were conducted on five real-world networks of varying sizes and densities:
- CELE (bio-celegansneural): A metabolic network of C. elegans.
- EMAIL (ia-email-univ): A university email exchange network.
- CAIDA (misc-as-caida): A network of Internet Service Provider routing relationships.
- FULLB (misc-fullb): A large positive definite matrix from a finite-element method.
- SOCFB (socfb-B-anon): A network of user friendships on Facebook.
These datasets range from hundreds of vertices to millions, allowing for evaluation on different scales.
Key Insights and Ideas
- Unified Sampling: Lifting is the first method that can simultaneously sample all graphlet types of a given size, unlike previous methods that might be tailored to specific graphlets.
- Local Information is Sufficient: The core innovation is that graphlet probabilities can be computed using only local neighborhood queries, making it highly scalable for massive, distributed networks.
- Shotgun Sampling Efficiency: The "shotgun" variant demonstrates a clever way to get more sampling "bang for your buck" by exploring multiple graphlet possibilities from a single lifting step, leading to faster convergence.
- Inherited Mixing Properties: Lifting inherits the mixing properties of the underlying vertex random walk, which is generally much faster than the mixing of subgraph random walks used in other methods. This leads to less correlated samples and faster convergence.
Key Results
- Competitive Performance: Lifting demonstrated competitive or superior performance compared to state-of-the-art methods like Waddling and Pairwise Subgraph Random Walk (PSRW) across various graphlets and networks.
- Accuracy on Rare Graphlets: Lifting showed a particular advantage in detecting rare graphlets, especially in sparse networks, where other methods struggled.
- Scalability: The method was successfully implemented and tested on a 2.9 million vertex Facebook graph for 6-graphlets, demonstrating its ability to scale to large networks and complex graphlets (k > 5) without specialized modifications.
- Faster Convergence with Shotgun: The shotgun variant of Lifting showed faster convergence rates than Waddling for smaller graphlets (k=3).
- Theoretical Guarantees: The paper provides theoretical backing for the unbiasedness of the estimators and bounds on their variance, which are comparable to existing methods.
Limitations and Future Work
- Exact Counting is Faster (for small k): The paper acknowledges that for small graphlets (k < 6), exact counting methods like ESCAPE and PGD are faster, but they do not scale to larger graphlets or networks.
- Shotgun Sample Dependence: While shotgun sampling is efficient, the samples within a single "shot" are dependent, which is not fully captured by the current theoretical variance bounds.
- Future Work: The authors suggest exploring the impact of different base vertex distributions (e.g., uniform vs. stationary distribution) on variance and further investigating the theoretical properties of the shotgun estimator. They also highlight that Lifting's ability to handle large graphlets without modification is a significant advantage for future research.
Summary updated