{'fraction_non_alphanumeric': 0.05945575120054882, 'fraction_numerical': 0.011205122341641893, 'mean_word_length': 3.75120285581251, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lossless Representation of Graphs using Distributions

We consider complete graphs with edge weights and/or node weights taking values in some set. In the first part of this paper, we show that a large number of graphs are completely determined, up to isomorphism, by the distribution of their sub-triangles. In the second part, we propose graph representations in terms of one-dimensional distributions (e.g., distribution of the node weights, sum of adjacent weights, etc.). For the case when the weights of the graph are real-valued vectors, we show that all graphs, except for a set of measure zero, are uniquely determined, up to isomorphism, from these distributions. The motivating application for this paper is the problem of browsing through large sets of graphs.


Introduction
Graphs in general, and more particularly weighted or vector weighted graphs, are often used to represent complex structures such as 3D objects (Foulds 1992). This is often done, for example, when trying to determine whether two objects have a similar structure: by using a graph representation, the problem is simplified into determining whether the two underlying graphs are similar. The problem of determining whether two graphs are the same, up to a relabeling of the nodes, is called the graph isomorphism problem. While graph isomorphism is not an NP hard problem, it is still very hard. In fact, the problem is sometimes assigned to a special complexity class called graph isomorphism complete (Skiena [29]).
Graph isomorphism has been a mainstream research problem for more than 30 years (Gati [13], Read and Corneil [25]). Over these years, several solutions have been developed, including graph matching methods (Corneil and Gotlieb [8], Ullmann [32], Kitchen and Rosenfeld [17], Kim and Kim [16], Falkenhainer et al. [11], Horaud and Skordas [15], Myaeng and Lopez-Lopez [23]), canonical labeling representation methods (McKay [19]), graphs invariants (Corneil and Kirkpatrick [9], Umeyama [33], Chung [7], Messmer and Bunke [21], Messmer and Bunke [22]), graph matching based on error-correcting isomorphism methods (Tsai and Fu [30], Shapiro and Haralick [28], Sanfeliu and Fu [26], Eshera and Fu [10], Wong [35]), and approximate graph matching methods (Herault et al. [14], Kittler et al. [18], Christmas et al. [6], Almohamad and Duffuaa [1]). In this paper, we show that many graphs can be uniquely reconstructed from some simple distributions. For example, in the first section of the paper, we show that a large number of weighted graphs can be uniquely reconstructed from their distribution of subtriangles. In other words, their distribution of subtriangles provides a faithful (i.e., lossless) representation for these graphs. This means that isomorphism can be detected simply by comparison of the respective distribution of triangles. For simpler comparison and visualization, we also introduce graph representation in terms of one-dimensional distributions (e.g., node weights, edge weights and sum of adjacent edge weights). As we show in Section 3, for many graphs, these representations are lossless. Actually, when the weights of the graphs take values inside R, the set of exception form a set of measure zero. This work can be viewed as an extension to graphs of the representations we proposed in (Boutin & Kemper 2004) for point configurations.
The results we present are interesting both from a graph theory point point of view and from an application point of view. From an application point of view, having a faithful representation which can be compared quickly is useful in the case where many graphs need to be compared in a short amount of time. For example, an important problem is the problem of browsing for graphs within a large database. In this problem, being able to compare graphs quickly is a key issue. However, this is not the only issue. Indeed, exhaustive searches are not efficient ways to query a large database because their complexity is proportional to the size of the database. For faster search, an index structure must be built. Database indices exploit the presence of natural clusters in the dataset to successively rule out large regions of the data space. Unfortunately, some datasets do not exhibit natural clusters, particularly high-dimensional ones (Beyer et al. [2]). Indeed, while some highdimensional datasets can be dealt with successfully (Shaft and Ramakrishnan [27]) (e.g., when the underlying dimensionality of the dataset is much lower than the dimension of the vectors), clusters can usually only be found in low-dimensional projections of the high-dimensional vectors (Wang and Yang [34]). However, projecting graph representations which are not invariant under isomorphism is unproductive because the labeling ambiguity blurs the distinction between the dimensions being projected. Thus an isomorphism invariant representation is needed. Moreover, a faithful representation guarantees the highest level of comparison accuracy. In particular, small distinguishing features are guaranteed to be preserved. In other words, for a large set of graphs, the proposed representations provide explicit coordinates to represent graphs, and thus naturally lend themselves to the array of database projection and indexing techniques available in the literature. This is in contrast with many current graph indexing approaches which first approximate the structure with a lossy representation before indexing.
From a graph theory point of view, there is a long tradition of considering subgraphs of a given graph and asking how much information about the graph is contained in its subgraph structure. Perhaps the most important example of this approach is Ulam's conjecture (see Ulam [31]), also called the reconstruction problem. The conjecture can be stated as follows: Let G be a simple nondirected graph with n ≥ 3 nodes (simple means for each pair of nodes there either is an edge between them or not). Take the set of all isomorphism classes of (n − 1)-subgraphs of G, i.e., all graphs obtained from G by deleting one node. To each of these isomorphism classes assign its multiplicity, i.e., the number of nodes of G whose deletion leads to a graph in this isomorphism class. The set of isomorphism classes together with their multiplicities is an example of a multiset. We call it the distribution of (n − 1)-subgraphs of G. Ulam's conjecture states that every simple graph with n ≥ 3 nodes is uniquely determined, up to isomorphism, by the distribution of its (n − 1)-subgraphs. This is often phrased by saying that G is reconstructible from its (n − 1)-subgraphs. Ulam's conjecture is still open. Using computational techniques, McKay [20] showed that it holds for n ≤ 11. See also Pouzet and Thiéry [24] for some background and related questions.
Given the difficulty of Ulam's conjecture, there is no way that we could expect that all nonisomorphic graphs can be distinguished by their distributions of subtriangles. Indeed, the first counter example occurs when one looks at graphs with 5 nodes. The example is given by the two graphs in Figure 1. So the question is just how well the distribution of subtriangles discriminates graphs, and how it compares with other graph invariants. As we show in Section 2, quite a large number of graphs can be uniquely represented from their distribution of triangles.

Preliminaries
By a graph G with n nodes we understand a function which assigns to each subset {i, j} ⊆ {1, . . . , n} an element gßi, j in some set X. The value gßi, j is interpreted as the weight of the edge between the nodes i and j. Typically, X will be R or R d , but any other set, including finite sets, are possible. In other words, the graphs we consider are complete, undirected graphs with weighted edges, including edges between a node and itself. The values gßi, i between a node and itself may be interpreted as a node weight. Other classes of graphs are included as special cases: • We may consider nodes i and j with gßi, j = 0 (or some other designated value in X) as not connected. So the case of incomplete graphs is included. The set of edges will be • If all node weights gßi, j are equal, this amounts to the same as saying that there are no node weights. So the case of graphs without any node weights and without edges between a node and itself is included. Likewise, we may consider graphs which have node weights but no edge weight.
• If all gßi, j lie in {0, 1}, then G may be considered as a simple graph, i.e., a graph which has no edge weights. The set of edges of G are then given by (1.1).
Let G and G ′ two graphs, both with n nodes and edge weights gßi, j and g ′ ßi, j in the same set X. We say that G and G ′ are isomorphic if there exists a permutation π ∈ S n such that g ′ ßi, j = gßπ(i), π(j) for all i, j ∈ {1, . . . , n}.
We write G ∼ = G ′ for this.
Let D be a function which assigns a value to each graph G with n nodes and edge weights in a set X. We say that D is a class function if G ∼ = G ′ implies D(G) = D(G ′ ). Assume that D is a class function and G is a graph. We say that G is reconstructible from D (or, by abuse of language, reconstructible from D(G)) if for all other graphs G ′ with n nodes and edge weights in the same set X, we have the implication Note that saying that G is reconstructible from D is equivalent to saying that D is a lossless representation of G. Sometimes we will restrict G and G ′ to special classes of graphs, such as graphs with edge weights but no node weights. So reconstructibility of G from D means that D(G) determines G up to isomorphism. The word "reconstructible" should not be misunderstood to mean that we actually have a method for constructing G, or an equivalent graph, from the knowledge of D(G). In Section 3 we will consider various class functions D 1 , . . . , D r . We say that G is reconstructible from D 1 , . . . , D r if for all other graphs G ′ with n nodes and edge weights in the same set X, we have the implication All functions D on graphs that we consider will assign a distribution to a graph G, the simplest example being the distribution of all edge weights gßi, j. To make this precise, we use the concept of a multiset. A multiset is a set M together with a function M → N >0 into the set of positive integers, which we interpret as assigning a multiplicity to each element of M. Two multisets are considered equal if their underlying sets and multiplicity functions are equal. If we speak of the multiset consisting of all a i for some range of i, we mean that the multiplicity of each a i is |{j | a j = a i }|.
A typical statement using this language would be that a graph G with edge weights gßi, j is reconstructible from the distribution of its edge weights gßi, j. It is easy to see that this statement is true if and only if all edge weights of G are equal. However, if we restrict to graphs which have no node weights, then every graph with at most three nodes is reconstructible from the distribution of its edge weights.

Reconstructibility from the distribution of subtriangles
Let G be graph with n ≥ 3 nodes and edge weights gßi, j ∈ X. In order to get a more distinctive notation for edges between a node and itself, we write w i := gßi, i, which we interpret as the weight of the node i. For i, j, k ∈ {1, . . . , n} pairwise distinct, let tßi, j, k be the multiset consisting of the ordered pairs (gßi, j, w k ), (gßi, k, w j ), and (gßj, k, w i ) ∈ X × X. So tßi, j, k represents the subgraph of G with nodes i, j, k. Taking tßi, j, k as a multiset means that we do not assign any ordering on the nodes, so the subgraph is considered up to isomorphism. Such a subgraph tßi, j, k will be called a subtriangle. Moreover, let T G be the multiset consisting of all t S for S ⊆ {1, . . . , n} with |S| = 3. T G is called the distribution of subtriangles of G. If G ′ is a graph with weighted edges such that G ′ is isomorphic to G, then clearly T G ′ = T G , so T is a class function.

A partial isomorphism
The following lemma establishes a "partial isomorphism" between graphs having the same distribution of subtriangles. Theorem 2.3 and Corollary 2.4 deal with situations where this is a "full" isomorphism.
Lemma 2.1. In the above situation write Let G ′ be a further graph with edge weights g ′ ßi, j and node weights w ′ i such that T G ′ = T G . Then there exists π ∈ S n (the set of bijective maps {1, . . . , n} → {1, . . . , n}) such that (a) for all i ∈ {1, . . . , n} we have Proof. Since T G has n 3 elements, it follows that G ′ , like G, has n nodes. For S, T ∈ P we have by the definition of E: Form the union (with adding multiplicities) of all multisets tßi, j, k lying in T G , and then take the multiset consisting of the first components of all (gßi, j, w k ) lying in this union. This yields the multiset consisting of all g S , S ∈ P , counted n − 2 times for each S ∈ P . Since T G ′ = T G , this implies that the multiset of all g S , S ∈ P and the multiset of all g ′ S , S ∈ P , coincide. With it follows that there exists a bijection ϕ: E → E ′ such that: From the definition of E ′ , we obtain for all S, T ∈ P : Claim 1. For all S, T ∈ E we have: The claim is clearly true if S = T , so we may assume that S = T . To prove the implication "⇒", write S = {i, j}, T = {i, k} with i, j, k ∈ {1, . . . , n} pairwise distinct. The (multi-) set {(gßi, j, w k ), (gßi, k, w j ), (gßj, k, w i )} occurs in T G and therefore also in T G ′ . Hence there exist pairwise distinct r, s, t ∈ {1, . . . , n} with {gßi, j, gßi, k, gßj, k} = {g ′ ßr, s, g ′ ßr, t, g ′ ßs, t}.
But g S = g ′ ßi, j and g T = g ′ ßi, k are elements in the set on the left hand side, so by (2.1) we see that S ∩ T = ∅. This completes the proof of Claim 1.
Indeed, the injectivity of ϕ implies that the intersection has at most one element. Let i ∈ I and choose j, k ∈ N i distinct. By Claim 1, ϕ ({i, j}) and ϕ ({i, k}) have non-empty intersection, so we can write ϕ ({i, j}) = {r, s} and ϕ ({i, k}) = {r, t} with r, s, t ∈ {1, . . . , n} pairwise distinct. We have to show that for every l ∈ N i we have r ∈ ϕ ({i, l}). Assume the contrary. Since ϕ ({i, l}) has a non-empty intersection with {r, s} and with {r, t} by Claim 1, To prove this claim, assume that there exist i, r ∈ I with i = r such that π(i) = π(r). Choose j, k ∈ N i distinct and s, t ∈ N r distinct. By (2.4) we have by Claim 1. This implies i = s or i = t or j = r. In all cases, {i, r} ∈ E follows, thus we may specify our choice of k and t further by setting k = r and t = i. This choice implies j = r and s = i.
Forming the intersection of both sides yields a contradiction with (2.6). This proves Claim 3.
Claim 5. For every i ∈ I we have w ′ π(i) = w i . (Recall that w i is the weight of node i, see before the statement of the theorem.) For the proof, let i ∈ I and choose j, k ∈ N i distinct. Because T G ′ = T G , there exist pairwise distinct r, s, t ∈ {1, . . . , n} such that We have gßi, j = g ′ ßπ(i), u and gßi, k = g ′ ßπ(i), v. Since gßi, j, gßi, k, gßj, k are pairwise distinct, it follows that (gßj, k, w i ) = (g ′ ßu, v, w ′ π(i) ). Hence w i = w ′ π(i) , proving Claim 5.
Claim 6. The map π: I ∪ B 0 → {1, . . . , n} is injective, and for i, To prove this claim, take i, j ∈ I ∪ B 0 distinct. If i, j ∈ I, then both assertions follow from Claims 3 and 4.
Next, assume i ∈ I and j ∈ B 0 . The second assertion follows from the definition of π. By way of contradiction, assume that π(i) = π(j). Choose k, l ∈ N i distinct and write N j = {r}. Then which implies π(i) = π(j) since ϕ ({j, r}) has two elements.
Finally, assume i, j ∈ B 0 distinct. Then {i, j} / ∈ E by the definition of B 0 , so the second assertion of Claim 6 holds automatically.
Since the set on the left side has three distinct elements, we conclude, using (2.10), that gßi, j = g ′ ßπ(i), π(j). This completes the proof.

Distinct weights
We say that a graph G with weighted edges is reconstructible from the distribution of subtriangles if G is reconstructible from T . In other words, we demand that every graph G ′ with the same distribution of subtriangles as G is isomorphic to G.
Example 2.2. Figure 1 on page 2 shows a pair of graphs which are not isomorphic, but have the same distribution of subtriangles. Each edge that is drawn represents an edge of weight 1, and an edge which is not drawn represents weight 0. The node weights can all be taken to be 0. Simple counting reveals that in both graphs there are two subtriangles with all edge weights 0, four subtriangles with one non-zero edge weight, four subtriangles with two non-zero edge weights, and no subtriangle with all weights non-zero. So there exist graphs which are not reconstructible from the distribution of subtriangles. In fact, Figure 1 gives the simplest such example. ⊳ Let 0 ∈ X be some distinguished weight, so gßi, j = 0 may be interpreted as saying that the nodes i and j are not connected. The hypotheses of the following theorem sound a bit technical. For that reason we formulate a special case as Corollary 2.4, where the hypotheses are easier to state (and to remember), so readers might wish to read Corollary 2.4 first. Example 2.5 is a typical example where the hypotheses of Theorem 2.3, but not those of Corollary 2.4, are satisfied. Assume that for every {i, j} ∈ P at least one of the following conditions holds: Then G is reconstructible from the distribution of subtriangles Proof. Let G ′ be a graph with T G ′ = T G , and let π ∈ S n be a bijection as given by Lemma 2.1. Writing ϕ π : P → P for the map induced by π, we obtain gßi, j = g ′ ϕπ({i,j}) = g ′ ßπ(i), π(j) for all {i, j} ∈ P satisfying condition (i) or (ii) of the theorem. In particular, if g S is non-zero for an S ∈ P , then the same is true for g ′ ϕπ(S) . But since the multisets of all g S and of all g ′ S coincide (see the beginning of the proof of Lemma 2.1), it follows that if g S is zero, then g ′ ϕπ(S) is zero, too. So for {i, j} ∈ P satisfying condition (iii) we have gßi, j = 0 = g ′ ϕπ({i,j}) = g ′ ßπ(i), π(j).
The following corollary is just a weaker version of Theorem 2.3. The hypothesis means that 0 is the only weight between distinct edges that may occur repeatedly, or, by interpreting weight 0 as "not connected", that the edge weights between pairs of connected nodes are pairwise distinct. We conclude this section by asking whether distributions of subtriangles can be represented in a practical, computer friendly way. Multisets are not very practical, since the are hard to visualize and to compare. Whether a better representation exists depends on the set X in which the weights gßi, j and w i lie. If X is finite, we may assume X = {1, . . . , r − 1} with an integer r. A pair (gßi, j, w k ) can then be uniquely represented by the single integer gßi, jr + w k < r 2 . Instead of representing a subtriangle tßi, j, k as a multiset, we can order the elements (represented as integers less than r 2 ) by size, so we get 0 ≤ a 1 ≤ a 2 ≤ a 3 < r 2 . These can be uniquely represented by a 1 r 4 + a 2 r 2 + a 3 < r 6 . Continuing this way, T G may be uniquely represented as a single integer between 0 and r 6( n 3 ) − 1. However, the situation becomes much more tricky if X is infinite. Even for X = R, it is far from clear that there is a good way of representing the distribution of subtriangles, and for X = R d it becomes harder still. That is why we turn to simpler, one-dimensional distributions in Section 3.

Some statistics
The hypotheses of Theorem 2.3 and Corollary 2.4 are, very roughly speaking, that the edge weights are sufficiently distinct. It is therefore clear that these hypothesis will tend to be met if the weights take a large range of values, and vice versa. But even if the weights lie in a small set, we can hope that graphs are reconstructible from the distribution of subtriangles even if our theorem fails to guarantee that. To get some idea of to how many graphs this applies, we ran some computer experiments. The results are given in Table 1.
For several values of n and m, we considered all graphs with n points, where the edge weights appearing in the graph are precisely all integers between 0 and m − 1. We considered graphs without node weights. The third column in the table gives the number of graphs which are not reconstructible from the distribution of subtriangles, divided by the number of all graphs. For example, 98.8% of all graphs with 5 nodes and 6 different edge weights are reconstructible from the distribution of subtriangles. Even if most graphs are not reconstructible (as in the case of 6 nodes and 2 different weights), it is still possible that there only exists a small set of pairs of graphs which are not isomorphic but have the same distribution of subtriangles. In fact, this tends to be the case. For example, there are 2 15 = 32768 simple graphs of 6 nodes, affording 2 30 ≈ 10 9 ordered pairs of graphs. Among those, we found precisely 7680960 pairs of two graphs which are non-isomorphic but have the same distribution of triangles. We interpret this by saying that for simple graphs with 6 nodes, the error probability of testing by subtriangles is 7680960/2 30 ≈ 7.15 · 10 −3 . These error probabilities are given in the fourth column of Table 1.
We compared this to the possibilities of discriminating non-isomorphic graphs by another invariant, the spectrum. This is perhaps the best-known graph invariant. By definition, the spectrum of a graph is the set of eigenvalues, with multiplicities, of the adjacency matrix. The fifth column of Table 1 contains the error probabilities when one tries to discriminate non-isomorphic graphs by using the spectrum. So the entry is the number of all pairs of cospectral graphs with a given number of nodes and weights, divided by the number of all pairs. But the spectrum and the distribution of subtriangles should not be regarded as competing invariants, because together they work best, as the last column of the table shows. This column gives the error probabilities one gets when combining the spectrum and the distribution of subtriangles.
The computation were all done by using the computer algebra system Magma (see Bosma et al. [3]).

Reconstructibility from one-dimensional distributions
In this section, we concentrate on the case where the weights of a graph take on real (vector) values. The representations we construct are in terms of simple one-dimensional distributions. As we show in the following, except for a set of measure zero of graphs, the representations we propose are lossless.
Most of the claims in this section are based on the following lemma. A proof can be found in (Boutin & Kemper 2007).

Graphs with edge weights
We first consider the case of a complete graph with n nodes and real valued edge weights g {i,j} . For example, the nodes of the graph could represent a set of points on a circle, and the weights between the nodes could be taken as the Euclidean distance between the corresponding points. Denote by D g (G) the distribution of the weights of the graph. Obviously, most graphs are not reconstructible from the distributions of their weights. But in addition to the weights of the graph, one can also consider the sums of weights assigned to adjacent edges, which we denote by α i,j,k , where α i,j,k = g {i,j} + g {j,k} .
Denote by D α (G) the distribution of the α i,j,k 's of a graph G. Observe that both D g (G) and D α (G) are unchanged under a relabeling of the nodes. Observe also that α i,j,k = α k,j,i , therefore and so to compute D a (G), it is sufficient to compute the distribution of the α i,j,k 's with i, j, k distinct and i < k. We now show that a large number of weighted graphs are reconstructible from the distribution of their weights together with the distribution of the sum of weights assigned to adjacent edges.  Figure 3: A point configuration on a circle can be viewed as a complete weighted graph where the nodes correspond to the points and the edge weights are the Euclidean distances between the corresponding points. We propose to represent such a graph using two distributions: the distribution of the weights, and the distribution of the sums of any two adjacent weights. For most graphs, including the two point configurations pictured above, this is a lossless representation. More precisely, the set of graphs which are not uniquely reconstructible, up to isomorphism, from these two distributions for a set of measure zero. In particular, randomly chosen weights yield, with probability one, graphs that do not lie in the exceptional set. The points of the two configurations above were chosen (uniformly) at random on a unit circle; the histogram of their pairwise distances and the histogram of their sums of adjacent distances are clearly different.
We claim that there exists π ∈ S n such that ϕ ({i, j}) = {π(i), π(j)}, for every distinct i, j = 1, . . . , n, that is to say, that ϕ is simply a relabeling of the nodes. This is because, if we assume the contrary, then, by Lemma 3.1, there exists distinct indices i 0 , j 0 , k 0 such that Since D α (G) = D α (G), there exists i 1 , j 1 , k 1 such that Therefore g {i1,j1} + g {j1,k1} = g {m,p} + g {q,r} which contradicts our hypothesis, and thus ϕ must be a relabeling of the nodes.

Remark 3.3.
A similar result would hold if we defined α i,j,k as the product α i,j,k = g {i,j} g {j,k} . In that case, the hypothesis would be that the graph must satisfy for every pairwise distinct i, j, k and every pairwise distinct m, p, q, r. In particular, graphs with zerovalued weights would automatically be excluded. A work-around would be to shift all the weights by the same non-zero constant λ. Alternatively, one could define α i,j,k as α i,j,k = g {i,j} + λ g {j,k} + λ . Actually, the number of possibilities for the definition of α i,j,k is endless, as any function f of the two arguments g {i,j} g {j,k} can be used. For any such function f , the corresponding theorem hypothesis would be written as f g {i,j} , g {j,k} = f g {m,p} , g {q,r} , for every pairwise distinct i, j, k and every pairwise distinct m, p, q, r. Similar remarks can be made for every theorem in this section.
Observe that the proof of Theorem 3.2 is also valid in the case of vector valued weights g {i,j} = g 1 {i,j} , . . . , g k {i,j} ∈ R k , for any integer k. However, in that case, both D g and D α become kdimensional distributions. From a practical perspective, it is easier to deal with one-dimensional distributions. In particular, comparing one-dimensional distributions is much easier than comparing higher-dimensional distributions. So an interesting question is: "Can graphs with edge weights g {i,j} ∈ R k be uniquely represented, up to isomorphism, by a set of one-dimensional distributions?". We begin by considering the case g {i,j} ∈ R 2 . (Such graphs will be called (2, 0)-attribute graphs.) Denote by α 1 i,j,k the sum of the first weight assigned to two adjacent edges and denote by α 2 i,j,k the sum of the second weight assigned to same two adjacent edges: for all pairwise distinct i, j, k. We also define the mixed sum Denote by D α 1 (G) and D α 2 (G) the distributions of the α 1 i,j,k and of the α 2 i,j,k respectively, for all i, j, k pairwise distinct. Similarly, denote by D α 12 (G) the distribution of the α 12 i,j,k with i, j, k pairwise distinct. We show that most (2, 0)-attribute graphs are reconstructible from five distributions.
Theorem 3.4. Let G be a graph with n ≥ 5 nodes and vector valued weights g {i,j} ∈ R 2 . Suppose that for every pairwise distinct i, j, k and every pairwise distinct m, p, q, r we have Then G is reconstructible from D g 1 (G), D g 2 (G), D α 1 (G), D α 2 (G) and D α 12 (G).
The above proof can trivially be generalized to the case of graphs with vector valued edge weights g {i,j} ∈ R d , for any integer d. Indeed, for any r i, j, k pairwise distinct, we can define the quantities Then we denote by D α l (G) the distributions of the α l i,j,k , for all pairwise distinct i, j, k. Similarly, denote by D α l,l+1 (G) the distribution of the α l,l+1 i,j,k , for all pairwise distinct i, j, k. Using the exact same arguments as for the above proof, we can show that these 3d − 1 one-dimensional distributions fully characterize a large number of vector-valued weighted graphs. More precisely, we obtain the following theorem.
Theorem 3.5. Let G be a graph with n ≥ 5 nodes and weights g {i,j} ∈ R d . Suppose that for every pairwise distinct i, j, k and every pairwise distinct m, p, q, r we have

Graphs with node weights
We now consider the case of a graph with n nodes and node weights w j = g {jj} ∈ R d . First, let us assume that the graph does not have edge weights. Clearly, the graph is then reconstructible from the distribution of the node weights, which is a d-dimensional distribution. But since we are interested in graph representation in terms of one-dimensional distributions, we seek a different representation for d > 1.
Let D w l (G) be the distribution of the w l i , for all i = 1, . . . , n. Let D β l,l+1 (G) be the distribution of the b l,l+1 i,j,k , for all pairwise distinct i, j, k.
Theorem 3.6. Let G be a graph with n ≥ 5 nodes and node weights w j ∈ R d . Suppose that, for every pairwise distinct i, j, k and every pairwise distinct m, p, q, r, we have w l i w l j + w l+1 j w l+1 k = w l m w l p + w l+1 q w l+1 r , for all l = 1, . . . , d − 1.
Since D w l (G) = D w l (G), there exists π l ∈ S n such that w l π(i) = w l i , for all i = 1, . . . , n.
for l = 1, . . . , d. . Using the same argument as in the proof of Theorem3.4 d − 1 times, we can show that this implies that π 1 = π 2 = . . . π d . Therefore G must be isomorphic to G.
Finally, we consider the general case of a complete graph G with both edge weights g {i,j} ∈ R d1 and node weights w i ∈ R d2 . For l = 1, . . . , min{d 1 , d 2 }, let ∆ l i,j,k = w l i + w l j + g l {j,k} .
Denote by D ∆ l (G) the distribution of the ∆ l i,j,k 's with i, j, k pairwise distinct. Using the same arguments as for the previous theorems, we can show the following.
Theorem 3.7. Let G be a graph with n ≥ 5 nodes. Suppose that G has edge weights g {i,j} ∈ R d1 and node weights w i ∈ R d2 . Assume that w l i + w l j + w l+1 j + w l+1 k = w l m + w l p + w l+1 q + w l+1 r , for all l = 1, . . . , d 1 , g l {i,j} + g l+1 {j,k} = g l {m,p} + g l+1 {q,r} , for all l = 1, . . . , d 2 , w 1 i + w 1 j + g 1 {j,k} = w 1 m + w 1 p + g 1 {q,r} , for any pairwise distinct i, j, k and any pairwise distinct m, p, q, r. Then G is reconstructible from the following distributions: