On Class Distributions Induced by Nearest Neighbor Graphs for Node Classification of Tabular Data
Authors: Federico Errica
Venue: NeurIPS 2023 poster (2023)
Keywords: Deep Graph Networks
Graph Neural Networks
Graph Representation Learning
Nearest Neighbors
Node Classification
Tabular Data
TL;DR: We formally study how nearest neighbor structures, used in the past when a graph structure is not available, impact the performance of message passing neural networks.

Abstract: Researchers have used nearest neighbor graphs to transform classical machine learning problems on tabular data into node classification tasks to solve with graph representation learning methods. Such artificial structures often reflect the homophily assumption, believed to be a key factor in the performances of deep graph networks. In light of recent results demystifying these beliefs, we introduce a theoretical framework to understand the benefits of Nearest Neighbor (NN) graphs when a graph structure is missing. We formally analyze the Cross-Class Neighborhood Similarity (CCNS), used to empirically evaluate the usefulness of structures, in the context of nearest neighbor graphs. Moreover, we study the class separability induced by deep graph networks on a k-NN graph. Motivated by the theory, our quantitative experiments demonstrate that, under full supervision, employing a k-NN graph offers no benefits compared to a structure-agnostic baseline. Qualitative analyses suggest that our framework is good at estimating the CCNS and hint at k-NN graphs never being useful for such classification tasks under full supervision, thus advocating for the study of alternative graph construction techniques in combination with deep graph networks.

On Class Distributions Induced by Nearest Neighbor Graphs for Node Classification of Tabular Data
Federico Errica NEC Laboratories Europe Heidelberg, Germany
Abstract
Researchers have used nearest neighbor graphs to transform classical machine learning problems on tabular data into node classification tasks to solve with graph representation learning methods. Such artificial structures often reflect the homophily assumption, believed to be a key factor in the performances of deep graph networks. In light of recent results demystifying these beliefs, we introduce theoretical framework
understand the benefits of Nearest Neighbor (NN) graphs when a graph structure is missing. We formally analyze the Cross-Class Neighborhood Similarity (CCNS), used to empirically evaluate the usefulness of structures, in the context nearest neighhor graphs. Moreover, we study the class separability induced by deep graph networks on k-NN graph. Motivated by the theory, our quantitative experiments demonstrate that, under full supervision, employing a k-NN graph offers no benefits compared to structure-agnostic baseline. Qualitative analyses suggest that our framework is good at estimating the CCNS and hint k-NN graphs never being useful for such classification tasks under full supervision, thus advocating for the study of alternative graph construction techniques combination with deep graph networks.
Introduction
The pursuit of understanding real-world phenomena has often led researchers model the system of interest as set of interdependent constituents, which influence each other in complex ways. In disciplines such as chemistry, physics, and network science, graphs are convenient and well- studied mathematical object to represent such interacting entities and their attributes. In machine learning, the term "graph representation learning" refers methods that can automatically leverage grrphestructured data to solve tasks such entity (or node), link, and whole-graph predictions
12
32
78
Most of these methods assume that the relational information, that is the connections between entities, naturally emerges from the domain of the problem and is thus known. There is also broad consensus that connected entities typically share characteristics, behavioral patterns, or affiliation, something known as the homophily assumption 45). This is possibly why, when the structure not available, researchers have tried to artificially build Nearest Neighbor (NN) graphs from tabular data, by connecting entities based on some attribute similarity criterion, with applications in healthcare 44 65), fake news and spam detection 339 71, biology [77, (2), and document classification [56] to name a few. From an information- -thoorttic perspective, the creation of such graphs does not add new information as it depends on the available data; that said, what makes their use plausible is that the graph construction is form of feature engineering that often encodes the homophily assumption. Combined with the inductive bias of Deep Graph Networks (DGNs) [59] 46), this strategy aims at improving the generalization performances on tabular data compared to cruuctur-agnostte baselines, for example, Multi-Layer Perceptron (MLP).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Indeed, using k--N graph [2] has recently improved the node classification performances under the scareity of training labels [24 23]. This is also known as the semi-supervised setting, where one can access the features of all nodes but the class labels are available for handful of those. A potential explanation for these results that, by incorporating neighboring values into each entity's representation, the neighborhood aggregation performed by DGNs acts as a regularization strategy that prevents the classifier from overfitting the attributes of the few labeled nodes, similar to input jittering [57 62, 6]. However, it is still unclear what happens when one has access to all training labels (hereinafter the fully-supervised setting), namely if these graph-building strategies grant a baseline. In this
statistically significant advantage in generalization compared to a structure-agnose respect, proper comparisons against such baselines are often lacking or unclear in previous works, an issue that has also been reported in recent papers about the reproducibility of node and graph classification experiments [61 22
In addition, it was recently shown 43 that homophily is not required to achieve good classification performances node classification tasks; rather, what truly matters is how different the neighborhood class label distributions of nodes of separate classes are. This resulted in the definition of the empirical Cross-Class Neighborhood Similarity (CCNS) [43] [3], an object that estimates such similarities based on the available connectivity structure. Yet, whether or not artificially built graphs can be useful for the task at hand has mainly remained an empirical question, and more theoretical conditions for which this happens are still not understood.
In this paper, we introduce a theoretical framework to approach this question, and we provide two analyses of independent interest. Inspired by the CCNS, Section 3.1 studies the neighboring class label distribution of nearest neighbor graphs. Then Section 3.2 deals with the distribution of entity embeddings induced by DGNs on a k-NN graph, and we use it to quantify class separability in both the input and the embedding spaces. Overall, our theoretical results suggest that building a k-NN graph is not good idea. To validate the theory with empirical evidence, we robustly compare (Sections and 5 four baselines across 11 tabular datasets to check that the k-NN graph construction does not give statistically significant advantages in the fully-supervised setting. In addition, we reverse-engineer the theory to learn data distributions that would make a k--N graph useful in practice when combined with DGNs. From the empirical results, we conjecture that this is never the case. Therefore, we hope to raise awareness in the graph machine learning community about the need for alternative (either NN-based or not) graph construction techniques.
In summary, our contributions are: i) under some assumptions, we can estimate the CCNS for nearest neighbor graphs and provide its first lower bound; ii) we study how applying a simple DGN to an artificial k-NN graph affects the class separability of the input data; ii) we carry out a robust comparison between structure-agnostie and structure-aware baselines agreement with our theoretical results; iv) qualitative analyses based on the theory further suggest that using the N-NN graph might not be advisable.
set of 11 datasets that is in
2
Related Work
The early days of graph representation learning date back to the end of the previous century, when researchers proposed backpropagation through structures process directed acyelic graphs [63] 25
These ideas laid the foundations for the adaptive processing of cyclic graphs by the recurrent Graph Neural Network (59) and the feedforward Neural Network for Graphs 44), which today's DGNs build upon. Both methods iteratively compute embeddings of the graphs' entities (also called nodes) via a local and iterative message passing mechanism [27] that propagates the information through the graph. In recent years, many neural and probabilistic DGNs have emerged [50] 36) 31 69 77, 3] bridging ideas from different fields of machine learning; we set up our analysis in the context of these message- message-passing architectures, Even more recently, transformer models have begun to appear
in graph-related tasks as well 19 B7 (75). Akin to kernel methods for graphs [7] [38, this class of methods mainly relies on feature engineering to extract rich information from the input graph,
and some perform very well at molecular tasks [4]] However, the architecture of transformers is not intrinsically more expressive than DGNs, and their effectiveness depends on the specific
encodings used [8). Therefore, gaining a better understanding of the inductive bias of DGNs remains compelling research question.
2

---

The construction of NN graphs found recent application in predicting the mortality of patients, by connecting them according to specific attributes of the electronic health records 44 65]. In addition, it was used in natural language processing to connect messages and news with similar contents to tackle spam and fake news detection, respectively [39 7 In both cases, the authors computed similarity based on some embedding representation of the text, and the terms' frequency in a document was the graph-building criterion for a generic document classification task [56]. Finally, k-NN graphs have also been built based on chest computerized tomography similarity for early diagnoses of COVID-19 777 42 or to understand debts will be repaid in time [29].
Most of the theoretical works on DGNs deal with the problems of over swoothigg 40
28 of learned representations. as well as the discriminative power of such models [7 [74] 226 10]. In this context, researchers mostly agreed that DGNs based on message passing perform favorably for homophilic graphs and not so much for heterophilic ones 79] However, recent works suggest different perspective; the generalization performances depend more on the neighborhood distributions of nodes belonging to different classes 44 and on a good choice of the model's 's weights [67]. The Cross-Class Neighborhood Similarity (CCNS) Ma et al. 43 stands out as an effective (but purely empirical) strategy to understand whether a graph structure is useful or not for node classification task. In our work, we take inspiration from the CCNS to study the behavior of the neighborhood class label distributions around nodes and compute the first approximation and lower bound of the CCNS for NN graphs without the need to explicitly build them.
and over- squashin 66
Structure learning and graph rewiring are also related but orthogonal topics. Rather than pre- computing fixed structure, these approaches discover latent dependencies between samples 22 72
and can enrich the original graph structure when this available 17 76 [6] [4]. They have been applied in contexts of scarce supervision, where k-NN graph proved to be an effective baseline
when combined with DGNs [23]. At the same time, the combinatorial nature of graphs makes
difficult and expensive to explore the space of all possible structures, making the priori construction of the graph a sensible and efficient alternative.
3 Methodology
We begin by introducing notions and assumptions that will be used throughout the paper. Our starting point is classification task over a set of classes C, where each sample u is associated with a vector of D attributes x, E R and a target class label yu E C.
A graph g of size N is quadruple (V, E,X, where V = =1,.... NJ represents the set of nodes and ε is the set of directed edges (u, v) from node u to node v. The symbol X' = (Xu, Vu E V} defines the set of random variables (F.v.) with realizations v. IR, E V. The same definition applics to the set of target variables y = (Y., Vu E V} and their realizations yu E C, u E V. When we talk about the subset of nodes with target label E C, use the symbol Ve: also, we define the neighborhood of node u as N₁, = (v Vl(u, u) E E}.
A Gaussian (or normal) univariate distribution with mean and standard deviation μr, a E RR > 0 represented as ((:;p,02), using μ E TR. Σ E DxD for the multivariate case. The probability density function (p.d.f) of a univariate normal F.V. parametrized by μ,, is denoted by Φ(-) together with its cumulative density function (c.d.f) F Fww)= + (""")) (1 + (af(("=)) )), where erf is the error function. Subscripts will denote quantities related specific random variable.
We want to transform the initial task into a node classification problem, where different i.i.d. samples become the nodes of single graph, and the edges are computed by some nearest neighbor al- gorithm. We assume (assumption 1) the true data distribution p(X = x) of each sample (thus abstracting from u) is defined by the graphical model of Figure [ (left). This model reflects the common assumption that observables of a given class share the same distribution [30, (7), and we choose this distribution to be a mixture of Gaussian distributions. Such choice is not restrictive since, in principle, with enough mixture components it is possible to approximate al- most any continuous density (9) Note that it is also possible to sample discrete attribute val- ues by rounding the samples of a properly parametrized Gaussian mixture. Formally, we con- sider [C] latent classes modeled by categorical E. C. with prior distribution p(C c) and [M mixtures for each class modeled by M ~ p(M = m|C = c),m E M, E C, such that p(æ]c) ΣM p( m, c)p(mlc). In Section 3.1
we further require (assumption 2) that the
3

---

data model
M
X
p(x|C 0)
paxC 1)
p(x)
Xn
Xx
Xu
Figure I: Left: we represent assumption on the data distribution through graphical model, i.e., hierarchical mixture of distributions, where observed variables are shaded and latent ones are white circles. Right: visual example of data distribution generated by the graphical model, with intuitive visualization of the class posterior mass around point Tu.
D observables are conditionally independent when the class and the mixture m are known, i.e., IM E==1 p(m|c) I p(zy m,,), c). We refer the reader to Section 3.3 for
p(X x) = E p(c) Σ discussion about this assumption. Figure ( depicts an example of one such data distribution 1. Hereinafter we shall have p(X, = xylm, c) (a (emf; dmm,) for the individual attributes and p(X = x/m,e c) = N(x; jmmes Emc) for the multivariate case. We will also use diagonal covariance matrices denoted as Ame diag(omme........ . me Finally, akin to [43], assume that the neighbors of node v are i.i.d. (assumption 3), meaning their attributes and class distributions only depend on the properties of node u; such assumption is especially reasonable when one considers how nearest neighbor structures are typically built, by picking set of neighbors based only their distance to the target node
To talk about the surroundings a point in space we will use the notion hypercubes (or D-cubes). A hypercube of dimension D centered at point a E R.D of side length & >> 0 is the set of points given
by the Cartesian product Hg (x) = [1 2. 5] x ITD DD + 5
3.1 Analytical Computation of the CCNS for Nearest Neighbor Graphs
computes how similar the neighborhoods of two distinct nodes in terms of class label distribution, and it provides an aggregated result over pairs of target classes. Intuitively, if nodes belonging distinct classes happen have similar neighboring class label distributions, then it will be unlikely that a classifier will correctly discriminate between these two nodes after a message passing operation because the nodes' embeddings will look very similar. On the other hand, nodes of different classes with very different neighboring class label distributions will be easier to separate. This intuition implies that nodes of different classes typically have different attribute values.
The CCNS 43
Definition 3.1 (Cross Class Neighborhood Similarity, extended from [43). Given a graph g, the cross-class neighborhood similarity between classes c, c' C given by
<(c, c) Ppp (A)) qar")))
where Z computes (disasimilarity score between vectors and the function d. IR. - RIC| (resp qer) computes the probability vector that node of class e (resp. c') with attributes æ (resp. x') has a neighbor of class c". for every c" C.C. C.
The definition of qe and ge' is the key ingredient of Equation 1 In the following, we are going to show that it possible analytically compute these quantities when we assume NN structure. For every norm-induced metric, which is also convex, the lower bound of Equation I follows from Jensen's inequality and from the linearity of expectation:
<cc, c') 2
E (Fptaletpteeeee
q. (x')]
Ep(ale) (x)) Eppeeter (x') ||-
This bound assigns non-zero values to the inter-class neighborhood similarity, but as we shall see one can resort to Monte Carlo approximations of Equation to estimate both the inter and intru-class scores. From now we will use the Euclidean distance our Ω.

---

We first study the class label distribution in the surroundings of some node u. In the example of Figure (right), we consider a binary classification problem with [M| = 2 and depict the conditional distributions p(ar..C' = 0), p( line, instead, represents p(x)) assuming a con-informative class prior. the neighbors of u belong to the hypercube Hg (m..) for some E, then the probability that a neighbor will belong to class depends on how much class-specific probability mass, that the shaded green and blue areas, there is the hypercube. Since the blue area is larger than the green one, finding a neighbor of class 1 is more likely to happen. Formally, we define the (unnormalized) probability of a neighbor belonging to class in given hypercube the weighted posterior mass of C contained in that hypercube.
1) with green and blue curves, respectively. A dashed black
Definition 3.2 (Posterior Mass Mx(c,s) Around Point x). Given hypercube (x) centered at point æ E RDD and class c C. the posterior mass M (c, 8) the unnormalized probability that a point in the hypercube has class
p(c)))p(w)du = p(c) / (x)
Ma (c, <) (w)
p(wlc)dw, (3)
(m)
where the last equality follows from Bayes' theorem.
The following proposition shows how to compute Mz(c,e) analytically. The interested reader can find all proofs of our paper in Section A.3
Proposition 3.3. Under assumptions 1,2, Ma(c,e) has the following analytical form
[M]
D
Σ p(mlc) II (F (Iz+ 2 - (01- - 2 m=1
p(c)
(4)
f=1
where Z is a r.v. with Gaussian distribution N Hemp o lemm))
To reason about entire class rather than individual samples, therefore being able to compute the two quantities on the right-hand side Equation we extend the previous definition by taking into account all samples of class d' E C. Thus, seek to compute the average unnormalized probability that a sample belongs to class e in the hypercubes centered around samples of class é'
Definition 3.4 (Expected Class c Posterior Mass Mar E) for Samples of Class d'). Given a hyper- cube length e and class d' E C, the unnormalized probability that sample of class e has another sample of class e lying in its hypercube is defined as
(c,(c,))
E Ex-p(e)) (M (M,(c)))
(5)
It is also possible to compute Md (c, e) in closed form, which show in the next theorem. Theorem 3.5. Under assumptions 1,2, (c, has the following analytical form
)) (6)
Penm' + 3/ Memm
& Pem's f & Mero
p(c)
plm'le p(mmcc))(mlc)
II
Vomms + o2mm's
Vooms 5 + o² oemms
Thanks to Theorem 3.5
we know how much class-c posterior probability mass we have, on average, around samples of class c'. To get proper class e' e'speciffic distribution over neighboring class labels, we apply normalization step using the fact that (c, E) 2 Ve
Definition 3.6 (e-Neighboring Class Distribution). Given class e' and an > O, the neighboring class distribution around samples of class is modeled as
(c,
(e((c)) Σ Ma(
This distribution formalizes the notion that, in neighborhood around points of class c', the probability that points belong to class does not necessarily match the true prior distribution p(C = c). However, this becomes false when consider infinitely-Iare large hyper-cube, as we show in the next result.
5

---

Proposition 3.7. Let the first D derivatives of Σ |0l
=1 (i) (i) be different from O in open interval I
around 8 = O and not lending to infinity for & O. Under assumptions 1,2, Equation 7 has limits
p(c) Eia p(mle))(mm (c') I[-=1 7mmmmmm (0)
lim Pe (c, e-0
lim (c p(c) 5
Ei p(i) E Em pmm)))p(mm (c') Ilp= &mmmm' (0)
(8)
where Zimm's has distribution N(; -himmm De y),
Oimm's 2(Hoe'm' - Homs) and Dimmns 2 im + 02
c'm'
The choice of E, which implicitly encodes our definition of "nearest" neighbor, plays crucial role in determining the distribution of a neighbor's class label. When the hypereube is too big, the probability that a neighbor has class e matches the true prior p(c) regardless of the class c' that is we make a crude assumption about the neighbor's class distribution of a sample. If we instead consider a smaller hypercube, then we observe less trivial behavior and the probability Pe (c, e) is directly proportional to the distances between the means pmcmm and Pem. as one would intuitively expect for simple examples.
To summarize, we can use (e( as an approximation for Ep(nje))gg of Equation similarly. we use normalized version of M,(x)) in place of go(ar) estimate Equation via Monte Carlo sampling without the need of building a NN graph. For space reasons, in Appendix A.3 we qualitatively discuss the results for 1-dimensional instance of data distribution, and we investigate the quality of the CCNS approximation while varying k.
3.2 Class Separability Induced by DGNs on a k-NN Graph
This section formally investigates the properties of the embedding space created by DGNs under the k-NN graph. Our goal is to understand whether using such a graph can improve the separability between samples belonging different classes or not. Provided that conclusions would be interesting: if the k-NN graph helps, then we know the conditions for that to happen; if that is not the case, we have identified and formalized the need for new graph construction mechanisms.
assumptions hold, both
we consider linear I-layer DGN with the following neighborhood aggregation scheme that computes node embeddings h2 E R Vu E V:
Akin to previous works 40 6
5
Σ T..
h
R:
VEN.
The node embedding of sample u is then fed into standard machine learning classifier, e.g., an MLP. As done in previous works, we assume that a linear (learnable) transformation W E I DxD of the input V., often used in DGN models such the Neural Network for Graphs (46) and the Graph Convolutional Network [36] is absorbed by the subsequent classifier.
Mimicking the behavior of the k-NN algorithm, which connects similar entities together. model the attribute distribution of a neighbor v E N₁, as a normal distribution A (xx Va diag(o" (0².... of......'* o²). where o² is a syper-paramete that ensures it is highly unlikely to sample neighbors outside of Hæ(x))) from now on we use the symbol dg to make this connection clear. Under assumption neighbors' sampling is independently repeated k times and the attributes are averaged together. Therefore, we use statistical properties of normal distributions (please refer to Lemmas A.2 and A.I compute the resulting node u's embedding distribution:
ph (..) (h,;;; Tu,, Ac), Ag =
(10)
Therefore, the more neighbors a node has (i.e., higher k) the more skewed the resulting distribution is around T. (i.e., lower variance). This is fairly reasonable assumption if we think of an infinitely large dataset; informally, each of the neighbors will be much more likely to lie near x., than near the surface of the hypereube, hence h. will be close to R,, with high probability.
To understand how Equation 9 Jaffects the separability of samples belonging to different classes, we compute a divergence score between the distributions p(h(c) and p(hlc') [68] 51 20 & 52). When

---

this divergence is higher than that of the distributions p(z]c) and p(z]e'), then the k-NN structure and the inductive bias of DGNs are helpful for our task. Below, we show that for two mixtures of Gaussians we can obtain the analytical form of their Squared Error Distance (SED), the simplest symmetric divergence defined as SF q) = = (((())((())))))))) - ( dr. This provides a concrete strategy to understand, regardless of training. if would make sense to build k-NN graph for our problem |
Proposition 3.8. Under assumptions 1,3, let us assume that the entity embeddings of a I-layer DGN applied on an artificially built k-NN graph follow the distribution of Equation [0] Then the Squared Error Distances SED(p(hke)) c))) and SED(p( (x]c)) p(xx(c)) have analytical forms.
In the interest of space, we have deferred the analytic formulas to the appendix.
As an immediate but important corollary, a k-NN graph improves the ability to distinguish samples of different classes c, c' if it holds that SED(p( (h c). p(hcc)) > SED(p(z)c), p(z](c)). Indeed, class distributions diverge more in the embedding space, which has the same dimensionality as the input space, then they will be easier to separate by a universal approximator such as an MLP. We use this corollary in our experiments, by reverse-engineering the theory to find out "good" data models.
3.3 Limitations and Future Directions
is extremely challenging to prove that a l--N graph never helps to improve the classification performances using a DGN. The reason is that theoretical results of this kind rely, is common [43], on assumptions of the true data generating distribution and on the specific assignments of parameters such as μ and E. The true data distribution is typically unknown and hard to find [68], but assumptions and 3 remain quite reasonable due to the flexibility of mixture models and the nature of the nearest neighbors construction. In addition, assumption 2 has been widely used in the graphical models literature because it is particularly attractive from a theoretical perspective [64), despite cannot cover all real-world cases; we note, however, that it plays no role in the analysis of Section 3.2 Finally, as done in the past [40] 15 5 43), we have ignored the non-linearity in the neighborhood aggregation of Equation 9 As we shall see in our empirical results, the intuitions we gained from the theoretical analysis seem to hold for non-linear models as well.
Our analysis has considered hyper-cubes in the interest of simplicity, but nearest neighbor graphs typically compute hyper-bally balls centered at a point. In nigh-dimensional spaces, the volume of hyper- cubes and hyper-balls can differ non-trivial ways [18, so future work should improve on our results by replacing hyper-cubes with hyper-balls. Similarly, the results of Section 3 could be used to guide the definition of new graph construction strategies based on attribute similarity criteria, for instance by proposing good & for the data at hand. We leave this idea to future investigations.
4 Experiments
We conduct quantitative and qualitative experiments to support our theoretical insights. For all experiments used server with 32 cores, 128 GBs of RAM, and GPUs with 11 GBs of memory.
Quantitative Experiments Quantitatively speaking, we want to compare a structure-agnostic baseline, namely an MLP (58). against different graph machine Icarning models, such as a simple gyquationFoollowee
DGN (sDGN) that implements Network (GIN) (74) and the Graph Convolutional Network (GCN) (36. The goal is to show that in the fully-supervised setting using a k-NN graph does not offer any concrete benefit. We consider 11 datasets, eight of which were taken from the UCI repository (2). namely Abalone, Adult, Dry Bean, Electrical Grid Stability, Isolet, Musk v2, Occupancy Detection, Waveform Database Generator v2, as well as the citation networks Cora, Citeseer (60), and Pubmed (49 For each dataset, we build k-NN graph, where k is hyper-parameter, using the node attributes' similarity to find neighbors (discarding the original structure in the citation networks). We report some datasets statisties in Table 2, and the metric to optimize is the Fl score. Note that it is difficult to ascertain if our assumptions hold for these datasets because we have no access to the true data distribution; however, robust comparison for this topic is lacking in the literature and can help us gather further insights on whether our ideas might also hold in more general setting. For every dataset and model, we follow the rigorous and fair evaluation setup of [22] we perform a 10-fold cross validation for risk assessment,
by an MLP classifier, the Graph Isomorphism
'The proof also makes simple but meaningful connection to the over-smoothig problem.
7

---

Table 1: Node classification mean and standard deviation results for a structure atrusture-agnostic baseline (MLP) compared to graph machine learning methods applied to artificially built k-NN graphs. We performed model selection w.r.t. the Fl score, but we also include the accuracy for completeness.
MLP
sDGN
GIN
GCN
F1
ACC
F1
ACC
F1
ACC
F1
ACC
Abalone
0.55
55.5
0.55
55.3
0.54
54.2+1.7
0.54
54.4
Adult
0.70=a.02
77.6+1.7
0.72.20.22
77.8+1.9
0.69+0.02
76.2+1a
0.70
78.6-a.9
DryBean
0.78
77.414.0
0.77=0008
77.3:5.4
0.75
74.413.2
0.71
72.6=4.9
eGrid
0.95
95.610.6
0.95
95.810.4
0.9310.01
94.010.6
0.82:0.02
83.1-144
Isolet
0.95
95.410.5
0.95
95.4.10.3
0.95
95.310.7
0.92
91.7=114
Musk
0.99_2..1
99.3+0.3
0.99_0.01
99.5...3
0.94
97.012.2
0.94-n.02
96.720.9
Occupancy
0.99
98,940.4
0.99
98.940.5
0,98
98.640.6
0.90=0.17
95.826.0
Waveform
0.85
85.5
0,85g0.02
85.341.5
0.84
84.5+1.7
0.84
84.0=2.2
Cora
0.71
74.3+2.4
+0.00
74.1+2.5
0.72
74.9+2.4
0.70
73,0=2.6
Citeseer
0.69
71.8+1.9
0.69
0.003
72.9+2.7
0.69
72.1
0.70
74,4=2.4
Pubmed
0.87 =0.0=
87.6+0.7
0.87 =0.01
87.6+0.6
0.87 #0.01
86.6+0.9
0.83
83.5
with a hold-out model selection (90% training/10% validation) for each of the 10 external training folds. We report the hyper-parameters for the model selection phase in Table For each of the 10 best models, we perform 3 final re-training runs and average their test performances on the corresponding external fold to mitigate bad initializations. The final score is the average of these 10 test results.
Qualitative Experiments We provide four qualitative experiments. First, we study how se changes for varying values of & and different priors p(c) under specific class-conditional data distributions. Second, we analyze the first limit of Proposition 3.7 under the same conditional data distributions as before (D = hence assumptions are trivially satisfied). We translated one of the distributions by different values and computed the SED between them, together with the quantity pe(c',) under different priors. The goal here is to show the relation between the SED and the limit. Third, we reverse-engincer the theoretical results to find, if possible, data distributions satisfying SED(p(())), p(hlc') > SED(((a x (c), p(x) (())).)). There is no dataset associated with this experiment, rather we learn the parameters of the graphical model of Figure (left) together with E. e.k.o o. (k is treated as continuous value during the optimization) in order to minimize the following objective: LSED- ALCENS, where À a hyper-parameter LSED sums SED( (c), p(x)(c)) (ED(pphacc p()cc)) for all pairs of distinct classes c, c,c', whereas LCONS computes the lower bound for the inter-class similarity, thus acting as a regularizer that avoids the trivial solution p(xlc)= =p(z=c') for class pairs c, c'_ The set of configurations for this experiment is reported in Table and we use Adam (35] as optimizer. In the last qualitative experiment, we compute the true CCNS and its approximations for the specific example of Figure [ (right), showing that the quantities obtained Proposition 3.3 and Theorem 3.5 3.5 are good representatives of the CCNS for nearest neighbor graphs. Please refer to Appendix A.5 for an additional study of this kind. |
5 Empirical Results
We now present our empirical results support the theory. The interested reader can find statistics on the chosen hyper- arper-parametess and additional ablation studies in Appendix A.6
Quantitative Results Table details the empirical comparison between the structure-agnostic MLP and the structure-aware baselines sDGN, GIN, and GCN. We observe that in terms of Micro Fl score, which is the metric all models are optimized against, there no statistically significant improvement in performance (unpaired two samples t-test with v-vuuue 0.05) for the different DGNs when using an artificial k-NN graph. When looking at accuracy one can observe a similar trend, but the results fluctuate more because accuracy is not the metric to be optimized. These results further confirm that using k-NN graphs does not bring a substantial contribution to the generalization performances. On the contrary. it would seem the K-NN graph can even be considered harmful for the performances of GIN and GCN (e-g., DryBean, Musk, eGrid, Waveform). We hypothesize that the information flow
tabular aa_d

---

pic) [0.5.005]
p(c) [0.3=
10-
P
0.65
pv00.4
0.8
0.
pixc-11
PM1.4]
0.7
0.55
p.(0.4]
px
-.
Px( 41
0.50
0.5
p)
0.4
0.4
0.-
0.40
0.0-
0.35
0.2
10
Figure 2: We show how Pe(c', varies for different values of and prior distributions assuming the classccon data distributions on the left.
of message passing does not act anymore regularizer (we refer the reader to the discussion in S as it might happen the scarce supervision scenario [23], rather becomes harmful noise for the learning process. This is possibly the reason why sDGN, which is also the simplest of the DGNs considered, tends to overfit less such noise and always performs on par with the MLP.
Therefore, one of the main takeaways of the quantitative analysis is that the k-NN graph might generally not be good artificial structure for addressing the classification of tabular data using graph representation learning methods. Different artificial structures, possibly inspired by our theoretical results, should be proposed to create graphs that help DGNs to better generalize this context. We note that this research direction is broader than tabular classification, but tabular data offers great starting point since samples are typically assumed i..dd in ML and are thus easier to manipulate. Also, in Appendix [A.4] we discuss the impact of different Ω (the cosine similarity) in the construction of the k-NN graphs
These results also substantiate our conjecture that, under assumptions 1,3, 3, the k-NN graph never induces a better class separability the embedding space: since p(hlc) is a mixture of distributions with the same mean but higher variance than p(æ|c) (proof of Proposition 3.8) in cow-dimensional space intuition suggests that the distributions of different classes will always overlap more in the embedding space than in the input space.
Qualitative Results We present the main qualitative results in Figures and First, see from Figure when e very small the probability that neighbor is of the same class is high for both classes (but not the same), since there is less overlap between samples of the green (C -C=00 and blue (C' = 1) distributions. As we increase the side length of the hypercube (or equivalently, consider more and more nearest neighbors), the curves converge the priors that set for this example. This result is in agreement with the second limit of Proposition 3.7
can
As regards the first limit of Proposition 3.7 in Figure we observe that the behavior of lim po(c' is non- con-trivial when the two curves still overlap. In particular, the greater the overlap the closer po(c,e) e) is to p(c), which makes sense since becomes harder to distinguish samples of different classes. On the other hand, the behavior becomes trivial when the curves are distant enough from each other: there, in the limit, every node will only have neighbors of the same class.
In the engineeenginn experiment of Figure 4 (left), for each possible configuration of the models tried in Table 4] we have computed the LSED for varying values of k E [1,500]. We have then normalized all values for readability, by dividing each value of (E c))p(())c)) by (FD(((()()) p(xr(()), as the latter is independent of k. This particular figure depicts the curves for the binary classification cases, but the conclusions do not change for multi-class classification, for on the y-axis
instance with 5 classes. We find that the normalized value of SED(p(h)))) ((h))) is always upper-bounded by 1, meaning that (ED(p(h c), p(h c')) < SED(p(a x c), p( c')) for all the configurations tried, even in higher dimensions. This result further indicates that it could be unlikely that a A-NN graph induces better class separability in the embedding space of a DGN. We ask machine learning practitioners to take these insights into consideration when building artificial nearest neighbor graphs.
ee))
I Lastly, we go back to the data distribution of Figure I (right) and show how to approximate the true CCNS under the k--N graph with our theoretical framework. We first generate 10000 data points and set w.l.o.g. k 5 to connect them. We compute the lower bound of the CCNS in the first

---

1.00
pix(C= 0)
8-
0.75
pixic-1)
6-
0.25
2'
0.00
translation of pix(0)
p(c) [0.5, 0.5]
p(c) (0.3...7
1.00
1.00
0.75
p)
0.75-
p:10,
psll.
p.(0,
p)
0.25
e)
0.25
0.00
0.00
translation p(x(0)
translation of pix(0)
Figure 3: We show how (c varies for different translations of the conditional data distributions p(z[0) and different priors approaches
1.0
0.27
0.23
1.1
SEDtHo, Hy) H1)
0.5
1
1.1 0.3
1.1
0.3
100
200
300
400
500
[e]
163
(c)
Figure 4: Left: Each curve specifies the variation of SED(p(hle)) lc), lec.p...... p(hlc')) against different values of k for different hyperparameters' configurations that have been trained minimize the learning objective. The curves are normalized w.r.t their corresponding SED(p((a c), p(x]cc)) Right: The CCNS lower bound (a), its Monte Carlo approximation for 0.1, obtained without creating any graph (b), and the true CCNS (c) for the example of Figure and 5-NN graph. Heatmaps (a) and (b) are computed using the theory of Section 3.1 Please refer the text for more details.
heatmap (a), Monte Carlo (MC) approximation of Equation (1000 samples per class pair) in the heatmap (b), and the true CCNS in the heatmap (c). In this case the lower bound has computed a good approximation of the inter-class CCNS, and the MC estimate very close to the true CCNS. In Appendix A.6 we also show that the MC approximation is better for higher values of k. It is important recall that both heatmaps and (b) computed using the theoretical results of Section and an 8 close to the empirical one, hence seems that the theory is in accord with the evidence.
6 Conclusions
We introduced a new theoretical tool understand how much nearest neighbor graphs can help in the classification of tabular data. Our theory and empirical evidence suggest that some attribute- based graph construction mechanisms, namely the k-NN algorithm, for obtaining better DGNs' generalization performances. This is particularly troubling result since researchers often used nearest neighbor graphs when the graph structure was unavailable. We recommend using great care in future empirical evaluations of such techniques by always comparing against atructure-agnostic baselines to ascertain real improvements from fictitious ones. Moreover, we provided theoretically principled way to model the CCNS for nearest neighbor graphs, showing its approximation in a practical example. We hope that the results of this work will foster better strategies for building artificial graphs guideline for new structure learning methods.
not promising strategies
10

---

Acknowledgments and Disclosure of Funding
The author would like to acknowledge, in no particular order, Sascha Saralajew, Julia Gastinger, Ammar Shaker, Filippo Grazioli, Luca Oneto, Sandra Tartarelli, and Timo Sztyler for the stimulating discussions and extremely helpful feedback. A warm thank you also goes to the reviewers for striving to further improve this work and make it ready for publication.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference Learning Representations (ICLR), 2021.
[2] Arthur Asuncion and David Newman. Uci machine learning repository, 2007. URL https //archive.ies uus.suui.edu//
[3] Davide Bacciu, Federico Errica, and Alessio Micheli. Probabilistic learning on graphs via contextual architectures. Journal of Machine Learning Research, 21(134):1 2020.
[4] Davide Bacciu, Federico Errica, Alessio Micheli, and Marco Podda. gentle introduction to deep learning for graphs. Neural Networks, 129:203-223 221, 9 2020.
[5] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-rf-distiibuttin generalization. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
[6] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(11), 2006.
[7] Adrien Benamira, Benjamin Devillers, Etienne Lesot, Ayush K Ray, Manal Saadi, and Fragkiskos D Malliaros. Semi-supervised learning and graph neural networks for fake news detection. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2019.
[8] Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. In Proceedings of the 2018 ACM Conference Computer and Communications Security (SIGSAC), 2018
[9] Christopher M Bishop. Pattern recognition and machine learning. Springer, 2006.
[10] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In Proceedings of the 35th Conference Neural Information Processing Systems (NeurlPS), 2021.
[11] Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS), 2022.
[12] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34 (4):18-422 2017.
[13] Andrea Cavallo, Claas Grohnfeldt, Michele Russo, Giulio Lovisotto, and Luca Vassio. 2-hop neighbor class similarity (2ncs): A graph structural metric indicative of graph neural network performance. Workshop Graphs and more Complex structures for Learning and Reasoning (AAAI), 2023.
[14] Ben Chamberlain, James Rowbottom, Maria Gorinova. Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In Proceedings of the 38th International Conference on Machine Learning (ICML). PMLR, 2021.
[15] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 3438-3445. 2020.
[16) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.

---

[17] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Proceedings of the 34th Conference on Neural Information Processing Systems (Neur/PS), 2020.
[18] Pedro Domingos, A few useful things to know about machine learning. Communications of the ACM, 55(10):78-87, 2012.
[19] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. Workshop on Deep Learning on Graphs: Methods and Applications (AAAI), 2021.
[20] Gamaleldin Elsayed. Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification. In Proceedings of the 32nd Conference on Neural Information Processing Systems (NeurIPS), 2018.
[21] David Eppstein, Michael S Paterson, and F Frances Yao. On nearest-neighhor graphs. Discrete & Computational Geometry, 17:263-282, 1997.
[22] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In 8th International Conference on Learning Representations (ICLR), 2020.
[23] Bahare Fatemi, Layla El Asri, and Seyed Mehran Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS), 2021.
[24] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
[25] Paolo Frasconi, Marco Gori, and Alessandro Sperduti. A general framework for adaptive processing of data structures. IEEE Transactions on Neural Networks, 9()):668-786, 1998.
[26] Floris Geerts, Filip Mazowiecki, and Guillermo Perez. Let's agree to degree: Comparing graph convolutional networks in the message-passing framework. In Proceedings of the 38th International Conference on Machine Learning (ICMI.), 2021.
[27] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICMI.), 2017.
[28] Alessio Gravina, Davide Bacciu, and Claudio Gallicchio. Anti-symmetric dgn: stable archi- tecture for deep graph networks. In / /th International Conference on Learning Representations (ICLR), 2023.
[29] Xiawei Guo, Yuhan Quan, Huan Zhao, Quanming Yao, Yong Li, and Weiwei Tu. Tabgnn: Multiplex graph neural network for tabular data prediction. Workshop on Deep Learning Practice for High- Diggeniinnsional Sparse Data (KDD), 2021.
[30] Jacques A Hagenaars and Allan L McCutcheon. Applied latent class analysis. Cambridge University Press, 2002.
[31] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st Conference on Neural Information Processing Systems (NIPS), 2017.
[32] William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3):52-74, 2017.
[33] Marko Helén and Tuomas Virtanen. Query by example of audio signals using euclidean distance between gaussian mixture models. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2007.
[34] Anees Kazi, Luca Cosmo, Geyed-Ahmate Ahmadi, Nassir Navab, and Michael M Bronstein. Differentiable graph module (dgm) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(2): (612)))6666111) 1617, 2022.
[35] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations (ICLR), 2015.
[36] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference Learning Representations (ICLR), 2017.
12

---

[37] Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létournaa, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurlPS), 2021.
[38] Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
[39] Ao Li, Zhou Qin, Runshi Liu, Yiqun Yang. and Dong Li. Spam review detection with graph con- volutional networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (CIKM), 2019.
[40] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAT), 2018.
[41] Yi-Lun Liao and Tess Smidt. Equiformer: Equivariant graph attention transformer for 3d atomistic graphs. In 11th International Conference on Learning Representations (ICLR), 2023.
[42] Siyuan Lu, Ziquan Zhu, Juan Manuel Gorriz, Shui-Hua Wang, and Yu-Dong Zhang. Nagnn: classification of covid-19 19 based on neighboring aware representation from deep graph neural network. International Journal of Intelligent Systems, 37(2):152--1598, 2022.
[43] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In 10th International Conference on Learning Representations (ICLR), 2022.
[44] Brandon Malone, Alberto Garcia-Duran, and Mathias Niepert. Learning representations of missing data for predicting patient outcomes. In Workshop on Deep Learning on Graphs: Method and Applications (AAAI), 2021.
[45] Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-44 2001.
[46] Alessio Micheli. Neural network for graphs: A contextual constructive approach. IEEE Trunsuctions on Neural Networks, 20(3):498-511 -11, 2009.
[47] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAT), volume 33, 2019.
[48] Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášek. Attending to graph transformers, arXiv preprint Stti::2002004888) 2023.
[49] Galileo Mark Namata, Ben London, Lise Getoor, and Bert Huang. Query-driven active surveying for collective classification. In Proceedings of the Workshop on Mining and Learning with Graphs (MLG), 2012.
[50] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural networks for graphs. In Proceedings of the 33rd International Conference on Machine Learning (ICML), 2016.
[51] Il-Seok Oh, Jin-Seon Lee, and Ching Y. Suen. Analysis of class separation and combination of class-dependent features for handwriting recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21 21(10):089--194 1999.
[52] Luca Oneto, Sandro Ridella, and Davide Anguita. Do really need new theory understand over-paramettriiztionn? Neurocomputing, 543, 2023.
[53] KB Petersen and MS Pedersen. The matrix cookbook, version 20121115. Technical report, Technical University of Denmark, 2012.
[54] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? In 11th International Conference on Learning Representations (ICLR),
2023.
[55] Lutz Prechelt. Early stopping-but when? Neural networks: tricks of the trade: second edition, pages 53-67, 2012.
[56] Rahul Ragesh, Sundararajan Sellamanickam, Arun Iyer, Ramakrishna Bairi, and Vijay Lingam. Hetegen: heterogeneous graph convolutional networks for text classification. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining ( (WSDM), 2021.
13

---

[57] Russell Reed and Robert J MarksII. Neural smithing: supervised learning in feedforward artificial neural networks. Mit Press, 1999.
[58]
Frank Rosenblatt. The perceptron: probabilistic model for information storage and organiza- tion in the brain. Psychological review, 65(6):386, 1958.
[59] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 2061),6 2009.
[60]
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93 2008.
[61] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Workshop on Relational Representation Learning, Neural Information Processing Systems (NeurIPS), 2018.
[62] Vikas Sindhwani, Partha Niyogi, and Mikhail Belkin. Beyond the point cloud: from transductive to semi-supervised learning. In Proceedings of the 22nd International Conference on Machine Learning (ICML), 2005.
[63] Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 833):714-735, 1997.
[64] Charles Sutton, Andrew McCallum, et al. An introduction to conditional random fields. Foundations and Trends@ in Machine Learning, 4(4): 2012.
[65] Catherine Tong, Emma Rocheteau, Petar Veličković, Nicholas Lane, and Pietro Liò. Predicting patient outcomes with graph representation learning. In Al for Disease Surveillance and Pandemic Intelligence: Intelligent Disease Detection in Action, pages 281-293. Springer, 2022.
[66] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain. Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In 10th International Conference on Learning Representations (ICLR), 2022.
[67] Domenico Tortorella and Alessio Micheli. Leave graphs alone: Addressing over-squashing without rewiring. In Proceedings of the 1st Conference on Learning on Graphs (LOG), 2022.
[68] Vladimir Vapnik and Vlamimir Vapnik. Statistical learning theory wiley. New York, 1(624):2, 1998.
[69] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations (ICLR), 2018.
[70] Jeroen K Vermunt and Jay Magidson. Latent class cluster analysis. Applied latent class analysis,
1 (06),,0 2002.
[71] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 1 11(Ap))11011-1222, 2010.
[72] Yue Wang, Yonghin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph can for learning on point clouds. Acm Transactions On Graphics (tog), 385))11-12, 2019.
[73] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4224, 2020.
[74] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations (ICLR), 2019.
[75] Chengxuan Ying. Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS), 2021.
[76] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-revised convolutional network. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMI. PKDD), 2021.
[77] Xiang Yu, Siyuan Lu, Lili Guo, Shui-Hua Wang, and Yu-Dong Zhang. Resgnet-c: A graph convolutional neural network for detection of covid-19. 19. Neurocomputing, 452:592-608 2021.
14

---

[78] Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey, IEEE Transactions on Knowledge and Data Engineering. 34(1):249-22 270, 2020.
[79] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Proceedings of the 34th Conference on Neural Information Processing Systems (NeurIPS), 2020.
15

---

A Appendix
A.1
Dataset Statisties
This section shows the main statistics of the datasets used in this work.
Table Datasets' statistics.
# samples
# attributes
# classes
Abalone
4177
8
3
Adult
48842
14
2
DryBean
13611
17
7
eGrid
10000
14
2
Isolet
7797
617
26
Musk
6598
168
2
Occupancy
20560
2
Waveform
5000
40
3
Cora
2708
1433
7
Citeseer
3327
3703
6
Pubmed
19717
500
3
A.2 Hyper-Parameters Tried
The table below specifies the configurations tried by the model selection procedure for all the baselines considered in this work. We apply satience-based early stopping technique the validation Micro Fl-score as the only regularization technique [55]. The free parameters' budget of all three baselines the same. We used Adam to train all models.
Table 3: Sopper-aaramtery tried during model selection for all the benchmarks of the paper. Note that in GCN the use of the normalized Laplacian implies a mean aggregation.
# hidden units
# layers
learning rate
epochs
patience
aggregation
MLP
32/64/128
1/2/3
le-2/1e-3
5000
1000
sDGN
32/64/128
1/2/3
le-2/1e-3
1/3/5/10
5000
1000
GIN
32/64/128
1/2/3
le-2/1e-3
1/3/5/10
5000
1000
sum/mean
GCN
32/64/128
1/2/3
le-2/1e-3
1/3/5/10
5000
1000
mean
The following table, instead, reports the configurations tried during the qualitative experiments. We
still apply patience-based early stopping technique LSED.
Table Hyper- paraamearssesers tried for the qualitative experiments.
D
[M|
[c]
learning rate
epochs
patience
2, 10, 50
5, 10
2,
0.0, 1.0, 5.0, 10.0
le-2
10000
3000
16

---

A.3 Proofs
Proposition
3.3
Under assumptions 1,2, Mc E) has the following analytical form
M
D
p(c) p(mlc)
II f=1
(Zzems (xz+ Fzzms (zg- - ))
(1I)
Pemf where c is a E. with Gaussian distribution / Pe: Pemp).
Proof. Thanks to the conditional independence assumption, we can compute the integral of product as product of integrals over the independent dimensions. Defining a 2 2 and by I + 2. we have
/ (m)
E E (a) (t)
c/w)] p(c)
p(alccddw
(12)
MMI
= =p(c)
pmw/m, c))(m))d
(13)
WE (mr) (ar)
m=1
IMI
p(c)
p(mlc)
p(u|m, c)dw
(14)
WwHHe (w)
IMI
bi
bn
= p(c)
Σ p(m|c)
II f=1
play (m, cjdwD.... dun
(15)
m=1
IMI
p(c)
Σ p(mlc)
II
p(wylm, c)dws
(16)
m=1
f=1 Jay
IMI
= p(c)
p(mlc)
II
FZemy (xs + 2) --Fzmm FZzms (0g (01-2)) 2)
(17)
where Zemz (emo/ oem
and the last equality follows from the known fact p(a S X S b) F(b) F(a).
We introduce the following lemmas that will be useful in Theorem 3.5 and Theorem 3.8 which are about addition, linear transformation, and marginalization involving mixtures of distributions.
Lemma A.1. Let X, Y be two independent random variables with corresponding mixture distribu- tions Φx (w) = Ei= (e)e( and (w) Σÿ= (ydj(w). Then Z X + Y still follows mixture distribution.
Proof. By linearity of expectation the moment generating function of X (and analogously Y) has the following form
(t) = Eje" w1
( (
e" x
(18)
| t" 1 asf((w)d
(19)
Σ Mx. (t)
(20)
where X; is the r. corresponding to component of the distribution. Using the fact that the moment generating function of Z X Y is given by Mz = Mx (t), we have that
ΣΣ 3 Mx. (t) (t).
1
Mz(t)=
a; Mx (1) (1)
By My, (t)
(21)
1=1
==
2.y=,+YY,
17

---

Therefore, Z follows mixture model with IJ components where each component follows the distribution associated with the random variable Zij +x++,, +Y,
Lemma A.2. Let X be with multivariate Gaussian mixture distribution dx(w)) Ei a;N(W pi, E.), u E TRD. Then Z AX,A RDDD still follows a mixture distribu- lion.
Proof. Using change variable 2 Aww we have
(z(w) = Φx (A ww)leed 11 = Σ o,NNAA-uu ps: 2,) det(A -)]-
(22)
By expanding the terms, we see that the distribution of still a mixture of distributions of the following form
kz(w) Σ
Ap,
(23)
Lemma A.3. Let X, Y be two independent random variables with corresponding Gaussian mixtures
of distributions ox (w) El= aN aNN Hx, oxx) and (w) ΣS= 3,N(w: ,y,, ,y,, Then
Ex[Pr(w)] = / (x))))x())dd j=1 Vo;; + xxx
px. MYs
(24)
Proof. It is useful to look at this integral from probabilistic point of view. In particular, we know that
PV XXX w) p(Y s w) (w)
(25)
and that, by marginalizing over all possible values of X,
p(Y x) / p(x xxXx = w)p(X w)dw [F(())x(w)ddx
(26)
Ex (w))
Therefore, finding the solution corresponds to computing p(Y X < 0). Because X,Y are
independent, the resulting variable Z = X is distributed (using Lemma A.l and Lemmal A.2
(z(w)= Σ Σ ar a,B,N(w; Mx + +
(27)
and hence, using the fact that the c.d.f. of a mixture of Gaussians is the weighted sum of the individual components' c.d.f.s:
μx: -KY,
p 50
3 $
(28)
08 + +0x,
18

---

Theorem 3.5
Under assumptions 1,2, Mc (C,E) has the following analytical form
Voams odmis ))
M
D
p(c)
plm'le') (mmpc))))
II f=l
Φ
Pem's + Momp
+ Hem's 1 - Home
Voms + oem's
(29)
Proof. The proof relies on the previous Lemma A.3 We begin by expanding the formula and using the result of Proposition 3.3 We define the r.v. Zims N(w; Him f of fmm)) to write
pxpppl (Ma (c)
(30)
IMI
= =ʃ p(c)
Σ p(mlc)
II
Fzoms
(zs+ + ()) Fzoms (zs- (-) placle
(31)
f=1
M
p(c) /
p(mlc)
II
Fizmy (IF + [)) -Fzemm (is =)
Σ mu
plalmn umm,,', (D)pmllee) 1c))
de
[=1
(32)
p(c)
p(ml p(m'lc') (m)le)
II
PZoms Bs +5) Fzzms (o) - 5) plarlmn ,e
(33)
fm1
[MI
/ II Fizms (1s (2s+ + 2) -Famms
D
p(c)
p(m' 1e (m)
-Fems (x) - 2)) II
pla//mm, , c')dd (34)
f=1
m
IMI
p(m' le (m(l)))))))))m)mm)))))) / / --I
II FZzms (0/+ ()) -Fzms (2) (z)- () p(( e'
p(c)
d') (35)
IMI
D
p(m' p((m))))) II (Fzems (2z + +) FFzms (zg- 2) playylmm, dd)d (36)
p(c)
[MI
p(c)
p(m' (en'le')) (m(l))))
II
Fzems (wg + +) plas playlmm, ,'',d'drr; Fzems (x, - 2 plaz Imm, d')drs
(37)
f=1
1 (1)
R2 / PP (144- 5)1
We first note that Fzemf (x + ( Fr(xy) where Y follows distribution N (w; Pemf (and symmetrically for Fzoms (xg {)),, so we can apply Lemma A.3 and obtain
))
M
p(c)
Σ
p(m' Ie' (m(ml)
II f=1
Pemey + Hems
Pemms Home
Voems + 02
Vo'ns + o2mer
(38)
19

---

Proposition 3.7
around 00 and not tending infinity for - == (i) be different from O in an open interval Then, under assumptions 1,2, Equation has
Let the first D derivatives of Σ |c|
the following limits (the first of which requires the assumptions)
plo) Σ
MM
m= p(mlc)p((m (c) II ommm' (0)
lim Pe (c) 6-+0
m
lim Po (c, = p(c) 60000
p(mlc)p(mm(cc) II Oz cmmm's (0) p m=
(39)
where Zimms' has distribution M(; aimm'' f 5 (immemm) f)s
f 2(peemes (amm) and bimmn f =2 2 0mmm /om0m
02 cmmf
Proof. The second limit follows from lim, +00 ( = and lim - ((x) = 0. As regards the first limit, we first expand the terms
(
MM
(Øl
steemm'l)
4
bommly
Bemm's
lim Pe (c,E) e-0
lim e00
m
CC
M
(ttommmm))
p(t)
Dmmm'
=1
(40)
where aimm's 2(pomm's fimmf) and bimm's 2 + Jem's Vi E C to simplify the notation. By defining Zimm's ~ N(; Osmm' f: by Dmmmn') I)
rewrite the limit
p(c)
Σ MM
p(mlc)p(mm))) 17- Pz Firemmn ( Piremmnt (-E)
(41)
6
p(i)
Σ p(mli)p(m')))) II?- Fzrmm' Rammm,(( (E) F E'zmn'' (-5)
m==1
m
p(c) Σ
[M
p(mlc)((mm() (c) II domm' y (e)
lim 2-0
(42)
Σ p(i)
p(mli)p(m'((c) II? dimmn' 1 (())
Both the numerator and denominator tend to zero in the limit, so we try to apply L' L'Hôpital's 's rule, potentially multiple times.
For reasons that will become clear soon, show that the limit of the first derivative of each term in the product is not zero nor infinity:
lim 6
immm
(s)
lim
(Zeenn'' (5) + d Z ( 2m cmm's (0):
(43)
5-0
In addition, let us consider the n-th derivative of the product of functions (by applying the generalized product rule):
II 1=1
D
demms (()) (n)
Σ
( n ),."".
II 1=1
(is) Anne p(e)
(44)
+jD=n JI.... jD
and we note that, as long < D there will exist assignment to jr 0 fff in the summation, and thus the limit of each product will always tend to 0 when e goes to since the individual terms cannot tend to infinity for assumptions. However, when we take the D-th derivative, there exists one term in the summation that does not go to 0 in the limit, which is
(L.D.
D
)
I
D
(
= D!! II
D
C (E)
(45)
1
F=1
f=1
D
lim -0
D
II
(
2 D!
Oz m (0)(z)
(46)
1,...,,
20

---

Therefore, by applying the L' L'Hópital's 's rule D times, we obtain
p(c)
M
p(mle)p(mm(c)]1 demm's f (e)
lim
(47)
C
M p(mll)p(mm(cc) IT dimm' (()
p
p(c) Σ JM
p(mlc)p(mmlc II WZemm's (0)
m==
(48)
Σ
p(i) p(mli)p(m' (c)
[T 2Zomm'y (0)
However, to be valid, L'Hôpital's rule requires that the derivative the denominator never goes to for points different from 0. This is part of our assumptions, hence conclude the proof.
For = 1 we can show that this last requirement holds as e damm' f (e) if and only if e 0. In fact,
(E) > 0 Ve, dammns ((6) 2 0, and
III
damm' (e)) (1) Σ
(e)))
II t f=1
(ir smm' y
(49)
f=1
is a sum over terms that are all greater than 0 for + O.
Analytical form of the n-th derivative of E (i) To verify if the hypotheses of Proposition 3.7 is true given the parameters of all features' distributions, one could compute the n-th derivative of the denominator w.r.t. & and check that it is not zero around O. We start again from
III f=1
D
demm'
( (5)
(n)
(.......i 31 +Jo=n SiD
E
G
n2
II
domn y (E)
(50)
and we proceed using the fact that the n-th derivative of the standard normal distribution S NO, 1) has well-known form in terms of the n-th (probabilist) Hermite polynomial He,, (z). We note the following equivalence:
W + aiime''
Zemm's (w) =
bimm's Φs(
(51)
bimm' f
hence write
d(a) d f(E) ( = (0z (E) oz (=)mm
(E))(n-1)
(52)
(0zemn', (n)) (0z (1-))
(53)
+ aimm' 1 (n-1)
"iim'' Øs(
(54)
bimm's
Oiimen $ In-1)
+ bimmyy / Øs(
(55)
bimm's f
1
(0s(
+ Oimmm' $
(n- (0s(
aémam' S (n-11)
(56)
bimm's
bimm's f
bymm't f
1
(NI
E + asmm! f 0. ()) + (N( + aimem' 1 0, 1))
(57)
=bmmn'f
bimam'
Dimmis $
1
(-1)m-2H4 He He E+ Gémm'' I )os( E Odmmm's
=bimn's
bimm's
bimm's f
+ ((11)-11He, He,
- aimmm' f
Vos( - aimen's
D 2))
(58)
bimm' f
Dimm's
21

---

We use this result in the expansion of Equation 50
Σ
II
(is) imm (c)
(59)
JD
tit-
f=1
Σ
Ci.....
n
II 1-1.DD
dimm f (e).
(60)
jn)
31 ti
1520 /=1...
However, we can readily see that computing the derivative for a single has combinatorial complexity, which makes the application of the above formulas practical only for small values of D.
Class Separability Analysis of Section 3.2
We now present a result that will help us compute the
SED divergence between two Gaussian mixtures of distributions.
Lemma A.4. Let X,Y Y. be two independent random variables with corresponding Gaussian mixture distributions dx (w)) Ei=10s 0sfx((w)
E (w: μº²" EXx) and Φy En-1 Byfy, (w) = Σ B,N(w: u. Σn) w E R.P Then the SED divergence between (x(w) and Φy (w) can be computed as
SED(Ox,
Σ
aga Ai,
8,8,Ba, - ΣΣ
- a Og,3Ci.5.
(61)
iml
6=1
where
(62)
Aijj = No x (EF )X())
(63)
B1 -N(H) M4 (D) + /
(64)
Ci. -NV(N m. (EX + E ))
(65)
Proof.
(r) (Øx((x)) (r()))
(66)
2
SED(ox,or) /
Σ aifx Σ 3,fr dw
(67)
ΣΣ a:ay / (x)( (w) +
J J
BrB, / fr (w))
Σ> 1=1
(68)
i=1
2 ΣΣ 0: / fx( (w)dw.
(69)
==
Finally, we can compute the integral of the product of two Gaussians as follows (Section 8.1.8 of
53
J NN mn, En (wo (w: μ2, Σ2)dwr = (11 /4, (E) + Ez))
(70)
obtain the desired value.
Under assumptions 1.3, let assume that the entity embeddings of l-layer DGN applied on an artificially built k-NN graph follow the distribution Equation [0] Then the Squared Error Distances (pD((()))) ph((')) and SFD(pp(z)c), p(x)(c) have analytical forms.
Proposition 3.8
Proof. First, we have to show how we can compute the conditional probabilities p(h|c) and p(hle") and then we derive the analytical computation of the SF.D divergence to verify the inequality in similar manner of Helén and Virtanen (33].
22

---

We first work out the explicit form of p(hlc),, by marginalizing out æ:
IM
/ Σ
p((cc)
(71)
Σ p(mlc) / p(hlx))p(z/mm.)) c)dx
(72)
IMI
Σ p(m/))
N( As Ac) pomes Emo) )
(73)
E p(mlc) / NN(h x; A.)) Mmes me)
(74)
Gaussian convolution
[M] p(mle)N(h;; Mmme Emo + Ae).
(75)
Therefore, the distribution resulting from the k-NN neighborhood aggregation will change the input's variance in way that is inversely proportional the number of neighbors. In the limit of k: oo and finite it follows that p(hlc) p(æ|c). Since p(h(c) still follows mixture of distributions of known form, we that repeated aggregation of the neighborhood aggregation mechanism (without any learned transformation) would only increase the values of the covariance matrix. In turn, this would make the distribution spread more and more, causing what is known in the literature the oversmoothing effect (see Section 2).
Since both X, and He follow Gaussian mixture distribution, apply Lemma A.4 obtain closed-form solution and be able to evaluate the inequality. In particular
SED(ox... (xx))
(76)
p(mlc)p(m' (epl))p(m'ccW/((( C)N(eemm Mem' Dem + Exom
(77)
Σ
p (NN perimt Eiem + Deetm
(78)
2
(mm)) ple'n', Dam Ddieee
(79)
and
SED(on. )H,))=
(80)
[M]
p(mlc)p(mm (atpppmmnee))/W(( (c)
pem' Eom + Ecm + 2Ag)
(81)
[
(omlc')p(m'lee))) ( Pe Eem + De'm + 2Ag)
(82)
=1
M
2
p(mlc)p(m' (e)N(uemmi me Eom + Ed'm + +AA)).
(83)
m =
23

---

As an additional remark, if SED( (H.)) SED( (xx, (x2), points in the DGN's ' latent space will be easier to classify than those the input space because the former pair of distributions are more separable than the latter.
We also observe that p(h(c) is mixture of Gaussians that differs from p(z]cc)oll in the higher variance of the individual Gaussian components. In other words, the distribution of p(h(c) looks "flatter" than p(æ|c). At least one two-dimensional space, flatter distributions p(f](c and p(hlc') should therefore increase the overlap (and therefore decrease the SED) compared to the SED the original space. This intuition, despite its simplicity, is unfortunately hard prove for technical reasons, for instance the dependence of the distance value on the specific parameters μ and E.
A.4 Impact of the Metric in the Construction of k-NN Graphs
To judge how much the results might change if used different metric, test the cosine similarity as done in [56]. We note that the cosine distance is less expressive than the Euclidean distance as does consider the magnitude of values, and that results overall worse performances. DGNs typically work in the Euclidean space when aggregating neighbors, hence the homophily assumption be imposed to a certain extent only by computing nearest neighbors in terms of Euclidean distance. In addition, building k-NN graphs using the Euclidean distance criterion has an easy interpretation terms of "how similar the attributes of adjacent nodes are". We observe that the results below still agree with our theoretical intuitions and empirical results.
Table 5: Node classification mean and standard deviation results for structure structure-ggnostie baseline (MLP) compared to graph machine learning methods applied to artificially built k-NN graphs. We performed model selection w.r.t. the F1 score, but we also include the accuracy for completeness. Here, k-NN graphs are built using the cosine similarity as metric.
MLP
sDGN
GIN
GCN
F1
ACC
F1
ACC
F1
ACC
F1
ACC
Abalone
0.55
55.5
0.55
55.5
0.55
55.2
0.55
55.1 (1.9)
Adult
0.70
77.641.7
0.64
79.0
0.69
79.5
0.53
76.4 (0.6)
DryBean
0.78
77.4+4.0
0.77
77.0+5.0
0.79
78.2+2.
78.2 0.78
eGrid
0.95
95.610.6
0.84
85.8
0.93
93,940.8
0.81
82.6 (1.4)
Isolet
0.95
95.410.5
0.93
92.7.110
0.95
94.811.0
0.90
90.6 (4.1)
Musk
0.99
99.310.3
0.96
98.010.6
0.93
96.242.5
0.93
97.1 (0.7)
Occupancy
0.99_n..1
98.940.4
0.99
98.640.3
0.99
98.940.3
0.95
(4.8)
Waveform
0.85
85.5
0.84
84,0+1.4
0.84
84.141.6
0.82=n.03
Cora
0.71
74.342.4
0.71
74.1
0.72.0.02
75.5
0.72.0.03
(2.3)
Citeseer
0.69
71.8+1.9
0.69
71,8+1.8
0.70
73.7+1.3
00.9
71.7 (2.4)
Pubmed
0.87
87.640.7
0.84
83.8+0.7
0.86
86.740.8
0.84
83.7 (0.6)
24

---

A.5 Analysis of CCNS approximation's quality
In the figure below, we visualize how the CCNS gets closer to the MC approximation when the number of neighbors & increases for random data distribution with 5 classes. The choice of the e parameter for the MC estimation of the CCNS has marginal impact here. This behavior is expected, because as k increases we get better approximation of the posterior class distribution in the hypercube around each point, which is the one we computed in Section 3.1 When too small, the empirical (true) CCNS might be more unstable and dataset-dependent
0.59
0.6
0.61
0.6
0.61
0.61
0.59
0.6
0.59
0.61
0.6
0.59
0.61
0.01
0.56
0.8
0.59
0.61
0.6
0.6
0.58
0.38
0.39
0.39
0.39
0.37
0.39
0.39
0.39
9.4
0.39
0.39
0.39
0.39
0.42
0.39
0.39
0.47
0.35
0.99
0.37
0.39
True CCNS for k-25
0.34
0.35
0.35
0.35
0.34
0.35
0.35
0.35
0.36
0.36
0.38
0.3
0.36
True CCNS for k-30
0.33
0.32
0.34
0.34
3
True CONS 10=
0.32
0.24
0.32
0.3
0.32
0.92
0.25
0.31
0.29
0.31
0.29
0.31
0.25
Figure 5: Comparison of the true CCNS for varying values of and the MC approximation according our theory for random initialization of 5-class data model.
25

---

A.6 Best Configurations and Ablation Studies
In the figure below, we show which are the best and & values picked by the models trained for the qualitative experiments.
30-
30
Count
20-
20
10-
10-
12
Figure 6: We show the histograms of the learned & and for the different configurations of Table 4 It appears that lower values of both parameters are preferred by the trained models.
Analysis of Chosen Hyper-parameters For completeness, in the following we display the best & number of layers, and number of hidden units chosen by the different families of models on each dataset of [ We recall that for each dataset and model there are 10 best configurations due to the use of 10-fold cross validation for risk assessment [22]. We did not find any significant pattern except for SDGN preferring lower values of k and the DGNs often choosing at least 2 convolutional layers.
abalore
adult
drybean
TeAlS
CP CCN
CCH
10
10
10
electricatgrd
modie H4. 100M
T50M HLP
MLP OCN
12
ocoupancy
LOOM
Chant
channerr
pubmed
model
(DoM
ST0M
Figure 7: Histograms of the 1 chosen by each model on the different datasets during a 10-fold cross validation for risk assessment.
26

---

drybean
MGP
Core
electricalgrd
Isalet
musk
chokk
COGN
Coat
bocupancy
woveform
modd
eook Gii
GNU
GCN
GCN
GON
laye's
Figure 8: Histograms the number of layers chosen by each model on the different datasets during 10-fold cross validation for risk assessment.
27

---

NLP
Core
Falie usas
electricalgrdd
Isalet
musk
COGN
Cont
pccupancy
waveforrm
Prace: GAN
riode
KOGA Gif GOL
Git
302
120
23
120
Gil GOV
10000 2113
Figure 9: Histograms of the hidden units chosen by each model on the different datasets during 10-fold cross validation for risk assessment.
28

---

Ablation Study We now provide ablation study of the validation performances of the models during the model selection phase (i.e., across possible configurations). We show the ablations for the most important architectural choices of the syper-parameters Also in this case, a lower is associated with better performances, but there does not seem to be marked improvements when using more than 1 graph convolutional layer.
drybcan
HELP AETOO
ML-
22-
electricalgrid
lsolet
musk
100
100
703
15
ecoupancy
waveform
cora
1.0
90
mode
72-
DCM
CM
CCN
CO
10
50
72
70-
HALF MOCM
DCM
Figure 10: Ablation study for the & chosen by each model on the different datasets. We report the validation performances computed during model selection for all configurations tried.
29

---

drybean
100
30
20
Uovers Isolet
electricalgrd
musk
JOCM
LOCN
211
CH
CAN
eccupancy
Wavvefomm
cora
11:50
CCN
MLD
PLL
Figure 11: Ablation study for the number of layers chosen by each model on the different datasets. We report the validation performances computed during model selection for all configurations tried.
30

---

drybcan
MLY CO
JOCM
JOCM
#
electricalgrd
loolet
musk
100
80-
JOCM
LDCK
42
2314
CNN
ocoupancy
waveffom
cora
100
TOCKI
CIN
CCN
CCN
64
325
120
50
HLP
$2.5
PAL
teidden unif
Figure 12: Ablation study for the hidden units chosen by each model on the different datasets. We report the validation performances computed during model selection for all configurations tried.
31


Reviews:
[{"review_id": "uKUahJAVzK", "reviewer": "Reviewer_VEGV", "summary": "This paper proposes to investigate the practice of using nearest neighbour graphs build upon tabular data in order to classify samples (then relying on a node classification model). The authors note that this practice has been shown to be relevant in the semi-supervised case, but not with full supervision - and that it often exploits the common idea that homophily is a desired graph property for node classification models. However, recent works shows that the difference between the distributions of labels of neighbours for nodes of separate class (measured by the Cross-Class Neighborhood Similarity, CCNS) is what matters for their efficiency. This brings the authors to propose (1) a formal model for computing an approximation of these distributions under several assumptions (2) under the same assumptions, study the separability of classes induced by a simple node representation model relying on message passing on the NN-graph. \nThe authors then propose two sets of experiments to draw conclusions: (1) an study of the results of learning classification models directly on tabular data or on NN-graphs for 11 tasks (2) qualitative experiments relying on their theoretical work, verifying if, for a toy task of binary classification based on simple distributions built following their assumptions: (a) there exists of configuration where classes are more separable using a NN-graph structure (b) the quantities obtained via their approximation of CCNS concurr to the conclusion of (a). ", "questions": "- The purpose of the CCNS approximation proposed is a little unclear. Is it supposed to be a practical tool for testing the relevance of the k-NN graph for a classification task ?", "limitations": "- Limitations have been adequately addressed. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- This paper is very well written, and easy to follow, despite the difficulty of the subject.\n- This paper demonstrates experimentally that using nearest neighbour graphs build upon tabular data in order to classify samples does not help performance. \n- This paper provides well-motivated theoretical arguments showing that a model built on message-passing for a k-NN graph will not improve class separability.\n- Finally, this paper provides a theoretical framework (under assumptions) to build a tool, allowing to approximate the CCNS (an indicator of potential success of node classification models).", "weaknesses": "- While the paper clearly discusses the limitations brought by the assumptions it makes, it would be interesting and useful to explore how significant they are.\n- The utility of the theoretical developments for the experimental demonstration is not made completely clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the reviewer found our work well presented and motivated. Below, we comment on the points raised by the reviewer, hoping that it will better clarify the scope of this work.\n\n**Q:** While the paper clearly discusses the limitations brought by the assumptions it makes, it would be interesting and useful to explore how significant they are.\n\n**A:** A challenge, common to all theoretical machine learning problems like this one, in verifying how impactful the assumptions are is that we do not have access to the true data generating distribution of real-world datasets. \n\nFor instance, analyses that focus on variable correlations cannot ensure that there is a real causation between variables in the dataset, so the assumption of independence cannot be easily verified.\n\nHowever, we have at least empirically tested the impact of non-linearities on the results by comparing sDGN with GIN and GCN, and we have observed no influence on the performances. In addition, the use of a mixture of Gaussians in the data generating model allows us to represent any distribution with a sufficiently high number of mixtures, so it is not a limiting assumption.\n\n**Q:** The utility of the theoretical developments for the experimental demonstration is not made completely clear.\n\n**A:** Improving the theoretical understanding of a phenomenon can influence the discovery of new practical methods, but not all theoretical insights have an easy and straightforward application. The theoretical developments of Section 3.1 are the first steps of a longer-term research plan on how to build *useful* synthetic graphs from tabular data, and to the best of our knowledge we are the first to do this from a theoretical perspective.\n\nIn contrast, the theoretical studies of Section 3.2 are more directly related to the evaluation of various methods under the k-NN graph construction, which is why we could provide a thorough empirical analysis on that end.\n\n--\n\nWe hope to have addressed the doubts of the reviewer, but please let us know if we should further clarify some aspects of our work. Thank you again for the constructive feedback.\n"}, {"review_id": "Z21i11rgOd", "reviewer": "Reviewer_Cqgk", "summary": "The main contributions of this paper are as follows:\n\n1. The authors of the paper study Cross-Class Neighborhood Similarity (CCNS) for nearest neighbor graphs and provide its first lower bound. \n2. They apply a Deep Graph Network (DGN) to an artificial k-NN graph and study how it affect the class separability of the input data. \n3. They carry out a robust comparison between structure-agnostic and structure-aware baselines on a set of 11 datasets, and their results are in agreement with their theoretical results. \n4. Qualitative analyses based on the theory further suggest that using the k-NN graph might not be advisable.\n\nOverall, the authors introduce a theoretical framework to understand the benefits of Nearest Neighbor (NN) graphs when a graph structure is missing and provide both theoretical and empirical evidence to support their conclusions. They try to raise awareness about the potential limitations of k-NN graphs for node classification tasks and advocates for the study of alternative graph construction techniques.", "questions": "1. How does your work relate to other dataset formats more than tabular data?\n\n2. How would your conclusions apply to other settings, such as the semi-supervised setting where only a subset of training labels is available?", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The authors introduce a theoretical framework to understand the benefits of Nearest Neighbor (NN) graphs when a graph structure is missing.\n2. They provide a formal analysis of the Cross-Class Neighborhood Similarity (CCNS) in the context of nearest neighbor graphs and provide an analytical computation of the CCNS for Nearest Neighbor Graphs.\n3. They carry out a robust comparison between structure-agnostic and structure-aware baselines on a set of 11 datasets that is in agreement with their theoretical results.\n\nOverall, this paper provides both theoretical and empirical evidence to support its conclusions and makes a contribution to the understanding of the benefits and limitations of using k-NN graphs for node classification tasks. ", "weaknesses": "As the authors mentioned in the paper, they assume that the attributes are conditionally independent when conditioned on a specific mixture and class. These assumptions may not hold for all datasets and could limit the generalizability of their results.\n\nAdditionally, the authors’ analysis is focused on the fully-supervised setting, where all training labels are available. It is not clear how their conclusions would apply to other settings, such as the semi-supervised setting where only a subset of training labels is available.\n\nOverall, while this paper provides valuable insights into the benefits and limitations of using k-NN graphs for node classification tasks, its conclusions are based on specific assumptions and conditions and may not apply to all situations.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the merits and strengths of our work. Below, we will address the comments and questions that have been raised.\n\n**On the independence assumption**\n\nThe conditional independence assumption has been widely used in the graphical models literature because it is particularly attractive from a theoretical perspective [*], despite it cannot cover all real-world cases. \n\nWe also want to remark that this assumption is only needed in Section 3.1 to approximate the CCNS, and it is not required in Section 3.2 which deals with the more practical problem of class separability induced by DGNs.\n\nAssumptions 1 and 3 are still quite reasonable considering the flexibility of mixture models and the nearest neighbors construction (line 148). In addition, we tested the non-linear assumption of Section 3.2 empirically, and we showed that it does not affect the analyses of Section 3.2.\n\nOverall, the results we have obtained help us better understand the observed behaviour of models under speficic conditions, but they also pave the way for other researchers to extend these results to more general scenarios, which is usually the case for theoretical works.\n\n[*] Sutton, Charles, and Andrew McCallum. \"An introduction to conditional random fields.\" Foundations and Trends in Machine Learning 4.4 (2012): 267-373.\n\n**On the fully supervised setting**\n\nOur results do not apply to the semi-supervised setting: it has already been shown in the literature (lines 31-48) that a k–NN graph can help in the semi-supervised setting, possibly due to a regularizing effect that prevents overfitting of the few labels.\n\nFor this reason, we study the only alternative scenario where the above conclusions have not been comprehensively tested yet, and our theory suggests an opposite result in the fully supervised context. \n\n**Q:** How does your work relate to other dataset formats more than tabular data?\n\n**A:** Our work is specific to tabular data tasks that are transformed into node classification tasks, as it is becoming a more and more common approach.\n\n**Q:** How would your conclusions apply to other settings, such as the semi-supervised setting where only a subset of training labels is available?\n\n**A:** please refer to our considerations above.\n\n--\n\nWe hope to have adequately addressed the reviewer’s doubts. Please let us know if there is something we should further clarify.\n"}, {"review_id": "2kw0a6mCD0", "reviewer": "Reviewer_CVih", "summary": "This submission provides a theoretical framework to explore the benefits of Nearest Neighbor (NN) graphs in the absence of a predefined graph structure. The Cross-Class Neighborhood Similarity (CCNS) is formally analyzed to evaluate the usefulness of structures within nearest neighbor graphs. The study also investigates the class separability induced by deep graph networks on a k-NN graph. Quantitative experiments conducted under full supervision demonstrate that employing a k-NN graph provides no advantages compared to a structure-agnostic baseline. Qualitative analyses indicate that the framework effectively estimates CCNS and suggests that k-NN graphs are not useful for such classification tasks. This highlights the need to explore alternative graph construction techniques.", "questions": "N/A", "limitations": "The authors have discussed the limitations.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The theoretical analysis is interesting.\n\n2. The motivation is clear.", "weaknesses": "To be honest, I am not familiar with this topic. I can only provide high-level comments as follows,\n\n1. Equation (2) is not clear. For example, how to derive the equivalent between two absolute values?\n\n2. Figure 2 left is not very easy to be understood. For example, what are the colors mean, and what is the meaning of each line? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read and assess our work. Below we provide an answer to the questions posed.\n\n**Q1:** Equation (2) is not clear. For example, how to derive the equivalent between two absolute values?\n\n\n**A:** The equivalence of Eq. 2 follows from the linearity of expectations and from the fact that $q_c(x)$ does not depend on $p(x|c’)$ and vice versa ($q_c’(x),p(x|c)$), so the two resulting expectations further simplify:\n\n$\\\\mathbb{E}\\_{p(x|c)p(x'|c')}[q\\_c(x) - q\\_{c'}(x')] = \\\\mathbb{E}\\_{p(x|c)\\\\cancel{p(x'|c')}}[q\\_c(x)] -  \\\\mathbb{E}\\_{\\\\cancel{p(x|c)}p(x'|c')}[q\\_{c'}(x')] = \\\\mathbb{E}\\_{p(x|c)}[q\\_c(x)] -  \\\\mathbb{E}\\_{p(x'|c')}[q\\_{c'}(x')] $\n\nThanks for mentioning this, we will add it to the paper.\n\n**Q2:** Figure 2 left is not very easy to be understood. For example, what are the colors mean, and what is the meaning of each line?\n\n**A:** With Figure 2, we want to empirically test whether there exist tabular datasets (following our assumptions) where a nearest-neighbor structure can help to better discriminate the samples. Each curve/color corresponds to a different configuration of hyper-parameters (Table 4 appendix) for the data generating distribution of the dataset.\n\nThe value on the y-curve indicates if the embedding space constructed using $k$-NN graphs and DGNs is more separable than the original space. To be more separable, the value should exceed 1, but we observe that the lines never cross this value and reach an asymptote as we increase $k$. Therefore, $k$-NN graphs do not seem to help when the data generating distribution behaves according to our theory.\n\n--\n\nWe hope to have adequately addressed the concerns of the reviewer. If not, please let us know and we will do our best to further clarify these points.\n"}, {"review_id": "BrtEouoC0t", "reviewer": "Reviewer_Ysph", "summary": "This paper shows that using a k-NN graph in tabular data classification is not beneficial compared to MLP. Specifically, based on Cross-Class Neighborhood Similarity, the authors theoretically induce the analytical forms of the squared error distance (SED) of two approaches. In the experiment, they demonstrate that the SED of the method using a k-NN graph is smaller than the SED of the method using attributes directly. Furthermore, in fully-supervised setting, they show that MLP exhibits comparable performance with methods using k-NN graphs. ", "questions": "- Following [W1], could you provide the correlation between attributes in the real-world datasets?\n- Following [W2], would you provide eivdences about the relation between SED and classification performance?\n- Following [W3], could you provide more evidences that the SED for the methods using a k-NN graph is smaller than the SED of the methods using attributes directly?\n- Following [W4], would you provide the detailed description about analytic forms? Also, I'm curious about the conditions when SED of methods using a k-NN graph gets large based on the analytic forms?", "limitations": "As the authors mentioned, the assumptions seem strong [W1]. ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- They propose a theoretical framework to analyze the method using a k-NN graph.\n- They show that the SED for using a k-NN graph is smaller than the SED for using attributes directly in synthetic data.\n- They demonstrate that MLP exhibits comparable performance with the approaches using a k-NN graph in fully-supervised setting.", "weaknesses": "- [W1] As the authors mentioned, the assumptions seem strong. Especially, for assumption 1, it would not hold that attributes are independent in the real-world data. Also, they fix GNN architecture as GCN in Equation 9, but there exists many effective GNNs.\n- [W2] I understand that SED can be related with performance. However, it seems not enough to exploit the statement that the methods with large SED would show better performance than the methods with small SED.\n- [W3] As far as I understand, the proposed framework gives only the analytic forms of SED and the empirical evidence for SED difference is also suggested in the synthetic setting. It seems not enough to assert that using a k-NN graph offers no benefits compared to a structure-agnostic baseline.\n- [W4] The analysis about the analytic forms does not provided in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for providing constructive feedback. Below, we address the reviewer questions, each of which is related to a specific weakness.\n\n**Q:** Following [W1], could you provide the correlation between attributes in the real-world datasets?\n\nA:  Please have a look at the PDF in the general response to reviewers. We provide the Pearson correlation analysis for two datasets that have few attributes in the pdf attached to this submission. However, we would like to remind the reviewer that *correlation does not imply causation*, hence we cannot still draw conclusions about the form of the true data generating distribution.\n\nIn our opinion, assumptions 1 and 3 are quite reasonable considering the flexibility of mixture models and the nearest neighbors construction (line 148). In addition, we tested the non-linear assumption of Section 3.2 empirically, and we showed that it does not affect the analyses of Section 3.2.\n\nAssumptions 2, instead, is widely used in the literature and make graphical models particularly attractive from a theoretical perspective [*], despite it is also known that they cannot cover all real-world cases.\n\n[*] Sutton, Charles, and Andrew McCallum. \"An introduction to conditional random fields.\" Foundations and Trends in Machine Learning 4.4 (2012): 267-373.\n\n**Q:** Following [W2], would you provide evidences about the relation between SED and classification performance?\n\n**A:** We can mention a few of the numerous works in the literature (see list below) where this relation, in the more general case of distance metrics and not just SED, is discussed and analyzed. Thank you for pointing this out, we will include a clarification with the references in the paper.\n\n- Oneto, et al. \"Do we really need a new theory to understand over-parameterization?.\" Neurocomputing 543 (2023).\n- Biggio and Roli. \"Wild patterns: Ten years after the rise of adversarial machine learning.\" Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 2018.\n- Elsayed, Gamaleldin, et al. \"Large margin deep networks for classification.\" Advances in neural information processing systems 31 (2018).\n- Vapnik,. \"Statistical learning theory.\" Wiley series on adaptive and learning systems for signal processing, communications and control (1998).\n- Oh, Il-Seok et al.,  \"Analysis of class separation and combination of class-dependent features for handwriting recognition.\" IEEE Transactions on Pattern Analysis and Machine Intelligence 21.10 (1999).\n\n**Q:** Following [W3], could you provide more evidences that the SED for the methods using a k-NN graph is smaller than the SED of the methods using attributes directly?\n\n**A:** Because assumptions about data are inevitable, it is very hard to prove that a k-NN graph *never* helps. However, below we provide more theoretically inspired evidence as to why this should be always the case -- at least under our assumptions.\n\nIn the proof of Prop 3.8 (appendix), we observe that $p(h|c)$ is a mixture of Gaussians that differs from $p(x|c)$ only in the higher variance of the individual Gaussian components. In other words, the distribution of $p(h|c)$ looks “flatter” than $p(x|c)$. At least in a one or two-dimensional space, flatter distributions $p(h|c)$ and $p(h|c’)$ should therefore increase the overlap (and therefore decrease the SED) compared to the SED in the original space. This intuition, despite its simplicity, is unfortunately hard to prove for technical reasons, for instance the dependence of the distance value on the specific parameters $\\mu$ and $\\Sigma$.\n\nWe hope this addresses the reviewer's question, but please let us know if there is something else specific we should clarify.\n\n**Q:** Following [W4], would you provide the detailed description about analytic forms? Also, I'm curious about the conditions when SED of methods using a k-NN graph gets large based on the analytic forms?\n\n**A:** Due to space reasons we could not include the analysis in the main paper and had to leave our considerations in the appendix (lines 659-672). We might be able to include those, however, in the camera ready version.\n\nThis is a great question and related to our answer above. Without making assumptions over the values of the $\\mu$ and $\\Sigma$ of the true data generating distributions, one cannot easily see when the SED gets large. However, since the SED of the embedding space seems to be (empirically) always smaller than the SED of the original space and closely related in shape (theoretically), we can argue that the former should get larger as the latter increases. This happens when the class-specific distributions in the original space get farther away from each other, which makes the use of a k-NN graph even less useful because different classes become more separable.\n\n--\n\nWe thank the reviewer for the questions that touch profound points of our work. We hope to have provided satisfactory answers to the reviewer’s curiosity and to have addressed the doubts. We remain available for continuing a constructive discussion should clarifications be needed.\n"}, {"review_id": "F1xK7ox9DS", "reviewer": "Reviewer_MyQ5", "summary": "The paper studies quantitative measures to evaluate the usefulness of k-NN graphs when performing classification in datasets that do not originally come with a known graph topology. The authors argue that the use of k-NN graphs is not useful. ", "questions": "1. In the definition (1), q_c does not seem to depend on the graph structure, unlike the original definition in [39]. How do you incorporate the notion of \"neighborhood\" here?\nIn fact, the whole development in Section 3.1 does not need to assume that we are performing node classification in a graph. Only in (9) do we use the notion of a node's neighborhood. \n\n1. What is the purpose of the derivations in Prop 3.3 - 3.7? These are never used anywhere else in the paper or experiments (except for a very simple synthetic example). While I understand that the authors \"leave these ideas to future investigations\", there should be empirical studies to demonstrate that the results are of interest or useful.\n\n1. The distribution p(\\omega | c) in (3) has not been stated. Looking through the proofs and Prop 3.3, it seems to be assumed to be a Gaussian. Is this reasonable and is there empirical evidence for it?\n\n1. The definition of SED in Prop 3.8 was never properly given. One has to look at the proof to realize the measure used is Lebesgue measure. Why is that when p(\\omega | c) above is assumed to be Gaussian?\n\n1. In the experiments, what distance metric is assumed to construct the k-NN graphs? The performance of different GNN models depends very much on the graph topology. Have different metrics been considered and do the authors' conclusions hold regardless of the metric?", "limitations": "Theoretical assumptions have not been comprehensively tested.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "A study of applying k-NN to construct a graph and then using standard GNN models for node classification. This is compared to using the baseline MLP that does not make use of any neighboring node information. ", "weaknesses": "1. The paper is very heavy on assumptions, especially using the use of Gaussian models to derive certain results. There is no empirical evidence that such models hold in the datasets used.\n\n2. The numerical experiments are not convincing enough. Maybe I misunderstood how the experiments are conducted. A major concern is how the k-NN graphs are constructed and how the GNN models are applied. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing constructive feedback and the opportunity to clarify unclear points. \n\n**W1**: As we better discuss in our answers below, we rely on Gaussian **mixtures** that are known to be universal approximators. In addition, despite not covering all use-cases, assumption 2 is often used in the literature because they are particularly attractive from a theoretical perspective [*].\n\nIn our opinion, assumptions 1 and 3 are quite reasonable considering the flexibility of Gaussian mixtures and the nearest neighbors construction (line 148) in the (implicitly Euclidean) message passing mechanism. In addition, we tested the non-linear assumption of Section 3.2 empirically, and we showed that it does not affect the analyses of Section 3.2.\n\n[*] Sutton, Charles, and Andrew McCallum. \"An introduction to conditional random fields.\" Foundations and Trends in Machine Learning 4.4 (2012): 267-373.\n\n**W2**: We construct the experiment as follows:\n- Every dataset is a set of $n$ samples to be classified. For the GNN models, we construct a single k-NN graph of size $n$ using the Euclidean distance between attributes (see also our answer to the question below).\n- A GNN is trained on top of this graph to carry out the original classification problem as a node classification problem \n\nOur empirical setting follows the rigorous one of [19], trying many configurations for all baselines. Please let us know if we missed something we need to better clarify about this.\n\n**Q:** In the definition (1), q_c does not seem to depend on the graph structure, unlike the original definition in [39]. How do you incorporate the notion of \"neighborhood\" here?\n\n**A:** In nearest neighbor graphs, we can define a maximum neighboring distance $\\epsilon$ from each node/sample. Hence, we incorporate the notion of neighborhood through the use of hyper-cubes (lines 150-152), which represent the set of all possible points (that is, neighbors) around the hyper-cube’s center (that is, the sample of interest).\n\n**Q + Limitations:** What is the purpose of the derivations in Prop 3.3 - 3.7? ... **(partially omitted for space limitations)**\n\n**A:** Improving the theoretical understanding of a phenomenon can influence the discovery of new practical methods, but not all theoretical insights have an easy and straightforward application. The theoretical developments of Section 3.1 are the first steps of a longer-term research plan on how to build *useful* synthetic graphs from tabular data, and to the best of our knowledge we are the first to do this from a theoretical perspective.\n\nThe practical use of these results is left to future works simply because we would require an additional paper to first create an algorithm and then test it properly and convincingly.\n\nWe hope this clarifies the long-term impact of our research and its relevance for future methods. We thank the reviewer for challenging us so that we can better improve the motivation for our studies in the paper.\n\n**Q:** The distribution p(\\omega | c) in (3) has not been stated. Looking through the proofs and Prop 3.3, it seems to be assumed to be a Gaussian. Is this reasonable and is there empirical evidence for it?\n\n**A:** In the graphical model of Figure 1 (left), the distribution $p(x|c)$ (or equivalently $p(\\omega | c)$) is a **mixture of Gaussians** conditioned on the class $c$. It is computed by marginalizing over the possible values of the variable $M$: $p(x|c) = \\sum_m p(x|m,c)p(m|c)$. As an additional remark, mixtures of Gaussians are known to be universal approximators of distributions.\n\nWe will fix the paper accordingly.\n\n**Q:** The definition of SED in Prop 3.8 was never properly given. One has to look at the proof to realize the measure used is Lebesgue measure. Why is that when p(\\omega | c) above is assumed to be Gaussian?\n\n**A:** Thank you for spotting this, we will add the SED definition in the main paper at line 248. As discussed in our previous answer, $p(\\omega | c)$ is a mixture of Gaussians and the SED is the only distance for which there exists an exact, rather than approximated, close-form equation for Gaussian mixtures [29]. \n\n**Q:** In the experiments, what distance metric is assumed to construct the k-NN graphs? The performance of different GNN models depends very much on the graph topology. Have different metrics been considered and do the authors' conclusions hold regardless of the metric?\n\n**A:** We thank the reviewer for the insightful suggestion.  All related works (with the exception of [50] that uses the cosine similarity) rely on the Euclidean distance for two main reasons:\n- GNNs models typically work in the Euclidean space when aggregating neighbors, hence the homophily assumption can therefore be imposed - to a certain extent - only by computing nearest neighbors in terms of Euclidean distance\n- Euclidean distance has an easy interpretation in terms of “how similar are the attributes of adjacent nodes”\n\nOur analysis is set in this context, and we will clarify this in the paper. In addition, we considered the reviewer’s suggestion and ran additional experiments by using the cosine similarity as in [50] to construct the k-NN graphs. As shown in the PDF in the general response to reviewers, in general we observe generally worse performances of the GNN methods using this alternative metric, for instance on Adult and eGrid.\n\nThis makes sense because, in addition to the above considerations, the use of cosine similarity is not “expressive” as the Euclidean distance as it ignores the magnitude of the vectors.\n\n-- \n\nWe hope to have adequately addressed the points raised by the reviewer. as we understand their importance in the final reviewer’s decision especially as regards the need for assumptions in a theoretical work. Thank you again for the opportunity to improve these aspects and we remain available should further clarifications be necessary.\n"}, {"review_id": "mTmgjfyiya", "reviewer": "Reviewer_TGZz", "summary": "This paper studies the machine learning problems on tabular data and convert the problem into node classification. Then, they formally analyze the Cross-Class Neighborhood Similarity (CCNS) and validate the performance on benchmark datasets. ", "questions": "See weakness. ", "limitations": "See weakness. ", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1. The studied problem is very important. \n\nS2. The paper offers theoretical analysis. \n\nS3. The paper is well written and the idea is easy to follow.", "weaknesses": "W1. More baselines are needed, such as other SOTA solutions in long-tail node classification. \n\nW2. Neighbors’ sampling for balanced classes seems to be less novel [1]. The technical contribution is weak.\n\nW3. Introducing graph data for tabular data has been studied a lot [2]. \n\n[1] Implicit Class-Conditioned Domain Alignment for Unsupervised Domain Adaptation, ICML 20\n\n[2] TabGNN: Multiplex graph neural network for tabular data prediction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing that the problem we study is important, and that we managed to present the theoretical ideas in a clear form. \n\nWe address the questions/concerns of the reviewer below.\n\n**W1:** Long-tail node classification baselines deal, depending on its definition, with problem of power-law distributed degrees [*] or variable sized graphs [**]. In our experiments, each dataset correspond to a single graph where all nodes have exactly $k$ neighbors, so the inductive bias of the baselines suggested by the reviewer would not be advantageous in this context.\n\nTo further clarify, the goal of the experimental approach is to show that k-NN approaches are not a panacea that always improves the performances on tabular data. If creating a k-NN graph was really helpful for the task, then we would observe improvements already with \"more basic\" methods like GCN and GIN.\n\n[*] Long-tailed graph neural networks via graph structure learning\nfor node classification, Applied Intelligence, 2023.\n\n[**] On Size-Oriented Long-Tailed Graph Classification of Graph Neural Networks, WWW, 2022.\n\n\n**W2:** We are not entirely sure there is a connection between the referenced paper about unsupervised domain adaptation and what we are currently proposing. Also, our paper is not about neighbor’s sampling for balanced classes. \n\nWe would appreciate if the reviewer could clarify this aspect.\n\n**W3:** We thank the reviewer for suggesting an additional reference to be included in the paper. There are many works, like the ones we mention in Section 2, that generate a graph for tabular data and try to empirically evaluate the performance of graph machine learning methods. However, **none** of these studies approach the problem from a theoretical perspective, and therefore the conclusions these studies draw remain limited to specific datasets.\n\nThe novelty of our work mainly lies in a theoretical analyses that suggest how creating nearest neighbor graphs, and in particular k-NN graphs, might not be helpful to improve the performances in a fully supervised setting. The experimental part is only meant to bring additional empirical evidence supported by the theoretical results.\n\nIn summary, while the introduction of graph for tabular data has been already studied, it is still unclear why and if it makes sense to do it in a fully supervised setup. Our work is the first theoretical study in this direction; we hope to have clarified this aspect.\n\n--\n\nWe hope to have adequately addressed the points raised by the reviewer, but please let us know if further clarifications are needed.\n"}]

Author rebuttal:
We sincerely thank all reviewers for their constructive feedback. We did our best to answer all questions and we look forward to a fruitful discussion.

Attached you can find a PDF with additional results to answer the reviewers' questions. Please note that the Table is partially complete due to running experiments, and we will do our best to complete it or to update you during the discussion period. 

Meta-review: In this paper the authors present a theoretical and empirical analysis for understanding the impact of k-Nearest Neighbor (NN) graphs on classification problems with tabular data, where one does not have an explicit graph structure. Their analysis suggests that under full supervision, kNN graphs do not offer benefits compared to a baseline that doe snot use the structure. The reviewers were mostly positive, nothing both theoretical and empirical contributions. While reviewers also had some concerns and questions, most of them were addressed during the rebuttal process. Overall, the consensus is that this is a valuable contribution  and should be accepted to the conference.
Decision: Accept (poster)