Network analysis, inference and optimization represent methodological challenges which play a central role in large scale data analysis. Their practical  relevance arises from the huge  quantity of empirical data that is being made available in many fields of science, biology and economics in first place.  In this talk we shall discuss some new statistical physics approaches to basic network optimization problems that come from sub-graph identification.
Firstly we show how to approach the so called sub-graph isomorphism problem, one of the most fundamental NP-hard problems in graph theory. We display three applications: maximum clique identification, graph alignment and network motif counting. Secondly we discuss how to generalize the cavity method to deal with the problem of searching for  sub-network which are subject to topological constraints. The specific case of bounded depth Spanning trees is discussed in some detail, together with a novel application to high dimensional  data clustering.