# Joint Object Detection and Multi-Object Tracking Based on Hypergraph Matching
## 3 Preliminaries of Hypergraph Matching  
We introduce the preliminary concept association graph, on which our methods are based. For clarification, we first summarize important notations and definitions in Table 1.  
Graph Matching (GM) is a fundamental problem, which is NP-complete. It aims to match graphs \(\mathcal{G}^{1}=(\mathcal{V}^{1},\epsilon^{1})\) and \(\mathcal{G}^{2}=(\mathcal{V}^{2},\epsilon^{2})\), involving the establishment of node correspondences between the two graphs based on node-to-node and edge-to-edge affinities. It can be formulated as a Quadratic Assignment Programming (QAP) problem [51], in graph matching tasks, assuming a perfect match corresponds to the highest affinity score, the objective \(\mathcal{J}(\mathbf{X})\) needs to be maximized while satisfying certain constraints. \[ \begin{array}{l}\mathcal{J}(\mathbf{X})=\text{vec}(\mathbf{X})^{\text{T}} \mathbf{K}\text{vec}(\mathbf{X}),\\ s.t.\mathbf{X}\in[0,1]^{n_{1}\times n_{2}},\mathbf{X}\mathbf{1}_{n_{2}}= \mathbf{1}_{n_{1}},\mathbf{X}^{\text{T}}\mathbf{1}_{n_{1}}\leq\mathbf{1}_{n_{2 }}\end{array} , \tag{1}\]  
where \(\mathbf{X}\) is a doubly stochastic matrix, where all its rows sum to 1 and all its column sums are \(\leq\)1. \(\mathbf{1}_{n_{1}}\), \(\mathbf{1}_{n_{2}}\) represent column vectors of length \(n_{1}\) and \(n_{2}\), with all elements equal to 1, where \(n_{1}\) and \(n_{2}\) denote the number of vertices in \(\mathcal{G}^{1}\) and \(\mathcal{G}^{2}\). Initially, to measure the similarity between nodes in two graphs, an affinity matrix, \(\mathbf{K}\in\mathbb{R}^{n_{1}n_{2}\times n_{1}n_{2}}\), is constructed. The diagonal elements, \(\mathbf{K}_{iia,ia}\in s_{v}(\mathcal{V}^{1}_{i},\mathcal{V}^{2}_{a})\), represent the first-order node similarity between node \(\mathcal{V}^{1}_{i}\) and node \(\mathcal{V}^{2}_{a}\). The off-diagonal elements, \(\mathbf{K}_{ia,jb}\in s_{e}(\epsilon^{1}_{ij},\epsilon^{2}_{ab})\), indicate the second-order edge similarity between edges \(\epsilon^{1}_{ij}\) and \(\epsilon^{2}_{ab}\). Subsequently, as shown in Figure 2, the association graph, \(\mathcal{G}^{\text{A}}=(\mathcal{V}^{\text{A}},\epsilon^{\text{A}})\), between the two graphs is constructed, transforming the graph matching problem into the node classification problem on the association graph, which simplifies the problem's structure and allows the application of graph embedding and machine learning techniques. The nodes of the association graph, \(\mathcal{V}^{\text{A}}_{ia}\), represent potential matching relationships between the nodes \(\mathcal{V}^{1}_{i}\) and \(\mathcal{V}^{2}_{a}\), where the superscript means the index of graphs and the subscript means the index of vertices. Specifically, if \(\mathcal{V}^{1}_{i}\) is a node in \(\mathcal{G}^{1}\) and \(\mathcal{V}^{2}_{a}\) is a node in \(\mathcal{G}^{2}\), then vertex \(\mathcal{V}^{\text{A}}_{ia}\) in the association graph represents the match between \(\mathcal{V}^{1}_{i}\) and \(\mathcal{V}^{2}_{a}\). The edges in the association graph, \(\epsilon^{\text{A}}_{ia,jb}\), represent the consistency between matching pairs. If two matching pairs, \((\mathcal{V}^{1}_{i},\mathcal{V}^{2}_{a})\) and \((\mathcal{V}^{1}_{j},\mathcal{V}^{2}_{b})\), can coexist in an optimal match, then there is an edge between \(\mathcal{V}^{\text{A}}_{ia}\) and \(\mathcal{V}^{\text{A}}_{jb}\). The weighted adjacency matrix of association graph \(\mathbf{W}\) comes from the off-diagonal elements of \(\mathbf{K}\). To better exploit the first-order similarities, diagonal elements, \(\mathbf{K}_{ia,ia}\), are further assigned as node attributes, \(\mathcal{V}^{\text{A}}\). In order to perform node classification on the association graph, GCNs are first used to embed the nodes of the association graph, capturing the topological structure information between nodes and generating feature representations for each node. We denote \(\mathbf{v}^{(k)}\in\mathbb{R}^{n_{1}n_{2}\times l_{k}}\) as \(l_{k}\)-dimensional vertex embeddings on layer \(k\).