End-to-End Learning of Probabilistic Hierarchies on Graphs

Daniel Zügner, Bertrand Charpentier, Morgane Ayle, Sascha Geringer, Stephan GünnemannICLR 2022 · OpenReview

Hierarchical clustering is a cornerstone of unsupervised learning, allowing us to see data not just as a flat collection of groups, but as a multi-scale organization—think of an evolutionary tree or a file system. However, performing this on graphs has traditionally been a choice between fast but "dumb" heuristics (like average linkage) or sophisticated deep learning models that struggle with the discrete, non-differentiable nature of trees.

In this work, researchers introduce Flexible Probabilistic Hierarchies (FPH), a framework that turns hierarchical clustering into a fully differentiable optimization problem using the elegant mathematics of Markov chains.

The Challenge of Discrete Trees

Traditional hierarchical clustering algorithms (like Agglomerative Nesting) are often greedy and heuristic-based; they do not optimize a global objective function. While newer deep learning methods attempt to optimize metrics like Dasgupta cost or Tree Sampling Divergence (TSD), they hit a wall: trees are inherently discrete structures.

To make these metrics differentiable, previous "continuous" methods relied on approximations or proxy losses to estimate the probability of two nodes sharing a common ancestor. These approximations are often computationally expensive or mathematically "fuzzy," leading to sub-optimal hierarchies. Furthermore, many existing deep learning approaches for hierarchies fail to scale well to massive real-world networks.

Methods: A Markov Chain Approach

The core innovation of FPH is treating a hierarchy as an acyclic absorbing Markov chain.

Probabilistic Hierarchy Model
  1. Continuous Relaxation: Instead of a hard binary tree, the model uses two matrices, $A$ and $B$, representing the probability of a leaf node or an internal node having a specific parent. This allows the model to learn a "soft" hierarchy.
  2. The Markov Chain Link: Imagine a random walk starting at a leaf node and moving "up" the hierarchy. Each step follows the probabilities in $A$ and $B$ until it reaches the root (the "absorbing state").
  3. Exact LCA Probabilities: Using the Fundamental Matrix of Markov chains, the authors derived exact, vectorized, closed-form expressions for the probability that any internal node $z$ is the Lowest Common Ancestor (LCA) of two leaves $v_i$ and $v_j$.
  4. End-to-End Optimization: Because the LCA probabilities are now exact and differentiable, the authors can directly maximize "Soft-TSD" or minimize "Soft-Dasgupta" cost using Projected Gradient Descent (PGD).
  5. Scalability: To handle massive graphs, they implemented a subgraph batching scheme that allows the model to learn from local structures without keeping the entire graph in GPU memory.

Key Insights and Ideas

  • The "Aha" Moment on LCAs: The realization that LCA probabilities—the hardest part of hierarchical optimization—could be solved exactly using Markov chain theory is the paper's biggest contribution. It replaces "soft" heuristics with rigorous math.
  • Integrality of Soft-TSD: The authors prove that the Soft-TSD optimization problem is integral. This means the global maximum of their continuous relaxation is guaranteed to be a discrete, valid tree. This justifies the use of continuous optimization for a discrete problem.
  • PGD > Softmax: A practical insight for practitioners: the authors found that standard Softmax parameterization leads to vanishing gradients in this architecture. Using Projected Gradient Descent (PGD) on the raw matrices yielded significantly better results.
  • Hierarchies for Link Prediction: Even though FPH is never trained to predict edges, the hierarchies it discovers are so representative of the graph's structure that it achieves state-of-the-art results on link prediction tasks "out of the box."

Key Results

The authors evaluated FPH on 11 real-world graphs (ranging from small brain networks to massive datasets like ogbn-products with 2.3M nodes) and several synthetic benchmarks.

Clustering Performance Table
  • State-of-the-Art Clustering: As shown in the results table, FPH outperformed both traditional baselines (like Average Linkage and Ward) and recent deep learning methods (like HypHC and RGHC) across almost all datasets in terms of Dasgupta cost (lower is better) and Normalized TSD (higher is better).
  • Massive Scaling: FPH was the only deep learning-based method capable of producing a high-quality hierarchy for the 2.3M-node ogbn-products dataset, where others ran out of memory or failed to converge.
  • Link Prediction: On the OpenFlight dataset, FPH achieved a 99.3% AUC-PR for link prediction, outperforming dedicated models like Variational Graph Autoencoders (VGAE).
  • Efficiency: Despite the complex math, the vectorized implementation is very fast. A full forward pass on a graph with thousands of nodes takes only ~130ms on a standard GPU.

Limitations and Future Work

  • Fixed Capacity: The number of internal nodes is a hyperparameter that must be set beforehand. The model doesn't currently "grow" or "prune" the number of levels dynamically during training.
  • Dasgupta Integrality: While Soft-TSD is proven to be integral, the authors note that Soft-Dasgupta is not obviously so, which might lead to more local optima when optimizing for that specific metric.
  • Downstream Tasks: While the paper shows great results for link prediction, future work could explore how these learned hierarchies improve other tasks like node classification or graph visualization.

Summary updated

Abstract

We propose a novel probabilistic model over hierarchies on graphs obtained by continuous relaxation of tree-based hierarchies. We draw connections to Markov chain theory, enabling us to perform hierarchical clustering by efficient end-to-end optimization of relaxed versions of quality metrics such as Dasgupta cost or Tree-Sampling Divergence (TSD). We show that our model learns rich, high-quality hierarchies present in 11 real world graphs, including a large graph with 2.3M nodes. Our model consistently outperforms recent as well as strong traditional baselines such as average linkage. Our model also obtains strong results on link prediction despite not being trained on this task, highlighting the quality of the hierarchies discovered by our model.
BibTeX
@inproceedings{zugner2022end,
  author = {Daniel Zügner and Bertrand Charpentier and Morgane Ayle and Sascha Geringer and Stephan Günnemann},
  title = {{End-to-End Learning of Probabilistic Hierarchies on Graphs}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=g2LCQwG7Of},
}
Figure