Whereas data mining in structured data focuses on frequent data values, in semi-structured and graph data the emphasis is on frequent labels and common topologies. Here, the structure of the data is just as important as its content. When data contains large amount of different labels, both fully labeled and partially data may be useful. More informative patterns can be found in the database if some of the pattern nodes can be regarded as 'unlabeled'. We study the problem of discovering typical fully and partially labeled patterns of graph data. Discovered patterns are useful in many applications, including: compact representation of source information and a road-map for browsing and querying information sources.