Heterogeneous graph adaptive flow network
Authors: Lu Yiqi
Feng Ji
Wee Peng Tay
Venue: Accepted by TMLR ()

Abstract: Many graphs or networks are heterogeneous by nature, involving various vertex types and relation types. Most graph learning models for heterogeneous graphs employ meta-paths to guide neighbor selections and extract composite relations. However, the use of meta-paths to generate relations between the same vertex types may result in directed edges and failure to fully utilize the other vertex or edge types in the data. To address such a limitation, we propose Heterogeneous graph adaptive flow network (HetaFlow), which removes the need for meta-paths. HetaFlow decomposes the heterogeneous graph into flows and performs convolution across heterogeneous vertex and edge types, using an adaptation to change the vertex features based on the corresponding vertex and edge types during aggregation. Experiments on real-world datasets for vertex clustering and vertex classification demonstrate that HetaFlow outperforms other benchmark models and achieves state-of-the-art performance on commonly used benchmark datasets. The codes are available at https://github.com/AnonymizedC/HetaFlow.

Published in Transactions on Machine Learning Research (10/2024)
Heterogeneous graph adaptive flow network
Lu Yiqi
yiqi001 Ge.ntu. ee..nt..du..... edu.sg
Deportment of Electricol and Electronic Engineering Nongang Technological University
Ji Feng
jifeng edu...eedu.....
Department of Electricol and Electronic Engineering
Nangang Technological University
Tay Wee Peng
uptay@ntu.cdee edu...
Deportment of Electricol and Electronic Engineering
Nonyang Technological University
Reviewed on OpenReview: /ttps://openreen net/ forum? iinnm?iddda id= id=usug3yhjA
Abstract
Many graphs or networks are heterogeneous by nature, involving various verlex types and relation types. Most graph learning models for heterogeneous graphs employ meta-paths to guide neighbor selections and extract composite relations. However, the use of meta- paths to generate relations between the same vertex types may result in directed edges and failure to fully utilize the other vertex or edge types in the data. To address such a limitation, we propose Heterogeneous graph adaptive flow network (HetaFlow), which removes the need for meta-paths. HctaFlow docomposes the heterogencous graph into flows and performs convolution across heterogeneous vertex and edge types, using an adaptation to change the vertex features based the corresponding vertex and edge types during aggregation. Experiments on real-world datasets for vertex clustering and vertex classification demonstrate that HetaFlow outperforms other benchmark models and achieves state-of- the-art performance on commonly used benchmark datasets. The codes are available at https:// http:://gtthhhhoo///oo ChooomizzdCHHotaaPPPaa
1 Introduction
A significant number of real-world graphs come with diversity of vertex types and relation types. For
example, the ACM dataset (Wang et al.) 2019) (example data shown in Fig. [ consists of four types of vertices: paper, author, conference, and subject. Many heterogeneous graph neural network (HGNN) models are based on the idea of meta-paths (Huang et al. 2016 Zhhan et al. 2018a Hu et al. 2018). A meta-path is an ordered sequence of edge types, which defines a new composite relation between the source vertex type and the destination vertex type. For example, in the ACM dataset, a relation between two papers can be described by the meta-path Paper-Author-Paper (P-A-P), which represents an author's co-authorship of these two papers; or Paper-Subject-Paper (P-S-P), which implies that the two papers investigate the same subject. Depending the meta- meta-path, the relation between vertices can have different semantics.
Most meta-path- basd- based heterogencous graph models for semi-supervised vertex classification and clustering [Zhang et al., 2019a Shi et al. 2018 Fan et al. 2019) follow two similar steps to create homogeneous graphs on which traditional GNN models can then be applied: 1) Meta-paths are chosen so that the source and destination vertex types are the same. 2) Then, one employs a set of predefined meta-paths to decompose the original heterogeneous graph into one or several subgraphs with homogeneous vertex types. An appropriate GNN model each subgraph can then be applied and the results fused to obtain the final inference.

---

Published in Transactions on Machine Learning Research (10/2024)
People also proposed www-mett--ptt--aaseeee models. These models mainly follow two approaches. They either introduce some projection methods and attention mechanisms to aggregate representations of vertices, like HGT Hu et al. (2020) and HetSANN Hong et al. (2020), or find suitable meta-paths by themselves, like ie- ie-HGCN Yang et al. (0211). These two directions have different challenges.
Methods of the first direction normally set different weights for different edge types. For example, HGT Hu let al.) (0200) assigns different aggregation weights for each edge type. However, edges in heterogeneous graphs are very likely to be directed, and edges of one edge type may connect different vertex types. So, there is room to improve in the projection and aggregation parts, like introducing type-related adjustment part models can automatically find suitable
during aggregation. Although the other kind of non-meta-path- meta-paths, they still need to face problems caused by the usage of meta-paths. For instance, the obvious direction of meta-pati and the information loss of intermediate vertices.
Most heterogencous graph models fail to consider the directions of edges. In some heterogencous graph applications, edges have an inherent direction based on the vertex types of their end vertices. For example, in a network connecting teachers and students, viewing an edge going from teacher student versus the opposite direction has different meanings. Therefore, the importance of vertex to another vertex depends how that vertex is reached and not just on the distance edge attention weights wetween them. Mela-patth-bsse methods are more likely to meet such challenges, like the meta-path Bubject-PPpper-Ce Saapieee-aape--Cnnfeeeeee----e Conference-Subjeet (S-P-C-S) in Fig. [ Thus, it may be appropriate to assign different weights to neighboring vertices according to their positions. Allocating the same weight to vertices al the same distance may result in suboptimal resulls.
Many existing heterogeneous graph models failed exploit the type information fully. It makes sense that features of different vertex types should be projected to different spaces, and aggregations along various edge types should use separate filters. Similarly, it is also appropriate to assign different. weights to the same vertex when aggregating with vertices of different types (even when the edges are of the same type). Thus, the performance can be improved by introducing type-basod adjustment weights during aggregations.
As shown in Fig. [d), all the intermediate vertices and the vertices that do not appear in the chosen meta- meta-paths are not represented in the homogeneous subgraphs created using the meta-path approach. Furthermore, all subgraphs only contain a single vertex type. A substantial proportion of the vertex features from vertex types not represented are discarded, which is apparently detrimental (e.g., HERec (Shi al. 2018) and HAN (Wang et al. 2019)). Embedding methods such as MAGNN Fuu et al., 2020) employ encoders to encode the features of intermediate vertices. However, it is unclear how one can choose an efficient encoder for different datascts. Furthermore, these embeddings use type-based vertex feature transformations, which do not take the intermediate connections into consideration.
The choice of meta-paths limits the relationships the model can learn. As shown in Fig. [c). the meta-path P-A-P allows a model to learn the relationship between two papers with a common author. It does not however learn other relationships like P-S-P if this meta-path has not been explicitly included.
The number of possible meta-paths increases exponentially with respect to the number of vertex lypes and edge lypes. There is positive correlation between the number of filters that are needed and the number of meta-paths. Most models in the literature Dong et al. 2017) Shi et al. 2018 Fu et al. (2020); Fu & King (2024) either discard some meta- meta-paths or require siguificant computational power if all meta-paths are included. Meta- sataa-path-asseee approaches are thus not scalable if they want to include all possible meta-paths.
We introduce parallel flow decomposition and type-basod adjustment address these challenges. We decompose the graph into 1D paths which allows us assign different weights to vertices based on their positions instead of distances.
2

---

Published in Transactions on Machine Learning Research (10/2024)
Author
A2
A
A
Comferisoo
P2
Paper
1141
T
T
T
T
Smlgect
Si
P.A Mitsepath (P-A-P)
Mite-path
No)oode Type
Heterngemme Gragia
(PLA.P) bosed
neighhor
Figure 1: An example of a heterogeneous graph based on the ACM dataset.
We propose novel Heterogeneous graph adaptive flow network (HetaFlow).. HetaFFlw first decomposes the graph into several groups of paths, which call "parallel flows". Then, for each edge, the model encodes it according to its edge type and its two end vertex types. HetaFlow applies type-specific linear transformations to project heterogencous vertex attributes for cach vertex to common vector space. Each edge thus gets its type-based edge ura. Next, HetaFllw performs intra-path aggregation along each path in every parallel flow, and inter-flow aggregations across multiple parallel flows with type- base- feature adjustments.
The computational complexity of HetaFlow is lowered significantly compared these other models and its model size depends only on the number of parallel flows used. See the discussion about model size and complexity in Appendix B and Appendix C.
In this work, we introduce the concepts of paths and parallel flows to heterogencous graphs and design type-based adjustments. We generalize the model to heterogeneous graphs with addit ional mechanisms to handle the heterogeneity of the graphs. Extensive numerical experiments are provided to verify our module choices.
2
Related work
2.1 Graph neural networks
GNNs exlend convolution neural networks (CNNs) general graph-structured data. There are two main classes of GNNs, namely spectral-based and spatial-based. Spectral-based GNNs operate in the Fourier domain. An example is ChebNet (Defferrard et al. 2016), which processos graph signals (vertex features) using Chebyshev polynomials of the graph Laplacians. By simplifying the parameters of ChebNet, GCN (Kipf & Welling 2016) overcomes the overfitting problem of ChebNet. However, spectral-based GNNs require the whole graph as an imput in the worst case when the polynomial degrees are high, and are sensitive to graph structures. They thus suffer from scalability issues.
Spatial-basod GNNs imitate the convolution operation CNNs. GNNs of this kind operate directly on vertex's neighbors. An example GraphSAGE (Hamilton et al., 2017), which learns embeddings by aggregating features of the target vertex and its neighbor vertices. Other spatial-based GNN variants have been proposed by improving the aggregator function. GAT (Velickovic et al. 2018 employs the attention mechanism in the aggregator to assign different importance weights based on the neighboring vertices' features. GFCN (Ji et al. 2020) decomposes a graph into non-intersecting paths and performs convolutions along these paths before aggregating them. It can be shown that GFCN recovers the GCN model. Inspired by the idea of GGNN (Li et al. (016)) that adds gated recurrent unit (GRU) [Cho al. 2014) into the aggregator function, GaAN [Zhang al.] [2018b) combines GAT and GGNN for spatio-temporal graphs. To improve the accuracy, STAR-GCN (Zhang et. al. 2019c) employs various GCN encoder-decoders.
3

---

Published in Transactions on Machine Learning Research (10/2024)
The above-mentioned GNNs are designed for homogencous graphs in which all vertices and edges are of the same type. One main limitation that stops GNNss from being adapted to heterogeneous graphs is that the vertex features for different vertex types in a heterogeneous graph are from different spaces.
Adaptive graph learning (Luo et al. 2017 Li et al. 2018 Zhou et al. 2019 has shown good generalization ability when facing real problems, where data are on an irregular grid or in other kinds of non-Fuclidean domains. Adaptive graph learning can help models to be more general. To obtain a discriminative feature subset, Luo et al. (2017) learns the optimal reconstruction graph and selective matrix simultancously. The
graph learning into a unified learning model. To paramcterize the similarity between two vertices on the graph, Li ct al. (2018) employs & bearnable distance metric. In this work, we design a type-based adaptive method to parameterize the filters in some layers so that our model can better handle heterogeneous graphs.
paper Zhou et al. 2019 combines multi-featur dictionary learning and adaptive
2.2 Heterogeneous graph embedding
Various heterogeneous graph embedding methods have been proposed to embed vertex features into a low- dimensional space. For example, metapath2vec (Dong et al. 2017) employs meta-path-based random walks and skip-gram [Mikolov et al. 2013a generate vertex embeddings. With the guidance of manually-defined meta- paths, ESim (Shang et al. 2016) learns vertex features in user- eser-preferred embedding space. H1N2vec (uu et al. 2017) learns vertex embeddings and meta-path reprosentations simultancously by carrying out multiple prediction training tasks. Given a meta-path, HERec (Shi el al. 2018) proposes an algorithm that converts a heterogeneous graph into meta-path-bee based neighbors and then employs the DeepWall (Perozzi ct al. 2014) model to learn the target vertex embodding. Similar to HERec, HAN (Wang et al.) 2019) also decomposcs a heterogeneous graph into multiple meta-path-basee homogencous graphs. HAN uses a graph attention mechanism to combine results from different meta-paths.
These heterogeneous graph embedding models suffer from the limitations discussed in Section ! due to the reliance on meta-paths to construct homogeneous subgraphs. The use of meta-paths inevitably introduces some limitations like discarding vertex features or loss of vertices and connections. For example, metapath2vec, ESim, HIN2vec, and HERec omit vertex features, which lowers their performance when performing tasks on graphs with rich vertex features. Furthermore, HERec and HAN only consider the two end vertices of each meta-path while ignoring the vertices along the path, which results in information loss. The method metapath2vee achieves suboptimal performance as it takes only one meta-path the input. ScHGNN (Yng) ett al. 2023) improves the performance by introducing feature projection. However, it needs a complicated extra data pre-processing step.
Several HGNNs (Zhang et al. 2019b Yun ct al. 2019 Ly et al. 2021 Ahn et al., 2022 have boen proposed to solve the meta-path selection dilemma by generating new graph structures. For instance, HeiGNN (hang et al. 2019b) divides neighbors into subsets based on their types and employs an aggregator function for each type of neighbor. However, as pointed out by Lv et al. (2021), HetGNN has "information missing in homogeneous basclines" and "GAT with correct inputs gets clearly better performance". Simple-HGN (Lv et al. 2021 is based on GAT. It leverages type information by introducing learnable type embeddings and enhanced modeling power with residual connections and 42 normalization on the output embeddings.
Many attention-based models failed to learn node-level and relation-level attention simultancously. BA-GNN Iyer et al. (2021) employs a novel bi-level graph attention mechanism to overcome this issue. Instead of from the global graph context, BA-GNN attends to both types of information from local neighborhood contexts. It achieved good performance. However, it assigns the same weights to the neighbor vertices of the same distance, which means the directions of edges are not exploited during aggregation.
ic- Hc-HGCN Yang et al. 2021) proposed a hicrarchical architecture as object-level and type-level aggregation. ie-HGNN can learn the representations of objects and automatically discover and exploit the most useful meta-paths. Its 'two-level aggregation structure' shows good performance and interpretability in capturing semantic relations. Our HetaFlow has a similar design. HetaFlow's 's intra-path aggregation and inter-path aggregation empower it to catch semantic relations efficiently. As mentioned in Section D ic-HGCN fails to consider the directions of edges. It assigns the same weights to neighbor vertices in the same distance. By
4

---

Published in Transactions on Machine Learning Research (10/2024)
Table 1: Notations
Notations
Description
R"
The n-dimensional Euclidean space. Graph with vertex set V and edge set E. The set of vertex types.
g (V,E)
A
R
The set of edge types.
The embedding of vertex a and edge (u, v), respectively.
Tas Tav
The collection of paths that contain the vertex v.
Po
(h)h)
The --hop neighborhood of vertex v.
X
Feature vector of vertex v.
he
Hidden state (embedding) of vertex v. Activation function.
(t)
Element-wise multiplication.
1.1
The cardinality of set.
II
Vector concatenation.
1/3
211
015
15
U14
011
012
013
11
612
174
173
U11
F1
110
1/5
1/2
1/3
1/4
Parallel flow
210
Mia 61
115
1/4
11.2
0g
1/
V15
01
0/.
011
V12
V13
014
015
07
76
01d
V1g
01
8/2
08
074
216
017
V15
Parallel flow 2
(a)
(b)
(d)
Figure 2: (a) A heterogeneous graph: different colors for vertices and edges indicate different types. (b) A
subgraph with homogencous edge type. (c) parallel flow decomposition. (d) Two parallel flows.
decomposing the graph into 1-D flows, HetaFlow capable of learning different weights to neighbors with the same distance.
HGT Hu et al. (0200) and HetSANN Hong et al. (2020) also non-meta-path-bast methods. They avoid the meta-path selection dilemma by projecting the representations to the same space and employing attention mechanisms to help aggregations. They make use of the 'type' information by assigning different aggregation weights to various edge types. However, this may not be enough since the same-type edges may connect vertices of different vertex types, which usually happens when there cxists only one edge type in the heterogeneous graph. HetaFlow mitigales this problem by introducing an adjustment component. HetaFlow employs learnable parameters to generate adjustment weights based on the embeddings of types of vertices and edges. When aggregating on the same edge type, the fcatures of neighbor vertices adjusted differently based on their vertex types.
3 Preliminaries
In this section, we define important terminologies related to heterogencous graphs. Graphical illustrations are provided in Fig. 2 We summarize the commonly used notations this paper Table Throughout this paper, consider graph G (V,E), where V is the set of vertices and & is the set of edges of the graph.

---

Published in Transactions on Machine Learning Research (10/2024)
Definition 1. (Heterogeneous graph) A heterogeneous graph G is associated with vertez type mapping function Φ V/ A and on edge type mapping function 1/ -> R, where A and R. denole the predefined sels of verter types and edge types, respectively, with |A] + [R] > 2. Purthermore, if subgruph G' includes only single edge type, then we call g' a subgraph of 9 with homogeneous edge type.
An example of heterogeneous graph is shown in Fig. 2aa). This heterogeneous graph consists of four different
types of vertices and two types of edges. Fig. (b)) illustrates subgraph with homogeneous edge type. Though it contains only the green edge type, there are four types of vertices in it, which means it is also heterogencous graph.
Definition 2. (Path) A path P of heterogeneouus graph G a connected subgraph such that each verter of P has a degree not more than 2 in P. In particular, a single verter or cycle a path.
Definition 3. (Parallel flow) Two paths P1 and P2 said to be parallel to each other if they do not shore any common verlices in G. Furthermore, a set of palhs P (P, Pn) is parallel flow if ils elements are pairwise parallel.
For example, in Fig. 2 aa), consider the path P1 given by the vertex sequence (V10, 15, 12, 03 v4): the path P2 (v16, U14, vG, U7, Ug, U9) and the path P3 (V17, VIG, V12, U13), we can see any two of Pt, P2, and P3s are parallel since there are no common vertices edges between them. Furthermore, the set {Pi, P2, Pa is parallel flow all its elements
pairwise parallel.
Definition 4. (Parallel flow decomposition) Consider a collection of parallel flows Pi...., Pm, each of which contains paths of homogeneous edge type. If Uf= P, contains all edges in the heterogeneous graph 9, then this collection of parallel flows called a parallel flow decomposition of g.
Since each edge in Fig. 2 b) appears in Fig. d and the two parallel flows do not share common edges, Fig. d) is an example of a parallel flow decomposition of Fig. b). Parallel flow decompositions are not unique for a heterogeneous graph G. For instance, in Fig. Lb), we can choose a parallel flow consisting of a single path 11--0-----111-11---1
and a parallel flow consisting of two four-vertex paths in 01-U2-08-04 and 01-014-111-11 This forms a parallel flow decomposition of Fig. 2bb) different from that in Fig. (d)..
Besides accuracy, runtime speed or computational complexity of a GNN concern for large graphs The computational complexity is closely related to the model size. To quantify our model size, require the following definitions and upper bound on the number of parallel flows (Ji et al. 2020). We briefly recall the following notions and results from Ji et al. (2020) for the homogeneous graphs.
Definition 5. set of parallel flows (PI..... ......,m! Pm] is a cover of G if the union of all the paths in the parallel flows contains all the edges of 9. The smallest m such that there cover consisting of m porallel flows is denoted as u()).
4
Heterogeneous adaptive flows
In this section, we present HetaFllw. We refer the reader to Fig. 3 for an illustration of the HetaFlow framework, which is summarized as follows:
We first explain the motivation for introducing such decomposition methods. See Section 4.1
We perform parallel flow decomposition of given heterogeneous graph G, with each parallel flow having single edge type. See Section 4.2
We perform vertex feature transformation to map the features of all vertices to the same space. See Section
Intra-path aggregation with attention weights is performed along each path in each parallel flow. See Section 44
A vertex may appear in multiple parallel flows, each of which generates a feature vector in the steps above. Inter-flow aggregation is performed to fuse these feature vectors for each vertex. See Section 4.5

---

Published in Transactions on Machine Learning Research (10/2024)
Vertex-level
Path-based adjustment weights
Undated Graph
Edge embeddings }
adjustment weights
Adaptive
Auc
{FF}
layer
0000
(lc)Atativee jadjustments
Graph
Labels
(hC)
(h.
Original features [xx]
MLP
(a) Paralllll flow decomposition
Eb]Edge embedding and node feature transformation
(d)lntra-path aggregation
(e) Inter-flow
(() Passing to next aggregation loop or prediction layer
aggregation
Figure 3: The overall framework of HetaFlow. Steps (c), (d), and (e) can be repeated.
4.1 Motivation and differences
Before delving into the details of the model, we first discuss why we choose decompose the heterogencous graph into parallel flows. Without relying on any prior mela-path knowledge, we want to decompose a heterogeneous graph into subgraphs that traditional GNNs can handle. An intuitive idea is to form subgraphs by selecting the edges that follow similar patterns, i.e., build subgraphs with homogeneous edge type. For example, consider the heterogeneous graph shown in Fig. 2 aa). It can be decomposed into two subgraphs: one subgraph is shown in Fig. bb) and the other subgraph consists the three separate blue lines in Fig. 2 a). However, even though a subgraph has homogeneous edge types, it may still not be appropriate to apply a homogencous GNN on the subgraph due the following two considerations.
Firstly, there may exist multiple vertex types in each subgraph, and thus we need to make adjustments based the types of the vertices when performing convolutions. We resolve this challenge by introducing vertex feature transformation, which is discussed in detail in Section
4.3 As discussed in the comparisons in
Section 2.2 many non-meta-pate based methods, like HGT Hu et al. 2020) and HetSANN Hong et al. (2020) employ different weights for the aggregations along each edge typc. However, edges of one edge type may connect various types vertices. For instance, 'paper' type vertices can be linked both 'conference' type and 'journal' type vertices by 'be submitted to' type edge. When predicting the research area of a 'paper' vertex, it better assign different weights 'conference' type and 'journal' type vertices because journals are more general in some research area. However, HGT and HctSANN shall use the same filter since the edge type is the same. We introduce the adaptation adjustments improve the performance against this problem.
Secondly, some types of edges may be directed, like the steeccher-teacchessttueele relations in a social network. Consider a path with 3 vertices and two edges, for a person. When trying to predict the academic interest. of ny; we may find features of U and ey are of different importance. Thus, may be appropriate assign different weights to neighboring vertices according to their positions instead of distances. Allocating the same weight to vertices the same distance may result in suboptimal results the weights no longer capture the importance of these vertices to the target vertex at which the convolution is applied.
where each vertex stands
We introduce parallel flow decomposition that decomposes the graph into 1D paths and allows us to assign different weights to vertices based on their positions a neighborhood of the target vertex on the 1D path. Morcover, though the odges of each subgraph are likely to follow similar patterns, they may contain different. meanings and need be processed differently. For example, consider a computer vision task. In an image, the horizontal and vertical edges follow the same pattern (both be detected by similar 1D convolution
7

---

Published in Transactions on Machine Learning Research (10/2024)
filters) but may have different meanings and contributions when performing prediction tasks. Parallel flow decompasition helps us to capture such information by splitting the graph into different flows.
However, there's a certain degree of randomness to this decomposition process. Parallel flow decompasition was originally designed for homogeneous graphs, which means it failed to consider the relations between the flows of different subgraphs. Note that. 'type information' now available, as well as some semantic relations between the flows of various subgraphs. HetaFlow designs a transformer-basee based semantic adaptation module and employs attention mechanism (step (c) in Fig. 3) to learn the mutual attention between semantic The whole forward propagation process is illustrated in
flows (see in Section 4.3
Section 4.4 Section 4.5
Algorithm
4.2 Flow decomposition
4.2.1 Implementation
Let O be an operation that takes a heterogeneous graph Go = (V, as the input and outputs a subgraph G1 = (1),&)) with homogencous edge type. One intuitive example of O is to select all edges of a certain type in 9n- Starting with a given heterogeneous graph 90, we build a subgraph 91 = (G))) Then, we repeat. this operation on the remaining part, i.c., the complement of graph 91 with respect to 9o: to obtain another homogeneous edge type subgraph G2 O()), where 9i (V, &i). This procedure is repeated until no edges remain.
The original heterogencous graph is thus decomposed into several subgraphs with homogencous edge types. Then, we can follow Ji et al. (2020) to decompose each subgraph into parallel flows and take the union of the decompositions. This union is a parallel flow decomposition of the original heterogeneous graph.
For completeness, we now provide brief description of the parallel flow dccomposition implementation. Note that this approach is only one of many possible approaches. For details, we refer the reader to Ji et al. (2020). For every subgraph G. (V, &,) (can be possibly disconnected), forest Ga (Vi, En) consisting of trees that span the components of G, is found by performing a depth-first search of the graph (in this paper, we select a vertex with the highest degree in subgraph G, to be the root vertex for each component). Denote the complement of the forest Ga with respect to G, as Gi whose edge set is & &E and isolated vertices after removing En are removed. Repeating the process, we again find a spanning forest Giz for G This procedure repeated until the remaining complement is emply. The procedure terminates a finile number of steps n because the number of edges remaining in the complement at each step decreases. We then have G. - Gij-
Nexi, we consider the parallel flow decomposition of tree in each forest Gij obtained in the above procedure. Let this tree be 7' and degmux be its maximal degree. We can label each edge in T with number in the set {1,2...., (degmax +1)/2]} such that every label is used at most twice for edges in T connected to cach verlex in T. Finally, to form a parallel flow, we take edges that have the same label. The tree T is now decomposed into multiple parallel flows.
4.3 Feature embedding
We first record the types of vertices and edges so that we can adjust the vertex features according to their types. For most datasots, the vertex types and edge types are categorical. We use onc-hot encoding for them.
For an edge (u, u) connecting vertices u and v, let Tu RIAI denote the one-hot encoding of the type of vertex u, and Tap E [ be the one-hot encoding of the type of edge (u,v), v). Then, its edge embedding given by:
Zuo Tu T T.
Different vertex types may have feature vectors with unequal dimensions and belong to different feature spaces. So we apply a type-based lincar transformation for each type of vertices before fcoding vertex feature vectors into the intra-path aggregation module. Let x, E Rd denote the original feature vector of vertex e, and WA A Rd'xda denote the parametric weight matrix for type vertices. Then, for vertex v of type
8

---

Published in Transactions on Machine Learning Research (10/2024)
A E A, the projected latent vector is given by
hy = Wx ER"
(2)
4.4 Intra-path aggregation
Since the intra-path aggregation involves only vertices on this path, it is natural to consider 1D convolution. For each parallel flow P, we employ the same 1D convolution filter of odd length for all paths P E P. Let No P N 1)/2) to denote neighbors of vertex v on path P. The 1D convolution each vertex v along the path P is given by:
h =a
Σ WEN!
w Ph
(3)
where the weights w are the 1D convolution filter weights for the parallel flow P.
To fuse features Icarned from different edge types and parallel flows, we perform vertex-lovel and flow-basod mdjustments. The weighting coefficients employed this process are called adjustment weights.
We design an adjustment weight that modifies the edge weights based on the types of edges and their end vertices. Let W. and b, be learnable paramcters. Then, the vertex-level adjustment weight A is defined as:
Aue (W WaZue ba) EER ERR.
(4)
Suppose that vertex u is neighbor of vertex on path P. We modily as:
Σ a (w Awv)) KENT
(5)
Next, we use attention mechanisms learn the importance eP of a neighboring vertex u vertex v on the path P, which is then normalized across all choices of u E Noe using the softmax function. Then, we obtain a normalized importance weight a for each neighboring vertex this path.
Furthermore, to reduce the variance introduced by the parallel flow decomposition, extend the attention mechanism to multiple heads by concatenating independent allention mechanisms. Let h E Rd denote the features of vertex i after intra-path aggregation, [<Pu], denote the importance of to v the k-th head, [oPu] denote the normalized importance of to in the k-th head, and [ap]s E Rdd the parameterized attention vector for path P in the k-th head. Then, the k-th attention mechanism, for k = I...., K, can be expressed as:
[cpu], LeakyRoLU (aallx
[ (6.16=])
exp ([ePu)
P. [ava]
EsENs exp (lepals)
(6)
h kml
P
=
σ
Σ jEN!
[afle h,
To fuse the features h in 6 of the same vertex different paths P, we incorporate an atlention mechanism based on paths. Each path from a parallel flow consists of only one edge type. Let Tp be the edge type encoding of path P, and W,, by be learnable parameters. The path-based adjustment weight F for path P is defined as:
FP = by) E "
(7)
9

---

Published in Transactions on Machine Learning Research (10/2024)
We update the vertex features by doing element-wist multiplication. The feature h E R of vertex path P, which is processed by the inter-flow aggregation in the next step, can be expressed as:
h = h OF..
(8)
4.5 Inter-flow aggregation
Suppose there M parallel flows in the parallel flow decomposition of Section 4.2 since it belongs to at most one path in each parallel flow, have at most M latent vectors {h? P P.). where P. is the collection of all paths that contain vertex and [Pol s M. Since paths in P. are not equally important to the vertex it is reasonable to use the attention mechanism to assign different weights to features obtained from different paths. We use 3 to denote the relative importance of path P to vertex v. We perform a weighted sum of all the path-based feature vectors of u using the parameterized attention vector q Rdd follows:
Then for cach vertex e,
c = q h
exp (e.")
86 ΣpEp. exp (c))'
(9)
h
Σ 8 h
PEP
Finally, we add a layer with a learnable weight matrix Wo E xd to change the shape of the output vector:
h =0 (Wof.)).
(10)
4.6 Training
To process the vertex representations, we use the following loss functions. Here we denote the set of vertices that have labels as Vz, the number of classes as C, the one-hot label vector of vertex u as Ye, and the predicted probability vector of vertex u as h, For semi-supervised learning, we use the cross entropy loss as follows:
C= Σ VEV.
Σ
yolc] log h.]c,,
(11)
where yo [c] denotes the e-th component of the vector yo-
For unsupervised learning, let be the of positive (observed) vertex pairs, and Q be the set of negative vertex pairs sampled from the complement of Ω. Then, minimize the following loss function via negative sampling (c.f. Mikolov et al. (2033)) with sigmoid function o(-):
C=
log hh.
Σ (1.))e
log (-h, h,)
(12)
(a.))e
4.7 Analysis of HetaFlow
4.7.1 Generality
In this section we want discuss about the generality of HetaFlow. can represent more general polynomials than most current meta-pat meta-path-ben base- heterogeneous GNNs. It is even capable of achieving aggregations that not be expressed by polynomials.
10

---

Published in Transactions on Machine Learning Research (10/2024)
Assume that given heterogeneous graph has types of edges and let S denote fixed graph shift operator (one common choice is the graph's normalized adjacency matrix Laplacian matrix). For edge type i, we can pick out all corresponding elements in S and perform zero paddings to form a submatrix S,, whose shape is the same as S. In this way, we decompose 5 into the sum of n submatrices Si,..., where S is the corresponding graph shift operator for edges of type i.
Many current heterogeneous GNNs perform convolutions among each subgraph and then fuse the outputs of each subgraph (Wang et al., 2019 Fu et al.) 2020 Fu & King, 2024). For given graph signal X, assume that meta-path- math-based model fuses with the sum function. Then the final output is
(s)))))
(13)
where (() is the activation function, and pt(+) denoles given graph convolution filter for edge lype i. HetaFlow is capable representing a more general polynomial, where each monomial consists of several variates. This observation is expressed in the following result.
Proposition 1. Suppose no edge contained in different paths inside a given set of parallel flows. If M is the number of monomials and N denotes the lorgest number of voriates contained in one monomial, then there is a HetaFlow model with M + + E ki hidden layers producing the same output as the convolution filler
P(S ................................ Sn) _
ke
(14)
ag
for any input graph signal, where aij denotes the inder of the j-th variate in the i-th monomial, and ki and by denote the corresponding power and coefficient, respectively.
Proof. See Appendix
Proposition shows that there no loss in generality adopting HetaFlow with parallel flow decomposition when compared to traditional heterogeneous GNNs like HAN Wang et al. (2019), MAGNNFu al. (2020), and Simple-HGN et al. 20211) It is clear from (14h that the representations can learn using HetaFlow are strictly richer than that achievable by the heterogeneous GNNs in 13 This motivates us to consider the use of parallel flow decompositions in HetaFlow.
In contrast, 14 is a multi- variat polynomial and involves interactions between different edge types with the same weights assigned to the same kind of interaction. It is also clear that HetaFlow not restricted to that particular form. By utilizing 1D convolutions along paths, HetaFlow can assign different weights to vertices at the same distance in the path (i.e., the 1D filter is non-symmetric). And under this case, is obvious that. can not any polynomial to represent it.
In Section 5.4 we perform ablation studies on the effect of introducing parallel flow decompositions to obtain insights into the impact of different decomposition approaches.
4.7.2 Time complexity
We provide detailed general analysis of the model size and computational complexity of HetaFlow in Appendix B and Appendix [ Here follow the assumptions of SeHGNN al. 2023) to make clearer comparisons with other models. The theoretical results are summarized as Table 2
We assume one-layer structure with M mela-paths for SeHGNN and HAN. Let. be the maximum hop of meta-paths. To ensure the same receptive field size, we assume a l-layer structure for Simple-HGN and HetaFlow. The dimension of input and hidden vectors d. Instcad of considering all vertices, here we discuss the case when doing tasks on vertices of one vertex type. The number of target-type vertices n. For HAN, let ej be the average number of neighbors in meta-path neighbor graphs. Let 62 be involved neighbors during
11

---

Published in Transactions on Machine Learning Research (10/2024)
multi-layer aggregation Simple-HGN. Both e1 and 62 grow exponentially with the length of metapaths and layer number 1. (19) shows that the computational complexity of HetaFlow is closely related to 'the number of edge types' and 'the max degree of vertices'. Let [R'| denotes the total number of edge types of the involved subgraphs, and [P'] denotes the total number of parallel flows to be aggregated.
Then from 19), the time complexity of HetaFlow
= = +)nd).
((
(15)
For complicated graphs whose number of types of vertices and edges are large, RR| is normally much smaller than the total number of edge types [R]. There are |A|2 possible edge types and edges of at most 2| edge types connecting target-type vertices (for the generality of discussion, we consider the directed graph here. If it is undirected, then [R'] is at most [A]). So, HetaFlow only needs to decompose at most 2| subgraphs. Moreover, HetaFlow can discard parallel flows that do not contain target-type vertices. For instance, consider the example claimed in Fig.
2 HetaFllow can discard parallel flow in Fig. 2 d) if the target vertex type is the blue vertex type. So |P'| normally smaller than the total number of parallel flows [P]. And the number of possible meta-paths is large for complicated graphs. Take length meta-paths an example (we assume the endpoints of meta-paths are of the target node type), cach intermediate position the meta-path has |A| possibilities. There are |AlS possible meta-paths that contain targel vertices as the endpoints. Thus, M > R when trying to consider all possible meta-paths for complicated graphs.
For the four datasets we tested in experiments, if want to consider all possible meta-path, then we have M >> [R']|P' so the theoretical complexity of HelaFlow much lower than that of SeHGNN, and much lower than that of HAN and Simple-HGA according to Yang et al. 2023
Feature Neighbor
Semantic fusion (m(Mdd+MMad O(nMd
Total
projection aggregation (n)
SeHGNN HAN
M
(nd?)
O(nMeid)
MMd)
Simple-HOL HGN (nldd)
((nedd) O(RR'IP' medd)
((d((e2+ld) O([R' ()ndf))
HetaFlow
O(nld))
Table 2: Time complexity of HetaFlow, SeHGNN, HAN, and Simple-HGN.
5
Experiments
In this section, conduct experiments on the clustering and classification lasks using benchmark dalasets. We compare the performance of HetaFlow to other state-of-the-art baseline models. The implementation details are claimed in Appendix D After testing with benchmarks, we further conduct experiments on several variants HetaFlow to validate the effectiveness each component of our model. We test the validity of vertex feature adjustment, the importance of introduging parallel flow decomposition, and the influence of different decomposition methods separately. These ablation studies are illustrated in Appendix |
5.1 Datasets
We test the performance of HetaF'low on the Heterogeneous Graph Benchmark (HGB) (Lv et al, 2021 using the following vertex classification dalasets:
ACM. We choose the papers published in SIGMOD, KDD, MobiCOMM, SIGCOMM, and VLDB. The papers belong to three categories: Data Mining, Wireless Communication, and Database. Then we construct a subset. that comprises 5835 authors (A), 3025 papers (P), and 56 subjects (S). Paper features are the of embedding of keywords. The papers are labeled based on their classes.
DBLP. We construct a subset of DBLP by selecting 14328 papers (P) and 8789 terms (T). We further include the related 4057 authors (A) and 20 venues (V) in this subset. According research areas,
12

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm HetaFlow forward propagation.
Require:
The node feature {x, V).
The number of layers L,
The number of attention heads K
Ensure: The final node embedding Zy.
for edge type R E R do
Perform BFS based flow decomposition and get a set of parallel flows SR = (Pi,P2,.... P2...., , Pagti
end for
Get the parallel decomposition S by combine all the sets of several parallel flows 8 U Sn,i
Calculate Tee, Tui A E ie V by one hot encoding according to their types Tecs Tni Do edge encoding Ze, + Tni Tea Tajs e E, whereas i, j are the end nodes of e;
for node type A E A do Node content transformation h < WA X ViEVA
end for for 1 1 do for parallel flow P E parallel decomposition S do for path P E parallel flow P do Calculate the two adaptive factors: [Arey] a (Wa, -Zery +b,)), A2p
a (Wl, 02 Ter + bba)):
for node E Vp PnV do for node E N? = N, do
Calculate path-based representation [i]]]
using the edge-level instance encoder:
olw,(h" A1 )}
NEN?
Calculate weight coefficient a. according to 6
end for
Combine the learned embeddings from all heads [T[]] 111 EEENZ [o [ir]'):
end for Perform flow-based adjustments [h,]' <- [ c Azp:
Calculate the importance weight 3p for each path-flow;
end for
Fuse the embeddings of the same node on different paths: fi. + Drep [h[T', VEER;
end for Update node features for the next layer with Layer output projection [h',]++1 +- o (W: .R.) V u uEV;
end for Zy h/, V V; return Zy V V:
13

---

Published in Transactions on Machine Learning Research (10/2024)
Table
Dataset statistics.
Datasets
Nodes
Node Types
Edges
Edge Types
Classes
Features
ACM
10,942
4
547,872
8
3
1830
DBLP 26,128
4
239,566
6
4
334
Freebase
180,098
8
1,057, 1,07,688 ,688
36
7
IMDB
21,420
4
86,642
6
5
1232
we place the authors into four calegories: information retrieval, data mining, database, and machine learning. The research area of each author is labeled based the conferences they participate in. We take the bag-of-words representation of keywords as the author features.
IMDB. We construct a heterogeneous graph that consists of 4278 movies, 5257 actors, and 2081 directors after data preprocessing. We label the movies (Action, Comedy, and Drama) according their genre information. Movie features are the bag-of-words representation of its plot keywords.
Freebase. Freebase is huge knowledge graph of the world's information. It involves many aspects
like music, movies, people, and so on. Following the procedure of a previous survey Yang et al. (020))
we sample subgraph of 8 categories of vertex types with about 1,000,000 edges.
Simple statistics of the datasets are sunmarized in Table 3 and network schema is illustrated in Appendix S For vertices with no attributes, we use the average of the features of their neighbors as their input features.
5.2
Baselines
To evaluate the performance of HelaFlow, we compare with widely-used baselines: RGCN (Shhlchhtkrll)
et al.
2018 HAN (Wang al. 2019) GTN (Yun et al. 2019), RSHN (Zhu et al. 2019).
HetGNN (Zhang
ct al.
2019b), MAGNN Fuu et al. 2020), HctSANN (Hong et al. 2020). HGT (Hu et al.
2020). GCN (Kipf
& Welling 2016), GAT Velickovic et al. 2018), MECCH (Fu & King 2024). SeHGNN Yang et al. 2023
and
Simple-HGN LL et al. 2021).
For comparison purposes, when testing on the homogencous and the random-wai feslom-walk-bbaeee models, we first build homogeneous subgraph, which is homogeneous in both edge and vertex types, for each meta-path. We then test the model each subgraph. After obtaining the performance of the model for every meta-path, take the best one as the performance of the model. For those models based on random walks, the window size is set to be 5, walk length to be 100, walks per vertex to be 40, and the number of negative samples to be 5. For a fair comparison, the embedding dimension decided according to the best results reported in the paper Shi et al. (2018) for all models.
5.3 Numerical results
In all the tables, the best and second-best results for each setting are highlighted by red and blue, respectively. We consider the results to be tied for the best/second-besl results if they are close (within 0.1%).
5.3.1 Classification results
From Table 4 we see that HetaFlow has the best performance for most cases, although it does not utilize meta-paths. In general, HetaFlow has comparable performance on the IMDB dataset and outperforms the other basclines by 0.5 - 0.8% on DBLP and ACM datasets. This verifies our conjecture that parallel flow decomposition suffers less information loss than meta-path mata--ath- reconstruction methods and can make use of edge directions.
Compared to the models that simply average over vertex neighbors, GAT and Simple-HGN perform well since they train weights to weigh the information properly. Compared to HAN and MAGNN, HetaFlow, which requires manually defined naths, captures even richer semantics successfully.
14

---

Published in Transactions on Machine Learning Research (10/2024)
Table 4: Quantitative results (%) on HGB for vertex classification task. Performances of benchmark models are cited from Yang ct al. 2023). Fu & King (2024) and Lv al. (2021).
ACM
DBLP
IMDB
Macro-F1
Micro-F1
Macro-F1
Micro-F1
Macro-F1
Micro-F1
RGČN
91.55 + 0.74 91.41 = 0.75 91.52 = 0.50 92.07 = 0.50 58.85 = 0.26 62.05 + 0.15
HAN
90.89 + 0.43 90.79 0.43 91.67 + 0.49 92.05 : 0.62 57.74
0.96 64.63 - 0.58
GTN
91.31 # 91.20
93.52 0.55
93.97
60.47 0.54
0.98 65.14
RSHN
90.50 + 1.51 90.32
93.31 0.58 93.81
0.55 59.85
3:21 61.22 1.03
HelGNN
85.91 0.25
1.47
9.43
48:25
0.67 51.16
MAGNN
90.88 + 0.64 90.77 = 9.51
9..76+
56.49
64.67 1.67
HetSANN
90.02 89.91 # 78.55
80.56
49.47 57.68
HGT
91.12 0.76 91.00 0.76 93.01
93.49
63.00
67.20 0.57
GCN
92.17 92.12
90.4
91.47
37.88
64.82
GAT
92.26 : 0.94 92.19
9.27
93.39
58.94
64.86
Simple-HGN
93.42 + 0.44 08.35
94.01
94.46
63.53
67.36 0.57
MECCH
92.74 + 0.40 92.67
1 94.31
0.29
95.08
62.59
64.62 2.38
SeHGNN
94.05 1 0.35 93.98
1 0.36 95.06
1 0.17
95.42
67.11
69.17 0.38
HelaFlow
94.42 0.33 94.31 0.34 95.17 0.30 95.04 1 0.35 66.79 + 0.28 69.40 0.33
Table 5: Quantitative results (%) and training time (per epoch/s) on vertex classification task with low- dimensional vertex feature. Performances of benchmark models are cited from Yang ct al. (2023).
Datasets
Metrics
RGCN
HGT
GCN
GAT Simple-HGN
SeHGNN HetaFlow
Macro-F1 16.78 29. 12.52 27.8113.13 40.74
51.87 10.86 66.2910.45
47.72-1148
52.13 1.05
Freebase
Micro-F1 58.3311157 1..51 60.2310.92 65.2610.80
65.08110.45
6..1
Training time
0.85 6.29
0.77
0.31
0.48
All models suffer poor performance on IMDB. This may be due to the labels of vertices: though each movie vertex may be assigned multiple labels, we merely select the most related one as its label. HetaFlow achieves smaller performance gain DBLP than on the other two datasets. This is mainly because it turns out that one of the manually defined meta-paths (A-P-C-P-A) contains most of the information necessary for correct classification. Thus, the performance gain is not as much as on the other two datasets ACM and IMDB. Another reason is that some vertices are discarded since they are not on the meta-paths. Therefore, GCN test only a part of the datasct and may avoid vertices that are hard to classify.
Comparing the results in Table 5 and Table | we observe that although SeHGNN is the best performer on IMDB, it has poor performance on Freebase. This may be due to Freebase having insufficient vertex features. We see that the performance of HetaFlow is more stable across different datasets, which suggests that the adaptive adjustments in HetaFlow are useful. The training time of GAT and GCN is not recorded since the performance is of one meta-path HetaFlow has a fast training speed with the help of data pre-processing (the parallel flow decomposition) and lower complexity.
5.3.2 Clustering
We conduct the clustoring task to evaluate the embeddings learned from the above algorithms. We utilize the K-Means algorithm to perform vertex clustering and the number of clusters K is set to the number of classes for every dataset, i.e. 4 for DBLP and 3 for both IMDB and ACM. We use the same ground truth as in vertex classification. Morcover, we use the Normalized Mutual Information
(SMT))Sttehl& & Ghosh 2002) and the Adjusted Rand Index (ARI) Yeung& & Ruzzo 2001) to measure the quality of the clustering results. Since the performance of K-Means is highly affected by the initial centroids chosen, we repeat. K-Means ten times for each run of the model. Furthermore, we run each model 10 times and report the averaged results in Table G
As seen in Table G on DBLP and ACM, GCN performs better than metapath2vec for the vertex classification task while metapath2vec is better for the clustering task. Candom-walk-beee methods (i.e., metapath2vec)
15

---

Published in Transactions on Machine Learning Research (10/2024)
Table Quantitative results (%) on vertex clustering task.
Datasets
Metries
metapath2vec
GCN
MAGNN
HAN
GTN
Simple-HGN
HetaFlow
NMI
21.22:1.51
51.49110.83
61.9611..3
61.4010.14
61.83:1.24
61.9410.26
62.26:10.25
ACM
ARI
21.00=0.41
53.2410.56
64.79:10.27
64.82:10.24
65.40=0..34
65.3410.25
66.05:1..24
NMI
74.22:00.52 75.41+0..52
81.11+0.37
79.09-F0.12
81 81.02=0.36
81.08+0.35
81.81+0.31
DBLP
ARI
78.50=0..1
80.91+00.77
84.79:40.31
81.56:00.28
85.20=#0.41
85.08=+0.35
85.40:10.32
NMI
1.20=t0.63
5.79:00899
10.07:0.55
10.82:0.50
10.45=0.68
11.27=0.86
11.7240.60
IMDB
ARI
1.70=#0.46
3.78+1.00
9.78
10.08=:0.55
11.53=0.53
11.79+0.89
12.40=00.2
Table 7: Quantitative results (%) of ablation study on parallel flow decomposition, Percentages in the header denote the sizes of training sets. 'M' means million.
Model
Parameter Size
Score
20%
40%
60%
80%
Macro-F1 90.72
91.5110.26
91.97-10.23
92.72:10.16
HetaFlowpr
4.78M
Micro-F1
90.76=10.30
91.6410.30
92.28:0.19
92.73:10.19
Macro-F1
90.84=0.26
91.3410.20
91.5310.15
92.0110.13
HetaFlowwo
6.32M
Micro-F1 P1 90.92=00.30
91.43+0.28
91.68+0.26
91.97+0.19 19
Macro-F1
89.43=0.19
89.97#0.14
90.3240.11
91.26+0.11
HetaFlowiaut
4.98M
Micro-F1
89.20=0.24
89.61=0.18
90.5440.14
90.92+00008
have advantages in vertex clustering because the use of random walks makes vertices that have small distances in the graph to be close in the embedding space You et al. 2019). Thus, the positional information is concerned, which facilitates the K-Means algorithm as clusters vertices based on the Euclidean distances between embeddings. Despite this, HetaFlow performs consistently better than all baselines, which demonstrates that through the use of parallel flow decompositions, HetaFlow can learn powerful vertex embedding without any meta-paths.
5.4 Parallel flow decomposition methods
We study two aspects of the parallel flow decomposition: the influence of introducing such decomposition and the efficiency of various decomposition methods. We test different approaches on the ACM dataset.
The main motivations for introducing parallel flow decomposition are discussed in Section 4.2 HetaFlow allows us to assign different weights to the neighboring vertices, i.e., weights are assigned based on positions instead of distances. With the same number of layers, HetaF'low models can represent richer class of polynomials than traditional GNN approaches.
Firstly, we test the models without parallel flow decomposition nor limits on the model sizes. Secondly, we test models that employ parallel flow decomposition but with a limit on the model size. Then, we test models without parallel flow decomposition but with similar constraints on model sizes. The results are shown in Table
In Table HetaFllow denotes our base HetaFlow model (model size is measured by the number of parameters, which is limited to 5M in this experiment), i.e., the one used to compare with other basclines Table 6 HetaFlow is the equivalent model without utilizing parallel flow decomposition and has no limits its model size. It decomposes the heterogencous graph into subgraphs with homogencous edge types instcad. During convolutions, HetaFlowwo shall assign weights according to the distance as normal GNNs and HetaFlow also keeps the adjustment layers. HetaFlowHmit denotes the model that does not employ parallel flow decomposition and whose model size no larger than 5M. From Table 7 we observe that HetaFlow, pr generally has on-par performance as HetaFlow even though the model size much smaller, RetaFloWjuit has the worst performance.
16

---

Published in Transactions on Machine Learning Research (10/2024)
013
112
01
02
21
2/2
18
877
U11
1/4
M5
Parallel flow
V11
1/4
Ug
03
Parallel flow
U12
U11
P15
11
01
U7
013
Parallel flow 2
Parallel flow
(a) HetaFlowordd order
(b) HetaFlow position
Figure 4: Examples of different parallel flow decomposition methods.
Next, we test different methods select paths in the parallel flow decomposition using the ACM dataset, and the results reported in Table For the decomposition method mentioned in Section 4.2.1 there exist multiple ways to allocate labels to the edges of the spanning subtree.
We consider the following methods to allocate edge labels during the parallel flow decomposition procedure (all methods start from the root vertex and then target at the neighbor vertices following the descending order of their degrees in the tree):
(i) For each vertex under consideration, label adjacent edges according to the descending order of their end vertices' degrees in the original helerogeneous graph G. For instance, consider the spanning tree whose root vertex uy as shown in Fig, a). The vertex Ug has four neighbors in the tree: 02 with degree 4 in the original graph, Uy with degree 3, va with degree 2, and 17 with degree 3. We assign label 1 to the two edges that connect vertices with the first two highest degrees, i.e. the edge (es, 02) and the edge U7). Then we remove 12 and from the neighbor set (V) Repeat the procedure. After all edges that connect us are labeled, we then move to U2, the neighbor vertex of us. Since one or several edges that connect our target vertex may have already been assigned with labels, we skip the corresponding labels so that no label is used more than twice. Here, we obtain the two parallel flows of Fig. b) as shown in Fig. [a). We call this variant HetaFllooorder
17).
(ii) For each vertex e under considcration, select the neighboring vertex with the highest degree 9 as the left neighbor and the neighboring vertex with the lowest degree in as the right neighbor to construct path. Remove these from the neighbor set (1) and repeat the procedure to obtain another path and so on. Consider the example of in Fig. ( again. We obtain the parallel flows shown in Fig. b). This variant is denoted as HetaFlow position
(iii) For each vertex under consideration, assign random labels to the edges connecting it (from 1 to [(degmux +1)/2]) under the constraints that no label is used more than twice. This is our base model HctaFlowp!-
In addition, we also include a comparison with clustering approach to create subcomponents as follows.
(iv) We follow Carranza al. (2018 to construct parallel-flow-like subcomponents. This denoted HetaFlowocuster-
From Table S we observe that the different parallel flow decomposition approaches yield similar performance.
This suggests that HetaFlow is insensitive to the choice of parallel flow decomposition method.
5.5 Visualization
To visualize the results more intuitively, we project the embeddings learned by the above models into a 2-dimensional space. We visualize the author embeddings in DBLP with t-SNE (Van der Maaten Hinton 2008). Various colors denote the different research areas of the authors.
17

---

Published in Transactions on Machine Learning Research (10/2024)
Table 8: Quantitative results (%) of ablation study for parallel flow decomposition method. The best and second-best results for cach sctting are boldfacod and underlined, respectively. Percentages in the header denole the sizes of training sets.
Model
Score
20%
40%
60%
80%
Macro-F1
90.8610.31
91.2211.27
91.8310.13 92.8110.111
HetaFlowordes
Micro-F1
90.94++022
91.46+0.15 92.31+0.15
92.87+0.11
Macro-F1
90.43:10.28
91.6710.27
91.8210.19
92.56.10.14
HetaFlowposiee position
Micro-Fl F1
90.50:10.27
91.5410.24 92.32+0.25
91.78#0.11
Mlacoo-Fl
90.8510.34 91.4310.31
92.11
92.7810.28
Heta Foowpr
Micro-F1
90.88+0.17
91.57:0.16
92.28+0.13
92.67+0.11
Macro-F1
90.43++0.28
90.6440.24
91.30+0.27
91.99-4.344
HetaF HetaFloweluster loweluster
Micro-F1
90.311:0.1 91.0440.18
91.711:.28
91.5840.20
(a) GCN
(b) metapath2vee
(c) HAN
(dd) HetaFlow
Figure 5: Visualization of other embedding methods DBLP. Each point indicates one author and its color indicates the research area.
that the homogeneous GNN, namely GCN, give more separate islands and the boundaries between different colors not clear. Furthermore, we observe area. where all four types of vertices are mixed. One possible reason is that these two models only take information from one meta-path. For some vertices, their labels may be hard to tell apart under certain meta-paths
From Fig. 5
This phenomenon also appears the results of other models, but HAN and HetaFlow perform better as they take information from more meta-paths or the whole heterogeneous graph, respectively. For HAN, we observe that there are at most three kinds of vertices that are mixed together. Meanwhile, there exist places where all four types of vertices HetaFlow, there are fewer places where more than two types of vertices are mixed. Morcover, fewer vertices, which are of different colors, are mixed when compared with the visua sisualization of HAN.
mixed in the results of GCN and metapath2vec. When it comes to the result of
6 Limitations and Future Work
In graph classification tasks that involve a multitude of graphs in both the training and test sets, HetaFlow may not perform well. This is because the parallel flow decomposition is not unique. We may get different. subgraphs when performing parallel flow decomposition using different methods on the same graph. As a result, the filters and attention weights learned on one training graph may not perform well on another graph unless more restrictions imposed to make the parallel flow decomposition unique.
In HetaFlow, the graph is decomposed into multiple parallel flows, with cach vertex now appearing [(deg +1)/2 times. Moreover, unlike meta-path-based methods, HetaFlow retains all vertices in the graph. The memory usage of HetaFlow is thus higher during runtime. A future research direction is to investigate the use of sparse matrix representations and idcas like "drop token" (Hou al.] (022) reduce memory storage. An optimization example illustrated in Appendix[]] Possible future research directions include the investigation of techniques like sparse matrix representaf at and dropping of tokens and graph edges reduce the model
18

---

Published in Transactions on Machine Learning Research (10/2024)
memory usage of HetaFlow. Due to its similarity to CNNs, there is also room to improve HctaFlow further by applying the wealth of methods developed for CNN models.
7 Conclusion
In this paper, have proposed a HGNN framework called HetaFlow to perform semi-supervisod vertex classification and clustering tasks on heterogeneous graphs. HetaFlow addresses three limitations of existing HGNNs: loss of vertex content features due to vertex selection, the dependence on meta-path, and allocation of the same weights to neighboring vertices at the same distances. HetaFlow introduces the notion of parallel decomposition for heterogeneous graphs, which is used to enable the model to assign different weights to neighboring vertices al the same distance. This property benefits detailed vertex-level adaptive adjust ments. HetaFlow applies four building block components: vertex content transformation, intra-path aggregation, adaptive adjustments, and inter-flow aggregation. In experiments, HetaFlow achieves stato-of-the-art results benchmark datasets in the vertex classification and clustering lasks.
References
Hongjoon Ahn, Yongyi Yang, Quan Gan, Taesup Moon, and David Wipf. Descent steps of relation-aware energy produce heterogeneous graph neural networks. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Inf. Process. Syst., 2022. URL http:ts://ppeereeeee...e. forum? frrum?id-hghle hgggkkCKK...
Aldo G Carranza, Ryan Rossi, Amup Rao, and Eunyee Koh, Higher-order spectral clustering for heteroge- neous graphs. arXiv preprint arXiv:1810. 02959, 2018.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN deoodrrdeccodr for statistical machine translation. In Proc. Empirical Methods Natural Language Process., pp. 1724 1734, Doha, Qatar, October 2014. Association for Computational Linguistics. doi: 10.3115/11/D1411
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. CoRR, abs/1606.09375, 2016.
Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In Proc. Int. Conf. Knowl. Discovery Data Mining, pp. 135 144, Halifax, NS, Canada, August 2017. ACM. doi:
Shaohua Fan, Junxiong Zhu, Xiaotian Han, Chuan Shi, Linmei Hu, Biyu Ma, and Yongliang Li. Mctapath- guided heterogeneous graph neural work for intent recommendation. In Proc. Inl. Conf. Knowl. Discovery Data Mining, pp. 2478- 77882 Anchorage, AK, USA, August 2019. ACM.
Yang Fu, Wang-Chien Lee, and Zhen Lei. Hin2vec: Explore meta-paths in heterogeneous information networks for representation learning. In Proc. Conf. Inf. Knowl. Manage., pp. 1797 1806, Singapore, SG, Singapore, November 2017. ACM. doi: 10.1145/31322447.11333 31339933.
Xinyu Fu and Irwin King. Mecch: metapath context convolution-based heterogeneous graph neural networks. Neural Networks, 170:266-210 205,2775,11 2024.
Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. MAGNN: metapath aggregated graph neural network for heterogeneous graph embedding. In The Web Conf. 2020, pp. 2331 1-421,11, Taipei, Taiwan, April 2020. ACM / IW3C2. doi: 10.1145/33666 //////36662333382277
William L. Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Proc. Conf. Newral Inf. Process. Syst., pp. 1024 1034, Long Beach, CA, USA, December 2017. NIPS.
Huiting Hong, Hantao Guo, Yucheng Lin, Xiaoqing Yang, Zang Li, and Jieping Ye. An attention based graph neural network for heterogeneous structural learning. In Proc. A AAAT, volume 34, pp. 4132 4139, 2020.
19

---

Published in Transactions on Machine Learning Research (10/2024)
Le Hou, Richard Yuanzhe Pang, Tianyi Zhou, Yuexin Wu, Xinying Song, Xiaodan Song, and Denny Zhou. Token dropping for efficient bert pretraining. In Proc. 60th ACI, volume 32, pp. 3774-37747- Dublin, Ireland, 2022.
Binbin Hu, Chuan Shi, Wayne Xin Zhao, and Philip S Yu. Leveraging meta-path based context for top-n recommendation with neural co-attention model. In Proc. 24th ACM Int. Conf. Knowl. Discovery Data Mining, pp. 1531-1540, 2018.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In Proc. Web Conf. 2020, pp. 2704-2710, 2020.
Zhipeng Huang, Yudian Zheng, Reynold Cheng, Yizhou Sun, Nikos Mamoulis, and Xiang Li. Meta structure: Computing relevance in large heterogeneous information networks. In Proc. 22nd ACM Int. Conf. Knowl, Discovery Data Mining, pp. 1595-1604, 2016.
Roshni G Lyer, Wei Wang, and Yizhou Sun. Bi-level attention graph neural networks. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 1126-1131. IEFE, 2021.
Feng Ji, Jielong Yang, Qiang Zhang, and Wee Peng Tay. GFCN: A new graph convolutional network based on parallel flows. In Proc. Int. Conf. Acoustics, Speech, Signal Process., pp. 3332 -336,, Barcelona, Spain, May 2020. IEEE doi:
URL https://arxiv. http::://arri.ooor///////0//
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. Int. Conf. Learn. Representations, San Diego, CA, USA, May 2015. Conf. Track Proc.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutiona networks. CoRR, abs/1609.02000 02900, 2016.
Ruoyu Li, Sheng Wang, Feiyun Zhn, and Junzhou Huang. Adaptive graph convolutional neural networks. In Proc. AAAI, volume 32, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In Proc. Int. Conf. Learn. Representations, San Juan, Puerto Rico, May 2016. Conf. Track Proc.
Minnan Luo, Feiping Nie, Xiaojun Chang, Yi Yang, Alexander G Hauptmann, and Qinghua Zheng, Adaptive unsupervised fcature selection with structure regularization. IEEE Trans. Neural Networks Learn. Syst., 29(4):944 956, 2017.
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Feng, Siming Hc, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks. In Prec. 27th ACM SIGKDD, pp. 1150-11600 2021.
Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. In Proc. Int. Conf. Learn. Representations, Scottsdale, Arizona, USA, May 2013a. Workshop
Track Proc.
Tomás Mikolov, llya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In Proc. Conf. Neural Inf. Process. Syst., pp. 3111-3119, Lake Tahoe, Nevada, USA, December 2013b. NIPS.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representations. In Proc. Int. Conf. Knowl, Discovery Data Mining, pp. 701-710, New York, NY, USA, August 2014. ACM.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In Proc. 15th ESWC, pp. 593 607, Heraklion, Crete, Greece, 2018. Springer.
Jingbo Shang, Meng Qu, Jialu Liu, Lance M. Kaplan, Jiawei Han, and Jian Peng. Meta-path guided embedding for similarity search in large-scale heterogeneous information networks. CoRR, abs/1610.09769, 2016.
20

---

Published in Transactions on Machine Learning Research (10/2024)
Chuan Shi, Binbin Hu, Wayne Xin Zhao, and S Yu Philip. Heterogencous information network embedding for recommendation. IEEE Trans. Knowl. Dala Eng., 31 (2):357-377) 2018. doi: 10.1109/TKDE.2201..2255 28333443..
Alexander Strehl and Joydeep Ghosh. Cluster ensembles- a knowledge reuse framework for combining multiple partitions. J. Mach. Learn. Res., 3(Dec):588 617, 2002. doi: 00.1622/1324433321977775
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using I-sne. J. Mach. Learn. Res,, 9(11): 2579-2605, 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liö, and Yoshua Bengio. Graph attention networks. In Proc. Int. Conf. Learn. Representations, Vancouver, BC, Canada, 2018.
OpenReview.net.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S. Yu. Hetcrogencous graph atlention network. In Proc. World Wide Web Conf,, pp. 2022 2032, San Francisco, CA, USA, May 2019.
ACM. doi: 45553335558888
Carl Yang, Yuxin Xiao, Yu Zhang, Yizhou Sun, and Jiawei Han. Heterogeneous network representation learning: A unified framework with survey and benchmark. IEEE Transactions on Knowledge and Data Engincering, 34(10):4854-48755 2020.
Xiaocheng Yang, Mingyu Yan, Shirui Pan, Xiaochun Ye, and Dongrui Fan. Simple and efficient heterogeneous graph neural network. In Proc. AAAI, volume 37, pp. 10826, 2023.
Yaming Yang, Ziyu Guan, Jianxin Li, Wei Zhao, Jiangtao Cui, and Quan Wang. Interpretable and efficient heterogeneous graph convolutional network. IEEE Transactions Knowledge and Data Engineering, 35 (2):1637-1650, 2021.
Ka Yee Yeung and Walter L Ruzzo. Details of the adjusted rand index and clustering algorithms, supplement to the paper empirical study on principal component analysis for clustering gene expression data. Bioinformatics, 17:763 774, 2001.
Jiaxuan You, Rex Ying, and Jure Leskovee. Position-aware graph neural networks. CoRR, abs/1906.04817, 2019.
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jacwoo Kang, and Hyunwoo Kim. Graph transformer networks. Advances in Newral Inf. Process. Syst., 32, 2019.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V. Chawla. Hetcrogencous graph neural network. In Proc. Inl. Conf. Knowl. Discovery Dala Mining, pp. 793 803, Anchorage, AK, USA, August 2019a. ACM.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Helerogeneous graph neural network. In Proc. 25th ACM SIGKDD, pp. 793 803, 2019b.
Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Metagraph2vec: Complex semantic path augmented heterogeneous network embedding. In Proc. Pacific-Asie Conf. Knowl, Discovery Data Mining, pp. 196-208. Springer, 2018a.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Din Yeung, Gaan: Gated attention networks for learning on large and spatiotemporal graphs. In Proc. Conf. Uncertainty Artif. Intell., pp. 339 349, Monterey, California, USA, August 2018b. AUAI Press.
Jiani Zhang, Xingjian Shi, Shenglin Zhao, and Irwin King. STAR-GCN: stacked and reconstructed graph convolutional networks for recommender systems. In Proc. Int. Joint Conf. Artif. Intell., pp. 4264 4270, Macao, China, August 2019c. IJCAI. doi: 1.24963//jeai.2015
Runwu Zhou, Xiaojun Chang, Lei Shi, Yi-Dong Shen, Yi Yang, and Feiping Nic. Person reidentification via multi-feature fusion with adaptive graph learning. IEEE Trans. Neural Networks Learn. Syst., 31 1592-1600 2019.
21

---

Published in Transactions on Machine Learning Research (10/2024)
Shichao Zhu, Chuan Zhou, Shirui Pan, Xingquan Zhu, and Bin Wang. Relation structure-aware heterogeneous graph neural network. In ICDM, pp. 1539-1539. TEEE, 2019.
22

---

Published in Transactions on Machine Learning Research (10/2024)
A Proof of Proposition
Input layer
Repeat 2 times:
Conv. layer on subgraph S3: (1,01) 1)
Fusion by sum
Conv. layer on subgraph S1: (1, 1)
Fusion by sum
Repeat times:
Conv. layer subgraph S3: 01,0, 1)
Fusion by sum
X 3
Output layer
Figure 6: An example HetaFlow network to model a given monomial 3S
Given target polynomial ΣM b; I1 Saij, generating the equivalent output of each item in this polynomial and finally fuse them. The output of one monomial can be achieved by concatenating several convolution layers and fusion layers, where every convolution layer uses a 3x1 1 filter and fusion layers take different fusion functions with respect to the graph shift operator to be used. Here we assume that = A, the adjacency matrix, so fusion layers take sum as the fusion function (same fusion function normalized Laplacian matrix, then fusion functions should be changed average).
construct the corresponding HetaFlow model by
is the Laplacian matrix; if use normalized adjacency matrix
Recall that Sn denotes the graph shift operator of the subgraph Gn, where Gn is the subgraph consisting of all parallel flows with the edge type T, E RÍ The proposition hypothesis assumes that there is no common edge between the parallel flows of the same subgraph. After convolutions with the filter (1, 0, 1) alone each parallel flow of the subgraph Gn, we can achieve the monomial S, with a fusion layer to sum the output of each parallel flow. For example, we can achieve the monomial 3 with the model shown in Fig. where assume the graph shift be the adjacency matrix.
For the general expression b; I Ski the i-th monomial of our target polynomial, we can choose the filter (1, 0, 1) and perform convolutions on the subgraph San by kn times, followed by convolutions on the subgraph Sa., by kg times and so on. HetaFlow repeats similar operations until finally obtaining I[ Say. Then by multiplication with an appropriate coefficient, HetaFlow generates this monomial. The target polynomial is achieved by summing all the monomials. An explicit example of the whole model is shown Fig. 7
HetaFlow needs 2 ky hidden layers to generate the output of one monomial. There are thus
M + DA Σ/en kij hidden layers in total in the HetaFlow model to achieve the polynomial
14
23

---

Published in Transactions on Machine Learning Research (10/2024)
Input layer
Decomposition based on edge types Couvolution on subgraphs
Repeat Kuy times."
[Répeat Kar times:
Conv. layer on 1yrrpph Suary? (1. 0,
Conv. layer p.ppraph Suns!
Fusion by sum
Fusion by sum
Repraa Karz times:
Repeat ki times:
Conv. layer subgraph Says?
Conv. layer subgraph Sons (1.0, I)
01,0,1
Fusion by
Fusion by
Repeat kars times:
Repeat Kii times
Conv. layer on subgraph Sunce 1,
Conv. layer subgraph Soys?
(1.0,)
Fusion sum
Fusion by sum
xb
X6g
Xb
Oulput layer
Figure 7: An example HetaFlow network to model a given polynomial.
B
Model size
According Ji al. (2020
Theorem 1. For any homogeneous graph 9, let degmax be the matimal degree of G. Then
m(g) S (1 degmax +1
degmax +1
+ 1)
(16)
2
2
The above result proved as Corollary 1 of et al. (020). We discuss the upper bound for the heterogeneous graph case in Section 4.7
We now present upper bound of the number of parallel flows in a parallel flow decomposition, which is heterogencous graph version of Thcorem [ after the following lemma.
Lemma 1. Suppose G Gi UG. Then u()) < ((G1) + ((G)).
Proof. Assume that covers of G1 and G2 are given by two sets (P "mm...,,m)..._ and 2 (Q1.... enF respectively, where v(Gi) = | and p(G2) = 2.). Remove all common edges of the two sets from 9 obtain 3, where A = " if there does not exist any common edge. Then, the union & 2 is parallel flow decomposition of G. Thus, (())
9 | p(G)) + p(G2) and the proof is complete.
Theorem 2. For any heterogeneous graph G with [ different edge types, for i = 1...., (R), let G. be the subgraph of 9 with homogeneous edge type and deg the marimal degree of G.. Then,
[ Σ
deg +1
deg +1
( < i=1
+1)
(17)
2
2
24

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. By Theorem for each homogeneous subgraph 9,, 1...., |R], we have
(( & (L(deg'n +1) + +1) Lddeg'n +1) /2].
(18)
Since 9 - 9a the result follows from Lemma
For a heterogeneous graph 9 = E) with |A| vertex types and [R] edge types, the transformation layer t has [A d learnable parameters, where d' and dout are the dimensions of the input and output embeddings, respectively.
Suppose the graph g decomposed into (()) parallel flows. Suppose that there are convolution layers. For convolution layer n 21.2....,4 NN, assume that the length of the filter used is k" and the dimensions of the imput and output embeddings are di and dout respectively. Since each convolution layer employs one filter for each flow, convolution layer contains p(G) d d learnable parameters. For each convolution layer, there exists one corresponding adaptive layer and two attention parts. According to our encoding method, the dimension of edge embeddings is 2| + [R]. To calculate the corresponding adaptive weights, the adaptive layer employs four weight matrices whose shapes are din x (2] + [R]), di X 1, dout x [A] and d x 1. The attention mechanism introduccs 2dd + d%ao) parameters for cach convolution layer n.
Let wmax maxn kn, din max, dbu: dmax max, dout: and degmax max; degm. From Theorem (()) [[ ).. Then, the HetaFlow model has
Σ nSN
((g))²) di + di (2/AA) + (R| 3) dour (LAI + +3)
Alldin
S 0 N (deg maxy? maxg | ymma max ymar gmaz
+ +NAII + (R)( + (maz) ddnar) |Aldin doou
trainable parameters in total.
C Computational complexity
We adopt the same notations as in the previous subsection. Consider the convolution process in parallel flow P in the convolution layer n. HetaFlow applics the convolution filter at most |Vpl times, onco at cach vertex of the flow, where V/l is the number of vertices contained the parallel flow P. For each verlex, hn dot products are computed. Thus, the computational complexity for flow P in the convolution layer n is O(Vp lk* di dmoa). Let | maxp Vpl. The complexity for all parallel flows is bounded by ((((G) | m-max dmaa d ).
Compared with the convolution process, the vertex-level adjustment process requires one extra step to calculate the weights. However, this can be omitted since the dimensions of edge-type embeddings are much smaller than the dimensions of vertex features. Following similar steps in the above discussion, the final complexity of vertex-level adjustments is (p(()) max m. d dmaa))
As for other tasks, the complexities are O(V)d doua) and O(VId deaa) for transformation and prediction part respectively, where layer i the transformation layer and layer p is the prediction layer. Similarly, for path-based adjustments, the complexity is (e after ignoring the extra step of weight calculation, where layer is the layer that outputs features with the highest dimension.
Supposing that di, d'un 2 dr dout and doue the total computational complexity of HetaFlow is given by
d ((((g) (mmxx))))mxxxxmm max aaax gmaz + -Vid d'or)) S
(19)
((R](de max)? 2 mmax k max a d + Middn dout).
25

---

Published in Transactions on Machine Learning Research (10/2024)
Music
anfiicn
Term
Film
Book
Location
Author
Paper
Anthor
Paper
Subject
Actor
Movie
Director
Venue
Person
Sport
(a) ACM
(b) IMDB
(c) DBLP
(d) Freebasc
Figure Network schema of the four datasets.
Implementation details
We employ the Adam optimizer Kingma & Ba 2015 to optimize the model. To find a suitable initial parameter setting, we test multiple initial hyperparameter settings, including: different dimensions of the semantic-level features from 2 to 21; several numbers of the attention head K including {8, 4, 2, 1}; and various dropout rates from 0.4 to 0.85 with step
different numbers of convolution layers from size of 0.15; two learning rates including {0.01, 0.053; two regularization parameters {0.001, 0.00005). We compare with basclines from Lv et al. (2021) and Ahn et al. (2022). For ablation studies, settings in Wang et al. (2019). During the robust test, only part of the training set is available, namely 20%, 40%, 60%, 80%, while the random split of training, validation, and testing sets is fixed. Furthermore, we apply early stopping with a patience of 100.
follow the
E More ablation studies
To validate the effectiveness of each component of our model, we further conduct experiments on several variants of HetaFlow. We test the validity of vertex feature adjustment, the importance of introducing parallel flow docomposition, and the inffuence of different decomposition methods separately.
E.1 Robustness test
We test the robustness of HetaFlow by limiting the size of the training set and following the settings in Wang et al. (2019). The results are shown in Appendix g In general, HetaFlow outperforms the other baselines by 3% and has comparable performance when does not. We believe this due to parallel flow decomposition suffers less information loss than meta-path-baat based reconstruction methods.
E.2 Vertex feature adjustment
We consider additive adjustments and multiplicative adjustments for comparison. For additive adjustments, we perform the following. Equation (5) for our base model uses multiplicative adjustment. For additive adjustment, we generate the type-based weight matrix Aup in the same way as our base model However, equation (5) is then changed as follows:
Σ a [[w] + Amo)hh.]
(20)
BEND
Furthermore, variants of multiplicative adjustment are possible. In our base model, we adjust feal based on the vertex types of the target vertex and its neighboring vertex during convolution, and the edge types of their connection. See [1] and ( This method provides detailed adjustments but has high computational costs. One vertex feature may be assigned with different adjustment weights in two different convolutions on the same subgraph.
26

---

Published in Transactions on Machine Learning Research (10/2024)
Table Quantitative results (%) on vertex classification task with different training splits.
Datasets
Metries Train metapath2vec
GCN
MAGNN
HAN
GTN Simple-HGN
HetaFlow
20%
64.53+0.82 87.20=1.04 87.83+0.76 89.92-0.23 90.43++0.66
90.59++0.75
91.83+0.31
40%
69.08++0.77
87.76=0.93 88.4840062 90.06+0.29 91.12+0.1
91.24+0.62
92.18+0.37
Macro-F1
ACM
60%
70.80:0.78 88.14=0.97
90.03++0.16 89.15=0.26 92.21+:0.50
92.08++..54
92.84+0.38
80%
73.97=0.73
90.34=0.77
91.87:0.76
90.16:0.16
92.81=0.67
92.93++0.58
94.10=0.31
20%
61.6811.14
86.78-1.13
86.8910.90
89.0310.21
90.67110.12
91.13.10.46
91.79.10.37
40%
69.23:10.93
8..43-1.01 87.4310.89 89.6710.18 91.35:10.39
91.65.10.66
92.43310.32
Micro-Fi
60%
71.59+0.92
88.39=1.01 88.31=0.85
89.39=0.17 92.13+0.41
0..3 93.24#0.29
80%
73.88+0.83
89.76=0.85
90.25+0.67
90.28=0.14 92.71+0.27
93.09+0..5
94.04+0.31
20%
89.91+0.88
89.31=0.64
90.56+0.97
90.04+0.29
91.13+0.42
91.04++.23
91.48++0.44
40%
89.71+0.74
90.81=0.68
92.22+0.91
90.92+0.28 92.47+0.56
92.53+0.28
92.90-+0.45
DBLP Macro-F1
60%
90.46+0078 90.87=0.71 92.79-0.766
91.57+0.22 93.73++0.61
93.71++0.99
93.43-1-42
80%
90.43+0.71 91.25=0.66
93.31#0.71
92.16=0.22
93.71+0.47
93.91+
94.37=0034
20%
88.62:1112
88.44-0.81
90.9011.05
90.5810.25
91.42.1.45
90.4011.221
91.52.10.29
40%
89.8911.011
89.21-0.76
91.8110.95
91.2710.18 92.18.1.37
91.9610.28
92.15.10.30
Micro-F1
60%
90.35+1.03
90.80=0.56 93.03+0.81
91.94=0.18 93.4240.58
03.03##.26
94.43++0.27
80%
90.61+0.61
91.06=0.66 73.88+0.76
92.18+0.12 93.81+0.64
93.82+0.28
94.27+0033
20%
40.74+1.00
44.85=1.15
49.6841.14
51.10#1.19 51.1341.13
51.59+0.98
52.28+1.22
40%
04.47+0.76
47.86=1.03
52.11+1.01
52.08+1.21 52.43+1.21
53.17++.05
53.89+
Macro-F1
IMDB
60%
01.24+0.67
49.07=0.71
53.96++087
54.08+1.18 54.61+1.18
55.44++1.26
56.38+11.16
80%
45.56+0.70
51.93=0.64
55.291:074
55.57=1.17 55.40+1.116
56.85+1.22
59.42+11.08
20%
15.47:10.94
50.26=0.88
51.68.10.66
55.91
57.41
55.63
16.12.11.26
40%
48.0 18.05:10.89
51.88-0084
56.25110.71
57.4911.29
58.18.1..22
58.8111..16
59.12.11.1
Micro-F1
60%
48. 48.8640.78 51.76=0.83 55.94+0.68 58.37+1.28
58.86+1.22
59.60+1.21
11.11+1.26
80%
48.86+0.78 55.08=0.68 56.46+0.66 58.94+1.24 59.11+1.224
60.85+1.22 62.39+1.18
Another variant of multiplicative adjustment is to conduct adjustments according to the type of vertex be adjusted and the edge types the subgraph to be worked on, which mcans one vertex shares the same adjustment weights on one subgraph. For this method, the equation
1 is changed as follows:
Z.P = Tw Tp,
(21)
where Tp is the one-hot encoding of the edge type of parallel flow P. This adjustment method can be performed before the convolution operation. The equations and are replaced by:
Aup σ (W,Z, + bb),
hpp h ④ Aup,
(22)
h Σ (w hhpp))
WEN!
This method results in notable computational cost reduction. For instance, consider the example shown in Fig. 2 Vertex en needs four adjustment weights for the base model but requires only one adjustment weight for this second approach. However, the second approach provides less detailed adjustments than our base model.
We report the results obtained from the three datasets on vertex classification in Table 10 Each score (i.e., either Macro-F1 or Micro-F1) is an average of the scores in different training proportions. Here HetaFlowbass is our base model, i.c., the one used to compete with other baselines in Appendix and Table 0 Let HetaFlow be the variant model without utilizing vertex feature adjustments; HetaFlownow now be the variant that follows (11 and (22), which performs flow-based multiplicative adjustments; and HetaFlowadd be the model that uses the additive adjustment in (20h. All other settings are the same for these variants of HetaFlow.
From Table 10 we observe that in most cases, adjustments used in our base model yield the best outputs, whereas flow-based multiplicative adjustment has the second-best performance. The gap between these two
27

---

Published in Transactions on Machine Learning Research (10/2024)
Table 10: Quantitative results (%) for different adjustment methods HetaFlow.
Datasets
Score
wo
add
flow
base
Macro-F1
90.10
88.14
91.23
91.79
ACM
Micro-F1
90.31
88.27
91.44
91.85
Macro-F1
92.86
91.64
93.81
94.41
DBLP
Micro-Pi Fl
93.65
91.99
94.12
94.72
Macro-Fi
52.80
50.22
53.76
53.85
IMDB
Micro-Fi F1
57.69
55.91
58.39
58.17
methods is however small. The additive adjustment approach is inferior the multiplicative adjustments. Together with the variant without vertex feature adjustment, these produce the worst performances.
F Drop Token Examples
Though the number of filters in HetaFlow does not scale with the size of the graph, the heterogeneity of graph affects the number of parallel flows required. Since each parallel flow requires a separate filter, we may need to discard some edges to decrease the parallel flow number. We may need to make a trade-off between the number parallel flows and the number of omitted edges.
U4
Ug V10 V11
Figure 9: An example molecule graph. Different colors for edges indicate different types.
For example, consider the heterogeneous molecule graph shown in Fig. g which has one type of vertices and two types of edges. Assume that twelve black edges in this graph belong edge type while the red edge connecting vp and v7 belong to edge lype 2. To contain all edges in the parallel flow decomposition, we will need two parallel flows. One parallel flow contains the path Pi (es, 07) while the other consists of two paths Pg (#1, 12, l6,, v10, uo, Us. 01) and P3 (Vz, Ug U12 U11, #7, vi)). However, if we discard the type 2 edge, then we only need one parallel flow. This means that by discarding the edge (va, 07), we reduce the size of our model almost by half while only losing 7.7% of the edges. Research on methods that choose the edges to discarded part of our future work.
HetaFlow's convolution filter assigns various weights to the neighbor vertices based the position relationships between them and the central vertex. On the other hand, if one chooses the graph adjacency Laplacian matrix as the graph shift operator for GCN, then common weight is shared by the neighbors with the same distance to the central vertex. In this regard, HetaFlow is much closer to CNN, which means it may benefit. from techniques developed for CNNs. Our future work includes investigations into this observation.
28


Reviews:
[{"review_id": "jOBTmZBDno", "reviewer": "Reviewer_dAfN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I like the ideas behind the approach, although I do not have the expertise to judge the novelty. The design of the model seems decent, and the experiments are also decent, showing significant performance increases on the baselines (although with increased complexity). \n\nWeaknesses: The explanation of the method is fairly difficult to follow and quite long. It could use a restructuring. The paper compares in the introduction to meta-path-based methods, but the arguments made here are not convincingly supported by evidence in the paper. The paper primarily compares to heterogeneous GNN methods from before 2020, if I understand correctly. I do not have the expertise to judge if these baselines are strong (enough).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study learning on heterogeneous graphs consisting of varied types of nodes. To deal with heterogeneity, the authors create a decomposition of the graph into paths following a particular edge type (called a parallel flow decomposition). Then, the model (HetaFlow) implements a convolution and attention within each path, and then between the different paths.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major\n- (Critical) The introduction spends a significant amount of time comparing the method to meta-path-based methods, but this comparison is not made as clearly in the paper. I think there is a major theoretic result in 4.1.1, but this was difficult to follow because it was introduced before the method was introduced. Furthermore, it does not directly relate to the points made in the introduction, leaving the reader to infer what exactly this proposition implies. It should be moved until after\n- (Critical) Similarly, the paper claims that meta-path-based methods are not scalable and that Hetaflow addresses this challnge, but no comparison on scalability is performed empirically. The authors claim in the limitations that the memory use of HetaFlow is higher (which makes sense, as it has separate weights for each parallel flow). Although future directions for scalability are proposed, this claim could use more support by showing runtime and memory usage for both, and showing how many parallel flows and paths are used in each dataset.\n- (Strengthen) Additionally, scalability is further shown by using a dataset that is an order of a magnitude larger and comparing runtimes/memory usage.\n- (Critical) The related work compares HetaFlow to Simple-HGN by saying that it has over-smoothing and limited receptive field. However, it is not argued why HetaFlow overcomes these issues. In general, I'm surprised why meta-path-based methods are singled out in the introduction, even though Simple-HGN seems to be performing best among the baselines, and further comparison could help convince the reader.\n- (Critical) Section 4 could use a restructure. Start with a high level overview of the method before diving into details. Section 4.1.1 should come after the method is introduced: The proposition mentions 'HetaFlow model', but this concept is not yet defined. This section also needs more high-level explanation: Why is a polynomial better? And isn't $M+2\\sum_i^ M\\sum_j^ N k_{ij}$ a massive number of layers, suggesting this result is not as powerful? \n- (Strengthen) A pseudoalgorithm figure could greatly help to understand the total computation. \n\n\nMinor\n- (Critical) It is unclear if the authors assume there is at most 1 edge between each pair of nodes\n- (Critical) Section 4.1.2: It is not clear how edges in the tree are labelled with a number. I don't think there's a unique way to do this, so it should be mentioned.\n- (Critical) Section 4.3: It wasn't clear to me if there's a weight $w_u^ P$ for every node, or if it is just unique to each parallel flow. \n- (Critical) What is the activation function $\\sigma$?\n- (Critical) Motivate why intra-flow aggregation uses 'Bahdanau attention' with concatenation while inter-flow aggregation uses the (currently more standard) dot-product attention.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9DZqrVH6IQ", "reviewer": "Reviewer_QmFN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- The authors provide the codes of the work, facilitating good reproducibility.\n- The experiments are extensive and the results are promising.\n- The concept of parallel flow defined in this work is interesting.\n\nWeaknesses\n\n- The major concern of this work is that the motivation of this work is fragile. There exist HGNN methods that do not require meta-paths, e.g., [1,2,3]. In particular, the previous HGNN method [3] has been proven to be able to automatically discover and exploit useful meta-paths from all possible ones. These works should be discussed in the text, and the difference and the connection between them and the proposed work should be analyzed.\n- I am confused about why propose the new local structure of parallel flow.\n- The sentence below Definition 3 seems to be incomplete.\n\n\nRefs:\n\n[1] [WWW 2020] [HGT] Heterogeneous Graph Transformer\n\n[2] [AAAI 2020] [HetSANN] An Attention-based Graph Neural Network for Heterogeneous Structural Learning\n\n[3] [TKDE 2021] [ie-HGCN] Interpretable and Efficient Heterogeneous Graph Convolutional Network", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission contributes a new heterogeneous graph neural network (HGNN) method to address the limitation that previous HGNN methods require meta-paths.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors are suggested to enhance the motivation by investigating more existing HGNN methods that do not require meta-paths [1,2,3], especially the work that can automatically search meta-paths [3]. This is critical to securing my recommendation.", "broader_impact_concerns": "I did not identify any concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5ihM6HIj45", "reviewer": "Reviewer_TKc7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Figure 1 is informative in describing the problem setting of heterogenous graphs and Introduction section summarizes the research work’s contributions comprehensively. \n\nThis work is missing references to an important state-of-the-art GNN model that outperforms HAN without using metapaths. This work should reference that model in the “Related Work” section for recency and relevance:\n\"Bi-Level Attention Graph Neural Networks,\" in 2021 IEEE International Conference on Data Mining (ICDM), Auckland, New Zealand, 2021 pp. 1126-1131. doi: 10.1109/ICDM51629.2021.00133\n\nSection 3 is well-written and useful for understanding background on notation. \n\nIn Section 4, the authors describe the components of their model architecture, however novelty of the work seems to be limited. Specifically, the attention mechanism used seems to be highly similar to GAT based attention and Transformer based attention. Works like HAN already learn attention at both node and edge (relation) level. The authors need to more clearly explain what the novelty of their work is compared to the existing state-of-the-art. \n\nI also have a concern that the size of the dataset being evaluated is small-scale (limited to thousands of nodes), when there are several large-scale datasets (RDF) that contain millions of nodes. Can the authors also evaluate on these datasets and provide a section on the memory and runtime complexity of the model?\n\nExperiment results achieve good performance and the authors have identified limitations and future directions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes Heterogeneous graph adaptive flow network (HetaFlow), which removes the need for meta-paths. HetaFlow decomposes the heterogeneous graph into flows and performs convolution across heterogeneous vertex and edge types, using an adaptation to change the vertex features based on the corresponding vertex and edge types during aggregation. Authors perform experiments for vertex clustering and vertex classification and release their source code for reproducibility.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the above section.", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the task of vertex clustering and classification in heterogenous graphs. It proposes a decomposition of heterogeneous graphs into a set of paths called flows. Each flow contains homogeneous edges and potentially heterogeneous vertices. These are processed in parallel, aggregating information within each path, and between paths.

The approach is computationally efficient, albeit at a higher memory cost. Its performance on benchmark datasets meets or exceeds meta-path based approaches and other approaches.

The reviewers had some concerns around the structure of the paper, missed references, comparison to non-meta-path-based approaches, additional complexity analysis and comparison, lack of large-scale benchmarks, and distinguishing the novelty of the approach from GAT networks. These were all addressed in the revision. There was a minor comment from one of the reviewers about oversmoothing, but that is orthogonal to this work and not mentioned as one of the claims in the paper.

Minor comments:
- One minor request is that the bold numbers in the tables only correspond to the highest mean, whereas if two numbers are within standard error then I think that they should both be bolded.

- The responses on OpenReview include timing information (per epoch), but these are absent from the current version of the paper. I think that including these would be informative.
Decision: Accept (poster)