4 ms·

Don't bring a tree to a mesh fight

48 points by valand 5y ago

dragontamer 5y ago
Don't bring a mesh / graph to a hypergraph fight. Hypergraphs seem to be the "biggest generalization" I've come across in the list -> tree -> graph -> hypergraph hierarchy. (That is: all lists are trees. All trees are graphs. All graphs are hypergraphs) In a graph, an "edge" connects two nodes. In hypergraphs, a "hyperedge" can connect 2-or-more nodes. ------- You might think that hypergraphs are purely theoretical, except... they are in common usage all the time. You might also know hypergraphs by their alternative name: Relational Tables. Well, I'm being loose with the language last paragraph. A relational-table is really a hyper-edge. And the nodes of the hypergraphs are the domains of whatever you're working with. If your relational-table only has 2-columns, you have a normal graph relationship between the data. But as anyone who has worked with relational databases knows: you often have 3-columns, 4-columns or more to represent the data. Once you reach 3-columns / 4-columns or beyond, you no longer are working with "simple" graphs but instead hypergraphs, and the theoretical complexity of the whole system reaches a new level. -------- CREATE TABLE PersonsHyperedges ( PersonID int, LastName varchar(255), FirstName varchar(255), Address varchar(255), City varchar(255) ); You can imagine this Table as a list of hyperedges, connecting "PersonID", "LastName", "FirstName", "Address" and "City" nodes together. -------- CREATE TABLE PersonsGraphEdges ( LastName varchar(255), FirstName varchar(255), ); In this case, since there's only 2-elements in the "hyperedge", this table is a list of "normal graph-edges" ----------- There are also things "in-between". Bipartite graphs are very common for example. The hierarchy fits as "tree -> bipartite graph -> graph" (all trees are bipartite graphs). If you have assurances that your problem you're working with is bipartite, then favor bipartite graph algorithms. There are a lot of NP-complete problems over graphs that are in P for bipartite-graphs
- brrrrrm 5y ago
  A hypergraph can always be viewed as a bipartite graph
  - dragontamer 5y ago
    I'm not sure if you're correct or wrong? But its a strange statement to make. Like, any graph can have a "minimum spanning tree" representation for example. But the minimum-spanning tree has some degree of information loss compared to the original. Similarly: a graph / tree could have a Lexicographic ordering (ie: a list representation), but this list-representation lost a lot of information in the translation process. --------- It just turns out that a lot of algorithms could work on the minimum-spanning tree (or the lexicographic list) of the graph. So instead of working on the general graph of a problem, you simplify it down into a simpler structure, and THEN work on the simplified structure.
    - m_a_g 5y ago
      "Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite 'incidence graph' or 'Levi graph' corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs."
    - lmeyerov 5y ago
      The duality is super useful in practice! In the table/dataframe -> hypergraph dataframe transform @ https://github.com/graphistry/pygraphistry https://github.com/graphistry/pygraphistry , we do `hypergraph(multicolumn_table, direct=True | False)['graph'].plot()` , which renders hypergraphs as a regular graph. That lets you pick. Saves a lot of wrangling! Consider exploring some logs of customer activity or security events. A hyperedge becomes either: - a node of a bipartite graph. Ex: each log event becomes a node connecting the various entity nodes it mentions. Event <> IPs, accounts, countries, ... - .. or a bunch of pairwise entity<>entity edges. Ex: connect each IP<>account<>country directly, and label each edge with the hyperedge event id it came from. In both cases, you can now directly leverage a lot of traditional graph thinking, and in our case, GPU acceleration & visualization. Other systems might render hyperedges as say circles encomposing their nodes, but that's trickier at even small/medium scales, so I haven't seen much widely popular I increasingly just directly equate 'logs' with 'property hypergraphs' and skip the relational step. Funny enough, a lot of our enterprise+gov work is undoing the weird tabular & taxonomy optimizations of SQL engines that leak into the user experience when we're to get simple 360 views for users. It's cool an org built out 10,000 tables, but..... :) Same thing when we're doing graph neural networks: logs => hypergraphs (encoded as bipartite or regular property graphs) => event embeddings / classifications / predictions .
- bopbeepboop 5y ago
  For people who want to understand more of the math behind things like hypergraphs. Hypergraphs as math object: https://en.wikipedia.org/wiki/CW_complex https://en.wikipedia.org/wiki/CW_complex Or with data: https://en.wikipedia.org/wiki/Sheaf_(mathematics) https://en.wikipedia.org/wiki/Sheaf_(mathematics) And then you find things like hypergraphs in data fusion: https://www.youtube.com/watch?v=b1Wu8kTngoE https://www.youtube.com/watch?v=b1Wu8kTngoE Or related to logic: https://ncatlab.org/nlab/show/cubical+type+theory https://ncatlab.org/nlab/show/cubical+type+theory
- tasogare 5y ago
  Great comment. I've worked on modeling a specific kind of data as graph and it was too limited. I thus used hypergraph and realized after a while it was in fact relational data, with hyperedge being like table like you explained. I still sticked to the graph model as it was convenient to not have the relationships hardcoded in a database.
runnerup 5y ago
I think there's a typo: > It is in the shape of a Directed Acyclic Rooted Tree or simply a tree. The neat thing is, a tree-shaped computation is always "one-pass". Each node can only be passed at least once. Should be: > Each node can only be passed at most once.
- valand 5y ago
  Author here. Thank you for catching that (and taking time to read)! Fixing it up tonight.
  - karolkozub 5y ago
    I think I found one more minor typo – in the Control Flow Graph section I believe "The possible number of calls to c is zero to infinity;" should be "zero to one" instead, as the flow terminates as soon as it reaches "c", so there is no chance for it to be greater than one.
    - valand 5y ago
      Thanks. Great catch! One thing to learn from this, working past 6pm will most likely yield bugs rather than values.
  - runnerup 5y ago
    No, thank you. I thoroughly enjoyed the article. I also enjoy the title, although it caused some cognitive dissonance by implying that the primary thesis would be: to be careful trying to use trees, where meshes are more appropriate. Instead the concluding thesis was: "Whenever Possible, Make a Tree" and due to my expectations I thought for a second that I may have accidentally skipped over some section which championed meshes. Potentially, putting the thesis as a single sentence near the top would prime readers so they can accurately ingest the rest of the article with proper prejudice.
    - valand 5y ago
      "Whenever Possible, Make a Tree" I've thought about it, but I added " and the Other Way Around" instead, just because I feel the original title gets more glances than the alternatives.
3np 5y ago
Is “mesh” in this context a term I’m not aware of? The author never defines it. My guess is that “mesh” here is supposed to mean “directed cyclic graph” but it’s not very clear.

48 points by valand 5y ago

Don't bring a mesh / graph to a hypergraph fight. Hypergraphs seem to be the "biggest generalization" I've come across in the list -> tree -> graph -> hypergraph hierarchy. (That is: all lists are trees. All trees are graphs. All graphs are hypergraphs) In a graph, an "edge" connects two nodes. In hypergraphs, a "hyperedge" can connect 2-or-more nodes. ------- You might think that hypergraphs are purely theoretical, except... they are in common usage all the time. You might also know hypergraphs by their alternative name: Relational Tables. Well, I'm being loose with the language last paragraph. A relational-table is really a hyper-edge. And the nodes of the hypergraphs are the domains of whatever you're working with. If your relational-table only has 2-columns, you have a normal graph relationship between the data. But as anyone who has worked with relational databases knows: you often have 3-columns, 4-columns or more to represent the data. Once you reach 3-columns / 4-columns or beyond, you no longer are working with "simple" graphs but instead hypergraphs, and the theoretical complexity of the whole system reaches a new level. -------- CREATE TABLE PersonsHyperedges ( PersonID int, LastName varchar(255), FirstName varchar(255), Address varchar(255), City varchar(255) ); You can imagine this Table as a list of hyperedges, connecting "PersonID", "LastName", "FirstName", "Address" and "City" nodes together. -------- CREATE TABLE PersonsGraphEdges ( LastName varchar(255), FirstName varchar(255), ); In this case, since there's only 2-elements in the "hyperedge", this table is a list of "normal graph-edges" ----------- There are also things "in-between". Bipartite graphs are very common for example. The hierarchy fits as "tree -> bipartite graph -> graph" (all trees are bipartite graphs). If you have assurances that your problem you're working with is bipartite, then favor bipartite graph algorithms. There are a lot of NP-complete problems over graphs that are in P for bipartite-graphs

brrrrrm 5y ago
A hypergraph can always be viewed as a bipartite graph
- dragontamer 5y ago
  I'm not sure if you're correct or wrong? But its a strange statement to make. Like, any graph can have a "minimum spanning tree" representation for example. But the minimum-spanning tree has some degree of information loss compared to the original. Similarly: a graph / tree could have a Lexicographic ordering (ie: a list representation), but this list-representation lost a lot of information in the translation process. --------- It just turns out that a lot of algorithms could work on the minimum-spanning tree (or the lexicographic list) of the graph. So instead of working on the general graph of a problem, you simplify it down into a simpler structure, and THEN work on the simplified structure.
  - m_a_g 5y ago
    "Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite 'incidence graph' or 'Levi graph' corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs."
  - lmeyerov 5y ago
    The duality is super useful in practice! In the table/dataframe -> hypergraph dataframe transform @ https://github.com/graphistry/pygraphistry https://github.com/graphistry/pygraphistry , we do `hypergraph(multicolumn_table, direct=True | False)['graph'].plot()` , which renders hypergraphs as a regular graph. That lets you pick. Saves a lot of wrangling! Consider exploring some logs of customer activity or security events. A hyperedge becomes either: - a node of a bipartite graph. Ex: each log event becomes a node connecting the various entity nodes it mentions. Event <> IPs, accounts, countries, ... - .. or a bunch of pairwise entity<>entity edges. Ex: connect each IP<>account<>country directly, and label each edge with the hyperedge event id it came from. In both cases, you can now directly leverage a lot of traditional graph thinking, and in our case, GPU acceleration & visualization. Other systems might render hyperedges as say circles encomposing their nodes, but that's trickier at even small/medium scales, so I haven't seen much widely popular I increasingly just directly equate 'logs' with 'property hypergraphs' and skip the relational step. Funny enough, a lot of our enterprise+gov work is undoing the weird tabular & taxonomy optimizations of SQL engines that leak into the user experience when we're to get simple 360 views for users. It's cool an org built out 10,000 tables, but..... :) Same thing when we're doing graph neural networks: logs => hypergraphs (encoded as bipartite or regular property graphs) => event embeddings / classifications / predictions .
bopbeepboop 5y ago
For people who want to understand more of the math behind things like hypergraphs. Hypergraphs as math object: https://en.wikipedia.org/wiki/CW_complex https://en.wikipedia.org/wiki/CW_complex Or with data: https://en.wikipedia.org/wiki/Sheaf_(mathematics) https://en.wikipedia.org/wiki/Sheaf_(mathematics) And then you find things like hypergraphs in data fusion: https://www.youtube.com/watch?v=b1Wu8kTngoE https://www.youtube.com/watch?v=b1Wu8kTngoE Or related to logic: https://ncatlab.org/nlab/show/cubical+type+theory https://ncatlab.org/nlab/show/cubical+type+theory
tasogare 5y ago
Great comment. I've worked on modeling a specific kind of data as graph and it was too limited. I thus used hypergraph and realized after a while it was in fact relational data, with hyperedge being like table like you explained. I still sticked to the graph model as it was convenient to not have the relationships hardcoded in a database.

runnerup 5y ago

I think there's a typo: > It is in the shape of a Directed Acyclic Rooted Tree or simply a tree. The neat thing is, a tree-shaped computation is always "one-pass". Each node can only be passed at least once. Should be: > Each node can only be passed at most once.

valand 5y ago
Author here. Thank you for catching that (and taking time to read)! Fixing it up tonight.
- karolkozub 5y ago
  I think I found one more minor typo – in the Control Flow Graph section I believe "The possible number of calls to c is zero to infinity;" should be "zero to one" instead, as the flow terminates as soon as it reaches "c", so there is no chance for it to be greater than one.
  - valand 5y ago
    Thanks. Great catch! One thing to learn from this, working past 6pm will most likely yield bugs rather than values.
- runnerup 5y ago
  No, thank you. I thoroughly enjoyed the article. I also enjoy the title, although it caused some cognitive dissonance by implying that the primary thesis would be: to be careful trying to use trees, where meshes are more appropriate. Instead the concluding thesis was: "Whenever Possible, Make a Tree" and due to my expectations I thought for a second that I may have accidentally skipped over some section which championed meshes. Potentially, putting the thesis as a single sentence near the top would prime readers so they can accurately ingest the rest of the article with proper prejudice.
  - valand 5y ago
    "Whenever Possible, Make a Tree" I've thought about it, but I added " and the Other Way Around" instead, just because I feel the original title gets more glances than the alternatives.

3np 5y ago

Is “mesh” in this context a term I’m not aware of? The author never defines it. My guess is that “mesh” here is supposed to mean “directed cyclic graph” but it’s not very clear.