Homogeneous vs. Heterogeneous Graphs

So far, we have been implicitly working with homogeneous graphs, where all the nodes in the graph and all the edges in the graph are of the same type. For example, a social network is a homogeneous graph, where nodes represent humans and edges represent relationships. However, we can also construct heterogeneous graphs, where nodesand edges are of different types.

The above is an example of a heterogeneous directed graph, where we have author nodes, institution nodes, paper nodes, and field of study nodes, connected by edges indicating "writes," "cites," "affiliated with," and "has topic." Bipartite graphs are a kind of heterogeneous graph with two different types of nodes, which are often used in recommender systems predicting whether a user would like a specific item (which I might cover in the future). We can ignore the type differences or use node and edge embeddings to express the differences in some way to treat the heterogeneous graphs as homogeneous graphs, but the model will be more expressive when it accounts for such type differences among nodes and edges.

Relational GNNs

The easiest way to distinguish nodes and edges of different types is to stack multiple GNN layers for each edge type, aggregate the results, and make it a single layer. For example, R-GCN by Schlichtkrull, M. et al. (2017) has the following layer:

Here, $R$ is the set of all types of edges in a graph, and $c_{i,r}$ can either be the degree or a learnable parameter. One noticeable problem with the above approach is the increase in the number of parameters, especially with highly multi-relational data. Hence, Schlichtkrull, M. et al. (2017) use basis decomposition, $W_r = \sum_{b}^B a_{r,b}V_b$, where the value of $b$ is smaller than $r$, allowing the relationships to share a basis and reduce relation-specific weights (block decomposition too).

You can imagine doing the same thing for other layers built for homogeneous graphs or using different layers with different complexities depending on the relationships. Graph Transformers are also promising, as they can easily support heterogeneous graphs by preparing appropriate embeddings and encodings. For TokenGT, as an instance, we can prepare different node and edge embeddings for different types as well as appropriate type identifiers.

GNN APIs

So far, we have been working with TensorFlow (or PyTorch) without standard ways of preparing datasets. It is manageable to do so for homogeneous graphs, but it becomes intractable for heterogeneous graphs. Hence, we can move on and start using GNN APIs provided by TensorFlow and PyTorch to standardize GNN pipelines, which allows us to make use of predefined data formats and even models. The following covers the basics of GNN APIs for TensorFlow and PyTorch.　(Click to open)

Both frameworks handle multiple types of nodes and edges using dictionaries and manage edges using edge indices that specify the source and target indices. Both frameworks also provide predefined models. In my opinion, the documentation and interface of PyG are much easier to read and interact with, so I recommend using PyG unless there are specific technical requirements that necessitate another framework.

Conclusion

We covered a new type of graph: heterogeneous graphs, relational GNNs for heterogeneous graphs, and GNN APIs that allow efficient handling of both homogeneous and heterogeneous graphs. In the next article, we will finally discuss the overall GNN pipeline, including the downstream tasks and the meanings of transductive and inductive learning in the context of graph learning.

Resources

• PyTorch. 2024. PyG Documentation. PyTorch.
• Schlichtrull, M. et al. 2017. Modeling Relational Data with Graph Convolutional Networks. ArXiv.
• TensorFlow. 2024. TF-GNN: TensorFlow Graph Neural Networks. GitHub.