 Award ID(s):
 1744129
 NSFPAR ID:
 10276807
 Date Published:
 Journal Name:
 IEEE Transactions on Signal Processing
 ISSN:
 1053587X
 Page Range / eLocation ID:
 1 to 1
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Cliquecounting is a fundamental problem that has application in many areas eg. dense subgraph discovery, community detection, spam detection, etc. The problem of kcliquecounting is difficult because as k increases, the number of kcliques goes up exponentially. Enumeration algorithms (even parallel ones) fail to count kcliques beyond a small k. Approximation algorithms, like TuránShadow have been shown to perform well upto k = 10, but are inefficient for larger cliques. The recently proposed Pivoter algorithm significantly improved the stateoftheart and was able to give exact counts of all kcliques in a large number of graphs. However, the clique counts of some graphs (for example, comlj) are still out of reach of these algorithms. We revisit the TuránShadow algorithm and propose a generalized framework called YACC that leverages several insights about realworld graphs to achieve faster cliquecounting. The bottleneck in TuránShadow is a recursive subroutine whose stopping condition is based on a classic result from extremal combinatorics called Turán's theorem. This theorem gives a lower bound for the kclique density in a subgraph in terms of its edge density. However, this stopping condition is based on a worstcase graph that does not reflect the nature of realworld graphs. Using techniques for quickly discovering dense subgraphs, we relax the stopping condition in a systematic way such that we get a smaller recursion tree while still maintaining the guarantees provided by TuránShadow. We deploy our algorithm on several realworld data sets and show that YACC reduces the size of the recursion tree and the running time by over an order of magnitude. Using YACC, we are able to obtain clique counts for several graphs for which cliquecounting was infeasible before, including comlj.more » « less

null (Ed.)Quickest change detection in a sensor network is considered where each sensor observes a sequence of random variables and transmits its local information on the observations to a fusion center. At an unknown point in time, the distribution of the observations at all sensors changes. The objective is to detect the change in distribution as soon as possible, subject to a false alarm constraint. We consider minimax formulations for this problem and propose a new approach where transmissions are ordered and halted when sufficient information is accumulated at the fusion center. We show that the proposed approach can achieve the optimal performance equivalent to the centralized cumulative sum (CUSUM) algorithm while requiring fewer sensor transmissions. Numerical results for a shift in mean of independent and identically distributed Gaussian observations show significant communication savings for the case where the change seldom occurs which is frequently true in many important applications.more » « less

We present an exact algorithm for graph coloring and maximum clique problems based on SAT technology. It relies on four subalgorithms that alternatingly compute cliques of larger size and colorings with fewer colors. We show how these techniques can mutually help each other: larger cliques facilitate finding smaller colorings, which in turn can boost finding larger cliques. We evaluate our approach on the DIMACS graph coloring suite. For finding maximum cliques, we show that our algorithm can improve the stateoftheart MaxSATbased solver IncMaxCLQ, and for the graph coloring problem, we close two open instances, decrease two upper bounds, and increase one lower bound.more » « less

We design new polynomialtime algorithms for recovering planted cliques in the semirandom graph model introduced by Feige and Kilian 2001. The previous best algorithms for this model succeed if the planted clique has size at least n2/3 in a graph with n vertices (Mehta, Mckenzie, Trevisan 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for plantedclique sizes approaching n1/2  the informationtheoretic threshold in the semirandom model (Steinhardt 2017) and a conjectured computational threshold even in the easier fullyrandom model. This result comes close to resolving open questions by Feige 2019 and Steinhardt 2017. Our algorithms are based on higher constant degree sumofsquares relaxation and rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite ErdősRényi random graphs into algorithms for semirandom planted clique. The use of a higherconstant degree sumofsquares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size k=o(n2/3). We also provide some evidence that the informationcomputation tradeoff of our current algorithms may be inherent by proving an averagecase lower bound for unbalanced bicliques in the lowdegreepolynomials model.more » « less

Abstract A
colouring of a graph$(p,q)$ is an edgecolouring of$G$ which assigns at least$G$ colours to each$q$ clique. The problem of determining the minimum number of colours,$p$ , needed to give a$f(n,p,q)$ colouring of the complete graph$(p,q)$ is a natural generalization of the wellknown problem of identifying the diagonal Ramsey numbers$K_n$ . The bestknown general upper bound on$r_k(p)$ was given by Erdős and Gyárfás in 1997 using a probabilistic argument. Since then, improved bounds in the cases where$f(n,p,q)$ have been obtained only for$p=q$ , each of which was proved by giving a deterministic construction which combined a$p\in \{4,5\}$ colouring using few colours with an algebraic colouring.$(p,p1)$ In this paper, we provide a framework for proving new upper bounds on
in the style of these earlier constructions. We characterize all colourings of$f(n,p,p)$ cliques with$p$ colours which can appear in our modified version of the$p1$ colouring of Conlon, Fox, Lee, and Sudakov. This allows us to greatly reduce the amount of casechecking required in identifying$(p,p1)$ colourings, which would otherwise make this problem intractable for large values of$(p,p)$ . In addition, we generalize our algebraic colouring from the$p$ setting and use this to give improved upper bounds on$p=5$ and$f(n,6,6)$ .$f(n,8,8)$