Matching Algorithm

Matcher

class qbindiff.matcher.Matcher(similarity_matrix: SimMatrix, primary_adj_matrix: AdjacencyMatrix, secondary_adj_matrix: AdjacencyMatrix)

Bases: object

compute(tradeoff: Ratio = 0.75, epsilon: Positive = 0.5, maxiter: int = 1000) → Iterator[int]

Launch the computation for a given number of iterations, using specific QBinDiff parameters

Parameters:

• tradeoff – tradeoff between the node similarity and the structure

• epsilon – perturbation to add to the similarity matrix

• maxiter – maximum number of iterations for the belief propagation

Returns:

an iterator over each step of the belief propagation

property confidence_score: list[float]

Confidence score for each match in the nodes mapping

property mapping: RawMapping | None

Nodes mapping between the two graphs

Returns:

The raw mapping between the nodes in the two input graphs

primary_adj_matrix

Adjacency matrix of the primary graph

process(sparsity_ratio: Ratio = 0.6, sparse_row: bool = False, compute_squares: bool = True) → None

Initialize the matching algorithm

Parameters:

• sparsity_ratio – The ratio between null element over the entire similarity matrix

• sparse_row – When building the sparse similarity matrix we can either filter out the elements by considering all the entries in the similarity matrix (sparse_row == False) or by considering each vector separately (sparse_row == True)

• compute_squares – Whether to compute the squares matrix

refine(mapping: RawMapping, score_matrix: SimMatrix) → RawMapping

Refine the mappings between the nodes of the two graphs by matching the unassigned nodes

Parameters:

• mapping – initial mapping

• score_matrix – similarity matrix

Returns:

updated raw mapping

secondary_adj_matrix

Adjacency matrix of the secondary graph

sim_matrix

Similarity matrix used by the Matcher

BeliefMWM

class qbindiff.matcher.belief_propagation.BeliefMWM(sim_matrix: csr_matrix, epsilon: float)

Bases: object

Computes the optimal solution to the Maxmimum Weight Matching problem.

Parameters:

• sim_matrix – similarity matrix (sparse numpy matrix)

• epsilon – perturbation for algorithm convergence

best_mapping: tuple[list[int], list[int]]

Current best mapping

best_marginals

Current associated marginals as a SparseMatrix

compute(maxiter: int = 1000) → Generator[int, Any, Any]

Repeat the belief propagation round for a given number of iterations

Parameters:

maxiter – Maximum number of iterations for the algorithm

Returns:

generator that yield at each iteration

property current_mapping: tuple[list[int], list[int]]

Current mapping

property current_marginals: csr_matrix

Current marginals in a sparse matrix

property current_score: float

Current score

epsilon

Current epsilon

max_avg_score: float

Current maximum average score

scores: list[float]

Scores list

weights

The weights sparse matrix

BeliefQAP

class qbindiff.matcher.belief_propagation.BeliefQAP(sim_matrix: csr_matrix, squares: csr_matrix, tradeoff: float, epsilon: float)

Bases: BeliefMWM

Computes an approximate solution to the Quadratic Assignment problem.

Parameters:

• sim_matrix – similarity matrix (sparse numpy matrix)

• squares – square matrix

• tradeoff – trade-off value (close to 0 similarity, close to 1 squares (callgraph))

• epsilon – perturbation value for convergence

best_mapping: tuple[list[int], list[int]]

Current best mapping

best_marginals

Current associated marginals as a SparseMatrix

compute(maxiter: int = 1000) → Generator[int, Any, Any]

Repeat the belief propagation round for a given number of iterations

Parameters:

maxiter – Maximum number of iterations for the algorithm

Returns:

generator that yield at each iteration

property current_mapping: tuple[list[int], list[int]]

Current mapping

property current_marginals: csr_matrix

Current marginals in a sparse matrix

property current_score: float

Current score of the solution

epsilon

Current epsilon

max_avg_score: float

Current maximum average score

property numsquares: int

Number of squares

scores: list[float]

Scores list

weights

The weights sparse matrix