The Sample Complexity of Differential Analysis for Networks that Obey Conservation Laws

Networked systems that obey conservation laws are common in many domains such as power grids, biological systems, and social networks. These systems are described by socalled balance equations that link injected flows and node potentials, ensuring that the flow at each node is balanced. For example, electric networks follow Kirchhoff's laws, while social networks model group consensus. Understanding the structure of these networks based on node potential data has become an important research topic. In this work, we focus on the problem of differential network analysis for systems that obey conservation laws. That is, instead of the structure of a network, we focus on estimating the structural differences between two networks from their node potential data. We propose a method that uses a high-dimensional estimator to directly identify these structural changes. We provide theoretical guarantees and test our method on both synthetic networks and benchmark power network data to validate its performance. The results show that our method works well but also highlight some gaps between the theoretical guarantees and experimental outcomes. Addressing these gaps is an important step for improving future methods.