# Asking More Informative Questions for Grounded Retrieval

Sedrick Keh
Carnegie Mellon University
<EMAIL_ADDRESS>
&Justin T. Chiu
Cornell Tech
<EMAIL_ADDRESS>
&Daniel Fried
Carnegie Mellon University
<EMAIL_ADDRESS>
###### Abstract

When a model is trying to gather information in an interactive setting, it
benefits from asking informative questions. However, in the case of a grounded
multi-turn image identification task, previous studies have been constrained
to polar yes/no questions White et al. (2021), limiting how much information
the model can gain in a single turn. We present an approach that formulates
more informative, open-ended questions. In doing so, we discover that off-the-
shelf visual question answering (VQA) models often make presupposition errors,
which standard information gain question selection methods fail to account
for. To address this issue, we propose a method that can incorporate
presupposition handling into both question selection and belief updates.
Specifically, we use a two-stage process, where the model first filters out
images which are irrelevant to a given question, then updates its beliefs
about which image the user intends. Through self-play and human evaluations,
we show that our method is successful in asking informative open-ended
questions, increasing accuracy over the past state-of-the-art by 14%, while
resulting in 48% more efficient games in human evaluations.

##  1 Introduction

As NLP models are increasingly deployed in interactive settings, it is key
that these models are able to gather information about the user’s intentions
and the underlying world context. Models might do this by asking questions to
the user — however, asking informative questions is challenging, as it relies
on reasoning about the current context, the history of the interaction, and
potential future plans. Past work on question generation for interaction has
formulated questions that are predicted to be informative, but has typically
used questions with constrained answer spaces Rao and Daumé III (2018); Yu et
al. (2020); White et al. (2021), which can lead to inaccurate and inefficient
interactions in contextually rich tasks.

We present an approach for generating open-ended questions in one such
contextually rich task: a multi-turn image identification task White et al.
(2021) inspired by interactive retrieval. In this task, a model is presented
with an array of images, one of which is a _target_ image known only to a
human user. The model has to identify this image by formulating questions for
the user to answer. A sample game can be seen in Figure 1, and more details
can be found in Section 2. We select this task as a challenging test bed for
strategic contextual interaction: requiring strong abilities in grounding (to
distinguish between similar images that differ only in their less-salient
details, e.g. all images in Figure 1 contain a computer) and planning (asking
informative questions that take into account the history of interaction).

Figure 1: We propose a method for interactive image identification, where our
model’s goal is to ask the most informative questions to quickly and
accurately guess the target image (highlighted in red).

Previous approaches to this task White et al. (2021) have used polar yes/no
questions in the form of "IsA" questions. Although these IsA questions are
formulated to be maximally informative according to an expected information
gain metric (Section 2.2), polar questions do not scale well to settings where
images are similar, or with a larger number of images. It is also not
straightforward to simply replace IsA questions with broader open-ended
questions (i.e. _wh-_ questions such as who, where, when, etc.) We show
(Section 5) that doing so naively produces questions with presupposition
errors, where an off-the-shelf visual question answering (VQA) model gives
confident answers to questions that are irrelevant to an image. An example of
a presupposition error would be asking "What is the dog eating?" when there is
no dog in the target image. This failure renders the standard information gain
metric inappropriate and results in a chain of errors in belief updates over
the model’s target images. Constraining to polar yes/no questions largely
protected previous approaches from facing such issues, but once open-ended
questions are introduced, the chances for presupposition errors rise
substantially.

We propose a method that can generate open-ended informative questions in the
interactive image retrieval setting, relaxing the polar yes/no constraints,
while at the same time being able to handle presuppositions. We do this by
conducting a two-stage process: first explicitly checking for presuppositions
to filter out irrelevant images, then calculating information gain based only
on the relevant images. We show that after handling such errors, asking open-
ended _wh-_ questions substantially outperforms constraining to polar yes/no
questions. In our human evaluations, our method results in 48% more efficient
games compared to the past state-of-the-art for this task White et al. (2021),
while improving accuracy by 13%. We further conduct ablation studies to verify
that our two-stage pipeline is indeed successful in eliminating presupposition
errors, and that it can generalize to settings where there are substantially
more images to choose between. Our method is even more successful in this more
challenging setting, resulting in an average of 3.5 times shorter games.

##  2 Background

We discuss the task and notation used, as well as some key concepts/tools used
in our model.

###  2.1 Task

The multi-turn grounded image retrieval task was formally introduced in White
et al. (2021), though it can be viewed as an extended setting of a Lewis
signaling game Lewis (1969). In this setting, there are a total of $k$ images
(we consider $k=10$ and $k=100$) containing one target image, chosen at
random. There are two agents who can both observe all the images. One agent
(the responder) knows the identity of the target image, while the other agent
(the guesser) does not. The goal of the guesser is to ask clarifying questions
in order to accurately identify the target image in as few turns as possible.
This dialogue proceeds for multiple turns, until either the guesser is
confident enough to make a guess, or until a set threshold (number of turns)
is reached, in which case the guesser will have to make a guess. In our paper,
the guesser is a model (whose goal is to identify the target image by asking
clarifying questions), while the responder can either be a human or another
model.

More formally, we define $I$ = $\\{i_{1},i_{2},\dots i_{k}\\}$ as the set of
images, and $y$ as the target image. In each turn $t$ of the interaction, the
guesser (model) asks a question $q$, and the responder answers with a response
$r$. We additionally define $x^{t}$ as the history of the interaction
$(q_{1},r_{1},q_{2},r_{2},\dots q_{t},r_{t})$.

In our version of the task, we add a new component — the "No Answer" option.
Instead of responding to the guesser’s clarifying question, the responder may
opt to not provide an answer. The option to deliberately not answer a question
will provide valuable information to a model. Using our notation, we represent
this as $r_{null}$. This simple change is a necessary addition if we wish to
incorporate _wh-_ questions, as the responder needs an appropriate way to
respond to the guesser’s question if it does not apply to the target image.

###  2.2 Expected Information Gain

To quantify the most informative question, one common metric (Lindley, 1956;
Rao and Daumé III, 2018; Yu et al., 2020; White et al., 2021) is the expected
information gain of a given question $\mathrm{EIG}(y,r;q,x^{t})$. A model
maintains a _belief distribution_ $P(y\mid x^{t},q,r)$ over which image is the
target, and aims to ask questions that will minimize uncertainty in this
belief distribution, taking answer likelihood into account. This is given by
minimizing the conditional entropy of the belief distribution, in expectation
over possible answers to the question:

$\arg\min_{q}\mathop{\mathbb{E}}_{p(y\mid x^{t})}\mathop{\mathbb{E}}_{p(r\mid
q,y)}[-\ln P(y\mid x^{t},q,r)]$ (1)

Note that this requires a model $p(r\mid q,y)$ to predict the user’s response
to any $(q,I,y)$ set. For this, we use a proxy VQA answering model, which we
discuss more in Section 3.2.

Figure 2: Overview of our pipeline/flow for a single turn of the interactive
image retrieval task. The colored boxes represent modules (which can be a
model, a ground truth oracle, or a human player), while the clear boxes
represent various inputs/outputs during the game.

##  3 Methods

Our main pipeline is illustrated in Figure 2. We use a training-free approach,
using only off-the-shelf pre-trained VQA and text processing models. Using the
image contexts, we first generate a large pool of possible candidate questions
$Q$ (Section 3.1), then select the question $q\in Q$ which gives the highest
expected information gain about the belief distribution (which estimates which
image is the target), taking into consideration the various presupposition
assumptions (Section 3.2). Upon asking the question $q$ and receiving a
response $r$, the model then updates its belief distribution accordingly
(Section 3.3).

###  3.1 Candidate Question Generation

In order to generate appropriate questions, we first generate a list of
captions, then convert each caption to a list of several questions, as was
done in White et al. (2021). This approach allows us to leverage the strong
capabilities of image captions combined with text generation models (for
caption-to-question), which results in more diverse and higher quality
questions as compared to directly conditioning on the image.

More formally, for each image $i\in I$, in order to generate question set
$Q_{i}$, we first obtain a caption $C_{i}$, then convert the caption $C_{i}$
into $\\{q_{i_{1}},q_{i_{2}},\dots q_{i_{j}}\\}\in Q_{i}$, where each
$q_{i_{j}}$ represents a possible way to convert caption $C_{i}$ into a
question. For instance, if the caption $C_{i}$ is “A man brushing his teeth
with a toothbrush”, then possible questions $q_{i_{1}},q_{i_{2}},q_{i_{3}}$
could be “What is the man doing?”, “Where is the man?”, and “What color is the
toothbrush?” Notably, all our questions are open-ended _wh-_ questions, as
opposed to the polar yes/no questions used in previous studies (White et al.,
2021). To convert each caption $C_{i}$ into a set of candidate questions
$Q_{i}$, we leverage in-context learning capabilities of large language models
such as GPT-4 OpenAI (2023). Specifically, we provide a system prompt
describing the task in detail, as well as 4 few-shot examples in the format
"Caption:[$C_{i}$]. Questions:[$q_{i_{1}},q_{i_{2}},\dots q_{i_{j}}$]". In
order to make the in-context learning more robust, we vary $j$ across the
different captions, ranging from 3 to 7, with an average of 4.75 questions per
caption. More details on the prompting process and our exact prompts can be
found in Appendix A.

###  3.2 Top Question Selection

Selecting the most informative question is done based on highest expected
information gain (Eq. 1). In order to calculate expected information gain, we
use a response simulator model (i.e., a VQA model) which allows us to
calculate the probability $P(r\mid q,i)$, for any $(r,q,i)$ tuple.
Intuitively, this probability represents how likely a user would be to respond
to a question in a given way, if a particular image is the target.

However, as mentioned earlier, the model often faces presupposition errors, in
which case the probability updates may not accurately reflect the true amount
of information gained. As such, rather than simply using the expected
information gain, we modify the question selection process to account for
presuppositions. To do this, we employ a two-step process, as denoted by the
Existence Simulator Model and the Response Simulator Model in Figure 2. We
verify the importance of each of these components in ablations in Section 6.1.

Existence Simulation Step: The goal of this step is to identify which images a
particular questions is relevant to, as it would not make sense to run
response simulation on images where the question does not apply.

For each question, we define $\text{Relevance}(q,i)$ as the indicator variable
that is $1$ when question $q$ is relevant to image $i$, and $0$ otherwise. We
compute $P(\text{Relevance}(q,i))$ as follows: (1) We convert wh- question $q$
into a set of polar yes/no questions $\\{q_{yn_{1}},q_{yn_{2}},\dots
q_{yn_{j}}\\}$. This is done by parsing the question with a constituency
parser Kitaev and Klein (2018) and extracting all possible subjects (nouns or
noun phrases). Each possible subject $s_{1},s_{2},\dots s_{j}$ is then
directly converted into a yes/no question $q_{yn_{1}},q_{yn_{2}},\dots
q_{yn_{j}}$ by asking "Is there a $s_{j}$?" or "Are there $s_{j}$?" (2) Using
our VQA model, we implicitly ask each of these yes/no questions and take the
mean across questions, so $P(\text{Relevance}(q,i))$ is computed as

$\frac{1}{j}\sum_{k=1}^{j}VQA(r_{\text{yes}}\mid q_{yn_{k}},i)$ (2)

where $r_{\text{yes}}$ denotes the case where the response to the polar
question is "yes".

Response Simulation Step: Here, the response simulator is a VQA model that
calculates $P(r\mid q,i)$ for any $(r,q,i)$ tuple. We then define

$P(r\mid q,i)_{\text{rel}}\propto P(r\mid q,i)\cdot P(\text{Relevance(q,i))}$
(3)

where “rel” refers to the relevance-adjusted probability. We proceed with the
information gain calculation in Eq. 1 using $P(r\mid q,i)_{\text{new}}$, and
the question with the highest information gain computed using the process
above is then selected as the final question the model chooses to ask.

###  3.3 Belief Updates

The model initially has a uniform belief distribution over all images, i.e.,
$P(i=y\mid x^{0})=\frac{1}{k}$ for all $i$, where $k$ is the number of images.
Recall that $x^{t}$ is defined as the history of the interaction
$(q_{1},r_{1},\dots q_{t},r_{t})$. After the model asks a questions and
receives a response from its partner (which is either a human or, in automatic
evaluation, another VQA model — see Section 4.5), the model will need to
update its internal beliefs conditioned on the given response. As discussed in
Section 2.1, our setting allows two types of responses, either the standard
response or a null response (i.e., responding with "No Answer"). This is the
response-side analog to the $P(\text{Relevance}(q,i))$ discussed in 3.2. It
allows us to account for presuppositions, so we can properly update the model
depending on whether or not an image applies to the question. We outline the
two possible scenarios below:

#### Standard Response.

This describes the scenario when the model provides an actual answer to the
question (rather than responding with “No Answer”). Here, we wish to compute
$P(y\mid x^{t},q,r)$. We can apply Bayes’ Rule to obtain

$P(y|x^{t},q,r)\propto\\\ P(r|x^{t},y,q)P(q|x^{t},y)P(y|x^{t})$ (4)

where $P(r\mid x^{t},y,q)$ can be calculated using the VQA model, $P(q\mid
x^{t},y)$ can be calculated using the question selector model, and $P(y\mid
x^{t})$ can be calculated recursively. Full details for these calculations can
be found in Appendix B.

#### Null Response.

This describes the scenario when the model responds with “No Answer”. Here,
the calculation for $P(y\mid x^{t},q,r_{null})$ is done similarly to the
standard case above, except with the change that we consider $P(r_{null}\mid
x^{t},i_{y},q)$ instead of $P(r\mid x^{t},i_{y},q)$. Because "No Answer" is
not in the vocabulary for our VQA model, we instead design a proxy method to
calculate $P(r_{null}\mid x^{t},i,q)$. We thus define
$P(\text{Irrelevance}(q,i))$ and calculate it similar to Eq. 2, but with
$r_{no}$ instead of $r_{yes}$ (more details in Appendix B.) We then
approximate $P(r_{null}\mid i,q)\approx P(\text{Irrelevance}(q,i))$. When
multiplied with the other probabilities in Eq. 4, this effectively results in
upweighting the images which do not contain the subject, and downweighting the
images which contain the subject.

The entire process is then repeated until one of the beliefs in the model’s
distribution over images exceeds a certain threshold $\gamma$.

##  4 Experimental Setup

We describe our experimental setup in Sections 4.1, 4.2, and 4.3. We then
compare our approach to baselines in both games with human partners (Section
4.4), as well as in automatic model-based evaluations (Section 4.5).

###  4.1 Datasets and Image Selection

We compile image sets from the MS-COCO dataset Lin et al. (2014). Image
sampling is done under various configurations. In the easy setting, $k=10$
images are simply sampled randomly from the MS-COCO validation set, as was
done in White et al. (2021). We refer to this setting as easy since, with
sufficiently diverse images and a strong questioning model, most of these
cases should be quickly solvable by simply asking a general question like
“What is the subject of the image?”

In order to test the question-asking ability of the model, we also reduce the
diversity among the images, i.e., make the images more similar to each other.
This also more closely reflects real-world retrieval settings, where a group
of images may share many similarities. To identify similar images, we parse
the MS-COCO ground truth captions to identify the main subject of each image.
For the hard setting, we select $k=10$ images which all share a single
subject, while for the medium setting, we select 2 subjects, with $5$ images
all sharing the first subject, and the remaining $5$ images sharing the second
subject. An example of a hard setting can be found in Figure 1.

###  4.2 Modules

We previously highlighted multiple modules in our pipeline. We detail each of
them below.

#### Image Captions.

To test the question-asking capabilities of our approach, we wish to make the
captions as accurate as possible in order to reduce the possible sources of
error in the pipeline. As such, we use the provided ground truth captions in
the MS-COCO dataset.

#### Candidate Question Generation Model.

We want a strong model that can use in-context learning to convert captions to
candidate questions. For this, we use GPT-4 OpenAI (2023).

#### Question Selection Model.

For both the Existence Simulator Model and the Response Simulator Model, we
use ViLT-VQA Kim et al. (2021b), which is a strong vision-language model
trained on the VQA-v2 benchmark Goyal et al. (2016).

#### User Response Simulator.

We consider a variety of possible sources for the ground truth. In the basic
setting, we evaluate models in games with human partners (more details in
Section 4.4). However, we also consider a self-play version, where we use a
separate VQA model to serve as the responder (more details in Section 4.5). We
call this responder model the user response simulator, and we use it as a
proxy for the human when conducting the self-play evaluations. Specifically,
we use BLIP Li et al. (2022) as our user response simulator.

| Easy | Medium | Hard
---|---|---|---
Model | Accuracy | Turns | Accuracy | Turns | Accuracy | Turns
Polar Yes/No | 0.78 | 3.81 | 0.72 | 3.62 | 0.69 | 3.60
Open-Ended (No Presupp.) | 0.95 | 1.38 | 0.84 | 1.99 | 0.81 | 2.74
Open-Ended (With Presupp.) | 0.93 | 1.55 | 0.85 | 1.86 | 0.83 | 2.46
Table 1: Averaged results for self-play evaluations. Each (model, difficulty) pair is evaluated over 80 games. | Easy | Hard
---|---|---
Model | Accuracy | Turns | Accuracy | Turns
Polar Yes/No | 0.73 | 3.32 | 0.68 | 3.38
Open-Ended (With Presupp.) | 0.83 | 1.70 | 0.73 | 2.73
Table 2: Averaged results for human evaluations. Each (model, difficulty) pair
is evaluated over 40 games.

###  4.3 Models and Baselines

We test the performance of the following pipelines:

  1. 1.

Polar Yes/No Questions – This closely follows the method of White et al.
(2021), but instead of their previously used CNN-based VQA classifier, we use
the VQA models listed in Section 4.2, as we found these off-the-shelf
pretrained VQA models to perform better than training our own CNN-based
classifier. More details on Yes/No question generation can be found in
Appendix C.

  2. 2.

Open-Ended Questions (No Presupp.) – This is the pipeline described in Section
3, except that it does not contain the existence simulation step during
question selection, and it does not allow "No Answer" as a response.

  3. 3.

Open-Ended Questions (With Presupp.) – This is exactly the pipeline described
in Section 3.

In terms of evaluation metrics, we consider game length (number of turns) and
accuracy (how often the model guesses correctly).

###  4.4 Human Evaluation

We recruited annotators from Amazon Mechanical Turk to play the game with the
model. We selected annotators who have completed our qualification test and
have >98% acceptance rate and >10k completed HITs. For each HIT, the
annotators would be paired with a random model type (polar questions versus
open-ended questions) and presented with $k=10$ images, where the target image
would be highlighted. The human would provide responses to the model’s
questions, and the game automatically stops when the model’s confidence
exceeds a certain threshold. For the open-ended setting, there is a separate
button for "No Answer" that the user can select. More details on the human
evaluation process can be found in Appendix E.

###  4.5 Model-Based Evaluation

We use a BLIP VQA model Li et al. (2022) to provide a response $r$ given
$(q,I)$. This is straightforward for the polar yes/no and for open-ended (no
presupp.) settings. However, for the open-ended (with presupp.) setting, we
need a way to provide the “No Answer” response. To do this, we first convert
the question $q$ into polar yes/no questions $\\{q_{yn_{1}},q_{yn_{2}},\dots
q_{yn_{j}}\\}$. We then feed each of these $q_{yn}$ yes/no questions to BLIP
to receive a yes/no response
$r_{yn_{j}}=\arg\max_{r\in\\{\text{yes,no}\\}}VQA(r\mid q_{yn_{j}},i)$. If at
least half of the responses to $\\{q_{yn_{1}},q_{yn_{2}},\dots q_{yn_{j}}\\}$
are “no”, then the self-play response model responds with “No Answer.”
Otherwise, it treats it as a standard question and provides a standard answer.

##  5 Results

###  5.1 Self-Play Evaluations

We see in Table 1 that the model which asks open-ended questions while
explicitly handling presuppositions performs the best, both in terms of
accuracy and number of turns. In general, both open-ended methods perform much
better than the polar yes/no questions in terms of game length, which
demonstrates that open-ended questions indeed fetch more information for the
model.

One interesting finding in the self-play experiments is that even without
proper presupposition handling, the naive open-ended model already performs
relatively well most of the time. We notice that the gap between the naive
open-ended model and the smart open-ended model only begins to reveal itself
in the medium and hard settings. This is likely because in the easy setting,
the images are often diverse enough to be solvable in 1 or 2 turns, as
evidenced by the low number of turns. As such, there likely will not be many
presuppositions encountered early on, as a general probing question like “What
is the main subject of the image?” would be very highly informative and be
(correctly) selected as the first question a majority of the time. In
contrast, when the images are more similar to each other, the games will
naturally take longer, and there will be more opportunities for scenarios with
presupposition errors to appear. We further verify this hypothesis in an even
more challenging setting in Section 5.3.

###  5.2 Human Evaluations

We validate these self-play results using human evaluations, comparing the
polar yes/no setting against the open-ended (with presupp.) setting. We select
the easy and hard settings, and conduct 40 human-played games per (model,
setting) pair. Results are given in Table 2.

These human evaluations corroborate our self-play findings, demonstrating that
open-ended questions, when asked properly, indeed outperform the polar yes/no
method of White et al. (2021). There is a slight drop in human performance as
compared to the self-play performance. This is likely because the VQA models
used in self-play are able to capture very tiny details in the images, which
humans may look past or fail to discern (e.g., “How many [X] are there in the
image?” may be troublesome for a human to answer if $X>10$).

###  5.3 Scaling To Large Image Sets

In Section 5.1, we observed that the performance improvement from
presupposition handling in the open-ended model begins to widen as the
difficulty of the task increases. Here, we further verify this by considering
an even more challenging task: increasing the number of images $k$ from $10$
to $100$, while still maintaining the hard setting of sharing the same
subject.

In Table 3, we see an even larger improvement from presupposition handling in
this more challenging setting. Notably, there is a significant accuracy drop
for the open-ended (no presupp.) setting, which is likely because as these
presupposition errors appear in this challenging setting, they accumulate over
multiple turns and lead to worse belief updates. This does not happen in the
open-ended (with presupp.) model, where accuracy stays roughly the same as the
$k=10$ case. For game length, the number of turns increases for all settings
beyond $k=10$, but the increase is most substantial for the polar and No
Presupp settings, while remaining minimal for the open-ended setting that
handles presuppositions. This demonstrates that being able to avoid
presupposition errors is indeed beneficial for the model to truly be able to
ask the most informative open-ended questions.

| k=100
---|---
Model | Accuracy | Turns
Polar Yes/No | 0.73 | 13.4
Open-Ended (No Presupp.) | 0.73 | 9.6
Open-Ended (With Presupp.) | 0.83 | 3.8

Table 3: Averaged self-play results for the large-scale image set challenge
setting where number of images $k=100$. Each (model, difficulty) pair is
evaluated over 30 games.

##  6 Analysis and Ablation Studies

We conduct an ablation study (Section 6.1) to examine the importance of
various components of the presupposition handling process.

Presupp. Handling | Accuracy | Turns
---|---|---
None (No Presupp.) | 0.81 | 2.74
None (Double Update) | 0.72 | 1.60
Only in question selection | 0.81 | 2.73
Only in belief updates | 0.83 | 3.54
Both (With Presupp.) | 0.83 | 2.46
Table 4: Presupposition ablation results for the open-ended questions (self-
play). Here, "Double Update" refers to simply conducting the belief updates
twice in each turn.

Setting |  First Question | Correct? | Turns
---|---|---|---
Polar Yes/No |  Is there a restaurant table? | No | 3
Open-Ended (No Presupp.) |  What is next to the knife? | No | 2
Open-Ended (With Presupp.) |  What type of food are the people eating? | Yes | 1

Table 5: First question asked by each model in the game above, together with
game statistics. Full game conversations can be found in Appendix F.

###  6.1 Presupposition Handling

Because our method employs a two-step process in the belief updates, one
possible explanation for the performance improvement could be an increase in
the number of belief updates being performed. To test this, we consider a case
where we do not do any presupposition handling, but instead simply conduct the
belief updates twice in each round. This is represented by "None (Double
Update)" in Table 4. We observe that performing this double update results in
significantly shorter games, which is likely due to each turn having sharper
updates. However, the accuracy also suffers a significant drop, likely because
even the incorrect beliefs will get updated twice. In contrast, our proposed
method is able to reduce the number of turns without compromising the
accuracy.

We further examine the effect of removing various components of the
presupposition handling pipeline. Specifically, we consider what happens when
we remove presupposition handling during question selection, as well as when
we remove it during belief updates. As we see in Table 4, only adding
presupposition handling in the question selection results in very little
change. This may be because the better selection quality is offset by the
model’s inability to update its beliefs accordingly. On the other hand, only
adding it in the belief updates results in much longer turns. Qualitatively,
we observed that the model tends to get "stuck" more in this scenario, as
there are games which would exceed 10 turns. These ablations confirm the
importance of our full approach for handling presuppositions in informative
question generation.

###  6.2 Qualitative Analysis

Table 5 contains an example set of images, together with the self-play results
for three types of models. The images were taken from a game in the hard
setting, with the common subject “food.”

Here, the open-ended (with presuppp.) model performs the best, finishing the
game in a single turn (Answer: “Dessert”) and guessing the response correctly.
Meanwhile, if we remove the presupposition handling, the model generates an
unanswerable first question “What is next to the knife?”, as there is no knife
in the image. The self-play user simulator responds with “cake”, but since the
model cannot handle presuppositions, it mistakenly gets led towards Image 7
instead of Image 1 and hence predicts incorrectly. Meanwhile, the polar yes/no
setting asks a sensible question, but it is quite inefficient compared to the
type of questions asked by the open-ended questions.

###  6.3 Further Discussion

Here, we address the topic of human cognitive load. This is crucial for a
system which interacts with humans, as we do not wish to increase accuracy at
the expense of substantially increasing cognitive effort for users. Indeed, a
part of our model’s performance improvements likely emerge due to the dialogue
partner offering more comprehensive information. However, we argue that our
model does not lead to an increased cognitive load but rather makes it easier
overall for the users. We can view total cognitive load as a variable
dependent on two factors: the number of questions in the interaction, and the
cognitive load-per-question. Our approach produces a substantial reduction in
the number of questions required, from 3.3 turns to 1.7 turns in the easy
setting and 3.4 to 2.7 turns in the hard setting (Table 2). Although
investigating load-per-question is inherently difficult, we argue
qualitatively that the "wh-" questions generated by our approach are typically
natural (Table 6) without very complex syntactic structure and typically
involving binary relationships (e.g. "Q: What is next to the knife? A: Cake.")
Indeed, when playing this game, humans naturally ask open-ended questions
without placing undue burden on their communicative partners.

##  7 Related Work

#### Interactive information seeking

Ambiguity is a persistent challenge in language. Recent work has approached
ambiguity resolution through the lens of interactive information seeking,
borrowing from the optimal experimental design literature (Lindley, 1956).
These methods rely on a partner model, which is used to measure the
informativity of questions (Rao and Daumé III, 2018; Lee et al., 2018;
Shridhar and Hsu, 2018; Yu et al., 2020). Most related to ours is the work by
White et al. (2021), which proposes an unsupervised approach to informative
question generation. Their approach is limited to polar yes/no questions,
which we extend to open-ended _wh-_ questions. Krishna et al. (2019) also
present an approach to generating open-ended informative questions by training
a variational autoencoder on VQA datasets. Similar to our approach, their
method selects questions that are both (1) informative and (2) relevant to the
image. Our approach optimizes for similar objectives, but uses off-the-shelf
VQA and LLMs without any training data for generating questions.

#### Presupposition errors and question decomposition

Presupposition errors lead to one form of unanswerable question (Davis, 2020).
Such questions have been extensively explored in literature (Zhu et al., 2019;
Kim et al., 2021a). Past work has shown that models trained on datasets
without unanswerable questions often fail to generalize to unanswerable
questions (Rajpurkar et al., 2018; Kim et al., 2023). We propose a method for
adapting a model trained only on answerable questions to unanswerable
questions via question decomposition, without supervision. This contrasts with
recent work on question decomposition, which has focused on decomposing
complex questions (Perez et al., 2020; Press et al., 2023).

#### Collaborative reference games

Collaborative reference games focus on building common ground in a symmetric
dialogue setting, where both participants have equal roles (He et al., 2017;
Haber et al., 2019; Udagawa and Aizawa, 2019, 2021; Fried et al., 2021; Khani
et al., 2018). While both settings require reasoning, we focus on the
asymmetric question-answering setting, where the asymmetry prevents the
questioner from relying too heavily on their partner.

##  8 Conclusion

We present an approach for generating open-ended informative questions in a
grounded multi-turn image identification task. As compared to previous methods
which ask questions with constrained answer spaces, our method is able to ask
more general questions. We show that directly asking open-ended questions may
lead to presupposition errors, where off-the-shelf VQA models may answer
questions despite their irrelevance to images. To address this, we propose a
two-stage method where we first formulate a question to verify the
presupposition, then update the belief distribution over the images
accordingly. Through both human and self-play evaluations, we show that asking
presupposition-aware open-ended questions outperforms the previous state-of-
the-art in both accuracy and efficiency.

## Acknowledgements

We thank Jing Yu Koh and Saujas Vaduguru for feedback on initial drafts of our
paper. We thank Jiefu Ou for guidance with Amazon MTurk evaluations.

## Limitations

The method that we are proposing is able to ask questions that achieve high
information gain. However, there are some limitations to the way the model
generates and selects questions, as well as with the way self-play evaluations
are conducted. First, the reponses allowed by the system is limited by the
answer space of the VQA models. While this is usually very exhaustive (around
4000 for ViLT), it may not be enough to cover certain good answers that humans
may want to give to certain questions. In addition, questions are generated
using captions, not directly from images. Because of this intermediate step,
there may be additional room for the models to make an error. In our medium
and hard game settings, we also select similar images using a subject/caption
system, rather than taking into account the images. This means that the model
may miss out on certain parts of the image that the caption is not able to
capture. One alternative is to instead consider using the image space using
more modern models such as CLIP. Lastly, with our self-play experiments, our
response models only answer based on the question and the target image. It
does not take into consideration all the other images, which may be crucial in
helping to provide answers that can better clarify or disambiguate.

## Ethics

In our human evaluations, we recruit workers from Amazon Mechanical Turk. We
made sure to compensate these annotators fairly, paying them $0.25$ USD per
HIT. From our estimates, a HIT on average can be comfortably completed in less
than a minute, so given that pace, the compensation adds up to more than
$15.00$ USD per hour.

## References

  * Davis (2020) Ernest Davis. 2020.  Unanswerable questions about images and texts.  _Frontiers in Artificial Intelligence_ , 3.
  * Fried et al. (2021) Daniel Fried, Justin T. Chiu, and Dan Klein. 2021.  Reference-centric models for grounded collaborative dialogue.  In _Proceedings of EMNLP_.
  * Goyal et al. (2016) Yash Goyal, Tejas Khot, Douglas Summers-Stay, Dhruv Batra, and Devi Parikh. 2016.  Making the v in vqa matter: Elevating the role of image understanding in visual question answering.  _International Journal of Computer Vision_ , 127:398–414.
  * Haber et al. (2019) Janosch Haber, Tim Baumgärtner, Ece Takmaz, Lieke Gelderloos, Elia Bruni, and Raquel Fernández. 2019.  The PhotoBook dataset: Building common ground through visually-grounded dialogue.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1895–1910, Florence, Italy. Association for Computational Linguistics.
  * He et al. (2017) He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang. 2017.  Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings.  _CoRR_ , abs/1704.07130.
  * Khani et al. (2018) Fereshte Khani, Noah Goodman, and Percy Liang. 2018.  Planning, inference and pragmatics in sequential language games.  _Transactions of the Association for Computational Linguistics_ , 6:543–555.
  * Kim et al. (2023) Najoung Kim, Phu Mon Htut, Samuel R. Bowman, and Jackson Petty. 2023.  (QA)2: Question answering with questionable assumptions.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 8466–8487, Toronto, Canada. Association for Computational Linguistics.
  * Kim et al. (2021a) Najoung Kim, Ellie Pavlick, Burcu Karagol Ayan, and Deepak Ramachandran. 2021a.  Which linguist invented the lightbulb? presupposition verification for question-answering.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 3932–3945, Online. Association for Computational Linguistics.
  * Kim et al. (2021b) Wonjae Kim, Bokyung Son, and Ildoo Kim. 2021b.  Vilt: Vision-and-language transformer without convolution or region supervision.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 5583–5594. PMLR.
  * Kitaev and Klein (2018) Nikita Kitaev and Dan Klein. 2018.  Constituency parsing with a self-attentive encoder.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2676–2686, Melbourne, Australia. Association for Computational Linguistics.
  * Krishna et al. (2019) Ranjay Krishna, Michael Bernstein, and Li Fei-Fei. 2019.  Information maximizing visual question generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2008–2018.
  * Lee et al. (2018) Sang-Woo Lee, Yu-Jung Heo, and Byoung-Tak Zhang. 2018.  Answerer in questioner’s mind: Information theoretic approach to goal-oriented visual dialog.  In _Neural Information Processing Systems_.
  * Lewis (1969) David K. Lewis. 1969.  _Convention: A Philosophical Study_.  Harvard University Press.
  * Li et al. (2022) Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi. 2022.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In _ICML_.
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. 2014.  Microsoft coco: Common objects in context.  In _European Conference on Computer Vision_.
  * Lindley (1956) D. V. Lindley. 1956.  On a Measure of the Information Provided by an Experiment.  _The Annals of Mathematical Statistics_ , 27(4):986 – 1005.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.  _ArXiv_ , abs/2303.08774.
  * Perez et al. (2020) Ethan Perez, Patrick Lewis, Wen-tau Yih, Kyunghyun Cho, and Douwe Kiela. 2020.  Unsupervised question decomposition for question answering.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 8864–8880, Online. Association for Computational Linguistics.
  * Press et al. (2023) Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis. 2023.  Measuring and narrowing the compositionality gap in language models.
  * Rajpurkar et al. (2018) Pranav Rajpurkar, Robin Jia, and Percy Liang. 2018.  Know what you don’t know: Unanswerable questions for SQuAD.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 784–789, Melbourne, Australia. Association for Computational Linguistics.
  * Rao and Daumé III (2018) Sudha Rao and Hal Daumé III. 2018.  Learning to ask good questions: Ranking clarification questions using neural expected value of perfect information.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2737–2746, Melbourne, Australia. Association for Computational Linguistics.
  * Shridhar and Hsu (2018) Mohit Shridhar and David Hsu. 2018.  Interactive visual grounding of referring expressions for human-robot interaction.  _CoRR_ , abs/1806.03831.
  * Udagawa and Aizawa (2019) Takuma Udagawa and Akiko Aizawa. 2019.  A natural language corpus of common grounding under continuous and partially-observable context.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33(01):7120–7127.
  * Udagawa and Aizawa (2021) Takuma Udagawa and Akiko Aizawa. 2021.  Maintaining common ground in dynamic environments.  _Transactions of the Association for Computational Linguistics_ , 9:995–1011.
  * White et al. (2021) Julia White, Gabriel Poesia, Robert Hawkins, Dorsa Sadigh, and Noah Goodman. 2021.  Open-domain clarification question generation without question examples.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 563–570, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Yu et al. (2020) Lili Yu, Howard Chen, Sida I. Wang, Tao Lei, and Yoav Artzi. 2020.  Interactive classification by asking informative questions.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 2664–2680, Online. Association for Computational Linguistics.
  * Zhu et al. (2019) Haichao Zhu, Li Dong, Furu Wei, Wenhui Wang, Bing Qin, and Ting Liu. 2019.  Learning to ask unanswerable questions for machine reading comprehension.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4238–4248, Florence, Italy. Association for Computational Linguistics.

##  Appendix A Question Generation Prompts

In generating the prompt to convert captions to images, we initially only used
few-shot examples with a simple system prompt. However, we soon discovered
that the model was generating questions which were impossible to answer just
visually (e.g. “How tall is the man?”) We thus modified our prompt. For our
experiments, we settled with providing OpenAI’s GPT-4 OpenAI (2023)
ChatCompletion API with the following system prompt.

> "You are tasked to produce reasonable questions from a given caption.
> The questions you ask must be answerable only using visual information.
> As such, never ask questions that involve exact measurement such as ’How
> tall’, ’How big’, or ’How far’, since these cannot be easily inferred from
> just looking at an object.
> Likewise, never ask questions that involve age (’How old’), composition
> (’What is it made of’), material, emotion, or personal relationship.
> When asking ’Where’ questions, the subject of your question must be a person
> or a small object.
> Never ask questions that can be answered with yes or no.
> When referring to objects, try to be general. For example, instead of saying
> ’cat’, you should say ’animal’. Instead of saying ’cake’, you should say
> ’food’.
> I repeat, when referring to object, try to be general!
> Good questions to ask include general ’What color’, as well as general
> probing questions such as ’What is the man doing?" or ’What is the main
> subject of the image?’
> For each caption, please generate 3-5 reasonable questions."

In addition, we use the following hand-crafted few-shot examples:

  1. 1.

Caption: A living room with a couch, coffee table and two large windows with
white curtains. Questions: What color is the couch? How many windows are
there? How many tables are there? What color is the table? What color are the
curtains? What is next to the table? What is next to the couch?

  2. 2.

Caption: A cat is wearing a pink wool hat. Questions: What color is the
animal? What color is the hat? What is the cat wearing?

  3. 3.

Caption: A stop sign with a skeleton painted on it, next to a car. Questions:
What color is the sign? What color is the car? What is next to the sign? What
is next to the car? What is on the sign? Where is the car?

  4. 4.

Caption: A man brushing his teeth with a toothbrush. Questions: What is the
man doing? Where is the man? What color is the toothbrush?

In the ChatCompletion API, these prompts are added alternately, with the user
providing the caption and the assistant returning the list of questions.

##  Appendix B Belief Update Calculation

In Section 3.3, we defined how the standard response (i.e., when the human
responds with an actual answer rather than “No Answer”) and the null response
(i.e., when the human responds with “No Answer”) affect the belief updates. We
list down the more fine-grained details below.

#### Standard Response.

We wish to compute the probability $P(y\mid x^{t},q,r)$. Note that here, we
use $y$ to denote the indicator variable that $i=y$. For all images $i$ we can
apply Bayes’ Rule to obtain that $P(y\mid x^{t},q,r)$ is proportional to

$P(r\mid x^{t},y,q)P(q\mid x^{t},y)P(y\mid x^{t})$ (5)

Here, $P(r\mid x^{t},y,q)$ can be calculated from the VQA model described in
Section 3.2 (we assume $VQA(r\mid q,i)$ is independent of the history
$x^{t}$), while $P(q\mid x^{t},y)$ is essentially the result of the question
selection process. Lastly, $P(y\mid x^{t})$ is recursively computed since we
know $P(y\mid x^{0})$ (uniform) and $P(y\mid x^{t})=P(y\mid x^{t-1},q,r)$ by
definition. These probabilities are then multiplied and normalized to compute
$P(y\mid x^{t},q,r)$ for each image at each timestep $t$.

#### Null Response.

Here, the calculation for $P(y\mid x^{t},q,r_{null})$ is done similar to the
standard case, except with the change that we consider $P(r_{null}\mid
x^{t},y,q)$ instead of a standard $r$. Because “No Answer” is not in the
vocabulary for our VQA model, we instead design a proxy method to calculate
$P(r_{null}\mid x^{t},i,q)$. To do this, we once again assume that $x^{t}$ is
independent of $VQA(r\mid q,i)$ and calculate $P(r_{null}|i,q)$ similar to how
we calculated $P(\text{Relevance}(q,i))$ in Eq. 2. However, rather than
calculating $\frac{1}{j}\sum_{k=1}^{j}VQA(r_{\text{yes}}|q_{yn_{k}},i)$ as in
Eq. 2, we instead calculate
$P(\text{Irrelevance}(q,i))=\frac{1}{j}\sum_{k=1}^{j}VQA(r_{\text{no}}|q_{yn_{k}},i)$.
We then approximate $P(r_{null}\mid i,q)\approx P(\text{Irrelevance}(q,i))$.
When multiplied with the other probabilities in Eq. 4, this results in
upweighting the images which do not contain the subject, and downweighting the
images which contain the subject.

##  Appendix C Yes/No Question Generation

To generate a set of yes/no questions from a given caption, we follow the
method of White et al. (2021). First, we use a constituency parser Kitaev and
Klein (2018) to parse the nouns and noun phrase subtrees in the caption. These
nouns and noun phrases are then directly converted to questions by asking “Is
there a [NP]” or “Are there [NP]” based on rule-based plurality checking.
These questions are then used as the yes/no questions generated from the
caption.

##  Appendix D Additional Experiment Settings

The game is continued until the model’s confidence in a certain image exceeds
a certain threshold $\gamma$. Based on our initial validation experiments, we
found $\gamma=0.8$ to work the best. In instances where the model never
reaches $\gamma$ within a certain number of turns, we simply terminate the
game and select the image with the highest probability according to the model.
In our experiments, we stopped the game if it exceeded 20 turns.

Setting |  First Question |  Response
---|---|---
Polar Yes/No |  Is there a restaurant table? |  Yes
|  Is there a woman? |  Yes
|  Is there a wooden table? |  Yes
|  Guess: Image 8 (Incorrect) |
Open-Ended (No Presupp.) |  What is next to the knife? |  Cake
|  What is on top of the food? |  Sugar
|  Guess: Image 7 (Incorrect) |
Open-Ended (With Presupp.) |  What type of food are the people eating? |  Dessert
|  Guess: Image 1 (Correct) |

Table 6: Full game conversations for all settings.

##  Appendix E Human Evaluations

We recruit annotators from Amazon Mechanical Turk. To filter for high-quality
annotators, we restrict only to annotators with >10,000 completed tasks, >98%
acceptance rate, and are located in the United States. To further ensure that
the annotators understand the requirements and rules of our tasks, we first
add a qualifying requirement in the form of a test that the annotators must
complete before they can perform any HIT.

This test consists of four sample games of our task, each chosen specifically
to test for a particular skill in completing our task. Specifically:

  1. 1.

Q1: Sample task for the polar yes/no setting. Main goal is to get the
annotators familiar with this setting. Must complete in $\leq$ 3 turns.

  2. 2.

Q2: Sample task for the open-ended _wh-_ setting. Main goal is to get the
annotators familiar with this setting. Must complete in 1 turn.

  3. 3.

Q3: Tests for knowing when to use the “No Answer” option. Must complete in
$\leq$ 2 turns.

  4. 4.

Q4: Tests for being able to reason pragmatically, i.e., look at all the images
and identify what distinguishes the target image. Must complete in 1 turn.

To pass this qualifying test, the annotators must correctly make the model
guess the target image in all 4 rounds, and they must complete each round
within the allotted number of turns. For the open-ended _wh-_ games, in order
to reduce unpredictability in uman behavior, we restricted the anwer space to
the vocabulary of the VQA model (i.e. ViLT VQA Kim et al. (2021b)), though
this is not strictly necessary.

We display screenshots of system instructions, as well as an example of a
polar IsA game and an open-ended _wh-_ game in Figure 3.

Figure 3: Our system instructions to all human annotators (top), an example of
a polar yes/no game (specifically Q1 in our qualifying test) (middle), an
example of an open-ended _wh-_ game (specifically Q2 in our qualifying test)
(bottom)

We make sure to compensate our Amazon Mechanical Turk workers fairly. (See
Ethics section for a discussion on this.)

##  Appendix F Additional Examples

In Table 5, we outlined the game statistics for 3 different settings. In this
appendix section, we list out the full games for all 3 settings in Table 6.


# Method for solving inverse spectral problems on quantum star graphs

Sergei A. Avdonin1, Vladislav V. Kravchenko2
1 Department of Mathematics and Statistics, University of Alaska, Fairbanks,
AK 99775, USA
2 Departamento de Matemáticas, Cinvestav, Unidad Querétaro,
Libramiento Norponiente #2000, Fracc. Real de Juriquilla, Querétaro, Qro.,
76230 MEXICO
e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A new method for solving inverse spectral problems on quantum star graphs is
proposed. The method is based on Neumann series of Bessel functions
representations for solutions of Sturm-Liouville equations. The
representations admit estimates for the series remainders which are
independent of the real part of the square root of the spectral parameter.
This feature makes them especially useful for solving direct and inverse
spectral problems requiring calculation of solutions on large intervals in the
spectral parameter. Moreover, the first coefficient of the representation is
sufficient for the recovery of the potential.

The method for solving the inverse spectral problem on the graph consists in
reducing the problem to a two-spectra inverse Sturm-Liouville problem on each
edge. Then a system of linear algebraic equations is derived for computing the
first coefficient of the series representation for the solution on each edge
and hence for recovering the potential. The proposed method leads to an
efficient numerical algorithm that is illustrated by a number of numerical
tests.

##  1 Introduction

Under quantum graphs or, in other words, differential equation networks we
understand differential operators on metric graphs coupled by certain vertex
matching conditions. Network-like structures play a fundamental role in many
problems of science and engineering. The classical problem here that comes
from applications is the problem of oscillations of the flexible structures
made of strings, beams, cables, and struts. These models describe bridges,
space-structures, antennas, transmission-line posts and other typical objects
of civil engineering. Quantum graphs arise also as natural models of various
phemonema in chemistry (free-electron theory of conjugated molecules), biology
(genetic networks, dendritic trees), geophysics, environmental science,
decease control, and even in Internet (Internet or network tomography). In
physics, interest to quantum graphs arose, in particular, from applications to
nano-electronics and quantum waveguides. On the other hand, quantum graph
theory gives rise to numerous challenging problems related to many areas of
mathematics from combinatorics to PDE and spectral theory. A number of surveys
and collections of papers on quantum graphs appeared last years, and the first
books on this topic by Berkolaiko and Kuchment [9], Mugnolo [21] and Kurasov
[17] contain excellent lists of references.

Inverse spectral theory of network-like structures is an important part of the
rapidly developing area of applied mathematics — analysis on graphs. The known
results in this direction concern almost exclusively trees, i.e. graphs
without cycles, see e.g. [18, 24, 8, 6, 7, 4].

To date, there are few papers containing numerical results for inverse
problems on graphs, all of them concern only very simple trees [8, 3]. It is
known that the problems of space discretization of differential equations on
metric graphs turn out to be very difficult, and even the forward boundary
value problems on graphs contain a lot of numerical challenges (see, e.g.
[2]).

In the present work we develop a new method for solving inverse spectral
problems on compact quantum star graphs that leads to efficient numerical
algorithms. This method is based on Neumann series of Bessel functions
representations for solutions of Sturm-Liouville equations. The method was
proposed in [14] and successfully applied to solving direct and inverse
spectral problems on intervals and the semiaxis in [13]. Here we extend this
method to the inverse spectral problem for the Schrödinger equation on star
graphs.

The Neumann series of Bessel functions representations for solutions of Sturm-
Liouville equations,

$-y^{\prime\prime}+q(x)y=\rho^{2}y,$

possess two remarkable features which make them especially convenient for
solving inverse problems. The remainders of the series admit
$\rho$-independent bounds for $\rho\in\mathbb{R}$, and the potential of the
equation can be recovered from the very first coefficient of the series. The
first feature allows us to work with the approximate solutions on very large
intervals in $\rho$, and the second implies that computationally satisfactory
results require considering a reduced number of the terms of the series which
eventually results in a reduced number of linear algebraic equations which
should be solved in each step.

The method consists of the following steps. First, using the given spectral
data we compute coefficients of the series representations for solutions
satisfying the homogeneous Dirichlet condition at the boundary vertices and
for their derivatives at the end point of each edge, which is associated with
the common vertex of the star graph. This first step allows us to split the
problem on the graph into separate problems on each edge. Second, the set of
coefficients for the series representation of the solution, evaluated at the
end point of the interval allows us to compute the Dirichlet-Dirichlet
eigenvalues of the potential on each edge. Moreover, the first feature of the
series representations implies that if necessary hundreds of the eigenvalues
can be computed with uniform accuracy, and for this few coefficients of the
series representations are sufficient. Next, the knowledge of the Dirichlet-
Dirichlet eigenvalues allows us to compute the important parameter (half of
the integral of the potential) that is necessary for computing the Dirichlet-
Neumann eigenvalues, for which, besides the parameter, the coefficients from
the series representation of the derivative of the solution are used.

Thus, the inverse spectral problem on a graph is reduced to a two spectra
inverse Sturm-Liouville problem on each edge. Results on the uniqueness and
solvability of the two spectra problem are well known and can be found, e.g.,
in [11], [20], [23], [25]. For this problem we propose a method which again
involves the Neumann series of Bessel functions representations for solutions
and their derivatives. It allows us to compute multiplier constants [10]
relating the Dirichlet-Neumann eigenfunctions associated with the same
eigenvalues but normalized at the opposite endpoints of the interval. This
leads to a system of linear algebraic equations for the coefficients of their
series representations already for interior points of the interval. Solving
the system we find the very first coefficient, from which the potential is
recovered. Note that the Neumann series of Bessel functions representations
were first used for solving inverse Sturm-Liouville problems in [12]. Later on
the approach from [12] was improved in [13] and [16]. In these papers the
system of linear algebraic equations was obtained from the Gelfand-Levitan
integral equation. Here we develop another approach which is based on the
consideration of the eigenfunctions normalized at the opposite endpoints and
does not involve the Gelfand-Levitan equation.

##  2 Problem setting

Let $\Omega$ denote a compact star graph consisting of $M$ edges
$e_{1}$,…,$e_{M}$ connected at the vertex $v$. Every edge $e_{j}$, is
identified with an interval $(0,L_{j})$ of the real line in such a way that
zero corresponds to the boundary vertex $\gamma_{j}$, and the endpoint $L_{j}$
corresponds to the vertex $v$. By $\Gamma$ we denote the set of the boundary
vertices of $\Omega$, $\Gamma=\left\\{\gamma_{1},\ldots,\gamma_{M}\right\\}$.
We associate the standard spectral problem on the graph $\Omega$ with a real
valued potential $q\in L_{2}(\Omega)$:

$-w^{\prime\prime}(x)+q(x)w(x)=\lambda w(x),$ (2.1) $w\in C(\Omega),$ (2.2)
$\sum_{j=1}^{M}\partial w_{j}(v)=0,$ (2.3) $w(\gamma_{j})=0,\quad
j=1,\ldots,M,$ (2.4)

where $\partial w_{j}(v)$ denotes the derivative of $w$ at the vertex $v$
taken along the edge $e_{j}$ in the direction outward the vertex. The sum in
the Kirchhoff-Neumann condition (2.3) is taken over all the edges $e_{j}$,
$j=1,\ldots,M$.

Thus, if for a certain value of the spectral parameter $\lambda$ there exists
a nontrivial solution $w$ of the problem (2.1)-(2.4), it consists of $M$
components $w_{j}(x)$ associated with the corresponding edges $e_{j}$, such
that each component satisfies the equation

$-w_{i}^{\prime\prime}(x)+q_{i}(x)w_{i}(x)=\lambda w_{i}(x),\quad
x\in(0,L_{i}),$ (2.5)

the initial condition

$w_{i}(0)=0$ (2.6)

and the coupling relations

$w_{i}(L_{i})=w_{j}(L_{j})\quad\text{for all
}i,j\in\left\\{1,\ldots,M\right\\},$ (2.7)
$\sum_{i=1}^{M}w_{i}^{\prime}(L_{i})=0.$ (2.8)

The potential $q_{i}(x)$ in (2.5) is the component of $q(x)$ corresponding to
the edge $e_{i}$.

It is well known that problem (2.1)-(2.4) has a discrete spectrum consisting
of an infinite sequence of eigenvalues $\lambda_{1}\leq\lambda_{2}\leq\ldots$,
$\lambda_{k}\rightarrow+\infty$, and the corresponding eigenfunctions $u_{1}$,
$u_{2}$,… can be chosen so that $\left\\{u_{k}\right\\}_{k=1}^{\infty}$ forms
an orthonormal basis in $\mathcal{H}:=L_{2}(\Omega)$,

$\left\langle
u_{i},u_{j}\right\rangle_{\mathcal{H}}=\int_{\Omega}u_{i}(x)u_{j}(x)dx=\delta_{ij}.$

Denote $\chi_{k}(\gamma):=\partial u_{k}(\gamma)$, $\gamma\in\Gamma$. Let
$\alpha_{k}$ be the $M$-component column vector defined as

$\alpha_{k}=\operatorname{col}\left(\frac{\chi_{k}(\gamma)}{\sqrt{\lambda_{k}}}\right)_{\gamma\in\Gamma}.$

###### Definition 2.1

The set of pairs $\left\\{\lambda_{k},\alpha_{k}\right\\}_{k=1}^{\infty}$ is
called the Dirichlet spectral data of the graph $\Omega$.

The inverse spectral problem consists in recovering the potential $q(x)$ from
the Dirichlet spectral data. The aim of the present work is to propose a
method for its solution.

##  3 Neumann series of Bessel functions representations

By $\varphi_{i}(\rho,x)$ and $S_{i}(\rho,x)$ we denote the solutions of the
equation

$-y^{\prime\prime}(x)+q_{i}(x)y(x)=\rho^{2}y(x),\quad x\in(0,L_{i})$

satisfying the initial conditions

$\varphi_{i}(\rho,0)=1,\quad\varphi_{i}^{\prime}(\rho,0)=0,$
$S_{i}(\rho,0)=0,\quad S_{i}^{\prime}(\rho,0)=1.$

Here $\rho=\sqrt{\lambda}$, $\operatorname{Im}\rho\geq 0$. The main tool used
in the present work are the series representations obtained in [14] for the
solutions of (2.5) and their derivatives.

######  Theorem 3.1 ([14])

The solutions $\varphi_{i}(\rho,x)$ and $S_{i}(\rho,x)$ and their derivatives
with respect to $x$ admit the following series representations

$\displaystyle\varphi_{i}(\rho,x)$ $\displaystyle=\cos\left(\rho
x\right)+\sum_{n=0}^{\infty}(-1)^{n}g_{i,n}(x)\mathbf{j}_{2n}(\rho x),$ (3.1)
$\displaystyle S_{i}(\rho,x)$ $\displaystyle=\frac{\sin\left(\rho
x\right)}{\rho}+\frac{1}{\rho}\sum_{n=0}^{\infty}(-1)^{n}s_{i,n}(x)\mathbf{j}_{2n+1}(\rho
x),$ (3.2) $\displaystyle\varphi_{i}^{\prime}(\rho,x)$
$\displaystyle=-\rho\sin\left(\rho
x\right)+\frac{1}{2}\int_{0}^{x}q_{i}(t)\,dt\,\cos\left(\rho
x\right)+\sum_{n=0}^{\infty}(-1)^{n}\gamma_{i,n}(x)\mathbf{j}_{2n}(\rho x),$
(3.3) $\displaystyle S_{i}^{\prime}(\rho,x)$ $\displaystyle=\cos\left(\rho
x\right)+\frac{1}{2\rho}\int_{0}^{x}q_{i}(t)\,dt\,\sin\left(\rho
x\right)+\frac{1}{\rho}\sum_{n=0}^{\infty}(-1)^{n}\sigma_{i,n}(x)\mathbf{j}_{2n+1}(\rho
x),$ (3.4)

where $\mathbf{j}_{k}(z)$ stands for the spherical Bessel function of order
$k$ (see, e.g., [1]). The coefficients $g_{i,n}(x)$, $s_{i,n}(x)$,
$\gamma_{i,n}(x)$ and $\sigma_{i,n}(x)$ can be calculated following a simple
recurrent integration procedure (see [14] or [13, Sect. 9.4]), starting with

$\displaystyle g_{i,0}(x)$ $\displaystyle=\varphi_{i}(0,x)-1,\quad
s_{i,0}(x)=3\left(\frac{S_{i}(0,x)}{x}-1\right),$ (3.5)
$\displaystyle\gamma_{i,0}(x)$
$\displaystyle=g_{i,0}^{\prime}(x)-\frac{1}{2}\int_{0}^{x}q_{i}(t)\,dt,\quad\sigma_{i,0}(x)=\frac{s_{i,0}(x)}{x}+s_{i,0}^{\prime}(x)-\frac{3}{2}\int_{0}^{x}q_{i}(t)\,dt.$

For every $\rho\in\mathbb{C}$ all the series converge pointwise. For every
$x\in\left[0,L_{i}\right]$ the series converge uniformly on any compact set of
the complex plane of the variable $\rho$, and the remainders of their partial
sums admit estimates independent of $\operatorname{Re}\rho$.

This last feature of the series representations (the independence of
$\operatorname{Re}\rho$ of the estimates for the remainders) is of crucial
importance for what follows. In particular, it means that for
$S_{i,N}(\rho,x):=\frac{\sin\left(\rho
x\right)}{\rho}+\frac{1}{\rho}\sum_{n=0}^{N}(-1)^{n}s_{i,n}(x)\mathbf{j}_{2n+1}(\rho
x)$ (and analogously for $S_{i,N}^{\prime}(\rho,x)$) the estimate holds

$\left|S_{i}(\rho,x)-S_{i,N}(\rho,x)\right|<\varepsilon_{i,N}(x)$ (3.6)

for all $\rho\in\mathbb{R}$, where $\varepsilon_{i,N}(x)$ is a positive
function tending to zero as $N\rightarrow\infty$. That is, the approximate
solution $S_{i,N}(\rho,x)$ approximates the exact one equally well for small
and for large values of $\rho$. This is especially convenient when considering
direct and inverse spectral problems. Moreover, for a fixed $z$ the numbers
$\mathbf{j}_{k}(z)$ rapidly decrease as $k\rightarrow\infty$, see, e.g., [1,
(9.1.62)]. Hence, the convergence rate of the series for any fixed $\rho$ is,
in fact, exponential.

More detailed estimates for the series remainders depending on the regularity
of the potential can be found in [14].

Note that formulas (3.5) indicate that the potential $q_{i}(x)$ can be
recovered from the first coefficients of the series (3.1) or (3.2). We have

$q_{i}(x)=\frac{g_{i,0}^{\prime\prime}(x)}{g_{i,0}(x)+1}$ (3.7)

and

$q_{i}(x)=\frac{\left(xs_{i,0}(x)\right)^{\prime\prime}}{xs_{i,0}(x)+3x}.$
(3.8)

##  4 Solution of the direct problem

Due to the Dirichlet condition at the boundary vertices the component $w_{i}$
of the eigenfunction has the form

$w_{i}(x)=c_{i}(\rho)S_{i}(\rho,x),$

where $c_{i}(\rho)$ is a constant. Equalities (2.7) give us $M-1$ equations of
the form

$c_{i}(\rho)S_{i}(\rho,L_{i})-c_{i+1}(\rho)S_{i+1}(\rho,L_{i+1})=0,\quad
i=1,\ldots,M-1,$

and equality (2.8) gives us the $M$-th equation

$\sum_{i=1}^{M}c_{i}(\rho)S_{i}^{\prime}(\rho,L_{i})=0.$

This system of $M$ equations can be written in the matrix form

$\mathbf{S}(\rho)\overrightarrow{c}(\rho)=$
$\left(\begin{array}[c]{cccccc}S_{1}(\rho,L_{1})&-S_{2}(\rho,L_{2})&0&0&\ldots&0\\\
0&S_{2}(\rho,L_{2})&-S_{3}(\rho,L_{3})&0&\ldots&0\\\ &&\ddots&&&\\\
0&0&\ldots&0&S_{M-1}(\rho,L_{M-1})&-S_{M}(\rho,L_{M})\\\
S_{1}^{\prime}(\rho,L_{1})&S_{2}^{\prime}(\rho,L_{2})&\ldots&&S_{M-1}^{\prime}(\rho,L_{M-1})&S_{M}^{\prime}(\rho,L_{M})\end{array}\right)\left(\begin{array}[c]{c}c_{1}(\rho)\\\
c_{2}(\rho)\\\ \vdots\\\ c_{M-1}(\rho)\\\ c_{M}(\rho)\end{array}\right)=0.$

The number $\rho$ is a square root of an eigenvalue if and only if the
determinant of the matrix $\mathbf{S}(\rho)$ is zero. Computation of zeros of
$\det\mathbf{S}(\rho)$ can be easily performed by using the series
representations (3.2) and (3.4). Let $\rho_{k}$ be such a zero. The vector
$\overrightarrow{c}(\rho_{k})$ then is an eigenvector of
$\mathbf{S}(\rho_{k})$ corresponding to the zero eigenvalue of
$\mathbf{S}(\rho_{k})$. In order to compute the column vector $\alpha_{k}$ we
notice that $\alpha_{k}=a\overrightarrow{c}(\rho_{k})$, where $a$ is a
constant such that

$\sum_{i=1}^{M}\left(ac_{i}(\rho_{k})\right)^{2}\rho_{k}^{2}\int_{0}^{L_{i}}S_{i}^{2}(\rho_{k},x)dx=1,$

which means that the corresponding eigenfunction is normalized. Thus,

$a^{2}=\left(\rho_{k}^{2}\sum_{i=1}^{M}c_{i}^{2}(\rho_{k})\int_{0}^{L_{i}}S_{i}^{2}(\rho_{k},x)dx\right)^{-1}$

and hence the components of $\alpha_{k}$ have the form

$\alpha_{k,i}=\frac{c_{i}(\rho_{k})}{\rho_{k}\sqrt{\sum_{i=1}^{M}c_{i}^{2}(\rho_{k})\int_{0}^{L_{i}}S_{i}^{2}(\rho_{k},x)dx}}.$
(4.1)

The components of the normalized eigenfunction $u_{k}$ have the form
$u_{k,i}(x)=\alpha_{k,i}\rho_{k}S_{i}(\rho_{k},x)$.

##  5 Solution of the inverse spectral problem

The method for solving the inverse problem consists of several steps. Given
the spectral data, first, we compute the constants
$\left\\{s_{i,n}(L_{i})\right\\}$ and $\left\\{\sigma_{i,n}(L_{i})\right\\}$
for every $i=1,\ldots,M$, that is, the values of the coefficients from (3.2)
and (3.4) at the endpoint of the edge $e_{i}$. This first step allows us to
split the problem on the graph and reduce it to the problems on the edges.
This is because the knowledge of the numbers $\left\\{s_{i,n}(L_{i})\right\\}$
and $\left\\{\sigma_{i,n}(L_{i})\right\\}$ allows us in the second step to
compute the Dirichlet-Dirichlet and Dirichlet-Neumann spectra for the
potential $q_{i}(x)$, $x\in\left[0,L_{i}\right]$, thus obtaining a two-spectra
inverse problem for each component of the potential $q(x)$.

In the third step the two-spectra inverse problem is solved with the aid of
the representation (3.2) and an analogous series representation for the
solution $\psi_{i}(\rho,x)$ of (2.5) satisfying the initial conditions

$\psi_{i}(\rho,L_{i})=1,\quad\psi_{i}^{\prime}(\rho,L_{i})=0.$ (5.1)

The two-spectra inverse problem reduces to a system of linear algebraic
equations, from which we obtain the coefficient $s_{i,0}(x)$. Finally, the
potential $q_{i}(x)$ is calculated from (3.8).

###  5.1 Reduction to the two spectra inverse problem on the edge

Given the set of the Dirichlet spectral data, that is, given the numbers
$\rho_{k}$ and the constants $c_{i}(\rho_{k})$ for which the equalities are
valid

$c_{i}(\rho_{k})S_{i}(\rho_{k},L_{i})-c_{i+1}(\rho_{k})S_{i+1}(\rho_{k},L_{i+1})=0,\quad
i=1,\ldots,M-1$ (5.2)

and

$\sum_{i=1}^{M}c_{i}(\rho_{k})S_{i}^{\prime}(\rho_{k},L_{i})=0.$ (5.3)

Note that $c_{i}(\rho_{k})=\chi_{k}(\gamma_{i})=\alpha_{k,i}\rho_{k}$.

Consider equations (5.2). With the aid of (3.2) they can be written in the
form

$\displaystyle
c_{i}(\rho_{k})\sum_{n=0}^{\infty}(-1)^{n}s_{i,n}(L_{i})\mathbf{j}_{2n+1}(\rho_{k}L_{i})-c_{i+1}(\rho_{k})\sum_{n=0}^{\infty}(-1)^{n}s_{i+1,n}(L_{i+1})\mathbf{j}_{2n+1}(\rho_{k}L_{i+1})$
$\displaystyle=-c_{i}(\rho_{k})\sin(\rho_{k}L_{i})+c_{i+1}(\rho_{k})\sin(\rho_{k}L_{i+1}),\quad
i=1,\ldots,M-1.$ (5.4)

The set of these equations gives us a system of linear algebraic equations for
computing the constants $s_{i,n}(L_{i})$, $i=1,\ldots,M$. For every $\rho_{k}$
we have $M-1$ equations of the form (5.4). The knowledge of a finite number of
spectral data allows us to compute a finite number of the approximate
constants $\left\\{s_{i,n}(L_{i})\right\\}_{n=0}^{N}$ for all $i=1,\ldots,M$.
Thus, for each edge $e_{i}$ we can compute the approximate function

$S_{i,N}(\rho,L_{i})=\frac{\sin\left(\rho
L_{i}\right)}{\rho}+\frac{1}{\rho}\sum_{n=0}^{N}(-1)^{n}s_{i,n}(L_{i})\mathbf{j}_{2n+1}(\rho
L_{i})$ (5.5)

for any value of $\rho$. Note that small perturbations in the coefficients
$s_{i,n}(L_{i})$, caused by truncating series in (5.4) and disposing of a
finite number of spectral data, provoke only small perturbations in the value
of $S_{i,N}(\rho,L_{i})$ due to the fact that the spherical Bessel functions
are bounded ($\left|\mathbf{j}_{m}(t)\right|\leq 1$) and decreasing
($\mathbf{j}_{m}(t)=\frac{\sin(t-m\pi/2)}{t}+O\left(\frac{1}{t^{2}}\right)$)
for all $m=0,1,\ldots$ and $t\in\mathbb{R}$.

The function (5.5) gives us an approximation of the solution $S_{i}(\rho,x)$
evaluated at the endpoint $L_{i}$. Moreover, for all real $\rho$ (and $\rho$
remaining in some strip $\left|\operatorname{Im}\rho\right|<C$) the difference
between the exact value $S_{i}(\rho,L_{i})$ and the approximate one
$S_{i,N}(\rho,L_{i})$ remains bounded by the same constant
$\varepsilon_{i,N}(L_{i})$ (see (3.6)).

Since $S_{i}(\rho,x)$ satisfies the Dirichlet condition at $x=0$, zeros of the
function $S_{i}(\rho,L_{i})$, which we denote by $\mu_{i,k}$, are the square
roots of the eigenvalues of the Sturm-Liouville problem

$-y^{\prime\prime}+q_{i}(x)y=\lambda y,\quad x\in(0,L_{i}),$ (5.6)
$y(0)=y(L_{i})=0.$ (5.7)

Thus, computation of zeros of the function $S_{i,N}(\rho,L_{i})$ gives us an
approximation of the Dirichlet-Dirichlet spectrum of the potential $q_{i}(x)$
(the spectrum of problem (5.6), (5.7)). The uniform bound (3.6) guarantees the
uniform bound of the absolute error of computation of the numbers $\mu_{i,k}$
[15, Proposition 7.1]. Moreover, arbitrarily many numbers $\mu_{i,k}$ can be
computed (hundreds or even thousands in practice). This gives us the
possibility to compute an important parameter

$\omega_{i}=\frac{1}{2}\int_{0}^{L_{i}}q_{i}(t)\,dt.$

Indeed, the sequence of numbers $\mu_{i,k}$ satisfies the asymptotic relation

$\mu_{i,k}=\frac{\pi}{L_{i}}k+\frac{\omega_{i}}{\pi k}+\frac{\xi_{i,k}}{k},$

where $\left\\{\xi_{i,k}\right\\}_{k=1}^{\infty}\in\ell_{2}$ (see, e.g., [25,
p. 18]). In other words, the sequence
$\left\\{k\left(\mu_{i,k}-\frac{\pi}{L_{i}}k\right)-\frac{\omega_{i}}{\pi}\right\\}_{k=1}^{\infty}$
belongs to $\ell_{2}$. Suppose that finitely many numbers
$\left\\{\mu_{i,k}\right\\}_{k=1}^{K_{D}}$ are known. Then an approximate
value of the parameter $\omega_{i}$ can be found by minimizing the
$\ell_{2}$-norm of the sequence
$\left\\{k\left(\mu_{i,k}-\frac{\pi}{L_{i}}k\right)-\frac{\omega_{i}}{\pi}\right\\}_{k=K_{0}}^{K_{D}}$,
where $K_{0}$ is some integer between $1$ and $K_{D}$, chosen to skip several
first numbers $\mu_{i,k}$ which can differ considerably from their
asymptotics. One can take, e.g., the floor of $K_{D}/2$, $K_{0}=\left\lfloor
K_{D}/2\right\rfloor$, and obtain that

$\omega_{i}\approx\arg\min_{\omega_{i}}\sum_{k=\left\lfloor
K_{D}/2\right\rfloor}^{K_{D}}\left(k\left(\mu_{i,k}-\frac{\pi}{L_{i}}k\right)-\frac{\omega_{i}}{\pi}\right)^{2}.$

Having computed the parameter $\omega_{i}$, with the aid of (3.4) equation
(5.3) can be written in the form

$\displaystyle
c_{1}(\rho_{k})\sum_{n=0}^{\infty}(-1)^{n}\sigma_{1,n}(L_{1})\mathbf{j}_{2n+1}(\rho_{k}L_{1})+\ldots+c_{M}(\rho_{k})\sum_{n=0}^{\infty}(-1)^{n}\sigma_{M,n}(L_{M})\mathbf{j}_{2n+1}(\rho_{k}L_{M})$
$\displaystyle=-\sum_{i=1}^{M}c_{i}(\rho_{k})\left(\rho_{k}\cos\left(\rho_{k}L_{i}\right)-\omega_{i}\sin\left(\rho_{k}L_{i}\right)\right).$

This gives us a system of linear algebraic equations for computing the
constants $\sigma_{i,n}(L_{i})$.

Thus, for each edge $e_{i}$ we can compute the value of the function

$S_{i,N}^{\prime}(\rho,L_{i})=\cos\left(\rho
L_{i}\right)+\frac{\omega_{i}}{\rho}\sin\left(\rho
L_{i}\right)+\frac{1}{\rho}\sum_{n=0}^{N}(-1)^{n}\sigma_{i,n}(L_{i})\mathbf{j}_{2n+1}(\rho
L_{i})$ (5.8)

for any value of $\rho$, which gives us the approximate derivative of the
corresponding solution evaluated at the endpoint $L_{i}$, and again,
$\left|S_{i}^{\prime}(\rho,L_{i})-S_{i,N}^{\prime}(\rho,L_{i})\right|$ remains
uniformly bounded for all $\rho$ belonging to a strip
$\left|\operatorname{Im}\rho\right|<C$.

With the aid of $S_{i,N}^{\prime}(\rho,L_{i})$ we compute the approximate
Dirichlet-Neumann eigenvalues of the potential $q_{i}(x)$. Indeed, considering
the Sturm-Liouville problem

$-y^{\prime\prime}+q_{i}(x)y=\lambda y,\quad x\in(0,L_{i}),$ (5.9)
$y(0)=y^{\prime}(L_{i})=0$ (5.10)

we notice that zeros of the function $S_{i}^{\prime}(\rho,L_{i})$, which we
denote by $\nu_{i,k}$, are the square roots of the eigenvalues of problem
(5.9), (5.10). Thus, having computed a number of the constants
$\left\\{\sigma_{i,n}(L_{i})\right\\}_{n=0}^{N}$ gives us the possibility to
compute the approximate Dirichlet-Neumann singular numbers $\nu_{i,k}$ by
computing zeros of the function (5.8). Again, arbitrarily many numbers
$\nu_{i,k}$ can be computed, and thus on each edge $e_{i}$ we obtain a
classical inverse Sturm-Liouville problem of recovering the potential
$q_{i}(x)$ from two spectra: the Dirichlet-Dirichlet spectrum of problem
(5.6), (5.7) and Dirichlet-Neumann spectrum of problem (5.9), (5.10).

###  5.2 Solution of the inverse spectral problem on the edge

At this stage we dispose of two sequences of singular numbers
$\left\\{\mu_{i,k}\right\\}_{k=1}^{K_{D}}$ and
$\left\\{\nu_{i,k}\right\\}_{k=1}^{K_{N}}$ which are square roots of the
eigenvalues of problems (5.6), (5.7) and (5.9), (5.10), respectively, as well
as of two sequences of numbers $\left\\{s_{i,n}(L_{i})\right\\}_{n=0}^{N}$ and
$\left\\{\sigma_{i,n}(L_{i})\right\\}_{n=0}^{N}$, which are the values of the
coefficients from (3.2) and (3.4) at the endpoint. The number $K_{N}$ may be
chosen equal to $K_{D}$ or different.

The two-spectra inverse problem, in principle, can be solved by any available
method. However, we chose an approach which makes use of the knowledge of the
coefficients $\left\\{s_{i,n}(L_{i})\right\\}_{n=0}^{N}$ and
$\left\\{\sigma_{i,n}(L_{i})\right\\}_{n=0}^{N}$ and does not require the
Dirichlet-Dirichlet singular numbers
$\left\\{\mu_{i,k}\right\\}_{k=1}^{K_{D}}$ (which were used in the previous
step for computing the parameters $\omega_{i}$).

Let us consider the solution $\psi_{i}(\rho,x)$ of equation (5.9) satisfying
the initial conditions at $L_{i}$:

$\psi_{i}(\rho,L_{i})=1,\quad\psi_{i}^{\prime}(\rho,L_{i})=0.$

Analogously to the solution (3.1) the solution $\psi_{i}(\rho,x)$ admits the
series representation

$\psi_{i}(\rho,x)=\cos\left(\rho\left(L_{i}-x\right)\right)+\sum_{n=0}^{\infty}\left(-1\right)^{n}\tau_{i,n}\left(x\right)\mathbf{j}_{2n}\left(\rho\left(L_{i}-x\right)\right),$
(5.11)

where $\tau_{i,n}\left(x\right)$ are corresponding coefficients, analogous to
$g_{i,n}\left(x\right)$ from (3.1). Similarly to (3.7) the equality

$q_{i}(x)=\frac{\tau_{i,0}^{\prime\prime}(x)}{\tau_{i,0}(x)+1}$ (5.12)

is valid.

Note that for $\rho=\nu_{i,k}$ the solutions $S_{i}(\nu_{i,k},x)$ and
$\psi_{i}(\nu_{i,k},x)$ are linearly dependent because both are eigenfunctions
of problem (5.9), (5.10). Hence there exist such real constants
$\beta_{i,k}\neq 0$, that

$S_{i}(\nu_{i,k},x)=\beta_{i,k}\psi_{i}(\nu_{i,k},x).$ (5.13)

Moreover, these multiplier constants can be easily calculated by recalling
that $\psi_{i}(\nu_{i,k},L_{i})=1$. Thus,

$\displaystyle\beta_{i,k}$ $\displaystyle=S_{i}(\nu_{i,k},L_{i})\approx
S_{i,N}(\nu_{i,k},L_{i})$
$\displaystyle=\frac{\sin\left(\nu_{i,k}L_{i}\right)}{\nu_{i,k}}+\frac{1}{\nu_{i,k}}\sum_{n=0}^{N}(-1)^{n}s_{i,n}(L_{i})\mathbf{j}_{2n+1}(\nu_{i,k}L_{i}).$
(5.14)

Having computed these constants we use equation (5.13) for constructing a
system of linear algebraic equations for the coefficients $s_{i,n}(x)$ and
$\tau_{i,n}\left(x\right)$. Indeed, equation (5.13) can be written in the form

$\displaystyle\frac{1}{\nu_{i,k}}\sum_{n=0}^{\infty}(-1)^{n}s_{i,n}(x)\mathbf{j}_{2n+1}(\nu_{i,k}x)-\beta_{i,k}\sum_{n=0}^{\infty}\left(-1\right)^{n}\tau_{i,n}\left(x\right)\mathbf{j}_{2n}\left(\nu_{i,k}\left(L_{i}-x\right)\right)$
$\displaystyle=-\frac{\sin\left(\nu_{i,k}x\right)}{\nu_{i,k}}+\beta_{i,k}\cos\left(\nu_{i,k}\left(L_{i}-x\right)\right).$

We have as many of such equations as many Dirichlet-Neumann singular numbers
$\nu_{i,k}$ are computed. For computational purposes we choose some natural
number $N_{c}$ \- the number of the coefficients $s_{i,n}(x)$ and
$\tau_{i,n}\left(x\right)$ to be computed. More precisely, we choose a
sufficiently dense set of points $x_{m}\in(0,L_{i})$ and at every $x_{m}$
consider the equations

$\displaystyle\frac{1}{\nu_{i,k}}\sum_{n=0}^{N_{c}}(-1)^{n}s_{i,n}(x_{m})\mathbf{j}_{2n+1}(\nu_{i,k}x_{m})-\beta_{i,k}\sum_{n=0}^{N_{c}}\left(-1\right)^{n}\tau_{i,n}\left(x_{m}\right)\mathbf{j}_{2n}\left(\nu_{i,k}\left(L_{i}-x_{m}\right)\right)$
$\displaystyle=-\frac{\sin\left(\nu_{i,k}x_{m}\right)}{\nu_{i,k}}+\beta_{i,k}\cos\left(\nu_{i,k}\left(L_{i}-x_{m}\right)\right),\quad
k=1,\ldots,K_{N}.$ (5.15)

Solving this system of equations we find $s_{i,0}(x_{m})$ and
$\tau_{i,0}\left(x_{m}\right)$ and consequently $s_{i,0}(x)$ and
$\tau_{i,0}\left(x\right)$ at a dense set of points of the interval
$(0,L_{i})$. Finally, with the aid of (3.8) or (5.12) we compute $q_{i}(x)$.

Schematically the proposed method for solving the inverse spectral problem on
a quantum star graph is presented in the following diagram.

$SD=\left\\{\rho_{k},\alpha_{k}\right\\}_{k=1}^{K}\quad\overset{(1)}{\Longrightarrow}\quad\left\\{s_{i,n}(L_{i}),\omega_{i};\
\sigma_{i,n}(L_{i})\right\\}_{n=0}^{N}\quad\overset{(2)}{\Longrightarrow}\quad\text{two
spectra }\left\\{\mu_{i,k}\right\\}_{k=1}^{K_{D}},\
\left\\{\nu_{i,k}\right\\}_{k=1}^{K_{N}}$
$\left\\{s_{i,n}(L_{i})\right\\}_{n=0}^{N},\,\left\\{\nu_{i,k}\right\\}_{k=1}^{K_{N}}\quad\overset{(3)}{\Longrightarrow}\quad\left\\{\beta_{i,k}\right\\}_{k=1}^{K_{N}}$
$\left\\{\nu_{i,k},\beta_{i,k}\right\\}_{k=1}^{K_{N}}\quad\overset{(4)}{\Longrightarrow}\quad
s_{i,0}(x),\ \tau_{i,0}\left(x\right)\quad\overset{(5)}{\Longrightarrow}\quad
q_{i}(x).$

Note that in the first step $K$ should be greater than $N$.

After step (1) the problem is reduced to separate problems on the edges. The
two spectra problem arising after step (2) can be solved by different existing
methods, nevertheless here we propose a method which uses the fact that the
constants $\left\\{s_{i,n}(L_{i})\right\\}_{n=0}^{N}$ and
$\left\\{\sigma_{i,n}(L_{i})\right\\}_{n=0}^{N}$ are also known.

It is worth mentioning that when dealing with the truncated systems of linear
algebraic equations we do not seek to work with the square systems. In
computations a least-squares solution of an overdetermined system (provided by
Matlab, which we used in this work) gives very satisfactory results.

##  6 Numerical examples

Example 1. Let us consider a star graph of five edges of lengths

$L_{1}=\frac{e}{2},\,L_{2}=1,\,L_{3}=\frac{\pi}{2},\,L_{4}=\frac{\pi}{3},\,L_{5}=\frac{e^{2}}{4}.\,$
(6.1)

The corresponding five components of the potential are defined as follows

$q_{1}(x)=\left|x-1\right|+1,\,q_{2}(x)=e^{-(x-\frac{1}{2})^{2}},\,q_{3}(x)=\sin\left(8x\right)+\frac{2\pi}{3},$
(6.2) $q_{4}(x)=\cos\left(9x^{2}\right)+1,\quad q_{5}(x)=\frac{1}{x+0.1}.$
(6.3)

We computed $100$ eigenvalues and corresponding norming constants as described
in Section 4. In Table 1 some of the computed eigenvalues are presented.

Table 1: Computed eigenvalues of the quantum star graph (6.1)-(6.3)
---
$\lambda_{1}$ | $\lambda_{2}$ | $\lambda_{5}$ | $\lambda_{10}$ | $\lambda_{100}$
$1.5656490615325$ | $2.1509437903100$ | $3.2180647998489$ | $5.493521290269$ | $46.683594634217$

Then to the computed spectral data we applied the method introduced in Section
5 for solving the inverse problem. The number $N$ of the coefficients in (5.5)
and (5.8) was chosen $N=10$. Our numerical experiments showed that even a more
reduced number of the coefficients (say, five-six of them) gives already quite
satisfactory (slightly less accurate) results. For the number $N_{c}$ from
(5.15) was chosen the same value, $N_{c}=10$, though this parameter, of
course, may differ from $N$.

In Fig. 1 we show the recovered potentials on the five edges. The absolute
error of each recovered potential slightly grows at the endpoints of the
interval attaining its maximum value in the second decimal digit (for
$q_{5}(x)$ at the origin), while in the interior points of the interval it
remains two orders of magnitude smaller.

Figure 1: The recovered potential of the quantum star graph (6.1)-(6.3) from
$100$ spectral eigendata with $N=10$.

It is interesting to track how accurately the two spectra were computed on
each edge. For example, Table 2 presents some of the “exact” Dirichlet-
Dirichlet eigenvalues on $e_{2}$ computed with the aid of the Matslise package
(first column), the approximate eigenvalues, computed as described in
Subsection 5.1 by calculating zeros of $S_{2,10}(\rho,L_{2})$ and the absolute
error of each presented eigenvalue. Notice that both the absolute and the
relative errors remain small even for large indices.

Table 2: Dirichlet-Dirichlet eigenvalues of $q_{2}(x)$
---
$n$ | $\lambda_{n}$ | $\widetilde{\lambda}_{n}$ | $\left|\lambda_{n}-\widetilde{\lambda}_{n}\right|$
$1$ | $10.8381543$ | $10.8381555$ | $1.2\cdot 10^{-6}$
$11$ | $1195.1450218$ | $1195.1450282$ | $6.4\cdot 10^{-6}$
$41$ | $16591.72758$ | $16591.72741$ | $0.00016$
$101$ | $100680.75706$ | $100680.75692$ | $0.00014$
$201$ | $398742.80997$ | $398742.80983$ | $0.00013$

Based on the computed Dirichlet-Dirichlet eigenvalues the parameter
$\omega_{i}$ was computed for all $i$, as explained in Subsection 5.1. In the
case of $e_{2}$ the absolute error of the approximation was
$\left|\omega_{2}-\widetilde{\omega}_{2}\right|=7.2\cdot 10^{-5}$.

Next, using the quantum graph spectral eigendata and the computed $\omega_{i}$
the Dirichlet-Neumann eigenvalues for each potential component $q_{i}(x)$ were
computed. Table 3 presents the result of computation for $q_{2}(x)$. One can
observe that while the accuracy is slightly worse than in the case of the
Dirichlet-Dirichlet eigenvalues, it is still quite satisfactory and uniform.

Table 3: Dirichlet-Neumann eigenvalues of $q_{2}(x)$
---
$n$ | $\lambda_{n}$ | $\widetilde{\lambda}_{n}$ | $\left|\lambda_{n}-\widetilde{\lambda}_{n}\right|$
$1$ | $3.3898$ | $3.3920$ | $0.0022$
$11$ | $1089.0464$ | $1089.0487$ | $0.0023$
$41$ | $16189.5411$ | $16189.5418$ | $0.0006$
$101$ | $99686.394414$ | $99686.394415$ | $8.8\cdot 10^{-7}$
$201$ | $396761.48688$ | $396761.48678$ | $0.0001$

In the considered example the worst accuracy was obtained for the component of
the potential $q_{5}(x)$. Table 4 shows the accuracy of the Dirichlet-
Dirichlet eigenvalues computed.

Table 4: Dirichlet-Dirichlet eigenvalues of $q_{5}(x)$
---
$n$ | $\lambda_{n}$ | $\widetilde{\lambda}_{n}$ | $\left|\lambda_{n}-\widetilde{\lambda}_{n}\right|$
$1$ | $3.99363768$ | $3.99363773$ | $4.5\cdot 10^{-8}$
$11$ | $351.545497$ | $351.545501$ | $3.8\cdot 10^{-6}$
$41$ | $4863.543766$ | $4863.543738$ | $2.8\cdot 10^{-5}$
$101$ | $29505.854685672381$ | $29505.8546235738$ | $6.2\cdot 10^{-5}$

Based on this result, the approximation of the parameter $\omega_{5}$ resulted
in the following value of the absolute error
$\left|\omega_{5}-\widetilde{\omega}_{5}\right|=0.0042$. Finally, some
Dirichlet-Neumann eigenvalues for $q_{5}(x)$ are presented in Table 5.

Table 5: Dirichlet-Neumann eigenvalues of $q_{5}(x)$
---
$n$ | $\lambda_{n}$ | $\widetilde{\lambda}_{n}$ | $\left|\lambda_{n}-\widetilde{\lambda}_{n}\right|$
$1$ | $1.5067$ | $1.5026$ | $0.0040$
$11$ | $320.4508$ | $320.4470$ | $0.0037$
$41$ | $4745.682$ | $4745.678$ | $0.0041$
$101$ | $29214.456$ | $29214.452$ | $0.0044$

It is worth noting that the whole computation takes few seconds performed in
Matlab 2017 on a Laptop equipped with a Core i7 Intel processor.

The method copes equally well with inverse spectral problems on star graphs
with a larger number of edges, though to obtain similar accuracy in this case
more spectral data are required.

Example 2. Consider a nine edges quantum star graph with five edges and
components of potential coinciding with those from the previous example and
with the additional edges $L_{6}=1.1,\,L_{7}=1.2,\,L_{8}=1.3,\,L_{9}=1.4$ and
the corresponding components of the potential

$q_{6}(x)=\frac{1}{\left(x+0.1\right)^{2}},\,\,q_{7}(x)=e^{x},\,\,q_{8}(x)=\pi^{2},\,\,q_{9}(x)=J_{0}(9x),$

where $J_{0}(z)$ stands for the Bessel function of the first kind of order
zero. Fig. 2 presents the potential recovered from $200$ spectral data.

Figure 2: The potential of the quantum star graph from Example 2 recovered
from $200$ spectral eigendata with $N=10$.

##  7 Conclusions

A new method for solving the inverse spectral problem on quantum star graphs
is developed. The main role in the proposed approach is played by the
coefficients of the Neumann series of Bessel functions expansion of solutions
of the Sturm-Liouville equation. With their aid the given spectral data lead
to separate two spectra Sturm-Liouville inverse problems on each edge. These
two-spectra problems are solved by a direct method reducing each problem to a
system of linear algebraic equations, and the crucial observation is that the
potential is recovered from the first component of the solution vector.

The method is simple, direct and accurate. Its performance is illustrated by
numerical examples. In subsequent works we plan to extend this method to other
types of inverse spectral problems and to more general graphs.

## Acknowledgements

Research was supported by CONACYT, Mexico via the project 284470 and partially
performed at the Regional mathematical center of the Southern Federal
University with the support of the Ministry of Science and Higher Education of
Russia, agreement 075-02-2022-893. The research of Sergei Avdonin was
supported in part by the National Science Foundation, grant DMS 1909869, and
by Moscow Center for Fundamental and Applied Mathematics.

## References

  * [1] Abramovitz M. and Stegun I. A. (1972), Handbook of mathematical functions, New York: Dover.
  * [2] Arioli M. and Benzi M. (2018), A finite element method for quantum graphs. IMA J. Numer. Anal., 38, no. 3, 1119–1163.
  * [3] Avdonin S., Belinskiy B., and Matthews J. (2011), Inverse problem on the semi-axis: local approach, Tamkang Journal of Mathematics, 42, no. 3, 1–19.
  * [4] Avdonin S. and Bell J. (2015), Determining physical parameters for a neuronal cable model defined on a tree graph, Journal of Inverse Problems and Imaging, 9, no. 3, 645-659.
  * [5] Avdonin S. and Kravchenko V. V. (2022) Method for solving inverse spectral problems on quantum star graphs. Submitted.
  * [6] Avdonin S. and Kurasov P. (2008), Inverse problems for quantum trees, Inverse Problems and Imaging, 2, no. 1, 1–21.
  * [7] Avdonin S., Leugering G., and Mikhaylov V. (2010), On an inverse problem for tree-like networks of elastic strings, Zeit. Angew. Math. Mech., 90, no. 2, 136–150.
  * [8] Belishev M. and Vakulenko A. (2006), Inverse problems on graphs: Recovering the tree of strings by the BC-method, _J. Inv. Ill-Posed Problems_ , 14 , 29-46.
  * [9] Berkolaiko G. and Kuchment P. (2013), Introduction to Quantum Graphs, AMS, Providence, R.I.
  * [10] Brown B. M., Samko V. S., Knowles I. W., Marletta M. (2003), Inverse spectral problem for the Sturm–Liouville equation, _Inverse Probl._ 19 , 235–252.
  * [11] Chadan Kh., Colton D., Päivärinta L., Rundell W. (1997), _An introduction to inverse scattering and inverse spectral problems_. SIAM, Philadelphia.
  * [12] Kravchenko V. V. (2019), On a method for solving the inverse Sturm–Liouville problem, _J. Inverse Ill-posed Probl._ 27, 401–407.
  * [13] Kravchenko V. V. (2020), _Direct and inverse Sturm-Liouville problems: A method of solution_ , Birkhäuser, Cham.
  * [14] Kravchenko V. V., Navarro L. J. and Torba S. M. (2017), Representation of solutions to the one-dimensional Schrödinger equation in terms of Neumann series of Bessel functions, _Appl. Math. Comput._ 314, 173–192.
  * [15] Kravchenko V. V. and Torba S. M. (2015), Analytic approximation of transmutation operators and applications to highly accurate solution of spectral problems,_Journal of Computational and Applied Mathematics_ 275, 1-26.
  * [16] Kravchenko V. V. and Torba S. M. (2021), A direct method for solving inverse Sturm-Liouville problems, _Inverse Probl._ 37, 015015 (32pp).
  * [17] Kurasov P. (2022) Quantum Graphs: Spectral Theory and Inverse Problems, Springer (to appear).
  * [18] Kurasov P. and Nowaczyk M. (2005), Inverse spectral problem for quantum graphs, _J. Phys. A.,_ 38, 4901-4915.
  * [19] Lagnese J.E., Leugering G., and Schmidt E.J.P.G. (1994), _Modelling, Analysis and Control of Multi-Link Flexible Structures_ , Basel: Birkhäuser.
  * [20] Levitan B. M. (1987), _Inverse Sturm-Liouville problems_ , VSP, Zeist.
  * [21] Mugnolo, D. (2014), Semigroup Methods for Evolution Equations on Networks, Understanding Complex Systems, Springer, Cham.
  * [22] Shishkina E. L. and Sitnik S. M. (2020), _Transmutations, singular and fractional differential equations with applications to mathematical physics_ , Elsevier, Amsterdam.
  * [23] Savchuk A. M., Shkalikov A. A. (2005), Inverse problem for Sturm–Liouville operators with distribution potentials: reconstruction from two spectra, _Russ. J. Math. Phys._ 12, 507–514.
  * [24] Yurko V. A. (2005), Inverse Sturm-Lioville operator on graphs, _Inverse Problems_ , 21, 1075-1086.
  * [25] Yurko V. A. (2007), _Introduction to the theory of inverse spectral problems_ , Fizmatlit, Moscow, (in Russian).