AutoAC: Towards Automated Attribute Completion for Heterogeneous Graph
  Neural Network
Many real-world data can be modeled as heterogeneous graphs that contain
multiple types of nodes and edges. Meanwhile, due to excellent performance,
heterogeneous graph neural networks (GNNs) have received more and more
attention. However, the existing work mainly focuses on the design of novel GNN
models, while ignoring another important issue that also has a large impact on
the model performance, namely the missing attributes of some node types. The
handcrafted attribute completion requires huge expert experience and domain
knowledge. Also, considering the differences in semantic characteristics
between nodes, the attribute completion should be fine-grained, i.e., the
attribute completion operation should be node-specific. Moreover, to improve
the performance of the downstream graph learning task, attribute completion and
the training of the heterogeneous GNN should be jointly optimized rather than
viewed as two separate processes. To address the above challenges, we propose a
differentiable attribute completion framework called AutoAC for automated
completion operation search in heterogeneous GNNs. We first propose an
expressive completion operation search space, including topology-dependent and
topology-independent completion operations. Then, we propose a continuous
relaxation schema and further propose a differentiable completion algorithm
where the completion operation search is formulated as a bi-level joint
optimization problem. To improve the search efficiency, we leverage two
optimization techniques: discrete constraints and auxiliary unsupervised graph
node clustering. Extensive experimental results on real-world datasets reveal
that AutoAC outperforms the SOTA handcrafted heterogeneous GNNs and the
existing attribute completion method
Guanghui Zhu, Zhennan Zhu, Wenjie Wang, Zhuoer Xu, Chunfeng Yuan, Yihua Huang
AutoAC: Towards Automated Attribute Completion for Heterogeneous Graph Neural Network (Extended Version)

###### Abstract

Many real-world data can be modeled as heterogeneous graphs that contain multiple types of nodes and edges. Meanwhile, due to excellent performance, heterogeneous graph neural networks (GNNs) have received more and more attention. However, the existing work mainly focuses on the design of novel GNN models, while ignoring another important issue that also has a large impact on the model performance, namely the missing attributes of some node types. The handcrafted attribute completion requires huge expert experience and domain knowledge. Also, considering the differences in semantic characteristics between nodes, the attribute completion should be fine-grained, i.e., the attribute completion operation should be node-specific. Moreover, to improve the performance of the downstream graph learning task, attribute completion and the training of the heterogeneous GNN should be jointly optimized rather than viewed as two separate processes. To address the above challenges, we propose a differentiable attribute completion framework called AutoAC for automated completion operation search in heterogeneous GNNs. We first propose an expressive completion operation search space, including topology-dependent and topology-independent completion operations. Then, we propose a continuous relaxation schema and further propose a differentiable completion algorithm where the completion operation search is formulated as a bi-level joint optimization problem. To improve the search efficiency, we leverage two optimization techniques: discrete constraints and auxiliary unsupervised graph node clustering. Extensive experimental results on real-world datasets reveal that AutoAC outperforms the SOTA handcrafted heterogeneous GNNs and the existing attribute completion method.

 heterogeneous graph, graph neural network, attribute completion, differentiable search

## I Introduction

Graph-structured data are ubiquitous, such as social networks [1], scholar networks [2], biochemical networks [3], and knowledge graphs [4]. Meanwhile, many real-world graph data are heterogeneous [5]. Unlike the homogeneous graph with only one node type and one edge type, the heterogeneous graph [6] consists of multiple types of nodes and edges associated with attributes in different feature spaces. For example, the IMDB dataset is a typical heterogeneous graph, which contains three node types (movie, actor, director) and two edge types (movie-actor, movie-director), as shown in Figure 1(a). Due to containing rich information and semantics, heterogeneous graphs have drawn more and more attention.

Recently, graph neural networks (GNNs) [7, 8] have demonstrated powerful representation learning ability on graph-structured data [9]. Meanwhile, many heterogeneous GNNs (HGNNs) have been proposed for heterogeneous graphs [10][11][12][13][14][15][16][17]. However, the existing work on heterogeneous graphs mainly focuses on the construction of novel GNN models, while ignoring another important issue that also has a large impact on the model performance, namely the attributes of some types of nodes are missing [18]. Missing node attributes is a common problem because collecting the attributes of all nodes is prohibitively expensive or even impossible due to privacy concerns. Since the attributes of all nodes are required in the GNN-based heterogeneous models, some handcrafted ways are employed to deal with the problem of missing attributes. For example, the missing attribute vector can be the sum or the mean of directly connected nodes' attribute vectors. Besides, the one-hot representations of a certain node type can also be used to replace the missing attributes. However, the handcrafted ways require huge expert experience and domain knowledge. Also, the topological relationships in the graph are not taken into account. Recently, an attention-based method [18] was proposed to complete each no-attribute node by weighted aggregation of the attributes from the directly neighboring attributed nodes. Such an attribute completion method only considers the attributes of 1-hop neighbors without exploiting the attributes of higher-order neighbors.

Moreover, existing attribute completion methods are all coarse-grained. That is, for a specific node type without attributes, they adopt the same attribute completion operation for all nodes without considering the differences in semantic characteristics between nodes. In practice, fine-grained attribute completion is more reasonable. The attribute completion operations for the nodes with different semantics should be different. Take the IMDB dataset as an example. The target type of nodes (i.e., movie nodes) has attributes, and the other types of nodes (i.e., actor nodes and director nodes) have no attributes. As shown in Figure 1(b), there exist three attribute completion operations, including 1) For actors (e.g. Jackie Chan) who are involved in movies that mostly belong to the same genre (Kung Fu movies), average attribute aggregation of local (i.e., 1-hop) neighboring nodes should be used. 2)
For actors who have strong collaborative relationships with other actors and directors, the message-passing based multi-hop attribute aggregation is more suitable. 3) For guest actors without representative movies, we can directly use the simple one-hot encoding to complete attributes.

For the IMDB dataset, the number of actor nodes that have no attributes is 6124. Manually differentiating the semantic characteristics of all no-attribute nodes and then selecting the most suitable completion operations according to semantic characteristics is infeasible. Thus, an automated attribute completion method that can search the optimal completion operations efficiently is required. Moreover, to improve the performance of the downstream graph learning task, the automated attribute completion and the training of the heterogeneous GNN should be jointly optimized rather than viewed as two separate processes.

To address the above challenges, we propose a differentiable attribute completion framework called AutoAC1 for automated completion operation search in heterogeneous GNNs. AutoAC is a generic framework since it can integrate different heterogeneous GNNs flexibly. By revisiting the existing attribute completion methods, we first propose an expressive completion operation search space, including topology-dependent and topology-independent completion operations. Instead of searching over the discrete space (i.e., candidate completion operations for each no-attribute node), we propose a continuous relaxation scheme by placing a weighted mixture of candidate completion choices, which turns the search task into an optimization problem regarding the weights of choices (i.e., completion parameters). Thus, due to the continuous search space, the search process becomes differentiable and we can perform completion operation search via gradient descent.

Footnote 1: AutoAC is available at [https://github.com/Pasal_ab/AutoAC](https://github.com/Pasal_ab/AutoAC)

To further improve the search efficiency, we formulate the search of attribute completion operations and the training of GNN as a constrained bi-level joint optimization problem. Specifically, we keep the search space continuous in the optimization process of completion parameters (i.e., upper-level optimization) but enforce attribute completion choices being discrete in the optimization process of weights in the heterogeneous GNN (i.e., lower-level optimization). In this way, there is only one activated completion operation for each no-attribute node during the training of GNN, removing the need to perform all candidate completion operations. Inspired by NASP [19], we employ proximal iteration to solve the constrained optimization problem efficiently.

Finally, to reduce the dimension of the attribute completion parameters, we further leverage an auxiliary unsupervised graph node clustering task with the spectral modularity function during the process of GNN training.

To summarize, the main contributions of this paper can be highlighted as follows:

* We are the first, to the best of our knowledge, to model the attribute completion problem as an automated search problem for the optimal completion operation of each no-attribute node.
* We propose an expressive completion operation search space and further propose a differentiable attribute completion framework where the completion operation search is formulated as a bi-level joint optimization problem.
* To improve search efficiency, we enforce discrete constraints on completion parameters in the training of heterogeneous GNN. Moreover, we leverage an auxiliary unsupervised graph node clustering task to reduce the dimension of the attribute completion parameters.
* Extensive experimental results on real-world datasets reveal that AutoAC is effective to boost the performance of heterogeneous GNNs and outperforms the SOTA attribute completion method in terms of performance and efficiency.

## II Related Work

### _Heterogeneous Graph Neural Network_

Graph neural network [8][20][1][21][22][9] aims to extend neural networks to graphs. Since heterogeneous graphs are more common in the real world [5], heterogeneous GNNs have been proposed recently. Part of the work is based on meta-paths. HAN [10] leverages the semantics of meta-paths and uses hierarchical attention to aggregate neighbors. MAGNN [14] utilizes RotatE [23] to encode intermediate nodes along each meta-path and mix multiple meta-paths using hierarchical attention. Another part of the work chooses to extract rich semantic information in heterogeneous graphs. GTN [11] learns a soft selection of edge types and composite relations for generating useful multi-hop connections. HetGNN [13] uses Bi-LSTM to aggregate node features for

Fig. 1: (a) Example of heterogeneous graphs with incomplete attributes, i.e., the IMDB dataset. (b) Different attribute completion operations for the actor node, i.e., local attribute aggregation, message-passing based multi-hop attribute aggregation, and one-hot representation.
each type and among types. As the state-of-the-art model, SimpleHGN [17] revisits existing methods and proposes a simple framework using learnable edge-type embedding and residual connections for both nodes and edges. Recently, AS-GCN [24] employs the heterogeneous GNN to mine the semantics for text-rich networks.

Different from the above methods, HGNN-AC [18] notices that most of the nodes in the real heterogeneous graph have missing attributes, which could cause great harm to the performance of heterogeneous models, and proposes an attention-based attribute completion method. However, HGNN-AC needs to get node embeddings based on network topology using metapath2vec [25], which is a time-consuming process. Moreover, the attribute completion in HGNN-AC is coarse-grained and supports only one completion operation for all no-attribute nodes. HGCA [26] unifies attribute completion and representation learning in an unsupervised heterogeneous network. MRAP [27] performs node attribute competition in knowledge graphs with multi-relational propagation.

### _Neural Architecture Search (NAS)_

NAS [28] that designs effective neural architectures automatically has received more attention. The core components of NAS contain search space, search algorithm, and performance estimation strategy. Recently, many works use NAS to design GNN models due to the complexity of GNN [29]. PolicyGNN [30] uses reinforcement learning to train meta-strategies and then adaptively determines the choice of aggregation layers for each node. SANE [31] and SNAG [31] search for aggregation functions using microscope-based and reinforcement learning-based strategies, respectively. The architecture-level approaches such as GraphNAS [32], AutoGNN [33], and PSP [34] aim to search for architectural representations of each layer, including sampling functions, attention computation functions, aggregation functions, and activation functions. The above works are based on homogeneous graphs. Due to the rich semantic and structural information in heterogeneous graphs, applying NAS to heterogeneous graphs is more challenging. Recently, there exist some excellent attempts. GEMS [35] uses the evolutionary algorithm to search for meta-graphs between source and target nodes. DiffMG [36] uses differentiable methods to find the best meta-structures in heterogeneous graphs. However, the above works only focus on the GNN model and ignore the heterogeneous graph data itself, which is even more important in practice.

### _Proximal Iteration_

Proximal iteration [37] is used to handle the optimization problem with a constraint \(\mathcal{C}\), i.e., \(\min_{x}f(x)\), s.t. \(x\in\mathcal{C}\), where \(f\) is a differentiable objective function. The proximal step is:

\[\begin{split}& x^{(k+1)}=\text{prox}_{\mathcal{C}}\left(x^{(k)}- \epsilon\nabla f\left(x^{(k)}\right)\right)\\ &\text{prox}_{\mathcal{C}}(x)=\operatorname*{arg\,min}_{z}\frac{1 }{2}(\left\|z-x\right\|)^{2},\text{s.t.}\ z\in\mathcal{C}\end{split} \tag{1}\]

where \(\epsilon\) is the learning rate. Due to the excellent theoretical guarantee and good empirical performance, proximal iteration has been applied to many deep learning problems (e.g., architecture search [19]).

## III Preliminaries

_Heterogeneous Graph._ Given a graph \(G=\langle V,E\rangle\) where \(V\) and \(E\) denote the node set and the edge set respectively, \(G\) is heterogeneous when the number of node and edge types exceeds 2. Each node \(v\in V\) and each edge \(e\in E\) are associated with a node type and an edge type respectively.

_Attribute Missing in Heterogeneous Graph._ Let \(x_{v}\in\mathbb{R}^{d}\) denote the original \(d\)-dimensional attribute vector in the node \(v\). In practice, the attributes of some types of nodes are not available. Thus, the node set \(V\) in \(G\) can be divided into two subsets, i.e., \(V^{+}\) and \(V^{-}\), which denote the attributed node-set and no-attribute node-set.

_Attribute Completion._ Let \(X=\{x_{v}\mid v\in V^{+}\}\) denote the input attribute set. Attribute completion aims to complete the attribute for each no-attribute node \(v\in V^{-}\) by leveraging the available attribute information \(X\) and the topological structure of \(G\). Let \(x_{v}^{C}\) denote the completed attribute. Thus, after completion, the node attributes for the training of heterogeneous GNN is \(X^{new}=X\cup X^{C}=\{x_{v}\mid v\in V^{+}\}\cup\{x_{v}^{c}\mid v\in V^{-}\}\). In this paper, we aim to search for the optimal completion operation for each no-attribute node to improve the prediction performance of GNN models.

## IV The Proposed Methodology

In this section, We first present the proposed completion operation search space and then introduce the differentiable search strategy. Moreover, we introduce the optimization techniques including discrete constraints and the auxiliary unsupervised graph node clustering task for further improving the search efficiency.

### _Search Space of Attribute Completion Operation_

Due to the semantic differences between nodes, using a single attribute completion operation for all no-attribute nodes belonging to the same node type is not reasonable. The available completion operations should be diverse and we can select the most suitable completion operation for each node with missing attributes. Thus, to capture both the node semantics and the topological structure information during the attribute completion process, we first propose an expressive completion operation search space, which consists of topology-dependent and topology-independent operations.

Specifically, the topology-dependent operations employ the topology information of the graph to guide the attribute completion. Inspired by the node aggregation operations in typical GNNs (e.g., GraphSage [1], GCN [8], APPNP [38]), we design three topology-dependent attribute completion operations, i.e., mean, GCN-based, PPNP-based operations. In contrast, the topology-independent operation directly uses one-hot encoding to replace the missing attribute. AutoAC aims to search the optimal operation for each no-attribute node from the general and scalable search space where we can draw
on more node aggregation operations in GNNs as attribute completion operations.

#### Iii-A1 Topology-Dependent Completion Operation

Such type of completion operations can be further divided into two categories: local attribute aggregation and global (i.e., multi-hop) attribute aggregation.

_Local Attribute Aggregation._ Similar to the node aggregation in GraphSage [1], we first propose mean attribute aggregation.

_Mean Attribute Aggregation._ For the node \(v\in V^{-}\), we calculate the mean of neighbors' attributes to complete the missing attribute. The completed attribute \(x_{v}^{C}\) is as follows:

\[x_{v}^{C}=W\cdot\mathrm{mean}\left\{x_{u},\forall u\in N_{v}^{+}\right\} \tag{2}\]

where \(N_{v}^{+}\) denotes the local (i.e, 1-hop) neighbors of node \(v\) in set \(V^{+}\). \(W\) is the trainable transformation matrix.

_GCN-based Attribute Aggregation._ Similar to spectral graph convolutions in GCN [8], we complete the missing attribute with the following renormalized graph convolution form.

\[x_{v}^{C}=\sum_{u\in N_{v}^{+}}(\mathrm{deg}(v)\cdot\mathrm{deg}(u))^{-1/2} \cdot x_{u}\cdot W \tag{3}\]

_Global Attribute Aggregation._ Motivated by the node aggregation in APPNP [38], we propose PPNP-based completion operation for global attribute aggregation.

_PPNP-based Attribute Aggregation._ Besides the GCN-based attribute completion, we use another popular node aggregation method PPNP (i.e., Personalized PageRank [38]) for attribute completion. Specifically, let \(A\in\mathbb{R}^{n\times n}\) denote the adjacency matrix of the graph \(G\). \(\tilde{A}=A+I_{n}\) denotes the adjacency matrix with added self-loops. The form of PPNP-based attribute completion is:

\[\begin{split}& X^{ppnp}=\alpha\left(I_{n}-(1-\alpha\hat{\tilde{A}}) \right)^{-1}\cdot X^{\prime},X^{\prime}=X\cdot W\\ & X_{C}=\{X_{i}^{ppnp}\ |\ \forall i\in V^{-}\}\end{split} \tag{4}\]

where \(\hat{\tilde{A}}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) is the symmetrically normalized adjacency matrix with self-loops, with the diagonal degree matrix \(\tilde{D}\). \(\alpha\in(0,1]\) is the restart probability. Note that the missing attributes are filled with zeros in \(X\). After PPNP-based attribute aggregation, we complete the attributes of the nodes in \(V^{-}\) with \(X^{ppnp}\).

#### Iii-A2 Topology-Independent Completion Operation

For the no-attribute nodes that have few neighbors or are less affected by the neighbor information, we can directly use one-hot encoding to replace the missing attributes. The one-hot representation of a specific node type is also a commonly used handcrafted attribute completion method [17]. For example, there are \(K\) distinct actors in IMDB. The one-hot representation for the actor node is a \(K\)-dimensional vector. For a specific actor, the element in the corresponding index is 1 and the others are 0. Then, the one-hot representation is transformed linearly for dimension alignment.

#### Iii-A3 Search Space Size Analysis

In summary, the proposed search space \(\mathcal{O}\) contains a diverse set of attribute completion operations. Let \(N^{-}\) denote the total number of nodes with missing attributes. Thus, the space size can be calculated by \(\left|\mathcal{O}\right|^{N^{-}}\), which is exponential to \(N^{-}\). In practice, the attribute missing of some node types is a common problem, leading to huge search space. Thus, the block-box optimization-based search method (e.g., evolutionary algorithm) over a discrete search space is infeasible. To address this issue, we propose a differentiable search strategy to find the optimal completion operations efficiently.

### _Differentiable Search Strategy_

In this section, we first introduce a continuous relaxation scheme for the completion operation search space to make the search process to be differentiable. Then, we introduce the differentiable search algorithm and two optimization techniques to improve the search efficiency.

#### Iii-B1 Continuous Relaxation and Optimization

Inspired by the success of the differentiable NAS, we first design a continuous search space and then perform differentiable completion operation search via gradient descent.

As shown in Equation 5, instead of searching over the discrete space, we view the completion operation as a weighted mixture of candidate choices.

\[x_{v}^{C}=\sum_{o\in\mathcal{O}}\frac{\exp\left(\alpha_{o}^{(v)}\right)}{\sum_ {o^{\prime}\in\mathcal{O}}\exp\left(\alpha_{o^{\prime}}^{(v)}\right)}o\left(v\right) \tag{5}\]

where \(v\) denotes the node with the missing attribute, \(o\) denotes the candidate operation in the search space \(\mathcal{O}\), \(o\left(v\right)\) denotes the completed attribute of node \(v\) with \(o\). \(\alpha^{(v)}\) indicates the mixing weight vector of dimension \(\left|\mathcal{O}\right|\) for node \(v\). Furthermore, we refer to \(\alpha=\{\alpha^{(v)}\ |\ v\in V^{-}\}\in\mathbb{R}^{N^{-}\times\left|\mathcal{O}\right|}\) as the completion parameters.

After continuous relaxation, the search objective becomes the learning of the completion parameters \(\alpha\). To this end, we formulate the search problem as an optimization problem that can jointly learn the completion parameters \(\alpha\) and the weights \(w\) in the heterogeneous GNN by gradient descent. Let \(\mathcal{L}_{train}\) and \(\mathcal{L}_{val}\) denote the training loss and validation loss respectively. Since both losses are determined by the completion parameters \(\alpha\) and the weights \(w\), the search objective is a bi-level optimization problem.

\[\begin{split}&\min_{\alpha}\mathcal{L}_{val}\left(\omega^{*}, \alpha\right)\\ &\text{s.t.}\ \omega^{*}=\operatorname*{argmin}_{w}\mathcal{L}_{train}( \omega,\alpha)\end{split} \tag{6}\]

where the upper-level optimization is for the optimal completion parameters \(\alpha\) and the lower-level optimization is for the optimal weights \(w\) in the GNN model.

#### Iii-B2 Overview

Figure 2 shows the overall framework of automated attribute completion for heterogeneous graphs. First, we perform a continuous relaxation of the search space by placing a mixture of candidate completion operations. Then,
the completion parameters \(\alpha\) are optimized. After determining the attribute completion operations for each no-attribute node, we view the completed attributes together with the raw attributes as the initial embedding for the training of the graph neural network.

_Why not use the weighted mixture._ Although the continuous relaxation allows the search of completion operations to be differentiable, there still exist following limitations when directly using the weighted mixture of all completion operations:

1. _High computational overhead:_ After continuous relaxation, we need to perform all candidate completion operations for each no-attribute node when training heterogeneous GNNs, leading to huge computational overhead. Also, solving the bi-level optimization problem in Equation 6 incurs significant computational overhead.
2. _Performance gap:_ At the end of the search, continuous parameters \(\alpha\) needs to be discretized, i.e., \(\operatorname*{argmax}_{\alpha\in\mathcal{O}}\alpha_{\alpha}^{(v)}\), resulting in inconsistent performance between searched and final completion operations.
3. _Large dimension of \(\alpha\):_ The dimension of completion parameters \(\alpha\) is \(N^{-}\times|\mathcal{O}|\), which is proportional to the total number of nodes with missing attributes. The large dimension of \(\alpha\) leads to a slow convergence rate and low search efficiency.

To address the first two issues (i.e., reducing computational overhead and avoiding performance gap), we first propose an efficient search algorithm with discrete constraints. Specifically, for each no-attribute node \(v\), the completion parameters satisfy the following constraints: \(\alpha^{(v)}\in\mathcal{C}=\mathcal{C}_{1}\cap\mathcal{C}_{2}\), where \(\mathcal{C}_{1}=\{\alpha^{(v)}\mid\|\alpha^{(v)}\|_{0}=1\}\), \(\mathcal{C}_{2}=\{\alpha^{(v)}\mid 0\leq\alpha_{i}^{(v)}\leq 1\}\). The constraint \(\mathcal{C}_{2}\) allows \(\alpha\) to be optimized continuously, and \(\mathcal{C}_{1}\) keeps the choices of completion operation to be discrete when training GNN. As shown in Figure 2, there is only one activated edge for each choice when training GNN, removing the need to perform all candidate completion operations. The final completion operation is derived from the learned completion parameter \(\alpha\). For node \(v\), the edge with the maximum completion parameter will be kept. We leverage proximal iteration [37] to solve the constrained optimization problem. Moreover, proximal iteration can improve the computational efficiency of optimizing \(\alpha\) without second-order derivative.

Moreover, to address the third issue (i.e., reducing the dimension of \(\alpha\)), we propose an auxiliary unsupervised clustering task. In practice, the no-attribute nodes with similar semantic characteristics may have the same completion operation. Take the actor nodes in the IMDB dataset as an example. For the actors with a large number of representative movies, the average attribute aggregation operation is more suitable. Thus, we can cluster all no-attribute nodes into \(M\) clusters, where the nodes in each cluster have the same completion operation. The optimization goal becomes to search for the optimal attribute completion operation for each cluster. In this way, the size of the completion parameters \(\alpha\) is reduced from \(N^{-}\times|\mathcal{O}|\) to \(M\times|\mathcal{O}|\), \(M\ll N^{-}\). As shown in Figure 2, the auxiliary unsupervised clustering loss can be jointly optimized with the node classification loss (i.e., cross-entropy).

The proposed framework AutoAC is composed of multiple iterations. In each iteration, the completion parameters \(\alpha\) and the weights in the GNN are optimized alternatively. Next, we introduce the search algorithm with discrete constraints and the auxiliary unsupervised clustering task in detail.

### _Search Algorithm with Discrete Constraints_

Equation 6 implies a bi-level optimization problem with \(\alpha\) as the upper-level variable and \(w\) as the lower-level variable.

Fig. 2: The overall workflow of automated attribute completion for the heterogeneous graph neural network.
Following the commonly used methods in meta learning [39] and NAS [40], we use a one-step gradient approximation to the optimal internal weight parameters \(\omega^{*}\) to improve the efficiency. Thus, the gradient of the completion parameters \(\alpha\) is as follows (we omit the step index \(k\) for brevity):

\[\begin{split}&\nabla_{\alpha}\mathcal{L}_{val}\left(\omega^{*}, \alpha\right)\\ \approx&\nabla_{\alpha}\mathcal{L}_{val}\left(\omega- \xi\nabla_{\omega}\mathcal{L}_{train}(\omega,\alpha),\alpha\right)\\ =&\nabla_{\alpha}\mathcal{L}_{val}\left(\omega^{ \prime},\alpha\right)-\xi\nabla_{\alpha,\omega}^{2}\mathcal{L}_{train}( \omega,\alpha)\nabla_{\omega^{\prime}}\mathcal{L}_{val}\left(\omega^{\prime}, \alpha\right)\end{split} \tag{7}\]

where \(\omega\) is the weights of the GNN, \(\xi\) is the learning rate of internal optimization, and \(\omega^{\prime}=\omega-\xi\nabla_{\omega}\mathcal{L}_{train}(\omega,\alpha)\) indicates the weights for a one-step forward model. We update the completion parameters \(\alpha\) to minimize the validation loss. In Equation 7, there exists a second-order derivative, which is expensive to compute due to a large number of parameters. Also, the continuous relaxation trick further leads to huge computational overhead since all candidate completion operations need to be performed when training the GNN. Moreover, the overall search process is divided into two stages: search and evaluation. In the evaluation stage, the continuous completion parameters \(\alpha\) need to be discretized for replacing every mixed choice as the most likely operation by taking the argmax, leading to performance gap between the search and evaluation stage.

To optimize \(\alpha\) efficiently and avoid the performance gap, we propose a search algorithm with discrete constraints when optimizing completion parameters \(\alpha\). For the no-attribute node \(v\), let the feasible space of \(\alpha^{(v)}\) be \(\mathcal{C}=\{\alpha^{(v)}\mid\|\alpha^{(v)}\|_{0}=1\wedge 0\leq\alpha_{i}^{(v)}\leq 1\}\). We denote it as the intersection of two feasible spaces (i.e., \(\mathcal{C}=\mathcal{C}_{1}\cap\mathcal{C}_{2}\)), where \(\mathcal{C}_{1}=\{\alpha^{(v)}\mid\|\alpha^{(v)}\|_{0}=1\}\), \(\mathcal{C}_{2}=\{\alpha^{(v)}\mid 0\leq\alpha_{i}^{(v)}\leq 1\}\). The optimization problem under constraints can be solved by the proximal iterative algorithm.

**Proposition 1**: _\(\text{prox}_{\mathcal{C}}(z)=\text{prox}_{\mathcal{C}_{2}}(\text{prox}_{ \mathcal{C}_{1}}(z))\)_

Inspired by Proposition 1[19, 37], in the \(k\)-th proximal iteration, we first get discrete variables constrained by \(\mathcal{C}_{1}\), i.e., \(\bar{\alpha}^{(k)}=\text{prox}_{\mathcal{C}_{1}}(\alpha^{(k)})\) (the node notation \(v\) is omitted for brevity). Then, we derive gradients w.r.t \(\bar{\alpha}^{(k)}\) and keep \(\alpha\) to be optimized as continuous variables but constrained by \(\mathcal{C}_{2}\).

\[\alpha^{(k+1)}=\text{prox}_{\mathcal{C}_{2}}(\alpha^{(k)}-\epsilon\nabla_{ \bar{\alpha}^{(k)}}\mathcal{L}_{val}(\bar{\alpha}^{(k)})) \tag{8}\]

The detailed search algorithm is described in Algorithm 1. First, we get a discrete representation of \(\alpha\) by proximal step (Line 3). Then, we view \(\omega^{(k)}\) as constants and optimize \(\alpha^{(k+1)}\) for continuous variables (Line 4). Since there is no need to compute the second-order derivative, the efficiency of updating \(\alpha\) can be improved significantly. After updating \(\alpha\), we further refine discrete choices and get \(\bar{\alpha}^{(k+1)}\) for updating \(\omega^{(k)}\) on the training dataset, which contributes to reducing the performance gap caused by discretizing completion parameters \(\alpha\) from continuous variables. Moreover, since only one candidate choice is activated for each no-attribute node, the computational overhead can also be reduced. The computational efficiency of updating \(\alpha\) can be significantly improved.

```
1: Initialize completion parameters \(\alpha\) according to defined search space \(\mathcal{O}\);
2:while not convergedo
3: Get discrete choices of attribute completion operations: \(\bar{\alpha}^{(k)}=\text{prox}_{\mathcal{C}_{1}}(\alpha^{(k)})\)
4: Update \(\alpha\) for continuous variables: \(\alpha^{(k+1)}=\text{prox}_{\mathcal{C}_{2}}(\alpha^{(k)}-\epsilon\nabla_{ \bar{\alpha}^{(k)}}\mathcal{L}_{val}(\omega^{(k)},\bar{\alpha}^{(k)}))\)
5: Refine discrete choices after updating: \(\bar{\alpha}^{(k+1)}=\text{prox}_{\mathcal{C}_{1}}(\alpha^{(k+1)})\)
6: Update \(\omega^{(k)}\) by \(\nabla_{\omega^{(k)}}\mathcal{L}_{train}\big{(}\omega^{(k)},\bar{\alpha}^{(k+ 1)})\)
7:endwhile
```

**Algorithm 1** Search Algorithm in AutoAC

### _Auxiliary Unsupervised Clustering Task_

As mentioned before, the dimension of the completion parameters \(\alpha\) is \(N^{-}\times|\mathcal{O}|\left(|\mathcal{O}|\ll N^{-},|\mathcal{O}|=4\right)\). Take the DBLP dataset as an example, the number of nodes with missing attributes is about \(1.2\times 10^{4}\), leading to a large dimension of completion parameters \(\alpha\). As a result, optimizing \(\alpha\) with a limited size of validation dataset is very difficult.

Inspired by the observation that the no-attribute nodes with similar explicit topological structure or implicit semantic characteristics, we further propose an auxiliary unsupervised clustering task to divide all no-attribute nodes into \(M\) clusters. In each cluster, all nodes share the same completion operation. In this way, the dimension of the completion parameters \(\alpha\) can be reduced to \(M\times|\mathcal{O}|\), \(M\ll N^{-}\), and optimizing \(\alpha\) becomes feasible and efficient.

It is well known that the EM algorithm [41] is a commonly used method (e.g., K-Means [42]) to solve the problem of unsupervised clustering. In the scenario of graph node clustering, let \(h_{v}\) denote the hidden node representation learned by the heterogeneous GNN. The E-step is responsible for assigning the optimal cluster for each node \(v\) by calculating the distances between \(h_{v}\) and all cluster centers. The M-step is used to update the centers of all clusters. The E-step and M-step are performed alternately until convergence.

Although the EM algorithm has a convergence guarantee, it is sensitive to the initial values, making it difficult to apply to the proposed automated completion framework. The main reason is that the bi-level optimization problem defined in Equation 6 is iterative. In the early optimization process, the weights of the GNN have not yet converged and the node representations learned in the GNN are less informative. Such low-quality representations lead to inaccurate clustering, which has a negative impact on the subsequent clustering quality and further leads to a deviation from the overall optimization direction.

To address this issue, we first formulate the problem of unsupervised node clustering as a form of soft classification, and use the assignment matrix \(\mathbf{C}\) to record the probability of each node belonging to each cluster. Moreover, as shown in Figure 2, we embed the clustering process into the bi-level iterative optimization process.
Motivated by graph pooling and graph module partitioning, we introduce the Spectral Modularity Function \(\mathcal{Q}\)[43][44]. From a statistical perspective, this function can reflect the clustering quality of graph node modules through the assignment matrix \(\boldsymbol{C}\)[45]:

\[\mathcal{Q}=\frac{1}{2\left|E\right|}\sum_{ij}\left[\boldsymbol{A}_{ij}-\frac{ d_{i}d_{j}}{2\left|E\right|}\right]\delta\left(c_{i},c_{j}\right) \tag{9}\]

where \(\left|E\right|\) is the number of edges in the graph, \(\delta(c_{i},c_{j})=1\) only if nodes \(i\) and \(j\) are in the same cluster, otherwise 0. \(d_{i}\) and \(d_{j}\) represent the degrees of node \(i\) and node \(j\) respectively. It can be known that in a random graph, the probability that node \(i\) and node \(j\) are connected is \(\frac{d_{i}d_{j}}{2\left|E\right|}\)[45].

Then, the optimization goal is converted into maximizing the spectral modularity function \(\mathcal{Q}\), but it is an NP-hard problem. Fortunately, this function can be represented by an approximate spectral domain relaxation form:

\[\mathcal{Q}=\frac{1}{2\left|E\right|}\operatorname{Tr}\left(\boldsymbol{C}^{ \top}\boldsymbol{B}\boldsymbol{C}\right) \tag{10}\]

where \(\mathcal{C}_{ij}\in[0,1]\) denotes the cluster probability. \(\boldsymbol{B}\) is the modular matrix \(\boldsymbol{B}=\boldsymbol{A}-\frac{\boldsymbol{\boldsymbol{\boldsymbol{ \boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{ \boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{\boldsymbol{ \boldsymbol{\boldsymbol{ \boldsymbol{ \boldsymbol{       }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\)\)\)\)\ \ \ \ \ \\\\\ \
statistics of the four datasets are summarized in Table I. More details of datasets can be seen in Appendix A.

Moreover, the handcrafted attribute completion methods for existing heterogeneous GNNs are provided by HGB. Micro-F1 and Macro-F1 are provided to evaluate the node classification performance, while the MRR and ROC-AUC metrics are used for link prediction. The evaluation metrics are obtained by submitting predictions to the HGB website2.

Footnote 2: [https://www.bientdata.xyz/competition/hgb-1/](https://www.bientdata.xyz/competition/hgb-1/)

### _Implementation Details_

All experiments are performed in the transductive setting. We employ the Adam optimizer [46] to optimize both \(\omega\) and \(\alpha\). For optimizing \(\omega\), the learning rate and the weight decay are 5e-4 and 1e-4 respectively. For optimizing \(\alpha\), the learning rate and the weight decay are 5e-3 and 1e-5 respectively.

We implement AutoAC based on the widely-used heterogeneous GNNs, i.e., MAGNN [14] and SimpleHGN [17]. The loss weighted coefficient \(\lambda\) and the number of clusters \(M\) are two hyperparameters of AutoAC. For MAGNN, we empirically set \(\lambda\) to 0.5 for all datasets, \(M\) to 4 for the DBLP and ACM datasets, 16 for the IMDB dataset. For SimpleHGN, \(\lambda\) is 0.4 for all datasets, and \(M\) is 8 for the DBLP dataset, 12 for the ACM and IMDB datasets. Moreover, all the GNN models are implemented with PyTorch. All experiments are run on a single GPU (NVIDIA Tesla V100) five times and the average performance and standard deviation are reported.

### _Effectiveness of AutoAC_

#### Iv-C1 Performance comparison with humancrafted heterogeneous GNNs

Depending on whether or not the meta-path is used, we divide the humancrafted heterogeneous GNNs into two categories:

* GNNs with meta-path: HAN [13], GTN [11], Het-SANN [16], MAGNN [14], HGCA [26].
* GNNs without meta-path: HGT [15], GATNE [47], Het-GNN [13], GCN [8] and GAT [20] (two commonly used general-purpose GNNs), as well as the current SOTA GNN model SimpleHGN [17].

The configurations of baselines can be seen in Appendix B. As a generic framework, AutoAC can integrate different GNNs. We select two representative GNN models from the two categories (i.e., MAGNN and SimpleHGN) from the perspective of performance and computational efficiency. Then, we combine AutoAC with the two models, denoted by MAGNN-AutoAC and SimpleHGN-AutoAC respectively.

Table II shows the performance comparison between AutoAC and existing heterogeneous GNNs on node classification. AutoAC can improve the performance of MAGNN and SimpleHGN stably on all datasets. The performance gain obtained by AutoAC over MAGNN is around 0.7%-3% and the error rate is reduced by 2.87%-11.69%. Also, SimpleHGN-AutoAC outperforms SimpleHGN by 1%-3% and reduces the error rate by 1.59%-22.09%. By combining with the SOTA model SimpleHGN, SimpleHGN-AutoAC can achieve the best performance in all models.

Moreover, Table II shows that AutoAC can bring significant performance improvement on the datasets where the classification target nodes have no raw attributes (e.g., DBLP). Besides, for the datasets where the target nodes already have raw attributes (e.g., ACM and IMDB), completing other non-target nodes using AutoAC can still promote the classification accuracy of target nodes. Especially, for the IMDB dataset, since there are too many non-target nodes with missing attributes (i.e., 77% of all nodes), the performance improvement with AutoAC is more significant.

Note that the performance of MAGNN without attribute completion is not as good as other models, such as GTN and GAT. However, MAGNN-AutoAC performs better than GTN on DBLP and ACM, and outperforms GAT on DBLP and IMDB, which indicates that effective attribute completion for heterogeneous graphs can compensate for the performance gap introduced by the GNN model. By unifying attribute completion and representation learning in an unsupervised heterogeneous network, the recently proposed HGCA can also achieve competitive performance on DBLP and ACM. Such experimental results further verify the necessity of AutoAC.

#### Iv-C2 Performance comparison with the existing attribute completion method HGNN-AC

As the current SOTA attribute completion method, HGNN-AC [18] uses the attention mechanism to aggregate the attributes of the direct neighbors for the nodes with missing attributes. The attention information is calculated by the pre-learning of topological embedding. To be fair, both AutoAC and HGNN-AC are evaluated under the unified HGB benchmark. And, we also combine HGNN-AC with MAGNN and SimpleHGN, denoted by MAGNN-HGNNAC and SimpleHGN-HGNNAC respectively.

Table III shows that AutoAC outperforms HGNN-AC on all datasets. Specifically, MAGNN-AutoAC achieves 1%-4% performance improvement over MAGNN-HGNNAC. For the SimpleHGN model, SimpleHGN-AutoAC outperforms SimpleHGN-HGNNAC by 0.4%-2%. Moreover, the performance improvement of HGNN-AC for attribute completion is not stable. As shown in Table III, after attribute completion with HGNN-AC, MAGNN-HGNNAC is instead inferior to MAGNN on the three datasets, while MAGNN-AutoAC can achieve significant performance improvement with attribute completion. Similarly, there is a degradation in performance on the DBLP dataset compared to SimpleHGN.
### _Efficiency Study_

Besides the effectiveness, we also evaluate the efficiency of AutoAC in the terms of runtime overhead. Table II and V show the runtime of AutoAC and other handcrafted HGNNs on node classification and link prediction tasks. Although the attribute completion and GNN training are jointly optimized in AutoAC, the computational efficiency of AutoAC is still competitive compared to other baselines.

Also, we compare AutoAC with the existing attribute completion method HGNN-AC. Table IV shows the efficiency comparison between AutoAC and HGNN-AC. AutoAC contains the search and retraining stages, and HGNN-AC contains the pre-learning and training stages. We can see that AutoAC is much more efficient than HGNN-AC. The end-to-end runtime overhead of AutoAC can be reduced by 15\(\times\) to 465\(\times\). The main reason why HGNN-AC is inefficient is that the pre-leaning stage that learns a topological embedding for each node is very time-consuming. Especially for the DBLP dataset with a large number of nodes, the pre-learning overhead is up to 9 GPU hours. In contrast, there is no additional pre-leaning stage in AutoAC. Moreover, by introducing the discrete constraints and auxiliary unsupervised clustering task, the search efficiency can be improved significantly.

In summary, AutoAC can not only achieve better performance but also demonstrate higher computational efficiency.
### _Ablation Study_

Iv-E1 Study on the necessity of searching attribute completion operations from a diverse search space

We compare AutoAC with the following two methods:

* **Single-operation attribute completion:** We complete all no-attribute nodes with the same single completion operation (i.e., GCN_AC, PPNP_AC, MEAN_AC, and One-hot_AC).
* **Random attribute completion:** For each no-attribute node, we randomly select an attribute completion operation from the search space.

Table VI and Table VII show the completion operation ablation study on SimpleHGN and MAGNN. Due to the differences in the data characteristics, there is no single completion operation that can perform well on all datasets. By searching the optimal attribute completion operations AutoAC can achieve the best performance on all datasets.

Take SimpleHGN shown in Table VI for example. GCN_AC is more effective on DBLP and IMDB, while PPNP_AC performs better on ACM. Moreover, for a specific attribute completion operation, the performance is related to the dataset and the chosen GNN model. We take DBLP as an example. GCN_AC performs better on SimpleHGN. However, when the GNN model becomes MAGNN, GCN_AC is not as good as MEAN_AC. Additionally, the performance of the random attribute completion is not stable and can be even worse than the baseline model. Choosing an inappropriate completion operation can have a negative effect on the final performance.

#### Iv-E2 Study on the search algorithm with discrete constraints

When optimizing the attribute completion parameters \(\alpha\), we enforce discrete constraints on \(\alpha\) and solve the bi-level optimization problem with proximal iteration. To verify the effectiveness of discrete constraints, we further run AutoAC with and without discrete constraints in Table VIII.

The search algorithm with discrete constraints can achieve better performance with less search time overhead on all datasets. Additionally, proximal iteration allows removing the need for second-order derivative in solving the bi-level optimization problem. Thus, the memory overhead can also be reduced significantly.As shown in Table VIII, the memory overhead of MAGNN-AutoAC without discrete constraints is huge and the out-of-memory error occurs on DBLP.

#### Iv-E3 Study on the auxiliary unsupervised clustering

To reduce the dimension of the completion parameters \(\alpha\), we leverage an auxiliary unsupervised clustering task. Figure 3 shows the performances of different clustering methods.

* **w/o cluster:** We directly search the attribute completion operations for each no-attribute node without clustering.
* **EM:** After each iteration of the optimization process, we adopt the EM algorithm for clustering according to node representation learned by the GNN model.
* **EM with warmup:** a variant of the EM algorithm, which adds a warm-up process at the beginning of the clustering.

In Figure 3, AutoAC can achieve the best performance on all datasets. Searching completion operations without clustering yields relatively poor performance. Reducing the dimension of \(\alpha\) with unsupervised clustering is very necessary. Moreover,

Fig. 4: Convergence of \(\mathcal{L}_{GmoC}\) on three datasets.

Fig. 3: Performance comparison between different clustering methods.
the proposed unsupervised clustering method outperforms EM and its variant, indicating the effectiveness of the joint optimization of the unsupervised clustering loss and the classification loss. Figure 4 also shows the convergence of the unsupervised clustering loss \(\mathcal{L}_{GmoC}\), which exhibits a stable decreasing trend during the optimization process.

### _Distribution of Searched Completion Operations_

Figure 5 shows the proportion of attribute completion operations searched by SimpleHGN-AutoAC and MAGNN-AutoAC. For different models and datasets, the proportions of searched completion operations are quite different. In SimpleHGN-AutoAC, DBLP tends to select GCN_AC, while ACM prefers PPNP_AC. For the same dataset, different

Fig. 5: Distribution of searched attribute completion operations.

Fig. 6: Detailed distribution of searched completion operations for each no-attribute node type on the ACM dataset using SimpleHGN-AutoAC.

Fig. 7: Detailed distribution of searched completion operations for each no-attribute node type on the IMDB dataset using SimpleHGN-AutoAC.
GNNs also result in different distributions. Take DBLP as an example. MAGNN-AutoAC is more inclined to MEAN_AC than GCN_AC compared to SimpleHGN-AutoAC. The results further indicate the necessity of searching for suitable attribute completion operations under different datasets and GNNs.

Figure 6 and Figure 7 show the proportion of searched completion operations for each no-attribute node type on ACM and IMDB. For ACM, multiple different completion operations are selected even for the same node type. Specifically, more than half of the author and subject nodes choose PPNP_AC, while the proportions of other three operations are quite similar. Most term nodes are assigned PPNP_AC (i.e., 94.74%), indicating that the term type is more likely to capture the global information. The main reason is that the target node type (i.e., paper) with raw attributes in ACM contains only the paper title. The high-order PPNP_AC operations are preferred. In contrast, GCN_AC accounts for the majority of completion operations on IMDB. This is because the target node type (i.e., movie) has raw attributes and contains rich features, such as length, country, language, likes of movies, and ratings. Thus, the local completion operation GCN_AC is appropriate.

Next, we analyze the completion operations of concrete actor nodes. In IMDB, node No.10797 is the actor Leonardo DiCaprio, who has starred in 22 movies, and the neighborhood information is very rich. As a result, AutoAC chooses GCN_AC for him. In contrast, node No.10799 is the actor Leonie Benesch, who has appeared in only one movie. Thus, one-hot_AC is automatically selected by AutoAC.

### _Hyperparameter Sensitivity_

#### Iv-G1 Effect of the number of clusters \(M\)

Figure 8 shows the performance of AutoAC under different \(M\). Both SimpleHGN-AutoAC and MAGNN-AutoAC can achieve stable performance, showing that AutoAC has sufficient robustness to \(M\).
the IMDB dataset. Moreover, the performance of both models decreases as the masked edge rate increases.

## VI Conclusion

In this paper, we proposed a differentiable attribute completion framework called AutoAC for automated completion operation search in heterogeneous GNNs. First, we introduced an expressive completion operation search space and proposed a continuous relaxation scheme to make the search space differentiable. Second, we formulated the completion operation search as a bi-level joint optimization problem. To improve search efficiency, we enforced discrete constraints on completion parameters and further proposed a proximal iteration-based search algorithm. Moreover, we leveraged an auxiliary unsupervised node clustering task to reduce the dimension of completion parameters. Extensive experimental results reveal that AutoAC is effective to boost the performance of heterogeneous GNNs and outperforms the SOTA attribute completion method in terms of performance and efficiency.

## Acknowledgment

This work was supported by the National Natural Science Foundation of China (#62102177), the Natural Science Foundation of Jiangsu Province (#BK20210181), the Key R&D Program of Jiangsu Province (#BE2021729), Open Research Projects of Zhejiang Lab (#2022PG0AB07), and the Collaborative Innovation Center of Novel Software Technology and Industrialization, Jiangsu, China. Guanghui Zhu and Yihua Huang are corresponding authors with equal contributions.
