Web services are a new kind of Web applications. As the services published on the Internet expand exponentially, finding them becomes more and more timeconsuming. UDDI v2 has added a new feature, publisherAssersion, to express the relation between business entities in a UDDI repository center just like a hyperlink between the Web pages. Thus, a Web service graph can be generated. This paper observes the new features of Web services first. The principles and an algorithm for constructing a Web service graph is proposed and analyzed in detail. Using the Web services graph for service discovery is elaborated then. Finally, it is shown from the simulated experiments that the Web services graph proposed in this paper is useful for composite Web service discovery.