We Mapped 45 Graph Algorithms Onto 20 Graph Databases

Why this survey exists

Graph databases have spent the last two decades moving from a niche curiosity to the default choice for anyone managing genuinely connected data, social networks, biological pathways, financial transaction webs, legal citation graphs. Most of the top ranked systems have converged on the property graph model, where both nodes and edges carry labels and key value properties, giving developers a rich enough schema to model real world entities without falling back to a relational join for everything.

What the authors noticed is that despite this convergence on a shared data model, there has been no systematic accounting of which of these databases can actually run the analytical workhorses of graph data science, centrality scores, community detection, shortest paths, similarity measures, out of the box. Vendors publish feature lists, but there was no independent, apples to apples map connecting a full taxonomy of algorithms to the databases that claim to support graph analytics. This survey builds that map, and then goes one step further by actually running the algorithms and timing them.

One deliberate scoping choice shapes everything that follows. The authors explicitly exclude machine learning and graph learning methods from the survey. Their reasoning is that in most graph databases, machine learning tasks are handled by importing an external library into a generic pipeline rather than by a method that is natively implemented inside the database engine itself. Data analytics algorithms, by contrast, are frequently built directly into the database as native procedures, which makes them the right object of study for a survey specifically about what property graph databases can do on their own.

Forty five algorithms, seven categories

The paper organizes its algorithm catalog around the type of result each method produces rather than the mathematics behind it, which makes the taxonomy easy to apply when you already know what question you are asking of your data.

Centrality algorithms split further into two philosophically different camps. Neighbor based methods, Degree Centrality, Eigenvector Centrality, PageRank, and HITS, judge a node’s importance by looking at immediate connections or the recursive influence of neighbors. Path based methods, Betweenness Centrality, Closeness Centrality, Harmonic Centrality, and Katz Centrality, instead analyze the global topology by tracing paths across the whole network, which is why they are better at surfacing nodes that act as structural bridges rather than nodes that simply have a lot of neighbors.

Community detection methods split along a similar four way line. Connectivity based methods like Weakly and Strongly Connected Components rely purely on reachability. Propagation based methods like Label Propagation and its Speaker Listener and HANP variants use iterative local consensus, where each node adopts whatever label the majority of its neighbors currently hold. Metric based methods like Modularity Optimization and Louvain instead try to directly maximize a quality function that rewards dense internal connections. Attribute based methods like K means Clustering ignore the graph structure entirely and group nodes purely by property similarity, which is a genuinely different kind of community detection than the other three families.

A closer look at PageRank, because it is everywhere

PageRank deserves particular attention since it shows up repeatedly throughout the survey’s benchmarks. Originally developed to rank web pages by analyzing the network of hyperlinks between them, PageRank works on the principle that a node’s importance depends on the importance of the nodes linking to it, solved iteratively as an equation involving a damping factor that represents the probability a random walker loses interest and jumps to an arbitrary node rather than following a link. The related HITS algorithm, standing for Hyperlink Induced Topic Search, computes two separate scores instead of one, an authority score for nodes that are frequently pointed to and a hub score for nodes that frequently point to good authorities, useful for distinguishing a well cited reference from a well curated index.

How the databases stack up on paper

Before running a single benchmark, the authors mapped the twenty most popular graph databases, ranked by the independent DB Engines listing captured in January 2026, against the property graph model and against algorithm support. The result narrows the field considerably.

Of the twenty systems on the full popularity list, only these ten support the property graph model, and only ten of the twenty support some form of graph data analytics, a pair of subsets the authors note almost completely overlap. That overlap is not an accident. It reflects the fact that the property graph model, with its explicit node and edge labels and properties, gives an analytics engine the structural hooks it needs to run algorithms like Louvain or Betweenness Centrality directly against the stored data rather than requiring an export step first.

The survey groups how these databases actually implement analytics into three broad strategies. The first is a built in native library, the approach Neo4j and TigerGraph take most comprehensively, where algorithms ship as first party procedures callable directly against the database. The second is integration with an external framework, the approach Azure Cosmos DB and JanusGraph lean on, projecting data out to Apache Spark or Apache Hadoop for the actual computation. The third is hybrid, exemplified by Memgraph’s MAGE library, which bundles a large set of built in algorithms while also making it easy to reach out to external libraries like NetworkX when something is missing.

That observation about query language integration points to a real gap in the field. Shortest Path is the one algorithm that has started to earn first class syntax inside query languages themselves, Cypher’s SHORTEST construct, Gremlin’s traversal centric step chains, and the emerging GQL standard all treat path finding as part of the pattern matching vocabulary rather than as a bolted on procedure call. Everything else, PageRank, Louvain, Betweenness Centrality, still gets invoked the way you would call a stored procedure, with a syntax like CALL gds.pageRank rather than anything resembling a native language construct like ORDER BY PageRank or GROUP BY Louvain. The authors flag this as a real opportunity for future query language design.

Putting three databases through the same benchmark

Of the ten databases supporting the property graph model with analytics coverage, the authors narrowed their hands on benchmark to three, Neo4j, Memgraph, and TigerGraph, selected because each has an open source or free tier version, each is among the most widely used engines by the DB Engines ranking, and together they cover the algorithm catalog most extensively. Neo4j and Memgraph ran on a fourteen core Intel Xeon server with 128 gigabytes of RAM and SSD storage. TigerGraph, whose free on premise tier restricts full access to its analytics library, ran instead on an Amazon AWS cloud instance with eight virtual CPUs and matching 128 gigabytes of RAM, chosen specifically because it represents the highest performance environment available to a researcher without an enterprise license.

Synthetic graphs, three topologies, sizes doubling from 100,000 to 3.2 million nodes

The first benchmark round used synthetic graphs generated under three classic network models, Random, Scale Free, and Small World, holding edge density constant while doubling node count at each step up to 3.2 million nodes and more than 100 million edges at the largest scale. Three algorithms were tested at every size and topology, PageRank, Label Propagation, and Weakly Connected Components, each repeated ten times per configuration and averaged.

A consistent pattern emerged across every single database tested. Algorithms ran fastest on Small World networks, a result the authors attribute to the combination of a high clustering coefficient and a short average path length, which together mean information needs far fewer iterations to propagate across the whole graph. Random and Scale Free networks produced broadly similar execution times to each other, with two small but consistent exceptions. Label Propagation ran slightly faster on Random networks, likely because the more even distribution of edges again favors fewer propagation iterations, while PageRank ran faster on Scale Free networks, likely because a small number of high degree hub nodes let the algorithm converge on the important nodes more quickly than when connections are spread evenly.

Five real world graphs, five different personalities

Synthetic graphs are convenient for isolating the effect of pure size, but real graphs rarely look like textbook models. The second benchmark round used five datasets drawn from the Open Graph Benchmark, each chosen because its network characteristics diverge sharply from the others.

Seven algorithms were run against all five datasets, PageRank, Betweenness Centrality, Label Propagation, Weakly Connected Components, Jaccard Similarity, Shortest Path, and Breadth First Search, each repeated ten times with consistent random node selections used across all three databases for the algorithms that require picking specific nodes.

The headline result here is that there is no overall winner. Neo4j consistently led on PageRank across every one of the five datasets, and it also consistently outperformed the other two on Weakly Connected Components. Memgraph, meanwhile, significantly outperformed both competitors on Betweenness Centrality in four out of five datasets and was consistently the fastest at Label Propagation and Breadth First Search. TigerGraph was generally the slowest of the three across most tests, but its execution times were also the least sensitive to which dataset it was running against, staying relatively flat across topologies where Neo4j and Memgraph both showed sharper swings depending on node count, edge count, or number of disconnected components.

A few dataset specific quirks are worth calling out because they illustrate how sensitive these algorithms are to structure rather than raw size. On the Bio-KG dataset, the densest of the five in terms of edges per node, Memgraph’s Shortest Path performance dropped noticeably, which the authors attribute to its higher edge count rather than its node count. On the HIV dataset, which is dominated by tens of thousands of tiny disconnected molecular components, TigerGraph performed particularly poorly while Neo4j and Memgraph both benefited, since a graph broken into many small pieces is comparatively cheap for traversal heavy algorithms once you are only ever searching within one small component at a time.

What this means for choosing a graph database

The practical upshot for anyone shopping for a graph database is that the question is never simply which system is fastest. It is closer to a three part question, which algorithms do you actually need, what does your graph’s topology look like, and how much does licensing flexibility matter to you.

If your workload leans heavily on PageRank style centrality or connected components analysis and you want an open source option with a mature ecosystem, Neo4j’s results here are hard to beat. If Betweenness Centrality or traversal algorithms like Breadth First Search sit at the center of your pipeline, Memgraph’s advantage was large enough in this survey to be worth testing directly against your own data before committing elsewhere. If your priority is predictable, topology agnostic performance rather than chasing the fastest number on any single algorithm, and you can work within TigerGraph’s licensing model, its consistency across five very differently shaped real world graphs is itself a meaningful selling point, particularly for teams that cannot predict in advance what kind of graph their production data will eventually look like.

It is also worth remembering what this survey deliberately leaves out. Machine learning and graph learning methods, the kind of workflow where you would train a graph neural network or compute node embeddings, are explicitly excluded, because in nearly every one of these databases those tasks still get routed out to an external library rather than run as a native procedure. If your project depends heavily on that kind of workload, this survey tells you about the data analytics layer beneath it, not about the machine learning layer sitting on top.

Honest limitations

The authors are direct about the boundaries of their own study. The scope was deliberately restricted to data analytics algorithms and explicitly excludes machine learning and graph learning techniques, on the grounds that those tasks are not yet consistently native to graph database engines the way data analytics procedures are. The deeper analysis and the hands on benchmark were both limited to the top ranked systems by usage, and specifically to those supporting the property graph model, which means closed source or lower ranked systems that might still offer compelling analytics support were not evaluated in the same depth. The performance benchmark itself was restricted to the three systems offering free or open source access, Neo4j, Memgraph, and TigerGraph, a choice made deliberately to keep the results reproducible and accessible to researchers without an enterprise license, but one that leaves systems like Amazon Neptune Analytics or ArangoDB’s Graph Analytics Engines outside the head to head comparison despite each supporting a meaningful subset of the same algorithm catalog.

Conclusion

What makes this survey worth reading in full rather than skimming for the benchmark charts is the map it draws before it ever runs a single query. Forty five algorithms sorted into seven categories, checked against twenty databases, filtered down to ten that actually support any of it natively, is the kind of unglamorous cataloging work that rarely gets done well because it takes far longer than it takes to write about a single new algorithm or a single new system. That map alone would justify the paper even without the benchmarks that follow it.

The benchmark results add a second layer that matters just as much in practice. Popularity rankings and marketing pages tell you almost nothing about whether a specific algorithm will run fast on your specific data, and this survey demonstrates just how much that answer depends on the interaction between algorithm, database engine, and graph topology all at once. Neo4j’s edge on PageRank, Memgraph’s edge on Betweenness Centrality, and TigerGraph’s steadiness across five structurally different real world graphs are not conclusions that could have been guessed from documentation alone.

The observation that data analytics algorithms are still treated as external procedure calls rather than as native constructs inside query languages like Cypher, GQL, or GSQL is perhaps the most forward looking part of the paper. As the field moves toward standardizing GQL as a genuine successor to SQL for graph data, the authors make a reasonable case that centrality and community metrics deserve the same first class treatment inside pattern matching queries that shortest path algorithms are only just beginning to receive.

Anyone actively evaluating a graph database for a new project, rather than defaulting to whichever name shows up first on a ranking site, now has a concrete, reproducible reference point for what forty five algorithms actually cost across three of the most credible open options on the market, tested against graphs that range from a few thousand densely interacting nodes to more than a million loosely connected ones.

Frequently asked questions

What is a property graph database and how is it different from a relational database

A property graph database represents both the schema and the data instances as a graph, where nodes and edges are explicitly labeled and can carry key value property pairs. Queries are designed around graph specific operations like traversal and pattern matching rather than the table joins that relational databases rely on, which makes property graph databases considerably more efficient for workloads centered on network structure.

Which graph database performed best overall in this survey

No single system won across every test. Neo4j consistently led on PageRank and Weakly Connected Components, Memgraph significantly outperformed the others on Betweenness Centrality and traversal algorithms like Breadth First Search, and TigerGraph, while generally the slowest, showed the most consistent performance across differently shaped real world graphs.

Why does graph topology affect performance so much

Algorithms that rely on iterative propagation or path finding need more steps to converge on graphs with long average path lengths and low clustering. Small World networks, which combine short paths with tight local clustering, consistently processed faster across every database and every algorithm tested than Random or Scale Free networks of the same size.

Does this survey cover machine learning on graphs

No. The authors explicitly exclude machine learning and graph learning methods from the survey, since in most graph databases those tasks are still routed through generic external pipelines rather than implemented as native database procedures, which was the specific scope this survey set out to map.

Why were only three databases included in the performance benchmark

Neo4j, Memgraph, and TigerGraph were chosen because each offers a free or open source version, each ranks among the most widely used graph databases according to DB Engines, and together they cover the survey’s forty five algorithm catalog more extensively than any other combination of systems that also meet the open access requirement.

How many of the top twenty graph databases actually support graph data analytics natively

Only ten of the twenty most popular graph database systems ranked by DB Engines support any native graph data analytics algorithms at all, and that subset almost completely overlaps with the databases that support the property graph data model in the first place.

Throughout this piece we also link back to our broader coverage of computer vision research on aitrendblend.com.

Related on aitrendblend