Graph

[doss...@cs.uregina.ca]

Has anyone talked yet about introducing a graph data structure? This group has a focus on "graphing" and "graph programming". Graphs are useful in:

• Neural networks and deep learning
• State-search research and problems
• Game maps and worlds
• Mathematical combinatorics and related disciplines

[Vincent Reverdy]

Hello!

Yes, it was put as a research direction in the original paper for SG19.

But it's far from simple when considering performance issues and memory layouts.

Let's say that for now, it's in the back of my mind for SG19 (together with tree data structures).

Best,

Vincent

[doss...@cs.uregina.ca]

Thanks for the reply. I am assuming that there will be both a static and dynamic graph yes? The static one might be implemented using the upcoming matrix object, which would all one to compute, for example, powers of the matrix to count the number of walks between nodes. How about graph algorithms like breadth- and depth- first searches?

In terms of the trees, will they be generic k-ary (and intrusive-style) trees, so that one could insert arbitrary nodes and specify parents?

[Michael Wong]

For me right from day one, I am interested in supporting both static, but also especially dynamic graph generation.

[Vincent Reverdy]

In terms of trees: I've been working on tree abstractions in high performance computing for the last 4 years. I personnally aim for generic trees. Or more exactly tree buidling blocks so that you can compose the best tree for your particular need.

[Eugenio Bargiacchi]

In my work I also often use factor graphs [1], which are a type of bipartite graphs. They are useful for Bayesian inference and for action selection in cooperative multi-agent settings. There aren't many libraries that implement these as they are composed of two types of alternating nodes, while most graph implementations usually assume only a single type of node.

[1]: https://en.wikipedia.org/wiki/Factor_graph

--
You received this message because you are subscribed to the Google Groups "SG19 - Machine Learning" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sg19+uns...@isocpp.org.
To post to this group, send email to sg...@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/sg19/.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/sg19/1224d28e-a0a5-4e69-970f-b35b1010ae78%40isocpp.org.

[Frank Seide]

Could we define dynamic graph (in the NN context)? Do we mean:

 

• define-as-you-go, i.e. graph is generated by “executing” operations, aka trace-based graph generation. This is the normal way for static NN graphs as well. The main special thing for dynamic is that it must be very low-cost, since it is executed repeatedly.
• a static graph that contains dynamic operators, such as conditional, loop expressions, or function calls. Examples are ONNX and TensorFlow, and I would also count jit-based TorchScript (graph===interpreted code in our context).

 

Thanks,

 

Frank

--

You received this message because you are subscribed to the Google Groups "SG19 - Machine Learning" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sg19+uns...@isocpp.org.
To post to this group, send email to sg...@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/sg19/.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/sg19/abd48241-698c-42f6-9edd-bd9f803f8909%40isocpp.org.

[lennard...@student.uni-tuebingen.de]

There has already been some talk about this in https://groups.google.com/a/isocpp.org/forum/#!topic/std-proposals/5iyi--Rg2H8/discussion

But since the ML proposal will necessarily need to introduce new data structures, introducing graphs with it is most likely a good idea

The consensus of this discussion is more or less: any good graph proposal unfortunately will have to bake on a preceding library (since there are so many aspects to look at, trying which ones will fit most generously can hardly ever be done in a paper).

In my opinion, an excellent generic library is the BGL (boost graph library) which supports adjacency lists and matrices, which are a good fit for any tree-like structure, performance-wise.

There has been a more recent library ported to C++17 (using rangesv3) by Chris Bowen (https://github.com/cbbowen/graph/) which seems a lot more like what a graph data structure proposal could look like.

Most important to know will be what kinds of algorithms one will generally want to support in the standard.

Obviously we can implement any search algorithm (depth-first, breadth-first). However I am thinking that a graph proposal can only truly shine when the data structure gives efficient access to subgraphs. 

This way coroutines can be used to tackle cluster problems over giant graphs (I am thinking of ensemble problems that can be efficiently solved on subgraphs).

Best

Lennard

[Richard Dosselmann]

It is great to see such interest in this topic. Whatever the design, there should probably be both static and dynamic versions of a graph. Graph search problems are big in research, relying on depth- and breadth- first searches.

[William Tambellini]

Would nt Boost Graph do some parts of the job:

https://www.boost.org/doc/libs/1_69_0/libs/graph/doc/index.html

?

[Richard Dosselmann]

Certainly so yes! We are looking at it as a possible model. Thanks for your interest in this topic!

[pra...@outlook.com]

Someone mentioned BGL. I investigated it years ago. I think it's important to pay attention to the abstractions it embodies but we ought to be looking to modern features to do it. The meta programming (presented by Herb) is a intriguing direction that may provide useful benefits. 

An issue I had with BGL was that it obscured the implementation so much that it was difficult to validate what was really going on. Another issue I had was that a hand-coded graph was 2-3x faster than BGL. This something I need to revisit; compilers are better and I may not have used BGL in the best way.

[Richard Dosselmann]

I have looked at BGL many times. I have also considered graphs in Python and Java. Most such systems seem to have a few fixed graph structures. Given that there are so many types of graphs (and trees), the thinking at the moment is to create components of graphs, such as nodes and edges, that can be assembled to allow users to create whichever type of graph they need. Of course, modern elements of C++ will be useful in doing this.

[Emad Barsoum]

Not all graphs are equal, for ML it is usually a computation graph which have different requirements (Most frameworks don't use BGL). Some of the requirements already mentioned, here the list:

1. Basic: topology sort, various search algorithms.

2. Shallow and deep clone a subgraph from a graph.

3. Static versus dynamic graph.

4. Dependencies between nodes, most frameworks can execute the graph in parallel. So having a way to partition the graph in order to run each part in parallel is desirable.

5. Sub-graph in a node for loop construct.

6. Optimization: graph transform, node fusion...etc.

7. Advance: generate graph from C++ code.

Thanks,

Emad

[Frank Seide]

Let me add a requirement:

 

8. Highly efficient

 

This is necessary for dynamic networks with automatic batching, where one not only creates the graph dynamically for each minibatch, but also runs through each batch item separately. I prototyped this (and auto-batching) with CNTK, and since the CNTK graph library was not optimized for speed (since in default CNTK, the graph was only created once), I found graph-creation cost to be a major bottleneck.

 

From: Emad Barsoum [mailto:ebar...@gmail.com]

Sent: Monday, March 11, 2019 11:18
To: SG19 - Machine Learning <sg...@isocpp.org>

Subject: Re: Graph

--

You received this message because you are subscribed to the Google Groups "SG19 - Machine Learning" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sg19+uns...@isocpp.org.
To post to this group, send email to sg...@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/sg19/.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/sg19/0c3d8e60-6229-4b13-a2f0-cfa7048ee94c%40isocpp.org.

[Phil Ratzloff]

That sounds like a good start. I think everyone would be looking for the algorithm-iterator-container abstractions like STL. If those don’t exist then it would be perceived as incomplete.

 

 

From: Richard Dosselmann <doss...@cs.uregina.ca>
Sent: Sunday, March 10, 2019 3:19 PM
To: SG19 - Machine Learning <sg...@isocpp.org>
Subject: Re: Graph

 

I have looked at BGL many times. I have also considered graphs in Python and Java. Most such systems seem to have a few fixed graph structures. Given that there are so many types of graphs (and trees), the thinking at the moment is to create components of graphs, such as nodes and edges, that can be assembled to allow users to create whichever type of graph they need. Of course, modern elements of C++ will be useful in doing this.

--

You received this message because you are subscribed to the Google Groups "SG19 - Machine Learning" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sg19+uns...@isocpp.org.
To post to this group, send email to sg...@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/sg19/.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/sg19/d60156f5-ae78-44d2-ab3a-31c54b5a2400%40isocpp.org.

[Vincent Reverdy]

Just as a remark:

• At the last C++ committee meeting, we had a presentation by one of the author of the BGL, Andrew Lumsdaine. This was super informative. I got the feeling that if he had to do it again today, he would do it in a different way. With a more "functional-programming" approach. I indepently came to the same conclusions by working on trees for the last several years. Most of the complexity of the BGL arises from PropertyMaps. I think we need to have a similar mechanism but learn from the experience of the BGL.
• Surprisingly there are far more ways to implement trees than graphs in terms of memory layout and optimization. I think that we'll need almost two interfacable libraries (that share the same concepts though).

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/sg19/DM5PR03MB26330CF619EF8E3CF9CBD524DD480%40DM5PR03MB2633.namprd03.prod.outlook.com.

--

Vincent Reverdy
Ph.D. in Astronomy & Astrophysics

Department of Astronomy (Room 223) 

University of Illinois at Urbana-Champaign

MC-221, 1002 West Green Street, Urbana, IL 61801, USA

[Richard Dosselmann]

Given the importance of trees and graphs, all of the remarks will be taken into consideration to ensure that these are highly useful (and easily modified) data structures. Thanks for all of the great input and feedback!