Source-linked AI summary
HARP: Hierarchical Representation Learning for Networks
Haochen Chen, Bryan Perozzi, Yifan Hu, Steven Skiena
TL;DR
Existing graph-embedding methods can neglect higher-order structure and converge to poor solutions because of local approaches and non-convex optimization. HARP hierarchically coarsens graphs, embeds the coarsest versions, and transfers those representations to finer graphs. Across DeepWalk, LINE, and Node2vec, HARP improves classification performance on real-world networks, with gains up to 14% Macro F1.
Problem
Existing graph-embedding methods do not model higher-order structure and can suffer from poor initialization during stochastic optimization.
Method
HARP recursively coarsens the input graph into structurally similar smaller graphs, learns coarse embeddings, and uses them to initialize embeddings at finer levels.
Results
HARP improves DeepWalk, LINE, and Node2vec on classification tasks across real-world networks, with improvements as large as 14% Macro F1.
Takeaways & Limitations
The hierarchical paradigm provides improved implementations of multiple state-of-the-art graph representation-learning methods.
Takeaways & Limitations
The paper identifies future work in extending HARP beyond shallow Skip-gram methods to deep representation-learning methods.
Abstract
from arXiv · showhide
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.
Introduction
Graph embeddings support prediction tasks but existing approaches can miss global structure and suffer from poor non-convex optimization, motivating HARP’s hierarchical paradigm. HARP improves DeepWalk, LINE, and Node2vec embeddings, with classification gains up to 14% Macro F1.
- Motivation: Large networks motivate low-dimensional node representations for tasks including classification, clustering, and link prediction.Traditional dimensionality-reduction methods are at least quadratic in the number of nodes, limiting their use on large networks.
- Limitations: Existing neural graph-embedding methods focus on local neighborhoods and can miss long-distance global structural patterns.DeepWalk and Node2vec use short random walks, while LINE models relationships up to two hops away.
- HARP: HARP recursively coalesces a graph into smaller, structurally similar graphs and transfers coarse embeddings as initializations to progressively finer graphs.The process continues until representations are learned for every node in the original graph.
- Contribution: HARP combines graph-drawing and graph-representation-learning ideas into a multilevel paradigm for better graph embeddings.The approach is designed as a general representation-learning strategy rather than a separate embedding objective.
- Results: 14% Macro F1 is the largest reported improvement over the original implementations on classification tasks across real-world networks.HARP(DW), HARP(LINE), and HARP(N2V) consistently outperform their corresponding baselines.
Problem Formulation
The hierarchical representation-learning problem seeks compact graphs that preserve essential structure and provide better conditions for embedding large graphs. The proposed procedure coarsens the graph, embeds the coarsest level, and iteratively refines representations to the original graph.
- Problem Formulation: Graph representation learning maps nodes in G to d-dimensional latent vectors, with d much smaller than the number of nodes.Existing methods are described as limited by missing higher-order structure and poor initialization during stochastic optimization.
- Hierarchical Problem: The target coarse graph Gs preserves essential structure while having far fewer nodes and edges than the original graph G.The formulation requires |Vs| << |V| and |Es| << |E|.
- Hierarchical Problem: Coarsening reduces pairwise relationships and may smooth the objective, making optimization easier than on the original graph.The comparison is between |Vs|^2 and |V|^2 possible pairwise relationships.
- Hierarchical Problem: A smaller graph may also have a shorter diameter, allowing locally focused algorithms to exploit global graph structure.This is presented as a second reason why the coarse graph can be easier to embed.
- Procedure: The general procedure simplifies G into successively smaller graphs, learns an embedding at the coarsest level, and refines it toward the original graph.The supplied formulation specifies a coarse embedding Φ_G_L = f(G_L, ∅) followed by iterative refinement.
Method
HARP’s hierarchical paradigm embeds graphs from coarse to fine and includes graph coarsening as its crucial structure-preserving step.
- Method: HARP first presents the hierarchical graph-embedding paradigm, then develops a structure-preserving algorithm for graph coarsening.Graph coarsening is identified as the crucial step in the method’s construction.
Algorithm: HARP
HARP hierarchically coarsens a graph, embeds the smallest representation, and progressively refines embeddings back to the original graph. Its hybrid coarsening preserves complementary structural proximities and is designed as an algorithm-independent strategy with comparable asymptotic training complexity.
- Hierarchical representation learning: The method combines graph coarsening, graph embedding, and representation refinement to produce an embedding matrix for the original graph.Representations from coarser graphs are prolonged to finer graphs and refined with the supplied embedding algorithm.
- Hierarchical representation learning: HARP builds successively smaller graphs that preserve the original graph’s global structure, then embeds them from coarsest to finest.The hierarchy supplies initial representations for each more detailed graph.
- Algorithm independence: HARP is algorithm-independent because it relies only on the provided Embed() function, allowing the paradigm to extend to existing graph representation-learning methods.The supplied algorithm is applied at each level, beginning with the coarsest graph.
- Hybrid graph coarsening: The hybrid coarsening scheme combines star collapsing and edge collapsing to preserve second-order and first-order proximity, respectively.Star collapsing merges nodes with shared neighbors, while edge collapsing merges disjoint incident edge pairs.
- Hybrid graph coarsening: Edge collapsing alone compresses star-like graphs slowly, requiring O(k) steps rather than O(log k) when the hub degree is k.Star collapsing addresses this limitation by merging peripheral nodes with identical neighborhoods.
- Complexity: HARP(DW) and HARP(LINE) retain the asymptotic training complexities of DeepWalk and LINE, respectively.The stated complexities are O(γ|V|tw(d + dlog|V|)) for HARP(DW) and O(r|E|) for HARP(LINE).
Experiment
Experiments evaluate HARP-enhanced DeepWalk, LINE, and Node2vec on real-world graph classification, coarsening, visualization, and runtime. Across datasets, HARP improves classification performance while adding limited runtime overhead.
- Datasets and Methods: Experiments use DBLP, BlogCatalog, and CiteSeer for multi-label classification, comparing DeepWalk, LINE, Node2vec, and their HARP-enhanced versions.The datasets represent co-authorship, social relationships, and citation networks, respectively.
- Datasets and Methods: Equal total sample counts are used for each baseline and its corresponding HARP-enhanced algorithm to ensure fair comparison.This control applies because all three methods are sampling-based.
- Graph Coarsening: At level 8, every test graph retains less than 10% of its original nodes and edges after continued coarsening.The first coarsening step removes about half the nodes, while BlogCatalog loses only about 10% of its edges initially.
- Visualization: A 21-node level-5 graph already resembles the original Poisson 2D layout, and prolongated layouts preserve global structure at subsequent levels.HARP(LINE) embeddings are visualized across coarsening levels with two-dimensional representations.
- Multi-label Classification: HARP improves Macro F1 for all three neural embedding methods across DBLP, BlogCatalog, and CiteSeer.At the reported label rates, gains range from 0.3% for HARP(N2V) on DBLP to 13.6% for HARP(LINE) on CiteSeer.
- Runtime: HARP typically adds less than 10% to total runtime, while its runtime scales linearly with graph size and coarsening overhead is negligible on large graphs.Sampling and Skip-gram training dominate total runtime.
Related Work
Graph representation learning has progressed from small-graph dimensionality reduction to scalable neural methods, but these methods remain vulnerable to poor local optima and limited global-structure capture. HARP extends multilevel graph-drawing ideas to address these weaknesses in neural graph embeddings.
- Non-convex optimization with random or zero initialization can converge to poor local minima.
- HARP extends multilevel graph layout to neural representation learning and combines the paradigm with three state-of-the-art embedding methods.
Conclusion
HARP addresses poor initialization and neglected global structure by recursively coarsening graphs, learning representations from coarse to fine, and combining this process with established embedding methods. The authors report higher-quality embeddings across DeepWalk, LINE, and Node2vec, while identifying broader method integration as future work.
- HARP recursively coalesces graphs into smaller structurally similar forms to capture global structure and derive initialization for the input graph.
- HARP is combined with DeepWalk, LINE, and Node2vec as a multilevel graph representation-learning paradigm.
- HARP produces higher-quality graph embeddings for all three evaluated state-of-the-art methods on various real-world graphs.
- Future work includes combining HARP with other graph representation-learning methods, especially deep methods beyond shallow Skip-gram learning.