# Graph-Based Node Finding in Big Complex Contextual Social Graphs

Authors: Keshou Wu; Guanfeng Liu; Junwen Lu
Journal: Complexity
 (2020)

---

## Abstract

Graph pattern matching is to find the subgraphs matching the given pattern graphs. In complex contextual social networks, considering the constraints of social contexts like the social relationships, the social trust, and the social positions, users are interested in the top-K matches of a specific node (denoted as the designated node) based on a pattern graph, rather than the entire set of graph matching. This inspires the conText-Aware Graph pattern-based top-K designated node matching (TAG-K) problem, which is NP-complete. Targeting this challenging problem, we propose a recurrent neural network- (RNN-) based Monte Carlo Tree Search algorithm (RN-MCTS), which automatically balances exploring new possible matches and extending existing matches. The RNN encodes the subgraph and maps it to a policy which is used to guide the MCTS. The experimental results demonstrate that our proposed algorithm outperforms the state-of-the-art methods in terms of both efficiency and effectiveness.


---

## Body

## 1. Introduction

Graph pattern matching (GPM) is widely used in many applications, like computer vision [1], chemical structure [2], and social networks [3–6]. Formally, given a pattern graph Q and a data graph G, GPM is to compute the set MQ,G of matches Q in G. Based on GPM, many applications focus on finding matches of a specific pattern (query) node, rather than the entire set of graph matching, for example, expert recommendation [7, 8] and egocentric search [9]. This leads to the top-K designated node matching (topKP) [10] problem, where given a designated node u0 in Q, it is to find the top-K matching nodes of u0 ranked by a quality function in G.In a social network, like crowd-sourcing travel [11] and social network based e-commerce [12], social queries often need to find matches of the topKP under requirements of social contexts, i.e., the social positions, the social trust, and the social relationships that have significant influence on collaborations and decision-making [13, 14]. For example, in the expert recommendation, people are more willing to find experts who can build the intimate relationships with team members. Example 1 discusses this scenario with a social network.Example 1.
A fraction of a collaboration network is given as graphG in Figure 1. Each node in G denotes a person, with attributes such as job title, e.g., project manager (PM), database developer (DB), programmer (PRG), and software tester (ST). Each edge indicates a supervision relationship; e.g., edge A1,D1 indicates that A1 supervised D1. The number added on the edge indicates the intimacy between the two persons. In order to simplify, in graph G, only the intimacy of corresponding edges of Q is given.
A company issues a graph search query to find the best PM inQ who supervises both PRG and DB, and moreover, (1) the DB worked under the PRG, and (2) the intimacy between the three persons must be larger than specific values in Q. It can be seen that, for the three PMs in G, i.e., A1, A2, and A3, only A2 does not meet the requirements. In addition, the intimacy among A3,B2,C2 is higher than A1,B1,C1; hence, A3 is the PM we would like to find.
This discussion above leads to the conText-Aware Graph pattern-based top-K designated node matching (TAG-K), which aims to find the topKP results under Multiconstrained Simulation (MCS) [12, 15]. There are multiple end-to-end constraints for the attributes. So the MCS becomes NP-complete, as it is exponential of the time complexity to find the best solution to investigate each combination of the different attributes. Therefore, TAG-K is NP-complete, as it subsumes the classical NP-complete multiconstrained path selection problem [12]. The existing topKP methods for the MCS problem [10, 16–19] need to enumerate all possible subgraphs that satisfy the constraints of social contexts, leading to the expensive time cost. In addition, even though these methods can find TAG-K results, once the problem statements change slightly (i.e., the value of social contexts), they need to be revised. Therefore, the existing methods are not applicable when dealing with the large-scale data graphs. In contrast, machine learning methods have the potential to be applicable across many optimization tasks by automatically discovering their own heuristics based on the training data, and they can get stable performance without adjusting the model in different social contexts.
While supervised learning is used widely in most successful machine learning methods, it is not applicable to the TAG-K problem because one does not have access to the optimal labels. However, we can compare the quality of subgraphs by using a verifier and provide some reward feedbacks to a learning algorithm. Hence, we follow the idea of Monte Carlo Tree Search (MCTS), which is an effective way of solving NP-complete problems [12, 20]. The key idea of MCTS is to construct a search tree of states (i.e., possible subgraphs) evaluated by fast Monte Carlo simulations [21]. Then, the state value is estimated as the mean outcome of the simulations. Meanwhile, a search tree is maintained to guide the direction of simulation, for which bandit algorithms can be employed to balance exploration and exploitation [22]. Then, after certain times of simulations, we can get TAG-K results based on the state values.
The problem poses a major challenge; since the state space of TAG-K is large, MCTS needs to traverse most subgraphs to get the accurate state values, which takes a lot of time. Inspired by the graph embedding technique, Hamilton and Ying [23] use neural networks to extract graph structural information and graph properties, which is an effective and efficient way to solve the graph analytic problem. In this paper, we utilize the characteristics of experience (i.e., vector representations of found matches) to train an RNN structure, which can evaluate the “potential” of the node to be the TAG-K result without traversing it. Our contributions are summarized as follows:(i)
We formulate TAG-K as the MCTS problem and design the neural network, which is trained by the subgraphs generated in the searching process to evaluate nodes inG(ii)
We propose the upper tree and the lower tree with optimal strategies to return TAG-K results without accessing all nodes inG(iii)
Using real social network datasets, we experimentally verify that our algorithm outperforms the existing methods in both efficiency and effectivenessFigure 1
Querying collaboration network: (a) pattern graphQ; (b) data graph G.


## 2. Related Work

### 2.1. Isomorphism-Based topKP

This type of the topKP is based on the subgraph isomorphism [24]. Tian and Patel [18] propose the concept of approximate subgraph matching, which allows node mismatches and node/edge insertions and deletions. For coping with approximate subgraph matching problem, an index-based method is presented in [18], called TALE. In addition, Ding et al. [16] define the matching similarity between a data graph and a query graph to order results. Built on NH-index in [18], Ding et al. [16] employ the index to prune unpromising candidate nodes for each query node. Furthermore, Zhu et al. [25] consider the entire structure matching rather than substructure matching and propose an algorithm to respond to the topKP similarity query using two distance lower bounds with different computational costs.


### 2.2. Simulation-Based topKP

Existing isomorphism-based topKP methods are still too strict to be used in some applications, e.g., finding social experts [26] and project organization [10]. Based on graph simulation [27], Fan et al. [10] propose a novel topKP method supporting a designated pattern node u0, which can find the topKP without computing the entire graph matching results. In addition, Chang et al. [28] study the problem of top-K tree pattern matching, where the edges in the tree are mapped to the shortest paths in G connecting the corresponding nodes and then proposed an optimal enumeration paradigm [28].However, the existing topKP methods do not consider the social contexts which are common in social network-based applications, like crowd-sourcing travel [11, 29, 30] and social network-based e-commerce [12]. Therefore, these methods cannot support the NP-complete TAG-K that exists in many real applications.Recently, based on [10], Lie et al. [31] propose an Monte Carlo-based approximation algorithm (MC-TAG-K) for TAG-K, which uses a random sampling method that cannot guarantee the algorithm performance, and MC-TAG-K has to traverse the data graph more than once, which costs a lot of time when the data graph is large; therefore, it is not a good solution to the TAG-K problem.


## 2.1. Isomorphism-Based topKP

This type of the topKP is based on the subgraph isomorphism [24]. Tian and Patel [18] propose the concept of approximate subgraph matching, which allows node mismatches and node/edge insertions and deletions. For coping with approximate subgraph matching problem, an index-based method is presented in [18], called TALE. In addition, Ding et al. [16] define the matching similarity between a data graph and a query graph to order results. Built on NH-index in [18], Ding et al. [16] employ the index to prune unpromising candidate nodes for each query node. Furthermore, Zhu et al. [25] consider the entire structure matching rather than substructure matching and propose an algorithm to respond to the topKP similarity query using two distance lower bounds with different computational costs.


## 2.2. Simulation-Based topKP

Existing isomorphism-based topKP methods are still too strict to be used in some applications, e.g., finding social experts [26] and project organization [10]. Based on graph simulation [27], Fan et al. [10] propose a novel topKP method supporting a designated pattern node u0, which can find the topKP without computing the entire graph matching results. In addition, Chang et al. [28] study the problem of top-K tree pattern matching, where the edges in the tree are mapped to the shortest paths in G connecting the corresponding nodes and then proposed an optimal enumeration paradigm [28].However, the existing topKP methods do not consider the social contexts which are common in social network-based applications, like crowd-sourcing travel [11, 29, 30] and social network-based e-commerce [12]. Therefore, these methods cannot support the NP-complete TAG-K that exists in many real applications.Recently, based on [10], Lie et al. [31] propose an Monte Carlo-based approximation algorithm (MC-TAG-K) for TAG-K, which uses a random sampling method that cannot guarantee the algorithm performance, and MC-TAG-K has to traverse the data graph more than once, which costs a lot of time when the data graph is large; therefore, it is not a good solution to the TAG-K problem.


## 3. Preliminaries

In this section, we first introduce the data graph, pattern graph, and multiconstrained simulation (MCS) [12] and then propose the ranking function and TAG-K problem.


### 3.1. Data Graph

A data graph is a contextual social graph (CSG).G=V,E,LG,ρ.(i)
V is the set of nodes of G, and each node represents the participant of a CSG.(ii)
E is the set of edges of G, and a direct edge e∈E from node v to node v′ is a quad v,v′,t,r, where v,v′∈V, t∈0,1, denotes the social trust between v and v′, r∈0,1 denotes the social intimacy degree between v and v′, the higher values of t and r, and the closer trust and social intimacy between the two participants.(iii)
LG is a function that assigns every node in V with the social role of a specific domain.(iv)
ρ is a function that assigns every node in V with a role impact factor, denoted as ρv∈0,1, which illustrates the impact of the participant in a specific domain. The greater the value of ρv, the more professional knowledge the participant v has t,r, and ρ are called social impact factors. For a path Pv1,vn=e1,e2,…,en−1 in G, where ei=vi,vi+1,ti,ri is the i-th edge in Pv1,vn. Based on the theories in Social Psychology [13], the aggregated social contexts of a path Pv,v′ are denoted as APv1,vn=AtPv1,vn,ArPv1,vn,AρPv1,vn, where (i)
AtPv1,vn=∏1n−1ti is the aggregated social trust of Pv1,vn(ii)
ArPv1,vn=∏1n−1ri is the aggregated social intimacy of Pv1,vn(iii)
AρPv1,vn=∑1nρvi/n is the aggregated role impact of Pv1,vnExample 2.
Figure1(b) shows the structure of a data graph, where we can find the labels and the intimacy relationships between two users.


### 3.2. Pattern Graph

A pattern graph is a directed graph.Q=VQ,EQ,LQ,λQ, where(i)
VQ is the set of nodes of Q(ii)
EQ is the set of edges of Q; u,u′∈EQ denotes the directed edge from u to u′, where u,u′∈VQ(iii)
LQ is a function that assigns every node in Q with a social role(iv)
λQ is a function that assigns every edge u,u′ with a quad l,λt,λr,λρ, where l is the bounded length of u,u′, which is a positive number, and λt, λr, and λρ in the range of 0,1 denote the multiple constraints of the aggregated social contextsExample 3.
Figure1(a) shows a pattern graph that contains three nodes and the corresponding edges. In each edge, we can find one of the constraints for social intimacy between nodes.


### 3.3. GPM-Based Multiconstrained Simulation (MCS)

A graphG=V,E,LG,ρ matches a pattern graph Q=VQ,EQ,LQ,λQ via MCS means there exists a binary relation S⊆VQ×V, where the following conditions apply:(i)
For each nodeu∈VQ, there exists a node v∈V such that u,v∈S(ii)
for each pair,u,v∈S(a)
LQu=LGv(b)
for each edgeu,u′∈EQ, there exists at least one path Pv,v′ (denoted as relevant path) v to v′ in G such that u′,v′∈S, Pv,v′≤lu,u′, Pv,v′ is the number of edges in Pv,v′, and the aggregated social contexts meet AtPv,v′≥λtu,u′, ArPv,v′≥λru,u′, and AρPv,v′≥λρu,u′It is known that ifG matches Q, then there exists a unique maximum relation set MQ,G=u1,v1,u2,v2,…,un,vn including all pairs in S.


### 3.4. Matches of Designated Node

Now we extend the pattern graph to beQ=VQ,EQ,LQ,λQ,u0, where u0 is the designated node in VQ. Then, the matches of u0 in G is defined as MUQ,G,u0=vu0,v∈MQ,G.


### 3.5. Ranking Function

#### 3.5.1. Relevant Set

Given a matchv of a designated node u0 in Q, the relevant node set of v with respect to u0 is denoted as Ru0,v, which includes all matches v′ of u′ for each descendant u′ of u0 in Q; i.e., if an edge u0,u′∈EQ, then v reaches v′ via a relevant path Pv,v′, where u′,v′∈MQ,G.That is,Ru0,v includes all matches v′ to which v can reach via a relevant path Pv,v′. Accordingly, we define relevant edge set REu0,v to save all relevant paths from v to all matches v′, and then for any match v of a query node u0, there exists unique, maximum relevant node set and relevant edge set.In the node matching, we need to consider the matching of nodes and the corresponding pattern. Based on [31], the ranking function to rank matches of the designated node u0 is defined as follows:(1)Fu0,v=2απarctanRu0,v+1−α∑Pi∈REu0,vUPiREu0,v,where α is used to balance the two functions; Ru0,v and REu0,v are the number of nodes and edges in Ru0,v and REu0,v, respectively; and UPi denotes the average social impact of Pi. In the complex social network, we have three social impact factors, i.e., trust, social intimacy, and social role impact,and they should be considered in the modelling of node matching. Therefore, we propose the following equation:(2)UP=wt×AtP+wr×ArP+wρ×AρP,where wt, wr, and wρ are the weights of social impact factors t, r, and ρ, respectively; wt,wr, and wρ are in the scope of 0,1 and wt + wr + wρ = 1.


### 3.6. TAG-K Problem

Definition 1.
Context-Aware Graph pattern based top-K designated node finding problem (TAG-K). Given a CSGG, a pattern graph Q with a designated node u0, a positive integer K, TAG-K is to find a subset D, where(3)D=argmaxD′∑vi∈D′Fu0,vi,where D′ is a subset of MUQ,G,u0 and D′=K. That is, TAG-K is to identify a set of K matches of u0, which maximizes the summation of ranking function F⋅, namely, ∀D′⊆MUQ,G,u0; if D′=K, then FD⩾FD′.
We denoteCu0 as the set of all the candidates v in G of u0 (i.e., v has the same label as u0) and use FLu0,v and FUu0,v to denote the lower bound and upper bound of Fu0,v, respectively, i.e., FLu0,v≤Fu0,v≤FUu0,v.Lemma 1.
For aK-element set D⊆Cu0, if (1) each v∈D is a match of u0 and (2) minv∈DFLu0,v≥maxv′∈Cu0\DFUu0,v′, then D is the TAG-K result.
Based on Lemma1, we can get TAG-K results without computing the entire MQ,G.


## 3.1. Data Graph

A data graph is a contextual social graph (CSG).G=V,E,LG,ρ.(i)
V is the set of nodes of G, and each node represents the participant of a CSG.(ii)
E is the set of edges of G, and a direct edge e∈E from node v to node v′ is a quad v,v′,t,r, where v,v′∈V, t∈0,1, denotes the social trust between v and v′, r∈0,1 denotes the social intimacy degree between v and v′, the higher values of t and r, and the closer trust and social intimacy between the two participants.(iii)
LG is a function that assigns every node in V with the social role of a specific domain.(iv)
ρ is a function that assigns every node in V with a role impact factor, denoted as ρv∈0,1, which illustrates the impact of the participant in a specific domain. The greater the value of ρv, the more professional knowledge the participant v has t,r, and ρ are called social impact factors. For a path Pv1,vn=e1,e2,…,en−1 in G, where ei=vi,vi+1,ti,ri is the i-th edge in Pv1,vn. Based on the theories in Social Psychology [13], the aggregated social contexts of a path Pv,v′ are denoted as APv1,vn=AtPv1,vn,ArPv1,vn,AρPv1,vn, where (i)
AtPv1,vn=∏1n−1ti is the aggregated social trust of Pv1,vn(ii)
ArPv1,vn=∏1n−1ri is the aggregated social intimacy of Pv1,vn(iii)
AρPv1,vn=∑1nρvi/n is the aggregated role impact of Pv1,vnExample 2.
Figure1(b) shows the structure of a data graph, where we can find the labels and the intimacy relationships between two users.


## 3.2. Pattern Graph

A pattern graph is a directed graph.Q=VQ,EQ,LQ,λQ, where(i)
VQ is the set of nodes of Q(ii)
EQ is the set of edges of Q; u,u′∈EQ denotes the directed edge from u to u′, where u,u′∈VQ(iii)
LQ is a function that assigns every node in Q with a social role(iv)
λQ is a function that assigns every edge u,u′ with a quad l,λt,λr,λρ, where l is the bounded length of u,u′, which is a positive number, and λt, λr, and λρ in the range of 0,1 denote the multiple constraints of the aggregated social contextsExample 3.
Figure1(a) shows a pattern graph that contains three nodes and the corresponding edges. In each edge, we can find one of the constraints for social intimacy between nodes.


## 3.3. GPM-Based Multiconstrained Simulation (MCS)

A graphG=V,E,LG,ρ matches a pattern graph Q=VQ,EQ,LQ,λQ via MCS means there exists a binary relation S⊆VQ×V, where the following conditions apply:(i)
For each nodeu∈VQ, there exists a node v∈V such that u,v∈S(ii)
for each pair,u,v∈S(a)
LQu=LGv(b)
for each edgeu,u′∈EQ, there exists at least one path Pv,v′ (denoted as relevant path) v to v′ in G such that u′,v′∈S, Pv,v′≤lu,u′, Pv,v′ is the number of edges in Pv,v′, and the aggregated social contexts meet AtPv,v′≥λtu,u′, ArPv,v′≥λru,u′, and AρPv,v′≥λρu,u′It is known that ifG matches Q, then there exists a unique maximum relation set MQ,G=u1,v1,u2,v2,…,un,vn including all pairs in S.


## 3.4. Matches of Designated Node

Now we extend the pattern graph to beQ=VQ,EQ,LQ,λQ,u0, where u0 is the designated node in VQ. Then, the matches of u0 in G is defined as MUQ,G,u0=vu0,v∈MQ,G.


## 3.5. Ranking Function

### 3.5.1. Relevant Set

Given a matchv of a designated node u0 in Q, the relevant node set of v with respect to u0 is denoted as Ru0,v, which includes all matches v′ of u′ for each descendant u′ of u0 in Q; i.e., if an edge u0,u′∈EQ, then v reaches v′ via a relevant path Pv,v′, where u′,v′∈MQ,G.That is,Ru0,v includes all matches v′ to which v can reach via a relevant path Pv,v′. Accordingly, we define relevant edge set REu0,v to save all relevant paths from v to all matches v′, and then for any match v of a query node u0, there exists unique, maximum relevant node set and relevant edge set.In the node matching, we need to consider the matching of nodes and the corresponding pattern. Based on [31], the ranking function to rank matches of the designated node u0 is defined as follows:(1)Fu0,v=2απarctanRu0,v+1−α∑Pi∈REu0,vUPiREu0,v,where α is used to balance the two functions; Ru0,v and REu0,v are the number of nodes and edges in Ru0,v and REu0,v, respectively; and UPi denotes the average social impact of Pi. In the complex social network, we have three social impact factors, i.e., trust, social intimacy, and social role impact,and they should be considered in the modelling of node matching. Therefore, we propose the following equation:(2)UP=wt×AtP+wr×ArP+wρ×AρP,where wt, wr, and wρ are the weights of social impact factors t, r, and ρ, respectively; wt,wr, and wρ are in the scope of 0,1 and wt + wr + wρ = 1.


## 3.5.1. Relevant Set

Given a matchv of a designated node u0 in Q, the relevant node set of v with respect to u0 is denoted as Ru0,v, which includes all matches v′ of u′ for each descendant u′ of u0 in Q; i.e., if an edge u0,u′∈EQ, then v reaches v′ via a relevant path Pv,v′, where u′,v′∈MQ,G.That is,Ru0,v includes all matches v′ to which v can reach via a relevant path Pv,v′. Accordingly, we define relevant edge set REu0,v to save all relevant paths from v to all matches v′, and then for any match v of a query node u0, there exists unique, maximum relevant node set and relevant edge set.In the node matching, we need to consider the matching of nodes and the corresponding pattern. Based on [31], the ranking function to rank matches of the designated node u0 is defined as follows:(1)Fu0,v=2απarctanRu0,v+1−α∑Pi∈REu0,vUPiREu0,v,where α is used to balance the two functions; Ru0,v and REu0,v are the number of nodes and edges in Ru0,v and REu0,v, respectively; and UPi denotes the average social impact of Pi. In the complex social network, we have three social impact factors, i.e., trust, social intimacy, and social role impact,and they should be considered in the modelling of node matching. Therefore, we propose the following equation:(2)UP=wt×AtP+wr×ArP+wρ×AρP,where wt, wr, and wρ are the weights of social impact factors t, r, and ρ, respectively; wt,wr, and wρ are in the scope of 0,1 and wt + wr + wρ = 1.


## 3.6. TAG-K Problem

Definition 1.
Context-Aware Graph pattern based top-K designated node finding problem (TAG-K). Given a CSGG, a pattern graph Q with a designated node u0, a positive integer K, TAG-K is to find a subset D, where(3)D=argmaxD′∑vi∈D′Fu0,vi,where D′ is a subset of MUQ,G,u0 and D′=K. That is, TAG-K is to identify a set of K matches of u0, which maximizes the summation of ranking function F⋅, namely, ∀D′⊆MUQ,G,u0; if D′=K, then FD⩾FD′.
We denoteCu0 as the set of all the candidates v in G of u0 (i.e., v has the same label as u0) and use FLu0,v and FUu0,v to denote the lower bound and upper bound of Fu0,v, respectively, i.e., FLu0,v≤Fu0,v≤FUu0,v.Lemma 1.
For aK-element set D⊆Cu0, if (1) each v∈D is a match of u0 and (2) minv∈DFLu0,v≥maxv′∈Cu0\DFUu0,v′, then D is the TAG-K result.
Based on Lemma1, we can get TAG-K results without computing the entire MQ,G.


## 4. Recurrent Neural Network-Based Monte Carlo Tree Search (RN-MCTS)

In our algorithm, we build the upper tree and the lower tree of each candidate node that are used to evaluate the upper boundFU⋅ and lower bound FL⋅, respectively; in the searching process, FU⋅ and FL⋅ will be updated, and FL⋅ will gradually close to F⋅; hence, in the worst case, RN-MCTS can still find TAG-K results. In addition, we use the RNN structure that trained by searching results to guide MCTS and propose some optimization strategies to speed up the searching process. In this section, we first introduce the tree structure of RN-MCTS, then introduce the RNN structure, and discuss the details of RN-MCTS combined with RNN and optimization strategies.


### 4.1. Objective Function

Given a CSGG, a pattern graph Q, and a path Pv,v′ in G, we first propose the objective function to investigate if Pv,v′ meets the constraints specified for the edge in Q. We use the objective function to combine the aggregated multiple attribute values and the corresponding constrains. Then, we could investigate the value of the objective function to check the feasibility of the graph search:(4)δPv,v′=maxλtu0,u′AtPv,v′,λru0,u′ArPv,v′,λρu0,u′AρPv,v′,Pv,v′lu0,u′,where u′∈Q and v′∈Cu′. From the objective function, we can see that if an edge u0,u′∈Q can be mapped into a path Pv,v′ in G, δPv,v′≤1; otherwise, δPv,v′>1.


### 4.2. Monte Carlo Tree Structure (MCT)

Now we introduce the Monte Carlo Tree structure (MCT) of RN-MCTS, and each node in the tree represents a node inG, while the tree’s edges correspond to the edges of G. MCTS grows the tree structure iteratively; with each iteration, the MCT is traversed and expanded. In an MCT, a root node represents a candidate in Cu0, and a child node represents the node connected with its ancestor by an edge in G; a leaf node represents (1) the paths through which it exceeds constraints of social contexts or cannot be relevant paths or (2) a new expanded node that has not been visited. Each MCT can be seen as the subgraph connected to a candidate node. Each node v′ in the MCT stores the set of statistics:(5)Pv,v′,RESv,v′,RSv,v′,FSv,v′,Nv,v′.Here, the root nodev of the MCT is a candidate, Pv,v′=v,…,v′ is the path from root node v to v′, Nv,v′ is the number of times that v′ has been visited in the MCT, RESv,v′ is a set that saves all relevant paths that start from Pv,v′ in the MCT, and RSv,v′ is a set that saves the corresponding relevant nodes; i.e., for a visited relevant path Pi=v,…,v′,…,vi, Pi∈RESv,v′ and vi∈RSv,v′. Then, it is known RSv,v′ is a subset of Ru0,v. FSv,v′ is defined as follows:(6)FSv,v′=2απarctanRSv,v′+1−α∑Pi∈RESv,v′UPiRESv,v′,where α is the same factor of equation (1). In the searching process, if RN-MCTS finds a new relevant path Pv,vj passing through Pv,v′, Pv,vj and vj will be added in RESv,v′ and RSv,v′, respectively, then updates FSv,v′ by (6).Given a candidatev of a designated node u0 in Q, if all the relevant paths of REu0,v has been visited in the MCT of v. Intuitively, Fu0,v can be calculated as follows:(7)Fu0,v=2απarctan∑viRSv,vi+1−α∑vi∑Pj∈RESv,viUPj∑viRESv,vi.Here,vi is the child node of v in the MCT. That is, after certain times of iterations, F⋅ of a candidate can be approximated by statistics of its child nodes. Then, we formulate the TAG-K problem as the Monte Carlo Tree Search (MCTS) problem. Since F⋅ of the root node is proportional to FS⋅ of child nodes, the aim of MCTS is to find high values of FS⋅ in the MCTs of candidates under limited searching time.


### 4.3. Recurrent Neural Network Policy

Now, we introduce the RNN policy. In the searching process, RNN is used to help RN-MCTS to select child nodes. Our RNN structure is simple and consists of two layers: an RNN layer and a fully connected layer. In the MCT ofv1, for the visited path Pv1,vn=v1,v2,…,vn, we can get the sequence: TPv1,vn=T1,T2,…,Tn−1, where Ti=Pv1,vi+1,RSv,vi+1,FSv,vi+1,i∈1,n−1. Here, each node v in Pv1,vi and RSv,vi is represented by a vector representation, i.e., Pv1,vi=ℰv1,ℰv2,…,ℰvi. ℰv is the vector representation of v that is generated by DeepWalk [32]. For the path Pv1,vn, we set TPv1,vn−1 as the input and the node selection ℰvn and FSv,vn as the output to train the RNN structure, and the lost function of a time step is defined as follows:(8)lostTi,Ti′=μRMSEP,P′+1−μRMSERS,RS′+FS−FS′2.Here,Ti′=P′,RS′,FS′ is the prediction of the last time step Ti−1. RMSE is the function of root mean squared error:(9)RMSEy,y′=∑i=1nyi−yS′2n.Then, for the current searching pathP, we define the output of the RNN structure (i.e., ℰvn and FSv,vn) as ℰnetP and FnetP, respectively.


### 4.4. UCT Function

An important problem of MCTS is to balance the exploration versus exploitation. The exploration approach promotes the exploration of unvisited nodes in the MCT, and this means that the exploration will expand the tree’s breath more than its depth. Exploitation tends to stick to one path that has the greatest estimated value (i.e., the maximal value ofFS⋅) to find more relevant nodes. The balance of exploration and exploitation can ensure our algorithm is not overlooking any potential relevant paths, avoiding the inefficiency in the search with a large number of candidates.Specifically, on each RN-MCTS iteration, the search process is rolled out by selecting child nodes according to the proposed variant of UCT [33] from the root node. During the search of a Monte Carlo Tree, we need to consider both the width and the depth of the tree search. Therefore, we propose equations (10) and (11):(10)vd=argmaxvsFSv,vs+β×dPv,vf,vsFnetPv,vf+γlnNv,vfNv,vs+1,where γ and β are the constants that control the level of exploration, Pv,vf is the current search path, and vs is the child node of vf. dPv,vf,vs is the similarity between vs and the predict of RNN, which is defined as follows:(11)dPv,vf,vs=cosℰnetPv,vf,ℰvs.Overall, UCT initially prefers nodes that have high similarity with the RNN outputℰnet⋅ and low visit count N⋅, but then asymptotically prefers nodes with high values of FS⋅.


### 4.5. The Bound of TAG-K Matching

Now, we introduce the upper tree and the lower tree that are variants of MCT to compute the estimate value of upper boundFU⋅ and lower bound FL⋅, respectively. RN-MCTS can stop as soon as Lemma 1 is satisfied, without computing the entire MUQ,G,u0. The details of the upper tree and lower tree are as follows.


#### 4.5.1. Upper Tree

In the upper tree, given a pattern graphQ=VQ,EQ,LQ,λQ,u0, RN-MCTS relaxes λQ=l,λt,λr,λρ to be λQ′=l′,λt′,λr′,λρ′ as follows:(12)l′,λt′,λr′,λρ′=maxle,minλte,minλre,minλρe,e∈EQ.In addition, in the upper trees,FS⋅ saved in the nodes is replaced by FSU⋅ and is defined as follows:(13)FSUv,v′=2απarctanRSv,v′+1−αmaxPi∈RESv,v′UPi.The upper boundFUu0,v is calculated by equation (7). Thus, comparing with equation (6), because of the relaxation of constraints and the selection of maximal U⋅, FUu0,v>Fu0,v. In the searching process of upper trees, RNN structure will not be used.


#### 4.5.2. Lower Tree

In the lower tree, the pattern graph and the MCT are not changed, andFLu0,v is calculated by using equation (6). Hence, with the increase in iterations, FLu0,v will be close to Fu0,v. Here, the RNN structure is used to guide the searching process.


### 4.6. Optimization Strategy

In this section, we introduce 3optimization strategies to reduce the searching space and speed up the searching process.Strategy 1.
Rapid evaluate. Social graphs are typically large, with millions of nodes and billions of edges; hence, RN-MCTS first usesrapid evaluate to make the preliminary estimate lower bounds and upper bounds of all candidates and details as below.
Given a designated nodeu0 in Q, a candidate v in Cu0, RN-MCTS builds the upper tree and the lower tree of v and performs once iteration on them, respectively, and then uses the searching results to calculate the initial values of lower bound and upper bound. In the process of rapid evaluate, if the candidate vc is a descendant in the MCT of v, vc will be preferentially selected, then RN-MCTS calculates FSv,vc in the lower tree and FSUv,vc in the upper tree; set them as the initial values of FLu0,vc and FUu0,vc, respectively, and then put vc into the protection set PT. The nodes in PT will be not deleted when performing optimization strategies, and vc will be taken out from PT the next time RN-MCTS searches the MCT of vc. In addition, FLu0,vc and FUu0,vc will be updated when vc is visited again and still in PT. Thus, RN-MCTS can get initial bounds of candidates without visiting all MCTs.Strategy 2.
Optimization at dominating nodes. In the MCTs, there can have multiple paths ending at the same nodes. To obtain a near-optimal solution, the first time the searching path (denoted asP1) reaches the node vi, RN-MCTS marks vi as visited and stores the value of δP1, and assume the parent node of vi is vs. In the following iterations, suppose there is another path from root node to vi(denoted as Py, assume the parent node of vi in Py as vt). If δP1>δPy, it indicates Py is better than P1, then we delete vi, which is the child node of vs; otherwise, if δP1<δPy, it indicates P1 is better than Py, then we delete vi that is the child node of vt.Strategy 3 (Reduce space).
Given a designated nodeu0 in Q and two candidates vi,vj∈Cu0, after certain times of iterations, if FLu0,vi>FUu0,vj, it is easy to know vi may be a better designated node matching than vj. In order to reduce the search space, RN-MCTS performs optimizations in the following situations:(i)
Situation 1: after certain times of iterations, ifvj∈Cu0 and FUu0,vj<∑vi∈Cu0FLu0,vi/Cu0, it indicates vj has a lower probability to be the top-K matches of u0, then we delete vj in Cu0(ii)
Situation 2: for a nodevj∈Cu0, if all nodes in the upper tree of vj have been visited and FUu0,vj<FLK, FLK is the K-th maximum FL⋅ value of nodes in Cu0 and it indicates vj cannot be the top-K matches of u0, then we delete vj in Cu0


### 4.7. MCTS Details

Each iteration of MCTS can be split up into four steps:selection, expansion, simulation, and backpropagation. The four steps of MCTS are discussed below, and the corresponding pseudocode is shown in Algorithm 1.Algorithm 1: RN-MCTS.
Data: CSG G=V,E,LG,ρ; query graph Q=VQ,EQ,LQ,λQ,u0; candidate node set Cu0; number of iterations I;
Perform rapid evaluate to build MCTs ofCu0;
UseT⋅,ℰ⋅,FS⋅ of rapid evaluate to train RNN;
for iteration it in 1…I do
Use probability function to selectv from Cu0; set the current node vu=v;
In the upper tree and lower tree ofv:
While δv,vu≤1 do
If vu is unvisited then
Markvu visited; add the neighbors vc of vu in G that δPv,vc≤1 into the MCT as the child nodes of vu; initial P,RS,RES,FS,N of these child nodes;
if vu.child=∅ then
Break;
end
end
if vu is a leaf node then
Break;
end
Select the nodevc with the maximum UCT value; update vu⟵vc;
end
for each node in Pv,vu do
UpdateP,RS,RES,FS,N; use T⋅,ℰ⋅,FS⋅ to train RNN;
end
Perform optimization strategy;
if meet the situation of early terminal then
Return top-K matches ofu0;
end
end
Return top-K matches ofu0.


#### 4.7.1. Probability Function

Before performing the iteration of MCTS, RN-MCTS uses the probability function to randomly select a candidatevc and the probability of vc to be selected is defined as follows:(14)Prvc=FHu0,vc∑vi∈Cu0FHu0,vi.Here, we use a function that is similar to UCT, which combined exploitation with exploration to define the weight of selection:(15)FHu0,vc=ℱu0,vc+θln∑vi∈Cu0NviNvc+1,and the constant θ controls the level of exploration. ℱu0,vc=FUu0,vc+FLu0,vc.Step 1 (Selection).
In this step, given a candidatev∈C as the root node of the MCT, starting from v, MCTS traverses the current MCT using a tree policy. A tree policy uses an evaluation function (i.e., UCT function) that prioritize nodes with the greatest estimated values. When the searching path reaches a leaf node, if the leaf node is unvisited and with children yet to be added, MCTS will transition to the expansion step; otherwise, if the leaf node has been visited, then MCTS will transition to the backpropagation step.Step 2 (Expansion).
In the expansion step, for the unvisited leaf node reached in the selection step, MCTS selects all neighbor nodes of the leaf node, and add all nodes thatδ⋅≤1 into the MCT as child nodes of the leaf node; namely, the searching paths ending at these neighboring nodes are feasible and then initializes P⋅,RES⋅=∅,RS⋅=∅,FS⋅=0,N⋅=0 of these child nodes. After that, MCTS transitions to the simulation step. If all δP values of neighboring nodes of vc are more than 1, it indicates vc is a leaf node that cannot find relevant paths through vc, then MCTS will transition to the backpropagation step.Step 3 (Simulation).
Since the child nodes of the current node have been added to the MCT, MCTS can continue to traverse the MCT. Therefore, in this step, MCTS performs selection and expansion repeatedly until reaches a visited leaf node and then transitions to thebackpropagation step.Step 4 (Backpropagation).
Now that the MCTS has reached the visited leaf node, and the rest of the MCT must be updated. Starting from the leaf node, RN-MCTS traverses back to the root node. During the traversal, the statistics stored in each node of the traversal (i.e.,RES⋅,RS⋅,FS⋅orFSU⋅,N⋅ are incremented. N⋅⟵N⋅+1. RES⋅,RS⋅,FS⋅, or FSU⋅ are updated as discussed before. In addition, for each node v′ in the traversal of backpropagation, we use Tv,vc,ℰv′,FSv,v′ to train the RNN. Here, vc is the parent node of v′ in the traversal.
We set RN-MCTS performs the above four steps forI iterations. So its time complexity is OI×selection+expansion+simulation+backpropagation. Let Nc denote the average number of child nodes at each layer of the tree and let D denotes the depth of the search tree. The selection step has the time complexity ONc, the expansion step has ONc, and both the simulation step and backpropagation step have ODNc. Therefore, the time complexity of RN-MCTS is OIDNc. In addition, we can use graph database to save the graph structure, and in addition, in real-world social networks, not all the pairs of nodes have links. Therefore, we can compress the sparse matrix of a data graph by using the Hybrid format [34] to save large graphs.


## 4.1. Objective Function

Given a CSGG, a pattern graph Q, and a path Pv,v′ in G, we first propose the objective function to investigate if Pv,v′ meets the constraints specified for the edge in Q. We use the objective function to combine the aggregated multiple attribute values and the corresponding constrains. Then, we could investigate the value of the objective function to check the feasibility of the graph search:(4)δPv,v′=maxλtu0,u′AtPv,v′,λru0,u′ArPv,v′,λρu0,u′AρPv,v′,Pv,v′lu0,u′,where u′∈Q and v′∈Cu′. From the objective function, we can see that if an edge u0,u′∈Q can be mapped into a path Pv,v′ in G, δPv,v′≤1; otherwise, δPv,v′>1.


## 4.2. Monte Carlo Tree Structure (MCT)

Now we introduce the Monte Carlo Tree structure (MCT) of RN-MCTS, and each node in the tree represents a node inG, while the tree’s edges correspond to the edges of G. MCTS grows the tree structure iteratively; with each iteration, the MCT is traversed and expanded. In an MCT, a root node represents a candidate in Cu0, and a child node represents the node connected with its ancestor by an edge in G; a leaf node represents (1) the paths through which it exceeds constraints of social contexts or cannot be relevant paths or (2) a new expanded node that has not been visited. Each MCT can be seen as the subgraph connected to a candidate node. Each node v′ in the MCT stores the set of statistics:(5)Pv,v′,RESv,v′,RSv,v′,FSv,v′,Nv,v′.Here, the root nodev of the MCT is a candidate, Pv,v′=v,…,v′ is the path from root node v to v′, Nv,v′ is the number of times that v′ has been visited in the MCT, RESv,v′ is a set that saves all relevant paths that start from Pv,v′ in the MCT, and RSv,v′ is a set that saves the corresponding relevant nodes; i.e., for a visited relevant path Pi=v,…,v′,…,vi, Pi∈RESv,v′ and vi∈RSv,v′. Then, it is known RSv,v′ is a subset of Ru0,v. FSv,v′ is defined as follows:(6)FSv,v′=2απarctanRSv,v′+1−α∑Pi∈RESv,v′UPiRESv,v′,where α is the same factor of equation (1). In the searching process, if RN-MCTS finds a new relevant path Pv,vj passing through Pv,v′, Pv,vj and vj will be added in RESv,v′ and RSv,v′, respectively, then updates FSv,v′ by (6).Given a candidatev of a designated node u0 in Q, if all the relevant paths of REu0,v has been visited in the MCT of v. Intuitively, Fu0,v can be calculated as follows:(7)Fu0,v=2απarctan∑viRSv,vi+1−α∑vi∑Pj∈RESv,viUPj∑viRESv,vi.Here,vi is the child node of v in the MCT. That is, after certain times of iterations, F⋅ of a candidate can be approximated by statistics of its child nodes. Then, we formulate the TAG-K problem as the Monte Carlo Tree Search (MCTS) problem. Since F⋅ of the root node is proportional to FS⋅ of child nodes, the aim of MCTS is to find high values of FS⋅ in the MCTs of candidates under limited searching time.


## 4.3. Recurrent Neural Network Policy

Now, we introduce the RNN policy. In the searching process, RNN is used to help RN-MCTS to select child nodes. Our RNN structure is simple and consists of two layers: an RNN layer and a fully connected layer. In the MCT ofv1, for the visited path Pv1,vn=v1,v2,…,vn, we can get the sequence: TPv1,vn=T1,T2,…,Tn−1, where Ti=Pv1,vi+1,RSv,vi+1,FSv,vi+1,i∈1,n−1. Here, each node v in Pv1,vi and RSv,vi is represented by a vector representation, i.e., Pv1,vi=ℰv1,ℰv2,…,ℰvi. ℰv is the vector representation of v that is generated by DeepWalk [32]. For the path Pv1,vn, we set TPv1,vn−1 as the input and the node selection ℰvn and FSv,vn as the output to train the RNN structure, and the lost function of a time step is defined as follows:(8)lostTi,Ti′=μRMSEP,P′+1−μRMSERS,RS′+FS−FS′2.Here,Ti′=P′,RS′,FS′ is the prediction of the last time step Ti−1. RMSE is the function of root mean squared error:(9)RMSEy,y′=∑i=1nyi−yS′2n.Then, for the current searching pathP, we define the output of the RNN structure (i.e., ℰvn and FSv,vn) as ℰnetP and FnetP, respectively.


## 4.4. UCT Function

An important problem of MCTS is to balance the exploration versus exploitation. The exploration approach promotes the exploration of unvisited nodes in the MCT, and this means that the exploration will expand the tree’s breath more than its depth. Exploitation tends to stick to one path that has the greatest estimated value (i.e., the maximal value ofFS⋅) to find more relevant nodes. The balance of exploration and exploitation can ensure our algorithm is not overlooking any potential relevant paths, avoiding the inefficiency in the search with a large number of candidates.Specifically, on each RN-MCTS iteration, the search process is rolled out by selecting child nodes according to the proposed variant of UCT [33] from the root node. During the search of a Monte Carlo Tree, we need to consider both the width and the depth of the tree search. Therefore, we propose equations (10) and (11):(10)vd=argmaxvsFSv,vs+β×dPv,vf,vsFnetPv,vf+γlnNv,vfNv,vs+1,where γ and β are the constants that control the level of exploration, Pv,vf is the current search path, and vs is the child node of vf. dPv,vf,vs is the similarity between vs and the predict of RNN, which is defined as follows:(11)dPv,vf,vs=cosℰnetPv,vf,ℰvs.Overall, UCT initially prefers nodes that have high similarity with the RNN outputℰnet⋅ and low visit count N⋅, but then asymptotically prefers nodes with high values of FS⋅.


## 4.5. The Bound of TAG-K Matching

Now, we introduce the upper tree and the lower tree that are variants of MCT to compute the estimate value of upper boundFU⋅ and lower bound FL⋅, respectively. RN-MCTS can stop as soon as Lemma 1 is satisfied, without computing the entire MUQ,G,u0. The details of the upper tree and lower tree are as follows.


### 4.5.1. Upper Tree

In the upper tree, given a pattern graphQ=VQ,EQ,LQ,λQ,u0, RN-MCTS relaxes λQ=l,λt,λr,λρ to be λQ′=l′,λt′,λr′,λρ′ as follows:(12)l′,λt′,λr′,λρ′=maxle,minλte,minλre,minλρe,e∈EQ.In addition, in the upper trees,FS⋅ saved in the nodes is replaced by FSU⋅ and is defined as follows:(13)FSUv,v′=2απarctanRSv,v′+1−αmaxPi∈RESv,v′UPi.The upper boundFUu0,v is calculated by equation (7). Thus, comparing with equation (6), because of the relaxation of constraints and the selection of maximal U⋅, FUu0,v>Fu0,v. In the searching process of upper trees, RNN structure will not be used.


### 4.5.2. Lower Tree

In the lower tree, the pattern graph and the MCT are not changed, andFLu0,v is calculated by using equation (6). Hence, with the increase in iterations, FLu0,v will be close to Fu0,v. Here, the RNN structure is used to guide the searching process.


## 4.5.1. Upper Tree

In the upper tree, given a pattern graphQ=VQ,EQ,LQ,λQ,u0, RN-MCTS relaxes λQ=l,λt,λr,λρ to be λQ′=l′,λt′,λr′,λρ′ as follows:(12)l′,λt′,λr′,λρ′=maxle,minλte,minλre,minλρe,e∈EQ.In addition, in the upper trees,FS⋅ saved in the nodes is replaced by FSU⋅ and is defined as follows:(13)FSUv,v′=2απarctanRSv,v′+1−αmaxPi∈RESv,v′UPi.The upper boundFUu0,v is calculated by equation (7). Thus, comparing with equation (6), because of the relaxation of constraints and the selection of maximal U⋅, FUu0,v>Fu0,v. In the searching process of upper trees, RNN structure will not be used.


## 4.5.2. Lower Tree

In the lower tree, the pattern graph and the MCT are not changed, andFLu0,v is calculated by using equation (6). Hence, with the increase in iterations, FLu0,v will be close to Fu0,v. Here, the RNN structure is used to guide the searching process.


## 4.6. Optimization Strategy

In this section, we introduce 3optimization strategies to reduce the searching space and speed up the searching process.Strategy 1.
Rapid evaluate. Social graphs are typically large, with millions of nodes and billions of edges; hence, RN-MCTS first usesrapid evaluate to make the preliminary estimate lower bounds and upper bounds of all candidates and details as below.
Given a designated nodeu0 in Q, a candidate v in Cu0, RN-MCTS builds the upper tree and the lower tree of v and performs once iteration on them, respectively, and then uses the searching results to calculate the initial values of lower bound and upper bound. In the process of rapid evaluate, if the candidate vc is a descendant in the MCT of v, vc will be preferentially selected, then RN-MCTS calculates FSv,vc in the lower tree and FSUv,vc in the upper tree; set them as the initial values of FLu0,vc and FUu0,vc, respectively, and then put vc into the protection set PT. The nodes in PT will be not deleted when performing optimization strategies, and vc will be taken out from PT the next time RN-MCTS searches the MCT of vc. In addition, FLu0,vc and FUu0,vc will be updated when vc is visited again and still in PT. Thus, RN-MCTS can get initial bounds of candidates without visiting all MCTs.Strategy 2.
Optimization at dominating nodes. In the MCTs, there can have multiple paths ending at the same nodes. To obtain a near-optimal solution, the first time the searching path (denoted asP1) reaches the node vi, RN-MCTS marks vi as visited and stores the value of δP1, and assume the parent node of vi is vs. In the following iterations, suppose there is another path from root node to vi(denoted as Py, assume the parent node of vi in Py as vt). If δP1>δPy, it indicates Py is better than P1, then we delete vi, which is the child node of vs; otherwise, if δP1<δPy, it indicates P1 is better than Py, then we delete vi that is the child node of vt.Strategy 3 (Reduce space).
Given a designated nodeu0 in Q and two candidates vi,vj∈Cu0, after certain times of iterations, if FLu0,vi>FUu0,vj, it is easy to know vi may be a better designated node matching than vj. In order to reduce the search space, RN-MCTS performs optimizations in the following situations:(i)
Situation 1: after certain times of iterations, ifvj∈Cu0 and FUu0,vj<∑vi∈Cu0FLu0,vi/Cu0, it indicates vj has a lower probability to be the top-K matches of u0, then we delete vj in Cu0(ii)
Situation 2: for a nodevj∈Cu0, if all nodes in the upper tree of vj have been visited and FUu0,vj<FLK, FLK is the K-th maximum FL⋅ value of nodes in Cu0 and it indicates vj cannot be the top-K matches of u0, then we delete vj in Cu0


## 4.7. MCTS Details

Each iteration of MCTS can be split up into four steps:selection, expansion, simulation, and backpropagation. The four steps of MCTS are discussed below, and the corresponding pseudocode is shown in Algorithm 1.Algorithm 1: RN-MCTS.
Data: CSG G=V,E,LG,ρ; query graph Q=VQ,EQ,LQ,λQ,u0; candidate node set Cu0; number of iterations I;
Perform rapid evaluate to build MCTs ofCu0;
UseT⋅,ℰ⋅,FS⋅ of rapid evaluate to train RNN;
for iteration it in 1…I do
Use probability function to selectv from Cu0; set the current node vu=v;
In the upper tree and lower tree ofv:
While δv,vu≤1 do
If vu is unvisited then
Markvu visited; add the neighbors vc of vu in G that δPv,vc≤1 into the MCT as the child nodes of vu; initial P,RS,RES,FS,N of these child nodes;
if vu.child=∅ then
Break;
end
end
if vu is a leaf node then
Break;
end
Select the nodevc with the maximum UCT value; update vu⟵vc;
end
for each node in Pv,vu do
UpdateP,RS,RES,FS,N; use T⋅,ℰ⋅,FS⋅ to train RNN;
end
Perform optimization strategy;
if meet the situation of early terminal then
Return top-K matches ofu0;
end
end
Return top-K matches ofu0.


### 4.7.1. Probability Function

Before performing the iteration of MCTS, RN-MCTS uses the probability function to randomly select a candidatevc and the probability of vc to be selected is defined as follows:(14)Prvc=FHu0,vc∑vi∈Cu0FHu0,vi.Here, we use a function that is similar to UCT, which combined exploitation with exploration to define the weight of selection:(15)FHu0,vc=ℱu0,vc+θln∑vi∈Cu0NviNvc+1,and the constant θ controls the level of exploration. ℱu0,vc=FUu0,vc+FLu0,vc.Step 1 (Selection).
In this step, given a candidatev∈C as the root node of the MCT, starting from v, MCTS traverses the current MCT using a tree policy. A tree policy uses an evaluation function (i.e., UCT function) that prioritize nodes with the greatest estimated values. When the searching path reaches a leaf node, if the leaf node is unvisited and with children yet to be added, MCTS will transition to the expansion step; otherwise, if the leaf node has been visited, then MCTS will transition to the backpropagation step.Step 2 (Expansion).
In the expansion step, for the unvisited leaf node reached in the selection step, MCTS selects all neighbor nodes of the leaf node, and add all nodes thatδ⋅≤1 into the MCT as child nodes of the leaf node; namely, the searching paths ending at these neighboring nodes are feasible and then initializes P⋅,RES⋅=∅,RS⋅=∅,FS⋅=0,N⋅=0 of these child nodes. After that, MCTS transitions to the simulation step. If all δP values of neighboring nodes of vc are more than 1, it indicates vc is a leaf node that cannot find relevant paths through vc, then MCTS will transition to the backpropagation step.Step 3 (Simulation).
Since the child nodes of the current node have been added to the MCT, MCTS can continue to traverse the MCT. Therefore, in this step, MCTS performs selection and expansion repeatedly until reaches a visited leaf node and then transitions to thebackpropagation step.Step 4 (Backpropagation).
Now that the MCTS has reached the visited leaf node, and the rest of the MCT must be updated. Starting from the leaf node, RN-MCTS traverses back to the root node. During the traversal, the statistics stored in each node of the traversal (i.e.,RES⋅,RS⋅,FS⋅orFSU⋅,N⋅ are incremented. N⋅⟵N⋅+1. RES⋅,RS⋅,FS⋅, or FSU⋅ are updated as discussed before. In addition, for each node v′ in the traversal of backpropagation, we use Tv,vc,ℰv′,FSv,v′ to train the RNN. Here, vc is the parent node of v′ in the traversal.
We set RN-MCTS performs the above four steps forI iterations. So its time complexity is OI×selection+expansion+simulation+backpropagation. Let Nc denote the average number of child nodes at each layer of the tree and let D denotes the depth of the search tree. The selection step has the time complexity ONc, the expansion step has ONc, and both the simulation step and backpropagation step have ODNc. Therefore, the time complexity of RN-MCTS is OIDNc. In addition, we can use graph database to save the graph structure, and in addition, in real-world social networks, not all the pairs of nodes have links. Therefore, we can compress the sparse matrix of a data graph by using the Hybrid format [34] to save large graphs.


## 4.7.1. Probability Function

Before performing the iteration of MCTS, RN-MCTS uses the probability function to randomly select a candidatevc and the probability of vc to be selected is defined as follows:(14)Prvc=FHu0,vc∑vi∈Cu0FHu0,vi.Here, we use a function that is similar to UCT, which combined exploitation with exploration to define the weight of selection:(15)FHu0,vc=ℱu0,vc+θln∑vi∈Cu0NviNvc+1,and the constant θ controls the level of exploration. ℱu0,vc=FUu0,vc+FLu0,vc.Step 1 (Selection).
In this step, given a candidatev∈C as the root node of the MCT, starting from v, MCTS traverses the current MCT using a tree policy. A tree policy uses an evaluation function (i.e., UCT function) that prioritize nodes with the greatest estimated values. When the searching path reaches a leaf node, if the leaf node is unvisited and with children yet to be added, MCTS will transition to the expansion step; otherwise, if the leaf node has been visited, then MCTS will transition to the backpropagation step.Step 2 (Expansion).
In the expansion step, for the unvisited leaf node reached in the selection step, MCTS selects all neighbor nodes of the leaf node, and add all nodes thatδ⋅≤1 into the MCT as child nodes of the leaf node; namely, the searching paths ending at these neighboring nodes are feasible and then initializes P⋅,RES⋅=∅,RS⋅=∅,FS⋅=0,N⋅=0 of these child nodes. After that, MCTS transitions to the simulation step. If all δP values of neighboring nodes of vc are more than 1, it indicates vc is a leaf node that cannot find relevant paths through vc, then MCTS will transition to the backpropagation step.Step 3 (Simulation).
Since the child nodes of the current node have been added to the MCT, MCTS can continue to traverse the MCT. Therefore, in this step, MCTS performs selection and expansion repeatedly until reaches a visited leaf node and then transitions to thebackpropagation step.Step 4 (Backpropagation).
Now that the MCTS has reached the visited leaf node, and the rest of the MCT must be updated. Starting from the leaf node, RN-MCTS traverses back to the root node. During the traversal, the statistics stored in each node of the traversal (i.e.,RES⋅,RS⋅,FS⋅orFSU⋅,N⋅ are incremented. N⋅⟵N⋅+1. RES⋅,RS⋅,FS⋅, or FSU⋅ are updated as discussed before. In addition, for each node v′ in the traversal of backpropagation, we use Tv,vc,ℰv′,FSv,v′ to train the RNN. Here, vc is the parent node of v′ in the traversal.
We set RN-MCTS performs the above four steps forI iterations. So its time complexity is OI×selection+expansion+simulation+backpropagation. Let Nc denote the average number of child nodes at each layer of the tree and let D denotes the depth of the search tree. The selection step has the time complexity ONc, the expansion step has ONc, and both the simulation step and backpropagation step have ODNc. Therefore, the time complexity of RN-MCTS is OIDNc. In addition, we can use graph database to save the graph structure, and in addition, in real-world social networks, not all the pairs of nodes have links. Therefore, we can compress the sparse matrix of a data graph by using the Hybrid format [34] to save large graphs.


## 5. Experiments

### 5.1. Experiment Settings

(i)
We conduct experiments on five large-scale real-world social graphs available atsnap.stanford.edu. These datasets have been widely used in the literature for studies of graph pattern matching and social network analysis. The details of these datasets are shown in Table 1.
(ii)
We use a popular social network generation tool, SocNetV (socnetv.org, with version 2.2) to generate five query graphs, and the details of these graphs are shown in Table 2, where we randomly select a node from each of the pattern graph as the designated node.
(iii)
The average constrains of edges in patternλt,λr,λρ are set in 0.1, 0.2, 0.3, 0.4, and 0.5 to ensure the high possibility of returning TAG-K designated nodes in a data graph. Otherwise, no or only few answers might be returned by all the algorithms, making it difficult to investigate their performance.
(iv)
In each of the datasets,α is set to 0.5; the number of iteration is set to 1000, 2000, 3000, 4000, and 5000; K is set to 5, 10, 15, 20, and 25; and the average maximal bounded path length of the pattern matching is set as 2, 4, 6, 8, and 10, respectively.
(v)
In order to avoid the bias in the tree search, we balance the search in both width and depth. Then, in the UCT function and probability function, the exploration parameters ofβ, γ, and θ are set to 0.5. In the RNN structure, μ is set to 0.5, the embedding of nodes are encoded by DeepWalk [32] with 16 dimensions. We use the ADAM optimization algorithm with a learning rate of 0.005 during training, and we set the mini-batch size to 8.
(vi)
In order to deliver fair experimental results to avoid the bias experimental results by a specific setting, we calculate the average ranking function value to illustrate the performance of the proposed method.Table 1
The social datasets.
Name
Nodes
Edges
Description
citHepTh
28k
353k
Citation network
Slashdot
77k
905k
Social network
DBLP
317k
1050k
Collaboration network
Twitter
741k
2400k
Social network
YouTube
1729k
3844k
Social networkTable 2
The pattern graphs.
Name
Nodes
Edges
Q
5
5
7
Q
10
10
21
Q
15
15
34
Q
20
20
50
Q
25
25
63


### 5.2. Implementation

In the following experiments, we will compare our RN-MCTS with the basic Monte Carlo Tree Search algorithm without the RNN structure (B-MCTS) and the state-of-art TAG-K method, MC-TAG-K [35]. Since the three algorithms are approximate methods, it is not appropriate to directly compare ranking function values returned by the three algorithms. Therefore, we traverse TAG-K results of the three algorithms and get the true ranking function values, respectively. The performance was investigated by the execution time, the true ranking function values, and the difference between the true ranking function values and the approximate ranking function values.All MC-TAG-K, B-MCTS, and RN-MCTS algorithms are implemented using Matlab R2019a running on a PC with Intel Core i7-7700K 4.2 GHz CPU, 16 GB RAM, Windows 10 operating system, and MySql 5.7 database. All the experimental results are averaged based on five independent runs.


### 5.3. Experimental Results and Analysis

#### 5.3.1. Exp-1: Effectiveness

This experiment is to investigate the effectiveness of our RN-MCTS by comparing the average ranking function values of the top-K matches based on different settings of parameters.Results. Figures 2 and 3 and Table 3 depict the average ranking function values of TAG-K results with different settings of parameters under MC-TAG-K, B-MCTS, and RN-MCTS. From these figures, we can see that the average ranking function values returned by MC-TAG-K are always less than that of B-MCTS and RN-MCTS. Overall, the average true function value delivered by RN-MCTS is 15.92% and 10.04% more than that of MC-TAG-K and B-MCTS, respectively.Figure 2
The average ranking function value based on different constrains.
(a)
(b)
(c)
(d)
(e)Figure 3
The average ranking function value based on different iterations.
(a)
(b)
(c)
(d)
(e)Table 3
The difference between approximate and true ranking function values.
citHepTh
Slashdot
DBLP
Twitter
YouTube
MC-TAG-K
0.0891
0.0953
0.1275
0.1324
0.1277
B-MCTS
0.0542
0.0465
0.0752
0.0846
0.0861
RN-MCTS
0.0475
0.0412
0.0624
0.0718
0.0724Analysis. The experimental results illustrate that (1) the approximate ranking function values returned by MC-TAG-K have a large deviation with the true ranking function values; (2) RN-MCTS and B-MCTS can deliver more accurate approximate ranking function values by using the neural network and MCTS; therefore, RN-MCTS and B-MCTS can get better matching results than MC-TAG-K; (3) with the assistance of neural network and optimal strategy, RN-MCTS can avoid the MCT search via a subgraph that has a lower probability to satisfy the constraints and then outperforms B-MCTS.


#### 5.3.2. Exp-2: Efficiency

This experiment is to investigate the efficiency of our RN-MCTS by comparing the average query processing time of MC-TAG-K, RN-MCTS, and B-MCTS based on different settings of parameters.Results. Figures 4 and 5 depict the average query processing time of the three algorithms in returning different numbers of designed nodes with different setting of parameters. From these figures, we can see that RN-MCTS and B-MCTS have better efficiency than MC-TAG-K. Statistically, on average, the query processing time of RN-MCTS is 75.30% less than that of MC-TAG-K and 17.30% more than that of B-MCTS.Figure 4
The average query processing time based on different constrains.
(a)
(b)
(c)
(d)
(e)Figure 5
The average query processing time based on different iterations.
(a)
(b)
(c)
(d)
(e)Analysis. The experimental results illustrate that (1) RN-MCTS can reduce the searching space and avoid to visit all nodes and edges in the data graph. Thus, RN-MCTS can greatly save the query processing time than MC-TAG-K; (2) because of the RNN structure, each iteration of RN-MCTS costs more time than B-MCTS.


## 5.1. Experiment Settings

(i)
We conduct experiments on five large-scale real-world social graphs available atsnap.stanford.edu. These datasets have been widely used in the literature for studies of graph pattern matching and social network analysis. The details of these datasets are shown in Table 1.
(ii)
We use a popular social network generation tool, SocNetV (socnetv.org, with version 2.2) to generate five query graphs, and the details of these graphs are shown in Table 2, where we randomly select a node from each of the pattern graph as the designated node.
(iii)
The average constrains of edges in patternλt,λr,λρ are set in 0.1, 0.2, 0.3, 0.4, and 0.5 to ensure the high possibility of returning TAG-K designated nodes in a data graph. Otherwise, no or only few answers might be returned by all the algorithms, making it difficult to investigate their performance.
(iv)
In each of the datasets,α is set to 0.5; the number of iteration is set to 1000, 2000, 3000, 4000, and 5000; K is set to 5, 10, 15, 20, and 25; and the average maximal bounded path length of the pattern matching is set as 2, 4, 6, 8, and 10, respectively.
(v)
In order to avoid the bias in the tree search, we balance the search in both width and depth. Then, in the UCT function and probability function, the exploration parameters ofβ, γ, and θ are set to 0.5. In the RNN structure, μ is set to 0.5, the embedding of nodes are encoded by DeepWalk [32] with 16 dimensions. We use the ADAM optimization algorithm with a learning rate of 0.005 during training, and we set the mini-batch size to 8.
(vi)
In order to deliver fair experimental results to avoid the bias experimental results by a specific setting, we calculate the average ranking function value to illustrate the performance of the proposed method.Table 1
The social datasets.
Name
Nodes
Edges
Description
citHepTh
28k
353k
Citation network
Slashdot
77k
905k
Social network
DBLP
317k
1050k
Collaboration network
Twitter
741k
2400k
Social network
YouTube
1729k
3844k
Social networkTable 2
The pattern graphs.
Name
Nodes
Edges
Q
5
5
7
Q
10
10
21
Q
15
15
34
Q
20
20
50
Q
25
25
63


## 5.2. Implementation

In the following experiments, we will compare our RN-MCTS with the basic Monte Carlo Tree Search algorithm without the RNN structure (B-MCTS) and the state-of-art TAG-K method, MC-TAG-K [35]. Since the three algorithms are approximate methods, it is not appropriate to directly compare ranking function values returned by the three algorithms. Therefore, we traverse TAG-K results of the three algorithms and get the true ranking function values, respectively. The performance was investigated by the execution time, the true ranking function values, and the difference between the true ranking function values and the approximate ranking function values.All MC-TAG-K, B-MCTS, and RN-MCTS algorithms are implemented using Matlab R2019a running on a PC with Intel Core i7-7700K 4.2 GHz CPU, 16 GB RAM, Windows 10 operating system, and MySql 5.7 database. All the experimental results are averaged based on five independent runs.


## 5.3. Experimental Results and Analysis

### 5.3.1. Exp-1: Effectiveness

This experiment is to investigate the effectiveness of our RN-MCTS by comparing the average ranking function values of the top-K matches based on different settings of parameters.Results. Figures 2 and 3 and Table 3 depict the average ranking function values of TAG-K results with different settings of parameters under MC-TAG-K, B-MCTS, and RN-MCTS. From these figures, we can see that the average ranking function values returned by MC-TAG-K are always less than that of B-MCTS and RN-MCTS. Overall, the average true function value delivered by RN-MCTS is 15.92% and 10.04% more than that of MC-TAG-K and B-MCTS, respectively.Figure 2
The average ranking function value based on different constrains.
(a)
(b)
(c)
(d)
(e)Figure 3
The average ranking function value based on different iterations.
(a)
(b)
(c)
(d)
(e)Table 3
The difference between approximate and true ranking function values.
citHepTh
Slashdot
DBLP
Twitter
YouTube
MC-TAG-K
0.0891
0.0953
0.1275
0.1324
0.1277
B-MCTS
0.0542
0.0465
0.0752
0.0846
0.0861
RN-MCTS
0.0475
0.0412
0.0624
0.0718
0.0724Analysis. The experimental results illustrate that (1) the approximate ranking function values returned by MC-TAG-K have a large deviation with the true ranking function values; (2) RN-MCTS and B-MCTS can deliver more accurate approximate ranking function values by using the neural network and MCTS; therefore, RN-MCTS and B-MCTS can get better matching results than MC-TAG-K; (3) with the assistance of neural network and optimal strategy, RN-MCTS can avoid the MCT search via a subgraph that has a lower probability to satisfy the constraints and then outperforms B-MCTS.


### 5.3.2. Exp-2: Efficiency

This experiment is to investigate the efficiency of our RN-MCTS by comparing the average query processing time of MC-TAG-K, RN-MCTS, and B-MCTS based on different settings of parameters.Results. Figures 4 and 5 depict the average query processing time of the three algorithms in returning different numbers of designed nodes with different setting of parameters. From these figures, we can see that RN-MCTS and B-MCTS have better efficiency than MC-TAG-K. Statistically, on average, the query processing time of RN-MCTS is 75.30% less than that of MC-TAG-K and 17.30% more than that of B-MCTS.Figure 4
The average query processing time based on different constrains.
(a)
(b)
(c)
(d)
(e)Figure 5
The average query processing time based on different iterations.
(a)
(b)
(c)
(d)
(e)Analysis. The experimental results illustrate that (1) RN-MCTS can reduce the searching space and avoid to visit all nodes and edges in the data graph. Thus, RN-MCTS can greatly save the query processing time than MC-TAG-K; (2) because of the RNN structure, each iteration of RN-MCTS costs more time than B-MCTS.


## 5.3.1. Exp-1: Effectiveness

This experiment is to investigate the effectiveness of our RN-MCTS by comparing the average ranking function values of the top-K matches based on different settings of parameters.Results. Figures 2 and 3 and Table 3 depict the average ranking function values of TAG-K results with different settings of parameters under MC-TAG-K, B-MCTS, and RN-MCTS. From these figures, we can see that the average ranking function values returned by MC-TAG-K are always less than that of B-MCTS and RN-MCTS. Overall, the average true function value delivered by RN-MCTS is 15.92% and 10.04% more than that of MC-TAG-K and B-MCTS, respectively.Figure 2
The average ranking function value based on different constrains.
(a)
(b)
(c)
(d)
(e)Figure 3
The average ranking function value based on different iterations.
(a)
(b)
(c)
(d)
(e)Table 3
The difference between approximate and true ranking function values.
citHepTh
Slashdot
DBLP
Twitter
YouTube
MC-TAG-K
0.0891
0.0953
0.1275
0.1324
0.1277
B-MCTS
0.0542
0.0465
0.0752
0.0846
0.0861
RN-MCTS
0.0475
0.0412
0.0624
0.0718
0.0724Analysis. The experimental results illustrate that (1) the approximate ranking function values returned by MC-TAG-K have a large deviation with the true ranking function values; (2) RN-MCTS and B-MCTS can deliver more accurate approximate ranking function values by using the neural network and MCTS; therefore, RN-MCTS and B-MCTS can get better matching results than MC-TAG-K; (3) with the assistance of neural network and optimal strategy, RN-MCTS can avoid the MCT search via a subgraph that has a lower probability to satisfy the constraints and then outperforms B-MCTS.


## 5.3.2. Exp-2: Efficiency

This experiment is to investigate the efficiency of our RN-MCTS by comparing the average query processing time of MC-TAG-K, RN-MCTS, and B-MCTS based on different settings of parameters.Results. Figures 4 and 5 depict the average query processing time of the three algorithms in returning different numbers of designed nodes with different setting of parameters. From these figures, we can see that RN-MCTS and B-MCTS have better efficiency than MC-TAG-K. Statistically, on average, the query processing time of RN-MCTS is 75.30% less than that of MC-TAG-K and 17.30% more than that of B-MCTS.Figure 4
The average query processing time based on different constrains.
(a)
(b)
(c)
(d)
(e)Figure 5
The average query processing time based on different iterations.
(a)
(b)
(c)
(d)
(e)Analysis. The experimental results illustrate that (1) RN-MCTS can reduce the searching space and avoid to visit all nodes and edges in the data graph. Thus, RN-MCTS can greatly save the query processing time than MC-TAG-K; (2) because of the RNN structure, each iteration of RN-MCTS costs more time than B-MCTS.


## 6. Conclusion and Future Work

In this paper, we have proposed an approximate algorithm RN-MCTS to support a new type context-aware graph pattern-based top-K designated node finding problem that is a corner stone for many social network-based applications. RN-MCTS achievesOIDNc in time cost, and the experiments conducted on five real-world large-scale social graphs have demonstrated the superiority of our proposed approaches in terms of effectiveness and efficiency.In our future work, we will extend our model to solve the dynamic node matching problem in complex social graphs.



---

*Source: 7909826-2020-02-26.xml*