Distributional Signals for Node Classification in Graph Neural Networks
Authors: Feng Ji
See Hian Lee
Zhao Kai
Wee Peng Tay
Jielong Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph neural networks
graph signal processing
regularization
smoothness
node classification

Abstract: In graph neural networks (GNNs), both node features and labels are examples of graph signals, a key notion in graph signal processing (GSP). While it is common in GSP to impose signal smoothness constraints in learning and estimation tasks, it is unclear how this can be done for discrete node labels. We bridge this gap by introducing the concept of distributional graph signals. In our framework, we work with the distributions of node labels instead of their values and propose notions of smoothness and non-uniformity of such distributional graph signals. We then propose a general regularization method for GNNs that allows us to encode distributional smoothness and non-uniformity of the model output in semi-supervised node classification tasks. Numerical experiments demonstrate that our method can significantly improve the performance of most base GNN models in different problem settings. 

DISTRIBUTIONAL SIGNALS FOR NODE CLASSIFICA- TION IN GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In graph neural networks (GNNs), both node features and labels examples of graph signals, key notion in graph signal processing (GSP). While it is common in GSP impose signal smoothness constraints in learning and estimation tasks, it is unclear how this can be done for discrete node labels. We bridge this gap by introducing the concept of distributional graph signals. In our framework, we work with the distributions of node labels instead of their values and propose notions of smoothness and non-uniformity of such distributional graph signals. We then propose general regularization method for GNNs that allows to encode distributional smoothness and non-uniformity of the model output in semi- supervised node classification tasks. Numerical experiments demonstrate that our method can significantly improve the performance of most base GNN models different problem settings.
INTRODUCTION
We consider the semi-supervised node classification problem (Kipf & Welling 2017) that determines class labels of nodes in graphs given sample observations and possibly node features. Numerous graph neural network (GNN) models have been proposed to tackle this problem. One of the first models the graph convolutional network (GCN) (Defferrard et al. 2016). Interpreted geometrically, a GCN aggregates information such as node features from the neighborhood of each node of the graph. Algebraically, this process is equivalent to applying a graph convolution filter node feature vectors. Subsequently, many GNN models with different considerations are introduced. Popular models include the graph attention network (GAT) (Veličković et al.) (018)) that learns weights between pairs of nodes during aggregation, and the hyperbolic graph convolutional neural network (HGCN) (Chami et al. 2019) that considers embedding of nodes of a graph in a hyperbolic space instead of Euclidean space. For inductive learning, GraphSAGE (Hamilton et al.) (017)) is proposed to generate low-dimensional vector representations for nodes that are useful for graphs with rich node attribute information. While new models draw inspiration from GCN, GCN itself is built upon the foundation of graph signal processing (GSP).
GSP is signal processing framework that handles graph-structured data (Shuman al. 2013 Ortega
ct al. 2018 Ji & Tay] (201)) A graph signal is a vector with each component corresponding to a node of graph. Examples include node features and node labels. Moreover, convolutions used in models such as GCN are special cases of convolution filters in GSP (Shuman et al. 2013). All these show the close connections between GSP theory and GNNs.
In GSP, signal smoothness (over the graph) is widely used to regularize inference tasks. Intuitively, a signal is smooth if its values are similar at each pair of nodes connected by an edge. One popular way to formally define signal smoothness is to use the Laplacian quadratic form. There are numerous GSP tools that leverage smooth prior of the graph signals. For example, Laplacian (Tikhonov) regularization is proposed for noise removal in /Shuman al. (2013) and signal interpolation (Narang ct al. 2013). In Chen et al. (2015), it is used in graph signal in-painting and anomaly detection. In Kalofolias (016)) the same technique is used for graph topology inference.
However, for GNNs, it is remarked in Yang et al. (2021 Section 4.1.2) that "graph Laplacian regularization can hardly provide extra information that existing GNNs cannot capture". Therefore, regularization scheme based on feature propagation is proposed. is demonstrated to be effective by comparing with other methods such as Feng al. (2021) and Deng & 7hu (2019) based on

---

adversarial learning and Stteetu et al. (019) that co-trains GNN models with additional agreement model, which gives the probability that two nodes have the same label. We partially agree with the above assertion regarding graph Laplacian regularization, while remaining reservative about its full correctness. In this paper, we propose a method that is inspired by Laplacian regularization. As our main contribution, we introduce the notion of distributional graph signals, instead of considering graph signals. Analogous to the graph signal smoothness defined using graph Laplacian, we define the smoothness of distributional graph signals. Together with another property known as non-uniformity, we devise a regularization scheme for GNNs in node classification tasks. This approach is easy to implement and can be used as plug-in regularization term together with any given base GNN model. Its effectiveness is demonstrated with numerical results.
2 DISTRIBUTIONAL GRAPH SIGNALS
In this section, we motivate and introduce distributional graph signals based on GSP theory.
2.1 GSP PRELIMINARIES AND SIGNAL SMOOTIIESS
In this subsection, we give brief overview of GSP theory (Shuman al., 2013). The focus is on the discussion of graph signal smoothness.
Let (V. E) be an undirected graph with V the vertex set and & the edge set. Suppose the size of the graph is [V]. Fix an ordering of V. Then, the space of graph signals can be identified with the vector space IR.", with graph signal x E RR" which assigns i-th component to the i-th vertex of G. By convention, signals are in column form, and æ(i) is the i-th component of æ.
In GSP, the key notion is the graph shift operator. Though there are several choices for the graph shift operator, in our paper, we consider a common choice: Lg. the Laplacian of G, defined by Lg = Dg Ag, where Dg. Ag are the degree matrix and adjacency matrix of G, respectively. The Laplacian Lg is positive semi-definite and symmetric. By the spectral theorem, it has an cigendccomposition Lg = Ug In the decomposition, Ag is a diagonal matrix, whose diagonal entries (A1 -.,, Am) } are eigenvalues of Lg. They are non-negative and we assume Xι ... An- The associated eigenbasis {uI,.... 4n} } are the columns of Ug. In GSP, an eigenvector with a small eigenvalue (and hence small index) is considered to be smooth. The signal values of such a vector have small fluctuations across the edges of G.
Given a graph signal æ, its graph Fourier transform is & U3 æ. or equivalently, .(1) (ar, u.). for 1 < < n. The components iti) of ă are called the frequency components of æ. Same as above, the signal smooth if (i) has a small absolute value for large i. Quantitatively, we can define its total variation by
T(x)=
Σ (x(i) (((1)=x())² x Lgæ. (EER))EE
(1)
is straightforward to compute that T(u,) = A₁ This observation indicates that is reasonable to use total variation as measure of smoothness. Minimizing the total variation of graph signals has many applications in GSP as we have pointed out in Section
2.2 STEP GRAPH SIGNALS
Let S be finite set of numbers. A step graph signal with respect to (W.F..) S is graph signal such that all its components take values in S, i.e., x E S".
Example 1. For the simplest example, consider the classical Heaviside function H on R. defined by (x) = 1, for > O and Hxx) 0, for x < 0. It is a non-smooth function, as it is not even continuous at x
On the other hand, let G be the path graph with 2m + nodes embedded on the real line by identifying the nodes of G with the integers in the interval [-m, Then H induces step graph signal h on G. Same as the Heaviside function H. the signal h should be considered to be non-smooth graph signal.
Step graph signals occur naturally in semi- superispe node classification tasks. In particular, if is the set of all possible class labels, then the labels of the nodes of G form step graph signal e w.r.t.
2

---

on G. We expect that analogous to Example I possibly be non-smooth. To demonstrate, analyze с using its Fourier transform è (cf. Section 2.1 I. More specifically, we take Gu to be the main connected component of the Cora graph Sen al. 20088) and to be the ground truth labels. We also generate a random signal r following the same empirical distribution (on S) estimated using c. We show plots of both Fourier transforms è and F in Fig. [ We see that the high-frequency components of the ground truth labels с can be large, and it is even possible that its spectrum, i.c., frequency components, resemble that of random signal. The observations support our speculation about the non-smoothness of the step signals. Therefore, in order to leverage signal smoothness to enhance model performance, we need to find an alternative the step (label) signals. This also supports the remark of Yang et al. (2021) regarding Laplacian regularization from different point of view (see also the experiments in Section 4.2
Glo and touth Iulocde (Uhux)
Raurioa labels
Supezingcoen plota (Cooss
20
20
10
10
10
10
F
-10
-10
-10
-20
-20
-20
600
1000
2600
500
1000
2000
2000
1000
1600
2000
2500
Teder Enequeac composince
Index
frequency comporrats
Indlex frequency comporarats
Figure 1: Plots of è and e for Cora.
2.3 DISTRIBUTIONAL GRAPH SIGNALS AND MARGINALS
We want to use probability theory to introduce the notion of "smoothness" for step signals in the next section. For preparation, in this subsection, we formally introduce distributional graph signals and discuss how they arise naturally in GNNs. Our theory (e.g., in Definition and equation (3) is based on probability measures defined on metric spaces. To this end, endow any discrete space S with the discrete metric d(s1, $2) = if $1 + 82 E S and 0 otherwise. For R", one can use the usual Euclidean metric any other norm.
For metric space M St or R", let P(M) be the space of probability measures on M. (w.r.t. the Borel a-algebra) having finite second moments. An element p. E P(M)) is called distributional graph signal. The marginals of distributional graph signal p. are the marginal distributions N = {ws 1 S S n} w.r.t. the n coordinates of either St or R
Definition 1.
To understand why a distribution j is related to GSP, consider a step graph signal (resp. ordinary graph signal) æ in S" (resp. RR) It induces the delta distribution 8 in P(S") supported at æ. Its marginals are the delta distributions {5((1) 1 < < n}. Therefore, Definition subsumes ordinary graph signals special cases.
X,
4/
X.
01
X2
10
19
U2
Figure 2: We give an example of the marginals of a distributional graph signal. We notice that for XI,:- the probability weights are equal and hard to determine the arg max of the classes. Moreover, the weights of the 2nd class have large differences along few edges, e.g., (22, U3), (V3, Uz). These features make prediction unreliable. We propose solutions to such issues in this paper.
Distributional graph signals also occur naturally in GNN models (illustrated in Fig. 2 As in the previous subsection, let S be the set of all possible class labels of size m and M (R) be the space of n x matrices. For typical model M such the GCN, the last stage of the pipeline usually
3

---

consists of the following steps
(2) The i-th row X;; of X can be viewed the weights of probability distribution yux, on S. They do not directly give a distributional graph signal in P(S"). However, we shall interpret Ax {ux.,: 1 n} as the marginals of some unknown distributional graph signal, and ./x the main subject of study in this paper. In order to mimic the ways smoothness of graph signals is used in GSP, we introduce an appropriate notion of the total variation of distributional graph signals in the next section.
Logits: O
Mn,m (R)
Sollmax:d
X 6(O) Mn.m
arg TILX
Output labels: c S".
3 REGULARIZED GRAPH NEURAL NETWORKS
In this section, we study smoothness and non-uniformity properties of distributional graph signals in Section 3.1 and Section 3.2 respectively. Each of these subsections yields an expression that we want minimize. They are combined in Section 3.3 to give the proposed regularization term.
3.1 TOTAL VARIATIONS AND LAPLACIAN REGULARIZATION
The goal of this subsection is introduce and compare different notions of total variation associated with distributional graph signals and their marginals that leverage signal smoothness. First all, given μ E PMM) for M- S R" its total variation can be modified directly from (1 as follows:
T(p) Eawp T(x)
Σ d(z((),z(j))² du(x)). (EER)))E
where d is the metric on $ or IR.
However, many cases of interest such as GNNs, only marginals of some μ are observed (cf. Section 2.3h. We want to define total variation in such situation as well. We borrow ideas from the prototype of the Wasserstein metric (Villani 2009), which we recall now. The notations and assumptions follow those of Definition
Definition 2. For f1, P(M)), the Wasserstein metric W between 11, is defined by
W ((11)2) rel(er.
inf
inf d(z,v)² dzxxx)
where [(p1, U22 is the set couplings of p1, 12, i.e., the collection of probability measures M x M whose marginals are μ1 and (22, respectively.
can be verified that :(.:) indeed defines metric on P(M) (see Villani 2009 )). As special case, if & and by are delta distributions supported on xr E M, then W(Oz 0g) d(r. y). -)).10 The key insight is that we want to take infimum over all possible distributions given the prescribed marginals; and whatever we define, it should subsume
[ special case for a collection of delta distributions.
Definition 3. Given N {14: isisi n) with μ4 E P(S) (resp. ls E P(RR), for 1 < then the total variation of N is defined as:
T(M)= inf T(p), HEl((M)
where I(M) is the collection of all distributional graph signals in P(S") (resp. P(R")) whose marginals agree with .Y.
Though important theoretical tool, the Wasserstein metric is usually difficult to compute explicitly, the other hand, if G is the graph with nodes connected by an edge and . (#1, (2), then T(M) W (p1, 22 As consequence, finding the exact value of T(M) can be challenging. Therefore, we next introduce approximations that can be more readily computed.
'To simplify the presentation, assume that all models considered have the intermediate softmax step, though some implementations omit this part using the fact that the exponential function increasing.
4

---

For M = (1: 1 1 siin)) n) with μ4 E P(S), let μ4, E R" be the graph signal of probability weights of 8, i..., (1) the probability weight ii at s. We can also stack these signals as a matrix X whose columns are μ4, Based the GSP version of total variation (cf. ( we introduce two more versions of total variation that are easy to compute.
Definition 4. Given N = {m 1 S S n) with μs E P(S), we define the ll and l versions of
total variations as:
= E (emee)E (1) |t,( and
-( Eieneye - (pe))) = Tr(X x xy) where Tr is the matrix
trace.
The complexity of computing either Ti or T2 is most O(S)) and it involves only matrix multiplication for Tz. In addition, T, 'I and Tz satisfy the following relation.
Theorem 1. Given N {ur : = i = n) with pa E P(S), we have
T2(m)) S ((() S (T(M).
Moreover, 2T if is a tree.
The discussion and proof of we expect ((AF) to be small for some N, then so are necessarily (i(V) and (2( In view of computation cost, mainly use To in the design of the regularization model in Section 3.3 Note
general result can be found in Appendix D
The upshot is that if
that this is analogous to the Laplacian regularization in GSP.
3.2 NON-UNIFORMITY
As discussed in Section 2.3 a base GNN model may output matrix X (in (2), with associated Nx = {,x,; < i < n... For node classification problems, it is desirable that there is less ambiguity in the decision for each node so that one can pinpoint the correct class label. Mathematically. this requires that each ,xx; deviates from the uniform distribution (B() on the finite set of label classes S. measured by the Wasserstein metric W (ux (S)). The following result proved in Appendix D
Lemma 1. For a fixed sequence of non nos-iivitivve numbers (a:)1sisn there is a constant C independens of X such that
DX)
Σ a.W(,,,. Isisa
(5)
where D is the diagonal matrix with diagonal entries (as)isisn Moreover, Tr(X. ( S Tr(X DX)= S Tr(X. u DXx), where X, is a matrix with each row a one-hot vector and X,, is the matrix with each entry 1/|8].
As want each μxx; to deviate from the uniform distribution, the right-hand side of (5) should be made small (as negative possible). This is ensured if the proxy Tr(X DX), which is easy to compute, is small. Moreover, we notice that X, (resp. (..p.XX)) corresponds to uniform (resp. 8) marginal distributions. The second half of the statement suggests that minimizing Tr(X DX) may drive marginals, i.e., rows of X, to comply with non-uniformity. Numerical experiments Section 4.2 support that this proxy works well. We this term in conjunction with Tz introduced in Section 3.1 in our proposed regularized model.
3.3 THE LOSS FUNCTION WITH REGULARIZATION
Suppose we are given a base GNN model, denoted by M. Let Fb be the matrix of input feature vectors and θ be the parameter space for M. Assume M has loss function L.M, and the model is set to solve the optimization problem mingee LM (F,0).
Consider the steps given in (2. We have X ((O) viewed matrix of probability weights. For
regularization, we introduce another loss Cn to supplement L Sections 3.1 and [.2 suggest that Co
should consist of two parts Lo L1 L2. The loss L1 (cf. Definition 4 related to the smoothness
5

---

of the distributional graph signal X and takes the form (X = Tr(X =
. On the other hand, L2 prevents the distributional signal from being uniform and can be explicitly expressed C2 (x) Tr(X DX) for suitably chosen negative semi-definite diagonal matrix D (ef. Lemma I. Summing up L1 and L2, we have (x(X) Tr (x (Dg Ag + D)
X))
In our experiments, we take D I - Dg and obtain the easily computable loss
(x Ir (x (In X))
In summary, if we express the output of the second last layer of M as O (F 0) of input F and model parameters 0, then the regularized model R-M of M solves the optimization:
(6) where the coefficient is tunable hyperparameter and denotes function composition. In the regularized model R-M, we do not make any other changes to the based model M apart from using the new loss function LR.M during training. A schematic illustration is shown in Fig. (a).
min (R (F,0) 8E6
min (M 0) + n Lolø 1b F, 0)), #EB
Base model M
R-module
Cxll
X
mx
Le(-)
Co(
((X)
R-M
(a)
(b)
Figure 3: This figure illustrates in (a) how R-M is constructed upon the base model M, and in (b) an R-module that can be used at different places in GNN models.
3.4 FURTHER DISCUSSIONS
Most regularization methods introduce penalty to supplement the base model loss. For example, in the recent work, P-reg (Yang et al. 2021) proposes to apply propagation matrix (c.g., the normalized adjacency matrix) the output features. The model penalizes large discrepancies, measured by a metric such as squared error distance, between the original and transformed features. In LEreg (Ma et al. (021), intra-energy and inter-energy losses are introduced. Both variants of the total variation (]. The novelty lies in introducing a "merged graph" with each node representing a whole label class. All these works related to the smoothness prior used in GSP theory (Section 2.1. In this paper, we take fundamentally different view of graph signals by treating a distribution as signal. This allows a principled and straightfowwad adaption of existing GSP approaches, as long as we have suitable notions of the signal's 's total variation. Moreover, non-uniformity does not have counterpart for ordinary graph signals, which are essentially delta distributions.
Compared to GSP as well as other regularization methods such as P-reg and LEreg, a salient feature of our method is that the matrix I, Ag in Lo general not positive semi-definite. Therefore, the infimum of Lo(X) can be - if the domain of the entries of X is unbounded. This is another reason why restricting to distributional graph signals is essential.
The proposed regularization is primarily for node classification distributional graph signals can be interpreted as the likelihoods of class labels. However, the method can be extended to other tasks through an R-module (Fig. 3 (b)) that consists of the following steps:
Apply ò (c.g., softmax) that turns feature X into matrix of probability weights ((X). * Pluu ((X) in the loss n/x Lo with tunable coefficient n1x-
Given base model, multiple R-modules can be inserted at different places of the model pipeline, and all the losses are combined with the original loss of the model. The insight is that useful node features for graph learning tasks should be inherently associated with smooth and non-uniform distributional graph signals. We demonstrate this approach with link prediction and graph classification tasks in Appendix

---

4 EXPERIMENTS
In this section, we verify the empirical performance of our proposed regularization method based on both Euclidean and hyperbolic GNN models. We consider node classification under both transductive and inductive settings. The datasets used include Cora, Citeseer, Pubmed, (Amazon) Photo. CS, Airport, Disease, and PPI (Sen et al. 2008 Namata al. 2012 Zhang & Chen 2018 Shehur et al., 2018: Fey & Lenssen | CChami et al. [2019] Szklarzzk et al. (016). Their statistics are given in
Appendix A For our regularization method, the source code is provided in Appendix [ No further
tuning of the base model is needed. We compare with base models and benchmarks in Section and
with variants of our model in Section 4.2 Other graph learning tasks discussed in Appendix
4.1 PERFORMANCE ON NODE CLASSIFICATION PROBLEMS
4.1.1 TRANSDUCTIVE LEARNING MODELS
In this subsection, we consider transductive tasks, in which there is single graph containing both labeled training nodes and test nodes. The base models include GCN (Defferrard et al. 2016), GAT
(Velicković et al. 2018), GraphSAGE (Hamilton et al. 2017) (abbreviated as SAGE) and GraphCON (Rusch et al. 2022) (abbreviated as CÓN). Implementation details are given in Appendix B
In addition to comparison with base models, as benchmarks. More specifically, we implement different versions of P-reg in (Yang et al. 2021). denoted by P-GCN and P-GAT' (based on popular GNN models GCN, GAT), and different versions of LEReg (Ma et al. (02T), denoted by L-GCN and L-GAT. The parameters are tuned as suggested by the respective papers. We also have the Laplacian method, denoted by LAP, in which the final class label e is used in the loss Lo. For fair comparison, tests are performed under the same hardware and software environment. Similar considerations are applied in Section 4.1.2
models having a similar structure to our approach
and 4.1.3
We also compare with BVAT (Deng& & Zhu 2019). GAM (Stretcu et al. 2019). and GraphAT (Feng al.] 202I) (the results are taken from literatures though they are unreported for Photo and CS). The test accuracies (in %) are shown in Table] [ In each row, best performers are highlighted in blue and red for our approach and benchmarks, respectively. An underlined entry means no noticeable performance improvement over the base model is observed. In general, we see that our proposed regularized models improve upon their respective base models with significant performance gain in many cases (cf. Appendix Eb. Moreover, our method can match up with or even outperform many benchmarks.
Table Transductive learning models.
Comparison hase models
Benchmarks
Ditset
GCN
R-GCN
GAT
R.GAT
SAGE
x RASAE
CON
R:CON
LAP
P-GUN
P-GAT
L.GCN
L-GAT
SWAT
GAM
GuaptA
83.4
K3.1
83.7
84.4
80.7
81.2
82.6
83.4
Coca
-1.07
10.24
10.61
10:40
10.65
10.31
11.12
11.52
10.88
1.0.61
1:0.65
10.45
10.75
11.01
=0.
10.60
70.6
73.6
68.7
70.7
70.6
72.0
73.5
74.6
70.7
70.4
70.3
71.1
60.0
73.9
72.7
73.5
Choseer
20.48
10.70
10.60
11:23
10.47
10.28
11.27
11.16
10.66
10.66
1.0.6
10.50
10.94
10.54
0066
10038
78.2
79.9
76.0
76.0
77.8
78.7
79.1
80.0
79.1
79.0
76.9
78.7
73.6
75.0
79.6
79.1
himmadd
-0.29
+0.40
+0.77
+0.77
+0.31
40.55
11.16
#1.18
+0.73
+0.31
+:096
+0.25
+0.47
+0..84
=0.63
+0.20
91.1
91.4
91.4
92.5
90.0
92.2
90.3
91.1
91.1
91.
91.8
91.5
92.0
Phoso
-0.55
+0.49
+0.41
+0.42
+0.36
2:0 42
#0.64
$0.43
+0.43
+0.20
#1.10
+0.28
+0.45
90.5
91.2
00.8
91.7
90.5
91.8
90.3
90.8
90.6
90.5
90.8
90.5
90.8
Cs
20.14
10.65
10.40
10.25
10.08
20.0 10
20.44
10.38
10.11
14.14
1:040
10.10
10.34
4.1.2 HYPERBOLIC MODELS
Base models considered in Section 4.1.1 generate embedding of nodes in Euclidean spaces. However, it is argued in works such as Chami et al. (2019) that for certain datasets such as Airport and Disease, one should consider embedding nodes in hyperbolic spaces and perform feature aggregation in the tangent spaces of hyperbolic spaces. Such a consideration is plausible as certain graphs are inherently hyperbolic (measured by d-hyperbolicity, see Bridson & Haefliger (1999)).
In this subsection for Airport and Disease datasets, we use hyperbolic versions of their Euclidean counterparts HGCN HGGCNCChami al. (2019), and HGAT Gulcehre et al. (2019) as base models. We also
7

---

consider the interactive model GIL that combines both Euclidean and hyperbolic approaches Zhu et al. (202). The comparison results are shown in Table 2 Again, we see a general improvement by using the proposed regularization, which yields performance comparable with benchmarks.
Table 2: Hyperbolic models.
Comparison w/ base models
Benchmarks
Dataset
HGCN
B-HOCN
ROAT
R-HGAT
Airport
88.8
89.3
89.9
91.0
90.3
91.4
88.8
58.9
90.0
68.7
89.7
#1.42
20.83
#1.63
#2.12
1:139
Discase
91.3
92.1
91.2
91.2
92.1
11.04
+1.00
#1.24
#1.31
#1.52
#1.52
+1.01
+1.07
#2.14
+0.90
#1.53
4.1.3 INDUCTIVE LEARNING MODELS
In contrast with transductive learning, inductive learning requires one deal with unseen data outside the training set. For example, in the PPI dataset, different graphs correspond to different human tissues and we test two of 24 graphs that are unseen during training. Though the citation datasets Cora, Citeseer, and Pubmed are for transductive learning, we modify the datasets following Mishra et al. (202T) that use the induced subgraph training nodes during training. During validation and testing, use induced subgraphs of validation nodes and testing nodes with training nodes, respectively. The nodes that are being predicted are unseen during training.
The base models are GCN, GAT, well as GraphSAGE that is primarily designed for inductive learning tasks. The performance comparison between the base models and their regularized versions is shown in Table The conclusion agrees with those observed in the previous subsections.
Table 3: Inductive learning models
Comparison w/ base models
Benchmarks
Dutaset
Cora
72.7
73.2
70.6
72.0
72.8
73.1
72.8
73.4
72.8
73.8
72.3
11220
11.77
40.75
4.33
Citeseer
65.5
41.33
11.27
#2.37
$2.18
41.31
4:115
:10.88
4:192
4.1.4
4.2.5
4:1.8
Pubiedd
73.2
73.8
72.8
73.8
73.3
73.5
73.5
73.5
73.4
73.4
72.9
1..0
+0.95
#1.01
#1.15
+0.90
+0.81
+1.52
+1.19
$0.85
+1.49
+1.42
PPI
70.2
71.3
97.6
98.2
72.6
72.6
70.8
69.7
98.0
60.8
98.2
+2.06
#0.51
#0.54
+1.4
#0.12
4.2 ANALYSIS AND ABLATION STUDIES
We analyze our model with R-GCN, which has significant gain as compared with its base model (cf. Ip. The graph Go (Vo, Eg) is the main connected component of Cora. Specifically, we want to study whether R-GCN indeed generates distributional graph signals with desired properties. For smoothness (cf. Section 3.I.. we have interpreted earlier ((O) of the output features of O as weights of marginal distributions. For the column di ((O).. we take the subvector indexed by Vo, then normalize and denote by æ (analysis of other columns are Appendix G). We compute its Fourier transform à and inspect its high-freque fighfrreqeenc components. We show 2 for different epochs in Fig. 4 We also show the spectral plots for the last epoch (epoch 200) of GCN and of the signal of (normalized) ground truth labels. We see clear shrinkage of high- grequurryy components for R-GCN (epoch 200).
For non-uniformity (cf. Section (.2), we collect in the set KR-GCN (resp. IKGCN) the probability weights for all the label classes and nodes, i.e.. 18956 entries of ((O) for epoch 200 of R-GCN (resp. GCN). unnfomiforntty suggests that KR-OCN contains less values near the average 1/7 and more values near 1, as compared with KOCN. To verify, we compare [KROON n [1/7 c1. 1/7 e1] with [Kaey n [1/7 e, 1/7 + e]]. and KR. n [1 E2 1] with [KaNN n - 62, 1]]. The plots for
different choices of (small) é1, 62 are shown in Fig. The results agree with speculation.
8

---

R-GCN (epoch 0)
R-GUN (epoch 20)
R-GUN (spels 120)
0.5
0.5
-0.5
-0.5
-0.5
1000
500
1000
1500
2000
2500
Index Erequency components
freqpentccy cocsponents
Frequenccy commonenns
II GCN (epoch 200;
GCN (epoch 200)
Ground truth label (Coca)
0.5
0.5
0.5
-0.5
-0.5
-0.5
1000
500
1000
1500
500
1000
1500
2500
Indes of Erequency components
Index of frequenccy comiponents
Index of Frequency componeens
Figure 4: Spectral plots of (normalized) signals of probability weights and ground truth labels.
Weights bebwaam 1/7 and 1/7
Wrights large thet 1
1503
2000
GUN
Suaber of lusvaaees
Number of LosCOUEE
6000
1000
4000
61
Figure 5: Number of instances of output probability weights within a given range.
Next, we conduct experiments on different R-GCN variants to validate the effectiveness of the components of our model. Recall that the newly introduced loss La has two components Lı and L2, accounting for smoothness and non-uniformity of distributional graph signals. We introduce modifications of R-GCN as follows: (a) RI-GCN: we only retain L, the loss; (b) R2-GCN: we only retain C2 in the loss, and (c) R3-GCN: input O directly in the loss without applying d. In this case, the entries of are not bounded, we only keep Li, which is positive semi-definite, the loss (cf. Section B.3). The results shown in Table 4 compared with its variants. This suggests that each component of R-GCN plays a useful role.
We that R R-GCN remains the most effective as
Table 4: Ablation study
Cora
Citeseer
Puhmed
R R-GCN
83.4
0.24
73.6
0.70
79.9 +: 0.40
R1-GCN
80.8 0.60
70.7 = 0.67
19.2:0..50
R2-GCN
82.0 +: 0.65
72.8 4 0.92
79.5 +: 0.61
R3-GCN
69.6 1.75
64.5 1.79
75.7 0.57
CONCLUSION
In this paper, we introduce the notion of distributional graph signals and total variations that measure the smoothness of such signals. Based on this and the concept of non-uniformity, we propose regularization scheme that can be applied directly to enhance the performance many GNN models. The method is analogous to the regularization method of smooth signal prior in GSP.

---

REFERENCES
R. Ando and T. Zhang. Learning on graph with Laplacian regularization. In NIPS, 2007.
C. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
M. Bridson and A. Haefliger. Metric Spaces Non-positive Curvature. Springer, 1999.
Chami, Z. Ying, Ré, and J. Leskovec. Hyperbolic graph convolutional neural networks. In NIPS, 2019.
D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In AAAI, 2020.
S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovačević. Signal recovery on graphs: Variation minimization. IEEE Trans. Signal Process., 66117):460944424, 2015.
M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filterin. In NIPS, 2016.
Y. Deng, Z. Dong and J. Zhu. Batch virtual adversarial training for graph convolutional networks. 19Xiv:1902.09190 2019.
F. Feng, X. He, J. Tang, and T. Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Trans. Knowl. Data Eng., 33(6):4933-254, 2021.
W. Feng. J. Zhang, Y. Dong, Y. Han, H. Luan, Q. Xu, Q. Yang, E. Kharlamov, and J. Tang. Graph random neural networks for semi-supervised learning on graphs. In NIPS, 2020.
M. Fey and J. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR, 2019.
C. Gulcehre, M. Denil, M. Malinowski, A. Razavi, R. Pascanu, K. M. Hermann, P. Battaglia, V. Bapst, D. Raposo, and A. Santoro. Hyperbolic attention networks. ICI.R, 2019.
W. L. Hamilton, R. Ying, and Leskovec. Inductive representation learning on large graphs. In NIPS, 2017.
Ji and W. Tay. A Hilbert space theory of generalized graph signal processing. IEEE Trans. Signal Process., 67(24);6188 6203, 2019.
V. Kalofolias. How learn graph from smooth signals. In AISTATS, 2016.
Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
G. Li, M. Müller, A. Thabet, and B. Ghanem. DeepGCNs: Can GCNs go deep CNNs? In ICCV, 2019.
D. Liben-Nower and J. Kleinberg. The link-prediction problem for social networks. JASIST, 58(7): 1019-1031, 2007.
Luan, M. Zhao, X. Chang, and D. Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In NIPS, 2019.
X. Ma, Chen, and G. Song. LEReg: Empower graph neural networks with local energy regulariza- tion. In CIKM, 2021.
P. Mishra, A. Piktus, G. Goossen, and F. Silvestri. Node masking: Making graph neural networks generalize and scale better. arXiv:2001.075244 2021.
G. Namata, B. London, I. Getoor, and B. Huang. Query-driven active surveying for collective classification. In MLGG, 2012.
S. Narang, A. Gadde, and A. Ortega. Signal processing techniques for interpolation in graph structured data. In ICASSP, 2013.
10

---

H. NT and T. Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv:190S.09550, 2019.
K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
A. Ortega, Frossard, J. Kovačević, M. F. Moura, and Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proc. IEEE, 106(5):808-88)) 828, 2018.
T. Rusch, B. Chamberlain, J. Rowbottom, S. Mishra, and M. Bronstein. Graph-coupled oscillator networks. ICML, 2022.
Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification in network data. Al Mag., 29(3):93, 2008.
O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. In NIPS, 2018.
D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process. Mag., 30(3):83-98 98, 2013.
O. Streteu, K. Viswanathan, D. Movshovitz-Attias, E. Platanios, S. Ravi, and A Tomkins. Graph agreement models for semi-supervised learning. In NIPS, 2019.
D. Szklarczyk, J. Morris, H. Cook, M. Kuhn, S. Wyder, M. Simonovic, A. Santos, N. Doncheva,
A. Roth, Bork, and al. The string database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucleic acids research, 2016.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks.
In ICLR, 2018
C. Villani. Optimal Transport, Old and New. Springer, 2009.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In ICLR, 2019.
P. Yanardag and S. Vishwanathan. Deep graph kernels. In KDD, 2015.
H. Yang, K. Ma, and J. Cheng. Rethinking graph regularization for graph neural networks. In AAAI, 2021.
M. Zhang and Y. Chen. Link prediction based on graph neural networks. NIPS, 2018.
L. Zhao and L. Akoglu. PairNorm: Tackling oversmoothing in GNNs. In ICLR, 2020.
D. Zhou, O. Bousquet, T. Lal, Weston, and B. Schölkopf. Learning with local and global consistency. In NIPS, 2004.
Zhu, S. Pan, C. Zhou, J. Wu, Y. Cao, and B. Wang. Graph geometry interaction learning. In NIPS, 2020.
X. Zhu, Z. Ghahramani, and Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003.

---

A
APPENDIX: DATA STATISTICS
In Table
we provide statistics of datasets used Section
Table 5: Dataset statistics
Dataset
Nodes
Edges
Classes
Features
Cora
2708
5429
1433
Citeseer
3327
4732
3703
Pubmed
19717
44338
500
Photo
7487
119043
745
CS
18333
81894
15
6805
Disease
1044
1043
1000
Airport
3188
18631
4
4
PPI
Ave. 2373
Ave. 34171
B APPENDIX: MODEL IMPLEMENTATION
In this appendix, we provide the source code for the loss function Lg and the implementation of the regularization method. In addition, give details of the base models used. For the source code, assume Py Torch and the Deep Graph Library (dgl) are used.
In Fig. 6 we first import modules and packages (though not all packages used for the other code segments below):
Iaport torch
Iaport torch.nn nn
Inport torch.nn. funetionunet as
inport dgl
inport dgl.nn dglnn
fron dgt.data inport CorsGraphDataset, CiteseerdrghDaatsset, PubmedGraphDstasee
fron dgl inport AddSeLfLoop
inport scipy
fron scipy inport sparse
Tron scipy. .10
Import argparse
Inport numpy
Figure 6: Import modules and packages.
In "my_loss" function (Fig. 7 we implement the loss Co (cf. Section 3.3 For the inputs of "'m__lss"
"g" is a dgl graph, and "x" corresponds to O in Section 3.3
def..y. BL. los.(gg...).....o. wtw.os..tee.eaae..eeoeeeeeee wwt.sccaat.ad...coo a.d.x.A...0.. wtw.sttte.uuuuutt.... wutputt..oott..
prob F.softmax(x) EGonRute wtw.teeeeeeeeec.eeeeet wec.ioal.ggsttctuuee wwstcchutaaooss.... wwtp:/owoooto..ooooooooo www.aeelo...ceeaaatt....
nun_nodes g.number_od of oowooffoonooo__oooooeoo (__eddee____edd..._. __eiidd.ts. his.ppubbr..e www.eee..ooooooooooooooooooeeese wtt.aet....se.eeeeeeeeeee
adj g.adjacency_natrie balacency_natrxx_sccy((rre seruunn_eeeeeeeeee (dss=aatse..sstttt (float), (fLoat)_eibe,
Laplacian sparse.eye _ndes))
taplacian torch.fron_numg (taptacian. tearray float())
y torch.nataul (attuulttocc.aeee wwwp:aatttttttoooeeeeeaa (torch, transpose (probo (etpp___oo_____________ (.t)__aptaciann) .robb
torch. trace wwwppotteeetttoeo the. Less.leatttaaac.u..
y/nun_nodes nodes, _ww.le..cee.... wtw.rssuttt.......ooooee www.per.tt.ooommo
Figure 7: "im_loss" function.
Suppose "loss1" (computed using "loss fen")) is the loss of the base model, we compute "loss2" for Lo (Fig. M.. They combined as in (6). using the tunable coefficient "eta".
12

---

8.2, swe.fiieeeeeeiceeet
Lossi Loss_fon
Loss2 ny_ my_loss(g, logits) _etee..eee........ less wwt.seeeeeeaaeeeeeeee.e. Wwwtbeal 1 Ree.c
Loss Lossi=eta<loss2 #Ine 1oss of the reqularized podel
Figure 8: The regularization term.
As have mentioned in the paper, do need make any other changes to the based model. Details of the base models used in Section are given as follows (links are for published works and not associated with the authors of the current paper):
In Section Citeseer, Pubmed are from examples/pytorchh For packages, we use torch 1.12.1 and dgl 0.9.0.
based models for GCN, GAT, SAGE and the datasets Cora, com/ dmlc/ dgL/tree/mmttter
In Section and CS are from https:///ithut: com dml c/ /tt/d/g///teeeee 7. x/eammpexxx//////eaoom.p
based models for GCN, GAT, SAGE and the datasets Photo
pytorch For packages, we use torch 1. 1.10.2, dgl 0.7.2 and cuda 10.2.
In Section 4.1.1 the base model for CON is from /tt http::////..uuu.oooooooe rusch/
GraphCON For packages, use Torch-geometric 2.0.4, Torch-scatter 2.0.9, Torch-sparse 0.6.14, Torchdiffqq 0.2.3, and torch 1.10.1 py3.8 cudal 1.3 cudnn8.2.0_00
In Section 4... the base models are from htttp::
GIL For packages, we use Torch 1.8. 1ccll01 Torch-cluster 1.5.9, Torch- 1.3.0, Torch-scatter 1.3.0, Torch-sparse 0.4.0 and Torch-spline--conv 1.2.1.
In Section 4.1 the base models are from from http://gg.hhiiooooooooooooo/oa// For packages, use torch 1.10.2, dgl 0.7.2 and cuda
com cm http://mmmmmcm/ggg////////
0. 7.x/ www.peese/pptttteeeeee 10.2.
Detailed model setups are contained in the respective github links, For example, according to https 7/qithub. com/ cmlc
trrin.pp.. py for GCN and datasets Cora, Citeseer, Pubmed, two convolution layers with 16 hidden units are used. The dropout rate is set to be 0.5. Adam optimizer is used with the learning rate 1e 2 and weight decay 5e 4. On the other hand, according to ht : /ttp://gtttttt /ggthu...uu... com/ dmlc/ dgl/ / /bl//olle htlp///bbb/// examples wwwytorrcggaattteeeee
haab/masterr/ wtw.er/eeeapplseeeeeeeeeee
ob/obb/mma hwwpo/oossteeeeeeeeeeeeeeeeeeeee masttr///eeeeee/memmm/ py for GAT and datasets Cora, Citeseer, Pubmed, two graph attention layers with 8 hidden units and 8 heads are used. The dropout rate is set to be 0.6. Adam optimizer is used with learning rate 5e 3 and weight decay 5e 4. As the regularization does not change the base model, the exact same setups are used.
In 6 provide the values for the coefficient 7) used in Section (irrelevant fields filled with "-"). We briefly describe the strategy of choosing We fix a lower bound (= 10-9) and an upper bound (= 1) for 7), both are loose. We perform search analogous binary search within the range based on validation performance. The scaling factor for the search can be different from 2: we large scaling factor identify an interval with significant performance improvement and then perform a fine-scale search within the interval. If no performance improvement is observed within the initial range, then we declare the regularization does not show improvement for the given base model.
Table 6: Choices of
Cura
Citeseer
Pubmed
Photo
Airport
Diveuse
Cora (ind.)
Citeseer (ind.)
Pubuned (ind.)
PPI
R-GCN
0.001
R-GAT
0.25
0.25
0.02
0.05
0.0005
0.01
0.05
0.0001
R-SAGE
0.2
0.2
0.02
0.02
0.1
0.01
0.1
0.001
R-CON
0.001
0.01
0.005
R-HGCN
0.01
0.001
R-HGAT
0.01
0.001
R-GIL
0.01
13

---

C APPENDIX: LINK PREDICTION AND GRAPH CLASSIFICATION
We follow Section 3.4 apply the proposed regularization method link prediction and graph classification.
For link prediction (Liben-Nowell & Kleinberg, 2007 Zhang & Chen 2018), we want to predict whether two nodes in a network are likely to have a link. Suppose a base GNN model for link prediction given. We insert an R-module ( (b)) the last node feature matrix in the model pipeline. The loss of the R-module is added directly the original loss. We test on Cora and Airport datasets with base models: GCN, GAT, HGCN, and GIL. The results are shown in Table Except for HGCN, that the regularization can enhance the performance of the base models.
Table 7: Link prediction. The best performer is highlighted in blue.
GCN
R-GCN
GAT
R-GAT
HGCN
R-HGCN
GIL
R-GIL
Cora
88.1
88.4
88.8
89.1
93.3
93.3
91.1
94.6
1.00
1.20
#1.41
1.26
40.43
+0.43
13.4
47.99
Airport
93.0
93.2
93.6
93.6
97.6
97.6
97.3
97.7
10.44
10.37
00.61
10.61
10.13
10.13
13.73
13.27
We next consider graph classification. For such task, want to determine the class label of each graph in dataset containing multiple graphs. Graph classification is closely related to the theoretical problem of graph isomorphism test, and GIN (Xu al. 2019) is GNN model that explores such connection. We use GIN and the variant GIN2 with the learnable importance of the target node compared to its neighbors,
base models. Similarly to link prediction, we insert an R-module (Fig. (b)) to the last node feature matrix in the model pipeline. We test with bioinformatics datasets MUTAG and PTC YYanardag & Vishwanathan 2015)), following the protocol described in (Xu et al., 2019) and report the 10-fold cross validation accuracy. Comparison results are shown in Table 8 The regularization indeed works for both models.
Table Graph classification. The best performer highlighted in blue.
GIN
R-GIN
GIN2
R-GIN2
MUTAG
88.7 + 8.80
89.9 + 6.40
86.7 + 6.77
89.3 - 7.98
PTC 64.6 + 8.53
64.8 + 5.91
64.8 + 9.37
66.3 + 9.63
D APPENDIX: PROOFS OF THEORETICAL RESULTS
In this appendix, discuss and prove general result that implies Theorem In addition, also prove Lemma [ We start with a computation of the Wasserstein distance.
Suppose $ {si...., Sm is a finite discrete set and d is the discrete metric on S. For p, E P(S), let (u(s:)) and (v(s)))ssiss be their respective probability weights.
Lemma 2.
1 Σ (u(ss) v(8))) Isism
3
14

---

Proof. L I5assm
be in [(,, v). We have
Σ
Σ
( 8y)d(st, 8,)²
1s m mm
Σ
Σ
(5)
Isism ISffism
E
Σ 159sm
(8) (8),
(7)
Isism
Σ i3imm
(u(s;) (8),
Σ (u(s:) min(m(s:)) m
As W(,, 2)2 is defined by taking the infimum of the left-hand side over all y E T(u, v), we have W), 2 Eisism (u(s;) - min(u((;;,, v(s;)). By the same argument, we also have W(,,v)² 2 Eigism (v(si) min(p(s;), (s:)). Summing up these inequalities, we have Σ (u(s;) (s:) (nin( 1sism
2W (2,
Σ (m(s)) - (v()))
msigm
Therefore, to prove the lemma, it suffices to show that there is 7 such that 7ss, si) min (H(8i), u(:)). For this, we prove a slightly more general claim: if non-negative numbers (zx)igigm and (y:)igigm satisfy Eisigm I; = Eisism Vi = a, then there are non-negative (#i.) such that Eisism Fij = Iz, 1 S m. Eisism Fi Mi S j S m, and Rr, = min((;;,;))) S isim m.
We prove this by induction on m. The case for m is trivially true by taking 21,1 = 21 91 For m 2, without loss of generality, we assume that 2 y1 and S y2. Then we choose 21,1 y1. 22,2 = 222, æı.j = 0, < j S m and 212 = 0, < i sequences of neganege numbers to 22 - 1/1 By the induction hypothesis, we are able to find non-negative (zf.))sst.smm for the two new sequences length m each. It suffices to let 21,j = 2 for or j > 2 and
< m. As a result, we form another two y1, 23. ... and 1/2 22, 1/....... 3m with both summing
R1 = 2 for (illustrated Fig. 9h. This proves claim and hence the lemma.
O
0
4111-11
Fj.1
0
0
Figure 9: The relations between žiạj and =1.3"
To state and prove a general form Theorem we need to introduce a few more notions. We fix marginal distributions N = {μ: < i n) with μa P(S). For any pair of nodes and f and s E S, define
Pis(s) (1/(s//44 if (s))) & (s(s) and otherwise.
(8)
15

---

More generally, if P ( v4)) is directed path 9 from Uig to Uai then
pp(s) = II (s).
05
is important to point out that pp can be computed directly as long as V is given.
In the graph G. suppose H is a spanning tree and Un is a fixed (root) node. Let Ey be the edge set of H and ' = E ExE.. For each edge and Us (resp. vy). Moreover, vo is an endpoint of P: n Py. and let eg be the other endpoint of P; n Pj- Denote by Q: (resp. Q2) be the direct path (on H)) from Eg to vs (resp. 0ÿ) (see Fig. 10). We introduce
(v,, v;), let P. (resp. Pÿ) be the unique path H connecting vo
(s)(5) (4(5) (s(s) 2px (s)pp,())pQ) (s).
Definition 5. Define
TH,
Σ
Σ (x).
sE3 (M)
= (1)) E E
H.
Q
Uj
Uk
1o
Figure 10: An example of paths Q; and Qj-
We can compute the special case where G = 7. is a tree. Notice that for an edge e = (0,, U3) E En
directed from vs to vj. then on i2 and Q: [ui]. J. Qj and po, (s) 1. If (=(s) 2 1y((8) (8), then (x)PP) (8) (s)p2, (+) = (x;(s) (1(())/ (s) = 2p3 (8). Hence, we have
p=(s) + (s) - 2 (s) PQ. (s) (s) = ms(s) 145()) = (pi(s) - ms(s)] The case (4(s) < M (s(s) (s) is similar, and in summary
(.)(s) (s(s) + (s)(s) (s)(s) (s) lui(s) Hs(s))
(10)
Therefore, for any vo, we have
(A) = Σ Σ [H((s) - my(ss)
sE3 (N.R))ES
(11)
(.(t) m.(i) = T((M).
#ES (14.8))EE
where μt (i) is same as (s(s) (cf. Section 3.1
Following the notations in Section 3.1 we have the following generalization of Theorem |
Theorem 2. For any spanning tree H. o and root node Up. we have
Ta( < & < (N.
Before proving the result, remark that although TH, (-F is defined in convoluted way, it can however be computed directly given .N H. and un- Therefore, the result gives computable upper and lower bounds of ((N).
16

---

Proof. As (p)(1) [s((5] - is trivially true that (2(3)) S ((A)).
To show (i( & (TA)) ) we first claim that T(A) = infper(or) T(p) is achieved for some No E (()). The map a T(M)= - R. H T(u) continuous. On the other hand, ((A) is compact subset of Euclidean space. This is because P(S") a bounded subset of Im" with the components corresponding to weights of the joint distribution. Moreover, I(-4) is closed because the condition to have the prescribed marginal distributions is a set of linear conditions. By the extreme value theorem, inf a is achieved for some f4 E ((,)). For each edge (vs, 15) E &, let jo,i.j be the marginal distribution of the pair Uy). The marginals po,s. are pa and bj at is and vy respectively. We have
T(X) = T(Ho)= =
/
Σ (OL.))EE
(xx(),x((i)) d2o(x)
d(x(1), x(())) duo(ar)
(MEN))EE
Σ
d(y(i), x()))² (3)
Σ
W(ps;
(0L,))EE
Lem
2
Σ
mo(1) ps(ii 2 T.M)
(VG WEB
We now prove (T( S TH. (M). Given a spanning tree H and node Uo. we construct HHH I'(4) using ideas from the theory of Bayesian networks (Bishop 2006) as follows, We make H directed by requiring that each edge is pointed away from the (root) node up As consequence, each node has at most 1 incoming edge. Let x = (æ:) sign be the random vector with æ; the (random) label at e, For each directed edge (ve, U2) H. let uua E 144)))))) be a distribution that realizes W (us, p5),, which give conditional probability weights
P..j = (s,,(s,s') s'): s, E E = = { = x =) s, E S}.
By |Bshopp 2006) Section 8.1 (8.5), there is a distribution (at,en E ((()) such that its marginal for each edge (U,. vy) Ex j..j. For each edge Uz) E 8l, let pوa be the marginal of prr to the pair (w, v2). As jt, realizes W (pt, p.). by Lemma 2 (s, s) = min(p,(s). p2 (s)) for each E S. In particular, ss. = (s) (cf. (8)). More generally, if P is directed path in H from U; to Uy, then the following inequality holds
(is(s,s) 2 pp(s).
(12)
According to the definition, we have T( S (HUN,N)) SEn + Se:. The summand
Sex Σ
d(v((), de),s(y)
(EL,)))ERH
is the summation over the edges of Ex, while
/
Sg. Σ
(p),,
the summand over 8l. For Sen, we have seen that for each edge (v,, E En
f d(y(1), v())² (v)
(i(ss) p15(5)
2
#ES
10
(Hi(s) + +1y (8) - (s)(s) (s)),
2
17

---

where the hight-hand-side is the term (s) (cf. ( that corresponds to (0t, uy) in Tu, (MM).
Consider (oy, 0/) E E' and we first notice the following identity:
2 f d(y(i), dul, (3)
Σ SEB
(s(s) Ms(ss 2111
To show the summand is bounded by (s)(s),, it suffices to show 14,, 8) is bounded below by Pq. (S) (s) (s), with eg and paths Qi Qj be in (9) We estimate using the construction of Hi based on the method of Bayesian network (on directed 7() as follows:
(8,) 2 p(a; = 8, U = 0 = 8)
=p(x; = 8, 2 = =8 ah = (8)
pk.ils, s)px s)mu(s)
(s) (s)
For the last equality, we use the fact that QnQQ, = {ux ): and hence 2,, 2, are independent given æ by the Bayesian network construction. The last line follows from (2)). Consequently, the inequality that (MN S TH. follows.
If we examine the formula of vno (-F (by changing summation order), it can be decomposed into two parts L(gg,))EE and ((s,,))e The former is essentially Ti of N on the tree H. This is the reason that Theorem implies Theorem Formally we have the following.
Proof of Theorem 7 It suffices to prove the last statement for & being tree. As we have seen in [I1 that if & a tree, then TH, (JV (TN). Therefore, Theorem 2 implies 2T( (T)) and hence Theorem
We end this section by proving Lemma
Proof of Lemmal
| Using Lemma
we estimate
2 Σ
a;W U())
Isisn
Σ
4 Σ
X
<
Σ
4i (Xi.
2
S
1siSn
15/5m
1SiSa
15/5m
Σ
Σ
x
2 Σ
Σ
X
i.j
+
Σ
1Sish
15jsm
ISiSB
15/SM
15i50
15j5m
=T((X DX) -
Σ
0
ISiSh
ISiSh
=Tr(X DX) 1
Tr(D).
Therefore, 2 Eisisa a.W independent X.
W (ux U())
T DX) + with C' - Tr(D), which is
The last statement of the lemma follows from the simple fact that for each 1 S í S n, we have
Σ
x 1
2
15j5m
15/5m
18

---

E APPENDIX: SIGNIFICANCE OF THE PERFORMANCE
In this appendix, we analyze the significance of the performance (in Section 4.1 of the proposed regularization method with the following setup. Suppose we have models A and / with A having higher average accuracy. To determine if the difference is significant, we perform the hypothesis test for the null hypothesis that the difference in accuracy between model A and B has 0 mean. We compute the p-value. The smaller the p-value, the higher the confidence to reject the null hypothesis and to conclude that model has a better performance. p-value less than 0.05 typically considered statistically significant.
In Section 4.1 we have 38 comparisons between regularized models and based models. We perform the tests described in the previous paragraph and record the p-values. The boxplot of the p-values is shown in Fig. [ indicates that most cases, our proposed regularization significantly improves the respective based models. On the other hand, there are 11 comparisons between approach and best benchmarks. We again perform the hypothesis test for each comparison and record the p-value. The boxplot of the p-values shown in Fig. T1 We that in many cases, method significantly outperforms the benchmarks.
0.8
0.7
0.6
p-values
0.5
0.4
0.3
0.2
0.1
Compare w/ base models
0.8
0.7
0.6
p-values
0.5
0.4
0.3
0.2
0.1
0
Compare w/ benchmarks
Figure 11: Boxplots of p-values. In each plot, the dashed line marks the 0.05 threshold.
F APPENDIX: MORE ON RELATED WORKS
Though it is argued in Yang al. 202 and supported by evidence in Section 2.2 that Laplacian regularization may have its draw backs, it has achieved a certain degree of success in earlier works Zhu al. (2003); Zhou et al. 22004); Ando & Zhang (2007). These methods are based the insight that neighboring nodes are likely to have the same labels. In the language GSP, they intend to leverage the smoothness of the class label graph signal.
19

---

On the other hand, though graph signal smoothness has been fundamental in both GSP and GNNs, the negative effect of mmoothig has also been examined (NT & Machara 2019 Oono & Suzuki )020 and models are proposed to alleviate it. For example, apart from the more recent works such as Yang et al. (202)) | Ma et al. (202T) that have already been discussed in detail, PairNorm proposed in Zhao & Akoglu u (020) encourages the similarity between connected nodes, and the same time adds a negative term based on distances between disconnected pairs. MADReg in CCen et al. (2020) proposes to use step size limits to make the graph nodes receive less interference noise. Inng et al. (2020), randomly dropping nodes is proposed to reduce the convergence speed of over-smoothing. Adding skip connections is also introduced in Li et al. (2019) Luan al. (2019).
In our paper, we take a different point of view by not considering the smoothness of ordinary graph signals. Instead, we speculate that properties such as smoothness and non-uniformity of distributional graph signals may play important roles. Moreover, requiring distributional graph signal to satisfy non-uniformity partially prevents the unfavorable situation that many connected nodes have similar marginal distributions that are approximately uniform. This can be viewed as countermeasure to over-smoothing intrinsically contained in our approach.
G APPENDIX: ADDITIONAL PLOTS FOR MODEL ANALYSIS
We supplement Fig. by showing spectral plots of signals of probability weights (OO).., S I for the Cora dataset. The index corresponds to the i-th label class. From the plots, observe that during the training of R- R-GCN, the geghffreuencc components indeed shrink for all the label classes. Compared with GCN, the last epoch of R-GCN has smaller high-frequency components for the 3rd and 5th label classes
R GCN (epodi 0)
GCN (epoch 20)
It GCV (epoch 120)
14
-0.5
-0.5
-0.5
500
1000
1800
2000
2500
500
1000
1500
2000
2500
500
1000
1800
2000
2500
Todex frequeecy competennss
Index
frequency components
Tndex of frequeccy compotennts
R. GCN (opoch 200)
GCN (epocls 200)
0.5
-.55
500
1000
1600
2000
2500
500
1000
1500
2000
Indee Drequnccy compocents
Enequeccy componets
Figure 12: Spectral plots of (normalized) signals of probability weights for the 2nd label class.
20

---

R-GCN (epock
B-GCN (opoch
R-GCN (epoch 120)
0.5
0.5
500
1000
1500
2000
2500
500
1000
1500
2000
2500
500
1000
1500
2000
2500
Toolex of Erequesyy compooeils
Lncles of (requeicy composente
Iodes of Erequesacy comperenia
H-GON (spoch
GUN (spoch
0.5
0.5
500
1000
1500
2000
2500
0
500
1000
1500
2000
2500
Index of Erequency compoceents
Todex of trequecacy componemts
Figure 13: Spectral plots of (normalized) signals of probability weights for the 3rd label class.
R-GUN (epoch 03
H-GCN jspoch 20)
R-GON (spoch 120)
-0.5
-0.5
-0.5
1000
2000
2500
Erequeccy compenennss
Erequency components
Erequency components
It GCN (epoch 200)
GCN (epoch 200)
0.5
0.5
0.5
-0.5
2000
500
1600
Index of Erequenccy compocents
Iodex:
Erequecccy components
Figure 14: Spectral plots of (normalized) signals of probability weights for the 4th label class.
0)
(epoch 20)
R.GCN (epoch 123)
of www.thogoeeaenoooooooooooooo
500
1000
1600
2000
2500
500
1000
1500
2000
2500
500
1000
1600
2000
2500
Todles trequescy compenents
Index Erequency
Indes of Erequency
GCN (epoch 200)
GCN (epochs 200)
-0.5
-0.5
500
000
1900
2000
2500
500
1000
1500
2000
2500
Indls of Erequeccy compouents
Todex
Erequecccy compenentss
Figure 15: Spectral plots of (normalized) signals of probability weights for the 5th label class.
21

---

RAGON tepoch 0)
R-GON tspoch 20)
R-GON (spoch 120)
-0.5
-0.5
-0.5
frequeeyy companimts::
frequmcy composents
Frequimy compotemts
R-GCN (spoch 200)
OCN (epocki 200)
0.5
0.5
0.5
0.5
1000
500
Index of Crequency compoсetts
Todex Erequeccy componeii
Figure 16: Spectral plots of (normalized) signals of probability weights the 6th label class.
R-GON (epoch 0)
R-GCN (spoch 20)
R-GON (epoch 120)
-0.5
-0.5
-0.5
hrequecy competeents:
frequency components
heequiccy components:
R.G (opoch 200)
GCN (epoch: 200)
0.5
0.5
005
-0.5
2000
Ehequomcyy componints
Enequecccy componets
Figure 17: Spectral plots of (normalized) signals of probability weights for the 7th label class.
22


Reviews:
[{"review_id": "FNSp_mR-uM", "reviewer": "Reviewer_Eo3M", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new regularization for Graph Neural Networks. Signal smoothness in cases if discrete node classification task is hard to define. Instead, the paper proposes to look at the distribution of the class labels at per node level and define smoothness on the distributional graph signals. The proposed regularization additionally ensures that nodes do not end up having uniform probabilities. The paper then proposes to use the regularization at different layers of a GNN model so as to be able to extend it for tasks beyond node classification. ", "summary_of_the_review": "The paper proposes a regularization term for Graph Neural Networks. The paper proposes to define graph distributional signal and define a smoothness on this signal, however, the final proposed form does not seem to be very different from standard regularizers. Secton 3.1 does not seem to actually make any substantial point. Also, it is unclear how Section 3.3 follows from Section 3.2. The final proposed regularizer seems to have come from air, based on very thin justifications. The gains reported in the experiment section are well within a single standard deviation of the best baseline. So it is unclear whether the observed are statistically significant or not.\n\nBased on these, I am inclined to mark this as marginally below acceptance.", "strength_and_weaknesses": "# Strength:\n1. The regularization of a GNN is an important problem.\n2. The paper has some interesting ideas.\n***\n# Weaknesses:\n1. While the organization of the paper is fairly clear. The arguments are not easy to follow. \n2. The gains in the results are within a single standard deviation of the best baseline. It would be good to do a stat-sig test to see whether the observed gains are statistically significant or not.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "EKWL6S9TEl", "reviewer": "Reviewer_34XZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors proposed a regularization term that can be added to traditional GNN training. The regularization term incorporate the defined distributional graph signals, which is a probability measure defined over the node label space, and shows significant improvement when compared to baseline models without regularization in empirical results. ", "summary_of_the_review": "Overall, I think the paper's idea is neat and empirical results show it work nicely with different input data in various learning task. Given the simplicity and versatility of method, I would recommend acceptance of the paper. ", "strength_and_weaknesses": "Pros: \n- Provides a distributional view in the final softmax layer, which open possibility to add different GSP regularizations. \n- Theoretical analysis on the bound of total variations/losses. \n- No need to change the base model, and can apply to almost all existing framework. \n- Works on both Euclidean space and Hyperbolic space models. \n- Extensive empirical experiments with multiple baseline models in different real-world dataset. \n\nCons: \n- Selection/Tuning of \\ita is missing. \n- Does the method works on different input feature space (Euclidean and Hyperbolic), with only one total variance (or the two surrogate T_1, T_2)? Same for transiting from transductive to inductive learning, why would the assumption still be true if the underlying signal are coming from different/unseen space? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CbGrC46Tuy", "reviewer": "Reviewer_XoLJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper addresses the limitation that the graph signal smoothing framework only works on continuous values, and proposes the concept of *distributional graph signals* in order to support discrete node labels.\nThe paper generalizes some important notions in graph signal processing (GSP), i.e., smoothness and non-uniformity, to distributional graph signals based on the Wasserstein metric.\nThe paper also proposes a general regularization method based on the proposed concept to enhance graph neural networks (GNNs) for the semi-supervised node classification task.\n", "summary_of_the_review": "This paper provides an interesting and novel idea with good mathematical foundation. However, the work lacks a discussion of related work, and the experiments do not provide compelling evidence of the effectiveness of the proposed framework. The experiments need to be conducted more carefully with proper significance testing. Moreover, the experimentation should include more recent base models and richer datasets.", "strength_and_weaknesses": "**Strengths**:\n    1. This paper introduces the concept of *distributional graph signals*, generalizes important notions in GSP to the proposed frameworks, and constructs a novel graph regularization method, with a solid mathematical and theoretical foundation.\n    2. The proposed regularization method shows empirical performance improvements compared to the selected base models and outperforms other selected regularization methods.\n\n  - **Weaknesses**:\n1. There is no comprehensive discussion on related work. The paper lacks a section devoted to related work, but beyond this, the embedded discussion (in the introduction and experiments sections, for example) does not provide an adequate introduction to compared methods and does not explain how the proposed approach differs and offers advantages. Example works on regularization that could be included in a discussion of related work are [R1-R4]; pioneering works on graph regularization include [R5-R6]. But beyond this, the paper needs to position the proposed technique within the general landscape of node classification methods. \n\n 2. It appears that many of empirical improvements on the based model and outperformance over the benchmarks are not statistically significant. The paper mentions “noticeable” improvement, but there is no definition of this. There is no mention of testing to demonstrate a statistically significant improvement. In many cases the improvements appear to lie within 1 std, which doesn't augur well for the outcome of a carefully conducted test. \n\n3.    The majority of the experiments are on Cora, Citeseer, Pubmed and PPI. These are small datasets that have received too much experimental attention – methods are over-tuned to a limited number of datasets. The limitations of the datasets do not allow one to properly examine the expressive capability of the models. One cannot trust that a technique will provide improvement for general graph datasets if experiments are only provided for these datasets. There are now many graph datasets to choose from and most recent GNN papers perform experiments on a much richer set.\n\n4. The authors only verify the proposed enhancement method on the base models GCN, GAT and GraphSAGE (as well as GIN for graph-classification). All of these models were presented in papers published 4 or 5 years ago. The results would be much more persuasive if experiments were conducted with SOTA models as the base models. \n\n[R1]: Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling Oversmoothing in GNNs. In ICLR 2020.\n[R2]: Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and Relieving the Over-Smoothing Problem for Graph Neural Networks from the Topological View. In Proc. AAAI, 2020.\n[R3]: Yang, Z., Cohen, W. and Salakhudinov, R., . Revisiting semi-supervised learning with graph embeddings. In Proc. ICML, 2016.\n[R4]: Li, Q., Wu, X. M., Liu, H., Zhang, X., & Guan, Z. Label efficient semi-supervised learning via graph filtering. In *CVPR, 2019*.\n[R5]: Zhu, Xiaojin, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proc. ICML, 2003.\n[R6]: Zhou, D., Bousquet, O., Lal, T., Weston, J., & Schölkopf, B. Learning with local and global consistency.  In Proc. NeurIPS, 2003.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject