Pith. sign in

REVIEW 6 major objections 3 minor 64 references

Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming

T0 review · 6 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A sparse linear program learns a balanced signed graph Laplacian directly from sample covariance, so positive-graph spectral tools transfer to signed data.

desk verdict The ADMM speed-up and HQIC-based rho selection are real, but the LP's diagonal sign constraint contradicts the paper's own PSD condition for the positive counterpart, so the filter-reuse claim is not guaranteed. read the letter →

arxiv 2506.01826 v1 pith:WMMEXCAU submitted 2025-06-02 cs.LG eess.SP

Haruki Yokota , Hiroshi Higashi , Yuichi Tanaka , Gene Cheung This is my paper
classification cs.LGeess.SP MSC 05C2290C0505C50
keywords balancedsignedgraphsgraphlearningLaplaciansparselinearprogramminginversecovarianceestimationCLIMEsignalprocessingADMM
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a method to learn a balanced signed graph Laplacian directly from observed data, without first estimating a signed graph and then balancing it in a separate step. Balanced signed graphs are exactly those whose nodes can be split into two polarities such that positive edges join same-polarity pairs and negative edges join opposite-polarity pairs, a characterization known as the Cartwright-Harary theorem. The paper exploits this to add linear sign constraints to the per-column sparse inverse covariance estimator CLIME, yielding a linear program for each Laplacian column. It solves each column with a tailored ADMM, achieves $O(N)$ per-column cost when the number of observations $K$ is much smaller than the number of nodes $N$, and proves local convergence. Because a balanced signed graph Laplacian is similar to a positive graph Laplacian via a diagonal polarity matrix $T$, the learned graph inherits a one-to-one eigenvector mapping, so spectral filters, wavelets, and graph convolutional networks designed for positive graphs can be reused on signed data; experiments support this on synthetic and four real-world datasets.

What carries the argument

The load-bearing object is the per-column sparse linear program $\min_{l_i} \|l_i\|_1$ with constraint set $\|C l_i - e_i\|_\infty \leq \rho_i$ and $S_i l_i \leq 0$. Here $S_i = \mathrm{diag}(\beta_i \beta_j)$ converts the balance condition -- the sign of edge $(i,j)$ equals $\beta_i \beta_j$ -- into a linear inequality, which keeps the problem an LP. The Cartwright-Harary theorem supplies the polarities: a signed graph is balanced if and only if such $\beta$ exists. Solving this LP per column is done with a tailored ADMM that rewrites the LP in standard form and, for $K \ll N$, replaces the covariance $C$ by the two sparse constraints $r = \frac{1}{K-1} X \phi - e_i$ and $\phi = X^\top l_i$, cutting the per-column cost from $O(N^2)$ to $O(N)$. The similarity transform $T = \mathrm{diag}(\beta)$ is what connects the learned $L_b$ to a positive graph Laplacian $L_+$, giving the spectral-transfer property that motivates the whole construction.

What would settle it

On a synthetic balanced signed graph with known polarities, compute the sample covariance from Gaussian Markov random field observations, then deliberately flip the estimated signs for a random fraction $p$ of the initial polarities before running the algorithm; if the relative error of the learned Laplacian grows steeply even for small $p$, the initialization is load-bearing. Conversely, generate data from an unbalanced signed graph containing an odd negative cycle and compare the method's relative error to unconstrained CLIME: if the balance-constrained estimate stays reasonable, the balance prior is more robust than claimed.

Watch

Extended reading notes

Core claim

The central claim is that a sparse, balanced signed graph Laplacian $L_b$ can be estimated directly from a sample covariance matrix $C$ by solving, for each column $l_i$, the linear program $\min_{l_i} \|l_i\|_1$ subject to $\|C l_i - e_i\|_\infty \leq \rho_i$ and $S_i l_i \leq 0$, where $S_i = \mathrm{diag}(\beta_i \beta_j)$ encodes the polarities $\beta \in \{1,-1\}^N$ guaranteed to exist by the Cartwright-Harary theorem. The sign constraints make every edge consistent with the polarities, so the learned matrix is the Laplacian of a balanced signed graph, and its spectrum equals that of the positive graph $L_+ = T L_b T$ formed by taking absolute edge weights, with $T = \mathrm{diag}(\beta)$. The paper argues this imposes balance directly during inverse covariance estimation rather than by post-hoc balancing, and that the tailored ADMM solver makes each column problem solvable in $O(N)$ time when $K \ll N$ by writing the data matrix $X$ rather than the dense covariance in the constraints. It also derives a per-column sparsity parameter $\rho_i$ from a combination of an information criterion and a minimum-feasibility lower bound, and proves that the alternating column updates converge to a local minimum. On synthetic and four real datasets, the learned balanced graphs give lower mean-squared error in denoising and interpolation than competing two-step approaches and the recent balanced-signature graph method, while enabling positive-graph filters and GNNs to be applied directly.

Load-bearing premise

The load-bearing premise is that the initial node polarities, read off a variance-weighted sample covariance matrix, are accurate for most nodes; if they are wrong for a substantial fraction of nodes, the linear sign constraints lock in incorrect edge signs and the learned graph cannot approximate the true inverse covariance.

Editorial extensions

If this is right

  • If the central claim is correct, a balanced signed graph can be learned directly from data with per-column cost $O(N)$ when $K \ll N$, making the approach scalable to graphs with many nodes and few observations.
  • The learned balanced Laplacian's eigenvectors map through the diagonal transform $T$ to eigenvectors of a positive graph Laplacian with the same eigenvalues, so spectral filters, wavelets, and GCNs built for positive graphs can process signed-graph signals after flipping signs with $T$.
  • Enforcing balance during estimation, rather than balancing a previously estimated signed graph, yields graphs closer to the true inverse covariance, as measured by F-measure, relative error, and adjacency error on synthetic data, and by lower MSE in denoising and interpolation on four real datasets.
  • The per-column sparsity parameter $\rho_i$ chosen by combining an information criterion with a minimum-feasibility lower bound improves graph quality over methods that use a single global parameter.
  • The alternating column-wise optimization converges monotonically in the $\ell_1$ objective to a local minimum, so repeated column updates cannot increase the overall graph sparsity cost.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A likely extension is to make the polarity initialization robust: the variance-of-covariance heuristic could be replaced or corrected by a small cut-based or SDP step triggered only when the LP objective stops improving, which would reduce sensitivity to heavy-tailed noise.
  • The similarity-transform argument implies that not only untrained GNNs but also GNNs trained on positive graphs should transfer to balanced signed data with a $T$-preprocessing; the paper demonstrates the untrained setting, leaving the trained-transfer claim as a testable consequence.
  • For datasets containing genuine unbalanced odd cycles (frustration), the balance constraint will bias the estimated inverse covariance; the method's advantage should shrink or reverse in such regimes, so a natural stress test is to measure relative error against unconstrained CLIME on data generated from an unbalanced signed graph.
  • The paper asserts the variance-of-covariance polarity initialization is accurate but offers no sensitivity analysis; a natural stress test is to flip a fraction of the initial polarities and measure recovery error, which would reveal how load-bearing that initialization is.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

6 major / 3 minor

Summary. The paper proposes a method to learn a balanced signed graph Laplacian directly from a sample covariance matrix. The method extends the CLIME linear-programming formulation by adding linear sign-consistency constraints derived from the Cartwright-Harary theorem, solves each column LP with an ADMM-based algorithm, and selects the CLIME parameter rho via a Hannan-Quinn information criterion combined with a minimum-feasibility rule. The authors claim that the learned balanced graph enables reuse of spectral filters, wavelets, and GCNs designed for positive graphs via a similarity transform, and they provide a local-convergence proof plus experiments on synthetic and real-world datasets.

Significance. If correct, the paper would provide an efficient and principled way to learn balanced signed graphs and would connect signed-graph data to the well-developed toolbox of positive graph spectral methods. The column-wise LP formulation and the use of the Cartwright-Harary theorem to encode balance are natural and potentially useful ideas, and the K << N reformulation based on the raw data matrix is a worthwhile direction. However, the current manuscript has several internal inconsistencies that directly affect the central claims: the diagonal sign constraint contradicts the paper's own PSD condition for the positive counterpart, the standard-form LP in Section V is not equivalent to the original constraint set as typeset, and the convergence proof does not establish monotonicity of the total objective. These issues must be resolved before the method and its reuse claim can be accepted.

major comments (6)
  1. [IV-C, Eq. (10); III-D] As written, the sign-consistency constraint S_i l_i <= 0_N in (10) applies to every entry of l_i, including the diagonal l_i,i, because S_i,ii = beta_i^2 = 1. Equation (9) explicitly restricts the constraint to j != i, so the diagonal should be excluded. This is not a cosmetic issue: a generalized Laplacian diagonal satisfies l_i,i = W_i,i + sum_{j != i} W_i,j, and the sufficient condition in Section III-D for L+ to be PSD is W_i,i >= 2 sum_{j != i} [-W_i,j]_+, which implies l_i,i >= sum_{j != i} |W_i,j| >= 0. The LP therefore forces l_i,i <= 0 and excludes the very graphs for which the reuse claim is made, while imposing no link between the diagonal and the magnitudes of negative edges. The optimization should constrain only off-diagonal entries and explicitly encode diag(W+) >= 0 (or an equivalent PSD guarantee) if the spectral-reuse claim is to be supported.
  2. [V-A, Eq. (19)] The aggregate equality constraint as typeset does not represent the inequalities in (10). Rows 2 and 3 read r = -rho 1_N and r = rho 1_N, which together are infeasible except when rho = 0, and the slack variable q does not appear in any of the inequality rows. Consequently, the standard-form LP (20) solved by the ADMM in Section V-B is not equivalent to (10) as printed. Please correct the matrix and the b vector so that the inequalities -r <= rho 1_N, r <= rho 1_N, \tilde{l} - l_i >= 0, \tilde{l} + l_i >= 0, and S_i l_i <= 0 are encoded through q >= 0, and verify that the implementation matches the corrected formulation.
  3. [IV-F] The convergence argument is incomplete. Updating the i-th row and column of L changes the L1 norm of every other column, so the inequality ||l*_i||_1 <= ||l'_i||_1 does not imply that ||L||_1 = sum_j ||l_j||_1 is non-increasing. For example, replacing L = [[10,0],[0,0]] by L' = [[0,6],[6,0]] decreases ||l_1||_1 from 10 to 6 but increases sum_j ||l_j||_1 from 10 to 12. The proof must either account for the symmetric update when computing the change in the total objective or establish monotonicity from the specific structure of the feasible set.
  4. [V-C, V-E] The claimed O(N) complexity for the K << N case does not follow from the stated argument. Even though A in (30) has O(N) nonzeros, the system matrix Psi = A^T A + diag(0,I) in (25) contains the N x N dense block X X^T, so an explicit Psi has Theta(N^2) nonzeros. The paper states that CG is O(nnz(Psi)) and that ADMM iterations are a constant independent of N, but neither the sparsity of Psi nor the constant iteration count is established. If CG is applied matrix-free using A and A^T, each iteration can be O(N), but this needs to be stated and the total iteration count still needs a bound for the complexity claims in Section V-E.
  5. [IV-E, Eq. (15)] The HQIC criterion in (15) contains the term log det(L), which is only defined when L is positive definite. The LP (10) does not constrain L to be PSD, and the diagonal constraint discussed above can push the learned Laplacian toward indefiniteness. The paper does not explain how log det(L) is computed for indefinite L or whether a projection or regularization is applied; without this, the rho-selection procedure used in all experiments is not well defined.
  6. [VI, Tables II-III, Figs. 3-4] The experimental claims of consistent improvement are reported as averages over 30 or 50 runs without error bars or statistical tests. Several reported differences are very small (e.g., Table III, USS GCN at noise 0.40: proposed 0.127 versus BsigGL 0.125), so the 'outperforms' statement is not supported by the current evidence. Please add standard deviations or confidence intervals, and state the number of runs used for each table and figure.
minor comments (3)
  1. [IV-A, IV-D] The paper states that initial polarities 'have proven sufficiently accurate, and thus few further updates are necessary,' but no experiment or analysis quantifies this. Since the sign constraints in (10) depend entirely on the polarities, a sensitivity study (e.g., random polarity initialization or reporting the number of polarity flips) would strengthen the robustness claim.
  2. [V-E] The abstract states O(N) per-column cost when K << N, while Section V-E states total O(N^2) complexity for that case; please clarify whether O(N) refers to per-ADMM-iteration, per-column, or per-optimization cost.
  3. [VI-A, Table II] The column headers for noise variance and noise level are duplicated and misaligned in the table, making it difficult to map results to the two experimental settings; please reformat the table.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular dependency found: the balanced graph LP, the similarity-transform argument, and the model-selection procedure are self-contained, with self-citations used only as background and not as load-bearing premises.

full rationale

The paper's derivation chain is not circular. The core optimization in (10) extends CLIME by adding the linear sign-consistency constraints S_i l_i <= 0 derived from CHT in (9). The objective ||l_i||_1 and the feasibility constraints ||C l_i - e_i||_inf <= rho_i are standard sparse inverse-covariance estimation, and no target quantity is used to define the inputs. The similarity-transform claim in Section III-C is proved in the paper itself via (5), TL_bT^{-1} = D - |W| + diag(W) = L_+, which is an algebraic consequence of the definitions of L_b and L_+; the citation to [22] is therefore background, not load-bearing. The initial polarity assignment in Section IV-D is a heuristic initialization from the covariance sign pattern, not a fitted parameter that is later renamed as a prediction; the subsequent LP still must approximate the inverse covariance, and a poor initialization would degrade accuracy rather than guarantee the answer. The CLIME parameter rho_i is selected by HQIC and a minimum-feasibility criterion (Section IV-E), which is standard model selection on the training data, and real-world restoration uses held-out test signals (10% of samples). The reviewer's PSD concern -- that (10) does not enforce diag(W^+) >= 0 from Section III-D -- is a genuine correctness or robustness gap in the reuse claim, but it is not a circularity: the learned graph is not defined so as to make the reuse claim true by construction. The paper also explicitly acknowledges the risk of statistical mismatch when enforcing balance (Section IV-C2). Overall, no equation or fitted parameter reduces to the claimed output by construction.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central method introduces no new physical or conceptual entities. It relies on standard balance theory, a known similarity transform, and the assumption that the sample covariance encodes a balanced Laplacian precision matrix. The tunable parameters are limited to the CLIME sparsity rho, the ADMM penalty gamma, the VoC kernel scale sigma_v, and the search increment delta.

free parameters (4)
  • sigma_v = not specified
    Kernel scale in Eq. (13) that weights the sample covariance entries by the reliability of their variance estimates; affects initial polarities and all downstream results.
  • rho_i = per column via HQIC and feasibility LPs
    CLIME sparsity parameter for each column LP in (10); selected by a grid search over HQIC increments, so it is tuned to the data.
  • gamma = not specified
    ADMM penalty parameter in (23); its value affects convergence speed and solution accuracy, but no default is given.
  • delta = not specified
    Increment used to step rho in the HQIC search (Section IV-E1); no value or stopping tolerance is reported.
assumptions (4)
  • standard math Cartwright-Harary Theorem: a signed graph is balanced if and only if nodes can be assigned polarities so that positive/negative edges connect same/opposite polarities.
    Invoked in Section III-B as Theorem 1 to justify the sign constraints in (9).
  • domain assumption The balanced signed graph Laplacian L_b is similar to a positive graph Laplacian L_+ via diagonal matrix T.
    Stated in Eq. (5) and attributed to [22]; this is the basis for reusing positive graph spectral filters.
  • domain assumption The observed data are generated so that the sample covariance C approximates a balanced signed graph Laplacian precision matrix.
    The objective in (10) seeks L that approximately inverts C; if the true precision is not a balanced Laplacian, the enforced balance causes statistical mismatch, acknowledged in Section IV-C2.
  • ad hoc to paper The sequence of rho selections keeps previous solutions feasible, enabling the monotonic convergence argument.
    Section IV-F relies on LP (17) to guarantee that the previous column solution remains feasible; this requires solving an extra LP at each iteration.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming." pith.science (2026). https://pith.science/paper/WMMEXCAU

@misc{pith2026250601826,
  author       = {Pith},
  title        = {Pith review of: Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WMMEXCAU}},
  note         = {Machine review of arXiv:2506.01826}
}
abstract

Signed graphs are equipped with both positive and negative edge weights, encoding pairwise correlations as well as anti-correlations in data. A balanced signed graph is a signed graph with no cycles containing an odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map via a simple linear transform to ones in a corresponding positive graph Laplacian, thus enabling reuse of spectral filtering tools designed for positive graphs. We propose an efficient method to learn a balanced signed graph Laplacian directly from data. Specifically, extending a previous linear programming (LP) based sparse inverse covariance estimation method called CLIME, we formulate a new LP problem for each Laplacian column $i$, where the linear constraints restrict weight signs of edges stemming from node $i$, so that nodes of same / different polarities are connected by positive / negative edges. Towards optimal model selection, we derive a suitable CLIME parameter $\rho$ based on a combination of the Hannan-Quinn information criterion and a minimum feasibility criterion. We solve the LP problem efficiently by tailoring a sparse LP method based on ADMM. We theoretically prove local solution convergence of our proposed iterative algorithm. Extensive experimental results on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables reuse of spectral filters, wavelets, and graph convolutional nets (GCN) constructed for positive graphs.

Figures

Figures reproduced from arXiv: 2506.01826 by the authors.

Figure 1
Figure 1. Balanced signed graph (Left) and its positive graph counterpart (Right). [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Overview of proposed balanced graph learning approach. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Results of signal denoising using estimated graph Laplacians. Figures in the top row are the results of graph low-pass filtering (BL), and figures in the [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Results of signal interpolation using estimated graph Laplacians. The mean squared errors (MSE) are averaged over 50 independent runs. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: First 30% eigenvalues of estimated graph Laplacians (rescaled to [0, 1]). The horizontal axis represents the index of eigenvalues. VII. CONCLUSION We propose an efficient algorithm to learn a balanced signed graph directly from data. We augment a previous linear progra…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

64 extracted references · 59 canonical work pages

  1. [1]

    The emerging field of signal processing on graphs: Extending high- dimensional data analysis to networks and other irregular domains,

    D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high- dimensional data analysis to networks and other irregular domains,” IEEE Signal Process. Mag. , vol. 30, no. 3, pp. 83–98, 2013

    work page 2013

  2. [2]

    Graph Signal Processing: Overview, Challenges, and Applications,

    A. Ortega, P. Frossard, J. Kovaˇcevi´c, J. M. F. Moura, and P. Vandergheynst, “Graph Signal Processing: Overview, Challenges, and Applications,” Proc. IEEE, vol. 106, no. 5, pp. 808–828, 2018

    work page 2018

  3. [3]

    Sampling Signals on Graphs: From Theory to Applications,

    Y . Tanaka, Y . C. Eldar, A. Ortega, and G. Cheung, “Sampling Signals on Graphs: From Theory to Applications,” IEEE Signal Process. Mag. , vol. 37, no. 6, pp. 14–30, 2020. IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. X, NO. X, MAY 2025 12

    work page 2020

  4. [4]

    Semi-supervised classification with graph convolutional networks,

    T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proceedings of the 5th International Conference on Learning Representations (ICLR) , 2017

    work page 2017

  5. [5]

    Sparse inverse covariance estimation with the graphical lasso,

    J. Friedman, T. Hastie, and R. Tibshirani, “Sparse inverse covariance estimation with the graphical lasso,” Biostatistics, vol. 9, no. 3, pp. 432–441, 2008

    work page 2008

  6. [6]

    How to Learn a Graph from Smooth Signals,

    V . Kalofolias, “How to Learn a Graph from Smooth Signals,” in Proc. 19th Int. Conf. Artif. Intell. Stat. PMLR, 2016, pp. 920–929

    work page 2016

  7. [7]

    Learning heat diffusion graphs,

    D. Thanou, X. Dong, D. Kressner, and P. Frossard, “Learning heat diffusion graphs,” IEEE Trans. Signal Inf. Process. Netw. , vol. 3, pp. 484–499, 2016

    work page 2016

  8. [8]

    Graph Signal Denoising via Trilateral Filter on Graph Spectral Domain,

    M. Onuki, S. Ono, M. Yamagishi, and Y . Tanaka, “Graph Signal Denoising via Trilateral Filter on Graph Spectral Domain,” IEEE Trans. Signal Inf. Process. Netw. , vol. 2, no. 2, pp. 137–148, 2016

    work page 2016

Show all 64 references
  1. [9]

    Graph Laplacian regularization for inverse imaging: Analysis in the continuous domain,

    J. Pang and G. Cheung, “Graph Laplacian regularization for inverse imaging: Analysis in the continuous domain,” in IEEE Trans. Image Process., vol. 26, no.4, April 2017, pp. 1770–1785

    2017

  2. [10]

    Localized spectral graph filter frames: A unifying framework, survey of design considerations, and numerical comparison,

    D. I. Shuman, “Localized spectral graph filter frames: A unifying framework, survey of design considerations, and numerical comparison,” IEEE Signal Processing Magazine , vol. 37, no. 6, pp. 43–63, 2020

    2020

  3. [11]

    Wavelets on graphs via spectral graph theory,

    D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” Applied and Computational Harmonic Analysis, vol. 30, no. 2, pp. 129–150, 2011

    2011

  4. [12]

    Bilateral filter: Graph spectral interpretation and extensions,

    A. Gadde, S. K. Narang, and A. Ortega, “Bilateral filter: Graph spectral interpretation and extensions,” in 2013 IEEE International Conference on Image Processing , 2013, pp. 1222–1226

    2013

  5. [13]

    Signal recovery on graphs: Variation minimization,

    S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kova ˇcevi´c, “Signal recovery on graphs: Variation minimization,” IEEE Transactions on Signal Processing, vol. 63, no. 17, pp. 4609–4624, 2015

    2015

  6. [14]

    Graph-based joint dequantization and contrast enhancement of poorly lit jpeg images,

    X. Liu, G. Cheung, X. Ji, D. Zhao, and W. Gao, “Graph-based joint dequantization and contrast enhancement of poorly lit jpeg images,” IEEE Transactions on Image Processing , vol. 28, no. 3, pp. 1205–1219, 2019

    2019

  7. [15]

    Interpolation and denoising of graph signals using plug-and-play admm,

    Y . Yazaki, Y . Tanaka, and S. H. Chan, “Interpolation and denoising of graph signals using plug-and-play admm,” in ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019, pp. 5431–5435

    2019

  8. [16]

    Graph signal restoration using nested deep algorithm unrolling,

    M. Nagahama, K. Yamada, Y . Tanaka, S. H. Chan, and Y . C. Eldar, “Graph signal restoration using nested deep algorithm unrolling,” IEEE Transactions on Signal Processing , vol. 70, pp. 3296–3311, 2022

    2022

  9. [17]

    On the Laplacian Eigenvalues of Signed Graphs,

    Y . Hou, J. Li, and Y . Pan, “On the Laplacian Eigenvalues of Signed Graphs,” Linear Multilinear Algebra , vol. 51, no. 1, pp. 21–30, 2003

    2003

  10. [18]

    Spectral Analysis of k- Balanced Signed Graphs,

    L. Wu, X. Ying, X. Wu, A. Lu, and Z.-H. Zhou, “Spectral Analysis of k- Balanced Signed Graphs,” in Adv. Knowl. Discov. Data Min., ser. Lecture Notes in Computer Science, J. Z. Huang, L. Cao, and J. Srivastava, Eds. Berlin, Heidelberg: Springer, 2011, pp. 1–12

    2011

  11. [19]

    Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization,

    J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E. W. De Luca, and S. Albayrak, “Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization,” in Proceedings of the 2010 SIAM Interna- tional Conference on Data Mining (SDM) , ser. Proceedings. Society for ...

    2010

  12. [20]

    Signal Processing on Signed Graphs: Funda- mentals and Potentials,

    T. Dittrich and G. Matz, “Signal Processing on Signed Graphs: Funda- mentals and Potentials,” IEEE Signal Process. Mag. , vol. 37, no. 6, pp. 86–98, 2020

    2020

  13. [21]

    Discrete nodal domain theorems,

    E. B. Davies, J. Leydold, and P. F. Stadler, “Discrete nodal domain theorems,” Elsevier Linear Algebra and its Application , 2000

    2000

  14. [22]

    Efficient signed graph sampling via balancing & gershgorin disc perfect alignment,

    C. Dinesh, G. Cheung, S. Bagheri, and I. V . Baji ´c, “Efficient signed graph sampling via balancing & gershgorin disc perfect alignment,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 47, no. 4, pp. 2330–2348, 2025

    2025

  15. [23]

    Efficient learning of balanced signature graphs,

    G. Matz, C. Verardo, and T. Dittrich, “Efficient learning of balanced signature graphs,” in ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2023, pp. 1–5

    2023

  16. [24]

    The graphical lasso: New insights and alternatives,

    R. Mazumder and T. Hastie, “The graphical lasso: New insights and alternatives,” Electron J Stat , vol. 6, pp. 2125–2149, 2012

    2012

  17. [25]

    Balancing signed graphs,

    J. Akiyama, D. Avis, V . Chv´atal, and H. Era, “Balancing signed graphs,” Discrete Applied Mathematics , vol. 3, no. 4, pp. 227–233, 1981

    1981

  18. [26]

    Linear-Time Sampling on Signed Graphs Via Gershgorin Disc Perfect Alignment,

    C. Dinesh, S. Bagheri, G. Cheung, and I. V . Baji´c, “Linear-Time Sampling on Signed Graphs Via Gershgorin Disc Perfect Alignment,” in ICASSP 2022 - 2022 IEEE Int. Conf. Acoust. Speech Signal Process. ICASSP , 2022, pp. 5942–5946

    2022

  19. [27]

    Signed graph balancing with graph cut,

    H. Yokota, J. Hara, Y . Tanaka, and G. Cheung, “Signed graph balancing with graph cut,” in 2023 31st European Signal Processing Conference (EUSIPCO), 2023, pp. 1853–1857

    2023

  20. [28]

    A constrained ℓ1 minimization approach to sparse precision matrix estimation,

    T. Cai, W. Liu, and X. Luo, “A constrained ℓ1 minimization approach to sparse precision matrix estimation,” Journal of the American Statistical Association, vol. 106, no. 494, pp. 594–607, 2011

    2011

  21. [29]

    On the notion of balance of a signed graph

    F. Harary, “On the notion of balance of a signed graph.” Mich. Math. J. , vol. 2, no. 2, pp. 143–146, 1953

    1953

  22. [30]

    A new alternating direction method for linear programming,

    S. Wang and N. Shroff, “A new alternating direction method for linear programming,” in Advances in Neural Information Processing Systems, I. Guyon, U. V . Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017. ...

    2017

  23. [31]

    The determination of the order of an autoregression,

    E. J. Hannan and B. G. Quinn, “The determination of the order of an autoregression,” Journal of the Royal Statistical Society. Series B (Methodological), vol. 41, no. 2, pp. 190–195, 1979

    1979

  24. [32]

    Variational Splines and Paley–Wiener Spaces on Combina- torial Graphs,

    I. Pesenson, “Variational Splines and Paley–Wiener Spaces on Combina- torial Graphs,” Constr Approx, vol. 29, no. 1, pp. 1–21, 2009

    2009

  25. [33]

    Graph attention networks,

    P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y . Bengio et al., “Graph attention networks,” in Proceedings of the 6th International Conference on Learning Representations (ICLR) , 2018

    2018

  26. [34]

    Graph Learning From Data Under Laplacian and Structural Constraints,

    H. E. Egilmez, E. Pavez, and A. Ortega, “Graph Learning From Data Under Laplacian and Structural Constraints,” IEEE J. Sel. Top. Signal Process., vol. 11, no. 6, pp. 825–841, 2017

    2017

  27. [35]

    Kumar, J

    S. Kumar, J. Ying, J. V . d. M. Cardoso, and D. P. Palomar, Structured graph learning via laplacian spectral constraints . Red Hook, NY , USA: Curran Associates Inc., 2019

    2019

  28. [36]

    Spectral graph learning with core eigenvectors prior via iterative GLASSO and projection,

    S. Bagheri, T. T. Do, G. Cheung, and A. Ortega, “Spectral graph learning with core eigenvectors prior via iterative GLASSO and projection,” IEEE Transactions on Signal Processing , vol. 72, pp. 3958–3972, 2024

    2024

  29. [37]

    Learning lapla- cian matrix in smooth graph signal representations,

    X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning lapla- cian matrix in smooth graph signal representations,” IEEE Transactions on Signal Processing , vol. 64, no. 23, pp. 6160–6173, 2016

    2016

  30. [38]

    Learning graphs from data: A signal representation perspective,

    X. Dong, D. Thanou, M. Rabbat, and P. Frossard, “Learning graphs from data: A signal representation perspective,” IEEE Signal Process. Mag. , vol. 36, no. 3, pp. 44–63, 2019

    2019

  31. [39]

    Joint signal interpolation / time-varying graph estimation via smoothness and low-rank priors,

    S. Bagheri, G. Cheung, T. Eadie, and A. Ortega, “Joint signal interpolation / time-varying graph estimation via smoothness and low-rank priors,” in ICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2024, pp. 9646–9650

    2024

  32. [40]

    Feature graph learning for 3d point cloud denoising,

    W. Hu, X. Gao, G. Cheung, and Z. Guo, “Feature graph learning for 3d point cloud denoising,” IEEE Transactions on Signal Processing , vol. 68, pp. 2841–2856, 2020

    2020

  33. [41]

    Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment,

    C. Yang, G. Cheung, and W. Hu, “Signed Graph Metric Learning via Gershgorin Disc Perfect Alignment,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 10, pp. 7219–7234, 2022

    2022

  34. [42]

    Interpretable lightweight transformer via unrolling of learned graph smoothness priors,

    V . H. T. T. DO, P. Eftekhar, S. A. Hosseini, G. Cheung, and P. Chou, “Interpretable lightweight transformer via unrolling of learned graph smoothness priors,” in Advances in Neural Information Processing Systems , A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. To...

    2024

  35. [43]

    Bilateral filtering for gray and color images,

    C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” in Sixth International Conference on Computer Vision , 1998, pp. 839–846

    1998

  36. [44]

    Spectral analysis of signed graphs for clustering, prediction and visualization,

    J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E. W. D. Luca, and S. Albayrak, “Spectral analysis of signed graphs for clustering, prediction and visualization,” in Proceedings of the 2010 SIAM International Conference on Data Mining (SDM) , 2010, pp. 559–570. [Online]. Ava...

    2010 doi

  37. [45]

    Efficient learning of balanced signed graphs via iterative linear programming,

    H. Yokota, H. Higashi, Y . Tanaka, and G. Cheung, “Efficient learning of balanced signed graphs via iterative linear programming,” in ICASSP 2025 - 2025 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2025, pp. 1–5

    2025

  38. [46]

    A faster algorithm for solving general LPs,

    S. Jiang, Z. Song, O. Weinstein, and H. Zhang, “A faster algorithm for solving general LPs,” in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , ser. STOC 2021. Association for Computing Machinery, Jun. 2021, pp. 823–832

    2021

  39. [47]

    Graph Fourier transform with negative edges for depth image coding,

    W.-T. Su, G. Cheung, and C.-W. Lin, “Graph Fourier transform with negative edges for depth image coding,” in 2017 IEEE International Conference on Image Processing (ICIP) , 2017, pp. 1682–1686

    2017

  40. [48]

    R. S. Varga, Gershgorin and his circles . Springer, 2004

    2004

  41. [49]

    Graph spectral image processing,

    G. Cheung, E. Magli, Y . Tanaka, and M. K. Ng, “Graph spectral image processing,” in Proceedings of the IEEE , vol. 106, no.5, May 2018, pp. 907–930

    2018

  42. [50]

    Complex graph Lapla- cian regularizer for inferencing grid states,

    C. Dinesh, J. Wang, G. Cheung, and P. Srikantha, “Complex graph Lapla- cian regularizer for inferencing grid states,” in 2023 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm) , 2023. IEEE TRANSACTIONS ON SIGNA...

    2023

  43. [51]

    Semidefinite relaxation of quadratic optimization problems,

    Z.-q. Luo, W.-k. Ma, A. M.-c. So, Y . Ye, and S. Zhang, “Semidefinite relaxation of quadratic optimization problems,” IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 20–34, 2010

    2010

  44. [52]

    Dynamics of social balance on networks,

    T. Antal, P. L. Krapivsky, and S. Redner, “Dynamics of social balance on networks,” Phys. Rev. E, vol. 72, no. 3, p. 036121, Sep. 2005

    2005

  45. [53]

    Bipartite consensus for multi-agent systems on directed signed networks,

    J. Hu and W. X. Zheng, “Bipartite consensus for multi-agent systems on directed signed networks,” in 52nd IEEE Conference on Decision and Control, Dec. 2013, pp. 3451–3456

    2013

  46. [54]

    The Structural Balance Theory of Sentiment Networks: Elaboration and Test,

    C. M. Rawlings and N. E. Friedkin, “The Structural Balance Theory of Sentiment Networks: Elaboration and Test,” American Journal of Sociology, vol. 123, no. 2, pp. 510–548, Sep. 2017

    2017

  47. [55]

    Testing structural balance theories in heterogeneous signed networks,

    A. Gallo, D. Garlaschelli, R. Lambiotte, F. Saracco, and T. Squartini, “Testing structural balance theories in heterogeneous signed networks,” Commun Phys, vol. 7, no. 1, pp. 1–13, May 2024

    2024

  48. [56]

    F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel, Robust Statistics. Wiley, 2005

    2005

  49. [57]

    Information Theory and an Extension of the Maximum Likelihood Principle,

    H. Akaike, “Information Theory and an Extension of the Maximum Likelihood Principle,” in Selected Papers of Hirotugu Akaike , E. Parzen, K. Tanabe, and G. Kitagawa, Eds. New York, NY: Springer, 1998, pp. 199–213

    1998

  50. [58]

    Estimating the dimension of a model,

    G. Schwarz, “Estimating the dimension of a model,” The Annals of Statistics, vol. 6, no. 2, pp. 461–464, 1978

    1978

  51. [59]

    Graph learning information criterion,

    K. Yamada and Y . Tanaka, “Graph learning information criterion,” in ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , 2022, pp. 5642–5646

    2022

  52. [60]

    S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers . Now Foundations and Trends, 2011

    2011

  53. [61]

    An introduction to the conjugate gradient method without the agonizing pain,

    J. R. Shewchuk, “An introduction to the conjugate gradient method without the agonizing pain,” Carnegie Mellon University, USA, Tech. Rep., 1994

    1994

  54. [62]

    On random graphs i,

    P. Erd¨os and A. R ´enyi, “On random graphs i,” Publicationes Mathemati- cae Debrecen, vol. 6, pp. 290–297, 1959

    1959

  55. [63]

    Untrained Graph Neural Networks for Denoising,

    S. Rey, S. Segarra, R. Heckel, and A. G. Marques, “Untrained Graph Neural Networks for Denoising,”IEEE Transactions on Signal Processing, vol. 70, pp. 5708–5723, 2022

    2022

  56. [64]

    Biggs, Algebraic graph theory

    N. Biggs, Algebraic graph theory . Cambridge university press, 1993, no. 67. APPENDIX A. Derivation of Linear System We derive linear system (25) from optimization (24). For convenience, we first define y = [x; q] ∈ R8N . Thus, B   x q ˜q   − b 05N = A 0 6N,5N 05N,3N I5N −...

    1993

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.