Given an undirected graph and a size parameter k, the Densest k-Subgraph (DkS) problem extracts the subgraph on k vertices with the largest number of induced edges. While DkS is NP--hard and difficult to approximate, penalty-based continuous relaxations of the problem have recently enjoyed practical success for real-world instances of DkS. In this work, we propose a scalable and exact continuous penalization approach for DkS using the error bound principle, which enables the design of suitable penalty functions. Notably, we develop new theoretical guarantees ensuring that both the global and local optima of the penalized problem match those of the original problem. The proposed penalized reformulation enables the use of first-order continuous optimization methods. In particular, we develop a non-convex proximal gradient algorithm, where the non-convex proximal operator can be computed in closed form, resulting in low per-iteration complexity. We also provide convergence analysis of the algorithm. Experiments on large-scale instances of the DkS problem and one of its variants, the Densest (k1, k2) Bipartite Subgraph (Dk1k2BS) problem, demonstrate that our method achieves a favorable balance between computation cost and solution quality.

We introduce the triangle-densest-k-subgraph problem (TDkS) for undirected graphs: given a size parameter k, compute a subset of k vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge-based densest-k-subgraph problem (DkS) to the case of higher-order network motifs. We prove that TDkS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDkS is submodular to construct a convex relaxation for the problem based on the Lovasz extension for submodular functions. We ´ demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DkS. We use document summarization to showcase why TDkS is a useful generalization of DkS

Given an unweighted, undirected, and simple graph, the Densest k-Subgraph (DkS) problem aims to find a subgraph of k vertices that has the maximum average induced degree. In this paper, we consider an equivalent reformulation of the DkS problem via diagonal loading. On relaxing the combinatorial constraint of the reformulated problem, we show that the resulting non-convex, continuous relaxation is tight under certain conditions by leveraging an extension of the Motzkin-Straus theorem. We utilize two projection-free approaches to solve the relaxed problem: one based on the Frank-Wolfe algorithm and the other on explicit constraint parameterization. We compare their performance to state-of-the-art baselines across various benchmarks. Our empirical results show that the Frank-Wolfe-based algorithm proposed in this paper outperforms existing baselines in terms of subgraph density and computational complexity.

Crowdsourcing is becoming increasingly important for contemporary applications in machine learning and artificial intelligence. However, crowdsourcing systems may be susceptible to adversarial attacks where a subset of annotators deliberately provide erroneous responses. This paper introduces a novel algorithm for identifying adversarial attacks in crowdsourcing systems by recasting the problem as dense subgraph detection in bipartite graphs. In particular, we represent crowdsourced data as a weighted bipartite graph between workers and data points which are connected with edges whose weights are computed from annotators’ responses. The constructed bipartite graph is then analyzed with a sequential peeling algorithm to detect the dense subgraph that includes adversarial attacks. Compared to previous methods where only adversaries are detected, our proposed method can simultaneously identify adversarial annotators as well as affected data points. Preliminary results on real datasets showcase the potential of this novel approach.

Dense subgraph discovery (DSD) is a key primitive in graph mining that typically deals with extracting cliques and near-cliques. In this paper, we revisit the optimal quasi-clique (OQC) formulation for DSD and establish that it is NP--hard. In addition, we reveal the hitherto unknown property that OQC can be used to explore the entire spectrum of densest subgraphs of all distinct sizes by appropriately varying a single hyperparameter, thereby forging an intimate link with the classic densest-k-subgraph problem (DkS). We corroborate these findings on real-world graphs by applying the simple greedy algorithm for OQC with improved hyperparameter tuning, to quickly generate high-quality approximations of the size-density frontier. Our findings indicate that OQC not only extracts high quality (near)-cliques, but also large and loosely-connected subgraphs that exhibit well defined local community structure. The latter discovery is particularly intriguing, since OQC is not explicitly geared towards community detection.

We introduce the triangle-densest-K-subgraph problem (TDKS) for undirected graphs: given a size parameter K, compute a subset of K vertices that maximizes the number of induced triangles. The problem corresponds to the simplest generalization of the edge based densest-K-subgraph problem (DKS) to the case of higher-order network motifs. We prove that TDKS is NP-hard and is not amenable to efficient approximation, in the worst-case. By judiciously exploiting the structure of the problem, we propose a relaxation algorithm for the purpose of obtaining high-quality, sub-optimal solutions. Our approach utilizes the fact that the cost function of TDKS is submodular to construct a convex relaxation for the problem based on the Lovász extension for submodular functions. We demonstrate that our approaches attain state-of-the-art performance on real-world graphs and can offer substantially improved exploration of the optimal density-size curve compared to sophisticated approximation baselines for DKS. We use document summarization to showcase why TDKS is a useful generalization of DKS.

Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP–hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this article, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art.

Graphs are powerful abstractions that naturally capture the wealth of relationships in our interconnected world. This paper proposes a new approach for graph alignment, a core problem in graph mining. Classical (e.g., spectral) methods use fixed embeddings for both graphs to perform the alignment. In contrast, the proposed approach fixes the embedding of the 'target' graph and jointly optimizes the embedding transformation and the alignment of the 'query' graph. An alternating optimization algorithm is proposed for computing high-quality approximate solutions and compared against the prevailing state-of-the-art graph aligning frameworks using benchmark real-world graphs. The results indicate that the proposed formulation can offer significant gains in terms of matching accuracy and robustness to noise relative to existing solutions for this hard but important problem.

Given an undirected graph, the Densest-k-Subgraph problem (DkS) seeks to find a subset of k vertices such that the sum of the edge weights in the corresponding subgraph is maximized. The problem is known to be NP-hard, and is also very difficult to approximate, in the worst-case. In this paper, we present a new convex relaxation for the problem. Our key idea is to reformulate DkS as minimizing a submodular function subject to a cardinality constraint. Exploiting the fact that submodular functions possess a convex, continuous extension (known as the Lovasz extension), we propose to minimize the Lovasz extension over the convex hull of the cardinality constraints. Although the Lovasz extension of a submodular function does not admit an analytical form in general, for DkS we show that it does. We leverage this result to develop a highly scalable algorithm based on the Alternating Direction Method of Multipliers (ADMM) for solving the relaxed problem. Coupled with a pair of fortuitously simple rounding schemes, we demonstrate that our approach outperforms existing baselines on real-world graphs and can yield high quality sub-optimal solutions which typically are a posteriori no worse than65-80%of the optimal density.

Graph matching aims to align a pair of graphs by minimizing their edge disagreements. As the problem is NP–hard in the worst-case, various methods have been proposed for approximately solving the problem. One popular approach is to relax the combinatorial problem to a continuous formulation, whose solution represents a soft correspondence between the vertex-sets of the graphs. Previous work has primarily motivated such soft matching formulations as an intermediate step towards obtaining hard correspondences. In this paper, we depart from this viewpoint and provide an alternate motivation for soft matching as a means of identifying classes of topologically-invariant subgraphs, which cannot be revealed by hard correspondences. Drawing on this observation, we consider the family of doubly-stochastic relaxations for graph matching and propose a new convex relaxation for the problem. We establish that the objective function of our formulation can be interpreted as the tightest convex relaxation of the combinatorial quadratic graph matching objective function in a certain sense, and describe an efficient first-order algorithm for computing its solution. Through experiments conducted on real-world data, we demonstrate the empirical effectiveness of the algorithm relative to the prevailing relaxations for graph matching.

Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. In this work, we formally establish that two recurring characteristics of real-world graphs, namely heavy-tailed degree distributions and large clustering coefficients, imply the existence of substantially large vertex neighborhoods with high edge-density. This observation suggests a very simple approach for extracting large quasi-cliques: simply scan the vertex neighborhoods, compute the clustering coefficient of each vertex, and output the best such subgraph. The implementation of such a method requires counting the triangles in a graph, which is a well-studied problem in graph mining. When empirically tested across a number of real-world graphs, this approach reveals a surprise: vertex neighborhoods include maximal cliques of non-trivial sizes, and the density of the best neighborhood often compares favorably to subgraphs produced by dedicated algorithms for maximizing subgraph density. For graphs with small clustering coefficients, we demonstrate that small vertex neighborhoods can be refined using a local-search method to grow larger cliques and near-cliques. Our results indicate that contrary to worst-case theoretical results, mining cliques and quasi-cliques of non-trivial sizes from real-world graphs is often not a difficult problem, and provides motivation for further work geared towards a better explanation of these empirical successes.

We consider the NP-hard combinatorial optimization problem of minimizing arbitrary quadratic forms over the {0, 1 } (Boolean) lattice. While polynomial-time approximation algorithms do exist for such problems, they suffer from the practical drawback of being computationally involved - often a side effect of being agnostic to the combinatorial structure inherent in the problem. In this paper, we propose a computationally lightweight approximation alternative which specifically exploits the combinatorial structure of the problem. The key result underlying our approach is that any Boolean quadratic function can be expressed as a difference of quadratic sub-modular functions, which enables us to construct and iteratively minimize a sequence of global submodular upper bounds on the cost function. This entails solving a quadratic submodular function minimization problem at each step, which can be efficiently accomplished via the seminal Max-Flow algorithm. Overall, our algorithm performs iterative approximation by solving a sequence of maximum-flow problems. The merits of using this approach are illustrated via simulations which indicate the very favorable performance of our algorithm.

Graph matching, the problem of aligning a pair of graphs so as to minimize their edge disagreements, has received widespread attention owing to its broad spectrum of applications in data science. As the problem is NP-hard in the worst-case, a variety of approximation algorithms have been proposed for obtaining high quality, suboptimal solutions. In this paper, we approach the task of designing an efficient polynomial-time approximation algorithm for graph matching from a previously unconsidered perspective. Our key result is that graph matching can be formulated as maximizing a monotone, supermodular set function subject to matroid intersection constraints. We leverage this fact to apply a discrete optimization variant of the minorization-maximization algorithm which exploits supermodularity of the objective function to iteratively construct and maximize a sequence of global lower bounds on the objective. At each step, we solve a maximum weight matching problem in a bipartite graph. Differing from prior approaches, the algorithm exploits the combinatorial structure inherent in the problem to generate a sequence of iterates featuring monotonically non-decreasing objective value while always adhering to the combinatorial matching constraints. Experiments on real-world data demonstrate the empirical effectiveness of the algorithm relative to the prevailing state-of-the-art.

Energy disaggregation is the task of decomposing the aggregated power consumption readings of a household into its constituent parts. In this paper, we propose a supervised, non-parametric framework for energy disaggregation. We demonstrate that the problem is equivalent to maximizing a set-function subject to combinatorial constraints, which is NP-hard in its general form. A simple polynomial-time successive approximation algorithm which exploits submodularity per set-block to iteratively maximize a sequence of global lower bounds of the objective function is proposed for obtaining approximate solutions. Experiments on real data indicate the superior disaggregation performance and scalability of our approach over a state-of-the-art parametric Factorial Hidden Markov Model based framework employing convex relaxation.

Quadratically constrained quadratic programming (QCQP) forms an important class of optimization tasks in various engineering disciplines. Fast identification of a feasible point under low computational complexity load is critical for several approximation techniques which have been developed to solve non-convex QCQPs. This paper introduces two projection-based techniques to compute feasible points of non-convex QCQPs with low computational complexity footprints: The first one employs successive projection mappings, while the second one builds on a composition of successive and averaged projection steps. Extensive experiments on synthetically generated instances of non-convex quadratically constrained feasibility problems demonstrate that the simple successive-projection based technique compares favorably against state-of-the-art feasible point pursuit methods which capitalize on successive convex approximation, parallel projections and computationally demanding interior-point techniques.

Quadratically Constrained Quadratic Programming (QCQP) is NP-hard in its general non-convex form, but it frequently arises in engineering design and applications ranging from state estimation to beamforming and clustering. Several polynomial-time approximation algorithms exist for non-convex QCQP problems (QCQPs), but their success hinges upon the ability to find at least one feasible point - which is also hard for a general problem instance. In this paper, we present a framework for computing feasible points of general non-convex QCQPs using simple first-order methods. Our approach features low computational and memory requirements, which makes it well-suited for application on large-scale problems. Experiments indicate the empirical effectiveness of our approach, despite currently lacking theoretical guarantees.

Owing to the rapidly increasing traffic demands on satellite connectivity, the current exclusive frequency allocation is becoming obsolete. Instead, aggressive frequency reuse and interference mitigation techniques are promising ideas that both industry and academia are investigating. This paper proposes an optimization precoding technique for dealing with the multibeam interference due to the aggressive frequency reuse. In contrast to general multiuser multiple input multiple output (MIMO) schemes, multibeam satellite precoding techniques call for frame-by-frame quadratically constrained quadratic optimization of a large number of variables. We focus on the multigroup multicast beamforming optimization problem, and we propose to adopt a consensus-based alternating direction method of multipliers (C-ADMM) approach, in order to mitigate complexity. The proposed C-ADMM approach is shown to exhibit comparable optimization performance at considerably lower complexity relative to the prior state-of-art for the formulation considered.

Estimating the power spectrum of a wide-sense stationary stochastic process is a core component of several signal processing tasks. Distributed spectrum sensing problems naturally emerge in cases where measurements of different realizations of a stochastic process are collected at multiple spatial locations. This paper describes a distributed power spectrum sensing scheme for stochastic processes which are well represented by an autoregressive (AR) process. The sensing model comprises a network of scattered low-end sensors which transmit randomly filtered, one bit quantized power measurements to a fusion center. The problem of AR power spectrum estimation from such binary power measurements is cast as a non-convex optimization problem, and an alternating minimization algorithm is proposed to obtain a stationary point. Simulations showcase the effectiveness of this scheme when the AR parametrization is valid.

Wideband spectrum sensing is one of the core components of cognitive radio. A novel frugal sensing scheme was recently proposed by Mehanna et al, aiming to crowdsource spectrum sensing operations to a network of sensors transmitting randomly filtered power measurement bits to a fusion center (FC). The ambient power spectrum is then estimated at the FC using a non-parametric approach. Here, it is assumed that the primary signal admits a Moving Average (MA) parametrization, and the frugal sensing problem is revisited from a parametric spectral estimation point of view. We show that the problem of estimating admissible MA parameters (and thus the MA power spectrum) from single bit quantized data can be formulated as a non-convex Quadratically Constrained Quadratic Program (QCQP). This is NP-Hard in general, but semidefinite-relaxation (SDR) can be employed to obtain approximate solutions. Simulations reveal the superior performance of the SDR technique over the globally optimal solution obtained from the non-parametric formulation, when the MA assumption is valid.

Quadratically Constrained Quadratic Programming (QCQP) has a broad spectrum of applications in engineering. The general QCQP problem is NP-Hard. This article considers QCQP with Toeplitz-Hermitian quadratics, and shows that it possesses hidden convexity: it can always be solved in polynomial-time via Semidefinite Relaxation followed by spectral factorization. Furthermore, if the matrices are circulant, then the QCQP can be equivalently reformulated as a linear program, which can be solved very efficiently. An application to parametric power spectrum sensing from binary measurements is included to illustrate the results.

Quadratically constrained quadratic programs (QCQPs) have a wide range of applications in signal processing and wireless communications. Non-convex QCQPs are NP-hard in general. Existing approaches relax the non-convexity using semi-definite relaxation (SDR) or linearize the non-convex part and solve the resulting convex problem. However, these techniques are seldom successful in even obtaining a feasible solution when the QCQP matrices are indefinite. In this letter, a new feasible point pursuit successive convex approximation (FPP-SCA) algorithm is proposed for non-convex QCQPs. FPP-SCA linearizes the non-convex parts of the problem as conventional SCA does, but adds slack variables to sustain feasibility, and a penalty to ensure slacks are sparingly used. When FPP-SCA is successful in identifying a feasible point of the non-convex QCQP, convergence to a Karush-Kuhn-Tucker (KKT) point is thereafter ensured. Simulations show the effectiveness of our proposed algorithm in obtaining feasible and near-optimal solutions, significantly outperforming existing approaches.