Data represented as graphs with complex structures are ubiquitous nowadays. Examples include technological networks (e.g., the Internet), informational networks (e.g., the World-Wide Web), social networks (e.g., Facebook's friendship graph), and biological networks (e.g., protein interactions). In this talk, I will present algorithms for both relational classification and clustering in such networked data. I will pay special attention to issues surrounding scalability, sparsity of labels, various levels of relational dependency, and performance consistency across assorted domains.