[1,2,3,4]Ahmed M Salih

[1]Department of Population Health Sciences, University of Leicester,
University Rd, LE1 7RH, Leicester, UK 2]William Harvey Research Institute,
NIHR Barts Biomedical Research Centre, Queen Mary University of London,
Charterhouse Square, London, EC1M 6BQ, London, UK 3]Barts Heart Centre, St
Bartholomew’s Hospital, Barts Health NHS Trust, West Smithfield, London, EC1A
7BE, UK 4]Department of Computer Science, University of Zakho, Duhok road,
Zakho, Kurdistan, Iraq

# Explainable Artificial Intelligence and Multicollinearity : A Mini Review of
Current Approaches

<EMAIL_ADDRESS>*  [  [  [

###### Abstract

Explainable Artificial Intelligence (XAI) methods help to understand the
internal mechanism of machine learning models and how they reach a specific
decision or made a specific action. The list of informative features is one of
the most common output of XAI methods. Multicollinearity is one of the big
issue that should be considered when XAI generates the explanation in terms of
the most informative features in an AI system. No review has been dedicated to
investigate the current approaches to handle such significant issue. In this
paper, we provide a review of the current state-of-the-art approaches in
relation to the XAI in the context of recent advances in dealing with the
multicollinearity issue. To do so, we searched in three repositories that are:
Web of Science, Scopus and IEEE Xplore to find pertinent published papers.
After excluding irrelevant papers, seven papers were considered in the review.
In addition, we discuss the current XAI methods and their limitations in
dealing with the multicollinearity and suggest future directions..

###### keywords:

XAI, Multicollinearity, Machine learning

##  1 Introduction

Explainable Artificial Intelligence (XAI) emerged to uncover the vagueness
around complex models including deep learning and make them more
understandable from human point of view [1]. It is a set of tools, framework
and algorithms that is developed to interpret the predictions of the machine
learning models. It has shown massive success in different domains including
healthcare [2], genetic [3], education [4], finance [5], social science [6]
and ecology [7].
One of the most common outcome of XAI methods is the list of informative
features in the model when applied to tabular data. It shows what are the
features that significantly drive the model decision. In addition, it shows
whether the association of these features with the outcome positive, negative
or does not have effect at all. Other form of XAI outcome is the dependency
between a feature or group of features with the outcome. It shows whether the
association is linear or non-linear including monotonic.
However, XAI is not mature yet and still in the development stage which
necessitate to evaluate its outcomes. There are several concerns related to
understanding and interpreting the outcome of XAI methods include the impact
of one feature in the model on the outcome when the features are not
independent. One of the big issue in machine learning and XAI is presence of
multicollinearity. It is a phenomena where multiple features in the machine
learning models are highly correlated. Such issue affect the reliability of
the prediction and interpreting the results. This is because it is difficult
to determine the individual effect of a feature in the model on the outcome.
In real-life scenario and especially in healthcare and biology, the features
are usually correlated. XAI methods need to consider this phenomena when
providing list of most informative features and when they reveal the impact of
one individual feature toward the outcome.
This review aims to explore the advances and solutions related to issue of
multicollinearity in XAI methods. Moreover, it discussed some common XAI
methods and how they deal with the multicollinearity issue when they explain a
model.

##  2 XAI and Multicollinearity

On of the most common output of XAI methods is the list of informative
features which sort them in a descend order based on their influence on the
model prediction. For instance, if featureX is on the top of the list, it
means that feature has the most powerful impact on the prediction. This is
correct if the feature is independent from other features in the model.
However, if feature X is highly collinear with other features in the model,
the interpretation of the list of informative features is not realistic and
not reliable. Other form of XAI method is the dependency plot where it shows
the association of one or two features toward model output. It shows how
change in a feature led to change in the output. Again, this seems incorrect
if that feature is collinear with other features in the model. Below we
discuss most common XAI methods that provide list of informative features or
reveal the kind of association between a feature and the outcome. We do not
discuss in deep the technical details of each method, we rather discuss how
each method deals with the multicollinearity issue when it explains the model
prediction.

  1. 1.

SHapley Additive exPlanations (SHAP) is a mode-agnostic XAI based on game
theory to calculate the attribution of each feature in the model toward model
prediction [8]. There have been many publications that explained in details
how SHAP works which is outside the scope of the current review. However, what
we are interested in is the assumption behind features-dependency. In the
original version of SHAP, it assumes that the features are independent when it
calculates a score of each feature. For instance, if feature X and Z are
collinear and they are correlated with the outcome, only one of them get a
high SHAP score. This is because the second one does not improve the model
performance when it is added in the model. Accordingly, the SHAP score does
not really capture the real impact of the features toward the outcome when the
features are collinear. There have been many methods proposed to modify SHAP
in order to provide explanation and consider the multicollinearity
simultaneously [9, 10, 11, 12]. The proposed methods will be discussed more in
details in the following section.

  2. 2.

Local Interpretable Model-agnostic Explanations (LIME) is a local model-
agnostic XAI method. It approximates any model to explain an instance through
a local linear model. The outcome of LIME is the coefficient (weights) value
of the features generated by the local linear model. The interpretation of the
weights indicates that increasing or decreasing one unite in the feature
causes increasing or deceasing in the outcome by one unite while holding all
other features in the model constant. Such interpretation is correct when the
features are independent. However, in real life applications the features are
usually collinear. Accordingly, LIME explanation is not realistic as it does
not consider multicollinearity in its outcomes.

  3. 3.

Partial Dependence Plot (PDP) is a model-agnostic XAI method that reveals the
impact of one or two features on the outcome in machine learning models [13].
It shows whether the association between the features simple (e.g., linear),
monotonic or more complicated. One of the limitations of PDP is that it
assumes the features are independent when it generates the plots [14]. It is
kind of similar to interpreting the coefficient in a linear model because it
averages over the marginal distribution of other features when it generates
the plot for a specific feature. The explanation provided by PDP does not
reflect the interactions between the features and on the outcome.

  4. 4.

Accumulated Local Effects (ALE) [15] is similar to PDP which aims to examine
the association between one or two features with the outcome globally.
However, ALE is better in terms of handling the multicollinearity issue
because it focuses on the prediction change rather than on averaging the
features as the case in PDP. It divides the feature of interest into intervals
and then calculate the changes in the prediction in each interval. The plots
generated by ALE are more realistic and unbiased compared to PDP. However, the
interpretation of the plots assume that the changes happen in the prediction
for each interval while the instances value of other features are fixed.
Moreover, the presence of multicollinearity make it difficult to understand
the ALE plot and interpret it correctly [14].

  5. 5.

Anchor [16] is a local agnostic rule-based XAI method that aims to explain a
classification model for an individual. If the changes does not affect the
prediction, a rule anchors the prediction. Thereafter, these rules are
presented in if-then statement which is easy to understand. The method has
some limitations in terms of highly configurable, discretization and running
time. To decrease the running time, anchor uses reinforcement learning
alongside with graph search analysis. The anchors might be difficult to be
build accurately when the features are dependent because it is perturbation-
based.

##  3 Literature review

Search was conducted on 21st of April 2024 in the Web of Science, Scopus and
IEEE Xplore repositories. The search was specified to English papers without
restriction in the year of publication. The search was conducted using a query
that involves the key words and synonyms related to multicollinearity and XAI
methods (Table S1). The search aimed to find the key words in the abstract of
the papers.
Figure 1 shows the number of papers from each repositories and the process of
excluding papers. Any paper that did not use XAI dealing with
multicollinearity issue was excluded. There was a massive number of papers
when the search was conducted. However, after removing the duplicates,
excluding those did not deal with XAI and multicollinearity, seven papers left
to include in the current review.

Figure 1: Literature review search.

Table 1 lists the seven papers included in the review. The table shows whether
the method can be implemented as a global or local explanation. In addition,
it shows whether the proposed method specific to an XAI method or agnostic
which means can be applied to any XAI method.

Method | Global or Local | Specific or Agnostic
---|---|---
Modified Index Position (MIP) [17] | Global & Local | Agnostic
Extended Kernel SHAP [9] | Local | Specific to SHAP
Normalized Movement Rate (NMR) [18] | Global & Local | Agnostic
SHAP Cohort Refinement (SCR) [10] | Local | Specific to SHAP
Multi$-$collinearity Corrected (MCC) [11] | Global | Specific to SHAP
Conditional Subgroups (CS) [19] | Global | Agnostic
Conditional Inference Trees (CIT) [12] | Local | Specific to SHAP
Table 1: The proposed methods to handle the features-dependency issue in the
outcome of XAI.

The seven methods are discussed more in details below. The discussion is
focused on how it works, applied to any XAI method and whether its
implementation is publicly available in any coding language so the reader
could use it.

  1. 1.

Modified Index Position: MIP [17] was proposed to modify and enhance any XAI
method that does not consider multicollinearity when generates the
explanation. It can be applied to any XAI method both globally and locally.
The method works as post-hoc of XAI to consider features-dependency issue.
Once the model was trained and XAI was applied to generate the list of
significant features, then MIP modifies the outcomes of XAI to consider the
multicollinearity. It removes iteratively the top feature from the list,
retrain the model, apply XAI and generates the list of significant features
again. The hypothesis behind that is if two features are collinear and
correlated with the outcome, then once one of them removed from the model, the
other one will top the list. The faster the feature reach the top list when
every time one is removed, the more the feature is significant in the model.
They evaluated their method using Principal component analysis applied to the
features to generate new independent components. Their method shows that when
PCA was applied, the outcome of XAI more stable and less model-dependent. The
implementation of the MIP in Python is available at Github.

  2. 2.

Extended Kernel SHAP: The method was mainly proposed to modify the Kernel SHAP
method to consider the multicollinearity and explain the model locally at
individual level [9]. In the original Kernal SHAP method, it is assumed that
the features are independent and the conditional distribution can be replaced
by the marginal distribution. However, such assumption is not realistic in
real-life applications specifically in healthy-care which might lead to
incorrect explanation. Extended Kernel SHAP proposed four approaches to
estimate the conditional distribution instead of replacing it with the
marginal distribution. The proposed approaches are Gaussian copula
distribution, Gaussian distribution, Empirical conditional distribution and
the combination of the empirical approach and either the Gaussian or the
Gaussian copula. The user has the ability to chose a specific distribution
over others based on the distribution of the data. The method is a local
explanation and works only with SHAP. The implementation of the method in R is
available at Github.

  3. 3.

Normalized Movement Rate : XAI methods are usually model-dependent which means
each model might provide different explanation even if the accuracy is
relatively similar [20]. One of the main factor that causes this discrepancy
is the multicollinearity because each model deals with this issue differently.
The question is when applying several models which one of the explanation to
consider given that the accuracy of the models is similar. NMR [18] was
proposed to assess the stability of the explanation in presence of
multicollinearity. It works by iteratively removing the top feature from the
outcome of XAI, then train the model again and apply XAI. Thereafter, it
compares whether the left features changed their positions in the XAI outcome
compared to previous list. The less the features change their positions, the
better the model against the collinearity. It calculates a value between zero
and one which represents the changes of the positions of the features when
every time the top one is removed. NMR value close to zero means that the
features do not change their positions a lot when the top one is removed from
the model and the XAI is more stable. On contrary, NMR value close to one
means that when the top feature is removed from the mode, the rest of the
features change their positions massively which indicates that the model and
the XAI outcome is not stable or robust against the multicollinearity. NMR can
be applied to any XAI both globally and locally. It does not generate an
explanation with considering multicollinearity issue, it rather help to chose
a more stable model against features-dependency issue. The implementation of
the NMR in Python is available at Github.

  4. 4.

SHAP Cohort Refinement: SCR [10] is another method was proposed to deal with
the limitation of the original version of SHAP and consider the
multicollinearity in the explanation locally for a single subject. In order to
deal with the issue, it creates a new cohort that is similar to the instance
need to be explained. To do so, it combines many data points that are similar
to the instance that need to be explained. Measuring the similarity depends on
the kind of the data. If the data are categorical, then SCR uses the frequency
of each value to find similar instances. On the other hand, if the features
are continues variables, then it uses distance-based methods. Once it creates
the cohort, then it applies SHAP to explain the target instance. Accordingly,
the method eliminates or mitigates the impact of the multicollinearity as the
explanation of the instance was explained in reference to the new similar
cohort. The implementation of the SCR in Python is available at Github.

  5. 5.

Multi$-$Collinearity Corrected: Another approach was proposed to handle the
multicollinearity issue in the explanation provided by SHAP [11]. The main
idea behind MCC is that they remove the impact of dependency between the
features before calculating the SHAP score. To do so, they proposed to add an
Adjustment Factor (AF) for each feature correlated with the feature of
interest while removing or randomize the feature that SHAP score is calculated
for. The role of the AF is to decrease or eliminate the correlation between
the feature of interest with the rest of features. This is validated by
calculating the covariance between the feature of interest with the other
features plus the AF. MCC was implemented in the approximate SHAP version as
the original SHAP is computationally expensive. They implemented the method on
several datasets using several models.

  6. 6.

Conditional Subgroups: CS [19] was proposed to handle the issue of
multicollinearity using conditional subgroup with permutation feature
importance and partial dependency plot. The main idea behind the proposed
method is that creating groups in a way that the feature of interest is less
dependent on all other features in the all subgroups. Decision tree is used to
split the data into groups in a way that the distribution of the feature of
interest more homogeneous in one group and more heterogeneous in the rest of
groups. It is implemented with PDP which lead to a different interpretation of
the original version of PDP. In the modified version of PDP, the change in the
outcome is reflected by the change of the feature of the interest given that
the variation in all other features based on the join distribution. The
implementation of the SC in R is available at Github.

  7. 7.

Conditional Inference Trees: Extended Kernel SHAP [9] was proposed to extend
the original version of SHAP to consider the dependency among the features for
continues variables by estimating the dependency distribution. However, the
method was limited to only continues features while in real-life scenario a
model might involve more than one type of features. CIT [12] was proposed to
extend the SHAP value method aiming to solve the dependency among the features
when the model involves mixture of different types of features including
continuous, discrete, ordinal and categorical. The authors followed similar
approach to [9] to handle the multicollinearity issue by estimating the
conditional distribution. However, instead of using the marginal distribution,
they used CIT to estimate the conditional distribution. CIT is known to be
better to handle categorical variables and modelling simple and complex
collinearity structure. The proposed method is available in R as additional
method to the shapr package Github.

##  4 Open issue and future direction

Our review shows that although XAI methods are applied extensively in variety
of research area including sensitive domain where misinterpreting is sever,
multicollinearity issue is not explored and investigated adequately in the
literature. There is no XAI method that by its nature mitigate the impact of
such important issue. The current available XAI methods and their modified
versions are either limited to a specific XAI method (e.g., SHAP) or they are
limited to local explanation. Moreover, the methods based on the conditional
distribution depends highly on the efficiency of the conditional sampler which
is challenging in high dimension [21]. Accordingly, more research is required
on sampling methods with XAI and presence of multicollinearity. Conditional
probability could be one of the ways to estimate the impact of a specific
feature given that the other features have specific values. In addition, it
might be difficult to estimate the impact of a feature on the outcome by one
single score due to the interaction between the dependent-features. Possible
way is to estimate a distribution using Bayesian models which reflect the
impact of a feature given that different values for different correlated
features. Moreover, current plots of XAI to explain the models either locally
or globally are misleading because they do not reflect the complexity
interaction between the features and they rather give impression of that the
features are independent. Accordingly, new plots are required to embed and
reflect the interaction between the features and their effect on the outcome.
This is especially significant when the models involves more than one type of
features and they are highly correlated.

## References

  *   * Angelov et al. [2021] Angelov, P.P., Soares, E.A., Jiang, R., Arnold, N.I., Atkinson, P.M.: Explainable artificial intelligence: an analytical review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 11(5), 1424 (2021)
  * Salih et al. [2023] Salih, A., Boscolo Galazzo, I., Gkontra, P., Lee, A.M., Lekadir, K., Raisi-Estabragh, Z., Petersen, S.E.: Explainable artificial intelligence and cardiac imaging: toward more interpretable models. Circulation: Cardiovascular Imaging 16(4), 014519 (2023)
  * Novakovsky et al. [2023] Novakovsky, G., Dexter, N., Libbrecht, M.W., Wasserman, W.W., Mostafavi, S.: Obtaining genetics insights from deep learning via explainable artificial intelligence. Nature Reviews Genetics 24(2), 125–137 (2023)
  * Chaushi et al. [2023] Chaushi, B.A., Selimi, B., Chaushi, A., Apostolova, M.: Explainable artificial intelligence in education: A comprehensive review. In: World Conference on Explainable Artificial Intelligence, pp. 48–71 (2023). Springer
  * Weber et al. [2023] Weber, P., Carl, K.V., Hinz, O.: Applications of explainable artificial intelligence in finance—a systematic review of finance, information systems, and computer science literature. Management Review Quarterly, 1–41 (2023)
  * Johs et al. [2022] Johs, A.J., Agosto, D.E., Weber, R.O.: Explainable artificial intelligence and social science: Further insights for qualitative investigation. Applied AI Letters 3(1), 64 (2022)
  * Ryo et al. [2021] Ryo, M., Angelov, B., Mammola, S., Kass, J.M., Benito, B.M., Hartig, F.: Explainable artificial intelligence enhances the ecological interpretability of black-box species distribution models. Ecography 44(2), 199–205 (2021)
  * Lundberg and Lee [2017] Lundberg, S.M., Lee, S.-I.: A unified approach to interpreting model predictions. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems 30, pp. 4765–4774. Curran Associates, Inc., ??? (2017)
  * Aas et al. [2021] Aas, K., Jullum, M., Løland, A.: Explaining individual predictions when features are dependent: More accurate approximations to shapley values. Artificial Intelligence 298, 103502 (2021)
  * Mase et al. [2019] Mase, M., Owen, A.B., Seiler, B.: Explaining black box decisions by shapley cohort refinement. arXiv preprint arXiv:1911.00467 (2019)
  * Basu and Maji [2022] Basu, I., Maji, S.: Multicollinearity correction and combined feature effect in shapley values. In: Australasian Joint Conference on Artificial Intelligence, pp. 79–90 (2022). Springer
  * Redelmeier et al. [2020] Redelmeier, A., Jullum, M., Aas, K.: Explaining predictive models with mixed features using shapley values and conditional inference trees. In: Machine Learning and Knowledge Extraction: 4th IFIP TC 5, TC 12, WG 8.4, WG 8.9, WG 12.9 International Cross-Domain Conference, CD-MAKE 2020, Dublin, Ireland, August 25–28, 2020, Proceedings 4, pp. 117–137 (2020). Springer
  * Friedman [2001] Friedman, J.H.: Greedy function approximation: a gradient boosting machine. Annals of statistics, 1189–1232 (2001)
  * Molnar [2018] Molnar, C.: A guide for making black box models explainable. URL: https://christophm. github. io/interpretable-ml-book 2(3), 10 (2018)
  * Apley and Zhu [2020] Apley, D.W., Zhu, J.: Visualizing the effects of predictor variables in black box supervised learning models. Journal of the Royal Statistical Society Series B: Statistical Methodology 82(4), 1059–1086 (2020)
  * Ribeiro et al. [2018] Ribeiro, M.T., Singh, S., Guestrin, C.: Anchors: High-precision model-agnostic explanations. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32 (2018)
  * Salih et al. [2024] Salih, A.M., Galazzo, I.B., Raisi-Estabragh, Z., Petersen, S.E., Menegaz, G., Radeva, P.: Characterizing the contribution of dependent features in xai methods. IEEE Journal of Biomedical and Health Informatics (2024)
  * Salih et al. [2022] Salih, A., Galazzo, I.B., Cruciani, F., Brusini, L., Radeva, P.: Investigating explainable artificial intelligence for mri-based classification of dementia: a new stability criterion for explainable methods. In: 2022 IEEE International Conference on Image Processing (ICIP), pp. 4003–4007 (2022). IEEE
  * Molnar et al. [2023] Molnar, C., König, G., Bischl, B., Casalicchio, G.: Model-agnostic feature importance and effects with dependent features: a conditional subgroup approach. Data Mining and Knowledge Discovery, 1–39 (2023)
  * Salih et al. [2023] Salih, A., Raisi-Estabragh, Z., Galazzo, I.B., Radeva, P., Petersen, S.E., Menegaz, G., Lekadir, K.: Commentary on explainable artificial intelligence methods: Shap and lime. arXiv preprint arXiv:2305.02012 (2023)
  * Molnar et al. [2020] Molnar, C., König, G., Herbinger, J., Freiesleben, T., Dandl, S., Scholbeck, C.A., Casalicchio, G., Grosse-Wentrup, M., Bischl, B.: General pitfalls of model-agnostic interpretation methods for machine learning models. In: International Workshop on Extending Explainable AI Beyond Deep Models and Classifiers, pp. 39–68 (2020). Springer


# Walk entropy and walk-regularity

Kyle Kloster111Department of Computer Science, NC State University, Raleigh,
NC 27695, USA. E-mail<EMAIL_ADDRESS>The work of this
author was supported in part by the Gordon & Betty Moore Foundation’s Data-
Driven Discovery Initiative through Grant GBMF4560 to Blair D. Sullivan.
Daniel Král’222Mathematics Institute, DIMAP and Department of Computer
Science, University of Warwick, Coventry CV4 7AL, UK. E-mail:
<EMAIL_ADDRESS>The work of this author was supported by the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No 648509). This publication reflects
only its authors’ view; the European Research Council Executive Agency is not
responsible for any use that may be made of the information it contains. Blair
D. Sullivan††footnotemark:

###### Abstract

A graph is said to be walk-regular if, for each $\ell\geq 1$, every vertex is
contained in the same number of closed walks of length $\ell$. We construct a
$24$-vertex graph $H_{4}$ that is not walk-regular yet has maximized walk
entropy, $S^{V}(H_{4},\beta)=\log 24$, for some $\beta>0$. This graph is a
counterexample to a conjecture of Benzi [Linear Algebra Appl. 443 (2014),
395–399, Conjecture 3.1]. We also show that there exist infinitely many
temperatures $\beta_{0}>0$ so that $S^{V}(G,\beta_{0})=\log n_{G}$ if and only
if a graph $G$ is walk-regular.

MSC: 05C50

Keywords: graph entropy; walk-regularity; subgraph centrality; matrix
exponential

##  1 Introduction

We study the interplay between the structural property of graphs called walk-
regularity and the algebraic property called walk entropy. A simple graph $G$
is walk-regular [8] if every vertex of $G$ is contained in the same number of
closed walks of length $\ell$ for every $\ell\in{\mathbb{N}}$. Observe that a
graph $G$ is walk-regular if and only if for every $\ell\in{\mathbb{N}}$, all
the diagonal entries of the power $\boldsymbol{A}^{\ell}$ of the adjacency
matrix $\boldsymbol{A}$ of $G$ are the same. Also note that if a graph $G$ is
walk-regular, then it is necessarily degree-regular, i.e., every vertex of $G$
has the same degree.

Estrada et al. [5] initiated the study of the relationship between walk-
regularity and an algebraic parameter of a graph called the walk entropy. The
walk entropy of a graph $G$ at the temperature $\beta\geq 0$ is defined as

$S^{V}(G,\beta)=-\sum_{i=1}^{n_{G}}\frac{\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{ii}}{\mbox{Tr}\;\mbox{e}^{\beta\boldsymbol{A}}}\log\frac{\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{ii}}{\mbox{Tr}\;\mbox{e}^{\beta\boldsymbol{A}}}\;\mbox{,}$

where $n_{G}$ denotes the number of vertices of $G$ (in general, we use
$n_{H}$ for the number of vertices of a graph $H$ throughout the paper). In
other words, the walk entropy is the entropy associated with the probability
distribution on the vertex set $V(G)$ that is linearly proportional to the
subgraph centrality of the vertices. We note that any probability distribution
on $V(G)$ gives rise to a corresponding notion of graph entropy; Dehmer [3]
called such distributions _information functionals_ , and introduced this more
general class of graph entropies.

The _subgraph centrality_ of the $i$-th vertex of a graph $G$ [7] is equal to
$\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{ii}$, the corresponding diagonal
entry of $\mbox{e}^{\beta\boldsymbol{A}}$. Note that the walk entropy
$S^{V}(G,\beta)\in[0,\log n_{G}]$ and $S^{V}(G,\beta)=\log n_{G}$ if and only
if all the diagonal entries of $\mbox{e}^{\beta\boldsymbol{A}}$ are the same.
That is, walk entropy is maximized precisely when all the vertices have the
same subgraph centrality.

It is easy to see that if a graph $G$ is walk-regular, then its walk entropy
$S^{V}(G,\beta)$ is equal to $\log n_{G}$ for every $\beta\geq 0$. Estrada et
al. [5] conjectured that the converse is also true.

######  Conjecture 1 (Estrada et al. [5, Conjecture 1]).

A graph $G$ is walk-regular if and only if $S^{V}(G,\beta)=\log n_{G}$ for all
$\beta\geq 0$.

The conjecture was proven by Benzi in the following stronger form.

######  Theorem 1 (Benzi [1, Theorem 2.2]).

Let $I$ be any set of real numbers containing an accumulation point. If a
graph $G$ satisfies $S^{V}(G,\beta)=\log n_{G}$ for all $\beta\in I$, then $G$
is walk-regular.

Benzi also proposed the following strengthening of his result.

######  Conjecture 2 (Benzi [1, Conjecture 3.1]).

A graph $G$ is walk-regular if and only if there exists $\beta>0$ such that
$S^{V}(G,\beta)=\log n_{G}$.

From the contrapositive, Estrada et al. [5, 6] proposed that non–degree-
regular graphs cannot have maximum walk entropy.

######  Conjecture 3 (Estrada et al. [6, Conjecture 1.2]).

Let $G$ be a non–degree-regular graph. Then $S^{V}(G,\beta)<\log n_{G}$ for
every $\beta>0$.

Estrada et al. [6] attempted to prove Conjectures 2 and 3, but their argument
contains a flaw. In Section 2 we show that Conjectures 2 and 3 are false by
presenting a 24-vertex graph, which we denote $H_{4}$, that is not walk-
regular yet attains $S^{V}(H_{4},\beta)=\log 24$ for some $\beta>0$. The graph
$H_{4}$ contains vertices of degree four and five, i.e., it is not even
degree-regular, which resolves the question, mentioned in the concluding
remarks in [1], of whether degree-regularity is implied by the existence of a
$\beta$ that maximizes walk entropy. On the positive side, we show that there
exist infinitely many temperatures $\beta_{0}>0$ such that a graph $G$ is
walk-regular if and only if $S^{V}(G,\beta_{0})=\log n_{G}$ (Corollary 4),
i.e., there are temperatures that properly classify walk-regularity.

##  2 Non–degree-regular graph maximizing walk entropy

In this section, we present a counterexample to Conjectures 2 and 3. We start
by presenting a closed formula for the diagonal entries of the exponential of
the adjacency matrix of a graph. Let $G$ be a graph and $\boldsymbol{A}$ its
adjacency matrix. Further, let $\lambda_{1},\ldots,\lambda_{n_{G}}$ be the
eigenvalues of $\boldsymbol{A}$ and $\textbf{u}_{1},\ldots,\textbf{u}_{n_{G}}$
an orthonormal basis formed by the eigenvectors of $\boldsymbol{A}$. It
follows that

$\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{ii}=\sum_{k=1}^{n_{G}}\textbf{u}_{k,i}^{2}\cdot\mbox{e}^{\beta\lambda_{k}}$
(1)

for every $i=1,\ldots,n_{G}$. In particular, each diagonal entry of
$\mbox{e}^{\beta\boldsymbol{A}}$ is an analytic function of $\beta$, which is
a linear combination of at most $n_{G}$ exponential functions.

We next present a construction of graphs $H_{m}$ parameterized by a positive
integer $m\in{\mathbb{N}}$. The graph $H_{m}$ is obtained from $m$ isolated
vertices and $m+1$ cliques of order $m$ by including a perfect matching
between the $m$ isolated vertices and each of the $m+1$ cliques. The graph
$H_{m}$ has $m+(m+1)m=m^{2}+2m$ vertices; $m$ vertices have degree $m+1$ and
the remaining $m^{2}+m$ vertices have degree $m$. We are convinced that
$H_{m}$ is a counterexample to Conjecture 2 for every $m\geq 4$; however, we
will here analyze the case $m=4$ only. The graph $H_{4}$ and its adjacency
matrix are presented in Figure 1.

$\boldsymbol{A}_{K_{4}}=\left(\begin{array}[]{cccc}0&1&1&1\\\ 1&0&1&1\\\
1&1&0&1\\\ 1&1&1&0\end{array}\right)$,
$\boldsymbol{I}_{4}=\left(\begin{array}[]{cccc}1&0&0&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\end{array}\right)$,
$\boldsymbol{A}_{H_{4}}=\left(\begin{array}[]{cccccc}0&\boldsymbol{I}_{4}&\boldsymbol{I}_{4}&\boldsymbol{I}_{4}&\boldsymbol{I}_{4}&\boldsymbol{I}_{4}\\\
\boldsymbol{I}_{4}&\boldsymbol{A}_{K_{4}}&0&0&0&0\\\
\boldsymbol{I}_{4}&0&\boldsymbol{A}_{K_{4}}&0&0&0\\\
\boldsymbol{I}_{4}&0&0&\boldsymbol{A}_{K_{4}}&0&0\\\
\boldsymbol{I}_{4}&0&0&0&\boldsymbol{A}_{K_{4}}&0\\\
\boldsymbol{I}_{4}&0&0&0&0&\boldsymbol{A}_{K_{4}}\end{array}\right)$

Figure 1: The graph $H_{4}$ and its adjacency matrix $\boldsymbol{A}_{H_{4}}$.

######  Theorem 2.

There exists $\beta>0$ such that $S^{V}(H_{4},\beta)=\log 24$.

###### Proof.

Let $\boldsymbol{A}$ be the adjacency matrix of the graph $H_{4}$. The matrix
$\boldsymbol{A}$ has six different eigenvalues, which are given with
corresponding eigenvectors in Table 1. Note that the vectors given in Table 1
are not normalized to be unit and orthogonal. We will show that there exists
$\beta>0$ such that all the diagonal entries of the matrix
$\mbox{e}^{\beta\boldsymbol{A}}$ are the same, which yields the statement of
the theorem.

$\begin{array}[]{cc}\mbox{Eigenvalue}&\mbox{ \hskip 178.0pt Eigenvector \hskip
178.0pt}\\\ \end{array}$

$\begin{array}[]{c@{\hskip
0.05in}lllllllr}\hline\cr\hline\cr\vspace{2pt}\frac{3+\sqrt{29}}{2}\approx
4.193\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{3+\sqrt{29}},\frac{10}{3+\sqrt{29}},\frac{10}{3+\sqrt{29}},\frac{10}{3+\sqrt{29}},&1,1,1,1,&1,1,1,1,&1,1,1,1,&1,1,1,1,&1,1,1,1&\Big{)}\\\
\vspace{2pt}\par 3\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,1,1,1,&-1,-1,-1,-1,&0,0,0,0,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}3\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,1,1,1,&0,0,0,0,&-1,-1,-1,-1,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}3\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,1,1,1,&0,0,0,0,&0,0,0,0,&-1,-1,-1,-1,&0,0,0,0&\Big{)}\\\
\vspace{2pt}3\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,1,1,1,&0,0,0,0,&0,0,0,0,&0,0,0,0,&-1,-1,-1,-1&\Big{)}\\\
\vspace{2pt}\par\frac{-1+\sqrt{21}}{2}\approx 1.791\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{-1+\sqrt{21}},\frac{-10}{-1+\sqrt{21}},0,0,&1,-1,0,0,&1,-1,0,0,&1,-1,0,0,&1,-1,0,0,&1,-1,0,0&\Big{)}\\\
\vspace{2pt}\frac{-1+\sqrt{21}}{2}\approx 1.791\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{-1+\sqrt{21}},0,\frac{-10}{-1+\sqrt{21}},0,&1,0,-1,0,&1,0,-1,0,&1,0,-1,0,&1,0,-1,0,&1,0,-1,0&\Big{)}\\\
\vspace{2pt}\frac{-1+\sqrt{21}}{2}\approx 1.791\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{-1+\sqrt{21}},0,0,\frac{-10}{-1+\sqrt{21}},&1,0,0,-1,&1,0,0,-1,&1,0,0,-1,&1,0,0,-1,&1,0,0,-1&\Big{)}\\\
\vspace{2pt}\par-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,-1,0,0,&-1,1,0,0,&0,0,0,0,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,-1,0,&-1,0,1,0,&0,0,0,0,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,0,-1,&-1,0,0,1,&0,0,0,0,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,-1,0,0,&0,0,0,0,&-1,1,0,0,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,-1,0,&0,0,0,0,&-1,0,1,0,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,0,-1,&0,0,0,0,&-1,0,0,1,&0,0,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,-1,0,0,&0,0,0,0,&0,0,0,0,&-1,1,0,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,-1,0,&0,0,0,0,&0,0,0,0,&-1,0,1,0,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,0,-1,&0,0,0,0,&0,0,0,0,&-1,0,0,1,&0,0,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,-1,0,0,&0,0,0,0,&0,0,0,0,&0,0,0,0,&-1,1,0,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,-1,0,&0,0,0,0,&0,0,0,0,&0,0,0,0,&-1,0,1,0&\Big{)}\\\
\vspace{2pt}-1\hfil\hskip 3.61371pt&\Big{(}\hskip
3.0pt0,0,0,0,&1,0,0,-1,&0,0,0,0,&0,0,0,0,&0,0,0,0,&-1,0,0,1&\Big{)}\\\
\vspace{2pt}\par\frac{3-\sqrt{29}}{2}\approx-1.193\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{3-\sqrt{29}},\frac{10}{3-\sqrt{29}},\frac{10}{3-\sqrt{29}},\frac{10}{3-\sqrt{29}},&1,1,1,1,&1,1,1,1,&1,1,1,1,&1,1,1,1,&1,1,1,1&\Big{)}\\\
\vspace{2pt}\par\frac{-1-\sqrt{21}}{2}\approx-2.791\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{-1-\sqrt{21}},\frac{-10}{-1-\sqrt{21}},0,0,&1,-1,0,0,&1,-1,0,0,&1,-1,0,0,&1,-1,0,0,&1,-1,0,0&\Big{)}\\\
\vspace{2pt}\frac{-1-\sqrt{21}}{2}\approx-2.791\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{-1-\sqrt{21}},0,\frac{-10}{-1-\sqrt{21}},0,&1,0,-1,0,&1,0,-1,0,&1,0,-1,0,&1,0,-1,0,&1,0,-1,0&\Big{)}\\\
\vspace{2pt}\frac{-1-\sqrt{21}}{2}\approx-2.791\hfil\hskip
3.61371pt&\Big{(}\hskip
3.0pt\frac{10}{-1-\sqrt{21}},0,0,\frac{-10}{-1-\sqrt{21}},&1,0,0,-1,&1,0,0,-1,&1,0,0,-1,&1,0,0,-1,&1,0,0,-1&\Big{)}\par\end{array}$

Table 1: The eigenvalues and the corresponding eigenvectors of the adjacency
matrix of the graph $H_{4}$.

Let $f_{1}(\beta)=\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{11}$ and
$f_{2}(\beta)=\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{55}$. Note that
$\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{ii}=f_{1}(\beta)$ for
$i=1,\ldots,4$ and
$\left[\mbox{e}^{\beta\boldsymbol{A}}\right]_{ii}=f_{2}(\beta)$ for
$i=5,\ldots,24$. Observe that the $k$-th derivative of $f_{i}(\beta)$ for
$\beta=0$ is equal to the corresponding diagonal entry of
$\boldsymbol{A}^{k}$. In particular, $f_{1}(0)=f_{2}(0)=1$,
$f^{\prime}_{1}(0)=f^{\prime}_{2}(0)=0$, $f^{\prime\prime}_{1}(0)=5$ and
$f^{\prime\prime}_{2}(0)=4$. This implies that there exists $\varepsilon>0$
such that $f_{1}(\beta)>f_{2}(\beta)$ for all $\beta\in(0,\varepsilon)$. On
the other hand, it holds that $f_{1}(1)<f_{2}(1)$; a direct computation shows
that $f_{1}(1)\approx 6.481$ and $f_{2}(1)\approx 7.175$. Since both
$f_{1}(\beta)$ and $f_{2}(\beta)$ are continuous functions of $\beta$ on the
interval $[0,1]$, there exists $\beta\in(0,1)$ such that
$f_{1}(\beta)=f_{2}(\beta)$, i.e., such that all the diagonal entries of
$\mbox{e}^{\beta\boldsymbol{A}}$ are the same. ∎

A numerical computation yields that the value of $\beta$ from the proof of
Theorem 2 is approximately $0.499$. There also exists $\beta>1$ such that
$f_{1}(\beta)=f_{2}(\beta)$. Indeed, assume that $\lambda_{1}$ is the largest
eigenvalue of the adjacency matrix of the graph $H_{4}$ and let
$\textbf{u}_{1}$ be the corresponding unit eigenvector. Since
$\textbf{u}_{1,1}^{2}>\textbf{u}_{1,5}^{2}$, it follows from (1) that there
exists $\beta_{0}>0$ such that $f_{1}(\beta)>f_{2}(\beta)$ for all
$\beta\geq\beta_{0}$. Since $f_{1}(1)<f_{2}(1)$, we get that there exists
$\beta\in(1,\beta_{0})$ such that $f_{1}(\beta)=f_{2}(\beta)$; a numerical
computation shows that the value of such $\beta$ is approximately $1.912$. We
remark that each of the graphs $H_{m}$ with $m\in{\mathbb{N}}$ greater than 1,
has six different eigenvalues with the structure of corresponding eigenvectors
similar to that of $H_{4}$.

We would like to conclude with an intuitive explanation behind the
construction of the graph $H_{m}$. The graph $H_{m}$ has vertices of degree
$m$ and $m+1$, and any pair of vertices of the same degree can be mapped to
each other by an automorphism of $H_{m}$. The values of the diagonal entries
of $\mbox{e}^{\beta\boldsymbol{A}}$ are controlled by the diagonal entries of
$\boldsymbol{A}^{2}$ for $\beta$ close to zero, by the diagonal entries of
$\boldsymbol{A}^{3}$ for larger (but still small) values of $\beta$, then by
the diagonal entries of $\boldsymbol{A}^{4}$, etc. As $k$ grows, the diagonal
of $\boldsymbol{A}^{k}$ becomes proportional to the Perron-Frobenius
eigenvector of $\boldsymbol{A}$. Hence, the diagonal entries of
$\mbox{e}^{\beta\boldsymbol{A}}$ are proportional to the degrees of the
corresponding vertices for the first regime of $\beta$, and to the eigenvector
centrality of the vertices for $\beta$ in the third regime (for a precise
analysis, see [2]). In the graph $H_{m}$, the vertex degrees and Perron-
Frobenius eigenvector values produce the same ordering on the vertices. On the
other hand, the diagonal entries of $\mbox{e}^{\beta\boldsymbol{A}}$
corresponding to the vertices of degree $m$ become larger than those
corresponding to the vertices of degree $m+1$ in the middle regime of $\beta$,
since the vertices of degree $m$ are contained in many triangles and cycles of
length four. This explains the behavior of the functions $f_{1}$ and $f_{2}$
that we have observed in the proof of Theorem 2.

##  3 Temperatures classifying walk-regularity

We start by observing that a graph $G$ achieves the maximum walk entropy for
at most finitely many temperatures unless $G$ is walk-regular.

######  Theorem 3.

If a graph $G$ is not walk-regular, then there are only finitely many
$\beta>0$ such that $S^{V}(G,\beta)=\log n_{G}$.

###### Proof.

We proceed by contradiction. Suppose that there exists a graph $G$ that is not
walk-regular but the set $I$ of $\beta\geq 0$ such that $S^{V}(G,\beta)=\log
n_{G}$ is infinite. Since the diagonal entries of
$\mbox{e}^{\beta\boldsymbol{A}}$ are continuous functions of $\beta$ bounded
away from zero, it follows that $S^{V}(G,\beta)$ is continuous and the set $I$
is closed. Let $\boldsymbol{A}$ be the adjacency matrix of $G$,
$\lambda_{1},\ldots,\lambda_{k}$ all distinct eigenvalues of $\boldsymbol{A}$,
and $f_{i}(\beta)$ the $i$-th diagonal entry of
$\mbox{e}^{\beta\boldsymbol{A}}$, $i=1,\ldots,n_{G}$. We can assume that
$\lambda_{1}>\cdots>\lambda_{k}$. By (1), there exist non-negative reals
$a_{ij}$, $i=1,\ldots,n_{G}$ and $j=1,\ldots,k$ such that

$f_{i}(\beta)=\sum_{j=1}^{k}a_{ij}\cdot\mbox{e}^{\beta\lambda_{j}}$ (2)

for every $i=1,\ldots,n_{G}$ and $\beta\geq 0$. If
$f_{1}(\beta)=\cdots=f_{n_{G}}(\beta)$ for all $\beta>0$, $G$ would be walk-
regular by Theorem 1. Hence, $f_{i}\not=f_{i^{\prime}}$ for some
$i\not=i^{\prime}$. By symmetry, we can assume that $f_{1}\not=f_{2}$.

Let $j$ be the smallest integer such that $a_{1j}\not=a_{2j}$. We can assume
by symmetry that $a_{1j}>a_{2j}$, which implies that

$\lim_{\beta\to\infty}\left(f_{1}(\beta)-f_{2}(\beta)\right)=\infty\;\mbox{.}$

It follows that there exists $\beta_{0}$ such that
$f_{1}(\beta)\not=f_{2}(\beta)$ for all $\beta\geq\beta_{0}$, i.e., the set
$I$ is a subset of the interval $[0,\beta_{0})$. Since the set $I$ is
infinite, it has an accumulation point, which implies that $G$ is walk-regular
by Theorem 1, contrary to our original assumption. ∎

The next corollary immediately follows from Theorem 3.

######  Corollary 4.

There exists $\beta_{0}>0$ such that the following holds: a graph $G$ is walk-
regular if and only if $S^{V}(G,\beta_{0})=\log n_{G}$.

###### Proof.

Let $X$ be the set of all $\beta>0$ such that there exists a graph $G$ that is
not walk-regular and $S^{V}(G,\beta)=\log n_{G}$. Since there are only
finitely many such $\beta$ for each non–walk-regular graph $G$ by Theorem 3,
the set $X$ is countable. Hence, there exists $\beta_{0}\in(0,\infty)\setminus
X$ and any such $\beta_{0}$ has the property claimed in the statement of the
corollary. ∎

##  4 Concluding remarks

Corollary 4 shows that there are temperatures $\beta_{0}>0$ such that, for any
graph $G$, the graph $G$ is walk-regular if and only if its walk entropy for
$\beta_{0}$ is $\log n_{G}$. Unfortunately, we were not able to explicitly
find any such $\beta_{0}$, and so it remains an open problem to identify a
value $\beta_{0}$ with this property. It could be the case that $\beta_{0}=1$
is such a value of interest, as conjectured by Estrada [4].

######  Conjecture 4 (Estrada [4], Conjecture 3).

A graph $G$ is walk-regular if and only if $S^{V}(G,1)=\log n_{G}$.

It could even be the case that for every non–walk-regular $G$, the walk
entropy $S^{V}(G,\beta)$ is not maximized at any positive, rational value
$\beta_{0}$.

######  Conjecture 5.

A graph $G$ is walk-regular if and only if there exists a rational $\beta>0$
such that $S^{V}(G,\beta)=\log n_{G}$.

Theorem 3 asserts that if a graph $G$ is not walk-regular, then the set of
temperatures $\beta$ such that $S^{V}(G,\beta)=\log n_{G}$ is finite. We
believe that it is possible to bound the size of this set in terms of the
number of vertices of $G$ as follows.

######  Conjecture 6.

If a graph $G$ is not walk-regular, then there are at most $n_{G}-1$ values
$\beta>0$ such that $S^{V}(G,\beta)=\log n_{G}$.

## Acknowledgments

The authors would like to thank Eric Horton for useful discussions on non-
walk-regular graphs that maximize other notions of graph entropy.

## References

  * [1] M. Benzi: A note on walk entropies in graphs, Linear Algebra Appl. 443 (2014), 395–399.
  * [2] M. Benzi, C. Klymko: On the limiting behavior of parameter-dependent network centrality measures, SIAM J. Matrix Anal. Appl. 36.2 (2015), 686–706.
  * [3] M. Dehmer: Information processing in complex networks: Graph entropy and information functionals, Appl. Math. Comput. 201 (2008), 82–94.
  * [4] E. Estrada: About the discriminant power of the subgraph centrality and other centrality measures (working paper), preprint available as arXiv:1305.6836.
  * [5] E. Estrada, J. A. de la Peña, N. Hatano: Walk entropies in graphs, Linear Algebra Appl. 443 (2014), 235–-244.
  * [6] E. Estrada, J. A. de la Peña: Maximum walk entropy implies walk regularity, Linear Algebra Appl. 448 (2014), 542–547.
  * [7] E. Estrada, J. A. Rodríguez-Velázquez: Subgraph centrality in complex networks, Phys. Rev. E71 (2005), 056103.
  * [8] C. Godsil, G. Royle: Algebraic graph theory, Grad. Texts in Math., vol. 207, Springer-Verlag, 2001.