The short answer is yes, you can do that. k-fold cross-validation is typically used when sample data is sufficiently limited. From your description, unless your computer is rather resource-limited, it appears that you have a very large sample size. If that is the case (your sample data set is sufficiently large), then you could do a 2-fold cross-validation. This would lead to 2 samples (A and B), where you first train on A and test on B, then vice versa.
As a commenter mentioned, bagging (bootstrap aggregation) is another option, although an ensemble classifier may not be applicable/desirable to your particular problem. Another option would be to randomly draw samples of ~ 10% of the data for training, then another 10% for testing and repeat that process multiple times and assess variability of your results.
What may complicate the analysis is that you stated you are attempting to learn network structure. If the network structure (edges between nodes) is already defined, assessing variability of network weights is fairly straightforward but quantifying variability in network structure (which nodes are connected and in what direction) is a more complicated process.