More Like this

1. Micro-Expression Classification based on Landmark Relations with Graph Attention Convolutional Network

   Kumar, Ankith Jain; Bhanu, Bir (June 2021, Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops)

   null (Ed.)

   Facial micro-expressions are brief, rapid, spontaneous gestures of the facial muscles that express an individual's genuine emotions. Because of their short duration and subtlety, detecting and classifying these micro-expressions by humans and machines is difficult. In this paper, a novel approach is proposed that exploits relationships between landmark points and the optical flow patch for the given landmark points. It consists of a two-stream graph attention convolutional network that extracts the relationships between the landmark points and local texture using an optical flow patch. A graph structure is built to draw out temporal information using the triplet of frames. One stream is for node feature location, and the other one is for a patch of optical-flow information. These two streams (node location stream and optical flow stream) are fused for classification. The results are shown on, CASME II and SAMM, publicly available datasets, for three classes and five classes of micro-expressions. The proposed approach outperforms the state-of-the-art methods for 3 and 5 categories of expressions. 

   more » « less
2. Flows, growth rates, and the veering polynomial

   https://doi.org/10.1017/etds.2022.63  

   LANDRY, MICHAEL P.; MINSKY, YAIR N.; TAYLOR, SAMUEL J. (January 2022, Ergodic Theory and Dynamical Systems)

   Abstract For a pseudo-Anosov flow $$\varphi $$ without perfect fits on a closed $$3$$ -manifold, Agol–Guéritaud produce a veering triangulation $$\tau $$ on the manifold M obtained by deleting the singular orbits of $$\varphi $$ . We show that $$\tau $$ can be realized in M so that its 2-skeleton is positively transverse to $$\varphi $$ , and that the combinatorially defined flow graph $$\Phi $$ embedded in M uniformly codes the orbits of $$\varphi $$ in a precise sense. Together with these facts, we use a modified version of the veering polynomial, previously introduced by the authors, to compute the growth rates of the closed orbits of $$\varphi $$ after cutting M along certain transverse surfaces, thereby generalizing the work of McMullen in the fibered setting. These results are new even in the case where the transverse surface represents a class in the boundary of a fibered cone of M . Our work can be used to study the flow $$\varphi $$ on the original closed manifold. Applications include counting growth rates of closed orbits after cutting along closed transverse surfaces, defining a continuous, convex entropy function on the ‘positive’ cone in $H^1$ of the cut-open manifold, and answering a question of Leininger about the closure of the set of all stretch factors arising as monodromies within a single fibered cone of a $$3$$ -manifold. This last application connects to the study of endperiodic automorphisms of infinite-type surfaces and the growth rates of their periodic points. 

   more » « less
3. The Weil–Petersson gradient flow ofrenormalized volume and 3–dimensional convex cores

   https://doi.org/10.2140/gt.2023.27.3183  

   Bridgeman, Martin; Brock, Jeffrey; Bromberg, Kenneth (January 2023, Geometry topology)

   We use the Weil–Petersson gradient flow for renormalized volume to study the space CC(N;S,X) of convex cocompact hyperbolic structures on the relatively acylindrical 3-manifold (N;S). Among the cases of interest are the deformation space of an acylindrical manifold and the Bers slice of quasifuchsian space associated to a fixed surface. To treat the possibility of degeneration along flow-lines to peripherally cusped structures, we introduce a surgery procedure to yield a surgered gradient flow that limits to the unique structure M_geod in CC( N;S,X) with totally geodesic convex core boundary facing S. Analyzing the geometry of structures along a flow line, we show that if V_R(M) is the renormalized volume of M, then V_R(M)−V_R(M_geod) is bounded below by a linear function of the Weil Petersson distance d_WP(∂_c M,∂_cM_geod), with constants depending only on the topology of S. The surgered flow gives a unified approach to a number of problems in the study of hyperbolic 3-manifolds, providing new proofs and generalizations of well-known theorems such as Storm’s result that M geod has minimal volume for N acylindrical and the second author’s result comparing convex core volume and Weil–Petersson distance for quasifuchsian manifolds. 

   more » « less
4. Identifying Taxonomic Units in Metagenomic DNA Streams

   https://doi.org/10.1101/2020.08.21.261313  

   Zheng, V; Sariyuce, AE; Zola, J (January 2020, BIOKDD - 19th International Workshop on Data Mining in Bioinformatics)

   With the emergence of portable DNA sequencers, such as Oxford Nanopore Technology MinION, metagenomic DNA sequencing can be performed in real-time and directly in the field. However, because metagenomic DNA analysis is computationally and memory intensive, and the current methods are designed for batch processing, the current metagenomic tools are not well suited for mobile devices. In this paper, we propose a new memory-efficient method to identify Operational Taxonomic Units (OTUs) in metagenomic DNA streams. Our method is based on finding connected components in overlap graphs constructed over a real-time stream of long DNA reads as produced by MinION platform. We propose an efficient algorithm to maintain connected components when an overlap graph is streamed, and show how redundant information can be removed from the stream by transitive closures. Through experiments on simulated and real-world metagenomic data, we demonstrate that the resulting solution is able to recover OTUs with high precision while remaining suitable for mobile computing devices. 

   more » « less
5. Space Complexity of Minimum Cut Problems in Single-Pass Streams

   https://doi.org/10.4230/LIPIcs.ITCS.2025.43  

   Ding, Matthew; Garces, Alexandro; Li, Jason; Lin, Honghao; Nelson, Jelani; Shah, Vihan; Woodruff, David P (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the specific application of finding minimum cuts in streams is less well-studied. To this end, we show upper and lower bounds on minimum cut problems in insertion-only streams for a variety of settings, including for both randomized and deterministic algorithms, for both arbitrary and random order streams, and for both approximate and exact algorithms. One of our main results is an Õ(n/ε) space algorithm with fast update time for approximating a spectral cut query with high probability on a stream given in an arbitrary order. Our result breaks the Ω(n/ε²) space lower bound required of a sparsifier that approximates all cuts simultaneously. Using this result, we provide streaming algorithms with near optimal space of Õ(n/ε) for minimum cut and approximate all-pairs effective resistances, with matching space lower-bounds. The amortized update time of our algorithms is Õ(1), provided that the number of edges in the input graph is at least (n/ε²)^{1+o(1)}. We also give a generic way of incorporating sketching into a recursive contraction algorithm to improve the post-processing time of our algorithms. In addition to these results, we give a random-order streaming algorithm that computes the exact minimum cut on a simple, unweighted graph using Õ(n) space. Finally, we give an Ω(n/ε²) space lower bound for deterministic minimum cut algorithms which matches the best-known upper bound up to polylogarithmic factors. 

   more » « less