Showing 1–21 of 21 results for author: Conroy, J

DAG Covers: The Steiner Point Effect

Authors: Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, Da Wei Zheng

Abstract: Given a weighted digraph $G$, a $(t,g,μ)$-DAG cover is a collection of $g$ dominating DAGs $D_1,\dots,D_g$ such that all distances are approximately preserved: for every pair $(u,v)$ of vertices, $\min_id_{D_i}(u,v)\le t\cdot d_{G}(u,v)$, and the total number of non-$G$ edges is bounded by $|(\cup_i D_i)\setminus G|\le μ$. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG c… ▽ More Given a weighted digraph $G$, a $(t,g,μ)$-DAG cover is a collection of $g$ dominating DAGs $D_1,\dots,D_g$ such that all distances are approximately preserved: for every pair $(u,v)$ of vertices, $\min_id_{D_i}(u,v)\le t\cdot d_{G}(u,v)$, and the total number of non-$G$ edges is bounded by $|(\cup_i D_i)\setminus G|\le μ$. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of \emph{Steiner} DAG cover, where the DAGs are allowed to contain Steiner points. We obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a $(1,2,\tilde{O}(n\cdot tw))$-Steiner DAG cover. For planar digraphs we provide a $(1+\varepsilon,2,\tilde{O}_\varepsilon(n))$-Steiner DAG cover. We also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth $1$ with stretch $t<2$ and sub-quadratic number of extra edges requires $Ω(\log n)$ DAGs. △ Less

Submitted 5 April, 2026; originally announced April 2026.

Dynamic Light Spanners in Doubling Metrics

Authors: Sujoy Bhore, Jonathan Conroy, Arnold Filtser

Abstract: A $t$-spanner of a point set $X$ in a metric space $(\mathcal{X}, δ)$ is a graph $G$ with vertex set $P$ such that, for any pair of points $u,v \in X$, the distance between $u$ and $v$ in $G$ is at most $t$ times $δ(u,v)$. We study the problem of maintaining a spanner for a dynamic point set $X$ -- that is, when $X$ undergoes a sequence of insertions and deletions -- in a metric space of constant… ▽ More A $t$-spanner of a point set $X$ in a metric space $(\mathcal{X}, δ)$ is a graph $G$ with vertex set $P$ such that, for any pair of points $u,v \in X$, the distance between $u$ and $v$ in $G$ is at most $t$ times $δ(u,v)$. We study the problem of maintaining a spanner for a dynamic point set $X$ -- that is, when $X$ undergoes a sequence of insertions and deletions -- in a metric space of constant doubling dimension. For any constant $\varepsilon>0$, we maintain a $(1+\varepsilon)$-spanner of $P$ whose total weight remains within a constant factor of the weight of the minimum spanning tree of $X$. Each update (insertion or deletion) can be performed in $\operatorname{poly}(\log Φ)$ time, where $Φ$ denotes the aspect ratio of $X$. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space. △ Less

Submitted 24 March, 2026; originally announced March 2026.

Where did you get that? Towards Summarization Attribution for Analysts

Authors: Violet B, John M. Conroy, Sean Lynch, Danielle M, Neil P. Molino, Aaron Wiechmann, Julia S. Yang

Abstract: Analysts require attribution, as nothing can be reported without knowing the source of the information. In this paper, we will focus on automatic methods for attribution, linking each sentence in the summary to a portion of the source text, which may be in one or more documents. We explore using a hybrid summarization, i.e., an automatic paraphrase of an extractive summary, to ease attribution. We… ▽ More Analysts require attribution, as nothing can be reported without knowing the source of the information. In this paper, we will focus on automatic methods for attribution, linking each sentence in the summary to a portion of the source text, which may be in one or more documents. We explore using a hybrid summarization, i.e., an automatic paraphrase of an extractive summary, to ease attribution. We also use a custom topology to identify the proportion of different categories of attribution-related errors. △ Less

Submitted 28 October, 2025; originally announced November 2025.

MSC Class: cs.AI; cs.CL; cs.IR

Vitessce Link: A Mixed Reality and 2D Display Hybrid Approach for Visual Analysis of 3D Tissue Maps

Authors: Eric Mörth, Morgan L. Turner, Cydney Nielsen, Xianhao Carton Liu, Mark Keller, Lisa Choy, John Conroy, Tabassum Kakar, Clarence Yapp, Alex Wong, Peter Sorger, Liam McLaughlin, Sanjay Jain, Johanna Beyer, Hanspeter Pfister, Chen Zhu-Tian, Nils Gehlenborg

Abstract: Advances in spatial omics and high-resolution imaging enable the creation of three-dimensional (3D) tissue maps that capture cellular organization and interactions in situ. While these data provide critical insights into tissue function and disease, their exploration is often constrained by tools limited to 2D displays or stereoscopic rendering without analytical integration. We present Vitessce L… ▽ More Advances in spatial omics and high-resolution imaging enable the creation of three-dimensional (3D) tissue maps that capture cellular organization and interactions in situ. While these data provide critical insights into tissue function and disease, their exploration is often constrained by tools limited to 2D displays or stereoscopic rendering without analytical integration. We present Vitessce Link, a web-based hybrid framework that unites a 3D stereoscopic view in mixed reality with a synchronized 2D display environment. Users can navigate volumetric data with intuitive hand gestures while controlling channels, filters, and derived data views through the Vitessce platform. Built on open standards and running entirely in the browser, Vitessce Link minimizes friction, supports integration with computational notebooks, and synchronizes interactions across devices via a lightweight WebSocket architecture. Case studies in nephrology and oncology demonstrate how the hybrid approach enhances segmentation evaluation, distance measurement, and interpretation of spatial relationships. Vitessce Link establishes a paradigm for integrative, web-native analysis of 3D tissue maps. △ Less

Submitted 6 November, 2025; originally announced November 2025.

Cutting Planarians: Planar Emulators for String Graphs

Authors: Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, Da Wei Zheng

Abstract: In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\varepsilon$ distortion regimes. Furthermore, the distance sketches themselves are planar graphs. First, we show that every unweighted string graph $G$ has an $O(1)$-distortion planar emulator: that is, there exists an edge-weight… ▽ More In this paper we construct distance sketches for intersection graphs of arbitrary path-connected regions in the plane (known as the string graphs) in the constant and $1+\varepsilon$ distortion regimes. Furthermore, the distance sketches themselves are planar graphs. First, we show that every unweighted string graph $G$ has an $O(1)$-distortion planar emulator: that is, there exists an edge-weighted planar graph $H$ containing every vertex in $G$, such that every pair of vertices $(u,v)$ satisfies $δ_G(u,v) \le δ_H(u,v) \le O(1) \cdot δ_G(u,v)$. Furthermore, we show that for any constant $\varepsilon > 0$, there is an edge-weighted planar graph $H'$ such that every pair of vertices $(u,v)$ satisfies $δ_G(u,v) \le δ_{H'}(u,v) \le (1+\varepsilon) \cdot δ_G(u,v) + O(\varepsilon^{-4}\textrm{poly}\log n)$. No previous constructions of sparse distance sketches were known even for intersection graphs of simple shapes like axis-parallel rectangles or fat convex polygons. As applications, we construct the first $(1+\varepsilon, +O(1))$ mixed-distortion tree cover and distance oracle for arbitrary string graphs, as well as the first additive $+(\varepsilonΔ+O(1))$-distortion embedding of string graphs $G$ with diameter $Δ$ into graphs of constant treewidth $O(\varepsilon^{-4})$. △ Less

Submitted 24 June, 2026; v1 submitted 24 October, 2025; originally announced October 2025.

Comments: full version of STOC 2026 paper

Clustering in Varying Metrics

Authors: Deeparnab Chakrabarty, Jonathan Conroy, Ankita Sarkar

Abstract: We introduce the aggregated clustering problem, where one is given $T$ instances of a center-based clustering task over the same $n$ points, but under different metrics. The goal is to open $k$ centers to minimize an aggregate of the clustering costs -- e.g., the average or maximum -- where the cost is measured via $k$-center/median/means objectives. More generally, we minimize a norm $Ψ$ over the… ▽ More We introduce the aggregated clustering problem, where one is given $T$ instances of a center-based clustering task over the same $n$ points, but under different metrics. The goal is to open $k$ centers to minimize an aggregate of the clustering costs -- e.g., the average or maximum -- where the cost is measured via $k$-center/median/means objectives. More generally, we minimize a norm $Ψ$ over the $T$ cost values. We show that for $T \geq 3$, the problem is inapproximable to any finite factor in polynomial time. For $T = 2$, we give constant-factor approximations. We also show W[2]-hardness when parameterized by $k$, but obtain $f(k,T)\mathrm{poly}(n)$-time 3-approximations when parameterized by both $k$ and $T$. When the metrics have structure, we obtain efficient parameterized approximation schemes (EPAS). If all $T$ metrics have bounded $\varepsilon$-scatter dimension, we achieve a $(1+\varepsilon)$-approximation in $f(k,T,\varepsilon)\mathrm{poly}(n)$ time. If the metrics are induced by edge weights on a common graph $G$ of bounded treewidth $\mathsf{tw}$, and $Ψ$ is the sum function, we get an EPAS in $f(T,\varepsilon,\mathsf{tw})\mathrm{poly}(n,k)$ time. Conversely, unless (randomized) ETH is false, any finite factor approximation is impossible if parametrized by only $T$, even when the treewidth is $\mathsf{tw} = Ω(\mathrm{poly}\log n)$. △ Less

Submitted 9 October, 2025; originally announced October 2025.

Comments: Accepted to FSTTCS 2025

Auto-ARGUE: LLM-Based Report Generation Evaluation

Authors: William Walden, Marc Mason, Orion Weller, Laura Dietz, John Conroy, Neil Molino, Hannah Recknor, Bryan Li, Gabrielle Kaili-May Liu, Yu Hou, Dawn Lawrie, James Mayfield, Eugene Yang

Abstract: Generation of citation-backed reports is a primary use case for retrieval-augmented generation (RAG) systems. While open-source evaluation tools exist for various RAG tasks, tools designed for report generation are lacking. Accordingly, we introduce Auto-ARGUE, a robust LLM-based implementation of the recently proposed ARGUE framework for report generation evaluation. We present analysis of Auto-A… ▽ More Generation of citation-backed reports is a primary use case for retrieval-augmented generation (RAG) systems. While open-source evaluation tools exist for various RAG tasks, tools designed for report generation are lacking. Accordingly, we introduce Auto-ARGUE, a robust LLM-based implementation of the recently proposed ARGUE framework for report generation evaluation. We present analysis of Auto-ARGUE on the report generation pilot task from the TREC 2024 NeuCLIR track and on two tasks from the TREC 2024 RAG track, showing good system-level correlations with human judgments. Additionally, we release ARGUE-Viz, a web app for visualization and fine-grained analysis of Auto-ARGUE judgments and scores. △ Less

Submitted 29 April, 2026; v1 submitted 30 September, 2025; originally announced September 2025.

Comments: SIGIR 2026: Demo Track

Distance Approximating Minors for Planar and Minor-Free Graphs

Authors: Hsien-Chih Chang, Jonathan Conroy

Abstract: Given an edge-weighted graph $G$ and a subset of vertices $T$ called terminals, an $α$-distance-approximating minor ($α$-DAM) of $G$ is a graph minor $H$ of $G$ that contains all terminals, such that the distance between every pair of terminals is preserved up to a factor of $α$. Distance-approximating minor would be an effective distance-sketching structure on minor-closed family of graphs; in th… ▽ More Given an edge-weighted graph $G$ and a subset of vertices $T$ called terminals, an $α$-distance-approximating minor ($α$-DAM) of $G$ is a graph minor $H$ of $G$ that contains all terminals, such that the distance between every pair of terminals is preserved up to a factor of $α$. Distance-approximating minor would be an effective distance-sketching structure on minor-closed family of graphs; in the constant-stretch regime it generalizes the well-known Steiner Point Removal problem by allowing the existence of (a small number of) non-terminal vertices. Unfortunately, in the $(1+\varepsilon)$ regime the only known DAM construction for planar graphs relies on overlaying $\tilde{O}_\varepsilon(|T|)$ shortest paths in $G$, which naturally leads to a quadratic bound in the number of terminals [Cheung, Goranci, and Henzinger, ICALP 2016]. We break the quadratic barrier and build the first $(1+\varepsilon)$-distance-approximating minor for $k$-terminal planar graphs and minor-free graphs of near-linear size $\tilde{O}_\varepsilon(k)$. In addition to the near-optimality in size, the construction relies only on the existence of shortest-path separators [Abraham and Gavoille, PODC 2006] and $\varepsilon$-covers [Thorup, J.\ ACM 2004]. Consequently, this provides an alternative and simpler construction to the near-linear-size emulator for planar graphs [Chang, Krauthgamer, and Tan, STOC 2022], as well as the first near-linear-size emulator for minor-free graphs. Our DAM can be constructed in near-linear time. △ Less

Submitted 21 September, 2025; originally announced September 2025.

Comments: 32 pages, 6 figures. Accepted to FOCS 2025

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

Authors: Jonathan Conroy, Arnold Filtser

Abstract: Roughly, a metric space has padding parameter $β$ if for every $Δ>0$, there is a stochastic decomposition of the metric points into clusters of diameter at most $Δ$ such that every ball of radius $γΔ$ is contained in a single cluster with probability at least $e^{-γβ}$. The padding parameter is an important characteristic of a metric space with vast algorithmic implications. In this paper we prove… ▽ More Roughly, a metric space has padding parameter $β$ if for every $Δ>0$, there is a stochastic decomposition of the metric points into clusters of diameter at most $Δ$ such that every ball of radius $γΔ$ is contained in a single cluster with probability at least $e^{-γβ}$. The padding parameter is an important characteristic of a metric space with vast algorithmic implications. In this paper we prove that the shortest path metric of every $K_r$-minor-free graph has padding parameter $O(\log r)$, which is also tight. This resolves a long standing open question, and exponentially improves the previous bound. En route to our main result, we construct sparse covers for $K_r$-minor-free graphs with improved parameters, and we prove a general reduction from sparse covers to padded decompositions. △ Less

Submitted 31 March, 2025; originally announced April 2025.

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Shay Solomon, Cuong Than

Abstract: A $(1+\varepsilon)$-stretch tree cover of an edge-weighted $n$-vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with a constant number of trees, w… ▽ More A $(1+\varepsilon)$-stretch tree cover of an edge-weighted $n$-vertex graph $G$ is a collection of trees, where every pair of vertices has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated Dumbbell Theorem by Arya et. al. [STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with a constant number of trees, where the constant depends on $\varepsilon$ and the dimension $d$. This result was generalized for arbitrary doubling metrics by Bartal et. al. [ICALP'19]. While the total number of edges in the tree covers of Arya et. al. and Bartal et. al. is $O(n)$, all known tree cover constructions incur a total lightness of $Ω(\log n)$; whether one can get a tree cover of constant lightness has remained a longstanding open question, even for 2-dimensional point sets. In this work we resolve this fundamental question in the affirmative, as a direct corollary of a new construction of $(1+\varepsilon)$-stretch spanning tree cover for doubling graphs; in a spanning tree cover, every tree may only use edges of the input graph rather than the corresponding metric. To the best of our knowledge, this is the first constant-stretch spanning tree cover construction (let alone for $(1+\varepsilon)$-stretch) with a constant number of trees, for any nontrivial family of graphs. Concrete applications of our spanning tree cover include a $(1+\varepsilon)$-stretch light tree cover, a compact $(1+\varepsilon)$-stretch routing scheme in the labeled model, and a $(1+\varepsilon)$-stretch path-reporting distance oracle, for doubling graphs. [...] △ Less

Submitted 28 March, 2025; originally announced March 2025.

Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$

Authors: Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michał Pilipczuk

Abstract: Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected $1+\varepsilon$ distortion of $n$-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth $O(\varepsilon^{-1}\log^{13} n)$. Their embedding is the first to achieve polylogarithmic treewidth. However, there remains a large gap between the treewidth of their embedding and… ▽ More Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected $1+\varepsilon$ distortion of $n$-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth $O(\varepsilon^{-1}\log^{13} n)$. Their embedding is the first to achieve polylogarithmic treewidth. However, there remains a large gap between the treewidth of their embedding and the treewidth lower bound of $Ω(\log n)$ shown by Carroll and Goel [CG04]. In this work, we substantially narrow the gap by constructing a stochastic embedding with treewidth $O(\varepsilon^{-1}\log^{3} n)$. We obtain our embedding by improving various steps in the CLPP construction. First, we streamline their embedding construction by showing that one can construct a low-treewidth embedding for any graph from (i) a stochastic hierarchy of clusters and (ii) a stochastic balanced cut. We shave off some logarithmic factors in this step by using a single hierarchy of clusters. Next, we construct a stochastic hierarchy of clusters with optimal separating probability and hop bound based on shortcut partition [CCLMST23, CCLMST24]. Finally, we construct a stochastic balanced cut with an improved trade-off between the cut size and the number of cuts. This is done by a new analysis of the contraction sequence introduced by [CLPP23]; our analysis gives an optimal treewidth bound for graphs admitting a contraction sequence. △ Less

Submitted 31 October, 2024; originally announced November 2024.

Comments: 39 pages, 6 figures

Optimal Euclidean Tree Covers

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than

Abstract: A $(1+\varepsilon)\textit{-stretch tree cover}$ of a metric space is a collection of trees, where every pair of points has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated $\textit{Dumbbell Theorem}$ [Arya et~al. STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with… ▽ More A $(1+\varepsilon)\textit{-stretch tree cover}$ of a metric space is a collection of trees, where every pair of points has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated $\textit{Dumbbell Theorem}$ [Arya et~al. STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d} \cdot \log(1/\varepsilon))$ trees, where the $O_d$ notation suppresses terms that depend solely on the dimension~$d$. The running time of their construction is $O_d(n \log n \cdot \frac{\log(1/\varepsilon)}{\varepsilon^{d}} + n \cdot \varepsilon^{-2d})$. Since the same point may occur in multiple levels of the tree, the $\textit{maximum degree}$ of a point in the tree cover may be as large as $Ω(\log Φ)$, where $Φ$ is the aspect ratio of the input point set. In this work we present a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d+1} \cdot \log(1/\varepsilon))$ trees, which is optimal (up to the $\log(1/\varepsilon)$ factor). Moreover, the maximum degree of points in any tree is an $\textit{absolute constant}$ for any $d$. As a direct corollary, we obtain an optimal {routing scheme} in low-dimensional Euclidean spaces. We also present a $(1+\varepsilon)$-stretch $\textit{Steiner}$ tree cover (that may use Steiner points) with $O_d(\varepsilon^{(-d+1)/{2}} \cdot \log(1/\varepsilon))$ trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive $O_d(n \log n)$ term; this improves over the running time underlying the Dumbbell Theorem. △ Less

Submitted 26 March, 2024; originally announced March 2024.

Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than

Abstract: The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices $u$ and $v$ in the graph, there exists a path between $u$ and $v$ that intersects only a few clusters. They proved that any planar graph admi… ▽ More The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCLMST23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices $u$ and $v$ in the graph, there exists a path between $u$ and $v$ that intersects only a few clusters. They proved that any planar graph admits a shortcut partition and gave several applications, including a construction of tree cover for arbitrary planar graphs with stretch $1+\varepsilon$ and $O(1)$ many trees for any fixed $\varepsilon \in (0,1)$. However, the construction heavily exploits planarity in multiple steps, and is thus inherently limited to planar graphs. In this work, we breach the "planarity barrier" to construct a shortcut partition for $K_r$-minor-free graphs for any $r$. To this end, we take a completely different approach -- our key contribution is a novel deterministic variant of the cop decomposition in minor-free graphs [And86, AGG14]. Our shortcut partition for $K_r$-minor-free graphs yields several direct applications. Most notably, we construct the first optimal distance oracle for $K_r$-minor-free graphs, with $1+\varepsilon$ stretch, linear space, and constant query time for any fixed $\varepsilon \in (0,1)$. The previous best distance oracle [AG06] uses $O(n\log n)$ space and $O(\log n)$ query time, and its construction relies on Robertson-Seymour structural theorem and other sophisticated tools. We also obtain the first tree cover of $O(1)$ size for minor-free graphs with stretch $1+\varepsilon$, while the previous best $(1+\varepsilon)$-tree cover has size $O(\log^2 n)$ [BFN19]. △ Less

Submitted 31 July, 2023; originally announced August 2023.

Summarization from Leaderboards to Practice: Choosing A Representation Backbone and Ensuring Robustness

Authors: David Demeter, Oshin Agarwal, Simon Ben Igeri, Marko Sterbentz, Neil Molino, John M. Conroy, Ani Nenkova

Abstract: Academic literature does not give much guidance on how to build the best possible customer-facing summarization system from existing research components. Here we present analyses to inform the selection of a system backbone from popular models; we find that in both automatic and human evaluation, BART performs better than PEGASUS and T5. We also find that when applied cross-domain, summarizers exh… ▽ More Academic literature does not give much guidance on how to build the best possible customer-facing summarization system from existing research components. Here we present analyses to inform the selection of a system backbone from popular models; we find that in both automatic and human evaluation, BART performs better than PEGASUS and T5. We also find that when applied cross-domain, summarizers exhibit considerably worse performance. At the same time, a system fine-tuned on heterogeneous domains performs well on all domains and will be most suitable for a broad-domain summarizer. Our work highlights the need for heterogeneous domain summarization benchmarks. We find considerable variation in system output that can be captured only with human evaluation and are thus unlikely to be reflected in standard leaderboards with only automatic evaluation. △ Less

Submitted 18 June, 2023; originally announced June 2023.

Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than

Abstract: Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with $O(1)$ trees for planar metrics and an additive embedding into small treewidth graphs. In this note, we apply the same partition to resolve the Steiner point removal (SPR) problem in planar graphs: Given any set $K$ of terminals i… ▽ More Recently the authors [CCLMST23] introduced the notion of shortcut partition of planar graphs and obtained several results from the partition, including a tree cover with $O(1)$ trees for planar metrics and an additive embedding into small treewidth graphs. In this note, we apply the same partition to resolve the Steiner point removal (SPR) problem in planar graphs: Given any set $K$ of terminals in an arbitrary edge-weighted planar graph $G$, we construct a minor $M$ of $G$ whose vertex set is $K$, which preserves the shortest-path distances between all pairs of terminals in $G$ up to a constant factor. This resolves in the affirmative an open problem that has been asked repeatedly in literature. △ Less

Submitted 13 September, 2023; v1 submitted 9 June, 2023; originally announced June 2023.

Comments: Manuscript not intended for publication. The results have been subsumed by arXiv:2308.00555 from the same authors

Covering Planar Metrics (and Beyond): O(1) Trees Suffice

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than

Abstract: While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a \emph{tree cover} of a metric space $(X, δ)$ is a collection of trees, so that every pair of points $u$ and… ▽ More While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a \emph{tree cover} of a metric space $(X, δ)$ is a collection of trees, so that every pair of points $u$ and $v$ in $X$ has a low-distortion path in at least one of the trees. The celebrated "Dumbbell Theorem" [ADMSS95] states that any low-dimensional Euclidean space admits a tree cover with $O(1)$ trees and distortion $1+\varepsilon$, for any fixed $\varepsilon \in (0,1)$. This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19]. Does the same result hold for planar metrics? A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics. In this work, we answer this fundamental question affirmatively. Specifically, we show that for any given fixed $\varepsilon \in (0,1)$, any planar metric can be covered by $O(1)$ trees with distortion $1+\varepsilon$. Our result for planar metrics follows from a rather general framework: First we reduce the problem to constructing tree covers with \emph{additive distortion}. Then we introduce the notion of \emph{shortcut partition}, and draw connection between shortcut partition and additive tree cover. Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs. [...] △ Less

Submitted 5 November, 2023; v1 submitted 9 June, 2023; originally announced June 2023.

Comments: Abstract truncated to fit arXiv limits

Two to Five Truths in Non-Negative Matrix Factorization

Authors: John M. Conroy, Neil P Molino, Brian Baughman, Rod Gomez, Ryan Kaliszewski, Nicholas A. Lines

Abstract: In this paper, we explore the role of matrix scaling on a matrix of counts when building a topic model using non-negative matrix factorization. We present a scaling inspired by the normalized Laplacian (NL) for graphs that can greatly improve the quality of a non-negative matrix factorization. The results parallel those in the spectral graph clustering work of \cite{Priebe:2019}, where the authors… ▽ More In this paper, we explore the role of matrix scaling on a matrix of counts when building a topic model using non-negative matrix factorization. We present a scaling inspired by the normalized Laplacian (NL) for graphs that can greatly improve the quality of a non-negative matrix factorization. The results parallel those in the spectral graph clustering work of \cite{Priebe:2019}, where the authors proved adjacency spectral embedding (ASE) spectral clustering was more likely to discover core-periphery partitions and Laplacian Spectral Embedding (LSE) was more likely to discover affinity partitions. In text analysis non-negative matrix factorization (NMF) is typically used on a matrix of co-occurrence ``contexts'' and ``terms" counts. The matrix scaling inspired by LSE gives significant improvement for text topic models in a variety of datasets. We illustrate the dramatic difference a matrix scalings in NMF can greatly improve the quality of a topic model on three datasets where human annotation is available. Using the adjusted Rand index (ARI), a measure cluster similarity we see an increase of 50\% for Twitter data and over 200\% for a newsgroup dataset versus using counts, which is the analogue of ASE. For clean data, such as those from the Document Understanding Conference, NL gives over 40\% improvement over ASE. We conclude with some analysis of this phenomenon and some connections of this scaling with other matrix scaling methods. △ Less

Submitted 5 September, 2023; v1 submitted 6 May, 2023; originally announced May 2023.

Hop-Spanners for Geometric Intersection Graphs

Authors: Jonathan B. Conroy, Csaba D. Tóth

Abstract: A $t$-spanner of a graph $G=(V,E)$ is a subgraph $H=(V,E')$ that contains a $uv$-path of length at most $t$ for every $uv\in E$. It is known that every $n$-vertex graph admits a $(2k-1)$-spanner with $O(n^{1+1/k})$ edges for $k\geq 1$. This bound is the best possible for $1\leq k\leq 9$ and is conjectured to be optimal due to Erdős' girth conjecture. We study $t$-spanners for $t\in \{2,3\}$ for… ▽ More A $t$-spanner of a graph $G=(V,E)$ is a subgraph $H=(V,E')$ that contains a $uv$-path of length at most $t$ for every $uv\in E$. It is known that every $n$-vertex graph admits a $(2k-1)$-spanner with $O(n^{1+1/k})$ edges for $k\geq 1$. This bound is the best possible for $1\leq k\leq 9$ and is conjectured to be optimal due to Erdős' girth conjecture. We study $t$-spanners for $t\in \{2,3\}$ for geometric intersection graphs in the plane. These spanners are also known as \emph{$t$-hop spanners} to emphasize the use of graph-theoretic distances (as opposed to Euclidean distances between the geometric objects or their centers). We obtain the following results: (1) Every $n$-vertex unit disk graph (UDG) admits a 2-hop spanner with $O(n)$ edges; improving upon the previous bound of $O(n\log n)$. (2) The intersection graph of $n$ axis-aligned fat rectangles admits a 2-hop spanner with $O(n\log n)$ edges, and this bound is tight up to a factor of $\log \log n$. (3) The intersection graph of $n$ fat convex bodies in the plane admits a 3-hop spanner with $O(n\log n)$ edges. (4) The intersection graph of $n$ axis-aligned rectangles admits a 3-hop spanner with $O(n\log^2 n)$ edges. △ Less

Submitted 30 October, 2023; v1 submitted 13 December, 2021; originally announced December 2021.

Comments: 36 pages, 24 figures, full version of an extended abstract in the Proceedings of SoCG 2022

Journal ref: Journal of Computational Geometry 14(2):26-64 (2023)

Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection

Authors: Jonathan Conroy, Christopher Thierauf, Parker Rule, Evan Krause, Hugo Akitaya, Andrei Gonczi, Matias Korman, Matthias Scheutz

Abstract: Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradiation. In this paper, we propose a purpose-made inexpensive robotic platform with off-the-shelf components and standard navigation software that, with… ▽ More Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradiation. In this paper, we propose a purpose-made inexpensive robotic platform with off-the-shelf components and standard navigation software that, with a novel algorithm for finding optimal irradiation locations, addresses both shortcomings to offer affordable and efficient solutions for UVC irradiation. We demonstrate in simulations the efficacy of the algorithm and show a prototypical run of the autonomous integrated robotic system in an indoor environment. In our sample instances, our proposed algorithm reduces the time needed by roughly 30\% while it increases the coverage by a factor of 35\% (when compared to the best possible placement of a static light). △ Less

Submitted 12 April, 2021; v1 submitted 7 April, 2021; originally announced April 2021.

Comments: Preliminary version of this paper will be published in the ICRA 2021 conference

On a 'Two Truths' Phenomenon in Spectral Graph Clustering

Authors: Carey E. Priebe, Youngser Park, Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Minh Tang, Avanti Athreya, Joshua Cape, Eric Bridgeford

Abstract: Clustering is concerned with coherently grouping observations without any explicit concept of true groupings. Spectral graph clustering - clustering the vertices of a graph based on their spectral embedding - is commonly approached via K-means (or, more generally, Gaussian mixture model) clustering composed with either Laplacian or Adjacency spectral embedding (LSE or ASE). Recent theoretical resu… ▽ More Clustering is concerned with coherently grouping observations without any explicit concept of true groupings. Spectral graph clustering - clustering the vertices of a graph based on their spectral embedding - is commonly approached via K-means (or, more generally, Gaussian mixture model) clustering composed with either Laplacian or Adjacency spectral embedding (LSE or ASE). Recent theoretical results provide new understanding of the problem and solutions, and lead us to a 'Two Truths' LSE vs. ASE spectral graph clustering phenomenon convincingly illustrated here via a diffusion MRI connectome data set: the different embedding methods yield different clustering results, with LSE capturing left hemisphere/right hemisphere affinity structure and ASE capturing gray matter/white matter core-periphery structure. △ Less

Submitted 11 February, 2019; v1 submitted 23 August, 2018; originally announced August 2018.

Journal ref: PNAS 116 (2019) 5995-6000

Fast Approximate Quadratic Programming for Large (Brain) Graph Matching

Authors: Joshua T. Vogelstein, John M. Conroy, Vince Lyzinski, Louis J. Podrazik, Steven G. Kratzer, Eric T. Harley, Donniell E. Fishkind, R. Jacob Vogelstein, Carey E. Priebe

Abstract: Quadratic assignment problems (QAPs) arise in a wide variety of domains, ranging from operations research to graph theory to computer vision to neuroscience. In the age of big data, graph valued data is becoming more prominent, and with it, a desire to run algorithms on ever larger graphs. Because QAP is NP-hard, exact algorithms are intractable. Approximate algorithms necessarily employ an accura… ▽ More Quadratic assignment problems (QAPs) arise in a wide variety of domains, ranging from operations research to graph theory to computer vision to neuroscience. In the age of big data, graph valued data is becoming more prominent, and with it, a desire to run algorithms on ever larger graphs. Because QAP is NP-hard, exact algorithms are intractable. Approximate algorithms necessarily employ an accuracy/efficiency trade-off. We developed a fast approximate quadratic assignment algorithm (FAQ). FAQ finds a local optima in (worst case) time cubic in the number of vertices, similar to other approximate QAP algorithms. We demonstrate empirically that our algorithm is faster and achieves a lower objective value on over 80% of the suite of QAP benchmarks, compared with the previous state-of-the-art. Applying the algorithms to our motivating example, matching C. elegans connectomes (brain-graphs), we find that FAQ achieves the optimal performance in record time, whereas none of the others even find the optimum. △ Less

Submitted 13 September, 2014; v1 submitted 22 December, 2011; originally announced December 2011.

Comments: 17 pages, 5 figures, 2 tables