How to validate the regulatory interactions inferred from gene expression data?
You can validate the interactions by knockding down (KD) or overexpressing (OE) a gene and checking the change in expression levels of the downstream nodes. You can do this in a high throughput fashion using microarray or RNAseq. For protein you can do an LC-MS. However this method cannot help you in:


Differentiating direct vs indirect interactions
Finding regulation in case of loops and other non-linear interactions in the network


Loops are tricky but sampling at multiple time intervals can let you know if oscillations exist or not. For most usual cases this approach works out. 

Usually this is followed by another round of validation using a relatively low throughput but sensitive technique such as 


Real-time PCR (KD vs OE)
Western blots (KD vs OE)
Reporter assays (KD vs OE) would detect direct interactions. For e.g. possible promoter for a (Transcription Factor) TF (upstream of gene-Y) is used to express GFP to see if GFP responds to the TF; thereby validating the effect of TF on Gene-Y via the promoter.


In some cases you may have to do ChIP-seq to find out if a gene has binding sites for a TF in its promoter/enhancer. You may also use predictions for TF binding sites. For finding regulation by miRNAs you can see this post.

For finding complex dynamics such as pulses and oscillations you have to collect time-course data. 


  how to quantify their expression levels as over or under expressed?


For that you first need to define your control (up/down regulated wrt what?). Having done that you can compare the expression and use right statistical tests to check differential regulation. If you have just one sample then most tests won't work. For RNAseq,  EM algorithms are used which use a bayesian model to obtain likelihoods and p-value (I have used cufflinks and eXpress). Then a FDR correction can be performed when comparing the test vs control. I am not very sure about algorithms used for comparing LC-MS data for proteins.