#  Task Oriented Conversational Modelling With Subjective Knowledge

Raja Kumar

University of California Santa Cruz
<EMAIL_ADDRESS>
###### Abstract

Existing conversational models are handled by a database(DB) and API based
systems. However, very often users’ questions require information that cannot
be handled by such systems. Nonetheless, answers to these questions are
available in the form of customer reviews and FAQs. DSTC-11 proposes a three
stage pipeline consisting of knowledge seeking turn detection, knowledge
selection and response generation to create a conversational model grounded on
this subjective knowledge. In this paper, we focus on improving the knowledge
selection module to enhance the overall system performance. In particular, we
propose entity retrieval methods which result in an accurate and faster
knowledge search. Our proposed Named Entity Recognition (NER) based entity
retrieval method results in 7X faster search compared to the baseline model.
Additionally, we also explore a potential keyword extraction method which can
improve the accuracy of knowledge selection. Preliminary results show a 4 %
improvement in exact match score on knowledge selection task. The code is
available here

##  1 Introduction

Figure 1: An Example Conversation with Subjective Knowledge

With the advent of Artificial Intelligence (AI), conversational models, also
referred to as dialogue systems interchangeably, have become the need of many
industries ranging from banking, medical to customer services. Most of these
dialogue systems are built on domain specific databases (DB) and APIs (Kim et
al., 2020). It converts user input to a semantic representation such as
domain, intent, and slot, which is then used by the back-end to create a
response. However, such DB based models either give unnatural responses or
fail to answer specific user queries for which data is unavailable (Kim et
al., 2020). Nonetheless, this information is available in the form of customer
reviews or FAQs. An example conversation as shown in Fig. 1 illustrates such
an instance. It can be seen in the example conversation that the last question
about whether the hotel offers WiFi to watch online videos cannot be handled
by the existing DB. However, there are customer reviews which provide this
information. Therefore, a need arises to build a dialogue system which can be
grounded on the available knowledge so that the response generated based on
this knowledge could be much more engaging and accurate. In addition to
building an engaging and cohesive conversation, the system should also be fast
and efficient as these systems are used in real-time by users.

DSTC-11 (Kim, ) proposes a three stage pipeline consisting of knowledge
seeking turn detection, knowledge selection and response generation (see fig
2). Given the conversation history and user utterance, knowledge seeking turn
detection (KSTD) step detects whether there is a need for knowledge from the
knowledge source or it can be handled by the DB? If KSTD detects a need for
knowledge, then Knowledge selection is performed. In Knowledge selection (KS),
the model finds the knowledge which are relevant to the current query and
conversation history. Finally the response generation (RG) model generates the
response based on the selected knowledge and the conversation history.

In this paper, We further break down the knowledge selection into a two steps
consisting of entity retrieval and knowledge matching (see 4). During the
entity retrieval step, the entity name is extracted from the dialogue history
which results in a much smaller search space compared to the baseline model
(see figure 3). Once we find the entity, we perform knowledge matching on the
reduced knowledge base to find the top knowledge candidates. For entity
retrieval, we propose two methods. First, we propose entity retrieval using
fuzzy logic which retrieves the correct entity with 100% accuracy on
validation data. Second we propose entity retrieval using Named Entity
Recognition (NER) which is 7x faster than the proposed fuzzy logic based
entity retrieval method. For the knowledge matching, we first perform keyword
extraction and then perform knowledge similarity to find the top candidates.

The rest of the paper is organized as follows. In Section 2, a brief review on
the related work in dialogue systems is presented and the knowledge grounded
conversational model is discussed. The proposed method is described in Section
3 followed by the implementation and training details in Section 4. Finally,
the results obtained using the proposed two-stage knowledge selection method
are presented in Section 5 followed by a brief discussion on the future scope
of this work and conclusions in Sections 6 and 7 respectively.

Figure 2: An overview of the three stage pipeline proposed by dstc-11 (Kim, )
Figure 3: An overview of how entity retrieval can help reduce the search space
- (a) search space when we don’t know the entity name (left) (b) reduced
search space once we find the entity name as "Entity 2" (right).

##  2 Prior Work

Several studies have explored ways to effectively utilize available knowledge
base in a task-oriented dialogue(TOD) system. (Hosseini-Asl et al., 2020) uses
a single language model trained on all sub-tasks through a simple TOD system
to improve the performance of dialogue state-tracking through GPT2. (Wu et
al., 2020) proposes TOD-BERT, which integrates user and system tokens into
language modeling, and outperforms BERT in intent recognition, dialogue state
tracking, dialogue act prediction, and response selection by training with ToD
datasets. While some models generate conversational interactions based on a
general scenario, (Ghazvininejad et al., 2018) utilizes dialogue context and
knowledge documents as an encoder-decoder model. Additionally, (Zhao et al.,
2020) efficiently generates responses based on unlabeled dialogues by
optimizing knowledge selection through unsupervised learning in relevant
knowledge documents.

Various Information Retrieval (IR) techniques have also been used in
literature to incorporate the desired knowledge, and successfully implement a
knowledge-grounded system. (Song et al., 2018) extracts keywords from a query
dataset using Term Frequency–Inverse Document Frequency (TF-IDF) to search for
the most relevant reply, while (Yan and Zhao, 2018) generates relevant
information for user responses. A document-grounded matching network is
presented in (Zhao et al., 2019) to use external knowledge in selecting
responses for a knowledge-aware retrieval-based chatbot system, that achieves
state-of-the-art performance. In addition, an end-to-end process is proposed
in (Gu et al., 2020) that directly learns ranking scores using neural
networks. Further, knowledge generation and generation based on a pre-trained
language model have been successfully implemented in (Zhao et al., 2020).

Figure 4: The proposed two stage knowledge selection pipeline

##  3 Proposed Method

This section discusses the proposed method in detail. Figure 3 shows an
instance where if we can find the right entity and keywords, we can make our
selection model faster and more accurate. Based on this intuition, Figure 4
shows the proposed two step knowledge selection model consisting of entity
retrieval and knowledge matching. This report proposes two variants of entity
retrieval methods - (a) entity retrieval using fuzzy logic and, (b) entity
retrieval using NER.

###  3.1 Entity retrieval using fuzzy logic

In the proposed entity retrieval method using fuzzy logic, we find the entity
by comparing all the entity names with the n-grams created using the
conversation history. Figure 5 shows the proposed methodology. We first
convert the conversation history to $n$-grams, where $n$ is the maximum length
of the entity. Then, we perform the fuzzy matching between these $n$-grams
with all the entities present in the knowledge database and select the one
with the highest similarity score as the final entity name. We put a threshold
score of $0.95$ to find only the relevant entities.

Figure 5: The proposed Entity retrieval using fuzzy logic

Using the proposed method, we are able to find the correct entity $100\%$ of
the time, on validation data. However, this method is still slow as it
requires comparing the similarity between all the $n$-grams and entity names.
Therefore, we propose the NER based entity recognition which extracts the
entity name directly from the conversation history without the need to compare
with all the entity names.

###  3.2 Entity retrieval using NER

Figure 6: A sample example for IOB tagging

NER is a commonly used method to locate and classify named entities mentioned
in unstructured text into predefined categories such as person names,
organizations, locations etc. In the context of our tasks, the entity names
are included in the conversation history almost all the time. Therefore, we
define this problem as an NER which identifies the entities in the given
conversation. We use the POS tagging to prepare the training dataset where
each token is labeled as one of the followings, B-ent (Beginning entity),
I-ent (Inside entity) and O (outside entity). Figure 6 shows one example of
dataset preparation. We get the true entity name from the entity name of the
ground truth selected knowledge in training data. We fine-tune the BERT model
using our training data to perform token classification. Fig 7(a) shows the
model architecture.

(a) The NER model used to extract the entity

(b) Table 1

###  3.3 Keyword Extraction for improved knowledge matching

As shown in Fig 1, we observe that we don’t need the whole conversation for
the knowledge selection. We notice that there are a few keywords which are
sufficient to find the relevant knowledge. These keywords are contained in the
last few utterances of the conversation. Based on this observation, we propose
to use a keyword extraction before knowledge matching. A model could not be
trained to do this because of the limited time. However, we show an ablation
study in Table 3 of Section 5 to validate our claim.

###  3.4 Dataset

We use the dataset provided in DSTC-11 challenge which is an augmented version
of MultiWoz 2.1 (Zang et al., 2020) dataset . It includes newly introduced
subjective knowledge-seeking turns. Table 7(b) shows the summary of the
dataset. We train the baseline models for knowledge seeking turn detection and
response generation using the provided dataset. However, for NER model
training we prepare the dataset as explained in Section 3.2 using the ground
truth from knowledge selection ground truth label.

##  4 Implementation Details

First, the baseline model for all three modules, namely KSTD, KS and RG, are
trained. KSTC and KS use the DeBERTaV3 model (He et al., 2021) while RG uses
the BART model (Lewis et al., 2019). KSTC and RG are trained for 10 epochs and
KS is trained for 3 epochs. It takes a total of $\sim$4 hours to train all
three models on a single nvidia V100 GPU. For the NER training, the same
DeBERTaV3 model (He et al., 2021) is used to train it for 10 epochs on a
single nvidia V100 GPU. All other hyper-parameters are kept as default values.
The maximum token is trimmed to 256 for both history utterance and knowledge.

##  5 Results

In this section, we present the experimental results obtained using the
proposed entity retrieval methods using fuzzy logic and NER. In table 1 we
show the accuracy of entity retrieval using proposed fuzzy logic, pre-trained
NER model (Devlin et al., 2018) and fine-tuned NER. The proposed fuzzy logic
always finds the entity name correctly. However it takes a long time since it
uses n-gram comparison with all the entity names. Therefore, we use the NER to
extract the entity name. The fine-tuned NER model achieves an accuracy of 72%
while being 7X more faster than fuzzy logic.

Table 1: Accuracy and inference speed comparison of the proposed fuzzy logic, a pretrained NER model[add ref] and fine-tuned NER model Method | Accuracy(in %) | Evaluation Time (in secs)
---|---|---
Fuzzy logic | 100 | 1459
Pre-trained-NER | 65 | 220
Fine-tuned NER | 72 | 220 ($\sim$7X speedup)

In table 2 we show the ablation study of how many turns are enough to extract
the entity name from the conversation history. We observe that using only the
last 5 utterances are enough to find the entity name most of the time. A
similar trend is observed for the fine-tuned NER.

Table 2: Ablation study of how many turns are needed to find the entity name # dialogue turns | Fuzzy logic(in %) | Fine-tuned NER (in %)
---|---|---
1 | 15 | 11
2 | 84 | 56
5 | 98 | 66
all | 100 | 72

Further, We perform an ablation study to find whether the proposed keyword
extraction can improve the knowledge selection. To this end, we perform the
knowledge selection by varying the number of dialogue turns. Table 3 shows
that using only the last utterance leads to an improvement of $\sim$4% in
exact match accuracy as compared to when we use all the utterances. We also
observe an improvement in the response generation bleu and rouge1 score with
an increase in knowledge selection accuracy, as these three tasks are
performed in sequential manner.

Table 3: Preliminary results showing the effectiveness of keyword extraction. | Knowledge Selection | Response Generation
---|---|---
# dialogue turns | f1 | em_accuracy(in %) | bleu | rouge1
1 | 0.833 | 39.5 | 0.103 | 0.361
2 | 0.825 | 35.8 | 0.102 | 0.358
5 | 0.828 | 37.6 | 0.103 | 0.361
all | 0.818 | 35.8 | 0.101 | 0.358

##  6 Future work

Although this report shows that the NER based entity retrieval is much faster,
it is still to reach the desired accuracy. Therefore, a future scope of work
is to improve the accuracy of NER for this specific task. Another scope for
improvement is with respect to the generalizability of the model. The training
set provided in DSTC-11 has data only from the ‘hotel’ and ‘restaurant’
domain. Although the proposed method does not utilize this information, the
model can be biased and hence may not generalize well to data from other
domains like ‘flight’, ‘taxi’ etc. Hence, the present work can be extended to
improve the generalizability of the model.

##  7 Conclusion

Knowledge grounded dialogue systems are the need of the hour, to make dialogue
systems accurate and cohesive. This report finds that knowledge selection is
the bottleneck for improving the performance of such a system. In this report
the knowledge selection step is further broken down into an entity retrieval
step followed by a knowledge matching step. To make the search faster, two
variants of the entity retrieval method are proposed. The proposed fuzzy logic
based entity retrieval achieves 100% accuracy, while the NER based entity
extraction makes the inference faster. Further, an ablation study shows that
knowledge selection can be improved by performing keyword extraction.

## References

  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  _CoRR_ , abs/1810.04805, 2018.  URL http://arxiv.org/abs/1810.04805.
  * Ghazvininejad et al. [2018] Marjan Ghazvininejad, Chris Brockett, Ming-Wei Chang, Bill Dolan, Jianfeng Gao, Wen-tau Yih, and Michel Galley.  A knowledge-grounded neural conversation model.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Gu et al. [2020] Jia-Chen Gu, Zhen-Hua Ling, Quan Liu, Zhigang Chen, and Xiaodan Zhu.  Filtering before iteratively referring for knowledge-grounded response selection in retrieval-based chatbots.  _arXiv preprint arXiv:2004.14550_ , 2020.
  * He et al. [2021] Pengcheng He, Jianfeng Gao, and Weizhu Chen.  Debertav3: Improving deberta using electra-style pre-training with gradient-disentangled embedding sharing, 2021.
  * Hosseini-Asl et al. [2020] Ehsan Hosseini-Asl, Bryan McCann, Chien-Sheng Wu, Semih Yavuz, and Richard Socher.  A simple language model for task-oriented dialogue.  _Advances in Neural Information Processing Systems_ , 33:20179–20191, 2020.
  * [6] Seokhwan Kim.  The eleventh dialog system technology challenge.  https://dstc11.dstc.community/tracks.  Accessed: 2022-03-21.
  * Kim et al. [2020] Seokhwan Kim, Mihail Eric, Karthik Gopalakrishnan, Behnam Hedayatnia, Yang Liu, and Dilek Hakkani-Tur.  Beyond domain APIs: Task-oriented conversational modeling with unstructured knowledge access.  In _Proceedings of the 21th Annual Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 278–289, 1st virtual meeting, July 2020. Association for Computational Linguistics.  URL https://aclanthology.org/2020.sigdial-1.35.
  * Lewis et al. [2019] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer.  BART: denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _CoRR_ , abs/1910.13461, 2019.  URL http://arxiv.org/abs/1910.13461.
  * Song et al. [2018] Yiping Song, Rui Yan, Cheng-Te Li, Jian-Yun Nie, Ming Zhang, and Dongyan Zhao.  An ensemble of retrieval-based and generation-based human-computer conversation systems.  2018\.
  * Wu et al. [2020] Chien-Sheng Wu, Steven Hoi, Richard Socher, and Caiming Xiong.  Tod-bert: Pre-trained natural language understanding for task-oriented dialogue.  _arXiv preprint arXiv:2004.06871_ , 2020.
  * Yan and Zhao [2018] Rui Yan and Dongyan Zhao.  Coupled context modeling for deep chit-chat: towards conversations between human and computer.  In _Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 2574–2583, 2018.
  * Zang et al. [2020] Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen.  MultiWOZ 2.2 : A dialogue dataset with additional annotation corrections and state tracking baselines.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI_ , pages 109–117, Online, July 2020. Association for Computational Linguistics.  doi: 10.18653/v1/2020.nlp4convai-1.13.  URL https://aclanthology.org/2020.nlp4convai-1.13.
  * Zhao et al. [2019] Xueliang Zhao, Chongyang Tao, Wei Wu, Can Xu, Dongyan Zhao, and Rui Yan.  A document-grounded matching network for response selection in retrieval-based chatbots.  _arXiv preprint arXiv:1906.04362_ , 2019.
  * Zhao et al. [2020] Xueliang Zhao, Wei Wu, Can Xu, Chongyang Tao, Dongyan Zhao, and Rui Yan.  Knowledge-grounded dialogue generation with pre-trained language models.  _arXiv preprint arXiv:2010.08824_ , 2020.


# A construction for a counterexample to
the pseudo $2$-factor isomorphic graph conjecture

Marién Abreu<EMAIL_ADDRESS>Martin Funk<EMAIL_ADDRESS>Domenico Labbate<EMAIL_ADDRESS>Federico Romaniello
<EMAIL_ADDRESS>Università degli Studi della Basilicata, Viale
dell’Ateneo Lucano 10, 85100 Potenza, Italy.

###### Abstract

A graph $G$ admiting a $2$-factor is pseudo $2$-factor isomorphic if the
parity of the number of cycles in all its $2$-factors is the same. In [1] some
of the authors of this note gave a partial characterisation of pseudo
$2$-factor isomorphic bipartite cubic graphs and conjectured that $K_{3,3}$,
the Heawood graph and the Pappus graph are the only essentially $4$-edge-
connected ones. In [7] Jan Goedgebeur computationally found a graph
$\mathscr{G}$ on $30$ vertices which is pseudo $2$-factor isomorphic cubic and
bipartite, essentially $4$-edge-connected and cyclically $6$-edge-connected,
thus refuting the above conjecture. In this note, we describe how such a graph
can be constructed from the Heawood graph and the generalised Petersen graph
$GP(8,3)$, which are the Levi graphs of the Fano $7_{3}$ configuration and the
Möbius-Kantor $8_{3}$ configuration, respectively. Such a description of
$\mathscr{G}$ allows us to understand its automorphism group, which has order
$144$, using both a geometrical and a graph theoretical approach
simultaneously. Moreover we illustrate the uniqueness of this graph.

###### keywords:

$2$-factor, cubic, bipartite, configurations, automorphisms

###### MSC:

[2010] 05B30, 05C25, 05C38, 05C75

††journal: —

##  1 Introduction

All graphs considered in this note are simple (without loops or multiple
edges) and undirected. Most of our terminologies are standard; for further
definitions and notation not explicitly stated in the paper, please refer to
[4] and [8].

A $2$-factor of a graph $G$ is a $2$-regular spanning subgraph of $G$. A graph
$G$ admiting a $2$-factor is pseudo $2$-factor isomorphic if the parity of the
number of cycles in all its $2$-factors is the same. In a cubic graph, the
three edges incident with a vertex constitute a $3$-edge-cut because their
removal leaves an isolated vertex, and is called _trivial_ , others being
_non-trivial_. A cubic graph is said to be _essentially $4$-edge-connected_ if
it contains no non-trivial $3$-edge-cut. A set $S$ of edges of a graph $G$ is
a _cyclic edge cut_ if $G-S$ has two components each of which contains a
cycle. We say that a graph $G$ is _cyclically $m$-edge-connected_ if each
cyclic edge cut of $G$ has size at least $m$. In [1] some of the authors of
this note gave a partial characterization of pseudo $2$-factor isomorphic
bipartite cubic graphs and conjectured:

######  Conjecture 1.1.

[1, Conjecture $3.6$] Let $G$ be an essentially $4$-edge-connected pseudo
$2$-factor isomorphic cubic bipartite graph. Then $G$ must be $K_{3,3}$, the
Heawood graph or the Pappus graph.

In [7] Jan Goedgebeur computationally found a graph $\mathscr{G}$ on $30$
vertices which is pseudo $2$-factor isomorphic cubic and bipartite,
essentially $4$-edge-connected and cyclically $6$-edge-connected, thus
refuting the above Conjecture 1.1 (cf. Figure 2). Here, we explain how
$\mathscr{G}$ (which we will also refer to as _Goedgebeur’s graph_) is
generated and why it is unique in its kind, providing a construction. In
particular, we analyse the structure of $\mathscr{G}$ describing how it arises
from the Heawood graph and the generalised Petersen graph $GP(8,3)$, which are
the Levi graphs of the Fano $7_{3}$ configuration $F$ and the Möbius-Kantor
$8_{3}$ configuration $MK$, respectively. This construction will completely
explain the automorphism group of $\mathscr{G}$ as a semidirect product of
groups of order $9$ and $16$ respectively. This construction does not
generalize in a natural way to an infinite family of graphs preserving all
properties of $\mathscr{G}$, in particular being pseudo $2$-factor isomorphic.

Recall that a cubic bipartite graph on $2n$ vertices with girth at least $6$
is the Levi graphs of a symmetric configurations $n_{3}$. When counting
symmetric configurations, we must distinguish between self-dual
configurations, which give rise to one bipartite graph of girth at least $6$
(via its Levi graph), and pairs of distinct configurations dual to each other
with isomorphic Levi graphs. With increasing order $n$ the number of pairwise
non-isomorphic structures exponentially increases but almost all of them are
rigid, i.e. they have a trivial automorphism group. Therefore it makes sense
to focus on graphs which have a large automorphism group, say at least $4n$.

The graph $\mathscr{G}$ has $30=2n$ vertices and is the Levi graph of a
$n_{3}=15_{3}$ configuration $\mathscr{C}$. For $n=15$, there are $125571$
cubic bipartite graphs with girth at least $6$, which give rise to $5802$
$15_{3}$ self-dual configurations and $119770$ pairs of non-isomorphic
$15_{3}$ configurations dual to each other. Note that the automorphism group
of the Levi graph of a configuration $n_{3}$ is twice as big as the one of the
corresponding configuration. There are $6$ graphs with large automorphism
group, namely the Levi graph of the generalised quadrangle of order $2$, with
automorphism group of order $2\cdot 8094$, moreover there are two Levi graphs
of self-dual configurations with automorphism group $2\cdot 720$ and $2\cdot
128$, respectively, a pair of non-isomorphic configurations with automorphism
group of order $192$, as well as Goedgebeur’s graph $\mathscr{G}$, i.e. a
self-dual graph with automorphism group of order $144$. All Levi graphs of
other $15_{3}$ configurations have automorphism group of order less than $4n$
(cf. [2], [3], [7]).

In Section 2 we will describe the construction that gives rise to
$\mathscr{G}$; in Section 3 we investigate the automorphism group of
$\mathscr{G}$ and in Section 4 we analyse the uniqueness of $\mathscr{G}$.

##  2 The Construction

In this section we describe how the configuration $\mathscr{C}$, of which
$\mathscr{G}$ is the Levi graph, arises by appropriately joining the Fano
configuration $F$ and the Möbius-Kantor configuration $MK$. The following
definition will be very useful for our purposes:

######  Definition 2.2.

A quadrilateral consists of $4$ points $P_{0},P_{1},P_{2},P_{3}$ in general
position (i.e. no three collinear) and the $4$ (oriented) lines
$P_{i}P_{i+1}$, indices taken modulo $4$.

Now we define two structures that arise from the configurations $MK$ and $F$
by removing some point/line incidences without deleting neither points nor
lines, and changing only the valency of some of them.
Consider the classical representation of $MK$ as two quadrilaterals
simultaneously inscribed and circumscribed (e.g. cf. [6, pag. 430]).
Disregarding the circumscription, i.e. removing the corrisponding incidences
it defines, we obtain an _$MK$ -residue_ in which the valency of 4 points and
4 lines decreases from three to two. Similarly, removing the incidences of a
quadrilateral in $F$, we obtain an _$F$ -residue_ with 4 points and 4 lines of
valency two.
The configuration $\mathscr{C}$ then arises by suitably adding incidences
among points and lines of valency two between an $F$-residue and an
$MK$-residue.

Consider the labellings of the Möbius-Kantor and Fano plane configurations as
in Figure 1 and choose the $MK$-residue and the $F$-residue accordingly.

Figure 1: Möbius-Kantor and Fano plane configurations

Note that the quadrilaterals $P_{0}P_{1}P_{2}P_{3}$ and
$P^{\prime}_{0}P^{\prime}_{1}P^{\prime}_{2}P^{\prime}_{3}$ are both diagonal
free, in the sense that the pairs
$P_{0}P_{2},P_{1}P_{3},P^{\prime}_{0}P^{\prime}_{2}$ and
$P^{\prime}_{1}P^{\prime}_{3}$ are all non collinear. These two quadrilaterals
are in fact mutually inscribed and circumscribed. The $MK$-residue is obtained
by removing the circumscription, i.e. the incidences
$P_{0}|l_{2},P_{1}|l_{3},P_{2}|l_{0},P_{3}|l_{1}$, where $l_{i}$ is defined as
in Figure 1. The $F$-residue is obtained by removing the incidences
$P^{\prime\prime}_{i+1}|l^{\prime\prime}_{i}$ of the quadrilateral
$P^{\prime\prime}_{0},P^{\prime\prime}_{1},P^{\prime\prime}_{2},P^{\prime\prime}_{3}$,
indices taken modulo $4$, where $l^{\prime\prime}_{i}$ is also defined as in
Figure 1. There are $576$ ways to join the points and lines of the
$MK$-residue and the $F$-residue in order to obtain a $15_{3}$ configuration
(cf. Section 4), but the choice of the incidences $P_{i}|l^{\prime\prime}_{i}$
and $P^{\prime\prime}_{i}|l_{i}$, indices taken modulo $4$, gives rise to
$\mathscr{C}$ and has $\mathscr{G}$ as its Levi Graph (cf. Figure 2). In
Section 4 we will analyse what the other choices of incidences give, but first
we study $Aut(\mathscr{G})$.

Figure 2: Goedgebeur’s graph $\mathscr{G}$

##  3 The Automorphism Group of $\mathscr{G}$

In order to investigate the automorphism group $Aut(\mathscr{G})$, we consider
the Levi graph of the $F$-residue and the $MK$-residue described in the
previous section and mantain the inheritatd labelling on the vertices, some
corresponding to points and other to lines, on different sides of the
bipartition. We refer to the edges connecting the $F$-residue with the
$MK$-residue as the eight-bridge. Observe that in $\mathscr{G}$ there is a
unique edge $e$ at distance $2$ from each vertex
$P^{\prime\prime}_{i},l^{\prime\prime}_{i},i=0,\ldots,3$ and hence from the
eight-bridge. Morover, the edges
$f_{i}=P^{\prime\prime}_{i}l^{\prime\prime}_{i},\quad i=0,\ldots,3$ are
independent. Also, in the Levi graph of the MK-residue part of $\mathscr{G}$,
there are exactly four independent edges $m_{0},\ldots,m_{3}$, at distance two
from the eight-bridge (cf. Figure 2).

######  Theorem 3.3.

$Aut(\mathscr{G})\cong(\mathbb{Z}_{3}\times\mathbb{Z}_{3})\rtimes(D_{4}\times\mathbb{Z}_{2})$

###### Proof.

Using Magma Computational Algebra System [5], we computed $Aut(\mathscr{G})$
and realized that it can be described in terms of its action on the set of
edges $M:=\left\\{e,f_{0},\dots,f_{3},m_{0},\dots,m_{3}\right\\}$, so abusing
notation, we will denote automorphisms of $\mathscr{G}$ as permutations of the
edges in $M$.

There are 8 automorphisms characterised by the fact that they map the edge $e$
onto one edge out of $\left\\{f_{0},\dots,f_{3},m_{0},\dots,m_{3}\right\\}$.
Together with the identity, these automorphisms are a subgroup $K$ of
$Aut(\mathscr{G})$ generated by automorphisms $\sigma_{0}$ and $\sigma_{1}$:

$\sigma_{0}=(e,m_{0},m_{2})(m_{1},f_{3},f_{0})(m_{3},f_{2},f_{1})$
---
$\sigma_{1}=(e,f_{1},f_{3})(f_{0},m_{0},m_{3})(f_{2},m_{1},m_{2})$

These automorphisms have order 3, and $K$, which is not cyclic, is hence
isomorphic to $\mathbb{Z}_{3}\times\mathbb{Z}_{3}$. Moreover, $K\triangleleft
Aut(\mathscr{G})$.

On the other hand, the stabilizers in $Aut(\mathscr{G})$ of each edge in $M$
represent isomorphic non-abelian subgroups of order 16, none of which is
normal in $Aut(\mathscr{G})$. Besides the identity, in each group there are 11
and 4 elements of order 2 and 4 respectively. Using the well-known
classification of groups (cf. [9]), these are isomorphic to
$D_{4}\times\mathbb{Z}_{2}$, and they form a unique class of conjugacy in
$Aut(\mathscr{G})$. Hence, we may choose the stabilizer of the edge $e$, say
$H$. In $H$, we find a transpostion $\tau$ which inverts the endvertices of
the edges in $M$, acting as a horizontal mirror through the center of Figure
2. Moreover there are two automorphisms:

$\delta=(e)(f_{0},f_{2})(f_{1})(f_{3})(m_{0},m_{1})(m_{2},m_{3})$
---
$\rho=(e)(f_{0},f_{1},f_{2},f_{3})(m_{0},m_{1},m_{2},m_{3})$

such that $<\delta,\rho>=D_{4}$.

In conclusion we have that

$Aut(\mathscr{G})\cong K\rtimes
H\cong(\mathbb{Z}_{3}\times\mathbb{Z}_{3})\rtimes(D_{4}\times\mathbb{Z}_{2}).$

∎

##  4 The uniqueness of $\mathscr{G}$

In the construction of $\mathscr{G}$, we made a very specific choice of the
eight-bridge. We now analyse what the other choices are, and to some extent,
what graphs they give rise to. On the first place, we observe that not every
eight-bridge preserves bipartition and girth $6$ and that those that do,
correspond to two permutations of four elements, i.e. from the symmetric group
$S_{4}$, say $\alpha$ and $\beta$ which are used to establish the edges
$P_{i}|l^{\prime\prime}_{\alpha(i)}$ and $l_{i}|P^{\prime\prime}_{\beta(i)}$.
There are $24$ choices for each of $\alpha$ and $\beta$ for a total of $576$
choices for the eight-bridge (preserving bipartition and girth). Let
$\mathscr{G}_{\alpha,\beta}$ be the graph with the choice of the eight-bridge
according to $\alpha$ and $\beta$. To describe and analyse the choices we
consider a partition of the symmetric group $S_{4}$ as in Table 1 in which the
first row contains the normal Klein subgroup
$\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, and the other rows its laterals. In the
last column of Table 1, we have represented the effect of, say $\alpha$, on
the other adjacencies between $l^{\prime\prime}_{i}$ and the vertices
$\\{a,b\\}$ (as in Figure 2).

Class I | $id$ | $(02)$ | $(13)$ | $(02)(13)$ |
---|---|---|---|---|---
Class II | $(01)(23)$ | $(0123)$ | $(0321)$ | $(03)(12)$ |
Class III | $(01)$ | $(012)$ | $(031)$ | $(0312)$ |
Class IV | $(23)$ | $(023)$ | $(132)$ | $(0213)$ |
Class V | $(03)$ | $(032)$ | $(013)$ | $(0132)$ |
Class VI | $(12)$ | $(021)$ | $(123)$ | $(0231)$ |
Table 1: The partition of $S_{4}$

We distinguish among two types of choices of $\alpha$ and $\beta$.

  * 1.

Case 1: When $\alpha=\beta$

  * 2.

Case 2: When $\alpha\neq\beta$.

In case 1, $\tau$, the mirror automorphism of $\mathscr{G}$ described in the
previous section, is still an automorphism of $\mathscr{G}_{\alpha,\beta}$.
The choice of $\alpha$ from the first two rows of Table 1 gives rise to graphs
isomorphic to $\mathscr{G}$ because the rest of the $F$-residue is preserved.
Thus, we have $8$ graphs isomorphic to $\mathscr{G}$. The other $16$ graphs
with $\alpha$ from rows $3-6$ of Table 1 do no longer preserve the
automorphisms $\sigma_{0}$ and $\sigma_{1}$, but they all belong to the same
isomorphism class. Such graphs have automorphism group of order $24$, having
lost the $\mathbb{Z}_{3}\times\mathbb{Z}_{3}$ part of the automorphism group
of $\mathscr{G}$.

In case 2 the situation of symmetries gets much worse, and the results are
summarized in Table 2.

$|Aut(G)|$ |  $\\#$ Isomorphism Classes |  $\\#$ Representants
---|---|---
16 | 1 | 8
8 | 6 | 16
4 | 1 | 64
4 | 32
2 | 2 | 64
1 | 1 | 128
Table 2: Summary of $\mathscr{G}_{\alpha,\beta}$

In conclusion, the graph $\mathscr{G}$ is unique, up to automorphisms of the
$F$-residue, which as described in case 1.

There is also another sense in which $\mathscr{G}$ seems to be unique. As far
as we could check, the construction of joining residues of Levi graphs of
$n_{3}$ configurations, do not preserve, in general a strong property such as
being pseudo $2$-factor isomorphic. The problem lies in the kinds of cycles
which are created that are, thus, able to produce $2$-factors of both
parities. Intuitively, there is too much room, whereas the MK-residue and the
F-residue are very compact. Moreover, also using several copies of the same
residues does not preserve the behavior of the parity of cycles in a
$2$–factor.

## Acknowledgement

The research that led to the present note was partially supported by the group
GNSAGA of INdAM.

## References

  * [1] M. Abreu, A.A. Diwan, B. Jackson, D. Labbate and J. Sheehan. Pseudo $2$-factor isomorphic regular bipartite graphs. Journal of Combinatorial Theory, Series B, 98(2) (2008), 432–444.
  * [2] A. Betten, Private communication.
  * [3] A. Betten, G. Brinkmann, T. Pisanski. Counting symmetric configurations $v_{3}$. Discr. Applied Math., 99 (2000), 331–338.
  * [4] J.A. Bondy, U.S.R. Murty. Graph Theory. Springer Series: Graduate Texts in Mathematics, 244 (2008).
  * [5] W. Bosma, J. Cannon and C. Playoust. The Magma algebra system. I: The user language. J. Symbolic Comput., 24 (1997), 235–265.
  * [6] H.S.M. Coxeter. Self-dual configurations and regular graphs. Bull. Amer. Math. Soc., 56(5) (1950), 413–455.
  * [7] J. Goedgebeur. A counterexample to the pseudo $2$-factor isomorphic graph conjecture. Discr. Applied Math., 193 (2015), 57–60.
  * [8] H. Wielandt. Finite permutation groups, Academic Press, New York, (1964).
  * [9] M. Wild. The groups of order sixteen made easy. The American Mathematical Monthly, 112(1) (2005), 20–31