• A formal connection is established between Graph Transformers and the Congested clique , a popular model in distributed computing. • The work compares Graph Transformers against Message Passing neural networks in terms of their expressive power and provides new insights into this direction. • The theoretical findings are validated through empirical experiments. It is shown that the node representations learned by Graph Transformers can capture global graph properties even if the number of layers of the model is relatively small. In recent years, Transformers have become the dominant neural architecture in the fields of natural language processing and computer vision. The generalization of Transformers to graphs, so-called Graph Transformers, have recently emerged as a promising alternative to the successful message passing Graph Neural Networks (MPNNs). While the expressive power of MPNNs has been intensively studied in the past years, that of Graph Transformers is still underexplored. Existing results mostly rely on the employed structural/positional encodings and not on the pure architecture itself. However, gaining an understanding of the strengths and limitations of Graph Transformers would be very useful both for the scientific community and the practitioners. In this paper, we derive a connection between Graph Transformers and the Congested clique , a popular model in distributed computing. This connection allows us to translate theoretical results for different graph problems from the latter to the former. We show that under certain conditions, Graph Transformers with depth 2 are Turing universal. We also show that there exist Graph Transformers that can solve problems which cannot be solved by MPNNs. We empirically investigate whether Graph Transformers and MPNNs with depth 2 can solve graph problems on some molecular datasets. Our results demonstrate that Graph Transformers can generally address the underlying tasks, while MPNNs are incapable of learning any information about the graph.

Abstract In this work, we generalize the ideas of Kaiming initialization to Graph Neural Networks (GNNs) and propose a new scheme (G-Init) that reduces oversmoothing, leading to very good results in node and graph classification tasks. GNNs are commonly initialized using methods designed for other types of Neural Networks, overlooking the underlying graph topology. We analyze theoretically the variance of signals flowing forward and gradients flowing backward in the class of convolutional GNNs. We then simplify our analysis to the case of the GCN and propose a new initialization method. Results indicate that the new method (G-Init) reduces oversmoothing in deep GNNs, facilitating their effective use. Our approach achieves an accuracy of 61.60% on the CS dataset (32-layer GCN) and 69.24% on Cora (64-layer GCN), surpassing state-of-the-art initialization methods by 25.6 and 8.6 percentage points, respectively. Extensive experiments confirm the robustness of our method across multiple benchmark datasets, highlighting its effectiveness in diverse settings. Furthermore, our experimental results support the theoretical findings, demonstrating the advantages of deep networks in scenarios with no feature information for unlabeled nodes (i.e., “cold start” scenario).

Abstract The performance of Graph Neural Networks (GNNs) diminishes as their depth increases. That is mainly attributed to oversmoothing, which leads to similar node representations through repeated graph convolutions. To enable deep GNNs, several approaches have been proposed, among which the use of residual connections. Residual connections have proven effective in benchmark datasets, but the way in which they improve the performance of deep GNNs has not been fully studied. We show that residual connections force the model to focus on the local neighborhood of graph nodes, making the GNN equivalent to the sum of shallow GCNs. We explain theoretically why this is the case and verify the theoretical results experimentally. However, our findings raise the question of whether residual connections are helpful in cases where deep networks are necessary. We assess this experimentally, in two situations: (a) in the presence of the “cold start" problem, i.e. when there is no feature information about unlabeled nodes; and (b) in a new synthetic dataset of controllable long-interactions. These experiments highlight the drawbacks of GNNs using residual connections, while showing that simpler methods can be more effective.

Abstract In this work we investigate an observation made by Kipf and Welling (5th International Conference on Learning Representations, 2017), who suggested that untrained Graph Convolutional Networks (GCNs) can generate meaningful node embeddings. In particular, we investigate the effect of training only a single layer of a GCN or a GAT (Graph Attention Network), while keeping the rest of the layers frozen. We propose a basis on which the effect of the untrained layers and their contribution to the generation of embeddings can be predicted. Moreover, we show that network width influences the dissimilarity of node embeddings produced after the initial node features pass through the untrained part of the model. Additionally, we establish a connection between partially trained GCNs and oversmoothing, showing that they are capable of reducing it. We verify our theoretical results experimentally and show the benefits of using deep networks that resist oversmoothing, in a “cold start” scenario, where there is a lack of feature information for unlabeled nodes.

The performance of Graph Neural Networks (GNNs) deteriorates as the depth of the network increases. That performance drop is mainly attributed to oversmoothing, which leads to similar node representations through repeated graph convolutions. We show that in deep GNNs the activation function plays a crucial role in oversmoothing. We explain theoretically why this is the case and propose a simple modification to the slope of ReLU to reduce oversmoothing. The proposed approach enables deep networks without the need to change the network architecture or to add residual connections. We verify the theoretical results experimentally and further show that deep networks, which do not suffer from oversmoothing, are beneficial in the presence of the “cold start” problem, i.e. when there is no feature information about unlabeled nodes.

Contemporary applications require the processing of large, high-velocity streams of symbolic events derived from sensor data. A complex event recognition (CER) system processes these symbolic events online and reports the satisfaction of complex event patterns with minimal latency. We extend an Event Calculus dialect optimised for online CER with Allen’s interval algebra, in order to provide more accurate event patterns. We demonstrate the effectiveness of our system on real data streams from maritime situational awareness.