A Metadata-Driven Approach to Understand Graph Neural Networks
Authors: Ting Wei Li
Qiaozhu Mei
Jiaqi Ma
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Metadata-Driven Analysis
Gini Coefficient of Degree Distribution
TL;DR: We use a metadata-driven approach to understand the graph neural network performance.

Abstract: Graph Neural Networks (GNNs) have achieved remarkable success in various applications, but their performance can be sensitive to specific data properties of the graph datasets they operate on. Current literature on understanding the limitations of GNNs has primarily employed a \emph{model-driven} approach that leverage heuristics and domain knowledge from network science or graph theory to model the GNN behaviors, which is time-consuming and highly subjective. In this work, we propose a \emph{metadata-driven} approach to analyze the sensitivity of GNNs to graph data properties, motivated by the increasing availability of graph learning benchmarks. We perform a multivariate sparse regression analysis on the metadata derived from benchmarking GNN performance across diverse datasets, yielding a set of salient data properties. To validate the effectiveness of our data-driven approach, we focus on one identified data property, the degree distribution, and investigate how this property influences GNN performance through theoretical analysis and controlled experiments. Our theoretical findings reveal that datasets with more balanced degree distribution exhibit better linear separability of node representations, thus leading to better GNN performance. We also conduct controlled experiments using synthetic datasets with varying degree distributions, and the results align well with our theoretical findings. Collectively, both the theoretical analysis and controlled experiments verify that the proposed metadata-driven approach is effective in identifying critical data properties for GNNs.

A Metadata-Driven Approach to Understand Graph Neural Networks
Ting Wei Li University of Michigan tingwl@umich. edu
Qiaozhu Mei University of Michigan qmei Gumi ch. edu
Jiaqi Ma
University of Illinois Urbana- Urbana-Champina Champaign jiaqimaBillines edu
Abstract
Graph Neural Networks (GNNs) have achieved remarkable success in various applications, but their performance be sensitive specifie data properties of the graph datasets they operate on. Current literature on understanding the limitations of GNNs has primarily employed model-driven approach that leverages heuristics and domain knowledge from network science or graph theory to model the GNN behaviors, which is time-consuming and highly subjective. this work, we propose a metadata-driven approach to analyze the sensitivity of GNNs to graph data properties, motivated by the increasing availability of graph learning benchmarks. We perform multivariate sparse regression analysis on the metadata derived from benchmarking GNN performance across diverse datasets, yielding a set of salient data properties. To validate the effectiveness of our data-driven approach, we focus on one identified data property, the degree distribution, and investigate how this property influences GNN performance through theoretical analysis and controlled experiments. Our theoretical findings reveal that datasets with a more balanced degree distribution exhibit better linear separability of node representations, thus leading to better GNN performance. We also conduct controlled experiments using synthetic datasets with varying degree distributions, and the results align well with our theoretical findings. Collectively, both the theoretical analysis and controlled experiments verify that the proposed identifying critical data properties for GNNs.
approach is effective in
1 Introduction
Graph Neural Networks (GNNs), broad family of graph machine learning models, have gained increasing research interests in recent years. However, unlike the ResNet model [14] in computer vision the Transformer model (36] in natural language processing, there has been dominant GNN architecture that is universally effective across a wide range of graph machine learning tasks. This may be attributed the inherently diverse nature of graph-structured data, which results in the GNN performance being highly sensitive to specific properties of the graph datasets. Consequently, GNNs that demonstrate high performance on certain benchmark datasets often underperform on others with distinct properties. For example, early GNNs have been shown to exhibit degraded performance when applied to oon-homophilous graph datasets, where nodes from different classes
are highly interconnected and mixed [45] 46 32
11 99.
However, it is non-trivial to identify and understand critical graph data properties that are highly influential on GNN performance. Current literature primarily employs what we term as a model- driven approach, which attempts model GNN performance using specific heuristics or domain knowledge derived from network science or graph theory [1] Although this approach can offer an in-depth understanding of GNN performance, can also be time-consuming, subjective, and may not fully capture the entire spectrum of relevant data properties.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

To address these limitations and complement the model-driven approach, we propose a metadata- driven approach identify critical data properties affecting GNN performance. With the increasing availability of diverse benchmark datasets for graph machine learning [6 27 we hypothesize that critical graph data properties can be inferred from the henchmarking performance of GNNs on these datasets, which can be viewed as the metadata of the datasets. More concretely, we carry out a multivariate sparse regression analysis on the metadata obtained from large-scale benchmark experiments [27] involving multiple GNN models and variety of graph datasets. Through this regression analysis, we examine the correlation between GNN performance and the data properties of each dataset, thereby identifying set of salient data properties that significantly influence GNN performance.
To validate the effectiveness of the proposed metadata-driven approach, we further focus on specific salient data property, degree distribution, identified from the regression analysis, and investigate the mechanism by which this data property affects GNN performance. In particular, our regression analysis reveals a decline in GNN performance as the degree distribution becomes more imbalanced. We delve deeper into this phenomenon through theoretical analysis and a controlled experiment.
We initiate our investigation with theoretical analysis of the GNN performance under the assumption that the graph data is generated by a Degree- Degree-Corrected Contextual Stochastic Block Model (DC- CSBM). Here, we define DC-CSBM by combining and generalizing the Contextual Stochastic Block Model and the Degree-Corde Corrected Stochastic Block Model [17]. Building upon the analysis by Baranwal al. [3], we establish a novel theoretical result on how the degree distribution impacts the linear separability of the GNN representations and subsequently, the GNN performance. Within the DC-CSBM context, our theory suggests that more imbalanced degree distribution leads to few nodes being linearly separable in their GNN representations, thus negatively impacting GNN performance.
Complementing our theoretical analysis, we conduct a controlled experiment, evaluating GNN per- formance on synthetic graph datasets with varying degree distribution while holding other properties fixed. Remarkably, we observe a consistent decline in GNN performance correlating with the increase of the Gini coefficient of degree distribution, which reflects the imbalance of degree distribution. This observation further corroborates the findings of our metadata-driver driven regression analysis.
In summary, our contribution in this paper is two-fold. Firstly, we introduce a novel metadata-driven approach identify critical graph data properties affecting GNN performance and demonstrate its effectiveness through a case study on a specific salient data property identified by our approach. Secondly, we develop an in-depth understanding of how the degree distribution of graph data influences GNN performance through both a novel theoretical analysis and a carefully controlled experiment, which is of interest to the graph machine learning community in its own right.
2 Related Work
2.1 Analysis on the Limitations of GNNs
There has been wealth of existing literature investigating the limitations of GNNs. However, most of the previous works employ the model-driven approach. Below we summarize a few well- known limitations of GNNs while acknowledging that exhaustive review of the literature is impractical. Among the limitations identified, GNNs have been shown to be sensitive to the extent of homophily in graph data, and applying GNNs to non-homophilous data often has degraded performance [ 9 23 46 45). In addition, wwooshno phenomenon where GNNs lose their discriminative power with deeper layers 20 B4 o is primary concern particularly for node-level prediction tasks where distinguishing the nodes within the graph is critical. Further, when applied to graph-level prediction tasks, GNNs are limited by their ability to represent and model specific functions or patterns on graph-structured data, an issue often referred to as the expressiveness problem of GNNs. [4 30 25 43 Most of these limitations are understood through model-driven approach, which offers in-depth insights but is time-consuning and highly subjective. In contrast, this paper presents a metadata-drivel approach, leveraging metadata from benchmark datasets to efficiently screen through a vast array of data properties.
2

---

2.2 Data-Driven Analysis in Graph Machine Learning
With the increasing availability of graph learning benchmarks, there have been several recent studies that leverage diverse benchmarks for data-driven analysis. For example, Liu et [24] presents principled pipeline to laxonomize benchmark datasets. Specifically, by applying number of different perturbation methods on each dataset and obtaining the sensitivity profile of the resulting GNN performance on perturbed datasets, they perform hierarchical clustering on these sensitivity profiles to cluster statistically similar datasets. However, this study only aims to categorize datasets instead of identifying salient data properties that influence GNN performance. Ma et al. [27] establish Graph Learning Indexer (GLI) library that curates a large collection of graph learning benchmarks and GNN models and conducts large-scale benchmark study. We obtain our metadata from their benchmarks. Palowitch et al. 31 introduce GraphWorle library that can generate diverse synthetic graph datasets with various properties. These synthetic datasets can be used to test GNN models through controlled experiments. In this paper, we have used this library to verify the effectiveness of the identified critical data properties.
2.3 Impact of Node Degrees on GNN Performance
There have also been a few studies investigating the impact of node degrees on GNNs. In particular, it has been observed that within a single graph dataset, there tends to be an accuracy discrepancy among nodes with varying degrees [35] 22
33 Typically, GNN predictions on nodes with lower degrees tend to have lower accuracy. However, the finding of the Gini coefficient of the degree distribution as a strong indicator of GNN performance is novel. Furthermore, this indicator describes the dataset-level characteristics, allowing comparing GNN performance across different graph datasets. In addition, this paper presents a novel theoretical analysis, directly relating the degree distribution to the generalization performance of GNNs.
44
3
A Metadata-Driven Analysis on GNNs
3.1 Understanding GNNs with Metadata
Motivation. Real-world graph data are heterogeneous and incredibly diverse, contrasting with images or texts that often possess common structures or vocabularies. The inherent diversity of graph data makes it particularly challenging, if not unfeasible, to have one model to rule all tasks and datasets in the graph machine learning domain. Indeed, specific types of GNN models often only perform well on a selected set of graph learning datasets. For example, the expressive power of GNNs 41 is primarily relevant to graph-level prediction tasks rather than node-level tasks higher-order GNNs with improved expressive power are predominantly evaluated on graph-level prediction tasks (30, 41 As another example, several early GNNs such as Graph Convolution Networks (GCN) 19 or Graph Attention Networks (GAT) (37 only work well when the graphs exhibit homophily [45). Consequently, it becomes crucial to identify and understand the critical data properties that influence the performance of different GNNs, allowing for more effective model design and selection.
The increasing availability of graph learning benchmarks that offer a wide range of structural and feature variations [6 27 presents a valuable opportunity: one can possibly infer critical data properties from the performance of GNNs on these datasets. To systematically identify these critical data properties, we propose to conduct a regression analysis on the metadata of the benchmarks.
Regression Analysis on Metadata. In the regression analysis, the performance metrics of various GNN models on each dataset serve the dependent variables, while the extracted data properties from each dataset act as the independent variables. Formally, we denote the number of datasets as n, the number of GNN models g, and the number of data properties p. Define the response variables {y: Jeelg to be GNN model performance operated on each dataset and the covariate variables {x, ) to be properties of each dataset. Note that y; E R", Vi E [q] and x; E I Vj E [p]. For ease of notation, we define Y (y1...., Yy) E IRax be the response matrix of n samples and g variables, and X (K,,..,, Xp) E Ruxp to be the covariate matrix of n samples and variables.
3

---

Given these data matrices, we establish the following multivariate linear model to analyze the relationship between response matrix Y and covariate matrix X, which is characterized by the coefficient matrix B.
Definition 3.1 (Multivariate Linear Model).
XB + W,
(1)
where B E RPxq is the coefficient matrix and W (WI,...,g)) E R2x is the matrix of enror terms.
Our goal is to find the most salient data properties that correlate with the performance of GNN models given number of samples. To this end, we introduce two sparse regularizers for feature selections, which leads to the following Multivariate Sparse Group Lasso problem.
Definition 3.2 (Multivariate Sparse Group Lasso Problem).
1 Y XBI2 + + BlI + Ag [
argmin B 2n
(2)
where |BI| E Eÿ= Byy is the L1 norm of B, Bll2, Ei= group norm of B, and \1, Ag > 0 are the corresponding penalty parameters.
Ei= B2y is the L2,1
In particular, the L1 penalty encourages the coefficient matrix B to be sparse, only selecting salient data properties. The L2, penalty further leverages the structure of the dependent variables and tries to make only small set of the GNN models' performance depends on each data property, thus differentiating the impacts on different GNNs.
To solve for the coefficient matrix in Equation - using matrices Y and X input. To ensure proper input for the MSGLasso solver [2]] have preprocessed the data by standardizing the columns of both Y and X.
we employ an R package, MSGLasso 21],
3.2 Data Properties and Model Performance
Next, introduce the metadata used for the regression analysis. We obtain both the benchmark datasets and the model performance using the Graph Learning Indexer (GLJ) library (7).
Data Properties. We include the following benchmark datasets in regression analysis: cora
42
citeseer 42 pubmed 422 texas [33], cornell [33 wisconsin
33 actor [33], squirrel 33
chameleon 33 arxiv-year [23 snap-patents 233 penn94 223 pokec [3]. genius 23 and
twitch-gamen gamers 233 For each graph dataset, we calculate 15 data properties, which can be categorized
into the following six groups:
Basic: Edge Density, Average Degree, Degree Assortativity;
Distance: Pseudo Diameter;
Connectivity: Relative Size of Largest Connected Component (RSLCC);
Clustering: Average Clustering Coefficient (ACC), Transitivity, Degeneracy;
Degree Distribution: Gini Coefficient of Degree Distribution (Gini-Degree);
Astribute: Edge Homogeneity, In-Feature Similarity, Out-Feature Similarity, Feature Angular SNR, Homophily Measure, Attribute Assortativity.
The formal definition of these graph properties be found in Appendix
Model Performance. For GNN models, we include GCN 19, GAT 37 GraphSAGE [3]
MoNet 29), MixHop 11. and LINKX (23 into our regression analysis. We also include a non-graph
model, Multi-Layer Perceptron (MLP). The complete experimental setup for these models can be
found in Appendix B

---

The estimated cocfficient matrix B of the multivariate sparse regression analysis. Each entry indicates the strength (magnitude) and direction (+, -) of the relationship between graph data property and the performance of GNN model. The six most salient data properties are indicated in bold.
Table 1:
Graph Data Property
GCN
GAT
GraphSAGE
MoNet
MixHop
LINKX
MLP
Edge Density
0
0
0
0
0.0253
0.0983
Average Degree
0.2071
0.1048
0.1081
0
0.3363
0 -0.6119
Pseudo Diameter
0
-0.349
-0.1531
0
-0,4894
-0,3943
Degree Assortativity
0
0
-0.0744
0
RSLCC
0.1019
0
0.0654
0
0.1309
0 -0.0502
ACC
0
0
0
0
0
Transitivity
-0.0518 0
0
-0.1372
0
0.2311
0
Degeneracy
0
0
0
0
-0.1657
Gini-Degree
-0.4403
-0.2961
-0.3267
-0.2944
-0.4205
-0.367
-0.1958
Edge Homogeneity
0.7094
0.4705
0,7361
0,8122
0.6407
0,2006
0.4776
In-Feature Similarity
0.3053
0.1081
0.1844
0,1003 0
0.4613 0
0.6396
0.2399
Out-Feature Similarity
0
0
0
0 0.3731
Feature Angular SNR
0.2522
0.2506
0
0.2381
0.3563
Homophily Mcasure
0
0.4072
0
0
Aurrbbuee Assortativity
0
0
3.3 Analysis Results
The estimated coefficient matrix B is presented in T As can be seen, the estimated coefficient matrix is fairly sparse, allowing us identify salient data properties. Next, we will discuss the six most salient data properties that correlate to some or all of the GNN models' performance. For the data properties that have an impact on GNNs performance, we call them Widely Influential Factors; for the data properties that have an impact on over one-half of GNNs' performance, we call them Narrowly Influential Factors. Notice that the (+, -) sign after the name the factors indicates whether this data property has positive negative correlation with the GNN performance.
Widely Infiuential Factors. We discover that the Gini coefficient of the degree distribution (Gini- Degree), Edge Homogeneity, and F--Fetture Similarity impact all GNNs model performance consis- tently.
Gini-Degree (-) measures how the graph's degree distribution deviates from the perfectly equal distribution, i.e., regular graph. This is erucial data property that dramatically influences GNNs' performance but remains under-explored prior literature.
Edge Homogeneity (+) a salient indicator for all GNN models' performance. This phe- nomenon coincides with the fact that various GNNs assume strong homophily condition 28
to obtain improvements on node classification tasks [13 19 37].
In-feature Similarity (+) calculates the average of feature similarity within each class, Under the homophily assumption, GNNs work better when nodes with the same labels additionally have similar node features, which also aligns with existing findings in the literature (15).
Narrowly Influential Factors. We find that Average Degree, Pseudo Diameter, and Feature Angular SNR are salient factors for subset of GNN models, although do not yet have good understanding on the mechanism of how these data properties impact model performance.
Average Degree (+) is more significant for GCN, GraphSAGE, MoNet, and LINKX.
Pseudo Diameter (-) is more significant for GAT, GraphSAGE, MixHop, LINKX, and MLP.
Feature Angular SNR (+) is more significant for GCN, GraphSAGE, MixHop, LINKX, and MLP.
We note that the regression analysis only indicates associative relationships between data properties and the model performance. While our analysis has successfully identified well-known influential
5

---

data properties, e.g. Edge Homogeneity, the mechanism for most identified data properties through which they impact the GNN performance remains under-explored.
To further verify the effectiveness of the proposed metadata-driven approach in identifying critical data properties, we perform an in-depth analysis for Gini-Degree, of the most widely influential factors. In the following Section 4 and [ we conduct theoretical analysis and controlled experiments understand how Gini-Degree influences GNNs' performance.
Theoretical Analysis on the Impact of Degree Distribution
In this section, we present a theoretical analysis on influence of graph data's degree distribution on the performance of GNNs. Specifically, our analysis investigates the linear separabilityy of node representations produced by applying graph convolution to the node features. In the case that the graph data comes from different classes are more separable when their degree exceeds threshold. This separability result relates the graph data's 's degree distribution to the GNN performance. Finally, we discuss the role of Gini-Degree on the GNN performance using implications of our theory.
Degree-Corrected Stochastic Block Model, we show that nodes from
4.1 Notations and Sketch of Analysis
The Graph Data. Let 9 EV be undirected graph, where V is the set of nodes and E is the set of edges. The information regarding the connections within the graph can also be summarized as an adjacency matrix A E (0,1) xiv1, where | is the number nodes in the graph G. Each node i V possesses a d-dimensional feature vector x; E Rdd The features for all nodes in 9 can be stacked and represented feature matrix X E R xd In the context of node classification, each node i is associated with class label E C, where C is the set of labels.
Graph Convolutional Network [19.. In our analysis, we consider a single-layer graph convolution, which can be defined as operation on the adjacency matrix and feature matrix of graph G to produce new feature matrix X. Formally, the output of single-layer graph convolution operation can be represented as X = D-'ÁX where Á A + I is the augmented adjacency matrix with added self-loops, and D is the diagonal degree matrix with D deg(i) Σ)e(n] Aij- Hence, for each node E V, the new node representation will become x; E Rdd, which is the ith row of the output matrix X.
Sketch of Our Analysis. Our analysis builds upon and generalizes the theoretical framework introduced by Baranwal et al. B3. where they demonstrate that in comparison to raw node features, the graph convolution representations of nodes have better linear separability if the graph data comes from Contextual Stochastic Block Model (CSBM) [,8]. However, in CSBM, the nodes within the same class all have similar degrees with high probability, which prevents us to draw meaningful conclusions about the impact of degree distribution.
To better understand the role of degree distribution in the GNN performance, we develop non-trivial generalization of the theory by Baranwal et al. [3] Specifically, we first coin a new graph data generation model, Dorree-Correeted Contextual Stochastic Block Model (DC-CSBM) that combines and generalizes Pegree-Corrected SBM (DC-SBM) [7 and CSBM, and leverages heterogeneity in node degrees into considcration. Under DC-CSBM, we find that node degrees play a crucial role in the statistical properties of the node representations. and the node degrees have to exceed a certain threshold in order for the node representations sufficiently leverage the neighborhood information and become reliably separable. Notably, the incorporation of the node degree heterogeneity into the analysis requires non-trivial adaptation of the analysis by Baranwal et al.
4.2 Degree-Corrected Contextual Stochastic Block Model (DC-CSBM)
In this section, we introduce the DC-CSBM that models the generation of graph data. Specifically, we assume the graph data is randomly sampled from DC-CSBM with 2 classes.

---

DC-CSBM With 2 Classes. Let us define the class assignments (c))sejn) as independent and identically distributed (i.id.) Bernoulli random variables coming from Ber( ()) where
[ is the number nodes in the graph G. These class assignments divide n nodes into 2 classes: Co fi [n] c = 0} and C1 {i [n] G 1}. Assume that inter-class edge probability is and intra-class edge probability is p. and no self-loops are allowed. For each node i, we additionally introduce degree-correctie correction parameter 0, (0, ra/. which can be interpreted as the propensity of
node i to connect with others. Note that to keep the DC-SBM identifiable and easier to analyze, we adopt normalization rule to enforce the following constraint: Eiec, 0, = |Col. Eiec, 0g [Ci] and thus Diey 02 n.
Assumptions on Adjacency Matrix and Feature Matrix. Conditioning on (ei))E(n): each entry of the adjacency matrix A is a Poisson random variable with Au ~ Poi(0,0,p) if i, are in the same class and Aij ~ Poi(O,0,g) if j are in different classes. On top of this, let X E [nuxd be the feature matrix where each row x; represents the node feature of node i. Assume each x; is an independent d- d-dimensional Gaussian random vector with x; ~ N(,, ŞI)) if E Co and x; ~ N(,, I if i e C1.
We let μ. V E I2d to be fixed d-dimensional vectors with || ||l|2 S 1, which serve as the Gaussian mean for the two classes.
Given a particular choice of n, μt, V, P, y and 0 = (0))sefm) we can define a class of random graphs generated by these parameters and sample a graph from such DC-CSBM as G = (A, X) ~ DC- CSBM U, q, 0)-
v,
4.3 Linear Separability After Graph Convolution
Linear Separability. Linear separability refers to the ability to linearly differentiate nodes in the two classes based on their feature vectors. Formally, for any V. S V, we say that fx; i E V. is linearly separable if there exists some unit vector v E R and scalar b such that v Tx; + b < O, vi e Co and x, + 6 > 0, Vi E Ci,,, Note that linear separability closely related to GNN performance. Intuitively, more nodes being linearly separable will lead to better GNN performance.
Degree- Thresholedd Subgroups of Co and C1. To better control the behavior of graph convolution operation, we will focus on particular subgroups of Co and C₁ where the member nodes having degree-corrected factor larger equal notations, we denote these subgroups as Co(ar) and Ci (ax), which are formally defined below.
pre-defined threshold > 0. Slightly abusing the
Definition 4.1 (a-Subgroups). Given any a E (0, n), define a-subgroups of Co and C1 as follows:
Co(a) [j [n] 03 2 a and j E Co}:
(a) = (i E [m] 0 2 a and j E Ct).
Let V. == -C(aa) U (a),, we are interested analyzing the linear separability of the node representations after the graph convolution operation, namely {x : E V. Recall that for each node i, x; ds Σj Xj, where (ii is the set of neighbors of node
Relationship Between a and Linear Separability. We first make the following assumptions about the DC-CSBM, closely following the assumptions made by Baranwal et al. [3]
Assumption 4.2 (Graph Size). Assume the relationship between the graph size n and the feature dimension d follows lo d) S O(poly(d)).
Assumption 4.3 (Edge Probabilities). Define T(p,g) = P-9. Assume the edge probabilities p, satisfy p, = (log? (n)/n) and [pp, q) = 2(1).
Theorem 4.4 asserts that if the threshold ar is not too small, then the set V, = Co(a) U (a() can be linear separated with high probability. The proof of Theorem
found in Appendix C
Theorem 4.4 (Linear Separability of a-Subgroups). Suppose that Assumption 4.2 and 4.3 hold. For any (X, A) ~ DC-CSBM(n, M, 0), if
|max
logn
then
logn' An(p
2
V. is linearly separable) - where o1( is a quantity that converges O as d approaches infinity.
P({$
7

---

Note that Theorem 4.4 suggests that, when the heterogeneity of node degrees is taken into considera- tion, the nodes with degrees exceeding a threshold a are more likely to be linearly separable. And the requirement for the threshold a depends on the DC-CSBM parameters: P. 9, p.,
Remark 4.5. If we let p.q E O(1o0" ") and ll - v122 be fixed constant, then the requirement can be reduced to E w( (oggn) which is not too large. Given this particular setting and reasonable selection of the regime of acceptable a is broad and thus demonstrates the generalizability of Theorem
4.4 Implications on Gini-Degree
Finally, we qualitatively discuss the relationship between Gini-Degree and GNNs' performance using the results from Theorem 4.4 For any that meets the criteria in the statement, we consider,
1. Negative correlation between Gini-Degree and the size of V.: If the number of nodes and edges is fixed, a higher Gini-Degree implies more high-degree nodes in the network and thus the majority of nodes are receiving lower degrees. Clearly, if most of the nodes have lower degrees, then there will be fewer nodes having degrees exceeding a certain threshold proportional to dl and being placed in Va. Hence, a dataset with higher (or lower) Gini- Lni-Degree will lead to a smaller (or larger) size of Va.
2. Positive correlation between the size V. and model performance: Intuitively, the GNN performance tends to be better if there are more nodes that can be linearly separable after graph convolution. Consequently, the GNN performance is positively relevant to the size of Va corresponding to the minimum possible a.
Combining the two factors above, our analysis suggests that Gini-Degree tends to have a negative correlation with GNNs' performance.
5 Controlled Experiment on Gini-Degree
To further verify whether there is a causal relationship between the degree distribution of graph data (in particular, measured by Gini- Gini-Degree) and the GNN performance, we conduct controlled experiment using synthetic graph datasets.
Experiment Setup. We first generate series of synthetic graph datasets using the Graph World library (3I. To investigate the causal effect of Gini-Degree, we manipulate the data generation parameters to obtain datasets with varying Gini-Degree while keeping bunch of other properties fixed. Specifically, we use the SBM generator in GraphWorld library and set the number of nodes 5000, the average degree as 30, the number of clusters 4, cluster size slope as 0.5, feature center distance as 0.5, the edge probability ratio p/q = 4.0, feature dimension as 16, feature cluster variance 0.05. The parameters above are fixed throughout our experiments, and their complete definition can be found in the Appendix. By manipulating the power law exponent parameter of the generator, we obtain five synthetic datasets with Gini-Degree 0.906, 0.761, 0.526, 0.354, and 0.075, respectively.
Then we train the same set of GNN models and MLP model as mentioned in Table Ion each dataset. We randomil split the nodes into training, validation, and test sets with a ratio of 3:1:1, We closely follow the hyperparameters and the training protocol in the GLI library
(27). which is where we We run five independent trials with different random seeds.
obtain the metadata in Section 3
The experiment results are shown in Table 2 We observe an evident monoton- ically decreasing trend for the performance of the graph- models, GCN, GAT, GraphSAGE. MoNet, MixHop, and LINKX, as Gini-Degree increases. However, there is no clear pattern for the non-graph model, MLP. This result suggests that these widely-used GNN models are indeed sensitive to Gini-Degree which validates our result of sparse regression analysis. Note that MLP does not take the graph structure into consideration, and hence the degree distribution has less influence
Experiment Results.
Note that the expected value of the degree of node is proportional to 0, when we ignore self- (See Appendix C for more information.) Thus, the lower bound a on Segree-correetee factors can be translated to the lower bound ra(p + 4)a degrees.
8

---

Table 2: Controlled experiment results for varying Gini-Degree. Standard deviations are derived from independent runs. The performances of all models except for MLP have an evident negative correlation with Gini-Degree
Gini-Degrve
GCN
GAT
GraphSAGE
MoNet
MixHop
LINKX
MI.P
0,906
0.798:10.004
0.659110011
0.76110.005
0.672.10.002
0.80411.005
0.832=0.002
0.595=0.006
0,761
0,817=0.001
0.732=0.005
0.818=0.004
0.69620.015
0.817=0.004
0.849=0.002
0.756=0.002
0,526
0.874:10.004
0.002-0.006
0.005
0.8::0028
0.826=0.003
0.853=0.002
0.655=00005
0.354
0,906:10.002
0.737=0.008
0.857:10.008
0.83:100013
0.837:100002
0.867=0.002
0.66=0.07
0.075
0.948=0.002
0.746=0.005
0.878=0.002
0.9210.002
0.84100002
0.893=0.001
0.705=00002
on the performance of MLP. The result on MLP also indicates that we have done reasonably well-controlled experiment.
6 Conclusion
In this work, we propose novel metadata-driven approach that can efficiently identify critical graph data properties influencing the performance of GNNs. This significant contribution given the diverse nature of graph-structured data and the sensitivity of GNN performance to these specific properties. We also verify the effectiveness of the proposed approach through an in-depth case study around one identified salient graph data property.
As side product, this paper also highlights the considerable impact of the degree distribution, salient data property identified through our metadata-driven regression analysis, on the GNN performance. We present novel theoretical analysis and carefully controlled experiment demonstrate this impact.
Acknowledgement
The authors would like to thank Pingbang Hu for the feedback on the draft.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[2] Robert Adler, Jonathan E Taylor, et al. Random fields and geometry, volume 80. Springer, 2007.
[3] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved lincar separability and out-of-distribution generalization. arXiv preprint 2 2021.
[4] Norbert Binkiewicz, Joshua T Vogelstein, and Karl Rohe. Covariate-assisted spectral clustering. Biometrika, 104(2)361-3377.00)
[5] Shaked Brody, Uri Alon, and Eran Yahav. How attentive graph attention networks? arXiv preprint arXiv: 14491, 2021.
[6] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.1332 2020.
[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735. PMLR, 2020.
[8] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018.

---

[9] Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network-basee fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 315-324, 2020.
[10] Jian Du, Shanghang Zhang, Guanhang Wu, José MF Moura, and Soummya Kar. Topology adaptive graph convolutional networks. arXiv preprint (:Xiv::11101031101 2017.
[11] Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
[12] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv: 2018.
[13] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[14] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[15] Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma, Hongzhi Chen, and Ming- Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference on Learning Representations, 2019.
[16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118-2215 2020.
[17] Brian Karrer and Mark EJ Newman. Stochastic blockmodels and community structure in networks. Physical review E, 83(1):016107, 2011.
[18] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[19] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (ot::00000000 2016.
[20] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[21] Yanming Li, Bin Nan, and Ji Zhu. Multivariate sparse group lasso for the multivariate multiple linear regression with an arbitrary group structure. Biometrics, 71(2):354-33,, 2015.
[22] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, and Jieping Ye. Resnorm: Tackling long-tailed degree distribution issuc in graph neural networks via normalization. arXiv preprint arXiv:2206.0812 08181, 2022.
[23] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20905 2021.
[24] Renming Liu, Semih Cantürk, Frederik Wenkel, Sarah McGuire, Xinyi Wang, Anna Little, Leslie O' Bray, Michael Perlmutter, Bastian Rieck, Matthew Hirn, al. Taxonomy of bench- marks in graph representation learning. In Learning on Graphs Conference, pages 6-1. PMLR, 2022.
[25] Xiao Liu, Lijun Zhang, and Hui Guan. Uplifting message passing neural network with graph original information, 2023.
[26] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, arXiv preprint 1xX1v11711.51001, 2017.
10

---

[27] Jiaqi Ma, Xingjian Zhang, Hezheng Fan, Jin Huang, Tianyue Li, Ting Wei Li, Yiwen Tu, Chenshu Zhu, and Qiaozhu Mei. Graph learning indexer: A contributor-friende and metadata- rich platform for graph learning benchmarks. arXiv preprint arXiv:2212.04533 2022.
[28] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, 27(1):1154444, 2001.
[29] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 5115-5124, 2017.
[30] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[31] John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. Graphworld: Fake graphs bring real insights for gnns. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3691-3701, 2022.
[32] Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th international conference World Wide Web, pages 201-210, 2007.
[33] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002. 2020.
[34] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey oversmoothing in graph neural networks. arXiv preprint arXiv:2303. 10993, 2023.
[35] Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltu- ional networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1435-1444, 2020.
[36] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[37] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 17Xv::1100110000 2017.
[38] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[39] Quanmin Wei, Jinyan Wang, Xingcheng Fu, Jun Hu, and Xianxian Li. Aic-gnn: Adversarial information completion for graph neural networks. Information Sciences, 2023.
[40] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference machine learning, pages 6861- PMLR, 2019.
[41] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
[42] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi sumerisueeee learning with graph embeddings. In International conference on machine learning, pages 40) PMLR, 2016.
[43] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity- graph neural networks. Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 10737-10745, 2021.
11

---

[44] Sukwon Yun, Kibum Kim, Kanghoon Yoon, and Chanyoung Park. Lte4g: Long-tail experts for graph neural networks. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pages 2434,2443, 2022.
[45] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-78044 2020.
[46] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11 1166-11177, 2021.
12

---

A Definitions of Dataset Properties
We introduce the formal definitions the dataset properties mentioned in Section 3.2 Following the definitions in Section 4.1 further define | and |E| to denote the number of nodes and edges of graph G. Also, in the context of the node classification task, we define y E R as the vector of node labels and C' the number of classes.
A.1 Basic
Edge Density: The edge density for undirected graph is calculated as n(n-1)² graph, is computed m(=-1)
2m
while for directed
Average Degree:
The average degree for an undirected graph is defined as 2m while for directed graph, is defined m
Degree Assortativity: The degree assortativity is the average Pearson correlation coefficient of all
pairs of connected nodes. It quantifies the tendency of nodes in network to be connected to nodes with similar or dissimilar degrees and ranges between -1 and
A.2 Distance
Pseudo Diameter: The pseudo diameter is an approximation of the diameter of a graph and provides lower bound estimation of its exact value.
A.3
Connectivity
Relative Size of Largest Connected Component (RSLCC): The relative size of the largest con- nected component determined by calculating the ratio between size the largest connected component and
A.4 Clustering
Average Clustering Coefficient (ACC): First define T(u) as the number of triangles including node u, then the local clustering coefficient node u calculated as drg(w)(rg(wu--) (uu) undirected
graph, where deg(u) is the degree of node u; and is calculated
(o)) deg Tww)
for directed graph, where deg fot (u) is the sum of in-degree and out-degree of node and deg ** (u) the reciprocal degree of u. The average clustering coefficient is then defined as the average local clustering coefficient of all the nodes in the graph.
Transitivity: The transitivity is defined as the fraction of all possible triangles present in the graph. Formally, can be written Mtriangles where a triad is a pair of two edges with shared vertex.
#uiads
Degeneracy: The degeneracy is determined as the least integer k such that every induced subgraph of the graph contains a vertex with its degree smaller equal to k.
A.5 Degree Distribution
Gini Coefficient of Degree Distribution (Gini-Degree); The Gini coefficient of the node degrees of
the graph.
A.6 Attribute
Edge Homogeneity [1]: The edge homogeneity is defined as the ratio of edges whose endpoints have the same node labels.
In-Feature Similarity [31] First define within-class angular feature similarity as 1 picpulaa_ddsttneeex... x,) for edge (i.j) with its endpoints i and have the same node labels.
In-Feature Similarity is the average within-class angular feature similarity of all such edges in the graph.
13

---

First define between- angular feature similarity as 1- angular (istance(x,,xx x,) for an edge (i,j) with its endpoints and have different node labels. Out-Feature Similarity is the average between-class angular feature similarity of all such edges in the graph.
Out-Feature Similarity 31:
Feature Angular SNR 311 The feature angular SNR is computed as the ratio between in in-feature
similarity and out-feature similarity.
Homophily Measure 233 The homophily measure is defined as
|C& +
h
Σ
1I2
C-1
where [a]- = (ax 0), |Ck| is the total number of nodes having their label l and hg is the class-wise homophily metric defined below,
Ew.y. du (')))
hk
Euyu. du
where d, is the number of neighbors of node and d..i) is the number of neighbors of node having the same node label.
Attribute Assortativity: The attribute assortativity is the average Pearson correlation coefficient of all pairs connected nodes. It quantifies the tendency of nodes in network to connected to nodes with the same or different attributes (here node label) and ranges between -1 and 1.
B Experiment Setup for Obtaining Metadata
In this section, we describe more details the experimental setup to obtain GNNs' performance that in Section 3.2, mostly following Ma et al. (27]. For completeness, we list down the model setting used by them in the following paragraphs.
GCN 191. GAT (37, GraphSAGE [3], MoNet 29 MLP, and MixHop [1 are set to have two
layers with hidden dimension equals For LINKX 231, MLPA, MLPx are set be a one-layer network and MLP LP, to be two-layers network, following the setting in Lim et al. 23
For the of the training settings, adopt the same configuration for all experiments. Specifically, we set learning rate = 0.01, weight decay = 0.001, dropout rate = 0.6, max epoch = 10000, and batch optimizer for all models except LINKX. AdamW 226 used
size 256. We use Adam [X] with LINKX in order to comply with Lim et al. (23). For datasets with binary labels (i.e., penn94, pokec, genius, and twitch-gandn sanch,,,mer),, we choose the ROC AUC score as the evaluation metric; while for other datasets, we use test accuracy instead.
We also let all the detailed model settings remain consistent with the same with Ma et al. Namely,
GAT: Number of heads in multi-head attention = 8. LeakyReLU angle of negative slope 0.2. No residual is applied. The dropout rate on attention weight is the same as the overall dropout.
GraphSAGE:
Aggregator type is GCN. No norm is applied.
MoNet: Number kernels = 3. Dimension of pseudo-coordinte = Aggregator type sum.
List of powers of adjacency matrix [,,2,3], No norm is applied. Layer Dropout rate 0.9.
MixHop:
LINKX: No inner activation.
C Proof of Theorem 4.4
Proof Sketch. To prove Theorem we first show that degree and the neighborhood distribution of each node concentrate with high probability. Then claim that the node features after the
14

---

convolution operation will be centered around specific mean values, depending on the node classes. Finally, we demonstrate that the nodes in different classes can be linearly separated by the hyperplane passing through the mid-point of the two mean values μe, with high probability.
We prove the intermediate results in Lemma inequalities) by utilizing Lemma C.5 (Chernoff bound for Poisson random variable) and in LemmalC.t (convoluted feature concentration) by making use of Lemma C.7 (Borell's inequality). Finally, given the requirement of a stated in Theorem 4.4 we argue that the convoluted node features in two classes can be linearly separated with high level of confidence.
(degree and neighborhood distribution concentration
Novelty of our Proof. The general structure of our proof follows that of Baranwal et al. [3] However, our analysis requires non-trivial adaptation of the proof by Baranwal al. [3]. This is because we have a more general data model, DC-CSBM, where the CSBM assumed by Baranwal al. is a restricted special case of ours. In particular, we assume each edge is generated by the Poisson random variable following DC-SBM, instead of the Bernoulli random variable assumed by CSBM; we also incorporate the degree-corrected factor our analysis to model node degree heterogeneity within communities, which gives us the flexibility to discuss linear separability for subgraphs with different levels of sparsity.
Before we state and prove Lemma C.4
let us first define the following events that we will work on.
Definition C.1 (Class Size Concentration). For any 6 O, define
n (" 5) s /Col. 2 ()
(6)
Definition C.2 (Degree Concentration). For any 8' and for each node i [n], define
Du 16) { 1 (1-1))(11))))) 8')0: S
S 2 (r 4) 8')0,
n
Definition C.3 (Neighborhood Distribution Concentration). For any 8' and for each node i [m]]
define
Ia,1(0') = { (1 - c:)p + 6:9 (1 -1-60 (1-8') 1Co NN
(1 -1-63 =:) + Egg
p+ (1 + +0)
p p+9
Dú
(1 6:) EP (1 - 8)) s
|Ci
p+g (1 + +80
Ei)g + ai
p+q
DR
where N₂ denotes the set of nodes connected to node i.
Then in Lemma C.4 argue that for nodes in the c-subgroup defined in 4.1 for some appropriately chosen a >> O, the above events will happen simultaneously with high probability.
Lemma C.4 (Concentration Inequalities). Given a (oog nl,, Co(a)), Ci(a) defined by Defini-
tion 4.1 and Va Cola) U (i)... Let 8 = -1/2+c and 8' (a log log -1/2, then for 0 small enough, we have for any > 0, there is some >> such that
P (6) N 120(0') iEV.
N I.,((7) iEV.
2
C n
Proof. Firstly, we consider the event (0). Since (G))e()) ~ Ber( by the Hoeffding's ' inequality for independent Bernoulli random variables [38] Theorem 2.2.6], we have for any 8 > 0 that
Σ
2 6/2
2 exp(-no0
E
n
Notice that Di = |C1| and |Col + G1l n, we conclude that for any 5 > 0, the probability that the number of nodes in each class concentrates will satisfy
Col
C11
1
1 + 0))
E
8,
2 1 - C' eexp(-cn0),,
n2
T2
2
2
15

---

for some constant C 0.
We the events (I2,((")))Eji)) Notice that the node degrees of independent Poisson random variables. It is known that sums of independent Poisson random variables will be another Poisson random variable. Hence, conditioning 0 (0:) for each node [n]. have
Da 1+ Poi(
2 (p +q)0.).
where Dss the degree of node i, and
B [ =
11
(p + g)0,-
2
To prove that (0') will oceur with high probability for each E [n], we introduce the following result [38] Corollary 2.3.7] whose proof can be found in the referred literature:
Lemma C.5 (Corollary 2.3.7 38 ). If Poi(A), then for tort E (0, A}, we have
ot2
P([X A 2 t) S 2 2cxp(
A
Here, we can let 8'A where E (0, 1] and get a tail bound as follows:
P( - E D.]] 2 8 D')) & 2exp( D,)),, = 2exp(-c[[Du)0")
E[D.]]
It follows that for each i [n] and any 8' (0, we have
Dis 1 1 [p 9) 8')0., 2 (p + q)(1 + 50)0 1) Cexp(=ee(pp+p)) 9)0,8
1
P
2
n
for some C, 0.
We next consider the events (6'))())) Observe that for each node we can decompose node degree as Dis = D Dimeer where
Dintra
Σ 116 = b3),
JEN(1)
and
Dinter
Σ SEN(1)
1fc c.
Obviously, Dim = IC., N. and Dimter |C1=e; nM, will concentrate around upd. and mgo: 2 correspondingly. And given the tail bound for (8), by similar argument, we have for each [ni] and any 8' e (0, 1].
2
P(Is,(8')) 2 -m- 9))
for some C, c > 0.
Define the union event U') = ( (0') (8'). Recall that Vi E Va, we have
0, 2 Thus, can then choose d 1/2+c and 8' (a log n 1/22t, Since p, w log" n from Assumption 4.3 by a simple union bound, we have for c > 0 small enough, for any e > there is C > 0 such that
P(U (n (allog
((-tt//te,((alo (c/2og)))//2t))) >
n
Finally, establish the lower bound for indicated in the statement, which is logn" The reason why we need this lower bound is that o is too small, then the subgroups: Co(a), (a) will be too sparse that their member nodes' degree is too small to assure the concentration inequalities.
16

---

By the definition of the event: ((6, and union bound, we have
P (I) Cexp(-cno"
s Cexp(-cnn
(plug in 8 - n1 11/2er)
log log 0), 2log
C/n²
(if we choose
and
P
(0)) n Io.((')
S n Cexp(-cn(p) 9)
iiEV
iEVo
S n Cexp(-clog n a.?)
(by Assumption 4.3
Ceep(llog - clog n a(a logn)-1-2y -1-20
rexp(logn-cloee
(plug in 8 la
C exp(loo n clog (a log 2))
C expplogn (1 (1-c- c. (a log n) (²))
Cn log
We want to ensure the last term stays in O(1/n9) for some 0. Notice that if < log n, we cannot find suitable >> 0 for some small satisfy e- (a log O. Hence, we can conclude that a natural lower bound for should be Togn i.c., a logn'
Thus, combining Equation 3with this fact, we complete the proof.
Next, in Lemma C.6 we claim that given the adjacency matrix A, class memberships (c))iem)) degree-corrected factors (0s) and pre-defined threshold a > then with high probability, the convoluted node features X; RJ pot-gg for E Co(a) and x; s qutrp for E (a.)
ptq
ptg
Lemma C.6 (Convoluted Feature Concentration). Given a E (logn) n), Co(a:), Ci defined by Desinition 4.1 and V. Co(a) (a.). Conditionally A, (ei)kE(m) and (0))s we have that for any e 0 and some C > with probability at least n for every node Va and any unit vector w.
x;
ph + qu
p p+g g .w (1+0(1))
=0 (V
log n dnlp + q)a
for i Cu(a),
log n =0 (v dn(p + g)a
8: qu + pv
p+g w (1(+0(1)))
for E Ci(a).
Proof. Since (X, A) is sampled from DC-CSBM(1, V.P.9,0) 0), when conditioning on (G))se()) we have node i's node feature x; N(m,, 111 where m, - if i Co and m, = if C1. We can also write
9b Vd
x; (1 - ei) euU +
where g: ~ ~N(O,)) is standard normal vector.
On the other hand, conditioning the adjacency matrix A and class memberships (ei) the mean of the convoluted feature node can be written as
m(1) = E[
Σ Agm,
D
jE(n)
17

---

by the definition of the graph convolution operation (x; = D (.))). Thus, for any unit vector w, have
X W
(x,
w) Davd
Σ jE(y]
Aig (gg, w).
Dis jEIn]
Di.vd Eje(m] Aij (g), w) and observe that (g), w) is standard Gaussian random variable for all j E [m]. Thus, we have that F; ~ ~V(0 D..)) conditioning on the adjacency matrix A. Now introduce Borell's inequality 2 to give high-probability bound of [F for all d E V..
Let define F;
Lemma C.7 (Borell's Inequality, Theorem 2.1.1 in Adler et al. 2 Let F; N' of for each
i E Va. Then for any K O, we have
K
(Inax F; Elmax F.) K) exp( maxiev, FF BEV.
VEV.
We further define the event Qa Qa(t)= fmaxiev. [F]] S t). Observe that
AA)
P(max [F|] > ((A)
LeVa
S 2IF (max F; > t/A)
ieV.
2Ia F; E [max F.J M/max F.](A). iEV.
EV
.VVa
we let the union event U == Unn -1/2+e, (a log log defined the same as in Lemma C.4 then by Lemma C.7 and the definition of Va.
P(Qa) < P(U n n2a) + P(U))
2 d Emax F.])² dn(p ()a) 1
iEV.
no²
for any e > 0 and some > 0.
By the definition of event (6, 8'), we can derive the upper bound of maxiev, dR, as follows:
max OF = max iEV.
max EV.
d= g) 87)0 S
VEV.
dD
dd(p + q)(1 - -0)a
Since 8' is determined, we have for some constant K,k k> 0.
log n dulp 4)xx
Elmax Fi] S W'Vlog maxor S kiy V
VEV.
TEV.
By choosing t C¹ dn(p+q)a
n
for some large constant C' k O, we can obtain
log
log > 0.
E
max F.J C² EV.
dn(p + a)a KV dn(p + q)a
Thus, we have
n 2 - P(U9) -
2 expp( 2exp(-d(1
max F.]) + g)a) VEV.
ne
2
> 1
n2
ne'(C" -k²
18

---

Recall that when conditioning on the event U, we have
mi) = pp + qu
(1 + o())
for E Co(a),
(5)
+
qu + pM
m(i)
(1 + o for E Ci(a).
(6)
p + q
Thus, on the event U n Qa. we have for each node Va-
(x; m(t), w)| w)|= =0 (v -0
log dn(p 9)a )
which completes the proof.
Now are ready to prove Theorem 4.4
Proof. Recall the definition of linear separability, we need to find some unit vector v E R. and E I such that
(R,, v) < for E Co(a:)
(x, v) b> for i E C1(a).
We fix V = 24 (v (4) and = (u+v where } 211 2112. By Assumption 4.3 Lemma C.4
and C.6 with probability at least O(n 9) for any c 0, for all i Co(a), we have
(x; v) +b
(p + qu, v)
(1+ o(1) +o (V log n dnlp + g)ax
+
(By Lemma C.6
p+
(Vanlo dnlp Vdn(p+0)) + q)
(p (u -1) v)
+1)+ v) (1 (1+ o(1)) +0
log
(1+
-1 =(0))==))))) (1/
log
(dnlpp+0) +
log
-->T(p.)) + o(7)
(a Eww
dn(p + 9)>
< 0.
(by Assumption 4.3
Similarly, for all i E Ci (a), we have
(X, F) +
(1 (1+) (v/
(au + pv, v)
log
|d(pp (Van(p
+ b
(By Lemma C.6
p+q q
9)a
-( (p -(0- ()(v (v- H)
v) (1+ (1+)(1))+00 (v
log d q)a
2(p+9)
= =1 o()) + (011)))+011 (0
log n dd(p 9)a
log n
= =1 + o1)) + o(7)
(a E w dn(p + 9)
0.
(by Assumption 4.3
The above two inequalities imply the linear separability of (X,, E Val, which completes the proof.
D
19

---

Table 3: Description of parameters used in the controlled experiments.
Parameter Name
Description
TI
Number of vertices in the graph. the slope of cluster sizes when ordered by size.
cluster size slope
feature dimension
the number of dimensions of node features.
feature center distance
distance between feature cluster centers.
p/q ratio
the ratio intra-class edge probability inter-class edge probability. the average expected degrees nodes.
average degree
power exponent
the value of power-law exponent used to generate expected node degrees. variance of feature clusters around their centers.
feature cluster variance
Table 4: Remaining parameters used in experiments. One of the parameters manipulated to generate synthetic datasets with varying data properties indicated in the first column.
Average Degree
Power Exponent
Feature Cluster
Experiments
p/q ratio
Variance
Gini-Degree
3
[1.5, 2, 2.5, 3, 51
0.25
Average
3
[10, 20, 30, 40, 50]
0.25
Degree
Edge
[1,233,510]]
20
2
0.1
Homogeneity
In-Feature
2
[2. I, 0.5, 0.2, 0.1]
Similarity
Feature
2
20
2
[2. 1, 0.5, 0.2, 0.1,
Angular SNR
D Controlled Experiments of Identified Salient Factors
From Section 3.3 we discover six prominent dataset properties that correlate with some or all of the GNN models performance. In Section we have presented controlled experiments for Gini- Degree to verify its relationship to GNNs' performance (Table In this section, we further conduct controlled experiments for all the remaining identified salient factors, except for Pseudo Diameter, which is hard to control via manipulating explicit parameters provided by Graph World.
Across all experiments, we fix the number of nodes 5000, cluster size slope as 0.0, the number of clusters as 4, feature dimension as 16, and feature center distance as 0.05. For each of the experiments, we will keep most of the remaining Graph World parameters the same and only vary one of the parameters. The remaining parameters that we will manipulate are the p/q ratio, average degree, power exponent, and feature cluster variance. We give short description of all the parameters 3 For completeness, we summarize the value of the remaining parameters used in four experiments in Table 4
Table 5] 6 and [ show the results of the four controlled experiments, correspondingly. Note that varying feature cluster variance can manipulate In-Feature Similarity and Feature Angular SNR simultaneously (Table In general, all the results closely follow the regression results indicated in Table and the discussion in Section 3.3
Table Controlled experiment results for varying Average Degree. Standard deviations are derived from 5 independent runs. The performances of all models except for GAT, MixHop, and MLP have an evident positive correlation with Average Degree.
Average Degree
GCN
GAT
GraphSAGE
MoNet
MixHop
LINKX
MLP
10
0.71:10.118
0.67-10.009
0.725.10.002
0.55610.024
0.69610.001
0.693=0.006
0.632-10.004
0.823-10001
0.734=00013
0.797-1.006
0.59310.012
0.806=0.003
0.825=0.001
0.54:10.024
0.839=0.005
0.722-00017
0.80110.002
0.76120.005
0.756=0.002
0.852=0.003
0.65310.004
40
0.806-:0.033
0.742-10.006
0.825
0.705200002
0.794=0.003
0.876=0.002
0.008
50
0.940.0044
0.73410.019
0.86:10.002
0.81410.003
0.788=0.011
0.8910.005
0.65110.002
20

---

Table 6: Controlled experiment results for varying Edge Homogeneity. Standard deviations are derived from independent runs. The performances of all models except for MixHop and MLP have an evident positive correlation with Edge Homogeneity.
Edge Homogeneity
GCN
GAT
GraphSAGE
MoNet
MixHop
LINKX
MLP
0.249
0.737=0.004
0.565=0.009
0.732:10.005
0.5151:0.044
0.83610.002
0.823:10.005
0.744110033
0.375
0.873=0.002
0.825=0.011
0.84740.003
0.57=00009
0.945:10.022
0,93=0.003
0,93=0.001
0.452
0.917=00.02
0.887:10.004
0.896.10.000 0.007
0.598:10.005
0.947:10.001
0,949:100002
0.78410.09
0.559
0.925=0.002
0.8910.004
0.925:1.004
0.678+4.003
0.913-10.005
0.94310.005
0,910.004
0.702
0.946=0.004
0.933=000044
0.953=0.001
0.802+40.003
0,942#1.001
0.959=000001
0.865+000044
Table 7: Controlled experiment results for varying In-Feature Similarity / Feature Angular SNR.
Standard deviations are derived from 5 independent runs. The performances of all models except for MoNet have an evident positive correlation with In- Fn-Feature Similarity Feature Angular SNR.
Feature Similarity
Feature Angular SNR
GCN
GAT
GraphSAGE
MoNet
MixHop
LINKX
MLP
0.506
1.009
0.478.10:016
0.412.10.016
0.446.10.005
0.562.10.021
0.433.100001
0.59810.002
0.402.10.002
0.516
1,022
0,5631:0004
0,47:0.006
0.51710.008
0.61520.002
0.531=0.003
0.661:0.004
0.47:0.001
0.527
1,039
0.71740.008
0.507=0.006
0.6=0.006
0.555=0.021
0.621=0.007
0.737=0.001
0.48==0.003
0.582
1,101
0,7844-0.01
0.599-00014
0.744+0.01
0.533-0.01
0.848+0.001
0.854+0.000
0.611-0.003
0.602
1.154
0.88740.006
0.791=0.004
0.82540.006
0.627=0.004
0.924:0.004
0.91340.006
0.915=0.002
E Robustness of the Sparse Regression Analysis
To demonstrate the robustness of the identified salient factors (defined in Section 3.3
we expand our
sparse regression analysis include five additional models that more recent and popular. The models are TAGCN (10), GATv2 (5), SGC [40]. APPNP [2] and GCNII 77). For the additional experiments, adopt the same configuration in Appendix The updated analysis result is
presented in Table [
We can observe that the widely influential factors and the narrowly influential factors all remain salient after incorporating the five additional models. The results show that our proposed multivariate regression analysis is robust with respect to diverse choice of GNN models.
Table 8: The estimated coefficient matrix B of the multivariate sparse regression analysis with five additional GNN models. These five models are indicated in blue. Each entry indicates the strength (magnitude) and direction (+, -) the relationship between graph data property and the performance of GNN model. The six most salient data properties are indicated in bold. Notice that these factors are the same as the ones we presented in Section 3.3
Graph Property
GraphSAGE
MoNet
MixHlop
TAGCN
APINP
Edge Density
0.8937
Average Degree
0.2336
0
0.098
0.1047
0.3362
0
0.173
0.4588
0
Pscudo Diameter
-0.9224
-0.6608
-0.0133
-0.5915
-03937
.0.691
0025114
-0.1428
-0.0816
-0,401
-0.2962
Degres Assortaivity
0.0587
0
0
RSLOC
0,1014
0,0673
0.1312
.00023
-0.1139
0.0276
Transiivityy
-0.0458
-0.488
0.2168
D
000795
0
-0.00
Degeneracy
0
0
0
-0. 1555
D
-0.0652
-0,399
-0.2266
Gini-Degree
-0,4437
-0.2455
-0,3313
-0.992
-0 4269
00.388
-0 1993
-0 3838
-0,243
-0 1907
-0 0.3021
-0.33
Edge Homogeneity
0.714
0.4197
0.7241
0.8108
0,6396
0.2017
0.4777
0.7147
0,7007
0.2817
0.7962
0.7184
Pe-uutuure Similarity
0.3103
0.0926
0.1878
0,0969
0.1576
0.6406
0.2421
0.1391
0.0059
0.0255
Out-Feature Similarity
0
Feature Angulor SNR
0.2492
0.0933
0.2455
0
0.2355
0.356 3564
0. 0,3682
0.1 1354
0.3 33038
-8 -0.0997
0.2733
0.359
Homophily Hat
0.456
0
D
0.4795
0
Attibatt Assoriativity
21


Reviews:
[{"review_id": "fCEOS3oU0O", "reviewer": "Reviewer_aoxj", "summary": "The authors analyze the sensitivity of GNNs to graph properties such as degree distribution, homophily, etc. Using a multivariate sparse regression analysis (based on Lasso), they find a set of properties that are universal in that they effect all kinds of GNNs and some properties that are local in that they effect only a few of the GNNs. Among the global properties, one that is prominent is degree distribution that has an inverse effect on node classification accuracy. In the second half of the paper, the authors analyze the reasons behind this behavior using a theoretical model based on a Degree-Corrected Contextual Stochastic Block Model. The results of the model are validated by a controlled experiment.\n", "questions": "Please see above.", "limitations": "None.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper presents a good analysis of the effect of degree distribution through empirical and theoretical analysis.\n", "weaknesses": "Translating the theoretical results into empirical outcomes requires the total degree to be bounded so that there are many nodes with similar degrees. Is this true for the datasets the authors considered?\n\nAt the same time, it is not surprising that it becomes harder to classify nodes that have similar degrees since one of the important features is not useful anymore. \n\nCan the theoretical model explain the other universal features such as edge heterogeneity and in-feature similarity?\n\nLasso requires the errors to be Gaussian. Did the authors verify this?\n\nIt is interesting to see that MLP also suffers from the effect of degree distribution.\n\nOverall, the impact of the paper is not likely to be high since it only considers the problem of node classification. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's acknowledgment that we present a good analysis of the effect of the degree distribution. We address your concerns in detail below.\n\n**W1: [Requirement of bounded total degree for datasets.]**\n\nA: We clarify that a bounded total degree does not necessarily imply that many nodes will have similar degrees. Given the total degree fixed, how “equally” the edges are distributed among nodes is controlled by Gini-Degree. There could still be a skewed degree distribution for some choice of Gini-Degree. We believe that the bounded degree assumption is not a strong assumption.\n\n**W2: [Node degree as an important feature for node classification.]**\n\nA: Indeed, a higher Gini-Degree implies that the graph will have more nodes with similar node degrees. However, our main contribution is to verify that a higher Gini-Degree will result in poorer performance of GCNs. Under this situation, fewer nodes will have higher degrees in this dataset. By the assumption we made in Section 4, we know that nodes with lower degrees will be harder to classify, and hence the GCN model will perform worse in this case. (According to the discussion in Section 4.4)\n\nSo the main reason why datasets with high Gini-Degree are considered more challenging tasks is not brought by the fact that we lose “node degree” as a node feature.\n\nMoreover, Node degrees should not be considered a crucial feature in general. For example, if the dataset is generated from a DC-CSBM (in Section 4.2), nodes with larger degrees will be easier to classify in our setting, even though they have very similar degrees.\n\n\n**W3: [Can the theoretical model explain other universal features?]**\n\nA: We clarify that the purpose of our theoretical analysis is NOT to explain all the factors discovered in our regression analysis in the first place. Instead, both the theoretical analysis (Section 4) and the controlled experiment (Section 5) are designed to explain the impact of Gini-Degree, as a proof-of-concept verification that our main contribution, the metadata-driven approach for discovering salient graph characteristics (Section 3), is effective.\n\nIt is indeed also interesting to further understand other salient factors discovered by our metadata-driven approach, but we believe that examining all factors is beyond the scope of this paper and will leave it for future research.\n\n\n**W4: [Lasso requires the errors to be Gaussian.]**\n\nA: We would like to point out that Lasso has been widely used for the purpose of feature selection, which works without requiring the data to have Gaussian errors. In fact, the effectiveness of Lasso for feature selection has been theoretically verified under weak conditions when Gaussian assumptions are not met. See, for example, the following paper [1].\n\n[1] Zhao and Yu, On Model Selection Consistency of Lasso, 2006.\n\n**W5: [MLP suffers from degree distribution.]**\n\nIn fact, MLP is much less influenced by degree distribution. In Table 1, the absolute magnitude of the coefficient for MLP is much smaller than that for other models. In Table 2, there is not much variation of MLP performance for varying Gini-Degree.\n\n**W6: [Limited impact due to node classification problems only.]**\n\nA: While we acknowledge that our empirical study focuses on node classification datasets in this paper, we would like to point out that the conceptual framework of a metadata-driven approach is not limited to node classification tasks. Furthermore, node classification is already a broad class of problems. So we respectfully disagree with the reviewer's comment that a paper would have limited impact if \"it only considers the problem of node classification\". In addition, we believe that a side product of our proposed approach, the understanding of the impact of degree distribution on GNN performance, is also a significant contribution in its own right.\n"}, {"review_id": "e2xiP8NZAL", "reviewer": "Reviewer_f4if", "summary": "Graph neural networks (GNNs) have demonstrated significant success across various problem areas. In this study, the authors propose a metadata-driven approach to examine the sensitivity of GNNs to graph data properties, spurred by the growing availability of graph learning benchmarks. A multivariate sparse regression analysis is performed on GNN performance across a range of datasets, identifying a set of significant data properties. The authors then focus on the degree distribution, investigating its influence on GNN performance through theoretical analysis and controlled experiments.", "questions": "The overall contribution of the study seems weak, mainly because of Section 3. Please refer to the weaknesses listed above.", "limitations": "The authors have acknowledged the limitations of their approach.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to comprehend.\n2. The concept of metadata-driven analysis is intriguing and holds potential for further refinement in future research.\n3. The paper includes a theoretical contribution that enhances our understanding of GNNs' success.", "weaknesses": "1. Given the comprehensive nature of this study, the authors should justify their selection of the GNN models used in Section 3, given the hundreds of models available in this field. There should be a principled approach to choosing models that are (1) representative, (2) popular, and (3) have diverse operational mechanisms, ensuring that the study is reliable and generalizable.\n2. The metadata-driven analysis presented in Section 3 is somewhat incomplete. As mentioned by the authors in Lines 201 - 202, Section 3 only investigates the correlation between GNN performances and data properties. Causality is explored later and exclusively for Gini-Degree. The insights related to edge homogeneity and in-feature similarity are primarily replications of existing work findings. Regarding the other three properties, the authors note that \"we do not yet have a good understanding of the mechanism of how these data properties impact model performance,\" indicating that the study is not fully complete.\n3. There should be a more comprehensive discussion relating to node degrees, as this is a popular property used to understand graphs and networks. The authors claim that \"the finding of the Gini coefficient of the degree distribution\" is novel, but how is it distinctly novel compared to existing work? I suggest the authors connect the findings in this work more closely to those in previous studies to strengthen their theoretical contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's acknowledgment of the clarity of our paper, the value of our proposed metadata-driven analysis, and our theoretical contribution. We address your concerns in detail below.\n\n**W1: [Selection of the GNN model we use for regression analysis.]**\n\nA: We agree that many possible GNN models can be used for the regression analysis. Our choice inherited the ones selected by the Graph Learning Indexer (GLI) paper [1] since we rely on this library to obtain the metadata. \n\n[1] Ma et al. Graph Learning Indexer: A Contributor-Friendly and Metadata-Rich Platform for Graph Learning Benchmarks. 2022\n\nTo address your concern, we further implement five additional models (that are popular and widely cited) to obtain more metadata for the regression analysis, including SGC, APPNP, TAGCN, GATv2, and GCNII. The result of the regression analysis can be found in the global pdf we submitted with our rebuttal. \n\nThe six salient factors we discover in our paper remain crucial after including the metadata associated with these five models, demonstrating the robustness and efficacy of our regression analysis and the salient factors we found.\n\n**W2: [Incompleteness of our regression analysis.]**\n\nA: The metadata-driven analysis shows the saliency of the correlation between certain dataset properties and GNN model performances. Since correlation does not necessarily imply causality, we further explore the relationship between Gini-Degree and GNN performance to validate the observation made in Section 3. \n\nWe chose to investigate Gini-Degree because edge homogeneity and in-feature similarity are well-known factors. There are various papers that verify these factors are essential for GNNs through theoretical and empirical analysis. Hence, edge homogeneity and in-feature similarity are not significant findings of our analysis. This discovery is more like verifying that our regression analysis is valid and can uncover widely known and studied factors. On the other hand, degree distribution is widely considered an essential factor but lacks in-depth analysis. We provide a thorough theoretical analysis to explain the relationship between Gini-Degree and GNN performances. \n\nIt is true that we do not have a technical justification for the three selective factors (Average Degree, Pseudo Diameter, and Feature Angular SNR) mentioned in our paper. However, this does not undermine the effectiveness and completeness of our metadata-driven analysis, which serves as our prime contribution. Further investigation for these selective factors will certainly be possible direction building off this work, but this will not affect the fact that this paper can complement current data-driven analysis approaches.\n\n**W3: [Discussion relating to node degrees.]**\n\nA: We have included some GNN works discussing node degrees in Section 2.3. Previous works on this topic recognize that node-wise classification accuracy will vary depending on node degrees. But most of them designed new GNN architecture to overcome the low accuracy on lower degree nodes. Our theoretical contribution laid a more fundamental basis for a dataset-level understanding. We utilized a simplified version of GCN to tell the reason why degree distribution has a direct relationship with GNN performance.\n"}, {"review_id": "zn51etdorp", "reviewer": "Reviewer_FJsn", "summary": "This paper offers an intriguing analysis aimed at analyzing the performance of Graph Neural Networks (GNNs). The analysis explores various graph-theoretic properties of the graph datasets, which may impact the performance of GNNs. The authors investigate 15 graph properties across 15 datasets and examine the coefficient matrix of a multivariate linear regression model using the obtained metadata. The analysis reveals an intriguing observation: a negative correlation between Gini-Degree and the performance of GNNs. The authors support this observation with theoretical analysis and controlled experiments, providing compelling evidence to support their claim.", "questions": "1- I am curious to know if this observation holds true for the graph classification task as well.\n\n2- Table 2 indicates that all GNNs exhibit improved performance with a decrease in Gini-degree. However, is this consistently the case, or is there a relationship with the type of convolution used? It would be intriguing to explore the connection between different graph convolution operators such as MPNN and GIN, and their relationship with Gini-Degree.", "limitations": "-", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "1 - the hypothesis considered makes sense and properly evaluated\n2 - the paper is well-written and well-organized\n3 - the investigation reveal clear results and are supported by theoretical analysis and controlled experiments ", "weaknesses": "1 - I appreciate the thorough investigation of the proposed hypothesis on generated synthetic datasets for node classification. However, it would be intriguing to expand the analysis by exploring a few real-world datasets that demonstrate both high and low Gini-degree. This would provide valuable insights into the applicability and generalizability of the observed relationship in real-world scenarios.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's acknowledgment of the soundness and clarity of our paper. We address your individual concerns in detail below.\n\n**W1: [Real-world datasets with varying Gini-Degree.]**\n\nA: We would like to clarify that the real-world datasets used in Section 3 do have varying Gini-Degree. Specifically, these real-world datasets have their Gini-Degree ranging from 0.4 to 0.73. If there is no variation of Gini-Degree among the datasets, the sparse penalty will likely drive the coefficient for this factor to 0. \n\nHowever, it is tricky to conduct controlled experiments on real-world datasets, as it is difficult to find datasets that only vary in Gini-Degree while all other factors are similar.\n\n**Q1: [Graph classification tasks.]**\n\nA: We consider extending our current framework to analyze other graph learning tasks, including graph classification tasks. But notice that for graph classification tasks, the datasets become “sets of graphs” and our regression analysis only works for a single graph for each dataset. \n\nIntuitively, we can compute the average graph properties among graphs in a single dataset to find a representative set of factors describing the entire graph classification dataset. And it will be straightforward to apply the same regression analysis to discover prominent factors. \n\nUnfortunately, we didn’t have time to run multiple graph classification algorithms and conduct a thorough analysis for this task in the rebuttal phase. It will be an exciting future direction for further research, including defining other aggregation schemes other than simple averaging.\n\n**Q2: [Consistent for different types of convolution.]**\n\nA: In our paper, we observe that it is consistent for a few different types of convolutional operations, such as GCN, GAT, MixHop, etc. To further verify the consistency and robustness of our analysis, during the rebuttal period, we incorporate five more models that are popular on node classification tasks, including TAGCN, GATv2, SGC, APPNP, and GCNII, into our multivariate regression analysis. The regression results are shown in the global pdf. We can observe that the factors we discover in Section 3.3 remain valid even if we involve these additional GNN models.\n"}, {"review_id": "7oKdwnf78Y", "reviewer": "Reviewer_zbzi", "summary": "Edit: Based on the new experiments, I am increasng my score slightly\n\nThey conduct a multivariate regression on the metadata of datasets and performance of multiple GNN models and examine the correlation between GNN performance and data properties. \n\nThey show that Gini-Degree, Edge Homogeneity, and In-feature similarity are salient features for all of the models they consider and that average degree, pseudo-diameter, and feature angular snr are salient for some of the models. \n\nThey also perform some analysis on how the gini-coefficient of the degree distribution affects model performances on a novel SBM.\n\nOverall, I think this is a novel approach to an important problem and a good paper.", "questions": "\nThere are GNNs which use non-local aggregations such [1] and [2]. Do you think that they would be able to avoid the dependence on the Pseudo Diameters?\n\n[1] https://arxiv.org/abs/2305.13084\n[2] https://arxiv.org/abs/2201.08932\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "\nThis is a novel approach to an important problem. Advances in ML are based on empirical performance on benchmarks as much, if not more than, as they are on theoretical guarantees. Therefore, understanding the benchmark-datasets, and what makes a network preform well on them is of paramount importance. This paper which focuses on the metadata of the datasets can play a complementary role to other model driven analyses. \n\nThe DC-SBM model is interesting as is the concept of separate the $C(\\alpha)'s$ rather than the entire classes.\n\nAs a disclaimer: I did not read the proof of Theorem 4.4 as thoroughly as I would like to due to time constraints. At a glance, it appears to be a well-organized application of concentration of measure techniques. Would be curious if any of the reviewers have checked it more closely. (This is obviously not the authors fault and I do not hold it against them.)", "weaknesses": "\nThe characterization of ``universal factors\" is somewhat misleading as they are only universal amongst the several GNN models considered. Indeed, a potential direction, building off of this work would be to find GNN models which are not affected by these `universal' factors. For instance, there are GNNs designed to alleviate the oversmoothing issue and they might be more robust to datasets with low edge homogeneity or in-feature similarity. \n\nSome of the equations in the proof are spilling off of the page.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's acknowledgment of the novelty and importance of this study. We address your concerns and questions in detail below.\n\n**W1: [Characterization of universal factors.]**\n\nA: This is a good point. These so-called \"universal\" factors are only salient for the GNN models we considered in the analysis. We agree that \"universal\" might be misleading. We plan to change the names to \"widely influential factors\" and \"narrowly influential factors\".\n\n**W2: [Equations spilling off the page.]**\n\nA: Thank you for the comment. We will fix them in our next version.\n\n**Q1: [GNNs with non-local aggregations vs. Pseudo Diameter.]**\n\nA: Thank you for the suggestion. We conducted additional experiments to investigate this question. Due to time and GPU memory constraints, we only performed experiments on the first paper’s model (FLODE) mentioned by the reviewer. \n\nWe tried two versions of the regression analysis to investigate whether there is a dependency between FLODE’s performance and Pseudo Diameter. In the first version, we only use FLODE’s performance as regression targets (univariate regression analysis). In the second version, we use the performance of all models as regression targets (multivariate regression analysis). \n\nWe agree with your intuition that since fLode uses non-local aggregation to alleviate over-smoothing problems, its performance should not be very sensitive to the diameter of the graph. However, the results from both regression analyses show that there is still a dependency between fLode performance and Pseudo Diameter. We do not have a good explanation for this result yet. This will undoubtedly be a very intriguing follow-up work to our current paper. \n\nThe regression results (coefficients of FLODE) from univariate/multivariate regression analysis are shown below.\n|  Graph Data Property | Coefficient from Univariate Analysis  | Coefficient from Multivariate Analysis |\n|:----: | :----: | :----: |\n| Edge Density |  0.1676 | 0.1599 |\n| Average Degree  | 0  | 0|\n| Pseudo Diameter  | -0.2263  | -0.2348|\n| Degree Assortativity |  0 | 0|\n| RSLCC| 0  | 0.0566|\n| ACC |  0 | 0|\n| Travsitivity| 0.3203  | 0.3614| \n| Degeneracy |  0| 0 |\n| Gini-Degree|  -0.2271 | -0.2597|\n| Edge Homogeneity | 0.8022 | 0.8128|\n| In-Feature Similarity | 0  | 0|\n| Out-Feature Similarity|  0 | 0|\n| Feature Angular SNR| 0.3158  | 0.3277|\n| Homophily Measure | 0  | 0.031|\n| Attribute Assortativity | 0  | 0|\n"}]

Author rebuttal:
Dear Reviewers,

We appreciate your thorough evaluation of our paper and the valuable feedback you have provided. We have carefully considered your comments and responded individually. We would also like to summarize below our response to the major concerns raised in the reviews.

*Clarification of Main Contribution.* The primary focus of our work is to introduce a metadata-driven analysis approach that sheds light on the relationship between complex dataset properties and the performance of GNNs. We want to clarify that the theoretical analysis and controlled experiments were not designed to verify every single salient factor comprehensively, but rather to serve as proof-of-concept verification for the proposed metadata-driven methodology. We chose the factor related to degree distribution for further investigation mainly due to its popularity and the lack of in-depth studies in previous works. Theoretical framework or experimental setup for comprehensively verifying all salient factors identified by our methodology are exciting future directions.

*Robustness of analysis.* As suggested by reviewers, we have expanded our analysis to include five more models that are more recent and also popular. The experiment results are reported in the global pdf attached with this general response. The results show that our proposed multivariate regression analysis is fairly robust with respect to the choice of GNN models. For this additional experiment, we adopt the same configuration as our paper for the default training settings. 

We would like to thank all the reviewers again for their valuable feedback, which has enabled us to clarify our central contributions and showcase the robustness of the metadata-driven regression analysis. We hope our responses have successfully addressed all the concerns and look forward to hearing from the reviewers for further comments.


Meta-review: This paper proposes a metadata-driven approach to analyze the sensitivity of GNNs to graph data properties, motivated by the increasing availability of graph learning benchmarks. The authors perform a multivariate sparse regression analysis on the metadata derived from benchmarking GNN performance across diverse datasets, yielding a set of salient data properties. 

Overall, the reviewers have acknowledged that concept of metadata-driven analysis is intriguing and holds potential for further refinement in future research, although there are concerns about justifying selection of the GNN models (addressed in rebuttal), more thorough comparison with existing works, and some practical limitations.
Decision: Accept (poster)