# Relative Entropy-Based Similarity for Patterns in Graph Data

Authors: Shihu Liu; Li Deng; Haiyan Gao; Xueyu Ma
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

How to make a correct similarity between patterns is a groundwork in data mining, especially for graph data. Despite these methods that can obtain great results, there may be still some limitations, for instance, the similarity of patterns in directed weighted graph data. Here, we introduce a new approach by taking the so-called the second-order neighbors into consideration. The proposed new similarity approach is named as relative entropy-based similarity for patterns in graph data, wherein the relative entropy provides a brand new aspect to make the difference between patterns in directed weighted graph data. The proposed similarity measure can be partitioned under three phases. First of all, strength set is given by degree and weight of patterns; in this phase, four variables holding the strength about out-degree, in-degree, out-weight, and in-weight are constructed. Then, with the help of Euclidean metric, pattern’s probability set is constructed, which contains influence of similarity between pattern and its all one-order neighbors. Finally, relative entropy is used to measure the difference between patterns. In order to examine the validity of our approach as well as its advantage comparing with the state-of-art approach, two sorts of experiments are suggested for real-world and synthetic graph data. The outcomes of experiment indicate that the recommended method get handy execution done measuring similarity and gain accurate results.


---

## Body

## 1. Introduction

At present, many practical networks like Facebook social networks, protein interaction networks, aviation networks, and disease transmission networks can be presented as graph data. This type of data is no longer a straightforward portrayal of pattern’s attribute information and composes possible topological information between patterns additionally, i.e., degree and weight of patterns. Due to the extensive use of graph data, many practical problems including pattern analysis, link prediction, and community detection can be abstracted into problems of graph data for research. Among these researches, how to calculate similarity between patterns in graph data is considered as one of the fundamental problems. Many researches on graph data are based on the pattern’s similarity measure, for example, traffic networks [1], image classification [2], and pattern recognition [3, 4].Over the past few decades, discovering similarity between patterns has attracted substantial consideration [5, 6]. Scholars proposed a range of methods to measure pattern’s similarity, for example, shared neighbor-based similarity, random walk-based similarity, path-based similarity, and information theory-based similarity; these methods discuss the similarity of patterns from different perspective.The shared neighbor-based similarity measure takes into account the shared information of the connected neighbors between patterns, and the greater the coincidence rate of shared neighbors means the higher similarity of two patterns. Cosine index [7], Sorensen index [8], Jaccard index [9], AA (Adamic-Adar) index [10], and WAA (weighted Adamic-Adar) index [11] are also common methods used in the research of similarity measure, which take into account the number of shared neighbors. Besides, LP (local path) [12] index is an improvement of CN index [13]; on the basis of CN index, the influence of neighbor with path length of 3 on the connection between patterns is added. These indicators reduce the computation time and earn good results in the identification of the most similar patterns. Unfortunately, they remain significant challenges, only topological information of first-order neighbors is taken into account, and many patterns with high similarity have no common neighbors, which leads to certain limitations of such indicators.Random walk-based similarity is widely used to measure the topological similarity of patterns, such as MLRW (Multiplex Local Random Walk) index [14], BRW (Biased Random Walk) index [15], and LRW (Local Random Walk) index [16]. In the process of calculation, these two methods measure similarity moving from one to other patterns through multistep random walk without the global information of graph data. They simplify the similarity measure to some extent, but these three similarity measures rely on large-degree patterns and most similar patterns may be large-degree patterns, which makes the similarity results sensitive to large pattern dependence.Path-based similarity is an important method used to measure similarity of patterns, Katz index [17, 18] and ACT (average commute time) [19]. Compared with local index, global index requires the overall topological information. Besides, Aziz et al. in [20] proposed global and quasilocal extensions of some commonly used local similarity index. Although global index provides more accurate similarity than local index, the computation of global metrics is time-consuming and generally not applicable to large-scale graph data, and sometimes, global topology information is unavailable, especially when implemented in a decentralized manner.In addition to the similarity measures mentioned above, information theory-based similarity is a kind of similarity measure that is often used. Hereinto, relative entropy is an important concept of information theory, which are used to measure similarity of patterns. Scholars have proposed pattern similarity measure based on relative entropy such as LRE (i.e., the abbreviation of local relative entropy) [21, 22], LRWE-SNM (Local Network Relative Weighted Entropy Based Similar Node Mining) [23], and RE-model (relative entropy model) [24]. These methods have advantages in their respective fields and can also measure the similarity of patterns to a certain extent. Although it is faster and simpler to measure, some pattern’s information and complex relationships between patterns are lost, for example, information about second-order neighbors of patterns. That is to say, it is hard to distinguish differences between patterns with similar degree. In addition, there are many other ways to calculate pattern similarity, see [25–28] for details.For the similarity of patterns in directed weighted graph data, similarity is affected by the direction of the edge and edges in different directions have an impact on its weight. Besides, each pattern has information such as out-degree and in-degree, out-weight, and in-weight, and the relationship between the pattern and its neighbors in different scales is complex. Therefore, the similarity measure of patterns in directed weighted graph data cannot start from a single direction. Generally speaking, the above measure of similarity has been used extensively. Nonetheless, there are still some inevitable limitations. These index that used mutual information are limited to the common neighbor structure or local information of patterns; so, it is easy to make the patterns of larger degree become the general patterns in the similarity calculation. Even if existing submethods simplify the measure of topological information, they ignore the directivity of the pattern’s connection and its corresponding degree and weight diversity of the relationship between patterns. Under the circumstances, some edge information of pattern is lost, leading to their performance for calculating the similarity of patterns failing to get further enhancement. In particular, there may be a poor effect when the above indices are applied to ink prediction. To sum up, calculating similarity of patterns from the aspects of degree and weight diversity is still a hotspot [29–31].In this paper, we aim at similarity of pattern in directed weighted graph data. To this, an extended version of the similarity measure approach from a relative entropy point of view is proposed. For more details, the comprehensive process can be considered as three stages. First, compute strength set. By using degree and weight of pattern’s information in its first-order neighbors, four variables that contain the influence of topological information about degree and weight diversity are constructed. Second, generate probability set. To take advantage of the second-order neighbor information of patterns, Euclidean metric is presented to measure the similarity between pattern and its first-order neighbors. On this basis, the value of similarity is normalized to construct probability set of each pattern. Third, Quantify similarity of pattern. With the help of relative entropy, the dissimilarity of any two patterns is measured, and similarity can be gained subsequently. We numerically simulated the proposed similarity measure and verified its effectiveness and efficiency in similarity measure and link prediction. In this paper, there is a proposed relative entropy-based similarity for patterns in graph data with the following several contributions in mind.(1)
This paper presents a similarity measure based on relative entropy, which considers the information of second-order neighbors of patterns(2)
In the process of pattern’s similarity measure, the proposed method considers both degree information and weight information(3)
Compared with most benchmark methods, the proposed similarity measure has a great advantage in measuring similarity of patterns and gets good performance the link predictionTo make a detailed description of the above proposed similarity approach, in this section, we will provide a brief introduction to the structure of this paper. Section2 contains some preliminaries. Section 3 describes generation of strength set for patterns in detail. Section 4 proposes probability set calculated by similarity set. Section 5 constructs a measure to compute the similarity of pattern in graph data, and a novel algorithm is proposed. Section 6 carries out two type experiments to prove the effectiveness of the proposed method. Conclusion is given in section 7.


## 2. Preliminaries

In this section, we propose some basic concepts used in this paper, such as graph data [26], relative entropy [32], and pattern’s neighbor [23].


### 2.1. Graph Data

A graph dataG is defined as a set of patterns and a set of edges. Generally speaking, the so-named directed weighted graph data can be expressed as a 4-tuple G=V,E,D,W, formally, where
(i)
V=vii=1,2,⋯,n is the set of patterns, and vi∈V represents the ith pattern(ii)
E=eiji,j=1,2,⋯,n is the set of edges, and eij∈E indicates the set of edges. Hereinto, eij=1 if pattern vi and vj are connected; otherwise, eij=0(iii)
D=dvi,d+vi,d−vii=1,2,⋯,n is the set of corresponding weight with respect to patterns, thereinto d+vi and d−vi represent in-degree and out-degree of vi∈V, respectively, and the value of them, take vi for example, can be determined by equations
(1)d+vi=∑j=1neji,d−vi=∑j=1neji.Moreover, the degreedvi can be calculated by the sum of in-degree and out-degree, i.e.,
(2)dvi=d+vi+d−vi=∑j=1neij+eji.(iv)
W=wvi,w+vi,w−vii=1,2,⋯,n is the set of weights with respect to the corresponding edges. Analogously, wvi,w+vi,w−vi represent the weight, in-weight, and out-weight of pattern vi, respectively. The value of in-weight and out-weight can be determined by following equations:
(3)w+vi=∑j=1nwji,w−vi=∑i=1nwij,Thereinto, wij represents weight on edge of vi and vj. Furthermore, the value of weight can be calculated by the sum of in-weight and out-weighted, i.e.,
(4)wvi=w+vi+w−vi=∑j=1nwij+wji.


### 2.2. Relative Entropy

As we known, relative entropy is an asymmetric measure and can be applied to measure the difference between two probability distributions. In general, its mathematical version can be expressed as(5)DKLPQ=∑i=1mPilnPiQi,where P and Q are two probability distributions, and “m” in equation (5) represents the number of variables that P and Q depended on. Certainly, the greater value of DKLPQ reflects the smaller similarity of P and Q, and vice versa.


### 2.3. Pattern’s Neighbor

For a graph dataG=V,E,D,W, if there exists at least two patterns vi and vj such as eij≠0 or eji≠0. Then, one can say that vi is the neighbor of vj, and vice versa. All the neighbors of vi constitute the so-named neighborhood with respect of vj, in aspect of topological information. For the need of simplicity and uniformity, we summarize it as the following definition.Definition 1. (first-order neighborhood).
Given thatG=V,E,D,W is a directed weighted graph data, if eij≠0 or eji≠0 for j=1,2,⋯,n, then the pattern vj is a first-order neighbor of vi. Certainly, all of the neighbors of vi constitute the first-order neighborhood of it and can be expressed as
(6)Nvi=vjeij≠0oreji≠0.
Generally speaking, if patternvi has pfirst neighbors, then Nvi can be represented as Nvi=vi1,vi2,⋯,vip. Obviously, the elements of Nvi reflect the topological information of vi directly. For the case that eij≠0 and ejk≠0 but eik=0, how to depict the direct relationship of vi and vk in aspect of topological information is no longer an obvious question. To this, next definition gives the concept of second-order neighborhood to depict such situation.Definition 2. (second-order neighborhood).
Given thatG=V,E,D,W is a graph data and vi∈V, the second-order neighborhood of a pattern vi denoted as the set contained neighbors of its all first-order neighbors, which notes as Nvi,2, which can be expressed as
(7)Nvi,2=Nvi1,Nvi2,⋯,Nvip.Definition 3. (local neighborhood).
Given thatG=V,E,D,W is a graph data and vi∈V, the so-named local neighborhood of vi can be expressed as
(8)Lvi=vi∪Nvi=vi,vi1,⋯,vip,where vik∈Nvi is the kth first order neighbor of vi, for k=1,2,⋯,p.


## 2.1. Graph Data

A graph dataG is defined as a set of patterns and a set of edges. Generally speaking, the so-named directed weighted graph data can be expressed as a 4-tuple G=V,E,D,W, formally, where
(i)
V=vii=1,2,⋯,n is the set of patterns, and vi∈V represents the ith pattern(ii)
E=eiji,j=1,2,⋯,n is the set of edges, and eij∈E indicates the set of edges. Hereinto, eij=1 if pattern vi and vj are connected; otherwise, eij=0(iii)
D=dvi,d+vi,d−vii=1,2,⋯,n is the set of corresponding weight with respect to patterns, thereinto d+vi and d−vi represent in-degree and out-degree of vi∈V, respectively, and the value of them, take vi for example, can be determined by equations
(1)d+vi=∑j=1neji,d−vi=∑j=1neji.Moreover, the degreedvi can be calculated by the sum of in-degree and out-degree, i.e.,
(2)dvi=d+vi+d−vi=∑j=1neij+eji.(iv)
W=wvi,w+vi,w−vii=1,2,⋯,n is the set of weights with respect to the corresponding edges. Analogously, wvi,w+vi,w−vi represent the weight, in-weight, and out-weight of pattern vi, respectively. The value of in-weight and out-weight can be determined by following equations:
(3)w+vi=∑j=1nwji,w−vi=∑i=1nwij,Thereinto, wij represents weight on edge of vi and vj. Furthermore, the value of weight can be calculated by the sum of in-weight and out-weighted, i.e.,
(4)wvi=w+vi+w−vi=∑j=1nwij+wji.


## 2.2. Relative Entropy

As we known, relative entropy is an asymmetric measure and can be applied to measure the difference between two probability distributions. In general, its mathematical version can be expressed as(5)DKLPQ=∑i=1mPilnPiQi,where P and Q are two probability distributions, and “m” in equation (5) represents the number of variables that P and Q depended on. Certainly, the greater value of DKLPQ reflects the smaller similarity of P and Q, and vice versa.


## 2.3. Pattern’s Neighbor

For a graph dataG=V,E,D,W, if there exists at least two patterns vi and vj such as eij≠0 or eji≠0. Then, one can say that vi is the neighbor of vj, and vice versa. All the neighbors of vi constitute the so-named neighborhood with respect of vj, in aspect of topological information. For the need of simplicity and uniformity, we summarize it as the following definition.Definition 1. (first-order neighborhood).
Given thatG=V,E,D,W is a directed weighted graph data, if eij≠0 or eji≠0 for j=1,2,⋯,n, then the pattern vj is a first-order neighbor of vi. Certainly, all of the neighbors of vi constitute the first-order neighborhood of it and can be expressed as
(6)Nvi=vjeij≠0oreji≠0.
Generally speaking, if patternvi has pfirst neighbors, then Nvi can be represented as Nvi=vi1,vi2,⋯,vip. Obviously, the elements of Nvi reflect the topological information of vi directly. For the case that eij≠0 and ejk≠0 but eik=0, how to depict the direct relationship of vi and vk in aspect of topological information is no longer an obvious question. To this, next definition gives the concept of second-order neighborhood to depict such situation.Definition 2. (second-order neighborhood).
Given thatG=V,E,D,W is a graph data and vi∈V, the second-order neighborhood of a pattern vi denoted as the set contained neighbors of its all first-order neighbors, which notes as Nvi,2, which can be expressed as
(7)Nvi,2=Nvi1,Nvi2,⋯,Nvip.Definition 3. (local neighborhood).
Given thatG=V,E,D,W is a graph data and vi∈V, the so-named local neighborhood of vi can be expressed as
(8)Lvi=vi∪Nvi=vi,vi1,⋯,vip,where vik∈Nvi is the kth first order neighbor of vi, for k=1,2,⋯,p.


## 3. Degree and Weight-Based Pattern’s Strength Set

In this section, we investigate the problem of how to construct the pattern’s strength set in terms of degree and weight.For any patternvi in G=V,E,D,W, its first order neighborhood Nvi depends on the corresponding topological connection. Whatever the connection, the topological information for each pattern can be described by four variables: in-degree d+vi, out-degree d−vi, in-weight w+vi, and out-weight w−vi.In what follows, we introduce the concept of strength set for any patternvi in a graph data G.Definition 4. (strength set).
Given thatG=V,E,D,W is a graph data, for any pattern vi∈G, its strength set Uvi can be expressed by following equation:
(9)Uvi=uvi,uvi1,,uvi2,,⋯,uvip,where k=1,2,⋯,p and p=Nvi. Each variable in Uvi contains four strength values consisting of in-degree, out-degree, in-weight, and out-weight, take vi for example, uvi=ud+vi,ud−vi,uw+vi,uw−vi, in which case
(i)
ud−vi represents the strength of out-degree and can be computed by equation
(10)ud−vi=d−vidvi⋅d−vi∑i=1nd−vi+1.(ii)
ud+vi represents the strength of in-degree and can be computed by equation
(11)ud+vi=d+vidvi⋅d+vi∑i=1nd+vi+1.(iii)
uw−vi represents the strength of out-weight and can be computed by equation
(12)uw−vi=w−viwvi⋅w−vi∑i=1nw−vi+1.(iv)
uw+vi represents the strength of in-weight and can be computed by equation
(13)ww+vi=w+viwvi⋅w+vi∑i=1nw+vi+1.Analogously,uvik represents the strength of kth first-order neighbor to vi, which can be calculated by equations mentioned above. One can find that the above proposed strength fully depicts personal properties and topological information with respect to corresponding its first-order neighbors.As discussed above, takevi and vj for example, if vi and vj are two different patterns, then Nvi≠Nvj is nothing unusual to some extent. In particular, there would be one extreme situation that Nvi≠Nvj if vi≠vj, for i,j=1,2,⋯,n and i≠j.By making a deeper investigation of relative entropy, one can see that the patterns with more neighbors will lose certain information, for it only calculates the value of nonzero elements in probability set, and the information of nonzero elements in the probability set of its corresponding patterns will also be lost. Considering this deficiency, we introduce a concept, the scale of strength set, to depict the strength set. Before doing this, we suppose that for a graph dataG, there exists at least one pattern vi that having the most neighbors, in which we denote the number of it as np=maxvi∈VNvi. To this, for the pattern vi with Nvi=p1 and pattern vj with Nvj=p2, we take the following cases into consideration:Case 1.
Ifp1=p2=p=np, then the Uvi and Uvj can be represented as
(14)Unewvi=uvi,uvi1,uvi2,⋯,uvip,Unewvj=uvj,uvj1,uvj2,⋯,uvjp.Case 2.
Ifp1=p2=p<np, then the Uvi and Uvj can be changed into
(15)Unewvi=uvi,uvi1,uvi2,⋯,uvip,0,0,⋯,0⏞np−p,Unewvj=uvj,uvj1,rvj2,⋯,uvjp,0,0,⋯,0⏞np−p.In other words, appendnp−p zeros, i.e., 0=0,0,0,0 to the end of Uvi and Uvj.Case 3.
Ifp1<p2<np, we append p2−p1 average strength values uvi∗ of vi to the end of Uvi by the equation
(16)uvi∗=uvi1+uvi2+⋯+uvip1p1.Generally speaking, theUvi and Uvj can be changed into
(17)Unewvi=uvi,uvi1,uvi2,⋯,uvip1,uvi∗,⋯,uvi∗⏞p2−p1,0,0,⋯,0⏞np−p2,Unewvj=uvj,uvj1,uvj2,⋯,uvjp2,0,0,⋯,0⏞np−p2,where the insufficient p2−p1 locations of Uvi will be appended by strength values uvi∗ calculated with the help of equation (16), and the rest location of Uvi and Uvj will be appended by p−p2 zeros, i.e., 0=0,0,0,0.Case 4.
Ifp2<p1<np, the Uvi and Uvj can be changed into
(18)Unewvj=uvj,uvj1,uvj2,⋯,uvjp2,uvj∗,⋯,uvj∗⏞p1−p2,0,0,⋯,0⏞np−p1,Unewvi=uvi,uvi1,uvi2,⋯,uvip2,0,0,⋯,0⏞np−p1,where strength value uvj∗ of vj can be calculated as the following equation:
(19)uvj∗=uvj1+uvj2+⋯+uvjp2p2.


## 4. Generating Probability Set

Relative entropy is applied to compare the difference of two probability set. To some extent, the similarity can be regarded as the difference. For this, we try to calculate the similarity between patterns in aspect of relative entropy. Before do this, how to construct the probability set of each patternvi∈G constitutes the first step of similarity measure.We have known that the strength setUvi, take vi for example, and its one order-neighbors can be determined in terms of degree and weight. To make full use of relative entropy for the purpose of similarity measure, in what follows, we construct an approach to generate the probability set of patterns vi∈V for i=1,2,⋯,n. Each strength value of the j first-order neighbors is composed by four variables; here, the Euclid metric can be applied to compute the similarity between vi and vj∈Nvi for j=1,2,⋯,p with respect to its strength set. The concrete formula can be depicted as the following equation:
(20)svi,vij=<uvi,uvij>.Obviously, the valuesvi,vij describes the similarity between vi and its jth first-order neighbor, and it is only a local description in view point of Nvi. With the help of equation (20), we can make a global description of the similarity of pattern vi by the following equation:
(21)Svi=svi,vi1,svi,vi2,⋯,svi,vip.Up to now, the caring thing, that is, creating probability set, can be realized by the following equation:(22)Pvi=pvi,vi1,pvi,vi2,⋯,pvi,vip,where
(23)pvi,vij=svi,vij∑k=1psvi,vik.By above aforementioned, the relative entropy between the probability setPvi and Pvj, take vi,vj in G for example, it can be determined by the equation
(24)DKLPviPvj=∑k=1m′pvi,viklnpvi,vikpvj,vjk,where m′ represents the maximal neighbors of patterns vi and vj; that is, m′=maxNvi,Nvj.It can be analyzed that, in the process of calculating relative value of patternvi and vj, strength set of first-order neighbors of pattern vi and vj is constructed, which contain second-order neighbor information. That is to say, with the help of Euclidean metric, the information of pattern’s second-order neighbors is indirectly used during similarity calculation process.


## 5. Similarity and Algorithm

The calculation of relative entropy among the patterns has been discussed in detail. In this section, the calculated value of relative entropy will be used to compute the similarity between patterns. And then, an algorithm is proposed.


### 5.1. Quantify Similarity of Pattern

From the process mentioned above, relative entropy of any two patterns is obtained based on the sorted probability sets. Therefore, the relative entropy matrixR of graph data with respect to any two patterns can be represented as
(25)R=r11r12⋯r1nr21r22⋯r2n⋮⋮⋱⋮rn1rn2⋯rnn.And then, the similarity matrixS of graph data G can be given as follows.
(26)S=s11s12⋯s1ns21s22⋯s2n⋮⋮⋱⋮sn1sn2⋯snn.For the value of relative entropy is asymmetric, takevi and vj for example, both DKLPviPvj and DKLPvjPvi describe dissimilarity of pattern vi and vj. To obtain more accurate similarity of pattern, the value of relative entropy can be calculated by taking both DKLPviPvj and DKLPvjPvi into consideration, and the specific calculations of it are shown as follows:
(27)sij=1−rijmaxR,(28)rij=DKLPviPvj+DKLPvjPvi2.


### 5.2. Algorithm

With the purpose of a better understanding for the proposed pattern similarity measure, this section will give an algorithm containing detailed description of this similarity measure. Notice that for briefness, “Relative entropy-based similarity for patterns in graph data” can be summarized as “RESG.” In terms of this algorithm, the similarity of any two patterns will be computed, after which the most similar patterns can be obtained. One can easily see that there are four states of this algorithm. The input of the RESG algorithm is a weighted directed graph dataG, and the output is a matrix S composed of similarity between any two patterns in G.Algorithm 1: Relative entropy-based similarity for patterns in graph data.
Input: A directed weighted graph data G.Output: Similarity matrix S of patterns in G.1:for each vi∈Gdo2: Calculate first-order neighborsLvi3: CalculateUvi by equation (10)- (13)4:end5:for each vi∈G with p1 neighbors and vj∈G with p2 neighbors do6:ifp1>p2then7:p1−p2uvj∗⟶Uvj8:else9:p2−p1uvi∗⟶Uvi10:end11:end12:forvi∈V,vij∈Lvido13: ComputeSvi by equation (20) and (21)14: ComputePvi by equation (22)15:end16:for each vi,vj∈Gdo17: ComputeDKLPviPvj by equation (24)18: Compute entropy matrixR by equation (25)19: Compute similarity matrixsij by equation (27)20:end21:return Similarity matrix SThe first state of the RESG algorithm is lines 1-4, strength setU of each pattern in G is generated, and each strength set has four variables in terms of in-degree, out-degree, in-weight, and out-weight. The second state is lines 5-11, to fully utilize information of pattern’s first-order neighbors, the pattern with less neighbors will append average strength value in the end of strength set. The third state of the RESG algorithm is lines 12-15, the similarity between patterns and its one-order will be computed, and similarity set is generated. With the help of similarity set, pattern’s probability set will be obtained. It is not hard to find; during the process of generating similarity set, the information of pattern’s second-order neighbors will be used indirectly. The last state is lines 16-20; by taking the above information into account, the relative entropy and similarity of patterns are measured.


## 5.1. Quantify Similarity of Pattern

From the process mentioned above, relative entropy of any two patterns is obtained based on the sorted probability sets. Therefore, the relative entropy matrixR of graph data with respect to any two patterns can be represented as
(25)R=r11r12⋯r1nr21r22⋯r2n⋮⋮⋱⋮rn1rn2⋯rnn.And then, the similarity matrixS of graph data G can be given as follows.
(26)S=s11s12⋯s1ns21s22⋯s2n⋮⋮⋱⋮sn1sn2⋯snn.For the value of relative entropy is asymmetric, takevi and vj for example, both DKLPviPvj and DKLPvjPvi describe dissimilarity of pattern vi and vj. To obtain more accurate similarity of pattern, the value of relative entropy can be calculated by taking both DKLPviPvj and DKLPvjPvi into consideration, and the specific calculations of it are shown as follows:
(27)sij=1−rijmaxR,(28)rij=DKLPviPvj+DKLPvjPvi2.


## 5.2. Algorithm

With the purpose of a better understanding for the proposed pattern similarity measure, this section will give an algorithm containing detailed description of this similarity measure. Notice that for briefness, “Relative entropy-based similarity for patterns in graph data” can be summarized as “RESG.” In terms of this algorithm, the similarity of any two patterns will be computed, after which the most similar patterns can be obtained. One can easily see that there are four states of this algorithm. The input of the RESG algorithm is a weighted directed graph dataG, and the output is a matrix S composed of similarity between any two patterns in G.Algorithm 1: Relative entropy-based similarity for patterns in graph data.
Input: A directed weighted graph data G.Output: Similarity matrix S of patterns in G.1:for each vi∈Gdo2: Calculate first-order neighborsLvi3: CalculateUvi by equation (10)- (13)4:end5:for each vi∈G with p1 neighbors and vj∈G with p2 neighbors do6:ifp1>p2then7:p1−p2uvj∗⟶Uvj8:else9:p2−p1uvi∗⟶Uvi10:end11:end12:forvi∈V,vij∈Lvido13: ComputeSvi by equation (20) and (21)14: ComputePvi by equation (22)15:end16:for each vi,vj∈Gdo17: ComputeDKLPviPvj by equation (24)18: Compute entropy matrixR by equation (25)19: Compute similarity matrixsij by equation (27)20:end21:return Similarity matrix SThe first state of the RESG algorithm is lines 1-4, strength setU of each pattern in G is generated, and each strength set has four variables in terms of in-degree, out-degree, in-weight, and out-weight. The second state is lines 5-11, to fully utilize information of pattern’s first-order neighbors, the pattern with less neighbors will append average strength value in the end of strength set. The third state of the RESG algorithm is lines 12-15, the similarity between patterns and its one-order will be computed, and similarity set is generated. With the help of similarity set, pattern’s probability set will be obtained. It is not hard to find; during the process of generating similarity set, the information of pattern’s second-order neighbors will be used indirectly. The last state is lines 16-20; by taking the above information into account, the relative entropy and similarity of patterns are measured.


## 6. Experimental Materials

In this section, we introduce some experimental materials such as experimental environment, the graph data used in experiment, and benchmark algorithms. The experimental environment we used is listed in Table1.Table 1
Experimental environment.
ParameterParameter valueRAM16 GBSpeed2.10 GHzProgrammingMATLAB 2018aCPUAMD Ryzen 54600 UGUPAMD Radeon GraphicsSystemWindows 10 system with 8 cores


### 6.1. Data

This subsection will give a detailed description about the directed weighted graph data used in experiments.A synthetic graph dataDatal generated by means of the graph generator Gephi will be applied in first experiment. Datal contains 21 patterns and 31 edges and can be used to illustrate the feasibility of the proposed RESG algorithm in the following illustrative example.The following is a detailed description of graph data used in second experiment.Data2 and Gene [33] will be used to demonstrate the similarity of our proposed RESG index and other similarity measures. For the edge connections of Data 2 and Gene [33], see Figures 1 and 2 for detail. Stmarks, FWEW, FWMW,FWFW, Celegans, and Email167 are directed weighted graph data collected from Stanford Dataset. Each of them will be used to show the effectiveness of the proposed RESG algorithm in link prediction. The topology information of these eight graph data are shown in Table 2, where n is the number of patterns, m is the number of edges, d is the average shortest distance, ρ is the density, k is the average degree, and c is the clustering coefficient.Figure 1
Data2.Figure 2
Gene.Table 2
Topological properties of graph data.
Graph datanmdρkcData229723586.00000.049214.50000.3092Gene63639594.00000.022612.00000.5701Stmarks543503.00000.244612.96300.4128EW698803.00000.375125.50720.5521FWMW9714463.00000.310629.91440.4683FWFW12820753.00000.254032.41290.3364Celegans29721482.45500.048914.46460.3079Email16716732505.00000.234538.92220.6864


### 6.2. Benchmark Algorithms

Here, we introduce several benchmark pattern’s similarity indices, which are usually used for similarity measure and link prediction. Adamic-Adar (AA) [10], weighted Adamic-Adar (WAA) [11], local relative entropy (LRE) [21], common neighbors (CN) [13], Katz [17], local path (LP) [12], and Local Random Walk (LRW) [16] are often used for the purpose of comparing results with the RESG algorithm. The basic definitions of these indexes are given below.AA index is the extended version ofCN index, which is defined as
(29)sijAA=∑vz∈Nvi∩Nvj1logdvk.WAA index is the weighted version of AA index, which is defined as(30)sijWAA=∑vz∈Nvi∩Nvjwvi+wvjlog1+a,where a may be smaller than 1; so, we use log1+a to avoid a negative value.CN index directly takes the number of all common neighbors between patterns as similarity into consideration, which is defined as(31)sijCN=Nvi∩Nvj.LRE index is a similarity measure based on relative entropy and local structure of patterns, which is defined as(32)sijLRE=1−DKLPiPj+DKLPjPimDKLPiPj+DKLPjPi,whereinto
(33)DKLPiPj=∑k=1ΔGpiklnpikpjk,pik=dvi∑vk∈Nvidvk,k≤dvi,0,dvi+1≤k≤ΔG.Hereinto,ΔG is the maximum degree of the graph data, and G,Pi is the probability set of pattern vi with respect to degree.Katz index is based on the global information of graph data, which is defined as(34)sijKatz=∑k=1∞⋅βl⋅pathsij<l>,where pathsij<l> represents the set of all paths with distance l between pattern vi and vj,β is the damping factor used to control the path weight.LP index considers the third-order paths on the basis of common neighbors, which is defined as(35)sijLP=A2+αA3,where A is the adjacency matrix of graph data [34], A3ij represents the number of paths with length of 3 between patterns vi and vj, and α is adjustable parameter.LRW index is proposed based on the local random walk of particles between two patterns, which is defined as(36)sijLRW=dvi2⋅E⋅πijt+dvj2⋅E⋅πjit,where E is the number of the edges in the graph data, πijt is obtained according to the density vector evolution equation: π⟶it+1=PT⋅π⟶it, the P is the transition probability matrix, and T is the matrix transpose.


## 6.1. Data

This subsection will give a detailed description about the directed weighted graph data used in experiments.A synthetic graph dataDatal generated by means of the graph generator Gephi will be applied in first experiment. Datal contains 21 patterns and 31 edges and can be used to illustrate the feasibility of the proposed RESG algorithm in the following illustrative example.The following is a detailed description of graph data used in second experiment.Data2 and Gene [33] will be used to demonstrate the similarity of our proposed RESG index and other similarity measures. For the edge connections of Data 2 and Gene [33], see Figures 1 and 2 for detail. Stmarks, FWEW, FWMW,FWFW, Celegans, and Email167 are directed weighted graph data collected from Stanford Dataset. Each of them will be used to show the effectiveness of the proposed RESG algorithm in link prediction. The topology information of these eight graph data are shown in Table 2, where n is the number of patterns, m is the number of edges, d is the average shortest distance, ρ is the density, k is the average degree, and c is the clustering coefficient.Figure 1
Data2.Figure 2
Gene.Table 2
Topological properties of graph data.
Graph datanmdρkcData229723586.00000.049214.50000.3092Gene63639594.00000.022612.00000.5701Stmarks543503.00000.244612.96300.4128EW698803.00000.375125.50720.5521FWMW9714463.00000.310629.91440.4683FWFW12820753.00000.254032.41290.3364Celegans29721482.45500.048914.46460.3079Email16716732505.00000.234538.92220.6864


## 6.2. Benchmark Algorithms

Here, we introduce several benchmark pattern’s similarity indices, which are usually used for similarity measure and link prediction. Adamic-Adar (AA) [10], weighted Adamic-Adar (WAA) [11], local relative entropy (LRE) [21], common neighbors (CN) [13], Katz [17], local path (LP) [12], and Local Random Walk (LRW) [16] are often used for the purpose of comparing results with the RESG algorithm. The basic definitions of these indexes are given below.AA index is the extended version ofCN index, which is defined as
(29)sijAA=∑vz∈Nvi∩Nvj1logdvk.WAA index is the weighted version of AA index, which is defined as(30)sijWAA=∑vz∈Nvi∩Nvjwvi+wvjlog1+a,where a may be smaller than 1; so, we use log1+a to avoid a negative value.CN index directly takes the number of all common neighbors between patterns as similarity into consideration, which is defined as(31)sijCN=Nvi∩Nvj.LRE index is a similarity measure based on relative entropy and local structure of patterns, which is defined as(32)sijLRE=1−DKLPiPj+DKLPjPimDKLPiPj+DKLPjPi,whereinto
(33)DKLPiPj=∑k=1ΔGpiklnpikpjk,pik=dvi∑vk∈Nvidvk,k≤dvi,0,dvi+1≤k≤ΔG.Hereinto,ΔG is the maximum degree of the graph data, and G,Pi is the probability set of pattern vi with respect to degree.Katz index is based on the global information of graph data, which is defined as(34)sijKatz=∑k=1∞⋅βl⋅pathsij<l>,where pathsij<l> represents the set of all paths with distance l between pattern vi and vj,β is the damping factor used to control the path weight.LP index considers the third-order paths on the basis of common neighbors, which is defined as(35)sijLP=A2+αA3,where A is the adjacency matrix of graph data [34], A3ij represents the number of paths with length of 3 between patterns vi and vj, and α is adjustable parameter.LRW index is proposed based on the local random walk of particles between two patterns, which is defined as(36)sijLRW=dvi2⋅E⋅πijt+dvj2⋅E⋅πjit,where E is the number of the edges in the graph data, πijt is obtained according to the density vector evolution equation: π⟶it+1=PT⋅π⟶it, the P is the transition probability matrix, and T is the matrix transpose.


## 7. Experimental Analysis

In this section, we evaluated the proposed RESG index into different real-world graph data, and two different forms of experiments are used to demonstrate experimental results, which aims to further prove the effectiveness and efficiency of proposed RESG index.


### 7.1. Illustrative Example

Data1 is used to illustrate the proposed RESG index, for the edge connections of Data1, see Figure 3 for detail. Taking pattern v15 and v10 for example, in terms of RESG index, next, we deal with the problem of pattern similarity step by step.Figure 3
Data1.Firstly, we find pattern’s first-order neighbors of them, respectively, and put them inLvi, and relevant strength value about topological information ud−,ud+,uw−,uw+of v15 and v10 is calculated and shown in Tables 3 and 4, respectively. However, it can be easily found that d15=5 and d10=4. Based on this, a pattern v0 with the average value of v10 for ud−,ud+,uw− and uw+ is added as the one-neighbor of v10. After that, the neighbors of the two patterns reached the same number, which avoided the partial information loss of v15 in the subsequent calculation of relative entropy.Table 3
TheLvi and Uvi of pattern v15.
Serial numberkoutkinwoutwinukoutukinuwoutuwinv15235100.07270.18000.05560.2564v1220500.18180.00000.16670.0000v1311230.04550.05000.02670.0692v17130120.27270.00000.03330.0000v1813260.02270.22500.06670.1731v2112360.03030.13330.03330.1538Table 4
TheLvi and Uvi of pattern v10.
Serial numberkoutkinwoutwinukoutukinuwoutuwinv1013180.03130.25000.00560.4183v412240.04170.14810.03330.1569v621510.16670.03700.20830.0098v1420600.25000.00000.30000.0000v2012530.04170.14810.15630.0662v00.10630.11660.14070.1302Secondly, the similarity sets are generated in the process of calculating the similarity between patterns and its first-order neighbors, and the details ofSv15 and Sv10 are shown as
(37)Sv15=0.5115,0.2313,0.7248,0.1860,0.1225,(38)Sv10=0.2821,0.5212,0.6099,0.3965,0.3533.The details of probability set based on strength set ofv15 and v10 can be calculated and arranged each element in descending order, which can be shown as
(39)Pv15=0.4801,0.2880,0.1302,0.1047,0.0690,Pv10=0.2820,0.2410,0.1833,0.1633,0.1304.Then, with the help of equation (24), the relative entropy r10,15 of pattern v15 and v10 can be computed as follows.
(40)r10,15=DKLPv15Pv10+DKLPv10Pv152=0.0986.Finally, by computing pattern’s similarity of the graph dataG, the maximum value of pattern similarity can be found from Figure 4; in terms of equation (25), similarity of v15 and v10 is 0.8901. Obviously, the similarity calculation process of v15 and v10 can help better understand RESG index. The details of relevance matrix of graph data G are shown in Figure 4, and the most similar pattern in G is shown in Table 5.Figure 4
The relevance value and similarity ofG.Table 5
The most similar pattern of each pattern inG.
PatternMost similar patternPatternMost similar patternPatternMost similar patternv1v6v8v21v15v5v2v6v9v12v16v13v3v13v10v7v17v21v4v3v11v16v18v7v5v15v12v10v19v21v6v1v13v3v20v21v7v18v14v16v21v20According to Figure3, we can find that compared with patterns v10,v5 and v15, they have more similar topological structures. Depending on Table 5, the most similar pattern of v15 is exactly identified as pattern v5. Illustrative example given shows that RESG index is simple, efficient, and reliable with highly satisfactory accuracy.


### 7.2. Result Analysis

To further illustrate the efficiency of the proposed RESG algorithm in measuring pattern’s similarity, this subsection gives comparative experiments with serval proposed similarity measures. In order to make a detailed description of experimental results, two ways are given. The first way of comparative experiment is to show the experimental results through scatter plots and table of the most similar pattern. The second way is to demonstrate the effectiveness by applying the RESG to link prediction.The scatter plot reflects the distribution of similarity between patterns. For example, if the most similar pattern ofv1 is v12, then there exists draw points on 1,12 in plane. There is a good similarity measure, whose scatter plot is dispersed on the plane, rather than concentrated on both sides of diagonal. The reason is that if the points are concentrated on both sides of the diagonal line, it shows that this method is easier to identify its neighbors as most similar patterns, which is not accurate enough. In the following, under Data2 and Gene, the scatter plots of the proposed RESG index and other seven similarity indices are used to further validate the performance of similarity measure, which are vividly shown in Figures 5 and 6, respectively.Figure 5
The scatter plots underData2.
(a)
AA(b)
WAA(c)
CN(d)
LRE(e)
Katz(f)
LRW(g)
LP(h)
RESGFigure 6
The scatter plots underGene.
(a)
AA(b)
WAA(c)
CN(d)
LRE(e)
Katz(f)
LRW(g)
LP(h)
RESGFigures5(a), 6(a), 5(b), 6(b), 5(c), and 6(c) show scatter plots formed by AA index, WAA index, and CN index, respectively. As we can see, the most similar patterns are concentrated near to diagonal. There is no denying that these three indices are low computational complexity; nevertheless, it uses very limited information. Generally speaking, similarity is determined by the number of common neighbors between patterns. Accordingly, the most similar patterns are distributed near the corresponding patterns. Although the symmetry of patterns is good, it is difficult to accurately describe the similarity between patterns when only one path is considered.Figures5(d) and 6(d) show scatter plots formed by LRE, respectively. It can be found that the most similar patterns are not distributed near to diagonal nevertheless. From overall view, LRE takes information of the local structure into consideration, and it remains a daunting challenge on obtaining accurate similarity value. In addition, with the size of graph data increasing, the symmetry between patterns decreases significantly.Figures5(e) and 6(e) show scatter plots formed by Katz. It is worth noting that the adjustable parameter of Katz index is set to α=0.001, whereby the scatter plot under Katz index is concentrated around the diagonal line. Furthermore, the symmetry is not desirable. Katz index relies more on path among patterns in graph data, and patterns with larger degree are more likely to be in the path between different patterns; so, there is a greater probability that most patterns are similar to the patterns with greater degree in graph data.Figures5(f) and 6(f) show scatter plots formed by LRW index, and the number of random walks in this experiment is set to 3. One can see that the scatter plots are unevenly distributed, and the accuracy of similarity obtained by this similarity measure needs to be further improved. Moreover, LRW index considers the random walk with finite number of steps, and the computational complexity of this measure is higher.The scatter plots of LP index are vividly showed in Figures5(g) and 6(g). The advantage of LP index is low computational complexity. However, due to the limited information used, the distribution of similarity values is too concentrated, which makes distinguishable similarity between patterns.Figures5(h) and 6(h) show scatter plots formed by RESG index, respectively. As we can see that the most similar pattern is not distributed near to diagonal, and with the size of graph data increasing, the scatter plot formed RESG index still maintains good symmetry. RESG index measures the similarity between patterns using influence of pattern degree and weight and takes the information of first-order neighbors and second-order neighbors of patterns into account, which can get more accurate similarity of any two patterns. Under the circumstances, most patterns avoid becoming general patterns and avoid being identified as certain patterns with common structure that are most similar to multiple patterns. Moreover, in terms of runtime, RESG index is higher to LRW index, CN index, and AA index. However, compared with the same type of relative entropy-based similarity LRE index, the running time of RESG index is only 1/4 of it. In addition, comparing with the normal algorithm, RESG index is simple and efficient and can satisfy measure the similarity of patterns in large graph data efficiently.For a different method, a quantification named most similar pattern listed in Table6 is used to demonstrate the difference between RESG index and three existing measures: LRE index, CN index, and EI index [35], so as to verify the good effect of RESG index from another perspective. The first line of Table 6 is the pattern’s label, three of every 100 patterns are selected randomly, and a total of 20 will be used as experimental patterns listed. “/” represents that the pattern does not have the most similar pattern. Since there is such a situation that pattern in graph data has more than one of the most similar patterns, only the same pattern sequence numbers are listed, and the rest of most similar patterns are shown in the table with abbreviation numbers. Take pattern v5 under the EI index for example, (148) represents pattern v5 which has 148 most similar patterns.Table 6
The most similar pattern inGene.
PatternRESGLREEICNv5v76v76148(15)v52v32v76/v6v81v127v85/v6v104v376v557148/v157v9v126//v172v156v76/2v201v129v76./v172v2532v25172v297v192v557148/v314v578v52018/v348v324v346148v340v397v480v251//v429v87v4341487v459v193v76/v457v498v181v76/v592v518v100v5577/v552v482v76//v590v100v154148/v616v241v483//v636v459v181148v631As it shows in Table6, pattern v7 is identified as the most similar pattern of 7 different patterns under LRE index, including pattern v5,v52,v172. LRE index takes the degree of patterns into consideration simply; so, it is possible that most patterns may have the same degree distribution, which leads to the same similarity of patterns. Analogously, under the EI index, several patterns have more than one most similar pattern. For example, a number of 148 most similar patterns are identified by patterns v5,v104,v297 and so on. However, there are also patterns without the most similar pattern, for instance, patterns v52,v81.As we can see, there is no situation that multiple patterns identify the same most similar patterns under RESG index. RESG index takes information of pattern’s one-order and second-order neighbors into account, which can accurately calculate the similarity. Meanwhile, the weight of patterns also contains a lot of topological information, and there may be a situation that the degree distribution is the same but the weight is different. RESG index starts from the perspective of degree and weight, which may make it exact to distinguish the similarity. As a result, RESG index is feasible and effective.To further verify the feasibility of the proposed similarity measure, RESG index is applied to link prediction and compared the prediction performance with CN index, LP index, Katz index, and LRW index. The experiment is carried out on six graph data collected from Stanford Dataset, and AUC is selected as an index to evaluate the prediction performance of effective path topology stability. For the more information of AUC, see reference [34] for details.Figure7 shows the comparison of AUC results on RESG and other four similarity measures. Among them, CN index only considers the degree information of patterns, LRW index, LP index, and Katz index either consider the local path or the global path of graph data; so, their time complexity is relatively high. As we can see from Figure 7, compared with RESG index and LRW index, the AUC value of CN index, LP index, and Katz value on Stmarks and FWEW is not ideal. However, compared with RESG index, LRW index has higher time complexity. The AUC of RESG index is the highest on four graph data: FWMW, FWFW, Celegans, and Email167, second only to LRW index on Stmarks and FWEW. Meanwhile, compared with the AUC of other four measures, the improvement rate can reach 2%−21%. The experiment suggests that RESG index can achieve the highest AUC value in four graph data; to some extent, it shows the effectiveness and feasibility of RESG index.Figure 7
The AUC comparison of each index on six graph data.However, it deserves our attention that the proposed RESG index also has limitations, and it can achieve better link prediction effect on graph data with small clustering coefficients. For graph data with large clustering coefficient, the effect of this measure needs to be further improved and optimized.


## 7.1. Illustrative Example

Data1 is used to illustrate the proposed RESG index, for the edge connections of Data1, see Figure 3 for detail. Taking pattern v15 and v10 for example, in terms of RESG index, next, we deal with the problem of pattern similarity step by step.Figure 3
Data1.Firstly, we find pattern’s first-order neighbors of them, respectively, and put them inLvi, and relevant strength value about topological information ud−,ud+,uw−,uw+of v15 and v10 is calculated and shown in Tables 3 and 4, respectively. However, it can be easily found that d15=5 and d10=4. Based on this, a pattern v0 with the average value of v10 for ud−,ud+,uw− and uw+ is added as the one-neighbor of v10. After that, the neighbors of the two patterns reached the same number, which avoided the partial information loss of v15 in the subsequent calculation of relative entropy.Table 3
TheLvi and Uvi of pattern v15.
Serial numberkoutkinwoutwinukoutukinuwoutuwinv15235100.07270.18000.05560.2564v1220500.18180.00000.16670.0000v1311230.04550.05000.02670.0692v17130120.27270.00000.03330.0000v1813260.02270.22500.06670.1731v2112360.03030.13330.03330.1538Table 4
TheLvi and Uvi of pattern v10.
Serial numberkoutkinwoutwinukoutukinuwoutuwinv1013180.03130.25000.00560.4183v412240.04170.14810.03330.1569v621510.16670.03700.20830.0098v1420600.25000.00000.30000.0000v2012530.04170.14810.15630.0662v00.10630.11660.14070.1302Secondly, the similarity sets are generated in the process of calculating the similarity between patterns and its first-order neighbors, and the details ofSv15 and Sv10 are shown as
(37)Sv15=0.5115,0.2313,0.7248,0.1860,0.1225,(38)Sv10=0.2821,0.5212,0.6099,0.3965,0.3533.The details of probability set based on strength set ofv15 and v10 can be calculated and arranged each element in descending order, which can be shown as
(39)Pv15=0.4801,0.2880,0.1302,0.1047,0.0690,Pv10=0.2820,0.2410,0.1833,0.1633,0.1304.Then, with the help of equation (24), the relative entropy r10,15 of pattern v15 and v10 can be computed as follows.
(40)r10,15=DKLPv15Pv10+DKLPv10Pv152=0.0986.Finally, by computing pattern’s similarity of the graph dataG, the maximum value of pattern similarity can be found from Figure 4; in terms of equation (25), similarity of v15 and v10 is 0.8901. Obviously, the similarity calculation process of v15 and v10 can help better understand RESG index. The details of relevance matrix of graph data G are shown in Figure 4, and the most similar pattern in G is shown in Table 5.Figure 4
The relevance value and similarity ofG.Table 5
The most similar pattern of each pattern inG.
PatternMost similar patternPatternMost similar patternPatternMost similar patternv1v6v8v21v15v5v2v6v9v12v16v13v3v13v10v7v17v21v4v3v11v16v18v7v5v15v12v10v19v21v6v1v13v3v20v21v7v18v14v16v21v20According to Figure3, we can find that compared with patterns v10,v5 and v15, they have more similar topological structures. Depending on Table 5, the most similar pattern of v15 is exactly identified as pattern v5. Illustrative example given shows that RESG index is simple, efficient, and reliable with highly satisfactory accuracy.


## 7.2. Result Analysis

To further illustrate the efficiency of the proposed RESG algorithm in measuring pattern’s similarity, this subsection gives comparative experiments with serval proposed similarity measures. In order to make a detailed description of experimental results, two ways are given. The first way of comparative experiment is to show the experimental results through scatter plots and table of the most similar pattern. The second way is to demonstrate the effectiveness by applying the RESG to link prediction.The scatter plot reflects the distribution of similarity between patterns. For example, if the most similar pattern ofv1 is v12, then there exists draw points on 1,12 in plane. There is a good similarity measure, whose scatter plot is dispersed on the plane, rather than concentrated on both sides of diagonal. The reason is that if the points are concentrated on both sides of the diagonal line, it shows that this method is easier to identify its neighbors as most similar patterns, which is not accurate enough. In the following, under Data2 and Gene, the scatter plots of the proposed RESG index and other seven similarity indices are used to further validate the performance of similarity measure, which are vividly shown in Figures 5 and 6, respectively.Figure 5
The scatter plots underData2.
(a)
AA(b)
WAA(c)
CN(d)
LRE(e)
Katz(f)
LRW(g)
LP(h)
RESGFigure 6
The scatter plots underGene.
(a)
AA(b)
WAA(c)
CN(d)
LRE(e)
Katz(f)
LRW(g)
LP(h)
RESGFigures5(a), 6(a), 5(b), 6(b), 5(c), and 6(c) show scatter plots formed by AA index, WAA index, and CN index, respectively. As we can see, the most similar patterns are concentrated near to diagonal. There is no denying that these three indices are low computational complexity; nevertheless, it uses very limited information. Generally speaking, similarity is determined by the number of common neighbors between patterns. Accordingly, the most similar patterns are distributed near the corresponding patterns. Although the symmetry of patterns is good, it is difficult to accurately describe the similarity between patterns when only one path is considered.Figures5(d) and 6(d) show scatter plots formed by LRE, respectively. It can be found that the most similar patterns are not distributed near to diagonal nevertheless. From overall view, LRE takes information of the local structure into consideration, and it remains a daunting challenge on obtaining accurate similarity value. In addition, with the size of graph data increasing, the symmetry between patterns decreases significantly.Figures5(e) and 6(e) show scatter plots formed by Katz. It is worth noting that the adjustable parameter of Katz index is set to α=0.001, whereby the scatter plot under Katz index is concentrated around the diagonal line. Furthermore, the symmetry is not desirable. Katz index relies more on path among patterns in graph data, and patterns with larger degree are more likely to be in the path between different patterns; so, there is a greater probability that most patterns are similar to the patterns with greater degree in graph data.Figures5(f) and 6(f) show scatter plots formed by LRW index, and the number of random walks in this experiment is set to 3. One can see that the scatter plots are unevenly distributed, and the accuracy of similarity obtained by this similarity measure needs to be further improved. Moreover, LRW index considers the random walk with finite number of steps, and the computational complexity of this measure is higher.The scatter plots of LP index are vividly showed in Figures5(g) and 6(g). The advantage of LP index is low computational complexity. However, due to the limited information used, the distribution of similarity values is too concentrated, which makes distinguishable similarity between patterns.Figures5(h) and 6(h) show scatter plots formed by RESG index, respectively. As we can see that the most similar pattern is not distributed near to diagonal, and with the size of graph data increasing, the scatter plot formed RESG index still maintains good symmetry. RESG index measures the similarity between patterns using influence of pattern degree and weight and takes the information of first-order neighbors and second-order neighbors of patterns into account, which can get more accurate similarity of any two patterns. Under the circumstances, most patterns avoid becoming general patterns and avoid being identified as certain patterns with common structure that are most similar to multiple patterns. Moreover, in terms of runtime, RESG index is higher to LRW index, CN index, and AA index. However, compared with the same type of relative entropy-based similarity LRE index, the running time of RESG index is only 1/4 of it. In addition, comparing with the normal algorithm, RESG index is simple and efficient and can satisfy measure the similarity of patterns in large graph data efficiently.For a different method, a quantification named most similar pattern listed in Table6 is used to demonstrate the difference between RESG index and three existing measures: LRE index, CN index, and EI index [35], so as to verify the good effect of RESG index from another perspective. The first line of Table 6 is the pattern’s label, three of every 100 patterns are selected randomly, and a total of 20 will be used as experimental patterns listed. “/” represents that the pattern does not have the most similar pattern. Since there is such a situation that pattern in graph data has more than one of the most similar patterns, only the same pattern sequence numbers are listed, and the rest of most similar patterns are shown in the table with abbreviation numbers. Take pattern v5 under the EI index for example, (148) represents pattern v5 which has 148 most similar patterns.Table 6
The most similar pattern inGene.
PatternRESGLREEICNv5v76v76148(15)v52v32v76/v6v81v127v85/v6v104v376v557148/v157v9v126//v172v156v76/2v201v129v76./v172v2532v25172v297v192v557148/v314v578v52018/v348v324v346148v340v397v480v251//v429v87v4341487v459v193v76/v457v498v181v76/v592v518v100v5577/v552v482v76//v590v100v154148/v616v241v483//v636v459v181148v631As it shows in Table6, pattern v7 is identified as the most similar pattern of 7 different patterns under LRE index, including pattern v5,v52,v172. LRE index takes the degree of patterns into consideration simply; so, it is possible that most patterns may have the same degree distribution, which leads to the same similarity of patterns. Analogously, under the EI index, several patterns have more than one most similar pattern. For example, a number of 148 most similar patterns are identified by patterns v5,v104,v297 and so on. However, there are also patterns without the most similar pattern, for instance, patterns v52,v81.As we can see, there is no situation that multiple patterns identify the same most similar patterns under RESG index. RESG index takes information of pattern’s one-order and second-order neighbors into account, which can accurately calculate the similarity. Meanwhile, the weight of patterns also contains a lot of topological information, and there may be a situation that the degree distribution is the same but the weight is different. RESG index starts from the perspective of degree and weight, which may make it exact to distinguish the similarity. As a result, RESG index is feasible and effective.To further verify the feasibility of the proposed similarity measure, RESG index is applied to link prediction and compared the prediction performance with CN index, LP index, Katz index, and LRW index. The experiment is carried out on six graph data collected from Stanford Dataset, and AUC is selected as an index to evaluate the prediction performance of effective path topology stability. For the more information of AUC, see reference [34] for details.Figure7 shows the comparison of AUC results on RESG and other four similarity measures. Among them, CN index only considers the degree information of patterns, LRW index, LP index, and Katz index either consider the local path or the global path of graph data; so, their time complexity is relatively high. As we can see from Figure 7, compared with RESG index and LRW index, the AUC value of CN index, LP index, and Katz value on Stmarks and FWEW is not ideal. However, compared with RESG index, LRW index has higher time complexity. The AUC of RESG index is the highest on four graph data: FWMW, FWFW, Celegans, and Email167, second only to LRW index on Stmarks and FWEW. Meanwhile, compared with the AUC of other four measures, the improvement rate can reach 2%−21%. The experiment suggests that RESG index can achieve the highest AUC value in four graph data; to some extent, it shows the effectiveness and feasibility of RESG index.Figure 7
The AUC comparison of each index on six graph data.However, it deserves our attention that the proposed RESG index also has limitations, and it can achieve better link prediction effect on graph data with small clustering coefficients. For graph data with large clustering coefficient, the effect of this measure needs to be further improved and optimized.


## 8. Conclusion

Measuring similarity of patterns in graph data is a significant work in many fields. In this paper, to overcome the shortcomings and limitations of existing similarity measures, a relative entropy-based similarity for patterns in graph data abbreviated as RESG index is constructed. Our main work is divided into three aspects. Firstly, strength set is given by degree and weight, which proposed four variables that contains the information of topological relationship in first-order neighbors. Then, in order to generate probability set, patterns with smaller neighbors are redefined by appending empty neighbors up to the same neighbors as another. Finally, relative entropy is computed, and pattern’s similarity will be calculated. In addition, two sets of comparison experiments with serval classic similarity measure are used to show effectiveness and feasibility of the proposed RESG index algorithm. Experiments indicate that by taking pattern’s degree, weight and second-order neighbors into consideration, the RESG index algorithm can better identify similarity between patterns. To some extent, our purposed approach can enrich the research in area of pattern’s similarity in graph data.



---

*Source: 7490656-2022-07-26.xml*