The paper introduces an efficient method for learning balanced signed graph Laplacians directly from data. By extending the CLIME sparse inverse covariance estimation framework, it formulates a linear programming problem for each Laplacian column with sign constraints that enforce positive edges between nodes of the same polarity and negative edges otherwise. The authors develop a tailored ADMM-based sparse LP solver, prove convergence properties, and demonstrate through experiments that the learned balanced graphs outperform existing methods and allow the reuse of spectral filtering tools, wavelets, and graph neural networks designed for positive graphs.
By Haruki Yokota, Hiroshi Higashi, Yuichi Tanaka, Gene Cheung
The paper investigates how signed graph filters respond to structural changes such as edge additions, deletions, and sign flips. It shows that both the nature of the edge perturbation and the correlation among node features jointly influence the stability of learned representations. Leveraging this insight, the authors propose a perturbation strategy that targets structurally influential signed edges, and experiments demonstrate that this approach causes greater embedding drift, polarity change, and link‑prediction degradation than baseline methods.
By Ning Zhang, Li Zhang
arXiv:2607. 07513v1 Announce Type: new Abstract: Self-supervised learning matches supervised accuracy from a fraction of the labels, but the labeled-sample efficiency behind this has lacked a theoretical explanation.
By Adam M. Oberman
arXiv:2609.23668v1 Announce Type: cross
Abstract: Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constra...
By Christoffer Kjellson, Claudio Altafini, Emma Tegling
The paper investigates how to recover low‑dimensional latent geometry from a random geometric graph built from noisy, high‑dimensional data. It analyzes a spectral embedding algorithm on the Signal+Noise Graph Model, where vertices are perturbed points and edges are added when their inner product exceeds a threshold. In the regime where both the number of points and ambient dimension grow, the authors prove that, under a spectral gap condition, the leading eigenvectors and eigenvalues of the adjacency matrix can approximately recover the original point cloud up to an orthogonal transformation, and demonstrate the method on nested spheres and high‑dimensional sinusoid curves.
By Tatiana Brailovskaya, Nicholas A. Cook, Sofia Poinelli
arXiv:2606. 02223v1 Announce Type: new Abstract: Estimating the generative mechanism of large-scale networks is a fundamental challenge in statistical machine learning.
By Charles Dufour, Ulysse Naepels, Leonardo V. Santoro