Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming

arXiv:2506.01826v2 Announce Type: replace 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 computation 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. We derive a feasible CLIME parameter $\rho_i$ for each sign-constrained column problem. We solve the LP problem efficiently by tailoring a sparse LP method based on ADMM. We theoretically prove that the row / column updates produce a non-increasing objective sequence, and show that the iterations are terminated in a finite number of steps. 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 neural nets (GNN) constructed for positive graphs.

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 computation 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. We derive a feasible CLIME parameter $\rho_i$ for each sign-constrained column problem. We solve the LP problem efficiently by tailoring a sparse LP method based on ADMM. We theoretically prove that the row / column updates produce a non-increasing objective sequence, and show that the iterations are terminated in a finite number of steps. 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 neural nets (GNN) constructed for positive graphs.

Machine Learning (cs.LG); Signal Processing (eess.SP)

arXiv:2506.01826 [cs.LG]

(or arXiv:2506.01826v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2506.01826 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming

Subiecte conexe