Neighborhood-based link prediction for recommendation systems
A recommendation system implements a linkage (connectivity) score learning algorithm for user-item interaction bipartite graphs that is combined with a lightweight iterative degree update process in the bipartite graph where the degrees used in the scoring formula are updated several times to exploit local graph structures without any node (user/item) modeling. In the linkage score learning algorithm, for user u1 and item i2, the predicted linkage score between them is the sum over all sub-scores of each 3-step linkage path between u1 and i2. The linkage score learning algorithm pre-defines 6 learnable candidate parameter values, selects the best combination of parameters, and predicts a set of linkage scores that can be used for recommendation systems. The linkage score learning algorithm addresses the problem of link prediction by predicting new links in a graph that do not already exist in training data.
1 . A search system for searching a dataset of user and item nodes to identify at least one item in the dataset to recommend to a user, comprising:
a user-item bipartite graph of nodes connecting at least one user and the at least one item; and
a processor that recommends the at least one item in the user-item bipartite graph to the user by executing instructions to perform operations comprising:
computing linkage scores from the user-item bipartite graph to weigh propagated links between respective nodes of the user-item bipartite graph from user u to an item i to be searched as inversely proportional to a number of nodes of the user-item bipartite graph connecting the user u to the item i, wherein computing the linkage scores comprises computing a linkage score ŷ for all user-item pairs of length 3 from a node degrees set P including a number of nodes of the user-item bipartite graph and every path of length 3 between user-item pairs ((u,i) pairs) as:
y
ˆ
(
i
2
|
u
1
)
∑
(
ix
,
ux
)
∈
P
(
u
1
,
i
2
)
(
d
u
1
a
·
d
ix
β
·
d
ux
γ
·
d
i
2
δ
)
-
1
for intermediate nodes ix and ux between user node u1 and item node i2 in the user-item bipartite graph, where d is a node degree of respective nodes of the user-item bipartite graph of respective paths of length 3 between each user and item and α, β, γ, δ are learnable input parameters;
sorting the propagated links in the user-item bipartite graph by linkage scores;
adding a top predetermined percent of new propagated links with highest linkage scores to the user-item bipartite graph to obtain an updated user-item bipartite graph;
repeating computing linkage scores, sorting the propagated links, and adding the new propagated links using the updated user-item bipartite graph to obtain a final recommendation search matrix;
performing a search of the dataset for the at least one item to recommend to the user using the final recommendation search matrix; and
displaying, based on a result of the search, the at least one item to the user on a user interface.
2 . The system of claim 1 , wherein the processor executes instructions to compute linkage scores from the user-item bipartite graph by executing instructions to preprocess the user-item bipartite graph to obtain the node degrees set P.
3 . The system of claim 2 , wherein the processor executes instructions to compute linkage scores from the user-item bipartite graph by further executing instructions to compute the linkage scores using the node degrees for every path of length 3 between the user-item pairs from set P and to accumulate the computed linkage scores.
4 . The system of claim 3 , wherein the processor executes instructions to compute linkage scores from the user-item bipartite graph by further executing instructions to compute the linkage score for all user-item pairs of length 3 as a function of (1) the node degree d of respective nodes of the user-item bipartite graph of respective paths of length 3 between each user and item and (2) the learnable input parameters.
5 . The system of claim 4 , wherein the processor further executes instructions to optimize the learnable input parameters using a training algorithm.
6 . The system of claim 1 , wherein the processor further executes instructions to compute linkage scores from the user-item bipartite graph by executing instructions to compute the final recommendation search matrix L as:
L
=
(
D
α
,
β
⊙
M
)
M
T
(
M
⊙
D
γ
,
δ
)
where ⊙ indicates a Hadamard product, D α,β is a matrix version of d α u1 ·d β ix , D γ,δ is a matrix version of d γ ux ·d δ i2 , a number of paths of length 3 between a node u and i is given by [(MM T )M] ui where M T is a transpose of matrix M, and L j,k =ŷ(i k |u j ) for respective items i k and respective users u j .
7 . A computer-implemented method of searching a dataset of nodes to identify at least one item in the dataset to recommend to a user using a user-item bipartite graph of nodes connecting at least one user and the at least one item, the method comprising:
computing linkage scores from the user-item bipartite graph to weigh propagated links between respective user and item nodes of the user-item bipartite graph from a user u to an item i to be searched as inversely proportional to a number of nodes of the user-item bipartite graph connecting the user u to the item i, wherein computing the linkage scores comprises computing a linkage score ŷ for all user-item pairs of length 3 from a node degrees set P including a number of nodes of the user-item bipartite graph and every path of length 3 between user-item pairs ((u,i) pairs) as:
y
ˆ
(
i
2
|
u
1
)
∑
(
ix
,
ux
)
∈
P
(
u
1
,
i
2
)
(
d
u
1
a
·
d
ix
β
·
d
ux
γ
·
d
i
2
δ
)
-
1
for intermediate nodes ix and ux between user node u1 and item node i2 in the user-item bipartite graph, where d is a node degree of respective nodes of the user-item bipartite graph of respective paths of length 3 between each user and item and α, β, γ, δ are learnable input parameters;
sorting the propagated links in the user-item bipartite graph by linkage scores;
adding a top predetermined percent of new propagated links with highest linkage scores to the user-item bipartite graph to obtain an updated user-item bipartite graph;
repeating computing linkage scores, sorting the propagated links, and adding the new propagated links using the updated user-item bipartite graph to obtain a final recommendation search matrix; and
performing a search of the dataset for the at least one item to recommend to the user using the final recommendation search matrix; and
displaying, based on a result of the search, the at least one item to the user on a user interface.
8 . The method of claim 7 , wherein computing linkage scores from the user-item bipartite graph comprises preprocessing the user-item bipartite graph to obtain the node degrees set P.
9 . The method of claim 8 , wherein computing linkage scores from the user-item bipartite graph further comprises computing the linkage scores using the node degrees for every path of length 3 between the user-item pairs from set P and accumulating the computed linkage scores.
10 . The method of claim 9 , wherein computing linkage scores from the user-item bipartite graph further comprises computing the linkage score for all user-item pairs of length 3 as a function of (1) the node degree d of respective nodes of the user-item bipartite graph of respective paths of length 3 between each user and item and (2) the learnable input parameters.
11 . The method of claim 10 , further comprising optimizing the learnable input parameters using a training algorithm.
12 . The method of claim 7 , wherein computing linkage scores from the user-item bipartite graph further comprises computing the final recommendation search matrix L as:
L
=
(
D
α
,
β
⊙
M
)
M
T
(
M
⊙
D
γ
,
δ
)
where ⊙ indicates a Hadamard product, D α,β is a matrix version of d α u1 ·d β ix , D γ,δ is a matrix version of d γ ux ·d δ i2 , a number of paths of length 3 between a node u and i is given by [(MM T )M] ui where M T is a transpose of matrix M, and L j,k =ŷ(i k |u j ) for respective items i k and respective users u j .
13 . A non-transitory computer-readable storage medium, the computer-readable storage medium including instructions that when executed by a processor cause the processor to search a dataset of user and item nodes to identify at least one item in the dataset to recommend to a user using a user-item bipartite graph of nodes connecting at least one user and the at least one item by performing operations comprising:
computing linkage scores from the user-item bipartite graph to weigh propagated links between respective nodes of the user-item bipartite graph from a user u to an item i to be searched as inversely proportional to a number of nodes of the user-item bipartite graph connecting user u to the item i, wherein computing the linkage scores comprises computing a linkage score ŷ for all user-item pairs of length 3 from a node degrees set P including a number of nodes of the user-item bipartite graph and every path of length 3 between user-item pairs ((u,i) pairs) as:
y
ˆ
(
i
2
|
u
1
)
∑
(
ix
,
ux
)
∈
P
(
u
1
,
i
2
)
(
d
u
1
a
·
d
ix
β
·
d
ux
γ
·
d
i
2
δ
)
-
1
for intermediate nodes ix and ux between user node u 1 and item node i 2 in the user-item bipartite graph, where d is a node degree of respective nodes of the user-item bipartite graph of respective paths of length 3 between each user and item and α, β, γ, δ are learnable input parameters;
sorting the propagated links in the user-item bipartite graph by linkage scores;
adding a top predetermined percent of new propagated links with highest linkage scores to the user-item bipartite graph to obtain an updated user-item bipartite graph;
repeating computing linkage scores, sorting the propagated links, and adding the new propagated links using the updated user-item bipartite graph to obtain a final recommendation search matrix;
performing a search of the dataset for the at least one item to recommend to the user using the final recommendation search matrix; and
displaying, based on a result of the search, the at least one item to the user on a user interface.
14 . The computer-readable storage medium of claim 13 , wherein the instructions for computing linkage scores from the user-item bipartite graph comprise instructions for preprocessing the user-item bipartite graph to obtain the node degrees set P.
15 . The computer-readable storage medium of claim 14 , wherein the instructions for computing linkage scores from the user-item bipartite graph further comprise instructions for computing the linkage scores using the node degrees for every path of length 3 between the user-item pairs from set P and accumulating the computed linkage scores.
16 . The computer-readable storage medium of claim 15 , wherein the instructions for computing linkage scores from the user-item bipartite graph further comprise instructions for computing the linkage score for all user-item pairs of length 3 as a function of the node degree d of respective nodes of the user-item bipartite graph of respective paths of length 3 between each user and item and the learnable input parameters.
17 . The computer-readable storage medium of claim 16 , wherein the instructions further comprise instructions for optimizing the learnable input parameters using a training algorithm.