检索结果-内蒙古大学图书馆

Box2flow: Instance-based Action flow graphs from Videos

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Li, Jiatong Basioti, Kalliopi Pavlovic, Vladimir Rutgers University PiscatawayNJ08854 United States

A large amount of procedural videos on the web show how to complete various tasks. These tasks can often be accomplished in different ways and step orderings, with some steps able to be performed simultaneously, while others are constrained to be completed in a specific order. flow graphs can be used to illustrate the step relationships of a task. Current task-based methods try to learn a single flow graph for all available videos of a specific task. The extracted flow graphs tend to be too abstract, failing to capture detailed step descriptions. In this work, our aim is to learn accurate and rich flow graphs by extracting them from a single video. We propose Box2flow, an instance-based method to predict a step flow graph from a given procedural video. In detail, we extract bounding boxes from videos, predict pairwise edge probabilities between step pairs, and build the flow graph with a spanning tree algorithm. Experiments on MM-ReS and YouCookII show our method can extract flow graphs effectively. Copyright © 2024, The Authors. All rights reserved.

关键词： data flow graphs

An OverviewDetail Layout for Visualizing Compound graphs

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Han, Chang Lieffers, Justin Morrison, Clayton Isaacs, Katherine E. The University of Utah United States The University of Arizona United States Lum AI United States

Compound graphs are networks in which vertices can be grouped into larger subsets, with these subsets capable of further grouping, resulting in a nesting that can be many levels deep. In several applications, including biological workflows, chemical equations, and computational data flow analysis, these graphs often exhibit a treelike nesting structure, where sibling clusters are disjoint. Common compound graph layouts prioritize the lowest level of the grouping, down to the individual ungrouped vertices, which can make the higher level grouped structures more difficult to discern, especially in deeply nested networks. Leveraging the additional structure of the tree-like nesting, we contribute an overview+detail layout for this class of compound graphs that preserves the saliency of the higher level network structure when groups are expanded to show internal nested structure. Our layout draws inner structures adjacent to their parents, using a modified tree layout to place substructures. We describe our algorithm and then present case studies demonstrating the layout’s utility to a domain expert working on data flow analysis. Finally, we discuss network parameters and analysis situations in which our layout is well suited. © 2024, CC BY.

关键词： data flow graphs

Using Stream Rewriting for Mapping and Scheduling data flow graphs onto Many-Core Architectures

学校读者我要写书评

暂无评论

Using Stream Rewriting for Mapping and Scheduling Data Flow ...

47th Asilomar Conference on Signals, Systems, and Computers

作者： Haubelt, Christian Ludwig, Florian Middendorf, Lars Zebelein, Christian Univ Rostock D-18055 Rostock Germany

ISBN: (纸本)9781479923908

dataflow graphs, consisting of concurrent actors connected by communication channels, are widely used to model multimedia applications. As dataflow graphs explicitly expose the parallelism contained in the application, they yield well to synthesis for many-core architectures. However, in case of varying and unpredictable workloads, a static mapping of actors to computing resources is often infeasible, but a dynamic approach becomes challenging due to the numerous amount of actors. Our concept of stream-rewriting represents a novel execution semantics for dataflow graphs on many-core architectures, which allows for a completely dynamic binding of actors instances to processing units. In addition, we present a distributed scheduling mechanism, global resource sharing and lightweight lock-free synchronization based on pattern matching. Also, an optimized architecture for stream-rewriting is prototyped and evaluated.

关键词： core construction data flow graphs actor ARCHITECTURE data flow MAPPING(MATHEMATICAL) mapping Communication channels Resource sharing parallelism

Convergence of gradient based training for linear Graph Neural Networks

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Patel, Dhiraj Savostianov, Anton Schaub, Michael T. Computational Network Science RWTH Aachen University Aachen Germany

Graph Neural Networks (GNNs) are powerful tools for addressing learning problems on graph structures, with a wide range of applications in molecular biology and social networks. However, the theoretical foundations underlying their empirical performance are not well understood. In this article, we examine the convergence of gradient dynamics in the training of linear GNNs. Specifically, we prove that the gradient flow training of a linear GNN with mean squared loss converges to the global minimum at an exponential rate. The convergence rate depends explicitly on the initial weights and the graph shift operator, which we validate on synthetic datasets from well-known graph models and real-world datasets. Furthermore, we discuss the gradient flow that minimizes the total weights at the global minimum. In addition to the gradient flow, we study the convergence of linear GNNs under gradient descent training, an iterative scheme viewed as a discretization of gradient *** Codes 05C82, 91020, 92B20, 68T05 © 2025, CC BY.

关键词： data flow graphs

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Duan, Ran Mao, Jiayi Mao, Xiao Shu, Xinkai Yin, Longhui Tsinghua University China Stanford University United States Max Planck Institute for Informatics Germany

We give a deterministic O(m log2/3 n)-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the O(m + n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP. Copyright © 2025, The Authors. All rights reserved.

关键词： data flow graphs

TOPOLOGICAL flow data ANALYSIS FOR TRANSIENT flow PATTERNS: A GRAPH-BASED APPROACH

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Sakajo, Takashi Matsumoto, Takeshi Kaji, Shizuo Yokoyama, Tomoo Uda, Tomoki Department of Mathematics Kyoto University Kyoto606-8502 Japan Department of Physics Kyoto University Kyoto606-8502 Japan Institute of Mathematics for Industry Kyushu University Fukuoka819-0395 Japan Department of Mathematics Saitama University Saitama338-8570 Japan Academic Assembly University of Toyama Toyama930-8555 Japan

We introduce a time-series analysis method for transient two-dimensional flow patterns based on Topological flow data Analysis (TFDA), a new approach to topological data analysis. TFDA identifies local topological flow structures from an instantaneous streamline pattern and describes their global connections as a unique planar tree and its string representation. With TFDA, the evolution of two-dimensional flow patterns is reduced to a discrete dynamical system represented as a transition graph between topologically equivalent streamline patterns. We apply this method to study the lid-driven cavity flow at Reynolds numbers ranging from Re = 14000 to Re = 16000, a benchmark problem in fluid dynamics data analysis. Our approach reveals the transition from periodic to chaotic flow at a critical Reynolds number when the reduced dynamical system is modelled as a Markov process on the transition graph. Additionally, we perform an observational causal inference to analyse changes in local flow patterns at the cavity corners and discuss differences with a standard interventional sensitivity analysis. This work demonstrates the potential of TFDA-based time-series analysis for uncovering complex dynamical behaviours in fluid flow data. © 2025, CC BY-NC-ND.

关键词： data flow graphs

学校读者我要写书评

暂无评论

flow-critical graphs

arXiv 2025年

作者： Árnadóttir, Arnbjörg Soffía Dvořák, Zdeněk Lidický, Bernard Moore, Benjamin Smith-Roberge, Evelyne Šámal, Robert Federal University of Minas Gerais Belo Horizonte Brazil Charles University Prague Czech Republic Iowa State University AmesIA United States Institute of Science and Technology Austria Klosterneuburg Austria Georgia Institute of Technology AtlantaGA United States

Lovász et al. proved that every 6-edge-connected graph has a nowhere-zero 3-flow. In fact, they proved a more technical statement which says that there exists a nowhere zero 3-flow that extends the flow prescribed on the incident edges of a single vertex z with bounded degree. We extend this theorem of Lovász et al. to allow z to have arbitrary degree, but with the additional assumption that there is another vertex x with large degree and no small cut separating x and z. Using this theorem, we prove two results regarding the generation of minimal graphs with the property that prescribing the edges incident to a vertex with specific flow does not extend to a nowhere-zero 3-flow. We use this to further strengthen the theorem of Lovász et al., as well as make progress on a conjecture of Li et al. Copyright © 2025, The Authors. All rights reserved.

关键词： data flow graphs

Compositional imprecise probability

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liell-Cock, Jack Staton, Sam University of Oxford United Kingdom

Imprecise probability is concerned with uncertainty about which probability distributions to use. It has applications in robust statistics and machine learning. We look at programming language models for imprecise probability. Our desiderata are that we would like our model to support all kinds of composition, categorical and monoidal;in other words, guided by dataflow diagrams. Another equivalent perspective is that we would like a model of synthetic probability in the sense of Markov categories. Imprecise probability can be modelled in various ways, with the leading monad-based approach using convex sets of probability distributions. This model is not fully compositional because the monad involved is not commutative, meaning it does not have a proper monoidal structure. In this work, we provide a new fully compositional account. The key idea is to name the non-deterministic choices. To manage the renamings and disjointness of names, we use graded monads. We show that the resulting compositional model is maximal and relate it with the earlier monadic approach, proving that we obtain tighter bounds on the uncertainty. Copyright © 2024, The Authors. All rights reserved.

关键词： data flow graphs

DEFOG: DISCRETE flow MATCHING FOR GRAPH GENERATION

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Qin, Yiming Madeira, Manuel Thanou, Dorina Frossard, Pascal LTS4 EPFL Lausanne Switzerland

Graph generation is fundamental in diverse scientific applications, due to its ability to reveal the underlying distribution of complex data, and eventually generate new, realistic data points. Despite the success of diffusion models in this domain, those face limitations in sampling efficiency and flexibility, stemming from the tight coupling between the training and sampling stages. To address this, we propose DeFoG, a novel framework using discrete flow matching for graph generation. DeFoG employs a flow-based approach that features an efficient linear interpolation noising process and a flexible denoising process based on a continuous-time Markov chain formulation. We leverage an expressive graph transformer and ensure desirable node permutation properties to respect graph symmetry. Crucially, our framework enables a disentangled design of the training and sampling stages, enabling more effective and efficient optimization of model performance. We navigate this design space by introducing several algorithmic improvements that boost the model performance, consistently surpassing existing diffusion models. We also theoretically demonstrate that, for general discrete data, discrete flow models can faithfully replicate the ground truth distribution - a result that naturally extends to graph data and reinforces DeFoG’s foundations. Extensive experiments show that DeFoG achieves state-of-the-art results on synthetic and molecular datasets, improving both training and sampling efficiency over diffusion models, and excels in conditional generation on a digital pathology dataset. © 2024, CC BY.

关键词： data flow graphs