Crystal structures are characterized by atomic bases within a primitive unit cell that repeats along a regular lattice throughout 3D space. The periodic and infinite nature of crystals poses unique challenges for geometric graph representation learning. Specifically, constructing graphs that effectively capture the complete geometric information of crystals and handle chiral crystals remains an unsolved and challenging problem. In this paper, we introduce a novel approach that utilizes the periodic patterns of unit cells to establish the lattice-based representation for each atom, enabling efficient and expressive graph representations of crystals. Furthermore, we propose ComFormer, a SE(3) transformer designed specifically for crystalline materials. ComFormer includes two variants: iComFormer that employs invariant geometric descriptors of Euclidean distances and angles, and eComFormer that utilizes equivariant vector representations. Experimental results demonstrate the state-of-the-art predictive accuracy of ComFormer variants on various tasks across three widely-used crystal benchmarks. Our code is publicly available as part of the AIRS library (https://github.com/divelab/AIRS).
more »
« less
Interactive 2D Periodic Graphs
We present an educational web app for interactively drawing and editing 2D periodic graphs. The user defines the unit cell and the finite set of vertex and edge representatives, from which a sufficiently large fragment of the periodic graph is created for the visualization. The periodic graph can also be modified by applying several transformations, including isometries and relaxations of the unit cell. A finite representation of the infinite periodic graph can be saved in an external file as a quotient graph with Z²-marked edges. Its geometry is recorded using fractional (crystallographic) coordinates. The facial structure of non-crossing periodic graphs can be revealed by the user interactively selecting face representatives. An accompanying video demonstrates the functionality of the web application.
more »
« less
- Award ID(s):
- 2212309
- PAR ID:
- 10511460
- Editor(s):
- Chambers, Erin W; Gudmundsson, Joachim
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Journal Name:
- 39th International Symposium on Computational Geometry (SoCG 2023)
- Subject(s) / Keyword(s):
- Periodic graphs isometric transformations Theory of computation → Computational geometry
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Abstract Inquiry instruction often neglects graphing. It gives students few opportunities to develop the knowledge and skills necessary to take advantage of graphs, and which are called for by current science education standards. Yet, it is not well known how to support graphing skills, particularly within middle school science inquiry contexts. Using qualitative graphs is a promising, but underexplored approach. In contrast to quantitative graphs, which can lead students to focus too narrowly on the mechanics of plotting points, qualitative graphs can encourage students to relate graphical representations to their conceptual meaning. Guided by the Knowledge Integration framework, which recognizes and guides students in integrating their diverse ideas about science, we incorporated qualitative graphing activities into a seventh grade web‐based inquiry unit about cell division and cancer treatment. In Study 1, we characterized the kinds of graphs students generated in terms of their integration of graphical and scientific knowledge. We also found that students (
n = 30) using the unit made significant learning gains based on their pretest to post‐test scores. In Study 2, we compared students' performance in two versions of the same unit: One that had students construct, and second that had them critique qualitative graphs. Results showed that both activities had distinct benefits, and improved students' (n = 117) integrated understanding of graphs and science. Specifically, critiquing graphs helped students improve their scientific explanations within the unit, while constructing graphs led students to link key science ideas within both their in‐unit and post‐unit explanations. We discuss the relative affordances and constraints of critique and construction activities, and observe students' common misunderstandings of graphs. In all, this study offers a critical exploration of how to design instruction that simultaneously supports students' science and graph understanding within complex inquiry contexts. -
Abstract In this paper we show that every non-cycle finite transitive directed graph has a Cuntz–Krieger family whose WOT-closed algebra is $B(\mathcal {H})$ . This is accomplished through a new construction that reduces this problem to in-degree 2-regular graphs, which is then treated by applying the periodic Road Colouring Theorem of Béal and Perrin. As a consequence we show that finite disjoint unions of finite transitive directed graphs are exactly those finite graphs which admit self-adjoint free semigroupoid algebras.more » « less
-
Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter.more » « less
-
more » « less
We present a tool for multi-omics data analysis that enables simultaneous visualization of up to four types of omics data on organism-scale metabolic network diagrams. The tool’s interactive web-based metabolic charts depict the metabolic reactions, pathways, and metabolites of a single organism as described in a metabolic pathway database for that organism; the charts are constructed using automated graphical layout algorithms. The multi-omics visualization facility paints each individual omics dataset onto a different “visual channel” of the metabolic-network diagram. For example, a transcriptomics dataset might be displayed by coloring the reaction arrows within the metabolic chart, while a companion proteomics dataset is displayed as reaction arrow thicknesses, and a complementary metabolomics dataset is displayed as metabolite node colors. Once the network diagrams are painted with omics data, semantic zooming provides more details within the diagram as the user zooms in. Datasets containing multiple time points can be displayed in an animated fashion. The tool will also graph data values for individual reactions or metabolites designated by the user. The user can interactively adjust the mapping from data value ranges to the displayed colors and thicknesses to provide more informative diagrams.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.SoCG.2023.63
