AMS 467/667, Spring 2020, HW2: Hello DL World
Due: Thursday, March 5, 9AM

This is a second short exercise, meant to give everyone hands-on experience with PyTorch (or your favorite neural-network platform). You can follow the steps described in Yuanye Ma's tutorial from February 20.

On this assignment you are again welcome to get help from fellow students and friends. Two students, working together, can turn in a single paper.

The task is to design a DNN to estimate the size of a largest stable set in an graph. The following files contain all labeled graphs on n = 4, 5, 6 nodes. Each line contains a graph, where the edges are indicated by a 0-1 vector. The components of the vector correspond to the edges ordered lexicographically. For example, for n = 4 the edges are [0,1] [0,2] [0,3] [1,2] [1,3] [2,3]. The last number on each line is the size of the largest stable set in the graph.


Here is the C code used to generate the graphs: allgen.c

It is fine to use different networks for each value of n. The challenge is to obtain good results with a relatively small training set. (If you train on the full set of graphs for a given n, then you should get close to a perfect classification.)

You should submit (by email) your code, a table of results, and a short (1-page) description of the structure of your neural network and your test results.