Viktor Zamaraev

Jonathan Balasingham, Viktor Zamaraev, Vitaliy Kurlin

The structure-property hypothesis says that the properties of all materials are determined by an underlying crystal structure. The main obstacle was the ambiguity of conventional crystal representations based on incomplete or discontinuous descriptors that allow false negatives or false positives. This ambiguity was resolved by the ultra-fast Pointwise Distance Distribution (PDD), which distinguished all periodic structures in the world's largest collection of real materials (Cambridge Structural Database). The state-of-the-art results in property predictions were previously achieved by graph neural networks based on various graph representations of periodic crystals, including the Crystal Graph with vertices at all atoms in a crystal unit cell. This work adapts the Pointwise Distance Distribution for a simpler graph whose vertex set is not larger than the asymmetric unit of a crystal structure. The new Distribution Graph reduces mean-absolute-error by 0.6\%-12\% while having 44\%-88\% of the number of vertices when compared to the crystal graph when applied on the Materials Project and Jarvis-DFT datasets using CGCNN and ALIGNN. Methods for hyper-parameters selection for the graph are backed by the theoretical results of the Pointwise Distance Distribution and are then experimentally justified.

Ivan Lahtin, Viktor Zamaraev

We study the Temporal Exploration problem, where an agent must visit all vertices of a temporal graph while traversing at most one available edge per time step. Unlike static graphs, which can be explored in linear time, temporal constraints can substantially increase exploration time even when every snapshot of the graph is connected. To better understand the source of this complexity, we focus on a near-static setting and consider always-connected $k$-edge-deficient temporal graphs, in which each snapshot is connected and differs from a fixed underlying $n$-vertex graph by at most $k$ edges. Although such graphs are structurally close to static graphs, they can still exhibit non-trivial temporal behaviour. Prior work showed that these graphs can be explored in $O(kn \log n)$ time steps and established a lower bound of $Ω(n \log k)$, leaving open whether linear-time exploration in $n$ is possible. We resolve this question by showing that any always-connected $k$-edge-deficient temporal graph admits an exploration schedule of length $O(nk \log k)$. Moreover, given such a temporal graph, the corresponding exploration schedule can be computed in polynomial time. The obtained bound is linear in the number of vertices up to a factor depending only on $k$, removes the extraneous logarithmic dependence on $n$, and is nearly optimal. In particular, for constant $k$, our result yields an order-optimal $Θ(n)$ exploration time, showing that temporal exploration in this near-static regime essentially retains the linear-time character of static graph traversal.

Jonathan Balasingham, Viktor Zamaraev, Vitaliy Kurlin

Periodic material or crystal property prediction using machine learning has grown popular in recent years as it provides a computationally efficient replacement for classical simulation methods. A crucial first step for any of these algorithms is the representation used for a periodic crystal. While similar objects like molecules and proteins have a finite number of atoms and their representation can be built based upon a finite point cloud interpretation, periodic crystals are unbounded in size, making their representation more challenging. In the present work, we adapt the Pointwise Distance Distribution (PDD), a continuous and generically complete isometry invariant for periodic point sets, as a representation for our learning algorithm. The PDD distinguished all (more than 660 thousand) periodic crystals in the Cambridge Structural Database as purely periodic sets of points without atomic types. We develop a transformer model with a modified self-attention mechanism that combines PDD with compositional information via a spatial encoding method. This model is tested on the crystals of the Materials Project and Jarvis-DFT databases and shown to produce accuracy on par with state-of-the-art methods while being several times faster in both training and prediction time.