Neat, I did research in this area over a decade ago for the same customer as the people in the article. It is a really interesting area of theoretical computer science and we know more about it than the article conveys.

This all started with the problem of analyzing real-world graphs with several trillion edges, back when big data was barely a thing. We used supercomputers, in fact, but those did not make it make it much more tractable. At that scale, it really exposed our poor understanding of how to reason about and expose the deep structure of graphs. Initially, we couldn’t even handle simple graphs at that scale.

A core part of the problem, touched on in the article, is literal data model representation. There are dozens of ways to express a graph in theory (not just the standard three in undergrad CS) but most of them have weaknesses that get exposed when graphs become large, complex, and with a lot of high-order structure you need to access efficiently. And the real-world produces very messy high-order graph structure. Hyper-graphs are neither here nor there; you need a theoretical basis for algorithms that can inductively organize all of that structure in a scalable system.

IBM Research provided the first crude ideas of how to level this up but other people ran with it. There was an evolution through spatial, high-order embedding, topological, moduli space, etc representations trying to surface and capture deep structure in an efficient way. Some of it worked very well but I don’t know if an ideal “final form” was ever arrived at by anyone. Almost none of this research was ever published, though I understand why, and as far as I can tell by talking to people some of it may actually have been lost through people attrition and lack of information sharing.

I really enjoyed working on these problems. Very pure and abstract exotic CS intersects hardcore low-level scalability.

Do you have some recommended reading for the concepts you described? I've dug quite deep into hypergraphs but would like to know the broader field of large scale graph representations

FWIW jandrewrogers has a habit of making deep and well-informed posts that usually end by saying something like "this research area / idea was already conceived of by industry 10--20 years ago, but due to financial motives or secrecy we never published".

I hope jandrewrogers, who posts a ton on HN and makes what seem like high quality comments can start to provide some links / references to make them more useful.

No, this is the frustrating thing about it. I only know about it because I was there. The volume of research is simply too large for a single person to write up unless they have nothing better to do. Best I can do is remind people that it is possible because I observed other people doing it first-hand.

There was a period of time when a lot of very impressive computer science and algorithm R&D was being directly supported by the US intelligence community, and they actively sought out unorthodox researchers — it wasn’t just PhDs, there were high school dropouts making credible advances on hard problems. While often not classified per se, most of the results were never published at the wish of the customer.

Due to a change in government policy around a decade ago, this community no longer exists. Most of the people doing that research retired, changed fields, etc. While I could write up some of this research in detail, it would require extraordinary effort and I am over-employed as it is. Also, a lot of it isn’t my research so I feel a bit weird writing about it. I’ve tried to convince a couple of my friends who worked in those programs to publish but they are just done, retired from it.

There are analogues in database communities, where really neat algorithms are freely traded that aren’t published in a formal sense.

As someone who is research-active in this area: The differences between graphs and hypergraphs are wildly overblown in this article. A hypergraph can be represented as a graph using a Poincare-style duality. This is not something esoteric, it's even in the Wikipedia page on hypergraphs.

As someone who is research-active in the area: I applaud and welcome their propaganda ;)

An interesting algorithm based on graph theory and topology is umap, used for dimensionality reduction.

https://umap-learn.readthedocs.io/en/latest/how_umap_works.h...

I am always amazed at how well umap work for diverse dataset.

I was reading some old computer magazines not long ago and was surprised to see some great articles about graph theory in the 1970's. They were very well written for the beginner, and all of the code examples were in BASIC.

Let that sink in: Graph theory in BASIC.

Thought that the article would be abou the quest for a better random graph model. It's weird that Quanta didn't talk about this yet.

For the other direction (ML helping graph theory and not vice versa), see Constructions in Combinatorics via Neural Networks [0] by Wagner (2021). I made an implementation to play with [1].

[0]: https://arxiv.org/abs/2104.14516

[1]: https://github.com/dpaleka/cross-entropy-for-combinatorics

I'm one of the authors of the simplicial neural networks paper cited in the article. Happy to take questions :-)

awesome!

any recommendations on papers / tutorials here, + any libs, esp. scalable?

For context, we have been looking at rgcn and transfer gns for handling identity graphs and event hypergraphs (= big & dynamic heterogeneous property graphs), esp for node classification and edge prediction, and with libs that handle multi-gpu w bigger-than-memory processing. Something like pattern mining / motif mining would also be interesting, which I'm guessing your approach may open up as well :)

> any recommendations on papers / tutorials

There's essentially two sides to the story: the convolutional deep network side and the topological side. The former is is excellently covered by my coauthor in another paper of his (https://arxiv.org/abs/1606.09375), and the latter is covered by many a textbook or intro text (like http://graphics.stanford.edu/courses/cs164-09-spring/Handout...).

> + any libs, esp. scalable?

https://paperswithcode.com/paper/simplicial-neural-networks

The code isn't very performant, but there's lots of room for improvement. It's more a proof of concept, with lots of low-hanging improvements that can be made.

> For context, we have been looking at rgcn and transfer gns for handling identity graphs and event hypergraphs (= big & dynamic heterogeneous property graphs), esp for node classification and edge prediction, and with libs that handle multi-gpu w bigger-than-memory processing. Something like pattern mining / motif mining would also be interesting, which I'm guessing your approach may open up as well :)

Very interesting!

I feel the current marketing of topological data analysis and similar is directed towards people who have at least taken several graduate math courses.

I'm really not an expert in TDA, I only know Ghrist's book and have read Hatcher. Are there really important topology ideas in topological learning, or it can all be phrased combinatorially?

If it's an important research area, the current language really raises the bar to entry.

> I feel the current marketing of topological data analysis and similar is directed towards people who have at least taken several graduate math courses.

Oh I don't know about that. Lots of TDA is accessible at an undergrad level, as for example the book by Ghrist that you mention shows. I may be biased as I did my PhD in the field, but I also supervised several master's students, and some came from engineering or science backgrounds with little more math than undergrad level under their belts. They mostly did well and learned the basics of the field enough to make contributions during their thesis work. I would say that the field spans a vast range of applied-ness (from straight up data analysis with persistent homology as merely a tool, to fully theoretical work on e.g. multi-persistence). The more applied areas of the field tends to be far more accessible to people without a deep math background.

> Are there really important topology ideas in topological learning, or it can all be phrased combinatorially?

I think topological machine learning is still in its (very exciting!) infancy, and there's nothing I'd like more than to be able to answer that question! I think there's lots of potential for an extremely interesting fusion of two disciplines. And I never forget something the above-mentioned Ghrist once told me (during a discussion unrelated to ML): Never underestimate the treasure-hunting way of doing research – there's lots of be had from bringing together ideas from seemingly unrelated fields, especially when combining old and young ones. (That's me paraphrasing from memory, obviously, Ghrist is a lot more eloquent than that!)

TDA is in some sense just that: the very old of algebraic topology meets the very new of computation, data analysis, etc. And I think the meeting of topology and machine learning has potential to be very exciting too!

PS: When you say "or can it all be phrased combinatorially?", I wanna point out that topology and combinatorics are not mutually exclusive. This is a nice book that straddles the realms of TDA, topology and combinatorics: https://www.springer.com/gp/book/9783540719618 . See also Matt Kahle's fabulous works on showing the probabilistic properties of certain randomly generated combinatorial topological spaces (in some sense generalizing the classical work of Erdős and Rényi pertaining to properties of graphs that you may know, https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_...).

My background is in complex systems physics. Surprisingly, a lot of the work in this area (and most of my own work) revolves around using graph theory and data science to study problems in fields, ranging from epidemiology, linguistics, social and political science, information diffusion, social interactions, etc.

Earlier this year I started a substack where I work through some of the ideas and algorithms using real world datasets: http://graphs4sci.substack.com/

For those interested in practical applications research in this area, there is the Big-ANN competition running as part of NeurIPS this year: https://big-ann-benchmarks.com/

I'm part of a team working on the competition in my spare time and it's a really fascinating problem space!

Hypergraphs seem like a pretty natural and important idea. I believe Wolfram is using them in his ‘theory of everything’ work. Also, the minimum cut problem they mention - hypergraph partitioning - is equivalent to clustering, which itself is also highly related to dimension reduction.

Well, in the war on terror, it took an extensive and sophisticated set of graph theory tools to get information about the entire human population on this planet.

No one had worked on that scale before.

...

Don't we know since Heraclitus who fathers what?