Harnessing spectral representations for subgraph alignment
With the rise and advent of graph learning techniques, graph data has become
ubiquitous. However, while several efforts are being devoted to the design of
new convolutional architectures, pooling or positional encoding schemes, less
effort is being spent on problems involving maps between (possibly very large)
graphs, such as signal transfer, graph isomorphism and subgraph correspondence.
With this paper, we anticipate the need for a convenient framework to deal with
such problems, and focus in particular on the challenging subgraph alignment
scenario. We claim that, first and foremost, the representation of a map plays
a central role on how these problems should be modeled. Taking the hint from
recent work in geometry processing, we propose the adoption of a spectral
representation for maps that is compact, easy to compute, robust to topological
changes, easy to plug into existing pipelines, and is especially effective for
subgraph alignment problems. We report for the first time a surprising
phenomenon where the partiality arising in the subgraph alignment task is
manifested as a special structure of the map coefficients, even in the absence
of exact subgraph isomorphism, and which is consistently observed over
different families of graphs up to several thousand nodes.