{'fraction_non_alphanumeric': 0.03919933277731443, 'fraction_numerical': 0.007228245760355852, 'mean_word_length': 4.388568794653146, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
HeteSim: A General Framework for Relevance Measure in Heterogeneous Networks

Similarity search is an important function in many applications, which usually focuses on measuring the similarity between objects with the same type. However, in many scenarios, we need to measure the relatedness between objects with different types. With the surge of study on heterogeneous networks, the relevance measure on objects with different types becomes increasingly important. In this paper, we study the relevance search problem in heterogeneous networks, where the task is to measure the relatedness of heterogeneous objects (including objects with the same type or different types). A novel measure HeteSim is proposed, which has the following attributes: (1) a uniform measure: it can measure the relatedness of objects with the same or different types in a uniform framework; (2) a path-constrained measure: the relatedness of object pairs are defined based on the search path that connect two objects through following a sequence of node types; (3) a semi-metric measure: HeteSim has some good properties (e.g., self-maximum and symmetric), that are crucial to many data mining tasks. Moreover, we analyze the computation characteristics of HeteSim and propose the corresponding quick computation strategies. Empirical studies show that HeteSim can effectively and efficiently evaluate the relatedness of heterogeneous objects.


I. INTRODUCTION
Similarity search is an important task in a wide range of applications, such as web search [1] and product recommendations [2]. The key of similarity search is similarity measure, which evaluates the similarity of object pairs. Similarity measure has been extensively studied for traditional categorical and numerical data types, such as Jaccard coefficient and cosine similarity.
There are also a few studies on leveraging link information in networks to measure the node similarity, such as Personalized PageRank [3], SimRank [4], and PathSim [5]. Conventional study on similarity measure focuses on objects with same type. That is, the objects being measured are of the same type, such as "document-to-document", "webpage-to-webpage" and "user-to-user".
There is seldom research on similarity measure on objects with different types. That is, the objects being measured are of different types, such as "author-to-conference" and "user-to-movie". It is reasonable. The similarity of objects with different types is a little against our common sense.
Moreover, different from the similarity of objects with same type, which can be measured on homogeneous situation (e.g., the same feature space or homogeneous link structure), it is even hard to define the similarity of objects with different types.
However, the similarity of objects with different types is not only meaningful but also useful in some scenarios. For example, the author J. F. Naughton is more relevant to SIGMOD than KDD. A teenager may like the movie "Harry Potter" more than "The Shawshank Redemption".
Moreover, the similarity measure of objects with different types are needed in many applications.
For example, in a recommendation system, we need to know the relatedness between users and movies to make accurate recommendations. In an automatic profile extraction application, we need to measure the relatedness of objects with different types, such as authors and conferences, conferences and organizations etc. Particularly, with the advent of study on heterogeneous information networks [5], [6], it is not only increasingly important but also feasible to study the relatedness among objects with different types. Heterogeneous information networks are the logical networks involving multiple-typed objects and multiple-typed links denoting different relations [7]. For example, a bibliographic network includes authors, papers, conferences, terms and their links representing their relations. It is clear that heterogeneous information networks are ubiquitous and form a critical component of modern information infrastructure [7]. So it is essential to provide a relevance search function on objects with different types in such networks, typed objects and links are coexist in a network and they carry different semantic meanings.
As an bibliographic example shown in Fig. 2(b) (more details in Section V.A), it includes author, paper, term, and conference type. The relation "author-paper" means author writing paper, while the relation "paper-conference" means paper published in conference. If disregarding the difference of types and semantics, it does not make sense to mix different-typed objects to measure the similarity. We can find that search paths, connecting two objects through a sequence of relations between object types, embody rich semantic information [5]. Based on different search paths, the relatedness of two objects may be totally different. For example, the relatedness of authors and conferences should be different based on the "author-paper-conference" path and "author-paper-author-paper-conference" path, which mean the relations of authors publishing papers in conferences and their co-authors publishing papers in conferences, respectively. As a consequence, a desirable relevance measure should be path-dependent, since such a measure can capture the semantics under paths and return meaningful values based on different paths. (2) It is difficult to design a uniform and symmetric relevance measure for heterogeneous objects. In heterogeneous networks, the paths connecting objects with same type are usually symmetric and the path length is a even number, so it may be not difficult to design a symmetric measure based on the symmetric paths, as the PathSim [5] does. However, the paths connecting objects with different types are asymmetric and the path length may be an odd number. In this condition, it is not easy to design a symmetric relevance measure. It is more challengeable to design a uniform relevance measure for these two conditions.
Inspired by the intuition that two objects are related if they are referenced by related objects, we propose a general framework, called HeteSim, to evaluate the relatedness of heterogeneous objects in heterogeneous networks. HeteSim is a path-based relevance measure, which can May 22, 2014 DRAFT effectively capture the subtle semantics of search paths. Based on pair-wise random walk model, HeteSim treats arbitrary search paths in a uniform way, which guarantees the symmetric property of HeteSim. An additional benefit is that HeteSim can evaluate the relatedness of objects with same or different types in the same way. Moreover, HeteSim is a semi-metric measure. In other words, HeteSim satisfies the properties of non-negativity, identity of indiscernibles, and symmetry. It implies that HeteSim can be used in many learning tasks (e.g., clustering and collaborative filtering). We also consider the computation issue of HeteSim and propose four fast computation strategies. The extensive experiments validate the effectiveness of HeteSim.
As a general relevance measure, HeteSim illustrates its benefits and generality in knowledge discovery of heterogeneous networks through four case studies: automatically extracting object profile, experts finding through relative importance of object pairs, relevance search based on path semantics, and semantic-based movie recommendation. HeteSim also shows its potential in the machine learning tasks (i.e., query and clustering) where HeteSim outperforms other wellestablished similarity measures. In addition, numerous experiments test the significance of fast computing strategies of HeteSim.

II. RELATED WORK
The most related work to relevance search is similarity search. Here we briefly summarize these works. Similarity search has been well studied for a long time. These studies can be roughly categorized into two types: feature based approaches and link based approaches. The feature based approaches measure the similarity of objects based on their feature values, such as cosine similarity, Jaccard coefficient and Euclidean distance. The k nearest neighbor is also widely used in similarity measure [10], [11], which aims at finding top-k nearest neighbors according to similarities defined on numerical features. Based on feature similarity, the top-k similarity pair search algorithm (i.e., top-k-join) considers similarity between tuples [12]. This type of approaches does not consider link relation among objects, so they cannot be applied to networked data.
The link based approaches measure the similarity of objects based on their link structures in a graph. The asymmetrical similarity measure, Personalized PageRank [3], evaluates the probability starting from a source object to a target object by randomly walking with restart. It is extended to the scalable calculation for online queries [13], [14] and the top-k answers [15]. SimRank May 22, 2014 DRAFT [4] is a symmetric similarity measure, which evaluates the similarity of two objects by their neighbor's similarities. Because of its computational complexity, many follow-up studies are done to accelerate such calculations [16], [17]. SCAN [18] measures similarity of two objects by comparing their immediate neighbor sets. Recently, Jin et al. proposed RoleSim to measure the role similarity of node pair by automorphic equivalence [19]. These approaches just consider the objects with the same type, so they can not be applied in heterogeneous networks. ObjectRank [20] applies authority-based ranking to keyword search in labeled graphs and PopRank [21] proposes a domain-independent object-level link analysis model. Although these two approaches noticed that heterogeneous relationships could affect the similarity, they do not consider the distinct semantics of paths that include different-typed objects, so they also cannot measure the similarity of objects in heterogeneous networks.
Recently, the relevance research in heterogeneous data emerge. Wang et al. [22] proposed a model to learn relevance from heterogeneous data, while their model more focuses on analyzing the context of heterogeneous networks, rather than network structure. Based on a Markovchain model of random walk, Fouss et al. [23] designed a similarity metric ECTD with nice properties and interpretation. Unfortunately, absent of path constraint, ECTD cannot capture the subtle semantics in heterogeneous networks. Considering semantics in meta paths constituted by different-typed objects, Sun et al. [5] proposed PathSim to measure the similarity of sametyped objects based on symmetric paths. However, many valuable paths are asymmetric and the relatedness of different-typed objects are also meaningful. PathSim is not suitable in these conditions. In information retrieval community, Lao and Cohen [9], [24] proposed a Path Con-  Fig.2(a). It contains objects from seven types of entities: papers (P), authors (A), affiliations (F), terms (T), subjects (S), venues (V), and conferences (C) (a conference includes multiple venues, e.g., KDD including KDD2010, KDD2009 and so on). There are links connecting different-typed objects. The link types are defined by the relations between two object types. For example, links exist between authors and papers denoting the writing or written-by relations, between venues and papers denoting the publishing or published-in relations. Fig.2 between type A 1 and A l+1 , where • denotes the composition operator on relations. The length of the path P is the number of relations in P, which is l.
For simplicity, we can also use type names denoting the relevance path if there are no multiple relations between the same pair of types: P = (A 1 A 2 · · · A l+1 ). We say a concrete path p = (a 1 a 2 · · · a l+1 ) between a 1 and a l+1 in network G is a path instance of the relevance path P, if for each a i , φ(a i ) = A i and each link e i = a i , a i+1 belongs to the relation R i in P. It can be denoted as p ∈ P. A relevance path P −1 is the reverse path of P, which defines an inverse relation of the one defined by P. Similarly, we define the reverse path instance of p −1 as the reverse path of p in G. Further, a relevance path P is a symmetric path, if the relation R defined by it is symmetric (i.e., P is equal to P −1 ), such as AP A and AP CP A. Two relevance paths P 1 = (A 1 A 2 · · · A l ) and P 2 = (B 1 B 2 · · · B k ) are concatenable if and only if A l is equal to B 1 , and the concatenated path is written as P = (P 1 P 2 ), which equals to (A 1 A 2 · · · A l B 2 · · · B k ). A simple concatenable example is that AP and P V can be concatenated to the path AP V .

A. Basic Idea
In many domains, similar objects are more likely to be related to some other similar objects.
For example, similar researchers usually publish many similar papers; similar customers purchase similar commodities. As a consequence, two objects are similar if they are referenced by similar objects. This intuition is also fit for heterogeneous objects. For example, a researcher is more relevant to the conferences that the researcher has published papers in; and a customer is more faithful to the brands that the customer usually purchased. Although the similar idea has been applied in SimRank [4], it is limited to homogeneous networks. When we apply the idea to heterogeneous networks, it faces the following challenges. (1) The relatedness of heterogeneous objects is path-constrained. The relevance path not only captures the semantics information but also constrains the walk path. So we need to design a path-based similarity measure. (2) A uniform and symmetric measure should be designed for arbitrary paths. For a given path (symmetric or asymmetric), the measure can evaluate the relatedness of heterogeneous object pair (same or different types) with one single score. In the following section, we will illustrate these challenges and their solutions in detail.

B. Path-based Relevance Measure
Different from homogeneous networks, the paths in heterogeneous networks have semantics, which makes the relatedness of object pair depend on the given relevance path. Following the basic idea that similar objects are related to similar objects, we propose a path-based relevance measure: HeteSim. DEFINITION 3: HeteSim: Given a relevance path P = R 1 • R 2 • · · · • R l , the HeteSim score between two objects s and t (s ∈ R 1 .S and t ∈ R l .T ) is: where O(s|R 1 ) is the out-neighbors of s based on relation R 1 , and I(t|R l ) is the in-neighbors of t based on relation R l .
When s does not have any out-neighbors (i.e., O(s|R 1 ) = ∅) or t does not have any inneighbors (i.e., I(t|R l ) = ∅) following the path, we have no way to infer any relatedness between s and t in this case, so we define their relevance value to be 0. Particularly, we consider objects with same type to have self-relation (denoted as I relation) and each object only has self-relation with itself. It is obvious that an object is just similar to itself for I relation. So its relevance measure can be defined as follows: DEFINITION 4: HeteSim based on self-relation: HeteSim between two same-typed objects s and t based on the self-relation I is: where δ(s, t) = 1, if s and t are same, or else δ(s, t) = 0.
Equation (1) shows that the computation of HeteSim(s, t|P) needs to iterate over all pairs (O i (s|R 1 ), I j (t|R l )) of (s, t) along the path (s along the path and t against path), and sum up the relatedness of these pairs. Then, we normalize it by the total number of out-neighbors of s and in-neighbors of t. That is, the relatedness between s and t is the average relatedness between the out-neighbors of s and the in-neighbors of t. The process continues until s and t will meet along the path. Similar to SimRank [4], HeteSim is also based on pair wise random walk, while it considers the path constraint. As we know, SimRank measures how soon two random surfers are expected to meet at the same node [4]. By contrast, HeteSim(s, t|P) measures how likely s and t will meet at the same node when s follows along the path and t goes against the path.

C. Decomposition of Relevance Path
However, the source object s and the target object t may not meet along a given path P. For the similarity measure of same-typed objects, the relevance paths are usually even-length, even symmetric, so the source object and the target object will meet at the middle objects. However, for the relevance measure of different-typed objects, the relevance paths are usually odd-length.
In this condition, the source and target objects will never meet at the same objects. Taking the AP V C path as an example, authors along the path and conferences against the path will never meet in the same objects. So the original HeteSim is not suitable for odd-length relevance paths.
In order to solve this difficulty, a basic idea is to transform odd-length paths into even-length paths, and thus the source and target objects are always able to meet at the same objects. As a consequence, an arbitrary path can be decomposed as two equal-length paths.
When the length l of a relevance path P = (A 1 A 2 · · · A l+1 ) is even, the source objects (along the path) and the target objects (against the path) will meet in the middle type object M = A l 2 +1 on the middle position mid = l 2 + 1, so the relevance path P can be divided into two equal-length path P L and P R . That is, P = P L P R , where P L = A 1 A 2 · · · A mid−1 M and When the path length l is odd, the source objects and the target objects will meet at the relation Al+1 2 Al+1 2 +1 . For example, based on the APSPVC path, the source and target objects will meet at the SP relation after two steps. In order to let the source and target objects meet at same-typed objects, we can add a middle type object E between the atomic relation Al+1 and Al+1 2 +1 at the same time. Then the new path becomes P ′ = (A 1 · · · E · · · A l+1 ) which length is l + 1, an even number. In the aforementioned example, the path becomes APSEPVC, whose length is even now. The source objects and the target objects will meet in the middle type object M = E on the middle position mid = l+1 2 + 1. As a consequence, the new relevance path P ′ can also be decomposed into two equal-length path P L and P R .
DEFINITION 5: Decomposition of relevance path. An arbitrary relevance path P = (A 1 A 2 · · · A l+1 ) can be decomposed into two equal-path path P L and P R (i.e., P = P L P R ), where P L = A 1 A 2 · · · A mid−1 M and M and mid are defined as above.
Obviously, for a symmetric path P = P L P R , P −1 R is equal to P L . For example, the relevance path P = AP CP A can be decomposed as P L = AP C and P R = CP A. For the relevance path APSPVC, we can add a middle type object E in SP and thus the path becomes APSEPVC, so The next question is how we can add the middle type object E in an atomic relation R between Al+1 2 and Al+1 2 +1 in an odd-length path. In order to contain original atomic relation, we need to make the R relation be the composition of two new relations. To do so, for each instance of relation R, we can add an instance of E to connect the source and target objects of the relation instance. An example is shown in Fig. 3(a), where the middle type object E is added in between the atomic relation AB along each path instance.
DEFINITION 6: Decomposition of atomic relation. For an atomic relation R, we can add an object type E (called edge object) between the R.S and R.T . And thus the atomic relation R is decomposed as R O and R I where R O represents the relation between R.S and E and R I represents that between E and R.T . For each relation instance r ∈ R, an instance e ∈ E connects r.S and r.T . The paths r.S → e and e → r.T are the instances of R O and R I , respectively.
It is clear that the decomposition has the following property, whose proof can be found in the Appendix A. based on an atomic relation R (s ∈ R.S and t ∈ R.T ) is: It is easy to find that HeteSim(s, t|I) is a special case of HeteSim(s, t|R), since, for the  We also find that the similarity of an object and itself is not 1 in HeteSim. Taking the right figure of Fig. 3(c) as example, the relatedness of a 2 and itself is 0.33. It is obviously unreasonable.
In the following section, we will normalize the HeteSim and make the relevance measure more reasonable.

D. Normalization of HeteSim
Firstly, we introduce the calculation of HeteSim between any two objects given an arbitrary relevance path. It is easy to prove that the transition probability matrix has the following property. The proof can be found in the Appendix A.
According to the definition and Property 2 of HeteSim, the relevance between objects in A 1 and A l+1 based on the relevance path The above equation shows that the relevance of A 1 and A l+1 based on the path P is the inner product of two probability distributions that A 1 reaches the middle type object M along the path and A l+1 reaches M against the path. For two instances a and b in A 1 and A l+1 , respectively, their relevance based on path P is where P M P (a, :) means the a-th row in P M P .
We have stated that HeteSim needs to be normalized. It is reasonable that the relatedness of the same objects is 1, so the HeteSim can be normalized as follows: DEFINITION 10: Normalization of HeteSim. The normalized HeteSim between two objects a and b based on the relevance path P is: In fact, the normalized HeteSim is the cosine of the probability distributions of the source object a and target object b reaching the middle type object M. It ranges from 0 to 1. Fig.   3(d) shows the normalized HeteSim scores. It is clear that the normalized HeteSim is more reasonable. The normalization is an important step for HeteSim with the following advantages.
(1) The normalized HeteSim has nice properties. The following Property 4 shows that HeteSim satisfies the identity of indiscernibles. (2) It has nice interpretation. The normalized HeteSim is the cosine of two vectors representing reachable probability. As Fouss et al. pointed out [23], the angle between the node vectors is a much more predictive measure than the distance between the nodes. In the following section, the HeteSim means the normalized HeteSim.

E. Properties of HeteSim
HeteSim has good properties, which makes it useful in many applications. The proof of these properties can be found in the Appendix A.
Property 3 shows the symmetric property of HeteSim. Although PathSim [5] also has the similar symmetric property, it holds only when the path is symmetric and a and b are with the same type. The HeteSim has the more general symmetric property not only for symmetric paths (note that P is equal to P −1 for symmetric paths) but also for asymmetric paths. Property 4 shows HeteSim is well constrained. For a symmetric path P (i.e., P L = P R −1 ), P M P L (a, :) is equal to P M P R −1 (a, :), and thus HeteSim(a, a|P) is equal to 1. If we define the distance between two objects (i.e., dis(s, t)) as dis(s, t) = 1 − HeteSim(s, t), the distance of the same object is zero (i.e., dis(s, s) = 0). As a consequence, HeteSim satisfies the identity of indiscernibles. Note that it is a general identity of indiscernibles. For two objects with different types, their HeteSim score is also 1 if they have the same probability distribution on the middle type object. It is reasonable, since they have the similar structure based on the given path.
Since HeteSim obeys the properties of non-negativity, identity of indiscernibles, and symmetry, we can say that HeteSim is a semi-metric measure [25]. Because of a path-based measure, HeteSim does not obey the triangle inequality. A semi-metric measure has many good merits and can be widely used in many applications [25].
Here HeteSim is the non-normalized version.
This property reveals the connection of SimRank and HeteSim. SimRank sums up the meeting probability of two objects after all possible steps. HeteSim just calculates the meeting probability along the given relevance path. If the relevance paths explore all possible meta paths among the two objects, the sum of HeteSim based on these paths is the SimRank. So we can say that HeteSim is a path-constrained version of SimRank. Through relevance paths, HeteSim can subtly evaluate the similarity of heterogeneous objects with fine granularity. This property also implies that HeteSim is more efficient than SimRank, since HeteSim only needs to calculate the meeting probability along the given relevance path, not all possible meta paths.

F. Discussion
Let us analyze the time and space complexity of computing HeteSim. Suppose the average size of one type of objects is n and there are T types objects, the space requirement of HeteSim is just O(n 2 ) to store the relatedness matrix. Let d be the average of |O(s|R i )||I(t|R j )| over all object-pairs (s, t) based on relation R i and R j . For a given l-length relevance path, the time required is O(ldn 2 ), since node pairs (i.e., n 2 ) calculate their relatedness along the relevance path.
For SimRank, the similarity of node pairs in all types (i.e., (T n) 2 ) are iteratively calculated at the same time, so its space complexity is O(T 2 n 2 ), and the time complexity where k is the number of iterations. So the complexity of computing HeteSim is much smaller than SimRank.
Here, we discuss how to choose relevance path. There are several ways to do it. work. Although the RW model can also satisfy the symmetric property through the combination of the reachable probability based on the paths P and P −1 , it is redundancy for symmetric path, as well as short of nice interpretability. For the PRW model, it is inevitable to face the problem that the source and target object will not meet when the length of relevance path is odd. In order to solve it, some optional strategies can be applied, such as assigning the meeting object type. This paper adopts the path deposition strategy based on the following advantages.
(1) It has a uniform framework to evaluate the relevance of same or different-typed objects for arbitrary paths. (2) It provides a simple but effective method to evaluate the relevance of two different-typed objects based on an atomic relation (see Def. 7).
Furtherly, we compare six well-established similarity measures in Table I

A. Datasets
Three heterogeneous information networks are employed in our experiments. authors, and 1.8K author affiliations. After removing stop words in the paper titles and abstracts, we get 1.5K terms that appear in more than 1% of the papers. The network also includes 73 subjects of these papers in ACM category. The network schema of ACM dataset is shown in Fig. 2(a).
DBLP dataset [27]: The DBLP dataset is a sub-network collected from DBLP website 4 involving major conferences in four research areas: database, data mining, information retrieval and artificial intelligence, which naturally form four classes. The dataset contains 14K papers, 20 conferences, 14K authors and 8.9K terms, with a total number of 17K links. In the dataset, 4057 authors, all 20 conferences and 100 papers are labeled with one of the four research areas.
The network schema is shown in Fig. 2(b).
Movie dataset [28]: The IMDB movie data comes from the Internet Movie Database 5 , which includes movies, actors, directors and types. A movie heterogeneous network is constructed from the movie data and its schema is shown in Fig. 2(c). The movie data contains 1.5K movies, 5K actors, 551 directors, and 112 types.

B. Case Study
In this section, we demonstrate the traits of HeteSim through case study in four tasks: automatic object profiling, expert finding, relevance search, and semantic recommendation.    Chen are the young professors and they have done good work in their research areas. However, if the relevance measure is not symmetric (e.g., PCRW), it is very hard to tell which authors are more influential when comparing these relevance scores. For example, the PCRW score of Yan Chen and SIGCOMM is the largest one in the APVC path. However, the value is the smallest one when the opposite path (i.e., CVPA path) is considered. A quantitative experiment in the Appendix C illustrates that, compared to PCRW, HeteSim can reveal the relative importance of author-conference pairs more accurately.

3) Task 3: Relevance Search based on Path Semantics:
As we have stated, the path-based relevance measure can capture the semantics of paths. In this relevance search task, we will observe the importance of paths and the effectiveness of semantics capture through the comparison of three path-based measures (i.e., HeteSim, PCRW, and PathSim) and SimRank. This task is to find the top 10 related authors to Christos Faloutsos based on the AP V CV P A path which means authors publishing papers in same conferences. Through ignoring the heterogeneity of objects, we directly run SimRank on whole network and select top ten authors from the rank results which mix different-typed objects together. The comparison results are shown in Table   IV. At first sight, we can find that three path-based measures all return researchers having the similar reputation with Christos in slightly different orders. However, the results of SimRank are totally against our common sense. We think the reason of bad performances is that SimRank only considers link structure but ignores the link semantics. In heterogeneous networks, different-  Suppose that "M" represents movie, "T" represents the movie types. "A" and "D" represent the actors and directors, respectively. If users want to find movies that share the same actors with "Iron Man", the MAM path can be used in the recommendation system. For users who like the movies which are of the same type with "Iron Man", the path MTM can be used.
The recommendation results are illustrated in Table V. It is shown that HeteSim can recommend different movies based on different paths. The MAM path recommends movies which share actors with the movie "Iron Man", such as "The Kite Runner" and "The Good Night". Although the first four recommended movies (except "Iron Man" itself) all have only one common actor with "Iron Man", the Kite Runner has less actors, so its score is higher. The MTM path recommends movies of the same type with "Iron Man", such as "The Incredible Hulk", "Teenage Mutant Turtles", and "Spawn". "The Incredible Hulk" has more common types with "Iron Man", so it ranks the top one. More interestingly, based on relevance paths, the HeteSim can recommend objects of different types. For example, a user may like the movies that have the same type with the movies of the actor "Sylvester Stallone". The AMTM path can be adopted. The results are shown in the last column of Table V. Since "Sylvester Stallone" has acted the leading role in many movies about boxing and sport, the HeteSim recommends this kind of movies, such as "Rocky" and "Million Dollar Baby". Following this idea, we have designed a semantic-based recommendation system HeteRecom [28].  path. The iterative computation in SimRank and P-PageRank make them longer running time.
The neighbor matching process in RoleSim has high time complexity, which makes it very timeconsuming. The experiments show that HeteSim not only does well on similarity measure of same-typed objects but also has the potential as the similarity measure in clustering with high efficiency.

VI. QUICK COMPUTATION STRATEGIES AND EXPERIMENTS
HeteSim has a high computation demand for time and space. It is not affordable for online query in large-scale information networks. So a primary strategy is to compute relevance matrix off-line and do on-line queries with these matrix. For frequently-used relevance paths, the relatedness matrix HeteSim(A, B|P) can be materialized ahead of time. The on-line query on HeteSim(a, B|P) will be very fast, since it only needs to locate the row and column in the matrix. However, it also costs much time and space to materialize all frequently-used paths.
As a consequence, we propose four strategies to fast compute the relevance matrix. Moreover, experiments validate the effectiveness of these strategies.

A. Computation Characteristics of HeteSim
The computation of HeteSim includes two phases: matrix multiplication (denoted as MUL, i.e., the computation of P M P L and P M P R −1 ), relevance computation (denoted as REL, i.e., the computation of P M P L * P M P R −1 and normalization). In order to analyze the computation characteristics of HeteSim, we do experiments to observe the running time of these two phases on different paths with varying path lengths.
Based on the ACM dataset (see Section V.A), we select four paths with varying length (l): (AP A) l , (AP CP A) l , (AP SP A) l , and (T P T ) l . l means times of path repetition and ranges from 1 to 5. We record the running time of different phases of HeteSim based on these paths as shown in Fig. 5. We first observe MUL's running time in Fig. 5(a). Different paths have different running time. With the increment of path length, the running time of matrix multiplication persistently increase, since more matrix need to be multiplied. Then we consider the running time of REL phase in Fig. 5(b). Besides the same observation with Fig. 5(a), the running time of REL is greatly affected by the length l. That is, the running time of REL significantly increases for (AP CP A) l and (AP SP A) l when l is 2 and 4. Let's take the (AP CP A) l as an example to analyze the reason. When l is 1, 3, and 5, the source and target nodes will meet at the middle node C along the (AP CP A) l path, so the relevance calculation is P M AC × P M CA . However, the relevance calculation is P M AA × P M AA when l being 2 and 4. Since the dimension of A is much larger than that of C, the running time of P M AA × P M AA is much longer than that of P M AC × P M AC . The similar reason makes (T P T ) l have the opposite fluctuation. In addition, the time spent in REL does not grow any longer when the matrix become a dense one. So its increase ratio gradually decreases. For the (AP A) l path, the dimension of A and P are close (# A 17K and # P 12K), so its running time has no distinct difference for different path lengths. In addition, the reachable probability matrix always keeps sparse, which makes the running time of (AP A) l smaller than that of other paths. On the other hand, the ratio of MUL consistently increases with the increment of path length.
From these experiments, we can summarize two characteristics of HeteSim computation. (1) The relevance computation is the main time-consuming phase. It implies that the speedup of matrix multiplication may not significantly reduce HeteSim's running time, although this kind of strategies is widely used in accelerating SimRank [4] and PCWR [24]. (2) The dimension and sparsity of matrix greatly affect the efficiency of HeteSim.

B. Quick Computation Strategies
Although we cannot reduce the running time of relevance computation phase directly, we can accelerate the computation of HeteSim through adjusting matrix dimension and keeping matrix May 22, 2014 DRAFT sparse. Based on above idea, we design the following four strategies.

1) Dynamic Programming Strategy:
The matrix multiplication obeys the associative property. Moreover, different computation sequences have different time complexities. The Dynamic Programming strategy (DP) changes the sequence of matrix multiplication with the associative property. The basic idea of DP is to assign low-dimensioned matrix with the high computation priority. For a path P = R 1 • R 2 • · · · • R l , the expected minimal computation complexity of HeteSim can be calculated by the following equation and the computation sequence is recorded by i.
The above equation can be easily solved by dynamic programming method with the O(l 2 ) complexity. The running time can be omitted, since l is much smaller than the matrix dimension.
There may be many duplicate sub-paths in the relevance path. Obviously, these reduplicative sub-paths only need to be computed once. For example, the result of APTPA can be obtained by computing the matrix AP T once. During the matrix multiplication, the DP strategy reserves the computation sequences of matrices and corresponding results. For a new computation sequence, if it has been computed before, the corresponding result can be employed directly. So the reuse strategy further accelerates the matrix multiplication. Note that the DP strategy only accelerates the MUL phase (i.e., matrix multiplication) and it does not change relevance result, so the DP is a information-lossless strategy.

2) Truncation Strategy:
The truncation strategy is based on the hypothesis that removing the probability on those less important nodes would not significantly degrade the performance, which have been proved by many researches [24], [31]. One advantage of this strategy is to keep matrix sparse. The sparse matrix greatly reduces the amount of space and time consumption.
The basic idea of truncation strategy is to add a truncation step at each step of random walk.
In the truncation step, the relevance value is set with 0 for those nodes when their relevance values are smaller than a threshold ε. A static threshold is usually used in many methods (e.g., ref. [24]). However, it has the following disadvantage: it may truncate nothing for matrix whose elements all have high probability and it may truncate most nodes for matrix whose elements all have low probability. Since we usually pay close attention to the top k objects in query task, the threshold ε can be set as the top k relevance value for each search object. For a similarity matrix with size M × L, the k can be dynamicly adjusted as follows.
where W is the number of top objects, decided by users. The basic idea of dynamic adjustment is that the k slowly increases for super object type (i.e., L is large). The W and β determine the truncation level. The larger W or β will cause the larger k, which means a denser matrix. It is expensive to determine the top k relevance value for each object, so we can estimate the value by the top kM value for the whole matrix. Furtherly, the top kM value can be approximated by the sample data with ratio γ from the raw matrix. The larger γ leads to more accurate approximation with longer running time. In summary, the truncation strategy is an information-loss strategy, which keeps matrix sparse with small sacrifice on accuracy. In addition, it needs additional time to estimate the threshold ε.
3) Hybrid Strategy: As discussed above, the DP strategy can accelerate the MUL phase and the truncation strategy can indirectly speed up the REL phase by keeping sparse matrix. So a hybrid strategy can be designed to combine these two strategies. For the MUL phase, the DP strategy is applied. After obtaining the P M P L and P M P R −1 , the truncation strategy is added.
Different from the above truncation strategy, the hybrid strategy only truncates the P M P L and P M P R −1 . The hybrid strategy utilizes the benefits of DP and truncation strategies. It is also an information-loss strategy, since the truncation strategy is employed. In this study, we applied the MC strategy to estimate the value of P M P L and P M P R −1 . The value of P M P (a, b) can be approximated by the normalized count of the number of times that the walkers visit the node b from a along the path P.

4) Monte Carlo
P M P (a, b) = #times the walkers visit b along P #walkers f rom a  The number of walkers from a (i.e., K) controls the accuracy and amount of computation.
The larger K will achieve more accurate estimation with more time cost. An advantage of the MC strategy is that its running time is not affected by the dimension and sparsity of matrix.
However, the high-dimension matrix needs larger K for high accuracy. As a sampling method, the MC is also an information-loss strategy.

C. Quick Computation Experiments
We  is not the case for the truncation and hybrid strategies, which significantly accelerate the HeteSim computation and have a close speedup ratio on most conditions. Except the AP A path, the MC strategy has the highest speedup ratio among all four strategies on most conditions. Then, let's observe their accuracy from Fig. 6 (e)-(h). The accuracy of the DP strategy is always close to 1. The hybrid strategy achieves the second performances for most paths. The accuracy of the MC strategy is also high for most paths, while it fluctuates on different paths. Obviously, the truncation strategy has the lowest accuracy on most conditions. As we have noted, the DP is an information-lossless strategy and it only speeds up the MUL phase. Moreover, the MUL phase is not the main time-consuming part for most paths. So the DP strategy trivially accelerates HeteSim with the accuracy close to 1. The truncation strategy is an information-loss strategy to keep matrix sparse, so it can effectively accelerate HeteSim. That is the reason why the truncation strategy has the high speedup ratio but low accuracy. The hybrid strategy combines the DP and truncation strategy. So it has a close speedup ratio to the truncation strategy. The hybrid strategy only does truncation on the last step of random walk, which makes it less information-loss. It explains that its accuracy is higher than the truncation strategy. As we know, the essence of the MC strategy is repeatedly random sampling. In order to achieve high accuracy, more walkers (i.e., larger K) are needed for high-dimension or sparse matrix. In our experiments, the fixed walkers (i.e., K is 500) makes the MC strategy the poor accuracy on some conditions. For example, in Fig. 6 (h), the relevance calculation is P M T P × P M T P for (T P T ) 5 . The high dimension of P and even distribution result in the low accuracy of MC strategy.
In order to clearly illustrate the effect of these strategies on two phases of HeteSim computation, a typical running-time example on (AP CP A) l is shown in Fig. 7. It is clear that the DP strategy greatly accelerates the MUL phase indeed, but it has no effect on the REL phase. On the contrary, the truncation strategy is slower than the baseline on the MUL phase, due to sparse matrix and additional time spent in estimating the threshold. However, the truncation strategy greatly accelerates the REL phase because the sparse matrix is kept. Compared to the truncation strategy, the MC strategy not only accelerates the REL phase but also benefits the MUL phase on dense matrix.
According to the analysis above, these strategies are suitable for different paths and scenarios.
For very sparse matrix (e.g., (AP A) l ) and low-dimension matrix (e.g., (AP CP A) 3 ), all strategies cannot significantly improve efficiency. However, in these conditions, the HeteSim can be quickly computed without applying any quick computation strategies. For those dense (e.g., (AP CP A) 4 ) and high-dimension matrix (e.g., (AP SP A) 4 ) which has huge computation overhead, the truncation, hybrid, and MC strategies can effectively improve the HeteSim's efficiency. Particularly, the speedup of the hybrid and MC strategies are up to 100 with little loss in accuracy. If the MUL phase is the main time-consuming part for a path, the DP strategy can also speed up HeteSim greatly without loss in accuracy. The MC strategy has very high efficiency, but its accuracy may degrade for high-dimension matrix. So the appropriate K needs to be set through balancing the efficiency and effectiveness.

VII. CONCLUSION
In this paper, we study the relevance search problem which measures the relatedness of heterogeneous objects (including same-typed or different-typed objects) in heterogeneous networks. We propose a general relevance measure, called HeteSim. As a path-constraint measure, HeteSim can measure the relatedness of same-typed and different-typed objects in a uniform framework. In addition, HeteSim is a semi-metric measure, which can be used in many applications. Extensive experiments validate the effectiveness and efficiency of HeteSim on evaluating the relatedness of heterogeneous objects.
There are some interesting directions for future work. Firstly, more methods can be explored May 22, 2014 DRAFT to measure the relatedness of heterogeneous objects, such as path count and RW strategies.
Secondly, since the quick computation strategies proposed in this paper are all in-memory methods, the parallel computation methods of HeteSim can be an interesting topic to explore.
Last but not least, the problem on how to choose and weight different meta paths are also important issues for heterogeneous networks.
APPENDIX A

PROOF OF PROPERTIES
Proof of Property 1. According to Definition 6, for each relation instance a → b in relation A and b ∈ B), add an object e (e ∈ E) between a and b, and let w ae = w eb = √ w ab where w means the weight of relation instances. Note that for adjacent matrix, w ae = w eb = √ w ab =1. Since a and b only meet on e, so R O (a, :) * R I (:, b) = w ae * w eb = w ab = R(a, b). So Since the process is unique, the decomposition is unique. )) = 1, so HeteSim(a, b|P) = 1.
= HeteSim(a 1 , a 2 |RR −1 )   It is reasonable, since these conferences all share many authors whose research areas are data mining and knowledge management.

APPENDIX C EVALUATION OF RELATIVE IMPORTANCE
The relative importance is hard to quantitatively measure. However, we can roughly measure the relatedness of authors and conferences by the number of papers that authors publish in conferences, and then rank the relatedness as their relative importance (i.e., ground truth). We also compute the relatedness of authors and conferences based on HeteSim and PCRW, and then rank these values. Through computing the average rank difference from the ground truth, we can roughly measure the accuracy of relative importance. For example, C. Faloutsos is ranked 1st on KDD as ground truth, while an approach rank him 6th. So the rank difference is 5. Note    By contrast, the CVPAPA path emphasizes on the publication records of the co-authors. The results also reflect this point. For example, although Charu C. Aggarwal published 13 papers in KDD, not the highest publication records, he has many co-authors which include many highpublication-record authors (e.g., Philip Yu and Jiawei Han), so he is the first author related to KDD based on CVPAPA path. The same thing also happens to other authors. Taking Bianca Zadrozny for example, she only published 6 papers in KDD. However, her co-authors also include many high-publicaton-record authors, such as Philip Yu, Naoki Abe, and Wei Fan. In all, HeteSim can accurately capture the semantics under relevance paths.