Similarities and Representations of Graph Structures

Abstract

Graphs are a natural representation for diverse systems ranging from social networks to the Web and brain structure. Even when data is not interconnected explicitly, it is often convenient to convert it into a graph for further analysis. Many tasks involving graphs, such as link prediction, community detection, and classification, rely on various definitions of similarities between nodes in graphs or graphs as a whole. However, such similarities are mostly implicit, meaning that objects are not represented by a feature vector in some space. In contrast, modern machine learning methods require explicit representations of objects in the Euclidean space. To leverage machine learning powers on graph data, we must find suitable explicit representations of graphs. <br /> This thesis develops efficient algorithms for obtaining expressive, explicit representations of graph-structured data. We focus on the scalability of the algorithms, as they must have an ability to process Web-sized graphs to be relevant for practice. Local graph algorithms have that ability; we introduce scalable local algorithms for representing nodes, edges, and whole graphs as vectors in the Euclidean space. Studying representations through the lens of the underlying similarity allows us to elucidate previous work and introduce extremely desirable properties to our proposed models. Notably, we introduce the first anytime and the first local algorithms for representing graphs' nodes. For the case of whole graphs, we propose the first representation that empowers multi-scale comparison of graphs and a method for its local approximation. We verify experimentally that our methods do not sacrifice the expressivity of representations for algorithms' scalability. We introduce novel applications of graph analysis and use our methods on massive graphs with billions of nodes.