A Theory of Random Graph Shift in Truncated-Spectrum vRKHS
This work addresses domain adaptation for graph-structured data, which is challenging due to non-Euclidean properties, but it is incremental as it builds on existing theories with a more fine-grained analysis.
The paper tackles the problem of graph classification under domain shift by developing a theory that models intra-class graphs as generated from random graph models, with shifts arising from changes in model components. It derives a generalization bound that factors shift penalty into domain discrepancy, spectral-geometry, and amplitude terms, and empirically verifies these insights on real and simulated data.
This paper develops a theory of graph classification under domain shift through a random-graph generative lens, where we consider intra-class graphs sharing the same random graph model (RGM) and the domain shift induced by changes in RGM components. While classic domain adaptation (DA) theories have well-underpinned existing techniques to handle graph distribution shift, the information of graph samples, which are itself structured objects, is less explored. The non-Euclidean nature of graphs and specialized architectures for graph learning further complicate a fine-grained analysis of graph distribution shifts. In this paper, we propose a theory that assumes RGM as the data generative process, exploiting its connection to hypothesis complexity in function space perspective for such fine-grained analysis. Building on a vector-valued reproducing kernel Hilbert space (vRKHS) formulation, we derive a generalization bound whose shift penalty admits a factorization into (i) a domain discrepancy term, (ii) a spectral-geometry term summarized by the accessible truncated spectrum, and (iii) an amplitude term that aggregates convergence and construction-stability effects. We empirically verify the insights on these terms in both real data and simulations.