A spectral graph convolution for signed directed graphs via magnetic Laplacian

• Published in: Neural networks 2023-07, Vol.164, p.562-574
• Main Authors: Ko, Taewook, Choi, Yoonhyuk, Kim, Chong-Kwon
• Format: Article
• Language: English
• Subjects: Algorithms; Graph convolution; Link existence prediction; Link sign prediction; Magnetic Laplacian; Magnetic Phenomena; Physical Phenomena; Signed directed graphs; Spectral convolution
• ISSN: 0893-6080; 1879-2782
• DOI: 10.1016/j.neunet.2023.05.009

Signed directed graphs contain both sign and direction information on their edges, providing richer information about real-world phenomena compared to unsigned or undirected graphs. However, analyzing such graphs is more challenging due to their complexity, and the limited availability of existing methods. Consequently, despite their potential uses, signed directed graphs have received less research attention. In this paper, we propose a novel spectral graph convolution model that effectively captures the underlying patterns in signed directed graphs. To this end, we introduce a complex Hermitian adjacency matrix that can represent both sign and direction of edges using complex numbers. We then define a magnetic Laplacian matrix based on the adjacency matrix, which we use to perform spectral convolution. We demonstrate that the magnetic Laplacian matrix is positive semi-definite (PSD), which guarantees its applicability to spectral methods. Compared to traditional Laplacians, the magnetic Laplacian captures additional edge information, which makes it a more informative tool for graph analysis. By leveraging the information of signed directed edges, our method generates embeddings that are more representative of the underlying graph structure. Furthermore, we showed that the proposed method has wide applicability for various graph types and is the most generalized Laplacian form. We evaluate the effectiveness of the proposed model through extensive experiments on several real-world datasets. The results demonstrate that our method outperforms state-of-the-art techniques in signed directed graph embedding. •This paper introduces a novel complex Hermitian adjacency matrix that encodes signed directed graphs using complex numbers.•It proposes a magnetic Laplacian matrix via the Hermitian and proves its positive semi-definite property.•With the magnetic Laplacian, this paper define a spectral graph convolution operation.•The proposed convolution enjoys wide applicability for several graph types from vanilla to signed directed.•SD-GCN shows superior performance in several datasets compare to other SOTAs.