Hyperbolic geometry has recently emerged as a powerful alternative to Euclidean spaces for representing graph-structured data, particularly due to its ability to capture hierarchical and scale-free structures with low distortion. This paper presents a comprehensive survey of hyperbolic graph embedding methods, providing both a conceptual overview and a systematic taxonomy of existing approaches. Beyond a purely descriptive survey, our work is specifically designed to address key limitations of existing surveys by incorporating a unified and reproducible experimental perspective. Unlike prior surveys, which mainly focus on theoretical foundations, our work places a particular emphasis on anomaly detection in graphs as a unifying and practically relevant evaluation task. To this end, we combine theoretical analysis with a unified evaluation protocol and a practical and reproducible evaluation framework, including a publicly available open-source library that provides a common platform implementing the most representative hyperbolic embedding methods. Using this framework, we conduct extensive experiments on diverse real-world datasets to systematically assess the effectiveness of hyperbolic representations for anomaly detection and to compare them against Euclidean baselines.

Intrusion Detection Systems (IDS) play a crucial role in safeguarding systems and networks from different types of attacks. However, IDSes face significant hurdles in detecting Advanced Persistent Threats (APTs), which are sophisticated cyber-attacks characterised by their stealth, duration, and advanced techniques. Recent research has explored the effectiveness of Graph Neural Networks (GNNs) in APT detection, leveraging their ability to analyse intricate-relationships within graph data. However, existing approaches often rely on local models, limiting their adaptability to evolving APT-tactics and raising privacy-concerns. In response to these challenges, this paper proposes integrating Federated-Learning (FL) into the architectures of GNN-based Intrusion Detection Systems. Moreover, our solution includes an enhanced encryption-system of the clients’ weights to safely send them to the server through the system’s network. This solution prevents man-in-the-middle (MitM) attacks from intercepting the weights and reconstructing clients data using reverse engineering. We evaluate our approach on several datasets, demonstrating promising results in reducing false-positive rates compared to state-of-the-art Provenance-based IDSes (PIDS).

Graph-based anomaly detection has emerged as a powerful tool in cybersecurity for identifying malicious activities within computer systems and networks. While existing approaches often rely on embedding graphs in Euclidean space, recent studies have suggested that hyperbolic space provides a more suitable geometry for capturing the inherent hierarchical and complex relationships present in graph data. In this paper, we explore the efficacy of hyperbolic graph embedding for anomaly detection in the context of cybersecurity. We conduct a comparison of six state-of-the-art hyperbolic graph embedding methods, evaluating their performance on a well-known intrusion detection dataset. Our analysis reveals the strengths and limitations of each method, demonstrating the potential of hyperbolic graph embedding for enhancing security.

We consider the problem of data augmentation for graph neural networks. While other areas of deep learning, especially computer vision, has benefited greatly from data augmentation, graph deep learning is limited by the complex structure and nodes dependency of graph datasets. The works studying data augmentation for graphs focus on ways to train the model on generated graphs or disturb the original one by masking attributes or dropping nodes/edges. Our work studies data augmentation for graphs in the latent space. We propose an architecture to train a graph neural network including a data augmentation component which also has a denoising and structure enhancer function. Our architecture leverages the supervised feedback to introduce the graph neural network component to a new latent representation of the graph with lesser irrelevant connections on the graph domain. We perform experiments on datasets from several domains with different sizes and show that our architecture improves the performance over a variety of plain graph neural networks on node classification.

We introduce a new graph sparsification method that targets the neighborhood information available for each node. Our approach is motivated by the fact that neighborhood information is used by several mining and learning tasks on graphs as well as reachability queries. The result of our sparsification technique is a sparsified graph that can be used instead of the original graph in the above tasks while still ensuring fairly good approximations for the results. Moreover, our sparsification method allows users to control the size of the resulting sparsified graph by adjusting the amount of information loss tolerated by the targeted applications. Our extensive experiments conducted on various real and synthetic graphs show that our sparsification considerably reduces the size of the graphs by achieving 40% sparsification rate on average on several input graphs. Furthermore, in the experimental study we show the utility and efficiency of our sparsification algorithm for notable data-driven tasks, such as node classification, graph classification and shortest path approximations.

We introduce the γ -clustering problems, which are variants of the well-known Cluster Editing/Deletion/Completion problems, and defined as: given a graph G , how many edges must be edited in G , deleted from G , or added to G in order to have a disjoint union of γ -quasi-cliques. We provide here the complete complexity classification of these problems along with FPT algorithms parameterized by the number of modifications, for the NP -complete problems. We also study here a variant of these problems where the number of final clusters is a fixed constant, obtaining mostly the same results regarding classical and parameterized complexity.

IoT networks are the favorite target of cybercriminals. With more and more connected IoT devices, IoT networks offer large attack surface. There are many potential entry points for cybercriminals in these networks. Hence, attack detection is an essential part of securing IoT networks and protecting them against the potential harm or damage that can result from successful attacks. In this paper, we propose a graph-based framework for detecting attacks in IoT networks. Our approach involves constructing an activity graph to represent the networking events occurring during a monitoring window. This graph is a rich attributed graph capturing both structure and semantic features from the network traffic. Then, we train a neural network on this graph to distinguish between normal activities and attacks. Our preliminary experiments show that our approach is able to accurately detect a large range of attacks when the size of the monitoring window is correctly set.

IoT networks are the favorite target of cybercriminals. With more and more connected IoT devices, IoT networks offer large attack surface. There are many potential entry points for cybercriminals in these networks. Hence, attack detection is an essential part of securing IoT networks and protecting against the potential harm or damage that can result from successful attacks. In this paper, we propose a graph-based framework for detecting attacks in IoT networks. Our approach involves constructing an activity graph to represent the networking events occurring during a monitoring window. This graph is a rich attributed graph capturing both structure and semantic features from the network traffic. Then, we train a neural network on this graph to distinguish between normal activities and attacks. Our preliminary experiments show that our approach is able to accurately detect a large range of attacks when the size of the monitoring window is correctly set.

Learning low dimensional representations requires an expressive technique capable of capturing the different features for nodes, the relationship between nodes in the network and thus their similarities. However, many existing embedding techniques focus only on capturing the structural patterns in the network by randomly sampling the nodes in the neighborhood of the target node. To deal with this issue, we propose DSNCR, a node representation framework which uses the non-linear node attributes as well as their neighbourhood structural information to capture nodes similarities. This approach computes a semi-supervised regression analysis on the node attributes to guide a flexible probability walk procedure, such that different neighbourhoods are explored to capture rich network attributes and structures in a learned embedding. We verify the effectiveness of our model on link prediction and node classification tasks using real-life benchmark datasets, for which our technique performs better than existing embedding methods.

We consider the problem of comparing deformable 3D objects represented by graphs, i.e., Triangular tessellations. We propose a new algorithm to measure the distance between triangular tessellations using a new decomposition of triangular tessellations into triangle-Stars. The proposed algorithm assures a minimum number of disjoint triangle-Stars, offers a better measure by covering a larger neighborhood and uses a set of descriptors which are invariant or at least oblivious under most common deformations. We prove that the proposed distance is a pseudo-metric. We analyse its time complexity and we present a set of experimental results which confirm the high performance and accuracy of our algorithm.

Data aggregation is a promising method for conserving energy in Wireless Sensor Networks (WSNs). The most efficient approach to aggregation is organizing the network into clusters. However, this approach which achieves good performance in periodic data collecting applications is proved to be inappropriate for event-driven applications, such as real-time data gathering. In fact, in this case maintaining clusters turned to be very expensive in term of message overhead. To deal with this problem, we propose a clustering scheme suitable for event-driven applications. We show that if the structure is adapted to the occurrence of events, structured approaches can provide good results in real-time WSNs. Simulation results show that our approach performs well both in aggregation gain and energy consumption.

Abstract Motivated by the problem of link scheduling in wireless sensor networks where different sensors have different transmission and interference ranges and may be mobile, we study the problem of “distance edge coloring” of graphs, which is a generalization of proper edge coloring. Let Gbe a graph modeling a sensor network. An ℓ‐distance edge coloring of Gis a coloring of the edges of Gsuch that any two edges within distance ℓof each other are assigned different colors. The parameter ℓis chosen, so that the links corresponding to two edges that are assigned the same color do not interfere. We investigate the ℓ‐distance edge coloring problem on several families of graphs that can be used as topologies in sensor deployment. We focus on determining the minimum number of colors needed and optimal coloring algorithms. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013

With the development of e-commerce over Internet, web service discovery received much interest. A critical aspect of web service discovery is web service similarity search or matchmaking. To enhance the similarity precision, several solutions that do not limit to a syntactic comparison of inputs and outputs of the compared services have been proposed. Most of them introduce the structure of web service operations in the similarity measure. In this paper, we analyze these approaches and point out their time complexity drawback. Then, we propose a more efficient matching algorithm based on the concept of decomposition kernels of graphs. We study the complexity of our approach and present performance analysis.

The challenges in designing secure and scalable group key management solutions are dynamic updates of keys caused by member addition and member deletion. Most proposed solutions in the literature do not take this parameter into consideration and so suffer from the 1-affects-n scalability problem. In this paper, we present a group key management protocol that achieves a maximum of Log3n message exchange to rekey the group after a leave operation.

This paper considers the problem of fault-tolerance and built-in robustness in key agreement for dynamic peer groups. A fault-tolerant key establishment protocol is developed by extending the group Diffie-Hellman key agreement protocol to support asynchronous settings and faulty participants. The protocol uses recent results on failure detection in asynchronous distributed systems. Simulation results show that the key agreement protocol augmented with failure detection increases significantly the number of group members that participate in the computation of the group key while introducing a low message overhead.

Smooth handoff was introduced in mobile IP to overcome this problem of packet loss during handoff. However, smooth handoff causes packets sequence disruption during packet forwarding procedure, which may result in degradation of network performance in higher layer protocol. In this paper, we discuss the impact of receiving out-of-sequence packets by the mobile node on TCP and UDP applications and we propose a technique, which minimizes the arrival of out-of-sequence packets to the mobile node. This technique anticipates forwarding of packets from the current foreign agent to the new one while the mobile node initiates its handoff. To evaluate our solution, we use the unstable time period (UTP) when the packet sequence could be mis-ordered. We show that the unstable period in our solution is very low than the unstable time period in classical smooth handoff. Furthermore, we also show that our solution reduces the considerably out-of-sequence packets generated by smooth handoff.

It is now well recognised that the consensus problem is a fundamental problem when one has to implement fault-tolerant distributed services. We extend the consensus paradigm to asynchronous distributed mobile systems prone to disconnection and process crash failures. The paper, first, shows that a consensus problem between mobile hosts is reducible to two agreement problems (a consensus problem and a group membership problem) between fixed hosts. Then, following an approach investigated by Guerraoui and Schiper (see IEEE Transactions on Software Engineering, vol.27, no.1, p.29-41, 2001), the paper uses a genetic consensus service as a basic building block to construct a modular and simple solution.