You better try graph embedding and for that I propose going through Horst Bunke from University of Bern who has been doing it for years. Just search him in google scholar and go through his publication network (co-authors,cited papers, citing papers,etc) for example this and this as more classic papers or this as an exact answer to your question. I am pretty confident you will find your solution as it's exactly his research direction. I am on mobile so referencing is difficult now but I can update my answer later.
The other point that I would like to mention is that graph embedding has two kinds:
- Embedding the vertices (nodes) of one graph into a n-dimensional space i.e. each vector will be a node of the graph. (see this)
- Embedding a dataset of graphs into a n-dimensional space in which each vector will be an entire graph.
You need the second one.
The other thing worth to mention is looking at the problem from Network Science point of view in which the statistical and structural of a graph is widely studied. There are plenty of graph/network measures which are less or more tolerante to the number of nodes e.g. Clustering Coefficient. Using them as features can be fed to a classifier to see how it works.
The last but not the least is what you actually asked! What you are looking for is called Graph Kernel. It is nothing but the definition of the ML-known concept Kernel but on graphs. So kernel methods can get benefit of that by skipping the feature extraction step (like what I suggested above) and directly work with structural inputs. For this purpose I would suggest that you equip yourself with the graph kernels e.g. this paper.