Link weights recovery in heterogeneous information networks
Hong-Lan Botterman Robin Lamarche-Perrin



Socio-technical systems usually consists of many intertwined networks, 
each connecting different types of objects (or actors) through a variety 
of means. As these networks are co-dependent, one can take advantage of 
this entangled structure to study interaction patterns in a particular 
network from the information provided by other related networks.
A method is hence proposed and tested to recover the weights of missing or unobserved links in heterogeneous information networks (HIN) - abstract representations of systems composed of multiple types of entities and their relations.
Given a pair of nodes in a HIN, this work aims at recovering the exact weight of the incident link to these two nodes, knowing some other links present in the HIN. 
To do so, probability distributions resulting from path-constrained random walks i.e., random walks where the walker is forced to follow only a specific sequence of node types and edge types, capable to capture specific semantics and commonly called a meta-path, are combined in a linearly fashion in order to approximate the desired result.  
This method is general enough to compute the link weight between any types of nodes. Experiments on Twitter and bibliographic data show the applicability of the method.

A Constant-Factor Approximation Algorithm for Online 
Coverage Path Planning with Energy Constraint
    Ayan Dutta, Gokarna Sharma
A. Dutta is with the School of Computing, University of North Florida, Jacksonville, FL 32224, USA
a.dutta@unf.edu G. Sharma is with the Department of Computer Science,
Kent State University, Kent, OH 44242, USA
sharma@cs.kent.edu


    December 30, 2023
=======================================================================================================================================================================================================================================================================

empty




§ INTRODUCTION


Networked data are ubiquitous in real-world applications. Examples of such data are humans in social activities, proteins in biochemical interactions, pages of Wikipedia or movies-users from Amazon just to name a few. These are abstracted by a network where nodes represent the entities (e.g. individuals or pages) of the examined system whilst (directed) links stand for existing physical or virtual ties between them. Weights can also be put on links to state, for instance, their importance.
In some cases, the nodes and/or the links are of different nature. For example, in social activities, the links can reflect online or offline communication or more obviously, in the movie-user case, nodes represent two different objects. 
Taking these differences explicitly into account in the modeling can only enrich the understanding of the inspected system. 
Thus, heterogeneous information networks (HIN), abstract representations of systems composed of multiple types of entities and their relations, are good candidates to model such data together with their relations, since they can effectively fuse a huge quantity of information and contain rich semantics in nodes and links.

In the last decade, the heterogeneous information network analysis has attracted a growing interest and many novel data mining tasks have been designed in such networks, such as similarity search, clustering, classification and link prediction <cit.>. 
The latter can sometimes refer to the term recovery, in the sense that links already exist but are missing or imperfectly  observed in the data. This could be due to sampling or depending on the system under scrutiny, due to node/agent's voluntary decision not to give access to all her data (e.g. online social apps).  
Whatever the reason, capturing the presence of a link is sometimes not enough sufficient. For instance, in a social network, knowing two individuals are linked does not say anything about the frequency of their communication or the strength of their friendship. 
Hence recovering the actual link weight can bring useful information as for instance, in recommendation systems where the weight can be taken for the “rating" a user would give to an item. 
The goal of this work is to recover, for a given pair of nodes in a weighted HIN, the actual incident link weight to these two nodes, knowing some other links present in the HIN. 

Link prediction can be related to node similarity problem. Indeed, the similarity score between two nodes, result of a particular function of these two nodes, can be seen as the strength of their connection.
Here, this function is related to a particular random walk on the graph and so, to the probabilities of reaching one node through different paths, starting from another.

In HIN, most of similarity scores <cit.> are based on the concept of meta-path. In simple terms, this corresponds to a concatenation of node types linked by corresponding link types and the type of a node/link is basically a label in the abstract representation. 
Meta-paths can be used as a constraint to a classic random walk: the walker is allowed to take only paths satisfying a particular meta-path. These path-constrained random walks have the sensitivity to explicitly take into account different semantics present in HIN.
For instance, in a bibliographic network, we can distinguish four types of entities: Authors (A), Papers (P), Venues (V) and Topics (T). Starting from a particular paper, if a walker follows the meta-path PVP, he is likely to end to any another paper published in the same venue than the first. Now, if he follows the meta-path PTP, the ending paper will be about the same topic. Even if the starting and ending papers are the same, the semantics behind may be radically different.

Back to our goal, we can see it as a (linear) regression problem where the aim is to recover the link weight i.e., a continuous value.
This means that the target link weight between a pair of nodes is approximated by a linear combination of probabilities, results of path-constrained random walks performed on the HIN. These probabilities thus translate the fact of being at a particular node starting from another one and are the regressors  for the linear regression.   
Thenceforth, in order to make recovery tasks, data is commonly split into two sets: training and test. The proposed method aims at finding a relevant set of meta-paths together with their coefficient such that the difference between the exact link weight and its approximation is minimized for the training set. Obtained coefficient are then tested on the test set. 
 
The rest of this paper is organized as follows. 
In Sec. <ref>, some basic concepts about HIN are presented and the problem statement is exposed.
Sec. <ref> explains our method and we apply it on empirical data in Sec. <ref>. First, in Sec. <ref>, the method is tested to recover the link weights between entities of different types into Twitter data. Then, in Sec. <ref>, it is applied on bibliographic data with the same type of target nodes. 
We review some related work in Sec. <ref> and  we finally conclude and discuss some perspectives in Sec. <ref>.



§ PREMIMINARY CONCEPTS



In this section, we present some basic concepts of weighted HIN useful for the following and define the “weight recovery” problem. Fig. <ref> illustrates this section. 


A weighted directed mutligraph is a 5-tuple G :=(V,E,w,μ_s,μ_t) with V the node set, E the link set, w: E →ℝ^+ the function that assigns to each link a real non negative weight, μ_s: E → V the function that assigns to each link a source node, μ_t: E → V the function that assigns to each link a target node.


This concept allows us to introduce the definition of HIN which basically is a weighted directed multigraph with multiple node and link types.


A HIN H := (G,𝒱,ℰ,ϕ,ψ) is a weighted directed multigraph G along with 𝒱 the node type set, ℰ the link type set, ϕ: V →𝒱 the function that assigns a node type to each node and ψ: E →ℰ the function that assigns a link type to each link such that if two links belong to the same link type, the two links share the same starting and target node type i.e.,
∀  e_1, e_2 ∈ E,  ( ψ(e_1) = ψ(e_2) ) ⇒( ϕ(μ_s(e_1)) = ϕ(μ_s(e_2))  ∧ ϕ(μ_t(e_1)) = ϕ(μ_t(e_2)) ).




Fig.<ref> illustrates such a network composed of five node types and twenty link types. However, disentangling the different entities present in the HIN is not necessarily a trivial task. Indeed, it sometimes takes a broader view of the system in question to describe it. For that purpose, the concept of network schema i.e. the meta level description of the HIN, is proposed. In simple terms, this corresponds to the graph defined over the node and link types of the associated HIN. It is represented in Fig.<ref>.  


Let H be a HIN. The schema T_H for H is a directed graph defined on the node types 𝒱 and the link types ℰ i.e., T_H := (𝒱,ℰ,ν_s,ν_t) with ν_s : ℰ→𝒱 : E^* ↦ν_s(E^*) := ϕ(μ_s (e) ) the function that assigns to each link a source node and ν_t : ℰ→𝒱 : E^* ↦ν_t(E^*) := ϕ(μ_t (e) ) the function that assigns to each link a target node, where e ∈ E such that ψ(e) = E^*


Note that we can effectively take any such element e since {e ∈ E  | ψ(e) = E^* } is the equivalence class of any of its elements, with the equivalence relation “has the same type of”. By definition of HIN, it is sufficient to take one member of the equivalence class to know the node types that the link type E^* connects.

Two entities in a HIN can be linked via different paths and these paths have different semantics. These paths can be defined as meta-paths as follows <cit.>.


A meta-path 𝒫 of length n ∈ℕ is a sequence of node types V_0, ⋯, V_n ∈𝒱 linked by link types E_1, ⋯, E_n ∈ℰ as follows: 𝒫 = V_0    V_1  ⋯   V_n-1   V_n which can also be denoted as 𝒫 = E_1 E_2 ⋯ E_n.


Given a meta-path 𝒫 = V_0      V_1   ⋯    V_n-1     V_n and a path P = v_0      v_1   ⋯    v_n-1     v_n, if ∀  i  ∈{0, ..., n },  ϕ(v_i)=V_i,  ∀  i  ∈{1, ..., n },  μ_s(e_i) = v_i-1,  μ_t(e_i)=v_i and ψ(e_i) = E_i, then path P satisfies meta-path 𝒫 and we note P ∈𝒫. Hence, a meta-path is a set of paths.

In Fig.<ref>, an example of meta-path is ▪→▴→, in blue, in the network schema. Blue paths in the HIN in Fig.<ref> are said to satisfy this meta-path since each one of their segments respects the aforementioned conditions.

[Weight recovery]
Let be a HIN H=(G,𝒱,ℰ,ϕ,ψ), with G=(V,E,w,μ_s,μ_t) a directed weighted multigraph, and a target link type E_c between two node types. The “weight recovery problem” is to find a set of relevant meta-paths ℰ_𝒫 and a linear function F of probabilities resulting from random walks constrained by these meta-paths that best quantifies, for each pair of nodes in H, the strength of their connection via E_c. 






§ METHOD



We present our method for solving Problem <ref> in three steps. 
Consider a HIN and let us denote by E_c the target link type defined between V_0 and V_n.
We consider a meta path 𝒫 = V_0    V_1  ⋯   V_n-1   V_n different from E_c. There may be repetitions in this sequence of nodes and links. Let us introduce the notation 𝒫≡𝒫^0,n and let us denote by 𝒫^a,b the truncated meta path of 𝒫 from node type V_a to V_b.



 §.§ Path-Constrained Random Walk.



Let X_i ∈ V_i be a random variable representing the position of a random walker  in the set V_i. A random walk starting from X_0 constrained by the meta-path 𝒫 corresponds to a discrete-time Markov chain i.e., a sequence of random variables X_0,  X_1, ...,  X_n with the Markov property: ∀  i ∈{0,...,n },  ∀  (v_0,...,v_n) ∈ V_0 × ... × V_n,

    ℙ(X_i=v_i  |  X_i-1=v_i-1, ..., X_0 = v_0) = ℙ(X_i=v_i  |  X_i-1=v_i-1).


Here, since there may be more than one link type between two node types, we introduce de notation ℙ((X_i=v_i  |  X_i-1=v_i-1)  | 𝒫^i,i+1) =: ℙ((v_i  |  v_i-1)  | 𝒫^i,i+1) = ℙ((v_i  |  v_i-1)  |  E_i) to emphasize the fact that the random walk is constrained by the meta-path 𝒫. 
This means that for a walker to reach v_i from v_i-1, he has to follow only links of type E_i ≡𝒫^i,i+1. 
The probability ℙ((v_i  |  v_i-1)  |  E_i) thus defined is computed as 

    ℙ((v_i  |  v_i-1)  |  E_i) = 
    w_E_i(v_i-1,v_i)/∑_k w_E_i(v_i-1,v_k)

where w_E_i(v_j,v_k) is the link's weight of type E_i between nodes v_j and v_k.

Thenceforth, given v_n ∈ V_n and v_0 ∈ V_0, the probability of reaching v_n from v_0 following the meta path 𝒫, denoted by ℙ((v_n | v_0)  | 𝒫), is simply defined by the random walk starting at v_0 and ending at v_n following only paths satisfying 𝒫. 
This conditional probability may be expressed recursively by means of the law of total probability

    ℙ((v_n | v_0)  | 𝒫)
       = ∑_v_n-1∈ V_n-1[
    ℙ((v_n | v_n-1)  |  E_n )  
       ×ℙ((v_n-1| v_0)  | 𝒫^0,n-1) 
    ] 
    
       = ∑_v_n-1∈ V_n-1[
    w_E_n(v_n-1,v_n)/∑_k w_E_n(v_n-1,v_k) 
       ×ℙ((v_n-1| v_0)  | 𝒫^0,n-1)
    ]
 
with ℙ((v_1 | v_0) |𝒫^0,1)=w_E_1(v_0,v_1) / ∑_k w_E_1(v_0,v_k) the basis of recurrence. 
In the following, we use the notation PCRW(𝒫) to denote the column vector of such conditional probabilities ℙ((v_n | v_0)  | 𝒫), ∀  v_0,   v_n i.e., PCRW(𝒫) = [ℙ((v_0 | v_0)  | 𝒫), ℙ((v_1 | v_0)  | 𝒫), ...., ℙ((v_n | v_n)  | 𝒫)]^T.

For instance, in the HIN in Fig.<ref>, the probability for a walker to reach the green star  from the green square ▪ following the meta-path ▪→▴→ equals 5/12.

Note that we forbid the walker to return to the initial node on the penultimate step of the walk i.e., if V_n-1=V_0, the sum in eq. (<ref>) only holds for all v_n-1≠ v_0. 
It prevents us from using what we are looking for to find what we are looking for.


It is possible that a node v_i ∈ V_i is not connected to any node v_j ∈ V_j by the link type E_ij and thus, the transition probability is not defined. To overcome this problem, we provide each set V_k with a hole node h_k on which point all the disconnected nodes. Plus, all the holes are connected with each other and holes cannot point to another node (i.e., no hole node). 
Formally, ∀  V_k ∈𝒱,   V^h_k := V_k ∪{ h_k }. ∀  E_ij∈ℰ, if w_E_ij(v_i,v_j)=0,  ∀  v_j ∈ V_j then w_E_ij(v_i,h_j)=1, otherwise w_E_ij(v_i,h_j)=0. Furthermore, ∀  E_ij∈ℰ, w_E_ij(h_i,h_j)=1 and ∑_v_j ∈ V_j w_E_ij(h_i,v_j)=0.
In this fashion, transition probabilities are always well defined. 




 §.§ Linear Regression Model.

Since H is a HIN, multiple types of links can connect the nodes. Hence, there is no reason to restrict ourselves to a single meta path to compute the reachability of one node from another. 
As a result, the similarity between v_n and v_0 is defined by several path-constrained random walk results combined through a linear regression model of the form

    F((v_n | v_0)  | ℰ_𝒫)
    :=
    β_0 + 
    ∑_𝒫∈ℰ_𝒫β_𝒫 ℙ((v_n | v_0)  | 𝒫)

where ℰ_𝒫 is the set of selected meta-paths and the vector  := [β_0, β_1, ⋯, β_|ℰ_𝒫|]^T is real-valued coefficients. 
The coefficients stress the contribution of each meta-path in the final similarity score F((v_n | v_0)  | ℰ_𝒫).
Since the components of  are not confined in [0,1] and do not sum to 1, F is a real-valued function whose image is neither confined in [0,1].

Now, we have a linear regression problem since we want to recover the exact link weights with respect to E_c. The dependant variable is thus PCRW(E_c) whilst the predictors are PCRW(𝒫), 𝒫∈ℰ_𝒫. 

The choice of linear model is simply motivated by its interpretability in our particular case. 
Given example node pairs and their link weights,  is estimated by the least squares method which is appreciated for its applicability and simplicity. In formulae with 1 the column vector whose entries are 1: 




c PCRW(E_c) 
↓
[c]

 PCRW(E_c)
=
cccc1   PCRW(𝒫_0)   …    PCRW(𝒫_|ℰ_𝒫|)
↓   ↓      ↓
[cccc]         
         
4cPCRW(ℰ_𝒫)
         
         

c

[c]

β
+
c

[c]

ϵ 

= 
[ F(ℰ_𝒫) ]
+
[ ϵ ] 



and we choose  such that the residual sum of squares RSS =ϵ^T ϵ = ‖ϵ‖^2 is minimized i.e.,  = ( PCRW(ℰ_𝒫) ^T PCRW(ℰ_𝒫)  )^-1 PCRW(ℰ_𝒫) ^T PCRW(E_c).




 §.§ Forward Selection Procedure.

In order to determine the set ℰ_𝒫, we use the forward selection with p-value and r^2 criteria. This is a greedy approach but very simple and intuitive. The p-values are used to test the significance of each predictor. Given the hypothesis H_0: β = 0 against the hypothesis H_1: β≠ 0, the p-value p is the probability, under H_0, of getting a statistics as extreme as the observed value on the sample. We reject the hypothesis H_0, at the level α, if p ≤α in favor of H_1. Otherwise, we reject H_1 in favor of H_0.
Conversely, the r^2 score is used to test the quality of the entire model. It is the proportion of the variance in the dependent variable that is predictable from the predictors. 
Note that the r^2 = 1-RSS/TSS where TSS is the total sum of squares i.e., is the sum of the squares of the difference of the dependent variable and its mean. Hence, maximizing the r^2 is equivalent to minimizing the RSS.

So, given k predictors or explanatory variables which are the probability distributions PCRW(𝒫_k), the forward selection procedure works as follows



0em

  * Start with a null model i.e. no predictor but only an intercept. Typically, this is the average of the dependent variable;

  * Try k linear regression models (i.e., models with only one predictor) and chose the one which gives the best model with respect to the criterion. In our case, the one that minimizes RSS or alternatively, the one that maximizes the coefficient of determination r^2;

  * Search among the remaining variables the one that, added to the model, gives the best result i.e., the higher r^2 such that all the variables in the model are significant i.e., their p-value is below the chosen threshold. Iterate this step until no further improvement.





 §.§ Validation

Since we would like to use the regression model as a prediction model (i.e., not only a descriptive one), we use Monte Carlo cross-validation a.k.a. repeated random sub-sampling validation <cit.>.
Given a data set of N points, the method simply splits them into a training subset s_t and a test subset s_v. The model is then trained on s_t and tested on s_v. This procedure is repeated multiple times and the results are then averaged over the splits.
Note that the results of Monte Carlo cross-validation tends towards those of leave-p-out cross-validation <cit.> as the number of random splits tends to infinity.
The drawbacks of this method are the possibility that some observations may never be selected for training or on the contrary, may be used at each split. Plus, the results depend on the different random splits i.e., it displays Monte Carlo variation.
However, it has advantage (over k-fold cross validation <cit.>) as the proportion of the split is independent of the folds (iterations). It means Monte Carlo allows to explore somewhat more possible partitions, though one is unlikely to get all of them since there exist [   N; s_t ] unique training subsets.



Given a HIN H with 𝒱 = { V_1, ..., V_k, ..., V_m } the set of node types with V_k = {V_k,1, ..., V_k,q}, one can want to understand the “role” of each V_k,r. 
Let two node types V_i and V_j (not necessarily distinct) be the target node types and ℰ_𝒫 the set of meta-paths.
Plus, let V_i and V_j be linked by a specific meta-path including the node type V_k, namely, 𝒫 =  V_i   ⋯     V_k ⋯     V_j with 𝒫∈ℰ_𝒫. 
We can thus construct q subsets S_i,r = { v_i ∈ V  | ϕ(v_i) ∈ V_i ∧∃  P = v_i   ⋯     v_k,r⋯     v_j } and q subsets S_j,r = { v_j ∈ V  | ϕ(v_j) ∈ V_j ∧∃  P = v_i   ⋯     v_k,r⋯     v_j } (r=1,..,q) such that with v_k,r∈ V_k,r⊆ V_k (v_j ∈ V_j and v_i ∈ V_i resp.) and P ∈𝒫.
We can thus build q linear regression models: one for each HIN H_r formed from the node set {v ∈ V  | ϕ(v) ∈𝒱∖{ V_k, V_i, V_j }}∪{ S_i,r, S_j,r} with meta-paths ℰ_𝒫∖𝒫.
Analysing the vector  of each final model can bring some insight about the “role” of each V_r.





§ EXPERIMENTS



We test the proposed methods on two real-worls data sets. The first one, related to FIFA WorldCup 20104 Twitter data, allows us to perform tests between target nodes with different types. The task consists in recovering the user-hashtag frequency. The second data set, related to bibliographic data, focuses on target nodes of the same types and tackles the problem of co-authorship.






 §.§ FIFA WorldCup 2014 Twitter data.



We present the data set on which we test the proposed method as well as the construction of the resulting graphs. Then, we report our results concerning different tests namely, the importance of meta path length, a description task and finally a recovery task. 



  §.§.§ Data Set Description and Setup.


The data we use is a set of tweets collected from Twitter during the Football World Cup 2014. This period extents from June 12 to July 13, 2014. 
Twitter allows multiple kinds of interactions between its users. Here, we consider retweet (RT), reply (RP) and mention (MT) actions plus the fact of posting hashtags (UH). 
The RT relationship means that a user broadcasts a tweet previously posted by another user. The RP action is simply a response tweet to another user in connection with her previous tweet. The last action considered here is the MT action. This happens when a user mentions explicitly another user in her post.

Based on these actions, we construct a HIN with two node types 𝒱={users, hashtags} and four edge types ℰ={RT, RP, MT, UH} as illustrated in Fig. <ref>. 
Each node represents a user or a hashtag. We create a link from u_1 to u_2 if u_1 retweets, replies (to) or mentions u_2 and the weight of the link correspond to the number of times u_1 performs the specific action towards u_2 during the whole world cup. For the user-hashtag graph, a link exists between u and h if h appears in u's post and the weight of the link corresponds to the number of times u post h during the whole world cup. Note that we exclude hashtags present in the retweeted posts since in these cases, users do not write them themselves. Furthermore, considering them would provoke a trivial correlation between UH and RT-UH. All graphs are directed and weighted. 

The data set contains 13,826 users and 14,392 hashtags.
The RT graph is composed of 6,069 nodes and 19,495 links, the RP graph is composed of 8,560 nodes and 11,782 links and the MT graph is composed of 11,782 nodes and 60,506 links.
Note that Pearson coefficient between the stochastic matrices rises to 0.1776, 0.6783 and 0.4286 for RT/RP, RT/MT et RP/MT respectively. Thus, the retweet and mention relationships are clearly correlated which may cause some problems for the proposed method, as we shall see, since it is well known that least squares method is sensitive to that.
Since the data is related to the world cup, the most used hashtags of bipartite users-hashtags graph UH are those referring to the 32 countries involved in the final phase as well as those referring directly to the event (#WorldCup2014, #Brazil, #Brasil2014, #CM2014, ...). The semi finalists have the greatest in-strength (in-strength of the node j is s^in_j = ∑_i w_ij).



  §.§.§ Results.

We apply the proposed method to find if the hashtags posted by users (UH) can be explained by other relations (RT, RP, MT and their combinations). For instance, given a user u, explaining UH by RT-UH and MT-RP-UH means that the hashtags posted by u are, to some extent, a combination of those posted by the users retweeted by u and those posted by the users who received a response from users mentioned by u. In other words, we try to understand if, in the case of the football World Cup 2014, the probability that users post hashtags can be explained by the relations these users have with other users and the probability that these latter have to post these hashtags. 

Meta-Paths of Length 2.
We test linear regression models with all the possible combinations of meta-paths of length 2 (see Table <ref>). This test allows a first glimpse of the contribution of the simplest predictors. 

First, the more the predictors, the better the value of r^2. It thus could be tempting to consider them all. Nevertheless, it does not mean that all predictors are significant.
Indeed, the analysis of the coefficients and p-values makes it possible to realize the correlation of some variables. In models B2 and A3, the RT-UH and MT-UH meta-paths are both present. However, the p-value associated to RT-UH is greater than 0.05 which states that we accept the null hypothesis for this predictor. This could be a consequence of the correlation between RT-UH and MT-UH. 


In summary and as it can be seen in Table <ref>, the best model according to the r^2 and the p-values with threshold α=0.05 would be the model A2 whose predictors are RT-UH and RP-UH. The gain in the r^2 with respect to any other model with 1 regressor (and so simpler model) is worth it i.e., important r^2 improvement and not really more complexity added.
This means that, for a given user, the hashtags she posts can be explained by the hashtags posted by the users she retweets with a contribution of 0.5795 and the users she replies to with a contribution of 0.3957. This model accounts for 61.16% of the variance.

Importance of Meta Path Length.
This subsection looks at the length of the meta-paths for a given link type. 
More specifically, we compute, for each link type, the r^2 score when the only predictor is associated to a random walk of length l=1,...,10 repeating the same link type. For instance, for l=2 and the retweet action, the predictor will be RT-RT-UH representing the hashtags posted by people who are retweeted by people who are themselves retweeted. 
Intuitively, the importance of a meta-path decreases with its length (=l+1) since considering longer meta-paths means considering more extended neighborhoods, hence the information is more diffused. By way of illustration, the walker can attain a lot of nodes with some of them really far from the starting node.

This is corroborated in Fig.<ref> where we can see a tendency to decrease with respect to the meta-path length.
Each link type brings a different quantity of information and the MT type is the more informative for our purpose.




Plus, this analysis exposes a characteristic of the reply dynamics: most of the time, the replies involved only two people <cit.>. This is reflected through the oscillations of the reply scores in Fig. <ref>. The scores associated to odd length random walks are low since the walker is forbidden to return to the initial node on the penultimate step of the walk (see Fig. <ref>).



We also draw in black the r^2 scores when we do not differentiate the link types (ALL) i.e., all the link weights between to nodes are aggregated. This score is below the average score of the three specific link types. One can see that just taking the mention or retweet type is more informative than the aggregation which reinforces the relevance of differentiating the link types.

Fig. <ref> shows r^2 scores when we combine variables of different lengths related to the same link type in the model. 
Actually, the r^2 associated to n number of variables is related to the model whose predictors are all meta-paths of length smaller or equals to n+1 and whose the steps except the last are in the same type of links. 
For instance, for 3 variables, the predictors are RT-UH, RT-RT-UH and RT-RT-RT-UH (for the RT case). 
Again, the more the variables, the better the score. Also, the increase is not linear; the best improvement happens when we combine length-1 and length-2 variables which indicates the need to consider them together.
We can also observe that scores given by the RT and MT types are really similar when considering more than two variables while there is a clear difference in the r^2 score for single variable. It means that their respective combinations have the same result in term of r^2 although the underlying semantics are different.
Once again, the r^2 score for the aggregation is shown and is far below the other scores. This indicates that it is important to distinguish the types of links.

Since it is often desirable to keep a model simple both in term of interpretability and computation time, there is a trade-off between the highest possible r^2 and the cost to attain it. 
The tests here performed tend to show that considering too long as well as too many meta-paths is not necessarily useful in our case. Indeed, the gain in the r^2 is not worth it considering the complexity it brings.

Forward Linear Regression for Data Description.
We apply the proposed algorithm on the entire data set with a threshold α = 0.05 for p-values. As a reminder, the procedure stops when there is no longer possible to improve the r^2 by adding significant regressors. Since the length of meta-paths is unbounded, the set of possible meta-paths is infinite. Here, the k potential predictors are those of length less than or equal to 4. This is motivated by the test performed in the previous subsection. In addition, the semantics of longer paths are less clear than shorter paths.

Results are reported in Table <ref>. The final model thus obtained contains five predictors related to meta-paths whose length are no longer than 3 and no intercept. This regression model accounts for 71.29% of the variance. To comfort the goodness of fit of the model, we plot in Fig. <ref> the density plot in log-log scale of the predicted probabilities versus the observed ones in the data. The green line represents the ideal case where predicted probabilities match observed ones. Most of the data points fall to this line which reinforces the use of a linear model.





The best improvement with respect to r^2 comes with the addition of the second variable (see Mod. 2 of Table <ref>). 
The model with two predictors is actually a local extremum since the model with the best r^2 is the one with RT-UH and RP-UH predictors (see Table <ref>). Although the difference is tenuous, this allows to point two weaknesses of the method: there is no guarantee of finding the best model and the order of the variable selection is important.
Note that the first two variables are part of the most direct relationships (meta-paths of length 2) which is intuitive: the direct neighborhood of a user shares common topics with her.
The last meta path included in the model (Mod. 5) provokes an important change in the other coefficients. This suggests this meta-path is either correlated to other meta-paths already present in the model or the presence of outliers i.e., 
observation which is “distant” from other observations. It is well known that ordinary least squares method is sensitive to that.

Forward Linear Regression for Data Recovery.
We validate the method by performing a task aiming to recover the weights of missing links. 
In other words, this part tries to answer to the question: is it possible to know, in a quantitative way, the way some people post some hashtags, knowing the way other people do ? 

We perform Monte Carlo cross-validation with 80% of the users as the training set and obtain the vector  for them. Then, we use it on the testing set i.e. the remaining 20% and compute the r^2 associated to each model. We proceed to ten splits i.e., we create ten training sets. 
The final models do not include the same variables as before. Not surprisingly, it depends on the 80% selected. The number of predictors is five or six. 
Nevertheless, whatever the training set, the meta-path MT-UH is always the first predictor to be selected. After, there is no more consensus on the second regressor but the RP-UH and RT-RP-UH always compete for the second place. Again, it is not surprising to obtain the RP-UH meta-path since, for a user, it is related to one of the closest neighbors with respect to our graph construction and very weakly correlated to the MT-UH meta-path already present in the model.
Although the best r^2 scores of the final models reach, on average, 0.7 for the training sets, we only get, on average, a best score of 0.5 for the test sets (Fig. <ref>). The method seems to reach a limit. One also observes that even if a model better fits the training set, it does not mean that it will give the best recovery. Indeed, it is sometimes better to consider a model with fewer regressors, and so a lower r^2 for training set, to better recover. 




 



 §.§ Bibliographic data.



Bibliographic networks are also good examples of heterogeneous information networks since they contain multiple types of nodes and links. We here focus on scientific publications.



  §.§.§ Data Set Description and Setup.

Fig. <ref> illustrates an example of such networks where one can distinguish four types of nodes that is authors, papers, venues and topics; and four types of links (eight when we differentiate a type from its inverse) that is write, publish, cite and belong to.



The HIN we analyse in this article is constructed from DBLP publications <cit.>.
The data set contains 95,855 authors with 1,537,407 co-author relationships and 186,175 papers with 1,356,893 citation relationships.
The papers belong to nine distinct topics: Artificial Intelligence, Computer Graphic: multimedia, Computer Networks, Database: Data Mining: Information Retrieval, Human Computer Interaction: Ubiquitous Computing, Information Security, Interdisciplinary Studies, Software Engineering and Theoretical Computer Science. These topics are represented in the 92 venues present in the data set. 

The presented method is used to find out if the co-author relationship A→P←A is correlated with other directly extractable relationships of the underlying graph. 
Table <ref> shows the different meta-paths used in the models selected according to their semantics contrary to the previous experiment. 
Since there is only one directed type of links between two given types of nodes, we only mention the types of nodes to describe the meta-path. 




distinct of the targeted authors


As mentioned, meta-paths are no longer determined by their length but selected by a more solid prior knowledge of the data.
Here are given some motivations about the selected meta-paths.



  * A→P→A←P→A means that two authors have written with a third common author. It represents a triangle when the AP-PA graph is projected onto A. This meta-path is the most “social”;

  * A→P→P←A and A→P←P←A state for the interest of a person (say a) for the work of another (say b). It could be meaningful to think that if a is interested in b's work and cites it, a is eager to communicate with b and even to collaborate and to publish with her. The same holds if a and b exchange their role;

  * A→P→P←P←A means that two authors cite the same paper and are thus inspired by the same ideas. This could be a good reason for a co-author relation;

  * A→P←P→P←A is quite different since it states that a third person (say c) cites the work of a et b but it does not mean that a and b work on the same thing. So, we expect this meta-path to be less significant that the previous one, albeit the structure is fairly close;

  * A→P→V←P←A and A→P→T←P←A mean that a's paper and b's paper are in the same venue or belong to the same topic respectively. Even if some venues can gather a lot of people, being accepted in the same venue might trigger collaborations. Plus, working on the same topic can also be a source of collaboration. 
 

 
Starting from the data, we construct four matrices associated to four bipartite graphs. 
In particular, AP where AP_ap equals 1 when authors a writes paper p, 0 otherwise. PP where PP_pq equals 1 when paper p cites paper q, 0 otherwise. PV where PV_pv equals 1 when paper p is published/presented in conference/venue v, 0 otherwise. PT where PT_pt equals 1 when paper p belongs to topic t, 0 otherwise. 
These matrices are binary but it does not imply the co-author matrix (AA) is binary too.
In order to compute the proposed variables/meta-paths, matrices are transformed into row-stochastic matrices i.e., normalized such that the sum of each line equals 1. In this setting, we can consider these matrices as transition matrices and perform random walks on it. 
For Fig. <ref>, we have the following matrices:




AP = 
[   1   0   0   0   0; 1/2 1/2   0   0   0; 1/2   0 1/2   0   0;   0 1/3 1/3 1/3   0;   0   0 1/2 1/2   0;   0   0   0   0   1 ]
   
PV = 
[ 1 0 0; 1 0 0; 1 0 0; 0 1 0; 0 0 1 ] 
 

PP = 
[   0 1/2 1/2   0   0;   0   0   1   0   0;   0   0   0   0   1;   0   0   1   0   0;   0   0   0   0   1 ]   PT = 
[ 1 0 0 0; 1 0 0 0; 0 1 0 0; 0 0 1 0; 0 0 0 1 ]





where the red entries (last columns and rows of each matrix) are related to the so-called hole nodes (see Sec. <ref>). Remark that paper p_3 points to the hole node in the PP graph since it does not cite any paper.

Furthermore, note that for meta-paths of the form A→P→ “node type” ←P←A with “node type” in {P, V, T}, one forbids the walker to return to the same paper in his second and fourth step. 
It prevents us from using what we are looking for.
For instance, in Fig. <ref>, a walker constrained by the A→P→A←P←A meta-path and having travelled through the path a_1 → p_1 → a_3 cannot return on p_1 at her next step but has to go to p_3.



  §.§.§ Results.


As said, the aim of this experiment is to express the distribution of co-author relationship of all the authors in the data set by a combination of other distributions. The results are once again divided into explanatory and recovery tasks.

Forward Liner Regression for Data Description.
Two tests are performed: first, we consider all the presented meta-paths as regressors (Table <ref>) and second, we aggregate some meta-paths a.k.a. features (see third column of Table <ref>) and utilize them into the algorithm (Table <ref>). 
We propose this aggregation because if the direction of the arrows is neglected, the meta-paths composing a feature are the same. In other words, the sequence of the node types is the same. The aim is to quantify the quality loss (if any) of the prediction when aggregating meta-paths into features.

Meta-paths as regressors.
For the first test, we see that only three meta-paths are retained into the final model. This latter is able to explained 66,61% of the variance
in the dependent variable from the independent variables. According to this model, the most significant meta-paths to explained the co-author relationship are related to the way authors share the same co-authors (some kind of transitivity[Transitivity of the authors-authors graph equals 0.6948.]), cite and co-cite, plus the venues in which papers are published/presented. Meta-path related to “topic” is not included in the model.




Features as regressors.
When we aggregated some meta-paths into features, those related to citing the same paper and the venues are not included in the model (see Table <ref>). For the first one, it could be explained by the fact that only one meta-path (A→P→P←P←A) among two is imported in the first test[Of course, the same remark can be made for the v_PP meta-paths and yet, v_PP is part of the model.]. 

No immediate reason is given for the absence of v_V variable. 
Plus, this second model only accounts for 59.97% of the variance: each meta-path brings its own meaning and even if some of them seem close to each other, wanting to aggregate them is not beneficial for our purpose. Actually, we have already mentioned a “fundamental” difference between variables of v_PPP.
As in the previous case, feature related to “topic” is not significant for the specific objective when other variables (see Table <ref>) are considered in the forward linear regression.



Topics under scrutiny.
The small number of considered topics, compared with the number of papers, could partly explain why the topic meta-path is not taken into account. Indeed, only one topic is assigned to each paper so the meta-path P→T→P generate a dense “paper-paper matrix”[The same comment could be made for meta-path P→V→P since the number of venues is also limited - although to a lesser extent since a topic encompasses several venues. The number of non zero entries of the matrix APTPA (not really the same as PTP but the final result is encompassed in APTPA) equals 6,515,232 while for APVPA, this number raises to 3,940,634, which is still 1.6 times lower.] and when computing the matrix product  
A→P→T←P←A, any relevant information is somewhat lost.

Thus we think the meta-path A→P→T←P←A brings a too diffuse information. However, the idea of considering topics is not meaningless since an author interested in a topic is often interested for a while and therefore, has the time to collaborate with other people, who are themselves interested in the same subject. Authors writing about a same topic might partly be co-authors.  





So, we split the data into nine subsets, each one related to one topic, and apply the method with the six meta-paths cited above i.e., all except A→P→T←P←A (see Remark <ref>). Results are reported in Table <ref>. 
On average, we have a better descriptive model than before: ⟨ r^2 ⟩ = 0.6970 (and σ= 0.0710). 
This could mean that inside some topics, there are some patterns more homogeneous or frequent and we are more capable of explaining them.
However, for Artificial Intelligence and Theoretical Computer Science, it is harder to find a model that fits the data well.

In Fig. <ref> are reported the final models' coefficient values for the different topics.
Meta-path A→P→A←P←A is selected by each topic: sharing the same co-author is the most useful to explain co-author relationship in a given topic. 
Meta-path A→P→V←P←A is important for 7 topics out of 9. Only Computer Networks and Theoretical Computer Science do not take it into account. 
Note that only Theoretical Computer Science includes A→P←P→P←A in its final model. This topic is also the only one for which A→P→A←P←A has not the greatest coefficient, it is surpassed by A→P→P←A and closely followed by A→P→P←P←A. The paper relations seem highly important for this domain. 

Forward Linear Regression for Data Recovery.
We are now interested in the recovery of link weights. Average results Monte-Carlo cross-validations are reported in Table <ref>. All p-values associated to the regressors are below the fixed threshold α=0.05.



For Database, Human Computer Interaction and Interdisciplinary Studies, the recovery is somehow achievable in the sense that the score of the test set is almost as good as for the training set. For the other domains, the quality loss is more significant, even for Information Security and Software Engineering which have a good r^2 for the training set. 
Finally, note that for Theoretical Computer Sciences, the r^2 for recovery is really low and its true relevance can be somewhat even questioned (albeit the p-values are below 0.05). 
However, to be sure of its relevance, the results computed from our data set are compared with a null hypothesis model that preserve some properties of the network topology (e.g. degree distributions) but randomly reshuffles the links among the nodes. 
The aim is to show that degree distributions only are not enough to generate such a correlation in the data and that this correlation arises from the particular data or at least, from more involved topological properties. Indeed, results for such null models are not significant (no regressor with p-value smaller than 0.12) and the average score ⟨ r^2 ⟩ over 15 generations of null graphs are at most equal to 0.26.





§ RELATED WORK



Compared to previous work, which usually focuses on undirected binary 
graphs, the approach we present addresses the recovery of 
directed and weighted links in HIN. To this end, our 
regression model directly estimates the weight of links without 
computing any intermediate ranking on these links, or applying any 
threshold to reduce the recovery task to binary graphs.

As previously explained, our work is based on node similarity measures and thus, is also related to link prediction. 
Similarity measures and link prediction have been extensively studied in the past few years.
One often roughly differentiates two kinds of approaches: unsupervised versus supervised.
For the first category, one often proposes different similarity measures based upon either node attributes or the topology of the underlying graph. One can further distinguish local from global indices. Local indices makes use of local neighborhood information e.g. Adamic-Adar index, Common Neighbor or Preferential Attachment Index, Ressource Allocation just to name a few. By contrast, global indices are based on global properties such as paths. These encompass Shortest Path, Katz or measures using random walks e.g. Random Walk with Restart, PageRank, Hitting Time, Commute Time and so on.   
Based on these aforementioned features, a plethora of supervised methods have been conceived to predict links. Amongst them, one distinguishes feature-based classification <cit.> from probabilistic model <cit.> and matrix factorization <cit.>. 
However, all these measures are mostly used in homogeneous networks and for a review of these methods, see <cit.>.

Recently, several measures have tackled the problem of node similarity in HIN which takes into account not only the structure similarity of two entities but also the metapaths connecting them. Amongst these measures, PathCount (PC<cit.>) and Path Constrained Random Walk (PCRW<cit.>) are the two most basic and gave birth to several extensions <cit.>.

Methods related to PC are based on the count of paths between a pair of nodes, given a meta path. PathSim <cit.> measures the similarity between two objects of same type along a symmetric meta path which is restrictive since many valuable paths are asymmetric and
the relatedness between entities of different types is not useless. Two measures based on it <cit.> incorporate more information such as the node degree and the transitivity. However, all these methods have the drawback of favoring highly connected objects since they deal with raw data.
 
Methods related to PCRW are based on random walks and so the probability of reaching a node from another one, given a meta path. Considering a random walk implies a normalisation and, depending on the data, offers better results. 
An adaptation, HeteSim <cit.>, measures the meeting probability between two walkers starting from opposite extremities of a path, given a meta path. However, this method requires the decomposition of atomic relations for odd-length meta-paths. This decomposition allows the walkers to meet at the middle of the meta-path and at the same node type but it is very costly for large graphs. 
To address this issue, AvgSim <cit.> computes the similarity between two nodes using random walks conditioned by a meta path and its inverse. But it is mostly appreciated in undirected networks since in these cases, it is just as sensible to walk a path in one direction as in the other.

In these cited works, when the similarity scores are used for link prediction/detection, the scores are ranked and then, the presence of links is inferred based on this ranking. 
Also some work try to combine meta-paths but the target values to recover are binary; the networks are unweighted. 
At variance with these works, we set ourselves in the general framework of directed and weighted HINs. We do not use any ranking or threshold but take directly the similarity measures obtained by means of an adequate combination of PCRWs as link weights. This allows not only to perform description tasks but also, to some extent, recovery tasks.




§ CONCLUSION



We have considered a linear combination of probability distributions resulting from path-constrained random walks to explain, to some extent, a specific relation in heterogeneous information networks. 
This proposed method allows to express the weight of a link between two nodes knowing some other links in a graph. 
This could be useful for prediction or recommendation tasks.
In particular, we have shown by working on Twitter data, that the hashtags posted by a specific user is mainly related to those posted by her direct neighborhood, especially the mention and reply neighborhood. This method has also shown that the retweet relation is not really useful for our purpose.
Then we have shown the applicability of the method to bibliographic data in order to recover the co-author relationship. It has been found that (data separated into) some topics are more suited to our method and so, the functioning of co-authors seemed to differ from one topic to another.  

Nevertheless, the main drawback of the method is its sensitivity to outliers. Hence, more robust least square alternatives could be envisaged such that Least Trimmed Squares or parametric alternatives.

Furthermore when there is no prior knowledge about the data, as for the Twitter data experiment, we had to provide all the meta-paths whose length is no longer than four. Even if it has been motivated by previous tests, this threshold is clearly data related. Hence, it could be interesting to build a method able to find relevant meta-paths by itself.

Finally, all data have been aggregated in time. Consequently, the chronology of the events is ignored. Since it is possible to extract the time stamp of tweets or to take into account the papers' publication date, a future work could be the integration of time by defining a random walk process on temporal graphs <cit.> or by counting the temporal paths <cit.> (plus normalisation). The walker can thus only follow time-respecting paths which can perhaps improve the quality of the model.



§ ACKNOWLEDGEMENTS


This work is funded in part by the European Commission H2020 FETPROACT 
2016-2017 program under grant 732942 (ODYCCEUS)


plain


