Research at Google     {{link.text}} {{link.text}} Home Publications People Teams   Blog Work at Google     More Google Scholar YouTube Tech Talks Follow Us Google+ Twitter Google Google About Google Privacy Policy Terms     Graph Mining Google NYC Algorithms and Optimization Google NYC Algorithms and Optimization Our mission is to build the most scalable library for graph algorithms and analysis and apply it to a multitude of Google products. We formalize data mining and machine learning challenges as graph problems and perform fundamental research in those fields leading to publications in top venues. Our algorithms and systems are used in a wide array of Google products such as Search, YouTube, AdWords, Play, Maps, and Social. Take a look at our publications and recent Research Seminars. Some of Our Projects Large-Scale Balanced Partitioning Balanced Partitioning splits a large graph into roughly equal parts while minimizing cut size. The problem of "fairly" dividing a graph occurs in a number of contexts, such as assigning work in a distributed processing environment. Our techniques provided a 40% drop in multi-shard queries in the Google Maps Driving Directions, saving a significant amount of CPU usage. Learn more Distributed Balanced Partitioning via Linear Embedding Large-Scale Clustering Our team specializes in clustering graphs at Google scale. We have efficient implementations of many different algorithms including hierarchical clustering, overlapping clustering, local clustering, and spectral clustering. Learn more A Local Algorithm for Finding Well-Connected Clusters Affinity Clustering: Hierarchical Clustering at Scale Large-Scale Connected Components Connected Components is a fundamental subroutine in many graph algorithms. We have state-of-the-art implementations in a variety of paradigms including MapReduce, a distributed hash table, Pregel, and ASYMP. Our methods are 10-30x faster than the best previously studied algorithms, and easily scale to graphs with trillions of edges. Learn more Connected Components in MapReduce and Beyond Large-Scale Link Modeling Our similarity ranking and centrality metrics serve as good features for understanding the characteristics of large graphs. They allow the development of link models useful for both link prediction and anomalous link discovery. Our tool Grale learns a similarity function that models the link relationships present in data. Learn more When Recommendation Goes Wrong: Anomalous Link Discovery in Recommendation Networks Large-Scale Similarity Ranking Our research in pairwise similarity ranking has produced a number of innovative methods, which we have published at top conferences such as WWW, ICML, and VLDB. We maintain a library of similarity algorithms including distributed Personalized PageRank, Egonet similarity, Adamic Adar, and others. Learn more Ego-net Community Mining Applied to Friend Suggestion Reduce and Aggregate: Similarity Ranking in Multi-categorical Bipartite Graphs Research from VLDB 2016: Improved Friend Suggestion using Ego-Net Analysis SoK: The Evolution of Sybil Defense via Social Networks Public-private Graph Computation Our award-winning research on novel models of graph computation addresses important issues of privacy in graph mining. Specifically, we present techniques to efficiently solve graph problems, including computing clustering, centrality scores and shortest path distances for each node, based on its personal view of the private data in the graph while preserving the privacy of each user. Learn more Efficient Algorithms for Public-Private Social Networks KDD 2015 Best Research Paper Award: "Algorithms for Public-Private Social Networks" Streaming and Dynamic Graph Algorithms We perform innovative research analyzing massive dynamic graphs. We have developed efficient algorithms for computing densest subgraph and triangle counting which operate even when subject to high velocity streaming updates. Learn more Efficient Densest Subgraph Computation in Evolving Graphs TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size ASYMP: Async Message Passing Graph Mining ASYMP is graph mining framework based on asynchronous message passing. We have highly scalable code for Connected Components and shortest-path to a subset of nodes in this framework. Large-Scale Centrality Ranking Google’s most famous algorithm, PageRank, is a method for computing importance scores for vertices of a directed graph. In addition to PageRank, we have scalable implementations of several other centrality scores, such as harmonic centrality. Large-Scale Graph Building Our library GraphBuilder can convert data from a metric space (such as document text) into a similarity graph. GraphBuilder scales to massive datasets by applying fast locality sensitive hashing and neighborhood search. Some of Our Publications     Ego-net Community Mining Applied to Friend Suggestion Alessandro Epasto, Silvio Lattanzi, Vahab S. Mirrokni, Ismail Sebe, Ahmed Taei, Sunita Verma Proceedings of VLDB (2016)     Distributed Graph Algorithmics: Theory and Practice Silvio Lattanzi, Vahab S. Mirrokni WSDM (2015), pp. 419-420     Efficient Algorithms for Public-Private Social Networks Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, Vahab Mirrokni KDD (2015)     Connected Components in MapReduce and Beyond Raimondas Kiveris, Silvio Lattanzi, Vahab Mirrokni, Vibhor Rastogi, Sergei Vassilvitskii SOCC 2014     Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs Alessandro Epasto, Jon Feldman, Silvio Lattanzi, Stefano Leonardi, Vahab Mirrokni WWW (2014), pp. 349-360     A Local Algorithm for Finding Well-Connected Clusters Zeyuan Allen Zhu, Silvio Lattanzi, Vahab Mirrokni The 30th International Conference on Machine Learning, ICML 2013     Affiliation Networks Silvio Lattanzi, D. Sivakumar Proceedings of the 41st Annual ACM Symposium on Theory of Computing, ACM (2009), pp. 427-434 See More of Our Posts See More of Our Publications Research At Google Home Publications People Teams Outreach Blog Work at Google More Google Scholar YouTube Tech Talks Follow Us Google+ Twitter Google About Google Privacy Terms Feedback