# Evaluating the Impact of Knowledge Graph Context on Entity Disambiguation
Models

Isaiah Onando Mulang<EMAIL_ADDRESS>Fraunhofer IAIS
and Zerotha Research, Germany ,  Kuldeep Singh<EMAIL_ADDRESS>Cerence GmbH and Zerotha Research Germany ,  Chaitali Prabhu  s6chprab@uni-
bonn.de University of Bonn Germany ,  Abhishek Nadgeri
<EMAIL_ADDRESS>Zerotha Research, India ,  Johannes Hoffart
<EMAIL_ADDRESS>Goldman Sachs, Germany and  Jens Lehmann
<EMAIL_ADDRESS>University of Bonn, Germany

(2020; 2020)

###### Abstract.

Pretrained Transformer models have emerged as state-of-the-art approaches that
learn contextual information from text to improve the performance of several
NLP tasks. These models, albeit powerful, still require specialized knowledge
in specific scenarios. In this paper, we argue that context derived from a
knowledge graph (in our case: Wikidata) provides enough signals to inform
pretrained transformer models and improve their performance for named entity
disambiguation (NED) on Wikidata KG. We further hypothesize that our proposed
KG context can be standardized for Wikipedia, and we evaluate the impact of KG
context on state-of-the-art NED model for the Wikipedia knowledge base. Our
empirical results validate that the proposed KG context can be generalized
(for Wikipedia), and providing KG context in transformer architectures
considerably outperforms the existing baselines, including the vanilla
transformer models.

††copyright: acmcopyright††journalyear: 2020††copyright:
rightsretained††journalyear: 2020††conference: Proceedings of the 29th ACM
International Conference on Information and Knowledge Management; October
19–23, 2020; Virtual Event, Ireland††booktitle: Proceedings of the 29th ACM
International Conference on Information and Knowledge Management (CIKM ’20),
October 19–23, 2020, Virtual Event, Ireland††doi:
10.1145/3340531.3412159††isbn: 978-1-4503-6859-9/20/10

##  1\. Introduction

Entity Linking (EL) generally consists of two subtasks namely: surface form
extraction (mention detection) and named entity disambiguation (NED). A
surface form is a contiguous span of text that refers to a named entity. The
NED task aims to link the identified named entity to ground truth entities in
a given knowledge base (Singh et al., 2018). For a long time, researchers
focused on NED tasks over semi-structured knowledge repositories such as
Wikipedia111https://www.wikipedia.org/ or publicly available KGs such as
DBpedia (Lehmann et al., 2015), Freebase (Bollacker et al., 2008), and YAGO
(Suchanek et al., 2007). Wikidata (Vrandecic, 2012) has recently attracted the
community’s attention as a rich source of knowledge, and new approaches have
been developed to target NED over Wikidata (Cetoli et al., 2019).

Motivation: A peculiarity of Wikidata is that the contents are collaboratively
edited. As at April 2020; Wikidata contains 83,151,903 items and a total of
over 1.2B edits since the project
launch222https://www.wikidata.org/wiki/Wikidata:Statistics. Considering
Wikidata is collaboratively edited, the user-created entities add additional
noise and non standard labels ((e.g. labels have several numeric and special,
non-alphanumeric ASCII characters, also contains multi word labels up to 62
words, etc)) (et al., 2020) since users do not follow a strict naming
convention. For instance, there are 17,88,134 labels in which each label
matches with at least two different URIs. Hence, NED on Wikidata is quite
challenging as pointed out by initial studies (et al., 2020; Sakor et al.,
2019b). For example, consider the sentence from Wikidata-Disamb (Cetoli et
al., 2019) dataset: ”the short highway in New South Wales and the Australian
Capital Territory in Australia, it is part of Sydney-Canberra National Highway
link”. The entity surface form National Highway matches four(4) different
entities in Wikidata that share the same entity label (i.e., ”National
Highway”) while 2,055 other entities contain the whole mention in their
labels. The correct entity wikidata:Q1967298333wikidata:Q1967298 binds to
https://www.wikidata.org/wiki/Q1967298 refers to Highway System of Australia,
whereas wikidata:Q1967342 refers to the highway system in India. Having these
two entities as candidates may require extra information in addition to the
surface form or the sentence context. Attention-based Neural Networks (Vaswani
et al., 2017) and pretrained transformer models (et al., 2019f, d), have
provided an avenue for encoding the context within text, howbeit, in cases
such as our example, pure textual context may not be sufficient (et al.,
2019b). As such, a method to obtain matching contextual information from the
KG itself could be beneficial to disambiguate in such close scenarios.
Inspired by the work of (Cetoli et al., 2019) and inherited Wikidata NED
challenges (nonstandard multi-word, long, implicit, case-sensitive), we
hypothesize that the performance of pretrained transformer models improves by
considering further context from the KG. We investigate three research
questions: RQ1:How does applying KG context impact the performance of
transformer models on NED over Wikidata? RQ2: What is the performance of
different configurations of KG context as new information signals on the NED
task? RQ3: Can we generalize our proposed context in a state of the art NED
model for other knowledge bases such as Wikipedia? The structure of the paper
is follows: next section defines the task followed by related work in 3.
Section 4 describes approach and we present experiments in section 5. We
conclude in section 6.

Figure 1. Overall Approach : $\Phi$ refers to the ordered set of triples from
the KG for a candidate entity while $\Phi^{max}\subseteq\Phi$, is the maximum
number of triples that fits in the sequence length. For brevity: N →
”National”, H → ”Highway”, desc → ”description”

##  2\. Task Definition

Given a sentence, a recognized entity surface form, a set of candidate
entities, and a Knowledge Graph ($KG$), the objective is to select the entity
within the $KG$ that matches the surface form in the text. A sentence
$\mathcal{D}=\\{w_{1},w_{2},...,w_{n}\\}$ is a set of tokens of length $n$.
The set of entity surface forms
$S=\\{s_{1},s_{2},...,s_{k}\\}:s_{i}=(w^{\prime}\in\mathcal{D})+$ contains
recognized entities s.t. each $s$, spans one or more tokens in $\mathcal{D}$.
We view a KG as a labeled directed graph. A
$KG=(\mathcal{E},\mathcal{H}^{+},\mathcal{R})$ is a 3-tuple where: i) set
$\mathcal{E}$ of all entities represent the vertices. ii) set $\mathcal{R}$ is
the set of all edges between the entity instances in the graph. And; iii)
$\mathcal{H}^{+}\subseteq\mathcal{E}\times\mathcal{R}\times\mathcal{E}$ is the
ordered set of all triples. The function
$\ell(a\in{\mathcal{E}\cup\mathcal{R}})$ is defined that retrieves labels of
any given entity or relation from the KG.

Candidate Entities : A set containing selected entities from the KG given as:
$\mathcal{E}^{\prime}=\\{e^{\prime}_{1},e^{\prime}_{2},...,e^{\prime}_{m}\\}$
where $e^{\prime}_{j}\in\mathcal{E}$ and $\mathcal{E}^{\prime}=\sigma(s_{i}\in
S)$, is obtained by a semantic selection operation $\sigma$ on a given surface
form. This paper addresses the problem of named entity disambiguation which
selects an entity $e^{c}\in\mathcal{E}^{\prime}$ that matches the textual
mention $s\in S$ . We view this task as a classification $f=Classify(h(X))$ on
the conditional probability $h(X)=P(Y=1|X)$. Taking $x\in
X=(s,e^{\prime};\theta)$ we study configurations of the context parameters
$\theta$.

##  3\. Related Work

There is a wide variety of approaches in the literature for Entity Linking
(EL) ranging from graph traversal (Usbeck et al., 2014), rule-based (Sakor et
al., 2019a), to Neural Network-based approaches (Kolitsas et al., 2018; et
al., 2020). For detailed information on entity linking we refer to the surveys
in (Shen et al., 2015; Balog, 2018). Herein, we restrict ourselves to very
closely related recent literature. Advances in Neural Networks and the
introduction of self-attention based techniques (Vaswani et al., 2017) that
allow for encoding of contextual meaning from text have advanced research in
EL. Work in (Ganea and Hofmann, 2017) improved EL performance by proposing a
new approach that combines deep learning with more traditional methods such as
graphical models and probabilistic mention-entity maps. Research in (Kolitsas
et al., 2018) aims to achieve an end-to-end EL through context-aware mention
embeddings, entity embeddings, and a probabilistic mentions.

In the meantime, research on the learning of contextual data has advanced in
two directions. On one hand, the powerful pretrained transformer models (et
al., 2019d, f) have emerged as state-of-the-art for representing context
within text and have seen burgeoning reuse through fine-tuning for several NLP
tasks (Chen et al., 2020). On the other hand, KGs are increasingly being seen
as a source of additional knowledge for Neural Networks. For instance
researchers in (et al., 2019a) recently released an embedding library for the
Wikidata KG while the work by (et al., 2019b) introduced an extension of BERT
(KBERT) in which KG triples are injected into the sentences as domain
knowledge. Specific to the EL task, the work by (et al., 2020) employs
information from a locally derived KG to improve the performance of end-to-end
EL using attention-based Neural Networks. Researchers in (Cetoli et al., 2019)
fetched a significant amount (as high as 1500) of 2-hop KG triples and used
Recurrent Neural Networks (RNN) to encode this information. In this paper, we
argue that a slight amount of KG triple context is enough for a pretrained
transformer. We study the different configuration of KG context on transformer
models to target NED on Wikidata.

##  4\. Approach

Figure 1 illustrates the overall approach. For the classification :
$f(h(s,e^{\prime};\theta))=y$ such that $s$, the mentioned surface form, and
$e^{\prime}$, the candidate entity, are known. A set of contextual parameters
$\theta$ is then provided to the model. By adding the original sentence as
part of the input, we let the model learn source context. Our approach then
models a set of information from the target KG in the form of KG triples
$\Phi$ as context. The aim is to maximize both the true positives and true
negatives such that, for every input, if $y=1$ then the $e^{c}$ is the ground
truth entity of $s$ in the KG. The classifier employs the binary cross-entropy
loss.

Knowledge Graph Context: We use a SPARQL endpoint to fetch triples of the
identified entity in the sentence. There are two sets of triple configurations
considered in our experiments, depending on the hop counts from the head
entity. The parameter $\Phi$ is therefore an ordered set of of triples
$(h^{e},r_{hp},t_{hp})^{i}$ such that $h^{e}$, the head (subject) of any
triple is the candidate entity to be classified whereas $hp=1|2$ is the hop
count. The $i$ refers to the position of the triple in the set and can range
between 1 and over 1000. To formulate our input, we consider the natural
language labels of the retrieved triples $l_{h^{e}}$ , $l_{r}$ , $l_{t}$. A
triple is therefore verbalized into it’s natural language form:
”$l_{h^{e}}[whitespace]l_{r}[whitespace]l_{t}$”. The sequence of these
verbalized triples are appended to the original sentence and surface form
delimited by the [SEP] token. Figure 1 shows how the context input is handled
such that the Segment Embeddings for every triple is different and provides a
unique signal to the tokens at the embeddings layer of the network. When the
total number of triples is too many, we use the maximum sequence length to
limit the input where the final context representation
$\Phi^{max}\subseteq\Phi$. The values of $\Phi^{max}$,for entity: Q1967298 in
figure 2, is given as: [National Highway description highway system in
Australia [SEP] National Highway label National Highway [SEP] National Highway
date modified 31 May 2019 [SEP]]

##  5\. Evaluation

Datasets: The first dataset is Wikidata-Disamb(Cetoli et al., 2019), which
aligns Wiki-Disamb30 (Ferragina and Scaiella, 2010) to Wikidata entities, and
adds closely matching entities as negative samples to every entity in the
dataset. It consists of 200,000 Train and 20,000 Test samples. We also
consider the ISTEX dataset introduced by (Delpeuch, 2019), extracted from
scientific publications and contains 1000 author-affiliation strings from
research articles aligned to Wikidata. For generalizing the impact of KG
context, we choose standard Wikipedia dataset: AIDA-CoNLL (et al., 2011). We
aligned its Wikipedia entities to corresponding Wikidata mentions to fetch the
KG triples. Datasets are accompanied with a pre-computed candidate list.
Baselines:  We compare our results with three types of baselines. First is
(Cetoli et al., 2019), which experimented with numerous configurations of KG
context on Long Short Term Memory (LSTM) networks and reported an ablation of
these configurations. These models were augmented with a massive amount of
1&2-hop KG triples. We also run the model on the ISTEX dataset to enable
performance comparison. We create a second set of baselines by employing the
vanilla transformer models of RoBERTa and XLNet(i.e., transformers without KG
context) on Wikidata-Disamb and ISTEX. We fine-tuned vanilla models on
Wikidata-Disamb training set. For AIDA-CoNLL, we chose (et al., 2019c) as our
underlying model which is the second peer reviewed SOTA on this dataset.
Authors used Wikipedia descriptions as a context for candidate entities, and
we replaced this context with our proposed 1-hop KG triple context fetched
from Wikidata triples of corresponding Wikipedia entities. We verbalized the
fetched triples, as described in our approach.

Figure 2. KG context : Top three 1-hop triples from Wikidata for the two
entities with same label: National Highway.

Model Parameters:  We chose two state of the art transformer architectures:
RoBERTa (et al., 2019d), and XLNet (et al., 2019f) and fine-tune them using
Wikidata-Disamb30 training set. We report P,R,F values following the baseline
of Wikidata-Disamb and ISTEX dataset. For each vanilla Transformer
architecture, we add a classification head. The maximum sequence length for
the inputs in both models is fixed at 512 tokens, and we use this to limit the
amount of KG context to feed. We publicly release code, datasets, training
details, and results for reusability and reproducibility. On AIDA-CoNLL, We
use open source implementation of (et al., 2019c) for feeding the KG context
and report In-KB accuracy as prior work(s).

Model |  Prec |  Recall |  F1
---|---|---|---
LSTM + RNN-triplets (Cetoli et al., 2019) |  90.1 |  92.0 |  91.1
LSTM+RNN-triplets+ATN(Cetoli et al., 2019) |  90.2 |  93.0 |  91.6
RoBERTa - without KG context |  89.09 |  84.67 |  86.23
XLNet-without KG context |  89.32 |  87.62 |  88.46
Our Contextual models |  |  |
RoBERTa + 1-hop KG Context |  91.48 |  93.23 |  92.35
RoBERTa + 1&2-hop KG Context |  89.88 |  87.64 |  88.75
XLNet + 1-hop KG Context |  91.55 |  93.14 |  92.34
XLNet + 1&2-hop KG Context |  91.93 |  92.36 |  92.14
Table 1. Comparison of our model against baselines on the Wikidata-Disamb
dataset. Best results in dark bold

Results and Discussion: Table 1 shows the results from evaluating our approach
against the baselines on the Wikidata-Disamb30 and table 2 indicates the
performance of the models on the ISTEX dataset. The results in table 2
obtained by running the same model trained on the Wikidata-Disamb30 dataset
(also for baseline) with context, but during testing, no more context is
provided. Based on our results, we postulate that although the Transformer
based language models are trained on huge corpus and possess context for the
data, they show limited performance even against the RNN model. This RNN model
(Cetoli et al., 2019) uses GloVe embeddings together with task-specific
context (cf. Table 1). However, the transformer models outperform the baseline
models when fed with our proposed KG context. For instance, (cf. Table 1),
RoBERTa, with a 1-hop context, can correctly link entities in additional 1127
sample sentences in the test set (flipped from incorrect to the correct
predictions) compared to its vanilla setting. These samples have 997 unique
Wikidata IDs.

Model |  Prec |  Recall |  F1
---|---|---|---
LSTM + RNN of triplets + ATN (Cetoli et al., 2019) |  86.32 |  96.38 |  90.97
RoBERTa + 1-hop Triples (Ours) |  91.70 |  91.98 |  91.84
XLNet + 1-hop KG Context(Ours) |  96.39 |  89.11 |  92.61
Table 2. Our models against baseline on ISTEX dataset

These results also indicate that the transformer models achieve better
precision compared to recall; this is clear in table 2 and interpreted as
follows: our model is more likely to classify an entity as the correct entity
only when it is true (few false positives). For brevity, the detailed analysis
of each experimental setup and corresponding data can be found in our
Github444https://github.com/mulangonando/Impact-of-KG-Context-on-ED.

Model |  In-KB. Acc.
---|---
Yamada et al. (2016) (et al., 2016) |  91.5
Ganea&Hofmann (2017) (Ganea and Hofmann, 2017) |  92.22$\pm$0.14
Yang et al. (2018) (et al., 2018) |  93.0
Le&Titov (2018) (Le and Titov, 2019) |  93.07$\pm$0.27
DeepType (2018) (Raiman and Raiman, 2018) |  94.88
Fang et al. (2019) (et al., 2019e) |  94.3
Le& Titov (2019) (Le and Titov, 2019) |  89.66$\pm$0.16
DCA-SL (2019)(et al., 2019c) |  94.64$\pm$0.2
Chen et al. (2020) (et al, 2020) |  93.54$\pm$0.12
DCA-SL + Triples(ours) |  94.94$\pm$0.2
Table 3. Generalizability Study: Comparison of KG Context based model against
baselines on the AIDA-CONLL dataset. Best value in bold and previous SOTA
value is underline.

Concerning RQ2, our results indicate that including triples from higher hop
counts either exhibit an inverse impact on the performance or have minimal
effect on overall model behavior (cf. Table 1 RoBERTa vs. XLNet 2-hop values).
This signals that the further away we drift from the head entity, the noisier
the signal provided by the context added. As such, we did not extend
evaluation to higher triple hops. However, we can observe that XLNet shows a
more stable behavior in cases when the excess context is provided as it can
preserve already learned information. It is in contrast to RoBERTa, which
loses necessary signals in an attempt to learn from the extra context. The
amount of data fed as the context in our models is minimal (up to 15 1-hop
triples). In contrast, the best performing model from work in (Cetoli et al.,
2019), was fed up to 1500 1+2-hop triples. Our best performance can then be
attributed to the quality of textual context learned by the transformers as
well as the optimal choice of KG-triples context.
Generalizing KG Context: We induced 1-hop KG context in DCA-SL model (et al.,
2019c) for candidate entities. The replacement of the unstructured Wikipedia
description with structured KG triple context containing entity aliases,
entity types, consolidated entity description, etc. has a positive impact on
the performance. Our proposed change (DCA-SL + Triples) outperforms the
baselines for Wikipedia entity disambiguation(cf. Table 3). Please note, out
of 207,544 total entities of AIDA-CoNLL datasets, 7591 entities have no
corresponding Wikidata IDs. Even if we do not feed the KG context for 7591
entities, the performance increases. It validates our third research question
(RQ3), and we conclude KG triple context can be standardized for the NED task
for Wikipedia.

##  6\. Conclusion

In this paper, we study three closely related research questions. We
demonstrate that pretrained Transformer models, although powerful, are limited
to capturing context available purely on the texts concerning the original
training corpus. We observe that an extra task-specific KG context improved
the performance. However, there is a limit to the number of triples as the
context that can improve performance. We note that 2-hop triples resulted in
negative or little impact on transformer performance. Our triple context can
be generalized (for Wikipedia) and observes a positive effect on the NED model
for Wikipedia, leading into a new SOTA for AIDA-CoNLL dataset. For the future
work, it would be interesting to understand which triples negatively impact
the context and how to select the ”optimal choice of KG-triples context,”
considering we rely on the triple in the same order of the SPARQL endpoint
returned results. As a viable next step, we plan to study independent effect
of various KG attributes (entity properties such as aliases, descriptions,
Instance-of, etc.) on NED models’ performance.

##  7\. Acknowledgments

This work is co-funded by the Federal Ministry of Education and Research’s
(BMBF) Software Campus initiative under the Answer-KiNG Project.

## References

  * (1)
  * Balog (2018) Krisztian Balog. 2018\.  _Entity Linking_.  Springer International.
  * Bollacker et al. (2008) Kurt D. Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. 2008.  Freebase: a collaboratively created graph database for structuring human knowledge. In _ACM SIGMOD_.
  * Cetoli et al. (2019) Alberto Cetoli et al. 2019\.  A Neural Approach to Entity Linking on Wikidata. In _ECIR_. 78–86.
  * Chen et al. (2020) Shuang Chen, Jinpeng Wang, Feng Jiang, and Chin-Yew Lin. 2020\.  Improving Entity Linking by Modeling Latent Entity Type Information.  _CoRR_ (2020).
  * Delpeuch (2019) Antonin Delpeuch. 2019\.  OpenTapioca: Lightweight Entity Linking for Wikidata.  _CoRR_ (2019).
  * et al. (2019a) Adam Lerer et al. 2019a.  PyTorch-BigGraph: A Large-scale Graph Embedding System.  _CoRR_ (2019).
  * et al. (2020) Isaiah Mulang’ et al. 2020\.  encoding knowledge graph entity aliases in attentive neural network for wikidata entity linking.  _WISE_ (2020).
  * et al. (2016) Ikuya Yamada et al. 2016\.  Joint Learning of the Embedding of Words and Entities for Named Entity Disambiguation. In _CoNLL_.
  * et al. (2011) Johannes Hoffart et al. 2011\.  Robust Disambiguation of Named Entities in Text. In _EMNLP_.
  * et al (2020) Shuang Chen et al. 2020\.  Improving Entity Linking by Modeling Latent Entity Type Information. In _AAAI 2020_.
  * et al. (2019b) Weijie Liu et al. 2019b.  K-BERT: Enabling Language Representation with Knowledge Graph.  _ArXiv_ (2019).
  * et al. (2019c) Xiyuan Yang et al. 2019c.  Learning Dynamic Context Augmentation for Global Entity Linking. In _EMNLP_.
  * et al. (2019d) Yinhan Liu et al. 2019d.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _CoRR_ (2019).
  * et al. (2018) Yi Yang et al. 2018\.  Collective Entity Disambiguation with Structured Gradient Tree Boosting. In _NAACL_.
  * et al. (2019e) Zheng Fang et al. 2019e.  Joint Entity Linking with Deep Reinforcement Learning. In _WWW_.
  * et al. (2019f) Zhilin Yang et al. 2019f.  XLNet: Generalized Autoregressive Pretraining for Language Understanding.  _CoRR_ (2019).
  * Ferragina and Scaiella (2010) Paolo Ferragina and Ugo Scaiella. 2010.  TAGME: on-the-fly annotation of short text fragments (by Wikipedia entities).  _CoRR_ (2010).
  * Ganea and Hofmann (2017) Octavian-Eugen Ganea and Thomas Hofmann. 2017.  Deep Joint Entity Disambiguation with Local Neural Attention. In _EMNLP_.
  * Kolitsas et al. (2018) Nikolaos Kolitsas, Octavian-Eugen Ganea, and Thomas Hofmann. 2018.  End-to-End Neural Entity Linking. In _In CoNLL_.
  * Le and Titov (2019) Phong Le and Ivan Titov. 2019.  Boosting Entity Linking Performance by Leveraging Unlabeled Documents. In _ACL_.
  * Lehmann et al. (2015) Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N. Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, and Christian Bizer. 2015.  _Semantic Web Journal_ (2015).
  * Raiman and Raiman (2018) Jonathan Raiman and Olivier Raiman. 2018.  DeepType: Multilingual Entity Linking by Neural Type System Evolution. In _AAAI 2018_.
  * Sakor et al. (2019a) Ahmad Sakor, Isaiah Onando Mulang’, Kuldeep Singh, Saeedeh Shekarpour, Maria Esther Vidal, Jens Lehmann, and Sören Auer. 2019a.  Old is gold: linguistic driven approach for entity and relation linking of short text. In _NAACL HLT_. 2336–2346.
  * Sakor et al. (2019b) Ahmad Sakor, Kuldeep Singh, Anery Patel, and Maria-Esther Vidal. 2019b.  Falcon 2.0: An Entity and Relation Linking Tool over Wikidata.  _arXiv preprint arXiv:1912.11270_ (2019).
  * Shen et al. (2015) W. Shen, J. Wang, and J. Han. 2015.  Entity Linking with a Knowledge Base: Issues, Techniques, and Solutions.  _IEEE Transactions on Knowledge and Data Engineering_ 27, 2 (2015), 443–460.
  * Singh et al. (2018) Kuldeep Singh, Arun Sethupat Radhakrishna, Andreas Both, Saeedeh Shekarpour, Ioanna Lytra, Ricardo Usbeck, Akhilesh Vyas, Akmal Khikmatullaev, Dharmen Punjani, Christoph Lange, Maria-Esther Vidal, Jens Lehmann, and Sören Auer. 2018\.  Why Reinvent the Wheel: Let’s Build Question Answering Systems Together. In _The Web Conference_.
  * Suchanek et al. (2007) Fabian M. Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007\.  Yago: A Core of Semantic Knowledge. In _16th International Conference on the World Wide Web_. 697–706.
  * Usbeck et al. (2014) Ricardo Usbeck, Axel-Cyrille Ngonga Ngomo, Michael Röder, Daniel Gerber, Sandro Athaide Coelho, Sören Auer, and Andreas Both. 2014.  AGDISTIS - Graph-Based Disambiguation of Named Entities Using Linked Data. In _The Semantic Web - ISWC 2014_. Springer, 457–471.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017\.  Attention Is All You Need.  _CoRR_ abs/1706.03762 (2017).
  * Vrandecic (2012) Denny Vrandecic. 2012\.  Wikidata: a new platform for collaborative data collection. In _WWW (Companion Volume)_.


result to directed graphs as this is only about $2$-way partitioning (recall
the discussion above 4.2). This potentially can also be used to explain the
good empirical performance of the spectral algorithm in Theorem 1.8.

######  Theorem 4.5 (Improved Cheeger’s inequality for Directed Vertex
Expansion).

Let $G=(V,E,\pi)$ be a vertex-weighted directed graph. For any $2\leq k\leq
n$,

$\vec{\lambda}_{2}^{v*}(G)\lesssim\vec{\psi}(G)\lesssim\frac{k^{3/2}\cdot\log(\Delta\cdot\alpha(G))\cdot\vec{\lambda}_{2}^{v*}(G)}{\sqrt{\vec{\lambda}_{k}^{v*}(G)}}\lesssim\frac{k^{3/2}\cdot\log(\Delta/\vec{\psi}(G))\cdot\vec{\lambda}_{2}^{v*}(G)}{\sqrt{\vec{\lambda}_{k}^{v*}(G)}}.$

######  Theorem 4.6 (Improved Cheeger’s inequality for Directed Edge
Conductance).

Let $G=(V,E,w)$ be an edge-weighted directed graph. For any $2\leq k\leq n$,

$\vec{\lambda}_{2}^{e*}(G)\lesssim\vec{\phi}(G)\lesssim\frac{k^{3/2}\cdot\log\alpha(G)\cdot\vec{\lambda}_{2}^{e*}(G)}{\sqrt{\vec{\lambda}_{k}^{e*}(G)}}\lesssim\frac{k^{3/2}\cdot\log(1/\vec{\phi}(G))\cdot\vec{\lambda}_{2}^{e*}(G)}{\sqrt{\vec{\lambda}_{k}^{e*}(G)}}.$

The proofs of the two results are similar to that in [KLLOT13, KLT22] and also
similar to each other as in Section 3, so we just provide a sketch of the
proof of Theorem 4.5 in the following.

Note that $\vec{\lambda}_{k}^{v*}(G)$ not a convex optimization problem. As in
[KLT22], we change the objective in 1.2 to maximize the sum of the $k$
smallest eigenvalues $\sum_{i=1}^{k}\lambda_{i}({\mathcal{L}})$, so that we
can use 2.2 to write this as a semidefinite program, which we call
$\vec{\sigma}_{k}^{v*}(G)$. Using the same manipulations as in [KLT22,
Proposition 5.2] and 3.3, we can write

$\displaystyle\vec{\sigma}_{k}^{v*}(G):=\min_{f:V\rightarrow\mathbb{R}^{n}}\max_{A\geq
0}$ $\displaystyle~{}~{}~{}\frac{1}{2}\sum_{uv\in E}A(u,v)\cdot\left\lVert
f(u)-f(v)\right\rVert^{2}$ subject to $\displaystyle~{}~{}~{}A(u,v)=0$
$\displaystyle\forall uv\not\in E$ $\displaystyle~{}~{}~{}\sum_{v\in
V}A(u,v)=\sum_{v\in V}A(v,u)$ $\displaystyle\forall u\in V$
$\displaystyle~{}~{}~{}\sum_{v\in V}A(v,u)=\pi(u)$ $\displaystyle\forall u\in
V$ $\displaystyle~{}~{}~{}\sum_{v\in V}\pi(v)\cdot f(v)f(v)^{T}\preccurlyeq
I_{n}$ $\displaystyle~{}~{}~{}\sum_{v\in V}\pi(v)\cdot\left\lVert
f(v)\right\rVert^{2}=k.$

The proof will relate $\vec{\lambda}_{2}^{v*}(G)$ and
$\vec{\sigma}_{k}^{v*}(G)$ to $\vec{\psi}(G)$. Note that
$\vec{\lambda}_{k}^{v*}(G)\leq\vec{\sigma}_{k}^{v*}(G)\leq
k\cdot\vec{\lambda}_{k}^{v*}(G)$. This is where an extra factor of $\sqrt{k}$
is lost compared to the bound in [KLLOT13].

We follow the same two-step approach in [KLLOT13, KLT22]. The first step is to
prove that if there is a $1$-dimensional solution to
$\vec{\lambda}_{v}^{(1)}(G)$ that is close to a $k$-step function (i.e. a
function with at most $k$ distinct values), then the approximation guarantee
of threshold rounding in Section 3.5.3 is improved.

######  Proposition 4.7 (Improved Threshold Rounding).

Let $G=(V,E,\pi)$ be a vertex-weighted directed graph. Given a solution
$f:V\to\mathbb{R}$ to $\vec{\lambda}_{v}^{(1)}(G)$ with objective value
$\lambda_{f}$ and a $k$-step function $y_{f}:V\to\mathbb{R}$ approximating
$f$, it holds that

$\vec{\psi}(G)\lesssim\eta_{v}(G)\lesssim k\cdot\lambda_{f}+k\left\lVert
f-y_{f}\right\rVert_{\pi}\sqrt{\lambda_{f}},$

where $\eta_{v}(G)$ is the $\ell_{1}$-version of $\vec{\lambda}_{v}^{(1)}(G)$
in 3.18, and $\left\lVert z\right\rVert_{\pi}^{2}:=\sum_{v}\pi(v)\cdot
z(v)^{2}$ for any $z:V\to\mathbb{R}$. Note the first inequality is by 3.23.

The second step is to prove that if $\vec{\sigma}_{k}^{v*}(G)$ is large for a
small $k$, then there is a good $k$-step approximation to a good solution to
$\vec{\lambda}_{v}^{(1)}(G)$. As in Section 3.5.3, we consider the $\ell_{1}$
dual program $\xi_{v}(G)$ in 3.21 of $\eta_{v}(G)$.

######  Proposition 4.8 (Constructing $k$-Step Approximation).

Let $G=(V,E,\pi)$ be a vertex-weighted directed graph. Given a solution
$f:V\to\mathbb{R}$ to $\xi_{v}(G)$ with objective value $\xi_{f}$, there
exists a $k$-step function $y:V\rightarrow\mathbb{R}$ with

$\left\lVert
f-y\right\rVert_{\pi}^{2}\lesssim\frac{k\cdot\xi_{f}}{\vec{\sigma}_{k}^{v*}(G)}.$

Combining the two propositions, using $\lambda_{f}=\xi_{f}$, and applying the
dimension reduction result in Theorem 3.11, we get

$\vec{\psi}(G)\lesssim k\cdot\lambda_{f}+k\left\lVert
f-y_{f}\right\rVert_{\pi}\sqrt{\lambda_{f}}\lesssim\frac{k^{1.5}\cdot\lambda_{f}}{\sqrt{\vec{\sigma}_{k}^{v*}(G)}}\lesssim\frac{k^{1.5}\cdot\log(\Delta\cdot\alpha(G))\cdot\vec{\lambda}_{2}^{v*}(G)}{\sqrt{\vec{\lambda}_{k}^{v*}(G)}}.$

The proof of 4.7 is by combining the arguments in [KLT22, Proposition 6.3] and
3.20. The proof of 4.8 is essentially the same as in [KLT22, Proposition 6.3].
There are no new steps in these proofs, so we omit them so as not to overload
this paper.

##  5 Cheeger-Type Inequalities for Hypergraphs

Louis [Lou15] and Chan, Louis, Tang, Zhang [CLTZ18] developed a spectral
theory for hypergraphs based on a continuous time diffusion process. They used
it to derive a Cheeger inequality for hypergraph edge conductance, a higher-
order Cheeger inequality for hypergraph $k$-way edge conductance, and a
Cheeger inequality for hypergraph small-set conductance.

In this section, we will use the reweighted eigenvalue approach to derive
similar results and compare with the results in [CLTZ18]. In addition, we will
prove an improved Cheeger inequality for hypergraph edge conductance, that was
not known before. Since the proofs of these results are all essentially the
same as the corresponding proofs in [KLT22], we just provide quick sketches so
as to not overload this paper.

We note that vertex expansion in a hypergraph $H$ can simply be reduced to
vertex expansion in its clique-graph $G$, and so the results of [KLT22] can be
directly applied with $\Delta(G)\leq\Delta(H)\cdot r$, where $r$ is the
maximum size of a hyperedge in $H$. So we will only focus on hypergraph edge
conductance in this section.

###  5.1 Cheeger Inequality for Hypergraphs

Results in [Lou15, CLTZ18]: Given a hypergraph $H=(V,E)$ with a weight
function $w:E\to\mathbb{R}_{\geq 0}$, they defined a nonlinear Laplacian
operator and its eigenvalues
$\gamma_{1}\leq\gamma_{2}\leq\ldots\leq\gamma_{|V|}$ based on a continuous
time diffusion process. Then they derived a Cheeger inequality
$\frac{1}{2}\gamma_{2}\leq\phi(H)\leq\sqrt{2\gamma_{2}}$ in [CLTZ18, Theorem
6.1], where $\phi(H)$ is the hypergraph edge conductance of $H$ in 1.9. But
the quantity $\gamma_{2}$ in [CLTZ18, Definition 3.1] is not polynomial time
computable, and so a semidefinite programming relaxation
$\widetilde{\gamma}_{2}$ of $\gamma_{2}$ (see [CLTZ18, SDP 8.3]) was used in
[CLTZ18, Theorem 8.1] to prove that

$\widetilde{\gamma}_{2}\lesssim\phi(H)\lesssim\sqrt{\widetilde{\gamma}_{2}\cdot\log
r}.$ (5.1)

Our Results: In the reweighted eigenvalue approach, we use $\gamma_{2}^{*}(H)$
in 1.10 as a relaxation to $\phi(H)$. We can prove the easy direction as in
3.2 by a reduction, but we actually do not need to prove it as we will see
soon. As in 3.4, we can write $\gamma_{2}^{*}(H)$ as the following
semidefinite program:

$\displaystyle\gamma_{2}^{*}(H):=\min_{f:V\rightarrow\mathbb{R}^{n}}\max_{A\geq
0}$ $\displaystyle~{}~{}~{}\sum_{e\in E}\sum_{\\{u,v\\}\subseteq
e}c(u,v,e)||f(u)-f(v)||^{2}$ subject to
$\displaystyle~{}~{}~{}\sum_{\\{u,v\\}\subseteq e}c(u,v,e)\leq
w(e)\quad\quad\forall u,v\in V$ $\displaystyle~{}~{}~{}\sum_{v\in
V}d_{w}(v)\cdot f(v)=\vec{0}$ $\displaystyle~{}~{}~{}\sum_{v\in
V}d_{w}(v)\cdot\left\lVert f(v)\right\rVert^{2}=1.$

By using LP duality in the inner maximization problem as in 3.21, it follows
that

$\displaystyle\gamma_{2}^{*}(H)=\min_{f:V\rightarrow\mathbb{R}^{n}}\min_{g:V\to\mathbb{R}_{\geq
0}}$ $\displaystyle~{}~{}~{}\sum_{e\in E}g(e)\cdot w(e)$ subject to
$\displaystyle~{}~{}~{}g(e)\geq\left\lVert
f(u)-f(v)\right\rVert^{2}\quad\quad\forall\\{u,v\\}\subseteq e,\forall e\in E$
$\displaystyle~{}~{}~{}\sum_{v\in V}d_{w}(v)\cdot f(v)=\vec{0}$
$\displaystyle~{}~{}~{}\sum_{v\in V}d_{w}(v)\cdot\left\lVert
f(v)\right\rVert^{2}=1.$

It turns out that $\gamma_{2}^{*}(H)$ in this form is exactly the same as
$\widetilde{\gamma}_{2}$ in [CLTZ18, SDP 8.3]. (Also, $\gamma_{2}$ in [CLTZ18]
is simply this dual program restricted to one dimensional embeddings
$f:V\to\mathbb{R}$ as stated in 3.22.) Therefore, Theorem 1.11 follows from
their result in (5.1). We would like to mention that we initially proved
Theorem 1.11 using the same proofs as in [KLT22], which is not surprising as
the proofs in [KLT22] are very similar to that in [LRV13, CLTZ18].

###  5.2 Higher-Order Cheeger Inequality and Small-Set Expansion for
Hypergraphs

Results in [Lou15, CLTZ18]: Given a hypergraph $H=(V,E)$ with a weight
function $w:E\to\mathbb{R}_{\geq 0}$, the $k$-way edge conductance of $H$ is
defined as $\phi_{k}(H):=\min_{S_{1},S_{2},\ldots,S_{k}}\max_{1\leq i\leq
k}\phi(S_{i})$ where $S_{1},S_{2},\ldots,S_{k}$ are over pairwise disjoint
subsets of $V$. [CLTZ18, Theorem 6.14] states that

$\widetilde{\gamma}_{k}\lesssim\phi_{k}(H)\lesssim k^{4}\cdot\log
k\cdot\log\log k\cdot\log
r\cdot\sqrt{\widetilde{\gamma}_{k}}{\rm~{}and~{}}\phi_{(1-{\epsilon})k}(H)\lesssim\frac{k^{2.5}}{{\epsilon}^{1.5}}\cdot\log
k\cdot\log\log k\cdot\log r\cdot\sqrt{\widetilde{\gamma}_{k}}$ (5.2)

for any ${\epsilon}\geq 1/k$, where $\widetilde{\gamma}_{k}$ is an SDP
relaxation of $\gamma_{k}$ which can be computed in polynomial time.
Furthermore, they proved a stronger bound in [CLTZ18, Corollary 3.23] about
small-set conductance that there is a subset $S$ with $|S|=\Theta(n/k)$ and

$\phi(S)\lesssim k^{1.5}\cdot\log k\cdot\log\log k\cdot\log
r\cdot\sqrt{\widetilde{\gamma}_{k}}.$ (5.3)

Our Results: We define $\gamma_{k}^{*}(H)$ as in 1.10 but the objective is to
maximize the $k$-th smallest eigenvalue of the normalized Laplacian matrix
${\mathcal{L}}=I-D^{-1/2}AD^{-1/2}$. This is, however, not a convex
optimization problem. As in [KLT22], we change the objective to maximize the
sum of the $k$ smallest eigenvalues
$\sum_{i=1}^{k}\lambda_{i}({\mathcal{L}})$, so that we can use 2.2 to write
this as a semidefinite program that we call $\sigma_{k}^{*}(H)$. Using the
same manipulations as in [KLT22, Proposition 5.2], we can write

$\displaystyle\sigma_{k}^{*}(H):=\min_{f:V\rightarrow\mathbb{R}^{n}}\min_{g:V\to\mathbb{R}_{\geq
0}}$ $\displaystyle~{}~{}~{}\sum_{e\in E}g(e)\cdot w(e)$ subject to
$\displaystyle~{}~{}~{}g(e)\geq\left\lVert
f(u)-f(v)\right\rVert^{2}\quad\quad\forall\\{u,v\\}\subseteq e,\forall e\in E$
$\displaystyle~{}~{}~{}\sum_{v\in V}d_{w}(v)\cdot f(v)f(v)^{T}\preccurlyeq
I_{n}$ $\displaystyle~{}~{}~{}\sum_{v\in V}d_{w}(v)\cdot\left\lVert
f(v)\right\rVert^{2}=k.$

Following the same but rather long proof in [KLT22, Section 5.2-5.4], we can
construct functions $f_{1},\ldots,f_{l}$ with disjoint supports such that each
is a good solution to 1.10, and prove the exact same statement as in [KLT22,
Theorem 5.20].

######  Theorem 5.1 (Higher-Order Cheeger Inequality for Hypergraphs).

For any hypergraph $H=(V,E)$ with weight function $w:E\to\mathbb{R}_{\geq 0}$,

$\frac{1}{k}\sigma_{k}^{*}(H)\lesssim\phi_{k}(H)\lesssim k^{4}\log k\sqrt{\log
r\cdot\sigma_{k}^{*}(H)}\quad{\rm
and}\quad\phi_{(1-{\epsilon})k}(H)\lesssim\frac{1}{{\epsilon}^{4}}\log
k\sqrt{\log r\cdot\sigma_{k}^{*}(H)}.$

Compared to (5.2), the result for $k$-way partitioning is comparable with an
extra factor of $\sqrt{k}$ but a factor of $\sqrt{\log r}$ less, while the
result for $[(1-{\epsilon})k]$-way partitioning for constant ${\epsilon}$ is
an improvement by a factor of more than $k^{2}$. As a consequence, this also
implies an improvement of (5.3) for small-set conductance by a factor of more
than $k$.

###  5.3 Improved Cheeger Inequality for Hypergraphs

Using the reweighted eigenvalue approach, we can also prove an analog of the
improved Cheeger’s inequality as described in Section 4.3. This is a new
result that was not obtained in [Lou15, CLTZ18]. Combining with the higher-
order Cheeger inequality for hypergraphs in Theorem 5.1, this implies the
following corollary that only depends on the combinatorial structure of $H$:
If the $k$-way edge conductance $\phi_{k}(H)$ is large for a small $k$, then
$\gamma_{2}^{*}(H)$ is a tighter approximation to $\phi(H)$.

######  Theorem 5.2 (Improved Cheeger’s Inequality for Hypergraphs).

Let $H=(V,E)$ be a hypergraph with weight function
$w:E\rightarrow\mathbb{R}_{\geq 0}$. For any $2\leq k\leq n$,

$\phi(H)\lesssim\frac{k^{3/2}\cdot\log
r\cdot\gamma_{2}^{*}(H)}{\sqrt{\gamma_{k}^{*}(H)}}.$

The proof of Theorem 5.2 follows the same two-step approach as in [KLLOT13,
KLT22] and also in Section 4.3 in this paper. Actually, the proof for
hypergraphs is very similar to that for undirected vertex expansion in
[KLT22], and is easier than that for directed graphs in Section 4.3. So, we
omit the details and refer the reader to Section 4.3 for an overview. The only
new element is the formulation in 1.10.

##  6 Concluding Remarks

In this paper, we show that the reweighted eigenvalue approach can be extended
substantially to derive Cheeger inequalities for directed graphs and
hypergraphs. Most notably, this develops into an interesting new spectral
theory for directed graphs, which is much closer to the spectral theory for
undirected graphs than what are previously known. We hope that this spectral
theory will find more applications in practice, in clustering and partitioning
of directed graphs and hypergraphs.

Technically, the reweighted eigenvalue approach provides an intuitive and
unifying method to reduce the study of expansion properties in more general
settings to the basic setting of edge conductance in undirected graphs. We
believe that this approach can be used to lift more results in spectral graph
theory for undirected graphs to more general settings, as the ideas are
consistent with recent works on directed Laplacian solvers and hypergraph
spectral sparsification that we mentioned in Section 1.3.

There are some concrete open problems. The most obvious one is to prove tight
bounds for the two main results Theorem 1.3 and Theorem 1.8, to settle whether
the dependency on the asymmetric ratio can be completely removed or not999See
3.12 that the dimension reduction result for directed edge conductance is
tight, and so a positive result removing the $\log\alpha(G)$ factor in Theorem
1.8 would probably need substantial new ideas. We incline to believe that the
$\log\alpha(G)$ factor in Theorem 1.8 cannot be completely removed, but we do
not have an example supporting this belief. We are less sure about what the
right bound should be for Theorem 1.3.. Another one is to formulate and prove
higher-order Cheeger inequality and bipartite Cheeger inequality for directed
graphs as discussed in Section 4. An important one for applications is to
design fast algorithms (ideally near-linear time algorithms) for computing
reweighted eigenvalues.

## References

  * [ACMM05] Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev. $O(\sqrt{n})$ approximation algorithm for min UnCut, min 2CNF deletion, and directed cut problems. In Proceedings of the 37th Annaul ACM Symposium on Theory of Computing (STOC), 573–581, 2005.
  * [AF02] David Aldous, James Allen Fill. Reversible Markov chains and random walks on graphs/ Unfinished monograph, 2002 (recomplied 2014), available at http://www.stat.berkeley.edu/ãldous/RWG/book.html.
  * [Alo86] Noga Alon. Eigenvalues and expanders. Combinatorica, 6, 83–96, 1986.
  * [AM85] Noga Alon, Vitali Milman. $\lambda_{1}$, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory, Series B, 38(1), 73–88, 1985.
  * [ABS10] Sanjeev Arora, Boaz Barak, David Steurer. Subexponential algorithms for unique games and related problems. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 563–572, 2010.
  * [ARV09] Sanjeev Arora, Satish Rao, Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56(2):1–37, 2009.
  * [BDX04] Stephen Boyd, Persi Diaconis, Lin Xiao.  Fastest mixing markov chain on a graph.  SIAM review, 46(4):667–689, 2004.
  * [CLTZ18] T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, Chenzi Zhang. Spectral properties of hypergraph Laplacian and approximation algorithms. Journal of the ACM, 65(3):1–48, 2018.
  * [CTWZ19] T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu, Chenzi Zhang. Diffusion operator and spectral analysis for directed hypergraph Laplacian. Theoretical Computer Science 784, 46–64, 2019.
  * [CTZ15] T.-H. Hubert Chan, Zhihao Gavin Tang, Chenzi Zhang. Cheeger inequalities for general edge-weighted directed graphs. Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON), 30–41, 2015.
  * [CKN20] Yu Chen, Sanjeev Khanna, and Ansh Nagda. Near-linear size hypergraph cut sparsifiers. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), 61–72, 2020.
  * [Che70] Jeff Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis, Princeton University Press, 195–199, 1970.
  * [Chu97] Fan Chung. Spectral graph theory. volume 92 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997. 9
  * [Chu05] Fan Chung. Laplacians and Cheeger Inequality for Directed Graphs. Annals of Combinatorics 9, 1–19, 2005.
  * [CKP+16] Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), 583–592, 2016.
  * [CKP+17] Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Anup B. Rao, Aaron Sidford, Adrian Vladu. Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 410–419, 2017.
  * [CLSZ20] Mihai Cucuringu, Huan Li, He Sun, Luca Zanetti. Hermitian matrices for clustering directed graphs: insights and applications. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
  * [EMPS16] Alina Ene, Gary L. Miller, Jakub Pachocki, Aaron Sidford. Routing under balance. In Proceedings of the 48th Annual Symposium on Theory of Computing (STOC), 598–611, 2016.
  * [Fil91] James Allen Fill. Eigenvalue bounds on convergence to stationary for nonreversible Markov chains, with an application to the exclusion process. The Annals of Applied Probability 1(1), 62–87, 1991.
  * [Gan06] Murali Krishnan Ganapathy. Robust Mixing. PhD thesis, University of Chicago, 2006.
  * [GM17] Krystal Guo, Bojan Mohan. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory 85(1), 217–248, 2017.
  * [HLW06] Shlomo Hoory, Nathan Linial, Avi Wigderson. Expander Graphs and Their Applications. Bull. Amer. Math. Soc. 43(4), 439–562, 2006.
  * [JPV22] Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong. Dimension reduction for maximum matchings and the Fastest Mixing Markov Chain. In arXiv:2203.03858, 2022.
  * [KKTY21] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 1159–1170, 2021.
  * [KLLOT13] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan. Improved Cheeger’s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap. In Proceedings of the 45th Annual Symposium on Theory of Computing (STOC), 11–20, 2013.
  * [KLT22] Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung. Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2022.
  * [LS20] Steinar Laenen, He Sun. Higher-order spectral clustering of directed graphs. In Proceedings of 34th Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
  * [LOT12] James R. Lee, Shayan Oveis Gharan, Luca Trevisan. Multi-way spectral partitioning and higher-order Cheeger inequalities. In Proceedings of the 44th Annual Symposium on Theory of Computing (STOC), 1117–1130, 2012.
  * [LP17] Davia Levin and Yuval Peres. Markov chains and mixing times. American Mathematical Society, Volume 107, 2017.
  * [LM18] Pan Li, Olgica Milenkovic. Submodular hypergraphs: $p$-Laplacians, Cheeeger inequalities and spectral clustering. In Proceedings of the 35th International Conference on Machine Learning (ICML), 3014–3023, 2018.
  * [LSZ19] Huan Li, He Sun, Luca Zanetti. Hermitian Laplacians and a Cheeger inequality for the Max-2-Lin problem. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), 71:1–71:14, 2019.
  * [LL15] Jianxi Liu, Xueliang Li. Hermitian-adjacency matrices and Hermitian energies of mixed graphs. Linear Algebra and its Applications 466(1), 182–207, 2015.
  * [Lou15] Anand Louis. Hypergraph Markov operators, eigenvalues and approximation algorthms. In Proceedings of the 47th Annual Symposium on Theory of Computing (STOC), 713–722, 2015.
  * [LRTV12] Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh Vempala. Many sparse cuts via higher eigenvalues. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), 1131–1140, 2012.
  * [LRV13] Anand Louis, Prasad Raghavendra, Santosh Vempala. The complexity of approximating vertex expansion. In Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Secience (FOCS), 360–369, 2013.
  * [Lux07] U. von Luxburg. A tutorial on spectral clustering. Statistics and Computing 17(4), 395–416, 2007.
  * [MMR19] Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn. Performance of Johnson-Lindenstrauss transform for $k$-means and $k$-medians clustering. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), 1027–1038, 2019.
  * [OZ22] Sam Olesker-Taylor, Luca Zanetti. Geometric bounds on the fastest mixing Markov chain. In the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022).
  * [Roc05] Sébastien Roch. Bounding fastest mixing. Electron. Commun. Probab. 10:282–296, 2005.
  * [SM00] Jianbo Shi, Jitendra Malik. Normalized cuts and image segmentation. IEEE Pattern Anal. Mach. Intell., 22(8), 888–905, 2000.
  * [Sim95] Stephen Simons. Minimax theorems and their proofs. Minimax and applications, 1–23, 1995.
  * [Tre09] Luca Trevisan. Max cut and the smallest eigenvalue. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 263–272, 2009.
  * [Yos16] Yuichi Yoshida. Nonlinear Laplacian for digraphs and its applications to network analysis. In Proceedings of the 9th ACM International Conference on Web Search and Data Mining (WSDM), 483–492, 2016.
  * [Yos19] Yuichi Yoshida. Cheeger inequalities for submodular transformations. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2582–2601, 2019.