Accepted Papers

Higher-order Clustering in Complex Heterogeneous Networks

Aldo Carranza: Stanford University; Ryan Rossi: Adobe Research; Anup Rao: Yale University; Eunyee Koh: Adobe


Download

Heterogeneous networks are seemingly ubiquitous in the real world. Yet, most graph mining methods such as clustering have mostly focused on homogeneous graphs by ignoring semantic information in real-world systems. Moreover, most methods are based on first-order connectivity patterns (edges) despite that higher-order connectivity patterns are known to be important in understanding the structure and organization of such networks. In this work, we propose a framework for higher-order spectral clustering in heterogeneous networks through the notions of typed graphlets and typed-graphlet conductance. The proposed method builds clusters that preserve the connectivity of higher-order structures built up from typed graphlets. The approach generalizes previous work on higher-order spectral clustering. We theoretically prove a number of important results including a Cheeger-like inequality for typed-graphlet conductance that shows near-optimal bounds for the method. The theoretical results greatly simplify previous work while providing a unifying theoretical framework for analyzing higher-order spectral methods. Empirically, we demonstrate the effectiveness of the framework quantitatively for three important applications including clustering, compression, and link prediction.

How can we assist you?

We'll be updating the website as information becomes available. If you have a question that requires immediate attention, please feel free to contact us. Thank you!

Please enter the word you see in the image below: