  Suppose we are given a system of coupled oscillators on an unknown graph
along with the trajectory of the system during some period. Can we predict
whether the system will eventually synchronize? Even with a known underlying
graph structure, this is an important yet analytically intractable question in
general. In this work, we take an alternative approach to the synchronization
prediction problem by viewing it as a classification problem based on the fact
that any given system will eventually synchronize or converge to a
non-synchronizing limit cycle. By only using some basic statistics of the
underlying graphs such as edge density and diameter, our method can achieve
perfect accuracy when there is a significant difference in the topology of the
underlying graphs between the synchronizing and the non-synchronizing examples.
However, in the problem setting where these graph statistics cannot distinguish
the two classes very well (e.g., when the graphs are generated from the same
random graph model), we find that pairing a few iterations of the initial
dynamics along with the graph statistics as the input to our classification
algorithms can lead to significant improvement in accuracy; far exceeding what
is known by the classical oscillator theory. More surprisingly, we find that in
almost all such settings, dropping out the basic graph statistics and training
our algorithms with only initial dynamics achieves nearly the same accuracy. We
demonstrate our method on three models of continuous and discrete coupled
oscillators -- the Kuramoto model, Firefly Cellular Automata, and
Greenberg-Hastings model. Finally, we also propose an "ensemble prediction"
algorithm that successfully scales our method to large graphs by training on
dynamics observed from multiple random subgraphs.
