Search for: All records

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. 

Recent work has shown that repetition coding followed by interleaving induces signal structure that can be exploited to separate multiple co-channel user transmissions, without need for pilots or coordination/synchronization between the users. This is accomplished via a statistical learning technique known as canonical correlation analysis (CCA), which works even when the channels are time-varying. Previous analysis has established that it is possible to identify the user signals up to complex scaling in the noiseless case. This letter goes one important step further to show that CCA in fact yields the linear MMSE estimate of the user signals up to complex scaling, without using any explicit training. Instead, CCA relies only on the repetition and interleaving structure. This is particularly appealing in asynchronous ad-hoc and unlicensed setups, where tight user coordination is not practical. 

In this paper, we present a method for decoding uplink messages in Internet of Things (IoT) networks that employ packet repetition. We focus on the Sigfox protocol, but our approach is applicable to other IoT protocols that employ message repetition. Our approach endeavors to enhance the reliability of message capture as well as the error rate performance at the base station. To achieve this goal, we propose a novel technique that capitalizes on the unique features of the IoT network’s uplink transmission structure. Through simulations, we demonstrate the effectiveness of our method in various scenarios, including single-user and multi-user setups. We establish the resilience of our approach under higher system loads and interference conditions, showcasing its potential to improve IoT network performance and reliability even when a large number of devices operates over limited spectrum. Our findings reveal the potential of the proposed method as a promising solution for enabling more dependable and energy-efficient communication in IoT Low Power Wide Area Networks. 

Canonical correlation analysis (CCA) is a classic statistical method for discovering latent co-variation that underpins two or more observed random vectors. Several extensions and variations of CCA have been proposed that have strengthened our capabilities in terms of revealing common random factors from multiview datasets. In this work, we first revisit the most recent deterministic extensions of deep CCA and highlight the strengths and limitations of these state-of-the-art methods. Some methods allow trivial solutions, while others can miss weak common factors. Others overload the problem by also seeking to reveal what is {\em not common} among the views -- i.e., the private components that are needed to fully reconstruct each view. The latter tends to overload the problem and its computational and sample complexities. Aiming to improve upon these limitations, we design a novel and efficient formulation that alleviates some of the current restrictions. The main idea is to model the private components as {\em conditionally} independent given the common ones, which enables the proposed compact formulation. In addition, we also provide a sufficient condition for identifying the common random factors. Judicious experiments with synthetic and real datasets showcase the validity of our claims and the effectiveness of the proposed approach. 

Channel estimation in rapidly time-varying or short and bursty communication scenarios is costly in terms of both pilot overhead and co-channel interference. In recent work, it was shown that multipath delay-diversity can be exploited to detect multiple co-channel user signals, provided that the relative multipath delays for the different users are distinct, and the two multipath ‘taps’ of each user have roughly commensurate power. These requirements may not hold naturally, however, especially for relatively narrowband or short-range transmissions with small delay spread. As an alternative, this paper advocates using dual antenna transmission in a manner that introduces artificial multipath and tight control of the power of the two channel taps, via baseband processing at the transmitter. The approach enjoys theoretical guarantees and affords simple decoding and accurate synchronization as a side bonus. Similar claims have been previously laid using packet repetition via a single transmit-antenna, but the dual-antenna artificial multipath scheme proposed herein doubles the transmission rate relative to packet repetition. Laboratory experiments using programmable radios are used to demonstrate successful operation of the proposed transmission scheme in practice.