Critical bug in same-class generation

juice500ml commented 4 years ago

Critical issue! @ainch @Naruu @young917

Problems

Bug location: https://github.com/Multi-Objective-NAS/self-supervised-nas/blob/master/src/datasets.py#L55
For metric learning, we have to generate at least k isomorphic graphs (currently 8), which is impossible in some graphs.
For some graphs, there exists only a unique upper triangular adjacency matrix.
- For all the paths in DAG, indices has to be sorted to make an upper triangular adjacency matrix.
```
Valid graph
1
|
2
/ \
3 4 
1-2-3 and 1-2-4 is sorted. This results in upper triangular adjacency matrix.
```

Invalid graph 1 | 3 / \ 2 4 This fails, because 1-3-2 is not sorted.


-   - ex) `1-2-3-4`: There is no way to make another sorted path.
- Currently, NAS-Bench-101 only accepts upper triangular matrix, to ensure that the input matrix is DAG.
- Therefore, only using isomorphic graphs are **impossible**!
- We should implement edit-distance=1, 2, 3 cases.
- But, number of nodes may change when we edit the graph.
- We are **not** sure about whether pytorch.nn.LSTM model can accept multiple length sequences in a single batch.
  - ex) Batch 1: `[ seq1, seq2, seq3 ] = [  [1,2,3],  [1,2],  [1]  ]`
  - Limiting number of nodes = 7 is *cheating* btw. We should solve this anyways.
- Training seemed okay previously, because SemiNAS implementation of `convert_arch_to_seq` ignores lower triangle.
  - Embedder (LSTM) was simply getting blank sequences (except ops).
  - https://github.com/Multi-Objective-NAS/SemiNAS/blob/fc8d530c496d92362a3c3f28589261f3d9cf203e/nas_bench/utils.py#L114-L115

## TODOs
- [ ] Check if torch implements multi-length sequences in a single batch
  - Reference. https://pytorch.org/docs/stable/generated/torch.nn.utils.rnn.pack_sequence.html#torch.nn.utils.rnn.pack_sequence
- [x] Implement generating k-edit graphs
- [x] Implement adjacency matrix --> upper triangular adjacency matrix

young917 commented 4 years ago

I think torch can implement multi-length sequences in a single batch... I ran https://github.com/snap-stanford/GraphRNN this code before.

In this code,

Data Loader (pytorch) : https://github.com/snap-stanford/GraphRNN/blob/1ef475d957414d7c0bf8c778a1d44cb52dd7829b/data.py#L574 Use an adjacency matrix as a sequence of input [row1, row2, row3, ... ]. One row( fixed length ) is an input of rnn model in one time, and the number of rows is the length of seqence.
Before training: https://github.com/snap-stanford/GraphRNN/blob/1ef475d957414d7c0bf8c778a1d44cb52dd7829b/train.py#L452 Sort the sequences in a batch in order of the largest length.
Forward in the model: https://github.com/snap-stanford/GraphRNN/blob/1ef475d957414d7c0bf8c778a1d44cb52dd7829b/model.py#L314 Use pack_padded_sequence(sorted multi-length sequences, list of length of sequences)

Hope this helps even if I'm wrong...

Naruu commented 4 years ago

https://en.wikipedia.org/wiki/Adjacency_matrix -> ctrl +F "isomorphic"

original

permuted graph

node5 of permuted graph does not have outgoing edge to OUTPUT node

juice500ml commented 4 years ago

Critical issues are solved in previous PRs. To avoid staleness & multi-length sequences is not critical now, I'm closing this issue and make another issue with multi-length sequences.

Multi-Objective-NAS / self-supervised-nas