HN Theater @HNTheaterMonth

Yes, graphs have been around for ages. They're as old as trees! ;-)

And you're right, first-year intro courses present graphs as matrices, it's usually the first graph representation you learn.

However, historically that's not how graphs have been represented in commercial or open-source databases due to the computational complexity and impracticality of supporting different architectures. Many PhD research papers over the years have been about the task of creating one-off implementations for the new hardware of the day.

For an overview of GraphBLAS in the context Heterogeneous High-Performance Computing (HHPC) systems running on NVIDIA GPUs and Intel Xeon Phis, see the 2015 talk Scott McMillan (https://insights.sei.cmu.edu/author/scott-mcmillan/) gave at the CMU Software Engineering Institute:

Graph Algorithms on Future Architectures [video] https://www.youtube.com/watch?v=-sIdS4cz7-4

The figure cited by Scott McMillan in the CMU video is that each new hardware architecture implementation requires about 10,000 lines of code for BFS, and that's just one algorithm. The GraphBLAS standard makes this problem go away.

Furthermore, general on-demand access to GPU and TPU accelerators in cloud data centers just now became a thing. GraphBLAS will make it possible for non PhDs to run graph algos on clusters of accelerators in the cloud at supercomputer speeds.

https://cloud.google.com/gpu/

https://cloud.google.com/tpu/

Having the power of a Graph 500 (https://graph500.org) supercomputer at your fingertips and the ability to tap into that power on demand...well that's new! :-) And kinda crazy cool too, don't ya think?

P.S. A few years back, Jeremy Kepner did a mini-course on D4M (the precursor to GraphBLAS). The videos and material are on MIT OCW...

MIT D4M: Mathematics of Big Data and Machine Learning [video] https://www.youtube.com/watch?v=iCAZLl6nq4c&list=PLUl4u3cNGP...

Discussion: https://news.ycombinator.com/item?id=18105931

Re: nvgraph, NVIDIA is one of Tim Davis's research sponsors and uses his code, as is (and does) Google. Among other things, he also wrote the open-source NVIDIA CULA sparse matrix library. See the list of libraries at the bottom of this page (scroll down) http://faculty.cse.tamu.edu/davis/research.html

Re: cuStinger, it's no longer...it's now Hornet, which uses CUB by NVIDIA Research https://github.com/hornet-gt/hornet

Re: gunrock, they have plans on adding GraphBLAS as part of their backend: https://github.com/gunrock/gunrock/issues?utf8=%E2%9C%93&q=i...

Re: GraphBLAS, see my comment from yesterday...

Log(Graph): A Near-Optimal High-Performance Graph Representation (2018)

https://news.ycombinator.com/item?id=18099520

For an overview of GraphBLAS in the context of Heterogeneous High-Performance Computing (HHPC) systems such as NVIDIA GPUs or Intel Xeon Phis, see the 2015 talk Scott McMillan (https://insights.sei.cmu.edu/author/scott-mcmillan/) gave at the CMU Software Engineering Institute:

Graph Algorithms on Future Architectures [video] https://www.youtube.com/watch?v=-sIdS4cz7-4

And a few years back, Jeremy Kepner did a mini-course on D4M (the precursor to GraphBLAS). The videos and material are on MIT OCW...

MIT D4M: Mathematics of Big Data and Machine Learning [video] https://www.youtube.com/watch?v=iCAZLl6nq4c&list=PLUl4u3cNGP...

Discussion: https://news.ycombinator.com/item?id=18105931

⬐ lmeyerov

... That makes it sound like the implementations are not meant for direct long-term use, as folks assume them uncompetitive with tuned GPU versions that show up in hornet et al, and in practice they will be used when no GPU equiv is available / out of convenience? Likewise, even when used directly, it will be by framework / lib devs, so some sort of hornet-blas?

To be clear, the work has been interesting to me for years, so this is purely a practitioner's question as we are not in a position to ship-all-the-things.

⬐ melling

About 25 minutes in he explains that we had the fundamentals in the mid 1950’s. It took half a century for Moore’s Law to solve the problem.

⬐ sonabinu

Listened to this talk given on another campus! It's a great intro and makes the concepts feel accessible

⬐ graycat

His first lecture is good in that he outlines how neural nets are trained to recognize. E.g., can train a network to recognize cats, dogs, and parrots or some such.

IMHO his material on linearity is somewhat interesting but avoids the common approach that what is linear is a function. The usual definition goes, function f is linear provided

f(ax + by) = af(x) + bf(y)

for appropriate cases of a, b, x, y. In linear algebra, commonly f is a matrix, a and b are numbers in a field, usually the real or complex numbers, and x and y are vectors.

Linearity continues quite broadly in math, especially analysis and geometry. One text by G. F. Simmons stated that the two pillars of analysis in math were linearity and continuity.

It appears that after the first lecture, the course is heavily from a paper he and some others wrote on something of a software architecture to ease writing software for the computing for training neural networks.

His architecture is based on his definition of associative arrays which seem to be one, if you will, data structure which can take data from, be regarded as generalizations of, spreadsheets, matrices, maybe usually sparse, some graphs (that is, nodes connected by arcs), etc. For the associative arrays, he defines operations that generalize addition and multiplication of matrix theory, etc. and shows that the operations obey a distributive law that he regards as the key to linearity.

Then the general, infrastructure (interface) software layer is supposed to be small and easy to write.

Some of his examples of anomaly detection from "big data" (it really was big) are impressive.

His framework might significantly help the productivity of building and using neural networks.

First cut, it looks like the main interests in neural networks have been for recognition of speech and images, but his examples likely provide good evidence of other significant application areas.

As might expect from Lincoln Labs, he's fully serious and not just fooling around or pushing hype.

His lecture notes and writing are relatively good.

He has a textbook available at Amazon.

For just the course materials, he has a ZIP file download of 35,802,178 bytes that from just one use of a standard UNZIP command expands into about 640 files/directories (the number of files/directories of his course on my disk is 640 and nearly all of those are from the UNZIP command). Among the many files are some well done PDF files.

He does admit that it is not known why neural networks work as well as they do.

⬐ espeed

The first lecture is from this summer, the others are from an MIT mini-course few years back when D4M was still incubating.

During that time D4M was developed into a standard, which is now GraphBLAS, see my comment from yesterday...

Log(Graph): A Near-Optimal High-Performance Graph Representation (2018)

https://news.ycombinator.com/item?id=18099520

For an overview of GraphBLAS in the context of Heterogeneous High-Performance Computing (HHPC) systems such as NVIDIA GPUs or Intel Xeon Phis, see the 2015 talk Scott McMillan (https://insights.sei.cmu.edu/author/scott-mcmillan/) gave at the CMU Software Engineering Institute:

Graph Algorithms on Future Architectures [video] https://www.youtube.com/watch?v=-sIdS4cz7-4

⬐ rdudekul

Beautiful explanations of key mathematical concepts such as linearity and associated generalizations. Good to get a sense of how so many real life complex phenomenon can be modeled by combining simple mathematical constructs.