Abstract
How do vertices and edges collaboratively exert influence in graphs? We develop a framework for edge spectral clustering that reveals how both vertices and edges collaboratively accomplish directed influence in directed graphs. In contrast to the ubiquitous vertex clustering which groups vertices, edge clustering groups edges by assigning edges that share a functional affinity to the same cluster thus forming an influence subgraph cluster. With a complexity comparable to that of vertex clustering, this framework presents three different methods for edge spectral clustering that reveal important influence subgraphs in graph data, with each method providing different insight into directed influence processes in directed graphs. Central to the edge clustering methods are three new graph flow Laplacians that capture different directed flow processes and could potentially open new avenues in graph analysis and learning. Several synthetic and real-world examples demonstrate the potential for widespread application of edge spectral clustering in exploratory data analysis.