We show that the classification performance of Graph Convolutional Networks is related to the alignment between features, graph and ground truth, which we quantify using a subspace alignment measure corresponding to the Frobenius norm of the matrix of pairwise chordal distances between three subspaces associated with features, graph and ground truth. The proposed measure is based on the principal angles between subspaces and has both spectral and geometrical interpretations. We showcase the relationship between the subspace alignment measure and the classification performance through the study of limiting cases of Graph Convolutional Networks as well as systematic randomizations of both features and graph structure applied to a constructive example and several examples of citation networks of different origin. The analysis also reveals the relative importance of the graph and features for classification purposes.
The graph is encoded in @math , where @math is the adjacency matrix of a graph with added self-loops, @math is the identity matrix, and @math is a diagonal matrix containing the degrees of @math . In the remainder of this work (and to ensure comparability with the results in @cite_12 ), we use @math as the descriptor of the graph @math .
@cite_12
2065527713 2068332510 2950966800 2764230287
We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes. It is well known that the smallest eigenvalue of the adjacency matrix of a connected d-regular graph is at least − d and is strictly greater than − d if the graph is not bipartite. More generally, for any connected graph G = (V, E), consider the matrix Q = D + A where D is the diagonal matrix of degrees in the graph G and A is the adjacency matrix of G. Then Q is positive semidefinite, and the smallest eigenvalue of Q is 0 if and only if G is bipartite. We will study the separation of this eigenvalue from 0 in terms of the following measure of nonbipartiteness of G. For any S ⊆ V, we denote by emin(S) the minimum number of edges that need to be removed from the induced subgraph on S to make it bipartite. Also, we denote by cut(S) the set of edges with one end in S and the other in V − S. We define the parameter Ψ as ***image*** The parameter Ψ is a measure of the nonbipartiteness of the graph G. We will show that the smallest eigenvalue of Q is bounded above and below by functions of Ψ. For d-regular graphs, this characterizes the separation of the smallest eigenvalue of the adjacency matrix from −d. These results can be easily extended to weighted graphs. © 1994 Wiley Periodicals, Inc. A graph @math is called @math -full if @math contains a subgraph @math of @math edges such that, for any non-empty @math , @math holds. Here, @math denotes the set of vertices incident to @math . It is known that the family of edge sets of @math -full graphs forms a family of matroid, known as the sparsity matroid of @math . In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for @math -fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property @math or far from @math ). Depending on the values of @math and @math , it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for @math -edge-connected-orientability in the bounded-degree model, where an undirected graph @math is called @math -edge-connected-orientable if there exists an orientation @math of @math with a vertex @math such that @math contains @math arc-disjoint dipaths from @math to each vertex @math and @math arc-disjoint dipaths from each vertex @math to @math . A tester is called a one-sided error tester for @math if it always accepts a graph satisfying @math . We show, for @math and (proper) @math , any one-sided error tester for @math -fullness and @math -edge-connected-orientability requires @math queries. We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs @math converging locally to a Galton--Watson tree @math (GWT), we provide an explicit formula for the asymptotic multiplicity of the eigenvalue 0 in terms of the degree generating function @math of @math . In the first part, we show that the adjacency operator associated with @math is always self-adjoint; we analyze the associated spectral measure at the root and characterize the distribution of its atomic mass at 0. In the second part, we establish a sufficient condition on @math for the expectation of this atomic mass to be precisely the normalized limit of the dimension of the kernel of the adjacency matrices of @math . Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.