Latent Network Summarization: Bridging Network Embedding and Summarization

Di Jin, Ryan A. Rossi, Eunyee Koh, Sungchul Kim, Anup Rao, Danai KoutraKDD 2019 · DOI · OpenReview

TL;DR

This paper introduces "Latent Network Summarization" (LNS), a novel approach to represent large graphs in a compact, size-independent manner. MULTI-LENS, their proposed method, learns a summary that allows for efficient on-the-fly derivation of node embeddings, significantly reducing storage requirements compared to traditional graph embedding techniques.

What Problem Does This Paper Address?

Traditional graph embedding methods generate dense, K-dimensional vectors for each node in a graph. While effective for downstream tasks like link prediction and node classification, these embeddings become computationally and storage-prohibitive for massive graphs. For instance, a graph with a billion nodes could require terabytes of storage for its embeddings. Furthermore, these dense embeddings often consume more space than the original graph data. This paper addresses this challenge by proposing a new paradigm: latent network summarization, which aims to create a compact, graph-size independent representation that can still be used to derive node embeddings when needed.

Methods

The core of the proposed solution is the MULTI-LENS framework. It operates in several key stages:

  • Multi-level Structure Extraction: MULTI-LENS uses a set of "relational operators" and "relational functions" to capture structural information at multiple levels of a node's neighborhood (i.e., egonets and higher-order subgraphs). This is achieved by iteratively composing functions that aggregate information from neighbors.
  • Heterogeneous Context Derivation: To handle the inherent skewness in graph features and capture rich contextual patterns, MULTI-LENS transforms the extracted structural features into histogram-based representations. This process is generalized to handle various graph heterogeneities, including multiple node and edge types, and directionality.
  • Low-Rank Latent Summarization: Finally, MULTI-LENS employs low-rank approximation (specifically, Singular Value Decomposition - SVD) on the heterogeneous context matrices to derive a compact, size-independent summary. This summary consists of the learned relational functions and low-rank matrices.

A key aspect of MULTI-LENS is its inductive nature, meaning the learned summary can be applied to new, unseen graphs to derive their node embeddings. It also supports on-the-fly embedding derivation, where embeddings are computed only when needed, further saving resources.

Datasets

The authors evaluated MULTI-LENS on several real-world heterogeneous network datasets from the Network Repository:

  • Facebook: A homogeneous friendship network.
  • Yahoo! Messenger Logs: A heterogeneous network of communication patterns with location attributes.
  • DBpedia: A heterogeneous subgraph with entity and relation types.
  • Digg: A heterogeneous network of user voting behaviors.
  • Bibsonomy: A k-partite network representing user-tag-publication interactions.

Key Insights and Ideas

  • Bridging Summarization and Embedding: The paper successfully bridges the gap between traditional graph summarization (which often loses information for downstream tasks) and graph embedding (which is computationally expensive). MULTI-LENS offers the best of both worlds: a compact summary that can still generate useful node representations.
  • Size-Independent Representation is Key: The core innovation is the size-independent representation. This is crucial for scaling to massive graphs where traditional embedding methods fail due to memory and storage constraints.
  • Inductive Learning for Graphs: The framework's inductive capability is a significant advantage, allowing the learned summary to generalize to new graphs without retraining. This is particularly useful for dynamic or evolving networks.
  • Heterogeneity Handling: The method's ability to naturally handle diverse graph structures (node/edge types, directionality) without requiring explicit meta-schemas (like metapath2vec) is a strong practical benefit.

Key Results

  • Storage Efficiency: MULTI-LENS summaries require significantly less storage space, ranging from 80x to 2152x less than baseline embedding methods on large datasets. For smaller datasets, the savings are still substantial (3-12x).
  • Link Prediction Performance: MULTI-LENS achieved 3.5%-34.3% improvement in AUC for link prediction tasks compared to state-of-the-art embedding methods.
  • Scalability: The method scales linearly with the number of nodes and edges and is comparable to efficient baselines like node2vec, while using less memory. It can handle graphs with up to 10^7 nodes.
  • Inductive Anomaly Detection: The learned summaries demonstrated effectiveness in detecting anomalous subgraphs and events in real-world temporal graphs.

Limitations and Future Work

  • Relational Operators: While MULTI-LENS is general, the choice of relational operators can impact performance. The paper notes that sum and mean operators tend to have higher impact than max and min, and combinations involving distances can lead to worse performance.
  • Higher-Order Features: The paper suggests that while higher-level features can capture more information, they might also incorporate noisy or less relevant structural information, potentially leading to a slight drop in accuracy.
  • Future Work: The authors suggest exploring more sophisticated relational operators and functions, as well as investigating applications in other graph mining tasks. The inductive nature of the summaries also opens doors for transfer learning across different graph domains.

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
@inproceedings{jin2019latent,
  author = {Di Jin and Ryan A. Rossi and Eunyee Koh and Sungchul Kim and Anup Rao and Danai Koutra},
  title = {{Latent Network Summarization: Bridging Network Embedding and Summarization}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  doi = {10.1145/3292500.3330992},
}
Figure