On Spectral Analysis of Directed Signed Graphs
It has been shown that the adjacency eigenspace of a network contains key information of its underlying structure. However, there has been no study on spectral analysis of the adjacency matrices of directed signed graphs. In this paper, we derive theoretical approximations of spectral projections from such directed signed networks using matrix perturbation theory. We use the derived theoretical results to study the influences of negative intra cluster and inter cluster directed edges on node spectral projections. We then develop a spectral clustering based graph partition algorithm, SC-DSG, and conduct evaluations on both synthetic and real datasets. Both theoretical analysis and empirical evaluation demonstrate the effectiveness of the proposed algorithm.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringSimilar Papers 제목 키워드 기반
Signed Graph Neural Networks: A Frequency Perspective
Graph convolutional networks (GCNs) and its variants are designed for unsigned graphs containing only positive links. Many existing GCNs have been derived from the spectral domain analysis of signals lying over (unsigned…
Link Sign PredictionNode ClassificationA Unified Spectral Sparsification Framework for Directed Graphs
Recent spectral graph sparsification research allows constructing nearly-linear-sized subgraphs that can well preserve the spectral (structural) properties of the original graph, such as the first few eigenvalues and eig…
A Graph Convolution for Signed Directed Graphs
A signed directed graph is a graph with sign and direction information on the edges. Even though signed directed graphs are more informative than unsigned or undirected graphs, they are more complicated to analyze and ha…
Link Sign PredictionMSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian
Signed and directed networks are ubiquitous in real-world applications. However, there has been relatively little work proposing spectral graph neural networks (GNNs) for such networks. Here we introduce a signed directe…
Graph Neural NetworkLink PredictionNode ClusteringStochastic Block Model+2Clustering Edges in Directed Graphs
How do vertices exert influence in graph data? We develop a framework for edge clustering, a new method for exploratory data analysis that reveals how both vertices and edges collaboratively accomplish directed influence…
Clustering