Search

Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer's perception, in particular, pre-attentive processing (e.g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most $k$ times for some integer $k \ge 1$. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-$k$-planarity testing is NP-complete already for $k =1$ and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward $1$-planar drawing in which all vertices are incident to the outer face., Comment: This is the extended version, with full appendix, of a paper to appear in the Proc. 32nd Int. Symp. Graph Drawing & Network Visualization (GD 2024)

Topology and superconductivity, two distinct phenomena offer unique insight into quantum properties and their applications in quantum technologies, spintronics, and sustainable energy technologies if system can be found where they coexist. Tin (Sn) plays a pivotal role here as an element due to its two structural phases, $\alpha$-Sn and $\beta$-Sn, exhibiting topological characteristics ($\alpha$-Sn) and superconductivity ($\beta$-Sn). In this study we show how precise control of $\alpha$ and $\beta$ phases of Sn thin films can be achieved by using molecular beam epitaxy grown buffer layers with systematic control over the lattice parameter. The resulting Sn films showed either $\beta$-Sn or $\alpha$-Sn phases as the lattice constant of the buffer layer was varied from 6.10 A to 6.48 A, covering the range between GaSb (closely matched to InAs) and InSb. The crystal structures of the $\alpha$- and $\beta$-Sn films were characterized by x-ray diffraction and confirmed by Raman spectroscopy and scanning transmission electron microscopy. The smooth and continuous surface morphology of the Sn films was validated using atomic force microscopy. The characteristics of $\alpha$- and $\beta$-Sn phases were further verified using electrical transport measurements by observing resistance drop near 3.7 K for superconductivity of the $\beta$-Sn phase and Shubnikov-de Haas oscillations for the $\alpha$-Sn phase. Density functional theory calculations showed that the stability of the Sn phases is highly dependent on lattice strain, with $\alpha$-Sn being more stable under tensile strain and $\beta$-Sn becoming favorable under compressive strain, which is in good agreement with experimental observations. Hence, this study sheds light on controlling Sn phases through lattice engineering, enabling innovative applications in quantum technologies and beyond.

Multimodal neuroimaging grants a powerful in vivo window into the structure and function of the human brain. Recent methodological and conceptual advances have enabled investigations of the interplay between large-scale spatial trends, or gradients, in brain structure and function, offering a framework to unify principles of brain organization across multiple scales. Strong community enthusiasm for these techniques has been instrumental in their widespread adoption and implementation to answer key questions in neuroscience. Following a brief review of current literature on this framework, this perspective paper will highlight how pragmatic steps aiming to make gradient methods more accessible to the community propelled these techniques to the forefront of neuroscientific inquiry. More specifically, we will emphasize how interest for gradient methods was catalyzed by data sharing, open-source software development, as well as the organization of dedicated workshops led by a diverse team of early career researchers. To this end, we argue that the growing excitement for brain gradients is the result of coordinated and consistent efforts to build an inclusive community and can serve as a case in point for future innovations and conceptual advances in neuroinformatics. We close this perspective paper by discussing challenges for the continuous refinement of neuroscientific theory, methodological innovation, and real-world translation to maintain our collective progress towards integrated models of brain organization.

Mixed-precision quantization of efficient networks often suffer from activation instability encountered in the exploration of bit selections. To address this problem, we propose a novel method called MetaMix which consists of bit selection and weight training phases. The bit selection phase iterates two steps, (1) the mixed-precision-aware weight update, and (2) the bit-search training with the fixed mixed-precision-aware weights, both of which combined reduce activation instability in mixed-precision quantization and contribute to fast and high-quality bit selection. The weight training phase exploits the weights and step sizes trained in the bit selection phase and fine-tunes them thereby offering fast training. Our experiments with efficient and hard-to-quantize networks, i.e., MobileNet v2 and v3, and ResNet-18 on ImageNet show that our proposed method pushes the boundary of mixed-precision quantization, in terms of accuracy vs. operations, by outperforming both mixed- and single-precision SOTA methods., Comment: Proc. The 38th Annual AAAI Conference on Artificial Intelligence (AAAI)

Building autonomous --- i.e., choosing goals based on one's needs -- and adaptive -- i.e., surviving in ever-changing environments -- agents has been a holy grail of artificial intelligence (AI). A living organism is a prime example of such an agent, offering important lessons about adaptive autonomy. Here, we focus on interoception, a process of monitoring one's internal environment to keep it within certain bounds, which underwrites the survival of an organism. To develop AI with interoception, we need to factorize the state variables representing internal environments from external environments and adopt life-inspired mathematical properties of internal environment states. This paper offers a new perspective on how interoception can help build autonomous and adaptive agents by integrating the legacy of cybernetics with recent advances in theories of life, reinforcement learning, and neuroscience., Comment: 28 pages, 4 figures, 3 boxes

The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the $k$-planar drawings $(k \geq 1)$, where each edge cannot cross more than $k$ times. We generalize $k$-planar drawings, by introducing the new family of min-$k$-planar drawings. In a min-$k$-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than $k$ crossings. We prove a general upper bound on the number of edges of min-$k$-planar drawings, a finer upper bound for $k=3$, and tight upper bounds for $k=1,2$. Also, we study the inclusion relations between min-$k$-planar graphs (i.e., graphs admitting min-$k$-planar drawings) and $k$-planar graphs. In our setting we only allow simple drawings, that is, any two edges cross at most once, no two adjacent edges cross, and no three edges intersect at a common crossing point., Comment: Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)

This paper introduces JaxPruner, an open-source JAX-based pruning and sparse training library for machine learning research. JaxPruner aims to accelerate research on sparse neural networks by providing concise implementations of popular pruning and sparse training algorithms with minimal memory and latency overhead. Algorithms implemented in JaxPruner use a common API and work seamlessly with the popular optimization library Optax, which, in turn, enables easy integration with existing JAX based libraries. We demonstrate this ease of integration by providing examples in four different codebases: Scenic, t5x, Dopamine and FedJAX and provide baseline experiments on popular benchmarks., Comment: Jaxpruner is hosted at http://github.com/google-research/jaxpruner