Representation Learning

A graph is formally defined as G = (V, E) — a set of vertices (nodes) connected by edges. Both correct answers are saying the same thing in different vocabularies: Nodes and edges (A) is the standard computer science terminology, and entities and relationships (C) is the semantic/knowledge-graph terminology where "entities" map to nodes and "relationships" map to edges. B is wrong — "hyperplanes" are geometric constructs from linear algebra, not graph components. D is wrong — features and labels belong to supervised machine learning, not graph theory.

In a directed graph (digraph), every edge has an arrow pointing from a source node to a target node (A) — for example, a "follows" relationship on Twitter. B is wrong — bidirectional edges describe undirected graphs; in directed graphs, A→B does not imply B→A. C is wrong — in directed graphs, in-degree and out-degree of a node are generally different, so degrees are asymmetric. D is wrong — directed graphs can absolutely contain cycles (e.g., A→B→C→A); only a special subtype called a DAG (Directed Acyclic Graph) is guaranteed to be acyclic.

An adjacency matrix A is an n×n matrix where entry A[i][j] = 1 if there is an edge from node i to node j, and 0 otherwise. Its primary purpose is to represent which nodes are connected (A). B is partially related — a weighted adjacency matrix can store edge weights too, but the basic adjacency matrix only captures connectivity (0 or 1), not general edge weights. C is wrong — community detection is an algorithm applied on top of graph data; the adjacency matrix itself doesn't detect communities. D is wrong — node attributes, labels, and other metadata are stored separately, not in the adjacency matrix.

All four are correct — graphs are an incredibly flexible data structure. Text (A) can be represented as a graph where words are nodes and co-occurrence or dependency relations are edges (e.g., TextRank). Movie reviews (B) can be modelled as a bipartite graph of users and movies, with reviews as weighted edges. Social networks (C) are the canonical graph example — users are nodes, friendships or follows are edges. Web browsing history (D) can form a graph of webpages (nodes) connected by hyperlinks or sequential visits (edges). The key insight is: whenever you have entities and relationships between them, a graph is a valid representation.

Link prediction is the task of predicting whether a missing or future edge should exist between two nodes. Recommender systems (A) predict a link between a user node and a product/movie node — "will this user like this item?" is structurally identical to "should this edge exist?" "People you may know" (C) directly predicts missing friend/follow edges in a social network graph. Question answering (B) is wrong — QA systems like ChatGPT generate text based on language modelling, which is a sequence prediction task, not graph link prediction. Graph visualisation (D) is wrong — visualisation is a rendering/display task that works with existing known edges; it does not predict new ones.

Edges with no direction (A) — in an undirected graph, if A is connected to B, then B is equally connected to A; there is no "from" or "to". This directly implies a symmetric adjacency matrix (B) — if A[i][j] = 1 then A[j][i] = 1 as well, so the matrix equals its own transpose. C is wrong — planarity (the ability to draw a graph without edge crossings) is a separate property with no relationship to directedness; many undirected graphs are non-planar (e.g., K₅ or K₃,₃). D is wrong — in-degree and out-degree are concepts from directed graphs; undirected graphs only have a single "degree" per node.

A bipartite graph has nodes split into two disjoint sets U and V such that every edge connects a node in U to a node in V — no edges exist within the same set (A). A classic example is a user-movie graph in recommender systems: users form one set, movies the other, and edges represent ratings. B is wrong — this is the opposite of bipartite; edges within the same set are precisely what bipartite graphs forbid. C is wrong — "two-way relationships" sounds like undirected edges, which is a different concept; bipartite refers to the structure of the node sets, not edge direction. D is wrong — a DAG is a directed acyclic graph, which is an entirely different property unrelated to bipartiteness.

In a weighted graph, each edge carries a numerical value (weight). A is true — the defining property is that edges have associated numerical values. D is true — these weights commonly encode real-world quantities such as road distances, travel costs, similarity scores, or signal strengths. B is wrong — weighted graphs can be either directed or undirected; directedness and weightedness are independent properties. For example, a weighted undirected graph could represent a road network where distances are symmetric. C is wrong — the weights belong to edges in a weighted graph, not to nodes; node weights are a separate concept that exists but does not define a "weighted graph."

The correct AUC formula for link prediction is: AUC = (n' + 0.5 × n'') / n, where n' = times missing link scores higher (52), n'' = ties (27), and n = total pairs (150). Ties count as half because neither link clearly wins. So: AUC = (52 + 0.5 × 27) / 150 = (52 + 13.5) / 150 = 65.5 / 150 ≈ 0.437. None of options A–D equal 0.437, so the answer is E — None of the above. The distractors are all wrong: A ignores ties, B uses the wrong numerator, C and D use incorrect logic. Always remember to account for tied pairs in the AUC calculation.

Word representation learning (e.g., Word2Vec) works by learning embeddings from co-occurrence or interaction frequency between entities. The key test: does the "word frequency" analogue capture a meaningful, recurring interaction signal? A is correct — users are entities (words) and following relationships capture how often they interact with others (frequency analogue). C is correct — webpages are entities and hyperlinks encode structural co-occurrence, exactly like word co-occurrence in documents. E is correct — movies and users as entities, with ratings as the interaction signal, maps naturally to the Word2Vec framework (similar to item2vec). B is wrong — products should be the "context" (like surrounding words), not mapped as "frequency"; the mapping is inverted. D is wrong — answers are not a frequency signal for questions; the question–answer relationship is a one-to-many semantic pairing, not a co-occurrence count.