Current language models have been criticised for learning language from text alone without connection between words and their meaning. Consequently, multimodal training has been proposed as a way for creating models with better language understanding by providing the lacking connection. We focus on pre-trained multimodal vision-and-language (VL) models for which there already are some results on their language understanding capabilities. An unresolved issue with evaluating the linguistic skills of these models, however, is that there is no established method for adapting them to text-only input without out-of-distribution uncertainty. To find the best approach, we investigate and compare seven possible methods for adapting three different pre-trained VL models to text-only input. Our evaluations on both GLUE and Visual Property Norms (VPN) show that care should be put into adapting VL models to zero-shot text-only tasks, while the models are less sensitive to how we adapt them to non-zero-shot tasks. We also find that the adaptation methods perform differently for different models and that unimodal model counterparts perform on par with the VL models regardless of adaptation, indicating that current VL models do not necessarily gain better language understanding from their multimodal training.

§ INTRODUCTION

Having models learn language from text alone has been criticised based on several aspects, from fundamental arguments about how language works <cit.> to findings on lack of certain information in text <cit.>. To train language models on more sources than text is therefore a proposed direction for creating language models with better language understanding <cit.>. These models would then become multimodal, with the capability to process both text and information from other modalities.

every picture/.style=line width=0.75pt

[draw opacity=0][line width=1.5]  (175,21) – (190,21) – (190,96) – (175,96) – cycle ; [color=rgb, 255:red, 189; green, 16; blue, 224   ,draw opacity=0.49 ][line width=1.5]   ; [color=rgb, 255:red, 189; green, 16; blue, 224   ,draw opacity=0.49 ][line width=1.5]  (175,36) – (190,36)(175,51) – (190,51)(175,66) – (190,66)(175,81) – (190,81) ; [color=rgb, 255:red, 189; green, 16; blue, 224   ,draw opacity=0.49 ][line width=1.5]  (175,21) – (190,21) – (190,96) – (175,96) – cycle ;

[draw opacity=0][line width=0.75]  (165,31.5) – (180,31.5) – (180,106.5) – (165,106.5) – cycle ; [color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][line width=1.5]   ; [color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][line width=1.5]  (165,46.5) – (180,46.5)(165,61.5) – (180,61.5)(165,76.5) – (180,76.5)(165,91.5) – (180,91.5) ; [color=rgb, 255:red, 245; green, 166; blue, 35   ,draw opacity=1 ][line width=1.5]  (165,31.5) – (180,31.5) – (180,106.5) – (165,106.5) – cycle ;

[draw opacity=0][fill=rgb, 255:red, 134; green, 233; blue, 164   ,fill opacity=1 ] (236,112.4) .. controls (236,107.21) and (240.21,103) .. (245.4,103) – (312.6,103) .. controls (317.79,103) and (322,107.21) .. (322,112.4) – (322,140.6) .. controls (322,145.79) and (317.79,150) .. (312.6,150) – (245.4,150) .. controls (240.21,150) and (236,145.79) .. (236,140.6) – cycle ;

[draw opacity=0] (174.5,139.5) – (189.5,139.5) – (189.5,199.5) – (174.5,199.5) – cycle ; [color=rgb, 255:red, 74; green, 74; blue, 74   ,draw opacity=1 ]  ; [color=rgb, 255:red, 74; green, 74; blue, 74   ,draw opacity=1 ] (174.5,154.5) – (189.5,154.5)(174.5,169.5) – (189.5,169.5)(174.5,184.5) – (189.5,184.5) ; [color=rgb, 255:red, 74; green, 74; blue, 74   ,draw opacity=1 ] (174.5,139.5) – (189.5,139.5) – (189.5,199.5) – (174.5,199.5) – cycle ;

[draw opacity=0][line width=1.5]  (155,41.5) – (170,41.5) – (170,116.5) – (155,116.5) – cycle ; [color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][line width=1.5]   ; [color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][line width=1.5]  (155,56.5) – (170,56.5)(155,71.5) – (170,71.5)(155,86.5) – (170,86.5)(155,101.5) – (170,101.5) ; [color=rgb, 255:red, 74; green, 144; blue, 226   ,draw opacity=1 ][line width=1.5]  (155,41.5) – (170,41.5) – (170,116.5) – (155,116.5) – cycle ;

[fill=rgb, 255:red, 0; green, 0; blue, 0   ,fill opacity=1 ] (145.5,24) – (153,24) – (153,32) – (145.5,32) – cycle ;

[color=rgb, 255:red, 208; green, 2; blue, 95   ,draw opacity=1 ]   (193,85.5) – (230.04,118.28) ;
[shift=(232.5,120), rotate = 214.88] [fill=rgb, 255:red, 208; green, 2; blue, 95   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle    ;

[color=rgb, 255:red, 74; green, 74; blue, 74   ,draw opacity=1 ]   (193,169.5) – (230.04,136.72) ;
[shift=(232.5,135), rotate = 145.12] [fill=rgb, 255:red, 74; green, 74; blue, 74   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle    ;

[color=rgb, 255:red, 208; green, 2; blue, 95   ,draw opacity=1 ]    (324.5,125.8) – (353.59,125.73) ;
[shift=(357.59,125.72), rotate = 179.86] [fill=rgb, 255:red, 208; green, 2; blue, 95   ,fill opacity=1 ][line width=0.08]  [draw opacity=0] (8.13,-3.9) – (0,0) – (8.13,3.9) – cycle    ;

(242,110) node [anchor=north west][inner sep=0.75pt]  [color=rgb, 255:red, 255; green, 255; blue, 255   ,opacity=1 ] [align=left] [lt]52.04pt

(114,139) node [anchor=north west][inner sep=0.5pt]  [font=,color=rgb, 255:red, 74; green, 74; blue, 74   ,opacity=1 ] [align=left] [lt]40pt

(193,54) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 150; green, 150; blue, 150   ,opacity=1 ,rotate=-332.48] [align=left] $\bm{\ldots}$;

(94.5,36.9) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 74; green, 144; blue, 226   ,opacity=1 ]  $\mu ( V_{\mathrm{train}})$;

(125,18.9) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 245; green, 166; blue, 35   ,opacity=1 ]  $V( \ \ \ )$;

(161,7) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 189; green, 16; blue, 224   ,opacity=0.49 ]  $\bm{\vec{0}}$;

(210.5,83) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 208; green, 2; blue, 95   ,opacity=1 ] [align=left] ?;

(360,112) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 245; green, 205; blue, 35 ] [align=left] ;

(333.5,104) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 208; green, 2; blue, 95   ,opacity=1 ] [align=left] ?;

(195,20) node [anchor=north west][inner sep=0.75pt]  [font=,color=rgb, 255:red, 150; green, 150; blue, 150   ,opacity=1 ] [align=left] visual features;

An overview of different ways to adapt a multimodal model to text-only input. It showcases three of the seven adaptations evaluated in this work.

The multimodal models of interest in this work are vision-and-language (VL) models that have been trained on images and their corresponding captions or visual questions <cit.>. These models are performant on several image-text tasks such as image captioning and VQA, while there also is an increased interest for evaluating how their natural language understanding is influenced by their multimodal training <cit.>.

It is however tricky to investigate the pure natural language understanding of the aforementioned VL models, since their language processing is conditioned on visual features. For certain investigations, we may simply wish to evaluate the models on text-only domains, while these models have not been developed for this purpose. If we do not attend to the issue of accurately adapting VL models to text-only domains we risk evaluating them out-of-distribution and fail to accurately measure their natural language understanding capabilities.

Different methods for adapting VL models to a text-only input have already been tried and we have some results on the natural language understanding capabilities of these models <cit.>.

However, no systematic search for the best way to adapt VL models to a text-only input has been performed and it is unclear how well the VL models work with the
previously proposed
adaptations. If we wish to continue the search for better natural language understanding in multimodal models,

we should ensure that we evaluate them in the best way possible. In this work, we search for the best method for adapting existing VL models to a text-only input, as illustrated in <Ref>.[Code available at <https://github.com/lovhag/adapt-pre-trained-VL-models-to-text>]

With the adaptations in place, we can then compare the VL models to their unimodal text-only counterparts. This will complement already existing results on the natural language understanding capabilities of VL models and the effect of multimodal training.

The contributions of our work are as follows:

* We investigate and compare seven methods for adapting LXMERT <cit.>, VisualBERT <cit.> and CLIP-BERT <cit.> to a text-only input (<Ref>). Two of these adaptations have already been used in previous investigations of the linguistic capabilities of VL models <cit.>.

* We evaluate these adaptations on the GLUE benchmark <cit.> (<Ref>). This gives us results on how well the adaptations work for tasks that aim to evaluate general natural language understanding.

* We also evaluate the adaptations on the Visual Property Norms (VPN) <cit.> (<Ref>). This gives us results on how well the adaptations work for zero-shot tasks that aim to evaluate visual conceptual knowledge in the models.

* We compare the adapted VL models to their unimodal BERT-base <cit.> counterparts on the aforementioned evaluation tasks. The ensuing results should provide additional clarity on the natural language understanding of VL models.

* We also compare the adapted VL models to the multimodal FLAVA model <cit.> that requires no adaptation to text-only tasks.

Model     Size     Pre-train data     Backbone

BERT-base     110M     English Wiki, BookCorpus     -

FLAVA      86M     CCNews, BookCorpus, PMD     -

CLIP-BERT     110M     English Wiki, BookCorpus, CLIP-BERT V+L     CLIP

LXMERT     230M     LXMERT V+L     Faster R-CNN

VisualBERT     110M     English Wiki, BookCorpus, VisualBERT V+L     Faster R-CNN

The models evaluated with details on their pre-training data. The V+L datasets refer to model-specific VL datasets. With `FLAVA` we refer to the text encoder.

§ MODELS

We investigate adaptations to text-only input for the three multimodal models CLIP-BERT, LXMERT and VisualBERT. We also compare their results with those of a baseline BERT-base model and  FLAVA. The models are further described below and an overview of them can be found in <Ref>.

For each of the multimodal models, we also describe how to make the model function without visual input. This is later used in some of the adaptations we evaluate, described in <Ref>.

All models evaluated in this work except for CLIP-BERT are provided by the Huggingface library <cit.>. The pre-trained model weights for all models except for CLIP-BERT are also provided by this library. The CLIP-BERT weights are found in our public repository.

§.§ VisualBERT

VisualBERT is a single-stream model that has been initialized from pre-trained BERT-base weights and then further trained on MS COCO as well as VQA <cit.>. As a result, it has been trained on 1.27M more texts and 0.12M more images than BERT-base. It utilizes a Faster R-CNN detector <cit.> as backbone, for which it has been trained on the features of the 36 first detections, meaning that it expects visual input features with shape $(36, 2048)$.

Usage without visual input
The single-stream architecture of this model implies that it simply concatenates the embeddings from the visual features with the word embeddings from the text input and then forwards this to the BERT encoder.
Therefore, this model can be queried with text only without changing anything in the model architecture, since it simply means that only the word embeddings are fed to the BERT encoder.

§.§ LXMERT

LXMERT is a dual-stream model trained on MS COCO, VQA, VG, GQA and VG-QA <cit.>. It has not been initialized from BERT-base weights. In total, it has been trained on 9.18M visual texts and 0.18M images. Similarly to VisualBERT, this model expects visual features of the shape $(36, 2048)$ from 36 Faster R-CNN detections.

Usage without visual input
The dual-stream architecture of this model implies that it processes the visual embeddings and word embeddings in separate encoders before it fuses the information from them in a so called Cross-Modality Encoder. For this model it does not suffice to simply omit the visual input since it is expected by a separate visual encoder. However, the language output of the model is only affected by the visual input at a set of cross-attention sub-layers with residual connections in the Cross-Modality Encoder. Consequently, we can set the added residual from the cross-attention layer to zero and remove the visual encoder of the model.

§.§ CLIP-BERT

CLIP-BERT is a single-stream VL model that is architecturally very similar to VisualBERT. The main differences this model introduces are two, 1) it has a CLIP <cit.> backbone that generates visual features of dimension $(512,)$ for each image, and 2) it has been trained on 4.72M visual texts and 2.91M images, a vision-language dataset approximately four times larger than that of VisualBERT, in addition to having been initialized from BERT-base weights.

Usage without visual input
Similarly to VisualBERT, the single-stream architecture of this model implies that it can be queried with text only without changing anything in the model architecture, since it simply means that only the word embeddings are fed to the BERT encoder.

§.§ BERT-base

Since all VL models we evaluate to some extent are based on BERT-base, we use this unimodal model as a baseline in our evaluations seen in <Ref>.

We also create two additional baseline versions of BERT-base by further training the pre-trained model on LXMERT text data[The data is described in <https://github.com/airsplay/lxmert>.] and a subset of the English Wikipedia corpus from the Huggingface Datasets library <cit.> sampled to match the LXMERT text data in size, respectively. We do this to enable more fair comparisons to the evaluated VL models, since they have received additional training on text and images. These model versions are denoted by  and . The unchanged BERT-base model is denoted by .

Since the original LXMERT model developed by <cit.> was not initialized from BERT weights, we also develop a third baseline version of BERT that has been trained from scratch on LXMERT text data for comparison. This model version is denoted by .

More information about the datasets used to train the BERT-base baselines and training procedures can be found in <Ref> respectively.

§.§ FLAVA

FLAVA is a multimodal model that works for all combinations of VL modalities without any need for adaptation <cit.>. It sidesteps all issues related to the aforementioned VL models and can directly be evaluated for its linguistic capabilities. It consists of three separate parts: an image encoder, a text encoder, and a multimodal encoder that combines the input from the unimodal encoders. The unimodal encoders are pretrained on unimodal datasets and the full model is then trained end-to-end on the Public Multimodal Datasets (PMD) corpus <cit.>. We use the text encoder of this model as a baseline in our evaluations.

§ ADAPTATIONS TO TEXT-ONLY INPUT

There are several ways to adapt a VL model to a text-only input. In this work we investigate and compare seven possible adaptations, as described below. Two of the adaptations described here have already been used for investigating the linguistic capabilities of VL models <cit.>. Common for all adaptations is that their intended use is for evaluation of a pre-trained VL model (encoder) on text-only input. When we refer to the word adaptation we refer to the adaptation of a VL model to text-only input.

The adaptions can be grouped into three different categories based on how they are implemented. For the first category, we simply remove the visual input to the VL model (<Ref>). For the second category, we provide the model with visual features that are constant and can be viewed as fillers, (<Ref>). For the third category, we provide the model with visual features predicted from text (<Ref>).

§.§ Using model as-is without visual input

All VL models considered in this work can be queried with text only, or after performing a small set of alterations to the model architecture without changing any pre-trained model weights, as described in <Ref>. Thus, we can directly evaluate the pre-trained models on the text-only task of interest. This adaptation is denoted by .

This adaptation is very simple to apply and does not require any additional computations, while it assumes that the VL model can be queried without visual input. It is also not certain that the models will function as intended due to the imposed train/test shift of this adaptation. To our knowledge, this approach has not been tested before.

§.§ Fine-tuning model on text-only input

Before evaluating the pre-trained VL model we fine-tune it on a small text-only fine-tuning task, similarly to how several natural language understanding tasks are performed <cit.>. The idea is that this will acclimatize the model to the aforementioned domain shift. Similarly to the  adaptation, this also relies on being able to use the model  without visual input.

We create two separate fine-tuning sets
for this adaptation. The sets have been extracted from the text part of the LXMERT training data and from English Wikipedia. Their sizes have been adapted to match those of typical fine-tuning sets for e.g. SuperGLUE <cit.> and we have ensured that the number of tokens in each fine-tuning set is roughly equal. More information about the datasets can be found in <Ref>.

Finetuning the VL models on each of these sets should give us results on both the performance of the method, and on how dependent it is on the chosen fine-tuning set.
These adaptations are denoted by  and  respectively.

This method avoids having to work with image feature extractors and image data. However, it requires setting up a training algorithm and additional computations. Moreover, since the full model needs to be trained for this adaptation, it is more sensitive to hyperparameter choices. It is also not certain whether it is sufficient to perform fine-tuning on text to acclimatize VL models to a text-only input. More information on tuning procedures can be found in <Ref>.

§.§ Using averaged visual features from the training dataset

In this method we give the VL model a constant visual feature input together with the text of interest at evaluation, where the visual features are the average of all the visual features in the train or evaluation data of the model. The provided visual-features should then be kept in-distribution, while they also are uninformative.
This adaptation has already been used by <cit.> for ablating visual input to VL models. We denote it by .

No assumptions or changes to the model architecture are necessary for this method. However, it requires access to the datasets used to train the model of interest and the computation of the averaged visual feature vector.

We calculate the averaged visual feature vector for CLIP-BERT based on the CLIP features of its training data. We also calculate the averaged visual features and position vectors for LXMERT from its corresponding training data. We take the average across training samples per detection for the LXMERT visual features such that we get one average feature vector for the first detection, another for the second detection and so forth up to the 36th.

The original released VisualBERT visual features are not compatible with the Huggingface implementation of the model used in this work.
We instead provide VisualBERT with the LXMERT averaged visual features, since they are compatible.

§.§ Using visual features from a black image

The idea is yet again to give the VL model a constant visual feature input together with the text of interest. In this case, the visual features are extracted from a black image using the model backbone. The model then receives a visual input similar to what it has been trained on, while it does not contain any information. This adaptation has already been used by <cit.> for evaluating e.g. VisualBERT and LXMERT on GLUE. We denote it by .

Similarly to the averaged features adaptation, this adaptation makes no assumptions about the model of interest. However, it requires access to the backbone of the model and the computation of the visual features from a black image.

We use the LXMERT feature extractor to extract 36 detections with their visual features and bounding boxes from a black image. The extractor is a Faster R-CNN model developed by <cit.>. These features are then given to LXMERT and VisualBERT during evaluation. For CLIP-BERT we use CLIP to extract visual features from the same black image.

§.§ Using constant zero vector visual features

We give the model of interest constant visual features, and the positions of bounding boxes in the case of LXMERT, that are zeros. There are no guarantees that this method will work well for adapting VL models to a text-only input. It is however easy to implement and can be seen as a baseline to be compared with the other adaptations. To the knowledge of the authors, this method has not been used previously. We denote it by .

§.§ Using tuned visual features

We tune the visual features to a frozen version of the model of interest, and then use these constant features at evaluation together with the text of interest. To the knowledge of the authors, this method has not been used previously to adapt VL models to a text-only input. However, the key idea of tuning the input to the model has been used in previous works <cit.>.

We tune visual features to frozen and pre-trained versions of CLIP-BERT, VisualBERT and LXMERT respectively. We tune on the same LXMERT and Wikipedia sets used for the adaptation described in <Ref>. More information on tuning procedures can be found in <Ref>.

This method offers more flexibility for finding the most suitable constant visual features for a VL model evaluated on text-only tasks. However, it also requires setting up the training, more computations and is more sensitive to hyperparameter tuning. We denote these adaptations on the different fine-tuning sets by  and  respectively.

§.§ Predicting visual features from text

Some feature extractors map text representations and visual representations to the same parametric space. Consequently, they can be used to “imagine” visual features from text. The CLIP model serving as a backbone for the CLIP-BERT model has this capability and can be used to generate visual features from text during evaluation on text-only tasks. We implement it for the CLIP-BERT model and denote it by .

This method is quite simple to implement, while it requires access to CLIP and computing the visual features from the evaluation corpus. It is also not clear how well CLIP representations work for text that is not specifically related to visual concepts.

§ EVALUATION METHODS

To assess the performance of our text-only adaptations, we firstly evaluate them on the GLUE benchmark, described in <Ref>. These evaluations will give us results on how well the models and their adaptations work for general natural language understanding tasks. This benchmark has been used by both <cit.> and <cit.> to evaluate natural language understanding capabilities of BERT and VL models.

Furthermore, to assess the performance of the adaptations on text domains that are more focused on visual concepts, we perform evaluations on VPN, further described in <Ref>. This will provide us with results on tasks the VL models potentially are more attuned to, complementing the general GLUE results.

MLM query     Gold labels

a cow usually is [...]      black, white

a mug has a [...]     handle

q: a greeting card has? a: [...]     pictures

Query samples from the VPN dataset for the concepts cow, mug and greeting card using three out of nine possible query templates. The [...] is typically replaced with a  token.

§.§ GLUE

The General Language Understanding Evaluation (GLUE) benchmark has the aim to evaluate model performance across several NLU tasks. It was developed by <cit.> and has since then been used to evaluate the natural language understanding of several LMs, including BERT.

GLUE contains nine different tasks testing for grammatical correctness understanding (CoLA), sentiment classification (SST-2), semantic equivalence detection on different text domains (MRPC, QQP, STS-B), textual entailment (MNLI, RTE), answer extraction from text (QNLI) and reading comprehension (WNLI). All tasks are sentence classification tasks and have corresponding train and validation sets for fine-tuning.

VL models have already been evaluated on GLUE by <cit.> using the black image adaptation method listed in <Ref>. We extend the GLUE evaluation to include all alternative adaptation approaches listed in <Ref>.

To evaluate the performance of our adaptations on GLUE, we first fine-tune our selected multimodal models with each adaptation on the training sets of the GLUE tasks. We then report the validation scores of the models and their adaptations. More information about the fine-tuning procedures can be found in <Ref>.

clip,trim=0cm 0cm 7.3cm 0.1cm

Visual Property Norms (PF $\geq10$)

clip,trim=2.6cm 0cm 7.8cm 0.1cm

clip,trim=8.5cm 7.65cm 1.6cm 0.3cm

clip,trim=8.5cm 4.9cm 1.6cm 3.1cm

Results on GLUE and VPN from evaluating different adaptations to text-only input. The GLUE results are given by the mean of the scores for the development sets of all tasks, excluding WNLI. The metric used for each task is F1 score for QQP and MRPC, Matthews correlation for CoLA, Spearman correlation for STS-B, and accuracy for the remaining tasks. For VPN the box length indicates prompt sensitivity over nine different query templates.

CoLA     MNLI     MRPC     QNLI      QQP      RTE     SST-2     STS-B

BERT-base                      61.1         84.6         87.3/91.2         91.9         91.1/88.0         70.4         93.7          88.2

FLAVA                          50.1         81.6         83.6/88.3         87.8         90.4/87.2         55.6         92.4          87.1

CLIP-BERT                      55.4         83.2         75.5/84.1         89.8         91.1/88.0         58.1         92.0          87.8

LXMERT                         15.9         68.1         69.9/81.6         68.0         84.1/76.8         58.5         86.6          40.1

VisualBERT                     53.3         83.7         80.4/86.4         90.7         90.9/87.6         67.5         91.7          89.6

GLUE development set results per task for the best performing adaptation on average. The best performing adaptation for each model is `default` for BERT-base, `avg-visual-features` for CLIP-BERT, `no-visual-features-finetuned-Wikipedia` for LXMERT and `no-visual-features-finetuned-Wikipedia` for VisualBERT . We report Matthew's correlation for CoLA, average accuracy for MNLI, accuracy/F1 score for MRPC, accuracy for QNLI, accuracy/F1 for QQP and accuracy for RTE and SST-2 and Spearman correlation for STS-B.

VPN Score

BERT-base                   49.1 $\pm$ 13.2

FLAVA                30.7 $\pm$ 6.9

CLIP-BERT                   48.2 $\pm$  4.2

LXMERT                  42.8 $\pm$ 10.8

VisualBERT                  38.1 $\pm$ 9.1

VPN results for the best tations. The best performing

§.§ Visual Property Norms

Our current VL models are not necessarily the best fit for general NLU tasks such as GLUE <cit.>. Therefore, we also evaluate them on a task we assume they are more suitable to. Visual Property Norms (VPN) essentially queries a model for the basic visual properties of a set of concepts <cit.>. It is a text-only task, while it explicitly focuses on visual properties and concepts. Thus, if the VL models should perform particularly well on any text-only task, this would be the one. <Ref> displays examples of queries from the VPN dataset.

The VPN dataset is a zero-shot evaluation task that evaluates a model using masked language modelling (MLM), an objective our models already have been trained on. To mitigate issues with prompt-sensitivity of LMs, nine different query templates are applied during evaluation.

VPN is a version of the CSLB concept property norms dataset <cit.> filtered to only contain visual conceptual features. The original property norms dataset was created with the help of 123 human participants asked to list the features of a set of concepts. Each concept has in total been exposed to 30 humans and the maximum frequency of a feature reported for a concept is then 30 and the minimum 2. This frequency is referred to as Production Frequency (PF).

VPN has been segmented into five partitions based on thresholding of PFs. We evaluate our adaptations on the segment for which PF $\geq 10$, such that ten or more annotators jointly have produced the visual features in this set. It consists of 2,001 feature entries for 621 different concepts.

§ RESULTS

We report the evaluation results for CLIP-BERT, LXMERT and VisualBERT with the seven potential adaptions to text-only input in <Ref>. We also report the results for our four BERT-base baselines. For GLUE we report the macro-averaged score over the GLUE tasks. The score for each task is measured using its corresponding predefined metric described by <cit.>. For VPN evaluation we report the mean average precision (mAP) score averaged over each concept and relation per query template.

We also report the evaluation results on GLUE for each task and model for the best performing adaptation measured by average GLUE score in <Ref>. <Ref> similarly reports the model scores on VPN for the best adaptation on average. We compare these results to those of the FLAVA text encoder that requires no adaptation. Complete numerical results can be found in <Ref>.

We format our discussion around a set of statements that can be made with respect to the results of this work, as follows.

Model performance on GLUE is more sensitive to pre-training than to adaptation
Model performance on GLUE varies insignificantly between different adaptations for each model in <Ref>. The CLIP-BERT performance varies with less than 0.01 score points between adaptations and the VisualBERT performance with at most 0.02 score points between 'no-visual-features-finetuned-Wikipedia' and 'zeroed-visual-features'. The LXMERT performance also has a performance difference of at most 0.02 score points between 'default' and 'zero-image-visual-features'.

The largest performance difference on the GLUE benchmark can be observed between models, where LXMERT and BERT-base trained from scratch on LXMERT data perform significantly worse in comparison to the other models. Most likely, this is due to that the models were not initialized from BERT weights and consequently were not tuned to more general language usage.

A possible explanation for why the adaptation methods seem to matter so little for the GLUE results is that the benchmark is not zero-shot. The fine-tuning performed on each task might provide a sufficient of signal to the model for it to adapt to the unimodal domain.

Lastly, our results on GLUE for LXMERT and VisualBERT differ from those obtained by <cit.>. Especially with respect to LXMERT for which we observe a significant performance difference compared to the other VL models, while the same cannot be observed in the results by <cit.>. However, this should not raise any concerns about the robustness of the results, since we evaluated the original released models, while <cit.> evaluated models that had been unified and trained on the same data by <cit.>. And as we observed previously, GLUE results are sensitive to pre-training process.

Performance on Visual Property Norms is sensitive to adaptation

In contrast to the observations made for GLUE, performance on VPN differs significantly between different adaptions in <Ref>. In contrast to GLUE, this task is zero-shot and may provide a greater challenge for models that are not sufficiently tuned to the unimodal text domain.

Additionally, it is worth noting that the model performance is quite sensitive to the choice of query template. However, this is not entirely unexpected since it has been shown that LMs are prompt-sensitive in prompt-based retrieval evaluations <cit.>.

Different adaptations perform differently for different models on Visual Property Norms

For CLIP-BERT, the most suitable adaptation for evaluation on VPN is to provide the model with visual features that have been tuned on LXMERT text data. For LXMERT, the best approach is to use the model as-is without visual input, and for VisualBERT the best adaptation is to fine-tune the model on LXMERT data without visual features. Common for all of these adaptations is that they involve some kind of prior tuning on LXMERT text data. A potential explanation for this is that the LXMERT data is more similar to VPN and results in a smaller domain shift.

An explanation for the varying adaptation fits between VL models is potentially found by looking at the different pre-training datasets and architectures of the models. VisualBERT has been tuned on much less data compared to the other models, and may therefore benefit from more training in general. Additionally, the single-stream CLIP-BERT and VisualBERT models process all linguistic and visual information in a joint manner, without the same ability to disentangle signals as the dual-stream LXMERT model.

FLAVA does not outperform adapted VL models

On both GLUE and especially VPN, FLAVA is not better than the adapted VL models. This contrasts the GLUE results reported for FLAVA and other VL models by <cit.>. The difference in results may arise from differences in fine-tuning methods for GLUE and that we do not evaluate unified VL models.

Based on our results, adapting VL models to text-only input works better or equal to developing a model to work for all modalities from the start, as was done for FLAVA. However, since all models evaluated have been trained on different datasets with different objectives we cannot draw certain conclusions related to model design.

BERT-base baselines outperform vision-and-language models regardless of adaptation

Lastly, we can observe in <Ref> how default BERT-base and BERT-base trained on LXMERT text data each have among the best performances on GLUE and VPN respectively. For GLUE it is expected: <cit.> have already observed that VL models on average perform worse on GLUE. <cit.> also found similar results when they compared the quality of the linguistic representations of VisualBERT to those of BERT-base. The general natural language understanding capabilities evaluated in GLUE are potentially not easy to learn from a visual modality, explaining why the VL models did not perform better on this task. Our results on VPN are perhaps more surprising.

From their visual training, the VL models should more easily have gained natural language understanding capabilities necessary for better performance on VPN. Three potential explanations for why a LM still outperforms a VL model on VPN are 1) BERT-base is better tuned and therefore has a better overall performance, 2) the VL models evaluated in this work do not learn more about visual concepts from images compared to text that has been curated to contain visual information, or 3) the VPN task does not accurately measure the visual conceptual information we have in mind. More investigations are necessary to accurately determine the reason. In support of explanation (2), <cit.> found that there are similarities between color representations in LMs and actual perceptual color spaces, indicating that visual perceptual information may be found in text.

We should also note that none of the models evaluated in this work were developed with the goal of achieving better natural language understanding by multimodal training. This potentially explains some of our results, and provides an interesting avenue for future research in developing models that have a better performance on both unimodal and multimodal tasks.

§ RELATED WORK

As previously mentioned, <cit.> have already looked at the language understanding capabilities of VL models, while they only looked at one way of adapting these models to a text-only input and only evaluated on GLUE. <cit.> also look at the language understanding capabilities of VL models by evaluating the linguistic representations of VisualBERT and compare them to a BERT-base model that has been trained on the same text data. In contrast to their work, we investigate several VL models and evaluate their performance on language generation tasks.

<cit.>, <cit.>, <cit.> and <cit.> also perform extensive evaluations of several VL models such as LXMERT and VisualBERT. In contrast to our work, they primarily focus on the VL performance of the models, and do not consider the model performance on text-only input.

<cit.> introduce a new method for enriching the textual representations of a model by training on visual information. Their method results in a model that can be directly applied to text-only tasks and outperforms its standard BERT model counterpart on GLUE.
This method provides a parallel research avenue compared to adapting VL models to text-only input.

§ CONCLUSIONS

We have investigated and compared seven possible adaptations of CLIP-BERT, LXMERT and VisualBERT to text-only input by evaluation on GLUE and Visual Property Norms. We can conclude that care should be put into adapting these pre-trained VL models to text-only input for better performance on zero-shot tasks, while the choice of adaptation method seems to be less impactful on tasks coupled with fine-tuning sets.

Finally, we have observed that a unimodal LM has a performance on text-only tasks that is better or comparative to that of its VL model counterparts, regardless of how these counterparts were adapted to text-only input. Seemingly, improved pure text capabilities are not guaranteed from simply training a model on arbitrary multimodal tasks. This agrees with and solidifies previous research results on VL models.

§ ACKNOWLEDGEMENTS

We would like to thank the reviewers for their valuable feedback and advice on related work.

This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

The computations were enabled by resources provided by the Swedish National Infrastructure for Computing (SNIC), partially funded by the Swedish Research Council through grant agreement no. 2018-05973.

§ DATASETS FOR TRAINING AND TUNING

More detailed information on the datasets used for training and fine-tuning the models investigated in this work can be found here.

§.§ Training of BERT baselines

More information about the LXMERT and Wikipedia training datasets used for the BERT-base baselines can be found in <Ref>. By training the BERT model on LXMERT text data, it will have seen the same textual information as LXMERT. And by training it on the Wikipedia data, it will have seen the same amount of text as LXMERT.

Corpus     Partition     # of samples     # of tokens     # of tokens/sample

LXMERT     train     9.0M     59.0M     6.6

dev     0.2M     1.4M     6.8

Wikipedia     train     4.4M     59.0M     13.4

dev     0.1M     1.3M     13.4

The two text datasets used for developing two additional BERT-base baselines. The number of samples are roughly equal to the number of sentences for these datasets. The LXMERT data is the text part of the LXMERT training data. Wikipedia is a subset of general English Wikipedia texts that has been adapted to match the LXMERT data in total number of tokens.

§.§ Fine-tuning model on text-only input

The LXMERT and Wikipedia datasets used for fine-tuning text-only versions of VL models are further described in <Ref>. The two fine-tuning sets cover quite different domains. This is already visible from the tokens/sample count in the table, in which the Wikipedia corpus generally contains long sentences and the LXMERT corpus generally contains shorter sentences more suitable for image captions.

Corpus     Partition     # of samples     # of tokens     # of tokens/sample

LXMERT-f     train     9,500     63,000     6.6

dev     3,300     22,000     6.6

Wikipedia-f     train     4,600     63,000     13.7

dev     1,600     22,000     13.5

The two text datasets used for fine-tuning, denoted by the “-f” ending. The number of samples are roughly equal to the number of sentences for these datasets.

§ TRAINING PROCEDURES

More detailed information on our training procedures can be found here.

§.§ Training BERT-base baselines

For the training of BERT-base on both the LXMERT and Wikipedia datasets we use an MLM objective, a batch size of 16,384 and learning rate 5e-5 until the model performance on the dev set had converged. The maximum training time was at most 23 hours on 32 Tesla T4 GPUs.

§.§ Fine-tuning model on text-only input

We fine-tune the models using an MLM objective, batch size of 256 and learning rate 5e-5 until the model performance on the dev set had converged. The maximum training time was two hours on eight Tesla T4 GPUs.

§.§ Using tuned visual features

We tune the visual features using an MLM objective, batch size 64 and a learning rate of 0.05 until the model performance had converged on the dev set. The maximum training time was 18 hours on one Tesla T4 GPU.

§.§ Fine-tuning on GLUE

For the GLUE fine-tuning, we tune our models for four epochs with a learning rate of 3e-5, weight decay of 0.01 and batch size of 32. The longest tuning time was four hours on two A100 GPUs. We then pick the model checkpoint with the best validation score during training for evaluation.

§ COMPLETE NUMERICAL RESULTS

The complete numerical results on GLUE and VPN can be viewed in <Ref> respectively.

Model     Adaptation     Score

BERT-base     trained-LXMERT       80.7

trained-LXMERT-scratch       64.1

trained-Wikipedia       81.1

default       83.7

FLAVA     default       78.8

CLIP-BERT     default       79.6

no-visual-features-finetuned-LXMERT       79.0

no-visual-features-finetuned-Wikipedia       79.7

avg-visual-features       79.8

zero-image-visual-features       79.4

zeroed-visual-features       79.7

finetuned-LXMERT-visual-features       79.5

finetuned-Wikipedia-visual-features       79.6

imagined-visual-features       79.6

LXMERT     default       61.9

no-visual-features-finetuned-LXMERT       59.7

no-visual-features-finetuned-Wikipedia       61.9

avg-visual-features       61.3

zero-image-visual-features       59.9

zeroed-visual-features       61.8

finetuned-LXMERT-visual-features       61.5

finetuned-Wikipedia-visual-features       61.6

VisualBERT     default       80.6

no-visual-features-finetuned-LXMERT       80.1

no-visual-features-finetuned-Wikipedia       81.3

avg-visual-features       80.9

zero-image-visual-features       80.6

zeroed-visual-features       79.0

finetuned-LXMERT-visual-features       79.9

finetuned-Wikipedia-visual-features       80.5

The adaptation and baseline results for GLUE seen in <Ref>.

Model     Adaptation     Median      Standard deviation

BERT-base     trained-LXMERT                  49.1     13.2

trained-LXMERT-scratch                  44.3     13.2

trained-Wikipedia                  35.5      9.5

default                  39.0     12.4

FLAVA     default                  30.7      6.9

CLIP-BERT     default                  44.3      4.7

no-visual-features-finetuned-LXMERT                  44.5      7.0

no-visual-features-finetuned-Wikipedia                  41.5      5.4

avg-visual-features                  33.1      5.0

zero-image-visual-features                  41.8      5.8

zeroed-visual-features                  39.3      4.9

finetuned-LXMERT-visual-features                  48.2      4.2

finetuned-Wikipedia-visual-features                  33.3      4.8

imagined-visual-features                  31.4     10.2

LXMERT     default                  42.8     10.8

no-visual-features-finetuned-LXMERT                  41.0      7.5

no-visual-features-finetuned-Wikipedia                  34.6     10.0

avg-visual-features                  37.3     12.9

zero-image-visual-features                  42.1     11.0

zeroed-visual-features                  35.2     12.0

finetuned-LXMERT-visual-features                  37.2     13.9

finetuned-Wikipedia-visual-features                  28.5     11.7

VisualBERT     default                  29.0     10.9

no-visual-features-finetuned-LXMERT                  38.1      9.1

no-visual-features-finetuned-Wikipedia                  21.6      9.0

avg-visual-features                  29.8     11.0

zero-image-visual-features                  25.6     10.2

zeroed-visual-features                   7.1      3.1

finetuned-LXMERT-visual-features                  34.5     10.3

finetuned-Wikipedia-visual-features                  20.1      9.9

The adaptation and baseline results for VPN.


# Contrastive General Graph Matching with Adaptive Augmentation Sampling

Jianyuan Bo  Yuan Fang Singapore Management University, Singapore
{jybo.2020<EMAIL_ADDRESS>
###### Abstract

Graph matching has important applications in pattern recognition and beyond.
Current approaches predominantly adopt supervised learning, demanding
extensive labeled data which can be limited or costly. Meanwhile, self-
supervised learning methods for graph matching often require additional side
information such as extra categorical information and input features, limiting
their application to the general case. Moreover, designing the optimal graph
augmentations for self-supervised graph matching presents another challenge to
ensure robustness and efficacy. To address these issues, we introduce a novel
Graph-centric Contrastive framework for Graph Matching (GCGM), capitalizing on
a vast pool of graph augmentations for contrastive learning, yet without
needing any side information. Given the variety of augmentation choices, we
further introduce a Boosting-inspired Adaptive Augmentation Sampler (BiAS),
which adaptively selects more challenging augmentations tailored for graph
matching. Through various experiments, our GCGM surpasses state-of-the-art
self-supervised methods across various datasets, marking a significant step
toward more effective, efficient and general graph matching.

##  1 Introduction

Graph Matching (GM) refers to the process of establishing a correspondence
between the nodes of two graphs based on their structure and node attributes
Yan et al. (2016); Zanfir and Sminchisescu (2018), and entails various
applications. In pattern recognition Shokoufandeh et al. (2012), graph
matching facilitates the alignment of visual patterns within images Wang et
al. (2018). In bioinformatics Krissinel and Henrick (2004), it is crucial for
understanding protein-protein interaction networks Zaslavskiy et al. (2009).
In social networks, aligning user profiles and their connections is essential
for understanding social behaviors Zhang et al. (2018).

Despite the widespread applications of graph matching, prevailing methods such
as BBGM Rolínek et al. (2020) and NGM Wang et al. (2021) heavily depend on the
supervised learning paradigm, which requires a large number of label to
annotate the node correspondence across graphs. To avoid the costly labeling
effort, self-supervised learning (SSL) on graphs Peng et al. (2020); Zeng and
Xie (2021) becomes a practical alternative. Different from supervised
learning, SSL exploits label-free graphs to model intrinsic graph properties
general to an application domain, which guides the learning of node
representations amenable to graph matching. While label-free graphs are often
abundant or easy to obtain, existing SSL-based approaches for graph matching
often assume the availability of additional side information besides graphs.
On the one hand, approaches like GANN Wang et al. (2023) and IA-SSGM Guo et
al. (2023) still require graph pairs that are potentially matchable as
training data, although they do not need exact annotations on node
correspondence. The potentially matchable graph pairs are typically sampled
from the same category, under the assumption that graph pairs from distinct
categories involve totally different kinds of nodes and cannot be matched.
Hence, such approaches require extra categorical information, which can be
considered as a form of weak supervision. On the other hand, SCGM Liu et al.
(2022) requires raw image as input in order to perform augmentation,
leveraging additional image features in visual applications, and thus cannot
be generalized to graph matching in non-visual domains. Additionally, image
features may not be available for privacy or commercial considerations.

Thus, toward more general graph matching, an immediate challenge arises: Is it
feasible to employ SSL for graph matching without relying on any side
information? To address this, we develop a Graph-centric Contrastive framework
for Graph Matching (GCGM), using a _large pool_ of graph augmentations to
compensate for the lack of any side information. As a form of SSL, contrastive
learning (CL) Wu et al. (2018); Chen et al. (2020) regards corresponding/non-
corresponding nodes from two different views of the same graph as
positive/negative pairs, where a graph can be augmented in different ways to
generate different views Hassani and Khasahmadi (2020). For robustness, we
consider both structure- and feature-space augmentations. First, the
structure-space augmentations include edge removal, node dropping, and node
replacement, etc., which alter the structure of the graph, thereby improving
matching against structure variations. Second, the feature-space augmentations
include feature masking and scaling, which manipulate nodes features, thereby
improving matching against feature variations. Generally speaking, each type
of augmentation focuses on a specific kind of variation across graphs to
enhance a specific aspect of matching capability. Moreover, each type of
augmentation (e.g., node dropping) in fact entails a family of augmentations
defined by some hyperparameters (e.g., probability of dropping a node) to vary
the difficulty levels within each type. Together, we form a large,
comprehensive pool of augmentations to improve the robustness of graph
matching.

However, given a comprehensive pool of graph augmentations, a second challenge
follows: How do we select the most effective augmentations for graph matching?
The pool of graph augmentations includes various types of structure- and
feature-space augmentations, and each type can instantiate a family of
augmented views by tuning the hyperparameters of that type. In existing graph
contrastive learning, hyperparameter tuning for each type of augmentation is
the prevailing solution You et al. (2020), which can be expensive and tends to
overfit. A few automated methods exist in selecting the right type of
augmentations. JOAO You et al. (2021) always exploits the most challenging
augmentation w.r.t. the current loss, while recent research Cai et al. (2020);
Robinson et al. (2021); Wang and Liu (2021) finds that the hardest instances
are not necessarily the best for learning. Meanwhile, GCA Zhu et al. (2021)
adaptively augments each graph through edge removal based on node centrality
and masking unimportant node features, which requires custom design for each
type of augmentation and does not generalize to other types. To counter this
challenge, we present a Boosting-inspired Adaptive Augmentation Sampler (BiAS)
that automatically and adaptively samples graph augmentations beyond naïve
uniform sampling, providing a general solution to the otherwise expensive task
of selecting and tuning the optimal augmentations.

By addressing the challenges, we make three major contributions to graph
matching. (1) We propose GCGM, a graph-centric contrastive framework for
general graph matching, based on a large pool of graph augmentations without
the need of any labeled data or side information. (2) We introduce BiAS, an
adaptive augmentation selection strategy for GCGM, to optimize graph matching
and eliminate manual tuning effort over the pool of augmentations. (3) We
conduct experiments on both real-world and synthetic datasets, demonstrating
that our approach consistently outperforms state-of-the-art self-supervised
baselines.

##  2 Related Work

#### Deep Graph Matching

In supervised graph matching, GMN Zanfir and Sminchisescu (2018) has pioneered
the use of deep learning for GM. Subsequent research, like PCA Wang et al.
(2020), has advanced this by learning node, edge, and affinity features end-
to-end. Another notable approach is the channel-independent embedding with
Hungarian attention in deep graph matching Yu et al. (2019).

Furthermore, NGM Wang et al. (2021) extends GM to hypergraphs and multi-graph
matching (MGM). Additionally, BBGM Rolínek et al. (2020) addresses GM using
differentiable operations on combinatorial solvers. Besides, addressing
outliers and noise is crucial for obtaining accurate matches. Notably, RGM Liu
et al. (2023) introduced a reinforcement learning approach with a revocable
action scheme to counteract the impact of outliers, using a pre-trained BBGM
as a feature extractor that still requires labels.

While supervised graph matching methods have progressed using large labeled
datasets, unsupervised or self-supervised approaches have emerged to tackle
label scarcity. GANN utilizes graduated assignment mechanisms that allows for
joint MGM and clustering. SCGM introduces a two-stage contrastive learning
framework where image augmentation is essential, necessitating visual access
and limiting its use in other domains. Given the advantage of self-supervised
learning, our research primarily benchmarks against these approaches in the
evolving landscape of graph matching.

#### Graph Contrastive Learning

Graph learning has advanced significantly with the advent of graph neural
networks (GNNs) Veličković et al. (2017) and the introduction of contrastive
learning methods Chen et al. (2020), leading to the novel concept of graph
contrastive learning (GCL) You et al. (2020). As a major branch of self-
supervised learning, GCL enhances the representation of nodes Tan et al.
(2022), edges Li et al. (2023), and entire graphs Peng et al. (2020) by
contrasting corrupted views augmented by different graph augmentations Xu et
al. (2022), providing superior performance to traditional graph learning
techniques. However, these approaches face the challenge of designing
effective augmentations, which may involve custom designs or extensive
hyperparameter tuning You et al. (2020); Zhao et al. (2021), posing a
significant overhead.

Figure 1: Framework of the proposed GCGM with BiAS. (a) Pre-training: Each
graph $\mathcal{G}$ in the training set is augmented by sampling augmentation
pairs from a large pool, guided by the BiAS strategy. (To be clear, we only
show one training graph here; the same augmentation process is applied to
every graph in the training set.) (b) Inference: The pre-trained model is
frozen and applied to unseen graph pairs.

##  3 Proposed Method

In this section, we introduce our GCGM framework, starting with the overall
framework and preliminaries, followed by our augmentation designs and adaptive
sampling strategy.

###  3.1 Overall Framework

#### Pre-training

Fig. 1(a) depicts the self-supervised pre-training phase. The illustrated
augmentation process is applied across all graphs in the entire training set.

Specifically, for each graph $\mathcal{G}=\\{\mathbf{X},\mathbf{A}\\}$ in a
batch during pre-training, defined by node features
$\mathbf{X}\in\mathbb{R}^{N\times F}$ and the adjacency matrix $\mathbf{A}$,
we sample a augmentation pair $(\tau_{j},\tau_{k})$ based on their weights
w.r.t. the current mini-batch, from a randomly initialized augmentation pairs
pool as shown in Fig. 1(a)(i). Through graph augmentation, we produce two
distinct views of each input graph: $\tilde{\mathcal{G}}^{A}$ and
$\tilde{\mathcal{G}}^{B}$, with $N_{A}$ and $N_{B}$ nodes respectively, which
will then be processed by an graph encoder, capturing both local and global
graph patterns. Node embeddings are then refined through the node-level
contrastive strategy, optimizing the embedding by matching congruent nodes
across views and differentiating non-correspondence nodes. Finally, the
encoded embeddings will be processed by the subsequent affinity learning
module and GM solver to produce the predicted matching matrix
$\hat{\mathbf{G}}\in\mathbb{R}^{N_{A}\times N_{B}}$.

Enhancing this workflow, as illustrated in Fig. 1(a)(ii), our BiAS technique
dynamically updates the weights of the augmentation pair according to the
matching accuracy between the two corresponding augmented views. This
adjustment influences the sampling probability for subsequent mini-batches. By
doing so, BiAS adaptively samples challenging augmentations tailored for GM,
mitigating the necessity for exhaustive hyperparameter tuning and augmentation
pool selection.

#### Inference

In the inference phase, as shown in Fig. 1(b), we apply the pre-trained, now-
frozen graph encoder and affinity learning module to unseen graph pairs. The
GM solver predicts the matching matrix, which determines the node-to-node
alignment for each input graph pair.

We will next introduce some technical preliminaries (Sect. 3.2), before
discussing our main contributions on the comprehensive pool of graph
augmentations (Sect. 3.3) and our adaptive sampler BiAS (Sect. 3.4),
respectively.

###  3.2 Preliminaries

#### Graph Encoder

During training, our proposed graph encoder takes an augmented graph
$\tilde{\mathcal{G}}$ as input to produce both node and graph-level
representations as output. Given the comprehensive graph augmentations we
carry out, it is essential to leverage information at multiple granularities
to preserve both local and global graph patterns. To achieve this, we have
opted for the commonly used GraphSAGE framework Hamilton et al. (2017) as our
base graph encoder, denoted as $f(\cdot)$ in Fig. 1. This encoder captures
both local node-level embedding $\tilde{\mathbf{h}}_{v}$ using GraphSAGE
layers with skip connections, and global graph-level embedding
$\tilde{\mathbf{h}}_{\tilde{\mathcal{G}}}$ via a readout function. The node-
and graph-level embeddings are then utilized for the affinity learning and GM
solver modules, to be elaborated next. For detailed specifications of the
encoding function $f(\cdot)$, refer to Appendix A.

#### Affinity Learning and GM Solver

On one hand, the affinity learning module accepts these embeddings from the
two views (graphs) as input and generates an affinity matrix, containing the
pairwise affinity scores between the nodes from the two views. Subsequently,
the GM solver leverages the affinity matrix to determine the node
correspondence across the two graphs. We will use the affinity learning module
and GM solver following previous work Rolínek et al. (2020); Wang et al.
(2021).

#### Contrastive Loss

After processing the two augmented views of the graph through our encoder, as
depicted in Fig. 1(a), we employ a contrastive framework to learn node
embeddings. Adapting from GRACE Zhu et al. (2020), we employ both intra-view
and inter-view contrastive objectives to enhance the comparison and alignment
of nodes between distinct graph views.

First, the intra-view contrastive objective aims to differentiate anchor nodes
from other nodes within the same view by maximizing their dissimilarity.
Specifically, in view $\tilde{\mathcal{G}}^{A}$ with $N_{A}$ nodes, the
dissimilarity between the anchor node ${v}^{A}_{i}$ with feature
$\tilde{\mathbf{h}}_{i}^{A}$ and the negative nodes is

$\textstyle\ell^{A}_{\text{intra}}(v_{i})=\sum_{j=1;j\neq
i}^{N_{A}}\exp\left(\operatorname{sim}\left(g(\tilde{\mathbf{h}}_{i}^{A}),g(\tilde{\mathbf{h}}_{j}^{A})\right)/T\right),$
(1)

where $\operatorname{sim}(\cdot,\cdot)$ denotes cosine similarity,
$g(\cdot):\mathbb{R}^{d_{h}}\to\mathbb{R}^{d^{\prime}_{h}}$ is a non-linear
projection head, and $T$ is the temperature hyperparameter. This approach
ensures that distinct nodes within the same view become dissimilar.

Second, our inter-view contrastive objective, operating across distinct
augmented views $\tilde{\mathcal{G}}^{A}$ and $\tilde{\mathcal{G}}^{B}$,
maximizes the similarity of corresponding nodes across views while minimizing
that of an anchor node and all other nodes in the opposite view. We first sum
up the similarities across all inter-view pairs, centered around the anchor
node in view $\tilde{\mathcal{G}}^{A}$:

$\textstyle\ell^{A}_{\text{inter}}(v_{i})=\sum_{j=1}^{N_{B}}\exp\left(\operatorname{sim}\left(g(\tilde{\mathbf{h}}_{i}^{A}),g(\tilde{\mathbf{h}}_{j}^{B})\right)/T\right).$
(2)

Integrating both intra- and inter-view objectives based on the NT-Xent loss
Chen et al. (2020), the contrastive loss for an anchor node is

$\textstyle\ell^{A}_{i}=-\log\frac{\exp\left(\operatorname{sim}\left(g(\tilde{\mathbf{h}}_{i}^{A}),g(\tilde{\mathbf{h}}_{i}^{B})\right)/T\right)}{\ell^{A}_{\text{intra}}(v_{i})+\ell^{A}_{\text{inter}}(v_{i})}.$
(3)

The total contrastive loss averages across all anchor nodes in the two views:

$\displaystyle\textstyle\mathcal{L}_{\text{node
}}=\frac{1}{N_{A}+N_{B}}\left(\sum_{i=1}^{N_{A}}\ell_{i}^{A}+\sum_{i=1}^{N_{B}}\ell_{i}^{B}\right).$
(4)

In essence, our contrastive strategy attempts to align corresponding nodes in
the two views to achieve graph matching.

#### Graph Matching Loss

While our contrastive loss refines individual node representations, our
approach recognizes the importance of holistic graph matching. To this end, we
incorporate a graph matching loss $\mathcal{L}_{\text{match}}$. This loss
bridges the gap between our predicted matching matrix, $\hat{\mathbf{G}}$, and
a self-labeled ground-truth matching matrix $\mathbf{G}^{\text{self}}$.
$\mathbf{G}^{\text{self}}$ can be readily determined without supervision, as
$\tilde{\mathcal{G}}^{A}$ and $\tilde{\mathcal{G}}^{B}$ originate from the
same input graph.

$\mathcal{L}_{\text{match}}=\mathcal{L}\left(\hat{\mathbf{G}},\mathbf{G}^{\text{self}}\right)$
(5)

The specific GM solver used determines the form of the loss: a permutation
loss for NGM Wang et al. (2021), or a Hamming loss for BBGM Rolínek et al.
(2020).

Our overall loss
$\mathcal{L}=\mathcal{L}_{\text{node}}+\mathcal{L}_{\text{match}}$ combines
contrastive loss and graph matching loss, ensuring that the overall graph
representations are optimized for graph matching tasks.

(a)

(b)

(c)

(d)

Figure 2: Graph augmentation: (a) input graph; (b) node insertion; (c) node
replacement; (d) edge removal. The blue node represents the inserted node, and
the dotted edge indicates the added edge.

###  3.3 Comprehensive Graph Augmentations

Appropriate graph augmentations are crucial for the success of contrastive
learning toward general graph matching. As illustrated in Fig. 1(a), we
propose to select from a comprehensive pool of augmentation pairs to generate
two views for each input graph. While existing methods often adopt a small
number of standard augmentations, we argue that, in the absence of side
information for graph matching, we need to formulate a comprehensive pool of
augmentations for robustness. In particular, we not only focus on a diverse
range of augmentation types to improve different aspects of matching, but also
expand each augmentation type into a family of augmentations with varying
difficulty levels. In the following, we first introduce different types of
augmentations; then, we discuss the construction of the pool of paired
augmentations for contrastive learning.

#### Types of Augmentation

We introduce four major graph augmentation types to robustly handle real-world
matching scenarios, most notably the complexities in managing outliers, noises
Cho et al. (2014) and high-order structures. The first three types operate in
the structure space, while the last one operates in the feature space.

_Node Insertion (NI)._ Recognizing outliers, or nodes that are exclusive to
only one of the graph in a candidate matching pair, is a crucial aspect for
graph matching. Inspired by node addition in contrastive learning for graph
classification Zeng and Xie (2021), we propose a node insertion strategy to
simulate outliers. As shown in Fig. 2(b), given a randomly selected subset of
nodes from the original input graph, we aggregate their features to construct
a dummy node (e.g., $v_{d}^{1}$) and randomly link it to randomly chosen nodes
not in the given subset. The augmented graph view with the dummy nodes can
provide contrastive samples to learn outliers.

_Node Replacement (NR)._ This is a variant of node insertion, to simulate the
matching scenario where there can still be outliers even though the total
number of nodes are the same in a candidate pair. As illustrated in Fig. 2(c),
we first drop some nodes randomly from the original graph (e.g., $v_{1}$,
$v_{3}$) along with their incident edges, and then insert an equal number of
dummy nodes (e.g., $v_{d}^{1}$, $v_{d}^{2}$) following the node insertion
strategy above.

_Edge Removal (ER)._ In many real-world graphs, first-order connections (i.e.,
edges to one-hop neighbors) are often noisy or sparse. This limitation can be
alleviated by considering high-order structural connectivity or node features.
To recognize node correspondences without overly relying on first-order
connections, we adopt an edge removal strategy Hassani and Khasahmadi (2020).
As shown in Fig. 2(d), a subset of edges (e.g., $v_{3}$–$v_{4}$) is randomly
removed from the graph, which encourages the model to focus more on the high-
order connections (e.g., $v_{3}$–$v_{5}$–$v_{4}$) or invariant features.

_Feature Scaling (FS)._ Node features in graphs can exhibit significant
variability and contain considerable noises. To address this, we present two
feature scaling techniques Laskin et al. (2020). First, node features are
scaled using a univariate random variable, such that all dimensions of the
feature vector of the same node are scaled by the same factor. Second, we
apply a multivariate random variable, such that different scaling factors can
be applied to different dimensions.

In addition to above four major types of augmentations designed to deal with
different matching scenarios, we further adopt a series of standard graph
augmentations aimed to capture general graph properties that are widely used
in previous work. We summarize the four major of augmentations used in our
approach in Tab. 1; the additional types of augmentation are in Appendix B.
Note that each type of augmentation is also associated with one or more
hyperparameters, adjusting which can instantiate different augmentations with
variable difficulty. Additionally, we introduce a special type
$\tau_{\varnothing}$ that does nothing, which enables us to generate a view
using the the original graph.

Formally, let $\mathcal{T}$ denote the set of augmentation types including
$\tau_{\varnothing}$. Further define $\mathcal{I}_{\tau}$ as the set of
augmentations that can be instantiated from type $\tau\in\mathcal{T}$, by
sampling different hyperparameter values associated with $\tau$. Hence, the
full set of augmentations under consideration is
$\mathcal{I}=\cup_{\tau\in\mathcal{T}}\mathcal{I}_{\tau}$.

Type | Matching scenario | Hyperparameters
---|---|---
NI |  node outlier (unequal node count in two views) |  $p_{\text{ni}}\in[0.1,0.9]$: fraction of nodes inserted; $k_{\text{ni}}\geq 2$: size of subset; $aggr_{\text{ni}}\in\\{\text{mean},\text{max}\\}$: aggregation function; $e_{\text{ni}}\geq 1$: number of edges inserted
NR |  node outlier (equal node count in two views) |  $p_{\text{nr}}\in[0.1,0.9]$: fraction of nodes replaced; $k_{\text{nr}}\geq 2$: size of subset; $aggr_{\text{nr}}\in\\{\text{mean},\text{max}\\}$: aggregation function; $e_{\text{nr}}\geq 1$: number of edges inserted
ER |  sparse/noisy first- order connections | $p_{\text{er}}\in[0.1,0.9]$: probability of each edge being removed
FS |  feature variations & noises |  $\alpha\in[0.2,0.8]$: lower bound of uniform distribution; $\beta\in[1.2,1.8]$: upper bound of uniform distribution

Table 1: Details of the four major types of graph augmentation.

#### Pool of Paired Augmentations

As illustrated in Fig. 1(a)(i), given an input graph, we generate two
augmented views of the graph by applying a pair of augmentations. Existing
graph contrastive learning approaches mostly employ well-tuned hyperparameters
for every augmentation type. However, given a large number of augmentation
types and associated hyperparameters, extensive tuning can be combinatorially
costly and tends to overfit. Moreover, recent research shows Cai et al. (2020)
that training can often benefit from samples of variable difficulty level. In
our case, as the difficulty of augmentation is controlled by its associated
hyperparameters, it is not ideal to only rely on one set of tuned
hyperparameters.

In our approach, given an input graph, we propose to apply a pair of
augmentations sampled from $\mathcal{P}$, the pool of all possible pairs. Most
generally, we can define $\mathcal{P}=\mathcal{I}^{2}$, i.e., the Cartesian
product of $\mathcal{I}$ with itself, where $\mathcal{I}$ is the set of all
augmentations. However, we exclude two special cases: (1) Both augmentations
in the pair belong to the $\tau_{\varnothing}$ type, since both views being
the original graph does not form a meaningful contrastive example; (2) both
belong to the mixup type following earlier work Liu et al. (2022) which tends
to give poor empirical performance.

###  3.4 Sampling Augmentation Pairs via BiAS

Given a pool of augmentation pairs $\mathcal{P}$, we sample a pair to be
applied to each input graph to form the contrastive example for training.
Adopting a uniform sampler is the most straightforward approach, but its
disadvantage is twofold. First, it does not distinguish the importance of
different augmentations; second, it is static and task irrelevant, which does
not adapt to the fluctuations in training.

In our GCGM framework, we propose BiAS, a Boosting-inpired Adaptive
Augmentation Sampler. As the name suggests, BiAS is adaptive to training
fluctuations, inspired by the boosting technique Schapire (1999) in ensemble
learning that iteratively refines weak learners by focusing on more difficult
examples. Specifically, augmentation pairs that result in subpar matching
performance in a mini-batch during training are marked as difficult,
suggesting that the model needs further adaptation to data variations
introduced by such augmentations. These challenging augmentation pairs
subsequently receive more frequent sampling by increasing their probability.
Conversely, pairs that can be solved effortlessly with high accuracy are
deemed easy and are less frequently sampled in the following mini-batches.
Essentially, this strategy biases toward certain augmentations dynamically,
addressing the drawbacks of a uniform sampler.

Formally, we introduce a weight updating scheme to dynamically adjust the
sampling probability of each augmentation pair from the pool $\mathcal{P}$, as
illustrated in Fig. 1(a)(ii). Specifically, each augmentation pair
$i\in\mathcal{P}$ is associated with a weight $w_{t}^{i}$ in the $t$-th mini-
batch. The weight is updated in the next mini-batch as follows.

$w_{t+1}^{i}=\lambda w_{t}^{i}+(1-\lambda)e^{\alpha(1-\phi_{t}^{i})},$ (6)

where $\phi_{t}^{i}$ indicates the mean performance score for all matchings
where augmentation pair $i$ was previously applied up to the current mini-
batch $t$. In our implementation, we adopt the $F_{1}$ score as the
performance score (see Appendix E), which measures the accuracy of the
predicted matching against the contrastive self-supervision generated from the
two graph views. The hyperparameter $\alpha\geq 1$ regulates the magnitude of
weight adjustment, while $\lambda\in[0,1]$ serves the purpose of momentum
update to constrain the potentially exponential increase in weights of those
very challenging pairs yielding low $\phi_{t}^{i}$ repeatedly. The weights in
the $t$-th mini-batch are then normalized into a probability distribution over
the pool of augmentation pairs $\mathcal{P}$, given by
$P_{t}(i)={w_{t}^{i}}/\sum_{j\in\mathcal{P}}w_{t}^{j}$. The initial weight
$w^{i}_{0}$ is set to $e^{\alpha}$ for all augmentation pairs, i.e., we start
with a uniform sampler.

Finally, given an input graph in the $t$-th mini-batch, we generate two views
using an augmentation pair $i\sim P_{t}(i)$ drawn from the distribution over
the pool $\mathcal{P}$. Pseudocode of our method can be found in Appendix A.

In summary, BiAS offers an adaptive strategy to choose the right
augmentations. Compared to the uniform sampling strategy, BiAS dynamically
selects the most useful augmentation pairs in each mini-batch during training.
Compared to the conventional approach of tuning the hyperparameters of each
augmentation type, BiAS is much cheaper and can benefit from a wider range of
augmentations.

##  4 Experiment

In this section, we empirically evaluate the proposed model GCGM and BiAS.

###  4.1 Experiment Setup

#### Datasets

We tested three real-world datasets. (1) Pascal VOC Bourdev and Malik (2009);
Everingham et al. (2010) includes images from 20 classes; (2) Willow Cho et
al. (2013) offers 256 images over five classes; (3) SPair-71k Min et al.
(2019) has 70,958 image pairs across 18 classes. Besides, we followed a recent
work Liu et al. (2023) to generate a synthetic dataset from random 2D node
coordinates for the general non-visual domain. All graphs are constructed
based on Delaunay triangulation. More dataset details are presented in
Appendix C.

#### Baselines

We assessed the performance of GCGM against diverse baselines, including
supervised, learning-free, and unsupervised methods. Our emphasis is
benchmarking against graph-centric self-supervised methods, given our
exclusion of labeled data or side information. Supervised methods included
cutting-edge techniques like CIE Yu et al. (2019), BBGM Rolínek et al. (2020),
and NGMv2 Wang et al. (2021). Learning-free methods included RRWM Cho et al.
(2010), IFPF Leordeanu et al. (2009), and SM Leordeanu and Hebert (2005). For
self-supervised baselines, we compared against GANN-GM Wang et al. (2023) and
SCGM Liu et al. (2022).

#### Settings and Hyperparameters

GCGM with BiAS is a generic framework that can be applied to any GM solver. To
demonstrate this, we paired them with both BBGM Rolínek et al. (2020) and
NGMv2 Wang et al. (2021). As GCGM is graph-centric, we froze the image
backbone on the visual datasets, and treated each input image solely as a
graph. Our implementation is based on ThinkMatch Wang et al. (2021), and we
kept the original configurations for both solvers. Our reported results for
supervised methods and SCGM might be slightly lower than their original papers
due to our 80:20 train-validation split from the original training set, as the
original splits lack a validation set. We repeated the splits five times using
varied random seeds. We tuned the hyperparameters of our encoder using Tree-
structured Parzen Estimator (TPE) Bergstra et al. (2011) via Optuna Akiba et
al. (2019) based on the validation set. For BiAS, we set $\lambda=0.8$,
$\alpha=3$, $|\mathcal{P}|=512$. However, for the Willow dataset, due to its
smaller size, we adjust $|\mathcal{P}|$ to 128. Early stopping was applied if
performance improvements were below the threshold $\epsilon=0.001$. Detailed
model and parameter configurations can be found in Appendix A.

For other supervised and SSL baselines, we also applied the same early
stopping criterion. On visual datasets, we allowed them to fine-tune their
visual backbone and employ visual augmentations (if any) per their original
paper. More detailed baseline settings can be found in Appendix D.

Methods | Pascal VOC | Willow | SPair-71k
---|---|---|---
Intsec | Unfilt | Intsec | Intsec | Unfilt
CIE (SUP) |  66.8$\pm$0.4 | - |  82.6$\pm$0.2 |  69.3$\pm$0.3 | -
BBGM (SUP) |  77.3$\pm$0.1 |  55.0$\pm$0.1 |  96.2$\pm$0.1 |  77.7$\pm$0.2 |  48.4$\pm$0.2
NGMv2 (SUP) |  76.8$\pm$0.1 |  56.7$\pm$0.1 |  94.5$\pm$0.3 |  76.6$\pm$0.2 |  49.8$\pm$0.08
IPFP |  45.8$\pm$0.02 |  31.5$\pm$0.002 |  80.1$\pm$0.06 |  57.0$\pm$0.04 |  31.7$\pm$0.01
RRWM |  47.2$\pm$0.02 |  31.7$\pm$0.001 |  83.4$\pm$0.09 |  58.6$\pm$0.05 |  32.3$\pm$0.01
SM |  46.2$\pm$0.03 |  30.4$\pm$0.002 |  81.3$\pm$0.08 |  57.7$\pm$0.04 |  30.3$\pm$0.01
GANN-GM^ |  34.5$\pm$0.3 |  23.4$\pm$0.2 |  89.3$\pm$0.1 |  34.7$\pm$0.4 |  19.4$\pm$0.3
SCGM+BBGM |  54.8$\pm$0.05 |  36.6$\pm$0.04 |  93.1$\pm$0.08 |  60.2$\pm$0.05 |  34.1$\pm$0.01
SCGM+NGMv2 |  50.8$\pm$0.1 |  32.9$\pm$0.03 |  84.2$\pm$0.1 |  59.8$\pm$0.1 |  30.5$\pm$0.3
GCGM+BBGM |  56.8$\pm$0.02 |  36.2$\pm$0.01 |  94.4$\pm$0.3 |  60.6$\pm$0.1 |  35.9$\pm$0.07
GCGM+NGMv2 |  57.3$\pm$0.11 |  37.4$\pm$0.07 |  95.0$\pm$0.1 |  62.6$\pm$0.02 |  35.4$\pm$0.07

Table 2: Performance (%) on real-world datasets. Supervised methods are marked
with ‘SUP’, included for reference only. -: running exception in handling the
matching scenario. $\hat{~{}}$: self-supervised methods that require
categorical information. Bold/underlined: best/runner-up results (excluding
supervised methods).

#### Evaluation Metric

We used the $F_{1}$ score for evaluation (see Appendix E), combining precision
and recall for a balanced measure, which is vital for matching graphs with
outliers. We repeated the experiments on the five different splits described
above, and report their average and standard deviation in $F_{1}$.

###  4.2 Performance Evaluation

In our experiments, we adopted the two pairwise GM settings outlined by SCGM.
The Intersection (Intsec) setting confines keypoints (i.e., nodes) to only
those shared between the input graph pair. Meanwhile, the Unfiltered (Unfilt)
setting includes all keypoints, accounting for potential outliers and
variations in keypoint counts between graphs. Notably, the Unfiltered setting
is more challenging because of the presence of the outliers. Note that in the
case of the Willow dataset, the Intersection and Unfiltered scenarios are
equivalent due to each graph class containing 10 shared keypoints (i.e.,
nodes) without outliers. Consequently, we only report the Intersection
results. For training, we used the original graph without any filtering,
retaining all the keypoints.

#### Real-world Datasets

In Tab. 2, we present the performance evaluation on the visual datasets (see
detailed per-class results in Appendix F). We make several observations.

First, in terms of overall performance, GCGM consistently surpasses other SSL
baselines and learning-free methods. On the Willow dataset, GCGM outperforms
even some supervised methods. This result highlights the effectiveness of our
contrastive approach, especially given that the baselines are allowed to fine-
tune the visual backbone and apply image augmentations (if applicable),
whereas our GCGM is graph-centric and does not rely on these visual elements.

Second, when paired with the same GM solver, GCGM consistently outperforms the
state-of-the-art SCGM. This finding highlights the flexibility and robustness
of GCGM when working with different GM solvers. Specifically, when pairing
with NGMv2, a GNN-based solver, our approach tends to perform the best. For
brevity, in subsequent results, we default to reporting only the performance
of GCGM using the NGMv2 solver.

Third, GCGM demonstrates solid performance in both Intersection and Unfiltered
settings. In particular, the Unfiltered setting is often more challenging
given the presence of outliers. Hence, all methods give lower performance in
this setting, while GCGM continues to maintain a clear advantage.

#### Synthetic Dataset

Methods | Synthetic
---|---
Intsec | Unfilt
GANN-GM^ |  11.2$\pm$0.04 |  10.2$\pm$0.03
SCGM + BBGM |  33.5$\pm$2.0 |  24.3$\pm$1.2
SCGM + NGMv2 |  35.2$\pm$0.6 |  25.0$\pm$0.4
GCGM |  58.1$\pm$0.5 |  39.9$\pm$0.4

Table 3: Performance (%) of SSL methods on the synthetic dataset.

The performance of various SSL methods on the synthetic dataset is presented
in Tab. 3, providing a focused and fair comparison since our GCGM is self-
supervised. Note that supervised methods (CIE, BBGM and NGMv2) and learning-
free methods (IPFP, RRWM and SM) as shown in Tab. 2 are for reference only; we
report their results on the synthetic dataset in Appendix F.

In this dataset, GCGM excels over other SSL methods in both Intersection and
Unfiltered settings. It is worth noting that the performances of SCGM and
GANN-GM significantly trail behind GCGM, widening the gap observed on the
visual datasets. The reason is that the synthetic dataset does not require
visual backbone processing or visual input, making SCGM and GANN-GM unable to
exploit the visual aspects in their original design. Hence, they tend to
perform poorly in general graph matching outside the visual domain. In
contrast, our GCGM is graph-centric and does not rely on visual information,
lending to its effectiveness and robustness in general graph matching.

###  4.3 Ablation and Model Analyses

#### Effect of Graph Augmentations

Augmentation Set | Pascal VOC | Willow | SPair-71k | Synthetic
---|---|---|---|---
Intsec | Unfilt | Intsec | Intsec | Unfilt | Intsec | Unfilt
$\mathcal{T}\setminus$NI | 56.9 | 36.6 | 94.8 | 61.8 | 34.9 | 57.9 | 40.5
$\mathcal{T}\setminus$NR | 56.5 | 36.5 | 95.1 | 61.8 | 34.4 | 57.8 | 40.0
$\mathcal{T}\setminus$ER | 57.3 | 37.2 | 95.0 | 59.8 | 32.5 | 57.9 | 40.0
$\mathcal{T}\setminus$FS | 57.5 | 37.2 | 95.0 | 62.1 | 35.1 | 57.8 | 40.3
$\mathcal{T}$ | 57.3 | 37.4 | 95.0 | 62.6 | 35.4 | 58.1 | 39.9

Table 4: Ablation study on graph augmentations.

We explored the contribution of different types of graph augmentation, by
excluding each type from the augmentation set $\mathcal{T}$. As observed in
Tab. 4, Node Insertion (NI) and Node Replacement (NR) generally have a
significant impact on the performance, particularly on Pascal VOC and
SPair-71k. For the synthetic dataset, the two augmentation types appear not
useful. A potential reason is that the node features are generated randomly,
which means the feature differences between outliers and inliers are less
significant. Thus, NI and NR can help less on the synthetic dataset. On the
other hand, excluding Edge Removal (ER) and Feature Scaling (FS) generally
results in a slight performance dip. In particular, ER appears to be the most
useful to SPair-71k, due to the significant variability in viewpoint and scale
in this dataset, as compared to other datasets Min et al. (2019). This
variability leads to diverse geometric configurations of keypoints across
images, which impacts and alters the graph structures formed. By randomly
removing edges, ER encourages the model to focus on invariant features over
variable graph structures, which is important on SPair-71k.

#### Effect of BiAS and Augmentation Pool

Tab. 5 compares the performance of GCGM under different strategies for
selecting augmentations. In the first category including ‘Random’, ‘Tuning’
and ‘Tuning + BiAS’, we only adopt one hyperparameter setting for each
augmentation type. In ‘Random’, the hyperparameters of an augmentation type
are initialized randomly, whereas in ‘Tuning’ or ‘Tuning + BiAS’, they are
selected via 100 trials of TPE based on validation performance. Furthermore,
‘Random’ and ‘Tuning’ applies a uniform sampler when selecting the
augmentation pair in each mini-batch, whereas ‘Tuning + BiAS’ applies our BiAS
sampler. In the second category including ‘Uniform’ and ‘BiAS’, we do not rely
on just one set of hyperparameters for each augmentation type. As discussed in
Sect. 3.3, we instantiate a family of augmentations from each type with
different hyperparameter settings. In each mini-batch, we select an
augmentation pair from all pairs of instantiations using either the uniform or
BiAS sampler.

In terms of performance, we observe that ‘Tuning’ generally outperforms
‘Random’, implying that hyperparameter settings are important to each
augmentation type. Moreover, ‘Tuning + BiAS’ generally improves over ‘Tuning’,
and ‘BiAS’ consistently improves over ‘Uniform’, highlighting the
effectiveness of the BiAS sampler. Furthermore, using a large pool of
augmentation pairs can compensate for the lack of hyperparameter tuning, as
evident from the improvements made by ‘Uniform’ and ‘BiAS’ w.r.t. ‘Random’.

In terms of time cost, ‘Tuning’ and ‘Tuning + BiAS’ fare poorly due to the
need of hyperparameter tuning. Yet, their performance rarely surpasses BiAS.
On the other hand, the time cost of BiAS is two orders of magnitude smaller
than tuning-based methods, and simultaneously achieves the best or near-best
performance. It is also worth-noting that the weight updating strategy in BiAS
incurs a negligible overhead, taking similar training time as ‘Random’ or
‘Uniform’ while achieving better results.

In summary, BiAS offers a robust solution for selecting optimal augmentations,
yet without the significant time overhead required by the tuning-based
methods.

Settings | $\mathcal{P}$ | Pascal VOC | Willow | SPair-71k
---|---|---|---|---
Intsec | Unfilt | Time/h | Intsec | Time/h | Intsec | Unfilt | Time/h
Random | ✗ | 55.0 | 35.9 | 0.26 | 93.8 | 0.04 | 61.4 | 35.2 | 0.38
Tuning | ✗ | 55.9 | 36.8 | 23.76 | 94.8 | 4.54 | 61.5 | 35.6 | 31.96
Tuning + BiAS | ✗ | 55.8 | 37.0 | 23.95 | 95.4 | 4.54 | 61.9 | 36.0 | 31.88
Uniform | ✓ | 56.9 | 36.7 | 0.32 | 94.7 | 0.05 | 62.0 | 34.8 | 0.35
BiAS | ✓ | 57.3 | 37.4 | 0.39 | 95.0 | 0.05 | 62.6 | 35.4 | 0.34

Table 5: Performance of different initialization of augmentations and the use
of augmentation pool. Time (hour) represents the total wall clock time spent
on tuning the augmentations (for ‘Tuning’ methods) and training the model. The
‘$\mathcal{P}$’ column indicates if a pool of augmentation pairs is used.

#### Additional Model Analyses

Additionally, we experimented our framework with varying sizes of the
augmentation pool and different combinations of the hyperparameter $\lambda$
and $\alpha$. We also investigated the effect of the individual design
elements in BiAS, namely, momentum update and performance criterion. Finally,
we compared GCGM with SCGM when the level of input information varies, to show
the robustness of our approach given minimum input. Due to space constraint,
we omit these results here, and present them in Appendix F.

##  5 Conclusion

We introduced the Graph-centric Contrastive framework for Graph Matching
(GCGM), a novel framework toward general graph matching without the need of
any side information. GCGM utilizes a comprehensive pool of graph
augmentations for self-supervised contrastive learning, which enhances
matching robustness in the absence of side information. It is further
complemented with a Boosting-inspired Adaptive Augmentation Sampler (BiAS),
which dynamically selects the challenging augmentations for optimal results
without tuning the hyperparameters associated with the augmentations.
Together, through our experiments GCGM with BiAS achieves superior performance
in graph matching, surpassing state-of-the-art self-supervised methods across
various domains. At the same time, it is significantly more efficient than
conventional augmentations with hyperparameter tuning.

## Acknowledgements

This research project is supported by the Ministry of Education, Singapore,
under its Academic Research Fund Tier 2 (Proposal ID: T2EP20122-0041). Any
opinions, findings and conclusions or recommendations expressed in this
material are those of the author(s) and do not reflect the views of the
Ministry of Education, Singapore.

## References

  * Akiba et al. [2019] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama.  Optuna: A next-generation hyperparameter optimization framework.  In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
  * Bergstra et al. [2011] James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl.  Algorithms for hyper-parameter optimization.  In Advances in Neural Information Processing Systems, volume 24, 2011.
  * Bourdev and Malik [2009] L. Bourdev and J. Malik.  Poselets: Body part detectors trained using 3d human pose annotations.  In International Conference on Computer Vision, pages 1365–1372, 2009.
  * Cai et al. [2020] Tiffany Tianhui Cai, Jonathan Frankle, David J Schwab, and Ari S Morcos.  Are all negatives created equal in contrastive instance discrimination?  arXiv preprint arXiv:2010.06682, 2020.
  * Chen et al. [2020] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International Conference on Machine Learning, pages 1597–1607, 2020.
  * Cho et al. [2010] Minsu Cho, Jungmin Lee, and Kyoung Mu Lee.  Reweighted random walks for graph matching.  In European Conference on Computer Vision, Part V, pages 492–505, 2010.
  * Cho et al. [2013] Minsu Cho, Karteek Alahari, and Jean Ponce.  Learning graphs to match.  In International Conference on Computer Vision, pages 25–32, 2013.
  * Cho et al. [2014] Minsu Cho, Jian Sun, Olivier Duchenne, and Jean Ponce.  Finding matches in a haystack: A max-pooling strategy for graph matching in the presence of outliers.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2083–2090, 2014.
  * Everingham et al. [2010] Mark Everingham, Luc Van Gool, Christopher KI Williams, John Winn, and Andrew Zisserman.  The pascal visual object classes (voc) challenge.  International Journal of Computer Vision, 88:303–338, 2010.
  * Guo et al. [2023] Wenqi Guo, Lin Zhang, Shikui Tu, and Lei Xu.  Self-supervised bidirectional learning for graph matching.  In AAAI Conference on Artificial Intelligence, volume 37, pages 7784–7792, 2023.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Advances in Neural Information Processing Systems, volume 30, 2017.
  * Hassani and Khasahmadi [2020] Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive multi-view representation learning on graphs.  In International Conference on Machine Learning, pages 4116–4126, 2020.
  * Krissinel and Henrick [2004] Eugene Krissinel and Kim Henrick.  Secondary-structure matching (ssm), a new tool for fast protein structure alignment in three dimensions.  Acta Crystallographica Section D: Biological Crystallography, 60(12):2256–2268, 2004.
  * Laskin et al. [2020] Misha Laskin, Kimin Lee, Adam Stooke, Lerrel Pinto, Pieter Abbeel, and Aravind Srinivas.  Reinforcement learning with augmented data.  In Advances in Neural Information Processing Systems, volume 33, pages 19884–19895, 2020.
  * Leordeanu and Hebert [2005] Marius Leordeanu and Martial Hebert.  A spectral technique for correspondence problems using pairwise constraints.  In IEEE International Conference on Computer Vision (ICCV’05) Volume 1, volume 2, pages 1482–1489, 2005.
  * Leordeanu et al. [2009] Marius Leordeanu, Martial Hebert, and Rahul Sukthankar.  An integer projected fixed point method for graph matching and map inference.  In Advances in Neural Information Processing Systems, volume 22, 2009.
  * Li et al. [2023] Jintang Li, Ruofan Wu, Wangbin Sun, Liang Chen, Sheng Tian, Liang Zhu, Changhua Meng, Zibin Zheng, and Weiqiang Wang.  What’s behind the mask: Understanding masked graph modeling for graph autoencoders.  In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1268–1279, 2023.
  * Liu et al. [2022] Chang Liu, Shaofeng Zhang, Xiaokang Yang, and Junchi Yan.  Self-supervised learning of visual graph matching.  In European Conference on Computer Vision, pages 370–388, 2022.
  * Liu et al. [2023] Chang Liu, Zetian Jiang, Runzhong Wang, Lingxiao Huang, Pinyan Lu, and Junchi Yan.  Revocable deep reinforcement learning with affinity regularization for outlier-robust graph matching.  In International Conference on Learning Representations, 2023.
  * Min et al. [2019] Juhong Min, Jongmin Lee, Jean Ponce, and Minsu Cho.  Spair-71k: A large-scale benchmark for semantic correspondence.  arXiv prepreint arXiv:1908.10543, 2019.
  * Peng et al. [2020] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang.  Graph representation learning via graphical mutual information maximization.  In ACM The Web Conference, pages 259–270, 2020.
  * Robinson et al. [2021] Joshua Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive learning with hard negative samples.  In International Conference on Learning Representations, 2021.
  * Rolínek et al. [2020] Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius.  Deep graph matching via blackbox differentiation of combinatorial solvers.  In European Conference on Computer Vision, Part XXVIII, pages 407–424, 2020.
  * Schapire [1999] Robert E. Schapire.  A brief introduction to boosting.  In International Joint Conference on Artificial Intelligence, page 1401–1406, San Francisco, CA, USA, 1999. Morgan Kaufmann Publishers Inc.
  * Shokoufandeh et al. [2012] A Shokoufandeh, Y Keselman, M Fatih Demirci, D Macrini, and Sven Dickinson.  Many-to-many feature matching in object recognition: a review of three approaches.  IET Computer Vision, 6(6):500–513, 2012.
  * Tan et al. [2022] Zhen Tan, Kaize Ding, Ruocheng Guo, and Huan Liu.  Supervised graph contrastive learning for few-shot node classification.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 394–411, 2022.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * Wang and Liu [2021] Feng Wang and Huaping Liu.  Understanding the behaviour of contrastive loss.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2495–2504, 2021.
  * Wang et al. [2018] Qianqian Wang, Xiaowei Zhou, and Kostas Daniilidis.  Multi-image semantic matching by mining consistent features.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 685–694, 2018.
  * Wang et al. [2020] Runzhong Wang, Junchi Yan, and Xiaokang Yang.  Combinatorial learning of robust deep graph matching: an embedding based approach.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(6):6984–7000, 2020.
  * Wang et al. [2021] Runzhong Wang, Junchi Yan, and Xiaokang Yang.  Neural graph matching network: Learning lawler’s quadratic assignment problem with extension to hypergraph and multiple-graph matching.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5261–5279, 2021.
  * Wang et al. [2023] Runzhong Wang, Junchi Yan, and Xiaokang Yang.  Unsupervised learning of graph matching with mixture of modes via discrepancy minimization.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(8):10500–10518, 2023.
  * Wu et al. [2018] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin.  Unsupervised feature learning via non-parametric instance discrimination.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3733–3742, 2018.
  * Xu et al. [2022] Xovee Xu, Fan Zhou, Kunpeng Zhang, and Siyuan Liu.  Ccgl: Contrastive cascade graph learning.  IEEE Transactions on Knowledge and Data Engineering, 35(5):4539–4554, 2022.
  * Yan et al. [2016] Junchi Yan, Xu-Cheng Yin, Weiyao Lin, Cheng Deng, Hongyuan Zha, and Xiaokang Yang.  A short survey of recent advances in graph matching.  In ACM on International Conference on Multimedia Retrieval, pages 167–174, 2016.
  * You et al. [2020] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  In Advances in Neural Information Processing Systems, volume 33, pages 5812–5823, 2020.
  * You et al. [2021] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang.  Graph contrastive learning automated.  In International Conference on Machine Learning, pages 12121–12132, 2021.
  * Yu et al. [2019] Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li.  Learning deep graph matching with channel-independent embedding and hungarian attention.  In International Conference on Learning Representations, 2019.
  * Zanfir and Sminchisescu [2018] Andrei Zanfir and Cristian Sminchisescu.  Deep Learning of Graph Matching.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2684–2693, 2018.
  * Zaslavskiy et al. [2009] Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert.  Global alignment of protein–protein interaction networks by graph matching methods.  Bioinformatics, 25(12):i259–1267, 2009.
  * Zeng and Xie [2021] Jiaqi Zeng and Pengtao Xie.  Contrastive self-supervised learning for graph classification.  In AAAI Conference on Artificial Intelligence, volume 35, pages 10824–10832, 2021.
  * Zhang et al. [2018] Jing Zhang, Bo Chen, Xianming Wang, Hong Chen, Cuiping Li, Fengmei Jin, Guojie Song, and Yutao Zhang.  Mego2vec: Embedding matched ego networks for user alignment across social networks.  In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 327–336, 2018.
  * Zhao et al. [2021] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah.  Data augmentation for graph neural networks.  In AAAI Conference on Artificial Intelligence, volume 35, pages 11015–11023, 2021.
  * Zhu et al. [2020] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Deep graph contrastive representation learning.  arXiv preprint arXiv:2006.04131, 2020.
  * Zhu et al. [2021] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Graph Contrastive Learning with Adaptive Augmentation.  In ACM The Web Conference, pages 2069–2080, April 2021.