Tensor Spectral Clustering for Partitioning Higher-order Network Structures

Abstract

Spectral graph theory-based methods represent an important class of tools for studying the structure of networks. Spectral methods are based on a first-order Markov chain derived from a random walk on the graph and thus they cannot take advantage of important higher-order network substructures such as triangles, cycles, and feed-forward loops. Here we propose a Tensor Spectral Clustering (TSC) algorithm that allows for modeling higher-order network structures in a graph partitioning framework. Our TSC algorithm allows the user to specify which higher-order network structures (cycles, feed-forward loops, etc.) should be preserved by the network clustering. Higher-order network structures of interest are represented using a tensor, which we then partition by developing a multilinear spectral method. Our framework can be applied to discovering layered flows in networks as well as graph anomaly detection, which we illustrate on synthetic networks. In directed networks, a higher-order structure of particular interest is the directed 3-cycle, which captures feedback loops in networks. We demonstrate that our TSC algorithm produces large partitions that cut fewer directed 3-cycles than standard spectral clustering algorithms.

SDM 2015

References in corpus (4)

• Community structure in directed networks
• Clique percolation in random networks
• Using Triangles to Improve Community Detection in Directed Networks
• Degree Relations of Triangles in Real-world Networks and Models

Cited by in corpus (25)

• Higher-order organization of complex networks
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
• Motifs in Temporal Networks
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• What are higher-order networks?
• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Representing higher-order dependencies in networks
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks
• Magnetic eigenmaps for community detection in directed networks
• Design and Analysis of the NIPS 2016 Review Process
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• HONEM: Learning Embedding for Higher Order Networks
• A framework for second order eigenvector centralities and clustering coefficients
• Higher-Order Networks Representation and Learning: A Survey
• General Tensor Spectral Co-clustering for Higher-Order Data
• Spectral Sparsification of Simplicial Complexes for Clustering and Label Propagation
• The Atlas for the Aspiring Network Scientist
• Detecting highly cyclic structure with complex eigenpairs
• Higher-Order Spectral Clustering of Directed Graphs
• PASTA: A Parallel Sparse Tensor Algorithm Benchmark Suite
• Spectral Clustering with Smooth Tiny Clusters
• Mixed-Order Spectral Clustering for Networks
• DynACPD Embedding Algorithm for Prediction Tasks in Dynamic Networks
• User-Guided Clustering in Heterogeneous Information Networks via Motif-Based Comprehensive Transcription