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

THE ORIENTED graph COMPLEX REVISITED

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Merkulov, Sergei Willwacher, Thomas Wolff, Vincent Department of Mathematics Luxembourg University Maison du Nombre 6 Avenue de la Fonte Grand Duchy Esch-sur-AlzetteL-4364 Luxembourg Department of Mathematics ETH Zurich Zurich Switzerland

关键词： graph algorithms

Parallel Triangles and Squares Count for Multigraphs Using Vertex Covers 23rd

学校读者我要写书评

暂无评论

Parallel Triangles and Squares Count for Multigraphs Using...

23rd International Conference on Computational Science, ICCS 2023

作者： Cappelletti, Luca Fontana, Tommaso Green, Oded Bader, David University of Milan Milan Italy New Jersey Institute of Technology Newark United States Georgia Tech AtlantaGA United States

ISBN: (纸本)9783031360268

Triangles and squares count are widely-used graph analytic metrics providing insights into the connectivity of a graph. While the literature has focused on algorithms for global counts in simple graphs, this paper presents parallel algorithms for global and per-node triangle and square counts in large multigraphs. The algorithms have linear improvements in computational complexity as the number of cores increases. The triangle count algorithm has the same complexity as the best-known algorithm in the literature. The squares count algorithm has a lower execution time than previous methods. The proposed algorithms are evaluated on six real-world graphs and multigraphs, including protein-protein interaction graphs, knowledge graphs and large web graphs. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

关键词： graph algorithms

CERTAIN FINITE GROUPS WHOSE COMMUTING CONJUGACY CLASS graph SATISFY HANSEN-VUKIČEVIĆ CONJECTURE

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Das, Shrabani Nath, Rajat Kanti Department of Mathematical Sciences Tezpur University Sonitpur Assam Napaam784028 India

In this paper we compute first and second Zagreb indices of commuting conjugacy class graphs of finite groups and determine several classes of finite groups such that their commuting conjugacy class graphs satisfy Han... 详细信息

关键词： graph algorithms

ITERATION OF THE MINCUT graph OPERATOR

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kriel, Christo Mphako-Banda, Eunice School of Mathematics University of the Witwatersrand PB 3 Wits 2050 South Africa

A graph operator is a mapping which maps every graph G from some class of graphs to a new graph (G). In this paper, we introduce and study the properties of the mincut operator, specifically the effects of iteration of the operator. We show that the property of being super edge-connected and regular is both necessary and sufficient for a graph to remain fixed under the mincut operator. Furthermore, we show that no graph diverges under iteration of this operator. We conclude by stating further research questions on the mincut operator. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

graph Agnostic Causal Bayesian Optimisation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Mukherjee, Sumantrak Zhang, Mengyan Flaxman, Seth Vollmer, Sebastian J. Germany Department of Computer Science University of Oxford United Kingdom Department of Computer Science University of Kaiserslautern-Landau Germany

We study the problem of globally optimising a target variable of an unknown causal graph on which a sequence of soft or hard interventions can be performed. The problem of optimising the target variable associated with a causal graph is formalised as Causal Bayesian Optimisation (CBO), which has various applications in biology, manufacturing, and healthcare. However, in many real-world applications, the true data-generating process is often unknown or partially known. We study the CBO problem with unknown causal graphs for two settings, namely structural causal models with hard interventions and function networks with soft interventions. We propose graph Agnostic Causal Bayesian Optimisation (GACBO), an algorithm that actively discovers the causal structure that contributes to achieving optimal rewards. GACBO seeks to balance exploiting the actions that give the best rewards against exploring the causal structures and functions. We show our proposed algorithm outperforms baselines in simulated experiments and real-world applications. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

SpreadFGL: Edge-Client Collaborative Federated graph Learning with Adaptive Neighbor Generation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zhong, Luying Pi, Yueyang Chen, Zheyi Yu, Zhengxin Miao, Wang Chen, Xing Min, Geyong College of Computer and Data Science Fuzhou University China Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing Fuzhou University China Engineering Research Center of Big Data Intelligence Ministry of Education China School of Computing and Communications University of Lancaster United Kingdom School of Engineering Computing and Mathematics University of Plymouth United Kingdom Department of Computer Science University of Exeter United Kingdom

Federated graph Learning (FGL) has garnered widespread attention by enabling collaborative training on multiple clients for semi-supervised classification tasks. However, most existing FGL studies do not well consider the missing inter-client topology information in real-world scenarios, causing insufficient feature aggregation of multi-hop neighbor clients during model training. Moreover, the classic FGL commonly adopts the FedAvg but neglects the high training costs when the number of clients expands, resulting in the overload of a single edge server. To address these important challenges, we propose a novel FGL framework, named SpreadFGL, to promote the information flow in edge-client collaboration and extract more generalized potential relationships between clients. In SpreadFGL, an adaptive graph imputation generator incorporated with a versatile assessor is first designed to exploit the potential links between subgraphs, without sharing raw data. Next, a new negative sampling mechanism is developed to make SpreadFGL concentrate on more refined information in downstream tasks. To facilitate load balancing at the edge layer, SpreadFGL follows a distributed training manner that enables fast model convergence. Using real-world testbed and benchmark graph datasets, extensive experiments demonstrate the effectiveness of the proposed SpreadFGL. The results show that SpreadFGL achieves higher accuracy and faster convergence against state-of-the-art algorithms. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms

Reconstructing graph Signals from Noisy Dynamical Samples

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Aldroubi, Akram Bailey, Victor Krishtal, Ilya Miller, Brendan Petrosyan, Armenak

We investigate the dynamical sampling space-time trade-off problem within a graph setting. Specifically, we derive necessary and sufficient conditions for space-time sampling that enable the reconstruction of an initial band-limited signal on a graph. Additionally, we develop and test numerical algorithms for approximating the optimal placement of sensors on the graph to minimize the mean squared error when recovering signals from time-space measurements corrupted by i.i.d. additive noise. Our numerical experiments demonstrate that our approach outperforms previously proposed algorithms for related problems. © 2024, CC BY.

关键词： graph algorithms

An Efficient Loop and Clique Coarsening Algorithm for graph Classification

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Qi, Xiaorui Bai, Qijie Wen, Yanlong Zhang, Haiwei Yuan, Xiaojie College of Computer Science Nankai University China

graph Transformers (GTs) have made remarkable achievements in graph-level tasks. However, most existing works regard graph structures as a form of guidance or bias for enhancing node representations, which focuses on node-central perspectives and lacks explicit representations of edges and structures. One natural question arises as to whether we can leverage a hypernode to represent some structures. Through experimental analysis, we explore the feasibility of this assumption. Based on our findings, we propose an efficient Loop and Clique Coarsening algorithm with linear complexity for graph Classification (LCC4GC) on GT architecture. Specifically, we build three unique views, original, coarsening, and conversion, to learn a thorough structural representation. We compress loops and cliques via hierarchical heuristic graph coarsening and restrict them with well-designed constraints, which builds the coarsening view to learn high-level interactions between structures. We also introduce line graphs for edge embeddings and switch to edge-central perspective to alleviate the impact of coarsening reduction. Experiments on eight real-world datasets demonstrate the improvements of LCC4GC over 31 baselines from various architectures. Our code is available: https://***/NickSkyyy/LCC-for-GC. © 2024, CC BY.

关键词： graph algorithms

ON SPECTRAL graph DETERMINATION

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Sason, Igal Krupnik, Noam Hamud, Suleiman Berman, Abraham Technion - Israel Institute of Technology Technion City Haifa3200003 Israel

The study of spectral graph determination is a fascinating area of research in spectral graph theory and algebraic combinatorics. This field focuses on examining the spectral characterization of various classes of graphs, developing methods to construct or distinguish cospectral nonisomorphic graphs, and analyzing the conditions under which a graph’s spectrum uniquely determines its structure. This paper presents an overview of both classical and recent advancements in these topics, along with newly obtained proofs of some existing results, which offer additional insights. Copyright © 2024, The Authors. All rights reserved.

关键词： graph algorithms