Generative LLE modifies LLE to generate stochastic embeddings.
problem Nonlinear dimensionality reduction and manifold learning.
method Generative LLE modifies LLE by using stochastic linear reconstruction.
result Generative LLE can generate various LLE embeddings stochastically.
For graphs generated from stochastic blockmodels, adjacency spectral embedding is asymptotically consistent. Further, adjacency spectral embedding composed with universally consistent classifiers is universally consistent to achieve the Bayes error. However when the graph contains private or sensitive information, trea…
In deep neural nets, lower level embedding layers account for a large portion of the total number of parameters. Tikhonov regularization, graph-based regularization, and hard parameter sharing are approaches that introduce explicit biases into training in a hope to reduce statistical complexity. Alternatively, we propo…
Vertex clustering in a stochastic blockmodel graph has wide applicability and has been the subject of extensive research. In thispaper, we provide a short proof that the adjacency spectral embedding can be used to obtain perfect clustering for the stochastic blockmodel and the degree-corrected stochastic blockmodel. We…
The paper studies how adding an ℓ2 penalty affects network embeddings.
problem The impact of ℓ2 regularization on network embeddings.
method Analyzes the asymptotic behavior of ℓ2 regularized node2vec embeddings under graphon theory.
result The learned embeddings asymptotically form a graphon with a nuclear-norm-type penalty.
Unified view of SOMs and SNE from a common framework.
problem Comparing and understanding SOMs and SNE.
method Unified mathematical framework, quantitative comparison on datasets.
result SOMs and SNE can be derived from a common framework.
Stochastic Neighbor Embedding and its variants are widely used dimensionality reduction techniques -- despite their popularity, no theoretical results are known. We prove that the optimal SNE embedding of well-separated clusters from high dimensions to any Euclidean space R^d manages to successfully separate the cluste…
Explains SNE, t-SNE, and their variants for manifold learning.
problem Dimensionality reduction and manifold learning.
method Probabilistic approach using Gaussian and Student-t distributions.
result Out-of-sample extension and acceleration methods for t-SNE.
This work connects LLE, factor analysis, and probabilistic PCA through a stochastic perspective.
problem Exploring the theoretical connection between LLE, factor analysis, and probabilistic PCA.
method Solving the stochastic linear reconstruction of LLE using expectation maximization.
result LLE, factor analysis, and probabilistic PCA are shown to be connected through a stochastic perspective.
Geometric approach for unsupervised word embedding alignment.
problem Learning alignment between word embeddings of source and target languages.
method Formulates alignment as domain adaptation on the manifold of doubly stochastic matrices, employing Riemannian conjugate gradient algorithm.
result Empirically outperforms state-of-the-art methods on bilingual lexicon induction tasks.
Improved graph embedding through refined linear transformation and community recovery.
problem Identifying meaningful latent communities in graph data.
method Refined graph encoder embedding via linear transformation, self-training, and latent community recovery.
result Improved vertex embedding and better decision boundaries for vertex classification.
A new method estimates rare failure events in complex systems.
problem Estimating the probability of rare failure events in non-linear systems.
method Stochastic Spectral Embedding (SSE) combined with modifications for efficient rare event estimation.
result Rare failure probability decomposed into conditional probabilities for easier computation.
The paper examines node2vec embeddings for community detection in networks.
problem Theoretical understanding of node2vec embeddings for community detection.
method Analysis of node2vec embeddings for community recovery in stochastic block models.
result k-means clustering on node2vec embeddings gives weakly consistent community recovery for stochastic block models.
Proposes MR-SNE for multimodal data visualization.
problem Visualizing data from multiple domains with relations across them.
method Extends t-SNE to compute augmented relations and jointly embed them in a low-dimensional space.
result Demonstrates promising performance in visualizing Flickr and Animal with Attributes 2 datasets.
The paper tackles biases in session-based recommender systems by modeling user interest as a stochastic process.
problem Data uncertainty, popularity bias, and exposure bias in session-based recommender systems.
method The paper proposes treating user interest as a stochastic process in the latent space, debiasing item embeddings, modeling dense user interest, and introducing fake targets to simulate extended exposure.
result The proposed approach mitigates challenges in session-based recommender systems, as shown by computational experiments on various datasets.
The paper introduces new KMEs to capture stochastic process filtrations.
problem Missing filtration information in stochastic processes.
method Higher order kernel mean embeddings (KMEs) conditioned on filtrations.
result Consistent estimators and tests for filtration-sensitive information.
We describe a method for learning word embeddings with data-dependent dimensionality. Our Stochastic Dimensionality Skip-Gram (SD-SG) and Stochastic Dimensionality Continuous Bag-of-Words (SD-CBOW) are nonparametric analogs of Mikolov et al.'s (2013) well-known 'word2vec' models. Vector dimensionality is made dynamic b…
Embeds sparsity in deep neural networks, allowing exact zero parameters.
problem Learning sparse structures in deep networks.
method Embeds sparsity into neural network structure, allowing exact zero parameters during training.
result Can learn both structured and unstructured sparsity.
We introduce a nonlinear method for directly embedding large, sparse, stochastic graphs into low-dimensional spaces, without requiring vertex features to reside in, or be transformed into, a metric space. Graph data and models are prevalent in real-world applications. Direct graph embedding is fundamental to many graph…
ULES embeds dynamic networks with stability guarantees.
problem Stability of time-varying node embeddings in evolving networks.
method Unfolded Laplacian Spectral Embedding (ULSE) using normalized Laplacian operators.
result ULES satisfies cross-sectional and longitudinal stability under dynamic stochastic block model.
A probabilistic method for deep embedding that improves classification accuracy and interpretability.
problem Improving classification accuracy and interpretability in deep learning.
method A probabilistic approach that treats embeddings as random variables, using a product distribution over labeled instances and marginalizing prototype proximity.
result Superior large- and open-set classification accuracy compared to state-of-the-art methods.
Inference for the stochastic blockmodel is currently of burgeoning interest in the statistical community, as well as in various application domains as diverse as social networks, citation networks, brain connectivity networks (connectomics), etc. Recent theoretical developments have shown that spectral embedding of gra…
DeepWalk embeddings converge on SBM graphs, recovering cluster structure.
problem Theoretical guarantees for DeepWalk embeddings on complex graphs.
method Solving a nonconvex optimization problem using random walks.
result DeepWalk embeddings on SBM graphs recover cluster structure with high probability.
We unify subsampling methods for network embeddings and prove their asymptotic distribution.
problem Understanding and improving the performance of network embeddings learned via subsampling.
method Unified framework for node2vec-like methods, proving asymptotic distribution under exchangeable graph assumption.
result Asymptotic distribution of learned embedding vectors decouples and provides rates of convergence.
Node2vec embeddings are unstable and unstable with parameter choices.
problem Stability and robustness of node2vec embeddings for graph classification.
method Analysis of node2vec embeddings from multiple perspectives.
result Node2vec embeddings are unstable with respect to parameter choices.
Spectral embedding of adjacency or Laplacian matrices of undirected graphs is a common technique for representing a network in a lower dimensional latent space, with optimal theoretical guarantees. The embedding can be used to estimate the community structure of the network, with strong consistency results in the stoch…
New tools for uncertainty in dynamical systems without distribution assumptions.
problem Uncertainty representation in dynamical systems without distributional assumptions.
method Kernel mean embedding and kernel probabilistic programming.
result Distribution-free representation, comparison, and propagation of uncertainties.
We present a method to estimate block membership of nodes in a random graph generated by a stochastic blockmodel. We use an embedding procedure motivated by the random dot product graph model, a particular example of the latent position model. The embedding associates each node with a vector; these vectors are clustere…
A new algorithm reduces the time for ordinal embedding, making it faster and more scalable.
problem Efficiently learning representations from ordinal comparisons, especially for large datasets.
method SVRG-SBB: Stochastic variance reduced gradient with adaptive step size.
result Achieves $O( rac{1}{T})$ convergence rate and global linear convergence under certain assumptions.
This paper studies node embeddings of networks, revealing their geometric properties.
problem Understanding the geometric properties of node embeddings in random networks.
method Characterization of ergodic limits, generalization, and convex relaxations of random walk node embedding objectives.
result The optimal node embedding Grammians have rank 1 for a nuclear norm relaxation of the non-randomized objective.
FastGAE scales graph AE and VAE to large graphs with millions of nodes.
problem Scalability issues in graph AE and VAE.
method Stochastic subgraph decoding scheme to speed up training.
result Outperforms existing approaches on various real-world graphs.
The paper analyzes DeepWalk and node2vec for community detection in stochastic blockmodels.
problem Theoretical understanding of community detection in stochastic blockmodels.
method Matrix factorization perspective on DeepWalk and node2vec.
result Node2vec and DeepWalk can perfectly recover community memberships in sparse graphs.
In this paper, we propose a scalable algorithm for spectral embedding. The latter is a standard tool for graph clustering. However, its computational bottleneck is the eigendecomposition of the graph Laplacian matrix, which prevents its application to large-scale graphs. Our contribution consists of reformulating spect…
The t-distributed Stochastic Neighbor Embedding (t-SNE) is a powerful and popular method for visualizing high-dimensional data. It minimizes the Kullback-Leibler (KL) divergence between the original and embedded data distributions. In this work, we propose extending this method to other f-divergences. We analytically a…
Graph-based methods are known to be successful in many machine learning and pattern classification tasks. These methods consider semi-structured data as graphs where nodes correspond to primitives (parts, interest points, segments, etc.) and edges characterize the relationships between these primitives. However, these …
New method uses Cantor embeddings and Wasserstein distances to analyze predictive states in time series data.
problem Analyzing predictive states in stochastic processes using time series data.
method Wasserstein distances for detecting predictive equivalences in symbolic data, using Cantor embeddings for finite-dimensional representation.
result Exploratory analysis of temporal structure in various processes reveals insights.
The study of higher-order homology embeddings for manifold topology.
problem Understanding the structure of higher-order homology embeddings to disclose geometric or topological information.
method Analysis of the null space of the k-th order Laplacian and proposing an algorithm to factorize the homology embedding. result The proposed spectral loop detection algorithm is more efficient and effective on various data types.
Word embedding, which encodes words into vectors, is an important starting point in natural language processing and commonly used in many text-based machine learning tasks. However, in most current word embedding approaches, the similarity in embedding space is not optimized in the learning. In this paper we propose a …
Mathematical analysis of SNE and t-SNE for dimension reduction.
problem Optimal mapping of high-dimensional data to low dimensions.
method Gradient flow of relative entropy to minimize the distance between points.
result The diameter of the evolving sets remains bounded for SNE but may blow up for t-SNE.
The study models mortgage prepayment risk using stochastic housing market activity.
problem Modeling prepayment risk in mortgages under varying housing market conditions.
method Developed a stochastic model for prepayment option value, using swaption pricing formulas and non-standard actuarial hedging.
result Housing market covariance significantly impacts prepayment option prices.
MCE reduces embedding instability in nonlinear dimensionality reduction.
problem Embedding instability caused by random initialization.
method Median of multiple embeddings (MCE) based on large deviation theory.
result MCE achieves consistency at an exponential rate and effectively mitigates instability.
The paper corrects for node degree in spectral clustering using random walk Laplacian.
problem Node degree heterogeneity in spectral clustering.
method Graph spectral embedding using the random walk Laplacian.
result The embedding provides uniformly consistent estimates of degree-corrected latent positions.
We consider three different approaches to define natural Riemannian metrics on polytopes of stochastic matrices. First, we define a natural class of stochastic maps between these polytopes and give a metric characterization of Chentsov type in terms of invariance with respect to these maps. Second, we consider the Fish…
Paper studies t-SNE convergence with generalized kernels.
problem Understanding convergence of t-SNE with generalized kernels.
method Concrete formulation of generalized kernels, proving convergence to an equilibrium distribution.
result t-SNE converges to an equilibrium distribution under certain conditions for generalized kernels.
We exploit the symmetry concepts developed in the companion review of this article to introduce a stochastic version of link reversal symmetry, which leads to an improved understanding of the reciprocity of directed networks. We apply our formalism to the international trade network and show that a strong embedding in …
Study of intrinsic sub-Laplacian for hypersurfaces in contact sub-Riemannian manifolds.
problem Characterizing the intrinsic sub-Laplacian for hypersurfaces in contact sub-Riemannian manifolds.
method Construction and analysis of the intrinsic sub-Laplacian using Riemannian approximations and stochastic processes.
result The intrinsic sub-Laplacian is stochastically complete, ensuring the process does not hit characteristic points.
New graph embedding method improves link prediction and node classification.
problem Improving graph embedding methods for better node representation.
method Spectral-biased random walks with neighborhood similarity bias.
result Significantly improves link prediction and node classification.
Learning representation from relative similarity comparisons, often called ordinal embedding, gains rising attention in recent years. Most of the existing methods are batch methods designed mainly based on the convex optimization, say, the projected gradient descent method. However, they are generally time-consuming du…