JP2014021862A - Associated node searching device, associated node searching method and program - Google Patents

Abstract

An object of the present invention is to quickly and accurately search a number of nodes having high relevance based on PPR or nodes within a threshold.
Relevance is calculated based on PPR (Personalized PageRank) from graph data consisting of a plurality of nodes and a query distribution, and K nodes are searched in descending order of relevance, or the relevance is greater than a predetermined threshold. In the related node search device for searching for nodes having a node, the inverse matrix of the unitary matrix and the upper triangular matrix used for calculating the degree of association of a specific node based on the PPR is calculated from the graph data and stored in the storage means Search for K nodes in descending order of relevance using the pre-calculation means, the query distribution, and the inverse matrix of the unitary matrix and upper triangular matrix obtained by the pre-calculation means, or greater than a predetermined threshold Searching means for searching for and outputting nodes having relevance.
[Selection] Figure 1

Description

  The present invention relates to a technique for calculating a degree of association based on a personalized page rank and performing a search.

  Graphs are data structures that represent data with nodes and edges, and are used in various fields. In recent years, interest in personalized search using graphs has increased. An example of a personalized search is a service that makes recommendations individually from an individual purchase history.

  Node relevance is one of the important properties in graph theory, and various methods have been proposed for node relevance. Among them, Personalized PageRank (PPR) is one of the things that attracts the most attention as the degree of relevance of nodes. This is because PPR can calculate the degree of relevance based on the structural features of the graph, unlike the shortest distance between nodes that has been often used in graph theory so far (Non-Patent Documents 1 and 2).

  PPR can be conceptually explained as follows. A random walk is started from the existence probability of each node based on the inquiry distribution, and the node randomly moves to an adjacent node with a probability proportional to the edge weight. Furthermore, every time the node is reached, the node returns to the node with a probability based on the query distribution with a certain probability. As a result of recursively repeating this operation, a steady state probability at each node is obtained. PPR is a method in which the obtained steady state probability is used as a degree of relevance.

Glen Jeh and Jennifer Widom, Scaling personalized web search, WWW, 2003 Hanghang Tong and Christos Faloutsos, Center-piece subgraphs: problem definition and fast solutions, KDD, 2006 D′ aniel Fogaras and Bal′azs R′acz and K′aroly Csalog′any and Tam′as Sarl′os, Towards Scaling Fully Hanghang Tong and Christos Faloutsos and Jia-Yu Pan, Fast Random Walk with Restart and Its Applications, ICDM, 2006 Jimeng Sun and Huiming Qu and Deepayan Chakrabarti and Christos Faloutsos, Neighborhood Formation and Anomaly Detection in Bipartite Graphs, ICDM, 2005 Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 2001 David A. Harville, Matrix Algebra From a Statistician's Perspective. Springer, 2008

  PPR is a degree of relevance applied to applications in various fields, but there is a problem that the calculation amount is high. Therefore, various speed-up methods have been proposed so far (Non-Patent Documents 3, 4, and 5), but they sacrifice accuracy. However, it is not preferable that accuracy is sacrificed when considering application to an application. In an actual application, the relevance of all other nodes is not calculated from the query distribution, but processing of nodes with high relevance is performed (Non-Patent Document 5).

  The present invention has been made in view of the above points, and when a query distribution and the number of searches or a threshold value are given, the number of nodes having a high degree of relevance based on PPR or the nodes within the threshold value for the query distribution An object of the present invention is to provide a technique that enables a high-speed and accurate search for a computer.

In order to solve the above problems, the present invention calculates the relevance based on PPR (Personalized PageRank) from graph data consisting of a plurality of nodes and a query distribution, and searches for K nodes in descending order of relevance. Or a related node search device for searching for a node having a relevance greater than a predetermined threshold,
From the graph data, a unitary matrix used to calculate the degree of association of a specific node based on PPR and an inverse matrix of an upper triangular matrix are calculated, and a pre-calculating unit that stores the matrix in a storage unit;
Using the inquiry distribution and the inverse matrix of the unitary matrix and upper triangular matrix obtained by the pre-calculation means, search for K nodes in descending order of relevance, or nodes having relevance greater than a predetermined threshold It is comprised as a related node search apparatus characterized by including the search means which searches for and outputs.

The pre-calculating means rearranges the nodes in the graph data so that the unitary matrix and the inverse matrix of the upper triangular matrix are sparse, and stores the graph data in which the nodes are rearranged in the storage means Rearrangement means; and inverse matrix calculation means for calculating an inverse matrix of the unitary matrix and the upper triangular matrix using the graph data in which the nodes are rearranged by the node rearrangement means,
The search means estimates a lower limit value of the relevance level for all nodes based on an adjacency matrix of the graph and the query distribution, and a relevance level estimation means for estimating an upper limit value of the relevance level based on the lower limit value; For a specific node, it may be configured to include relevance calculation means for calculating relevance using the unitary matrix and the inverse matrix of the upper triangular matrix.

  Further, in the search means, the relevance estimation means searches the nodes until the upper limit of the relevance is less than the Kth relevance or less than the predetermined threshold in descending order of the lower limit. While the upper limit value is less than the Kth relevance level or less than the predetermined threshold, the relevance calculation unit calculates an accurate relevance level to search K nodes in descending order of relevance level, or A node having a degree of relevance greater than the predetermined threshold may be searched.

  The present invention can also be configured as a related node search method executed by the related node search apparatus. Furthermore, the present invention can also be configured as a program for causing a computer to function as each means in the related node search apparatus.

  According to the present invention, the relevance of a specific node is calculated using a sparse matrix, and unnecessary relevance calculation is omitted in the search. it can. In addition, the search result according to the present invention is accurate, and further, there is an effect that the user does not need to adjust parameters for the present invention.

It is a functional block diagram of the related node search apparatus 1 which concerns on embodiment of this invention. It is a functional block diagram of the prior calculation part 10 which concerns on embodiment of this invention. It is a functional block diagram of the search part 20 which concerns on embodiment of this invention. It is a figure which shows the algorithm 1 which is an algorithm of the replacement | exchange of a node. It is a flowchart of node replacement. It is a figure which shows the algorithm 2 which is an algorithm of a top K piece search. It is a flowchart of a top K piece search. It is a figure which shows the algorithm 3 which is an algorithm of a range search. It is a flowchart of a range search.

  Embodiments of the present invention will be described below with reference to the drawings. The embodiment described below is only an example, and the embodiment to which the present invention is applied is not limited to the following embodiment.

(Basic configuration of the device)
An outline of the configuration and functions of the related node search device 1 according to the present embodiment will be described with reference to FIGS.

  FIG. 1 is a functional configuration diagram of a related node search device 1 according to the present embodiment. As shown in FIG. 1, the related node search device 1 according to the present embodiment includes a pre-calculation unit 10 and a search unit 20. The pre-calculation unit 10 receives the graph data as an external input and outputs an inverse matrix of the unitary matrix and the upper triangular matrix. The search unit 20 receives the unitary matrix and the inverse matrix of the upper triangular matrix from the pre-calculation unit 10 and receives the query distribution, the number of searches, and the like from the outside. Based on these inputs, the search unit 20 outputs related nodes that are search results.

  FIG. 2 shows a functional configuration of the pre-calculation unit 10. As illustrated in FIG. 2, the prior calculation unit 10 includes a node rearrangement unit 11 and an inverse matrix calculation unit 12. The node rearrangement unit 11 receives a graph, rearranges the nodes of the graph, and outputs the result. The output rearranged graph data is stored in a storage means such as a memory. The inverse matrix calculator 12 receives the graph in which the nodes are rearranged and outputs an inverse matrix of the unitary matrix and the upper triangular matrix. The output data of the inverse matrix of the unitary matrix and the upper triangular matrix is stored in the data storage unit 23 (storage means) described later.

  FIG. 3 shows a functional configuration of the search unit 20. As illustrated in FIG. 3, the search unit 20 includes a relevance level estimation unit 21, a relevance level calculation unit 22, a data storage unit 23, and a search processing control unit 24.

  The relevance estimation unit 21 receives the query distribution, the number of searches, and the like from the outside, the relevance calculated by the relevance calculation unit 22, and the search target node from the data storage unit 23. . Based on these inputs, the relevance level estimation unit 21 estimates the relevance level of the node, and stores the estimated relevance level in the data storage unit 23.

  The relevance calculation unit 22 receives an inverse matrix of a unitary matrix and an upper triangular matrix from the pre-calculation unit 10, and receives a search target node from the data storage unit 23. The relevance calculation unit 22 calculates the relevance level of the nodes based on these inputs, and outputs the calculated relevance level to the data storage unit 23.

  The search processing control unit 24 performs control such as determining a search target node so that processing is performed according to an algorithm described later, and outputs the search result to the outside.

  The related node search device 1 according to the present embodiment can be realized by causing a computer including a storage unit such as a CPU, a memory, and a hard disk to execute a program corresponding to the processing of the functional units described in the present embodiment. It is. The program may be stored in a storage medium such as a portable memory and distributed, installed on the computer, or downloaded from a server on a network and installed on the computer. Each calculation process described in the present embodiment is executed while the CPU reads and processes data stored in a storage unit such as a memory and stores the processed result in the storage unit. .

(Processing operation of related node search device 1)
Hereinafter, the principle and processing procedure of the processing contents executed by the related node search device 1 according to the embodiment of the present invention will be described in detail. In describing the embodiment, first, symbols used in this specification are defined, and necessary background knowledge is described.

<About PPR>
PPR is a way to calculate the relevance of graph nodes. In PPR, the existence probability of each node is determined from the query distribution, and a random walk is performed from the determined node. Each time a node is reached in a random walk, it returns to each node based on the query distribution with a certain probability c. Here, n is the number of nodes in the graph. Let s be an n × 1 matrix and represent the probability of a random walk of s _u elements to node u. Also, let d be an n × 1 matrix determined by the query distribution. Also, let A be an adjacency matrix of a graph with normalized columns (that is, the A _{u, v} element represents the probability of a random walk from node v to node u). The existence probability at each node in the steady state can be calculated by repeating the following expression until it converges recursively.
s = (1-c) As + cd (1)
PPR is a method that uses the probability in steady state as the relevance. That is, the s _u element of the s matrix is the degree of relevance to the distribution d of the node u.

  From the definition, when the number of repetitions is t, the calculation cost of PPR is O (mt). Therefore, it takes a very long time to calculate the PPR value when the graph is large.

<Principle of the technology according to the present embodiment>
The technique according to the present embodiment is roughly configured by the following two methods (sparse matrix calculation and relevance estimation).

(1) Sparse Matrix Calculation As described above, the degree of relevance to the query distribution can be obtained by calculating the probability in the steady state by iterative calculation. Since this method recursively calculates the relevance of all nodes in the graph, the calculation cost is high. Therefore, in the method according to the present embodiment, the relevance of all the nodes is not calculated, but only the relevance of the selected node is calculated to enable high-speed search.

The degree of relevance of the selected node can be calculated by using an inverse matrix obtained directly from the equation (1). Therefore, if this inverse matrix is calculated in advance, the relevance can be calculated at high speed. However, it is generally a problem that O (n ² ) memory is required to hold the inverse matrix.

  Therefore, in the method according to the present embodiment, in order to hold this inverse matrix as a sparse matrix, the QR decomposition is calculated by first rearranging the nodes in the search preprocessing, and the obtained unitary matrix and upper triangular matrix are calculated. Calculate the inverse matrix. Since the inverse matrix of the unitary matrix and the upper triangular matrix is a sparse matrix, the relevance of the selected node can be calculated from the sparse matrix by using the adjacent list representation (Non-patent Document 6).

(2) Estimation of relevance The relevance of the selected node can be calculated at high speed by the above sparse matrix calculation method. However, in order to search for the top K nodes, the relevance of all nodes must be calculated. Therefore, in the technique according to the present embodiment, the relevance is estimated in order to search at high speed. Specifically, the degree of association is estimated for each node, and an accurate degree of association is calculated using a sparse matrix only for nodes that are expected to have a high degree of association. Since the estimated value of the node can be calculated by O (1), the calculation of the relevance can be omitted with a small calculation cost. As will be described later, the estimated value of the relevance used in the present embodiment is guaranteed to be an accurate upper limit of the relevance, so that there is an advantage that the search result is accurate even if the estimation is used.

<Relationship calculation using sparse matrix, sparse matrix calculation>
Hereinafter, processing for calculating the degree of association of the selected node using the sparse matrix will be described in detail. First, it will be explained that the relevance of the selected node can be calculated from an inverse matrix, and a method for calculating the inverse matrix from a sparse matrix will be described.

When the matrix P and the node of the permutation matrix, the adjacency matrix of the graph A is converted into A '= through calculations that PAP ^T matrix A'. Here, the matrix P ^T is a transposed matrix of the matrix P. Here, the permutation matrix P having a size of n × n is an orthogonal matrix, and has an element having a single value of 1 in each row and column and an element having a value of 0 in the other cases. P _ij = 1 indicates that the j-th row is replaced with the i-th row.

Here, since I = P ^T IP, P ⁻¹ = P ^T , and A = P ^T AP (P ⁻¹ is an inverse matrix of P), Equation (1) can be rewritten as follows.
s = c {I- (1-c) A} ^-1 d = c {P ^T IP- (1-c) P ^T A′P} ^-1 d = cP ^T {I- (1-c) A ′ } ^-1 Pd (2)
In order to calculate the relevance of a specific node, the QR decomposition of the matrix I − (1 −c) A ′ is calculated in this embodiment. That is, QR = I− (1−c) A ′, where the matrix Q is an orthogonal matrix (unitary matrix), and the matrix R is an upper triangular matrix. Formally, the relevance of a specific node x is calculated as follows.

Definition 1: Given an n × n matrix F = cP ^T R ⁻¹ , an n × 1 vector g = Q ^T Pd, and a 1 × n vector f _i as the i-th row vector of the matrix F, the node x The degree of relevance s _x for the distribution d of can be calculated as follows.
s _x = f _x · g (3)
Relevance node x from equation (3) can be determined without repeatedly calculating the use of the vector f _x and g. Since the vector d is given by the user, it is necessary to calculate the vector g first in order to calculate the relevance.

  The following theorem holds for definition 1.

Theorem 1: If | f _x | and | Q | are the numbers of nonzero elements in f _x and Q, respectively, the amount of computation required to calculate the relevance of a particular node is O (| f _x | + | Q |)

Proof of Theorem 1: In this embodiment, in order to calculate the relevance, first, the vector g is calculated from the distribution d. Since the vector Pd can be obtained by replacing the node of the distribution d, the amount of calculation required to calculate the vector g = Q ^T Pd is O (| Q |). Since the calculation cost for calculating the inner product of the vectors f _x and g is O (| f _x | + | Q |), the amount of calculation required to calculate the relevance is O (| f _x | + | Q |)

Since F = cP ^T R ^-1 and g = Q ^T Pd, it is necessary to reduce the non-zero elements of the matrices R ^-1 and Q in order to calculate the relevance from Theorem 1 at high speed. Recognize. Therefore, in this embodiment, a method described later for reducing non-zero elements is used.

Before describing the method in detail, a method for calculating the matrices R ⁻¹ and Q will be described. If the vector q _i is the i-th column vector of the matrix Q and w _i is the i-th column vector of the matrix W = I-(1-c) A ′, then the matrices Q and R are Gram-Schmidt orthonormalization methods. (See Non-Patent Document 7).

Where || q ′ _i || is the norm of q ′ _i . The elements of the matrix R ⁻¹ can be calculated as follows by using backward substitution (see Non-Patent Document 7).

It can be seen from equations (4) and (5) that the column vectors of the matrices Q and R can be obtained by calculating the inner product of the orthogonal column vector and the matrix W from the left to the right column. It can be seen from equation (6) that the column vector of the matrix R ⁻¹ is obtained from the right to the left column, and the elements of each column vector are obtained in the order of the bottom to top elements. It can also be seen from equations (4), (5), and (6) that the matrices Q and R can be calculated from the matrix W.

In order to reduce non-zero elements of the matrix Q, the following knowledge is used in the present embodiment. "If column vector w _i has one non-zero element in matrix W where all left elements are all zero, then column vector w _i is orthogonal to all left column vectors of matrix Q. Become.". This is because the column vector w _i is linearly independent. Thus, the matrix Q has a sparse data structure.

The following two findings are used to make the matrix R ^-1 sparse. “If the right and bottom elements of matrix R are sparse, the right and bottom elements of matrix R ⁻¹ are also sparse.” “If the right and bottom elements of matrix W are sparse, the right and bottom elements of matrix R are also sparse.”

  FIG. 4 shows an algorithm 1 for a node replacement method for obtaining a sparse matrix. FIG. 5 shows a flowchart of processing executed by the node rearrangement unit 11 of the pre-calculation unit 10 corresponding to the algorithm 1.

The algorithm shown in FIG. 4 is based on knowledge of the matrices Q and R ⁻¹ . In this algorithm, V is a set of nodes in the graph, and set “P” is a set of replaced nodes. deg (u) is the number of edges that enter node u, and e (u) is the number of edges that have not exited node u from the set “P”. First, the node rearrangement unit 11 initializes the permutation matrix P to a zero matrix, and sets the set “P” as an empty set (first and second rows, step 11 in FIG. 5).

A node set U in which the number of edges is min {e (u) | uεV \ P} is calculated from the set V \ P of nodes that are not replaced (line 4, step 12). This process is based on knowledge of the matrix Q. If the right and bottom elements of the matrix A 'are sparse, the matrix R ^-1 will also be sparse, so select the node with the largest number of edges to make the left and top elements of the matrix A' dense (5th line, step 13). Then, the elements of the matrix P are determined from the selected node, and the order of replacement is determined (lines 6-7, steps 14 and 15).

<About estimation of relevance>
Next, the estimation of relevance will be described. In this method, in order to search for the top K nodes, the upper limit value of the relevance level of a node for which an accurate relevance level is not calculated during the search is estimated at high speed. In order to calculate the upper limit value of the relevance level, the lower limit value of the relevance level is first estimated in the present embodiment. The lower limit value of the relevance is calculated using the minimum number of hops from the seed node where the value of the given distribution does not become zero. The minimum number of hops from the seed node is calculated using a breadth-first search. Let h _{u be} the minimum number of hops from the seed node for node u, and H (i) be the set of nodes whose minimum hop number from the seed node is i. That is, H (i) constitutes the i-th layer, and H (0) is a set of seed nodes. In the present embodiment, the lower limit value of the relevance is calculated as follows.

Definition 2: The lower limit value s _{u of the} degree of association with the distribution d of the node u is defined as follows.

幅優先探索を用いることにより、すべてのノードに対して下限値を計算するには、O(n+m) の計算コストが必要になる。この下限値の性質を示すために以下の補助定理を示す。

Using the breadth-first search requires O (n + m) calculation cost to calculate the lower limit for all nodes. In order to show the property of this lower limit, the following lemma is shown.

Lemma 1: s _u ≤ s _u holds for all nodes included in H (i).

Proof of Lemma 1: Use mathematical induction for proof. First, we show that this holds for the nodes included in H (0). In PPR, the random walk reaches the seed node in two cases: (1) the random walk jumps to the seed node with probability c, or (2) the random walk reaches the seed node in the process. In the case of (1), the random walk jumps to a certain seed node u with a probability cd _u . Therefore, the probability of the seed node u in the steady state does not become smaller than cd _u . Therefore, this holds for nodes included in H (0).

Next, when s _v ≦ s _v holds for the nodes included in H (i−1), it is shown that s _v ≦ s _v holds for the nodes included in H (i). The nodes included in H (i-1) are a subset of the nodes of the entire graph, and c and du ≥ 0, so the following holds in equation (1).

Therefore, Lemma 1 holds.

In this embodiment, in order to search for the top K nodes, each node is traced one by one to calculate the upper limit value and the exact degree of association. The upper limit value of the relevance level is calculated using the lower limit value of the relevance level, and the upper limit value of the relevance level is calculated as follows when u _i is the i-th tracing node.

Definition 3: node u _i

Is defined as follows:

  The computational cost of calculating the upper limit is O (n) if i = 1. If not, the upper limit has already been calculated

Since the calculation can be performed sequentially using, the calculation cost is O (1).

  In this embodiment, the nodes are traced in descending order of the lower limit of the relevance level. There are two reasons for this. The first reason is that it is expected that the larger the lower limit value, the larger the accurate lower limit value. Therefore, the top K nodes can be searched efficiently. The second reason is that the processing is stopped in the middle of the search by the following theorem and the search is performed at a higher speed.

  Lemma 2: When following the nodes in descending order of the lower limit of relevance,

Holds.

  Proof: First

Show that. From Equation (8) and Lemma 1, the following equation holds.

Next,

Indicates that From equation (8)

It becomes. Therefore it holds.

FIG. 6 shows algorithm 2 for searching for the top K nodes. FIG. 7 shows a flowchart of processing executed in the search unit 20 in accordance with this algorithm. Is θ in the algorithm 2 is K-th relevance in the node set of candidate solutions, V _a is the node set of candidate solutions, V _e is the searched-node set. In this process, the relevance estimation unit 21 in the search unit 20 calculates the lower limit and upper limit of the relevance, and the relevance calculation unit 22 calculates the correct relevance. The data storage unit 23 stores calculation result data, mid-calculation data, matrix data necessary for the calculation, and other data necessary for the calculation. The search processing control unit 24 performs processing control so that the processing is performed according to the algorithm 2, and performs control to output a final result (K related nodes).

In the algorithm 2, after initialization, the relevance estimation unit 21 adds K dummy nodes having _a relevance of 0 to Va as data to be stored in the data storage unit 23 (line 4, FIG. 7). Step 22). Then, the relevance estimation unit 21 calculates a lower limit value of relevance for all nodes (5th line, step 23). Then, the node having the highest relevance value is selected from the unsearched node set V \ V _e stored in the data storage unit 23, and the relevance value upper limit value of the selected node is calculated (7). -8th line, steps 24, 25). When the upper limit value of the relevance of the node selected from Lemma 2 is smaller than θ, the node and the unsearched node cannot be the solution node. Therefore, in that case, the relevance estimation unit 21 stops the processing (9th to 10th lines, steps 26 and 27).

If not, the selected node can be the solution. Therefore, the relevance calculation unit 22 calculates the exact relevance of the node (12th line, step 28). If the calculated relevance is greater than theta, relevance calculator 22 updates the set V _a and K th relevance theta candidate solutions in the data storage unit 23 (13-18 line, step 29-33) .

  The following theorem is shown to show that this algorithm can search the solution node accurately.

  Theorem 2: Algorithm 2 searches the top K nodes accurately.

Proof of Theorem 2: When θ _K is the Kth relevance level at the solution node, the upper limit value of the relevance level of the solution node is never smaller than θ _K (Lemma Theorem 2). If the upper limit of relevance is smaller than θ, algorithm 2 prunes the node. The K-th relevance θ in the solution candidate node set never becomes larger than θ _K , so that the solution node is not pruned by the algorithm 2. If a node is smaller than θ, the node is pruned by algorithm 2. Therefore, Theorem 2 holds.
The calculation cost required to search the top K nodes is as follows.

  Theorem 3: Algorithm 2 requires O (n log n + m + | F | + | Q |).

  Proof of Theorem 3: Algorithm 2 first calculates the lower limit of relevance for all nodes, but the lower limit can be calculated by a breadth-first search that requires O (n + m) calculation costs. Then select the node with the highest lower relevance value and calculate the upper relevance value, but if no nodes are pruned, these calculate O (n log n) and O (n) respectively. Cost is required.

Therefore, calculating the relevance of all nodes from Theorem 1 requires O (| F | + | Q |) calculation cost. Therefore, in order to search the top K nodes, a calculation cost of O (n log n + m + | F | + | Q |) is required.

<Range search for nodes with relevance greater than threshold ε>
Although the method of searching for the top K nodes has been described so far, the related node search apparatus 1 according to this embodiment can also search for a node having a degree of association greater than the threshold ε. That is, the related node search apparatus 1 according to the present embodiment can perform a range search for nodes having a relevance greater than the threshold ε. Details will be described below.

  The lower limit value of the degree of association is used to search for nodes having a degree of association greater than the threshold ε. Specifically, if the lower limit value of the relevance level of a certain node is larger than the threshold value ε, the correct relevance level of the node is obviously larger than the threshold value ε. Therefore, the calculation of the correct relevance for such a node is omitted. As in the case of searching for the upper K nodes, the nodes are searched in the descending order of the lower limit value. Then, the upper limit value of the relevance level is calculated, and the unnecessary relevance level calculation is omitted. However, if accurate relevance is not calculated, the upper limit cannot be calculated using Definition 3. Therefore, if the calculation of the correct relevance is omitted, the upper limit value of the relevance is calculated as follows.

Definition 4: If the exact relevance calculation of node u _i-1 is omitted, node u _i

Is calculated as follows.

  The following lemma for this definition is shown.

Lemma 3: For node u _i searched for i-th definition 4

Holds. The calculation cost for calculating the upper limit is O (1) if i ≠ 1.

  Proof of Lemma 3: First

Show that. If V _i-1 is a set of nodes searched up to i −1 and V _e is a set of nodes searched up to i −1, the exact relevance is calculated. From Lemma 1, the following equation holds.

Next

Indicates that From equation (9)

It becomes.

  Next, we show that if the calculation cost is i ≠ 1, then O (1). this is

Already before calculating

It is clear from the fact that has been calculated. Therefore it holds.

  FIG. 8 shows a range search algorithm 3. FIG. 9 shows a flowchart of range search executed by the search unit 20 according to the algorithm 3. In this process, the relevance estimation unit 21 in the search unit 20 calculates the lower limit and upper limit of the relevance based on the algorithm 3, and the relevance calculation unit 22 calculates the correct relevance. The data storage unit 23 stores calculation result data, mid-calculation data, matrix data necessary for the calculation, and other data necessary for the calculation. The search processing control unit 24 performs process control so that the process is performed according to Algorithm 3, and performs control to output a final result (related node that satisfies a condition).

  In this algorithm 3, after initialization, the relevance estimation unit 21 calculates a lower limit value of relevance for all nodes (third line, step 41 in FIG. 9). Then, the node having the highest relevance value is selected from the set of unsearched nodes stored in the data storage unit 23, and the relevance estimation unit 21 calculates the relevance value of the selected node. (5th to 6th lines, steps 43 and 44). If the upper limit is not greater than ε, the node and unsearched nodes cannot be solution nodes. Therefore, in that case, the relevance estimation unit 21 stops the processing (7th to 8th lines, steps 45 and 46).

  If the lower limit value of the selected node is larger than ε, the node becomes a solution node. Therefore, the relevance estimation unit 21 adds the node to the set of solution nodes in the data storage unit 23 (9th to 10th lines, steps 47 and 48). Otherwise, the relevance calculation unit 22 calculates an accurate relevance, and checks whether or not the selected node is a solution node (11th to 16th lines, steps 49 to 51).

  The following shows that the range search can be accurately performed by the algorithm 3.

  Theorem 4: Algorithm 3 performs a range search exactly at the computational cost of O (n log n + m + | F | + | Q |).

  First, Algorithm 3 shows that the range search is performed correctly. If the upper limit value of the selected node is smaller than ε, algorithm 3 prunes that node and other unsearched nodes. Algorithm 3 also prunes the selected node if the exact relevance of the selected node is less than ε. Since the upper limit value of the unsearched nodes is never smaller than the upper limit value of the selected node, these nodes are not included in the set of solution nodes.

  In addition, when the lower limit value and the exact relevance of the selected node are larger than ε, the algorithm 3 sets that node as a solution node. Therefore, algorithm 3 performs a range search accurately.

  Next, algorithm 3 shows that the range search is performed at a calculation cost of O (n log n + m + | F | + | Q |). Algorithm 3 first calculates the lower limit of the relevance level for all nodes, but the lower limit can be calculated by a breadth-first search that requires O (n + m) calculation costs. The node with the highest relevance value is selected and the upper relevance value is calculated. If no node is pruned, these are the calculation costs of O (n log n) and O (n), respectively. Cost.

Therefore, calculating the relevance of all nodes from Theorem 1 requires O (| F | + | Q |) calculation cost. Therefore, in order to search the top K nodes, a calculation cost of O (n log n + m + | F | + | Q |) is required. Therefore, Theorem 4 holds.

  The present invention is not limited to the above-described embodiments, and various modifications and applications are possible within the scope of the claims.

DESCRIPTION OF SYMBOLS 1 Related node search apparatus 10 Prior calculation part 11 Node rearrangement part 12 Inverse matrix calculation part 20 Search part 21 Relevance degree estimation part 22 Relevance degree calculation part 23 Data storage part 24 Search process control part

Claims (7)

Calculate the relevance based on PPR (Personalized PageRank) from graph data consisting of multiple nodes and query distribution, and search for K nodes in descending order of relevance, or nodes with relevance greater than a predetermined threshold A related node search device for searching,
From the graph data, a unitary matrix used to calculate the degree of association of a specific node based on PPR and an inverse matrix of an upper triangular matrix are calculated, and a pre-calculating unit that stores the matrix in a storage unit;
Using the inquiry distribution and the inverse matrix of the unitary matrix and upper triangular matrix obtained by the pre-calculation means, search for K nodes in descending order of relevance, or nodes having relevance greater than a predetermined threshold And a search means for searching for and outputting the related node search device. The pre-calculating means is
Reordering the nodes in the graph data so that the unitary matrix and the inverse matrix of the upper triangular matrix are sparse, and node reordering means for storing the reordered nodes in the storage means;
Inverse matrix calculation means for calculating an inverse matrix of the unitary matrix and the upper triangular matrix using the graph data in which the nodes are rearranged by the node rearrangement means,
The search means includes
Relevance estimation means for estimating a lower limit of relevance for all nodes based on an adjacency matrix of the graph and the query distribution, and estimating an upper limit of relevance based on the lower limit;
The related node search device according to claim 1, further comprising: a relevance level calculating unit that calculates a relevance level for a specific node using an inverse matrix of the unitary matrix and the upper triangular matrix. In the search means,
The relevance level estimation means searches for nodes until the upper limit value of the relevance level is less than the Kth relevance level or less than the predetermined threshold in descending order of the lower limit value, and the upper limit value of the relevance level is the Kth While the degree of relevance is not less than or less than the predetermined threshold value, the relevance degree calculating means calculates the exact relevance degree, thereby searching for K nodes in descending order of the relevance degree, or larger than the predetermined threshold value. The related node search device according to claim 2, wherein a node having a relevance level is searched. Calculate the relevance based on PPR (Personalized PageRank) from graph data consisting of multiple nodes and query distribution, and search for K nodes in descending order of relevance, or nodes with relevance greater than a predetermined threshold A related node search method executed by a related node search device to search,
A pre-calculation step of calculating a unitary matrix and an inverse matrix of an upper triangular matrix used for calculating the relevance of a specific node based on the PPR from the graph data, and storing in a storage unit;
Using the inquiry distribution and the inverse matrix of the unitary matrix and upper triangular matrix obtained by the pre-calculation means, search for K nodes in descending order of relevance, or nodes having relevance greater than a predetermined threshold And a retrieval step for retrieving and outputting the related node. The pre-calculation step includes
Reordering the nodes in the graph data so that the unitary matrix and the inverse matrix of the upper triangular matrix are sparse, respectively, and a node reordering step of storing the reordered nodes in the storage means;
An inverse matrix calculation step of calculating an inverse matrix of the unitary matrix and the upper triangular matrix using the graph data in which the nodes are rearranged by the node rearrangement step, and
The search step includes
A relevance estimation step for estimating a lower limit value of relevance for all nodes based on an adjacency matrix of the graph and the query distribution, and estimating an upper limit value of relevance based on the lower limit;
The related node search method according to claim 4, further comprising: a relevance level calculating step of calculating a relevance level for a specific node using an inverse matrix of the unitary matrix and the upper triangular matrix. In the search step,
The relevance level estimation step searches for nodes until the upper limit value of the relevance level is less than the Kth relevance level or less than the predetermined threshold in descending order of the lower limit value, and the upper limit value of the relevance level is the Kth While the degree of relevance is less than or less than the predetermined threshold, K nodes are searched in descending order of the degree of relevance by calculating an accurate degree of relevance in the relevance degree calculating step, or larger than the predetermined threshold The related node search method according to claim 5, wherein a node having a relevance level is searched.   The program for functioning a computer as each means in the related node search apparatus of any one of Claims 1 thru | or 3.

Images