Source-linked AI summary
HeteSpaceyWalk: A Heterogeneous Spacey Random Walk for Heterogeneous Information Network Embedding
Yu He, Yangqiu Song, Jianxin Li, Cheng Ji, Jian Peng, Hao Peng
TL;DR
Prior meta-path-guided HIN embedding methods give little attention to the higher-order Markov nature of their walks and their stationary distributions. The paper introduces HeteSpaceyWalk and embedding frameworks for meta-paths, meta-graphs, and meta-schemas; experiments report improved performance with smaller walk-times and walk-lengths.
Problem
Prior meta-path-guided HIN embedding methods pay little attention to the higher-order Markov nature of their walks, especially their limiting stationary distributions.
Source: §1 · p. 1Method
HeteSpaceyWalk uses a personalized spacey random walk, extended through scalable embedding frameworks guided by meta-paths, meta-graphs, or meta-schemas.
Source: §1 · p. 2Results
Experiments report better performance with smaller walk-times and walk-lengths, and considerable outperformance on node classification and link prediction across four heterogeneous networks.
Source: §1 · p. 2, §6 · p. 10Takeaways & Limitations
The framework supports embedding multiple node types using an arbitrary user-given meta-path, a meta-graph, or a general meta-schema without handcrafted meta-paths.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Heterogeneous information network (HIN) embedding has gained increasing interests recently. However, the current way of random-walk based HIN embedding methods have paid few attention to the higher-order Markov chain nature of meta-path guided random walks, especially to the stationarity issue. In this paper, we systematically formalize the meta-path guided random walk as a higher-order Markov chain process, and present a heterogeneous personalized spacey random walk to efficiently and effectively attain the expected stationary distribution among nodes. Then we propose a generalized scalable framework to leverage the heterogeneous personalized spacey random walk to learn embeddings for multiple types of nodes in an HIN guided by a meta-path, a meta-graph, and a meta-schema respectively. We conduct extensive experiments in several heterogeneous networks and demonstrate that our methods substantially outperform the existing state-of-the-art network embedding algorithms.
1 INTRODUCTION
Meta-path-guided walks are higher-order Markov processes, but prior embedding methods give little attention to their stationary distributions and to balancing or designing meta-paths. The paper introduces HeteSpaceyWalk and scalable embedding frameworks for meta-paths, meta-graphs, and meta-schemas, and reports better performance across heterogeneous networks and mining tasks.
1 INTRODUCTION
- Existing meta-path-guided walks are higher-order Markov processes, yet prior methods pay little attention to their limiting stationary distributions.For APVPA, the next transition from a Paper node depends on whether the preceding node was an Author or Venue.Source: §1 · p. 1
- HeteSpaceyWalk uses a personalized spacey strategy to skip trivial transitions while preserving the original walk’s unique limiting stationary distribution.It folds a user-given meta-path into multiple paths and dynamically adjusts their probabilities during the walk.Source: §1 · p. 2
- SpaceyMetapath, SpaceyMetagraph, and SpaceyMetaschema extend the approach to user-given meta-paths, meta-graphs, and general meta-schemas.The meta-schema framework does not require handcrafted meta-paths.Source: §1 · p. 2
- Experiments in four heterogeneous networks report that the methods considerably outperform homogeneous and heterogeneous embedding baselines on node classification and link prediction.The compared heterogeneous methods are guided by meta-paths or meta-graphs.Source: §1 · p. 2
2 PROBLEM DEFINITION
The section defines heterogeneous networks and schema-level structures used to represent their types and relationships. It then defines embedding as mapping network nodes to low-dimensional vectors that capture structure and semantics.
2 PROBLEM DEFINITION
- A heterogeneous information network has multiple entity types or multiple relation types.It is represented as a directed graph with mappings from nodes and edges to their respective types.Source: §2 · p. 2
- A meta-schema is a graph whose nodes are entity types and whose edges are relation types.It provides a high-level description of an HIN.Source: §2 · p. 2
- A meta-path is a schema-level type sequence defining a composite relation, while a meta-graph integrates multiple meta-paths to capture complex semantics.A meta-graph is a directed acyclic graph on the HIN schema, generally with one source and one target entity type.Source: §2 · p. 2
- HIN embedding maps each node to a low-dimensional vector intended to capture the structure and semantics of multiple node and relationship types.The embedding dimension is much smaller than the number of network nodes.Source: §2 · p. 3
3 HETEROGENEOUS SPACEY RANDOM WALK BASED EMBEDDINGS
This section develops HIN embedding frameworks that use heterogeneous spacey random walks under meta-path, meta-graph, or meta-schema guidance. The approach formalizes meta-path walks as higher-order Markov chains and uses spacey strategies to address walk efficiency, stationarity, and guidance choices.
3 HETEROGENEOUS SPACEY RANDOM WALK BASED EMBEDDINGS
- Meta-path, meta-graph, and meta-schema guidance each support a framework for learning embeddings of heterogeneous nodes.The frameworks generate walks and use Skipgram to learn embeddings.Source: §3 · p. 3, §3.1.4 · p. 5, §3.2 · p. 5
3.1.1 Background of Random Walk over HIN.
- Meta-path walks use type-to-type transition probabilities, while the long-run behavior of meta-path-constrained walks is governed by their stationary distribution.The paper notes that earlier random-walk embedding methods paid little attention to the higher-order Markov property and limiting stationary distribution.Source: §3.1.1 · p. 3
3.1.2 Higher-order Markov Chains.
- The meta-path APVPA defines a second-order Markov chain because the last two node types determine the next type.Repeated intermediate transitions can be trivial, motivating probabilistic skips along folded subpaths.Source: §3.1.2 · p. 3
3.1.3 Heterogeneous Personalized Spacey Random Walk.
- HeteSpaceyWalk skips intermediate transitions using past-state history, and its limiting distribution matches the original walk’s stationary solution under the rank-one approximation condition.The personalized walk is described as an efficient alternative that does not change limiting stationarity.Source: §3.1.3 · pp. 4–5
3.1.4 Spacey Random Walk based Embedding.
- SpaceyMetapath generates heterogeneous neighborhoods with HeteSpaceyWalk and feeds them to Skipgram to learn node embeddings.The Skipgram objective models context nodes around each central node in generated paths.Source: §3.1.4 · p. 5
3.2 Meta-graph based HIN Embedding
- SpaceyMetagraph extends the spacey strategy to balance branch choices while integrating multiple meta-paths, then uses generated neighborhoods with Skipgram.The meta-graph walk uses personalized occupation probabilities to guide branch choices.Source: §3.2 · p. 5
3.3 Meta-schema based HIN Embedding
- SpaceyMetaschema guides walks over a schema without duplicate types; its first-order walk dynamically chooses the next node type and then a node of that type.The method is a special case of the meta-graph approach with first-order Markov chains.Source: §3.3 · p. 6
4 EXPERIMENTS
Experiments evaluate the proposed embedding methods on four heterogeneous networks across node classification and link prediction, alongside parameter-sensitivity and scalability analyses.
4.1 Datasets
- The four evaluation networks are ACM, DBLP, Douban, and Yelp, each with multiple entity types and relations.Source: §4.1 · p. 6
4.2 Experimental Settings
- Experiments use common embedding and walk settings, α = 0.8 for proposed methods, and selected meta-paths or meta-graphs for guided baselines and variants.Source: §4.2 · pp. 6–7
4.3 Multi-label Node Classification
- Across all datasets and both F1 metrics, proposed algorithms beat baselines; on ACM author classification, gains span 0.01–0.10 Micro-F1 and 0.04–0.12 Macro-F1.Source: Table 1 · p. 7, Table 2 · p. 7, §4.3 · p. 7
4.4 Link Prediction
- Proposed methods outperform comparison methods on all datasets; on ACM, mean AUC gains are 0.05–0.25 over DeepWalk, LINE, and PTE and 0.01–0.21 over Metapath2vec and Metagraph2vec.Source: Table 4 · p. 8, §4.4 · p. 8
4.5 Parameter Sensitivity
- On ACM author classification, SpaceyMetapath with walk length 40 matches Metapath2vec at length 640, an approximately 16x speedup; performance gains from larger walk parameters taper.Source: §4.5 · p. 8, Figure 4 · p. 9
4.6 Complexity and Scalability Analysis
- On synthetic DBLP-schema graphs from 1k to 10,000k nodes, authors report linear time complexity in node count for neighborhood generation and embedding training.For the walk phase, the stated complexity is O(wl|A||V|); Skipgram training is also described as linear and parallelizable.Source: §4.6 · p. 9
5 RELATED WORK
Prior HIN embedding work spans factorization, relation-prediction models, and meta-path- or meta-graph-guided random walks. The proposed-model timing figure compares walk and training time across network sizes.
5 RELATED WORK
- Prior work on heterogeneous embedding includes methods cited as [40].Source: §5 · p. 9
- Figure 6 compares the proposed models’ walk and training time across different network sizes.Source: Figure 6 · p. 9
- Meta-path- and meta-graph-guided random-walk embedding methods use Skipgram, but earlier approaches paid little attention to the walks’ higher-order Markov-chain nature.The related-work discussion situates this paper’s focus on higher-order Markov chains within that line of work.Source: §5 · p. 9
- Matrix and tensor factorization can be costly in computation and memory, while TransE, PTE, and related approaches model binary-relation co-occurrences.Collective matrix factorization jointly factorizes relation matrices; TransE translates entities by relation vectors, and PTE learns from one-hop neighborhoods in edge-type bipartite networks.Source: §5 · p. 9
6 CONCLUSIONS
The paper proposes a heterogeneous personalized spacey random walk and scalable embedding algorithms guided by a meta-path, meta-graph, or meta-schema. Experiments report better performance with smaller walk times and walk lengths.
6 CONCLUSIONS
- The heterogeneous personalized spacey random walk generates heterogeneous neighborhoods and is presented as having a solid mathematical foundation.Source: §6 · p. 10
- SpaceyMetapath produces node embeddings guided by an arbitrary meta-path, and SpaceyMetagraph and SpaceyMetaschema extend the approach to meta-graphs and meta-schemas.Source: §6 · p. 10
- Experiments report that the methods achieve better performance with smaller walk times and walk lengths.Source: §6 · p. 10