G&N Unit 9

We want to develop an application for access control to a building based on fingerprint recognition, using graphs as representation. Which is the best strategy?

• An exact graph matching between the query graph (fingereprint) and the valid ones of the database.

• Finding the maximum common subgraph between the query graph (fingereprint) and the valid ones of the database.

• Defining a graph embedding, and compute the dot product as similarity masure between the query graph and the valid ons in the database.

• Both, exact graph matching and similarity between graph embeddings are equivalent and give the same output, so any of them.

A subgraph isomorphism betwn two graphs G1 and G2 is ...

• An injective mapping between the nodes of G1 and the nodes of G2 such that each G1 node finds a compatible G2 node preserving the structure induced by the edges.

• A minimum cost edit sequence that transforms G1 into G2.

• A function that projects the graphs into a n-dimensional space such that the similarity between them can be calculated using a dot product.

• A convolutional neural network based in message passing.

What is an association graph (product graph) between two attributed graphs G1 and G2?

• A maximum common subgraph.

• A compatibility graph, i.e. a new graph whose nodes represent compatible node pairs, and whose edges represent compatible edge pairs between G1 and G2.

• The graph that is generated with the same graph edit sequence from the two graphs.

• A graph that merges the cliques of G1 and G2.

What is the graph edit distance between two graphs?

• The dot product between the bag of graphlets vectors.

• The number of common cliques of two graphs.

• The minimum cost edit sequence that transforms one graph into the other one.

• The number of edit operations that transform one graph into the other.

Given the two graphs of the figure, and the following edit costs:

Node and edge substitution: 0 if they have the same label, 1 otherwise.

Node and edge deletion and insertion: 2

Which one is the minimum cost edit sequence?

• v1 -> w2, v2 -> w1, e1 -> f1, v3 -> λ, e2 -> λ, e3 -> λ

• delete first all the nodes and edges of G1, and insert all the nodes and edges of G2

• v1 -> w1, v2 -> w2, e1 -> f1, v3 -> λ, e2 -> λ, e3 -> λ

• The answers B and C are equivalent (same edit cost)

What is a graph embedding?

• A function that transforms a graph into a numeric feature vector.

• A function that calculates the subgraph matching from one graph to another one.

• A function that sorts the graph nodes in terms of their centralities.

• A functions that calculates the product graph.

How does a random walk kernel work?

• It constructs the embeddings as a bag of graphlets.

• It computes the similarity between two graphs as the dot product between the centralities vector.

• It extracts the number of common walks from the power of the adjacency matrix of the association graph.

• It computes the lenght of the edit sequence between two graphs.

Which of the following sentences on GNNs is NOT TRUE?

• Graph Neural Networks are message passing networks that at each layer calculatee the hidden embeddings with aggregation functions.

• The problem of graph neural networks is that they are not permutation invariant.

• Graph neural networks can be used to predict/classify both nodes or graphs.

• The number of layers of a GNN is proportional to the size of the subgraph in terms of number of hops that is considered when a node embedding is calculated.