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.
The paper introduces a sampling theory for graphons with a Poincaré inequality and proves consistency.
The study proves sampling-based GNNs can approximate training on full graphs with small subgraphs.
We study signal recovery on graphs based on two sampling strategies: random sampling and experimentally designed sampling. We propose a new class of smooth graph signals, called approximately bandlimited, which generalizes the bandlimited class and is similar to the globally smooth class. We then propose two recovery s…
A framework for hypothesis testing on attributed graphs using sampling.
SteinGen generates diverse graph samples from a single example.
New sampling methods improve node embedding efficiency.
New method improves graph neural networks by considering different types of relations in sampling.
A new model for graph sampling that preserves structure without explicit targeting.
New graph properties inherited by Frechet mean and median.
New method uses CNNs to estimate graph means.
We describe the first sub-quadratic sampling algorithm for the Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample sm…
New model learns from random graph samples to estimate graph parameters.
We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, …
Graph Convolutional Networks (GCNs) are powerful models for learning representations of attributed graphs. To scale GCNs to large graphs, state-of-the-art methods use various layer sampling techniques to alleviate the "neighbor explosion" problem during minibatch training. We propose GraphSAINT, a graph sampling based …
BLISS optimizes GNN training by adaptively sampling nodes.
Graphs from features improve classification accuracy in tasks.
Study on sample complexity for pure exploration in feedback graph settings.
Graph neural Thompson Sampling improves online decision-making for graph data.
Graph Laplace operators uniquely identify metrics and densities on manifolds.
It has been shown recently that graph signals with small total variation can be accurately recovered from only few samples if the sampling set satisfies a certain condition, referred to as the network nullspace property. Based on this recovery condition, we propose a sampling strategy for smooth graph signals based on …
One of the most fundamental concepts in statistics is the concept of sample mean. Properties of the sample mean that are well-defined in Euclidean spaces become unwieldy or even unclear in graph spaces. Open problems related to the sample mean of graphs include: non-existence, non-uniqueness, statistical inconsistency,…
New graph representation learning network improves scalability and feature integration.
Sampling is a fundamental topic in graph signal processing, having found applications in estimation, clustering, and video compression. In contrast to traditional signal processing, the irregularity of the signal domain makes selecting a sampling set non-trivial and hard to analyze. Indeed, though conditions for graph …
SANS uses graph structure to find meaningful negatives for entity and relation embeddings.
Proposes BGCN-NRWS for semi-supervised node classification with reduced overfitting.
Active graph-based semi-supervised learning (AG-SSL) aims to select a small set of labeled examples and utilize their graph-based relation to other unlabeled examples to aid in machine learning tasks. It is also closely related to the sampling theory in graph signal processing. In this paper, we revisit the original fo…
We consider the problem of offline, pool-based active semi-supervised learning on graphs. This problem is important when the labeled data is scarce and expensive whereas unlabeled data is easily available. The data points are represented by the vertices of an undirected graph with the similarity between them captured b…
A method to uniformly sample graph-encoded surfaces of fixed size.
Sharp threshold found for Frechet mean of inhomogeneous graphs.
Distributed Thompson sampling improves regret convergence in constrained communication networks.
GraphBSI generates graphs by refining a belief in continuous space, outperforming existing models.
Network sampling is integral to the analysis of social, information, and biological networks. Since many real-world networks are massive in size, continuously evolving, and/or distributed in nature, the network structure is often sampled in order to facilitate study. For these reasons, a more thorough and complete unde…
We consider the problem of providing nonparametric confidence guarantees for undirected graphs under weak assumptions. In particular, we do not assume sparsity, incoherence or Normality. We allow the dimension to increase with the sample size . First, we prove lower bounds that show that if we want accurate infe…
We consider the problem of vertex classification for graphs constructed from the latent position model. It was shown previously that the approach of embedding the graphs into some Euclidean space followed by classification in that space can yields a universally consistent vertex classifier. However, a major technical d…
Graph convolutional networks (GCNs) have recently received wide attentions, due to their successful applications in different graph tasks and different domains. Training GCNs for a large graph, however, is still a challenge. Original full-batch GCN training requires calculating the representation of all the nodes in th…
Unified framework for adaptive connection sampling in GNNs improves performance and robustness.
Graph diffusion processes approximate manifold heat semigroups using graph transition matrices.
We analyze the sample complexity of learning graphical games from purely behavioral data. We assume that we can only observe the players' joint actions and not their payoffs. We analyze the sufficient and necessary number of samples for the correct recovery of the set of pure-strategy Nash equilibria (PSNE) of the true…
Learning properties of large graphs from samples has been an important problem in statistical network analysis since the early work of Goodman \cite{Goodman1949} and Frank \cite{Frank1978}. We revisit a problem formulated by Frank \cite{Frank1978} of estimating the number of connected components in a large graph based …
Many popular dimensionality reduction procedures have out-of-sample extensions, which allow a practitioner to apply a learned embedding to observations not seen in the initial training sample. In this work, we consider the problem of obtaining an out-of-sample extension for the adjacency spectral embedding, a procedure…
This short note aims at (re)proving that the symmetrically normalized graph Laplacian $L=\Id - D^{-1/2}WD^{-1/2}$ (from a graph defined from a Gaussian weighting kernel on a sampled smooth manifold) converges towards the continuous Manifold Laplacian when the sampling become infinitely dense. The convergence rate with …
New guarantees for matrix completion from any deterministic sampling patterns.
For a graph representation of a dataset, a straightforward normality measure for a sample can be its graph degree. Considering a weighted graph, degree of a sample is the sum of the corresponding row's values in a similarity matrix. The measure is intuitive given the abnormal samples are usually rare and they are dissi…
Recent advancements in deep neural networks for graph-structured data have led to state-of-the-art performance on recommender system benchmarks. In this work, we present a Graph Convolutional Network (GCN) algorithm SWAG (Sample Weight and AGgregate), which combines efficient random walks and graph convolutions on weig…
Graph Energy Matching improves generation quality for molecular graphs.
New insights into negative sampling for graph representation learning.
Neighborhood sampling affects graph neural network training outcomes.
Unified interpretation of softmax cross-entropy and negative sampling for knowledge graph embedding.