Random projection tree similarity metric for SpectralNet

• URL: http://arxiv.org/abs/2302.13168v1
• Date: Sat, 25 Feb 2023 21:32:16 GMT
• Title: Random projection tree similarity metric for SpectralNet
• Authors: Mashaan Alshammari, John Stavrakakis, Adel F. Ahmed, Masahiro Takatsuka
• Abstract summary: SpectralNet is a graph clustering method that uses neural network to find an embedding that separates the data. We proposed a new SpectralNet similarity metric based on random projection trees (rpTrees) Our experiments revealed that SpectralNet produces better clustering accuracy using rpTree similarity metric compared to $k$-nn graph with a distance metric.
• Score: 1.376408511310322
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: SpectralNet is a graph clustering method that uses neural network to find an embedding that separates the data. So far it was only used with $k$-nn graphs, which are usually constructed using a distance metric (e.g., Euclidean distance). $k$-nn graphs restrict the points to have a fixed number of neighbors regardless of the local statistics around them. We proposed a new SpectralNet similarity metric based on random projection trees (rpTrees). Our experiments revealed that SpectralNet produces better clustering accuracy using rpTree similarity metric compared to $k$-nn graph with a distance metric. Also, we found out that rpTree parameters do not affect the clustering accuracy. These parameters include the leaf size and the selection of projection direction. It is computationally efficient to keep the leaf size in order of $\log(n)$, and project the points onto a random direction instead of trying to find the direction with the maximum dispersion.

Related papers

• Fast online node labeling with graph subsampling [4.259367043722417]
  Graph-based methods, such as node prediction, aim for computational efficiency regardless of graph size. In this paper, we consider an emphonline subsampled APPR method, where messages are intentionally dropped at random. We use tools from graph sparsifiers and matrix linear algebra to give approximation bounds on the graph's spectral properties.
  arXiv  Detail & Related papers  (2025-03-21T00:13:16Z)
• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  unsupervised ground metric learning approaches have been introduced. We propose to augment the WSV method by embedding samples and features on trees, on which we compute the tree-Wasserstein distance (TWD) We demonstrate theoretically and empirically that the algorithm converges to a better approximation of the full WSV approach than the best known alternatives, and does so with $mathcalO(n3)$ complexity.
  arXiv  Detail & Related papers  (2024-11-11T23:21:01Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Fitting trees to $\ell_1$-hyperbolic distances [4.220336689294244]
  Building trees to represent or to fit distances is a critical component of phylogenetic analysis. We study the tree fitting problem as finding the relation between the hyperbolicity (ultrametricity) vector and the error of tree (ultrametric) embedding.
  arXiv  Detail & Related papers  (2024-09-02T07:38:32Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• A parameter-free graph reduction for spectral clustering and SpectralNet [1.5469452301122175]
  We introduce a graph reduction method that does not require any parameters. First, distances from every point $p$ to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. The edges that survive two steps form the constructed graph that was passed to spectral clustering SpectralNet.
  arXiv  Detail & Related papers  (2023-02-25T21:19:30Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• Sampling Enclosing Subgraphs for Link Prediction [2.1270496914042996]
  Link prediction is a fundamental problem for graph-structured data computation. This paper presents a scalable solution, that we call ScaLed, which utilizes sparse enclosing subgraphs to make predictions. By leveraging the smaller sampled subgraph, ScaLed can scale to larger graphs with much less overhead while maintaining high accuracy.
  arXiv  Detail & Related papers  (2022-06-23T22:48:44Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  We study the problem of robustly estimating the parameter $p$ of an ErdHos-R'enyi random graph on $n$ nodes. We give an inefficient algorithm with similar accuracy for all $gamma 1/2$, the information-theoretic limit.
  arXiv  Detail & Related papers  (2021-11-09T18:43:25Z)
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
  We design and analyze an algorithm that boosts the error exponent by at least 40% when $rho$ is at least $0.8$. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph.
  arXiv  Detail & Related papers  (2021-10-27T10:45:21Z)
• Correlation detection in trees for partial graph alignment [3.5880535198436156]
  We consider alignment of graphs, which consists in finding a mapping between the nodes of two graphs which preserves most of the edges. Our approach is to compare local structures in the two graphs, matching two nodes if their neighborhoods are 'close enough' for correlated graphs. This problem can be rephrased in terms of testing whether a pair of branching trees is drawn from either a product distribution, or a correlated distribution.
  arXiv  Detail & Related papers  (2021-07-15T22:02:27Z)
• On Explainability of Graph Neural Networks via Subgraph Explorations [48.56936527708657]
  We propose a novel method, known as SubgraphX, to explain graph neural networks (GNNs) Our work represents the first attempt to explain GNNs via identifying subgraphs explicitly.
  arXiv  Detail & Related papers  (2021-02-09T22:12:26Z)

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.