Rate-Agnostic (Causal) Structure Learning
Causal structure learning from time series data is a major scientific challenge. Extant algorithms assume that measurements occur sufficiently quickly; more precisely, they assume approximately equal system and measurement timescales. In many domains, however, measurements occur at a significantly slower rate than the underlying system changes, but the size of the timescale mismatch is often unknown. This paper develops three causal structure learning algorithms, each of which discovers all dynamic causal graphs that explain the observed measurement data, perhaps given undersampling. That is, these algorithms all learn causal structure in a "rate-agnostic" manner: they do not assume any particular relation between the measurement and system timescales. We apply these algorithms to data from simulations to gain insight into the challenge of undersampling.
This paper proposes a framework and algorithms for learning causal structures from "undersampled" time series data, i.e. where the sampling occurs at a lower rate than the system, when it is unknown what the ratio of undersampling is; the only previous approach to deal with the undersampling problem required that the ratio of undersampling be small and known.The authors attempt to learn an equivalence class of structures for which an undersampling ratio exists that is consistent with the observed time series by learning a structure for the time series and then iterating over possible structures for the system while pruning the solution tree. The authors prove that their first algorithm, RASL_{re} is correct and complete and then introduce more efficient refinements, RASL_{ie} and RASL_{il}. The authors devote a significant portion of the paper to simulation studies comparing these three algorithms in different contexts where the structure for observed time series is known and then the authors provide one synthetic data example when this structure is unknown. The authors are dealing with a very difficult problem that is often shoved under the rug in related approaches. The framework for how they've approached this problem is very interesting and may turn out to be very fruitful, but the paper appears to be very preliminary at this point and is missing some things. The results section focuses a lot of attention to comparing the 3 different versions of RASL when the correct structure for the undersampled time series is known, which is essentially an implementation issue, at the expense of testing the full procedure in a realistic context when this graph is unknown. Only one synthetic data example is given with a 5 node structure and the discussion is limited. I'm left not really knowing what the significance of the edge omission and commission rates are, whether they converge, or how scalable this algorithm. The lack of discussion is sort of a problem throughout the results section and exacerbated by the fact that there is no conclusion. There are a lot of interesting observations given, but not much in terms of holistic conclusions about the performance of the algorithm. Aside from the last two sentences in 4.2, the authors don't really do much to "sell" their procedure. The authors also neglect the issue of learning the structure of the undersampled system. Several methods are mentioned, but the authors do not discuss the assumptions or implications of using one of these methods over another or whether they are correct or complete (which seems important since the authors prove their method which uses the results from these methods is correct and complete). Results are only given SVAR because the authors say it gave accurate and stable solutions in pilot testing, but they don't discuss further as to why they picked SVAR and whether they tested other methods. Including results for these other methods is another way that the results section could be improved. The authors also mention a number of possible application areas at the beginning of the paper, but do not apply their method to any real data. Some attempt to assess the performance on real data (even if the absolute ground truth is unknown), would also improve the results section.