2025/11/14 by J. Liu, Liu, Jitian, Nicolas Kozachuk +3
Computer Science · Engineering · #05C85 #05C90 #Advanced Graph Neural Networks #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Social and Information Networks (cs.SI) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2511.11517
openalex publication_date 2025/11/14 · openalex created_date 2025/11/18 · openalex updated_date 2026/07/31
We study distributed optimization of finite-degree polynomial Laplacian spectral objectives under fixed topology and a global weight budget, targeting the collective behavior of the entire spectrum rather than a few extremal eigenvalues. By re-formulating the global cost in a bilinear form, we derive local subgraph problems whose gradients approximately align with the global descent direction via an SVD-based test on the \(ZC\) matrix. This leads to an iterate-and-embed scheme over disjoint 1-hop neighborhoods that preserves feasibility by construction (positivity and budget) and scales to large geometric graphs. For objectives that depend on pairwise eigenvalue differences \(h(λi-λj)\), we obtain a quadratic upper bound in the degree vector, which motivates a ``warm-start'' by degree-regularization. The warm start uses randomized gossip to estimate global average degree, accelerating subsequent local descent while maintaining decentralization, and realizing ∼95% of the performance with respect to centralized optimization. We further introduce a learning-based proposer that predicts one-shot edge updates on maximal 1-hop embeddings, yielding immediate objective reductions. Together, these components form a practical, modular pipeline for spectrum-aware weight tuning that preserves constraints and applies across a broader class of whole-spectrum costs.