False discovery rate multiple tests

Question

I wrote an algorithm which finds a monopartite projection of a bipartite graph. The output looks quite strange to me, but since I cannot find mistakes in the code, I'm wondering if maybe they're not so strange after all. At a certain point the algorithm performs a multiple hypothesis test. For each couple on nodes of the graph, the null ipothesis is that the edge between the 2 nodes belongs to the graph. I have a matrix of p-values for each edge. Now the text suggests to use a false discovery rate procedure for multiple hypothesis testing, that is: sort the the p-values in ascending order, then take the largest p-value which satisfies: $$ p_i \le \frac{i\alpha}{M}$$ where M is the number of hypothesis and $\alpha$ is the significance level of the test. Then reject all the tests with pvalues less than $p_i$. In my case $M= N(N-1)/2$, which is really large( in my case $N=700$), so that the right-hand side is almost 0. I'm wondering if maybe this procedure is too stringent. In general when you have a lot of hyphotesis the second member will be low, so you will reject very few hypothesis. In my case with $\alpha = 0.1$, only $65$ tests are rejected. If for instance I use $\alpha= 0.05$, and I perform each test independently, I obtain that in $36428$ cases the null hypothesis is rejected. Are these numbers normal? I mean when you test a lot of hyphotesis, unless you have almost 0 pvalues yuo will always accept the null hypothesis, I got that this procedure is meant to control uncorrect rejected null hypthosesis, but is it not just too strict control?

Answer 1

Since I do not have enough reputation to comment on your question, here we go.

This problem reminds me of this paper

http://jmlr.csail.mit.edu/papers/volume10/li09a/li09a.pdf

I am not aware of any other multiplicity procedure incorporated with the graphical models, though. The procedure you have described, Benjamini-Hochberg procedure, is meant to be stringent to control the false discovery rate. If your problem satisfies the certain dependence assumption, you may try Benjamini-Yekutieli procedure: Section 1.3 in

http://www.math.tau.ac.il/~ybenja/MyPapers/benjamini_yekutieli_ANNSTAT2001.pdf

I guess that your graph is too dense since not so many hypotheses are rejected. See if your algorithm implements a set of multiple hypothesis testings at the right steps. You may not have to accept all hypotheses to establish a single edge.

This might be helpful, too:

Multiple hypothesis testing correction with Benjamini-Hochberg, p-values or q-values?