SimRank++ similarity algorithm

Algorithm overview

SimRank is a method for measuring the similarity between entities in a structural context. The core idea is that if two objects, a and b, are related to two other objects, c and d, and c and d are known to be similar, then a and b are also considered similar. The similarity of any node to itself is 1. SimRank uses the known similarity between some entities to infer the similarity between other related entities.

The SimRank algorithm is based on a simple and intuitive graph-theoretic model. It models objects and their relationships as a directed graph G = (V, E), where V is the set of nodes representing all objects in the application domain, and E is the set of edges representing the relationships between objects. For a node in the graph, the set of its in-neighbors is denoted as , and the set of its out-neighbors is denoted as . The similarity between object and object is represented by and is calculated as follows:

This formula shows that the similarity between entities and depends on the similarity of all nodes connected to and . In the formula, is a constant decay factor.

The preceding formula can also be expressed in matrix form. Assume S is the SimRank score matrix of the directed graph G, where represents the similarity score between objects and . Let P be the adjacency matrix of G, where represents the number of edges from vertex to vertex . Then:

In matrix notation, this is:

In this formula, matrix is the column-normalized matrix , and is the identity matrix of . sets the main diagonal elements of the matrix to 1.

The SimRank++ algorithm extends the SimRank algorithm by introducing a new function to represent the transition probability between nodes in a bipartite graph:

Here, and represent any two queries, and represent any two ads, and the factors and are defined as follows:

These two extensions—using weights and evidence values to calibrate the original results—create the SimRank++ algorithm.

Antonellis et al. proposed SimRank++ in 2008 for query rewriting in sponsored search.

Application in recommendation systems

The original SimRank++ algorithm was designed for query rewriting in computational advertising, where it typically uses cumulative click data from a recent time window to compute query-query and ad-ad relevance.

Because the intent expressed by a query remains stable in the short term, using behavioral data from multiple days to calculate similarity is reasonable.

In a recommendation system, you usually do not have queries with explicit intent. Instead, the SimRank++ algorithm typically uses a bipartite graph of user-item clicks or other behaviors as input.

Without the constraints of query relevance, a user's behavioral intent in a recommendation scenario is less explicit. A single user may have multiple interests during the same period, and these interests can evolve over time.

Furthermore, the number of users, ranging from millions to billions, is often much larger than the number of queries. This poses a significant challenge to the implementation of the SimRank++ algorithm.

For these reasons, we recommend using a session-based behavioral bipartite graph to calculate item-item similarity. Within a single session, a user's interests are more focused and typically do not span items from multiple categories. In scenarios without an explicit session ID, you can use concat(user_id, date) as the session ID.

Incremental calculation

Merging data from multiple days as input is not recommended due to the large volume of session IDs and computational constraints.

To address the resulting coverage issue, we propose an incremental calculation solution. The SimRank++ toolkit retains item-to-item similarity data over multiple days. When calculating the similarity for day T, it initializes the item-to-item similarity matrix with the item similarity data from day T-1. The toolkit does not retain session-to-session similarity data.

Finally, the item similarity scores from multiple days are accumulated to produce the final item-to-item (i2i) similarity score, .

Here, is a discount factor. When past similarity scores are accumulated to the current time, a discount is applied. The older the data, the greater the discount.

Note: The accumulated similarity score is not guaranteed to be normalized. If you require normalization, you must perform it yourself.

Optimization 1: Popularity suppression

In recommendation scenarios, the "Harry Potter effect" can easily occur. Popular items receive more exposure, and without intervention, the algorithm may conclude that a popular item is similar to many other items. This leads to a Matthew effect where "the rich get richer". To mitigate this issue, this SimRank toolkit introduces a popularity suppression mechanism.

Specifically, we first aggregate the edge weights for each item from the input bipartite graph (by summing them) to identify popular items. Then, we apply a z-score transformation to the item's popularity (denoted as ):

Next, we convert into a monotonically decreasing function with a value range of (0, 1):

Finally, we multiply the original edge weight by to get the new weight. This is equivalent to increasing the resistance of a random walk towards popular items.

Optimization 2: Reweighting by preferred category

In recommendation scenarios, user click behavior can be noisy, for example, due to accidental clicks. To reduce noise, we adjust the weights of the bipartite graph by computing a user's preference for item categories.

For a given user, their preference score for category is as follows:

The weight for item is adjusted from the original to , where item belongs to category .

Input and output formats

The input table, which supports partitioned tables, contains four columns:

• user_id: User ID, session_id, query, and so on (any type)

• item_id: Item ID (any type)

• weight: A double-precision weight

• category: [Optional] The item's category. Setting this field can improve accuracy (any type).

• The input table must not contain duplicate <user_id, item_id> pairs. Merge weights in advance.

• When using category data to enhance the algorithm's performance, records with a null value in this field are deleted. Check the category column for null values.

• Note: You must control the variance of weights for the same query. If the variance is too high, elements of the weight transition matrix may become zero, which significantly reduces recall.

  • We recommend that you normalize or standardize the weight column in advance, for example, by applying "min-max", "z-score", "log", or "sigmoid" transformations.

  • You can also configure the input_weight_normalizer parameter.

• Setting appropriate weights for the edges of the bipartite graph significantly improves algorithm performance.

  • Using ctr as a weight can easily introduce noisy data because records with a high CTR may have a low impression count (pv).

  • Consider using log(1+click) as the edge weight.

• We recommend performing data cleaning to filter out noisy data.

  • For a given query, you can filter out data where click/sum(click) < threshold. For example, threshold=3e-5.

Item similarity (i2i) output table format (supports partition columns):

• item1: Item ID

• item2: Similar item ID

• cumulative_score: The cumulative similarity score calculated using data from multiple days. Use this field as the final result.

• score: The similarity score calculated from the current day's data. May be null.

Note: $$score\in (0,1)$$ and cumulative_score are not normalized.

Query similarity (q2q) output table format (supports partition columns):

• query1: Original query

• query2: Similar query

• score: Similarity score

Submit a job

1. Download the simrank_plus_plus-1.3.jar algorithm package.

2. Upload the package as a resource to your MaxCompute project.

   In the Create resource dialog box, set Engine Type to MaxCompute and Resource Type to JAR. Select Upload as ODPS Resource, upload the simrank_plus_plus-1.3.jar file from your computer, and then click Create.

3. In DataWorks, create an ODPS MR node (using an ODPS SQL node may cause errors), and submit the job with the following command.

   --@resource_reference{"simrank_plus_plus-1.3.jar"}
   jar -resources simrank_plus_plus-1.3.jar
   -classpath simrank_plus_plus-1.3.jar
   com.aliyun.pai.simrank.SimRankDriver
   -project ${max_compute_project}
   -end_point http://service.cn-hangzhou.maxcompute.aliyun.com/api
   -access_id ${access_id}
   -access_key ${access_key}
   -input_table simrank_i2i_input
   -input_table_partition ds=${bizdate}
   -output_table simrank_i2i_output
   -output_table_partition ds=${bizdate}
   -init_partition ds=${yesterday}
   -session_column device_id
   -item_column item_id
   -category_column cate_lv3_id
   -num_matmul_reducer 2000
   ;

Parameters

Parameter	Type	Description	Default
access_id	string	The AccessKey ID of your Alibaba Cloud account.	None
access_key	string	The AccessKey secret of your Alibaba Cloud account.	None
sts_token	string	The security token of your Alibaba Cloud account.	None
end_point	string	The MaxCompute service endpoint. For the public cloud, see Endpoints.	None
project	string	The default MaxCompute project.	None
input_table	string	The name of the input table.	None
input_table_partition	string	The partition of the input table.	None
init_partition	string	The partition of the item similarity output table that is used for initialization.	None. Typically, the previous day's partition is used.
output_table	string	The item similarity output table.	None
output_table_partition	string	The partition of the output table.	None
session_output_table	string	The query similarity output table.	None
session_output_table_partition	string	The partition of the query similarity output table.	None
session_column	string	The column name in the input table that represents the query.	user_id
item_column	string	The column name in the input table that represents the item.	item_id
category_column	string	The column name in the input table that represents the item category.	None
job_name	string	The name of the job and the prefix for intermediate tables. Set this parameter to resume an interrupted job. The name must be unique across different jobs.	A UUID is automatically generated.
debug	bool	Specifies whether to enable debug mode.	false
iter_times	int	The number of iterations for the SimRank algorithm.	3
decay_factor	float	The decay factor C of the SimRank algorithm. Value range: (0, 1).	0.8
discount_factor	float	The time decay factor for similarity scores. This parameter is used only for incremental calculation. Value range: (0, 1].	0.95
sim_threshold	float	The similarity filtering threshold used during the SimRank algorithm iteration.	0.000001
weight_threshold	float	The filtering threshold for the edge weights of the bipartite graph.	1e-6
input_weight_normalizer	string	The normalization function for input weights, such as LOG10(1+weight).	None
zero_spread_weight_cnt	int	The error threshold for zero values in the weight transition matrix score. Zero values indicate that the variance of the input weight is too high.	100
default_evidence	float	The default evidence weight used by the SimRank++ algorithm. Value range: (0, 0.5).	0.25
evidence_amplifier	float	The amplification factor for the evidence weight. The amplified evidence range is [default_evidence, evidence_amplifier].	1/decay_factor
anti_popular	bool	Specifies whether to enable popularity suppression to address the "Harry Potter effect".	true
item_block_size	int	The size of the item matrix block. This parameter is performance-related and we recommend that you do not modify it. Matrix blocking is not triggered for small input datasets.	50000
session_block_size	int	The size of the query matrix block. This parameter is performance-related and we recommend that you do not modify it. Matrix blocking is not triggered for small input datasets.	50000
matmul_strategy	int	The matrix block multiplication strategy. Valid values: 2, 3, and 4. Matrix blocking is not triggered for small input datasets.	4
matmul_reducer_memory	int	The memory of the reducer for matrix multiplication job 1, in MB.	12288 if matrix blocking is triggered; 3072 otherwise.
matmul_split_size	int	The slice size of the mapper for matrix multiplication, in MB.	16 if matrix blocking is triggered; 256 otherwise.
num_matmul_reducer	int	The number of reducers for matrix multiplication job 1.	Automatically calculated if matrix blocking is triggered; not applicable otherwise.
num_matmul_reducer2	int	The number of reducers for matrix multiplication job 2. Not required if blocking is not triggered.	None
evidence_split_size	int	The slice size of the mapper for calculating the evidence matrix, in MB.	16
num_evidence_reducer1	int	The number of reducers for evidence matrix calculation job 1.	None
num_evidence_reducer2	int	The number of reducers for evidence matrix calculation job 2.	None
priority	int	The job priority.	1

For search scenarios such as query rewriting, set anti_popular to false. For recommendation scenarios, set it to true.

Case study

In a search scenario, the input data consists of approximately 17 million rows, with 1.2 million queries and 1.5 million items. With the following parameters, the entire pipeline finishes in about 87 minutes.

--@resource_reference{"simrank_plus_plus-1.3.jar"}
jar -resources simrank_plus_plus-1.3.jar
-classpath simrank_plus_plus-1.3.jar
com.aliyun.pai.simrank.SimRankDriver
-project ${project}
-end_point http://service.cn-shanghai.maxcompute.aliyun.com/api
-access_id ${access_id}
-access_key ${access_key}
-input_table ${input_table}
-input_table_partition dt=20240512
-output_table simrank_i2i_score
-output_table_partition dt=20240512
-session_output_table simrank_q2q_score
-session_output_table_partition dt=20240512
-output_table_lifecycle 7
-session_column query_word
-item_column item_id
-category_column category
-anti_popular false
-num_matmul_reducer 2000
-num_evidence_reducer1 1000
-num_evidence_reducer2 200

References

• Similarity calculation in collaborative filtering algorithms

• Principle analysis of the SimRank++ algorithm