The impossibility of low rank representations for triangle-rich complex networks
C. Seshadhri Aneesh Sharma Andrew Stolman Ashish Goel
cs.LG cs.DM cs.SI stat.ML































Event-Triggered Quantized Average Consensus via Mass Summation
    Apostolos I. Rikos, Member, IEEE
	Apostolos I. Rikos is with Division of Decision and Control Systems, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden. E-mail: rikos@kth.se., 
Christoforos N. Hadjicostis, Fellow, IEEE 
	Christoforos N. Hadjicostis is with the Department of Electrical and Computer Engineering at the University of Cyprus, Nicosia, Cyprus, and also with the Department of Electrical and Computer Engineering at the University of Illinois, Urbana-Champaign, IL, USA. E-mail: chadjic@ucy.ac.cy.
	Parts of the results for quantized average consensus via event-triggered mass summation appear in <cit.>. The present version of the paper includes complete proofs for convergence as well as an enhanced version of the algorithm that allows nodes to determine when to seize transmissions, once quantized average consensus is reached (not addressed in <cit.>).

    
========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



  The study of complex networks is a significant development in modern
  science, and has enriched the social sciences, biology, physics, and
  computer science. Models and algorithms for such networks are
  pervasive in our society, and impact human behavior via social
  networks, search engines, and recommender systems to name a few. A
  widely used algorithmic technique for modeling such complex networks
  is to construct a low-dimensional Euclidean embedding of the
  vertices of the network, where proximity of vertices is interpreted
  as the likelihood of an edge. Contrary to the common view, we argue
  that such graph embeddings do not capture salient
  properties of complex networks. The two properties we focus on are
  low degree and large clustering coefficients, which have been widely
  established to be empirically true for real-world networks. We
  mathematically prove that any embedding (that uses dot products to
  measure similarity) that can successfully create these two
  properties must have rank nearly linear in the number of
  vertices. Among other implications, this establishes that popular
  embedding techniques such as Singular Value Decomposition and
  node2vec fail to capture significant structural aspects of
  real-world complex networks. Furthermore, we empirically study a
  number of different embedding techniques based on dot product, and
  show that they all fail to capture the triangle structure.








§ INTRODUCTION
 

Complex networks (or graphs) are a fundamental object of study
in modern science, across domains as diverse as the social sciences,
biology, physics, computer science, and engineering <cit.>. 
Designing good models for these networks is a crucial area of research,
and also affects society at large, given the role of online social networks
in modern human interaction <cit.>. Complex networks are massive, high-dimensional,
discrete objects, and are challenging to work with in a modeling
context. A common method of dealing with this challenge
is to construct a low-dimensional Euclidean embedding that tries
to capture the structure of the network (see <cit.> for a recent survey). Formally,
we think of the n vertices as vectors v⃗_1, v⃗_2, …, v⃗_n ∈^d,
where d is typically constant (or very slowly growing in n).
The likelihood of an edge (i,j) is proportional to (usually a non-negative
monotone function in) v⃗_i·v⃗_j <cit.>. This gives a graph
distribution that the observed network is assumed to be generated from.

The most important method to get such embeddings is the Singular Value Decomposition (SVD)
or other matrix factorizations of the adjacency
matrix <cit.>. Recently, there has also been an explosion of
interest in using methods from deep neural networks to learn such graph embeddings <cit.>
(refer to <cit.> for more references). Regardless of the
specific method, a key goal in building an embedding is to 
keep the dimension d small — while trying to preserve the network
structure — as the embeddings are used in a variety of downstream
modeling tasks such as graph
clustering, nearest neighbor search, and link
prediction <cit.>.  Yet a fundamental question remains unanswered: 
to what extent do such low dimensional embeddings actually capture
the structure of a complex network?

These models are often justified by treating the (few) dimensions as “interests" of individuals,
and using similarity of interests (dot product) to form edges.
Contrary to the dominant view, we argue that low-dimensional embeddings are
not good representations of complex networks. We demonstrate
mathematically and empirically that they lose local structure,
one of the hallmarks of complex networks. This runs counter
to the ubiquitous use of SVD in data analysis. The weaknesses
of SVD have been empirically observed in recommendation tasks <cit.>,
and our result provides a mathematical validation of these findings.

Let us define the setting formally. Consider a set of vectors v⃗_1, v⃗_2, …, v⃗_n ∈ℝ^d
(denoted by the d × n matrix V) used to represent the n vertices in a network. 
Let _V denote the following distribution of graphs over the vertex set [n].
For each index pair i,j, independently insert (undirected) edge (i,j) with probability
max(0,min(v⃗_i ·v⃗_j, 1)). (If v⃗_i ·v⃗_j is negative,
(i,j) is never inserted. If v⃗_i ·v⃗_j ≥ 1, (i,j) is always inserted.)
We will refer to this model as the “embedding" of a graph G, and focus
on this formulation in our theoretical results. 
This is a standard model in the literature, 
and subsumes the classic Stochastic Block Model <cit.>
and Random Dot Product Model <cit.>. There are 
alternate models that use different functions of the dot product
for the edge probability, which are discussed in Section <ref>.
Matrix factorization is a popular method to obtain such a vector representation: the original adjacency matrix A
is “factorized" as V^TV, where the columns of V are v⃗_1, v⃗_2, …, v⃗_n.



Two hallmarks of real-world graphs are: (i) Sparsity: The average degree is typically constant with respect
to n, and (ii) Triangle density: there are many triangles incident to low degree vertices <cit.>.
The large number of triangles is considered a local manifestation of community structure. Triangle counts have a rich history
in the analysis and algorithmics of complex networks. Concretely, we measure these properties
simultaneously as follows. 

  For parameters c > 1 and Δ > 0, a graph G with n vertices
has a (c,Δ)-triangle foundation if there are at least Δ n triangles contained among vertices of degree at most c.
Formally, let S_c be the set of vertices of degree at most c. Then, the number of triangles
in the graph induced by S_c is at least Δ n.


Typically, we think of both c and Δ as constants. 
We emphasize that n is the total number of vertices in G, not the number
of vertices in S (as defined above).
Refer to real-world graphs
in Table <ref>. In Figure <ref>, we plot the value
of c vs Δ. (Specifically, the y axis is the number of triangles divided by n.)
This is obtained by simply counting the number of triangles contained in the set of vertices of degree at most c. 
Observe that for all graphs,
for c ∈ [10,50], we get a value of Δ > 1 (in many cases Δ > 10). 

Our main result is that any embedding of graphs that generates graphs with (c,Δ)-triangle foundations,
with constant c,Δ, must have near linear rank. This
contradicts the belief that low-dimensional embeddings capture the structure of real-world complex networks.

  Fix c > 4, Δ > 0. Suppose the expected number of triangles 
in G ∼_V that only involve vertices of expected degree c is at least Δ n.
Then, the rank of V is at least min(1,(Δ/c)) n/^2n.


Equivalently, graphs generated from low-dimensional embeddings cannot contain many
triangles only on low-degree vertices. We point out an important
implication of this theorem for Stochastic Block Models. In this model, each vertex is modeled
as a vector in [0,1]^d, where the ith entry indicates the likelihood
of being in the ith community. The probability of an edge is exactly
the dot product. In community detection applications, d is thought of as a constant,
or at least much smaller than n. On the contrary, main implies
that d must be Ω(n/^2n) to accurately model the low-degree triangle behavior.



 §.§ Empirical validation
 



We empirically validate the theory on a collection of complex
networks detailed in Table <ref>. For each real-world graph, we compute a 100-dimensional embedding through SVD
(basically, the top 100 singular vectors of the adjacency matrix).
We generate 100 samples of graphs from these embeddings, and compute
their c vs Δ plot. This is plotted with the true c vs Δ plot.
(To account for statistical variation, we plot
the maximum value of Δ observed in the samples, over all graphs. The variation
observed was negligible.)
Figure <ref> shows such a plot for a physics coauthorship network.
More results are given in Section <ref>.
 
Note that this plot
is significantly off the mark at low degrees for the embedding. Around the lowest degree,
the value of Δ (for the graphs generated by the embedding) 
is 2-3 order of magnitude smaller than the original value. This demonstrates
that the local triangle structure is destroyed around low degree vertices.
Interestingly, the total number of triangles is preserved well, as shown
towards the right side of each plot. Thus, a nuanced view of the triangle
distribution, as given in foundation, is required to see the shortcomings
of low dimensional embeddings.




 §.§ Alternate models
 
We note that several other functions of dot product have been
  proposed in the literature, such as the softmax
  function <cit.> and linear 
models of the dot product <cit.>. Theorem <ref> does not have
direct implications for such models, but our empirical validation holds for 
them as well. The embedding in Theorem <ref> uses the truncated
dot product (TDP) function max(0,min(v⃗_i ·v⃗_j, 1)) to model
edge probabilities. We construct other embeddings that compute edge probabilities
using machine learning models with the dot product and Hadamard product
as features. This subsumes linear models as given in <cit.>. Indeed, the TDP
can be smoothly approximated as a logistic function.
We also consider (scaled) softmax functions, as in <cit.>, and standard
machine learning models (LRDP, LRHP). 
(Details about these models are given in Section <ref><ref>.)

For each of these models (softmax, LRDP, LRHP), we perform the same experiment described above.
Figure <ref> also shows the plots for these other models.
Observe that none of them capture the low-degree triangle structure,
and their Δ values are all 2-3 orders of magnitude lower than the original.  

In addition (to the extent possible), we compute vector embeddings
from a recent deep learning based method (node2vec <cit.>).
We again use all the edge probability models discussed above, and perform
an identical experiment (in Figure <ref>, these
are denoted by “n2v"). Again, we observe that the low-degree triangle behavior
is not captured by these deep learned embeddings.




 §.§ Broader context
 
The use of geometric embeddings for graph analysis has a rich history, arguably
going back to spectral clustering <cit.>. In recent years, the Stochastic Block Model
has become quite popular in the statistics and algorithms community <cit.>.
and the Random Dot Product Graph model is a generalization of this notion
(refer to recent surveys <cit.>). As mentioned earlier, Theorem <ref>
brings into question the standard uses of these methods to model social networks.
The use of vectors to represent vertices
is sometimes referred to as latent space models, where geometric proximity models
the likelihood of an edge. Although dot products are widely used, we
note that some classic latent space approaches use
Euclidean distance (as opposed to dot product) to model edge probabilities <cit.>,
and this may avoid the lower bound of Theorem <ref>.
Beyond graph analysis, the method of Latent Semantic Indexing (LSI) also falls
in the setting of Theorem <ref>, wherein we have a low-dimensional embedding
of “objects" (like documents) and similarity is measured by dot product <cit.>. 




§ HIGH-LEVEL DESCRIPTION OF THE PROOF
  

In this section, we sketch the proof of Theorem <ref>.
The sketch provides
sufficient detail for a reader who wants to understand the reasoning
behind our result, but is not concerned with technical details. 
We will make the simplifying assumption that all v_is have the same
length L.  We note that this setting is interesting in
its own right, since it is often the case in practice that all vectors
are non-negative and normalized. In this case, we get a stronger rank
lower bound that is linear in n. Section <ref> 
provides intuition on how we can remove this assumption. 
The full details of the proof are given in Section <ref>.



First, we lower bound L. By Cauchy-Schwartz, v⃗_i ·v⃗_j ≤ L^2. Let X_i,j
be the indicator random variable for the edge (i,j) being present. Observe that all X_i,js
are independent and [X_i,j] = min(v⃗_i ·v⃗_j, 1) ≤ L^2.

The expected number of triangles in G ∼_V is:

    [∑_i≠ j ≠ k X_i,j X_j,k X_i,k] 
       ≤   ∑_i ∑_j,k[X_j,k] [X_i,j] [X_i,k] 
       ≤    L^2 ∑_i ∑_j,k[X_i,j] [X_i,k] = L^2 ∑_i (∑_j [X_i,j])^2


Note that ∑_j [X_i,j] = [∑_j X_i,j] is at most the degree of i,
which is at most c. (Technically, the X_i,i term creates a self-loop, so the correct
upper bound is c+1. For the sake of cleaner expressions, we omit the additive +1
in this sketch.)
 
 The expected number of triangles is at least Δ n. Plugging these bounds
in:

    Δ n ≤ L^2 c^2 n ⟹ L ≥√(Δ)/c


Thus, the vectors have length at least √(Δ)/c. Now, we lower bound the rank of V.
It will be convenient to deal with the Gram matrix M = V^TV, which has the same rank as V.
Observe that M_i,j = v⃗_i ·v⃗_j ≤ L^2.
We will use the following lemma stated first by Swanapoel, but has appeared
in numerous forms previously <cit.>. 

 Consider any square matrix M ∈^n × n. Then

    (M) ≥| ∑_i M_i,i|^2/( ∑_i ∑_j |M_i,j|^2 )



Note that M_i,i = v⃗_i ·v⃗_i = L^2, so the numerator
|∑_i M_i,i|^2 = n^2 L^4. The denominator requires more work. We split 
it into two terms.

    ∑_i,j
    v⃗_i ·v⃗_j ≤ 1 (v⃗_i ·v⃗_j)^2
    ≤∑_i,j
    v⃗_i ·v⃗_j ≤ 1v⃗_i ·v⃗_j ≤ cn

If for i≠ j, v⃗_i ·v⃗_j > 1, then (i,j) is an edge with probability 1.
Thus, there can be at most (c-1)n such pairs. Overall, there are at most cn pairs 
such that v⃗_i ·v⃗_j > 1. So, ∑_i,j
v⃗_i ·v⃗_j > 1 (v⃗_i ·v⃗_j) 
≤ cnL^4. Overall, we lower bound the denominator in the rank lemma by cn(L^4+1).

We plug these bounds into the rank lemma. We use the fact that f(x) = x/(1+x) is decreasing for positive x,
and that L ≥√(Δ)/c.

    (M) ≥n^2 L^4/cn(L^4 + 1)≥n/c·Δ^2/c^4/Δ^2/c^4 + 1
    = Δ^2/c(Δ^2 + c^4)· n




 §.§ Dealing with varying lengths
 

The math behind tri2 still holds with
the right approximations. Intuitively, the existence of at least Δ n triangles 
implies that a sufficiently large number of vectors have length at least √(Δ)/c.
On the other hand, these long vectors need to be “sufficiently far
away" to ensure that the vertex degrees remain low. There
are many such long vectors, and they can can only be far away 
when their dimension/rank is sufficiently high.

The rank lemma is the main technical tool that formalizes this
intuition. When vectors are of varying length,
the primary obstacle is the presence of extremely long vectors that create triangles.
The numerator in the rank lemma sums M_i,i, which is the length of the vectors.
A small set of extremely long vectors could dominate the sum, increasing the numerator.
In that case, we do not get a meaningful rank bound.

But, because the vectors inhabit low-dimensional space, the long vectors from different
clusters interact with each other. We prove a “packing" lemma (dot) showing that 
there must be many large positive dot products among a set of extremely long vectors.
Thus, many of the corresponding vertices have large degree, and triangles incident
to these vertices do not contribute to low degree triangles.
Operationally, the main proof uses the packing lemma to show that there are few long vectors.
These can be removed without affecting the low degree structure. One can then perform
a binning (or “rounding") of the lengths of the remaining vectors, to implement
the proof described in the above section.




§ PROOF OF THEOREM <REF>
 

For convenience, we restate the setting.
Consider a set of vectors v⃗_1, v⃗_2, …, v⃗_n ∈^d, that represent
the vertices of a social network. 
We will also use the matrix V ∈^d × n for these vectors,
where each column is one of the v⃗_is.
Abusing notation, we will use V to represent
both the set of vectors as well as the matrix. We will refer to the vertices by the index in [n].

Let _V denote the following distribution of graphs over the vertex set [n].
For each index pair i,j, independently insert (undirected) edge (i,j) with probability
max(0,min(v⃗_i ·v⃗_j, 1)).



 §.§ The basic tools
 

We now state some results that will be used in the final proof.

  [Rank lemma <cit.>] Consider any square matrix A ∈^n × n. Then

    | ∑_i A_i,i|^2 ≤(A) ( ∑_i ∑_j |A_i,j|^2 )



  Consider a set of s vectors w⃗_1, w⃗_2, …, w⃗_s in ^d.

    ∑_(i,j) ∈ [s] × [s] 
    w⃗_i ·w⃗_j < 0 |w⃗_i ·w⃗_j|
    ≤∑_(i,j) ∈ [s] × [s] 
    w⃗_i ·w⃗_j > 0 |w⃗_i ·w⃗_j|



  Note that (∑_i ≤ sw⃗_i)· (∑_i ≤ sw⃗_i) ≥ 0.
Expand and rearrange to complete the proof.


Recall that an independent set is a collection of vertices that induce no edge.

  Any graph with h vertices and maximum degree b
has an independent set of at least h/(b+1).


  Intuitively, one can incrementally build an independent set,
by adding one vertex to the set, and removing at most b+1 vertices from the graph.
This process can be done at least h/(b+1) times.

Formally, we prove by induction on h. First we show
the base case. If h ≤ b+1, then the statement is trivially true.
(There is always an independent set of size 1.) For the induction step, let us construct
an independent set of the desired size. Pick an arbitrary vertex x and add it to the independent set.
Remove x and all of its neighbors. By the induction hypothesis, the remaining graph
has an independent set of size at least (h - b - 1)/(b+1) = h/(b+1) - 1.



  Consider the distribution _V.
Let _i denote the degree of vertex i ∈ [n].
[^2_i] ≤[_i] + [_i]^2.


 (of Claim <ref>) Fix any vertex i ∈ [n]. Observe that _i = ∑_j ≠ i X_j, where X_j is the indicator random variable
for edge (i,j) being present. Furthermore, all the X_js are independent.

    [D^2_i]     =    [(∑_j ≠ i X_j)^2] = [∑_j ≠ i X^2_j + 2∑_j≠ j' X_j X_j'] 
        =    [∑_j ≠ i X_j] + 2∑_j ≠ j'[X_j] [X_j'] 
       ≤   [_i] + (∑_j ≠ i[X_j])^2 = [_i] + [_i]^2





A key component of dealing with arbitrary length vectors is the following dot product lemma.
This is inspired by results of Alon <cit.> and Tao <cit.>,
who get a stronger lower bound of 1/√(d) for absolute values of the dot products.

   Consider any set of 4d unit vectors u⃗_1, u⃗_2, …, u⃗_4d
in ^d. There exists some i ≠ j such that u⃗_i ·u⃗_j ≥ 1/4d.


 (of dot)  We prove by contradiction, so assume ∀ i ≠ j, u⃗_i ·u⃗_j < 1/4d.
We partition the set [4d] × [4d] into 
= {(i,j) | u⃗_i ·u⃗_j < 0} and = {(i,j) | u⃗_i ·u⃗_j ≥ 0}.
The proof goes by providing (inconsistent) upper and lower bounds for ∑_(i,j) ∈ |u⃗_i ·u⃗_j|^2.
First, we upper bound ∑_(i,j) ∈ |u⃗_i ·u⃗_j|^2 by:

    ≤   ∑_(i,j) ∈ |u⃗_i ·u⃗_j|        (u⃗_is are unit vectors)
       ≤   ∑_i ≤ 4du⃗_i^2_2 + ∑_1 ≤ i ≠ j ≤ 4d
     (i,j) ∈ |u⃗_i ·u⃗_j|        (neg)
        <     4d + 16d^2/4d = 8d     (since u⃗_i ·u⃗_j < 1/4d)


For the lower bound, we invoke the rank bound of rank on the 4d × 4d Gram matrix M of u⃗_1, …, u⃗_4d.
Note that (M) ≤ d, M_i,i = 1, and M_i,j = u⃗_i ·u⃗_j.
By rank, ∑_(i,j) ∈ [4d] × [4d] |u⃗_i ·u⃗_j|^2 ≥ (4d)^2/d = 16 d. 
We bound

    ∑_(i,j) ∈ |u⃗_i ·u⃗_j|^2     =    ∑_i ≤ 4du⃗_i^2_2 + ∑_(i,j) ∈, i ≠ j |u⃗_i ·u⃗_j|^2 
       ≤    4d + (4d)^2/(4d)^2 ≤ 5d

Thus, ∑_(i,j) ∈ |u⃗_i ·u⃗_j|^2 ≥ 16d - 5d = 11d. This contradicts the bound of dot-upper.

 




 §.§ The main argument
 

We prove by contradiction. We assume that the expected number
of triangles contained in the set of vertices of expected degree at most c,
is at least Δ n. We remind the reader that n
is the total number of vertices. For convenience, we simply remove the vectors
corresponding to vertices with expected degree at least c.
Let V̂ be the matrix of the remaining vectors, and we focus
on _V̂. The expected number of triangles in G ∼_V̂
is at least Δ n.

The overall proof can be thought of in three parts.

Part 1, remove extremely long vectors: Our final aim is to use the rank lemma (Lemma <ref>)
to lower bound the rank of V. The first problem we encounter is that
extremely long vectors can dominate the expressions in the rank lemma,
and we do not get useful bounds. We show that the number of such long vectors
is extremely small, and they can removed without affecting too many triangles.
In addition, we can also remove extremely small vectors, since they cannot participate
in many triangles.

Part 2, find a “core" of sufficiently long vectors that contains enough triangles: The previous step
gets a “cleaned" set of vectors. Now, we bucket these vectors by length. We show
that there is a large bucket, with vectors that are sufficiently long, such that
there are enough triangle contained in this bucket.

Part 3, apply the rank lemma to the “core": We now focus on this core of vectors,
    where the rank lemma can be applied. 
    At this stage, the mathematics shown
    in Section <ref> can be carried out almost directly.


Now for the formal proof.
For the sake of contradiction, we assume that d = (V̂) < α (Δ^4/c^9) · n/^2n
(for some sufficiently small constant α > 0).

Part 1: Removing extremely long (and extremely short) vectors

We begin by showing that there cannot be many long vectors in V̂.

  There are at most 5cd vectors of length at least 2√(n).


 Let  be the set of “long" vectors, those with length at least 2√(n).
Let us prove by contradiction, so assume there are more than 5cd long vectors.
Consider a graph H = (,E), where vectors v⃗_⃗i⃗,v⃗_⃗j⃗∈ (i ≠ j) are connected
by an edge if v⃗_⃗i⃗/v⃗_i_2·v⃗_⃗j⃗/v⃗_j_2≥ 1/4n.
We choose the 1/4n bound to ensure that all edges in H are edges in G.

Formally, for any edge (i,j) in H, v⃗_⃗i⃗·v⃗_⃗j⃗≥v⃗_i_2 v⃗_j_2/4n 
≥ (2√(n))^2/4n = 1. So (i,j) is an edge with probability 1
in G ∼_V. The degree of any vertex
in H is at most c. By ind, H contains an independent set I of size at least 5cd/(c+1) ≥ 4d.
Consider an arbitrary sequence of 4d (normalized) vectors in I  u⃗_1, …, u⃗_4d.
Applying dot to this sequence, we deduce the existence of (i,j) in I (i ≠ j) such that 
v⃗_⃗i⃗/v⃗_i_2·v⃗_⃗j⃗/v⃗_j_2≥ 1/4d ≥ 1/4n.
Then, the edge (i,j) should be present in H, contradicting the fact that I is an independent set.


Denote by V' the set of all vectors in V̂ with length in the range [n^-2, 2√(n)]. 

  The expected degree of every vertex in G ∼_V' is 
at most c, and the expected number of triangles in G is at least Δ n/2.


 Since removal of vectors can only decrease the 
degree, the expected degree of every vertex in _V' is naturally at most c.
It remains to bound the expected number of triangles in G ∼_V'.
By removing vectors in V∖ V', we potentially lose some triangles. Let us
categorize them into those that involve at least one “long" vector (length ≥ 2√(n))
and those that involve at least one “short" vector (length ≤ n^-2) but no long vector.

We start with the first type.
By long, there are at most 5cd long vectors. For any vertex, the expected number
of triangles incident to that vertex is at most the expected square of the degree.
By var, the expected degree squares is at most c + c^2 ≤ 2c^2.  Thus,
the expected total number of triangles of the first type is at most 5cd× 2c^2 ≤Δ n/^2n.

Consider any triple of vectors (u⃗,v⃗,w⃗) where u⃗ is short
and neither of the others are long. The probability that this triple forms
a triangle is at most 

    min(u⃗·v⃗,1) ·min(u⃗·w⃗,1) 
       ≤   min(u⃗_2v⃗_2,1) ·min(u⃗_2 w⃗_2,1) 
       ≤    (n^-2· 2√(n))^2 ≤ 4n^-3

Summing over all such triples, the expected number of such triangles is at most 4.

Thus, the expected number of triangles in G ∼_V' is at least Δ n - Δ n/^2n - 4 ≥Δ n/2.


Part 2: Finding core of sufficiently long vectors with enough triangles


For any integer r, let V_r be the set of vectors {v⃗∈ V' | v⃗_2 ∈ [2^r, 2^r+1)}.
Observe that the V_rs form a partition of V'. Since all lengths in V'
are in the range [n^-2,2√(n)], there are at most 3 n non-empty V_rs.
Let R be the set of indices r such that |V_r| ≥ (Δ/60c^2)(n/ n).
Furthermore, let V” be ⋃_r∈ R V_r.

  The expected number of triangles in G ∼_V” is at least Δ n/8.


 The total number of vectors in ⋃_r ∉ R V_r is at most 
3 n × (Δ/60c^2) (n/ n)  ≤ (Δ/20c^2) n. By var and linearity of expectation,
the expected sum of squares of degrees of all vectors in ⋃_r ∉ R V_r
is at most (d+c^2) × (Δ/20c^2) n ≤Δ n/10. Since the expected
number of triangles in G ∼_V' is at least Δ n/2
(prune) and the expected number of triangles
incident to vectors in V' ∖ V” is at most Δ n/10,
the expected number of triangles in G ∼_V” is at least Δ n/2 - Δ n/10 ≥Δ n/8.


We now come to an important claim. Because the expected number of triangles in G ∼_V” is large,
we can prove that V” must contain vectors of at least constant length.

  max_r ∈ R 2^r ≥√(Δ)/4c.


 Suppose not. Then every vector in V” has length at most √(Δ)/4c.
By Cauchy-Schwartz, for every pair u⃗, v⃗∈ V”, u⃗·v⃗≤Δ/16c^2.
Let I denote the set of vector indices in V” (this corresponds to the vertices in G ∼_V”).
For any two vertices i ≠ j ∈ I, let X_i,j be the indicator random variable for 
edge (i,j) being present.
The expected number of triangles incident to vertex i in G ∼_V”
is 

    [∑_j≠ k ∈ I X_i,jX_i,kX_j,k]  =  ∑_j≠ k ∈ I[X_i,j X_i,k] [X_j,k]

Observe that [X_j,k] is at most v⃗_⃗j⃗·v⃗_⃗k⃗≤Δ/16c^2.
Furthermore, ∑_j ≠ k ∈ I[X_i,j X_i,k] = [D^2_i]
(recall that D_i is the degree of vertex i.)
By var, this is at most c+c^2 ≤ 2c^2. The expected number of triangles in G ∼_V”
is at most n × 2c^2 ×Δ/16c^2 = Δ n/8. This contradicts prune2.


Part 3: Applying the rank lemma to the core

We are ready to apply the rank bound of rank to prove the final result. The following
lemma contradicts our initial bound on the rank d, completing the proof. We will omit
some details in the following proof, and provide
a full proof in the SI.

  (V”) ≥ (αΔ^4/c^9) n/^2 n.


 It is convenient to denote the index set of V” be I.
Let M be the Gram Matrix (V”)^T(V”), so for i,j ∈ I, 
M_i,j = v⃗_i ·v⃗_j
By rank, (V”) = (M) ≥ (∑_i ∈ I M_i,i)^2/∑_i,j ∈ I |M_i,j|^2.
Note that M_i,i is v⃗_⃗i⃗^2_2, which is at least 2^2r
for v⃗_⃗i⃗∈ V_r. Let us denote max_r ∈ R 2^r by L,
so all vectors in V” have length at most 2L.
By Cauchy-Schwartz, all entries in M are at most 4L^2.

We lower bound the numerator. 

    (∑_i ∈ Iv⃗_⃗i⃗^2_2)^2 ≥(∑_r ∈ R 2^2r |V_r|)^2 
       ≥   (max_r ∈ R 2^2r (Δ/60 c^2)(n/ n))^2 
        =     L^4(Δ^2/3600 c^4)(n^2/^2 n)








Now for the denominator. We split the sum into four parts and bound each separately.

    ∑_i,j ∈ I |M_i,j|^2     =    ∑_i ∈ I |M_i,i|^2 + ∑_i,j ∈ I 
     i ≠ j, M_i,j∈ [0,1] |M_i,j|^2 
        +    ∑_i,j ∈ I 
     i ≠ j, M_i,j > 1 |M_i,j|^2 + ∑_i,j ∈ I 
     M_i,j < 0 |M_i,j|^2  :!


Since |M_i,i| ≤ L^2, the first term is at most 4nL^4.
For i ≠ j and M_i,j∈ [0,1], the probability that edge (i,j) is present is precisely M_i,j.
Thus, for the second term, 

    ∑_i,j ∈ I 
     i ≠ j, M_i,j∈ [0,1] |M_i,j|^2 
    ≤∑_i,j ∈ I 
     i ≠ j, M_i,j∈ [0,1] M_i,j≤ 2cn


For the third term, we observe that when M_i,j > 1 (for i ≠ j),
then (i,j) is an edge with probability 1. There can be at most 2cn pairs (i,j), i ≠ j,
such that M_i,j > 1. Thus, the third term is at most 2cn · (4L^2)^2 = 32cnL^4.

Now for the fourth term. Note that M is a Gram matrix, so we can invoke neg on its entries.

    ∑_i,j ∈ I 
     M_i,j < 0 |M_i,j|^2  
           ≤    L^2∑_i,j ∈ I 
     M_i,j < 0 |M_i,j| 
       ≤    L^2(∑_i ∈ I |M_i,i| + ∑_i,j ∈ I 
     M_i,j > 0 |M_i,j|) 
       ≤    4nL^4 + L^2 ∑_i,j ∈ I 
     M_i,j∈ [0,1] |M_i,j|  + 
    4L^4 ∑_i,j ∈ I 
     M_i,j > 1 1 
       ≤    4nL^4 + 2cn L^2 + 8cnL^4


Putting all the bounds together,
we get that ∑_i,j ∈ I |M_i,j|^2 ≤ n(4L^4 + 2c + 32cL^4 + 4L^4 + 2cL^2 + 8cL^4)
≤ 32n(L^4 + c(1 + L^2 + L^4)). If L ≤ 1, we can upper bound
by 128cn. If L ≥ 1, we can upper bound by 128cnL^4. In either case,
128cn(1+L^4) is a valid upper bound.























Crucially, by len, L ≥√(Δ)/4c. Thus, 4^4 c^4 L^4/Δ^2 ≥ 1.
Combining all the bounds (and setting α < 1/(128· 3600 · 4^4)),

    (V”)    ≥   L^4(Δ^2/3600 c^4)(n^2/^2 n)/128cn(1+16L^4)
       ≥   L^4(Δ^2/3600 c^4)(n/^2 n)/128cn(4^4 c^4 L^4/Δ^2+16L^4)
       ≥    (αΔ^4/c^9)(n/^2 n)





§ DETAILS OF EMPIRICAL RESULTS
 
	
 Data Availability:   The datasets used are summarized in datasets. 
   We present here four publicly available datasets from different domains. The  is a co-authorship network
    is a social network,  is a citation network, all obtained from the SNAP graph database <cit.>.
   The  dataset is a protein-protein-interaction network obtained from <cit.>. (The citations
   provide the link to obtain the corresponding datasets.)

   We first describe the primary experiment, used to validate Theorem <ref>
   on the SVD embedding.
	We generated a d-dimensional embedding for various values of d
    using the SVD.
    Let G be a graph with the n × n (symmetric) adjacency matrix A,
    with eigendecomposition ΨΛΨ^T.  Let Λ_d be the matrix with the d × d diagonal matrix 
    with the d largest magnitude eigenvalues of A along the diagonal. Let Ψ_d be the n × d matrix 
    with the corresponding eigenvectors as columns. We compute the matrix A_d = Ψ_d Λ_d Ψ_d^T and 
    refer to this as the d spectral embedding of G. This is the standard PCA approach.

	From the spectral embeddings, we generate a graph from A_d by considering every pair of vertices (i, j) and generate a random value in [0, 1]. If the (i, j)^th entry of A_d is greater than the random value generated, the edge is added to the graph. Otherwise the edge is not present. This is the same as taking A_d and setting all negative values to 0, and all values greater than 1 to 1 and performing Bernoulli trials for each edge with the resulting probabilities. 
    In all the figures, this is referred to as the “SVD TDP" (truncated dot product) embedding.
		











 §.§ Triangle distributions

  To generate Figure <ref> and Figure <ref>, we calculated the number of triangles incident to vertices of different degrees in both the original graphs and the graphs generated from the embeddings. Each of the plots shows the number of triangles in the graph on the vertical axis and the degrees of vertices on the horizontal axis. Each curve corresponds to some graph, and each point (x, y) in a given curve shows that the graph contains y triangles if we remove all vertices with degree at least x. We then generate
  100 random samples from the 100-dimensional embedding, as given by SVD (described above). For each value of c,
  we plot the maximum value of Δ over all the samples. This is to ensure that our results are not affected
  by statistical variation (which was quite minimal).




 §.§ Alternate graph models
 

 We consider three other functions of the dot product, to construct graph distributions
from the vector embeddings. Details on
parameter settings and the procedure used for the optimization are given in the SI.


Logistic Regression on the Dot Product (LRDP): We consider the probability
    of an edge (i,j) to be the logistic function L(1+exp(-k(v⃗_i ·v⃗_j - x_0)))^-1,
    where L, k, x_0 are parameters. Observe that the range of this function is [0,1],
    and hence can be interpreted as a probability. We tune these parameters to fit the expected
    number of edges, to the true number of edges. Then, we proceed as in the TDP experiment.
    We note that the TDP can be approximated by a logistic function, and thus the LRDP
    embedding is a “closer fit" to the graph than the TDP embedding.


Logistic Regression on the Hadamard Product (LRHP): This is inspired
    by linear models used on low-dimensional embeddings <cit.>. Define the Hadamard
    product v⃗_i ⊙v⃗_j to be the d-dimensional vector where the rth
    coordinate is the product of rth coordinates. We now fit a logistic function over
    linear functions of (the coordinates of) v⃗_i ⊙v⃗_j. This is a significantly
    richer model than the previous model, which uses a fixed linear function (sum). Again,
    we tune parameters to match the number of edges.
    The fitting of LRDP and LRHP was done
    using the Matlab function glmfit (Generalized Linear Model Regression Fit)
    <cit.>. The distribution parameter was set to “binomial", since
    the total number of edges is distributed as a weighted binomial. 


Softmax: This is inspired by low-dimensional embeddings for random walk
    matrices <cit.>. The idea is to make the probability
    of edge (i,j) to be proportional to softmax, 
    exp(v⃗_i ·v⃗_j)/∑_k ∈ [n]v⃗_i ·v⃗_k.
    This tends to push edge formation even for slightly higher dot products, and one might
    imagine this helps triangle formation. We set the proportionality constant separately for
    each vertex to ensure that the expected degree is the true degree. The probability matrix
    is technically undirected, but we symmetrize the matrix. 

node2vec experiments: 
We also applied node2vec,
a recent deep learning based graph embedding method <cit.>, to generate vector representations
of the vertices. 
We used the optimized C++
implementation <cit.> for node2vec, which is equivalent
to the original implementation provided by the authors <cit.>. For all our experiments, we use the default
settings of walk length of 80, 10 walks per node, p=1 and q=1. 
The node2vec algorithm tries to model the random walk
matrix associated with a graph, not the raw adjacency matrix. The dot products
between the output vectors v⃗_i ·v⃗_j are used to model 
the random walk probability of going from i to j, rather than the presence of an edge. It does not make
sense to apply the TDP function on these dot products, since this will
generate (in expectation) only n edges (one for each vertex). We apply
the LRDP or LRHP functions, which use the node2vec vectors as inputs to a machine learning
model that predicts edges.


In Figures <ref> and <ref>, we show results for all the datasets. 
We note that for all datasets and all embeddings, the models fail to capture the low-degree triangle behavior.






 §.§ Degree distributions


We observe that the low-dimensional embeddings obtained from SVD and the truncated dot product
can capture the degree distribution accurately. In Figure <ref>, we plot the degree
distribution (in loglog scale) of the original graph with the expected degree distribution
of the embedding. For each vertex i, we can compute its expected degree by the sum ∑_i p_ij,
where p_ij is the probability of the edge (i,j). In all cases, the expected degree distributions
is close to the true degree distributions, even for lower degree vertices. 
The embedding successfully captures the “first order"
connections (degrees), but not the higher order connections (triangles). We believe that this
reinforces the need to look at the triangle structure to discover the weaknesses of low-dimensional
embeddings.























 §.§ Detailed relationship between rank and triangle structure
 

For the smallest Facebook graph, we were able to compute the entire set of eigenvalues.
This allows us to determine how large a rank is required to recreate the low-degree triangle structure.
In Figure <ref>, for varying rank of the embedding,
we plot the corresponding triangle distribution.
In this plot, we choose the embedding given by the eigendecomposition
(rather than SVD), since it is guaranteed to converge to the correct triangle distribution
for an n-dimensional embedding (n is the number of vertices). The SVD and eigendecomposition
are  mostly identical for large singular/eigenvalues, but tend to be different (up to a sign)
for negative eigenvalues.

We observe that even a 1000 dimensional embedding does not capture the c vs Δ plots
for low degree. Even the rank 2000 embedding
is off the true values, though it is correct to within an order of magnitude.
This is strong corroboration of our main theorem, which says that near linear
rank is needed to match the low-degree triangle structure. 






alpha


