Cost and Hungarian methods of graphical comparison

Cost and Hungarian methods of graphical comparison

Graph comparison analyses similarities and differences between data structures and is a method used in network analysis, bioinformatics, chemical structure analysis and machine learning. This enables a deeper understanding of structures and relationships, which can be useful for anomaly detection and feature extraction. The cost method and the Hungarian method are described below among the graph comparison approaches. 1.

1. Cost method: The cost method finds correspondences between nodes and edges when comparing graphs and quantifies these correspondences as ‘costs’. This method is particularly used to calculate the Graph Edit Distance (GED).

The characteristics of the cost method include the fact that it is solved as an overall minimisation problem by setting a cost to each editing operation, using the Graph Edit Distance to find the minimum cost of the editing operations (insert, delete, replace) necessary to make two graphs identical, and that an approximation algorithm is used to find an optimal solution, as the computational complexity is very high. Approximation algorithms are used to find the optimum solution, as they are computationally very expensive.

Specific applications include pattern recognition (e.g. shape comparison in images), chemical informatics (e.g. comparison of compound structures) and network analysis (e.g. comparison of social graphs).

2. Hangarian method: the Hungarian Algorithm is an algorithm for finding the best correspondence (pairing) between two sets, particularly suitable for solving bipartite matching and assignment problems.

Features include the fact that the input is a cost matrix (e.g. describing the cost between nodes), the output is a matching where the cost is minimised, the computational complexity is (O(n^3)) (where (n) is the dimension of the matrix), and when finding correspondences between graphs, the optimal matching between nodes using cost matrix The specific applications include the ability to calculate the optimal node-to-node matching using cost matrix when determining the correspondence between graphs.

Specific applications include the calculation of node correspondences between graphs, work assignment (e.g. assigning multiple tasks to multiple workers), robotics and tracking algorithms (e.g. multiple object tracking).

The above can be compared as follows.

Relevant algorithms

Typical relevant algorithms related to cost and Hungarian methods are listed below.

1. algorithms related to graph comparison

(1) Graph Edit Distance (GED)
– Abstract: The problem of minimising the cost of the editing operations (insert, delete, replace, etc.) required to match two graphs.
– Related algorithms:
– A* Search Method: uses a heuristic function to make the whole search more efficient.
– Dynamic programming: uses the solution of a subproblem to solve the whole.
– Approximation algorithms: approximate the optimal solution to reduce computation time.

(2) Maximum Clique Problem
– Abstract: The problem of finding a subgraph (clique) in a graph in which all nodes are connected to each other.
– Related algorithms:
– Bron-Kerbosch method: efficient enumeration of maximum cliques. For details, see “Bron-Kerbosh Method Overview, Algorithm, and Example Implementation.
– Branch and Bound method: to restrict the solution search space to improve efficiency.

(3) Graph Isomorphism
– Abstract: The problem of determining whether two graphs are structurally identical.
– Related algorithms:
– VF2 algorithm: efficient comparison considering node and edge labels. See “VF2 Algorithm Overview and Implementation Examples” for details.
– Nauty algorithm: generates and compares graph canonical labels. See “Nauty Algorithm Overview and Examples” for details.

2. algorithms related to the Hungarian method

(1) Linear assignment problem
– Abstract: The problem of assigning nodes at minimum cost based on a cost matrix.
– Related algorithms:
– Hungarian method: the cost matrix is iteratively updated to obtain an optimal solution.
– Kuhn-Munkres algorithm: an extension of the Hungarian method that can also handle asymmetric cost matrices. For more information, see “Overview of the Kuhn-Munkers Algorithm and Examples of Implementations.

(2) Maximum Matching Problem
– Abstract: The problem of finding the maximum number of correspondences between nodes in a bipartite graph.
– Related algorithms:
– Hopcroft-Karp Algorithm: efficiently computes the maximum matching. For details, see “Overview of the Hopcroft-Karp Method, Algorithm and Example Implementation.
– Edmonds’ Blossom Algorithm: a maximum matching algorithm that can be applied to non-bipartite graphs. For more information, see “Overview of Edmons’ Blossom Algorithm and Examples of Algorithms and Implementations.

3. other relevant optimisation algorithms

(1) Dynamic programming
– Abstract: Divides the problem into smaller subproblems and combines them to find the overall solution. See deatil in “Overview of dynamic programming and examples of application and implementation in python“– Applications: graph edit distance and shortest path problems.

(2) Linear Programming (LP)
– Abstract: Optimises the objective function under linear constraints. See Deatil in “Overview of linear programming and examples of algorithms and implementations“- Applications: theoretical basis of the Hungarian method.

(3) Branch and Bound
– Abstract: Divides the solution space and limits the range to make the search more efficient. See Deatil in “Overview of Branch-and-Bound Method, Algorithms, and Examples of Implementations“– Applications: graph edit distance and maximum clique problems.

(4) Heuristic algorithms
– Abstract: An algorithm that efficiently obtains an approximate solution without seeking an exact solution. See detail in “Heuristics and Frame Problems“– Applications: to NP-hard graph comparison problems.

implementation example

The following are basic implementations of the Hungarian method and Graph Edit Distance (GED). These use Python and can also be utilised with the help of libraries.

1. example implementation of the Hungarian method: a convenient method is to use Python’s scipy.optimise.linear_sum_assignment. The following is an example of finding a minimum cost matching with a cost matrix as input.

import numpy as np
from scipy.optimize import linear_sum_assignment

# cost matrix
cost_matrix = np.array([
    [4, 2, 8],
    [2, 3, 7],
    [3, 6, 5]
])

# Calculate optimal matching using the Hungarian method.
row_ind, col_ind = linear_sum_assignment(cost_matrix)

# Show Results
print("optimal matching:")
for r, c in zip(row_ind, col_ind):
    print(f"Task {r} -> Worker {c}(Cost: {cost_matrix[r, c]})")

# total cost
total_cost = cost_matrix[row_ind, col_ind].sum()
print(f"total cost: {total_cost}")

output example

optimal matching:
Task 0 -> Worker 1 (Cost: 2)
Task 1 -> Worker 0 (Cost: 2)
Task 2 -> Worker 2 (Cost: 5)
Total Cost: 9

2. Example implementation of Graph Edit Distance (GED): The networkx library is a useful tool for calculating graph edit distances in Python. The following is an example of calculating the edit distance between two graphs.

Code.

import networkx as nx

# Define two graphs
G1 = nx.Graph()
G1.add_edges_from([(1, 2), (2, 3), (3, 1)])

G2 = nx.Graph()
G2.add_edges_from([(1, 2), (2, 3), (3, 4)])

# Calculate graph edit distance.
def cost(node1, node2):
    # Node costs (e.g. based on differences in inter-node labels)
    return 0 if node1 == node2 else 1

edit_distance = nx.graph_edit_distance(G1, G2, node_subst_cost=cost)

# Show Results
print(f"Graph Edit Distance: {edit_distance}")

output example

Graph Edit Distance: 1.0

3. custom implementation: Hungarian method (simplified version): The following is an example of a self-implementation of the basic logic of the Hungarian method.

import numpy as np

def hungarian_algorithm(cost_matrix):
    n, m = cost_matrix.shape
    u = np.zeros(n)
    v = np.zeros(m)
    p = np.zeros(m, dtype=int)
    way = np.zeros(m, dtype=int)

    for i in range(1, n + 1):
        links = np.full(m, -1)
        mins = np.full(m, np.inf)
        visited = np.zeros(m, dtype=bool)
        marked_i, marked_j = i, 0
        while True:
            visited[marked_j] = True
            cur_i = int(p[marked_j])
            delta = np.inf
            cur_j = 0
            for j in range(m):
                if not visited[j]:
                    cur = cost_matrix[marked_i - 1][j] - u[marked_i - 1] - v[j]
                    if cur < mins[j]:
                        mins[j] = cur
                        links[j] = marked_j
                    if mins[j] < delta: delta = mins[j] cur_j = j for j in range(m): if visited[j]: u[int(p[j]) - 1] += delta v[j] -= delta else: mins[j] -= delta marked_j = cur_j marked_i = int(p[marked_j]) if marked_i == 0: break while True: links_idx = links[marked_j] p[marked_j] = p[links_idx] marked_j = links_idx if marked_j == 0: break result = np.zeros(n, dtype=int) for j in range(1, m): if p[j] > 0:
            result[int(p[j]) - 1] = j - 1
    return result

# test
cost_matrix = np.array([
    [4, 2, 8],
    [2, 3, 7],
    [3, 6, 5]
])
assignment = hungarian_algorithm(cost_matrix)
print("Matching results:", assignment)

Application examples

The Hungarian method and Graph Edit Distance (GED) are used in various fields and industries. Specific examples of their application are described below.

1 Application examples of the Hungarian method

1.1 Delivery optimisation (Vehicle Routing Problem)
– Example: Given multiple delivery vehicles and destinations, the problem is to decide which destination to allocate to each vehicle.
– Application: Define the cost matrix as ‘the cost of each vehicle travelling to a specific destination’. A minimum cost delivery plan is created using the Hungarian method.

1.2 Task Assignment
– Example: efficient assignment of multiple tasks to multiple personnel.
– Application: modelling the skill level of each person and the time taken to complete a task as a cost. Calculate the minimum cost (efficient assignment) using the Hungarian method.

1.3 Matching problem (Stable Matching)
– Example: problem of assigning students to internships or university programmes.
– Application: transform student and programme preferences into a cost matrix. Calculate the optimal allocation using the Hungarian method.

2. application examples of Graph Edit Distance (GED)

2.1 Pattern Recognition
– Examples: image processing and character recognition, comparing a template image with an input image.
– Application: Represent images as graphs (nodes are feature points, edges are relations). Similarity is assessed by calculating the graph edit distance.

2.2 Comparison of chemical structures
– Example: Evaluate the similarity of chemical molecules and search for drug candidates.
– Application: representation of molecules as graphs (atoms are nodes, bonds are edges); differences between the structures of two molecules are assessed by graph edit distance.

2.3 Analysis of social networks
– Example: compare social network structures at two different points in time and track changes in the network.
– Application: use graph edit distance to evaluate insertion and deletion of nodes and edges. Used for network evolution and anomaly detection.

2.4 Merging knowledge graphs
– Example: merge knowledge graphs created from different data sources.
– Application: evaluate differences in the structure of each knowledge graph in terms of graph edit distance. Identify similar nodes and edges to optimise the merging process.

2.5 Action Recognition
– Example: Identification of human actions in a video.
– Application: represent skeleton models of actions as graphs (nodes are joints, edges are relations). Recognise actions by comparing the graph of the input data with a known template graph.

3. actual application projects

Distribution planning for a logistics company
– Background: optimise deliveries from multiple warehouses to customers.
– Solution: use of the Hungarian method to calculate the allocation of warehouses and delivery destinations. Result: delivery costs reduced by more than 10%.

Bioinformatics
– Background: comparison of genetic data.
– Solution: representation of gene sequence structure as a graph. Graph edit distance is used to assess similarity and predict the function of new genes.

reference book

This section describes reference books related to the Hungarian method and graph editing distance.

Books related to the Hungarian method (Assignment Problem)

1. ‘Combinatorial Optimisation: Algorithms and Complexity’.
– Author(s): Christos H. Papadimitriou, Kenneth Steiglitz
– Description: covers combinatorial optimisation of assignment problems, matching problems and network flows, including the Hungarian method. Provides theoretical background and efficient algorithm design.
– Features: ideal for those who want to learn the basics of combinatorial optimisation. 2.

2. ‘Introduction to Algorithms’
– Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
– Description: describes in detail a number of algorithms, including the assignment problem and the shortest path problem. The Hungarian method is also mentioned as an application to the assignment problem.
– Features: standard book on algorithms. Can be used in a wide range of fields. 3.

3. ‘Network Flows: Theory, Algorithms, and Applications’.
– Authors: Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
– Description: in-depth theory and practical algorithms for network flows and assignment problems. Also describes the Hungarian method and related algorithms.
– Features: practical content with a focus on applications.

Books on Graph Edit Distance

1. ‘Graph Matching: Theoretical Foundations, Algorithms, and Applications’.
– Author(s): Christoph H. Schmid, Horst Bunke
– Description: Theory, algorithms and applications related to graph matching and edit distance. Describes approximate algorithms for minimising graph edit distance.
– Features: useful for serious research on graph edit distances.

2. ‘Graph Similarity and Matching’.
– Author(s): David Conte, Pasquale Foggia
– Description: An introduction to feature-based methods for graph similarity computation. Covers various methods of graph matching, including edit distance.
– Features: focus on graph similarity evaluation in practice. 3.

3. ‘Pattern Recognition and Machine Learning’
– Author: Christopher M. Bishop
– Description: covers pattern recognition in general and also touches on graph theory and distance measurement methods. Edit distance is described as an example application.
– Features: ideal for learning about the integration of machine learning in relation to applications of graph edit distance. 4.

4. ‘Graph-Based Representations in Pattern Recognition’
– Editors: Luc Brun, Mario Vento
– Description: details how graph theory can be applied to pattern recognition. Includes the latest developments in pattern recognition based on edit distance.
– Features: aimed at applied researchers.

General graph theory reference books.

1. ‘Graph Theory’.
– Author: Reinhard Diestel
– Contents: comprehensive coverage of the fundamentals and applications of graph theory. Includes the theory of graph matching in relation to edit distances.
– Features: suitable for those who want to learn the theory thoroughly.

2.「Structural Pattern Recognition」（Bunke, H.）

3. 「The Hungarian Method for the Assignment Problem」（Kuhn, H.）

4.「Graph Theory with Applications」(Bondy, J. A. & Murty, U. S. R.)

5. 「Algorithm Design」(Kleinberg, J. & Tardos, É.)

6. 「Introduction to Graph Theory」(West, D. B.)