We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a cor…
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.
168,742 papers · 148 categories
Trend · papers per month
48 results for “graph recovery”
Paper explores exact recovery of communities in weighted graphs using Gaussian and exponential distributions.
problem Exact recovery of communities in weighted graphs with Gaussian and exponential distributions.
method Introduces a new semi-metric to describe conditions for exact recovery and analyzes conditions for both complete and incomplete graphs.
result Necessary and sufficient conditions for exact recovery are asymptotically tight and applicable to both complete and incomplete graphs.
Paper proposes a novel graph recovery attack from node embeddings.
problem Privacy risks of integrating graph embeddings with machine learning pipelines.
method Model-agnostic graph recovery attack exploiting preserved structural information in node embeddings.
result Adversaries can recover graph edges with decent accuracy from node embeddings alone.
Partial recovery of node mappings between correlated graphs is possible under specific conditions.
problem Recovering a one-to-one mapping between nodes of two correlated graphs with a fraction of correct matches.
method Analyzing the graph isomorphism problem as a noisy version, considering Erdős-Rényi graphs, and providing conditions for partial recovery.
result Necessary and sufficient conditions for partial recovery of node mappings in correlated graphs are given.
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…
Study recovers community structure from coarse graph measurements.
problem Community recovery from low-resolution graph measurements.
method Formalized coarsening process of graph measurements, developed conditions for perfect recovery.
result Simple and closed-form asymptotic conditions for perfect recovery of coarse graph communities.
This work aims at recovering signals that are sparse on graphs. Compressed sensing offers techniques for signal recovery from a few linear measurements and graph Fourier analysis provides a signal representation on graph. In this paper, we leverage these two frameworks to introduce a new Lasso recovery algorithm on gra…
The paper tracks patient recovery using graphs of joint movement data.
problem Tracking individual patient recovery trajectories in physical therapy.
method Bayesian learning of Random Geometric Graphs from joint movement data.
result Optimal exercise routines can be recommended based on patient recovery data.
Improves graph recovery in Gaussian graphical modeling.
problem Calibrating regularization parameters for graph recovery.
method Thresholded adaptive validation applied to graphical lasso.
result Thresholding pipeline improves graph recovery.
We study graph matching with correlated Gaussian features and find thresholds for exact recovery.
problem Graph matching with correlated Gaussian features.
method Information-theoretic thresholds and conditions for exact and almost exact recovery.
result Contextual information introduces a richer structure, with thresholds for exact and almost exact recovery no longer coinciding.
In this paper, we consider the problem of estimating the underlying graph associated with an Ising model given a number of independent and identically distributed samples. We adopt an \emph{approximate recovery} criterion that allows for a number of missed edges or incorrectly-included edges, in contrast with the widel…
Detection of dense cycles in graphs reveals a gap between easy detection and hard recovery.
problem Detecting and recovering dense cycles in Erdős-Rényi graphs.
method Characterization of computational thresholds for detection and recovery using low-degree polynomial algorithms.
result A gap exists between the detection and recovery thresholds for certain parameter regimes.
Researchers prove it's impossible to partially recover graph alignments in certain conditions.
problem Recovering vertex correspondence between two random graphs with correlated edges.
method Used the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.
result Proved an impossibility result for partial recovery in the sparse regime with constant average degree and correlation.
This paper sets thresholds for recovering vertex correspondences in partially correlated graphs.
problem Recovering hidden vertex correspondences in partially correlated graphs.
method Proposed partially correlated Erdős-Rényi graphs model; information-theoretic thresholds; correlated functional digraphs.
result Optimal rates for partial and exact recovery of vertex correspondences.
New method recovers graph latent positions under edge differential privacy.
problem Recovering latent graph information from privatized graphs.
method Applying geometric insights to adjust statistical inference for privatized graphs.
result Achieves consistent recovery of latent positions under local edge differential privacy constraints.
NGRs merge sparse graph recovery with PGMs for efficient probabilistic inference.
problem Efficiently recover sparse graphs and learn distributions over variables.
method Integrates sparse graph recovery methods with PGMs using Graph-constrained path norm.
result NGRs can handle multimodal data and perform sparse graph recovery and probabilistic inference.
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.
Motivated by applications such as discovering strong ties in social networks and assembling genome subsequences in biology, we study the problem of recovering a hidden -nearest neighbor (NN) graph in an -vertex complete graph, whose edge weights are independent and distributed according to for edges in the…
Paper models graph edge dependencies using latent variables for community detection.
problem Graphs' edge dependencies not fully explained by community membership.
method Introduces auxiliary latent variables to model edge dependencies and analyzes conditions for exact recovery.
result Exact recovery possible by semidefinite programming down to maximum likelihood threshold.
Study exact community recovery in noisy SBM with limited queries.
problem Community recovery in noisy stochastic block models with limited queries.
method Balanced uniform querying, two-stage adaptive strategy, sublinear queries, subsampled graph.
result Adaptive querying can improve exact recovery limits in noisy SBM.
Graph matching with feature vectors is solved using a two-layer graph neural network.
problem Graph matching in the presence of sparse binary features.
method Two-layer graph neural network with graph structure.
result Graph neural network can recover correct mapping with high probability under certain conditions.
Continuous vector representations of words and objects appear to carry surprisingly rich semantic content. In this paper, we advance both the conceptual and theoretical understanding of word embeddings in three ways. First, we ground embeddings in semantic spaces studied in cognitive-psychometric literature and introdu…
New algorithm achieves almost exact graph matching in almost quadratic time.
problem Graph matching under correlated Erdős-Rényi models.
method Rank-based graph matching using local tree correlation tests.
result Achieves almost exact recovery in almost quadratic time complexity.
From Observation to Orientation: an Adaptive Integer Programming Approach to Intervention Designcs.LG
Adaptive IP approach optimizes intervention design for causal graph recovery.
problem Designing efficient interventions to recover causal relationships from data.
method Iterative integer programming approach for optimizing information gain.
result Adaptive IP approach achieves full causal graph recovery with fewer interventions.
Paper studies vertex correspondence recovery in correlated graphs with node features.
problem Recovering hidden vertex correspondence between two correlated graphs with observed edge weights and node features.
method Introduced featured correlated Gaussian Wigner model and proposed QPAlign algorithm for quadratic programming relaxation.
result Characterized optimal information-theoretic thresholds for exact and partial recovery of latent mapping.
Spectral clustering for geometric graphs achieves strong consistency in community recovery.
problem Community recovery in dense geometric graphs.
method Spectral clustering algorithm using eigenvectors of adjacency matrix.
result Strong consistency in community recovery proved.
Researchers prove inner product recovery is impossible in latent space models.
problem Recovering inner products in latent space models with random geometric graphs.
method Rate-distortion theory applied to Gaussian or spherical latent locations.
result Impossible to recover inner products if dimensionality exceeds , matching positive results' conditions.
The stochastic block model (SBM) is a random graph model with different group of vertices connecting differently. It is widely employed as a canonical model to study clustering and community detection, and provides a fertile ground to study the information-theoretic and computational tradeoffs that arise in combinatori…
This paper tackles exact recovery of clusters in a stochastic Ising model on a SBM graph.
problem Recovering clusters in a stochastic Ising model on a SBM graph.
method Proposes a Stochastic Ising Block Model (SIBM) and establishes a sharp threshold for exact recovery.
result Sharp threshold for exact recovery of clusters in SIBM, with time complexity for .
This work studies the denoising of piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness over a graph, where the value at each node can be vector-valued. We extend the graph trend filtering framework to denoising vector-valued graph signals with a family of non-convex regularizers, which exhibi…
This paper considers regression tasks involving high-dimensional multivariate processes whose structure is dependent on some {known} graph topology. We put forth a new definition of time-vertex wide-sense stationarity, or joint stationarity for short, that goes beyond product graphs. Joint stationarity helps by reducin…
Paper tackles community recovery in binary symmetric SBM graphs.
problem Community detection in binary symmetric SBM graphs.
method Proposes a two-stage iterative method using projected power iterations and orthogonal iterations.
result Proposed method can exactly recover communities with high probability in logarithmic sparsity regime.
LogSpecT learns graphs from stationary signals without infeasibility issues.
problem Infeasibility of SpecT model for graph learning from stationary signals.
method Design of LogSpecT and rLogSpecT models with recovery guarantees.
result rLogSpecT is always feasible and provides recovery guarantees.
The paper infers multiple graphs from stationary signals on them.
problem Inferring multiple graphs from signals observed on their nodes.
method Convex optimization method leveraging matrix polynomial commutation.
result High-probability bounds on recovery error provided.
This paper is concerned with jointly recovering node-variables from a collection of pairwise difference measurements. Imagine we acquire a few observations taking the form of ; the observation pattern is represented by a measurement graph with an ed…
New bounds for convex clustering under graph connectivity.
problem Understanding clustering performance under different graph connectivity structures.
method Random walks and concentration inequalities for random graph models.
result Improved rates of convergence for centroid recovery.
Proposes methods to recover labels from shuffled networks using graph averages.
problem Recovering labels from a shuffled network using graph averages.
method Cluster networks into classes, then match the new graph to cluster-averages, minimizing the graph matching objective function.
result Higher fidelity matching performance when clustering networks into different classes.
This paper explores the information-theoretic limitations of graph property testing in zero-field Ising models. Instead of learning the entire graph structure, sometimes testing a basic graph property such as connectivity, cycle presence or maximum clique size is a more relevant and attainable objective. Since property…
Neural node embeddings have recently emerged as a powerful representation for supervised learning tasks involving graph-structured data. We leverage this recent advance to develop a novel algorithm for unsupervised community discovery in graphs. Through extensive experimental studies on simulated and real-world data, w…
The paper tackles partial inference in structured prediction using a convex optimization approach.
problem Maximizing a score function with unary and pairwise potentials in graph label spaces.
method Generative model approach with two-stage convex optimization for label recovery.
result Conditions for recovering a majority of labels with provable guarantees.
Paper uses SDP for community detection with side information.
problem Community detection in graphs with additional non-graph data.
method Formulates SDP relaxation for maximum likelihood node labeling with side information.
result SDP achieves same exact recovery threshold as maximum likelihood with side information.
In the Network Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascad…
Study spectral properties of sparse random graphs to recover latent vectors.
problem Recovering latent vectors in sparse random geometric graphs.
method Analyzes spectral concentration and uses orthogonal polynomial expansions, decoupling, and matrix concentration.
result Sharpens spectral norm bounds and proves exact recovery for Gaussian mixture models.
Improved sample efficiency in learning sparse Ising models.
problem Learning the graph of a sparse Ising model with limited samples.
method Combining L0 and L2 norms to induce sparsity and model non-zero coefficients.
result Improved sample complexity, achieving new state-of-the-art recovery guarantees.
We analyze directed, unweighted graphs obtained from by connecting vertex to iff . Examples of such graphs include -nearest neighbor graphs, where varies from point to point, and, arguably, many real world graphs such as co-purchasing graphs. We ask whethe…
uGLAD recovers sparse graphs from data using deep unrolled networks.
problem Sparse graph recovery from complex data.
method Optimizing deep unrolled networks to learn precision matrices.
result uGLAD outperforms existing algorithms in sparsity optimization and robustly handles missing data.
Paper introduces HGSL for heterogeneous graphs, improving edge type and weight recovery.
problem Learning structure in heterogeneous graphs with multiple node and edge types.
method Proposes H2MN model for DGPs and derives alternating optimization method.
result Demonstrates superior performance on synthetic and real-world datasets.
Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and…