{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"name":"python","version":"3.11.13","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"},"kaggle":{"accelerator":"none","dataSources":[{"sourceId":116062,"databundleVersionId":14084779,"sourceType":"competition"}],"dockerImageVersionId":31192,"isInternetEnabled":true,"language":"python","sourceType":"notebook","isGpuEnabled":false}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Graph topological sort problems\n\nThis kernel is made to illustrate the problems of Graph implementation provided by the hosts. This could potentially impact the evaluation. Even though I believe the impact should not be critical since affecting only a few terms, I d like to highlight the issue\n\nThe idea is following: there is propagation function that is applied to both targets and preditions during evaluation. The function is provided below:\n```python\ndef propagate(matrix, ont, order, mode='max'):\n    \"\"\"\n    Update inplace the score matrix (proteins x terms) up to the root taking the max between children and parents\n    \"\"\"\n    if matrix.shape[0] == 0:\n        raise Exception(\"Empty matrix\")\n\n    deepest = np.where(np.sum(matrix[:, order], axis=0) > 0)[0][0]\n    if deepest.size == 0:\n        raise Exception(\"The matrix is empty\")\n\n    # Remove leaves\n    order_ = np.delete(order, [range(0, deepest)])\n\n    for i in order_:\n        # Get direct children\n        children = np.where(ont.dag[:, i] != 0)[0]\n        if children.size > 0:\n            # Add current terms to children\n            cols = np.concatenate((children, [i]))\n            if mode == 'max':\n                matrix[:, i] = matrix[:, cols].max(axis=1)\n            elif mode == 'fill':\n                # Select only rows where the current term is 0\n                rows = np.where(matrix[:, i] == 0)[0]\n                if rows.size:\n                    idx = np.ix_(rows, cols)\n                    matrix[rows, i] = matrix[idx].max(axis=1)\n    return\n```\n\nThe key point here is the loop over the `order_` indices. `order` argumnent is the attribute of the parsed obo graph and it defines the order of terms processing, which is important - children should always be processed before parents. The example how it is called:\n\n```python\npropagate(matrix, ontologies[ns], ontologies[ns].order, mode='max')\nlogging.debug(\"gt matrix propagated {} {} \".format(ns, matrix))\n```\n\nTo ensure the correct order, `Graph` class implements the `.top_sort` method. It is called inside the `__init__`, so, parsed graph already should be properly sorted. The issue is - there are some term pairs that seems to have the wrong order. Let's check this out","metadata":{}},{"cell_type":"code","source":"# This Python 3 environment comes with many helpful analytics libraries installed\n# It is defined by the kaggle/python Docker image: https://github.com/kaggle/docker-python\n# For example, here's several helpful packages to load\nimport sys\nimport numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\n\n# Input data files are available in the read-only \"../input/\" directory\n# For example, running this (by clicking run or pressing Shift+Enter) will list all files under the input directory\n\nimport os\nfor dirname, _, filenames in os.walk('/kaggle/input'):\n    for filename in filenames:\n        print(os.path.join(dirname, filename))\n\n# You can write up to 20GB to the current directory (/kaggle/working/) that gets preserved as output when you create a version using \"Save & Run All\" \n# You can also write temporary files to /kaggle/temp/, but they won't be saved outside of the current session","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true,"execution":{"iopub.status.busy":"2025-11-29T21:04:17.152218Z","iopub.execute_input":"2025-11-29T21:04:17.152531Z","iopub.status.idle":"2025-11-29T21:04:17.536530Z","shell.execute_reply.started":"2025-11-29T21:04:17.152505Z","shell.execute_reply":"2025-11-29T21:04:17.535603Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Get the metric code\n","metadata":{}},{"cell_type":"code","source":"!git clone https://github.com/claradepaolis/CAFA-evaluator-PK.git\n\nsys.path.append('CAFA-evaluator-PK/src')\nfrom cafaeval.parser import obo_parser, ia_parser","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:20:46.572219Z","iopub.execute_input":"2025-11-29T22:20:46.572583Z","iopub.status.idle":"2025-11-29T22:20:46.716575Z","shell.execute_reply.started":"2025-11-29T22:20:46.572552Z","shell.execute_reply":"2025-11-29T22:20:46.715432Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Read the graph using the provided parser\n\n","metadata":{}},{"cell_type":"markdown","source":"Now, we will parse the .obo file and obtain the graph ","metadata":{}},{"cell_type":"code","source":"ontologies = obo_parser(\n    obo_file='/kaggle/input/cafa-6-protein-function-prediction/Train/go-basic.obo', \n    valid_rel=(\"is_a\", \"part_of\"), \n    ia_file='/kaggle/input/cafa-6-protein-function-prediction/IA.tsv', \n    orphans=True\n)\n\nontologies","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T21:08:53.894670Z","iopub.execute_input":"2025-11-29T21:08:53.895089Z","iopub.status.idle":"2025-11-29T21:08:59.044073Z","shell.execute_reply.started":"2025-11-29T21:08:53.895060Z","shell.execute_reply":"2025-11-29T21:08:59.043202Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Case 1\n\nLet's check it detailed. It is the part of biological process. Select this sub graph","metadata":{}},{"cell_type":"code","source":"G = ontologies['biological_process']","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T21:10:44.963185Z","iopub.execute_input":"2025-11-29T21:10:44.963555Z","iopub.status.idle":"2025-11-29T21:10:44.968402Z","shell.execute_reply.started":"2025-11-29T21:10:44.963527Z","shell.execute_reply":"2025-11-29T21:10:44.967197Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"There is a term `GO:0006338` which has 2116 index in `.terms_list`. Let's check its info","metadata":{}},{"cell_type":"code","source":"G.terms_list[2116]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:06:15.075260Z","iopub.execute_input":"2025-11-29T22:06:15.075592Z","iopub.status.idle":"2025-11-29T22:06:15.081625Z","shell.execute_reply.started":"2025-11-29T22:06:15.075558Z","shell.execute_reply":"2025-11-29T22:06:15.080774Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":" According to the node data, we can see, it has single parent, that has index 2112. Let's check this term, it is `GO:0006325`. We can see index 2116 of term `GO:0006338` in the children list, so, information is consistent\n","metadata":{}},{"cell_type":"code","source":"G.terms_list[2112]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:05:11.113505Z","iopub.execute_input":"2025-11-29T22:05:11.114864Z","iopub.status.idle":"2025-11-29T22:05:11.124459Z","shell.execute_reply.started":"2025-11-29T22:05:11.114821Z","shell.execute_reply":"2025-11-29T22:05:11.123204Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"According to that we have to process 2116 before 2112 at the propagation stage. However, let's check the actual order, provided by graph","metadata":{}},{"cell_type":"code","source":"G.order.index(2116), G.order.index(2112)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T21:13:56.764797Z","iopub.execute_input":"2025-11-29T21:13:56.765730Z","iopub.status.idle":"2025-11-29T21:13:56.773487Z","shell.execute_reply.started":"2025-11-29T21:13:56.765692Z","shell.execute_reply":"2025-11-29T21:13:56.772541Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Other cases found\n## Case 2","metadata":{}},{"cell_type":"code","source":"G.terms_list[2597]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:24:09.851373Z","iopub.execute_input":"2025-11-29T22:24:09.851774Z","iopub.status.idle":"2025-11-29T22:24:09.859132Z","shell.execute_reply.started":"2025-11-29T22:24:09.851716Z","shell.execute_reply":"2025-11-29T22:24:09.858190Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"G.terms_list[2596]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:24:10.022439Z","iopub.execute_input":"2025-11-29T22:24:10.022725Z","iopub.status.idle":"2025-11-29T22:24:10.029426Z","shell.execute_reply.started":"2025-11-29T22:24:10.022706Z","shell.execute_reply":"2025-11-29T22:24:10.028556Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"G.order.index(2597), G.order.index(2596)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:24:37.404584Z","iopub.execute_input":"2025-11-29T22:24:37.405174Z","iopub.status.idle":"2025-11-29T22:24:37.414767Z","shell.execute_reply.started":"2025-11-29T22:24:37.405136Z","shell.execute_reply":"2025-11-29T22:24:37.413845Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Case 3","metadata":{}},{"cell_type":"code","source":"G.terms_list[17210]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:26:06.927282Z","iopub.execute_input":"2025-11-29T22:26:06.927650Z","iopub.status.idle":"2025-11-29T22:26:06.934316Z","shell.execute_reply.started":"2025-11-29T22:26:06.927618Z","shell.execute_reply":"2025-11-29T22:26:06.933061Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"G.terms_list[2620]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:26:07.123127Z","iopub.execute_input":"2025-11-29T22:26:07.123434Z","iopub.status.idle":"2025-11-29T22:26:07.130515Z","shell.execute_reply.started":"2025-11-29T22:26:07.123411Z","shell.execute_reply":"2025-11-29T22:26:07.129663Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"G.order.index(17210), G.order.index(2620)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:26:07.325453Z","iopub.execute_input":"2025-11-29T22:26:07.325819Z","iopub.status.idle":"2025-11-29T22:26:07.334024Z","shell.execute_reply.started":"2025-11-29T22:26:07.325792Z","shell.execute_reply":"2025-11-29T22:26:07.333043Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"## Case 4\n\nThe last one belongs to cellular component","metadata":{}},{"cell_type":"code","source":"G = ontologies['cellular_component']\nG.terms_list[596]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:29:23.262970Z","iopub.execute_input":"2025-11-29T22:29:23.263299Z","iopub.status.idle":"2025-11-29T22:29:23.270453Z","shell.execute_reply.started":"2025-11-29T22:29:23.263277Z","shell.execute_reply":"2025-11-29T22:29:23.269396Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"G.terms_list[303]","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:29:23.504985Z","iopub.execute_input":"2025-11-29T22:29:23.505303Z","iopub.status.idle":"2025-11-29T22:29:23.513254Z","shell.execute_reply.started":"2025-11-29T22:29:23.505278Z","shell.execute_reply":"2025-11-29T22:29:23.512070Z"}},"outputs":[],"execution_count":null},{"cell_type":"code","source":"G.order.index(596), G.order.index(303)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:30:03.896617Z","iopub.execute_input":"2025-11-29T22:30:03.896986Z","iopub.status.idle":"2025-11-29T22:30:03.905060Z","shell.execute_reply.started":"2025-11-29T22:30:03.896960Z","shell.execute_reply":"2025-11-29T22:30:03.903819Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"Just to compare, the order is correct for second parent","metadata":{}},{"cell_type":"code","source":"G.order.index(596), G.order.index(1844)","metadata":{"trusted":true,"execution":{"iopub.status.busy":"2025-11-29T22:32:11.874365Z","iopub.execute_input":"2025-11-29T22:32:11.874672Z","iopub.status.idle":"2025-11-29T22:32:11.880725Z","shell.execute_reply.started":"2025-11-29T22:32:11.874648Z","shell.execute_reply":"2025-11-29T22:32:11.879929Z"}},"outputs":[],"execution_count":null},{"cell_type":"markdown","source":"# Conclusion\n\nThese cases are the only inconsistetncy I found at the moment, the rest terms ordering looks fine. Kindly ask the hosts to check that","metadata":{}}]}