Bridging Network Embedding and Graph Summarization

An important reason behind the prevalence of node representation learning is their superiority in downstream machine learning tasks on graphs. However, storing the vector-based node representation of massive real-world graphs often requires space that is orders of magnitude larger. To alleviate this issue, we introduce the problem of latent network summarization that is complementary to the problem of network embedding, and propose a general framework called Multi-LENS. Instead of deriving dense node-wise representations, the goal of latent network summarization is to summarize the structural properties of the graph in a latent space with dimensionality that is independent of the nodes or edges in the input graph. The size-independent graph summary given by Multi-LENS consists of (i) a set of relational aggregators with their compositions (relational functions) that captures structural features of multi-order node-centric subgraphs, and (ii) the low-rank approximations to matrices that incorporate captured structural features. In addition, Multi-LENS is able to derive node embeddings on the fly from this latent summary due to its inductive properties. Multi-LENS bridges advantages brought by both embeddings and graph summarization, and applies to graphs with or without directionality, weights, attributes or labels. Extensive experiments on both synthetic and real-world graphs show that Multi-LENS achieves 2 - 89% improvement in AUC for link prediction, while requiring less than 79x space compared to existing representation learning approaches. We also show the effectiveness of Multi-LENS summaries in anomaly and event detection on two real-world graphs.

• Publication year

  2018

• Venue

  arXiv.org

• Publication date

  2018-11-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1811.04461
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning Role-based Graph Embeddings

  2018cited by this paper
• AspEm: Embedding Learning by Aspects in Heterogeneous Information Networks

  2018influential reference
• Deep Inductive Network Representation Learning

  2018cited by this paper
• REGAL: Representation Learning-based Graph Alignment

  2018cited by this paper
• Summarizing Static and Dynamic Big Graphs

  2017cited by this paper
• metapath2vec: Scalable Representation Learning for Heterogeneous Networks

  2017influential reference
• Graph Embedding Techniques, Applications, and Performance: A Survey

  2017cited by this paper
• Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec

  2017influential reference
• struc2vec: Learning Node Representations from Structural Identity

  2017cited by this paper
• Exploratory Analysis of Graph Data by Leveraging Domain Knowledge

  2017cited by this paper
• Graph Summarization Methods and Applications

  2016cited by this paper
• Unsupervised Entity Resolution on Multi-type Graphs

  2016influential reference
• Mining Summaries for Knowledge Graph Search

  2016cited by this paper
• Scalable Pattern Matching over Compressed Graphs via Dedensification

  2016cited by this paper
• Large-Scale Embedding Learning in Heterogeneous Event Data

  2016cited by this paper
• Deep Neural Networks for Learning Graph Representations

  2016influential reference
• node2vec: Scalable Feature Learning for Networks

  2016influential reference
• TimeCrunch: Interpretable Dynamic Graph Summarization

  2015cited by this paper
• LINE: Large-scale Information Network Embedding

  2015influential reference
• GraRep: Learning Graph Representations with Global Structural Information

  2015cited by this paper
• A Spectral Framework for Anomalous Subgraph Detection

  2014cited by this paper
• DeepWalk: online learning of social representations

  2014cited by this paper
• Graph summarization with quality guarantees

  2014cited by this paper
• Neural Word Embedding as Implicit Matrix Factorization

  2014cited by this paper
• DELTACON: A Principled Massive-Graph Similarity Function

  2013cited by this paper
• Motif simplification: improving network visualization readability with fan, connector, and clique glyphs

  2013cited by this paper
• Leveraging social media networks for classification

  2011cited by this paper
• Mining Graph Patterns Efficiently via Randomized Summaries

  2009cited by this paper
• A scalable pattern mining approach to web graph compression with communities

  2008cited by this paper
• Graph summarization with bounded error

  2008cited by this paper
• Fast unfolding of communities in large networks

  2008cited by this paper
• Space efficient mining of multigraph streams

  2005cited by this paper
• Graphs over time: densification laws, shrinking diameters and possible explanations

  2005cited by this paper
• Representing Web graphs

  2003cited by this paper
• Fast Monte-Carlo algorithms for finding low-rank approximations

  1998cited by this paper
• Ieee Transactions on Knowledge and Data Engineering Slashburn: Graph Compression and Mining beyond Caveman Communities

  year unknowncited by this paper

• No citing papers are available for this paper.