Stable GNN Embeddings for Relational Data

Authors: Alan Gany, Paul Landrier, Bogdan Cautis, Laks V. S. Lakshmanan, Silviu Maniu
Primary area: learning on graphs and other geometries & topologies
Keywords: GNN, stability, database embeddings

Abstract:
Graph neural networks (GNNs) are a valuable tool for extracting meaningful representations from graph-structured data. Graphs, like relational databases, represent relationships between entities. Recent research has explored the potential of using GNNs for downstream tasks on relational data, such as entity resolution and missing value imputation. However, applying GNNs to relational databases presents two challenges. The first challenge is data conversion: relational databases, organized as tables connected by key / foreign key constraints,
must be transformed into graphs without losing essential information. The second challenge is ensuring that the embedding technique can adapt to the dynamic nature of databases. When a database is updated, the embeddings of the resulting database should be recomputable efficiently. This requires that previously computed embeddings remain stable despite changes to the data.

Motivated by using GNNs for relational databases, we study stability, i.e., how much the embeddings generated by a GNN change when the input graph undergoes modifications. Building upon the work of Gama et al. (2020), which established a limit for the distance between embeddings of similar graphs, we focus on node-level stability for GNN embeddings, particularly when the graphs originate from relations. We propose several techniques for transforming relational databases into graphs. To assess the effectiveness of these methods, we conduct experiments using the TPC-E database benchmark and analyze their stability.

Decision: reject
Reviewer scores: 6, 5, 3, 6

Reviews and discussion:
<thread>
creation date:
1730597272203

thread_type:
official_review

<thread_object>
creator: reviewer_ffdv

<content>
summary:
The paper studies the stability, i.e., minimal variation under perturbation, of node embeddings for relational databases under common database operation (e.g., value or node deletions). To this end, the paper builds on previous work from Lama et al. using the Signal Processing Graph Neural Network (SPGNN) model, and derives extended results. In particular, the paper proves a new stability bound that crucially does not depend on the number of nodes in the input graph. The paper then derives results based on individual node embeddings, first showing how the general bound in Theorem 2 leads to an asymptotic stability bound on at least half the nodes, subject to SPGNN instantiations where graph shift operations (GSOs) have eigenvalues that do not increase with the number of nodes $N$. The paper then provides an individual node-level bound based on the notion of $k-$hop equality, showing that nodes with more similar subgraphs across perturbations tend to remain more closely embedded. The paper also discusses the operations can be studied within this framework (tuple and value removal), and how these can be reflected in the GSO comparison.

Empirically, the paper conducts experiments on Cora, showing that a 1st-order SPGNN (as is specified in the Theorem 2 result) better maintains its accuracy (only when re-trained) than standard GNN baselines on subsets of Cora following node removals, and shows that node degrees have a minor, but not problematic effect of node embedding stability.  Finally, the paper discusses and empirically compares different relational database graph encoding techniques on a subset of the TPC-E dataset, including their own proposed 5-DB encoding, showing that their encoding is more resilient for tuple removal, but that denser encodings (at the value) like Tuple+Clique are more resilient in the value removal context.

strengths:
- The theoretical results are interesting, and appear sound (although I must admit that I did not check these in detail).
- The empirical setup comparing different encodings on TPC-E is informative, and the tasks being studied are a useful baseline for this area of research.
- The discussion of the results, and the overall flow of the paper, is easy to follow.

weaknesses:
- 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.
- 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.

questions:
Please address weaknesses mentioned above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730639289880

thread_type:
official_review

<thread_object>
creator: reviewer_v2r2

<content>
summary:
This paper focuses on analysing the stability of signal processing GNNs (SPGNNs) by establishing limits for both node-level and graph-level embeddings. It also studies how to effectively transform relational databases into graphs towards better graph representation learning on relational databases.

strengths:
- The paper provides a comprehensive and thorough study on the stability of Signal Processing GNNs by showing a more refined bound that no longer depends on the number of nodes, which is interesting.

- The graph construction for relational databases is under-explored, and this work presents a novel approach that are empirically outperforming existing transformations methods.

- Empirically, the authors show that SPGNNs are stable under shifts in the underlying databases.

weaknesses:
- The topic and the focus of the paper is two-folded which are loosely related. It would be ideal if the paper can focus on one particular aspect, such as the stability of GNNs only (with potentially further results). In the current presentation, the respective parts of the paper read like two separate papers. 

- While the experiments provide valuable insights, the scope of the chosen datasets is rather limited. It would be better if the authors could validate the observation on additional baselines, especially the heterophilic datasets [1]? Relatedly, it would be interesting to know whether the proposed graph transformation can be applies to new relational database benchmark [2]?

- There are quite a few presentation issues in the mathematical notation. For example:
  -The definition of operator norm (line 247) should come before its use (Theorem 1);
  - What are $v_i$ and $\hat{v}_i$ in Theorem 2, equation 3? Two corresponding nodes from the original and edited graphs, respectively? Two different ones?

- Minor issues: Figures 5-7 in the appendix are hardly readable. Also isn't there a $\delta$ missing in the statement of Theorem 1?

questions:
- How would the results be affected when applied on standard heterophilic graph datasets in [1], both theoretically and empirically?
- Are the results directly applicable to link-level prediction? If not, can the authors comment on whether and how it could be adapted?
- Can you please elaborate on why WLOG Theorem 2 can be directly applied to higher-degree polynomial as the filter? Specifically, how do you deal with the non-linearity? (Remark 4)
- In Theorem 2, it is stated that the shift operators must be symmetric: is this not an unrealistic assumption, since  the edges are typically directed in relational databases (making the shift operators not symmetric)?
- Is transformation from relational database to graph really needed? Why should we model relational database as graph given that there is already a lot of models dedicated for reasoning over tabular data?
- Figure 2 shows that the theoretical upper-bound is of up to 8 order of magnitude larger than the empirical average distance. While the empirical results are quite interesting, are the bounds of any use, given that they are so loose? 
- Are there any similar results (theoretical or empirical) on other models, for instance Graph Transformers [3] or even GATs [4]?
- On the empirical side, how can we distinguish stability effect from over-smoothing [5], especially when operating on such large graphs? (It might be better to conduct experiments with very few layers).

[1] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation of
GNNs under heterophily: Are we really making progress? ICLR, 2023.

[2] Robinson, Joshua, et al. Relbench: A benchmark for deep learning on relational databases. arXiv preprint arXiv:2407.20060, 2024.

[3] Min, E., Chen, R., Bian, Y., Xu, T., Zhao, K., Huang, W., Zhao, P., Huang, J., Ananiadou, S., Rong, Y. Transformer for Graphs: An Overview from Architecture Perspective, arXiv preprint arXiv:2205.08455, 2022.

[4] Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y. Graph Attention Networks, ICLR 2018.

[5] Rusch, TK, Bronstein, MM, Mishra, S. A Survey on Oversmoothing in Graph Neural Networks, arXiv preprint arxiv:2303.10993, 2023.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730639952018

thread_type:
official_review

<thread_object>
creator: reviewer_jor2

<content>
summary:
The work poses in the topic of GNN and stability of learned embeddings. In particular the aim is to study the stability of embeddings learned by GNNs in relational databases and to present some techniques to transform a relational database into a graph in order to apply message passing schema

strengths:
- The theoretical foundation supporting this work is robust, making it a crucial component.
-  Additionally, the problem being addressed is highly relevant.

weaknesses:
- The paper lacks clarity in several areas, which I will specify in my subsequent questions.
- While the paper argues for treating a relational database as a homogeneous graph, it does not adequately explain why this is the case. Since this claim is significant, I recommend that the authors clarify it further.
- The experimental section is limited by the absence of a recent benchmark [1] related to relational databases, which I suggest the authors incorporate into their experiments.
- The paper does not address various models typically used for heterogeneous graphs as competitors.

questions:
**Main**

- In the final part of the Introduction (**our second contribution**), you mention that current database-to-graph construction methods often result in overly heterogeneous structures. However, it’s unclear why this is problematic. Given the importance of this claim, please provide more justification.
- In the last paragraph of Related Works, you mention approaches that use LLMs to generate embeddings from databases but don’t cite them or discuss their limitations. Please elaborate on these methods and, if relevant, include a comparison or clarify why a comparison isn’t necessary.
- In the definition of SPGNN (3.2) in the node embeddings paragraph, you state that the $L-$th layer of SPGNN does not output embeddings. What does it output, then? This part is unclear, as $X^{(l)}$ was previously defined as the feature map at layer $l$.
- In Section 5, could you clarify why you describe the first two database-to-graph transformation methods as heterophilic? They seem more accurately described as heterogeneous rather than heterophilic. Additionally, you mention that these methods fail to capture the underlying structure of the database, but the reasoning behind this could be expanded right now, it’s a bit unclear.
- In Section 5, under **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—this works for tuple removal, but what about when tuples are added, as often occurs in relational databases?
- In relational databases, nodes are often both added and removed over time. In your experiments, however, you only demonstrate node removal. Could you show both additions and removals simultaneously? This would better support your model’s stability in relational database scenarios.
- There is a recent benchmark [1] that proposes a way of constructing graph from relational databases that you don’t compare with.
- 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.

**Minors**
- The introduction lacks citations in several parts. For instance, when you state, “Recent advances in deep learning, particularly Graph Neural Networks, have shown effectiveness in learning from tabular, relational data,” you should support this with references. The same applies to other paragraphs in this section.
- The "stability" subsection in Related Works feels disjointed, and the connection between each paragraph and the current work is unclear.
- In section 4.1 you write that as limitations of the previous work is that the result is local. It is not very clear how you define local in this context


[1] Robinson et al., Relbench: A benchmark for deep learning on relational databases, 2024
</content>
</thread_object>

</thread>
<thread>
creation date:
1730722130765

thread_type:
official_review

<thread_object>
creator: reviewer_6hkw

<content>
summary:
This paper theoretically examines the stability of GNNs in the context of significant graph perturbations, a common challenge in relational databases. By comparing existing database-to-graph construction methods, the paper proposes a new method designed for improved stability, demonstrating practical advantages.

strengths:
1. This paper expands the applicability of current stability bounds to a broader range of settings, making it more relevant for practical relational database use.
2. It introduces a new method for converting relational databases to graphs with enhanced stability.
3. The experiments are conducted on various datasets, supplemented by empirical analyses to validate GNN effectiveness.

weaknesses:
1. 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 graphs datasets from HGB [1]

[1] Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks https://arxiv.org/abs/2112.14936

questions:
1. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732180092080

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
general comment to all reviewers

comment:
We thank all the reviewers for their extensive comments and questions. 

Following the reviewers' suggestions, we have included additional experiments on (i) sequences of tuple additions / deletions in a relational database and their effects on stability on the GNN embeddings of the database-to-graph constructions (Fig.  15-17) and  (ii) the potential effect of over-smoothing in the GNNs (Fig. 10-11 for the comparison on the Mutagenesis dataset).  These experiments further consolidate the main observations of our initial empirical evaluation.

The edits for all minor comments / clarifications were done directly in the revised  paper. Next, we provide our answers to the detailed questions.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This manuscript analyzes the stability of signal-processing GNNs (SPGNNs) by establishing limits for both node-level and graph-level embeddings. The stability is related to how much the embeddings generated by a GNN change when the input graph undergoes modifications. This manuscript presents some techniques to transform a relational database into a graph to apply message-passing schema.

Reviewers commented that the topic is interesting and that the problem being addressed is highly relevant to the venue. However, some critical issues make this manuscript incomplete, and the manuscript needs to be reviewed again after major revisions. The authors should consider the following points in the revisions.
- Compare with Heterogeneous GNNs in experiments
- Compare with a recent benchmark [1] that proposes a way of constructing graphs from relational databases
- Clarify terminologies and details questioned by the reviewers.
- The paper's topic and focus are two-folded and loosely related. Relate the two seemingly separable stories and make the manuscript more coherent. 

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