Topology Discovery from a Single Interaction Trajectory of an Agent Collective

We consider the setting of autonomous agents on an open network that hold persistent state and revise it asynchronously from the states of the agents they are coupled to. In many scenarios, the coupling graph is rarely observable: agents pair at run time, and what is recorded is only a log of state revisions, timestamped and attributed to the agent that made them. Learning the coupling graph is crucial for several downstream tasks such as credit assignment and root cause analysis. We ask when the interaction log alone determines the graph efficiently. Modeling the updates as noisy asynchronous DeGroot averaging with Gaussian innovations identifies the log with a single trajectory of random-scan Gaussian Glauber dynamics, and the coupling graph with the conditional-independence graph of a Gaussian graphical model. Existing procedures for recovering such a structure from a non-stationary trajectory must either wait for the corresponding Markov chain to mix (which could take time that is super-polynomial in the number of agents $p$ without strong asssumptions) or forfeit optimal dependence on the weakest coupling strenth $\kappa$. We remove that tradeoff. We propose two techniques for topology learning that work directly off the update sequence that, for a degree $d$ graph, can provably recover the graph in $\widetilde O(pd^{2}/\kappa^{2})$ and $\widetilde O(pd^{4}/\kappa^{2})$ updates respectively. While the former depends mildly on the conditioning of the model, the latter works uniformly with no such assumptions. The analysis techniques that intricately leverage the independent innovations in a highly dependent data stream could be of independent interest.