Cyber-physical systems (CPSs) are today ubiquitous in urban environments. Such systems now serve as the backbone to numerous critical infrastructure applications, from smart grids to IoT installations. Scalable and seamless operation of such CPSs requires sophisticated tools for monitoring the time series progression of the system, dynamically tracking relationships, and issuing alerts about anomalies to operators. We present an online monitoring system (illiad) that models the state of the CPS as a function of its relationships between constituent components, using a combination of model-based and data-driven strategies. In addition to accurate inference for state estimation and anomaly tracking, illiad also exploits the underlying network structure of the CPS (wired or wireless) for state estimation purposes. We demonstrate the application of illiad to two diverse settings: a wireless sensor motes application and an IEEE 33-bus microgrid.