Latent Network Summarization: Bridging Network Embedding and Summarization
arXiv:1811.04461
Abstract
Motivated by the computational and storage challenges that dense embeddings pose, we introduce the problem of latent network summarization that aims to learn a compact, latent representation of the graph structure with dimensionality that is independent of the input graph size (i.e., #nodes and #edges), while retaining the ability to derive node representations on the fly. We propose Multi-LENS, an inductive multi-level latent network summarization approach that leverages a set of relational operators and relational functions (compositions of operators) to capture the structure of egonets and higher-order subgraphs, respectively. The structure is stored in low-rank, size-independent structural feature matrices, which along with the relational functions comprise our latent network summary. Multi-LENS is general and naturally supports both homogeneous and heterogeneous graphs with or without directionality, weights, attributes or labels. Extensive experiments on real graphs show 3.5 - 34.3% improvement in AUC for link prediction, while requiring 80 - 2152x less output storage space than baseline embedding methods on large datasets. As application areas, we show the effectiveness of Multi-LENS in detecting anomalies and events in the Enron email communication graph and Twitter co-mention graph.
References in corpus (7)
- Fast unfolding of communities in large networks
- Graph Embedding Techniques, Applications, and Performance: A Survey
- struc2vec: Learning Node Representations from Structural Identity
- Scale-Free Networks are Ultrasmall
- Role Discovery in Networks
- Learning Role-based Graph Embeddings
- A Spectral Framework for Anomalous Subgraph Detection