8 ms·

The Future Is Big Graphs: A Community View on Graph Processing Systems

144 points by Anon84 5y ago

triska 5y ago
Very interesting! I especially like the expressed interest in logic-based approaches for reasoning about graphs. Quoting from the article: "Logic-based and declarative formalisms. Logic provides a unifying formalism for expressing queries, optimizations, integrity constraints, and integration rules. Starting from Codd's seminal insight relating logical formulae to relational queries, many first order (FO) logic fragments have been used to formally define query languages with desirable properties such as decidable evaluation. Graph query languages are essentially a syntactic variant of FO augmented with recursive capabilities. [...] The influence of logic is pivotal not only to database languages, but also as a foundation for combining logical reasoning with statistical learning in AI. Logical reasoning derives categorical notions about a piece of data by logical deduction." This interest could be good news for vendors of logic programming languages such as Prolog and its syntactic subset Datalog. These languages enable very convenient reasoning about graphs and allow both storing and querying the database with the same simple language elements that can themselves also be analyzed and reasoned about with the same formalism. Imagine how convenient it would be to have a large graph database represented as a set of Prolog clauses that can be queried, run and analyzed with an efficient Prolog system! The data itself, queries, and any desired transformation and augmentation could be uniformly expressed in this way.
- sfvisser 5y ago
  This has been the semantic web dream for decades now.
  - triska 5y ago
    Yes indeed, although the semantic web chose a much more convoluted set of technologies without the syntactic and conceptual coherence and simplicity of actual logic programming languages, thus making reasoning about everything extremely complex and inconvenient in comparison. I think this is a severe handicap when using these technologies in practice. All automated reasoning is by necessity exclusively syntactic in nature since the meaning of processed symbols is inaccessible to a machine, therefore a careful consideration of syntactic aspects is very important to ensure easy analysis and meta-interpretation of logic programs and queries. As I see it, a good formalism for knowledge representation makes it easy to reason about the knowledge and also about all programs and queries that themselves reason about the knowledge, enabling easy meta-interpretation and coherent extension languages.
- beaconstudios 5y ago
  well if you think about it, a triple store is basically a database of propositional logic statements.
- LukeEF 5y ago
  I know at least one vendor of a prolog based graph database [1] that hopes the interest continues to grow. [1] https://github.com/terminusdb/terminusdb https://github.com/terminusdb/terminusdb
wirthjason 5y ago
Anyone have an idea how a graph database like Neo4J is implemented? I imagine it as a unique query language (cypher) sitting on top of a traditional relational database.
- heinrichhartman 5y ago
  Neo4J is a native database build on the JVM. It does not use any underlying relational DBs. IIRC, Graph links are implemented as direct references to other node objects (if they are in memory), which make traversal way faster than what you would get with relational DBs.
- thanatos519 5y ago
  RedisGraph uses OpenBLAS sparse matrices which deliver astounding performance. It's not as feature-complete as Neo4J but it's a promising start.
- malthejorgensen 5y ago
  I’d imagine it’s more like an adjacency list structure with various indexes (similar to a regular relational dbs) to allows lookups based on node properties
- rajman187 5y ago
  Neo4J uses index-free adjacency which means each node is storing the address of where its edges point to. This raises an interesting question about “big” graphs and distributed systems—-storing the address in memory across machines. So Neo4J, last I looked into it, is very fast for reads using a master-slave setup but may not scale well beyond a single machine. Other approaches such as RedisGraph use OpenBLAS, but again you’re limited to a matrix representation. And yet others, like TitanDB (bought by DataStax and open-source community forked into JanusDB) use graph abstractions that sit on top of distributed systems (HBase, Cassandra, Dynamo, etc) and these rely on adjacency lists and large indices. So the idea of “big graph” has been around for at least 6 years in the NoSQL world, but indeed everything is not a graph problem, tempting as that may be to claim. Good article on native graph representation: https://dzone.com/articles/letter-regarding-native-graph https://dzone.com/articles/letter-regarding-native-graph
leetrout 5y ago
A previous coworker now works at Katana Graph and I've been keeping an eye on what they claim to be doing. Sounds very interesting. https://katanagraph.com/ https://katanagraph.com/
christkv 5y ago
Distributing a graph is a really hard problem does anyone know what the state of this is?
- topicseed 5y ago
  Dgraph and ArangoDB seems to be doing it well.
  - junon 5y ago
    We ended up ditching Arango for a new project, despite it having decent enough graph handling. This is because, unlike many other DBs (namely Mongo, which we're trying desperately to move away from), you can't spin up a new instance and allow the application to idempotently initialize it. The multi-modal engine of Arango seems great, but the DX surrounding its use is a bit subpar, and would greatly shift a lot of burden to the environment config, which only adds to potential security vulnerabilities. This is only made worse by the fact it has a severely limited granularity with security permissions.
    - ta988 5y ago
      Security is another big issue with the open graph databases. Some closed ones have ok mechanisms. But we are not there yet.
    - redwood 5y ago
      Out of curiosity, are you self managing the database today or using a service?
      - junon 5y ago
        Self hosting. Services don't usually have as tight of security as I'd like.
        redwood 5y ago
        I would argue that it's a common misconception: the risk of doing something wrong when you're self managing every layer means you're opening yourself up to so much surface area that needs to be done with expert precision. Obviously services are not some magic wand either, EG the recent Microsoft snafus. But they're a third-tier cloud player
Anon84 5y ago
If you're interested in learning more about graphs, you might find my "Graphs for Data Science" substack: https://graphs4sci.substack.com/ https://graphs4sci.substack.com/ where I work though using graph perspectives to analyze real world datasets.
graphviz 5y ago
Someone on the internet is wrong! Or maybe just partially correct. This is very interesting work. There is some selling going on, not discussing enough about the issues that drove the database community toward relational databases and away from "network" databases in the 1970s. If you think of visualization systems as a microcosm of more general computing, notice people need more than graphs - they need all kinds of tables, charts, maps, and other things. Same with "graph databases". This area does exist because the database community underinvested in computing on graphs and networks, the same as it did with usability for a long time. It is still catching up but there is a lot of great work. Another problem is helping users to understand the cost of what they are trying to compute. Select and join? I can estimate that. Find betweenness centrality of a large network? Find a tour that visits all the cycles of a network exactly once? All the edges? All nodes? Oops. What about graph object types? Is it OK to mix them? Sometimes I wonder arguments that "graph databases are [more] efficient for linked structures." After 20 or 30 years of intense R&D, relational databases already seem pretty efficient for computing with relationships.
- _wldu 5y ago
  SQL struggles with hierarchical data (trees), which are graphs.
  - pphysch 5y ago
    In practice most hierarchies are shallow (or poorly designed) Country, Province/State, City, Neighborhood/ZIP, Building, Room. 5 jumps to go from planetary to personal. 5 JOINs is not unreasonable.
    - deleted 5y ago
      [deleted]
ThePhysicist 5y ago
I think graph processing has great potential for use cases where the data model is heterogeneous and the structure of a problem really can be modeled as a graph problem. I think the tooling and the technologies are still not nearly as mature as e.g. relational databases and most developers have very little exposure to graph models, so adoption is still quite low, but will probably rise as the cloud providers offer hosted graph databases. In 2015 I was quite excited for TitanDB and the TinkerPop stack but I think the acquisition of the team behind it (Aurelius) by DataStax kind of sucked the air out of the community edition. As far as I understand Amazon is using many ideas and concepts from TitanDB in their Neptune graph database, but unfortunately they don't seem to care to open-source it. I don't think graph databases & graph processing will become mainstream tough, as they're just not a good fit for most problems.
- ta988 5y ago
  Neptune sucked the air out of blazegraph as well... It is a constant problem. Graph databases will only ever become more mainstream when we get a real postgresql-level database in term of reliability, maintenance and trust in its evolution.
  - zozbot234 5y ago
    PostgreSQL is a fine graph database. It would be nice if it supported the graph-like query language that's now being standardized as an extension to SQL, but other than that it works quite well.
    - ta988 5y ago
      It is pretty slow for most graph operations though. It works ok for simple things, especially with the recently added functions.
      - zozbot234 5y ago
        Well yes, if you need to run actual graph algorithms on network data I agree that pgSQL (or any general purpose database, including "semantics" oriented graph db's) is not the best.
deleted 5y ago
[deleted]
chubot 5y ago
It feels like this should have a citation to Scalability! At What COST? https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf https://www.usenix.org/system/files/conference/hotos15/hotos... which evaluates distributed graph processing frameworks (circa 2015) on various problems and shows that they can be slower than a single threaded program on a laptop. They have a data set with 105 M nodes and 3.7B edges that fits in 14 GB, which all fits in memory (at least 128-256 GB of memory should be taken for granted in these types of problems). Maybe with a clever encoding you can store the entire social network of the world, or at least a FB-sized one. (Storing nodes as integers is efficient and useful for many graph algorithms. You can later "join" with the ancillary data using a fast non-graph distributed processing framework). This article mentions the challenges but doesn't mention the solution of simply using a single machine for big graphs: Even seemingly minute HPAD variations, for example the graph's degree distribution, can have significant performance implications. Graph processing systems rely on complex runtimes that combine software and hardware platforms. It can be a daunting task to capture system-under-test performance—including parallelism, distribution, streaming vs. batch operation Anyone who has done programming with say MapReduce knows that it can be very elegant and fun, but also limiting. This is even more true of graph processing frameworks, as the article explains. If you simply put everything in memory and write native code (which isn't hard at all for batch jobs), then you have so much more flexibility with ANY algorithm, and especially graph algorithms. This type of programming is also fun! You don't have to fit your problem into the framework and switch frameworks when it doesn't fit (or more likely just accept 10-1000x performance decrease when it doesn't fit). --- Abstract: We offer a new metric for big data platforms, COST, or the Configuration that Outperforms a Single Thread. The COST of a given platform for a given problem is the hardware configuration required before the platform outperforms a competent single-threaded implementation. COST weighs a system’s scalability against the overheads introduced by the system, and indicates the actual performance gains of the system, without rewarding systems that bring substantial but parallelizable overheads.
amw-zero 5y ago
I don't have a number of course, but I believe that almost all relational db models are more naturally modeled as graphs. In fact, all normalized relational db models that use foreign keys are just implementing a graph - foreign keys represent edges between nodes. has-many, has-one, and many-to-many are all graph relationships. The relational model + foreign keys is just one way to encode a graph.
- pphysch 5y ago
  Yeah, tables/rows are basically vertices with 1 label & many properties*, and FKs are labeled edges without properties. But, you can easily implement edge properties with many-to-many tables, at the cost of an extra JOIN. In practice, this is a useful and efficient species of graph. I think many people get baited by Neo4j's marketing without really understanding relational models and RDBMS (I sure did). * With the (often true) assumption that many vertices will follow the same normalized schema.
- bawolff 5y ago
  Graphs are the least restricting data model. I think everything is easier to model as a graph, because its just things (verticies) and how they are related (edges). You mostly get to skip the modelling step. The benefit of modelling as a relational db is that it forces you to put the data in a form that's easy to work with from a computer perspective.
danieljh 5y ago
The Future is Tiny Graphs! [1] In the style of "Scalability! At What COST?" I've started a side-project bringing succinct data structures (rank/select [2], elias-fano coding) and modern instruction sets (popcount, pdep) to graphs. For some reason the article doesn't mention the field of graph compression and I think it shows: for example most if not all popular open source routing engines don't do anything regarding graph compression. It's time to change that! Reach out to me (preferably on the Github project) if you want try some ideas :) [1] https://tinygraph.org https://tinygraph.org [2] http://www.cs.cmu.edu/~dga/papers/zhou-sea2013.pdf http://www.cs.cmu.edu/~dga/papers/zhou-sea2013.pdf
- LukeEF 5y ago
  We built TerminusDB[1], our OSS knowledge graph, using succinct data structures. As we have a immutable delta encoding approach to allow domain teams to build and curate data products that they then share, this has been a very fruitful combination. We wrote a technical white paper all about it! [2] [1] https://github.com/terminusdb/terminusdb https://github.com/terminusdb/terminusdb [2] https://github.com/terminusdb/terminusdb/blob/dev/docs/whitepaper/terminusdb.pdf https://github.com/terminusdb/terminusdb/blob/dev/docs/white...
zomglings 5y ago
I have spent the last 7 years building ontologies (knowledge bases), small and large. Like with most tech articles, this one is pushing a very specific point of view that is relevant to megacorporations but certainly not to most companies that would benefit from the deployment of graph-structured knowledge bases. Unless a company has tons of extra cash to burn using technologies like neo4j, Spark, etc., they are better off just building an ontology on top of their existing datastores. The work on the semantic web in the 2000s added a lot of valuable ideas and I see a tendency to downplay these ideas in favor of new technologies. Storing relationships as RDF triples and building indices that are well-suited to your queries will be good enough for the majority of people who need an ontology. I have found that graph-based systems don't model time well. When you are building a knowledge base, you often need to understand how knowledge has changed over time. You may want to relate facts across time or understand what the state of knowledge was within a given period of time. This usually takes extra work. Another thing that I have found these graph-based systems to do poorly is the management of storage classes for different types of data. If you are building a graph knowledge base, not all the information in your knowledge base will be consumed in the same way. If your knowledge base is sufficiently large, you will want to store less frequently accessed data on cheaper storage (e.g. HDD or even object storage like S3) and hotter data on more expensive storage (SSD or even maybe keep it in memory). I have always had to write this code by myself and haven't found a tool that helps to manage this very importance concern in ontology building. That turned into a bit of a ramble, but damn ontologies are cool. :)
- amw-zero 5y ago
  I am honestly intrigued any time I hear anyone mention RDF. You have had success using it? It wasn't exactly clear how you used it from what you said.
  - zomglings 5y ago
    I only use RDF triples as a storage format for edges. I don't normally take advantage of triple stores (e.g. apache Jena), sparql query engines, etc. It's just a simple format and it's easy to build different types of query/analysis capabilities around. The only thing that's a little awkward is applying types to items in an rdf triple (in a way that's computationally cheap). Typing is a general problem, though.
rrwright 5y ago
I’m the creator of thatDot Connect [1], a distributed asynchronous streaming graph interpreter, where we’ve been working on exactly this problem for about 7 years now. Scalable distributed graph processing has so many applications! We were fortunate enough to be funded by DARPA for a while working on automated APT detection for cyber-security. Some of our recent work has shown linear scalability of this approach on large clusters at high throughput. For example, we got to half a million complex graph events ingested per second on a combined read/write workload and could have just kept scaling. We’re in the process of writing up this work and sharing all the details. [1] https://www.thatdot.com/technology/ https://www.thatdot.com/technology/
molham 5y ago
We usually talk about several paradigms for data management and programming: navigational (e.g. CODASYL, OO databases/languages, most graph DBs), tensor-based (e.g. MOLAP, Matlab, TensorFlow, Pytorch), Map-Reduce (e.g. Hadoop and Spark before they started to disown their MR heritage). Semistructured (e.g. JSON) and dataframes (e.g. Pandas) are also important abstractions. These abstractions can be captured in the relational paradigm — in other words we can think of them as special cases and represent them as views on relational models. It is clear from the last 50 years of our industry that the relational paradigm (eventually) always wins. It wins because it separates the what from the how and automates away a bunch of tricky programming that we have to do with the more imperative paradigms. — the OLTP workload was originally supported by navigational systems and then switched to relational systems mostly based on 3rd normal form schemas — the OLAP workload was originally supported by multi-dimensional array (tensor) systems then switched to relational systems based on star and snowflake schemas — the Big Data workload was originally supported by map-reduce systems then switched to relational systems based on star/snowflake + JSON schemas. I believe that the Graph (via navigational), Reasoning (via procedural), and ML (via dataframe and tensor) workloads will move to relational systems based on graph normal form (GNF) schemas. Those relational systems won't be built like the SQL-based systems of today. They will need new relational language extensions, new semantic optimizers, new optimal join algorithms, materialized views that are maintained efficiently, new data structures, etc. We are working on such a system at RelationaAI. We’re in limited preview now but hope to have an open preview by early next year.
- rambojazz 5y ago
  > It is clear from the last 50 years of our industry that the relational paradigm (eventually) always wins You cannot make a foreign key to link two different tables with RDBMSes. It requires to make another table. With graphs instead this is easy, just make a link from/to any node. With RDBMSes the schema is fixed. With RDBMSes you cannot have "metaproperties" (or properties about properties). With graphs you can easily say {caesar born{source "foobar"} "100BC"}. With RDBMSes this quickly becomes a mess to handle when you have more properties. These are just some use cases why relational does not always win.
lmeyerov 5y ago
Some slightly different views based on our experiences with startups/techco's/enterprises/govs. A lot of what there is true, but at the same time, we've been seeing major appetite in 2 areas that lead to quite different directions from the article. To be clear, I do think the CACM authors are right about a lot of what is commercially + academically popular in big graph land today. Ex: Powering better knowledge graphs, especially for NLP neural network empowered use cases (BERT/GPT). Ex: Enriching inputs into traditional neural network inference calls, like a user 360 before making a recommendation. I expect graph DBs to keep improving to help with theses. At the same time, working with teams from first-principles to help skate to where the puck is going, we've come to 2 overall different priorities where those ideas aren't the primary technology enablers for big graph use cases in terms of engineering + big $$$$ enablers. Broadly, it's useful to think though what Data Analysts are doing and what Data Scientists are doing: 1. Graph BI: Similar to Tableau, Looker, and more autoML-y successors, there are a LOT of analysts who are trying to better understand all that data in their data warehouses. Operational data in Splunk/ELK, transactions & business data in SalesForce CRM / RedShift transactions / etc. Graph questions are powerful here. Graphs are all about relationships like user/cohort behavior, so opens up a lot of questions/answers for analysts, especially if made accessible. However, from a data engineering perspective, copying that data into graph DBs as a second system of record is historically a "now you have 2 problems" thing, and part of why most data lake projects fail. So we've been focusing on building graph query pushdown + virtual fabric style projects that expose graph thinking over your existing data infra. The discussion in the CACM article on dynamic graphs touches on this, but that's only one piece of that problem. Getting analyst graph insights over warehouses as ~easy as it is today for basic time questions on events requires a lot more. Surprisingly, we suspect so much so that it may commoditize the particular choice of graph compute engine (vs say connectors/virtualization/UI/automation/AI.) 2. Graph AI: Traditional neural networks have been increasingly dominating due to strong ability to combine categorical & continuous data around entities of interest (think computer vision realizing some pixels are a cat)... but struggled to leverage relationship structure: imagine a communication or transaction between people/devices/companies with rich histories & communities. Being able to fuse those matters a LOT on commercial contexts, so we'd been watching graph neural networks for awhile. Over the last ~2 years, with the mounting focus by the AI community, key problems around performance, heteorgeneous data, etc., have been getting solved, so GNNs are starting to show up in all sorts of places now. Interestingly, most companies using them don't plug graph databases or knowledge graphs or even traditional graph compute engines into them. If you look at how pytorch, dgl, etc. are being built, they largely ignore what traditional graph infra vendors focus on as 1-3 magnitudes too slow, and overall, wrong tool for the job: different problem space. In both cases, teams building/using graph DB or graph compute engines, like the CACM authors, get enlisted to help as natural stakeholders for pieces of the problem. Likewise, they naturally want to help + grow their scope. Unfortunately, from a perspective of "you're lucky to do even 1-3 things well", they've been struggling to provide the needed end-to-end solutions. There are plenty of critical & fascinating scale, design, + use case challenges to tackle far beyond the core db/compute engine perspective here. Anyways, this is an awesome time for this stuff so I encourage getting involved! We're actively hiring for help creating these new categories (all levels: fullstack, UI, BI, data, AI) + launching projects with lighthouse design partners, so if either is relevant, please reach out! Likewise, traditional graph DB/compute is important too (see: CACM article), and been a no-brainer for attracting most of the VC attention for the last few years due to being a traditional DB play, and we've enjoyed partnering with friends at them, so I'd recommend looking at those companies as well.

144 points by Anon84 5y ago

Very interesting! I especially like the expressed interest in logic-based approaches for reasoning about graphs. Quoting from the article: "Logic-based and declarative formalisms. Logic provides a unifying formalism for expressing queries, optimizations, integrity constraints, and integration rules. Starting from Codd's seminal insight relating logical formulae to relational queries, many first order (FO) logic fragments have been used to formally define query languages with desirable properties such as decidable evaluation. Graph query languages are essentially a syntactic variant of FO augmented with recursive capabilities. [...] The influence of logic is pivotal not only to database languages, but also as a foundation for combining logical reasoning with statistical learning in AI. Logical reasoning derives categorical notions about a piece of data by logical deduction." This interest could be good news for vendors of logic programming languages such as Prolog and its syntactic subset Datalog. These languages enable very convenient reasoning about graphs and allow both storing and querying the database with the same simple language elements that can themselves also be analyzed and reasoned about with the same formalism. Imagine how convenient it would be to have a large graph database represented as a set of Prolog clauses that can be queried, run and analyzed with an efficient Prolog system! The data itself, queries, and any desired transformation and augmentation could be uniformly expressed in this way.

sfvisser 5y ago
This has been the semantic web dream for decades now.
- triska 5y ago
  Yes indeed, although the semantic web chose a much more convoluted set of technologies without the syntactic and conceptual coherence and simplicity of actual logic programming languages, thus making reasoning about everything extremely complex and inconvenient in comparison. I think this is a severe handicap when using these technologies in practice. All automated reasoning is by necessity exclusively syntactic in nature since the meaning of processed symbols is inaccessible to a machine, therefore a careful consideration of syntactic aspects is very important to ensure easy analysis and meta-interpretation of logic programs and queries. As I see it, a good formalism for knowledge representation makes it easy to reason about the knowledge and also about all programs and queries that themselves reason about the knowledge, enabling easy meta-interpretation and coherent extension languages.
beaconstudios 5y ago
well if you think about it, a triple store is basically a database of propositional logic statements.
LukeEF 5y ago
I know at least one vendor of a prolog based graph database [1] that hopes the interest continues to grow. [1] https://github.com/terminusdb/terminusdb https://github.com/terminusdb/terminusdb

wirthjason 5y ago

Anyone have an idea how a graph database like Neo4J is implemented? I imagine it as a unique query language (cypher) sitting on top of a traditional relational database.

heinrichhartman 5y ago
Neo4J is a native database build on the JVM. It does not use any underlying relational DBs. IIRC, Graph links are implemented as direct references to other node objects (if they are in memory), which make traversal way faster than what you would get with relational DBs.
thanatos519 5y ago
RedisGraph uses OpenBLAS sparse matrices which deliver astounding performance. It's not as feature-complete as Neo4J but it's a promising start.
malthejorgensen 5y ago
I’d imagine it’s more like an adjacency list structure with various indexes (similar to a regular relational dbs) to allows lookups based on node properties
rajman187 5y ago
Neo4J uses index-free adjacency which means each node is storing the address of where its edges point to. This raises an interesting question about “big” graphs and distributed systems—-storing the address in memory across machines. So Neo4J, last I looked into it, is very fast for reads using a master-slave setup but may not scale well beyond a single machine. Other approaches such as RedisGraph use OpenBLAS, but again you’re limited to a matrix representation. And yet others, like TitanDB (bought by DataStax and open-source community forked into JanusDB) use graph abstractions that sit on top of distributed systems (HBase, Cassandra, Dynamo, etc) and these rely on adjacency lists and large indices. So the idea of “big graph” has been around for at least 6 years in the NoSQL world, but indeed everything is not a graph problem, tempting as that may be to claim. Good article on native graph representation: https://dzone.com/articles/letter-regarding-native-graph https://dzone.com/articles/letter-regarding-native-graph

leetrout 5y ago

A previous coworker now works at Katana Graph and I've been keeping an eye on what they claim to be doing. Sounds very interesting. https://katanagraph.com/ https://katanagraph.com/

christkv 5y ago

Distributing a graph is a really hard problem does anyone know what the state of this is?

topicseed 5y ago
Dgraph and ArangoDB seems to be doing it well.
- junon 5y ago
  We ended up ditching Arango for a new project, despite it having decent enough graph handling. This is because, unlike many other DBs (namely Mongo, which we're trying desperately to move away from), you can't spin up a new instance and allow the application to idempotently initialize it. The multi-modal engine of Arango seems great, but the DX surrounding its use is a bit subpar, and would greatly shift a lot of burden to the environment config, which only adds to potential security vulnerabilities. This is only made worse by the fact it has a severely limited granularity with security permissions.
  - ta988 5y ago
    Security is another big issue with the open graph databases. Some closed ones have ok mechanisms. But we are not there yet.
  - redwood 5y ago
    Out of curiosity, are you self managing the database today or using a service?
    - junon 5y ago
      Self hosting. Services don't usually have as tight of security as I'd like.
      - redwood 5y ago
        I would argue that it's a common misconception: the risk of doing something wrong when you're self managing every layer means you're opening yourself up to so much surface area that needs to be done with expert precision. Obviously services are not some magic wand either, EG the recent Microsoft snafus. But they're a third-tier cloud player

Anon84 5y ago

If you're interested in learning more about graphs, you might find my "Graphs for Data Science" substack: https://graphs4sci.substack.com/ https://graphs4sci.substack.com/ where I work though using graph perspectives to analyze real world datasets.

graphviz 5y ago

Someone on the internet is wrong! Or maybe just partially correct. This is very interesting work. There is some selling going on, not discussing enough about the issues that drove the database community toward relational databases and away from "network" databases in the 1970s. If you think of visualization systems as a microcosm of more general computing, notice people need more than graphs - they need all kinds of tables, charts, maps, and other things. Same with "graph databases". This area does exist because the database community underinvested in computing on graphs and networks, the same as it did with usability for a long time. It is still catching up but there is a lot of great work. Another problem is helping users to understand the cost of what they are trying to compute. Select and join? I can estimate that. Find betweenness centrality of a large network? Find a tour that visits all the cycles of a network exactly once? All the edges? All nodes? Oops. What about graph object types? Is it OK to mix them? Sometimes I wonder arguments that "graph databases are [more] efficient for linked structures." After 20 or 30 years of intense R&D, relational databases already seem pretty efficient for computing with relationships.

_wldu 5y ago
SQL struggles with hierarchical data (trees), which are graphs.
- pphysch 5y ago
  In practice most hierarchies are shallow (or poorly designed) Country, Province/State, City, Neighborhood/ZIP, Building, Room. 5 jumps to go from planetary to personal. 5 JOINs is not unreasonable.
  - deleted 5y ago
    [deleted]

ThePhysicist 5y ago

I think graph processing has great potential for use cases where the data model is heterogeneous and the structure of a problem really can be modeled as a graph problem. I think the tooling and the technologies are still not nearly as mature as e.g. relational databases and most developers have very little exposure to graph models, so adoption is still quite low, but will probably rise as the cloud providers offer hosted graph databases. In 2015 I was quite excited for TitanDB and the TinkerPop stack but I think the acquisition of the team behind it (Aurelius) by DataStax kind of sucked the air out of the community edition. As far as I understand Amazon is using many ideas and concepts from TitanDB in their Neptune graph database, but unfortunately they don't seem to care to open-source it. I don't think graph databases & graph processing will become mainstream tough, as they're just not a good fit for most problems.

ta988 5y ago
Neptune sucked the air out of blazegraph as well... It is a constant problem. Graph databases will only ever become more mainstream when we get a real postgresql-level database in term of reliability, maintenance and trust in its evolution.
- zozbot234 5y ago
  PostgreSQL is a fine graph database. It would be nice if it supported the graph-like query language that's now being standardized as an extension to SQL, but other than that it works quite well.
  - ta988 5y ago
    It is pretty slow for most graph operations though. It works ok for simple things, especially with the recently added functions.
    - zozbot234 5y ago
      Well yes, if you need to run actual graph algorithms on network data I agree that pgSQL (or any general purpose database, including "semantics" oriented graph db's) is not the best.

deleted 5y ago

[deleted]

chubot 5y ago

It feels like this should have a citation to Scalability! At What COST? https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf https://www.usenix.org/system/files/conference/hotos15/hotos... which evaluates distributed graph processing frameworks (circa 2015) on various problems and shows that they can be slower than a single threaded program on a laptop. They have a data set with 105 M nodes and 3.7B edges that fits in 14 GB, which all fits in memory (at least 128-256 GB of memory should be taken for granted in these types of problems). Maybe with a clever encoding you can store the entire social network of the world, or at least a FB-sized one. (Storing nodes as integers is efficient and useful for many graph algorithms. You can later "join" with the ancillary data using a fast non-graph distributed processing framework). This article mentions the challenges but doesn't mention the solution of simply using a single machine for big graphs: Even seemingly minute HPAD variations, for example the graph's degree distribution, can have significant performance implications. Graph processing systems rely on complex runtimes that combine software and hardware platforms. It can be a daunting task to capture system-under-test performance—including parallelism, distribution, streaming vs. batch operation Anyone who has done programming with say MapReduce knows that it can be very elegant and fun, but also limiting. This is even more true of graph processing frameworks, as the article explains. If you simply put everything in memory and write native code (which isn't hard at all for batch jobs), then you have so much more flexibility with ANY algorithm, and especially graph algorithms. This type of programming is also fun! You don't have to fit your problem into the framework and switch frameworks when it doesn't fit (or more likely just accept 10-1000x performance decrease when it doesn't fit). --- Abstract: We offer a new metric for big data platforms, COST, or the Configuration that Outperforms a Single Thread. The COST of a given platform for a given problem is the hardware configuration required before the platform outperforms a competent single-threaded implementation. COST weighs a system’s scalability against the overheads introduced by the system, and indicates the actual performance gains of the system, without rewarding systems that bring substantial but parallelizable overheads.

amw-zero 5y ago

I don't have a number of course, but I believe that almost all relational db models are more naturally modeled as graphs. In fact, all normalized relational db models that use foreign keys are just implementing a graph - foreign keys represent edges between nodes. has-many, has-one, and many-to-many are all graph relationships. The relational model + foreign keys is just one way to encode a graph.

pphysch 5y ago
Yeah, tables/rows are basically vertices with 1 label & many properties*, and FKs are labeled edges without properties. But, you can easily implement edge properties with many-to-many tables, at the cost of an extra JOIN. In practice, this is a useful and efficient species of graph. I think many people get baited by Neo4j's marketing without really understanding relational models and RDBMS (I sure did). * With the (often true) assumption that many vertices will follow the same normalized schema.
bawolff 5y ago
Graphs are the least restricting data model. I think everything is easier to model as a graph, because its just things (verticies) and how they are related (edges). You mostly get to skip the modelling step. The benefit of modelling as a relational db is that it forces you to put the data in a form that's easy to work with from a computer perspective.

danieljh 5y ago

The Future is Tiny Graphs! [1] In the style of "Scalability! At What COST?" I've started a side-project bringing succinct data structures (rank/select [2], elias-fano coding) and modern instruction sets (popcount, pdep) to graphs. For some reason the article doesn't mention the field of graph compression and I think it shows: for example most if not all popular open source routing engines don't do anything regarding graph compression. It's time to change that! Reach out to me (preferably on the Github project) if you want try some ideas :) [1] https://tinygraph.org https://tinygraph.org [2] http://www.cs.cmu.edu/~dga/papers/zhou-sea2013.pdf http://www.cs.cmu.edu/~dga/papers/zhou-sea2013.pdf

LukeEF 5y ago
We built TerminusDB[1], our OSS knowledge graph, using succinct data structures. As we have a immutable delta encoding approach to allow domain teams to build and curate data products that they then share, this has been a very fruitful combination. We wrote a technical white paper all about it! [2] [1] https://github.com/terminusdb/terminusdb https://github.com/terminusdb/terminusdb [2] https://github.com/terminusdb/terminusdb/blob/dev/docs/whitepaper/terminusdb.pdf https://github.com/terminusdb/terminusdb/blob/dev/docs/white...

zomglings 5y ago

I have spent the last 7 years building ontologies (knowledge bases), small and large. Like with most tech articles, this one is pushing a very specific point of view that is relevant to megacorporations but certainly not to most companies that would benefit from the deployment of graph-structured knowledge bases. Unless a company has tons of extra cash to burn using technologies like neo4j, Spark, etc., they are better off just building an ontology on top of their existing datastores. The work on the semantic web in the 2000s added a lot of valuable ideas and I see a tendency to downplay these ideas in favor of new technologies. Storing relationships as RDF triples and building indices that are well-suited to your queries will be good enough for the majority of people who need an ontology. I have found that graph-based systems don't model time well. When you are building a knowledge base, you often need to understand how knowledge has changed over time. You may want to relate facts across time or understand what the state of knowledge was within a given period of time. This usually takes extra work. Another thing that I have found these graph-based systems to do poorly is the management of storage classes for different types of data. If you are building a graph knowledge base, not all the information in your knowledge base will be consumed in the same way. If your knowledge base is sufficiently large, you will want to store less frequently accessed data on cheaper storage (e.g. HDD or even object storage like S3) and hotter data on more expensive storage (SSD or even maybe keep it in memory). I have always had to write this code by myself and haven't found a tool that helps to manage this very importance concern in ontology building. That turned into a bit of a ramble, but damn ontologies are cool. :)

amw-zero 5y ago
I am honestly intrigued any time I hear anyone mention RDF. You have had success using it? It wasn't exactly clear how you used it from what you said.
- zomglings 5y ago
  I only use RDF triples as a storage format for edges. I don't normally take advantage of triple stores (e.g. apache Jena), sparql query engines, etc. It's just a simple format and it's easy to build different types of query/analysis capabilities around. The only thing that's a little awkward is applying types to items in an rdf triple (in a way that's computationally cheap). Typing is a general problem, though.

rrwright 5y ago

I’m the creator of thatDot Connect [1], a distributed asynchronous streaming graph interpreter, where we’ve been working on exactly this problem for about 7 years now. Scalable distributed graph processing has so many applications! We were fortunate enough to be funded by DARPA for a while working on automated APT detection for cyber-security. Some of our recent work has shown linear scalability of this approach on large clusters at high throughput. For example, we got to half a million complex graph events ingested per second on a combined read/write workload and could have just kept scaling. We’re in the process of writing up this work and sharing all the details. [1] https://www.thatdot.com/technology/ https://www.thatdot.com/technology/

molham 5y ago

We usually talk about several paradigms for data management and programming: navigational (e.g. CODASYL, OO databases/languages, most graph DBs), tensor-based (e.g. MOLAP, Matlab, TensorFlow, Pytorch), Map-Reduce (e.g. Hadoop and Spark before they started to disown their MR heritage). Semistructured (e.g. JSON) and dataframes (e.g. Pandas) are also important abstractions. These abstractions can be captured in the relational paradigm — in other words we can think of them as special cases and represent them as views on relational models. It is clear from the last 50 years of our industry that the relational paradigm (eventually) always wins. It wins because it separates the what from the how and automates away a bunch of tricky programming that we have to do with the more imperative paradigms. — the OLTP workload was originally supported by navigational systems and then switched to relational systems mostly based on 3rd normal form schemas — the OLAP workload was originally supported by multi-dimensional array (tensor) systems then switched to relational systems based on star and snowflake schemas — the Big Data workload was originally supported by map-reduce systems then switched to relational systems based on star/snowflake + JSON schemas. I believe that the Graph (via navigational), Reasoning (via procedural), and ML (via dataframe and tensor) workloads will move to relational systems based on graph normal form (GNF) schemas. Those relational systems won't be built like the SQL-based systems of today. They will need new relational language extensions, new semantic optimizers, new optimal join algorithms, materialized views that are maintained efficiently, new data structures, etc. We are working on such a system at RelationaAI. We’re in limited preview now but hope to have an open preview by early next year.

rambojazz 5y ago
> It is clear from the last 50 years of our industry that the relational paradigm (eventually) always wins You cannot make a foreign key to link two different tables with RDBMSes. It requires to make another table. With graphs instead this is easy, just make a link from/to any node. With RDBMSes the schema is fixed. With RDBMSes you cannot have "metaproperties" (or properties about properties). With graphs you can easily say {caesar born{source "foobar"} "100BC"}. With RDBMSes this quickly becomes a mess to handle when you have more properties. These are just some use cases why relational does not always win.

lmeyerov 5y ago

Some slightly different views based on our experiences with startups/techco's/enterprises/govs. A lot of what there is true, but at the same time, we've been seeing major appetite in 2 areas that lead to quite different directions from the article. To be clear, I do think the CACM authors are right about a lot of what is commercially + academically popular in big graph land today. Ex: Powering better knowledge graphs, especially for NLP neural network empowered use cases (BERT/GPT). Ex: Enriching inputs into traditional neural network inference calls, like a user 360 before making a recommendation. I expect graph DBs to keep improving to help with theses. At the same time, working with teams from first-principles to help skate to where the puck is going, we've come to 2 overall different priorities where those ideas aren't the primary technology enablers for big graph use cases in terms of engineering + big $$$$ enablers. Broadly, it's useful to think though what Data Analysts are doing and what Data Scientists are doing: 1. Graph BI: Similar to Tableau, Looker, and more autoML-y successors, there are a LOT of analysts who are trying to better understand all that data in their data warehouses. Operational data in Splunk/ELK, transactions & business data in SalesForce CRM / RedShift transactions / etc. Graph questions are powerful here. Graphs are all about relationships like user/cohort behavior, so opens up a lot of questions/answers for analysts, especially if made accessible. However, from a data engineering perspective, copying that data into graph DBs as a second system of record is historically a "now you have 2 problems" thing, and part of why most data lake projects fail. So we've been focusing on building graph query pushdown + virtual fabric style projects that expose graph thinking over your existing data infra. The discussion in the CACM article on dynamic graphs touches on this, but that's only one piece of that problem. Getting analyst graph insights over warehouses as ~easy as it is today for basic time questions on events requires a lot more. Surprisingly, we suspect so much so that it may commoditize the particular choice of graph compute engine (vs say connectors/virtualization/UI/automation/AI.) 2. Graph AI: Traditional neural networks have been increasingly dominating due to strong ability to combine categorical & continuous data around entities of interest (think computer vision realizing some pixels are a cat)... but struggled to leverage relationship structure: imagine a communication or transaction between people/devices/companies with rich histories & communities. Being able to fuse those matters a LOT on commercial contexts, so we'd been watching graph neural networks for awhile. Over the last ~2 years, with the mounting focus by the AI community, key problems around performance, heteorgeneous data, etc., have been getting solved, so GNNs are starting to show up in all sorts of places now. Interestingly, most companies using them don't plug graph databases or knowledge graphs or even traditional graph compute engines into them. If you look at how pytorch, dgl, etc. are being built, they largely ignore what traditional graph infra vendors focus on as 1-3 magnitudes too slow, and overall, wrong tool for the job: different problem space. In both cases, teams building/using graph DB or graph compute engines, like the CACM authors, get enlisted to help as natural stakeholders for pieces of the problem. Likewise, they naturally want to help + grow their scope. Unfortunately, from a perspective of "you're lucky to do even 1-3 things well", they've been struggling to provide the needed end-to-end solutions. There are plenty of critical & fascinating scale, design, + use case challenges to tackle far beyond the core db/compute engine perspective here. Anyways, this is an awesome time for this stuff so I encourage getting involved! We're actively hiring for help creating these new categories (all levels: fullstack, UI, BI, data, AI) + launching projects with lighthouse design partners, so if either is relevant, please reach out! Likewise, traditional graph DB/compute is important too (see: CACM article), and been a no-brainer for attracting most of the VC attention for the last few years due to being a traditional DB play, and we've enjoyed partnering with friends at them, so I'd recommend looking at those companies as well.