Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 10 min ago
PreprintCC BY 4.0arXiv

Non-backtracking Laplacian for hypergraphs

  • Eleonora Andreotti
  • Raffaella Mulas
Open at sourcePDFDOICite

Abstract

We extend the non-backtracking Laplacian for graphs, introduced by Jost, Mulas and Torres, to hypergraphs. The operator is defined on the permutations of the edges and is normalized by the number of edges through which a non-backtracking walk can continue. We show that it satisfies a symmetry that generalizes the graph case, and that it can be obtained from the random walk Laplacian of a directed graph by rescaling if and only if all edges have the same cardinality. Moreover, we show that, up to copies of the eigenvalue $1$, its spectrum can be computed from a much smaller matrix indexed by the incidences of the hypergraph, and we use this reduction to bound the remaining eigenvalues away from $1$.

Related

  1. The real eigenvalues of the non-backtracking Laplacian
    Raffaella Mulas, Leo Torres
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  2. Backtracking Direct, Indirect and Total Effects
    Jose M. Peña
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Scope-Restricted Backtracking Counterfactuals
    Johan de Aguas, Martin Jullum
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  4. An Alon-Boppana Bound for the Non-Backtracking Operator
    Theo McKenzie
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  5. Phase transition of random non-uniform hypergraphs
    Élie de Panafieu
    Journal of Discrete AlgorithmsPeer-reviewedLicence not statedFull text17 citedCombinatorics & discrete mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{andreotti2026nonbacktracking,
  title = {{Non-backtracking Laplacian for hypergraphs}},
  author = {Eleonora Andreotti and Raffaella Mulas},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01121},
  eprint = {2611.01121},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01121},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Non-backtracking Laplacian for hypergraphs
AU  - Eleonora Andreotti
AU  - Raffaella Mulas
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01121
UR  - https://arxiv.org/abs/2611.01121
AB  - We extend the non-backtracking Laplacian for graphs, introduced by Jost, Mulas and Torres, to hypergraphs. The operator is defined on the permutations of the edges and is normalized by the number of edges through which a non-backtracking walk can continue. We show that it satisfies a symmetry that generalizes the graph case, and that it can be obtained from the random walk Laplacian of a directed graph by rescaling if and only if all edges have the same cardinality. Moreover, we show that, up to copies of the eigenvalue $1$, its spectrum can be computed from a much smaller matrix indexed by the incidences of the hypergraph, and we use this reduction to bound the remaining eigenvalues away from $1$.
ER  -