Graph–based techniques and spectral graph theory in control and machine learning

Graphs are powerful data structure for representing objects and their relationships. They are extremely useful in the study of dynamical systems, evaluating how different agents interact among each other and behave. An example is represented by the consensus problem where a graph models a set of agents that locally interact and exchange their opinions with the aim of reaching a common opinion (consensus state). At the same time, many learning techniques rely on graphs exploiting their potentialities in modeling the relationships between data and determining additional features related to the data similarities. To study both the consensus problem and specific machine learning applications based on graphs, the study of the spectral properties of graphs reveals fundamental. In the consensus problem, the convergence rate to the consensus state strictly depends on the spectral properties of the transition probability matrix associated to the agents network. Whereas graphs and their spectral properties are fundamental in determining learning algorithms able to capture the structure of a dataset. We propose a theoretical and numerical study of the spectral properties of a network of agents that interact with the aim of increasing the rate of convergence to the consensus state keeping as sparse as possible the graph involved. Experimental results demonstrate the capability of the proposed approach in reaching the consensus state faster than a classical approach. We then investigate the potentialities of graphs when applied in classification problems. The results achieved highlight the importance of graphs and their spectral properties handling with both semi–supervised and supervised learning problems