Year: 2019

Abstract:
Due to high utility in many applications, from social networks to blockchain to power grids, deep learning on non-Euclidean objects such as graphs and manifolds continues to gain an ever increasing interest. Most currently available techniques are based on the idea of performing a convolution operation in the spectral domain with a suitably chosen nonlinear trainable filter and then approximating the filter with finite order polynomials. However, such polynomial approximation approaches tend to be both non-robust to changes in the graph structure and to capture primarily the global graph topology. In this paper we propose a new Fractional Generalized Graph Convolutional Networks (FGCN) method for semisupervised learning, which casts the Lévy Flights into random walks on graphs and, as a result, allows to more accurately account for the intrinsic graph topology and to substantially improve classification performance, especially for heterogeneous graphs.

text: Due to high utility in many applications, from social networks to blockchain to power grids, deep learning on non-Euclidean objects such as graphs and manifolds continues to gain an ever increasing interest. Most currently available techniques are based on the idea of performing a convolution operation in the spectral domain with a suitably chosen nonlinear trainable filter and then approximating the filter with finite order polynomials. However, such polynomial approximation approaches tend to be both non-robust to changes in the graph structure and to capture primarily the global graph topology. In this paper we propose a new Fractional Generalized Graph Convolutional Networks (FGCN) method for semisupervised learning, which casts the Lévy Flights into random walks on graphs and, as a result, allows to more accurately account for the intrinsic graph topology and to substantially improve classification performance, especially for heterogeneous graphs.

heading: 1 INTRODUCTION
text: Adaptation of deep learning (DL) to graphs and other non-Euclidean objects has recently witnessed an ever increasing interest, leading to the new subfield of geometric deep learning. In particular, geometric deep learning is an emerging direction in machine learning which aims at generalizing the concepts of deep learning for data in non-Euclidean spaces, e.g., graphs and manifolds, by bridging the gap between graph theory and deep neural networks (see discussion by Bronstein et al., 2017; Monti et al., 2017; Monti, 2019, and references therein).
Many such DL approaches for non-Euclidian objects are based on the idea of performing a convolution operation in the spectral domain with a suitably chosen nonlinear trainable filter. As a result, node features are mapped into some Euclidian space. Next, graph filters are approximated with various finite order polynomials, e.g., Chebyshev polynomials (i.e., the ChebNet model family of Defferrard et al., 2016; Kipf & Welling, 2017), Cayley transform (i.e., CayleyNet of Levie et al., 2018) or the generalization of polynomial filters in a form of Auto-Regressive Moving Average (ARMA) models (Bianchi et al., 2019). However, deep learning approaches based on approximation with finite order polynomials tend to be non-robust to even minor changes in the graph structure and to largely disregard the local graph topology that often plays the critical role for learning on heterogeneous graphs. In contrast, as noted by Bianchi et al. (2019), one of the primary benefits of the ARMA filters over polynomial ones is that ARMA filters are not computed in the Fourier space induced by a graph Laplacian, and as a result, ARMA filters are local in the node space and enable to more flexibly and accurately capture the underlying graph topology.
In this paper we further advance this localized approach to DL on graphs and propose a fractional generalized graph-based convolutional filter for semi-supervised learning, which casts the Lévy Flights into random walks on graphs. As a result, our new Fractional Generalized Graph Convolutional Networks (FGCN) method allows to more accurately account for the intrinsic local graph topology and to substantially improve classification performance, especially for heterogeneous graphs.
The key contributions of our paper can be summarized as follows:
• we propose a new fractional generalized graph-based convolutional filter for semisupervised learning, which casts the Lévy Flights into random walks on graphs and, as a result, provides a more efficient exploration of the graph structure.
• we develop a new Fractional Generalized Graph Convolutional Networks (FGCN) method that substantially improves accuracy of node classification for graphs of smaller sizes and with a lower number of node features.
• the proposed architecture of FGCN uses two state-of-the-art operations – gated maxaverage pooling and residual block. The architecture has been shown to significantly improve the training convergence and model output stability.

heading: 2 RELATED WORK
text: Many earlier semi-supervised learning approaches on graphs, e.g., Gaussian mixture models, cotraining, harmonic function, and label propagation, employed only the label information (i.e., labeled instances) to train models based on the smoothness assumption over the labels (Zhu & Goldberg, 2009) and largely disregarded the graph structure. To improve performance, several learning methods on graphs propose to incorporate intrinsic “graph-based” information by designing a classifying function via generalizing the normalized cut and adding smooth function with respect to the intrinsic structure (Zhou et al., 2004; Zhou & Burges, 2007). A recent approach of Avrachenkov et al. (2012) proposes a generalized optimization framework through considering the above two methods as particular cases. However, one of the major limitations to these graph-based semi-supervised learning methods is disregarding important information contained in graph edges.
To address this disadvantage, Defferrard et al. (2016) propose a formulation of convolutional neural networks (CNN) based on spectral graph theory – ChebNet, which employs approximation via finite order polynomials and, in particular, is based in the Chebyshev expansion for fast filtering instead of the expensive eigen-decomposition. Graph Convolutional Networks (GCN) of Kipf & Welling (2017) simplifies ChebNet and further addresses the gradient vanishing problem and reduces the number of optimization. Other related approaches to graph learning with deep neural networks include, for instance, mixture model networks (MoNet) (Monti et al., 2017), graph attention networks (GAT) (Veličković et al., 2017), graph convolutional recurrent networks (Seo et al., 2018), dual graph convolutional networks (Zhuang & Ma, 2018), FastGCN (Chen et al., 2018), and simplified version of GCN (Wu et al., 2019).
To extend the success of GCN on undirected graphs to directed graphs, MotifNet of Monti et al. (2018) replaces the normalized Laplacian with the motif Laplacian in a multivariate polynomial filter, where the motifs information can help capture the network structure. Finally, the most recent approach of Bianchi et al. (2019) provides more flexible responses than GCN by using parallel and periodic concatenations of the convolutional kernel via the ARMA filter. As a result, the ARMA approach which is applicable to both directed and undirected networks allows to more accurately incorporate the underlying local graph structure into the graph learning process.

heading: 3 METHODOLOGY
text: Given a graph structure G = {V, E ,W}, with V the set of nodes (N = |V|) and E ⊆ V × V the set of edges between any two nodes. Let square matrix W represents the adjacency matrix of a graph whose entries {ωij}1≤i,j≤N are the edge weight function such that each edge eij ∈ E has a weight ωij . We call W the symmetric adjacency matrix (ωij 6= 0 if there is an edge between vertex vi and vertex vj) if we assume that graph G is undirected. In reality, however, undirected graph is a simplified representation of complex networks, we also consider directed graph (in which case W> 6= W ) and we can easily transform the non-symmetric W to the symmetric one through W ′ = (W> +W )/2.
We takeN×Q feature matrixX as the input to a semi-supervised learning algorithm whereQ is the number of different node features. Suppose we would like to classify N data points into K classes (communities), we define N ×K label matrix Y as:
Yik = { 1, if vertex i is labelled as a class k, 0, otherwise. (1)
Here we refer to each column Y·k of matrix Y as a labeling function. Also define an N ×K matrix F and call its columns F·k classification functions.

heading: 3.1 GRAPH SIGNAL PROCESSING
text: In graph signal processing, a real-symmetric matrix has N real eigenvalues and its N real eigenvectors form an orthonormal basis. Given the symmetric adjacency matrix W of a graph, let D be the degree matrix where dii = ∑N j=1 wij and denote L = U
>ΛU the Standard Laplacian matrix, where Λ = diag(λ0, . . . , λN−1) and U = [u0, . . . , uN−1] is the matrix of eigenvectors.
In the following, we will revisit three popular semi-supervised learning methods - graph-based semisupervised learning, fractional graph-based semi-supervised learning, and graph convolutional networks and gain new insights for improving their modeling capabilities.
Graph-based semi-supervised learning. Graph-based semi-supervised learning (G-SSL) has received much attention as an alternative approach to the population paradigm of supervised learning in recent years. G-SSL develops a generalized optimization framework, which has three particular cases (i) the Standard Laplacian (SL); (ii) Normalized Laplacian (NL); (iii) PageRank (PR). The optimization formulation with the following expression:
min F
{ 2FT·kD σ−1LDσ−1F·k + µ(F·k − Y·k)TD2σ−1(F·k − Y·k) } , (2)
where µ is a regularization parameter. The minimization of the first term in Eq. 2 corresponds to the idea that if two nodes are close in graph with respect to some metric, they should belong to the same class; and by minimizing the second term we would like to bring the classification function F·k as close as possible to the labelling function Y·k. The Eq. 2 allows us to obtain the Standard Laplacian based formulation (σ = 1), the Normalized Laplacian formulation (σ = 12 ), and PageRank formulation (σ = 0). The objective of the generalized optimization framework for G-SSL is a convex function and the corresponding classification function:
F·k = (1− α) ( I − αD−σWDσ−1 )−1 Y·k, (3)
where α = 22+µ and for k = 1, . . . ,K.
Tuning the parameter σ on the power of degree matrix D, we can obtain three mentioned above particular semi-supervised learning methods:
• SL method (σ = 1): F·k = (1− α) ( I − αD−1W )−1 Y·k
• NL method (σ = 12 ): F·k = (1− α) ( I − αD−12 WD−12 )−1 Y·k
• PR method (σ = 0): F·k = (1− α) ( I − αWD−1 )−1 Y·k
From above formulations, the classification function F , i.e., the result of random walk process which provides the connection to the probabilistic interpretation of G-SSL. The parameter α controls the strength of the ground truth label matrix Y in the generalized optimization framework.
Fractional graph-based semi-supervised learning. To improve the classification performance (in particular, fuzzy graphs and unbalanced labeled data) of G-SSL, fractional graph-based semisupervised learning (De Nigris et al., 2017) embeds Lévy Flights into random walks on graphs by constructing from powers of the Laplacian matrix, i.e., the Lγ operator. This operation can be used to generate different transition probabilities (i.e., corresponding to stochastic adjacency matrix) based on different γ values. Intuitively, embedding Lévy Flights into random walks allows for better capturing mixing properties (i.e., dependence) in the data. Based on a fractional Laplacian matrix, 0 < γ < 1, the anomalous (fractional) diffusion processes on networks can be constructed from the spectra data and eigenvectors of the Laplacian matrix. The fractional powers of L allows Lévy random walks with long-range navigation on a network. For example, the long-range transitions
on a network can directly move node u and node v with the transition probability m(γ)u→v through a random walker, where m(γ)u→v is an element in the fractional transition matrix M(γ) (see the graph within dotted circle in Figure 1). The transition probability m(γ)u→v between any two nodes whose geodesic distance is not infinite can be summarized as follow:
m(γ)u→v = δuv − (Lγ)uv
k (γ) u
, (4)
where δuv represents the Kronecker delta, k (γ) u denotes the fractional degree of the node u and k (γ) u ≡ (Lγ)uu. Eq. 4 provides transition probabilities for the Lévy Flights. Unlike the standard random walk, the Lévy Flights can jump immediately over several hops in a graph. This feature makes Lévy Flights a very good exploratory process. There is a price to pay for this: the typically sparse transition probability matrix becomes non-sparse. We can mitigate non-sparsity by taking a reasonable number of principal singular eigenvectors or limiting the number of terms in the Taylor expansion. Through replacing the L operator with Lγ = U>ΛγU , the new optimization formulation leaves us with the following expression:
min F
{ 2FT·kD σ−1 γ L γDσ−1γ F·k + µ(F·k − Y·k)TD2σ−1γ (F·k − Y·k) } , (5)
where (Dγ)ii = (Lγ)ii.
Let 0 < γ < 1, the closed form solution for Eq. 5 can be obtain as fellow:
F·k = (1− α) ( I − αD−σγ WγDσ−1γ )−1 Y·k, (6)
for k = 1, . . . ,K. Therefore, we can conclude three particular fractional semi-supervised learning mehtods like G-SSL:
• Fractional SL method (σ = 1): F·k = (1− α) ( I − αD−1γ Wγ )−1 Y·k
• Fractional NL method (σ = 12 ): F·k = (1− α) ( I − αD −1 2 γ WγD −1 2 γ )−1 Y·k
• Fractional PR method (σ = 0): F·k = (1− α) ( I − αWγD−1γ )−1 Y·k

heading: 3.2 PROPOSED FRACTIONAL GENERALIZED GRAPH CONVOLUTIONAL NETWORKS FOR SEMI-SUPERVISED NODE CLASSIFICATION
text: Although both G-SSL and fractional G-SSL achieve comparable and consistent (low variance) performance on some datasets, e.g., Les Miserables, Wikipedia-math, and MNIST, these approaches consider only the given adjacency matrix W and the label matrix Y without using the feature matrix X . Such limitation is crucial especially when dealing with datasets that not only exhibit a sophisticated topological graph structure but also provide node feature information, such as citation, biological, financial, and power grid networks. To address this drawback, through using the feature matrix X instead of the label matrix Y and encoding the graph structure by using neural network framework, many graph-based neural networks methods, e.g., graph convolutional networks (GCN), have been recently proposed and have been shown to demonstrate very impressive advances in semi-supervised learning performance on graphs. Next, we turn to discussing the new Fractional Generalized Graph Convolutional Networks (FGCN) for semi-supervised node classification.
Fractional Generalized Graph Convolutional Networks (FGCN). The key idea behind our proposed method is Fractional Generalized Sigma-based (FGS) filter gFGS(α, σ, γ) = (1 − α) ( I − αD−σγ WγDσ−1γ )−1 = (1 − α)(I − αL̃)−1. Let us insert Taylor series expansion into the expression of the FGS filter and this has the advantage of avoiding the inverse computation. We have the following expression:
gFGS(α, σ, γ) = (1− α) ( I + (αL̃)1 + (αL̃)2 + (αL̃)3 + · · · ) = (1− α) ∞∑ i=0 ( αL̃ )i , (7)
where 0 < α ≤ 1, 0 ≤ σ ≤ 1, 0 < γ ≤ 1. We then obtain the general classification function by multiplying the feature matrix X:
X̄ = gFGS(α, σ, γ)X = (1− α) (
X︸︷︷︸ the first item + αL̃X︸ ︷︷ ︸ the second item + α2L̃2X︸ ︷︷ ︸ the third item
+ · · · ) , (8)
where, recursively,
(X ′ )i = X + αL̃(X ′ )i−1, (X ′ )0 = X, (i = 1, 2, · · · ). (9)
Convolutional layer. During the training process, the convolutional model need to train the trainable parameters (W,b) of the graph filter which can scan the given input feature matrix into a series of feature maps with neurons. Thereby, we provide an implementation of Eq. 8 as a FGS convolutional layer:
H(t+1) = σ ( (1− α)
∞∑ i=0 ( αL̃ )i H(t)W(t) ) , (10)
whereH(t+1) is the hidden layer output matrix of activations in the t-th layer andH(0) = X , σ(·) is the adopted activation function, and Wt is the trainable weight in the t-th layer. Besides, we borrow the concept of the parallel system in reliability theory to improve the consistency of our proposed method. A parallel system is a configuration that the entire system works as long as not all involved components in the system fail. Hence, the parallel system structure is more robust against noisy inputs, compared to a single system structure.
Lemma 1. Let X̄FGS be the output matrix P1 from a pooling layer. Let U = {1, 2, . . . , N} be a finite population such that each unit i, i ∈ U is associated with an output matrix X(i)FGS , i = 1, . . . , N . Then
Var(X̄FGS) = (
1− n N ) S2 n , n < N, n ∈ Z+, (11)
where S2 = ∑N i=1 ( X (i) FGS − X̄UFGS )2 /(N − 1).
Suppose there are n components in a parallel system, with the probability of non-failure P (i)R (where i = 1, · · · , n) in a parallel system, then the reliability of this parallel system PPSR can be obtained with the following expression:
PPSR = 1− n∏ i=1 (1− P (i)R ) = 1− (1− P (1) R )× (1− P (2) R )× · · · × (1− P (n) R ). (12)
According to Lemma 11, the parallel system allows for enhancing stability and reducing estimation variance up to order of n (i.e., Var(X̄FGS) = O(S2/n)). In this way, we establish both theoretical and practical guarantees for our proposed model to reach stable over a large set of hyperparameters, small datasets, and noisy labels based on this parallel implementation.
Pooling layer. When implementing the form of pooling operation to aggregate information from the outputs of parallel FGS convolutional layer, instead of using some popular pooling functions such as max and average pooling, we apply the state-of-art pooling operation - gated max-average pooling (Lee et al., 2016) to capture the local and global information from all the nodes and graph structure. The rationale behind the gated max-average pooling, is that it considers “responsive” strategy (i.e., improving translation invariance and scale invariance via considering input in each gating mask) based on the mixed max-average pooling equation. We have:
fgate(XFGS) = σ ( W>XFGS ) fmax(XFGS) + ( 1− σ ( W>XFGS )) favg(XFGS), (13)
where W is the trainable weight matrix, XFGS is the output matrix from the parallel FGS convolutional layer after concatenation operation.
Residual building block. Inspired by residual learning, we apply a residual block by adding the skip connection after the pooling layer. One of the advantages of the residual learning is the identity mapping which provides a direct path for propagating information. When using the residual building block, we adopt a similar scheme in He et al. (2016) to deal with the output of the pooling layer. Let H(x) be an underlying mapping and we cast it as H(x) = F(x) + x, where F(x) is the residual mapping defined by H(x) − x. In other words, it is easier to optimize the residual mapping F(x) than optimizing the direct mapping H(x) and helps to avoid the gradient vanishing problem during training. To this end, we use an exponential linear unit (ELU) in direct mapping and place a rectified linear unit (ReLU) after addition in our model.

heading: 4 EXPERIMENTS

heading: 4.1 DATASETS
text: Undirected networks. Cora-ML (this Cora dataset consists of Machine Learning papers), CiteSeer and PubMed are three standard citation networks benchmark datasets used for semi-supervised learning evaluation. In these citation networks, nodes represent publications, edges denote citation, the input feature matrix are bag of words and label matrix contain the class label of publication. We use the same data format as GCN, i.e., 20 labels per class in each citation network.
Directed networks. We evaluate our method on four directed networks - Cora, IEEE 118-bus system (IEEE bus), Texas 2000-bus system (TX bus), and South Carolina 500-bus system (SC bus). Unlike the small subset of the Cora-ML dataset (above), Cora is extracted from original dataset which contains more than 50, 000 computer science research papers, where nodes represent scientific papers and directed edges between node u and node v (u → v) represent citation of paper v in paper u. In addition to citation networks, we also test our method on power grid networks. For
IEEE 118-bus system, we consider a (unweighted-directed) graph as a model for the IEEE 118- bus system where nodes represent units such as generators, loads and buses, and edges represent the transmission lines. The input features of power grid network are generator active power upper bound (PMAX) and real power demand (PD) obtained from MATPOWER case struct. For Texas 2000-bus system and South Carolina 500-bus system, we treat them as weighted directed power grid networks. In particular, we use total line charging susceptance (BR B) as edge weight and input features are: (i) real power demand (PD); (ii) reactive power demand (QD); (iii) voltage magnitude (VM); (iv) voltage angle (VA); (v) base voltage (BASE KV). On directed networks, we test them separately from two scenarios: (i) on Cora, the number of features are decomposed into a low dimension (130 components) based on principal component analysis (PCA), the dataset is trained with 10% label rate and evaluated in another 10% fraction whose labels are withheld; (ii) on IEEE 118-bus system, Texas 2000-bus system, and South Carolina 500-bus system, 10% label rate for training set, 20% for validation and 70% for test sets. The statistics of data we used in the experimental section are summarized in Table 1.

heading: 4.2 SETUP AND BASELINES
text: Baselines. In this setting, on undirected networks, we compare FGCN with the state-of-the art semi-supervised classification approaches including (i) using the label matrix as input: label propagation (LP) (Zhu & Ghahramani, 2002); (ii) using the feature matrix as input: DeepWalk (DW) (Perozzi et al., 2014), graph attention networks (GAT), GNN with ChebNet polynomials filter (ChebNet), GCN, GNNs with convolutional ARMA filters (ARMA), Graph Markov Neural Networks (GMNN) (Qu et al., 2019), and Large-Scale Learnable Graph Convolutional Networks (LGCNs) (Gao et al., 2018). In addition, on undirected networks, we use MotifNet (using symmetric motif adjacency matrix instead of Normalized Laplacian matrix in multivariate polynomial filters), ChebNet, GCN, ARMA, GMNN, and LGCNs as the benchmarks.
Training setting details. The training is done by using Adam optimizer with learning rate lr1 = 0.01 for undirected networks and lr2 = {0.1; 0.001} for directed networks. To prevent the model from overfitting, we consider both adding dropout layer before two graph convolutional layers and kernel regularizers (`2) in each layer. For undirected networks: we follow the experimental setup in Kipf & Welling (2017) to set the parameters of baselines (GAT, ChebNet, GCN, ARMA, GMNN, and LGCNs) by using two graph convolutional layers with 16 hidden units, `2 regularization term with coefficient 5 × 10−4, and dropout probability pdrop. of 0.5 (for ARMA, except for number of hidden units, the hyperparameters setting are significantly different from others). For directed networks: we consider the MotifNet setting with using dropout rate pdrop. of 0.5, `2 regularization term with coefficient 0.001, and the degree of multivariate polynomials k = 4 for MotifNet; for other three baselines (i.e., ChebNet, GCN, ARMA, GMNN, and LGCNs), we also use a two-layer network but with 16 hidden units, learning rate lr2 with 0.001, 0.5 dropout rate and `2 regularization weight of 5 × 10−4. In the following, Table 2 displays the best hyperparameter configurations of FGCN for each dataset by using standard grid search mechanism (the optimal kernel regularization weight `2 always equal to 5× 10−4).
* n[1]h denotes the number of hidden units in the first layer; #C [1] and #C[2] represents the number of statistically independent parallel components in the first layer and the second layer respectively; nFGS denotes the number of items in Taylor series polynomial expansion of FGS filter; φ(RB) represents the type of activation functions in residual block structure.

heading: 5 RESULTS
text: Performance comparison of semi-supervised node classification. Table 3 reports the average accuracy delivered by FGCN and competing methods for fixed train/valid/test sizes (see Table 1). The best performance for each dataset is marked in bold.
Table 3 shows that FGCN outperforms all competing approaches in all data sets, except for CiteSeer (FGCN delivers the fouth best accuracy result), PubMed (FGCN delivers the second best accuracy result), Cora (FGCN delivers the third best accuracy result after the LGCNs approach and the difference between FGCN and LGCNs for Cora is less than 0.05%). The improvement gain of FGCN over the next most accurate method ranges from 0.75% (for undirected Cora-ML over GMNN) to 4.21% (for directed IEEE 118-Bus over GMNN). Remarkably, methods that are applicable both to undirected and directed networks (i.e., ChebNet, GCN, ARMA, GMNN, and LGCNs) tend to deliver noticeably lower accuracy results for a directed networks (especially on weighted-directed networks), while the new FGCN method yields a more stable performance across both directed and undirected networks. In turn, CiteSeer (unweighted-undirected), GMNN and LGCNs outperform FGCN up to 1.7%. For the PubMed (unweighted-undirected), our FGCN model delivers marginally better performance results than LGCNs, and GMNN has better performance than FGCN. Finally, both GMNN and LGCNs outperform FGCN on CORA (unweighted-directed), but the delivered accuracy results are very close. Based on the obtain results, the new FGCN approach tends to be the most competitive and, hence, preferred node classification method for sparser networks with higher label rates.
Furthermore, the IEEE 118-Bus data set is the smallest among the considered data (see Table 1), and we might expect to observe lower accuracy results for this data set due to a limited training set. However, the accuracy yielded by FGCN is among the highest ones across all data sets.
Evaluation of FGCN-specific parameters. During grid search over three parameters (i.e., α, σ, and γ), we find that: (i) the regularization parameter α which used to specify the relative importance of a graph in clustering strongly relates to the probability of initial conditions for random walks when the self-refreshing process works, and it strongly influences the network’s generalization ability and node classification performance for all datasets; (ii) the free unifying parameter σ provides enough flexibility to construct a canonical formulation of different graph-based semi-supervised methods. Table 3 indicates that the optimal value of σ depends on both the types of networks (undirected and directed) and label rate not on the size of network; (iii) the fractional power parameter γ substantially impacts the accuracy of node classification for the small datasets (see e.g., Figure 2), however, no similarly strong influence is found in the larger datasets.
Sensitivity analysis. In the sensitivity analysis setting, we have the ability to analyze the sensitivity of the node classification accuracy to variation from three FGCN-specific parameters - α ∈ {0.1, · · · , 1}, σ ∈ {0, 0.1, · · · , 1}, and γ ∈ {0.001, 0.01, 0.1, 1}. In this case, we only show the results from sensitively analysis for FGCN model on IEEE 118-bus dataset. First, we perform the parameter learning experiments on four scenarios with a fixed parameter γ. Figure 2 shows that the accuracy substantially decreases when α is larger than 0.8, especially in γ equals to 0.001 and 0.01 (see Figure 2a, 2b). Setting γ = {0.1, 1}, we observe that the classification accuracy nearly monotonic decreases while increasing α. Additionally, there is little difference of classification accuracy between γ = 0.001 and γ = 0.01 and FGCN generally gives consistent and higher accuracy when the α parameter is within the range of {0.1, 0.2, 0.3, 0.4}. We then explore the variation of accuracy based on tuning parameter γ within the range of [0.001, 0.002, · · · , 0.01] (setting σ ∈ {0, 0.1, · · · , 1} at the same time), however, it is hard to obtain the optimal (σ̂, γ̂) combination through gathering finite experimental results (100 runs) since some of the results are very close. Therefore, we run the following experiments to demonstrate the impact evaluation of γ:
• Step 1: Setting γ ∈ {0.001, 0.002, · · · , 0.1}.
• Step 2: For each γ (i.e., fix the γ value in each experiment), we run our proposed model 100 times separately for σ from 0 to 1 by 0.01; Then we can obtain the 100 average accuracies for each γ under fixed γ, that is, {AACσ=0, ACCσ=0.01, · · · , AACσ=1}[i], where i = 1, · · · , 10.
• Step 3: Fitting the Gaussian distribution to {AACσ=0, ACCσ=0.01, · · · , AACσ=1}[i] (see Figure 3b).
Similar to γ, we can fit the Gaussian distribution to {AACγ=0.001, ACCγ=0.002, · · · , AACγ=0.01}[j] by fixing σ, where j = 1, · · · , 11 (see Figure 3a). From Figure 3, we find that there exist larger difference between the shapes of approximate Gaussian distributions by fixing the parameter σ than fixing the parameter γ which means the parameter σ is more important factor in FGCN approach for small datasets.

heading: 6 CONCLUSION
text: In this paper we have proposed a new Fractional Generalized Graph Convolutional Networks (FGCN) method to semi-supervised learning on graphs that enables to better capture the intrinsic local graph topology. The key idea behind our new approach is a new fractional generalized graph-based convolutional filter which casts the Lévy Flights into random walks on graphs and, as a result, allows for a more efficient, accurate and robust exploration of the local graph structure which often plays the key role in graph learning performance, especially for heterogeneous graphs.
Our numerical studies have indicated that the new FGCN method tends to outperform all competing deep learning approaches on both unweighted-directed and unweighted-undirected graphs in all considered data sets, except of Cora for which the difference between the best result delivered by the GMNN and FGCN is less than 0.85%. The gain in learning accuracy of FGCN over the next best competitor ranges from 0.75% to 4.21%, and the highest gain has been achieved for the IEEE 118-Bus data set which is the smallest among the considered data sets. Furthermore, in contrast to the competing approaches, FGCN tends to deliver a more stable performance across directed and undirected networks regardless of the label rate.
In the future we plan to advance the proposed FGCN technique to learning on multilayer networks and to enhance graph learning process with topological information on the underlying deep neural network.

heading: A APPENDIX
text: Proof of Lemma 1: The parallel structure (Henley & Kumamoto, 1981) is constructed in a similar spirit as bagging of features in random forest and other ensemble learning methods. The key rationale behind the parallel structure is to reduce variance and increase stability.
Let us first consider (11). Suppose that Υ is a random sample drawn without replacement from a finite population U = {1, 2, . . . , N} according to a sampling design p(·). Each unit i, i = 1, . . . , N of U is associated with X(i)FGS , i.e. the i-th output matrix from FGS convolution for new feature matrix Xi. Probability of choosing sample υ is Pr(Υ = υ) = p(Υ) > 0 for all υ ∈ U and υ 6= ∅. Let Z be the indicator variable such that
Zi = { 1, if Xi is in the sample 0, otherwise. (14)
Hence, probability that the unit i, i = 1, . . . , N is selected, is given by πi = E(Zi), and probability that units i and j, i, j = 1, . . . , N are selected simultaneously is πij = E(ZiZj); πi and πij are called first order inclusion probability and second order inclusion probability, respectively. Since in the current paper, we consider a simple random sampling design of n units X(i)FGS without replacement from U , πi = n/N and πij = n(n− 1)/N(N − 1).
Let X̄FGS = ∑ i∈N X (i) FGS/n = ∑N i=1 ZiX (i) FGS/n. Hence, given {X (1) FGS , . . . , X (N) FGS}, we find that
E[X̄FGS ] = N∑ i=1 E [Zi] X (i) FGS n = N∑ i=1 πi X (i) FGS n = N∑ i=1 n N X (i) FGS n = N∑ i=1 X (i) FGS N = X̄UFGS ,
where X̄FGS is be the output matrix P1 from a pooling layer (see Figure 1), which implies that X̄FGS is an unbiased estimator of population mean X̄UFGS .
In turn,
Var(X̄FGS) = 1
n2 V ( N∑ i=1 ZiX (i) FGS )
= 1
n2 Cov  N∑ i=1 ZiX (i) FGS , N∑ j=1 ZjX (j) FGS  = 1
n2  N∑ i=1 (X (i) FGS) 2 Var (Zi) + N∑ i=1 N∑ j 6=i X (i) FGSX (j) FGS Cov (Zi, Zj)  = 1
n2  n N ( 1− n N ) N∑ i=1 (X (i) FGS) 2 − N∑ i=1 N∑ j 6=i X (i) FGSX (j) FGS 1 N − 1 ( 1− n N )( n N ) = 1
n
( 1− n
N ) 1 N(N − 1) (N − 1) N∑ i=1 (X (i) FGS) 2 − ( N∑ i=1 X (i) FGS )2 + N∑ i=1 (X (i) FGS) 2  = 1
n
( 1− n
N ) 1 N(N − 1) N N∑ i=1 (X (i) FGS) 2 − ( N∑ i=1 X (i) FGS )2 = (
1− n N ) S2 n ,
(15)
where S2 = ∑N i=1 ( X (i) FGS − X̄UFGS )2 /(N −1) and the factor (1−n/N) is called the finite population correction (FPC). Hence, the proposed PS structure decreases an original estimation variance S by order of n. Note that we can consider other sampling designs p(·), including, for example, weighted sampling and p-extended simple random sampling with replacement (see discussion by Wong & Easton, 1980; Scott & Köhl, 1994; Ozturk & Balakrishnan, 2019, and references therein).
The stability result of the parallel structure (Nowak & Collins, 2012) follows from verbatim application of the probability bound on the intersection of independent events.

heading: B APPENDIX
text: The general idea of graph-based semi-supervised learning (G-SSL) is based on two widely used optimization frameworks. The first formulation, the Standard Laplacian based formulation (Zhou & Burges, 2007) as follows:
min F  N∑ i=1 N∑ j=1 wij ‖Fi. − Fj.‖2 + µ N∑ i=1 di ‖Fi. − Yi.‖2  , (16)
where dii is (i, i)-element in degree matrix D and wij represents the edge weight for edge eij in adjacency matrix W . For the second formulation, the Normalized Laplacian based formulation (Zhou et al., 2004), is as follows:
min F  N∑ i=1 N∑ j=1 wij ∥∥∥∥∥ Fi.√dii − Fj.√djj ∥∥∥∥∥ 2 + µ N∑ i=1 ‖Fi. − Yi.‖2  (17)
The following lemma (Avrachenkov et al., 2012) asserts that the generalized optimization framework, i.e., G-SSL, which has as particular cases the two above mentioned formulations:
Lemma 2. Let σ denote an alternative parameter on the power of degree matrix D whose entries are the degrees dii; and let 0 ≤ σ ≤ 1. Then
min F  N∑ i=1 N∑ j=1 wij ∥∥dσ−1ii Fi. − dσ−1jj Fj.∥∥2 + µ N∑ i=1 d2σ−1ii ‖Fi. − Yi.‖ 2  . The classification functions for the generalized semi-supervised learning are given by
F·k = (1− α) ( I − αD−σWDσ−1 )−1 Y·k.
Proof: The objective function of the generalized semi-supervised learning framework (i.e., Lemma 2.) can be rewritten in the following matrix form:
Q(F ) = 2 K∑ k=1 FT.kD σ−1LDσ−1F.k + µ K∑ k=1 (F.k − Y.k)T D2σ−1 (F.k − Y.k) .
Given the first order optimality condition DF.kQ(F ) = 0, we have 2FT.k ( Dσ−1LDσ−1 +Dσ−1LTDσ−1 ) + 2µ (F.k − Y.k)T D2σ−1 = 0.
Multiplying the above expression from the right hand side by D−2σ+1 leads to 2FT.k ( Dσ−1 ( L+ LT ) D−σ ) + 2µ (F.k − Y.k)T = 0.
Then, substituting L = D −W and rearranging the terms yields FT.k ( 2I −Dσ−1 ( W +WT ) D−σ + µI ) − µY T.k = 0.
Since the resulting adjacency matrix W is a symmetric matrix (see transformation 3 in the main body of the paper through replacing µ with α = 2/(2 + µ)), we obtain
FT.k = µY T .k
( 2I − 2Dσ−1WD−σ + µI )−1 ,
which concludes the proof.

Review summaries:
This paper proposes a fractional graph convolutional networks for semi-supervised learning. The proposed method used a classification function of a fractional graph semi-supervised learning (GSSL) [De Nigris et al., 2017] as a graph filter. In addition, the authors adopt a parallel system and weighted combination of max and average pool. Experimental results show that the proposed method (FGCN) shows the best accuracy compared to other recent graph-based neural networks for all datasets except one.