Cross-heterogeneity Graph Few-shot Learning

Procedure for Extracting Meta-patterns. For a single HG ${G}$, we propose a random walk-based approach to capture prevalent local structures and form meta-patterns: (1) Starting from each node in ${G}$, ${N}_{\emph{path}}$ paths with a length of ${l}$ are randomly chosen for each node, and these paths are aggregated into a set $\mathbf{S}_{\emph{path}}$. (2) For every node type $\Phi_{i}\in\mathcal{A}$ ($\Phi_{i}$ denotes the $i$-th node type), subpaths that connect nodes with the same node type $\Phi_{i}$ are extracted from $\mathbf{S}_{\emph{path}}$, forming the set $\mathbf{S}_{\emph{path}}^{i}$. (3) $\mathbf{S}_{\emph{path}}^{i}$ is then partitioned into distinct groups based on the type patterns of the subpaths (e.g., subpaths with the ”author-paper-author” pattern and the ”author-venue-author” pattern are assigned to different groups). (4) Meta-patterns for $\Phi_{i}$ are identified by selecting the patterns with the top-${K}_{\emph{mp}}$ highest counts. Hence, the meta-patterns in ${G}$ can be represented as $\mathcal{P}$ = $\{\mathcal{P}_{i}|\Phi_{i}\in\mathcal{A}\}$.

Categorization for Meta-patterns. Our categorization approach firstly divides meta-patterns into two main categories: affiliation patterns (APs) and interaction patterns (IPs). Within each category, we further classify the patterns into two subcategories based on the strength of the relationship they represent. For instance, APs can be further categorized as either strong affiliation patterns (SAPs) or weak affiliation patterns (WAPs). This categorization is inspired by existing studies that adopt two general types of relations to classify various relationships in HGs (Lu et al., 2019; Shi et al., 2020): the affiliation relation between nodes with individual properties and nodes with set properties (e.g., ”paper-venue”), and the interaction relation between nodes with individual properties (e.g., ”author-author”).

Meta-pattern Instance Aggregation. To begin with, we perform the aggregation of instances belonging to the same meta-pattern category and the same view (e.g., $\mathcal{I}^{\emph{sum-SIP}}$). Let $\mathcal{I}_{v}^{\emph{sum-SIP}}$ represent a set of instances that start from node $v$ and are extracted from $\mathcal{I}^{\emph{sum-SIP}}$. An instance encoder is employed to transform the node features of each instance into a single vector:

where $\mathbf{x}_{\emph{u}}$ is the feature of node u, ${I}_{v\emph{-}i}^{\emph{sum-SIP}}$ represents the ${i}$-th instance in $\mathcal{I}_{v}^{\emph{sum-SIP}}$, and $f^{\emph{SIP}}_{\theta}(\cdot)$ denotes the shared encoder function for SIP instances. Since each instance contributes differently to the representation of the target node, we learn the importance weight for each instance and utilize a multi-head attention mechanism to calculate weighted sums of the instance representations:

where $\alpha^{\emph{sum-SIP}}_{v\emph{-}i,k}$ denotes the importance of ${i}$-th instance at the ${k}$-th attention head, $\|$ denotes the concatenation operation, $\mathbf{a}_{\emph{sum-SIP}}$ represents the trainable attention parameter shared among SIP instances obtained from the sum-view, ${K}_{\emph{att}}$ corresponds to the number of attention heads, and $\sigma(\cdot)$ denotes an activation function.

Meta-pattern Category Aggregation. Next, we aggregate the information from the four meta-pattern categories under the same view. Specifically, we adopt an attention mechanism to aggregate information from these meta-pattern categories:

where $\mathbf{S}_{\emph{mp}}$ = $\{\emph{SAP, WAP, SIP, WIP}\}$ is the set of meta-pattern categories, $\mathbf{W}_{\emph{sum}}$ and $\mathbf{b}_{\emph{sum}}$ are trainable parameters, $\mathbf{a}_{\emph{sum}}$ denotes the shared attention parameter for meta-pattern categories in the sum-view.

View Aggregation. Finally, we aggregate the information from the three views to obtain the final embedding:

where $\mathbf{S}_{\emph{view}}$ = $\{\emph{sum, max, mean}\}$ is the set of views, $\mathbf{W}_{\emph{view}}$ and $\mathbf{b}_{\emph{view}}$ are trainable parameters, and $\mathbf{a}_{\emph{view}}$ denotes a view level attention parameter.

Graph-level Score Submodule. This submodule is proposed to evaluate the transferability of each source HG. By comparing the similarity of heterogeneous information between the source HG and the target HG, we determine whether the source HG contains sufficient generalized knowledge for effective knowledge transfer. Specifically, we calculate the transferability of each source HG by comparing the meta-pattern distributions between this source HG and the target HG. Since the mean-view in the multi-view learning module captures the distributions of all meta-patterns, we utilize the vector $\mathbf{h}_{v}^{\emph{mean}}$ output by the mean-view (cf. Eq. 9) to compute the representation of the meta-pattern distribution for each HG:

where $\tau$ is an $N$-way $K$-shot task, $T_{i}$ is the set of tasks for $i$-th source HG $G_{i}$, and mean$(\cdot)$ denotes the averaging operation. For the target HG $G_{t}$, we randomly select $N\times K\times|T_{i}|$ nodes and input them into the current model to obtain $h_{v}^{\emph{mean}}$ and form $h_{G_{t}}$ using the mean$(\cdot)$ operation. Note that this process is solely for obtaining representations of different HGs in the same vector space, and therefore the gradients during the vector acquisition process are not optimized. Next, we concatenate the representations of each source HG and the target HG and adopt softmax to compute the graph-level score for each source HG:

where $\mathbf{W}_{g}$ is the trainable parameter.

Task-level Score Submodule. This submodule is proposed to evaluate the consistency of each task. In meta-learning, each task consists of a support set and a query set. The support set is utilized to adapt the model to a specific task, while the query set is employed to evaluate the model’s performance on unseen examples from the same task. When it comes to few-shot learning on HGs, there may exist meta-pattern differences between nodes in the support and query sets, even if they are sampled from the same class. These discrepancies in meta-patterns can impact the feedback provided by the query set, potentially resulting in inaccurate evaluations of the model’s ability to acquire knowledge from the support set. However, existing methods solely consider the graph structure to assess the task importance (Zhang et al., 2022c; Song et al., 2022), disregarding the influence of meta-pattern differences. Therefore, we propose to assess the importance of each task by examining the consistency between the meta-patterns surrounding nodes in the query set and support set. Similar to the mean-view vector $\mathbf{h}_{v}^{\emph{mean}}$ used for comparing meta-pattern distributions at the graph-level score, we utilize the sum-view vector $\mathbf{h}_{v}^{\emph{sum}}$ to represent all meta-patterns surrounding $v$ and generate representations for the support set and query set:

where $\tau^{i}=\{\tau^{i}_{\emph{spt}},\tau^{i}_{\emph{qry}}\}$ is a single task. Then, we concatenate the representations of the support set and query set and apply the softmax function to compute the task-level score for each task:

where $\mathbf{W}_{t}$ is the trainable parameter. Since we only compare tasks within the same HG, $T$ is the set of tasks of a single source HG.

Node-level Score Submodule. This submodule is proposed to evaluate the informativeness of each labeled node. We consider that the informativeness of the node is highly correlated to the importance of its meta-pattern instances. Consequently, we first calculate the importance of each instance as follows (here we take ${i}$-th SIP instance of node $v$, i.e., ${I}_{v\emph{-}i}^{\emph{SIP}}$, as an example):

where $\mathcal{I}^{\emph{SIP}}_{v}$ is the set of instances that start from ${v}$ and match patterns in $\mathcal{P}^{\emph{SIP}}$, $\mathbf{a}_{\emph{SIP}}$ is the trainable attention parameter shared by SIP instances. ${{s}}_{v}$ and ${{s}}_{v\emph{-}i}^{\emph{SIP}}$ denote the initial scores of ${v}$ and $I_{v\emph{-}i}^{\emph{SIP}}$, respectively, which are computed as follows:

where $\mathbf{W}_{s}$ and $\mathbf{W}_{\emph{SIP}}$ are trainable parameters. The function ${f}_{\emph{agg}}(\cdot)$ is used to aggregate the information of nodes in each instance, such as operations like ${mean}(\cdot)$, ${max}(\cdot)$, or ${sum}(\cdot)$. Then, we utilize $|\mathcal{I}^{\emph{SIP}}_{v}|$ to quantify the popularity of node ${v}$, and then apply a sigmoid non-linearity to calculate the node-level score for the SIP category, which can be expressed as follows:

where $\eta$ is a small constant. Next, we calculate the average score for all meta-pattern categories to obtain the node-level score:

Prototypical Network. After obtaining the node-level score for each node sample, CGFL follows the idea of prototypical networks (Snell et al., 2017) and calculates the weighted average of ${K}$-shot embedded nodes belonging to class ${c}$ to obtain the prototype of that class:

where ${sc}_{i}$=${ns}_{i}/\sum\nolimits^{K}_{{i}=1}{ns}_{i}$ is the normalized node-level score, $\mathbf{h}_{i}$ is the embedding of node $i$ that is output by multi-view learning. The node-level score submodule is trained through meta-training and used to compute the class prototype in meta-testing.

Loss Function. During meta-training, the prototype for each class is computed by utilizing the nodes in the support set $\tau^{\emph{spt}}$. To determine the class of a query node $u$ in the query set $\tau^{\emph{qry}}$, we calculate the probability for each class based on the distance between the node embedding $\mathbf{h}_{u}$ and each prototype:

where ${d}(\cdot)$ is a distance metric function and we adopt squared Euclidean distance (Snell et al., 2017). Under the episodic training framework, the objective of each meta-training task is to minimize the classification loss between the predictions of the query set and the ground truth. The training loss of a single task $\tau$ can be defined as the average negative log-likelihood probability of assigning correct class labels:

where ${y}^{*}_{i}$ is the ground truth label of ${v}_{i}$. Then, by incoporating the graph-level score and task-level score, the total meta-training loss can be defined as:

where $\mathcal{L}^{i}_{\tau_{j}}$ denotes the training loss on $j$-th task of $i$-th source HG.

Few-shot learning based on local subgraphs: CGFL extracts subgraphs around $N$-way $K$-shot labeled nodes for learning, rather than processing the entire graph structure. This approach ensures the input graph size for CGFL remains small and consistent during computation, resulting in stable memory consumption and improved computational efficiency.

Independent of node type for heterogeneous information extraction: CGFL does not rely on specific node types to capture heterogeneous information; instead, it focuses on capturing four widely existing meta-pattern categories across HGs. This ensures that the computational complexity of CGFL remains unaffected when the number of node types increases.

Datasets. We adopt four real-world datasets: DBLP, IMDB, YELP, and PubMed. These datasets are publicly available and have been widely used in studies of node classification in HGs (Wang et al., 2019; Shi et al., 2020). Details of the datasets are provided in Table 2.

Meta-learning Settings. Since the node types in any two of the four datasets are completely different, we choose to use one dataset as the target HG for meta-testing, while the remaining three datasets are used as source HGs for meta-training. This setting yields the most challenging scenario for heterogeneous graph few-shot learning, wherein the datasets for meta-training and meta-testing have entirely different heterogeneities. We repeat such challenging scenarios to conduct all four separate experiments, where each of the four datasets serves as the target HG in one experiment.

Baselines. Given the absence of dedicated solutions designed for the cross-heterogeneity graph few-shot learning problem, we select 12 representative and state-of-the-art methods as baselines. These baselines can be categorized into four groups:

• •

  Homogeneous GNNs: GAT (Velickovic et al., 2017), SGC (Wu et al., 2019) and GIN (Xu et al., 2018).

• •

  Heterogeneous GNNs: HAN (Wang et al., 2019), MAGNN (Fu et al., 2020) and SGAT (Lee et al., 2022).

• •

  Few-shot learning methods: MAML (Finn et al., 2017) and ProtoNet (Snell et al., 2017).

• •

  Graph few-shot learning methods: Meta-GNN (Zhou et al., 2019), GPN (Ding et al., 2020), G-Meta (Huang and Zitnik, 2020) and TENT (Wang et al., 2022b).

While most baselines can follow our meta-learning setting with minor modifications, it is worth mentioning that HAN and MAGNN employ specialized modules to capture information from specific node types and meta-paths. Consequently, these models can only deal with HGs with single-heterogeneity. Therefore, we only train HAN and MAGNN on the target HG to evaluate the effectiveness of these methods in leveraging heterogeneous information of the target HG to address the few-shot problem.

Parameter Settings. In the ${N}$-way ${K}$-shot setting, ${N}$ is set to {2, 3} and K is set to {1, 3, 5}. The number of task m is set to 100 for all datasets. To ensure fair comparisons, the embedding dimension is set to 64 for both the baselines and CGFL; the parameters for each baseline are initially set to the values reported in the original paper and then optimized through grid-searching to achieve the best performance. For CGFL, in the meta-pattern extraction module, ${N}_{\emph{path}}$ is set to 20, ${l}$ is set to 40, ${K}_{\emph{mp}}$ is set to 10, $\theta_{\emph{lp}}$ is set to 3. In the multi-view learning module, ${N}_{\emph{mean}}$ is set to 5, $\emph{f}_{\theta}^{\emph{SAP}}(\cdot)$, $\emph{f}_{\theta}^{\emph{WAP}}(\cdot)$, $\emph{f}_{\theta}^{\emph{SIP}}(\cdot)$ and $\emph{f}_{\theta}^{\emph{WIP}}(\cdot)$ are set as $\emph{mean-pooling}(\cdot)$, $\emph{K}_{\emph{att}}$ is set to 4, the activation $\sigma(\cdot)$ is set to $\emph{relu}(\cdot)$. In the meta-learning module, $f_{\emph{agg}}(\cdot)$ is set to $\emph{sum}(\cdot)$.

Evaluation Metrics. The performance of all methods is evaluated by two widely used node classification metrics: Accuracy and Macro-F1 score (Velickovic et al., 2017; Zhou et al., 2019). To ensure a fair and accurate assessment of the performance of all methods, we perform 10 independent runs for each N-way K-shot setting and report the average results.

Performance Comparison with Baselines (RQ1). Tables 3 and 4 present the performance comparison between CGFL and baselines. The ”DBLP” column presents the results of the experiment where the DBLP dataset is set as the target HG and the rest three datasets are set as source HGs. The results demonstrate a substantial improvement of CGFL over the best-performing baselines. On average, CGFL achieves a 5.56% increase in accuracy (ranging from 1.69% to 10.37%) and a 4.97% increase in F1-score (ranging from 0.95% to 11.55%). This improvement can be attributed to the utilization of the proposed multi-view HGNN and score module in CGFL, which effectively learn generalized knowledge across HGs. In contrast, the baselines struggle to generalize information from source HGs with different heterogeneities. thereby resulting in inferior performance when applied to a new heterogeneity with few-labeled data.

Ablation Study (RQ2). We create ten variants of CGFL to investigate the impact of its three main modules: (1) Four variants are created to investigate the impact of the meta-pattern extraction module by removing meta-patterns of SAP, WAP, SIP, and WIP. These variants are denoted as M\SAP, M\WAP, M\SIP, and M\WIP, respectively. (2) Three variants are developed to explore the influence of the multi-view learning module by removing the sum-view, max-view, and mean-view. These variants are denoted as M\Sum, M\Max, and M\Mean, respectively. (3) Three variants are created to study the impact of the score module by removing submodules of the graph-level score, task-level score, and node-level score. These variants are named M\G-Score, M\T-Score, and M\N-Score, respectively. From Fig. 3, we have the following observations:

Impact of the Number of Source HGs (RQ3). We investigate whether CGFL can effectively extract generalized knowledge from different types of heterogeneities by varying the number of source HGs. The results presented in Table 5 illustrate that as the number of source HGs increases, CGFL consistently demonstrates improved performance. This is due to CGFL’s capability to enrich generalized knowledge by learning from more source HGs with various heterogeneities and effectively transfer the enriched generalized knowledge to the target HG.

Parameter Study (RQ4). We evaluate the sensitivity of several important parameters in CGFL, and show their impacts in Fig. 4. For the meta-pattern threshold $\theta_{\emph{mp}}$ and length threshold $\theta_{\emph{lp}}$, moderate values should be set around 10 and 3 respectively. This selection helps effectively categorize meta-patterns into general categories. For the number of meta-patterns $K_{\emph{mp}}$, a larger value (greater than 10) generally yields better results. This is because a larger $K_{\emph{mp}}$ allows CGFL to capture a broader range of diverse meta-patterns. For the number of instances in the mean-view $N_{\emph{mean}}$, performance stabilizes when $N_{\emph{mean}}$ exceeds 5. This is because subsequently extracted instances may not possess distinct characteristics that contribute to the learning of meta-pattern distributions.