A Metadata-Driven Approach to Understand Graph Neural Networks
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
$\textit{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
$\textit{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.
Ting Wei Li, Qiaozhu Mei, Jiaqi Ma
# A Metadata-Driven Approach to Understand Graph Neural Networks

###### 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 _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. In 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 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 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 metadata-driven approach is effective in identifying critical data properties for GNNs.

## 1 Introduction

Graph Neural Networks (GNNs), as a broad family of graph machine learning models, have gained increasing research interests in recent years. However, unlike the ResNet model [14] in computer vision or the Transformer model [36] in natural language processing, there has not been a dominant GNN architecture that is universally effective across a wide range of graph machine learning tasks. This may be attributed to 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 non-homophilous graph datasets, where nodes from different classes are highly interconnected and mixed [45; 46; 32; 11; 9].

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 to model GNN performance using specific heuristics or domain knowledge derived from network science or graph theory [41; 45]. Although this approach can offer an in-depth understanding of GNN performance, it can also be time-consuming, subjective, and may not fully capture the entire spectrum of relevant data properties.
To address these limitations and complement the model-driven approach, we propose a _metadata-driven approach_ to identify critical data properties affecting GNN performance. With the increasing availability of diverse benchmark datasets for graph machine learning [16; 27], we hypothesize that critical graph data properties can be inferred from the benchmarking 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 a variety of graph datasets. Through this regression analysis, we examine the correlation between GNN performance and the data properties of each dataset, thereby identifying a set of salient data properties that significantly influence GNN performance.

To validate the effectiveness of the proposed metadata-driven approach, we further focus on a 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 a theoretical analysis and a controlled experiment.

We initiate our investigation with a theoretical analysis of the GNN performance under the assumption that the graph data is generated by a Degree-Corrected Contextual Stochastic Block Model (DC-CSBM). Here, we define DC-CSBM by combining and generalizing the Contextual Stochastic Block Model [4] and the Degree-Corrected Stochastic Block Model [17]. Building upon the analysis by Baranwal et 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 performance 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-driven regression analysis.

In summary, our contribution in this paper is two-fold. Firstly, we introduce a novel metadata-driven approach to 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

### Analysis on the Limitations of GNNs

There has been a 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 an 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 [1; 9; 23; 46; 45]. In addition, over-smoothing, a phenomenon where GNNs lose their discriminative power with deeper layers [20; 34; 6], is a 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. [41; 30; 25; 43]. Most of these limitations are understood through a _model-driven_ approach, which offers in-depth insights but is time-consuming and highly subjective. In contrast, this paper presents a _metadata-driven_ approach, leveraging metadata from benchmark datasets to efficiently screen through a vast array of data properties.
### 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 al. [24] presents a principled pipeline to taxonomize benchmark datasets. Specifically, by applying a 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 a Graph Learning Indexer (GLI) library that curates a large collection of graph learning benchmarks and GNN models and conducts a large-scale benchmark study. We obtain our metadata from their benchmarks. Palowitch et al. [31] introduce a GraphWorld 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.

### 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; 44; 39]. 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.

## 3 A Metadata-Driven Analysis on GNNs

### 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 [16; 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 as 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 as \(q\), and the number of data properties as \(p\). Define the response variables \(\{\mathbf{y}_{i}\}_{i\in[q]}\) to be GNN model performance operated on each dataset and the covariate variables \(\{\mathbf{x}_{j}\}_{j\in[p]}\) to be properties of each dataset. Note that \(\mathbf{y}_{i}\in\mathbb{R}^{n},\forall i\in[q]\) and \(\mathbf{x}_{j}\in\mathbb{R}^{n},\forall j\in[p]\). For ease of notation, we define \(\mathbf{Y}=(\mathbf{y}_{1},...,\mathbf{y}_{q})\in\mathbb{R}^{n\times q}\) to be the response matrix of \(n\) samples and \(q\) variables, and \(\mathbf{X}=(\mathbf{x}_{1},...,\mathbf{x}_{p})\in\mathbb{R}^{n\times p}\) to be the covariate matrix of \(n\) samples and \(p\) variables.
Given these data matrices, we establish the following multivariate linear model to analyze the relationship between response matrix \(\mathbf{Y}\) and covariate matrix \(\mathbf{X}\), which is characterized by the coefficient matrix \(\mathbf{B}\).

**Definition 3.1** (Multivariate Linear Model).: \[\mathbf{Y}=\mathbf{X}\mathbf{B}+\mathbf{W},\] (1)

_where \(\mathbf{B}\in\mathbb{R}^{p\times q}\) is the coefficient matrix and \(\mathbf{W}=(\mathbf{w}_{1},...,\mathbf{w}_{q})\in\mathbb{R}^{n\times q}\) is the matrix of error terms._

Our goal is to find the most salient data properties that correlate with the performance of GNN models given a 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).: \[\underset{\mathbf{B}}{\operatorname{argmin}}\frac{1}{2n}\|\mathbf{Y}-\mathbf{ X}\mathbf{B}\|_{2}^{2}+\lambda_{1}\|\mathbf{B}\|_{1}+\lambda_{g}\|\mathbf{B}\|_{2,1},\] (2)

_where \(\|\mathbf{B}\|_{1}=\sum_{i=1}^{p}\sum_{j=1}^{q}|\mathbf{B}_{ij}|\) is the \(L_{1}\) norm of \(\mathbf{B}\), \(\|\mathbf{B}\|_{2,1}=\sum_{i=1}^{p}\sqrt{\sum_{j=1}^{q}\mathbf{B}_{ij}^{2}}\) is the \(L_{2,1}\) group norm of \(\mathbf{B}\), and \(\lambda_{1},\lambda_{g}>0\) are the corresponding penalty parameters._

In particular, the \(L_{1}\) penalty encourages the coefficient matrix \(\mathbf{B}\) to be sparse, only selecting salient data properties. The \(L_{2,1}\) penalty further leverages the structure of the dependent variables and tries to make only a 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 \(\mathbf{B}\) in Equation 2, we employ an R package, MSGLasso [21], using matrices \(\mathbf{Y}\) and \(\mathbf{X}\) as input.

To ensure proper input for the MSGLasso solver [21], we have preprocessed the data by standardizing the columns of both \(\mathbf{Y}\) and \(\mathbf{X}\).

### Data Properties and Model Performance

Next, we introduce the metadata used for the regression analysis. We obtain both the benchmark datasets and the model performance using the Graph Learning Indexer (GLI) library [27].

Data Properties.We include the following benchmark datasets in our regression analysis: corona [42], citeseer [42], pubmed [42], texas [33], cornell [33], wisconsin [33], actor [33], squirrel [33], chameleon [33], arxiv-year [23], snap-patents [23], penn94 [23], pokec [23], genius [23], and twitch-gamers [23].

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);
* _Attribute_: Edge Homogeneity, In-Feature Similarity, Out-Feature Similarity, Feature Angular SNR, Homophily Measure, Attribute Assortativity.

The formal definition of these graph properties can be found in Appendix A.

Model Performance.For GNN models, we include GCN [19], GAT [37], GraphSAGE [13], MoNet [29], MixHop [1], 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.
### Analysis Results

The estimated coefficient matrix \(\mathbf{B}\) is presented in Table 1. As can be seen, the estimated coefficient matrix is fairly sparse, allowing us to 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 all 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 of the factors indicates whether this data property has a positive or negative correlation with the GNN performance.

Widely Influential Factors.We discover that the Gini coefficient of the degree distribution (Gini-Degree), Edge Homogeneity, and In-Feature Similarity impact all GNNs' model performance consistently.

* _Gini-Degree_\((-)\) measures how the graph's degree distribution deviates from the perfectly equal distribution, i.e., a regular graph. This is a crucial data property that dramatically influences GNNs' performance but remains under-explored in prior literature.
* _Edge Homogeneity_\((+)\) is a salient indicator for all GNN models' performance. This phenomenon 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 a subset of GNN models, although we do not yet have a 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.

\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline Graph Data Property & GCN & GAT & GraphSAGE & MoNet & MixHop & LINKX & MLP \\ \hline Edge Density & 0 & 0 & 0 & 0 & 0 & 0.0253 & 0.0983 \\
**Average Degree** & 0.2071 & 0 & 0.1048 & 0.1081 & 0 & 0.3363 & 0 \\
**Pseudo Diameter** & 0 & -0.349 & -0.1531 & 0 & -0.4894 & -0.3943 & -0.6119 \\ Degree Assortativity & 0 & 0 & 0 & -0.0744 & 0 & 0 & 0 \\ RSLCC & 0.1019 & 0 & 0 & 0.0654 & 0 & 0.1309 & 0 \\ ACC & 0 & 0 & 0 & 0 & 0 & 0 & -0.0502 \\ Transitivity & 0 & -0.0518 & 0 & -0.1372 & 0 & 0.2311 & 0 \\ Degeneracy & 0 & 0 & 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.4613 & 0.6396 & 0.2399 \\ Out-Feature Similarity & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
**Feature Angular SNR** & 0.2522 & 0 & 0.2506 & 0 & 0.2381 & 0.3563 & 0.3731 \\ Homophily Measure & 0 & 0.4072 & 0 & 0 & 0 & 0 & 0 \\ Attribute Assortativity & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The estimated coefficient matrix \(\mathbf{B}\) of the multivariate sparse regression analysis. Each entry indicates the strength (magnitude) and direction \((+,-)\) of the relationship between a graph data property and the performance of a GNN model. The six most salient data properties are indicated in **bold**.
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 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_, one of the most widely influential factors. In the following Section 4 and 5, we conduct theoretical analysis and controlled experiments to understand how Gini-Degree influences GNNs' performance.

## 4 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 separability of node representations produced by applying graph convolution to the node features. In the case that the graph data comes from a Degree-Corrected Stochastic Block Model, we show that nodes from different classes are more separable when their degree exceeds a threshold. This separability result relates the graph data's degree distribution to the GNN performance. Finally, we discuss the role of Gini-Degree on the GNN performance using implications of our theory.

### Notations and Sketch of Analysis

The Graph Data.Let \(\mathcal{G}=\{\mathcal{V},\mathcal{E}\}\) be an undirected graph, where \(\mathcal{V}\) is the set of nodes and \(\mathcal{E}\) is the set of edges. The information regarding the connections within the graph can also be summarized as an adjacency matrix \(\mathbf{A}\in\{0,1\}^{|\mathcal{V}|\times|\mathcal{V}|}\), where \(|\mathcal{V}|\) is the number of nodes in the graph \(\mathcal{G}\). Each node \(i\in\mathcal{V}\) possesses a \(d\)-dimensional feature vector \(\mathbf{x}_{i}\in\mathbb{R}^{d}\). The features for all nodes in \(\mathcal{G}\) can be stacked and represented as a feature matrix \(\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times d}\). In the context of node classification, each node \(i\) is associated with a class label \(y_{i}\in\mathcal{C}\), where \(\mathcal{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 an operation on the adjacency matrix and feature matrix of a graph \(\mathcal{G}\) to produce a new feature matrix \(\tilde{\mathbf{X}}\). Formally, the output of a single-layer graph convolution operation can be represented as \(\tilde{\mathbf{X}}=\mathbf{D}^{-1}\tilde{\mathbf{A}}\mathbf{X}\), where \(\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}\) is the augmented adjacency matrix with added self-loops, and \(\mathbf{D}\) is the diagonal degree matrix with \(\mathbf{D}_{ii}=\text{deg}(i)=\sum_{j\in[n]}\tilde{\mathbf{A}}_{ij}\). Hence, for each node \(i\in\mathcal{V}\), the new node representation will become \(\tilde{\mathbf{x}}_{i}\in\mathbb{R}^{d}\), which is the \(i\)th row of the output matrix \(\tilde{\mathbf{X}}\).

Sketch of Our Analysis.Our analysis builds upon and generalizes the theoretical framework introduced by Baranwal et al. [3], 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) [4; 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 a non-trivial generalization of the theory by Baranwal et al. [3]. Specifically, we first coin a new graph data generation model, Degree-Corrected Contextual Stochastic Block Model (DC-CSBM) that combines and generalizes Degree-Corrected SBM (DC-SBM) [17] and CSBM, and leverages heterogeneity in node degrees into consideration. 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 to sufficiently leverage the neighborhood information and become reliably separable. Notably, the incorporation of the node degree heterogeneity into the analysis requires a non-trivial adaptation of the analysis by Baranwal et al. [3].
### 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 a DC-CSBM with two classes.

DC-CSBM With 2 Classes.Let us define the class assignments \((\epsilon_{i})_{i\in[n]}\) as independent and identically distributed (i.i.d.) Bernoulli random variables coming from \(\text{Ber}(\frac{1}{2})\), where \(n=|\mathcal{V}|\) is the number of nodes in the graph \(\mathcal{G}\). These class assignments divide \(n\) nodes into 2 classes: \(C_{0}=\{i\in[n]:\epsilon_{i}=0\}\) and \(C_{1}=\{i\in[n]:\epsilon_{i}=1\}\). Assume that inter-class edge probability is \(q\) and intra-class edge probability is \(p\), and no self-loops are allowed. For each node \(i\), we additionally introduce a degree-correction parameter \(\theta_{i}\in(0,n]\), which can be interpreted as the propensity of node \(i\) to connect with others. Note that to keep the DC-SSBM identifiable and easier to analyze, we adopt a normalization rule to enforce the following constraint: \(\sum_{i\in C_{0}}\theta_{i}=|C_{0}|\), \(\sum_{i\in C_{1}}\theta_{i}=|C_{1}|\) and thus \(\sum_{i\in\mathcal{V}}\theta_{i}=n\).

Assumptions on Adjacency Matrix and Feature Matrix.Conditioning on \((\epsilon_{i})_{i\in[n]}\), each entry of the adjacency matrix \(\mathbf{A}\) is a Poisson random variable with \(\mathbf{A}_{ij}\sim\text{Poi}(\theta_{i}\theta_{j}p)\) if \(i,j\) are in the same class and \(\mathbf{A}_{ij}\sim\text{Poi}(\theta_{i}\theta_{j}q)\) if \(i,j\) are in different classes. On top of this, let \(\mathbf{X}\in\mathbb{R}^{n\times d}\) be the feature matrix where each row \(\mathbf{x}_{i}\) represents the node feature of node \(i\). Assume each \(\mathbf{x}_{i}\) is an independent \(d\)-dimensional Gaussian random vector with \(\mathbf{x}_{i}\sim\mathcal{N}(\boldsymbol{\mu},\frac{1}{d}\mathbf{I})\) if \(i\in C_{0}\) and \(\mathbf{x}_{i}\sim\mathcal{N}(\boldsymbol{\nu},\frac{1}{d}\mathbf{I})\) if \(i\in C_{1}\). We let \(\boldsymbol{\mu},\boldsymbol{\nu}\in\mathbb{R}^{d}\) to be fixed \(d\)-dimensional vectors with \(\|\boldsymbol{\mu}\|_{2},\|\boldsymbol{\nu}\|_{2}\leq 1\), which serve as the Gaussian mean for the two classes.

Given a particular choice of \(n,\boldsymbol{\mu},\boldsymbol{\nu},p,q\) and \(\theta=(\theta_{i})_{i\in[n]}\), we can define a class of random graphs generated by these parameters and sample a graph from such DC-CSBM as \(\mathcal{G}=(\mathbf{A},\mathbf{X})\sim\text{DC-CSBM}(n,\boldsymbol{\mu}, \boldsymbol{\nu},p,q,\theta)\).

### 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 \(\mathcal{V}_{s}\subseteq\mathcal{V}\), we say that \(\{\tilde{\mathbf{x}}_{i}:i\in\mathcal{V}_{s}\}\) is linearly separable if there exists some unit vector \(\mathbf{v}\in\mathbb{R}^{d}\) and a scalar \(b\) such that \(\mathbf{v}^{\top}\tilde{\mathbf{x}}_{i}+b<0,\forall i\in C_{0}\cap\mathcal{V} _{s}\) and \(\mathbf{v}^{\top}\tilde{\mathbf{x}}_{i}+b>0,\forall i\in C_{1}\cap\mathcal{V} _{s}\). Note that linear separability is closely related to GNN performance. Intuitively, more nodes being linearly separable will lead to better GNN performance.

Degree-Thresholded Subgroups of \(C_{0}\) and \(C_{1}\).To better control the behavior of graph convolution operation, we will focus on particular subgroups of \(C_{0}\) and \(C_{1}\) where the member nodes having degree-corrected factor larger or equal to a pre-defined threshold \(\alpha>0\). Slightly abusing the notations, we denote these subgroups as \(C_{0}(\alpha)\) and \(C_{1}(\alpha)\), which are formally defined below.

**Definition 4.1** (\(\alpha\)-Subgroups).: _Given any \(\alpha\in(0,n]\), define \(\alpha\)-subgroups of \(C_{0}\) and \(C_{1}\) as follows:_

\[C_{0}(\alpha) =\{j\in[n]:\theta_{j}\geq\alpha\text{ and }j\in C_{0}\},\] \[C_{1}(\alpha) =\{j\in[n]:\theta_{j}\geq\alpha\text{ and }j\in C_{1}\}.\]

Let \(\mathcal{V}_{\alpha}:=C_{0}(\alpha)\cup C_{1}(\alpha)\), we are interested in analyzing the linear separability of the node representations after the graph convolution operation, namely \(\{\tilde{\mathbf{x}}_{i}:i\in\mathcal{V}_{\alpha}\}\). Recall that for each node \(i\), \(\tilde{\mathbf{x}}_{i}=\frac{1}{\text{deg}(i)}\sum_{j\in\mathcal{N}(i)}\mathbf{ x}_{j}\), where \(\mathcal{N}(i)\) is the set of neighbors of node \(i\).

Relationship Between \(\alpha\) 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 \(\omega(d\log d)\leq n\leq O(\text{poly}(d))\)._

**Assumption 4.3** (Edge Probabilities).: _Define \(\Gamma(p,q):=\frac{p-q}{p+q}\). Assume the edge probabilities \(p,q\) satisfy \(p,q=\omega(\log^{2}(n)/n)\) and \(\Gamma(p,q)=\Omega(1)\)._

Theorem 4.4 asserts that if the threshold \(\alpha\) is not too small, then the set \(\mathcal{V}_{\alpha}=C_{0}(\alpha)\cup C_{1}(\alpha)\) can be linear separated with high probability. The proof of Theorem 4.4 can be found in Appendix C.
**Theorem 4.4** (Linear Separability of \(\alpha\)-Subgroups).: _Suppose that Assumption 4.2 and 4.3 hold. For any \((\mathbf{X},\mathbf{A})\sim\text{DC-CSBM}(n,\boldsymbol{\mu},\boldsymbol{\nu},p,q,\theta)\), if \(\alpha=\omega\left(\max\left(\frac{1}{\log n},\frac{\log n}{dn(p+q)\|\boldsymbol {\mu}-\boldsymbol{\nu}\|_{2}^{2}}\right)\right)\), then_

\[\mathbb{P}(\{\tilde{\mathbf{x}}_{i}:i\in\mathcal{V}_{\alpha}\}\text{ is linearly separable})=1-o_{d}(1),\]

_where \(o_{d}(1)\) is a quantity that converges to 0 as \(d\) approaches infinity._

Note that Theorem 4.4 suggests that, when the heterogeneity of node degrees is taken into consideration, the nodes with degrees exceeding a threshold \(\alpha\) are more likely to be linearly separable. And the requirement for the threshold \(\alpha\) depends on the DC-CSBM parameters: \(n,p,q,\boldsymbol{\mu},\boldsymbol{\nu}\).

**Remark 4.5**.: _If we let \(p,q\in\Theta(\frac{\log^{3}n}{n})\) and \(\|\boldsymbol{\mu}-\boldsymbol{\nu}\|_{2}\) be fixed constant, then the requirement can be reduced to \(\alpha\in\omega(\frac{1}{\log n})\), which is not too large. Given this particular setting and reasonable selection of \(p,q\), the regime of acceptable \(\alpha\) 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 \(\alpha>0\) that meets the criteria in the statement, we can consider

1. _Negative correlation between Gini-Degree and the size of \(\mathcal{V}_{\alpha}\)_: 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 \(\alpha\)1 and being placed in \(\mathcal{V}_{\alpha}\). Hence, a dataset with a higher (or lower) Gini-Degree will lead to a smaller (or larger) size of \(\mathcal{V}_{\alpha}\). Footnote 1: Note that the expected value of the degree of node \(i\) is proportional to \(\theta_{i}\) when we ignore self-loops. (See Appendix C for more information.) Thus, the lower bound \(\alpha\) on degree-corrected factors can be translated to the lower bound \(n(p+q)\alpha\) on degrees.
2. _Positive correlation between the size of \(\mathcal{V}_{\alpha}\) 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 \(\mathcal{V}_{\alpha}\) corresponding to the minimum possible \(\alpha\).

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-Degree) and the GNN performance, we conduct a controlled experiment using synthetic graph datasets.

Experiment Setup.We first generate a series of synthetic graph datasets using the GraphWorld library [31]. To investigate the causal effect of Gini-Degree, we manipulate the data generation parameters to obtain datasets with varying Gini-Degree while keeping a bunch of other properties fixed. Specifically, we use the SBM generator in GraphWorld library and set the number of nodes \(n=5000\), the average degree as \(30\), the number of clusters as \(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 as \(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 as \(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 1 on each dataset. We randomly 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 obtain the metadata in Section 3. We run five independent trials with different random seeds.

**Experiment Results.** The experiment results are shown in Table 2.

We observe an evident monotonically decreasing trend for the performance of the graph-based 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 on the performance of MLP. The result on MLP also indicates that we have done a reasonably well-controlled experiment.

## 6 Conclusion

In this work, we propose a novel metadata-driven approach that can efficiently identify critical graph data properties influencing the performance of GNNs. This is a 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 a side product, this paper also highlights the considerable impact of the degree distribution, a salient data property identified through our metadata-driven regression analysis, on the GNN performance. We present a novel theoretical analysis and a carefully controlled experiment to demonstrate this impact.

#### Acknowledgement

The authors would like to thank Pingbang Hu for the feedback on the draft.
