## 2 Materials and Methods
### Interpretability and Feature Importance
#### 2.7.1 Model Interpretability
### The Complexity of Graph Convolutional Networks (GCNs) and SHapley Additive exPlanations (SHAP)

The complexity of graph convolutional networks (GCNs) is crucial because it determines the computational cost, especially when dealing with large-scale graphs ([PERSON] et al. [67]). This complexity arises from the need to aggregate information from neighboring nodes through matrix multiplications involving the adjacency matrix and feature matrix at each layer. Understanding the complexity of GCNs helps in optimizing the model for efficiency. In practice, large graphs with millions of nodes and edges can make training and inference computationally expensive. By analyzing the complexity, researchers and practitioners can identify potential bottlenecks of GCN. The complexity of GCN ([PERSON] et al. [68]) can be obtained as follows:

\[O\Big{(}L|E|F^{2}+LN^{2}F\Big{)} \tag{3}\]

where \(L\) denotes the number of graph convolutional layers within the network. Each layer includes operations that propagate node features across the graph. \(|E|\) refers to the number of edges in the graph. Because the adjacency matrix in GCN is usually sparse, the computations for graph-related operations depend more on the number of edges than on nodes. \(F\) represents the number of features per node at each layer. At each layer, the feature matrix of size \(N\times F\), where \(N\) is the number of nodes, is multiplied by the weight matrices. \(F^{2}\) represents the feature transformation at each layer. \(N^{2}F\) results from the fact that certain operations require dense matrix multiplications between node features. \(L|E|F^{2}\) describes the cost of sparse matrix multiplications between the adjacency matrix and feature matrix. It is paramount when the graph is sparse, i.e., when the \(N^{2}\) is much larger than the number of edges \(|E|\). \(LN^{2}F\) describes the cost of operations involving all node pairs in the graph. It is most important for dense graphs where there are plenty of connections between nodes. Regarding the complexity of computing SHAP scores, previous research has demonstrated that SHAP scores can be calculated in polynomial time for binary classifiers that are defined on binary features ([PERSON] et al. [69]). More recently, this finding has been expanded to discrete non-binary features by [PERSON] et al. [70]. There are three limitations to this work. The first is its application only to binary classifiers, i.e., classifiers for which the set of classes is \(\{0,1\}\). Another limitation is its read-once circuit. The third one is the discrete feature. Independent research [PERSON] et al. [71] proved that SHAP scores can be efficiently computed in polynomial time for certain families, e.g., additive tree ensembles, including the XGBoost model we use, linear regression models, decision trees, factorization machines, etc. ## 3 Case Study

Identifying potential leaders within an organization is essential because it enables one to find nodes within the social network that have key values. Because they have more relationships with other members of the company and greater task-specific knowledge of work-related problems, leaders are seen as valuable contributors. We aim to use state-of-the-art GCN, XAI, and AutoML methods to identify leaders at organizations. From an HR perspective, our strategy helps organizations retain employees who have the potential to become members of the leadership team in the future if we can identify members who behave like leaders. We validate our approach with datasets from different industries because various organizational cultures can show their unique patterns of leadership and social interactions. It will enhance the richness and comprehensiveness of our study. ### Leaders in a Social Network at an IT Company with Real-World Datasets

For the development of this work, a project is developed by an IT company, which is a leader in providing intra-logistics solutions and warehouse automation globally. It has a network of 53 locations in the world.