Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Summary

Q1 (3 marks)

1.1 Are the graphs in Figure 1 and Figure 2 homomorphic? If so, demonstrate a matching instance. (1 mark)

1.2 Present all unique subgraphs in Figure 1 that are isomorphic to the graph in Figure 3. For example, {�1:�,�2:�,�3:�}, {�1:�,�2:�,�3:�}, and {�1:�,�2:�,�3:�} are all considered as the same subgraph abc. (2 marks)

Q2 (5 marks)

2.1 Given the graph in Figure 4, compute the betweenness centrality and closeness centrality of nodes F and G. Round each value to two decimal places (e.g., 3.333 becomes 3.33; 3.7571 becomes 3.76). (2 marks)

2.2 Given the graphs G and G' in Figure 5, compute the Weisfeiler-Lehman (WL) kernel as follows:

• Compute the color count vector for each graph after color refinement converges.
• Compute the WL kernel value between G and G'.

Use lexicographical order for color refinement. (3 marks)

Q3 (8 marks)

Suppose we aim to count the number of triangles that each vertex belongs to in an undirected graph using Pregel, as shown in Figure 6. The simple implementation below works but may leave room for improvement. Your task is to analyze the code and, if appropriate, optimise it.
Note: self.tri_local stores the number of triangles the vertex is in. self.neighbors is an unordered list of neighbor vertex IDs.

void __init__(self): self.tri_local = 0 void Compute(self, messages: List): if (Superstep() == 0): for u in self.neighbors: SendMessageTo(u, (self.vertexID, self.neighbors)) elif (Superstep() == 1): for (v, Nv) in messages: for w in self.neighbors: if w in Nv: self.tri_local += 0.5 VoteToHalt()

3.1  Code optimisation (4 marks)
Examine the pseudo-code snippet above. What is the total CPU computation time complexity of the algorithm? What is the network cost complexity? (Network cost accounts for all messages and their payloads, not just the number of messages.) Can this algorithm be optimized (e.g., reduced CPU computation cost, lower network cost, earlier termination, etc.)?

• If your answer is yes, briefly describe the improvement and provide the key lines (pseudo-code is sufficient) that you would change / add. State the new time and network cost complexity.
• If your answer is no, give a short technical reason why the current design is already asymptotically optimal under the Pregel model.

3.2  Execution trace (2 marks)
Assume three Pregel workers with the following vertex-to-worker assignment:
  • Vertices 1 and 5 → worker X
  • Vertices 2 and 4 → worker Y
  • Vertices 3 and 6 → worker Z
For each superstep produced by your algorithm (optimised or not), list
(i) the active vertices and
(ii) for every vertex, the messages sent/received (both the total count and the concrete payload).

3.3  Combiner feasibility (2 marks)
Can a Pregel combiner be applied to the triangle-counting algorithm?

• If yes, provide combiner pseudo-code and recalculate the number of messages per superstep under the vertex-to-worker assignment in 3.2.
• If no, give a concise argument why the semantics of this problem preclude a combiner.

Q4 (4 marks)

Given an undirected graph as shown in Figure 7, we aim to compute the output �1 of the first graph convolutional layer with self-loops using the Graph Attention Network (GAT) model. The goal is to transform the initial node embeddings from a dimension of 4 to a dimension of 5 through this layer. The equation can be written as:

ℎ�(�)=�(∑�∈�(�)∪{�}����(�)ℎ�(�−1)),

where ℎ�� indicates the ��-dimensional embedding of node � in layer �, and ��=[ℎ�1�,ℎ�2�,ℎ�3�,ℎ�4�,ℎ�5�,ℎ�6�]�. ���=1|�(�)∪{�}| is the weighting factor of node �'s message to node �. �(�)∈���∗��−1 denotes the weight matrix for the neighbours of � in layer �, �� denotes the dimension of the node embedding in layer �. �(⋅) denotes the ���� non-linear function. The initial embedding for all nodes is stacked in �0. �1 is the weight matrices. Self-loops are included in the calculation to ensure that the node's information is retained. Therefore, the term � is added to its set of neighbors, which can be expressed as {�}∪�(�). Round each value to two decimal places (e.g., 3.333 becomes 3.33; 3.7571 becomes 3.76).

�0=(0.800.90−0.700.700.50−0.800.30−0.40−0.900.400.50−0.100.800.70−0.80−0.600.50−0.90−0.20−0.400.70−0.200.40−0.90)

�1=(11010110101101001011)

END OF QUESTIONS