Near-Balanced Signed Graph Learning & Filtering for Depression Score Prediction

Recent studies have shown that strongly anti-correlated signals often induce nearly balanced signed graphs containing only a small number of inconsistent negative cycles (frustrations). However, existing methods do not learn such statistics as near-balanced signed graphs nor exploit this graph structure for signal filtering. We formulate an optimization that jointly learns a near-balanced signed graph and filters signals by alternating between balanced and frustrated graph components. Specifically, we construct a generalized expectation maximization (GEM) framework that alternates between graph learning (M-step) and signal estimation (E-step). The M-step learns a near-balanced graph by trading off data fidelity and graph frustration, while the E-step denoises a signal by minimizing a graph Laplacian regularizer, alternating between low-pass filtering on the balanced component and solving a linear system for the frustrated component. Unrolling the resulting iterations yields a lightweight and interpretable transformer-like neural network with direct correspondence to the underlying optimization steps. Applied to fMRI-based depression score prediction, the proposed framework matches state-of-the-art (SOTA) performance while reducing parameters to fewer than 5% of SOTA methods, outperforming both positive and perfectly balanced graph models.