Abstract
Graphlets are fundamental building blocks for understanding network topology. However, in real-world multi-layer networks—such as overlapping social media platforms—access to data is often restricted by limited APIs. This paper introduces a Restricted Random Walk (RRW) framework to estimate the frequency of 3-node graphlets in these coupled systems. By leveraging a "squished" graph representation and precomputed isomorphic state coefficients, the proposed approach provides unbiased estimators that achieve high accuracy even when one network layer is only partially observable.
Introduction
Graphlets, or small induced subgraphs, serve as motifs that reveal the structural characteristics of complex networks. While methods for counting graphlets in single-layer networks are well-established, real-world systems are increasingly multi-layered. For instance, individuals may interact across multiple social platforms simultaneously, creating inter-layer dependencies.
Analyzing these multi-layer networks presents two primary challenges: computational complexity and restricted data access. Researchers often lack the full graph and must rely on APIs that permit random walks on one "Upper Layer" while offering only limited "one-hop" queries on a "Lower Layer." This paper addresses the problem of obtaining unbiased graphlet estimates under such restricted conditions.
Multi-layer Graphlet Taxonomy
The authors define a comprehensive suite of sixteen 3-node two-layer graphlets. These represent all possible non-isomorphic configurations of nodes and edges across two coupled layers.
These graphlets capture the nuances of cross-platform interactions, such as a "friend of a friend" pattern that exists partially on one platform and partially on another.
Methodology: Restricted Random Walk
To estimate graphlet concentrations without full network access, the authors propose the Restricted Random Walk (RRW) approach. A key innovation is the concept of "squishing" a two-layer graphlet into a single-layer visualization where different colors represent different layers.
The framework includes several algorithmic variants:
- RWNbN (Node-by-node): The walker traverses nodes in the accessible layer and periodically queries the restricted layer for corresponding local structures.
- RWEbE (Edge-by-edge): The walker moves across edges, which is more effective for identifying dense graphlet structures.
- Budget-Aware Variants (RWOMRN & RWMix): These allow users to balance the "cost" of querying the restricted layer against the exploration of the accessible layer.
To ensure unbiased results, the authors precompute isomorphic state coefficients ($\alpha_i$). These coefficients correct for the varying probabilities of encountering different graphlet types during a random walk, allowing the final estimator to converge to the true distribution.
Experimental Evaluation
The algorithms were tested on synthetic networks (Erdos-Renyi, Small World, and Barabasi-Albert models) and "hybrid" real-world networks constructed from Epinions and Facebook datasets. The evaluation focused on the Mean Relative Error (MRE) and convergence speed.
Key Results
- High Precision: For graphlets with a concentration above $10^{-4}$, the MRE remained consistently below 0.04.
- Convergence: Estimators typically converged to ground truth within 20,000 sampling steps, confirming the mathematical proof of unbiasedness.
- Performance Parity: The restricted algorithms performed comparably to unrestricted baselines (RWNR), demonstrating that full access to both layers is not a prerequisite for accurate local structural analysis.
Conclusion
This research provides a robust framework for sampling graphlets in multi-layer networks under realistic data access constraints. By formalizing the Restricted Random Walk and the "squished" graphlet representation, the authors enable accurate network characterization even with limited API budgets. Future work will explore extending this framework to larger graphlets (4-node and 5-node) and dynamic, time-evolving networks.
Summary updated