Embodiments of the present invention provide systems, methods, and computer storage media for latent summarization of a graph. Structural features can be captured from feature vectors associated with each node of the graph by applying base functions on the feature vectors and iteratively applying relational operators to successive feature matrices to derive deeper inductive relational functions that capture higher-order structural information in different subgraphs of increasing size (node separations). Heterogeneity can be summarized by performing capturing features in appropriate subgraphs (e.g., node-centric neighborhoods associated with each node type, edge direction, and/or edge type). Binning and/or dimensionality reduction can be applied to the resulting feature matrices. The resulting set of relational functions and multi-level feature matrices can form a latent summary that can be used to perform a variety of graph-based tasks, including node classification, node clustering, link prediction, entity resolution, anomaly and event detection, and inductive learning tasks.