Research on graph structure optimization based on Jordan form

Abstract

This thesis investigates the optimization of graph structures in graph signal processing, with a special focus on constructing graphs that satisfy the shift invariance condition. Graph signal processing has emerged as an effective tool for analyzing data defined on complex networks, but its effectiveness highly depends on the accuracy of the underlying graph structure. However, in many practical applications, the graph structure is often unknown or only partially known, and existing graph learning methods rarely consider the shift invariance condition for graph filters, which may lead to learned graph structures unsuitable for specific graph signal processing tasks. To address this issue, we propose a graph structure optimization framework based on the Jordan form. First, we establish the theoretical connection between the Jordan form and the shift invariance condition for graph filters, proving that adjacency matrices satisfying the shift invariance condition can be parameterized by eigenvalues and eigenvector matrices. Based on this theory, we design a graph structure optimization model that transforms complex algebraic constraints into an optimization problem in the parameter space. For efficient solution, we propose a parameter optimization method based on QR decomposition and an alternating optimization algorithm, and develop a distributed processing strategy for largescale graphs. We theoretically prove the convergence of the algorithm, analyze its computational complexity and error bounds, and validate its effectiveness on various synthetic datasets. Experimental results show that our method not only constructs graph structures satisfying the shift invariance condition but also outperforms existing methods in signal reconstruction, prediction, and classification tasks. Furthermore, we investigate the feasibility of non-convex optimization and the robustness of the algorithm, providing comprehensive theoretical and practical guidance for graph structure optimization. The innovation of this research lies in applying Jordan form theory to graph structure optimization for the first time, providing a new perspective and effective tools for constructing graph structures that satisfy specific algebraic conditions, which is significant for advancing graph signal processing theory and expanding its applications.