HARP: Hierarchical Representation Learning for Networks

Abstract

We present HARP, a novel method for learning low dimensional embeddings of a graph's nodes which preserves higher-order structural features. Our proposed method achieves this by compressing the input graph prior to embedding it, effectively avoiding troublesome embedding configurations (i.e. local minima) which can pose problems to non-convex optimization. HARP works by finding a smaller graph which approximates the global structure of its input. This simplified graph is used to learn a set of initial representations, which serve as good initializations for learning representations in the original, detailed graph. We inductively extend this idea, by decomposing a graph in a series of levels, and then embed the hierarchy of graphs from the coarsest one to the original graph. HARP is a general meta-strategy to improve all of the state-of-the-art neural algorithms for embedding graphs, including DeepWalk, LINE, and Node2vec. Indeed, we demonstrate that applying HARP's hierarchical paradigm yields improved implementations for all three of these methods, as evaluated on both classification tasks on real-world graphs such as DBLP, BlogCatalog, CiteSeer, and Arxiv, where we achieve a performance gain over the original implementations by up to 14% Macro F1.

To appear in AAAI 2018

Cited by in corpus (39)

• Learning Graph Embedding with Adversarial Training Methods
• An Overview of Deep Semi-Supervised Learning
• Is a Single Embedding Enough? Learning Node Representations that Capture Multiple Social Contexts
• Machine Learning on Graphs: A Model and Comprehensive Taxonomy
• Semi-Implicit Graph Variational Auto-Encoders
• DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
• Graph Clustering with Graph Neural Networks
• Graph InfoClust: Leveraging cluster-level node information for unsupervised graph representation learning
• MILE: A Multi-Level Framework for Scalable Graph Embedding
• GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding
• Learning event representations for temporal segmentation of image sequences by dynamic graph embedding
• Fairness-Aware Node Representation Learning
• Learning Topological Representation for Networks via Hierarchical Sampling
• Multiple Kernel Representation Learning on Networks
• Hierarchical Message-Passing Graph Neural Networks
• Calibrating and Improving Graph Contrastive Learning
• Topic-aware latent models for representation learning on networks
• Discourse-level Relation Extraction via Graph Pooling
• JITuNE: Just-In-Time Hyperparameter Tuning for Network Embedding Algorithms
• Initialization for Network Embedding: A Graph Partition Approach
• Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank
• Graph Cross Networks with Vertex Infomax Pooling
• Representation Learning of Graphs Using Graph Convolutional Multilayer Networks Based on Motifs
• The Atlas for the Aspiring Network Scientist
• A Quotient Space Formulation for Generative Statistical Analysis of Graphical Data
• HiCoRe: Visual Hierarchical Context-Reasoning
• Attribute2vec: Deep Network Embedding Through Multi-Filtering GCN
• TempNodeEmb:Temporal Node Embedding considering temporal edge influence matrix
• Unsupervised Hierarchical Graph Representation Learning by Mutual Information Maximization
• About Graph Degeneracy, Representation Learning and Scalability
• Bidirectional group random walk based network embedding for asymmetric proximity
• DGEM: A New Dual-modal Graph Embedding Method in Recommendation System
• Transformation of Node to Knowledge Graph Embeddings for Faster Link Prediction in Social Networks
• Graph Embedding with Hierarchical Attentive Membership
• Bitcoin Transaction Forecasting with Deep Network Representation Learning
• Matching through Embedding in Dense Graphs
• Multi-Hot Compact Network Embedding
• Better Understanding Hierarchical Visual Relationship for Image Caption
• Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings