Bit Flip Attacks (BFAs) are a well-established class of adversarial attacks, originally developed for Convolutional Neural Networks within the computer vision domain. Most recently, these attacks have been extended to target Graph Neural Networks (GNNs), revealing significant vulnerabilities. This new development naturally raises questions about the best strategies to defend GNNs against BFAs, a challenge for which no solutions currently exist. Given the applications of GNNs in critical fields, any defense mechanism must not only maintain network performance, but also verifiably restore the network to its pre-attack state. Verifiably restoring the network to its pre-attack state also eliminates the need for costly evaluations on test data to ensure network quality. We offer first insights into the effectiveness of existing honeypot- and hashing-based defenses against BFAs adapted from the computer vision domain to GNNs, and characterize the shortcomings of these approaches. To overcome their limitations, we propose Crossfire, a hybrid approach that exploits weight sparsity and combines hashing and honeypots with bit-level correction of out-of-distribution weight elements to restore network integrity. Crossfire is retraining-free and does not require labeled data. Averaged over 2,160 experiments on six benchmark datasets, Crossfire offers a 21.8% higher probability than its competitors of reconstructing a GNN attacked by a BFA to its pre-attack state. These experiments cover up to 55 bit flips from various attacks. Moreover, it improves post repair prediction quality by 10.85%. Computational and storage overheads are negligible compared to the inherent complexity of even the simplest GNNs.

We investigate the vulnerability of Graph Neural Networks (GNNs) to bit-flip attacks (BFAs) by introducing an analytical framework to study the influence of architectural features, graph properties, and their interaction. The expressivity of GNNs refers to their ability to distinguish non-isomorphic graphs and depends on the encoding of node neighborhoods. We examine the vulnerability of neural multiset functions commonly used for this purpose and establish formal criteria to characterize a GNN’s susceptibility to losing expressivity due to BFAs. This enables an analysis of the impact of homophily, graph structural variety, feature encoding, and activation functions on GNN robustness. We derive theoretical bounds for the number of bit flips required to degrade GNN expressivity on a dataset, identifying ReLU-activated GNNs operating on highly homophilous graphs with low-dimensional or one-hot encoded features as particularly susceptible. Empirical results using ten real-world datasets confirm the statistical significance of our key theoretical insights and offer actionable results to mitigate BFA risks in expressivity-critical applications.

Graph Neural Networks (GNNs) have become essential for handling large-scale graph applications. However, the computational demands of GNNs necessitate the development of efficient methods to accelerate inference. Mixed precision quantization emerges as a promising solution to enhance the efficiency of GNN architectures without compromising prediction performance. Compared to conventional deep learning architectures, GNN layers contain a wider set of components that can be quantized, including message passing functions, aggregation functions, update functions, the inputs, learnable parameters, and outputs of these functions. In this paper, we introduce a theorem for efficient quantized message passing to aggregate integer messages. It guarantees numerical equality of the aggregated messages using integer values with respect to those obtained with full (FP32) precision. Based on this theorem, we introduce the Mixed Precision Quantization for GNN (MixQ-GNN) framework, which flexibly selects effective integer bit-widths for all components within GNN layers. Our approach systematically navigates the wide set of possible bit-width combinations, addressing the challenge of optimizing efficiency while aiming at maintaining comparable prediction performance. MixQ-GNN integrates with existing GNN quantization methods, utilizing their graph structure advantages to achieve higher prediction performance. On average, MixQ-GNN achieved reductions in bit operations of 5.5x for node classification and 5.1x for graph classification compared to architectures represented in FP32 precision.

The lottery ticket hypothesis (LTH) is well-studied for convolutional neural networks but has been validated only empirically for graph neural networks (GNNs), for which theoretical findings are largely lacking. In this paper, we identify the expressivity of sparse subnetworks, i.e. their ability to distinguish non-isomorphic graphs, as crucial for finding winning tickets that preserve the predictive performance. We establish conditions under which the expressivity of a sparsely initialized GNN matches that of the full network, particularly when compared to the Weisfeiler-Leman test, and in that context put forward and prove a Strong Expressive Lottery Ticket Hypothesis. We subsequently show that an increased expressivity in the initialization potentially accelerates model convergence and improves generalization. Our findings establish novel theoretical foundations for both LTH and GNN research, highlighting the importance of maintaining expressivity in sparsely initialized GNNs. We illustrate our results using examples from drug discovery.

This paper proposes the Compressed Binary Matrix (CBM) format, a novel, computation-friendly compression scheme for binary matrices. CBM not only reduces the memory footprint of the matrix but also enables faster matrix multiplication between binary and dense, real-valued matrices. The CBM format can be applied to accelerate various graph-related tasks, where the (binary) adjacency matrix of the graph is repeatedly multiplied by another matrix, such as during inference and training of various types of Graph Neural Networks (GNNs). The format is evaluated on a shared-memory architecture in both serial and parallel settings. Experimental results show that CBM can reduce the memory footprint of real-world graphs up to$11 \times$, and that the parallel matrix multiplication using CBM is more than$5 \times$faster than state-of-the-art sparse-dense matrix multiplication kernels. Furthermore, when applied to the inference stage of Graph Convolutional Networks (GCNs), the CBM format achieves speedups close to$2.5 \times$compared to inference using other parallel matrix multiplication kernels.

Iterative solvers for large, sparse linear systems are widely used on HPC machines. When solving very large problems, communication poses a significant bottleneck, which has prompted the development of communication-avoiding iterative$s$-step methods. At the same time, randomization has had a profound impact on numerical linear algebra, leading to orders-of-magnitude performance improvements for many existing algorithms. In this work, we focus on the application of ideas from randomized numerical linear algebra to communication-avoiding$s$-step GMRES methods. We propose a novel randomized$s$step GMRES algorithm called RTBGS-GMRES that improves performance in the construction of the basis for the solution subspace for some matrices, while minimizing the number of global synchronizations in parallel computing environments. We compare our novel algorithm with the state-of-the-art randomized and deterministic$s$-step GMRES methods in terms of numerical stability, convergence, performance, and scalability. Numerical experiments on a large cluster show that with suitable parameter settings the parallel randomized GMRES methods in general outperform the parallel deterministic$s$-step method BCGSI2-GMRES. Our novel RTBGS-GMRES outperforms the other methods and achieves speedups of about$2 \times$and about$4 \times$over BCGSI2-GMRES for two different basis types.

Prior attacks on graph neural networks have focused on graph poisoning and evasion, neglecting the network's weights and biases. For convolutional neural networks, however, the risk arising from bit flip attacks is well recognized. We show that the direct application of a traditional bit flip attack to graph neural networks is of limited effectivity. Hence, we discuss the Injectivity Bit Flip Attack, the first bit flip attack designed specifically for graph neural networks. Our attack targets the learnable neighborhood aggregation functions in quantized message passing neural networks, degrading their ability to distinguish graph structures and impairing the expressivity of the Weisfeiler-Leman test. We find that exploiting mathematical properties specific to certain graph neural networks significantly increases their vulnerability to bit flip attacks. The Injectivity Bit Flip Attack can degrade the maximal expressive Graph Isomorphism Networks trained on graph property prediction datasets to random output by flipping only a small fraction of the network's bits, demonstrating its higher destructive power compared to traditional bit flip attacks transferred from convolutional neural networks. Our attack is transparent, motivated by theoretical insights and confirmed by extensive empirical results.

Quantizing deep neural networks (DNNs) is an important strategy for training or inference in time critical applications. State-of-the-art quantization approaches focus on post-training quantization. While some work on quantization during training exists, most approaches require refinement in full precision (usually single precision) in the final training phase, use a rather coarse quantization, that leads to a loss in accuracy, or enforce a global bit-width across the entire DNN. This leads to suboptimal assignments of bit-widths to layers and, consequently, suboptimal resource usage. To overcome such limitations, we introduce AdaPT, a new fixed- point quantized sparsifying training strategy for deep neural networks. AdaPT decides about precision switches between training epochs based on an information theory motivated heuristic. On a per-layer basis, AdaPT chooses the lowest precision that causes no quantization-induced information loss, while keeping the precision high enough such that future learning steps do not suffer from vanishing gradients. The benefits of this quantization are evaluated based on an analytical performance model. We illustrate an average 1.31 × (or 4.76× adjusted for iso-accuracy) speedup compared to standard training in float32 at iso-accuracy, even achieving an average accuracy increase of 0.74 percentage points for AlexNet/ResNet-20 on CIFAR10/CIFAR100/EMNIST and LeNet-5/MNIST. We demonstrate that these trained models reach an average inference 2.28× speedup with a model size reduction up to 51% of the corresponding unquantized model.

We study a randomized and a deterministic algorithm for the fixed-precision low-rank approximation problem of large sparse matrices. The Randomized QB Factorization (RandQB_EI) constructs a reduced and dense representation of the originally sparse matrix based on randomization. The representation resulting from the deterministic Truncated LU Factorization with Column and Row Tournament Pivoting (LU_CRTP) is sparse, but fill-in introduced in the factorization process can affect sparsity and performance. We therefore attempt to mitigate fill-in with an incomplete LU_CRTP variant with thresholding (ILUT_CRTP). We analyze this approach and identify potential problems that may arise in practice. We design parallel implementations of RandQB_EI, LU_CRTP and ILUT_CRTP. We experimentally evaluate strong scaling properties for different problems and the runtime required for achieving a given approximation quality. Our results show that LU_CRTP tends to be particularly competitive for low approximation quality. However, when a lot of fill-in occurs, LU_CRTP is outperformed by RandQB_EI especially for higher approximation quality. ILUT_CRTP outperforms both LU_CRTP and RandQB_EI and can achieve speedups up to 40 over LU_CRTP, depending on the amount of fill-in.

As computers reach exascale and beyond, the incidence of faults will increase. Solutions to this problem are an active research topic. We focus on strategies to make the preconditioned conjugate gradient (PCG) solver resilient against node failures, specifically, the exact state reconstruction (ESR) method, which exploits redundancies in PCG.

We study algorithmic approaches for recovering from the failure of several compute nodes in the parallel preconditioned conjugate gradient (PCG) solver on large-scale parallel computers. In particular, we analyze and extend an exact state reconstruction (ESR) approach, which is based on a method proposed by Chen (2011). In the ESR approach, the solver keeps redundant information from previous search directions, so that the solver state can be fully reconstructed if a node fails unexpectedly. ESR does not require checkpointing or external storage for saving dynamic solver data and has low overhead compared to the failure-free situation.

Gossip ("epidemic") algorithms can be used for computing aggregation functions of local values across a distributed system without the need to synchronize participating nodes. Although several (theoretical) studies have proven that these algorithms scale well with the number of nodes n, most of these studies are restricted to fully connected networks and based on rather strong assumptions, e.g., it is often assumed that all messages are sent at exactly the same time on different nodes. Applying gossip algorithms on non-fully connected networks significantly increases the number of messages/rounds, especially on weakly connected networks without a regular structure. We present new acceleration strategies for gossip-based averaging algorithms based on ant colony optimization, which specifically target weakly connected networks with irregular structure, where existing gossip averaging algorithms tend to be slow. The proposed acceleration strategies reduce the message and time complexity of standard gossip algorithms without any additional communication cost. The overhead only consists of additional local computation which is proportional to the node degree. All findings are confirmed experimentally for different types of network topologies and for different network sizes.

Most distributed statistical signal processing methods assume conditionally uncorrelated sensor measurements although this assumption is often not satisfied. Here, we propose a distributed algorithm for decorrelating the sensor measurements in a wireless sensor network. The algorithm employs a matrix-valued Chebyshev approximation to achieve an approximate decorrelation using only local computations and communication between neighboring sensors. We apply the algorithm to consensus-based distributed particle filtering in a target tracking problem with correlated measurement noises. Simulations show that the decorrelation yields a substantial accuracy improvement while causing only a small communication overhead.

We compare different algorithms for computing eigenvalues and eigenvectors of a symmetric band matrix across a wide range of synthetic test problems. Of particular interest is a comparison of state-of-the-art tridiagonalization-based methods as implemented in Lapack or Plasma on the one hand, and the block divide-and-conquer (BD&C) algorithm as well as the block twisted factorization (BTF) method on the other hand. The BD&C algorithm does not require tridiagonalization of the original band matrix at all, and the current version of the BTF method tridiagonalizes the original band matrix only for computing the eigenvalues. Avoiding the tridiagonalization process sidesteps the cost of backtransformation of the eigenvectors. Beyond that, we discovered another disadvantage of the backtransformation process for band matrices: In several scenarios, a lot of gradual underflow is observed in the (optional) accumulation of the transformation matrix and in the (obligatory) backtransformation step. According to the IEEE 754 standard for floating-point arithmetic, this implies many operations with subnormal (denormalized) numbers, which causes severe slowdowns compared to the other algorithms without backtransformation of the eigenvectors. We illustrate that in these cases the performance of existing methods from Lapack and Plasma reaches a competitive level only if subnormal numbers are disabled (and thus the IEEE standard is violated). Overall, our performance studies illustrate that if the problem size is large enough relative to the bandwidth, BD&C tends to achieve the highest performance of all methods if the spectrum to be computed is clustered. For test problems with well separated eigenvalues, the BTF method tends to become the fastest algorithm with growing problem size.

Over the last years, several gossip-based aggregation algorithms have been developed which focus on providing resilience in failure-prone distributed systems. The main objective of such algorithms is the efficient in-network computation of aggregates even in the case when system failures occur during runtime. In this paper, we evaluate performance and limitations in practical computations of those gossip-based aggregation algorithms with the most promising theoretical fault tolerance properties. Theoretical analyses of these algorithms usually address only the principal ability of handling or overcoming a certain kind of system failure. Most of the time, there are no formal results on the concrete impact of failure handling on the performance of the algorithms, e. g., in terms of convergence speed. This leaves a wide gap between theory and practice, as we illustrate in this paper. In order to bridge this gap, we first categorize common system failures of interest. Then, we experimentally investigate how well these common failure types are handled in practice by the considered algorithms and up to which extent these state-of-the-art methods provide a reasonable degree of fault tolerance in practice. Our experimental studies reveal (i) that certain failure handling approaches which work in theory exhibit unacceptable performance in practice and (ii) that in some cases the failure handling mechanisms used introduce new problems, e.g., numerical inaccuracy. Our investigations illustrate that for some failure types (such as permanent node failures) further algorithmic advances are required to achieve resilience with a reasonably small overhead and acceptable performance.

The representation of Internet traffic as connection graphs augments anomaly detection systems by providing insight on the structural connection properties, i.e., who-talks-to-whom. However, these graphs are extremely large and one has to decide in advance on which aspect to focus. In the context of malware detection, this is difficult as malware often mimics legitimate traffic. In this paper, we present a statistical approach for extracting the typical traffic destinations for a set of monitored hosts, and derive a reduced graph that contains only connections that are anomalous for that host. This graph can then be analyzed efficiently. Our system is designed to scale to thousands of monitored hosts. We evaluate our approach using a data set from a real network, and show that we can reliably detect injected malware activity.

More and more Internet services are hosted by Content Distribution Networks or Cloud operators. Often, IP addresses are reused for several services, and the mapping between domain names and IPs has become highly agile. This complicates the analysis of monitoring data, as it is not clear anymore which IP address represents which service at which time. We propose a system that continuously monitors this activity using captured DNS packets in a large network. Thereby we are able to (i) understand the allocation strategies inside a hosting provider, and (ii) report significant changes that are not due the normal agility of a particular service. We evaluate our system using a 2-weeks data set from a large network operator, and demonstrate how it can be used to find malicious sites.

We introduce a new distributed eigensolver (dOI) for square matrices based on orthogonal iteration. In contrast to standard parallel eigensolvers, our approach performs only nearest neighbor communication and provides much more flexibility with respect to the properties of the hardware infrastructure on which the computation is performed. This is achieved by utilizing distributed summation methods with randomized communication schedules which do not require global synchronization across the nodes. Our algorithm is particularly attractive for loosely coupled distributed networks with arbitrary network topologies and potentially unreliable components. Our distributed eigensolver dOI is based on a novel distributed matrix-matrix multiplication algorithm and on an extension of a distributed QR factorization algorithm proposed earlier. We illustrate the advantages of dOI in terms of higher flexibility with respect to the underlying network and lower communication cost compared to a related distributed eigensolver by Kempe and McSherry. Moreover, we experimentally illustrate how the overall communication cost of dOI is further reduced by adapting the accuracy of each distributed summation during the orthogonal iteration process.

Over the last decade a large number of routing protocols has been designed for achieving energy efficiency in data collecting wireless sensor networks. The drawbacks of using a static sink are well known. It has been argued in the literature that a mobile sink may improve the energy dissipation compared to a static one. Some authors focus on minimizing Emax, the maximum energy dissipation of any single node in the network, while others aim at minimizing Ebar, the average energy dissipation over all nodes. In our paper we take a more holistic view, considering both Emax and Ebar. The main contribution of this paper is to provide a simulation-based analysis of the energy efficiency of WSNs with static and mobile sinks. The focus is on two important configuration parameters: mobility path of the sink and duty cycling value of the nodes. On the one hand, it is well known that in the case of a mobile sink with fixed trajectory the choice of the mobility path influences energy efficiency. On the other hand, in some types of applications sensor nodes spend a rather large fraction of their total lifetime in idle mode, and therefore higher energy efficiency can be achieved by using the concept of reduced duty cycles. In particular, we quantitatively analyze the influence of duty cycling and the mobility radius of the sink as well as their interrelationship in terms of energy consumption for a well-defined model scenario. The analysis starts from general load considerations and is refined into a geometrical model. This model is validated by simulations which are more realistic in terms of duty cycling than previous work. It is illustrated that over all possible configuration scenarios in terms of duty cycle and mobility radius of the sink the energy dissipation in the WSN can vary up to a factor of nine in terms of Emax and up to a factor of 17 in terms of Ebar. It turns out that in general the choice of the duty cycle value is more important for achieving energy efficiency than the choice of the mobility radius of the sink. Moreover, for small values of the duty cycle, a static sink turns out to be optimal in terms of both Emax and Ebar. For larger values of the duty cycle, a mobile sink has advantages over a static sink, especially in terms of Emax. These insights into the basic interrelationship between duty cycle value and mobility radius of a mobile sink are relevant for energy efficient operation of homogeneous WSNs beyond our model scenario.

Solving Eigen's quasispecies model for the evolution of virus populations involves the computation of the dominant eigenvector of a matrix whose size N grows exponentially with the chain length of the virus to be modeled. Most biologically interesting chain lengths are so far well beyond the reach of existing algorithms and hardware.

We present the idea and implementation details of a highly effective and reliable e-mail filtering technique. At the core of the component-based architecture is a novel combination of an enhanced self-learning variant of greylisting with a reputation-based trust mechanism. These strategies provide separate feature extraction and classification components with the opportunity of utilizing the time between two delivery attempts of an e-mail message. The approach presented features a very high spam blocking rate and also minimizes the workload on the client side, as no responsibility for messages classified as spam is taken. The reputation-based trust mechanism decreases the delay in the transfer process of e-mail messages from reliable senders and also reduces the number of erroneously blocked legitimate messages.

An empirical study of unsolicited commercial/bulk e-mail traffic collected from various spam traps (honeypots) is summarized and discussed. Some of these spam traps were created specifically for this study and thus could be monitored since their initialization. This allows for a thorough analysis of the development of current spam traffic on the Internet, quantitatively as well as qualitatively.

A three-component architecture for the classification and filtering of unsolicited bulk and commercial e-mail ("spam") is introduced. The first component, an enhanced self-learning variant of greylisting, sets the stage for the following feature extraction and classification components. Through the temporary rejection of selected messages by the greylisting component time becomes available for an "offline" in-depth examination of the e-mail content before the message is accepted and delivered to the final recipient. Within the feature extraction component a set of features for each newly arriving e-mail message is determined. These features are then used for the categorization of a message within the classification engine, which contains the adaptation of a vector space model. Based on this model, an implementation of latent semantic indexing for spam filtering is investigated. The architecture proposed contributes to the goal of minimizing the waste of resources caused by spam and is able to react to high load situations (including DoS attacks) via adaptations in the feature extraction and classification components

A novel management layer architecture for mobile grid environments and ad-hoc networks is presented. We address a key challenge in dynamic mobile environments with a high degree of fluctuation in the hardware infrastructure: how to store information persistently and at the same time efficiently. Most currently available approaches are based on replication strategies. These strategies achieve persistency even in highly dynamic environments, but have to pay a high price in terms of redundancy. Our proposed architecture is based on the adaptation of fault-tolerant data distribution strategies utilizing erasure codes, such as RAID or Reed-Solomon, and thus combines persistency with high storage efficiency.

Congestion in wireless sensor networks leads to the degradation of communication links that result in decreased throughput and waste of energy which is one of the scarcest resources of a sensor node. Various techniques have been proposed to cope with data congestion, such as data aggregation techniques, multi hop routing techniques and flow control techniques. Although these techniques help to avoid or control congestion, they do not address the issue of data persistency effectively. This paper presents an adaptive self configuring in-network storage model for data persistency in wireless sensor networks. The model is built on a clustered sensor field where we have utilized dense node deployment in the vicinity of the routing nodes to act as data buffers during congestion periods in order to avoid data loss. We show that the in-network storage model can be used in combination with congestion avoidance/control techniques to develop data persistent congestion avoidance/control strategies

A block tridiagonalization algorithm is proposed for transforming a sparse (or "effectively" sparse) symmetric matrix into a related block tridiagonal matrix, such that the eigenvalue error remains bounded by some prescribed accuracy tolerance. It is based on a heuristic for imposing a block tridiagonal structure on matrices with a large percentage of zero or "effectively zero" (with respect to the given accuracy tolerance) elements. In the light of a recently developed block tridiagonal divide-and-conquer eigensolver [Gansterer, Ward, Muller, and Goddard, III, SIAM J. Sci. Comput. 25 (2003), pp. 65--85], for which block tridiagonalization may be needed as a preprocessing step, the algorithm also provides an option for attempting to produce at least a few very small diagonal blocks in the block tridiagonal matrix. This leads to low time complexity of the last merging operation in the block divide-and-conquer method. Numerical experiments are presented and various block tridiagonalization strategies are compared.

A divide-and-conquer method for computing eigenvalues and eigenvectors of a block-tridiagonal matrix with rank-one off-diagonal blocks is presented. The implications of unbalanced merging operations due to unequal block sizes are analyzed and illustrated with numerical examples. It is shown that an unfavorable order for merging blocks in the synthesis phase of the algorithm may lead to a significant increase of the arithmetic complexity. A strategy to determine a good merging order that is at least close to optimal in all cases is given. The method has been implemented and applied to test problems from a quantum chemistry application.