A Simple and Scalable Graph Neural Network for Large Directed Graphs
Node classification is one of the hottest tasks in graph analysis. Though
existing studies have explored various node representations in directed and
undirected graphs, they have overlooked the distinctions of their capabilities
to capture the information of graphs. To tackle the limitation, we investigate
various combinations of node representations (aggregated features vs. adjacency
lists) and edge direction awareness within an input graph (directed vs.
undirected). We address the first empirical study to benchmark the performance
of various GNNs that use either combination of node representations and edge
direction awareness. Our experiments demonstrate that no single combination
stably achieves state-of-the-art results across datasets, which indicates that
we need to select appropriate combinations depending on the dataset
characteristics. In response, we propose a simple yet holistic classification
method A2DUG which leverages all combinations of node representations in
directed and undirected graphs. We demonstrate that A2DUG stably performs well
on various datasets and improves the accuracy up to 11.29 compared with the
state-of-the-art methods. To spur the development of new methods, we publicly
release our complete codebase under the MIT license.
Seiji Maekawa, Yuya Sasaki, Makoto Onizuka
# Why Using Either Aggregated Features or Adjacency

###### Abstract

Node classification is one of the hottest tasks in graph analysis. In this paper, we focus on the choices of node representations (aggregated features vs. adjacency lists) and the edge direction of an input graph (directed vs. undirected), which have a large influence on classification results. We address the first empirical study to benchmark the performance of various GNNs that use either combination of node representations and edge directions. Our experiments demonstrate that no single combination stably achieves state-of-the-art results across datasets, which indicates that we need to select appropriate combinations depending on the characteristics of datasets. In response, we propose a simple yet holistic classification method **A2DUG** which leverages all combinations of node representation variants in directed and undirected graphs. We demonstrate that A2DUG stably performs well on various datasets. Surprisingly, it largely outperforms the current state-of-the-art methods in several datasets. This result validates the importance of the adaptive effect control on the combinations of node representations and edge directions.

## 1 Introduction

The semi-supervised node classification task is one of the hottest topics in graph analysis. Its goal is to predict unknown labels of the nodes by using the topology structure and node attributes, given partially labeled networks. Many algorithms [2; 6; 8; 12; 13; 14; 16; 21; 23; 32; 35; 38; 42; 43] have been proposed to tackle this task and they have gained wide research interest from various domains including chemistry [4; 7], physics [29], social science [12], and neuroscience [41]. Since nodes and edges are core components in graphs, our focus is on to what extent we can improve the classification accuracy by leveraging various node representations and edge directions. Actually, existing techniques primarily emphasize two key aspects: 1) node representations (aggregated features vs. adjacency lists), and 2) edge directions within input graphs (directed vs. undirected).

Aggregated feature vs. Adjacency list.There are two major approaches to constructing node representations: 1) Graph Neural Networks (GNNs) adopting feature aggregation [2; 12; 17; 30; 32; 39] and 2) methods using adjacency lists as node features [14; 15; 16]. As for the first approach, GNNs adopt feature aggregation that aggregates node features/embeddings from local neighbor nodes to obtain denoised features (we call _aggregated features_). The second approach utilizes an adjacency matrix, i.e., the adjacency list of a node (node ID list), as its node feature. Hence, aggregated features and adjacency lists capture the different characteristics of nodes and complement each other.

Figure 1 depicts two motivating examples in which methods using only either aggregated features or adjacency lists cannot correctly predict the node labels. In these example graphs, nodes indicate papers, edges indicate citations, and each node has its attribute vector.
In Figure 0(a), the prediction target is the publication year of each paper. Using adjacency lists, nodes \(p\) and \(p^{\prime}\) are distinguishable as they connect to different nodes. Since nodes \(p\) and \(q\) share the same adjacency lists and node features, the label of node \(p\) is correctly predicted as \(2016\), the same label as that of \(q\). Similarly, the label of node \(p^{\prime}\) is accurately predicted as \(2018\) using information from labeled node \(q^{\prime}\). However, methods utilizing feature aggregation fail to predict the distinct labels for node \(p\) and \(p^{\prime}\) because they share the same aggregated features, i.e., the same node features within 1-hop and 2-hop, resulting in identical embeddings. Next, Figure 0(b) shows another example graph in which labels indicate the research fields of papers, e.g., NLP and DB. In this example, the methods using adjacency lists fail to predict the label of node \(t\) because there are no intersections between the adjacency lists of node \(t\) and the labeled node \(x\), which shares the same label as node \(t\). As for methods using feature aggregation, node \(t\) obtains the embedding similar to those of locally neighboring nodes \(u,v,\) and \(w\). As a result, they are expected to correctly predict the label of node \(t\), i.e., "DB".

**Directed graph vs. Undirected graph.** Most methods focus on undirected graphs [2, 12, 13, 21, 35, 38, 42, 43]. Since edges in most graphs are potentially associated with direction information that may contribute to classification quality, several existing studies have addressed a node classification task for directed graphs. First, a small number of GNN algorithms [30, 31, 39] utilizes feature aggregation in directed graphs rather than in undirected graphs. Second, as for methods using adjacency lists, users can choose whether to use a directed or undirected adjacency list for input. However, the choice of utilizing a directed or undirected graph depends on the characteristics of datasets.

We give two examples to show that users need to choose whether to use the input graph as directed or undirected. In Figure 0(a), since the prediction target is the publication years of papers, edge directions play a crucial role, i.e., edge directions indicate time directions cited from new papers to old ones. For instance, nodes \(r\) and \(s\) have no incoming edge, and thus methods using directed graphs can predict that they are recent papers, i.e., their labels are \(2022\). If we choose the input graph as undirected, methods cannot utilize the time direction. We also give another example in which an undirected graph is preferable in Figure 0(b). In this example, the nodes in a densely connected subgraph have the same label. For instance, node \(t\) does not receive any information from its neighbor since it has no incoming edge. This means that methods using only directed graphs fail to utilize the existence of edges. Hence, users need to adaptively select a directed or undirected graph depending on datasets.

**Issues in existing studies.** The above discussions on node representations and edge directions clarify that users need to select whether to use aggregated features or adjacency lists and whether to treat an input graph as directed or undirected. However, it is burdensome and difficult to choose an appropriate combination for each dataset. Nevertheless, no studies have comprehensively investigated the performance of methods using either combination of node representations and edge directions with various directed graphs.

**Contributions.** First, we address the following research question: **Q1.** _To what extent do node representations (aggregated features vs. adjacency lists) and edge directions (directed vs. undirected) affect node classification quality?_ To answer this question, we conduct experiments using various existing methods including state-of-the-art methods on eight directed graphs. The experiments demonstrate that classification results highly depend on the characteristics of graphs, e.g., methods using edge directions perform well on a graph in which the prediction target is publication years (arxiv-year [16]) and methods ignoring edge directions perform well on a graph in which the prediction target is research fields (ogbn-arxiv [10]). Hence, we address the following research question: **Q2.** _Can we adaptively choose the best combination of node representations and edge

Figure 1: Motivating examples. The red and white nodes indicate labeled and unlabeled nodes belonging to training and validation/test sets, respectively. To make the explanation easier to understand, we show the ground truth labels of all nodes.
directions for each dataset?_ To answer this question, we propose a simple yet holistic method, **A2DUG**, that leverages all combinations of node representation variants in directed and undirected graphs, as illustrated in Figure 2. Further, it achieves high scalability by adopting precomputation-based GNNs [21; 34]. We summarize key insights through our experiments as follows.

* Our empirical study demonstrates that no existing methods stably perform well across datasets since they use only either combination of node representations and edge directions.
* By incorporating both aggregated features and adjacency lists in directed/undirected graphs into the model training, the performance of A2DUG is robust against various datasets. Surprisingly, it achieves better results than state-of-the-art methods with large margins in arxiv-year, snap-patents, and wiki, despite its simple architecture. This is because A2DUG can adaptively combine and control the effects from aggregated features and adjacency lists in directed/undirected graphs rather than simply selecting either combination.
* A2DUG scales well to the largest dataset wiki having more than \(0.3\) billion edges because it adopts scalable batchwise training, similarly to precomputation-based GNNs.

We hope that this paper demonstrates the potential of future research on the combination of aggregated features and adjacency lists in directed/undirected graphs. To spur the development of new methods, we publicly release our complete codebase2 under the MIT license.

Footnote 2: [https://github.com/seijimaekawa/A2DUG](https://github.com/seijimaekawa/A2DUG)

## 2 Preliminaries

An _attributed graph with class labels_ is a triple \(G=(\mathbf{A},\mathbf{X},\mathbf{C})\) where \(\mathbf{A}\in\{0,1\}^{n\times n}\) is an adjacency matrix, \(\mathbf{X}\in\mathbb{R}^{n\times d}\) is an attribute matrix assigning attributes to nodes, and a class matrix \(\mathbf{C}\in\{0,1\}^{n\times y}\) contains class information of each node, and \(n,d,y\) are the numbers of nodes, attributes, and classes, respectively. We denote a transposed adjacency matrix by \(\mathbf{A}^{\top}\), where \(\mathbf{A}^{\top}_{ij}=\mathbf{A}_{ji}\). Given an adjacency matrix \(\mathbf{A}\), we can obtain an undirected adjacency matrix \(\mathbf{A}^{\text{und}}\in\{0,1\}^{n\times n}\), where \(\mathbf{A}^{\text{und}}_{ij}=\mathbf{A}^{\text{und}}_{ji}=1\) if \(\mathbf{A}_{ij}=1\) or \(\mathbf{A}_{ji}=1\) otherwise \(\mathbf{A}^{\text{und}}_{ij}=\mathbf{A}^{\text{und}}_{ji}=0\). Also, we define \(\Omega_{l}\) as the class for label \(l\), i.e., the set of nodes labeled with \(l\). We define the degree matrix \(\mathbf{D}=\text{diag}(D_{1},\dots,D_{n})\in\mathbb{R}^{n\times n}\) as a diagonal matrix, where \(D_{i}\) expresses the degree of node \(i\). We also define an identity matrix \(\mathbf{I}=\text{diag}(1,\dots,1)\in\mathbb{R}^{n\times n}\).

**Problem Definition (Node classification).** We split nodes into train/validation/test sets. Given an adjacency matrix \(\mathbf{A}\), an attribute matrix \(\mathbf{X}\), and a partial class matrix \(\mathbf{C}^{\prime}\) which contains class information of nodes in the train/validation sets, we predict the labels of the nodes in the test set.

### Prior Work of Node Classification

To address the aforementioned node classification task, existing studies have proposed a variety of methods including GNNs and methods using adjacency lists. We briefly explain their motivations and several key instances. We summarize the input of existing methods and A2DUG in Table 1.

Figure 2: Our proposal **A2DUG** leverages both aggregated features and adjacency lists in directed/undirected graphs through MLP and GNN, respectively. \(\text{MLP}_{\mathbf{X}}\), \(\text{MLP}_{\mathbf{A}}\), and \(\text{MLP}_{\mathbf{A}^{\text{und}}}\) create node representations for node features \(\mathbf{X}\), adjacency lists \(\mathbf{A}\), and undirected adjacency lists \(\mathbf{A}^{\text{und}}\). GNN and \(\text{GNN}^{\text{und}}\) compute aggregated features by inputting node features and adjacency lists. Finally, it concatenates the embeddings from MLP and GNN, and then outputs the results via \(\text{MLP}_{\text{final}}\). For the sake of brevity, we omit a transposed adjacency list in this figure (see the details in Section 3).
GNNs using feature aggregation in undirected graphs.Feature aggregation is an effective approach to obtain node representations denoised by locally neighboring nodes, e.g., the average, sum, or max pooling of neighboring nodes, specifically for homophilous graphs3. Feature aggregation is operated in graph convolution which has been proposed in [12]. Since then, many successor GNN techniques [2; 6; 8; 13; 21; 23; 32; 35; 38; 42; 43] adopt feature aggregation in order to obtain node representations/embeddings suitable for various downstream tasks including node classification and link prediction. These GNNs do not directly use adjacency lists as node features and focus on only undirected graphs.

Footnote 3: In homophilous graphs, nodes in the same class tend to be connected.

GNNs for directed graphs.While many studies in the literature on GNNs have addressed developing techniques for undirected graphs, several studies [18; 30; 31; 39] have proposed techniques for node classification in directed graphs. DiGraph [30] extends the spectral-based graph convolution to directed graphs by leveraging the inherent connections between graph Laplacian and stationary distributions of PageRank [24]. MagNet [39] utilizes a complex Hermitian matrix known as the magnetic Laplacian, where the real and imaginary parts represent the undirected and directed edges, respectively. However, similar to GNNs for undirected graphs, these GNNs for directed graphs do not use adjacency lists as node features. While not only for node classification, several studies [9; 33] have addressed a recommendation task in directed graphs, they are out of our scope.

Methods using adjacency lists as node features.Several node embedding methods [11; 15; 36] leverage an adjacency matrix as node features. LINKX [16] achieves state-of-the-art performance on non-homophilous graphs. However, LINKX obtains lower accuracy on homophilous graphs than existing GNNs since it does not adopt graph convolution that is tailored to capture the homophily. A recent work, GloGNN++ [14], creates node features by combining an adjacency matrix and an attribute matrix. Then, it aggregates information from global nodes in the graph, i.e., nodes having similar combined node features, while other GNNs aggregate information from local neighbors4. Since these methods use adjacency lists as node features, they can be easily applied to directed graphs by replacing undirected adjacency lists with directed adjacency lists. However, users need to decide whether to use a directed or undirected graph for each dataset. Also as for directed graphs, inverse edges may have different semantics from the original edges. Hence, these choices for an appropriate input to their methods increase users' burdens. In summary of this subsection, no existing methods combine aggregated features and adjacency lists in directed/undirected graphs though they complement each other.

Footnote 4: As we explained in this subsection, we categorize GloGNN++ into methods using adjacency lists since it utilizes adjacency lists for node features and does not use local feature aggregation.

### Related Work of Benchmarking GNNs

Several studies [3; 5; 37] empirically evaluate various GNNs to benchmark their performance from diverse perspectives such as scalability to large-scale graphs, accuracy in various tasks, and the impact of components in GNN architectures. Other studies [19; 25] aim to clarify the strengths and weaknesses of GNNs by generating various synthetic graphs. To the best of our knowledge, no study has comprehensively explored both GNNs and methods utilizing adjacency lists with respect to edge directions.

\begin{table}
\begin{tabular}{l|c c c c} \hline Methods & Aggregated feature & Adjacency list & Directed graph & Undirected graph \\ \hline GNNs for undirected graphs & & & & \\ GNNs for directed graphs & & & & \\ Methods using adjacency lists & & & & \\ \hline A2DUG (proposal) & & & & \\ \hline \end{tabular}
\end{table}
Table 1: Node representations and edge directions of existing methods and A2DUG. \(\bigvee\) indicates that methods (do not) support the node representation and edge direction. \(\bigvee^{*}\) indicates that methods use either a directed or undirected graph.
A2DUG: A Simple yet Holistic Method Leveraging Aggregated Features and Adjacency Lists in Directed/Undirected Graph

We propose a simple yet holistic method leveraging Aggregated features and **A**djacency lists in **D**irected/**U**ndirected **G**raphs (**A2DUG**) that satisfies two key design criteria for the effectiveness and scalability: **D1** leveraging both aggregated and adjacency lists features in directed/undirected graphs, **D2** adopting precomputation-based GNNs for minibatch training.

**D1: Leveraging both aggregated features and adjacency lists in directed/undirected graphs.** First, to adaptively control the effect from aggregated features and adjacency lists in directed/undirected graphs during the model training, we simply input all the combinations to multi-layer perceptions (MLPs) as follows:

\[\mathbf{Y}=\text{MLP}_{\text{final}}\Big{(}\sigma(\mathbf{H_{X}}\|\mathbf{H_{A}}\|\mathbf{H_{A ^{\top}}}\|\mathbf{H_{A^{\text{md}}}}\|\mathbf{H_{\text{GNN}}}\|\mathbf{H_{\text{GNN}^{ \top}}}\|\mathbf{H_{\text{GNN}^{\text{md}}}})\Big{)}, \tag{1}\]

where \(\mathbf{Y}\) is the predicted labels, \(\|\) indicates a concatenation operation, \(\sigma\) indicates an activation function, e.g., ReLU, and \(\mathbf{H_{X}},\mathbf{H_{A}},\mathbf{H_{A^{\top}}},\mathbf{H_{A^{\text{md}}}},\mathbf{H_{\text{GNN }}},\mathbf{H_{\text{GNN}^{\top}}},\mathbf{H_{\text{GNN}^{\text{md}}}}\) are node representation matrices of node features, adjacency lists, transposed adjacency lists, undirected adjacency lists, aggregated features in directed graphs, transposed aggregated features in directed graphs, and aggregated features in undirected graphs, respectively. We include the node representations from _transposed_ directed graphs5, i.e., \(\mathbf{H_{A^{\top}}}\) and \(\mathbf{H_{\text{GNN}^{\top}}}\), since inverse edges may have different semantics from the original edges. Each \(\mathbf{H}\) is formulated as follows:

Footnote 5: Transposed directed graphs indicate graphs where edge directions are opposite to their original graphs.

\[\mathbf{H_{X}}=\text{MLP}_{\mathbf{X}}(\mathbf{X}), \tag{2}\] \[\mathbf{H_{A}}=\text{MLP}_{\mathbf{A}}(\mathbf{A}),\ \ \mathbf{H_{A^{\top}}}=\text{MLP}_{\mathbf{A^{\top}}}(\mathbf{A^{ \top}}),\ \ \mathbf{H_{A^{\text{md}}}}=\text{MLP}_{\mathbf{A^{\text{md}}}}(\mathbf{A^{\text{md}}}),\] \[\mathbf{H_{\text{GNN}}}=\text{GNN}(\mathbf{A},\mathbf{X}),\ \ \mathbf{H_{\text{GNN}^{\top}}}=\text{GNN}^{\top}(\mathbf{A^{ \top}},\mathbf{X}),\ \ \mathbf{H_{\text{GNN}^{\text{md}}}}=\text{GNN}^{\text{md}}(\mathbf{A^{\text{md}}},\mathbf{X }),\]

where \(\text{GNN}\), \(\text{GNN}^{\top}\), and \(\text{GNN}^{\text{md}}\) are GNN-based encoders. Since A2DUG leverages both aggregated features and adjacency lists in directed/undirected graphs, it satisfies the first design criteria6.

Footnote 6: While other model architectures may satisfy our design criteria, our model architecture is the simplest among the ones satisfying the design criteria

Footnote 7: Though other GNNs can also be applied to our proposal, its scalability cannot be ensured in the case.

**D2: Adopting precomputation-based GNNs for minibatch training.** Second, to ensure the scalability of our proposal, we adopt precomputation-based GNNs, which ensures high scalability while showing competitive classification quality to other GNNs7. Existing precomputation-based GNNs [6, 21, 34] compute feature aggregation as a preprocess. Their models thus can be trained with small input batches of node features once features are computed, leading to their high scalability. Also, motivated by existing GNNs [21], we utilize both adjacency matrices with and without self-loops, i.e., \(\mathbf{A}\) and \(\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}\), which improve the classification quality in both homophilous and non-homophilous graphs. We formulate a \(k\) layer GNN-based graph encoder as follows:

Footnote 7: Though other GNNs can also be applied to our proposal, its scalability cannot be ensured in the case.

\[\text{GNN}_{\text{precomp}}=\text{MLP}(\mathbf{A}\mathbf{X}\|\hat{\mathbf{A}}\mathbf{X}\|\bm {A^{2}}\mathbf{X}\|\hat{\mathbf{A}^{2}}\mathbf{X}\|\ldots\|\mathbf{A^{k}}\mathbf{X}\|\hat{\mathbf{A}^{ k}}\mathbf{X}). \tag{3}\]

Also, we derive the formula for \(\text{GNN}_{\text{precomp}}^{\top}\) by replacing \(\mathbf{A}\) in Eq (3) with \(\mathbf{A}^{\top}\).

As for feature aggregation in an undirected graph, an adjacency matrix is typically normalized by node degrees [12, 21, 32, 34]. Following this, we apply the node degree-normalization to an undirected adjacency matrix and formulate a GNN-based graph encoder for undirected graphs as follows:

\[\text{GNN}_{\text{precomp}}^{\text{und}}=\text{MLP}(\mathbf{S}\mathbf{X}\|\hat{\mathbf{S} }\mathbf{X}\|\mathbf{S}^{2}\mathbf{X}\|\hat{\mathbf{S}}^{2}\mathbf{X}\|\ldots\|\mathbf{S}^{k}\mathbf{X}\| \hat{\mathbf{S}}^{k}\mathbf{X}), \tag{4}\]

where \(\mathbf{S}\) is a degree-normalized adjacency matrix, i.e., \(\mathbf{S}=(\mathbf{D^{\text{und}}})^{-\frac{1}{2}}\mathbf{A^{\text{und}}}(\mathbf{D^{\text{und }}})^{-\frac{1}{2}}\), and \(\hat{\mathbf{S}}\) is a degree-normalized adjacency matrix with self-loops.

**Training procedure.** We train our proposed model in an end-to-end training framework for a node classification task. To scale the training of the model for large-scale graphs, we adopt batchwise training which is introduced in existing precomputation-based GNNs [21, 34] and methods using adjacency lists [16]. To be concrete, we can handle \(\mathbf{X},\mathbf{A},\mathbf{A}^{\top},\mathbf{A^{\text{md}}},\mathbf{A}\mathbf{X},\hat{\mathbf{A}}\mathbf{X}, \mathbf{A}^{\top}\mathbf{X},\hat{\mathbf{A}}^{\top}\mathbf{X},\)
\(\mathbf{S}\mathbf{X},\hat{\mathbf{S}}\mathbf{X},\ldots,\mathbf{A}^{k}\mathbf{X},\hat{\mathbf{A}}^{k}\mathbf{X},( \mathbf{A}^{\top})^{k}\mathbf{X},(\mathbf{A}^{\top})^{k}\mathbf{X},\mathbf{S}^{k}\mathbf{X}\), and \(\hat{\mathbf{S}}^{k}\mathbf{X}\) as node features and execute row-wise decomposition for batchwise training. Hence, the proposed method satisfies the second key design, i.e., it scales well to large-scale graphs.

Connection with existing methods.Since A2DUG is based on a general and holistic form of leveraging both aggregated features and adjacency lists in directed/undirected graphs, it can employ any existing method as a component in Eq. (1). For example, A2DUG can imitate LINKX and GloGNN++, which are methods using adjacency lists, by utilizing their formulations to generate one of the node representations in Eq. (1), e.g., \(\mathbf{H_{A}}\) or \(\mathbf{H_{A^{\text{md}}}}\). Other examples are GCN [12], FSGNN [21], and ACMGCN [17], which can be used as \(\mathbf{H_{\text{GNN}^{\text{md}}}}\). In this paper, to ensure high scalability, A2DUG adopts simple and scalable components in its model architecture (see Eq. (2), (3), and (4)).

Complexity.The precomputation and training step of A2DUG have time complexity of \(\mathcal{O}(dk|E|+(h|E|+ndkh+nh^{2}L)T)\), in which \(h\) is the hidden dimension, \(|E|\) is the number of edges, \(L\) is the number of MLP's layers, and \(T\) is the number of epochs. This is because it requires \(\mathcal{O}(dk|E|)\) to precompute aggregated features within \(k\)-hops. Then, for the training step, it requires \(\mathcal{O}(h|E|)\) cost for the first linear mapping of \(\mathbf{A},\mathbf{A}^{\top}\), and \(\mathbf{A^{\text{md}}}\), \(\mathcal{O}(ndkh)\) cost for the first linear mapping of aggregated features within \(k\)-hops, and \(\mathcal{O}(nh^{2}L)\) cost for MLP operations on hidden features. This complexity is comparable with existing scalable methods using aggregated features or adjacency lists, e.g., FSGNN or LINKX, since A2DUG also employs their efficient feature precomputation and model architectures. Detailed discussion is described in our supplementary material.

## 4 Empirical Studies

We aim to answer the following questions: **Q1.**_How effectively and efficiently do existing methods perform in various graphs?_ **Q2.**_How does_ A2DUG _perform well?_ **Q3.**_To what extent do aggregated features and adjacency lists in directed/undirected graphs affect node classification?_

Datasets.We use eight directed graphs: Two small-scale chameleon and squirrel[26]8, three middle-scale genius, arxiv-year [16], and ogbn-arxiv [10], and three large-scale pokec, snap-patents, and wiki [16]. We note arxiv-year and ogbn-arxiv have the same graph structure and node features but have different classes. We follow the same way to split training/validation/test sets as the papers that propose the datasets [10; 16; 26]. We summarize the statistics of the datasets in the supplementary materials.

Footnote 8: Since a study [26] pointed out the presence of a large number of duplicate nodes in the original datasets of chameleon and squirrel, we use the filtered versions that do not have any duplicate node.

Baselines.For GNNs using feature aggregation in undirected graphs, we use GCN [12], SGC [34], GPRGNN [2], FSGNN [21], and ACMGCN[17]. For GNNs for directed graphs, we use DGCN[31], DiGraph [30], its variant DiGraphIB, and MagNet [39]. As for methods using adjacency lists as node features, we use LINK [40], LINKX [16], and GloGNN++ [14]. We also execute a graph-agnostic classifier, multi-layer perceptron (MLP) as a baseline, i.e., it ignores the topology structure.

Settings.We report the performance as mean classification accuracy and standard deviation over five random runs with different random seeds. As following [16], we use ROC-AUC as the metric for the class-imbalanced genius dataset (about \(80\%\) of nodes are in the majority class), as it is less sensitive to class-imbalance than accuracy. In the methods using adjacency lists (i.e., LINK, LINKX, and GloGNN++), we evaluate both directed and undirected graphs as their inputs. The more detailed settings are described in the supplementary material.

We use a single NVIDIA A100-PCIE-40GB for all our experiments. As for large datasets, snap-patents, pokec, and wiki, we use minibatch training by setting batchsizes to \(10,10\), and \(20\), respectively. To efficiently precompute aggregated features on the largest dataset wiki, which does not fit to the GPU memory, we utilize the block-wise precomputation scheme proposed in [20].

### Q1. Benchmarking Existing Methods

To answer the first question, we benchmark the performance of existing methods in directed and undirected graphs. Tables 2 and 3 show the node classification results in small-/middle-scale and large-scale graphs, respectively. We observe that no single existing method stably achieves high classification quality across datasets. This motivates us to propose a new method A2DUG. From
Table 2, we can see that FSGNN, which uses aggregated features in undirected graphs, obtains the highest accuracy for chameleon, squirrel, and ogbn-arxiv. While, in arxiv-year, the methods that can capture edge directions such as LINK directed, LINKX directed, GloGNN++ directed, and Magnet, achieve much higher accuracy than FSGNN. Also, in genius, LINKX undirected and GloGNN++ undirected achieve higher accuracy than the others. We here note that DGCN, Digraph, and DigraphIB show low scalability due to the computationally heavy operations, e.g., the computation of second-order proximity and eigenvectors of an adjacency matrix.

From Table 3, we can see MLP, SGC, FSGNN, LINK, and LINKX scale well to large-scale graphs, which adopt minibatch training. In large-scale graphs, methods using adjacency lists LINK, LINKX, and GloGNN++ outperform other methods adopting feature aggregation. This means that the information from adjacency lists is more important to predict labels in these datasets than one from aggregated features. Comparing LINK and LINKX using directed/undirected graphs, on one hand, LINK/LINKX directed perform well in snap-patents and wiki. On the other hand, LINK/LINKX undirected achieve higher accuracy in pokec.

These results validate that an appropriate selection of directed/undirected graphs is necessary to obtain state-of-the-art classification quality. In summary, through our empirical studies with small-, middle-, and large-scale datasets, no single existing method stably obtains state-of-the-art classification results.

### Q2. Effectiveness and Efficiency of A2DUG

**Effectiveness.** In Tables 2 and 3, we observe that A2DUG achieves results within top-2 across all datasets. This shows the performance stability of A2DUG in various datasets. Further, despite its sim

\begin{table}
\begin{tabular}{l|c c|c c c} \hline  & chameleon & squirrel & genius & arxiv-year & ogbn-arxiv \\ \hline MLP & \(37.65_{\pm 3.10}\) & \(35.13_{\pm 3.87}\) & \(85.84_{\pm 0.88}\) & \(36.92_{\pm 0.23}\) & \(53.78_{\pm 0.29}\) \\ GCN & \(37.17_{\pm 3.37}\) & \(32.26_{\pm 2.96}\) & \(82.23_{\pm 3.42}\) & \(43.73_{\pm 0.22}\) & \(69.30_{\pm 0.16}\) \\ SGC & \(38.64_{\pm 3.79}\) & \(38.50_{\pm 1.93}\) & \(80.08_{\pm 2.82}\) & \(38.79_{\pm 0.22}\) & \(67.40_{\pm 0.02}\) \\ GPRGNN & \(38.22_{\pm 5.05}\) & \(35.03_{\pm 1.66}\) & \(89.89_{\pm 0.54}\) & \(40.21_{\pm 0.33}\) & \(67.52_{\pm 0.80}\) \\ FSGNN & \(44.96_{\pm 0.02}\) & \(41.12_{\pm 2.58}\) & \(88.95_{\pm 1.51}\) & \(45.99_{\pm 0.35}\) & \(71.26_{\pm 0.30}\) \\ ACMGCN & \(39.44_{\pm 9.32}\) & \(38.85_{\pm 0.56}\) & \(73.16_{\pm 8.27}\) & \(43.30_{\pm 0.90}\) & \(67.51_{\pm 0.69}\) \\ \hline LINK undirected & \(41.60_{\pm 5.62}\) & \(36.31_{\pm 1.90}\) & \(69.16_{\pm 0.11}\) & \(48.43_{\pm 0.10}\) & \(63.33_{\pm 0.04}\) \\ LINKX undirected & \(41.55_{\pm 2.45}\) & \(40.10_{\pm 2.64}\) & \(89.27_{\pm 1.11}\) & \(47.90_{\pm 0.20}\) & \(61.78_{\pm 0.40}\) \\ GloGNN++ undirected & \(38.49_{\pm 9.02}\) & \(34.48_{\pm 7.13}\) & \(90.00_{\pm 0.38}\) & \(50.55_{\pm 0.12}\) & \(46.30_{\pm 2.74}\) \\ \hline LINK directed & \(38.21_{\pm 2.82}\) & \(33.06_{\pm 2.62}\) & \(55.46_{\pm 0.11}\) & \(51.71_{\pm 0.22}\) & \(57.17_{\pm 0.04}\) \\ LINKX directed & \(39.64_{\pm 5.95}\) & \(36.00_{\pm 1.18}\) & \(88.35_{\pm 0.45}\) & \(52.61_{\pm 0.26}\) & \(59.81_{\pm 0.43}\) \\ GloGNN++ directed & \(40.07_{\pm 3.36}\) & \(34.87_{\pm 8.12}\) & \(87.82_{\pm 0.13}\) & \(53.67_{\pm 0.32}\) & \(55.36_{\pm 20.59}\) \\ \hline DGCN & \(42.42_{\pm 4.60}\) & \(41.04_{\pm 2.07}\) & (TO) & (TO) & (TO) \\ Digraph & \(34.29_{\pm 0.82}\) & \(35.01_{\pm 0.60}\) & (M) & (M) & (M) \\ DigraphIB & \(38.28_{\pm 2.69}\) & \(33.90_{\pm 0.20}\) & (M) & (M) & (M) \\ Magnet & \(35.66_{\pm 3.91}\) & \(31.96_{\pm 1.48}\) & \(86.68_{\pm 2.78}\) & \(52.10_{\pm 0.32}\) & \(68.50_{\pm 0.11}\) \\ \hline
**A2DUG** & \(42.78_{\pm 4.79}\) & \(42.28_{\pm 2.36}\) & \(89.85_{\pm 3.15}\) & \(59.14_{\pm 0.48}\) & \(69.51_{\pm 0.24}\) \\ \hline \end{tabular}
\end{table}
Table 2: Experimental results on small- and middle-scale datasets. Test accuracy is displayed for most datasets, while genius displays test ROC AUC. Standard deviations are over five runs with different random seeds. The two best results per dataset are highlighted. (M) denotes some (or all) hyperparameter settings run out of memory and (TO) denotes that the runs do not finish in 24 hours.

\begin{table}
\begin{tabular}{l|c c c} \hline  & snap-patents & pokec & wiki \\ \hline MLP & \(31.49_{\pm 0.07}\) & \(62.53_{\pm 0.04}\) & \(39.74_{\pm 0.28}\) \\ \hline GCN & \(39.99_{\pm 0.35}\) & \(63.05_{\pm 4.23}\) & (M) \\ SGC & \(35.26_{\pm 0.04}\) & \(69.83_{\pm 0.32}\) & \(45.07_{\pm 0.09}\) \\ GPRGNN & \(32.44_{\pm 0.25}\) & \(65.79_{\pm 8.59}\) & (M) \\ FSGNN & \(45.44_{\pm 0.05}\) & \(78.21_{\pm 1.09}\) & \(58.40_{\pm 0.26}\) \\ ACMGCN & \(40.07_{\pm 0.40}\) & \(69.91_{\pm 0.06}\) & (M) \\ \hline LINK undirected & \(49.93_{\pm 0.07}\) & \(79.17_{\pm 0.05}\) & \(58.42_{\pm 0.04}\) \\ LINKX undirected & \(51.40_{\pm 0.11}\) & \(79.44_{\pm 0.13}\) & \(61.02_{\pm 0.36}\) \\ GloGNN++ undirected & (M) & \(82.66_{\pm 0.07}\) & (M) \\ \hline LINK directed & \(57.54_{\pm 0.07}\) & \(71.53_{\pm 0.09}\) & \(59.69_{\pm 0.03}\) \\ LINKX directed & \(61.09_{\pm 0.07}\) & \(71.88_{\pm 0.09}\) & \(62.08_{\pm 0.14}\) \\ GloGNN++ directed & (M) & \(75.36_{\pm 0.07}\) & (M) \\ \hline Magnet & (M) & \(75.14_{\pm 1.59}\) & (M) \\ \hline
**A2DUG** & \(72.38_{\pm 0.10}\) & \(82.55_{\pm 0.08}\) & \(65.13_{\pm 0.07}\) \\ \hline \end{tabular}
\end{table}
Table 3: Experiments on large-scale datasets. (M) denotes some hyperparameter settings run out of memory. We omit methods that cannot work on large-scale datasets.
ple architecture, A2DUG outperforms other state-of-the-art methods with large margins in arxiv-year (see Table 2), snap-patents, and wiki (see Table 3). These surprising results demonstrate that A2DUG can adaptively control the effects from aggregated features and adjacency lists in directed/undirected graphs rather than simply selecting which feature is important for the classification.
Next, we discuss the importance of aggregated features and adjacency lists. The variant "wo aggregation" obtains better results than "wo adjacency" in pokec and wiki. This means that adjacency lists play more important roles than aggregated features in these datasets. In contrast, the accuracy of "wo adjacency" is better than that of "wo aggregation" in snap-patent. This indicates that the importance of aggregated features and adjacency lists also depends on datasets. These observations validate that the adaptive effect control on aggregated features and adjacency lists is required. We also observe that "wo transpose" obtains lower results than A2DUG in most cases. We validate the effectiveness of using inverse edges in directed graphs.

Through the above observations, we conclude that the importance of aggregated features and adjacency lists in directed/undirected graphs highly depends on datasets and their prediction target. As a result, it is important to adaptively control the effects from aggregated features and adjacency lists in directed/undirected graphs. Thus, A2DUG is robust across various prediction targets and achieves superior results to existing methods on datasets in which the combination of multiple factors is necessary since it can leverage the information from all of them.

## 5 Conclusion

We demonstrated that no existing methods stably obtain state-of-the-art results on various graphs since the importance of combinations depends on datasets. We proposed a simple yet holistic method, A2DUG, that leverages all the combinations of node representations and edge directions. Our empirical studies showed that A2DUG stably achieves state-of-the-art results across various datasets.

**Limitations.** This work shows the potential improvement of GNNs using all the combinations of node representations and edge directions by proposing a simple method combining all of them. In other words, we do not focus on developing the optimal model architecture. For instance, our ablation study in Section 4.3 demonstrated that removing unnecessary features for classification can contribute to performance improvement. Hence, it is an interesting direction to combine our method and feature selection techniques such as [22]. Also, it is an open question of how we can construct appropriate model architecture for further improvement of node classification quality. Indeed, concurrent works [27; 28] have addressed developing sophisticated but complicated model architectures and thus achieved state-of-the-art classification quality. It is our future work to incorporate these methods into our approach while ensuring scalability.

## Acknowledgments and Disclosure of Funding

This work was supported by JSPS KAKENHI Grant Numbers JP20H00583 and JST PRESTO Grant Number JPMJPR21C5.
