Semi-structured business processes are emerging at a rapid pace in industries such as government, insurance, banking and healthcare. The workflows underlying these case-oriented processes are non-deterministic. They are mostly driven by human decision making and content status and they may change frequently depending on factors such as economic conditions, legislative policy changes and technological upgrades. This paper describes a method to detect changes in a running business process by conducting spectral graph analysis of sets of execution traces of the process. This method is beneficial because it does not require mining a process model of the business process, and is consequently independent of any assumptions about the nature of the business process. This makes it particularly applicable to case-oriented semi-structured business processes whose lifecycle is not fully driven by a formal process model. In this paper we present our algorithm for computing graph spectra from business process execution traces, and discuss some initial promising results, as well as exciting ideas generated by this research for future work. © 2011 IEEE.