Search

Graph theory analysis, as a mathematical tool, has been widely employed in studying the connectivity of the brain to explore the structural organization. Through the computation of graph theory metrics, it can effectively reveal the nonlinear and complex behavioral features of neuroimaging data, e.g., Electroencephalogram (EEG) and Magnetic Resonance Imaging (MRI), which are often challenging to interpret using simple linear methods. Graph neural networks (GNNs), employing deep learning, offer a more flexible approach to handling large-scale, high-dimensional brain network data. This review aims to investigate the applications of graph theory and Graph Neural Networks in the diagnosis of neurological disorders. The complexity and multi-level features of neurological disorders pose challenges for traditional methods in addressing such issues. The paper begins by introducing the fundamental principles of graph theory and GNNs, elucidates the mechanisms behind diagnosis process using these methods, and then provides a comprehensive overview of their specific applications. Finally, it discusses and summarizes the current challenges in this research field, proposing future directions for development. In conclusion, this review provides a thorough theoretical foundation and methodological insight for exploring the potential applications of graph theory and GNNs in the diagnosis of neurological disorders. ● This review explores GNNs and its variants in diagnosing neurological disorders using EEG and MRI data, analyzing gaps and improvements. ● The study highlights epilepsy research prevalence due to quality data and distinctive EEG patterns, noting GCN's dominant use and impact. ● The review calls for better data quality, GNN interpretability, and efficiency, promoting multi-disease diagnostics for personalized medicine. [ABSTRACT FROM AUTHOR]

Among the Graph Neural Network (GNN) models that address the task of node classification, Graph Echo State Networks (GESN) have proved particularly effective in addressing the challenge of heterophily, i.e. the presence of a significant fraction of inter-class edges in the learning task graph. The effectiveness of GESN is paired with its efficiency, owing to the reservoir computing paradigm. While previous literature has analyzed the design of reservoirs for sequence ESN and GESN for graph-level tasks, the problem of providing effective designs of reservoirs for node-level GESN is so far largely unexplored. In this paper we analyze the impact of different reservoir designs on node classification accuracy and on the quality of node embeddings computed by GESN, focusing both on dense and sparse reservoir layouts. As measures of embedding richness, we adopt both graph topology-dependent metrics previously employed in the analysis of embedding smoothing, and topology-independent metrics from the areas of information theory and numerical analysis. In particular, we propose the application of entropy measures for quantifying information in node embeddings. [Display omitted] • First systematic analysis of reservoir computing designs for node classification. • Proposing a set of topology-aware and -agnostic richness measures for node embeddings. • Random ensembles and dense orthogonal reservoirs perform generally better. • Extremely sparse reservoirs preserve accuracy and node embedding quality. [ABSTRACT FROM AUTHOR]

Deep learning approaches, given their low cost and high reliability, have gained much popularity in different subjects, such as computer vision and natural language processing, and more recently in graph data types. Spatiotemporal graph-based neural networks have been more and more developed to solve problems related to spatiotemporal data, mainly for analyzing changes over time and for provisioning purposes. In this systematic literature review, we have aimed to answer the most important questions regarding spatiotemporal graph deep learning architectures in different applications domains, such as traffic related topics, medical imaging, and geographical data analysis. We have selected more than 50 papers that cover a wide range of applications and very different architectures and innovations. We have also noticed that most of them consider the spatiotemporal graphs to be quite classic graphs without any further sophisticated modeling of temporal and spatial data evolution. Moreover, core problems (such as node classification, frequent pattern recognition, etc.) and application domains are not sufficiently addressed by the state-of-the-art. This study thus opens many perspectives to new developments in spatio-temporal graph deep learning with different strategies in order to solve various end-to-end tasks and other problems related to this special kind of graph. • We have conducted a large systematic literature review about the development of spatiotemporal graph deep learning. • Our selection process reached to more than 50 articles related to various applications and innovations. • We concluded that most research works use quite classic representations of spatiotemporal data. • Moreover, we noticed that graph problems and applications are not addressed in the literature. • Both findings open the way to various perspectives in spatiotemporal graph based deep learning. [ABSTRACT FROM AUTHOR]

Relational Graph Neural Networks (RGNNs) are designed to extract structural information from relational graphs and have garnered attention in the domain of Knowledge Graph Completion (KGC). However, recent empirical investigations have indicated that some prominent RGNN-based methodologies have not significantly enhanced precision, prompting questions regarding the efficacy of RGNNs in KGC applications. In this paper, we introduce a novel RGNN-based KGC approach, the Proximity Relational Graph Neural Network (PRGNN), which excels at modeling high-order proximities among entities. PRGNN is founded on a notably straightforward yet effective RGNN framework that discards unnecessary components commonly incorporated in previous approaches, such as attention layers, and linear and non-linear mappings. We demonstrate that PRGNN empowers traditional KGC techniques to apprehend high-order proximities among entities more effectively. Through extensive experimentation on benchmark datasets, we establish that PRGNN consistently outperforms conventional KGC methods and achieves state-of-the-art results. Furthermore, we show that PRGNN necessitates considerably less training time (ranging from one-third to one-fifth) and fewer parameters (ranging from half to two-thirds), rendering it an exceptionally efficient approach. All data and code have been made available at 1 1 https://github.com/zhudanhao/PRGNN.. [ABSTRACT FROM AUTHOR]

Link prediction is a crucial aspect of graph machine learning, with applications as diverse as disease prediction, social network recommendations, and drug discovery. It involves the prediction of potential new links between nodes within a network. Despite its importance, current models for link prediction exhibit notable limitations. Graph Convolutional Networks have shown high efficiency in link prediction across various datasets. However, they face significant challenges when applied to short-path networks and ego networks, resulting in poor performance. This issue represents a critical area of concern that our work seeks to address. This paper introduces the Node Centrality and Similarity-based Parameterised Model (NCSM), a novel method for link prediction tasks. NCSM uniquely integrates node centrality and similarity measures as edge features in a customised Graph Neural Network (GNN) layer, effectively leveraging the topological information of large networks. This model represents the first parameterised GNN-based link prediction model that considers topological information. The proposed model was evaluated on five benchmark graph datasets, each comprising thousands of nodes and edges. Experimental results highlight NCSM's superiority over existing state-of-the-art models like Graph Convolutional Networks and Variational Graph Autoencoder, as it outperforms them across various metrics and datasets. This exceptional performance can be attributed to NCSM's innovative integration of node centrality, similarity measures, and its efficient use of topological information. • Introduced Node Centrality and Similarity based Parameterised Model (NCSM) for link prediction. • NCSM uses node centrality and similarity as edge features in a custom Graph Neural Network. • Evaluated NCSM on five benchmark datasets, surpassing models like Graph Convolutional Networks and Variational Graph Autoencoder. • NCSM excels by uniquely combining node measures and effectively utilising network topology. [ABSTRACT FROM AUTHOR]

Entity alignment refers to finding equivalent entities from different knowledge graphs. Most of the existing entity alignment methods are studied based on homogeneous graphs. However, the knowledge graph is a heterogeneous graph containing many types of nodes, such as entities, relations, and attributes. Therefore, we propose introducing a heterogeneous graph neural network to model entities and relations simultaneously and propose an iterative fusion method to enhance the interaction between these two semantic nodes. Since not all datasets contain relation information, this paper does not directly introduce a feature representation of relations. The generalizability of the approach is improved by utilizing a relation-aware strategy to obtain information about the relation. Specifically, the information propagation of the head and tail entities in the triplet is utilized to obtain the feature representation of the relation. Experimental results show that the present method performs better on three cross-lingual datasets D B P 15 K and two large-scale datasets D W Y 100 K. [ABSTRACT FROM AUTHOR]

The digitization of healthcare systems has led to the proliferation of electronic health records (EHRs), serving as comprehensive repositories of patient information. However, the vast volume and complexity of EHR data present challenges in extracting meaningful insights. This paper addresses the need for automated analysis of EHRs by proposing a novel graph learning model with label attention (GLLA) for temporal event prediction. GLLA utilizes graph neural networks to capture intricate relationships between medical codes and patients, incorporating hierarchical structures and shared risk factors. Furthermore, it introduces the Label Attention and Attention-based Transformer (LAAT) algorithm to analyze unstructured clinical notes as a multi-label classification problem. Evaluation on the widely-used MIMIC III dataset demonstrates the efficacy of GLLA in enhancing diagnostic prediction performance. The contributions of this research include a comprehensive analysis of existing models, the identification of limitations, and the development of innovative approaches to improve the accuracy and effectiveness of EHR analysis. Ultimately, GLLA aims to advance healthcare decision-making, disease management strategies, and patient outcomes. • Graph Learning with Label Attention (GLLA), leveraging GNNs to predict EHR events. • Introduced the Label Attention and Attention-based Transformer (LAAT) for EHRs. • Conducted a comprehensive evaluation using the MIMIC III dataset. • Integrated hyperbolic embeddings within GLLA to capture the hierarchical structures. • Provide a thorough analysis of existing models. [ABSTRACT FROM AUTHOR]

Graph Neural Networks (GNNs) have exhibited significant success in various applications, but they face challenges when labeled nodes are limited. A novel self-supervised learning paradigm has emerged, enabling GNN training without labeled nodes and even surpassing GNNs with limited labeled data. However, self-supervised methods lack class-discriminative node representations due to the absence of labeled information during training. In this paper, we exploit a supervised graph contrastive learning approach (SGCL) framework to tackle the issue of limited labeled nodes, ensuring coherent grouping of nodes within the same class. We propose augmentation techniques based on a novel centrality function to highlight important topological structures. Additionally, we introduce a supervised contrastive learning method that removes the necessity for negative samples and simplifies complex elements effortlessly. Our approach combines supervised contrastive loss and node similarity regularization while achieving consistent grouping of unlabeled nodes with labeled ones. Furthermore, we utilize the pseudo-labeling technique to propagate label information to distant nodes and address the underfitting problem, especially with low-degree nodes. Experimental results on real-world graphs demonstrate that SGCL outperforms both semi-supervised and self-supervised methods in node classification. [ABSTRACT FROM AUTHOR]

Combinatorial optimization problems (COPs) play an important role in both industrial production and theoretical research. As a classical class of optimization algorithms, evolutionary algorithms have shown good performance in COPs. However, as the size of the problem increases, it becomes difficult for evolutionary algorithms to produce satisfactory solutions within the specified time. In recent years, neural network algorithms have been applied to solve COPs and have shown superior effects. Inspired by this, this paper proposes a new algorithm based on graph structure for solving COPs. Through relaxation, COPs are transformed into their corresponding continuous optimization problems. The output state of our algorithm is converted to a discrete solution by approximation method. Compared with previous algorithms, our algorithm can not only solve COPs with general form such as binary quadratic programming (BQP), but also solve COPs with special form, which greatly expands the application scope of neural network algorithms. In addition, our algorithm can be embedded into other problem frameworks such as solving multi-objective combinatorial optimization problem (MOCOP) through scalarization method. A new penalty function is added to the objective function, which enables our algorithm to overcome the inconsistency between the optimal solution of the original problem and the corresponding continuous problem, so that our algorithm can perform well on various problems. Several numerical simulations are used to illustrate the effectiveness of our algorithm in solving COPs. Experimental results show that our algorithm can effectively solve COPs with general form and has a shorter solving time compared to traditional evolutionary algorithms. [ABSTRACT FROM AUTHOR]

The mainstream Multi-Agent Reinforcement Learning (MARL) methods introduce the teammate modeling or the communication mechanism into Centralized Training Decentralized Execution (CTDE) paradigm, which can improve coordination performance. However, the existing teammate modeling methods predict either actions or local observations, limiting their applicability. In addition, the traditional communication mechanism only considers the quantity of the communication links while ignoring the quality of retained communication links, leading to inefficient and redundant communication. To solve the above problems, this paper proposes a novel Multi-Agent Cooperative Strategy with Explicit Teammate Modeling and Targeted Informative Communication (MACS), which can generate and send the more informative message with the higher communication efficiency, further improving the coordination performance. Specifically, the Variational Auto-Encoder (VAE) is leveraged to allow each agent to simultaneously predict the observations and actions of teammates, thus generating more comprehensive communication message. Then, we propose a new Mutual Information (MI) between the communication message and teammate Q-value, which can obtain the informative message, ensuring the exploration and stability of the method. In addition, a targeted dynamic informative communication graph is established by the Graph Neural Network (GNN) which can reduce the redundant communication link through hypothetical analysis, further improving the overall communication efficiency. Eventually, we conduct experiments in StarCraft II, Collaborative Navigation, and Multi-Target Multi-Sensor Coverage environments. Experimental results show that the proposed approach is superior to the state-of-the-art in terms of coordination performance and communication efficiency. [ABSTRACT FROM AUTHOR]

The advancement of low-cost, non-manually labeled big data technologies for fault detection in wind turbines is crucial to guarantee their safe and efficient operation. In this context, Normal Behavior Modelling (NBM) is a prevalent approach. However, existing NBM methods for wind turbine fault detection inadequately utilize complex spatial–temporal correlations within the Supervisory Control and Data Acquisition (SCADA) during the normal behavior prediction stage. To cope with this limitation, this paper propose a hierarchical spatial-temporal autocorrelation graph neural network method for online wind turbine pitch system fault detection. This approach integrates a dynamic graph network with an adaptive structure for spatial correlation learning and a transformer model with autocorrelation attention to identify periodic time-distance correlations. Furthermore, a hierarchical neural network, specifically designed for wind turbine physical structure, enhances local information extraction through seven latent graph neural networks and a probsparse attention mechanism. The proposed method demonstrates significant effectiveness in real-world applications, as evidenced by data from a Shanghai wind farm. [ABSTRACT FROM AUTHOR]

Coping with the growing demand for data and parameters in complex neural network (NN) models of contemporary times typically involves distributing them across multiple devices, giving rise to the device placement problem. Several widely adopted solutions to this challenge leverage graph embedding schemes. However, the current graph embedding models employed for device placement suffer from several limitations, such as being highly time-consuming in the search for optimal parallelization strategies and yielding suboptimal parallel results. In this paper, we develop a novel graph embedding approach CP-GNNAK for efficient device placement. CP-GNNAK mainly depends on an efficient subgraph-based node embedding strategy, namely GNN as kernel, and a novel cosine phase position embedding scheme. CP-GNNAK goes beyond encoding only the immediate neighbors by deriving the representation of each node from the encoding of a surrounding subgraph. This expanded approach significantly enhances the efficiency of device placement through the integration of subgraph sampling strategies. Additionally, the cosine phase position embedding not only considers the positional information between nodes but also captures the directional information underlying the nodes. This adds richness to the node embeddings and improves the performance of device placement. The experimental results clearly indicate that the CP-GNNAK model achieves the state-of-the-art device placement results. Specifically, the experimental results reveal a remarkable 13.77% improvement in runtime when employing CP-GNNAK compared to Placeto. CP-GNNAK also outperforms GraphSAGE by 7.36% and P-GNN by 0.94%. Turning to computation time, CP-GNNAK exhibits a substantial speedup of 3.40 × over Placeto, 3.87 × over GraphSAGE, and 3.20 × over P-GNN. • A novel graph embedding approach, CP-GNNAK, was developed for optimizing device placement. • Enhanced processing speed and device placement performance through subgraph sampling strategy. • Developing a novel cosine-phase position embedding significantly enhances the expressiveness of node embedding. • Numerous experiments validate the superiority of CP-GNNAK. [ABSTRACT FROM AUTHOR]

Combinatorial optimization problem (COP) is an NP-hard problem for which finding an optimal solution is difficult, especially as the problem size increases. The Traveling Salesman Problem (TSP), one of the COPs that can be formulated over a graph, is a well-researched area in operations research and computer science. Deep Reinforcement Learning (DRL) is now regarded as a promising approach for solving TSP and other NP hard problems. In this paper, we propose a novel Gated Deep Graph Attention Network (G-DGANet) which builds upon the existing Graph Neural Network (GNN) to solve TSP. The proposed G-DGANet uses gating mechanism between subsequent layers of the network to extract representations of nodes deeper in the network without loss in performance. G-DGANet also designs a novel aggregator to construct global graph embeddings from different embedding preferences. In addition, to effectively learn underlying structure of a graph, G-DGANet integrates node and edge information of the graph while updating node representations in the message passing mechanism. We used proximal policy optimization (PPO) to train G-DGANet on randomly generated instances. We conducted an experiment on randomly generated instances and on real-world road network data generated from digital maps to verify the performance of G-DGANet. The findings from experiments demonstrate that G-DGANet outperforms most traditional heuristics and existing DRL approaches, with high generalization abilities from random instance training to random instance testing and real-world road network instance testing. [ABSTRACT FROM AUTHOR]

Relation prediction is a task designed for knowledge graph completion which aims to predict missing relationships between entities. Recent subgraph-based models for inductive relation prediction have received increasing attention, which can predict relation for unseen entities based on the extracted subgraph surrounding the candidate triplet. However, they are not completely inductive because of their disability of predicting unseen relations. Moreover, they only rely on the graph neural network (GNN) to learn the embedding of extracted subgraph relations and independently assign learnable parameters to each relation, which ignores the role of relations and leads to inaccurate prediction on long-tail relations. In this paper, we introduce Re lation-dependent Co ntrastive Le arning (ReCoLe) for inductive relation prediction, which adapts contrastive learning with a novel sampling method based on clustering algorithm to enhance the role of relation and improve the generalization ability to unseen relations. Instead of directly learning embedding for relations, ReCoLe allocates a pre-trained GNN-based encoder for each relation to strengthen the influence of relations. The GNN-based encoder is optimized by contrastive learning, which improves the expressiveness of the embedding of long-tail relations and ensures satisfactory performance. In addition, the cluster sampling method equips ReCoLe with the ability to handle both unseen relations and entities. Experimental results suggest that ReCoLe outperforms state-of-the-art methods on commonly used inductive datasets. [ABSTRACT FROM AUTHOR]