The -NN graph has played a central role in increasingly popular data-driven techniques for various learning and vision tasks; yet, finding an efficient and effective way to construct -NN graphs remains a challenge, especially for large-scale high-dimensional data. In this paper, we propose a new approach to const…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,181 papers · 148 categories
Trend · papers per month
48 results for “NN graphs”
Implementing -NN classification using Gromov--Wasserstein distances
problem Comparing metric measure spaces
method Gromov--Wasserstein and fused Gromov--Wasserstein distances
result Universal consistency of -NN classifiers
The study evaluates and tests -NN models in various applications.
problem The relation between parameters and accuracy of -NN models is not well understood.
method Developed a randomized algorithm to test the -NN property with a complexity of .
result The algorithm can detect -NN models with bad accuracy in significantly less time than building the model.
New method reduces spectral clustering complexity by sparsifying graphs.
problem Computational bottleneck in spectral clustering due to eigendeomposition of NN graph Laplacian matrices.
method Spectrum-preserving graph sparsification via low-stretch spanning trees and spectral off-tree embedding.
result Ultra-sparse NN graphs with preserved first few eigenvectors for scalable spectral clustering.
Improved convergence rate for kNN graph Laplacians with adaptive bandwidth.
problem Enhancing the efficiency of graph-based data analysis methods.
method Introducing a new class of kNN graph with adaptive bandwidth and proving operator convergence rate.
result Operator convergence rate of for the kNN graph Laplacian, up to a log factor.
Study shows SNN graph Laplacians converge to k-NN graph Laplacians under large scale asymptotics.
problem Understanding the convergence of SNN graph Laplacians to k-NN graph Laplacians.
method Analyzing the asymptotic behavior of SNN and k-NN graph Laplacians.
result The graph Laplacians of SNN and k-NN graphs converge to the same limit under large scale asymptotics.
Graph NNs lose predictive power exponentially with more layers.
problem Graph Neural Networks (graph NNs) lose predictive power exponentially with more layers.
method Generalized the forward propagation of a Graph Convolutional Network (GCN) as a dynamical system and analyzed its asymptotic behaviors.
result GCNs' output exponentially approaches signals related to node degrees and connected components, leading to 'information loss' in the limit of infinite layers.
Graph neural networks can be adapted to new graphs with a limit object called graphon NNs.
problem Transferability of graph neural networks across different graphs.
method Introduced graphon NNs as limit objects of GNNs and proved a bound on the difference between GNN and graphon-NN outputs.
result The bound on the difference between GNN and graphon-NN outputs vanishes with growing number of nodes if the graph convolutional filters are bandlimited.
The paper improves spectral convergence rates for graph Laplacians.
problem Improving spectral convergence rates for graph Laplacians.
method Utilizing regularity of continuum eigenfunctions and strong pointwise consistency results.
result Eigenvalues and eigenvectors of graph Laplacian converge to continuum at rate .
New method improves nearest neighbor search using neural networks and graph partitioning.
problem Efficient nearest neighbor search in high-dimensional spaces.
method Developed a new framework for space partitioning using neural networks and graph partitioning.
result Neural LSH partitions outperform existing methods on standard benchmarks.
Nearest Neighbors (NN) is one of the most widely used supervised learning algorithms to classify Gaussian distributed data, but it does not achieve good results when it is applied to nonlinear manifold distributed data, especially when a very limited amount of labeled samples are available. In this paper, we pro…
Proposes a new CG interpretation of neural networks for better theoretical analysis.
problem Lack of theoretical analysis in neural networks interpretation.
method Interprets neural networks as chain graphs and feed-forward as approximate inference.
result Provides novel theoretical support and insights for various neural network techniques.
This paper studies the large sample asymptotics of data analysis procedures based on the optimization of functionals defined on -NN graphs on point clouds. The paper is framed in the context of minimization of balanced cut functionals, but our techniques, ideas and results can be adapted to other functionals of rele…
The paper examines how neural network topology affects adversarial robustness.
problem Understanding how neural network topology influences adversarial robustness.
method Investigated the graph of input traversing all layers of a neural network, comparing clean and adversarial inputs.
result Under-optimized edges in neural network graphs are a source of adversarial vulnerability and can be used to detect adversarial inputs.
ASK-NN: An Asymmetric Nearest-Neighbor Test that detects Distribution Drifts in Natural Languagecs.LG
ASK-NN detects distribution drifts in LLM-generated text.
problem Hallucinations and artificial text in LLM-generated outputs.
method Asymmetric two-sample test based on directed k-nearest-neighbor graph.
result ASK-NN is competitive with baselines on various benchmarks.
Graph construction is a crucial step in spectral clustering (SC) and graph-based semi-supervised learning (SSL). Spectral methods applied on standard graphs such as full-RBF, -graphs and -NN graphs can lead to poor performance in the presence of proximal and unbalanced data. This is because spectral methods based…
Spectral clustering (SC) and graph-based semi-supervised learning (SSL) algorithms are sensitive to how graphs are constructed from data. In particular if the data has proximal and unbalanced clusters these algorithms can lead to poor performance on well-known graphs such as -NN, full-RBF, -graphs. This is becaus…
The paper studies recovering hidden nearest neighbor graphs in large networks.
problem Discovering strong ties in social networks and assembling genome subsequences.
method Maximum likelihood estimator for recovering hidden -nearest neighbor graphs.
result The maximum likelihood estimator achieves asymptotic recovery guarantees under specific conditions.
GNTK reveals convergence of GNNs on large graphs.
problem Understanding and optimizing GNNs on large graphs.
method Graph Neural Tangent Kernels (GNTK) and graphons.
result GNTKs converge to graphon NTKs on large graphs, enabling task inference.
Graph neural networks detect collusion patterns across markets.
problem Detecting and predicting collusion in different national markets.
method Two-phase approach using GNNs for zero-shot learning and OOD generalization.
result GNNs outperform NNs in detecting complex collusive patterns.
Previously, we proposed a physically inspired rule to organize the data points in a sparse yet effective structure, called the in-tree (IT) graph, which is able to capture a wide class of underlying cluster structures in the datasets, especially for the density-based datasets. Although there are some redundant edges or…
GNNs outperform NNs in interpolating bandlimited functions on Euclidean cubes.
problem Interpolating bandlimited functions on Euclidean cubes using GNNs vs. NNs.
method Investigates optimal GNN configurations and weights for function interpolation.
result GNNs require fewer weights and samples to interpolate bandlimited functions compared to NNs.
Paper introduces MNNs for efficient neural network training.
problem Training large-scale sparse neural networks efficiently.
method Formal derivation of MNN architecture with forward-only gradient propagation.
result MNNs can efficiently compute gradients without backward computation.
Study designs neural networks for fault localization, state estimation, and optimal PMU placement in power systems.
problem Fault localization, state estimation, and optimal PMU placement in power systems.
method Designs and compares various neural networks for fault localization, builds machine learning schemes for state estimation and parameter estimation, and designs an algorithm for optimal PMU placement.
result Comprehensive comparison of neural networks for fault localization shows that Graphical Convolutional NN and Neural Graph-based ODE perform best.
Graph convolutional deep kernel machine learns representations for graph tasks.
problem Limited representation learning in infinite-width neural networks.
method Developed a graph convolutional deep kernel machine as an infinite-width limit.
result Representation learning improves performance for heterophilous node classification tasks.
We propose a non-parametric anomaly detection algorithm for high dimensional data. We score each datapoint by its average -NN distance, and rank them accordingly. We then train limited complexity models to imitate these scores based on the max-margin learning-to-rank framework. A test-point is declared as an anomaly…
Nearest neighbor (k-NN) graphs are widely used in machine learning and data mining applications, and our aim is to better understand what they reveal about the cluster structure of the unknown underlying distribution of points. Moreover, is it possible to identify spurious structures that might arise due to sampling va…
Study uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
problem Uniform convergence of random walk Laplacians to diffusion Laplacian on smooth manifolds.
method Analysis of random walks on geometric and directed kNN graphs, using concentration tools and differential geometry.
result Uniform convergence of NN Laplacians to diffusion Laplacian, without continuity of transition kernel.
The paper proposes a method to achieve 1-NN speed with k-NN accuracy.
problem Achieving both the speed of 1-NN and the accuracy of k-NN.
method Aggregating denoised 1-NN predictors over a small number of distributed subsamples.
result Small subsample sizes can match or improve k-NN performance without sacrificing 1-NN's computational efficiency.
Study evaluates neural networks based on random graph structures and finds key performance indicators.
problem Understanding and optimizing neural network architectures using graph theory.
method Evaluation of neural networks with random graph structures, focusing on structural and numerical properties.
result A new numerical graph characteristic selects a set of quasi-1-dimensional graphs that perform well.
New method predicts dynamic relationships in terrorist networks.
problem Dynamic co-evolution of multiplex graphs and nodal attributes in terrorism networks.
method Time-varying stochastic latent factor models with neural network Gaussian processes.
result Superior performance in predicting unobserved dynamic relationships.
cuSLINK clusters data faster on GPUs, saving space and time.
problem Efficiently clustering large datasets on GPUs.
method Reformulated SLINK algorithm on GPU with optimized building blocks.
result cuSLINK uses space and trades off space and time with parameter .
Neural networks improve geospatial data analysis by relaxing linearity assumptions.
problem Traditional geospatial analysis assumes linear models, limiting flexibility.
method Embedding neural networks within traditional geostatistical models for non-linear mean functions.
result NN-GLS algorithm provides consistent and scalable predictions for irregular spatial data.
Randomly trained neural networks can generalize well if there's a simpler underlying teacher model.
problem Why randomly trained neural networks generalize well despite interpolating training data.
method Examined a random neural network that interpolates training data and showed it generalizes well if there's a simpler underlying teacher model.
result Randomly trained neural networks can generalize well if there's a simpler underlying teacher model.
This paper analyzes deep Stable neural networks, showing convergence rates under different growth settings.
problem Analyzing the behavior of deep Stable neural networks as width increases.
method Large-width asymptotic analysis and convergence rates for fully connected feed-forward deep Stable NNs.
result The rescaled deep Stable NN converges weakly to a Stable SP under joint growth, with sup-norm convergence rates established.
Study bridges GARCH and NN models for volatility forecasting.
problem Lack of interaction between GARCH and NN approaches for volatility forecasting.
method Established equivalence between GARCH and NN models, introduced GARCH-NN approach.
result GARCH-NN approach enhances volatility forecasting compared to standalone models.
Non-asymptotic uniform rates for k-NN regression are derived.
problem Estimating functions from noisy observations with unknown lower dimensionality.
method Derives high-probability finite-sample uniform rates of consistency for k-NN regression.
result k-NN regression rates are optimal up to logarithmic factors and adapt to unknown lower dimensions.
Paper proposes MS-k-NN for improved convergence rate in k-NN classification.
problem Improving convergence rate of k-NN classification methods.
method Proposes MS-k-NN that extrapolates unweighted k-NN estimators to k=0.
result MS-k-NN achieves improved convergence rate under certain conditions.
A fast method for LOOCV in k-NN regression reduces computation time.
problem Efficient computation of LOOCV for k-NN regression.
method Identical LOOCV estimate to (k+1)-NN MSE on training data.
result LOOCV computation can be done with (k+1)-NN regression once.
Adds layers to NNs to protect them from reverse engineering.
problem Extracting the underlying model of a Neural Network.
method Introducing parasitic layers that approximate a noisy identity mapping with a Convolutional NN.
result The protected NN's predictions remain mostly unchanged while making reverse-engineering more complex.
Study resilience of NN accelerators, especially fault characterization and mitigation.
problem Faults in hardware accelerators of NNs, especially at 10nm technology node.
method Characterized fault vulnerability of RTL NN components and developed a fault mitigation technique.
result Fault mitigation technique improves accuracy by 47.3%.
Universal consistency and rates of convergence of multiclass prototype algorithms in metric spacescs.LG
Prototype rules simplify multiclass classification in metric spaces, achieving consistency and reduced complexity.
problem Multiclass classification in metric spaces, focusing on universal consistency and convergence rates.
method Novel Proto-NN and hybrid rules for multiclass classification in metric spaces, analyzing convergence rates.
result Proto-NN is universally consistent and simpler to implement, with similar computational advantages.
We propose a direct estimation method for Rényi and f-divergence measures based on a new graph theoretical interpretation. Suppose that we are given two sample sets and , respectively with and samples, where is a constant value. Considering the -nearest neighbor (-NN) graph of in the j…
Modular NNs improve training speed and stability.
problem Complexity in NNs with many parameters or intricate architectures.
method Decompose NN into control and functional modules.
result Modular NNs outperform monolithic ones in training speed and stability.
This work establishes the equivalence between neural networks and support vector machines.
problem Establishing the equivalence between neural networks and support vector machines.
method Proposed a method to establish the equivalence between infinitely wide neural networks trained by soft margin loss and standard soft margin SVMs with NTK trained by subgradient descent.
result The equivalence between NN and SVM is established, enabling practical applications such as non-vacuous generalization bounds and robustness certificates.
New metrics for assessing neural network dependability.
problem Need for metrics to measure NN dependability.
method Proposed metrics for NN robustness, interpretability, completeness, correctness.
result Efficiently computable metrics for NN dependability.
Estimates generalization error for two-layer ReLU NNs through minimum norm solutions.
problem Estimating generalization error for two-layer ReLU NNs trained by mean squared error.
method Uses minimum norm solutions and Neural Tangent Kernel (NTK) regime to derive generalization error bounds.
result Derives an a priori generalization error bound for two-layer ReLU NNs without requiring exponentially large number of neurons.
RIO estimates uncertainty in NN predictions without changing model architecture.
problem Uncertainty estimation in NN point predictions.
method RIO uses a Gaussian Process with an I/O kernel to model NN residuals.
result RIO provides reliable uncertainty estimates and reduces prediction error.