Matching Algorithm

Matcher

class qbindiff.matcher.Matcher(similarity_matrix: ndarray, primary_adj_matrix: ndarray, secondary_adj_matrix: ndarray)[source]

Bases: object

compute(tradeoff: float = 0.75, epsilon: float = 0.5, maxiter: int = 1000) None[source]

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:

None

property confidence_score: list[float]

Confidence score for each match in the nodes mapping

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

Nodes mapping between the two graphs

primary_adj_matrix

Adjacency matrix of the primary graph

process(sparsity_ratio: float = 0.75, sparse_row: bool = False, compute_squares: bool = True)[source]

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

Returns:

None

refine(mapping: tuple[list[int], list[int]], score_matrix: ndarray) tuple[list[int], list[int]][source]

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 = 0.5)[source]

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][source]

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 = 0.5, epsilon: float = 0.5)[source]

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