Bridging Network Embedding and Graph Summarization

Di Jin, Ryan A. Rossi, Danai Koutra, Eunyee Koh, Sungchul Kim, Anup Rao

Introduction

In the rapidly evolving field of graph analytics, network embeddings—such as node2vec and DeepWalk—have become indispensable tools. They transform complex, high-dimensional graph structures into dense vector representations that can be easily ingested by standard machine learning models. However, these methods suffer from a significant "storage tax." Traditional embeddings typically produce an $N \times K$ matrix, where $N$ is the number of nodes and $K$ is the embedding dimension. For massive real-world graphs with billions of nodes, this representation can grow to terabytes, often becoming larger and more unwieldy than the original sparse graph itself.

Comparison of traditional graph embedding vs. latent summarization.

To overcome this scalability wall, we present Multi-LENS (Multi-level Latent Network Summarization). This framework introduces a paradigm shift: instead of storing individual vectors for every node, it summarizes the latent structure of the network. By storing structural "recipes" and a compact set of basis vectors, Multi-LENS creates a representation whose size is independent of the number of nodes, allowing for massive compression without sacrificing the ability to derive fine-grained node embeddings on demand.

Methodology: The Multi-LENS Framework

The core innovation of Multi-LENS lies in its ability to capture structural roles across multiple scales through a three-stage pipeline.

The Multi-LENS pipeline for multi-level structure extraction and summarization.

1. Relational Function Composition

Rather than identifying nodes by unique IDs, Multi-LENS characterizes them based on their structural properties. It utilizes a set of base relational operators—such as sum, mean, max, and variance—and applies them recursively to a node's neighborhood. For instance, a first-level feature might be the node's degree, while a second-level feature could be the "maximum degree among its neighbors." This recursive composition allows the model to capture the "role" a node plays in the network hierarchy, effectively extracting multi-level structural features.

2. Heterogeneous Context Derivation

Real-world networks are often heterogeneous, containing multiple types of nodes and edges. Multi-LENS handles this complexity by constructing logarithmic histograms of the extracted structural features. This binning process serves two purposes: it accommodates diverse node/edge types and it "smooths" the extreme power-law distributions (where a few nodes have disproportionately high connectivity) that are ubiquitous in social and biological networks.

3. Low-Rank Latent Summarization

The final stage applies a low-rank approximation, such as Singular Value Decomposition (SVD), to the feature distributions. Crucially, the system does not store the resulting node-level embeddings. Instead, it stores the relational functions (the "recipe") and the basis vectors of the latent feature subspace. Because these basis vectors represent structural archetypes rather than specific nodes, the summary remains compact even as the graph grows.

Experimental Evaluation

The researchers evaluated Multi-LENS across a diverse array of real-world networks, including Facebook (social), Yahoo! Messenger (heterogeneous), DBpedia (knowledge graph), and Twitter (temporal).

Storage Efficiency and Scalability

The most striking result is the degree of compression achieved. Multi-LENS required 80x to 2152x less storage space than baseline embedding methods on large-scale datasets. Furthermore, the algorithm's complexity is linear with respect to the number of edges, enabling it to scale effortlessly to graphs with 10 million nodes—a threshold where popular baselines like node2vec frequently encounter out-of-memory errors.

Accuracy and Inductive Capabilities

Despite the aggressive compression, Multi-LENS demonstrated superior performance in downstream tasks. In link prediction experiments, it outperformed state-of-the-art embeddings like Metapath2vec, yielding a 3.5% to 34.3% improvement in AUC.

A key advantage of this approach is that it is inductive by design. Because it learns structural patterns rather than node-specific values, a summary learned on one graph can be used to generate embeddings for a completely new graph or for new nodes appearing in a streaming data environment. This was demonstrated in temporal graph analysis, where Multi-LENS successfully flagged major real-world events, such as the Ebola outbreak, by detecting sudden shifts in the network's latent structural summary.

Conclusion

Multi-LENS successfully bridges the gap between the descriptive power of network embeddings and the efficiency of graph summarization. By focusing on the "how" of network structure rather than the "who," it provides a scalable, inductive, and highly compressed representation for modern graph analytics. Future research will explore automating the discovery of optimal relational operators and further reducing the computational overhead of on-the-fly embedding generation.

Summary updated

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.
BibTeX
@misc{jin2018bridging,
  author = {Di Jin and Ryan A. Rossi and Danai Koutra and Eunyee Koh and Sungchul Kim and Anup Rao},
  title = {{Bridging Network Embedding and Graph Summarization}},
  year = {2018},
  eprint = {1811.04461},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1811.04461},
}
Figure