Source-linked AI summary
Meta-Path Guided Embedding for Similarity Search in Large-Scale Heterogeneous Information Networks
Jingbo Shang, Meng Qu, Jialu Liu, Lance M. Kaplan, Jiawei Han, Jian Peng
TL;DR
Similarity search in large heterogeneous information networks needs to capture rich structural semantics while reflecting user-preferred meanings. ESim learns low-dimensional vertex embeddings guided by user-defined meta-paths and uses sampling-based parallel optimization for scale. Experiments on two real-world large-scale HINs show improved effectiveness over previous state-of-the-art methods and scalability.
Problem
Existing HIN similarity-search methods do not fully explore rich network-embedded semantics or incorporate users’ preferred similarity guidance.
Method
ESim learns low-dimensional vertex embeddings from HIN structures under user-defined meta-path guidance, using sampling-based parallel optimization for large-scale networks.
Results
ESim outperforms previous state-of-the-art algorithms on two real-world large-scale HINs and demonstrates scalability.
Takeaways & Limitations
Meta-path-guided embeddings provide an effective framework for similarity search among same-type vertices in large HINs.
Takeaways & Limitations
Automatically learning weighted combinations of meta-paths from user preferences remains future work, while this study uses grid search assuming ground truth.
Abstract
from arXiv · showhide
Most real-world data can be modeled as heterogeneous information networks (HINs) consisting of vertices of multiple types and their relationships. Search for similar vertices of the same type in large HINs, such as bibliographic networks and business-review networks, is a fundamental problem with broad applications. Although similarity search in HINs has been studied previously, most existing approaches neither explore rich semantic information embedded in the network structures nor take user's preference as a guidance. In this paper, we re-examine similarity search in HINs and propose a novel embedding-based framework. It models vertices as low-dimensional vectors to explore network structure-embedded similarity. To accommodate user preferences at defining similarity semantics, our proposed framework, ESim, accepts user-defined meta-paths as guidance to learn vertex vectors in a user-preferred embedding space. Moreover, an efficient and parallel sampling-based optimization algorithm has been developed to learn embeddings in large-scale HINs. Extensive experiments on real-world large-scale HINs demonstrate a significant improvement on the effectiveness of ESim over several state-of-the-art algorithms as well as its scalability.
1. INTRODUCTION
Similarity search in heterogeneous information networks must capture both rich network semantics and users’ preferred similarity meanings. ESim addresses these needs by learning embeddings guided by user-specified meta-paths and scaling through sampling and parallel optimization.
- 1. INTRODUCTION: User-specified meta-paths guide ESim toward similarity semantics preferred for a particular search task.Different users may emphasize different relations, such as shared technical terms or publication venues.
- 1. INTRODUCTION: Existing PathSim searches along specified meta-path instances but does not efficiently capture deeper semantic similarity embedded in the HIN structure.For example, authors publishing in different but semantically similar venues can receive zero PathSim similarity.
- 1. INTRODUCTION: Projection-based HIN embedding methods can lose underlying semantics and incur high costs when constructing projected networks.Directly modeling the original heterogeneous network is presented as a richer alternative.
- 1. INTRODUCTION: ESim proposes a general embedding-based similarity-search framework for heterogeneous information networks with varied vertex and edge types.The framework supports undirected, directed, weighted, and unweighted edges.
- 1. INTRODUCTION: A novel sampling method and parallel optimization framework make ESim suitable for large-scale HINs.These components are listed as contributions supporting efficient handling of large networks.
2. RELATED WORK
Prior work includes meta-path-based similarity measures, homogeneous-network embeddings, and heterogeneous-network embedding methods. These approaches motivate embedding-based similarity search while highlighting the need to preserve HIN semantics and fit models to intended uses.
- 2. RELATED WORK: PathSim defines same-type vertex similarity through normalized counts of path instances following a user-specified meta-path.It is presented as capturing peer-similarity semantics better than certain random-walk-based measures.
- 2. RELATED WORK: LINE and DeepWalk learn low-dimensional representations in homogeneous networks by preserving network proximity or using network links.These methods treat vertices as belonging to the same type.
- 2. RELATED WORK: HIN embedding research has also incorporated multimodal content, supervised labels, knowledge-graph relations, and other heterogeneous information.The cited approaches target tasks including predictive word embeddings, question answering, and retaining entity relations.
- 2. RELATED WORK: Embedding and similarity-search models must be revised to fit the desired usage and model setting.The related work discussion emphasizes that an appropriate model depends on the intended application.
- 2. RELATED WORK: The paper uses cosine similarity over vertex embeddings and existing efficient top-k nearest-neighbor techniques for online queries.This connects learned vector representations with practical similarity-search serving.
3. PRELIMINARIES
The preliminaries define heterogeneous information networks, meta-paths, path instances, and meta-path-guided similarity search. Bibliographic examples show how these concepts encode relations such as co-authorship and shared venues.
- 3. PRELIMINARIES: A heterogeneous information network contains typed vertices and typed edges, with edges represented as ordered triples of two vertices and an edge type.The definition supports multiple edge types between vertices and directed or undirected edges.
- 3. PRELIMINARIES: A meta-path is a compatible sequence of edge types whose adjacent vertex types match, and any contiguous subsequence forms a sub-meta-path.An individual edge type is a length-1 meta-path.
- 3. PRELIMINARIES: A path instance is an edge sequence that follows the edge types and vertex-type transitions specified by a meta-path.The formal definition requires each edge to have the corresponding type and connect the required successive vertices.
- 3. PRELIMINARIES: In a bibliographic network, A−P−A represents co-authorship, while A−P−V−P−A captures authors connected through shared venues.Concrete examples include two authors collaborating on a paper and authors publishing in the same venue.
- 3. PRELIMINARIES: Meta-path-guided similarity search uses user-specified meta-paths to determine the semantic meaning of similarity between same-type vertices.Users may jointly select paths such as A−P−V−P−A and A−P−A when searching for similar authors.
- 3. PRELIMINARIES: The discussion focuses on a single meta-path because the principal ideas extend to weighted combinations and optimal combinations showed limited additional gains in experiments.Learning weighted combinations from high-level user guidance is left for future work.
4. METHODOLOGY
ESim learns vertex embeddings that preserve HIN structure while incorporating user-specified meta-path semantics. It trains these embeddings from sampled path instances using probabilistic objectives and supports efficient similarity search with cosine similarity.
- Model Formulation: ESim models HIN structure by learning embeddings in which vertices co-occurring in many meta-path instances receive similar representations.The model defines a meta-path-conditioned relevance score using vertex embeddings and meta-path-specific parameters.
- Model Formulation: The meta-path-conditioned score combines a global bias, meta-path-specific shifts, and vertex embeddings to represent semantic relevance.The shifts modify the embeddings according to the meta-path semantics, while the global bias adjusts the score range.
- Model Formulation: ESim offers sequential and pairwise path-instance objectives, with the pairwise formulation modeling relevance among all vertices in a path instance.The paper later reports that pairwise is more effective because it exploits meta-path guidance more thoroughly.
- Optimization: Noise-contrastive estimation converts training into binary discrimination between observed meta-path instances and samples from a noise distribution.This avoids the cost of computing likelihood gradients linear in the number of vertices.
- Optimization: The training framework samples positive and negative path instances, optimizes their labels, and returns vertex embeddings after convergence.Sampling follows a user-specified meta-path and uses a negative sampling ratio K.
- Similarity Search: Online similarity is computed with cosine similarity, enabling approximate nearest-neighbor search after vector normalization.The method chooses cosine similarity because vector norms do not help the similarity-search task.
5. EXPERIMENTS
Experiments on DBLP and Yelp evaluate ESim against established similarity-search and embedding baselines using quantitative, qualitative, sensitivity, and efficiency analyses. ESim-pair benefits from appropriate user-selected meta-paths, produces stronger embeddings, and scales linearly with network size.
- AUC Evaluations: Meta-path choice materially affects performance: shared venues work best for DBLP Research Area, co-authorship for Research Groups, and review words for Yelp groupings.The experiments associate each grouping with a preferred similarity semantics reflected by its strongest meta-path.
- AUC Evaluations: ESim-pair performs best with significant advantages over PathSim and PTE, while reasonable meta-path guidance makes user-guided models outperform LINE.The reported comparisons cover DBLP and Yelp settings with dataset-appropriate meta-paths.
- Visualizations: ESim-pair yields the clearest DBLP Research Area embedding visualization, using A−P−V−P−A, and beats PTE and LINE-1st on Research Group visualization using A−P−A.The visual comparisons use variants selected for best AUC performance and project embeddings into two dimensions with t-SNE.
- Parameter Sensitivity: Embedding dimension 50 is selected in the reported parameter-sensitivity analysis for ESim-pair.The supplied sensitivity passage states the observed setting but does not include the complete curve or accompanying values.
- Efficiency: ESim-pair running time is linear in network size, while longer meta-paths incur slightly more time.The efficiency study varies network size on DBLP and Yelp and reports consistency with the theoretical time-complexity analysis.
6. CONCLUSIONS
ESim is an embedding-based similarity-search framework for HINs that combines meta-paths with network structure to learn vertex representations. It outperforms prior methods on two large-scale HINs, while its efficiency is shown to be scalable; the paper identifies several extensions for future work.
- ESim learns vertex embeddings from given meta-paths and HIN structure, using cosine similarity between same-type vertex embeddings.
- ESim outperforms previous state-of-the-art algorithms on two real-world large-scale HINs.
- The paper reports that ESim is scalable in efficiency and suggests extending similarity to different vertex types and automatically learning meta-paths or their weighted combinations.