Graph Classification Gaussian Processes via Hodgelet Spectral Features

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-05 23:57:08

Abstract: The problem of classifying graphs is ubiquitous in machine learning. While it is standard to apply graph neural networks for such tasks,
Gaussian processes can also be used for graph classification, by transforming the graph signals into the spectral domain, and using the spectral features as inputs. However, this approach only takes into account signals on the vertices of the graph, whereas some data also support signals on the edges. In this work, we present a Gaussian process-based classification algorithm that can utilise both vertex and/or edges features to help classify graphs. Furthermore, we take advantage of the Hodge decomposition of vertex and edge signals to increase the flexibility to the model, which can be beneficial on some tasks.

Main paper: 
 gaussian processes for graph classification: 
 Let us assume a dataset containing M graphs G (1) , . . . , G (M ) and labels y (i) ∈ Z for i = 1, . . . , M .G (i) = (V (i) , E (i) ) has N (i) v vertices and N (i)e edges, and incidence matrixB (i) ve ∈ Z N (i) v ×N (i)e . The latter encodes the adjacency of each vertex with edges in G (i) , and furthermore defines the graph LaplacianL (i) v := B (i) ve B (i)⊤ ve ∈ Z N (i) v ×N (i)v . Likewise, we can define the graph Helmholtzian,L (i) e := B (i)⊤ ve B (i) ve ∈ Z N (i) e ×N (i)e , which is an analogous notion of the graph Laplacian, except applied to edge signals. By vertex or edge signals, we refer to functions V (i) → R Dv andE (i) → R De , respectively for some D v , D e ∈ N.By introducing an ordering of the vertices / edges, we can represent these trivially as vectors in RN (i) v × • • • × R N (i) v (D v times) and R N (i) e × • • • × R N (i) e(D e times). These may be understood as vertex / edge features of the graph data with D v / D e channels. We denote the vertex signals ofG (i) by x (i) vd ∈ R N (i) v , 1 ≤ d ≤ D vand the edge signals byx (i) ed ∈ R N (i) e , 1 ≤ d ≤ D e .Note that a graph dataset may have vertex signals, edge signals, or both.The key idea behind our graph classification algorithm is to convert the vertex and edge signals into signals in the Euclidean domain so that we can apply standard GP classification using these transformed features. To this end, we first consider the eigendecomposition of the graph Laplacian and HelholtzianEQUATIONand define the graph Fourier transform as the projection of vertex / edge signals onto the eigenbasesEQUATIONThe resulting spectral signalsx(i) vd ∈ R N (i) v , x(i) ed ∈ R N (i) eare invariant to vertex/edge ordering, making them sound choices for input signals to the GP. Note that each entry of the spectral signal captures global properties of the original signal. However, in many cases, it may actually be beneficial to use information that is spatially localized (i.e., focusing only on local neighbourhoods). One way to achieve this is to make use of graph wavelet transforms in [9] . Consider for λ ∈ R, a mixture of wavelet functionsEQUATIONEQUATIONwhere a : R → R and c : R → R are so-called low-pass filters, b : R → R and d : R → R be band-pass filters, and θ vj , θ ek are trainable parameters controlling the different scales of localisation to be used. The wavelet transforms of the vertex and edge signals are given byEQUATIONHodge decomposition [24] states that an arbitrary vertex / edge signal can be decomposed into the sum of three orthogonal parts: exact, co-exact and harmonic. This is a far reaching generalisation of the Helmholtz decomposition, which decomposes an arbitrary 2D vector field into gradient-free, curl-free and harmonic components. Thus, we may split the eigenbasis as follows:EQUATIONIt is known thatEQUATIONvc corresponds to the nonzero eigenvalues of L Here, we describe how we generate features from the wavelet transforms for the GP to then use downstream in classification. For each vertex and edge signal, we first take the wavelet transform (5) with respect to the sub-bases (6), yielding three transformed representations corresponding to the exact (grad-free), co-exact (curl-free) and harmonic components. For each component, we then concatenate the 2-norms of the corresponding vertex representation x(i) vdj for each 1 ≤ j ≤ W v andEQUATIONh ∈ R WvDv . We apply a similar process to get the edge spectral features e(i)g , ec , eh ∈ R WeDe . Finally, these are used as inputs to a GP with the following additive kernelEQUATIONh ) +k eg (e (i) g , e (j)EQUATIONh ),where each k •• is for example, the squared-exponential or Matérn kernels. The GP is then used for classification, where we use variational inference to approximate the posterior given labels y (i) . 
experiments: 
 The aim of the experiments is two-fold: (1) we validate the added flexibility given by the Hodge decomposition;(2) we demonstrate that when edge signals are present, it is beneficial to work with edges directly than converting it to a line graph. The latter point has been observed in previous works such as Schaub et al. [21] , Yang et al. [15] and our experiments further validate their observations.In our first experiment, we compare our method to Opolka et al. [6] on some standard graph classification benchmark datasets that only contain vertex features. Specifically, we compare their algorithm, which we refer to the wavelet-transform GP (WT-GP), which does not use the Hodge decomposition, to our method, WT-GP-Hodge, which uses the decomposition. In Table 1 , we display the results on some real and synthetic datasets used in Opolka et al. [6] . We observe that on all but one dataset (IMDB-BINARY), WT-GP-Hodge improves the classification accuracy. This is surprising given that for vertex signals, Hodge decomposition only yields the co-exact and harmonic parts (since the exact part vanishes) and moreover, the harmonic parts are just constant signals on connected components of the graph. This implies that we can gain accuracy by splitting up a signal into a constant bias (the harmonic part) and fluctuations around it (the co-exact part), and treating them separately with different kernels. However, when the constant biases do not aid the classification, (e.g. when each class has vertex features of roughly equal magnitudes), then we do not expect WT-GP-Hodge to improve over WT-GP.In this experiment, we consider the task of classifying noisy vector fields; predicting whether they are mostly divergence-free or curl-free. We proceed by generating 100 random vector fields, with half being divergence-free and the other half curl-free (see Appendix C). The generated vector fields are then projected onto the edges of a randomly generated simplicial mesh on a square domain with N vertices (see Appendix C). Finally, we corrupt the signals with i.i.d. Gaussian noise to prevent the fields from being exactly divergence-free or curl-free. The resulting dataset consists of 100 oriented graphs, each containing edge features corresponding to the net flow of the vector field along the edge. Again, we compare our method against the vanilla WT-GP classification method. However, since the WT-GP does not take edge features, when using this, we first convert the graph to a line graph before applying it. We thus refer to it as WT-GP-LG. In Table (2), we display the results of WT-GP-LG and WT-GP-Hodge on this task for various choices of N . We see that WT-GP-Hodge is consistently better, with large improvements as mesh size is increased. On the other hand, WT-GP-LG cannot distinguish accurately between divergence-free and curl-free fields even as the resolution becomes higher. Likely reasons for this are (1) the Hodge decomposition in WT-GP-Hodge can help to more clearly distinguish between divergence-free and curl-free signals;(2) there are properties that are canonical to edges, such as orientation, which WT-GP-Hodge can handle naturally, whereas WT-GP-LG cannot. In Figure 1 , we also plot the classification accuracy with varying noise level, which further shows robustness of WT-GP-Hodge to noise compared to WT-GP-LG. 
conclusion and future directions: 
 We presented a GP-based classification method that can classify graphs based on vertex and/or edge signals. The vertex and edge signals were processed by considering its projection onto the eigenbasis of the graph Laplacian and Helmholtzian, respectively. The resulting spectral representation was then used to construct wavelet spectral features which were used as inputs to a standard GP classification algorithm. Further, by considering the Hodge decomposition, we have shown that it can provide improvements over Opolka et al. [6] , even on data with only vertex features, owing to the added flexibility of the model. Overall, we have demonstrated the efficacy of our approach for graph classification tasks where edge features or topological information are essential. In the future, we intend to consider extensions to higher-order networks such as simplicial and cellular complexes, which we illustrate briefly in Appendix B.To project a vector field X : R 2 → R 2 onto the edges of a graph, we employ the de Rham map [27] ,which "discretises" a vector field into edge signals. For a given edge e = (v 0 , v 1 ) with endpoint coordinates x 0 and x 1 , we define the projection X e of X onto e by the following integral.EQUATIONwhere t := x1-x0 ∥x1-x0∥ is the unit tangent vector along the edge. Numerically, this can be computed efficiently using numerical quadratures, owing to the fact that the integral is only defined over the interval [0, 1]. Note that this depends on the ordering of the vertices v 0 and v 1 characterising the edge -if we flip the order, then the sign of X e flips. Thus, we require the graph to be oriented in order for the projections {X e } e∈E to be well-defined. In  
: 
 Our paper aims to fill this gap by proposing a GP based classification algorithm that can naturally incorporate signals on vertices, edges and higher order structures such as simplicial cells by building atop recent works defining GPs on edge spaces [15] and complexes [16] . Furthermore, utilising the Hodge decomposition of signals supported on vertices, edges, etc..., which splits the aforementioned linear signal spectrum space into three canonical subspaces, each with distinct properties, we can model each component separately using different kernels. This idea have been utilised successfully in past works [17] [18] [19] 15] , allowing for greater model flexibility. To the best of our knowledge, we are not aware that these recent extensions and techniques have been applied in the context of graph classification. We demonstrate empirically that these extensions achieve similar or better performance to the GP-based graph classification method of [6] .Finally, while we only consider graph data in this work, our method can be extended easily to higherorder networks, such as simplicial and cellular complexes, that can represent polyadic interaction [20] [21] [22] [23] , generalising the dyadic interaction present in graphs (see Appendix B). 
 
 Appendix:  



Reviews: review: title: title: Review of GP Graph Classification with Hodge Decomposition on vertex and edge spectral signals
main_review: main_review: This paper presents a novel approach for graph classification with GP with spectral features constructed from both vertex and edges of the graph. It extends the interesting approach of the paper Graph classification gaussian processes via spectral features. It not only extends the features to include edges in addition to vertex, but also introduces the Hodge decomposition approach and formulates the GP classification model with additive kernels. Several interesting approaches and novel ideas are proposed and integrated by this paper to improve further on GP graph classification.

The paper also compares its approach and previous approach in several benchmark dataset extensively to demonstrate the classification improvement. In addition, this paper also designs the simulation of vector fields as evaluation dataset of graph classification. It shows the performance improvement on the vector field classification. Further discussions on higher-order networks are also presented.
title: title: Official Review of Submission85 by Reviewer ETym
main_review: main_review: The paper proposes a Hodge decomposition graph classification algorithm within a Gaussian process framework that captures signals on vertices, edges, and higher-order graph structures by analyzing their projections onto the eigenbasis of the graph Laplacian and Helmholtzian. The key idea is to convert the non-Euclidean graph signals into the ones in the Euclidean domain and then apply the standard GP classification algorithm. The paper introduces graph wavelet transforms of the vertex and edge signals and further generates features based on Hodge decomposition as an input to downstream tasks. Experimental results validate the effectiveness of the WT-GP-Hodge algorithm as well as its improvement over the existing methods.

**Strengths**

1. The algorithm directly processes vertex and edge signals, as opposed to WT-GP, which needs to transform the original graph into a line graph. The algorithmic flexibility and practicality are enhanced.
2. The idea of Hodge decomposition and graph wavelet transforms before a standard GP is simple and interesting.
3. The paper is well-written and the results are presented clearly.

**Weaknesses**

1. The method can tackle vertex and edge signals. However, only an algorithm incapable of processing edge features is compared. Empirically, it might be better to conduct an experiment to illustrate that WT-GP can also beat an algorithm incapable of processing vertex features.

2. The authors claim that WT-GP can incorporate high-order graph features and briefly discuss the methodology in Appendix B, which essentially replaces Laplacian / Helmholtzian with the k-th Hodge Laplacian. I am a little skeptical about the kernel in (12) losing high-order information. Experimental results should be added to illustrate this point.