# SecureLLM: Using Compositionality to Build
Provably Secure Language Models for Private, Sensitive, and Secret Data

Abdulrahman Alabdulkareem  Christian M Arnold*†
Yerim Lee Pieter M Feenstra
Boris Katz Andrei Barbu
CSAIL and CBMM, MIT
* Equal Contribution † US Space Force
<EMAIL_ADDRESS>
###### Abstract

Traditional security mechanisms isolate resources from users who should not
access them. We reflect the compositional nature of such security mechanisms
back into the structure of LLMs to build a provably secure LLM; that we term
SecureLLM. Other approaches to LLM safety attempt to protect against bad
actors or bad outcomes, but can only do so to an extent making them
inappropriate for sensitive data. SecureLLM blends access security with fine-
tuning methods. Each data silo has associated with it a separate fine-tuning
and a user has access only to the collection of fine-tunings that they have
permission for. The model must then perform on compositional tasks at the
intersection of those data silos with the combination of those individual
fine-tunings. While applicable to any task like document QA or making API
calls, in this work we concern ourselves with models that learn the layouts of
new SQL databases to provide natural-language-to-SQL translation capabilities.
Existing fine-tuning composition methods fail in this challenging environment,
as they are not well-equipped for handling compositional tasks.
Compositionality remains a challenge for LLMs. We contribute both a difficult
new compositional natural-language-to-SQL translation task and a new
perspective on LLM security that allows models to be deployed to secure
environments today.

##  1 Introduction

Information silos[1][10][30][40][4]f Combined
---
fine-tunings
LLM

Figure 1: No user-LLM interaction can access information silos that the user
does not have permissions for; the fine-tunings associated with those silos
are not connected to the user’s LLM. This is the key component of SecureLLM:
reflect the compositional nature of access security back into the structure of
the fine-tunings of the LLM. LLMs have great difficulty generalizing to this
composition environment. Worse, existing fine-tuning methods fail in this
challenging compositional environment. We introduce new fine-tuning methods
that perform well because they are selected specifically for this domain.

Using language models in environments with sensitive information is fraught
with problems. Models can be convinced to reveal information they should not,
to answer questions they should not, to reveal their training data and
prompts, to run API calls they should not, etc. Various approaches have tried
to grapple with this problem, yet no prior work offers a method that provides
any guarantees, merely offering mitigations. When dealing with sensitive data,
this is practically and often legally insufficient. We provide the first
method to build provably secure LLMs by reflecting the compositionality
inherent in access security into the LLM.

We consider the scenario where a number of silos of information are available
(fig. 1). These may be APIs, databases, or collections of documents with
sensitive information. Each user has access to some subset of these silos.
Nominally, one could imagine an exponential number of LLMs with an LLM for
each subset of silos. This would guarantee security, as an LLM being used
would only be trained on data that the user has access to. Creating and
maintaining an exponentially-increasing number of models is impractical.
Instead, we show how to achieve the same goals with a linear number of LLM
fine-tunings. While using only one fine tuned model per silo, we can configure
and compose a model specific to the user’s permissions at runtime.

Knowledge about the target domain is critical. A silo may contain a large
volume of documents, databases, or APIs, each with their own internal logic.
Even Retrieval-Augmented Generation (RAG) is insufficient for such
applications because it presupposes that the model understands the logic of a
target domain. You cannot accurately retrieve something that you don’t
understand at all; imagine a new technology or capability. SQL translation
tasks offer an extreme version of this where the target database schema must
be known. Often, the schema itself is highly sensitive and should not be
revealed to all users. This is the scenario we consider here.

To build such secure LLMs we rely on fine-tuning. For each information silo we
fine-tune a model using a method that isolates the weight updates to a small
part of the model which can then be excised and stored separately. Then, when
a user interacts with the system, their permissions automatically determine
the collection of fine-tunings that must be applied to the model and how those
fine-tunings must be applied. For example, a user with access to silos A, B,
and C that wants to communicate to another user with access to only A and B,
would set up their model with positive fine-tunings for A and B in order to
actively avoid topics related to C.

This idea is reminiscent of recent work like LoraHub (Huang et al., 2023)
which also composes fine-tunings. Given a target task, LoraHub selects a set
of fine-tunings, Low Rank Adapters (LoRAs) (Hu et al., 2021), that are added
together. However, LoraHub is designed for soft tasks, where a model already
tends to perform well, and where LoraHub’s aim is to increase performance by a
few percent. The domain we consider here is radically different, we seek
compositionality for unrelated silos of information. Questions that require
access to silos A and B, by definition cannot be answered with access to only
A or only B. The underlying performance of models is nearly zero. LoraHub is
not well-suited to such tasks and performs very poorly. It is only through
exploiting the compositionality of security as a domain that our methods
achieve much higher performance.

Our contributions are: 1\. formulating a difficult new compositional task that
LLMs have great difficulty with – natural-language-to-SQL where not only is a
model trained on queries of individual databases but also where the generated
response requires cross-database joins, 2\. formulating the notion of access
security in terms of this task, 3\. demonstrating that existing fine-tuning
methods fail in this compositional environment, 4\. the introduction of new
compositional fine-tuning methods for this problem, While we only concern
ourselves with the task of understanding queries by translating them to SQL,
our methods are generic and can be applied to numerous other domains like
translating commands to API calls and answering questions from large
collections of documents.

##  2 Related Work

Model Composition. Our framework relies on composing LLM fine-tunings at
inference time which follows a set of previous works that use model
composition. A recent method combines pretrained LLM prompts each tuned for
separate tasks to achieve generalization on downstream tasks (Sun et al.,
2023) which requires training at inference time. AdapterSoup composes fine-
tunings by linearly averaging their weights depending on a criteria to
determine which fine-tunings are relevant to the new domain (Chronopoulou et
al., 2023). PEM Addition is a method that doesn’t require further training
such as composing fine-tunings using arithmetic operations directly on the
weights (Zhang et al., 2023). LoraHub is a recent simple framework that also
composes different LoRa fine-tunings (Hu et al., 2021) at inference time where
each fine-tuning is trained on a different task (Huang et al., 2023); we
include comparisons using LoraHub and PEM Addition.

Privacy Attacks. Many recent works discuss a range of different privacy
attacks against large language models and Deep Learning models in general.
Membership inference attacks are a type of privacy attack which try to
determine if a piece of text was contained in the training data of a model
possibly without access to the weights (Hisamoto et al., 2020; Nasr et al.,
2019; Hu et al., 2022). An even larger security risk is posed by training data
extraction attacks where large language models leak text in their training
data verbatim (Carlini et al., 2019) including personally identifiable
information (Inan et al., 2021). This attack is shown to be successful even
when such data was only mentioned in a single document and this behavior
worsens with an increase in model size (Carlini et al., 2021). Similarly,
training data extract attacks were effective on models fine-tuned on a smaller
dataset (Zanella-Béguelin et al., 2020). With recent work tackling these
privacy issues for Retrieval-Augmented Generation using multi party
communication (Zyskind et al., 2023).

Differential Privacy. A popular algorithmic technique to train machine
learning models with certain privacy guarantees is differential privacy (Abadi
et al., 2016) which has also been applied to large recurrent language models
(McMahan et al., 2017). Multiple recent works manage to use differentially
private learning on large language models with hundreds of millions of
parameters to achieve efficient differentially private fine-tuning with slight
degradation in performance (Li et al., 2021; Yu et al., 2021). Many other
methods borrow inspiration from differential privacy like Confidentially
Redacted Training which provably prevents memorization of the training data
(Zhao et al., 2022). However, there are differences between Differential
Privacy and our approach. In differential privacy, there exists a non-zero
amount of privacy loss parameterized by the privacy budget ($\epsilon$ and
$\delta$) from the resulting model as the privatization step minimizes but
does not completely ensure that the updated model parameters do not leak
private information. Additionally, there is a difference in what is considered
private information compared to what is non-confidential. Differential Privacy
considers the individual records within the training data as private such that
any individual record is sufficiently obfuscated while holistic trends are
still learnt by the resulting model. Comparatively, our notion of privacy
ensures that every individual record in a private silo needs to be completely
private including any and all holistic information gained from the silo.

A common trend in privacy preserving research into LLMs is the focus on
preventing models from memorizing and/or leaking individual records or pieces
of information while attempting to maintain a holistic distillation of the
training data into the model. This distinguishes our work as we consider any
and all information gleaned from a silo to be confidential no matter how
granular or holistic it is. We also avoid falling back to probabilistic claims
or claims in expectation and ensure that all claims of confidentiality are
provably correct as the resulting model weights that an individual user
interacts with have only been optimized using data that the user is authorized
to access.

##  3 Framework

SecureLLM takes several fine-tunings each trained on distinct information
silos and composes them at inference time. The goal of the composed model is
to answer questions about both individual silos and questions that span silos.
For example, in our case, a natural-language to SQL LLM would need to be able
to generate joins across the databases of multiple silos to answer complex
questions that have never been seen at training time. This is a trivial task
for humans, but one that challenges LLMs. We go a step further: not only must
such an LLM work, it must operate through a combination of fine-tunings, i.e.,
not only has it never seen combinations of silos at training time, its fine
tunings have only ever seen a single silo each. This challenges, and defeats,
current fine-tuning methods. The upshot of this difficult task is that it
solves several key security problems for LLMs.

Given $N$ data silos $\\{S_{1},S_{2},\cdots,S_{N}\\}$ and $N$ fine-tuned LLMs
$\\{M_{1},M_{2},\cdots,M_{N}\\}$ where $M_{i}$ has been fine-tuned on the data
silo $S_{i}$, and given a set of target indices
$T\subseteq\\{1,2,\cdots,N\\}$, the goal is to obtain a composed model
$M_{T}:=M_{T_{1}}\oplus\cdots\oplus M_{T_{|T|}}$ at inference time with no
additional training such that $M_{T}$ is able to correctly answer any question
about the information contained in the target silos $S_{i},\forall i\in T$ and
should fail to answer any question about information not contained in the
target silos $S_{j},\forall j\notin T$ as to not leak any information that the
desired model $M_{T}$ is not intended to have. Additionally, the target model
$M_{T}$ should be able to answer new union questions $q_{union,ij}\in S_{i\cup
j}$ where $i\in T\wedge j\in T$ where the question relies on information
contained in both $S_{i}$ and $S_{j}$. We note that the union questions
$q_{union,ij}$ are not answerable by any individual data silos, thus none of
the individual models $M_{i}$ are able to answer any union questions while a
successfully composed model should be able to answer such questions without
the need of any training.

It is critical that the composed model $M_{T}$ has no knowledge of information
silo that the user is not authorized to access, i.e. data silos $S_{i},i\notin
T$. Without this condition, a trivial solution is to train a single model
$M_{All}$ on all data silos $\\{1,\cdots,N\\}$ however this approach is
susceptible to leaking confidential information as the model would have
knowledge of information contained in silos that users are not authorized to
view and thus is not a valid approach. This approach is also problematic for
scenarios that employ security through contradiction, in that some silos may
directly contradict information in another silo in order to protect sensitive
information (SecureLLM could potentially solve this by applying weights to
silos of higher confidentiality). We refer to $M_{All}$ as the Exponential
Model that has seen every combination and such a model is used as an insecure
upper bound to performance in our experiments.

An alternative to composing fine-tunings while also preserving privacy would
be to create an exponential number of models, one for the powerset of
information silos. This would maximize performance and minimize the amount of
generalization needed, as long as one had a way to automatically generate
cross-silo questions, perhaps with another LLM. This is obviously impractical.
In essence, our method provides the advantages of the exponential approach but
with linear storage and training runtime.

###  3.1 Security as a relaxation

What sets security-related issues apart from other fine-tuning combination
scenarios is a relationship to a simple and easy-to-formalize idealized
problem. Assume that each silo has a disjoint alphabet, that the contents of
each silo is modeled by a state machine, and that the output the LLM must
produce should be an utterance that is accepted by the union of the per-silo
state machines. In this setting, security is simple. The optimal output
depends on one silo at a time and there is no need to mix information about
silos. The methods we provide here are optimal in this idealized setting
because of its likeness to SQL.

For SQL generation tasks the model primarily must insert table and column
names which are part of individual silos while following the overall structure
of SQL which is silo-independent. Of course, real security scenarios are
relaxations of this problem. For example, cross-silo question answering, is
faithful to this idealized problem if portions of the answers are derived
entirely from individual silos, while if they require cross-silo reasoning
then QA becomes a relaxation. Current methods, as we show below, are not well-
suited for this idealized problem or its relaxations. Formalizing this setting
will hopefully lead to new composition operators.

###  3.2 Composing fine-tunings

We discuss several existing methods, none of which perform well. A few other
plausible methods that also do not perform well are shown in the appendix.
Finally we describe two new methods that do perform well with one clear
winner.

LoraHub The LoraHub method for composition introduced by Huang et al. (2023)
is a two-step process involving element-wise summation of LoRA fine-tunings
(COMPOSE), and then learning weight optimizations via gradient-free methods to
apply to each fine-tuning (ADAPT). For this paper, we do not implement the
ADAPT stage because weights for every possible combination would need to be
learned, and we could not say that this process is completed at inference
time.

We observe that LoraHub performs poorly on the secure composition task. The
authors warn that combining too many fine-tunings can lead to poor
performance, however this cannot be the source of poor performance as we
compose only up to three LoRAs.

PEM Addition The summation method introduced by Zhang et al. (2023) is similar
to LoraHub, however, instead of summing the embeddings of the encoder and
decoder prior to receiving the input $x$, one executes each fine-tuning
independently at the attention-layer level, and then adds the result. This
version of summed composition shows improved performance over LoraHub.

Average of Adapter Weights Computing the simple average of each Lora fine-
tuning response, as suggested by Chronopoulou et al. (2023), $\sum_{i\to
n}{\frac{L_{i}}{n}}$, produced compositions that were 50% less effective than
PEM Addition in initial informal tests.

Variations of LogSumExp of Adapter Weights Du et al. (2020) proposes a
disjunctive composition process based on Energy Based Modeling,
$-logsumexp(-E_{1}(x),-E_{2}(x),\cdots)$. Every variation tried performed
significantly worse than PEM Addition, and upon closer inspection, this
process substantially distorts encoder and decoder embeddings.

Adapter Concatenation The Mangrulkar et al. (2022) library implements weight
concatenation, however we found that concatenating LoRA encoder/decoder fine-
tunings performed significantly worse than PEM Addition.

###  3.3 Our Methods

Maximum Difference The intuition behind this method is to select the
embeddings from each fine-tuning with the strongest response (either positive
or negative) at each attention layer. In order to accomplish this, each LoRA
fine-tuning is evaluated separately on input $x$. Then a mask of zeros with
the same dimension as the output is created, $h_{max}$, to aggregate LoRA
responses. For each LoRA fine-tuning response $L_{i}$, an element-wise
comparison is made, and if the absolute values of the fine-tuning response is
greater than the aggregated response, then the signed response from that fine-
tuning replaces the element in the aggregated response.

Logit Composition Given fine-tunings to compose $M_{1},\cdots,M_{n}$ and input
$x$, we define logit composition as performing the complete forward pass for
each fine-tuning independently to obtain logit probabilities. We select the
maximum value of each logit. One could instead sum logits for each fine-
tuning. We found little difference between the two implementations, although
the sum may have issues as the number of fine-tunings increases.

Note that we are not claiming this method to be a superior compositional
approach in every case. The requirements of compositional security are
different than those of some other compositional tasks. In a sense, by its
very nature, compositional security implies that most of the time every silo
but one is irrelevant and confused, and one silo is likely to produce
confident results. This motivates our compositional methods and explains why
other methods preform so poorly.

##  4 Data generation

Our goal is to automatically create a challenging dataset for compositions of
silos. There are countless other natural-language-to-SQL datasets out there,
which we do not aim to replace. As such, we focus specifically on within and
between silo questions. We also cover only a portion of SQL. We do not aim to
exhaustively test how well models understand SQL, we aim to understand how
well models generalize their knowledge from questions about individual silos
to questions that span silos. As such, we consider only a subset of SQL which
is otherwise an imposingly complex language.

We automatically generate SQL databases, one per silo, with 2-3 tables per
database, that share columns which can be joined together both within and
between databases. Databases are otherwise disjoint and on different topics.
For each database we generate natural language questions along their
equivalent SQL. Then, we generate questions and SQL pairs that span pairs and
triples of databases. Two methods are used to generate these pairs: a CFG (see
fig. 2) and ChatGPT 4 (see fig. 3). The CFG generates both the SQL and the
question in parallel. We do this at large scale, with 100,000 pairs per silo
or combination of silos. To ensure that our results scale to more realistic
queries we also generate 300 pairs per silo or combination of silos.

Q: What’s the average age of all teachers that are older than 72 or that
taught art classes for 9th graders in the school. Answer: ⬇ 1 SELECT
AVG(instructors.teacher_age) 2 FROM instructors INNER JOIN classes 3 ON
instructors.teacher_id = classes.teacher_id 4 WHERE instructors.teacher_age >=
72 5 OR classes.class_subject = ’art’ AND classes.level = 9 (a) Sample from
Silo 1 ($S_{1}$) Q: What’s the minimum height of all appliances in the
inventory that are currently unavailable in stores located in NY, CA, or MA
and with a rating higher than or equal to 2 stars. Answer: ⬇ 1 SELECT
MIN(inventory.height) 2 FROM inventory INNER JOIN store ON 3 store.store_id =
inventory.store_id 4 WHERE inventory.available = 0 5 AND (store.location =
’NY’ 6 OR store.location = ’CA’ 7 OR store.location = ’MA’) 8 AND
store.star_rating >= 2 (b) Sample from Silo 2 ($S_{2}$) Q: Provide the names
of all managers located in TX and the names of all teachers that are younger
than 86 and that taught english, sociology, or art classes that achieved a
grade higher than 89 in the database. Answer: ⬇ 1 SELECT store.name 2 FROM
classes 3 INNER JOIN instructors ON instructors.teacher_id =
classes.teacher_id 4 INNER JOIN store ON store.name = instructors.name 5 WHERE
store.location = ’TX’ 6 AND instructors.teacher_age <= 86 7 AND
(classes.class_subject = ’english’ OR classes.class_subject = ’sociology’ OR
classes.class_subject = ’art’) 8 AND classes.grade >= 89 (c) Sample from Union
Silo 1,2 ($S_{1\cup 2}$) Figure 2: Examples of input/output pairs of a
question paired with the target SQL query which are unconditional samples from
a Context-Free Grammar. Q: What is the average age of instructors who are aged
72 or older or teach art at level 9? Answer: ⬇ 1 SELECT
AVG(instructors.teacher_age) 2 FROM instructors INNER JOIN classes 3 ON
instructors.teacher_id = classes.teacher_id 4 WHERE instructors.teacher_age >=
72 5 OR classes.class_subject = ’art’ AND classes.level = 9 (a) Sample from
Silo 1 ($S_{1}$) that was rephrased with ChatGPT Q: What’s the minimum height
of all appliances in the inventory that are currently unavailable in stores
located in NY, CA, or MA and with a rating higher than or equal to 2 stars.
Answer: ⬇ 1 SELECT MIN(inventory.sloth) 2 FROM inventory INNER JOIN store ON 3
store.bear = inventory.bear 4 WHERE inventory.pony = 0 5 AND (store.alpaca =
’NY’ 6 OR store.alpaca = ’CA’ 7 OR store.alpaca = ’MA’) 8 AND store.raccoon >=
2 (b) Sample from Silo 2 ($S_{2}$) with obfuscated column names Figure 3:
Examples of input/output pairs of a question paired with the target SQL query
which (a) are from the ChatGPT rephrased silos and (b) use column names
obfuscated by an arbitrary but consistent mapping.

We limit the scope of generated SQL statements. All statements generated from
our CFG, an excerpt of which is shown in the appendix, are select statements
that only contain the SQL keywords from, natural join, and where. The majority
of the complexity is in the where clause which requires specialized knowledge
about the schema along with language comprehension to properly generate based
on the input question. The task for the LLM is to generate the where clause of
an SQL statement which answers the input question.

We introduce a useful normalization, for which we provide ablations in the
results section. This normalization is closely related to 6NF Date et al.
(2003). It ensures that joins are natural and that column names are easily
identified. In general, this transformation could help all SQL LLMs. One could
provide columns with unique names, factor away complex relationships, and
design redesign schemas such that joins are natural. This transformation is
bidirectional, one could normalize such a schema, generate a query against it,
and then transform those queries back to the original schema. Little to no
work exists on database normalizations that are specific to LLMs. Existing
database normalizations focus on ease of query generation for humans and
concerns like execution efficiency for machines. As described in the results
section, our composition methods are far superior irrespective of this
normalization. But we believe it is a valuable observation that is likely to
lead to many more LLM-specific normalizations as they become serious consumers
of SQL.

From each SQL schema we randomly generate an instance of that SQL database.
For each sample, the LLM’s output is assembled into an SQL statement then
executed on the database to obtain the query results, if the query results are
exactly equivalent to the query result of the ground truth SQL statement then
the LLM’s output is considered correct. Furthermore, we ensure that each query
in training and validation responds with at least one record to avoid trivial
false positives. Given that natural language questions can lead to long
queries, this is a high bar, as even the smallest mistake leads to zero
performance.

We employ a second score that parses the generated query conditions into a
tree then calculates the tree-edit distance Zhang et al. (1996) between the
ground query and the generated query. This is the number of edit operations
required to transition between the two, which are normalized by the number of
nodes in the ground tree. These are averaged across all queries for a silo or
collection of silos. This edit distance score provides a far more fine-grained
view into the performance of models, fine-tunings, and compositions of fine
tunings.

CFG | Baseline | Baseline |  |  | Ours | Ours (Logits) |
---|---|---|---|---|---|---|---
Generated | Exponential | Generalized |  | PEM | (Maximum | Without DB | Ours
| Model | Model | LoraHub | Addition | Difference) | Normalization | (Logits)
$\text{Silos}_{1}$ | 0.0 (100.0%) | 0.0 0(98.3%) | 1.9 | 1.0 | 0.4 | 0.4 | 0.1
$\text{Silos}_{2}$ | 0.0 0(96.7%) | 0.0 (100.0%) | 2.7 | 0.7 | 0.3 | 0.2 | 0.0
$\text{Silos}_{3}$ | 0.0 (100.0%) | 0.0 (100.0%) | 1.2 | 0.7 | 0.2 | 0.1 | 0.1
$\text{Silos}_{1\cup 2}$ | 0.0 0(98.3%) | 1.0 00(0.0%) | 1.8 | 1.0 | 0.9 | 0.7 | 0.3
$\text{Silos}_{1\cup 3}$ | 0.0 0(99.2%) | 0.5 00(0.0%) | 1.6 | 0.7 | 0.7 | 0.6 | 0.2
$\text{Silos}_{2\cup 3}$ | 0.0 (100.0%) | 0.4 00(1.7%) | 1.7 | 0.7 | 0.7 | 0.5 | 0.4
$\text{Silos}_{1\cup 2\cup 3}$ | 0.0 (100.0%) | 0.5 00(1.7%) | 2.2 | 0.7 | 0.7 | 0.4 | 0.4
$\mu\pm\sigma$ | $0.00\pm 0.00$ | $0.35\pm 0.35$ | $1.88\pm 0.45$ | $0.78\pm 0.13$ | $0.55\pm 0.24$ | $0.42\pm 0.21$ | $\boldsymbol{0.21\pm 0.12}$

Table 1: Normalized tree edit distance for CFG-generated question and SQL
pairs with accuracy reported in parentheses (average and std. dev. only
applies to normalized tree edit distance). The exponential baseline sees all
combinations of silos at training time, this is intractable and insecure, but
has maximal performance. The generalization baseline sees all silos but not
combinations of silos at training time, this is tractable but insecure. The
other methods are used to build a SecureLLM. As described above, we do not
include detailed reports on methods which underperform both LoraHub and PEM
Addition. Note that our methods significantly outperform prior work. They
retain all the generalization performance there is (since the generalization
model sees all silos at once, while the fine-tunings each see silos
separately, the generalization model should nominally perform better), even
outperforming the generalization baseline.

GPT | Baseline | Baseline |  |  | Ours | Ours (Logits) |
---|---|---|---|---|---|---|---
Generated | Exponential | Generalized |  | PEM | (Maximum | Without DB | Ours
| Model | Model | LoraHub | Addition | Difference) | Normalization | (Logits)
$\text{Silos}_{1}$ |  000.0 (87.5%) | 0.1 (79.2%) | 2.0 | 1.1 | 0.5 | 0.6 | 0.3
$\text{Silos}_{2}$ | 0.2 (60.8%) | 0.2 (56.7%) | 2.9 | 1.0 | 0.5 | 0.3 | 0.4
$\text{Silos}_{3}$ | 0.1 (56.7%) | 0.2 (51.7%) | 1.4 | 1.1 | 0.5 | 0.4 | 0.2
$\text{Silos}_{1\cup 2}$ | 0.2 (20.8%) | 0.4 0(0.0%) | 2.1 | 0.7 | 0.6 | 0.6 | 0.2
$\text{Silos}_{1\cup 3}$ | 0.2 (29.2%) | 0.4 0(0.0%) | 1.6 | 1.0 | 0.6 | 0.6 | 0.4
$\text{Silos}_{2\cup 3}$ | 0.1 (33.3%) | 0.3 0(3.3%) | 2.3 | 0.6 | 0.5 | 0.4 | 0.3
$\text{Silos}_{1\cup 2\cup 3}$ | 0.1 (50.0%) | 0.3 0(2.5%) | 2.1 | 0.6 | 0.5 | 0.4 | 0.2
$\mu\pm\sigma$ | $0.15\pm 0.06$ | $0.28\pm 0.13$ | $2.06\pm 0.45$ | $0.85\pm 0.21$ | $0.52\pm 0.05$ | $0.48\pm 0.11$ | $\boldsymbol{0.30\pm 0.07}$

Table 2: Results on the ChatGPT-paraphrased questions. See table 1 for a
detailed explanation. Our method continues to outperform all others, and again
outperforms the generalization baseline. Scaling to realistic queries still
favours our approach.

Obfuscated | Baseline | Baseline |  |  | Ours | Ours (Logits) |
---|---|---|---|---|---|---|---
Generated | Exponential | Generalized |  | PEM | (Maximum | Without DB | Ours
| Model | Model | LoraHub | Addition | Difference) | Normalization | (Logits)
$\text{Silos}_{1}$ | 0.0 0(99.2%) | 0.0 0(94.2%) | 2 | 1.1 | 0.5 | 0.5 | 0.2
$\text{Silos}_{2}$ | 0.0 0(92.5%) | 0.0 (100.0%) | 3.1 | 1.4 | 0.5 | 0.4 | 0.4
$\text{Silos}_{3}$ | 0.0 (100.0%) | 0.0 (100.0%) | 0.9 | 0.8 | 0.5 | 0 | 0.1
$\text{Silos}_{1\cup 2}$ | 0.0 0(80.8%) | 0.7 00(0.8%) | 1.6 | 2.2 | 1.1 | 0.9 | 0.5
$\text{Silos}_{1\cup 3}$ | 0.0 0(98.3%) | 0.4 00(0.0%) | 1.3 | 1.4 | 0.7 | 0.6 | 0.4
$\text{Silos}_{2\cup 3}$ | 0.0 0(77.5%) | 0.6 00(1.7%) | 1.6 | 2.5 | 0.9 | 0.7 | 0.8
$\text{Silos}_{1\cup 2\cup 3}$ | 0.0 (100.0%) | 0.4 00(1.7%) | 1.9 | 2.5 | 1.0 | 0.6 | 0.3
$\mu\pm\sigma$ | $0.01\pm 0.01$ | $0.31\pm 0.28$ | $1.76\pm 0.65$ | $1.70x\pm 0.65$ | $0.73\pm 0.24$ | $0.54\pm 0.24$ | $\boldsymbol{0.36\pm 0.22}$

Table 3: Following table 1 while obfuscating the table names. Our methods
continue to perform well showing that they are not taking advantage of a
trivial solution. For real-world applications, one would likely use a much
larger baseline model. This would improve the absolute execution scores, which
would method would benefit from since it retains the performance of the
underlying model in this challenging compositional task.

##  5 Experiments

To demonstrate the capabilities of model composition at inference-time, we
first begin by obtaining individual fine-tunings that are knowledgeable in a
single silo by fine-tuning a Llama-2-7B model for each silo separately. The
fine-tuning results in a Low-Rank Adaptation (LoRA) for each silo which can
independently be applied to the base Llama-2-7b model. Once the individual
LoRA fine-tunings are obtained we compose them using one of several
compositional schemes with the requirement that the composition happens at
inference time with no additional training. We additionally train two insecure
baseline models that act as an upper-bound using LoRA, the baseline
generalized model is trained on all the individual silos together and must
then generalize it’s knowledge to the union silos. While the baseline
exponential model also breaks privacy guarantees by training on all the
individual silos along with the union silos, the term exponential refers to
the fact that training such a model while preserving privacy would mean that
$\mathcal{O}(2^{N})$ models would need to be trained where $N$ is the number
of silos in the database. Both baseline models are considered insecure as
there is no method of removing knowledge about certain silos at inference time
when the user does not have the sufficient credentials unlike our proposed
SecureLLM method which can remove and add fine-tunings with each silo’s
knowledge at inference time. We fine-tune all models with one epoch until
saturation (achieving near 100% accuracy on the CFG validation set) using a
frozen Llama-2 7B (Touvron et al., 2023) with a trainable LoRa fine-tuning (Hu
et al., 2021) using LoRa parameters $r=8,\alpha=32$ and a dropout (Srivastava
et al., 2014) of $0.1$, an Adam optimizer (Kingma and Ba, 2014) with a
learning rate of $0.0002$, a batch size of $32$, and a weight decay of
$0.002$.

We report the results of the two insecure baseline models along with the
secure composition ($M_{1}\oplus M_{2}\oplus M_{3}$ where $M_{i}$ was trained
on $\text{Silo}_{i}$) using multiple compositional methods (section 3.2,
section 3.3) including our best method (in section 3.3) with and without using
6NF-like database normalization, which is equivalent to the scenario where a
user has credentials to access $T=\\{1,2,3\\}$. We note that neither the
baseline generalized model nor the secure compositions have seen the union
Silos ($S_{1\cup 2}$, $S_{1\cup 3}$, $S_{2\cup 3}$, and $S_{1\cup 2\cup 3}$)
and that only the exponential baseline model has been trained on those silos.
The performance of the composed fine-tunings on the individual Silos would
give an indication as to whether the resulting composition is able to retain
the knowledge of each individual fine-tuning from each separate Silo; This
performance is expected to be traded off for privacy while the better
compositional methods mitigate the extent of this trade off and maintain
maximal privacy. The performance on the union Silos indicates whether the
composed fine-tunings are able to successfully generalize knowledge from the
individual fine-tunings which is an essential component in answering questions
that no individual fine-tuning or silo can answer.

##  6 Results

The highest performance one can possibly achieve is if the LLM is trained not
just on every silo but the powerset of silos, i.e., the insecure baseline
exponential model described above. Realistically, our model is upper-bounded
by a variant of the model that sees all of the silos at training time, but
sees no combination of silos. Both of these are insecure, in that they have
access to all of the data. Our goal is to find a method to combine individual
silo fine-tunings to reproduce the performance of the baseline generalized
model.

Raw overall performance is not a relevant metric, although we report it in
each case for the baseline models. Raw performance is a function of the size
of the model. And we use the modestly sized Llama-2-7B. What is critical is
the fraction of retained performance. This is what we focus our results on,
the difference in tree edit distance.

LoraHub and PEM addition were the only two competitive methods that were
previously published. All other methods described earlier performed so poorly
we did not include them in the final results table to make room for additional
experiments.

In table 1 we report performance for the CFG-generated data. Note that for
every probe silo combination our methods have by far the lowest tree edit
distances. Even without the database normalization described above, our
methods outperform all others in every case. With the database normalization
our method retains all the performance that exists, i.e., it nearly always
matches the tree edit distance of the baseline generalized model.

One might wonder if these results are merely an artifact of the CFG-based
approach. When replicating the same experiment with sentences rephrased by
ChatGPT, see table 2, we come to the same conclusions. LoraHub and PEM
Addition, along with all prior methods we attempted significantly underperform
our approach. Note that this is an extremely challenging test set as the
ChatGPT paraphrases are only used for testing, not for training.

To guard against a potential trivial solution to this problem, we also
introduce a column-name obfuscated version. A model that is good at guessing a
likely name for a table based on the entities it refers to might otherwise get
a leg up. We are interested in the ability of models to retain compositional
reasoning, rather than circumventing the task. In any case, in real world
conditions column names are often rather complex. In table 3 each column is
given an arbitrary but stable and coherent name, in this case an animal.
Relative to table 1 our method loses little performance, meaning that it
encourages compositional reasoning.

##  7 Conclusion

LLM security is critical to numerous commercial and government applications.
We take a different view of LLM security compared to that of prior work, one
where we import the traditional notion of access security to LLMs. This is
enabled by the new compositional methods we introduce that prove themselves to
be effective.

Note that our experiments are an extreme case, one where no prior knowledge is
useful for understanding the structure of a silo, particularly in the case
where column names are obfuscated. We also consider a weak LLM, Llama-2-7B. We
showed that these novel composition methods are able to take advantage of the
generalization capabilities of the LLM with SQL edit distances that are the
same or even at times better than the baseline LLM when it attempts to
generalize. In other words, fine-tuning the LLM on each silo jointly, performs
as well as fine-tuning on each silo individually and combining the fine-
tunings. This is as much as one could hope for. Practical applications would
need to use a far stronger underlying LLM to achieve high execution accuracy.

There are numerous possible extensions of this work, including applications to
document QA where each silo is a collection of documents rather than a
database. One possible followup could look at the converse task, given a
question determine the silos necessary to answer it. This could be used to
monitor conversations or to automatically mark the security level of an
exchange between users. Another possible direction would be to look at
negative silos that exclude information. A negative silo would explicitly
avoid a topic, which would prevent accidental leaks. Models could rewrite text
or data to refer or exclude particular silos. The traditional world of access
security is rich with problems for LLMs to address, and our work opens up the
way for doing so. In addition, by providing provable security, i.e., there can
be no leaks from silos the user doesn’t have access to, we take a key step
toward enabling the use of LLMs in secure environments.

##  8 Additional Information

###  8.1 Limitations

We disentangle and address a very specific slice of LLM safety, one that is
often commingled with a larger story about safety. SecureLLM only concerns
itself with security in the traditional sense: quantized access permissions to
data. It relies on traditional security techniques to manage access
permissions. There is a widely held belief that LLM security is a totally
disjoint new field, but as we show, with the SecureLLM approach we can reduce
many of those security problems back to traditional access permission issues.
Many security problems of LLM are manageable through traditional means when
one can assume that only vetted actors have access, just as they are with
current document storage systems. The same systems which ensure patient
privacy, financial privacy, and that manage secret information today can be
used to manage collections of fine-tunings, and the same supervision methods
can trace access to the LLM.

From this perspective SecureLLM solves data leakage and prompt injection
attacks, in the same sense that traditional security solves data leakage:
those without permissions cannot access this information, and those with
permissions have full access with training and supervision. Although, in the
future one might imagine extensions that provide more fine-grained
permissions. Organizations are already set up for this form of security, both
for managing the user permissions and for the associated documents, making the
deployment of SecureLLM straightforward. In settings where this structure is
not available or not appropriate, SecureLLM is not directly applicable, but
those scenarios never had meaningful security to begin with.

Explicitly out of scope are other notions of safety and security. For example,
the LLM may still fabricate information, produce toxic or biased results,
follow guidance that it should not, etc. The only mitigation that we offer is
that only a user that has permissions to that data will be impacted directly;
hopefully this user will receive appropriate training about the limitations
and dangers of LLMs.

###  8.2 Ethics

SecureLLM could pose some ethical issues. At the moment, surveillance is
limited by the need to process a deluge of data. This results in mostly
processing metadata. Enabling LLMs to work in secure environments could
contribute to large-scale monitoring, detection, and tracking. Novel uses of
LLMs in secure environments can advance numerous defense applications. As with
many other dual-use technologies, we hope that this work will be used for
positive ends.

###  8.3 Computational Considerations

We use NVIDIA Titan RTX 24GB VRAM GPUs for all our experiments.

For all of our PEFT parameters, less than one GPU-hours per PEFT was required
for training. Between around one GPU-hours was required for composition
growing with respect to the number of compositions. For each run,
approximately 20 GB of VRAM is needed as we use half precision for all
training and inference. Each PEFT can be trained and inferenced on one GPU.

We estimate a total of 10 GPU-hours is required to replicate results for
training, and 20 GPU-hours is required to perform the same experiments
described in this manuscript.

###  8.4 Reproducibility

All code and data required to reproduce our work will be provided at this
GitHub repository under the MIT license https://github.com/Scuwr/SecureLLM.

###  8.5 Acknowledgements

This work was supported by the DARPA Machine Common Sense (MCS) program, the
Center for Brains, Minds, and Machines, NSF STC award CCF1231216, the NSF
award 2124052, the MIT CSAIL Machine Learning Applications Initiative, the
MIT-IBM Watson AI Lab, the DARPA Artificial Social Intelligence for Successful
Teams (ASIST) program, the DARPA Knowledge Management at Scale and Speed
(KMASS) program, the United States Air Force Research Laboratory and the
Department of the Air Force Artificial Intelligence Accelerator under
Cooperative Agreement Number FA8750-19-2-1000, the Air Force Office of
Scientific Research (AFOSR) under award number FA9550-21-1-0014, and the
Office of Naval Research under award number N00014-20-1-2589 and award number
N00014- 20-1-2643. The views and conclusions contained in this document are
those of the authors and should not be interpreted as representing the
official policies, either expressed or implied, of the Department of the Air
Force or the U.S. Government. The U.S. Government is authorized to reproduce
and distribute reprints for Government purposes notwithstanding any copyright
notation herein.

## References

  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep learning with differential privacy.  In _Proceedings of the 2016 ACM SIGSAC conference on computer and communications security_ , pages 308–318.
  * Carlini et al. (2019) Nicholas Carlini, Chang Liu, Úlfar Erlingsson, Jernej Kos, and Dawn Song. 2019\.  The secret sharer: Evaluating and testing unintended memorization in neural networks.  In _28th USENIX Security Symposium (USENIX Security 19)_ , pages 267–284.
  * Carlini et al. (2021) Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. 2021.  Extracting training data from large language models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2633–2650.
  * Chronopoulou et al. (2023) Alexandra Chronopoulou, Matthew E Peters, Alexander Fraser, and Jesse Dodge. 2023\.  Adaptersoup: Weight averaging to improve generalization of pretrained language models.  _arXiv preprint arXiv:2302.07027_.
  * Date et al. (2003) C. J. Date, Hugh Darwen, and Nikos A. Lorentzos. 2003.  _Temporal Data and the Relational Model A detailed investigation into the application of interval and relation theory to the problem of temporal database management_.  Morgan Kaufmann Publishers.
  * Du et al. (2020) Yilun Du, Shuang Li, and Igor Mordatch. 2020.  Compositional visual generation and inference with energy based models.  _arXiv preprint arXiv:2004.06030_.
  * Hisamoto et al. (2020) Sorami Hisamoto, Matt Post, and Kevin Duh. 2020.  Membership inference attacks on sequence-to-sequence models: Is my data in your machine translation system?  _Transactions of the Association for Computational Linguistics_ , 8:49–63.
  * Hu et al. (2021) Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2021.  Lora: Low-rank adaptation of large language models.  _arXiv preprint arXiv:2106.09685_.
  * Hu et al. (2022) Hongsheng Hu, Zoran Salcic, Lichao Sun, Gillian Dobbie, Philip S Yu, and Xuyun Zhang. 2022.  Membership inference attacks on machine learning: A survey.  _ACM Computing Surveys (CSUR)_ , 54(11s):1–37.
  * Huang et al. (2023) Chengsong Huang, Qian Liu, Bill Yuchen Lin, Tianyu Pang, Chao Du, and Min Lin. 2023\.  Lorahub: Efficient cross-task generalization via dynamic lora composition.  _arXiv preprint arXiv:2307.13269_.
  * Inan et al. (2021) Huseyin A Inan, Osman Ramadan, Lukas Wutschitz, Daniel Jones, Victor Rühle, James Withers, and Robert Sim. 2021.  Training data leakage analysis in language models.  _arXiv preprint arXiv:2101.05405_.
  * Kingma and Ba (2014) Diederik P Kingma and Jimmy Ba. 2014.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_.
  * Li et al. (2021) Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. 2021.  Large language models can be strong differentially private learners.  _arXiv preprint arXiv:2110.05679_.
  * Mangrulkar et al. (2022) Sourab Mangrulkar, Sylvain Gugger, Lysandre Debut, Younes Belkada, Sayak Paul, and Benjamin Bossan. 2022.  Peft: State-of-the-art parameter-efficient fine-tuning methods.  https://github.com/huggingface/peft.
  * McMahan et al. (2017) H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. 2017.  Learning differentially private recurrent language models.  _arXiv preprint arXiv:1710.06963_.
  * Nasr et al. (2019) Milad Nasr, Reza Shokri, and Amir Houmansadr. 2019.  Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.  In _2019 IEEE symposium on security and privacy (SP)_ , pages 739–753. IEEE.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The journal of machine learning research_ , 15(1):1929–1958.
  * Sun et al. (2023) Tianxiang Sun, Zhengfu He, Qin Zhu, Xipeng Qiu, and Xuanjing Huang. 2023.  Multitask pre-training of modular prompt for Chinese few-shot learning.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 11156–11172, Toronto, Canada. Association for Computational Linguistics.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _arXiv preprint arXiv:2307.09288_.
  * Yu et al. (2021) Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. 2021.  Differentially private fine-tuning of language models.  _arXiv preprint arXiv:2110.06500_.
  * Zanella-Béguelin et al. (2020) Santiago Zanella-Béguelin, Lukas Wutschitz, Shruti Tople, Victor Rühle, Andrew Paverd, Olga Ohrimenko, Boris Köpf, and Marc Brockschmidt. 2020.  Analyzing information leakage of updates to natural language models.  In _Proceedings of the 2020 ACM SIGSAC conference on computer and communications security_ , pages 363–375.
  * Zhang et al. (2023) Jinghan Zhang, Shiqi Chen, Junteng Liu, and Junxian He. 2023.  Composing parameter-efficient modules with arithmetic operations.  _arXiv preprint arXiv:2306.14870_.
  * Zhang et al. (1996) Kaizhong Zhang, Jason TL Wang, and Dennis Shasha. 1996.  On the editing distance between undirected acyclic graphs.  _International Journal of Foundations of Computer Science_ , 7(01):43–57.
  * Zhao et al. (2022) Xuandong Zhao, Lei Li, and Yu-Xiang Wang. 2022.  Provably confidential language modelling.  _arXiv preprint arXiv:2205.01863_.
  * Zyskind et al. (2023) Guy Zyskind, Tobin South, and Alex Pentland. 2023.  Don’t forget private retrieval: distributed private similarity search for large language models.  _arXiv preprint arXiv:2311.12955_.

##  Appendix A Negative Results

We briefly outline some methods that seemed promising but did not perform
well, far worse than PEM Addition in testing.

Strongest Output Embedding Response Only using the LoRA Layer, $L_{i}$, that
generated the strongest output embedding response at a given attention layer
produced compositions that were 50% less effective than PEM Addition in
initial informal tests.

Element-wise Maximum Using the standard max function in pytorch,
$max\left([L_{1}(x),\cdots,L_{n}(x)],dim=0\right)$, produced compositions that
were 50% less effective than PEM Addition in initial informal tests.

##  Appendix B An example of the Context-Free Grammar (CFG)

We provide an excerpt from the CFG of one of the silos in fig. 4 which is
parsed by our custom parser as to jointly construct a natural language
questions alongside an SQL query.

⬇

1

2:1:root:{whats_the} average {prop_number} {suffix}:T=AVG

3:1:root:{whats_the} maximum {prop_number} {suffix}:T=MAX

4:1:root:{whats_the} minimum {prop_number} {suffix}:T=MIN

5:1:root:{list_the} {prop_number} {suffix}:T=none

6:1:root:{whats_the} number of {prop_countable} {suffix}:T=COUNT

7:1:root:{list_the} names of all teachers {teacher_multi_cond} {suffix}:T=none
; WANT=instructors.name ; TABLES = instructors

8# {more not shown here}

9:1:list_the:output a list of the:none

10:1:list_the:provide a list of the:none

11:1:whats_the:what is the:none

12:1:whats_the:what’s the:none

13:1:suffix:in our records:none

14:1:suffix:in the school:none

15# {more not shown here}

16

17:1:prop_countable:teachers {teacher_multi_cond}:TABLES = instructors

18:1:prop_countable:{class}:TABLES = classes

19:1:prop_number:age of all teachers
{teacher_multi_cond}:WANT=instructors.teacher_age ; TABLES = instructors

20:1:prop_number:grade of all {class}:WANT=classes.grade ; TABLES = classes

21# {more not shown here}

22:1:teacher_multi_cond::none

23:3:teacher_multi_cond:{teacher_cond_taught}:none

24:2:teacher_multi_cond:{teacher_cond_age}:none

25:4:teacher_multi_cond:{teacher_cond_age} and {teacher_cond_taught}:none

26:4:teacher_multi_cond:{teacher_cond_age} or
{teacher_cond_taught}:ADDER_PROPS={"comb":"OR"}

27:1:teacher_cond_taught:that taught {class}:TABLES = classes

28:1:teacher_cond_age:that are older than
{number,20,90}:CONDITIONS=instructors.teacher_age >= {0}

29# {more not shown here}

30

31:1:class:{subject} classes:none

32:2:class:{subject} classes that {class_avg}:none

33:2:class:{subject} classes that {class_avg} and {class_year}:none

34:2:class:{subject} classes {class_level_single}:none

35:2:class:{subject} classes {class_level_single} that {class_year}:none

36:1:class_avg:achieved a grade higher than
{number,60,95}:CONDITIONS=classes.grade >= {0}

37:1:class_year:were conducted before
{number,2000,2020}:CONDITIONS=classes.year <= {0}

38# {more not shown here}

39

40:1:subject::none

41:1:subject:{single_subject}:CONDITIONS=classes.class_subject = ’{0}’

42:1:subject:{single_subject} or
{single_subject}:CONDITIONS=classes.class_subject = ’{0}’ OR
classes.class_subject = ’{1}’

43# {more not shown here}

44:1:single_subject:math

45:1:single_subject:economics

46:1:single_subject:history

47# {more not shown here}

Figure 4: An excerpt of the Context-Free Grammar for Silo 1 ($S_{1}$). The
content is shortened with many lines removed as to fit inside the figure while
conveying the general structure of the grammar. Each rule contains a pair of a
natural language phrase followed by a colon and the sufficient information
required to properly build the resulting SQL which is our own custom


# Computing the vertex connectivity of a locally maximal 1-plane graph in
linear time

Therese Biedl and Karthik Murali  David R. Cheriton School of Computer
Science, University of Waterloo, Waterloo, Canada
<EMAIL_ADDRESS>Work of TB supported by NSERC, FRN
RGPIN-2020-03958.

###### Abstract

It is known that the vertex connectivity of a planar graph can be computed in
linear time. We extend this result to the class of locally maximal 1-plane
graphs: graphs that have an embedding with at most one crossing per edge such
that the endpoints of each pair of crossing edges induce the complete graph
$K_{4}$.

##  1 Introduction

One of the oldest problems in graph algorithms is the _connectivity problem_ :
Given a connected graph $G$, what is the smallest number of vertices (denoted
by $\kappa(G)$) that need to be removed from $G$ to make it disconnected? This
has applications in security and network reliablity; it is hence important to
be able to test efficiently whether $\kappa(G)$ is sufficiently large and to
find a corresponding _minimum separating set_ , i.e., a smallest set of
vertices whose removal disconnects the graph.

Let $G$ be a graph with $n$ vertices and $m$ edges. It is very easy to test in
linear time (i.e. $O(m+n)$-time) whether $\kappa(G)\geq 1$ by running any
graph traversal algorithm, and $\kappa(G)\geq 2$ can easily be tested in
linear time by modifying a depth-first search [Tar72]. Testing whether
$\kappa(G)\geq 3$ in linear time is harder; an algorithm for this was proposed
by Hopcroft and Tarjan in 1973 [HT73], but it had some errors which were
pointed out and corrected in 2000 by Gutwenger and Mutzel [GM00]. For the
general question of determining the connectivity of a graph, for the longest
time the fastest known algorithms ran in $O(n^{2})$ time. For the simplest
case when $m\in O(n)$, and hence $\kappa(G)\in O(1)$, Kleitman showed how to
determine the connectivity in $O(n^{2})$ time [Kle69]. For $\kappa(G)=4$ and
any $m$, the first $O(n^{2})$ algorithm was by Kanevsky and Ramachandran
[KR91]. For $\kappa(G)\in O(1)$ and any $m$, the first $O(n^{2})$ algorithm
was by Nagamochi and Ibaraki [NI92].

The last few years have seen some breakthroughs for computing vertex
connectivity. Recently, Forster et al. [FNY+20] used fast local-cut algorithms
to show that when $\kappa(G)\in O(\text{polylogn})$, there is a randomised
algorithm that takes time $\tilde{O}(m+nk^{3})$111$\tilde{O}$ hides poly-
logarithmic factors, $\hat{O}$ hides arbitrarily small polynomial factors. to
compute vertex connectivity, and hence is nearly linear. As for deterministic
algorithms, when $k:=\kappa(G)<n^{1/8}$, Gao et al. [GLN+19] used balanced
sparse cuts to give a sub-quadratic time algorithm for computing vertex
connectivity; the running time is
$\widehat{O}(m+\min\\{n^{1.75}k^{1+k/2},n^{1.9}k^{2.5}\\})$11footnotemark: 1.

In this paper, we consider the connectivity problem for special kinds of graph
classes. Our work was motivated by a result for planar graphs, i.e., graphs
that can be embedded on the plane such that no edge crosses another. These
graphs have been extensively studied, and their structural properties have
been used in the development of many efficient algorithms. Any simple planar
graph has at most $3n-6$ edges, therefore any planar graph $G$ contains a
vertex with at most five distinct neighbours, and so $\kappa(G)\leq 5$. The
recent results on vertex connectivity show that there exists a near-linear-
time randomized algorithm to determine the connectivity of a planar graph. But
this result is actually much older: Eppstein [Epp99] gave in 1999 a
deterministic linear-time algorithm to test whether the vertex connectivity of
a planar graph is at least $k$ (which by $\kappa(G)\leq 5$ gives a linear-time
algorithm to determine the connectivity). This is based on the following
approach. Given a planar graph $G$, let the _radialisation_ $\Lambda(G)$ be
the planar graph obtained by adding a new face vertex inside each face of $G$
and connecting the face vertex to all the vertices on the boundary of the
face. Eppstein credits Nishizeki with the observation that any minimum
separating set $S$ corresponds to a separating cycle $X$ in $\Lambda(G)$ that
separates two vertices of $G$,222Eppstein actually states the condition
slightly differently, demanding $X$ to separate two vertices of $G$ in
$\Lambda(G)\setminus E(G)$, but we believe this to be incorrect, since the two
separated vertices could then be connected via an edge in $G$. has length
$2|S|$, visits all vertices of $S$, and uses only edges added during the
radialisation. Determining the connectivity of a planar graph $G$ hence
reduces to finding cycles of length $2k$ (for $k=1,2,3,4$) in $\Lambda(G)$
that satisfy these properties; this can be done by modifying Eppstein’s
subgraph isomorphism testing algorithm slightly [Epp99].

Our goal in this paper is to generalize these results to a _1-planar graph_ ,
i.e., a graph that can be embedded in the plane with at most one crossing per
edge. This graph class was first introduced by Ringel [Rin65] and has excited
much interest recently, both with respect to the theoretical properties of
these graphs and for developing algorithms tailored to this graph class. See a
2017 overview paper [KLM17] as well some chapters in a recent book [HT20] for
more details. To our knowledge, no previous results concerning connectivity-
testing in 1-planar graphs have appeared. Any simple 1-planar graph has at
most $4n-8$ edges [BSW83], and therefore trivially $\kappa(G)\leq 7$. With the
recent breakthrough results, there exists a randomized (but complicated)
algorithm to determine the connectivity of a 1-planar graph in near-linear
time. But our aim is to instead extend the approach by Eppstein, and therefore
gain more insight into the structure of a 1-planar graph, as well as a
deterministic linear-time algorithm for the connectivity of a 1-planar graph.

(a)

(b)

Figure 1: An example to illustrate that a minimum separating of a 1-plane
graph $G$ does not always correspond to a bounded length separating cycle in
$\Lambda(G)$.

For 1-planar graphs, we define the analogue of radialisation, called radial
planarisation, where we first planarise the graph by adding dummy vertices at
crossing points, and then radialise. Observe that the straight-forward
approach of finding separating cycles in the radial planarisation $\Lambda(G)$
does not always work. Consider Figure 1(a) and the two bold vertices, which
form a minimum separating set $S$. In $\Lambda(G)$ (Figure 1(b)), there is no
cycle of length $2|S|=4$ that contains these two vertices, and the example can
easily be extended to show that in fact no cycle of length $O(1)$ goes through
both vertices of $S$. So not every minimum separating set can give rise to a
short separating cycle in $\Lambda(G)$. However, as we will show, the approach
via radial planarisation _does_ work for a subclass of 1-planar graphs.
Specifically, call a 1-planar graph _locally maximal_ [FHM+20] if it has a
1-planar embedding in the plane where the endpoints of any crossing induce the
complete graph $K_{4}$. As our main result in this paper, we show that for
such 1-planar graphs, minimum separating sets indeed correspond to separating
cycles (with some other constraints) in $\Lambda(G)$. As such, testing
connectivity again reduces to subgraph isomorphism (with some other
constraints), and since $\Lambda(G)$ is planar, this can be tested in linear
time.

##  2 Preliminaries

(We assume that the reader is familiar with basic concepts of graph theory.
See e.g. [Die18].) Let $G=(V,E)$ be a graph, which we assume to have no loops
since they are irrelevant for connectivity. A drawing of $G$ on the plane maps
each vertex to a distinct point and each edge to a distinct curve on the
plane. We assume that all graph drawings are good [Sch13], i.e., each edge is
drawn as a simple non-self-intersecting arc connecting its endpoints, and any
two edges intersect at most once, either at a common endpoint or in the
interior of the edges. A planar graph is a graph that can be drawn on the
plane such that no two edges cross; such a drawing is called a planar drawing.
A planar drawing divides the plane into connected regions called faces. A face
is identified by its facial circuit, which is a directed walk along the
boundary of the face such that the face lies to the left of all the edges in
the directed walk. This set of facial circuits is called a planar embedding.
All drawings of a planar graph with the same embedding are equivalent, and are
said to respect the planar embedding. A planar graph with a given planar
embedding is called a plane graph.

Let $G$ be a plane graph with a drawing that respects the planar embedding,
and let $v$ be a vertex. The rotation at $v$, denoted by $\rho(v)$, is the
clockwise sequence of edges incident with $v$. If a set of edges
$(v,w_{1}),\dots,(v,w_{k})$ incident with $v$ occur in the same order (not
necessarily consecutive) in $\rho(v)$, we write
$\langle(v,w_{1}),(v,w_{2}),\dots,(v,w_{k})\rangle\subseteq\rho(v)$. An angle
at $v$ is a sequence $\langle u,v,w\rangle$, where $(v,w)$ and $(v,u)$ are
consecutive edges in $\rho(v)$. A _bigon_ is a closed face that contains
exactly two angles. The rotation system is the set of rotations at all the
vertices of $G$.

A crossing in a drawing of a graph is a pair of edges that intersect at a
point that is not a vertex. The point of intersection is called the crossing
point. An endpoint of a crossing is a vertex that is incident with either edge
of the crossing. Since all graph drawings are good, each crossing has four
distinct endpoints.

A 1-planar graph is a graph that can be drawn on the plane such that each edge
is crossed at most once by another edge; such a drawing is called a 1-planar
drawing. A 1-planar graph on $n$ vertices has $O(n)$ edges and crossing points
[BSW83, PT97]. For a given 1-planar drawing of a graph $G$, the planarisation
of $G$, denoted by $G^{\times}$, is obtained by placing a dummy vertex at each
crossing point so that the drawing becomes planar. The set of all facial
circuits of a planarised 1-planar drawing is called a 1-planar embedding.
Given a planar graph, one can obtain a planar embedding in linear time (see
e.g. [HT08] and the references therein). In contrast, testing 1-planarity is
NP-hard [GB07, KM13]. Hence for algorithmic purposes, we must assume that a
1-planar graph comes with a given 1-planar embedding; such a graph is called a
1-plane graph.

(a)

(b)

Figure 2: A locally maximal 1-plane graph and its radial planarisation.

A _locally maximal 1-plane graph_ is a 1-plane graph $G$ in which the
endpoints of each crossing induce a $K_{4}$ (Figure 2(a)). Thus, if
$\\{(u,v),(w,x)\\}$ is a crossing in $G$ then all edges $(u,x)$, $(x,v)$,
$(v,w)$, $(w,u)$ exist somewhere in $G$. Let $c$ be the crossing point of this
crossing. If edge $e=(u,x)$ is such that $\\{u,x,c\\}$ bounds a face of
$G^{\times}$, then $e$ is called a kite edge of the crossing; the
corresponding face is called a kite face of the crossing. Note that our
definition of locally maximal 1-plane does not require all crossings to have
kite edges. However, if edge $e=(u,x)$ does not bound a face incident to $c$,
then we can always add an uncrossed edge $e^{\prime}$ parallel to $e$ (i.e.,
with the same endpoints $u,x$) to get a kite face $\\{u,x,c\\}$. Adding
parallel edges do not affect the vertex connectivity of a graph, and kite
edges can be added in $O(n)$ time since a 1-planar graph has $O(n)$ crossings.
Hence, for the purposes of connectivity testing, we can consider “locally
maximal 1-plane” to be equivalent to “has a 1-plane drawing where all
crossings have all four kite edges.”

We assume throughout the paper that the input graph $G$ is connected. A
separating set of $G$ is a set $S$ of vertices such that $G-S$ is
disconnected. Each of the connected components of $G-S$ is called a flap. A
separating cycle is a cycle that is a separating set. A minimum separating set
is a separating set of minimum cardinality. The size of a minimum separating
set is also called the vertex connectivity of the graph, and is denoted by
$\kappa(G)$. A separating set $S$ is a minimal separating set if $S-\\{v\\}$
is not a separating set for any $v\in S$. The following useful observation on
minimal separating sets is easy to verify:

######  Observation 1.

Each vertex of a minimal separating set $S$ has a neighbour in each flap of
$G-S$.

##  3 The main idea

Let $G$ be a locally maximal 1-plane graph. The main idea for computing the
vertex connectivity of $G$ is to show a correspondence between minimum
separating sets of $G$ and shortest constrained separating cycles in an
auxiliary graph $\Lambda(G)$, called the radial planarisation of $G$. We
define these terms below.

For any plane graph, the _radial graph_ [FT06] is the bipartite graph obtained
by placing a face vertex in every face and connecting it to every vertex
incident with that face. We use $R(G)$ to denote the radial graph of
$G^{\times}$, and let the _radial planarisation_ $\Lambda(G)$ be the union of
$G^{\times}$ and $R(G)$, embedded in such a way that the edges of the radial
graph bisect the corresponding angles of $G^{\times}$ (Figure 2).

Not every separating cycle $X$ of $\Lambda(G)$ gives rise to a separating set
of $G$ (for example, one flap could only contain dummy vertices), and so we
must restrict further the separating cycles that we are searching for. A cycle
$X$ of $\Lambda(G)$ is called a _constrained separating cycle_ if it satisfies
the following constraints:

  1. ($\Psi$1)

$\Lambda(G)\setminus X$ has at least two flaps that contain vertices of $G$.

  2. ($\Psi$2)

$X$ is a subgraph of $R(G)$.

  3. ($\Psi$3)

$X$ does not visit any dummy vertices of $\Lambda(G)$ (i.e., vertices that
correspond to crossing points of $G$).

Theorem 2 captures the correspondence between minimum separating sets of $G$
and shortest constrained separating cycles of $\Lambda(G)$, and is the main
result of this paper.

######  Theorem 2.

Let $G$ be a locally maximal 1-plane graph. Then $G$ has a separating set of
size at most $k$ if and only if $\Lambda(G)$ has a constrained separating
cycle of length at most $2k$.

(In [Epp99], Eppstein proves a similar theorem for planar graphs, and is the
basis for computing vertex connectivity of planar graphs in linear time.) By
Theorem 2, separating sets of size $k$ in $G$ correspond to constrained
separating cycles of length $2k$ in $\Lambda(G)$. (The factor 2 appears
because a constrained separating cycle is a subgraph of $R(G)$ by $\Psi 2$.)
Therefore, it suffices to compute a shortest constrained separating cycle in
$\Lambda(G)$ to compute the vertex connectivity of $G$. It is easy to find
such a shortest constrained cycle, based on the planar subgraph isomorphism
algorithm developed by Eppstein in [Epp99]. We use $\Lambda(G)$ as the planar
host graph and a constrained separating cycle as the pattern graph. Eppstein’s
algorithm searches the host graph for an instance of the pattern graph, and
outputs the instance if it exists. His algorithm runs in linear time when the
size of the pattern graph is bounded. Eppstein also explains briefly in his
paper how to modify the algorithm so that it checks for constraints $(\Psi 1)$
and $(\Psi 2)$, and similar easy modifications can be done to ensure $(\Psi
3)$. Since a 1-planar graph is at most 7-connected, by Theorem 2, there exists
a shortest constrained separating cycle of $\Lambda(G)$ with length at most
14, and therefore of bounded size. Thus, a shortest constrained separating
cycle of $\Lambda(G)$ can be computed in linear time. As we will see in Lemma
4, it is very easy to extract a minimum separating set from a constraint
separating cycle. By Theorem 2, we therefore have:

######  Theorem 3.

Let $G$ be a locally maximal 1-plane graph. Then a minimum separating set of
$G$ can be computed in linear time.

##  4 Proof of Theorem 2

The proof of Theorem 2 proceeds in two directions. For convenience, we
introduce the following notation. Let $X$ be a separating cycle of
$\Lambda(G)$. Then the set of vertices of $G$ on $X$ is denoted by $V_{G}(X)$.
We prove the easy direction (the reverse direction) in the following lemma.

######  Lemma 4.

Let $X$ be a constrained separating cycle of $\Lambda(G)$. Then $V_{G}(X)$ is
a separating set of $G$.

###### Proof.

From $(\Psi 1)$, there exist two vertices $u,w\in V(G)$ that belong to
different flaps of $\Lambda(G)\setminus X$. Consider a simple path $P$
connecting $u$ and $w$ in $G$. Let $P^{\prime}$ be the path in $\Lambda(G)$
corresponding to $P$ defined as follows: for each edge $e\in P$, (a) if $e$ is
uncrossed, add $e$ to $P^{\prime}$; (b) if $e$ is crossed, add the two edges
of $\Lambda(G)$ corresponding to $e$ to $P^{\prime}$. Note that $P^{\prime}$
may contain both original vertices of $G$ and dummy vertices corresponding to
crossing points. Since $X$ separates $u$ and $w$ in $\Lambda(G)$, the path
$P^{\prime}$ intersects $X$ at some vertex $v\in X$, where $v\notin\\{u,w\\}$.
From $(\Psi 3)$, $v$ is not a dummy vertex of $\Lambda(G)$. Therefore, $v$ is
a vertex of $G$, and hence $v\in V_{G}(X)$. Since $P$ is arbitrary, every path
of $G$ connecting $u$ and $w$ contains a vertex of $V_{G}(X)$ in its interior.
This shows that $V_{G}(X)$ is a separating set of $G$. ∎

We prove the forward direction of Theorem 2 in Lemma 5.

######  Lemma 5.

Let $S$ be a separating set of $G$. Then $\Lambda(G)$ has a constrained
separating cycle $X$ such that $V_{G}(X)\subseteq S$.

###### Proof.

We can assume that $S$ is minimal, since otherwise we can always choose a
subset of $S$ that is a minimal separating set. The plan is to take a maximal
path that alternates between face vertices and vertices of $S$, and then to
show that extending it would give a cycle that has a vertex of $G$ inside and
a vertex of $G$ outside. Note that such a cycle satisfies all the three
constraints $(\Psi 1)$, $(\Psi 2)$ and $(\Psi 3)$ with the property that
$V_{G}(X)\subseteq S$.

To obtain such a cycle, we first mark face vertices of $\Lambda(G)$ that have
some suitable properties. Let $\langle u,v,w\rangle$ be an angle in
$G^{\times}$ such that $v\in S$. (Note that either $u$ or $w$ could be a dummy
vertex of $\Lambda(G)$.) Let $f$ be the face vertex at the angle. If $u$ and
$w$ are both vertices of $G$, and they belong to different flaps of $G-S$,
then we mark $f$. We also mark $f$ if one of $u,w$ is a vertex of $G$ and in
$S$. Put differently, face vertex $f$ is marked if it either is incident to an
edge connecting two vertices of $S$, or it witnesses a transition from one
flap to another.

######  Claim 6.

Each marked face vertex is incident with at least two edges whose other
endpoint is in $S$.

###### Proof.

If a face vertex $f$ is marked, then there is a vertex $v\in S$ and an angle
$\langle u,v,w\rangle$ in $G^{\times}$ that satisfies the conditions for
marking. If either $u\in S$ or $w\in S$, we are done. Otherwise, $u$ and $w$
are vertices of $G$ that are in different flaps of $G-S$; in particular they
are not dummy vertices. Therefore the face $F$ of $G$ corresponding to $f$ is
not a kite face. Consider a directed walk along the boundary of $F$, starting
from the edge $(v,w)$ in the direction $v$ to $w$, and ending at edge $(u,v)$.
The walk does not see any dummy vertices since $F$ is not a kite face and the
graph is locally maximal 1-planar. As $u$ and $w$ belong to different flaps,
the walk (which begins in the flap of $w$ and ends in the flap of $u$) must
visit some vertex of $S$ inbetween. Thus the walk either sees a vertex of $S$
different from $v$, or sees $v$ again at another angle of the face. In either
case, there must be two edges connecting $f$ to vertices of $S$. ∎

In Claim 7, we show that each vertex $v$ of $S$ also has two incident edges
connecting it to marked face vertices. But in fact, we need a stronger claim,
namely, that these two edges can be restricted within their location of
$\rho(v)$ to lie on opposite sides of two edges to two flaps. To clarify this,
we introduce some notation. Let $\rho_{G}(v)$ and $\rho_{\Lambda}(v)$ be the
rotation at a vertex $v$ in $G$ and $\Lambda(G)$ respectively. Let $(u,v)$ be
an edge of $G$. The notation $(u,\bar{v})$ refers to the edge in $\Lambda(G)$
that is incident with $u$ and corresponds to $(u,v)$ in $G$. That is,
$\bar{v}=v$ if $(u,v)$ is uncrossed; else $\bar{v}$ is the dummy vertex on
$(u,v)$.

######  Claim 7.

Let $\phi_{1}$ and $\phi_{2}$ be two flaps of $G-S$. Let $(v,t_{1})$ and
$(v,t_{2})$ be two edges such that $v\in S$, $t_{1}\in\phi_{1}$ and
$t_{2}\in\phi_{2}$. Then there exist a marked face vertex $f$ such that
$\langle(v,\bar{t_{1}}),(v,f),(v,\bar{t_{2}})\rangle\subseteq\rho_{\Lambda}(v)$.

###### Proof.

Take the closest pair of edges $(v,w_{1})$, $(v,w_{2})$ that lie between
$(v,t_{1})$, $(v,t_{2})$ in $\rho_{G}(v)$ such that $w_{1}\in\phi_{1}$ and
$w_{2}\in\phi_{2}$. More precisely, take a pair of edges $(v,w_{1}),(v,w_{2})$
such that $\langle(v,t_{1})$, $(v,w_{1})$, $(v,w_{2})$,
$(v,t_{2})\rangle\subseteq\rho_{G}(v)$ (where possibly $t_{1}=w_{1}$ and/or
$w_{2}=t_{2}$) and such that there is no vertex
$v^{\prime}\in\phi_{1}\cup\phi_{2}$ with $\langle(v,w_{1})$, $(v,v^{\prime})$,
$(v,w_{2})\rangle\subseteq\rho_{G}(v)$. It suffices to show that there is a
marked face vertex $f$ such that $\langle(v,\bar{w_{1}})$, $(v,f)$,
$(v,\bar{w_{2}})\rangle\subseteq\rho_{\Lambda}(v)$. We have two cases:

Case 1: $(v,w_{1})$ and $(v,w_{2})$ are consecutive in $\rho_{G}(v)$. We claim
that both $(v,w_{1})$ and $(v,w_{2})$ are uncrossed. For contradiction,
suppose that $(v,w_{1})$ is crossed by an edge $(u,u^{\prime})$. Then there
exist kite edges $(v,u)$, $(v,u^{\prime})$ before and after $(v,w_{1})$ in
$\rho_{G}(v)$. Hence (up to renaming) $u^{\prime}=w_{2}$. Since
$(w_{1},u^{\prime})$ is also a kite edge, $w_{1}$ and $w_{2}$ are adjacent,
which contradicts that they are in different flaps. Therefore, $(v,w_{1})$ is
uncrossed, and similarly $(v,w_{2})$ is also uncrossed. This implies that
$\langle w_{1},v,w_{2}\rangle$ is an angle at $v$ in $G$. Since $w_{1}$ and
$w_{2}$ belong to different flaps, the face vertex $f$ at this angle is marked
as desired.

Case 2: $(v,w_{1})$ and $(v,w_{2})$ are not consecutive in $\rho_{G}(v)$. Then
there is a vertex $v^{\prime}$ such that
$\langle(v,w_{1}),(v,v^{\prime}),(v,w_{2})\rangle\subseteq\rho_{G}(v)$. Choose
$(v,v^{\prime})$ to be the first edge that comes after $(v,w_{1})$ in
$\rho_{G}(v)$. By the choice of $w_{1}$ and $w_{2}$,
$v^{\prime}\notin\phi_{1}\cup\phi_{2}$. We have two subcases. If
$(v,v^{\prime})$ is uncrossed, then $\langle w_{1},v,v^{\prime}\rangle$ is an
angle at $v$ and $v$ is not a dummy-vertex. Since $v^{\prime}\notin\phi_{1}$,
it either belongs to $S$ or to some other flap; either way the face vertex $f$
at this angle is marked and we are done. Now suppose that $(v,v^{\prime})$ is
crossed by an edge $(u,u^{\prime})$ at $c$. Then there exist kite edges
$(v,u)$ and $(v,u^{\prime})$ before and after $(v,v^{\prime})$ in
$\rho_{G}(v)$. By the choice of $v^{\prime}$, we have (up to renaming)
$u=w_{1}$. So $u^{\prime}$ is a neighbour of $w_{1}$, which means that it
either belongs to the same flap $\phi_{1}$ or to $S$. In particular
$u^{\prime}\neq w_{2}$. But this implies $u^{\prime}\not\in\phi_{1}$ by choice
of $w_{1},w_{2}$, so $u^{\prime}\in S$. Therefore $\langle
c,v,u^{\prime}\rangle$ is an angle in $G^{\times}$ with $u^{\prime},v\in S$
and the face vertex $f$ at this angle is marked as desired. ∎

### Constructing the constrained separating cycle.

We now show how to construct the desired constrained separating cycle in
$\Lambda(G)$ using only vertices of $S$ and marked face vertices. Let $v_{1}$
be an arbitrary vertex of $S$. Let $P=v_{1}\dots v_{k}$ be a simple path that
alternates between marked face vertices and vertices of $S$ and that is
maximal in the following sense: $v_{k}\in S$, and for any marked face vertex
$v_{k+1}$ and any vertex $v_{k+2}$ in $S$ the extension
$P\cup\\{(v_{k},v_{k+1}),(v_{k+1},v_{k+2})\\}$ would not be a simple path.
Since $v_{k}\in S$, there exist vertices $t_{1}\in\phi_{1}$ and
$t_{2}\in\phi_{2}$ that are adjacent to $v_{k}$ (Observation 1). By symmetry,
we may assume that
$\langle(v_{k},\bar{t_{2}}),(v_{k},v_{k-1}),(v_{k},\bar{t_{1}})\rangle\subseteq\rho_{\Lambda}(G)$.
From Claim 7, there is a marked face vertex $f$ such that
$\langle(v_{k},\bar{t_{1}}),(v_{k},f),(v_{k},\bar{t_{2}})\rangle\subseteq\rho_{\Lambda}(G)$.

(a)

(b)

(c)

Figure 3: Constructing a constrained separating cycle in $\Lambda(G)$

  * •

Suppose that $f=v_{i}\in P$, for some $1\leq i\leq k-1$ (Figure 3(a)). Then
$X:=v_{i}v_{i+1}\dots v_{k}v_{i}$ is a cycle that separates $t_{1}$ and
$t_{2}$ (since they are on either side of the cycle).

  * •

Suppose that $f\notin P$. By Claim 6, $f$ has two edges $e,e^{\prime}$ to
vertices of $S$. We may assume that $e$ is the edge $(v_{k},f)$ that brought
us to $f$, and consider extending $P$ via $e$ and $e^{\prime}$. Since this
gives a non-simple path by choice of $P$, we have $e^{\prime}=(f,v_{i})$ for
some $1\leq i\leq k$. If $1\leq i\leq k-1$ (Figure 3(b)), then
$X:=v_{i}v_{i+1}\dots v_{k}fv_{i}$ is a cycle that separates $t_{1}$ and
$t_{2}$. If $i=k$, then $e$ and $e^{\prime}$ form a 2-cycle, and there must
exist a vertex $u\in G$ inside the 2-cycle because the radial graph $R(G)$
does not contain bigons (Figure 3(c)). Therefore, $X:=v_{k}fv_{k}$ is a cycle
separating $u$ from $t_{1}$ (and $t_{2}$).

Note that by construction, $X$ separates two vertices of $G$, is a subgraph of
$R(G)$, does not visit dummy vertices, and all vertices of $G$ on $X$ belong
to $S$. This proves the lemma. ∎

##  5 Outlook

In this paper, we studied how to compute the vertex connectivity of a locally
maximal 1-plane graph $G$. We showed that any minimum separating set $S$
corresponds to a separating cycle of length $2|S|$ (and with some other
properties) in $\Lambda(G)$. By appealing to known subgraph isomorphism
results, we can find such a cycle, and with it a minimum separating set, in
linear time.

(a)

(b)

Figure 4: An example of a 4-connected 1-plane graph that does not have a
separating 8-cycle in its radial planarisation passing through a minimum
separating set (bold vertices).

The most natural open question is to extend the result to more subclasses of
1-planar graphs. We required that the 1-plane graph was locally maximal, i.e.,
for every crossing all four kite edges exist. We believe that the techniques
used here can be extended (after a slight modification to $\Lambda(G)$) even
to the case when there are only three kite edges, and even to the case when
there are only two kite edges and they do not have a common endpoint. (Details
will be given in a forthcoming publication.) The case when there are only two
kite edges with a common endpoint appears problematic, since the example in
Figure 4 shows that (at least for our way of defining the radial
planarisation) there exists a minimum separating set of size 4 (bold
vertices), but no 8-cycle in the radial planarisation connecting them. Even
more problematic is the situation when there are no kite edges at all, as
illustrated in Figure 1. We suspect that radically different techniques, not
based on radial planarisation, will be needed to find the minimum separating
set of all 1-plane graphs in $O(n)$ time.

Finally, looking more broadly, can we find linear-time connectivity testing
algorithms for other graph classes that are defined via some geometric
properties, such as $k$-planar graphs, fan-planar graphs, or sphere-of-
influence graphs?

## References

  * [BSW83] Rainer Bodendiek, Heinz Schumacher, and Klaus Wagner.  Bemerkungen zu einem Sechsfarbenproblem von G. Ringel.  Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 53:41–52, 1983.
  * [Die18] Reinhard Diestel.  Graph theory (Fifth edition), volume 173 of Graduate Texts in Mathematics. Springer, 2018.
  * [Epp99] David Eppstein.  Subgraph isomorphism in planar graphs and related problems.  J. Graph Algorithms Appl., 3(3):1–27, 1999.
  * [FHM+20] I. Fabrici, J. Harant, T. Madaras, S. Mohr, R. Soták, and C. T. Zamfirescu.  Long cycles and spanning subgraphs of locally maximal 1-planar graphs.  J. Graph Theory, 95(1):125–137, 2020.
  * [FNY+20] Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms.  In ACM-SIAM Symposium on Discrete Algorithms, pages 2046–2065. SIAM, 2020.
  * [FT06] Fedor V. Fomin and Dimitrios M. Thilikos.  New upper bounds on the decomposability of planar graphs.  J. Graph Theory, 51(1):53–81, 2006.
  * [GB07] Alexander Grigoriev and Hans L. Bodlaender.  Algorithms for graphs embeddable with few crossings per edge.  Algorithmica, 49(1):1–11, 2007.
  * [GLN+19] Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Deterministic graph cuts in subquadratic time: Sparse, balanced, and k-vertex.  CoRR, abs/1910.07950, 2019.
  * [GM00] Carsten Gutwenger and Petra Mutzel.  A linear time implementation of SPQR-trees.  In Graph Drawing, volume 1984 of Lecture Notes in Computer Science, pages 77–90. Springer, 2000.
  * [HT73] John E. Hopcroft and Robert Endre Tarjan.  Dividing a graph into triconnected components.  SIAM J. Comput., 2(3):135–158, 1973.
  * [HT08] Bernhard Haeupler and Robert Endre Tarjan.  Planarity algorithms via PQ-trees (extended abstract).  Electron. Notes Discret. Math., 31:143–149, 2008.
  * [HT20] Seok-Hee Hong and Takeshi Tokuyama, editors.  Beyond Planar Graphs, Communications of NII Shonan Meetings.  Springer, 2020.
  * [Kle69] Daniel Kleitman.  Methods for investigating connectivity of large graphs.  IEEE Transactions on Circuit Theory, 16(2):232–233, 1969.
  * [KLM17] S. Kobourov, G. Liotta, and F. Montecchiani.  An annotated bibliography on 1-planarity.  Computer Science Review, 25:49–67, 2017.
  * [KM13] Vladimir P. Korzhik and Bojan Mohar.  Minimal obstructions for 1-immersions and hardness of 1-planarity testing.  Journal of Graph Theory, 72(1):30–71, 2013.
  * [KR91] Arkady Kanevsky and Vijaya Ramachandran.  Improved algorithms for graph four-connectivity.  J. Comput. Syst. Sci., 42(3):288–306, 1991.
  * [NI92] Hiroshi Nagamochi and Toshihide Ibaraki.  A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph.  Algorithmica, 7(5&6):583–596, 1992.
  * [PT97] János Pach and Géza Tóth.  Graphs drawn with few crossings per edge.  Combinatorica, 17(3):427–439, 1997.
  * [Rin65] Gerhard Ringel.  Ein Sechsfarbenproblem auf der Kugel.  Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 29(1):107–117, 1965.
  * [Sch13] M. Schaefer.  The graph crossing number and its variants: A survey.  The Electronic Journal of Combinatorics [electronic only], 20, 04 2013.
  * [Tar72] Robert Endre Tarjan.  Depth-first search and linear graph algorithms.  SIAM J. Comput., 1(2):146–160, 1972.