Title: STUDY OF A SIMPLE, EXPRESSIVE AND CONSISTENT GRAPH FEATURE REPRESENTATION

Abstract: Graphs possess exotic features like variable size and absence of natural ordering of the nodes that make them difficult to analyze and compare. To circumvent this problem and learn on graphs, graph feature representation is required. Main difficulties with feature extraction lie in the trade-off between expressiveness, consistency and efficiency, i.e. the capacity to extract features that represent the structural information of the graph while being deformation-consistent and isomorphism-invariant. While state-of-the-art methods enhance expressiveness with powerful graph neural-networks, we propose to leverage natural spectral properties of graphs to study a simple graph feature: the graph Laplacian spectrum (GLS). We analyze the representational power of this object that satisfies both isomorphism-invariance, expressiveness and deformation-consistency. In particular, we propose a theoretical analysis based on graph perturbation to understand what kind of comparison between graphs we do when comparing GLS. To do so, we derive bounds for the distance between GLS that are related to the divergence to isomorphism, a standard computationally expensive graph divergence. Finally, we experiment GLS as graph representation through consistency tests and classification tasks, and show that it is a strong graph feature representation baseline.

1. INTRODUCTION:

No matter where and at which scale we look, graphs are present. Social networks, public transport, information networks, molecules, any structural dependency between elements of a global system is a graph. An important task is to extract information from these graphs in order to understand whether they contain certain structural properties that can be represented and used in downstream machine learning tasks. In general, graphs are difficult to use as input of standard algorithms because of their exotic features like variable size and absence of natural orientation. Consequently, graph feature representation with equal dimensionality and dimension-wise alignment is required to learn on graphs.

Any embedding method is traditionally associated to a trade-off between preservation of structural information (expressiveness) and computation time (efficiency) (Cai et al., 2018) . In the expressiveness, we particularly consider two key attributes of graph feature representation: consistency under deformation and invariance under isomorphism. The first forces the embedding to discriminate two graphs consistently with their structural dissimilarity. The second enables to have one representation for each graph, which can be a challenge since one graph has many possible orientations. In this paper, we propose to analyze the importance of satisfying the introduced criteria through a known but unused, simple, expressive and efficient candidate graph feature representation: the graph Laplacian spectrum (GLS). The Laplacian matrix of a graph is a well-known object in spectral learning (Belkin & Niyogi, 2002) for several reasons. First, the Laplacian eigenvalues give many structural information like the presence of communities and partitions (Newman, 2013) , the regularity, the closed-walks enumeration, the diameter or the connectedness of the graph (Brouwer & Haemers, 2011) . It is also interpretable in term of physics or mechanics (Bonald et al., 2018) . It is backed by efficient and robust approximate eigen decomposition algorithms enabling to scale on large graphs and huge datasets (Halko et al., 2011) . These properties give intuition that GLS can be an appropriate candidate for graph representation. In this paper we go further and analyze additional interesting properties of the Laplacian spectrum through the following contributions: (1) we build a perturbation-based framework to analyze the representation capacity of the GLS, (2) we analyze the consistency between structural deformation of the graph and its GLS by deriving bounds for the distance between the GLS of two graphs, (3) we validate the consistency and the representational power of the GLS with different experiments on synthetic and real graphs.

The rest of the paper is built as follows. Section 2 gives an overview of interesting properties of the GLS for graph representation. A presentation of the mathematical framework and the theoretical analysis are displayed respectively in Section 3 and 4. Section 5 proposes experiments to illustrate theoretical results and show the representational power of GLS. Finally, Section 6 describes related work for whole-graph representation.

2. THE MEANINGFUL PROPERTIES OF THE LAPLACIAN SPECTRUM:

The Laplacian matrix of a graph is a major object in spectral learning (Belkin & Niyogi, 2002) . However, most of the attention is usually directed to its eigenvectors and not its spectrum, and spectral learning is generally applied to node clustering or classification, not whole-graph representation. But, Laplacian spectrum holds interesting properties for graph representation. First, Laplacian spectrum is invariant under graph isomorphism. In fact, graph isomorphism is equivalent to simultaneous permutation of lines and columns in the adjacency matrix, and since the determinant of a permutation is 1 or -1, characteristic polynomial of the Laplacian remains unchanged. Second, each eigenvalue can be seen as an entire whole-graph feature representation by itself, containing specific structural information. Hence any subset of Laplacian eigenvalues is a meaningful and valuable embedding. This enables the usage of truncated Laplacian spectrum (t-GLS) instead of GLS as whole-graph feature representation. Using t-GLS reduces the embedding time thanks to eigenvalue algorithms that do not require entire diagonalization to give partial spectrum (Halko et al., 2011) . Finally, GLS is related to some interpretable structural information of the graph, as reminded below.

Interpretation of the GLS The smallest non-zero eigenvalue of the Laplacian is the spectral gap, corresponding the difference between the two largest eigenvalues of the Laplacian. It contains information about the connectivity of the graph. High spectral gap means high connectivity. For example, given a number of vertices in a connected graph, a minimum spectral gap indicates that the graph is a double kite (Marsden, 2013) . The largest eigenvalue gives a lower bound of the maximal node degree of the graph. The spectral gap can also be viewed as the difference in energy between the ground state and first excited state of a dynamical system (Cubitt et al., 2015) . More generally each eigenvalue of the Laplacian corresponds to the energy level of a stable configuration of the nodes in the embedding space (Bonald et al., 2018) . The lower the energy, the stabler the configuration. In (Shuman et al., 2016) , the Laplacian eigenvalues correspond to frequencies associated to a Fourier decomposition of any signal living on the vertices of the graph. Thus, the truncation of the Fourier decomposition acts as filter on the signal. Characterizing a graph by the some eigenvalues of its Laplacian is thus comparable to characterizing a melody by some fundamental frequencies.

In summary, Laplacian spectrum contains many graph structural information. Methods to get such information are generally computationally expensive. In the light of these properties, we go further and analyze in the following sections the capacity of GLS to represent graph structure.

3. PERTURBATION APPROACH AND PROBLEM SETUP:

We consider two undirected and weighted graphs

G 1 = (V 1 , E 1 , W 1 ) and G 2 = (V 2 , E 2 , W 2 )

with respective adjacency matrix W 1 and W 2 , degree matrix D 1 and D 2 . These matrices are set with respect to an arbitrary indexing of the nodes. Laplacian matrix L i of G i is defined as L i = D i -W i . We aim at using the GLS to build fixed-dimensional representation that encodes structural information to compare any graphs G 1 and G 2 that are not aligned nor equally sized. For the rest of the paper, and without loss of generality we postulate that |V 1 | ≤ |V 2 |. The rest of this section introduces the definitions, hypothesis and notations needed for our theoretical analysis of the GLS.

Definition 1. Let G = (V, E, W ) a weighted graph with n nodes, with W ∈ M n×n the n × n weighted adjacency matrices. We define P ∈ M n×n a symmetric matrix with

P ii = 0, P ij ∈ [-W ij , W ij ] such that W ij + P ij ∈ [0, 1] ∀(i, j).

We define the two following perturbations applied on graph G:

• Adding isolated nodes: W = W 0 n×m 0 m×n 0 m×m • Adding or removing edges: W P = W + P We call edge-perturbation the addition or removal of edges, and node-perturbation the addition of nodes. A complete perturbation is done by adding isolated nodes and perturbing the augmented graph with edge-perturbation. We note that the withdrawal of a node is equivalent to removal of all edges around this nodes. Moreover, if graph G is unweighted, i.e. with binary adjacency, then edge perturbations P ij ∈ {-1, 0, 1}.

Remark 1. If P = -W + Π T W Π with Π ∈ P(n) then the perturbation is a permutation of the node indexing. Such a perturbation is not interesting and edge perturbation due to node indexing has to be annihilated by a permutation matrix as in the following Definition 2: Definition 2. We say that G P * is a perturbed version of G if we have

W P * = Π * T (W + P * )Π * s.t. Π * = arg min Π W P * -Π T W Π 1

i.e. such that P * is the sparsest possible i.e. does not include permutations.

Notations We denote P * the sparsest perturbation as defined in Definition 2. We denote G the completion of G with isolated nodes. If M is a matrix associated to G, we denote M the equivalent matrix for G. We denote λ(X) the eigenvalue of a square matrix X in ascending order, λ i (X) the i th smallest eigenvalue. 

V 2 \ V 1 .

We have defined a notion of continuous deformation of graphs. This deformation has a natural and simple interpretation: any graph G 2 is a perturbed version of graph G 1 , and the larger the perturbation the higher the structural dissimilarity between G 1 and G 2 .

The next section uses the previously presented mathematical framework to analyze the consistency of the Laplacian spectrum as graph representation and its natural link to graph isomorphism problem.

4. LAPLACIAN SPECTRUM AS GRAPH FEATURE REPRESENTATION:

We place ourselves under the Hypothesis 1 saying that the difference between graphs G 1 and G 2 is characterized by the unknown deformation P * . A good embedding of these graphs should be close when level of deformation is low, and far otherwise. This level of deformation can be quantified by the global and node-wise entries of P * . These features are by construction present in the Laplacian of P * , denoted L P * . We use this idea to propose an analysis of the distance between to GLS.

4.1. CONSISTENCY UNDER DEFORMATION AND RELATION TO GRAPH ISOMORPHISM:

Two graphs G 1 and G 2 are isomorphic if and only if ris, 1994) , hence when they are structurally equivalent irrespective to the vertex ordering. Several papers has proposed to use a notion of divergence to graph isomophism (DGI) to compare graphs (Grohe et al., 2018; Rameshkumar et al., 2013) . The DGI between graphs G 1 and G 2 is generally the minimal Frobenius norm of the difference between L 1 and Π -1 L 2 Π. Considering this definition, the following Lemma links the graph-isomorphism problem and the Laplacian of the hypothetical perturbation P * and show that this divergence is the norm of L P * : Lemma 1. Using the notations from Hypothesis 1, we have: L 2 = Π * T L 1 + L P * Π * , with L P * = diag(P * 1 |V1| )-P * the Laplacian of P * and 1 n the n-dimensional unit vector. In particular,

∃Π ∈ P(|V 1 |) such that L 2 = Π -1 L 1 Π (Mer-

min Π L 2 -Π T L 1 Π F = L P * F .

We remind that graph isomorphism is at best solved in quasipolynomial time (Babai, 2016) and can not be used in practice for large graphs and datasets. The following Proposition show how the distance between GLS relaxes the isomorphism-based graph divergence. Proposition 1. Using Hypothesis 1 and Lemma 1:

λ(L 2 ) -λ(L 1 ) 2 ≤ L P * F .

The above result tells us that the higher the difference between GLS, the larger the hypothetical perturbation P * , i.e. the higher the structural dissimilarity.

We now study the implication of GLS closeness. This problem tackles the notion of non-isomorphic L-cospectrality, i.e. the idea that two graphs can have equal eigenvalues while having different Laplacian matrix (Brouwer & Haemers, 2011) . The following proposition gives a simple insight into the problem of spectral characterization in our perturbation-based framework: Proposition 2. We denote

L i = Q i Λ i Q T i the SVD of L i such that the diagonal of Λ i is in ascending order. Hence we have L P * F ≤ λ(L 2 ) -λ(L 1 ) 2 + Π * T Q 1 Λ 2 Q 1 T Π * -L 2 F .

This proposition shows that equal spectrum means equal graphs only when eigenvectors are also equal. Otherwise, L-cospectrality for non-isomorphic graphs tells us that there exists families of graphs that are not fully determined by their spectrum. These families are characterized by some structural properties such that two non-isomorphic graphs with equal Laplacian spectrum share these properties but not their adjacency (Van Dam & Haemers, 2003) . In practice, this is not a problem. First, almost all graphs are determined by their spectrum (Brouwer & Haemers, 2011) . Second, equal GLS indicates the precious information that graphs share common statistical, mechanical, physical or chemical properties (see Section 2), no matter the adjacency matrix. These physical properties are what we seek to represent when representing graphs for ML tasks. Third, non-isomorphic L-cospectrality concerns equally sized graphs which is not likely with respect to all possible reallife graphs. When the studied dataset contains specifically L-cospectral non-isomorphic graphs and when the task requires unique representation property, GLS is not appropriate and more sophisticated and powerful embedding methods taking for example eigenvectors into account (Verma & Zhang, 2017 ) should be studied and used. Otherwise, i.e. in almost every situations, according to previously presented results, GLS characterizes the graph and is directly related to the hypothetical perturbation P * .

Nevertheless, we accordingly propose the Proposition 3 to better understand GLS proximity even when graphs are non-isomorphic cospectral. Proposition 3. The closer the GLS, the closer to unitary-similarity the Laplacian matrices.

We remind that two real n-square matrices A and B are unitary-similarity if there exists an orthogonal matrix O such that B = OAO T . Similarity is an equivalence relation on the space of square-matrices. Moreover, divergence to unitary-similarity is a relaxed version of the divergence to graph-isomorphism (Grohe et al., 2018) , where the permutation matrix space is replaced by a unitary matrix space. Finally from Proposition 1 and 3 we can bound the distance between GLS as follows:

min O∈O(|V2|) L 1 -OL 2 O T F ≤ λ(L 1 ) -λ(L 2 ) 2 ≤ L P * .

In this section, we have shown that structural similarity (divergence) between graphs can be reasonably approximated by the similarity (divergence) between their GLS.

4.2. LAPLACIAN SPECTRUM AS WHOLE-GRAPH REPRESENTATION IN PRACTICE:

Previous section showed the capacity of the distance between Laplacian spectrum to serve as proxy for graph similarity. In practice, a fixed embedding dimension d must be chosen for all graphs in dataset D. According to previous analysis, the most obvious dimension is d = max G∈D |V | and all graphs with less than d nodes may be pad with isolated nodes. We note that padding with isolated nodes is equivalent than adding zeros in the GLS. Nevertheless, in some datasets, some graphs can be significantly larger and the padding can become abusive. We therefore propose for these graph to have d < max G∈D |V |. We simply truncate the GLS such that we keep only the highest d eigenvalues. This method also enables to save computation time.

The problem with this method is that we may lose information for graphs with more than d nodes. In practice, for large graphs, the contribution of the lowest eigenvalues to the distance between GLS as a proxy for graph divergence is negligible. In particular, large graph have many sparse areas, such that many eigenvalues are very low, hence truncating the bottom part of the GLS may not be a problem. We assess the impact of the truncation in the experimental section.

Though, we can also propose several ways to avoid this problem, like embedding the lowest eigenvalues with simple statistics, like moments or histograms. In the experimental section, we do not use this trick.

5. EXPERIMENTS:

All experiments can reproduced using the notebook given at: https://github.com/ researchsubmission/ICLR2020/.

5.1. PRELIMINARY EXPERIMENTS:

As a first illustration of deformation-based results presented in Section 4, we propose to use Erdos-Rnyi random graphs (Erdős & Rényi, 1959) with parameter p = 0.05. We focus on three simple experiments.

First, the distance between the Laplacian spectrum of a graph and a perturbed version of this graph is related to the number of perturbations. We can find the experimental illustration in Figure 1 . We see that the number of perturbations is roughly equally related to the distance between GLS features for edge addition and edge withdrawal, i.e. for graph sparsity decrease or increase. A relation between graph sparsity and Laplacian eigenvalues can be seen for example through the Gershgorin circle theorem (Gershgorin, 1931) .

Figure 1 : Experimental results to illustrate how GLS behaves under edge addition (left), edge withdrawal (right). In this case, studied adjacency and perturbation matrix are binary.

Second, we mentioned that when a graph is significantly bigger than other graphs of a dataset, w can use a truncated GLS (t-GLS). This method both saves computation time thanks to iterative eigenvalues algorithms and avoid the addition of isolated nodes in all other graphs. In Figure 3 , we show results of experiments showing that t-GLS is consistent with node addition. As experimental setup, we take a reference graph with n nodes and compute its GLS. Then we add a randomly connected node and compute the t-GLS of the new graph, by keeping only the n largest eigenvalues. We repeat it 20 times. We compute the L 2 -distance to reference GLS, for different levels of connectivity for the additional nodes. We first observe that the t-GLS is consistent with node addition. We also confirm our previous theoretical results by observing that the more connected the additional nodes, the higher the GLS divergence.

5.2. CLASSIFICATION OF MOLECULAR AND SOCIAL NETWORK GRAPHS:

We evaluate spectral feature embedding with a classification task on molecular graphs and social network graphs. Experimental setup for classification task is given in Appendix E. We assume here that two structurally close graphs belong to the same class. We challenge this assumption with the following experiments. All values reported in Table 1 and Table 2 are taken from the above-mentioned papers.

On molecular graphs We use five datasets for the experiments: Mutag (MT), Enzymes (EZ), Proteins Full (PF), Dobson and Doig (DD) and National Cancer Institute (NCI1) (Kersting et al., 2016) . All graphs are chemical components. Nodes are atoms or molecules and edges represent checmical or electrostatic bindings. We note that molecular graphs contain node attributes, that are used by some models presented in Table 1 . We let the question of the relevance of comparing models with slightly different inputs to the discretion of the reader. Description and statistics of molecular datasets are presented in Table 3 

Analysis of the results:

The classification results above illustrate the capacity of GLS to capture graph structural information, under the assumption that structurally close graphs belong to the same class. The graph neural-networks are globally more expressive since they can leverage specific information for graph classification since is end-to-end. In particular, they obtain strong results when there are node labels (see molecular experiments 5.2). Nevertheless, GLS is a simple way to represent graphs in an unsupervised manner, with theoretical background, simplicity of implementation (eigendecomposition is accessible to anyone interested in any computer) and competitive downstream classification results.

On the reasonability of using truncated GLS We assess the impact of truncating the GLS. Using truncated GLS (t-GLS) enables to (1) reduce the computational cost for large graphs and ( 2) reduce the dimensionality of the graph representation for all graphs. Results are presented in Figure 3 for molecular datasets.

Figure 3 : Illustration of the impact of the truncation in term of classification accuracy of the molecular graphs. We represent the impact relatively to the 95-percentile truncation adopted for classification experiments.

We see that truncating GLS is not highly impacting classification results. Only ENZYME multiclass classification, which is a particularly difficult task (see experiments in Section 5.2), suffers from truncation. Additional insight about the t-GLS is given in Appendix G.

6. RELATED WORK:

We propose to divide graph feature representation into three categories: graph kernel methods, feature-based methods and deep learning.

Graph kernel methods Kernel methods create a high-dimensional feature representation of data.

The kernel trick (Shawe-Taylor et al., 2004) avoids to compute explicitly the coordinates in the feature space, only the inner product between all pairs of data image: it is an implicit embedding methods. These methods are applied to graphs (Nikolentzos et al., 2018; 2017) . It consists in performing pairwise comparisons between atomic substructures of the graphs until a good representative dictionary is found. The embedding of a graph is then the number of occurrences of these substructures within it. These substructures can be graphlets (Yanardag & Vishwanathan, 2015) , subtree patterns (Shervashidze et al., 2011 ), random walks (Vishwanathan et al., 2010) or paths (Borgwardt & Kriegel, 2005) . The main difficulty lives in the choice of appropriate algorithm and kernel that accept graphs with variable size and capture useful feature for downstream task. Moreover, kernel methods can be computationally expensive but techniques like the Nystrm algorithm (Williams & Seeger, 2001) allow to lower the number of comparison with a low rank approximation of the similarity matrix.

Feature-based methods Feature-based representation methods (Barnett et al., 2016) represent each graph as the concatenation of features. Generally, the feature-based representation can offer a certain degree of interpretability and transparency. The most basic ones are the number of nodes or edges, the histogram of node degrees. These simple graph-level features offers by construction the sought isormorphism-invariance but suffer from low expressiveness. More sophisticated algorithms consider features based on attributes of random walks on the graph (Gómez & Delvenne) while others are graphlet based (Kondor et al., 2009) . (Kondor & Borgwardt, 2008) explicitly built permutation-invariant features by mapping the adjacency matrix to a function on the symmetric group. (Verma & Zhang, 2017) proposed a family of graph spectral distances to build graph features. Experimental work in (de Lara & Pineau, 2018) used normalized Laplacian spectrum with random forest for graph classification with promising results. (Wilson & Zhu, 2008) analyzes the cospectrality of different graph matrices and studies experimentally the representational power of their spectra. These two last works are directly related to the current work. Nevertheless, in both cases, the theoretical analysis is absent and comparative experiment with current benchmarks and methods is limited. in this paper we propose a response to these concerns.

Deep learning based methods GNNs learn representation of nodes of a graph by leveraging together their attributes, information on neighboring nodes and the attributes of the connecting edges.

When graphs have no vertex features, the node degrees are used instead. To create graph-level representation instead of node representation, node embeddings are pooled by a permutation invariant readout function like summation or more sophisticated information preserving ones (Ying et al., 2018; Zhang et al., 2018) . A condition of optimality for readout function is presented in (Xu et al., 2019) . Recently, Xinyi & Chen (2018) levraged capsule networks (Sabour et al., 2017) , neural units designed to enable to better preserve information at pooling time. Other popular evolution of GNNs formulate convolution-like operations on graphs. Formulation in spectral domain (Bruna et al., 2013; Defferrard et al., 2016) is limited to the processing of different signals on a single graph structure, because they rely on the fixed spectrum of the Laplacian. Conversly, formulation in spatial domain are not limited to one graph structure (Atwood & Towsley, 2016; Duvenaud et al., 2015; Niepert et al., 2016; Hamilton et al., 2017) and can infer information from unseen graph structures. At the same time, alternative to GNN exist and are related to random walk embedding. In Li et al. (2017) , neural networks help to sample paths which preserve significant graph properties. Other approaches transforms graphs into sequence of nodes embedding passed into a recurrent neural network (RNN) (You et al., 2018; Pineau & de Lara, 2019) to get useful embedding. These models do not inherently include isomorphism-invariance but greedy learn it by seeing the same graph numerous times with different node ordering and embedding. These methods are powerful and globally obtain a high level of expressiveness (see experimental section 5.2).

7. CONCLUSION:

In this paper, we analyzed the graph Laplacian spectrum (GLS) as whole graph representation.

In particular, we showed that comparing two GLS is a good proxy for the divergence between two graphs in term of structural information. We coupled these results to the natural invariance to isomorphism, the simplicity of implementation, the computational efficiency offered by modern randomized algorithms and the rare occurrence of detrimental L-cospectral non-isomorphic graphs to propose the GLS as a strong baseline graph feature representation.

A PROOF OF LEMMA 1

Proof.

L 2 = D 2 -W 2 = diag(W 2 1) -W 2 = diag(Π * T W 1 + P * Π * 1) -Π * W 1 + P * Π * = diag(Π * T W 1 Π * 1) + diag(Π * T P * Π * 1) -Π * T W 1 Π * -Π * T P * Π * = Π * T D 1 Π * -Π * T W 1 Π * + Π * T D P * Π * -Π * T P * Π * = Π * T L 1 Π * + Π * T L P * Π *

with L P * = diag(P * 1) -P * = D P * -P * and 1 the unit vector.

Therefore,

min Π L 2 -Π T L 1 Π F = min Π Π T L P * Π F = L P * F B PROOF OF PROPOSITION 1

Proof. From lemma 1 we have L 2 = Π * T L 1 Π * + Π * T L P * Π * . Moreover, from Weyl's eigenvalues inequalities and since eigenvalues are isomorphism invariant:

λ i (L 2 ) ≤ λ i (L 1 ) + λ |V2| (L P * ) λ i (L 1 ) + λ 1 (L P * ) ≤ λ i (L 2 )

Hence:

λ 1 (L P * ) ≤ λ i (L 2 ) -λ i (L 1 ) ≤ λ |V | (L P * )

Now let (λ, x) be any eigen couple of a matrix M ∈ M n×n . We can always pick i ∈ {1 . . . n} and build x such that |x i | = 1 and |x j =i | < 1. Hence:

(M x) i = λx i ⇐⇒ n j=1 m ij x j = λx i ⇐⇒ λ 2 ≤ n j=1 (m ij x j ) 2 =⇒ λ 2 ≤ n j=1 (m ij ) 2 =⇒ λ 2 ≤ 1 n n i,j=1 m 2 ij

Using previous results we get:

|V2| i=1 λ i (L 2 ) -λ i (L 1 ) 2 ≤ |V 2 | 1 |V 2 | |V2| i,j=1 L P * 2 ij = L P * 2 F , with X F = i j |X ij | 2 the Frobenius norm.

C PROOF OF PROPOSITION 2

Proof. We remind that the Forbenius norm is unitarily invariant thanks to the cyclic property of the trace. For any P ∈ O(|V 2 |) we have:

L P * F = Π * T L 1 Π * -L 2 F = Π * T L 1 Π * -P T L 2 P + P T L 2 P -L 2 F ≤ Π * T L 1 Π * -P T L 2 P F + P T L 2 P -L 2 F .

In particular if

P = Q 2 Q 1 T Π * : P T L 2 P -L 2 F = (Q 2 Q 1 T Π * ) T L 2 Q 2 Q 1 T Π * -L 2 F = (Q 2 Q 1 T Π * ) T Q 2 Λ 2 Q 2 T Q 2 Q 1 T Π * -L 2 F = Π * T Q 1 Λ 2 Q 1 T Π * -L 2 F ,

We also have that

Π * T L 1 Π * -P T L 2 P F = Q 1 Λ 1 Q 1 T -Π * (Q 2 Q 1 T Π * ) T Q 2 Λ 2 Q 2 T Q 2 Q 1 T Π * Π * T F = Λ 1 -Λ 2 F .

Hence:

L P * F ≤ Λ 1 -Λ 2 F + Π * T Q 1 Λ 2 Q 1 T Π * -L 2 F .

D PROOF OF PROPOSITION 3:

Proof. Denoting O(n) the n-orthogonal matrices group (orthogonal since real), we want to show that:

min O∈O(|V2|) L 1 -O T L 2 O F ≤ λ(L 1 ) -λ(L 2 ) 2

We denote

L i = Q i Λ i Q i T the eigendecomposition of the Laplacian L i with Λ i = diag(λ(L i ))

. Since Q 1 is unitary and using property of Frobenius norm, we have, ∀O ∈ O(|V 2 |):

L 1 -O T L 2 O F = Λ 1 -Q 1 T O T Q 2 Λ 2 Q 2 T OQ 1 F ,

We know that Q 1 and Q 2 are orthogonal since they are respectively eigenvector matrices of symmetric matrix L 1 and L 2 . We therefore have:

(Q T 2 OQ 1 ) T (Q T 2 OQ 1 ) = Q 1 T O T Q 2 Q T 2 OQ 1 = I |V1| Moreover ∀ Π ∈ P(|V 2 |) ⊂ O(|V 2 |), if O = Q 2 ΠQ 1 T then O ∈ O(|V 2 |).

Hence,

min O∈O(|V2|) L 1 -O T L 2 O F = min O∈O(|V2|) Λ 1 -Q 1 T O T Q 2 Λ 2 Q 2 T OQ 1 F ≤ min Π∈P(|V2|) Λ 1 -Q 1 T (Q 2 ΠQ 1 T ) T Q 2 Λ 2 Q 2 T (Q 2 ΠQ 1 T )Q 1 F = min Π∈P(|V2|) Λ 1 -ΠT Λ 2 Π F = min Π∈P(|V2|) Λ 1 -ΠΛ 2 ΠT F = min Π∈P(|V2|) Λ 1 -ΠΛ 2 ΠT F = min σ∈S(|V2|) λ(L 1 ) -λ(L 2 ) σ(1:|V2|) 2 ≤ λ(L 1 -λ(L 2 ) 2

with S(n) the permutation group of {1 . . . n}.

E EXPERIMENTAL SETUP FOR CLASSIFICATION OF GRAPHS:

For classification, we use standard 10-folds cross validation setup. Each dataset is divided into 10 folds such that the class proportions are preserved in each fold for all datasets. These folds are then used for cross-validation i.e, one fold serves as the testing set while the other ones compose the training set. Results are averaged over all testing sets. All figures gathered in the tables of results are build using this setup. For the dimension d ∈ 1, max G∈D |V | , representing the number of eigenvalues we keep to build the truncated GLS, we chose the percentile 95 of the distribution of graph sizes in each dataset, i.e. we truncate the 5% smallest eigenvalues. Considering weak truncation impact (see Section 5.2, when we have large datasets containing large graphs, like the two REDDIT datasets, we can truncate more severely to make the problem computationally more efficient. In particular considering that GLS approached as a simple baseline more than a final graph representation for large scale usage.

We use the support vector classifier (SVC) from scikit-learn (Pedregosa et al., 2011) . We impose Radial Basis Function as kernel, i.e. K(λ(L 1 ), λ(L 2 )) = exp (-γ λ(L 1 ) -λ(L 2 ) 2 2 ). It is a similarity measure related to L 2 -norm between GLS. Hence, our theoretical results remain consistent with our experiments. Hyper parameters C and γ are tuned among respectively {0.5, 1, 5} and {0.0001, 0.001, 0.01, 0.1, 0.5, 1, 5} for the molecular datasets, and {0.5, 1, 5, 25, 50} and {0.0001, 0.001, 0.01, 0.1} for the social network datasets. In practice, using a global pool for all the datasets gives equivalent results, but hyperparameter inference becomes expensive with a too large grid, in particular in a 10-fold cross validation setup. We use a nested hyperparameter search cross-validation for each of the 10 folds: in each 90% training fold we performe a 5-fold random search cross-validation before training. We therefore avoid the problem of overfitting related to model selection that appear when using non-nested cross-validation (Cawley & Talbot, 2010) .

We additionally put our results with k-nearest neighbor algorithm with L 2 norm, in order to illustrate the notion of proximity we introduced: neighboring GLS is related to structurally close graphs (i.e. eventually graphs from the same class).

F CHARACTERISTICS OF THE REAL DATASETS:

We use five molecular datasets and five social network datasets for the experiments (Kersting et al., 2016) . Tables 3 and 4 gives statistics of the differents datasets. All used datasets can be found at https://ls11-www.cs.tu-dortmund.de/staff/morris/ graphkerneldatasets (Kersting et al., 2016) .

Molecular graphs datasets are Mutag (MT), Enzymes (EZ), Proteins Full (PF), Dobson and Doig (DD) and National Cancer Institute (NCI1). In MT, the graphs are either mutagenic and not mutagenic. EZ graphs are tertiary structures of proteins from the 6 Enzyme Commission top level classes. In DD, compounds are secondary structures of proteins that are enzyme or not. PF is a subset of DD without the largest graphs. In NCI1, graphs are anti-cancer or not. The graphs of these datasets have node labels that can be leverages by graph neural networks. Social networks datasets are IMDB-Binary (IMBD-B), IMDB-Multi (IMDB-M), REDDIT-Binary (REDDIT-B), REDDIT-5K-Multi (REDDIT-M) and COLLAB. REDDIT-B and REDDIT-M contain graphs representing discussion thread, with edges between users (nodes) when one responded to the other's comment. Classes are the subreddit topics from which thread have originated. IMDB-B and IMDB-M contain networks of actors that appeared together within the same movie. IMDB-B contains two classes for action or romance genres and IMDB-M three classes for comedy, romance and sci-fi. COLLAB graphs represent scientific collaborations, with edge between two researchers meaning that they co-authored a paper. Labels of the graphs correspond to subfields of Physics. The graphs of these datasets have no node attributes and therefore enable fair comparison with deep learning methods. 

MT:



IMDB:



G ADDITIONAL INSIGHT ON THE ACCEPTABILITY OF USING TRUNCATED GLS:

Figure 4 illustrates the reasonability of using only the highest eigenvalues of the Laplacian spectrum as whole-graph feature representation. We take the original and final graphs of the deformationconsistency test presented in Figure 3 . We compute the L 2 distance between t-GLS with dimension d and divide it by d, for d varying from 1 to 15 . The objective is to confirm that first eigenvalues are relatively more important to discriminate to structurally different graphs, which is the case. We note that for the Erdos-Reyni case with few connected additional nodes, first eigenvalues are not as relatively important as for the other example. In fact, adding nodes with stochastic connections is the construction process of Erdos-Reyni graphs. Hence, discriminating augmented graph from the original one is difficult based only on the structural information.

:



Figures and Tables:

Without loss of generality, we assume that G 2 is a perturbed version of G 1 , i.e. ∃P * the sparsest |V 2 |-square perturbation matrix and Π * ∈ P(|V 2 |) a |V 2 |-square permutation matrix such that W 2 = Π * T W 1 + P * Π * . P * is a |V 2 |-square block matrix, with top-left block P * 11 being a |V 1 |-square perturbation matrix for graph G 1 . Bottom right block P * 22 is the (|V 2 | -|V 1 |)square adjacency matrix of the additional nodes. P * 12 is the |V 1 | × (|V 2 | -|V 1 |) adjacency matrix representing the links between graph G 1 and the additional nodes

Figure 2: Experimental results illustrate how truncated GLS behaves under iterative addition of 20 new nodes with respectively 0, 1, 2 and 3 random connections with graph, for respectively synthetic a 80-nodes Erdos-Reyni graph (left) and a 28-nodes molecular graph from MUTAG dataset (right). Horizontal dotted lines (right figure) are the quartiles 25, 50, 75 and 100 of the distances between the GLS of the 28-nodes graph and the other 187 graphs of the dataset.

Figure4: Illustration of the relative importance of the dimensionality of GLS-embedding, after the iterative addition of 20 new nodes with respectively 0, 1, 2 and 3 random connections with graph, for respectively synthetic a 80-nodes Erdos-Reyni graph (left) and a 28-nodes molecular graph from MUTAG dataset (right). We see that the first largest eigenvalues of the Laplacian are the most important to discriminate a graph and its perturbed version.

Accuracy (%) of classification with different graph representations, on molecular graphs. All graphs are social networks. The graphs of these datasets do not contain node attributes. Therefore, we can more appropriately compare GLS + SVC to deep learning based classification. Statistics about social networks datasets are presented in Table4, Appendix F.

Table content: <table><tr><td/><td/><td>, Appendix F.</td><td/><td/><td/></tr><tr><td/><td>MT</td><td>EZ</td><td>PF</td><td>DD</td><td>NCI1</td></tr><tr><td>EMD + SVC</td><td>86.1 ± 0.8</td><td>36.8 ± 0.8</td><td>-</td><td>-</td><td>72.7 ± 0.2</td></tr><tr><td>PM + SVC</td><td>85.6 ± 0.6</td><td>28.2 ± 0.4</td><td>-</td><td>75.6 ± 0.6</td><td>69.7 ± 0.1</td></tr><tr><td>FB + SVC</td><td>84.7 ± 2.0</td><td>29.0 ± 1.2</td><td>70.0 ± 1.3</td><td>-</td><td>62.9 ± 1.0</td></tr><tr><td>DyF + SVC</td><td>86.3 ± 1.3</td><td>26.6 ± 1.2</td><td>73.1 ± 0.4</td><td>-</td><td>66.6 ± 0.3</td></tr><tr><td>VRGC</td><td>86.3 ± 8.6</td><td>48.4 ± 6.2</td><td>74.8 ± 3.0</td><td>-</td><td>80.7 ± 2.2</td></tr><tr><td>GCN*</td><td>85.6 ± 5.8</td><td>-</td><td>76.0 ± 3.2</td><td>-</td><td>80.2 ± 2.0</td></tr><tr><td>DGCNN*</td><td>85.8 ± 1.7</td><td>51.0 ± 7.3</td><td>75.5 ± 0.9</td><td>79.4 ± 0.9</td><td>74.4 ± 0.5</td></tr><tr><td>CapsGNN*</td><td>86.7 ± 6.9</td><td>54.7 ± 5.7</td><td>76.3 ± 3.6</td><td>75.4 ± 4.2</td><td>78.4 ± 1.6</td></tr><tr><td>GIN-0*</td><td>89.4 ± 5.6</td><td>-</td><td>76.2 ± 2.8</td><td>-</td><td>82.7 ± 1.7</td></tr><tr><td>GraphSAGE*</td><td>85.1 ± 7.6</td><td>-</td><td>75.9 ± 3.2</td><td>-</td><td>77.7 ± 1.5</td></tr><tr><td>GLS + SVC</td><td>87.9 ± 7.0</td><td>40.7 ± 6.3</td><td>75.3 ± 3.5</td><td>74.3 ± 3.5</td><td>73.3 ± 2.1</td></tr></table>

Classification accuracy (%) of different deep learning based models plus ours over standard social networks datasets. Graphs of these datasets does not have node features. SVC stands for support vector classifier.

Table content: <table/>

Molecular datasets statistics. Bias indicates the proportion of the dominant class.

Table content: <table><tr><td>EZ</td><td>PF</td><td>DD</td><td>NCI1</td></tr></table>

Social network datasets statistics. Bias indicates the proportion of the dominant class.

Table content: <table><tr><td/><td>-B</td><td>IMDB-M</td><td>REDDIT-B</td><td>REDDIT-M</td><td>COLLAB</td></tr><tr><td># graphs</td><td>1000</td><td>1500</td><td>2000</td><td>4999</td><td>5000</td></tr><tr><td># classes</td><td>2</td><td>3</td><td>2</td><td>5</td><td>3</td></tr><tr><td>bias (%)</td><td>50.0</td><td>33.3</td><td>50.0</td><td>20.0</td><td>52.0</td></tr><tr><td>min./max. |V |</td><td>12/136</td><td>7/89</td><td>3/3760</td><td>22/3606</td><td>32/492</td></tr><tr><td>avg. |V |</td><td>20</td><td>13</td><td>426</td><td>501</td><td>75</td></tr><tr><td>avg. |E|</td><td>97</td><td>66</td><td>496</td><td>590</td><td>2458</td></tr><tr><td>Node attributes</td><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
This paper focuses on the laplacian spectrum of a graph as means to generate a representation. This representation can be used to compare graphs, and classify them. The authors prove that structural similarity is reflected by the similarity in their GLS. I propose rejection of this paper for the following reasons: - The idea of using the spectrum for defining graph similarity is definitely not novel. See the tutorial *Node Similarity, Graph Similarity and Matching: Theory and Applications*. - The claim that structural similarity (especially cut similarity) is reflected on the Laplacian spectrum is known. - This paper misses important literature, and actually many papers on graph similarity. E.g., *Least-squares estimation of transformation parameters between two point patterns* by Umeyama. Since then a lot of work has followed up on the topic. A beautiful work related to this was published recently by Kolla et al *Spectrally Robust Graph Isomorphism* - The paper is not well-written. Besides the existence of typos (E.g., Rnyi is R*{e}nyi), some parts can become shorter since they are standard. - Isomorphism on random binomial graphs is known to be an easy (i.e., in P) problem. I understand that it stands as a sanity check, but a more interesting sanity check would be great. Overall the experiments are not convincing.