Abstract
Graph Echo State Networks (GraphESNs) provide an efficient framework for processing structured data, but standard readout mechanisms often rely on global averaging of vertex states, which can obscure localized informative features. This paper introduces GraphESN-wnn, a model that employs a distance-weighted K-Nearest Neighbor (K-NN) readout to adaptively weight vertex contributions based on their relevance in the reservoir state space. Evaluated on the Predictive Toxicology Challenge (PTC) benchmark, the proposed method demonstrates superior performance over standard GraphESN averaging and achieves results competitive with state-of-the-art graph kernels.
Introduction
Processing structured data, such as molecular graphs or social networks, requires models that can capture both local connectivity and global properties. Graph Echo State Networks (GraphESNs) offer a computationally efficient solution by utilizing an untrained, contractive reservoir to generate unique state vectors for every vertex in a graph. However, a significant challenge remains: how to aggregate these individual vertex states into a single, accurate prediction for the entire graph.
The Challenge of Graph-Level Readout
Traditionally, GraphESNs employ a State Mapping Function (SMF) to transition from vertex-level representations to graph-level outputs. The most common SMF is a simple mean, which averages the states of all vertices. This approach assumes that every vertex contributes equally to the final target property. In domains like molecular toxicology, this assumption is often flawed; specific functional groups or sub-structures typically drive a molecule's carcinogenicity or toxicity. The authors address this "blunt instrument" approach by proposing a flexible readout that automatically identifies and weights the most predictive parts of a graph.
Methodology: GraphESN-wnn
The proposed GraphESN-wnn architecture replaces the standard linear readout with a localized, instance-based mechanism. The process follows several key steps:
- State Generation: A standard GraphESN reservoir processes the input graph, producing a state vector $x(v)$ for every vertex $v$.
- Vertex-Level Prediction: For each vertex in a test graph, the model identifies the $K$ most similar vertex states in the training set using a K-Nearest Neighbor search.
- Relevance Weighting: The model calculates a "relevance" weight ($\alpha_r$) for each vertex. Vertices whose neighbors in the state space have consistent target values (low variance) are assigned higher weights, effectively performing automated feature selection.
- Global Aggregation: The final graph output is a weighted sum of individual vertex predictions, prioritizing those deemed most relevant by the K-NN analysis.
To maintain efficiency, the authors utilize kd-trees for the K-NN search and perform the search in a reduced space defined by the first three Principal Components (PCs) of the reservoir states. This dimensionality reduction leverages the "Markovian" property of the reservoir, where nearby states in the manifold correspond to vertices with similar local topologies and labels.
Experimental Evaluation
The model was evaluated using the Predictive Toxicology Challenge (PTC) dataset, a classic benchmark for graph classification. The dataset contains 417 organic molecules, and the task is to predict carcinogenicity across four rodent groups: Male Mice (MM), Female Mice (FM), Male Rats (MR), and Female Rats (FR).
Results and Discussion
Experimental results indicate that the GraphESN-wnn approach consistently improves upon the standard Mean SMF baseline. In specific configurations, the model outperformed the standard GraphESN on three out of four tasks (MM, FM, and FR). For instance, accuracy on the Female Rats (FR) task improved from 64.44% to 67.37%.
As shown in the comparative analysis above, GraphESN-wnn is not only superior to the standard GraphESN but also highly competitive with more computationally expensive state-of-the-art graph kernels. Notably, it achieved results comparable to, or better than, the Marginalized (MG) and Optimal Assignment (OA) kernels on the Female Mice and Male Rat tasks.
Conclusion
By moving from global averaging to a localized, weighted readout, GraphESN-wnn effectively exploits the rich information contained within the reservoir state space. The model's ability to automatically identify relevant sub-structures through distance-weighted variance makes it a powerful and efficient tool for structured data classification. Future work may explore more adaptive modeling of vertex influence, such as learned attention mechanisms, to further refine the extraction of information from the reservoir.
Summary updated