Source-linked AI summary
On spectral hypergraph theory of the adjacency tensor
Kelly J. Pearson, Tan Zhang
TL;DR
Different notions of eigenvalues for a hypergraph can lead to surprisingly different outcomes. The paper studies H- and E/Z-eigenvalues of adjacency tensors, establishes positivity and uniqueness results under stated conditions, and investigates E-spectrum symmetry.
Problem
Different notions of eigenvalues used for a given hypergraph may lead to surprisingly different outcomes.
Method
The paper studies H- and E/Z-eigenvalues of uniform multi-hypergraph adjacency tensors, including maximization of AHx^m over S+ for Z-eigenvalues.
Results
For connected m-multigraphs, the paper proves a positive Z-eigenvalue with a nonnegative Z-eigenvector; under stated conditions, the largest H-eigenvalue has a unique strictly positive eigenvector.
Takeaways & Limitations
The results give conditions connecting largest positive H- or Z-eigenvalues to strictly positive eigenvectors and characterize symmetry of the E-spectrum in the studied cases.
Takeaways & Limitations
The Z-eigenvalue analysis must address that the adjacency tensor is always reducible for m-graphs, and some results assume an m-partite m-graph with even m.
Abstract
from arXiv · showhide
We study both $H$ and $E/Z$-eigenvalues of the adjacency tensor of a uniform multi-hypergraph and give conditions for which the largest positive $H$ or $Z$-eigenvalue corresponds to a strictly positive eigenvector. We also investigate when the $E$-spectrum of the adjacency tensor is symmetric.
0. Introduction
The paper addresses how nonlinear tensor eigenvalue notions produce different spectral behavior for hypergraphs. It studies H- and E/Z-eigenvalues of uniform multi-hypergraph adjacency tensors, including positive eigenvectors and E-spectrum symmetry.
- Hypergraph spectral theory remains less developed than graph spectral theory, with combinatorial and geometric connections described as interesting but elusive.
- Different tensor eigenvalue notions can yield surprisingly different results for the same hypergraph.
- The paper studies H- and E/Z-eigenvalues of adjacency tensors for uniform multi-hypergraphs.
- A proof based on weak irreducibility extends earlier H-eigenvalue results to m-multigraphs.
- The authors give conditions for the largest positive Z-eigenvalue to have a nonnegative, and under an additional connectivity concept strictly positive, eigenvector.
- The paper also investigates symmetry of the adjacency tensor’s E-spectrum and provides bounds, examples, and open questions.
1. Basic Tensor Definitions
This section introduces tensor notation, irreducibility, symmetry, H-, E-, and Z-eigenpairs, and the spectral-radius concepts used later. It also distinguishes the proof machinery available for H-eigenvalues from the limitations of applying it to Z-eigenvalues.
- A tensor is irreducible when no nonempty proper index subset satisfies the specified zero-entry condition; otherwise it is reducible.
- Weak irreducibility is defined through strong connectivity of the directed graph associated with a nonnegative tensor.
- E-eigenpairs may be complex, whereas Z-eigenpairs are E-eigenpairs whose eigenvalue and eigenvector are both real.
- H-eigenpairs are real solutions of the tensor eigenvalue equations, and the H-spectral radius is defined using the eigenvalue of maximum modulus.
- Generalized Perron-Frobenius results establish positive H-eigenvectors under irreducibility assumptions, with differences concerning uniqueness and boundary eigenvectors.
- The contraction-mapping technique used for H-eigenvalues does not apply to the Z-eigenvalue problem because the relevant map is not sub-linear for m > 2.
2. Basic Hypergraph Definitions
This section defines hypergraphs and uniform multi-hypergraphs, together with connectivity, multipartiteness, regularity, completeness, and adjacency tensors. These definitions establish the combinatorial objects represented by the later spectral analysis.
- A hypergraph consists of a finite vertex set and an edge collection, while a multi-hypergraph allows the edge collection to be a multiset.
- An m-uniform multi-hypergraph has m total memberships in every edge, including repeated memberships.
- An m-complete hypergraph contains every m-element vertex subset as an edge, while an r-regular hypergraph gives every vertex degree r.
- A chain alternates vertices and distinct edges, and connectivity requires such a chain between every pair of vertices.
- A k-partite hypergraph partitions vertices into k parts so each edge’s k selected vertices lie in distinct parts.
- The adjacency tensor of an m-multigraph is symmetric and records whether an indexed m-tuple belongs to an edge.
3. Main Results
The paper establishes spectral results for adjacency tensors of uniform multi-hypergraphs, including positive H- and Z-eigenvectors, a connectivity condition governing strict positivity, and symmetry conditions for the E-spectrum.
- H-eigenvalues: A connected m-multigraph has a largest H-eigenvalue equal to the adjacency tensor’s spectral radius, with a unique strictly positive eigenvector up to positive scaling.The eigenvalue is characterized as the maximum of the homogeneous polynomial over the nonnegative unit sphere.
- Z-eigenvalues: Every m-multigraph has a positive Z-eigenvalue with a corresponding nonnegative eigenvector, together with degree- and edge-count-based bounds.The largest real Z-eigenvalue is obtained from maximizing the homogeneous polynomial on the standard unit sphere.
- Connectivity structure: For m greater than 2, nicely-connectedness is equivalent to irreducibility of the adjacency tensor, although a nicely-connected hypergraph can have a reducible but weakly irreducible adjacency tensor.The property is intrinsically determined by the hypergraph rather than by any tensor associated with it.
- Z-eigenvector positivity: Nicely-connectedness is equivalent to strict positivity of every Z-eigenvector associated with a Z-eigenpair, while failure of this condition permits a positive eigenvalue with a zero coordinate.This connectivity notion is structurally distinct from ordinary connectivity and regularity, and is defined directly from the hypergraph.
- Special cases and computation: For an r-regular m-graph, λ0 = rn^−(m−2)/2 is a Z-eigenvalue associated with the all-ones vector; m-complete graphs likewise yield positive Z-eigenvectors.Connected m-multigraphs also support a linearly convergent NQZ approach after a small positive perturbation.
- E-spectrum: If m is odd, or if the hypergraph is m-partite with m even, every E-eigenvalue occurs with its negative, and the sum of all E-eigenvalues is zero.The paper gives these as the two conditions ensuring symmetry of the E-spectrum.
4. Examples and Open Problems
The examples examine positive Z-eigenvectors, eigenvalue multiplicity, and symmetric E/Z-spectra across connected, regular, complete, and multipartite hypergraphs. They also formulate open questions about uniqueness, geometric simplicity, and spectral symmetry.
- Positive Z-eigenvectors: The largest Z-eigenvalue can correspond to a strictly positive eigenvector, while other positive eigenvalues may correspond to nonpositive eigenvectors.In one 2-regular 3-multigraph, 0.951057 has eigenvector (0.850651, 0.525731), whereas 0.5 has eigenvector (0,1).
- Positive Z-eigenvectors: Connected hypergraphs need not have positive Z-eigenvectors for every positive Z-eigenvalue, and examples demonstrate failures of nice connectivity.One example has a positive eigenvalue whose eigenvector is not positive in all coordinates; another records V0={1}.
- Eigenvalue multiplicity: A connected hypergraph’s largest Z-eigenvalue may have multiple eigenvectors, so it need not be real geometrically simple.A nicely-connected non-regular 3-graph has infinitely many positive Z-eigenvectors for the largest positive Z-eigenvalue.
- Spectral symmetry: Examples illustrate symmetric E-spectra and symmetric Z-spectra for suitable regular or multipartite hypergraphs.A 1-regular 4-partite 4-graph has E-eigenvalues 0 and ±1, while a 3-regular 3-graph illustrates symmetric Z-spectrum.
- Open problems: For the complete 3-graph on five vertices, the largest positive eigenvalue has one eigenvector, whereas the other positive eigenvalues have multiple eigenvectors.The eigenvalues are obtained from an elimination polynomial, and the examples motivate questions about uniqueness and geometric simplicity.
- Open problems: The section asks which conditions ensure a unique positive eigenvector, geometric simplicity of the largest Z-eigenvalue, and symmetric adjacency-tensor spectra.These questions are posed for m-multigraphs, connected regular m-graphs, and connected m-graphs.