Protein-protein interaction networks (PPINs) are indispensable in exploring complex biological systems, facilitating advancements in fields like drug discovery, protein function annotation, and disease mechanism elucidation.So far, predicting the dynamical properties of biochemical pathways has relied on costly numerical simulations.In this paper, we propose exploiting the topological information in PPINs to restate the problem of predicting pathway robustness as a link prediction task.Our experiments show that the PPIN topology can supply information on inter-pathway relationships, significantly improving predictions of the graph-agnostic baseline relying only on protein sequence embeddings.

The increasing popularity of deep learning on graphs has motivated the need for the co-design of hardware and graph representation models.We propose Randomized Ising Model (RIM), a reservoir computing model for encoding topological information of graph nodes, that is amenable to physical implementation via neuromorphic hardware.Our experiments demonstrate that RIM's node embeddings are able to provide sufficient topological information to be suitable to address node classification tasks, exhibiting an accuracy in line with Graph Echo State Networks.

Understanding the inductive bias of Deep Graph Networks (DGNs) is crucial because it reveals how these models generalize from training data to unseen data. Discovering these learning assumptions, and their alignment to the task’s characteristics, allows informed architectural design choices and facilitates interpretation. With this goal, we analyze the different inductive biases of DGNs by relating the node-level explanations produced by explainable AI (XAI) methods to known network science measures of lower-order (local) and higher-order (increasingly global) connectivity. We then apply graph signal processing to refine this analysis at the granularity of the graph frequency spectrum spanned by the explanation signals. Our main finding is that different DGNs focus on different regions of the graph frequency spectrum, and in particular, high-frequency DGNs generalize by focusing on lower-order graph connectivity, while low-frequency DGNs generalize by recognizing higher-order graph structures. This characterization is first derived on synthetic benchmarks by showing that explanations align with network science measures sitting at the two extremes of the spectrum (Katz centrality in the high frequencies, and Fiedler eigenvector scores in the low frequencies). Moving to real-world chemical benchmarks, this result is generalized by showing that inductive biases do indeed lie on a continuum that corresponds to sub-regions of the frequency spectrum.

Network quantification (NQ) is the problem of estimating the proportions of nodes belonging to each class in subsets of unlabelled graph nodes. When prior probability shift is at play, this task cannot be effectively addressed by first classifying the nodes and then counting the class predictions. In addition, unlike non-relational quantification, NQ demands enhanced flexibility in order to capture a broad range of connectivity patterns, resilience to the challenge of heterophily, and scalability to large networks. In order to meet these stringent requirements, we introduce XNQ, a novel method that synergizes the flexibility and efficiency of the unsupervised node embeddings computed by randomized recursive Graph Neural Networks, with an Expectation-Maximization algorithm that provides a robust quantification-aware adjustment to the output probabilities of a calibrated node classifier. In an extensive evaluation, in which we also validate the design choices underpinning XNQ through comprehensive ablation experiments, we find that XNQ consistently and significantly improves on the best network quantification methods to date, thereby setting the new state of the art for this challenging task. XNQ also provides a training speed-up of up to 10x–100x over other methods based on graph learning.

Continual learning aims to address the challenge of catastrophic forgetting in training models where data patterns are non-stationary.Previous research has shown that fully-trained graph learning models are particularly affected by this issue.One approach to lifting part of the burden is to leverage the representations provided by a training-free reservoir computing model.In this work, we evaluate for the first time different continual learning strategies in conjunction with Graph Echo State Networks, which have already demonstrated their efficacy and efficiency in graph classification tasks.Research partly supported by PNRR, PE00000013 -"FAIR -Future Artificial Intelligence Research" -Spoke 1, funded by European Commission under the NextGeneration EU programme.35

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.

The forward-forward algorithm (FFA) is a recently proposed alternative to end-to-end backpropagation in deep neural networks.FFA builds networks greedily layer by layer, thus being of particular interest in applications where memory and computational constraints are important.In order to boost layers' ability to transfer useful information to subsequent layers, in this paper we propose a novel regularization term for the layerwise loss function that is based on Renyi's quadratic entropy.Preliminary experiments show accuracy is generally significantly improved across all network architectures.In particular, smaller architectures become more effective in addressing our classification tasks compared to the original FFA.

Graph Echo State Networks (GESN) have recently proved effective in node classification tasks, showing particularly able to address the issue of heterophily.While previous literature has analyzed the design of reservoirs for sequence ESN and GESN for graph-level tasks, the factors that contribute to rich node embeddings are so far 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 using tools from the areas of information theory and numerical analysis.In particular, we propose an entropy measure for quantifying information in node embeddings.

Node classification tasks on graphs are addressed via fully-trained deep message-passing models that learn a hierarchy of node representations via multiple aggregations of a node’s neighbourhood. While effective on graphs that exhibit a high ratio of intra-class edges, this approach poses challenges in the opposite case, i.e. heterophily, where nodes belonging to the same class are usually further apart. In graphs with a high degree of heterophily, the smoothed representations based on close neighbours computed by convolutional models are no longer effective. So far, architectural variations in message-passing models to reduce excessive smoothing or rewiring the input graph to improve longer-range message passing have been proposed. In this paper, we address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification. GESN is a reservoir computing model for graphs, where node embeddings are recursively computed by an untrained message-passing function. Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models that implement ad hoc variations in the architectural bias or perform rewiring as a preprocessing step on the input graph, with an improvement in terms of efficiency/accuracy trade-off. Furthermore, our analysis shows that GESN is able to effectively encode the structural relationships of a graph node, by showing a correlation between iterations of the recursive embedding function and the distribution of shortest paths in a graph.

Graph Echo State Networks (GESN) have already demonstrated their efficacy and efficiency in graph classification tasks.However, semi-supervised node classification brought out the problem of oversmoothing in end-to-end trained deep models, which causes a bias towards high homophily graphs.We evaluate for the first time GESN on node classification tasks with different degrees of homophily, analyzing also the impact of the reservoir radius.Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to fully trained deep models that implement ad hoc variations in the architectural bias, with a gain in terms of efficiency.

Graph echo state networks (GESN) are a class of reservoir computing models for the efficient and effective processing of graphs. They compute graph embeddings by the convergence to a fixed point of a dynamical system, randomly initialized according to a generalization of the echo state property, called the graph embedding stability (GES) property. In this paper, we prove new and more accurate bounds for necessary and sufficient GES conditions. Experiments demonstrate how these bounds allow an easier parameter selection and better quality reservoirs.

Dynamic temporal graphs represent evolving relations between entities, e.g.interactions between social network users or infection spreading.We propose an extension of graph echo state networks for the efficient processing of dynamic temporal graphs, with a sufficient condition for their echo state property, and an experimental analysis of reservoir layout impact.Compared to temporal graph kernels that need to hold the entire history of vertex interactions, our model provides a vector encoding for the dynamic graph that is updated at each time-step without requiring training.Experiments show accuracy comparable to approximate temporal graph kernels on twelve dissemination process classification tasks.