A Structural Smoothing Framework For Robust Graph Comparison
In this paper, we propose a general smoothing framework for graph kernels by taking \textit{structural similarity} into account, and apply it to derive smoothed variants of popular graph kernels. Our framework is inspired by state-of-the-art smoothing techniques used in natural language processing (NLP). However, unlike NLP applications which primarily deal with strings, we show how one can apply smoothing to a richer class of inter-dependent sub-structures that naturally arise in graphs. Moreover, we discuss extensions of the Pitman-Yor process that can be adapted to smooth structured objects thereby leading to novel graph kernels. Our kernels are able to tackle the diagonal dominance problem, while respecting the structural similarity between sub-structures, especially under the presence of edge or label noise. Experimental evaluation shows that not only our kernels outperform the unsmoothed variants, but also achieve statistically significant improvements in classification accuracy over several other graph kernels that have been recently proposed in literature. Our kernels are competitive in terms of runtime, and offer a viable option for practitioners.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Oversmoothing as Loss of Sign: Towards Structural Balance in Graph Neural Networks
Oversmoothing is a common issue in graph neural networks (GNNs), where node representations become excessively homogeneous as the number of layers increases, resulting in degraded performance. Various strategies have bee…
Smoothness Really Matters: A Simple Yet Effective Approach for Unsupervised Graph Domain Adaptation
Unsupervised Graph Domain Adaptation (UGDA) seeks to bridge distribution shifts between domains by transferring knowledge from labeled source graphs to given unlabeled target graphs. Existing UGDA methods primarily focus…
Domain AdaptationGRAPH DOMAIN ADAPTATIONTransfer LearningGraph Alignment via Dual-Pass Spectral Encoding and Latent Space Communication
Graph alignment, the problem of identifying corresponding nodes across multiple graphs, is fundamental to numerous applications. Most existing unsupervised methods embed node features into latent representations to enabl…
AGNN: Alternating Graph-Regularized Neural Networks to Alleviate Over-Smoothing
Graph Convolutional Network (GCN) with the powerful capacity to explore graph-structural data has gained noticeable success in recent years. Nonetheless, most of the existing GCN-based models suffer from the notorious ov…
Graph EmbeddingClass-level Structural Relation Modelling and Smoothing for Visual Representation Learning
Representation learning for images has been advanced by recent progress in more complex neural models such as the Vision Transformers and new learning theories such as the structural causal models. However, these models …
Graph SamplingRelationRepresentation Learning