Title: FRACTIONAL GRAPH CONVOLUTIONAL NETWORKS (FGCN) FOR SEMI-SUPERVISED LEARNING Anonymous

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.

1. INTRODUCTION:

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 Lé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 Lé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.

2. RELATED WORK:

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) (Veličković 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.

3. METHODOLOGY:

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 e ij ∈ E has a weight ω ij . We call W the symmetric adjacency matrix (ω ij = 0 if there is an edge between vertex v i and vertex v j ) 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 = W ) and we can easily transform the non-symmetric W to the symmetric one through W = (W + W )/2.

We take N × Q feature matrix X as the input to a semi-supervised learning algorithm where Q 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:

EQUATION

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.

3.1. GRAPH SIGNAL PROCESSING:

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 d ii = N j=1 w ij and denote L = U ΛU the Standard Laplacian matrix, where Λ = diag(λ 0 , . . . , λ N -1 ) and U = [u 0 , . . . , u N -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:

EQUATION

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 (σ = 1 2 ), and PageRank formulation (σ = 0). The objective of the generalized optimization framework for G-SSL is a convex function and the corresponding classification function:

EQUATION

where α = 2 2+µ 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 -1 W -1 Y •k • NL method (σ = 1 2 ): F •k = (1 -α) I -αD -1 2 W D -1 2 -1 Y •k • PR method (σ = 0): F •k = (1 -α) I -αW D -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 Lé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 Lé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 Lé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:

EQUATION

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 Lévy Flights. Unlike the standard random walk, the Lévy Flights can jump immediately over several hops in a graph. This feature makes Lé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:

EQUATION

where

(D γ ) ii = (L γ ) ii .

Let 0 < γ < 1, the closed form solution for Eq. 5 can be obtain as fellow:

EQUATION

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 (σ = 1 2 ): 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 3.2 PROPOSED FRACTIONAL GENERALIZED GRAPH CONVOLUTIONAL NETWORKS FOR SEMI-SUPERVISED NODE CLASSIFICATION

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

g F GS (α, σ, γ) = (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:

EQUATION

where

0 < α ≤ 1, 0 ≤ σ ≤ 1, 0 < γ ≤ 1.

We then obtain the general classification function by multiplying the feature matrix X:

EQUATION

where, recursively,

EQUATION

)

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:

EQUATION

where H (t+1) is the hidden layer output matrix of activations in the t-th layer and H (0) = X, σ(•) is the adopted activation function, and W t 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 XF GS be the output matrix P 1 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)

EQUATION

where

S 2 = N i=1 X (i) F GS -XU F GS 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 P P S R can be obtained with the following expression:

EQUATION

According to Lemma 11, the parallel system allows for enhancing stability and reducing estimation variance up to order of n (i.e., Var( XF GS ) = O(S 2 /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:

EQUATION

)

where W is the trainable weight matrix, X F GS 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.

4. EXPERIMENTS:



4.1. DATASETS:

Undirected networks. Cora-ML (this Cora dataset consists of Machine Learning papers), Cite-Seer 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 118bus 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 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 lr 1 = 0.01 for undirected networks and lr 2 = {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 p drop. 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 p drop. 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 lr 2 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 ). 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; nF GS denotes the number of items in Taylor series polynomial expansion of FGS filter; φ(RB) represents the type of activation functions in residual block structure.

5. RESULTS:

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.

6. CONCLUSION:

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 Lé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. , where the red curve denotes the PR-based method (σ = 0), green curve denotes the NL-based method (σ = 0.5), and blue curve denotes the SL-based method (σ = 1); the dotted curves represent common scenarios in FGCN model, that is, the generalized parameter σ falls within the range of (0, 0.5) ∪ (0.5, 1). (b) the red, green, blue dotted curve represents the scenario when setting the fractional parameter γ equals to 0.001, 0.005, and 0.01, respectively; The solid curves represent scenarios where γ in the range of (0.001, 0.005) ∪ (0.005, 0.01).

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.

A APPENDIX:

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)

F GS , i.e. the i-th output matrix from FGS convolution for new feature matrix X i . Probability of choosing sample υ is P r(Υ = υ) = p(Υ) > 0 for all υ ∈ U and υ = ∅. Let Z be the indicator variable such that

EQUATION

Hence, probability that the unit i, i = 1, . . . , N is selected, is given by π i = E(Z i ), and probability that units i and j, i, j = 1, . . . , N are selected simultaneously is π ij = E(Z i Z j ); π 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)

F GS without replacement from U, π i = n/N and π ij = n(n -1)/N (N -1).

Let XF GS = i∈N X (i)

F GS /n = N i=1 Z i X (i)

F GS /n. Hence, given {X

(1) F GS , . . . , X (N ) F GS }, we find that

E[ XF GS ] = N i=1 E [Z i ] X (i) F GS n = N i=1 π i X (i) F GS n = N i=1 n N X (i) F GS n = N i=1 X (i) F GS N = XU F GS ,

:



Figures and Tables:

Figure 1: Illustration Fractional Generalized Graph Convolutional Network model. The input is the feature matrix X and the graph within dotted circle represents embedding Lévy Flights into random walks on graph (where L γ is the Laplacian matrix L to a power γ). FGCN architecture consists of three main components: (i) FGS convolutional layer with parallel structure; (ii) gated max-average pooling layer; (iii) activation block for residual learning.

Figure 2: Accuracy of FGCN for PageRank, Normalized Laplacian, and Standard Laplacian, which depends on the function of α and fixes the fractional power γ = {0.001 (a), 0.01 (b), 0.1 (c), 1.0 (d)}

Figure3: Generalized Gaussian density of accuracy of FGCN: (a) the solid curves represent three particular scenarios in FGCN, where the red curve denotes the PR-based method (σ = 0), green curve denotes the NL-based method (σ = 0.5), and blue curve denotes the SL-based method (σ = 1); the dotted curves represent common scenarios in FGCN model, that is, the generalized parameter σ falls within the range of (0, 0.5) ∪ (0.5, 1). (b) the red, green, blue dotted curve represents the scenario when setting the fractional parameter γ equals to 0.001, 0.005, and 0.01, respectively; The solid curves represent scenarios where γ in the range of (0.001, 0.005) ∪ (0.005, 0.01).

Dataset statistics.

Table content: <table><tr><td colspan="7">particular, we use total line charging susceptance (BR B) as edge weight and input features are:</td></tr><tr><td colspan="7">(i) real power demand (PD); (ii) reactive power demand (QD); (iii) voltage magnitude (VM); (iv)</td></tr><tr><td colspan="7">voltage angle (VA); (v) base voltage (BASE KV). On directed networks, we test them separately</td></tr><tr><td colspan="7">from two scenarios: (i) on Cora, the number of features are decomposed into a low dimension (130</td></tr><tr><td colspan="7">components) based on principal component analysis (PCA), the dataset is trained with 10% label</td></tr><tr><td colspan="7">rate and evaluated in another 10% fraction whose labels are withheld; (ii) on IEEE 118-bus system,</td></tr><tr><td colspan="7">Texas 2000-bus system, and South Carolina 500-bus system, 10% label rate for training set, 20%</td></tr><tr><td colspan="7">for validation and 70% for test sets. The statistics of data we used in the experimental section are</td></tr><tr><td colspan="2">summarized in Table 1.</td><td/><td/><td/><td/><td/></tr><tr><td>Dataset</td><td colspan="5">Vertices Edges Features Classes Label rate</td><td>Train/Valid/Test</td></tr><tr><td>Cora-ML</td><td>2,708</td><td>5,429</td><td>1,433</td><td>7</td><td>0.052</td><td>140 / 500 / 1,000</td></tr><tr><td>CiteSeer</td><td>3,327</td><td>4,732</td><td>3,703</td><td>6</td><td>0.036</td><td>120 / 500 / 1,000</td></tr><tr><td>PubMed</td><td>19,717</td><td>44,338</td><td>500</td><td>3</td><td>0.003</td><td>60 / 500 / 1,000</td></tr><tr><td>Cora</td><td>19,793</td><td>65,311</td><td>8,710</td><td>70</td><td>0.100</td><td>1,979 / 1,979 / 1,979</td></tr><tr><td>IEEE Bus</td><td>118</td><td>182</td><td>2</td><td>3</td><td>0.100</td><td>11 / 35 / 70</td></tr><tr><td>TX Bus</td><td>2,000</td><td>2,668</td><td>5</td><td>3</td><td>0.100</td><td>200 / 400 / 1,400</td></tr><tr><td>SC Bus</td><td>500</td><td>584</td><td>5</td><td>3</td><td>0.100</td><td>50 / 100 / 350</td></tr><tr><td colspan="3">4.2 SETUP AND BASELINES</td><td/><td/><td/><td/></tr></table>

Hyperparameters setting of FGCN

Table content: <table><tr><td>Dataset</td><td colspan="2">p drop. n</td><td>[1] h</td><td>α</td><td>σ</td><td>γ</td><td colspan="2">n F GS {#C [1] ; #C [2] }</td><td>φ(RB)</td></tr><tr><td>Cora-ML</td><td>0.75</td><td colspan="5">32 0.6 0.50 1.000</td><td>7</td><td>{5;2}</td><td>ELU + ReLU</td></tr><tr><td>CiteSeer</td><td>0.75</td><td colspan="5">32 0.6 0.53 1.000</td><td>7</td><td>{3;2}</td><td>ELU + ELU</td></tr><tr><td>PubMed</td><td>0.00</td><td colspan="5">32 0.6 0.50 1.000</td><td>7</td><td>{5;2}</td><td>ELU + ReLU</td></tr><tr><td>Cora</td><td>0.00</td><td colspan="5">128 0.4 1.00 1.000</td><td>15</td><td>{1;1}</td><td>ELU + ELU</td></tr><tr><td>IEEE Bus</td><td>0.00</td><td colspan="5">128 0.1 0.20 0.004</td><td>40</td><td>{7;2}</td><td>ELU + ELU</td></tr><tr><td>TX Bus</td><td>0.00</td><td colspan="5">128 0.3 0.10 0.100</td><td>14</td><td>{5;2}</td><td>ELU + ELU</td></tr><tr><td>SC Bus</td><td>0.00</td><td colspan="5">128 0.2 0.10 0.100</td><td>20</td><td>{5;2}</td><td>ELU + ELU</td></tr><tr><td>* n [1]</td><td/><td/><td/><td/><td/><td/><td/></tr></table>

Comparison of average accuracy (%) of semi-supervised classification approaches for both undirected networks and directed networks.

Table content: <table><tr><td/><td colspan="2">Undirect networks</td><td/><td/><td colspan="2">Directed networks</td><td/></tr><tr><td>Method</td><td colspan="3">Cora-ML CiteSeer PubMed</td><td colspan="4">Cora IEEE Bus TX Bus SC Bus</td></tr><tr><td>LP</td><td>68.70</td><td>46.32</td><td>65.92</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>DW</td><td>67.20</td><td>43.27</td><td>65.33</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>MotifNet</td><td>-</td><td>-</td><td>-</td><td>60.00</td><td>65.75</td><td>82.00</td><td>95.18</td></tr><tr><td>GAT</td><td>83.11</td><td>70.85</td><td>78.56</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>ChebNet</td><td>81.45</td><td>70.23</td><td>78.40</td><td>58.93</td><td>60.00</td><td>80.04</td><td>94.13</td></tr><tr><td>GCN</td><td>81.50</td><td>71.11</td><td>79.00</td><td>57.75</td><td>52.86</td><td>73.36</td><td>90.33</td></tr><tr><td>ARMA</td><td>82.80</td><td>72.30</td><td>78.80</td><td>58.99</td><td>70.55</td><td>81.20</td><td>94.33</td></tr><tr><td>GMNN</td><td>83.72</td><td>73.10</td><td>81.80</td><td>61.20</td><td>78.88</td><td>86.21</td><td>96.57</td></tr><tr><td>LGCNs</td><td>83.35</td><td>73.08</td><td>79.51</td><td>60.72</td><td>71.43</td><td>85.57</td><td>95.14</td></tr><tr><td>FGCN (ours)</td><td>84.35</td><td>71.89</td><td>79.56</td><td>60.70</td><td>82.20</td><td>87.74</td><td>97.61</td></tr></table>

Peer review (iclr2020):
This paper presents a fractional generalized graph convolutional networks for semi-supervised learning. The authors design a new graph convolutional filter based on Levy Flights, and propose new feature propagation rules on graphs. Experimental results on multiple graph datasets are reported and discussed. Pros. 1. This paper presents a nice overview of three popular semi-supervised learning methods in Section 3.1, and presents insights regarding these models. 2. A new graph convolutional filter is proposed. The motivation is clear, and the technical details are easy to follow. 3. Experiments on five benchmark datasets are conducted. Both undirected and directed graphs are used in experiments. Cons. 1. The proposed method contains three major components: parallel FGS convolution, pooling, and residual block. Although some justifications are provided for such designs, it is difficult to justify the role of each component. In other words, it is unclear whether the performance gain is from the parallel structure, or the residual block. What would be the model performance without parallel structures? Also, given that FGCN has quite a few layers, the motivation of using residual blocks should be carefully justified. 2. Many recent methods on graph neural networks are not discussed or included as baselines, such as [a-b]. [a] GMNN: Graph Markov Neural Networks, ICML 2019 [b] Large-Scale Learnable Graph Convolutional Networks, KDD 2018 [c] SPAGAN: Shortest Path Graph Attention Network, IJCAI 2019 ------------------------------------------------- The response from authors addressed many of my concerns. The rating has been updated.