Source-linked AI summary
MetaGraph2Vec: Complex Semantic Path Augmented Heterogeneous Network Embedding
Daokun Zhang, Jie Yin, Xingquan Zhu, Chengqi Zhang
TL;DR
Heterogeneous networks and sparse links make it difficult for conventional embeddings and strict metapath-based methods to capture relationships between distant nodes. MetaGraph2Vec guides random walks with metagraphs and learns embeddings for multiple node types; the paper reports better performance than state-of-the-art baselines across several mining tasks.
Problem
Conventional network embedding does not handle HINs’ multiple node and relation types, while sparse connections and missing links limit metapath-based capture of distant-node semantics.
Source: §1 · p. 2Method
MetaGraph2Vec uses metagraph-guided random walks to generate heterogeneous neighborhoods and learns embeddings for multiple node types.
Source: §1 · pp. 3–4Results
The paper reports that MetaGraph2Vec outperforms state-of-the-art baselines across node classification, node clustering, and similarity search.
Source: §1 · p. 4Takeaways & Limitations
Metagraph-guided walks provide richer structural contexts and semantic relations between distant nodes in HINs.
Source: §1 · p. 3, §5 · p. 11The authors identify automatic metagraph learning and evaluation on biological and social HINs as future work.
Source: §5 · p. 11
Abstract
from arXiv · showhide
Network embedding in heterogeneous information networks (HINs) is a challenging task, due to complications of different node types and rich relationships between nodes. As a result, conventional network embedding techniques cannot work on such HINs. Recently, metapath-based approaches have been proposed to characterize relationships in HINs, but they are ineffective in capturing rich contexts and semantics between nodes for embedding learning, mainly because (1) metapath is a rather strict single path node-node relationship descriptor, which is unable to accommodate variance in relationships, and (2) only a small portion of paths can match the metapath, resulting in sparse context information for embedding learning. In this paper, we advocate a new metagraph concept to capture richer structural contexts and semantics between distant nodes. A metagraph contains multiple paths between nodes, each describing one type of relationships, so the augmentation of multiple metapaths provides an effective way to capture rich contexts and semantic relations between nodes. This greatly boosts the ability of metapath-based embedding techniques in handling very sparse HINs. We propose a new embedding learning algorithm, namely MetaGraph2Vec, which uses metagraph to guide the generation of random walks and to learn latent embeddings of multi-typed HIN nodes. Experimental results show that MetaGraph2Vec is able to outperform the state-of-the-art baselines in various heterogeneous network mining tasks such as node classification, node clustering, and similarity search.
1 Introduction
MetaGraph2Vec uses metagraph-guided walks to represent richer semantic relationships between distant nodes in heterogeneous networks, addressing sparse contexts and the limits of metapath-based methods.
1 Introduction
- HINs combine multiple node and relation types, while conventional embedding methods assume homogeneous networks and cannot handle that heterogeneity.Source: §1 · pp. 1–2
- Metapaths guide random walks to preserve semantic similarity, but sparse connections and missing links can leave short walks that miss relationships between distant nodes.For example, missing paper–venue links can prevent metapath-based walks from capturing latent author similarity.Source: §1 · p. 2
- MetaGraph2Vec uses a metagraph to guide walks, combining multiple relationship paths and allowing more flexible matching than a single metapath.The illustrated walk from a1 to a4 cannot be generated using metapaths P1 and P2.Source: §1 · p. 3, Figure 2 · p. 3
- The method generates heterogeneous neighborhoods, generalizes Skip-Gram to multiple node types, and uses heterogeneous negative sampling to predict neighborhoods.Source: §1 · p. 4
- The paper reports that MetaGraph2Vec outperforms state-of-the-art methods on node classification, node clustering, and similarity search.Source: §1 · p. 4
2 Preliminaries and Problem Definition
This section defines heterogeneous information networks and embeddings, then formalizes metagraph structure and the random walks constrained by it.
2 Preliminaries and Problem Definition
- A heterogeneous information network is a directed graph whose nodes and edges have types, with a schema specifying the allowable node and link types.Source: §2 · p. 4
- Heterogeneous network embedding maps nodes into a low-dimensional Euclidean space so nodes with similar semantics have nearby representations.Source: §2 · p. 4
- A metagraph is a directed acyclic graph over the HIN schema with one source and one target, whose nodes and edges are occurrences of schema types.Source: §2 · p. 5
- Metagraph nodes are organized into topological layers, each containing distinct node types; a type may occur in multiple layers.Source: §2 · p. 5
- The recursive metagraph is formed by tail-head concatenation of copies of a metagraph, enabling its constraints to extend across walk steps.Source: §2 · p. 5
- A metagraph-constrained walk follows HIN edges while advancing through the recursive metagraph from a node of the designated source type.The example walk captures successive same-venue and shared-coauthor relations.Source: §2 · pp. 5–6
3 Methodology
MetaGraph2Vec uses metagraph-guided walks to generate heterogeneous neighborhoods, then learns node embeddings from their context pairs. Its methodology combines constrained walk transitions with context-prediction models and negative sampling.
3.1 MetaGraph Guided Random Walk
- Given a domain-specified metagraph, walks start at source-type nodes and allow only network edges consistent with the recursive metagraph.Transitions that fail either the network-edge or metagraph constraint have probability zero.Source: §3.1 · p. 6
- At each step, the walk randomly selects a qualified edge type, then a neighbor of that type; it terminates when none qualify.The transition probability accounts for the number of qualified edge types and same-type forward neighbors.Source: §3.1 · p. 6
3.2 MetaGraph2Vec Embedding Learning
- Walks supply w-window node-context pairs; MetaGraph2Vec counts each pair's frequency and learns embeddings by maximizing context-occurrence probability.The algorithm samples context pairs according to their frequency and uses stochastic gradient descent to update parameters.Source: §3.2 · pp. 6–7
- Two context models are offered: homogeneous Skip-Gram ignores context-node type, while heterogeneous Skip-Gram makes its probability depend on that type.Source: §3.2 · p. 7
- Negative sampling approximates the objective; negatives come from all nodes for homogeneous Skip-Gram or the target context node's type for heterogeneous Skip-Gram.The method uses the sigmoid function for the negative-sampling objective.Source: §3.2 · p. 7
4 Experiments
Experiments evaluate author embeddings on DBLP through classification, clustering, and similarity search. MetaGraph2Vec variants lead the reported comparisons, while parameter sensitivity varies by parameter.
4.1 Experimental Settings
- The DBLP experiments simulate paper–venue sparsity by removing venue links from one-fifth of papers and evaluate author embeddings across three mining tasks.The dataset includes papers, authors, venues, and their relationships; the tasks are classification, clustering, and similarity search.Source: §4 · p. 7, §4.1 · p. 8
4.2 Node Classification Results
- MetaGraph2Vec and MetaGraph2Vec++ achieve the best author-classification accuracy in all tested cases.The comparison varies training-data ratios from 1% to 9%.Source: §4.2 · p. 9, Table 1 · p. 9
4.3 Node Clustering Results
- MetaGraph2Vec and MetaGraph2Vec++ yield the best author-clustering results on Accuracy, F score, and NMI.K-means uses the learned author embeddings, with author labels as ground truth.Source: §4.3 · p. 10, Table 2 · p. 10
4.4 Node Similarity Search
- MetaGraph2Vec and MetaGraph2Vec++ achieve the best author-search precisions at both precision@100 and precision@500.The experiment ranks similar authors by cosine similarity for 1,000 randomly selected authors.Source: §4.4 · p. 10, Table 3 · p. 11
4.5 Parameter Sensitivity
- At a 5% training ratio, increasing embedding dimension improves performance before it stabilizes, while random-walk count and window size have little effect.The parameters are γ, the number of metagraph-guided walks from each author; w, the context-pair window size; and d, embedding dimension.Source: §4.5 · p. 10, Figure 3 · p. 11
5 Conclusions and Future Work
The paper proposes metagraph-guided random walks and MetaGraph2Vec for embedding heterogeneous networks, particularly very sparse HINs. It identifies automatic metagraph learning and evaluation on other HIN types as future work.
5 Conclusions and Future Work
- Metagraph augments metapaths with a more flexible relationship descriptor for sparse HINs, where metapath-based approaches can be ineffective.The paper presents MetaGraph2Vec as an embedding method that captures richer contexts and semantics and reports that it outperforms the state of the art.Source: §5 · p. 11
- MetaGraph2Vec uses metagraph-guided random walks to capture rich contexts and semantics between different node types.The paper identifies this approach and the embedding algorithm as its two main contributions.Source: §5 · p. 11
- Future work includes efficient automatic metagraph learning, assessing individual metagraph contributions, and evaluation on biological and social HINs.The paper names these as directions for further study.Source: §5 · p. 11