Heterogeneous Information Network Embedding for Meta Path based Proximity

1. INTRODUCTION

• HIN proximity reflects relationship semantics as well as closeness, so two nearby objects can be related in meaningfully different ways.For example, an author may be close to both a coauthor and a venue, but through different relationships.Source: §1 · p. 1
• Earlier HIN embedding work did not target meta-path proximity in general HINs, despite meta-path measures outperforming traditional structured proximities in reported tasks.Meta-path proximity has been applied to tasks including k-NN search, link prediction, recommendation, classification, and clustering.Source: §1 · pp. 1–2
• HINE maps HIN objects into a low-dimensional space, with an objective that minimizes the distance between distributions of original and embedded proximities.The objective preserves relative proximity rankings; the method considers meta paths up to a length threshold.Source: §1 · p. 2
• Across four real HINs, HINE outperforms state-of-the-art methods in most qualitative measures and data-mining tasks including classification, clustering, and visualization.The comparisons include LINE and DeepWalk, which do not consider meta-path-based proximity.Source: §1 · p. 2
• The authors investigate negative sampling to accelerate optimization.The introduction identifies it as an optimization technique for HINE.Source: §1 · p. 2

2.1 Heterogeneous Information Networks

• HIN research addresses authority propagation, collective classification, link-based clustering, link prediction, and entity recommendation.PathSelClus lets users express clustering preferences through seed examples.Source: §2.1 · p. 2

2.2 Meta Path and Proximity Measures

• Meta-path proximity measures include PathCount, its normalized version PathSim, PCRW, and HeteSim; this paper focuses on PathCount and PCRW.PathCount counts meta-path instances, while PCRW measures the probability of reaching an object through such an instance.Source: §2.2 · p. 2

2.3 Network Embedding

• Traditional dimensionality reduction and graph factorization do not necessarily preserve global network structure, while GraRep is costly on large networks.GraRep involves matrix powers and SVD; SDNE is also discussed, but its source code was unavailable for reproduction and comparison.Source: §2.3 · p. 2
• DeepWalk does not account for HIN heterogeneity and preserves only second-order proximity, whereas LINE separately learns first- and second-order vectors before concatenating them.The paper proposes embedding proximities of all orders simultaneously rather than separating the two orders.Source: §2.3 · p. 2
• HINE focuses on meta-path proximity and uses network structure and node and edge types, not other HIN information.The paper specifically notes that it does not consider other information in the HIN.Source: §2.3 · p. 3

3. PROBLEM DEFINITION

• A HIN is a directed graph whose objects and links have types, with a schema describing allowable links between object types.The formulation assumes each object has a single type, but the technique can be adapted to objects with multiple types.Source: §3 · p. 3
• A meta path is a sequence of object types joined by link types that models a particular relationship between objects.For example, the author–paper–venue–paper–author path represents authors connected through a shared venue.Source: §3 · p. 3
• PathCount counts instances of a meta path, while PCRW assigns an instance the probability that a random walk restricted to that path follows it.The paper also notes that its embedding technique can be adapted to PathSim, HeteSim, and BPCRW.Source: §3 · p. 3
• The proximity of two objects is the sum of their proximities over meta paths, allowing multiple kinds of relationships to contribute.Each path instance contributes a score defined by the selected proximity measure.Source: §3 · p. 3
• The embedding problem is to map every object in a HIN to a vector in R^d while preserving the proximities between object pairs.The section presents meta path-based proximity as the basis for this preservation objective.Source: §3 · p. 3

4.1 Truncated Proximity Calculation

• Truncated proximity considers only meta paths up to length l because longer paths are less informative and the number of possible paths can grow exponentially or become infinite.A dynamic-programming approach computes proximities successively by path length, with time complexity O(|V| · lD) for average degree D.Source: §4.1 · p. 4

4.2 Model

• The model defines embedded pair probabilities and minimizes the KL-divergence between them and the empirical pair-proximity distribution in the original HIN.The objective is intended to preserve meta path-based proximities.Source: §4.2 · p. 4

4.3 Negative Sampling

• HINE’s negative-sampling optimization addresses a trivial infinite-vector solution and the cost of summing over all nonzero proximity scores.It samples a small number of negative objects to enhance the influence of positive objects; the noise distribution is proportional to out-degree raised to 3/4.Source: §4.3 · pp. 4–5
• HINE uses asynchronous stochastic gradient descent, sampling object pairs with nonzero proximity to optimize its objective.For each sampled pair, the gradient with respect to the vector for the first object is calculated.Source: §4.3 · p. 5

5. EXPERIMENTS

• The evaluation covers network recovery, classification, clustering, k-NN search, visualization, a top-k case study, parameter l, and runtime.The paper states that it uses four real datasets.Source: §5 · p. 5, §5.1 · p. 5

5.1 Dataset and Configurations

• The datasets are DBLP, a bibliographic network; MOVIE, a movie network; YELP, a restaurant-review network; and GAME, a video-game network.The DBLP subset covers four research areas; the MOVIE and GAME data are restricted to specified genres, and YELP to selected restaurant types.Source: §5.1 · p. 5
• HINE_PC uses PathCount and HINE_PCRW uses PCRW; the competitors include DeepWalk and LINE, which are applied without accounting for HIN heterogeneity.Unless otherwise stated, the embedding dimension is 10 and HINE_PC uses l = 2.Source: §5.1 · p. 5

5.2 Network Recovery

• The network-recovery evaluation enumerates candidate object pairs for each link type and uses AUC against the real network as ground truth.The reported results use embedding dimension d = 10.Source: §5.2 · pp. 5–6
• HINE_PCRW has the best overall network-recovery performance, generally outperforming LINE and DeepWalk, and remains close to other methods when it loses.HINE_PCRW also outperforms HINE_PC; the authors relate this to random-walk proximity weighting nearby objects more than remote ones.Source: §5.2 · p. 6
• LINE_1st performs much better than LINE_2nd, and concatenating the two vectors gives LINE worse performance than LINE_1st.The authors report that the LINE_2nd component harms link-prediction accuracy.Source: §5.2 · p. 6

5.3 Classification

• HINE_PCRW performs best on DBLP and MOVIE, while LINE is slightly better on YELP and DeepWalk leads on GAME.LINE is about 1% better than HINE_PCRW on YELP; on GAME, LINE and HINE_PCRW perform similarly.Source: §5.3 · p. 6
• DeepWalk’s classification performance is unstable across datasets, while LINE performs well overall.Source: §5.3 · p. 6
• As embedding dimension increases on DBLP, all approaches improve initially and then converge; HINE_PCRW has the best overall classification performance.Source: §5.3 · p. 6

5.4 Clustering

• HINE_PCRW is reported to outperform the other methods overall in clustering, although dataset-specific leaders vary.DeepWalk and HINE perform better than LINE on DBLP; HINE performs best on MOVIE, LINE on YELP, and DeepWalk on GAME.Source: §5.4 · p. 6
• On DBLP, HINE_PCRW generally outperforms the other methods across embedding dimensions, except DeepWalk slightly leads at d = 10.Source: §5.4 · pp. 6–7

5.5 k-NN Search

• For DBLP k-NN search, HINE_PCRW finds authors with more WWW papers and produces a top-k list closer to the original HIN.Source: §5.5 · p. 7

5.6 Visualization

• HINE_PCRW gives the clearest DBLP author-group separation, leaving substantial empty space between clusters.HINE_PC also separates groups better than DeepWalk, while LINE leaves some blue points mixed with other groups.Source: §5.6 · p. 7

5.7 Case Study

• For Jiawei Han, HINE_PCRW ranks KDD and ICDM first and second among venues, favors top researchers, and returns the general topic “mining.”LINE fails to rank KDD among the top venues; DeepWalk places ICDM fifth.Source: §5.7 · p. 7

5.8 Effect of the l Threshold

• For DBLP classification, HINE_PCRW is stable across l and performs best at l = 2, while HINE_PC performs best at l = 1.PCRW assigns smaller weights to longer instances, whereas PathCount treats meta-path instances of different lengths equally; the authors say this explains HINE_PCRW’s advantage in these tasks.Source: §5.8 · pp. 7–8
• For DBLP clustering, HINE_PCRW outperforms HINE_PC when l > 1, but HINE_PC performs much better at l = 1.At l = 1, HINE_PCRW captures only very local proximities.Source: §5.8 · p. 8

5.9 Efficiency

• At l = 2, all-pair truncated proximity computation on DBLP takes less than 1000 seconds; ASGD takes an average of 27.48 seconds with d = 10.The authors report that the proximity algorithm scales well with l.Source: §5.9 · p. 8

• The objective minimizes the distance between distributions of meta-path proximities and proximities in the low-dimensional embedding.Source: §6 · p. 8
• Negative sampling is investigated as a way to accelerate optimization.Source: §6 · p. 8
• The embedding methods better recover the original network and perform better than state-of-the-art methods on classification, clustering, and visualization.Source: §6 · p. 8