Jure Leskovec

Life and career

Jure Leskovec belongs to the generation that got to ask an entirely new question: what happens to network science when you can measure a network with a hundred million nodes instead of a hundred?

He grew up in Slovenia and studied at the University of Ljubljana before going to Carnegie Mellon for a doctorate, working with Christos Faloutsos in the mid-2000s. This was exactly the moment when large-scale web, email, citation, and early social network data became available to researchers, and Leskovec's dissertation work took full advantage of it. Instead of studying static snapshots and asking whether they matched the degree distribution predicted by a model, he studied networks *over time* — and immediately found that the field's standard assumptions were wrong.

A postdoctoral year at Cornell with Jon Kleinberg followed, extending his range from empirical measurement toward the algorithmic side, and in 2009 he joined the Stanford computer science faculty, where he has remained. He served for several years as chief scientist at Pinterest, which gave his group a recommendation problem at genuine web scale and produced one of the first demonstrations that graph neural networks could run in production on billions of nodes. He later co-founded a company built around learning directly on relational database structure, and has held an affiliation with the Chan Zuckerberg Biohub, applying network methods to biomedical data.

His most durable contribution may be infrastructure rather than any single paper. SNAP — the Stanford Network Analysis Platform — provided both a fast graph analysis library and a curated public collection of large network datasets that became the default benchmark suite for a decade of research. He later led the Open Graph Benchmark effort for the same reason, having watched the graph learning literature accumulate results on small datasets whose conclusions did not survive contact with scale. He also co-authors *Mining of Massive Datasets*.

Key contributions

**Empirical laws of evolving networks.** With Kleinberg and Faloutsos, Leskovec showed that real networks *densify* over time — the number of edges grows superlinearly in the number of nodes, following a power law — and that their effective diameter *shrinks* rather than growing as $\log n$ would predict. Both findings contradicted the standard generative models of the day, which assumed constant average degree and slowly growing diameter. This forced new generative models: the Forest Fire model, which produces both effects through a recursive burning process, and the Kronecker graph framework, which builds a large graph by repeated Kronecker products of a small initiator matrix, yielding a few-parameter model that reproduces many observed structural properties and admits tractable fitting.

**The structure of communities at scale.** In a widely cited empirical study with Kevin Lang, Anirban Dasgupta, and Michael Mahoney, Leskovec systematically measured the quality of the best community — by conductance — as a function of community size across dozens of large networks. The resulting *network community profile* has a characteristic shape: conductance improves as you grow communities up to roughly a hundred nodes, and then steadily worsens. The implication is uncomfortable for the field's ambitions: large real networks do not decompose into large, well-separated modules. The best communities are small and often attached to the core by a thin "whisker," and beyond that scale the network is a single expander-like blob.

**Outbreak detection and cost-effective sensing.** With Andreas Krause, Carlos Guestrin, and others, Leskovec developed the CELF algorithm for selecting a set of nodes to monitor so that a spreading contagion is detected early. The technical foundation is submodularity of the detection objective, which yields the greedy $1-1/e$ guarantee; CELF's contribution is a lazy evaluation scheme that exploits submodularity to skip the vast majority of marginal-gain recomputations, giving order-of-magnitude speedups. It was validated on both a municipal water distribution network and on information cascades through blogs.

**node2vec.** With Aditya Grover, Leskovec introduced a node embedding method that reframes graph representation learning as a language modeling problem: generate random walks from each node, treat the walks as sentences, and apply skip-gram with negative sampling. The specific contribution is the *biased* walk, governed by two parameters $p$ and $q$ that interpolate between breadth-first and depth-first exploration. This matters because the two extremes capture different notions of similarity — BFS-like walks encode structural equivalence (nodes playing similar roles), DFS-like walks encode homophily (nodes in the same community) — and the right balance is task-dependent.

**GraphSAGE and inductive graph learning.** With Will Hamilton and Rex Ying, Leskovec addressed a limitation that made earlier embedding methods unusable in production: they are *transductive*, learning a lookup-table embedding per node, so a new node requires retraining. GraphSAGE instead learns *aggregator functions* that compute a node's representation from the features of its sampled neighborhood, recursively over $K$ hops. Because the learned object is a function rather than a table, embeddings can be computed for nodes never seen in training, and because neighborhoods are sampled to a fixed size, computation is bounded regardless of degree. The production version at Pinterest combined this with importance-based neighborhood sampling and efficient MapReduce inference to serve a recommender over billions of nodes.

**Expressiveness of graph neural networks.** With Keyulu Xu, Stefanie Jegelka, and Weihua Hu, Leskovec co-authored the analysis showing that message-passing graph neural networks are at most as powerful as the Weisfeiler–Lehman graph isomorphism test at distinguishing graph structures, and characterizing the aggregation functions — injective on multisets — that achieve that bound. The resulting Graph Isomorphism Network uses summation with a learned MLP rather than mean or max pooling, because mean and max lose multiset information. This paper gave the field its first clear theoretical ceiling and is now the standard reference point for expressiveness claims.

**Explanation and applications.** His group also produced GNNExplainer, which identifies the compact subgraph and feature subset most responsible for a given GNN prediction by maximizing mutual information, and a line of biomedical applications with Marinka Zitnik — including modeling polypharmacy side effects as link prediction on a multimodal drug–protein–side-effect graph.

In battle

Leskovec is the roster's clearest example of a specialist, and the numbers say so without ambiguity. He carries 114 problems, but his mean score across them is only 34.9, with a median of 30 and a range from 6 to 97. Seven problems put him at 80 or above; thirty-eight put him at 20 or below. That is not the profile of a generalist who is competent everywhere. It is a profile with a tall, narrow spike and a long flat plain, and knowing where the spike sits is the whole of playing him well.

The spike is graphs. His network category averages 67.9 across sixteen problems — nearly thirty points clear of his next-best category, classification at 39.5, and roughly double his overall mean. Inside that category he is close to unbeatable. **P274, "A hundred sensors for a city's water," scores 97**, the highest cell he holds anywhere, because the problem is effectively a restatement of his own municipal water-network study: the submodular objective, the greedy guarantee, and the CELF lazy-evaluation scheme that made the greedy algorithm tractable at city scale. Its sibling **P186, "Where to place the sensors," scores 96**, and **P272, "Learning on the molecule graph," also 96**, where the demand to reason about graph-isomorphism expressiveness limits lands directly on the Weisfeiler–Lehman ceiling he co-established. **P092, "Contagion on the network," scores 93** from his cascade and diffusion measurement work; **P270, "Choose the first hundred believers," scores 88** on influence maximization; **P268, "Who will know whom next year?," scores 86** on link prediction; and **P090, "The communities in the graph," scores 78**, tempered by the fact that his own community-profile results are partly a negative finding about how badly large graphs decompose. **P027**, semi-supervised learning from thirty labels and thirty thousand unlabeled points, scores 80 — the one non-network dominance, and it arrives through graph-based label propagation rather than through statistics.

Everything else falls away, and it falls away steeply. Games average 11.5, testing 13.0, information theory 15.0, search 15.5, reinforcement learning 17.0. His floor problems are worth naming because they mark the boundaries precisely: **P248, "The machine that overdosed," scores 6** — the Therac-25, a safety-critical concurrency and formal-verification failure from a decade before he entered the field, with no contact point in a career spent on analytical batch computation. **P113, "The first randomized trial," P141, "Why least squares, exactly?," P169, "The scratch on the disc," P199, "Prune the game tree, provably," and P236, "A thousand words, connected speech," all score 8.** Between them they cover classical experimental design, the foundations of estimation theory, coding theory, mid-century game-tree search, and early speech recognition — five distinct traditions, each of which he can read but none of which he built.

The pedagogical point is worth stating plainly rather than softening: Leskovec is a modern figure with an enormous citation record who nonetheless loses most of the problems in this game. The reach of his methods in the present is not the same as breadth across the history of the field, and the matrix scores the second thing. Played correctly he is a devastating card in a narrow band and dead weight outside it. If the problem has a large graph in it, play him and expect to win. Otherwise hold him.