Stable GNN Embeddings for Relational Data

...paper 2-folded..loosely related..parts read like separate papers

Our objective was to establish the applicability of embeddings derived from relational databases for downstream tasks and for direct latent space querying. Achieving this 2-fold objective is a substantial step forward. Stability, which guarantees the robustness of embeddings against database updates, is therefore fundamental to the construction of robust vector databases. We will strengthen the paper's coherence by explicitly highlighting the crucial link between these objectives. We have further emphasized this relationship in Sec 5 of the revised rebuttal.

limited scope of datasets..additional baselines, heterophilic datasets[1]..the new relational database benchmark[2]

Our work centered on exploring methods for generating stable graph-based embeddings for relational databases. We believe the datasets we employed are representative enough to demonstrate that db-to-graph transformations can yield stable embeddings. It's important to note that TPC-E is a widely recognized and comprehensive benchmark for relational databases; we leveraged it to build our datasets.

Results affected if applied on standard heterophilic graph datasets[1]

They would not be affected, our theoretical results remain valid for any graph, when used with SPGNNs

Results applicable to link prediction?

Indeed, our stability results show that the performance of downstream tasks (including link prediction) on the original graph remains robust to perturbations

Why Th2 can be applied to higher-degree polynomial as filter/non-linearity?

Thank you for this question. The statement was clarified in the revised pdf, including the precise bound that applies to any-degree SPGNNs. The crux to deal with non-linearity is that a high-degree polynomial can be unfolded as a sequence of 1-degree ones: $a_n X^n+a_{n-1} X^{n-1}+...+a_1X+a_0 = (...((a_n X+a_{n-1})X+a_{n-2})X+...+a_1)X+a_0$. So we can represent a SPGNN$\Psi$ using filters of any degree as an SPGNN$\Phi$ using 1-degree polynomials, so with a higher number of parameters. In addition to the formal definition, in Sec.A.4.1, we added Fig 4 to detail this transformation $\Psi$ to $\Phi$.

Th2: shift operators must be symmetric: is this unrealistic...edges are typically directed in relational databases, shift operators not symmetric?

Please note that all db-to-graph transformations we investigate (existing or ours) yield undirected graphs, and our results hold for these constructions. For completeness, we have now included a formal statement for directed graphs (Sec A.4.2).

Why db-to-graph transformation?

A significant body of literature, e.g. [3-5], demonstrates the effectiveness of graph-based models for downstream tasks on tabular data. Graphs can provide a natural representation of relational databases, preserving essential logical properties like isomorphism, query closure, foreign key constraints.

...theoretical upper-bound is up to 8 orders of magnitude larger than the empirical average distance, are bounds of any use?

While the theoretical bound on stability is a worst-case one, the average case (after Corollary 2.1) exhibits significantly better stability. This aligns with previous research on stability [6], which also observed a gap theoretical bounds vs practical performance. As theoretical bounds often rely on conservative assumptions, experimental validation is crucial. Despite the bound's looseness, our theoretical work gives 2 valuable insights: (i) the bound's form identifies key stability parameters, enabling the design of more stable graph constructions, (ii) the Lipschitz-like bound - novel contribution - which addresses a fundamental, natural question in stability theory.

...other models, Graph Transformers/GAT?

Although spectral GNNs have been subject to some theoretical analysis [7], a comprehensive investigation of other GNN models was beyond the scope of this work

...distinguish stability from over-smoothing...experiments with very few layers

We conducted stability experiments (paragraph Oversmoothing, Appendix B) using the same graphs from the appendix, but with a 2-layer SPGNN instead of the original one. They lead to very similar results (Fig.10-11), at slightly different scales

[1] PLATONOV et al A critical look at the evaluation of GNNs under heterophily: Are we really making progress?arXiv 2023

[2]ROBINSON et al Relbench:A benchmark for deep learning on relational databases.arXiv2024

[3]FEY et al Relational deep learning: Graph representation learning on relational databases.arXiv2023

[4]CAPPUZZO et al Creating embeddings of heterogeneous relational datasets for data integration tasks.SIGMOD20

[5]SCHLICHTKRULL et al Modeling relational data with graph convolutional networks.ESWC18

[6]GAMA et al Stability properties of graph neural networks.Signal Processing2020

[7]HUANG et al On the stability of expressive positional encodings for graph neural networks.arXiv2023

Dear Reviewer,

We hope we have adequately addressed all the points raised in your review. We remain open to further discussion on any remaining concerns before the discussion period concludes.

Sincerely, The Authors

In Introduction ... you mention that current database-to-graph construction methods often result in overly heterogeneous structures. However, it’s unclear why this is problematic... justification.

We regret any confusion caused by our previous statement. We aim to avoid or minimize heterophily in graphs derived from relational databases, which are inherently heterogeneous (with several types of nodes), since this characteristic can hinder the effectiveness of GNNs (e.g., as discussed in the three references below). In contrast, existing approaches, such as the tripartite graph construction EmBDi, typically yield heterophilic graphs, hence with both properties (heterogeneous and heterophilic) simultaneously. The revised pdf addresses this discrepancy.

Jiong Zhu et al.Graph neural networks with heterophily.AAAI21.

Dongxiao He et al.Block modeling-guided graph convolutional neural networks.AAAI22.

Tao Wang et al.Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily.AAAI22.

... you mention approaches that use LLMs to generate embeddings from databases but don’t cite them or discuss their limitations. Please elaborate...

We would like to stress here the importance of GNNs and GNN embeddings for database applications, supported by the rich line of recent research that directly applies GNNs to databases for various downstream tasks. Our theoretical and experimental findings contribute to this field. While other embedding methods are available, GNNs provide a strong theoretical foundation and are significantly more efficient and economical than LLMs.

In Sec 5, clarify why you describe the first two database-to-graph transformation methods as heterophilic? They seem more accurately described as heterogeneous rather than heterophilic.

We will clarify next why heterophilic is the right term here. The term heterogeneous graphs refers to graphs which have different types / semantics attached to their nodes. For example, in our relational-to-graph transformations, these types can represent tuples, attributes, values, relations, or tuple-value pairs.

The term heterophilic graphs refers to heterogeneous graphs where nodes of different types are more likely to be connected. For example, in bipartite (or multi-partite) graphs constructed from relational databases using existing approaches (e.g., [8]), a node connects only to others having a different type.

Additionally, you mention that these methods fail to capture the underlying structure of the database ... expand reasoning

Graphs derived from databases that do not fully capture the underlying database structure can drastically affect the performance of downstream tasks. For one example, the EmBDi (tripartite) graph cannot differentiate between two distinct tuples that happen to involve the same values (e.g., FirstName: John, LastName: Oliver vs. FirstName: Oliver, LastName: John).

In Sec 5, Perturbations, you suggest two strategies for handling size mismatches in shift operators. In the second, you propose keeping deleted nodes but removing their connections to maintain node count... what about when tuples are added ?

Please note that the case of tuple addition is symmetric to the one of tuple removal: adding a tuple to a database instance $D$ to obtain an instance $D'$ is the exact opposite operation of removing the added tuple from $D'$ to obtain $D$. As required, the perturbation metric must be symmetric in the two input databases. Therefore, these two operations present no conceptual differences and without loss of generality we did not discuss further the case of tuple addition. We have clarified this point in the revised version of the paper.

In relational databases, nodes are often both added and removed ... Could you show both additions and removals simultaneously?

We added in the appendix new experiments where both tuple deletions and additions occur (Fig. 15-17). The results show that embeddings remain stable even under both kinds of modifications.

There is a recent benchmark [1] that proposes a way of constructing graphs from relational databases that you don’t compare with.

[1] Robinson et al. Relbench: A benchmark for deep learning on relational databases. arXiv 2024.

Thank you for pointing out this recent paper, released around the time of our submission. Indeed, all the datasets presented there can be used within our stability framework. For databases that are temporal, we could apply our framework to specific snapshots thereof.

Since treating a relational database as a homogeneous graph is not very convincing, it would be interesting to compare relational GNN approaches with your model when considering databases as heterogeneous.

We stress that the database graphs we consider are not homogeneous. Database graphs obtained using our transformations are all heterogeneous. This has been clarified further in the revised version of the paper.

Thank you for engaging in the discussion during this rebuttal phase and for the additional requests for clarifications.

1. Heterogeneous and heterophilic are not the same. A graph can be heterogeneous yet exhibit high homophily...

It seems that we do not use the same definition for heterogeneous graphs. In our work, as indicated in the paper and in the rebuttal, we used the term heterogeneous for graphs having different types of nodes, but only one type of edges.

2. Can you demonstrate that GNN methods are more efficient and cost-effective than LLMs...

This statement deserves a more detailed justification, indeed. In terms of both data size and model size, it is generally accepted that LLMs are much more expensive to train, maintain, or adapt to different application contexts. LLMs often have billions of parameters, requiring substantial computational resources for training; they require massive datasets, often in the terabytes or even petabytes range, to learn complex language patterns. GNNs typically have fewer parameters, especially when compared to large LLMs, making them less computationally intensive; they can be trained on smaller datasets, especially for domain-specific tasks, reducing data acquisition and preprocessing costs, as discussed in the recent survey below.

Ren et al. A Survey of Large Language Models for Graphs.KDD24

3. The phrase "The term heterophilic graphs..." seems to imply that heterogeneous graphs are inherently heterophilic...

Please note that our statement does not at all mean that all heterogeneous graphs are automatically heterophilic. The phrase "where nodes of different types are more likely to be connected" is essential to understanding our meaning: a graph needs to heterogeneous AND have a high probability of connections between nodes of different types in order to be heterophilic.

5. ...on node addition/removal...addition is different...

As previously mentioned, we do not see node addition and node deletion as distinct issues, neither in the theory nor in the implementation. Here is how we proceed for additions: let us consider a graph $\mathcal{G}$ and its shift operator $\mathbf{S}$, as well as a graph $\hat{\mathcal{G}}$ with its shift operator $\hat{\mathbf{S}}$, such that $\hat{\mathcal{G}}$ is obtained from $\mathcal{G}$ by adding one node $n$ along with edges connecting it to other nodes. We need to identify the integer $i$ such that the $i$-th row/column of $\hat{\mathbf{S}}$ corresponds to the edges of $n$. Then, we would add a row/column of 0s in $\mathbf{S}$ at the $i$-th position, so that it matches the shape of $\hat{\mathbf{S}}$ (this is conceptually as if $n$ was already in $\mathcal{G}$, but unconnected to the rest of the graph). We would use this new matrix $\mathbf{S}$ to compare the embeddings of nodes in both graphs. Deletion amounts to the symetrical construction. When we consider a chain of additions/deletions, we simply iterate such constructions.

While it is true that we do not know in advance the final number of nodes, following additions, we always compute the bound after all the modifications are made, at the end of the process. This means that when we compute the bound, we indeed have access to the set of added / deleted nodes, as in the case where we only consider node deletions. Hence there is no specific difficulty on this aspect.

7. The paper I cited was accepted around June-July, a couple of months before the deadline. Since it includes some datasets, it would have been beneficial to include a few experiments using them

The paper was indeed uploaded to arXiv on July 29th; we are currently unaware of its official acceptance date. We are of course open to incorporating additional datasets into our experimental framework, in a revised version. We do believe that the datasets we currently use are sufficiently representative to demonstrate the stability of embeddings generated through db-to-graph transformations. Our experiments encompass a variety of graph types, including citation networks and graphs derived from relational databases. These databases span diverse domains, from industry-standard benchmarks like TPC-E to specialized fields such as medicine and geography. Furthermore, our experiments cover both homogeneous (citation networks) and heterogeneous datasets.

8. There is extensive literature on using Heterogeneous GNNs for heterogeneous graphs...include such methods in your experiments

As mentioned in our answer to (1), it seems that we do not use the same definition for heterogeneous graphs. The methods you cite focus on heterogeneous graphs with directed labeled edges. Our work applies to graphs where the edges are non labeled, which are still heterogeneous according to the definition used in our paper. The extension of our work to more specific classes of GNNs, including Heterogeneous GNNs, is indeed very interesting for future work, but it is out of the scope of this paper.

We wish to emphasize that the proposed graph databases are designed to precisely replicate the structure and logical relationships found in the original relational databases they represent. This structural and logical similarity is a key factor in generating meaningful embeddings.

Unfortunately, HGCNs often perform poorly in capturing the overall graph structure when meta-paths (paths capturing interactions between nodes of different types via directed edges) are automatically determined [4-6] (i.e., not pre-specified by users [1-3]). To avoid this known and well-documented limitation of HGCNs, we prioritize in this work classical GNNs, which are more effective in extracting both local and global information from the graph while maintaining computational efficiency [7].

Please note as well that a substantial body of literature exists on GNNs for graphs lacking edge labels -- especially those that are not RDF-like or RDF-compatible -- and is continuously enriched by new studies. This literature remains relevant and is in no way superseded by research on heterogeneous GNNs.

Furthermore, we wish to bring to your kind attention a key aspect of our work: the concept of stability is fundamental to the robust performance of ANY neural model including GNNs, regardless of the type, viz., homogenous or heterogeneous (whether heterophilic or not). One can certainly make comparative evaluations with all types of GNNs, but these comparisons are necessarily empirical. The importance of stability is theoretical and fundamental and it plays a central role in our work. Unfortunately this does not seem to be recognized either in the review or in the rebuttal discussion. In our paper, we have chosen to use GNNs applied to graphs obtained from transformations to relational databases to showcase the importance of stability. We ask that you kindly take this into account.

[1] WANG, Xiao, JI, Houye, SHI, Chuan, et al. Heterogeneous graph attention network. WWW 2019

[2] ZHOU, Sheng, BU, Jiajun, WANG, Xin, et al. HAHE: Hierarchical attentive heterogeneous information network embedding. arXiv preprint arXiv:1902.01475, 2019.

[3] WANG, Shen, CHEN, Zhengzhang, LI, Ding, et al. Attentional heterogeneous graph neural network: Application to program reidentification. In SIAM SDM 2019

[4] ZHANG, Yizhou, XIONG, Yun, KONG, Xiangnan, et al. Deep collective classification in heterogeneous information networks. In WWW 2018

[5] CHEN, Xia, YU, Guoxian, WANG, Jun, et al. ActiveHNE: Active heterogeneous network embedding. arXiv preprint arXiv:1905.05659, 2019.

[6] ZHANG, Chuxu, SONG, Dongjin, HUANG, Chao, et al. Heterogeneous graph neural network. In KDD 2019

[7] YANG, Yaming, GUAN, Ziyu, LI, Jianxin, et al. Interpretable and efficient heterogeneous graph convolutional network. IEEE TKDE 2021

The empirical results on relational databases need scaffolding with a signal from a machine learning task, e.g., predicting missing edges, tuple classification, etc., to place the observed stability into context. While stability in itself is valuable, it's important that this pairs with robust model performance. This is somewhat covered in the Cora experiment through accuracy, but not done in the TPC-E setting. I strongly recommend the authors add a task dimension to complement their existing study. This would also add more information about the merits of the corresponding relational database graph encoding schemes.

Thank you for the suggestion. This paper primarily focuses on database-to-graph constructions and the stability of resulting embeddings in the face of incomplete or perturbed data. While we acknowledge the importance of other downstream tasks, such as tuple classification, missing value imputation, or entity resolution, a comprehensive evaluation of these tasks was beyond the scope of this work.

I find that the experimental analysis could be better served with more detailed explanations of how the bounds apply on a smaller synthetic task, i.e., a case study. As it stands, the TPC-E experiment demonstrates a substantial difference (roughly 6 orders of magnitude) between observed and theoretical stability, with not much discussion accompanying this observation. It just leaves it harder to make the connection between the experiments and the theoretical contribution. The authors, to their credit, acknowledge that their node-level bounds are less intuitive, and so adding some experiments that are more fundamental and small-scale, i.e., toy experiments, to illustrate the bounds in action would be a very insightful addition to the work.

Thank you for the insightful suggestion. Theoretical bounds are often loose in practice, as they typically consider worst-case scenarios. This is evident in Corollary 2.1, where the average-case bound is significantly tighter. Our new experiments on sequential data modifications (additions and removals), in Appendix, Figures 15-17, further corroborate this finding, revealing stability measures that align more closely with this theoretical bound (within one order of magnitude).

I thank the authors for their rebuttal. I understand your points on scope and on my theoretical suggestion. All in all, I will maintain my rating.

The selected graph datasets are limited to a single domain (citation networks) and type (highly homogeneous graphs). This may restrict the generalizability of the method to other scenarios, such as heterogeneous graph datasets from HGB [1].

Please note that while our first experimental stage uses citation network graphs, our second (and primary) experimental investigation involves graphs obtained from relational databases. These databases cover a wide range, from the industry-standard TPC-E benchmark to specialized domains such as medical and geographical data. Therefore, our experiments do cover both homogeneous (citation networks) and heterogeneous datasets. For the latter, we recall the type of graphs that are obtained from a relational database through graph transformations. For instance, the 5-DB relational-to-graph transformation produces a heterogeneous graph with 5 different node types (Relation names, AT, Tuple, Attribute names, Values) and 4 edge types (R-T, T-AT, AT-A, AT-V).

Many large relational datasets are temporal, so predictions must follow causal constraints. This means future events cannot be used when making predictions. To handle this, temporal sampling is often necessary within GNNs. It is important to consider whether this method can work well in a temporal setting. Specifically, when predicting for a node, different nodes and time embeddings may be included in the sampled subgraph due to varying time constraints. How would these modifications affect stability?

Thank you for this question. First, please note that stability is a desirable property of embeddings, regardless of whether they are obtained from static data or temporal, evolving data. Most databases today remain relational and primarily focus on the current state (aka snapshot) of the data, rather than its historical evolution or future state predictions. While interest in temporal and time-series databases is growing, traditional relational databases still dominate the market by far. While we haven't explored the temporal aspect of relational databases in this work, we believe that understanding the resilience of embeddings to incomplete data is crucial. Tasks like missing value imputation and tuple classification rely heavily on stable embeddings. As missing data increases, unstable embeddings can significantly impact downstream accuracy (see [1]).

Investigating the stability of embeddings in a temporal database is certainly a promising avenue for future research.

[1] SCHUMACHER et al. The effects of randomness on the stability of node embeddings. ECML/PKDD 2021