Conecte-se

Bibliografias temáticas / Sparsification de graphe / Artigos de revistas

Siga este link para ver outros tipos de publicações sobre o tema: Sparsification de graphe.

Artigos de revistas sobre o tema "Sparsification de graphe"

Autor: Grafiati

Publicado: 25 de janeiro de 2025

Crie uma referência precisa em APA, MLA, Chicago, Harvard, e outros estilos

Selecione um tipo de fonte:

Veja os 50 melhores artigos de revistas para estudos sobre o assunto "Sparsification de graphe".

Ao lado de cada fonte na lista de referências, há um botão "Adicionar à bibliografia". Clique e geraremos automaticamente a citação bibliográfica do trabalho escolhido no estilo de citação de que você precisa: APA, MLA, Harvard, Chicago, Vancouver, etc.

Você também pode baixar o texto completo da publicação científica em formato .pdf e ler o resumo do trabalho online se estiver presente nos metadados.

Veja os artigos de revistas das mais diversas áreas científicas e compile uma bibliografia correta.

1

Chen, Yuhan, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge e Nishil Talati. "Demystifying Graph Sparsification Algorithms in Graph Properties Preservation". Proceedings of the VLDB Endowment 17, n.º 3 (novembro de 2023): 427–40. http://dx.doi.org/10.14778/3632093.3632106.

Texto completo da fonte

Resumo:

Graph sparsification is a technique that approximates a given graph by a sparse graph with a subset of vertices and/or edges. The goal of an effective sparsification algorithm is to maintain specific graph properties relevant to the downstream task while minimizing the graph's size. Graph algorithms often suffer from long execution time due to the irregularity and the large real-world graph size. Graph sparsification can be applied to greatly reduce the run time of graph algorithms by substituting the full graph with a much smaller sparsified graph, without significantly degrading the output quality. However, the interaction between numerous sparsifiers and graph properties is not widely explored, and the potential of graph sparsification is not fully understood. In this work, we cover 16 widely-used graph metrics, 12 representative graph sparsification algorithms, and 14 real-world input graphs spanning various categories, exhibiting diverse characteristics, sizes, and densities. We developed a framework to extensively assess the performance of these sparsification algorithms against graph metrics, and provide insights to the results. Our study shows that there is no one sparsifier that performs the best in preserving all graph properties, e.g. sparsifiers that preserve distance-related graph properties (eccentricity) struggle to perform well on Graph Neural Networks (GNN). This paper presents a comprehensive experimental study evaluating the performance of sparsification algorithms in preserving essential graph metrics. The insights inform future research in incorporating matching graph sparsification to graph algorithms to maximize benefits while minimizing quality degradation. Furthermore, we provide a framework to facilitate the future evaluation of evolving sparsification algorithms, graph metrics, and ever-growing graph data.

Estilos ABNT, Harvard, Vancouver, APA, etc.

2

Parchas, Panos, Nikolaos Papailiou, Dimitris Papadias e Francesco Bonchi. "Uncertain Graph Sparsification". IEEE Transactions on Knowledge and Data Engineering 30, n.º 12 (1 de dezembro de 2018): 2435–49. http://dx.doi.org/10.1109/tkde.2018.2819651.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

3

Batson, Joshua, Daniel A. Spielman, Nikhil Srivastava e Shang-Hua Teng. "Spectral sparsification of graphs". Communications of the ACM 56, n.º 8 (agosto de 2013): 87–94. http://dx.doi.org/10.1145/2492007.2492029.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

4

Spielman, Daniel A., e Shang-Hua Teng. "Spectral Sparsification of Graphs". SIAM Journal on Computing 40, n.º 4 (janeiro de 2011): 981–1025. http://dx.doi.org/10.1137/08074489x.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

5

Li, Jiayu, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad e Reza Zafarani. "Graph sparsification with graph convolutional networks". International Journal of Data Science and Analytics 13, n.º 1 (13 de outubro de 2021): 33–46. http://dx.doi.org/10.1007/s41060-021-00288-8.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

6

Sun, He, e Luca Zanetti. "Distributed Graph Clustering and Sparsification". ACM Transactions on Parallel Computing 6, n.º 3 (5 de dezembro de 2019): 1–23. http://dx.doi.org/10.1145/3364208.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

7

Spielman, Daniel A., e Nikhil Srivastava. "Graph Sparsification by Effective Resistances". SIAM Journal on Computing 40, n.º 6 (janeiro de 2011): 1913–26. http://dx.doi.org/10.1137/080734029.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

8

Danciu, Daniel, Mikhail Karasikov, Harun Mustafa, André Kahles e Gunnar Rätsch. "Topology-based sparsification of graph annotations". Bioinformatics 37, Supplement_1 (1 de julho de 2021): i169—i176. http://dx.doi.org/10.1093/bioinformatics/btab330.

Texto completo da fonte

Resumo:

Abstract Motivation Since the amount of published biological sequencing data is growing exponentially, efficient methods for storing and indexing this data are more needed than ever to truly benefit from this invaluable resource for biomedical research. Labeled de Bruijn graphs are a frequently-used approach for representing large sets of sequencing data. While significant progress has been made to succinctly represent the graph itself, efficient methods for storing labels on such graphs are still rapidly evolving. Results In this article, we present RowDiff, a new technique for compacting graph labels by leveraging expected similarities in annotations of vertices adjacent in the graph. RowDiff can be constructed in linear time relative to the number of vertices and labels in the graph, and in space proportional to the graph size. In addition, construction can be efficiently parallelized and distributed, making the technique applicable to graphs with trillions of nodes. RowDiff can be viewed as an intermediary sparsification step of the original annotation matrix and can thus naturally be combined with existing generic schemes for compressed binary matrices. Experiments on 10 000 RNA-seq datasets show that RowDiff combined with multi-BRWT results in a 30% reduction in annotation footprint over Mantis-MST, the previously known most compact annotation representation. Experiments on the sparser Fungi subset of the RefSeq collection show that applying RowDiff sparsification reduces the size of individual annotation columns stored as compressed bit vectors by an average factor of 42. When combining RowDiff with a multi-BRWT representation, the resulting annotation is 26 times smaller than Mantis-MST. Availability and implementation RowDiff is implemented in C++ within the MetaGraph framework. The source code and the data used in the experiments are publicly available at https://github.com/ratschlab/row_diff.

Estilos ABNT, Harvard, Vancouver, APA, etc.

9

Fung, Wai-Shing, Ramesh Hariharan, Nicholas J. A. Harvey e Debmalya Panigrahi. "A General Framework for Graph Sparsification". SIAM Journal on Computing 48, n.º 4 (janeiro de 2019): 1196–223. http://dx.doi.org/10.1137/16m1091666.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

10

Broutin, Nicolas, Luc Devroye e Gábor Lugosi. "Almost optimal sparsification of random geometric graphs". Annals of Applied Probability 26, n.º 5 (outubro de 2016): 3078–109. http://dx.doi.org/10.1214/15-aap1170.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

11

Bodwin, Greg. "A note on distance-preserving graph sparsification". Information Processing Letters 174 (março de 2022): 106205. http://dx.doi.org/10.1016/j.ipl.2021.106205.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

12

Vallvé, Joan, Joan Solà e Juan Andrade-Cetto. "Pose-graph SLAM sparsification using factor descent". Robotics and Autonomous Systems 119 (setembro de 2019): 108–18. http://dx.doi.org/10.1016/j.robot.2019.06.004.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

13

Nair, Aditya G., e Kunihiko Taira. "Network-theoretic approach to sparsified discrete vortex dynamics". Journal of Fluid Mechanics 768 (10 de março de 2015): 549–71. http://dx.doi.org/10.1017/jfm.2015.97.

Texto completo da fonte

Resumo:

We examine discrete vortex dynamics in two-dimensional flow through a network-theoretic approach. The interaction of the vortices is represented with a graph, which allows the use of network-theoretic approaches to identify key vortex-to-vortex interactions. We employ sparsification techniques on these graph representations based on spectral theory to construct sparsified models and evaluate the dynamics of vortices in the sparsified set-up. Identification of vortex structures based on graph sparsification and sparse vortex dynamics is illustrated through an example of point-vortex clusters interacting amongst themselves. We also evaluate the performance of sparsification with increasing number of point vortices. The sparsified-dynamics model developed with spectral graph theory requires a reduced number of vortex-to-vortex interactions but agrees well with the full nonlinear dynamics. Furthermore, the sparsified model derived from the sparse graphs conserves the invariants of discrete vortex dynamics. We highlight the similarities and differences between the present sparsified-dynamics model and reduced-order models.

Estilos ABNT, Harvard, Vancouver, APA, etc.

14

Imre, Martin, Jun Tao, Yongyu Wang, Zhiqiang Zhao, Zhuo Feng e Chaoli Wang. "Spectrum-preserving sparsification for visualization of big graphs". Computers & Graphics 87 (abril de 2020): 89–102. http://dx.doi.org/10.1016/j.cag.2020.02.004.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

15

Goranci, Gramoz, Monika Henzinger e Pan Peng. "Improved Guarantees for Vertex Sparsification in Planar Graphs". SIAM Journal on Discrete Mathematics 34, n.º 1 (janeiro de 2020): 130–62. http://dx.doi.org/10.1137/17m1163153.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

16

Tale, Prafullkumar. "Sparsification lower bound for linear spanners in directed graphs". Theoretical Computer Science 898 (janeiro de 2022): 69–74. http://dx.doi.org/10.1016/j.tcs.2021.10.022.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

17

Sutic, Davor, e Ervin Varga. "Scaling industrial applications for the big data era". Computer Science and Information Systems, n.º 00 (2021): 39. http://dx.doi.org/10.2298/csis200531039s.

Texto completo da fonte

Resumo:

Industrial applications tend to rely increasingly on large datasets for regular operations. In order to facilitate that need, we unite the increasingly available hardware resources with fundamental problems found in classical algorithms. We show solutions to the following problems: power flow and island detection in power networks, and the more general graph sparsification. At their core lie respectively algorithms for solving systems of linear equations, graph connectivity and matrix multiplication, and spectral sparsification of graphs, which are applicable on their own to a far greater spectrum of problems. The novelty of our approach lies in developing the first open source and distributed solutions, capable of handling large datasets. Such solutions constitute a toolkit, which, aside from the initial purpose, can be used for the development of unrelated applications and for educational purposes in the study of distributed algorithms.

Estilos ABNT, Harvard, Vancouver, APA, etc.

18

Koutis, Ioannis, e Shen Chen Xu. "Simple Parallel and Distributed Algorithms for Spectral Graph Sparsification". ACM Transactions on Parallel Computing 3, n.º 2 (8 de agosto de 2016): 1–14. http://dx.doi.org/10.1145/2948062.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

19

Eppstein, David, Zvi Galil, Giuseppe F. Italiano e Amnon Nissenzweig. "Sparsification—a technique for speeding up dynamic graph algorithms". Journal of the ACM 44, n.º 5 (setembro de 1997): 669–96. http://dx.doi.org/10.1145/265910.265914.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

20

Cheng, Yu, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff e Jason Zhang. "Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut". Proceedings of the ACM on Management of Data 2, n.º 2 (10 de maio de 2024): 1–18. http://dx.doi.org/10.1145/3651148.

Texto completo da fonte

Resumo:

In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 ± ε)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires Ω(n 2 ) bits even for constant ε. To circumvent this, recent works study β-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most β times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous Ømega(n √β/ε) lower bound in the for-each model to ~Ω (n √β /ε) and we improve the previous Ω(n β/ε) lower bound in the for-all model to Ω(n β/ε 2 ). This resolves the main open questions of (Cen et al., ICALP, 2021). The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an ΩL(min m, m/ε 2 k R) lower bound for this problem, which improves the previous ΩL(m/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+ε)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors.

Estilos ABNT, Harvard, Vancouver, APA, etc.

21

Chandran, L. Sunil, e Rishikesh Gajjala. "Graph-theoretic insights on the constructability of complex entangled states". Quantum 8 (3 de julho de 2024): 1396. http://dx.doi.org/10.22331/q-2024-07-03-1396.

Texto completo da fonte

Resumo:

The most efficient automated way to construct a large class of quantum photonic experiments is via abstract representation of graphs with certain properties. While new directions were explored using Artificial intelligence and SAT solvers to find such graphs, it becomes computationally infeasible to do so as the size of the graph increases. So, we take an analytical approach and introduce the technique of local sparsification on experiment graphs, using which we answer a crucial open question in experimental quantum optics, namely whether certain complex entangled quantum states can be constructed. This provides us with more insights into quantum resource theory, the limitation of specific quantum photonic systems and initiates the use of graph-theoretic techniques for designing quantum physics experiments.

Estilos ABNT, Harvard, Vancouver, APA, etc.

22

Czumaj, Artur, Peter Davies e Merav Parter. "Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space". ACM Transactions on Algorithms 17, n.º 2 (junho de 2021): 1–27. http://dx.doi.org/10.1145/3451992.

Texto completo da fonte

Resumo:

The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n , the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O (log Δ + log log n )-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O ( n ɛ ) space on each machine for any constant ɛ > 0. These algorithms also run in O (log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O (log 2 Δ) rounds by Censor-Hillel et al. [DISC’17].

Estilos ABNT, Harvard, Vancouver, APA, etc.

23

Kiouche, Abd Errahmane, Hamida Seba e Karima Amrouche. "A maximum diversity-based path sparsification for geometric graph matching". Pattern Recognition Letters 152 (dezembro de 2021): 107–14. http://dx.doi.org/10.1016/j.patrec.2021.09.019.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

24

Vallve, Joan, Joan Sola e Juan Andrade-Cetto. "Graph SLAM Sparsification With Populated Topologies Using Factor Descent Optimization". IEEE Robotics and Automation Letters 3, n.º 2 (abril de 2018): 1322–29. http://dx.doi.org/10.1109/lra.2018.2798283.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

25

Apers, Simon, e Ronald de Wolf. "Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving". SIAM Journal on Computing 51, n.º 6 (16 de dezembro de 2022): 1703–42. http://dx.doi.org/10.1137/21m1391018.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

26

Batjargal, Dolgorsuren, Kifayat Ullah Khan e Young-Koo Lee. "EM-FGS: Graph sparsification via faster semi-metric edges pruning". Applied Intelligence 49, n.º 10 (3 de maio de 2019): 3731–48. http://dx.doi.org/10.1007/s10489-019-01479-4.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

27

Nam, Jiyeon, Soojeong Hyeon, Youngjun Joo, DongKi Noh e Hyungbo Shim. "Spectral Trade-Off for Measurement Sparsification of Pose-Graph SLAM". IEEE Robotics and Automation Letters 9, n.º 1 (janeiro de 2024): 723–30. http://dx.doi.org/10.1109/lra.2023.3337590.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

28

Pilipczuk, Marcin, Michał Pilipczuk, Piotr Sankowski e Erik Jan Van Leeuwen. "Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs". ACM Transactions on Algorithms 14, n.º 4 (13 de outubro de 2018): 1–73. http://dx.doi.org/10.1145/3239560.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

29

Jansen, Bart M. P., e Astrid Pieterse. "Sparsification Upper and Lower Bounds for Graph Problems and Not-All-Equal SAT". Algorithmica 79, n.º 1 (22 de agosto de 2016): 3–28. http://dx.doi.org/10.1007/s00453-016-0189-9.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

30

Houle, Michael E., Xiguo Ma, Vincent Oria e Jichao Sun. "Improving the quality of K-NN graphs through vector sparsification: application to image databases". International Journal of Multimedia Information Retrieval 3, n.º 4 (21 de setembro de 2014): 259–74. http://dx.doi.org/10.1007/s13735-014-0067-7.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

31

Antoniadis, Charalampos, Nestor Evmorfopoulos e Georgios Stamoulis. "Graph-Based Sparsification and Synthesis of Dense Matrices in the Reduction of RLC Circuits". IEEE Transactions on Very Large Scale Integration (VLSI) Systems 29, n.º 3 (março de 2021): 580–90. http://dx.doi.org/10.1109/tvlsi.2021.3049628.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

32

You, Haoran, Zhihan Lu, Zijian Zhou, Yonggan Fu e Yingyan Lin. "Early-Bird GCNs: Graph-Network Co-optimization towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets". Proceedings of the AAAI Conference on Artificial Intelligence 36, n.º 8 (28 de junho de 2022): 8910–18. http://dx.doi.org/10.1609/aaai.v36i8.20873.

Texto completo da fonte

Resumo:

Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art deep learning model for representation learning on graphs. However, it remains notoriously challenging to train and inference GCNs over large graph datasets, limiting their application to large real-world graphs and hindering the exploration of deeper and more sophisticated GCN graphs. This is because as the graph size grows, the sheer number of node features and the large adjacency matrix can easily explode the required memory and data movements. To tackle the aforementioned challenges, we explore the possibility of drawing lottery tickets when sparsifying GCN graphs, i.e., subgraphs that largely shrink the adjacency matrix yet are capable of achieving accuracy comparable to or even better than their full graphs. Specifically, we for the first time discover the existence of graph early-bird (GEB) tickets that emerge at the very early stage when sparsifying GCN graphs, and propose a simple yet effective detector to automatically identify the emergence of such GEB tickets. Furthermore, we advocate graph-model co-optimization and develop a generic efficient GCN early-bird training framework dubbed GEBT that can significantly boost the efficiency of GCN training by (1) drawing joint early-bird tickets between the GCN graphs and models and (2) enabling simultaneously sparsification of both the GCN graphs and models. Experiments on various GCN models and datasets consistently validate our GEB finding and the effectiveness of our GEBT, e.g., our GEBT achieves up to 80.2% ~ 85.6% and 84.6% ~ 87.5% savings of GCN training and inference costs while offering a comparable or even better accuracy as compared to state-of-the-art methods. Our source code and supplementary appendix are available at https://github.com/RICE-EIC/Early-Bird-GCN.

Estilos ABNT, Harvard, Vancouver, APA, etc.

33

Shen, Xiao, Sitong Mao e Fu-lai Chung. "Cross-Network Learning With Fuzzy Labels for Seed Selection and Graph Sparsification in Influence Maximization". IEEE Transactions on Fuzzy Systems 28, n.º 9 (setembro de 2020): 2195–208. http://dx.doi.org/10.1109/tfuzz.2019.2931272.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

34

Zhao, Xueqian, Lengfei Han e Zhuo Feng. "A Performance-Guided Graph Sparsification Approach to Scalable and Robust SPICE-Accurate Integrated Circuit Simulations". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34, n.º 10 (outubro de 2015): 1639–51. http://dx.doi.org/10.1109/tcad.2015.2424958.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

35

Shu, Tong, e Young Hoon Joo. "Non-Centralised Balance Dispatch Strategy in Waked Wind Farms through a Graph Sparsification Partitioning Approach". Energies 16, n.º 20 (18 de outubro de 2023): 7131. http://dx.doi.org/10.3390/en16207131.

Texto completo da fonte

Resumo:

A novel non-centralised dispatch strategy is presented for wake redirection to optimise large-scale offshore wind farms operation, creating a balanced control between power production and fatigue thrust loads evenly among the wind turbines. This approach is founded on a graph sparsification partitioning strategy that takes into account the impact of wake propagation. More specifically, the breadth-first search algorithm is employed to identify the subgraph based on the connectivity of the wake direction graph, while the PageRank centrality computation algorithm is utilised to determine and rank scores for the shared turbines’ affiliation with the subgraphs. By doing so, the wind farm is divided into smaller subsets of partitioned turbines, resulting in decoupling. The objective function is then formulated by incorporating penalty terms, specifically the standard deviation of fatigue thrust loads, into the maximum power equation. Meanwhile, the non-centralisation sequential quadratic programming optimisation algorithm is subsequently employed within each partition to determine the control actions while considering the objectives of the respective controllers. Finally, the simulation results of case studies prove to reduce computational costs and improve wind farm power production by balancing accumulated fatigue thrust loads over the operational lifetime as much as possible.

Estilos ABNT, Harvard, Vancouver, APA, etc.

36

Yaşar, Abdurrahman, Muhammed Fati̇h Balin, Xiaojing An, Kaan Sancak e Ümit V. Çatalyürek. "On Symmetric Rectilinear Partitioning". ACM Journal of Experimental Algorithmics 27 (31 de dezembro de 2022): 1–26. http://dx.doi.org/10.1145/3523750.

Texto completo da fonte

Resumo:

Even distribution of irregular workload to processing units is crucial for efficient parallelization in many applications. In this work, we are concerned with a spatial partitioning called rectilinear partitioning (also known as generalized block distribution). More specifically, we address the problem of symmetric rectilinear partitioning of two dimensional domains, and utilize sparse matrices to model them. By symmetric, we mean both dimensions (i.e., the rows and columns of the matrix) are identically partitioned yielding a tiling where the diagonal tiles (blocks) will be squares. We first show that the optimal solution to this problem is NP-hard, and we propose four heuristics to solve two different variants of this problem. To make the proposed techniques more applicable in real life application scenarios, we further reduce their computational complexities by utilizing effective sparsification strategies together with an efficient sparse prefix-sum data structure. We experimentally show the proposed algorithms are efficient and effective on more than six hundred test matrices/graphs.

Estilos ABNT, Harvard, Vancouver, APA, etc.

37

Han, Lengfei, Xueqian Zhao e Zhuo Feng. "An Adaptive Graph Sparsification Approach to Scalable Harmonic Balance Analysis of Strongly Nonlinear Post-Layout RF Circuits". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34, n.º 2 (fevereiro de 2015): 173–85. http://dx.doi.org/10.1109/tcad.2014.2376991.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

38

Geetanjali Kale (Rao). "BUGTGNN: Bayesian Uncertainty and Game Theory for Enhancing Graph Neural Networks through Mathematical Analysis". Advances in Nonlinear Variational Inequalities 28, n.º 2 (9 de outubro de 2024): 84–105. http://dx.doi.org/10.52783/anvi.v28.1853.

Texto completo da fonte

Resumo:

The ongoing COVID-19 pandemic has emphasized the critical need for rapid and accurate diagnostic methods. Precise classification of chest X-ray images into COVID-19 and non-COVID-19 cases serves as a pivotal tool in effective disease management and control. Existing methods often suffer from trade-offs between accuracy, precision, and computational efficiency, hindering their practical utility. Current approaches mainly rely on traditional machine learning algorithms or Convolutional Neural Networks (CNNs), which while effective, still present limitations in terms of sensitivity, specificity, and computational speed. These constraints necessitate the exploration of innovative techniques for improving classification metrics across multiple dimensions. In this work, we introduce a novel framework for optimizing Graph Neural Networks (GNNs) through mathematical analysis, specifically incorporating spectral methods, dynamic graph sparsification, game-theoretic attention mechanisms, Bayesian uncertainty models, and advanced graph partitioning techniques. When applied to the classification of COVID-19 chest X-rays, our model demonstrated significant improvements—increasing precision by 8.3%, accuracy by 8.5%, recall by 4.9%, specificity by 4.5%, and the Area Under the Curve (AUC) by 5.9%, while simultaneously reducing computational delay by 10.5% across multiple datasets. The proposed optimization strategies showcase the power of interdisciplinary approaches in advancing machine learning techniques for medical applications. The demonstrated improvements in classification metrics and computational efficiency highlight the model's potential for broader adoption in healthcare settings, providing a robust, fast, and more accurate tool for COVID-19 diagnosis.

Estilos ABNT, Harvard, Vancouver, APA, etc.

39

Zou, Muquan, Lizhen Wang, Pingping Wu e Vanha Tran. "Efficiently mining maximal l-reachability co-location patterns from spatial data sets". Intelligent Data Analysis 27, n.º 1 (30 de janeiro de 2023): 269–95. http://dx.doi.org/10.3233/ida-216515.

Texto completo da fonte

Resumo:

A co-location pattern is a set of spatial features that are strongly correlated in space. However, some of these patterns could be neglected if the prevalence metrics are based solely on the clique (or star) relationship. Hence, the l-reachability co-location pattern is proposed by introducing the l-reachability clique where the members of each instance pair can be reachable to each other in a given step length l. Because the average size of l-reachability co-location patterns tends to be longer, maximal l-reachability co-location pattern mining is researched in this paper. First, some sparsification strategies are introduced to shorten star neighborhood lists of instances in an updated graph called the l-reachability neighbor relationship graph, and then, they are grouped by their corresponding patterns. Second, candidate maximal l-reachability co-location patterns are iteratively detected in a size-independent way on bi-graphs that contain group keys and their intersection sets. Third, the prevalence of each candidate maximal l-reachability co-location pattern is checked in a binary search way with a natural l-reachability clique called the ⌊l/2⌋-reachability neighborhood list. Finally, the effectiveness and efficiency of our model and algorithms are analyzed by extensive comparison experiments on synthetic and real-world spatial data sets.

Estilos ABNT, Harvard, Vancouver, APA, etc.

40

Zhang, Ying, Zhiqiang Zhao e Zhuo Feng. "diGRASS: Di rected Gra ph S pectral S parsification via Spectrum-Preserving Symmetrization". ACM Transactions on Knowledge Discovery from Data, 4 de janeiro de 2024. http://dx.doi.org/10.1145/3639568.

Texto completo da fonte

Resumo:

Recent spectral graph sparsification research aims to construct ultra-sparse subgraphs for preserving the original graph spectral (structural) properties, such as the first few Laplacian eigenvalues and eigenvectors, which has led to the development of a variety of nearly-linear time numerical and graph algorithms. However, there is very limited progress for spectral sparsification of directed graphs. In this work, we prove the existence of nearly-linear-sized spectral sparsifiers for directed graphs under certain conditions. Furthermore, we introduce a practically-efficient spectral algorithm (diGRASS) for sparsifying real-world, large-scale directed graphs leveraging spectral matrix perturbation analysis. The proposed method has been evaluated using a variety of directed graphs obtained from real-world applications, showing promising results for solving directed graph Laplacians, spectral partitioning of directed graphs, and approximately computing (personalized) PageRank vectors.

Estilos ABNT, Harvard, Vancouver, APA, etc.

41

Pelleg, Eden, e Stanislav Živný. "Additive Sparsification of CSPs". ACM Transactions on Algorithms, 30 de setembro de 2023. http://dx.doi.org/10.1145/3625824.

Texto completo da fonte

Resumo:

Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC’96], have proved extremely influential and found various applications. Precise characterisations were established for sparsifiability of graphs with other 2-variable predicates on Boolean domains by Filtser and Krauthgamer [SIDMA’17] and non-Boolean domains by Butti and Živný [SIDMA’20]. Bansal, Svensson and Trevisan [FOCS’19] introduced a weaker notion of sparsification termed “additive sparsification”, which does not require weights on the edges of the graph. In particular, Bansal et al. designed algorithms for additive sparsifiers for cuts in graphs and hypergraphs. As our main result, we establish that all Boolean Constraint Satisfaction Problems (CSPs) admit an additive sparsifier; that is, for every Boolean predicate P : {0, 1} k → {0, 1} of a fixed arity k , we show that CSP(P) admits an additive sparsifier. Under our newly introduced notion of all-but-one sparsification for non-Boolean predicates, we show that CSP(P) admits an additive sparsifier for any predicate P : D k → {0, 1} of a fixed arity k on an arbitrary finite domain D .

Estilos ABNT, Harvard, Vancouver, APA, etc.

42

Forster, Sebastian, e Tijn de Vos. "Faster Cut Sparsification of Weighted Graphs". Algorithmica, 1 de novembro de 2022. http://dx.doi.org/10.1007/s00453-022-01053-4.

Texto completo da fonte

Resumo:

AbstractA cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $$(1\pm \epsilon )$$ ( 1 ± ϵ ) . This paper considers computing cut sparsifiers of weighted graphs of size $$O(n\log (n)/\epsilon ^2)$$ O ( n log ( n ) / ϵ 2 ) . Our algorithm computes such a sparsifier in time $$O(m\cdot \min (\alpha (n)\log (m/n),\log (n)))$$ O ( m · min ( α ( n ) log ( m / n ) , log ( n ) ) ) , both for graphs with polynomially bounded and unbounded integer weights, where $$\alpha (\cdot )$$ α ( · ) is the functional inverse of Ackermann’s function. This improves upon the state of the art by Benczúr and Karger (SICOMP, 2015), which takes $$O(m\log ^2 (n))$$ O ( m log 2 ( n ) ) time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP, 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi–Ibaraki forest packing. MSF packings have previously been used by Abraham et al. (FOCS, 2016) in the dynamic setting, and are defined as follows: an M-partial MSF packing of G is a set $$\mathcal {F}=\{F_1, \ldots , F_M\}$$ F = { F 1 , … , F M } , where $$F_i$$ F i is a maximum spanning forest in $$G{\setminus } \bigcup _{j=1}^{i-1}F_j$$ G \ ⋃ j = 1 i - 1 F j . Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

Estilos ABNT, Harvard, Vancouver, APA, etc.

43

Lai, Ming-Jun, e Jiaxin Xie and Zhiqiang Xu. "Graph Sparsification by Universal Greedy Algorithms". Journal of Computational Mathematics, março de 2023, 0. http://dx.doi.org/10.4208/jcm.2201-m2021-0130.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

44

Ali, Sarwan, Muhammad Ahmad, Maham Anwer Beg, Imdad Ullah Khan, Safiullah Faizullah e Muhammad Asad Khan. "SsAG : Summarization and Sparsification of Attributed Graphs". ACM Transactions on Knowledge Discovery from Data, 6 de março de 2024. http://dx.doi.org/10.1145/3651619.

Texto completo da fonte

Resumo:

Graph summarization has become integral for managing and analyzing large-scale graphs in diverse real-world applications, including social networks, biological networks, and communication networks. Existing methods for graph summarization often face challenges, being either computationally expensive, limiting their applicability to large graphs, or lacking the incorporation of node attributes. In response, we introduce SsAG , an efficient and scalable lossy graph summarization method designed to preserve the essential structure of the original graph. SsAG computes a sparse representation (summary) of the input graph, accommodating graphs with node attributes. The summary is structured as a graph on supernodes (subsets of vertices of G ), where weighted superedges connect pairs of supernodes. The methodology focuses on constructing a summary graph with k supernodes, aiming to minimize the reconstruction error (the difference between the original graph and the graph reconstructed from the summary) while maximizing homogeneity with respect to the node attributes. The construction process involves iteratively merging pairs of nodes. To enhance computational efficiency, we derive a closed-form expression for efficiently computing the reconstruction error (RE) after merging a pair, enabling constant-time approximation of this score. We assign a weight to each supernode, quantifying their contribution to the score of pairs, and utilize a weighted sampling strategy to select the best pair for merging. Notably, a logarithmic-sized sample achieves a summary comparable in quality based on various measures. Additionally, we propose a sparsification step for the constructed summary, aiming to reduce storage costs to a specified target size with a marginal increase in RE. Empirical evaluations across diverse real-world graphs demonstrate that SsAG exhibits superior speed, being up to 17 × faster, while generating summaries of comparable quality. This work represents a significant advancement in the field, addressing computational challenges and showcasing the effectiveness of SsAG in graph summarization.

Estilos ABNT, Harvard, Vancouver, APA, etc.

45

Zhang, Xikun, Dongjin Song e Dacheng Tao. "Ricci Curvature-Based Graph Sparsification for Continual Graph Representation Learning". IEEE Transactions on Neural Networks and Learning Systems, 2023, 1–13. http://dx.doi.org/10.1109/tnnls.2023.3303454.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

46

Chen, Hubie, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse e PaweŁRzĄŻewski. "Sparsification Lower Bounds for List H -Coloring". ACM Transactions on Computation Theory, 15 de setembro de 2023. http://dx.doi.org/10.1145/3612938.

Texto completo da fonte

Resumo:

We investigate the List H -Coloring problem, the generalization of graph coloring that asks whether an input graph G admits a homomorphism to the undirected graph H (possibly with loops), such that each vertex v ∈ V ( G ) is mapped to a vertex on its list L ( v )⊆ V ( H ). An important result by Feder, Hell, and Huang [JGT 2003] states that List H -Coloring is polynomial-time solvable if H is a so-called bi-arc graph , and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an n -vertex instance be efficiently reduced to an equivalent instance of bitsize \(\mathcal {O}(n^{2-\varepsilon }) \) for some ε > 0? We prove that if H is not a bi-arc graph, then List H -Coloring does not admit such a sparsification algorithm unless \({\mathsf {NP \subseteq coNP/poly}} \) . Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs H which are not bi- graphs.

Estilos ABNT, Harvard, Vancouver, APA, etc.

47

Feng, Zhuo. "GRASS: GRAph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 1. http://dx.doi.org/10.1109/tcad.2020.2968543.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

48

Jain, Chirag. "Coverage-preserving sparsification of overlap graphs for long-read assembly". Bioinformatics, 9 de março de 2023. http://dx.doi.org/10.1093/bioinformatics/btad124.

Texto completo da fonte

Resumo:

Abstract Read-overlap-based graph data structures play a central role in computing de novo genome assembly. Most long-read assemblers use Myers’s string graph model to sparsify overlap graphs. Graph sparsification improves assembly contiguity by removing spurious and redundant connections. However, a graph model must be coverage-preserving, i.e., it must ensure that there exist walks in the graph that spell all chromosomes, given sufficient sequencing coverage. This property becomes even more important for diploid genomes, polyploid genomes and metagenomes where there is a risk of losing haplotype-specific information. We develop a novel theoretical framework under which the coverage-preserving properties of a graph model can be analysed. We first prove that de Bruijn graph and overlap graph models are guaranteed to be coverage-preserving. We next show that the standard string graph model lacks this guarantee. The latter result is consistent with the observation made in (Hui et al., 2016) that removal of contained reads, i.e., the reads that are substrings of other reads, can lead to coverage gaps during string graph construction. Our experiments done using simulated long reads from HG002 human diploid genome show that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets. To remedy this, we propose practical heuristics that are well-supported by our theoretical results, and are useful to decide which contained reads should be retained to avoid coverage gaps. Our method retains a small fraction of contained reads (1 – 2%) and closes majority of the coverage gaps. Implementation Source code is available through GitHub (https://github.com/at-cg/ContainX) and Zenodo with doi: 10.5281/zenodo.7687543

Estilos ABNT, Harvard, Vancouver, APA, etc.

49

Zhang, Yihao, Yuhao Wang, Wei Zhou, Pengxiang Lan, Haoran Xiang, Junlin Zhu e Meng Yuan. "Conversational recommender based on graph sparsification and multi-hop attention". Intelligent Data Analysis, 14 de setembro de 2023, 1–21. http://dx.doi.org/10.3233/ida-230148.

Texto completo da fonte

Resumo:

Conversational recommender systems provide users with item recommendations via interactive dialogues. Existing methods using graph neural networks have been proven to be an adequate representation of the learning framework for knowledge graphs. However, the knowledge graph involved in the dialogue context is vast and noisy, especially the noise graph nodes, which restrict the primary node’s aggregation to neighbor nodes. In addition, although the recurrent neural network can encode the local structure of word sequences in a dialogue context, it may still be challenging to remember long-term dependencies. To tackle these problems, we propose a sparse multi-hop conversational recommender model named SMCR, which accurately identifies important edges through matching items, thus reducing the computational complexity of sparse graphs. Specifically, we design a multi-hop attention network to encode dialogue context, which can quickly encode the long dialogue sequences to capture the long-term dependencies. Furthermore, we utilize a variational auto-encoder to learn topic information for capturing syntactic dependencies. Extensive experiments on the travel dialogue dataset show significant improvements in our proposed model over the state-of-the-art methods in evaluating recommendation and dialogue generation.

Estilos ABNT, Harvard, Vancouver, APA, etc.

50

Hu, Haojie, Fang He, Fenggan Zhang, Yao Ding, Xin Wu, Jianwei Zhao e Minli Yao. "Unifying Label Propagation and Graph Sparsification for Hyperspectral Image Classification". IEEE Geoscience and Remote Sensing Letters, 2022, 1. http://dx.doi.org/10.1109/lgrs.2022.3178708.

Texto completo da fonte

Estilos ABNT, Harvard, Vancouver, APA, etc.

Oferecemos descontos em todos os planos premium para autores cujas obras estão incluídas em seleções literárias temáticas. Contate-nos para obter um código promocional único!