A New Paradigm for Federated Structure Non-IID Subgraph Learning
Authors: Xunkai Li
Wentao Zhang
Rong-Hua Li
Yulin Zhao
Yinlin Zhu
Guoren Wang
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph neural network
federated learning
structure non-iid subgraphs

Abstract: Federated graph learning (FGL), a distributed training framework for graph neural networks (GNNs) has attracted much attention for breaking the centralized machine learning assumptions. Despite its effectiveness, the differences in data collection perspectives and quality lead to the challenges of heterogeneity, especially the domain-specific graph is partitioned into subgraphs in different institutions. However, existing FGL methods implement graph data augmentation or personalization with community split which follows the cluster homogeneity assumptions. Hence we investigate the above issues and suggest that subgraph heterogeneity is essentially the structure variations. From the observations on FGL, we first define the structure non-independent identical distribution (Non-IID) problem, which presents covariant shift challenges among client-wise subgraphs. Meanwhile, we propose a new paradigm for general federated data settings called Adaptive Federated Graph Learning (AdaFGL). The motivation behind it is to implement adaptive propagation mechanisms based on federated global knowledge and non-params label propagation. We conduct extensive experiments with community split and structure Non-IID settings, our approach achieves state-of-the-art performance on five benchmark datasets.

Under review as a conference paper at ICLR 2023
A NEW PARADIGM FOR FEDERATED STRUCTURE NON-IID SUBGRAPH LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated graph learning (FGL), a distributed training framework for graph neu- ral networks (GNNs) has attracted much attention for breaking the centralized machine learning assumptions. Despite its effectiveness, the differences in data collection perspectives and quality lead to the challenges of heterogeneity, es- pecially the domain-specific graph is partitioned into subgraphs in different in- stitutions. However, existing FGL methods implement graph data augmentation personalization with community split which follows the cluster homogeneity assumptions. Hence we investigate the above issues and suggest that subgraph heterogeneity is essentially the structure variations. From the observations FGL, we first define the structure non-independent identical distribution (Non- IID) problem, which presents unique challenges among client-wise subgraphs. Mcanwhile, we propose new paradigm for general federated data settings called Adaptive Federated Graph Learning (AdaFGL). The motivation behind is im- plement adaptive propagation mechanisms based on federated global knowledge and non-params label propagation. We conduct extensive experiments with com- munity split and structure Non-lID settings, our approach achieves state-of-the-art performance on five benchmark datasets.
INTRODUCTION
The graph as a relational data structure is widely used model real-world entity relations such as citation networks Yang et al. (2016a), recommended systems Wu et al. (2022), drug discov- ery Gaudelet et al. (2021), particle physics[Shlome et al. (202T), etc. However, due to the collection agents and privacy concerns, generally, the global domain- graph consists of many subgraphs collected by multiple institutions. order to analyze the local subgraph, each client maintains a powerful graph mining model such graph neural networks (GNNs), which have achieved state- of-the-art art performance in many graph learning tasks Zhang et al. (2026)); Hu et al. (202T); Zhang & Chen (2018). Despite its effectiveness, the limited data provide sub sub-optimal performance in most cases. Motivated by the success of federated learning (FL), a natural idea is to combine the GNNs with FL. utilize the distributed subgraphs. Recently, federated graph learning (FGL) He et al. (202T): Wang et al. (2022b) is proposed to achieve collaborative training without directly sharing data, yet an essential concern is the heterogeneity of the distributed subgraphs.
Notably, graph heterogeneity is different from the heterogeneity of labels or features in the fields of computer vision or natural language processing, we suggest that it depends on the graph structure. However, The existing FGL methods simulate the federated subgraph distributions through com- munity split, which follows the cluster homogeneity assumption shown in Fig Specifically, community split leads to the subgraph structure being consistent and the same as the original graph, e.g., connected nodes are more likely to have the same labels. Obviously, hard to satisfy in reality, hence consider more reasonable setting shown in Fig We first refer to the above problem as structure non-independent identical distribution (Non-IID).
overly desirable and
The motivation behind it is due to graph structure directly related to node labels and feature distribu- tions. Meanwhile, the challenges of structure heterogeneity are ubiquitous in the real world Zheng et al. (2022b). For instance, in citation networks, we consider research teams focused computers and intersectional fields (c.g.. Al Science) [Shlomi et al.] (202)) Gaudelet et al. (202T) as clients. In online transaction networks, fraudsters more likely to build connections with customers instead

---

Under review as a conference paper at ICLR 2023
FGL Global Server
FGL Local System
Homophily
Homophily
Init model
2. Receives model
Receives message
3. Local training
Cliege
GNN
Chent
Chient
(grads, cmbs, adj..)
Client
ddd Client 30
Clien 2
S. Handless messages
Broadcasts results
Repent 2.3
Heterophily
(a) Existing FGI. Based on Community Split
(b) General FGI. Pipeline
(c) Challenges Hased on Stracture Noe-III Split
Figure I: We utilize black circles for base class and gray circles for other class. (a): Limitations of existing FGL methods. (b): The general collaborative training pipeline. (c): The new challenges of graph structure Non-IID for FGL.
of other fraudsters Pandit et al. (2007) We consider different regions as clients to detect financial fraudsters by analyzing online transaction subgraphs. Specifically, graph structure can be divided into two types: homogeneity means that connected nodes are more likely to have the same label and similar feature distributions and heterogeneity is the opposite. In order to explain it intuitively,
visualize the 3 clients partitioning result on Cora in Table. [ and Table. 2 where Homo represents the homogeneity degree of the local subgraph, and it is computed by popular metric [Pei et al. (2020). Obviously, compared to community split, which follows the cluster homogeneity assumption and uniform distribution principle, structure Non-IID brings challenges to the existing FGL methods.
Table I: Community split in Cora.
Table Structure Non-IIID Cora.
Community
#Nodes
#Edges
Homo
Non-IID
#Nodes
#Edges
Homo
Clientl
903
1696
0.85
Clientl
1095
1473
0.43
Client2
903
1575
0.78
Client2
946
1400
0.87
Client3
902
1592
0.87
Client3
667
1212
0.31
Based on this, we investigate the above issues through empirical analysis shown in Fig. According to the results, we observe that in case the original graph satisfies the homogeneity assumption then the label distributions satisfy Non-IID. It is the opposite when the original graph satisfies the hetero- geneity. This is due to the fact that the nodes partitioned into the same clients are communities and follow the uniform distribution principle. In addition, the local accuracy indicates that the subgraph structure performs a more important role in FGL compared to the label distributions, which also supports motivation. In model performance, Non-IID problem, and FedSage+ trains NeighGen to implement local subgraph augmentation by sharing node embeddings. However, the above methods fail achieve competitive results as SGC on the homogeneous subgraphs while considering heterogeneity.
observe that the GGCN improves the structure
In order to efficiently analyze distributed subgraphs with both homogeneity and heterogeneity. We propose a simple pipeline called Adaptive Federated Graph Learning (AdaFGL. for more general federated data settings, which consists of three main parts. Specifically, it starts by analyzing the subgraph structure through non-param label propagation and selects the appropriate base model: (i) the federated global knowledge extractor (e.g., MLP, powerful GNNs, or any reasonable embedding models), which does not rely on any learning over the subgraph. Then, the base predictor is trained based on the global data, which can be done offline or in parallel with local training, benefiting from the flexibility of our approach. Finally, the local client implements two adaptive propagation mechanisms: (ii) homogeneity propagation module or (iii) heterogeneity propagation module based on the local subgraph. Notably, with non non-params label propagation, the above process is adaptive.
To summarize, the contributions of this paper are as follows: (1) To the best our knowledge, we are the first to analyze the structure Non-IID problem in FGL, which is more general federated data setting and brings new challenges. (2) We propose AdaFGL, a new paradigm for structure Non-IID subgraph learning, which shows its flexibility in FGL with impressive performance. (3) Extensive experiments demonstrate the effectiveness of AdaFGL. Specifically, our approach achieves state-of- the-art performance in the above two data settings. Compared to the best prediction accuracy in the
2

---

Under review as a conference paper at ICLR 2023
Caes1
Structure Challenges in CiteSeer & Squirrel
Clacsa
Gassa
Classi
Class
Local Accuracy
Casss
R.6.
disst
Class2
class3
Cassi
1010
70
10
02
Gssss
10:3
15
Community Split
Structure Non-IID
Client
Figure 2: FedSGC: FedAvg+SGC, FedGGCN: FedAvg+GGCN represent the representative meth- ods. The upper and lower parts represent CiteSeer and Squirrel, respectively, left and right parts represent community split and structure Non-IID, respectively. The left x-axis represents the client ID, and the number represents the number samples each client corresponding to the classes. The dark color represents the number of samples with high numbers.
baselines, our method achieves performance gains of 4.67% and 2.65% in structure Non-IID and community split data settings, respectively.
PRELIMINARIES
In this section, we first introduce the eemi-supereieed node classification task. Then, we review the prior diverse GNNs and very recent FGL methods. Consider graph G = (V, E) with [V] = nodes and EE| = m edges, the adjacency matrix (including self loops) is denoted as Å R=x" the feature matrix is denoted as X (2.., in which Th E R represents the feature vector of node v, and f represents the dimension of the node attributes. Besides,
{y1, U2...., Yn) is the label matrix, where Yo E IR YI is a one-hot vector and |Y| represents the number of the node classes. The semi-supervised node classification task is based the topology of labeled set V,. and unlabeled set Vu, and the nodes in Vú are predicted with the model supervised by Vi.
GNNs. As the most popular GNN method, The forward information propagation process of the I-th layer GCN Kipf & Welling (2117) is formulated as D
(1)
where D represents the degree matrix with Å, [0, denotes the convolution kernel coefficient, W represents the trainable weight matrix, and (-)) represents the non-linear activation function.
In GCN, we set r 1/2, and then 1-1/2 AD AD11 is called symmetric normalized adjacency matrix. Despite their effectiveness, they have limitations in real-world graphs, which have complex heterogeneous relationship patterns. Some recent researches Liu et al. (2021); Chien et al. (2021); He et al. (2022); Wang et al. (0022a); Yang al. (2022) solve it by higher-order neighborhood discovery or message combination strategies to improve the GNN process via
Aggregate (1) (fht (G)))),
(2)
Update (h mt),
where h; denotes the information of multi-hop neighbors (V))). m represents the higher-order messages of node v from the previous layers, Aggregate(.) and Update(-) denote the message aggregation function and update function, respectively. However, these methods suffer from high computational complexity and fail to achieve competitive performance on the homogeneous graph.
FGL has received growing attention for breaking centralized graph machine learning assumptions. FedGraphNN He al. (202I) and FS-G Wang et al. (202bb) propose general FGL packages, which contain a wide range of graph learning tasks. GCFL Xie et al. (2021) and FED-PUB Back et al. (2022) investigate the personalized technologies in gevel and node-level, respectively. Fur- thermore, some recent researches improve performance with local subgraph augmentation, includ- ing FedGNN Wu et al. (202)), FedGL. Chen al. (202T), and FedSage Zhang et al. (202)). Inspired

---

Under review as a conference paper at ICLR 2023
Federated Global Knowledge Extractor
MLF
Global embeddings
Global embeddings
MLP
Smoothed feature
Local feature
Propagation matrix
Homogeneity Propagation Module
Non-Params Label Propagation
Heterogeneity Propagation Module
Figure 3: Overview of our model-free pipeline with a toy example. The federated global knowledge extractor represents wide variety of node embedding models. The middle part of the black circles represents labeled nodes and the gray circles represent unlabeled nodes. Based on this we obtain graph structure properties and implement the adaptive propagation mechanisms.
by FS-G Wang et al. (202bb), ules. Specifically, we model the information such as gradients and node embeddings uploaded by the clients messages. Then consider the server processes and broadcast results as the various message-handling mechanisms. Here we illustrate the GNNs combined with collaborative training. Its generic form with N clients is defined
consider the collaborative training process in FGL mod-
NV
FGL Clients (Local Update)
min N
Σ
E
Y.),,
(3)
Σ Eiv,, KEV2
() .
(1 Yz²) log(1 Softmax (Y,)))
where for and Loe are the i-th local GNN with parameters and cross-entropy loss function, respectively. It be replaced by any other appropriate loss function depending on the task. (A,, Y,) ~ Dj represents the local subgraph (A, X,, Y:) sampled from the distribution D; FedAvg McMahan al. (2017) is an efficient FL algorithm, which can be defined as
FGL - Server (Aggregate) - Vi, W W 199, WHI
Σ "i
(4)
where represents the round number of the FL process. W represents the model weights, 17 repre- sents the learning rate, g represents the gradient calculated from the Eq. and represent the i-th local client data size and the global data size, respectively.
ADAFGL PIPELINE
The basic idea of AdaFGL is to perform adaptive propagation mechanisms based federated global knowledge and non-params label propagation. The pipeline with three main parts as shown in Fig, 3 which combine the global knowledge embeddings and local structure properties. The above decou- pling process utilizes the computational capacity of the local system while minimizing communica- tion costs and the risk of privacy leakage. AdaFGL can benefit from the evolution of FL and GNN through the base predictor and adaptive propagation. Notably, the base predictor obtained by feder- ated training and personalized propagation are viewed as two decoupled modules that are executed sequentially, Mcanwhile, both of them accomplish the training without sharing local private data.
3.1 FEDERATED GLOBAL KNOWLEDGE EXTRACTOR
In FGL. limited data yields sub-optimal performance in most cases. Therefore, AdaFGL starts to perform non-params label propagation adaptive process. Note this process does not rely any
4

---

Under review as a conference paper at ICLR 2023
learning over the subgraph. Specifically, the labeled nodes are initialized y Yo: Vo VL, and the unlabeled nodes are denoted as y" = M (.)) Vu Vv. Then, the non non-params label propagation of the k-step is expressed as
ya - graph aggregator (y: --- 10 N..
= = + (1 o) Σ VEN.
1
(5)
vd.da
We follow the approximate calculation of the personalized PageRank matrix Klicpera et al. (2019), where N₂ represents the one-hop neighbors of e, and we default set a = 0.5. Then, we design the homogeneity confidence score (HCS) computed by the number of correct predictions, and the default ratio of the boolean mask is 0.5. Finally, we set thresholds À for the adaptive binary selection of the homogeneity propagation module and heterogeneity propagation module each client. In ex- periments, we default set À 0.6 To demonstrate that AdaFGL is simple yet effective framework, we choose simple models (e.g. MLP or SGC) and FedAvg to achieve federated training. Due the flexibility of AdaFGL, they can be replaced by any other powerful GNNs and federated methods.
From the perspective of FL Non-IID data, we default choose MLP as the base predictor, which is independent of the graph structure. Then we quote the convergence theorem [i et al. (2020) in T rounds and E epochs, the federated global knowledge extractor error bound ffed is expressed as
ffed S +T -
2L
Σ
pi + 6L 8(F 1)? I1 -W1I))
(6)
It assumes that the mapping function satisfies L-smooth and μı-ttrongly convex, where and represent the local random gradient and the degree of model heterogeneity, respectively, y = max(8L/u, },, denotes the divergence of local model, and W* represents the global optima.
We observe that the base predictor error bound is mainly determined by the differences in the node feature distributions, and the model performance will be further hurt if the graph structure is con- sidered. Therefore, we are motivated to propose adaptive propagation mechanisms. Specifically, we implement the binary selection of the homogeneity propagation module heterogeneity propaga- tion module in each client by comparing the HCS value and the threshold A. We will describe the technical details of personalized propagation strategies.
3.2
ADAPTIVE HOMOGENEITY PROPAGATION
After that, we use the base predictor to embed local subgraph nodes into the global knowledge space Xglobal and improve the accuracy with the local homogeneous structure. The motivation behind it is that the feature propagation satisfying homogeneity has a significant positive impact on prediction performance, which has also been confirmed in many recent research works Zhang et al. (2022a); WWang & Leskovec (2020). Hence we expect to utilize local smoothing features to correct predictions. Then, we first define the homogeneous feature propagation
(k) smooth = graph - operator(A (A) (0) Vk 1.....K
Hoomo message updater(X smooth) = ( smoothh);
(R)
(k)
where graph operator(-) represents the graph operator in feature propagation, default to
use symmetric normalized adjacency as shown in Eq. x smooth represents the local smoothing features after K-steps propagation, message updater denotes the model training process, and we use fo to represent the linear regression or MLP with parameters of O.
In order correct the global embedding and local information, mechanism and online distillation to achieve an effective combination of the local smooth structure prior and the global embeddings, which can be written
the local message update
H Local Wiocal X Xglabals
Led Hhomo
H
Based on this, we can make local smoothing information and global embeddings to achieve mutual supervision and end-to-end training by gradient updating. This exploits the local structure informa- tion to reduce the error bound. Notably, the above adaptive process accomplished in the local client and has additional communication costs and privacy concerns.
5

---

Under review as a conference paper at ICLR 2023
3.3 ADAPTIVE HETEROGENEITI PROPAGATION
In contrast, in order to break the heterogeneous structure limitations, we optimize the message- passing framework by embeddings X giobal to detect subgraph heterogeneous patterns. Specifically, we propose an adaptive propagation mechanism by discovering the global dependency of the current node and modeling the positive or negative impact of the messages. Intuitively, we first expect to optimize the propagation probability matrix and align the local structure by global embeddings (0)
X giobbll X
prop
global:
Xalign -graph operator A p
X (0)
Obviously, the original propagation probability matrix introduces high error, improve it by scal- ing the aggregated messages and making it trainable. Formally, let P.j Aprop correspond to the i-th row and j-th col of A Aprop: define the scaling operator d; = dis(P P.y) for j * where dis(-) is a distance function or a function positively relative with the difference, which can be implemented using identity distance. Thus the corrected propagation matrix is expressed prop pop /ddd 'dd diag(A)) prop))
(10) The purpose of it is to measure the global dependency of the current node through the probability difference. Then, we further model the positive and negative impacts of the messages to implement effective aggregation, which is formally represented as follows
H (1) WH 1)
A
(1) prop
A (1-1) + 3 H (HOHO)
H ( PoSign A prop
H
H neg
NeSign( A (1) H
(11)
pos
prop
H (++1 H
+
H
H
where H Xalign. PoSign(-) and NeSign(-) represent the trainable adaptive propagation prob- abilities, it can be replaced by any reasonable nonlinear activation function. Here we analyze the error bound for the above adaptive heterogeneous propagation mechanism. The proof of the follow- ing theorem and reasonable assumptions are given in Appendix. A.
Theorem 3.1 Suppose that the latent ground-truth mapping & X - y from node features to node labels is differentiable and satisfies L-Lipschitz constraint, the following approximation error is
Σ (()(H jAi
H
(Pos (1) &Nggi H
i7i
[llealll Epi, 0 (1 H HH + -0
where * represents the global optimal, e denotes immediate neighbors error. O(-) denotes a higher order infinitesimal, & and k represent propagation matrix and model differences. respectively.
The core of the above propagation mechanisms is to generate embeddings based on other nodes in the embedding space. other words, it means that any node representation can be mapped to a linear combination of existing node representations, which has been applied in many studies Zheng al. (2022a): Yang al. (2022). However, most of the methods use ranking mechanisms for representation and fail to consider modeling propagation processes, which has limitations.
4 EXPERIMENTS
In this section, we conduct experimental analysis on five benchmark datasets with community split and structure Non-III settings to validate the effectiveness of AdaFGI. We aim to answer the following five questions. Q1: Compared with other state-of-the-art FGL baselines, can AdaFGL achieve better predictive accuracy in the community split setting? Q2: How does structure Non- IID influence existing methods and can AdaFGL improve it? Q3: Are knowledge distillation and message detection working in adaptive propagation mechanisms? Q4: Why AdaFGL achieve desirable predictions utilizing the interactions between decoupled modules? Q5: Compared with existing FGL methods and heterogeneous GNNs, what are the advantages of AdaFGL.?

---

Under review as a conference paper at ICLR 2023
The results of test accuracy based on Cora and Chameleon by implementing the community split: mean accuracy + standard deviation. The best results are shown bold.
Table 3:
Cora
Chameleon Client5
Community Client3
Client5
Client10
Client3
Clientl0
FedMLP
63.65+1.03
64.91=1.33
7.24
44.88+0.97
42,46#1.44 1.22
42.88=1.40
FedSGC
81.71=0.06
81.58=0.12
82.07=0.23
33.57+0.23
30.4440.21
30.03+0.19
FedNLGNN
82.16+1.01
82.47=0.88
84.04+1.31
55.92+1.92
13.94+1.54
39.31+3.18
FedGGCN
82.7940.27
1..1
82.80+0.97
16.16+1.43
55.59=1.11
41.52:1.25
FedGI.
81.47+0.76
82.88+1.09
83.01+1.61
48. 18.13:1.23
42.62+2.06
39.95+1.21
GCFL+ 83.9240.17
83.98+1.00
84.53+0.30
41.8540.43
35.85=0.93
35.04=0.71
FedSage+
82.80+0.63
83.06+0.55
85,49+0.91
34.16+1.67
53.08+1.79 .79
50. 1.9.95
w/o HomoKD
83.22#0.54
83.24=1.68
85,51=0.98
60.19E2.14 89,74
14,43+1.52
w/o HeteTA
84.91
8..87+1.75
86.47=0.83
57.98+1.2 1.27
1.39
51,28 1.06
AdaFGL
84.9120.57
85.87+1.75
86.89+1.02
59.74
60.19+2.14
5..43+1.52
Table 4:
The results of test accuracy are based Cora and Chameleon by implementing the
structure Non-IID: mean accuracy + standard deviation. The best results are shown in bold.
Cora Client5
Chameleon Client5
Non-III
Client3
Client10
Client3
Client10
FedMLP
69.0240.82
71.16=1.10
74.90=
47.95+0.98
17.10
18.10
FedSGC
65.1640.20
73.10+0.06
70.98+0.39
26.9240.42
28.08=0.39
25.3240.21
FedNIGGNN
68.21+0.78
72.93=0.72
76.40#1.10
53.74+2.34
56.75=1.61
47.98+1.45
FedGGCN
75.19
1..20#1.04
78.78=0.98
55.59+0.84
60.51+1.58
49.90#1.17
FedGL
67.8620.73
74.62+1.14
71.82+0.58
54.53+1.93
55.59+2.23
49.79+1.91
GCFL+ 68.81+0.36
74.15=0.64
72.05=0..39
41.15+0.83
44.6420.66
48.16+0.61
FedSage+
77.90+0.89
76.83=0.91
80.81=0.74
49,80+1.85
52.21=1.96
53.21+2.33
w/o HomoKD
78.34+0.43
80.54+0.97
80.38+1.28
60.89+1.12
1..85+1.83
59.89+2.37
w/o HeteTA
78.87+0.41
80.92=0.89
80.9640.87
58.75+0.99
1..28#1.66
58.72+2.18
AdaFGL 79.0340.46
81.15+1.18
82.32+1.34
61.05+1.16
68.41+1.97
60.2842.49
4.1 EXPERIMENTAL SETUP AND BASELINES
Existing FGL methods implement data partitioning by community split Wang et al. (2022b). We fol- low it while proposing more convincing strategy structure Non-IID. Due to space limitations, the implementation details of the structure Non-IID can be found in Appendix, A.3 and Appendix. [A.6] To demonstrate the effectiveness of AdaFGL, we combine powerful GNNs with FedAvg the rep- resentative methods. Mcanwhile, we compare the recently proposed FGL methods such as FedGL, FedSaget, and GCFL+ FedSGC efficiently exploits the local structure prior by performing fea- ture propagation. FedNLGGNN implements node embeddings by MIP or GCN to discover potential neighbors. FedGGCN further exploits the relationship between over-smoothing and heterogene- ity to achieve weighted propagation. FedGL aims to optimize the local model performance using global information, is essentially graph structure learning without overlapping nodes. FedSage+ performs local graph augmentation to improve prediction performance. GCFL+ implements the clustering process to perform the personalized update mechanisms. More details about baseline methods can be referred Appendix. A.2
4.2 OVERALL PERFORMANCE
We first present the complete results on Cora and Chameleon in Table. 4 and Table. 3 which are two representative homogeneous and heterogeneous datasets. Due the space limitation, the de- tails about the experiment environment and results in other datasets can be found in Appendix Notably, since we randomly inject homogeneous or heterogeneous information into the structure Non-IID data partitioning process, the model performance does not directly relate to the number of clients. Meanwhile, in the community split setting, the process of model aggregation by mul- tiple clients to achieve federated learning be considered ensemble learning. Therefore, the prediction performance gets better with the increasing number of clients in some cases.
To answer Q1, Table. 3 shows the comparison results with the baseline methods in community split setting. For the homogeneous dataset Cora, compared with the most competitive FGL methods, AdaFGI. achieved accuracy gains of 1.18%, 2.25%, and 1. 1.64% in multiple client settings, respec-
7

---

Under review as a conference paper at ICLR 2023
Cora
PubMed
Chameleon
Squirrel
PER
Local Accuracy
Fezzk GELA
dola Ous
Dutt
Dui
Pefagge
Figure 4:
The results based on two data partitioning methods on 10 clients, where the upper part represents structure Non-IID and the lower part represents community split.
ori (Homogeneiit)
Federated Extractor
Adapative Propagation
Ori (Heterogenalty)
Rederated Extractor
Adapative Propagation
Nodes
Nodes
Nodes
Nodes
Nodes
Nodes
Figure 5: The heat maps of nodes similarity on PubMed for 10 clients. Homogeneity and hetero-
geneity represent local structure assumptions, respectively. Dark color indicates high similarity.
tively. Meanwhile, AdaFGL exceeds the best methods among all considered baselines on the het- erogeneous datasets by margin of 6.37% 8.52%. In the community split setting, we improve the prediction accuracy by utilizing the local smoothing prior and adaptive propagation mechanisms.
To answer Q2, We demonstrate the performance of existing methods the face structure Non-IID challenges in Table. 4 Although FedGGCN performs well in general, it cannot obtain competitive performance. Despite FedSage+ achieving effective local graph augmentation by sharing global data, structure Non-IID is natural challenge, and this weakness is amplified when heterogeneity is high. In contrast, our method achieves performance gains of 1.45%, 3.77%, and 1.87% compared to the highest prediction accuracy. Impressively, AdaFGL improves performance by 9.82%, 13.06%, and 13.29% in the structure Non-IID setting for the heterogeneous dataset Chameleon. From the observation of the comparison results with the baselines, our method has significant advantages, especially in terms of robustness and impressive performance.
4.3 ABLATION EXPERIMENTS
To answer Q3, we present the ablation experiment results Table. Table. where HomoKD represents the online distillation in the homogeneous propagation module and Te represents the trainable probability propagation matrix in the heterogeneous propagation module. We observe that the online distillation enhances Homogeneous propagation by combining local smoothing features and local embeddings, can effectively improve model performance without adding additional com- putation costs. In essence, it achieves mutually supervised end-to-end learning of global and local information. Furthermore, the trainable probability propagation matrix optimizes the heterogene- ity propagation module. learns the global optimal propagation mechanism and detects positive and negative messages to generate embeddings. HeteTA can discover the global dependence of the current node and achieve effective message aggregation, which proved by Theorem. 3.1
4.4 VISUALIZATIONN AND EXPLAINABILITY ANALYSIS
To answer Q4, present the local prediction accuracy trends with the competitive baseline methods Fig. 4 According to it, we can notice that our method achieves the best performance in most cases under both community split and structure Non-IID data settings, while the overall trend is optimized. Due to space limitations, the relevant experimental results about the hyperparameter sensitivity analysis experiments AdaFGL and conclusions can be found in Appendix. A.5
In order to illustrate the effectiveness of the federated global knowledge extractor and the adaptive propagation mechanisms, also analyze the explainability by presenting the heat maps shown
8

---

Under review as a conference paper at ICLR 2023
Table 5: A summary of very recent FGL methods and our approach.
Method
Type
Exchange Messages
Structure Non-IID
FedSage+
Augmentation
Model Params (GraphSAGE., NeighGenn) Node Embeddings
K
FedGL.
Augmentation
Model Params (Lincar Regression or MLP)
X
GCFL+
Personalization
Model Params (Linear Regression or MLP), Model Gradient
X
Ours
Personalization
Model Params (Linear Regression or MLP)
Table 6: A summary of powerful GNNs in heterogeneous graph and our approach.
Method
Neighbor Discovery
Message Combination
Strategy
Heterogeneity
MI.P
X
X
Ignore Structure, Update Function
X
FedGL.
X
Graph Strueture Learning, Update Function
FedSage+
/
Graph Augmentation. Update Function
NLGNN
/
Embedding Model, Similarity Ranking
GGCN
Nodal Degree Weighting. Update Function
Ours
7
Trainalee Propagation Matri
in Fig. [ We perform structure Non-III partitioning for 10 clients on PubMed, then select the client with the highest number of nodes with homogeneity and heterogeneity. Based on this, we randomly sampled 20 nodes to obtain the similarity score by computing the embedding transpose. From the observation of the results, we notice that the federated global knowledge extractor only obtains fuzzy results and cannot be optimized for the local subgraphs. Fortunately, we achieve an effective combination of global knowledge and local subgraph structure prior to obtaining explicit node embeddings, which is also demonstrated through the final output in Fig.
4.5 METHODS COMPARISON
To answer Q5, review three recent FGL methods and analyze our approach to them in terms of three aspects: method type, exchange messages, and the ability to solve structure Non-IID problems as shown in Table Obviously, although FedSage+ can achieve competitive results, it introduces significant communication costs and privacy concerns. Specifically, FedSage+ trains two models and thus has communication costs, while implementing cross-client information sharing to improve pre- dictive performance, which no doubt increases privacy concerns. GCFL+ has limitations in model selection leads to its failure to handle the structure Non-IID problem subgraph learning. In our experiments, FedGL is essentially local graph structure learning process. In contrast, our approach can utilize the computational capabilities of the local system while minimizing communication costs and privacy concerns. More experimental details can be found in Appendix. A.4
Then, we compare the effectiveness of existing GNNs and our approach to handling heterogeneous graph, which focuses two points: Neighbor Discovery and Message Combination, which is shown in Fig. 6 We observe that MLP ignores graph structure prior which leads to the failure to handle heterogeneous graphs. Although FedGL. and FedSage+ can improve this problem by utilizing global information for local graph augmentation, the limitations of propagation lead to the fact that they are still not the best solutions. Notably, they cannot handle the structure Non-IID problem in FGL. Although NLGNN and GGCN attempt to solve the heterogencous structure problem, they cannot be directly applied in FGL. Therefore, we are motivated by these methods and propose adaptive propagation mechanisms to improve the performance, which has been validated to be effective.
CONCLUSION
In this paper, we discover and define the structure Non-III problem in FGL, which is a new chal- lenge for existing methods. Based on this, we propose a new paradigm AdaFGL for more general federated data settings. Specifically, we investigate the structure Non-IIID problem in FGL for sup- plementing the existing community split data partitioning approach, which is a more practical feder- ated data setting. To implement effective FGL on heterogeneous distributed subgraphs, we propose AdaFGL which consists of the federated global knowledge extractor and adaptive propagation mod- ules. It combines FL and GNNs tightly and benefits from their evolution. Extensive experiments based on the community split and structure Non-IID data settings demonstrate the effectiveness of AdaGFL. We believe that the ability to fully utilize the graph structure information is the key to achieving efficient FGL, thus the research graph structure in FGL is promising direction.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, KDD, pp. 2623-2631, 2019.
Jinheon Back, Wonyong Jeong, Jiongdao Jin, Jachong Yoon, and Sung Ju Hwang. Personalized subgraph federated learning. arXiv preprint arXiv:2206. 10206, 2022.
Chuan Chen, Weibo Hu, Ziyue Xu, and Zibin Zheng. Fedgl: federated graph learning framework with global self-supervision. arXiv preprint arXiv:2105.033 03/0000,0077... 2021.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. International Conference on Learning Representations, ICLR, 2021.
Thomas Gaudelet, Ben Day, Arian R Jamasb, Jyothish Soman, Cristian Regep, Gertrude Liu, Jeremy B R Hayter, Richard Vickers, Charles Roberts, Jian Tang, David Roblin, Tom L Blun- dell, Michael M Bronstein, and Jake Taylor-King, Utilizing graph machine learning within drug discovery and development. Briefings in Bioinformatics, 22(6). 05 2021.
Chaoyang He, Songze Li, Jinhyun So, Xiao Zeng, Mi Zhang, Hongyi Wang, Xiaoyang Wang, Pra- neeth Vepakomma, Abhishek Singh, Hang Qiu, et al. Fedml: A research library and benchmark for federated machine learning. arXiv preprint 2rXiv:2007.135/1 2020.
Chaoyang He, Keshav Balasubramanian, Emir Ceyani, Carl Yang. Han Xie, Lichao Sun, Lifang He, Liangwei Yang, S Yu Philip. Yu Rong, et al. Fedgraphnn: A federated learning benchmark system for graph neural networks. In International Conference on Learning Representations, ICLR Workshop Distributed and Private Machine Learning, 2021.
Dongxiao He, Chundong Liang, Huixin Liu, Mingxiang Wen, Pengfei Jiao, and Zhiyong Feng- Block modeling-guinn guided graph convolutional neural networks. Proceedings of the AAAI Confer- on Artificial Intelligence, 36(4):4022 4029, Jun. 2022.
Youpeng Hu, Xunkai Li, Yujie Wang, Yixuan Wu, Yining Zhao, Chenggang Yan, Jian Yin, and Yue Gao. Adaptive hypergraph auto-encoder for relational data clustering. IEEE Transactions on Knowledge and Data Engineering, 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, ICLR, 2017.
J. Klicpera, A. Bojchevski, and S Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, ICLR, 2019.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, ICLR, 2020.
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algo- rithmic applications. Combinatorica, 15(2):215-245, 1995.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE Transac- fions on Pattern Analysis and Machine Intelligence, pp. 1-1, 2021.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficie learning of deep networks from decentralized data. Artificial intelli- gence and statistics, pp. 1273-1282, 2017.
Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. Proceedings of the 16th inter- national conference World Wide Web, WWW, pp. 201-210, 2007.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang. Yu Lei, and Bo Yang. Geom Geo:-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, ICLR, 2020.
10

---

Under review as a conference paper at ICLR 2023
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Jour- nal of Complex Networks, 9(2), 05 2021.
Jonathan Shlomi, Peter Battaglia, and physics. Machine Learning: Science and Technology, 2(2):021001, jan 2021.
Vlimant. Graph neural networks in particle
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propa- gation. arXiv preprint arXiv:2002.06755, 2020.
Tao Wang, Di Jin, Rui Wang, Dongxiao He, and Yuxiao Huang. Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4):4210-47) 421804 Jun. 2022a.
Zhen Wang, Weirui Kuang, Yuexiang Xie, Liuyi Yao, Yaliang Li, Bolin Ding, and Jingren Zhou. Federatedscope-gnnt Towards unified, comprehensive and efficient package for federated graph learning. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD,, pp. 41 4024120, 2022b.
Chuhan Wu, Fangzhao Wu, Yang Cao, Yongfeng Huang, and Xing Xie. Fedgnn: Federated graph neural network for privacy-preservigg recommendation. arXiv preprint arXiv:2102.04925, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinherger. Sim- plifying graph convolutional networks. International conference on machine learning, ICML, 2019.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: A survey. ACM Comput. Surv., mar 2022. ISSN 0360-0300.
Han Xie, Jing Ma, Li Xiong, and Carl Yang. Federated graph classification over non-iid graphs. Advances in Neural Information Processing Systems, NeurIPS, 34, 2021.
Yujun Yan, Milad Hashemi. Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint 1eXiv:2102.06462.. 2021.
Tianmeng Yang, Yujing Wang, Zhihan Yue, Yaming Yang, Yunhai Tong, and Jing Bai. Graph pointer neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8): 8832-8839, Jun. 2022.
Z. Yang, W. W. Cohen, and R. Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on International Conference on Machine Learning, ICML, 2016a.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. Proceedings of the 33rd International Conference on International Conference Machine Learning, ICML, pp. 40-48. JMLR.org, 2016b.
Ke Zhang, Carl Yang, Xiaoxiao Li, Lichao Sun, and Siu Ming Yiu. Subgraph federated learning with missing neighbor generation. Advances in Neural Information Processing Systems, NeurIPS, 34, 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, NeurIPS, 31, 2018
Wentao Zhang, Yu Shen, Zheyu Lin, Yang Li, Xiaosen Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Pasea: A graph neural architecture search system under the scalable paradigm. In Proceedings of the ACM Web Conference, WWW, pp. 1817 1817-1828. 2022a.
Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD, pp. 4570, New York, NY, USA, 2022b.
11

---

Under review as a conference paper at ICLR 2023
Wenqing Zheng, Edward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete or missing neighbor- hoods. In International Conference Learning Representations, ICLR, 2022a.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey, arXiv preprint arXiv:2202.070883 2022b.
A APPENDIX OUTLINE
The appendix is organized as follows:
A.1 Theory error bounds for adaptive heterogeneous propagation modules.
A.2 More details about the compared baselines.
A.3 Datasets description and structure Non-III) data setting.
A.4 Communication costs analysis.
A.5 Hyperparameter sensitivity analysis.
A.6 Experimental environment and additional base results.
A.1 THEORY ERROR BOUNDS FOR ADAPTIVE HETEROGENHOUS PROPAGATION
To demonstrate the effectiveness of the adaptive heterogeneous propagation module, we prove its error bound. We first make the reasonable following assumption and definitions.
Assumption A.1 & is L-smooth, Vx1,
dom ())
((x1) < ((x2) + (x1 x2) (x)())
+ 2 [|x]
Xx
Then we quote the embedding method theorem Linial al. (1995).
Definition A.1
Given two metric spaces (V, d) and (Z, d and mapping function V 2, the distortion Edistor is definied as Yu, V, e/ddistor d( v) S d' (#(u), ((v)) S d(u, v).
Theorem A.1 (Bourgain theorem) Given any finite metric space (V,d) with V there exists an embedding of (V, d) into & under any Lp metric, where k Ollgg n), and the distortion of the embedding is nl.
defines the distortion (log n) the embedding space (V, d) for mapping methods satisfying the above conditions. Based on this, we consider a graph G with fixed structure represented by A = D-1/2AD 1/2 embeddings represented with H in the forward propagation, and nodes mapping function & (H), which satisfies the Theorem, A. it can be expressed
(H) ((HHS dH,, S1.2)
d(H, Slogn.llog
k
where d(H, St,) min d(H, u... St C Vii 1,2, Jogn,j 1, 1,2, log repre- sents clog n random sets, where e constant. is chosen by including each point in V indepen- dently with probability 1/25. Then motivated by Xie et al. (2021) and the above conclusions, we have the following model weights difference proposition.
Proposition A.1 Assume the propagation probability matrix, hidden embeddings, and label differ- ence with global optima J and local model Jo are bounded with
P Pl
Ep 112 I cp
H' - H = EH 2 < CH
2
|| 1l2 E
12

---

Under review as a conference paper at ICLR 2023
Based on this, given that we have H H H
H
H H (H
EH)
|
Let
X X = SH then
E || S cH/ōε
би we choose SGC Wu et al. (219 for the forward
propagation, the model weights difference with the inftuence of feature difference represented
= l1. - foll2 =
(PH . (PH)
H H
P Y + Ex) - H P
Y -1--1p 1p
(H
p Ý H
Ex
PP-L + (PH PE - -
H
P
(PH) 112 EHEY
(PH)
dx
Similarly, there exists
[P P
|P
(P EPP)
|PLip 1
óp, and
|P- - Ep all S cp /pp
we can obtain the model weight differences with the influence of structure difference.
Φ == 115 - Soll2
(P'H) . (PH) -
2
H
p xx+ -P- 1-11)
+ Ep-1 ) + Ex) - -p-1- --1ip
H
P 1 Ep-1 Y + Ep-1 Fay
H
1|2
cy
||P
11
cP óp
Y 2
+
épe óp
Proof A.1 Here, based on the Eq.
we consider the adaptive heterogeneous propagation process
H(+1)
(
H neg
pos
H PoSign A
(
H + NeSign A
H
prop
prop
H
PoSign
(11) 3WH (1 11) (WH D)T) (()
prop
NeSign (A (oo + SWH (WH(" H
Take node an example, given that 4(-) is differentiable, where contains the gradient update of the model difference 6. Meanwhile, in order to quantify the difference between our trainable propagation probability matrix and the global optimum, we define
Ki [i
A
prople:
Σ BWH (WH WHH
where P represents the optimal propagation probability matrix. Then, Pos, Neg denote the positive and negative message propagation weights P Aprop. there exist
(1)
H [++1]
Σ P (H
H + Σ (Pos (1) + (egg))H
jti
Ki + P + Σ (Pos!) (1) + Neg!")
(!))
jti
13

---

Under review as a conference paper at ICLR 2023
where Posij (1)
Negij
(8)
A propp 9. Then, we perform a first-order Taylor expansion with Peano's
form of remainder at H and consider the model differences
( ((H (H)
Σ
PP;
((H
H + O(IH H("l2))
1+1
$#1
Σ P + Σ P 2
(H) 11)
H Σ
P. 112)
j
Now, let Ejft Pi (H H Ci there exist
P (H()0(H())=
K4 P +
(Pos (1)
Nog!") O
(1)
j7i
jfi
0
Σ
(HH
(H Es + Σ
PI ! (12)
jti
(
Σ
P. (H) - Ki PP +
Σ (Pos +
Negis)
(
Σ
Pi - (111))
a(H 61
IFC
According to Cauchy-Schwarz inequality and propertyi property, we have
(H
( ) ((H
O(HOYT Es
|eell2 S |leell2.
Therefore, the approximation of H
+ Σ zz (Pos !1) + Nog.j H is bounded by
Pt
(HH))
- H Σ (Pos !1) + NNeg H
@4
IPtj (1
H - (1),)) + (H 1
A(H(OTT
(
EPjo (1) H -H) 1.) + +[I (|''l)
+
A(HOT
[|lell2 + EP O H H 11) -
IN
j4s
where H represents the global optimal embeddings. Based on this, we obtain the theory error bound for heterogeneous propagation. From the observation of error bounds, we reveal that in theory, the adaptive heterogeneous propagation process can minimize the immediate neighbors error ei the model difference ó, and the propagation probability matrix difference & to scale the error to improve the predictive performance.
A.2 COMPARED BASELINES
The main characteristic of baselines are listed below:
FedMLP: The combination of FedAvg and MLP, employ two-layer MLP with the hidden dimension of 64. It generates node embeddings based on the original features while ignoring graph structure information in the forward propagation process.
14

---

Under review as a conference paper at ICLR 2023
Table 7:
Statistics of five benchmark datasets.
Datasets
#Nodes
#liges
#Classes
Nodes Homo
Edges Homo
Cora
2708
5278
7
0.83
0.81
CiteSeer
3703
4552
6
0.71
0.74
PubMed 19717
44324
3
0.79
0,80
Chameleon 2277
36101
5
0.25
0.24
Squirrel 5201
217073
5
0.22
0.22
FedSGC: We combine FedAvg and SGC Wu al. (2019), we default to use the 3-layer feature propagation process, which follows the homogeneous assumption and thus fails to deal with hetero- geneous graph.
FedNLGNN: Implementation of NLGNN (NLMLP or NLGCN) Liu et al. (022 1) based on FedAvg, we select the more effective version to present the model performance. depends on the embedding model and suffers from representational limitations.
The combination FedAvg and GGCN Yan et al. (2021), we follow the experimental setup of the original paper much as possible, which can handle heterogeneous graphs effectively, but cannot achieve competitive results on homogeneous graphs.
FedGGCN:
FedGL et al. 2021) As FGL training framework, it strongly relies the overlapping nodes assumption, which in our data setting is essentially local graph structure learning.
GCFL+ Xie et al. (2021): : due to the limitations of personalized techniques in model selection, they cannot fundamentally solve the structure Non-IID challenges.
FedSage+ Zhang et al. 202T): y: It trains NeighGen to achieve local subgraph augmentation by sharing global missing subgraph feature and topology information for the most powerful results, but suffers from privacy leakage risk and additional computational costs.
For fairness, we follow the experimental setup of the baseline methods paper as much as possible, and in other cases, show the best prediction accuracy. In addition, the number of rounds for the above baseline methods is 50, and the local epoch 20.
A.3 DATASETS DESCRIPTION AND STRUCTURE NON-IID DATA SETTING
The statistics of datasets are summarized in Table. 7 which contains both homogeneity and hetero- geneity. In our experiments, use five benchmark datasets containing homogeneity and hetero- geneity, for which details are given below.
Cora, Citeseer, and Pubmed Yang al. (2016b) are three popular citation network datasets. In these three networks, papers from different topics are considered as nodes, and the edges are citations among the papers. The node attributes are binary word vectors, and class labels are the topics papers belong to.
Chameleon and Squirrel
web page datasets collected from Wikipedia Rozemberczki al. (20T), where nodes are web pages on specific topics and edges are hyperlinks between them.
Based this, illustrate the structure Non-IID data partitioning process in detail. The of it is the Dirichlet process He et al. (2020), Its basic analysis is as follows. The pdf of the Dirichlet distribution is defined
II, I(a.) r(E. as)
p(P = (p:)oa)
where a; fai....... .0......000 ax) is the dimensionless distribution parameter, the scale (or concentra- tion) = Σ, a; the base measure (at..... ( a = aq/ and [(n) = (n - 1)!. Dirichlet is a distribution over Multinomials, thus there is E, 1, 0, where pt represents the probability.
15

---

Under review as a conference paper at ICLR 2023
Table 8: The results of accuracy based Cora and CiteSeer by implementing the community split of 10 clients: mean accuracy = standard deviation. The best results are shown in bold.
Dataset
Cora
CiteSeer
Method
# Val Acc
# Test Acc
# Params
# Val Acc
# Test Acc
# Params
FedSage
85.32+0.87
85,49+0.91
x.52 10"
75.49=0.63 16.1540.54
x 107
FedGGCN
82.34:0.84
82 804
5.52 10
75.32+0.95
75.78+1.12
1.42x 106
Ours
87.97=0.98
86.89=1.02
2.88x105
79.63+1.48
7.26x 77.05+1.72
Table 9: The results of accuracy based on Chameleon and Squirrel by implementing the community
split of 10 clients: mean accuracy = standard deviation. The best results are shown in bold.
Dataset
Chamelcon # Test Acc
Squirrel
Method
# Val Acc
Params
Val Acc
# Test Acc
# Params
FedSage
53.4942.06
50.11#1.95
2.44x 10
31.4442.17
31.27#1.93
2.19x 10"
FedGGCN
13.81+1.37
41.52#1.25
8.95 109
35.26+1.10 39.16+1.88
34.10#1.25
8.04 10
Ours
58.06+1.23
54.43+1.52
8.95 10
35.43+2.53
8.04 10
It determines the mean distribution, and the scale affects the variance, then we obtain
04 E(p:) 1 aj
(; a) a3)) Var(p.) 02(0 1)
(0+1)
Coo(pi,P;) 02(0 +1)
aaa
which means that a Dirichlet with small scale 9 favors extreme distributions, but this prior belief is very weak and is casily overwritten by data. As 0 + the covariance 0, the samples - base measure.
Based on this, start sampling the edges determine the attribution of pair of nodes. If conflicting set of nodes exists it is sampled again and finally generates induced subgraphs. Then, randomly inject homogeneous or heterogeneous information based the label prior, which can solve unreal structure loss and enhance structure identity. We propose to set three probabilities Pians Phomos and Phete for each client individually represent the probability of avoiding isolated nodes, increasing homogeneous edges, and increasing heterogeneous edges in the subgraph, respectively. Specifically, Piso represents the probability of isolated nodes generating edges with other nodes, which can effectively be used to prevent the generation of isolated nodes. Phomo applies to the subgraph of clients that are selected to enhance homogeneity, and represents the probability of connection between two nodes with the same label based on the label prior information. Corre- spondingly, Phote represents the probability used to perform the structure information injection for the client subgraph that performs the heterogeneity enhancement.
A.4 COMMUNICATION COSTS ANALYSIS
The advantage of our approach to exploit the local structure prior while making full use of the global information, which considers the characteristics of GNNs. It has the benefit of reducing the communication costs and privacy concerns during the federated training process. Meanwhile, thanks to the utilization of the local structure information, we can obtain models with better representational power to improve the performance. experimental results of AdaFGL with the two most competitive methods, FedSage and FedGGCN, as shown in Tables. A.4 and Table. A4
demonstrate the effectiveness of our method, we provide the
According to the experimental results, we observe that AdaFGL maintains the low communication costs and achieves a satisfying result, which mainly benefits from the utilization of local structure information by the adaptive propagation modules. Compared to FedSage, which is the current most competitive FGL approach, suffers from the performance improvement and communication costs dilemma, which also brings more privacy concerns.
16

---

Under review as a conference paper at ICLR 2023
Cora
Chameleon
0.82
0.69
0.81
0.68
0.80
0.67
0.79
0.66
0.78
0.65
0.10
0.10
KD Loss Ratio
0.08
KD Loss Ratio
0.08
0.06
0.06
0.0
0.2
0.04
0.2
0.04
Propagation Smooth
0.4
0.6
0.02
Propagation Smooth
0.4
0.6
0.02
0.8
1.0
0.00
0.8
1.0
Figure 6: Hyperparameter sensitivity analysis the Cora and Chameleon for 5 clients.
Table 10: The results test accuracy based on CiteSeer and Squirrel by implementing the commu- nity split: mean accuracy + standard deviation. The best results are shown in bold.
CiteSeer ClientS
Squirrel ClientS
Community
Client3
Client10
Client3
Client10
FedMLP
65.8340.66
70.54=1.42
70.8642.03
29.90#0.59
40.89=0.64
30.58+0.70
FedSGC
72.5910.40
73.3120.05
75.68+0.10
29. 29.9840.13
32.59=1.06
27.9620.59
FedNLGNN
71.3540.78
73.1420.89
75.05+0.65
40.79+1.58
14.32+1.66
32.22+1.24
FedGGCN
70.02+0.57
73.30=0.70
75.78+1.12
42.76+0.57
48.45=1.03
34.10#1.22
FelGL
71.57+1.05
72.28=0.62
74.40=0.78
32.45+2.74
35.32+1.04
29 29.9640.56
GCFL+
73.25=00.27
73.30=0.49
76.28=00.6
27.17=0.46
28.03=0.30
27.33+0.39
FedSage+
69.15+0.62
71.88+0.73
75.49+0.63
36.72+1.05
43.65=1.46
31.27+1.93
w/o HomoKD
71.4620.71
74.2620.88
76.12
43.02+1.19
4..38+1.62
35,4342.53
w/o HeteTA
72.57+0.50
73.57+0.39
75.81+1.06
41.9440.71
47.79=1.10
33.16+1.44
AdaFGL 73.6920.65
75.32+0.90
77.05=1.72
43.02+1.19
49.38+1.62
35.4342.53
A.5 HYPERPARAMETER SENSITIVITY ANALYSIS
Here we conduct the hyperparameter sensitivity of AdaFGL, and the experimental results are shown in Fig. 66 In our experiments, we analyze the ratio of online distillation loss in the homogeneous propagation module and the smoothing coefficient of the trainable propagation matrix in the het- erogeneous propagation module. According to the experimental results, we observe that AdaFGI. performs robustness except for extreme cases. Furthermore, we obtain the conclusion from the re- sults generated by the extreme knowledge distillation loss ratios, where the low confidence base predictor results instead affect the homogeneous propagation module. Motivated by this, in order to avoid global embeddings with low confidence from influencing the propagation module, measure the confidence of the global model according to the characteristics of the base predictor.
A.6 EXPERIMENTAL ENVIRONMENT AND ADDITIONAL BASE RESULTS
The experiments are conducted on a machine with Intel(R) Xeon(R) Gold 6230R CPU 2.10GHz, and single NVIDIA GeForce RTX 3090 with 24GB memory. The operating system of the machine Ubuntu 18.0 04.6.. As for software versions, we use Python 3.8. Pytorch 1.0, and CUDA 11.4. To alleviate the influence of randomness, characteristics. The hyper-parameters of baselines are set according the original paper available. We use Optuna Akiba et al. (2019) to implement hyperparameters search. Following the above principles, we present the results of two data partitioning as follows.
repeat each method 10 times and report the statistical
17

---

Under review as a conference paper at ICLR 2023
The results test accuracy based CiteSeer and Squirrel by implementing the streuture Non-IID: mean accuracy + standard deviation. The best results are shown in bold.
Table 11:
CiteSeer Client5
Squirrel Client5
Non-IID
Client3
Client10
Client3
Client10
FedMLP
69.5840.65
1..6
7..92+1.36
30.5940.44
30,42=0.46
30.27:0.97
FedSGC
83.1240.25
46.84=0.05
49.52=0.19
39.06+0.64
28.44=0.67
36.95=0.23
FedNIGGNN
81.35+0.97
70.78=0.98
70.17=0.93
46.82+2.58
37.85=2.17
42.33+1.77
FedGGCN
80.7240.52
10.90=1.54
70.83=1.14
53.3540.95
43.59=0.90
38.2220.82
FedGL
82.91=0.99
69.28=0.70
68.1240.54
35.06+1193
32.88+1.51
33.85+2.49
GCFL+
83,42+0.08
51.70=0.43
53.73+0.82
1640.11
31 31.08=.446
39, 39,90=0.39
FedSage+
69.64x0.63
72.49=0.70
70.92+0.53
34.79+ 1.26
33.37+0.89
34,42+2.87
w/o HomoKD
82.6240.51
72.0320.84
70.89+1.41
55.0641.08
44.9991.088
45.89+1977
HeteTA
83.3740.28
71.15+0.33
70.0940.72
54.2240.87
43.4820.73
1..83+1.39
AdaFGL.
84.05#0.49
72.95=0.92
71.44+1.53
55.2771.13
45.55=1.01
46.15+2.06
Table 12:
The results of test accuracy based on PubMed by implementing the community split and structure Non-IID: mean accuracy + standard deviation. The best results are shown in bold.
PubMed (Community)
PubMed (Non-IID)
Client3
Client5
Client10
Client3
ClientS
Client10
FedMLP
84.10#0.44
81.92=0.70
88.2640.84
85.65#0.29
84.78=0.18
85.29=0.52
FedSGC
76.3740.22
77.3420.31
74.32+0.10
87.05+0.03
87 87.8420.19
59.7240.1 11
FedNLGGN
85.61+0.26
84.04=0.40
85.10=0.46
90.17+0.26
91 91.20>e0.16
85.11
FedGGCN
86. 16.1190.29
86.5320.52
85.6740.35
92.3820.13 90.2440.19
86.5940.63
FelGL
84.17+0.28
82.46=0.15
80.50+0.76
92. 14.0210
86. 16.1690.19 19
85.16+0.11
GCFL+
86.38+0.11
86.38=0.11
86.19=0.05
89.99x0.01
91.88=0.08
74.91
FedSage+
85.33+0.43
85.17=0.49
84.32+0.57
1240.37
84.85=0.17 17
86.93+0.56
w/o HomoKD
84.83+0.21
85.17=0.30
84.99+0.32
92.47+0.08
93.17=0.08
87.87+0.42
w/o HeteTA
86.49+0.26
86.69=0.35
86.01=0.38
94.3240.04
93.98=0.04
86.23+0.25
AdaFGL
86.4920.26
86.6920.35
86.49:0.47
94.55+0.09
95.4550.07
88.3940.37
18


Reviews:
[{"review_id": "lIN7EdP58P", "reviewer": "Reviewer_3ztS", "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": "Instead of taking the community split method used in the previous federated graph learning trend, this paper introduces a new heterogeneous graph split method named structure non-iid and designs a new framework called AdaFGL to deal with the new problem. In the method, a HomoKD part is used for propagating the homogeneity message and a HeteTA part is leveraged to fit with the graph heterogeneity. Some experiments are provided to verify the effectiveness of the proposed method.", "summary_of_the_review": "Learning GNN from heterogeneous data in a federated setup is rather a novel and interesting topic. The authors provide a novel Non-IID setting that is new and different from the previous work. I am not sure about the soundness of this assumption, and the authors only provide datasets split according to this assumption.", "strength_and_weaknesses": "Weaknesses:\n1. How can you justify the correctness of your structure Non-IID assumption? In the current paper, the authors only provided experimental results on the ideal split dataset according to their assumption. \n2. In Table 3, the authors claim that the community split only provides a homogeneous distribution over different clients. The reported results show that AdaFGL obtains *totally the same performance* as the method w/o HeteTA on the Cora dataset. Interestingly, AdaFGL gets *the same performance* as the method w/o HomoKD on the Chameleon dataset. Please check your experimental results or put more effort into providing a reasonable explanation.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "UBlM2JM3MX", "reviewer": "Reviewer_45Ek", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper proposes a novel federated learning (FL) paradigm, AdaFGL, for subgraph learning (i.e., each client holds a subgraph and considers node classification or link prediction task). AdaFGL is designed to handle the structure non-iidness, a graph unique non-iidness issue in FL. The authors conducted extensive empirical studies, which show that AdaFGL outperforms SOTA federated graph learning algorithms under both community-based and non-iid structure splits.", "summary_of_the_review": "I admit that the motivation in this paper is natural and the proposed paradigm seems to be novel. However, due to the weakness in terms of clarity, I cannot fully understand its idea. Although this paper's empirical studies are comprehensive, I still think it has not been above the bar of ICLR. If the authors are willing to giving further explanation, I am likely to change my opinion.", "strength_and_weaknesses": "Strengths:\n1. The proposed paradigm is well motivated, where the structure non-iidness has been discussed in FS-G but has not been well addressed before.\n2. As the node classification task is often a semi-supervised learning setting, the proposed homogeneity confidence score (HCS) is interesting and tends to be helpful. It is novel to me.\n\nWeaknesses:\n1. It is difficult for me to follow the story due to its poor presentation. Specifically, I cannot find the definition of some important matrix such as $X_{\\text{global}}$. Moreover, the bound Eq. 6 and the theorem are very confusing. What is the relationship between base predictor and the HCS, especially considering that MLP does not depend on graph structure? What are the trainable parameters at all? Among them, which are client-wise? In Sec. 3.2, \"base predictor to embed local subgraph nodes into the global knowledge space\" is confusing. The author just analyzed its error bound in Eq. 6.", "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": "94I2OFVeq", "reviewer": "Reviewer_fd7h", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 investigates the Non-IID problems of subgraph Federated Learning (FL), where the authors consider both the well-known homogeneity assumption and the under-explored heterogeneity assumption. To tackle those two problems, the authors propose the global knowledge extractor that uses global data to extract features on the global graph, and the adaptive propagation modules that combine global embeddings and locally updated features for local node representations. The authors verify the proposed method, called AdaFGL, on both homogeneous and heterogeneous graph datasets, showing the effectiveness of their AdaFGL.", "summary_of_the_review": "The idea of considering both homophily and heterophily of graph-structured data for subgraph FL is novel, however, there are many unclear claims and the evaluation setup is not convincing. Thus, I cannot recommend the acceptance. ", "strength_and_weaknesses": "### Strengths\n* The idea of considering both the homophily and heterophily of graph-structured data for subgraph FL is novel and interesting.\n* The proposed AdaFGL outperforms other graph FL baselines. \n\n### Weaknesses\n* The experimental setups for heterogeneous assumption are problematic. In particular, the authors use the Dirichlet process (He et al., 2020) for graph-structured data, to simulate the heterogeneous scenarios. However, this Dirichlet process is not suitable for making heterogeneous subgraph FL. This is because, when the number of clients is relatively large (e.g., 10), the number of edges is often smaller than the number of nodes, which is not realistic. Also, when the number of clients is relatively small (e.g., 3), there are no obvious heterogeneous patterns in the partitioned graphs: the data homogeneity of heterogeneous scenarios is similar to the homogeneous scenarios. Those results are reported in Table 13-22, and, based on that, I don't think the evaluation for heterogeneous assumption is correctly done. \n* The usage of global data is not convincing, and it is not applicable to realistic FL. In FL, data sharing is not possible, therefore, we cannot obtain the global graph consisting of all nodes distributed to all clients. However, the authors propose the FL framework that leverages the global graph. How can we obtain the global graph, when each subgraph cannot share its subgraph to others under the FL assumption? Also, comparing the proposed AdaFGL that uses global graph against other subgraph FL baselines that do not use global graph looks unfair. \n* There are many unclear major-claims, which should be clarified. See Clarity in the below. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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