Coupled Hierarchical Structure Learning using Tree-Wasserstein Distance

• URL: http://arxiv.org/abs/2501.03627v1
• Date: Tue, 07 Jan 2025 08:54:42 GMT
• Title: Coupled Hierarchical Structure Learning using Tree-Wasserstein Distance
• Authors: Ya-Wei Eileen Lin, Ronald R. Coifman, Gal Mishne, Ronen Talmon,
• Abstract summary: We introduce a coupled hierarchical structure learning method using tree-Wasserstein distance (TWD) Our method jointly computes TWDs for samples and features, representing their latent hierarchies as trees. We show that this iterative procedure converges and empirically improves the quality of the constructed trees.
• Score: 12.2853783834605
• License:
• Abstract: In many applications, both data samples and features have underlying hierarchical structures. However, existing methods for learning these latent structures typically focus on either samples or features, ignoring possible coupling between them. In this paper, we introduce a coupled hierarchical structure learning method using tree-Wasserstein distance (TWD). Our method jointly computes TWDs for samples and features, representing their latent hierarchies as trees. We propose an iterative, unsupervised procedure to build these sample and feature trees based on diffusion geometry, hyperbolic geometry, and wavelet filters. We show that this iterative procedure converges and empirically improves the quality of the constructed trees. The method is also computationally efficient and scales well in high-dimensional settings. Our method can be seamlessly integrated with hyperbolic graph convolutional networks (HGCN). We demonstrate that our method outperforms competing approaches in sparse approximation and unsupervised Wasserstein distance learning on several word-document and single-cell RNA-sequencing datasets. In addition, integrating our method into HGCN enhances performance in link prediction and node classification tasks.

Related papers

• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  unsupervised ground metric learning approaches have been introduced. One promising option employs Wasserstein singular vectors (WSVs), which emerge when computing optimal transport distances between features and samples simultaneously. We propose to augment the WSV method by embedding samples and features on trees, on which we compute the tree-Wasserstein distance (TWD)
  arXiv  Detail & Related papers  (2024-11-11T23:21:01Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• Pushing the Efficiency Limit Using Structured Sparse Convolutions [82.31130122200578]
  We propose Structured Sparse Convolution (SSC), which leverages the inherent structure in images to reduce the parameters in the convolutional filter. We show that SSC is a generalization of commonly used layers (depthwise, groupwise and pointwise convolution) in efficient architectures'' Architectures based on SSC achieve state-of-the-art performance compared to baselines on CIFAR-10, CIFAR-100, Tiny-ImageNet, and ImageNet classification benchmarks.
  arXiv  Detail & Related papers  (2022-10-23T18:37:22Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  We propose a one-step gradient matching scheme, which performs gradient matching for only one single step without training the network weights. Our theoretical analysis shows this strategy can generate synthetic graphs that lead to lower classification loss on real graphs. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance.
  arXiv  Detail & Related papers  (2022-06-15T18:20:01Z)
• Structural Optimization Makes Graph Classification Simpler and Better [5.770986723520119]
  We investigate the feasibility of improving graph classification performance while simplifying the model learning process. Inspired by progress in structural information assessment, we optimize the given data sample from graphs to encoding trees. We present an implementation of the scheme in a tree kernel and a convolutional network to perform graph classification.
  arXiv  Detail & Related papers  (2021-09-05T08:54:38Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• Unsupervised Embedding of Hierarchical Structure in Euclidean Space [30.507049058838025]
  We consider learning a non-linear embedding of data into Euclidean space as a way to improve the hierarchical clustering produced by agglomerative algorithms. We show that rescaling the latent space embedding leads to improved results for both dendrogram purity and the Moseley-Wang cost function.
  arXiv  Detail & Related papers  (2020-10-30T03:57:09Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Oblique Predictive Clustering Trees [6.317966126631351]
  Predictive clustering trees (PCTs) can be used to solve a variety of predictive modeling tasks, including structured output prediction. We propose oblique predictive clustering trees, capable of addressing these limitations. We experimentally evaluate the proposed methods on 60 benchmark datasets for 6 predictive modeling tasks.
  arXiv  Detail & Related papers  (2020-07-27T14:58:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.