Post #77

​​My thoughts on Kelly's conjecture. A Kelly's conjecture (a.k.a. reconstruction conjecture) states that for a graph with n vertices, a deck with n graphs on (n-1) vertices can reconstruct exactly a graph. In other words, pick a graph, remove one vertex (with all its outgoing edges), and put to the set. Then start with the original graph, remove another vertex, and put it to the set. Repeat for all vertices. Finally, you will have a set of n graphs with n-1 vertices, which is called a deck. Now, the conjecture states that deck uniquely determines the original graph, hence, it's a complete graph invariant, i.e. two graphs have the same deck if and only if, they are isomorphic. This conjecture has been known since 1957 and many results have been achieved. For example, it's known that regular graphs or trees can be reconstructed uniquely with a deck, but directed graphs are not. For general undirected case it's still not clear. There is even an ArXiv paper from 2017 that claimed to resolve the conjecture, but after communication with the authors, they admit there is a mistake in the proof. This idea has been in graph representation too. In particular, there is a graphlet kernel that decomposes a graph into a set of small graphlets/motifs. This is quite expressive kernel, i.e. it can recognize a lot of graphs, but whether it recognizes all of the graphs is still a question. For a long time, I believed that if Kelly's conjecture is true (which is quite likely), then not only a deck of graphs on (n-1) vertices is unique, but also of smaller graphs. The assumption was that you can in turn decompose a (n-1) graph into a set of (n-2) deck and move deeper to any number of vertices that you want. But yesterday I found that there are non-isomorphic graphs that have the same decomposition on smaller graphs. In particular, if you take a cycle of 4k+2 vertices as G1 and two cycles of 2k+1 as G2, then a decomposition into k-size graphlets will be the same. For example, for k=3, we have graphlets, i.e. triplets which are connected in all possible ways. In this case, G1 is a cycle on 10 vertices and G2 is two cycles on 5 vertices. The number of closed triangles would be 0 for G1 and G2, the number of 2 connected points and one disconnected would be 60 for G1 and G2, and so on. In the end, the decomposition would be the same, while the graphs are different. Moreover, in recent paper IJCAI '18 it's shown that graphlet kernel cannot identify some planar from non-planar, bijective from non-bijective, and connected from disconnected graphs. This is quite interesting as it shows the limitations of graphlet kernel and in general graphlet decomposition.