Nonbacktracking Matrix

The nonbacktracking matrix, also called the Hashimoto matrix (Hashimoto 1989), of a finite simple graph is the binary matrix whose rows and columns are indexed by the two directed edges obtained from each edge in and whose entries are

(1)

Thus exactly when the directed edge can follow without immediately traversing the same edge in reverse.

If has edges, then is a generally nonsymmetric matrix. Entries of count directed walks of length with no immediate reversal. The matrix spectrum separates informative eigenvalues from a bulk of uninformative eigenvalues in sparse random graph models, making the matrix useful for community detection (Krzakala et al. 2013).

The Bethe Hessian is a symmetric matrix of vertex dimension that retains the informative real spectral data of the nonbacktracking matrix for suitable parameter values. Nonbacktracking operators can also be defined for hypergraphs by indexing incident vertex-hyperedge pairs (Chodrow et al. 2023).