Higher-order Spectral Clustering for Heterogeneous Graphs
Higher-order connectivity patterns such as small induced sub-graphs called graphlets (network motifs) are vital to understand the important components (modules/functional units) governing the configuration and behavior of complex networks. Existing work in higher-order clustering has focused on simple homogeneous graphs with a single node/edge type. However, heterogeneous graphs consisting of nodes and edges of different types are seemingly ubiquitous in the real-world. In this work, we introduce the notion of typed-graphlet that explicitly captures the rich (typed) connectivity patterns in heterogeneous networks. Using typed-graphlets as a basis, we develop a general principled framework for higher-order clustering in heterogeneous networks. The framework provides mathematical guarantees on the optimality of the higher-order clustering obtained. The experiments demonstrate the effectiveness of the framework quantitatively for three important applications including (i) clustering, (ii) link prediction, and (iii) graph compression. In particular, the approach achieves a mean improvement of 43x over all methods and graphs for clustering while achieving a 18.7% and 20.8% improvement for link prediction and graph compression, respectively.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringLink PredictionSimilar Papers 제목 키워드 기반
Higher-Order Spectral Clustering for Geometric Graphs
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral…
ClusteringHigher-Order Spectral Clustering under Superimposed Stochastic Block Model
Higher-order motif structures and multi-vertex interactions are becoming increasingly important in studies that aim to improve our understanding of functionalities and evolution patterns of networks. To elucidate the rol…
ClusteringCommunity DetectionStochastic Block ModelSubmodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs arise in clustering applications in which higher-or…
ClusteringHigher-Order Attribute-Enhancing Heterogeneous Graph Neural Networks
Graph neural networks (GNNs) have been widely used in deep learning on graphs. They can learn effective node representations that achieve superior performances in graph analysis tasks such as node classification and node…
AttributeClusteringGraph Neural NetworkNode Classification+2Constructing Robust Affinity Graphs for Spectral Clustering
Spectral clustering requires robust and meaningful affinity graphs as input in order to form clusters with desired structures that can well support human intuition. To construct such affinity graphs is non-trivial due to…
Clustering