{'fraction_non_alphanumeric': 0.037747941167045856, 'fraction_numerical': 0.016214310891787098, 'mean_word_length': 4.43409367926171, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Restructuring Graph for Higher Homophily via Learnable Spectral Clustering

While a growing body of literature has been studying new Graph Neural Networks (GNNs) that work on both homophilic and heterophilic graphs, little work has been done on adapting classical GNNs to less-homophilic graphs. Although lacking the ability to work with less-homophilic graphs, classical GNNs still stand out in some properties such as efficiency, simplicity and explainability. We propose a novel graph restructuring method to maximize the benefit of prevalent GNNs with the homophilic assumption. Our contribution is threefold: a) learning the weight of pseudo-eigenvectors for an adaptive spectral clustering that aligns well with known node labels, b) proposing a new homophilic metric that measures how two nodes with the same label are likely to be connected, and c) reconstructing the adjacency matrix based on the result of adaptive spectral clustering to maximize the homophilic scores. The experimental results show that our graph restructuring method can significantly boost the performance of six classical GNNs by an average of 25% on less-homophilic graphs. The boosted performance is comparable to state-of-the-art methods.


Introduction
Graph Neural Networks (GNNs) were originally inspired under the homophilic assumption -nodes of a graph with the same label are more likely to be connected than nodes with different labels. Recent studies reveal the limitations of this homophilic assumption when GNNs are applied on less-homophilic or heterophilic graphs (Pei et al., 2020). Ever since, a number of approaches have focused on developing deep learning architectures for heterophilic graphs (Zhu et al., 2021b;Kim and Oh, 2021;Chien et al., 2021;Bo et al., 2021;Lim et al., 2021). However, little work has been done on adapting classical GNNs to less-homophilic graphs. Although classical GNNs are lacking the ability to work with less-homophilic graphs, they still stand out in some properties such as efficiency (Zeng et al., 2020), simplicity (Wu et al., 2019) and explainability (Ying et al., 2019).
Our work studies a graph restructuring method that reconstructs the adjacency matrix of a graph from scratch to uplift the benefit of prevalent homophilic GNNs. Our work is partially inspired by Klicpera et al. (2019b), we extend the restructuring approach to heterophilic graphs and improve the performance of GNNs which do not work well on heterophilic graphs. Our observation from spectral clustering of heterophilic graphs shows that the eigenvectors corresponding to the leading eigenvalues do not always align well with the node labels. Particularly, in a heterophilic graph, two adjacent nodes are unlikely to have the same label, which is in contradiction with the smoothness properties of leading eigenvectors. However, when we choose eigenvectors appropriately, the correlation between the similarity of spectral features and node labels increases. To generalize this observation, we propose a learnable spectral clustering algorithm that, a) divides the Laplacian spectrum into even slices called pseudo-eigenvalues, each slice corresponds to an embedding matrix called pseudo-eigenvector; b) learns the weights of pseudo-eigenvectors from existing node labels; c) restructures the graph according to node embedding distance to maximize homophily. To measure the homophilic level of graphs, we further introduce a new metric that addresses some limitations of the previous metrics. Our experimental results show that the performances of node-level prediction tasks with restructured graphs are greatly improved on classical GNNs.

Related Work
GNNs for heterophilic graphs. Early GNNs assume homophily implicitly. Such an inductive bias results in a degenerated performance on less-homophilic graphs (Lim et al., 2021). Recently, homophily is also shown to be an effective measure of a graph's robustness to both over-smoothing and adversarial attacks. In the over-smoothing setting, node representations converge to a stationary state of similar values ("over-smoothed") as a GNN goes deeper. A graph of low homophily is more prone to this issue as the stationary state is reached with fewer GNN layers (Yan et al., 2021). Similarly, homophilic graphs are more resilient to a graph injection attack than their heterophilic counterparts in the adversarial attack setting. Some techniques defend against such attacks by improving or retaining homophily under graph injection (Zhu et al., 2021a;Chen et al., 2022). Pei et al. (2020) firstly draw attention to the limitation of GNN on less-homophilic graphs. Since then, various GNNs have been proposed to improve performance on these graphs. H 2 GCN (Zhu et al., 2020) show that proper utilization of ego-embedding, higher-order neighbourhoods, and intermediate embeddings can improve results in heterophilic graphs. A recent scalable model, LINKX (Lim et al., 2021), shows separating feature and structural embedding improves performance. Kim and Oh (2021) study this topic specifically for graph attention and finds improvements when an attention mechanism is chosen according to homophily and average degrees. Chien et al. (2021) propose to use a generalized PageRank method that learns the weights of a polynomial filter and show that the model can adapt to both homophilic and heterophilic graphs. Similarly,  use learnable spectral filters for achieving an adaptive model on graphs of different homophilic levels. Zhu et al. (2021b) recently propose to incorporate a learnable compatibility matrix into GNN-based methods to handle heterophily of graphs.
Learning spectral clustering. From the deep learning perspective, most previous studies about spectral clustering aim at clustering using learning approaches, or building relations between a supervised learning model and spectral clustering. Law et al. (2017) and Bach and Jordan (2003) reveal that minimizing the loss of node similarity matrix can be seen as learning the leading eigenvector representations used for spectral clustering. Bianchi et al. (2020) train cluster assignment using a unsupervised MinCut objective and further use the learned clusters in a pooling layer to improve GNN performance. Instead of directly optimizing a similarity matrix, Tian et al. (2014) adopt an unsupervised autoencoder design that uses representations learned in hidden layers to perform K-means. Chowdhury and Needham (2021) show that Gromov-Wasserstein learning, an optimal transport-based clustering method, is connected with a two-way spectral clustering.
Graph restructuring and rewiring. GDC (Klicpera et al., 2019b) is one of the first works proposed to rewire edges in a graph. It uses diffusion kernels, such as heat kernel and personalized PageRank, to redirect messages passing beyond existing edges. Chamberlain et al. (2021) and Eliasof et al. (2021) extend the diffusion kernels to different classes of partial differential equations. In a slightly different setting where graph structures are not readily available, some try to construct graphs from scratch instead of modifying the existing edges. Fatemi et al. (2021) construct homophilic graphs via self-supervision on masked node features. Kalofolias (2016) learns a smooth graph by minimizing tr(X T LX). These works belong to the "learning graphs from data" family (Dong et al., 2019) which is relevant but different to our work because a) these methods infer graphs from data where no graph topology is readily available, while in our setting, the original graphs are the key ingredients; b) as shown by Fatemi et al. (2021), without the initial graph, the performance of these methods are not comparable to even a naive GCN; c) these methods are mostly used to solve graph generation problems instead of a node-or link-level task.

Preliminaries
Spectral filtering. Let G = (V, E, A, X) be an undirected graph with N nodes, where V , E, and A ∈ {0, 1} N ×N are the node set, edge set, and adjacency matrix of G, respectively, and X ∈ R N ×F is the node feature matrix. The normalized Laplacian matrix of G is defined as L = I − D −1/2 AD −1/2 , where I is the identity matrix with N diagonal entries and D ∈ R N ×N is the diagonal degree matrix of G. In spectral graph theory, the eigenvalues Λ = diag(λ 1 , ..., λ N ) and eigenvectors U of L = U ΛU H are known as the graph's spectrum and spectral basis, respectively, where U H is the Hermitian transpose of U . The graph Fourier transform takes the form ofX = U H X and its inverse is X = UX.
It is known that the Laplacian spectrum and spectral basis carry important information on the connectivity of a graph (Shuman et al., 2013). Intuitively, lower frequencies correspond to global and smooth information on the graph, while higher frequencies correspond to local information, discontinuities and possible noise (Shuman et al., 2013). One can apply a spectral filter and use graph Fourier transform to manipulate signals on a graph in various ways, such as smoothing and denoising (Schaub and Segarra, 2018), abnormally detection (Miller et al., 2011) and clustering (Wai et al., 2018). Spectral convolution on graphs is defined as the multiplication of a signal x with a filter g(Λ) in the Fourier domain, i.e. (1) Spectral Clustering (SC) as low-pass filtering. SC is a well-known method for clustering nodes in the spectral domain. A simplified SC algorithm is described in Appendix A.5. Spectral clustering can be interpreted as low-pass filtering on a one-hot node signal δ i ∈ R N , where the i-th element of δ i is 1, i.e. δ i (i) = 1, and 0 elsewhere, for each node i. Filtering δ i in the graph Fourier domain can be expressed as where g λ L is the low-pass filter that filter out components whose frequencies are greater than λ L as As pointed out by Tremblay et al. (2016); Ramasamy and Madhow (2015), f i − f j 2 can be approximated by filtering random node features with g λ L . Consider a random node feature matrix R = [r 1 |r 2 |...|r η ] ∈ R N ×η consisting of η random features r i ∈ R N of V i.i.d sampled form the normal distribution with zero mean and 1/η variance. Let H λ L = U g λ L (Λ)U H . We can definẽ (4) R is a random Gaussian matrix of zero mean and U is orthonormal. We apply the Johnson-Lindenstrauss lemma (Appendex A.3) to obtain the following error bounds. Proposition 3.1 (Tremblay et al. (2016)). Let , β > 0 be given. If η is larger than: then with probability at least 1 − N −β , we have: Hence, f i −f j is a close estimation of the Euclidean distance f i −f j . Note that the approximation error bounds in Equation 6 hold for any band-pass filterḡ e1,e2 : where 0 ≤ e 1 ≤ e 2 ≤ 2 since the spectrum of a normalized Laplacian matrix has the range [0, 2]. This fact is especially useful when the band passḡ e1,e2 can be expressed by a specific functional form such as polynomials, since H e1,e2 = Uḡ e1,e2 (Λ)U H can be computed without eigen-decomposition.

Learnable Spectral Clustering
Now we propose a learnable method for spectral clustering which empowers us to restructure a graph to improve graph homophily while preserving the original graph structures as much as possible.

Discrepancy between SC and labels
Spectral clustering aims to cluster nodes such that the edges between different clusters have low weights and the edges within a cluster have high weights. Such clusters are likely to align with the labels of nodes when a graph is homophilic, i.e., nodes with the same labels are likely to be connected. Whereas this may not hold in the case of less-homophilic graphs. Figure 1 visualizes the nodes in the Wisconsin and Europe Airport datasets based on the eigenvectors corresponding to the five smallest eigenvalues. As shown in Figure 1a and 1c, the labels are not aligned with the node clusters. However, if we choose the eigenvectors carefully, nodes clusters can align better with their labels, as evidenced by Figure 1b and 1d, which are visualized using manually chosen eigenvectors. Below, we discuss how to develop a learnable SC method that aligns the clustering structure with node labels by learning the underlying frequency patterns. The spectral expressive power of this method is discussed separately in Appendix A.7.

Learning eigenvector coefficients
Let f Z i be the representation of a node i obtained from an arbitrary set Z ⊆ [N ] of eigenvectors in place of the ones with the leading eigenvalues. We cast the problem of finding eigenvectors to align with the known node labels into a minimization problem of computing the distance between the representations of nodes i and j when their labels are the same. Let d(·) be a distance metric between two node representations. Then, our objective is formalized as where V Y is a collection of nodes whose labels are available, 1 is an indicator function, y i is the label of node i, and is a loss function. The loss function penalizes the objective when two nodes with the same label are far from each other, as well as when two nodes with different labels are close. In this work, we use Euclidean distance and a contrastive loss function.
Solving the above objective requires iterating over all possible combinations of eigenvectors, which is infeasible in general. It also requires performing expensive eigendecomposition with O(N 3 ) time complexity. In addition, SC does not consider feature similarity between nodes. To address these challenges, we introduce two key ideas to generalize SC in the next section.

Eigendecomposition-free SC
As explained in Section 3, f i − f j can be approximated by a filtering operation under the Johnson-Lindenstrauss lemma. The same holds true for the generalized case f Z i . However, the operation still requires expensive eigendecomposition as Equation 7 takes eigenvalues explicitly. To mitigate this issue, we propose to use a series of rectangular functions, each serving as a band-pass filter that "slices" the Laplacian spectrum into a finite set of equal-length and equal-magnitude ranges. Each filter takes the same form of Equation 7, but is relaxed on the continuous domain. This formulation comes with two major advantages. Firstly, rectangular functions can be efficiently approximated with polynomial rational functions, thus bypassing expensive eigendecomposition. Secondly, each g e1,e2 groups frequencies within the range (e 1 , e 2 ] to form a "coarsened" pseudo-eigenvalue. Because nearby eigenvalues capture similar structural information, the "coarsening" operation reduces the size of representations, while still largely preserving the representation power. Spectrum slicers. We approximate the band-pass rectangular filters in Equation 7 using a rational function where s ≥ 2 is a parameter that controls the width of the passing window on the Laplacian spectrum, a ∈ [0, 2] is another parameter that controls the horizontal center of the function, and m is the approximation order. A larger m can reduce the approximate error but is more expensive to compute. Figure 2 shows an example of these functions. With properly chosen s and a, the Laplacian spectrum can be evenly sliced into chunks of range (λ i , λ i+1 ). Each chunk is a "coarsened eigenvalue" that umbrellas eigenvalues within the range. Substituting g(λ) in Equation 1 withĝ s,a , the spectral filtering operation becomes An important property of Equation 10 is that the matrix inversion can be computed via truncated Neumann series (Wu et al., 2013). This can bring the computation cost of O(N 3 ) down to O(pN 2 ).
can be expressed by a Neumann series with guaranteed convergence. (A proof is given in Appendix A.4.)

SC with node features
Traditionally, SC does not use node features. However, independent from graph structure, node features can provide extra information that is valuable for a clustering task. This is especially true where node features are in disagreement with representations obtained from eigenvectors. Therefore, we incorporate node features into the SC filtering operation by concatenating it with the random signal before the filtering operation Γ s,a =ĝ s,a (L)(R X), where is a column-wise concatenation operation. Γ s,a has the shape of N × (P + F ) and is sometimes referred as "dictionary" (Thanou et al., 2014). When using a series of g s,a , we have Γ = (Γ s1,a1 Γ s2,a2 ...). Figure 3: Graph restructuring workflow using learnable spectral clustering.
Let P be the dimension of embeddings and Θ represent a learnable weight matrix or a feed-forward neural network. The concatenated dictionary is then fed into a learnable function to obtain a node embedding matrix H ∈ R N ×P as H = Θ(Γ).
(13) Our objective in Equation 8 can then be realized as where N Y (k) is a set of negative samples whose labels are different from node i, i.e. y i = y k . The intuition is if the labels of nodes i and j are the same, then the distance between the two nodes needs to be less than the distance between i and k, to minimize the loss.
[a] + = max(a, 0) and is a scalar offset between distances of intra-class and inter-class pairs. By minimizing the objective w.r.t the weight matrix Θ, we can learn the weight of each band that aligns the best with the given labels.

Restructure graphs to maximize homophily
After training, we obtain a distance matrix D where D ij = H i · −H j · . As suggested by Klicpera et al. (2019b), there are two ways to restructure a graph from the matrix. One way is to apply a threshold on D and entries below the threshold are kept as edges; another way is to draw edges between K nodes pairs of the smallest distance. As the D is learned with labels, the restructured graph is likely to have higher homophily than the original graph. In practice, for better control of sparsity, we draw edges between node pairs with a small distance. Specifically,Â is the adjacency matrix whose entries are defined aŝ where topK -1 returns node pairs of the k smallest entries in D . In the implementation, we start with an empty adjacency matrix and iteratively add edges until the homophily score starts to drop. A simplified workflow is illustrated in Figure 3. A detailed algorithm can be found in Appendix A.6.

Complexity analysis
The most expensive operation of our method is the matrix inversion in Equation 10 which has the time complexity of O(pN 2 ). A small p ≤ 4 is sufficient because the Neumann series is a geometric sum so exponential acceleration tricks can be applied. We use Equation 10 because it is closer to a rectangular function and better illustrates the spectrum slicing idea, but in practice, it can be replaced by other slicer functions that do not require matrix inversion, such as a quadratic function 1 − (sL − a) 2 , to further reduce cost. It is also worth noting that the matrix inversion and multiplication only need to be computed once and can be pre-computed offline. The training step can be mini-batched easily. We randomly sample 8 − 64 negative samples per node so the cost of computing Equation 14 is low.

Homophily Measure
Various methods have been proposed to measure the homophily of a graph (Zhu et al., 2020;Lim et al., 2021). The two most used are edge homophily h edge and node homophily h node : the former uses  Figure 4: Examples of graphs with different label-topology relationships and comparison of different homophily measures. The node colour represents the node labels. The red edges connect nodes of different labels, while the green edges connect nodes of the same labels. Figure 4a -Figure 4c shows homophilic graphs of different densities. h den gives a higher score when a graph is dense, while the other metrics give the same scores. Figure 4d and Figure 4e are two graphs that only consist of inter-class edges, but are of different densities. Figure 4f is a label-imbalanced graph. Figure 4g and Figure 4h are two regular graphs, where Figure 4g has an intra-class/inter-class edge ratio of 0.5, Figure 4h is an example of an Erdos-Reyi graph sampled with uniform edge probability. where N u is the neighbour set of node u, and y is the node label.
As pointed out by Lim et al. (2021), both edge and node homophily suffer from sensitivity to both label number and label imbalance. For instance, a balanced graph of C labels would induce homophily of 1 C for both measures. In addition, both metrics fail to handle cases of imbalanced labels, resulting in undesirably high homophily scores where the majority nodes are of the same label.
To mitigate these issues, Lim et al. (2021) proposed a new metric h norm that takes into account the label-wise node and edge proportion: K is the number of unique labels, Y k is the node set of label k, and h k is the label-wise homophily.
Nevertheless, h norm only captures relative edge proportions and ignores graph connectivity, resulting in high homophily scores for highly disconnected graphs. For example, Figure 4a has the same h norm as Figure 4b and 4c. The absence of edge density in the homophilic metric brings undesirable results in restructuring as the measurement always prefer a disconnected graph. Moreover, although h norm is lower-bounded by 0, it does not explicitly define the meaning of h norm = 0 but instead refers to such graphs as less-homophilic in general, resulting in further confusion when comparing less-homophilic graphs.
Given the limitations of existing metrics, we propose a density-aware homophily metric that measures the tendency of edges connecting nodes of the same label (intra-class) over nodes of different labels (inter-class). For a graph of K > 1 labels, the following five propositions hold for our new metric: 1. A dense homophilic graph of a complete set of intra-class edges and zero inter-class edges has a score of 1. (Figure 4c) 2. A dense heterophilic graph of a complete set of inter-class edges and zero intra-class edges has a score of 0. (Figure 4e) 3. An Erdos-Renyi random graph G(n, p) of n nodes and the edge inclusion probability p has the score of ≈ 0.5, i.e. a graph that is uniformly random (Figure 4h). 4. A totally disconnected graph and a complete graph have the same score of 0.5. 5. For graphs with the same intra-class and inter-class edge ratios, the denser graph has a relatively higher score. (Figure 4a, 4b and 4c) (Figure 4d and 4e), (Figure 4g and 4h) Proposition 1 and 2 define the limits of homophily and heterophily given a set of nodes and their labels. Proposition 3 and 4 define neutral graphs which are neither homophilic nor heterophilic. Proposition 3 states that a uniformly random graph, which has no label preference on edges, has homophily score of 0.5. Proposition 5 considers edge density: for graphs with the same tendencies of connecting inter-and intra-class nodes, the denser one has a higher absolute score value. The metric is defined as below.ĥ (17) where d k is the edge density of the subgraph formed by nodes from the label k, i.e. the intra-class edge density of k including self-loops, andd k is the maximum inter-class edge density of label k where d kj is the inter-class edge density of label j and k, i.e. edge density of the subgraph formed by nodes from label k and j.
Equation 17 has the range (−1, 1). To make it comparable with the other homophily metrics, we scale it to the range (0, 1) using Proposition 1, 2, 4 and 5 are easy to prove. We hereby give a brief description and proof for Proposition 3. Lemma 2. ∀K > 1, E[h den ] = 0.5 for the Erdos-Renyi random graph G(n, p). (A proof is given in Appendix A.4.) Figure 4 shows some example graphs with four different metrics. Compared with h node and h edge , h den is not sensitive to the number of labels and label imbalance. Compared with h norm , h den is able to detect neutral graphs. h den gives scores in the range (0, 0.5) for graphs of low-homophily, allowing direct comparison between them. h den also considers edge density and therefore is more robust to disconnectivity.
Experimental setup. Hyperparameters are tuned using grid search for all models on the unmodified and restructured graphs of each dataset. We record prediction accuracy on the test set averaged over 10 runs with different random initializations. We use the same split setting as Pei et al. (2020); Zhu et al. (2020). The results are averaged over all splits. We adopt early stopping and record the results from the epoch with highest validation accuracy. Homophily scores are computed using validation set only in the validation step. We report the averaged accuracy as well as the standard deviation. For the spectrum slicer in Equation 10, we use a set of 20 slicers with s = 40 and m = 4 so that the spectrum is sliced into 20 even range of 0.1. The graphs are restructured to have edges that give the highest h den before it starts to decrease. All experiments are run on a single NVIDIA RTX A6000 48GB GPU unless otherwise noted.
Node classification results. Node classification tasks predict labels of nodes based on graph structure and node features. We aim to improve the prediction accuracy of GNN models by restructuring edges via the learnable SC method, particularly for heterophilic graphs. The evaluation results are shown in Table 1. On average, the performance of GNN models is improved by an average of 25%. We attribute this improvement to the increased homophily in the restructured graphs.
Performance vs. Homophily Figure 5b shows an ideal scenario where the "optimal edges" point corresponds to both the highest homophily and accuracy. Figure 5a shows a less-ideal scenario where the "optimal edges" point slightly lags behind best accuracy. In fact, in the latter case, the highest homophily scores of training, validation and test sets are reached at different edge numbers. The highest homophily on the training set is reached where the edge number is around 12,000, while it is 40,000 and 70,000 on the validation and test set. This suggests a discrepancy of frequency patterns in training, validation and test sets, as the clustering model is trained on training sets, it learns only the frequency patterns on the training set and generalizes sub-optimally on the unseen sets. This is also shown in Table 1 where the performance improvements achieved on SQUIRREL are greater than on CHAMELEON. We show this as a limitation of our model: when the frequency patterns on training and unseen sets are different, the learnable spectral clustering approach has limited ability to improve downstream model performance. We also noticed increased homophily on homophilic graphs does not always bring performance improvement, but we will leave this for future work.

Conclusion
We propose an approach to enhance GNN performance on less-homophilic graphs by restructuring the graph to maximize its homophily. Our method is inspired and closely related to Spectral Clustering (SC). It extends SC beyond the leading eigenvalues and learns the frequencies that are best suited to cluster a graph. To achieve this, we use rectangular spectral filters expressed in the Neumann series to slice the graph spectrum into chunks that umbrellas small ranges of frequency. We also proposed a new homophily metric that is density-aware and is a better homophily indicator for the quality of graph restructuring. There are many promising extensions of this work, such as using it to guard against over-smoothing and adversarial attacks, by monitoring changes in homophily and adopting tactics to maintain it.

A.1 Dataset Details
We use 6 datasets listed in Table 2. TEXAS, WISCONSIN and CORNELL are graphs of web page links between universities, known as the CMU WebKB datasets. We use the pre-processed version in Pei et al. (2020), where nodes are classify into 5 categories of course, faculty, student, project and staff. SQUIRREL and CHAMELEON are graphs of web pages in Wikipedia, originally collected by Sen et al. (2008), then Pei et al. (2020) classifies nodes into 5 classes according to their average traffic. ACTOR is a graph of actor co-occurrence in films based on Wikipedia, modified by Pei et al. (2020) based on Tang et al. (2009). A.2 Experiment Results Figure 6 shows the node classification accuracy from Table 1. The performance of classical GNNs before and after restructuring are plotted as histograms. Performance of three GNNs that target less-homophilic datasets, Geom-GCN, H 2 GCN and GPRGNN, are plotted as horizontal lines.

A.3 Johnson-Lindenstrauss Theorem
Theorem A.1 (Johnson-Lindenstrauss Theorem (Dasgupta and Gupta, 2003)). For any 0 < < 1 and any integer n, let k be a positive integer such that k ≤ 4( 2 /2 − e 3 /3) −1 ln n Then for any set S of n points in R d , there is a map f : R d −→ R k such that for all u, v ∈ S, Furthermore, this map can be found in randomized polynomial time.
We refer the readers to Dasgupta and Gupta (2003) for proof. In this work, we adopt a side result of their proof, which shows the projection f = R x is an instance of such mapping that satisfies Equation 22, where R is a matrix of random Gaussian variables with zero mean. Achlioptas (2003) further extends the proof and shows that a random matrix drawn from [1, 0, −1], or [1, −1] also satisfies the theorem. We leave these projections for future study.
In another word, ρ(I − T ) < 1. Gelfand's formula shows that if ρ(I − T ) < 1, then lim p→∞ (I − T ) p = 0 and the inverse of T can be expressed by a Neumann series T −1 = ∞ p=0 (I − T ) p .
We recall Lemma 2: Lemma 2. ∀K > 1, E[h den ] = 0.5 for the Erdos-Renyi random graph G(n, p). (A proof is given in Appendix A.4.) Proof. For each node label k of |Y k | nodes, the are at most |Y k |+1 2 = |Y k |(|Y k | + 1)/2 intra-class edges (including self-loops). For each pair of label (k, j), there are at most |Y k ||Y j | inter-class edges. On average G(n, p) has n+1 2 p edges, among which |Y k |+1 2 p = |Y k |(|Y k |+1)p 2 are intra-class for k, and |Y k ||Y j |p are inter-class for the class pair (k, j). Hence from Equation 18   we minimize the square error between H ∈ R N ×1 in Equation 13 and the target pixel values, i.e.
where Y i is the target pixel value of node i. We train the models with 3000 iterations and stop early if the loss is not improving in 100 consecutive epochs.  Table 3 shows the square loss of our method along MLP and 2 GNNs. Our method consistently outperforms other models. Some output images are shown in Figure 8. As expected, MLP fails to learn the frequency pattern across all three categories. GCN, GAT and GIN are able to learn the low-pass pattern but failed in learning the band and high-frequency patterns. Although ChevNet shows comparable results in the high-pass task, it is achieved with 41,537 trainable parameters while our method only requires 2,050 parameters. Lastly, our method is the only one that can learn and accurately resemble the band-pass image, demonstrating a better flexibility in learning frequency patterns.

A.8 Code
The code of our experiments is released under the MIT license at https://anonymous.4open. science/r/graph_restructure-1BBB. Figure 8: The low-pass, band-pass and high-pass images learned using MLP, GIN, ChevNet and our method. The images learned using our method better resemble the images shown in Figure 7 across all three categories.