  Deep metric learning plays a key role in various machine learning tasks. Most
of the previous works have been confined to sampling from a mini-batch, which
cannot precisely characterize the global geometry of the embedding space.
Although researchers have developed proxy- and classification-based methods to
tackle the sampling issue, those methods inevitably incur a redundant
computational cost. In this paper, we propose a novel Proxy-based deep Graph
Metric Learning (ProxyGML) approach from the perspective of graph
classification, which uses fewer proxies yet achieves better comprehensive
performance. Specifically, multiple global proxies are leveraged to
collectively approximate the original data points for each class. To
efficiently capture local neighbor relationships, a small number of such
proxies are adaptively selected to construct similarity subgraphs between these
proxies and each data point. Further, we design a novel reverse label
propagation algorithm, by which the neighbor relationships are adjusted
according to ground-truth labels, so that a discriminative metric space can be
learned during the process of subgraph classification. Extensive experiments
carried out on widely-used CUB-200-2011, Cars196, and Stanford Online Products
datasets demonstrate the superiority of the proposed ProxyGML over the
state-of-the-art methods in terms of both effectiveness and efficiency. The
source code is publicly available at https://github.com/YuehuaZhu/ProxyGML.
