Institute of Information Science, Academia Sinica

Our networks are constantly generating an enormous amount of information. Such information creates exciting opportunities for network analytics and provides deep insights into the complex interactions among network entities. We want to make sense of these rich and diverse data our networks provide. However, a major challenge to enable effective network analytics is the presence of missing data, measurement errors, and anomalies. Despite significant work in network analytics, fundamental issues remain: (i) the existing works do not explicitly account for anomalies or measurement noise, and incur serious performance degradation under significant noise or anomalies, and (ii) they assume network matrices have low-rank structure, which may not hold in reality.

To address these issues, we develop LENS decomposition, a novel technique to accurately decompose a network matrix into a low-rank matrix, a sparse anomaly matrix, an error matrix, and a small noise matrix. This decomposition naturally reflects the inherent structures of real-world data and is more general than existing compressive sensing techniques by removing the low-rank assumption and explicitly supporting anomalies.

LENS has the following nice properties: (i) it is general: it can effectively support matrices with or without anomalies, and having low-rank or not, (ii) its parameters are self tuned so that it can adapt to different types of data, (iii) it is accurate by incorporating domain knowledge, such as temporal locality, spatial locality, and initial estimate ([@BackSlash]eg, obtained from models), (iv) it is versatile and can support many applications including missing value interpolation, prediction, and anomaly detection.

A wide range of applications benefits from LENS. We demonstrate the effectiveness by apply LENS to practical systems, including anomaly detection in customer care call centers, WiFi rate adaptation, localization systems, and smart measurement plane for Software-Defined Network (SDN).

Yi-Chao Chen received the B.S and M.S. degrees in computer science and information engineering from National Taiwan University in 2004 and 2006. He entered The University of Texas at Austin to study computer science for Ph.D. degree in 2009. His research interests focus on networked systems and span the areas of WiFi systems, network measurement and analytics, and mobile computing.