This work provides the first unifying theoretical framework for node (positional) embeddings and structural graph representations, bridging methods like matrix factorization and graph neural networks. Using invariant theory, we show that the relationship between structural representations and node embeddings is analogous to that of a distribution and its samples. We prove that all tasks that can be performed by node embeddings can also be performed by structural representations and vice-versa. We also show that the concept of transductive and inductive learning is unrelated to node embeddings and graph representations, clearing another source of confusion in the literature. Finally, we introduce new practical guidelines to generating and using node embeddings, which fixes significant shortcomings of standard operating procedures used today.
This paper tries to clarify some confounding concepts around graph/node representation learning by providing a unifying theoretical framework based on invariant theory. The authors define node embedding and structural graph representation based on a minimal number of requirements, which is, in turn, used to derive some useful properties and unify two seemly different concepts. Based on these, a new graph neural network framework is proposed. The experiments on multiple tasks with multiple datasets validate the main claim that a single node embedding is insufficient to capture the structural representation of a graph.
Overall, this paper tries to suggest a solution to a somewhat confusing and controversial problem that everyone recognises but hard to figure out a clear resolution. In that sense, this paper would serve as a good starting point by providing some theoretical baselines. I would like to see more discussion on this topic in future.
In many graph problems where each node is endowed with a certain feature set, we often observe the case where two subsets of nodes are isomorphic in terms of link structure but with different edge of node features. It would be good if there are some discussions on these cases.
Here's a minor comment on the representation of the paper. Although the concept of node embedding and structural representations get clearer as reading, the introduction, where I couldn't find any reference of these, seems unlikely to clarify the difference between these two concepts. The familiar representation in Section 3 might be the first part where the readers could get some intuition about their differences.