michelpp

When you consider that a graph and a matrix are isomorphic, doing vector matrix multiplication takes a vector with a set value, say row 4, and multiplies it by a matrix where row 4 has values present that represent edges to the nodes that are adjacent to it (ie "adjacency" matrix). The result is a vector with the next "step" in a BFS across the graph, do that in a loop and you step across the whole graph.

A cool result of this is, for example, taking an adjacency matrix and squaring it is the "Friend of a Friend" graph. It takes every node/row and multiplies it by itself, returning a matrix that are adjacent to the adjacencies of each node, ie, the friends (adjacencies of the adjacencies) of friends (adjacencies) of the nodes.

Deeper traversal are just higher powers, a matrix cubed are the friends of the friends of the friends. You literally say `A @ A @ A` in Python, and you're done, no dictionary or lists or loops or anything else.

A picture is worth a thousand words, see figure 7 of this paper:

https://arxiv.org/pdf/1606.05790.pdf

Also check out figure 8, this shows how incidence matrices can work to represent hyper and multi graphs. An pair of incidence matrices reprsent two graphs, one from nodes to edges and the other from edges to nodes, these are n by m and m by n. When you multiply them, you get a square adjacency matrix that "projects" the incidence into an adjacency. This can be used to collapse hypergraphs into simple graphs that use different semirings to combine the multiple edges.

For some pretty pictures of this kind of stuff, check out CoinBLAS (note I am not a crypto-bro, it was just a very handy extremely large multi-graph that I could easily download in chunks to play with):

https://github.com/Graphegon/CoinBLAS/

> It's well understood, graphs can be conveniently represented as matrices/tables/relations, and they are equivalent to edge lists.

Maybe I'm missing what you're saying here, but matrices are not "equivalent" to edge lists, they are abstract mathematical objects decoupled from whatever storage method you use in a computer. For example, SuiteSparse:GraphBLAS has four storage formats: dense, bitmap, sparse, and hypersparse. None of these are equivalent to edge lists.

Edge lists are a way to store a representation to a graph, but they are not a graph. Like a matrix, a graph is a abstract mathematical concept that has different methods of representing itself in computers. But mathematically, graphs and matrices are isomorphic, every graph is a matrix, and every matrix is a graph. The isomorphism extends to operations as well, every BFS is a matrix multiplication, and vice versa.

> ex. "with 100 nodes and 200 edges...If we use an adjacency matrix representation...we need a 100×100 matrix containing 200 ones and 9,800 zeros. If we instead use an edge list we need only 200 pairs of nodes."

The GraphBLAS is a sparse matrix library, it does not store the non-present values.

Also, a non-present value may or may not be zero. For example in shortest path algorithms, the non present value is positive infinity.

In the language of Linear Algebra, the type of a graph is a sparse matrix. Adjacency matrices can express simple directed and undirected graphs, and Incidence matrices can express multi, hyper, and ubergraphs.

The real power of using matrices for graphs is that you can use Linear Algebra to process them. Instead of "edge and node" thinking, LA brings the power of matrix multiplication and semirings to graph algorithms. Instead of working about edgelists, hashmaps of visited nodes, thread pools and when to fork or not to fork, by using a standard like the GraphBLAS you can just express an algorithm as a system of matrix operations, and the underlying library can choose how to run it, and on what hardware.

For example, the current state of the art GraphBLAS implementation is SuiteSparse:GraphBLAS, has a JIT compiler that runs graph algorithms on a variety of CPUs and CUDA GPUs. The same sparse deep neural network inference code that is a few lines of Python can run on a chromebook all the way up to a large GPU system with no changes, the only difference is the size of the graph and the time it takes to process it.

As graphs get into billions and trillions of edges, writing algorithms by hand that target different architectures gets extremely difficult and tedious. Future versions of SuiteSparse have a lot of exciting feature planned, including operation fusion and distributed processing. Retargeting hand written algorithms will be a thing of the past.

One of the best parts about the GraphBLAS is that the graph really does have a "type" in the programming language sense, it's a Matrix, and the same operators and operations you expect to work are there. There is great support for both Julia and Python at the moment for beginners and data science oriented folks to dive in quickly.

Here's an interesting paper on how to express centrality algorithms like PageRank and Triange Centrality (disclaimer: I am one of the paper authors):

https://www.researchgate.net/publication/356707900_The_Graph...

I also created an introductory video some time ago explaining the very basic concepts:

https://www.youtube.com/watch?v=JUbXW_f03W0

Which can all be represented with Incidence Matrices:

https://en.wikipedia.org/wiki/Incidence_matrix

RedisGraph is now FalkorDB:

https://github.com/FalkorDB/FalkorDB

> you probably want more specialised tools like BLAS/LAPACK

The GraphBLAS and LAGraph are sparse matrix optimized libraries for this exact purpose:

https://github.com/DrTimothyAldenDavis/GraphBLAS

https://github.com/GraphBLAS/LAGraph/

I think one of the elements that author is missing here is that graphs are sparse matrices, and thus can be expressed with Linear Algebra. They mention adjacency matrices, but not sparse adjacency matrices, or incidence matrices (which can express muti and hypergraphs).

Linear Algebra is how almost all academic graph theory is expressed, and large chunks of machine learning and AI research are expressed in this language as well. There was recent thread here about PageRank and how it's really an eigenvector problem over a matrix, and the reality is, all graphs are matrices, they're typically sparse ones.

One question you might ask is, why would I do this? Why not just write my graph algorithms as a function that traverses nodes and edges? And one of the big answers is, parallelism. How are you going to do it? Fork a thread at each edge? Use a thread pool? What if you want to do it on CUDA too? Now you have many problems. How do you know how to efficiently schedule work? By treating graph traversal as a matrix multiplication, you just say Ax = b, and let the library figure it out on the specific hardware you want to target.

Here for example is a recent question on the NetworkX repo for how to find the boundary of a triangular mesh, it's one single line of GraphBLAS if you consider the graph as a matrix:

https://github.com/networkx/networkx/discussions/7326

This brings a very powerful language to the table, Linear Algebra. A language spoken by every scientist, engineer, mathematician and researcher on the planet. By treating graphs like matrices graph algorithms become expressible as mathematical formulas. For example, neural networks are graphs of adjacent layers, and the operation used to traverse from layer to layer is matrix multiplication. This generalizes to all matrices.

There is a lot of very new and powerful research and development going on around sparse graphs with linear algebra in the GraphBLAS API standard, and it's best reference implementation, SuiteSparse:GraphBLAS:

https://github.com/DrTimothyAldenDavis/GraphBLAS

SuiteSparse provides a highly optimized, parallel and CPU/GPU supported sparse Matrix Multiplication. This is relevant because traversing graph edges IS matrix multiplication when you realize that graphs are matrices.

Recently NetworkX has grown the ability to have different "graph engine" backends, and one of the first to be developed uses the python-graphblas library that binds to SuiteSparse. I'm not a directly contributor to that particular work but as I understand it there has been great results.

A similar and more recent example of graph decomposition is the fast graphlet transform:

https://github.com/fcdimitr/fglt

This algorithm has a nice Algebraic formulation recently implemented with the GraphBLAS in LAGraph:

https://github.com/GraphBLAS/LAGraph/blob/stable/experimenta...

PageRank's linear algebraic formulation also has a natural interpretation in the GraphBLAS sparse graph linear algebra library. Here's an example from a paper that benchmarks C, Julia, and Python with pygraphblas (this example hasn't yet been ported to the newer python-graphblas library):

https://www.researchgate.net/publication/356707900_The_Graph...

(disclaimer: I'm one of the paper authors).

The GraphBLAS handles sparse matrices very efficiently, so extremely large graphs can be used, we were able to benchmark against graphs with 65M nodes and billions of triangles in just over a minute. Both the Python and Julia bindings came reasonably close to the "native" C implementation in LAGraph.

system_stat is another one specific to PostgreSQL:

https://github.com/EnterpriseDB/system_stats

Great! I was trying to remember the model name of this processor the other day in a conversation, and no amount of googling could bring it up, all my results were swamped by all the new AI-du-jour chips everyone is working on. The young person I was talking to could not believe there was a neural network chip in the 90s and looked at me like I was having some kind of memory issue.

I remember the 80170 just not getting that much attention when it came out, at the time I was just out of high school, hammering away on Turbo C++ and working through the third volume of Parallel Distributed Processing and thinking to myself, "someone should make a chip that does this" and then eventually reading about the 80170 having come and gone. I vaguely recall a demo where they would quickly flash NIST digits at the chip and it could recognize them with high speed and accuracy.

I think what maybe killed the effort was the extreme pace of Moore's law at the time, made a NN chip more efficient than software? No biggie in 8 months we'll just double the density and speed of the current x86 chip and beat it in software. There's probably also the extreme internal competition in Intel to kill anything that might even vaguely threaten x86.

Anyway, good flashbacks. I should dig up my copy of PDP, I remember skimming over the second volume on biological models and I think at this stage in my life that might be the most interesting.

I like the "solve the now" perspective here, and having code examples is very helpful to understand some of the rational behind the approach. Having read your previous "tedious survey"[0] post on various token formats, I generally agree with a lot of your conclusions. Curious though about your thought process wrt macaroons vs biscuits.

To me the one major downside of macaroons has always been the single shared root symmetric key. Many use cases are addressed by third party attenuation, but then there are the problems like key rotation, having to do online verification, no built in encryption, no peer-to-peer support through an "untrusted" fly.io, and no third party token verification without decryption like in signcryption[1] schemes. Of course this is traded off by having to do PK issuance and management so I can see the simplicity of it.

Is fly.io scoping this pretty hard to just auth tokens with third party attenuation, or do you see further development and maybe moving to other token systems like biscuit when/if the need arises to address those known issues?

fwiw I've done a bit of research work myself on a token format using signcryption [2] where I explored addressing some of these ideas (but not the attenuation side of it yet, which I get is a big deal here).

[0] https://fly.io/blog/api-tokens-a-tedious-survey/

[1] https://github.com/jedisct1/libsodium-signcryption

[2] https://github.com/michelp/pgsodium/blob/feat/signcryption-t...

Sure let's chat about it in an issue thanks!

What piques my interest in this tool is that I haven't found a good "notebook" like solution for Postgres yet, I've tried using SQL magic functions in Jupiter to generate some documentation for pgsodium[1] but I'm not entirely pleased with the results, there's too much Python still showing through.

Would this tool work as a general purpose documentation generator for a Postgres extension?

[1] https://michelp.github.io/pgsodium/Public_Key_Cryptography.h...

Can Pluto do the same Postgres example given? I googled for it but didn't see anything immediately stand out.

Alternatively you could use Continuous Archiving with Point In Time Recovery [1] which has been built into Postgres for a while. Once your db exceeds several tens of gigabytes dumping to SQL is just not a viable solution anymore.

[1] https://www.postgresql.org/docs/current/continuous-archiving...

There is a great video where Danny Hillis describes their thinking behind the design of the CM-2, and how it influenced the design of the then still in development CM-5.

What's crazy is when he talked about "bits in the machine" that are not stored in RAM, but are stored in wires "in flight" across the room sized machine with one big synchronous clock.

https://www.youtube.com/watch?v=Ua-swPZTeX4

> There’s a theory that work expands to fill the time you give it

https://en.m.wikipedia.org/wiki/Parkinson's_law

Yes that's true, there are efficient heuristic graph algorithms for many problems, for example the travelling salesman problem has several good heuristic algorithms that gives you a short path, but perhaps not the exact shortest.

But for problems like connected components, there is only one right answer, a component is connected or it is not, there is no useful heuristic solution. Same goes for all shortest paths, yes A* is heuristic for finding an optimally short path from a specific source to a specific destination, but to get all destination shortest paths you have to visit all the nodes anyway, so there is only one useful solution.

This is interesting to me because it's advancing the work on the notion of quantum graph problem solving.

I'm sure we've all heard how quantum computers can be used in the future to decrypt information from today. There's a lot of research out there on how QC may be able to efficiently factor large semiprimes and bust our existing cryptographic algorithms, but to me this is the more mundane side of QC.

The exciting side to me is that many graph problems, particularly whole graph problems like connectivity and shortest paths have a potential quantum advantage. This is particularly advantageous for sparse and hypersparse graphs that have billions of nodes but relatively low node degree. Language Models, chemical assay databases, proteomics, causal inference, and fraud detection are just a few problems that involve huge sparse graphs that could get a huge boost from quantum.

And to show my own bias here [1], I think the future of graph algorithms, including quantum, is expressing them in Linear Algebraic form with the GraphBLAS API. Using the GraphBLAS, you can write your algorithm in a mathematical form using the multiplication of adjacency matrices that is then synthesized to some optimal form for a given architecture.

The same code you write can then be run on a variety of backends, currently CPUs and CUDA using SuiteSparse's new JIT, but soon FPGAs and yes, quantum computers. Parallelism will become so broad and conceptually divergent that you won't even be able to conceive of an efficient hand written single function for all possible platforms.

[1] https://github.com/Graphegon/pygraphblas

The young are needed for slave labor and click farming, and you have to feed them something. Real food is for the rich.

> That said if anyone from supabase reads this - I'd love to see GPG signing, version hashing/integrity verification, 2FA if it's not their already

Yep, we've got all these on the road map, thanks!

> and I know this one is a lot of extra work - but any type of automated even cursory glance for malicious code.

Unfortunately a "cursory glance" is trivially sidestepped, and anything complete enough to be useful is probably impossible. Maybe you want to write an extension that automates logically replicating your data off the server, or truncates a table after processing it, to you that's useful, to someone else that's malicious, there's just no way to know.

If you don't trust the authors then the only way to trust a TLE is to inspect the code yourself in the context of what "safe" means to you. The pytorch example you mentioned was very likely caught by a human, if an automated system were possible for python (but likely impossible) it would have caught it sooner.

Good news for you then! plv8 is a trusted language and works with pg_tle just fine.

EDIT: I think I misunderstood your comment, plv8 itself is a compiled extension and thus cannot be a TLE, however TLEs can be written in plv8 once you have it installed. Sorry for the confusion!

Like any package or plugin for any language or framework, you are responsible for understanding what you are installing. Since TLEs do not come with any compiled code, this is relatively easy for you to verify yourself with code inspection.

We expect a lot of DBAs to say "no way" to something like TLEs, that's fine, for similar reasons people don't use pip, npm, or cpan. You make your own risk/benefit analysis.

MIT OCW Signals and Systems is excellent:

https://www.youtube.com/watch?v=6xaaeop7gJ8&list=PLADC1A1B7F...

So much awesome fail, sir, I salute you!

“You're afraid of making mistakes. Don't be. Mistakes can be profited by. Man, when I was young I shoved my ignorance in people's faces. They beat me with sticks. By the time I was forty my blunt instrument had been honed to a fine cutting point for me. If you hide your ignorance, no one will hit you and you'll never learn.”

― Ray Bradbury, Fahrenheit 451

I agree and just want to add to your list, Intel missed the low power mobile processor market and may never even achieve a foothold.

One benefit of the approach we are taking is that you can use regular Postgres security rules and policies (GRANTs, RLS, etc) to constrain access to decrypted secrets. It's not quite going all the way to encrypted VMs, but it's better than all or nothing.

Secure enclaves is something that is on our list, one issue we have is that so many of our components we ship are extensions and open source projects, attestation becomes very hard. We've considered a very, very minimal postgres build with almost no extensions enabled except pgsodium, which would run on an encrypted VM purely for the purposes of secret storage, but then "in-use" becomes rather restricted. Definitely open to hearing any ideas you may have on the subject!

You've hit the nail right on the head with this question on how hard group encryption is, and we don't have all the answers yet as we are still working the use cases around it. We are hoping to reach a level of security that you mention in your SE question using something similar to the excellent accepted answer, distributed private key sharing among trusted participants.

The basis we are exploring is using an algorithm called Signcryption (https://github.com/jedisct1/libsodium-signcryption) that is already included in pgsodium. This doesn't solve any of the shared private key issues you mention above, but it is a useful foundation for distributing encrypted messages that separate out sender and receiver identifiers from their keys, a sort of lower level foundation on top of which distributed key sharing can occur.

I also think signcryption is a great foundation for a better token format than JWT or PASETO, as it covers all of their use cases without algorithm confusion attacks (despite PASETO's insistence on "Algorithm Lucidity") and supports more features such as third party verification and streaming shared key generation from any token without having to exchange the key, we hope to use these tokens so that end-to-end peers can exchange tokens, derive streaming shared keys, and then do direct point-to-point message exchange using libsodium crypto_secretstream API which supports key ratcheting for forward secrecy.

Would love to discuss more about your research with you and include it with attribution into our future work, send me an intro at michel@supabase.io when any other ideas or resources you'd like us to see!