Deep positional encoders for graph classification

• We introduce Deep Positional Encoders (DPE), a novel learnable approach that directly learns eigenvectors of the graph Laplacian through Deep Dirichlet Energies, overcoming the anchoring effect of precomputed spectral methods. • Our method achieves computational efficiency with O(N K + EK) complexity compared to O(N 3) for traditional eigendecomposition, enabling scalable application to large graphs while maintaining theoretical spectral properties. • Comprehensive evaluation across 15 datasets demonstrates consistent improvements over state-ofthe-art positional encodings, with notable gains on molecular graphs (87.80 competitive performance on large-scale benchmarks (OGB, LRGB). • DPE shows versatility across different architectures, enhancing both traditional GNNs (GCN, GIN, GatedGCN) and modern Graph Transformers, with ablation studies confirming the critical importance of balancing task and spectral objectives. • The method bypasses sign ambiguity and stability issues inherent in traditional spectral approaches by learning task-adaptive eigenvectors that react to both classification loss and spectral constraints through end-to-end optimization. Structural Pattern Recognition (SPR) includes the study of graphs as encoders of non-sequential and permutation-invariant patterns. In this regard, Graph Neural Networks (GNNs) are paving the way towards “inductive SPR” where classical structural problems such as graph classification can be approached through learnable priors. However, since graphs do not have a canonical order, existing GNNs struggle to learn the structural role of each node in the graph, which becomes key in graph classification. In this paper, we address this problem by making Spectral Graph Theory “inductive”, i.e. by learning the eigenvectors of the graph Laplacian, and then using them as positional encoders (PEs). Our experiments show that we improve significantly the SOTA of GNN-based graph classification.