#  SynDy: Synthetic Dynamic Dataset Generation
Framework for Misinformation Tasks

Michael Shliselberg<EMAIL_ADDRESS>University of
ConnecticutStorrsConnecticutUSA06269 ,  Ashkan Kazemi<EMAIL_ADDRESS>Meedan575 Market St., 4th FloorSan FranciscoCaliforniaUSA94105
0000-0002-2475-1007 ,  Scott A. Hale<EMAIL_ADDRESS>Meedan & University of
Oxford1 St GilesOxfordUKOX1 3JS 0000-0002-6894-4951 and  Shiri Dori-Hacohen
<EMAIL_ADDRESS>University of ConnecticutStorrsConnecticutUSA06269

(2024)

###### Abstract.

Diaspora communities are disproportionately impacted by off-the-radar
misinformation and often neglected by mainstream fact-checking efforts,
creating a critical need to scale-up efforts of nascent fact-checking
initiatives. In this paper we present SynDy, a framework for Synthetic Dynamic
Dataset Generation to leverage the capabilities of the largest frontier Large
Language Models (LLMs) to train local, specialized language models. To the
best of our knowledge, SynDy is the first paper utilizing LLMs to create fine-
grained synthetic labels for tasks of direct relevance to misinformation
mitigation, namely Claim Matching, Topical Clustering, and Claim Relationship
Classification. SynDy utilizes LLMs and social media queries to automatically
generate distantly-supervised, topically-focused datasets with synthetic
labels on these three tasks, providing essential tools to scale up human-led
fact-checking at a fraction of the cost of human-annotated data. Training on
SynDy’s generated labels shows improvement over a standard baseline and is not
significantly worse compared to training on human labels (which may be
infeasible to acquire). SynDy is being integrated into Meedan’s chatbot
tiplines that are used by over 50 organizations, serve over 230K users
annually, and automatically distribute human-written fact-checks via messaging
apps such as WhatsApp. SynDy will also be integrated into our deployed
Co·Insights toolkit, enabling low-resource organizations to launch tiplines
for their communities. Finally, we envision SynDy enabling additional fact-
checking tools such as matching new misinformation claims to high-quality
explainers on common misinformation topics.

weak supervision, distance supervision, misinformation, argument mining, claim
matching, fact-checking

††copyright: acmcopyright††journalyear: 2024††copyright:
rightsretained††conference: Proceedings of the 47th International ACM SIGIR
Conference on Research and Development in Information Retrieval; July 14–18,
2024; Washington, DC, USA††booktitle: Proceedings of the 47th International
ACM SIGIR Conference on Research and Development in Information Retrieval
(SIGIR ’24), July 14–18, 2024, Washington, DC, USA††doi:
10.1145/3626772.3657667††isbn: 979-8-4007-0431-4/24/07††ccs: Information
systems Information retrieval††ccs: Information systems World Wide Web††ccs:
Information systems Web mining

##  1\. Introduction

Misinformation predates the Internet (Altay et al., 2023), but combined with
the ease of producing and re-sharing content, information on the Internet
often spreads without people considering the accuracy of what they see or
share (Pennycook and Rand, 2021; Pantazi et al., 2021). Misinformation is
impactful: it can affect people’s beliefs and attitudes (Lewandowsky et al.,
2017), how they vote (Vaccari and Morini, 2014), health choices such as
vaccination (Jamieson et al., 2021; Pierri et al., 2022; Ferreira Caceres et
al., 2022), and (in)action to confront the climate emergency (Benegal and
Scruggs, 2018). Despite repeated efforts, there are no purely automated
systems that successfully and accurately fact-check content (Arnold, 2020;
Graves, 2018); thus, best practice has shifted from attempts to improve
automated fact-checking to building automated tools supporting human fact-
checking efforts, such as by matching misinformation claims to existing fact-
checks (claim matching) (Kazemi et al., 2021).

Figure 1. A mockup of the Co·Insights dashboard (built atop Meedan’s existing
Check platform) with a new “Narrative Category” column that will be enabled by
SynDy’s LLM-generated topic annotations. This, in turn, enables linking to
preemptive explainer content in response to end user fact-checking queries on
our AAPI nonprofits’ dedicated misinformation tiplines.

Misinformation targeting diaspora communities is often off the radar of
mainstream fact-checking organizations in both host and home countries. For
example, the 2017 measles outbreak disproportionately killed more Somali
Americans than any other ethnicity group as a result of their Minneapolis
community being targeted with anti-vaccine misinformation (Leslie et al.,
2018; Dyer, 2017). While many diaspora communities have formed initiatives to
counter misinformation, these community efforts are smaller and lower
resourced than mainstream efforts, and there is a critical need for technology
to help scale their work. Transformer models are useful for a variety of tasks
with lower costs and faster throughput than larger frontier models.
Nonetheless, it is unreasonable to expect such models to perform well off-the-
shelf on the emerging, low resource, and/or out-of-domain topics that are of
relevance to diaspora communities. Furthermore, obtaining annotated data may
be difficult, costly, time-consuming, or risk vicarious trauma for annotators.

In this demo paper we present SynDy, a framework enabling organizations,
especially small and/or low-resourced ones, to leverage generative large
language models (LLMs) to train local models to perform misinformation-related
tasks, reducing the need for costly, time-consuming, and possibly harmful
manual annotation. To the best of our knowledge, SynDy is the first paper
utilizing LLMs to create fine-grained synthetic labels for tasks relevant to
misinformation mitigation, namely Claim Matching, Topical Clustering, and
Claim Relationship Classification. As we explain below, each of these tasks is
an essential tool to mitigate misinformation by scaling up the impact of
human-led fact-checking. Our demonstration video and codebase are both
available online.111Backend: https://github.com/RIET-lab/syndy-service; UI:
https://github.com/RIET-lab/syndy-ui; Demo Video:
https://bit.ly/syndyDemoVideo

##  2\. Team, Project, and Audience

SynDy was developed by the Reducing Information Ecosystem Threats (Riet) Lab
and Meedan as part of Co·Insights, a large-scale misinformation mitigation
initiative funded by the NSF Convergence
Accelerator.222https://meedan.com/project/co-insights The Riet Lab at the
University of Connecticut focuses on threats to the online ecosystem from an
information retrieval lens. Meedan is a global technology non-profit that
builds software and programmatic initiatives to strengthen journalism, digital
literacy, and information accessibility online and off. Meedan develops open-
source tools for creating and sharing context on digital media through
annotation, verification, archival, and translation. Led by Meedan,
Co·Insights is a unique platform that enables a community-led approach to
identify, preempt, and respond to misinformation in minoritized communities.
Co·Insights is co-developed with: Asian American & Pacific Islander (AAPI)
organizations operating in the fact-checking space (Piyaoba, Tayo, Viet Fact
Check, and DesiFacts)333https://www.piyaoba.org/ ; https://www.tayohelp.com/ ;
https://vietfactcheck.org/ ; https://vietfactcheck.org/ ;
https://www.desifacts.org/ and universities (the Annenberg Public Policy
Center (APPC) at the University of Pennsylvania, University of Massachusetts
Amherst, University of Connecticut, Rutgers University, and University of
Colorado Boulder).

As with Meedan’s other misinformation mitigation tools, the intended audience
for SynDy is fact-checkers, journalists, and community organizations,
including especially our Co·Insights partners. Meedan supports over 75 partner
organizations, developing technology for newsrooms, fact-checkers, public
health professionals, and NGOs. In 2022 alone, Meedan’s software served 237K
audience members by sending them 200K fact-checks, facilitating 419K
conversations with fact-checkers, and matching 43K claims to existing fact-
checks (Meedan, Inc., 2022).

Figure 2. A schematic showing the SynDy framework and how it fits within the
larger Co·Insights initiative. SynDy’s output is an LLM-annotated dataset
which includes labeled tuples for post-claim, post-topic, and claim-claim-
relationships labeled as $\\{Support,Undermine\\}$. The labels are then
utilized as training data to improve misinformation-related tasks. The Dataset
Annotation stage can be applied to social media datasets beyond those selected
by SynDy.

##  3\. Motivating Challenges

SynDy arose from our partners’ pain points, with the goal of better serving
them and their communities. We aim to address two real-world challenges:
neglected topics in mainstream misinformation response efforts and scaling
response efforts to narrative themes; these challenges demand fine-tuned
models for a few misinformation-related tasks.

Challenge #1: Neglected Topics in Mainstream Misinformation Mitigation.
Co·Insights commenced with extensive customer discovery (Blank and Dorf, 2020)
with our AAPI organizations. We learned that misinformation content targeting
their communities is too often out-of-sight from mainstream response efforts.
Such content is in languages, regarding topics, and spreads on platforms
beyond those usually considered in the US. SynDy’s main objective, therefore,
is to improve coverage and performance of fact-checking pipelines,
specifically on emerging and/or niche topics where training data is neither
readily available nor easy to procure. SynDy was also designed with the goal
of full integration into Meedan’s existing, claim matching pipelines and
chatbot tiplines.

Challenge #2: Scaling Misinformation Efforts to Narrative Themes. APPC
highlighted to us a challenge with current human-led fact-checking efforts:
they tend to address claims one at a time after they appear, i.e., in a
reactive way. Looking at claims in isolation in this manner results in less
effective debunking: by the time interventions occur claims are widespread.
However, claims do not exist in isolation (Ophir and Jamieson, 2021; Scales et
al., 2021), but rather within a larger framework of recurring narrative and
topical themes, and even in fairly predictable patterns (Full Fact, 2019). By
mapping individual claims to these larger “narrative clusters,” we can move
away from the current reactive model to a new proactive model where context
explainers, preemptive knowledge (“pre-bunking” (Lewandowsky and Van Der
Linden, 2021)), conversation guides, and media literacy materials can be
produced and disseminated before harmful claims spread widely. Since one
narrative usually encompasses multiple claims, this approach can greatly
increase the relevance and impact of each misinformation intervention. Our
AAPI partner organizations have identified the “green card backlog,” “zero-
dollar shopping,” and affirmative action (specifically w/r/t AAPI communities)
as topics that could benefit from this approach. Therefore, SynDy is also
driven by a vision of enabling new misinformation tools to map individual
claims to narrative themes (see Figure 1) and facilitate pre-bunking.

Relevant Misinformation Tasks. We set out to improve upon zero-shot
performance for three misinformation-related tasks: Claim Matching, Topical
Clustering, and Claim Relationship Classification. First, Claim Matching
algorithms match new pieces of social media content to existing fact-checks
(Shaar et al., 2020; Kazemi et al., 2021). However, in-the-wild performance of
claim matching usually degrades compared to performance on benchmark datasets
like CheckThat! (Nakov et al., 2021) due to the continual, ongoing evolution
of misinformation requiring the continual retraining of models. Topical
Clustering allows us to match claims to prewritten, high-quality explainers on
common topics anticipated by experts as discussed in Challenge 2 above.
Finally, Claim Relationship Classification helps human fact-checkers
understand and prioritize what misinformation claims to address, based on
which claims support or undermine one another. Crucially, discerning that such
relationships exist does not rely on the need to determine the veracity of
claims, but relies only on the connections between claims. Though similar to
stance detection, we emphasize connections between claims, rather than the
reaction of a subject to a claim, as in most Stance Detection tasks. Taken
together, these tasks represent essential tools to mitigate misinformation by
scaling up the impact of human-led fact-checking. We also envision them
enabling new tools, representing a critical next step for the evolution of
fact-checking.

##  4\. Proposed Framework

We propose a framework for Synthetic Dynamic Dataset Generation (SynDy) that
leverages the recent advances in LLMs (OpenAI, 2023; Ouyang et al., 2022) to
create distantly-supervised, automatically labeled training datasets (despite
these models’ well-documented limitations (see, e.g., Chiesurin et al.,
2023)). SynDy employs LLMs and leverages prompt engineering in various
subtasks, chiefly to extract annotations from social media posts. As a proof
of concept, we implemented SynDy both with Python scripts that run locally,
and with scalable AWS infrastructure. Figure 2 show the SynDy framework,
composed of two main steps: Dataset Selection and Dataset Annotation, in the
context of the Co·Insights project’s broader misinformation mitigation
efforts.

Dataset Selection. We receive a topic as input and produce a set of social
media posts on that topic as output, predicated on the availability of some
form of query language and social media API (e.g., X/Twitter, Reddit,
etc.).444Alternatively, the dataset could be externally supplied and the
selection step skipped. In our experiments, we used the Reddit API. We perform
keyword generation for the topic to construct social media API queries. While
keyword extraction can be performed in a variety of ways, in our experiments
we provide the stated topic to the GPT-3.5-Turbo API with a prompt to generate
two groups of topical keywords: heavily associated keywords that are largely
indicative of the topic and lesser associated keywords that can be associated
with the topic but are not mutually exclusive. We then create a collection of
queries by sampling one from the former and two from the latter and joining
them via AND clauses.

Synthetic Dataset Annotation. To generate synthetic labels for social media
datasets, we take advantage of LLMs’ strength in lexical and semantic
capabilities, rather than domain knowledge (thus significantly reducing the
risks of fabrications (Emsley, 2023; Hatem et al., 2023)). We constructed
specialized prompts through a mixture of following community tips and
iterative testing.555Prompts are omitted for space considerations, but are
available in our codebase. Figure 2 shows how we utilize LLM queries to
generate labeled tuples for claim extraction, topic clustering, and claim
relation classification. The former two tasks receive individual posts as
input and provide tuples of the form $(Post,Label)$. For Relation
Classification, we need to output source and target claims and their
corresponding relationship (support/undermine). This task receives the
synthetically-labeled $(Post,Claim)$ tuples as input; we then use GPT to
generate, for each claim extracted in the previous step, the following two
items in the tuple. Finally, a Semantic Clustering step helps tackle the issue
of different inputs producing reworded but semantically-identical outputs. We
utilize a pretrained sentence transformer (SentenceT5-Large) to map all
targets/claims into a dense space and cluster closely packed ones into a
single target. The clusters are defined deterministically,where all node pairs
with a similarity score above some threshold $\tau$ (which we set at 0.95) are
within the same cluster.

##  5\. Experimental Setup

We set out to evaluate whether SynDy-labeled datasets could be used as
training data for misinformation-related tasks. Specifically, we want to
evaluate whether they could (a) improve upon zero-shot settings and (b) be
substituted for human annotations as training data for these tasks. To that
end, we use several preexisting datasets to compare an off-the-shelf baseline
and fine-tuned models using either SynDy-generated synthetic labels or human-
labeled data. We evaluate the results on human-labeled data. For Claim
Matching, we use the CheckThat!2022 dataset for spotting fact-checked claims
in tweets (Nakov et al., 2022). For Topical Clustering, we use the Cardiff NLP
multiple-topic dataset (Antypas et al., 2022) and the Perspectrum Dataset’s
topics (Chen et al., 2019), both of which are provided in the form of
topic–tweet pairs. Model training for both these tasks involve fine-tuning
SentenceT5-Large (Ni et al., 2021), and evaluating with Mean Average Precision
(MAP). For Claim Relation Classification, we again use the Perspectrum Dataset
in its claim and perspective portion, which provides claim-to-claim
relationships with a $\\{Support,Undermine\\}$ label. Here, we use a cross-
encoder, encoding both the source and target together. Training involves fine-
tuning Roberta-Large (Liu et al., 2019). We use Macro F1 to evaluate the claim
relationship, as is common in similar tasks such as stance detection and
entailment. We omit further configuration details for space considerations,
but our codebase is available.

##  6\. Results

| Train Sets
---|---
Test Sets | Baseline | Human Labels | Synthetic Labels
CheckThat!’22 | .824 | .927 | .927
CardiffNLP | .660 | .753 | .702
Pers.-Clustering | .793 | .800 | .828
Pers.-Classification | – | .907 | .863

Table 1. Experiment results for claim matching (MAP@20; row 1), topical
clustering (MAP@20; rows 2 & 3), and claim relationship classification (F1
Macro; row 4) tasks. Baseline for matching & clustering is SentenceT5-Large
with no task-specific training.

Results are presented in Table 1. Across both the Claim Matching and Topic
Clustering tasks, our fine-tuned models utilizing SynDy outperformed the
Sentence-T5-Large baseline, which was SynDy’s explicit goal. In the Claim
Matching experiment, our generated and original train sets achieve similar
MAP@20, both markedly improving over the pretrained model. In the context of
Topical Clustering, the model fine-tuned on synthetic data slightly trails
human annotated fine-tuning for the CardiffNLP dataset; perhaps surprisingly,
on the Perspectrum-Topics dataset, training on the synthetic dataset actually
improved performance above training on human data, possibly due to the higher
number of annotations SynDy generated. Finally, for Claim Relation
Classification, training on SynDy-generated labels yields a Macro-F1 of 0.863,
which is lower than the 0.907 from the original dataset, but still promising.
Across all tasks, models trained on synthetic labels perform no worse than
-6.8% relative to models trained on human annotated datasets, and provide a
minimum 4.4% (on Perspectrum topical clustering) and maximum 12.5% (on
CheckThat!’22 claim matching) relative improvement over a zero-shot baseline
across different experimental settings. Overall, models trained on SynDy-
generated labels demonstrate comparable performance to training on human-
annotated data.

##  7\. Conclusion

In this demonstration paper, we presented SynDy, a distantly-supervised
framework for automatically generating datasets with synthetic labels, with
the goal of improving coverage and precision of misinformation related tasks.
Specifically, we focused on Claim Matching, Topical Clustering, and Claim
Relation Classification. We demonstrated that on these tasks, SynDy-generated
datasets and synthetic labels can compete with human annotations. We leave
more direct comparisons of LLM-generated labels to human-annotated labels, the
task of narrative theme matching, and cross-lingual challenges to future work.
SynDy supports misinformation response efforts in an ever changing information
environment.

### Acknowledgements

We thank our collaborators on Co·Insights for inspiring SynDy and extensive
feedback; Aidan Kierans for LaTeX assistance; and our anonymous reviewers for
thoughtful feedback. This material is based in part upon work supported by the
National Science Foundation Convergence Accelerator (contract 49100421C0035),
by the National Science Foundation Program on Fairness in Artificial
Intelligence in Collaboration with Amazon (#IIS-2147305), and by a grant from
The Alan Turing Institute. Any opinions, findings and conclusions or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation or The
Alan Turing Institute.

## References

  * (1)
  * Altay et al. (2023) Sacha Altay, Manon Berriche, and Alberto Acerbi. 2023.  Misinformation on Misinformation: Conceptual and Methodological Challenges.  _Social Media + Society_ 9, 1 (2023).  https://doi.org/10.1177/20563051221150412
  * Antypas et al. (2022) Dimosthenis Antypas, Asahi Ushio, José Camacho-Collados, Leonardo Neves, V’itor Silva, and Francesco Barbieri. 2022.  Twitter Topic Classification.  _ArXiv_ abs/2209.09824 (2022).
  * Arnold (2020) Phoebe Arnold. 2020.  The challenges of online fact checking.  _Full fact_ 17 (2020).
  * Benegal and Scruggs (2018) Salil D. Benegal and Lyle A. Scruggs. 2018.  Correcting misinformation about climate change: the impact of partisanship in an experimental setting.  _Climatic Change_ 148, 1 (2018), 61–80.  https://doi.org/10.1007/s10584-018-2192-4
  * Blank and Dorf (2020) Steve Blank and Bob Dorf. 2020.  _The startup owner’s manual: The step-by-step guide for building a great company_.  John Wiley & Sons.
  * Chen et al. (2019) Sihao Chen, Daniel Khashabi, Wenpeng Yin, Chris Callison-Burch, and Dan Roth. 2019.  Seeing Things from a Different Angle: Discovering Diverse Perspectives about Claims.  _CoRR_ abs/1906.03538 (2019).  arXiv:1906.03538 http://arxiv.org/abs/1906.03538
  * Chiesurin et al. (2023) Sabrina Chiesurin, Dimitris Dimakopoulos, Marco Antonio Sobrevilla Cabezudo, Arash Eshghi, Ioannis Papaioannou, Verena Rieser, and Ioannis Konstas. 2023.  The Dangers of trusting Stochastic Parrots: Faithfulness and Trust in Open-domain Conversational Question Answering.  arXiv:2305.16519 [cs.CL]
  * Dyer (2017) Owen Dyer. 2017.  Measles outbreak in Somali American community follows anti-vaccine talks.  _BMJ_ 357 (2017).  https://doi.org/10.1136/bmj.j2378 arXiv:https://www.bmj.com/content/357/bmj.j2378.full.pdf
  * Emsley (2023) Robin Emsley. 2023.  ChatGPT: these are not hallucinations–they’re fabrications and falsifications.  _Schizophrenia_ 9, 1 (2023), 52.
  * Ferreira Caceres et al. (2022) Maria Mercedes Ferreira Caceres, Juan Pablo Sosa, Jannel A Lawrence, Cristina Sestacovschi, Atiyah Tidd-Johnson, Muhammad Haseeb Ui Rasool, Vinay Kumar Gadamidi, Saleha Ozair, Krunal Pandav, Claudia Cuevas-Lou, Matthew Parrish, Ivan Rodriguez, and Javier Perez Fernandez. 2022.  The impact of misinformation on the COVID-19 pandemic.  _AIMS Public Health_ 9, 2 (2022).  https://doi.org/10.3934%2Fpublichealth.2022018
  * Full Fact (2019) Full Fact. 2019.  Report on the Facebook Third Party Fact Checking programme.
  * Graves (2018) D Graves. 2018.  Understanding the promise and limits of automated fact-checking.  _Reuters Institute for the Study of Journalism_ (2018).
  * Hatem et al. (2023) Rami Hatem, Brianna Simmons, and Joseph E. Thornton. 2023.  Chatbot Confabulations Are Not Hallucinations.  _JAMA Internal Medicine_ 183, 10 (10 2023), 1177–1177.  https://doi.org/10.1001/jamainternmed.2023.4231
  * Jamieson et al. (2021) Kathleen Hall Jamieson, Daniel Romer, Patrick E. Jamieson, Kenneth M. Winneg, and Josh Pasek. 2021.  The role of non–COVID-specific and COVID-specific factors in predicting a shift in willingness to vaccinate: A panel study.  _Proceedings of the National Academy of Sciences_ 118, 52 (2021), e2112266118.  https://doi.org/10.1073/pnas.2112266118 arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.2112266118
  * Kazemi et al. (2021) Ashkan Kazemi, Kiran Garimella, Devin Gaffney, and Scott Hale. 2021.  Claim Matching Beyond English to Scale Global Fact-Checking. In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_. Association for Computational Linguistics, Online, 4504–4517.  https://doi.org/10.18653/v1/2021.acl-long.347
  * Leslie et al. (2018) Timothy F. Leslie, Paul L. Delamater, and Y. Tony Yang. 2018.  It could have been much worse: The Minnesota measles outbreak of 2017.  _Vaccine_ 36, 14 (2018), 1808–1810.  https://doi.org/10.1016/j.vaccine.2018.02.086
  * Lewandowsky et al. (2017) Stephan Lewandowsky, Ullrich K.H. Ecker, and John Cook. 2017.  Beyond Misinformation: Understanding and Coping with the “Post-Truth” Era.  _Journal of Applied Research in Memory and Cognition_ 6, 4 (2017), 353–369.  https://doi.org/10.1016/j.jarmac.2017.07.008
  * Lewandowsky and Van Der Linden (2021) Stephan Lewandowsky and Sander Van Der Linden. 2021.  Countering misinformation and fake news through inoculation and prebunking.  _European Review of Social Psychology_ 32, 2 (2021), 348–384.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  RoBERTa: A Robustly Optimized BERT Pretraining Approach.  _CoRR_ abs/1907.11692 (2019).  arXiv:1907.11692 http://arxiv.org/abs/1907.11692
  * Meedan, Inc. (2022) Meedan, Inc. 2022.  Annual Report 2022.  https://meedan.com/post/annual-report-2022
  * Nakov et al. (2022) Preslav Nakov, Alberto Barrón-Cedeño, Giovanni Da San Martino, Firoj Alam, Julia Maria Struß, Thomas Mandl, Rubén Míguez, Tommaso Caselli, Mucahid Kutlu, Wajdi Zaghouani, Chengkai Li, Shaden Shaar, Gautam Kishore Shahi, Hamdy Mubarak, Alex Nikolov, Nikolay Babulkov, Yavuz Selim Kartal, Javier Beltrán, Michael Wiegand, Melanie Siegel, and Juliane Köhler. 2022.  Overview of the CLEF-2022 CheckThat! Lab on Fighting the COVID-19 Infodemic and Fake News Detection. In _Proceedings of the 13th International Conference of the CLEF Association: Information Access Evaluation meets Multilinguality, Multimodality, and Visualization_ _(CLEF ’2022)_. Bologna, Italy.
  * Nakov et al. (2021) Preslav Nakov, Giovanni Da San Martino, Tamer Elsayed, Alberto Barrón-Cedeño, Rubén Míguez, Shaden Shaar, Firoj Alam, Fatima Haouari, Maram Hasanain, Watheq Mansour, Bayan Hamdan, Zien Sheikh Ali, Nikolay Babulkov, Alex Nikolov, Gautam Kishore Shahi, Julia Maria Struß, Thomas Mandl, Mücahid Kutlu, and Yavuz Selim Kartal. 2021.  Overview of the CLEF-2021 CheckThat! Lab on Detecting Check-Worthy Claims, Previously Fact-Checked Claims, and Fake News.  _CoRR_ abs/2109.12987 (2021).  arXiv:2109.12987 https://arxiv.org/abs/2109.12987
  * Ni et al. (2021) Jianmo Ni, Gustavo Hernández Ábrego, Noah Constant, Ji Ma, Keith B. Hall, Daniel Cer, and Yinfei Yang. 2021.  Sentence-T5: Scalable Sentence Encoders from Pre-trained Text-to-Text Models.  _CoRR_ abs/2108.08877 (2021).  arXiv:2108.08877 https://arxiv.org/abs/2108.08877
  * OpenAI (2023) OpenAI. 2023.  GPT-4 Technical Report.  arXiv:2303.08774 [cs.CL]
  * Ophir and Jamieson (2021) Yotam Ophir and Kathleen Hall Jamieson. 2021.  The effects of media narratives about failures and discoveries in science on beliefs about and support for science.  _Public Understanding of Science_ 30, 8 (2021), 1008–1023.  https://doi.org/10.1177/09636625211012630 PMID: 34000907.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. 2022.  Training language models to follow instructions with human feedback.  arXiv:2203.02155 [cs.CL]
  * Pantazi et al. (2021) Myrto Pantazi, Scott Hale, and Olivier Klein. 2021.  Social and Cognitive Aspects of the Vulnerability to Political Misinformation.  _Political Psychology_ 42, S1 (Dec. 2021), 267–304.  https://doi.org/10.1111/pops.12797
  * Pennycook and Rand (2021) Gordon Pennycook and David G. Rand. 2021.  The Psychology of Fake News.  _Trends in Cognitive Sciences_ 25, 5 (May 2021), 388–402.  https://doi.org/10.1016/j.tics.2021.02.007
  * Pierri et al. (2022) Francesco Pierri, Brea L. Perry, Matthew R. DeVerna, Kai-Cheng Yang, Alessandro Flammini, Filippo Menczer, and John Bryden. 2022.  Online misinformation is linked to early COVID-19 vaccination hesitancy and refusal.  _Scientific Reports_ 12, 1 (2022).  https://doi.org/10.1038/s41598-022-10070-w
  * Scales et al. (2021) David Scales, Jack Gorman, and Kathleen H. Jamieson. 2021.  The Covid-19 Infodemic — Applying the Epidemiologic Model to Counter Misinformation.  _New England Journal of Medicine_ (2021).  https://doi.org/10.1056/NEJMp2103798
  * Shaar et al. (2020) Shaden Shaar, Nikolay Babulkov, Giovanni Da San Martino, and Preslav Nakov. 2020.  That is a Known Lie: Detecting Previously Fact-Checked Claims. In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_. Association for Computational Linguistics, Online, 3607–3618.  https://doi.org/10.18653/v1/2020.acl-main.332
  * Vaccari and Morini (2014) Cristian Vaccari and Marco Morini. 2014.  The Power of Smears in Two American Presidential Campaigns.  _Journal of Political Marketing_ 13, 1-2 (2014), 19–45.  https://doi.org/10.1080/15377857.2014.866021


# Remarks on the Spectral Approach to Finding Short Paths

Kelly Yancey and Matthew P. Yancey Institute for Defense Analyses / Center for
Computing Sciences (IDA / CCS<EMAIL_ADDRESS>for Defense
Analyses / Center for Computing Sciences (IDA / CCS<EMAIL_ADDRESS>
###### Abstract

We are interested in the general question: to what extent are the spectral
properties of a graph connected to the distance function? Our motivation is a
concrete example of this question that is due to Steinerberger. We provide
some negative results via constructions of families of graphs where the
spectral properties disagree with the distance function in a manner that
answers many of the questions posed by Steinerberger. We also provide a
positive result by replacing Steinerberger’s set-up with conditions involving
graph curvature.

##  1 Introduction

We assume connected graph $G$ with vertex set $V$ and edge set $E$ is fixed.
We will use the notation $V=\\{1,2,\ldots,n\\}$. The Laplacian of $G$ is
$L=D-A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree
matrix. We assume some vertex $i$ is fixed, which we will call _the special
vertex_. Let $L_{i}$ denote the minor of $L$ formed by removing row $i$ and
column $i$. The length of a path is the number of edges it contains.

The eigenvector associated to the second smallest eigenvalue of $L$ is called
the Fiedler vector. When appropriately normalized, the Fiedler
vector—interpreted as a function $f:V\rightarrow\mathbb{R}$—is known to be a
solution to the optimization problem

$\min_{\|g\|_{2}=1,0=\sum_{j}g(j)}\sum_{jk\in E}|g(k)-g(j)|^{2}.$ (1)

We define $V_{i}=V\setminus\\{i\\}$, and let
$f_{i}:V_{i}\rightarrow\mathbb{R}$ be the eigenvector associated to the
smallest eigenvalue of $L_{i}$. Steinerberger [4] recently posed many
questions about the relationship between the values of $f_{i}$ and the set
shortest paths in $G$ with endpoint $i$. In this connection, the function
$f_{i}$ is lifted to have domain $V$ by setting $f_{i}(i)=0$. This lift allows
us to describe $f_{i}$ as the solution to an optimization problem that
resembles the characterization of the Fiedler vector of the Laplacian: $f_{i}$
is a solution to

$\min_{\|g\|_{2}=1,0=g(i)}\sum_{jk\in E}|g(k)-g(j)|^{2}.$ (2)

To facilitate the connection between $f_{i}$ and the shortest paths beginning
at $i$, Steinerberger proved several results about $f_{i}$.

Let $G-i$ denote the graph $G$ after vertex $i$ is deleted. If $G-i$ is not
connected, then the problem of finding paths in $G$ can be separated into
independent sub-problems.

######  Theorem 1.1 ([4]).

If $G-i$ is connected, then the following are true about $f_{i}$.

  * •

If $f_{i}(u)>0$ for some vertex $u$, then $f_{i}(u^{\prime})>0$ for all
$u^{\prime}\in V_{i}$. By multiplying all values of $f_{i}$ by $-1$, we will
assume for the rest of the paper that $f_{i}$ is positive over $V_{i}$.

  * •

For $u\in V_{i}$, there exists a $u^{\prime}\in N(u)$ (possibly
$u^{\prime}=i$) such that $f_{i}(u^{\prime})<f_{i}(u)$.

By the above results, for each $i$ one can construct a spanning tree $T_{i}$
of $G$ by connecting each vertex of $V_{i}$ to the neighbor that minimizes
$f_{i}$. We will call the unique path in $T_{i}$ from $j$ to $i$ the _spectral
path from $j$ to $i$_, which is not necessarily the same collection of edges
and vertices as the spectral path from $i$ to $j$. Steinerberger [4] gave
ample empirical evidence that a spectral path is commonly also a shortest path
between two vertices, and frequently has length that exceeds the distance
between the endpoints by a small bound. The _symmetric spectral path between
$i$ and $j$_ is the shorter of the spectral path from $i$ to $j$ and the
spectral path from $j$ to $i$ (if they are the same length, chose among them
arbitrarily).

Using a spectral path to find a short (if not shortest) path between vertices
in a graph was motivated by Steinerberger as a discretization of a process in
partial differential equations (PDE) about which several important questions,
like the “Hot Spots conjecture,” remain open. The hope is that a better
understanding of spectral paths in graphs might possibly translate into new
results in PDE. Steinerberger mentioned many different ideas that deserved
exploration—in [4] there are six open problems in Section 2.6 and two more in
Section 3.3. The main result of this paper is to resolve a majority of these
questions, which we summarize as a single question next.

######  Question 1.2 ([4]).

Are there graphs such that, for some pair of vertices $i\neq j$, the spectral
path from $i$ to $j$ is $c$-times the distance between $i$ and $j$ for any
$c>1$? This question can be weakened in four senses. First, what if we
restrict to planar graphs? Second, what if vertices $i$ and $j$ are chosen
randomly (in other words, does the bound hold for all but an asymptotically-
small subset of pairs $\\{i,j\\}$)? Third, can we at least bound the length of
the symmetric spectral path? Finally, can the length of a spectral path be
bounded as a multiple of the diameter of the space?

We will give a negative answer to Question 1.2 (including all four
relaxations) by constructing families of graphs where spectral paths are
unboundedly long between pairs of vertices at bounded distance apart.

We also have a positive result, which partially answer Question 6 of Section
2.6 in [4], which asks for “effective variants” of Steinerberger’s set-up. Our
approach to achieving a positive result is to incorporate the field of _graph
curvature_ , which is the study of discretizations of various algebraic and
geometric definitions of a curved space. Our result connects the distance
between two vertices with the length of a path formed by locally-optimal
choices over a spectral function, although we use a different spectral
formulation than (2). In particular, we replace the Fiedler vector of the
Laplacian with the “spread” of a graph, which we will define in Section 3 (its
connection to the Fiedler vector of a Laplacian is described in Section 1.3 of
[5]).

Of the eight questions stated in [4], this collection of results leaves only
one fully open: Question 4 of Section 2.6 in [4] asks about the computational
efficiency of spectral paths.

We will construct the family of graphs that answer Question 1.2 in Section 2.
We will prove our positive result and ask a question that could lead to
another positive result in Section 3.

##  2 Constructions

The empirical results in [4] showed that the spectral paths were short on
random graphs; the spectral paths had small inefficiencies on “deterministic
graphs.” Our families of graphs will be highly structured. Our approach to
analyzing the affect of these structures on spectral paths will be common
among the different graph families we consider. Thus, the core arguments that
will be repeated are combined and presented in Section 2.1. Although only a
subsection, Section 2.1 is by far the largest part of this paper and with the
most sophisticated arguments. We construct three graph families, which are
presented in each of Sections 2.2, 2.3, and 2.4, respectively.

###  2.1 Using Symmetries to Simulate Weights

A graph automorphism is a bijection $\pi:V\rightarrow V$ such that $xy\in E$
if and only if $\pi(x)\pi(y)\in E$.

######  Theorem 2.1.

The eigenvector $f_{i}$ is the unique eigenvector of $L_{i}$ where each
coordinate is nonnegative. This implies that for any graph automorphism $\pi$
that is fixed on $i$, we have that $f_{i}$ is invariant under $\pi$.

###### Proof.

It is folklore that because $L$ is symmetric and real (and therefore
Hermitian), its eigenvectors are real-valued and pairwise orthogonal. The
assumptions of the previous sentence also apply to $L_{i}$, and therefore so
does the conclusions. By Theorem 1.1 $f_{i}$ is positive over all coordinates
in $V_{i}$. Any nonzero real vector that is orthogonal to $f_{i}$ must have a
negative coordinate, implying that $f_{i}$ is the unique nonnegative
eigenvector. If $\pi$ is a graph automorphism that fixes $i$, then
$f_{i}\circ\pi$ is a positive eigenvector of $L_{i}$ (with the same eigenvalue
as $f_{i}$). By the uniqueness of $f_{i}$, this implies $f_{i}\circ\pi=f_{i}$.
∎

In this subsection, we will show how to generalize the current set up to
account for both vertex weights and edge weights. The edge weights take the
form of a symmetric function $w_{E}:V\times V\rightarrow\mathbb{R}_{\geq 0}$
that satisfies $w_{E}(u,v)=0$ if $uv\notin E$. The vertex weights take the
form of a function $w_{V}:V\rightarrow\mathbb{R}_{\geq 0}$ with at least one
positive value. For a function $g:V\rightarrow\mathbb{R}$, we define
$\|g\|_{w}:=\sqrt{\sum_{u\in V}w_{V}(u)g(u)^{2}}$. In the weighted version,
the function $f_{i}$ is a function that solves the optimization problem

$\min_{\|g\|_{w}=1,0=g(i)}\sum_{jk\in E}w_{E}(j,k)|g(k)-g(j)|^{2}.$ (3)

It should be pointed out that we have not proven that $f_{i}$ is unique
(although we will prove this under modest assumptions in Theorem 2.10) so
$f_{i}$ is to be treated as some arbitrary solution.

Observe that in the above statement, the original unweighted version can be
recovered when the weight of each edge and vertex is set to $1$. Importantly,
we still consider the length of a path to be the number of edges it contains.
Because this choice is atypical of the field, let us emphasize that the length
of a path is independent of the weight functions. When computing $f_{i}$, we
can assume that all edges have positive weight, as deleting them will not
affect (3). However, they still play a role in determining the distance
between vertices.

Question 1.2 is not interesting for weighted graphs, as any induced path in
any graph can be made a symmetric spectral path by giving the corresponding
edges sufficiently large weight. We introduce weights because the spectral
paths of some large unweighted graphs can be determined by reducing the
problem to smaller graphs with weights.

Let $u\sim_{i}v$ denote the relation between vertices in $u,v\in V_{i}$ that
there exists a graph automorphism $\pi$ that fixes $i$ and $\pi(u)=v$. Because
graph automorphisms are closed under inverses and compositions, $\sim_{i}$
forms an equivalence relation. We construct weighted graph $G_{i}$ from $G$ by
creating a bijection between the vertices of $G_{i}$ and the
$\sim_{i}$-equivalence classes of $G$. Let $\phi_{i}:V(G)\rightarrow V(G_{i})$
be the mapping such that $\phi_{i}$ maps each vertex to the equivalence class
containing that vertex. The weight functions of $G_{i}$ are defined as
follows: $w_{V}(u)=|\phi_{i}^{-1}(u)|$ and $w_{E}(uv)$ is the number of edges
with an endpoint in $\phi^{-1}(u)$ and the other endpoint in $\phi^{-1}(v)$.
Let $\widehat{f}_{i}$ be a solution to the optimization problem (3) over
$G_{i}$ with special vertex $\phi_{i}(i)$. We omit the proof to the following
theorem, as it clearly follows from Theorem 2.1 and the construction of
$G_{i}$.

######  Theorem 2.2.

If each $\sim_{i}$-equivalence class of $G$ contains no edges, then we can
construct111We allow the non-uniqueness of $f_{i}$ to correspond with the
possibly non-uniqueness of $\widehat{f}_{i}$. $f_{i}$ from $\widehat{f}_{i}$
by setting $f_{i}(j)=\widehat{f}_{i}(\phi_{i}(j))$ for each $j\in V$.

We now proceed to study the function $f_{i}$ in this weighted context; for the
rest of the subsection we assume $G$ is a weighted graph. The function $w_{E}$
is represented in matrix form as $W_{E}$ and the function $w_{V}$ is
represented as diagonal matrix $W_{D}$. The degree of a vertex $k$ is defined
to be $d(k):=\sum_{j\in V}w_{E}(kj)$. The Laplacian for a graph with edge
weights is $L=D-W_{E}$.

We define a function $c$ when $\|g\|_{w}>0$ as

$c(w_{V},w_{E},g)=\frac{\sum_{jk\in
E}w_{E}(k,j)|g(k)-g(j)|^{2}}{\|g\|_{w}^{2}}.$ (4)

A function that solves optimization problem (3) for fixed $w_{V},w_{E}$ is
characterized as the function $g/\|g\|_{w}$ where $g$ minimizes
$c(w_{V},w_{E},g)$ under the criteria $g(i)=0$. Let $g_{i}\in\mathbb{R}^{n-1}$
be the vector representation of $g$ restricted to $V_{i}$, and let $W_{V,i}$
be $W_{V}$ with row $i$ and column $i$ deleted. Observe that when $g(i)=0$ we
have

$c(w_{V},w_{E},g)=\frac{g_{i}^{T}L_{i}g_{i}}{g_{i}^{T}W_{V,i}g_{i}}.$

We say that a graph is “positively connected” if there exists a path between
any two vertices using only edges with positive weights.

######  Proposition 2.3.

If $G$ is positively connected, then $L_{i}$ is positive definite.

###### Proof.

If $M$ is symmetric and real, then for $M$ to be positive definite it is
necessary and sufficient that for any nonzero real vector $x$ we have
$x^{T}Mx>0$. Let us interpret $x$ as a function from $V_{i}$ to $\mathbb{R}$
instead of a vector $\mathbb{R}^{V_{i}}$. Next, we lift $x$ to $x_{*}$ which
domain $V$ by setting $x_{*}(i)=0$. Under this setting, we have
$x^{T}L_{i}x=\sum_{jk\in E}w_{E}(j,k)(x_{*}(k)-x_{*}(j))^{2}$. Because $x$ is
a nonzero vector, there is some index $j$ such that $x(j)\neq 0$. By the
assumption, there exists a path $i=u_{1},u_{2},\ldots,u_{k}=j$ using only
positively weighted edges. Let $t$ be the smallest index such that
$x(u_{t})\neq x(u_{t+1})$. Therefore

$\displaystyle x^{T}L_{i}x$ $\displaystyle=$ $\displaystyle\sum_{jk\in
E}w_{E}(j,k)(x_{*}(k)-x_{*}(j))^{2}$ $\displaystyle\geq$ $\displaystyle
w_{E}(u_{t},u_{t+1})(x_{*}(u_{t})-x_{*}(u_{t+1}))^{2}$ $\displaystyle>$
$\displaystyle 0.$

∎

If $L_{i}$ is positive definite, then because it is also real and symmetric,
it has a Choleskey decomposition $L_{i}=U_{i}^{T}U_{i}$, where $U_{i}$ is real
and invertible. For $g_{i}\in\mathbb{R}^{V_{i}}$, let
$g_{i}^{\prime}=U_{i}g_{i}$ so that

$c(w_{V},w_{E},g)=\frac{\|g_{i}^{\prime}\|_{2}^{2}}{g_{i}^{\prime
T}(U_{i}^{T})^{-1}W_{V,i}U_{i}^{-1}g_{i}^{\prime}}.$

Let $L_{i}^{\prime}=(U_{i}^{-1})^{T}W_{V,i}U_{i}^{-1}$, which is real and
symmetric. Applying the Courant-Fischer theorem, $c(w_{V},w_{E},g)$ is
minimized by choosing $g_{i}^{\prime}$ to be the dominant eigenvector of
$L_{i}^{\prime}$. Reverting the change of variables gives the following
statement.

######  Lemma 2.4.

When $G$ is positively connected, the solutions that optimize (3) correspond
with the dominant right-eigenvectors of $L_{i}^{-1}W_{V,i}$.

With this set up, we are able to generalize Theorem 1.1 to weighted graphs
under modest assumptions. For ease of presentation, we split it into two
statements.

######  Theorem 2.5.

Assume $G-i$ is positively connected. Let $f_{i}$ be a function that optimizes
(3). If $f_{i}(u)>0$ for some vertex $u$, then $f_{i}(u^{\prime})>0$ for all
$u^{\prime}\in V_{i}$.

###### Proof.

We prove the first statement by contradiction. We begin by assuming that
$f_{i}$ is nonnegative. Let $Z=\\{j:f_{i}(j)=0,j\neq i\\}$ and assume that
$Z\neq\emptyset$. Because $G-i$ is positively connected, there exists an edge
with positive weight with one endpoint in $Z$ and the other endpoint in
$V_{i}\setminus Z$. Suppose we modify $f_{i}$ by increasing $f_{i}(j)$ for
each $j\in Z$ by some $\epsilon>0$, and consider the affect that change would
have on $c(w_{V},w_{E},f_{i})$. Specifically, consider the definition of $c$
in (4): the denominator would increase, and when $\epsilon$ is sufficiently
small the numerator would decrease. This contradicts the choice of $f_{i}$.

So now suppose the sets $N=\\{j:f_{i}(j)<0,j\neq i\\}$ and
$P=\\{j:f_{i}(j)>0,j\neq i\\}$ are each nonempty. We define function
$f_{i}^{+}=|f_{i}|$. Observe that $\|f_{i}^{+}\|_{w}=\|f_{i}\|_{w}$. If there
is an edge with positive weight with an endpoint in $N$ and another endpoint
in $P$, then $c(w_{V},w_{E},f_{i}^{+})<c(w_{V},w_{E},f_{i})$, contradicting
the choice of $f_{i}$. Therefore, because $G-i$ is positively connected, there
are edges with positive weights connecting $P$ to $Z$ and $Z$ to $N$, and thus
$N\neq\emptyset$. Moreover, we have
$c(w_{V},w_{E},f_{i}^{+})=c(w_{V},w_{E},f_{i})$, and $f_{i}^{+}$ is a second
solution to the optimization problem (3). But this is a contradiction, because
$f_{i}^{+}$ is not a solution to the optimization problem (3), as $f_{i}^{+}$
exactly matches the case described in the previous paragraph. ∎

######  Theorem 2.6.

Assume $G$ and $G-i$ are each positively connected. Let $f_{i}$ be a function
that optimizes (3). For $u\in V_{i}$, there exists a $u^{\prime}\in N(u)$
(possibly $u^{\prime}=i$) such that $f_{i}(u^{\prime})\leq f_{i}(u)$.
Moreover, we may assume the inequality is strict if $w_{V}(u)>0$.

###### Proof.

Let $g_{i}\in\mathbb{R}^{V_{i}}$ be the vector representation of $f_{i}$.
Recall that $g_{i}$ is a $\lambda$-eigenvector of $L_{i}^{-1}W_{V,i}$, where
$\lambda$ is the largest eigenvalue. Moreover, $L_{i}^{-1}W_{V,i}$ is similar
to $L_{i}^{\prime}$. For any vector $x\in\mathbb{R}^{V_{i}}$ we have
$x^{T}L_{i}^{\prime}x=\|U_{i}^{-1}x\|_{w}$, and therefore $L_{i}^{\prime}$ is
positive semi-definite (positive definite if and only if each vertex has
positive weight). This implies $\lambda\geq 0$, and because $\lambda$ is the
largest eigenvalue we have that $\lambda>0$ unless $W_{V,i}=0$. But then the
weight function $w_{V}$ is identically $0$, which contradicts our definition
of a vertex weight function.

We now consider the equation $W_{V,i}g_{i}=\lambda L_{i}g_{i}$. Applying this
formula at vertex $u$ with the definition of $L_{i}$ we get that

$\displaystyle 0$ $\displaystyle\leq$ $\displaystyle w_{V}(u)g_{i}(u)$
$\displaystyle=$ $\displaystyle\lambda\sum_{j\neq
u}w_{E}(u,j)(g_{i}(u)-g_{i}(j))$ $\displaystyle\leq$ $\displaystyle\lambda
d(u)\max_{j}(g_{i}(u)-g_{i}(j)).$

If $G$ is positively connected, then $d(u)>0$. Thus, $\lambda d(u)>0$, and we
conclude that $\max_{j}(g_{i}(u)-g_{i}(j))\geq 0$. Moreover, if $w_{V}(u)>0$,
then by Theorem 2.5 we have a strict inequality in the first line of the
equation array above, which gives the stronger conclusion
$\max_{j}(g_{i}(u)-g_{i}(j))>0$. ∎

Unfortunately, Theorem 2.6 can not be strengthened. It is a simple calculus
exercise directly applied to the formulation (3) that if $w_{V}(u)=0$, then
the value $f_{i}(u)$ is the average of the value of its neighbors (formally,
$f_{i}(u)=d(u)^{-1}\sum_{j\neq u}w_{E}(u,j)f_{i}(j)$). So, if $u$ is incident
with merely a single edge $ux$, then $f_{i}(u)=f_{i}(x)$. On the other hand,
it also follows that if $w_{V}(u)=0$ and $u$ has a neighbor $x$ such that
$f_{i}(x)>f_{i}(u)$, then $u$ has another neighbor $y$ such that
$f_{i}(y)<f_{i}(u)$.

######  Theorem 2.7.

The spectral path from $j$ to $i$ is well-defined if $G$ and $G-i$ are each
positively connected and $w_{V}(j)>0$.

###### Proof.

Let us attempt to construct the tree $T_{i}$ as described in the introduction,
only vertex $x$ has no arcs leaving it if $f_{i}(x)\geq\max_{yx\in
E}f_{i}(y)$. In other words, we only include an arc in $T_{i}$ if the
corresponding value in $f_{i}$ strictly decreases along that arc.

Let us consider the maximal directed path in $T_{i}$ starting at $j$. That is,
we consider the sequence $j=j_{0},j_{1},j_{2},\ldots,j_{k}$ where for $\ell<k$
we have that $j_{\ell+1}$ is the neighbor of $j_{\ell}$ that minimizes
$f_{i}(j_{\ell+1})$, and $k$ is the first index that satisfies (A) $j_{k}=i$,
(B) every neighbor $x$ of $j_{k}$ satisfies $f_{i}(x)\geq f_{i}(j_{k})$, or
(C) the vertex $y$ that minimizes $f_{i}(y)$ among neighbors of $j_{k}$
satisfies $y\in\\{j_{0},j_{1},\ldots,j_{k-1}\\}$. The spectral path from $j$
to $i$ is well-defined by definition when we are in case (A) above.

By way of contradiction, we assume that we are in case (B) or (C) above. The
sequence $f_{i}(j_{0}),f_{i}(j_{1}),\ldots,f_{i}(j_{k})$ is monotone
decreasing, which implies that if we are in case (C), then we are also in case
(B). So assume that every neighbor $x$ of $j_{k}$ satisfies $f_{i}(x)\geq
f_{i}(j_{k})$. By Theorem 2.6, this implies $w_{V}(j_{k})=0$. By the
assumption $w_{V}(j)>0$, this implies $k\geq 1$. Observe that because $k$ is
chosen as the first index where (B) occurs, we know that
$f_{i}(j_{k-1})>f_{i}(j_{k})$ and $j_{k-1}$ is a neighbor of $j_{k}$. By the
discussion prior to the statement of the theorem, this implies that we can not
be in case (B). This contradicts our assumption, so we must be in case (A),
and the theorem is proven. ∎

Finding a function that solves the optimization problem (3) for a fixed graph
is an easy problem computationally. But proving that a constructed function is
a solution for a family of graphs is quite hard, even for unweighted graphs.
Still, we can have some control over spectral paths using the following
theorem.

######  Theorem 2.8.

Fix three vertices $j,i,k$. Suppose $G-j$ is not connected, with $i$ and $k$
in different components of $G-j$. Under these assumptions, if $G$ and $G-i$
are each positively connected and $w_{V}(k)>0$, then $f_{i}(k)>f_{i}(j)$.
Moreover, the spectral path from $k$ to $i$ will pass through $j$.

###### Proof.

By Theorem 2.7, there is a spectral path from $k$ to $i$. By definition,
$f_{i}$ monotonically decreases along this path. The assumption is equivalent
to stating that every path from $k$ to $i$ includes $j$, and therefore $j$ is
in the spectral path from $k$ to $i$. ∎

Let us remark that a spectral path may not be completely deterministic if a
vertex had multiple neighbors with the smallest value under $f_{i}$, but
Theorem 2.8 still holds regardless of how such ties are resolved. This implies
that such ties can not occur in certain circumstances.

######  Corollary 2.9.

Fix three vertices $j,i,k$. Suppose $G-j$ is not connected, with $i$ and $k$
in different components of $G-j$. Moreover, assume $jk\in E$. Under these
assumptions, if $G$ and $G-i$ are each positively connected and $w_{V}(k)>0$,
then $j$ is the unique vertex that satisfies $f_{i}(j)=\min_{z\in
N(k)}f_{i}(z)$.

###### Proof.

By Theorem 2.8, there is a spectral path from $k$ to $i$ and it passes through
$j$. By way of contradiction, assume that there exists a $z\in N(j)$ with
$f_{i}(z)\leq f_{i}(j)$. Then there is a spectral path from $k$ to $i$ that
uses edge $kz$. But such a spectral path will eventually pass through $j$,
which contradicts that $f_{i}$ strictly decreases along spectral paths. ∎

Our presentation in the next subsections of the counterexamples to Question
1.2 will use the following outline. We will construct a sequence of graphs,
where each member of that sequence reduces to the same fixed graph $G_{i}$
under the mapping defined by Theorem 2.2—but with different weights. In our
sequence of graphs, some $\sim_{i}$-equivalence classes will remain fixed in
size, while others will grow asymptotically large. We will scale $w_{V}$ and
$w_{E}$ so that the largest weights remain fixed in value, and the smallest
weights become infinitesimally small. We will consider the limit of this
sequence; removing edges with weight zero will allow us to apply Theorem 2.8.
The penultimate step of the argument is stating some graph in the sequence of
graphs will be close enough to the limit of the sequence that it will have the
same spectral paths. Finally, Theorem 2.7 will imply that a spectral path
exists, Theorem 2.8 will describe what that path looks like, and Theorem 2.2
will provide a “lift” of the spectral path in the weighted graph to a (family
of) spectral paths in the original unweighted graph.

The rest of this subsection will be spent on a key part of the above argument
that still needs to be shown: for the penultimate step, we require that the
spectral paths in the graphs in the sequence are somehow related to the
spectral paths in the limiting graph. That is, we need to show that $f_{i}$ is
continuous under perturbations of $w_{V}$ and $w_{E}$. We will do this by
recalling that $f_{i}$ is the eigenvector of some matrix, which are known to
be continuous under perturbations of that matrix when the eigenvalue is
simple. This is is a bit of a surprising result in its own right: eigenvectors
are known to be discontinuous, and spectral graph theory is filled with
examples of eigenvalues with large multiplicity (for example, see [1] and the
references therein).

######  Theorem 2.10.

If $G$ and $G-i$ are each positively connected, then the largest eigenvalue of
$L_{i}^{-1}W_{V,i}$ is simple. Equivalently (up to reflection from positive to
negative values) the function that solves the optimization problem (3) is
unique.

###### Proof.

The equivalence between the two statements is given by Lemma 2.4. Let
$\lambda$ be the largest eigenvalue of $L_{i}^{-1}W_{V,i}$.

By way of contradiction, assume $\lambda$ has multiplicity at least two.
Recall that $L_{i}^{-1}W_{V,i}$ is similar to $L_{i}$, which is real and
symmetric, and therefore diagonalizable. Therefore the $\lambda$-eigenspace of
$L_{i}^{-1}W_{V,i}$ has dimension at least two. Let $f_{i,1}$ and $f_{i,2}$ be
independent $\lambda$-eigenvectors of $L_{i}^{-1}W_{V,i}$.

Because $\lambda$-eigenvectors is closed under linear combinations, there
exists a vector $f_{i,*}=\alpha_{1}f_{i,1}+\alpha_{2}f_{i,2}$ for
$\alpha_{1},\alpha_{2}\in\mathbb{R}$ that is a $\lambda$-eigenvector of
$L_{i}^{-1}W_{V,i}$ and has a negative and a positive coordinate. By Lemma
2.4, $f_{i,*}$ is a solution to the optimization problem (3). But this
contradicts Theorem 2.5. ∎

######  Theorem 2.11.

The function $f_{i}$ that solves the optimization problem (3) is continuous
under perturbations of $w_{V}$ and $w_{E}$ inside the space of weights where
$G$ and $G-i$ are positively connected.

###### Proof.

Assume that the vertex set and edge set of our graph $G$ is fixed, as well as
the special vertex $i$. Let $\mathcal{W}_{V}$ denote the space of vertex
weights and let $\mathcal{W}_{E}$ denote the space of edge weights such that
$G$ and $G-i$ are positively connected. Let $M_{n-1}(\mathbb{R})$ be the space
of $(n-1)\times(n-1)$ real matrices. We define a function
$\tau:\mathcal{W}_{V}\times\mathcal{W}_{E}\rightarrow M_{n-1}(\mathbb{R})$ as
$\tau(w_{V},w_{E})=L_{i}^{-1}W_{V,i}$.

We can think of elements of $\mathcal{W}_{V}\times\mathcal{W}_{E}$ as points
in $\mathbb{R}^{V+E}$ and an element of $M_{n-1}(\mathbb{R})$ as a point in
$\mathbb{R}^{(n-1)^{2}}$. This frame of context allows us to apply natural
norms to these spaces (such as $\ell_{2}$), and we claim that $\tau$ is
continuous in such a setting. As $L_{i}$ is independent of $w_{V}$, $\tau$ is
clearly continuous under perturbation of the $w_{V}$ variable. Observe that
$W_{V,i}$ is independent of $w_{E}$ and $L_{i}$ is continuous under
perturbations of $w_{E}$. Because matrix inverse is a continuous operation,
$\tau$ is continuous under perturbation of the $w_{E}$ variable. This proves
the claim.

We define a function $\rho:M_{n-1}(\mathbb{R})\rightarrow\mathbb{R}^{n-1}$
that takes a matrix and returns an (arbitrarily chosen) eigenvector
corresponding to the largest eigenvalue $\lambda$. It is folklore222See, for
example,
https://mathoverflow.net/questions/207452/ or
https://math.stackexchange.com/questions/1133071/ or
https://math.stackexchange.com/questions/807144/ for different approaches to
this. that when $\lambda$ is a simple eigenvalue, $\rho$ is continuous. By
Theorem 2.10, $\rho$ is continuous.

As constructed, Lemma 2.4 implies that $f_{i}=\rho(\tau(w_{V},w_{E}))$. The
proof concludes by stating that the composition of two continuous functions is
continuous. ∎

######  Corollary 2.12.

Suppose that $G$ and $G-i$ are positively connected. Also, suppose for fixed
vertices $j,i,k$, we have $G-j$ is not connected, with $i$ and $k$ in
different components of $G-j$, and $jk\in E$. There exists an $\epsilon>0$
such that if $w_{E}$ and $w_{V}$ are perturbed by at most $\epsilon$ where the
set of neighbors of $k$ remains fixed (we allow the creation/deletion of an
edge with weight $\epsilon$ that is not incident with $k$), then the spectral
path from $k$ to $i$ will still include $j$.

###### Proof.

This follows from the continuity from Theorem 2.11 and the uniqueness of the
spectral path from Corollary 2.9. ∎

By construction of spectral paths, if $j$ is on the spectral path $P$ from $k$
to $i$, then the spectral path from $j$ to $i$ is a sub-path of $P$. We can
thus iteratively apply Corollary 2.12 to achieve the next statement.

######  Corollary 2.13.

Suppose that $G$ and $G-i$ are positively connected and that there exists a
unique path $P$ from vertex $k$ to $i$. There exists an $\epsilon>0$ such that
if $w_{E}$ and $w_{V}$ are perturbed by at most $\epsilon$ where the set of
neighbors of vertices in $P$ remains fixed (we allow the creation of an edge
with weight $\epsilon$ that may create a new path from $k$ to $i$), then the
spectral path from $k$ to $i$ will still be $P$.

###  2.2 Weighted Cycle

We construct an unweighted graph family $G_{\ell,k}$, which is indexed by
positive integers $\ell,k$. For fixed $\ell,k$, we construct $G_{\ell,k}$ as
follows. Start by creating disjoint paths $x_{0,i}x_{1,i}x_{2,i}\ldots
x_{\ell,i}$ for each $1\leq i\leq k$. The vertices
$x_{0,1},x_{0,2},\ldots,x_{0,k}$ are identified to a single vertex $u$, and
the vertices $x_{\ell,1},x_{\ell,2},\ldots,x_{\ell,k}$ are identified to a
single vertex $v$. Finally, we add edge $uv$. Figure 1 illustrates the outcome
of this construction when $\ell=5$ and $k=2$. Observe that $G_{\ell,k}$ is a
planar graph for all $\ell$ and $k$. Let us consider the spectral paths for
special vertex $u$.

Figure 1: This is graph $G_{5,2}$.

######  Proposition 2.14.

Consider $G_{\ell,k}$ for $k\geq 2$. The equivalence classes of $\sim_{u}$ are
$\\{x_{1,i}\\}_{i},\\{x_{2,i}\\}_{i},\ldots,\\{x_{\ell-1,i}\\}_{i},\\{v\\}$.

###### Proof.

The map $\pi$ that fixes $u$ and $v$ and $\pi(x_{j,i})=\pi(x_{j,i+1})$ is a
graph automorphism. Therefore $x_{j,i}\sim_{u}x_{j^{\prime},i^{\prime}}$ if
$j=j^{\prime}$. This proves that each of the desired sets is a subset of an
equivalence class; the remainder of the proof will be to show that no other
equivalence relations exist. To do so, we repurpose the the idea of
“landmarks” in a graph. We make use of two facts about a graph automorphism
$\pi$: that $d(a)=d(\pi(a))$ and $d(a,b)=d(\pi(a),\pi(b))$ for any pair of
vertices $a,b$. In particular, if $\pi(b)=b$, then $d(a,b)=d(\pi(a),b)$. By
the first fact, if $\pi$ fixes $u$, then it also fixes $v$. We finish the
proof with the second fact by observing that if $j\neq j^{\prime}$ then
$d(u,x_{j,i})\neq d(u,x_{j^{\prime},i^{\prime}})$ or $d(v,x_{j,i})\neq
d(v,x_{j^{\prime},i^{\prime}})$. ∎

Let us constructed the smaller weighted graph $(G_{\ell,k})_{u}$ as in Theorem
2.2. Let $V_{*}=\\{v_{*},u_{*},x_{1,*},x_{2,*},\ldots,x_{\ell-1,*}\\}$ and
define $\phi$ by $\phi(v)=v_{*}$, $\phi(u)=u_{*}$, and
$\phi(x_{j,i})=x_{j,*}$. There are edges $u_{*}v_{*}$, $u_{*}x_{1,*}$,
$x_{\ell-1,*}v_{*}$, and $x_{j,*}x_{j+1,*}$ for $1\leq j\leq\ell-2$. The
vertex weights are $w_{V}(x_{j,*})=k$, $w_{V}(v_{*})=1$. All edges have weight
$k$ except $iv_{*}$, which has weight $1$.

######  Theorem 2.15.

Fix $\ell$. For any $i$ and $k$ sufficiently large, the spectral path from
$x_{\ell-1,i}$ to $u$ has length $\ell-1$, while the distance between those
vertices is $2$.

###### Proof.

We consider the weighted graph $(G_{\ell,k})_{u}$ where each edge weight and
vertex weight is multiplied by $k^{-1}$. The function optimizing (3) does not
change if we scale the weights of the vertices or edges by a uniform scalar.
Let $G_{(\ell)}$ be the resulting weighted graph when $k\rightarrow\infty$ and
all edges with zero weight are deleted. Specifically, $G_{(\ell)}$ is a path
with endpoints $u_{*}$ and $v_{*}$ where every edge has weight $1$. Each
vertex has weight $1$ except $v_{*}$, which has weight $0$. By Theorem 2.7
there is a spectral path from $x_{\ell-1,*}$ to $u_{*}$ in $G_{(\ell)}$. There
is only one path from $x_{\ell-1,*}$ to $u_{*}$, and it has length $\ell-1$.
By Corollary 2.13, for sufficiently large $k$, this is also the spectral path
in $(G_{\ell,k})_{u}$, which can be lifted to the spectral path in
$G_{\ell,k}$ that starts at $x_{\ell-1,i}$. ∎

###  2.3 Double Broom With Extra Structure

We construct an unweighted graph family $H_{\ell,k,t}$, which is indexed by
positive integers $\ell,k>2$ and positive real $t$. The graph $H_{\ell,k,t}$
contains a subgraph $B_{\ell,k}$ that will be used later, and so we describe
it separately. We start constructing $B_{\ell,k}$ with $2k$ disjoint paths:
for each $1\leq i\leq k$ create path $x_{0,i}x_{1,i}x_{2,i}\ldots
x_{\ell+1,i}$ and path $y_{0,i}y_{1,i}y_{2,i}y_{3,i}y_{4,i}y_{5,i}$. The
vertices $x_{0,1},y_{0,1},x_{0,2},y_{0,2},\ldots,x_{0,k},y_{0,k}$ are
identified to a single vertex $u$, and the vertices
$x_{\ell+1,1},y_{5,1},x_{\ell+1,2},y_{5,2},\ldots,x_{\ell+1,k},y_{5,k}$ are
identified to a single vertex $v$. The vertices
$y_{2,1},y_{2,2},\ldots,y_{2,k}$ are identified into a single vertex
$y_{2,*}$, and the vertices $y_{3,1},y_{3,2},\ldots,y_{3,k}$ are identified
into a single vertex $y_{3,*}$ (implicitly, the $k$ edges $y_{2,i}y_{3,i}$
become a single edge $y_{2,*}y_{3,*}$). We illustrate $B_{6,3}$ in Figure 2.
In this construction, we call vertices $u$ and $v$ the “connectors” of the
subgraph.

Figure 2: This is graph $B_{6,3}$.

Let $T=\lfloor tk\rfloor$. We construct $H_{\ell,k,t}$ from $B_{\ell,k}$ by
adding $T$ pendant vertices to each of $u$ and $v$. We illustrate
$H_{6,3,5/3}$ in Figure 3. Let $u_{1},\ldots,u_{T}$ be the pendant vertices
adjacent to $u$, and let $v_{1},\ldots,v_{T}$ be the pendant vertices adjacent
to $v$. For any $i,j$, the path from $u_{i}$ to $v_{j}$ is at most $7$. We
will show that for fixed $\ell$, the symmetric spectral path between $u_{i}$
and $v_{j}$ is $\ell+3$ when $k$ is sufficiently large. If we chose a vertex
pair at random from $H_{\ell,k,t}$, the probability that we would choose
$\\{u_{i},v_{j}\\}$ for some $i,j$ is $\frac{2T^{2}}{(2T+4+k(\ell+2))^{2}}$,
which converges to $\frac{1}{2}$ as $t$ grows (here, we fix both $\ell$ and
$k$).

Figure 3: This is graph $H_{6,3,\frac{5}{3}}$.

In the following, we consider special vertex $u_{1}$ and study the spectral
path from $v_{1}$ to $u_{1}$. Observe that by symmetry, this will describe the
spectral path from $u_{i}$ to $v_{j}$ and the spectral path from $v_{j}$ to
$u_{i}$ for all $i,j$. Because every path that ends at $u_{1}$ has $u$ as the
penultimate step, it suffices to establish the spectral path from $v_{1}$ to
$u$. Hence, we will deal with special vertex $u$ instead of $u_{1}$. We omit
the proof to the following statement, as it follows—in a longer, more tedious
way—the same argument as for Proposition 2.14.

######  Proposition 2.16.

Consider $H_{\ell,k,t}$ for $k>2$ and $\ell>6$. The equivalence classes of
$\sim_{u}$ are $\\{u_{i}\\}_{i}$, $\\{u\\}$,
$\\{x_{1,i}\\}_{i},\ldots,\\{x_{\ell,i}\\}_{i}$, $\\{y_{1,i}\\}_{i}$,
$\\{y_{2,*}\\}$, $\\{y_{3,*}\\}$, $\\{y_{4,i}\\}_{i}$, $\\{v\\}$,
$\\{v_{i}\\}_{i}$.

Let us constructed the smaller weighted graph $(H_{\ell,k,t})_{u}$ as in
Theorem 2.2. Let

$V_{*}=\\{v_{*},v^{\prime},u_{*},u^{\prime},x_{1}^{\prime},\ldots,x_{\ell}^{\prime},y_{1}^{\prime},\ldots,y_{4}^{\prime}\\}.$

We define $\phi$ and $w_{V}$ by

  * •

$\phi(v)=v_{*}$, $\phi(u)=u_{*}$, $\phi(y_{2,*})=y_{2}^{\prime}$,
$\phi(y_{3,*})=y_{3}^{\prime}$, each with weight $1$;

  * •

$\phi(v_{i})=v^{\prime}$ with weight $T$;

  * •

$\phi(u_{i})=u^{\prime}$ with weight $T$;

  * •

$\phi(x_{j,i})=x_{j}^{\prime}$, each with weight $k$; and

  * •

$\phi(y_{j,i})=y_{j}^{\prime}$ for $j\in\\{1,4\\}$, each with weight $k$.

All edges have weight $k$ except for $w_{E}(y_{2}^{\prime},y_{3}^{\prime})=1$
and $w_{E}(v_{*},v^{\prime})=w_{E}(u_{*},u^{\prime})=T$.

######  Theorem 2.17.

Fix $\ell>6$ and $t^{\prime}$, and consider the graph $H_{\ell,k,t}$. For $k$
sufficiently large, the spectral path from $v_{1}$ to $u_{1}$ has length
$\ell+3$, while the distance between those vertices is $7$.

###### Proof.

Recall that the spectral path from $v_{1}$ to $u_{1}$ is the spectral path
from $v_{1}$ to $u$ with the edge $uu_{1}$ appended. Thus, it suffices to
prove that the spectral path from $v_{1}$ to $u$ has length $\ell_{2}$.

We consider the weighted graph $(H_{\ell,k,t})_{u}$ where each edge weight and
vertex weight is multiplied by $k^{-1}$. Let $H_{(\ell,t)}$ be the resulting
weighted graph when $k\rightarrow\infty$ and the edge
$y_{2}^{\prime}y_{3}^{\prime}$ (the unique edge with weight zero) is deleted.
Observe that $w_{V}(v^{\prime})=t>0$, so by Theorem 2.7 there exists a
spectral path from $v^{\prime}$ to $u_{*}$ in $H_{(\ell,t)}$. The resulting
graph $H_{(\ell,t)}$ is a tree, so the spectral path from $v^{\prime}$ to
$u_{*}$ must be the unique path from $v^{\prime}$ to $u_{*}$, which is
$v^{\prime}v_{*}x_{\ell}^{\prime}x_{\ell-1}^{\prime}\cdots
x_{1}^{\prime}u_{*}$ and has length $\ell+2$. By Corollary 2.13, for
sufficiently large $k$, this is also the spectral path in
$(H_{\ell,k,t})_{u}$, which can be lifted to the spectral path in
$H_{\ell,k,t}$ that begins at $v_{1}$. ∎

###  2.4 A Path for a Block Structure

We construct an unweighted graph family $J_{\ell,k,d}$, which is indexed by
even positive integer $\ell>5$ and positive integers $k>2,d>\ell$. For fixed
$\ell,k,d$ we construct $J_{\ell,k,d}$ by taking a copy of $B_{\ell,k}$ with
connectors $u_{i},v_{i}$ for each $1\leq i\leq d$. We will name copy $i$ of
$B_{\ell,k}$ as $B_{i}$. We then identify $v_{i}$ with $u_{i+1}$ for each
$1\leq i<d$. We then add $k$ pendant vertices $x_{1},\ldots,x_{k}$ attached at
$u_{1}$ and $k$ more pendant vertices $y_{1},\ldots,y_{k}$ attached at
$v_{d}$.

For $d>\ell>6$, the diameter of $J_{\ell,k,d}$ is $5d+\ell-4$, which is
achieved by taking the distance from the copy of $x_{\ell/2-2,1}$ in $B_{1}$
to the copy of $x_{\ell/2+3,1}$ in $B_{d}$. Using arguments similar to those
in Section 2.3, it is clear that the length of the symmetric spectral path
from $x_{1}$ to $y_{1}$ is $(\ell+1)d+2$. Thus, spectral paths can have length
that is an unbounded multiple of the diameter of the overall space.

##  3 Conditions for Bounded Length Spectral Paths

In Section 3.1 we will prove Theorem 3.2, which is our positive result. In
Section 3.2 we present two questions whose answer could lead to a positive
answer to Question 1.2.

###  3.1 Spread

For simplicity, we will assume the special vertex $i$ is fixed during this
section.

We consider an optimization problem that can informally be interpreted as
replacing an $\ell_{2}$ norm in (1) with an $\ell_{\infty}$ norm:

$s_{*}:=\min_{\|g\|_{2}=1,0=\sum_{i}g(i)}\max_{ij\in E}|g(i)-g(j)|.$ (5)

The _spread_ of a graph is $s_{*}^{-1}$. We consider a related optimization
problem; it is derived from (5) using the same transformation that turned (1)
into (2):

$\min_{\|g\|_{2}=1,0=g(i)}\max_{ij\in E}|g(i)-g(j)|.$ (6)

Let $\tilde{f}$ be a function that solves optimization problem (6), and let
$s=\max_{ij\in E}|\tilde{f}(i)-\tilde{f}(j)|$. By replacing $\tilde{f}$ with
$-\tilde{f}$ when necessary, we assume that there exists a $j$ with
$\tilde{f}(j)>0$.

######  Proposition 3.1.

For each $j\neq i$ we have $\tilde{f}(j)>0$. Moreover, there exists a
$j^{\prime}\in N(j)$ such that $\tilde{f}(j^{\prime})=\tilde{f}(j)-s$.

###### Proof.

For a nonzero function $g$ with $g(i)=0$, we define function

$c^{\prime}(g)=\frac{\max_{ij\in E}|g(i)-g(j)|}{\|g\|_{2}}.$

The function $\tilde{f}$ can be taken as $g^{\prime}/\|g\|_{2}$ for a function
$g^{\prime}$ that minimizes $c^{\prime}$. The proof to the first statement of
the proposition then follows the same argument as Theorems 2.5. The proof to
the second statement then follows the same argument as Theorem 2.6. ∎

We construct the tree $T_{i}^{(c)}$ by replacing $f_{i}$ with $\tilde{f}$ in
the definition of $T_{i}$ in the Introduction. By Proposition 3.1,
$T_{i}^{(c)}$ is well-defined. We can define a _spread-path from $j$ to $i$_
as the path from $j$ to $i$ in $T_{i}^{(c)}$.

######  Theorem 3.2.

A spread-path from $j$ to $i$ is a shortest path from $j$ to $i$.

###### Proof.

By construction, $\tilde{f}$ monotonically decreases along any spread-path to
$i$. We will show that it decreases at a linear rate. Let
$L:V_{i}\rightarrow\mathbb{R}$ be a function defined by
$L(j^{\prime})=\tilde{f}(j^{\prime})-\min_{w\in N(j^{\prime})}\tilde{f}(w)$.
That is, $L$ represents how much $\tilde{f}$ decreases across the next edge of
the spread-path to $i$.

We claim that $L\equiv s$. Let $j^{\prime}$ be an arbitrary vertex other than
the special vertex $i$. By Proposition 3.1, $L(j^{\prime})\geq s$. By the
definition of $s$, we have $L(j^{\prime})\leq s$. Thus, the claim is proved.

The above claim implies that for each $j$ we have that $s^{-1}\tilde{f}(j)$ is
an integer and equals the length of the spread-path from $j$ to $i$. The
theorem follows from proving that every path from $j$ to $i$ has length at
least $s^{-1}\tilde{f}(j)$ Consider a path $j=x_{0}x_{1}\cdots x_{\ell}=i$. By
definition of $L$, we have for $i<\ell$ that
$\tilde{f}(x_{i+1})\geq\tilde{f}(x_{i})-L(x_{i})=\tilde{f}(x_{i})-s$.
Therefore $\ell\geq
s^{-1}(\tilde{f}(x_{0})-\tilde{f}(x_{\ell}))=s^{-1}(\tilde{f}(j)-0)$. ∎

###  3.2 Graphs with bounded curvature

The central claim to the proof of Theorem 3.2 is that $L$ is a constant
function. This is stronger than necessary; a positive result towards Question
1.2 would only require a uniform lower and upper bound on $L$. We are not the
first to be interested in a uniform upper bound: Chung and Yau [3] stated an
interest in bounds on “stretches $|f(x)-f(y)|$ of any given edge” $xy$ for
“combinatorial eigenfunction $f$.”

To avoid duplication of notation, we will use $f_{D}$ to denote our
“combinatorial eigenfunction.” In the contexts of Chung and Yau’s studies,
$f_{D}$ is typically the Fiedler right-eigenvector of the _random-walk
Laplacian_ , which is $D^{-1}L$, although they also consider other right-
eigenvectors of that matrix. Equivalently, $f_{D}$ is the vector that solves
the optimization problem $\min_{x\neq 0}\frac{x^{T}Lx}{x^{T}Dx}$.
Steinerberger ([4], Section 2.5) does consider the random-walk Laplacian, and
explains the focus on the Laplacian to be due to empirical performance. Let
$\lambda$ be the eigenvalue associated to $f_{D}$. Let
$L_{D}(x)=f_{D}(x)-\min_{y\in N(x)}f_{D}(x)$ when $f_{D}(x)\geq 0$ and
$L_{D}(x)=-f_{D}(x)+\min_{y\in N(x)}f_{D}(x)$ otherwise; so that $L_{D}$ is
the analogue of $L$ for the combinatorial eigenfunction.

Let $\Delta=\max_{j}d(j)$ denote the maximum degree. Let
$\alpha=\max_{j}|f_{D}(j)|$. We assume that by normalization we have
$\|f_{D}\|_{2}=1$, which implies that $\alpha\in[0,1]$.

Chung and Yau [3] established an upper bound on $L_{D}$ when the graph
satisfies graph curvature conditions. There are many different variations of
graph curvature; we survey eight variations of positive curvature on Page 545
of [5] and five variations of negative curvature are discussed at various
places in [6]; neither survey includes either of the two curvature variations
in [3]. The central definition of curvature in [3] is simply called
“curvature;” let $\kappa$ denote the curvature of $G$ when it is well-defined.
A connection between $\kappa$ and other forms of curvature can be found in
Section 3.3 of [3]. Chung and Yau [3] show that
$L_{D}\leq\alpha\sqrt{(8\Delta+4\kappa)\lambda}$. This is a generalization of
an earlier result [2] by the same authors for a class of graphs that satisfy
$\kappa=0$, which includes Cayley graphs of abelian groups.

On the other hand, a direct application of the definition of an eigenvector of
$D^{-1}L$ gives a (non-uniform) lower bound $L_{D}(x)\geq\lambda f_{D}(x)$.

Motivated by finding a second positive answer to Question 1.2, we pose the
following two questions. Can the work of Chung and Yau be adapted to the
presence of a special vertex? Is there a uniform lower bound on $L_{D}$ that
incorporates the diameter of the overall space (possibly under an assumption
of curvature)? Perhaps a weaker result would be a uniform lower bound that
incorporates $n$?

## References

  * [1] S. Akbari, E.R. van Dam, and M.H. Fakharan, “Trees with a large Laplacian eigenvalue multiplicity.” Linear Algebra and its Applications 586 (2020) 262–273.
  * [2] F. Chung and S.-T. Yau, “A Harnack inequality for homogeneous graphs and subgraphs,” Comm. Analysis and Geometry 2 (1994) 627–640.
  * [3] F. Chung and S.-T. Yau, “A strong Harnack inequality for graphs,” Comm. Analysis and Geometry 25(3) (2017) 557–588.
  * [4] S. Steinerberger https://arxiv.org/abs/2004.01163 .
  * [5] M. Yancey, “Positively Curved Graphs.” J. Graph Theory 94(4) (2020) 539–578.
  * [6] M. Yancey, “Negatively Curved Graphs.” https://arxiv.org/abs/1512.01281v2.