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. 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 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. 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. with L P * = diag(P * 1) − P * = D P * − P * and 1 the unit vector. Therefore, Moreover, from Weyl's eigenvalues inequalities and since eigenvalues are isomorphism invariant: Hence: 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: Using previous results we get: Proof. We remind that the Forbenius norm is unitarily invariant thanks to the cyclic property of the trace. For anyP ∈ O(|V 2 |) we have: We also have that Hence:
We study theoretically the consistency the Laplacian spectrum and use it as whole-graph embeddding This paper forcuses on the laplacian spectrum of a graph as means to generate a representation to be used to compare graphs and classify them. This work proposed to use Graph Laplacian spectrum to learn graph representation.