We derive an optimization framework for vertex sampling based on the notion of mean hitting time, which considers multiple graphs associated with a vertex set V representing an online community. First, we formulate a collection of Markov chains on the graph ensemble and describe the characteristics of the associated hitting times on V. Then, we design a branch and bound optimization technique for computing the subset of vertices A that exhibits the smallest hitting time cost across the multi-graph, given a constraint on the volume of A. We also design a greedy optimization method for computing an approximation to the optimal subset at lower complexity, which lends itself to a decentralized implementation, for further complexity reduction. We examine the performance of our framework via experiments involving synthetic and real data. We study the hitting-time trade-off across the multi-graph, driven by the node sampling cost factors λ_j associated with each graph layer G_j. Relative to conventional graph centrality methods of node selection, we demonstrate a substantial improvement in terms of sampling (network) cost reduction and information dissemination speed. In addition, we show how the framework can be employed to deliver higher semantic coherence in information search over a collection of items represented by a multi-graph.