Sampling Graphlets of Multi-layer Networks: A Restricted Random Walk Approach

Simiao Jiao, Zihui Xue, Xiaowei Chen, Yuedong XuarXiv 2020 · arXiv

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.

The sixteen non-isomorphic 3-node graphlets in a two-layer network.

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.

Illustration of two-layer graphlets and their projection into a single-layer representation.

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

Abstract

Graphlets are induced subgraph patterns that are crucial to the understanding of the structure and function of a large network. A lot of efforts have been devoted to calculating graphlet statistics where random walk based approaches are commonly used to access restricted graphs through the available application programming interfaces (APIs). However, most of them merely consider individual networks while overlooking the strong coupling between different networks. In this paper, we estimate the graphlet concentration in multi-layer networks with real-world applications. An inter-layer edge connects two nodes in different layers if they belong to the same person. The access to a multi-layer network is restrictive in the sense that the upper layer allows random walk sampling, whereas the nodes of lower layers can be accessed only though the inter-layer edges and only support random node or edge sampling. To cope with this new challenge, we define a suit of two-layer graphlets and propose a novel random walk sampling algorithm to estimate the proportion of all the 3-node graphlets. An analytical bound on the sampling steps is proved to guarantee the convergence of our unbiased estimator. We further generalize our algorithm to explore the tradeoff between the estimated accuracies of different graphlets when the sample size is split on different layers. Experimental evaluation on real-world and synthetic multi-layer networks demonstrate the accuracy and high efficiency of our unbiased estimators.
BibTeX
@misc{jiao2020sampling,
  author = {Simiao Jiao and Zihui Xue and Xiaowei Chen and Yuedong Xu},
  title = {{Sampling Graphlets of Multi-layer Networks: A Restricted Random Walk Approach}},
  year = {2020},
  eprint = {2001.07136},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.07136},
}
Figure