These notes review six lectures given by Prof. Andrea Montanari on the topic of statistical estimation for linear models. The first two lectures cover the principles of signal recovery from linear measurements in terms of minimax risk. Subsequent lectures demonstrate the application of these principles to several pract…
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 “clique recovery”
Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversariescs.CC
Paper shows statistical-computational gaps in learning sparse mixtures and robust estimation.
problem Statistical-computational gaps in learning sparse mixtures and robust estimation.
method Average-case reduction techniques, Imbalanced Sparse Gaussian Mixtures, and algorithmic change of measure.
result New hardness results for robust sparse mean estimation, semirandom planted dense subgraph, and universality principle for sparse mixture problems.
Compressive Network Analysisstat.ML
Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for …
Cakewalk Samplingstat.ML
Adaptive sampling improves finding good local optima in combinatorial optimization.
problem Finding good local optima in NP-hard combinatorial optimization problems.
method Derive a robust learning algorithm to adapt sampling distributions towards good local optima.
result Adaptive sampling outperforms related methods in recovering locally maximal cliques and k-medoid clustering.
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…
The maximum number of maximum cliques in a graph is determined for graphs with at least 15 vertices.
problem Determining the maximum number of maximum cliques in a graph with n vertices.
method Defining prime and composite graphs, analyzing edge bounds, and using combinatorial arguments.
result For graphs with at least 15 vertices, the graph with the maximum number of maximum cliques is composite.
Unified method detects and localizes anomalous cliques in inhomogeneous networks.
problem Detect and localize anomalous cliques in inhomogeneous networks.
method Unified method based on egonets for detection and localization.
result Unified method can detect and localize anomalous cliques in inhomogeneous networks.
Paper explores embedding methods for detecting pseudo-cliques in random graphs, showing limitations and potential.
problem Detecting planted pseudo-cliques in random dot product graphs.
method Adjacency Spectral Embedding (ASE) and Graph Encoder Embedding (GEE).
result These methods can localize pseudo-cliques with additional clean network data, but not without it.
Solves partial assignment problems using random clique complexes.
problem Partial assignment problems, especially with severe occlusions and distortions.
method Formulate as matching random clique complexes, analyze k-skeletons, match adjacency matrices, consider geometric neighbourhoods.
result Outperforms diverse matching algorithms significantly.
Infinite clique of rays in plane minus Cantor set.
problem Understanding the mapping class group of plane minus Cantor set.
method Using a graph of loops and cliques of high-filling rays.
result Construction of an infinite clique of high-filling rays.
Estimates joint probability distribution from 1-way marginals using low-rank tensors and random projections.
problem Nonparametric estimation of joint probability mass function (PMF) from limited data.
method Low-rank tensor decomposition and random projections to link data to PMF estimation.
result Estimates joint density from 1-way marginals using transformed space and novel algorithm.
Novel Machine Learning Algorithms for Centrality and Cliques Detection in Youtube Social Networkscs.LG
Research uses machine learning to find central nodes and cliques in YouTube social networks.
problem Identifying central nodes and cliques in YouTube social networks.
method Unsupervised machine learning, Python programming, Bron-Kerbosch algorithm.
result Successfully found central nodes through clique-centrality and degree centrality.
A novel approach selects EEGs for better brain disease diagnosis.
problem Invalid/noisy EEGs degrade diagnosis performance.
method mwcEEGs: maximum weight clique-based approach.
result Improves classification performance by selecting intra-clique and inter-clique EEGs.
Paper explores limits of high-order clustering with planted structures.
problem Statistical and computational limits of high-order clustering with planted structures.
method Developed methods for detection and recovery of clusters, identified signal-to-noise ratio boundaries.
result Sharp boundaries of signal-to-noise ratio for statistical and computational feasibility.
Tackles the computational hardness of HPC detection, conjecturing equivalence to PC detection.
problem Computational hardness of hypergraphic planted clique detection.
method No specific method mentioned; focuses on conjecturing equivalence.
result Equivalence of computational hardness between HPC and PC detection.
Improved Graph Clusteringstat.ML
Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model…
We introduce Clique Matrices as an alternative representation of undirected graphs, being a generalisation of the incidence matrix representation. Here we use clique matrices to decompose a graph into a set of possibly overlapping clusters, de ned as well-connected subsets of vertices. The decomposition is based on a s…
Sublinear algorithms detect cliques in graphs with high probability.
problem Detecting a planted clique in random graphs efficiently.
method Non-adaptive low-degree polynomial queries of adjacency matrix entries.
result Sublinear time detection is possible for a specific range of clique sizes.
New insights link diverse statistical problems via secret leakage planted clique.
problem Statistical-computational gaps in inference problems.
method Secret leakage planted clique as a new hardness assumption for reductions.
result Establishes tight statistical-computational tradeoffs for various problems.
Bayesian method for high-dimensional categorical data analysis.
problem Difficulties in probability modeling for high-dimensional data.
method Bayesian learning of clique tree structure.
result Optimal clique tree structure for probability modeling.
Proposes clique pooling for graph classification.
problem Graph classification challenges.
method Clique-based graph pooling within GCN and GraphSAGE.
result Competitive performance on graph classification benchmarks.
Learning Clique Forestsstat.ML
MFCF algorithm learns conditional dependency structure from sparse data.
problem Learning conditional dependency structure from sparse and noisy data.
method Repeated application of clique expansion to produce clique forest and MRF.
result MFCF outperforms Graphical Lasso for covariance selection models.
Develops a method to efficiently learn causal DAGs using directed clique trees.
problem Efficiently learning causal DAGs in the presence of large cliques.
method Decomposes DAGs into independently orientable components using directed clique trees and designs a two-phase intervention algorithm.
result Proves that the number of single-node interventions necessary to orient any DAG in an EC is at least the sum of half the size of the largest cliques in each chain component of the essential graph.
Paper explores limits of graph property testing in Ising models.
problem Understanding information-theoretic limits of graph property testing in Ising models.
method Combinatorial constructs and correlation-based tests.
result Property testing is more challenging for general Ising models than ferromagnets.
A tutorial on using MDL for graph analysis, focusing on clique size.
problem Analyzing the size of the largest clique in graphs.
method MDL principle applied to graph analysis.
result Interpretation of MDL results and common pitfalls.
Artin groups not free of infinity are shown to have finite centers.
problem Characterizing Artin groups with finite centers.
method Reduced clique-cube complexes and actions on them.
result Artin groups not free of infinity have finite centers, and are trivial in many cases.
Study evaluates methods for expanding communities in hypergraphs using random walks.
problem Expanding communities in hypergraphs using random walks.
method Clique-expansion and tensor methods evaluated; hybrid method proposed.
result Parameter regimes identified where methods outperform each other.
In financial markets, abnormal trading behaviors pose a serious challenge to market surveillance and risk management. What is worse, there is an increasing emergence of abnormal trading events that some experienced traders constitute a collusive clique and collaborate to manipulate some instruments, thus mislead other …
We introduce community trees to summarize network structures.
problem Stability of community structures in networks.
method Clique percolation method (CPM) and persistent diagrams.
result Total star number (TSN) provides an upper bound on community tree changes.
Discover novel multivariate relationships in time series data.
problem Capturing novel relationships between time series in complex systems.
method Introducing multipoles as linear relationships among more than two time series, identifying them as cliques of negative correlations in a correlation network.
result Almost all multipoles can be efficiently found using a clique-enumeration approach.
Maximal knotless graphsmath.GT
Maximal knotless graphs have at least 74% of their vertices' edges.
problem Characterizing maximal knotless graphs and understanding their edge constraints.
method Analyzing edge maximality and constructing graphs to meet constraints.
result There exists an infinite family of maximal knotless graphs with fewer edges than previously thought.
Estimates log-concave densities in graphical models using tent functions.
problem Maximum likelihood estimation of log-concave densities in undirected graphs.
method MLE as product of tent functions corresponding to maximal cliques.
result MLE can be found via convex optimization.
New algorithm finds minimal causal models for complex latent variables.
problem Learning causal structure in presence of latent variables and measurement dependencies.
method Graph theoretic edge clique cover problem, non-parametric algorithm.
result Minimality in minimal causal models implies specific properties.
We introduce a new embarrassingly parallel parameter learning algorithm for Markov random fields with untied parameters which is efficient for a large class of practical models. Our algorithm parallelizes naturally over cliques and, for graphs of bounded degree, its complexity is linear in the number of cliques. Unlike…
Proposes CLIQUE for improved local variable importance in multi-class classification.
problem Lack of methods to characterize local structure in model loss space.
method CLIQUE (Conditional Local Importance by Quantile Expectations)
result CLIQUE emphasizes locally dependent information and captures interaction behavior.
We construct a partial order relation which acts on the set of 3-cliques of a maximal planar graph G and defines a unique hierarchy. We demonstrate that G is the union of a set of special subgraphs, named `bubbles', that are themselves maximal planar graphs. The graph G is retrieved by connecting these bubbles in a tre…
The study shows acylindrical hyperbolicity for Artin groups not associated with joins or cones.
problem Proving acylindrical hyperbolicity for Artin groups of infinite type not associated with joins or cones.
method Developing and extending the clique-cube complex and action studies of Charney and Morris-Wright.
result Acylindrical hyperbolicity demonstrated for Artin groups of infinite type associated with graphs that are not cones.
As a model problem for clustering, we consider the densest k-disjoint-clique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized. We establish that such subgraphs can be recovered from the solution of a particular semidefinite re…
We consider two closely related problems: planted clustering and submatrix localization. The planted clustering problem assumes that a random graph is generated based on some underlying clusters of the nodes; the task is to recover these clusters given the graph. The submatrix localization problem concerns locating hid…
Constrained speaker linkingstat.ML
In this paper we study speaker linking (a.k.a.\ partitioning) given constraints of the distribution of speaker identities over speech recordings. Specifically, we show that the intractable partitioning problem becomes tractable when the constraints pre-partition the data in smaller cliques with non-overlapping speakers…
Deep nets learn structured densities without dimensionality issues.
problem Learning structured densities in high dimensions.
method Simple -minimizing loss for neural networks.
result Dimension-independent convergence rates for neural networks.
Paper calculates Gromov-Hausdorff distance between simplexes and 2-distance spaces.
problem Calculating Gromov-Hausdorff distance between simplexes and 2-distance spaces.
method Formulas derived for clique covering number and chromatic number of graphs.
result Complete solution to generalized Borsuk problem for 2-distance spaces.
We say a graph has property when it is an induced subgraph of the curve graph of a surface of genus with punctures. Two well-known graph invariants, the chromatic and clique numbers, can provide obstructions to . We introduce a new invariant of a graph, the 'nested complex…
Reduces average-case complexity of sparse PCA from weak PC conjectures.
problem Characterizing the average-case complexity of sparse PCA.
method Reduction from planted clique conjecture to spiked covariance model.
result First full characterization of computational barrier in spiked covariance model, providing tight lower bounds at all sparsities.
A new hypergraph-based active learning scheme reduces query complexity.
problem Efficiently querying and learning from complex hypergraph structures.
method Developed a novel hypergraph-based active learning scheme that can handle both pointwise and pairwise queries.
result Demonstrated that requires significantly fewer queries than a previously used graph-based method .
The Cartesian subgroup in graph products of groups is studied with bounds and algorithms.
problem Understanding the structure of Cartesian subgroups in graph products of groups.
method Theory of polyhedral products, lower and upper bounds, algorithm for small presentations.
result Bounds on the number of relations and deficiency in presentations of Cartesian groups.
Given a large data matrix , we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution , or instead contains a principal submatrix whose entries have marginal distribution . As …
Counts and samples DAGs equivalent to a ground truth DAG.
problem Identifying the number and structure of DAGs equivalent to a ground truth DAG.
method Clique tree representation of chordal graphs for counting and sampling.
result Polynomial time algorithm for counting and sampling in bounded degree graphs.