15 accepted papers
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
Computing the principal component (PC) of the adjacency matrix of an undirected graph has several applications ranging from identifying key vertices for influence maximization and controlling diffusion processes, to discovering densely interconnected vertex subsets. However, many networked datasets …
PageRank (PR) is a fundamental algorithm in graph machine learning tasks. Owing to the increasing importance of algorithmic fairness, we consider the problem of computing PR vectors subject to various group-fairness criteria based on sensitive attributes of the vertices. At present, principled algor…
The Densest $k$-Subgraph (D$k$S) is a fundamental combinatorial problem known for its theoretical hardness and breadth of applications. Recently, Lu et al. (AAAI 2025) introduced a penalty-based non-convex relaxation that achieves promising empirical performance; however, a rigorous theoretical unde…
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 con…
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 nove…
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 O…
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…
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 e…
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 solv…
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…
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 pr…
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 pro…
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 l…
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). T…