# Do Feature Attribution Methods Correctly Attribute Features?

Yilun Zhou1, Serena Booth1, Marco Tulio Ribeiro2, Julie Shah1

###### Abstract

Feature attribution methods are popular in interpretable machine learning.
These methods compute the attribution of each input feature to represent its
importance, but there is no consensus on the definition of “attribution”,
leading to many competing methods with little systematic evaluation,
complicated in particular by the lack of ground truth attribution. To address
this, we propose a dataset modification procedure to induce such ground truth.
Using this procedure, we evaluate three common methods: saliency maps,
rationales, and attentions. We identify several deficiencies and add new
perspectives to the growing body of evidence questioning the correctness and
reliability of these methods applied on datasets in the wild. We further
discuss possible avenues for remedy and recommend new attribution methods to
be tested against ground truth before deployment. The code is available at
https://github.com/YilunZhou/feature-attribution-evaluation.

##  1 Introduction

Consider the task of training a neural network to detect cancers from X-ray
images, wherein the data come from two sources: a general hospital and a
specialized cancer center. As can be expected, images from the cancer center
contain many more cancer cases, but imagine the cancer center adds a small
timestamp watermark to the top-left corner of its images. Since the timestamp
is a strongly correlated with cancer presence, a model may learn to use it for
prediction.

It is important to ensure the deployed model makes predictions based on
genuine medical signals rather than image artifacts like watermarks. If these
artifacts are known a priori, we can evaluate the model on counterfactual
pairs—images with and without them—and compute prediction difference to assess
their impact. However, for almost all datasets, we cannot realistically
anticipate every possible artifact. As such, feature attribution methods like
saliency maps (Simonyan, Vedaldi, and Zisserman 2013) are used to identify
regions which are important for prediction, which humans then inspect for
evidence of any artifacts. This train-and-interpret pipeline has been widely
adopted in data-driven medical diagnosis (Shen et al. 2019; Mostavi et al.
2020; Si et al. 2021) and many other applications.

Figure 1: The intuition behind our feature attribution ground truth: if we
know that for every input, only specific features (orange) are informative to
the label, then across the dataset, a high-performing model has to focus on
them and not get “distracted” by other irrelevant features. Thus, feature
attributions should highlight the union union of these features (purple), and
any attribution outside this area is misleading.

Crucially, this procedure assumes that the attribution methods works correctly
and does not miss influential features. Is this truly the case? Direct
evaluation on natural datasets is impossible as the very spurious correlations
we want attribution methods to find are, by definition, unknown. Many
evaluations try to sidestep this problem with proxy metrics (Samek et al.
2017; Hooker et al. 2019; Bastings, Aziz, and Titov 2019), but they are
limited in various ways, notably by a lack of ground truth, as discussed in
Sec. 2.2.

Instead, we propose evaluating these attribution methods on semi-natural
datasets: natural datasets systematically modified to introduce ground truth
information for attributions. This modification (Fig. 1) ensures that any
classifier with sufficiently high performance has to rely, sometimes solely,
on the manipulations. We then present desiderata, or necessary conditions, for
correct attribution values; for example, features known not to affect the
model’s decision should not receive attribution. The high-level idea is
domain-general, and we instantiate it on image and text data to evaluate
saliency maps, rationale models and attention mechanisms used to explain
common deep learning architectures. We identify several failure modes of these
methods, discuss potential reasons and recommend directions to fix them. Last,
we advocate for testing new attribution methods against ground truth to
validate their attributions before deployment.

##  2 Related Work

###  2.1 Feature Attribution Methods

Feature attribution methods assign attribution scores to input features, the
absolute value of which informally represents their importance to the model
prediction or performance.

Saliency maps explain an image $I$ by producing $S$ of the same size, where
$S_{h,w}$ indicates the contribution of pixel $I_{h,w}$. In various works, the
notion of contribution has been defined as sensitivity (Simonyan, Vedaldi, and
Zisserman 2013), relevance (Bach et al. 2015), local influence (Ribeiro,
Singh, and Guestrin 2016), Shapley values (Lundberg and Lee 2017), or filter
activations (Selvaraju et al. 2017).

Attention mechanisms (Bahdanau, Cho, and Bengio 2015) were originally proposed
to better retain sequential information. Recently they have been used as
attribution values, but their their validity is under debate with different
and inconsistent criteria being proposed (Jain and Wallace 2019; Wiegreffe and
Pinter 2019; Pruthi et al. 2020).

Rationale models (Lei, Barzilay, and Jaakkola 2016; Bastings, Aziz, and Titov
2019; Jain et al. 2020) are inherently interpretable models for text
classification with a two-stage pipeline: a selector extracts a rationale
(i.e. input words), and a classifier makes a prediction based on it. The
selected rationales are often regularized to be succinct and continuous.

###  2.2 Evaluation of Feature Attributions

At their core, feature attribution methods describe mathematical properties of
the model’s decision function. For example, gradient describes sensitivity
with respect to infinitesimal input perturbation, and SHAP describes a notion
of values in a multi-player game with features as players. We associate these
mathematical properties with high-level interpretations such as “feature
importance”, and it is this association that requires justification.

A popular way is to assess alignment with human judgment, but models and
humans can reach the same prediction while using distinct reasoning mechanisms
(e.g. medical signals used by doctors and watermarks used by the model). For
example, SmoothGrad (Smilkov et al. 2017) is proposed as an improvement to the
original Gradient (Simonyan, Vedaldi, and Zisserman 2013) since it gives less
noisy and more legible saliency maps, but it is not clear whether saliency
maps _should_ be smooth. Bastings, Aziz, and Titov (2019) evaluated their
rationale model by assessing its agreement with human rationale annotation,
but a model may achieve high accuracy with subtle but strongly correlated
textual features such as grammatical idiosyncrasy. Covert, Lundberg, and Lee
(2020) compared the feature attribution of a cancer prediction model to
scientific knowledge, yet a well-performing model may rely on other signals.
In general, positive results from alignment evaluation only support
plausibility (Jacovi and Goldberg 2020), not faithfulness.

Another common approach successively removes features with the highest
attribution values and evaluates certain metrics. One metric is prediction
change (e.g. Samek et al. 2017; Arras et al. 2019; Ismail et al. 2020), but it
fails to account for nonlinear interactions: for an OR function of two active
inputs, the evaluation will (incorrectly) deem whichever feature removed first
to be useless as its removal does not affect the prediction. Another metric is
model retraining performance (Hooker et al. 2019), which may fail when
different features lead to the same accuracy—as is often possible (D’Amour et
al. 2020). For example, a model might achieve some accuracy by using only
feature $x_{1}$. If a retrained model using only $x_{2}$ achieves the same
accuracy, the evaluation framework would (falsely) reject the ground truth
attribution of $x_{1}$ due to the same re-training accuracy.

Most similar to our proposal are works that also construct semi-natural
datasets with explicitly defined ground truth explanations (Yang and Kim 2019;
Adebayo et al. 2020). Adebayo et al. (2020) used a perfect background
correlation for a dog-vs-bird dataset, found that the model achieves high
accuracy on background alone, and claimed that the correct attribution should
focus solely on the background. However, we verified that a model trained on
their dataset can achieve high accuracy simultaneously on foreground alone,
background alone, and both combined, invalidating their ground truth claim.
Similarly, Yang and Kim (2019) argue that for background classification, a
label-correlated foreground should receive high attribution value, but a model
could always rely solely on background with perfect label correlation. We
avoid such pitfalls via label reassignment (Sec. 2), so that the model must
use target features for high accuracy. Furthermore, a more subtle failure
mode, in which the model can (rightfully) use the absence of information for a
prediction, is avoided by our joint effective region formulation, discussed in
the Remark at the end of Sec. 4.

Finally, Adebayo et al. (2018) proposed sanity checks for saliency maps by
assessing their change under weight or label randomization. We establish
complementary criteria for explanations by instead focusing on model-agnostic
dataset-side modifications, and identify additional failure cases.

##  3 Desiderata for Attribution Values

What should the attribution values be? Although the precise values may be
axiomatic, certain properties are de facto requirements if we want people to
understand how a model makes a decision, verify that its reasoning process is
sound, and possibly inform options for correction if it is not (c.f. the
opening example in Sec. 1). For example, while LIME and SHAP define
attribution differently, both would produce undeniably bad explanations if
they highlight features completely ignored by the model.

We study two types of features: those of fundamental importance to the model,
denoted by $F_{C}$, and those non-informative to the label, denoted by
$F_{N}$. A first requirement is that explanations should not miss important
features, $F_{C}$. Unfortunately, identifying all such features is not easy.
For example, while the model could potentially use the timestamp on some X-ray
images for cancer prediction, it could instead exclusively rely on genuine
medical features (as done by human doctors), and attributions should only
highlight the timestamp in the former case. This difficulty motivates our
dataset modification procedure detailed in the next section. In brief, we can
modify the dataset such that any model using only medical features could not
achieve a high accuracy (due to introduced label noise), thus establishing the
ground truth usage of the timestamp for any model with high accuracy. We can
then evaluate how well the attribution method identifies the contribution of
the timestamp by the attribution percentage $\mathrm{Attr}\%$ of the timestamp
pixels, with $\mathrm{Attr\%}(F)\doteq\left(\sum_{i\in
F}{|s_{i}|}\right)/\left(\sum_{i=1}^{D}{|s_{i}|}\right)$, where $D$ is the
total number of features and $s_{i}$ is the attribution value assigned to the
$i$-th feature. Since $F_{C}$ contains all features used by the model, we
should expect $\mathrm{Attr\%}(F_{C})\approx 1$.

Conversely, we can introduce non-informative features $F_{N}$ independent from
the label—for example, a white border added to randomly selected images. While
the model prediction could depend on it (e.g. more positive for those with the
border), methods that study features contributing to the performance should
not highlight $F_{N}$. In addition, any reliance on $F_{N}$ is detrimental to
performance, and as performance increases, a good prediction is less
“distracted” by $F_{N}$, which should correspondingly not get highlighted, or
in other words $\mathrm{Attr}\%(F_{N})$ should decrease to 0.

In addition to continuous attributions on all features, another formulation
selects $k$ features, with no distinction among them. This can either be
derived by a top-$k$ post-processing to induce sparse explanations, or
generated directly by some models, e.g. as rationales (Lei, Barzilay, and
Jaakkola 2016). For the first case, a hyper-parameter $k$ needs to be chosen.
A small value risks missing important features while a large value may include
unnecessary features that obfuscate true model reasoning. For the second case,
$k$ is typically chosen automatically by the model, e.g. the rationale
selector. In both cases, ensuring that $F_{C}$ is highlighted (i.e.
$\mathrm{Attr\%}\allowbreak=\allowbreak 1$) is easily “hackable” by just
selecting all features. As such, we instead use two information-retrieval
metrics, precision and recall, defined as $\mathrm{Pr}(F)=|F\cap F_{C}|/|F|$,
and $\mathrm{Re}(F)=|F\cap F_{C}|/|F_{C}|$ for evaluating these attributions,
where $F$ is the $k$ selected features.

##  4 Dataset Modification with Ground Truth

$X$$Y$$\widehat{Y}$$X$$\widehat{Y}$$X$$M$$\widehat{Y}$$\widehat{X}$$\Theta^{(1)},\
p^{(1)}$$\Theta^{(2)},\ p^{(2)}$$\Theta^{(3)},\ p^{(3)}$

Figure 2: The graphical model for our dataset modification.

We now present the dataset modification procedure that lets us quantify the
influence of certain features to the model. We use a running example of adding
a watermark pattern to a watermark-free X-ray cancer dataset, such that the
newly added watermark is guaranteed to affect the model decision.

Let $\mathcal{X}$ and $\mathcal{Y}\doteq\\{1,...,K\\}$ be input and output
space for $K$-class classification. Fig. 2 shows two modification steps: from
an original data instance (1st column), label reassignment reduces the
predictive power of existing signals (2nd column) and input manipulation
introduces new predictive features (3rd and 4th columns).

Label Reassignment  Our goal is to ensure that the model has to rely on
certain introduced features (e.g. a watermark) to achieve a high performance.
However, the model could in theory use any of the existing features (e.g.
medical features) to achieve high accuracy, and thus disregard the new
feature, even if it is perfectly correlated with the label. To guarantee the
model’s usage of new features, we need to weaken the correlation between the
original features and the labels.

We first consider label reassignment for binary classification, which is used
in all experiments. During reassignment, the label is preserved with
probability $r$ and flipped otherwise, so the accuracy without relying on the
manipulation is at most $p^{*}=\max(r,1-r)$. For the special case of $r=0.5$,
no features are informative to the label, and the performance is random in
expectation. After label reassignment, a data point $(x,y)$ becomes
$(x,\widehat{y})$.

More generally, the $K$-class setting is modeled by a reassignment matrix
$R\in\mathbb{R}^{K\times K}$. According to this matrix, the label reassignment
process assigns a new label $\widehat{y}$ based on the original label $y$ with
probability $R_{y,\widehat{y}}$. The expected accuracy $p^{(2)}$ of any
classifier is bounded by $p^{*}=\max_{i,j}R_{i,j}$.

Input Manipulation  Next, we apply manipulations on the input $x$ according to
its reassigned label $\widehat{y}$. We consider a set of $L$ input
manipulations, $\mathcal{M}=\\{m_{1},...,m_{L}\\}$, and a manipulation
function $q:\mathcal{M}\times\mathcal{X}\rightarrow\widehat{\mathcal{X}}$ such
that $q(m_{l},x)=\widehat{x}$ applies the manipulation on the input and
returns the manipulated output $\widehat{x}$. $\mathcal{M}$ can include the
blank manipulation $m_{\varnothing}$ that leaves the input unchanged.

To facilitate feature attribution evaluation, we require the manipulation to
be local, in that $q(m,x)$ affects only a part of the input $x$. Formally, we
define the effective region (ER) of $m_{l}$ on $x$ as the set of input
features modified by $m_{l}$, denoted as
$\phi_{l}(x)\doteq\left\\{i:\left[q(m_{l},x)\right]_{i}\neq x_{i}\right\\},$
where subscript $i$ indexes over individual features (e.g. pixels). The blank
manipulation has empty ER, $\phi_{\varnothing}=\varnothing$.

For $(x,\widehat{y})\sim\mathbb{P}_{X,\widehat{Y}}$, we choose a manipulation
$m_{l}$ from $\mathcal{M}$ according to $\widehat{y}$ and modify the input as
$\widehat{x}=q(m_{l},x)$. The label-dependent choice can be deterministic or
stochastic. We denote the new data distribution as
$\mathbb{P}_{\widehat{X},\widehat{Y}}$. With appropriate choice of
manipulation, $\mathbb{P}_{\widehat{X},\widehat{Y}}$ can satisfy
$\widehat{p}^{\,*}\doteq\sup_{\widehat{x},\widehat{y}}\allowbreak\mathbb{P}_{\widehat{Y}|\widehat{X}}(\widehat{y}|\widehat{x})>p^{*}$.
For example, $\widehat{p}^{\,*}=1$ is achievable when a watermark is applied
exclusively to the positive class.

_Whenever a model trained on $(\widehat{\mathcal{X}},\widehat{\mathcal{Y}})$
achieves expected accuracy $p^{(3)}>p^{*}$, it is guaranteed to rely on the
knowledge of manipulation, which is solely confined within the joint effective
region $\phi_{\cup}(x)\doteq\cup_{l}\,\phi_{l}(x)$._ This gives us a
straightforward, quantitative check for feature attribution methods: they
should recognize the contribution inside $\phi_{\cup}(x)$. For our example,
since only the watermark is applied to one class, $\phi_{\cup}$ corresponds to
the watermarked region.

On finite test sets, a classifier can achieve an accuracy $p>p^{*}$ without
using the manipulation, due to stochasticity in label reassignment. However,
for test set size $N$, the probability of this classifier achieving of $p$ or
higher, when the expected accuracy is bounded by $p^{*}$, is at most
$\sum_{n=\lfloor pN\rfloor}^{N}\mathrm{Binom}(n;N,p^{*})$, which vanishes
quickly with increasing $N$ and $p$.

Remark  It is crucial to consider the joint effective region over all
manipulations for attribution values, since a model could use the absence of
manipulation as a legitimate basis for decision. For example, consider an
image dataset, with each image having a watermark either on the top or bottom
edge correlated with the positive or negative label respectively. A model
could make negative predictions based on the absence of a watermark on the top
edge. In this case, the correct attribution to the top edge is within the
joint ER but not within the bottom watermark ER. Current evaluations (Yang and
Kim 2019; Adebayo et al. 2020) often omit this possibility by using the ER of
only the manipulation applied to the target class rather than the union of all
possible ERs for every class, potentially rejecting correct attributions. A
more detailed explanation of how our proposed work differs from and improves
upon those of Yang and Kim (2019) and Adebayo et al. (2020) is provided in
App. A.

In next three sections, we experimentally compare attribution values of three
types of models—saliency maps, attention mechanisms and rationale models—to
those expected by the desiderata. Through the analysis, we identify their
deficiencies and give recommendations for improvements.

##  5 Evaluating Image Saliency Maps

For these experiments, we simulate a common scenario where a model seemingly
achieves “superhuman” performance on some hard image classification task, only
for us to later find out that it exploits some image artifacts which are
accidentally leaked in during the data collection process. We evaluate the
extent to which several different saliency map attribution methods can
identify such artifacts.

Figure 3: Top: Dataset samples and test set confusion matrix of a ResNet-34
model. Bottom: Examples of five different saliency maps for a correct
prediction (Fish Crow).

Model: We used the ResNet-34 architecture (He et al. 2016) for all
experiments. The parameters are randomly initialized rather than pre-trained
on ImageNet (Deng et al. 2009).

Dataset: We curate our own dataset on bird species identification. First, we
train a ResNet-34 model on CUB-200-2011 (Wah et al. 2011) and identify the top
four most confusing class pairs. Then, we scrape Flickr for 1,200 new images
per class, center-crop all images to $224\times 224$ and mean-variance
normalize using ImageNet statistics. Last, we split the 1,200 images per class
into train/validation/test sets of 1000/100/100 images. Fig. 3 presents sample
images, the confusion matrix for a ResNet-34 model trained on this data, and
example saliency maps for a correct prediction.

Input Manipulations: We define five image manipulations which represent
artifacts that could be accidentally introduced in a dataset collection
process: blurring, brightness change, hue shift, pixel noise, and watermark.
Fig. 4 shows the effect of for three manipulations along with the effective
regions. Other manipulation types and additional details are presented in in
App. B.1.

Figure 4: Three manipulations applied on the same image and their effective
regions (gray).

Saliency Maps: We evaluate 5 saliency map methods: Gradient (Simonyan,
Vedaldi, and Zisserman 2013), SmoothGrad (Smilkov et al. 2017), GradCAM
(Selvaraju et al. 2017), LIME (Ribeiro, Singh, and Guestrin 2016), and SHAP
(Lundberg and Lee 2017), detailed in App. B.2.

Experiments:  We set up binary classifications with pairs of easily confused
species (e.g. common tern and Forester’s tern) to simulate a hard task which
is made easier through the presence of artifacts. Sec. 5.4 also uses pairs of
visually distinct species (e.g. common tern and fish crow).

Metric: We study the attribution percentage assigned to the joint effective
region $\mathrm{Attr}\%(\phi_{\cup})$. We calculate $\mathrm{\%Attr}$ for
images in the test set, and report the average separately for images of the
two classes.

###  5.1 Attr% by Attributions and Manipulations

Question: How well do saliency maps give attribution to the ground truth for
(near-)perfect models?

Setup: We train 100 models, each on a random pair of similar species and a
random manipulation type. We reassign labels with $r=0.5$ (i.e. totally
randomly), and apply the manipulation to images of the positive post-
reassignment class, leaving the negative class images unchanged.

Expectation:  With $r=0.5$, _only_ the manipulation is correlated with the
label. A near-perfect performance thus indicates that the model relies almost
exclusively on features inside $\phi_{\cup}$. Thus, we should expect
$\mathrm{Attr}\%(F_{\phi_{\cup}})\approx 1.0$, regardless of the size of
$\phi_{\cup}$.

Results:  70% of all runs achieve test accuracy of over 95%111Note that since
the model is not 100% accurate, it could be “distracted” by features outside
of $F_{C}$. However, such distraction is small, accounting for at most 5% of
errors, and it is much more important for users to understand that the over
95% accuracy comes solely from $F_{C}$, and thus requiring
$\mathrm{Attr\%}\approx 1$ is reasonable. . We compute
$\mathrm{Attr}\%(F_{\phi_{\cup}})$ for these models. Since $\mathrm{\%Attr}$
naturally depends on the size of $\phi_{\cup}$ (e.g. $\phi_{\cup}$ of the
entire image implies $\mathrm{Attr}\%=1$), we plot them against
$\mathrm{\%ER}$, defined as the size of $\phi_{\cup}$ as a fraction of image
size. Fig. 5 shows these two values for some methods and manipulations
(complete results in App. B.3).

Figure 5: $\mathrm{\%Attr}$ ($y$-axis) vs. $\mathrm{\%ER}$ ($x$-axis),
complete results in Fig. 15 of App. B.3. Blue circles and orange crosses are
for images with and without the manipulation. Green horizontal line indicates
the saliency map with $\mathrm{Attr\%}=1$ and red diagonal line indicates a
random saliency map.

The models successfully learn all manipulation types, as demonstrated by the
high test accuracy. However, none of the methods consistently scores
$\mathrm{\%Attr}$ $\approx 1$. Further, not all manipulations are equally well
detected by all saliency maps. While SHAP performs the best ($\mathrm{\%Attr}$
$=69\%$ at $\mathrm{\%ER}$ $=40\%$ on average), it is still hard to trust “in
the wild” since its efficacy strongly depends on manipulation type. The
_presence_ of a watermark is often better detected than its _absence_ , likely
because the model implicitly localizes objects (i.e. the watermark) (Bau et
al. 2017) and predicts a default negative class if it fails to do so. It is
also easier for perturbation-based methods such as LIME to “hide” it when
present than to “construct” it when absent. Thus, saliency maps may mislead
people about the true reason for a negative prediction, and better methods to
convey the absence of signals are needed.

###  5.2 Attribution vs. Test Accuracy

Question:  How does $\mathrm{\%Attr}$ change as the model’s test accuracy
increases during training?

Setup:  We use the the same setup as Sec. 5.1.

Expectation:  As the test accuracy increases, the model must also increasingly
rely on knowledge of manipulation. As a result, we should expect
$\mathrm{Attr}\%(F_{\phi_{\cup}})$ to increase.

Results:  For the training run of each model, we compute
$\mathrm{Attr}\%(F_{\phi_{\cup}})$ for models during intermediate epochs with
various test accuracy scores. Fig. 6 plots the lines representing the progress
of $\mathrm{\%Attr}$ vs. test accuracy (complete results in App. B.4). SHAP
with watermark shows the most consistent and expected increase in
$\mathrm{\%Attr}$ with test accuracy. For other saliency maps and feature
types, the trend is very mild or noisy, suggesting that the attribution method
fails to recognize model’s increasing reliance on the manipulation in making
increasingly accurate predictions.

Figure 6: $\mathrm{\%Attr}$ vs. test accuracy, more in App. B.4.

###  5.3 Attribution vs. Manipulation Visibility

Question: How well can saliency maps recognize manipulations of different
visibility levels?

Setup:  We conduct 100 runs, with 20 per manipulation. We further group the 20
runs into 4 groups, with 5 runs in a group using the same manipulation type
and effective region but varying degrees of visibility, detailed in App. B.5.
For example, the visibility for a watermark corresponds to its font size. As
before, the labels are reassigned with $r=0.5$ and manipulations applied to
the positive class only.

Expectation:  A good saliency map should not be affected by manipulation
visibility, as long as the model is objectively using it. However, different
saliency maps may be better suited to detect more or less visible
manipulations. For example, a less visible manipulation may be ignored by the
segmentation algorithm used by LIME, while inducing sharper gradients in the
decision space.

Figure 7: $\mathrm{\%Attr}$ vs. feature visibility, more in App. B.5.

Results:  Fig. 7 (left) plots each group of five runs as a line, with
visibility level on the $x$-axis and $\mathrm{\%Attr}$ on the $y$-axis
(complete results in App. B.5). Except for SHAP on watermark, other methods do
not show consistent trend of $\mathrm{\%Attr}$ increasing with visibility.
While SHAP is more effective on more visible manipulations, we rely most on
interpretability methods to uncover precisely the less visible manipulations
or artifacts. Unfortunately, none of the methods could satisfy this
requirement.

###  5.4 Attribution vs. Original Feature Correlation

Question: How does the attribution on the manipulation change if the
reassigned labels are correlated with the original labels (and thus original
input features) to higher or lower degrees (i.e. $r\in[0.5,1.0]$)?

Setup:  For each manipulation, we vary the label reassignment parameter
$r\in\allowbreak\\{0.5,\allowbreak 0.6,\allowbreak 0.7,\allowbreak
0.8,\allowbreak 0.9,\allowbreak 1.0\\}$. For each $r$, we train four models on
four class pairs: two of similar species (e.g. class 4 vs. 5 in Fig. 3) and
two of distinct ones (e.g. class 5 vs. 6), for a total of $5\times 6\times
4=120$ runs.

Expectation:  For $r>0.5$, there is no standard definition of the attribution
value on the original image features and the manipulations, as any decreasing
trend of $\mathrm{\%Attr}$ with increasing $r$ is reasonable. However, the
Shapley value (Roth 1988) is a commonly used axiomatic definition for feature
attributions. We denote the set of features inside the effective region as
$F_{M}$, for manipulated features, and that outside as $F_{O}$, for original
features. Their Shapley values on performance $v(F_{M})$ and $v(F_{O})$ are
defined as

$\displaystyle\textstyle v(F_{M})$
$\displaystyle=\textstyle\frac{1}{2}\left[a(F_{M}){-}a(\varnothing){+}a(F_{M}\cup
F_{O}){-}a(F_{O})\right],$ (1) $\displaystyle\textstyle v(F_{O})$
$\displaystyle=\textstyle\frac{1}{2}\left[a(F_{O}){-}a(\varnothing){+}a(F_{M}\cup
F_{O}){-}a(F_{M})\right],$ (2)

where $a(F_{M}),a(F_{O}),a(\varnothing)$, and $a(F_{M}\cup F_{O})$ refers to
the classifier’s expected accuracy when only $F_{M}$, only $F_{O}$, neither,
and both are available, respectively. For a classifier with accuracy $p$, we
have $a(\varnothing)=0.5$, $a(F_{M})=a(F_{M}\cup F_{O})=p$, and $a(F_{O})\leq
m$. The formal definition of $a(\cdot)$ and its calculation are in App. B.6.
We normalize the Shapley values to $\overline{v}(F_{M})$ and
$\overline{v}(F_{O})$ by their sum $\overline{v}(F_{M})+\overline{v}(F_{O})$.

It is easy to see that

$\displaystyle\overline{v}(F_{M})$ $\displaystyle\geq(2p-r-0.5)/(2p-1),$ (3)
$\displaystyle\overline{v}(F_{O})$ $\displaystyle\leq(r-0.5)/(2p-1).$ (4)

For (near-)perfect classifier with $p\approx 1$, we have
$\overline{v}(F_{M})\geq 1.5-r$, and $\overline{v}(F_{O})\leq r-0.5$. In
addition, $a(F_{O})$ should be close to $r$ for the distinct pair as the model
can better utilize the more distinct original image features, resulting in
lower attribution $\overline{v}(F_{M})$ on manipulated features.

Figure 8: $\mathrm{\%Attr}$ vs. $r$, more in App. B.6. Solid/dashed lines
represent similar/distinct species pairs. Green shades represent attribution
range per Shapley axioms: $\mathrm{\%Attr}$ $\geq 1.5-r$.

Results:  All models achieve test accuracy of over 95%. Fig. 8 (right) plots
$\mathrm{\%Attr}$ vs. $r$ (complete results in App. B.6). Solid lines
represent runs with a similar species pair, and dashed lines represent runs
with a distinct species pair. The green shaded area represents the area of
$\overline{v}(F_{M})\geq 1.5-r$, the Shapley value range at $p=1$. In other
words, values within the green shade are consistent with the Shapley axioms,
and those outside are not. Intuitively, for $r$ close to 0.5, the correlation
between $F_{O}$ and the label is very weak, and the (near-)perfect model has
to use $F_{M}$ for high performance, thus $\mathrm{\%Attr}$ close to 1. As $r$
increases, the model can choose to rely more heavily on the more-correlating
$F_{O}$ as well, resulting in larger allowable ranges of $\mathrm{\%Attr}$.

For watermark manipulation, SHAP shows clear decrease in attribution value as
$r$ increases, while gradient also tracks the predicted range, but only for
the positive class with the manipulation. This trend is not seen in other
feature types, even for SHAP which approximates the Shapley values. There does
not seem to be a clear difference in attribution values for similar vs.
distinct species pairs either. Considering that the set of Shapley axioms is
commonly accepted as reasonable, it is concerning to see that many saliency
maps are inconsistent with it, and important to develop a better understanding
about the underlying axiomatic assumptions (if any) made by each of them.

###  5.5 Discussion

Arguably one of the most important application of model explanation is to
detect any usage of spurious correlations, but our results cast doubt on this
capability from various aspects. We recommend that, before analyzing the
actual model, developers should first train models that are guaranteed to use
certain known features, and “dry run” the planned interpretability methods on
them to make sure that these features are indeed highlighted.

Figure 9: The process to build CN dataset for the experiment in Sec. 7.2.
First, a review is split into two halves at the midpoint, shown in bold and
italics. Then a label is randomly sampled and assigned to the review.
Depending on the label, the articles in the first half are changed to “a” or
“the”. They are called correlating articles. Then an article word is randomly
chosen for the second half, and all articles in the second half are changed to
that word. They are called non-correlating articles. For NC dataset, the roles
of two halves are switched.

##  6 Evaluating Text Attentions

It is known that certain non-semantic features can heavily influence model
prediction, such as the email headers (Ribeiro, Singh, and Guestrin 2016).
Plausibly, attention scores should highlight such features, and we rigorously
test this with our dataset modification in this section.

Model:  The attention architecture follows the one used by Wiegreffe and
Pinter (2019) closely. First, a sentence of $L$ words $(w_{1},...,w_{L})$ is
converted to a list of 200-dimensional embeddings
$(\mathbf{v}_{1},...,\mathbf{v}_{L})$. We use the same embedding data as Lei,
Barzilay, and Jaakkola (2016) and Bastings, Aziz, and Titov (2019). Then, a
Bi-LSTM network builds contextual representations for these words
$\mathbf{h}_{1},...\mathbf{h}_{L}$, where $\mathbf{h}_{i}\in\mathbb{R}^{400}$
is the concatenation of the forward and the backward hidden states, each of
200 dimensions. Finally, the attention mechanism computes the sentence
representation as

$\displaystyle\mathbf{k}_{i}$
$\displaystyle=\mathrm{tanh}(\mathrm{Linear}(\mathbf{h}_{i}))\in\mathbb{R}^{200},$
(5) $\displaystyle b_{i}$ $\displaystyle=\mathbf{q}\cdot\mathbf{k}_{i}$ (6)
$\displaystyle a_{1},...,a_{L}$
$\displaystyle=\mathrm{softmax}(b_{1},...,b_{L}),$ (7)
$\displaystyle\mathbf{h}$ $\displaystyle=\sum_{i=1}^{L}a_{i}\mathbf{h}_{i},$
(8)

where $\mathrm{Linear}()$ represents a linear layer with learned parameters,
$\mathbf{q}\in\mathbb{R}^{200}$ is a learned query vector applied to every
sentence, and $a_{1},...,a_{L}$ are the attention weights for
$w_{1},...,w_{L}$. Finally, a linear layer computes the 2-dimensional logit
vector for model prediction.

Dataset: We modify the BeerAdvocate dataset (McAuley, Leskovec, and Jurafsky
2012) and further select 12,000 reviews split into train, validation, and test
sets of sizes 10,000, 1,000 and 1,000 (shuffled differently for each
experiment).

Metric: The introduced manipulation changes specific words according to the
reassigned label. The metric is $\mathrm{\%Attr}$ defined on the target words
(i.e. effective region).

###  6.1 Highly Obvious Correlating Features

Question:  How well can attention scores focus on highly obvious
manipulations?

Setup:  From our filtered dataset, we first randomly assign binary labels. For
the positive reviews, we change all the article words (a / an / the) to “the”,
and for the negative reviews, we change these to “a”. Thus, only these
articles are correlated with the labels and constitute the effective region.

Expectation:  Attention of (near-)perfect models should have $\mathrm{\%Attr}$
$\approx 1$ to be valid attributions.

Results:  The model achieves over 97% accuracy. Across the test set,
$\mathrm{\%Attr}$ on article words is 8.6%. Considering that articles are 7.9%
of all words, this is better than random, albeit barely. Fig. 10 visualizes
the attention distribution for two reviews, with additional results in Fig. 19
of App. C.1. Each bars represent weights of words in the review. Green and
orange bars represent non-articles and articles respectively. As we can see,
the attention on article words either does not stand out from the rest, or at
most only locally, relative to their neighbors. Generally, there is no strong
correlation between high attention values and important words.

Figure 10: Attention scores for words in two reviews, with more in App. C.1.
Orange and green bars represent articles and non-articles, respectively.

###  6.2 Misleading Non-Correlating Features

Question: When some features are known to not correlate with the label but are
very similar to correlating ones, do attention scores also focus on these non-
correlating ones?

Setup: Again from our filtered dataset, we apply two similar manipulations,
with only one of them is correlated with the (reassigned) label. Fig. 9
details the construction of two datasets, CN and NC.

Expectation:  Same as above. In particular, non-correlating articles should
not be attended to.

Results:  The models on both datasets achieve over 97% accuracy. Fig. 11
presents attention visualization, with more in Fig. 20 of App. C.2. The two
models show very different behaviors. The CN model exclusively focuses
attention on correlating articles, while the NC model behaves similarly to the
previous experiment.

Figure 11: Word attentions for one review in CN (top) and NC (bottom) dataset,
with more in App. C.2. Orange, blue, and green bars represent correlating
articles, non-correlating articles, and other words, respectively.

Observing the large variation of behaviors, we further trained the three
models ten more times to see if any consistent attention pattern exists. All
models achieve over 97% accuracy. Fig. 1 (left) presents the mean and standard
deviation statistics for the 11 runs. The clean attention pattern by the CN
model does not persist, and the model sometimes assigns higher than random
weights on non-correlating articles, especially for the $NC$ dataset. These
results further suggests that attention weights cannot be readily and reliably
interpreted as attributions without further validation.

Dataset | Corr. Articles | Non-Corr. Articles | Other Words
---|---|---|---
Article | $10.3\%\pm\phantom{2}2.4\%\,\,|\,\,7.9\%$ | NA | $89.7\%\pm\phantom{2}2.4\%\,\,|\,\,92.1\%$
CN | $15.9\%\pm 25.7\%\,\,|\,\,4.1\%$ | $\phantom{1}5.9\%\pm 4.0\%\,\,|\,\,3.8\%$ | $78.2\%\pm 24.7\%\,\,|\,\,92.1\%$
NC | $12.0\%\pm\phantom{2}8.4\%\,\,|\,\,3.8\%$ | $12.6\%\pm 9.3\%\,\,|\,\,4.1\%$ | $75.4\%\pm 16.7\%\,\,|\,\,92.1\%$
Table 1: Attention attribution statistics across 11 training runs (format:
$\mathrm{mean(\%Attr)}\pm\mathrm{stdev(\%Attr)}\mid\mathrm{word\,\,\allowbreak
frequency}$). The “Article” dataset is the one used in Sec. 6.1.

###  6.3 Discussion

Attention is undoubtedly useful as a building block in neural networks, but
their interpretation as attribution is disputed. Due to the lack of ground
truth information on word-prediction correlation, past studies proposed
various, and sometimes conflicting, criteria for judging the validity of
attribution interpretation (Jain and Wallace 2019; Wiegreffe and Pinter 2019;
Pruthi et al. 2020). However, the fundamental correctness of such proxy
metrics is unclear. In our studies, we find that attentions can hardly be
interpreted as attribution for model understanding and debugging purposes: for
most training runs, the attention weights on correlating features at best
stand out only locally, easily overwhelmed by larger global variations,
setting the debate at least on the modified dataset. For natural datasets, we
would unavoidably need to rely on proxy metrics, but we recommend future
proposals of the metrics to be first calibrated with ground truth in a
controlled setting.

##  7 Evaluating Text Rationales

In this section, we evaluate rationale models with the same two experiments
above (and omit the Question and Setup descriptions). We consider two
variants: a reinforcement learning (RL) model (Lei, Barzilay, and Jaakkola
2016) and a continuous relaxation (CR) model (Bastings, Aziz, and Titov 2019).
In the original forms, both models regularize the rationale length and
continuity. In our experiments, rather than regularizing the length, we train
the models to produce rationales that match a target selection rate
$\mathrm{\%Sel}$. For a mini-batch of $B$ examples, we use
$\lambda\cdot\left|\sum_{i=1}^{B}\mathrm{len}({\mathrm{rationale}_{i})}/\sum_{i=1}^{B}\mathrm{len}({\mathrm{review}_{i})}-\mathrm{Sel}\%\right|$,
where $\lambda>0$ is the regularization strength. Incidentally, we found that
the training is much more stable with this regularization, especially for the
RL model. We also removed the discontinuity penalty, because ground truth
rationales in our experiments are not continuous. We use precision and recall
metrics as defined in Sec. 3.

###  7.1 Highly Obvious Manipulations

Expectation:  A necessary condition for a non-misleading rationale is that it
should include at least one article word, regardless of selection rate.
However, a desirable property of rationale is comprehensiveness (Yu et al.
2019): selecting as many article words as possible. Thus, a good rationale
model should have high precision when selection rate is low and high recall
when selection rate is high.

Results:  We train models with $\mathrm{\%Sel}$ $\in\\{0.07,\allowbreak
0.09,\allowbreak 0.11,\allowbreak 0.13,0.15\\}$, all with over 97% accuracy.
We evaluate precision and recall of the trained models and plot them in Fig.
12 (top) according to the actual rationale selection rate, $\mathrm{\%Sel}$,
on the test set. Blue and orange markers are for the RL and CR models
respectively. The two green lines show two optimality notions: the solid line
enforces aggregate $\mathrm{\%Sel}$ for the test set, and the dashed line
enforces $\mathrm{\%Sel}$ per review.

Except for the CR model at the lowest $\mathrm{\%Sel}$, all others achieve
near-perfect rationale selection on both the precision and and the recall
metrics. In particular, they are nearly dataset-wide optimal, due to
$\mathrm{\%Sel}$ regularization done at the mini-batch level. The “faulty” CR
model tends to select the first few words consistently, as shown in Fig. 12
(bottom) and App. D.1, but still selects some article words.

enjoyed @ la cave the bulles ; simon & the head brewer of brasserie de vines
hosted the tasting on 11/5 . medium body , frothy mouth-feel , nice
carbonation . nice fruity notes upfront , green apples and citrus , with the
hint of sourness . finishes with the fresh piney hop presence and the mild
bitterness . overall ; great diversity in flavors , very fresh tasting .

Figure 12: Top: Precision and recall for two rationale models in Sec. 7.1.
Bottom: A rationale pattern by the “faulty” CR model, selected non-articles in
orange bold italics, selected articles in green bold, and missed articles in
red italics, more in App. D.1.

###  7.2 Misleading Non-Correlating Features

Expectation: Similar to the previous experiment, at least one correlating
article word needs to be selected. However, selection of non-correlating
articles is arguably more misleading than selection of other non-article
words, because it suggests that these non-correlating articles also influence
the prediction, even though the classifier simply ignores them.

Results:  We train models with $\mathrm{\%Sel}$ $\in\\{0.03,\allowbreak
0.05,\allowbreak 0.07,\allowbreak 0.09\\}$, all with over 97% accuracy. Fig.
13 (top) plots the precision of correlating articles for the two datasets, as
well as the dataset-wide optimal value. We found the rationales consist of
almost exclusively article words. However, especially for the RL model, some
correlating articles are missed but non-correlating ones are selected,
resulting in markedly less than optimal precision. Fig. 13 (bottom) shows one
example for the RL model and additional ones are in App. D.2.

enjoyed @ la cave the bulles ; simon & the head brewer of brasserie de vines
hosted the tasting on 11/5 . medium body , frothy mouth-feel , nice
carbonation . nice fruity notes upfront , green apples and citrus , with a
hint of sourness . finishes with a fresh piney hop presence and a mild
bitterness . overall ; great diversity in flavors , very fresh tasting .

Figure 13: Top: Precision at different $\mathrm{\%Sel}$ for models in Sec.
7.2. RL model is in blue and CR in orange. The solid and dashed green lines
show optimal metric values when $\mathrm{\%Sel}$ is enforced at dataset- and
sentence-level. Bottom: A rationale selection on the NC dataset, correlating
articles in green bold and non-correlating articles in red italics, more in
App. D.2.

###  7.3 Discussion

The structure of rationale models guarantees that causal relationship between
the rationale features and the model prediction, but this does not necessarily
imply its usefulness to model understanding. Specifically, it could highlight
$F_{C}$ only barely, while including lots of non-correlating $F_{N}$ (and, in
particular, misleading words such as the non-correlating articles)222There are
additional concerns on the unfaithfulness of rationales as Trojan explanations
(Jacovi and Goldberg 2021; Zheng et al. 2021), but they were not identified in
our experiments.. Indeed, our results show that rationale methods are prone to
selecting misleading non-correlating features, which obfuscates the model’s
reasoning process by giving more but unnecessary information to the human. The
problem is more severe with RL training, possibly due to the known difficulty
with REINFORCE (Williams 1992). Post-processing methods could be developed to
further prune rationales to mitigate this problem.

##  8 Conclusion and Future Work

As interpretability methods, especially feature attribution ones, are
increasingly deployed for quality assurance of high-stakes systems, it is
crucial to ensure these methods work correctly. Current evaluations fall
short—primarily due to a lack of clearly defined ground truth. Rather than
evaluating explanations for models trained on natural datasets, we propose
“unit tests” to assess whether feature attribution methods are able to uncover
ground truth model reasoning on carefully-modified, semi-natural datasets.
Surprisingly, none of our evaluated methods across vision and text domains
achieve totally satisfactory performance, and we point out various future
directions in Sec. 5.5, 6.3 and 7.3 to improve attribution methods.

Our dataset modification procedure closely parallels the setup for identifying
and debugging model reliance on spurious correlations, which have been known
to frequently affect model decisions (e.g. Ribeiro, Singh, and Guestrin 2016;
Kaushik, Hovy, and Lipton 2019; Geirhos et al. 2020; Jabbour et al. 2020).
Hence, the mostly negative conclusions cast doubt on this use case of
interpretability methods.

An extension of the proposed evaluation procedure is to move beyond “artifact”
features, which result from the manual definition of the manipulation
function. Given the recent advances on generative modeling such as image
inpainting (Pathak et al. 2016) and masked language prediction (Devlin et al.
2019), more realistic features could be generated, perhaps also conditioned on
or guided by semantic concepts. This would make the modified dataset much more
realistic looking, and thus better simulate another intended use case of
interpretability: assisting scientific discovery, in which high-performing
models teach humans about features of previous unknown importance.

## Acknowledgement

An earlier version of this paper was presented at the 2021 NeurIPS Workshop on
Explainable AI Approaches for Debugging and Diagnosis. This research is
supported by the National Science Foundation (NSF) under the grant
IIS-1830282. We thank the reviewers for their reviews.

## References

  * Adebayo et al. (2018) Adebayo, J.; Gilmer, J.; Muelly, M.; Goodfellow, I.; Hardt, M.; and Kim, B. 2018\.  Sanity Checks for Saliency Maps.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 31, 9505–9515.
  * Adebayo et al. (2020) Adebayo, J.; Muelly, M.; Liccardi, I.; and Kim, B. 2020.  Debugging Tests for Model Explanations.  In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Arras et al. (2019) Arras, L.; Osman, A.; Müller, K.-R.; and Samek, W. 2019.  Evaluating Recurrent Neural Network Explanations.  In _ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP_ , 113–126.
  * Bach et al. (2015) Bach, S.; Binder, A.; Montavon, G.; Klauschen, F.; Müller, K.; and Samek, W. 2015.  On Pixel-Wise Explanations for Non-Linear Classifier Decisions by Layer-Wise Relevance Propagation.  _PLOS One_ , 10(7).
  * Bahdanau, Cho, and Bengio (2015) Bahdanau, D.; Cho, K. H.; and Bengio, Y. 2015.  Neural Machine Translation by Jointly Learning to Align and Translate.  In _International Conference on Learning Representations (ICLR)_.
  * Bastings, Aziz, and Titov (2019) Bastings, J.; Aziz, W.; and Titov, I. 2019.  Interpretable Neural Predictions with Differentiable Binary Variables.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_ , 2963–2977.
  * Bau et al. (2017) Bau, D.; Zhou, B.; Khosla, A.; Oliva, A.; and Torralba, A. 2017.  Network dissection: Quantifying interpretability of deep visual representations.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 6541–6549. IEEE.
  * Covert, Lundberg, and Lee (2020) Covert, I.; Lundberg, S. M.; and Lee, S.-I. 2020.  Understanding Global Feature Contributions With Additive Importance Measures.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 33.
  * D’Amour et al. (2020) D’Amour, A.; Heller, K.; Moldovan, D.; Adlam, B.; Alipanahi, B.; Beutel, A.; Chen, C.; Deaton, J.; Eisenstein, J.; Hoffman, M. D.; et al. 2020.  Underspecification Presents Challenges for Credibility in Modern Machine Learning.  _arXiv preprint arXiv:2011.03395_.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  ImageNet: A Large-Scale Hierarchical Image Database.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 248–255. IEEE.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , 4171–4186.
  * Geirhos et al. (2020) Geirhos, R.; Jacobsen, J.-H.; Michaelis, C.; Zemel, R.; Brendel, W.; Bethge, M.; and Wichmann, F. A. 2020.  Shortcut Learning in Deep Neural Networks.  _Nature Machine Intelligence_ , 2(11): 665–673.
  * Geirhos et al. (2018) Geirhos, R.; Rubisch, P.; Michaelis, C.; Bethge, M.; Wichmann, F. A.; and Brendel, W. 2018.  ImageNet-Trained CNNs Are Biased Towards Texture; Increasing Shape Bias Improves Accuracy and Robustness.  In _International Conference on Learning Representations (ICLR)_.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 770–778. IEEE.
  * Hooker et al. (2019) Hooker, S.; Erhan, D.; Kindermans, P.-J.; and Kim, B. 2019.  A Benchmark for Interpretability Methods in Deep Neural Networks.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , volume 32, 9737–9748.
  * Ismail et al. (2020) Ismail, A. A.; Gunady, M.; Bravo, H. C.; and Feizi, S. 2020.  Benchmarking Deep Learning Interpretability in Time Series Predictions.  In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Jabbour et al. (2020) Jabbour, S.; Fouhey, D.; Kazerooni, E.; Sjoding, M. W.; and Wiens, J. 2020.  Deep Learning Applied to Chest X-Rays: Exploiting and Preventing Shortcuts.  In _Machine Learning for Healthcare Conference (MLHC)_ , 750–782. PMLR.
  * Jacovi and Goldberg (2020) Jacovi, A.; and Goldberg, Y. 2020.  Towards Faithfully Interpretable NLP Systems: How Should We Define and Evaluate Faithfulness?  In _Annual Meeting of the Association for Computational Linguistics (ACL)_ , 4198–4205.
  * Jacovi and Goldberg (2021) Jacovi, A.; and Goldberg, Y. 2021.  Aligning Faithful Interpretations with Their Social Attribution.  _Transactions of the Association for Computational Linguistics (TACL)_ , 9: 294–310.
  * Jain and Wallace (2019) Jain, S.; and Wallace, B. C. 2019.  Attention is not Explanation.  In _Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , 3543–3556.
  * Jain et al. (2020) Jain, S.; Wiegreffe, S.; Pinter, Y.; and Wallace, B. C. 2020.  Learning to Faithfully Rationalize by Construction.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_ , 4459–4473.
  * Kaushik, Hovy, and Lipton (2019) Kaushik, D.; Hovy, E.; and Lipton, Z. 2019.  Learning The Difference That Makes A Difference With Counterfactually-Augmented Data.  In _International Conference on Learning Representations (ICLR)_.
  * Lei, Barzilay, and Jaakkola (2016) Lei, T.; Barzilay, R.; and Jaakkola, T. 2016.  Rationalizing Neural Predictions.  In _Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 107–117.
  * Lundberg and Lee (2017) Lundberg, S. M.; and Lee, S.-I. 2017.  A Unified Approach to Interpreting Model Predictions.  In _Advances in Neural Information Processing Systems (NIPS)_ , 4768–4777.
  * McAuley, Leskovec, and Jurafsky (2012) McAuley, J.; Leskovec, J.; and Jurafsky, D. 2012.  Learning Attitudes and Attributes from Multi-Aspect Reviews.  In _IEEE International Conference on Data Mining (ICDM)_ , 1020–1025. IEEE.
  * Mostavi et al. (2020) Mostavi, M.; Chiu, Y.-C.; Huang, Y.; and Chen, Y. 2020.  Convolutional Neural Network Models for Cancer Type Prediction Based on Gene Expression.  _BMC Medical Genomics_ , 13(5): 1–13.
  * Pathak et al. (2016) Pathak, D.; Krahenbuhl, P.; Donahue, J.; Darrell, T.; and Efros, A. A. 2016.  Context Encoders: Feature Learning by Inpainting.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2536–2544.
  * Pruthi et al. (2020) Pruthi, D.; Gupta, M.; Dhingra, B.; Neubig, G.; and Lipton, Z. C. 2020.  Learning to Deceive with Attention-Based Explanations.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_ , 4782–4793.
  * Ribeiro, Singh, and Guestrin (2016) Ribeiro, M. T.; Singh, S.; and Guestrin, C. 2016.  “Why Should I Trust You?” Explaining the Predictions of Any Classifier.  In _ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , 1135–1144.
  * Roth (1988) Roth, A. E. 1988.  _The Shapley Value: Essays in Honor of Lloyd S. Shapley_.  Cambridge University Press.
  * Samek et al. (2017) Samek, W.; Binder, A.; Montavon, G.; Lapuschkin, S.; and Müller, K. 2017\.  Evaluating the Visualization of What a Deep Neural Network Has Learned.  _IEEE Transactions on Neural Networks and Learning Systems (TNNLS)_ , 28(11): 2660–2673.
  * Selvaraju et al. (2017) Selvaraju, R. R.; Cogswell, M.; Das, A.; Vedantam, R.; Parikh, D.; and Batra, D. 2017.  Grad-CAM: Visual Explanations from Deep Networks via Gradient-Based Localization.  In _IEEE International Conference on Computer Vision (ICCV)_ , 618–626. IEEE.
  * Shen et al. (2019) Shen, L.; Margolies, L. R.; Rothstein, J. H.; Fluder, E.; McBride, R.; and Sieh, W. 2019.  Deep Learning to Improve Breast Cancer Detection on Screening Mammography.  _Scientific Reports_ , 9(1): 1–12.
  * Si et al. (2021) Si, K.; Xue, Y.; Yu, X.; Zhu, X.; Li, Q.; Gong, W.; Liang, T.; and Duan, S. 2021\.  Fully End-to-End Deep-Learning-Based Diagnosis of Pancreatic Tumors.  _Theranostics_ , 11(4): 1982.
  * Simonyan, Vedaldi, and Zisserman (2013) Simonyan, K.; Vedaldi, A.; and Zisserman, A. 2013.  Deep inside Convolutional Networks: Visualising Image Classification Models and Saliency Maps.  _arXiv preprint arXiv:1312.6034_.
  * Smilkov et al. (2017) Smilkov, D.; Thorat, N.; Kim, B.; Viégas, F.; and Wattenberg, M. 2017.  SmoothGrad: Removing Noise by Adding Noise.  _arXiv preprint arXiv:1706.03825_.
  * Wah et al. (2011) Wah, C.; Branson, S.; Welinder, P.; Perona, P.; and Belongie, S. 2011.  The Caltech-UCSD Birds-200-2011 Dataset.  Technical Report CNS-TR-2011-001, California Institute of Technology.
  * Wiegreffe and Pinter (2019) Wiegreffe, S.; and Pinter, Y. 2019.  Attention is not not Explanation.  In _Conference on Empirical Methods in Natural Language Processing and International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 11–20.
  * Williams (1992) Williams, R. J. 1992.  Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning.  _Machine Learning_ , 8(3-4): 229–256.
  * Yang and Kim (2019) Yang, M.; and Kim, B. 2019.  Benchmarking Attribution Methods with Relative Feature Importance.  _arXiv preprint arXiv:1907.09701_.
  * Yu et al. (2019) Yu, M.; Chang, S.; Zhang, Y.; and Jaakkola, T. 2019.  Rethinking Cooperative Rationalization: Introspective Extraction and Complement Control.  In _Conference on Empirical Methods in Natural Language Processing and International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , 4085–4094.
  * Zheng et al. (2021) Zheng, Y.; Booth, S.; Shah, J.; and Zhou, Y. 2021.  The Irrationality of Neural Rationale Models.  _arXiv preprint arXiv:2110.07550_.
  * Zhou et al. (2016) Zhou, B.; Khosla, A.; Lapedriza, A.; Oliva, A.; and Torralba, A. 2016.  Learning Deep Features for Discriminative Localization.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2921–2929. IEEE.

##  Appendix A Relationship to Closely Related Works

In this section, we detail the similarity and difference between our proposal
and two closely related ones (Yang and Kim 2019; Adebayo et al. 2020). In
terms of similarity, the high-level idea is similar: for a natural dataset, we
do not know individual feature contribution, but generally highly correlated
and easily discriminative features should have high contribution, and we
realize this notion by injecting such features directly. All three works can
be seen as operationalizations of this idea.

However, this high-level idea needs two caveats, which set our paper aparts
from both works. First, features that we think to be “easily discriminative”
may not be be considered as such by neural nets. For example, Geirhos et al.
(2018) showed that they have particular inclination toward textures. Thus, we
can’t really trust them to actually pick up and use our introduced features,
unless that we are assured that focusing on other features cannot achieve the
performance that the model is achieving now. In this aspect, we concretely
demonstrated that network trained by Adebayo et al. (2018) can achieve good
performance when using the “other features” exclusively. Yang and Kim (2019)
demonstrated this principle, but used out-of-distribution data, so it is not
clear whether the failure is due to achieve good performance is really due to
the network indeed ignoring the “other features” or due to instability of out-
of-distribution extrapolation.

The second caveat is that the “other features” cannot have any information on
the injected features. For example, in Fig. 4 by Adebayo et al. (2020), the
saliency map that perfectly crops out the foreground dog shape could imply
that the network actually uses the contour of the dog, which is inconsistent
with their target conclusion that “foreground doesn’t matter in highly
correlated background dataset”. In other words, background with a dog contour
cropped out is very informative to the fact that the foreground is a dog. A
similar cropping procedure is used by Yang and Kim (2019) as well. Another
loophole is discussed in the Remark of Sec. 4, where the lack of one feature
at one place could imply the presence of another feature at another place. By
comparison, in our work, we define the joint effective region to contain all
injected, so we are assured that the features outside of the region absolutely
cannot contribute to the high performance, and then evaluate Attr% for that
region.

Finally, our framing is more general. We propose our domain-agnostic framework
in Sec. 3 and 4. Thus, it it straightforward to instantiate our idea to other
domains such as graph, speech, or time-series data. By comparison, both works
are focused on the foreground/background patch setting, and introduces
necessary concepts under this context. We also proposed ways to evaluate
feature-selection style attributions, more common for text models, at the end
of Sec. 3.

##  Appendix B Additional Details and Results for Saliency Map Evaluations

###  B.1 Manipulation Types

Figure 14: Examples of the five manipulations applied to an image, with
respective effective regions (ER) shown in gray.

We consider five image manipulation types. These manipulations are designed to
simulate possible image artifacts, which an undesirable model may rely on to
make decisions. Each manipulation has parameters which define the effective
region and the visibility level of the manipulation effect. Some of the
manipulation effects are technically stochastic, such as a watermark being
placed in a random position, but the effective region captures the localized
manipulation effect of all possible random instantiations. The five
manipulations are described below, with examples of each manipulation and
their associated effective regions shown in Fig. 14.

  * •

Peripheral blurring applies a Gaussian filter to the part of the image outside
of a certain radius. It is parametrized by

    * –

the radius of the unaffected part; and

    * –

the standard deviation of the Gaussian blurring filter.

Blurring could be due to either camera in motion or artistic post-processing
to highlight the main subject of the image.

  * •

Central brightness shift gradually changes the brightness in the hue-
saturation-brightness (HSB) space inside a certain radius, with maximal change
in the center. For our experiments, the brightness change is negative, meaning
that the center is dimmed. It is parametrized by

    * –

the radius of the dimmed region; and

    * –

the magnitude of the brightness shift at the center.

Brightness shift could be due to times of the day, or the use of artificial
light to illuminate the subject.

  * •

Striped hue shift modifies the hue (i.e. color) value of a vertical stripe in
the image. From top to bottom in the stripe, the hue value is first increased
and then decreased in a sinusoidal pattern. It is parametrized by

    * –

the upper position of the stripe;

    * –

the lower position of the stripe, with the width of the stripe being (upper -
lower); and

    * –

the magnitude of sinusoidal pattern.

Hue shift could be due to errors in conversion of different color space
encodings, which may result in color loss or distortion.

  * •

Striped noise randomly changes pixels inside a vertical stripe to a uniformly
random RGB value. It is parametrized by

    * –

the upper position of the stripe;

    * –

the lower position of the stripe, with the width of the stripe being (upper -
lower); and

    * –

the probability that each pixel is replaced.

Pixel noise could be due to lossy compression or data loss during
transmission.

  * •

Watermark overlays a text reading “IMGxxxx”, where “xxxx” are four random
digits, to a random location inside a rectangular region. “IMG” is written in
white and the digits are written in black. It is parametrized by

    * –

the upper-left coordinate of the rectangular region;

    * –

the lower-right coordinate of the rectangular region; and

    * –

the font size of the watermark text.

Watermark is a commonly employed technique to attribute the
author/organization of the image.

Normally, none of them should be expected to correlate with the label.
However, especially with image scraping on the web and crowdsourced dataset
construction, it is possible that some spurious correlations leak into the
final dataset.

###  B.2 Saliency Map Methods

We consider five saliency map methods.

  * •

Gradient (Simonyan, Vedaldi, and Zisserman 2013) computes the gradient of the
logit for the predicted class with respect to the input image. The three
channels of gradient are summed up in absolute value to get a single channel.

  * •

SmoothGrad (Smilkov et al. 2017) averages the gradients on 50 copies of the
input image $I$, each injected with independent Gaussian noise with with
$\mu=0$ and $\sigma=0.15\cdot(\max I-\min I)$, where $\max I$ and $\min I$ are
the maximal and minimal pixel values of the image.

  * •

GradCAM (Selvaraju et al. 2017) computes a saliency map from convolution
filter responses. Since we use the fully convolutional ResNet-34, this method
reduces to the class activation mapping (CAM) (Zhou et al. 2016).

  * •

LIME (Ribeiro, Singh, and Guestrin 2016) performs a linear regression using
super-pixels of the input image. The absolute values of the coefficients are
used to derive the saliency map. We use the default implementation of
lime.lime_ image.LimeImageExplainer with the quickshift clustering as the
super-pixel segmentation algorithm.

  * •

SHAP (Lundberg and Lee 2017) uses the idea of Shapley value (Roth 1988) for
attribution. We use the GradientSHAP instantiation with the default setting of
shap.GradientExplainer. We us the entire test set as the “background” data.

###  B.3 Attribution vs. Effective Region Size

Fig. 15 shows $\mathrm{\%Attr}$ vs $\mathrm{\%ER}$ for all pairs of saliency
maps and manipulations.

Figure 15: $\mathrm{\%Attr}$ vs $\mathrm{\%ER}$ for all pairs of saliency maps
and manipulations.

###  B.4 Attribution vs. Test Accuracy

Fig. 16 shows $\mathrm{\%Attr}$ vs test accuracy for all pairs of saliency
maps and manipulations.

Figure 16: $\mathrm{\%Attr}$ vs test accuracy for all pairs of saliency maps
and manipulations.

###  B.5 Attribution vs. Manipulation Visibility

We define the five visibility levels for each manipulation type as below. Note
that for fair comparison of $\mathrm{\%Attr}$ at different visibility levels,
it is crucial that the effective regions are independent of the visibility,
which is satisfied in all manipulation types below.

  * •

Blurring: The visibility level is defined as the Gaussian blur standard
deviation, with values of $\\{2,4,6,8,10\\}$ pixels, from least visible to
most.

  * •

Brightness: The visibility level is defined as the magnitude of the brightness
shift, with values of $\\{0.1,\allowbreak 0.15,\allowbreak 0.2,\allowbreak
0.25,\allowbreak 0.3\\}$ brightness component of the color (in the range of
[0, 1]), from least visible to most.

  * •

Hue: The visibility is defined as the magnitude of the hue shift, with values
of $\\{0.05,\allowbreak 0.1,\allowbreak 0.15,\allowbreak 0.2,\allowbreak
0.25\\}$ hue component of the color (in the range of [0, 1]), from least
visible to most.

  * •

Noise: The visibility is defined as the probability that a pixel is replaced
by a random value, with values of $\\{0.02,\allowbreak 0.04,\allowbreak
0.06,\allowbreak 0.08,\allowbreak 0.1\\}$, from least visible to most.

  * •

Watermark: The visibility is defined as the font size of the watermark, with
values of $\\{7,9,11,13,15\\}$ pixels, from least visible to most.

Fig. 17 shows $\mathrm{\%Attr}$ vs manipulation visibility for all pairs of
saliency maps and manipulations.

Figure 17: $\mathrm{\%Attr}$ vs manipulation visibility for all pairs of
saliency maps and manipulations.

###  B.6 Attribution vs. Original Feature Correlation

As explained in Sec. 5.4, $a(F)$ represents the expected accuracy of the model
when given only feature $F$. Note that this value should not be calculated as
the model accuracy on images with every pixel but $F$ being blacked out,
because such images are out of distribution where the model may exhibit
unreasonable behaviors (c.f. discussion by Hooker et al. (2019)).

Instead, the suppression of information beyond $F$ can be understood as an
inability for the model to distinguish inputs that agree on $F$. This leads to
the following process of simulating such a prediction. First, let
$\mathbb{P}_{X,Y|F=f}$ be the data distribution conditioned on $F=f$. Since
all features other than $F$ are suppressed, the model cannot further
distinguish two inputs $x,x^{\prime}\sim\mathbb{P}_{X|F=f}$. As a result, the
expected accuracy can be computed by comparing the model’s prediction on $x$
against the ground truth label on $x^{\prime}$. Then we take the expectation
of this accuracy according to different values of $f\sim\mathbb{P}_{F}$, where
$\mathbb{P}_{F}$ is the marginal distribution of $F$. Formally, for the model
prediction function $g:\mathcal{X}\rightarrow\mathcal{Y}$, we have

$\displaystyle
a(F)=\mathbb{E}_{f\sim\mathbb{P}_{F}}\left[\mathbb{E}_{x,y\sim\mathbb{P}_{X,Y|F=f}}\left[\mathbb{E}_{x^{\prime},y^{\prime}\sim\mathcal{P}_{X,Y|F=f}}\left[\mathbbm{1}_{g(x)=y^{\prime}}\right]\right]\right].$
(9)

With balanced label distribution, $a(\varnothing)$ means that the model has no
information about the input, and thus the accuracy is 0.5. On the other hand,
$a(F_{M}\cup F_{O})$ means that the model has full access to the input, and
thus the accuracy is the normal model accuracy $p$. In addition, we have
$a(F_{O})\leq r$, because the label reassignment weakens the correlation
between $F_{O}$ and the label.

Finally and somewhat counter-intuitively, the above definition also implies
that $a(F_{M})=a(F_{M}\cup F_{O})=p$ for the following reason: since every
$F_{M}=f_{M}$ is perfectly correlated with the label, all the data in
$\mathbb{P}_{X,Y|F_{M}=f_{M}}$ have the same label and thus the non-
identifiability of any two inputs $x$ and $x^{\prime}$ does not additionally
degrade the model performance. However, note that this result comes from the
mechanical application of Shapley value calculation, which is a popular and
axiomatic definition of attribution. Whether it is reasonable in light of this
implication is beyond the scope of the paper.

Fig. 18 shows $\mathrm{\%Attr}$ vs the label reassignment parameter $r$ for
all pairs of saliency maps and manipulations.

Figure 18: $\mathrm{\%Attr}$ vs label reassignment parameter $r$ for all pairs
of saliency maps and manipulations.

##  Appendix C Additional Results for Attention Mechanism Evaluations

###  C.1 Highly Obvious Manipulations

Fig. 19 presents additional visualizations of the learned attention
distribution of the model.

Figure 19: Additional attention distributions. Orange/green bars represent
articles/non-articles.

###  C.2 Misleading Non-Correlating Features

Fig. 20 presents additional visualizations of the learned attention
distribution on the CN (left) and NC (right) datasets.

Figure 20: Additional attention visualizations on the CN (left) and NC (right)
datasets. Orange/blue/green bars represent corr. articles/ non-corr.
articles/other words.

##  Appendix D Additional Results for Rationale Model Evaluations

###  D.1 Highly Obvious Manipulations

Fig. 21 presents four additional reviews annotated by the “faulty” CR model
showing that it consistently selects the first few words of the review.

pours a clear yellow . 1/4 inch head of a white color . slight retention and slight lacing . smells of sweet malt , pale malt , fruit , and slight bread aroma . fits a style of a belgian pale ale . mouth feel is smooth and crisp with a high carbonation level . tastes of pale malt , yeast cleanliness , slight hops , and very slight fruit . overall , a decent brew but nothing special . |  bottle to snifter glass . pitch black with little lacing around edge . smells like the typical oatmeal stout . taste has the great balance between both milk and oatmeal . sweet from the sugars and mild dark chocolate in the after taste . smooth and chewey . leans to the heavier side in the mouth . great example of two styles blended . worth seeking .
---|---
12oz can poured into pint glass . pours the pale golden straw color with the 2 finger fizzy head that settles quickly . slightly hazy when held to the light . smell is fairly nuetral with the bit of sweet malts coming through . the slight scent of something metallic . taste is decent . nothing crazy or unique but extremely clean , classic american pale lager flavor . mild light malt flavor with just enough hops for balance . no major off-flavors here . mouthfeel is fluid and crisp . this went down quickly and i am not the fizzy yellow beer fan . for what it is , it ’s done well . |  a- dark brown with hints of amber at a edges , small head which disappeared quickly and dissipated into a few sad bubbles . s- tons of sweet bourbon booze . raisins , sugared malts , dark chocolate filled with raspberry . t- booze and brown sugared malts mingle with one another . this is drinking like a barleywine to me . lots of wood and oak flavor drenched in booze . m- smooth creamy with enough carbonation . d- it ’s a delicious brew that needs to be savored one of a best if not a best scotch ales ive had .
Figure 21: 4 additional reviews annotated by the “faulty” continuous
relaxation model that consistently selects the first few words regardless.
Selected non-articles in orange bold italics, selected articles in green bold,
and missed articles in red italics.

###  D.2 Misleading Non-Correlating Features

Fig. 22 shows rationale selections by the two models for the same review at
the same target $\mathrm{\%Sel}$.

|  CN Dataset |  NC Dataset
---|---|---
CR Model |  enjoyed @ la cave a bulles ; simon & a head brewer of brasserie de vines hosted a tasting on 11/5 . medium body , frothy mouth-feel , nice carbonation . nice fruity notes upfront , green apples and citrus , with the hint of sourness . finishes with the fresh piney hop presence and the mild bitterness . overall ; great diversity in flavors , very fresh tasting . |  enjoyed @ la cave the bulles ; simon & the head brewer of brasserie de vines hosted the tasting on 11/5 . medium body , frothy mouth-feel , nice carbonation . nice fruity notes upfront , green apples and citrus , with a hint of sourness . finishes with a fresh piney hop presence and a mild bitterness . overall ; great diversity in flavors , very fresh tasting .
RL Model |  enjoyed @ la cave a bulles ; simon & a head brewer of brasserie de vines hosted a tasting on 11/5 . medium body , frothy mouth-feel , nice carbonation . nice fruity notes upfront , green apples and citrus , with the hint of sourness . finishes with the fresh piney hop presence and the mild bitterness . overall ; great diversity in flavors , very fresh tasting . |  enjoyed @ la cave the bulles ; simon & the head brewer of brasserie de vines hosted the tasting on 11/5 . medium body , frothy mouth-feel , nice carbonation . nice fruity notes upfront , green apples and citrus , with a hint of sourness . finishes with a fresh piney hop presence and a mild bitterness . overall ; great diversity in flavors , very fresh tasting .
Figure 22: Additional reviews from CN and NC datasets for the two models.
Selected words are underlined. Ground truth correlating articles are in green
bold, and non-correlating articles in red italics. The CR model performs well
on this review, focusing exclusively on correlating articles, while the RL
model selects non-correlating articles, and misses a correlating one for the
NC dataset.


# Quadratic embedding constants of path graphs

Wojciech Młotkowski  Instytut Matematyczny, Uniwersytet Wrocławski, Plac
Grunwaldzki 2/4, 50-384 Wrocław, Poland<EMAIL_ADDRESS>
###### Abstract.

We characterize positive definiteness for some family of matrices. As an
application, we derive the explicit value of the quadratic embedding constants
of the path graphs.

###### Key words and phrases:

Positive definite matrix, conditionally negative definite matrix, distance
matrix of a graph, path graph, quadratic embedding constant

###### 2010 Mathematics Subject Classification:

Primary 05C50; Secondary 05C12, 15A15

##  1\. Introduction

Let $G=(V,E)$ be a graph, with $V$ as the set of vertices and $E$ as the set
of edges, i.e. two-element subsets of $V$. We assume that $G$ is connected,
which means that for every $x,y\in V$ there exists a walk connecting $x$ and
$y$: a finite sequence $x_{0},x_{1},\ldots,x_{n}\in V$ such that $n\geq 0$,
$x_{0}=x,x_{n}=y$ and $\\{x_{i-1},x_{i}\\}\in E$ for $i=1,\ldots,n$. The
distance $d(x,y)$ is defined as the smallest possible length $n$ of such a
walk. For some connected graphs the distance matrix $(d(x,y))_{x,y\in V}$ is
conditionally negative definite, equivalently, there exists a function $\phi$
which maps $V$ into a Hilbert space $\mathcal{H}$ and satisfies

$d(x,y)=\|\phi(x)-\phi(y)\|^{2}$

for all $x,y\in V$. This motivated the authors of [5] to introduce and study
the quadratic embedding constant, defined as

(1) $\mathrm{QEC}(G):=\sup\left\\{\sum_{x,y\in
V}d(x,y)f(x)f(y):f\in\mathcal{F}_{0,1}(V)\right\\},$

where $\mathcal{F}_{0,1}(V)$ denotes the set of all finitely supported
functions $f:V\to\mathbb{R}$ satisfying $\sum_{x\in V}f(x)=0$ and $\sum_{x\in
V}f(x)^{2}=1$. In particular, the distance matrix $(d(x,y))_{x,y\in V}$ is
conditionally negative definite if and only if $\mathrm{QEC}(G)\leq 0$.
Several examples and properties were furnished in [1, 2, 3, 4, 5]. Applying
the min-max theorem and the Perron-Frobenius theorem, one can observe that if
$V$ is finite and
$\lambda_{1}(G)\geq\lambda_{2}(G)\geq\ldots\geq\lambda_{|V|}(G)$ are the
eigenvalues of the distance matrix of $G$, then

$\lambda_{2}(G)\leq\mathrm{QEC}(G)<\lambda_{1}(G).$

In this paper we will study finite path graphs, i.e. graphs of the form
$P_{n}:=(V,E)$, where

$V:=\\{1,2,\ldots,n\\},\qquad
E:=\big{\\{}\\{1,2\\},\\{2,3\\},\ldots,\\{n-1,n\\}\big{\\}}.$

The eigenvalues $\lambda_{i}(P_{n})$ of the distance matrix of $P_{n}$ were
found in [7]. In particular,

$\lambda_{2}(P_{n})=\left\\{\begin{array}[]{ll}\displaystyle\frac{-1}{1+\cos(\pi/n)}\phantom{\frac{a}{\frac{a}{\frac{b}{c}}}}&\hbox{if
$n$ is even,}\\\ \displaystyle\frac{-1}{1-\cos\theta^{*}}&\hbox{if $n$ is
odd,}\end{array}\right.$

where $\theta^{*}$ is the maximal solution of the equation:

$\tan(\theta/2)\tan(n\theta/2)=-1/n,\qquad\theta\in(0,\pi).$

It was observed in [3, Proposition 5.4] that $\mathrm{QEC}(P_{n})$ is equal to
the minimal $t$ such that the matrix

(2) $\left[2\min\\{i,j\\}+t+t\cdot\delta_{i,j}\right]_{i,j=1}^{n-1}$

is positive definite, i.e. all the eigenvalues of this matrix are nonnegative.
This led to inequality: $\mathrm{QEC}(P_{n})\leq-1/2$, see [3, Theorem 5.6].
Our aim is to provide the exact value:

######  Theorem 1.1.

For $n\geq 2$ we have

(3) $\mathrm{QEC}(P_{n})=\frac{-1}{1+\cos(\pi/n)}.$

Consequently, if $n$ is even then $\lambda_{2}(P_{n})=\mathrm{QEC}(P_{n})$ and
if $n$ is odd then $\lambda_{2}(P_{n})<\mathrm{QEC}(P_{n})$.

As an immediate consequence we obtain the quadratic embedding constant for
$\mathbb{N}$ and $\mathbb{Z}$ regarded as infinite path graphs, with edges
$\\{i,i+1\\}$, $i\in\mathbb{N}$ or $i\in\mathbb{Z}$, c.f. [3, Theorem 5.7].

######  Corollary 1.2.

$\mathrm{QEC}(\mathbb{N})=\mathrm{QEC}(\mathbb{Z})=-1/2$.

The paper is organized as follows. First we examine a family of auxiliary
polynomials $S_{n}(a,b;t)$, $a,b\in\mathbb{R}$, $n\geq 0$. Section 3 is
devoted to the study of a family $A_{n}(s,t)$ of matrices, a two-parameter
version of (2). We provide formula for $\det A_{n}(s,t)$, $n<\infty$, in terms
of polynomials $S_{n}(a,b;t)$, and characterize these $s,t\in\mathbb{R}$ for
which $A_{n}(s,t)$, $1\leq n\leq\infty$, is positive definite. Finally we
prove Theorem 1.1.

##  2\. A family of polynomials

Now we are going to study a family of polynomials defined by the following
recurrence: $S_{0}(a,b;t):=1$, $S_{1}(a,b;t):=at+b$ and

(4) $S_{n}(a,b;t)=(1+2t)S_{n-1}(a,b;t)-t^{2}S_{n-2}(a,b;t)$

for $n\geq 2$, $a,b,t\in\mathbb{R}$.

######  Proposition 2.1.

For $n\geq 0$ we have $\deg S_{n}(a,b;t)\leq n$ and the coefficient at $t^{n}$
in $S_{n}(a,b;t)$ is equal to $an-n+1$. Moreover,

(5)
$S_{n}(a,b;t)=(at+b)\sum_{k=0}^{n-1}\binom{2n-k-1}{k}t^{k}-\sum_{k=0}^{n-2}\binom{2n-k-3}{k}t^{k+2}\\\
=\frac{1}{2^{n+1}\sqrt{1+4t}}\left[\left(2b-1+2(a-1)t+\sqrt{1+4t}\right)\left(1+2t+\sqrt{1+4t}\right)^{n}\right.\\\
\left.-\left(2b-1+2(a-1)t-\sqrt{1+4t}\right)\left(1+2t-\sqrt{1+4t}\right)^{n}\right].$

The former formula holds for $n\geq 1$, while the latter for $n\geq 0$ and
$t\neq-1/4$. For $t=-1/4$, $n\geq 0$ we have

(6) $S_{n}(a,b;-1/4)=\frac{1}{4^{n}}\left(4nb-na-n+1\right).$

###### Proof.

The first statement can be easily proved by induction. Now define:

(7) $W_{n}(t):=\sum_{k=0}^{n}\binom{2n-k+1}{k}t^{k}$

(see $A172431$ in OEIS [6]). Then $W_{0}(t)=1$, $W_{1}(t)=2t+1$, and one can
check that

$W_{n}(t)=(1+2t)W_{n-1}(t)-t^{2}W_{n-2}(t)$

for $n\geq 2$, so that $W_{n}(t)=S_{n}(2,1;t)$. Putting $Q_{0}(t):=1$ and

$Q_{n}(t):=(at+b)W_{n-1}(t)-t^{2}W_{n-2}(t)$

for $n\geq 1$ ($W_{-1}(t):=0$) we have $Q_{1}(t)=at+b$ and
$Q_{n}(t)=(1+2t)Q_{n-1}(t)-t^{2}Q_{n-2}(t)$ for $n\geq 1$, so $Q_{n}(t)$
coincides with $S_{n}(a,b;t)$ and the first formula in (5) holds. Moreover, it
is easy to verify by induction that $W_{n}(-1/4)=(n+1)/4^{n}$, which leads to
(6).

For $n\geq 0$, $a,b\in\mathbb{R}$, $t\neq-1/4$ put

$\phantom{u}T_{n}(t):=\frac{1}{2^{n+1}\sqrt{1+4t}}\left[\left(2b-1+2(a-1)t+\sqrt{1+4t}\right)\left(1+2t+\sqrt{1+4t}\right)^{n}\right.\\\
\left.-\left(2b-1+2(a-1)t-\sqrt{1+4t}\right)\left(1+2t-\sqrt{1+4t}\right)^{n}\right].\phantom{u}$

Then $T_{0}(t)=1$, $T_{1}(t)=at+b$ and from the identity

$\left(1+2t\pm\sqrt{1+4t}\right)^{2}=2(1+2t)\left(1+2t\pm\sqrt{1+4t}\right)-4t^{2}$

we have

$T_{n}(t)=(1+2t)T_{n-1}(t)-t^{2}T_{n-2}(t)$

for $n\geq 2$, which implies that $T_{n}(t)=S_{n}(a,b;t)$ for $n\geq 0$,
$t\neq-1/4$. ∎

For later use, we record the following identities:

######  Proposition 2.2.

For $W_{n}(t)$ defined in (7) we have:

(8) $W_{n}(t)=S_{n}(2,1;t)=S_{n}(1,t+1;t).$

Moreover,

(9)
$W_{n}(t)=\frac{1}{2^{n+1}\sqrt{1+4t}}\left[\left(1+2t+\sqrt{1+4t}\right)^{n+1}-\left(1+2t-\sqrt{1+4t}\right)^{n+1}\right].$

###### Proof.

The former equality in (8) was noted in the previous proof, the latter, as
well as (9), is a consequence of (5). ∎

In some particular cases we are able to find the roots of $S_{n}(a,b;t)$.

######  Proposition 2.3.

For $n\geq 1$ we have

(10) $\displaystyle\frac{1}{n+1}S_{n}(2,1;t)$
$\displaystyle=\prod_{k=1}^{n}\left(t+\frac{1}{2+2\cos\left(\frac{k\pi}{n+1}\right)}\right),$
(11) $\displaystyle S_{n}(1,1/2;t)$
$\displaystyle=\prod_{k=1}^{n}\left(t+\frac{1}{2+2\cos\big{(}\frac{(2k-1)\pi}{2n}\big{)}}\right),$
(12) $\displaystyle S_{n}(1,1;t)$
$\displaystyle=\prod_{k=1}^{n}\left(t+\frac{1}{2+2\cos\left(\frac{2k\pi}{2n+1}\right)}\right),$
(13) $\displaystyle\frac{1}{2n+1}S_{n}(3,1;t)$
$\displaystyle=\prod_{k=1}^{n}\left(t+\frac{1}{2+2\cos\big{(}\frac{(2k-1)\pi}{2n+1}\big{)}}\right).$

###### Proof.

First we note that in view of the first part of Proposition 2.1, if $a\geq 1$
then $\deg S_{n}(a,b;t)=n$ and the leading term is $(an-n+1)t^{n}$.

Fix $a,b,t\in\mathbb{R}$, with $1+4t<0$, and put

$\displaystyle w$ $\displaystyle:=2b-1+2(a-1)t+\sqrt{1+4t},$ $\displaystyle z$
$\displaystyle:=1+2t+\sqrt{1+4t},$

with $\mathrm{Im}(w)>0$, $\mathrm{Im}(z)>0$, $\alpha:=\mathrm{arg}(w)$,
$\beta:=\mathrm{arg}(z)$, $0<\alpha,\beta<\pi$. Then

$\cos\beta=\frac{1+2t}{-2t}\qquad\hbox{and hence}\qquad
t=\frac{-1}{2+2\cos\beta}.$

In view of (5), we have $S_{n}(a,b;t)=0$ if and only if $w\cdot
z^{n}=\overline{w}\cdot\overline{z}^{n}$, equivalently, $\alpha+n\beta=k\pi$
for some $k=1,2,\ldots,n$. Now we consider four cases.

1\. If $a=2$, $b=1$ then $w=z$, $\alpha=\beta$ and therefore
$\beta=k\pi/(n+1)$.

2\. If $a=1$, $b=1/2$ then $\alpha=\pi/2$ and then $\beta=(2k-1)\pi/(2n)$.

3\. If $a=b=1$ then

$\cos\alpha=\frac{1}{\sqrt{-4t}}=\sqrt{\frac{1+\cos\beta}{2}}=\cos(\beta/2),$

which implies $\alpha=\beta/2$ and $\beta=2k\pi/(2n+1)$.

4\. Finally, if $a=3$, $b=1$ then

$\phantom{aaa}\cos\alpha=\frac{1+4t}{\sqrt{4t(1+4t)}}=-\sqrt{\frac{1+4t}{4t}}=-\sqrt{\frac{1-\cos\beta}{2}}\\\
=-\sin(\beta/2)=\cos(\pi/2+\beta/2),\phantom{aaa}$

therefore $\alpha=\pi/2+\beta/2$ and, consequently, $\beta=(2k-1)\pi/(2n+1)$.
∎

######  Lemma 2.4.

For $n\geq 1$, $a,b\in\mathbb{R}$ we have

(14) $S_{n}(2,1;t)\cdot S_{n}(a,b;t)-S_{n-1}(2,1;t)\cdot
S_{n+1}(a,b;t)=t^{2n}.$

###### Proof.

Putting

$u_{\pm}:=2b-1+2(a-1)t\pm\sqrt{1+4t},\qquad v_{\pm}:=1+2t\pm\sqrt{1+4t}$

we have

$\phantom{uu}\left(v_{+}^{n+1}-v_{-}^{n+1}\right)\left(u_{+}v_{+}^{n}-u_{-}v_{-}^{n}\right)-\left(v_{+}^{n}-v_{-}^{n}\right)\left(u_{+}v_{+}^{n+1}-u_{-}v_{-}^{n+1}\right)\\\
=(u_{+}-u_{-})(v_{+}-v_{-})(v_{+}v_{-})^{n}=4(1+4t)\left(4t^{2}\right)^{n},\phantom{uu}$

and, by (5), the formula follows. ∎

Define

(15) $t_{n}:=\left\\{\begin{array}[]{ll}-\infty&\hbox{if $n=1$,}\\\
\displaystyle\frac{-1}{2+2\cos(\pi/n)}&\hbox{if $n\geq 2$.}\end{array}\right.$

######  Lemma 2.5.

If $t_{n}<t<t_{n+1}$ then $S_{n-1}(2,1;t)>0$, $S_{n}(2,1;t)<0$ and if
$t>t_{n+1}$ then $S_{n-1}(2,1;t)>0$, $S_{n}(2,1;t)>0$.

###### Proof.

First note that the function $\alpha\mapsto-1/(2+2\cos\alpha)$ is decreasing
with $\alpha\in(0,\pi)$. Therefore the statement is a consequence of (10),
because for $n\geq 2$ we have

$\frac{-1}{2+2\cos\big{(}2\pi/(n+1)\big{)}}<\frac{-1}{2+2\cos\big{(}\pi/n\big{)}}<\frac{-1}{2+2\cos\big{(}\pi/(n+1)\big{)}}.$

∎

Now we collect properties of polynomials of the form $S_{n}(1,s+1;t)$, which
will be applied in the next section.

######  Proposition 2.6.

For $s\in\mathbb{R}$, $n\geq 1$, we have

(16) $\phantom{uu}S_{n}(1,s+1;t)=S_{n}(1,1;t)+s\cdot S_{n-1}(2,1;t)\\\
=\sum_{k=0}^{n}\binom{2n-k}{k}t^{k}+s\sum_{k=0}^{n-1}\binom{2n-1-k}{k}t^{k}\\\
=\frac{1}{2^{n+1}\sqrt{1+4t}}\left[\left(1+2s+\sqrt{1+4t}\right)\left(1+2t+\sqrt{1+4t}\right)^{n}\right.\\\
\left.-\left(1+2s-\sqrt{1+4t}\right)\left(1+2t-\sqrt{1+4t}\right)^{n}\right].\phantom{uu}$

The latter formula is valid for $t\neq-1/4$, while

(17) $S_{n}(1,s+1;-1/4)=\frac{4ns+2n+1}{4^{n}}.$

###### Proof.

The first equality in (16) can be verified by induction: putting
$P_{n}(t):=S_{n}(1,1;t)+s\cdot S_{n-1}(2,1;t)$ we have $P_{0}(t)=1$,
$P_{1}(t)=t+1+s$ and $P_{n}(t)=(1+2t)P_{n-1}(t)-t^{2}P_{n-2}(t)$ for $n\geq
2$, consequently $P_{n}(t)=S_{n}(1,s+1;t)$ for all $n\geq 0$. Now (16) and
(17) are consequences of (5) and (6). ∎

##  3\. A family of matrices

Define a family of matrices

(18) $A_{n}(s,t):=\left[\min\\{i,j\\}+s+t\delta_{i,j}\right]_{i,j=1}^{n},$

where $s,t\in\mathbb{R}$, $1\leq n\leq\infty$. These matrices seem interesting
on their own, for the sake of Theorem 1.1 we are particularly interested in
the case $s=t$. We are going to study their determinants and positive
definiteness. Note that if $s_{1}\leq s_{2}$, $t_{1}\leq t_{2}$, $n_{1}\geq
n_{2}$ and $A_{n_{1}}(s_{1},t_{1})$ is positive definite then so is
$A_{n_{2}}(s_{2},t_{2})$.

######  Theorem 3.1.

For $s,t\in\mathbb{R}$, $n\in\mathbb{N}$, we have

(19) $\det A_{n}(s,t)=S_{n}(1,s+1;t)=S_{n}(1,1;t)+s\cdot S_{n-1}(2,1;t).$

With the notation of (15), the matrix $A_{n}(s,t)$ is positive definite if and
only if

(20) $t>t_{n}\qquad\hbox{and}\qquad S_{n}(1,s+1;t)\geq 0.$

###### Proof.

It is easy to verify (19) for $n=1,2$. Now assume that $n\geq 3$ and let
$\mathbf{k}_{j}$ denote the $j$th column of $A_{n}(s,t)$. Then

$\det
A_{n}(s,t)=\det(\mathbf{k}_{1},\ldots,\mathbf{k}_{n})=\det(\mathbf{k}_{1},\ldots,\mathbf{k}_{n-1},\mathbf{k}_{n}-\mathbf{k}_{n-1})$

and, denoting the transposition by “$\mathrm{T}$”, we have

$\mathbf{k}_{n}-\mathbf{k}_{n-1}=(0,\ldots,0,-t,1+t)^{\mathrm{T}}.$

Expanding the determinant along the last column
$\mathbf{k}_{n}-\mathbf{k}_{n-1}$, we get

$\det A_{n}(s,t)=(1+t)\det A_{n-1}(s,t)+t\det B,$

where

$B=\left(\mathbf{k}^{\prime}_{1},\ldots,\mathbf{k}^{\prime}_{n-2},\mathbf{k}^{\prime}_{n-1}+\eta\right),$

$\mathbf{k}^{\prime}_{j}$ is the $j$th column of $A_{n-1}(s,t)$ and
$\eta:=(0,\ldots,0,-t)^{\mathrm{T}}$. This yields

$\det B=\det A_{n-1}(s,t)-t\det A_{n-2}(s,t),$

and, consequently,

$\det A_{n}(s,t)=(1+2t)\det A_{n-1}(s,t)-t^{2}\det A_{n-2}(s,t),$

which completes the proof of (19).

Fix $t^{\prime}\in\mathbb{R}$ and put

$\ell_{k}(s):=\det A_{k}(s,t^{\prime}):=b_{k}+s\cdot a_{k}.$

Then, by Lemma 2.4, we have

(21) $a_{k}b_{k-1}-a_{k-1}b_{k}=(t^{\prime})^{2k-2}.$

With the notation of (15), if $t_{k-1}<t^{\prime}\leq t_{k}$ then $a_{k-1}>0$,
$a_{k}\leq 0$. Consequently, the lines $\ell_{k-1},\ell_{k}$ cross at some
point $(s^{\prime},y^{\prime})$, i.e.
$\ell_{k-1}(s^{\prime})=\ell_{k}(s^{\prime})=y^{\prime}$, and, by (21),

$y^{\prime}=\frac{a_{k}b_{k-1}-a_{k-1}b_{k}}{a_{k}-a_{k-1}}<0.$

This implies, that for every $s\in\mathbb{R}$ we have either $\ell_{k-1}(s)<0$
or $\ell_{k}(s)<0$, therefore the matrix $A_{n}(s,t^{\prime})$ is not positive
definite for $n\geq k$.

Now, if we assume that $t^{\prime}>t_{n}$ then $a_{1},\ldots,a_{n}>0$.
Defining $s_{k}$ by $\ell_{k}(s_{k})=0$, we have $s_{1}\leq
s_{2}\leq\ldots\leq s_{n}$, by (21). Therefore, if $\det
A_{n}(s,t^{\prime})>0$ then $s>s_{n}$, $\det A_{k}(s,t^{\prime})>0$ for all
$k\leq n$, and hence $A_{n}(s,t^{\prime})$ is positive definite. If $\det
A_{n}(s,t^{\prime})=0$ then $A_{n}(s,t^{\prime})$ is positive definite as
pointwise limit of positive definite matrices. The proof is complete. ∎

Note, that in particular,

(22) $\det A_{n}(t,t)=S_{n}(1,t+1;t)=S_{n}(2,1)=W_{n}(t).$

Since $S_{n}(1,s_{0}+1;t)$ is the characteristic polynomial of a real
symmetric matrix, we have

######  Corollary 3.2.

For every fixed $s_{0}\in\mathbb{R}$, $n\geq 1$, the polynomial
$S_{n}(1,s_{0}+1;t)$ has only real roots.

Now we consider some particular cases.

######  Theorem 3.3.

We have the following:

  * •

The matrix $A_{n}(t,t)$ is positive definite if and only if

$t\geq\frac{-1}{2+2\cos\big{(}\pi/(n+1)\big{)}}.$

  * •

The matrix $A_{n}(-1/2,t)$ is positive definite if and only if

$t\geq\frac{-1}{2+2\cos\big{(}\pi/(2n)\big{)}}.$

  * •

The matrix $A_{n}(0,t)$ is positive definite if and only if

$t\geq\frac{-1}{2+2\cos\big{(}2\pi/(2n+1)\big{)}}.$

  * •

The matrix $A_{n}(2t,t)$ is positive definite if and only if

$t\geq\frac{-1}{2+2\cos\big{(}\pi/(2n+1)\big{)}}.$

###### Proof.

First note that by (5) we have $S_{n}(1,2t+1;t)=S_{n}(3,1;t)$. It is easy to
check the statements for $n=1$. For $0<k<m$ put

$t^{k}_{m}:=\frac{-1}{2+2\cos(k\pi/m)}.$

Then, for $n>1$, we have $t^{2}_{n+1}<t^{1}_{n}<t^{1}_{n+1}$,
$t^{3}_{2n}<t^{1}_{n}<t^{1}_{2n}$, $t^{4}_{2n+1}<t^{1}_{n}<t^{2}_{2n+1}$,
$t^{3}_{2n+1}<t^{1}_{n}<t^{1}_{2n+1}$, and the statements follow from Theorem
3.1 and Proposition 2.3. ∎

Now we are able to describe the case $n=\infty$.

######  Theorem 3.4.

The infinite matrix $A_{\infty}(s,t)$ is positive definite if and only if

$1+4t\geq 0\qquad\hbox{and}\qquad 1+2s+\sqrt{1+4t}\geq 0.$

###### Proof.

If $1+4t\geq 0$ and $1+2s+\sqrt{1+4t}\geq 0$ then all the matrices
$A_{n}(s,t)$, $1\leq n<\infty$, are positive definite by (19), (16) and (17),
hence so is $A_{\infty}(s,t)$.

Now assume that $A_{\infty}(s,t)$ is positive definite. Then
$t>-1/\big{(}2+2\cos(\pi/n)\big{)}$ for every $n\in\mathbb{N}$, which implies
$t\geq-1/4$. If $t=-1/4$ then $s\geq-1/2$ in view of (17). If $1+4t>0$ then,
putting

$q:=\frac{1+2t-\sqrt{1+4t}}{1+2t+\sqrt{1+4t}},$

we have $0<q<1$ and, in view of the last formula in (16), the inequality

$1+2s+\sqrt{1+4t}\geq\left(1-2s+\sqrt{1+4t}\right)q^{n}$

holds for every $n\geq 1$. This implies that $1+2s+\sqrt{1+4t}\geq 0$. ∎

Figure 1. The range of positive definiteness of $A_{\infty}(s,t)$

For example, the following matrix is positive definite:

$4A_{\infty}(-1/2,-1/4)=\left(\begin{array}[]{cccccc}1&2&2&2&2&\ldots\\\
2&5&6&6&6&\ldots\\\ 2&6&9&10&10&\ldots\\\ 2&6&10&13&14&\ldots\\\
2&6&10&14&17&\ldots\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\ddots\end{array}\right).$

##  4\. Path graphs

Now we are ready to prove the main result of this paper.

###### Proof of Theorem 1.1.

In view of [3, Proposition 5.4], $\mathrm{QEC}(P_{n})$ is equal to the minimal
$t$ such that $A_{n-1}(t/2,t/2)$ is positive definite. It remains to apply the
first part of Theorem 3.3. ∎

Now we indicate explicitly a vector $\mathbf{x}_{n}$ on the vertices of
$P_{n}$ for which the supremum in (1) is attained. Put

(23)
$\mathbf{x}_{n}:=\left(x_{n,1},x_{n,2},\ldots,x_{n,n}\right),\quad\hbox{with}\quad
x_{n,i}:=(-1)^{i}\sin\left(\frac{2i-1}{2n}\pi\right).$

If $n$ is even then $\mathbf{x}_{n}$ is the eigenvector corresponding to the
second eigenvalue $\lambda_{2}(P_{n})$, see [7].

######  Proposition 4.1.

For $n\geq 2$ we have

(24) $\sum_{i=1}^{n}x_{n,i}=0,\qquad\sum_{i=1}^{n}x_{n,i}^{2}=\frac{n}{2}$

and

(25) $\sum_{i,j=1}^{n}|i-j|x_{n,i}\cdot
x_{n,j}=\frac{-1}{1+\cos(\pi/n)}\cdot\frac{n}{2}.$

###### Proof.

Denoting by “$\mathbf{i}$” the imaginary unit, we have

$\sum_{i=1}^{n}(-1)^{i}\exp\left(\frac{2i-1}{2n}\pi\mathbf{i}\right)=-\exp\left(\pi\mathbf{i}/(2n)\right)\frac{1+(-1)^{n}}{1+\exp\left(\pi\mathbf{i}/n\right)}=\frac{-1-(-1)^{n}}{2\cos\big{(}\pi/(2n)\big{)}}.$

Taking the imaginary part we get the first equation in (24). Similarly, since

$\sum_{i=1}^{n}\exp\left(\frac{(2i-1)\pi}{n}\mathbf{i}\right)=0,$

we get

$2\sum_{i=1}^{n}\sin^{2}\left(\frac{(2i-1)\pi}{2n}\right)=\sum_{i=1}^{n}\left[1-\cos\left(\frac{(2i-1)\pi}{n}\right)\right]=n,$

which completes the proof of (24).

Now we will prove (25). For $1\leq k<n$ we have

$\phantom{uuu}2\sum_{i=1}^{n-k}\sin\left(\frac{2i-1}{2n}\pi\right)\sin\left(\frac{2i+2k-1}{2n}\pi\right)\\\
=\sum_{i=1}^{n-k}\left[\cos(k\pi/n)-\cos\big{(}(2i+k-1)\pi/n\big{)}\right]\\\
=(n-k)\cos(k\pi/n)+\frac{\sin(k\pi/n)}{\sin(\pi/n)}.\phantom{uuu}$

Therefore

(26) $\phantom{uuu}\sum_{i,j=1}^{n}|i-j|x_{n,i}\cdot
x_{n,j}=2\sum_{k=1}^{n-1}k\sum_{i=1}^{n-k}x_{n,i}\cdot x_{n,i+k}\\\
=\sum_{k=1}^{n-1}(-1)^{k}k(n-k)\cos(k\pi/n)+\sum_{k=1}^{n-1}(-1)^{k}\frac{k\sin(k\pi/n)}{\sin(\pi/n)}.\phantom{uuu}$

Now applying elementary formulas:

$\displaystyle\sum_{k=1}^{n-1}kq^{k}$
$\displaystyle=\frac{q(1-q^{n})-nq^{n}(1-q)}{(1-q)^{2}},$
$\displaystyle\sum_{k=1}^{n-1}k(n-k)q^{k}$
$\displaystyle=\frac{nq(1-q)(1+q^{n})-q(1+q)(1-q^{n})}{(1-q)^{3}}$

to $q:=-\exp(\pi\mathbf{i}/n)$, so that $q^{n}=-(-1)^{n}$, we obtain

$\sum_{k=1}^{n-1}k(-1)^{k}\exp(k\pi\mathbf{i}/n)=\frac{-1-(-1)^{n}+(-1)^{n}n\big{(}\exp(-\pi\mathbf{i}/n)+1\big{)}}{4\cos^{2}\big{(}\pi/(2n)\big{)}},$
$\phantom{uuuu}\sum_{k=1}^{n-1}k(n-k)(-1)^{k}\exp(k\pi\mathbf{i}/n)\\\
=\frac{2n\cos\big{(}\pi/(2n)\big{)}\big{(}(-1)^{n}-1\big{)}+2\sin\big{(}\pi/(2n)\big{)}\big{(}1+(-1)^{n}\big{)}\mathbf{i}}{8\cos^{3}\big{(}\pi/(2n)\big{)}}.\phantom{uuuu}$

Consequently,

$\displaystyle\sum_{k=0}^{n}\frac{(-1)^{k}k\sin(k\pi/n)}{\sin(\pi/n)}$
$\displaystyle=\frac{-(-1)^{n}n}{4\cos^{2}(\pi/(2n))},$
$\displaystyle\sum_{k=0}^{n}(-1)^{k}k(n-k)\cos(k\pi/n)$
$\displaystyle=\frac{\left((-1)^{n}-1\right)n}{4\cos^{2}(\pi/(2n))},$

which, together with (26), leads to (25). ∎

## Acknowledgements

The author is grateful to Nobuaki Obata for useful discussions, in particular
for pointing out reference [7], and also to the anonymous referee for careful
reading the paper and useful comments, in particular for simplifying the proof
of Theorem 3.1.

## References

  * [1] E. T. Baskoro, N. Obata, Determining finite connected graphs along the quadratic embedding constants of paths, Electron. J. Graph Theory Appl. (EJGTA) 9 (2021), no. 2, 539–560.
  * [2] Zhenzhen Lou, Nobuaki Obata, Qiongxiang Huang, Quadratic Embedding Constants of Graph Joins, arXiv 2020.
  * [3] W. Młotkowski, N. Obata, On quadratic embedding constants of star product graphs, Hokkaido Math. J. 49 (2020), no. 1, 129–163.
  * [4] N. Obata, Quadratic embedding constants of wheel graphs, Interdiscip. Inform. Sci. 23 (2017), no. 2, 171–174.
  * [5] N. Obata, A. Y. Zakiyyah, Distance matrices and quadratic embedding of graphs, Electron. J. Graph Theory Appl. (EJGTA) 6 (2018), no. 1, 37–60.
  * [6] The On-Line Encyclopedia of Integer Sequences (OEIS), http://oeis.org/
  * [7] S. N. Ruzieh, D. L. Powers, The distance spectrum of the path $P_{n}$ and the first distance eigenvector of connected graphs, Linear and Multilinear Algebra, 28 (1990), 75–81.