Top-K ranking

This short video gives an interesting introduction to our viewpoints on top-K ranking. Hope you enjoy!


In the big data era, the task of rank aggregation faces a new challenge: due to the huge number of items/candidates to be ranked, observation of the complete data sets is often infeasible. This challenge brings about a series of significant questions. How can we identify a ranking of the items, given highly incomplete measurements of data sets? Is there a low-complexity algorithm that promises the optimal ranking accuracy, usually quantified as minimal sample complexity? Can we exploit realistic scenarios in which only a few significant items, say top-K items, are emphasized among the huge number of the entire items?

Focusing on the popular Bradley-Terry-Luce model, we found the minimax limits on the identifiability of top-K ranked items in the presence of non-adaptive random sampling. To achieve the limits, we propose a nearly linear-time ranking scheme, called Spectral MLE. Spectral MLE starts with an initial score estimate with minimal squared loss, which is obtained via a spectral method, and then successively refines each component of the estimate by coordinate-wise MLEs.

  • Y. Chen and C. Suh, “Spectral MLE: Top-K rank aggregation from pairwise comparisons,” presented at ICML 2015, submitted to JMLR 2015.

To verify the practical applicability of Spectral MLE, largely determined by time-complexity and scalability with respect to the total number of items, we intend to implement Spectral MLE (or its variants) in graph-engine-based frameworks such as Pregel, GraphX, and GraphLab, that enable large-scale distributed processing across many distinct clusters apart. Successful outcomes will make Spectral MLE applicable for fast ranking adaptation of a huge number of items.

Bursty networks

The standard information-theoretic models in wireless communications introduce transmitters that send signals at all times. One rationale behind the modeling can be that transmitters always have a sufficient amount of data they wish to transfer. However, in practice, transmitters are more likely to send signals in a bursty manner due to a variety of reasons - bursty data traffic and random media access control protocols, to name a few. We are interested in investigating such bursty networks. We have examined the role of relays in a few exemplary bursty networks, and found that relays play a significant role in bursty networks by exploiting idle moments of the transmitters.

In bursty interference channels (ICs), we found that relays can provide a degrees-of-freedom (DoF) gain that scales linearly with the number of relay antennas. More interestingly, they can help achieve interference-free DoF performances. The relay and active transmitters synchronously cooperate to cancel out interference in the air, and deliver only desired information to the receivers.

  • S. Kim, I.-H. Wang, and C. Suh, “A relay can increase degrees of freedom in bursty interference networks,” presented at ISIT 2015, submitted to IT 2015.

In bursty mutiple access channels (MACs), we found that relays can provide a DoF gain that scales to some extent with the number of relay antennas. What's more, they can help achieve collision-free DoF performances. The relay in effect schedules uncoordinated bursty transmissions.

  • S. Kim and C. Suh, “Degrees of freedom of bursty multiple access channels with a relay,” submitted to Allerton 2015.

Our results of the bursty networks have practical implications in future wireless systems. For example, when the Internet of Things (IoT) is considered, there are usually many mobile devices that gather and exchange small-sized data in a bursty manner, and a few central hubs that process the collected data to perform some functionality. In such scenarios, relays can be of great help. They can boost up the overall data throughput as they can increase the total number of degrees-of-freedom, for certain cases, linearly with additional relay antennas. Moreover, they can ease the need of complicated media access control protocols as they can in effect schedule uncoordinated bursty exchanges of data, thus creating collision-free environments for certain cases.

Two-way interaction

The inherent two-way nature of communication links allows nodes to adapt their transmitted signals to the past received signals in exchanging their messages. Understanding the role of interaction, that lies at the heart of two-way communication, has not been well explored. We are interested in understanding the role of interaction. We have examined Avestimehr-Diggavi-Tse (ADT) deterministic models that well capture the essence of Gaussian wireless networks, and found that feedback, that enables interaction, can be useful even when it comes with a cost.

In two-way interference channels (ICs), we found that the capacity gain due to feedback is strictly larger than the capacity gain due to the use of the backward IC for sending independent backward messages. In other words, the backward IC can be more efficiently used for sending feedback signals that aid forward-message transmission, rather than if it were used for transmitting its own independent backward messages. This finding shows that feedback can provide a net gain in capacity even when we take feedback cost into consideration.

  • C. Suh, I.-H. Wang, and D. Tse, “Two-way interference channels,” presented at ISIT 2012.

In two-way ICs where nodes now wish to compute functions of messages, rather than to decode the raw messages, we found that the computation capacity gain due to feedback is strictly larger than the computation capacity due to the use of the backward IC for sending feedback signals that aid forward-message computation. This finding again shows that feedback can provide a net gain in computation capacity even when we take feedback cost into consideration.

  • S. Shin and C. Suh, “Two-way function computation,” presented at Allerton 2014.

What our results in the two-way interaction networks show is that the role of interaction can be significant. There is a net gain in (computation) capacity, even when feedback cost, the opportunity cost imposed by using the backward network for feedback rather than other alternative uses, is taken into consideration. The results imply that in future wireless networks, where many nodes are more likely to act as both source and destination concurrently, interaction among them will be vital.