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.
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.
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.
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.
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.
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.
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 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…
In this paper, we consider the multivariate Bernoulli distribution as a model to estimate the structure of graphs with binary nodes. This distribution is discussed in the framework of the exponential family, and its statistical properties regarding independence of the nodes are demonstrated. Importantly the model can e…
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…
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.
Efficient algorithm for self-directed learning of convex clusters on graphs.
problem Self-directed classification of nodes on graphs with convex clusters.
method Developed efficient algorithms for (geodesically) convex clusters on graphs.
result Polynomial runtime algorithm with 3(h(G)+1)4lnn mistakes for graphs with two convex clusters. 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 L2-minimizing loss for neural networks. result Dimension-independent convergence rates for neural networks.
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.
A new method selects anchor words for better topic discovery in text corpora.
problem Selecting anchor words for improved topic modeling in text corpora.
method Proposes a new greedy method to find a minimum edge-weight anchor clique in a word similarity graph.
result The proposed method outperforms existing methods on topic quality and is faster.
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.
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 Pg,p when it is an induced subgraph of the curve graph of a surface of genus g with p punctures. Two well-known graph invariants, the chromatic and clique numbers, can provide obstructions to Pg,p. 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.
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 …
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 HS2 that can handle both pointwise and pairwise queries. result Demonstrated that HS2 requires significantly fewer queries than a previously used graph-based method S2. 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 A∈Rn×n, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution Aij∼P0, or instead A contains a principal submatrix AQ,Q whose entries have marginal distribution Aij∼P1=P0. 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.
We give a reduction from {\sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.
A fundamental property of complex networks is the tendency for edges to cluster. The extent of the clustering is typically quantified by the clustering coefficient, which is the probability that a length-2 path is closed, i.e., induces a triangle in the network. However, higher-order cliques beyond triangles are crucia…
This paper focuses on tools for constructing 4-manifolds that have fundamental group G isomorphic to a right-angled Artin group and that are also minimal, in the sense that they minimize b2(M), the dimension of H2(M;Q). For a finitely presented group G, define $h(G) = \min\{ b_2(M) | M \in \mathcal M…
Finding "densely connected clusters" in a graph is in general an important and well studied problem in the literature \cite{Schaeffer}. It has various applications in pattern recognition, social networking and data mining \cite{Duda,Mishra}. Recently, Ames and Vavasis have suggested a novel method for finding cliques i…