Log in

Relevant bibliographies by topics / Sparsification de graphe / Journal articles

To see the other types of publications on this topic, follow the link: Sparsification de graphe.

Journal articles on the topic 'Sparsification de graphe'

Author: Grafiati

Published: 25 January 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Sparsification de graphe.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

2

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

9

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

14

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

18

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

21

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

22

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

Full text

Abstract:

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].

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Antoniadis, Charalampos, Nestor Evmorfopoulos, and 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, no. 3 (March 2021): 580–90. http://dx.doi.org/10.1109/tvlsi.2021.3049628.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

You, Haoran, Zhihan Lu, Zijian Zhou, Yonggan Fu, and 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, no. 8 (June 28, 2022): 8910–18. http://dx.doi.org/10.1609/aaai.v36i8.20873.

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

33

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Zhao, Xueqian, Lengfei Han, and 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, no. 10 (October 2015): 1639–51. http://dx.doi.org/10.1109/tcad.2015.2424958.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

36

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

37

Han, Lengfei, Xueqian Zhao, and 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, no. 2 (February 2015): 173–85. http://dx.doi.org/10.1109/tcad.2014.2376991.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

39

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

40

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

41

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

Full text

Abstract:

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 .

APA, Harvard, Vancouver, ISO, and other styles

42

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

43

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

45

Zhang, Xikun, Dongjin Song, and 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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

49

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

Full text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

50

Hu, Haojie, Fang He, Fenggan Zhang, Yao Ding, Xin Wu, Jianwei Zhao, and 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.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!