# SelfGraphVQA: A Self-Supervised Graph Neural Network for Scene-based
Question Answering

Bruno Souza
University of Campinas
<EMAIL_ADDRESS>Work carried out as Guest Researcher at UiO. Marius
Aasan
University of Oslo
<EMAIL_ADDRESS>Helio Pedrini
University of Campinas
<EMAIL_ADDRESS>Adín Ramírez Rivera
University of Oslo
<EMAIL_ADDRESS>
###### Abstract

The intersection of vision and language is of major interest due to the
increased focus on seamless integration between recognition and reasoning.
Scene graphs (SGs) have emerged as a useful tool for multimodal image
analysis, showing impressive performance in tasks such as Visual Question
Answering (VQA). In this work, we demonstrate that despite the effectiveness
of scene graphs in VQA tasks, current methods that utilize idealized annotated
scene graphs struggle to generalize when using predicted scene graphs
extracted from images. To address this issue, we introduce the SelfGraphVQA
framework. Our approach extracts a scene graph from an input image using a
pre-trained scene graph generator and employs semantically-preserving
augmentation with self-supervised techniques. This method improves the
utilization of graph representations in VQA tasks by circumventing the need
for costly and potentially biased annotated data. By creating alternative
views of the extracted graphs through image augmentations, we can learn joint
embeddings by optimizing the informational content in their representations
using an un-normalized contrastive approach. As we work with SGs, we
experiment with three distinct maximization strategies: node-wise, graph-wise,
and permutation-equivariant regularization. We empirically showcase the
effectiveness of the extracted scene graph for VQA and demonstrate that these
approaches enhance overall performance by highlighting the significance of
visual information. This offers a more practical solution for VQA tasks that
rely on SGs for complex reasoning questions.

††To appear in Vision-and-Language Algorithmic Reasoning Workshop at ICCV 2023

##  1 Introduction

The successful execution of Visual Question Answering (VQA) relies on a
comprehensive understanding of the scene, including spatial interrelationships
and reasoning inference capabilities [1, 14]. Incorporating scene graph (SG)
representations in SG-VQA tasks has shown promising outcomes [16, 13, 18, 32,
25], providing concise representations of complex spatial and relational
information.

Earlier investigations into SG-VQA demonstrated that successful models
primarily rely on the utilization of manually annotated scene graphs for
training [20, 21, 25], resulting in remarkably high levels of accuracy on the
GQA dataset [14], surpassing human performance by a significant margin (see
Table 1).

Despite the promising results, we argue that utilizing pre-annotated SGs in
VQA is impractical in the real world due to its labor-intensive nature. Also,
it permits a wide range of semantically corresponding SG [12] and when
annotated it could potentially introduce questions-related biases, giving rise
to concerns about its generalizability [2]. These issues may limit the model’s
ability to solve real-world problems beyond the dataset [23]. This is evident
in a significant decline in accuracy, approximately 60% when models are
confronted with automatically generated SGs. Additionally, studies assert that
the main limitation in generalizing stems largely from linguistic
correlations. [2, 17].

In this study, we address these challenges by extracting an SG from a given
image using an unbiased, off-the-shelf scene graph generator [16], with the
aim of removing any potential information leakage, as illustrated in Fig. 1’s
structure. Furthermore, our method employs semantically preserving
augmentation, integrated with un-normalized contrastive framework, to further
mitigate potential linguistic biases to enhance the visual cues translated as
SG for VQA. We refer to it as the SelfGraphVQA framework, cf. Fig. 1.

GQIA Spurious correlation GQIG’Atimestimes How many chairs are in the room?
$f_{q}$ $g$ $g$ Wall Chair Table Toy Chair Toy Balls Floor $f_{g}$ $f_{g}$ $h$
$f_{c}$ $L^{\prime}$$L_{\mathcal{a}}$$z_{1}$$p_{1}$$z_{2}$Shared +
FrozenShared$\nabla$$\mathrel{\ooalign{\raisebox{1.0pt}{$\Large{\not}$}\hss\cr$\nabla$}}$

Figure 1: (Left) The statistical dependence of the task and the ideal graph,
$G$. (Right) Our proposed framework removes data leakage by using the
extracted SG $G^{\prime}$. Our architecture comprises a question encoder
$f_{q}$, a graph encoder $f_{g}$, and a classifier $f_{c}$. Two distinct views
of one image are processed by the same pipeline. We use a frozen pre-trained
SG generator $g$, and a prediction head $h$ is applied through the top view
with gradient backpropagation, while gradients are not propagated back from
the lower view. We maximize the representation of the views using the
similarity loss $L^{\prime}$.

Given its simplicity [7], our approach is trained using joint embeddings and a
Siamese network architecture, inspired by the SimSiam model, which does not
require negative samples [5, 9]. In this work, we explore three un-normalized
contrastive approaches (node-wise, graph-wise, and regularization for
permutation equivariance) and demonstrate its effectiveness by enhancing the
visual information for the VQA task. A graph neural network (GNN) with a self-
attention strategy (GAT) is employed to distill an SG representation relevant
to the question by capturing visual interaction content among objects in the
scene [7].

Our work differs from existing VQA models in three main aspects: (i) we
generate as SG using a pre-trained, unbiased scene graph generator [16] in a
more practical approach; (ii) we utilize un-normalized contrastive learning on
the SG representation, along with augmentation, to eliminate any potential
spurious correlations from annotated data and to heighten the visual
information; and (iii) the use of a GAT encoder to enhance high-level semantic
and spatial reasoning on the SG. We further investigate the behavior of visual
enhancement when employing a more expressive language encoder, specifically
BERT [15]. Importantly, our SelfGraphVQA framework does not require the costly
pre-training strategy common to transformer-based models commonly used in
vision-language tasks [32, 28, 8].

##  2 Related Work

Table 1: Our experiments revealed a notable accuracy reduction in top-notch
methods on the GQA dataset when transitioning from well-annotated to extracted
scene graphs. We categorize methods by data type (e.g., annotated data or
purely image-question extraction) and SGG usage. All methods are trained and
validated uniformly, except for the test extracted configuration, trained on
ideal data and validated on extracted SGG data.

Method | Eval. Data | Acc (%)
---|---|---
Human [14] | – | $89.30$
GraphVQA [20] | Annotated/SGG | $94.78$
LRTA [21] | Annotated/SGG | $93.10$
Lightweight [25] | Annotated/SGG | $77.87$
CRF [24] | Annotated | $72.10$
LXMERT [28] | Extracted | $59.80$
GraphVQA (original pre-trained on ideal) | Test Extracted/SGG | $29.7$
SelfGraphVQA (Local) | Extracted/SGG | $51.5$
SelfGraphVQA (Global) | Extracted/SGG | $52.3$
SelfGraphVQA (SelfSim) | Extracted/SGG | $54.0$

#### Scene Graph and Visual Question Answering.

Accurately assessment of VQA tasks, requiring a comprehensive understanding of
visual perception and semantic reasoning, has gained substantial attention in
the academic community, as these tasks holds significant practical value,
particularly in enhancing accessibility for the visually impaired [4, 15, 19,
34, 33].

Several works have explored the information that SG representations may bring
to VQA [31, 20], as opposed to the more data-hungry transformer-based visual
language models [28, 8, 19]. However, existing SG-VQA approaches typically
rely on idealized scene graphs and inherent dataset reasoning [21, 20].
Obtaining such annotations can be costly without an end-to-end pipeline.
Moreover, even SoTA methods in SG-VQA exhibit limited generalization
capabilities, potentially due to spurious correlations [2].

#### Self-Supervised Learning.

Broadly speaking, recent advancements in self-supervised learning can be
categorized into normalized [3, 6] and maximization representation learning
[11, 7, 29]. Contrastive methods aim to bring embeddings of identically
labelled images closer together while separating embeddings generated from
different versions. In visual-language data, the prevailing approach for self-
supervised learning involves pretraining a transformer-based model on a large
dataset to solve pretext tasks before fine-tuning for downstream tasks [32, 8,
28, 27]. However, these methods can be computationally expensive and complex
due to the use of negative samples and masking techniques. Modern un-
normalized contrastive learning methods, e.g., BYOL [11] and SimSiam [7], use
architectures inspired by reinforcement learning to maximize the informational
content of the representations. In our proposal, we adopt a similarity
maximization approach using a Siamese architecture for visual scene graph
representation.

##  3 Methodology

We refer the reader to the appendix for the implementation details. We
experiment with the maximization strategy with three independent and distinct
similarity losses over either a localized node representation (i.e., object-
wise), a global pooled graph representation (i.e., scene-wise), or a
regularization node representation term to induce permutation equivariance. We
denote the graph representations $z_{i}=f_{g}\big{(}g(x_{i}),f_{q}(q)\big{)}$,
and the predictor’s output vectors $p_{i}=h(z_{i})$. Generally, the
representations are maximized by minimizing the generic cosine distance $D$
loss.

#### Local Similarity.

To account for permutation invariance in the node representations, we compute
cosine distances over all object pairs from the two views and use the
maximally similar node embedding pairs to compute the local loss by

$L^{*}_{\mathrm{\ell}}(p_{1},z_{2})=\frac{1}{O}\sum_{i}^{O}\operatorname*{arg\,min}_{z_{2,j}}D(p_{1,i},z_{2,j}),$
(1)

where $O$ is the number of objects in the scene. Symmetrically, we compute
$L^{*}_{\mathrm{\ell}}(p_{2},z_{1})$, to obtain the overall local loss

$L_{\mathrm{\ell}}(z_{1},z_{2})=\frac{1}{2}\big{(}L^{*}_{\mathrm{\ell}}(p_{1},z_{2})+L^{*}_{\mathrm{\ell}}(p_{2},z_{1})\big{)}.$
(2)

#### Global Similarity.

After obtaining a graph representation, we follow an approach similar to
cosine similarity maximization for image classification [11, 7]. Along with
the intuition that contrasting between global representations may enhance the
visual cues, we assume that the global representation contains the full
information about the scene. Similar to the local representation, we minimize
the cosine distance, yielding a loss on the form

$L_{\mathcal{g}}(z_{1},z_{2})=\frac{1}{2}\big{(}D(p_{1},z_{2})+D(p_{2},z_{1})\big{)}.$
(3)

#### Regularization for Permutation Equivariance.

We employ an _anchor_ , where the SG of an unmodified image guides the SG of
the augmented image, allowing us to obtain a more accurate representation of
the original scene. Our assumption is that the local similarity loss decreases
the global performance, while global similarity provides a contextual
representation but loses local details. This technique aligns similar nodes
and encourages regularization, making augmented scene representations closer
to the original, thus mitigating permutation invariance in graph
representations.

Denote the anchored representation by $z_{1}$, and the augmented
representation by $z_{2}$. We determine intra-similarities of the anchors
$s_{1,i}=\operatorname*{arg\,min}_{z_{1,j}}D(z_{1,i},z_{1,j})$ and
similarities of augmented views $s_{2,ij}=D(z_{2,i},z_{2,j})$. We then compute
cross-entropy (CE) between anchors and augmentations

$J(z_{1},z_{2})=\mathrm{CE}(s_{1},s_{2}),$ (4)

which acts as a regularizer to constrain permutation equivariance for the
augmentations in addition to the local loss. We combine these losses using

$L_{\mathcal{s}}(z_{1},z_{2})=L_{\ell}(z_{1},z_{2})+J(z_{1},z_{2}),$ (5)

which we refer to as a local self-similarity loss (SelfSim).

#### Distribution Link Representation Regularization.

Similarly to the regularization for permutation equivariance, we apply link
regularization _in conjunction with one of the other three similarity
strategies_. The edges of the _anchor_ SG guide the edges of the augmented SG.
Denote the anchored edge score representation by $r_{1}$, and the augmented
edge score representation by $r_{2}$. These scores characterize the
relationship between the objects in the scene, and we aim to make the link
distribution more robust to perturbation. _In this case, the scene graph
generator[16] is trainable._ We compute the cross-entropy between the anchored
edge scores and the augmented edge scores
$J_{e}(r_{1},r_{2})=\mathrm{CE}(r_{1},r_{2})$, which acts as a regularizer to
constrain the link prediction distribution, yielding

$L_{\mathcal{e}}(z_{1},z_{2})=L_{\ell}(z_{1},z_{2})+J_{e}(r_{1},r_{2}).$ (6)

All models utilizing this added link distribution regularizer are
characterized by the inclusion of the term “link.”

#### Overall Optimization Objective.

Lastly, we outline the overall loss for optimizing the VQA objective. To
identify the correct answer $a\in A$ given an example $(x,q,A)$, where $x$
represents the input image, and $q$ is the associated question, we extract a
point estimate of probabilities

$p(a\>\lvert\>x,q)=\sigma\left(\operatorname{logit}(x)\right),$ (7)

where $\sigma$ is the softmax function, and $\operatorname{logit}(x)=f(x,q)$
are the logits for all possible answers produced by our encoder. We calculate
the cross-entropy loss for each instance,

$L_{\mathcal{sup}}(x)=\mathrm{CE}\left(p(a\>\lvert\>x,q),a\right).$ (8)

Our combined training loss is then given by

$L(x)=\alpha L_{\mathcal{sup}}(x)+\beta L^{\prime}(z_{1},z_{2}),$ (9)

where $L^{\prime}$ can be any of the aforementioned similarity loss
strategies: $L_{\ell}$, $L_{\mathcal{g}}$, or $L_{\mathcal{s}}$, with or
without $L_{\mathcal{e}}$. The $\alpha$ and $\beta$ are controlled
hyperparameters that balance the contribution of the various components in the
total loss.

##  4 Experiments and Ablations

We evaluate our framework on the GQA dataset [14]. Our study aims to establish
a practical foundation for demonstrating the potential of SG along with an un-
normalized contrasting approach to improve visual cues for VQA. Despite the
noise data in the extracted SG, we demonstrate its effectiveness, Fig.
LABEL:tab:sota, by highlighting the importance of further exploration. The
utilization of non-idealized SG-VQA methods with un-normalized contrastive
learning leads to improvements across all metrics, Table LABEL:tab:sota.
Furthermore, our framework demonstrates faster convergence during training,
approximately 20% faster in epochs compared to baselines. However, further
investigation is required to validate them.

The un-normalized contrastive approach universally enhances results across
question categories (Fig. 2), with specific types of approaches further
improving the model’s performance based on the query type.

Table 2: Results (%) on GQA by standard metrics.

Method |  Binary ($\uparrow$) |  Open ($\uparrow$) |  Consist. ($\uparrow$) |  Validity ($\uparrow$) |  Plausab. ($\uparrow$) |  Distr. ($\downarrow$) |  Acc ($\uparrow$)
---|---|---|---|---|---|---|---
Baseline | $65.8$ | $29.7$ | $58.2$ | $94.9$ | $90.5$ | $11.7$ | $50.1$
Baseline+BERT | $68.0$ | $32.2$ | $62.56$ | $95.0$ | $90.9$ | $7.7$ | $53.8$
Local | $66.80$ | $30.15$ | $59.42$ | $94.88$ | $90.61$ | $8.83$ | $51.47$
Global | $67.74$ | $30.76$ | $62.46$ | $94.9$ | $90.6$ | $6.74$ | $52.33$
SelfSim | 68.4 | $31.3$ | 65.9 | $94.9$ | $90.7$ | 2.1 | $54.0$
Global+BERT+link | $68.0$ | 33.0 | $63.9$ | $95.0$ | 91.2 | $8.9$ | 54.5
SelfSim+BERT+link | $68.2$ | $32.8$ | $64.3$ | 95.0 | $91.0$ | $8.0$ | 54.5

RelationAttributeObjectGlobalCategoryAverage$0.40$$0.45$$0.50$$0.55$$0.60$$0.65$$0.70$$0.75$$0.80$Accuracy
($\%$)BaselineBaseline+BERTGlobalGlobal+BERTSelfSimSelfSim+BERT Figure 2:
Accuracy on different question types.

We conducted ablations to demonstrate the functionality of our approach and
carried out detailed observations that go beyond mere reliance on metrics
using the GQA dataset.

#### Does the Scene Graph Really Matter?

Through a perturbation study where images were augmented based on question
types, we introduced disruptive noise such as image flipping to challenge the
model’s ability to answer spatial relational questions. The goal was to
observe mistakes in the model’s answers. The results, compared to the baseline
(Table 3), showed greater variation in our model’s performance, indicating
that it pays more attention to visual information, whereas the baseline
appears to rely on other sources of information.

Table 3: Change in accuracy under potentially disruptive augmentations and
perturbations.

Question Type | Augmentation | Baseline | Global | Local | SelfSim
---|---|---|---|---|---
Relation | Flip | $-1.6$ | $-3.37$ | $-3.24$ | $-3.89$
Attribute | Strong Color Jitter | +1.14 | $-3.72$ | $-0.76$ | $-1.15$
Global | Gaussian Noise + Crop | $-5.6$ | $-7.7$ | $-5.45$ | $-8.1$

#### Are Performance Gains Mainly Due to Augmentations?

We compared our approach with the baseline architecture, training solely with
data augmentation techniques to evaluate their influence on overall
performance. Table 4 provides evidence that data augmentation techniques
actually impair the performance of the architecture.

Table 4: Results(%) of the Aug. Baseline and SelfSim.

Method | Binary | Open | Validity | Plausibility | Acc
---|---|---|---|---|---
Baseline Aug | $65.05$ | $28.72$ | $94.62$ | $90.08$ | $50.11$
SelfSim | $68.44$ | $31.28$ | $94.9$ | $90.7$ | $54.0$

#### Are Our Models Less Biased?

Our initial hypothesis was that current top-performing models might
incorporate biases present in the questions into their weights. We conducted
experiments to analyze this issue, introducing random noise to features in the
scene graph while preserving its topology, and perturbing the language in up
to 50% of the words in the questions. The results in Table 5 demonstrate that
our approach relies less on linguistic features, prioritizing overall
information and reducing linguistic bias. Additionally, we explored visual
enhancement, even when trained with a more expressive language module such as
BERT. The experiments in Table 5 examine the impact of using BERT and its
effect on enhancing visual information.

Table 5: Sensitivity of accuracy (%) for bias question analyzes of
SelfGraphVQA and SelfGraphVQABERT.

Setup |  | Methods |  |
---|---|---|---|---
Scene Graph + Question | Baseline | Local | Global | SelfSim
Noise + SG | $16.2$ | $16.60$ | $28.6$ | $26.6$
Question + Noise | $39.93$ | $38.304$ | $37.39$ | $39.79$
Noise + Noise | $12.7$ | $14.6$ | $18.9$ | $21.0$
Question + Scene Graph | BERT Baseline | BERTGlobal+link | BERTSelfSim+link |
Noise + SG | $21.0$ | $23.2$ | $24.5$ |
Question + Noise | $42.4$ | $41.8$ | $42.8$ |
Noise + Noise | $19.8$ | $21.7$ | $21.3$ |

#### Examples.

Given the wide range of acceptable answers, we argue that solely relying on
standard evaluation metrics may not provide a fair comparison, thus presenting
additional challenges to the field. Fig. 3 demonstrates the utility of SG for
interpretability, as they enable a graphical analysis of objects and the
overall composition of the scene.

Relative | Synonym | Ambiguous
---|---|---
|  |
|  |
Q: Is there an airplane in the | Q: Where are the weeds? | Q: Is the man to the right
picture that is not small? |  | or to the left of the cup?
Answer: Yes | Answer: Plain | Answer: Right
Prediction: No | Prediction: Field | Prediction: Left

Figure 3: Examples to demonstrate the complexity of VQA.

##  5 Conclusions

Despite promising results in VQA tasks with idealized SG, our study revealed
that models relying on manually annotated and expensive SG struggle with real-
world data. To address this, we proposed SelfGraphVQA, a more practical SG-VQA
framework that breaks the spurious correlation of annotated SG and learns to
answer questions using extracted SG from a pre-trained SG generator. We
employed un-normalized contrastive learning to maximize similar graph
representations in different views. All approaches utilizing self-supervision
showed improvement over their baselines. Overall, we demonstrated the
effectiveness of extracted SG in VQA, underscoring the significance of
continued exploration of the potential of SG for complex tasks. We also showed
that self-supervision over the SG representation improved the results by
enhancing the visual information within the task. We hope that this work
raises awareness of the challenges of accentuating the role of the scene in
answering questions from images.

## Acknowledgements

This work was supported in part by the FAPESP (São Paulo Research Foundation)
grant no. 2022/09849-8 and BEPE grant no. 2022/09849-8. The computations were
performed in part on resources provided by Sigma2—the National Infrastructure
for High-Performance Computing and Data Storage in Norway—through Project
NN8104K. This work was funded in part by the Research Council of Norway, via
the Centre for Research-based Innovation funding scheme (grant no. 309439),
and Consortium Partners.

## References

  * [1] Aishwarya Agrawal, Dhruv Batra, Devi Parikh, and Aniruddha Kembhavi.  Don’t just assume; look and answer: Overcoming priors for visual question answering.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 4971–4980, 2018.
  * [2] Aishwarya Agrawal, Ivana Kajic, Emanuele Bugliarello, Elnaz Davoodi, Anita Gergely, Phil Blunsom, and Aida Nematzadeh.  Reassessing evaluation practices in visual question answering: A case study on out-of-distribution generalization.  In Conf. European Ch. Assoc. Comput. Ling. (EACL), pages 1171–1196, 2023.
  * [3] Laurence Aitchison.  InfoNCE is a variational autoencoder.  arXiv preprint arXiv:2107.02495, 2021.
  * [4] Hedi Ben-Younes, Rémi Cadene, Matthieu Cord, and Nicolas Thome.  Mutan: Multimodal tucker fusion for visual question answering.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 2612–2620, 2017.
  * [5] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah.  Signature verification using a “siamese” time delay neural network.  Adv. Neural Inf. Process. Sys. (NeurIPS), 6, 1993.
  * [6] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He.  Improved baselines with momentum contrastive learning.  arXiv preprint arXiv:2003.04297, 2020.
  * [7] Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 15750–15758, 2021.
  * [8] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu.  Uniter: Universal image-text representation learning.  In European Conf. Comput. Vis. (ECCV), pages 104–120. Springer, 2020.
  * [9] Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman, and Yann Lecun.  On the duality between contrastive and non-contrastive self-supervised learning.  arXiv preprint arXiv:2206.02574, 2022.
  * [10] Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh.  Making the V in VQA matter: Elevating the role of image understanding in visual question answering.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 6904–6913, 2017.
  * [11] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent-a new approach to self-supervised learning.  Adv. Neural Inf. Process. Sys. (NeurIPS), 33:21271–21284, 2020\.
  * [12] Xuanli He, Quan Hung Tran, Gholamreza Haffari, Walter Chang, Trung Bui, Zhe Lin, Franck Dernoncourt, and Nhan Dam.  Scene graph modification based on natural language commands.  arXiv preprint arXiv:2010.02591, 2020.
  * [13] Ronghang Hu, Anna Rohrbach, Trevor Darrell, and Kate Saenko.  Language-conditioned graph networks for relational reasoning.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 10294–10303, 2019.
  * [14] Drew A. Hudson and Christopher D. Manning.  GQA: A new dataset for real-world visual reasoning and compositional question answering.  10.48550/arxiv.1902.09506, 2019.
  * [15] Jin-Hwa Kim, Jaehyun Jun, and Byoung-Tak Zhang.  Bilinear attention networks.  Adv. Neural Inf. Process. Sys. (NeurIPS), 31, 2018.
  * [16] Boris Knyazev, Harm de Vries, Cătălina Cangea, Graham W Taylor, Aaron Courville, and Eugene Belilovsky.  Graph density-aware losses for novel compositions in scene graph generation.  arXiv preprint arXiv:2005.08230, 2020.
  * [17] Brenden Lake and Marco Baroni.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In Inter. Conf. Mach. Learn. (ICML), pages 2873–2882. PMLR, 2018\.
  * [18] Linjie Li, Zhe Gan, Yu Cheng, and Jingjing Liu.  Relation-Aware Graph Attention Network for Visual Question Answering.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 10313–10322, 2019.
  * [19] Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang.  VisualBERT: A simple and performant baseline for vision and language.  arXiv preprint arXiv:1908.03557, 2019.
  * [20] Weixin Liang, Yanhao Jiang, and Zixuan Liu.  GraghVQA: Language-guided graph neural networks for graph-based visual question answering.  In Wksp. Multimodal Artif. Intell. (ACLW), pages 79–86, Mexico City, Mexico, June 2021. Association for Computational Linguistics.
  * [21] Weixin Liang, Feiyang Niu, Aishwarya Reganti, Govind Thattai, and Gokhan Tur.  LRTA: a transparent neural-symbolic reasoning framework with modular supervision for visual question answering.  arXiv preprint arXiv:2011.10731, 2020.
  * [22] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  ViLBERT: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks.  In Adv. Neural Inf. Process. Sys. (NeurIPS), volume 32, 2019.
  * [23] Man Luo, Shailaja Keyur Sampat, Riley Tallman, Yankai Zeng, Manuha Vancha, Akarshan Sajja, and Chitta Baral.  ’just because you are right, doesn’t mean i am wrong’: Overcoming a bottleneck in the development and evaluation of open-ended visual question answering (VQA) tasks.  arXiv preprint arXiv:2103.15022, 2021.
  * [24] Binh X Nguyen, Tuong Do, Huy Tran, Erman Tjiputra, Quang D Tran, and Anh Nguyen.  Coarse-to-fine reasoning for visual question answering.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 4558–4566, 2022.
  * [25] Sai Vidyaranya Nuthalapati, Ramraj Chandradevan, Eleonora Giunchiglia, Bowen Li, Maxime Kayser, Thomas Lukasiewicz, and Carl Yang.  Lightweight visual question answering using scene graphs.  In ACM Inter. Conf. Inf. Knowl. Manag. (CIKM), pages 3353–3357, 2021.
  * [26] Jeffrey Pennington, Richard Socher, and Christopher D Manning.  GloVe: Global vectors for word representation.  In Conf. Empir. Methods Nat. Lang. Process. (EMNLP), pages 1532–1543, 2014.
  * [27] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In Inter. Conf. Mach. Learn. (ICML), pages 8748–8763. PMLR, 2021\.
  * [28] Hao Tan and Mohit Bansal.  Lxmert: Learning cross-modality encoder representations from transformers.  arXiv preprint arXiv:1908.07490, 2019.
  * [29] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Remi Munos, Petar Veličković, and Michal Valko.  Bootstrapped representation learning on graphs.  In Wksp. Geom. Topol. Represent. Learn. (ICLRW), 2021.
  * [30] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [31] Yanan Wang, Michihiro Yasunaga, Hongyu Ren, Shinya Wada, and Jure Leskovec.  VQA-GNN: Reasoning with multimodal semantic graph for visual question answering.  arXiv preprint arXiv:2205.11501, 2022.
  * [32] Zhecan Wang, Haoxuan You, Liunian Harold Li, Alireza Zareian, Suji Park, Yiqing Liang, Kai-Wei Chang, and Shih-Fu Chang.  SGEITL: Scene graph enhanced image-text learning for visual commonsense reasoning.  In AAAI Conf. Artif. Intell. (AAAI), volume 36, pages 5914–5922, 2022.
  * [33] Rowan Zellers, Jiasen Lu, Ximing Lu, Youngjae Yu, Yanpeng Zhao, Mohammadreza Salehi, Aditya Kusupati, Jack Hessel, Ali Farhadi, and Yejin Choi.  Merlot reserve: Neural script knowledge through vision and language and sound.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 16375–16387, 2022.
  * [34] Pengchuan Zhang, Xiujun Li, Xiaowei Hu, Jianwei Yang, Lei Zhang, Lijuan Wang, Yejin Choi, and Jianfeng Gao.  VinVL: Revisiting visual representations in vision-language models.  In IEEE/CVF Inter. Conf. Comput. Vis. Pattern Recog. (CVPR), pages 5579–5588, June 2021.

##  Appendix A Datasets

We evaluate our SelfGraphVQA frameworks on the GQA dataset [14]. GQA is
another large-scale effort (22M questions, each with one answer) that focuses
on the compositionality of template-generated questions for real-world images.
We use the official train/validation split of GQA.

The GQA dataset was selected for evaluation because it includes complex
relational and spatial questions that require multiple reasoning skills,
spatial understanding, and multi-step inference. These characteristics make it
more challenging compared to previous visual question-answering datasets.
Consequently, the GQA dataset is well-suited for evaluating the performance of
scene graph models.

In contrast to prior studies [24, 2], our approach takes a simplistic approach
by considering solely the ground truth distribution as a potential answer in
the training dataset as a candidate for the answer distribution, without any
filter techniques. Table A.1 provides detailed statistics for each dataset
examined in our investigation.

Table A.1: Detailed statistics for the GQA dataset examined in our study compared to other possible statistics and the original paper dataset. | Answers Candidates
---|---
Ours | 1878
Alternative [2, 22, 24] | 1533
Original [14, 10] | 1878

Despite the substantial variations in the answering classes, we emphasize that
our method proves to be effective and comparable to other existing approaches.
In addition to the aforementioned points, this further highlights the fact
that VQA is a complex and expansive challenge that lends itself to various
approaches and needs continued exploration and refinement.

##  Appendix B Baseline Architecture

Figure B.1 depicts the overall components of our baseline architecture. The
unbiased pre-trained scene graph generator model utilized in this study
originates from the research paper authored by Knyazev et al. [16]. Applying a
density-normalized edge loss to the model, the authors contend that the model
is aware of the graph density and, therefore, generalizes better even to rare
compositions.

In our project, the frozen weights pre-trained Scene Graph Generator takes the
image information and generates a scene graph representation. The Question
Encoder receives the instructions and provides them to the GNN-based encoder.
Each layer of the module pays attention to these instructions in order to
update its hidden node states. The Classifier then takes the graph
representation and the question vector concatenates them, and predicts the
correct answer.

Scene Graph Gen. $g$ Where was this photo taken? Question Encoder $f_{q}$ GNN-
based $f_{g}$ Answer Classifier $f_{c}$ Classroom Instructions decoded
Question vector representation Figure B.1: The baseline architecture.

We use the similar architecture of the state-of-the-art graph-based GraphVQA
model [20] and LRTA [21] over the GQA dataset as a baseline for our
experiments, with some modifications in order to reduce the dependence on the
annotated available data, as we aim to mitigate the limitations imposed by
data availability and enhance the model’s generalizability.

For practical purposes, the functional program instructions accompanying each
question in the GQA dataset [14] are not necessarily available for inference
on real-world data, so we train our decoder to decode the instructions from
the question itself. These additional labels are processed by the reasoning
module in the GraphVQA model which we explicitly omit in our baseline, as we
are more interested in generalizability and real-world performance rather than
expressively _solving_ the GQA dataset.

In addition, we omit the pre-processing using the scene graph encoding module
of the original GraphVQA, as the scene graph generation model $g$ was selected
to extract high quality SG-representations. Here, our $f_{g}$ module is a
graph attention network (e.g. GAT) [30].

In the GloVE embedding design, both the query encoder $f_{q}$ and the graph
encoder $f_{g}$ designs are shared between the original baseline and our
proposed modified model. Whereas in the BERT design, we only take the
similarity of the graph encoder module $f_{g}$ design, as our query encoder
$f_{q}$ and the language embedding is a BERT model. By adapting the similar
SoTA architecture strategy to the specific design choices of each model, we
aim to evaluate the performance and effectiveness of our proposed approach.

##  Appendix C Architecture Details

Within this section, we aim to provide additional details regarding all
components of our implementation approaches.

To ensure clarity and facilitate better comprehension, we have divided this
section into two subsections: one discussing the utilization of GloVE word
embedding along with a transformer-based model for the question encoder, and
the other focusing on the application of BERT for word embedding and the
question encoder.

Table C.1 provides a comprehensive overview of the two approaches employed in
this study.

It is worth mentioning that the scene graph generator module has its weights
frozen in all training approaches, except when we employ the Distribution Link
Representation Regularization technique.

###  C.1 GloVE Word Embedding and Transformer-based Question Encoder

The images are fed through a pre-trained scene graph generator $g$ from [16]
work that generates scene graphs from images on the fly.

Except for the pooled graph-level representation (i.e., the module that feeds
the classifier), which has a dimension size of $512$, all node and edge
features have dimension size $300$.

The word embedding for the transformed-based query encoder module $f_{q}$ has
its initial weights initialized by using embeddings from GloVe [26]. Both
hidden states and word embedding vectors have a dimension size of $300$. The
question representation is produced by the transformed-based question encoder.

Following [21, 20] work, we adopt a hierarchical sequence generation design,
i.e., a transformer decoder model first parses the question into a sequence of
$M$ instruction vectors, $[i_{1},i_{2},\dots,i_{M}]$. The $i$-th instruction
vector will correspond exactly to the $i$-th execution step processed by the
GNN encoder $f_{g}$ module. In our experiments, we force $M$ equals five. We
note that SelfGraphVQA does not require any explicit supervision on how to
solve the instruction step from the question, and we only supervise the final
answer prediction.

For the un-normalized contrastive approach, the MLP prediction head $h$ plays
a crucial role in our model architecture. It comprises three fully connected
layers, each followed by batch normalization and ReLU activation, except for
the final layer. This setup ensures non-linearity and facilitates effective
feature extraction. It is important to note that the MLP prediction head is
exclusively utilized during the training phase and is subsequently discarded
during inference, which aligns with prevailing practices in contemporary self-
supervised training methods [7, 11].

The classification module $f_{c}$ is another integral component of our model.
It is designed as a two-layer MLP with a dropout rate of $0.2$ and ELU
activation.

As explained in Section 3, we independently apply the three self-supervised
losses (i.e., local similarity, global similarity, and regularization for
permutation equivariance) and compared performances. Our experimental choices
were designed to minimize possible biases in the evaluation of our proposed
framework.

Both anchored and augmented scene graphs along with the question ground on the
scene feed our encoder model to infer a predicted answer. For a fair
comparison, we train most of our model from scratch, except for the pre-
trained scene graph generator $g$, whose weights are frozen.

###  C.2 BERT Word Embedding and Question Encoder

In this case, we employ the BERT model as our word embedding approach and the
question encoder, as being a more expressive language model.

Once again, the images are fed through a pre-trained scene graph generator $g$
from [16] work that generates scene graphs from images on the fly. In this
particular case, all graph-level and node-level representations possess a
dimension size of $512$, encompassing both node and edge features. This
configuration is deliberately chosen to ensure that the dimensions of the
representations closely align with the dimension yielded by BERT word
embedding, which is $756$. By maintaining consistency in the dimensionality
across different components, we aim to facilitate seamless integration and
compatibility with BERT-based models.

Table C.1: Detailed dimensions used in our study when employing the GloVE and
BERT approaches.

Methods | Word dim. | Question dim | Node Dim | Link Dim | Graph dim
---|---|---|---|---|---
GloVE+Transf | $300$ | $300$ | $300$ | $300$ | $512$
BERT | $756$ | $512$ | $512$ | $512$ | $512$

The word embedding for the BERT query encoder $f_{q}$ has its initial weights
initialized by using embeddings from BERT [15]. Both hidden states and word
embedding vectors have a dimension size of $512$. The final question
representation is derived by taking the average of all word embedding
representations generated by BERT.

Following the same approach of [21, 20], we adopt a hierarchical sequence
generation design, i.e., a transformer decoder module first parses the encoded
question into a sequence of $M$ instruction vectors,
$[i_{1},i_{2},\dots,i_{M}]$. The $i$-th instruction vector will correspond
exactly to the $i$-th execution step processed by the GNN encoder $f_{g}$
module. In our experiments, we force $M$ equals five. We note that
SelfGraphVQA does not require any explicit supervision on how to solve the
instruction step from the question, and we only supervise the final answer
prediction.

In this scenario, we employ two self-supervised loss techniques: global
similarity and regularization for permutation equivariance. Additionally, we
incorporate the Distribution Link Representation Regularization method overall
approaches performed in this case. It is important to note that the
Distribution Link Representation Regularization is jointly executed with one
of the self-supervised loss techniques.

As mentioned earlier, in this case, except for the object detector within the
module, we have unfrozen the scene graph generator $g$ weights, allowing it to
be trainable and to learn the representation and classification during the
training process, merely according to the prediction answers. We have made
deliberate experimental choices to mitigate potential biases and ensure an
unbiased evaluation of our proposed framework.

For the un-normalized contrastive training step, we employ the MLP prediction
head $h$. It comprises three fully connected layers, each followed by batch
normalization and ReLU activation, except for the final layer. This setup
ensures non-linearity and facilitates effective feature extraction. It is
important to note that the MLP prediction head is exclusively utilized during
the training phase and is subsequently discarded during inference, which
aligns with prevailing practices in contemporary self-supervised training
methods [7, 11].

The classification module $f_{c}$ is another integral component of our model.
It is designed as a two-layer MLP with a dropout rate of $0.2$ and ELU
activation.

##  Appendix D Training Details

In this section, we provide further elaboration on our training approaches.
Likewise, we have divided this section into two subsections: one with the
utilization of GloVE word embedding along with a transformer-based model for
the question encoder, and the other focusing on the application of BERT for
word embedding and the question encoder.

Table D.1: Training details for the GloVE and BERT approaches employed in our study. Methods | Batch | Optimizer | lr | Epochs
---|---|---|---|---
GloVE+Transf | 64 | Adam | $10^{-4}$ | 50
BERT | 32 | Adam Belief | $10^{-4}$ | 50

###  D.1 GloVe Word Embedding and Transformer-based Question Encoder

We train the models using the Adam optimizer with a learning rate of $10^{-4}$
and weight decay $10^{-4}$. We apply a batch size of $64$, and a a linear
learning rate schedule using a factor of $10^{-1}$ for every $20$ epochs. All
models are trained for $50$ epochs. We emphasize that during training the
weights of the scene graph generator $g$ are frozen, and do not receive weight
updates.

###  D.2 BERT for Word Embedding and Question Encoder

We train the models using the Belief Adam optimizer with a learning rate of
$10^{-4}$ and weight decay $10^{-4}$. We apply a batch size of $32$, and a
linear learning rate schedule using a factor of $10^{-1}$ for every $10$
epochs. All models are trained for $50$ epochs. It is worth noting that in
these cases, the weights of the scene graph generator $g$ are not frozen
during training. This deliberate choice allows for continual updates and
improvements, particularly in the edge representation, through the utilization
of the Distribution Link Representation Regularization strategy.

##  Appendix E Self-Supervised implementation details

Table E.1 provides a comprehensive overview of the approach adopted in our
study. It is worth noting that our training process was conducted sequentially
and iteratively, allowing us to evaluate the performance of each approach
before deciding on the subsequent implementation choice.

For instance, upon observing that the Local Similarity approach exhibited
comparatively lower performance, albeit surpassing the baseline, we made the
decision to discontinue its implementation on further research (i.e. with the
BERT module and link distribution regularization approach). This strategy
narrowed down the training possibilities, enabling us to focus solely on the
most promising experiments. Another noteworthy example pertains to the
utilization of BERT as our word embedding and query encoder module. Upon
observing its positive impact on results, we exclusively applied the link
distribution regularization technique with this architecture.

Table E.1: Detailed self-supervised implementation in our study by approaches.

| SGG Methods | Baseline | Local Sim | Global Sim. | Self Sim
---|---|---|---|---|---
GloVE+Transf | Frozen SGG | ✓ | ✓ | ✓ | ✓
Link Regularizer |  |  |  |
BERT | Frozen SGG | ✓ |  | ✓ |
Link Regularizer |  |  | ✓ | ✓

##  Appendix F Further Ablations

###  F.1 Further Discussion on Language Bias

We elaborate on additional experiments aimed at evaluating the model’s
robustness when trained with the BERT module. In this case, the experiments
investigate the impact of using a more expressive language model, such as
BERT, on language biases in the VQA task and whether it harms the enhancement
of visual information. We evaluate both how the biases convey not ideal
information when using a more expressive language model such as BERT, and how
the self-supervised approaches perform for robustness.

In this particular experiment, we augmented the images using various
semantically-preserving techniques including Gaussian blur, Gaussian noise,
color jitter with adjustments to brightness, contrast, and hue, as well as
random rotation of up to 45 degrees. As for the questions, a similar approach
was employed by randomly replacing up to 50% of the words with other words.ù

In this context, we emphasize that our approach maintains the semantic
integrity of the image content. Consequently, the underlying model retains its
fundamental objective of accurately predicting the correct response, despite
the heightened complexity introduced.

Table F.1 demonstrated that even when employing a more expressive language
model in the GQA dataset, the self-supervised learning still enhances the
visual information for the predicted answer. Precisely, the results presented
indicate that our approaches exhibit greater resilience to noise while
maintaining the importance of visual information for the task.

We emphasize that the findings of this study demonstrate that despite the
integration of a more expressive language model, such as BERT, the self-
supervised learning method remains effective in leveraging visual data to
classifier the predicted answers. Nevertheless, it is crucial to highlight
that in this particular scenario, the results indicate a possible influence of
language biases inherent in the dataset when utilizing a more advanced
language model. See the results when the perturbation is employed solely on
the scene graph compared to the non-perturbed one, in Table F.1. Additionally,
when analyzing the results with full perturbation, the findings indicate an
enhanced level of robustness when the self-supervision technique is combined
with the model.

Table F.1: Sensitivity of accuracy (%) for bias analyzes of BERT module.

Setup |  | Methods |
---|---|---|---
Question + Scene Graph | BERT Baseline | BERTGlobal+link | BERTSelfSim+link
Noise + SG | $21.0$ | $23.2$ | $24.5$
Question + Noise | $42.4$ | $41.8$ | $42.8$
Noise + Noise | $19.8$ | $21.7$ | $21.3$

###  F.2 Does SelfGraphVQA have a few-shot learning capability?

We trained SelfGraphVQA with varying percentages of labeled data and found
comparable performance to the GQA dataset, suggesting that adding self-
supervised contrastive loss improves model generalization. We wanted to
evaluate the different models on subsets of the full dataset. We tested
reducing the ground truth labeling requirements and compared the performance
when using SelfGraphVQA as opposed to directly training a fully supervised
classification network.

In this case, we trained our SelfGraphVQA varying the percentage of labeled
data, (i.e., 20%, 50%, and 100% of data) and evaluated it on the test dataset.
As demonstrated in Fig. F.1, our proposal performs comparably with half of the
GQA dataset evaluated on standard metrics. This insinuates that adding self-
supervised un-normalized contrastive loss improves the generalization of the
model.

Table F.2 shows how our proposal performs with the standard metrics when
trained with 50% of training data, and we see that the three approaches
perform on par with the baseline trained on the full dataset. In particular,
the validity and plausibility metrics are consistent when compared to models
trained on the full dataset.

Our intuition is that these metrics relate to linguistic bias and do not
necessarily require large amounts of samples to converge, indicating that the
model learns with little data what type of answer it should guess based on the
type of question.

$20$$30$$40$$50$$60$$70$$80$$90$$100$$42$$43$$44$$45$$46$$47$$48$$49$$50$$51$$52$$53$$54$$55$Percentage
of DataAccuracy (%)BaselineLocalGlobalSelfSim Figure F.1: Evaluation curve by
percentage of data used in training on GQA dataset. The models obtain
comparable results to baseline with 50% of the data. Note that we only
illustrate the accuracy of the baseline trained on the full dataset for
reference purposes. Table F.2: Results (in %) evaluating by the standard
metrics when training with 50% of GQA dataset.

Method | Binary | Open | Consistency | Validity | Plausibility | Accuracy
---|---|---|---|---|---|---
Global | $63.52$ | $27.58$ | $54.14$ | $94.83$ | $90.10$ | $48.24$
Local | $63.52$ | $25.63$ | $51.62$ | $94.56$ | $89.30$ | $47.08$
SelfSim | $64.28$ | $27.33$ | $54.68$ | $94.77$ | $90.11$ | $48.07$

###  F.3 More Examples

We present additional examples to illustrate how scene graphs can contribute
to the explainability of AI in the context of VQA, Figure F.2. These examples
highlight that VQA remains an open area of research and that the performance
of a model should be evaluated beyond standard metrics. These examples serve
as a reminder that there is room for further exploration and improvement in
the field of VQA, extending beyond conventional evaluation metrics.

All examples were predicted by the SelfSim framework. In the following
discussion, the additional examples demonstrate both the problem of low
agreement of VQA question answers due to ambiguity and the usefulness of scene
graphs in providing more explainable AI for this task.

For instance in example 1, the model accurately predicts the answer, and the
detection of the airplane in the scene graph is easily visualized. Conversely,
in example 2, the model correctly do not detect the object mentioned in the
question, leading to a correct answer of ’No’.

The benefits of using scene graphs for visual question answering become more
evident in examples 3 and 4. In example 3, the model provides an objectively
correct answer despite a different ground truth answer in the dataset. This
discrepancy is explained by the scene graph, which highlights that the
extracted object related to the question is ’flowers’ rather than ’flowers’.
In example 4, the model correctly classifies the link that relates the chair
located to the right of the curtains in the scene graph, enabling the model to
predict the correct answer.

In example 5, the acceptance of the model’s answer ’liquid’ as opposed to the
ground truth ’beverage’ is subjective and depends on the evaluator’s opinion.
This demonstrates that the model’s response may fail to precisely evaluate the
question, emphasizing the inherent challenges in VQA.

Overall, these examples highlight the potential benefits of incorporating
scene graphs in visual question answering, offering insights into the model’s
reasoning and contributing to more interpretable AI systems.

(1) Correct | (2) Correct | (3) SG explainable | (4) SG explainable | (5) Objectively Correct
---|---|---|---|---
|  |  |  |
|  |  |  |
Q: What is the aircraft | Q: Are there any parachutes | Q: What is the white pot holding? | Q: Which kind of furniture | Q: What is in the red glass??
on the ground? | or bags? |  | is right of the curtains? |
Answer: Airplane | Answer: No | Answer: Flower | Answer: Chair | Answer: Beverage
Prediction: Airplane | Prediction: No | Prediction: Flowers | Prediction: Chair | Prediction: Liquid

Figure F.2: Examples to demonstrate the complexity of VQA and the
explainability of the scene graph. All example is predicted by the SelfSim
framework.


# There is no equivariant coarse embedding of $L_{p}$ into $\ell_{p}$.

Krzysztof Święcicki

###### Abstract

In this paper we prove that $L_{p}$ does not admit an equivariant coarse
embedding into $\ell_{p}$ i.e there is no proper, affine, isometric action of
$L_{p}$, viewed as a group under addition with the standard metric
$||.||_{p}$, on $\ell_{p}$. This is done by showing that representations of
$L_{p}$ into $Isom(\ell_{p})$ has to be trivial, which allows us to reduce the
question to bi-Lipschitz setting.

##  1 Introduction

Both $\ell_{p}$ and $L_{p}$ spaces are some of the oldest examples of Banach
spaces so the question of their embeddability in different categories was
raised as soon as people started to study Banach spaces in those settings. Let
us look at a brief history of embeddability of $L_{p}$ into $\ell_{p}$.

Let’s first look at the linear theory - the fact that there is no bounded
linear embedding from the classical fact that $\ell_{2}$ is linearly isometric
to a subspace of $L_{p}$ for any $1\leq p\neq 2<\infty$ but does not bi-
Lipschitzly embed into $\ell_{p}$. More can be said about the linear theory
from a more general theorem of Kadets and Pełczyński [KP] which establishes a
dichotomy for a closed subspace $X$ of $L_{p}$ when $2<p<\infty$. Namely $X$
is either isomorphic to the Hilbert $\ell_{2}$ space or $X$ contains a
subspace that is isomorphic to $\ell_{p}$ and complemented in $L_{p}$.

A big step in the study of Banach spaces was when people started to look at
them from a purely metric point of view and forgot the underlying linear
structure. A fundamental result in this setting is a theorem by Mazur and Ulam
(see [MU]) that studies isometries $f\colon X\to Y$ between real normed spaces
$X,Y$, that maps $0$ to $0$. By looking at midpoints of line segments they
prove that $f$ is in fact a bounded linear operator. Thus the problem of
metric embedding of $L_{p}$ into $\ell_{p}$ can be reduced to the linear
setting, which gives us a negative answer.

The standard proof of nonexistence of bi-Lipschitz embedding from $L_{p}$ into
$\ell_{p}$ follows Heinrich and Mankiewicz who in [HM] proved more generally
that if $X\colon\to Y$ is a bi-Lipschitz embedding of separable Banach space
$X$ into a space $Y$ with the Radon–Nikodym property, then there exists a
point of Gâteaux differentiability of $f$ and the derivative at that point is
a linear embedding with distortion bounded by distortion of $f$. Their proof
is relying on the Rademacher’s differentiability theorem, which says that
every Lipschitz map $f\colon X\to Y$ from a separable Banach space $X$ into a
Banach space $Y$ with the Radon–Nikodym property is differentiable Haar-
almost-everywhere.

More general type of maps that one may consider is quasi-isometric (or coarse
Lipschitz) embeddings where linear bounds of the distance between any two
points in replaced by an affine bound. In this setting it was Kalton and
Randrianarivony who proved in [KR] that $L_{p}$ does not admit a quasi-
isometric embedding into $\ell_{p}$ by studying graphs
$G_{k}(\mathbb{M})=\\{\overline{n}=(n_{1},\dots,n_{k})\colon
n_{i}\in\mathbb{M},n_{1}<n_{2}<\dots<n_{k}\\}$ with a metric
$d(\overline{n},\overline{m})=|\\{i:n_{i}\neq m_{i}\\}|$ for any subset
$\mathbb{M}$ of the natural numbers. More precisely they estimate the minimal
distortion of any Lipschitz embedding of $G_{k}(\mathbb{M})$ into
$\ell_{p}$-like Banach spaces using Ramsey’s Theorem.

The most general metric embedding we’re going to consider is a coarse
category, where distance bounds we consider are arbitrary nondecreasing
functions. In this setting question about embeddability of $L_{p}$ into
$\ell_{p}$ has only partial answers. Namely for $1\leq p<2$ it follows by work
of by Mendel and Naor in [MN] that $L_{p}$ does embed into $\ell_{p}$. This is
done by factoring the embedding through Hilbert space, based on the argument
by Nowak who proved in [N] that $\ell_{2}$ coarsely embeds into $\ell_{p}$ for
$1\leq p<\infty$.

Changing the setting from metric to more general it is worth noting that
Johnson, Lindenstrauss and Schechtman proved in [JLS] that if Banach space $X$
is uniformly homeomorphic to $\ell_{p}$ for $1<p<\infty$ then $X$ is linearly
isomorphic to $\ell_{p}$. More recently Mendel and Naor in [MN2][Theorem 1.10]
showed that uniform homeomorphism from $L_{p}$ into $\ell_{q}$ exists if and
only if $p\leq q$ or $q\leq p\leq 2$. This was done by developing a theory of
metric cotype, which is an extension of the Rademacher’s cotype to a purely
metric setting.

In this paper, we focus on the category of equivariant coarse embeddings -
which are coarse embeddings that satisfy a certain compatibility condition
with a predetermine representation into isometry group of the target space. We
find that the existence of such an embedding of a normed vector space into
$\ell_{p}$ forces it to be linearly isomorphic to $\ell_{p}$. It is important
to note result by Cornulier, Tessera, Valette [CTV] that if locally compact,
compactly generated, amenable group $G$ coarsely embeds into the Hilbert
space, then it also embeds in the coarsely equivariant way. Since we view
$L_{p}$ as a topological group under addition, one can hope it might be
possible to generalize this fact in order to use our result to attack the
general question of coarse embeddability of $L_{p}$ into $\ell_{p}$.

##  2 Preliminaries

In this section we recall some basic definitions starting with some group
theoretic vocabulary:

######  Definition 1.

For a set $X$ we denote by $Sym(X)$ group of all bijections of $X$.

######  Definition 2.

We say that that a group element $g$ is a n-th root of a group element $h$ if
$g^{n}=h$

Note that if a group $G$ acts on $X$ and $g\in G$ fixes $x\in X$ then $g^{n}$
also fixes $x$ for any natural number $n$. Hence we established the following
claim.

######  Claim 3.

If $h$ is a n-th root of a group element $g$ acting on $X$ $supp(g)\subseteq
supp(h)$.

We now recall definitions of Banach spaces that we will study:

######  Definition 4.

For $1<p<\infty$ we define $\ell_{p}$ as space of all bi-infinite sequences
$\\{x_{i}\\}_{1}^{\infty}$ such that $\sum_{i\in\mathbb{Z}}|x_{i}|^{p}<\infty$
equipped with the norm $\|\\{x_{i}\\}_{1}^{\infty}\|_{p}=\sum_{n}|x_{n}|^{p}$.

######  Definition 5.

For $1<p<\infty$ we define $\mathcal{L}_{p}$ to be a space of all measurable
functions $f:\mathbb{R}\to\mathbb{R}$ such that
${\displaystyle\|f\|_{p}\equiv\left(\int_{S}|f|^{p}\;\mathrm{d}\mu\right)^{1/p}<\infty}$.
Further more we denote by $L_{p}$ the quotient space with respect to the
kernel of $||.||_{p}$, which defines a complete note on the said quotient.

Now we introduce different types of embeddings that we’ll consider:

######  Definition 6.

A map $f\colon(X,d_{X})\to(Y,d_{Y})$ is an isometry if it preserves distance
i.e. for any $x_{1},x_{2}\in X$ the following equality holds
$dd_{Y}(f(x_{1}),f(x_{2}))=d_{X}(x_{1},x_{2}).$

A set of all bijective isometries of a fixed metric space $(X,d_{X})$ forms a
group under composition that we are denoting by $Isom(X)$. A classical result
by Banach (see [Ban]) states that the only isometries of the space $\ell_{p}$
are permutations of the support of the sequence (which is corresponding to
$Sym(\mathbb{Z}\subset Isom(\ell_{p})$) and changes of signs of its elements
(every change of sign is corresponding to a different copy of $\mathbb{Z_{2}}$
and since there are $\mathbb{Z}$ many of them we conclude that
$\mathbb{Z}_{2}^{\mathbb{Z}}\subset Isom(\ell_{p})$). Since a permutation of
the support does not commute with a change of sign we conclude that the group
structure of $Isom(\ell_{p})$ is a semi-direct product of $Sym(\mathbb{Z})$
with $\mathbb{Z}_{2}^{\mathbb{Z}}$ where $Sym(\mathbb{Z})$ is acting by change
of support of $\mathbb{Z}_{2}^{\mathbb{Z}}$. By a standard fact in group
theory this is equivalent to the existence of the following short exact
sequence:

$1\to\mathbb{Z}_{2}^{\mathbb{Z}}\xrightarrow{i}Isom(\ell_{p})\xrightarrow{p}Sym(\mathbb{Z})\to
1.$

Now we introduce different generalizations of isometric maps:

######  Definition 7.

A map $f\colon(X,d_{X})\to(Y,d_{Y})$ is a a bi-Lipschitz embedding if there
exist constants d,D such that for any $x_{1},x_{2}\in X$ the following
inequality holds $dd_{Y}(f(x_{1}),f(x_{2}))\leq d_{X}(x_{1},x_{2})\leq
Dd_{X}(x_{1},x_{2}).$ Constant D is called distortion of $f$ and is denoted
$\mathrm{Dist}(f)$.

######  Definition 8.

A map $f\colon(X,d_{X})\to(Y,d_{Y})$ is a a coarse embedding if there exist
nondecreasing functions $\rho_{-},\rho_{+}\colon[0,\infty)\to[0,\infty)$ such
that ${\displaystyle\lim_{t\to\infty}\rho_{-}(t)=\infty}$ and for any
$x_{1},x_{2}\in X$ the following inequality holds
$\rho_{-}(d_{Y}(f(x_{1}),f(x_{2})))\leq
d_{X}(x_{1},x_{2})\leq\rho_{+}({d_{Y}(f(x_{1}),f(x_{2}))})$.

######  Definition 9.

Let $V$ be a normed, vector space. A linear bijection $U\colon V\to V$ is
called a linear isometry if it preserves the norm i.e. for every $v\in V$ we
have $U(\lVert v\rVert_{V})=\lVert v\rVert_{V}$.

Note that if $G$ is a group then having it act in an isometric way on $V$ is
the same as defining an isometric representation i.e. a homomorphism
$\pi\colon G\to Isom(V)$ into the group of all linear isometries of $V$

######  Definition 10.

An affine isometry of a normed vector space $V$ is a map $A\colon V\to V$ such
that for every $v\in V$ $A(v)=U(v)+b$, where $U$ is a linear isometry and $b$
is a fixed vector in $V$.

We say that group $G$ acts on $V$ by an affine isometries if for every $g\in
G$ there exists an affine isometry $A_{g}\colon V\to V$ such that
$A_{gh}=A_{g}A_{h}$. By our previous remark $A_{g}(v)=\pi_{g}v+b_{g}$ where
$\pi\colon G\to Isom(V)$ and $b\colon G\to V$.If we rewrite
$A_{gh}=A_{g}A_{h}$ in this form we reach identity known as the cocycle
condition:

$b_{gh}=\pi_{g}b_{h}+b_{g}$ (1)

We say that affine action of $G$ on $V$ is proper if
$lim_{|g|\to\infty}\|b_{g}\|_{V}=\infty$. It is important to remark here that
in the proof of our result we will be suing the standard $||.||_{p}$ norm as a
length function on $L_{p}$. Elementary calculation (see [NY] for a proof)
yields:

######  Proposition 11.

Let $G$ be a finitely generated group, which admits a proper, affine,
isometric action on a normed vector space $V$, with a cocycle b. Then b is a
coarse embedding.

Because of the above admitting a proper, affine, isometric action on $V$ is
viewed as a stronger version of a coarse embedding and is also called an
equivariant coarse embedding.

##  3 Proof of the main result

######  Lemma 12.

Let $Sym(\mathbb{Z})$ denote the group of bijections of integers. If
$\sigma\in Sym(\mathbb{Z})$ has a n-th root $\delta$ (i.e.
$\delta^{n}=\sigma$) then there exists a unique n-th root $\sqrt[n]{\sigma}$
s.t. $supp(\sqrt[n]{\sigma})=supp(\sigma)$.

###### Proof.

Let $k,l\in supp(\sigma)$ s.t $\sigma(k)=l$ and $m\in
supp(\delta)-supp(\sigma)$. Assume that $\delta(k)=m$. Notice that $\sigma$
and $\delta$ commute, since $\sigma$ belongs to a cyclic subgroup generated by
$\delta$. Thus $\sigma(\delta(k))=\sigma(m)=m$ and
$\delta(\sigma(k))=\delta(l)$ should be equal. But $\delta$ is an isomorphism
sending $k$ to $m$, so it can not send $l$ to $m$ as well. Contradiction.

We just showed that for any $k\in supp(\sigma)$, $\delta(k)$ also belongs to
$supp(\sigma)$. It mean that all cycles in a cycle decomposition of $\delta$
contain either only elements of $supp(\sigma)$ or only those from
$supp(\delta)-supp(\sigma)$. After removing later cycles from $\delta$ we
obtain $supp(\sqrt[n]{\sigma})$. ∎

######  Lemma 13.

Let $(V,+)$ be a vector space viewed as an abelian group under addition. Then
every homomorphism $\sigma:(V,+)\to Sym(\mathbb{Z})$ is trivial.

###### Proof.

For any $v\in V$ and natural number $n$ we have
$\sigma(\frac{v}{n})^{n}=\sigma(v)$, hence by Lemma 12 $\sqrt[n]{\sigma(v)}$
always exist. We will show that $\sigma(v)=e$. Consider two cases.

First assume that all elements of $supp(\sigma(v))$ have a finite orbit. Let
$k\in supp(\sigma(v))$ and its orbit consist of n integers. Then there exists
$\sqrt[n!]{\sigma(v)}$, which sends this n-tuple of integers to itself. Order
of all elements of $S_{n}$ is divides $n!$, so
$\sqrt[n!]{\sigma(v)}^{n!}=\sigma(v)$ acts on that n-tuple trivially. Thus
$k\notin supp(\sigma(v))$, contradiction.

Now let $k\in supp(\sigma(v))$ have an unbounded orbit. By Lemma 12
$\sqrt{\sigma(v)}$ sends $k$ to some $l\neq k$, which belongs to the orbit of
$k$ under $\sigma(v)$. It follows that $\sqrt{\sigma(v)}(l)=\sigma(v)(k)$. We
claim that $\sqrt{\sigma(v)}(\sigma(v)^{i}(l))=\sigma(v)^{i+1}(k)$ for any
integer i. Case $i=0$ is our basis of induction. Assume $i>0$ and
$\sqrt{\sigma(v)}(\sigma(v)^{i}(l))=\sigma(v)^{i+1}(k)$. Then
$\sigma(v)(\sqrt{\sigma(v)}(\sigma(v)^{i}(l)))=\sigma(v)(\sigma(v)^{i+1}(k))=\sigma(v)^{i+2}(k)$
is equal to
$\sqrt{\sigma(v)}(\sigma(v)(\sigma(v)^{i}(l)))=\sqrt{\sigma(v)}(\sigma(v)^{i+1}(l)))$,
proving inductive step. Similarly if $i<0$ and
$\sqrt{\sigma(v)}(\sigma(v)^{i}(l))=\sigma(v)^{i+1}(k)$. Then
$\sigma(v)(\sqrt{\sigma(v)}(\sigma(v)^{i-1}(l)))$ is equal to
$\sqrt{\sigma(v)}(\sigma(v)(\sigma(v)^{i-1}(l)))=\sqrt{\sigma(v)}(\sigma(v)^{i}(l)))$,
finishing the proof of the claim. Since $k=\sigma(v)^{i}(l)$ for some $i\neq
0$ we have
$\sqrt{\sigma(v)}(k)=\sqrt{\sigma(v)}\sigma(v)^{i}(l)=\sigma(v)^{i}(k)$, which
gives us that $i$ is an integer such that $2i=1$. Contradiction with the
assumption that $\sqrt{\sigma(v)}(k)=l$. Thus $\sigma(v)$ can not be of this
form. ∎

######  Theorem 14.

All representations $\pi:(V,+)\to Isom(\ell_{p})$ are trivial for $p\neq 2$.

###### Proof.

Recall that in section 2 we have established the existence of the following
short exact sequence:

$1\to\mathbb{Z}_{2}^{\mathbb{Z}}\xrightarrow{i}Isom(\ell_{p})\xrightarrow{p}Sym(\mathbb{Z})\to
1.$

By Lemma 13 homomorphisms $p\circ\pi:(V,+)\to Sym(\mathbb{Z})$ is trivial, so
$\pi(V)\leq ker(p)\cong im(i)\cong\mathbb{Z}_{2}^{\mathbb{Z}}$. But every
homomorphism $\rho:(V,+)\to\mathbb{Z}_{2}^{\mathbb{Z}}$ must be trivial, since
$\mathbb{Z}_{2}^{\mathbb{Z}}$ is a torsion group. Thus $\pi$ also needs to be
trivial. ∎

######  Theorem 15.

Every normed, vector space $(V,+)$ admitting a proper, affine, isometric
action on $\ell_{p}$ is isomorphically embeddable into $\ell_{p}$.

###### Proof.

By Theorem 14 linear representation of $V$ is trivial. The cocycle condition 1
gives us then the existence of an additive, coarse embedding $A:V\to l_{p}$
i.e. $\rho_{-}(\lVert v\rVert_{V})\leq\lVert
A(v)\rVert_{l_{p}}\leq\rho_{+}(\lVert v\rVert_{V})$. Now let
$\alpha\in\mathbb{R_{+}}$ be such that $\rho_{-}(\alpha)>0$.

There exists $n\in\mathbb{N}$ such that $2^{n}\alpha\leq\lVert v\rVert\leq
2^{n+1}\alpha$. Then $\lVert
A(v)\rVert=2^{n}\lVert\frac{A(v)}{2^{n}}\rVert\geq
2^{n}\rho_{-}(\alpha)\geq\frac{\rho_{-}(\alpha)}{2\alpha}\lVert v\rVert$.
Similarly $\lVert A(v)\rVert=2^{n}\lVert\frac{A(v)}{2^{n}}\rVert\leq
2^{n}\rho_{+}(2\alpha)\leq\frac{\rho_{+}(2\alpha)}{\alpha}\lVert v\rVert$. ∎

######  Corollary 16.

There is no equivariant coarse embedding of $L_{p}$ into $\ell_{p}$.

## References

  * [AK] F. Albiac, N. Kalton, Topics in Banach Space Theory 2nd edition, Graduate Texts in Mathematics, Springer 2016
  * [Ban] Stefan Banach, Teoria operacji liniowych, Wydawnictwo Kasy Im. Miankowskiego Instytutu Popoularyzowania Nauki, Warszawa 1931
  * [CTV] Y. de Cornulier, R. Tessera, A. Valette, Isometric group actions on Hilbert spaces:growth of cocycles, A. GAFA, Geom. funct. anal. (2007) 17: 770
  * [HM] S. Heinrich, P. Mankiewicz, Applications of ultrapowers to the uniform and Lipschitz
  * [JLS] W. Johnson, J. Lindenstrauss, G. Schechtman, Banach spaces determined by their uniform structures, Geom. Funct. Anal., 6, (1996) 430–470.
  * [KR] N. Kalton, N. Randrianarivony, The coarse Lipschitz structure of $\ell_{p}\bigoplus ell_{q}$, Math. Ann. 341 (2008), 223–237.
  * [KP] M. Kadets, A. Pełczyński, Bases, lacunary sequences and complemented subspaces in the spaces Lp. Stud. Math. 21, 161–176 (1961/1962)
  * [MN] M. Mendel and A. Naor, Euclidean quotients of finite metric spaces, Adv. Math. 189 (2004), 451–494.
  * [MN2] M. Mendel, A. Naor, Metric cotype, Annals of Mathematics, 168 (2008), 247–298
  * [N] P. Nowak, On coarse embeddability into lp-spaces and a conjecture of Dranishnikov, Fund. Math. 189 (2006), no. 2, 111–116.
  * [NY] Piotr Nowak, Guoliang Yu, Large Scale Geometry, European Mathematical Society Publishing House, 2012
  * [MU] S. Mazur, S. Ulam, Sur les transformations isométriques d’espaces vectoriels normés. C. R. Acad. Sci. Paris 194, 946–948 (1932)