5 ms·
How Big Data Carried Graph Theory into New Dimensions
- nighthawk454 5y agoHypergraphs 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.
- jandrewrogers 5y agoNeat, 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.
- igorkraw 5y agoDo 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
- _throw-rnp2f 5y agoFWIW 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.
- jandrewrogers 5y agoNo, 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.
- Borrible 5y agoWell, 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?
- pschetelat 5y agoAn interesting algorithm based on graph theory and topology is umap, used for dimensionality reduction. https://umap-learn.readthedocs.io/en/latest/how_umap_works.html https://umap-learn.readthedocs.io/en/latest/how_umap_works.h... I am always amazed at how well umap work for diverse dataset.
- theaeolist 5y agoAs 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 ;)
- reaperducer 5y agoI 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.
- gspr 5y agoI'm one of the authors of the simplicial neural networks paper cited in the article. Happy to take questions :-)
- dpaleka 5y agoI 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.
- gspr 5y ago> 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 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_model https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_...).
- Anon84 5y agoMy 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/ http://graphs4sci.substack.com/
- binarymax 5y agoFor 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/ 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!
- dpaleka 5y agoThought 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 https://arxiv.org/abs/2104.14516 [1]: https://github.com/dpaleka/cross-entropy-for-combinatorics https://github.com/dpaleka/cross-entropy-for-combinatorics