WorksMathematics
Non-backtracking Laplacian for hypergraphs
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 , 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 .
Introduction
Spectral graph theory studies the structural properties of a graph that are encoded in the eigenvalues of its associated operators, such as the adjacency matrix and the various Laplacians [15, 12, 21]. Among these, the non-backtracking matrix is of theoretical interest [18, 37, 36] and has proved remarkably effective in applications ranging from community detection [11, 22, 31, 10, 9] to node centrality [4, 23, 24, 39] and percolation [33, 13, 25]. Moreover, in [20], Jost, Mulas and Torres introduced the non-backtracking Laplacian and showed, computationally for graphs with a small number of nodes, that cospectral pairs are rarer for this operator than for the adjacency matrix, the Kirchhoff Laplacian, the normalized Laplacian and the non-backtracking matrix. Further spectral properties of this operator were established in [29], and a graph coloring number arising from that work was studied in [27].
The idea behind non-backtracking operators for graphs is the following. Fix a simple graph on nodes and edges, with minimum degree . Choosing an orientation for an edge means letting one of its endpoints be its input and the other its output, and we write for the oriented edge with input and output . Moreover, we let be the inverse of , and we let denote the oriented edges of . A non-backtracking random walk on is the Markov process on the oriented edges in which the walker at moves to each with and with equal probability , and the minimum degree assumption guarantees that at least one such exists. Seen as a process on the same walk is not Markovian, since the steps available at a vertex depend on how the walker arrived there, which is why we look at the oriented edges (Figure 1). The non-backtracking graph of (Figure 2), denoted , was introduced in 1989 by Hashimoto [19] as the directed graph whose vertices are the oriented edges of , having a directed edge from to precisely when the above transition is admissible, that is, when and . The transpose of the adjacency matrix of is the non-backtracking matrix of , while the random walk Laplacian of is the non-backtracking Laplacian of [20].

Figure 1. A non-backtracking walk is not Markovian as a process on the vertices, but it becomes Markovian as a process on the oriented edges. In (a) the cyclist only knows that they are at the vertex , and this is not enough to decide along which of the three edges at they may continue. In (b) their position is the oriented edge , which already records the vertex they came from: they may continue along or along (in purple), but not back along (dashed).
Figure 2. From a graph to its non-backtracking graph: the nodes of are the oriented edges of , with a directed edge from to when the output of is the input of and .
Hypergraphs, in which an edge may join any number of vertices, are the natural model for higher-order interactions, and their spectral theory has been developed for several operators; see, for instance, [6, 21] and the references therein. Non-backtracking techniques for hypergraphs have appeared as well: operators defined on the incidences of a hypergraph, that is, the edge–vertex pairs with , go back to the zeta function of Storm [35], and underlie spectral clustering and detectability methods [3, 14, 34] as well as the theory of percolation on hypergraphs [8]. These operators, however, are all of adjacency type, and to the best of our knowledge no Laplacian analogue has been proposed so far.
The closest object appears in the literature on hypergraph sampling: Nakajima, Kodakari and Aida [30] consider a non-backtracking walk that avoids both the previously visited node and the previously traversed edge, and derive its stochastic transition matrix on the incidences, together with its stationary distribution, with the aim of obtaining unbiased estimators of structural properties of large hypergraphs. Such a transition matrix does induce a Laplacian; being row-stochastic by construction, however, it is the random walk Laplacian of a weighted directed graph on the incidences, and its spectral theory is therefore that of a directed graph. This is an instance of a general phenomenon: transition probabilities are pairwise relations between states, and every hypergraph random walk Laplacian coincides with the random walk Laplacian of a weighted graph [28 Theorem 4.5]. An operator that is not reducible to a graph Laplacian must therefore fail to be row-stochastic, and the one we introduce below does. When and why higher-order models resist reduction to graph descriptions is currently under active discussion [38, 26, 32].
In this paper, we propose and study a generalization of the non-backtracking Laplacian for graphs [20, 29] to the case of hypergraphs. In line with the above discussion, a hypergraph Laplacian that cannot be reduced to the graph case must give up row stochasticity, and the off-diagonal entries of our operator are therefore not always probabilities.
Structure of the paper
In Section 2 we introduce the non-backtracking graph, matrix and Laplacian of a hypergraph, which reduce to those of [20] for graphs, and in Section 3 we compute the degrees and the size of the non-backtracking graph. In Section 4 we establish the first spectral properties of the non-backtracking Laplacian, including a symmetry that generalizes that of the graph case, and we show that it is an affine function of the random walk Laplacian of the non-backtracking graph if and only if the hypergraph is uniform. Finally, in Section 5, we study the eigenvalue 1, we show that the remaining eigenvalues can be computed from a smaller matrix, indexed by the incidences of the hypergraph, and we bound these eigenvalues away from 1.
Non-backtracking operators for hypergraphs
Throughout the paper we fix a hypergraph on nodes and edges. We let denote the edges of and, given , we let denote the cardinality of . We assume that has no repeated edges, that is, for .
The degree of a vertex , denoted , is the number of edges in which it is contained. We assume, from here on, that has minimum vertex degree and minimum edge cardinality . We also let
Moreover, given , we let
denote the permutations of the vertices in , listed with a fixed order.
Definition 2.1. Given a permutation of , we say that its first entry is its input, and we denote it by ; we say that its last entry is its output, and we denote it by . Moreover, we let
Example 2.2. If , then , and we can let
With this fixed order of the permutations of , we have that
and
Remark 2.3 (Permutations as orientations). The permutations of the edges generalize the orientations of graph edges. In fact, if is a graph, i.e. for all , then each edge has exactly two permutations, and , and these are precisely its two orientations and in the sense of [20]. In particular, the input and the output of Definition 2.1 are those of the corresponding oriented edge, and is the number of edges along which a non-backtracking walk that reaches through can continue. When , on the other hand, has more than two permutations, and when , a permutation is no longer determined by its input and output, since it also fixes the order in which the remaining vertices appear.
This generalization is not the only possible one, and several non-equivalent notions of orientation for hypergraph edges exist in the literature: an oriented edge may be defined as a pair of disjoint vertex sets, its tail and its head [17], as an ordered partition of its vertices [16], or as a list of its vertices in a fixed order [5]. All of them reduce to the orientations of a graph edge when . We adopt the last notion: the permutations are precisely the orientations of in the sense of [5], and their first and last entries provide the input and the output needed by the non-backtracking walk.
Generalizing the construction for graphs, we now define the non-backtracking graph of by letting the permutations of the edges play the role of the oriented edges. More precisely, a non-backtracking walk on moves from a permutation of to a permutation of a different edge , provided that the input of the latter is the output of the former (Figure 3).

Figure 3. A step of the non-backtracking walk on a hypergraph. The cyclist’s position is the permutation of , whose output is . They may continue along any permutation of a different edge whose input is , namely and (in purple), but not along a permutation of , such as (dashed).
Definition 2.4. The non-backtracking graph of is the directed graph such that:
;
There exists a directed edge in if and only if
Note that has nodes, which reduces to the oriented edges when is a graph.
We now generalize the non-backtracking matrix and the non-backtracking Laplacian of a graph as follows.
Definition 2.5. Let be the adjacency matrix of , i.e. the matrix with –entries such that
The non-backtracking matrix of is .
Definition 2.6. The non-backtracking Laplacian of is the matrix
where denotes the identity matrix and
Note that is invertible, since the assumption that implies that
for every . Hence, is well-defined.
Remark 2.7 (Consistency with the graph case). If is a graph, then Definitions 2.4, 2.5 and 2.6 recover the non-backtracking graph, matrix and Laplacian of [20]. In fact, by Remark 2.3, in this case the nodes of are the oriented edges of , and two oriented edges with belong to distinct edges if and only if . Moreover, is the out-degree of in ; therefore is the random walk Laplacian of .
Degrees and size of the non-backtracking graph
In this section we study the first structural properties of the non-backtracking graph . Recall from Definition 2.1 that
counts the edges through which a non-backtracking walk can continue after leaving through its output. If is a graph, this number coincides with the out-degree of in (Remark 2.7). We now compute the in- and out-degrees of the nodes of , and we show that coincides with the out-degree for every node of only in the graph case. In general, the out-degree counts the permutations, rather than the edges, through which the walk can continue. To count these permutations, we introduce the following notion.
Definition 3.1. The permutation degree of a vertex is
i.e. the number of permutations whose input is or, equivalently, the number of permutations whose output is .
Note that, if is a graph, then for every .
Lemma 3.2. Let , and let and . Then,
In particular, every node of has out-degree at least 1, and coincides with the out-degree matrix of if and only if is a graph.
Proof. By Definition 2.4, the out-neighbors of are the permutations with and . For each with , there are exactly permutations of whose input is . Therefore,
and the formula for the in-degree follows in the same way, by counting, for each with , the permutations of whose output is . Since , there exists at least one with , hence the out-degree is at least 1. Moreover, the sum above has exactly terms, each of which is at least 1. Hence, if and only if , i.e. , for every with . Since every vertex of is the output of some permutation of , letting range over all of shows that coincides with the out-degree matrix of if and only if for every edge that meets some other edge. Since , every edge meets some other edge, hence this condition is equivalent to for all , that is, to being a graph. □
Remark 3.3. Fix and let . The row of indexed by has an entry equal to 1 for each out-neighbor of in , and all other entries equal to 0, therefore it sums to . Multiplying by divides this row by . Hence, by Lemma 3.2, the row of indexed by sums to
The sum on the right has exactly terms, one for each edge through which the walk can continue after leaving at , and each term is at least 1. Therefore, the row sum is at least 1, with equality if and only if for every with . As in the proof of Lemma 3.2, this condition holds for every node of if and only if is a graph. Hence, in contrast with the graph case, is row-stochastic, and is the random walk Laplacian of , if and only if is a graph.
We can now prove the following generalization of [20 Lemma 3.1].
Lemma 3.4. The non-backtracking graph has
Proof. The number of nodes was already observed after Definition 2.4. Now, observe that equals the sum of the out-degrees of the nodes of . We group the nodes of according to their edge and their output vertex: for each and each , there are exactly permutations of whose output is , and by Lemma 3.2 each of them has out-degree . Hence,
Remark 3.5. If is a graph, then for all , therefore Lemma 3.4 gives
which is the same as in [20 Lemma 3.1].
We illustrate the results above on two families of hypergraphs. The first is a family of uniform hypergraphs, that is, hypergraphs whose edges all have the same cardinality; if this cardinality is , we say that the hypergraph is -uniform. Moreover, we say that a hypergraph is -regular if all its vertices have degree $r`.
Example 3.6. Given , the -lattice is the hypergraph whose vertices are the cells of an grid and whose edges are its rows and columns [2, 1]. It is -uniform and -regular, and for , it is the cycle graph on 4 vertices.
Let be the 3-lattice (Figure 4a): its vertices are for , while its edges are the rows and the columns . In this case, , , and for all . Since for every vertex, we have for every permutation, so that and . Moreover, for every , so that, by Lemmas 3.2 and 3.4, every node of has out-degree , and has

Figure 4. In (a), the 3-lattice, whose edges are the rows and the columns . In (b), the cyclist’s position is the permutation of , whose output is . The only other edge through is , so the cyclist may continue along its permutations with input (in purple), but not along a permutation of (dashed).
since each vertex lies in exactly two edges, which give two ordered pairs . The local structure of is shown in Figure 4b: from a permutation of a row with output , the walk can only continue into the unique column through , along either of its permutations with input , and vice versa. In particular, every walk on alternates between permutations of rows and permutations of columns, therefore is bipartite.

Figure 4a. The 3-lattice.

Figure 4b. A step of the walk from a permutation of .
In the lattices, all edges have the same cardinality. In the next family, the cardinalities of the edges vary.
Example 3.7. Given and , consider the rooted tree in which every node other than the leaves has exactly children and all leaves are at distance from the root (the complete -ary tree of depth ). The -laminar hypergraph has as vertices the leaves of the tree and, as edges, for each internal node of the tree, that is, for each node that is not a leaf, the set of leaves below it (Figure 5).
If an internal node has height , that is, if its leaves are at distance below it, then it gives an edge of cardinality , which we call a level- edge. In particular, any two edges are either disjoint or one of them contains the other.
Labeling the leaves by the words in , the level- edges are the sets of words sharing the first letters. Hence, has nodes and edges, of which $k^{p-\ell}

Figure 5. The laminar hypergraph obtained from the binary tree of depth 3. Each internal node of the tree gives the edge formed by the leaves below it, drawn in the same color: the four nodes at height 1 give the level-1 edges , the two nodes at height 2 give the level-2 edges , and the root gives the level-3 edge .
have cardinality ; since every leaf has exactly one ancestor at each height, for all , and is non-uniform. Since and , the hypergraph satisfies our assumptions.
We consider (Figure 5), which has , , and edges of cardinality 2 (four of them, level 1), 4 (two of them, level 2) and 8 (one, level 3). Since for every vertex, we have that for every permutation, therefore and
Moreover, for every , hence, by Lemmas 3.2 and 3.4, a permutation of a level- edge has out-degree in – namely 5046, 5041 and 7 for – and has
Comparing with Example 3.6 shows the effect of non-uniformity. As for the 3-lattice, all vertices of have the same degree, therefore is a scalar matrix; yet, since is not uniform, the out-degrees in depend on the level, ranging from 7 to 5046. Hence, the row sums of equal 2523, 2520.5 and 3.5 on the permutations of the level-1, level-2 and level-3 edges, respectively, and is far from being row-stochastic (Remark 3.3).
First spectral properties
We now turn to the spectral properties of . Given a square matrix , we let denote its spectrum, and we let denote the closed disk of center and radius .
If is a graph, then by [20 Remark 3.3], has eigenvalues (counted with algebraic multiplicity) that sum to . Moreover, in this case [7] and therefore, the real eigenvalues of are contained in the interval . For hypergraphs, these facts generalize as follows.
Proposition 4.1. The non-backtracking Laplacian has eigenvalues (counted with algebraic multiplicity) that sum to . Moreover,
where is the largest edge cardinality. In particular, the real eigenvalues of are contained in the interval .
Proof. Since is a matrix, it has eigenvalues, counted with algebraic multiplicity, and their sum is . Since all diagonal entries of equal , we have that . This proves the first claim.
Now, all the Gershgorin disks of are centered at . By Lemma 3.2, the radius of the disk corresponding to the row of indexed by , with , is
since the sum has exactly terms, each bounded above by . Hence, by the Gershgorin Disk Theorem,
:::
We now generalize [20 Theorem 3.8] to hypergraphs. To this end, we give the following definitions.
Definition 4.2. The reversal of a permutation is the permutation of the same edge. We let be the permutation matrix of the map , and, given , we define their -product as
where is the usual complex inner product.
With this notation, [20 Theorem 3.8] generalizes as follows.
Theorem 4.3. Let be the non-backtracking Laplacian of a hypergraph. Then,
, i.e., is -symmetric;
is self-adjoint with respect to the -product, i.e., is -self-adjoint;
If is an eigenpair for and is not real, then
Proof. Note that, by definition, and for every , and that and , since reversing a permutation twice gives back the original one.
Let be permutations of and , respectively, so that and are also permutations of and . We write for the entry of in the row indexed by and the column indexed by . For we have that
where denotes the indicator function. When this entry is non-zero, let . Then,
so that . On the diagonal, both and equal , and if and only if . Therefore,
for all , which proves the first claim.
Since and , we have that
where we have used that , which follows from the first claim, and that is a real matrix. Therefore, is self-adjoint with respect to the -product.
The second claim implies that, if is an eigenpair for , then
Hence, if , i.e. is not real, then . Since for every , this is the identity in the statement.
Remark 4.4. The proof of Theorem 4.3 only uses the fact that depends on alone. This singles out among the natural ways of counting how the walk can continue after exiting at , namely:
the number of edges with , which is our choice;
the number of pairs with , and ;
the number of permutations, i.e. the out-degree of in (Lemma 3.2).
The last two also depend on , and therefore yield a PT-symmetric operator if and only if any two edges sharing a vertex have the same cardinality, i.e. if and only if every connected component of is uniform; in this case, the three normalizations are proportional on each component.
On the other hand, only the last one always makes row-stochastic: the first does so if and only if is a graph (Remark 3.3), and the second if and only if all edges have at most 3 vertices. Hence, unless every connected component of is uniform, none of these normalizations is both PT-symmetric and stochastic: our choice preserves the symmetry, at the price of stochasticity.
We conclude this section by showing that the uniform hypergraphs are precisely those for which is an affine image of the random walk Laplacian of , so that its spectrum is obtained from that of a random walk Laplacian by an affine transformation. To this end, we let denote the out-degree matrix of , and we let
denote the random walk Laplacian of . Recall that is -uniform if all its edges have cardinality .
Proposition 4.5. There exist constants such that
if and only if is uniform. In this case, if is -uniform, then and , and
is the image of under the map ;
the constant functions are eigenfunctions of with eigenvalue .
Proof. Assume first that is -uniform. By Lemma 3.2, every with satisfies
Hence , and therefore
Conversely, assume that . Let be a permutation of with output . By Lemma 3.2, has at least one out-neighbor in , and comparing the entries in position gives , that is,
If two edges and share a vertex , applying this to a permutation of and to a permutation of , both with output , gives , i.e. . Hence, every connected component of is uniform. Moreover, if the edges of a component have cardinality , then for every vertex of this component we have , and the identity above gives . Since does not depend on the component, all components have the same edge cardinality, that is, is uniform. Finally, comparing the diagonal entries, which are all equal to in both and , gives .
Claim 1 follows from the identity
which maps each eigenvalue of to , with the same eigenvectors. For Claim 2, observe that every node of has at least one out-neighbor by Lemma 3.2, so that is row-stochastic and the constant functions lie in the kernel of . By the identity above, they are therefore eigenfunctions of with eigenvalue .
The reduced non-backtracking Laplacian
Recall that the incidences of are the edge–vertex pairs with , and let
In this section we show that, although is defined on the permutations of the edges, its spectrum can be computed from a much smaller matrix indexed by the incidences of , namely the reduced non-backtracking Laplacian of Definition 5.1 below. For instance, for the laminar hypergraph of Example 3.7, this reduces the size of the eigenvalue problem from 40376 to 24. This is possible because, by definition of the non-backtracking graph, the out-neighbors of a permutation in depend only on its edge and its output, and its in-neighbors depend only on its edge and its input. As a consequence, the eigenvalues of are those of the reduced non-backtracking Laplacian, together with additional eigenvalues that are equal to 1 (Theorem 5.4). The permutations still play a role in the spectrum, but only through their number: the entry of the reduced matrix corresponding to a step through from to is proportional to , which is the number of permutations of with input and output .
Since the spectra of and of the reduced non-backtracking Laplacian determine each other, one might take the latter as the definition of the non-backtracking Laplacian of a hypergraph. We explain in Remark 5.5 why we nevertheless work with .
Definition 5.1. The reduced non-backtracking Laplacian of is the matrix
where is the matrix defined by
In words, the incidence represents a walker that has just left through , and moves it through a different edge and out of it through a vertex , with weight , where counts the permutations of with input and output .
If is a graph, then and is the non-backtracking Laplacian , after identifying each incidence with the orientation of whose output is .
The key ingredient in the proofs of Theorem 5.4 and Corollary 5.6 is the following factorization of through the incidences. In the statement, for a positive integer , we let denote the all-ones matrix.
Lemma 5.2. Let and be the matrices defined, for and , by
and let and be the matrices
Moreover, let and . Then:
;
;
and are symmetric. Moreover, grouping the incidences by their vertex, is block diagonal with blocks
and therefore its eigenvalues are and . Grouping the incidences by their edge, is block diagonal with blocks
and therefore its eigenvalues are and .
In particular, , and are invertible.
Proof. Note that each row of (respectively, of ) contains exactly one non-zero entry, marking the incidence given by the output (respectively, the input) of the corresponding permutation. The matrix encodes the admissible changes of edge, since the walk leaves and enters a different edge through the same vertex, and normalizes by the number of such choices.
Let be permutations of and , respectively. A direct computation gives
so that . Moreover, , since only if , in which case . Hence,
Observe that
since the permutations of with fixed distinct input and output are exactly , while no permutation has equal input and output. Therefore,
Symmetry of and is clear from their entries, and the block structure follows from the computations above. Since has eigenvalues and , the eigenvalues are as stated, and they are non-zero because and . Hence and are invertible, and so is .
Example 5.3. We illustrate Lemma 5.2 on a single edge , with the permutations ordered as in Example 2.2. With rows and columns grouped by edge, and are block diagonal, with one block for each edge. The blocks of and corresponding to , with rows indexed by and columns by the incidences , are
Here, each row of marks the output of the corresponding permutation, and each row of its input. In particular, two permutations of have the same row of precisely when they have the same output. Moreover, the corresponding block of is
whose entry counts the permutations of with input and output , which here is exactly one for every . For an edge with , the corresponding block would be , the factor recording the two possible orders of the two vertices of other than the input and the output. Through the identity of Lemma 5.2, this is where the factor in the entries of comes from.
We can now prove the main result of this section: by Lemma 5.2, the non-backtracking Laplacian is similar to the direct sum of the reduced non-backtracking Laplacian and an identity matrix. For a multiset, we write for the element repeated times.
Theorem 5.4. The non-backtracking Laplacian is similar to the block diagonal matrix
In particular:
as multisets, ;
is an eigenvalue of if and only if is not a graph, in which case it is semisimple, with multiplicity ;
is diagonalizable if and only if is diagonalizable.
Proof. Let and . By Lemma 5.2, and , which is invertible. It follows that has full column rank and has full row rank, therefore has dimension . Moreover, : if , then , therefore . Hence, , and both subspaces are invariant under , since and for . In a basis formed by the columns of followed by a basis of , the matrix is therefore represented by , and by . We now prove the three claims.
Similar matrices have the same eigenvalues, with the same algebraic multiplicities, and the eigenvalues of a block diagonal matrix are those of its blocks.
Since is invertible, is not an eigenvalue of . Hence, the eigenvalue of only comes from the block , so that its algebraic and geometric multiplicities both equal , and it is semisimple. Moreover, if and only if for some , that is, if and only if is not a graph.
A block diagonal matrix is diagonalizable if and only if each of its blocks is, and is diagonal.
Remark 5.5 (Why and not ). By Theorem 5.4, the spectra of and determine each other, since and only depends on the cardinalities of the edges. Moreover, if is a graph, then , after identifying each incidence with the orientation of whose output is . One might therefore take as the definition of the non-backtracking Laplacian of a hypergraph. We nevertheless work with , because it is conceptually more natural. Indeed, is obtained from the adjacency matrix of a directed graph, normalized by the number of edges through which the walk can continue, whereas the weights of would be hard to motivate directly: they arise from , as the numbers of permutations of with fixed input and output.
While Theorem 5.4 determines the multiplicity of the eigenvalue , Lemma 5.2 also allows us to bound the other eigenvalues of away from .
Corollary 5.6. Every eigenvalue of satisfies
Proof. By Theorem 5.4, , that is, for some , so that . By Lemma 5.2, , where and are symmetric and invertible. Since the spectral norm of a symmetric matrix is the largest absolute value of its eigenvalues, the eigenvalues given in Lemma 5.2 yield
Since every eigenvalue of a matrix is bounded in absolute value by its spectral norm, and is an eigenvalue of , we obtain
which proves the claim.
In Corollary 5.6, the upper bound is the radius of the disk of Proposition 4.1, while the lower bound is new. For graphs, the lower bound is , which is the bound of [20 Section 4].
Remark 5.7. Operators indexed by the incidences of a hypergraph also appear in [14], where the incidences are called pointed edges. There, the non-backtracking operator, which we denote by , has entry from to if and only if , and [14 Definitions 2.1–2.2]: the walk crosses from to , and then moves to another edge at . Identifying with the incidence , Definition 5.1 gives
with as in Lemma 5.2. That is, is obtained from by weighting each crossing of an edge by the number of permutations of with the corresponding input and output, and by normalizing by the number of edges through which the walk can continue. Since and are both diagonal, conjugating by shows that is similar to , where
In particular, if takes the same value on all incidences, as is the case when all vertices have the same degree and either is -uniform, with , or all edges have at most 3 vertices, with , then . In general, is not scalar, and the two spectra need not be related in such a simple way.
Example 5.8 (Example 3.6, continued). Let be the 3-lattice of Example 3.6. Its set of incidences has elements and, since and for all and , all non-zero entries of equal : that is, is the adjacency matrix of the directed graph on in which, from an incidence , the walk moves to the unique other edge and exits it at either of the two vertices of (Figure 6). A direct computation shows that the characteristic polynomial of is
so that consists of , of with multiplicity 4 each, and of with multiplicity 4 each. Hence, by Theorem 5.4, as a multiset,
We point out three facts. First, is the eigenvalue of the constant functions, in accordance with Proposition 4.5. Second, is symmetric with respect to the map . As in the graph case [20 Proposition 3.4], this follows from the bipartiteness of observed in Example 3.6. Third, both bounds of Corollary 5.6 are sharp in this example: the upper bound , which is also the radius of the disk of Proposition 4.1, is attained by the eigenvalues and , and the lower bound by the eigenvalues and .

Figure 6. The directed graph on the 18 incidences of the 3-lattice whose weighted adjacency matrix is ; all weights equal . Top: the incidences of the rows; bottom: those of the columns. From , the walk crosses the column and exits it at either of its two other vertices (in purple); from , it crosses the row and exits it at either of its two other vertices (in teal). The arcs out of and are highlighted: they continue the walk of Figure 4, from the cyclist’s position .
Example 5.9 (Example 3.7, continued). Let , with vertices , level-1 edges and , and level-2 edge . As for the 3-lattice, for every vertex, therefore and , but in this case, is not uniform. The matrix has size 8, while has size (Figure 7): from an incidence of a level-1 edge, the walk enters and exits it at any of its three other vertices, with weight ; from an incidence , it enters the level-1 edge of and exits it at its other vertex, with weight 1. A direct computation gives the characteristic polynomial of , hence, by Theorem 5.4,
Figure 7. The weighted directed graph on the 8 incidences of whose weighted adjacency matrix is . From an incidence of a level-1 edge, the walk crosses and exits it at any of its three other vertices (in purple, weight 2); from an incidence , it crosses the level-1 edge of and exits it at its other vertex (in teal, weight 1). The arcs out of and are highlighted: they show two steps of the walk from the cyclist’s position .
As for the lattice, is symmetric with respect to , since every walk on alternates between the level-1 edges and , therefore is bipartite. Unlike for the lattice, however, neither bound of Corollary 5.6 is sharp: the eigenvalues of different from 1 lie at distance between and from 1, while the two bounds equal 1 and . Moreover, the constant functions are not eigenfunctions of , since the row sums of equal 6 on the permutations of the level-1 edges and 1 on those of (Remark 3.3); accordingly, unlike in the uniform case of Proposition 4.5, has no eigenvalue of the form .
Tool and computational resource disclosure
The authors used Claude as a tool for language polishing, for identifying possible inconsistencies or errors in preliminary drafts, and for drafting figures.
Funding
Raffaella Mulas is supported by the Dutch Research Council (NWO) through the grant VI.Veni.232.002 (Grant ID: https://doi.org/10.61686/NLUFV33835), which also supported Eleonora Andreotti’s research visit to VU Amsterdam in June 2026, during which this project was developed. Eleonora cycled from Trento to Amsterdam for this visit and returned by bus, so her bike ride was non-backtracking.
References
- [1]E. Andreotti. Generalizing lattice structures to hypergraphs: spectra of clique and hyperedge- based Laplacians. Linear Algebra and its Applications, 751:100–125, 2026.arxiv.org/abs/2511.11138
- [2]E. Andreotti and R. Mulas. Signless normalized Laplacian for hypergraphs. Electronic Journal of Graph Theory and Applications, 10(2):485–500, 2022.DOI
- [3]M. C. Angelini, F. Caltagirone, F. Krzakala, and L. Zdeborová. Spectral detection on sparse hypergraphs. In 53rd Annual Allerton Conference on Communication, Control, and Computing, pages 66–73. IEEE, 2015.DOI
- [4]F. Arrigo, P. Grindrod, D. J. Higham, and V. Noferini. Non-backtracking walk centrality for directed networks. Journal of Complex Networks, 6(1):54–78, 2018.DOI
- [5]T. Austin and T. Tao. Testability and repair of hereditary hypergraph properties. Random Structures & Algorithms, 36(4):373–463, 2010.DOI
- [6]A. Banerjee. On the spectrum of hypergraphs. Linear Algebra and its Applications, 614:82–110, 2021. Special Issue ILAS 2019.arxiv.org/abs/1711.09356
- [7]F. Bauer. Normalized graph Laplacians for directed graphs. Linear Algebra and its Applications, 436(11):4193–4222, 2012.arxiv.org/abs/1107.4847
- [8]G. Bianconi and S. N. Dorogovtsev. Theory of percolation on hypergraphs. Physical Review E, 109(1):014306, 2024.DOI
- [9]M. Bolla. The non-backtracking random walk and its usage for vertex clustering. arXiv preprint arXiv:2512.24434, 2025.arxiv.org/abs/2512.24434
- [10]M. Bolla, H. Reittu, and F. Abdelkhalek. Clustering the nodes of sparse edge-weighted graphs via non-backtracking spectra. In Future of Information and Communication Conference, pages 81–99. Springer, 2025.DOI
- [11]C. Bordenave, M. Lelarge, and L. Massoulié. Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE, 2015.DOI
- [12]A.E. Brouwer and W.H. Haemers. Spectra of graphs. Springer Science & Business Media, 2011.
- [13]C. Castellano and R. Pastor-Satorras. Relevance of backtracking paths in recurrent-state epidemic spreading on networks. Physical Review E, 98(5):052313, 2018.DOI
- [14]P. S. Chodrow, N. Eikmeier, and J. Haddock. Nonbacktracking spectral clustering of nonuniform hypergraphs. SIAM J. Math. Data Sci., 5(2):251–279, 2023.arxiv.org/abs/2204.13586
- [15]F. Chung. Spectral graph theory. American Mathematical Soc., 1997.
- [16]H. Galeana-Sánchez and M. Manrique. Directed hypergraphs: a tool for researching digraphs and hypergraphs. Discussiones Mathematicae Graph Theory, 29(2):313–335, 2009.
- [17]G. Gallo, G. Longo, S. Pallottino, and S. Nguyen. Directed hypergraphs and applications. Discrete Applied Mathematics, 42(2-3):177–201, 1993.DOI
- [18]C. Glover and M. Kempton. Some spectral properties of the non-backtracking matrix of a graph. Linear Algebra and its Applications, 618:37–57, 2021.DOI
- [19]K. Hashimoto. Zeta functions of finite graphs and representations of p-adic groups. In Automorphic Forms and Geometry of Arithmetic Varieties, volume 15 of Advanced Studies in Pure Mathematics, pages 211–280. Elsevier, 1989.
- [20]J. Jost, R. Mulas, and L. Torres. Spectral theory of the non-backtracking Laplacian for graphs. Discrete Mathematics, 346(10):113536, 2023.DOI
- [21]J. Jost, R. Mulas, and D. Zhang. Spectra of Discrete Structures. Number 221 in Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2026.DOI
- [22]F. Krzakala, C. Moore, E. Mossel, J. Neeman, A. Sly, L. Zdeborová, and P. Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935–20940, 2013.DOI
- [23]Y. Lin and Z. Zhang. Non-backtracking centrality based random walk on networks. The Computer Journal, 62(1):63–80, 2019.arxiv.org/abs/1803.03087
- [24]T. Martin, X. Zhang, and M. E. J. Newman. Localization and centrality in networks. Physical Review E, 90(5):052808, 2014.DOI
- [25]F. Morone and H. A. Makse. Influence maximization in complex networks through optimal percolation. Nature, 524:65–68, 2015.DOI
- [26]E. M. Moutiou. Graphs are focal hypergraphs: strict containment in higher-order interaction dynamics. arXiv preprint arXiv:2603.04215, 2026.
- [27]R. Mulas. Maximal colourings for graphs. Graphs and Combinatorics, 40(93), 2024.arxiv.org/abs/2307.10910
- [28]R. Mulas, C. Kuehn, T. Böhle, and J. Jost. Random walks and laplacians on hypergraphs: When do they match? Discrete Applied Mathematics, 317:26–41, 2022.arxiv.org/abs/2106.11663
- [29]R. Mulas, D. Zhang, and G. Zucal. There is no going back: Properties of the non-backtracking Laplacian. Linear Algebra Appl., 680:341–370, 2024.arxiv.org/abs/2303.00373
- [30]K. Nakajima, M. Kodakari, and M. Aida. Sampling nodes and hyperedges via random walks on large hypergraphs. Applied Network Science, 10:19, 2025.
- [31]M. Newman. Spectral community detection in sparse networks. arXiv preprint arXiv:1308.6494, 2013.arxiv.org/abs/1308.6494
- [32]C. Rommens, P. Traversa, G. Ferraz de Arruda, and Y. Moreno. The informational cost of structure: Representational complexity in networked dynamical systems, 2026.arxiv.org/abs/2607.03608
- [33]M. Shrestha, S. V. Scarpino, and C. Moore. Message-passing approach for recurrent-state epidemic models on networks. Physical Review E, 92(2):022821, 2015.pubmed.ncbi.nlm.nih.gov/26382468
- [34]L. Stephan and Y. Zhu. Sparse random hypergraphs: Non-backtracking spectra and community detection. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 567–575. IEEE, 2022.arxiv.org/abs/2203.07346
- [35]C. K. Storm. The zeta function of a hypergraph. Electron. J. Combin., 13(1):R84, 2006.DOI
- [36]L. Torres. Non-backtracking Spectrum: Unitary Eigenvalues and Diagonalizability. arXiv preprint arXiv:2007.13611, 2020.arxiv.org/abs/2007.13611
- [37]L. Torres. Geometric multiplicity of unitary non-backtracking eigenvalues. arXiv preprint arXiv:2205.02004, 2022.arxiv.org/abs/2205.02004
- [38]L. Torres. The cost of representing higher-order dynamics on graphs: A theoretical framework, 2026. Scroll Press.DOI
- [39]L. Torres, K. S. Chan, H. Tong, and T. Eliassi-Rad. Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization. SIAM Journal on Mathematics of Data Science, 3(2):656–675, 2021.DOI

