HeteroSample: Meta-path Guided Sampling for Heterogeneous Graph Representation Learning

Ao Liu, Jing Chen, Ruiying Du, Cong Wu, Yebo Feng, Teng Li, Jian Feng Ma

Introduction

As the Internet of Things (IoT) expands, data is increasingly represented as heterogeneous graphs—complex networks where nodes (e.g., devices, sensors, users) and edges (e.g., interactions, locations) possess distinct types and semantic meanings. Analyzing these graphs at scale presents a significant challenge for traditional Graph Neural Networks (GNNs) because the data volume often exceeds available memory.

Existing sampling techniques typically face two major limitations. Random walk-based methods are effective at capturing local neighborhoods but often fail to preserve the global structural integrity of the graph. Conversely, node-wise sampling methods, which select nodes based on simple importance metrics, frequently overlook the complex, multi-hop semantic relationships—known as meta-paths—that define the underlying data logic (e.g., Movie-Actor-Movie).

Overview of heterogeneous graph components and meta-paths

The HETEROSAMPLE Framework

To address these gaps, we propose HETEROSAMPLE, a deterministic sampling framework designed to create representative subgraphs that preserve both structural and semantic richness. The framework operates in three distinct stages:

  1. Top-Leader Selection: Instead of stochastic selection, the algorithm identifies influential "leaders" for every node type. It calculates a weighted importance score based on a node's degree and the inherent significance of its type, ensuring the initial sample contains a representative core of the original network.
  2. Balanced and Guided Expansion: The framework employs Balanced Neighborhood Expansion (BNE) to maintain the original distribution of node types, preventing bias toward dominant entities. Simultaneously, Meta-path Guided Neighborhood Expansion (MGNE) prioritizes neighbors that complete critical local semantic patterns.
  3. Meta-path Guided Global Sampling: To capture long-range dependencies, HETEROSAMPLE performs guided walks along predefined meta-paths. By prioritizing paths with higher importance weights, the algorithm ensures that semantically relevant multi-hop connections are preserved in the final subgraph.
The HETEROSAMPLE framework architecture

Experimental Evaluation

We evaluated HETEROSAMPLE on three standard benchmarks: DBLP (bibliographic), ACM (citation), and IMDB (movie database). The method was compared against state-of-the-art baselines, including HGSampling and HetGNN.

Key Results

  • Performance Gains: HETEROSAMPLE achieved up to a 15% increase in F1 scores across downstream tasks such as link prediction and node classification.
  • Efficiency: The deterministic nature of the algorithm reduced total training runtime by approximately 20% compared to stochastic methods.
  • Structural Fidelity: The framework consistently yielded the lowest scores in Node Type Distribution Similarity (NTDS) and Edge Type Distribution Similarity (ETDS), indicating that the sampled subgraphs are mathematically highly representative of the original global structures.

Conclusion

HETEROSAMPLE demonstrates that preserving the specific distribution of node and edge types is as critical as connection density for effective graph representation learning. By utilizing meta-paths as a guide for deterministic sampling, the framework maintains the "semantic soul" of the graph while significantly reducing computational overhead. Future work will focus on extending this approach to dynamic IoT data streams and distributed implementations for even larger-scale networks.

Summary updated

Abstract

The rapid expansion of Internet of Things (IoT) has resulted in vast, heterogeneous graphs that capture complex interactions among devices, sensors, and systems. Efficient analysis of these graphs is critical for deriving insights in IoT scenarios, such as smart cities, industrial IoT, and intelligent transportation systems. However, the scale and diversity of IoT-generated data present significant challenges, and existing methods often struggle with preserving the structural integrity and semantic richness of these complex graphs. Many current approaches fail to maintain the balance between computational efficiency and the quality of the insights generated, leading to potential loss of critical information necessary for accurate decision-making in IoT applications. We introduce HeteroSample, a novel sampling method designed to address these challenges by preserving the structural integrity, node and edge type distributions, and semantic patterns of IoT-related graphs. HeteroSample works by incorporating the novel top-leader selection, balanced neighborhood expansion, and meta-path guided sampling strategies. The key idea is to leverage the inherent heterogeneous structure and semantic relationships encoded by meta-paths to guide the sampling process. This approach ensures that the resulting subgraphs are representative of the original data while significantly reducing computational overhead. Extensive experiments demonstrate that HeteroSample outperforms state-of-the-art methods, achieving up to 15% higher F1 scores in tasks, such as link prediction and node classification, while reducing runtime by 20%. These advantages make HeteroSample a transformative tool for scalable and accurate IoT applications, enabling more effective and efficient analysis of complex IoT systems, ultimately driving advancements in smart cities, industrial IoT, and beyond.
BibTeX
@article{liu2025heterosample,
  author = {Ao Liu and Jing Chen and Ruiying Du and Cong Wu and Yebo Feng and Teng Li and Jian Feng Ma},
  title = {{HeteroSample: Meta-path Guided Sampling for Heterogeneous Graph Representation Learning}},
  journal = {IEEE Internet of Things Journal},
  year = {2025},
  doi = {10.1109/jiot.2024.3484996},
}
Figure