Neighborhood sampling affects graph neural network training outcomes.
problem Understanding the impact of neighborhood sampling on graph neural network training.
method Theoretical analysis using neural tangent kernels and Gaussian processes.
result Posterior covariance differs for different neighborhood sampling approaches, indicating no dominant approach.
As an efficient and scalable graph neural network, GraphSAGE has enabled an inductive capability for inferring unseen nodes or graphs by aggregating subsampled local neighborhoods and by learning in a mini-batch gradient descent fashion. The neighborhood sampling used in GraphSAGE is effective in order to improve compu…
Learn conditional averages in PAC framework for better predictions.
problem Learning average labels over neighborhoods in unknown concept class.
method Characterization of learnability using combinatorial parameters.
result Complete characterization and sample complexity bounds.
New method pools labels from similar data items to improve learning from small samples.
problem Learning from small, human-annotated samples with potential disagreement among annotators.
method Proposes neighborhood-based pooling for sharing labels across similar data items.
result Improves learning from small, noisy samples by pooling labels from similar items.
Applied researchers often construct a network from a random sample of nodes in order to infer properties of the parent network. Two of the most widely used sampling schemes are subgraph sampling, where we sample each vertex independently with probability p and observe the subgraph induced by the sampled vertices, and…
Flexible outlier detection using graph communities for robust performance.
problem Outlier detection in small sample size unbalanced problems.
method Local measure of label heterogeneity in a weighted graph topology.
result Overall outperforms local and global strategies in multi and single view settings.
A new ensemble method improves kNN performance by extending the neighborhood rule.
problem Traditional kNN's limitations when test points are outside the spherical region and ensemble's high errors.
method Determines neighbors in k steps, using bootstrap samples and optimal models selection.
result The proposed ensemble method outperforms state-of-the-art methods on 17 benchmark datasets.
Bagging reduces variance in LID estimation by preserving local distribution of NN distances.
problem High estimation variance from limited data in small neighborhoods.
method Subbagging to preserve local distribution of NN distances, combined with ensemble size.
result Bagging significantly reduces variance and MSE in LID estimation.
Proposes a new regularization method for deep learning models.
problem Lack of leverage from neighboring sample relationships in existing regularization techniques.
method Patch-level Neighborhood Interpolation (Pani) that constructs patch-level graphs and linearly interpolates neighborhood patch features.
result Demonstrates effectiveness of Pani in both supervised and semi-supervised settings.
In this paper we consider the task of estimating the non-zero pattern of the sparse inverse covariance matrix of a zero-mean Gaussian random vector from a set of iid samples. Note that this is also equivalent to recovering the underlying graph structure of a sparse Gaussian Markov Random Field (GMRF). We present two no…
EAGLE improves reproducibility and stability of model explanations.
problem Creating reliable explanations for opaque machine learning models.
method Formulates perturbation selection as an information-theoretic active learning problem.
result EAGLE learns a linear surrogate model with feature importance scores and uncertainty estimates.
Spectral analysis of neighborhood graphs is one of the most widely used techniques for exploratory data analysis, with applications ranging from machine learning to social sciences. In such applications, it is typical to first encode relationships between the data samples using an appropriate similarity function. Popul…
Proposes BGCN-NRWS for semi-supervised node classification with reduced overfitting.
problem Uncertainty in graph structure for semi-supervised node classification.
method Bayesian Graph Convolutional Network using Neighborhood Random Walk Sampling (BGCN-NRWS) with MCMC graph sampling and variational inference.
result Consistently competitive classification results compared to state-of-the-art.
Study statistical guarantees for DRO with OT and OT-regularized divergences.
problem Enhancing adversarial robustness in machine learning models.
method Derive concentration inequalities for supervised learning via DRO-based adversarial training.
result First to cover soft-constraint costs and reweighting mechanisms in adversarial training.
Proposes a measure to predict generalization in non-matching environments.
problem Characterizing and comparing generalization of machine learning models in non-matching environments.
method Neighborhood invariance measure, calculating invariance as the largest fraction of transformed points classified into the same class.
result Strong and robust correlation between neighborhood invariance and actual out-of-domain generalization.
In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate…
Markov networks are widely studied and used throughout multivariate statistics and computer science. In particular, the problem of learning the structure of Markov networks from data without invoking chordality assumptions in order to retain expressiveness of the model class has been given a considerable attention in t…
New method samples triplets from data distributions for training Triplet networks.
problem Training robust Triplet networks with discriminative triplets.
method Bayesian updating of multivariate normal distributions for dynamic class embedding sampling.
result Experimental validation on MNIST and histopathology CRC datasets shows effectiveness of the proposed method.
We derive spectral sequences for the intersection homology of stratified fibrations and approximate tubular neighborhoods in manifold stratified spaces. These neighborhoods include regular neighborhoods in PL stratified spaces.
SNG-DBSCAN clusters data faster with subsampled similarity queries.
problem Efficiently clustering large datasets with DBSCAN's high complexity.
method Subsampled ε-neighborhood graph for similarity queries. result Subsampling 0.1% of the graph leads to 200x speedup and 250x RAM reduction. Making an adaptive prediction based on one's input is an important ability for general artificial intelligence. In this work, we step forward in this direction and propose a semi-parametric method, Meta-Neighborhoods, where predictions are made adaptively to the neighborhood of the input. We show that Meta-Neighborhood…
Sampling random points can reveal submanifold topology.
problem Estimating the topology of submanifolds in Riemannian manifolds.
method Sampling random points in a neighborhood of the submanifold.
result Topology of the submanifold can be recovered with high confidence.
Data-driven neighborhood definitions and graph constructions are often used in machine learning and signal processing applications. k-nearest neighbor~(kNN) and ε-neighborhood methods are among the most common methods used for neighborhood selection, due to their computational simplicity. However, the choice of param…
KSS method converges and recovers correct clustering under certain conditions.
problem Subspace clustering for semi-randomly sampled data.
method Local convergence analysis and recovery guarantee for KSS method.
result KSS method converges superlinearly and finds correct clustering within loglog N iterations.
New algorithm for learning RBMs with sparse latent variables.
problem Learning RBMs with sparse latent variables efficiently.
method Algorithm with time complexity O(n^(2^s+1)) for sparse RBMs.
result Improves learning time for RBMs with sparse latent variables.
Study geodesics entering a fixed cusp neighborhood multiple times.
problem Understanding geodesics entering a specific cusp neighborhood multiple times.
method Investigate reciprocal geodesics entering a fixed cusp neighborhood a fixed number of times.
result Characterized the class of reciprocal geodesics entering a fixed cusp neighborhood a fixed number of times.
Urban2Vec combines street view imagery and POIs for better urban neighborhood embeddings.
problem Lack of comprehensive representation of urban neighborhoods using heterogeneous data.
method Unsupervised multi-modal framework using CNN for visual features and bag-of-words for POI data.
result Urban2Vec achieves better performance than baseline models and comparable to fully-supervised methods.
Paper analyzes convergence of Adam-type RL algorithms under Markovian sampling.
problem Theoretical convergence analysis of Adam-type RL algorithms.
method Develops techniques for analyzing convergence under Markovian sampling.
result PG-AMSGrad and TD-AMSGrad converge to stationary points or global optima at specified rates.
We present a neighborhood similarity layer (NSL) which induces appearance invariance in a network when used in conjunction with convolutional layers. We are motivated by the observation that, even though convolutional networks have low generalization error, their generalization capability does not extend to samples whi…
We study model recovery for data classification, where the training labels are generated from a one-hidden-layer neural network with sigmoid activations, also known as a single-layer feedforward network, and the goal is to recover the weights of the neural network. We consider two network models, the fully-connected ne…
Skeleta and other pure subsets of manifold stratified spaces are shown to have neighborhoods which are teardrops of stratified approximate fibrations (under dimension and compactness assumptions). In general, the stratified approximate fibrations cannot be replaced by bundles, and the teardrops cannot be replaced by ma…
We study clustering algorithms based on neighborhood graphs on a random sample of data points. The question we ask is how such a graph should be constructed in order to obtain optimal clustering results. Which type of neighborhood graph should one choose, mutual k-nearest neighbor or symmetric k-nearest neighbor? What …
New framework distinguishes knots via neighborhood invariants.
problem Distinguishing knots and knotoids.
method Study of knotoid spectra and neighborhood invariants.
result Neighborhood invariants can distinguish knots of higher Gordian distance.
This paper tackles selection bias in recommender systems by considering the neighborhood effect.
problem Selection bias in recommender systems due to filtering and user selection.
method Formalizes neighborhood effect as interference problem, introduces treatment representation, and proposes ideal loss.
result Proposed methods achieve unbiased learning when both selection bias and neighborhood effect are present.
Maximally hyperbolic solutions contain future neighborhoods of intersecting hypersurfaces.
problem Maximally globally hyperbolic solutions of higher-dimensional vacuum Einstein equations.
method Analyzing intersections of characteristic hypersurfaces.
result Contains a future neighborhood of intersecting hypersurfaces.
Many prediction problems can be phrased as inferences over local neighborhoods of graphs. The graph represents the interaction between entities, and the neighborhood of each entity contains information that allows the inferences or predictions. We present an approach for applying machine learning directly to such graph…
Proposes a new NMF method incorporating neighborhood structure for better anomaly detection.
problem NMF's inability to incorporate neighborhood structure information limits its performance in nonlinear manifold structures.
method Integrates neighborhood structure information using Minimum Spanning Tree (MST) within NMF framework.
result Empirical results show superior performance in anomaly detection using the proposed method.
Study on transverse knots and their neighborhoods, proving unique standard neighborhoods and destabilization results.
problem Understanding the structure and properties of transverse knots and their neighborhoods.
method Proves unique standard neighborhoods and structure theorems for non-loose Legendrian knots through destabilization results.
result Finds a manifold with infinite tight contact structures, up to contactomorphism, without Giroux torsion.
Private KL distribution estimation improved with instance-optimality.
problem Minimizing KL divergence between true and estimated distributions.
method Construct minimax optimal private estimators, then focus on instance-optimality.
result Achieved instance-optimality up to constant factors for KL estimation.
The paper shows cross-validation fails in learning Gaussian graphical model structures.
problem Cross-validation's failure in learning Gaussian graphical model structures.
method Finite-sample bounds on misidentification probability of Lasso estimator.
result Cross-validation is inconsistent for learning Gaussian graphical model structures.
The likelihood function is a fundamental component in Bayesian statistics. However, evaluating the likelihood of an observation is computationally intractable in many applications. In this paper, we propose a non-parametric approximation of the likelihood that identifies a probability measure which lies in the neighbor…
Revises GNN neighborhood aggregation for more accurate node classification.
problem Flaws in benchmark GNN models for node classification.
method Statistical signal processing approach to neighborhood aggregation.
result Novel insights for designing more efficient GNN models.
The study proves a neighborhood theorem for mean curvature flow in higher dimensions.
problem Proving a canonical neighborhood theorem for mean curvature flow in higher dimensions.
method Proved a canonical neighborhood theorem for mean curvature flow of compact submanifolds in RN with a pinching condition. result Proved a canonical neighborhood theorem for mean curvature flow in dimensions n≥5. A neighborhood homotopy is an equivalence relation on spatial graphs which is generated by crossing changes on the same component and neighborhood equivalence. We give a complete classification of all 2-component spatial graphs up to neighborhood homotopy by the elementary divisor of a linking matrix with respect to th…
GraphAIR improves graph representation learning by capturing non-linear interactions.
problem Challenges in capturing non-linear interactions in graph data.
method Integrates neighborhood aggregation and interaction modeling.
result Demonstrates improved performance on node classification and link prediction tasks.
Develops an online Gaussian process method that maintains convergence guarantees without sample complexity issues.
problem The computational intractability of Gaussian processes with streaming data.
method Parsimonious Online Gaussian Processes (POG) that maintains asymptotic consistency with bounded memory.
result POG preserves convergence guarantees to the population posterior with finite memory, even for constant error radius.
New method HNCI for evaluating treatment effects in network interference.
problem Evaluating the effectiveness of treatments or policies under network interference.
method High-dimensional network causal inference (HNCI) using linear regression with latent homogeneity.
result Valid confidence intervals and sets for average direct treatment effect and neighborhood size.
In this paper, we consider recommender systems with side information in the form of graphs. Existing collaborative filtering algorithms mainly utilize only immediate neighborhood information and have a hard time taking advantage of deeper neighborhoods beyond 1-2 hops. The main caveat of exploiting deeper graph informa…