GAMa: Cross-view Video Geo-localization

The existing work in cross-view geo-localization is based on images where a ground panorama is matched to an aerial image. In this work, we focus on ground videos instead of images which provides additional contextual cues which are important for this task. There are no existing datasets for this problem, therefore we propose GAMa dataset, a large-scale dataset with ground videos and corresponding aerial images. We also propose a novel approach to solve this problem. At clip-level, a short video clip is matched with corresponding aerial image and is later used to get video-level geo-localization of a long video. Moreover, we propose a hierarchical approach to further improve the clip-level geolocalization. It is a challenging dataset, unaligned and limited field of view, and our proposed method achieves a Top-1 recall rate of 19.4% and 45.1% @1.0mile. Code and dataset are available at following link: https://github.com/svyas23/GAMa.

Introduction
Video geo-localization is a challenging problem with many applications such as navigation, autonomous driving, and robotics [11,24,5]. The problem to estimate geo-location of the source of a ground video is also faced by first respondents now and then. To solve this problem, there are two main approaches; same-view geo-localization [19,17,3] and cross-view geo-localization [13,35,16]. In same-view geo-localization, the query ground image is matched with a street view image from the reference set or gallery. Research in videos is limited to same-view geolocalization where a frame-by-frame approach is followed. This approach relies on availability of ground view images for all the locations which may not be possible always.
In such scenarios, cross-view geo-localization is more useful where the query image is matched with the corresponding aerial or satellite image. However, cross-view geo-localization is a much difficult problem since there is a large domain shift between ground and aerial view. The limited field-of-view in the ground view makes this even harder and it is sometimes difficult even for humans to identify the correct location of a given image or video.
The existing works in cross-view geo-localization follow an image based approach where a ground image is matched with an aerial image [16,29,26]. In such an approach, the contextual information available with the video is lost. We focus on the geo-localization of ground videos instead of images to utilize the context, i.e. how the view in one frame is related/located w.r.t. another frame. To the best of our knowledge there are no existing datasets which are publicly available and can be used for this problem. Thus, we have collected a new dataset, named as GAMa (Ground-video to Aerial-image Matching), which contains ground videos with GPS labels and corresponding aerial images. It consists of ∼ 1.9M aerial images and 51K ground videos where each video is around 40 seconds long. An example video with representative frames and corresponding aerial image is shown in Figure 1. We will make this dataset publicly available for further research.
We propose GAMa-Net as a benchmark method to solve this problem at clip level where we match every 0.5 second (short clip) from a long video with the corresponding aerial view. A frame-by-frame approach can also be used for video geo-localization, where a 2D convolutional network is used to get the spatial features frame-by-frame. However, following a frame-by-frame approach ignores the rich contextual information available in a video. Considering this, we propose a 3D-convolution based approach for learning the ground level features from a video. The proposed approach is trained using an image-video contrastive loss which tries to match the ground view with the aerial view. This matching provides a clip-level geo-localization.
Next, we propose a hierarchical approach which helps in improving the cliplevel geo-localization performance while providing a video-level geo-localization with the help of clip-level predictions. It takes the set of aerial images corresponding to the clips of a long video, and matches them against a larger geographical area. Therefore, it makes use of the contextual information available with the sequence of clips corresponding to a longer video.
We evaluate the proposed approach on GAMa dataset and demonstrate its effectiveness for clip/video geo-localization. We provide an analysis and propose a set of baselines to benchmark the dataset. We make the following contributions: -A novel problem formulation i.e. cross-view video geo-localization and a large-scale dataset, GAMa, with ground videos and corresponding aerial images. This is the first video dataset for this problem to the best of our knowledge. -We propose GAMa-Net, which performs cross-view video geo-localization at clip-level by matching a ground video with aerial images using an imagevideo contrastive loss. -We also propose a novel hierarchical approach which provides video-level geo-localization and utilizes aerial images at different scales to improve the clip-level geo-localization.

Related works
Traditional features of classical computer vision were earlier used for image matching in geo-localization [20,33]. As deep learning has proven successful in feature learning most of the recent studies have adopted CNN based approach for learning discriminative features for image matching [25]. The problem of image or video geo-localization is solved using either the same view, which is mostly the ground view, or cross-view. Same-view Geo-localization makes use of the large collections of geo-tagged images available online [15,34,19,17,3,2]. The problem is approached with the assumption that there is a reference dataset consisting of geo-tagged ground images and there is an image corresponding to each query image. The problem is then solved as image retrieval of the matching reference to determine the location of the query. There is some research in video geo-localization as well which is solved at frame level which is followed by trajectory smoothing [6,17,3]. However, a more complete coverage by overhead reference data such as satellite/aerial imagery has spurred a growing interest in cross-view geo-localization. Cross-view Geo-localization. Most of the recent work adopt CNN based approaches. Several studies have explored CNN architectures for matching groundlevel query images to overhead satellite images [28,26,36,12,8,29]. Triplet loss is mostly used optimization function in these studies [8,16]. Certain studies however report better results with contrastive loss [15]. Field-of-view (FOV) also plays an important role in deciding the recall rate and ground panorama is highly accurate as compared to limited FOV [8,35]. Similarly, videos also contain more visual information as seen through the trajectory of the camera and can be expected to provide more accurate geo-localization as compared to images or frames with similar FOV. Current works on cross-view geolocalization follow image based approach since the existing datasets only contain image pairs for ground and aerial view [25,16,9,31,18]. However, some papers do report testing their model on videos using a frame-by-frame approach [9]. Most popular datasets, Cross-View USA (CVUSA) dataset [30], CVACT [13], and Vo et al. [28] contain ground panorama aligned with corresponding aerial image. Recent publications have shown very high recall rate on these datasets while using panoramas however these values are quite low when using limited FOV and unaligned images, i.e. top@1 recall of upto 14% [22,31]. VIGOR [35] dataset also contains panorama however being unaligned it is more realistic. All these datasets use ground panorama which is not realistic from video geo-localization, as videos have limited FOV, neither do they have time series data required for such training. It is possible to get unaligned images and limited FOV from these datasets however, there is no existing dataset with ground videos and aerial image pairs to solve cross-view geolocalization in videos and the proposed dataset addresses this gap. Cross-view is also used for fine geo-localization of UAVs or robots. Camera feed (also frame-by-frame) and a known small region/map, of about a mile is used to find a more exact location in the given map [7]. Sometimes a prior is given to estimate the vehicle pose [10]. However, our focus is on coarse geo-localization where the gallery spans over multiple cities.
A frame-by-frame geolocalization of videos is also possible with the proposed dataset where 2D convolutional networks are used to extract the spatial features. However, while following a frame-by-frame approach the contextual information as available from a video is ignored. Fusion of features obtained from 2D-CNN is also possible however it is more memory intensive as compared to a 3D-CNN network. Considering these limitations and challenges, we propose a videos based cross-view geo-localization.

GAMa dataset
The proposed GAMa (Ground-video to Aerial-image Matching) dataset comprises of select videos from BDD100k [32] and aerial images from apple maps.
Ground video selection: Most of the videos in BDD100k dataset are 40 sec long and usually have GPS label every second. The selection of videos from dataset was based on the range of latitude and longitude for a given video where we use a range parameter µ. We label the GPS points at n th second as X n (lat n , long n ), where the corresponding latitude is lat n and longitude is long n ( Figure 1R, Aerial image). Thus, for the whole video we have GPS points as X 1 (lat 1 , long 1 ), X 2 (lat 2 , long 2 ),.., X n (lat n , long n ). If max latitude = lat k and min latitude = lat l , then Latitude range = lat k -lat l . Also, if max longitude = long p and min longitude = long q , then Longitude range = long p -long q . Range, µ = max(Latitude range, Longitude range) In order to eliminate stationary and very fast videos, we select videos with µ from 0.001 to 0.004. Figure 1R. shows the distribution of training videos with range, µ. The distribution was similar for training and test sets. This selection left us with 46596 training and 6728 testing videos which were further screened based on the availability of GPS labels.
Aerial images: For the selected videos, aerial images are downloaded as tiles from Apple maps at 19x zoom [1]. The dataset comprises of one large aerial image (1792x1792) corresponding to each video of around 40 sec. and 49 uncentered small aerial images (256x256) for these large aerial regions. Table 1 summarizes the dataset statistics. Since, most of the videos have a GPS label every second we divide the videos into smaller clips of 1 sec. each and for each clip we have an aerial tile.
In Figure 1, we see an example of a large aerial region, along with the video frames at each second.
Aerial image centering: In Figure 2(L)a, we show an example of a large aerial image. We have a centered (CN) and an uncentered (UCN) set of small aerial images, Table 1. UCN aerial images are obtained by dividing the large aerial image into smaller tiles. The GPS label in these UCN smaller aerial images can be anywhere besides the center, Figure 2(L)b. There are three labels in the figure and for each of these GPS points the same tile will be considered as the ground truth. For making a centered (CN) set, as shown in Figure 2(L)c we take a crop centered around the corresponding GPS point however it has lead to overlap among the aerial images since in some videos we have a distribution where GPS points are nearby. In the dataset, we still have a one on one correspondence among aerial images and short ground clips. The overlap among the aerial images however increases the difficulty level for top-1 retrieval thus we evaluate with distance threshold. The dataset covers multiple cities, and the ground videos are distributed all over the US and also from middle eastern region. However, most of the videos are from four US cities; New York, Berkeley, San Francsico, and Bay area. They show different weather conditions, including sunny, overcast, and rainy, as well as different times of the day including day and night.
There is occlusion in videos and shadows of the skyscrapers in aerial images. Limited FOV in videos and all stated characteristics bring it closer to a realistic scenario however also makes it a difficult dataset for geolocalization. In Table 2, we show a comparison with existing datasets for cross-view geolocalization.

Method
An overview of the proposed approach which works on clip and video level is show in Figure 2R. Ground-video to Aerial-image Matching Network (GAMa-Net) learns features for ground view clips and aerial images; and bring the matching pair closer in the feature space by applying a contrastive loss. This provides a clip-level geolocalization for a long video. In addition, we propose an hierarchical approach, where we do video-level geolocalization and use it to update the gallery of aerial images by selecting top matched large aerial regions ( Figure 2R). The reduced gallery helps improve the clip-level geolocalization by screening out some of the visually similar however incorrect aerial images.

GAMa-Net: Clip-level Geo-localization
The proposed network takes as input a short clip from a ground video and matches it with corresponding aerial image. An overview of the proposed network is shown in Figure 3.
Visual encoders In GAMa-Net, we have a video encoder i.e. Ground Video Encoder (GVE) to get features from ground video frames and an image encoder for aerial image features i.e. Aerial Image Encoder (AIE). GVE uses 3D-ResNet18 as backbone and a two layer transformer encoder. Given a ground video C, GVE provides features for a 8 frame clip C i at the i th second of the video. There is a skip-rate of one frame so we are covering around half a second in the clip, C i . AIE on the other hand uses 2D-ResNet18 as the backbone. It takes the corresponding aerial image, A i as the input and learns the features to match with that of the ground video.
Transformer encoding: In the ground video all the visual features are not of equal importance for matching with the aerial view. This is true for aerial images as well and few features are more important when matching with ground videos. For example, the top of a building as seen from aerial images is not visible from a ground video and hence cannot be used to match the pair. To address this, we experimented with multi-headed self attention. We input the features obtained from convolutional networks to a transformer encoder framework which comprises of 4 heads and 2 layers, and uses positional encoding. A small neural network i.e. projection head is used to map the representations to the space where contrastive loss is applied. We use a MLP with one hidden layer to obtain the ground video and aerial image feature vectors e c i and e a i , respectively.
Image-video contrastive loss: We utilize contrastive loss formulation, base on NT-Xent [4,14,23], to train our network. For a given ground video the corresponding aerial image is considered a positive sample and rest of the samples are considered as negatives. This is a image-video contrastive loss applied on features from two different visual modalities i.e. ground videos and aerial images. In the loss formulation, the focus is on reducing the distance between the positive pair. We have a total of 2(N ) data points in any mini-batch with N examples. The image-video contrastive loss for a pair of positive examples is defined as, where e c i and e a i is a positive pair, e c i and (e c k or e a k ) are negative pairs, parameter, sim is the cosine similarity between a pair of features. The final loss is computed for all the positive pairs, both (e c , e a ) and (e a , e c ).

Hierarchical approach
In this approach, we introduce video-level geolocalization which also helps in reducing the search space for GAMa-Net ( Figure 2R). The clips of a given video are temporally related and provide contextual information to help improve the geolocalization. Similarly, while looking at this problem from aerial image view point, the sequence of aerial images corresponding to clips from a given video are also related geographically and some of the correct prediction at clip-level can be used to update the gallery. Using a smaller gallery also reduces the possibility of error in feature matching. Approach: We have four steps in this approach. In Step-1, we use GAMa-Net which takes one clip (0.5 sec) at a time and matches with an aerial image. Using multiple clips of a video, we get a sequence of aerial images for the whole video, i.e. around 40 small aerial images. In Step-2, we use these predictions of aerial images and match them to the corresponding larger aerial region. We use a screening network to match the features however the features are from the same view i.e aerial view. In Step-3, we use the predictions to reduce the gallery by only keeping top ranked large aerial regions corresponding to a video. These large aerial regions define our new gallery for a given video. In Step-4, we use GAMa-Net i.e. the same network as in Step-1, however geo-localize using the updated gallery.
Visually correct predictions from Step-1 which may not be the ground truth are used to reduce the gallery using this approach. This approach helps improve the clip-level geolocalization since the reduction of the gallery is based on the fact that all the clips of a given video are geolocated nearby. Thus, the aerial images predicted by GAMa-Net can be used to find that large aerial region where all these clips have been captured. In this case, the probability of finding all those visually correct aerial images in the same region is higher when we are searching at the correct geolocation. Hence, it is likely to match with correct large aerial region provided that meaningful and enough information is available.
Screening Network: Video-level geo-localization We use the screening network to match a sequence of smaller aerial images with the corresponding larger aerial region. The network is similar to GAMa-Net, however the sequence of aerial images is input to Small Aerial Encoder (SAE) with 2D-ResNet18 backbone and the sequence of features are later averaged to  Figure 4L). We also experimented with a 3D-ResNet18 backbone which is discussed later. The feature vector thus obtained is matched with the feature vector of corresponding large aerial image from Large Aerial Encoder (LAE). We apply contrastive loss similar to Equation 1. The predictions from this network are used to update the gallery for GAMa-Net.

Experiments and Results
Implementation and training details: We implement our GAMa-Net and screening network using PyTorch [14] and train using Adam optimizer with a learning rate (lr) of 8e-5. We use a lr scheduler with lr decay rate of 0.1. The screening network is trained in two step; first with the actual ground truth sequences, and then finetuned with predictions from GAMa-Net. The finetuning step allows the network to adapt to noisy aerial sequences which will be used during inference. We use pre-trained weights from Kinetics-400 for 3D-ResNet18 and ImageNet weights for 2D-ResNet18. The ground videos in the proposed dataset are from different times of the day, for faster training we have used only day videos in our experiments unless stated otherwise.
Evaluation: We use top-k recall for clip-level and video-level matching at different values of k. Given a video query, its closest k reference neighbors in the feature space are retrieved as predictions. Similar to image based geolocalization methods we use recall rates at top-1, top-5, top-10, and top 1%. More details can be found in [28,8,21]. We have UCN and CN sets of aerial images corresponding to each clip. In UCN set there is one-to-one correspondence between the clip and aerial image. The GPS point can be anywhere within the aerial image however in the CN set there is an overlap among the aerial images. To keep the evaluation similar to UCN set it is considered a correct match if the predicted GPS is within the range of 0.05 mile of the correct location. We also report top-1@t rate where t is a distance threshold to be used for correct prediction.
Baselines: We propose several baselines for comparison. For ground image based baselines we use the center frame of the clip as an input. Image-CBn, our proposed baseline uses 2D-CNN ResNet18 model to encode the ground video frame with similar contrastive loss formulation as GAMa-Net. We use two different loss functions for video based baselines (Triplet-Bn and CBn); margin triplet loss [27] and contrastive loss [4]. In these baselines, we utilize 2D-CNN ResNet18 for aerial images and 3D-CNN ResNet18 for ground videos.

Results
The evaluations of GAMa-Net and a comparison with baselines is shown in Table  3. We observe a Top-1 recall rate of 18.3% and 15.2%, using GAMa-Net with and without the hierarchical approach, respectively. On UCN set, we observe poor performance as compared to CN set which was expected.
Comparison: In the first row, we show results with our image-based baselines which uses a single frame from the ground video. We also compare with other image based methods using a single frame as input and observe that the proposed approach outperforms all these baselines. While training with a single image is faster we do not have the temporal information which in this case can be perceived as relative positioning or contextual information. As the camera moves along a path or trajectory we can see the buildings or objects pass-by giving an idea of their respective location. The information of distance/relativepositioning as seen by a 3D-CNN is the additional information when we train with videos. As shown in the Table 3, using a video provides better results as compared to images.
Few studies have reported better performance with contrastive loss [15], however triplet loss is also frequently used for geolocalization [35,17]. We also observe better performance with contrastive loss as compared to the triplet loss (Table  3). In GAMa-Net, we have features from two different visual modalities i.e. one from ground videos and other from aerial images, which is different from the traditional contrastive loss. Similarly, training with triplet loss also use imagevideo features. These differences are likely responsible for poor training with triplet loss.
Qualitative analysis: Figure 5 show sample Top-5 predictions with different models where the leftmost is Top-1 and the rightmost is 5th. The combined  model makes visually meaningful predictions. In the leftmost example, the camera is passing under a fly-over and the predictions show a similar locations. The middle example is of a road without any crossings or red lights in sight, and rightmost example is of a city street with crossing markings on road. The predictions by combined model match these specifications. However, in these samples, the ground truth is in top-1% but not in top-5 images. The predictions by GAMa-Net, with multi-headed self-attention improves the network performance and correct prediction moves up in the top-5 (More results in supplementary).
Hierarchical approach The predictions from the screening network are used for video-level geo-localization and to reduce the gallery for GAMa-Net. We experimented with both 2D-CNN and 3D-CNN backbone for aerial image sequence. As shown in Table 4, better results were achieved with 2D-CNN backbone likely due to better spatial features. A comparison of number of input aerial images show that 2D-CNN with 8 frames retains more ground truths at Top-1 (12.2%), Top-10 (35.3%) and Top-1% (49.3%). We do not have 32 samples in some of the samples which likely effects the performance. However, when we evaluated GAMa-Net after gallery reduction, Screening network i.e. 2D-CNN network with 32 aerial images provided the best results. Figure 4R shows qualitative results for video-level geo-localizaion. It shows one frame of the video input to GAMa-Net, the predicted seq of aerial images thus obtained was used to identify the larger aerial regions. The bottom row shows the correct matched large aerial regions for video-level geo-localization. More results are in supplementary. Gallery sizes: In Table 5, we discuss the results with GAMa-Net using various gallery sizes, i.e. Top-10, Top-1%, and Top-10% of large aerial regions, identified using screening network. We see better Top-1 results with Top-1% gallery as compared to Top-10 and Top-10%. There is a trade-off between reduced search space which improves matching and retaining the ground truth. As observed from Table 4, in Top-10 we have ground truth for only 20.9% of videos which increases to 83.8% at 10% gallery. However, this percentage will be different if we consider clips since we get different number of clips from each video, as per GPS labels. We evaluated GAMa-Net, which is clip level, using a reduced gallery. Even when ground truth was not available for many samples we see a Top-10 recall rate of 25.5%. When gallery is reduced to Top-10 and Top-1% of larger aerial regions we do not have enough clips to make upto 1% of the total gallery. In Figure 5, we show three examples of aerial image matching and it is evident that predictions by GAMa-Net are improved with hierarchical approach.

Ablations
Combined model: In Table 6, we observe better performance with combined model as compared to baselines, and a Top-1% recall of 92.4%. As expected, the performance improves as we increase the distance threshold. In the combined model, we have various augmentations which includes spatial and temporal centering, and random crop. Since images are not aligned in GAMa we stochastically rotate the aerial view (0, 90, 180, 270 deg) for view-point invariance. All these augmentations have been reported to help improve geo-localization. We also include hard negatives for better training however transformer encoder is not a part of combined model.
Transformer encoder: Similar to an aerial image, not all visual features in the ground video have the same importance for cross-view geolocalization. Thus, we implemented transformer encoder on ground video(Video-Tx) and aerial images(Aerial-Tx), individually. In both cases, we observe an increase in recall @Top-1. The performance is better with GAMa-Net(i.e. Aerial-Tx) and we observe 15.2% Top-1 recall which is higher than 14.1% with Video-Tx (Table  6). Observing an improvement in both cases we used transformer encoder on both sides(Dual-Tx) however it did not perform better than the GAMa-Net.
Hierarchical approach: We use hierarchical approach to improve the performance of GAMa-Net by reducing the gallery. Top-1@threshold (Table 6) shows that using the hierarchical approach makes the matching more effective by predicting the aerial images closer to the correct GPS location or ground truth. The difference in Top-1 recall, with and without hierarchical approach, is even higher at higher thresholds i.e 7.5% at 1.0 mile vs 3.9% at 0.1 mile. An increase in recall to 43.6% at 1.0 mile threshold shows that the ground truth is not very far from the Top-1.

Discussion
Videos and contextual information: In videos, we have more information which can be considered as contextual information from geo-localization point of view. It enables the network to locate a given frame or view with respect to the other frames in the video. One frame may contain features to complement another and together they are likely to provide more or complete information required for geo-locating. In Table 3, we have compared video based method with frame based baselines. Better recall rate with videos show that the network is able to utilize the additional information available with videos.
Centered vs Uncentered: In an UNC aerial image the corresponding GPS point can be anywhere in the tile. In cases where the GPS point is near the boundary, the visual information from the video is less likely to match the corresponding tile. As expected, after centering (CBn-CN) we observed an improvement in the recall rate as compared with the uncentered set (i.e. CBn-UCN).
Full Dataset: GAMa dataset is a large dataset which has its pros and cons. With large amount of data networks are better trained however this also  [31]. Most of the cross-view geolocalization datasets such as CVUSA report high R@k while using ground panorama and aligned aerial images which is unrealistic since a normal camera lens has a FOV of around 72% and it is not possible to get aligned images always. In GAMa dataset, the aerial images and ground videos are unaligned, and ground videos have a limited FOV which makes it a more realistic and difficult dataset.
Challenges: In GAMa dataset among the two sets of small aerial images, i.e. CN and UCN, the UCN set is more realistic however difficult for geolocalization. Unaligned aerial images increase this difficulty however, the orientation information can be extracted from the GPS information and is likely to improve the performance [13]. Also, the ground videos have varying lengths and in some of the cases GPS label is not available every second. Thus, the video length available for geolocalization is less than 40 sec. Additionally, there is occlusion because of the car hood and other objects. Such cases are more likely to appear in fail cases.
Limitations: The proposed hierarchical approach performs better with longer videos (8 sec. or more), however it can be used with shorter clips as well. The aim behind using a hierarchical approach is to filter out confusing samples to improve the retrieval rate. However, this sometimes leads to filtering of the ground truth from the gallery. The model is also likely to fail with indoor videos since it will not be possible to match the features with an aerial image. However, this limitation is common to all cross-view geo-localization methods.

Conclusions
In this work, we focus on the problem of video geolocalization via cross-view matching. We propose a new dataset for this problem which has more than 51K ground videos and 1.9 million satellite images. The dataset spans multiple cities and is a more realistic dataset, unaligned and limited FOV. We believe that this dataset will be useful for future research in cross-view video geo-localization. Our proposed GAMa-Net effectively makes use of the rich contextual information available with video. In addition, we propose a hierarchical approach which also utilize the contextual information to further improve the geo-localization.

A Overview
In this supplementary, we have included additional qualitative results. In Section B, we show and discuss some qualitative results for video-level geolocalization. In Section C, we have included additional qualitative results for clip-level geolocalization and ablations. Step-1 0.5 sec clips from the video are input to GAMa-Net. It takes one clip at a time and matches it with an aerial image. In Step-2, the sequence of aerial images obtained from GAMa-Net is input to the Screening network to retrieve the corresponding larger aerial region. This is our video-level geo-localization. In Step-3, top predictions of these larger aerial regions provides the updated gallery for a video.
Step-4, is prediction by GAMa-Net while using the updated gallery An outline of the proposed approach in Figure 6 shows how video level geo-localization is used to improve the clip-level results. The GAMa-Net outputs aerial image predictions at clip-level using the full gallery i.e. G f . A video comprises of a number of clips (upto 40 clips per video), thus a sequence of aerial images is obtained from each query video, this sequence is then input to the screening network. The screening network uses this sequence of small aerial images to predict a large aerial region corresponding to the query video. Then we select Top-1% large aerial images to update the gallery (the updated gallery G up ) for GAMa-Net and reduce the search space. We are hopeful that with further research this approach has the potential to be generalized to even larger scale. As shown in main paper we observe an improvement in Top-1 recall using this approach. The screening of the locations at large region level removed the confusing samples.

B Qualitative Results: Video-level Geo-localization
In Figure 7, we show some of the predictions of larger aerial regions as ranked by the screening network. For each sample, the first row shows frames of the video spanning over 35 sec. of time duration. In the subsequent row, we have the ground truth larger aerial region which is followed by Top-5 predictions by the screening network. The examples shown here are mostly correct predictions where Top-1 is same as the ground truth.
In the first sample (Figure 7), we see that the video frames are partially outdoors and partially indoors. Indoor setting appears to be a parking lot or an underpass. The screening network is able to correctly localize the larger aerial region while using the information available from all the clips. The prediction when used to reduce the gallery of GAMa-Net is likely to enable a better prediction by screening-out the far away regions. Frame-by-frame it would have been difficult to localize the indoor frames. However, using the hierarchical approach the network is able to use the context from outdoor frames. We also observed this from the predictions, with GAMa-Net only 12 clips out of the 38 clips had ground truth prediction in top-10 and after reducing the gallery using the prediction from screening network this number increased to 28 clips. In the second sample (Figure 7), we can see that all Top-5 predictions are visually similar. These predictions appears to be from the same region and most are from around a mile radius of the ground truth larger aerial region.
In the third sample, because of a car, there is occlusion in part of the video. GAMa-Net correctly localizes the initial clips however fails in the clips with occlusion. After screening the gallery using the correct larger aerial prediction, most of these clips were correctly geolocalized by GAMa-Net in Top-1, Top-5 or Top-10. Similarly, in fourth and fifth sample the occlusion is in all the frames either because of the car hood or rear view mirror. In the fourth sample, similar improvement in clip-level geolocalization was observed with GAMa-Net because of correct screening of the larger aerial region at the video-level. We see correct video-level Top-1 with fifth sample, however the improvement in the clip-level predictions by GAMa-Net was less and only 3-4 more clips had predictions added to top-10 as compared to retrieval from the full gallery. The second top prediction of this sample is visually similar to the ground truth however a closer look shows that it is a different image. In the last or sixth sample we can see that multiple correct predictions because of the visual similarity are in Top-5.
With all these video samples, because of some of the correct clip-level predictions by GAMa-Net, the screening network is able to localize at video-level and identify the correct larger aerial region. However, the last sample had correct clip-level prediction for a single clip out of 31. It is likely that the visual similarity of the incorrect aerial image predictions helped with correct video-level geolocalization at Top-1 using screening network. Fig. 7. Here, we show results for video-level geo-localization using the Screening network. In each sample, we show seven frames of the query video, followed by the ground truth aerial image and top-5 predictions of larger aerial regions.

C Additional Qualitative Results: Clip-level
Geo-localization In Figure 8 and Figure 9, we show additional results using the proposed GAMa-Net with Hierarchical approach, where we use the video-level predictions to improve clip-level geo-localization. Figure 8 shows examples of correct Top-1 predictions. We can see that most of the Top-5 predictions are nearby the ground truth. Because of the nearby GPS labels in video clips we have overlapping in aerial images and all these images appear in the Top-5 predictions along with the ground truth. Figure 9 shows examples of fail cases, we can see that most of the fails are due to shadows or occlusion or poor quality of aerial images. The model makes meaningful predictions however fails in difficult or confusing samples e.g. in the last sample traffic lights are visible in the video and predictions are with zebra crossings however does not retrieve the correct aerial image in Top-5.
In Figure 12 and Figure 13, we show some additional results with the combined model which does clip-level geolocalization by retrieving a matching aerial image. The network however is an ablation of the proposed GAMa-Net and does not have a transformer encoder. Fig. 8. Here we show sample success cases with GAMa-Net using Hierarchical approach where Top-1 prediction is correct. In each sample, four frames of the query clips are followed by ground truth aerial image and Top-5 predictions Fig. 9. Here we show sample fail cases with GAMa-Net using Hierarchical approach where Top-1 prediction is correct. In each sample, four frames of the query clips are followed by ground truth aerial image and Top-5 predictions Here we show success cases using GAMa-Net without Hierarchical approach where top-1 prediction is correct. In each sample, four frames of the query clips are followed by the ground truth aerial image and Top-5 predictions Fig. 11. Here we show fail cases using GAMa-Net without Hierarchical approach. In each sample, four frames of the query clips are followed by the ground truth aerial image and top-5 predictions


SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm

Graph matching finds the correspondence of nodes across two correlated graphs and lies at the core of many applications. When graph side information is not available, the node correspondence is estimated on the sole basis of network topologies. In this paper, we propose a novel criterion to measure the graph matching accuracy, structural inconsistency (SI), which is defined based on the network topological structure. Specifically, SI incorporates the heat diffusion wavelet to accommodate the multi-hop structure of the graphs. Based on SI, we propose a Structural Inconsistency reducing Graph Matching Algorithm (SIGMA), which improves the alignment scores of node pairs that have low SI values in each iteration. Under suitable assumptions, SIGMA can reduce SI values of true counterparts. Furthermore, we demonstrate that SIGMA can be derived by using a mirror descent method to solve the Gromov-Wasserstein distance with a novel K-hop-structure-based matching costs. Extensive experiments show that our method outperforms state-of-the-art methods.

Introduction
Graph matching (network alignment) aims to identify the correspondence of nodes across two related graphs, by minimizing the sum of pair-wise matching costs of corresponding nodes/edges. It has many applications, such as linking user accounts in social platforms [Shu et al., 2017, Wang et al., 2019b, aligning entities in knowledge graphs [Sun et al., 2020, Pei et al., 2020, and matching keypoints across two images [Sarlin et al., 2020, Wang et al., 2020a, to name a few.
The choice of matching costs is critical to the performance of graph matching. When node/edge side information, e.g. attributes, is available, one can rely on expert knowledge to design handcrafted node embeddings for the construction of matching costs Tong, 2016, Meng et al., 2016]. Recently, to alleviate the requirement of expert knowledge, end-to-end deep learning methods are proposed to learn the node embedding automatically based on the anchor links (labelled node correspondences) [Zanfir and Sminchisescu, 2018, Fey et al., 2019, Wang et al., 2019a, Sarlin et al., 2020, Wang et al., 2020b. However, in many tasks, side information may not be available Krevl, 2014, Heimann et al., 2021]. Under such circumstance, the matching costs can merely be estimated on the basis of the network topologies of the two graphs [Patro and Kingsford, 2012, Saraph and Milenković, 2014, Sun et al., 2015, Mémoli, 2011, Maretic et al., 2019, Xu et al., 2019b, Heimann et al., 2021.
Among these network-topology based methods, one line of works align graphs by borrowing tools from optimal transport (OT) and achieve the state-of-the-art performance [Mémoli, 2011, Maretic et al., 2019, Xu et al., 2019b, Titouan et al., 2019, Chowdhury and Mémoli, 2019, Barbe et al., 2020. Basically, these methods utilize OT to exploit the geometric properties of the metric spaces that underlie the graphs, and estimate the node correspondence by calculating the transport plan of the Gromov-Wasserstein distance. Typically, the matching costs in these methods are calculated depending on the one-hop neighborhood information of each node.
Recently, Heimann et al. [2021] reveals the connection between the graph matching accuracy and the matched neighborhood consistency (MNC), i.e., the Jaccard simliarity between the one-hop neighborhoods of matched node pairs. In particular, they show that accurate matching essentially entails high MNC. However, it remains unknown how the OT-based methods are related to MNC theoretically. Instead, they propose a method, RefiNA, by maximizing the numerators of MNC, which can be regarded as an opposite measure of the matching cost. Though the authors intend to find matching with high MNC, RefiNA actually diverges from their purpose, as the denominator of MNC is ignored and a high numerator does not ensure a high MNC. Moreover, both OT-based methods and RefiNA may suffer from one-hop structural indistinguishability and tend to misalign nodes that have low degrees, as they discard the abundant network topological information and estimate the graph matching merely depending on the one-hop neighborhoods structure.
In this paper, we propose a novel criterion to measure the graph matching accuracy, structural inconsistency (SI), which utilizes the abundant network topological information. Specifically, SI incorporates the heat diffusion wavelet [Donnat et al., 2018] to accommodate the multi-hop structure of the graphs. If a pair of nodes incurs zero SI, they are K-hop indistinguishable. On the other hand, SI values of true counterparts should be zero for two isomorphic graphs. In practice, the SI between a true corresponding pairs may only close to 0 due to the structural noise.
Based on SI, we propose a Structural Inconsistency reducing Graph Matching Algorithm (SIGMA), which improves the alignment scores of node pairs that have low SI values in each iteration. Under suitable assumptions, SIGMA can reduce SI values of true counterparts. As SI considers the multi-hop topological information, SIGMA can avoid the misguidance of one-hop structural indistinguishability and find graph matching of higher accuracy. Besides, we also show that our method increases a soft version of MNC values, which is positively related to MNC and should also be high/low for accurate/inaccurate matching. Furthermore, we demonstrate that SIGMA can be derived by using a mirror descent method to solve the Gromov-Wasserstein distance with a novel K-hop-structure-based matching costs. As a result, SIGMA can be regarded as the first OT-based method that are guaranteed to increase MNC in each iteration in the graph matching literature.
Extensive experimental results demonstrate that the proposed method outperforms state-of-the-art methods. The rest of the paper is organized as follows. In Sec. 2, we review the background and discuss the relationship between SI and matching accuracy. Based on SI, a new graph matching method SIGMA is proposed in Sec. 4. We give theoretical analysis in Sec. 5. Due to the limited space, all proof are given in the appendix. Experimental results are demonstrated in Sec. 6 and the appendix.

Preliminary
In this section, we give basic preliminary to facilitate the later discussion and review the main background.
Here, we first give the notations used in the main text. We use bold lowercase symbols, bold uppercase letters, and uppercase calligraphic fonts to denote vectors (e.g. x), matrices (e.g. A), and sets (e.g. A), respectively. (·) is the transpose of a vector or a matrix. A[i, :] and A [:, j] are the i-th row and the j-th column of matrix A respectively. For two matrices A and B that are of the same size, A, B = trace(A B) is the Frobenius dot-product. We denote the cardinality of set A by |A|.

Graph Matching
We consider undirected graphs without self-loops G = (V, E, W), where V is the set of vertices, E is the set of edges, and W = [W ij ] ∈ R |V|×|V| is a (binary or weighted) adjacency matrix. If there is an edge (i, j) connecting vertices i and j, i.e., (i, j) ∈ E, the entry W ij represents the weight of the edge; Otherwise, W ij = 0. The degree of each vertex i, written as d i , is defined as the sum of the weights of all the edges incident to it, i.e., d i = |V| j=1 W ij . The degree matrix D = [D ij ] has diagonal elements equal to the degrees D ii = d i , and zeros elsewhere. The Laplacian matrix of G is defined as L = D − W. The k-hop neighborhood of node i, denoted by N k (i), is the subgraph of G induced by all nodes that are k or fewer hops away from node i.
Given the source graph G s = (V s , E s , W s ) and the target graph G t = (V t , E t , W t ), assuming |V s |≤ |V t | without loss of generality graph matching aims to find an injective mapping π : V s → V t that matches nodes in G s to nodes in G t . In this paper, we focus on equal-size graph matching, i.e., V = |V s |= |V t |. In such case, π is restricted to be a bijective. For graphs with different number of nodes, one can add dummy isolated nodes into the smaller graph and make them equal-sized [Gold and Rangarajan, 1996, Zaslavskiy et al., 2008, Jiang et al., 2017. π is also commonly represented as a matching matrix [Fey et al., 2019, Heimann et al., 2021), where

Optimal Transport
Given two discrete measures α = m i=1 p i δ xi (x) and β = n j=1 q j δ yj (y), Optimal transport (OT) addresses the problem of optimally transporting Villani, 2008]. The p-Wasserstein distance between p and q is defined as where K ij is the distance between x i and y j , K p = [K p ij ] ∈ R m×n + and the feasible domain of transport plan T is given by the set of coupling measures Π(p, q) = {T ∈ R m×n + |T1 n = p, T 1 m = q}. Gromov-Wasserstein (GW) distance is a generalization of Wasserstein distance [Mémoli, 2011]. Let X and Y be two sample spaces. Endowing the spaces X and Y with metrics (distances) d X and d Y , the GW distance is defined as . , x m ∈ X and y 1 , . . . , y n ∈ Y.
Optimal transport can be applied to graph matching. The source graph G s and the target graph G t are modelled as two probability distributions µ s = [µ s i ] and µ t = [µ t i ] respectively, where A dissimilarity matrix B s can be assigned to G s to encode the structural information. Each entry B s ij models the distance between nodes i and j in G s , such as the edge weight-based distance [Xu et al., 2019b], the shortest path distance, or the harmonic distance [Verma and Zhang, 2017]. B t is defined similarly. Basically, the node correspondence is estimated by calculating the transport plan of the Gromov-Wasserstein distance that is defined as Node i ∈ V s is matched toî ∈ V t , whereî = argmax i T * ii and T * attains the minimum of Eq. (2).
Note that to better approximate matching matrices (1), one can relax the The matching matrix can then be interpreted as a transport plan from 1 to 1.

Heat Diffusion Wavelet
For each graph z = s, t, the heat diffusion on a graph is the solution to the discrete heat equation known as the Laplacian exponential diffusion kernel [Hammond et al., 2013]. As t approaches zero, high-order terms vanish, meaning that the kernel depicts local connectivity [Tsitsulin et al., 2018, Donnat et al., 2018. The K-th order approximation of exp(−tL z ) is The i-th row, Ψ[i, :], is the K-th order HDW for node i [Donnat et al., 2018] and measures the network connectivity between node i and each node j. B z = [B z ij ] that characterizes node dissimilarities within each graph is defined as where Ψ z ij is defined as Eq. (3), z = s, t and constantΨ > max i,j,z Ψ z ij .

Structural Inconsistency
Based on the local neighborhoods of node i and node i , they can be embedded into a V -dimensional space, which yields embedding vectors z i and z i respectively. The j-th dimension of z i (resp. j -th dimension of z i ) models the distance between i and j (resp. i and j ). In this paper, we instantiate the embeddings based on HDW, i.e., Given transport plan T ∈ Π(1, 1), we model the structural inconsistency (SI) of a pair of nodes (i, i ) ∈ V s × V t as a transport distance   Figure 1a and thus structural inconsistency occurs.
We illustrate SI(A, a) when K = 1 in Figure 1. Here the transport plans are depicted by the thin dashed lines and we omit them in SI. In Figure 1a, node B (resp. C) is wrongly matched to node c (resp. b). Nodes A and B (a and b) are connected by an edge while no edge connects a and c(A and C), which is depicted by the two red(yellow) circles. Therefore, structural inconsistency incurs. In Figure  1b, node A and its one-hop neighbors are correctly matched, which leads to SI(A, a) = 0.
One can derive a SI matrix. The SI for all node pairs (i, i ) given the matching matrix T, can be written where h denotes the element-wise square and ⊗ is the outer product of two vectors. We further define the structural inconsistency of true counterparts (CSI) as CSI(i; T) = SI(i, π * (i); T), where π * is the true matching. SI is closely related to alignment accuracy. On the one hand, if node pair (i,î) have zero SI values,î either is the true counterpart π * (i) or have the same local topology as π * (i), which is formalized in the following theorem.
Theorem 1 Assume G s and G t are isomorphic and there exists T that yields SI(i,î; T) = 0. Then, ifî = π * (i), N t k (î) and N t k (π * (i)) are isomorphic for all k ≤ K.
An example of Theorem 1 is matching two star graphs, each consisting of one center node connected to n − 1 peripheral nodes [Heimann et al., 2021]. Matching peripheral nodes to each other in any order leads to zero SI's, whatever the true correspondence of the peripheral nodes is. This inspires us to use larger neighborhoods to improve the performance, since N t k+1 (î) and N t k+1 (π * (i)) may not be isomorphic when N t k (î) and N t k (π * (i)) are. On the other hand, if G s is isomorphic to G t up to a few noisy or missing edges (the vetex sets remain the same), CSI (i; T * ) values are low where T * = [T * ii ] is matrix form of true matching. This is stated in the following theorem.
Theorem 2 Let ∆ k ∈ R V ×V denote the perturbation to the edge structure, which is given by ∆ k = (L s ) k − (L t ) k whereL t = T * L t T * is the Laplacian matrix of the registered target graph. Assume that for all i, the perturbation to the local neighborhood is bounded as k = max i j∈N s Then CSI (i; T * ) can be bounded from above as follows: where t is the propagation time.
Note that the propagation time t is often set to a small value in order to capture the local topology [Tsitsulin et al., 2018, Donnat et al., 2018. Thus, for a fixed K, when the perturbation k is small, CSI(i; T * ) has a small upper bound and even is close enough to 0. It is reasonable to conjecture that keeping decreasing CSI will lead to an optimal result, which is embodied in our method design.

Methodology
We update the matching matrix based on the SI matrix. The high level intuition is that each iteration decreases alignment scores for node pairs that have relatively high SI values. The recurrence of SIGMA reads where τ = 0, 1, . . . , is the element-wise multiplication and the exponentiation is also element-wise. The projection can be solved via Sinkhorn-Knopp algorithm with linear convergence rate [Sinkhorn and Knopp, 1967]. Actually, iteration (7) is the mirror descent update for calculating the GW distance. To solve problem the most common algorithm is gradient descent that iteratively updates T as follows where the gradient reads Mirror descent takes into account the geometry of the feasible domain [Bubeck et al., 2015], and is better-suited to Problem (8). Mirror descent is given by the recurrence where D ψ (T, T (τ ) ) stands for the Bregman divergence. When one selects the generalized KL-divergence KL(A|B) = ij A ij log Aij Bij − A ij + B ij as the Bregman divergence, (11) becomes iteration (7).
Algorithm 1 SIGMA 1: Input: Total rounds T , graphs G s and G t , initial transport plan T (0) . 2: Output: Correspondence set C. Update T (τ +1) by iteration 7. 6: end for 7:T = T (T ) 8: Initialize correspondence set C = ∅ 9: for i ∈ V s do 10: SIGMA is summarized in Algorithm 1. The matching cost is based on heat diffusion wavelets. It updates the matching matrix using (7). By choosing the largest index fromT[i, :] for each i, we find the correspondence.

Theoretical Analysis
In this section, we first prove that iteration (7) can reduce CSI(i; T) for all i under suitable assumptions. Then the convergence of SIGMA is proved. We also discuss its relationship to state-of-the-art methods.
With appropriate η (τ ) , iteration 7 can reduce alignment score T ii if SI(i, i ; T (τ ) ) is high, which is formalized in the following lemma.
We now state our main theorem.

Combining Lemma 3 and Theorem 4, if we have
) for all i and i =î, we can reduce CSI(i; T) at iteration τ .
By establishing the relationship between SIGMA and optimal transport based methods, we can borrow the convergence result of mirror descent and prove that SIGMA converges as follows.
Theorem 5 SIGMA converges to an -stationary point with the number of mirror descent iterations O( 1 2 ). The main steps of the proof follow Zhang and He [2018]. We further remark that the true matching matrix T * is a fixed point of update (7).
Computational complexity. The complexity for calculaing the heat diffusion wavlets is O(KV 3 ). Due to the two matrix multiplication steps of the term B s TB t , calculating the gradient involves computational complexity O(V 3 ). Note that the matrix multiplication is highly parallelizable and well-suited to modern computing architectures like GPUs. O(V 2 ) cost is induced by the matrix-vector multiplication in the projection operation. Therefore, if we run projected mirror descent for N iterations, each of which involves T matrix-vector multiplications in the projection, O(N T V 2 + (N + K)V 3 ) computational cost is required in learning the matching matrix. Such complexity is of the same order as state-of-the-art methods like Xu et al. [2019b], Konar

Connection to GWL Xu et al. [2019b]
The gradient that arises from Problem (2) [Xu et al., 2019b,a, Titouan et al., 2019, Barbe et al., 2020 and has the following form: where h denotes the element-wise square and ⊗ is the outer product of two vectors [Peyré et al., 2016]. Note that if we set µ z i = 1 for all i and z = s, t, (12) is identical to (10).
GWL uses proximal point method to solve Problem (2) [Xu et al., 2019b]. If one single mirror descent step is adopted to solve the sub-problem and the marginals are set as µ z i = 1, the proximal point method is identical to our mirror descent method.

Connection to RefiNA Heimann et al. [2021]
When K = 1, the pairwise SI has a more intuitive interpretation.
Proposition 6 When one only uses one-hop neighborhood information (i.e., K = 1), is the set of nodes onto which π maps i's neighborsÑ s k (i; π) = {j ∈ V t |∃j ∈ N s k (i) s.t. π(j) = j }, and the bijective is given by π(i) = argmax i [T ii ].

Chen et al. 2020 and Heimann et al. 2021 define a similar quantity.
Specifically, the matched neighborhood consistency (MNC) of node i in G s and node i in G t is the Jaccard similarity of the setsÑ s 1 (i; π) and N t 1 (i ), i.e., MNC(i, i ; π) = |Ñ s 1 (i;π)∩N t 1 (i )| |Ñ s 1 (i;π)∪N t 1 (i )| . SI(i, i ; T) and MNC(i, i ; π) can be related as follows.
Proposition 7 When propagation time t = 1 andÑ s 1 (i; π)∩N t 1 (i ) is not empty, According to Proposition 7, Lemma 3 and Theorem 4, SIGMA with K = 1 and t = 1 can also be viewed as increasing a soft version of MNC values, which is positively related to MNC and should also be high/low for accurate/inaccurate matching. Combined with the description in Sec. 4, SIGMA can be regarded as the first OT-based method that are guaranteed to increase MNC in each iteration in the graph matching literature. In addition, by characterizing the structure of a larger neighborhood via HDW, we alleviate the problem of near structural indistinguishability and improves the matching performance.

Experiments
In this section, we compare SIGMA and state-of-the-art methods. Due to the limited space, additional experimental results are provided in the appendix.

Experimental Setup
Computing infrastructure. All codes are implemented in Python 3.6 and the package dependencies are listed in the requirements.txt file in the code submission. The experiments are conducted on a Ubuntu server with two CPUs (Intel Xeon (R) CPU E5-2680 v4 @ 2.40GHz), 4 Nvidia 2080 Ti graphics cards, and 378 GB of RAM.
Baselines. Our baselines are unsupervised methods including (1) RefiNA [Heimann et al., 2021] that also explicitly considers the neighborhood consistency; (2) REGAL  that obtains the node embeddings based on matrix factorization; (3) GRAMPA [Fan et al., 2020] that is proposed to match correlated Erdős-Rényi graphs and involves computing all eigenvalues and the associated eigenvectors of the adjacency matrices; (4) MM [Konar and Sidiropoulos, 2020] that formulates graph matching as maximizing a monotone supermodular set function subject to matroid intersection constraints; (5) GWL [Xu et al., 2019b] that matches graphs based on OT; (6) GDD [Scott and Mjolsness, 2021] that involves solving a three-level nested optimization problem. As is shown in their papers, RefiNA and MM are sensitive to the noise and thus take the output of CONE-Align [Chen et al., 2020] as initialization. For fair comparison, GWL and SIGMA also use the output of CONE-Align to initialize the transport plan. We implement REGAL, GWL, and GDD based on the corresponding open-sourced code.
Evaluation Metric. We report node correctness (NC) that is defined as NC = |C∩C real | |C real | , where C and C real are the learned and ground truth node correspondences respectively.

Matching Permutated Networks
Datasets. Following the literature (eg. , Konar and Sidiropoulos, 2020, Heimann et al., 2021), we match two randomly permutated graphs, that is, the target graph is obtained by permutating the nodes of the original graph (source graph). SIGMA is tested against baselines on standard benchmark datasets, including PPI Yeast [Breitkreutz et al., 2007], Arxiv [Leskovec et al., 2007], and LastFM ASIA [Rozemberczki and Sarkar, 2020]. These datasets are listed in Table 1. Similar to , Konar and Sidiropoulos [2020], Heimann et al. [2021], we also add structural noise to the target graph by adding q|E s | edges.
Results. We report the performance of SIGMA and baselines in Figure 2, in which K is set to 3. The similarity matrix in GRAMPA incurs quadruple computational complexity and takes thousands of hours to obtain on LastFM ASIA and Arxiv. GRAMPA thus does not scale and its performance is not reported on these two datasets. OT-based methods and RefiNA take into account the local topology and have good performance on all datasets. SIGMA outperforms state-of-the-art methods in all cases. The improvement becomes more significant with the noise increasing.
Runtime. In Table 2, we compare the average runtimes of all different methods across noise levels. Time used to calculate the heat diffusion wavelets in SIGMA is included. The two fastest methods per dataset are in bold. SIGMA is faster than its closest competitors in accuracy (Figure 2).

Related Work
Matching attributed graphs. Deep learning-based methods take as input the node/edge attributes of the graphs and learn node embeddings suitable for graph matching [Zanfir and Sminchisescu, 2018, Fey et al., 2019, Wang et al., 2019a, Sarlin et al., 2020, Wang et al., 2020b, Yan et al., 2020. These supervised methods, however, require a large amount of anchor links that are often not available in practice. Optimal transport-based methods exploit structural information and match graphs in an unsupervised manner [Maretic et al., 2019, Xu et al., 2019b, Chowdhury and Mémoli, 2019. To further incorporate node attributes, Fused Gromov-Wasserstein distance-based methods are proposed to exploit both node attributes and structure information [Titouan et al., 2019, Barbe et al., 2020]. Node or edge attributes can be incorporated into the design of SI.
Graph distance. Comparison among graphs is ubiquitous in analyzing graphstructured data. Spectral distances usually do not take into account all the structural information, focusing only on the Laplacian matrix eigenvectors and ignoring a large portion of the structure encoded in eigenvectors [Jovanović andStanić, 2012, Gera et al., 2018]. The cut distance [Lovász, 2012] and the graph edit distance [Bougleux et al., 2017, Raveaux, 2021 require solving difficult discrete optimization problems. Another family of graph distances that is closely related to this paper is the graph diffusion distance [Hammond et al., 2013, Tsitsulin et al., 2018, Scott and Mjolsness, 2021. Hammond et al. 2013 assume the nodes of the two graphs are already matched and calculate the graph diffusion distance. Scott and Mjolsness 2021 extend Hammond et al. [2013]'s work and address the graph matching problem. Their method involves solving a three-level optimization problem and estimates the node correspondence in the innermost problem by matching eigenvalues of the heat diffusion kernel matrix. Note that our Eq. (8) also defines a distance between two graphs.

Conclusion
In this paper, we consider the problem of matching unattributed graphs without anchor links. A novel quantity, SI, is defined to measure the correspondence quality of a pair of nodes. We reveal that SI has a close relationship to matching quality. On the one hand, if the SI value of a pair of nodes is zero, they are either true counterparts or have the same local topology. On the other hand, true matching entails low SI values of matched node pairs. Based on SI, we propose a graph matching method named SIGMA which can reduce low SI values under suitable assumptions. Empirical results demonstrate the good performance of our method.

A.2 Missing Proofs of Sec. 5
Proof of Lemma 3. The mirror descent recurrence is T (τ +1) = Proj Π(1,1) T (τ ) The projection is achieved by Sinkhorn scaling [?], that is, where Y = T (τ ) G(T (τ ) ), and u, v ∈ R V + . The recurrence implies that, The feasible domain requires that where the first inequality is due to the fact that u i ≥ 0 and Y ii ≥ 0. Combining Eq. (14), (13), and 1 Proof of Theorem 4. By the definition of the structural inconsistency, Where the second equality is due to the fact that N s ii for all i and i = i * , The right hand side of the inequality is exactly SI(i, i * ; T (τ ) ).

Proof of Theorem 5
We can rewrite the transport plan T as a vector variable x ∈ R V 2 + and the Gromov-Wasserstein distance Eq. (8) as objective f (x) = x Ax, respectively.
It is easy to verify that 1. The feasible domain is a closed convex set.
2. f (x) is a weakly convex function.
3. The norm of the gradient ∇f (x) for all feasible x is bounded.
4. The optimal objective value, denoted as f min , exists and f min > −∞.
By Corollary 3.1 of Zhang and He [2018], SIGMA converges to an -stationary point with the number of mirror descent iterations O( 1 2 ).

B.1 Additional Experiment Details
We first include more experimental details about parameter choice in this subsection. For experiments in the main paper, we set the propagation time t = 1×10 −3 and the number of hops K = 3.
The influence of K. We empirically study the influence of K. On the one hand, increasing K can increase the distinguishability of nodes and thus boost the matching accuracy. On the other hand, SIGMA with a larger K is easier to be affected by structural noise, as is implied by the upper bound in Theorem 2. Figure 3 demonstrates that K = 3 can achieve a balance. With the amount of noise increasing, SIGMA with a larger K deteriorates faster. SIGMA with K = 1 outperforms RefiNA, which demonstrates that SIGMA is more related to MNC theoretically.  Sensitivity to propagation time t. The range of propagation time is determined by line search, which is demonstrated in Figure 4. On all datasets, SIGMA is not sensitive to the choice of propagation time t and achieves good performance when 1 × 10 −6 ≤ t ≤ 1 × 10 −3 . Note that when t is too small, Ψ I − tL where I is the identity matrix and SIGMA is reduced to only considering one-hop information. Therefore, the accuracy slightly drops when t ≤ 1 × 10 −5 .  We further demonstrate the performance of SIGMA by matching real-world correlated graphs, i.e., the structural difference between the two graphs is induced by real noise instead of simulated noise. The experiments are conducted on graphs of Autonomous Systems peering information inferred from Oregon Route-Views (RV) 1 between March 31 st , 2001 and April 28 th , 2001. The University's RV project 2 was a tool for Internet operators to obtain real-time border gateway protocol information about the global routing system. We match RV on March 31 st to RVs between March 31 st and April 28 th . The dataset statistics are listed in the Table 3. We still set t = 1 × 10 −3 and K = 3 for SIGMA. For fair comparison, RefiNA, MM, GWL, and SIGMA use the ouput of CONE-Align to initialize the matching matrix.

B.2 Matching Real-world Related networks
We report the results on Table 4. As RV changes over time, the performance of all methods decreases except the one on April 28 th . This is possibly due to monthly patterns in RVs. SIGMA outperforms all baselines. GDD does not take as input the result of CONE-Align and is a deterministic algorithm. The standard deviation is thus 0. Other 0.000 deviation values are induced by rounding to three decimal places.


extfieldsofstudy:
Computer Science
Engineering

text:
Design Guidelines for Inclusive Speaker Verification Evaluation Datasets

Speaker verification (SV) provides billions of voice-enabled devices with access control, and ensures the security of voice-driven technologies. As a type of biometrics, it is necessary that SV is unbiased, with consistent and reliable performance across speakers irrespective of their demographic, social and economic attributes. Current SV evaluation practices are insufficient for evaluating bias: they are over-simplified and aggregate users, not representative of real-life usage scenarios, and consequences of errors are not accounted for. This paper proposes design guidelines for constructing SV evaluation datasets that address these short-comings. We propose a schema for grading the difficulty of utterance pairs, and present an algorithm for generating inclusive SV datasets. We empirically validate our proposed method in a set of experiments on the VoxCeleb1 dataset. Our results confirm that the count of utterance pairs/speaker, and the difficulty grading of utterance pairs have a significant effect on evaluation performance and variability. Our work contributes to the development of SV evaluation practices that are inclusive and fair.

Introduction
Speaker verification (SV) technology, which determines the identity of a speaker from their voice, is widely used across the world as a form of biometric identification [1]. Applications range from devices like mobile phones and smart speakers to transactional, investment and mobile banking, call centers and proof-of-life verification of pensioners. While unobtrusive, SV is extremely sensitive to the recording hardware, the deployment context and environment [2]. Moreover, it is also sensitive to the demographic attributes of speakers [3].
In machine learning (ML), bias has become a priority concern for fair and inclusive development of ML technologies. A ML system is considered biased if its predictive outputs favour or are prejudiced against individuals or groups of people based on their demographic attributes [4]. An often-times unintended consequence of bias is discrimination, which can lead to public mistrust [5] and legal consequences [6]. It is thus important that potenatial bias in SV systems is evaluated and mitigated during development. Studies of bias in SV, and research to mitigate its effects, are currently limited. Recent research has highlighted that existing SV evaluation practices contribute to exacerbating bias in the development of SV systems [7]. In particular, unrepresentative benchmarks make it impossible to evaluate bias, let alone address it. This paper presents design guidelines for the creation of more inclusive evaluation datasets that are suitable for evaluating bias in SV. While existing SV datasets consider demographic representation on a speaker level [8,9,10], we show that it is also important to consider inclusion at the more finegrained level of utterance pairs. We address two key questions: 1. How should utterance pairs be constructed to support an unbiased evaluation?
2. How many utterance pairs are needed per speaker for a robust SV evaluation?
Using an iterative design approach, we propose an algorithm for constructing evaluation datasets that are representative of realistic application scenarios. We empirically validate the utility of the datasets. Our experimental results present evidence that the difficulty of utterance pairs impacts the evaluation outcome. We also show that randomized utterance pairings can result in significant performance variation if the utterance pair count per speaker is low. Based on these results we propose design guidelines that consider inclusion on an utterance level.
In the next section we present background information on SV evaluation. Design considerations for the evaluation dataset are discussed in Section 3. Section 4 outlines the experimental setup and results. We propose evaluation dataset design guidelines and an outlook on future work in Section 5 and conclude in Section 6.

Background
We now present a short overview of SV evaluation, and discuss shortcomings of current practices. For a detailed overview of SV techniques and systems we refer the reader to [1] for a historic, and to [11] for a recent survey of deep learning methods.

Speaker Verification Evaluation
SV performance is determined by the false positive (FP) rate and false negative (FN) rate at a threshold value to which the system has been calibrated. It is accepted that the two error rates present a trade-off, and that selecting an appropriate threshold is an application-specific design decision [12]. The threshold value is determined by balancing the FP and FN error rates for a particular objective, such as obtaining an equal error rate (EER) for FP and FN errors, or minimising a cost function. The US National Institute of Standards and Technology (NIST), which has been conducting speaker recognition evaluations for over two decades, advises against the use of the EER, as applications typically require either low FP or FN [13]. The detection cost function (DCF) is a weighted sum of FP and FN rates across threshold values, with weights determined by the application requirements [13]. To compare performance across models, systems are frequently tuned to the threshold value at the minimum of the DCF (minDCF), and the minDCF is reported as metric. NIST recommends that SV systems are evaluated with Detection Error Tradeoff (DET) curves to show SV performance across a range of error rates.

Short-comings of Current Evaluation Practices
Alongside the NIST, independent SV competitions are a popular mechanism for evaluating and driving advancement in SV techniques. Many competitions, such as SITW [10], the Vox-Celeb SRC [14] and the Far-Field SRC [15] have been hosted at Interspeech. The competitions serve as benchmarks, promote evaluation habits and implicitly guide the culture of evaluation in the domain. To enable comparison across competition entries, they focus their evaluations on one or two metrics, typically a version of the minDCF or EER.
Recent research on bias in SV has shown that evaluation outcomes are highly dependent on the evaluation dataset and metrics used for evaluation [7]. The paper found that current SV evaluation practices consider limited context, environment and user variability in the design of evaluation datasets and metrics. The authors argue that SV evaluation practices present an oversimplified view of application scenarios, promote unrepresentative benchmark populations and oversimplified metrics, do not consider the consequences of errors and favour low FP rates while neglecting the consequences of FN rates. This limits current evaluation practices in their ability to detect bias in realistic application settings and adds to bias that may already exist in SV technologies. We build on this work by studying approaches to mitigating bias in the design of evaluation datasets to ensure that evaluation practices are more inclusive and fair.

Dataset Design Considerations
In this section we consider consequences of speaker verification (SV) errors, introduce a schema for grading utterance pairs, and propose an algorithm for generating inclusive SV evaluation datasets.
We use the following terminology and notation. A speaker (S i ) is a unique individual with at least one speech utterance (u i ) in the set of all evaluation utterances (U). U i is the subset of evaluation utterances of speaker S i and S = {S 1 ...S K } is the set of all speakers in U. An evaluation dataset (D) is constructed by generating utterance pairs {ua, u b } from the evaluation utterances in U. Conventionally ua is the enrollment utterance, and u b is the test utterance. Practically, the order of utterance pairs does not matter in SV evaluation.
A same speaker pair {u 1 a , u 1 b } has the enrollment and test utterances drawn from U 1 , while a different speaker pair {u 1 a , u 2 a } has the enrollment and test utterances drawn from two different speakers, ie from U 1 and U 2 . The objective of creating an inclusive SV evaluation dataset, D, is then to: • offer an equivalent evaluation across all speakers in S • generate same speaker and different speaker utterance pairs that are reflective of deployment usage scenarios • facilitate an evaluation that is robust to perturbations in utterance pairings (e.g., if {u 1 a , u 2 a } is substituted with {u 1 b , u 3 f } the false positive error rate should not change significantly)

Difficulty Grading of Utterance Pairs
SV is a comparative task that compares an enrolled speaker utterance with a test utterance based on the difference between embeddings of the voice profiles. Naturally, system performance is affected by the utterance pairs being compared. However, not all utterance pairs are born equal.
It is important that evaluation utterance pairs test likely scenarios that a SV system will encounter when deployed, and that pairs of appropriate difficulty are constructed to test the limits of the system. A qualitative difficulty grading of utterance pairs has the advantage that it bares no computational cost and that it can be interpreted in relation to the application context. We thus created a schema for grading the difficulty of utterance pairs across four categories: trivial (cat 1), easy (cat 2), medium (cat 3) and hard (cat 4) for same and different speaker pairs. As a general rule, evaluation of same speakers is easier if utterance pairs are more similar, and harder if utterance pairs are more different. For different speakers the opposite is true: similar utterance pairs are harder, and different utterance pairs are easier to classify. Speaker, recording channel and environmental attributes affect the similarity of utterance pairs. In Table 1 we show how we use the schema to grade utterance pair difficulty based on speaker gender, nationality, recording channel and background noise (attributes chosen based on available metadata in the VoxCeleb1 dataset). Same speaker pairs always have the same gender and nationality, while different speaker pairs are never from the same recording. We assume that utterances from the same recording have the same noise conditions.

Generating Evaluation Datasets
Taking these considerations and the dataset requirements into account, we designed Algorithm 1 for generating an evaluation dataset, D, from a set of utterances, U. Given available utterances, our intention was to create an evaluation dataset in the most difficult category. To ensure that the evaluation is robust to perturbations in utterance pairings, the random seed for selecting same and different speaker utterance pairs can be changed to generate similar datasets with different utterance pairings. SV evaluation outcomes can then be compared across the datasets.

Experiments
We empirically validated our approach to generating SV evaluation datasets by conducting experiments with the VoxCeleb1 dataset [16]. Due to space limitations we only show experiments and results for speaker groups based on nationality. Our experiments show that model performance deteriorates significantly when evaluated on datasets with more difficult utterance pairs of same and different speakers. Moreover, when the number of utterance pairs per speaker is low, model performance has high variability. Evaluation robustness improves as the number of utterance pairs increases. In this section we describe the setup of the experiments and the baseline evaluation dataset, and then present results to demonstrate the effect of utterance pair grading and count.

Setup
We use a pre-trained end-to-end model based on a 34-layer ResNet trunk architecture. The model is described in detail in [17] where it is referred to as the performance optimized model. The model has been trained on the VoxCeleb 2 training set [8], with close to 1 million utterances of 5994 speakers. 61% of speakers are male and 29% of speakers have a US nationality, which is the most represented nationality. The feature

Algorithm 1 Evaluation Dataset Generation Algorithm
S ← set of all speakers i ← unique speaker a, b ← two recording instances u ← utterance U ← set of all utterances n ← count of different speaker utterance pairs/speaker r ← random seed pass end if end for D i same ← randomly select n pairs from D i same with seed r U i n ← randomly select n u from U i with seed r (replace ok) U j n ← randomly select n u from U j with seed r input to the model are 64-dimensional log Mel-filterbanks. We use the model in a SV inference pipeline to classify utterance pairs in an evaluation dataset D as being from the same or from different speakers. The only variable that we consider in the experiments is D. Evaluation datasets were generated from VoxCeleb1 with the algorithm described in Section 3. Different speaker pairs were constructed from speakers with the same gender and nationality. The evaluation sets are characterised by speaker nationalities, the count of utterance pairs/speaker (n) 1 and the random seed with which the dataset was generated. The experiments are detailed in Table 2

Baseline Evaluation Dataset
To benchmark our evaluation datasets, we compare them against a baseline evaluation on VoxCeleb1-H. Of the three VoxCeleb1 evaluation sets, VoxCeleb1-H is considered the "hard" set. It includes only different speaker pairs of the same gender and nationality, and requires groups of 5 or more speakers. Table 3 summarises the attributes of same speaker pairs 1 n is the count of same or different utterance pairs. As these two counts are equal, the total number of utterance pairs per speaker is 2n.
in VoxCeleb1 H. As can be seen from the table, the number of speakers, the total number of utterance pairs, and the count of utterances pairs per speaker varies across speaker groups based on nationality. Additionally, all groups contain trivial (cat 1) same speaker pairs. However, the proportion of trivial pairs in relation to all of the group's same speaker pairs differs.

Results
We now analyze the results of our experiments and show how utterance pair grading and utterance pair count affect the evaluation outcome. Figure 1: DET curves for a baseline and our inclusive dataset show significant performance decline when the latter is used for evaluation. This implies that the SV model performs worse under more realistic and inclusive evaluation scenarios.

Effect of Utterance Pair Grading
Experiment 1 included speakers from 8 nationalities, with 520 utterance pairs of different speakers (1040 total pairs) per speaker. We call this dataset VoxCeleb1-Inclusive. The key differences between the VoxCeleb1-H baseline and VoxCeleb1-Inclusive are that the latter contains an equal count of pairs/speaker across individual speakers and speaker groups, that trivial same speaker pairs have been excluded and that speakers were included if their unique utterance pair count for different speakers was greater than our selection value n. Due to our randomized utterance pair generation, the different speaker pairs in the two evaluation sets are not the same. The DET performance curves for the model evaluated on the two datasets is shown in Figure 1. When evaluated on Vox-Celeb1 H performance is reasonable: a FP rate of 1% results in a FN rate of 5%. However, at the same FP rate the FN rate triples to 15% when same speaker utterance pairs are exclusively of medium difficulty grading. Figure 2: DET curves show variability in evaluation outcomes for evaluation sets with 50, 225 and 520 utterance pairs (n) for Canadian, Indian and UK speakers. For each n five datasets were generated with different random seeds.

Effect of Utterance Pair Count
In Experiment 2 we investigate the effect of the utterance pair count on the robustness of the evaluation, given perturbations in utterance pairings. We compare the evaluation outcome for Canadian, Indian and UK speakers across evaluation datasets generated with 50, 100, 150, 225, 350, 450 and 520 distinct different speaker utterance pairs/speaker. For each utterance pair count n we generated five versions of the dataset with different random seeds. For the equal error rate (EER) and minimum Detection Cost Function (minDCF) performance metrics we observe significant variability in performance when n is small. Results for the minDCF are shown in Figure 3. To illustrate, the minDCF of the worst performing evaluation is 30% higher than the best evaluation for Canadian speakers when n = 50. This performance difference can be attributed entirely to utterance pairings generated with different random seeds. In general, we observe that variance is greater when the count of unique speakers in a group is smaller: UK speakers experience the lowest variance, while Indian speakers experience the greatest variance.
Variability is not limited to performance on the EER and minDCF metrics, but exists across the DET performance curve, as shown in Figure 2. As n increases, variability remains greatest at the end points of the curve where FP and FN error rates are the greatest/smallest. Variability stablilizes first in the center of the curve. This means that at very low FP rates the expected FN rate will carry significant uncertainty (and vice versa), unless n is large enough to ensure stable performance.

Evaluation Dataset Design Guidelines
Based on our analysis and empirical validation, we propose that an inclusive evaluation dataset for robust speaker verification evaluation should: 1. have an equal number of same speaker and different speaker utterance pairs for each speaker 2. have at least 500 different speaker utterance pairs for each speaker 3. have an equal number of utterance pairs per speaker 4. have an equal proportion of utterance pairs of each difficulty grading per speaker 5. have utterance pairs with difficulty gradings that are representative of usage scenarios of deployed applications 6. be compared against datasets variations with randomly generated utterance pairings to ensure robust evaluation outcomes Limitations and Future Work: While we studied the effects of utterance pairs on SV evaluation outcomes, we did not conduct a detailed study on the number of unique speakers that are required for a robust evaluation. This is an opportunity to extend the proposed design guidelines in future research. Our classification of utterance pairs by difficulty grading was limited by the metadata available for the VoxCeleb1 dataset. In actual usage scenarios hard utterance pairs may be more challenging than the pairs we evaluated. For example, smart device applications should consider different utterance pairs from same gender family members or colleagues, which present the most likely intruders to these systems. Future work should also consider speaker groups along different dimensions, such as age, accent, health conditions and time.

Conclusion
In this paper we present design guidelines for generating inclusive evaluation datasets towards robust speaker verification (SV) evaluation. During an iterative development process we elaborate on design considerations that account for consequences of SV errors, propose a taxonomy for grading the difficulty of utterance pairs, and present an algorithm for generating inclusive evaluation datasets. We empirically validate the evaluation datasets generated with our proposed method in a set of experiments on the VoxCeleb1 dataset. Our results confirm that the count of utterance pairs/speaker, and the difficulty grading of utterance pairs have a significant effect on evaluation outcomes. We advocate that current speaker verification evaluation practices can become more inclusive and robust by including equal counts of utterance pairs with the same difficulty grading for all individual speakers and groups.