Graph Bispectrum for Nonlinear Mode Interactions

Technical Summary: Graph Bispectrum for Nonlinear Mode Interactions

Problem Statement
Conventional Graph Signal Processing (GSP) relies heavily on second-order statistics, such as covariance and graph power spectra, to analyze signals defined on irregular domains (e.g., social networks, sensor arrays, brain connectivity). While effective for linear systems, these methods fail to capture nonlinear interactions between graph modes that are prevalent in complex dynamical systems, particularly in neuroscience. Classical higher-order spectral analysis (e.g., bispectrum and bicoherence) successfully detects nonlinear phase coupling in time-series data by leveraging the additive structure of Fourier frequencies. However, extending these methods to graphs is nontrivial because graph frequencies (Laplacian eigenvalues) are generally irregular and lack a natural addition rule, preventing the direct application of classical bispectral formulations. This creates a gap in GSP: there is no established framework for analyzing higher-order interactions between graph modes.

Methodology
The authors propose a Graph Bispectrum formulation to characterize third-order interactions in graph signals. The methodology proceeds as follows:

1. Graph Bispectrum Tensor Definition:
   The paper defines a graph bispectrum tensor $B_{ijk} = E[\hat{x}_i \hat{x}_j \hat{x}_k]$, where $\hat{x}$ represents the Graph Fourier Transform (GFT) coefficients. Unlike classical bispectrums that rely on frequency sums ($f_1 + f_2$), graph mode interactions are governed by the pointwise product of graph harmonics (eigenvectors). The interaction between modes $i$ and $j$ contributing to mode $k$ is quantified by coefficients $C_{ijk}$, derived from the projection of the product of eigenvectors $u_i \odot u_j$ onto the basis $u_k$.

   • Theoretical Validation: The authors prove that for a cycle graph (where eigenvectors match the discrete Fourier basis), the interaction coefficients $C_{ijk}$ are non-zero only if $k \equiv i + j \pmod N$, thereby recovering the classical frequency coupling structure.

2. Compact Graph Bicoherence:
   Recognizing that the full bispectrum tensor is high-dimensional ($N^3$) and difficult to interpret, the authors introduce a Compact Graph Bicoherence ($\gamma_k$). This is derived by:

   • Considering the quadratic signal $x \odot x$.
   • Projecting this signal onto the graph Fourier basis to obtain a mode-wise representation of nonlinear interactions.
   • Defining a compact statistic $b_k = E[\hat{x}_k \widehat{(x^2)}_k]$ and normalizing it to obtain $\gamma_k$.
     This results in a low-dimensional ($N$), scale-invariant measure that quantifies the alignment between a specific graph mode and its nonlinear interaction component.

3. Global Measure:
   A Normalized Graph Bispectral Energy is also defined as a global scalar measure of higher-order interaction strength across the entire graph.

Key Contributions

• Theoretical Formulation: The paper establishes a rigorous definition of the graph bispectrum tensor and compact bicoherence, bridging the gap between classical higher-order spectral analysis and GSP.
• Statistical Properties: The authors prove that the proposed measures vanish for zero-mean Gaussian graph signals (Property 1), making them sensitive indicators of nonlinearity and non-Gaussianity. They also demonstrate scale invariance.
• Dynamical Interpretation: The framework provides a dynamical interpretation where the evolution of a graph mode depends not only on linear diffusion but also on nonlinear interactions driven by other modes, modeled via a graph analogue of reaction-diffusion systems.
• Practical Representation: The introduction of the compact bicoherence reduces the complexity of higher-order analysis to a manageable, interpretable, and computationally efficient form.

Experimental Results
The proposed method was validated on two datasets:

1. Synthetic Random Graphs:

   • Experiments compared linear Gaussian signals against nonlinear signals generated via quadratic interactions on a 32-node Erdős-Rényi graph.
   • Finding: While the graph power spectra (second-order statistics) were nearly identical for both signal types, the compact graph bicoherence and normalized bispectral energy clearly distinguished the nonlinear signals, showing significantly higher values across all modes.

2. Real-World EEG Data (CHB-MIT Database):

   • The method was applied to scalp EEG recordings from pediatric epilepsy patients, comparing ictal (seizure) periods with interictal (non-seizure) periods.
   • Finding: Ictal activity exhibited substantially increased graph spectral power (consistent with known synchronization). Crucially, the graph bicoherence and normalized bispectral energy were also significantly elevated during seizures compared to interictal periods.
   • Implication: This indicates that seizure dynamics involve not just increased energy but also enhanced nonlinear coupling between graph modes, a feature invisible to standard power spectrum analysis.

Significance and Claims
The paper claims that the proposed approach provides an interpretable and computationally efficient tool for higher-order interaction analysis in graph signals. It demonstrates that higher-order graph spectral analysis yields information complementary to conventional methods. Specifically, the authors show that:

• Nonlinear dependencies can be detected even when second-order statistics are similar.
• In the context of EEG, seizure activity is characterized by enhanced higher-order coordination (nonlinear coupling) beyond simple power increases.
• The framework successfully generalizes bispectral analysis to non-Euclidean domains by replacing frequency addition with eigenvector-based harmonic interactions.

The authors conclude that this work lays the foundation for future applications, such as integrating graph bispectral features into Graph Neural Networks (GNNs) to capture higher-order nonlinear interactions, though this is presented as a direction for future work rather than a current result.