Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques aim at the identification of vertex ...subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are: li>What are the communities within an (online) social network? How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer? How must components be organised on a computer chip such that they can communicate efficiently with each other? What are the segments of a digital image? Which functions are certain genes (most likely) responsible for? The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyse various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails. This book is published in cooperation with the Center for Discrete Mathematics and Theoretical Computer Science.
This accessible book provides an introduction to the analysis and design of dynamic multiagent networks. Such networks are of great interest in a wide range of areas in science and engineering, ...including: mobile sensor networks, distributed robotics such as formation flying and swarming, quantum networks, networked economics, biological synchronization, and social networks. Focusing on graph theoretic methods for the analysis and synthesis of dynamic multiagent networks, the book presents a powerful new formalism and set of tools for networked systems.
The book's three sections look at foundations, multiagent networks, and networks as systems. The authors give an overview of important ideas from graph theory, followed by a detailed account of the agreement protocol and its various extensions, including the behavior of the protocol over undirected, directed, switching, and random networks. They cover topics such as formation control, coverage, distributed estimation, social networks, and games over networks. And they explore intriguing aspects of viewing networks as systems, by making these networks amenable to control-theoretic analysis and automatic synthesis, by monitoring their dynamic evolution, and by examining higher-order interaction models in terms of simplicial complexes and their applications.
The book will interest graduate students working in systems and control, as well as in computer science and robotics. It will be a standard reference for researchers seeking a self-contained account of system-theoretic aspects of multiagent networks and their wide-ranging applications.
This book has been adopted as a textbook at the following universities:
University of Stuttgart, GermanyRoyal Institute of Technology, SwedenJohannes Kepler University, AustriaGeorgia Tech, USAUniversity of Washington, USAOhio University, USA
Graph theory is an important area of applied mathematics with a broad spectrum of applications in many fields. This book results from aSpecialIssue in the journal Mathematics entitled ...“Graph-Theoretic Problems and Their New Applications”. It contains 20 articles covering a broad spectrum of graph-theoretic works that were selected from 151 submitted papers after a thorough refereeing process. Among others, it includes a deep survey on mixed graphs and their use for solutions ti scheduling problems. Other subjects include topological indices, domination numbers of graphs, domination games, contraction mappings, and neutrosophic graphs. Several applications of graph theory are discussed, e.g., the use of graph theory in the context of molecular processes.
Given simple graphs F, G, and H. We say F arrows (G, H) if for any red-blue coloring of the edge of F, we find either a red-colored graph G or a blue-colored graph H. The Ramsey number r(G, H) is the ...smallest positive integer r such that a complete graph Kr arrows (G, H). The size Ramsey number is the smallest positive integer rˆ such that a graph F with the size of rˆ arrows (G, H). The restricted size Ramsey number is the smallest positive integer r∗ such that a graph F, of order r(G, H) with the size of r∗, arrows (G, H). In this paper we give the restricted size Ramsey number of a matching of two edges and any disconnected graphs of order six with no isolates.
Anomalies are rare observations (e.g., data records or events) that deviate significantly from the others in the sample. Over the past few decades, research on anomaly mining has received increasing ...interests due to the implications of these occurrences in a wide range of disciplines - for instance, security, finance, and medicine. For this reason, anomaly detection, which aims to identify these rare observations, has become one of the most vital tasks in the world and has shown its power in preventing detrimental events, such as financial fraud, network intrusions, and social spam. The detection task is typically solved by identifying outlying data points in the feature space, which, inherently, overlooks the relational information in real-world data. At the same time, graphs have been prevalently used to represent the structural/relational information, which raises the graph anomaly detection problem - identifying anomalous graph objects (i.e., nodes, edges and sub-graphs) in a single graph, or anomalous graphs in a set/database of graphs. Conventional anomaly detection techniques cannot tackle this problem well because of the complexity of graph data (e.g., irregular structures, relational dependencies, node/edge types/attributes/directions/multiplicities/weights, large scale, etc.). However, thanks to the advent of deep learning in breaking these limitations, graph anomaly detection with deep learning has received a growing attention recently. In this survey, we aim to provide a systematic and comprehensive review of the contemporary deep learning techniques for graph anomaly detection. Specifically, we provide a taxonomy that follows a task-driven strategy and categorizes existing work according to the anomalous graph objects that they can detect. We especially focus on the challenges in this research area and discuss the key intuitions, technical details as well as relative strengths and weaknesses of various techniques in each category. From the survey results, we highlight 12 future research directions spanning unsolved and emerging problems introduced by graph data, anomaly detection, deep learning and real-world applications. Additionally, to provide a wealth of useful resources for future studies, we have compiled a set of open-source implementations, public datasets, and commonly-used evaluation metrics. With this survey, our goal is to create a "one-stop-shop" that provides a unified understanding of the problem categories and existing approaches, publicly available hands-on resources, and high-impact open challenges for graph anomaly detection using deep learning.
Abstract
Graph is a natural data structure for describing complex systems, which contains a set of objects and relationships. Ubiquitous real-life biomedical problems can be modeled as graph ...analytics tasks. Machine learning, especially deep learning, succeeds in vast bioinformatics scenarios with data represented in Euclidean domain. However, rich relational information between biological elements is retained in the non-Euclidean biomedical graphs, which is not learning friendly to classic machine learning methods. Graph representation learning aims to embed graph into a low-dimensional space while preserving graph topology and node properties. It bridges biomedical graphs and modern machine learning methods and has recently raised widespread interest in both machine learning and bioinformatics communities. In this work, we summarize the advances of graph representation learning and its representative applications in bioinformatics. To provide a comprehensive and structured analysis and perspective, we first categorize and analyze both graph embedding methods (homogeneous graph embedding, heterogeneous graph embedding, attribute graph embedding) and graph neural networks. Furthermore, we summarize their representative applications from molecular level to genomics, pharmaceutical and healthcare systems level. Moreover, we provide open resource platforms and libraries for implementing these graph representation learning methods and discuss the challenges and opportunities of graph representation learning in bioinformatics. This work provides a comprehensive survey of emerging graph representation learning algorithms and their applications in bioinformatics. It is anticipated that it could bring valuable insights for researchers to contribute their knowledge to graph representation learning and future-oriented bioinformatics studies.
Graph processing has become an important part of various areas of computing, including machine learning, medical applications, social network analysis, computational sciences, and others. A growing ...amount of the associated graph processing workloads are dynamic , with millions of edges added or removed per second. Graph streaming frameworks are specifically crafted to enable the processing of such highly dynamic workloads. Recent years have seen the development of many such frameworks. However, they differ in their general architectures (with key details such as the support for the concurrent execution of graph updates and queries, or the incorporated graph data organization), the types of updates and workloads allowed, and many others. To facilitate the understanding of this growing field, we provide the first analysis and taxonomy of dynamic and streaming graph processing. We focus on identifying the fundamental system designs and on understanding their support for concurrency, and for different graph updates as well as analytics workloads. We also crystallize the meaning of different concepts associated with streaming graph processing, such as dynamic, temporal, online, and time-evolving graphs, edge-centric processing, models for the maintenance of updates, and graph databases. Moreover, we provide a bridge with the very rich landscape of graph streaming theory by giving a broad overview of recent theoretical related advances, and by discussing which graph streaming models and settings could be helpful in developing more powerful streaming frameworks and designs. We also outline graph streaming workloads and research challenges.
Autoregressive Moving Average Graph Filtering Isufi, Elvin; Loukas, Andreas; Simonetto, Andrea ...
IEEE transactions on signal processing,
2017-Jan.15,-15, 2017-1-15, Volume:
65, Issue:
2
Journal Article
Peer reviewed
One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogs of classical filters, but intended for signals defined on graphs. This paper brings forth new ...insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which are able to approximate any desired graph frequency response, and give exact solutions for specific graph signal denoising and interpolation problems. The philosophy to design the ARMA coefficients independently from the underlying graph renders the ARMA graph filters suitable in static and, particularly, time-varying settings. The latter occur when the graph signal and/or graph topology are changing over time. We show that in case of a time-varying graph signal, our approach extends naturally to a two-dimensional filter, operating concurrently in the graph and regular time domain. We also derive the graph filter behavior, as well as sufficient conditions for filter stability when the graph and signal are time varying. The analytical and numerical results presented in this paper illustrate that ARMA graph filters are practically appealing for static and time-varying settings, as predicted by theoretical derivations.
PDF
