Pascal Schweitzer

Irene Heinrich, Masashi Kiyomi, Yota Otachi et al.

A graph is reconstructible if it is determined up to isomorphism by the multiset of its proper induced subgraphs. The reconstruction conjecture postulates that every graph of order at least 3 is reconstructible. We show that interval graphs with at least three vertices are reconstructible. For this purpose, we develop a technique to handle separations in the context of reconstruction. This resolves a major roadblock to using graph structure theory in the context of reconstruction. To apply our novel technique, we also develop a resilient combinatorial structure theory for interval graphs. A consequence of our result is that interval graphs can be reconstructed in polynomial time.

Billy Joe Franks, Markus Anders, Marius Kloft et al.

Random data augmentations (RDAs) are state of the art regarding practical graph neural networks that are provably universal. There is great diversity regarding terminology, methodology, benchmarks, and evaluation metrics used among existing RDAs. Not only does this make it increasingly difficult for practitioners to decide which technique to apply to a given problem, but it also stands in the way of systematic improvements. We propose a new comprehensive framework that captures all previous RDA techniques. On the theoretical side, among other results, we formally prove that under natural conditions all instantiations of our framework are universal. On the practical side, we develop a method to systematically and automatically train RDAs. This in turn enables us to impartially and objectively compare all existing RDAs. New RDAs naturally emerge from our approach, and our experiments demonstrate that they improve the state of the art.