# DHOT-GM: Robust Graph Matching Using A Differentiable Hierarchical Optimal
Transport Framework

Haoran Cheng1 Dixin Luo1 Hongteng Xu2,3
1School of Computer Science and Technology, Beijing Institute of Technology
2Gaoling School of Artificial Intelligence, Renmin University of China
3Beijing Key Laboratory of Big Data Management and Analysis Methods
Dixin Luo is the corresponding author<EMAIL_ADDRESS>
###### Abstract

Graph matching is one of the most significant graph analytic tasks in
practice, which aims to find the node correspondence across different graphs.
Most existing approaches rely on adjacency matrices or node embeddings when
matching graphs, whose performances are often sub-optimal because of not fully
leveraging the multi-modal information hidden in graphs, such as node
attributes, subgraph structures, etc. In this study, we propose a novel and
effective graph matching method based on a differentiable hierarchical optimal
transport (HOT) framework, called DHOT-GM. Essentially, our method represents
each graph as a set of relational matrices corresponding to the information of
different modalities. Given two graphs, we enumerate all relational matrix
pairs and obtain their matching results, and accordingly, infer the node
correspondence by the weighted averaging of the matching results. This method
can be implemented as computing the HOT distance between the two graphs — each
matching result is an optimal transport plan associated with the Gromov-
Wasserstein (GW) distance between two relational matrices, and the weights of
all matching results are the elements of an upper-level optimal transport plan
defined on the matrix sets. We propose a bi-level optimization algorithm to
compute the HOT distance in a differentiable way, making the significance of
the relational matrices adjustable. Experiments on various graph matching
tasks demonstrate the superiority and robustness of our method compared to
state-of-the-art approaches.

##  1 Introduction

As one of the most significant tasks in graph analysis, graph matching aims to
find the node correspondence across different graphs. With the correspondence
between nodes, the common patterns exhibited by multiple graphs are captured,
thus allowing for partial knowledge transfers between two or more graphs [21,
32]. This task commonly appears in many real-world applications. For instance,
the alignment of protein-protein interaction (PPI) networks helps to explore
the functionally similar proteins of different species and exhibit their
evolutionary relationships [29, 22]. Linking user accounts in different social
networks leads to a better understanding of user behavior patterns and thus
benefits many downstream tasks, e.g., personalized recommendation [19, 20] and
fraud detection [14, 13]. The vision tasks like shape matching and point cloud
registration can be formulated as graph matching problems [37, 8].

In practice, achieving exact graph matching is always challenging because of
its NP-hardness. Therefore, many methods have been developed to match graphs
approximately and efficiently, which can be coarsely categorized into
unsupervised methods and semi-supervised ones. Unsupervised graph matching
methods often formulate the task as a quadratic assignment problem (QAP) [23]
based on the adjacency matrices [35, 17, 48] or other relational matrices [53,
11, 47, 42] of graphs and develop approximate optimization algorithms to solve
the problem. Recently, some learning-based methods have been proposed [12, 34,
9], which embed graph nodes and then match the node embeddings across
different graphs. To mitigate the NP-hardness, semi-supervised graph matching
methods [50, 43, 52, 49] leverage the correspondence between partial nodes as
the prior of the matching task and infer the correspondence of the remaining
nodes. However, most existing methods merely apply the specific graph
information of a single modality (among adjacency matrices, node attributes,
and subgraph structures111In this study, we treat adjacency matrices, node
attributes, and subgraph structures as three different “modalities”, which
reflect different information hidden in graphs.) and thus often leads to non-
robust matching results. Although some attempts are made to match graphs based
on multi-modal information, e.g., FGW [36], GWL [42], and SLOTAlign [33],
these methods apply an over-simplified mechanism to fuse the multi-modal
information linearly and thus result in sub-optimal performance. Few of them
consider fully leveraging all the above information, let alone studying the
impacts of the cross-modal information on the matching results.

To overcome the above problem and fill in the blank, in this study we consider
the multi-modal information of graphs and their interactions in graph matching
tasks, proposing a robust graph matching method, called DHOT-GM, based on a
differentiable hierarchical optimal transport framework. As illustrated in
Figure 1, our DHOT method formulates the graph matching task as a hierarchical
optimal transport problem, leading to a bi-level optimization problem. In
particular, given two graphs, we first capture their multi-modal information
by a set of relational matrices, which correspond to the adjacency matrices
and the inner products of node embedding matrices. In the lower level, we
enumerate all pairs of the relational matrices and measure the discrepancies
between them by computing the Gromov-Wasserstein (GW) distance [25]. The
optimal transport (OT) matrices associated with the GW distances indicate the
graph matching results achieved based on the relational matrix pairs within
the same modality and across different modalities. Given these lower-level OT
matrices, we consider their fusion mechanism in the upper level, learning
their weights by solving an OT problem defined for modalities. The
significance of the modalities corresponds to the marginal distribution
associated with the upper-level OT problem, which can be learned jointly with
the weights by the Sinkhorn-scaling algorithm [5]. Solving the two-level
optimal transport problems iteratively leads to the proposed DHOT framework.
As a result, the weighted sum of the lower-level optimal transport matrices
indicates the final graph matching result.

Figure 1: The scheme of DHOT-GM. Given two graphs, we extract a set of
relational matrices for each of them based on the information of different
modalities. Our method not only matches their relational matrices within the
same modality (indicated by the green arrows) but also matches those across
different modalities (indicated by the red arrows). Each matching step leads
to a lower-level OT matrix for graph nodes, whose weight is determined by an
upper-level OT matrix for the modalities. The final matching result is the
weighted sum of the lower-level OT matrices.

Different from existing graph matching methods, our DHOT-GM method explicitly
considers the matching results across different modalities and demonstrates
their contributions to improving final matching performance. Additionally, by
learning the significance of the modalities and the weights of the modality
pairs, our DHOT-GM method can find useful modalities and rely more on their
matching results. We test our DHOT-GM method in both synthetic and real-world
graph matching tasks and compare it with state-of-the-art unsupervised and
semi-supervised graph matching methods. Experimental results demonstrate the
superiority of our method and its robustness in highly noisy cases.

##  2 Related work

###  2.1 Graph Matching

The most classic solution for graph matching is the QAP-based unsupervised
method, which has been widely studied in research [23]. This type of method
utilizes various relational matrices of graphs, such as the adjacency matrix
of the graph [35, 17, 48], the similarity matrix of node attributes [53, 2,
47], or their fusion matrix [11, 42]. However, due to the NP-hardness of the
problem, the QAP-based methods often have high computational complexity, and
their graph matching results often suffer from the identifiability issue. In
recent years, node embedding-based methods have emerged in unsupervised graph
matching. Representative work includes the matrix factorization-based [12] and
graph neural network-based methods [34, 9]. They all follow the paradigm of
extracting node embeddings first, and then performing graph matching based on
the similarity between embeddings.

Semi-supervised graph matching introduces the prior node correspondence to
guide the learning process. Typical methods include spectral-based [29],
matrix factorization-based [50], and random walk-based [54, 7] methods. In
general, the effectiveness of the semi-supervised methods is largely
determined by the number of predefined node pairs, while it is often expensive
to label matched nodes across different graphs, especially when dealing with
real-world graphs that have hundreds and thousands of nodes.

###  2.2 Graph Optimal Transport

Optimal transport (OT) distance and its variants provide an effective metric
for probability measures (e.g., distributions). In particular, the OT distance
in the Kantorovich form is called Wasserstein distance [15], which corresponds
to computing an optimal transport plan (or equivalently, called coupling)
between two probability measures. Given the samples of two probability
measures, the optimal transport plan between them is formulated as a matrix
indicating the pairwise coherency of the samples [31, 25]. Because of this
excellent property, OT has received great attention in extensive matching
tasks, such as shape matching [30], generative modeling [10], and image-text
alignment [3]. In graph data analysis, OT is also gradually being adopted for
graph-to-graph comparisons. One of the representatives is the Gromov-
Wasserstein (GW) distance that shows excellent performance in graph
partitioning [41], graph clustering [40] and graph dictionary learning [38].

Focusing on graph matching, the GW distance can be seen as a relaxation
strategy for the QAP problem. Therefore, based on the GW distance, a series of
OT-based graph matching methods have been proposed and achieved encouraging
performance. For example, GWL [42] is the first OT-based method that jointly
learns the node embeddings and finds the node correspondence between two
graphs via GW distance. FGW [36] extends the GW distance so that it can be
applied to the task of matching attribute graphs. SLOTAlign [33] combines GW
distance with multi-view structure learning to enhance graph representation
power and reduce the effect of structure and feature inconsistency inherited
across graphs.

Recently, hierarchical optimal transport (HOT) [28, 1], as a generalization of
original OT, is proposed to compare the distributions with structural
information, e.g., measuring the distance between different Gaussian mixture
models [4]. By solving OT plans at different levels, HOT has achieved
encouraging performance in multi-modal distribution [18, 46], multi-modal
learning [24], and neural architecture search [44]. However, to the best of
our knowledge, this technique has not yet been attempted in the graph matching
task.

##  3 Proposed DHOT-GM Method

###  3.1 Motivation

In this study, we denote a graph as $\mathcal{G}=(\mathcal{V},\bm{A},\bm{X})$.
Here, $\mathcal{V}$ is the set of nodes.
$\bm{A}\in\\{0,1\\}^{|\mathcal{V}|\times|\mathcal{V}|}$ is the adjacency
matrix, where $A_{ij}=1$ denotes the presence of an edge between nodes $i$ and
$j$, and $A_{ij}=0$ indicates the absence of an edge.
$\bm{X}\in\mathbb{R}^{|\mathcal{V}|\times d}$ denotes the node attribute
matrix, where $|\mathcal{V}|$ represents the number of nodes, and each node
has a $d$-dimensional attribute vector. Given two graphs, i.e.,
$\mathcal{G}_{s}=(\mathcal{V}_{s},\bm{A}_{s},\bm{X}_{s})$) and
$\mathcal{G}_{t}=(\mathcal{V}_{t},\bm{A}_{t},\bm{X}_{t})$, graph matching aims
to find the correspondence between their nodes. Without the loss of
generality, in the following content, we assume that
$|\mathcal{V}_{s}|\leq|\mathcal{V}_{t}|$.

To achieve this aim, we need to find a matrix
$\bm{T}^{*}=[T^{*}_{ij}]\in\mathbb{R}^{|\mathcal{V}_{s}|\times|\mathcal{V}_{t}|}$
indicating the correspondence: for each $i\in\mathcal{V}_{s}$, we can infer
its correspondence in $\mathcal{V}_{t}$ by
$j^{*}=\arg\max_{j\in\mathcal{V}_{t}}T^{*}_{ij}$. The inference of
$\bm{T}^{*}$ is often formulated in a QAP format [23], i.e.,

$\displaystyle\begin{aligned}
\bm{T}^{*}=\arg\sideset{}{{}_{\bm{T}\in\Omega}}{\max}\langle\bm{D}_{s}\bm{T}\bm{D}_{t}^{\top},~{}\bm{T}\rangle,\end{aligned}$
(1)

where $\langle\cdot,\cdot\rangle$ represents the inner product of matrix,
$\Omega$ is the feasible domain of $\bm{T}$, and
$\\{\bm{D}_{s}=[D_{ij}^{s}]\in\mathbb{R}^{|\mathcal{V}_{s}|\times|\mathcal{V}_{s}|},\bm{D}_{t}=[D_{ij}^{t}]\in\mathbb{R}^{|\mathcal{V}_{t}|\times|\mathcal{V}_{t}|}\\}$
are two relational matrices extracted from the graphs.

In the classic QAP problem, the feasible domain
$\Omega=\\{\bm{T}\in\\{0,1\\}^{|\mathcal{V}_{s}|\times|\mathcal{V}_{t}|}|\bm{T}\bm{1}_{|\mathcal{V}_{t}|}=\bm{1}_{|\mathcal{V}_{s}|},\bm{T}^{\top}\bm{1}_{|\mathcal{V}_{s}|}\leq\bm{1}_{|\mathcal{V}_{t}|}\\}$,
leading to a combinatorial optimization problem. To simplify the computation,
we often relax the feasible domain to a set of doubly-stochastic matrices,
i.e.,
$\Omega(\bm{\mu}_{s},\bm{\mu}_{t})=\\{\bm{T}>\bm{0}_{|\mathcal{V}_{s}|\times|\mathcal{V}_{t}|}|\bm{T}\bm{1}_{|\mathcal{V}_{t}|}=\bm{\mu}_{s},\bm{T}^{\top}\bm{1}_{|\mathcal{V}_{s}|}=\bm{\mu}_{t}\\}$,
where $\bm{\mu}_{s}$ and $\bm{\mu}_{t}$ are two vectors defined on
$(|\mathcal{V}_{s}|-1)$-Simplex and $(|\mathcal{V}_{t}|-1)$-Simplex,
respectively. Typically, we can set
$\bm{\mu}_{s}=\frac{1}{|\mathcal{V}_{s}|}\bm{1}_{|\mathcal{V}_{s}|}$ and
$\bm{\mu}_{t}=\frac{1}{|\mathcal{V}_{t}|}\bm{1}_{|\mathcal{V}_{t}|}$ when
there is no prior knowledge [42]. In such a situation, equation 1 is
equivalent to the computational problem of the Gromov-Wasserstein discrepancy
between $\bm{D}_{s}$ and $\bm{D}_{t}$ [26], i.e.,

$\displaystyle\begin{aligned}
d_{GW}(\bm{D}_{s},\bm{D}_{t}):=&\sideset{}{{}_{\bm{T}\in\Omega(\bm{\mu}_{s},\bm{\mu}_{t})}}{\min}\sideset{}{{}_{i,j,k,l}}{\sum}|D^{s}_{ij}-D^{t}_{kl}|^{2}T_{ij}T_{kl}\\\
=&\sideset{}{{}_{\bm{T}\in\Omega(\bm{\mu}_{s},\bm{\mu}_{t})}}{\min}\langle\bm{L}(\bm{D}_{s},\bm{D}_{t},\bm{T}),\bm{T}\rangle,\end{aligned}$
(2)

where
$\bm{L}(\bm{D}_{s},\bm{D}_{t},\bm{T})=(\bm{D}_{s}\odot\bm{D}_{s})\bm{\mu}_{s}\bm{1}_{|\mathcal{V}_{t}|}^{\top}+\bm{1}_{|\mathcal{V}_{s}|}\bm{\mu}_{t}^{\top}(\bm{D}_{t}\odot\bm{D}_{t})^{\top}-2\bm{D}_{s}\bm{T}\bm{D}_{t}^{\top}$
and $\odot$ denotes the Hadamard product of matrix. The optimal solution of
equation 2, i.e., $\bm{T}^{*}$, is called the optimal transport matrix, which
can be explained as the joint distribution of the nodes. In particular, its
element $T_{ij}^{*}$ is the coherency probability of the node
$i\in\mathcal{V}_{s}$ and the node $j\in\mathcal{V}_{t}$.

Typically, each relational matrix records the pairwise relations or
similarities for the nodes of a graph, which can be implemented as the
adjacency matrix of the graph [17, 35, 48], the similarity matrix of node
attributes [53, 2, 47], or their fusion matrix [11, 42, 36, 33]. However, in
our opinion, existing methods do not fully leverage the above information and
thus suffer from the following two issues.

  * •

Non-robust matching based on a single relational matrix pair. As
aforementioned, many methods match graphs based on their relational matrices
in a single modality. For example, the work in [41, 17, 35, 48] sets the
$\bm{D}_{s}$ and $\bm{D}_{t}$ in equation 2 as the adjacency matrices.
However, merely applying a single relational matrix pair often leads to non-
robust matching results, especially in highly-noisy cases.

  * •

Ignoring the potential of cross-modal matching. Recently, some work considers
fusing multi-modal relational matrices [11, 36]. For example, the GWL in [42]
and the SLOTAlign method in [33] construct the $\bm{D}_{s}$ and $\bm{D}_{t}$
in equation 2 by a linear fusion mechanism:

$\displaystyle\bm{D}_{s}=\sideset{}{{}_{k=1}^{K}}{\sum}\alpha_{k}\bm{D}_{s}^{(k)},~{}\bm{D}_{t}=\sideset{}{{}_{k=1}^{K}}{\sum}\alpha_{k}\bm{D}_{t}^{(k)}.$
(3)

Here, $K$ modalities are considered, and
$\\{\bm{D}_{s}^{(k)},\bm{D}_{t}^{(k)}\\}$ is the relational matrix pair
corresponding to the $k$-th modality. The coefficients
$\\{\alpha_{k}\\}_{k=1}^{K}$ control the significance of the modalities, which
can be fixed [42] or learnable [33]. Although the fused relational matrices
help to improve the robustness of graph matching, the linear fusion mechanism
is often over-simplified — the fusion step itself results in the loss of
structural information.222For example, merely based on the fused matrix
$\bm{D}_{s}$, we cannot obtain its multi-modal components
$\\{\bm{D}_{s}^{(k)}\\}_{k=1}^{K}$. The fusion step eliminates the
identifiability of different modalities. Moreover, existing methods require
the relational matrices of different graphs to be constructed in the same
manner. For the relational matrices in different modalities, existing methods
neither consider their matching problems nor study their potential impacts on
the graph matching results, which may result in sub-optimal performance.

In the following content, we will propose a robust graph matching method,
resolving the above two issues in a differentiable hierarchical optimal
transport framework.

Figure 2: The pipeline for extracting relational matrices.

###  3.2 A Differentiable Hierarchical Optimal Transport Framework

Instead of using a single relational matrix pair or fusing multi-modal
relational matrices linearly, our method extracts multi-modal relational
matrices and treats them as a set. As a result, a graph can be represented as
$\mathcal{G}=(\mathcal{V},\mathcal{D})$, where
$\mathcal{D}=\\{\bm{D}^{(k)}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}\\}_{k=1}^{K}$
is the set of $K$ modalities’ relational matrices and $K$ is the number of
modalities. As shown in Figure 2, we extract the $K$ relational matrices from
the following three resources.

  * •

Graph Topology. The adjacency matrix of a graph captures its topological
information, which can be treated as a relational matrix in nature, i.e.,
$\bm{D}^{(1)}=\bm{A}$.

  * •

Node Attributes. The node attributes are the information imposed on graph
nodes, and the inner product between arbitrary two nodes encodes their
pairwise similarity. Therefore, given normalized node attribute matrix
$\bm{X}=[\bm{x}_{1},\cdots,\bm{x}_{|\mathcal{V}|}]^{\top}\in\mathbb{R}^{|\mathcal{V}|\times
d}$, we construct the second relational matrix as
$\bm{D}^{(2)}=\bm{X}\bm{X}^{\top}$.

  * •

Subgraph Structures. Both the adjacency matrix and the node attribute
similarity matrix can only capture the relationships of node pairs. To capture
the relationships of subgraph pairs, we need a message-passing mechanism to
encode the neighborhood information of each node. In this study, we apply a
$N$-layer parameter-free message-passing [16] as follows:
$\bm{Z}^{(0)}=\bm{X}$, and

$\displaystyle\begin{aligned}
\bm{Z}^{(n)}=(\bm{M}^{-\frac{1}{2}}\hat{\bm{A}}\bm{M}^{-\frac{1}{2}})\bm{Z}^{(n-1)},~{}\text{for}~{}n=1,...,N,\end{aligned}$
(4)

where $\hat{\bm{A}}=\bm{A}+\bm{I}$ is the adjacency matrix with self-loop and
$\bm{I}$ is the identity matrix, $\bm{M}$ is the degree matrix of
$\hat{\bm{A}}$ that $M_{ii}=\sum_{j}\hat{A}_{ij}$. Obviously,
$\bm{Z}^{(n)}=[\bm{z}_{1}^{(n)},\cdots,\bm{z}^{(n)}_{|\mathcal{V}|}]^{\top}\in\mathbb{R}^{|\mathcal{V}|\times
d}$ is the output after $n$-step message-passing, and $\bm{z}_{i}^{(n)}$
encodes the subgraph corresponding to the $n$-hop neighborhood of the node
$i$. Accordingly, we can construct multiple relational matrices by the inner
products of the embeddings generated by different layers, i.e.,
$\bm{D}^{(n+2)}=\bm{Z}^{(n)}\bm{Z}^{(n)\top}$ for $n=1,...,N$, where
$\bm{D}^{(n+2)}$ indicates the pairwise similarities of the $n$-hop subgraphs.
From the viewpoint of graph spectral filtering [6], the message-passing steps
in equation 4 are equivalent to applying a low-pass graph filter to $\bm{X}$.

Setting the number of layers to $N=K-2$, we derive the multi-modal relational
matrix set $\mathcal{D}=\\{\bm{D}^{(k)}\\}_{k=1}^{K}$ by

$\displaystyle\begin{aligned}
\bm{D}^{(1)}=\bm{A},~{}\bm{D}^{(2)}=\bm{X}\bm{X}^{\top},~{}\bm{D}^{(k)}=\bm{Z}^{(k-2)}\bm{Z}^{(k-2)\top},~{}2<k\leq
K.\end{aligned}$ (5)

Given two graphs, i.e., $\mathcal{G}_{s}(\mathcal{V}_{s},\mathcal{D}_{s})$ and
$\mathcal{G}_{t}(\mathcal{V}_{t},\mathcal{D}_{t})$, where $\mathcal{D}_{s}$
and $\mathcal{D}_{t}$ are constructed by equation 5, our method formulates the
graph matching task in the following differentiable hierarchical optimal
transport framework. In particular, we first define the hierarchical optimal
transport distance between the two graphs, denoted as

$\displaystyle\begin{aligned}
d_{HOT}(\mathcal{G}_{s},\mathcal{G}_{t}):=d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW}(\mathcal{D}_{s},\mathcal{D}_{t})),\end{aligned}$
(6)

which corresponds to the composition of OT problems in two levels.

####  3.2.1 Lower-level Optimal Transports for Nodes

The $\bm{D}_{GW}(\mathcal{D}_{s},\mathcal{D}_{t})$ in equation 6 is a Gromov-
Wasserstein distance matrix with size $K\times K$, i.e.,
$\bm{D}_{GW}(\mathcal{D}_{s},\mathcal{D}_{t})=[d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})]\in\mathbb{R}^{K\times
K}$. Here, the element $d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})$ corresponds
to the GW distance between the $p$-th relational matrix of $\mathcal{G}_{s}$
and the $q$-th relational matrix of $\mathcal{G}_{t}$. As the definition in
equation 2, the computation of $d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})$
corresponds to solving a constrained nonsmooth nonconvex optimization problem.
Its optimal solution, denoted as $\bm{T}^{(p,q)}$, is the optimal transport
matrix indicating the graph matching result derived based on
$\bm{D}_{s}^{(p)}$ and $\bm{D}_{t}^{(q)}$.

  * •

Remark 1. Enumerating all relational matrix pairs, our method computes $K^{2}$
GW distances and derives the GW distance matrix $\bm{D}_{GW}$ associated with
a set of optimal transport matrices, denoted as
$\mathcal{T}=\\{\bm{T}^{(p,q)}\\}_{p=1,q=1}^{K}$. When $p=q$, $\bm{T}^{(p,q)}$
captures the node correspondence between $\mathcal{G}_{s}$ and
$\mathcal{G}_{t}$ based on the relational information within the same
modality. When $p\neq q$, $\bm{T}^{(p,q)}$ captures the node correspondence
between $\mathcal{G}_{s}$ and $\mathcal{G}_{t}$ across different modalities.
In other words, different from existing graph matching methods, our method
explicitly considers matching the graphs based on their cross-modal
similarities, as we claimed in Introduction.

####  3.2.2 An Upper-level Optimal Transport for Modalities

Taking the GW distance matrix $\bm{D}_{GW}$ as the grounding cost, we further
compute the Wasserstein distance between the modalities’ distributions, i.e.,
the $d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW})$ in equation 6. In
particular, its definition is shown below:

$\displaystyle\begin{aligned}
d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW}):=&\sideset{}{{}_{\bm{\Theta}\in\Omega(\bm{\nu}_{s},\bm{\nu}_{t})}}{\min}\sideset{}{{}_{p=1}^{K}}{\sum}\sideset{}{{}_{q=1}^{K}}{\sum}d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})\theta_{pq}\\\
=&\sideset{}{{}_{\bm{\Theta}\in\Omega(\bm{\nu}_{s},\bm{\nu}_{t})}}{\min}\langle\bm{D}_{GW},\bm{\Theta}\rangle.\end{aligned}$
(7)

Here, $\bm{\nu}_{s},\bm{\nu}_{t}$ are two vectors in the $(K-1)$-Simplex,
indicating the significance of the $K$ modalities for $\mathcal{G}_{s}$ and
$\mathcal{G}_{t}$, respectively. $\Omega(\bm{\nu}_{s},\bm{\nu}_{t})$ is the
set of the doubly-stochastic matrices that take $\bm{\nu}_{s}$ and
$\bm{\nu}_{t}$ as marginals.
$\bm{\Theta}=[\theta_{pq}]\in\Pi(\bm{\nu}_{s},\bm{\nu}_{t})$ is the transport
matrix defined for the modalities. It can be explained as a joint distribution
of the modalities corresponding to different graphs. In particular, its
element $\theta_{pq}$ can be explained as the coherency probability of the
$p$-th modality of $\mathcal{G}_{s}$ and the $q$-th modality of
$\mathcal{G}_{t}$.

  * •

Remark 2. In principle, the matrix $\bm{\Theta}$ indicates the significance of
different modality pairs. In particular, when the coherency probability of the
modality pair $(p,q)$ (i.e., $\theta_{pq}$) is large, the corresponding GW
distance $d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})$ should be small, which
means that $\bm{D}_{s}^{(p)}$ and $\bm{D}_{t}^{(q)}$ are matched well and
their matching result $\bm{T}^{(p,q)}$ is significant.

####  3.2.3 Robust Graph Matching by Minimizing HOT

The composition of the above two-level optimal transport problems leads to the
HOT distance shown in equation 6. The principle of our DHOT-GM method is
matching graphs by minimizing the HOT distance between them with learnable and
regularized modality distributions, i.e.,

$\displaystyle\begin{aligned}
\mathcal{T},\bm{\Theta},\bm{\nu}_{t},\bm{\nu}_{s}=\arg\sideset{}{{}_{\mathcal{T},\bm{\Theta},\bm{\nu}_{t},\bm{\nu}_{s}}}{\min}\underbrace{d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW})}_{d_{HOT}(\mathcal{G}_{s},\mathcal{G}_{t})}+\underbrace{\left(KL(\bm{\nu}_{s}\|\frac{1}{K}\bm{1}_{K})+KL(\bm{\nu}_{t}\|\frac{1}{K}\bm{1}_{K})\right)}_{\text{Regularizer
of modality significance}}.\end{aligned}$ (8)

Here, the first term is the HOT distance between the two graphs. It
corresponds to the computation of the $K^{2}$ lower-level optimal transport
matrices $\mathcal{T}=\\{\bm{T}^{(p,q)}\\}_{p,q=1}^{K}$ and the upper-level
optimal transport matrix $\bm{\Theta}$. Note that, we call this optimization
problem “Differentiable Hierarchical Optimal Transport” because the marginals
$\bm{\nu}_{s}$ and $\bm{\nu}_{t}$ are learnable variables in the problem. The
second term in equation 8 includes the regularizers of the marginals. Each
regularizer is implemented as the KL-divergence between a marginal and its
uniform prior, which helps to avoid trivial solutions (e.g., $\bm{\nu}_{s}$
and $\bm{\nu}_{t}$ are one-hot vectors and thus only one modality pair is used
to match graphs).

Given $\mathcal{T}$ and $\bm{\Theta}$, we compute the final matching result as
the weighted sum of all $\bm{T}^{(p,q)}$’s, i.e.,

$\displaystyle\begin{aligned}
\bm{T}=\sideset{}{{}_{p=1}^{K}}{\sum}\sideset{}{{}_{q=1}^{K}}{\sum}\theta_{pq}\bm{T}^{(p,q)}.\end{aligned}$
(9)

Accordingly, the final matching result is dominated by the $\bm{T}^{(p,q)}$’s
corresponding to the significant modality pairs.

###  3.3 Connections to Existing Methods

The DHOT framework allows us to explicitly capture the cross-modal matching
results (i.e., $\\{\bm{T}^{(p,q)}\\}_{p\neq q}$). We reveal the connections of
our DHOT-GM method to existing methods as follows.

####  3.3.1 Connection to single-modal graph matching

As aforementioned, when solving equation 8 without the regularizer, we have
the trivial solution

$\displaystyle\sideset{}{}{\min}_{\mathcal{T},\bm{\Theta},\bm{\nu}_{t},\bm{\nu}_{s}}d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW})=\sideset{}{}{\min}_{p,q\in\\{1,..,K\\}}d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)}),$
(10)

in which the optimal $\bm{\nu}_{t}^{*}$ and $\bm{\nu}_{s}^{*}$ are one-hot
vectors, and their non-zero elements indicate the modality pair $(p,q)$ that
corresponds to the minimum GW distance. When $p=q$, this trivial solution
corresponds to matching $\mathcal{G}_{s}$ and $\mathcal{G}_{t}$ based on the
relational matrices within the same modality. In such a situation, DHOT-GM
degrades to the classic single-modal graph matching strategy [41, 17, 35, 48].

####  3.3.2 Connection to linear fusion-based multi-modal graph matching

The GWL [42] and SLOTAlign [33] compute
$d_{GW}\left(\sideset{}{{}_{k=1}^{K}}{\sum}\bm{D}_{s}^{(k)},\sideset{}{{}_{k=1}^{K}}{\sum}\bm{D}_{t}^{(k)}\right)$,
leading to a $\bm{T}^{*}$ shared by all modality pairs. Because
$\mathcal{T}^{*}=\\{\bm{T}^{(p,q)}=\bm{T}^{*}\\}_{p,q=1}^{K}$ is a feasible
solution of equation 8, we have

$\displaystyle\begin{aligned}
d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW})&\leq\sideset{}{{}_{p,q=1}^{K}}{\sum}\langle\bm{L}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)},\bm{T}^{*}),\bm{T}^{*}\rangle\\\
&=\Bigl{\langle}\bm{L}\left(\sideset{}{{}_{k=1}^{K}}{\sum}\bm{D}_{s}^{(k)},\sideset{}{{}_{k=1}^{K}}{\sum}\bm{D}_{t}^{(k)},\bm{T}^{*}\right),\bm{T}^{*}\Bigr{\rangle}\\\
&=d_{GW}\left(\sideset{}{{}_{k=1}^{K}}{\sum}\bm{D}_{s}^{(k)},\sideset{}{{}_{k=1}^{K}}{\sum}\bm{D}_{t}^{(k)}\right).\end{aligned}$
(11)

In other words, compared to the $\bm{T}^{*}$ obtained by existing linear
fusion-based multi-modal graph matching methods, the $\mathcal{T}$ obtained by
DHOT-GM always contains some matching results corresponding to smaller GW
distances.

Algorithm 1 The computation of $d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})$

0: Marginals $\bm{\mu}_{s}$, $\bm{\nu}_{t}$, relational matrix $\bm{D}_{s}$,
$\bm{D}_{t}$, matching matrix $\bm{T}$, entropic regularizer $\lambda$, the
number of outer/inner iterations $\\{M,N\\}$.

1: Initialize $\bm{b}=\bm{\mu}_{t}$ and
$\bm{T}=\bm{\mu}_{s}\bm{\mu}_{t}^{\top}$

2: for $m=1,\cdots,M$ do

3:
$\bm{G}=\exp{(-\bm{L}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)},\bm{T})/\lambda)}\odot\bm{T}$

4: for $n=1,\cdots,N$ do

5: $\bm{a}=\bm{\mu}_{s}/(\bm{G}\bm{b})$, and then
$\bm{b}=\bm{\mu}_{t}/(\bm{G}^{\top}\bm{a})$

6: end for

7: $\bm{T}=\operatorname{diag}(\bm{a})\bm{G}\operatorname{diag}(\bm{b})$

8: end for

9:
$d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})=\langle\bm{L}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)},\bm{T}),\bm{T}\rangle$

10: return $d_{GW}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})$, and
$\bm{T}^{(p,q)}\leftarrow\bm{T}$.

###  3.4 Optimization Algorithm

We propose a bi-level learning algorithm to solve the DHOT problem in equation
8. In the lower-level, we need to compute $K^{2}$ GW distances. In this study,
we apply the proximal gradient algorithm [41] to compute each GW distance
efficiently. In theory, the algorithm ensures that the variables converge to a
stationary point [42]. The algorithmic scheme is shown in Algorithm 1. For a
graph with $V$ nodes and $K$ modalities, the computational complexity of this
algorithm is $\mathcal{O}(K^{2}V^{3})$ and can be reduced to
$\mathcal{O}(K^{2}V^{2}d)$ when considering the low-rank structure of
relational matrices [27].

In the upper-level, we need to $i)$ compute a Wasserstein distance with
$K\times K$ size and $ii)$ update the marginals. We can achieve these two
steps jointly in an algorithmic framework based on the Sinkhorn-scaling
algorithm [5]. Specifically, we rewrite the upper-level problem in equation 7
by introducing an entropic regularizer, i.e.,

$\displaystyle\begin{aligned}
\sideset{}{{}_{\bm{\Theta}\in\Omega(\bm{\nu}_{s},\bm{\nu}_{t})}}{\min}\langle\bm{D}_{GW},\bm{\Theta}\rangle+\lambda
H(\bm{\Theta}),\end{aligned}$ (12)

where $H(\bm{\Theta})=\langle\bm{\Theta},\log\bm{\Theta}\rangle$, and
$\lambda$ is the hyperparameter controlling the importance of the entropy
term.

Algorithm 2 Compute $d_{W}(\bm{\nu}_{s},\bm{\nu}_{t};\bm{D}_{GW})$ with
learnable $\\{\bm{\nu}_{s},\bm{\nu}_{t}\\}$

0: Marginals $\bm{\nu}_{s}$, $\bm{\nu}_{t}$, cost matrix $\bm{D}_{GW}$, the
number of modalities $K$, entropic regularizer $\lambda$, learning rate
$\gamma$, the number of Sinkhorn-Knopp iterations $M$, the importance factor
matrix $\Theta$.

1: $\bm{b}^{(0)}=\frac{1}{K}\bm{1}_{K}$,
$\bm{\Theta}=\bm{\nu}_{s}\bm{\nu}_{t}^{\top}$, and
$\bm{Q}=\exp{(-\bm{D}_{GW}/\lambda)}$

2: for $m=1,...,M$ do

3: $\bm{a}^{(m)}=\bm{\nu}_{s}/(\bm{Q}\bm{b}^{(m-1)})$, and then
$\bm{b}^{(m)}=\bm{\nu}_{t}/(\bm{Q}^{\top}\bm{a}^{(m-1)})$

4: end for

5:
$\bm{\nu}_{s}=\bm{\nu}_{s}-\gamma(\log\bm{a}-\frac{\log\bm{a}^{\top}\bm{1}}{\bm{Q}}\bm{1})/\lambda$,
$\bm{\nu}_{t}=\bm{\nu}_{t}-\gamma(\log\bm{b}-\frac{\log\bm{b}^{\top}\bm{1}}{\bm{Q}}\bm{1})/\lambda$

6: return
$\bm{\Theta}\leftarrow\operatorname{diag}(\bm{a}^{(M)})\bm{Q}\operatorname{diag}(\bm{b}^{(M)})$,
$\bm{\nu}_{s}$, and $\bm{\nu}_{t}$.

This entropic regularizer improves the smoothness of the original problem.
Accordingly, the entropic OT problem in equation 12 can be solved efficiently
by the Sinkhorn-scaling algorithm [5], as shown in Algorithm 2, whose
computational complexity is $\mathcal{O}(K^{2})$.

When updating the marginals, we apply the gradient descent algorithm, i.e.,

$\displaystyle\begin{aligned}
\bm{\nu}_{s}\leftarrow\bm{\nu}_{s}-\gamma\frac{\partial
d_{w}(\bm{\nu}_{s},\bm{\nu}_{t})}{\partial\bm{\nu}_{s}},~{}~{}\bm{\nu}_{t}\leftarrow\bm{\nu}_{t}-\gamma\frac{\partial
d_{w}(\bm{\nu}_{s},\bm{\nu}_{t})}{\partial\bm{\nu}_{t}},\end{aligned}$ (13)

where $\gamma$ is the learning rate. The computation of the gradients can be
efficiently approximated associated with the Sinkhorn-scaling iterations [39,
24], as shown in Line 5 of Algorithm 2.

In summary, our DHOT-GM method first computes $K^{2}$ GW distances and derives
the corresponding optimal transport matrices, each of which indicates a
matching result for graph nodes. Then, the significance of the matrices is
computed by solving an entropic OT problem with learnable marginals. The final
matching result is obtained by aggregating all the matching matrices according
to equation 9. Algorithm 3 gives the pipeline of our method.

Algorithm 3 DHOT-GM

0: Source graph $\mathcal{G}_{s}=(\mathcal{V}_{s},\bm{A}_{s},\bm{X}_{s})$,
target graph $\mathcal{G}_{t}=(\mathcal{V}_{t},\bm{A}_{t},\bm{X}_{t})$, the
number of modalities $K$, the number of training iterations $T$.

1: Reformulate the two graphs as
$\mathcal{G}_{s}=(\mathcal{V}_{s},\mathcal{D}_{s})$ and
$\mathcal{G}_{t}=(\mathcal{V}_{t},\mathcal{D}_{t})$ according to equation 5.

2: $\bm{\nu}_{s}=\frac{1}{K}\bm{1}_{K}$, $\bm{\nu}_{t}=\frac{1}{K}\bm{1}_{K}$,
$\bm{\mu}_{s}=\frac{1}{|\mathcal{V}_{s}|}\bm{1}_{|\mathcal{V}_{s}|}$,
$\bm{\mu}_{t}=\frac{1}{|\mathcal{V}_{t}|}\bm{1}_{|\mathcal{V}_{t}|}$

3: $\bm{T}=\bm{\mu}_{s}\bm{\mu}_{t}^{\top}$

4: for $t=1,\cdots,T$ do

5: for $\bm{D}_{s}^{(p)}\in\mathcal{D}_{s},\bm{D}_{t}^{(q)}\in\mathcal{D}_{t}$
do

6: Get $d_{GW}^{(p,q)}(\bm{D}_{s}^{(p)},\bm{D}_{t}^{(q)})$ and
$\bm{T}^{(p,q)}$ via Algorithm 1.

7: end for

8: Construct $\mathcal{T}=\\{\bm{T}^{(p,q)}\\}_{p=1,q=1}^{K}$ and
$\bm{C}=[d_{GW}^{(p,q)}]$.

9: Update $\bm{\nu}_{s}$, $\bm{\nu}_{t}$ and $\Theta$ via Algorithm 2.

10: $\bm{T}=\sum_{p=1}^{K}\sum_{q=1}^{K}\theta_{pq}\bm{T}^{(p,q)}$.

11: end for

Table 1: Description of the datasets. Dataset | #Nodes | #Edges | Dim. of Attr.
---|---|---|---
Douban Online-Offline | 3,906 | 16,328 | 538
1,128 | 3,022 | 538
ACM-DBLP | 9,872 | 39,561 | 17
9,916 | 44,808 | 17
PPI | 1,767 | 17,042 | 50
Cora | 2,708 | 5,278 | 1,433
Table 2: Comparison for the read-world graph matching on the node correctness (%) and runtime (second). For each dataset, we bold the best result in each methodological category and highlight the global optimal performance in red. Type | semi-supervised | unsupervised
---|---|---
Method | IsoRank | FINAL | DeepLink | CENALP | UniAlign | REGAL | GAlign | WAlign | GWL | FGW | SLOTAlign | DHOT-GM
ACM-DBLP | NC@1 | 17.09 | 30.25 | 12.19 | 34.81 | 0.08 | 3.49 | 58.43 | 63.91 | 4.02 | 49.11 | 65.52 | 68.11
NC@5 | 35.42 | 55.32 | 32.98 | 51.86 | 0.41 | 9.74 | 78.78 | 83.86 | 5.96 | 52.06 | 84.05 | 85.75
NC@10 | 47.11 | 67.95 | 44.58 | 62.23 | 0.91 | 13.61 | 84.46 | 89.12 | 7.34 | 52.09 | 87.76 | 90.25
Time(s) | 208.5 | 472.4 | 2369.3 | 20296.3 | 19.8 | 540.3 | 213.4 | 672.6 | 828.7 | 106.8 | 539.4 | 1435.7
Douban Online-Offline | NC@1 | 30.86 | 52.24 | 8.86 | 23.70 | 0.63 | 1.97 | 44.10 | 39.53 | 0.27 | 58.86 | 49.91 | 54.03
NC@5 | 50.09 | 89.80 | 22.36 | 38.10 | 3.49 | 6.44 | 67.98 | 61.63 | 0.72 | 63.23 | 74.69 | 74.06
NC@10 | 61.27 | 95.97 | 30.95 | 43.56 | 8.23 | 10.11 | 77.73 | 71.02 | 1.07 | 63.69 | 79.43 | 80.59
Time(s) | 5.4 | 134.9 | 286.1 | 1023.8 | 1.5 | 69.5 | 45.5 | 43.9 | 25.1 | 83.3 | 13.5 | 41.2
PPI | NC@1 | 17.71 | 38.09 | 10.36 | 28.35 | 0.68 | 6.68 | 67.18 | 64.63 | 11.38 | 83.32 | 76.63 | 86.98
NC@5 | 28.64 | 52.91 | 14.94 | 41.43 | 2.77 | 18.11 | 78.49 | 73.23 | 13.30 | 83.32 | 82.06 | 91.06
NC@10 | 34.75 | 55.35 | 18.05 | 47.82 | 4.92 | 25.69 | 82.57 | 76.91 | 16.07 | 83.32 | 83.76 | 92.19
Time(s) | 6.1 | 3.6 | 624.9 | 1546.7 | 1.9 | 28.8 | 18.3 | 45.8 | 14.9 | 5.3 | 8.1 | 31.3
Cora | NC@1 | 16.88 | 67.25 | 10.86 | 76.55 | 0.41 | 5.50 | 98.38 | 93.72 | 0.03 | 99.19 | 98.86 | 99.45
NC@5 | 34.12 | 81.35 | 27.81 | 86.85 | 1.85 | 11.11 | 99.85 | 96.01 | 0.11 | 99.19 | 99.89 | 100.00
NC@10 | 42.95 | 85.52 | 36.34 | 88.81 | 3.91 | 14.73 | 99.96 | 96.38 | 0.37 | 99.19 | 99.89 | 100.00
Time(s) | 43.9 | 353.8 | 1449.1 | 3128.2 | 1.9 | 50.3 | 30.8 | 109.9 | 27.7 | 4.7 | 22.5 | 78.7

##  4 Experiments

###  4.1 Experimental Setup

####  4.1.1 Baselines

To demonstrate the effectiveness of our DHOT-GM method, we verify it on the
attribute graph matching task compared with baselines. We select 7
unsupervised graph matching methods. Among these methods, UniAlign [17] is
QAP-based, REGAL [12], WAlign [9], and GAlign [34] are node embedding-based,
and GWL [42], FGW [36], SLOTAlign [33] are OT-based. To demonstrate the
advantages of DHOT-GM as an unsupervised method, we also select 4 semi-
supervised graph matching baselines for comparison, i.e., IsoRank [29], FINAL
[50], DeepLink [54] and CENALP [7]. Note that these baselines require a prior
matching matrix or matching node pairs as training labels. We use 10% of the
ground-truth when implementing the semi-supervised methods. All the
experiments are implemented in PyTorch and conducted on NVIDIA GeForce RTX
3090.

####  4.1.2 Datasets

We evaluate baselines and our DHOT-GM on two datasets and each dataset
contains one or two real-world graphs with their topology and attribute
information. Table 1 shows the statistics of the datasets. Details for
datasets are described below.

  * •

ACM-DBLP [50] is a two co-authorship networks dataset for publication
information. The ACM network includes 9,916 authors and 44,808 co-authorships,
while the DBLP network includes 9,872 authors and 39,561 co-authorships. Node
attributes are composed of the number of papers published by the author in 17
locations. The 6,325 co-authors in the two networks constitute the ground-
truth matching node pairs.

  * •

Douban Online-Offline [51] includes an online graph with 16,328 interactions
among 3,906 users and an offline graph with 3,022 interactions among 1,118
users. The user’s location represents node attributes. The ground-truth
matching is the 1,118 users appearing in both graphs.

  * •

Cora [45] is a citation network where nodes mean publications and edges mean
citation relationships. It includes 2,708 nodes and 5,278 edges and each node
has 1,433 attributes.

  * •

PPI [55] is a protein-protein interaction network dataset containing 24
graphs. We select the first graph which contains 1,767 nodes with 50
attributes and 17,042 edges for our task.

Since Cora and PPI only contain one graph, we generate the other graph by
cutting $E$% edges in the original graph randomly and adding $E$% random edges
accordingly. Here, $E\in\\{10,20,...,60\\}$, indicating different noise
levels.

####  4.1.3 Metrics

We evaluate the performance of different methods by the commonly used top-K
node correctness NC@K in the literature. Given a node of the graph
$\mathcal{G}_{s}$, NC@K takes the most similar K nodes from all possible
matching in the graph $\mathcal{G}_{t}$ as a Top-K list, and finally
calculates the percentage of ground-truth matching in the list.

###  4.2 Numerical Comparisons

####  4.2.1 Node Correctness and Runtime

We first show the matching performance of DHOT-GM on the real-world graph
matching task. In Table 2, it can be observed that DHOT-GM achieves the best
results on ACM-DBLP, PPI, and Cora. For Douban Online-Offline, although DHOT-
GM is slightly lower than FGW on NC@1, it outperforms all the unsupervised
methods on NC@10. We believe that this phenomenon is due to the large
disparity in the number of nodes in Douban Online-Offline, and the information
imbalance between modalities is more serious, which makes it difficult to
achieve exact matching without prior knowledge. However, even in this case,
DHOT-GM still outperforms FINAL which is the best in semi-supervised methods
on NC@1. This shows that DHOT-GM remains competitive with the semi-supervised
methods in an imbalanced situation of nodes. In addition, we note that the
performance of some unsupervised baselines like UniAlign, REGAL, and GWL is
poor on all datasets, which is because all these methods consider mainly the
graph topology for matching, and lack effective utilization of node
attributes. We also compare the runtime of DHOT-GM and baselines and DHOT-GM
is comparable in efficiency to existing unsupervised graph matching methods.

####  4.2.2 Robustness to Noise

Furthermore, we also investigate the impact of noise on DHOT-GM. Taking the
PPI dataset as an example, we continuously increase the ratio of randomly
reconnected edges to generate the graph. In Figure 3, we observe that DHOT-GM
still shows significant performance even after 60% of edges are affected by
noise, while other unsupervised methods that perform well at low noise levels
cannot guarantee this. This indicates that DHOT-GM has strong robustness at
high noise levels.

Figure 3: Results under different noise levels on PPI dataset.

###  4.3 Ablation Study

####  4.3.1 The Number of Modalities

We first investigate the matching performance of DHOT-GM with different
numbers of graph modalities selected. As shown in Table 3, the performance on
ACM-DBLP increases with the number of modalities. This shows that DHOT-GM is
able to fully utilize the matching results between multiple modalities of two
graphs on this dataset. On Douban Online-Offline, we observe that the highest
performance is achieved when the number of modalities is equal to 3.
Continuing to increase the number of modalities leads to a decrease in
performance instead. We believe that the number of nodes between the two
graphs in Douban Online-Offline is unbalanced, which leads to more significant
differences between their modalities and thus makes it more difficult to
match.

Table 3: Effects of the number of modalities. $K$ | ACM-DBLP | Douban Online-Offline
---|---|---
NC@1 | NC@5 | NC@10 | NC@1 | NC@5 | NC@10
2 | 66.62 | 85.61 | 89.96 | 41.14 | 57.16 | 60.29
3 | 68.11 | 85.75 | 90.25 | 54.03 | 74.06 | 80.59
4 | 68.95 | 86.53 | 90.28 | 47.32 | 72.81 | 76.92
Table 4: Ablation study on using different modalities. Used Modalities | ACM-DBLP | Douban Online-Offline
---|---|---
NC@1 | NC@5 | NC@10 | NC@1 | NC@5 | NC@10
Topology + Attribute | 66.97 | 85.34 | 89.36 | 41.14 | 57.16 | 60.29
Topology + Subgraph | 0.46 | 1.42 | 2.48 | 34.53 | 58.14 | 63.69
Attribute + Subgraph | 33.33 | 54.50 | 63.76 | 5.01 | 11.54 | 18.07
All | 68.11 | 85.75 | 90.25 | 54.03 | 74.06 | 80.59

####  4.3.2 The Contribution of Different Modalities

To further explore which modality can most affect the performance of graph
matching, we also conduct experiments for DHOT-GM through pairwise
combinations of 3 modalities. Results in Table 4 show that on the ACM-DBLP
dataset, the node attributes are necessary for the matching performance, but
on Douban Online-Offline, the graph topology is essential. This indicates that
for the attribute graph matching task, the matching performance is controlled
by different modalities in different dataset scenarios.

####  4.3.3 The Learning Rate of Marginal Update

We also explore the impact of the learning rate of the marginal update. We
take the value of the learning rate $\gamma$ from
$\\{0,0.01,0.05,0.1,0.5,1\\}$. It is observed that DHOT-GM has a tendency to
improve the performance on both datasets as the learning rate gradually
increases in Table 5. This phenomenon is consistent with our initial
assumption that the matching result between different modalities has different
significance. Learnable weights for different modalities can achieve better
matching performance than assigning the same uniform distribution to each
modality.

Table 5: Effects of updating marginals. $\gamma$ | ACM-DBLP | Douban Online-Offline
---|---|---
NC@1 | NC@5 | NC@10 | NC@1 | NC@5 | NC@10
0 | 61.34 | 84.41 | 89.22 | 24.96 | 56.62 | 66.46
0.01 | 64.79 | 84.60 | 89.30 | 24.87 | 56.71 | 66.01
0.05 | 65.52 | 84.77 | 89.28 | 26.12 | 56.62 | 65.74
0.1 | 56.4 | 84.52 | 89.12 | 28.71 | 59.12 | 67.62
0.5 | 67.73 | 85.63 | 89.74 | 38.28 | 68.96 | 75.04
1.0 | 68.11 | 85.75 | 90.25 | 54.03 | 74.06 | 80.59
Figure 4: The upper-level OT matrices (i.e., $\bm{\Theta}$’s) learned for
different datasets. Figure 5: The lower-level OT matrices (i.e.,
$\bm{T}^{(p,q)}$’s) for nodes across different modalities. For the convenience
of visualization, we take the first 100 nodes for all datasets. The darker the
color, the higher the value.

####  4.3.4 The Rationality of Using Cross-modal Matching

We visualize the learned OT matrices by DHOT-GM for different datasets. In
Figure 4, we discover that the weight for graph topology matching is dominant
on the ACM-DBLP and Douban Online-Offline datasets, while on the PPI and Cora
datasets, the OT matrices for modalities are more balanced. We believe this is
because on the ACM-DBLP and Douban Online-Offline datasets, the differences
between the two graphs are greater in the node attributes and subgraph
structures, whereas the graph topology is based only on the adjacency matrix
so it provides the main performance in graph matching. However, on the PPI and
Cora datasets, we generate a noisy version of the original graph, so the
relational matrices of the two are closer for each modality, and effective
matching results can be provided between different modalities. We further
visualize the results of some cross-modal relational matrices matching in
Figure 5 on PPI and Cora, and observe that they exhibit a similar diagonal
structure to the ground-truth. This phenomenon indicates that DHOT-GM can
effectively utilize the potential of cross-modal matching.

####  4.3.5 The Rationality of Only Using Low-pass Relational Matrices

As aforementioned in Section 3.2, the relational matrices corresponding to the
subgraph structures, i.e., $\\{\bm{D}^{k}\\}_{k=3}^{K}$, are achieved by
passing the node attributes through low-pass graph filters iteratively and
computing their inner products. Then, a question arises — can we derive the
relational matrices by high-pass graph filtering (e.g., constructing
$\bm{D}_{H}=\hat{\bm{L}}\bm{X}(\hat{\bm{L}}\bm{X})^{\top}$, where
$\hat{\bm{L}}$ is the normalized graph Laplacian matrix)? In our opinion,
applying such high-pass relational matrices to graph matching tasks may be
inappropriate. In particular, graph matching is naturally sensitive to the
topological noise (e.g., the random connections and disconnections of edges)
in graphs [34, 33], while the high-pass graph filtering encodes the
discrepancy of node attributes along graph edges, whose output is largely
influenced by the noise of the edges. As a result, the high-pass relational
matrix $\bm{D}_{H}$ amplifies the topological noise of the graph, and matching
graphs based on their $\bm{D}_{H}$’s often leads to undesired results.

To verify the above claim, we explore the impact of the high-pass relational
matrices on the performance of DHOT-GM, constructing a new multi-modal
relational matrix set $\mathcal{D}_{new}=\mathcal{D}\cup\\{\bm{D}_{H}\\}$ and
implementing our DHOT-GM method accordingly. The results in Table 6 show that
applying $\bm{D}_{H}$ results in the performance degradation. Additionally,
because of the noise within it, DHOT-GM encounters numerical issues under the
original parameter settings — the proximal gradient algorithm suffers from the
numerical instability when computing the GW distance relevant to $\bm{D}_{H}$.

Table 6: Ablation study on adding high-pass mechanism. Relational | Original #Epochs | Reduced #Epochs
---|---|---
matrix set | NC@1 | NC@5 | NC@10 | NC@1 | NC@5 | NC@10
Original $\mathcal{D}$ | 54.03 | 74.06 | 80.59 | 35.42 | 59.75 | 64.58
$\mathcal{D}\cup\\{\bm{D}_{H}\\}$ | NaN | NaN | NaN | 32.02 | 57.96 | 62.79

##  5 Conclusion

In this work, we propose a novel DHOT framework for graph matching using
multi-modal information from graphs. Given the multi-modal relational matrices
of graphs, the proposed framework makes attempts to leverage the cross-modal
matching results and demonstrate their usefulness. The experimental results
show that our method can achieve encouraging performance in unsupervised
attribute graph matching.

In the future, we plan to explore the impact of modal imbalance on graph
matching performance, making the framework more robust and scalable when
dealing with different source and target graph structures. At the same time,
we also hope to reduce duplicate calculations of unimportant modal
information, thereby improving the efficiency of the algorithm.

## References

  * [1] D. Alvarez-Melis, T. Jaakkola, and S. Jegelka.  Structured optimal transport.  In International conference on artificial intelligence and statistics, pages 1771–1780. PMLR, 2018.
  * [2] T. S. Caetano, J. J. McAuley, L. Cheng, Q. V. Le, and A. J. Smola.  Learning graph matching.  IEEE transactions on pattern analysis and machine intelligence, 31(6):1048–1058, 2009.
  * [3] L. Chen, Z. Gan, Y. Cheng, L. Li, L. Carin, and J. Liu.  Graph optimal transport for cross-domain alignment.  In International Conference on Machine Learning, pages 1542–1553. PMLR, 2020.
  * [4] Y. Chen, T. T. Georgiou, and A. Tannenbaum.  Optimal transport for gaussian mixture models.  IEEE Access, 7:6269–6278, 2018.
  * [5] M. Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  In C. J. C. Burges, L. Bottou, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2292–2300, 2013.
  * [6] M. Defferrard, X. Bresson, and P. Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  Advances in neural information processing systems, 29, 2016.
  * [7] X. Du, J. Yan, and H. Zha.  Joint link prediction and network alignment via cross-graph embedding.  In S. Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 2251–2257. ijcai.org, 2019.
  * [8] M. Fey, J. E. Lenssen, C. Morris, J. Masci, and N. M. Kriege.  Deep graph matching consensus.  In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
  * [9] J. Gao, X. Huang, and J. Li.  Unsupervised graph alignment with wasserstein distance discriminator.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 426–435, 2021.
  * [10] A. Genevay, G. Peyré, and M. Cuturi.  Learning generative models with sinkhorn divergences.  In International Conference on Artificial Intelligence and Statistics, pages 1608–1617. PMLR, 2018.
  * [11] S. Hashemifar, Q. Huang, and J. Xu.  Joint alignment of multiple protein–protein interaction networks via convex optimization.  Journal of Computational Biology, 23(11):903–911, 2016.
  * [12] M. Heimann, H. Shen, T. Safavi, and D. Koutra.  REGAL: representation learning-based graph alignment.  In A. Cuzzocrea, J. Allan, N. W. Paton, D. Srivastava, R. Agrawal, A. Z. Broder, M. J. Zaki, K. S. Candan, A. Labrinidis, A. Schuster, and H. Wang, editors, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pages 117–126. ACM, 2018.
  * [13] B. Hooi, K. Shin, H. A. Song, A. Beutel, N. Shah, and C. Faloutsos.  Graph-based fraud detection in the face of camouflage.  ACM Transactions on Knowledge Discovery from Data (TKDD), 11(4):1–26, 2017.
  * [14] M. Huang, Y. Liu, X. Ao, K. Li, J. Chi, J. Feng, H. Yang, and Q. He.  Auc-oriented graph neural network for fraud detection.  In Proceedings of the ACM Web Conference 2022, pages 1311–1321, 2022.
  * [15] L. V. Kantorovich.  On the translocation of masses.  In Dokl. Akad. Nauk. USSR (NS), volume 37, pages 199–201, 1942.
  * [16] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
  * [17] D. Koutra, H. Tong, and D. Lubensky.  Big-align: Fast bipartite graph alignment.  In 2013 IEEE 13th international conference on data mining, pages 389–398. IEEE, 2013.
  * [18] J. Lee, M. Dabagia, E. Dyer, and C. Rozell.  Hierarchical optimal transport for multimodal distribution alignment.  Advances in neural information processing systems, 32, 2019.
  * [19] C. Li, S. Wang, H. Wang, Y. Liang, P. S. Yu, Z. Li, and W. Wang.  Partially shared adversarial learning for semi-supervised multi-platform user identity linkage.  In W. Zhu, D. Tao, X. Cheng, P. Cui, E. A. Rundensteiner, D. Carmel, Q. He, and J. X. Yu, editors, Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM 2019, Beijing, China, November 3-7, 2019, pages 249–258. ACM, 2019.
  * [20] C. Li, S. Wang, P. S. Yu, L. Zheng, X. Zhang, Z. Li, and Y. Liang.  Distribution distance minimization for unsupervised user identity linkage.  In A. Cuzzocrea, J. Allan, N. W. Paton, D. Srivastava, R. Agrawal, A. Z. Broder, M. J. Zaki, K. S. Candan, A. Labrinidis, A. Schuster, and H. Wang, editors, Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22-26, 2018, pages 447–456. ACM, 2018.
  * [21] X. Liu, H. Hong, X. Wang, Z. Chen, E. Kharlamov, Y. Dong, and J. Tang.  Selfkg: self-supervised entity alignment in knowledge graphs.  In Proceedings of the ACM Web Conference 2022, pages 860–870, 2022.
  * [22] Y. Liu, H. Ding, D. Chen, and J. Xu.  Novel geometric approach for global alignment of PPI networks.  In S. P. Singh and S. Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 31–37. AAAI Press, 2017.
  * [23] E. M. Loiola, N. M. M. De Abreu, P. O. Boaventura-Netto, P. Hahn, and T. Querido.  A survey for the quadratic assignment problem.  European journal of operational research, 176(2):657–690, 2007.
  * [24] D. Luo, H. Xu, and L. Carin.  Differentiable hierarchical optimal transport for robust multi-view learning.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
  * [25] F. Mémoli.  Gromov–wasserstein distances and the metric approach to object matching.  Foundations of computational mathematics, 11:417–487, 2011.
  * [26] G. Peyré, M. Cuturi, and J. Solomon.  Gromov-wasserstein averaging of kernel and distance matrices.  In M. Balcan and K. Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2664–2672. JMLR.org, 2016.
  * [27] M. Scetbon, G. Peyré, and M. Cuturi.  Linear-time gromov wasserstein distances using low rank couplings and costs.  In International Conference on Machine Learning, pages 19347–19365. PMLR, 2022.
  * [28] B. Schmitzer and C. Schnörr.  A hierarchical approach to optimal transport.  In International conference on scale space and variational methods in computer vision, pages 452–464. Springer, 2013.
  * [29] R. Singh, J. Xu, and B. Berger.  Global alignment of multiple protein interaction networks with application to functional orthology detection.  Proceedings of the National Academy of Sciences, 105(35):12763–12768, 2008.
  * [30] J. Solomon, G. Peyré, V. G. Kim, and S. Sra.  Entropic metric alignment for correspondence problems.  ACM Transactions on Graphics (ToG), 35(4):1–13, 2016.
  * [31] B. Su and G. Hua.  Order-preserving wasserstein distance for sequence matching.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1049–1057, 2017.
  * [32] Z. Sun, Q. Zhang, W. Hu, C. Wang, M. Chen, F. Akrami, and C. Li.  A benchmarking study of embedding-based entity alignment for knowledge graphs.  ArXiv preprint, abs/2003.07743, 2020.
  * [33] J. Tang, W. Zhang, J. Li, K. Zhao, F. Tsung, and J. Li.  Robust attributed graph alignment via joint structure learning and optimal transport.  ArXiv preprint, abs/2301.12721, 2023.
  * [34] H. T. Trung, T. Van Vinh, N. T. Tam, H. Yin, M. Weidlich, and N. Q. V. Hung.  Adaptive network alignment with unsupervised and multi-order convolutional networks.  In 2020 IEEE 36th International Conference on Data Engineering (ICDE), pages 85–96. IEEE, 2020.
  * [35] S. Umeyama.  An eigendecomposition approach to weighted graph matching problems.  IEEE transactions on pattern analysis and machine intelligence, 10(5):695–703, 1988.
  * [36] T. Vayer, N. Courty, R. Tavenard, L. Chapel, and R. Flamary.  Optimal transport for structured data with application on graphs.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6275–6284. PMLR, 2019.
  * [37] M. Vento and P. Foggia.  Graph matching techniques for computer vision.  In Image Processing: Concepts, Methodologies, Tools, and Applications, pages 381–421. IGI Global, 2013.
  * [38] C. Vincent-Cuaz, T. Vayer, R. Flamary, M. Corneli, and N. Courty.  Online graph dictionary learning.  In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 10564–10574. PMLR, 2021.
  * [39] Y. Xie, Y. Mao, S. Zuo, H. Xu, X. Ye, T. Zhao, and H. Zha.  A hypergradient approach to robust regression without correspondence.  In International Conference on Learning Representations, 2020.
  * [40] H. Xu.  Gromov-wasserstein factorization models for graph clustering.  In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 6478–6485. AAAI Press, 2020.
  * [41] H. Xu, D. Luo, and L. Carin.  Scalable gromov-wasserstein learning for graph partitioning and matching.  In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d’Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3046–3056, 2019.
  * [42] H. Xu, D. Luo, H. Zha, and L. Carin.  Gromov-wasserstein learning for graph matching and node embedding.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6932–6941. PMLR, 2019.
  * [43] Y. Yan, S. Zhang, and H. Tong.  Bright: A bridging algorithm for network alignment.  In Proceedings of the Web Conference 2021, pages 3907–3917, 2021.
  * [44] J. Yang, Y. Liu, and H. Xu.  Hotnas: Hierarchical optimal transport for neural architecture search.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11990–12000, 2023.
  * [45] Z. Yang, W. W. Cohen, and R. Salakhutdinov.  Revisiting semi-supervised learning with graph embeddings.  In M. Balcan and K. Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 40–48. JMLR.org, 2016.
  * [46] M. Yurochkin, S. Claici, E. Chien, F. Mirzazadeh, and J. M. Solomon.  Hierarchical optimal transport for document representation.  Advances in neural information processing systems, 32, 2019.
  * [47] A. Zanfir and C. Sminchisescu.  Deep learning of graph matching.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2684–2693, 2018.
  * [48] M. Zaslavskiy, F. Bach, and J.-P. Vert.  A path following algorithm for the graph matching problem.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12):2227–2242, 2008.
  * [49] Z. Zeng, S. Zhang, Y. Xia, and H. Tong.  Parrot: Position-aware regularized optimal transport for network alignment.  In Proceedings of the ACM Web Conference 2023, pages 372–382, 2023.
  * [50] S. Zhang and H. Tong.  FINAL: fast attributed network alignment.  In B. Krishnapuram, M. Shah, A. J. Smola, C. C. Aggarwal, D. Shen, and R. Rastogi, editors, Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, pages 1345–1354. ACM, 2016.
  * [51] S. Zhang and H. Tong.  Attributed network alignment: Problem definitions and fast solutions.  IEEE Transactions on Knowledge and Data Engineering, 31(9):1680–1692, 2018.
  * [52] S. Zhang, H. Tong, L. Jin, Y. Xia, and Y. Guo.  Balancing consistency and disparity in network alignment.  In Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, pages 2212–2222, 2021.
  * [53] F. Zhou and F. D. la Torre.  Factorized graph matching.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16-21, 2012, pages 127–134. IEEE Computer Society, 2012.
  * [54] F. Zhou, L. Liu, K. Zhang, G. Trajcevski, J. Wu, and T. Zhong.  Deeplink: A deep learning approach for user identity linkage.  In IEEE INFOCOM 2018-IEEE conference on computer communications, pages 1313–1321. IEEE, 2018.
  * [55] M. Zitnik and J. Leskovec.  Predicting multicellular function through multi-layer tissue networks.  Bioinformatics, 33(14):i190–i198, 2017.


#  Quantum Electrodynamics and the Ether

Iver Brevik1 1Department of Energy and Process Engineering, Norwegian
University of Science and Technology, N-7491 Trondheim, Norway

###### Abstract

The ether concept - abandoned for a long time but reinstated by Dirac in
1951-1953 - has in recent years emerged into a fashionable subject in
theoretical physics, now usually with the name of the Einstein-Dirac ether. It
means that one special inertial frame is singled out, as the ”rest frame”.
What is emphasized in the present note, is that the idea is a natural example
of the covariant theory of quantum electrodynamics in media if the refractive
index is set equal to unity. A treatise on this case of quantum
electrodynamics was given by the present author back in 1971, published then
only within a preprint series. The present version is a brief summary of that
formalism, with a link to the original paper. We think it is one of the first
treatises on modern ether theory.

Consider first the general case where a uniform and isotropic medium with
constant refractive index $n=\sqrt{\varepsilon\mu}$ is moving with constant
four-velocity $V_{\mu}$. We employ coordinates $x_{\mu}=(x_{0},{\bf
x})=(t,{\bf x})$, with $g_{00}=+1$ and put $\hbar=c=1$, so that
$V^{\mu}V_{\mu}=1$. This means that one special inertial frame is singled out,
namely the medium’s rest frame where $V^{0}=1$.

Assume now that $n=1$, but maintain the overall medium picture. In classical
electrodynamics, a free field corresponds to the Lagrangian density

${\cal L}=-\frac{1}{4}F_{\mu\nu}F^{\mu\nu},$ (1)

where $F_{\mu\nu}=\partial_{\mu}A_{\nu}-\partial_{\nu}A_{\mu}$. The
variational equations obtained from Eq. (1) are

$\Box{A}_{\mu}-\partial_{\mu}\partial^{\nu}A_{\nu}=0,$ (2)

($\Box=\partial^{\mu}\partial_{\mu})$. These are equivalent to Maxwell’s
equations

$\partial_{\lambda}F_{\mu\nu}+\partial_{\mu}F_{\nu\lambda}+\partial_{\nu}F_{\lambda\mu}=0,\quad\partial^{\nu}F_{\mu\nu}=0.$
(3)

In quantum electrodynamics, one may instead start from the Fermi gauge
Lagrangian density

${\cal
L}=-\frac{1}{4}F_{\mu\nu}F^{\mu\nu}-\frac{1}{2}(\partial^{\mu}A_{\mu})^{2},$
(4)

and apply the conventional canonical quantization procedure. The variational
equations following from Eq. (4) are

$\Box A_{\mu}=0,$ (5)

so that in order to satisfy Maxwell’s equations, the Lorentz condition

$\partial^{\mu}A_{\mu}=0$ (6)

has to be imposed as an operator condition.

As is known, the Lorentz condition runs into conflict with the canonical
commutation rules (for a general discussion, see Ref. kallen58 ). Maxwell’s
equations (2) do not fit into the canonical scheme straightaway. Also, an
analysis based upon axiomatic field theory strocchi70 , confirms this
statement.

There exist various ways for how to solve the gauge problem in the quantum
case. One approach - the one that we will follow here - is to make use of the
special ”rest” frame anticipated above, corresponding to $V^{0}=1$. The
Fourier components of the four-potential are expanded into a covariant $k$
dependent basis $e_{\mu}^{(\lambda)}(k)$, whereby the potential components
along the basis vectors become Lorentz invariant quantities. We quantize two
of these components and retain the other two as c-numbers. The method has some
resemblance with the Coulomb gauge method, although as we work in the Fermi
gauge we have the freedom to perform gauge transformations $A_{\mu}\rightarrow
A_{\mu}+\partial_{\mu}\chi$, with the condition $\Box\chi=0$. A gauge
transformation affects the physically important c-number components an leaves
the physically important components unaffected. The Fock space gets a Lorentz
invariant meaning, and there is no need of introducing an indefinite metric.
The vacuum, defined in a gauge dependent way, is the state where both the
number of physical photons and the c-number components are zero. There is some
similarity between the present method and the the Gupta-Bleuler theory gupta50
; bleuler50 ; in the latter case the unphysical longitudinal and scalar
photons compensate each other.

Turn now to the quantization. For convenience we summarize the following
properties of the theory:

  * •

The potential $A_{\mu}$ transforms as a four-vector.

  * •

Equations (5) and (6), and accordingly also Eq. (2), are satisfied as operator
equations.

  * •

The potential components are decomposed into a covariant basis,

$a_{\mu}(k)=\sum_{\lambda=0}^{3}e_{\mu}^{(\lambda)}(k)a^{(\lambda)}(k),$ (7)

where the $e_{\mu}^{(\lambda)}$ are covariant vectors containing $k^{\mu}$ and
$V^{\nu}$. The expressions are complicated and we do not give them here,
although we mention that they fulfil the following basic properties,

$g^{\mu\nu}e_{\mu}^{(\lambda)}e_{\nu}^{(\lambda^{\prime})}=g^{\lambda\lambda^{\prime}},\quad\sum_{\lambda,\lambda^{\prime}=0}^{3}g_{\lambda\lambda^{\prime}}e_{\mu}^{(\lambda)}e_{\nu}^{(\lambda^{\prime})}=g_{\mu\nu},$
(8)

implying that in the rest system, ${\bf e}^{(2)}\times{\bf e}^{(3)}={\bf
k}/|{\bf k}|$.

We turn now to the commutation relations. Only those components which in the
rest system are orthogonal to $\bf k$ are quantized,

$[a^{(\lambda)}(k),a^{(\lambda^{\prime})^{\dagger}}(k^{\prime})]=\delta_{\bf{kk^{\prime}}}\delta_{\lambda\lambda^{\prime}},\quad\lambda=2,3,$
$[a^{(\lambda)}(k),a^{(\lambda^{\prime})^{\dagger}}(k^{\prime})]=\delta_{\bf{kk^{\prime}}}\delta_{\lambda\lambda^{\prime}},\quad\lambda=0,1.$
(9)

The components $a^{(0)},a^{(1)}$ are c-numbers, and because of the covariance
of the vectors $e_{\mu}^{(\lambda)}$ they also become Lorentz invariants. In
view of the Lorentz condition, they satisfy the relation

$a^{(0)}=a^{(1)}.$ (10)

Consider now the projection operator $\tau_{\mu\nu}$ that picks out the
transverse part $A_{\mu}^{\perp}$ of the potential,

$A_{\mu}^{\perp}=\tau_{\mu\nu}A^{\nu}.$ (11)

It is given by

$\tau_{\mu\nu}=g_{\mu\nu}+\frac{\partial_{\mu}\partial_{\nu}}{(V\cdot\partial)^{2}}-\frac{V_{\mu}\partial_{\nu}+V_{\nu}\partial_{\mu}}{V\cdot\partial}.$
(12)

Introducing the usual commutator function $D(x)$ and the anticommutator
function $D^{(1)}(x)$ kallen58 , we can write the photon propagator as

$D_{\mu\nu}(x-y)=-\frac{1}{2}\tau_{\mu\nu}D^{(1)}(x-y)-\frac{1}{2}\varepsilon(x-y)\tau_{\mu\nu}D(x-y),$
(13)

where $\varepsilon(x)=x_{0}/|x_{0}|$. In Fourier space,

$D_{\mu\nu}(k)=\frac{-i}{k^{2}+i\eta}\left[g_{\mu\nu}-V_{\mu}V_{\nu}+\frac{(k_{\mu}-V_{\mu}\,V\cdot
k)(k_{\nu}-V_{\nu}\,V\cdot k)}{(V\cdot k)^{2}-k^{2}}\right],$ (14)

with $\eta=0^{+}$.

Discussion

The underlying idea of the above formalism is the same as that of relativistic
covariant phenomenological electrodynamics in media. There is one particular
inertial frame, called the rest frame, where the formalism simplifies
significantly. In the case of a medium with $n>1$, the covariant formalism is
constructed such that it reduces to the standard electrodynamic formalism in
the rest frame.

In the formalism above, we set $n=1$, though still maintaining the picture of
a preferred inertial frame. As we have seen, the introduction of a preferred
frame makes the quantization of the electromagnetic field convenient. The
indefinite metric becomes unnecessary. It lies at hand to associate $V_{\mu}$
with the four-velocity of an ether, in a modern quantum mechanical sense. In
that way $V_{\mu}$ may be taken to reflect a physical property, instead of
being only a formal remedy to simplify the formalism. As mentioned, the ether
idea was reinstated again, in a quantum mechanical sense, by Dirac in
1951-1953 dirac51 .

The original paper of the author, published in the series ”Theoretical Physics
Seminar in Trondheim”, No. 4, 1971, cannot be uploaded here for technical
reasons, but can be assessed via the link https://hdl.handle.net/11250/2756581
.

## References

  * (1) G. Källén, in Handbuch der Physik, Volume V Part 1, edited by S. Flügge, Springer-Verlag, Berlin, 1958.
  * (2) F. Strocchi, Phys. Rev. 162, 1429 (1967); Phys. Rev. D 2, 2334 (1970).
  * (3) S. N. Gupta, Proc. Phys. Soc. 63, 681 (1950).
  * (4) K. T. Bleuler, Helv. Phys. Acta 23, 567 (1950).
  * (5) P. A. M. Dirac, Nature 168, 906 (1951); 169, 146, 702 (1952); Proceedings of the Lorentz Kamerlingh Onnes Memorial Conference, Leiden University 1953 (Amsterdam 1953), p. 888.